コンテナライブラリ

 

C++

言語

ヘッダ

コンセプト

言語サポートライブラリ

診断ライブラリ

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

文字列ライブラリ

コンテナライブラリ

アルゴリズムライブラリ

イテレータライブラリ

数値演算ライブラリ

入出力ライブラリ

ローカライゼーションライブラリ

正規表現ライブラリ(C++11)

アトミック操作ライブラリ(C++11)

スレッドサポートライブラリ(C++11)

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

技術仕様書

 

コンテナライブラリ

array (C++11)

vector

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

 

コンテナライブラリは、キュー、リスト、スタックのような一般的なデータ構造をプログラマが簡単に実装できるようなクラステンプレートとアルゴリズムの汎用のコレクションです。 コンテナはシーケンスコンテナ、連想コンテナ、非順序連想コンテナの3種類に分類され、それぞれ違った操作をサポートするよう設計されています。

コンテナは要素のために確保した記憶域空間を管理し、それらに直接またはイテレータ (ポインタに似た性質のオブジェクト) を通してアクセスするためのメンバ関数を提供します。

ほとんどのコンテナは少なくともいくつかのメンバ関数を共通して持っており、機能性を共有しています。 特定のアプリケーションに対してどのコンテナがベストかはその提供される機能性だけではなく、異なるワークロードに対する効率性にもよります。

シーケンスコンテナ

シーケンスコンテナはシーケンシャルアクセスが可能なデータ構造を実装しています。

array (C++11)	要素が隣接した静的な配列 (クラステンプレート)
vector	要素が隣接した動的な配列 (クラステンプレート)
deque	両端キュー (クラステンプレート)
forward_list (C++11)	片方向連結リスト (クラステンプレート)
list	双方向連結リスト (クラステンプレート)

連想コンテナ

連想コンテナは高速に (O(log n) の計算量で) 検索可能なソート済みのデータ構造を実装しています。

set	一意なキーによってソートされた、キーのコレクション (クラステンプレート)
map	一意なキーによってソートされた、キーと値のペアのコレクション (クラステンプレート)
multiset	キーによってソートされた、キーのコレクション (クラステンプレート)
multimap	キーによってソートされた、キーと値のペアのコレクション (クラステンプレート)

非順序連想コンテナ

非順序連想コンテナは高速に (償却 O(1)、ワーストケースでは O(n) の計算量で) 検索可能なソートされていない (ハッシュされた) データ構造を実装しています。

unordered_set (C++11)	一意なキーによってハッシュされた、キーのコレクション (クラステンプレート)
unordered_map (C++11)	一意なキーによってハッシュされた、キーと値のペアのコレクション (クラステンプレート)
unordered_multiset (C++11)	キーによってハッシュされた、キーのコレクション (クラステンプレート)
unordered_multimap (C++11)	キーによってハッシュされた、キーと値のペアのコレクション (クラステンプレート)

コンテナアダプタ

コンテナアダプタはシーケンシャルコンテナに対して異なるインタフェースを提供します。

stack	スタック (LIFO データ構造) を提供するためにコンテナを適合させます (クラステンプレート)
queue	キュー (FIFO データ構造) を提供するためにコンテナを適合させます (クラステンプレート)
priority_queue	優先度付きキューを提供するためにコンテナを適合させます (クラステンプレート)

イテレータの無効化

読み取りのみのメソッドはイテレータや参照を無効化しません。 コンテナの内容を変更するメソッドは、以下の表に示すように、イテレータや参照を無効化する場合があります。

カテゴリ	コンテナ	挿入後		削除後		条件
		イテレータは有効か?	参照は有効か?	イテレータは有効か?	参照は有効か?
シーケンスコンテナ	array	N/A		N/A
	vector	No		N/A		挿入が容量を変更する場合
		Yes		Yes		変更した要素の前
		No		No		変更した要素およびその後の要素
	deque	No	Yes	Yes (削除された要素は除く)		先頭または末尾の要素の変更
			No	No		途中の要素のみの変更
	list	Yes		Yes (削除された要素は除く)
	forward_list	Yes		Yes (削除された要素は除く)
連想コンテナ	set multiset map multimap	Yes		Yes (削除された要素は除く)
非順序連想コンテナ	unordered_set unordered_multiset unordered_map unordered_multimap	No	Yes	N/A		挿入により再ハッシュが発生した場合
		Yes		Yes (削除された要素は除く)		再ハッシュが発生しない場合

ここで、挿入は、コンテナに1個以上の要素を追加するあらゆるメソッドを指し、削除は、コンテナから1個以上の要素を削除するあらゆるメソッドを指します。

