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

Question

由于在堆栈中使用容器所需的唯一操作是:

为什么它的默认容器是deque而不是vector？

不要deque重新分配在front()之前给出元素缓冲区,以便push_front()是一个有效的操作吗？这些元素不会浪费,因为它们永远不会在堆栈的上下文中使用吗？

如果没有开销使用一个deque这种方式,而不是一个向量,为什么是priority_queue矢量不是一个deque也默认？(priority_queue需要front(),push_back()和pop_back() - 基本上与堆栈相同)

根据以下答案进行了更新:

似乎deque通常实现的方式是固定大小数组的可变大小数组.这使得比向量的增长速度(这需要重新分配和复制),所以对于像一个栈,所有关于添加和删除元素,双端队列可能是一个更好的选择.

priority_queue需要大量的索引,因为每个删除和插入需要你运行pop_heap()或push_heap().这可能使得向量成为更好的选择,因为添加元素仍然是分摊常数.

Answer 1

随着容器的增长,向量的重新分配需要将所有元素复制到新的内存块中.增加deque会分配一个新块并将其链接到块列表 - 不需要复制.

当然,如果您愿意,可以指定使用不同的后备容器.因此,如果你有一个你知道不会增长太多的堆栈,请告诉它使用向量而不是deque,如果这是你的偏好.

@Michael Burr：那为什么不使用“list”，为什么使用“deque”？ (3认同)
但是当指向块的指针列表增长时，这个列表必须偶尔重新分配，就像向量一样；渐进地，效率的任何提高充其量都是一个常数因子。对于 `std::deque` 来说，正确执行 push 和 pop 所需的迭代器操作比 `std::vector` 复杂得多，并且这些操作可能比重新分配更频繁地使用。我很难相信 `std::deque` 在实践中会击败 `std::vector`。 (2认同)

Answer 2

请参阅Herb Sutter的第54周的大师,了解vector和deque的相对优点.

我认为priority_queue和队列之间的不一致只是不同的人实现了它们.

此外,`priority_queue`必须保持排序,因此随机访问`deque :: iterator`的更高开销更成问题. (9认同)
priority_queue实际上并不使用push/pop_front,并且堆操作使第一个之外的元素引用无效.因此,与常规队列的情况不同,deque的好处都不会适用. (2认同)
@Potatoswatter：`priority_queue` 有一个被维护的“神奇顺序”，它没有排序。然而，你的观点是成立的。 (2认同)