51

可能重复：
为什么我更喜欢使用向量到双端队列

我很好奇为什么它std::vector比std::deque. 双端队列在查找方面几乎同样有效，在插入方面效率更高（没有 vector::reserve）并允许在前面插入/删除。

Herb Sutter 曾经建议，如果你想使用向量，就更喜欢 deque（我在解释）。然而，在最近一次关于编写现代 C++的演讲中，他再次强烈建议将std::vector其视为默认容器。根据我之前链接的GOTW，即使是标准也有类似的措辞。

这种差异有原因吗？仅仅是这样vector更简单、更广为人知，还是有技术原因？或者这vector只是一个更酷的名字..？

4

5 回答 5

57

我不能为任何人说话，但我可以为自己说话。

当我第一次阅读有关std::deque时，我认为它很酷，有一段时间，我不仅将其视为默认容器，而且几乎将其视为我使用的唯一容器。

然后有人问为什么，我详细解释了它的优点，为什么它是几乎所有东西的最佳容器，以及它是如何比std::vector.

幸运的是，质疑我决定的人足够有说服力，我做了一些测试。测试表明，几乎在所有情况下，std::deque都比 - 通常慢std::vector一个重要因素（例如，大约 2）。事实上，在我使用 编写的代码中，除了少数情况外std::deque，仅用 替换std::deque就可以加快速度。std::vector

从那以后我std::deque在一些情况下使用过，但绝对不要再把它当作默认值了。一个简单的事实是，在通常的实现中，它明显比大多数目的慢std::vector。

但是，我应该补充一点，我有理由确定，通过正确的实现，它几乎可以等同std::vector于几乎所有情况。从渐近的角度来看，大多数人使用的表示无疑是很棒的，但在现实世界中（出于许多目的）并不能很好地发挥作用。

于 2012-12-07T07:21:55.770 回答
14

std::vector很好理解，简单并且与 C 兼容（无论是在内存布局方面，还是在使用指针作为迭代器方面）。

对于某些操作，它也比std::deque. 通过索引访问元素就是一个例子。

对于给定的任务，使用能很好地完成工作的最简单的容器是有意义的。在许多情况下，最简单的容器是std::vector.

于 2012-12-07T07:14:50.310 回答
5

除了std::vector是最广为人知的容器类之外，它还比std::deque.

  • 典型的std::deque需要额外的间接访问元素，不像std::vector.
  • 情况下的迭代器std::deque必须是智能指针，而不是 . 情况下的指针std::vector。
  • an 的元素std::vector保证是连续的，因此它与将数组作为参数的 c 样式函数兼容。
  • std::deque不提供控制容量和重新分配时刻的支持。

特别是最后一点值得注意。

于 2012-12-07T07:20:04.340 回答
5

人们出于简单的原因使用 std::vector 而不是 std::deque。它们与许多 C 库接口，并且它们具有带有参数的函数，这些函数需要指向连续存储的指针，而 std::deque 不能（不能）保证。

另一个原因是当您根据 std::deque 构建代码并且您的需求发生变化以致必须支持连续访问时，您将需要进行一些重构。

我不得不提一下，有些库的作者声称已经创建了更高效的向量实现，以便在容量增加时克服效率低下的问题。

于 2012-12-07T07:21:16.657 回答
5

的结构std::deque有点复杂，这使得天真的迭代比std::vector. 插入std::vector及其重新分配往往不是大问题，尤其是在使用reserve()并仅附加到末尾时。此外，还有更容易理解的失效规则，std::vector尽管它实际上是std::deque对象在插入/删除时仅在任一端保持原位的优点（请注意，std::deque迭代器在每次插入时都会失效，与插入发生的位置无关）。另一个优点std:vector是保证这些值在内存中是连续的，从而减少了内存分配。

I guess, I would recommend use of std::deque algorithms were consistently optimized to use segmented sequences (I'm not aware that any standard C++ library does this optimization) and users were accessing sequences consistently using algorithms (as far as I can tell, only a tiny fraction of users considers the option to use algorithms). Otherwise I would suspect that std::deque is the better option with respect to performance only if you take advantage of its specific properties (e.g., that objects stay put and that you can insert/remove at the end). It is worth profiling the two alternatives, though.

于 2012-12-07T07:22:15.943 回答