Лекция 7. Collections [.NET Framework] презентация

Функции CTS
Система общих типов определяет способ объявления, использования и управления типами во время выполнения, а также поддерживает межъязыковую интеграцию в среде выполнения.
Устанавливает инфраструктуру, помогающую обеспечивать строгую типизацию, межъязыковую интеграцию и высокопроизводительное выполнение кода.
Предоставляет объектно-ориентированную модель, поддерживающую реализацию многих языков программирования.
Определяет правила, которых необходимо придерживаться в языке.

Контейнерные типы .NET Framework
Контейнеры или классы коллекций являются типами, которые хранят объекты, поддерживают способы обращения к ним, определяют функциональность объектов и могут использоваться в прикладных задачах.
Коллекция представляет собой набор объектов схожих типов. В коллекцию могут быть сгруппированы объекты любого типа, в том числе типа Object.
Типы коллекции, это распространенные виды коллекций данных, такие как стеки, очереди, хэш-таблицы, словари и списки.
Достоинство – использование конструкций, свойственных определенному языку.
Для работы с коллекциями предназначены интерфейсы.

Виды коллекций
Неуниверсальные, необщие, не родовые коллекции основаны на использовании шаблонов.
Исторически первые в .Net.Framework 1.0.
Находятся в пространстве имен System::Collection.
Хранят ссылки на объекты общего типа Object.
Контроль типов возлагается на разработчика.
Требуется приведение типов хранимых данных к Object при извлечении объекта.

Виды коллекций
Универсальные (общие, родовые, типизированные) коллекции основаны на использовании родовых классов.
Исторически появились в .Net.Framework 2.0.
Находятся в пространстве имен System::Collection::Generic.
Хранят ссылки на объекты порожденного типа.
Контроль типов происходит при добавлении элемента в коллекцию.
Коллекции различаются по тому, как элементы хранятся, как сортируются, как производится поиск и как выполняются сравнения.

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

Некоторые особенности коллекций
1. Перечислитель
Перечислитель – это объект, который выполняет итерацию в связанной с ним коллекции. Является перемещаемым указателем на любой элемент коллекции.
Перечислитель может быть связан только с одной коллекцией, но коллекция может иметь несколько перечислителей.
Оператор for each использует перечислитель и упрощает обращение с коллекцией.

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

Некоторые особенности коллекций
3. Емкость и количество элементов
Емкость коллекции Capacity, это число элементов, которое она может содержать. Количество элементов коллекции Count, это число элементов, которое она реально содержит.
Все коллекции System.Collections автоматически увеличивают емкость, если количество элементов достигает предела. Происходит перераспределение памяти, и элементы копируются из старой коллекции в новую.
Чтобы избежать потерь производительности, вызванных перераспределениями, следует установить начальную вместимость, равную предполагаемому размеру коллекции.

Некоторые особенности коллекций
4. Нижняя граница
Нижняя граница коллекции, это индекс ее первого элемента. Все индексированные коллекции в пространствах имен System.Collections имеют нижнюю границу, равную нулю. Array имеет нижнюю границу, равную нулю, по умолчанию, но при создании экземпляра Array с помощью CreateInstance может быть определена другая нижняя граница.

Виды коллекций
Часто используемые коллекции. Это распространенные виды коллекций данных, такие как хэш-таблицы, очереди, стеки, словари и списки. Имеют свои универсальные и неуниверсальные версии.
Битовые коллекции. Это коллекции, элементами которых являются битовые флаги. Их поведение отличается от поведения других коллекций.
Специализированные коллекции. Эти коллекции предназначены для реализации узких задач, обычно для обработки элементов определенного типа, такого как StringDictionary.

Структуры данных .Net
Тип коллекций Array – массивы, которые позволяют рассматривать их как коллекции.
Типы коллекций ArrayList и List – универсальные и нестандартные списки.
Типы коллекций Hashtable и Dictionary – универсальные и нестандартные типы словарей, основанных на хэше.
Типы коллекций SortedList и SortedDictionary – сортируемые словари и гибридные типы, объединяющие функции словаря и списка.
Тип коллекций Queue – универсальные и нестандартные очереди.
Типы коллекций Stack – универсальные и нестандартные стеки.
Тип коллекции HashSet – универсальный тип коллекции HashSet
.

