文章目錄

• • • 前言
    • deque 實現(xiàn)
    • • deque類
      • _Deque_iterator 類
      • deque 的元素插入 insert函數(shù)
      • deque如何模擬空間連續(xù)
    • queue 實現(xiàn)
    • stack 的實現(xiàn)

前言

---

C++容器中 deque是一個非常有趣的容器結(jié)構(gòu)，我們知道deque本身是一個支持雙向擴(kuò)容的結(jié)構(gòu)，對外表現(xiàn)出連續(xù)的存儲方式。
本節(jié)將從它的內(nèi)部實現(xiàn)抽絲剝繭，看看STL 團(tuán)隊的deque以及通過deque實現(xiàn)的queue和stack適配器的有趣實現(xiàn)。

關(guān)于deque 支持的基本接口如下：

• push_back()
• push_front()
• pop_back()
• pop_front()
• front()
• back()
• size()
• max_size()

關(guān)于接口的使用這里就不多說了，非常簡單明了。

接下來就看一下deque的實現(xiàn)。

本節(jié)涉及的源代碼是基于:gcc 2.95 版本的libstdc++ 標(biāo)準(zhǔn)庫進(jìn)行分析的。不同版本的代碼實現(xiàn)方式可能有一些差異，但是核心思想應(yīng)該是一樣的。
gcc-2.95 源碼下載

deque 實現(xiàn)

---

話不多說，先上圖

• 這個圖是 deque 在內(nèi)存中的存儲結(jié)構(gòu)，map這個指針指向的是deque的結(jié)構(gòu)。
  deque 中存儲了多個指針，分別指向不同的buffer，而實際存儲數(shù)據(jù)的就是buffer中的一個數(shù)據(jù)區(qū)域。 也就是deque實際的存儲結(jié)構(gòu)是分段連續(xù)的，并不是整個數(shù)據(jù)存儲區(qū)域都是連續(xù)的,其中灰色的區(qū)域表示還沒有進(jìn)行數(shù)據(jù)存儲的區(qū)域。

• deque的雙向push和pop功能則是通過兩端的迭代器: start 和 finish
  同時維護(hù)了一個用來訪問實際數(shù)據(jù)的迭代器，也就是我們通過deque<string>::iterator it; 這樣的方式聲明的可以在整個deque存儲結(jié)構(gòu)中訪問數(shù)據(jù)的迭代器。

• 接下來看一下iterator的結(jié)構(gòu)：

  • cur 指針 ，表示當(dāng)前iterator指向的 buffer的數(shù)據(jù)區(qū)域
  • first 指針，表示指向當(dāng)前buffer的頭部區(qū)域
  • last 指針，表示指向當(dāng)前buffer的 尾部區(qū)域
  • node 指針 則是和map指針相關(guān)聯(lián)，指向map中的一個地址

deque中的buffer區(qū)域增加和刪除 都是通過start 和 finish iterator 的指針變動來進(jìn)行維護(hù)的，這里的兩個iterator 是非常重要的。

deque 實現(xiàn)的類圖如下（代碼在 stl_deque.cc）：

從上面的類圖中我們可以看出deque的數(shù)據(jù)成員主要來自_Deque_base 和 _Deque_alloc_base兩個類，其中_Deque_base 類提供了我們的start和finish兩個迭代器，這兩個迭代器的用途我們在上面的一張deque結(jié)構(gòu)圖下已經(jīng)講過了，分別維護(hù)deque兩端的buffer區(qū)域的擴(kuò)張。

關(guān)于迭代器內(nèi)部的數(shù)據(jù)成員，我們上面的類圖也已經(jīng)給出了，右側(cè)的類圖中描述了迭代器內(nèi)部的數(shù)據(jù)成員，分別是四個指針，用來訪問buffer內(nèi)部的數(shù)據(jù)成員。

其次就是類 _Deque_alloc_base，包含map主節(jié)點的成員變量，包括map指針以及map_size的大小。

綜上，我們可以知道一個deque的對象的大小為（64位機(jī)器下）:sizeof(T*) * 8 + 8 + 4 = 72

