STL容器-向量，列表和双端队列之间的区别 [英] STL Containers - difference between vector, list and deque

问题描述

如果我也想在容器的开头插入元素，是否应该使用双端队列而不是向量？我应该何时使用列表以及它的意义是什么？

Should I use deque instead of vector if i'd like to push elements also in the beginning of the container? When should I use list and what's the point of it?

推荐答案

使用双端队列如果您需要在序列的开头和结尾以及随机访问中进行有效的插入/移除；如果您需要在任何地方进行高效插入，而牺牲了随机访问权限，请使用 list 。在容器的几乎任何变化下，迭代器和对 list 元素的引用都非常稳定，而 deque 具有非常独特的迭代器和参考无效规则（请仔细检查它们）。

Use deque if you need efficient insertion/removal at the beginning and end of the sequence and random access; use list if you need efficient insertion anywhere, at the sacrifice of random access. Iterators and references to list elements are very stable under almost any mutation of the container, while deque has very peculiar iterator and reference invalidation rules (so check them out carefully).

此外， list 是基于节点的容器，而双端队列使用大块连续的内存，因此内存局部性可能会对性能产生影响，而渐进复杂性估计无法捕获这种情况。

Also, list is a node-based container, while a deque uses chunks of contiguous memory, so memory locality may have performance effects that cannot be captured by asymptotic complexity estimates.

deque 几乎可以替代 vector ，应该将其视为默认容器C ++（由于其更灵活的内存要求）；选择 vector 的唯一原因是必须确保序列的连续内存布局。

deque can serve as a replacement for vector almost everywhere and should probably have been considered the "default" container in C++ (on account of its more flexible memory requirements); the only reason to prefer vector is when you must have a guaranteed contiguous memory layout of your sequence.

这篇关于STL容器-向量，列表和双端队列之间的区别的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！