[解決済み] なぜstd::stackはデフォルトでstd::dequeを使うのですか？

疑問点

スタックで使用するコンテナに必要な操作は、以下の通りであるため。

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

なぜデフォルトのコンテナはvectorではなくdequeなのでしょうか？

deque の再割り当ては、front() の前に要素のバッファを与えるので、push_front() は効率的な操作にならないのでしょうか? これらの要素はスタックのコンテキストで決して使用されることがないので、無駄ではないですか？

もし、vector の代わりに deque をこの方法で使用してもオーバーヘッドがないのであれば、なぜ priority_queue のデフォルトは deque ではなく vector なのでしょうか? (priority_queue は front(), push_back(), pop_back() を必要とします - 基本的にスタックと同じです)。

以下の回答を元に更新しました。

dequeの実装方法は、通常、固定サイズの配列を可変サイズにしたもののようです。これはベクター（再割り当てとコピーが必要）よりも高速に成長するので、要素の追加と削除がすべてであるスタックのようなものには、おそらくdequeがより良い選択です。

priority_queue は、削除と挿入のたびに pop_heap() または push_heap() を実行する必要があるため、インデックス付けが非常に必要です。これはおそらく、要素を追加することがとにかくまだ償却された定数であるので、そこではvectorがより良い選択となります。

どのように解決するのですか？

コンテナが成長すると、vector の再割り当てでは、すべての要素を新しいメモリブロックにコピーする必要があります。 deque を成長させると、新しいブロックが割り当てられ、ブロックのリストにリンクされます - コピーは必要ありません。

もちろん、必要であれば、異なるバッキングコンテナを使用するように指定することができます。 スタックがあまり大きくならないことがわかっている場合、dequeの代わりにvectorを使用するように指定します。