SortedList コレクション型と SortedDictionary コレクション型

更新 : 2007 年 11 月

System.Collections.SortedList クラス、System.Collections.Generic.SortedList<TKey, TValue> ジェネリッククラス、および System.Collections.Generic.SortedDictionary<TKey, TValue> ジェネリッククラスは、IDictionary インターフェイスを実装する点において Hashtable クラスと Dictionary<TKey, TValue> ジェネリッククラスに似ていますが、キーによる並べ替え順序で自身の要素を維持し、ハッシュテーブルの O(1) 挿入と取得の特性はありません。この 3 つのクラスには、次のような共通の特徴があります。

3 つのすべてのクラスは、System.Collections.IDictionary インターフェイスを実装します。2 つのジェネリッククラスは、System.Collections.Generic.IDictionary<TKey, TValue> ジェネリックインターフェイスも実装します。

各要素は、列挙で使用できるようにキーと値の組み合わせになっています。

メモ :
SortedList 非ジェネリッククラスは列挙されると DictionaryEntry オブジェクトを返しますが、2 つのジェネリック型のクラスは KeyValuePair<TKey, TValue> オブジェクトを返します。

要素は System.Collections.IComparer の実装 (非ジェネリッククラスの SortedList) または System.Collections.Generic.IComparer<T> 実装 (2 つのジェネリッククラス) に基づいて並べ替えられます。
各クラスは、キーのみまたは値のみを含むコレクションを返すプロパティを提供します。

次の表に、2 つの並べ替えリストクラスと SortedDictionary<TKey, TValue> クラスの違いを示します。

SortedList 非ジェネリッククラスと SortedList<TKey, TValue> ジェネリッククラス	SortedDictionary<TKey, TValue> ジェネリッククラス
キーと値を返すプロパティにはインデックスが付けられるため、インデックスを使用して効率的に取得できます。	インデックスを使用して取得することはできません。
取得は O(log n) です。	取得は O(log n) です。
挿入と削除は一般に O(n) ですが、既に並べ替えられているデータの挿入は O(1) のため、各要素はリストの最後に追加されます。これは、サイズを変更する必要がないことを前提にしています。	挿入と削除は O(log n) です。
SortedDictionary<TKey, TValue> より使用するメモリが少なくなります。	SortedList 非ジェネリッククラスと SortedList<TKey, TValue> ジェネリッククラスより多くのメモリを使用します。

メモ :
対応するキーを含む値 (従業員 ID 番号を含む従業員レコードなど) に対しては、KeyedCollection<TKey, TItem> ジェネリッククラスから派生することによってリストの特性と辞書の特性を合わせ持つキー付きのコレクションを作成できます。

参照