2 萬字 - 20 圖帶你手撕 STL 容器源碼

前言

源碼之前，了無祕密。

在 STL 編程中，容器是我們經常會用到的一種數據結構，容器分爲序列式容器和關聯式容器。

兩者的本質區別在於：序列式容器是通過元素在容器中的位置順序存儲和訪問元素，而關聯容器則是通過鍵 (key) 存儲和讀取元素。

本篇着重剖析序列式容器相關背後的知識點。

容器分類

前面提到了，根據元素存儲方式的不同，容器可分爲序列式和關聯式，那具體的又有哪些分類呢，這裏我畫了一張圖來看一下。

限於篇幅，這篇文章小賀會來重點講解一下經常使用到的那些容器，比如 vector，list，deque，以及衍生的棧和隊列其背後核心的設計和奧祕，不多 BB， 馬上就來分析。

vector

寫 C++ 的小夥伴們，應該對 vector 都非常熟悉了，vector 基本能夠支持任何類型的對象，同時它也是一個可以動態增長的數組，使用起來非常的方便。

但如果我問你，知道它是如何做到動態擴容的嗎？哎，是不是一時半會答不上來了，哈哈，沒事，我們一起來看看。

vector 基本數據結構

基本上，STL 裏面所有的容器的源碼都包含至少三個部分：

• 迭代器，遍歷容器的元素，控制容器空間的邊界和元素的移動；

• 構造函數，滿足容器的多種初始化；

• 屬性的獲取，比如 begin()，end() 等；

vector 也不例外，其實看了源碼之後就發現，vector 相反是所有容器裏面最簡單的一種。

template <class T, class Alloc = alloc>
class vector {
public:
   // 定義 vector 自身的嵌套型別
    typedef T value_type;
    typedef value_type* pointer;
    typedef const value_type* const_pointer;
    // 定義迭代器, 這裏就只是一個普通的指針
    typedef value_type* iterator;
    typedef const value_type* const_iterator;
    typedef value_type& reference;
    typedef const value_type& const_reference;
    typedef size_t size_type;
    typedef ptrdiff_t difference_type;
    ...
  protected:
    typedef simple_alloc<value_type, Alloc> data_allocator; // 設置其空間配置器
    iterator start;    // 當前使用空間的頭
    iterator finish;   // 當前使用空間的尾
    iterator end_of_storage; // 當前可用空間的尾
    ...
};

因爲 vector 需要表示用戶操作的當前數據的起始地址，結束地址，還需要其真正的最大地址。所以總共需要 3 個迭代器，分別來指向數據的頭 (start)，數據的尾 (finish)，數組的尾 (end_of_storage)。

構造函數

vector 有多個構造函數, 爲了滿足多種初始化。

我們看到，這裏面，初始化滿足要麼都初始化成功， 要麼一個都不初始化並釋放掉拋出異常，在 STL 裏面，異常機制這塊拿捏的死死的呀。

因爲 vector 是一種 class template， 所以呢，我們並不需要手動的釋放內存， 生命週期結束後就自動調用析構從而釋放調用空間，當然我們也可以直接調用析構函數釋放內存。

void deallocate() {
 if (start) 
        data_allocator::deallocate(start, end_of_storage - start);
}
// 調用析構函數並釋放內存
~vector()  { 
 destroy(start, finish);
 deallocate();
}

屬性獲取

下面的部分就涉及到了位置參數的獲取， 比如返回 vector 的開始和結尾，返回最後一個元素，返回當前元素個數，元素容量，是否爲空等。

這裏需要注意的是因爲 end() 返回的是 finish，而 finish 是指向最後一個元素的後一個位置的指針，所以使用 end() 的時候要注意。

public:
 // 獲取數據的開始以及結束位置的指針. 記住這裏返回的是迭代器, 也就是 vector 迭代器就是該類型的指針.
    iterator begin() { return start; }
    iterator end() { return finish; }
    reference front() { return *begin(); } // 獲取值
    reference back() { return *(end() - 1); } 
    ...
    size_type size() const { return size_type(end() - begin()); }  // 數組元素的個數
    size_type max_size() const { return size_type(-1) / sizeof(T); } // 最大能存儲的元素個數
    size_type capacity() const { return size_type(end_of_storage - begin()); } // 數組的實際大小
    bool empty() const { return begin() == end(); } 
    //判斷 vector 是否爲空， 並不是比較元素爲 0，是直接比較頭尾指針。

push 和 pop 操作

vector 的 push 和 pop 操作都只是對尾進行操作， 這裏說的尾部是指數據的尾部。當調用 push_back 插入新元素的時候，首先會檢查是否有備用空間，如果有就直接在備用空間上構造元素，並調整迭代器 finish。

當如果沒有備用空間，就擴充空間 (重新配置 - 移動數據 - 釋放原空間)，這裏實際是調用了另外一個函數：insert_aux 函數。

在上面這張圖裏，可以看到，push_back 這個函數里面又判斷了一次 finish != end_of_storage 這是因爲啥呢？這裏的原因是因爲 insert_aux 函數可能還被其他函數調用哦。

在下面的 else 分支裏面，我們看到了 vector 的動態擴容機制：如果原空間大小爲 0 則分配 1 個元素，如果大於 0 則分配原空間兩倍的新空間，然後把數據拷貝過去。

pop 元素：從尾端刪除一個元素。

public:
  //將尾端元素拿掉 並調整大小
  void pop_back() {
      --finish;//將尾端標記往前移動一個位置 放棄尾端元素
      destroy(finish);
  }

