STL容器 - 差异向量，列表和德克

Question

我应该使用deque而不是向量，如果我想推入也在容器的开始的元素？我应该什么时候使用列表，它有什么意义？

Answer 1

如果您需要在序列的开始和结束以及随机访问时进行有效的插入/移除，请使用deque;使用list如果您需要随机访问牺牲任何地方有效的插入。迭代器和对list元素的引用在容器几乎任何变化下都非常稳定，而deque具有非常特殊的迭代器和引用无效规则（因此请仔细检查它们）。

此外，list是一个基于节点的容器，而deque使用的是连续内存块，因此内存局部性可能具有无法通过渐近复杂度估计捕获的性能影响。

deque可以作为几乎所有地方的vector的替代品，并且应该可能被认为是C++中的“默认”容器（由于其更灵活的内存要求）;选择vector的唯一原因是您必须保证序列的连续内存布局。

Answer 2

deque和vector提供随机存取，list只提供线性存取。所以如果你需要做容器[我]，那就排除list。另一方面，您可以有效地在list的任何位置插入和移除项目，并且vector和deque中间的操作速度较慢。

deque和vector非常相似，基本上可以互换大多数用途。只有两个区别值得一提。首先，vector只能在最后有效地添加新项目，而deque可以有效地在任一端添加项目。那么为什么你会使用vector呢？与deque不同，vector保证所有项目都将存储在连续的内存位置，这使得在某些情况下可以更快地迭代它们。