概要

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

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

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

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

C++ のコレクション

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

C# のコレクション

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

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

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

実装方法による分類

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

名前	C++ STL	C# System.Collections
「配列リスト」	vector	List
「循環バッファ」	deque
「片方向連結リスト」	forward_list
「双方向連結リスト」	list	LinkedList

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

名前	C++ STL	C# System.Collections
「ソート済み配列」		SortedList
「ハッシュテーブル」	unordered_set, unordered_map	Dictionary, HashSet
「2分探索木」	set, map	SortedDictionary, SortedSet

用途による分類

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

名前	C++ STL	C# System.Collections
「スタック」	stack	Stack
「待ち行列」	queue	Queue
「優先度付き待ち行列」	priority_queue

連想コレクション

名前	C++ STL	C# System.Collections
「セット」	set, multiset, unordered_set, unordered_muliset	HashSet,　SortedSet
「辞書」	map, multimap, unordered_map, unordered_multimap	Dictionary, SortedDictionary, SortedList