Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

Vinllen Chen


To be a better coder

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中有几个需要注意的概念:

  1. vector中的size为数组大小,由用户指定。vector另外存在一个capacity的概念,其表示容量大小,那么什么是容量大小?容量是vector的实际配置的大小,其往往比客户分配的size更大一些,这样做的好处在于考虑到动态增删时的性能。否则频繁的增删将会引起数组的『抖动』:不断调用数组大小。
  2. 当新插入元素时,如果超过了当前capacity,将会引起容量的扩充,扩充至原来的两倍。如果仍然不够,将会继续扩张至足够大小。new_size = old_size + max(old_size, add_size);
  3. vector中元素的删除只会导致size变小,capacity并不会改变。
  4. capacity的扩张必将经历:新空间分配、元素移动和释放原空间的过程。
  5. 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):插入主要分为三种情况:

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

  以下三个图分别介绍了以上三种情况,图来自侯杰的《STL源码剖析》。
1.png
2.png
3.png

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

2.list

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

3.deque

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

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

    4.png

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支持以下几个操作:

  1. push_heap:堆末尾(即数组末尾)压入元素。根据堆的排序操作,压入后将会进行堆的调整
  2. pop_heap:根结点与末尾互换,最后一个元素排序完毕,同样会触发堆调整。
  3. sort_heap:持续调用pop_heap完成排序。
  4. make_heap:建堆操作。
  5. ……

  heap同样没有迭代器。

7.priority_queue

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

参考

《STL源码剖析》

说明

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


About the author

vinllen chen

Beijing, China

格物致知


Discussions

comments powered by Disqus