第五章 关联式容器
1、红黑树
operation: 左旋，右旋，变色， header实现技巧，平均查找时间复杂度nlog(n)
set/map/multiset/multimap
采用RB-tree红黑树实现；
删除/插入新元素，不会导致迭代器失效；
set/map不允许重复，multiset/multimap允许重复
3）hash_table
operation: hash function, vector<slist<key>>, vector作为buckets的容器。rehash遵循质数扩容
线性探测（存在primary clustering问题）、二次探测（存在secondary clustering问题）、开链法；
维护一个指针数组，每一个指针代表一个链表（具有相同的hash值）；
在插入数据时，会插入到同一个hash桶中的相同键值的数据的next 指向
当出现hashtable中元素个数达到阈值时（SGI是数组大小小于总元素个数时扩容），进行扩容（扩容大小为下一个质数），并将原来的数据rehash到新的表中（原来同一个桶中的数据，现在可能会hash到不同桶中，因此需要一个一个hash，这可能会导致同一个桶的数据出现翻转现象）；
注意针对double, float等未提供的 用户需要自定义hash function
4）hash_set/hash_map/hash_multiset/hash_multimap
采用hash_table实现；
hash_set/hash_map不允许重复，hash_multiset/hash_multimap允许重复；
map/multimap/unordered_map/ unordered_ multimap
原文：https://www.cnblogs.com/ChrisInsistPy/p/13203837.html