std::deque

 

C++

コンパイラサポート

フリースタンディングとホスト

言語

標準ライブラリ

標準ライブラリヘッダー

名前付き要件

機能テストマクロ (C++20)

言語サポートライブラリ

コンセプトライブラリ (C++20)

診断ライブラリ

メモリ管理ライブラリ

メタプログラミングライブラリ (C++11)

汎用ユーティリティライブラリ

コンテナライブラリ

イテレータライブラリ

Rangesライブラリ (C++20)

アルゴリズムライブラリ

文字列ライブラリ

テキスト処理ライブラリ

数値ライブラリ

日付と時刻ライブラリ

入出力ライブラリ

ファイルシステムライブラリ (C++17)

並行サポートライブラリ (C++11)

実行制御ライブラリ (C++26)

Technical specifications (技術仕様)

シンボルインデックス

外部ライブラリ

 

コンテナライブラリ

シーケンス

array (C++11)

vector

vector<bool>

inplace_vector (C++26)

hive (C++26)

deque

forward_list (C++11)

list

連想

set

multiset

map

multimap

非順序連想

unordered_set (C++11)

unordered_multiset (C++11)

unordered_map (C++11)

unordered_multimap (C++11)

アダプタ

stack

queue

priority_queue

flat_set (C++23)

flat_multiset (C++23)

flat_map (C++23)

flat_multimap (C++23)

表示

span (C++20)

mdspan (C++23)

表

イテレータの無効化

メンバ関数テーブル

非メンバ関数テーブル

 

std::deque

メンバ型
メンバ関数
コンストラクタ デストラクタ operator= assign assign_range (C++23)   get_allocator 要素アクセス at operator[] front back イテレータ begincbegin (C++11) endcend (C++11) rbegincrbegin (C++11) rendcrend (C++11)	容量 empty size max_size shrink_to_fit (DR*) 変更 clear insert insert_range (C++23) emplace erase push_front emplace_front (C++11) prepend_range (C++23) pop_front push_back emplace_back (C++11) append_range (C++23) pop_back resize swap
非メンバ関数
operator==operator<=> (C++20) swap(std::deque) erase(std::deque)erase_if(std::deque) (C++20)(C++20)	operator!=operator<operator>operator<=operator>= (C++20まで)(C++20まで)(C++20まで)(C++20まで)(C++20まで)
推論補助(C++17)

 

ヘッダー <deque> で定義
template<     class T,     class Allocator = std::allocator<T> > class deque;	(1)
namespace pmr {     template< class T >     using deque = std::deque<T, std::pmr::polymorphic_allocator<T>>; }	(2)	(C++17以降)

std::deque (double-ended queue、デック)は、シーケンスの先頭と末尾の両方で高速な挿入と削除を可能にする、インデックス付きシーケンスコンテナである。さらに、dequeのどちらかの端での挿入と削除は、残りの要素へのポインタや参照を決して無効にしない。

std::vector とは対照的に、deque の要素は連続して格納されない。典型的な実装では、個別に確保された固定長配列のシーケンスを追加の管理情報とともに使用する。これは、deque のインデックスアクセスがポインタのデリファレンスを2回実行する必要があることを意味するが、これに対して vector のインデックスアクセスは1回しか実行しない。

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

deque に対する一般的な操作の計算量(効率)は以下の通りである

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

std::deque は コンテナ(Container)、アロケータ認識コンテナ(AllocatorAwareContainer)、シーケンスコンテナ(SequenceContainer)、リバーシブルコンテナ(ReversibleContainer) の要件を満たす。

std::deque のすべてのメンバ関数は constexpr であり、定数式の評価中に std::deque オブジェクトを作成して使用することが可能である。 しかし、std::deque オブジェクトは一般的に constexpr にはなれない。なぜなら、動的に確保されたストレージはすべて、同じ定数式の評価中に解放されなければならないからである。

(C++26以降)

テンプレートパラメータ

T	-	要素の型。 T は コピー代入可能(CopyAssignable) と コピー構築可能(CopyConstructible) の要件を満たさなければならない。 (C++11まで) 要素に課される要件は、コンテナに対して実行される実際の操作に依存する。一般的に、要素型は完全な型であり、削除可能(Erasable) の要件を満たすことが要求されるが、多くのメンバ関数はより厳しい要件を課す。 (C++11以降)
アロケータ	-	メモリの確保/解放、およびそのメモリ内の要素の構築/破棄に使用されるアロケータ。この型は アロケータ(Allocator) の要件を満たさなければならない。Allocator::value_type が T と同じでない場合、その振る舞いは未定義である(C++20まで)プログラムは不適格となる(C++20から)。

イテレータの無効化

操作	無効になる条件
すべての読み取り専用操作。	なし。
swap, std::swap	過去終端イテレータが無効になることがある (実装定義)。
shrink_to_fit, clear, insert, emplace, push_front, push_back, emplace_front, emplace_back	常に。
erase	先頭で削除する場合 - 削除された要素のみ。 末尾で削除する場合 - 削除された要素と過去終端イテレータのみ。 それ以外の場合 - すべてのイテレータが無効になる。 過去終端イテレータがいつ無効になるかは未規定。(C++11まで) 過去終端イテレータも無効になる 削除された要素がコンテナの先頭にある場合を除く かつ、最後の要素が削除されない場合。 (C++11以降)
resize	新しいサイズが古いサイズより小さい場合 - 削除された要素と 過去終端イテレータのみ。 新しいサイズが古いサイズより大きい場合 - すべてのイテレータが無効になる。 それ以外の場合 - どのイテレータも無効にならない。
pop_front, pop_back	削除された要素へのイテレータ。 過去終端イテレータが無効になることがある (実装定義)。(C++11まで) 過去終端イテレータも無効になる。(C++11から)

