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

Введение

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

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

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

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

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

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

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

.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 (см. Приложение А) представлен пример использования коллекций, работы с элементами, добавление и удаление некоторых элементов. Приведенный пример взят из источника [3]. Результат работы этой программы представлен на рисунке А.1 в приложении А.

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

objectList = new ArrayList() { 1, 2, "string", 'c', 2.0f };<string> countries = new List<string>() { "Россия", "США", "Великобритания", "Китай" };

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

.Add("string2");

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

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

С помощью свойства Count у коллекций можно посмотреть количество элементов. [3]

.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. Этот интерфейс позволяет перебрать элементы коллекции в цикле. Интерфейс описывает всего один метод:

GetEnumerator();

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

Интерфейс IEnumerator.

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

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

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

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

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

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

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

}

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

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

(ElemType elem in someCollection)

{

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

}

Интерфейс ICollection

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

interface ICollection: Ienumerable

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

Count {get;}

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

CopyTo(Array array, int index);

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

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

(myCollection.SyncRoot)

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

}

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

Интерфейс IList.

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

interface IList : ICollection, Ienumerable

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

this[int index] { get; set; }

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

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

Add(object value);

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

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

Insert(int index, object value);

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

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

Remove(object value);

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

RemoveAt(int index);

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

Clear();

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

Contains(object value);

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

IndexOf(object value);

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

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

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

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

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

1 

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

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

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

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

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

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

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

Структура DictionaryEntry

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

object Key { get; set; }object Value { get; set; }

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

DictionaryEntry(object key, object value)

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

Классы необобщенных коллекций

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Список List<T>

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Очередь Queue<T>

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

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

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

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

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

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

Рисунок 1 - Очередь Queue<T>

Стек Stack<T>

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

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

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

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

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

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

Рисунок 2 - Стек Stack<T>

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

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

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

Этот класс имеет следующие свойства: [3]: само значение узла, представленное типом T: ссылка на следующий элемент типа LinkedListNode<T> в списке. Если следующий элемент отсутствует, то имеет значение null: ссылка на предыдущий элемент типа LinkedListNode<T> в списке. Если предыдущий элемент отсутствует, то имеет значение null

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Рисунок 3 - Класс LinkedList<T>

Словарь Dictionary<T, V>

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

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

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

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

Рисунок 4 - Модель словаря

Тип ключа

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Класс Dictionary<TKey, TValue>

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

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

Dictionary()Dictionary(IDictionary<TKey, TValue> dictionary)

public Dictionary(int capacity)

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

В классе Dictionary<TKey, TValue> определяется также ряд методов:()

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

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

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

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

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

Таблица 4 - Собственные свойства класса Dictionary<TKey, TValue>

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

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

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

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

TKey Key;TValue Value;

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

Классы HashSet<T> и SortedSet<T>

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

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

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

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

HashSet ()HashSet(IEnumerable<T> collection)

public HashSet(IEqualityCompare comparer)

public HashSet(IEnumerable<T> collection, IEqualityCompare comparer)

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

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

IEqualityComparer<T> Comparer { get; }

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

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

public SortedSet()SortedSet(IEnumerable<T> collection)SortedSet(IComparer comparer)SortedSet(IEnumerable<T> collection, IComparer comparer)

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

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

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

IComparer<T> Comparer { get; }T Max { get; }T Min { get; }

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

Класс SortedDictionary<TKey, TValue>

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

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

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

SortedDictionary<TKey, TValue> быстрее вставляет и удаляет элементы.

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

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

SortedDictionary()SortedDictionary(IDictionary<TKey, TValue> dictionary)SortedDictionary(IComparer<TKey> comparer)SortedDictionary(IDictionary<TKey, TValue> dictionary, IComparer<TKey> comparer)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

5.2 Наблюдаемые коллекции

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

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

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

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

data = new ObservableCollection<string>();.CollectionChanged += Data_CollectionChanged;.Add("One");.Add("Two");.Insert(1, "Three");

data.Remove("One");

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

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

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

. Битовые коллекции

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

.1 Класс BitArray

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

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

BitArray(bool[] values)

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

BitArray(byte[] bytes)

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

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

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

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

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

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

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

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

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

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

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

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

int Length { get; set; }

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

.2 Структура BitVector

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

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

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

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

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

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

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

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

