STL容器 - vector、list和deque的区别

Question

如果我想在容器的开头和末尾都添加元素，那么是不是应该使用双端队列（deque）而不是向量（vector）？什么时候该使用列表（list），它的优点是什么？

- fex

Answer 1

如果你需要在序列的开头和结尾高效插入/删除以及随机访问，请使用deque; 如果你需要在任何地方高效插入，但牺牲了随机访问，则使用list。在几乎任何情况下，对list元素的迭代器和引用都非常稳定，容器的任何变异都不会导致它们失效，而deque有非常特殊的迭代器和引用失效规则（因此请仔细检查它们）。

另外，list是一个基于节点的容器，而deque使用连续内存块，因此内存局部性可能会对性能产生影响，这是渐进复杂度估计无法捕捉的。

deque几乎可以替代vector，并且应该被认为是C++中的“默认”容器（由于其更灵活的内存需求）; 仅在必须拥有保证的连续内存布局时，才应优先选择vector。

- Kerrek SB

---

在我的经验中，vector 几乎总是比 deque 更高效。 - Don Reba

这取决于使用情况，性能分析是唯一的答案。如果要分配一个巨大的范围，向量可能会有困难，而deque可以分配新的块而无需移动旧的块。当然，这也取决于你在做什么。 - Kerrek SB

@KerrekSB，你能提供一些性能分析数据吗？这将对决定性能非常有帮助。 - Sisir

@Sisir：这不是一个很好的答案。虽然“deque”原则上是一个好主意，但有许多糟糕的实现，使用太小的块大小，因此有效地变成了链接列表。因此，您肯定需要进行比较和分析；对于许多“典型”的容器大小，即使在除末尾插入之外的插入中，“std::vector”通常表现更好。 - Kerrek SB

Answer 2

deque 和 vector 可以提供随机访问，而 list 只能提供线性访问。因此，如果你需要使用 container[i] 这种随机访问的方式，那么就不能选择 list 了。另一方面，你可以在一个 list 中高效地插入和删除元素，而在 vector 和 deque 中间插入或删除元素的操作则较慢。

deque 和 vector 非常相似，在大多数情况下基本上可以互换使用。只有两个值得注意的区别。首先，vector 只能在末尾高效地添加新项，而 deque 可以在两端高效地添加项。那么为什么还要使用 vector 呢？与 deque 不同，vector 保证所有项都存储在连续的内存位置中，在某些情况下可以更快地迭代它们。

- deong

---

你能提供一些性能分析数据吗？这将对决定性能非常有帮助。 - Sisir