erase 刪除元素

erase 函數清除指定位置的元素， 其重載函數用於清除一個範圍內的所有元素。實際實現就是將刪除元素後面所有元素往前移動，對於 vector 來說刪除元素的操作開銷還是很大的，所以說 vector 它不適合頻繁的刪除操作，畢竟它是一個數組。

//清楚[first, last)中的所有元素
  iterator erase(iterator first, iterator last) {
      iterator i = copy(last, finish, first);
      destroy(i, finish);
      finish = finish - (last - first);
      return first;
  }
  //清除指定位置的元素
  iterator erase(iterator position) {
      if (position + 1 != end()) 
          copy(position + 1, finish, position);//copy 全局函數
      }      
      --finish;
      destroy(finish);
      return position;
  }
  void clear() {
      erase(begin(), end());
  }

我們結合圖解來看一下:

清楚範圍內的元素，第一步要將 finish 迭代器後面的元素拷貝回去，然後返回拷貝完成的尾部迭代器，最後在刪除之前的。

刪除指定位置的元素就是實際就是將指定位置後面的所有元素向前移動, 最後析構掉最後一個元素。

insert 插入元素

vector 的插入元素具體來說呢，又分三種情況：

1、如果備用空間足夠且插入點的現有元素多於新增元素；

2、如果備用空間足夠且插入點的現有元素小於新增元素；

3、如果備用空間不夠；

我們一個一個來分析。

• 插入點之後的現有元素個數 > 新增元素個數

• 插入點之後的現有元素個數 <= 新增元素個數

如果備用空間不足

這裏呢，要注意一個坑，就是所謂的迭代器失效問題。通過圖解我們就明白了，所謂的迭代器失效問題是由於元素空間重新配置導致之前的迭代器訪問的元素不在了，總結來說有兩種情況：

• 由於插入元素，使得容器元素整體遷移導致存放原容器元素的空間不再有效，從而使得指向原空間的迭代器失效。

• 由於刪除元素，使得某些元素次序發生變化導致原本指向某元素的迭代器不再指向期望指向的元素。

前面提到的一些全局函數，這裏在總結一下：

• copy(a,b,c)：將 (a,b) 之間的元素拷貝到 (c,c-(b-a)) 位置

• uninitialized_copy(first, last, result)：具體作用是將 [first,last) 內的元素拷貝到 result 從前往後拷貝

• copy_backward(first, last, result)：將 [first,last) 內的元素拷貝到 result 從後往前拷貝

vector 總結

到這裏呢，vector 分析的就差不多了，最後提醒需要注意的是：vector 的成員函數都不做邊界檢查 (at 方法會拋異常)，使用者要自己確保迭代器和索引值的合法性。

我們來總結一下 vector 的優缺點。

優點

• 在內存中是分配一塊連續的內存空間進行存儲，可以像數組一樣操作，並且支持動態擴容。

• 因此元素的隨機訪問方便，支持下標訪問和 vector.at() 操作。

• 節省空間。

缺點

• 由於其順序存儲的特性，vector 插入刪除操作的時間複雜度是 O(n)。

• 只能在末端進行 pop 和 push。

• 當動態長度超過默認分配大小後，要整體重新分配、拷貝和釋放空間。

list

好了，下面我們來看一下 list，list 是一種雙向鏈表。

list 的設計更加複雜一點，好處是每次插入或刪除一個元素，就配置或釋放一個元素，list 對於空間的運用有絕對的精準，一點也不浪費。而且對於任何位置的元素插入或刪除，list 永遠是常數空間。

注意：list 源碼裏其實分了兩個部分，一個部分是 list 結構，另一部分是 list 節點的結構。

那這裏不妨思考一下，爲什麼 list 節點分爲了兩個部分，而不是在一個結構體裏面呢? 也就是說爲什麼指針變量和數據變量分開定義呢？

如果看了後面的源碼就曉得了，這裏是爲了給迭代器做鋪墊，因爲迭代器遍歷的時候不需要數據成員的，只需要前後指針就可以遍歷該 list。　

list 的節點結構如下圖所示：

list 數據結構 - 節點

__list_node 用來實現節點，數據結構中就儲存前後指針和屬性。

template <class T> struct __list_node {
    // 前後指針
   typedef void* void_pointer;
   void_pointer next;
   void_pointer prev;
    // 屬性
   T data;
};

來瞅一瞅，list 的節點長啥樣，因爲 list 是一種雙向鏈表，所以基本結構就是下面這個樣子：

基本類型

template<class T, class Ref, class Ptr> struct __list_iterator {
   typedef __list_iterator<T, T&, T*>     iterator; // 迭代器
   typedef __list_iterator<T, const T&, const T*> const_iterator;
   typedef __list_iterator<T, Ref, Ptr>    self;  
 
    // 迭代器是bidirectional_iterator_tag類型
   typedef bidirectional_iterator_tag iterator_category;
   typedef T value_type;
   typedef Ptr pointer;
   typedef Ref reference;
   typedef size_t size_type;
   typedef ptrdiff_t difference_type;
    ... 
};

構造函數

template<class T, class Ref, class Ptr> struct __list_iterator {
    ...
    // 定義節點指針
   typedef __list_node<T>* link_type;
   link_type node;
 // 構造函數
   __list_iterator(link_type x) : node(x) {}
   __list_iterator() {}
   __list_iterator(const iterator& x) : node(x.node) {}
   ... 
};

重載

