std :: vector与std :: list与std :: slist的相对性能？
对于一个简单的链表来说，对列表元素的随机访问是不需要的，使用std::list而不是std::vector有什么显着的优点（性能或其他） 如果需要向后遍历，在迭代元素之前使用std::slist和reverse()会更有效率吗？
像往常一样，性能问题的最佳答案是为你的用例分析两个实现，看看哪个更快。
一般情况下，如果插入到数据结构中（除了最后），那么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到处列表？
