std :: vector相对于std :: list和std :: slist的相对性能？

问题描述

对于不需要随机访问列表元素的简单链表，是否使用 std :: list 有任何显着的优点（性能或其他方面） std :: vector ？如果需要向后遍历，使用 std :: slist 和 reverse（）

像往常一样，性能问题的最佳答案是这两种实现方式，看看哪个更快。

一般来说，如果你有数据结构的插入（除了结尾），那么向量较慢，否则在大多数情况下向量预期执行优于 list //en.wikipedia.org/wiki/Locality_of_reference\">数据位置问题，这意味着如果在数据集中相邻的两个元素在内存中相邻，则下一个元素将已经在处理器的缓存中

请记住，向量的空间开销是常量（3个指针），而为每个元素支付列表的空间开销，这也减少了可以驻留的完整元素（数据加开销）的数量在任何时候在缓存中。

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?

解决方案

As usual the best answer to performance questions is to profile both 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 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.

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.

这篇关于std :: vector相对于std :: list和std :: slist的相对性能？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！