template<class T, class Ref, class Ptr> struct __list_iterator  {
    ...
 // 重載
   bool operator==(const self& x) const { return node == x.node; }
   bool operator!=(const self& x) const { return node != x.node; }
    ...

    // ++和--是直接操作的指針指向next還是prev, 因爲list是一個雙向鏈表
   self& operator++() { 
     node = (link_type)((*node).next);
     return *this;
   }
   self operator++(int) { 
     self tmp = *this;
     ++*this;
     return tmp;
   }
   self& operator--() { 
     node = (link_type)((*node).prev);
     return *this;
   }
   self operator--(int)  { 
     self tmp = *this;
     --*this;
     return tmp;
   }
};

list 結構

list 自己定義了嵌套類型滿足 traits 編程， list 迭代器是 bidirectional_iterator_tag 類型，並不是一個普通指針。

list 在定義 node 節點時， 定義的不是一個指針，這裏要注意。

template <class T, class Alloc = alloc>
class list {
protected:
    typedef void* void_pointer;
    typedef __list_node<T> list_node; // 節點 就是前面分析過的
    typedef simple_alloc<list_node, Alloc> list_node_allocator; // 空間配置器
public:      
    // 定義嵌套類型
    typedef T value_type;
    typedef value_type* pointer;
    typedef const value_type* const_pointer;
    typedef value_type& reference;
    typedef const value_type& const_reference;
    typedef list_node* link_type;
    typedef size_t size_type;
    typedef ptrdiff_t difference_type;
    
protected:
    // 定義一個節點, 這裏節點並不是一個指針.
    link_type node;
    
public:
    // 定義迭代器
    typedef __list_iterator<T, T&, T*>             iterator;
    typedef __list_iterator<T, const T&, const T*> const_iterator;
 ...
};

list 構造和析構函數實現

構造函數前期準備：

每個構造函數都會創造一個空的 node 節點，爲了保證我們在執行任何操作都不會修改迭代器。

list 默認使用 alloc 作爲空間配置器，並根據這個另外定義了一個 list_node_allocator，目的是更加方便以節點大小來配置單元。

template <class T, class Alloc = alloc>
class list {
protected:
    typedef void* void_pointer;
    typedef __list_node<T> list_node; // 節點
    typedef simple_alloc<list_node, Alloc> list_node_allocator; // 空間配置器

其中，list_node_allocator(n) 表示配置 n 個節點空間。以下四個函數，分別用來配置，釋放，構造，銷燬一個節點。

class list {
protected:
 // 配置一個節點並返回
  link_type get_node() { return list_node_allocator::allocate(); }
  // 釋放一個節點
  void put_node(link_type p) { list_node_allocator::deallocate(p); }
 // 產生(配置並構造)一個節點帶有元素初始值
  link_type create_node(const T& x) {
      link_type p = get_node();
      __STL_TRY {
        construct(&p->data, x);
      }
      __STL_UNWIND(put_node(p));
      return p;
  }
//銷燬(析構並釋放)一個節點
  void destroy_node(link_type p) {
    destroy(&p->data);
    put_node(p);
  }
  // 對節點初始化
  void empty_initialize() { 
    node = get_node();
    node->next = node;
    node->prev = node;
  }  
};

基本屬性獲取

template <class T, class Alloc = alloc>
class list {
    ...
public: 
 iterator begin() { return (link_type)((*node).next); } // 返回指向頭的指針
    const_iterator begin() const { return (link_type)((*node).next); }
    iterator end() { return node; } // 返回最後一個元素的後一個的地址
    const_iterator end() const { return node; }
    
    // 這裏是爲旋轉做準備, rbegin返回最後一個地址, rend返回第一個地址. 我們放在配接器裏面分析
    reverse_iterator rbegin() { return reverse_iterator(end()); }
    const_reverse_iterator rbegin() const { 
      return const_reverse_iterator(end()); 
    }
    reverse_iterator rend() { return reverse_iterator(begin()); }
    const_reverse_iterator rend() const { 
      return const_reverse_iterator(begin());
    } 
    
    // 判斷是否爲空鏈表, 這是判斷只有一個空node來表示鏈表爲空.
    bool empty() const { return node->next == node; }
    // 因爲這個鏈表, 地址並不連續, 所以要自己迭代計算鏈表的長度.
    size_type size() const {
      size_type result = 0;
      distance(begin(), end(), result);
      return result;
    }
    size_type max_size() const { return size_type(-1); }
    // 返回第一個元素的值
    reference front() { return *begin(); }
    const_reference front() const { return *begin(); }
    // 返回最後一個元素的值
    reference back() { return *(--end()); }
    const_reference back() const { return *(--end()); }
    
