C++編【標準ライブラリ】 第4章 STLコンテナ

このエントリーをはてなブックマークに追加

この章の概要

この章の概要です。

コンテナ

コンテナ(あるいはSTLコンテナ)は、 データの集まり(コレクション)を管理するクラステンプレート(【言語解説】第20章)で、以下のものがあります。

名称 概要 解説章
vector 動的な配列 第5章
list 双方向連結リスト 第6章
deque 両端待ち行列 第7章
set 重複を許可しないソートされた集合 第8章
multiset 重複を許可するソートされた集合 第8章
map 重複を許可しないキーと値のペアの集合 第9章
multimap 重複を許可するキーと値のペアの集合 第9章
basic_string
(string / wstring)
文字列 第2章

basic_string はやや毛色が違うかも知れませんが、文字の集まりを管理しているコンテナとみなすことができます。

また、これらのコンテナを内部的に使って実装されるクラステンプレートがあります。 これらはコンテナアダプタと呼ばれています。

名称 概要 解説章
stack スタック 第10章
queue 待ち行列 第11章
prioity_queue 優先度付き待ち行列 第12章

更に、STL におけるコンテナの要件は満たしていないものの、データの集まりという意味では共通なクラステンプレートがあります。

名称 概要 解説章
bitset ビット配列 第13章
valarray 数値配列 第33章

以上のコンテナ、およびそれに類するクラステンプレート達は、C++プログラミングを楽にする非常に実用度の高い機能群です。 (最後の valarray だけはかなり特殊なので、例外的に実用度は低いと言えます)。

C++11 (新たなコンテナ)

C++11 では、更に以下のコンテナが追加されました。 今のところ、個別の解説記事はありませんが、紹介だけしておきます。

