为什么更喜欢使用 std::vector 而不是 std::deque？

Question

为什么更喜欢使用 std::vector 而不是 std::deque？

c++stl

12

它们的访问复杂度和随机插入/删除复杂度都是O(1)。但是因为重新分配内存并复制，向量在扩展时成本更高，而双端队列则没有这个问题。

看起来双端队列性能更好，但为什么大多数人还是使用向量而不是双端队列呢？

- SwiftMango

2

当访问项目时，vector 更有效率。O(1) 复杂度并不意味着两者使用相同数量的周期。此外，重新分配 vector 将移动其项目（如果可能），而不一定是复制它们。 - syam

@syam 两者都具有O(1)的访问复杂度，不是吗？ - SwiftMango

6

@texasbruce说：是的；但是deque通常具有额外的间接级别，使访问变慢。 O(1)只是意味着随着容器变大，情况不会变得更糟。对于在末尾添加元素，它们都具有平摊的O(1)时间；但您的观点是vector（有时）仍然较慢。 - Mike Seymour

1

就其价值而言，MSVC的deque实现很容易退化为指针向量（如果sizeof(T)>16），这就像一个向量，但具有额外的间接和分配。 - R. Martinho Fernandes

@texasbruce：sleep(1)和sleep(10000)的时间复杂度都是O(1)，但完成所需的时间却非常不同。 - David Rodríguez - dribeas

显示剩余3条评论

5个回答

10

当扩展时，由于重新分配和复制，vector的成本更高。虽然vector有时需要在增长时重新分配其数组，但它会呈指数增长，因此摊销复杂度仍为O(1)。通常，您可以通过谨慎使用reserve()来避免重新分配。 deque似乎具有更好的性能。性能有许多方面；push_back所花费的时间只是其中之一。在某些应用程序中，容器可能很少被修改，或者在启动时填充，然后永远不再修改。在这种情况下，迭代和访问速度可能更重要。 vector是最简单的容器：一个连续的数组。这意味着迭代和随机访问可以通过简单的指针算术来实现，并且访问元素可以像解除引用指针一样快。 deque有进一步的要求：它不能移动元素。这意味着典型的实现需要额外的间接层 - 它通常被实现为指向数组的指针的数组之类的东西。这意味着元素访问需要解除引用两个指针，这将比一个指针慢。

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

- Mike Seymour

+1 这个回答和另一个回答可能是最好的直接回答 OP 的问题和观察的回答。然而，我有一个问题要问你。向量确实具有指数增长模式，但由于这个事实的本质，插入复杂度不是几何级数衰减（即倒数）吗？虽然很小，但是第一点，我不理解。 - WhozCraig

@WhozCraig：大小为n的重新分配最多会在每次插入n次时发生一次。因此，平摊成本为O(n/n) == O(1)。 - Mike Seymour

哈哈，我需要在做数学之前喝上我的早晨咖啡。谢谢你，迈克。非常感谢。 - WhozCraig

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 - 它不会比deque更差。

- Ivaylo Strandjev

1

@syam并不禁止deque也具有连续的存储空间。虽然效率低下，但仍然是可能的。 - Ivaylo Strandjev

@syam 实际上，如果您像在后面一样将内存留在前面（即将数据放在内存块的中间），那么push_front将与push_back一样有效。 - rabensky

我正在删除段落中引起进一步争论的部分 :) - Ivaylo Strandjev

@IvayloStrandjev 噢...这是一个很好的讨论。很遗憾...那我就在这里加上吧：讨论的内容是关于是否有可能将std::vector实现为环绕式的std::deque（当然需要适当的deque实现，以便存储是连续的）。 - rabensky

2

需要注意的是，Herb Sutter（链接文章的作者）早已改变了他的态度，更喜欢使用vector。http://coding.derkeiler.com/Archive/C_CPP/comp.lang.cpp/2004-10/3161.html - Benjamin Lindley

显示剩余5条评论

4

对于C++：

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

- Thomas Ayoub

对于队列、缓冲区、环形等各种用途，deque 绝对更合理：你希望在开头进行快速插入/删除，但不想使用列表，因为你想要接近向量的速度而不是常数级的指针查找。这在处理较大集合时尤其如此。但是，如果你有一个较小的东西，或者如果你更倾向于 stack，只涉及到其中一端，你应该使用 vector。关于为什么显然 C++ 默认使用 deque 实现 stack，这真是令人费解... - Andrew

3

个人而言，我更喜欢使用deque（总是不得不出于某种原因使用push_front），但是vector也有其用处/差异，主要的一点是：

vector具有连续的内存，而deque通过页面/块进行分配。请注意，页面/块非常有用：在容器的前面进行插入/删除时具有恒定时间。通常情况下，将大块内存分成一系列较小的块要比单个内存块更有效率。

你还可以说，因为deque缺少大小预留方法(capacity/reserve)，所以你需要担心的东西会更少。

我强烈建议你阅读Sutters'关于这个主题的GotW。

- Mohammed Hossain

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- John Dibling · Accepted Answer

why most people use vector instead of deque?

因为这就是他们所学的。vector和deque有稍微不同的用途，如果你只需要简单的对象容器，它们都可以使用。当学习编程C++时，这正是大多数人所需要的——一个把东西放进去、拿出来并走过的桶。当StackOverflow被问到“默认应该使用哪个容器”这样的问题时，几乎总是回答vector。问题通常是从学习C++的背景下提出的，在程序员提出此类问题的时候，他们还不知道自己不知道什么。而且他们还有很多东西要学。所以，我们（StackOverflow）需要一个容器，可以适合几乎所有需求，可以在几乎任何情况下使用，并且不需要程序员在得到近似正确答案之前问出所有正确的问题。此外，标准明确建议使用vector。虽然deque实际上比vector在许多常见用途中更好，但对于学习编程的程序员来说，它不会比vector好到我们应该违反标准的建议，因此StackOverflow选择了vector。在学习了C++语法和策略的基础知识后，程序员分为两个分支：那些关心学习更多并编写更好程序的人，以及那些不关心的人。那些不关心的人将永远停留在vector上。我认为许多程序员属于这个阵营。尝试超越这个阶段的程序员少之又少，他们开始提出其他问题——就像你在这里提出的问题一样。他们知道他们还有很多东西要学，他们想开始发现那些东西是什么。他们会很快（或不太快）发现，在选择vector和deque之间时，一些他们以前没有考虑过的问题是：1. 我需要内存连续吗？2. 我需要避免大量重新分配吗？3. 我需要在插入后保持有效的迭代器吗？4. 我的集合需要与某些类似C的古老函数兼容吗？然后他们真正开始思考他们正在编写的代码，发现了更多他们不知道的东西，如此循环往复...