Отсортированные типы коллекций

  • Статья

Класс 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>.

См. также