Реализация интерфейса IComparer

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

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

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

1. Коллекции в .Net

В .NET коллекция представляет собой объект. Даже самый примитивный массив является объектом. Массив можно создать, у него есть методы и свойства, и как все другие классы, он является ссылочным типом.

Ниже представлен пример использования простой коллекции. Сначала создается список строк, а затем просматриваются строки с помощью оператора foreach.

Рассмотрим виды и типы коллекций.

1.1 Виды коллекций Коллекция — некоторая конечная совокупность объектов, с которой можно совершать те или иные действия. Так, обычно по отношению к коллекции можно осуществлять перебор ее элементов. Физические реализации коллекций могут быть совершенно разными. Во Framework Class Library (FCL) коллекции в основном размещаются в пространстве имен System.Collections. Их список приведен в таблице 1. [1]

интерфейс оператор коллекция итератор Таблица 1.1 — Коллекции, доступные в .NET Framework

В .NET Framework массив не относится к числу коллекций, хотя по своему предназначению массивы тоже являются коллекциями. Массивы отделены от коллекций потому, что они поддерживаются средой исполнения непосредственно. [1]

Типы коллекций.

Главное преимущество коллекций заключается в том, что они стандартизируют обработку групп объектов в программе. Все коллекции разработаны на основе набора четко определенных интерфейсов. Некоторые встроенные реализации таких интерфейсов, в том числе ArrayList, Hashtable, Stack и Queue, могут применяться в исходном виде и без каких-либо изменений. Имеется также возможность реализовать собственную коллекцию, хотя потребность в этом возникает крайне редко. [2]

В среде .NET Framework поддерживаются пять типов коллекций: необобщенные, специальные, с поразрядной организацией, обобщенные и параллельные. [2]

Необобщенные коллекции.

Необобщенные или простые коллекции определены в пространстве имен System.Collections. Их особенность состоит в том, что их функциональность, функциональные возможности описываются в интерфейсах, которые также находятся в этом пространстве имен. [3]

Специальные коллекции.

Оперируют данными конкретного типа или же делают это каким-то особым образом. Например, имеются специальные коллекции для символьных строк, а также специальные коллекции, в которых используется однонаправленный список. Специальные коллекции объявляются в пространстве имен System.Collections.Specialized. [2]

Поразрядная коллекция.

В прикладном интерфейсе Collections API определена одна коллекция с поразрядной организацией — это BitArray. Коллекция типа BitArray поддерживает поразрядные операции, т. е. операции над отдельными двоичными разрядами, например. И, ИЛИ, исключающее ИЛИ, а, следовательно, она существенно отличается своими возможностями от остальных типов коллекций. Коллекция типа BitArray объявляется в пространстве имен System.Collections. [2]

Обобщенные коллекции.

Классы обобщенных коллекций находятся в пространстве имен System.Collections.Generic. Функционал коллекций также по большей части описывается в обобщенных интерфейсах. [3]

Обеспечивают обобщенную реализацию нескольких стандартных структур данных, включая связные списки, стеки, очереди и словари. Такие коллекции являются типизированными в силу их обобщенного характера. Это означает, что в обобщенной коллекции могут храниться только такие элементы данных, которые совместимы по типу с данной коллекцией. Благодаря этому исключается случайное несовпадение типов. [2]

Параллельные коллекции.

Поддерживают многопоточный доступ к коллекции. Это обобщенные коллекции, определенные в пространстве имен System.Collections.Concurrent.

В листинге 1 (см. Приложение А) представлен пример использования коллекций, работы с элементами, добавление и удаление некоторых элементов. Приведенный пример взят из источника. Результат работы этой программы представлен на рисунке А.1 в приложении А.

В этой программе используются две коллекции: необобщенная — ArrayList и обобщенная — List.

ArrayList objectList = new ArrayList () { 1, 2, «string», 'c', 2.0f };

List countries = new List () { «Россия», «США», «Великобритания», «Китай» };

Большинство коллекций поддерживают добавление элементов. В данном примере добавление производится методом Add, но для других коллекций название метода может отличаться. [3]

objectList.Add («string2»);

Также большинство коллекций реализуют удаление, в этом примере удаление производится с помощью метода RemoveAt. [3]

objectList.RemoveAt (0); // удаление первого элемента С помощью свойства Count у коллекций можно посмотреть количество элементов. [3]

1.2 Интерфейсы, используемые коллекциями Классы коллекций в FCL в большинстве своем реализуют некоторый набор интерфейсов, представленный в таблице 1.2. [1]

Одной из отличительных особенностей FCL является то, что названия интерфейсов отражают описываемые ими абстракции. Точно так же названия классов отражают реализацию абстракций, определенных интерфейсами.

Например, абстракция «словарь» (по-другому ее еще называют map) описывается интерфейсом IDictionary и реализуется классами Hashtable и SortedList. Название класса Hashtable отражает, что в качестве основного алгоритма реализации в нем используется алгоритм хэш-таблицы, а в SortedList — сортированного массива. [1]

Таблица 1.2

Стандартные интерфейсы, реализуемые коллекциями в .NET

Кроме непосредственно реализуемых коллекциями интерфейсов, перечисленных в таблице 2, имеется также набор дополнительных интерфейсов, используемых коллекциями или возвращаемых ими. Их список приведен в таблице 1.3. [1]

Таблица 1.3 Дополнительные интерфейсы, используемые коллекциями

Интерфейс IEnumerable.

Все коллекции в FCL реализуют интерфейс IEnumerable. Этот интерфейс позволяет перебрать элементы коллекции в цикле. Интерфейс описывает всего один метод:

IEnumerator GetEnumerator ();

Этот метод возвращает ссылку на интерфейс IEnumerator (перечислитель), при помощи которого можно осуществить перебор всех элементов коллекции. Для одного экземпляра коллекции можно одновременно запросить несколько перечислителей. Поэтому такого понятия, как «текущий элемент», нет. [1]

Интерфейс IEnumerator.

Этот интерфейс предназначен для перебора значений коллекции. В состав этого интерфейса входят: MoveNext (), Reset () и свойство Current.

Reset () позволяет сбросить состояние перечислителя в начальное состояние. В этом состоянии перечислитель находится сразу после его создания, при этом переход к следующему элементу приведет к тому, что текущим элементом станет первый элемент коллекции. [1]

Метод MoveNext () как раз и осуществляет переход к следующему элементу коллекции. Таким образом, MoveNext () нужно вызывать непосредственно перед обращением к первому или следующему элементу.

Свойство Current предоставляет доступ к текущему элементу. [1]

Ниже представлен пример использования этого интерфейса.

IEnumerator enumerator = ((IEnumerable)someCollection).GetEnumerator ();

while (enumerator.MoveNext ())

{

ElemType elem = (ElemType)enumerator.Current ();

// … какие-то действия с элементом коллекции.

}

Любое изменение содержимого коллекции или количества ее элементов приводит к тому, что перечислитель становится недействительным. Так что если коллекция изменилась, попытка обратиться к методам или свойствам интерфейса IEnumerator должна вызвать исключение. Но эти интерфейсы — это всего лишь декларация намерений. Реализация интерфейсов целиком и полностью лежит на разработчиках конкретных классов. Так, все коллекции, входящие в пространство имен System. Collections, поддерживают это соглашение. Но IEnumerator реализуется также и встроенными массивами, которые этому правилу не удовлетворяют. [2]

Использовать связку IEnumerable/IEnumerator удобнее всего с помощью оператора foreach. Так, приведенный выше пример можно переписать следующим образом:

foreach (ElemType elem in someCollection)

{

// … какие-то действия с элементом коллекции.

}

Интерфейс ICollection

Интерфейс ICollection наследуется от IEnumerable:

public interface ICollection: Ienumerable

Он определяет свойство, при помощи которого можно получить число элементов коллекции:

int Count {get;}

Помимо этого свойства, интерфейс определяет метод:

void CopyTo (Array array, int index);

Задачей этого метода является копирование элементов коллекции в массив. Копирование производится, начиная с элемента, индекс которого указан как второй аргумент метода. Ссылка на массив передается в качестве первого параметра. Размер массива должен быть достаточным для размещения копируемых элементов. [1]

Свойство SyncRoot возвращает ссылку на объект, который должен использоваться для синхронизации доступа к объекту. Необходимость в таком объекте возникает при создании сложных коллекций. Ниже представлен пример использования свойства SyncRoot:

lock (myCollection.SyncRoot)

{

myCollection[0] = myCollection[1] + myCollection[2];

}

Для обеспечения корректной работы коллекции в многопоточной среде часто бывает удобно не делать синхронизацию вручную, а воспользоваться оберткой вокруг коллекции, обеспечивающей синхронизацию доступа к коллекции. Свойство IsSynchronized позволяет определить, нужна ли такая обертка имеющейся ссылке на коллекцию, или она уже и так потокобезопасна. [2]

Интерфейс IList.

Описанные выше методы и свойства позволяют просто «гонять» итераторы от одного элемента коллекции к другому, и узнавать количество элементов коллекции. Если не будут реализованы собственные методы доступа к данным коллекции, коллекцией пользоваться не удастся. Так вот, интерфейс IList предоставляет полиморфный механизм манипуляции данными коллекции:

