Урок 37. Коллекция SortedList C#

Тридцать седьмая часть учебника по основам C# описывает использование класса SortedList (сортированный список). Эта коллекция словарей предоставляет гибрид типов Hashtable и Array; каждая запись представляет собой пару ключ / значение, отсортированную в соответствии с содержимым ключа.

Коллекция SortedList

Коллекция SortedList представляет собой гибрид структур данных Hashtable и Array . Это словарь, содержащий пары ключ / значение, которые автоматически сортируются в соответствии с данными в ключе. Это означает, что, в отличие от Hashtable, содержимое SortedList имеет определенный порядок и может быть доступно с помощью индексного номера, а также путем поиска ключа.

Вы можете подумать о том, что SortedList имеет два массива для хранения ключей и значений отдельно. По мере добавления элементов ключ вставляется в массив ключей в правильном месте для поддержания порядка сортировки. Значение вставляется в соответствующую позицию в массиве значений. Как и в случае с Hashtable, это сопряжение ключа и значения может быть доступно в качестве DictionaryEntry . Каждый словарь может иметь объекты для своего ключа и значения до тех пор, пока ключевая часть не является нулевой, является уникальной и поддерживает интерфейс IComparable, который позволяет сравнивать и сортировать элементы.

SortedList предоставляет дополнительную функциональность по сравнению с Hashtable из-за его способности быть адресованным по номеру индекса и из-за его автоматической сортировки. Следует отметить, что этот дополнительный функционал дает пониженную производительность.

Реализованные интерфейсы

Коллекция SortedList реализует интерфейсы IDictionary и ICollection. Это поведение описано в статье интерфейсы коллекции. В остальной части этой статьи описываются дополнительные функциональные возможности, предоставляемые SortedList.

Конструкторы

Класс SortedList предоставляет шесть конструкторов для создания экземпляра нового словаря. Первый - самый простой, не требующий никаких параметров. Новая, пустая коллекция создается с возможностью хранения нескольких элементов. При добавлении дополнительных элементов емкость коллекции автоматически удваивается. Он удваивается снова каждый раз, когда емкость превышена.

using System.Collections;
SortedList myList = new SortedList();

Если максимальное число элементов, которые будут храниться в списке сортировки, известно до создания коллекции, то эффективнее объявить емкость. Если размер занижен и заявленная вместимость превышена, то вместимость все равно будет удвоена для размещения дополнительных предметов. Чтобы объявить начальную емкость SortedList, емкость передается конструктору как целочисленный параметр.

SortedList myList = new SortedList(25);

Одной из ключевых особенностей коллекции SortedList является возможность автоматического упорядочивания по ключам. По умолчанию порядок сортировки основан на реализации интерфейса IComparer каждого ключа. Однако это можно переопределить с помощью альтернативного упорядочивания, передав компаратор конструктору. Использование IComparer-это сложный предмет, который выходит за рамки учебника для начинающих. Например, в следующем коде создается список сортировки, который выполняет сортировку ключей без учета регистра.

Примечание:при сортировке без учета регистра сами ключи нечувствительны к регистру. Это означает, что добавление ключей "abc" и " ABC " создает исключение, так как ключи не считаются уникальными.

SortedList myList = new SortedList(new CaseInsensitiveComparer());

Функциональность вышеуказанных двух конструкторов может быть объединена. Когда компаратор и начальная емкость SortedList должны быть указаны, оба могут быть переданы как параметры. Компаратор-это первый параметр, а емкость - второй.

SortedList myList = new SortedList(new CaseInsensitiveComparer(), 25);

В некоторых случаях у вас уже может быть коллекция словарей, которую вы хотите использовать для инициализации содержимого SortedList. Пятый конструктор создает и заполняет список сортировки, используя содержимое любой другой коллекции, реализующей IDictionary . В следующем примере содержимое хэш-таблицы используется для заполнения нового списка сортировки.

Hashtable myTable = new Hashtable();
myTable.Add("key1","value1");
SortedList myList = new SortedList(myTable);    

Наконец, вы можете заполнить список сортировки из содержимого существующего справочника, а также указать компаратор для упорядочивания элементов. Для этого передайте словарь в качестве первого параметра конструктора, а компаратор - в качестве второго.

Hashtable myTable = new Hashtable();
myTable.Add("key1","value1");
SortedList myList = new SortedList(myTable, new CaseInsensitiveComparer());

Добавление элемента

Все типы коллекций словарей, реализующие IDictionary, включают базовый метод Add для добавления нового элемента. Это поддерживается классом SortedList . Как описано выше, ключи должны быть уникальными и не могут быть пустыми. Повторяющиеся ключи вызывают исключение ArgumentException, чтобы быть брошенным. При попытке добавить ключ null возникает исключение ArgumentNullException.

SortedList myList = new SortedList();
 
myList.Add("key1","value1");
myList.Add("key1","value2");                // Duplicate: ArgumentException
myList.Add(null,"value2");                  // Null Key: ArgumentNullException

