在C++初阶的时候，我们已经接触了 STL 中的部分容器并进行了模拟实现，比如 vector、list、stack、queue 等，这些容器统称为序列式容器，因为其底层为线性序列的数据结构，里面存储的是元素本身；

同样，关联式容器也是用来存储数据的，但与序列式容器不同的是，关联式容器里面存储的是 结构的键值对，因此在数据检索时比序列式容器效率更高。

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

我们在上一节学习二叉搜索树的时候提到的 KV 模型 (key-value 模型) 中的 KV 其实就是键值对；我们可以用上一节中提到的英汉互译的例子来理解 key-value 键值对 – 现在要建立一个英汉互译的字典，那该字典中必然有英文单词与其对应的中文含义，而且，英文单词与其中文含义是一一对应的关系，即通过该应该单词，在词典中就可以找到与其对应的中文含义。

STL 中键值对的定义如下：(SGI 版本)

可以看到，C++ 中的键值对是通过 pair 类来表示的，pair 类中的 first 就是键值 key，second 就是 key 对应的信息 value；那么以后我们在设计 KV 模型的容器时只需要在容器/容器的每一个节点中定义一个 pair 对象即可；

这里有的同学可能会有疑问，为什么不直接在容器中定义 key 和 value 变量，而是将 key、value 合并到 pair 中整体作为一个类型来使用呢？这是因为 C++ 一次只能返回一个值，如果我们将 key 和 value 单独定义在容器中，那么我们就无法同时返回 key 和 value；而如果我们将 key、value 定义到另一个类中，那我们就可以直接返回 pair，然后再到 pair 中分别去取 first 和 second 即可。

make_pair 函数

由于 pair 是类模板，所以我们通常是以 显式实例化 + 匿名对象 的方式来进行使用，但是由于显式实例化比较麻烦，所以 C++ 还提供了 make_pair 函数，其定义如下：

如上，make_pair 返回的是一个 pair 的匿名对象，匿名对象会自动调用 pair 的默认构造完成初始化；但由于 make_pair 是一个函数模板，所以模板参数的类型可以根据实参来自动推导完成隐式实例化，这样我们就不用每次都显式指明参数类型了。

注：由于 make_pair 使用起来比 pair 方便很多，所以我们一般都是直接使用 make_pair，而不使用 pair。

根据应用场景的不同，STL 总共实现了两种不同结构的关联式容器 – 树型结构与哈希结构；树型结构的关联式容器主要有四种 – map、set、multimap、multiset，这四种容器的共同点是使用平衡二叉搜索树作为其底层结构，容器中的元素是一个有序的序列；本文将介绍这四个容器的使用。

set 是按照一定次序存储元素的容器，其底层是一棵平衡二叉搜索树，由于二叉搜索树的每个节点的值满足左孩子 < 根 < 右孩子，并且二叉搜索树中没有重复的节点，所以 set 可以用来排序、去重和查找，同时由于这是一棵平衡树，所以 set 查找的时间复杂度为 O(logN)，效率非常高；

同时，set 是一种 K模型 的容器，也就是说，set 中只有键值 key，而没有对应的 value，并且每个 key 都是唯一的；set 中的元素也不允许修改，因为这可能会破坏搜索树的结构，但是 set 允许插入和删除。

总结：

注：可能有的同学对 O(logN) 的时间复杂度没有什么具体的概念，那么我们可以列举一组数据大家就很清楚了：set 从1000个数据找查找某个数据最多找10次，从100万个数据中找某一个数据最多找20次，从10亿个数据中找某一个数据最多找30次；换一种说法，如果以身份证号作为 key 值存入 set 中 (假设内存足够)，那么我们从地球所有人类中查找某一个身份证号对应的人时最多只用找 31 次；相信现在大家对 O(logN) 是什么量级的存在已经有了很清楚的认识了。

构造

和传统容器一样，set 也支持单个元素构造、迭代器区间构造以及拷贝构造：

迭代器

迭代器也一样，包括正向迭代器和反向迭代器，正向和反向又分为 const 和 非const：

修改

set 有如下修改操作：

其中 swap 就是交换两棵树的根，clear 就是释放树中的所有节点，emplace 和 emplace_hint 我们放在 C++11 章节中学习，大家现在不用管它；最重要的修改操作是 insert 和 erase；

insert 支持插入一个值、在某个迭代器位置插入值、插入一段迭代器区间，我们学会第一个即可，插入的过程就是二叉搜索树的插入过程；需要注意的是 insert 的返回值是 pair 类型，pair 中第一个元素代表插入的迭代器位置，第二个元素代表是否插入成功 (插入重复节点会返回 false)：

erase 也有三种，常用的是第一种和第二种，删除指定键值的数据和删除指定迭代器位置的数据：

操作

set 还有一些其他操作相关的函数：

其中比较重要的只有 find，由于 set 中不允许出现相同的 key，因此在 set 中 count 函数的返回值只有1/0，可以说没有什么价值，set 中定义 count 主要是因为 count 在 multiset 中有作用，这里是为了保持一致；lower_bound 和 upper_bound 是得到一个左闭右开的迭代器区间，然后我们可以对这段区间进行某些操作，但实际中其实没什么人用；

find 的作用是在搜索树中查找 key 对应的节点，然后返回节点位置的迭代器，如果找不到，find 会返回 end()：

set 使用范例