STL中的序列式容器

在STL中，有以下几个序列式容器：array、vector、heap、priority_queue、list、slist、deque、stack、queue。其中vector、list、deque为三个标准容器（container）；stack和queue是在deque上进行封装而成的，专有名词叫做配接器（adapter）；array是C++内建容器，不对外使用；heap是基于vector封装的，priority_queue是基于heap封装的；slist是非标准的单向链表。

1.vector

vector是C++中的动态数组，可以动态增删，而不需要类似静态数组自己维护空间的分配，其维护的也是一个连续线性空间，支持随机存取，良好的特性使得其成为STL中最常用的容器之一。
vector中有几个需要注意的概念：

vector中的size为数组大小，由用户指定。vector另外存在一个capacity的概念，其表示容量大小，那么什么是容量大小？容量是vector的实际配置的大小，其往往比客户分配的size更大一些，这样做的好处在于考虑到动态增删时的性能。否则频繁的增删将会引起数组的『抖动』：不断调用数组大小。
当新插入元素时，如果超过了当前capacity，将会引起容量的扩充，扩充至原来的两倍。如果仍然不够，将会继续扩张至足够大小。new_size = old_size + max(old_size, add_size);。
vector中元素的删除只会导致size变小，capacity并不会改变。
capacity的扩张必将经历：新空间分配、元素移动和释放原空间的过程。
capacity的扩张将会导致原迭代器失效。这是因为空间的重分配。

其提供的主要接口如下：

begin()：返回数组初始位置的迭代器
end()：返回数组终止位置的迭代器
size()：数组大小
capacity()：数组容量
empty()：是否为空
operator[]：下标操作
front()：取头元素
end()：取末尾元素
erase(iterator first, iterator last)：删除指定迭代器区间的内容
erase(iterator position)：删除指定位置的元素
insert(iterator position, size_type n, const T &x)：在position位置插入n个值为x的元素
start：空间头私有变量
finish：空间结尾私有变量
end_of_storage：容量的结尾私有变量
……

别的操作大部分不难，我们重点介绍一下插入过程insert(iterator position, size_type n, const T &x)：插入主要分为三种情况：

插入后未达到capacity总容量，且『插入的元素』个数小于『插入点之后到数组结尾的元素』个数。
插入后未达到capacity总容量，且『插入的元素』个数大于等于『插入点之后到数组结尾的元素』个数。
插入后超过capacity总容量。

以下三个图分别介绍了以上三种情况，图来自侯杰的《STL源码剖析》。

或许有些人会跟我一样的疑问，第一个和第二个的移动为什么要分成两步操作，一起往后移动不就能搞定吗？这个问题保留着。

2.list

list的存储不是连续的空间，其为双向链表结构（slist为单向链表结构，但并不是标准的容器）。链表的优势在于插入、删除方便，不用引起空间的大范围挪动，只会操作单个结点，而且插入操作不会导致迭代器失效；缺点在于查找做不到O(1)的时间复杂度，因为其非连续空间。

3.deque

vector是一种单向开口的连续线性空间，而deque是一种双向开口的『连续』线性空间，之所以加上引号是因为其非严格的连续，而是将几个连续的空间组合而成。其主要性能如下：

deque支持常数时间的两端的push，pop操作。
deque没有capacity概念，而是动态地将分段连续空间组合而成。
除非必要，应尽量使用vector而非deque。deque对于排序性能比较慢，为了提高效率，可以将deque复制到一个vector执行排序操作后，再复制回deque。
deque通过一个中控器map（并非STL中的map容器）将多个连续空间连在一起，如下图所示：

4.stack

stack以deque为底部容器并封闭其头端开头，或者以list为底部容器。只允许对末端的压入、弹出、取栈顶操作。不允许并不提供迭代器遍历。

5.queue

类似于stack，queue也可以以deque或者list为底部容器。其只允许头端pop、取队顶，尾端push操作，同样不支持遍历。

6.heap

heap为堆结构，其为priority_queue（优先队列）的底部结构，其构成一个完全二叉树，并借助vector容器组成一个数组（对于i结点的左儿子位于2i，右儿子位于2i+1）。
堆排序：以自小到大排序为例子，我们需要构建一个最大堆，一个正常的堆操作包括：建堆（将所有数构成一个堆）、调整堆（自底向上调整：大的元素往上调）、压入元素（末尾压入，压入后会触发该结点向上的递归调整）、弹出元素（根结点必为最大元素，与末尾元素互换：这样最后一个元素就排完了，同样会出发自顶向下的调整操作）。不断弹出元素，最后排序就完成了。关于最小/大堆的排序操作可以参考严版的《数据结构》。
STL中的heap支持以下几个操作：

push_heap：堆末尾（即数组末尾）压入元素。根据堆的排序操作，压入后将会进行堆的调整
pop_heap：根结点与末尾互换，最后一个元素排序完毕，同样会触发堆调整。
sort_heap：持续调用pop_heap完成排序。
make_heap：建堆操作。
……

heap同样没有迭代器。

7.priority_queue

优先队列以heap为底部容器，相当于一个排序的堆，压入队列意味着压入堆，弹出队列意味着弹出堆中优先级最高的元素。与队列操作类似：支持取头部元素、pop头部、压入队尾灯操作。当然，也没有迭代器操作。需要注意的是：优先队列和堆不支持对已经压入的结点动态调整优先级操作，其将会触发的后果不定，具体原因与一次pop导致的堆调整为一个支线（自顶向下一条路径的递归）的调整，而不是整个堆。

参考

《STL源码剖析》

说明

转载请注明链接：vinllen.com/stlzhong-de-xu-lie-shi-rong-qi/

Your browser is out-of-date!

Vinllen Chen