Тип коллекции Stack
Общий тип «Стек» реализован как класс:
Stack в пространстве имен System.Collections.
Stack в пространстве имен System.Collections.Generic.
Оба являются классами коллекций с обратным порядком обработки элементов (LIFO – last-in-first-out), реализующими интерфейс ICollection.
Универсальный класс Stack
также реализует универсальный интерфейс ICollection
.

Класс Stack – реализация
Класс Stack реализован в виде циклического буфера.
Емкость коллекции Stack, это количество элементов, которое может вместить коллекция. Когда в коллекцию Stack добавляются элементы, емкость автоматически увеличивается посредством перераспределения.
Если значение свойства Count меньше значения емкости стека, метод Push является операцией O(1). Если для размещения нового элемента требуется увеличить емкость, метод Push становится операцией O(n), где n определяет значение свойства Count. Метод Pop является операцией O(1).
Объект Stack принимает значение nullptr как допустимое и разрешает дублировать элементы.

Создание и заполнение стека
// Объявление стека.
Stack^ My_Stack = gcnew Stack;
// Наполнение стека.
My_Stack ->Push("One" );
My_Stack ->Push("Two" );
My_Stack ->Push("Three" );

Перегрузка конструктора
Stack() – инициализирует новый пустой экземпляр класса Stack с начальной емкостью по умолчанию.
Stack(Int32) – инициализирует новый экземпляр класса Stack, который является пустым и обладает указанной начальной емкостью или емкостью по умолчанию, в зависимости от того, какое значение больше.
Stack(ICollection) – инициализирует новый экземпляр класса Stack, который содержит элементы, скопированные из указанной коллекции, и обладает начальной емкостью, равной количеству скопированных элементов.

Методы класса Stack
Pop – удаляет и возвращает верхний объект стека.
Push – вставляет объект как верхний элемент стека.
Peek – возвращает верхний объект стека, не удаляя его.
Contains – определяет, входит ли элемент в состав коллекции Stack.
Clear – удаляет все объекты из коллекции Stack.
CopyTo – копирует элементы класса Stack в существующий одномерный массив класса Array, начиная с указанного индекса массива.

Методы класса Stack
GetType – возвращает объект Type для текущего экземпляра (унаследовано от Object).
ToArray – копирует элементы Stack в новый массив.
ToString – возвращает объект String, который представляет текущий объект Object (унаследовано от Object).

Проблемы универсальности
Стек хранит ссылки на универсальные объекты типа Object.
Извлекаемый из стека элемент является дескриптором объекта.
Object^ Obj = safe_cast
(My_Stack_1->Pop());
Возвращаемое значение нужно проверять:
if (Obj->ToString()!="")
if (Obj != nullptr)

Тип коллекции Queue
Класс Queue и универсальный класс Queue
, это классы коллекций с прямым порядком обработки элементов (FIFO – first-in-first-out), реализующие интерфейс ICollection и универсальный интерфейс ICollection
.
Queue в пространстве имен System.Collections.
Queue
в пространстве имен System.Collections.Generic.
В коллекции Queue значение nullptr является допустимым.
Разрешается повторение элементов.

Реализация очереди
Класс Queue реализует очередь в виде циклического массива. Объекты добавляются в конец очереди, а удаляются из начала.
Емкость коллекции Queue, это количество элементов, которое может вместить коллекция. Когда в коллекцию Queue добавляются элементы, ее емкость автоматически увеличивается посредством перераспределения. Емкость может быть уменьшена вызовом метода TrimToSize.
Для коллекции Queue определяется коэффициент роста – число, на которое умножается текущая емкость при необходимости ее увеличения. По умолчанию 2,0. Независимо от коэффициента роста, емкость коллекции Queue всегда увеличивается не меньше, чем на 4.

Основные операции Queue
Enqueue – добавляет элемент в конец очереди.
Dequeue – удаляет элемент из начала очереди.
Peek – возвращает элемент из начала очереди, но не удаляет его из Queue.
Clear – удаляет все объекты из коллекции Queue.
Contains – определяет, принадлежит ли элемент коллекции Queue.
CopyTo – копирует элементы коллекции Queue в существующий одномерный массив Array начиная с указанного значения индекса массива.
TrimToSize – задает значение емкости, равное действительному количеству элементов в коллекции Queue.

