std::vector 与 std::list 与 std::slist 的相对性能?
对于不需要随机访问列表元素的简单链表，使用 std::list 代替 std 是否有任何显着优势(性能或其他)::vector?如果需要向后遍历，在遍历列表元素之前使用 std::slist 和 reverse() 会更有效吗?
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::list instead of std::vector? If backwards traversal is required, would it be more efficient to use std::slist and reverse() the list prior to iterating over its elements?
推荐答案
像往常一样，性能问题的最佳答案是 profile 适用于您的用例的两种实现，看看哪个更快.
As usual the best answer to performance questions is to profile both implementations for your use case and see which is faster.
一般来说，如果你有插入数据结构(不是在最后)那么 vector 可能会更慢，否则在大多数情况下 vector 预计会执行如果仅针对 数据局部性问题，则比 list 更好，这意味着如果数据集中相邻的两个元素在内存中相邻，那么下一个元素将已经在处理器的缓存中，并且不必将内存页错误到缓存中.
In general if you have insertions into the data-structure (other than at the end) then vector may be slower, otherwise in most cases vector is expected to perform better than list if 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 的空间开销是恒定的(3 个指针)，而 list 的空间开销是为每个元素支付的，这也减少了任意时刻可以驻留在缓存中的完整元素(数据加上开销)的数量.
Also keep in mind that the space overhead for a vector is constant (3 pointers) while the space overhead for a list is 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.
相关文章