Курсовая работа (т): Реализация интерфейса IComparer

Таблица 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;