目次

概要

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

今の世の中、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

更新履歴

ブログ