SortedList <>, SortedDictionary <> и словарь <>

Я нахожу, что SortedList<TKey, TValue> SortedDictionary<TKey, TValue> и Dictionary<TKey, TValue> реализуют те же интерфейсы.

Когда следует выбрать SortedList и SortedDictionary над Dictionary?
В чем разница между SortedList и SortedDictionary с точки зрения приложения?

Ответ 1

При повторении элементов в любом из двух элементов будут отсортированы. Не так с Dictionary<T,V>.
MSDN описывает разницу между SortedList<T,V> и SortedDictionary<T,V>:

Общий класс SortedDictionary (TKey, TValue) представляет собой двоичный поиск дерево с извлечением O (log n), где n - количество элементов в словарь. В этом отношении он похож на SortedList (TKey, TValue). Эти два класса имеют сходные объектные модели и оба имеют O (log n). Там, где два класса отличаются друг от друга, использование памяти и скорость вставки и удаления:

SortedList (TKey, TValue) использует меньше памяти, чем SortedDictionary (TKey, TValue).

SortedDictionary (TKey, TValue) имеет более быструю установку и удаление операции для несортированных данных: O (log n) в отличие от O (n) для SortedList (TKey, TValue).

Если список заполняется сразу из отсортированных данных, SortedList (TKey, TValue) быстрее, чем SortedDictionary (TKey, TValue).

Ответ 2

Я бы назвал разницу между словарями.

Над изображением показано, что Dictionary<K,V> равно или быстрее в каждом случае, чем Sorted аналоговый, но если требуется порядок элементов, например. для печати, Sorted выбирается один.

Src: http://people.cs.aau.dk/~normark/oop-csharp/html/notes/collections-note-time-complexity-dictionaries.html

Ответ 3

Если вы хотите, чтобы коллекция сортировалась по ключу, когда вы перебираете ее. Если вам не нужны ваши данные для сортировки, вам лучше всего использовать словарь, он будет иметь лучшую производительность.
SortedList и SortedDictionary в значительной степени выполняют одно и то же, но реализуются по-разному, поэтому имеют разные сильные и слабые стороны здесь объясняется.

Ответ 4

Чтобы суммировать результаты Performance Test - SortedList против SortedDictionary vs. Dictionary против Hashtable, результаты от самого лучшего до худшего для разных сценарии:

Использование памяти:

SortedList<T,T>
Hashtable
SortedDictionary<T,T>
Dictionary<T,T>

Вставки:

Dictionary<T,T>
Hashtable
SortedDictionary<T,T>
SortedList<T,T>

Операции поиска:

Hashtable
Dictionary<T,T>
SortedList<T,T>
SortedDictionary<T,T>

операции цикла foreach

SortedList<T,T>
Dictionary<T,T>
Hashtable
SortedDictionary<T,T>