.NETのコレクションまとめ 用途/計算量トレードオフ

title: .NETのコレクションまとめ 用途/計算量トレードオフ
url: http://csharptan.wordpress.com/2011/12/12/%e3%82%b3%e3%83%ac%e3%82%af%e3%82%b7%e3%83%a7%e3%83%b3/

snippet:

どのコレクションを使えば良いのかをトレードオフ

• 型名
• 用途
• 計算量
• 内部実装

-----引用-----
List<T>

• インデックスを使った読み書きはO(1)
• 末尾以外への要素の挿入や削除はO(n)
• あらかじめ大き目の配列を確保しておきます
• 要素が増えて、サイズが足りなくなったらより大きな配列を確保しなおします

LinkedList<T>

• 事前に大き目の領域を確保したくない場合や、要素数が大きく変わるので事前確保の量を決めにくい場合に使います

Stack<T>

• List<T>と同じ配列リストです

Queue<T>

• List<T>と同じ配列リストです

Dictionary<TKey, TValue>

• メモリに余裕がある場合にはもっとも高速な辞書です
• 要素の型は、GetHashCodeメソッドを正しく定義している必要があります
• 事前に大きな領域を確保できれば、ほぼO(1)で挿入・検索・削除可能
• 逆に最悪の場合、O(n)になります

SortedDictionary<TKey, TValue>

• 事前に大き目の領域を確保したくない場合や、要素数が大きく変わるので事前確保の量を決めにくい場合に使います
• 要素の挿入・検索・削除はO(log n)です
• 二分探索ツリー（赤黒ツリー）です

SortedList<TKey, TValue>

• 要素の挿入・削除よりも、検索の方が圧倒的に多い場合に使います
• 要素の挿入・削除はO(n)、検索はO(log n)

HashSet<T>
SortedSet<T>

同時実行（concurrent）系

• System.Collections.Concurrent名前空間に定義されています（.NET 4での追加）。

-----引用-----