Перечисления и коллекции в C#

Платформа .NET содержит набор типов для хранения и управления коллекциями объектов: списки с изменяемыми размерами, связанные списки, отсортированные и неотсортированные словари, массивы.

Типы в .NET для коллекций можно разделить на три категории:

  • интерфейсы, определяющие стандартные протоколы коллекций
  • готовые к использованию классы коллекций (списки, словари)
  • базовые классы для написания коллекций

Все эти типы расположены в следующих пространствах имен:

  • System.Collections — необобщенные классы и интерфейсы коллкций
  • System.Collections.Specialized — строго типизированные необобщенные классы коллекций
  • System.Collections.Generic — обобщенные классы и интерфейсы коллекций
  • System.Collections.ObjectModel — прокси и базовые классы для специальных коллекций
  • System.Collections.Concurrent — коллекции, безопасные к потокам

Все коллекции являются перечислениями и реализуют (должны реализовывать) интерфейс IEnumerable или IEnumerable<T>.

Интерфейсы перечислений обеспечивают протокол для итерации по коллекции, но не предоставляют механизма для определения размера коллекции, доступа к члену по индексу, поиска или модификации коллекции. Для данного функционала определены интерфейсы ICollection, IList и IDictionary. Каждый из них имеет обобщенную и необобщенную версию (однако необобщенные используются редко).

Иерархия интерфейсов коллекций:

  • IEnumerable<T> и IEnumerable — минимальный уровень функциональности: только перечисление
  • ICollection<T> и ICollection — средний уровень функциональности, например, свойство Count
  • IList <T>, IDictionary <K,V> и их необобщенные аналоги — максимальный уровень функциональности

Перечисление (Enumeration)

Нумератор, или перечислитель (enumerator) — доступный только для чтения однонаправленный курсор (forward-only cursor — курсор, движущийся только вперёд, без возможности обратного перемещения) перебирающий последовательность (sequence) значений. Нумератор представляет собой объект, реализующий интерфейс System.Collections.IEnumerator или System.Collections.Generic.IEnumerator<T>.

Инструкция foreach перебирает, или выполняет итерацию (iterate) над перечислимыми (enumerable) объектами. Перечислимые объекты — это логическое представление последовательностей. Перечислимый объект — это не курсор, о котором говорилось выше, а объект, содержащий такой курсор, способный перемещаться по объекту и перебирать его. Перечислимый объект либо реализует интерфейс IEnumerable или IEnumerable<T>, либо содержит метод GetEnumerator, который возвращает нумератор (enumerator).

Интерфейсы IEnumerable и IEnumerator

Интерфейс IEnumerator определяет базовый низкоуровневый протокол, посредством которого производится проход по элементам (перечисление) последовательности в одонаправленной манере. Объявление этого интерфейса:

Метод MoveNext передвигает текущий элемент, или курсор, на следующую позицию, возвращая false, если в последовательности больше не осталось элементов. Метод Current возвращает элемент в текущей позиции (приводя его от object к более специфичному типу). Перед извлечением первого элемента должен быть вызван метод MoveNext (это нужно для учета пустой коллекции). Метод Reset (если реализован) осуществляет перемещение к началу.

Коллекции обычно не реализуют перечислители, а предоставляют их через интерфейс IEnumerable:

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

Инструкция foreach предоставляет высокоуровневый и лаконичный способ перебрать перечислимый объект:

Тоже самое можно сделать более низкоуровневым способом без использования инструкции foreach:

Если нумератор реализует интерфейс IDisposable, инструкция foreach действует также как инструкция using, автоматически уничтожая объект нумератора.

Интерфейсы IEnumerable<T> и IEnumerator<T>

Интерфейсы IEnumerator и IEnumerable почти всегда реализуются в сочетании со своими обобщенными версиями:

Инициализаторы коллекций (Collection Initializers)

Можно объявлять и заполнять перечислимые объекты в один шаг:

Компилятор преобразует последнюю строку в следующие инструкции:

Для этого необходимо, чтобы перечислимый объект реализовывал интерфейс System.Collections.IEnumerable, а также у него должен быть метод Add.

Итераторы (Iterators)

