7.4　基本序列容器：vector、Iist和deque

所有基本序列容器完全按照存进去时的顺序持有对象。然而，对于不同的基本序列容器，它们的操作效率是不同的，因此如果想要操纵具有某种特点的序列，则应当针对不同的操作类型选择合适的容器。到现在为止，本教材中已经使用了vector作为精选的容器。并经常在一些示例中应用它。然而，当开始用容器做更复杂的工作时，更多地了解容器的底层实现和行为就变得很重要了，这样就使得程序员能够根据需要做出正确的选择。

7.4.1　基本序列容器的操作

下面的例子用一个模板演示了所有基本序列容器：vector、deque和list所支持的操作：

第1个函数模板，print（），演示了能够从任何序列容器中得到的基本信息：容器是否为空、容器当前大小、容器的最大可能尺寸、起始元素和终止元素等。也可以看到，每一个容器都有成员函数begin（）和end（）用以返回迭代器。

函数basicOps（）检测包括多种构造函数在内的所有其他信息（并且依次调用print（））：默认构造函数、拷贝构造函数、数量和初值、起始和终止迭代器。还有一个用于赋值的operator=和两种类型的assign（）成员函数。这两个函数其中之一用来获取数量和初始值，而另一个则用来获取起始迭代器和终止迭代器。

所有的基本容器都是可逆容器，就像使用成员函数rbegin（）和rend（）所演示的一样。一个序列容器可以重置它的大小，而且可以用clear（）删除容器中的全部内容（所有元素）。当调用resize（）扩展一个序列时，新的元素使用序列内元素类型的默认构造函数，如果它们是内置类型，则使用0作为初始值。

用一个迭代器来指定在任何一个序列容器中想要插入元素的起始位置，可以用insert（）插入单个元素，或插入具有相同值的一组元素，或者由一组起始和终止迭代器标识的来自其他容器的一组元素。

要用erase（）清除序列中间的一个元素，使用一个迭代器；要用erase（）清除序列中间的一组元素，使用一对迭代器。注意，因为仅支持双向迭代器，list中所有迭代器都只能通过增1或减1来进行移动。（如果容器为可以产生随机访问迭代器的vector或者deque, operator+和operator-可以使迭代器移动更大的距离。）

尽管list和deque支持push_front（）和pop_front（），vector却不支持，但3者都支持push_back（）和pop_back（）。

成员函数swap（）的命名令人有点疑惑，因为还存在另外一个非成员函数swap（）算法用以交换两个相同类型的对象的值。成员函数swap（）在两个容器间交换所有东西（如果这两个容器持有相同类型的对象的话），实际上高效地交换了容器本身。它通过交换各个容器的内容来高效地实现交换，这些容器通常存储的是指针。而非成员函数swap（）算法通常采用赋值的方式来交换其参数（对于整个容器来说是代价比较高的操作），但是对于标准容器来说，它已经通过模板的特化定制为调用成员函数swap（）了。还有一个iter_swap算法，使用迭代器来交换同一个容器中的两个元素。

以下部分的内容讨论各种类型的序列容器的特点。

7.4.2　向量

vector类模板被有意地设计成看起来像一个快速的数组，因为它具有数组风格的索引方式，而且它还可以动态地进行扩展。vector类模板具有非常基本的用途，以至于早在本教材的前面就用一种很基本的方法介绍过，并在前面的例子中经常使用。这一节将更深入地介绍vector。

为了达到最高效地进行索引和迭代，vector将其存储内容作为一个连续的对象数组来维护。在理解vector的行为时有一个关键点，那就是索引和迭代操作非常快，基本上和在一个对象数组上进行索引和迭代一样快。但是，这也意味着除了在最后一个元素之后插入新元素（即增补新元素）外，向vector中插入一个对象是不可以接受的操作。另外，当一个vector预分配的存储空间用完以后，为维护其连续的对象数组，它必须在另一个地方重新分配大块新的（更大的）存储空间，并把以前已有的对象拷贝到新的存储空间中去。这种方法造成了一些令人不快的副作用。

1.已分配存储区溢出的代价

vector从获取到某块存储区开始，就好像一直在进行猜测：程序员将计划放多少对象进去。在放入的对象还没有超出初始存储块所能装载的对象数目的时候，所有的操作都进行得飞快。（如果程序员预先知道有多少个对象的话，就可以使用reserve（）预先分配存储区）。但是，在程序运行过程中，最终将会放入过多的对象（超出该存储区的存储范围，即溢出），这时vector会做出如下响应：

