C++ std::vector 与 std::list 与 std::slist 的相对性能？

Relative performance of std::vector vs. std::list vs. std::slist?

提问by An???drew

For a simple linked list in which random access to list elements is not a requirement, are there any significant advantages (performance or otherwise) to using std::listinstead of std::vector? If backwards traversal is required, would it be more efficient to use std::slistand reverse()the list prior to iterating over its elements?

对于不需要随机访问列表元素的简单链表，使用std::list而不是std::vector? 如果需要向后遍历，在迭代其元素之前使用std::slist和reverse()列表会更有效吗？

回答by Motti

As usual the best answer to performance questions is to profileboth implementations for your use case and see which is faster.

像往常一样，性能问题的最佳答案是为您的用例分析两种实现，看看哪个更快。

In general if you have insertions into the data-structure (other than at the end) then vectormay be slower, otherwise in most cases vectoris expected to perform better than listif only for data locality issues, this means that if two elements that are adjacent in the data-set are adjacent in memory then the next element will already be in the processor's cache and will not have to page fault the memory into the cache.

一般来说，如果您插入数据结构（而不​​是在最后），那么vector可能会更慢，否则在大多数情况下vector，预计会比list仅用于数据局部性问题时表现更好，这意味着如果两个元素在数据集在内存中是相邻的，那么下一个元素将已经在处理器的缓存中，并且不必将内存分页错误到缓存中。

Also keep in mind that the space overhead for a vectoris constant (3 pointers) while the space overhead for a listis paid for each element, this also reduces the number of full elements (data plus overhead) that can reside in the cache at any one time.

还要记住，a 的空间开销vector是恒定的（3 个指针），而 a 的空间开销list是为每个元素支付的，这也减少了可以驻留在缓存中的完整元素（数据加上开销）的数量时间。

回答by Sam

Default data structure to think of in C++ is the Vector.

在 C++ 中要考虑的默认数据结构是Vector。

Consider the following points...

考虑以下几点...

1] Traversal:
List nodes are scattered everywhere in memory and hence list traversal leads to cache misses. But traversal of vectors is smooth.

1] 遍历：
列表节点分散在内存中的任何地方，因此列表遍历会导致缓存未命中。但是向量的遍历是平滑的。

2] Insertion and Deletion:
Average 50% of elements must be shifted when you do that to a Vector but caches are very good at that! But, with lists, you need to traverseto the point of insertion/deletion...so again... cache misses! And surprisingly vectors win this case as well!

2] 插入和删除：
平均 50% 的元素必须在您对 Vector 执行此操作时进行移动，但缓存非常擅长！但是，对于列表，您需要遍历到插入/删除的点......所以再次......缓存未命中！令人惊讶的是，向量也赢得了这个案例！

3] Storage:
When you use lists, there are 2 pointers per elements(forward & backward) so a List is much bigger than a Vector! Vectors need just a little more memory than the actual elements need.

Yout should have a reason not to use a vector.

3] 存储：
当您使用列表时，每个元素有 2 个指针（向前和向后），因此列表比向量大得多！向量只需要比实际元素需要的内存多一点。

你应该有理由不使用向量。

---

---

参考：


我在 Bjarne Stroustrup 勋爵的谈话中了解到这一点：https://youtu.be/0iWb_qi2-uI?t=2680https://youtu.be/0iWb_qi2-uI?t=2680

回答by gbjbaanb

Simply no. List has advantages over Vector, but sequential access is not one of them - if that's all you're doing, then a vector is better.

根本没有。List 比 Vector 有优势，但顺序访问不是其中之一——如果这就是你所做的，那么 vector 更好。

However.. a vector is more expensive to add additional elements than a list, especially if you're inserting in the middle.

然而..向量比列表更昂贵添加额外的元素，特别是如果你在中间插入。

Understand how these collections are implemented: a vector is a sequential array of data, a list is an element that contains the data and pointers to the next elements. Once you understand that, you'll understand why lists are good for inserts, and bad for random access.

