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

トップページC++編

C++編で扱っている C++ は 2003年に登場した C++03 という、とても古いバージョンのものです。C++ はその後、C++11 -> C++14 -> C++17 -> C++20 と更新されており、今後も 3年ごとに更新されます。
なかでも C++11 での更新は非常に大きなものであり、これから C++ の学習を始めるのなら、C++11 よりも古いバージョンを対象にするべきではありません。特に事情がないなら、新しい C++ を学んでください。 当サイトでは、C++14 をベースにした新C++編を作成中です。

この章の概要

この章の概要です。


コンテナ

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

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

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

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

名称 概要 解説章
stack スタック [第10 章](010.html)
queue 待ち行列 [第11 章](011.html)
prioity_queue 優先度付き待ち行列 [第12章](01 2.html)

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

名称 概要 解説章
bitset ビット配列 [第13章 ](013.html)
valarray 数値配列 [第33 章](033.html)

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

コンテナの分類

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

シーケンスコンテナは、要素が追加時の順序を保って管理されるタイプです。つまり、直線的に要素が並んでいるイメージになります。このタイプには、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章で取り上げます。

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

要素に求める要件

コンテナの要素には、一定の要件を満たすことが求められます。

まず、コンテナの要素は、コンテナの外部からコピーされて管理されるため、少なくともコピーができなければなりません。具体的には、コピーコンストラクタと代入演算子 (==演算子) が「公開」されている必要があります

また、コピー操作によって、コピー元とコピー先が正確に等しくならなければなりません。これは当たり前のように思えますが、コピーコンストラクタや代入演算子の実装によっては、等しくならない可能性があるので注意が必要です。

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

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

C言語の配列

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

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


練習問題

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

参考リンク


更新履歴

’2018/2/22 「サイズ」という表記について表現を統一。 型のサイズ(バイト数)を表しているところは「大きさ」、要素数を表しているところは「要素数」。

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

’2014/11/9 新規作成。



前の章へ (第3章 pair)

次の章へ (第5章 vector)

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

Programming Place Plus のトップページへ



はてなブックマーク に保存 Pocket に保存 Facebook でシェア
X で ポストフォロー LINE で送る noteで書く
rss1.0 取得ボタン RSS 管理者情報 プライバシーポリシー
先頭へ戻る