你什么时候喜欢使用std :: list <T>而不是std :: vector <T>？

Question

我从来没有用过std::list<T>自己.当我们已经拥有它时,我想知道人们何时使用它std::vector<T>就像具有连续内存的数组一样.std::vector当我们需要顺序容器时,它似乎是一个完美的选择

所以我的问题是

如果有性能考虑因素,请列出详细说明/信息.

如果可能,请引用一些参考资料,以支持您的答案.

Answer 1

sbi*_*sbi 29

所以我的问题是:当你到底喜欢 std::list过std::vector？

当我在性能敏感区域中需要顺序容器时,分析显示std::list更快.

到目前为止,这从未发生在我身上.

(std::list当我不得不在中间存放大量插入/移除的大型物体时,我可能会先尝试尝试.但是,在实践中,我从未遇到过这样的用例.)

+1"*当分析显示`std :: list`很快*"这是迄今为止最好的答案.数学和BigO表示法:**描述您的代码并了解机器的工作原理**,而不仅仅是*算法/数据结构的理论属性*. (4认同)

Answer 2

列表更适合插入或删除中间的任何位置,向量最好插入到最后.

向量也更适合访问元素.

这是他们实施方式的人工制品.

因此,如果集合变化很小(与访问相比)或者变化集中在最后,我会使用向量.

如果变化的数量很大(与访问相比)并且它们不在最后,我会使用一个列表.

举例来说,在程序启动时读取集合并且几乎不会更改它(或者如果更改是添加到结尾),这将是向量的良好候选.

另一方面,一个特别受欢迎和变化无常的摇滚明星的电话簿应用程序,我将寻找一个列表.实际上我正在寻找数据库连接,但这是我能在短时间内提出的最好的例子:-)

至于引用,最新的C++ 0x草案部分(23.3.4,列表)说明:

列表是一个序列容器,它支持双向迭代器,并允许在序列中的任何位置进行恒定时间插入和擦除操作,并自动处理存储管理.与矢量和deques不同,不支持对列表元素的快速随机访问.

第23.3.5节(关于向量):

向量是一个支持随机访问迭代器的序列容器.此外,它支持(摊销)最后的恒定时间插入和擦除操作; 在中间插入和擦除需要线性时间.

这在理论上是可以的.然而,在实践中,`std :: vector` __通常更快_,即使理论上`std :: list`应该表现得更好. (9认同)
@Nawaz:`std :: vector`在实践中更快,是当前处理器设计的工件.STL在90年代早期/中期被考虑过,当时可能并不那么明显.此外,两者都是传统的数据结构,任何容器库都应该提供.最后,总是存在大对象的用例.我从来没有碰到过这并不意味着它不存在. (3认同)

Answer 3

在std :: list和std :: vector之间进行选择时,需要考虑一些权衡因素.另外std :: list不是关于连续内存的,如果你无法承受迭代器失效或者你需要在begin/middle/end中分摊常量时间,它会非常有用.

Answer 4

我喜欢的唯一(几次)std::list是由于list::splice成员函数.如果您在列表中或列表之间的子范围内进行混洗,则此操作可能比使用快得多std::vector.