Перед тем как использовать нумератор с помощью инструкции foreach его нужно создать и сделать это можно с помощью итератора. Итератор — это метод, свойство или индексатор, содержащий одну или более инструкции yield. Также итератор должен обязательно возвращать (иметь тип) один из четырех интерфейсов (иначе компилятор выдаст ошибку):

  • System.Collections.IEnumerable
  • System.Collections.IEnumerator
  • System.Collections.Generic.IEnumerable<T>
  • System.Collections.Generic.IEnumerator<T>

Если инструкция return возвращает значение из метода и сразу же завершает метод, инструкция yield return действует иначе. Она возвращает очередной элемент перечислимого объекта. При этом метод не завершается сразу же: управление возвращается в точку вызова (обычно это итерация инструкции foreach), но метод-итератор не завершается, он остается в некотором застывшем состоянии до тех пор, пока в точке вызова не будет запрошен следующий элемент, после чего выполнение метода-итератора продолжается. Время жизни этого застывшего состояния итератора ограничивается нумератором — оно прекращается как только в точке вызова прекратиться перечисление.

Компилятор преобразует методы итераторы в частные классы реализующие интерфейс IEnumerable<T> и/или IEnumerator<T>. Логика в блоке итератора преобразуется и распределяется между методом MoveNext и свойством Current созданного компилятором класса нумератора. Это означает, что при вызове метода итератора на самом деле создается экземпляр созданного компилятором класса, а написанный нами код в действительности не выполняется. Наш код выполняется только, когда мы начинаем перебирать получившуюся последовательность, например, с помощью инструкции foreach.

Итераторы возвращающие интерфейс нумератора (т.е. фактически создающие нумератор) на практике используются редко. Они могут быть полезны при написании собственного класса коллекции. В этом случае сам класс коллекции реализует интерфейс IEnumerable<T> (т.е. создает перечислимый объект), а метод итератор получает название GetEnumerator и возвращает нумератор для коллекции.

Итераторы возвращающие интерфейс перечислимого объекта (т.е. фактически создающие такой объект) более просты в использовании и используются чаще. В этом случае нет необходимости создавать класс коллекции — компилятор это сделает за нас, создав частный класс реализующий интерфейс IEnumerable<T> (перечислимый объект) и класс реализующий IEnumerator<T> (нумератор для перечислимого объекта).

Итератор может содержать несколько инструкций yield:

Логика в этом случае такая же — каждая инструкция yield возвращает очередной элемент последовательности.

Инструкция yield break указывает на необходимость завершить блок итератора досрочно и не возвращать больше ни одного элемента:

Инструкция return в блоке итератора недопустима, для выхода из блока итератора нужно использовать только yield break.

Итераторы могут преобразовывать одну последовательность в другую:

Именно эта особенность используется для построения LINQ запросов.

Интерфейсы ICollection<T> и ICollection

ICollection<T> — стандартный интерфейс коллекции объектов с возможностью подсчета:

При реализации коллекции предназначенной только для чтения, методы Add, Remove и Clear должны генерировать исключение NotSupportedException.

Необобщенный интерфейс ICollection также предоставляет возможность подсчета, но не содержит функционал для изменения коллекции (Add, Remove, Clear) и проверки членства элементов (Contains):

Необобщенный интерфейс также определяет свойства для содействия в синхронизации (из обобщенной версии они были исключены).

Интерфейсы IList<T>, IList и IReadOnlyList<T>

IList<T> — стандартный интерфейс коллекции поддерживающей индексацию по позиции. Помимо функционала, унаследованного от ICollection<T> и IEnumerable<T>, он предоставляет возможность чтения и записи элемента по позиции (через индексатор) и вставки/удаления по позиции:

Необобщенный интерфейс IList имеет большее число членов, поскольку наследует меньшее их количество от ICollection:

Метод Add интерфейса IList возвращает индекс вновь добавленного элемента, тогда как метод Add интерфейса ICollection<T> возвращает viod.

Для реализации коллекций предназначенных только для чтения предусмотрен интерфейс IReadOnlyList<T>:

Класс Array

Класс Array является неявным базовым классом для всех одномерных и многомерных массивов. Когда объявляется массив с применением синтаксиса C#, среда CLR неявно создает подтип класса Array

