为什么我更喜欢使用向量而不是双端队列
因为：（
- 我推测）它们都是连续的内存容器；
- 在功能方面，双端队列几乎拥有向量所拥有的一切，但更多，因为在前面插入效率更高。
为什么有人会更喜欢 std::vector 而不是 std::deque？
Since:
- (I presume) they are both contiguous memory containers;
- feature wise, deque has almost everything vector has but more, since it is more efficient to insert in the front.
Why would anyone prefer std::vector to std::deque?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（8）
deque中的元素在内存中不连续；vector元素保证是。因此，如果您需要与需要连续数组的普通 C 库进行交互，或者您（非常）关心空间局部性，那么您可能更喜欢vector。此外，由于存在一些额外的簿记，其他操作可能比其等效的向量操作（稍微）昂贵。另一方面，使用许多/大型vector实例可能会导致不必要的堆碎片（减慢对new的调用）。另外，正如StackOverflow上的其他地方所指出的，这里有更多好的讨论：http://www.gotw.ca/gotw/054.htm 。
Elements in a
dequeare not contiguous 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 prefervector. In addition, since there is some extra bookkeeping, other ops are probably (slightly) more expensive than their equivalentvectoroperations. On the other hand, using many/large instances ofvectormay lead to unnecessary heap fragmentation (slowing down calls tonew).Also, as pointed out elsewhere on StackOverflow, there is more good discussion here: http://www.gotw.ca/gotw/054.htm .
要了解其中的区别，应该知道 deque 通常是如何实现的。内存被分配为大小相等的块，并且它们链接在一起（作为数组或可能是向量）。
因此，要找到第 n 个元素，您需要找到适当的块，然后访问其中的元素。这是常数时间，因为它总是恰好 2 次查找，但这仍然比向量多。
vector也适用于需要连续缓冲区的 API，因为它们要么是 C API，要么在能够获取指针和长度方面更加通用。 （因此你可以在下面有一个向量或一个常规数组，并从你的内存块调用 API）。deque最大的优点是：其中第二个不太为人所知，但对于非常大的集合大小：
当我过去处理大型集合并从连续模型转移到块模型时，在 32 位系统中内存耗尽之前，我们能够存储大约 5 倍大的集合。部分原因是，在重新分配时，它实际上需要在复制元素之前存储旧块和新块。
说了这么多，在使用“乐观”内存分配的系统上，您可能会遇到 std::deque 的麻烦。虽然它尝试请求大缓冲区大小以重新分配向量的尝试可能会在某些时候被
bad_alloc拒绝，但分配器的乐观本质可能总是会被拒绝。授予双端队列请求的较小缓冲区的请求，这可能会导致操作系统终止进程以尝试获取一些内存。无论它选择哪一个，都可能不太令人愉快。这种情况下的解决方法是设置系统级标志来覆盖乐观分配（并不总是可行），或者更手动地管理内存，例如使用您自己的分配器来检查内存使用情况或类似的情况。显然并不理想。 （这可能会回答你关于更喜欢矢量的问题......）
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).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.
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).Where
dequehas its biggest advantages are:The second of these is lesser known, but for very large collection sizes:
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.
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 avectorwill probably get rejected at some point with abad_alloc, the optimistic nature of the allocator is likely to always grant the request for the smaller buffer requested by adequeand 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.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...)
我已经多次实现了向量和双端队列。从实现的角度来看，双端队列要复杂得多。这种复杂性意味着更多的代码和更复杂的代码。因此，当您选择双端队列而不是向量时，通常会看到代码大小受到影响。如果您的代码仅使用向量擅长的功能（即push_back），您也可能会遇到轻微的速度影响。
如果您需要双端队列，双端队列显然是赢家。但如果您在后面进行大部分插入和擦除，则矢量将是明显的赢家。当您不确定时，请使用 typedef 声明您的容器（以便轻松来回切换），然后进行测量。
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).
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.
std::deque不保证连续内存 - 而且索引访问通常会慢一些。双端队列通常被实现为“向量列表”。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".根据 http://www.cplusplus.com/reference/stl/deque/ ，“与向量不同，双端队列不能保证其所有元素都位于连续的存储位置，从而消除了通过指针算术安全访问的可能性。”
双端队列稍微复杂一些，部分原因是它们不一定具有连续的内存布局。如果您需要该功能，则不应使用双端队列。
（之前，我的回答提出了标准化的缺乏（来自与上面相同的来源，“双端队列可以由特定库以不同的方式实现”），但这实际上适用于几乎任何标准库数据类型。）
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."
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.)
请注意，随着数组的增长，向量内存会重新分配。如果你有指向向量元素的指针，它们将变得无效。
另外，如果删除一个元素，迭代器就会变得无效（但“for(auto...)”则不会）。
编辑：将“双端队列”更改为“向量”
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'
双端队列是一个序列容器，允许随机访问其元素，但不保证具有连续的存储。
A deque is a sequence container which allows random access to it's elements but it is not guaranteed to have contiguous storage.
一方面，向量通常比双端队列快。如果您实际上并不需要双端队列的所有功能，请使用向量。
另一方面，有时您确实需要向量无法提供的功能，在这种情况下您必须使用双端队列。例如，我挑战任何人尝试重写此代码，而不使用双端队列，并且不使用极大地改变了算法。
On the one hand, vector is quite frequently just plain faster than deque. If you don't actually need all of the features of deque, use a vector.
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.