Коллекции (контейнерные классы). Лекция 36

1.

Лекция 36
Коллекции (контейнерные
классы)
1

2.

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

3.

Коллекции (контейнерные классы)
Каждый элемент списка содержит ключ,
идентифицирующий этот элемент. Ключ обычно
бывает либо целым числом, либо строкой и является
частью данных, хранящихся в каждом элементе
списка.
Над списками можно выполнять операции добавления,
удаления и вставки элемента, чтения элемента с
заданным ключом, упорядочивания списка по ключу
(ключам). Список не обеспечивает произвольный
доступ к элементу, поэтому при выполнении
операций чтения, вставки и удаления выполняется
последовательный перебор элементов, пока не будет
найден элемент с заданным ключом.
3

4.

Коллекции (контейнерные классы)
Стек — частный случай однонаправленного списка,
добавление элементов в который и выборка из
которого выполняются с одного конца, называемого
вершиной стека. Другие операции со стеком не
определены. При выборке элемент исключается из
стека. Стек реализует принцип обслуживания LIFO (Last In —
First Out, последним пришел — первым ушел).
Очередь — частный случай однонаправленного списка,
добавление элементов в который выполняется в один
конец, а выборка — из другого конца. Другие
операции с очередью не определены. При выборке
элемент исключается из очереди.
Очередь реализует принцип обслуживания FIFO (First In — First
Out, первым пришел — первым ушел).
4

5.

Коллекции (контейнерные классы)
Бинарное дерево — динамическая структура данных,
состоящая из узлов, каждый из которых содержит,
помимо данных, не более двух ссылок на различные
бинарные поддеревья. На каждый узел имеется ровно
одна ссылка. Начальный узел называется корнем
дерева. Узел, не имеющий поддеревьев,
называется листом. Исходящие узлы
называются предками, входящие — потомками.
Высота дерева определяется количеством уровней,
на которых располагаются его узлы.
5

6.

Коллекции (контейнерные классы)
6

7.

Коллекции (контейнерные классы)
Если дерево организовано таким образом, что для
каждого узла все ключи его левого поддерева меньше
ключа этого узла, а все ключи его правого поддерева
— больше, оно называется деревом поиска.
Одинаковые ключи не допускаются. В дереве поиска
можно найти элемент по ключу, двигаясь от корня и
переходя на левое или правое поддерево в
зависимости от значения ключа в каждом узле. Такой
поиск гораздо эффективнее поиска по списку,
поскольку время поиска определяется высотой
дерева, а она пропорциональна двоичному логарифму
количества узлов.
7

8.

Коллекции (контейнерные классы)
Хеш-таблица, ассоциативный массив, или словарь —
это массив, доступ к элементам которого
осуществляется не по номеру, а по некоторому ключу.
Можно сказать, что это таблица, состоящая из пар
"ключ-значение". Хеш-таблица эффективно реализует
операцию поиска значения по ключу. При этом ключ
преобразуется в число ( хэш-код ), которое
используется для быстрого нахождения нужного
значения в хеш-таблице.
Ключ
Значение
boy
мальчик
girl
девочка
dog
собачка
8

9.

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

10.

Коллекции (контейнерные классы)
Граф — это совокупность узлов и ребер, соединяющих
различные узлы. Например, можно представить себе
карту автомобильных дорог как граф с городами в
качестве узлов и шоссе между городами в качестве
ребер. Множество реальных практических задач
можно описать в терминах графов, что делает их
структурой данных, часто используемой при
написании программ.
Множество — это неупорядоченная совокупность
элементов. Для множеств определены операции
проверки принадлежности элемента множеству,
включения и исключения элемента, а также
объединения, пересечения и вычитания множеств.
10

11.

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

12.

Коллекции (контейнерные классы)
Большая часть классов коллекций содержится в
пространствах имен System.Collections
(простые необобщенные классы коллекций),
System.Collections.Generic (обобщенные или
типизированные классы коллекций)
и System.Collections.Specialized (специальные
классы коллекций). Также для обеспечения
параллельного выполнения задач и
многопоточного доступа применяются классы
коллекций из пространства имен
System.Collections.Concurrent.
12

13.

Коллекции (контейнерные классы)
Основой для создания всех коллекций является
реализация интерфейсов IEnumerator и
IEnumerable (и их обобщенных двойников
IEnumerator<T> и IEnumerable<T>). Интерфейс
Enumerator представляет перечислитель, с
помощью которого становится возможен
последовательный перебор коллекции, например,
в цикле foreach. А интерфейс IEnumerable через
свой метод GetEnumerator предоставляет
перечислитель всем классам, реализующим
данный интерфейс. Поэтому интерфейс
IEnumerable (IEnumerable<T>) является
базовым для всех коллекций.
13

