目錄

1. 深度探索 deque

2. 淺談 queue & stack

3. 淺談 RB-tree（紅黑樹）

4. 淺談 set/multiset

5. 淺談 map/multimap

6. 淺談 hashtable

7. hash_set/hash_multiset, hash_map/hash_multimap 概念

8. unordered 容器概念

1. 深度探索 deque

1.1 deque 概述

vector 是單向開口的連續(xù)線性空間，deque 則是一種雙向開口的連續(xù)線性空間先蒋，可以在頭尾兩端分別做元素的插入和刪除操作，如圖所示：

deque 和 vector 的最大差異，一在于 deque 允許于常數(shù)時(shí)間內(nèi)對頭端進(jìn)行元素的插入或移除操作岂傲，二在于 deque 沒有所謂容量（capacity）觀念碍粥，因?yàn)樗莿?dòng)態(tài)地以分段連續(xù)空間組合而成壤短，隨時(shí)可以增加一段新的空間并鏈接起來。換句話說蛮瞄，像 vector 那樣「因舊空間不足而重新配置一塊更大空間，然后復(fù)制元素谆扎，再釋放舊空間」這樣的事情在 deque 是不會(huì)發(fā)生的挂捅。也因此，deque 沒有必要提供所謂的空間保留（reserve）功能堂湖。

雖然 deque 也提供 Random Access Iterator闲先，但它的迭代器并不是普通指針，其復(fù)雜度和 vector 不可以道里計(jì)无蜂，這當(dāng)然影響了各個(gè)運(yùn)算層面伺糠。因此，除非必要斥季，我們應(yīng)盡可能選擇使用 vector 而非 deque训桶。

對 deque 進(jìn)行的排序操作，為了最高效率酣倾，可將 deque 先完整復(fù)制到一個(gè) vector 身上舵揭，將 vector 排序后（利用 STL sort 算法），再復(fù)制回 deque躁锡。

1.2 deque 的中控器

deque 是連續(xù)空間(至少邏輯上看來如此)午绳，連續(xù)線性空間總令我們聯(lián)想到
array 或 vectoro。array無法成長稚铣，vector 雖可成長箱叁，卻只能向尾端成長墅垮，而且其所謂成長原是個(gè)假象，事實(shí)上是（1）另覓更大空間耕漱；（2）將原數(shù)據(jù)復(fù)制過去算色；（3）釋放原空間三部曲。如果不是 vector 每次配置新空間時(shí)都有留下一些余裕螟够，其「成長」假象所帶來的代價(jià)將是相當(dāng)高昂灾梦。

deque 系由一段一段的定量連續(xù)空間構(gòu)成。一旦有必要在 deque 的前端或尾端增加新空間妓笙，便配置一段定量連續(xù)空間若河，串接在整個(gè) deque 的頭端或尾端。deque 的最大任務(wù)寞宫，便是在這些分段的定量連續(xù)空間上萧福，維護(hù)其整體連續(xù)的假象，并提供隨機(jī)存取的界而辈赋。避開了「重新配置鲫忍、復(fù)制、釋放」的輪回钥屈，代價(jià)則是復(fù)雜的迭代器架構(gòu)悟民。

受到分段連續(xù)線性空間的字面影響，我們可能以為 deque 的實(shí)現(xiàn)復(fù)雜度和
vector 相比雖不中亦不遠(yuǎn)矣篷就，其實(shí)不然射亏。主要因?yàn)椋仍环侄芜B續(xù)線性空間竭业，就必須有中央控制智润，而為了維持整體連續(xù)的假象，數(shù)據(jù)結(jié)構(gòu)的設(shè)計(jì)及迭代器前進(jìn)后退等動(dòng)作都頗為繁瑣永品。deque 的實(shí)現(xiàn)代碼份量遠(yuǎn)比 vector 或
list 都多得多做鹰。

deque 采用一塊所謂的 map （注意，不是 STL 的 map 容器）作為主控鼎姐。這里所謂 map 是一小塊連續(xù)空間钾麸，其中每個(gè)元素（此處稱為一個(gè)節(jié)點(diǎn)，node）都是指針炕桨，指向另一段（較大的）連續(xù)線性空間饭尝，稱為緩沖區(qū)。緩沖區(qū)才是 deque 的儲(chǔ)存空間主體献宫。GNU 2.9 中允許我們指定緩沖區(qū)大小钥平，默認(rèn)值 0 表示將使用 512 bytes 緩沖區(qū)。