Класс Array реализует интерфейсы коллекций вплоть до IList<T> (в обеих формах — обобщенной и необобщенной). Однако интерфейс IList<T> реализован явно, чтобы закрыть методы Add и Remove, генерирующие исключение. При этом класс Array имеет статический метод Resize (правда он создает новый массив и копирует в него все элементы).

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

Массив можно создать не только с помощью синтаксиса C#, но и динамически с помощью статического метода Array.CreateInstance. При этом можно указать тип элементов и ранг (количество измерений), а также создать массив с индексацией начинающейся не с нуля, за счет указания нижней границы:

Статические методы GetValue и SetValue позволяют получать доступ к элементам в динамически созданном массиве (также работают и с обычными массивами). Метод SetValue генерирует исключение, если элемент имеет тип несовместимый с массивом.

Динамически созданные массивы (индексируемые с нуля) можно привести к обычным массивам совпадающего или совместимого типа:

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

С помощью статического метода Array.ForEach можно выполнить перечисление:

Запросить длину и ранг массива можно с помощью следующих методов и свойств:

Класс Array содержит ряд статических методов для поиска в массиве:

  • BinarySearch — поиск элемента в отсортированном массиве. Этот метод является наиболее быстрым, но работает только на отсортированном массиве. Он может принимать объект IComparer или IComparer<T> для сопоставления элементов с искомым.
  • IndexOf и LastIndex — поиск элемента в несортированном массиве. Методы выполняют перечисление массива и возвращают индекс первого (или последнего) элемента, совпавшего с заданным значением.
  • Find, FindLast, FindIndex, FindLastIndex, FindAll, Exists иTrueForAll — поиска элемента/элементов, удовлетворяющих заданному предикату, в несортированном массиве. Предикат — это просто делегат, принимающий объект и возвращающий true или false:

Примеры использования метода Find:

Метод FindAll возвращает массив всех элементов, удовлетворяющих предикату (эквивалентен методу System.Linq.Enumerable.Where). Метод Existsвозвращает true, если член массива удовлетворяет заданному предикату (эквивалентен System.Linq.Enumerable.Any). Метод TrueForAll возвращаетtrue если все элементы удовлетворяют заданному предикату (эквивалентен System.Linq.Enumerable.All).

Ни один из методов поиска не генерирует исключение если элемент не найден, вместо этого методы возвращающие целочисленное значение возвращают -1, а методы возвращающие обобщенный тип — возвращают стандартное значение для этого типа (0для int, null для string).

С помощью методов Sort можно выполнять сортировку массива:

Каждый из методов дополнительно перегружен и может принимать такие аргументы:

Методы, принимающие пару массивов, упорядочивают элементы в каждом из них, но порядок сортировки определяется по первому массиву:

Метод Sort требует, чтобы элементы массива реализовывали интерфейс IComparable. Если элементы не сравнимы по сути, методу нужно передать либо объект, реализующий IComparer /IComparer<T>, либо делегат Comparison(public delegate int Comparison<T> (T x, T y);), которые и будут принимать решение об упорядочивании элементов:

Метод Reverse изменяет порядок всех или части элементов на противоположный:

Класс Array содержит четыре метода для выполнения поверхностного копированияClone, CopyTo, Copy и ConstrainedCopy. Первые два являются экземплярными, последние — статическими.

Метод ConvertAll приводит все элементы массива к другому типу. Исходный массив не изменяется: метод создает и возвращает новый массив. Приведение осуществляется с помощью переданного методу делегата Converter:

Пример:

Статический метод Resize позволяет изменить размер массива. Пир этом исходный массив не изменяется: метод создает и возвращает новый массив.

Списки

Платформа .NET предоставляет базовый набор классов коллекций, реализующих интерфейсы, описанные выше. Далее рассматриваются списковые коллекции.

List<T> и ArrayList

Обобщенный класс List и необобщенный класс ArrayList представляют собой массивы объектов с возможностью динамического изменения размеров. ArrayList реализует IList, а List<T> реализует IList, IList<T> и IReadOnlyList<T>. В отличие от массивов все интерфейсы реализованы явно, а методы Add и Remove открыты и работают ожидаемым образом.

Класс List<T> до семи раз быстрее чем ArrayList, если T является значимым типом, т.к. List<T> не выполняет упаковку и распаковку элементов (boxing/unboxing).