1）分配一块新的、更大的存储区。

2）将旧存储区中的对象拷贝到新开辟的存储区中去（使用拷贝构造函数）。

3）销毁旧存储区中所有的对象（为每一个对象调用析构函数）。

4）释放旧存储区的内存。

对于复杂对象，如果经常把vector装填得过满的话，系统将会为这些拷贝构造和析构操作的完成付出高昂的代价，这就是为什么vector（以及一般的STL容器）被设计成值类型（比如那些容易拷贝的类型）容器的原因。其中也包括指针。

为了观察在填充一个vector时会发生什么事情，这儿有一个前面已经提到过的Noisy类。它打印出其有关创建、析构、赋值以及拷贝构造的信息：

每个Noisy对象都有其标识符，并且设置了一些静态static变量用来跟踪所有的创建、赋值（使用运算符operator=）、拷贝构造和析构操作。使用计数器create中的默认构造函数来初始化id；而拷贝构造函数和赋值操作符则通过右值取得它们的id值。与运算符operator=在一起的左值是一个已经初始化了的对象，所以id在被右值覆盖重写以前打印出其原来的id值。

为了支持诸如排序和查找（它们被某些容器隐含地使用）操作，Noisy必须有运算符operator＜和operator==。这仅仅是比较id值。输出流ostream插入符遵循常用的形式并且仅打印出id值。

类型NoisyGen的对象是在检测期间产生Noisy对象的函数对象（因为有一个operator（））。

NoisyReport是一个单件对象，^[1]因为我们仅仅要在程序结束时打印一个报告。它有一个私有的private构造函数，故不可能创建另外的NoisyReport对象，它不允许赋值和拷贝构造，而且有一个静态的名为nr的NoisyReport实例。在析构函数中只有可执行语句，它们在程序退出和调用静态的析构函数时执行。该析构函数打印出Noisy中的所有static静态变量所收集的一些统计信息。

使用Noisy.h，下列程序演示了一个vector分配的存储区溢出的情形：

可以使用默认值1000，也可以通过命令行键入读者自己设定的值。

当运行该程序时，将会看到一个默认构造函数调用（为n），然后是很多的拷贝构造函数的调用，接下来是一些析构函数的调用，然后又是很多的拷贝构造函数的调用，等等。当vector用光了（超出）为线性数组分配的空间字节时，它必须（维护线性数组中的所有对象，这是它的工作中最重要的部分）获得一块更大的存储空间并且将原来的内容全部移过去，先拷贝然后销毁原来的对象。可以想到，如果存储了大量巨大而复杂的对象，该过程将会很快地变得令人望而却步。

这个问题有两种解决方案。最好的解决方案是要求程序员事先知道到底需要创建多少个对象。在这种情况下，可以使用reserve（）来告诉vector预分配多大的存储区，这样就避免了所有的拷贝和析构操作，而使得任何事情都可以很快地完成（特别是使用操作符operator[]来对对象进行随机访问）。注意，使用reserve（）预分配存储区与通过给出一个整数作为vector构造函数的第1个参数是有区别的；后者将使用元素类型的默认构造函数来初始化被规定的元素个数。

通常情况下，程序员并不知道将会需要多少个对象。如果vector的重分配操作使程序执行变得迟缓，可以改用其他序列容器。可以使用链表list，但是读者将会看到，deque允许在序列的两端快速地插入元素，并且在其扩展存储区的时候不需要拷贝和销毁对象的操作。deque也允许使用操作符operator[]进行随机访问，但是没有vector的操作符operator[]执行得那么快。因此，如果在程序的某一处创建所有的对象，并且在另一处随机访问它们，可以先填充一个deque，再从该deque的基础上创建一个vector，用以达到快速索引的目的。不应该按照这种习惯去编程—只要知道有这些问题就行了（也就是说，避免过早地进行性能优化）。

然而，vector的内存重分配还会带来更糟的问题。因为vector在一个优美简洁的数组中保存它的对象，被vector使用的迭代器可以是简单的指针。这很好——在所有的序列容器中，这些指针允许以最快的速度选择和操纵容器内的元素。不论它们是简单的指针，还是一个持有指向其容器内部指针的迭代器对象，考虑当添加了一个额外的对象时，为什么会发生导致vector进行重新分配存储区并且将其内容移动到别处去的事情。现在那个迭代器的指针指向了一个未知的地方：