public interface IList: ICollection, Ienumerable

В интерфейсе IList впервые встречается способ получить или присвоить какое-то значение элементу коллекции. Это делается с помощью индексатора:

object this[int index] { get; set; }

Аргументом в данном случае является индекс элемента. [1]

Чтобы добавить элемент в коллекцию, можно воспользоваться методом:

int Add (object value);

Метод должен вернуть индекс добавленного элемента. [1]

Если же необходимо вставить элемент в конкретное место коллекции, то можно использовать метод:

void Insert (int index, object value);

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

Чтобы удалить элемент, имеющий конкретное значение, можно использовать метод:

void Remove (object value);

Для удаления элемента по его индексу нужно воспользоваться методом:

void RemoveAt (int index);

Очистить коллекцию можно при помощи метода:

void Clear ();

Если нужно просто узнать, присутствует ли в коллекции элемент с заданным значением, можно воспользоваться методом:

bool Contains (object value);

Если же возникает задача узнать индекс объекта в коллекции, можно использовать метод IndexOf ():

int IndexOf (object value);

Свойство IsReadOnly позволяет узнать, предназначена ли коллекция только для чтения, то есть можно ли изменять число элементов коллекции и значения элементов. Свойство IsFixedSize помогает узнать, можно ли изменять число элементов коллекции после ее создания. [1]

IDictionary

Этот интерфейс описывает методы, которые должны быть у реализаций абстракции «словарь» (ассоциативной коллекции — хранящей пары ключ/значение). Ниже в таблице 1.4 представлены свойства интерфейса IDictionary, в таблице 1.5 — методы интерфейса IDictionary. [1]

Таблица 1.4 — Свойства интерфейса IDictionary

Таблица 1.5 — Методы интерфейса IDictionary

Хотя интерфейс IDictionary объявляется производным от Enumerable и переход к следующему элементу может осуществляться методом MoveNext, обычно такая возможность не используется — коллекции, реализующие IDictionary, ориентируются в первую очередь на обращение по ключу, а не на последовательный перебор элементов. По этой причине интерфейс IDictionary зависит от интерфейса IDictionaryEnumerator, который расширяет Enumerator и дополняет его тремя новыми свойствами:

Entry: возвращает пару «ключ/значение» для текущего элемента словаря.

Key: возвращает текущий ключ.

Value: возвращает ссылку на текущее значение.

2. Необобщенные коллекции Необобщенные коллекции вошли в состав среды .NET Framework еще в версии 1.0. Они определяются в пространстве имен System.Collections.

Необобщенные коллекции представляют собой структуры данных общего назначения, оперирующие ссылками на объекты. Таким образом, они позволяют манипулировать объектом любого типа, хотя и не типизированным способом. В этом состоит их преимущество и в то же время недостаток. Благодаря тому, что необобщенные коллекции оперируют ссылками на объекты, в них можно хранить разнотипные данные. Это удобно в тех случаях, когда требуется манипулировать совокупностью разнотипных объектов или же когда типы хранящихся в коллекции объектов заранее неизвестны. Но если коллекция предназначается для хранения объекта конкретного типа, то необобщенные коллекции не обеспечивают типовую безопасность, которую можно обнаружить в обобщенных коллекциях. [3]

Необобщенные коллекции определены в ряде интерфейсов и классов, реализующих эти интерфейсы. [2]

Интерфейсы необобщенных коллекций В пространстве имен System. Collections определен целый ряд интерфейсов необобщенных коллекций. Начинать рассмотрение необобщенных коллекций следует именно с интерфейсов, поскольку они определяют функциональные возможности, которые являются общими для всех классов необобщенных коллекций. Интерфейсы, служащие опорой для необобщенных коллекций, сведены в таблице 2. [2]

Таблица 2 — Интерфейсы, используемые в необобщенных коллекциях

Структура DictionaryEntry

В пространстве имен System. Collections определена структура DictionaryEntry. Необобщенные коллекции пар «ключ-значение» сохраняют эти пары в объекте типа DictionaryEntry. В данной структуре определяются два следующих свойства:

public object Key { get; set; }

public object Value { get; set; }

Эти свойства служат для доступа к ключу или значению, связанному с элементом коллекции. Объект типа DictionaryEntry может быть сконструирован с помощью конструктора:

public DictionaryEntry (object key, object value)

где key обозначает ключ, a value — значение. [2]

Классы необобщенных коллекций Ниже приведены классы необобщенных коллекций: [2]

ArrayList

Определяет динамический массив, т. е. такой массив, который может при необходимости увеличивать свой размер.

Hashtable

Определяет хеш-таблицу для пар «ключ-значение» .

Queue

Определяет очередь, или список, действующий по принципу «первым пришел — первым обслужен» .

SortedList

Определяет отсортированный список пар «ключ-значение» .

Stack

Определяет стек, или список, действующий по принципу «первым пришел — последним обслужен» .

3. Обобщенные коллекции Обобщенные коллекции — это те же самые обобщенные классы. Использование их перед необобщенными коллекциями имеет следующие преимущества: повышение производительности (не надо тратить время на упаковку и распаковку объекта) и повышенная безопасность. Классы обобщенных коллекций находятся в пространстве имен System.Collections. Generic. Функционал коллекций по большей части описывается в обобщенных интерфейсах. [4]

Необобщенные коллекции обычно предназначены для оперирования над типами System. Object и, таким образом, являются слабо типизированными контейнерами (тем не менее, некоторые необобщенные коллекции работают только со специфическим типом данных, таким как объекты string). В противоположность этому, обобщенные коллекции являются намного более безопасными к типам, учитывая, что требуется указывать «тип типа», который они будут содержать после создания. Признаком любого обобщенного элемента является наличие «параметра типа», обозначаемого с помощью угловых скобок (например, List). [6]

Параметр T в угловых скобках называется универсальным параметром, так как вместо него можно подставить любой тип. [3]

Интерфейсы обобщенных коллекций отличаются от необобщенных двойников не только наличием универсального параметра T, но и самой функциональностью. В таблице 2 представлены основные интерфейсы обобщенных коллекций. 2]

Таблица 2 — Интерфейсы обобщенных коллекций

Ниже, в таблице 3, представлены классы коллекций в пространстве имен System.Collections.Generic, которые реализуют интерфейсы, описанные в предыдущей таблице. [4]

Таблица 3 — Классы коллекций

Большинство обобщенных классов коллекций дублируют необобщенные классы коллекций. Но если не надо хранить объекты разных типов, то предпочтительнее использовать обобщенные коллекции. 3]

3.1 Основные обобщенные коллекции Список List

Класс List представляет простейший список однотипных объектов.

Среди его методов можно выделить следующие:

1) void Add (T item): добавление нового элемента в список;

2) void AddRange (ICollection collection): добавление в список коллекции или массива;

3) int BinarySearch (T item): бинарный поиск элемента в списке. Если элемент найден, то метод возвращает индекс этого элемента в коллекции. При этом список должен быть отсортирован;

4) int IndexOf (T item): возвращает индекс первого вхождения элемента в списке;

5) void Insert (int index, T item): вставляет элемент item в списке на позицию index;

6) bool Remove (T item): удаляет элемент item из списка, и если удаление прошло успешно, то возвращает true;

7) void RemoveAt (int index): удаление элемента по указанному индексу index;

8) void Sort (): сортировка списка.

В листинге 2 (см. Приложение А) представлен пример программы, реализующей список List заимствованный из источника.

В нем создаются два списка: один для объектов типа int, а другой — для объектов Person. В первом случае выполняется начальная инициализация списка: List numbers = new List () {1, 2, 3, 45};

Во втором случае используется другой конструктор, в который передается начальная емкость списка: List persons = new List (3).

Указание начальной емкости списка (capacity) позволяет в будущем увеличить производительность и уменьшить издержки на выделение памяти при добавлении элементов. Также начальную емкость можно установить с помощью свойства Capacity, которое имеется у класса List. [3]

Очередь Queue

Класс Queue представляет обычную очередь, работающую по алгоритму FIFO («первый вошел — первый вышел»). [3]

У класса Queue можно отметить следующие методы:

1) Dequeue: извлекает и возвращает первый элемент очереди;

2) Enqueue: добавляет элемент в конец очереди;

3) Peek: просто возвращает первый элемент из начала очереди без его удаления.

В листинге 3 представлен пример программы из источника [3], использующей класс Queue. Результат работы программы представлен на рисунке А.2. На рисунке 1 показано представление очереди.

Рисунок 1 — Очередь Queue

Стек Stack

Класс Stack представляет коллекцию, которая использует алгоритм LIFO («последний вошел — первый вышел»). При такой организации каждый следующий добавленный элемент помещается поверх предыдущего. Извлечение из коллекции происходит в обратном порядке — извлекается тот элемент, который находится выше всех в стеке. [3]

В классе Stack можно выделить два основных метода, которые позволяют управлять элементами. [3]

1) Push: добавляет элемент в стек на первое место;

2) Pop: извлекает и возвращает первый элемент из стека;

