【STL】序列式容器

容器（Containers）是 STL 六大组件中最被人熟知和常用的一个神器，根据组织方式大概分为序列式容器和关联式容器两大类。

1 STL 容器概览

STL 提供的容器如下图：

其中内缩表达基层与衍生层的关系，这里所谓的衍生，并非派生 (inheritance) 关系，而是内含 (containment) 关系。例如 heap 内含一个 vector，priority_queue 内含一个 heap 、stack 和 queue 都含一个 deque，set/map/multiset/multimap 都内含一个 RB-tree，hast_x 都内含一个 hashtable。

2 序列式容器

所谓序列式容器，其中的元素都可序（ordered），但未必有序（sorted），C++ 本身内建了一个序列式容器array，STL 另外提供了vector、list、deque、stack、queue、priority-queue 等序列式容器。其中 stack 和 queue 由于只是 deque 改头换面而来，技术上被归为一种配接器 (adapter)。接下来了解各序列式容器的具体实现。

3 vector

vector 采用的数据结构非常简单：线性连续空间。它以两个迭代器 start 和 finish 分别指向配置得来的连续空间中目前已被使用的范围，并以迭代器 end_of_storage 指向整块连续空间（含备用空间）的尾端。

template <class T, class Alloc = alloc>
class vector {
    ...
protected:
    iterator start;             // 表示目前使用空间的头
    iterator finish;            // 表示目前使用空间的尾
    iterator end_of_storage;    // 表示目前可用空间的尾
    ...
};

为了降低空间配置时的速度成本， vector 实际配置的大小可能比客户端需求量更大一些，以备将来可能的扩充。这便是容量 (capacity) 的观念。换句话说，一个 vector 的容量永远大于或等于其大小。一旦容量等于大小，下次再有新增元素，整个 vector 就得进行动态增加容量。

所谓动态增加容量，并不是在原来空间之后接续新空间（因为无法保证原空间之后尚有可供分配的空间），而是以原来大小的的两倍另外分配一块较大空间，然后将原内容拷贝过来，然后才开始在原内容之后构造新元素，并释放原空间。因此，对vector的任何操作，一旦引起空间重新配置，指向原 vector 的所有迭代器就都失效了。

当我们以 push_back() 将新元素插入于 vector 尾端时，该函数首先检查是否还有备用空间，如果有就直接在备用空间上构造元素，并调整迭代器 finish，使 vector 变大。如果没有备用空间了，就扩充空间（重新配置、移动数据、释放原空间）。

4 list

相对于 vector 的连续线性空间，list 就显得复杂许多，它的好处就是插入或删除一个元素，就配置或删除一个元素空间。对于任何位置的元素的插入或删除，list 永远是常数时间。

List 不仅是一个双向链表，而且是一个双向循环链表，只需一个指针就可遍历整个链表。

对于迭代器，只能通过 ++ 或 -- 操作将迭代器移动到后继/前驱节点元素处，而不能对迭代器进行 +n 或 -n 的操作。因此 List 的迭代器是双向迭代器。在 List 中增加任何元素都不会使迭代器失效。删除元素时，除了指向当前被删除元素的迭代器外，其它迭代器都不会失效。

4 deque

vector 是单向开口的连续线性空间，deque 则是一种双向开口的线性空间。所谓双向开口，意思是可以在头尾两端分别做元素的插入和删除操作，虽然 vector 也支持从头端插入元素，不过效率奇差。deque 容器类与 vector 类似，支持随机访问和快速插入删除，它在容器中某一位置上的操作所花费的是线性时间。

deque 与 vector 最大差异：

deque 允许常数时间内对头部进行元素的插入或移除操作。
deque 没有所谓的容量观念，因为它是动态的以分段连续空间组合而成，随时可以增加一段新的空间并拼接起来。

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

deque 采用一块所谓的 map（不是 STL 的 map 容器）作为主控。这里所谓 map 是一小块连续空间，其中每个元素（此处称为一个节点，node）都是指针，指向另一段（较大的）连续线性空间，称为缓冲区。缓冲区才是 deque 的储存空间主体。 SGI STL 允许我们指定缓冲区大小，默认值 0 表示将使用 512 bytes 缓冲区。deque 最初状态（无任何元素）保有一个缓冲区，因此，clear() 完成之后回到初始状态，也一样会保留一个缓冲区。

由于以上结构，deque 的迭代器实现也较为复杂，deque 的迭代器首先必须指出分段连续空间在哪里，其次它必须能够判断自己是否已经处在缓冲区的边缘，如果是，一旦前进或后退就必须跳跃下一个缓冲区，为了能够正常跳跃，deque 必须随时掌握管控中心（map）。下图展示了 deque 的中控器、迭代器和缓冲区的关系：

假设一个 deque 存储 20 个元素，每个缓冲区可以存储 8 个元素，则它的迭代器关系如下：

迭代器 start 内的 cur 指针指向第一块缓冲区的第一个元素，迭代器 finish 内的 cur 指针指向最后一块缓冲区的最后一个元素（的下一位置）。

下面来分析 deque 常用操作对迭代器的影响：

在队前或队后插入元素时（push_back()和push_front()），由于可能缓冲区的空间不够，需要增加 map 中控器，而中控器的个数如果也不够，就需要新开辟更大的空间来容纳中控器，所以可能会使迭代器失效；但指针、引用仍有效，因为缓冲区已有的元素没有重新分配内存。
在队列其他位置插入元素时，由于会造成缓冲区的一些元素的移动，所以肯定会造成迭代器的失效；并且指针、引用都会失效。
删除队头或队尾的元素时，由于只是对当前的元素进行操作，所以其他元素的迭代器不会受到影响，所以一定不会失效，而且指针和引用也都不会失效。
删除其他位置的元素时，也会造成元素的移动，所以其他元素的迭代器、指针和引用都会失效。

5 stack

stack 是一种先进后出（First In Last Out，FILO）的数据结构，它只有一个出口。stack 允许增加元素、移除元素、取得最顶端元素。但除了最顶端外，没有任何其他方法可以存取 stack 的其他元素，换言之，stack 不允许有遍历行为，因此 stack 没有迭代器。stack 默认以 deque 为底层容器。stack 是对 deque 的又一层封装，因此 stack 并不是容器，而被称作配接器。

除了 deque 外，stack 也可以使用 list 作为底层容器，因为二者都是双端开头的容器。

6 queue

queue 是一种先进先出（First In First Out，FIFO）的数据结构，它有两个出口，允许增加元素、移除元素、从最底端加入元素、取得最顶端元素。但除了最底端可以加入、最顶端可以取出外，没有任何其他方法可以存取 queue 的其他元素，换言之，queue不允许有遍历行为，因此 queue 没有迭代器。queue 默认以 deque 为底层容器。

除了 deque 外，queue 也可以使用 list 作为底层容器，因为二者都是双端开头的容器。

7 heap

heap 使用 vector 作为底层容器，关于 heap 的算法可在专题【数据结构】优先队列和堆中找到。STL 默认建立大顶堆。

8 priority_queue

priority_queue 底层使用 heap 实现。