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

与往常一样,性能问题的最佳答案是 profile 这两种实现都适用于您的用例,看看哪种更快。

一般来说,如果你在数据结构中插入了内容(而不是在末尾),那么 vector 可能较慢,否则在大多数情况下 矢量 预计将比 list 如果只是为了 data locality issues ,这意味着,如果数据集中相邻的两个元素在内存中相邻,那么下一个元素将已经在处理器的缓存中,并且不必将内存分页到缓存中。

还要记住 矢量 是常量(3个指针),而 列表 为每个元素付费,这也减少了任何时候可以驻留在缓存中的完整元素(数据加开销)的数量。

C++中需要考虑的默认数据结构是 矢量 .

考虑以下几点。..

1] 横向:
列表节点分散在内存中的任何地方,因此列表遍历会导致 缓存未命中 但向量的遍历是平滑的。

2] 插入和删除:
当你对Vector执行此操作时,平均50%的元素必须被移动,但缓存在这方面非常擅长!但是,有了列表,你需要 穿过 插入/删除。.. 再次如此。..缓存未命中! 令人惊讶的是,矢量也赢得了这场官司!

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

Yout应该有理由不使用矢量。

简单地说,不是。列表比矢量有优势,但顺序访问不是其中之一——如果你只做这些,那么矢量更好。

然而。.向量添加额外元素的成本比列表更高,尤其是在插入在中间时。

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

(因此,向量的反向迭代与正向迭代完全相同——迭代器每次只减去数据项的大小,列表仍然必须通过指针跳到下一个项)

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

传统的(双)链表在列表中的任何位置都提供了恒定的插入和删除时间;向量仅在列表末尾提供摊销的恒定时间插入和删除。对于向量,插入和删除时间在除结束之外的任何地方都是线性的。这不是全部;还有一些恒定的因素。向量是一种更简单的数据结构,根据上下文的不同,它有优点也有缺点。

理解这一点的最好方法是了解它们是如何实施的。链表中每个元素都有一个下一个指针和一个上一个指针。向量有一个由索引寻址的元素数组。由此可以看出,两者都可以进行高效的前向和后向遍历,而只有向量可以提供高效的随机访问。您还可以看到,链表的内存开销是按元素计算的,而向量的内存开销则是恒定的。您还可以看到为什么两种结构之间的插入时间不同。

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

正如其他人所指出的,连续内存存储意味着std::vector对大多数事情都更好。除了少量数据(所有数据都可以放在缓存中)和/或擦除和重新插入频繁的情况外,几乎没有充分的理由使用std::list。 复杂性保证与实际性能无关,因为缓存和主内存速度(200倍)之间存在差异,以及连续内存访问如何影响缓存使用。请参阅Chandler Carruth(谷歌)在这里谈论这个问题: https://www.youtube.com/watch?v=fHNmRkzxHWs

Mike Acton的面向数据的设计演讲在这里: https://www.youtube.com/watch?v=rX0ItVEVjHc

有关成本的详细信息,请参阅此问题:
What are the complexity Guarantees of the standard containers

如果你有一个slist,现在想以相反的顺序遍历它,为什么不将类型更改为到处列出呢?