这里举例说明了一个称为迭代器无效（iterator invalidation）的概念。某种操作引发了涉及容器底层数据的内部变化，因此在变化之前有效的那些迭代器可能后来都不再有效。如果这个程序正试图打破神秘感，那么在向一个vector加入多个对象时，请查看一下持有的迭代器的位置。在向vector中加入元素或者使用操作符operator[]来代替元素选择以后，需要得到一个新迭代器。如果将这种观察结果与向一个vector加入新对象所知道的潜在开销结合起来看的话，可以得出下述结论。使用一个vector的最安全的方法，就是一次性地填入所有的元素（在理想的情况下，首先应该知道到底需要多少个对象），然后在程序的另一处仅仅使用它（不再加入更多的元素）。这也是本教材到目前为止使用vector的方法。标准C++库文档给出了迭代器无效的容器操作。

在前面各章中那些使用vector作为“基本”容器的内容中，读者可能已经观察到，也许在所有的情况下不是最佳的选择。这是容器和数据结构理论中的一个基本问题，一般而言—“最佳”选择的改变取决于容器的使用方法。到目前为止，vector作为“最佳”选择的理由是它看起来跟一个数组非常相似，因此采用它使读者感到更熟悉和更容易。但是从现在开始，在选择容器时也应该考虑一下有关的其他问题。

2.插入和删除元素

使用vector最有效的条件是：

1）在开始时用reserve（）分配了正确数量的存储区，因此vector绝不再重新分配存储区。

2）仅仅在序列的后端添加或者删除元素。

利用一个迭代器向vector中间插入或者删除元素是可能的，但是下面的程序却演示了一个糟糕的想法：

在运行该程序的时候，可以看到，对预分配函数reserve（）的调用实际上仅仅是分配存储区—并没有调用构造函数。对generate_n（）的调用非常频繁：每次对NoisyGen：operator（）的调用都导致一次构造、一次拷贝构造（加入vector）和一个临时对象的析构操作。但是，当一个对象被插入到vector的中间位置时，必须向后移动该插入位置后面所有的对象以便维持这个线性数组，而且由于有足够的空间，它通过赋值操作符来实现。（如果reserve（）的参数是10而不是11，它就必须重新分配存储区。）当从vector中删除一个对象时，再次使用赋值操作符将该删除位置后面所有的元素向前移动以覆盖被删除元素的位置。（注意，这就要求赋值操作符可以正确地清理左值。）最后，数组末端那个对象被删除。

7.4.3　双端队列

双端队列deque容器是一种优化了的、在序列两端对元素进行添加和删除操作的基本序列容器。它也允许适度快速地进行随机访问—就像vector一样，它也有一个operator[]操作符。然而，它没有vector的那种把所有的东西都保存在一块连续的内存块中的约束。deque的典型实现是利用多个连续的存储块（同时在一个映射结构中保持对这些块及其顺序的跟踪）。因此，向deque的两端添加或删除元素所带来的开销很小。另外，它从不需要在分配新的存储区时复制并销毁所包含的对象（就像vector所做的那样），所以在向序列两端添加未知数量的对象时，deque远比vector更有效率。这意味着，只有在确切知道到底需要多少个对象的时候，vector才是最优的选择。另外，在本教材前面的章节所列举的许多使用vector和push_back（）的程序示例，如果改用deque替代的话，可能会更有效率。deque的接口和vector的接口仅仅有很小的不一致（比如，deque拥有push_front（）和pop_front（），当使用vector的时候就没有），所以将使用vector的代码转变为使用deque要做的工作是微不足道的。考虑程序StringVector.cpp，仅仅需要将程序中所有地方的单词“vector”改为“deque”，就可以使用deque了。下列程序将在StringVector.cpp中增加与vector操作平行的deque操作，并且比较它们的执行时间：

之所以向vector中增加对象时执行效率低下，就是因为存储区的重分配，读者可能期待两者之间产生戏剧性的差别。然而，对于一个有1.7MB的文本文件，由一个编译器编译的程序产生的输出如下（测试结果是被测量操作平台/编译器中特殊的时钟滴答声，不是秒数）：

不同的编译器和操作平台几乎都同意这个结果。得到的结果并没有产生什么戏剧性的变化，难道不是吗？这指出了一些重要的问题：

1）我们（程序员和作者）对此进行典型的最坏猜测，就是在程序中的某些地方有低效的事件发生。

2）效率来自各种效果的组合。在这里，读进每一行并将其转换为字符串就可以控制上面vector对deque的代价对照比较。

3）string类在效率方面的设计相当好。

