Boolan STL 第三周

deque：只能兩頭進(jìn)兩頭出的容器，實現(xiàn)為分段連續(xù)，使用者感覺用起來是整體連續(xù)的。

deque's iterator：由cur,first,last,node4個指針構(gòu)成，它內(nèi)部提供模擬出連續(xù)空間的功能。

deque的insert()實現(xiàn)：

不是頭和尾的情況下

deque模擬連續(xù)空間的實現(xiàn)：

stack：先進(jìn)后出，前閉后開。

queue：先進(jìn)先出，單向移動。

queue和stack不允許遍歷，不提供iterator。

queue和stack也可以選擇list作為底層，stack還可選vector作為底層，只要滿足提供使用的接口。

rb_tree:紅黑樹，是一種平衡二院搜索樹，有利于search和insert，保持適度平衡。

rb_tree提供iterator遍歷，單不應(yīng)使用iterator改變key的值。

rb_tree兩種insert():insert_unique不允許放入重復(fù)值，無法插入但不會報錯，insert_equal()允許放入重復(fù)值。

rb_tree實現(xiàn)：

rb_tree用例：

set/multiset：底層調(diào)用紅黑樹，set調(diào)用rb_tree的insert_unique()，multiset調(diào)用insert_equal()

set實現(xiàn)：

map與multimap同理與set/multiset。

map實現(xiàn)：

hashtable：哈希表，將object通過hash_function轉(zhuǎn)換為code存入不同的bucket中，若兩個元素放入同一個bucket中則為collision，沖突元素會和原來的元素以單向鏈表連接，當(dāng)元素個數(shù)等于bucket個數(shù)時，bucket數(shù)會擴(kuò)充到將近兩倍（G2.9版是兩倍附近的質(zhì)數(shù)），元素重新打散重排（rehashing）。

hashtable實現(xiàn)：

hashtable用例：

hash_function：對常見的數(shù)據(jù)類型系統(tǒng)給出了哈希函數(shù)，但對于c++的string類沒有自帶的hash_function，需要自己寫。

系統(tǒng)默認(rèn)的

char*類型hash_function

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