std :: vector与std :: list与std :: slist的相对性能?

对于一个简单的链表来说,对列表元素的随机访问是不需要的,使用std::list而不是std::vector有什么显着的优点(性能或其他) 如果需要向后遍历,在迭代元素之前使用std::slistreverse()会更有效率吗?

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

一般情况下,如果插入到数据结构中(除了最后),那么vector可能会变慢,否则在大多数情况下,如果只有数据局部性问题 , vector才会比list执行得更好,这意味着如果两个元素在数据集中相邻的数据集在内存中是相邻的,那么下一个元素将已经在处理器的caching中,而不必将内存错误地分页到caching中。

还要记住, vector的空间开销是恒定的(3个指针),而list的空间开销是为每个元素支付的,这也减less了可以驻留在caching中的满元素的数量(数据加开销)任何一次。

在C ++中思考的缺省数据结构就是Vector

考虑以下几点…

1]遍历:
列表节点散布在内存中的任何地方,因此列表遍历导致caching未命中 。 但是vector的遍历是平滑的。

2]插入和删除:
平均50%的元素必须移动到一个Vector上,但caching非常好! 但是,使用列表,你需要遍历到插入/删除的点……所以再次…caching未命中! 而令人惊讶的是vector赢得这种情况!

3]储存:
当你使用列表时,每个元素有2个指针(向前和向后),所以List比Vector要大得多! 向量只需要比实际元素需要更多的内存。

Yout应该有一个不使用vector的理由。


参考:
我在一篇关于主Bjarne Stroustrup的演讲中学到了这一点: https ://youtu.be/0iWb_qi2-uI?t = 2680

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

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

了解这些集合是如何实现的:vector是一个连续的数据数组,列表是包含数据和指向下一个元素的指针的元素。 一旦你明白了,你就会明白为什么列表适合插入,而不适合随机存取。

(所以,向量的反向迭代与向前迭代完全相同 – 迭代器每次只减去数据项的大小,列表仍然需要通过指针跳到下一个项)

如果你需要向后遍历,slist不太可能成为你的数据结构。

一个传统的(双重)链表为您提供了不断的插入和删除时间在列表中的任何地方; 一个向量只能在列表的末尾给出分期固定的时间插入和删除。 对于vector插入和删除时间是线性的,除了结束之外的任何地方。 这不是全部的事情; 也有不变的因素。 vector是一个更简单的数据结构,根据上下文具有优点和缺点。

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

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

正如其他人所指出的,连续的内存存储意味着std :: vector对于大多数情况来说更好。 实际上没有什么好的理由使用std :: list,除了less量的数据(它们都可以放入caching)和/或擦除和重新插入频繁的地方。 由于caching和主内存速度(200x)之间的差异以及连续的内存访问如何影响caching使用情况,因此复杂性保证与实际性能无关。 请参阅Chandler Carruth(google)在这里讨论此问题: https : //www.youtube.com/watch?v = fHNmRkzxHWs

Mike Acton的面向数据的devise在这里讨论: https : //www.youtube.com/watch?v=rX0ItVEVjHc

有关费用的详细信息,请参阅此问题:
标准容器的复杂性保证是什么?

如果你有一个slist,而你现在想要以相反的顺序遍历它,为什么不改变types到处列表?