目录

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 是单向开口的连续线性空间，deque 则是一种双向开口的连续线性空间，可以在头尾两端分别做元素的插入和删除操作，如图所示：

deque 和 vector 的最大差异，一在于 deque 允许于常数时间内对头端进行元素的插入或移除操作，二在于 deque 没有所谓容量（capacity）观念，因为它是动态地以分段连续空间组合而成，随时可以增加一段新的空间并链接起来。换句话说，像 vector 那样「因旧空间不足而重新配置一块更大空间，然后复制元素，再释放旧空间」这样的事情在 deque 是不会发生的。也因此，deque 没有必要提供所谓的空间保留（reserve）功能。

虽然 deque 也提供 Random Access Iterator，但它的迭代器并不是普通指针，其复杂度和 vector 不可以道里计，这当然影响了各个运算层面。因此，除非必要，我们应尽可能选择使用 vector 而非 deque。

对 deque 进行的排序操作，为了最高效率，可将 deque 先完整复制到一个 vector 身上，将 vector 排序后（利用 STL sort 算法），再复制回 deque。

1.2 deque 的中控器

deque 是连续空间(至少逻辑上看来如此)，连续线性空间总令我们联想到
array 或 vectoro。array无法成长，vector 虽可成长，却只能向尾端成长，而且其所谓成长原是个假象，事实上是（1）另觅更大空间；（2）将原数据复制过去；（3）释放原空间三部曲。如果不是 vector 每次配置新空间时都有留下一些余裕，其「成长」假象所带来的代价将是相当高昂。

deque 系由一段一段的定量连续空间构成。一旦有必要在 deque 的前端或尾端增加新空间，便配置一段定量连续空间，串接在整个 deque 的头端或尾端。deque 的最大任务，便是在这些分段的定量连续空间上，维护其整体连续的假象，并提供随机存取的界而。避开了「重新配置、复制、释放」的轮回，代价则是复杂的迭代器架构。

受到分段连续线性空间的字面影响，我们可能以为 deque 的实现复杂度和
vector 相比虽不中亦不远矣，其实不然。主要因为，既曰分段连续线性空间，就必须有中央控制，而为了维持整体连续的假象，数据结构的设计及迭代器前进后退等动作都颇为繁琐。deque 的实现代码份量远比 vector 或
list 都多得多。

deque 采用一块所谓的 map （注意，不是 STL 的 map 容器）作为主控。这里所谓 map 是一小块连续空间，其中每个元素（此处称为一个节点，node）都是指针，指向另一段（较大的）连续线性空间，称为缓冲区。缓冲区才是 deque 的储存空间主体。GNU 2.9 中允许我们指定缓冲区大小，默认值 0 表示将使用 512 bytes 缓冲区。

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 是块连续空间，其内的每个元素
                      // 都是一个指针（称为节点），指向一块缓冲区
  size_type map_size; // map 内可容纳多少指针
public:
  iterator begin() { return start; }
  iterator end() { return finish; }
  size_type size() const { return finish - start; }
...
};

通过源代码我们可以发现，其实 map 是一个 T**，也就是说它是一个指针，所指之物又是一个指针，指向型别为 T 的一块空间，如下图所示：

deque 的结构设计中，map 和 node-buffer（节点-缓冲区）的关系

1.3 deque 的迭代器

deque 是分段连续空间。维持其「整体连续」假象的任务，落在了迭代器的 operator++ 和 operator-- 两个运算子身上。

让我们思考一下，deque 迭代器应该具备什么结构：首先，它必须能够指出分段连续空间（意即缓冲区）在哪里；其次，它必须能够判断自己是否已经处于其所在缓冲区的边缘，如果是，一旦前进或后退时就必须跳跃至下一个或上一个缓冲区。为了能够正确跳跃，deuqe 必须随时掌握管控中心（map），所以有了如下实现方式：

下图所示是 deque 的中控器、缓冲区、迭代器的相互关系：

image.png

假设我们产生一个元素型态为 int，缓冲区大小为 8（个元素）的 deque（语法形式为 deque<int, alloc, 8>）经过某些操作后，deque 拥有 20 个元素，那么其 begin() 和 end() 所传回的两个迭代器应该如下图所示。这两个迭代器事实上一直保持在 deque 内，名为 start 和 finish。

image.png

20 个元素需要 20/8 = 3 个缓冲区，所以 map 之内运用了三个节点。迭代器 start 内的 cur 指针当然指向缓冲区的第一个元素，迭代器 finish 内的 cur 指向缓冲区的最后元素（的下一位置）。

注意：最后一个缓冲区尚有备用空间。稍后如果有新元素要插入于尾端，可直接拿此备用空间来使用。

deque 迭代器对各种指针运算都进行了重载操作，所以各种指针运算如加、减、前进、后退、都不能直观视之。其中最关键的就是：一旦行进时遇到缓冲区边缘，要特别当心，视前进或后退而定，可能需要调用 set_node() 跳一个缓冲区:

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());
  }
