Коллекции Итераторы Лекция 6

Коллекции Итераторы

Коллекции Итераторы

Коллекция Класс ( объект ), основное назначение которого – содержать в себе другие объекты по определенной дисциплине Примеры коллекций Массив, динамический массив Список, стек, очередь Дерево, множество, словарь ( хэш - таблица )

Основные пространства имен : System.Collections System.Collections Нетипизированные коллекции Специализированные коллекции ArrayList, Hashtable и др. System.Collections.Specialized System.Collections.Specialized Специализированные коллекции System.Collections.Generic System.Collections.Generic Обобщенные коллекции Список, очередь, словарь, стек System.Collections.ObjectModel System.Collections.ObjectModel Базовые реализации для собственных коллекция Специальные обобщенные коллекции System.Collections.Concurrent System.Collections.Concurrent Коллекции, позволяющие обращения из нескольких потоков до.NET 2 с.NET 2 с.NET 4

Не типизированные коллекции : Не типизированные коллекции : ArrayList ArrayList – Массив object переменной длинны HashTable HashTable – Таблица пар ключ / значение, основанная на хранении хэш - кода ключа BitArray BitArray - Компактный массив битовых значений Stack Stack – Стек object Queue Queue – Очередь object SortedList, SortedList,- Сортированный по ключам словарь Практически не используются, поскольку есть обобщенные версии ( появились в.NET 2) Практически не используются, поскольку есть обобщенные версии ( появились в.NET 2)

Старые специализированные коллекции : Старые специализированные коллекции : ListDictionary ListDictionary – не типизированный словарь пар ключ / значение, ориентированный на хранение до 10 значений HybridDictionary HybridDictionary– не типизированный словарь пар ключ / значение, который до 10 значений хранит данные как ListDictionary, а более – преобразуется в HashTable OrderedDictionary OrderedDictionary- словарь, позволяющий индексировать значения по номеру StringCollection StringCollection– представляет собой коллекцию строк StringDictionary StringDictionary– словарь, где и ключ и значение - string BitVector32 BitVector32– структура для компактного хранения 32 bool значений. Практически не используются, поскольку есть обобщенные версии ( появились в.NET 2) Практически не используются, поскольку есть обобщенные версии ( появились в.NET 2)

Обобщенный коллекции : Обобщенный коллекции : List List - Список Переменной длинны LinkedList LinkedList - Двунаправленный связанный список переменной длинны Stack Stack - Стек Queue Queue - Очередь Dictionary Dictionary - Словарь SortedList SortedDictionary SortedList и SortedDictionary - Сортированный по ключам словарь HashSet HashSet - Множество SortedSet SortedSet - Сортированное множество

Содержит базовые классы для создания своих коллекций Collection Collection KeyedCollection KeyedCollection ObservableCollection Тип ObservableCollection - динамическая обобщенная коллекция, которая генерирует события при изменении коллекции ( добавлении, удалении элемента или при обновлении всего списка ) Важное применение - WPF Коллекции обертки только для чтения ReadOnlyCollection ReadOnlyCollection ReadOnlyDictionary ReadOnlyDictionary ReadOnlyObservableCollection ReadOnlyObservableCollection

Потокобезопасные коллекции. Позволяют получать доступ к коллекции из нескольких потоков. Содержат встроенные, облегченные механизмы синхронизации потоков ConcurrentQueue ConcurrentQueue - потокобезопасная очередь ConcurrentStack ConcurrentStack - потокобезопасный стек ConcurrentDictionary ConcurrentDictionary - потокобезопасный словарь ConcurrentBag ConcurrentBag - потокобезопасный не упорядоченный список

Обобщенные vs. Необобщенные Обобщенные коллекции – контроль типов во время компиляции, необобщенные – контроля типов нет или во осуществляется во время выполнения В обобщенных коллекциях не нужно использовать boxing/unboxing при использовании типов - значений Обобщенные коллекции обладают более высокой производительностью Не обобщенные коллекции используются редко ( исключение – унаследованный код )

