C#の Collection (コレクション) パッケージをくわしくみる
HashSet<T> と SortedSet<T> は数学で言う集合
- キーの存在しか見ないようなコレクションの場合は、
HashSet<T>を使う
SortedList<T> と SortedDictionary<T> の違い
O(1)＞O(log n)＞O(n)＞O(n log n)＞O(n2)
で、左ほど優秀（高速）だと思ってください。
List<T>
用途
- インデックスを使って要素を読み書きする場合に使います
- 特に、ランダム アクセスが必要な場合
計算量
- インデックスを使った読み書きはO(1)
- 末尾以外への要素の挿入や削除はO(n)
内部実装
- いわゆる配列リストです
- C++から来た人は名前で混乱しがちですが、C++でいうとvectorです
- あらかじめ大き目の配列を確保しておきます
- 要素が増えて、サイズが足りなくなったらより大きな配列を確保しなおします
LinkedList<T>
連結リスト（linked list）
用途
- 事前に大き目の領域を確保したくない場合や、要素数が大きく変わるので事前確保の量を決めにくい場合に使います
計算量
- このノードの後ろに要素を追加したいというような、位置が事前にわかっている場合の挿入や削除はどこでもO(1)
内部実装
- 双方向連結リストです
- {値、前のノードへの参照、後ろのノードへの参照} という情報を持つ「ノード」（node: 節）をつないで作ります
Stack<T>
スタック（stack: 積み荷）。要素を上に積み上げていく感じ。
用途
- いわゆるLIFO（last in first out）
- 後に入れた要素ほど先に出す
計算量
- 要素の出し入れ（末尾にしかできません）はO(1)
内部実装
- List
と同じ配列リストです
Queue<T>
キュー（queue: 待ち行列）。後ろに並んで、前から出ていく感じ。
用途
- FIFO（fist in first out）
- 先に入れた要素ほど先に出す
計算量
- 要素の出し入れ（末尾への挿入、先頭の削除）はO(1)
内部実装
- いわゆる循環バッファー（明日説明）です
- 事前に配列を確保しておいて、状況に応じて再確保しなおす仕組みは配列リストと同様です
Dictionary<TKey, TValue>
辞書（dictionary）の代表格。後述のSortedDictionaryやSortedListと、辞書という意味では同じですが、内部的な挙動が異なります。
用途
- メモリに余裕がある場合にはもっとも高速な辞書です
- 要素の型は、GetHashCodeメソッドを正しく定義している必要があります
- キーの順序は保たれません
計算量
- 事前に大きな領域を確保できれば、ほぼO(1)で挿入・検索・削除可能
- 逆に最悪の場合、O(n)になります
内部実装
- ハッシュ テーブル（明日説明）です
SortedDictionary<TKey, TValue>
用途
- 事前に大き目の領域を確保したくない場合や、要素数が大きく変わるので事前確保の量を決めにくい場合に使います
- キーの順序通りに要素を列挙できます
計算量
- 要素の挿入・検索・削除はO(log n)です
内部実装
- 二分探索ツリー（赤黒ツリー）です
SortedList<TKey, TValue>
用途
- 要素の挿入・削除よりも、検索の方が圧倒的に多い場合に使います
計算量
- 要素の挿入・削除はO(n)、検索はO(log n)
内部実装
- key用の配列と、value用の配列の2つを持っています
- ソート済みの配列に対する二分探索を使っています
- 配列は、配列リスト同様の再確保を行います
HashSet<T>
いわば、Dictionary<TKey, TValue>のセット（値が必要ない、キーだけの辞書）版です。
用途
- 他のセットとの使いわけとしてはDictionary<TKey, TValue>と同じ
計算量
- 事前に大きな領域を確保できれば、ほぼO(1)で挿入・検索・削除可能
- 逆に最悪の場合、O(n)になります
内部実装
- ハッシュ テーブルです
SortedSet<T>
いわば、SortedDictionary<TKey, TValue>のセット版です。
用途
- 他のセットとの使いわけとしては
SortedDictionary<TKey, TValue>と同じ
計算量
- 要素の挿入・検索・削除はO(log n)です
内部実装
- 二分探索ツリーです
