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

Question

对于一个不需要随机访问列表元素的简单链表，使用 std::list 代替 std 是否有任何显着优势(性能或其他方面): : vector ?如果需要向后遍历，在遍历其元素之前使用 std::slist 和 reverse() 列表会更有效吗？

Answer 1

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

一般来说，如果你有插入到数据结构中(除了最后)，那么 vector 可能会更慢，否则在大多数情况下 vector 预计会执行如果仅适用于 data locality issues，则优于 list ，这意味着如果数据集中相邻的两个元素在内存中是相邻的，那么下一个元素将已经在处理器的缓存中，并且不必将内存分页到缓存中。

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