コレクション概要

概要

「データ構造」と呼ばれるものの代表格というと、 同じ型のデータをたくさん集めたもの、すなわちコレクションと呼ばれるものでしょう。

今の世の中、Java も C# も標準で、 List やら Dictionary やらいろいろなコレクションを持っています。 C++ も、1998年に標準化された STL と呼ばれるライブラリに、 一通りのコレクション（STL の流儀ではコンテナとも呼びます）が揃っています。

昔の人は結構な頻度でこの手のデータ構造を自作していました。 また、標準でその手のコレクションを利用できる現在においても、 どのコレクションの内部構造がどういう風になっているのか概要だけでも知っていれば、 どういうケースでどのコレクションを使うのが最適なのかがすぐに分かるという利点があります。

かなりの部分が STL の説明と被るので、 「単なるC# サンプルプログラム」みたいな扱いになりそうですが、 とにかく、コレクションについての説明をしていきたいと思います。

C++ のコレクション

1998年に標準化された STL（Standard Template Library）には多数のコレクションクラスが含まれています。 詳細は 「C++ STL」 で説明しますが、 C++ の STL は非常に高機能で、 現在の C++ では、ほとんどの場合、コレクションクラスを自作する必要がありません。

このページで説明を予定しているデータ構造で STL に含まれていないのは、 片方向連結リストとハッシュテーブルくらいです。 ちなみに、片方向連結リストはあまり利用する場面は多くありませんし、 ハッシュテーブルは探索木というデータ構造で代用が効きます。 また、C++ 標準には含まれていませんが、 STLport と呼ばれるライブラリ（STL の1実装）では、 ハッシュテーブルも実装されています。

C# のコレクション

.NET Framework には、 System.Collections 名前空間以下にコレクションクラスが用意されています。 C++ の STL と比べると、その機能はシンプルで、 特に需要の高いコレクションのみが揃っています。

STL と比べて欠けているのは、 deque、 priority_queue、 set および multiset に相当する物がないのと、 STL の iterator に相当する enumerator が、 forward iterator 相当の機能しか持っていないという点です。 これで困る場面はそれほど多くもないですが、 元々 C++ を使いこなしていた方には少々不満かもしれません。

C++/CLI （.NET Framework 向けに拡張された C++）専用で、 STL.NET というライブラリもありますが、 残念ながら C++/CLI からしか利用できません。

実装方法による分類

順序構造を保つコレクション

検索が高速なコレクション

用途による分類

要素の挿入・削除を一定ルールで行うコレクション

連想コレクション