var bitsl = new BitVector32 () ;bitl = BitVector32.CreateMask();bit2 = BitVector32.CreateMask(bitl);bit3 = BitVector32.CreateMask(bit2);bit4 = BitVector32.CreateMask(bit3);bit5 = BitVector32.CreateMask(bit4);[bitl] = true;[bit2] = false;[bit3] = true;[bit4] = true;[bi15] = true;.WriteLine(bits1);

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

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

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

CompareTo(object obj)

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

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

CompareTo(Т other). [2]

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

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

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

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

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

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

Compare(object x, object у)

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

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

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

 Compare(Т х, T у)

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

9. Перечислители

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

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

Current {get;}

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

Т Current {get;}

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

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

MoveNext()

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

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

Reset()

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

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

.1 Применение обычного перечислителя

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

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

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

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

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

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

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

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

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

bool MoveNext()

{(index == ints.Length - 1)

{();false;

}++;true;

}

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

public IEnumerator GetEnumerator()

{this;

}

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

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

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

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

System.Collections.IEnumerator GetEnumerator()

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

{return i;

}

}

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

static void Main()

{listClass1 = new ListClass();

(int i in listClass1)

{.Console.WriteLine(i);

}

}

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

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

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

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

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

{return i;

}

}

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

test = new ListClass();(int n in test.SampleIterator(1, 10))

{.Console.WriteLine(n);

}

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

public System.Collections.IEnumerator GetEnumerator()

{return "With an iterator, ";return "more than one ";return "value can be returned";

yield return ".";

}

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

(string element in new TestClass())

{.Console.Write(element);

}

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

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

IEnumerable.GetEnumerator()

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

{return books[i];

}

}

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

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

(Book b in library)

{.WriteLine(b.Name);

}

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

IEnumerable.GetEnumerator()

{return books[0];return books[1];return books[2];

}

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

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

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

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

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

IEnumerable GetBooks(int max)

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

{(i == books.Length)

{break;

}

{return books[i];

}

}

}

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

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

library = new Library();(Book b in library.GetBooks(5))

{.WriteLine(b.Name);

}

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

(i == books.Length)

{break;

}

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

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

System;System.Collections;MyClass

{ch = 'A';

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

}

}

Заключение

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

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

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

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

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

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

Приложение

Листинги и результаты работы программ

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

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

using System;System.Collections;System.Collections.Generic;

Collections

