您什么时候更喜欢使用 std::list而不是 std::vector？
我自己从未使用过 std::list 。我想知道当我们已经有了 std::vectorstd::vector 似乎是一个完美的选择！
所以我的问题是，
- 您到底什么时候更喜欢
std::list而不是std::vector？到底为什么？ - 您什么时候更喜欢
std::vector而不是std::list？为什么？
如果有性能方面的考虑，那么也请列出它们并附上详细的解释/信息。
如果可能的话，也引用一些参考文献来支持你的答案。
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!
So my question is
- When exactly do you prefer
std::listoverstd::vector? and why exactly? - When do you prefer
std::vectoroverstd::list? and why?
If there is performance consideration, then please list them too with detail explanation/information.
If possible, quote some references also, to support your answer.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（11）
当我需要在性能敏感区域使用顺序容器并且分析显示
std::list速度更快时。到目前为止，这种情况还没有发生在我身上。
（当我必须存储中间有大量插入/删除的非常大的对象时，我可能会想首先尝试
std::list。但是，在实践中，我从未遇到过这样的情况一个用例。）When I need a sequential container in a performance-sensitive area and profiling shows
std::listis faster.So far, this has never happened to me.
(I might be tempted to try
std::listfirst when I would have to store very big objects with lots of insertion/removal in the middle. However, in practice, I've never come across such a use-case.)列表更适合在中间的任何位置插入或删除，向量更适合在末尾插入。
向量也更适合访问元素。
这是它们实施方式的产物。
因此，如果集合变化很小（与访问相比）或者变化集中在最后，我会使用向量。
如果更改的数量很大（与访问相比）并且它们不在末尾，我会使用列表。
举例来说，在程序启动时读取集合并且几乎不对其进行更改（或者如果更改仅添加到末尾），这将是向量的良好候选者。
另一方面，对于特别受欢迎且善变的摇滚明星的电话簿应用程序，我会寻找一个列表。实际上，我正在寻找数据库连接，但这是我可以在短时间内想到的最好的例子:-)
至于参考文献，最新的 C++0x 草案（在这个答案时）部分说明了（ 23.3.4，列出）：
第 23.3.5 节（关于向量）：
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 :-)
As to references, the latest C++0x draft (at the time of this answer) states in part (23.3.4, lists):
Section 23.3.5 (on vectors):
在
std::list和std::vector之间进行选择时需要考虑一些权衡。另外，std::list 与连续内存无关，如果您无法承受迭代器失效或者需要在开始/中间/结束中插入分摊常量时间，那么它会非常有用。
There are a few trade-offs to be considered when choosing between
std::listandstd::vector.Also
std::listis not about contiguous memory, it can be quite useful if you can't afford iterator invalidation or if you need amortized constant time insertion in the begin/middle/end.我唯一（几次）喜欢
std::list是因为list::splice成员函数。如果您在列表内或列表之间的子范围内进行洗牌，则此操作可能比使用std::vector快得多。The only (few) times I preferred
std::listis due to thelist::splicemember function. If you are shuffling around subranges within a list or between lists this operation can be significantly faster than usingstd::vector.我不需要重复基础知识，但我通过艰难的方式学到的是，如果插入性能相关并且您有“大”对象，那么您应该真正考虑 std::list， 即使如果您只在末尾插入。 （嗯，一个列表，或者可能是一个智能指针/ ptr_vector 的向量。）
我们有一些用例，我们必须构建多个小 std::string 的先验未知大小的结构集合，并完全使用 std::vector杀死了插入性能并增加了不可忽略的内存开销。
在未知计数插入情况下，std::vector 的问题是：
这并不是为了抨击 std::vector，我仍然默认使用它——但知道你的数据结构会发生什么！
I don't need to repeat the basics, but what I learned the hard way is that if insertion performance is relevant and you have "large" objects, then you should really consider a std::list, even if you're only inserting at the end. (Well, a list or possibly a vector of smart pointer / ptr_vector.)
We had some use cases where we had to build up collections of a priori unknown size of structs of multiple small std::string and using a std::vector totally killed insertion performance and added a non-neglible memory overhead.
The problem with std::vector in the unknown count insert scenario is:
This is not to bash std::vector, I still use it by default -- but know what to expect of your datastructures!
除了其他答案之外，
基于节点的容器（
list/关联容器）可以提供强大的例外保证。
即使容器变异操作（例如插入）抛出
例外，所有指向元素的指针/引用/迭代器都保留
有效。
然而，线性内存（分段连续内存单元）容器可以
只提供基本保障。
当插入抛出异常时，即使插入实际上并未执行，
指针/引用/迭代器可能会失效
（尽管容器本身可以安全地销毁）。
In addition to other answers,
node-base containers(
list/associative containers) can provide strongexception guarantee.
Even if a container-mutating operation(for example insertion) throws an
exception, all the pointers/references/iterators to the elements remain
valid.
However, linear-memory(piecewise contiguous memory cell) containers can
provide only basic guarantee.
When an insertion throws, even if the insertion isn't actually executed,
pointers/references/iterators may be invalidated
(though the container itself can be destructed safely).
有人会说，可以说，您应该 永远不要再在代码中使用链表。 ；）
一个问题是向量具有更好的引用局部性，并且在许多情况下，由此产生的巨大性能增益将超过诸如删除之类的更（算法上）高效操作的优势并插入到一个链表中。
（有关此特定问题的更多讨论以及基准测试等，请参阅上面的博客文章。）
因此，std::vector 通常会胜过 std::list，即使您正在执行一定数量的操作，而列表会更自然（例如任意元素删除、在任意位置插入或拼接）。
但请注意，即使您确实执行了大量此类操作，最好将列表“托管”在 std::vector 的连续缓冲区中。
我在这篇博文中更详细地讨论了这一点，并提供了一些图表和代码示例： http:// upcoder.com/12/vector-hosted-lists/
在特定情况下，当您需要删除任意元素，但不需要在任意位置或拼接插入时，这是完整链表的一个很好的替代方案可以只是将条目标记为“死”并在迭代期间跳过这些死条目。
Some would say that you should, arguably, never ever ever use linked list in your code again. ;)
One issue is that vectors have much better locality of reference, and the big performance gains resulting from this will then, in many cases, outweigh the advantages of more (algorithmically) efficient operations for things like delete and insert in a linked list.
(See the blog post lined above for more discussion of this specific issue, with benchmarks and so on.)
So, often a std::vector will outperform std::list, even if you are doing a certain number of operations for which a list would be more natural (e.g. arbitrary element deletion, insert at arbitrary position, or splice).
But note that, even when you do do lots of these kinds of operations, you may be better off 'hosting' your list within the contiguous buffer of a std::vector.
I discuss this in more detail in this blog post, with some diagrams and code examples: http://upcoder.com/12/vector-hosted-lists/
In the specific case when you need to delete arbitrary elements, but don't need to insert at arbitrary positions or splice, a good alternative to a full blown linked list can be to just mark entries as 'dead' and skip over these dead entries during iteration.
当列表的失效语义和性能特征符合您的要求时，请使用列表。
列表可以在 O(1) 的任何位置插入/删除/拼接，并且这不会使任何迭代器失效。除了末尾之外，向量对于插入/擦除来说是 O(n) 的，即使这样也仅在大小 < 时才用于插入。容量;矢量无法拼接。性能比这更微妙，例如另一个答案中提到的缓存位置。
Use a list when its invalidation semantics and performance characteristics match your requirements.
List can insert/erase/splice anywhere in O(1), and this doesn't invalidate any iterators. Vector is O(n) for insert/erase except at the end, and even then only for insert if size < capacity; vector can't splice. Performance is even more subtle than this, with the caching locality mentioned in another answer, for example.
std::list几乎是我的首选，但vector不共享一个属性，那就是知道我指向list的指针将始终存在是有效的。因此，我可以使用它来包含单个区域中我需要的任何资产的所有实例，同时还借出对其他对象的引用以供使用。我能想到的最好的例子是一个图像加载器，它只在内存中保留一份像素副本，同时借出指向多个实体的指针，以便它们都可以从中绘制。所有向量都具有 O(1) 访问时间。虽然这听起来像是一笔巨大的资产，但实际上，除了从“第一个”到“最后一个”之外，我很少需要访问数据结构中的项目
std::listis my preferred almost exclusively for but one property thatvectordoes not share, and that's knowing my pointers into alistwill always be valid. Because of this, I can use this to contain all the instances of whatever asset I need in a single area, while also loaning out references to other objects to use. Best example I could think of would be an image loader that only keeps one copy of pixels in memory, while loaning out pointers to multiple entities so they can all draw from it.All
vectorhas going for it is O(1) access time. While that sounds like a huge asset, in practice I have very rarely ever needed to access items in a data structure outside stepping from 'first' to 'last'当您需要频繁修改除前面或后面以外的其他地方的序列时，可以使用 std::list 。与
std::list相比，std::vector中此类操作的开销很大。You use
std::listwhen you need to frequently modify the sequence in other places than the front or back. The overhead of such operations is large instd::vectorin comparisionstd::list.当您进行大量删除/插入操作时，应该使用列表。
如果元素的总大小变化不大并且进行一些交换，则可以使用向量。
You should use a list when you're doing a lot of deletions / insertions.
Vector can be used if the total size of elements does not change a lot, and if you do some swapping.