ps：
以上大小是在gcc 2.95這個版本的stl中的元素的大小，可能新版本C++中的大小會有細(xì)微的差異

deque類

接下來我們仔細(xì)看一下deque這個類，聲明如下：

template <class _Tp, class _Alloc = __STL_DEFAULT_ALLOCATOR(_Tp), size_t __bufsiz = 0> 
class deque : protected _Deque_base<_Tp, _Alloc, __bufsiz> {typedef _Deque_base<_Tp, _Alloc, __bufsiz> _Base;
public:                         // Basic typestypedef _Tp value_type;typedef value_type* pointer;typedef const value_type* const_pointer;typedef value_type& reference;typedef const value_type& const_reference......

模版類傳入除了正常的數(shù)據(jù)類型的參數(shù)_Tp之外還包括 _Alloc，和一個size_t類型的__buffsiz，這里的buffsiz指的是每個buffer 可容納的元素總大小。

這里表明我們可以自己指定buffer 的大小，即我們通過聲明deque<int, allocator<int>, 100>的方式來自己指定buffer的大小。

如果說我們自己沒有指定，則STL默認(rèn)會將buffsiz設(shè)置為0，此時分配buffsiz空間大小的函數(shù)則會由_Deque_alloc_base 類的_M_allocate_node函數(shù)進(jìn)行空間分配，最終調(diào)用__deque_buf_size計算需要分配的大小。

_Tp* _M_allocate_node(){ return _Node_alloc_type::allocate(__deque_buf_size(__bufsiz, sizeof(_Tp))); }inline size_t
__deque_buf_size(size_t __n, size_t __size)
{return __n != 0 ? __n : (__size < 512 ? size_t(512 / __size) : size_t(1));
}

分配的大小根據(jù)傳入的buffsiz的個數(shù)來判斷:
如果n不為0，傳回n，表示buffer的大小由使用者自己定
如果n 為0，表示buffer大小使用默認(rèn)設(shè)定的，那么仍需確認(rèn)：

• 如果(sizeof(value_type))小于512B，傳回512 / sizeof(value_type)
• 如果(sizeof(value_type))大于512B，則返回1

_Deque_iterator 類

deque的迭代器是一個非常重要的實現(xiàn)，因為我們在使用deque的時候需要遍歷迭代器的元素，需要對迭代器進(jìn)行自加，或者+= n 的操作。即，用戶認(rèn)為deque是連續(xù)的存儲方式，但是本身deque的存儲方式是分段連續(xù)，所以這里需要迭代器來實現(xiàn)deque的分段連續(xù)特性，要能夠?qū)⒈闅v元素?zé)o縫從上一個buffer切換到下一個buffer，且支持+= n的一次跨越多個元素更主要的是跨越多個buffer的操作。

接下來看一下迭代器類如何實現(xiàn)上述的操作，迭代器類的實現(xiàn)如下：

