序列式容器概述
序列式容器也叫作顺序性容器，各元素之间有顺序关系的线性表，是一种线性结构的有序群集。
容器中元素都是可序的，但未必是有序的。序列式容器最重要的特点就是可以在首端删除元素，在尾端添加元素，而双向序列容器，允许在两端添加和删除元素。
序列式容器有两种存储方式：连续存储和链式存储。如图1所示。
图1 序列式容器的存储方式
序列中每个元素都有固定的位置，除非用删除或插入的操作改变这个位置。这个位置和元素本身无关，而和操作的逻辑顺序有关。
标准库提供的基本序列式容器包括vector（向量）、deque（双端队列）、list（列表），在使用这三种容器时分别需要包含相应的头文件，示例如下：
#include <vector>
#include <deque>
#include <list>接下来我们就对这三个容器的实现及访问特点进行讲解。
1、vector向量的实现及访问特点
vector向量容器是一种支持高效的随机访问和高效向尾部插入新元素的容器。向量容器一般实现为一个动态分配的数组，向量中的元素连续地存放在这个数组中，因此对向量容器进行随机访问，具有和动态访问数组类似的效率。
向量容器具有扩展容器的功能，当数组的空间不够时，向量容器对象会自动new一块更大的空间，使用赋值运算符将原有的数据复制到新空间，并将原有空间释放。由于每插入一个新元素，向量容器都将“分配新空间—复制元素—释放原空间”的过程执行一遍，那么效率会特别低，因此向量容器在每次扩展空间时，实际分配的空间一般大于所需的空间。
另一方面，将已有元素从微量容器中删除时，多出的闲置空间并不会被释放，因为再插入新元素时可能会重新占用这些空间。因此，向量容器对象已分配的空间所能容纳的元素个数，通常会大于容器中实际存放的元素个数，容器所能存储的最多元素的大小叫作向量容器的容量（capacity），容器实际存储元素的个数叫做向量容器的大小（size），如图2所示。
图2 向量容器的存储结构
向量容器中插入新元素时，插入位置之后的元素都要被顺序的向后移动，因此在总体上向量容器的插入操作效率并不高。插入位置越靠前，执行插入所需的时间就越多。但在向量容器尾部插入元素的效率就比较高了。
在向向量容器中插入元素时，如果插入操作引起了向量容量的扩展，那么执行插入之前所获得的一切迭代器、指针、引用都会失效，因为空间被重新分配了，元素的内存地址发生了变化；如果插入操作没有引起向量容量的扩展，那么只有处于插入位置之后的迭代器、指针、引用失效，因为插入位置后面的元素被移动了，对插入之前的元素不会有影响。
在删除向量容器中的元素时，被删除元素后面的元素会顺序向前移动，将被删除元素留下的空位补上，而后面闲置的空间并不会被释放。删除操作的效率和插入类似，被删除元素越靠前，删除操作所需的时间就越多，删除操作不会引起向量容器容量的改变，因此被删除之前的迭代器、指针、引用都能够继续使用，而删除元素之后的迭代器、指针、引用都会失效。
2、deque双端队列的实现及访问特点
deque是“double-ended queue”的缩写，意为双端队列，和vector一样，都是STL的容器。与vector不同的是，deque是两端开口的，是一种支持向两端插入数据并支持随机访问的容器。双端队列的内部实现不如向量容器那样直观，在STL实现中，双端队列的数据被表示为一个分段数组，容器中的元素分段存放在一个个大小固定的数组中，此外容器还需要维护一个存放这些数组首地址的索引数组，如图3所示。
图3 deque容器存储结构
由于分段数组的大小是固定的，且它们的首地址被连续存储在索引数组中，因此可以对双端队列进行随机访问，但这种随机访问的效率比起向量容器要低的多，向两端加入新元素时（包括使用push_front、push_back、begin()、end()、insert()函数等），如果这一端的分段数组未满，则可以直接加入，如果这一端的分段数组已满，只需创建新的分段数组，并把该分段数组的首地址存储到deque容器中即可。无论哪种情况都不需要对已有元素进行移动，因此在双端队列的两端加入新的元素都具有较高的效率。
当删除双端队列中的元素时（包括使用pop_front()、pop_back()、begin()、end() – 1、erase()函数等），由于不需要发生元素的移动，因此效率也是非常高的。执行删除操作时，只会使被删除元素的迭代器、指针、引用失效，而不会影响其他元素。在删除元素时，deque的内存区块不使用时会被释放掉。
当向双端队列的中间插入元素时，需要将插入点到某一端之间的所有元素向容器的另一端移动，因此向中间插入元素的效率很低，而且往往插入位置越靠近中间，效率越低。这样的插入操作会使所有的迭代器、指针、引用失效，因为向中间插入元素会移动已有的元素，而且向哪一端移动是依STL的实现而定。
当删除双端队列中间的元素时，情况是类似的，由于被删除元素到某一端的所有元素都要向中间移动，因此删除元素越靠近中间，效率越低，删除操作也会使所有的迭代器、指针、引用失效。
3、list列表的实现及访问特点
列表是一种不能随机访问，但可以高效的在任意位置插入和删除元素的容器。列表容器一般实现为链表，而且是双向链表，如图4所示。
图4 list列表容器存储结构
在列表中插入新的元素，只需要为新元素建立一个新链表结点，并修改前后两个结点的指针，而无须移动任何已有元素，因此在列表中插入新元素的效率很高，而且不会使任何已有元素的迭代器、指针、引用失效。
当删除列表中的元素时，需要释放被删除元素所占用的空间，然后修改前后两个结点的指针，也无须移动任何元素，因此效率也很高。执行删除操作时，只会使指向被删除元素的迭代器、指针、引用失效，而不会影响其他元素。
STL所提供的这三种序列式容器各有所长，没有一种万能的容器，在编写程序时，应当根据对容器所执行的操作来选择使用哪一种容器。例如，如果需要执行大量的随机访问操作，就应当选择向量容器；如果需要执行大量的随机插入或删除元素操作，就应当选择列表容器。
了解了三种容器的实现及操作特点，那么接下来我们就来学习一下如何创建容器以及如何对这些容器进行操作。
隐藏目录
