Высокоуровневые методы информатики и программирования Лекция 15 Коллекции. - презентация

1 Высокоуровневые методы информатики и программирования Лекция 15 Коллекции

2 Коллекции Коллекции – классы, объекты которых могут хранить ссылки на объекты других классов (контейнеры) Коллекция Куча

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

4 Интерфейсы классов коллекций IEnumerable - Составляет список объектов классов коллекций с помощью оператора foreach IComparer - Сравнивает два объекта классов коллекций при их сортировке; ICollection - Реализуется всеми классами коллекций для обеспечения доступа к методу СоруТо(), GetEnumerator() и свойство Count; IList - Используется объектами классов коллекций, индексируемыми как массив. IDictionary - Используется классами коллекций, осуществляющими доступ по ключу или значению, таких как Hashtable и SortedList. IDictionaryEnumerator - Позволяет просмотреть (с помощью оператора foreach) объекты классов коллекций, поддерживающих интерфейс IDictionary

5 Интерфейс IEnumerable interface IEnumerable { IEnumerator GetEnumerator(); } interface IEnumerator { public bool MoveNext(); // i++ public void Reset(); // i=0; public оbject Current {get;}); //property }

6 Коллекции System.Array - массивы – простейший тип коллекций –фиксированный размер –однотипные объекты System.Collections. –ArrayList – неограниченный список элементов. –Queue – порядок элементов FIFO –Stack – порядок элементов LIFO –Hashtable – словарь (ключ - значение), оптимизирован для быстрого поиска значний.

7 Коллекции в.NET System.Collections –Нетипизированные коллекции –Специализированные коллекции System.Collections.Generic –Шаблонные коллекции

8 Основные элементы интерфейса ICollection ЭлементОписание Count свойство – количество объектов в коллекции CopyTo() метод копирования элементов коллекции в массив типа Array, начинас с заданного индекса массива GetEnumerator() получение объекта, поддерживающего интерфейс IEnumerable ), который позволяет просматривать всю коллекцию (для foreach )

9 Основные элементы интерфейса IList ЭлементОписание Add() метод добавления объекта к коллекции Clear() удаление всех объектов из коллекции Contains() проверка на наличие в коллекции объекта (true/false) IndexOf() определение индекса для заданного объекта Insert() вставка объекта в место заданное индексом Remove() удаление первого встреченного экземпляра указанного объекта RemoveAt() удаление всех объектов, начиная с заданного индекса [index] индексатор, который позволяет получить или задать объекты по заданному индексу.

10 Основные элементы интерфейса IDictionary Описывает не обобщенную коллекцию пар (ключ, значение) Основные методы: –Add() – добавляет элемент с заданным ключем и значением; –Clear() – удаляет все элементы из словаря; –Contains () – проверяетсодержит ли словарь заданный элемент; –CopyTo() – копирует элементы ICollection в массив начиная с заданного индекса массива (наследуется от ICollection); –GetEnumerator() – перегруженный метод для получения объекта Enumerator. –Remove () – удаление всех элементов с заданным ключем из объекта IDictionary.

11 Типы нетипизированных коллекций ArrayList – простая коллекция (наследуется от интерфейса IList), которая может хранить объекты любого типа. Экземпляры ArrayList могут хранить произвольное количество объектов, при необходимости, они увеличивают объем используемой памяти. Queue ­– коллекция, которая поддерживает следующий порядок работы с объектами: «первым пришел, первым вышел» (first-in, first-out – FIFO). Можно использовать Queue на сервере обработки сообщений, для временного хранения сообщений перед обработкой, или для хранения информации о клиентах, которые должны обрабатываться в порядке «Первым – пришел, первым – ушел». Stack – коллекция, которая поддерживает следующий порядок работы с объектами: «Последним пришел – первым ушел» (last- in, first-out – LIFO). Можно использовать Stack для хранения наиболее новых изменений, чтобы можно было их отменить.

12 Класс ArrayList Реализует интерфейсы IList, ICollection, IEnumerable, ICloneable, используя массив, размер которого динамически меняется по необходимости. ArrayList arl = new ArrayList( ); Свойства –Сount – количество элементов –Capacity – текущий объем списка –Item – получение элемента по индексу (indexer [ i ] – операция) Методы –Add( ) – добавить объект –Clear( ) – очистить –Sort( ) – сортировать –…