template <class T, calss Alloc = alloc, size_t BufSiz = 0>
calss deque {
public:             // Basic types
  typedef T value_type;
  typedef value_type* pointer;
  typedef _deque_iterator<T, T&, T*, BufSiz> iterator;
  ...
protected:          // Internal typedefs
  // 元素的指針的指針 (pointer of pointer of T)
  typedef pointer* map_pointer;    // T**
protected:          // Data members
  iterator start;
  iterator finish;
  map_pointer map;    // 指向 map姊途，map 是塊連續(xù)空間涉瘾，其內(nèi)的每個(gè)元素
                      // 都是一個(gè)指針（稱為節(jié)點(diǎn)）知态，指向一塊緩沖區(qū)
  size_type map_size; // map 內(nèi)可容納多少指針
public:
  iterator begin() { return start; }
  iterator end() { return finish; }
  size_type size() const { return finish - start; }
...
};

通過源代碼我們可以發(fā)現(xiàn)，其實(shí) map 是一個(gè) T**立叛，也就是說它是一個(gè)指針负敏，所指之物又是一個(gè)指針，指向型別為 T 的一塊空間秘蛇，如下圖所示：

deque 的結(jié)構(gòu)設(shè)計(jì)中其做，map 和 node-buffer（節(jié)點(diǎn)-緩沖區(qū)）的關(guān)系

1.3 deque 的迭代器

deque 是分段連續(xù)空間。維持其「整體連續(xù)」假象的任務(wù)赁还，落在了迭代器的 operator++ 和 operator-- 兩個(gè)運(yùn)算子身上妖泄。

讓我們思考一下，deque 迭代器應(yīng)該具備什么結(jié)構(gòu)：首先艘策，它必須能夠指出分段連續(xù)空間（意即緩沖區(qū)）在哪里蹈胡；其次，它必須能夠判斷自己是否已經(jīng)處于其所在緩沖區(qū)的邊緣朋蔫，如果是审残，一旦前進(jìn)或后退時(shí)就必須跳躍至下一個(gè)或上一個(gè)緩沖區(qū)。為了能夠正確跳躍斑举，deuqe 必須隨時(shí)掌握管控中心（map），所以有了如下實(shí)現(xiàn)方式：

下圖所示是 deque 的中控器病涨、緩沖區(qū)富玷、迭代器的相互關(guān)系：

image.png

假設(shè)我們產(chǎn)生一個(gè)元素型態(tài)為 int，緩沖區(qū)大小為 8（個(gè)元素）的 deque（語法形式為 deque<int, alloc, 8>）經(jīng)過某些操作后既穆，deque 擁有 20 個(gè)元素赎懦，那么其 begin() 和 end() 所傳回的兩個(gè)迭代器應(yīng)該如下圖所示。這兩個(gè)迭代器事實(shí)上一直保持在 deque 內(nèi)幻工，名為 start 和 finish励两。

image.png

20 個(gè)元素需要 20/8 = 3 個(gè)緩沖區(qū)，所以 map 之內(nèi)運(yùn)用了三個(gè)節(jié)點(diǎn)囊颅。迭代器 start 內(nèi)的 cur 指針當(dāng)然指向緩沖區(qū)的第一個(gè)元素当悔，迭代器 finish 內(nèi)的 cur 指向緩沖區(qū)的最后元素（的下一位置）。

注意：最后一個(gè)緩沖區(qū)尚有備用空間踢代。稍后如果有新元素要插入于尾端盲憎，可直接拿此備用空間來使用。

deque 迭代器對各種指針運(yùn)算都進(jìn)行了重載操作胳挎，所以各種指針運(yùn)算如加饼疙、減、前進(jìn)慕爬、后退窑眯、都不能直觀視之屏积。其中最關(guān)鍵的就是：一旦行進(jìn)時(shí)遇到緩沖區(qū)邊緣，要特別當(dāng)心磅甩，視前進(jìn)或后退而定炊林，可能需要調(diào)用 set_node() 跳一個(gè)緩沖區(qū):

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());
  }
