C++ STL 中的向量与列表

vector vs. list in STL

提问by skydoor

I noticed in Effective STL that

我在 Effective STL 中注意到

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

vector 是默认情况下应该使用的序列类型。

What's does it mean? It seems that ignore the efficiency vectorcan do anything.

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

Could anybody offer me a scenario where vectoris not a feasible option but listmust be used?

任何人都可以向我提供一个vector不是可行选项但list必须使用的场景吗？

采纳答案by Martin York

Situations where you want to insert a lot of items into anywhere but the end of a sequence repeatedly.

您想要将大量项目重复插入到序列末尾以外的任何位置的情况。

Check out the complexity guarantees for each different type of container:

查看每种不同类型容器的复杂性保证：

What are the complexity guarantees of the standard containers?

标准容器的复杂性保证是什么？

回答by Jonathan M Davis

vector:

向量：

• Contiguous memory.
• Pre-allocates space for future elements, so extra space required beyond what's necessary for the elements themselves.
• Each element only requires the space for the element type itself (no extra pointers).
• Can re-allocate memory for the entire vector any time that you add an element.
• Insertions at the end are constant, amortized time, but insertions elsewhere are a costly O(n).
• Erasures at the end of the vector are constant time, but for the rest it's O(n).
• You can randomly access its elements.
• Iterators are invalidated if you add or remove elements to or from the vector.
• You can easily get at the underlying array if you need an array of the elements.

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

list:

列表：

• Non-contiguous memory.
• No pre-allocated memory. The memory overhead for the list itself is constant.
• Each element requires extra space for the node which holds the element, including pointers to the next and previous elements in the list.
• Never has to re-allocate memory for the whole list just because you add an element.
• Insertions and erasures are cheap no matter where in the list they occur.
• It's cheap to combine lists with splicing.
• You cannot randomly access elements, so getting at a particular element in the list can be expensive.
• Iterators remain valid even when you add or remove elements from the list.
• If you need an array of the elements, you'll have to create a new one and add them all to it, since there is no underlying array.

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

In general, use vector when you don't care what type of sequential container that you're using, but if you're doing many insertions or erasures to and from anywhere in the container other than the end, you're going to want to use list. Or if you need random access, then you're going to want vector, not list. Other than that, there are naturally instances where you're going to need one or the other based on your application, but in general, those are good guidelines.

通常，当您不关心使用的是哪种类型的顺序容器时，请使用 vector，但如果您在容器中的任何位置（而不是末尾）进行多次插入或擦除操作，则您会想要使用列表。或者，如果您需要随机访问，那么您将需要向量，而不是列表。除此之外，在某些情况下，您自然会根据您的应用程序需要一个或另一个，但总的来说，这些都是很好的指导方针。

回答by Hans Passant

If you don't need to insert elements often then a vector will be more efficient. It has much better CPU cache locality than a list. In other words, accessing one element makes it verylikely that the next element is present in the cache and can be retrieved without having to read slow RAM.

如果您不需要经常插入元素，那么向量会更有效。它比列表具有更好的 CPU 缓存局部性。换句话说，访问一个元素使得下一个元素很可能出现在缓存中，并且可以在无需读取慢速 RAM 的情况下检索。

回答by Tomasz Gandor

Most answers here miss one important detail: what for?

这里的大多数答案都忽略了一个重要细节：为什么？

What do you want to keep in the containter?

您想在容器中保留什么？

If it is a collection of ints, then std::listwill lose in every scenario, regardless if you can reallocate, you only remove from the front, etc. Lists are slower to traverse, every insertion costs you an interaction with the allocator. It would be extremely hard to prepare an example, where list<int>beats vector<int>. And even then, deque<int>may be better or close, not justyfing the use of lists, which will have greater memory overhead.

如果是ints的集合，那么std::list在每种情况下都会丢失，无论您是否可以重新分配，您只能从前面删除等等。列表的遍历速度较慢，每次插入都会花费您与分配器的交互。准备一个例子是非常困难的，其中list<int>beats vector<int>。即便如此，deque<int>可能会更好或更接近，而不是仅仅使用列表，这将具有更大的内存开销。

