本周內(nèi)容：
（1）deque&queue 和 stack 深度探索
（2）R-B tree 深度探索
（3）set/multiset深度探索
（4）map/multimap深度探索
（5）hashtable深度探索
（6）unordered容器概念
一 deque&queue 和 stack 深度探索
deque：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è)連續(xù)的存儲(chǔ)空間(實(shí)質(zhì)表示連續(xù)分段的容器)逼裆。
deque實(shí)現(xiàn)代碼如下，gnu2.9模板參數(shù)有三個(gè)赦政，其中第三個(gè)BufSiz默認(rèn)為0胜宇，可以由使用者自定buffer大小。
同樣的恢着，deque的iterator需要回答算法的五個(gè)問題桐愉，即上周的iterator traits。
- deque<T>::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<class T,class Alloc,size_t BufSize>
typename deque<T,Alloc,BufSize>::iterator
deque<T,Alloc,BufSize>::insert_aux(iterator pos,const value_type& x){
difference_type index = pos - start; //安插點(diǎn)之前的元素個(gè)數(shù)
value_type x_copy =x;
if (index<size()/2){ //如果安插點(diǎn)之前的元素個(gè)數(shù)較少
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ù)空間的呢从诲？全都是deque iterators的功勞，源代碼做了大量的操作符重載靡羡，尤其是遇到buffer邊界時(shí)如何跳到控制中心盏求，使得deque的iterator能夠在buffer之間模擬出連續(xù)空間。實(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*());}
//兩根iterators之間的距離相當(dāng)于
//(1)兩根iterators間的buffers的總長(zhǎng)度+
//(2)itr至其buffer末尾的長(zhǎng)度+
//(3)x至其buffer起頭的長(zhǎng)度
difference_type
operator-(const self& x) const
{
return difference_type(buffer_size())*(node-x.node-1)+
(cur-first)+(x.last-x.cur);
//首尾buffers之間的buffers數(shù)量
//（cur-first）末尾（當(dāng)前）buffer的元素量亿眠，（x.last-x.cur）起始buffer的元素量
}
queue和stack底層都是由deque完成的碎罚，通常他們也被稱為容器適配器。
-
queue
queue.png -
stack
stack.png - stack和queue都不允許遍歷纳像，也不提供iterator荆烈。
- stack和queue都可選擇list和deque作為底層容器
- queue不可選擇vector作為底層結(jié)構(gòu)，stack可選擇vector作為底層結(jié)構(gòu)
- stack和queue都不可選擇set或map做底層結(jié)構(gòu)
二 R-B tree 深度探索
- Red-Black tree(紅黑樹）是平衡二元搜尋樹（balanced binary search tree）中常被使用的一種竟趾。平衡二元搜尋樹的特征：排列規(guī)則有利于search和insert憔购，并保持適度平衡，即無(wú)任何節(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才是不可被改變的褂萧。
- rb_tree提供兩種insertion操作：insert_unique()和insert_equal( )押桃。前者表示節(jié)點(diǎn)的key一定在整個(gè)tree中獨(dú)一無(wú)二，否則安插失數加獭唱凯；后者表示節(jié)點(diǎn)的key可重復(fù)羡忘。
紅黑樹的使用如下：
三 set/multiset深度探索
- set/multiset以rb_tree為底層結(jié)構(gòu)，因此有元素自動(dòng)排序特性磕昼。排序的依據(jù)是key壳坪，而set/multiset元素的value和key合一：value就是key。
- set/multiset提供“遍歷”操作及iterators掰烟。按正常規(guī)則（++ite）遍歷爽蝴，便能獲得排序狀態(tài)（sorted）。
- 我們無(wú)法使用set/multiset的iterators改變?cè)刂担ㄒ驗(yàn)閗ey有其嚴(yán)謹(jǐn)排列規(guī)則）纫骑。set/multiset的iterator是其底部的RB tree的const-iterator蝎亚，就是為了禁止user對(duì)元素賦值。
-
set元素的key必須獨(dú)一無(wú)二先馆，因此其insert()用的是rb_tree的insert_unique()发框。multiset元素的key可以重復(fù)，因此其insert()用的rb_tree的insert_equal().
set源代碼.png
四 map/multimap深度探索
- map/multimap以rb_tree為底層結(jié)構(gòu)煤墙，因此有元素自動(dòng)排序特性梅惯。排序的依據(jù)是key。
- map/multimap提供“遍歷”操作及iterators仿野。按正常規(guī)則（++ite）遍歷铣减，便能獲得排序狀態(tài)（sorted）。我們無(wú)法使用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賦值球涛。
-
map元素的key必須獨(dú)一無(wú)二劣针，因此其insert()用的是rb_tree的insert_unique()。multimap元素的key可以重復(fù)亿扁，因此其insert()用的是rb_tree的insert_equal()捺典。
map源代碼.png
五 hashtable深度探索
有一大堆的東西要放在容器里，每一個(gè)東西可以折射成一個(gè)數(shù)值从祝，這些數(shù)值的變化如果有2^32種變化襟己，所需要的空間要非常大，hashtable就是用來解決這個(gè)問題哄褒。
當(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源代碼如下：
第一第二個(gè)參數(shù)與紅黑樹為底層的set和map類似，第三個(gè)模板參數(shù)hashFcn的目的是希望根據(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è)分配器。
六 unordered容器概念
從C++11開始榨咐，以hash開頭的容器都改為unordered容器（不定序容器）
- Before C++11
- hash_set
- hash_multiset
- hash_map
- hash_multimap
- Since C++11
- unordered_set
- unordered_multiset
- unordered_map
- unordered_multimap
