c++ - STL 中的 vector 与列表

Question

我在 Effective STL 中注意到

vector is the type of sequence that should be used by default.

这是什么意思？似乎忽略效率 vector 可以做任何事情。

谁能给我一个 vector 不是可行选项但必须使用 list 的场景？

Answer 1

vector :

• 连续内存。
• 为 future 的元素预先分配空间，因此需要的额外空间超出了元素本身所需的空间。
• 每个元素只需要元素类型本身的空间(不需要额外的指针)。
• 可以在添加元素的任何时候为整个 vector 重新分配内存。
• 最后的插入是固定的、摊销的时间，但其他地方的插入是一个代价高昂的 O(n)。
• vector 末尾的删除是常数时间，但其余时间为 O(n)。
• 您可以随机访问其元素。
• 如果您在 vector 中添加或删除元素，迭代器将失效。
• 如果您需要一个元素数组，您可以轻松获取底层数组。

列表:

• 非连续内存。
• 没有预先分配的内存。列表本身的内存开销是恒定的。
• 每个元素都需要额外的空间用于保存该元素的节点，包括指向列表中下一个和上一个元素的指针。
• 永远不必仅仅因为添加一个元素就为整个列表重新分配内存。
• 无论出现在列表的哪个位置，插入和删除都很便宜。
• 将列表与拼接结合起来很便宜。
• 您不能随机访问元素，因此获取列表中的特定元素可能会很昂贵。
• 即使您在列表中添加或删除元素，迭代器仍然有效。
• 如果您需要一个元素数组，则必须创建一个新元素并将它们全部添加到其中，因为没有底层数组。

一般来说，当您不关心您使用的是什么类型的顺序容器时，请使用 vector ，但如果您要在容器中的任何位置(而不是末端)进行多次插入或删除，那么您就是想要使用列表。或者，如果您需要随机访问，那么您将需要 vector ，而不是列表。除此之外，根据您的应用程序，您自然会需要其中一种，但总的来说，这些都是很好的指导方针。