Sorted コレクション型

  • [アーティクル]

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

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

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

並べ替えられたリストや辞書に複数のスレッドから同時にアクセスできる必要がある場合、ConcurrentDictionary<TKey,TValue> から派生するクラスに並べ替えロジックを追加できます。 不変にしたい場合は、ImmutableSortedSet<T> と ImmutableSortedDictionary<TKey,TValue> の対応する不変型に同様の並べ替えセマンティクスがあります。

Note

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

.NET Framework 4 以降の SortedSet<T> クラスのツリーは、挿入、削除、検索後、自らバランスを取り、順序を並べ替えデータを保持します。 このクラスと HashSet<T> クラスは、ISet<T> インターフェイスを実装します。

関連項目