关联式容器：
关联式容器主要有基于红黑树实现的set map multiset multimap 等和基于hashtable实现的hash_set hash_map hash_multiset hash_multimap。其中RB-tree容器是非公开的，hash_XX非标准的，而在c++11里面用unordered_set unordered_map unordered_multimap unordered_multiset等替代hash_xx;
目录
c++11里unorunordered_xx
平衡二叉树AVL树：
任何节点左右子树高度相差1；平衡性破坏通过旋转调整平衡性。
平衡性破坏时：
左左和右右都称为外侧，可以采用单旋进行调整；左右和右左都是内侧，可以进行双旋进行调整；
- 左左情况（左孩子(L)的左子树(L)上插入新结点，使原来平衡二叉树变得不平衡）
在向树中追加“节点1”的时候，根据定义我们知道这样会导致了“节点3"失衡，满足“左左情况“，
- 右右情况（右子树的右边节点）
- 左右情况（左子树的右边节点）
当我们插入”节点3“时，“节点5”处失衡，注意，找到”失衡点“是非常重要的，当面对”左右情况“时，我们将失衡点的左子树进行"右右情况旋转"，然后进行”左左情况旋转“，经过这样两次的旋转就OK了。
- 右左情况(右子树的左边节点）
红黑树：
一种弱平衡二叉树，红黑树确保没有一条路径会比其它路径长出两倍。相对于要求严格的AVL树来说，它的旋转次数少，所以对于搜索，插入，删除操作较多的情况下。
性质：
1.每个节点非红即黑
2.根节点是黑的;
3.每个叶节点（叶节点即树尾端NULL指针或NULL节点）都是黑的;
4.如果一个节点是红色的，则它的子节点必须是黑色的。
5.对于任意节点而言，其到叶子点树NULL指针的每条路径都包含相同数目的黑节点;
恢复红黑属性需要少量(O(log n))的颜色变更(这在实践中是非常快速的)并且不超过三次树旋转(对于插入是两次)。
红黑树的优点：
AVL树是高度平衡的，频繁的插入和删除，会引起频繁的rebalance，导致效率下降；红黑树不是高度平衡的，算是一种折中，插入最多两次旋转，删除最多三次旋转。
所以红黑树在查找，插入删除的性能都是O(logn)，且性能稳定，所以STL里面很多结构包括map底层实现都是使用的红黑树。
Hashtable
SGI STL采用开链法，负载因子可以大于1，buckets 桶子节点（vector）；
hashtable_node链表节点(自己维护链表节点)；
Hashtable迭代器：只有++没有--，维护桶的指针和当前链表的指针。
Hashtable的数据结构：开链法不要求表格的大小为质数，SGI STL以质数来设计表格大小，先将28质数（逐渐程2倍关系）计算好以备随时取用，同时提供一个函数，用来查询28个质数中最接近且大于某数的质数的函数。
Resize()： hashtable，当元素个数.size>桶个数.bucket_count则resize下一个质数（近似2倍）
Hashfunction定位元素：
调用bkt_num函数——>bkt_num函数调用hash function,取得一个可以取模的数值。
Hashfunction 大部分对于char int long 等整形都忠实的返回原值。对于const char*
unsigned long h = 0;
for(;s;s++)
{
h = 5*h+*s;
}
return (size_t )h;
//除了以上类别，hashtable无法处理，如string,float,double类型等，除非自定义hashfunction;
插入元素：
Insert_unique()函数：bkt_num()定位桶à遍历对应的链表à是否有重复的à有则不插入返回，否则头插元素。
Insert_equal()函数：bkt_num()定位桶à遍历对应的链表à是否有重复的à有则插入其后，否则头插元素。
Set map multiset multimap //基于未公开容器RB-tree 自排序 lon(N)搜索 STL标准
hash_set hash_multiset hash_map hash_multimap // 基于hashtable lon(N)搜索 非标准
c++11里unordered_XX
unordered_set unordered_map unordered_multiset unordered_multimap//标准c++11里
void unordered_container()
{
unordered_map<string, int>un_m = { {"ccc",3}, {"aaa",1},{"bbb",2 } };
un_m.insert({ "ddd",4 });
for (auto pos: un_m)
{
cout << pos.first << " " << pos.second << endl;
}
un_m.erase("ccc");
for (auto pos : un_m)
{
cout << pos.first << " " << pos.second << endl;
}
auto it = un_m.find("aaa");
cout << it->first << " " << it->second << endl;
cout << un_m.count("ddd") << endl;
//桶管理函数：允许我们查看桶的状态，必要时进行重组
cout<<un_m.bucket_count()<<endl;//正在使用的桶数量
cout << un_m.max_bucket_count()<<endl;//容器最多能容纳的桶的数量
cout << un_m.bucket_size(2) << endl;//第2个桶有几个元素
cout << un_m.bucket("ddd") << endl;//关键字为"ddd"在哪个桶里
cout << un_m.load_factor() << endl;//平均每个桶有几个元素
}