Обновление с помощью ключа

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

SortedList veg = new SortedList();
 
veg["cabbage"] = "Red";                     
veg["cabbage"] = "Savoy";                   
veg["potato"] = "King Edward";
veg["lettuce"] = "Iceberg";
veg["carrot"] = "Imperator";

Обновление с использованием индекса

Можно получить доступ к элементам в отсортированном списке, используя их индексы, а не с помощью ключей. В отличие от массива, вы не можете указать номер индекса в квадратных скобках; это вызовет конфликты между номерами индекса и числовыми ключами. Чтобы использовать номер индекса для изменения значения существующего элемента, вызывается метод SetByIndex. Метод имеет два параметра: первый-это порядковый номер обновляемой записи, второй-новое значение.

SortedList veg = new SortedList();
 
veg["cabbage"] = "Savoy";
veg["potato"] = "King Edward";
veg["lettuce"] = "Iceberg";
veg["carrot"] = "Imperator";
 
veg.SetByIndex(0, "Late Flat Dutch");       

Примечание: помните, что номер индекса не связан с порядком, в котором элементы были добавлены в коллекцию. Он основан на положениях элементов после сортировки. В приведенном выше примере обновление работает только потому, что мы знаем, что "капуста" является первым ключом при сортировке по алфавиту.

Удаление элемента

SortedList позволяет удалять элементы с помощью метода Remove. При этом из коллекции удаляется элемент, соответствующий указанному ключу. SortedList также предоставляет дополнительный метод, который удаляет элемент на основе его номера индекса. Это и есть метод RemoveAt.

SortedList veg = new SortedList();
 
veg["cabbage"] = "Savoy";
veg["potato"] = "King Edward";
veg["lettuce"] = "Iceberg";
veg["carrot"] = "Imperator";
 
veg.RemoveAt(0);

Чтение информации SortedList

Получение элемента по индексу

Коллекция SortedList является словарем и, как таковой, позволяет читать элемент, используя ключ в качестве ссылки. Кроме того, вы можете получить доступ к элементам SortedList по номеру индекса с помощью метода GetByIndex.

SortedList veg = new SortedList();
 
veg["cabbage"] = "Savoy";
veg["potato"] = "King Edward";
veg["lettuce"] = "Iceberg";
veg["carrot"] = "Imperator";
 
Console.WriteLine(veg.GetByIndex(0));       

Получение ключа по индексу

Кроме возможности получения значения из списка сортировки по номеру индекса, ключ также может быть найден таким образом. Метод GetKey использует аналогичный синтаксис для GetByIndex, требуя целочисленный параметр, удерживающий номер индекса для поиска.

SortedList veg = new SortedList();
 
veg["cabbage"] = "Savoy";
veg["potato"] = "King Edward";
veg["lettuce"] = "Iceberg";
veg["carrot"] = "Imperator";
 
Console.WriteLine(veg.GetKey(0));           

Итерация с использованием объектов DictionaryEntry

При добавлении элемента в список сортировки элементы ключа и значения объединяются в один объект DictionaryEntry. Используя инструкцию foreach, можно выполнить итерацию по каждому элементу и извлечь ключ и значение из объекта DictionaryEntry. В следующем примере выводятся сведения о каждой паре ключ / значение в консоль.

SortedList veg = new SortedList();
 
veg["cabbage"] = "Savoy";
veg["potato"] = "King Edward";
veg["lettuce"] = "Iceberg";
veg["carrot"] = "Imperator";
 
foreach(DictionaryEntry de in veg)
{
    Console.WriteLine("{0}\t: {1}", de.Key, de.Value);
}
 
/* вывод
 
cabbage : Savoy
carrot  : Imperator
lettuce : Iceberg
potato  : King Edward
 
*/

Values

Как и в случае с Хэштабами, сортированные списки содержат свойство Values, которое возвращает коллекцию значений в справочнике:

SortedList veg = new SortedList();
 
veg["cabbage"] = "Savoy";
veg["potato"] = "King Edward";
veg["lettuce"] = "Iceberg";
veg["carrot"] = "Imperator";
 
foreach(string value in veg.Values)
{
    Console.WriteLine(value);
}
 
/* вывод
 
Savoy
Imperator
Iceberg
King Edward
 
*/

Keys

Свойство Keys аналогично свойству Values. Он возвращает объект ICollection, содержащий все ключи элементов в списке сортировки.

SortedList veg = new SortedList();
 
veg["cabbage"] = "Savoy";
veg["potato"] = "King Edward";
veg["lettuce"] = "Iceberg";
veg["carrot"] = "Imperator";
 
foreach(string value in veg.Keys)
{
    Console.WriteLine(value);
}
 
/* вывод
 
cabbage
carrot
lettuce
potato
 
*/

Методы GetValueList и GetKeyList

