问为什么我更喜欢使用向量而不是deque？

EN

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

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

要了解其中的区别，应该知道deque通常是如何实现的。内存以相等大小的块进行分配，并将它们链接在一起(作为一个数组，或者可能是一个向量)。

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

vector还可以很好地与需要连续缓冲区的API配合使用，因为它们要么是APIs，要么在能够接受指针和长度方面更加通用。(因此，您可以在下面使用一个向量或一个常规数组，并从内存块中调用API )。

deque最大的优势是：

1. 当从两端增大或缩小集合时
2. 当您处理非常大的集合大小时。
3. 当您处理布尔值并且您确实需要布尔值而不是位集时。

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

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

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

话虽如此，在使用“乐观”内存分配的系统上使用std::deque可能会遇到麻烦。尽管分配器尝试为重新分配vector而请求较大的缓冲区大小时，可能会在使用bad_alloc时被拒绝，但分配器的乐观性质很可能始终允许deque请求较小缓冲区的请求，这可能会导致操作系统终止进程以尝试获取一些内存。无论它选择哪一个，都可能不太令人愉快。

这种情况下的变通方法是设置系统级标志以覆盖乐观分配(并不总是可行的)，或者更多地手动管理内存，例如使用您自己的分配器检查内存使用情况或类似情况。显然不是很理想。(这可能会回答您关于首选向量的问题...)

我已经多次实现了vector和deque。从实现的角度来看，deque要复杂得多。这种复杂性转化为更多的代码和更复杂的代码。因此，当您选择deque而不是vector时，通常会看到代码大小命中。如果你的代码只使用向量擅长的东西(即push_back)，你也可能会遇到一些小的速度问题。

如果你需要一个双端队列，那么deque是最好的选择。但是如果你在后面做大部分的插入和擦除操作，向量显然会是赢家。当你不确定的时候，声明你的容器有一个类型定义(这样就很容易来回切换)，并测量。