• 挿入メソッドの例としては std::set::insert, std::map::emplace, std::vector::push_back, std::deque::push_front などがあります。
  • std::unordered_map::operator[] もマップに要素を挿入する場合があるため挿入メソッドに数えられます。

• 削除メソッドの例としては std::set::erase, std::vector::pop_back, std::deque::pop_front, std::map::clear などがあります。
  • clear はすべてのイテレータと参照を無効化します。 すべての要素を削除するので、これも論理的には上記のルールに従います。

終端イテレータに関しては特に述べておく価値があります。 一般的にこのイテレータは、削除されない要素を指す普通のイテレータのように振る舞います。 そのため、 std::set::end は無効化されることは決してなく、 std::unordered_set::end は再ハッシュが発生した場合のみ無効化され、 std::vector::end は常に無効化される (変更された要素より常に後にあるので) といった感じです。

これにはひとつ例外があります。 std::deque の最後の要素の削除は終端イテレータを無効化します。 それがコンテナの削除された要素でなくとも (あるいは要素でさえなくとも) です。 std::deque のイテレータの一般的なルールと組み合わせると、 std::deque::end を無効化しない唯一の変更操作は、最初の要素を削除するもののみという結論になります。

スレッド安全性

すべてのコンテナの関数は、異なるコンテナに対しては異なるスレッドから並行的に呼ぶことができます。 より一般的に言えば、 C++ の標準ライブラリの関数は、その関数の引数 (this ポインタを含む) を通して直接または間接的にアクセス可能でない限り、オブジェクトを読み込みません。 すべての const メンバ関数は、同じコンテナに対して異なるスレッドから並行的に呼ぶことができます。 さらに、メンバ関数 begin(), end(), rbegin(), rend(), front(), back(), data(), find(), lower_bound(), upper_bound(), equal_range(), at() および、連想コンテナのものを除く operator[] は、スレッド安全性の意味においては const のように振る舞います (つまり、同じコンテナに対して異なるスレッドから並行的に呼ぶことができます)。 より一般的に言えば、 C++ 標準ライブラリの関数は、その関数の非 const 引数 (this ポインタを含む) を通して直接または間接的にアクセス可能でない限り、オブジェクトを変更しません。 std::vector<bool> を除き、同じコンテナの異なる要素は、異なるスレッドから並行的に変更できます (例えば、 std::future オブジェクトの vector は複数のスレッドから値を取得できます)。 イテレータの操作 (例えばイテレータのインクリメント) は、ベースとなるコンテナを読み込みますが、変更はせず、同じコンテナの他のイテレータに対する操作や const メンバ関数、あるいは要素からの読み込みと、並行的に実行することができます。 何らかのイテレータを無効化するコンテナ操作は、既存のイテレータに対するいかなる操作とも、並行的に実行することはできません。 たとえそのイテレータが無効化されなくともです。 同じコンテナの複数の要素は、それらの要素にアクセスすると規定されていないメンバ関数と、並行的に変更できます。 より一般的に言えば、 C++ 標準ライブラリの関数は、仕様で要求されていない限り、その引数を通して間接的にアクセス可能なオブジェクト (コンテナの他の要素を含む) を読み込みません。 いずれの場合でも、コンテナの操作は、 (アルゴリズムや他のあらゆる C++ 標準ライブラリの関数と同様に) ユーザに可視な結果を変えない限り、内部的に並列化されるかもしれません (例えば、 std::transform は並列化されるかもしれませんが、シーケンスの各要素を順番にアクセスすると規定されている std::for_each は並列化することはできません)。

(C++11およびそれ以降)

メンバ関数表

	- C++03に存在する関数
	- C++11およびそれ以降に存在する関数
	- C++17およびそれ以降に存在する関数

		シーケンスコンテナ					連想コンテナ				非順序連想コンテナ				コンテナアダプタ
ヘッダ		<array>	<vector>	<deque>	<forward_list>	<list>	<set>		<map>		<unordered_set>		<unordered_map>		<stack>	<queue>
コンテナ		array	vector	deque	forward_list	list	set	multiset	map	multimap	unordered_set	unordered_multiset	unordered_map	unordered_multimap	stack	queue	priority_queue
	コンストラクタ	(暗黙)	vector	deque	forward_list	list	set	multiset	map	multimap	unordered_set	unordered_multiset	unordered_map	unordered_multimap	stack	queue	priority_queue
	デストラクタ	(暗黙)	~vector	~deque	~forward_list	~list	~set	~multiset	~map	~multimap	~unordered_set	~unordered_multiset	~unordered_map	~unordered_multimap	~stack	~queue	~priority_queue
	operator=	(暗黙)	operator=	operator=	operator=	operator=	operator=	operator=	operator=	operator=	operator=	operator=	operator=	operator=	operator=	operator=	operator=
	assign		assign	assign	assign	assign
