89

自从

  1. 它们都是连续的内存容器；
  2. 功能方面，deque 几乎拥有 vector 的所有功能，但更多，因为插入到前面更有效。

为什么有人更std::vector喜欢std::deque？

4

10 回答 10

122

a 中的元素在内存deque中不连续；vector元素是保证的。因此，如果您需要与需要连续数组的普通 C 库进行交互，或者如果您（非常关心）空间局部性，那么您可能更喜欢vector. 此外，由于有一些额外的簿记，其他操作可能（稍微）比同等vector操作更昂贵。另一方面，使用许多/大型实例vector可能会导致不必要的堆碎片（减慢对 的调用new）。

此外，正如StackOverflow 其他地方所指出的，这里有更多好的讨论：http ://www.gotw.ca/gotw/054.htm 。

于 2011-03-17T21:03:29.073 回答
40

要知道区别，应该知道deque通常是如何实现的。内存分配在大小相等的块中，并且它们链接在一起（作为数组或可能的向量）。

因此，要找到第 n 个元素，您需要找到适当的块，然后访问其中的元素。这是一个常数时间，因为它总是恰好 2 次查找，但这仍然比向量多。

vector也适用于需要连续缓冲区的 API，因为它们要么是 C API，要么在能够获取指针和长度方面更通用。（因此，您可以在下面有一个向量或一个常规数组，并从您的内存块调用 API）。

哪里deque有它最大的优点是：

  1. 从任一端扩大或缩小集合时
  2. 当您处理非常大的集合大小时。
  3. 在处理 bool 时，你真的想要 bool 而不是 bitset。

其中第二个鲜为人知，但对于非常大的集合大小：

  1. 重新分配的成本很大
  2. 必须找到一个连续的内存块的开销是有限的，因此您可以更快地耗尽内存。

当我过去处理大型集合并从连续模型转移到块模型时，在 32 位系统中内存不足之前，我们能够存储大约 5 倍大的集合。这部分是因为在重新分配时，它实际上需要在复制元素之前存储旧块以及新块。

std::deque说了这么多，您可能会在使用“乐观”内存分配的系统上遇到麻烦。虽然它为重新分配 a 请求较大缓冲区大小的尝试vector可能会在某个时候被 a 拒绝，bad_alloc但分配器的乐观性质可能总是允许 a 请求的较小缓冲区的请求，deque这可能会导致操作系统杀死一个进程以尝试获取一些内存。无论它选择哪一个都可能不太令人愉快。

在这种情况下，解决方法是设置系统级标志以覆盖乐观分配（并不总是可行）或更多地手动管理内存，例如使用您自己的分配器来检查内存使用情况或类似情况。显然不理想。（这可能会回答您更喜欢矢量的问题......）

于 2013-01-15T10:30:13.623 回答
33

我已经多次实现了向量和双端队列。从实现的角度来看，双端队列要复杂得多。这种复杂性转化为更多代码和更复杂的代码。因此，当您选择双端队列而不是向量时，通常会看到代码大小受到影响。如果您的代码仅使用向量擅长的东西（即 push_back），您也可能会遇到小速度影响。

如果你需要一个双端队列，deque 是明显的赢家。但是，如果您在后面进行大部分插入和擦除操作，vector 将是明显的赢家。当你不确定时，用 typedef 声明你的容器（这样很容易来回切换），然后测量。

于 2011-03-17T22:06:09.890 回答
5

std::deque不能保证连续的内存 - 索引访问通常会慢一些。双端队列通常被实现为“向量列表”。

于 2011-03-17T21:02:14.027 回答
2

根据http://www.cplusplus.com/reference/stl/deque/，“与向量不同，双端队列不能保证其所有元素都位于连续的存储位置，从而消除了通过指针算法进行安全访问的可能性。”

双端队列稍微复杂一些，部分原因是它们不一定具有连续的内存布局。如果您需要该功能，则不应使用双端队列。

（以前，我的回答导致缺乏标准化（来自与上述相同的来源，“双端队列可能由特定库以不同的方式实现”），但这实际上适用于几乎任何标准库数据类型。）

于 2011-03-17T21:04:12.033 回答
0

双端队列是一个序列容器，它允许随机访问它的元素，但不保证具有连续存储。

于 2011-03-17T21:02:24.877 回答
0

我认为对每个案例进行性能测试是个好主意。并根据此测试做出决定。

我宁愿std::deque比std::vector大多数情况下。

于 2011-06-10T00:12:10.563 回答
0

根据这些测试结果（带有源代码），您不会更喜欢向量而不是双端队列。

当然，您应该在您的应用程序/环境中进行测试，但总而言之：

  • push_back 对所有人基本相同
  • 在双端队列中插入，擦除比列表快得多，比向量快一点

更多的思考，以及要考虑循环缓冲区的注释。

于 2016-05-05T03:53:49.810 回答
0

一方面，vector 经常比 deque 快。如果您实际上并不需要双端队列的所有功能，请使用向量。

On the other hand, sometimes you do need features which vector does not give you, in which case you must use a deque. For example, I challenge anyone to attempt to rewrite this code, without using a deque, and without enormously altering the algorithm.

于 2016-12-17T19:40:56.133 回答
0

Note that vector memory is re-allocated as the array grows. If you have pointers to vector elements, they will become invalid.

Also, if you erase an element, iterators become invalid (but not "for(auto...)").

Edit: changed 'deque' to 'vector'

于 2020-03-29T16:56:45.290 回答