c++stack(堆棧）是一個容器的改編寇蚊，它實現(xiàn)了一個先進后出的數(shù)據(jù)結(jié)構(gòu)（FILO）
使用該容器時需要包含#include頭文件市栗；
定義stack對象的示例代碼如下：
stacks1;
stacks2;
stack的基本操作有：
1.入棧：如s.push(x);
2.出棧:如 s.pop().注意：出棧操作只是刪除棧頂?shù)脑剡端保⒉环祷卦撛亍?/p>
3.訪問棧頂：如s.top();
4.判斷棸傩拢空：如s.empty().當椕史。空時返回true。
5.訪問棧中的元素個數(shù)遵湖，如s.size（）;
下面舉一個簡單的例子：
#include?
#include?
using namespace std;?
int main(void)?
{?
? ? stacks;//定義一個棧?
? ? for(int i=0;i<10;i++)?
? ? ? ? s.push(i);?
? ? while(!s.empty())?
? ? {?
? ? ? ? printf("%lf\n",s.top());?
? ? ? ? s.pop();?
? ? }?
? ? cout<<"棧內(nèi)的元素的個數(shù)為："<
? ? return 0;?
}
1.容器deque
deque是一種分段連續(xù)的容器悔政，特點是雙向開口，可以認為它是一段連續(xù)的內(nèi)存空間延旧，不僅可以向前方增加內(nèi)存空間谋国，也可以向后方增加內(nèi)存空間。
在實際內(nèi)存中實現(xiàn)雙向擴充是比較復雜的事情迁沫，那么deque中是如何實現(xiàn)的呢芦瘾？ deque通過一個控制器來串聯(lián)一系列的緩沖器（buffer），從而達到邏輯上的連續(xù)效果集畅。
deque的內(nèi)存管理示意圖近弟，如下圖所示：
deque是通過一個vector在維護自身的控制器，在控制器中存儲的是指向buffer的指針牡整，因此我們需要用一個指向指針的指針來指向這個vector的地址藐吮。
deque能在邏輯上實現(xiàn)內(nèi)存連續(xù)，最關(guān)鍵的是iterator在起作用。 迭代器運行到邊界的時候谣辞，都需要檢測是否到邊界迫摔，然后通過回到控制buffer的那個vector來管理邊界的buffer了。 在iterator中泥从，cur句占、first、last和node分別指向了用戶使用時的當前的數(shù)據(jù)躯嫉，first指向了buffer的第一塊空間纱烘，last指向了buffer之后那個不在buffer中的空間， 而node指向了控制buffer的指針序列中的實際位置
deque的源代碼如下所示（參考課程PPT）：
deque iterator的源代碼如下所示：
deuqe的插入問題：
元素插入的時候因為是按順序排列祈餐，如果插入元素不在兩頭在中間擂啥，會改變其他元素的位置，如果插入點距離前段比較近帆阳，那么移動前段比較合適哺壶，效率較高；
如果插入點距離后端比較近蜒谤，那么將插入點之后的元素向后移動比較快山宾。
deque insert函數(shù)的源代碼如下：
iterator insert(iterator postion, const value_type& x){?
? ? if(postion.cur == start.cur)? //如果安插點是deque的最前端?
? ? {?
? ? ? ? push_front(x);? //直接使用push_front?
? ? ? ? return start;?
? ? }?
? ? else if(postion.cur == finish.cur)? //如果安插點是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;? ? //安插點之前的元素個數(shù)?
? ? value_type x_copy = x;?
? ? if(index < size() / 2){? //如果安插點之前的元素較少?
? ? ? ? push_front(front());? //在最前端加入第一個元素同值的元素?
? ? ? ? .......?
? ? ? ? copy(front2, pos1, front1);? //元素搬移?
? ? }?
? ? else {? ? //安插點之后的元素較少?
? ? ? ? push_back(back());//在尾端加入最末元素同值的元素?
? ? ? ? ......?
? ? ? ? copy_backward(pos, back2, back1);//元素搬移?
? ? }?
? ? *pos = x_copy;//在安插點上設(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之間的距離相當于?
//（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ù)量 + 末尾（當前）buffer的元素量 + 起始buffer的元素量?
}?
self& operator++()?
{?
? ? ++cur;? ? ? ? ? ? ? ? ? //切換至下一個元素?
? ? if(cur == last){? ? ? ? //如果抵達緩沖區(qū)的末尾?
? ? ? ? set_node(node + 1);? //就跳至下一個節(jié)點（緩沖區(qū)）的起點?
? ? ? ? cur = first;? ?
? ? }?
? ? return *this;?
}?
self operator++(int)?
{?
? ? self tmp = *this;?
? ? ++*this;?
? ? return tmp;?
}?
self& operator--()?
{?
? ? if(cur == first){? ? ? ? //如果目前在緩沖區(qū)開頭鳍徽，?
? ? ? ? set_node(node - 1);? //就跳至前一節(jié)點（緩沖區(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())?
? ? //目標位置在同一級緩存區(qū)?
? ? ? ? cur += n;?
? ? else{?
? ? ? //目標位置不在同一級緩存區(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圖，如下圖所示：
2.容器 queue
容器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();}?
}?
3.容器 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();}?
}?
4.容器 rb_tree
Red-Black tree（紅黑樹）是平衡二元搜尋樹（balanced Binary search tree）中常被使用的一種接剩。
平衡二院搜尋樹的特征：排列規(guī)律，有利于search和insert萨咳，并保持適度平衡懊缺，無任何節(jié)點過深。
紅黑樹的實現(xiàn)代碼：
5.容器 set培他，multiset
容器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ù)，從這點看來舀凛，set實際應該為container adapter?
}?
容器multiset的實現(xiàn)代碼如下：
6.容器 map和multimap
map的實現(xiàn)代碼如下：
multimap實現(xiàn)代碼如下：
容器map獨特的operator[]
