第五章 关联式容器

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