3) Peek: просто возвращает первый элемент из стека без его удаления.

Работу стека можно представить следующей иллюстрацией, представленной на рисунке 2.

Рисунок 2 — Стек Stack

Двухсвязный список LinkedList

Класс LinkedList представляет двухсвязный список, в котором каждый элемент хранит ссылку одновременно на следующий и на предыдущий элемент. [3]

Если в простом списке List каждый элемент представляет объект типа T, то в LinkedList каждый узел представляет объект класса LinkedListNode.

Этот класс имеет следующие свойства: [3]

Value: само значение узла, представленное типом T

Next: ссылка на следующий элемент типа LinkedListNode в списке. Если следующий элемент отсутствует, то имеет значение null

Previous: ссылка на предыдущий элемент типа LinkedListNode в списке. Если предыдущий элемент отсутствует, то имеет значение null

Используя методы класса LinkedList, можно обращаться к различным элементам, как в конце, так и в начале списка: [3]

1) AddAfter (LinkedListNode node, LinkedListNode newNode): вставляет узел newNode в список после узла node;

2) AddAfter (LinkedListNode node, T value): вставляет в список новый узел со значением value после узла node;

3) AddBefore (LinkedListNode node, LinkedListNode newNode): вставляет в список узел newNode перед узлом node;

4) AddBefore (LinkedListNode node, T value): вставляет в список новый узел со значением value перед узлом node;

5) AddFirst (LinkedListNode node): вставляет новый узел в начало списка;

6) AddFirst (T value): вставляет новый узел со значением value в начало списка;

7) AddLast (LinkedListNode node): вставляет новый узел в конец списка;

8) AddLast (T value): вставляет новый узел со значением value в конец списка;

9) RemoveFirst (): удаляет первый узел из списка. После этого новым первым узлом становится узел, следующий за удаленным;

10) RemoveLast (): удаляет последний узел из списка.

Пример использования списка LinkedList, заимствованный из источника [3], представлен в листинге 4 (см. Приложении А).

В нем создаются и используются два списка: для чисел и для объектов класса Person. [3]

Класс LinkedList представляет собой двухсвязный список, в котором каждый элемент ссылается на следующий и предыдущий, как показано на рисунке 1.

Рисунок 3 — Класс LinkedList

Словарь Dictionary

Еще один распространенный тип коллекции представляют словари. Словарь хранит объекты, которые представляют пару ключ-значение. Каждый такой объект является объектом класса KeyValuePair. Благодаря свойствам Key и Value, которые есть у данного класса, мы можем получить ключ и значение элемента в словаре. [2]

Пример использования словарей из источника представлен в листинге 5 (см Приложение А).

Класс словарей также как и другие коллекции, предоставляет методы Add и Remove для добавления и удаления элементов. Только в случае словарей в метод Add передаются два параметра: ключ и значение. А метод Remove удаляет не по индексу, а по ключу. [6]

На рисунке 4 представлена упрощенная модель словаря. Здесь ключами словаря служат идентификаторы сотрудников, такие как В4711. Ключ трансформируется в хеш. В хеше создается число для ассоциации индекса со значением. После этого индекс содержит ссылку на значение. Изображенная модель является упрощенной, поскольку существует возможность того, что единственное вхождение индекса может быть ассоциировано с несколькими значениями, и индекс может храниться в виде дерева.

Рисунок 4 — Модель словаря Тип ключа Тип, используемый в качестве ключа словаря, должен переопределять метод GetHashCode () класса Object. Всякий раз, когда класс словаря должен найти местоположение элемента, он вызывает метод GetHashCode ().

Целое число, возвращаемое этим методом, используется словарем для вычисления индекса, куда помещен элемент. [2]

Реализация метода GetHashCode () должна удовлетворять перечисленным ниже требованиям:

1) Один и тот же объект должен всегда возвращать одно и то же значение;

2) Разные объекты могут возвращать одно и то же значение;

3) Он должен выполняться насколько возможно быстро, не требуя значительных вычислительных затрат;

4) Он не должен генерировать исключений;

5) Он должен использовать как минимум одно поле экземпляра;

6) Значения хеш-кода должны распределяться равномерно по всему диапазону чисел, которые может хранить int;

7) Хеш-код не должен изменяться на протяжении времени существования объекта.

Хорошая производительность словаря основана на хорошей реализации метода GetHashCode (). [2]

Если два ключа возвращают хеш-значения, дающие один и тот же индекс, класс словаря вынужден искать ближайшее доступное свободное место для сохранения второго элемента, к тому же ему придется выполнять некоторый поиск, чтобы впоследствии извлечь требуемое значение. Это наносит ущерб производительности, и если множество ключей дают одни и те же индексы, куда их следует поместить, вероятность конфликтов значительно возрастает. Однако благодаря способу, которым работает часть алгоритма, принадлежащая Microsoft, риск снижается до минимума, когда вычисляемое значение хеш-кода равномерно распределено между int. MinValue и int.MaxValue. [2]

Помимо реализации GetHashCode () тип ключа также должен реализовывать метод IEquatable. Equals () либо переопределять метод Equals () класса Object. Поскольку разные объекты ключа могут возвращать один и тот же хеш-код, метод Equals () используется при сравнении ключей словаря. Словарь проверяет два ключа, А и В на эквивалентность, вызывая A. Equals (В). Это означает, что потребуется обеспечить истинность следующего утверждения:

Если истинно А. Equals (В), значит, А. GetHashCode () и В. GetHashCode () всегда должны возвращать один и тот же хеш-код. [2]

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

По этой причине компилятор С# будет отображать предупреждение, если вы переопределите Equals (), но не представите переопределения GetHashCode (). [3]

Для System. Object это условие истинно, поскольку Equals () просто сравнивает ссылки, a GetHashCode () в действительности возвращает хеш-код, основанный исключительно на адресе объекта. Это означает, что хеш-таблицы, основанные на ключе, не переопределяющем эти методы, будут работать корректно. Однако проблема такого подхода заключается в том, что ключи трактуются как эквивалентные только в том случае, если они представляют один и тот же объект. Это значит, что когда при помещении объекта в словарь, обязательно нужно обращаться к ссылкам на ключ. Возможности просто позднее создать экземпляр другого ключевого объекта с тем же значением нет. Если не переопределить Equals () и GetHashCode (), то тип будет не слишком удобным для использования в словаре. [6]

System.String реализует интерфейс IEquatable и соответственно переопределяет GetHashCode (). Equals () обеспечивает сравнение значений, а GetHashCode () возвращает хеш-код, основанный на значении строки. Строки с успехом могут использоваться в качестве ключей в словарях. [6]

Числовые типы, такие как Int32, также реализуют интерфейс IEquatable и перегружают GetHashCode (). Однако хеш-код, возвращаемый этими типами, просто отображает значение. Если число, которое нужно использовать в качестве ключа, само по себе не распределено по всему диапазону возможных целочисленных значений, применение целых в качестве ключей не отвечает правилу равномерного распределения ключевых значений для получения наилучшей производительности. Int32 не предназначен для использования в словаре. [3]

Если нужно использовать тип ключа, который не реализует IEquatable и не переопределяет GetHashCode соответственно значениям ключа, сохраняемым в словаре, то есть возможность создать компаратор, реализующий интерфейс IEqualityComparer. IEqualityComparer определяет методы GetHashCode () и Equals () с аргументом — переданным объектом, так что вы можете предоставить реализацию, отличающуюся от типа самого объекта. Перегрузка конструктора Dictionary позволяет передать объект, реализующий IEqualityComparer. Если такой объект присвоен словарю, этот класс используется для генерации хеш-кодов и сравнения ключей. [3]

Класс Dictionary

В классе Dictionary реализуются интерфейсы IDictionary, IDictionary, ICollection, ICollection>, IEnumerable, IEnumerable>, ISerializable и IDeserializationCallback. В двух последних интерфейсах поддерживается сериализация списка. Словари имеют динамический характер, расширяясь по мере необходимости. [2]

В классе Dictionary предоставляется немало конструкторов. Ниже перечислены наиболее часто используемые из них:

public Dictionary ()

public Dictionary (IDictionary dictionary)

public Dictionary (int capacity)

В первом конструкторе создается пустой словарь с выбираемой по умолчанию первоначальной емкостью. Во втором конструкторе создается словарь с указанным количеством элементов dictionary. А в третьем конструкторе с помощью параметра capacity указывается емкость коллекции, создаваемой в виде словаря. Если размер словаря заранее известен, то, указав емкость создаваемой коллекции, можно исключить изменение размера словаря во время выполнения, что, как правило, требует дополнительных затрат вычислительных ресурсов. [2]

В классе Dictionary определяется также ряд методов:

Add ()

Добавляет в словарь пару «ключ-значение», определяемую параметрами key и value. Если ключ key уже находится в словаре, то его значение не изменяется, и генерируется исключение ArgumentException

ContainsKey ()

Возвращает логическое значение true, если вызывающий словарь содержит объект key в качестве ключа; а иначе — логическое значение false

ContainsValue ()

Возвращает логическое значение true, если вызывающий словарь содержит значение value; в противном случае — логическое значение false

