std::stack がデフォルトで std::deque を使用するのはなぜですか?

Question

コンテナーをスタック内で使用するために必要な操作は以下だけであるため、

• 戻る（）
• プッシュバック()
• ポップバック()

デフォルトのコンテナーがベクターではなく両端キューであるのはなぜですか?

Push_front() が効率的な操作となるように、再割り当てのデキューでは、front() の前に要素のバッファーが提供されませんか?これらの要素はスタックのコンテキストでは決して使用されないため、無駄ではないでしょうか?

ベクトルの代わりにこの方法で両端キューを使用することにオーバーヘッドがない場合、priority_queue のデフォルトが両端キューではなくベクトルであるのはなぜですか?(priority_queue には、front()、push_back()、pop_back() が必要です - 基本的に stack の場合と同じです)

---

以下の回答に基づいて更新されました。

deque の通常の実装方法は、固定サイズの配列の可変サイズの配列であるようです。これにより、ベクトル (再割り当てとコピーが必要) よりも成長が速くなるため、要素の追加と削除がすべてのスタックのようなものには、deque の方が良い選択となる可能性があります。

priority_queue では、削除と挿入のたびに Pop_heap() または Push_heap() を実行する必要があるため、大量のインデックス作成が必要です。いずれにせよ、要素を追加しても一定の償却が行われるため、おそらくベクトルの方が良い選択肢となるでしょう。

Answer 1

コンテナーが大きくなるにつれて、ベクトルの再割り当てでは、すべての要素をメモリの新しいブロックにコピーする必要があります。デキューを拡張すると、新しいブロックが割り当てられ、ブロックのリストにリンクされます。コピーは必要ありません。

もちろん、必要に応じて、別のバッキング コンテナーを使用するように指定することもできます。したがって、あまり大きくならないことがわかっているスタックがある場合は、好みに応じて両端キューの代わりにベクトルを使用するように指示してください。

Answer 2

ハーブ・サッターの作品を見る 今週の第一人者 54 Vector と Deque の相対的なメリットについては、どちらでもよい場合に使用します。

priority_queue と queue の間に矛盾があるのは、単に異なる人が実装しただけだと思います。