std::deque

namespace std {
  template <class T, class Allocator = allocator<T>>
  class deque;

  namespace pmr {
    template <class T>
      using deque = std::deque<T, polymorphic_allocator<T>>;  // C++17から
  }
}

概要

deque（通常、"デック"のように発音する）はdouble-ended queue （二重終端キュー）の頭文字をとったものである。double-ended queue はシーケンスコンテナの一種である。要素は厳密な線形シーケンスに従って並べられる。

deque はライブラリによってさまざまな方法で実装されるかもしれないが、全ての場合においてランダムアクセスイテレータを介して個々の要素へアクセス可能であり、ストレージは（必要に応じて拡大または縮小して）自動的に処理される。

deque シーケンスは以下の特性を持つ。

• 個々の要素はその位置インデックスによってアクセスすることができる。
• 要素のイテレーションは任意の順序で実行することができる。
• 要素はいずれの端（シーケンスの先頭または最後）からも効率よく追加・削除される。

従ってこれは vector と同様の機能を提供するが、シーケンスの終端だけでなく先頭への効率的な挿入・削除を共に提供する。vector とは異なる欠点として deque は連続した位置のストレージに全ての要素を持つことを保証していないため、ポインタ演算を介しての安全なアクセスの可能性を排除する。

vector と deque は共に類似したインターフェイスを提供するため、類似した目的に利用することができるが、内部的にはかなり異なった方法で動作する。vector は通常の配列と非常によく似ており、容量が使い果たされるときにはブロック内の全ての要素を再配置することによって拡張する。deque は全ての情報を保持しつつ要素への均一なアクセスを提供することで、要素をストレージのいくつかのチャンクに分割することができる。従って deque の内部は少し複雑であるが、これは特に大規模なシーケンスにおいて大規模な再配置が回避されることを許すため、一般に容量増加の自動管理を vector より効率的に行うことを可能にする。

テンプレートパラメータは、以下を意味する：

• T : 要素の型。
• Allocator : ストレージの割り当てモデルを定義するために使用されるアロケータオブジェクトの型。デフォルトでは、値に依存しない単純なメモリ割り当てモデルを定義する、型 T の allocator クラステンプレートが使われる。

メンバ関数

構築／コピー／破棄

要素アクセス

イテレータ

領域

コンテナの変更

メンバ型

非メンバ関数

比較演算子

入れ替え

要素削除

推論補助

例

#include <iostream>
#include <deque>
#include <algorithm>

int main()
{
  std::deque<int> deq;

  deq.push_front(3);  // 先頭に要素を追加
  deq.push_back(1);   // 末尾に要素を追加

  // イテレータを介して全要素に対して操作を行う
  std::for_each(deq.begin(), deq.end(), [](int x) {
    std::cout << x << std::endl;
  });
}

出力

3
1

参照

• N2669 Thread-Safety in the Standard Library (Rev 2)