However, if you are dealing with large, ugly blobs of data - and few of them - you don't want to overallocate when inserting, and copying due to reallocation would be a disaster - then you may, maybe, be better off with a list<UglyBlob>than vector<UglyBlob>.

但是，如果您正在处理大而难看的数据块 - 而且很少 - 您不想在插入时过度分配，并且由于重新分配而复制将是一场灾难 - 那么您可能会更好list<UglyBlob>比vector<UglyBlob>。

Still, if you switch to vector<UglyBlob*>or even vector<shared_ptr<UglyBlob> >, again - list will lag behind.

尽管如此，如果您切换到vector<UglyBlob*>甚至vector<shared_ptr<UglyBlob> >，再次 - list 将落后。

So, access pattern, target element count etc. still affects the comparison, but in my view - the elements size - cost of copying etc.

因此，访问模式、目标元素计数等仍然会影响比较，但在我看来 - 元素大小 - 复制成本等。

回答by UncleBens

One special capability of std::list is splicing (linking or moving part of or a whole list into a different list).

std::list 的一项特殊功能是拼接（将部分或整个列表链接或移动到不同的列表中）。

Or perhaps if your contents are very expensive to copy. In such a case it might be cheaper, for example, to sort the collection with a list.

或者，如果您的内容复制起来非常昂贵。在这种情况下，例如，使用列表对集合进行排序可能会更便宜。

Also note that if the collection is small (and the contents are not particularly expensive to copy), a vector might still outperform a list, even if you insert and erase anywhere. A list allocates each node individually, and that might be much more costly than moving a few simple objects around.

另请注意，如果集合很小（并且复制内容不是特别昂贵），即使您在任何地方插入和擦除，向量仍可能优于列表。一个列表单独分配每个节点，这可能比移动几个简单的对象要昂贵得多。

I don't think there are very hard rules. It depends on what you mostly want to do with the container, as well as on how large you expect the container to be and the contained type. A vector generally trumps a list, because it allocates its contents as a single contiguous block (it is basically a dynamically allocated array, and in most circumstances an array is the most efficient way to hold a bunch of things).

我不认为有很硬的规则。这取决于您最想对容器做什么，以及您期望容器的大小和包含的类型。向量通常胜过列表，因为它将其内容分配为单个连续块（它基本上是一个动态分配的数组，在大多数情况下，数组是保存一堆东西的最有效方式）。

回答by jokoon

Well the students of my class seems quite unable to explain to me when it is more effective to use vectors, but they look quite happy when advising me to use lists.

好吧，我班的学生似乎无法向我解释什么时候使用向量更有效，但是当他们建议我使用列表时，他们看起来很高兴。

This is how I understand it

我是这样理解的

Lists: Each item contains an address to the next or previous element, so with this feature, you can randomize the items, even if they aren't sorted, the order won't change: it's efficient if you memory is fragmented. But it also has an other very big advantage: you can easily insert/remove items, because the only thing you need to do is change some pointers. Drawback: To read a random single item, you have to jump from one item to another until you find the correct address.

列表：每个项目都包含一个指向下一个或上一个元素的地址，因此使用此功能，您可以将项目随机化，即使它们没有排序，顺序也不会改变：如果您的内存碎片化，这很有效。但它还有另一个非常大的优势：您可以轻松插入/删除项目，因为您唯一需要做的就是更改一些指针。缺点：要读取随机单个项目，您必须从一个项目跳到另一个项目，直到找到正确的地址。

Vectors: When using vectors, the memory is much more organized like regular arrays: each n-th items is stored just after (n-1)th item and before (n+1)th item. Why is it better than list ? Because it allow fast random access. Here is how: if you know the size of an item in a vector, and if they are contiguous in memory, you can easily predict where the n-th item is; you don't have to browse all the item of a list to read the one you want, with vector, you directly read it, with a list you can't. On the other hand, modify the vector array or change a value is much more slow.