这并不意味着在不确定的对象数将被存入容器末端的时候不用deque而用vector。正相反，应该用deque—特别是在调整程序的性能的时候。同时也要注意到，引起程序性能方面的问题通常并不是在你认为有问题的地方，了解性能瓶颈确切地点的惟一方法就是进行测试。在本章稍后的内容中，读者将会看到vector、deque和list之间更“纯的”性能比较。

7.4.4　序列容器间的转换

有时在程序的某一部分需要某一种容器的行为或效率，而在程序的另一部分则需要不同容器的行为或效率。比如，在向容器中添加对象时需要deque的效率，但是在对这些对象进行索引时又需要vector的效率。每一个基本序列容器（vector、deque和list）都有一个双迭代器的构造函数（指明了在创建一个新的对象时在序列中读取的起始和终止位置），和一个用于将数据读入一个现存的容器中的成员函数assign（），所以可以很容易地将对象从一个序列容器移到另一个序列容器。

下面的例子将对象读入deque内，然后将其转换到一个vector：

读者可以尝试各种尺寸大小的容器，但是请注意，这其实并没有什么差别—这些对象仅被拷贝构造到新的vector中去。有趣的是，在构建vector的时候v1并不会导致多次内存分配，不管使用多少元素都是这样。读者可能最初会认为，必须遵循用在v2上的过程，预分配内存空间以避免零乱的重新分配，但这没有必要，因为v1使用的构造函数早就决定了需要的内存空间。

已配置存储区溢出的代价

与VectorOverflow.cpp不同，可以更清楚地看到，在使用deque的情况下，当一个存储块发生溢出时会发生什么事情。

在“cleaning up”输出出现之前，这里有相对较少的（如果有的话）析构函数调用。因为deque在多个块中分配所有的存储区，而不是像vector一样使用一个类数组的存储区，它从来不需要移动现存的各个数据块的存储区。（因此，就不会有额外的拷贝构造和析构发生。）deque仅仅分配一块新存储区。出于相同的原因，deque可以高效率地向序列开始端添加元素，因为如果它用完了存储区，它只需（再一次）为序列的开始端分配一个新的存储块。（然而，用于保存数据块索引信息的存储块却有可能需要重新分配。）可是，在一个deque的中间插入元素，可能甚至比vector更麻烦（但代价不大）。

因为deque聪明的存储管理方式，在向deque的两端添加元素以后，现存的迭代器都不会失效，就像在演示中对vector所做的那样（见VectorCoreDump.cpp）。如果坚持deque在以下情况下是最好的—从序列的两端插入或删除元素，合理地快速遍历，以及使用operator[]进行相当快速的随机访问—读者将会形成良好的编程习惯。

7.4.5　被检查的随机访问

vector和deque都提供了两个随机访问函数：进行索引操作符（operator[]），这是读者已经看到过的，以及at（），它检测正被索引的容器的边界，如果超出了边界则抛掷出一个异常。使用at（）时代价更高一些：

就像在第1章中看到的那样，不同的系统采用不同的方法来处理未捕获的异常，但是在使用at（）的时候，你可以通过多种途径知道程序的某一部分发生了错误，可是在使用operator[]时却可能对此一无所知。

7.4.6　链表

list以一个双向链表数据结构来实现，如此设计是为了在一个序列的任何地方快速地插入或删除元素，对于vector和deque而言这是一个代价高得多的操作。list没有操作符operator[]，所以当对一个list进行随机访问时速度非常之慢。其最适用的场合就是在按顺序从头到尾（反之亦然）遍历一个序列的时候，而不是随机地从序列中间选择某一个元素。尽管那样，其遍历速度与vector相比仍然较慢，但如果不做那么多遍历操作的话，那就不会成为影响程序性能的瓶颈。

在list中每个链接的内存开销需要为实际对象所在的存储区顶部设置一个前向和反向指针。因此，在有较大的对象需要从list中间进行插入或者删除时，list是一个较好的选择。

如果想查找对象要频繁地遍历序列，最好不使用list，因为遍历是从list的开始端—这是惟一能够开始的地方，除非已经得到一个迭代器，它指向已知道的离目标最近的位置—直到找到感兴趣的那个对象，所耗费的时间与该对象到list开始端之间的对象数目成比例。

list中的对象在创建以后绝不会移动。“移动”一个list的元素意味着改变其链接关系，但绝不会进行拷贝或者对某个实际的对象赋值。这就意味着，在元素被添加到list中时，迭代器不会失效，就像较早示例中利用vector演示的那样。这里有一个使用Noisy对象的list的例子：