Основные операции Queue
ToArray – копирует элементы коллекции Queue в новый массив.
ToString – возвращает объект String, который представляет текущий объект Object.
Пример.

Типы коллекций Hashtable и Dictionary
Класс Hashtable и универсальный класс Dictionary
реализуют интерфейс IDictionary. Универсальный класс
Dictionary
также реализует универсальный интерфейс IDictionary
.
Каждый элемент в этих коллекциях является парой «значение-ключ».
Объект Hashtable состоит из сегментов, содержащих элементы коллекции. Сегмент, это виртуальная подгруппа элементов внутри объекта Hashtable, позволяющая упростить и ускорить поиск и извлечение элементов по сравнению с большинством коллекций.

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

Объект Hashtable
Для каждого объекта, который используется как элемент в Hashtable, можно создать собственный хэш-код, используя реализацию метода GetHashCode.
Можно указать хэш-функцию для всех элементов в Hashtable, используя конструктор Hashtable, принимающий реализацию IHashCodeProvider в качестве одного из своих параметров.
Например, если хэш-функция для строки использует сумму ASCII-кодов всех ее знаков, то строки «пикник» и «корзина» будут иметь различные хэш-коды и будут находиться в разных сегментах.
Строки «приказ» и «каприз» будут иметь одинаковый хэш-код и будут находиться в одном сегменте.

Объект Hashtable
Каждый элемент в паре «ключ-значение» хранится в объекте DictionaryEntry. Ключ не может быть равным ссылке nullptr, а значение может.
Объекты, используемые в качестве ключей в коллекции Hashtable, должны быть доступны только для чтения.
Емкость коллекции Hashtable, это количество элементов, которое может вместить коллекция. Когда в коллекцию Hashtable добавляются элементы, ее емкость автоматически увеличивается посредством перераспределения.

Объект Hashtable
При добавлении элемента в коллекцию Hashtable, фактический показатель загрузки коллекции увеличивается. Когда фактический показатель загрузки становится равным заданному, количество сегментов в объекте Hashtable автоматически увеличивается до наименьшего простого числа, которое больше удвоенного текущего количества сегментов в коллекции Hashtable.
Показатель загрузки коллекции Hashtable определяет максимальное отношение количества элементов к количеству сегментов. Снижение показателя загрузки уменьшает среднее время поиска за счет увеличения объема используемой памяти. Значение показателя загрузки по умолчанию равно 1,0.

Некоторые методы Hashtable
Add – добавляет элемент с указанными ключом и значением в коллекцию Hashtable.
Clear – удаляет все элементы из коллекции.
Contains – определяет, содержит ли коллекция указанный элемент.
ContainsKey – определяет, содержит ли коллекция указанный ключ.
ContainsValue – определяет, содержит ли коллекция указанное значение.
CopyTo – копирует элементы коллекции Hashtable в экземпляр класса одномерного массива Array по указанному индексу.

Некоторые методы Hashtable
GetHash – возвращает хэш-код указанного ключа.
GetHashCode – играет роль хэш-функции для определенного типа, унаследовано от Object.
GetType – возвращает объект Type для текущего экземпляра.
ToString – возвращает объект String, который представляет текущий объект Object.
Remove – удаляет элемент с указанным ключом из коллекции.
KeyEquals – сравнивает указанный объект класса Object с указанным ключом, который содержится в коллекции Hashtable.

Итерация по элементам коллекции
Метод GetEnumerator возвращает объект IDictionaryEnumerator, который может осуществлять просмотр всех элементов коллекции Hashtable.
Для итерации по элементам таблицы используется оператор for each, для которого необходима информация о типе каждого элемента коллекции.
Каждый элемент коллекции Hashtable представляет собой пару «ключ-значение», и тип элемента не является типом ключа или типом значения, поэтому в качестве типа элемента используется DictionaryEntry.
Пример.

Пример
// Класс Hashtable.
Hashtable ^My_Table;
My_Table = gcnew Hashtable;
// Добавление элементов в коллекцию.
My_Table->Add("One","One_content");
My_Table->Add("Two","Two_content"); My_Table->Add("Three","Three_content");
My_Table->Add("Four","Four_content");

