個々のコレクションクラスについて詳しく見ていく前に、.NET Frameworkで用意されているコレクションのいくつかと特徴をざっと見ていきます。 .NET Frameworkでは、以下の名前空間にコレクションクラスと関連するインターフェイスが配置されています。
- System.Collections名前空間
- 基本的な非ジェネリックなコレクションクラスと関連するインターフェイス
- System.Collections.Generic名前空間
- ジェネリックコレクションクラスと関連するインターフェイス
- System.Collections.Concurrent名前空間
- マルチスレッドでの操作を目的としたスレッドセーフなジェネリックコレクションクラスと関連するインターフェイス
- System.Collections.ObjectModel名前空間
- 独自にジェネリックコレクションクラスを実装するための基本クラス
- System.Collections.Specialized名前空間
- 特定用途に用いられるタイプセーフな非ジェネリックコレクションクラス
コレクションクラスの種類とインターフェイス
System.Collections以下の名前空間に配置されているコレクションクラスの種類を大まかに分けると次の4つに分類できます。
- コレクション
- 単純な要素の集まり
ICollection<T>やICollectionを実装するクラス - リスト
- コレクションの機能に加え、要素の入れ替えやインデックスによるアクセスができるコレクション
IList<T>やIListを実装するクラス - ディクショナリ
- キーによる要素へのアクセスが出来るコレクション
IDictionary<TKey, TValue>やIDictionaryを実装するクラス - セット(集合)
- 集合の概念を表すコレクション
ISet<T>(.NET Framework 4以降)を実装するクラス
上記のインターフェイスはすべてIEnumerable<T>およびIEnumerableを継承しているため、結果としてすべてSystem.CollectionsやSystem.Collections.Generic等の名前空間にあるコレクションクラスは列挙操作が可能になっています。
コレクションクラスの特徴
個々のコレクションクラスが実装するインターフェイスを見ることで、そのコレクションクラスの大まかな特徴が分かります。 以下の表はコレクションクラスの特徴と実装するインターフェイスを抜粋して表にまとめたものです(個々のクラスの解説にもリンクしています)。 あわせて、要素の取得・設定の操作と、挿入・削除の操作のオーダーをランダウの記号を用いて併記しています。 表中のnはコレクション内の要素数を表します。
コレクション、リストのクラスと特徴
配列(Array)はSystem.Collections名前空間には含まれないクラスですが、比較のため表中に含めています。
| クラス | データ構造 | インデックスによるアクセス | 要素の取得・設定 | 要素の挿入・削除 | 実装するインターフェイス |
|---|---|---|---|---|---|
| Array | リスト (固定長) | できる | O(1) | - | IList<T>, ICollection<T>, IList, ICollection |
| ArrayList | リスト (可変長) | できる | O(1) | O(n)*1 | IList, ICollection |
| List<T> | リスト (可変長) | できる | O(1) | O(n)*1 | IList<T>, IList, ICollection<T>, ICollection |
| Collection<T> | リスト (可変長) | できる | O(1) | O(n)*1 | IList<T>, IList, ICollection<T>, ICollection |
| LinkedList<T> | 双方向連結リスト | できない | O(1)*2 | O(1) | ICollection<T>, ICollection |
| Queue | キュー | できない | O(1)*3 | O(n)*1 | ICollection |
| Queue<T> | キュー | できない | O(1)*3 | O(n)*1 | ICollection (ICollection<T>は実装していない) |
| Stack | スタック | できない | O(1)*3 | O(n)*1 | ICollection |
| Stack<T> | スタック | できない | O(1)*3 | O(n)*1 | ICollection (ICollection<T>は実装していない) |
- *1
- 容量の拡張が不要で、かつ末尾への追加となる場合はO(1)となる。
- *2
- 取得・設定しようとするノードの位置が既知の場合。 ノードの検索はO(n)となる。
- *3
- Peek, Dequeue, Popなどの操作による取得の場合。 設定は出来ない。
ディクショナリのクラスと特徴
| クラス | インデックスによるアクセス | 要素のソート | 要素のキー | 要素の取得・設定 | 要素の挿入・削除 | 実装するインターフェイス |
|---|---|---|---|---|---|---|
| Hashtable | できない | されない | 独立した値 | O(1) | O(1)*2 | IDictionary, ICollection |
| Dictionary<TKey, TValue> | できない | されない | 独立した値 | ほぼO(1) | ほぼO(1)*2 | IDictionary<TKey, TValue>, IDictionary, ICollection<KeyValuePair<TKey, TValue>>, ICollection |
| SortedList | できる | される | 独立した値 | O(log n)*1 | O(n)*3 | IDictionary, ICollection |
| SortedList<TKey, TValue> | できる | される | 独立した値 | O(log n)*1 | O(n)*3 | IDictionary<TKey, TValue>, IDictionary, ICollection<KeyValuePair<TKey, TValue>>, ICollection |
| SortedDictionary<TKey, TValue> | できない | される | 独立した値 | O(log n) | O(log n) | IDictionary<TKey, TValue>, IDictionary, ICollection<KeyValuePair<TKey, TValue>>, ICollection |
| KeyedCollection<TKey, TItem> | できる | されない | 要素自身から取得 | O(1) | O(n)*4 | IList<TItem>, IList, ICollection<TItem>, ICollection |
| OrderedDictionary | できる | されない | 独立した値 | ? | ? | IOrderedDictionary, IDictionary, ICollection |
- *1
- 存在しないキーの要素を設定する場合はO(n)となる。
- *2
- 挿入により容量が拡張される場合はO(n)となる。
- *3
- 末尾への追加となる場合はO(log n)となる。
- *4
- 末尾への追加となる場合はO(1)となる。
セットのクラスと特徴
| クラス | インデックスによるアクセス | 要素のソート | 要素の挿入・削除 | 実装するインターフェイス |
|---|---|---|---|---|
| HashSet<T> | できない | されない | O(1)*1 | ISet<T>, ICollection<T> |
| SortedSet<T> | できない | される | O(1)*1 | ISet<T>, ICollection<T>, ICollection |
- *1
- 挿入により容量が拡張される場合はO(n)となる。