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

2022-01-24 00:00:00 containers c++ stl

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

I've never used std::list<T> myself. I was wondering when people use it when we already have std::vector<T> which is just like arrays with contiguous memory. std::vector seems like a perfect choice when we need sequential container!

所以我的问题是

  • 您究竟是什么时候更喜欢 std::list 而不是std::vector?为什么?
  • 您什么时候更喜欢 std::vector 而不是std::list?为什么?
  • When exactly do you prefer std::list over std::vector? and why exactly?
  • When do you prefer std::vector over std::list? and why?

如果有性能方面的考虑，请也列出它们并附上详细的解释/信息.

If there is performance consideration, then please list them too with detail explanation/information.

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

推荐答案

列表更适合在中间插入或删除，向量更适合在末尾插入.

Lists are better for inserting or deleting anywhere in the middle, vectors are better for inserting at the end.

向量也更适合访问元素.

Vectors are also better for accessing elements.

这是它们实现方式的产物.

This is an artefact of the way they're implemented.

所以，如果一个集合变化很小(与访问相比)或者变化集中在最后，我会使用向量.

So, if a collection changes very little (compared to accesses) or the changes are concentrated at the end, I'd use a vector.

如果更改的数量很大(与访问相比)并且它们不在末尾，我会使用列表.

If the number of changes is substantial (compared to accesses) and they're not at the ends, I'd use a list.

例如，在程序启动时读入一个集合并且几乎不会更改它(或者如果更改只是添加到末尾)，这将是一个很好的向量候选者.

By way of example, reading in a collection at program start-up and hardly ever changing it (or if the changes are only adding to the end), this would be a good candidate for a vector.

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

On the other hand, a phone book application for a particularly popular and fickle rock star, I'd be looking towards a list. Actually I'd be looking toward a database connection but that was the best example I could come up with at short notice :-)

至于参考资料，最新的 C++0x 草案(在此答案时)部分说明(23.3.4，列表):

As to references, the latest C++0x draft (at the time of this answer) states in part (23.3.4, lists):

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

A list is a sequence container that supports bidirectional iterators and allows constant time insert and erase operations anywhere within the sequence, with storage management handled automatically. Unlike vectors and deques, fast random access to list elements is not supported.

第 23.3.5 节(关于向量):

Section 23.3.5 (on vectors):

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

A vector is a sequence container that supports random access iterators. In addition, it supports (amortized) constant time insert and erase operations at the end; insert and erase in the middle take linear time.

相关文章