// 以下各個(gè)重載運(yùn)算子是 __deque_iterator<> 成功運(yùn)作的關(guān)鍵。
  reference operator*() const { return *_M_cur; }
#ifndef __SGI_STL_NO_ARROW_OPERATOR
  pointer operator->() const { return _M_cur; }
#endif /* __SGI_STL_NO_ARROW_OPERATOR */

  difference_type operator-(const _Self& __x) const {
    return difference_type(_S_buffer_size()) * (_M_node - __x._M_node - 1) +
      (_M_cur - _M_first) + (__x._M_last - __x._M_cur);
  }

  // 參考 More Effective C++更胖，item6
  _Self& operator++() {
    ++_M_cur;                     // 切換至下一個(gè)元素
    if (_M_cur == _M_last) {      // 如果已經(jīng)達(dá)到所在緩沖區(qū)的尾端
      _M_set_node(_M_node + 1);   // 就切換至下一節(jié)點(diǎn)（亦即緩沖區(qū)）的第一個(gè)元素
      _M_cur = _M_first;   
    }
    return *this; 
  }
  _Self operator++(int)  {        // 后置式铛铁，標(biāo)準(zhǔn)寫法
    _Self __tmp = *this;
    ++*this;
    return __tmp;
  }

  _Self& operator--() {           
    if (_M_cur == _M_first) {     // 如果已達(dá)到所在緩沖區(qū)的頭端
      _M_set_node(_M_node - 1);   // 就切換到前一節(jié)點(diǎn)（亦即緩沖區(qū)）的最后一個(gè)位置（的下一個(gè)位置）
      _M_cur = _M_last;
    }
    --_M_cur;                     // 切換至前一個(gè)元素
    return *this;
  }
  _Self operator--(int) {         // 后置式，標(biāo)準(zhǔn)寫法
    _Self __tmp = *this;
    --*this;
    return __tmp;
  }
  // 以下實(shí)現(xiàn)隨機(jī)存取却妨。迭代器可以直接跳躍 n 個(gè)距離
  _Self& operator+=(difference_type __n)
  {
    difference_type __offset = __n + (_M_cur - _M_first);
    if (__offset >= 0 && __offset < difference_type(_S_buffer_size()))
      _M_cur += __n;    // 目標(biāo)位置在同一緩沖區(qū)內(nèi)
    else {              // 目標(biāo)位置不在同一緩沖區(qū)內(nèi)
      difference_type __node_offset =
        __offset > 0 ? __offset / difference_type(_S_buffer_size())
                   : -difference_type((-__offset - 1) / _S_buffer_size()) - 1;
      _M_set_node(_M_node + __node_offset);    // 切換至正確的節(jié)點(diǎn)（亦即緩沖區(qū)）
      _M_cur = _M_first +                      // 切換至正確的元素
        (__offset - __node_offset * difference_type(_S_buffer_size()));
    }
    return *this;
  }

  // 參考 More Effective C++ 饵逐，item 22
  _Self operator+(difference_type __n) const
  {
    _Self __tmp = *this;
    return __tmp += __n;        // 調(diào)用operator+=
  }
  // 將n變?yōu)?n就可以使用operator+=()函數(shù)實(shí)現(xiàn)operator-=()操作
  _Self& operator-=(difference_type __n) { return *this += -__n; }

  _Self operator-(difference_type __n) const {
    _Self __tmp = *this;
    return __tmp -= __n;        // 調(diào)用operator-=
  }

  //　以下實(shí)現(xiàn)隨機(jī)存取。迭代器可以直接跳躍ｎ個(gè)距離
  reference operator[](difference_type __n) const { return *(*this + __n); }　　　// 調(diào)用operator*, operator+

  bool operator==(const _Self& __x) const { return _M_cur == __x._M_cur; }
  bool operator!=(const _Self& __x) const { return !(*this == __x); }
  bool operator<(const _Self& __x) const {
    return (_M_node == __x._M_node) ? 
      (_M_cur < __x._M_cur) : (_M_node < __x._M_node);
  }
  bool operator>(const _Self& __x) const  { return __x < *this; }
  bool operator<=(const _Self& __x) const { return !(__x < *this); }
  bool operator>=(const _Self& __x) const { return !(*this < __x); }

