10

它们都具有 O(1) 的访问复杂度和 O(n) 的随机插入/删除复杂度。但是vector由于重新分配和复制而在扩展时成本更高，而deque则没有这个问题。

看起来deque的性能更好，但是为什么大多数人使用vector而不是deque呢？

4

5 回答 5

9 
why most people use vector instead of deque?

因为这是他们被教导的。

vector并deque服务于略有不同的目的。如果您需要的话，它们都可以用作简单的对象容器。在学习 C++ 编程时，这就是大多数人所需要的——一个可以放入、取出和走过的桶。

当 StackOverflow 被问到“我应该默认使用哪个容器”之类的问题时，答案几乎都是vector. 这个问题通常是从学习 C++ 编程的上下文中提出的，并且在程序员提出这样的问题时，他们还不知道他们不知道什么。还有很多他们还不知道。因此，我们（StackOverflow）需要一个容器，它几乎可以满足所有需求，无论好坏，几乎可以在任何情况下使用，并且不需要程序员在找到近似正确答案之前提出所有正确的问题。此外，该标准特别推荐使用vector. vector并非最适合所有用途，实际上deque比vector对于许多常见用途——但对于学习程序员来说，我们应该从标准对新手 C++ 程序员的建议中有所不同，这并没有那么好，所以 StackOverflow 登陆vector.

在学习了语法的基础知识以及（容我们说）C++ 编程背后的策略之后，程序员分成了两个分支：喜欢学习更多并编写更好的程序的人，以及不喜欢学习的人。没有的人会永远坚持vector下去。我想很多程序员都属于这个阵营。

试图超越这个阶段的少数程序员开始提出其他问题——就像你在这里提出的问题。他们知道有很多他们还不知道，他们想开始发现这些东西是什么。他们会很快（或较慢地）发现，在vector和之间进行选择时deque，他们之前没有想到要问的一些问题是：

  1. 我需要内存是连续的吗？
  2. 我需要避免大量的重新分配吗？
  3. 插入后是否需要保留有效的迭代器？
  4. 我是否需要我的收藏与一些古老的类 C 函数兼容？

然后他们真正开始思考他们正在编写的代码，发现更多他们不知道的东西，然后节拍继续……

于 2013-09-26T15:04:36.597 回答
8

从 C++ 标准第 23.1.1 节：

vector is the type of sequence that should be used by default... deque is 
the data structure of choice when most insertions and deletions take place
at the beginning or at the end of the sequence.

然而，也有一些相反的论点。

从理论上讲，它vector至少与deque提供其功能的子集一样有效。如果您的任务只需要 vector 的接口提供的内容，则更喜欢 vector - 它不会比双端队列更糟糕。

于 2013-09-26T14:50:40.723 回答
6

但是由于重新分配和复制，向量在扩展时成本更高

虽然确实vector有时必须随着数组的增长重新分配它的数组，但它会呈指数增长，因此摊销复杂度仍然是 O(1)。通常，您可以通过明智地使用reserve().

似乎 deque 有更好的性能

性能有很多方面；所花费的时间push_back只是一个。在某些应用程序中，容器可能很少被修改，或者在启动时填充然后从不修改。在这种情况下，迭代和访问速度可能更重要。

vector是最简单的容器：一个连续的数组。这意味着可以通过简单的指针算法来实现迭代和随机访问，并且访问元素可以像取消引用指针一样快。

deque有进一步的要求：它不能移动元素。这意味着一个典型的实现需要一个额外的间接级别——它通常被实现为一个指向数组的指针数组。这意味着元素访问需要取消引用两个指针，这将比一个慢。

当然，速度通常不是关键问题，您根据容器的行为属性而不是性能来选择容器。您可以选择vector是否需要元素是连续的，或者使用基于指针和数组的 API。您可以选择deque或者list如果您想要保证元素不会移动，那么您可以存储指向它们的指针。

于 2013-09-26T15:02:57.853 回答
2

对于 cplusplus ：

因此，它们提供了与向量相似的功能，但在序列的开头也可以有效地插入和删除元素，而不仅仅是在序列的结尾。但是，与向量不同，双端队列不能保证将其所有元素存储在连续的存储位置，因此不允许通过偏移指向元素的指针进行直接访问。

于 2013-09-26T14:53:01.163 回答
1

就个人而言，我更喜欢使用deque（我总是最终宠坏自己并且push_front出于某种原因不得不使用），但vector确实有其用途/差异，主要是：

vector具有连续的内存，而 adeque通过页/块分配。请注意，页面/块相当有用：在容器前面的恒定时间插入/擦除。同样典型的是，将一大块内存分成一系列较小的块比单个内存块更有效。

您也可以争辩说，因为deque“缺少”大小保留方法 ( capacity/ reserve)，您不必担心。

我强烈建议您阅读萨特斯关于该主题的 GotW。

于 2013-09-26T14:53:18.710 回答