{Program

{void Main(string[] args)

{

// необобщенная коллекция ArrayListobjectList = new ArrayList() { 1, 2, "string", 'c', 2.0f };

obj = 45.8;.Add(obj);.Add("string2");.RemoveAt(0); // удаление первого элемента

(object o in objectList)

{.WriteLine(o);

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

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

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

.Add("Франция");.RemoveAt(1); // удаление второго элемента(string s in countries)

{.WriteLine(s);

}.ReadLine();

}

}

}

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

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

Листинг 2 - Реализация списка List<T>

using System;System.Collections.Generic;

Collections

{Program

{void Main(string[] args)

{<int> numbers = new List<int>() { 1, 2, 3, 45 };.Add(6); // добавление элемента

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

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

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

(int i in numbers)

{.WriteLine(i);

}

<Person> persons = new List<Person>(3);.Add(new Person() { Name = "Том" });.Add(new Person() { Name = "Билл" });

(Person p in persons)

{.WriteLine(p.Name);

}

.ReadLine();

}

}

Person

{string Name { get; set; }

}

}

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

System;System.Collections.Generic;

Collections

{Program

{void Main(string[] args)

{<int> numbers = new Queue<int>();

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

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

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

<Person> persons = new Queue<Person>();

.Enqueue(new Person() { Name = "Tom" });.Enqueue(new Person() { Name = "Bill" });.Enqueue(new Person() { Name = "John" });

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

Person pp = persons.Peek();.WriteLine(pp.Name);

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

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

foreach (Person p in persons)

{.WriteLine(p.Name);

}

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

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

.WriteLine(person.Name);.ReadLine();

}

}

Person

{string Name { get; set; }

}

}

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

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

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

System;System.Collections.Generic;

Collections

{Program

{void Main(string[] args)

{<int> numbers = new LinkedList<int>();

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

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

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

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

foreach (int i in numbers)

{.WriteLine(i);

}

<Person> persons = new LinkedList<Person>();

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

LinkedListNode<Person> tom = persons.AddLast(new Person() { Name = "Tom" });.AddLast(new Person() { Name = "John" });.AddFirst(new Person() { Name = "Bill" });

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

Console.ReadLine();

}

}

Person

{string Name { get; set; }

}

}

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

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

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

System;System.Collections.Generic;

ConsoleApplication1

{UserInfo

{

// Метод, реализующий словарьstatic Dictionary<int, string> MyDic(int i)

{<int, string> dic = new Dictionary<int,string>();.WriteLine("Введите имя сотрудника: \n");

string s;(int j = 0; j < i; j++)

{.Write("Name{0} --> ",j);= Console.ReadLine();.Add(j, s);.Clear();

}dic;

}

}Program

{void Main()

{

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

{i = int.Parse(Console.ReadLine());<int, string> dic = UserInfo.MyDic(i);

// Получить коллекцию ключей<int> keys = dic.Keys;

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

foreach (int j in keys).WriteLine("ID -> {0} Name -> {1}",j,dic[j]);

}(FormatException)

{.WriteLine("Неверный ввод");

}.ReadLine();

}

}

}

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

Рисунок А.4 - Пример использования словарей

Листинг 6 - Пример использования класса SortedSet<T>

System;System.Collections.Generic;

ConsoleApplication1

{Program

{void Main()

{

// Создадим два множества<char> ss = new SortedSet<char>();<char> ss1 = new SortedSet<char>();.Add('A');.Add('B');.Add('C');.Add('Z');

ShowColl(ss, "Первая коллекция: ");.Add('X');

ss1.Add('Y');.Add('Z');(ss1, "Вторая коллекция");

.SymmetricExceptWith(ss1);

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

.ExceptWith(ss1);(ss, "Вычитание множеств");

Console.ReadLine();

}void ShowColl(SortedSet<char> ss, string s)

{.WriteLine(s);(char ch in ss).Write(ch + " ");.WriteLine("\n");

}

}

}

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

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

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

System;System.Collections.Concurrent;System.Threading;System.Threading.Tasks;

ConsoleApplication1

{Program

{BlockingCollection<int> bc;

void producer()

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

{

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

}.CompleteAdding();

}

void consumer()

{i;(!bc.IsCompleted)

{(bc.TryTake(out i)).WriteLine("Потребляется число: " + i);

}

}

static void Main()

{= new BlockingCollection<int>(4);Pr = new Task(producer);Cn = new Task(consumer);.Start();.Start();

{.WaitAll(Cn, Pr);

}(Exception ex)

{.WriteLine(ex);

}

{.Dispose();.Dispose();.Dispose();

}

.ReadLine();

}

}

}

Рисунок А.6 - Применения параллельных коллекций

Листинг 8 - Пример использования перечислителей

System;System.Collections.Generic;ConsoleApplication1

{Program

{void Main()

{<int> arr = new List<int>();ran = new Random();(int i = 0; i < 10; i++)

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

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

IEnumerator<int> etr = arr.GetEnumerator();(etr.MoveNext()).Write(etr.Current + "\t");

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

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

// для доступа к коллекции.Reset();

while (etr.MoveNext()).Write(etr.Current + "\t");

Console.ReadLine();

}

}

}

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

Рисунок А.7 - Использование перечислителей

Листинг 9 - Пример применения интерфейсов IEnumerator и IEnumerable

System;System.Collections;ConsoleApplication1

{MyInt : IEnumerable, IEnumerator

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

// Реализуем интерейс IEnumerableIEnumerator GetEnumerator()

{this;

}

// Реализуем интерфейс IEnumeratorbool MoveNext()

{(index == ints.Length - 1)

{();false;

}++;true;

}void Reset()

{= -1;

}object Current

{

{ints[index];

}

}

}Program

{void Main()

{mi = new MyInt();(int i in mi).Write(i+"\t");.ReadLine();

}

}

}

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

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

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

Book

{Book(string name)

{.Name=name;

}string Name { get; set; }

}Library : IEnumerable

{Book[] books;

Library()

{= new Book[] { new Book("Отцы и дети"), new Book("Война и мир"),Book("Евгений Онегин") };

}int Length

{{ return books.Length; }

}Book this[int index]

{

{books[index];

}

{

books[index] = value;

}

}

public IEnumerable GetBooks(int max)

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

{(i == books.Length)

{break;

}

{return books[i];

}

}

}

}