C++ 両端キュー

両端キュー(またの名をデック(deques))は ベクタと似ていますが、先頭や終端へ高速な挿入削除処理が行えます。

C++デックは一般的には両端をのばすことができる動的確保された配列で実装されます。これは、要素に 定数時間でアクセスできること、デックの両端での挿入削除処理が定数時間で終わること、両端以外への挿入削除処理が 線形時間で終わることを保証します。

Constructors	デックを生成し、いくつかのデータで初期化します
Operators	比較、割り付け、デック要素にアクセスします
assign	デックに要素を割り付けます
at	指定した位置の要素への参照を返却します
back	デックの最後の要素への参照を返却します
begin	デックの先頭を指し示すイテレータを返却します
clear	デックからすべての要素を取り除きます
empty	デックの要素がなければ真(true)を返却します
end	デックの最後の要素の1つ先を指し示すイテレータを返却します
erase	デックから要素を取り除きます
front	デックの先頭の要素への参照を返却します
insert	デックに要素を挿入します
max_size	デックが保持できる要素の最大数を返却します
pop_back	デックの最後の要素を取り除きます
pop_front	デックの最初の要素を取り除きます
push_back	デックの最後尾に要素を追加します
push_front	デックの先頭に要素を追加します
rbegin	デックの最後尾を指し示すreverse_iteratorを返却します
rend	デックの先頭を指し示すreverse_iteratorを返却します
resize	デックのサイズを変更します
size	デックに含まれる項目数を返却します
swap	別のデックと中身を取り替えます

覚え書き

dequeは"デック"と発音し、"両端キュー"を意味します。クヌース(Knuth)はE.J.シュウェップ(E.J.Schweppe)の造語だと報告しています。デックについてのより多くの情報はクヌース(Knuth)のセクション2.2.1を参照してください。 (D. E. Knuth, The Art of Computer Programming. Volume 1: Fundamental Algorithms, second edition. Addison-Wesley, 1973.)