Отсортированные типы коллекций
Класс System.Collections.SortedList, универсальный класс System.Collections.Generic.SortedList<TKey,TValue> и универсальный класс System.Collections.Generic.SortedDictionary<TKey,TValue> похожи на класс Hashtable и универсальный класс Dictionary<TKey,TValue> в том, что они реализуют интерфейс IDictionary, но сортировка элементов в них осуществляется по ключу. Кроме того, в них отсутствует возможность вставки O(1) и извлечения характеристик хэш-таблиц. Эти три класса имеют ряд схожих свойств:
Все три класса реализуют интерфейс System.Collections.IDictionary. Два универсальных класса также реализуют универсальный интерфейс System.Collections.Generic.IDictionary<TKey,TValue>.
Каждый элемент является парой ключ-значение для перечисления.
Примечание.
Неуниверсальный класс SortedList возвращает при перечислении объекты DictionaryEntry, несмотря на то, что два универсальных типа возвращают объекты KeyValuePair<TKey,TValue>.
Элементы сортируются в соответствии с реализацией System.Collections.IComparer (для неуниверсального класса SortedList) или с реализацией System.Collections.Generic.IComparer<T> (для двух универсальных классов).
Каждый класс предоставляет свойства, которые возвращают коллекции, содержащие только ключи или только значения.
В таблице ниже перечислены некоторые отличия между двумя классами отсортированных списков и классом 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>.
Примечание.
Для значений, содержащих собственные ключи (например, записи о сотрудниках, содержащие идентификационный номер сотрудника), вы можете создать коллекцию с ключами, имеющую некоторые характеристики списка и некоторые характеристики словаря. Для этого необходимо создать производный класс от универсального класса KeyedCollection<TKey,TItem>.
Начиная с .NET Framework 4, класс SortedSet<T> предоставляет самобалансируемое дерево, в котором после операций вставки, удаления или поиска данные сохраняются в отсортированном порядке. Этот класс и класс HashSet<T> реализуют интерфейс ISet<T>.