Remove ()

Удаляет ключ key из словаря. При удачном исходе операции возвращается логическое значение true, а если ключ key отсутствует в словаре — логическое значение false. [2]

Кроме того, в классе Dictionary определяются собственные свойства, помимо тех, что уже объявлены в интерфейсах, которые в нем реализуются. Эти свойства приведены ниже, в таблице 4. [5]

Таблица 4 — Собственные свойства класса Dictionary

Следует иметь в виду, что ключи и значения, содержащиеся в коллекции, доступны отдельными списками с помощью свойств Keys и Values. В коллекциях типа Dictionary. KeyCollection и Dictionary. ValueCollection реализуются как обобщенные, так и необобщенные формы интерфейсов ICollection и IEnumerable.

И наконец, в классе Dictionary реализуется приведенный ниже индексатор, определенный в интерфейсе IDictionary

public TValue this[TKey key] { get; set; }

Этот индексатор служит для получения и установки значения элемента коллекции, а также для добавления в коллекцию нового элемента. Но в качестве индекса в данном случае служит ключ элемента, а не сам индекс. При перечислении коллекции типа Dictionary из нее возвращаются пары «ключ-значение» в форме структуры KeyValuePair. Напомним, что в этой структуре определяются два поля. [4]

public TKey Key;

public TValue Value;

В этих полях содержится ключ или значение соответствующего элемента коллекции. Как правило, структура KeyValuePair не используется непосредственно, поскольку средства класса Dictionary позволяют работать с ключами и значениями по отдельности. Но при перечислении коллекции типа Dictionary, например, в цикле foreach перечисляемыми объектами являются пары типа KeyValuePair.

Классы HashSet и SortedSet

Класс SortedSet удобен тем, что при вставке или удалении элементов он автоматически обеспечивает сортировку элементов в наборе. Класс SortedSet понадобится информировать о том, как должны сортироваться объекты, за счет передачи его конструктору аргумента — объекта, реализующего обобщенный интерфейс IComparer.

Коллекция, содержащая только отличающиеся элементы, называется множеством (set). В составе .NET 4 имеются два множества — HashSet и SortedSet. Оба они реализуют интерфейс ISet. Класс HashSet содержит неупорядоченный список различающихся элементов, а в SortedSet элементы упорядочены. [6]

Интерфейс ISet предоставляет методы для создания объединения нескольких множеств, пересечения множеств и определения, является ли одно множество надмножеством или подмножеством другого. [2]

Ниже перечислены наиболее употребительные конструкторы, определенные в классе HashSet:

public HashSet ()

public HashSet (IEnumerable collection)

public HashSet (IEqualityCompare comparer)

public HashSet (IEnumerable collection, IEqualityCompare comparer)

В первой форме конструктора создается пустое множество, а во второй форме — множество, состоящее из элементов указываемой коллекции collection. В третьей форме конструктора допускается указывать способ сравнения с помощью параметра comparer. А в четвертой форме создается множество, состоящее из элементов указываемой коллекции collection, и используется заданный способ сравнения comparer. Имеется также пятая форма конструктора данного класса, в которой допускается инициализировать множество последовательно упорядоченными данными.

В этом классе предоставляется также метод RemoveWhere (), удаляющий из множества элементы, удовлетворяющие заданному условию, или предикату. Помимо свойств, определенных в интерфейсах, которые реализуются в классе HashSet, в него введено дополнительное свойство Comparer, приведенное ниже:

public IEqualityComparer Comparer { get; }

Оно позволяет получать метод сравнения для вызывающего хеш-множества. [4]

Ниже перечислены четыре наиболее часто используемых конструкторов, определенных в классе SortedSet:

public SortedSet ()

public SortedSet (IEnumerable collection)

public SortedSet (IComparer comparer)

public SortedSet (IEnumerable collection, IComparer comparer)

В первой форме конструктора создается пустое множество, а во второй форме — множество, состоящее из элементов указываемой коллекции collection. В третьей форме конструктора допускается указывать способ сравнения с помощью параметра comparer. А в четвертой форме создается множество, состоящее из элементов указываемой коллекции collection, и используется заданный способ сравнения comparer. Имеется также пятая форма конструктора данного класса, в которой допускается инициализировать множество последовательно упорядоченными данными.

В этом классе предоставляется также метод GetViewBetween (), возвращающий часть множества в форме объекта типа SortedSet, метод RemoveWhere (), удаляющий из множества элементы, не удовлетворяющие заданному условию, или предикату, а также метод Reverse (), возвращающий объект типа IEnumerable, который циклически проходит множество в обратном порядке. [6]

Помимо свойств, определенных в интерфейсах, которые реализуются в классе SortedSet, в него введены дополнительные свойства, приведенные ниже:

public IComparer Comparer { get; }

public T Max { get; }

public T Min { get; }

Свойство Comparer получает способ сравнения для вызывающего множества. Свойство Мах получает наибольшее значение во множестве, а свойство Min — наименьшее значение во множестве.

Класс SortedDictionary

Класс SortedDictionary представляет дерево бинарного поиска, в котором все элементы отсортированы на основе ключа. Тип ключа должен реализовать интерфейс IComparable. Если тип ключа не сортируемый, компаратор можно также создать, реализовав IComparer и указав его в качестве аргумента конструктора сортированного словаря. [2]

Классы SortedDictionary и SortedList имеют схожую функциональность. Но поскольку SortedList реализован в виде списка, основанного на массиве, a SortedDictionary реализован как словарь, эти классы обладают разными характеристиками:

SortedList использует меньше памяти, чем SortedDictionary

SortedDictionary быстрее вставляет и удаляет элементы.

При наполнении коллекции отсортированными данными SortedList работает быстрее, если при этом не требуется изменение емкости. [6]

В классе SortedDictionary реализуются интерфейсы IDictionary, IDictionary, ICollection, ICollection>, IEnumerable и IEnumerable>. В классе SortedDictionary предоставляются также следующие конструкторы:

public SortedDictionary ()

public SortedDictionary (IDictionary dictionary)

public SortedDictionary (IComparer comparer)

public SortedDictionary (IDictionary dictionary, IComparer comparer)

В первом конструкторе создается пустой словарь, во втором конструкторе — словарь с указанным количеством элементов dictionary. В третьем конструкторе допускается указывать с помощью параметра comparer типа IComparer способ сравнения, используемый для сортировки, а в четвертом конструкторе — инициализировать словарь, помимо указания способа сравнения. [2]

В классе SortedDictionary определен ряд методов. Некоторые наиболее часто используемые методы этого класса приведены ниже: [2]

Add ()

Добавляет в словарь пару «ключ-значение», определяемую параметрами key и value. Если ключ key уже находится в словаре, то его значение не изменяется, и генерируется исключение ArgumentException

ContainsKey ()

Возвращает логическое значение true, если вызывающий словарь содержит объект key в качестве ключа; в противном случае — логическое значение false

ContainsValue ()

Возвращает логическое значение true, если вызывающий словарь содержит значение value, в противном случае — логическое значение false

Remove ()

Удаляет ключ key из словаря. При удачном исходе операции возвращается логическое значение true, а если ключ key отсутствует в словаре — логическое значение false

Следует иметь в виду, что ключи и значения, содержащиеся в коллекции, доступны отдельными списками с помощью свойств Keys и Values. В коллекциях типа SortedDictionary. KeyCollection и SortedDictionary. ValueCollection реализуются как обобщенные, так и необобщенные формы интерфейсов ICollection и IEnumerable. [6]

И наконец, в классе SortedDictionary реализуется приведенный ниже индексатор, определенный в интерфейсе IDictionary:

public TValue this[TKey key] { get; set; }

Этот индексатор служит для получения и установки значения элемента коллекции, а также для добавления в коллекцию нового элемента. Но в данном случае в качестве индекса служит ключ элемента, а не сам индекс.

4. Параллельные коллекции В версию 4.0 среды .NET Framework добавлено новое пространство имен System.Collections.Concurrent. Оно содержит коллекции, которые являются потокобезопасными и специально предназначены для параллельного программирования. Это означает, что они могут безопасно использоваться в многопоточной программе, где возможен одновременный доступ к коллекции со стороны двух или больше параллельно исполняемых потоков. Для безопасного в отношении потоков доступа к коллекциям определен интерфейс IProducerConsumerCollection. Наиболее важными методами этого интерфейса являются TryAdd () и TryTake (). Метод TryAdd () пытается добавить элемент в коллекцию, но это может не получиться, если коллекция заблокирована от добавления элементов. Метод возвращает булевское значение, сообщающее об успехе или неудаче операции. [2]

TryTake () работает аналогичным образом, информируя вызывающий код об успехе или неудаче, и в случае успеха возвращает элемент из коллекции. Ниже перечислены классы из пространства имен System.Collections.Concurrent с кратким описанием их функциональности:

ConcurrentQueue

Этот класс коллекции реализован со свободным от блокировок алгоритмом и использует 32 массива, которые внутренне скомбинированы в связный список. Для доступа к элементам очереди применяются методы Enqueue (), TryDequeue () и TryPeek (). Имена этих методов очень похожи на уже известные методы Queue, но с добавлением префикса Try к тем из них, которые могут дать сбой. Поскольку этот класс реализует интерфейс IProducerConsumerCollection, методы TryAdd () и TryTake () просто вызывают Enqueue () и TryDequeue (). [6]