向量：使用向量时，内存组织得更像常规数组：每个第 n 项都存储在第 (n-1) 项之后和第 (n+1) 项之前。为什么它比 list 更好？因为它允许快速随机访问。方法如下：如果您知道向量中某项的大小，并且它们在内存中是连续的，则可以轻松预测第 n 项的位置；您不必浏览列表的所有项目来阅读您想要的内容，使用矢量，您可以直接阅读它，而使用列表则不能。另一方面，修改向量数组或更改值要慢得多。

Lists are more appropriate to keep track of objects which can be added/removed in memory. Vectors are more appropriate when you want to access an element from a big quantity of single items.

列表更适合跟踪可以在内存中添加/删除的对象。当您想从大量单个项目中访问一个元素时，向量更合适。

I don't know how lists are optimized, but you have to know that if you want fast read access, you should use vectors, because how good the STL fasten lists, it won't be as fast in read-access than vector.

我不知道列表是如何优化的，但你必须知道，如果你想要快速读取访问，你应该使用向量，因为 STL 固定列表有多好，它的读取访问速度不会比向量快。

回答by f4.

Basically a vector is an array with automatic memory management. The data is contiguous in memory. Trying to insert data in the middle is a costly operation.

基本上，向量是一个具有自动内存管理功能的数组。数据在内存中是连续的。尝试在中间插入数据是一项代价高昂的操作。

In a list the data is stored in unrelated memory locations. Inserting in the middle doesn't involve copying some of the data to make room for the new one.

在列表中，数据存储在不相关的内存位置。在中间插入并不涉及复制一些数据来为新数据腾出空间。

To answer more specifically your question I'll quote this page

为了更具体地回答您的问题，我将引用此页面

vectors are generally the most efficient in time for accessing elements and to add or remove elements from the end of the sequence. For operations that involve inserting or removing elements at positions other than the end, they perform worse than deques and lists, and have less consistent iterators and references than lists.

向量通常是访问元素以及从序列末尾添加或删除元素的最有效时间。对于涉及在末尾以外的位置插入或删除元素的操作，它们的性能比双端队列和列表差，并且迭代器和引用的一致性不如列表。

回答by dirkgently

Any time you cannot have iterators invalidated.

任何时候都不能让迭代器失效。

回答by AraK

When you have a lot of insertion or deletion in the middle of the sequence. e.g. a memory manager.

当序列中间有很多插入或删除时。例如内存管理器。

回答by Potatoswatter

When you want to move objects between containers, you can use list::splice.

当您想在容器之间移动对象时，可以使用list::splice.

For example, a graph partitioning algorithm may have a constant number of objects recursively divided among an increasing number of containers. The objects should be initialized once and always remain at the same locations in memory. It's much faster to rearrange them by relinking than by reallocating.

例如，图分区算法可能具有在数量不断增加的容器中递归划分的恒定数量的对象。对象应该被初始化一次并且始终保持在内存中的相同位置。通过重新链接重新排列它们比重新分配要快得多。

Edit:as libraries prepare to implement C++0x, the general case of splicing a subsequence into a list is becoming linear complexity with the length of the sequence. This is because splice(now) needs to iterate over the sequence to count the number of elements in it. (Because the list needs to record its size.) Simply counting and re-linking the list is still faster than any alternative, and splicing an entire list or a single element are special cases with constant complexity. But, if you have long sequences to splice, you might have to dig around for a better, old-fashioned, non-compliant container.

编辑：当库准备实现 C++0x 时，将子序列拼接成列表的一般情况随着序列的长度变得线性复杂。这是因为splice（现在）需要遍历序列以计算其中的元素数量。（因为列表需要记录它的大小。）简单地计数和重新链接列表仍然比任何替代方法都快，并且拼接整个列表或单个元素是具有恒定复杂性的特殊情况。但是，如果您有很长的序列要拼接，您可能不得不四处寻找更好的、老式的、不合规的容器。