Поделиться через

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

Класс 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).
Использует меньше памяти, чем a 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> интерфейс.

См. также