ConcurrentStack

Очень похож на ConcurrentQueue, но с другими методами доступа к элементам. Класс ConcurrentStack определяет методы Push (), PushRange (), TryPeek (), TryPop () и TryPopRange (). Внутри этот класс использует связный список для хранения элементов. [2]

ConcurrentBag

Этот класс не определяет никакого порядка для добавления или извлечения элементов. Он реализует концепцию отображения потоков на используемые внутренне массивы, и старается избежать блокировок. Для доступа к элементам применяются методы Add (), TryPeek () и TryTake (). [2]

ConcurrentDictionary

Безопасная в отношении потоков коллекция ключей и значений. Для доступа к членам в неблокирующем режиме служат методы TryAdd (), TryGetValue (), TryRemove () и TryUpdate (). Поскольку элементы основаны на ключах и значениях, ConcurrentDictionary не реализует интерфейс IProducerConsumerCollection. [2]

ConcurrentXXX. Эти коллекции безопасны к потокам в том смысле, что возвращают false, если какое-то действие над ними невозможно при текущем состоянии потоков. Прежде чем предпринимать какие-то дальнейшие действия, всегда следует проверять успешность добавления или извлечения элементов. Полностью доверять коллекции решение задачи нельзя. [2]

BlockingCollection

Коллекция, которая осуществляет блокировку и ожидает, пока не появится возможность выполнить действие по добавлению или извлечению элемента. BlockingCollection предлагает интерфейс для добавления и извлечения элементов методами Add () и Take (). Эти методы блокируют поток и затем ожидают, пока не появится возможность выполнить задачу. [2]

Метод Add () имеет перегрузку, которой можно также передать CancellationToken. Эта лексема всегда отменяет блокирующий вызов. Если не нужно, чтобы поток ожидал бесконечное время, без отмены вызова, доступны также методы TryAdd () и TryTake (). В них можно указать значение таймаута — максимального периода времени, в течение которого вы готовы блокировать поток и ждать, пока вызов не даст сбой. [2]

5. Специальные и наблюдаемые коллекции

5.1 Специальные коллекции В среде .NET Framework предусмотрен ряд специальных коллекций, оптимизированных для работы с данными конкретного типа или для их обработки особым образом. Классы этих необобщенных коллекций определены в пространстве имен System.Collections.Specialized и перечислены в таблице 5. [3]

Таблица 5 — Специальные коллекции C#

Кроме того, в пространстве имен System. Collections определены три базовых абстрактных класса: CollectionBase, ReadOnlyCollectionBase и DictionaryBase. Эти классы могут наследоваться и служить в качестве отправной точки для разработки собственных специальных коллекций. [2]

5.2 Наблюдаемые коллекции В случае если нужна информация о том, когда элементы коллекции удаляются или добавляются, можно использовать класс ObservableCollection. Этот класс был определен для WPF и предназначен для того, чтобы пользовательский интерфейс мог получать информацию об изменениях коллекции. По этой причине он включен в сборку WindowsBase, следовательно, на нее необходимо сослаться. Пространство имен этого класса — System.Collections.ObjectModel. [2]

Класс ObservableCollection унаследован от базового класса Collection, который может применяться для создания специальных коллекций; он использует внутри себя List. Методы базового класса SetItem () и RemoveItem () переопределены для инициации события CollectionChanged. Клиенты этого класса могут регистрироваться на это событие, используя интерфейс INotifyCollectionChanged.

В следующем примере показано применение ObservableCollection, при этом метод Data_CollectionChanged регистрируется на событие CollectionChanged.

Два элемента добавляются в конец коллекции, затем еще один вставляется и один удаляется:

var data = new ObservableCollection ();

data.CollectionChanged += Data_CollectionChanged;

data.Add («One»);

data.Add («Two»);

data.Insert (1, «Three»);

data.Remove («One»);

Метод Data_CollectionChanged принимает аргумент NotifyCollection Changed EventArgs, содержащий информацию об изменениях коллекции.

Свойство Action предоставляет информацию о том, был элемент добавлен или удален. Для удаленных элементов устанавливается свойство OldItems, перечисляющее удаленные элементы.

При добавлении элементов устанавливается свойство NewItems, которое перечисляет новые элементы.

6. Битовые коллекции Если требуется иметь дело с множеством битов, можно применить класс BitArray и структуру BitVector32. Класс BitArray расположен в пространстве имен System. Collections, a BitVector32 — в пространстве System.Collections.Specialized. Наиболее важное отличие между этими двумя типами состоит в том, что BitArray имеет изменяемый размер, а это удобно, когда необходимое количество бит известно заранее, и оно велико. Структура BitVector32 основана на стеке, и потому работает быстрее. BitVector32 содержит только 32 бита, которые хранятся в целом числе. [3]

6.1 Класс BitArray

Класс BitArray служит для хранения отдельных битов в коллекции. А поскольку в коллекции этого класса хранятся биты, а не объекты, то своими возможностями он отличается от классов других коллекций. Тем не менее, в классе BitArray реализуются интерфейсы ICollection и IEnumerable как основополагающие элементы поддержки всех типов коллекций. Кроме того, в классе BitArray реализуется интерфейс ICloneable. [2]

В классе BitArray определено несколько конструкторов. Так, с помощью приведенного ниже конструктора можно сконструировать объект типа BitArray из массива логических значений:

public BitArray (bool[] values)

В данном случае каждый элемент массива values становится отдельным битом в коллекции. Это означает, что каждому элементу массива values соответствует отдельный бит в коллекции. Более того, порядок расположения элементов в массиве values сохраняется и в коллекции соответствующих им битов. Коллекцию типа BitArray можно также составить из массива байтов, используя следующий конструктор: [2]

public BitArray (byte[] bytes)

Здесь битами в коллекции становится уже целый их набор из массива bytes, причем элемент bytes обозначает первые 8 битов, элемент bytes вторые 8 битов и т. д. [2]

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

В классе BitArray определяется ряд собственных методов, помимо тех, что уже объявлены в интерфейсах, которые в нем реализуются. Методы этого класса приведены ниже. [3]

В классе BitArray не поддерживается метод Synchronized (). Это означает, что для коллекций данного класса синхронизированная оболочка недоступна, а свойство IsSynchronized всегда имеет логическое значение false. Тем не менее, для управления доступом к коллекции типа BitArray ее можно синхронизировать для объекта, предоставляемого в упоминавшемся ранее свойством SyncRoot. [2]

And ()

Выполняет операцию логического умножения (И) битов вызывающего объекта и коллекции value. Возвращает коллекцию типа BitArray, содержащую результат

Get ()

Возвращает значение бита, указываемого по индексу

Not ()

Выполняет операцию поразрядного логического отрицания (НЕ) битов вызывающей коллекции и возвращает коллекцию типа BitArray, содержащую результат

Or ()

Выполняет операцию логического сложения (ИЛИ) битов вызывающего объекта и коллекции value. Возвращает коллекцию типа BitArray, содержащую результат. [2]

Set ()

Устанавливает бит, указываемый по индексу index, равным значению value

SetAll ()

Устанавливает все биты равными значению value

Xor ()

Выполняет логическую операцию исключающее (ИЛИ) над битами вызывающего объекта и коллекции value. Возвращает коллекцию типа BitArray, содержащую результат. [2]

В классе BitArray определяется также собственное свойство, помимо тех, что указаны в интерфейсах, которые в нем реализуются:

public int Length { get; set; }

Свойство Length позволяет установить или получить количество битов в коллекции. Следовательно, оно возвращает такое же значение, как и стандартное свойство Count, определяемое для всех коллекций. В отличие от свойства Count, свойство Length доступно не только для чтения, но и для записи, а значит, с его помощью можно изменить размер коллекции типа BitArray. [3]

6.2 Структура BitVector

Если необходимое количество бит известно заранее, то вместо BitArray можно использовать структуру BitVector32. Структура BitVector32 более эффективна, поскольку это тип значения, хранящий биты в стеке внутри целого числа. В единственном целом числе имеется место для 32 бит.

Если нужно больше, можно применять множество значений BitVector32 или же BitArray. Класс BitArray при необходимости может расти, а структура BitVector32 лишена такой возможности. [2]

Ниже перечислены члены структуры BitVector32, которые существенно отличаются от BitArray:

Data

Свойство Data возвращает данные BitVector32 в виде целого числа.

Item

Значение BitVector32 может быть установлено с использованием целого числа. Индексатор перегружен: получать и устанавливать значения можно с использованием маски или секции типа BitVector32.Section.

CreateMask ()

Статический метод, который позволяет создавать маску для доступа к определенным битам Bitvector32.

CreateSelection ()

Статический метод, который позволяет создавать несколько секций внутри 32 бит. В приведенном ниже примере создается структура BitVector32 с помощью конструктора по умолчанию, при этом все 32 бита инициализируются false. Затем создаются маски для доступа к битам внутри битового вектора. Первый вызов CreateMask () создает маску для доступа к первому биту. После вызова CreateMask () значение bitl равно 1. [2]