14.

Необобщенные коллекции
Необобщенные или простые коллекции определены в
пространстве имен System.Collections.
Основные интерфейсы:
IEnumerable: определяет метод GetEnumerator. Данный
метод возвращает перечислитель - то есть некоторый
объект, реализующий интерфейс IEnumerator.
IEnumerator: реализация данного интерфейса
позволяет перебирать элементы коллекции с
помощью цикла foreach
ICollection: является основой для всех необобщенных
коллекций, определяет основные методы и свойства для всех
необобщенных коллекций (например, метод CopyTo и
свойство Count). Данный интерфейс унаследован от
интерфейса IEnumerable, благодаря чему базовый интерфейс
также реализуется всеми классами необобщенных коллекций
14

15.

Необобщенные коллекции
IList: позволяет получать элементы коллекции по
порядку. Также определяет ряд методов для
манипуляции элементами: Add(добавление
элементов), Remove/RemoveAt (удаление элемента) и
ряд других.
IComparer: определяет метод int Compare(object x,
object y) для сравнения двух объектов
IDictionary: определяет поведение коллекции, при
котором она должна хранить объекты в виде пар
ключ-значение: для каждого объекта определяется
уникальный ключ, и этому ключу соответствует
определенное значение
IDictionaryEnumerator: определяет методы и свойства
15
для перечислителя словаря

16.

Необобщенные коллекции
IEqualityComparer: определяет два
метода Equals и GetHashCode, с помощью которых
два объекта сравниваются на предмет равенства
IStructuralComparer: определяет метод Compare для
структурного сравнения двух объектов: при таком
сравнении сравниваются не ссылки на объекты, а
непосредственное содержимое объектов
IStructuralEquatable: позволяет провести структурное
равенство двух объектов. Как и в случае с
интерфейсом IStructuralComparer сравнивается
содержимое двух объектов
16

17.

Необобщенные коллекции
Эти интерфейсы реализуются следующими классами коллекций
в пространстве имен System.Collections:
ArrayList: класс простой коллекции объектов. Реализует
интерфейсы IList, ICollection, IEnumerable
BitArray: класс коллекции, содержащей массив битовых
значений. Реализует интерфейсы ICollection, IEnumerable
Hashtable: класс коллекции, представляющей хэш-таблицу и
хранящий набор пар "ключ-значение"
Queue: класс очереди объектов, работающей по алгоритму FIFO
("первый вошел -первый вышел"). Реализует интерфейсы
ICollection, IEnumerable
SortedList: класс коллекции, хранящей наборы пар "ключзначение", отсортированных по ключу. Реализует интерфейсы
ICollection, IDictionary, IEnumerable
Stack: класс стека
17

18.

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

19.

Свойства интерфейса IList
int Count { get; } Содержит количество элементов в
коллекции на данный момент
bool IsSynchronized { get; } Принимает логическое
значение true, если коллекция синхронизирована, а
иначе — логическое значение false. По умолчанию
коллекции не синхронизированы.
Но для большинства коллекций можно получить
синхронизированный вариант
object SyncRoot { get; } Содержит объект, для которого
коллекция может быть синхронизирована
bool IsFixedSize { get; } Содержит логическое значение
true, если коллекция имеет фиксированный размер
bool IsReadOnly { get; } Содержит логическое значение
true, если коллекция доступна только для чтения 19

20.

Методы интерфейса IList
int Add(object value) Добавляет объект value в
вызывающую коллекцию. Возвращает индекс, по
которому этот объект сохраняется
void Clear() Удаляет все элементы из вызывающей
коллекции
bool Contains (object value) Возвращает логическое
значение true, если вызывающая коллекция содержит
объект value, а иначе — логическое значение false
int IndexOf(object value) Возвращает индекс объекта
value, если этот объект содержится в вызывающей
коллекции. Если же объект value не обнаружен, то
метод возвращает значение -1
20

21.