13 Пример работы ArrayList al = new ArrayList(); al.Add("Привет"); al.Add("Мир"); al.Add(5); al.Add(new FileStream("delemete", FileMode.Create)); Console.WriteLine("Коллекция содержит " + al.Count + " элемента:"); foreach (object s in al) Console.Write(s.ToString() + " "); Результат Коллекция содержит 4 элемента: Привет Мир 5 System.IO.FileStream

14 ArrayList al = new ArrayList(); ArrayList al = new ArrayList() {"Привет", "Мир", "это", "проверка"}; al.Remove("это"); al.Insert(1, "Наш"); al.Sort(); foreach (object s in al) Console.Write(s.ToString() + " "); Результатом работы будет следующая строка: Мир Наш Привет проверка

15 Метод преобразования коллекции к типу OfType () В не типизированных коллекциях могут храниться данные любого типа. Для применения LINQ нужно выбрать из них только те, которые имеют определенный тип (преобразовать в типизированную коллекцию) Метод OfType () выбирает из нетипизированной коллекции только объекты заданного типа и преобразует их к типу IEnumerable. Например: // Extract the ints from the ArrayList. ArrayList myStuff = new ArrayList(); myStuff.AddRange(new object[] { 10, 400, 8, false, new Car(), "string data" }); IEnumerable myInts = myStuff.OfType (); // Prints out 10, 400, and 8. foreach (int i in myInts) { Console.WriteLine("Int value: {0}", i); }

16 Класс очередей (Queue) Очередь (queue) - это класс коллекций, организованный по принципу FIFO (первым вошел - первым вышел). Классическая аналогия - очередь в кассу за билетами. Первый человек, стоящий в очереди, первый и выйдет из нее, когда купит билет. Очередь удачно подходит для управления ограниченными ресурсами.

17 Свойства и методы очереди Свойство –Count - Открытое свойство, позволяющее узнать текущее количество элементов очереди Методы –Enqueue() - Добавляет объект в конец объекта Queue –Dequeue() - Возвращает объект, стоящий в начале объекта Queue, и удаляет его из очереди –Peek() - Возвращает объект, стоящий в начале объекта Queue, не удаляя его –Contains () - Выясняет, находится ли данный элемент в объекте Queue –Clear() - Удаляет все элементы из объекта Queue

