std:: deque

std::deque (ダブルエンドキュー) は、先頭と末尾の両方で高速な挿入と削除を可能とするインデックス付きシーケンスコンテナです。さらに、デキューのどちらかの端での挿入と削除は、他の要素へのポインタや参照を決して無効化しません。

std::vector とは対照的に、dequeの要素は連続して格納されません：典型的な実装では、個別に割り当てられた固定サイズの配列のシーケンスと追加の簿記処理を使用します。これは、dequeへのインデックスアクセスが2回のポインタ間接参照を実行する必要があることを意味し、vectorのインデックスアクセスが1回のみ実行するのと比較されます。

dequeのストレージは必要に応じて自動的に拡張および縮小されます。dequeの拡張は、 std::vector の拡張よりもコストが低くなります。これは、既存の要素を新しいメモリ位置にコピーする必要がないためです。一方、dequeは通常、大きな最小メモリコストを持ちます。たとえば、1つの要素しか保持していないdequeでも、その内部配列全体を割り当てる必要があります（64ビットlibstdc++ではオブジェクトサイズの8倍、64ビットlibc++ではオブジェクトサイズの16倍または4096バイトのいずれか大きい方）。

デキューにおける一般的な操作の複雑性（効率）は以下の通りです：

• ランダムアクセス - 定数時間 O(1) 。
• 末尾または先頭への要素の挿入・削除 - 定数時間 O(1) 。
• 要素の挿入・削除 - 線形時間 O(n) 。

std::deque は Container 、 AllocatorAwareContainer 、 SequenceContainer および ReversibleContainer の要件を満たします。

#include <deque>
#include <iostream>
int main()
{
    // 整数を含むdequeを作成
    std::deque<int> d = {7, 5, 16, 8};
    // dequeの先頭と末尾に整数を追加
    d.push_front(13);
    d.push_back(25);
    // dequeの値を反復処理して出力
    for (int n : d)
        std::cout << n << ' ';
    std::cout << '\n';
}

13 7 5 16 8 25