    // 交換
    void swap(list<T, Alloc>& x) { __STD::swap(node, x.node); }
    ...
};
template <class T, class Alloc>
inline void swap(list<T, Alloc>& x, list<T, Alloc>& y) {
   x.swap(y);
}

list 的頭插和尾插

因爲 list 是一個循環的雙鏈表， 所以 push 和 pop 就必須實現是在頭插入，刪除還是在尾插入和刪除。

在 list 中，push 操作都調用 insert 函數， pop 操作都調用 erase 函數。

template <class T, class Alloc = alloc>
class list {
    ...
    // 直接在頭部或尾部插入
    void push_front(const T& x) { insert(begin(), x); } 
    void push_back(const T& x) { insert(end(), x); }
    // 直接在頭部或尾部刪除
    void pop_front() { erase(begin()); } 
    void pop_back() { 
      iterator tmp = end();
      erase(--tmp);
    }
    ...
};

上面的兩個插入函數內部調用的 insert 函數。

class list {
    ...
public:
  // 最基本的insert操作, 之插入一個元素
  iterator insert(iterator position, const T& x) {
      // 將元素插入指定位置的前一個地址
    link_type tmp = create_node(x);
    tmp->next = position.node;
    tmp->prev = position.node->prev;
    (link_type(position.node->prev))->next = tmp;
    position.node->prev = tmp;
    return tmp;
  }

這裏需要注意的是

• 節點實際是以 node 空節點開始的。

• 插入操作是將元素插入到指定位置的前一個地址進行插入的。

刪除操作

刪除元素的操作大都是由 erase 函數來實現的，其他的所有函數都是直接或間接調用 erase。

list 是鏈表，所以鏈表怎麼實現刪除元素， list 就在怎麼操作：很簡單，先保留前驅和後繼節點， 再調整指針位置即可。

由於它是雙向環狀鏈表，只要把邊界條件處理好，那麼在頭部或者尾部插入元素操作幾乎是一樣的，同樣的道理，在頭部或者尾部刪除元素也是一樣的。

template <class T, class Alloc = alloc>
class list {
    ...
 iterator erase(iterator first, iterator last);
    void clear();   
    // 參數是一個迭代器 修改該元素的前後指針指向再單獨釋放節點就行了
 iterator erase(iterator position) {
      link_type next_node = link_type(position.node->next);
      link_type prev_node = link_type(position.node->prev);
      prev_node->next = next_node;
      next_node->prev = prev_node;
      destroy_node(position.node);
      return iterator(next_node);
    }
    ...
};
...
}

list 內部提供一種所謂的遷移操作 (transfer)：將某連續範圍的元素遷移到某個特定位置之前，技術上實現其實不難，就是節點之間的指針移動，只要明白了這個函數的原理，後面的 splice，sort，merge 函數也就一一知曉了，我們來看一下 transfer 的源碼：

template <class T, class Alloc = alloc>
class list {
    ...
protected:
    void transfer(iterator position, iterator first, iterator last) {
      if (position != last) {
        (*(link_type((*last.node).prev))).next = position.node;
        (*(link_type((*first.node).prev))).next = last.node;
        (*(link_type((*position.node).prev))).next = first.node;  
        link_type tmp = link_type((*position.node).prev);
        (*position.node).prev = (*last.node).prev;
        (*last.node).prev = (*first.node).prev; 
        (*first.node).prev = tmp;
      }
    }
    ...
};

上面代碼的七行分別對應下圖的七個步驟，看明白應該不難吧。

另外 list 的其它的一些成員函數這裏限於篇幅，就不貼出源碼了，簡單說一些注意點。

splice 函數： 將兩個鏈表進行合併：內部就是調用的 transfer 函數。

merge 函數： 將傳入的 list 鏈表 x 與原鏈表按從小到大合併到原鏈表中 (前提是兩個鏈表都是已經從小到大排序了). 這裏 merge 的核心就是 transfer 函數。

reverse 函數： 實現將鏈表翻轉的功能：主要是 list 的迭代器基本不會改變的特點, 將每一個元素一個個插入到 begin 之前。

sort 函數： list 這個容器居然還自己實現一個排序，看一眼源碼就發現其實內部調用的 merge 函數，用了一個數組鏈表用來存儲 2^i 個元素, 當上一個元素存儲滿了之後繼續往下一個鏈表存儲, 最後將所有的鏈表進行 merge 歸併 (合併), 從而實現了鏈表的排序。

賦值操作： 需要考慮兩個鏈表的實際大小不一樣時的操作：如果原鏈表大 : 複製完後要刪除掉原鏈表多餘的元素；如果原鏈表小 : 複製完後要還要將 x 鏈表的剩餘元素以插入的方式插入到原鏈表中。

resize 操作： 重新修改 list 的大小，傳入一個 new_size，如果鏈表舊長度大於 new_size 的大小, 那就刪除後面多餘的節點。

clear 操作： 清除所有節點：遍歷每一個節點，銷燬 (析構並釋放) 一個節點。

remove 操作： 清除指定值的元素：遍歷每一個節點，找到就移除。

unique 操作： 清除數值相同的連續元素，注意只有 “連續而相同的元素”，纔會被移除剩一個：遍歷每一個節點，如果在此區間段有相同的元素就移除之。

感興趣的讀者可以自行去閱讀源碼體會。

list 總結

我們來總結一下。

list 是一種雙向鏈表。每個結點都包含一個數據域、一個前驅指針 prev 和一個後驅指針 next。

由於其鏈表特性，實現同樣的操作，相對於 STL 中的通用算法， list 的成員函數通常有更高的效率，內部僅需做一些指針的操作，因此儘可能選擇 list 成員函數。

優點

• 在內部方便進行插入刪除操作。

• 可在兩端進行 push 和 pop 操作。

缺點

• 不支持隨機訪問，即下標操作和. at()。

• 相對於 vector 佔用內存多。

deque

下面到了本篇最硬核的內容了，接下來我們學習一下 雙端隊列 deque 。

deque 的功能很強大。

首先來一張圖吧。

上面就是 deque 的示例圖，deque 和 vector 的最大差異一在於 deque 允許常數時間內對頭端或尾端進行元素的插入或移除操作。

二在於 deque 沒有所謂的容量概念，因爲它是動態地以分段連續空間組合而成隨時可以增加一塊新的空間並拼接起來。

雖然 deque 也提供 隨機訪問的迭代器，但它的迭代器和前面兩種容器的都不一樣，其設計相當複雜度和精妙，因此，會對各種運算產生一定影響，除非必要，儘可能的選擇使用 vector 而非 deque。一一來探究下吧。

deque 的中控器

deque 在邏輯上看起來是連續空間，內部確實是由一段一段的定量連續空間構成。

一旦有必要在 deque 的前端或尾端增加新空間，deque 便會配置一段定量的連續空間，串接在整個 deque 的頭部或尾部。

設計 deque 的大師們，想必設計的時候遇到的最大挑戰就是如何在這些分段的定量連續空間上，還能維護其整體連續的假象，並提供其隨機存取的接口，從而避開了像 vector 那樣的 “重新配置 - 複製 - 釋放” 開銷三部曲。

這樣一來，雖然開銷降低，卻提高了複雜的迭代器架構。

因此 deque 數據結構的設計和迭代器前進或後退等操作都非常複雜。

deque 採用一塊所謂的 map （注意不是 STL 裏面的 map 容器）作爲中控器，其實就是一小塊連續空間，其中的每個元素都是指針，指向另外一段較大的連續線性空間，稱之爲**緩衝區。**在後面我們看到，緩衝區纔是 deque 的儲存空間主體。

#ifndef __STL_NON_TYPE_TMPL_PARAM_BUG
template <class T, class Ref, class Ptr, size_t BufSiz>
class deque {
public:
  typedef T value_type;
  typedef value_type* pointer;
  ...
protected:
  typedef pointer** map_pointer;
  map_pointer map;//指向 map，map 是連續空間，其內的每個元素都是一個指針。
  size_type map_size;
  ...
};

其示例圖如下：deque 的結構設計中，map 和 node-buffer 的關係如下：

deque 的迭代器

deque 是分段連續空間，維持其 “整體連續” 假象的任務，就靠它的迭代器來實現，也就是 operator++ 和 operator-- 兩個運算子上面。

在看源碼之前，我們可以思考一下，如果讓你來設計，你覺得 deque 的迭代器應該具備什麼樣的結構和功能呢？

首先第一點，我們能想到的是，既然是分段連續，迭代器應該能指出當前的連續空間在哪裏；

其次，第二點因爲緩衝區有邊界，迭代器還應該要能判斷，當前是否處於所在緩衝區的邊緣，如果是，一旦前進或後退，就必須跳轉到下一個或上一個緩衝區；

第三點，也就是實現前面兩種情況的前提，迭代器必須能隨時控制中控器。

有了這樣的思想準備之後，我們再來看源碼，就顯得容易理解一些了。

template <class T, class Ref, class Ptr, size_t BufSiz>
struct __deque_iterator {
 // 迭代器定義
  typedef __deque_iterator<T, T&, T*, BufSiz>             iterator;
  typedef __deque_iterator<T, const T&, const T*, BufSiz> const_iterator;
  static size_t buffer_size() {return __deque_buf_size(BufSiz, sizeof(T)); }
 // deque是random_access_iterator_tag類型
  typedef random_access_iterator_tag iterator_category;
  // 基本類型的定義, 滿足traits編程
  typedef T value_type;
  typedef Ptr pointer;
  typedef Ref reference;
  typedef size_t size_type;
  typedef ptrdiff_t difference_type;
  // node
  typedef T** map_pointer;
  map_pointer node;
  typedef __deque_iterator self;
  ...
};

deque 的每一個緩衝區由設計了三個迭代器（爲什麼這樣設計？）

struct __deque_iterator {
 ...
  typedef T value_type;
  T* cur;
  T* first;
  T* last;
  typedef T** map_pointer;
  map_pointer node;
  ...
};

對啊，它爲什麼要這樣設計呢？回到前面我們剛纔說的，因爲它是分段連續的空間。

下圖描繪了 deque 的中控器、緩衝區、迭代器之間的相互關係：

看明白了嗎，每一段都指向一個緩衝區 buffer，而緩衝區是需要知道每個元素的位置的，所以需要這些迭代器去訪問。

其中 cur 表示當前所指的位置；

first 表示當前數組中頭的位置；

last 表示當前數組中尾的位置。

這樣就方便管理，需要注意的是 deque 的空間是由 map 管理的， 它是一個指向指針的指針， 所以三個參數都是指向當前的數組，但這樣的數組可能有多個，只是每個數組都管理這 3 個變量。

那麼，緩衝區大小是誰來決定的呢？這裏呢，用來決定緩衝區大小的是一個全局函數:

inline size_t __deque_buf_size(size_t n, size_t sz) {
  return n != 0 ? n : (sz < 512 ? size_t(512 / sz): size_t(1));
}
//如果 n 不爲0，則返回 n，表示緩衝區大小由用戶自定義
//如果 n == 0，表示 緩衝區大小默認值
//如果 sz = (元素大小 sizeof(value_type)) 小於 512 則返回 521/sz
//如果 sz 不小於 512 則返回 1

我們來舉例說明一下：

假設我們現在構造了一個 int 類型的 deque，設置緩衝區大小等於 32，這樣一來，每個緩衝區可以容納 32/sizeof(int) = 4 個元素。經過一番操作之後，deque 現在有 20 個元素了，那麼成員函數 begin() 和 end() 返回的兩個迭代器應該是怎樣的呢？

如下圖所示：

20 個元素需要 20/(sizeof(int)) = 3 個緩衝區。

所以 map 運用了三個節點，迭代器 start 內的 cur 指針指向緩衝區的第一個元素，迭代器 finish 內的 cur 指針指向緩衝區的最後一個元素 (的下一個位置)。

注意，最後一個緩衝區尚有備用空間，如果之後還有新元素插入，則直接插入到備用空間。

deque 迭代器的操作

主要就是兩種：前進和後退。

operator++ 操作代表是需要切換到下一個元素，這裏需要先切換再判斷是否已經到達緩衝區的末尾。

self& operator++() { 
  ++cur;      //切換至下一個元素
  if (cur == last) {   //如果已經到達所在緩衝區的末尾
     set_node(node+1);  //切換下一個節點
     cur = first;  
  }
  return *this;
}

operator-- 操作代表切換到上一個元素所在的位置，需要先判斷是否到達緩衝區的頭部，再後退。

self& operator--() {     
  if (cur == first) {    //如果已經到達所在緩衝區的頭部
     set_node(node - 1); //切換前一個節點的最後一個元素
     cur = last;  
  }
  --cur;       //切換前一個元素
  return *this;
}  //結合前面的分段連續空間，你在想一想這樣的設計是不是合理呢？

deque 的構造和析構函數

deque 的構造函數有多個重載函數，接受大部分不同的參數類型，基本上每一個構造函數都會調用 create_map_and_nodes，這就是構造函數的核心，後面我們來分析這個函數的實現。

template <class T, class Alloc = alloc, size_t BufSiz = 0> 
class deque {
    ...
public:                         // Basic types
  deque() : start(), finish(), map(0), map_size(0){
    create_map_and_nodes(0);
  }  // 默認構造函數
  deque(const deque& x) : start(), finish(), map(0), map_size(0) {
    create_map_and_nodes(x.size());
    __STL_TRY {
      uninitialized_copy(x.begin(), x.end(), start);
    }
    __STL_UNWIND(destroy_map_and_nodes());
  }
    // 接受 n:初始化大小, value:初始化的值
  deque(size_type n, const value_type& value) : start(), finish(), map(0), map_size(0) {
    fill_initialize(n, value);
  }
  deque(int n, const value_type& value) : start(), finish(), map(0), map_size(0) {
    fill_initialize(n, value);
  } 
  deque(long n, const value_type& value) : start(), finish(), map(0), map_size(0){
    fill_initialize(n, value);
  }
  ...

下面我們來看一下 deque 的中控器是如何配置的。

void deque<T,Alloc,BufSize>::create_map_and_nodes(size_type_num_elements) {
  //需要節點數= (每個元素/每個緩衝區可容納的元素個數+1)
  //如果剛好整除，多配一個節點
  size_type num_nodes = num_elements / buffer_size() + 1;
  //一個 map 要管理幾個節點，最少 8 個，最多是需要節點數+2
  map_size = max(initial_map_size(), num_nodes + 2);
  map = map_allocator::allocate(map_size);
 // 計算出數組的頭前面留出來的位置保存並在nstart.
  map_pointer nstart = map + (map_size - num_nodes) / 2;
  map_pointer nfinish = nstart + num_nodes - 1;
  map_pointer cur;//指向所擁有的節點的最中央位置
  ...
}

注意了，看了源碼之後才知道：deque 的 begin 和 end 不是一開始就是指向 map 中控器裏開頭和結尾的，而是指向所擁有的節點的最中央位置。

這樣帶來的好處是可以使得頭尾兩邊擴充的可能性和一樣大，換句話來說，因爲 deque 是頭尾插入都是 O(1)， 所以 deque 在頭和尾都留有空間方便頭尾插入。

那麼，什麼時候 map 中控器 本身需要調整大小呢？觸發條件在於 reserve_map_at_back 和 reserve_map_at_front 這兩個函數來判斷，實際操作由 reallocate_map 來執行。

那 reallocate_map 又是如何操作的呢？這裏先留個懸念。

// 如果 map 尾端的節點備用空間不足，符合條件就配置一個新的map(配置更大的，拷貝原來的，釋放原來的)
void reserve_map_at_back (size_type nodes_to_add = 1) {
  if (nodes_to_add + 1 > map_size - (finish.node - map))
    reallocate_map(nodes_to_add, false);
}
// 如果 map 前端的節點備用空間不足，符合條件就配置一個新的map(配置更大的，拷貝原來的，釋放原來的)
void reserve_map_at_front (size_type nodes_to_add = 1) {
  if (nodes_to_add > start.node - map)
    reallocate_map(nodes_to_add, true);
}

deque 的插入元素和刪除元素

因爲 deque 的是能夠雙向操作，所以其 push 和 pop 操作都類似於 list 都可以直接有對應的操作，需要注意的是 list 是鏈表，並不會涉及到界線的判斷， 而 deque 是由數組來存儲的，就需要隨時對界線進行判斷。

push 實現

template <class T, class Alloc = alloc, size_t BufSiz = 0> 
class deque {
    ...
public:                         // push_* and pop_*
    // 對尾進行插入
    // 判斷函數是否達到了數組尾部. 沒有達到就直接進行插入
  void push_back(const value_type& t) {
    if (finish.cur != finish.last - 1) {
      construct(finish.cur, t);
      ++finish.cur;
    }
    else
      push_back_aux(t);
  }
    // 對頭進行插入
    // 判斷函數是否達到了數組頭部. 沒有達到就直接進行插入
  void push_front(const value_type& t) {
    if (start.cur != start.first) {
      construct(start.cur - 1, t);
      --start.cur;
    }
    else
      push_front_aux(t);
  }
    ...
};

pop 實現

template <class T, class Alloc = alloc, size_t BufSiz = 0> 
class deque {
    ...
public: 
    // 對尾部進行操作
    // 判斷是否達到數組的頭部. 沒有到達就直接釋放
    void pop_back() {
    if (finish.cur != finish.first) {
      --finish.cur;
      destroy(finish.cur);
    }
    else
      pop_back_aux();
  }
    // 對頭部進行操作
    // 判斷是否達到數組的尾部. 沒有到達就直接釋放
  void pop_front() {
    if (start.cur != start.last - 1) {
      destroy(start.cur);
      ++start.cur;
    }
    else 
      pop_front_aux();
  }
    ...
};

pop 和 push 都先調用了 reserve_map_at_XX 函數，這些函數主要是爲了判斷前後空間是否足夠。

刪除操作

不知道還記得，最開始構造函數調用 create_map_and_nodes 函數，考慮到 deque 實現前後插入時間複雜度爲 O(1)，保證了在前後留出了空間，所以 push 和 pop 都可以在前面的數組進行操作。

現在就來看 erase，因爲 deque 是由數組構成，所以地址空間是連續的，刪除也就像 vector 一樣，要移動所有的元素。

deque 爲了保證效率儘可能的高，就判斷刪除的位置是中間偏後還是中間偏前來進行移動。

template <class T, class Alloc = alloc, size_t BufSiz = 0> 
class deque {
    ...
public:                         // erase
  iterator erase(iterator pos) {
    iterator next = pos;
    ++next;
    difference_type index = pos - start;
      // 刪除的地方是中間偏前, 移動前面的元素
    if (index < (size() >> 1)) {
      copy_backward(start, pos, next);
      pop_front();
    }
      // 刪除的地方是中間偏後, 移動後面的元素
    else {
      copy(next, finish, pos);
      pop_back();
    }
    return start + index;
  }
 // 範圍刪除, 實際也是調用上面的erase函數.
  iterator erase(iterator first, iterator last);
  void clear(); 
    ...
};

最後講一下 insert 函數

deque 源碼的基本每一個 insert 重載函數都會調用了 insert_auto 判斷插入的位置離頭還是尾比較近。

如果離頭進：則先將頭往前移動，調整將要移動的距離，用 copy 進行調整。

如果離尾近：則將尾往前移動，調整將要移動的距離，用 copy 進行調整。

注意 : push_back 是先執行構造在移動 node，而 push_front 是先移動 node 在進行構造，實現的差異主要是 finish 是指向最後一個元素的後一個地址而 first 指 向的就只第一個元素的地址，下面 pop 也是一樣的。

deque 源碼裏還有一些其它的成員函數，限於篇幅，這裏就不貼出來了，簡單的過一遍

**reallocate_map：**判斷中控器的容量是否夠用，如果不夠用，申請更大的空間，拷貝元素過去，修改 map 和 start，finish 的指向。

**fill_initialize 函數：**申請空間，對每個空間進行初始化，最後一個數組單獨處理。畢竟最後一個數組一般不是會全部填充滿。

**clear 函數：**刪除所有元素，分兩步執行：

首先從第二個數組開始到倒數第二個數組一次性全部刪除，這樣做是考慮到中間的數組肯定都是滿的，前後兩個數組就不一定是填充滿的，最後刪除前後兩個數組的元素。

**deque 的 swap 操作：**只是交換了 start, finish, map，並沒有交換所有的元素。

resize 函數： 重新將 deque 進行調整, 實現與 list 一樣的。

析構函數： 分步釋放內存。

deque 總結

deque 其實是在功能上合併了 vector 和 list。

優點：

1、隨機訪問方便，即支持 [] 操作符和 vector.at()；

2、在內部方便的進行插入和刪除操作；

3、可在兩端進行 push、pop

缺點：因爲涉及比較複雜，採用分段連續空間，所以佔用內存相對多。

使用區別：

1、如果你需要高效的隨即存取，而不在乎插入和刪除的效率，使用 vector。

2、如果你需要大量的插入和刪除，而不關心隨機存取，則應使用 list。

3、如果你需要隨機存取，而且關心兩端數據的插入和刪除，則應使用 deque 。

棧和隊列

以 deque 爲底層容器的適配器

最後要介紹的三種常用的數據結構，準確來說其實是一種適配器，底層都是已其它容器爲基準。

**棧 - stack：**先入後出，只允許在棧頂添加和刪除元素，稱爲出棧和入棧。

**隊列 - queue：**先入先出，在隊首取元素，在隊尾添加元素，稱爲出隊和入隊。

**優先隊列 - priority_queue：**帶權值的隊列。

常見棧的應用場景包括括號問題的求解，表達式的轉換和求值，函數調用和遞歸實現，深度優先遍歷 DFS 等；

常見的隊列的應用場景包括計算機系統中各種資源的管理，消息緩衝隊列的管理和廣度優先遍歷 BFS 等。

翻一下源碼，就知道 stack 和 queue 的底層其實就是使用 deque，用 deque 爲底層容器封裝。

stack 的源碼：

#ifndef __STL_LIMITED_DEFAULT_TEMPLATES
template <class T, class Sequence = deque<T> >
#else
template <class T, class Sequence>
#endif
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;

queue 的源碼：

#ifndef __STL_LIMITED_DEFAULT_TEMPLATES
template <class T, class Sequence = deque<T> >
#else
template <class T, class Sequence>
#endif
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;

heap 堆

最後我們來看一下，heap ，heap 並不是一個容器，所以他沒有實現自己的迭代器，也就沒有遍歷操作，它只是一種算法。

push_heap 插入元素

插入函數是 push_heap， heap 只接受 RandomAccessIterator 類型的迭代器。

template <class RandomAccessIterator>
inline void push_heap(RandomAccessIterator first, RandomAccessIterator last) {
  __push_heap_aux(first, last, distance_type(first), value_type(first));
}

template <class RandomAccessIterator, class Distance, class T>
inline void __push_heap_aux(RandomAccessIterator first, RandomAccessIterator last, Distance*, T*) {
    // 這裏傳入的是兩個迭代器的長度, 0, 還有最後一個數據
  __push_heap(first, Distance((last - first) - 1), Distance(0),  T(*(last - 1)));
}

pop_heap 刪除元素

pop 操作其實並沒有真正意義去刪除數據，而是將數據放在最後，只是沒有指向最後的元素而已，這裏使用 arrary 也可以，畢竟沒有對數組的大小進行調整。