Члены класса List<T>:

Помимо этих метод класс List<T> содержит экземплярные методы поиска и сортировки, аналогичные статическим методам класса Array. Пример использования методов:

LinkedList<T>

Класс LinkedList<T> представляет обобщенный двусвязный список. Двусвязный список — это цепочка узлов, в которой каждый узел ссылается на предыдущий узел, следующий узел и действительный элемент. Его главное преимущество в том, что элемент может быть эффективно вставлен в любое место списка, т.к. это требует только создания нового узла и обновления нескольких ссылок. Однако поиск выполняется медленно, путем прямого перебора, т.к. двоичный поиск не возможен и отсутствует механизм индексации.

Класс LinkedList<T> реализует IEnumerable<T> и ICollection<T> (и их необобщенные варианты), но не IList<T>, поскольку доступ по индексу не поддерживается. 

Узлы списка реализованы классом LinkedListNode<T>:

Члены класса LinkedList<T>:

Пример использования:

Queue<T> и Queue

Queue<T> и Queue — это очереди — структуры данных FIFO (first-in first-out — первым зашел, первым вышел). Очереди являются перечислимыми, но не реализуют интерфейсы IList<T>/IList, т.к. доступ к элементам по индексу не поддерживается. Основное преимущество — скорость добавления (в конец очереди) и извлечения (с начала очереди) элементов из очереди.

Пример использования:

Stack<T> и Stack

Stack<T> и Stack — это стэки — структуры данных LIFO (last-in first-out — последним пришел, первым вышел).

Пример использования:

BitArray

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

Класс поддерживает доступ по индексу, а также содержит четыре метода для выполнения побитовых операций: And, Or, Xor и Not (все кроме последнего принимают другой экземпляр BitArray).

HashSet<T> и SortedSet<T>

HashSet<T> и SortedSet<T> — обобщенные коллекции, обладающие следующими особенностями:

  • их методs Contains выполняются быстро с использованием основанного на хэшировании поиска
  • они не хранят дублированный элементы и молча игнорируют запросы на добавление дубликатов
  • доступ к элементам по позиции не возможен

SortedSet<T> хранит элементы упорядоченными, HashSet<T> — нет. HashSet<T> реализована с помощью хэш-таблицы, в которой хранятся только ключи, а SortedSet<T> реализована посредством красно-черного дерева.

Обе коллекции реализуют интерфейс ICollection<T> и помимо стандартных членов этого интерфейса включают следующие методы:

SortedSet<T> дополнительно включает следующие члены:

Словари

Словарь — это коллекция, в которой каждый элемент является парой ключ-значение. В .NET для словарей предусмотрено два интерфейса IDictionary и IDictionary <TKey, TValue>, а также ряд готовых классов (несортированные: Dictionary <K,V>HashtableListDictionaryOrderedDictionary; сортированный: SortedDictionary <K,V>SortedList <K,V>SortedList). Различаются они по функционалу и по скорости извлечения значение.

Интерфейс IDictionary<TKey,TValue> и IDictionary

Интерфейс IDictionary<TKey,TValue> определяет стандартный протокол для всех коллекций основанных на парах ключ-значение. Он расширяет ICollection<T>, добавляя методы и свойства для доступа к элементам с помощью ключей произвольных типов:

Добавить элемент в словарь можно либо с помощью метода Add, либо по индексу (с помощью индексатора). В последнем случае если ключ в словаре отсутствует элемент будет добавлен, в противном случае обновлен. Дублированные ключи запрещены, поэтому вызов Add дважды с тем же ключом приведет к генерации исключения.

Для извлечения элементов из словаря используется либо индексатор, либо метод TryGetValue. Если ключ не существует, индексатор генерирует исключение, а метод TryGetValue вернет false. С помощью метода ContainsKey можно проверить наличие элемента в словаре (по ключу).

Перечисление словаря возвращает последовательность структур KeyValuePair:

Существует также интерфейс IReadOnlyDictionary<TKey,TValue> для словарей предназначенных только для чтения.

Необобщенный интерфейс IDictionary в принципе схож с обобщенным аналогом, за исключением двух отличий:

  • извлечение несуществующего ключа через индексатор дает null, а не генерирует исключение
  • членство проверяется с помощью Contains, а не ContainsKey