More Effective C++彪标，item6：注意區(qū)分遞增（increment）和遞減（decrement）運(yùn)算符的前置（prefix）和后置（postfix）形式的區(qū)別：

• 后綴式有一個(gè)int類型參數(shù)倍权，當(dāng)函數(shù)被調(diào)用時(shí)，編譯器傳遞一個(gè)0作為int參數(shù)的值傳遞給該函數(shù)可以在定義時(shí)省略掉不想使用的參數(shù)名稱捞烟，以避免警告信息
• 后綴式返回const對象薄声，原因是 ：使該類的行為和int一致，而int不允許連續(xù)兩次自增后綴運(yùn)算题画；連續(xù)兩次運(yùn)算實(shí)際只增一次默辨，和直覺不符
• 前綴比后綴效率更高，因?yàn)楹缶Y要返回對象苍息，而前綴只返回引用另外缩幸，可以用前綴來實(shí)現(xiàn)后綴，以方便維護(hù)

More Effective C++竞思，item22：考慮使用運(yùn)算符的賦值形式來取代其單獨(dú)形式：

運(yùn)算符的賦值形式不需要產(chǎn)生臨時(shí)對象表谊，因此應(yīng)該盡量使用，對運(yùn)算符的單獨(dú)形式的最佳實(shí)現(xiàn)方法是 return Rational (lhs) += rhs; 這種形式盖喷，將返回值優(yōu)化和運(yùn)算符的賦值形式結(jié)合起來爆办，即高效，又方便

1.4 deque 的數(shù)據(jù)結(jié)構(gòu)

deque 除了維護(hù)一個(gè)先前說過的指向 map 的指針外课梳，也維護(hù) start距辆，finish 兩個(gè)迭代器，此外暮刃，它還必須記住當(dāng)前的 map 大小挑格。

template <class T, class Alloc = alloc, size_t BufSiz = 0> 
class deque {
public:                         // Basic types
  typedef T value_type;
  typedef value_type* pointer;
  typedef value_type& reference;
  typedef size_t size_type;
  
public:                         // Iterators
  typedef __deque_iterator<T, T&, T*, BufSiz>              iterator;
    
protected:                      // Internal typedefs
  // 元素的指針的指針（pointer of pointer of T）
  typedef pointer* map_pointer;    
  
protected:                      // Data members
  iterator start;     // 表現(xiàn)第一個(gè)節(jié)點(diǎn)
  iterator finish;    // 表現(xiàn)最后一個(gè)節(jié)點(diǎn)
  
  map_pointer map;    // 指向map，map是塊連續(xù)空間沾歪，
                      // 其每個(gè)元素都是個(gè)指針漂彤，指向一個(gè)節(jié)點(diǎn)（緩沖區(qū)）
  size_type map_size; // map 內(nèi)有多少指針
...
}

有了上述結(jié)構(gòu)，以下數(shù)個(gè)機(jī)能便可輕易完成：

public:                         // Basic accessors
  iterator begin() { return start; }
  iterator end() { return finish; }

  reference operator[](size_type n) {
    return start[difference_type(n)]; // 調(diào)用 __deque_iterator<>::operator[]
  }

  reference front() { return *start; } // 調(diào)用 __deque_iterator<>::operator*
  reference back() {
    iterator tmp = finish;    
    --tmp;    // 調(diào)用 __deque_iterator<>::operator--
    return *tmp;     // 調(diào)用 __deque_iterator<>::operator*
    // 以上三行何不改為：return *(finish-1);
    // 因?yàn)?__deque_iterator<> 沒有為 (finish-1) 定義運(yùn)算子？４焱（存疑）
  }

  // 下行最后有兩個(gè) ‘;’立润，雖奇怪但合乎語法
  size_type size() const { return finish - start;; } 
  // 以上調(diào)用iterator::operator-
  size_type max_size() const { return size_type(-1); }
  bool empty() const { return finish == start; }

2. 淺談 queue & stack