Методы интерфейса IList
void Insert(int index,object value) Вставляет в
вызывающую коллекцию объект value по индексу
index. Элементы, находившиеся до этого по индексу
index и дальше, смещаются вперед, чтобы освободить
место для вставляемого объекта value
void Remove(object value) Удаляет первое вхождение
объекта value в вызывающей коллекции. Элементы,
находившиеся до этого за удаленным элементом, смещаются
назад, чтобы устранить образовавшийся “пробел"
void RemoveAt(int index) Удаляет из вызывающей
коллекции объект, расположенный по указанному
индексу index. Элементы, находившиеся до этого за
удаленным элементом, смещаются назад, чтобы
устранить образовавшийся “пробел”
21

22.

Методы интерфейса IList
В интерфейсе IList определяется следующий
индексатор.
object this[int index] { get; set; }
Он служит для получения и установки значения
элемента коллекции.
Но его нельзя использовать для добавления в
коллекцию нового элемента. С этой целью
обычно вызывается метод Add(). Как только
элемент будет добавлен в коллекцию, он станет
доступным посредством индексатора.
22

23.

Класс ArrayList
Класс ArrayList позволяет программисту не
заботиться о выделении памяти и хранить в
одном и том же массиве элементы различных
типов - строки, числа и т.д..
По умолчанию при создании объекта типа
ArrayList строится массив из 16 элементов
типа object.
ArrayList arr1 = new ArrayList(); // 16 элементов
ArrayList arr2 = new ArrayList(1000);
ArrayList arr3 = new ArrayList();
arr3.Capacity = 1000; // кол-во элементов задается
23

24.

Класс ArrayList
Если при добавлении элемента в массив оказывается,
что фактическое количество элементов массива
превышает его емкость, она автоматически
удваивается, то есть происходит повторное выделение
памяти и переписывание туда всех существующих
элементов.
arr1.Add( 123 ); arr1.Add( -2 ); arr1.Add( "Вася" );
Доступ к элементу выполняется по индексу, однако при
этом необходимо явным образом привести
полученную ссылку к целевому типу, например:
int a = (int) arr1[0];
int b = (int) arr1[1];
string s = (string) arr1[2];
24

25.

Пример 1
using System;
using System.Collections;
namespace Collections{
class Program{
static void Main(string[] args){
ArrayList list = new ArrayList();
list.Add(2.3); // занести в список объект типа double
list.Add(55); // занести в список объект типа int
// занести в список строковый массив
list.AddRange(new string[] { "Hello", "world" });
// перебор значений
foreach (object o in list) {
Console.WriteLine(o);
25
}

26.

Пример 1
list.RemoveAt(0); // удалить первый элемент
list.Reverse(); // перевернуть список
// получить элемент по индексу
Console.WriteLine(list[0]);
// перебор значений
for (int i = 0; i < list.Count; i++) {
Console.WriteLine(list[i]);
}
Console.ReadLine();
}
}
}
26

27.

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

28.

Обобщенные коллекции
Основные интерфейсы обобщенных коллекций:
IEnumerable<T>: определяет метод GetEnumerator, с
помощью которого можно получать элементы любой
коллекции. Реализация данного интерфейса позволяет
перебирать элементы коллекции с помощью
цикла foreach
IEnumerator<T>: определяет методы, с помощью
которых потом можно получить содержимое
коллекции по очереди
ICollection<T>: представляет ряд общих свойств и
методов для всех необобщенных коллекций
(например, методы CopyTo, Add, Remove, Contains,
свойство Count)
28

29.

Обобщенные коллекции
IList<T>: предоставляет функционал для создания
последовательных списков
IComparer<T>: определяет метод Compare для
сравнения двух однотипных объектов
IDictionary<TKey, TValue>: определяет поведение
коллекции, при котором она должна хранить объекты
в виде пар ключ-значение: для каждого объекта
определяется уникальный ключ типа, указанного в
параметре TKey, и этому ключу соответствует
определенное значение, имеющее тип, указанный в
параметре TValue
IEqualityComparer<T>: определяет методы, с
помощью которых два однотипных объекта
29
сравниваются на предмет равенства

30.

Обобщенные коллекции
Эти интерфейсы реализуются следующими классами:
List<T>: класс, представляющий последовательный
список. Реализует интерфейсы IList<T>,
ICollection<T>, IEnumerable<T>
Dictionary<TKey, TValue>: класс коллекции, хранящей
наборы пар "ключ-значение". Реализует интерфейсы
ICollection<T>, IEnumerable<T>, IDictionary<TKey,
TValue>
LinkedList<T>: класс двухсвязанного списка. Реализует
интерфейсы ICollection<T> и IEnumerable<T>
Queue<T>: класс очереди объектов, работающей по
алгоритму FIFO("первый вошел -первый вышел").
Реализует интерфейсы ICollection, IEnumerable<T>
30

