为什么std::stack默认使用std::deque？

Question

既然一个容器在堆栈中使用所需的唯一操作是:

• back()
• push_back()
• pop_back()

那么为什么默认容器是deque而不是vector呢？

难道deque重新分配不会在front()之前提供一个元素缓冲区，使得push_front()成为一种有效的操作吗？既然这些元素在堆栈的上下文中永远不会被使用，它们岂不是被浪费了吗？

如果使用deque而不是vector没有任何额外开销，那么为什么priority_queue的默认值是vector而不是deque呢？（priority_queue需要front()，push_back()和pop_back() - 本质上与stack相同）

---

基于下面的回答进行更新：

看起来deque通常的实现方式是固定大小数组的可变大小数组。这使得增长比vector更快（后者需要重新分配和复制），因此对于像堆栈这样的东西，deque可能是更好的选择。

priority_queue需要大量索引，因为每次删除和插入都需要运行pop_heap()或push_heap()。这可能使得vector在这方面更好，因为添加元素仍然是摊销的常数时间。

- Greg Rogers

---

你的“更新”中的推理不太正确。相比deque，vector通常更快地从末尾添加和删除元素。deque在增加内存方面更快，而不是在推入元素方面更快。 - Mooing Duck

Answer 1

随着容器大小的增长，对于vector的重新分配需要将所有元素复制到新的内存块中。而增加一个deque会分配一个新的块并将其链接到块列表上——不需要复制任何内容。

当然，如果你愿意，可以指定使用不同的支持容器。因此，如果你知道一个堆栈不会增长太多，可以告诉它使用vector而不是deque，如果这是你的偏好的话。

- Mike B

---

但是当指向块的指针列表增长时，这个列表必须偶尔像向量一样被重新分配；渐近地，任何效率上的收益最多只能是一个常数因子。而且，为了正确执行推入和弹出操作，需要进行迭代器操作，对于std::deque来说比std::vector要复杂得多，并且这些操作很可能比重新分配操作更频繁地使用。我很难相信在实践中std::deque会胜过std::vector。 - Marc van Leeuwen

@Michael Burr：那为什么不使用list，而是使用deque呢？ - bappak

@MarcvanLeeuwen，关于你说你很难相信...你能否明确表态？你是指现在相信std::deque有机会在实践中击败std::vector，还是仍然怀疑它？谢谢。 - aafulei

@fleix 我不明白为什么我个人认为std::deque在实际应用中能够胜任与std::vector同样重要。但就我个人经验而言，我需要堆栈和队列数据结构，并不是为了一个大型的、复杂关键的任务，而是为了许多散布在我的代码中的小场合。因此，我更关心小规模情况下的行为，而deque在这方面表现得相当平庸。我的偏好是使用（自己实现的）单向链表。但你的情况可能会有所不同。 - Marc van Leeuwen

Answer 2

请参阅Herb Sutter的“Guru of the Week 54”，了解在可选情况下vector和deque的相对优点。

我认为priority_queue和queue之间的不一致性只是因为不同的人实现了它们。

- James Hopkin

---

priority_queue 实际上并不使用 push/pop_front 操作，除了第一个元素之外的其他元素的引用都会在堆操作中失效。因此，与常规队列不同，deque 的任何优点都不适用于 priority_queue。 - Potatoswatter

此外，priority_queue 必须保持有序，因此随机访问 deque::iterator 带来的较高开销更为棘手。 - Potatoswatter

@Potatoswatter：priority_queue 有一个被维护的“神奇顺序”，它并没有排序。无论如何，你说得没错。 - Mooing Duck