C++ 为什么我更喜欢使用 vector 来 deque

Why would I prefer using vector to deque

提问by Leon

Since

自从

1. they are both contiguous memory containers;
2. feature wise, deque has almost everything vector has but more, since it is more efficient to insert in the front.

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

Why whould anyone prefer std::vectorto std::deque?

为什么有人对子级宁愿std::vector到std::deque？

回答by phooji

Elements in a dequeare notcontiguous in memory; vectorelements are guaranteed to be. So if you need to interact with a plain C library that needs contiguous arrays, or if you care (a lot) about spatial locality, then you might prefer vector. In addition, since there is some extra bookkeeping, other ops are probably (slightly) more expensive than their equivalent vectoroperations. On the other hand, using many/large instances of vectormay lead to unnecessary heap fragmentation (slowing down calls to new).

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

Also, as pointed out elsewhere on StackOverflow, there is more good discussion here: http://www.gotw.ca/gotw/054.htm.

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

回答by CashCow

To know the difference one should know how dequeis generally implemented. Memory is allocated in blocks of equal sizes, and they are chained together (as an array or possibly a vector).

要知道差异，应该知道deque一般是如何实现的。内存以相同大小的块分配，并将它们链接在一起（作为数组或可能是向量）。

So to find the nth element, you find the appropriate block then access the element within it. This is constant time, because it is always exactly 2 lookups, but that is still more than the vector.

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

vectoralso works well with APIs that want a contiguous buffer because they are either C APIs or are more versatile in being able to take a pointer and a length. (Thus you can have a vector underneath or a regular array and call the API from your memory block).

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

Where dequehas its biggest advantages are:

deque它最大的优势在哪里：

1. When growing or shrinking the collection from either end
2. When you are dealing with very large collection sizes.
3. When dealing with bools and you really want bools rather than a bitset.

1. 从任一端增加或缩小集合时
2. 当您处理非常大的集合大小时。
3. 在处理 bool 并且您确实想要 bool 而不是 bitset 时。

The second of these is lesser known, but for very large collection sizes:

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

1. The cost of reallocation is large
2. The overhead of having to find a contiguous memory block is restrictive, so you can run out of memory faster.

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

When I was dealing with large collections in the past and moved from a contiguous model to a block model, we were able to store about 5 times as large a collection before we ran out of memory in a 32-bit system. This is partly because, when re-allocating, it actually needed to store the old block as well as the new one before it copied the elements over.

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

Having said all this, you can get into trouble with std::dequeon systems that use "optimistic" memory allocation. Whilst its attempts to request a large buffer size for a reallocation of a vectorwill probably get rejected at some point with a bad_alloc, the optimistic nature of the allocator is likely to always grant the request for the smaller buffer requested by a dequeand that is likely to cause the operating system to kill a process to try to acquire some memory. Whichever one it picks might not be too pleasant.

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

The workarounds in such a case are either setting system-level flags to override optimistic allocation (not always feasible) or managing the memory somewhat more manually, e.g. using your own allocator that checks for memory usage or similar. Obviously not ideal. (Which may answer your question as to prefer vector...)

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

回答by Howard Hinnant

I've implemented both vector and deque multiple times. deque is hugely more complicated from an implementation point of view. This complication translates to more code and more complex code. So you'll typically see a code size hit when you choose deque over vector. You may also experience a small speed hit if your code uses only the things the vector excels at (i.e. push_back).

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

If you need a double ended queue, deque is the clear winner. But if you're doing most of your inserts and erases at the back, vector is going to be the clear winner. When you're unsure, declare your container with a typedef (so it is easy to switch back and forth), and measure.

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

回答by Erik

std::dequedoesn't have guaranteed continuous memory - and it's often somewhat slower for indexed access. A deque is typically implemented as a "list of vector".

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

回答by patrickvacek

According to http://www.cplusplus.com/reference/stl/deque/, "unlike vectors, deques are not guaranteed to have all its elements in contiguous storage locations, eliminating thus the possibility of safe access through pointer arithmetics."

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

Deques are a bit more complicated, in part because they don't necessarily have a contiguous memory layout. If you need that feature, you should not use a deque.

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

(Previously, my answer brought up a lack of standardization (from the same source as above, "deques may be implemented by specific libraries in different ways"), but that actually applies to just about any standard library data type.)

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

回答by Sean

A deque is a sequence container which allows random access to it's elements but it is not guaranteed to have contiguous storage.

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

回答by Nick Westgate

You woudn't prefer vector to deque acording to these test results (with source).

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

Of course, you should test in your app/environment, but in summary:

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

• push_back is basically the same for all
• insert, erase in deque are much faster than list and marginally faster than vector

• push_back 基本上是一样的
• 在双端队列中插入、擦除比列表快得多，比向量略快

Some more musings, and a note to consider circular_buffer.

更多的思考，以及考虑circular_buffer的注意事项。

回答by BenGoldberg

On the one hand, vector is quite frequently just plain faster than deque. If you don't actually needall of the features of deque, use a vector.

一方面，vector 通常比 deque 快得多。如果您实际上不需要deque 的所有功能，请使用向量。

On the other hand, sometimes you doneed 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.

另一方面，有时您确实需要 vector 没有提供的功能，在这种情况下，您必须使用双端队列。例如，我挑战任何人尝试重写此代码，而不使用双端队列，并且不大量改变算法。

回答by Pierre

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

请注意，随着数组的增长，双端队列内存会重新分配。如果您有指向 deque 元素的指针，它们将无效。

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

此外，如果您删除一个元素，迭代器将变得无效（但不是“for(auto...)”）。

回答by George Gaál

I think that good idea to make perfomance test of each case. And make decision relying on this tests.

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

I'd prefer std::dequethan std::vectorin most cases.

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