Перечисление по необобщенному IDictionary возвращает последовательность структур DictionaryEntry:

Dictionary<TKey,TValue> и Hashtable

Обобщенный класс Dictionary<TKey,TValue> использует хэш-таблицу для хранения данных, в связи с чем является быстрым и эффективным. Необобщенная версия Dictionary<TKey,TValue> называется HashtableDictionary<TKey,TValue> реализует обобщенный и необобщенный интерфейсы IDictionary.

Пример использования Dictionary<TKey,TValue>:

Лежащая в основе словаря хэш-таблица преобразует ключ каждого элемента в целочисленный хэш-код — псевдоуникальное значение — а затем преобразует хэш-код в хэш-ключ. Этот хэш-ключ и применяется для определения, какое значение к нему относится. Словарь может работать с ключами любого типа благодаря средствам определения эквивалентности ключей и получения хэш-кодов. По умолчанию эквивалентность определяется с помощью метода object.Equals ключа, а псевдоуникальный хэш-код получается через метод GetHashCode. Поведение по умолчанию можно изменить либо переопределив указанные методы, либо передав конструктору словаря объект IEqualityComparer.

Элементы Dictionary и Hashtable не отсортированы, порядок, в котором они добавляются не сохраняется. Дублированные ключи не разрешены.

OrderedDictionary

Класс OrderedDictionary — это необобщенный словарь, который сохраняет элементы в том же самом порядке, в котором они добавлялись. Он не является отсортированным словарем. Получать доступ к элементам можно и по индексу, и по ключу.

Класс OrderedDictionary представляет собой комбинацию Hashtable и ArrayList: он обладает все функциональность Hashtable, а также функциями вроде RemoveAt и целочисленным индексатором.

Обобщенной версии этого класса не существует.

ListDictionary и HybridDictionary

Класс ListDictionary использует односвязный список для хранения данных. Он не является сортированным массивом, но сохраняет исходный порядок элементов. ListDictionary работает исключительно медленно для больших списков, но эффективен для очень маленьких списков (до 10 элементов).

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

Отсортированные словари

.NET предусматривает два класса отсортированных словарей: SortedDictionary<TKey,TValue> и SortedList<TKey,TValue>. Их содержимое всегда сортируется по ключу.

Класс SortedDictionary использует структуру красно-черно дерева, в силу чего работает одинаково хорошо и при вставке, и при удалении элементов. Класс SortedList внутренне реализован с помощью пары упорядоченных массивов, что обеспечивает быстрое извлечение, но низкую производительность вставки.

Класс SortedDictionary намного быстрее, чем SortedList при вставке элементов, но последний обладает возможность доступа к элементам по индексу. Дублированные ключи в обоих классах недопустимы.

Настраиваемые коллекции

Collection<T> и CollectionBase

Обобщенный класс Collection<T> и необобщенный CollectionBase позволяют управлять тем, что происходит при добавлении или удалении элемента.

Класс Collection<T> является оболочкой для List<T> и определяет четыре дополнительных виртуальных метода и частное свойство:

Необобщенный класс CollectionBase менее удобен в использовании. Он включает методы OnInsert, OnInsertComplete, OnSet, OnSetComplete, OnRemove,OnRemoveComplete,
OnClear и OnClearComplete, выполняющие тот же функционал.

KeyedCollection<TKey,TItem> и DictionaryBase

Класс KeyedCollection<TKey,TItem> является подклассом Collection<T>, в силу чего наследует его функционал и добавляет возможность доступа к элементам по ключу, почти как в словаре.

Дополнительные методы класса KeyedCollection<TKey,TItem>:

Класс DictionaryBase является необобщенной версиейKeyedCollection<TKey,TItem> и менее удобен в использовании.

ReadOnlyCollection<T>

Класс ReadOnlyCollection<T> является оболочкой для коллекции, делая ее доступной только для чтения. Конструктор класса принимает входную коллекцию и устанавливает на нее ссылку. Он не создает копии коллекции, поэтому если коллекция будет изменена из-вне, эти изменения будут видны через оболочку ReadOnlyCollection<T>.

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *