std::deque

std::deque (double-ended queue) は先頭と末尾の両方に高速な挿入と削除が行えるインデックス付きのシーケンスコンテナです。 さらに、 deque の先頭または末尾への挿入および削除は残りの要素に対するポインタや参照を決して無効化しません。

std::vector と異なり、 deque の要素は隣接して格納されません。 一般的な実装では、個別に確保された一連の固定サイズの配列を用い、 deque へのインデックスアクセスが2回のポインタ逆参照で行えるように追加の維持管理を行います。 それに対して vector のインデックスアクセスはポインタを1回逆参照するだけです。

deque の記憶域は必要に応じて自動的に拡張されたり縮小されたりします。 deque の拡張は、既存の要素を新しいメモリ位置にコピーする必要がないため、 std::vector の拡張よりも安く行えます。 一方で、 deque は一般的には大きな最小メモリコストを持ちます。 deque にたった1個の要素を格納するだけでも、完全な内部配列を確保する必要があります (例えば、64ビットのlibstdc++ではオブジェクトサイズの8倍、64ビットのlibc++ではオブジェクトサイズの16倍か4096バイトの大きい方が確保されます)。

deque の一般的な操作の計算量 (効率性) は以下の通りです。

• ランダムアクセス - 定数時間 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 の要素へのいかなる参照も無効化されません。

[編集] メンバ型

[編集] メンバ関数

[編集] 非メンバ関数

[編集] 推定ガイド(C++17以上)

[編集] 例

#include <iostream>
#include <deque>
 
int main()
{
    // Create a deque containing integers
    std::deque<int> d = {7, 5, 16, 8};
 
    // Add an integer to the beginning and end of the deque
    d.push_front(13);
    d.push_back(25);
 
    // Iterate and print values of deque
    for(int n : d) {
        std::cout << n << '\n';
    }
}

13
7
5
16
8
25