Пример
String ^ Str = gcnew String("");
for each( DictionaryEntry D in My_Table )
{
Str=D.Key+" "+D.Value;
// Можно перегрузить ToString().
this->listBox3->Items->Add(Str);
}

Объект Dictionary
Класс Dictionary
имеет такую же функциональность, как и класс Hashtable.
Dictionary
определенного типа, отличного от Object, имеет лучшую производительность по сравнению с Hashtable, так как элементы Hashtable имеют тип Object и, следовательно, при сохранении или извлечении типа значения происходит упаковка и распаковка.

Типы коллекций ArrayList и List
Класс ArrayList реализует интерфейс IList с помощью массива с динамическим увеличением размера до нужного значения. Находится в пространстве имен System.Collections.
Класс List
реализует универсальный интерфейс IList
с помощью массива, размер которого динамически увеличивается по мере необходимости.
List
представляет строго типизированный список объектов, доступных по индексу. Поддерживает методы для поиска по списку, выполнения сортировки и других операций со списками.
Находится в пространстве имен System.Collections.Generic.

Реализация ArrayList
Емкость коллекции ArrayList, это количество элементов, которое может вместить коллекция. При добавлении элементов в коллекцию, ее емкость автоматически увеличивается посредством перераспределения.
Емкость может быть уменьшена вызовом метода TrimToSize или с помощью явного задания свойства Capacity.
Доступ к элементам коллекции осуществляется с помощью целочисленного индекса, нумерация с нуля.
Объект ArrayList принимает значение nullptr как допустимое и разрешает дублировать элементы.

Создание и заполнение ArrayList
// Создает новый ArrayList.
ArrayList^ My_List = gcnew ArrayList;
My_List ->Add( " One" );
My_List ->Add( " Two" );
My_List ->Add( " Three" );

Итерация по элементам списка
IEnumerator^ My_enum=My_List->GetEnumerator();
while (My_enum>MoveNext())
{
Object^ Obj = safe_cast
(My_enum>Current);
//Что-то делать с Obj;
}

Некоторые свойства списка
Capacity – получает или задает число элементов, которое может содержать список ArrayList.
Count – получает число элементов, которое в действительности содержится в списке ArrayList.
Item – получает или задает элемент по указанному индексу.

Некоторые методы списка
ArrayList – конструктор, перегружен, инициализирует новый экземпляр класса ArrayList.
Add – добавляет объект в конец списка.
AddRange – добавляет элементы интерфейса ICollection в конец списка.
BinarySearch – использует алгоритм двоичного поиска для нахождения элемента в отсортированном списке ArrayList или в его части.
Clear – удаляет все элементы из списка ArrayList.
Contains – определяет, входит ли элемент в состав коллекции ArrayList.

Некоторые методы списка
CopyTo – копирует список ArrayList или его часть в одномерный массив.
Equals – определяет, равен ли заданный объект Object текущему объекту Object.
GetEnumerator – возвращает перечислитель, осуществляющий перебор элементов списка ArrayList.
GetType – возвращает объект Type для текущего экземпляра.
IndexOf – возвращает индекс (с нуля) первого вхождения значения в списке ArrayList или в его части.
Insert – вставляет элемент в список ArrayList по указанному индексу.

Некоторые методы списка
InsertRange – вставляет элементы коллекции в список ArrayList по указанному индексу.
LastIndexOf – возвращает индекс последнего вхождения значения в списке ArrayList или в его части.
Remove – удаляет первое вхождение указанного объекта из списка ArrayList.
RemoveAt – удаляет элемент с указанным индексом из списка ArrayList.
RemoveRange – удаляет диапазон элементов из списка ArrayList.
Reverse – изменяет порядок элементов в списке ArrayList или в его части на обратный.

Некоторые методы списка
SetRange – копирует элементы коллекции в диапазон элементов списка ArrayList.
Sort – сортирует элементы в списке ArrayList или в его части.
ToArray – копирует элементы списка в новый массив.
ToString – возвращает объект String, который представляет текущий объект Object.
TrimToSize –задает значение емкости, равное фактическому количеству элементов в списке ArrayList

Интерфейсы для работы с коллекциями

ICollection