イテレータ	begin cbegin	begin cbegin	begin cbegin	begin cbegin	begin cbegin	begin cbegin	begin cbegin	begin cbegin	begin cbegin	begin cbegin	begin cbegin	begin cbegin	begin cbegin	begin cbegin
	end cend	end cend	end cend	end cend	end cend	end cend	end cend	end cend	end cend	end cend	end cend	end cend	end cend	end cend
	rbegin crbegin	rbegin crbegin	rbegin crbegin	rbegin crbegin		rbegin crbegin	rbegin crbegin	rbegin crbegin	rbegin crbegin	rbegin crbegin
	rend crend	rend crend	rend crend	rend crend		rend crend	rend crend	rend crend	rend crend	rend crend
要素アクセス	at	at	at	at					at				at
	operator[]	operator[]	operator[]	operator[]					operator[]				operator[]
	front	front	front	front	front	front										front	top
	back	back	back	back		back									top	back
容量	empty	empty	empty	empty	empty	empty	empty	empty	empty	empty	empty	empty	empty	empty	empty	empty	empty
	size	size	size	size		size	size	size	size	size	size	size	size	size	size	size	size
	max_size	max_size	max_size	max_size	max_size	max_size	max_size	max_size	max_size	max_size	max_size	max_size	max_size	max_size
	resize		resize	resize	resize	resize
	capacity		capacity								bucket_count	bucket_count	bucket_count	bucket_count
	reserve		reserve								reserve	reserve	reserve	reserve
	shrink_to_fit		shrink_to_fit	shrink_to_fit
変更	clear		clear	clear	clear	clear	clear	clear	clear	clear	clear	clear	clear	clear
	insert		insert	insert	insert_after	insert	insert	insert	insert	insert	insert	insert	insert	insert
	insert_or_assign								insert_or_assign				insert_or_assign
	emplace		emplace	emplace	emplace_after	emplace	emplace	emplace	emplace	emplace	emplace	emplace	emplace	emplace
	emplace_hint						emplace_hint	emplace_hint	emplace_hint	emplace_hint	emplace_hint	emplace_hint	emplace_hint	emplace_hint
	try_emplace								try_emplace				try_emplace
	erase		erase	erase	erase_after	erase	erase	erase	erase	erase	erase	erase	erase	erase
	push_front			push_front	push_front	push_front
	emplace_front			emplace_front	emplace_front	emplace_front
	pop_front			pop_front	pop_front	pop_front										pop	pop
	push_back		push_back	push_back		push_back									push	push	push
	emplace_back		emplace_back	emplace_back		emplace_back									emplace	emplace	emplace
	pop_back		pop_back	pop_back		pop_back									pop
	swap	swap	swap	swap	swap	swap	swap	swap	swap	swap	swap	swap	swap	swap	swap	swap	swap
	merge				merge	merge	merge	merge	merge	merge	merge	merge	merge	merge
	extract						extract	extract	extract	extract	extract	extract	extract	extract
リスト操作	splice				splice_after	splice
	remove				remove	remove
	remove_if				remove_if	remove_if
	reverse				reverse	reverse
	unique				unique	unique
	sort				sort	sort
検索	count						count	count	count	count	count	count	count	count
	find						find	find	find	find	find	find	find	find
	lower_bound						lower_bound	lower_bound	lower_bound	lower_bound
	upper_bound						upper_bound	upper_bound	upper_bound	upper_bound
	equal_range						equal_range	equal_range	equal_range	equal_range	equal_range	equal_range	equal_range	equal_range
観察	key_comp						key_comp	key_comp	key_comp	key_comp
	value_comp						value_comp	value_comp	value_comp	value_comp
	hash_function										hash_function	hash_function	hash_function	hash_function
	key_eq										key_eq	key_eq	key_eq	key_eq
アロケータ	get_allocator		get_allocator	get_allocator	get_allocator	get_allocator	get_allocator	get_allocator	get_allocator	get_allocator	get_allocator	get_allocator	get_allocator	get_allocator
コンテナ		array	vector	deque	forward_list	list	set	multiset	map	multimap	unordered_set	unordered_multiset	unordered_map	unordered_multimap	stack	queue	priority_queue
		シーケンスコンテナ					連想コンテナ				非順序連想コンテナ				コンテナアダプタ