C++ コンテナ クラス入門
Copyright (C) 2014 by Nobuhide Tsuda

 

コンテナ クラス とは

「コンテナクラス」とは、クラス、構造体、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 で要素にアクセス;
        }
    
  • 範囲 for を使えば、以下のようにもっと簡潔に記述することが出来る。
  •     コンテナクラス名<T> c;
        c に要素を追加
        for(auto x : c) {
            x の値を参照;
        }