目次

概要

コレクション（collection: データの「集まり」）を管理する方法には色々な種類があって、 それぞれ一長一短あります（目的に応じて使い分けます）。

.NET Framework の標準ライブラリにも、色々なコレクションを表すクラスが用意されています。 ここでは、どのコレクションをどういう場面で使えばいいのか、 ある程度勘所をつかめるように、 それぞれの挙動について簡単に説明していきます。

大まかな分類

コレクションには、大きく分けると3系統のものがあります。

ここで紹介するコレクションは、いずれも System.Collections.Generic 名前空間で定義されています。

リスト系

挿入した順序に意味があるコレクションです。 インデックスを使った（i 番目の要素の）読み書きができたり、 挿入した順序通りに要素を取り出せたりするタイプです。

List<T>, LinkedList<T>, Stack<T>, Queue<T> があります。

List<T>

用途 * インデックスを使って要素を読み書きする場合に使います * 特に、ランダム アクセスが必要な場合
計算量 * インデックスを使った読み書きは O(1) * 末尾以外への要素の挿入や削除は O(n)
内部実装 * 「配列リスト」です * C++から来た人は名前で混乱しがちですが、C++でいうとvectorです * あらかじめ大き目の配列を確保しておきます * 要素が増えて、サイズが足りなくなったらより大きな配列を確保しなおします

LinkedList<T>

用途 * 事前に大き目の領域を確保したくない場合や、要素数が大きく変わるので事前確保の量を決めにくい場合に使います
計算量 * このノードの後ろに要素を追加したいというような、位置が事前にわかっている場合の挿入や削除はどこでも O(1)
内部実装 * 「連結リスト」です * {値、前のノードへの参照、後ろのノードへの参照} という情報を持つ「ノード」（node: 節）をつないで作ります

Stack<T>

用途 * いわゆる LIFO（last in first out）です * 後に入れた要素を先に出す * 要素を上に積み上げていく（一番上をどけないと、次の要素を取り出せない）ので、 スタック（stack: 積み荷）と呼ぶ
計算量 * 要素の出し入れ（末尾にしかできません）は O(1)
内部実装 * 「配列リスト」です

Queue<T>

用途 * いわゆる FIFO（first in first out）です * 先に入れた要素を先に出す * 後ろに並んで、前から出ていくので、 キュー（queue: 待ち行列）と呼ぶ
計算量 * 要素の出し入れ（末尾への挿入、先頭の削除）は O(1)
内部実装 * 「循環バッファー」です * 事前に確保した領域で足りなくなった場合に配列の再確保が発生する点は、「配列リスト」と同じです

セット系

数学的な意味での集合（set）は、順序に意味を持ちません。 要素を含んでいるかどうかということにだけ意味があります。

プログラミング的にいうと、順序は狂っても構わないので、 要素の検索だけ高速にできてほしい場合があって、 そういうコレクションのことをセット（set: もちろん、数学的な意味での集合のこと）と呼びます。

HashSet<T>, SortedSet<T> があります。

HashSet<T>

用途 * メモリに余裕がある場合にはもっとも高速なセットです * 要素の型は、GetHashCode メソッドを正しく定義している必要があります * 要素の順序保証はありません
計算量 * 事前に大きな領域を確保できれば、ほぼ O(1) で挿入・検索・削除可能 * 逆に、確保した領域目いっぱいに要素が詰まり出すと、最悪の場合、O(n) になります
内部実装 * 「ハッシュ テーブル」です

SortedSet<T>

用途 * 事前に大き目の領域を確保したくない場合や、要素数が大きく変わるので事前確保の量を決めにくい場合に使います * 要素の大小によって整列した状態で要素を列挙できます
計算量 * 要素の挿入・検索・削除は O(log n) です
内部実装 * 「二分探索ツリー」です

辞書系

キーを指定して値を検索する必要がある場合に使うコレクションです。

「キーと値のペア」を要素とするセットを作ればいいので、内部的なアルゴリズムはセットと同じになります。 逆にいうと、セットは、値のない（キーのみの）辞書と考えることもできます。

Dictionary<TKey, TValue>, SortedDictionary<TKey, TValue>, SortedList<TKey, TValue> があります。

Dictionary<TKey, TValue>

用途 * HashSet の辞書版 * メモリに余裕がある場合にはもっとも高速なセットです * 要素の型は、GetHashCode メソッドを正しく定義している必要があります * キーによる順序保証はありません
計算量 * 事前に大きな領域を確保できれば、ほぼ O(1) で挿入・検索・削除可能 * 逆に、確保した領域目いっぱいに要素が詰まり出すと、最悪の場合、O(n) になります
内部実装 * 「ハッシュ テーブル」です

SortedDictionary<TKey, TValue>

用途 * SortedSet の辞書版 * 事前に大き目の領域を確保したくない場合や、要素数が大きく変わるので事前確保の量を決めにくい場合に使います * 要素の大小によって整列した状態で要素を列挙できます
計算量 * 要素の挿入・検索・削除は O(log n) です
内部実装 * 「二分探索ツリー」です

SortedList<TKey, TValue>

用途 * 要素の挿入・削除よりも、検索の方が圧倒的に多い場合に使います
計算量 * 要素の挿入・削除は O(n)、検索は O(log n)
内部実装 * 整列済み配列の「二分探索」です * 配列は、「配列リスト」と同様の再確保を行います

追記予定

その他、特殊系

BitArray

Concurrent 系

ObservableCollection も？

更新履歴

ブログ