// 以下各个重载运算子是 __deque_iterator<> 成功运作的关键。
  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;                     // 切换至下一个元素
    if (_M_cur == _M_last) {      // 如果已经达到所在缓冲区的尾端
      _M_set_node(_M_node + 1);   // 就切换至下一节点（亦即缓冲区）的第一个元素
      _M_cur = _M_first;   
    }
    return *this; 
  }
  _Self operator++(int)  {        // 后置式，标准写法
    _Self __tmp = *this;
    ++*this;
    return __tmp;
  }

  _Self& operator--() {           
    if (_M_cur == _M_first) {     // 如果已达到所在缓冲区的头端
      _M_set_node(_M_node - 1);   // 就切换到前一节点（亦即缓冲区）的最后一个位置（的下一个位置）
      _M_cur = _M_last;
    }
    --_M_cur;                     // 切换至前一个元素
    return *this;
  }
  _Self operator--(int) {         // 后置式，标准写法
    _Self __tmp = *this;
    --*this;
    return __tmp;
  }
  // 以下实现随机存取。迭代器可以直接跳跃 n 个距离
  _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;    // 目标位置在同一缓冲区内
    else {              // 目标位置不在同一缓冲区内
      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);    // 切换至正确的节点（亦即缓冲区）
      _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;        // 调用operator+=
  }
  // 将n变为-n就可以使用operator+=()函数实现operator-=()操作
  _Self& operator-=(difference_type __n) { return *this += -__n; }

  _Self operator-(difference_type __n) const {
    _Self __tmp = *this;
    return __tmp -= __n;        // 调用operator-=
  }

  //　以下实现随机存取。迭代器可以直接跳跃ｎ个距离
  reference operator[](difference_type __n) const { return *(*this + __n); }　　　// 调用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：注意区分递增（increment）和递减（decrement）运算符的前置（prefix）和后置（postfix）形式的区别：

• 后缀式有一个int类型参数，当函数被调用时，编译器传递一个0作为int参数的值传递给该函数可以在定义时省略掉不想使用的参数名称，以避免警告信息
• 后缀式返回const对象，原因是 ：使该类的行为和int一致，而int不允许连续两次自增后缀运算；连续两次运算实际只增一次，和直觉不符
• 前缀比后缀效率更高，因为后缀要返回对象，而前缀只返回引用另外，可以用前缀来实现后缀，以方便维护

More Effective C++，item22：考虑使用运算符的赋值形式来取代其单独形式：

运算符的赋值形式不需要产生临时对象，因此应该尽量使用，对运算符的单独形式的最佳实现方法是 return Rational (lhs) += rhs; 这种形式，将返回值优化和运算符的赋值形式结合起来，即高效，又方便

1.4 deque 的数据结构

deque 除了维护一个先前说过的指向 map 的指针外，也维护 start，finish 两个迭代器，此外，它还必须记住当前的 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;     // 表现第一个节点
  iterator finish;    // 表现最后一个节点
  
  map_pointer map;    // 指向map，map是块连续空间，
                      // 其每个元素都是个指针，指向一个节点（缓冲区）
  size_type map_size; // map 內有多少指针
...
}

有了上述结构，以下数个机能便可轻易完成：

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

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

  reference front() { return *start; } // 调用 __deque_iterator<>::operator*
  reference back() {
    iterator tmp = finish;    
    --tmp;    // 调用 __deque_iterator<>::operator--
    return *tmp;     // 调用 __deque_iterator<>::operator*
    // 以上三行何不改为：return *(finish-1);
    // 因为 __deque_iterator<> 沒有为 (finish-1) 定义运算子？！（存疑）
  }

  // 下行最后有两个 ‘;’，虽奇怪但合乎语法
  size_type size() const { return finish - start;; } 
  // 以上调用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 一个是「先进先出」，一个是「先进后出」，都以 deque 作为缺省情况下的底层结构，它们可以算作 deque 的特化，只需将 deque 中的不需要的功能「阉割」即可，这里就不展开再分析了，贴出示意图：

3. 浅谈 RB-tree（红黑树）

Red-Black tree（红黑树）是一个颇具历史并被广泛运用的平衡二叉搜索树（balanced binary search tree）。平衡二叉搜索树的特征：排列规则有利 search 和 insert，并保持适度平衡——无任何节点过深。除此之外，红黑树还必须满足以下规则：

1. 每个节点不是红色就是黑色
2. 根节点为黑色
3. 如果节点为红，其子节点必须为黑
4. 任一节点至 NULL（树尾端）的任何路径，所含之黑节点数必须相同

4. 浅谈 set/multiset

因为不能改变 set 的元素值，为了杜绝写入操作，set iterators 是一种 constant iterators（相对于 mutable iterators）。

multiset 的特性以及用法和 set 完全相同，唯一的差别在于它允许键值重复。

5. 浅谈 map/multimap

map 的所以元素都是 pair，同时拥有实值（value）和键值（key）。pair 的第一元素被视为键值，第二元素被视为实值。map 不允许两个元素拥有相同的键值。

map 元素键值不能被改变，但是实值可以，因此 map iterators 既不是一种 constant iterators 也不是一种 mutable iterators。

map 的 [] 操作符允许进行插入操作：其中内含的函数 lower_bound 会返回「不破坏排序得以安插 value 的第一个适当位置」，然后再调用插入函数将需要的 value 插入。
multimap 因为 key 会重复，不允许使用 [] 做 insertion。

multimap 与 map 差别也只有其允许键值重复。

6. 浅谈 hashtable

这种数据结构在插入、删除、搜寻等操作上也具有「常数平均时间」的表现，而且这种表现是以统计为基础，不需仰赖输入元素的随机性。也称散列表、哈希表。

M个空间（M < N）则第 H 个元素放在 H % M（取余）的位置上。

hashtable 可提供对任何有名项（named item）的存取操作和删除操作，也可被视为一种字典结构（dictionary）。

7. hash_set/hash_multiset, hash_map/hash_multimap 概念

虽然 STL 只规范复杂度与接口，并不规范实现方法，但 STL set 多半以 RB-tree 为底层机制。SGI 则是在 STL 标准规格之外又提供了一个所谓的 hash 系列，以 hashtable 为底层机制。

RB-tree 有自动排序功能而 hashtable 没有，因此 set 的元素有自动排序功能而 hash_set 没有。其他几种结构也完全如此，不再赘述。

8. unordered 容器概念

就是把之前的 hash 系列重新「包装」了一下，不再赘述。

部分内容参考自《STL 源码剖析》以及网络