Еще один вызов CreateMask () возвращает маску для доступа ко второму биту, которая равна 2. bit3 имеет значение 4 для доступа к биту номер 3. bit4 имеет значение 8 для доступа к биту номер 4. Затем маски используются с индексатором для доступа к битам внутри вектора бит и соответствующей установки полей:

var bitsl = new BitVector32 () ;

int bitl = BitVector32. CreateMask ();

int bit2 = BitVector32. CreateMask (bitl);

int bit3 = BitVector32. CreateMask (bit2);

int bit4 = BitVector32. CreateMask (bit3);

int bit5 = BitVector32. CreateMask (bit4);

bitsl[bitl] = true;

bitsl[bit2] = false;

bitsl[bit3] = true;

bitsl[bit4] = true;

bitsl[bi15] = true;

Console.WriteLine (bits1);

7. Реализация интерфейса IComparable

Если требуется отсортировать коллекцию, состоящую из объектов определяемого пользователем класса, при условии, что они не сохраняются в коллекции класса SortedList, где элементы располагаются в отсортированном порядке, то в такой коллекции должен быть известен способ сортировки содержащихся в ней объектов. С этой целью можно, в частности, реализовать интерфейс IComparable для объектов сохраняемого типа. Интерфейс IComparable доступен в двух формах: обобщенной и необобщенной. Несмотря на сходство применения обеих форм данного интерфейса, между ними имеются некоторые, хотя и небольшие, отличия. [2]

Если требуется отсортировать объекты, хранящиеся в необобщенной коллекции, то для этой цели придется реализовать необобщенный вариант интерфейса IComparable. В этом варианте данного интерфейса определяется только один метод, CompareTo (), который определяет порядок выполнения самого сравнения. Ниже приведена общая форма объявления метода CompareTo ():

int CompareTo (object obj)

В методе CompareTo () вызывающий объект сравнивается с объектом obj. Для сортировки объектов по нарастающей конкретная реализация данного метода должна возвращать нулевое значение, если значения сравниваемых объектов равны; положительное — если значение вызывающего объекта больше, чем у объекта obj; и отрицательное — если значение вызывающего объекта меньше, чем у объекта obj. А для сортировки по убывающей можно обратить результат сравнения объектов. Если же тип объекта obj не подходит для сравнения с вызывающим объектом, то в методе CompareTo () может быть сгенерировано исключение ArgumentException. [2]

Если требуется отсортировать объекты, хранящиеся в обобщенной коллекции, то для этой цели придется реализовать обобщенный вариант интерфейса IComparable. В этом варианте интерфейса IComparable определяется приведенная ниже обобщенная форма метода CompareTo ():

int CompareTo (Т other). [2]

В методе CompareTo () вызывающий объект сравнивается с другим объектом other.

Для сортировки объектов по нарастающей конкретная реализация данного метода должна возвращать нулевое значение, если значения сравниваемых объектов равны; положительное — если значение вызывающего объекта больше, чем у объекта другого other; и отрицательное если значение вызывающего объекта меньше, чем у другого объекта other. А для сортировки по убывающей можно обратить результат сравнения объектов. При реализации обобщенного интерфейса IComparable имя типа реализующего класса обычно передается в качестве аргумента типа. [2]

8. Реализация интерфейса IComparer

Для сортировки объектов определяемых пользователем классов зачастую проще всего реализовать в этих классах интерфейс IComparable. Тем не менее, данную задачу можно решить и с помощью интерфейса IComparer. Для этой цели необходимо сначала создать класс, реализующий интерфейс IComparer, а затем указать объект этого класса, когда потребуется сравнение. [2]

Интерфейс IComparer существует в двух формах: обобщенной и необобщенной. Несмотря на сходство применения обеих форм данного интерфейса, между ними имеются некоторые, хотя и небольшие, отличия.

В необобщенном интерфейсе IComparer определяется только один метод Compare ():

int Compare (object x, object у) В методе Compare () сравниваются объекты х и у. Для сортировки объектов по нарастающей конкретная реализация данного метода должна возвращать нулевое значение, если значения сравниваемых объектов равны; положительное — если значение объекта х больше, чем у объекта у; и отрицательное — если значение объекта х меньше, чем у объекта у. А для сортировки по убывающей можно обратить результат сравнения объектов. Если же тип объекта х не подходит для сравнения с объектом у, то в методе CompareTo () может быть сгенерировано исключение ArgumentException. [2]

Объект типа IComparer может быть указан при конструировании объекта класса SortedList, при вызове метода ArrayList. Sort (IComparer), а также в ряде других мест в классах коллекций. Главное преимущество применения интерфейса IComparer заключается в том, что сортировке подлежат объекты тех классов, в которых интерфейс IComparable не реализуется. [2]

Интерфейс IComparer является обобщенным вариантом интерфейса IComparer. В нем определяется приведенный ниже обобщенный вариант метода Compare ():

int Compare (Т х, T у) В этом методе сравниваются объекты х и у и возвращается нулевое значение, если значения сравниваемых объектов равны; положительное — если значение объекта х больше, чем у объекта у; и отрицательное — если значение объекта х меньше, чем у объекта у. [2]

9. Перечислители К элементам коллекции нередко приходится обращаться циклически, например, для отображения каждого элемента коллекции. С этой целью можно, с одной стороны, организовать цикл foreach, а с другой — воспользоваться перечислителем. Перечислитель — это объект, который реализует необобщенный интерфейс IEnumerator или обобщенный интерфейс IEnumerator. [2]

В интерфейсе IEnumerator определяется одно свойство, Current, необобщенная форма которого приведена ниже:

object Current {get;}

А в интерфейсе IEnumerator объявляется следующая обобщенная форма свойства Current:

Т Current {get;}

В обеих формах свойства Current получается текущий перечисляемый элемент коллекции. Но поскольку свойство Current доступно только для чтения, то перечислитель может служить только для извлечения, но не видоизменения объектов в коллекции. [2]

В интерфейсе IEnumerator определяются два метода. Первым из них является метод MoveNext (), объявляемый следующим образом:

bool MoveNext ()

При каждом вызове метода MoveNext () текущее положение перечислителя смещается к следующему элементу коллекции. Этот метод возвращает логическое значение true, если следующий элемент коллекции доступен, и логическое значение false, если достигнут конец коллекции. Перед первым вызовом метода MoveNext () значение свойства Current оказывается неопределенным. [2]

Для установки перечислителя в исходное положение, соответствующее началу коллекции, вызывается приведенный ниже метод Reset ():

void Reset ()

После вызова метода Reset () перечисление вновь начинается с самого начала коллекции. Поэтому, прежде чем получить первый элемент коллекции, следует вызвать метод MoveNext (). [2]

В интерфейсе IEnumerator методы MoveNext () и Reset () действуют по тому же самому принципу. Необходимо также обратить внимание на два следующих момента. Во-первых, перечислитель нельзя использовать для изменения содержимого перечисляемой с его помощью коллекции. Следовательно, перечислители действуют по отношению к коллекции как к доступной только для чтения. И во-вторых, любое изменение в перечисляемой коллекции делает перечислитель недействительным.

9.1 Применение обычного перечислителя Прежде чем получить доступ к коллекции с помощью перечислителя, необходимо получить его. В каждом классе коллекции для этой цели предоставляется метод GetEnumerator (), возвращающий перечислитель в начало коллекции. Используя этот перечислитель, можно получить доступ к любому элементу коллекции по очереди. В целом, для циклического обращения к содержимому коллекции с помощью перечислителя рекомендуется придерживаться приведенной ниже процедуры:

1) Получить перечислитель, устанавливаемый в начало коллекции, вызвав для этой коллекции метод GetEnumerator (). [2]

2) Организовать цикл, в котором вызывается метод MoveNext (). Повторять цикл до тех пор, пока метод MoveNext () возвращает логическое значение true.

3) Получить в цикле каждый элемент коллекции с помощью свойства Current. [2]

Пример использования перечислителей, заимствованный из источника показан в листинге 8 (см. Приложение А).

Для циклического обращения к элементам коллекции цикл fоreach оказывается более удобным, чем перечислитель. Тем не менее, перечислитель предоставляет больше возможностей для управления, поскольку его можно при желании всегда установить в исходное положение.

9.2 Применение перечислителя типа IDictionaryEnumerator

Если для организации коллекции в виде словаря, например типа Hashtable, реализуется необобщенный интерфейс IDictionary, то для циклического обращения к элементам такой коллекции следует использовать перечислитель типа IDictionaryEnumerator вместо перечислителя типа IEnumerator. Интерфейс IDictionaryEnumerator наследует от интерфейса IEnumerator и имеет три дополнительных свойства. Первым из них является приведенное ниже свойство. [3]

DictionaryEntry Entry {get;}

Свойство Entry позволяет получить пару «ключ-значение» из перечислителя в форме структуры DictionaryEntry. Напомним, что в структуре DictionaryEntry определяются два свойства, Key и Value, с помощью которых можно получать доступ к ключу или значению, связанному с элементом коллекции. Ниже приведены два других свойства, определяемых в интерфейсе IDictionaryEnumerator

