一、关联式容器
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一个设置为>=，一个设置为>。这样刚好可以将我们输入值所处的区间进行控制，刚好满足左闭右开。无论是构造也好，删除也好，插入也好都是刚好十分方便的。