了解这些集合是如何实现的：向量是数据的顺序数组，列表是包含数据和指向下一个元素的指针的元素。一旦你理解了这一点，你就会明白为什么列表对插入有利，而对随机访问不利。

(so, reverse iteration of a vector is exactly the same as for forward iteration - the iterator just subtracts the size of the data items each time, the list still has to jump to the next item via the pointer)

（因此，向量的反向迭代与前向迭代完全相同——迭代器每次只减去数据项的大小，列表仍然必须通过指针跳转到下一项）

回答by janm

If you need backwards traversal an slist is unlikely to be the datastructure for you.

如果您需要向后遍历，slist 不太可能是适合您的数据结构。

A conventional (doubly) linked list gives you constant insertion and deletion time anywhere in the list; a vector only gives amortised constant time insertion and deletion at the end of the list. For a vector insertion and deletion time is linear anywhere other than the end. This isn't the whole story; there are also constant factors. A vector is a more simple datastructure that has advantages and disadvantages depending on the context.

传统的（双向）链表为您提供了在列表中任意位置的恒定插入和删除时间；向量仅在列表末尾给出摊销的常量时间插入和删除。对于一个向量，插入和删除时间在除末尾之外的任何地方都是线性的。这不是故事的全部；还有一些不变的因素。向量是一种更简单的数据结构，其优缺点取决于上下文。

The best way to understand this is to understand how they are implemented. A linked list has a next and a previous pointer for each element. A vector has an array of elements addressed by index. From this you can see that both can do efficient forwards and backwards traversal, while only a vector can provide efficient random access. You can also see that the memory overhead of a linked list is per element while for the vector it is constant. And you can also see why insertion time is different between the two structures.

理解这一点的最好方法是了解它们是如何实现的。链表的每个元素都有一个下一个指针和一个上一个指针。向量具有由索引寻址的元素数组。由此可以看出，两者都可以进行高效的向前和向后遍历，而只有向量才能提供高效的随机访问。您还可以看到，链表的内存开销是每个元素的，而向量则是常量。您还可以看到为什么两种结构之间的插入时间不同。

回答by metamorphosis

Some rigorous benchmarks on the topic: http://baptiste-wicht.com/posts/2012/12/cpp-benchmark-vector-list-deque.html

关于该主题的一些严格基准：http: //baptiste-wicht.com/posts/2012/12/cpp-benchmark-vector-list-deque.html

As has been noted by others, contiguous memory storage means std::vector is better for most things. There is virtually no good reason to use std::list except for small amounts of data (where it can all fit in the cache) and/or where erasure and reinsertion are frequent. Complexity guarantees do Not relate to real-world performance because of the difference between cache and main memory speeds (200x) and how contiguous memory access affects cache usage. See Chandler Carruth (google) talk about the issue here: https://www.youtube.com/watch?v=fHNmRkzxHWs

正如其他人所指出的，连续内存存储意味着 std::vector 对大多数事情都更好。除了少量数据（可以全部放入缓存）和/或经常删除和重新插入的情况外，几乎没有充分的理由使用 std::list。由于缓存和主内存速度 (200x) 之间的差异以及连续内存访问如何影响缓存使用，复杂性保证与实际性能无关。请参阅 Chandler Carruth (google) 在此处讨论该问题：https: //www.youtube.com/watch?v=fHNmRkzxHWs

And Mike Acton's Data Oriented Design talk here: https://www.youtube.com/watch?v=rX0ItVEVjHc

Mike Acton 的面向数据设计的演讲在这里：https: //www.youtube.com/watch?v=rX0ItVEVjHc

回答by Martin York

See this question for details about the costs:
What are the complexity Guarantees of the standard containers

有关成本的详细信息，请参阅此问题：
标准容器的复杂性保证是什么

If you have an slist and you now want to traverse it in reverse order why not change the type to list everywhere?

如果您有一个 slist 并且现在想以相反的顺序遍历它，为什么不将类型更改为在任何地方列出？