容器deque
C++ STL容器deque和vector很類似，也是采用動態(tài)數(shù)組來管理元素绰疤。
使用deque之前需包含頭文件：
#include <deque>
它是定義在命名空間std內(nèi)的一個class template：
template
class _Ax = allocator<_Ty> >
class deque;
第一個template參數(shù)用來表示元素型別，第二個可有可無，指定內(nèi)存模型证薇。一般使用默認(rèn)的內(nèi)存模型。
與vector不同的是deque的動態(tài)數(shù)組首尾都開放温峭，因此能夠在首尾進(jìn)行快速地插入和刪除操作。
deque是一種分段連續(xù)的容器字支，特點(diǎn)是雙向開口凤藏，可以認(rèn)為它是一段連續(xù)的內(nèi)存空間，不僅可以向前方增加內(nèi)存空間堕伪，也可以向后方增加內(nèi)存空間揖庄。
在實際內(nèi)存中實現(xiàn)雙向擴(kuò)充是比較復(fù)雜的事情，那么deque中是如何實現(xiàn)的呢刃跛？deque通過一個控制器來串聯(lián)一系列的緩沖器（buffer）抠艾，從而達(dá)到邏輯上的連續(xù)效果苛萎。
deque的內(nèi)存管理示意圖桨昙，如下圖所示：
deque是通過一個vector在維護(hù)自身的控制器，在控制器中存儲的是指向buffer的指針腌歉，因此我們需要用一個指向指針的指針來指向這個vector的地址蛙酪。
deque能在邏輯上實現(xiàn)內(nèi)存連續(xù)，最關(guān)鍵的是iterator在起作用翘盖。迭代器運(yùn)行到邊界的時候桂塞，都需要檢測是否到邊界，然后通過回到控制buffer的那個vector來管理邊界的buffer了馍驯。在iterator中阁危，cur玛痊、first、last和node分別指向了用戶使用時的當(dāng)前的數(shù)據(jù)狂打，first指向了buffer的第一塊空間擂煞，last指向了buffer之后那個不在buffer中的空間，而node指向了控制buffer的指針序列中的實際位置
deque的源代碼如下所示（參考課程PPT）：
deque iterator的源代碼如下所示：
deuqe的插入問題：
元素插入的時候因為是按順序排列趴乡，如果插入元素不在兩頭在中間对省，會改變其他元素的位置，如果插入點(diǎn)距離前段比較近晾捏，那么移動前段比較合適蒿涎，效率較高；
如果插入點(diǎn)距離后端比較近惦辛，那么將插入點(diǎn)之后的元素向后移動比較快劳秋。
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)之前的元素個數(shù)
value_type x_copy = x;
if(index < size() / 2){ //如果安插點(diǎn)之前的元素較少
push_front(front()); //在最前端加入第一個元素同值的元素
.......
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*());
}
//兩個iterator之間的距離相當(dāng)于
//（1）兩個iterator之間的buffer的總長度+
//（2）itr至buffer末尾的長度+
//（3）x至buffer開頭的長度
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; //切換至下一個元素
if(cur == last){ //如果抵達(dá)緩沖區(qū)的末尾
set_node(node + 1); //就跳至下一個節(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ū)開頭胖齐，
set_node(node - 1); //就跳至前一節(jié)點(diǎn)（緩沖區(qū)）的最末端俗批。
cur = last;
}
--cur; //往前移動一個元素（最末元素）
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)位置在同一級緩存區(qū)
cur += n;
else{
//目標(biāo)位置不在同一級緩存區(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版本中實現(xiàn)的dequeUML圖，如下圖所示：
衍生
deque和vector的不同之處：
- 兩端都能夠快速插入和刪除元素市怎。vector只能在尾端進(jìn)行岁忘。
- deque的元素存取和迭代器操作會稍微慢一些。因為deque的內(nèi)部結(jié)構(gòu)會多一個間接過程区匠。
- 迭代器是特殊的智能指針干像，而不是一般指針。它需要在不同的區(qū)塊之間跳轉(zhuǎn)驰弄。
- deque可以包含更多的元素麻汰，其max_size可能更大。因為不止使用一塊內(nèi)存戚篙。
- 不支持對容量和內(nèi)存分配時機(jī)的控制五鲫。
注意：在除了首尾兩端的其他地方插入和刪除元素，都將會導(dǎo)致指向deque元素的任何pointers岔擂、references位喂、iterators失效。不過乱灵，deque的內(nèi)存重分配優(yōu)于vector塑崖。因為其內(nèi)部結(jié)構(gòu)顯示不需要復(fù)制所有元素。 - deque的內(nèi)存區(qū)塊不再被使用時痛倚，會被釋放规婆。deque的內(nèi)存大小是可縮減的。不過，是不是這么做以及怎么做由實作版本定義抒蚜。
deque和vector相似的特性：
- 在中間部分插入和刪除元素相對較慢掘鄙，因為所有元素都要被移動。
- 迭代器屬于隨即存取迭代器嗡髓。
最好采用deque的情形：
- 需要在兩端插入和刪除元素通铲。
- 無需引用容器內(nèi)的元素。
3.要求容器釋放不再使用的元素器贩。
容器 queue
queue模版類的定義在頭文件中
queue與stack模版非常類似颅夺，queue模版也需要定義兩個模版參數(shù)，一個是元素類型蛹稍，一個是容器類型吧黄，元素類型是必要的，容器類型是可選的唆姐，默認(rèn)為dqueue類型拗慨。
定義queue對象的示例代碼如下：
queueq1;
queueq2;
queue的基本操作有：
- 入隊：如q.push(x):將x元素接到隊列的末端；
- 出隊：如q.pop() 彈出隊列的第一個元素奉芦，并不會返回元素的值赵抢；
- 訪問隊首元素：如q.front()
- 訪問隊尾元素，如q.back();
- 訪問隊中的元素個數(shù)声功，如q.size();
優(yōu)先隊列
在頭文件中烦却，還定義了一個非常有用的模版類priority_queue(優(yōu)先隊列），優(yōu)先隊列與隊列的差別在于優(yōu)先隊列不是按照入隊的順序出隊先巴，而是按照隊列中元素的優(yōu)先權(quán)順序出隊（默認(rèn)為大者優(yōu)先其爵，也可以通過指定算子來指定自己的優(yōu)先順序）。
priority_queue模版類有三個模版參數(shù)伸蚯，元素類型摩渺，容器類型，比較算子剂邮。其中后兩個都可以省略摇幻，默認(rèn)容器為vector，默認(rèn)算子為less挥萌，即小的往前排绰姻，大的往后排（出隊時序列尾的元素出隊）。
定義priority_queue對象的示例代碼如下：
priority_queueq1;
priority_queue >q2;
priority_queue瑞眼，greater >q3;//定義小的先出隊
priority_queue的基本操作均與queue相同
初學(xué)者在使用priority_queue時龙宏，最困難的可能就是如何定義比較算子了。如果是基本數(shù)據(jù)類型伤疙，或已定義了比較運(yùn)算符的類，可以直接用STL的less算子和greater算子——默認(rèn)為使用less算子，即小的往前排徒像，大的先出隊黍特。如果要定義自己的比較算子，方法有多種锯蛀，這里介紹其中的一種：重載比較運(yùn)算符灭衷。優(yōu)先隊列試圖將兩個元素x和y代入比較運(yùn)算符(對less算子，調(diào)用xy)旁涤，若結(jié)果為真翔曲，則x排在y前面，y將先于x出隊劈愚，反之瞳遍，則將y排在x前面，x將先出隊菌羽。
容器queue是以deque為底層結(jié)構(gòu)實現(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();}
}
容器 stack
容器stack也是以deque為底層結(jié)構(gòu)實現(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();}
}
容器 rb_tree
Red-Black tree（紅黑樹）是平衡二元搜尋樹（balanced Binary search tree）中常被使用的一種。
平衡二元搜尋樹的特征：排列規(guī)律是晨，有利于search和insert肚菠，并保持適度平衡，無任何節(jié)點(diǎn)過深罩缴。
紅黑樹的實現(xiàn)代碼：
容器 set案糙，multiset
需要包含頭文件
#include <set>
set和multiset都是定義在std空間里的類模板：
template
class _Pr = less<_Kty>,
class _Alloc = allocator<_Kty> >
class set
template
class _Pr = less<_Kty>,
class _Alloc = allocator<_Kty> >
class multiset
只要是可復(fù)賦值、可拷貝靴庆、可以根據(jù)某個排序準(zhǔn)則進(jìn)行比較的型別都可以成為它們的元素时捌。第二個參數(shù)用來定義排序準(zhǔn)則。缺省準(zhǔn)則less是一個仿函數(shù)炉抒，以operator<對元素進(jìn)行比較奢讨。
所謂排序準(zhǔn)則，必須定義strict weak ordering焰薄，其意義如下：
- 必須使反對稱的拿诸。
對operator<而言，如果x - 必須使可傳遞的塞茅。
對operator<而言亩码，如果x - 必須是非自反的。
對operator<而言野瘦，x
因為上面的這些特性描沟，排序準(zhǔn)則可以用于相等性檢驗飒泻，就是說，如果兩個元素都不小于對方吏廉，則它們相等泞遗。
set和multiset的功能
和所有關(guān)聯(lián)式容器類似，通常使用平衡二叉樹完成席覆。事實上史辙，set和multiset通常以紅黑樹實作而成。
自動排序的優(yōu)點(diǎn)是使得搜尋元素時具有良好的性能佩伤，具有對數(shù)時間復(fù)雜度聊倔。但是造成的一個缺點(diǎn)就是：
不能直接改變元素值。因為這樣會打亂原有的順序生巡。
改變元素值的方法是：先刪除舊元素耙蔑，再插入新元素。
存取元素只能通過迭代器障斋，從迭代器的角度看纵潦，元素值是常數(shù)。
容器set的實現(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)看來，set實際應(yīng)該為container adapter
}
容器multiset的實現(xiàn)代碼如下：
容器 map和multimap
map的實現(xiàn)代碼如下：
multimap實現(xiàn)代碼如下：
容器map獨(dú)特的operator[]
衍生：
- map和multimap容器跟set和multiset容器非常相似遂庄，包括外部接口和內(nèi)部結(jié)構(gòu)上寥院。不同之處就是set和multiset容器是以單個對象為管理元素，而map和multimap容器是以pair為管理元素涛目。map和multimap容器中元素同時是自動排序秸谢，它們排序的依據(jù)是各個元素的key值。
- map和multimap容器在內(nèi)部結(jié)構(gòu)上通常也采用平衡二叉樹(balanced binary tree)霹肝，擁有跟set和multiset一樣的能力和操作估蹄。不同之處就是元素形式上，另外map和multimap容器可以作為關(guān)聯(lián)數(shù)組使用沫换。
- 在map或者multimap容器中查找特定值的元素臭蚁，除了傳統(tǒng)的遍歷元素查找外，還可以使用通用算法來查找讯赏，但要自己設(shè)計函數(shù)對象
