c++stack(堆棧）是一個(gè)容器的改編，它實(shí)現(xiàn)了一個(gè)先進(jìn)后出的數(shù)據(jù)結(jié)構(gòu)（FILO）
使用該容器時(shí)需要包含#include<stack>頭文件；
定義stack對(duì)象的示例代碼如下：
stack<int>s1;
stack<string>s2;
stack的基本操作有：
1.入棧：如s.push(x);
2.出棧:如 s.pop().注意：出棧操作只是刪除棧頂?shù)脑?，并不返回該元素?br> 3.訪問棧頂：如s.top();
4.判斷棧空：如s.empty().當(dāng)?？諘r(shí)返回true。
5.訪問棧中的元素個(gè)數(shù)，如s.size（）;
下面舉一個(gè)簡單的例子：

#include<iostream>  
#include<stack>  
using namespace std;  
int main(void)  
{  
    stack<double>s;//定義一個(gè)棧  
    for(int i=0;i<10;i++)  
        s.push(i);  
    while(!s.empty())  
    {  
        printf("%lf\n",s.top());  
        s.pop();  
    }  
    cout<<"棧內(nèi)的元素的個(gè)數(shù)為："<<s.size()<<endl;  
    return 0;  
}

1.容器deque

deque是一種分段連續(xù)的容器，特點(diǎn)是雙向開口，可以認(rèn)為它是一段連續(xù)的內(nèi)存空間，不僅可以向前方增加內(nèi)存空間，也可以向后方增加內(nèi)存空間。
在實(shí)際內(nèi)存中實(shí)現(xiàn)雙向擴(kuò)充是比較復(fù)雜的事情，那么deque中是如何實(shí)現(xiàn)的呢？deque通過一個(gè)控制器來串聯(lián)一系列的緩沖器（buffer），從而達(dá)到邏輯上的連續(xù)效果。
deque的內(nèi)存管理示意圖，如下圖所示：

deque是通過一個(gè)vector在維護(hù)自身的控制器，在控制器中存儲(chǔ)的是指向buffer的指針，因此我們需要用一個(gè)指向指針的指針來指向這個(gè)vector的地址。
deque能在邏輯上實(shí)現(xiàn)內(nèi)存連續(xù)，最關(guān)鍵的是iterator在起作用。迭代器運(yùn)行到邊界的時(shí)候，都需要檢測是否到邊界，然后通過回到控制buffer的那個(gè)vector來管理邊界的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的插入問題：
元素插入的時(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 <class T, class Alloc, size_t BufSize>  
typename deque<T, Alloc, BufSize>::iterator_deque<T, Alloc, BufSIze>:: 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的總長度+  
//（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;                   //切換至下一個(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ū)開頭，  
        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圖，如下圖所示：

2.容器 queue

容器queue是以deque為底層結(jié)構(gòu)實(shí)現(xiàn)的，具體代碼如下：

template <class T, class Sequence = deque<T>>  
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 T, class Sequence = deque<T>>  
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é)點(diǎn)過深。

紅黑樹的實(shí)現(xiàn)代碼：

5.容器 set，multiset

容器set的實(shí)現(xiàn)代碼：

template <class Key, class Compare = less<Key>, 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<key_type, value_type, identity<value_type<. key_compare, Alloc> rep_type;  
     rep_type t;  
 public:  
      typedef typename rep_type::const_iterator iterator;    
...  
//set的所有操作，都調(diào)用底層rb_tree的函數(shù)，從這點(diǎn)看來，set實(shí)際應(yīng)該為container adapter  
}  

容器multiset的實(shí)現(xiàn)代碼如下：

6.容器 map和multimap

map的實(shí)現(xiàn)代碼如下：

multimap實(shí)現(xiàn)代碼如下：

容器map獨(dú)特的operator[]