C++のコンテナライブラリは、データを効率的に格納および操作するための様々なクラスを提供します。これにより、プログラム内でデータを管理する際の作業が簡素化されます。
ヘッダー一覧
編集この章で扱うヘッダーファイルは以下の通りです。
要件
編集コンテナライブラリに挿入される要素は、一般的に以下の要件を満たす必要があります。
コピー可能であること
編集要素は、コンテナに挿入、コピー、移動される際にコピーされる必要があります。 コピー可能な型には、以下のものがあります。
- プリミティブ型 (
int
,float
,double
など) - ポインタ型
- 標準ライブラリで定義されているコピー可能な型 (例:
std::string
,std::vector
) - ユーザー定義型 (コピーコンストラクタと代入演算子を定義している場合)
破壊可能であること
編集要素は、不要になったときに解放される必要があります。 破壊可能な型には、以下のものがあります。
- デストラクタを持つ型
- 標準ライブラリで定義されている破壊可能な型 (例:
std::string
,std::vector
) - ユーザー定義型 (デストラクタを定義している場合)
比較可能であること
編集連想コンテナ (例:std::map
, std::set
) に挿入される要素は、比較演算子 (<
, >
, <=
, >=
, ==
, !=
) を用いて比較できる必要があります。 比較可能な型には、以下のものがあります。
- プリミティブ型 (
int
,float
,double
など) - 標準ライブラリで定義されている比較可能な型 (例:
std::string
,std::vector
) - ユーザー定義型 (比較演算子を定義している場合)
デフォルトコンストラクタを持つこと
編集コンテナは、要素のデフォルトコンストラクタを使用して新しい要素を生成することがあります。 従って、要素型はデフォルトコンストラクタを定義する必要があります。 デフォルトコンストラクタを持たない型は、コンテナライブラリの一部操作で使用できない場合があります。
代入演算子を持つこと
編集コンテナ内の要素は、コピーや移動操作によって更新されることがあります。 従って、要素型は代入演算子 (=
) を定義する必要があります。 代入演算子を持たない型は、コンテナライブラリの一部操作で使用できない場合があります。
例外
編集上記の要件は、コンテナライブラリの一般的な要件です。 一部のコンテナは、特殊な要件を持つ場合があります。 例えば、std::unique_ptr
は、移動可能であることのみを要件としています。
また、ユーザー定義型の場合は、コンテナライブラリで定義されている型と同じインターフェースを実装する必要があります。 例えば、std::vector
に挿入される要素は、イテレータを使用して反復可能である必要があります。
シーケンスコンテナ
編集シーケンスコンテナは、要素を順序に保持するコンテナです。要素の追加や削除、並び替えなどの操作を効率的に行うことができます。C++標準ライブラリには、以下のシーケンスコンテナが用意されています。
vector
- 動的配列。要素の追加や削除を効率的に行うことができます。
list
- 双方向連結リスト。要素の挿入や削除を効率的に行うことができます。
forward_list
- 一方向連結リスト。要素の挿入を効率的に行うことができます。
deque
- 両端キュー。先頭と末尾から要素の追加や削除を行うことができます。
array
- 固定長の配列。要素数はコンパイル時に決定する必要があります。
string
- 文字列。文字列の操作に特化した機能が用意されています。
シーケンスコンテナの共通機能
編集シーケンスコンテナには、以下の共通機能があります。
- 要素の取得
[]
演算子を使用して、要素にアクセスすることができます。- 要素の追加
push_back()
メンバ関数を使用して、要素を追加することができます。- 要素の削除
erase()
メンバ関数を使用して、要素を削除することができます。- 要素の反復
begin()
とend()
メンバ関数を使用して、コンテナ内の要素を反復処理するための反復子を取得することができます。- アルゴリズム
- 標準ライブラリに用意されているアルゴリズムを使用して、コンテナ内の要素を処理することができます。
シーケンスコンテナの選択
編集シーケンスコンテナを選択する際には、以下の要素を考慮する必要があります。
- 要素の追加や削除の頻度
- 要素の追加や削除を頻繁に行う場合は、
vector
またはlist
が適しています。 - ランダムアクセス
- 要素へのランダムアクセスが必要な場合は、
vector
またはarray
が適しています。 - メモリ使用量
- 固定長の配列である
array
は、他のシーケンスコンテナよりもメモリ使用量が少ない場合があります。
シーケンスコンテナの使用例
編集以下に、シーケンスコンテナの使用例を示します。
- C++
#include <iostream> #include <vector> auto main() -> int { // vector の作成 auto numbers = std::vector{1, 2, 3, 4, 5}; // 要素へのアクセス std::cout << numbers[0] << std::endl; // 1 を出力 // 要素の追加 numbers.push_back(6); // 要素の削除 numbers.erase(numbers.begin() + 2); // 要素の反復処理 for (auto const number : numbers) { std::cout << number << " "; } std::cout << std::endl; return 0; }
- この例では、
vector
を使用して、整数のシーケンスを作成、操作しています。
- まとめ
シーケンスコンテナは、C++ でよく使用されるデータ構造です。要素の追加や削除、並び替えなどの操作を効率的に行うことができます。シーケンスコンテナを選択する際には、要素の追加や削除の頻度、ランダムアクセス、メモリ使用量などの要素を考慮する必要があります。
連想コンテナ
編集連想コンテナは、要素をキーと値のペアで格納するコンテナです。 キーに基づいて要素にアクセスできるため、効率的な検索と挿入が可能です。 C++ 標準ライブラリには、以下の連想コンテナが用意されています。
std::map
編集map
は、キーと値のペアを順序付きで格納する連想コンテナです。 キーは、比較可能である必要があります。 キーの比較は、std::less
などの比較関数を使用して行われます。
- 主な操作
-
insert
:要素を挿入するerase
:要素を削除するfind
:キーに対応する要素を探すcount
:キーに対応する要素の数を数えるlower_bound
:あるキー以上の要素の最初を探すupper_bound
:あるキーを超える要素の最初を探す
- 例
- C++
#include <iostream> #include <map> #include <string> auto main() -> int { std::map<std::string, int> scores; scores["Alice"] = 90; scores["Bob"] = 80; scores["Charlie"] = 70; for (const auto& pair : scores) { std::cout << pair.first << ": " << pair.second << std::endl; } return 0; }
- 実行結果
Alice: 90 Bob: 80 Charlie: 70
- この例では、
map
を使用して学生の名前と点数のペアを格納しています。insert
メソッドを使用して要素を挿入し、範囲ベースのfor文を使って要素を順に参照しています。
std::multimap
編集multimap
は、キーと値のペアを順序付きで格納する連想コンテナです。 キーは、比較可能である必要があります。 キーの比較は、std::less
などの比較関数を使用して行われます。 同じキーを持つ複数の要素を格納することができます。
- 主な操作
-
insert
:要素を挿入するerase
:要素を削除するfind
:キーに対応する要素の範囲を探すcount
:キーに対応する要素の数を数えるlower_bound
:あるキー以上の要素の最初を探すupper_bound
:あるキーを超える要素の最初を探す
- 例
- C++
#include <iostream> #include <map> #include <utility> auto main() -> int { std::multimap<std::string, int> scores; scores.insert({"Alice", 90}); scores.insert({"Alice", 85}); scores.insert({"Bob", 80}); scores.insert({"Charlie", 70}); for (const auto& pair : scores) { std::cout << pair.first << ": " << pair.second << std::endl; } std::cout << std::endl; }
- 実行結果
Alice: 90 Alice: 85 Bob: 80 Charlie: 70
- この例は、
multimap
を使用して学生の名前と点数のペアを格納しています。insert
メソッドを使用して要素を挿入し、範囲ベースのfor文を使って要素を順に参照しています。
連想コンテナの選択
編集どの連想コンテナを使用するかは、以下の要素を考慮する必要があります。
- 順序
- 要素の順序を保持する必要がある場合は、
map
またはmultimap
を使用します。 順序が不要な場合は、unordered_map
またはunordered_multimap
を使用します。 - 重複
- 同じキーを持つ複数の要素を許可する必要がある場合は、
multimap
またはunordered_multimap
を使用します。 同じキーを持つ要素を 1 つだけ許可する場合は、map
またはunordered_map
を使用します。 - 検索速度
- 高速な検索が必要な場合は、
unordered_map
またはunordered_multimap
を使用します。 順序付きの検索が必要な場合は、map
またはmultimap
を使用します。
- まとめ
連想コンテナは、キーと値のペアを効率的に格納および検索するための強力なツールです。 適切な連想コンテナを選択することで、アプリケーションのパフォーマンスと使いやすさを向上させることができます。
無順序連想コンテナ
編集無順序連想コンテナは、キーと値のペアを格納するコンテナですが、キーの順序は保持されません。つまり、要素は挿入された順序ではなく、ランダムな順序で格納されます。無順序連想コンテナは、高速な検索と挿入を提供し、キーの順序が重要でない場合に適しています。
主な無順序連想コンテナ
編集C++標準ライブラリには、以下の無順序連想コンテナが用意されています。
std::unordered_map
- キーと値のペアを格納するハッシュテーブルです。
std::unordered_multimap
- キーと値のペアを格納するハッシュテーブルですが、同じキーを持つ複数の値を格納できます。
std::unordered_set
- キーのみを格納するハッシュテーブルです。
無順序連想コンテナの操作
編集無順序連想コンテナは、以下の操作をサポートしています。
insert()
- キーと値のペアを挿入します。
erase()
- キーに基づいて要素を削除します。
find()
- キーに基づいて要素を検索します。
count()
- 特定のキーを持つ要素の数をカウントします。
begin()
- 要素の最初のイテレータを取得します。
end()
- 要素の最後のイテレータを取得します。
std::unordered_map
編集unordered_map
は、キーと値のペアを非順序付きで格納する連想コンテナです。 キーは、ハッシュ関数を使用してハッシュ値に変換されます。 ハッシュ値に基づいて要素にアクセスするため、map
よりも高速に検索と挿入を行うことができます。
- 主な操作
-
insert
:要素を挿入するerase
:要素を削除するfind
:キーに対応する要素を探すcount
:キーに対応する要素の数を数えるat
:キーに対応する要素にアクセスする
- 例
- C++
#include <iostream> #include <string> #include <unordered_map> auto main() -> int { std::unordered_map<std::string, int> scores; scores["Alice"] = 90; scores["Bob"] = 80; scores["Charlie"] = 70; for (const auto& pair : scores) { std::cout << pair.first << ": " << pair.second << std::endl; } return 0; }
- 実行結果
Charlie: 70 Bob: 80 Alice: 90
- この例は、
unordered_map
を使用して学生の名前と点数のペアを格納しています。insert
メソッドを使用して要素を挿入し、範囲ベースのfor文を使って要素を順に参照しています。
std::unordered_multimap
編集unordered_multimap
は、キーと値のペアを非順序付きで格納する連想コンテナです。 キーは、ハッシュ関数を使用してハッシュ値に変換されます。 ハッシュ値に基づいて要素にアクセスするため、multimap
よりも高速に検索と挿入を行うことができます。 同じキーを持つ複数の要素を格納することができます。
- 主な操作
-
insert
:要素を挿入するerase
:要素を削除するfind
:キーに対応する要素の範囲を探すcount
:キーに対応する要素の数を数えるat
:キーに対応する要素にアクセスする
- 例
- C++
#include <iostream> #include <unordered_map> #include <utility> auto main() -> int { std::unordered_multimap<std::string, int> scores; scores.insert({"Alice", 90}); scores.insert({"Alice", 85}); scores.insert({"Bob", 80}); scores.insert({"Charlie", 70}); for (const auto& pair : scores) { std::cout << pair.first << ": " << pair.second << std::endl; } return 0; }
- 実行結果
Charlie: 70 Bob: 80 Alice: 85 Alice: 90
- この例は、
unordered_multimap
を使用して学生の名前と点数のペアを格納しています。insert
メソッドを使用して要素を挿入し、範囲ベースのfor文を使って要素を順に参照しています。
無順序連想コンテナの注意点
編集無順序連想コンテナを使用する際には、以下の点に注意する必要があります。
- キーの順序は保持されないため、ループ処理などで要素を順序的に処理したい場合は、
std::vector
などの順序付きコンテナを使用する必要があります。 - ハッシュテーブルは衝突が発生する可能性があるため、パフォーマンスはキーの散らし具合に依存します。
まとめ
編集無順序連想コンテナは、高速な検索と挿入を提供する便利なコンテナですが、キーの順序が重要でない場合にのみ使用してください。
コンテナアダプタ
編集コンテナアダプタとは、既存のコンテナクラスを利用して、新たなインターフェースや動作を提供するクラスのことです。これは、基本的なコンテナ(例えば、std::vector
や std::deque
)に新たな機能や制約を追加するためのラッパークラスとして機能します。C++の標準ライブラリには、いくつかの代表的なコンテナアダプタが含まれています。
主なコンテナアダプタ
編集- スタック(
std::stack
) -
- 用途
- LIFO(Last In, First Out、後入れ先出し)のデータ構造を提供します。
- 内部コンテナ
- デフォルトでは
std::deque
を使用しますが、std::vector
など他のシーケンスコンテナを使用することも可能です。 - 主な操作
push
(要素の追加)、pop
(要素の削除)、top
(最上位の要素へのアクセス)。
- キュー(
std::queue
) -
- 用途
- FIFO(First In, First Out、先入れ先出し)のデータ構造を提供します。
- 内部コンテナ
- デフォルトでは
std::deque
を使用しますが、他のシーケンスコンテナを使用することも可能です。 - 主な操作
push
(要素の追加)、pop
(要素の削除)、front
(先頭要素へのアクセス)、back
(末尾要素へのアクセス)。
- 優先度付きキュー(
std::priority_queue
) -
- 用途
- 常に優先度の高い要素を先に処理するデータ構造を提供します。
- 内部コンテナ
- デフォルトでは
std::vector
を使用し、ヒープ(通常は最大ヒープ)として機能します。 - 主な操作
push
(要素の追加)、pop
(最大または最小の要素の削除)、top
(最大または最小の要素へのアクセス)。
- フラットマップ(
std::flat_map
)およびフラットセット(std::flat_set
) -
- 用途
- ソートされた連続メモリにキーと値を格納するデータ構造を提供します。
- 内部コンテナ
- 通常、ソートされた
std::vector
を内部で使用します。 - 主な操作
insert
(要素の追加)、erase
(要素の削除)、find
(要素の検索)。
コンテナアダプタの利点
編集- 抽象化
- 内部実装の詳細を隠蔽し、単純なインターフェースを提供する。
- カスタマイズ
- 内部コンテナを柔軟に選択できる。
- 再利用性
- 既存のコンテナをラップすることで、新たなデータ構造を簡単に実装できる。
使用例
編集以下に std::stack
の簡単な使用例を示します。
#include <stack> #include <vector> #include <iostream> auto main() -> int { std::stack<int, std::vector<int>> stack; stack.push(1); stack.push(2); stack.push(3); std::cout << "Top element: " << stack.top() << std::endl; // 3 stack.pop(); std::cout << "Top element after pop: " << stack.top() << std::endl; // 2 return 0; }
このように、コンテナアダプタは既存のコンテナの力を借りて、新しい機能や動作を提供するために非常に有用です。
- <queue>, <stack>, <flat_map>, <flat_set> ヘッダの定義
- ヘッダファイル
<queue>
,<stack>
,<flat_map>
, および<flat_set>
には、それぞれqueue
、priority_queue
、stack
、flat_map
、flat_multimap
、flat_set
、flat_multiset
というコンテナアダプタが定義されています。
- ヘッダファイル
- コンテナアダプタのテンプレートパラメータ
- 各コンテナアダプタは、
Container
、KeyContainer
、またはMappedContainer
という名前のテンプレートパラメータを取ります。これらはアダプタが適用されるコンテナの型を示します。各コンテナアダプタには、これらのテンプレートパラメータへの参照を引数として取るコンストラクタが少なくとも1つあります。コンストラクタは参照引数として与えられたコンテナをコピーします。もしコンテナがアロケータを使用する場合、アダプタのコンストラクタには互換性のあるアロケータを渡すことができます。そうでない場合は、通常のコピーまたはムーブコンストラクションが使用されます。単一のコンテナテンプレートパラメータContainer
を取るコンテナアダプタについては、アダプタの最初のテンプレートパラメータT
はContainer::value_type
と同じ型を示す必要があります。
- 各コンテナアダプタは、
- 例外のスローに関する規則
- コンテナアダプタの
swap
関数は、そのアダプタのContainer
、KeyContainer
、MappedContainer
、またはCompare
オブジェクト(存在する場合)のswap
が例外をスローしない限り、例外をスローしません。
- コンテナアダプタの
- コンストラクタテンプレートのオーバーロード解決への参加禁止条件
- コンテナアダプタのコンストラクタテンプレートは、
InputIterator
テンプレートパラメータを持ち、そのパラメータに対して入力イテレータと見なされない型が推論される場合、オーバーロード解決に参加しません。
- コンテナアダプタのコンストラクタテンプレートは、
- イテレータの有効性に関する影響
- コンテナアダプタに
insert
、emplace
、およびerase
メンバーがある場合、それらのメンバーは、コンテナの対応するメンバーと同じように、イテレータ、参照、およびポインタの有効性に影響を与えます。 - 例
flat_map<Key, T>::insert
の呼び出しは、そのflat_map
のすべてのイテレータを無効にする可能性があります。
- コンテナアダプタに
- 推論ガイドのオーバーロード解決への参加禁止条件
- コンテナアダプタの推論ガイドは、次のいずれかに該当する場合、オーバーロード解決に参加しません:
InputIterator
テンプレートパラメータがあり、そのパラメータに入力イテレータと見なされない型が推論される。Compare
テンプレートパラメータがあり、そのパラメータにアロケータと見なされる型が推論される。Container
、KeyContainer
、またはMappedContainer
テンプレートパラメータがあり、そのパラメータにアロケータと見なされる型が推論される。Container
、KeyContainer
、MappedContainer
テンプレートパラメータがなく、Allocator
テンプレートパラメータがあり、そのパラメータにアロケータと見なされない型が推論される。Container
およびAllocator
テンプレートパラメータがあり、uses_allocator_v<Container, Allocator>
が偽である。KeyContainer
およびAllocator
テンプレートパラメータがあり、uses_allocator_v<KeyContainer, Allocator>
が偽である。KeyContainer
およびCompare
テンプレートパラメータがあり、is_invocable_v<const Compare&, const typename KeyContainer::value_type&, const typename KeyContainer::value_type&>
が有効な式でないか偽である。MappedContainer
およびAllocator
テンプレートパラメータがあり、uses_allocator_v<MappedContainer, Allocator>
が偽である。
- コンテナアダプタの推論ガイドは、次のいずれかに該当する場合、オーバーロード解決に参加しません:
- エクスポジション専用エイリアステンプレート
iter-value-type
、iter-key-type
、iter-mapped-type
、range-key-type
、およびrange-mapped-type
といったエクスポジション専用エイリアステンプレートは、コンテナアダプタの推論ガイドに登場することがあります。
- 追加のエクスポジション専用エイリアステンプレート
- 次のエイリアステンプレートは、コンテナアダプタの推論ガイドに登場することがあります:
template<class Allocator, class T> using alloc-rebind = // exposition only typename allocator_traits<Allocator>::template rebind_alloc<T>;
ビュー
編集ビュー(view)は、データコンテナの内容に対する非所有権的な抽象化を提供するオブジェクトです。ビューは、コンテナ自体を保持せず、既存のデータの上に軽量なアクセス手段を提供するためのもので、データのコピーや移動を行うことなく、そのデータに対する操作や処理を可能にします。C++20のレンジライブラリ(Ranges Library)におけるビューは、特に効果的に使われます。
24.7.1 一般 (views.general)
編集<span>
ヘッダー- ヘッダー
<span>
には、ビューとしてspan
が定義されています。span
は、固定サイズの連続したメモリブロックを表現するためのクラステンプレートです。
- ヘッダー
<mdspan>
ヘッダー- ヘッダー
<mdspan>
には、多次元ビューと相互作用するためのクラステンプレートmdspan
およびその他の機能が定義されています。mdspan
は、異なる次元のデータを効率的に操作するための多次元ビューを提供します。
- ヘッダー
ビューは、効率的なメモリ管理と安全なデータアクセスを提供するために設計されており、特にパフォーマンスが重要なアプリケーションにおいて強力なツールとなります。
([Category:C++|こんてならいふらり])