名称 概要
array 固定サイズの配列
forward_list 単方向連結リスト
unordered_set ハッシュ値で管理され(順序を持たない)重複を許可しない、集合
unordered_multiset ハッシュ値で管理され(順序を持たない)重複を許可する、集合
unordered_map ハッシュ値で管理され(順序を持たない)重複を許可しない、キーと値のペアの集合
unordered_multimap ハッシュ値で管理され(順序を持たない)重複を許可する、キーと値のペアの集合
u16string / u32string
(basic_string の typename に追加)
UTF-16 および UTF-32 による文字列(第2章

コンテナの分類

コンテナは大きく分けると、シーケンスコンテナと連想コンテナに分類されます。

シーケンスコンテナは、要素が追加時の順序を保って管理されるタイプです。 つまり、直線的に要素が並んでいるイメージになります。 このタイプには、vector、list、deque、basic_string が該当します。

連想コンテナは、要素が追加時の順序を保たずに管理されるタイプです。 言い換えると、要素は直線的に並んでおらず、例えばソートされた状態で管理されます。 このタイプには、set、multiset、map、multimap が該当します。

勿論これらの分類は、どちらが優れているとかいうことではなく、単に特徴によって分類しただけです。

共通機能

すべてのコンテナに共通の機能が幾つかあります。

まず、必ず以下の3タイプのコンストラクタを持ちます。 以下、「Container」は任意のコンテナの型名が入ります。

Container c;                   // デフォルトコンストラクタ。空のコンテナを生成
Container c1(c2);              // コピーコンストラクタ。他のコンテナをコピー
Container c(itBegin, itEnd);   // 他のコンテナのある範囲をコピーして生成

c2 は c1 と同じ種類の別のコンテナです。
itBegin、itEnd はそれぞれイテレータ(第14章)で、コンテナ内の要素を指しています。 2つのイテレータによって、コンテナ内の範囲を表現しています。 例えば、イテレータは配列に対しても使えるため、配列の要素を使ってコンテナを初期化することができます。

int array[ARRAY_SIZE] = { 7, 5, 9, 2, 8 };
Container c(array, array + ARRAY_SIZE);

デストラクタも定義されています。 これは、コンテナの内部で確保されたすべてのメモリを解放します。 このおかげで、コンテナを使っていれば、メモリの解放忘れの可能性を大きく減らすことができます。

代入演算子が定義されており、同種のコンテナをコピーできます。

Container c1, c2;
c1 = c2;

2つのコンテナ間で、格納しているデータを交換する swapメンバ関数が定義されています。 また、std名前空間内にクラスに属さない通常の関数として swap関数(詳細は第15章を参照)が定義されており、 コンテナ同士の交換に使用できます。

Container c1, c2;

c1.swap(c2);
std::swap(c1, c2);

この例で、c2 はもう必要ないとすると「c1 = c2;」のように代入してしまうと、コンテナ全体のコピーが行われるので、 処理効率は良くありません。 swap の場合、コンテナ内部のデータを参照するポインタの交換だけで済むように実装されており、非常に効率的です。

コンテナに格納されている要素の数を、sizeメンバ関数で、 コンテナに格納可能な要素の最大数を、max_sizeメンバ関数で取得できます。 これらの関数の戻り値の型は「Container::size_type」で、各コンテナに typedef として用意されています。
また、コンテナが空かどうかは、emptyメンバ関数で調べることもできます。 空かどうかを調べる場合は、sizeメンバ関数よりも emptyメンバ関数を使う方が効率的なことがあるので、 優先的に emptyメンバ関数を使って下さい

例えば、C++03 の list では、sizeメンバ関数が連結リストを辿って要素数をカウントして返す実装をしている可能性があり、 この場合、かなり非効率になり得ます。ただし、C++11 では sizeメンバ関数をこのように実装することが事実上禁止されており、 emptyメンバ関数との効率の差は無くなりました。

Container c;

Container::size_type size = c.size();
Container::size_type maxSize = c.max_size();
bool isEmpty = c.empty();

コンテナ内の要素は、clearメンバ関数を使ってまとめて削除できます。

Container c;

c.clear();
assert(c.empty());  // clearメンバ関数の呼び出し直後は、emptyメンバ関数は必ず真を返す

イテレータを取得するための4つのメンバ関数が定義されています。 最初の要素を示すイテレータを返す beginメンバ関数、最後の要素の次を示すイテレータを返す endメンバ関数、 逆方向に走査する際の最初の要素を示す逆イテレータを返す rbeginメンバ関数、 逆方向に走査する際の最後の要素の次を示す逆イテレータを返す rendメンバ関数です。
イテレータについては、(第14章)で改めて取り上げます。

コンテナへ要素を挿入するために insertメンバ関数が定義されています。
コンテナは、要素のコピーを管理することに注意して下さい。 例えば、

Container c;

void func()
{
	int value = 10;
	c.insert(c.begin(), value);  // c の先頭に value のコピーを挿入
}

このようなプログラムを書いたとき、変数value はローカル変数ですが、 コンテナ c にはコピーが格納されているので、func関数を抜け出しても問題なく参照し続けられます。

コンテナから要素を削除するために eraseメンバ関数が定義されています。 これは、イテレータを使って、ある範囲内の要素をまとめて削除できるようになっています。

コンテナがメモリを確保するために使用するアロケータを取得する get_allocatorメンバ関数が定義されています。 アロケータについては、第32章で取り上げます。

比較用に、==、!=、<、<=、>、>= がそれぞれオーバーロードされています。 比較できるのは、型が同じコンテナ同士の場合に限られます。

C++11 の場合

C++11 の場合は少し違いがあります。

clearメンバ関数、insertメンバ関数、eraseメンバ関数が、array には定義されていません。 これは、array は静的で要素数固定の配列なので、要素数が変化することが無いためです。 これに関係していますが、array のデフォルトコンストラクタは、空のコンテナを生成せず、最初から要素が詰められた状態になります。
また、get_allocatorメンバ関数もありません。 動的なメモリ確保が起こらないため、アロケータが存在しないためです。

sizeメンバ関数が、forward_list には定義されていません。 C++11 では、sizeメンバ関数の計算量を O(1) で統一したいが(計算量については、アルゴリズムとデータ構造編【導入】第1章を参照)、 要素数を管理するメンバ変数を持たせた場合の、余分なメモリ使用量の増加は許容したくないという理由があります。
要素数が必要な場合は、beginメンバ関数と endメンバ関数が返すイテレータ間の距離を、std::distance関数(第14章)を使って計算します。

逆イテレータを返す rbeginメンバ関数、rendメンバ関数が、 forward_list、unordered_set、unordered_multiset、unordered_map、unordered_multimap には定義されていません。 forward_list は単方向連結リストなので逆方向には辿れませんし、残りの4種は順序という概念が無いので定義されていません。

要素に求める要件

コンテナの要素となるオブジェクトには、一定の要件が求められます。

まず、コンテナの要素は、コンテナの外部からコピーされて管理されるため、少なくともコピーが出来なければなりません。 具体的には、コピーコンストラクタと代入演算子 (==演算子) が「公開」されている必要があります
また、コピー操作によって、コピー元とコピー先が正確に等しくならなければなりません。 これは当たり前のように思えますが、コピーコンストラクタや代入演算子の実装によっては、等しくならない可能性があるので注意が必要です。

例えば、std::auto_ptr(第15章)は、コピー操作によってコピー元が破壊される特殊な実装になっています。 そのため、コンテナの要素としては不適格です。実際、使おうとするとコンパイルエラーになるはずです。

また、コンテナの要素を破棄するために、デストラクタが「公開」されていなければなりません

C++11 の場合

C++11 では、デフォルトコンストラクタが「公開」されていることが要件に追加されています。

C言語の配列

C言語の配列も、データの集まりであるという点ではコンテナの一種と言えますが、 STL のコンテナとしては要件を満たしていません。 そもそも、配列はクラスではないため、STLコンテナに共通のメンバ関数も使えません。

STLコンテナでは無いものの、STL の構成要素の1つである STLアルゴリズム(第18章)は適用できるようになっています。 また、もう1つの構成要素であるイテレータ(第14章)を利用することも考慮されています。 つまり、STL は配列のことを無視している訳ではありません。

C++11 には、array という STLコンテナが追加されており、配列の代わりとして使えます。 こちらはきちんと STLコンテナの要件を満たしています。


練習問題

この章の内容はあまり具体的でないので、練習問題はありません。

参考リンク

更新履歴

'2016/5/7 「コンテナの分類」での表現方法を修正。

'2014/11/9 新規作成。



前の章へ

次の章へ

C++編のトップページへ

Programming Place Plus のトップページへ