18 Queue q = new Queue(); q.Enqueue("Привет"); q.Enqueue("мир"); q.Enqueue("просто тестирование"); Console.WriteLine("Использование Queue:"); for (int i = 1; i

19 Класс Stack (Стек) это класс коллекции, организованный по принципу LIFO (последним вошел- первым вышел). Аналогией может служить стопка подносов в столовой самообслуживания (или, например, столбик из монет). Поднос, положенный в стопку последним, будет взят оттуда первым. Основными методами для работы со стеком являются Push ( ) (добавление элемента) и Рор() (удаление). Кроме того, класс Stack предоставляет метод Peek(), аналогичный одноименному методу класса Queue.

20 Свойства и методы стека Свойство –int Count – количество элементов стека Методы –void Push() – Помещает объект на вершину объекта Stack –object Pop() - Возвращает объект, находящийся на вершине объекта Stack, и удаляет его из стека –object Peek() – Возвращает объект, находящийся на вершине объекта Stack, не удаляя его –void Clear() – убрать все объекты –bool Contains(a) – проверка есть элемент

21 Пример работы со стеком Stack s = new Stack(); s.Push("Привет"); s.Push("мир"); s.Push("просто тестирование"); Console.WriteLine("\nИспользование Stack:"); for (int i = 0; i < 3; i++) Console.WriteLine (s.Pop().ToString()); Результат: Stack demonstration: просто тестирование мир Привет

22 Словари Классы словарей (dictionaries) задают соответствие между ключами (key) и значениями (value). Например, можно связать идентификатор сотрудника (например, табельный номер) с объектом класса, описывающего сотрудника номер. Значение словаря можно найти по значению ключа: –значение = словарь [ключ]; Словарь Ключ Ссылка Куча

23 Типы нетипизированных словарей Классы словарей (dictionaries) задают соответствие между ключами (key) и значениями (value). Например, можно связать идентификатор сотрудника (например, табельный номер) с объектом класса, описывающего сотрудника номер. В FCL включены следующие основные классы словарей: Hashtable – словарь (хешированная таблица) пар (имя, значение), которые могут быть получены по имени или индексу; SortedList – словарь, который автоматически сортируется по ключу; StringDictionary – словарь Hashtable в котором пары имя/значение могут быть только строками string.

24 Отсортированный список SortedList Поддерживает интерфейсы IDictionary, ICollection, IEnumerable, ICloneable Представляет собой коллекцию пар (ключ, значение), которые сортируются по ключу и доступны –по ключу [ключ] и –индексу [i].

25 SortedList sl = new SortedList(); sl.Add("Stack", "Коллекция объектов типа LIFO."); sl.Add("Queue", "Коллекция объектов типа FIFO."); sl.Add("SortedList", "Коллекция пар ключ/значение."); foreach (DictionaryEntry de in sl) Console.WriteLine(de.Value); string s = (string)sl["Queue"]; // s = "Коллекция объектов типа FIFO.«

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

27 Хеш-код (продолжение) Стандартная реализация метода GetHashCode() для строки сводится к тому, что Unicode-коды всех символов строки складываются, а затем с помощью деления по модулю получается значение от 0 до N, где N - количество блоков в хеш-таблице. Писать такой метод для типа string не надо, так как среда CLR предоставляет его по умолчанию. Когда в объект Hashtable вставляются значения, он вызывает метод GetHashCode() для каждого указанного ключа. Метод возвращает целочисленное значение, идентифицирующее блок, в который помещено значение. Не исключена ситуация, когда для нескольких ключей будет возвращен один номер блока. Это называется конфликтом (collision). Существует ряд способов разрешения конфликтов. Самым распространенным подходом, к тому же принятым в CLR, является ведение упорядоченного списка значений в каждом блоке.

28 Свойства и методы Hashtable Свойства –Count – текущее число элементов –[ ] – индексатор Методы –Clear() - Удаляет все элементы из объекта Hashtable –Add(object k, object v) - Добавляет запись с указанной парой ключ/значение –Remove() - Удаляет запись с указанным ключом –ContainsKey () - проверить наличие заданного ключа. –ContainsValue () - проверить наличие заданного значения.

29 Универсальные классы (Generic classes)

30 Обобщения (generics) Под обобщением (универсальностью, generality) понимается способность типа объявлять используемые им другие типы как параметры. Класс с параметрами, задающими типы, называется обобщенным или универсальным классом (generic class). Обобщенными могут быть: –классы –методы –делегаты –интерфейсы

31 Обобщенные классы (Generic Classes) class MyClass {...} Пример обобщенного класса: public class Point { //координаты точки, тип которых задан параметром T x, y; // другие свойства и методы структуры... } При описании переменной данного типа нужно задать конкретный используемый тип. Например: Point pt; pt = new Point ();

32 Пример обобщенного метода: class Change { static public void Swap (ref T x1, ref T x2) { T temp; temp = x1; x1 = x2; x2 = temp; }

33 Использование обобщенного метода public void TestSwap() { int x1 = 5, x2 = 7; Change.Swap (ref x1, ref x2); erson pers1 = new Person("Савлов", 25, 1500); Person pers2 = new Person("Павлов", 35, 2100); Change.Swap (ref pers1, ref pers2); }

34 Стандартные обобщенные делегаты В библиотеке FCL описаны стандартные обобщенные делегаты, которые активно используются в методах классов библиотеки: System.Action() – принимает значение (или значения) и ничего не возвращает; public delegate void Action ( T obj ) System.Comparison() – принимает два параметра и возвращает целое значение ( 0: x > y) public delegate int Comparison ( T x, T y ) System.Converter() – преобразование объекта из одного типа в другой public delegate TOutput Converter ( TInput input ) System.EventHandler – обработчик событий public delegate void EventHandler ( Object sender, TEventArgs e ) where TEventArgs : EventArgs System.Func() – принимает значение (или значения) и возвращает результат public delegate TResult Func ( T arg ) System.Predicate() – принимает значение и возвращает bool public delegate bool Predicate ( T obj )

35 Стандартные обобщенные интерфейсы ICollection IComparer IDictionary IEnumerable IEnumerator IList

36 Стандартные пространства имен System – содержит основные базовые классы; System.Collections – содержит интерфейсы и классы, которые описывают разные типы коллекций и словарей (не обобщенные). System.Collections.Generic содержит интерфейсы и классы, которые описывают обобщенные коллекции и словари, которые позволяют пользователям создавать строго типизированные коллекции, предоставляющие лучшую безопасность работы с типами и лучшую производительность, чем не обобщенные коллекции; System.Linq содержит классы и интерфейсы, которые поддерживают интегрированный в язык C# язык запросов - Language-Integrated Query (LINQ). System.Text содержит классы представляющие методы кодировки символов ASCII, Unicode, UTF-7 и UTF-8; абстрактные базовые классы для конвертирования наборов символов в набор байтов; и вспомогательный класс для манипулирования и форматирования String объектов без создания промежуточных экземпляров типа String.

37 Обобщенные коллекции из System.Collections.Generic List - список элементов переменного размера; Queue – порядок элементов FIFO; Stack – порядок элементов LIFO; LinkedList - двухсвязный список; Dictionary (dictionary – коллекция, которая ассоциирует ключ (key) со значением (value))

38 Соответствие между обобщенными классами и их обычными двойниками Универсальный классОбычный класс List ArrayList Queue Stack SortedDictionary SortedList Dictionary HashTable LinkedList нет

39 Пример использования Stack sp; sp = new Stack (); sp.Push(p); Point[ ] pa; pa = sp.ToArray();

40 public class Person : IComparable { string firstName, lastName; public int CompareTo(object obj) { Person otherPerson = (Person)obj; if (this.lastName != otherPerson.lastName) return this.lastName.CompareTo(otherPerson.lastName); else return this.firstName.CompareTo (otherPerson.firstName); } public Person(string _firstName, string _lastName){ firstName = _firstName; lastName = _lastName; } override public string ToString() { return firstName + " " + lastName; }

41 List group = new List (); group.Add(new Person("Григорий", "Дубина")); group.Add(new Person("Иван", "Ходырев")); group.Add(new Person("Александр", "Луценко")); group.Sort(); foreach (Person p in group) Console.Write(p.ToString() + ";");

42 SortedList sl = new SortedList (); sl.Add("One", 1); sl.Add("Two", 2); sl.Add("Three", 3); foreach (int i in sl.Values) Console.Write(i.ToString() + " "); int n = sl[Two]; // значение 2 Результат выполнения примера: 1 3 2

43 Словарь Dictionary Словарь (dictionary) - это класс коллекции, связывающий ключ со значением. По такому же принципу построены толковые словари, например словарь Вебстера связывает слово (ключ) с его толкованием (значение).

44 Свойства и методы IDictionary Свойство –Item – получить или записать элемент –Keys – получить ICollection всех ключей –Values - получить ICollection всех значений Методы –Add() – добавить ключ и значение к словарю; –Clear() – удалить все ключи и значения из словаря; –Remove () – удалить значение с указанным ключем; –bool ContainsKey(key) – определить есть ли в словаре указанный ключ; –bool ContainsValue(value) - определить есть ли в словаре указанное значение; –bool TryGetValue(key, out value) - получить значение связанное с заданным ключом.

45 Пример class Program { static void Main(string[] args) { int[ ] list = { 20, 1, 4, 8, 9, 44 }; int[ ] evenNumbers; // Call FindAll() using traditional delegate syntax. Predicate callback = new Predicate (IsEvenNumber); evenNumbers = Array.FindAll(list, callback); // анонимный делегат evenNumbers = Array.FindAll(list, delegate(int i) { return (i % 2) == 0; }); // Now, use a C# 2008 lambda expression. evenNumbers = Array.FindAll(list, i => (i % 2) == 0); Console.WriteLine("Here are your even numbers:"); foreach (int evenNumber in evenNumbers) { Console.Write("{0}\t", evenNumber); } Console.WriteLine(); } // Target for the Predicate delegate. static bool IsEvenNumber(int i) { // Is it an even number? return (i % 2) == 0; }