31.

Обобщенные коллекции
SortedSet<T>: класс отсортированной коллекции
однотипных объектов. Реализует интерфейсы
ICollection<T>, ISet<T>, IEnumerable<T>
SortedList<TKey, TValue>: класс коллекции, хранящей
наборы пар "ключ-значение", отсортированных по
ключу. Реализует интерфейсы ICollection<T>,
IEnumerable<T>, IDictionary<TKey, TValue>
SortedDictionary<TKey, TValue>: класс коллекции,
хранящей наборы пар "ключ-значение", отсортированных по
ключу. В общем похож на класс SortedList<TKey, TValue>,
основные отличия состоят лишь в использовании памяти и в
скорости вставки и удаления
Stack<T>: класс стека однотипных объектов. Реализует
интерфейсы ICollection<T> и IEnumerable<T>
31

32.

Список List<T>
Универсальный "двойник" класса ArrayList — класс
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 в
32
списке на позицию index

33.

Список List<T>
bool Remove(T item): удаляет элемент item из списка, и
если удаление прошло успешно, то возвращает true
void RemoveAt(int index): удаление элемента по
указанному индексу index
void Sort(): сортировка списка
void СоруТо (Т [ ] array, int index): копирует элементы
коллекции в массив array, начиная в массиве с
индекса index
int Capacity: получает или устанавливает количество
элементов, которое может содержаться в коллекции
void Clear (): удаляет все элементы из коллекции
bool Contains (T item): определяет, содержится ли
элемент в коллекции
33

34.

Список List<T>
IList<T> AsReadOnly(): возвращает доступный только
для чтения интерфейс к коллекции
IEnumerator<T> GetEnumerator(): получает экземпляр
IEnumerator<T> для итерации по коллекции.
Возвращаемый интерфейс является строго
типизированным и относится к типу Т, поэтому
выполнять приведение в циклах foreach не требуется
int Count: свойство, предоставляющее информацию о
количестве элементов в коллекции
Item: свойство, обеспечивающее доступ подобный
массивам (с помощью индексатора)
34

35.