对于list，例如，像进行逆转和排序这些看起来激进的操作都不需要拷贝对象，那是因为，仅需要改变链接而不是移动对象。然而，要注意sort（）和reverse（）都是list的成员函数，所以它们有list内在的特殊知识，能够以再排列元素来代替拷贝它们。另一方面，函数swap（）则是一个通用算法，它并不了解有关list的特别之处，所以它利用拷贝的方法来进行两个元素的交换。一般情况下，如果系统提供了某个算法的成员版本就使用这个成员版本而不使用其等价的通用算法。特别应当指出，通用的sort（）和reverse（）算法仅适用于数组、vector和deque。

如果有较大、复杂的对象，就可能要首先选择list，特别是如果构造、析构、拷贝构造以及赋值操作的代价巨大，如果要进行大量的像对对象进行排序或以别的方式对它们进行重新排列操作的时候更是这样。

1.特殊的list操作

list有一些特殊的内置操作使其以最好的方式利用list的结构。读者已经看到了reverse（）和sort（），这里还有另外一些操作：

在用Noisy对象填充了4个list之后，一个list通过3种方式结合成另一个list。首先，整个链表l2在迭代器it1处被接合为链表l1。注意，在接合之后l2是空的—该接合意味着从源链表中删除所有对象。第2次接合从链表l3中在迭代器it2位置开始，将那些元素插入到链表l1中从迭代器it1处开始的位置。第3次接合从链表l1在迭代器it1处开始，并且使用了链表l4中始于迭代器it3终于迭代器it4的那些元素。从表面上看对源链表的提及是多余的，这是因为必须将那些将被传输到目的链表的元素从源链表中删除。

演示删除函数remove（）的代码输出表明，删除具有特定值的所有元素，链表不必排序。

最后，如果要用merge（）合并两个链表，只有确定这些链表是否都已经排过序，合并才有意义。在这种情况下最终得到的是一个包含了两个链表中所有元素并排过序的新链表（源链表已经被删除—即其所有的元素已经被移动到目的链表中去了）。

一个unique（）成员函数将从list中删除所有重复的对象，惟一的条件就是首先对list进行排序：

在这里使用的list构造函数采用来自另外一个容器的起始和超越末尾的迭代器，并将那个容器中的所有元素复制到其自己的list中。这里，“容器”仅仅是一个数组，而“迭代器”是指向那个数组的指针，但是因为STL的设计，list的构造函数可以像使用任何其他容器一样很容易地使用数组。

函数unique（）仅仅将毗连的重复元素删除，因此在调用unique（）之前需要对序列进行排序。当试图解决的问题为根据当前排列的顺序除去毗连的重复元素的时候是个例外。

在这里还有4个附加的list成员函数未被演示：remove_if（）获得一个预报，该预报决定了某个元素是否能被删除；unique（）获得一个二元的预报以进行惟一性比较；merge（）获得一个附加的用于进行比较的参数；sort（）获得一个比较器（以提供比较或者覆盖当前存在的那个元素）。

2.链表与集合

看一看前面的那个例子，读者可能已经注意到，如果需要一个没有重复元素并且已排过序的序列，得到结果可以是一个集合set。对这两个容器的性能进行比较将会很有帮助：

当运行程序的时候，读者会发现set比list快得多。这是可靠的—毕竟，set的主要工作就是在排过序的序列中只保存独一无二的元素。

这个程序使用了头文件PrintContainer.h，其中包含一个函数模板，该函数模板用于将任何序列容器打印到一个输出流。PrintContainer.h定义如下：

这里定义的模板print（）仅调用了在前一章里的PrintSequence.h中定义的函数模板print（）。

7.4.7　交换序列

我们在前面已经提到过，所有的基本序列容器都有一个成员函数swap（），该函数被设计用来将一个序列转换为另一个序列（但只能用于相同类型的序列）。成员函数swap（）利用了它对特定容器内部结构的知识，从而提高了操作的效率。

在运行这个程序时，读者将会发现，每一种类型的序列容器都能在不需要复制或者赋值的情况下将一种序列变换为另一种序列，即使这些序列的尺寸不同。实际上，其所做的是完全地将一个对象的资源交换为另一个对象的资源。

STL算法也包含一个swap（），当该函数应用于两个相同类型的容器时，它使用成员函数swap（）来达到快速的性能。所以，如果对容器的一个容器应用sort（）算法，读者会发现其执行速度非常快—这表明对容器的一个容器进行快速排序也是设计STL的一个目的。

[1]单件是一种著名的设计模式，将在第10章中深入介绍。