體系結(jié)構(gòu)與內(nèi)核分析續(xù)
deque&queue 和 stack 深度探索
deque雙向隊(duì)列是一種雙向開口的連續(xù)線性空間曹抬，可以高效的在頭尾兩端插入和刪除元素忧额，deque在接口上和vector非常相似绿店。（連續(xù)是假象铲敛，分段是事實(shí)）
deque的內(nèi)存空間分布是小片的連續(xù)粟关，小片間用鏈表相連言询，實(shí)際上內(nèi)部有一個(gè)map的指針尔觉。其中buffer表示deque的緩沖區(qū)凉袱，每個(gè)buffer可以存放多個(gè)元素結(jié)點(diǎn)。并且每個(gè)buffer指針存放在vector容器中侦铜。每個(gè)iterator存放四個(gè)指針:cur专甩、first、last钉稍、node配深，cur表示當(dāng)前數(shù)據(jù)結(jié)點(diǎn)的指針，first表示buffer首指針嫁盲，last表示buffer的尾指針篓叶，node表示這個(gè)iterator在vector中的指針地址烈掠。所有容器都有兩個(gè)iterator分別指向頭和尾begin& finish。
deque用法：http://blog.csdn.net/hnust_xiehonghao/article/details/8800007
源代碼示例：deque::insert()
//在position處安插一個(gè)元素缸托，其值為x
iterator insert(iterator position,const value_type& x){
if(position.cur == start.cur){? ? ? ? ? ? ? //如果安插點(diǎn)是deque最前端
push_front(x);? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? //交給push——front()做
return start;
}
else if (position.cur == finish.cur) {? ? //如果安插點(diǎn)是deque最尾端
push_back(x);? ? ? ? ? ? ? ? ? ? ? ? ? ? ? //交給push——back()做
iterator tmp =finish;
--tmp;
return tmp;
}
else {
return insert_aux(position,x);
}
}
template
typename deque::iterator
deque::insert_aux(iterator pos,const value_type& x){
difference_type index = pos - start;? ? //安插點(diǎn)之前的元素個(gè)數(shù)
value_type x_copy =x;
if (index
push_front(front());? ? ? ? ? ? //在最前端加入與第一元素同值的元素
...
copy(front2,pos1,front1);? ? //元素搬移
}
else{? ? ? ? ? ? ? ? ? ? ? ? //安插點(diǎn)之后的元素個(gè)數(shù)較少
push_back(back());? //在尾端加入與最末元素同值的元素
...
copy_backward(pos,back2,back1);? ? ? //元素搬移
}
*pos = x_copy;? ? ? ? //在安插點(diǎn)上設(shè)定新值
return pos;
}
deque是如何模擬連續(xù)空間：源代碼做了大量的操作符重載左敌，尤其是遇到buffer邊界時(shí)如何跳到控制中心，使得deque的iterator能夠在buffer之間模擬出連續(xù)空間俐镐。iterator的功勞特別是大量的操作符重載矫限。
實(shí)現(xiàn)源代碼如下：
reference operator[] (size_type n)
{
return start[difference_type(n)];
}
reference front(){return *start;}
reference back()
{
iterator tmp = finish;
--tmp;
return *tmp;
}
size_type size() const {return finish - start;}
bool empty() const {return == start;}
reference operator*() const {return *cur;}
pointer operator->() const {return & (operator*());}
queue（先進(jìn)先出）和stack（先進(jìn)后出）：內(nèi)含一個(gè)deque封掉某些功能。
stack和queue都不允許遍歷佩抹，也不提供iterator叼风。
stack和queue都可選擇list和deque作為底層容器。
queue不可選擇vector作為底層結(jié)構(gòu)棍苹，stack可選擇vector作為底層結(jié)構(gòu)无宿。
stack和queue都不可選擇set或map做底層結(jié)構(gòu)。
RB-tree深度探索
Red-Black tree(紅黑樹）是平衡二元搜尋樹（balanced binary search tree）中常被使用的一種枢里。平衡二元搜尋樹的特征：排列規(guī)則有利于search和insert孽鸡，并保持適度平衡，即無任何節(jié)點(diǎn)過深栏豺。
紅黑樹的性質(zhì)如下:
1) 每一個(gè)節(jié)點(diǎn)或者著紅色,或者著成黑色.
2) 根是黑色的
3) 如果一個(gè)節(jié)點(diǎn)是紅色的,那么它的子節(jié)點(diǎn)必須是黑色的.
4) 從一個(gè)節(jié)點(diǎn)到一個(gè)NULL指針的每一條路徑必須包含相同數(shù)目的黑色節(jié)點(diǎn).
re_tree提供“遍歷”操作及iterators彬碱。按正常規(guī)則（++ite）遍歷，便能獲得排序狀態(tài)（sorted）奥洼。我們不應(yīng)使用rb_tree的iterators改變?cè)刂担ㄒ驗(yàn)樵赜衅鋰?yán)謹(jǐn)排列規(guī)則）巷疼。編程并未阻止此事。如此設(shè)計(jì)是正確的灵奖，因?yàn)閞b_tree即將為set和map服務(wù)（作為其底部支持）嚼沿，而map允許元素的data被改變，只有元素的key才是不可被改變的桑寨。key和data一起才為value伏尼。rb_tree提供兩種insertion操作：insert_unique()和insert_equal( )忿檩。前者表示節(jié)點(diǎn)的key一定在整個(gè)tree中獨(dú)一無二尉尾，否則安插失敗燥透；后者表示節(jié)點(diǎn)的key可重復(fù)沙咏。
RB-tree的用法：
begin()函數(shù)獲取最左（最小）的節(jié)點(diǎn)處班套，end()獲取的是根結(jié)點(diǎn)（由于使用了一個(gè)實(shí)現(xiàn)上的技巧肢藐，其實(shí)并不是真的根結(jié)點(diǎn)）；
empty()判斷是否為空, size(), max_size()最大數(shù)據(jù)的數(shù)量吱韭，count()吆豹；
insert_unique(const value_type& x)將x插入RB-tree中鱼的，保持節(jié)點(diǎn)值獨(dú)一無二；
insert_equal(const value_type& x)將x插入RB-tree中痘煤，允許節(jié)點(diǎn)值重復(fù)凑阶。
關(guān)聯(lián)式容器
set/multiset（set中key不可重復(fù)，multiset可以|后面map相同） （key就是vault）二分樹（高度平衡）map/multimap（有key和vault）（所有元素都會(huì)根據(jù)元素的鍵值自動(dòng)被排序）在STL中關(guān)聯(lián)容器使用紅黑樹來實(shí)現(xiàn)衷快，因?yàn)椴皇琼樞蚪Y(jié)構(gòu)宙橱，因而不能使用上面提到的push和pop函數(shù)，使用insert和erase函數(shù)來實(shí)現(xiàn)元素的插入刪除操作呕臂。關(guān)聯(lián)容器支持通過鍵來高效地查找和讀取元素强缘，兩個(gè)基本的關(guān)聯(lián)容器類型是map和set消别。map的元素以鍵-值（key-value）對(duì)的形式組織：鍵用于元素在map中的索引，而值則表示所存儲(chǔ)和讀取的數(shù)據(jù)宝冕。set僅包含一個(gè)鍵，并有效地支持關(guān)于某個(gè)鍵是否存在的查詢陨晶。map可理解為字典猬仁，set可理解為一類元素的集合。關(guān)聯(lián)容器和順序容器的本質(zhì)差別在于：關(guān)聯(lián)容器通過鍵（key）存儲(chǔ)和讀取元素先誉，而順序容器則通過元素在容器中的位置順序存儲(chǔ)和訪問元素湿刽。set 和 map 類型的對(duì)象所包含的元素都具有不同的鍵，不允許為同一個(gè)鍵添加第二個(gè)元素褐耳。如果一個(gè)鍵必須對(duì)應(yīng)多個(gè)實(shí)例诈闺，則需使用 multimap 或 multi set，這兩種類型允許多個(gè)元素?fù)碛邢嗤逆I铃芦。
set/multiset深度探索
set/multiset以rb_tree為底層結(jié)構(gòu)（內(nèi)含一個(gè)tree）雅镊，因此有元素自動(dòng)排序特性。排序的依據(jù)是key刃滓，而set/multiset元素的value和key合一：value就是key仁烹。
set/multiset提供“遍歷”操作及iterators。按正常規(guī)則（++ite）遍歷咧虎，便能獲得排序狀態(tài)（sorted）卓缰。
我們無法使用set/multiset的iterators改變?cè)刂担ㄒ驗(yàn)閗ey有其嚴(yán)謹(jǐn)排列規(guī)則）。set/multiset的iterator是其底部的RB tree的const-iterator砰诵，就是為了禁止user對(duì)元素賦值征唬。
set元素的key必須獨(dú)一無二，因此其insert()用的是rb_tree的insert_unique()茁彭。multiset元素的key可以重復(fù)总寒，因此其insert()用的rb_tree的insert_equal()。
map/multimap深度探索
map/multimap以rb_tree為底層結(jié)構(gòu)理肺，因此有元素自動(dòng)排序特性摄闸。排序的依據(jù)是key善镰。
map/multimap提供“遍歷”操作及iterators。按正常規(guī)則（++ite）遍歷年枕，便能獲得排序狀態(tài)（sorted）媳禁。我們無法使用map/multimap的iterators改變?cè)氐膋ey（因?yàn)閗ey有其嚴(yán)謹(jǐn)排列順序），但可以用它來改變?cè)氐膁ata画切。因此map/multimap內(nèi)部自動(dòng)將user指定的key type設(shè)為const竣稽，如此便能禁止user對(duì)元素的key賦值。（內(nèi)含tree限制某些功能）
map元素的key必須獨(dú)一無二霍弹，因此其insert()用的是rb_tree的insert_unique()毫别。multimap元素的key可以重復(fù)，因此其insert()用的是rb_tree的insert_equal()典格。
hashtable深度探索
Hashtable是非泛型的集合岛宦，所以在檢索和存儲(chǔ)值類型時(shí)通常會(huì)發(fā)生裝箱與拆箱的操作。
當(dāng)把某個(gè)元素添加到 Hashtable 時(shí)耍缴，將根據(jù)鍵的哈希代碼將該元素放入存儲(chǔ)桶中砾肺，由于是散列算法所以會(huì)出現(xiàn)一個(gè)哈希函數(shù)能夠?yàn)閮蓚€(gè)不同的鍵生成相同的哈希代碼，該鍵的后續(xù)查找將使用鍵的哈希代碼只在一個(gè)特定存儲(chǔ)桶中搜索防嗡，這將大大減少為查找一個(gè)元素所需的鍵比較的次數(shù)变汪。
Hashtable 的加載因子確定元素與Hashtable 可擁有的元素?cái)?shù)的最大比率。加載因子越小蚁趁，平均查找速度越快裙盾，但消耗的內(nèi)存也增加。默認(rèn)的加載因子 0.72通常提供速度和大小之間的最佳平衡他嫡。當(dāng)創(chuàng)建 Hashtable 時(shí)番官，也可以指定其他加載因子。（元素總量/ Hashtable 可擁有的元素?cái)?shù)=加載因子 ）當(dāng)向 Hashtable 添加元素時(shí)钢属，Hashtable 的實(shí)際加載因子將增加徘熔。當(dāng)實(shí)際加載因子達(dá)到指定的加載因子時(shí)，Hashtable 中存儲(chǔ)桶的數(shù)目自動(dòng)增加到大于當(dāng)前 Hashtable 存儲(chǔ)桶數(shù)兩倍的最小素?cái)?shù)淆党。（Hashtable適用于讀取操作頻繁酷师，寫入操作很少的操作類型）
當(dāng)碰撞的元素超過“籃子”的個(gè)數(shù)，經(jīng)驗(yàn)判斷為危險(xiǎn)宁否，則將“籃子”的數(shù)量擴(kuò)大為原來的兩倍窒升，一般籃子數(shù)量是素?cái)?shù)缀遍。GUC初始籃子數(shù)量為53慕匠，兩倍變成106，附近的素?cái)?shù)而且比106大的為193域醇√ㄒ辏可以使用hashtable iterators改變?cè)氐膁ata蓉媳，但不能改變?cè)氐膋ey（因?yàn)閔ashtable根據(jù)key實(shí)現(xiàn)嚴(yán)謹(jǐn)?shù)脑嘏帕校?/p>
hashtable源代碼：
template六個(gè)模板參數(shù)：value和key參數(shù)與紅黑樹為底層的set和map類似，第三個(gè)模板參數(shù)hashFcn(hash-function)的目的是希望根據(jù)元素值算出一個(gè)hash code（一個(gè)可進(jìn)行modulus運(yùn)算的值）锅铅，使得元素hash code映射之后能夠夠雜亂夠隨機(jī)地被置于hashtable內(nèi)酪呻，越是亂，越是不容易碰撞盐须，可以傳函數(shù)玩荠、仿函數(shù)、函數(shù)對(duì)象贼邓，它是通過模板偏特化實(shí)現(xiàn)阶冈，c風(fēng)格的字符串char*是一個(gè)指針，stl提供了實(shí)現(xiàn)方式塑径，而C++的字符串string則需要自己寫實(shí)現(xiàn)方式女坑；第四個(gè)ExtractKey告訴我們?nèi)绾稳〕鰇ey；第五個(gè)EqualKey告訴我們?nèi)绾伪容^key大型骋ā匆骗；第六個(gè)alloc為分配器。
hash_map和map的區(qū)別在哪里誉简？
構(gòu)造函數(shù)? hash_map需要hash函數(shù)碉就，等于函數(shù)；map只需要比較函數(shù)(小于函數(shù)).
存儲(chǔ)結(jié)構(gòu)? hash_map采用hash表存儲(chǔ)闷串，map一般采用紅黑樹(RB Tree)實(shí)現(xiàn)铝噩。因此其memory數(shù)據(jù)結(jié)構(gòu)是不一樣的。
unordered容器概念
Before C++11
hash_set
hash_multiset
hash_map
hash_multimap
Since C++11
unordered_set
unordered_multiset
unordered_map
unordered_multimap
只是名稱不同窿克，用法不變