#ifndef __STL_NON_TYPE_TMPL_PARAM_BUG
template <class _Tp, class _Ref, class _Ptr, size_t __bufsiz>
struct _Deque_iterator {typedef _Deque_iterator<_Tp,_Tp&,_Tp*,__bufsiz>             iterator;typedef _Deque_iterator<_Tp,const _Tp&,const _Tp*,__bufsiz> const_iterator;static size_t _S_buffer_size() { return __deque_buf_size(__bufsiz, sizeof(_Tp)); }......typedef random_access_iterator_tag iterator_category;typedef _Tp value_type;typedef _Ptr pointer;typedef _Ref reference;typedef size_t size_type;typedef ptrdiff_t difference_type;typedef _Tp** _Map_pointer;typedef _Deque_iterator _Self;//這是幾個迭代器內(nèi)部的重要指針_Tp* _M_cur;_Tp* _M_first;_Tp* _M_last;_Map_pointer _M_node;......

deque 的元素插入 insert函數(shù)

分段連續(xù)的實現(xiàn)，我們這里來看一個有趣的函數(shù)insert

//在position的位置插入一個value_type的元素
iterator insert(iterator position, const value_type& __x) {if (position._M_cur == _M_start._M_cur) {//如果安插點是deque的最前端push_front(__x);                       //則交給push_front處理return _M_start;}else if (position._M_cur == _M_finish._M_cur) { //如果安插點是deque的最末端push_back(__x);                               //則交給push_back處理iterator __tmp = _M_finish;--__tmp;return __tmp;}else {return _M_insert_aux(position, __x); //不在頭部，則不在尾部，則單獨處理，需要在分段的buffer之間跳躍}
}

可以看到insert在確認(rèn)了整個deque的兩端都沒法插入之后會調(diào)用一個_M_insert_aux函數(shù)來執(zhí)行中間部分的插入。依據(jù)deque的分段連續(xù)的實現(xiàn)，這個函數(shù)任務(wù)重大，它就是實現(xiàn)分段連續(xù)的關(guān)鍵。因為中間部分就是分段的，這個函數(shù)需要實現(xiàn)分段之間的連續(xù)跳躍以及跨段跳躍，并提供給使用者可以連續(xù)操作的接口（++,–,+=,-=）
_M_insert_aux函數(shù)實現(xiàn)如下：

template <class _Tp, class _Alloc, size_t __bufsize>
void 
deque<_Tp,_Alloc,__bufsize>::_M_insert_aux(iterator __pos,const value_type* __first,const value_type* __last,size_type __n)
{const difference_type __elemsbefore = __pos - _M_start;//獲取安插點之前的元素個數(shù)size_type __length = size();if (__elemsbefore < __length / 2) {// 如果安插點之前的元素較少，則靠近頭端插入iterator __new_start = _M_reserve_elements_at_front(__n);//調(diào)整新的start位置，預(yù)留下來足夠存儲元素n的空間iterator __old_start = _M_start;__pos = _M_start + __elemsbefore;__STL_TRY {if (__elemsbefore >= difference_type(__n)) { //確認(rèn)從原來的start 到pos之間的距離是否足夠存儲元素niterator __start_n = _M_start + difference_type(__n); //可以的話則保留元素n加入之后的位置uninitialized_copy(_M_start, __start_n, __new_start); //將m_start到start_n之間的元素都移動到new_start位置_M_start = __new_start;copy(__start_n, __pos, __old_start);//不同buffer之間的元素拷貝copy(__first, __last, __pos - difference_type(__n)); // 調(diào)整first和last指針，移動buffer內(nèi)部的元素}else {const value_type* __mid = __first + (difference_type(__n) - __elemsbefore);__uninitialized_copy_copy(_M_start, __pos, __first, __mid,__new_start);_M_start = __new_start;copy(__mid, __last, __old_start);}}__STL_UNWIND(_M_destroy_nodes(__new_start._M_node, _M_start._M_node));}else {// 如果安插點之前的元素較多（多于整個deque元素一半），則靠近尾端插入iterator //  __new_finish = _M_reserve_elements_at_back(__n);iterator __old_finish = _M_finish;const difference_type __elemsafter = difference_type(__length) - __elemsbefore;__pos = _M_finish - __elemsafter;__STL_TRY {if (__elemsafter > difference_type(__n)) {iterator __finish_n = _M_finish - difference_type(__n);uninitialized_copy(__finish_n, _M_finish, _M_finish);_M_finish = __new_finish;copy_backward(__pos, __finish_n, __old_finish);copy(__first, __last, __pos);}else {const value_type* __mid = __first + __elemsafter;__uninitialized_copy_copy(__mid, __last, __pos, _M_finish, _M_finish);_M_finish = __new_finish;copy(__first, __mid, __pos);}}__STL_UNWIND(_M_destroy_nodes(_M_finish._M_node + 1, __new_finish._M_node + 1));}
}

以上的代碼大體分為幾步：

1. 確認(rèn)插入的元素在整個deque所處的位置，如果靠近deque的頭部
   則插入頭部，插入的過程是：
   將從deque頭部到插入位置的元素向前拷貝sizeof(x)的位置（過程中可能有buffer之間的移動，以及新buffer空間的分配），再將新的元素插入當(dāng)前位置。
2. 如果在整個deque靠近尾部(小于deque.size / 2)的位置，則按照以上的方式進(jìn)行元素的移動，只不過是方向向后移動。

deque如何模擬空間連續(xù)

介紹deque模擬連續(xù)空間的實現(xiàn)之前，我們先看如下幾個函數(shù)的實現(xiàn)：

• front()函數(shù)

  //front函數(shù)返回整個deque的最開始位置，也就是_M_start所指向的位置
  reference front() { return *_M_start; }
  

• back()函數(shù)

  // 因為_M_finish是deque尾部的迭代器，且它的last指向最后一個元素的下一個元素
  // 所以需要取它的前一個指向，從而能夠訪問到deque的最后一個元素
  reference back() {iterator __tmp = _M_finish;--__tmp;return *__tmp;
  }
  

• size() 函數(shù)
  整個deque的大小就是從start 到 finish迭代器之間的距離

  size_type size() const { return _M_finish - _M_start;; }
  

到這里 我們總結(jié)一下deque模擬連續(xù)空間的功能在以上三個函數(shù)中都用到了，像操作符 *, --，- 都是經(jīng)過重載的。比如我們想要獲取deque 的大小，上面的實現(xiàn)中size僅僅是做了迭代器之間的 - 操作，但是迭代器內(nèi)部的指針計算 從 start 到 到end之間的距離（如下圖從start iterator訪問到finish iterator），這個過程內(nèi)是怎么移動的，涉及到可能跨越多個buffer的大小計算，所以這里還需要詳細(xì)看看對應(yīng)的運(yùn)算符的重載實現(xiàn)。

模擬連續(xù)空間的實現(xiàn)，迭代器功不可沒。
接下來看一下_Deque_iterator對幾個運(yùn)算符重載功能的實現(xiàn)。

• operator *
  返回了當(dāng)前迭代器中的cur指針，指向該迭代器所處buffer的元素，返回該元素的值。

  reference operator*() const { return *_M_cur; }
  

• operator ->
  返回迭代器的指針，也就是->符號訪問的還是一個迭代器

  pointer operator->() const { return _M_cur; }
  

• operator -
  兩個迭代器之間的距離相當(dāng)于：
  (1) 兩個iterator之間的buffer總長度 +
  (2) itr至其buffer末尾的長度 +
  (3) x 至其buffer起始的長度

  difference_type operator-(const _Self& __x) const {/*difference_type(_S_buffer_size()) 每個緩沖區(qū)的大小(_M_node - __x._M_node - 1) 表示完成的緩沖區(qū)的個數(shù)(_M_cur - _M_first) 末尾迭代器itr到其buffer末尾的長度(__x._M_last - __x._M_cur) x 到其buffer開頭的長度*/return difference_type(_S_buffer_size()) * (_M_node - __x._M_node - 1) +(_M_cur - _M_first) + (__x._M_last - __x._M_cur);
  }
  

• operator ++
  這里使用的是前++實現(xiàn)的后++運(yùn)算符

  _Self& operator++() {++_M_cur; //切換至下一個元素if (_M_cur == _M_last) { // 如果發(fā)現(xiàn)元素達(dá)到了buffer的邊界,由當(dāng)前迭代器的_M_last表示_M_set_node(_M_node + 1); // 就跳至下一個node點,_M_set_node實現(xiàn)在下面_M_cur = _M_first; // 將當(dāng)前的cur指向下一個node點的first節(jié)點}return *this; 
  }_Self operator++(int)  {_Self __tmp = *this;++*this; // 調(diào)用上面的 ++運(yùn)算符，即使用后++ 運(yùn)算符調(diào)用前 ++return __tmp;
  }
  // 重置當(dāng)前迭代器的幾個指針。
  void _M_set_node(_Map_pointer __new_node) {_M_node = __new_node;_M_first = *__new_node;_M_last = _M_first + difference_type(_S_buffer_size());
  }
  

• operator --
  同樣使用的是前–實現(xiàn)后–運(yùn)算符

  _Self& operator--() {if (_M_cur == _M_first) {// 減之前如果發(fā)現(xiàn)當(dāng)前節(jié)點已經(jīng)達(dá)到buffer首部邊界_M_set_node(_M_node - 1); //重置node，到node - 1(前一個buffer)_M_cur = _M_last; // 將cur指向 上一個buffer的last}--_M_cur;return *this;
  }
  _Self operator--(int) {_Self __tmp = *this;--*this;return __tmp;
  }
  

• operator +=
  += 運(yùn)算符表示支持迭代器cur指針可以跨越多個元素，這個過程難免要處理針對buffer的跨越處理

  _Self& operator+=(difference_type __n)
  {difference_type __offset = __n + (_M_cur - _M_first);if (__offset >= 0 && __offset < difference_type(_S_buffer_size()))// 目標(biāo)位置在同一buffer內(nèi)，沒有跨越緩沖區(qū)邊界_M_cur += __n;else {// 目標(biāo)位置在不同buffer內(nèi)，計算需要跨越多少個buffer// __offset / difference_type(_S_buffer_size()) difference_type __node_offset =__offset > 0 ? __offset / difference_type(_S_buffer_size()): -difference_type((-__offset - 1) / _S_buffer_size()) - 1;// 切換到了正確的buffer _M_set_node(_M_node + __node_offset);// 切換到正確的元素，使用__offset 減去跨越的緩沖區(qū)的距離，剩下的就是在新的緩沖區(qū)中的距離_M_cur = _M_first + (__offset - __node_offset * difference_type(_S_buffer_size()));}return *this;
  }//同時 + 運(yùn)算符也是借用+= 執(zhí)行的
  _Self operator+(difference_type __n) const
  {_Self __tmp = *this;return __tmp += __n;
  }
  

• operatro -=
  -= 運(yùn)算符的重載的實現(xiàn)更加便捷

  // 直接使用 += 一個-__n元素來進(jìn)行跳轉(zhuǎn)
  _Self& operator-=(difference_type __n) { return *this += -__n; }_Self operator-(difference_type __n) const {_Self __tmp = *this;return __tmp -= __n;
  }
  

• operator []
  因為deque對外體現(xiàn)的是連續(xù)的空間，所以需要提供能夠隨機(jī)訪問（下標(biāo)訪問）的能力
  這里是使用的+ 運(yùn)算符，即也就是+= 運(yùn)算符實現(xiàn)

  reference operator[](difference_type __n) const { return *(*this + __n); }
  

queue 實現(xiàn)

如下為基本的queue和stack操作，stack是先入先出

如上為queue和 stack的基本操作示意圖，queue是兩端開口，先入先出的形態(tài)。
默認(rèn)使用deque作為底層容器，并封裝了一些deque的細(xì)節(jié)，所以queue和stack也被成為適配器，并不是標(biāo)準(zhǔn)的容器。
實現(xiàn)代碼如下：

#ifndef __STL_LIMITED_DEFAULT_TEMPLATES
template <class _Tp, class _Sequence = deque<_Tp> > //deque實現(xiàn)底層容器
#else
template <class _Tp, class _Sequence>
#endif
class queue {friend bool operator== __STL_NULL_TMPL_ARGS (const queue&, const queue&);friend bool operator< __STL_NULL_TMPL_ARGS (const queue&, const queue&);
public:typedef typename _Sequence::value_type      value_type;typedef typename _Sequence::size_type       size_type;typedef          _Sequence                  container_type;typedef typename _Sequence::reference       reference;typedef typename _Sequence::const_reference const_reference;
protected:_Sequence c; // 底層容器 deque
public:queue() : c() {}explicit queue(const _Sequence& __c) : c(__c) {}/*queue 的功能都交給deque，調(diào)用對應(yīng)的deque接口實現(xiàn)*/bool empty() const { return c.empty(); }size_type size() const { return c.size(); }reference front() { 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(__x); }void pop() { c.pop_front(); }
};

這里 說一下為什么 queue和 stack都默認(rèn)使用deque作為底層容器？
可以看到queue的接口也就是上面中的那一些，也即只要有其他的容器能夠提供類似于上面的幾個接口，也能作為queue和stack的底層容器。這里有l(wèi)ist也能夠作為底層的容器，但是STL團(tuán)隊選擇deque肯定是有原因的，唯一的差異就是性能了，驗證代碼如下：

#include <iostream>
#include <deque>
#include <list>
#include <queue>
#include <ctime>using namespace std;int main()
{clock_t time_start = clock();	queue<int, list<int> > q;for (int i = 0 ;i < 1000000; i++) {q.push(i);}cout << "list as container of queue, push time is " << clock() - time_start << endl;time_start = clock();queue<int> Q;for (int i = 0 ;i < 1000000; i++) {Q.push(i);}cout << "deque as container of queue, push time is " << clock() - time_start << endl;return 0;
}

輸出如下:

list as container of queue, push time is 153782 # 微秒
deque as container of queue, push time is 45401 # 微秒

可以看到push 100萬個元素分別到不同容器實現(xiàn)的queue中，deque的實現(xiàn)性能要優(yōu)于queue接近四倍。

stack 的實現(xiàn)

同樣內(nèi)含deque，作為底層容器

#ifndef __STL_LIMITED_DEFAULT_TEMPLATES
template <class _Tp, class _Sequence = deque<_Tp> > // 同樣使用 deque作為底層容器
#else
template <class _Tp, class _Sequence>
#endif
class stack {friend bool operator== __STL_NULL_TMPL_ARGS (const stack&, const stack&);friend bool operator< __STL_NULL_TMPL_ARGS (const stack&, const stack&);
public:typedef typename _Sequence::value_type      value_type;typedef typename _Sequence::size_type       size_type;typedef          _Sequence                  container_type;typedef typename _Sequence::reference       reference;typedef typename _Sequence::const_reference const_reference;
protected:_Sequence _M_c;
public:stack() : _M_c() {}explicit stack(const _Sequence& __s) : _M_c(__s) {}bool empty() const { return _M_c.empty(); }size_type size() const { return _M_c.size(); }reference top() { return _M_c.back(); }const_reference top() const { return _M_c.back(); }void push(const value_type& __x) { _M_c.push_back(__x); }void pop() { _M_c.pop_back(); }
};

這里說一個注意事項：

我們知道所有的標(biāo)準(zhǔn)容器，list,vector,deque,set,map 是都允許使用迭代器進(jìn)行元素的遍歷，但是stack和queue 不允許。因為如果允許迭代器進(jìn)行遍歷，也就意味著迭代器可以對元素進(jìn)行任意的插入和刪除，那么也就破壞了stack和queue本身想要組織的數(shù)據(jù)形態(tài)

所以這樣的代碼
queue<string>::iterator ite; 會編譯出錯

no template named 'iterator' in'std::__1::queue<std::__1::basic_string<char>,std::__1::deque<std::__1::basic_string<char>,std::__1::allocator<std::__1::basic_string<char> > > >'; did you meansimply 'iterator'?

我們在queue中說了，只要支持queue和stack的底層操作，底層容器的選擇可以有其他的實現(xiàn)。那vector是否可以作為以上兩者的容器呢？
測試代碼：

#include <iostream>
#include <deque>
#include <list>
#include <queue>
#include <ctime>
#include <stack>
using namespace std;int main()
{clock_t time_start = clock();	queue<int, vector<int> > q;for (int i = 0; i < 10; ++i) {q.push(i);}q.front();q.back();q.empty();q.size();q.pop();stack<int, vector<int>> s;for (int i = 0; i < 10; ++i) {s.push(i);}s.top();s.empty();s.size();s.pop();return 0;
}

編譯以上代碼，發(fā)現(xiàn)出錯，發(fā)現(xiàn)是queue使用vector時，底層容器vector并沒有pop_front的成員函數(shù)，而stack可以使用vector作為底層容器。

error: no member named 'pop_front' in 'std::__1::vector<int,std::__1::allocator<int> >'void pop() {c.pop_front();}~ ^
STL_deque.cc:22:4: note: in instantiation of member function'std::__1::queue<int, std::__1::vector<int, std::__1::allocator<int> >>::pop' requested hereq.pop();

有趣的結(jié)構(gòu)，有趣的實現(xiàn)。

總結(jié)

以上是生活随笔為你收集整理的C++ STL: 超详细 容器 deque 以及 适配器queue 和 stack 源码分析的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。