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