本文详细介绍了 C++ STL 中的关联式容器，包括 map、set、multimap 和 multiset。内容涵盖键值对结构、各容器的特性差异（如元素唯一性、底层红黑树结构）、常用接口及操作复杂度。此外，文章对比了 AVL 树与红黑树的平衡机制，深入讲解了红黑树的插入调整策略（变色、旋转）及迭代器实现原理，并提供了相关模拟实现的参考链接。
键值对用来表示具有一一对应关系的一种结构，该结构中一般只包含两个成员变量 key 和 value，key 代表键值，value 表示与 key 对应的信息。
template <class T1, class T2> struct pair { T1 first; T2 second; pair(): first(T1()), second(T2()) {} pair(const T1& a, const T2& b): first(a), second(b) {} };
根据应用场景的不同，STL 总共实现了两种不同结构的关联式容器：树型结构与哈希结构。树型结构的关联式容器主要有四种：map、set、multimap、multiset。这四种容器的共同点是使用平衡二叉搜索树 (即红黑树) 作为其底层结构。
第一个模板参数可以认为是 key，也可以认为是 value，最后 set 底层元素是<T ,T>。第二个模板参数是比较规则，可以认为是底层红黑树中序的顺序，如果是小于比较那红黑树的中序就是升序，如果是大于比较那红黑树的中序就是降序。第三个模板参数是空间配置器类型。
默认构造，初始化一个空 set。
返回一个迭代器，迭代器中的红黑树节点指针指向红黑树最小节点。
返回红黑树中最大节点的下一个位置的迭代器，可以理解为迭代器中红黑树节点指针是 nullptr。
判断 set 是不是为空，也就是红黑树是不是为空。
返回 set 中元素个数，即红黑树中节点个数。
往 set 中插入元素，value_type 就是 key 的类型，如果已经存在，那就返回元素对应的迭代器，还有 false 表示插入失败。假如不存在，那就插入，然后返回插入元素的迭代器，还有 true 表示插入成功。
**第一个 erase 函数：**根据迭代器先查找，然后删除迭代器指向的元素。
**第二个 erase 函数：**删除所有键为 val 的元素，返回删除元素个数。
set 中只有一个成员红黑树，交换两个 set 其实就是交换红黑树。
清理底层红黑树所有节点。
查找键为 val 的元素，如果找不到就返回 end()，如果找到了就返回元素对应的迭代器。
返回 set 中键为 val 的元素的个数，因为 set 中不允许元素重复，所以这个返回值只会是 0 或 1。
第一个模板参数可以认为是 key，也就是键的类型。第二个模板参数是 value，也就是值的类型，最终 map 底层元素的类型其实就是<key，value>。第三个模板参数是比较规则，如果是小于比较那红黑树的中序就是升序，如果是大于比较那红黑树的中序就是降序。第四个模板参数是空间配置器类型。
默认构造，初始化一个空 map。
返回一个迭代器，迭代器中的红黑树节点指针指向红黑树最小节点。
返回红黑树中最大节点的下一个位置对应的迭代器，可以理解为迭代器中红黑树节点指针是 nullptr。
判断 map 是不是为空，也就是红黑树是不是为空。
返回 map 中元素个数，即红黑树中节点个数。
往 map 中插入元素，注意这里 value_type 是 pair<Key，Value>，如果已经存在，那就返回元素对应的迭代器，还有 false 表示插入失败。假如不存在，那就插入，然后返回插入元素的迭代器，还有 true 表示插入成功。
**第一个 erase 函数：**根据迭代器先查找，然后删除迭代器指向的元素。
**第二个 erase 函数：**删除所有键为 k 的元素，返回删除元素个数。
map 中只有一个成员红黑树，交换两个 map 其实就是交换红黑树。
清理底层红黑树所有节点。
查找键为 k 的元素，如果找不到就返回 end()，如果找到了就返回元素对应的迭代器。
返回 map 中键为 k 的元素的个数，因为 map 中不允许元素重复，所以这个返回值只会是 0 或 1。
map 的 operator[] 会返回键为 k 的元素对应的值 value 的引用。这个函数是一个插入查询函数，该函数会先尝试插入<k, Value()>的元素，如果键为 k 的元素已存在，那就插入失败，insert 会返回已存在元素的迭代器还有 false，operator[] 利用迭代器返回已存在元素对应值的引用，如果插入成功，insert 就就返回新插入元素的迭代器和 true，然后 operator[] 利用迭代器返回元素中值的引用。
(*((this->insert(make_pair(k,mapped_type()))).first)).second
multimap 和 map 的唯一不同就是：map 中的键 key 是唯一的，而 multimap 中键 key 是可以重复的。
AVL 树是在二叉搜索树的基础上添加了平衡因子，用来使搜索树保持平衡，对于一颗 AVL 树，要么是一颗空树，要么其每个节点都满足左右子树高度差不超过 1。
template<class T> struct AVLTreeNode { AVLTreeNode(const T& data) : _pLeft(nullptr), _pRight(nullptr), _pParent(nullptr) , _data(data), _bf(0) {} AVLTreeNode<T>* _pLeft; // 该节点的左孩子 AVLTreeNode<T>* _pRight; // 该节点的右孩子 AVLTreeNode<T>* _pParent; // 该节点的双亲 T _data; int _bf; // 该节点的平衡因子 };
AVL 树就是在二叉搜索树的基础上引入了平衡因子，因此 AVL 树也是二叉搜索树。AVL 树的插入过程可以分为两步：
bool Insert(const T& data) {
// 1. 先按照二叉搜索树的规则将节点插入到 AVL 树中
// ...
// 2. 新节点插入后，AVL 树的平衡性可能会遭到破坏，此时就需要更新平衡因子，并检测是否
//破坏了 AVL 树的平衡性
/* pCur 插入后，pParent 的平衡因子一定需要调整，在插入之前，pParent 的平衡因子分为三种情况：-1，0, 1, 分以下两种情况：
1. 如果 pCur 插入到 pParent 的左侧，只需给 pParent 的平衡因子 -1 即可
2. 如果 pCur 插入到 pParent 的右侧，只需给 pParent 的平衡因子 +1 即可
此时：pParent 的平衡因子可能有三种情况：0，正负 1，正负 2
1. 如果 pParent 的平衡因子为 0，说明插入之前 pParent 的平衡因子为正负 1，插入后被调整
成 0，此时子树的高度没有变化，所以无需继续往上调整
2. 如果 pParent 的平衡因子为正负 1，说明插入前 pParent 的平衡因子一定为 0，插入后被更
新成正负 1，此时该子树的高度增加，所以需要往上继续调整
3. 如果 pParent 的平衡因子为正负 2，则 pParent 的平衡因子违反平衡树的性质，需要对其进
行旋转处理 */
while (pParent) {
// 更新双亲的平衡因子
if (pCur == pParent->_pLeft) pParent->_bf--;
else pParent->_bf++;
// 更新后检测双亲的平衡因子
if (0 == pParent->_bf)
{
break;
} else if (1 == pParent->_bf || -1 == pParent->_bf) {
// 插入前父节点的平衡因子是 0，插入后父节点的平衡因为为 1 或者 -1，说明以父节点
为根的二叉树的高度增加了一层，因此需要继续向上调整
pCur = pParent; pParent = pCur->_pParent;
} else {
// 双亲的平衡因子为正负 2，违反了 AVL 树的平衡性，需要对以 pParent 为根的树进行旋转处理
f(2 == pParent->_bf)
{
// ...
}
else
{
// ...
}
}
return true;
}
pCur 插入后，pParent 的平衡因子一定需要调整，在插入之前，pParent 的平衡因子分为三种情况：-1，0, 1, 分以下两种情况：
此时：pParent 的平衡因子可能有三种情况：0，正负 1，正负 2
parent 平衡因子为 -2：
为 -2 说明 parent 左边高，那就找到 parent 左孩子节点 subL，假如 subL 的平衡因子为 -1，说明还是左边高，那就一个 parent 的右旋即可。
假如 subL 的平衡因子为 1，那就说明右边高，这里 subLR 的平衡因子会影响最后 parent 和 subL 的平衡因子，却不会影响旋转的方式。
注意：
1、所谓双旋，起始就是两次单旋而已
2、假如只需要一次单旋，那么会涉及两个节点的平衡因子的改变，且这两个节点平衡因子最后都会是 0
3、假如需要两次旋转，会涉及到三个节点，其中会有两个节点的平衡因子最后是 0，另一个节点平衡因子根据 subLR 或 subRL 一开始的平衡因子来决定
4、一次单旋中，会涉及到四个节点，其中有两个节点都可能为空（最上面和最下面），最终需要调整的指针个数是 4~6，两个不可能为空的节点各有两个指针需要调整，那两个可以为空的节点每有一个不为空，那就会多一个需要调整的指针
parent 的平衡因子为 2：
仿照为 -2 的思路即可
AVL 树是在二叉搜索树的基础上添加了平衡因子的设置，所以 AVL 树的验证分为两步，一个是二叉搜索树性质的验证，另一个是平衡树性质的验证
红黑树是在搜索树的基础上添加了颜色规则，对于一颗红黑树，要么该树是一颗空树，要么该树的根节点是黑，每条路径上都有相同数量的黑色节点，且不能有相邻的红色节点。
红黑树不像 AVL 树一样保证绝对的平衡，而是保证该树的最长路径不会超过最短路径的二倍，保证的是相对的平衡，这样放宽条件可大大减少旋转次数提高效率。
为什么最长路径不超过最短路径的二倍？
每条路径上的黑色节点个数相同，不能有相邻的红色节点，所以最长路径就是红色间隔黑色，而最短路径就是只有黑色，所以最长路径是最短路径的二倍。
// 节点的颜色
enum Color{RED, BLACK};
// 红黑树节点的定义
template<class ValueType> struct RBTreeNode {
RBTreeNode(const ValueType& data = ValueType(), Color color = RED)
: _pLeft(nullptr), _pRight(nullptr), _pParent(nullptr)
, _data(data), _color(color) {}
RBTreeNode<ValueType>* _pLeft; // 节点的左孩子
RBTreeNode<ValueType>* _pRight; // 节点的右孩子
RBTreeNode<ValueType>* _pParent; // 节点的双亲 (红黑树需要旋转，为了实现简单给出该字段)
ValueType _data; // 节点的值域
Color _color; // 节点的颜色
};
**注意：**红黑树节点的默认构造我们给的是红色，因为如果插入黑色节点，那么一定会破坏每条路径有相同数量黑色节点的规则，而如果插入红色节点则不一定破坏。
红黑树是在二叉搜索树的基础上加上颜色条件，因此红黑树的插入可分为两步：
插入红色新节点 cur，如果 parent 是黑色，那就不用调整。如果 parent 是红色，那就得调整，因为红黑树的根节点是黑色，所以 parent 肯定不是根节点，不是根节点那 parent 的父节点肯定存在，因为不能有相邻红色节点，所以 grandfa 一定是黑色，这时我们要根据叔叔节点来判断调整策略，我们需要先判断 parent 是 grandfa 的哪个孩子，然后就能得到叔叔节点了。
只需要将 parent 和 uncle 变为黑色，grandfa 变为红色，grandfa 子树每条路径的黑色节点个数不变，但需要往上继续调整，因为变红的 granfa 很有可能会再次导致有相邻的红色节点。
cur 是 parent 的左孩子还是右孩子不重要，因为调整策略是给 parent 和 uncle 变色，根本就没有旋转。
这时 cur 是 parent 的左孩子还是右孩子是有关系的，因为这时必须涉及旋转。
假如 parent 是左孩子，cur 也是左孩子，那这时就 grandfa 右旋，右边的路径黑色节点个数不变，左边的黑色节点个数减 1，然后 grandfa 变色，右边路径的黑色节点个数也减 1，然后 parent 再变成黑色，所有路径黑色节点个数加一，和之前一样，并且此时不再需要往上继续调整了，因为 parent 是子树的根且是黑色。
假如 parent 是左孩子，cur 是右孩子，那这时单单一个右旋加变色就不行了，因为最后 cur 和 grandfa 都是红色，还是不合规则，所以要进行两次旋转，先对 parent 左旋，然后对 grandfa 右旋，最后将 grandfa 和变成红，cur 变成黑。
红黑树是在二叉搜索树的基础上添加了颜色规则，所以要验证的有四点，中序是否有序来检验是不是搜索树，根节点是否为黑、是否不存在相邻的红色节点、每条路径上黑色节点个数是否相同三点保证是平衡树，如果都满足就是红黑树。
红黑树和 AVL 树都是高效的平衡二叉搜索树，查询的时间复杂度都是 O(log n)，红黑树不追求绝对平衡，其只保证最长路径不超过最短路径的 2 倍，相对而言，减少了插入删除导致旋转的次数，所以在经常进行增删的结构中性能比 AVL 树更优，而且红黑树实现比较简单，所以实际运用中红黑树更多。
STL 明确规定，begin() 与 end() 代表的是一段前闭后开的区间，而对红黑树进行中序遍历后可以得到一个有序的序列，因此，begin() 返回的迭代器指向的是红黑树中最小节点 (即最左侧节点)，end() 返回的迭代器指向的是最大节点 (最右侧节点) 的下一个位置，关键是最大节点的下一个位置在哪块？我们在设计红黑树迭代器的时候，其实结构和链表的迭代器结构差不多，里面有一个红黑树节点的指针，对于最大节点的下一个位置，我们选用的方案是让红黑树节点指针的值为 nullptr，然后 end()--会使红黑树节点指针指向最大节点，要实现这个操作，我们必须在迭代器中记录红黑树根节点才可以，不然仅凭一个 nullptr 如何找到最大节点。
++ 操作就是让红黑树节点指针指向下一个键更大的节点，如果当前节点右子树不为空，那下一个就是右子树的最小节点，如果为空，左子树都是比该节点小的，所以得往上找该节点的（右向父节点），就是父节点的左子树包含该节点。
-- 操作就是让红黑树结点指针指向上一个更小的值，如果该节点的左子树不为空，那就应该指向左子树中最大节点，如果左子树为空，那右子树全是比该节点大的，不和条件，所以要往上找左向父节点，也就是父节点右子树包含该节点。
总结：
微信公众号「极客日志」，在微信中扫描左侧二维码关注。展示文案：极客日志 zeeklog
使用加密算法（如AES、TripleDES、Rabbit或RC4）加密和解密文本明文。 在线工具，加密/解密文本在线工具，online
将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具，Base64 字符串编码/解码在线工具，online
将字符串、文件或图像转换为其 Base64 表示形式。 在线工具，Base64 文件转换器在线工具，online
将 Markdown（GFM）转为 HTML 片段，浏览器内 marked 解析；与 HTML 转 Markdown 互为补充。 在线工具，Markdown 转 HTML在线工具，online
将 HTML 片段转为 GitHub Flavored Markdown，支持标题、列表、链接、代码块与表格等；浏览器内处理，可链接预填。 在线工具，HTML 转 Markdown在线工具，online
通过删除不必要的空白来缩小和压缩JSON。 在线工具，JSON 压缩在线工具，online