Пример 2
using System;
using System.Collections;
using System.Collections.Generic;
namespace Collections{
class Program {
static void Main(string[] args) {
ArrayList objectList = new ArrayList() { 1, 2,
"string", 'c', 2.0f }; // необобщенная коллекция
object obj = 45.8;
objectList.Add(obj);
objectList.Add("string2");
objectList.RemoveAt(0); // удаление первого эл-та
foreach (object o in objectList) {Console.WriteLine(o);}
Console.WriteLine("Общее число элементов коллекции:
{0}", objectList.Count);
35

36.

Пример 2
// обобщенная коллекция List
List<int> numbers = new List<int>() { 1, 2, 3, 45 };
// добавление элемента
numbers.Add(6);
numbers.AddRange(new int[] { 7, 8, 9 });
// вставка на первое место в списке числа 666
numbers.Insert(0, 666);
// удаление второго элемента
numbers.RemoveAt(1);
foreach (int i in numbers) {
Console.WriteLine(i);
}
36

37.

Пример 2
List<Person> people = new List<Person>(3);
people.Add(new Person() { Name = "Том" });
people.Add(new Person() { Name = "Билл" });
foreach (Person p in people) {
Console.WriteLine(p.Name);
}
Console.ReadLine();
}
}
class Person {
public string Name { get; set; }
}
}
37

38.

Двухсвязный список LinkedList<T>
Класс LinkedList<T> представляет двухсвязный
список, в котором каждый элемент хранит ссылку
одновременно на следующий и на предыдущий
элемент. Если в простом списке List<T> каждый
элемент представляет объект типа T, то в
LinkedList<T> каждый узел представляет объект
класса LinkedListNode<T>. Свойства класса:
Value: само значение узла, представленное типом T
Next: ссылка на следующий элемент типа
LinkedListNode<T> в списке. Если следующий
элемент отсутствует, то имеет значение null
Previous: ссылка на предыдущий элемент типа
LinkedListNode<T> в списке. Если предыдущий
элемент отсутствует, то имеет значение null
38

39.

Двухсвязный список LinkedList<T>
Методы класса LinkedList<T>:
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.
39

40.

Двухсвязный список LinkedList<T>
AddFirst(LinkedListNode<T> node): вставляет новый
узел в начало списка
AddFirst(T value): вставляет новый узел со значением
value в начало списка
AddLast(LinkedListNode<T> node): вставляет новый
узел в конец списка
AddLast(T value): вставляет новый узел со значением
value в конец списка
RemoveFirst(): удаляет первый узел из списка. После
этого новым первым узлом становится узел,
следующий за удаленным
RemoveLast(): удаляет последний узел из списка
40

41.

Пример 3
using System;
using System.Collections.Generic;
namespace Collections{
class Program {
static void Main(string[] args) {
LinkedList<int> numbers = new LinkedList<int>();
// вставить узел со значением 1 на последнее место
numbers.AddLast(1);
// так как в списке нет узлов, то последнее будет также и первым
// вставить узел со значением 2 на первое место
numbers.AddFirst(2);
// вставить после последнего узла новый узел со значением 3
numbers.AddAfter(numbers.Last, 3);
foreach (int i in numbers) { Console.WriteLine(i); } // 2, 1, 341

42.

Пример 3
LinkedList<Person> persons =
new LinkedList<Person>();
LinkedListNode<Person> tom =
persons.AddLast(new Person() { Name = "Tom" });
persons.AddLast(new Person() { Name = "John" });
persons.AddFirst(new Person() { Name = "Bill" });
Console.WriteLine(tom.Previous.Value.Name);
Console.WriteLine(tom.Next.Value.Name);
Console.ReadLine();
}
}
class Person { public string Name { get; set; } }
}
42

43.

Очередь Queue<T>
Класс Queue<T> представляет обычную
очередь, работающую по алгоритму FIFO
("первый вошел - первый вышел").
У класса Queue<T> можно отметить следующие
методы:
Dequeue: извлекает и возвращает первый
элемент очереди
Enqueue: добавляет элемент в конец очереди
Peek: просто возвращает первый элемент из
начала очереди без его удаления
43

44.

Пример 4
using System;
using System.Collections.Generic;
namespace Collections{
class Program{
static void Main(string[] args){
Queue<int> numbers = new Queue<int>();
numbers.Enqueue(3); // очередь 3
numbers.Enqueue(5); // очередь 3, 5
numbers.Enqueue(8); // очередь 3, 5, 8
// получить первый элемент очереди
int queueElement = numbers.Dequeue(); // очередь 5, 8
Console.WriteLine(queueElement);
44

45.

Пример 4
Queue<Person> persons = new Queue<Person>();
persons.Enqueue(new Person() { Name = "Tom" });
persons.Enqueue(new Person() { Name = "Bill" });
persons.Enqueue(new Person() { Name = "John" });
// получить первый элемент без его извлечения
Person pp = persons.Peek();
Console.WriteLine(pp.Name);
Console.WriteLine("Сейчас в очереди {0}
человек", persons.Count);
// теперь в очереди Tom, Bill, John
foreach (Person p in persons) {
Console.WriteLine(p.Name);
}
45

46.

Пример 4
// Извлечь первый элемент в очереди - Tom
Person person = persons.Dequeue();
// теперь в очереди Bill, John
Console.WriteLine(person.Name);
Console.ReadLine();
}
}
class Person {
public string Name { get; set; }
}
}
46

47.

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

48.

Пример 5
using System;
using System.Collections.Generic;
namespace Collections{
class Program {
static void Main(string[] args) {
Stack<int> numbers = new Stack<int>();
numbers.Push(3); // в стеке 3
numbers.Push(5); // в стеке 5, 3
numbers.Push(8); // в стеке 8, 5, 3
// так как вверху стека находится число 8, то оно и извлекается
int stackElement = numbers.Pop(); // в стеке 5, 3
Console.WriteLine(stackElement);
Stack<Person> persons = new Stack<Person>();
persons.Push(new Person() { Name = "Tom" }); 48

49.

Пример 5
persons.Push(new Person() { Name = "Bill" });
persons.Push(new Person() { Name = "John" });
foreach (Person p in persons) {
Console.WriteLine(p.Name);
}
// Первый элемент в стеке
Person person = persons.Pop(); // в стеке Bill, Tom
Console.WriteLine(person.Name);
Console.ReadLine();
}
}
class Person { public string Name { get; set; } }
}
49

50.

Пример 5
50

51.

Коллекция Dictionary<T, V>
Еще один распространенный тип коллекции
представляют словари. Словарь хранит объекты,
которые представляют пару ключ-значение. Каждый
такой объект является объектом структуры
KeyValuePair<TKey, TValue>. Благодаря
свойствам Key и Value, которые есть у данной
структуры, можно получить ключ и значение
элемента в словаре.
Класс словарей также, как и другие коллекции,
предоставляет методы Add и Remove для добавления
и удаления элементов. Только в случае словарей в
метод Add передаются два параметра: ключ и
значение. А метод Remove удаляет не по индексу, а
51
по ключу.

52.

Пример 6
Dictionary<int, string> countries
= new Dictionary<int, string>(5);
countries.Add(1, "Russia");
countries.Add(3, "Great Britain");
countries.Add(2, "USA");
countries.Add(4, "France");
countries.Add(5, "China");
foreach (KeyValuePair<int, string> keyValue in countries){
Console.WriteLine(keyValue.Key + " - " +
keyValue.Value);
}
string country = countries[4]; // получение элемента по ключу
countries[4] = "Spain"; // изменение объекта
52
countries.Remove(2); // удаление по ключу

53.

Пример 7
Dictionary<char, Person> people = new Dictionary<char, Person>();
people.Add('b', new Person() { Name = "Bill" });
people.Add('t', new Person() { Name = "Tom" });
people.Add('j', new Person() { Name = "John" });
foreach (KeyValuePair<char, Person> keyValue in people){
// keyValue.Value представляет класс Person
Console.WriteLine(keyValue.Key + " - " + keyValue.Value.Name);
}
// перебор ключей
foreach (char c in people.Keys){ Console.WriteLine(c); }
// перебор по значениям
foreach (Person p in people.Values) {
Console.WriteLine(p.Name);
}
...
class Person { public string Name { get; set; } }
53

54.

Коллекция Dictionary<T, V>
Для добавления необязательно применять метод Add(),
можно использовать сокращенный вариант:
Dictionary<char, Person> people = new Dictionary<char,
Person>();
people.Add('b', new Person() { Name = "Bill" });
people['a'] = new Person() { Name = "Alice" };
Несмотря на то, что изначально в словаре нет ключа 'a'
и соответствующего ему элемента, то он все равно
будет установлен. Если же он есть, то элемент по
ключу 'a' будет заменен на новый объект new Person()
{ Name = "Alice" }
54

55.

Коллекция Dictionary<T, V>
В C# существует два способа инициализации словарей:
Dictionary<string, string> countries = new Dictionary<string,
string>{
{"Франция", "Париж"},
{"Германия", "Берлин"},
{"Великобритания", "Лондон"}
};
foreach(var pair in countries)
Console.WriteLine("{0} - {1}", pair.Key, pair.Value);
Dictionary<string, string> countries = new Dictionary<string,
string>{
["Франция"]= "Париж",
["Германия"]= "Берлин",
["Великобритания"]= "Лондон"
};
55

56.

Сортировка и поиск в обобщенных списках
Для сортировки списка необходим метод,
сравнивающий два объекта типа Т, а для выполнения
поиска — метод, проверяющий объект типа Т на
предмет того, отвечает ли он конкретным критериям.
Сортировка обобщенного списка реализуется с
применением обобщенных интерфейсов
IComparer<T> и IComparable<T>.
int IComparable<T>.CompareTo(Т otherObj)
bool IComparable<T>.Equals(T otherObj)
int IComparer<T>.Compare(T objectA, T objectB)
bool IComparer<T>.Equals (T objectA, T objectB)
int IComparer<T>.GetHashCode(T objectA)
56

57.

Класс ObservableCollection
Кроме стандартных классов коллекций типа
списков, очередей, словарей, стеков .NET также
предоставляет специальный класс
ObservableCollection. Он по функциональности
похож на список List за тем исключением, что
позволяет известить внешние объекты о том, что
коллекция была изменена.
Класс ObservableCollection находится в
пространстве имен
System.Collections.ObjectModel.
Класс ObservableCollection определяет событие
CollectionChanged, подписавшись на которое,
можно обработать любые изменения коллекции.
57

58.

Пример 8
using System;
using System.Collections.ObjectModel;
using System.Collections.Specialized;
namespace HelloApp{
class Program {
static void Main(string[] args) {
ObservableCollection<User> users =
new ObservableCollection<User>{
new User { Name = "Bill"},
new User { Name = "Tom"},
new User { Name = "Alice"}
};
58

59.

Пример 8
users.CollectionChanged +=
Users_CollectionChanged;
users.Add(new User { Name = "Bob" });
users.RemoveAt(1);
users[0] = new User{ Name = "Anders" };
foreach(User user in users) {
Console.WriteLine(user.Name);
}
Console.Read();
}
59

60.

Пример 8
private static void Users_CollectionChanged(object
sender, NotifyCollectionChangedEventArgs e) {
switch(e.Action) {
case NotifyCollectionChangedAction.Add:
User newUser = e.NewItems[0] as User;
Console.WriteLine("Добавлен новый объект:
{0}", newUser.Name);
break;
case NotifyCollectionChangedAction.Remove:
User oldUser = e.OldItems[0] as User;
Console.WriteLine("Удален объект: {0}",
oldUser.Name);
break;
60

61.

Пример 8
case NotifyCollectionChangedAction.Replace:
User replacedUser = e.OldItems[0] as User;
User replacingUser = e.NewItems[0] as User;
Console.WriteLine("Объект {0} заменен
объектом {1}", replacedUser.Name, replacingUser.Name);
break;
}
}
}
class User{
public string Name { get; set; }
}
}
61

62.

Пример 9
class Book{ // Класс Book представляет книгу
public Book(string name) { this.Name=name; }
public string Name { get; set; }
}
// Класс Library представляет библиотеку и
// используется для хранения набора книг
class Library{
Book[] books;
public Library(){
books = new Book[] { new Book("Отцы и дети"),
new Book("Война и мир"),
new Book("Евгений Онегин")
};
62
}

63.

Пример 9
public int Length{ get { return books.Length; } }
public Book this[int index] {
get { return books[index]; }
set { books[index] = value; }
}
}
class Program{
static void Main(string[] args) {
Library library = new Library();
Console.WriteLine(library[0].Name);
library[0] = new Book("Преступление и наказание");
Console.WriteLine(library[0].Name);
}
}
63

64.

Пример 10
class Matrix{
private int[,] numbers = new int[,] { { 1, 2, 4}, { 2, 3, 6 },
{ 3, 4, 8 } };
public int this[int i, int j] {
get { return numbers[i, j]; }
set { numbers[i, j] = value; }
}
}
…
Matrix matrix = new Matrix();
Console.WriteLine(matrix[0, 0]);
matrix[0, 0] = 111;
Console.WriteLine(matrix[0, 0]);
64

65.

Интерфейсы IEnumerable и IEnumerator
Интерфейс IEnumerable имеет метод, возвращающий
ссылку на другой интерфейс - перечислитель:
public interface IEnumerable{
IEnumerator GetEnumerator();
}
А интерфейс IEnumerator определяет функционал для
перебора внутренних объектов в контейнере:
public interface IEnumerator{
bool MoveNext(); // перемещение на одну позицию
// вперед в контейнере элементов
object Current {get;} // текущий элемент в контейнере
void Reset(); // перемещение в начало контейнера
}
65

66.

Пример 11
class Book{
public Book(string name) { this.Name=name; }
public string Name { get; set; }
}
class Library : IEnumerable{
private Book[] books;
public Library(){
books = new Book[] { new Book("Отцы и дети"),
new Book("Война и мир"),
new Book("Евгений Онегин") };
}
public int Length{
get { return books.Length; }
66
}

67.

Пример 11
public Book this[int index] {
get { return books[index]; }
set { books[index] = value; }
}
IEnumerator IEnumerable.GetEnumerator(){
return books.GetEnumerator(); // Вернуть перечислитель
}
}
class Program{
static void Main(string[] args){
Library library = new Library();
foreach (Book b in library) { Console.WriteLine(b.Name); }
}
}
67

68.

Пример 11
class Library{ // без реализации интерфейса IEnumerable
private Book[] books;
public Library() {
books = new Book[] { new Book("Отцы и дети"), new
Book("Война и мир"), new Book("Евгений Онегин") };
}
public int Length { get { return books.Length; } }
public Book this[int index]{
get { return books[index]; }
set { books[index] = value; }
}
public IEnumerator GetEnumerator(){
return books.GetEnumerator();
}
}
68

69.

Итераторы и оператор yield
Можно не полагаться на реализацию
перечислителя в массиве, а создать итератор с
помощью ключевого слова yield.
Итератор представляет метод, в котором
используется ключевое слово yield для
перебора по коллекции или массиву.
Для создания итератора можно использовать
метод, но оператор yield можно использовать
и внутри любого метода, только такой метод
должен возвращать объект интерфейса
IEnumerable. Подобные методы называют
именованными итераторами.
69

70.

Пример 12
class Book{
public Book(string name) { this.Name=name; }
public string Name { get; set; }
}
class Library : IEnumerable{
private Book[] books;
public Library(){
books = new Book[] { new Book("Отцы и дети"),
new Book("Война и мир"),
new Book("Евгений Онегин") };
}
public int Length{
get { return books.Length; }
70
}

71.

Пример 12
public Book this[int index] {
get { return books[index]; }
set { books[index] = value; }
}
IEnumerator IEnumerable.GetEnumerator(){ // изменен
for (int i = 0; i < books.Length; i++) {
yield return books[i];
}
}
}
class Program{
static void Main(string[] args){
Library library = new Library();
foreach (Book b in library) { Console.WriteLine(b.Name); }
}
}
71

72.

Пример 13
class Book{
public Book(string name) { this.Name=name; }
public string Name { get; set; }
}
class Library{
private Book[] books;
public Library() {
books = new Book[] { new Book("Отцы и дети"),
new Book("Война и мир"),
new Book("Евгений Онегин") };
}
public int Length { get { return books.Length; } }
public Book this[int index] {
get { return books[index]; } set { books[index] = value; }
}
72

73.

Пример 13
public IEnumerable GetBooks(int max) {
for (int i = 0; i < max; i++) {
if (i == books.Length) { yield break; }
else { yield return books[i]; }
}
}
}
class Program{
static void Main(string[] args){
Library library = new Library();
foreach (Book b in library.GetBooks(5)){
Console.WriteLine(b.Name);}
}
}
73

74.

Обобщенный делегат Action
Делегат Action является обобщенным, принимает
параметры и возвращает значение void:
public delegate void Action<T>(T obj)
Данный делегат имеет ряд перегруженных версий.
Каждая версия принимает разное число параметров:
от Action<in T1> до Action<in T1, in T2, ..., in T16>.
Таким образом можно передать до 16 значений в
метод.
Как правило, этот делегат передается в качестве
параметра метода и предусматривает вызов
определенных действий в ответ на произошедшие
действия.
74

75.

Пример 14
static void Main(string[] args) {
Action<int, int> op;
op = Add;
Operation(10, 6, op);
op = Substract;
Operation(10, 6, op);
}
static void Operation(int x1, int x2, Action<int, int> op){
if (x1 > x2) op(x1, x2);
}
static void Add(int x1, int x2){
Console.WriteLine("Сумма чисел: " + (x1 + x2));
}
static void Substract(int x1, int x2){
Console.WriteLine("Разность чисел: " + (x1 - x2));
}
75

76.

Обобщенный делегат Predicate
Делегат Predicate<T>, как правило, используется для
сравнения, сопоставления некоторого объекта T
определенному условию. В качестве выходного
результата возвращается значение true, если условие
соблюдено, и false, если не соблюдено:
Predicate<int> isPositive = delegate (int x) {
return x > 0;
};
Console.WriteLine(isPositive(20));
Console.WriteLine(isPositive(-20));
В данном случае возвращается true или false в
зависимости от того, больше нуля число или нет.
76

77.

Обобщенный делегат Func
Еще одним распространенным делегатом
является Func. Он возвращает результат действия и
может принимать параметры. Он также имеет
различные формы: от Func<out T>(), где T - тип
возвращаемого значения, до Func<in T1, in T2, ..., in
T16, out TResult>(), то есть может принимать до 16
параметров.
TResult Func<out TResult>()
TResult Func<in T, out TResult>(T arg)
TResult Func<in T1, in T2, out TResult>(T1 arg1, T2 arg2)
TResult Func<in T1, in T2, in T3, out TResult>(T1 arg1,
T2 arg2, T3 arg3)
TResult Func<in T1, in T2, in T3, in T4, out TResult>(T1
arg1, T2 arg2, T3 arg3, T4 arg4)
77

78.

Пример 15
static void Main(string[] args) {
Func<int, int> retFunc = Factorial;
int n1 = GetInt(6, retFunc);
Console.WriteLine(n1); // 720
int n2 = GetInt(6, x=> x *x);
Console.WriteLine(n2); // 36
}
static int GetInt(int x1, Func<int, int> retF){
int result = 0;
if (x1 > 0) result = retF(x1);
return result;
}
static int Factorial(int x){
int result = 1;
for (int i = 1; i <= x; i++) { result *= i; }
return result;
}
78

79.

Контрольные вопросы
1. Как используется конструкция yield?
2. Допускает ли структура "линейный список"
прямой доступ к своим элементам?
3. В каких задачах используется стек?
Приведите примеры.
4. В чем преимущество массива перед другими
структурами данных?
5. Каков состав пространства имен
System.Collections и какова краткая
характеристику основных типов-коллекций?
79