1.容器deque
C++ STL容器deque和vector很類(lèi)似宵统，也是采用動(dòng)態(tài)數(shù)組來(lái)管理元素流礁。
使用deque之前需包含頭文件：
#include
它是定義在命名空間std內(nèi)的一個(gè)class template：
template
class _Ax = allocator<_Ty> >
class deque;
第一個(gè)template參數(shù)用來(lái)表示元素型別炕置，第二個(gè)可有可無(wú)变过，指定內(nèi)存模型沐扳。一般使用默認(rèn)的內(nèi)存模型。
與vector不同的是deque的動(dòng)態(tài)數(shù)組首尾都開(kāi)放织鲸，因此能夠在首尾進(jìn)行快速地插入和刪除操作舔腾。
deque是一種分段連續(xù)的容器，特點(diǎn)是雙向開(kāi)口昙沦，可以認(rèn)為它是一段連續(xù)的內(nèi)存空間琢唾，不僅可以向前方增加內(nèi)存空間，也可以向后方增加內(nèi)存空間盾饮。
在實(shí)際內(nèi)存中實(shí)現(xiàn)雙向擴(kuò)充是比較復(fù)雜的事情采桃，那么deque中是如何實(shí)現(xiàn)的呢懒熙？deque通過(guò)一個(gè)控制器來(lái)串聯(lián)一系列的緩沖器（buffer），從而達(dá)到邏輯上的連續(xù)效果普办。
deque的內(nèi)存管理示意圖工扎，如下圖所示：
deque是通過(guò)一個(gè)vector在維護(hù)自身的控制器，在控制器中存儲(chǔ)的是指向buffer的指針衔蹲，因此我們需要用一個(gè)指向指針的指針來(lái)指向這個(gè)vector的地址肢娘。
deque能在邏輯上實(shí)現(xiàn)內(nèi)存連續(xù)，最關(guān)鍵的是iterator在起作用舆驶。迭代器運(yùn)行到邊界的時(shí)候橱健，都需要檢測(cè)是否到邊界，然后通過(guò)回到控制buffer的那個(gè)vector來(lái)管理邊界的buffer了沙廉。在iterator中拘荡，cur、first撬陵、last和node分別指向了用戶使用時(shí)的當(dāng)前的數(shù)據(jù)珊皿，first指向了buffer的第一塊空間，last指向了buffer之后那個(gè)不在buffer中的空間巨税，而node指向了控制buffer的指針序列中的實(shí)際位置
deque的源代碼如下所示（參考課程PPT）：
deque iterator的源代碼如下所示：
deuqe的插入問(wèn)題：
元素插入的時(shí)候因?yàn)槭前错樞蚺帕畜ǎ绻迦朐夭辉趦深^在中間，會(huì)改變其他元素的位置草添，如果插入點(diǎn)距離前段比較近驶兜，那么移動(dòng)前段比較合適，效率較高果元；
如果插入點(diǎn)距離后端比較近促王，那么將插入點(diǎn)之后的元素向后移動(dòng)比較快犀盟。
deque insert函數(shù)的源代碼如下：
iterator?insert(iterator?postion,?const?value_type&?x){
if(postion.cur?==?start.cur)??//如果安插點(diǎn)是deque的最前端
{
push_front(x);??//直接使用push_front
return?start;
}
else?if(postion.cur?==?finish.cur)??//如果安插點(diǎn)是deque的最末位
{
push_back(x);??//直接交給push_back
iterator?tmp?=?finish;
--tmp;
return?tmp;
}
else
{
return?insert_aux(postion,?x);
}
}
template?
typename?deque::iterator_deque::?itert_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)之前的元素較少
push_front(front());??//在最前端加入第一個(gè)元素同值的元素
.......
copy(front2,?pos1,?front1);??//元素搬移
}
else?{????//安插點(diǎn)之后的元素較少
push_back(back());//在尾端加入最末元素同值的元素
......
copy_backward(pos,?back2,?back1);//元素搬移
}
*pos?=?x_copy;//在安插點(diǎn)上設(shè)定新值
return?pos;
}
deque如何模擬連續(xù)空間而晒，全是的確iterators的功勞
具體代碼如下：
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?finish?==?start;
}
reference?operator*?()?const
{
return?*cur;
}
pointer?operator->()?const
{
return?&(operator*());
}
//兩個(gè)iterator之間的距離相當(dāng)于
//（1）兩個(gè)iterator之間的buffer的總長(zhǎng)度+
//（2）itr至buffer末尾的長(zhǎng)度+
//（3）x至buffer開(kāi)頭的長(zhǎng)度
difference_type
operator-?(const?self&?x)?const
{
return?difference_type(buffer_size())?*?(node?-?x.node?-?1)?+?(cur?-?first)?+?(x.last?-?x.cur);
//buffer?size?*?首尾buffer之間的buffer之間的數(shù)量?+?末尾（當(dāng)前）buffer的元素量?+?起始buffer的元素量
}
self&?operator++()
{
++cur;???????????????????//切換至下一個(gè)元素
if(cur?==?last){?????????//如果抵達(dá)緩沖區(qū)的末尾
set_node(node?+?1);??//就跳至下一個(gè)節(jié)點(diǎn)（緩沖區(qū)）的起點(diǎn)
cur?=?first;
}
return?*this;
}
self?operator++(int)
{
self?tmp?=?*this;
++*this;
return?tmp;
}
self&?operator--()
{
if(cur?==?first){?????????//如果目前在緩沖區(qū)開(kāi)頭，
set_node(node?-?1);???//就跳至前一節(jié)點(diǎn)（緩沖區(qū)）的最末端阅畴。
cur?=?last;
}
--cur;???????????????????//往前移動(dòng)一個(gè)元素（最末元素）
return?*this;
}
self?operator--(int)
{
self?tmp?=?*this;
--*this;
return?tmp;
}
void?set_node(map_pointer?new_node)
{
node?=?new_node;
first?=?*new_node;
last?=?first?+?difference_type(buffer_size));
}
self&?operator+=(difference_type?n?){
difference_type?offset?=?n?+?(cur?-?first);
if(offset?>=?0?&&?offset?<?difference_type(buffer_size())
//目標(biāo)位置在同一級(jí)緩存區(qū)
cur?+=?n;
else{
//目標(biāo)位置不在同一級(jí)緩存區(qū)內(nèi)
difference_type?node_offset?=?offset?>?0??offset?/?difference_type(buffer_size()):?-difference_type((-offset?-?1)?/?buffer_size;
//切換至正確的的緩存區(qū)
set_node(node?+?node_offset);
cur?=?first?+?(offset?-?node_offset?*?difference_type(buffser_size());
}
return?*this;
}
operator+(difference_type?n)?const
{
self?tmp?=?*this;
return?tmp?+=?n;
}
self&?operator-=(difference_type?n)
{
return?*this?+=?-?n;
}
self?operator-(difference_type?n)
{
self?tmp?=?*this;
return?tmp?-=?n;
}
reference?operator[]?(difference_type?n)const
{
return?*(*this?+?n);
}
GNU 4.9版本中實(shí)現(xiàn)的dequeUML圖倡怎，如下圖所示：
衍生：
deque和vector的不同之處：
1、兩端都能夠快速插入和刪除元素贱枣。vector只能在尾端進(jìn)行监署。
2、deque的元素存取和迭代器操作會(huì)稍微慢一些纽哥。因?yàn)閐eque的內(nèi)部結(jié)構(gòu)會(huì)多一個(gè)間接過(guò)程钠乏。
3、迭代器是特殊的智能指針春塌，而不是一般指針晓避。它需要在不同的區(qū)塊之間跳轉(zhuǎn)簇捍。
4、deque可以包含更多的元素俏拱，其max_size可能更大暑塑。因?yàn)椴恢故褂靡粔K內(nèi)存。
5锅必、不支持對(duì)容量和內(nèi)存分配時(shí)機(jī)的控制事格。
注意：在除了首尾兩端的其他地方插入和刪除元素，都將會(huì)導(dǎo)致指向deque元素的任何pointers搞隐、references驹愚、iterators失效。不過(guò)劣纲，deque的內(nèi)存重分配優(yōu)于vector么鹤。因?yàn)槠鋬?nèi)部結(jié)構(gòu)顯示不需要復(fù)制所有元素。
6味廊、deque的內(nèi)存區(qū)塊不再被使用時(shí)蒸甜，會(huì)被釋放。deque的內(nèi)存大小是可縮減的余佛。不過(guò)柠新，是不是這么做以及怎么做由實(shí)作版本定義。
deque和vector相似的特性：
1辉巡、在中間部分插入和刪除元素相對(duì)較慢恨憎，因?yàn)樗性囟家灰苿?dòng)。
2郊楣、迭代器屬于隨即存取迭代器憔恳。
最好采用deque的情形：
1、需要在兩端插入和刪除元素净蚤。
2钥组、無(wú)需引用容器內(nèi)的元素。
3今瀑、要求容器釋放不再使用的元素程梦。
2.容器 queue
2.1.queue模版類(lèi)的定義在頭文件中
queue與stack模版非常類(lèi)似，queue模版也需要定義兩個(gè)模版參數(shù)橘荠，一個(gè)是元素類(lèi)型屿附，一個(gè)是容器類(lèi)型，元素類(lèi)型是必要的哥童，容器類(lèi)型是可選的挺份，默認(rèn)為dqueue類(lèi)型。
定義queue對(duì)象的示例代碼如下：
queueq1;
queueq2;
queue的基本操作有：
1）.入隊(duì)：如q.push(x):將x元素接到隊(duì)列的末端贮懈；
2）.出隊(duì)：如q.pop() 彈出隊(duì)列的第一個(gè)元素匀泊，并不會(huì)返回元素的值影暴；
3）,訪問(wèn)隊(duì)首元素：如q.front()
4）,訪問(wèn)隊(duì)尾元素，如q.back();
5）,訪問(wèn)隊(duì)中的元素個(gè)數(shù)探赫，如q.size();
2.2.優(yōu)先隊(duì)列
在頭文件中型宙，還定義了一個(gè)非常有用的模版類(lèi)priority_queue(優(yōu)先隊(duì)列），優(yōu)先隊(duì)列與隊(duì)列的差別在于優(yōu)先隊(duì)列不是按照入隊(duì)的順序出隊(duì)伦吠，而是按照隊(duì)列中元素的優(yōu)先權(quán)順序出隊(duì)（默認(rèn)為大者優(yōu)先妆兑，也可以通過(guò)指定算子來(lái)指定自己的優(yōu)先順序）。
priority_queue模版類(lèi)有三個(gè)模版參數(shù)毛仪，元素類(lèi)型搁嗓，容器類(lèi)型，比較算子箱靴。其中后兩個(gè)都可以省略腺逛，默認(rèn)容器為vector，默認(rèn)算子為less衡怀，即小的往前排棍矛，大的往后排（出隊(duì)時(shí)序列尾的元素出隊(duì)）。
定義priority_queue對(duì)象的示例代碼如下：
priority_queueq1;
priority_queue >q2;
priority_queue抛杨，greater >q3;//定義小的先出隊(duì)
priority_queue的基本操作均與queue相同
初學(xué)者在使用priority_queue時(shí)够委，最困難的可能就是如何定義比較算子了。如果是基本數(shù)據(jù)類(lèi)型怖现，或已定義了比較運(yùn)算符的類(lèi)茁帽，可以直接用STL的less算子和greater算子——默認(rèn)為使用less算子，即小的往前排屈嗤，大的先出隊(duì)潘拨。如果要定義自己的比較算子，方法有多種饶号，這里介紹其中的一種：重載比較運(yùn)算符铁追。優(yōu)先隊(duì)列試圖將兩個(gè)元素x和y代入比較運(yùn)算符(對(duì)less算子，調(diào)用xy)讨韭，若結(jié)果為真脂信，則x排在y前面癣蟋，y將先于x出隊(duì)透硝，反之，則將y排在x前面疯搅，x將先出隊(duì)濒生。
容器queue是以deque為底層結(jié)構(gòu)實(shí)現(xiàn)的，具體代碼如下：
template?>
class?queue
{
............
public:
typedef?typename?Sequence::value_type?value_type
typedef?typename?Sequence::size_type?size_type
typedef?typename?Sequence::reference?reference;
typedef?typename?Sequence::const_reference?const_reference;
protected:
Sequence?c;??//底層容器
public:
bool?empty()?const{return?c.empty();}
size_type?size()?const{return?c.size();}
reference?front()?const?{return?c.front();}
const_reference?front()?const{?return?c.front();}
reference?back(){return?c.back();?}
const_reference?back()?const?{return?c.back();}
void?push?(const?value_type&?x){?c.push_back();?}
void?pop(){c.pop.front();}
}
3.容器 stack
容器stack也是以deque為底層結(jié)構(gòu)實(shí)現(xiàn)的幔欧，需要注意的是queue和stack都不允許遍歷罪治，也不提供iterator丽声，具體代碼如下：
template?>
class?stack
{
............
public:
typedef?typename?Sequence::value_type?value_type
typedef?typename?Sequence::size_type?size_type
typedef?typename?Sequence::reference?reference;
typedef?typename?Sequence::const_reference?const_reference;
protected:
Sequence?c;??//底層容器
public:
bool?empty()?const{return?c.empty();}
size_type?size()?const{return?c.size();}
reference?top()?const?{return?c.back();}
const_reference?top()?const{?return?c.back();}
void?push?(const?value_type&?x){?c.push_back();?}
void?pop(){c.pop.back();}
}
4.容器 rb_tree
Red-Black tree（紅黑樹(shù)）是平衡二元搜尋樹(shù)（balanced Binary search tree）中常被使用的一種。
平衡二院搜尋樹(shù)的特征：排列規(guī)律觉义，有利于search和insert雁社，并保持適度平衡，無(wú)任何節(jié)點(diǎn)過(guò)深晒骇。
紅黑樹(shù)的實(shí)現(xiàn)代碼：
5.容器 set霉撵，multiset
5.1需要包含頭文件：
#include
set和multiset都是定義在std空間里的類(lèi)模板：
[cpp]?view plain?copy?print?
template
class?_Pr?=?less<_Kty>,
class?_Alloc?=?allocator<_Kty>?>
class?set
[cpp]?view plain?copy?print?
template
class?_Pr?=?less<_Kty>,
class?_Alloc?=?allocator<_Kty>?>
class?multiset
只要是可復(fù)賦值、可拷貝洪囤、可以根據(jù)某個(gè)排序準(zhǔn)則進(jìn)行比較的型別都可以成為它們的元素徒坡。第二個(gè)參數(shù)用來(lái)定義排序準(zhǔn)則。缺省準(zhǔn)則less是一個(gè)仿函數(shù)瘤缩，以operator<對(duì)元素進(jìn)行比較喇完。
所謂排序準(zhǔn)則，必須定義strict weak ordering剥啤，其意義如下：
1）锦溪、必須使反對(duì)稱(chēng)的。
對(duì)operator<而言府怯，如果x
2）海洼、必須使可傳遞的。
對(duì)operator<而言富腊，如果x
3）坏逢、必須是非自反的。
對(duì)operator<而言赘被，x
因?yàn)樯厦娴倪@些特性是整，排序準(zhǔn)則可以用于相等性檢驗(yàn)，就是說(shuō)民假，如果兩個(gè)元素都不小于對(duì)方浮入，則它們相等。
5.2羊异、set和multiset的功能
和所有關(guān)聯(lián)式容器類(lèi)似事秀，通常使用平衡二叉樹(shù)完成。事實(shí)上野舶，set和multiset通常以紅黑樹(shù)實(shí)作而成易迹。
自動(dòng)排序的優(yōu)點(diǎn)是使得搜尋元素時(shí)具有良好的性能，具有對(duì)數(shù)時(shí)間復(fù)雜度平道。但是造成的一個(gè)缺點(diǎn)就是：
不能直接改變?cè)刂刀糜Ｒ驗(yàn)檫@樣會(huì)打亂原有的順序。
改變?cè)刂档姆椒ㄊ牵合葎h除舊元素，再插入新元素窘疮。
存取元素只能通過(guò)迭代器袋哼，從迭代器的角度看，元素值是常數(shù)闸衫。
容器set的實(shí)現(xiàn)代碼：
template?,?class?Alloc?=?alloc>
class?set{
public:
//typedefs:
typedef?Key?key_type;
typedef?Key?value_type;
typedef?Compare?key_compare;
typedef?Compare?value_compare;
private:
typedef?rb_tree?rep_type;
rep_type?t;
public:
typedef?typename?rep_type::const_iterator?iterator;
...
//set的所有操作涛贯，都調(diào)用底層rb_tree的函數(shù)，從這點(diǎn)看來(lái)蔚出，set實(shí)際應(yīng)該為container?adapter
}
容器multiset的實(shí)現(xiàn)代碼如下：
6.容器 map和multimap
map的實(shí)現(xiàn)代碼如下：
multimap實(shí)現(xiàn)代碼如下：
容器map獨(dú)特的operator[]
衍生：
1.map和multimap容器跟set和multiset容器非常相似疫蔓，包括外部接口和內(nèi)部結(jié)構(gòu)上。不同之處就是set和multiset容器是以單個(gè)對(duì)象為管理元素身冬，而map和multimap容器是以pair為管理元素衅胀。map和multimap容器中元素同時(shí)是自動(dòng)排序，它們排序的依據(jù)是各個(gè)元素的key值酥筝。
2.map和multimap容器在內(nèi)部結(jié)構(gòu)上通常也采用平衡二叉樹(shù)(balanced binary tree)滚躯，擁有跟set和multiset一樣的能力和操作。不同之處就是元素形式上嘿歌，另外map和multimap容器可以作為關(guān)聯(lián)數(shù)組使用掸掏。
3.在map或者multimap容器中查找特定值的元素，除了傳統(tǒng)的遍歷元素查找外宙帝，還可以使用通用算法來(lái)查找丧凤，但要自己設(shè)計(jì)函數(shù)對(duì)象
