有没有理由使用std :: list？

Question

在阅读了这个问题并在此处查看了一些结果后,似乎应该完全避免使用C++中的列表.我总是期望链接列表是我只需要迭代所有内容的情况下的首选容器,因为插入是指针操作的问题,并且永远不需要重新分配.

显然,由于"缓存局部性",列表的迭代速度非常慢,因此必须使用更少的保留内存或更快的添加(从第二个链接看起来速度不是那么快)的任何好处似乎都不值得它.

话虽如此,当我应该,从性能的角度来看,使用std::list过std::deque或者,如果可能的话,std::vector？

另外,std::forward_list还会有很多缓存未命中？

Answer 1

从性能的角度来看,我应该何时使用 std::list

从性能的角度来看,很少.想到的唯一情况是,如果您有许多列表需要拆分并加入以形成其他列表; 链接列表可以在不分配内存或移动对象的情况下执行此操作.

list稳定性的真正好处是:元素不需要是可移动的,并且迭代器和引用永远不会失效,除非它们引用已被擦除的元素.

另外,std::forward_list还会有很多缓存未命中？

是; 它仍然是一个链表.

Answer 2

std::list 在一些极端情况下很有用.

但是,C++顺序容器的一般规则是"如果您的算法兼容,请使用std::vector.如果您的算法不兼容,请修改您的算法,以便您可以使用std::vector."

存在例外情况,这是尝试详尽列出std::list更好选择的原因:

1. 当你需要(A)插入容器的中间并且(B)你需要内存中的每个对象位置都是稳定的.通常可以通过包含指向元素的指针的非稳定容器来移除要求(B),因此这不是一个强有力的使用理由std::list.

2. 当您需要(A)在容器(B)中间插入或删除比您需要迭代容器更多的数量级.这也是一个极端的极端情况:为了找到要从中删除的元素list,通常需要迭代!

这导致

3. 你需要(A)在容器中间插入或删除,(B)所有其他元素的迭代器保持有效.这最终成为案例1和案例2的隐藏要求:当您没有持久迭代器时,迭代很难删除或插入,并且迭代器和对象的稳定性高度相关.

4. 最后的情况,是拼接的情况曾经是一个使用的理由std::list.

回到C++ 03,所有版本的std::list::splicecan(理论上)都可以在O(1)时间内完成.但是,O(n)操作splice所需的极其有效的形式size.C++ 11要求size在listO(1)上,所以splice极端的效率仅限于"拼接整个其他列表"和"自拼接子列表"的情况.在单个元素拼接的情况下,这只是插入和删除.在子范围拼接的情况下,代码现在必须访问拼接中的每个节点以便对它们进行计数以便维持size为O(1)(除了自拼接).

因此,如果您只进行整个list拼接或自列表子范围splice,则list可以比其他非列表容器更快地执行这些操作.

Answer 3

std::list可以提供的最大改进是当您将一个或多个元素从一个列表的中间移动到另一个列表中时.该splice操作非常有效,list同时它可能涉及随机访问容器中的项目的分配和移动,例如vector.也就是说,这很少出现,而且大部分时间vector都是您在性能和简单性方面最好的容器.

如果您怀疑容器选择存在性能问题,请始终对代码进行概要分析.

Answer 4

当您经常在容器中间添加/删除项目时,您选择std::list了std::deque和std::vector(以及其他连续的内存容器),另请参阅.