一、概述
1、标准STL关联式容器分为set和map，以及这两大类的衍生体multiset和multimap。这些容器均以RB-tree完成，RB-tree也是
一个独立容器，但并不开放给外界使用。
2、SGI STL还提供了一个不在标准规格之列的关联式容器：hash table，以及以此为底层机制而完成的hash_set,hash_map
,hash_multiset,hash_multimap
3、所谓关联式容器，每笔数据都有一个键值和一个实值，set的键值就是实值，map的键值可以和实值分开。
4、关联式容器没有所谓头尾。
5、一般而言，关联式容器的内部结构式一个平衡二叉树，以便获得良好的搜寻效率。平衡二叉树有多种类型，其中并广泛运用于STL的
是RB-tree。
二、二叉搜索树
1、树，是十分基础的数据结构，几乎所有的操作系统都将文件存放在树状结构中，几乎所有的编译器都需要实现一个表达式树，文件
压缩所用的huffman算法，数据库所使用的B-tree，则是相当复杂的树状结构。
2、所谓二叉搜索树，可提供对数时间的元素插入和访问。二叉搜索树的节点放置原则是：
任何节点的键值一定大于其左子树中每一个节点的键值，并小于其右子树的键值。
3、二叉搜索树的插入，可从根节点开始，遇键值较大者向左，遇键值较小者向右，一直到尾端，即为插入点。
4、二叉搜索树的删除，分两种：
如果A只有一个子节点，直接将A的子节点连至A的父节点
如果A有两个子节点，就以右子树的最小节点取代A
三、AVL Tree
1、平衡的二叉搜索树，当平衡被破坏时，意味着X的左右两颗子树的高度相差2，可以分四种：
插入点位于C的左子节点的左子树---左左
插入点位于C的左子节点的右子树---左右
插入点位于C的右子节点的左子树---右左
插入点位于C的右子节点的右子树---右右
2、情况1和4彼此对称，称为外侧插入，可以采用单旋转操作调整，2和3，称为内侧插入，可以采用双旋转调整。
3、为什么称为双旋转，因为它可以利用两次单旋转完成。
4、单旋转和双旋转，都只需要将指针稍作调整，就可以迅速达成。
四、RB-tree
1、RB-tree，不仅是一个二叉搜索树，而且必须满足以下规则：
每个节点不是红色就是黑色
根节点为黑色
如果节点为红，其子节点必须为黑
任一节点至NULL（树尾端）的任何路径，所含之黑节点数必须相同。
2、根据规则4，新增节点必须为红，根据规则3，新增节点之父节点必须为黑。
当新节点根据二叉搜索树的规则到达其插入点，却未能符合上述条件时，就必须调整颜色并旋转树形。
3、RB-tree调整后可能产生不平衡状态（高度相差1以上），这倒没关系，因为RB-tree的平衡性本来就比AVL-tree弱
，然后RB-tree通常能够导致良好的平衡状态。是滴，经验告诉我们，RB-tree的搜索平均效率和AVL几乎相等。
4、RB-tree的节点设计
有红黑二色，并且拥有左右子节点，为了有更大的弹性，节点分为两层
5、RB-tree迭代器属于双向迭代器，但不具备随机定位能力。
五、set
1、set的特性是，所有元素都会根据元素的键值自动被排序。
2、set不允许两个元素有相同的键值。
3、可以通过set的迭代器改变set的元素值么？
不行，因为set元素值就是其键值，关系到set元素的排列规则。
六、map
1、map的特性是，所有元素都会根据元素的键值自动被排序。
2、map不允许两个元素有相同的键值
3、可以通过map的迭代器改变map的元素值么？
不行，因为map元素的键值，关系到map元素的排列规则。但可以修改元素的实值
七、multiset和multimap
1、multiset的特性以及用法和set完全相同，唯一的差别在于它允许键值重复。
2、multimap的特性以及用法和map完全相同，唯一的差别在于它允许键值重复。
八、hashtable
1、二叉搜索树具有对数平均时间的表现，但这样的表现构造在一个假设上：输入数据有足够的随机性
2、hashtable，在插入删除搜索上也具有“常数平均时间”，而且这种表现是以统计为基础的。
3、由于元素个数大于array容量，会产生碰撞问题。解决碰撞问题有许多种方法，包括：
线性探测、二次探测、开链等
4、开链
SGI STL采用开链手法，称hash table表格内的元素为桶子，至于桶子聚合体，则以vector完成。
判断元素的落脚处，通过调用hash function，取得一个可以执行取模运算的数值。
SGI STL以质数来设计表格大小，并且将28个质数计算好，以备随时访问，从53开始，逐渐呈现大约2倍的关系。
九、hash set、hash map、hash multiset、hash multimap
1、RB-trr有自动排序功能而hashtable没有，反应出来的结果是，set的元素有自动排序功能而hash set没有
2、hash map、hash multiset、hash multimap同理。
十、总结
关联式容器主要以RB-tree和hashtable为底层机制，所以有必要理清这两者是如何实现的。