C++程序设计：原理与实践（进阶篇）15.7　vector、list和string

15.7　vector、list和string

为什么我们对行用list而对字符用vector呢？更准确地说，我们为什么要用list保存行的序列而用vector保存字符序列呢？再有，为什么不用string来存储一行呢？

我们可以把这些问题再一般化一些。到现在为止，我们知道了四种存储字符序列的方法：

char[]（字符数组）；

vector<char>；

string；

list<char>。

那么对于一个给定问题应该采取哪种存储方式呢？当问题非常简单时，选择哪种方式都无所谓，因为它们都有非常相似的接口。例如，给定一个iterator，我们可以使用++遍历所有字符，用*访问字符。在与Document相关的代码示例中，我们的确可以将vector<char>换成list<char>或string，而不会引起任何逻辑上的问题。这是非常好的特性，因为这令我们只需从性能角度选择存储方式。但是，在考虑性能之前，我们先来看看这些存储方式的逻辑特性：有什么是它能做而其他方式所不能的？

Elem[]：不知道它自己的大小。没有begin()、end()或任何其他有用的容器成员函数。不能系统地实现边界检查。可以作为参数传递给用C或C++编写的函数。其中的元素在内存中连续存储。数组的大小在编译时就确定了。比较（==和!=）和输出（<<）操作使用的是指向数组第一个元素的指针，而不是元素。

vector[Elem]：基本上可以做所有事，包括insert()和erase()。支持下标操作。在其上的列表操作，例如insert()和erase()，通常需要移动字符（当元素很大或元素数目很多时效率会比较低）。可实现边界检查。元素在内存中连续存储。vector可以扩展（例如使用push_back()）。向量的元素（连续）存储在数组中。比较运算符（==、!=、<、<=、>、>=）对元素进行比较。

string：提供了所有常见的有用操作，还提供了特殊的文本处理操作，例如字符串的连接（+和+=）。其元素保证在内存中连续存储。string可以扩展。比较运算符（==、!=、<、<=、>、>=）对元素进行比较。

list[Elem]：提供了除下标外所有常见的有用操作。我们在进行insert()或erase()操作时不必移动其他元素。每个元素需要两个额外的字（用来存储链接指针）。list可以扩展。比较运算符（==、!=、<、<=、>、>=）对元素进行比较。

正如我们之前提到的（见12.2节和13.6节），当我们需要在底层和内存打交道或需要和C程序交互时数组是非常有用且必需的（见27.1.2节和27.5节）。在其他情况下，vector由于更方便、灵活且安全，应是首选。

试一试

上述的区别在实际的代码中意味着什么？分别定义一个保存值"Hello"的char数组、vector<char>、list<char>和string，并把它们作为参数传递给一个函数。该函数首先输出传来的字符串中的字符数目，并将其与函数内定义的"Hello"相比较（以判断你是否真的传递了"Hello"），然后再与"Howdy"比较，看看它们在字典中谁更靠前。把参数复制到另一个相同类型的变量中。

试一试

重复上面的“试一试”，这次测试int数组、vector<int>和list<int>，都保存数值{1,2,3,4,5}。

15.7.1　insert和erase

标准库vector是我们使用容器时的首选。它几乎具有所有所需特性，所以我们只在没有办法时才会使用其他的替代品。vector主要的问题在于每当我们执行列表操作（insert()和erase()）时，都需要对元素进行移动。当vector中的元素很多或元素很大时，移动元素会产生很高的代价。但也不必太担心这一点。我们可以放心地用push_back()读取50万个浮点数存入一个vector中，实验证明相对于预分配所有内存的方法，push_back()并无明显的性能劣势。在为了性能而做出重大改变前一定要进行性能测试，即使是专家也很难猜测性能。

正如在15.6节中所提到的，移动元素的特性还意味着一个逻辑限制：当你对一个vector执行列表操作（如insert()、erase()和push_back()）时一定不要保留指向其元素的迭代器或指针：若元素移动，你的迭代器或指针将会指向错误的元素，甚至根本不指向任何元素。这也正是list相对于vector（以及map，参见16.6节）的根本优势。如果你在程序中需要使用很多大对象，而且会在很多地方（用迭代器或指针）指向它们，则应考虑使用list。

我们来比较一下list和vector的insert()和erase()操作。首先看一个仅用来展示关键点的例子：

现在q是无效的。随着向量的大小增长，可能会为其元素分配新的内存。如果v有空闲空间，则它会原地增长，q很可能指向的是值为3的元素而不是值为4的元素，但千万不要认为一定会是这样。

也就是说，如果在insert()操作后执行一次erase()操作删除刚刚插入的元素，那么我们就回到了起始状态，只是q变成无效了。但是，在这两次操作之间，我们移动了插入点之后的所有元素，随着v增长所有元素可能都被重新分配空间了。

作为对比，我们使用list来完成相同的操作：

注意，q仍然指向值为4的元素。

 我们又一次发现回到了起始状态。但是，与vector的不同之处在于，我们没有移动任何元素，q始终是有效的。

list<char>与其他三种容器相比需要至少3倍的存储空间——在PC上，一个list<char>需要12个字节来保存每个元素，而vector<char>只需要1个字节。当字符数很多时，这种差距可能很重要。

那vector哪方面优于string呢？从它们的特性中可以发现，string似乎能完成比vector更多的功能。但这也正是部分问题的所在：由于string必须完成更多功能，对它进行优化也就更困难了。实际上，vector设计思想之一就是对push_back()这样的“内存操作”进行优化，而string并没有。取而代之，string对拷贝操作、短字符串处理以及与C风格字符串的交互进行了优化。在文本编辑器的例子中，我们选择vector是因为需要使用insert()和delete()，另一方面也是出于性能的考虑。vector和string逻辑的主要差异在于vector几乎可以用于任何元素类型，而只有在处理字符时我们才需要考虑string。总之，只有当需要进行字符串操作（例如字符串连接或读取空白符间隔的单词）时才考虑使用string，其他情况下，就用vector好了。