無効化に関する注意

• dequeのどちらかの端に挿入する場合、参照は insert と emplace によって無効化されない。
• push_front, push_back, emplace_front, emplace_back は、deque の要素へのいかなる参照も無効化しない。
• dequeのどちらかの端で削除する場合、削除されなかった要素への参照は erase, pop_front, pop_back によって無効化されない。
• resize をより小さいサイズで呼び出しても、削除されなかった要素への参照は無効化されない。
• resize をより大きいサイズで呼び出しても、deque の要素への参照は無効化されない。

メンバ型

メンバ型	定義
value_type	T
allocator_type	Allocator
size_type	符号なし整数型 (通常は std::size_t)
difference_type	符号付き整数型 (通常は std::ptrdiff_t)
reference	value_type&
const_reference	const value_type&
pointer	Allocator::pointer (C++11まで) std::allocator_traits<Allocator>::pointer (C++11以降)
const_pointer	Allocator::const_pointer (C++11まで) std::allocator_traits<Allocator>::const_pointer (C++11以降)
iterator	value_type への LegacyRandomAccessIterator および ConstexprIterator(C++26から)
const_iterator	const value_type への LegacyRandomAccessIteratorおよび ConstexprIterator(C++26から)
reverse_iterator	std::reverse_iterator<iterator>
const_reverse_iterator	std::reverse_iterator<const_iterator>

メンバ関数

(コンストラクタ)	deque を構築する (公開メンバ関数)
(デストラクタ)	deque を破棄する (公開メンバ関数)
operator=	コンテナに値を代入する (公開メンバ関数)
代入する	コンテナに値を代入する (公開メンバ関数)
assign_range (C++23)	コンテナに値の範囲を代入する (公開メンバ関数)
get_allocator	関連付けられたアロケータを返す (公開メンバ関数)
要素アクセス
at	境界チェック付きで指定された要素にアクセスする (public メンバ関数)
operator[]	指定された要素にアクセスする (public メンバ関数)
front	最初の要素にアクセスする (public メンバ関数)
back	最後の要素にアクセスする (public メンバ関数)
イテレータ
begincbegin (C++11)	先頭へのイテレータを返す (public メンバ関数)
endcend (C++11)	末尾へのイテレータを返す (public メンバ関数)
rbegincrbegin (C++11)	先頭への逆イテレータを返す (public メンバ関数)
rendcrend (C++11)	末尾への逆イテレータを返す (public メンバ関数)
容量
empty	コンテナが空かどうかをチェックする (public メンバ関数)
size	要素数を返す (public メンバ関数)
max_size	可能な最大要素数を返す (public メンバ関数)
shrink_to_fit (DR*)	未使用のメモリを解放してメモリ使用量を削減する (公開メンバ関数)
変更
clear	内容をクリアする (公開メンバ関数)
insert	要素を挿入する (公開メンバ関数)
insert_range (C++23)	要素の範囲を挿入する (公開メンバ関数)
emplace (C++11)	要素を直接構築する (公開メンバ関数)
erase	要素を削除する (公開メンバ関数)
push_back	末尾に要素を追加する (公開メンバ関数)
emplace_back (C++11)	末尾に要素を直接構築する (公開メンバ関数)
append_range (C++23)	末尾に要素の範囲を追加する (公開メンバ関数)
pop_back	最後の要素を削除する (公開メンバ関数)
push_front	先頭に要素を挿入する (公開メンバ関数)
emplace_front (C++11)	先頭に要素を直接構築する (公開メンバ関数)
prepend_range (C++23)	先頭に要素の範囲を追加する (公開メンバ関数)
pop_front	最初の要素を削除する (公開メンバ関数)
resize	格納されている要素の数を変更する (公開メンバ関数)
swap	内容を交換する (public メンバ関数)

非メンバ関数

operator==operator!=operator<operator<=operator>operator>=operator<=> (C++20で削除)(C++20で削除)(C++20で削除)(C++20で削除)(C++20で削除)(C++20)	2つの deque の値を辞書式順序で比較する (関数テンプレート)
std::swap(std::deque)	std::swap アルゴリズムを特殊化する (関数テンプレート)
erase(std::deque)erase_if(std::deque) (C++20)	特定の基準を満たすすべての要素を削除する (関数テンプレート)

推論補助

(C++17以降)

ノート

機能テストマクロ	値	規格	機能
__cpp_lib_containers_ranges	202202L	(C++23)	コンテナのRangeコンストラクタとRange挿入
__cpp_lib_constexpr_containers	202502L	(C++26)	constexpr std::deque

例

このコードを実行

#include <deque>
#include <iostream>
 
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 << ' ';
    std::cout << '\n';
}

出力

13 7 5 16 8 25

欠陥報告

以下の動作変更を伴う欠陥報告が、以前に公開されたC++標準に遡って適用されました。

DR	適用対象	公開された動作	正しい動作
LWG 230	C++98	T は コピー構築可能(CopyConstructible) である必要はなかった (型 T の要素が構築できない可能性がある)	T は以下も要求される CopyConstructible であること

関連項目

queue

キュー (FIFO データ構造) を提供するためにコンテナを適応させる (クラステンプレート)