Лекция 7. Collections [.NET Framework]

1. Common Type System – общая система типов

.NET Framework содержит классы, интерфейсы и типы
значений, которые облегчают процесс разработки и
обеспечивают доступ к функциям системы.
Классы .NET Framework могут быть представлены как
абстрактные или конкретные.
Существующие классы можно использовать как объекты
или на их основе можно создавать собственные
производные классы.
Чтобы использовать возможности интерфейса, можно
либо создать класс, реализующий интерфейс, либо создать
производный класс на основе одного из классов .NET
Framework, реализующего интерфейс.

2. Функции CTS

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

3. Контейнерные типы .NET Framework

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

4. Виды коллекций

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

5. Виды коллекций

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

6. Интерфейсы

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

7. Некоторые особенности коллекций

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

8. Некоторые особенности коллекций

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

9. Некоторые особенности коллекций

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

10. Некоторые особенности коллекций

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

11. Виды коллекций

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

12. Структуры данных .Net

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

13. Тип коллекции Stack

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

14. Класс Stack – реализация

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

15. Создание и заполнение стека

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

16. Перегрузка конструктора

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

17. Методы класса Stack

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

18. Методы класса Stack

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

19. Проблемы универсальности

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

20. Тип коллекции Queue

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

21. Реализация очереди

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

22. Основные операции Queue

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

23. Основные операции Queue

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

24. Типы коллекций Hashtable и Dictionary

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

25. Объект Hashtable

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

26. Объект Hashtable

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

27. Объект Hashtable

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

28. Объект Hashtable

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

29. Некоторые методы Hashtable

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

30. Некоторые методы Hashtable

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

31. Итерация по элементам коллекции

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

32. Пример

// Класс 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");

33. Пример

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

34. Объект Dictionary<TKey, TValue>

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

35. Типы коллекций ArrayList и List

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

36. Реализация ArrayList

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

37. Создание и заполнение ArrayList

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

38. Итерация по элементам списка

IEnumerator^ My_enum=My_List->GetEnumerator();
while (My_enum>MoveNext())
{
Object^ Obj = safe_cast<Object^>
(My_enum>Current);
//Что-то делать с Obj;
}

39. Некоторые свойства списка

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

40. Некоторые методы списка

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

41. Некоторые методы списка

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

42. Некоторые методы списка

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

43. Некоторые методы списка

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

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

45. ICollection

46. IEnumerator