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

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

背部()

推回()

pop_back()

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

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

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

---

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

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

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

1> Michael Burr..：

---

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

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

2> James Hopkin..：

---

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

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

---

此外,`priority_queue`必须保持排序,因此随机访问`deque :: iterator`的更高开销更成问题.

---

priority_queue实际上并不使用push/pop_front,并且堆操作使第一个之外的元素引用无效.因此,与常规队列的情况不同,deque的好处都不会适用.