Свойство Values возвращает коллекцию всех значений внутри отсортированного списка. Функциональные возможности этой коллекции ограничены интерфейсом ICollection. Метод GetValueList возвращает ту же информацию, что и значения в коллекции только для чтения, которая реализует интерфейс IList. Метод GetKeyList предоставляет ту же функциональность для ключей в списке сортировки. Эти методы полезны, потому что IList имеет более широкие возможности, чем ICollection.

SortedList veg = new SortedList();
 
veg["cabbage"] = "Savoy";
veg["potato"] = "King Edward";
veg["lettuce"] = "Iceberg";
veg["carrot"] = "Imperator";
 
IList keys = veg.GetKeyList();
IList values = veg.GetValueList();

ContainsKey

Все коллекции, реализующие IDictionary, включают метод с именем Contains, который возвращает логическое значение, указывающее, существует ли указанный ключ в коллекции. SortedList включает этот метод и другой с именем ContainsKey, который обеспечивает точно такую же функциональность.

ContainsValue

Помимо определения того, существует ли определенный ключ в пределах SortedList, может быть полезно проверить, происходит ли значение в коллекции. ContainsValue работает аналогично Contains и ContainsKey; объект для проверки передается как единственный параметр.

SortedList veg = new SortedList();
 
veg["cabbage"] = "Savoy";
veg["potato"] = "King Edward";
veg["lettuce"] = "Iceberg";
veg["carrot"] = "Imperator";
 
Console.WriteLine(veg.ContainsValue("Savoy"));          // вывод "True"
Console.WriteLine(veg.ContainsValue("Cos"));            // вывод "False"

IndexOfKey

Метод IndexOfKey улучшает метод ContainsKey. Вместо того, чтобы возвращать true или false, чтобы указать, существует ли указанный ключ, возвращается целочисленное значение. Если значение равно нулю или больше, то это индекс соответствующей записи ключа. Если ключ не найден, то метод возвращает значение -1.

SortedList veg = new SortedList();
 
veg["cabbage"] = "Savoy";
veg["potato"] = "King Edward";
veg["lettuce"] = "Iceberg";
veg["carrot"] = "Imperator";
 
Console.WriteLine(veg.IndexOfKey("potato"));            // "3"
Console.WriteLine(veg.IndexOfKey("parsnip"));           //  "-1"

IndexOfValue

Кроме того, чтобы иметь возможность найти ключ, можно найти индекс значения в пределах SortedList. Метод IndexOfValue возвращает номер индекса значения, соответствующего переданным критериям. Если значение не найдено, то результат равен -1. Если в коллекции имеется несколько вхождений значения, то возвращается индекс первого вхождения.

SortedList veg = new SortedList();
 
veg["cabbage"] = "Savoy";
veg["potato"] = "King Edward";
veg["lettuce"] = "Iceberg";
veg["carrot"] = "Imperator";
 
Console.WriteLine(veg.IndexOfValue("King Edward"));     // вывод "3"
Console.WriteLine(veg.IndexOfValue("Cos"));             // вывод "-1"

Размер SortedList

Как уже упоминалось ранее, при создании SortedList он имеет заданный размер. Размер может быть указан непосредственно в конструкторе, косвенно из-за способа инициализации SortedList или в качестве размера по умолчанию, который изменяется в зависимости от версии используемой платформы .NET framework.

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

Емкость объекта SortedList можно получить и изменить с помощью свойства Capacity. Это свойство содержит целое число.

SortedList myCollection = new SortedList();
 
int capacity = myCollection.Capacity;
Console.WriteLine("По умолчанию {0}", capacity);
 
myCollection.Capacity = 25;
capacity = myCollection.Capacity;
Console.WriteLine("Новая {0}", capacity);
 
/* Вывод
 
По умолчанию 16
Новая 25
 
*/

После того, как список сортировки будет полностью заполнен и никакие другие элементы не будут добавлены, память, выделенная для неиспользуемой части словаря, может быть восстановлена. Метод Trimmtosize задает емкость коллекции для соответствия текущему содержимому.

SortedList myCollection = new SortedList();
 
myCollection.Add("One", 1);
myCollection.Add("Two", 2);
myCollection.Add("Three", 3);
myCollection.Add("Four", 4);
myCollection.Add("Five", 5);
 
int capacity = myCollection.Capacity;
Console.WriteLine("Initial capacity is {0} items", capacity);
 
myCollection.TrimToSize();
capacity = myCollection.Capacity;
Console.WriteLine("New capacity is {0} items", capacity);
 
/* вывод
 
Initial capacity is 16 items
New capacity is 5 items
 
*/

Создание потокобезопасной оболочки SortedList

В предыдущей статье, посвященной интерфейсам коллекций, была описана концепция потокобезопасной синхронизированной коллекции. Для того чтобы создать потокобезопасный список сортировки, синхронизируемый словарь-оболочка создается с помощью статического метода Synchronized.

SortedList myDictionary = new SortedList();
SortedList myThreadSafe = SortedList.Synchronized(myDictionary);
Console.WriteLine(myThreadSafe.IsSynchronized);         // выведет "True"