.NET Разработчик

День сто сорок шестой. #ЗаметкиНаПолях

Коллекции в C#

6. Сортировка коллекций

В .Net реализованы следующие основные типы отсортированных коллекций:

1. SortedSet<T>

Поддерживает отсортированный порядок, не влияя на производительность вставки и удаления. Повторяющиеся элементы не допускаются. Изменение отсортированных значений существующих элементов не поддерживается и может привести к неожиданному поведению. Потокобезопасная версия - ImmutableSortedSet<T>.



2. SortedList<TKey,TValue> и SortedDictionary<TKey,TValue>

SortedList<TKey, TValue> - это массив пар ключ/значение с поиском за время O(log n). В этом он похож на SortedDictionary<TKey, TValue>. Два класса имеют похожие объектные модели, и оба имеют время извлечения O(log n). Различаются они в использовании памяти и скорости вставки и удаления:

- SortedList использует меньше памяти.

- SortedDictionary быстрее вставляет и удаляет несортированные данные (O(log n) против O(n) для SortedList).

- Если список заполняется сразу из отсортированных данных, SortedList работает быстрее.

SortedList поддерживает эффективный индексированный поиск ключей и значений через коллекции, возвращаемые свойствами Keys и Values. Нет необходимости повторно создавать списки при обращении к свойствам, поскольку они являются просто оболочками для внутренних массивов ключей и значений. В следующем коде показано использование индексатора свойства Values для извлечения значения из отсортированного списка строк:

string v = mySortedList.Values[3];

Элементы SortedList могут быть извлечены как объекты KeyValuePair<TKey, TValue>, для SortedDictionary – как KeyValuePair<TKey, TValue> или как необобщённые объекты DictionaryEntry.

Объекты ключей должны быть неизменяемыми, если они используются в качестве ключей в SortedList или SortedDictionary. Каждый ключ в должен быть уникальным, не нулевым. Значение может быть нулевым, если TValue - ссылочный тип.

SortedList и SortedDictionary требуют реализации компаратора для сортировки и выполнения сравнений. Компаратор по умолчанию Comparer<T>.Default проверяет, реализует ли тип ключа IComparable<T>, и использует эту реализацию, если она доступна. Если нет, он проверяет, реализует ли тип ключа IComparable. Если тип ключа не реализует ни один из этих интерфейсов, вы можете указать параметр-компаратор, реализующий IComparer<T>, в перегруженной версии конструктора.

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

Оператор foreach перебирает объекты типа элементов в коллекции. Поскольку элементы SortedList и SortedDictionary являются парами ключ/значение, foreach перебирает элементы KeyValuePair<TKey, TValue>:

foreach (KeyValuePair<int, string> kvp в sortedList)

{

  Console.WriteLine("{0} = {1}", kvp.Key, kvp.Value);

}

Кроме того, можно использовать метод Sort для несортированных списков:

- Sort(IComparer<T> comparer)

Cортирует все элементы, используя указанный компаратор.

- Sort(int index, int count, IComparer<T> comparer)

Cортирует элементы в диапазоне (count элементов, начиная с index), используя указанный компаратор.

- Sort()

Сортирует все элементы, используя компаратор по умолчанию.

- Sort(Comparison<T> cmp)

Сортирует все элементы списка, используя делегат сравнения. Делегат сравнения вида int Comparison<in T>(T x, T y) должен возвращать значение меньше 0, если x<y, больше 0, если x>y и 0, если x=y.

Например:

var list = new List<int>{2,4,3,1};

// сортировка по возрастанию (по умолчанию)

list.Sort(); // 1,2,3,4

// используем лямбда-выражение для сортировки по убыванию

list.Sort((x,y) => y-x); // 4,3,2,1

Источник: https://docs.microsoft.com/ru-ru/dotnet/api/system.collections.generic