在 GNU 2.9 中，queue 和 stack 一個(gè)是「先進(jìn)先出」媳板，一個(gè)是「先進(jìn)后出」桑腮，都以 deque 作為缺省情況下的底層結(jié)構(gòu)，它們可以算作 deque 的特化蛉幸，只需將 deque 中的不需要的功能「閹割」即可破讨，這里就不展開再分析了，貼出示意圖：

3. 淺談 RB-tree（紅黑樹）

Red-Black tree（紅黑樹）是一個(gè)頗具歷史并被廣泛運(yùn)用的平衡二叉搜索樹（balanced binary search tree）奕纫。平衡二叉搜索樹的特征：排列規(guī)則有利 search 和 insert提陶，并保持適度平衡——無任何節(jié)點(diǎn)過深。除此之外匹层，紅黑樹還必須滿足以下規(guī)則：

1. 每個(gè)節(jié)點(diǎn)不是紅色就是黑色
2. 根節(jié)點(diǎn)為黑色
3. 如果節(jié)點(diǎn)為紅隙笆，其子節(jié)點(diǎn)必須為黑
4. 任一節(jié)點(diǎn)至 NULL（樹尾端）的任何路徑，所含之黑節(jié)點(diǎn)數(shù)必須相同

4. 淺談 set/multiset

因?yàn)椴荒芨淖?set 的元素值升筏，為了杜絕寫入操作撑柔，set iterators 是一種 constant iterators（相對于 mutable iterators）。

multiset 的特性以及用法和 set 完全相同您访，唯一的差別在于它允許鍵值重復(fù)铅忿。

5. 淺談 map/multimap

map 的所以元素都是 pair，同時(shí)擁有實(shí)值（value）和鍵值（key）灵汪。pair 的第一元素被視為鍵值辆沦，第二元素被視為實(shí)值。map 不允許兩個(gè)元素?fù)碛邢嗤逆I值识虚。

map 元素鍵值不能被改變，但是實(shí)值可以妒茬，因此 map iterators 既不是一種 constant iterators 也不是一種 mutable iterators担锤。

map 的 [] 操作符允許進(jìn)行插入操作：其中內(nèi)含的函數(shù) lower_bound 會(huì)返回「不破壞排序得以安插 value 的第一個(gè)適當(dāng)位置」，然后再調(diào)用插入函數(shù)將需要的 value 插入乍钻。
multimap 因?yàn)?key 會(huì)重復(fù)肛循，不允許使用 [] 做 insertion。

multimap 與 map 差別也只有其允許鍵值重復(fù)银择。

6. 淺談 hashtable

這種數(shù)據(jù)結(jié)構(gòu)在插入多糠、刪除、搜尋等操作上也具有「常數(shù)平均時(shí)間」的表現(xiàn)浩考，而且這種表現(xiàn)是以統(tǒng)計(jì)為基礎(chǔ)夹孔，不需仰賴輸入元素的隨機(jī)性。也稱散列表、哈希表搭伤。

M個(gè)空間（M < N）則第 H 個(gè)元素放在 H % M（取余）的位置上只怎。

hashtable 可提供對任何有名項(xiàng)（named item）的存取操作和刪除操作，也可被視為一種字典結(jié)構(gòu)（dictionary）怜俐。

7. hash_set/hash_multiset, hash_map/hash_multimap 概念

雖然 STL 只規(guī)范復(fù)雜度與接口身堡，并不規(guī)范實(shí)現(xiàn)方法，但 STL set 多半以 RB-tree 為底層機(jī)制拍鲤。SGI 則是在 STL 標(biāo)準(zhǔn)規(guī)格之外又提供了一個(gè)所謂的 hash 系列贴谎，以 hashtable 為底層機(jī)制。

RB-tree 有自動(dòng)排序功能而 hashtable 沒有季稳，因此 set 的元素有自動(dòng)排序功能而 hash_set 沒有擅这。其他幾種結(jié)構(gòu)也完全如此，不再贅述绞幌。

8. unordered 容器概念

就是把之前的 hash 系列重新「包裝」了一下蕾哟，不再贅述。

部分內(nèi)容參考自《STL 源碼剖析》以及網(wǎng)絡(luò)