 pop 的實現有兩種，這裏都羅列了出來，另一個傳入的是 cmp 仿函數。

template <class RandomAccessIterator, class Compare>
inline void pop_heap(RandomAccessIterator first, RandomAccessIterator last,
                     Compare comp) {
    __pop_heap_aux(first, last, value_type(first), comp);
}
template <class RandomAccessIterator, class T, class Compare>
inline void __pop_heap_aux(RandomAccessIterator first,
                           RandomAccessIterator last, T*, Compare comp) {
  __pop_heap(first, last - 1, last - 1, T(*(last - 1)), comp,
             distance_type(first));
}
template <class RandomAccessIterator, class T, class Compare, class Distance>
inline void __pop_heap(RandomAccessIterator first, RandomAccessIterator last,
                       RandomAccessIterator result, T value, Compare comp,
                       Distance*) {
  *result = *first;
  __adjust_heap(first, Distance(0), Distance(last - first), value, comp);
}
template <class RandomAccessIterator, class T, class Distance>
inline void __pop_heap(RandomAccessIterator first, RandomAccessIterator last,
                       RandomAccessIterator result, T value, Distance*) {
  *result = *first; // 因爲這裏是大根堆, 所以first的值就是最大值, 先將最大值保存.
  __adjust_heap(first, Distance(0), Distance(last - first), value);
}

make_heap 將數組變成堆存放

template <class RandomAccessIterator>
inline void make_heap(RandomAccessIterator first, RandomAccessIterator last) {
  __make_heap(first, last, value_type(first), distance_type(first));
}
template <class RandomAccessIterator, class T, class Distance>
void __make_heap(RandomAccessIterator first, RandomAccessIterator last, T*,
                 Distance*) {
  if (last - first < 2) return;
    // 計算長度, 並找出中間的根值
  Distance len = last - first;
  Distance parent = (len - 2)/2;
    
  while (true) {
      // 一個個進行調整, 放到後面
    __adjust_heap(first, parent, len, T(*(first + parent)));
    if (parent == 0) return;
    parent--;
  }
}

sort_heap 實現堆排序

其實就是每次將第一位數據彈出從而實現排序功。

template <class RandomAccessIterator>
void sort_heap(RandomAccessIterator first, RandomAccessIterator last) {
  while (last - first > 1) pop_heap(first, last--);
}
template <class RandomAccessIterator, class Compare>
void sort_heap(RandomAccessIterator first, RandomAccessIterator last,
               Compare comp) {
  while (last - first > 1) pop_heap(first, last--, comp);
}

priority_queue 優先隊列

最後我們來看一下 priority_queue。

上一節分析 heap 其實就是爲 priority_queue 做準備，priority_queue 是一個優先級隊列，是帶權值的， 支持插入和刪除操作，其只能從尾部插入，頭部刪除， 並且其順序也並非是根據加入的順序排列的。

priority_queue 因爲也是隊列的一種體現， 所以也就跟隊列一樣不能直接的遍歷數組，也就沒有迭代器。

priority_queue 本身也不算是一個容器，它是以 vector 爲容器以 heap 爲數據操作的配置器。

類型定義

#ifndef __STL_LIMITED_DEFAULT_TEMPLATES
template <class T, class Sequence = vector<T>, 
          class Compare = less<typename Sequence::value_type> >
#else
template <class T, class Sequence, class Compare>
#endif
class  priority_queue {
public:
 // 符合traits編程規範
  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; // 定義vector容器的對象
  Compare comp; // 定義比較函數(僞函數)
  ...
};

屬性獲取

priority_queue 只有簡單的 3 個屬性獲取的函數, 其本身的操作也很簡單, 只是實現依賴了 vector 和 heap 就變得比較複雜。

class  priority_queue {
 ...
public:
  bool empty() const { return c.empty(); }
  size_type size() const { return c.size(); }
  const_reference top() const { return c.front(); }
    ...
};

push 和 pop 實現

push 和 pop 具體都是採用的 heap 算法。

priority_queue 本身實現是很複雜的，但是當我們已經瞭解過 vector，heap 之後再來看，它其實就簡單了。

就是將 vector 作爲容器， heap 作爲算法來操作的配置器，這也體現了 STL 的靈活性： 通過各個容器與算法的結合就能實現另一種功能。

最後，來自實踐生產環境的一個體會：上面所列的所有容器的一個原則：爲了避免拷貝開銷，不要直接把大的對象直接往裏塞，而是使用指針。

參考

1、《STL 源碼剖析》

2、https://github.com/FunctionDou/STL

本文由 Readfog 進行 AMP 轉碼，版權歸原作者所有。
來源：https://mp.weixin.qq.com/s/zU9YuKWtGyXjBqBp5ihaNA