爲什麼std :: stack默認使用std :: deque？

Question

由於在堆棧被用於容器所需的唯一操作是：

• 背面（）
• 的push_back（）
• pop_back（）

爲什麼是默認的容器因爲它是一個deque而不是一個向量？

不要deque reallocations給front（）前的元素的緩衝區，這樣push_front（）是一個有效的操作嗎？這些元素是不是浪費了，因爲它們永遠不會用在堆棧的上下文中？

如果沒有使用deque這種方式而不是使用向量的開銷，爲什麼priority_queue向量不是deque也是默認值？ （priority_queue需要前（），的push_back（）和pop_back（） - 基本上相同的作爲疊層）

---

更新基於下面的數目：

似乎雙端隊列的方式是通常實現的是固定大小數組的可變大小數組。這使得增長速度比一個向量（需要重新分配和複製）要快，因此對於類似堆棧的增加和刪除元素，deque可能是更好的選擇。

priority_queue需要大量編制索引，因爲每個刪除和插入都需要運行pop_heap（）或push_heap（）。這可能會使向量成爲更好的選擇，因爲添加元素仍然是不變的。

Answer 1

隨着容器的增長，爲矢量重新分配需要將所有元素複製到新的內存塊中。增加一個deque分配一個新塊並將其鏈接到塊列表 - 不需要副本。

當然，如果您願意，您可以指定使用不同的背襯容器。所以，如果你有一個你知道不會增長太多的堆棧，那麼告訴它使用一個向量而不是一個deque，如果這是你的偏好。

Answer 2

請參閱Herb Sutter的Guru of the Week 54以瞭解vector和deque的優缺點。

我想像priority_queue和隊列之間的不一致只是不同的人實現它們。