Список Динамически изменяет размер Обладает возможностью доступа по индексу Позволяет осуществлять поиск и сортировку Создание List list1 = new List (); List list2 = new List (10); List strList = new List () { один, два }; List complexList = new List () { new Complex() {Re =5, Im =7}, new Complex() {Re =3, Im =1}, }; Добавление Add(T item), AddRange( IEnumerable collection) Элемента ( ов ) ( в конец ) –Add(T item), AddRange( IEnumerable collection) list1.Add(5); list2.AddRange(list1); Insert(int index, T item), InsertRange(int index, IEnumerable collection) элемента ( ов ) в произвольное место Insert(int index, T item), InsertRange(int index, IEnumerable collection) Удаление Remove(T item) элемента Remove(T item) complexList.Remove(complex2); RemoveAt(int index), RemoveRange(int index, int count) Элемента ( ов ) по индексу RemoveAt(int index), RemoveRange(int index, int count) Clear() Всех элементов Clear()

[int index] Доступ к элементу по индексу [int index] int j = l[3]; Count Количество элементов - свойство Count int k = l.Count; Sort() Сортировка элементов Sort() list1.Sort(); T[] ToArray() Преобразование в массив T[] ToArray() int[] arr = list1.ToArray(); Поиск bool Contains(T item) bool Contains(T item) – проверка – содержится ли элемент в списке bool Exists(Predicate match) bool Exists(Predicate match) – проверка – содержится ли элемент удовлетворяющий условию T Find( Predicate match) T Find( Predicate match)– Поиск первого элемента, удовлетворяющего условию int IndexOf( T item ) int IndexOf( T item ) – возвращает индекс элемента

Работа со списком Сортировка комплексных чисел ReadOnlyCollection

Обобщенный стек Last In First Out (LIFO). Последним вошёл, первым вышел Динамически изменяет размер Создание Stack s = new Stack (); Push() Добавление элемента Push() s.Push(3); T Pop(). Clear() Удаление элемента T Pop(). Очистка всего стека Clear() int k = s.Pop(); T Peek() Просмотр элемента в вершине стека T Peek() int k = s. Peek(); Count Количество элементов - свойство Count if (s.Count == 0) … bool Contains(T item) bool Contains(T item) – проверка, содержится ли данный элемент в стеке T[] ToArray() Преобразование в массив T[] ToArray() int[] k = s. ToArray();

Обобщенная очередь first-in, first-out (FIFO). Первым вошел, первым вышел динамически изменяет размер Создание Queue q = new Queue (); Enqueue(T item ) Добавление элемента Enqueue(T item ) q.Enqueue(new Complex(4,5)); T Dequeue(). Clear() Удаление элемента T Dequeue(). Очистка всей очереди Clear() int k = s. Dequeue(); T Peek() Просмотр элемента в начале очереди T Peek() int k = s. Peek(); Count Количество элементов - свойство Count if (s.Count == 0) … bool Contains(T item) bool Contains(T item) – проверка, содержится ли данный элемент в очереди T[] ToArray() Преобразование в массив T[] ToArray() int[] k = s. ToArray();

