Boolan STL 第三周

deque：只能两头进两头出的容器，实现为分段连续，使用者感觉用起来是整体连续的。

deque's iterator：由cur,first,last,node4个指针构成，它内部提供模拟出连续空间的功能。

deque的insert()实现：

不是头和尾的情况下

deque模拟连续空间的实现：

stack：先进后出，前闭后开。

queue：先进先出，单向移动。

queue和stack不允许遍历，不提供iterator。

queue和stack也可以选择list作为底层，stack还可选vector作为底层，只要满足提供使用的接口。

rb_tree:红黑树，是一种平衡二院搜索树，有利于search和insert，保持适度平衡。

rb_tree提供iterator遍历，单不应使用iterator改变key的值。

rb_tree两种insert():insert_unique不允许放入重复值，无法插入但不会报错，insert_equal()允许放入重复值。

rb_tree实现：

rb_tree用例：

set/multiset：底层调用红黑树，set调用rb_tree的insert_unique()，multiset调用insert_equal()

set实现：

map与multimap同理与set/multiset。

map实现：

hashtable：哈希表，将object通过hash_function转换为code存入不同的bucket中，若两个元素放入同一个bucket中则为collision，冲突元素会和原来的元素以单向链表连接，当元素个数等于bucket个数时，bucket数会扩充到将近两倍（G2.9版是两倍附近的质数），元素重新打散重排（rehashing）。

hashtable实现：

hashtable用例：

hash_function：对常见的数据类型系统给出了哈希函数，但对于c++的string类没有自带的hash_function，需要自己写。

系统默认的 char*类型hash_function

unordered容器：将c++11以前的hash_set/multiset/map/multimap改为unordered_set/multiset/map/multimap