名前空間
変種
操作

コンテナライブラリ

提供: cppreference.com
< cpp

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

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

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

目次

[編集] シーケンスコンテナ

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

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

[編集] 連想コンテナ

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

一意なキーによってソートされた、キーのコレクション
(クラステンプレート) [edit]
一意なキーによってソートされた、キー値ペアのコレクション
(クラステンプレート) [edit]
キーによってソートされた、キーのコレクション
(クラステンプレート) [edit]
キーによってソートされた、キー値ペアのコレクション
(クラステンプレート) [edit]

[編集] 非順序連想コンテナ

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

一意なキーによってハッシュされた、キーのコレクション
(クラステンプレート) [edit]
一意なキーによってハッシュされた、キー値ペアのコレクション
(クラステンプレート) [edit]
キーによってハッシュされた、キーのコレクション
(クラステンプレート) [edit]
キーによってハッシュされた、キー値ペアのコレクション
(クラステンプレート) [edit]

[編集] コンテナアダプタ

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

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

[編集] スパン

span はオブジェクトの隣接したシーケンスに対する非所有ビューです。 その記憶域は何らかの別のオブジェクトによって所有されます。

(C++20)
オブジェクトの隣接したシーケンスに対する非所有ビュー
(クラステンプレート) [edit]

[編集] イテレータの無効化

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

カテゴリ コンテナ 挿入後 削除後 条件
イテレータは有効か? 参照は有効か? イテレータは有効か? 参照は有効か?
シーケンスコンテナ 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::end は無効化されることは決してなく、 std::unordered_set::end は再ハッシュが発生した場合のみ無効化され、 std::vector::end は常に無効化される (変更された要素より常に後にあるので) といった感じです。

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

スレッド安全性

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

[編集] メンバ関数表

- C++03 に存在する関数
- C++11 およびそれ以降に存在する関数
- C++17 およびそれ以降に存在する関数
- C++20 およびそれ以降に存在する関数
シーケンスコンテナ 連想コンテナ 非順序連想コンテナ コンテナアダプタ
ヘッダ <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[]
data
data
data
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
contains
contains
contains
contains
contains
contains
contains
contains
contains
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
シーケンスコンテナ 連想コンテナ 非順序連想コンテナ コンテナアダプタ