目录
关联式容器：
查找快，插入快
STL中的主要代表：红黑树，hashtable
红黑树的基本原理
- 单个结点来看，左孩子小于根节点，右孩子大于根节点（二叉搜索树）
红黑树是什么，有什么意义：排序二叉树有不平衡的问题，可能左子树很长但是右子树很短，造成查询时性能不佳（logn退化成n），完全平衡的二叉树能保证层数平均，从而查询效率高，但是维护又很麻烦，每次插入和删除有很大的可能要大幅调整树结构。红黑树就是介于完全不平衡和完全平衡之间的一种二叉树，通过每个节点有红黑两种颜色、从节点到任意叶子节点会经过相同数量的黑色节点等一系列规则，实现了【树的层数最大也只会有两倍的差距】，这样既能提高插入和删除的效率，又能让树相对平衡从而有还不错的查询效率。从整体上讲，红黑树就是一种中庸之道的二叉树
- 平衡性要求并不高，并不像AVL二叉树一样要求左右高差<=1
- 为了提高插入效率，旋转操作更少
基本要求
- 每个节点要么是红色，要么是黑色
- 根节点和叶子结点（nil）是黑色的
- 如果一个结点是红色的，那么它的孩子是黑色的（不能连续两个红色）
- 任意节点到叶节点的树链中包含相同数量的黑色结点
变色和旋转
rbtree
红黑树是一种平衡的二分查找树
设计树的时候，最害怕的就是某一个树上过长，造成查找效率降级，所以就有这种平衡树
提供遍历的操作，ite++就能得到一个排序的状态（中序）
begin记录最左边结点，end记录最右边结点
但是，不应该通过iterator去改变元素值(key)，因为会破坏红黑树的排序规则
红黑树的设计本身，并没有要求是否可以重复key值，并且提供了两种insertion操作：insert_unique()和insert_equal()
如果调用第一个并且元素重复，就会安插失败
源码G2.9
key表示关键字类型
value表示key和data合起来的类型
keyofvalue表示如何从value中取出key
compare表示如何进行key的比较
header是一个虚拟的元素，他的孩子是数根节点，会使实现容易许多
Compare key_compare中，作为一个函数，没有大小，其实是0
但对于编译器来说，实现的过程中，会有一个大小为1，
由于内存对齐，最后的结果为12
sizeof的大小 12
示例
一个实例
key value都是int，value是key和data合起来的，所以，key就是value就是data
使用identity来取出元素，用less来比较元素
2.9
4.9
