【C++从0到王者】第三十一站：map与set（上）

一、关联式容器

STL中的部分容器，比如：vector、list、deque、forward_list(C++11)等，这些容器统称为序列式容器，因为其底层为线性序列的数据结构，里面存储的是元素本身。

那什么是关联式容器？它与序列式容器有什么区别？

关联式容器也是用来存储数据的，与序列式容器不同的是，其里面存储的是<key, value>结构的键值对，在数据检索时比序列式容器效率更高

二、pair键值对

用来表示具有一一对应关系的一种结构，该结构中一般只包含两个成员变量key和value，key代表键值，value表示与key对应的信息

stl里面对于pair的定义是这样的

template <class T1, class T2>
struct pair
{
  typedef T1 first_type;
  typedef T2 second_type;
  T1 first;
  T2 second;
  pair() : first(T1()), second(T2())
  {}
  pair(const T1& a, const T2& b) : first(a), second(b)
  {}
};

pair有三种构造函数，不难看出，分别是无参的构造，拷贝构造，以及通过两个值来进行构造

除了三种构造函数以外，它还有一种方式，也可以生成pair对象。这个不是一个成员函数，所以可以直接使用。

如上的一些构造函数的使用将在map中进行演示

三、set

1. set的介绍

如下图所示：

我们可以注意到它的模板参数是要比其他容器多一个的，这个容器我们也可以看到是一个仿函数。我们使用优先级队列的时候也用过这个仿函数

集合是按照特定顺序存储唯一元素的容器。

在一个集合中，元素的值也标识它(值本身就是键，类型为 T)，并且每个值必须是唯一的。集合中元素的值在容器中不能修改(元素总是 const 类型的)，但是可以从容器中插入或删除元素。

在内部，集合中的元素总是按照其内部比较对象(类型为 Compare )指示的特定严格弱排序标准排序。

在通过键访问单个元素时，set 容器通常比 unordered_set 容器慢，但是它们允许基于次序对子集进行直接迭代。

集合通常以二叉搜索树的形式实现。这颗二叉搜索树是红黑树。

set其实就相当于key模型的二叉搜索树

注意：set里面的值是不可以被修改的，它实现这一点的原理就是将迭代器和const迭代器都是const迭代器没有任何区别。

2. set的部分接口以及应用

可以注意到，一共有三个构造函数，第一个是全缺省的默认构造函数，第二个是迭代器区间构造，第三个是拷贝构造。

不过这个拷贝构造的代价比较大，因为它是一个树的拷贝，而且析构也一样有很大的代价。

还有一个接口是insert

这里的value_type就是T

还有很多接口其实看一眼就大概知道啥意思

比如如下代码：可以简单的测试一下代码

void test_set1()
{
  set<int> s;
  s.insert(1);
  s.insert(5);
  s.insert(2);
  s.insert(2);
  s.insert(2);
  s.insert(2);
  s.insert(4);
  s.insert(4);
  s.insert(4);
  s.insert(3);
  set<int>::iterator it = s.begin();
  while (it != s.end())
  {
    cout << *it << " ";
    it++;
  }
  cout << endl;
}
int main()
{
  test_set1();
  return 0;
}

我们可以发现，set可以自动去重和排序

而它的去重原理就是：一个值已经有了，我们就不插入即可

同时我们也可以试一下set的删除

auto pos = s.find(3);
  s.erase(pos);
  s.erase(4);
  for (auto e : s)
  {
    cout << e << " ";
  }
  cout << endl;

如上有演示了两种删除，从表面来看，看上去好像没有什么大的区别。我们可以认为下面的是通过上面的进行实现的。

不过在find中如果没有找到的话，是会直接报错的。

而下面如果没有找到是什么也不会发生的

不过我们可以加一个判断来解决这个问题

这是因为find找不到会返回一个end迭代器导致的

在容器中搜索与val等效的元素，如果找到则返回一个迭代器，否则返回一个迭代器给set::end。

但是我们知道算法库里面也有一个find，这个find似乎也能完成这个操作

其实这两个find是存在一定的差异的，set里面的find是根据二叉搜索树的性质来进行查找的（其实是红黑树，效率更优），时间复杂度为O(logN)，而算法库里面的find是一个一个查找的，时间复杂度为O(N)。

3. count

count的作用是，给一个值，然后返回它出现了几次。不过因为set容器里面的值是唯一的，所以一个元素在这里面，返回1，否则返回0

如下的代码可以演示find和count寻找一个数据的使用

void test_set2()
{
  set<int> s;
  s.insert(1);
  s.insert(5);
  s.insert(2);
  s.insert(4);
  s.insert(4);
  s.insert(3);
  set<int>::iterator it = s.begin();
  while (it != s.end())
  {
    cout << *it << " ";
    it++;
  }
  cout << endl;
  if (s.find(5) != s.end())
  {
    cout << "找到了" << endl;
  }
  if (s.count(5))
  {
    cout << "找到了" << endl;
  }
}
int main()
{
  test_set2();
  return 0;
}

4. lower_bound和upper_bound

返回迭代器到下界

返回一个迭代器，该迭代器指向容器中的第一个元素，该元素不被认为位于val之前(即，它要么等价，要么在val之后)。

该函数使用其内部比较对象(key_comp)来确定这一点，并返回一个迭代器，指向key_comp(element,val)将返回false的第一个元素。

如果用默认比较类型(less)实例化set类，则该函数返回一个指向不小于val的第一个元素的迭代器。

类似的成员函数upper_bound具有与lower_bound相同的行为，只是set包含一个与val等效的元素:在这种情况下，lower_bound返回一个指向该元素的迭代器，而upper_bound返回一个指向下一个元素的迭代器。

返回迭代器到上界

返回一个迭代器，该迭代器指向容器中被认为在val之后的第一个元素。

该函数使用其内部比较对象(key_comp)来确定这一点，并返回一个迭代器，指向key_comp(val,element)将返回true的第一个元素。

如果用默认比较类型(less)实例化set类，则该函数返回指向第一个大于val的元素的迭代器。

类似的成员函数lower_bound具有与upper_bound相同的行为，只是set包含一个与val等效的元素:在这种情况下，lower_bound返回一个指向该元素的迭代器，而upper_bound返回一个指向下一个元素的迭代器。

我们可以使用这段代码来进行验证

void test_set3()
{
  std::set<int> myset;
  std::set<int>::iterator itlow, itup;
  for (int i = 1; i < 10; i++) myset.insert(i * 10); // 10 20 30 40 50 60 70 80 90
  itlow = myset.lower_bound(30);                   
  itup = myset.upper_bound(60);                        
  myset.erase(itlow, itup);                     // 10 20 70 80 90
  for (auto e : myset)
  {
    cout << e << " ";
  }
  cout << endl;
}
int main()
{
  test_set3();
  return 0;
}

lower_bound和upper_bound一个设置为>=，一个设置为>。这样刚好可以将我们输入值所处的区间进行控制，刚好满足左闭右开。无论是构造也好，删除也好，插入也好都是刚好十分方便的。