在完成了STL與泛型編程前兩周的學習之后屡穗，有一些總結和心得在這里通過學習筆記的方式分享出來练湿，筆記我是跟著老師在視頻中所講的內容按照順序記錄的，也不能說是流水賬涌庭，對課程中的一些問題還是添加了自己的理解和分析芥被，供也在學習C++的小伙伴用作學習交流，如有理解不到位的地方坐榆，歡迎批評指正拴魄。
上周，老師就分配器和部分容器結構做了詳細的介紹席镀，本周接著上周的內容繼續(xù)學習了容器的結構與分類匹中。
一．容器deque
deque是雙向開口，雙向進出的容器
Deque有n個buffer緩沖區(qū)豪诲，一個map相當于其控制中心顶捷，map用一個vector來存放指針，分別指向n個緩沖區(qū)屎篱。
Deque其實是分段連續(xù)的服赎，deque如何模擬連續(xù)空間，這全都是deque?iterators的功勞交播，其iterators是一個class重虑，iterators用4根指針，分別指向當前位置秦士、起始位置缺厉、終止位置和map控制中心的某個位置，以此來判斷是哪個緩沖區(qū)隧土。
二．容器queue和stack
容器queue是先進先出的容器提针；容器stack是一端開口，先進后出的容器;
它們可以選擇list和deque作為底層容器去支持它們的運行曹傀，標準庫默認用deque來作為底層容器关贵。Stack和queue都不允許遍歷，也不提供iterator卖毁。Stack可以選擇vector作為底層容器揖曾，但是queue不可以選擇vector落萎，原因是queue可以從前端出，即pop_front炭剪，但vector沒有pop_front.當然练链，stack和queue都不可以選擇set或map作為底層容器，這點很好理解奴拦。
三．容器rb_tree
Red-Black tree（紅黑樹）是平衡二元搜索樹（balanced binary search tree）中常被使用的一種媒鼓。其特征是：排列規(guī)則有理搜索和安插，并保持適度平衡错妖，即無任何節(jié)點過深绿鸣。
Rb_tree提供“遍歷”操作及iterators。按正常規(guī)則（++ite）遍歷暂氯，便能獲得排序狀態(tài)（sorted）潮模。
我們不應使用rb_tree的iterators改變元素值，因元素有其嚴謹排列規(guī)則痴施。但編程層面并喂阻絕擎厢，因為rb_tree會作為set和map的底層支持容器，而map允許元素的data被改變辣吃，只有元素的key是不能被改變的动遭。
Rb_tree提供了兩種插入元素的操作：insert_unique()表示節(jié)點的key一定在整個tree中獨一無二，否則安插失斏竦谩厘惦；insert_equal()表示節(jié)點的key可重復。
這里值得注意的是哩簿，在C++標準庫中绵估，key和data合成value。
四．容器set卡骂，multiset
Set和multiset以rb_tree為底層結構，因此有元素自動排序特性形入，排序依據是key全跨。set和multiset元素的value和key合一，其value就是key亿遂。
同樣浓若，set和multiset提供“遍歷”操作及iterators，按正常規(guī)則（++ite）遍歷蛇数，便能獲得排序狀（sorted）挪钓。
我們無法使用set和multiset的iterators改變元素值，因其key和value合一耳舅。Set和multiset的iterator是其底層容器rb_tree的const-iterator碌上，就是為了禁止對元素進行賦值操作倚评。
Set元素的key必須獨一無二，因此其insert()用的是rb_tree的insert_unique馏予；multiset元素的key可重復天梧，因此其insert()用的是rb_tree的insert_equal().
五．容器map，multimap
同樣以rb_tree為底層結構霞丧，可以進行“遍歷”操作有iterators?Map/multimap和set/multiset的不同在于使用map/multimap的iterators無法改變元素的key呢岗，但可以改變其data，key和data合成了元素的value蛹尝。
Map元素的key必須獨一無二后豫，因此其insert()用的是rb_tree的insert_unique()；multimap元素的key可以重復突那，因此其insert()用的是rb_tree的insert_equal()
這里值得注意的是挫酿，容器map有其獨特的operator[]：lower_bound試圖在sorted()中尋找元素value，若找到陨收，便傳回與value相等的第一個元素饭豹；若未找到，則傳回該map中最適合放這個元素的位置务漩，在這個點插入新元素拄衰。
六．容器hashtable
在本課程第一周的學習中，就對哈希表有了粗略的了解饵骨。當容器空間足夠時翘悉，元素以一個編號T安插在容器中的某個位置，當容器空間不足時居触，相同的編號便會發(fā)生碰撞妖混，通過key/M的余數放在相應的位置。
發(fā)生碰撞便安插鏈表轮洋，如果元素個數超過了bucket的個數制市，則將bucket擴大一倍，所有元素打散重新排列弊予，這叫做rehashing祥楣。
Rehashing擴大后的bucket個數刻意為擴大兩倍數附近的質數：53、97汉柒、193……
Hashtable涉及到的一些類如下代碼所示误褪，其中HashFcn用來提取元素的key:
哈希表的節(jié)點由兩部分組成：值+單向鏈表指針
這里值得注意的是：iterators走到單向鏈表邊緣時++ite后必須能夠到達下一個bucket。因此其iterator中的node* cur指向當前的元素碾褂，同時兽间，hashtable* ht指向hashtable本身，即這些bucket
最后正塌，由hash-function算出每個元素的hash-code嘀略，使得這些元素經過hash-code映射之后能夠足夠雜亂隨機地置于容器hashtable內恤溶，越是雜亂隨機，元素之間則越不容易發(fā)生碰撞屎鳍。模板庫中Hash-function對各種數據類型進行了偏特化宏娄，不同的數據類型對應不同的算法得到hash-code
七．Unordered容器
C++11將hash_***容器改為了unordered_***容器，但本質上并沒有區(qū)別逮壁，unordered容器仍然是建立在哈希表的基礎之上的孵坚。
