向量与双端队列的区别

Question

vector和deque都提供了在末尾插入元素的函数push_back。

deque还提供了一个在开头插入元素的函数push_front，但对于vector而言，这有点昂贵。

我的问题是，既然我们可以使用deque实现与vector相同的功能(push_back)，那么为什么还需要vector呢？

- rajenpandit

Answer 1

向量和双端队列的一个主要区别是后者允许高效地在结构体的前端和后端插入。

双端队列也不能保证它们的元素在内存中是连续的，因此 at-style 操作符（索引操作）可能不太高效。

请注意，在实践中，这种差异对于较小的集合来说并不重要，但如果，例如，集合大小增加或者你每秒钟进行多次修改，则通常会变得更加重要。

- paxdiablo

---

std::deque也是如此。 - Joseph Mansfield

高效的插入操作取决于元素数量和复制成本。如果元素数量不太多，且复制成本不太高，那么在std::vector中从前面插入可能比在std::deque中更便宜。 - James Kanze

@James，如果你的结构只包含少量元素，那么你可以使用数组而不必担心集合问题 :-) 我更多地考虑到更大的集合，这时候双端队列在前插入方面更有效率。但你提出了一个很好的观点，所以我会加上它。 - paxdiablo

@paxdiablo 这个问题是：什么时候容器变得足够大，以证明它们之间的差异。很久以前，我有一个同事测量了移动一百万字节所需的时间，结果惊人地低（但当时没有考虑缓存内存和潜在的缺失）。最终，我没有任何真正的答案：对于10个char，使用C风格数组或std::vector（或C++11中的std::array）。对于执行深拷贝（包括分配等）的数百万个元素，请使用std::deque。在两者之间是分界线，但我不知道在哪里。 - James Kanze

请注意，如果您正在保留对元素的指针引用，您必须使用 vector 而不是 deque，因为 deque 会被移动，从而使指针无效。 - Pierre

Answer 2

主要是性能。一个std::deque至少在常规使用中具有std::vector的所有功能，但是对它进行索引和迭代通常会稍微慢一些；如果您使用了reserve，在末尾添加也可能会出现相同的情况。当然，std::vector是默认容器，使用其他容器将向读者暗示您具有特殊要求。

此外，std::vector还保证连续性，因此它（仅它）可以用于与需要T*或T const*的旧函数进行接口。

我想补充一点，当我真正遇到性能问题并进行测量时，std::vector比std::deque更快，尽管我经常从前面删除元素（使用容器作为队列，在后面推入，在前面弹出）。我不知道是否普遍适用；在我的情况下，队列相对较短（从不超过约15个元素，通常更少），内容是char，非常便宜的复制。但总的来说，即使需要从前面删除元素，我也会使用std::vector，仅因为它更好的局部性。如果我预计有成千上万个昂贵的元素需要复制，我可能只会考虑std::deque。

- James Kanze

---

我实现了一个100个元素的FIFO结构，用于缓冲一些输入传感器数据。我使用deque实现，通过在新元素进入时推入队尾，并在达到100大小时弹出队首。您认为这是一个可接受的架构选择吗？我想知道您对实现用于缓冲传感器数据的先进先出结构的更好方法的看法。谢谢您的帮助。 - Employee

@Employee 这个函数可以工作，但对于 FIFO 来说不如 vector 理想。由于 FIFO 和向量一样是有序和连续的，它们是更好的一般配对。然而，如果您要在构建列表之后更改 FIFO 管道中项目的顺序，则 deque 可能更合适。 - That Realty Programmer Guy

Answer 3

std::deque是双端队列。与std::vector不同，它不仅提供在末尾插入和删除元素的高效方法，还能在开头进行操作。向量保证将元素存储在连续的存储器中，因此您可以通过索引/偏移量访问其元素。std::deque没有这个保证。

- Marius Bancila

---

您也可以使用[]或at()访问deque的元素。在该层面上，接口没有区别。 - James Kanze