object Key { get; }

object Value { get; }

С помощью этих свойств осуществляется непосредственный доступ к ключу или значению. [2]

Перечислитель типа IDictionaryEnumerator используется аналогично обычному перечислителю, за исключением того, что текущее значение в данном случае получается с помощью свойств Entry, Key или Value, а не свойства Current. Следовательно, приобретя перечислитель типа IDictionaryEnumerator, необходимо вызвать метод MoveNext (), чтобы получить первый элемент коллекции. А для получения остальных ее элементов следует продолжить вызовы метода MoveNext (). Этот метод возвращает логическое значение false, когда в коллекции больше нет ни одного элемента. [2]

9.3 Реализация интерфейсов IEnumerable и IEnumerator

Для циклического обращения к элементам коллекции зачастую проще организовать цикл foreach, чем пользоваться непосредственно методами интерфейса IEnumerator. Тем не менее, ясное представление о принципе действия подобных интерфейсов важно иметь по еще одной причине: если требуется создать класс, содержащий объекты, перечисляемые в цикле foreach, то в этом классе следует реализовать интерфейсы IEnumerator и IEnumerable.

Ниже представлен пример реализации интерфейса IEnumerator

public bool MoveNext ()

{

if (index == ints. Length — 1)

{

Reset ();

return false;

}

index++;

return true;

}

И пример реализации интерфейса Ienumerable

public IEnumerator GetEnumerator ()

{

return this;

}

Иными словами, для того чтобы обратиться к объекту определяемого пользователем класса в цикле foreach, необходимо реализовать интерфейсы IEnumerator и IEnumerable в их обобщенной или необобщенной форме.

10. Итераторы и оператор yield

Итератор представляет собой метод, в котором используется ключевое слово yield для перебора по коллекции или массиву. [3]

Наиболее простой способ создания итератора заключается в реализации метода GetEnumerator для интерфейса IEnumerable, например:

public System.Collections.IEnumerator GetEnumerator ()

{

for (int i = 0; i < 10; i++)

{

yield return i;

}

}

Наличие метода GetEnumerator создает тип перечисляемого типа и позволяет использовать оператор foreach statement. Если бы приведенный выше метод был частью определения класса для ListClass, то можно было бы использовать foreach для класса следующим образом [5]

static void Main ()

{

ListClass listClass1 = new ListClass ();

foreach (int i in listClass1)

{

System.Console.WriteLine (i);

}

}

Оператор foreach вызывает ListClass. GetEnumerator () и использует возвращенный перечислитель для итерации значений. [5]

Кроме того, можно использовать именованные итераторы в поддержку различных возможностей перебора одной и той же коллекции данных. [5]

Например, можно было бы предоставить один итератор, возвращающий элементы по возрастанию, а другой итератора, возвращающий элементы по убыванию. Итератор может также иметь параметры, позволяющие клиентам управлять всем поведением итератора или его часть. Следующий итератор реализует интерфейс IEnumerable при помощи именованного итератора SampleIterator [5]

public System.Collections.IEnumerable SampleIterator (int start, int end)

{

for (int i = start; i <= end; i++)

{

yield return i;

}

}

Именованный итератор вызывается следующим образом. [5]

ListClass test = new ListClass ();

foreach (int n in test. SampleIterator (1, 10))

{

System.Console.WriteLine (n);

}

В одном итераторе можно использовать несколько операторов yield, как в следующем примере. [5]

public System.Collections.IEnumerator GetEnumerator ()

{

yield return «With an iterator, «;

yield return «more than one «;

yield return «value can be returned» ;

yield return «.» ;

}

Результаты можно вывести с помощью оператора foreach. [5]

foreach (string element in new TestClass ())

{

System.Console.Write (element);

}

В каждой последовательной итерации цикла foreach (или прямом вызове IEnumerator. MoveNext) следующий текст кода итератора возобновляется после оператора yield и продолжается до конца текста итератора или до оператора yield break.

Итераторы не поддерживают метод IEnumeratorReset (). Для повторной итерации сначала необходимо получить новый итератор. [5]

IEnumerator IEnumerable. GetEnumerator ()

{

for (int i = 0; i < books. Length; i++)

{

yield return books[i];

}

}

Метод GetEnumerator () теперь будет являться итератором. Когда будет осуществляться перебор в объекте Library в цикле foreach, то будет идти обращение к вызову yield return books[i]. При обращении к оператору yield return будет сохраняться текущее местоположение. И когда метод foreach перейдет к следующей итерации для получения нового объекта, итератор начнет выполнения с этого местоположения. [3]

В основной программе в цикле foreach выполняется перебор, благодаря реализации итератора:

foreach (Book b in library)

{

Console.WriteLine (b.Name);

}

При реализации итератора в методе GetEnumerator () применять перебор массива в цикле for необязательно. Можно определить несколько вызовов оператора yield return, как показано в примере ниже. [3]

IEnumerator IEnumerable. GetEnumerator ()

{

yield return books[0];

yield return books[1];

yield return books[2];

}

В этом случае при каждом вызове оператора yield return итератор также будет запоминать текущее местоположение и при последующих вызовах начинать с него. [3]

10.1 Именованный итератор

Выше для создания итератора был использован метод GetEnumerator. Но оператор yield можно использовать внутри любого метода, только такой метод должен возвращать объект интерфейса IEnumerable. Подобные методы еще называют именованными итераторами. [3]

В листинге 10 (см. Приложение А) приведен пример из источника [3], в котором создается именованный итератор в классе Library.

Определенный здесь итератор — метод IEnumerable GetBooks (int max) в качестве параметра принимает количество выводимых объектов.

public IEnumerable GetBooks (int max)

{

for (int i = 0; i < max; i++)

{

if (i == books. Length)

{

yield break;

}

else

{

yield return books[i];

}

}

}

В процессе работы программы может сложиться, что его значение будет больше, чем длина массива books. И чтобы не произошло ошибки, используется оператор yield break. Этот оператор прерывает выполнение итератора. [3]

Применение итератора:

Library library = new Library ();

foreach (Book b in library. GetBooks (5))

{

Console.WriteLine (b.Name);

}

Вызов library. GetBooks (5) будет возвращать набор из не более чем 5 объектов Book. Но так как в примере всего три таких объекта, то в методе GetBooks после трех операций сработает оператор yield break. [3]

if (i == books. Length)

{

yield break;

}

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

Эту форму итератора можно перегрузить, расширив ее функциональные возможности. В приведенном ниже примере программы демонстрируется способ применения именованного итератора для получения элементов коллекции. В этом примере элементы перечисляются в заданных начальном и конечном пределах. [5]

using System;

using System. Collections;

class MyClass

{

char ch = 'A';

// Этот итератор возвращает буквы английского алфавита,

}

}

Заключение

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

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

Список использованных источников

1. Чистяков, В. Коллекции в .NET Framework Class Library / В. Чистяков // RSDN Magazine. — 2003. № 6. — С. 31−34.

2. Нейгел, Кристиан C# 5.0 и платформа .Net 4.5 для профессионалов / Кристиан Нейгел [и др.].; пер. с англ. Ю. Н. Артеменко — М.: ООО «И.Д. Вильямс», 2014. — 1440 с.

3. Троелсен, Эндрю Язык программирования C# 5.0 и платформа .NET 4.5 / Эндрю Троелсен; пер. с англ. Ю. Н. Артеменко. — 6-е изд. — М.: ООО «И.Д. Вильямс», 2013. — 1311 с.

Приложение

Листинги и результаты работы программ В листинге 1 представлен пример использования коллекций, работы с элементами, добавление и удаление некоторых элементов.

Листинг 1 — Создание и применение двух коллекций

using System;

using System. Collections;

using System.Collections.Generic;

namespace Collections

{

class Program

{

static void Main (string[] args)

{

// необобщенная коллекция ArrayList

ArrayList objectList = new ArrayList () { 1, 2, «string», 'c', 2.0f };

object obj = 45.8;

objectList.Add (obj);

objectList.Add («string2»);

objectList.RemoveAt (0); // удаление первого элемента

foreach (object o in objectList)

{

Console.WriteLine (o);

}

Console.WriteLine («Общее число элементов коллекции: «+ objectList. Count);

// обобщенная коллекция List

List countries = new List () { «Россия», «США», «Великобритания», «Китай» };

countries.Add («Франция»);

countries.RemoveAt (1); // удаление второго элемента

foreach (string s in countries)

{

Console.WriteLine (s);

}

Console.ReadLine ();

}

}

}

Результат работы программы представлен на рисунке А1.

Рисунок А.1 — Создание и применение коллекций ArrayList и List

Листинг 2 — Реализация списка List

using System;

using System.Collections.Generic;

namespace Collections