Словарь Содержит коллекцию ключей и соответствующих им значений Динамически изменяет свой размер Создание Dictionary d = new Dictionary (); Add(TKey key, TValue value) Добавление Add(TKey key, TValue value) d.Add( два, new Complx(4,5)); s.Add( один, one); Remove(TKey key)Clear() Удаление Remove(TKey key), всех записей Clear() d.Remove(myComplexVar); [Tkey key] Доступ по ключу [Tkey key] Complex complexVar = d[ два ]; bool TryGetValue( TKey key, out TValue value) Безопасное получение значения по ключу bool TryGetValue( TKey key, out TValue value) if (d.TryGetValue( два, out myComplexVar)) … Проверка, содержится ли в словаре bool ContainsKey(TKey key) Ключ - bool ContainsKey(TKey key) bool ContainsValue( TValue value Значение - bool ContainsValue( TValue value Count Количество элементов в словаре – свойство Count Коллекции ( свойства ) Keys Keys – коллекция ключей Values Values – коллекция значений

HashSet HashSet - Множество SortedSet SortedSet - Сортированное множество Не позволяют дублировать значения Имеют операции на объединение, вычитание, пересечение множеств Add(T item) – Add(T item) – добавление элемента в множество bool Remove(T item) RemoveWhere(Predicate match) bool Remove(T item) – удаление элемента из множества. RemoveWhere(Predicate match) – по условию UnionWith(IEnumerable other) UnionWith(IEnumerable other) – объединение 2 множеств Overlaps(IEnumerable other) Overlaps(IEnumerable other) – пересечение множеств Проверка на вхождение одного множества в другое IsSubsetOf(IEnumerable other), IsProperSubsetOf( IEnumerable other ) IsSubsetOf(IEnumerable other), IsProperSubsetOf( IEnumerable other ) IsSupersetOf(IEnumerable other), IsProperSupersetOf(IEnumerable other) IsSupersetOf(IEnumerable other), IsProperSupersetOf(IEnumerable other) ExceptWith( IEnumerable other ) ExceptWith( IEnumerable other ) – вычитание множеств Contains(T item) Contains(T item) – проверка на вхождение элемента во множество Count Свойство Count – количество элементов в множестве

Реализуйте программу, позволяющую пользователю вводить строки. Признаком окончания ввода пользователем строк является пустая строка По окончании ввода строк пользователем программа должна выводить введенные пользователем строки в алфавитном порядке.

Коллекции Итераторы

Цикл по всем элементам массива или коллекции ( реализующий интерфейс IEnumerable или IEnumerable ) Синтаксис foreach in foreach ( Тип _ элемента Имя _ переменной in Коллекция ) { // Можно использовать элемент коллекции через Имя _ переменной } Запрещено изменять саму коллекцию ( добавлять, удалять элементы ) внутри цикла Пример : List collection = new List (); … // Заполнение коллекции foreach (Complex comp in collection) { Console.WriteLine(comp); // collection.Add(new Complex(5,4)); Так нельзя. Нельзя изменять саму коллекцию comp.Re = 7; // Так можно. Не меняет саму коллекцию, а меняет внутренности элемента }

Итератор Предоставляет единый способ перебора элементов коллекции Не обязательно перебрать все элементы. Последовательность может быть бесконечной Можно использовать в специальном цикле foreach() По чему можно итерировать ( перебирать элементы ) По классу, реализующему интерфейс IEnumerable или IEnumerable По методу ( свойству ), возвращающему IEnumerator или IEnumerator Все.NET коллекции реализуют интерфейс IEnumerable или IEnumerable. Следовательно по ним можно итерировать

Для возможности перебора элементов класс должен реализовывать интерфейс IEnumerable IEnumerable: interface IEnumerable { IEnumerator GetEnumerator(); } Метод GetEnumerator() должен возвращать тип, реализующий интерфейс IEnumerator IEnumerator: interface IEnumerator { object Current {get;} bool MoveNext(); void Reset(); }

Интерфейс IEnumerable - наследник от IEnumerable IEnumerable : interface IEnumerable : IEnumerable { IEnumerator GetEnumerator(); IEnumerator GetEnumerator(); } Метод GetEnumerator() должен возвращать тип, реализующий интерфейс IEnumerator и IEnumerator ( необходима явная реализация одного из методов ) IEnumerator : interface IEnumerator : IEnumerator, IDisposable { object Current {get;} T Current {get;} bool MoveNext(); void Reset(); Dispose(); }

Собственный итератор

yield Квазиключевое слово yield yield return yield return [expression] yield break yield break; Когда встречается yield Запоминается состояние и возвращается текущее значение На следующей итерации продолжаем с этого состояния Количество итерируемых элементов не обязательно конечно Примеры : public IEnumerator GetEnumerator() { yield return x; yield return y; yield return z; yield break; } int odd = -1; public IEnumerable GetCustomCollection() { while (true) yield return odd+=2; }

Коллекции и Итераторы