《STL源码剖析》之关联式容器
这是 herongwei 的第 88 篇原创
阅读本文大概需要 8.88 分钟。
前面讲了常用的 STL 的序列式容器，如果忘记了可以查看这里：
今天继续讲一讲 STL 关联式容器的一些核心的知识点。
STL 关联式容器，可以看做一种小型的数据库，我们使用数据库的时候，不就是希望通过一个 key 查找一个value吗？用 key 关键字去找我们需要的数据。
1、rb_tree
rb_tree 是一种平衡二元查找树，rb_tree 提供两种 insert 操作：insert_unique() insert_equal()。
调用 insert_unique() 表示结点的 key 一定在整个 tree 中独一无二，否则安插失败；调用 insert_equal() 表示结点的 key 可以重复，但是重复的结点应该放在哪里呢？一般是在重复结点的附近。
当一组数据通过构造成一棵 rb_tree 之后，通过遍历其中的元素就是按照一定的规则顺序访问这些元素。
2、set/multiset
set / multiset 是以 rb_tree 为底层结构，因此有元素自动排序特性排序的依据就是key，而 set / multiset 元素的key和value合一。
提供迭代器访问元素，但是无法使用迭代器改变元素值，因为 key就是 value，set的元素必须独一无二，因此 insert 用的是 rb_tree 的 insert_unique() 函数。
set 的源码
public: typedef typename rep_type::const_iterator iterator注意这里的迭代器是 const 类型，所以迭代器不允许修改，因为key 就是 value，所以你你修改元素就是修改 key ，所以不能修改！
multiset 元素的 key 可以重复。
因此 insert 用的是 rb_tree 的insert_equal() 函数。
3、map/multimap
map/multimap 以 rb_tree 为底层结构，因此有元素自动排序特性，排序的依据是 key。
map/multimap 提供遍历操作以及 iterator，按正常规则（++iter）遍历便能得到排序状态。
我们要注意的是：我们无法使用 map/multimap 的 iterator 改变元素的 key，这是怎么做到的呢？看一下源码，我们知道了，原来是因为对 key 进行了 const 限定，将用户传进来的 key，value 组合成了一对 pair<const key ,T>value_type。
但可以用它改变元素的 value，因此 map/multimap 内部自动将 user 的指定的 key type 设为 const ，如此便能禁止 user 对元素的 key 赋值。
map 的元素的 key 必须独一无二，
因此 insert 用的是 rb_tree 的 insert_unique()函数。
而 multimap 允许元素重复，
因此 insert 用的是 rb_tree 的 insert_equal()函数。
4、map/set 基本操作
map / set 基本的操作函数是一样的，由上面也可得知，因为底层都是 rb_tree 实现。
begin() 返回指向map头部的迭代器clear(） 删除所有元素count() 返回指定元素出现的次数empty() 如果map为空则返回trueend() 返回指向map末尾的迭代器equal_range() 返回集合中与给定值相等的上下限的两个迭代器erase() 删除一个元素find() 查找一个元素get_allocator() 返回map的配置器insert() 插入元素key_comp() 返回比较元素key的函数lower_bound() 返回键值>=给定元素的第一个位置max_size() 返回可以容纳的最大元素个数rbegin() 返回一个指向map尾部的逆向迭代器rend() 返回一个指向map头部的逆向迭代器size() 返回map中元素的个数swap() 交换两个mapupper_bound() 返回键值>给定元素的第一个位置value_comp() 返回比较元素value的函数5、为何 map 和 set 的插入删除效率比其他序列容器高？
对于关联容器来说，插入和删除元素，不需要做内存拷贝和内存移动的动作，容器内所有元素都是以节点的方式来存储，其节点结构和链表差不多，指向父节点和子节点。结构图可能如下：
因此，插入的时候只需要稍做变换，把节点的指针指向新的节点就可以了。删除的时候类似，稍做变换后把指向删除节点的指针指向其它节点也 OK 了。这里的一切操作就是指针的操作，和内存移动没有关系。
6、关于迭代器失效的问题？
对于序列式容器来说， 比如 vector ，每一次删除和插入，指针都有可能失效，调用 push_back 在尾部插入也是如此。
因为为了保证内部数据的连续存放，iterator 指向的那块内存在删除和插入过程中可能已经被其他内存覆盖或者内存已经被释放了。
即 push_back 的时候，容器内部空间可能不够，需要一块新的更大的内存，vector 的动态扩容机制会把以前的内存释放，申请新的更大的内存，复制已有的数据元素到新的内存，把需要插入的元素放到最后，最后释放原有的空间。
也就是经典的三步操作：申请-搬移-释放，那么以前的内存指针自然就不可用了。
所以，使用 vector 有几个注意点：
1）注意插入和删除元素后迭代器失效的问题；
2）清空 vector 数据时，如果保存的数据项是指针类型，需要逐项 delete，否则会造成内存泄漏。
3）频繁调用 push_back() 影响：向 vector 的尾部添加元素，很有可能引起整个对象存储空间的重新分配，重新分配更大的内存，再将原数据拷贝到新空间中，再释放原有内存，这个过程是耗时耗力的，频繁对 vector 调用 push_back() 会导致性 能的下降。
对于关联式容器来说，iterator 这里就相当于指向节点的指针，内存没有变，因此指向内存的指针不会失效(当然被删除的那个元素本身已经失效了)。
总结：
迭代器失效分三种情况考虑，分别为数组型，链表型，树型数据结构。
数组型数据结构：该数据结构的元素是分配在连续的内存中，insert 和 erase 操作，都会使得删除点和插入点之后的元素挪位置，所以，插入点和删除掉之后的迭代器全部失效，也就是说insert(*iter) (或erase(*iter))，然后在 iter++，是没有意义的。
解决方法：erase(*iter) 的返回值是下一个有效迭代器的值。 iter =cont.erase(iter);
https://blog.csdn.net/lujiandong1/article/details/49872763
链表型数据结构：对于list型的数据结构，使用了不连续分配的内存，删除运算使指向删除位置的迭代器失效，但是不会失效其他迭代器.解决办法两种，erase(*iter) 会返回下一个有效迭代器的值，或者 erase(iter++).
树形数据结构：使用红黑树来存储数据，插入不会使得任何迭代器失效；删除运算使指向删除位置的迭代器失效，但是不会失效其他迭代器。.erase迭代器只是被删元素的迭代器失效，但是返回值为 void，所以要采用 erase(iter++) 的方式删除迭代器。
https://blog.csdn.net/lujiandong1/article/details/49872763
7、为什么工程中都喜欢红黑树？
3、首先说一下平衡二叉查找树的定义
二叉树中任意一个节点的左右子树的高度相差不能大于1。比如AVL树。红黑树严格意义上来不属于平衡二叉查找树，它从根节点到各个叶子节点的最长路径，有可能比最短路径大一倍。
4、平衡二叉树中的“平衡”的意思
就是让整棵树看起来比较“对称”。不会出现左右子树不会相差太大，不会出现左子树很高，右子树很矮的情况，这样让整棵树的高度相对来说低一些。相应的插入，查找，删除的操作效率高一些。
5、红黑树的由来
红黑树是一种平衡二叉树，它是为了解决普通二叉树在数据更新的过程中，复杂度退化的问题而产生的，高度近似 log2N，近似平衡，插入，删除，查找的时间复杂度是O（logn）（n=结点数）。
6、红黑树的一些特性：
1、红黑树的各项操作（插入、删除、查找等），复杂度都为 log(n) 。
2、 红黑树的五大特征：
a、节点要么为红色，要么为黑色；
b、根节点为黑色；
c、叶子节点为黑色（也就是最上面和最下面都是黑的）。
d、每个红色节点的左右孩子都是黑色（保证了从根节点到叶子节点不会出现连续两个红色节点）。
e、从任意节点到其每个叶子节点的所有路径，都包含相同数目的黑色节点。（d，e 是使得红黑树为平衡树的关键）。
7、和其它的对比：
1、AVL 树是一种高度平衡的树，所以查找效率很高，但是有利就有弊，AVL 树为了维持这种高度的平衡，就要付出更多的代价。每次插入，删除都要做调整，就比较复杂，耗时，所以对于有频繁插入，删除操作的数据集合场景下，不太适应 AVL 树。
2、红黑树只是做到了近视的平衡，不是一种严格的平衡，所以在维护平衡的成本上，要比 AVL 树低。
3、 如果你的应用中，搜索的次数远远大于插入和删除，那么选择AVL，如果搜索，插入删除次数几乎差不多，应该选择 rb_tree。
4、 总体来说，红黑树的插入，删除，查找各种操作都比较稳定，对于工程应用来说，要面对各种异常的情况，为了支撑这种工业级别的应用，更倾向于稳定的红黑树。
推荐阅读
认真的人，自带光芒！