コンテナ クラス とは
「コンテナクラス」とは、クラス、構造体、POD（int 等のいわゆるプレーンな古い型; Plain Old Data）を複数入れることが出来る「入れ物」のことである。
通常、ひとつのコンテナに入る要素の型はすべて同一である。
C++ には多種多様なコンテナ クラスが用意されていて、それぞれに固有の特徴がある。
したがって、各クラスの特徴をよく理解し、ケースバイケースで賢く使い分けて欲しい。
コンテナクラスはたいてい begin(), end() メンバ関数を持ち、コンテナクラスが保持している要素への イテレータ を返す。
イテレータを介して、コンテナが保持している要素を参照することが出来る。
C++ には sort(), reverse() などの便利なアルゴリズムが多数用意されており、それらのアルゴリズムの関数は引数にイテレータを取ることが多い。
コンテナ クラス 一覧
| クラス名 | 概要 |
|---|---|
| vector | 最も基本的で、最もよく使われるコンテナクラス。動的配列・可変長配列とも呼ばれる。 |
| array * | 固定長配列 |
| deque | 両端キュー |
| list | 任意位置要素の挿入削除が高速なクラス。双方向リストとも呼ばれる。 |
| forward_list | 単方向リスト |
| map | キーと値のペアを保持するクラス。キーから値を取り出すのが O(log N) と高速。 連想配列とも呼ばれる。 |
| multimap | 重複可能な連想配列 |
| unordered_map * | ハッシュによる連想配列 |
| unordered_multimap * | ハッシュによる重複可能な連想配列 |
| set | 順序付集合 |
| multiset | 重複可能な集合（多重集合） |
| unordered_set * | ハッシュによる集合 |
| unordered_multiset * | ハッシュによる重複可能な集合（多重集合） |
* は C++11 で追加されたコンテナクラス
コンテナクラス特徴
- コンテナクラスのデータ構造は以下の4種類に分類出来る
- 配列：vector, array, deque
- リスト：list, forward_list
- 二分木（赤黒木）：map, multimap, set, multiset
- ハッシュテーブル：unordered_map, unordered_multimap, unordered_set, unordered_multiset
- 配列は、ランダム・アクセス：O(1)、挿入削除：O(N)、検索：O(N)
- ただし、ソート済み配列の二分探索は O(log N)
- リストは、ランダム・アクセス：O(N)、挿入削除：O(1)、検索：O(N)
- 二分木は、ランダム・アクセス：O(N)、挿入削除：O(log N)、検索：O(log N)
- ハッシュテーブルは、ランダム・アクセス：O(N)、挿入削除：O(1)、検索：O(1)
- set, map は、要素の重複を許さないものと許すものがある。後者には「multi」が付加される。
- 全てのコンテナクラスには、以下のメンバ関数が備わっている
- 「empty() : bool」 コンテナが空かどうかを判定
- 「size() : size_t」 コンテナに含まれる要素数
- 「clear() : void」 コンテナを空にする
- 「insert(イテレータ, 要素) または insert(要素)」 要素を挿入
- 「erase(イテレータ), erase(first, last)」 要素を削除
- 「x.swap(y)」コンテナの中身を交換
- 「begin() : イテレータ」 最初の要素へのイテレータを返す
- 「end() : イテレータ」最後の要素の次へのイテレータを返す
- 「cbegin() : イテレータ」 最初の要素への const なイテレータを返す
- 「cend() : イテレータ」 最後の要素の次への const なイテレータを返す
- 「rbegin() : イテレータ」 要素の並びを逆順にした時の、最初の要素へのイテレータを返す
- 「rend() : イテレータ」要素の並びを逆順にした時の、最後の要素の次へのイテレータを返す
- 「crbegin() : イテレータ」 要素の並びを逆順にした時の、最初の要素への const なイテレータを返す
- 「crend() : イテレータ」 要素の並びを逆順にした時の、最後の要素の次への const なイテレータを返す
- 「イテレータ」とは、コンテナの要素を指すポインタのようなものである
- *itr でイテレータの指す先を参照できる
- ++itr （または itr++）でイテレータを進めることが出来る
- --itr （または itr--）でイテレータを戻すことが出来る
- == 演算子で一致しているかどうかを判定できる
- 通常、> >= < <= 演算子でイテレータの大小比較を行なうことは不可
- 配列、リスト類は、「front()」で最初の、「back()」で最後の要素への参照を取得できる
- 配列、リスト類は、「push_back(値)」で最後に値を追加、「pop_back()」で最後の要素を削除できる
- vector, array 以外の配列、リスト類は、「push_front(値)」で最初に値を追加、「pop_front()」で最初の要素を削除できる
- 全ての要素に対する処理は以下のように記述出来る
コンテナクラス名<T> c;
c に要素を追加
for(auto itr = c.begin(); itr != c.end(); ++itr) {
*itr で要素にアクセス;
}
コンテナクラス名<T> c;
c に要素を追加
for(auto x : c) {
x の値を参照;
}