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 の要件を満たします。

テンプレートパラメータ

イテレータの無効化

無効化に関する注記

• dequeの両端に挿入する場合、参照は insert および emplace によって無効化されません。
• push_front 、 push_back 、 emplace_front および emplace_back は、dequeの要素への参照を一切無効化しません。
• dequeの両端で削除する場合、削除されない要素への参照は erase 、 pop_front および pop_back によって無効化されません。
• より小さいサイズでの resize の呼び出しは、削除されない要素への参照を一切無効化しません。
• より大きいサイズでの resize の呼び出しは、dequeの要素への参照を一切無効化しません。

メンバー型

メンバー関数

非メンバー関数

注記

例

#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

不具合報告

以下の動作変更の欠陥報告書は、以前に公開されたC++規格に対して遡及的に適用されました。

関連項目