{

class Program

{

static void Main (string[] args)

{

List numbers = new List () { 1, 2, 3, 45 };

numbers.Add (6); // добавление элемента

numbers.AddRange (new int[] { 7, 8, 9 });

numbers.Insert (0, 666); // вставляем на первое место в списке число 666

numbers.RemoveAt (1); // удаляем второй элемент

foreach (int i in numbers)

{

Console.WriteLine (i);

}

List persons = new List (3);

persons.Add (new Person () { Name = «Том» });

persons.Add (new Person () { Name = «Билл» });

foreach (Person p in persons)

{

Console.WriteLine (p.Name);

}

Console.ReadLine ();

}

}

class Person

{

public string Name { get; set; }

}

}

Листинг 3 — Использование очереди Queue<�Т>

using System;

using System.Collections.Generic;

namespace Collections

{

class Program

{

static void Main (string[] args)

{

Queue numbers = new Queue ();

numbers.Enqueue (3); // очередь 3

numbers.Enqueue (5); // очередь 3, 5

numbers.Enqueue (8); // очередь 3, 5, 8

// получаем первый элемент очереди

int queueElement = numbers. Dequeue (); //теперь очередь 5, 8

Console.WriteLine (queueElement);

Queue persons = new Queue ();

persons.Enqueue (new Person () { Name = «Tom» });

persons.Enqueue (new Person () { Name = «Bill» });

persons.Enqueue (new Person () { Name = «John» });

// получаем первый элемент без его извлечения

Person pp = persons. Peek ();

Console.WriteLine (pp.Name);

Console.WriteLine («Сейчас в очереди {0} человек», persons. Count);

// теперь в очереди Tom, Bill, John

foreach (Person p in persons)

{

Console.WriteLine (p.Name);

}

// Извлекаем первый элемент в очереди — Tom

Person person = persons. Dequeue (); // теперь в очереди Bill, John

Console.WriteLine (person.Name);

Console.ReadLine ();

}

}

class Person

{

public string Name { get; set; }

}

}

Результат работы программы можно увидеть на рисунке А.2.

Рисунок А.2 — Результат использование очереди Queue<�Т>

Листинг 4 — Пример использования списка LinkedList

using System;

using System.Collections.Generic;

namespace Collections

{

class Program

{

static void Main (string[] args)

{

LinkedList numbers = new LinkedList ();

numbers.AddLast (1); // вставляем узел со значением 1 на последнее место

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

numbers.AddFirst (2); // вставляем узел со значением 2 на первое место

numbers.AddAfter (numbers.Last, 3); // вставляем после последнего узла новый узел со значением 3

// теперь у нас список имеет следующую последовательность: 2, 1, 3

foreach (int i in numbers)

{

Console.WriteLine (i);

}

LinkedList persons = new LinkedList ();

// добавляем persona в список и получим объект LinkedListNode, в котором хранится имя Tom

LinkedListNode tom = persons. AddLast (new Person () { Name = «Tom» });

persons.AddLast (new Person () { Name = «John» });

persons.AddFirst (new Person () { Name = «Bill» });

Console.WriteLine (tom.Previous.Value.Name); // получаем узел перед томом и его значение

Console.WriteLine (tom.Next.Value.Name); // получаем узел после тома и его значение

Console.ReadLine ();

}

}

class Person

{

public string Name { get; set; }

}

}

Результат работы программы представлен на рисунке А.3.

Рисунок А.3 — Результат использования списка LinkedList

Листинг 5 — Пример использования словарей

using System;

using System.Collections.Generic;

namespace ConsoleApplication1

{

class UserInfo

{

// Метод, реализующий словарь

public static Dictionary MyDic (int i)

{

Dictionary dic = new Dictionary ();

Console.WriteLine («Введите имя сотрудника: n»);

string s;

for (int j = 0; j < i; j++)

{

Console.Write («Name{0} —> «, j);

s = Console. ReadLine ();

dic.Add (j, s);

Console.Clear ();

}

return dic;

}

}

class Program

{

static void Main ()

{

Console.Write («Сколько сотрудников добавить? «);

try

{

int i = int. Parse (Console.ReadLine ());

Dictionary dic = UserInfo. MyDic (i);

// Получить коллекцию ключей

ICollection keys = dic. Keys;

Console.WriteLine («База данных содержит: «);

foreach (int j in keys)

Console.WriteLine («ID -> {0} Name -> {1}», j, dic[j]);

}

catch (FormatException)

{

Console.WriteLine («Неверный ввод»);

}

Console.ReadLine ();

}

}

}

Результат работы программы представлен на рисунке А.4.

Рисунок А.4 — Пример использования словарей Листинг 6 — Пример использования класса SortedSet

using System;

using System.Collections.Generic;

namespace ConsoleApplication1

{

class Program

{

static void Main ()

{

// Создадим два множества

SortedSet ss = new SortedSet ();

SortedSet ss1 = new SortedSet ();

ss.Add ('A');

ss.Add ('B');

ss.Add ('C');

ss.Add ('Z');

ShowColl (ss, «Первая коллекция: «);

ss1.Add ('X');

ss1.Add ('Y');

ss1.Add ('Z');

ShowColl (ss1, «Вторая коллекция»);

ss.SymmetricExceptWith (ss1);

ShowColl (ss," Исключили разноименность двух множеств: «);

ss.UnionWith (ss1);

ShowColl (ss, «Объединение множеств: «);

ss.ExceptWith (ss1);

ShowColl (ss, «Вычитание множеств»);

Console.ReadLine ();

}

static void ShowColl (SortedSet ss, string s)

{

Console.WriteLine (s);

foreach (char ch in ss)

Console.Write (ch + ««);

Console.WriteLine («n»);

}

}

}

Результат работы программы представлен на рисунке А.5.

Рисунок А.5 — Пример использования класса SortedSet

Листинг 7 — Пример применения параллельных коллекций

using System;

using System.Collections.Concurrent;

using System. Threading;

using System.Threading.Tasks;

namespace ConsoleApplication1

{

class Program

{

static BlockingCollection bc;

static void producer ()

{

for (int i = 0; i < 100; i++)

{

bc.Add (i * i);

Console.WriteLine («Производится число «+ i * i);

}

bc.CompleteAdding ();

}

static void consumer ()

{

int i;

while (!bc.IsCompleted)

{

if (bc.TryTake (out i))

Console.WriteLine («Потребляется число: «+ i);

}

}

static void Main ()

{

bc = new BlockingCollection (4);

Task Pr = new Task (producer);

Task Cn = new Task (consumer);

Pr.Start ();

Cn.Start ();

try

{

Task.WaitAll (Cn, Pr);

}

catch (Exception ex)

{

Console.WriteLine (ex);

}

finally

{

Cn.Dispose ();

Pr.Dispose ();

bc.Dispose ();

}

Console.ReadLine ();

}

}

}

Рисунок А.6 — Применения параллельных коллекций Листинг 8 — Пример использования перечислителей

using System;

using System.Collections.Generic;

namespace ConsoleApplication1

{

class Program

{

static void Main ()

{

List arr = new List ();

Random ran = new Random ();

for (int i = 0; i < 10; i++)

arr.Add (ran.Next (1, 20));

// Используем перечислитель

IEnumerator etr = arr. GetEnumerator ();

while (etr.MoveNext ())

Console.Write (etr.Current + «t»);

Console.WriteLine («n Повторный вызов перечислителя: n»);

// Сбросим значение и вновь исользуем перечислитель

// для доступа к коллекции

etr.Reset ();

while (etr.MoveNext ())

Console.Write (etr.Current + «t»);

Console.ReadLine ();

}

}

}

Результат работы программы с использованием перечислителей представлен на рисунке А.7

Рисунок А.7 — Использование перечислителей Листинг 9 — Пример применения интерфейсов IEnumerator и IEnumerable

using System;

using System. Collections;

namespace ConsoleApplication1

{

class MyInt: IEnumerable, IEnumerator

{

int[] ints = { 12, 13, 1, 4 };

int index = -1;

// Реализуем интерейс IEnumerable

public IEnumerator GetEnumerator ()

{

return this;

}

// Реализуем интерфейс IEnumerator

public bool MoveNext ()

{

if (index == ints. Length — 1)

{

Reset ();

return false;

}

index++;

return true;

}

public void Reset ()

{

index = -1;

}

public object Current

{

get

{

return ints[index];

}

}

}

class Program

{

static void Main ()

{

MyInt mi = new MyInt ();

foreach (int i in mi)

Console.Write (i+" t");

Console.ReadLine ();

}

}

}

Результат работы программы с использованием интерфейсов IEnumerator и Ienumerable представлен на рисунке А.8

Рисунок А.8 — Использование интерфейсов IEnumerator и Ienumerable

Листинг 10 — Пример использования именованного итератора

class Book

{

public Book (string name)

{

this.Name=name;

}

public string Name { get; set; }

}

class Library: IEnumerable

{

private Book[] books;

public Library ()

{

books = new Book[] { new Book («Отцы и дети»), new Book («Война и мир»),

new Book («Евгений Онегин») };

}

public int Length

{

get { return books. Length; }

}

public Book this[int index]

{

get

{

return books[index];

}

set

{

books[index] = value;

}

}

public IEnumerable GetBooks (int max)

{

for (int i = 0; i < max; i++)

{

if (i == books. Length)

{

yield break;

}

else

{

yield return books[i];

}

}

}

}

.ur