Паттерн Итератор

Пред. паттерн: Паттерн Посредник

Назначение: представляет доступ ко всем элементам составного объекта, не раскрывая его внутреннего представления.

Подробнее Iterator on Wiki

Мотивация

Практически любое приложение в той или иной мере работает с коллекциями данных. Мы постоянно используем векторы, списки, деревья и хеш-таблицы. В некоторых случаях для обработки данных коллекции мы используем специфический API конкретных коллекций, но в большинстве случаев мы получаем доступ к их внутренностям за счет специального абстрактного слоя итераторов.

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

Итераторы настолько укоренились в большинстве языков и платформ, что их поддержка появилась даже на уровне языков программирования: foreach в C#, range-for в C++ 11, for в Java 5+ и даже в консервативном Eiffel появилась аналогичная конструкция across. Более того, многие языки поддерживают не только потребление итераторов с помощью циклов foreach, но еще и их создание за счет блоков итераторов (Iterator Block в C# и VB) или так называемых Sequence Comprehension (доступных в F#, Scala, Phyton и многих других языках).

Примеры в .NET Framework

В .NET Framework итераторы представлены парами интерфейсов:

IEnumerable/IEnumerator для работы с необобщенными коллекциями (составными объектами),
IEnumerable<,T>,/IEnumerator<,T>, для работы с обобщенными коллекциями (составными объектами)
IObservable<,T>,/IObserver<,T>, для работы с реактивными (или push-based) коллекциями.

Использование итераторов в языке C# осуществляется с помощью цикла foreach, а создание итераторов упрощается за счет блоков итераторов (Iterator Block).

Обсуждение

Паттерн Итератор это один из немногих паттернов, который пришел в .NET Framework из книги банды четырех практически в неизменном виде. Если взять исходную диаграмму классов из книги Design Patterns, заменить Aggregate на IEnumerable<,T>,, Iterator на IEnumerator<,T>, и немного изменить методы класса Iterator, то мы получим очень похожую картину:

clip_image002

Рисунок 1 Классическая диаграмма паттерна Итератор

clip_image004

Рисунок 2 Паттерн Итератор в .NET Framework

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

Интерфейс IEnumerator также довольно прост:

MoveNext переход на следующий элемент агрегата. Возвращает false, если достигнут конец последовательности.
Current возвращает текущий элемент.
Reset возвращает итератор к началу агрегата. Реализуется не всегда.

Сразу после создания, итератор указывает на -1-й элемент, поэтому для перехода к первому элементу нужно вызвать MoveNext как минимум один раз.

Итераторы в .NET могут показаться довольно примитивными, особенно по сравнению с итераторами в С++. Стандарт С++ определяет несколько разных типов итераторов: Input <,- Forward <,- Bidirectional <,- Random Access. В С++ есть даже Output Iterator, т.е. итератор для вывода данных.

Платформа .NET поддерживает два типа итераторов: необобщенные и обобщенные итераторы. Первые появились с первой версии платформы .NET, а вторые были добавлены со второй версии вместе с обобщениями (generics) и блоками итераторов (iterator blocks).

clip_image006

Рисунок 3 Обобщенные и необобщенные итераторы.

Особенности итераторов в C#/.NET

Контракт итераторов

У любого класса или интерфейса есть контракт. Иногда контракт бывает явным, и тогда он описывается с помощью соответствующих инструментов, таких как Code Contracts. Иногда он является неявным, тогда для понимания принципов использования, предусловий, постусловий и инвариантов, нужно обратиться к документации, внимательно прочитать секцию remarks, а часто еще и вникнуть в детали реализации.

При установки библиотеки Code Contracts в нашем распоряжении появляются контракты всех типов BCL. Однако встроенные контракты интерфейсов IEnumerable/IEnumerator не слишком хороши, поэтому давайте выведем их самостоятельно.

Нас будут интересовать контракты лишь методов MoveNext и свойства Current:public T Current
{
get
{
Contract.Requires(!Disposed, 'Iterator should not be disposed.'),
Contract.Requires(IteratorPointsToCorrectValue,
'MoveNext() should be called and return 'true'.'),
Contract.Ensures(true, 'Returns current value from the Aggregate.'),
return default(T),
}
}
public bool
MoveNext()
{
Contract.Requires(!Disposed, 'Iterator should not be disposed.'),
Contract.Requires(Valid, 'Iterator should be valid.'),
// Если итератор еще не дошел до конца агрегата,
// то он будет перемещен на следующий элемент
Contract.Ensures(Finished() ||
InternalIndex == Contract.OldValue(InternalIndex) + 1
),
Contract.Ensures(Contract.Result<,bool>,() ==
(InternalIndex ==
InternalLength)),
return default(bool),
}

ПРИМЕЧАНИЕ
Обращаю внимание, что это не настоящие контракты итератора, это лишь мое представление того, каким они могли бы быть! Настоящий контракт итератора, определенный в mscorlib.Contracts.dll не содержит всех этих вещей.

Контракт свойства Current:

Предусловие:

Итератор не должен быть освобожден с помощью вызова Dispose.
Итератор должен указывать на корректное значение: пользовательский код должен вызвать метод MoveNext, который должен вернуть true.

Постусловие:

Свойство Current вернет значение, на которое указывает итератор.
Итератор не налагает ограничений, вернет ли это свойство null или нет.

Контракт метода MoveNext:

Предусловие:

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

Постусловие:

Если итератор не дошел до конца коллекции, то итератор перейдет на следующий элемент и метод вернет true, в противном случае, метод вернет false.

Тут есть несколько интересных моментов. Во-первых, предусловие свойства Current слабее предусловия метода MoveNext. На самом деле у свойства Current вообще нет предусловий: мы можем обратиться к свойству Current после вызова Dispose и до вызова MoveNext и не получим исключений! Я же добавил эти требования в контракт, поскольку никто в здравом уме не должен обращаться к свойству Current без выполнения этих условий.

И еще один момент, связанный с методом MoveNext: вам никто не запрещает вызывать MoveNext на завершенном итераторе. В этом случае метод MoveNext просто вернет false! Вот это более валидное требование, поскольку оно позволяет заново проходить по завершенному итератору, а также свободно использовать итератор пустой коллекции (который можно рассматривать как завершенный).

Блоки итераторов

Использование итераторов в блоке foreach мы рассмотрим в следующем разделе, а пока рассмотрим процесс создания итераторов.

Процесс создания итераторов вручную является достаточно утомительным занятием, которое включает управление состоянием, и перемещением по элементам коллекции при вызове MoveNext. С помощью блока итераторов реализовать итератор существенно проще:public static IEnumerator<,int>, CustomArrayIterator(this int[] array)
{
foreach (var n in array) { yield return n, }
}

(Пример создания итератора вручную рассмотрен в заметке Итераторы в C#. Часть 1)

С помощью блока итераторов мы можем создавать итераторы для своих коллекций, существующих коллекций или вообще для внешних ресурсов, таких как файлы. Для этого достаточно открыть файл в начале метода и возвращать прочитанные блоки данных с помощью yield return. Кроме того, мы можем генерировать данные бесконечным образом, о чем мы поговорим в разделе Итераторы и генераторы.

ПРИМЕЧАНИЕ
Теперь должно быть понятно, почему метод Reset в контракте итератора является необязательным. Представьте себе, что итератор возвращает данные, пришедшие по сети. Как в этом случае мы сможем реализовать метод Reset?

Блок итераторов преобразуется компилятором языка C# в конечный автомат с несколькими состояниями, соответствующие начальному положению итератора (когда он указывает на -1-й элемент), конечному положению (когда итератор прошел все элементы) и среднему положению, при котором он указывает на определенный элемент. При этом блок итераторов представляет собой некую форму корутин, которые продолжают исполнение с предыдущего места благодаря методу MoveNext.

Ленивость итераторов

Итераторы, полученные с помощью блока итераторов являются ленивыми: их тело исполняется не в момент вызова метода, а при переборе элементов с помощью метода MoveNext. Это приводит к некоторым особенностям обработки ошибок, ведь даже валидация аргументов метода, возвращающего итератор, будет производиться уже в момент потребления итератора. public static IEnumerable<,string>, ReadFromFile(string path)
{
if (path == null) throw new ArgumentNullException('path'),
foreach(string line in File.ReadLines(path))
{
yield return line,
}
}

// Где будет ошибка?
var result = ReadFromFile(null), //1
foreach (var l in
result)
{
Console.WriteLine(l), //2
}

На этом же принципе построена большая часть методов LINQ (Language Integrated Query), что позволяет получать сложные запросы без лишних накладных расходов.

Подробнее об итераторах в языке C#, а также о деталях реализации блоков итераторов смотрите в статьях: Итераторы в C# - Часть 1, Часть 2, Часть 3.

Использование итераторов в цикле foreach

Цикл foreach является универсальным инструментом для обработки коллекций/последовательностей. Способ его преобразования компилятором зависит от типа перебираемой коллекции (обобщенная/необобщенная) и представляет простой цикл while. Пример обхода необобщенной коллекции выглядит таким образом:public static void ForEachIEnumerable(IEnumerable sequence)
{
// foreach(var e in sequence) {Console.WriteLine(e),}
IEnumerator enumerator = sequence.
GetEnumerator(),
object current = null,
try
{
while (enumerator.MoveNext())
{
current
= enumerator.Current,
Console.WriteLine(current),
}
}
finally
{
IDisposable disposable = enumerator as IDisposable,
if (disposable != null)
{
disposable
.Dispose(),
}
}
}

ПРИМЕЧАНИЕ
Для поддержки цикла foreach не обязательно наличие интерфейса IEnumerable/IEnumerable<,T>,. На самом деле, достаточно, чтобы класс коллекции содержал метод GetEnumerator, который будет возвращать тип, с методом bool MoveNext() и свойством Current.
Подробнее об этом можно почитать в статье: Duck typing или так ли прост старина foreach.
Также стоит обратить внимание, что реализация блока foreach изменилась в C# 5.0, начиная с которого переменная current внесена во внутреннюю область видимости. Подробности: Замыкания на переменных цикла в C# 5.0

Интересный вопрос заключается в том, зачем нужна проверка во время исполнения того, реализует ли итератор интерфейс IDisposable с последующим вызовом метода Dispose? Можете подумать минутку самостоятельноJ

Давайте рассмотрим следующий совершенно корректный код:public IEnumerable CrazyMethod(string path)
{
var file = File.OpenText(path),
try
{
yield return file.ReadLine(),
yield return int.Parse(file.ReadLine()),
}
finally
{
file
.Close(),
}
}

Любой типизированный итератор реализует интерфейс IDisposable, поскольку сам интерфейс IEnumerator<,T>, наследует IDisposable. Причина этого в том, что итераторы, полученные с помощью блока итераторов легко могут содержать ресурсы, которые освобождаются в блоке finally, вызов которого как раз и осуществляется путем вызова Dispose итератора. Но дело все в том, что блок итераторов может возвращать не только типизированный итератор, но и его предшественников: IEnumerable/IEnumerator, которые не реализуют интерфейс IDisposable.

Итераторы или генераторы

Блок итераторов может использоваться для создания итераторов, т.е. для обхода некоторого агрегата в памяти (коллекции) или за ее пределами (итератор содержимого файла). Но помимо этого блок итераторов может использоваться для создания генераторов.

Вот пример простого бесконечного генератора чисел Фибоначчи:public static IEnumerable<,int>, GenerateFibonaci()
{
int prev = 0,
int current = 1,
while (true)
{
yield return current,
int tmp = current,
current
= prev + current,
prev
= tmp,
}
}

В этом плане, блок итераторов в C# напоминает более общие концепции из других языков программирования, такие как List Comprehension, предназначенные для создания последовательностей и коллекций.

Валидность итераторов

В некоторых языках, таких как С++, понятие инвалидации итераторов (когда итератор коллекции становится недействительным) определено в спецификации языка, в разделе, посвященном конкретной коллекции. Так, например, не для всех контейнеров операция добавления элемента делает итератор недействительным: добавление элемента в двусвязный список вполне допустима, а добавление элемента в вектор нет.

Подобные правила, хотя и не столь формальные, существуют и для коллекций .NET Framework. Точнее, есть лишь одно правило и оно не привязано к конкретному типу коллекции: при изменении коллекции все ранее полученные итераторы становятся недейсвтительными. Так, в обоих случаях ниже мы получим InvalidOperationException:var list = new List<,int>, { 42, 12 },
var listIter = list.
GetEnumerator(),
listIter
.MoveNext(),
list
.RemoveAt(1),
Console.WriteLine(listIter.Current), // Ok
listIter.MoveNext(), // InvalidOperationException
var linked = new LinkedList<,int
>,(),
linked
.AddLast(42),
var linkedIter = linked.
GetEnumerator(),
linkedIter
.MoveNext(),
linked
.AddLast(12),
Console.WriteLine(linkedIter.Current), // Ok
linkedIter.MoveNext(),
// InvalidOperationE ception

Это поведение коренным образом отличаются от правил коллекций языка С++, поскольку в случае std::vector и std::list обе приведенные операции были бы допустимыми.

Итераторы и структуры

Итераторы всех коллекций .NET Framework являются изменяемыми структурами. Это избавляет от дополнительного выделения памяти в управляемой куче при проходе по коллекции, а с другой стороны, может привести к неожиданному результату:var x = new {Items = new List<,int>, {1, 2, 3}.GetEnumerator()},
while (x.Items.
MoveNext())
{
Console.WriteLine(x.Items),
}

Но несмотря на потенциальную опасность, итераторы любой широко используемой коллекции должен быть структурой. Более того, в некоторых случаях есть правила, запрещающие использовать коллекции с классами-итераторами. Хорошим примером является правило участия в проекте Roslyn, которое запрещает использовать классы-итераторы в критических участках кода! (см. Roslyn. How to Contribute, раздел Coding Conventions)

ПРИМЕЧАНИЕ
Подробнее о проблемах с изменяемыми значимыми типами читайте в заметках: О вреде изменяемых значимых типов и О вреде изменяемых значимых типов. Часть 2, а еще один пример проблемы изменяемых итераторов рассмотрен в заметке: Observable.Generate и перечисление списков.

Push-based итераторы

Мало кто обратил внимание, что в книге Банды четырех определены два вида итераторов: внешний и внутренний, в зависимости от того, кто управляет итерацией клиент или сам итератор.

Внешний итератор это классический (pull-based) итератор, когда процессом обхода явно управляет клиент путем вызова метода Next или ему подобного. Внутренний итератор это push-based итератор, которому передается метод обратного вызова и он сам уведомляет клиента о посещении следующего элемента.

Несложно догадаться, что ранее мы рассмотрели внешний итератор, а внутренний итератор в .NET представлен библиотекой Reactive Extensions и парой интерфейсов: IObserver<,T>,/IObservable<,T>,. Да, эта пара интерфейсов больше напоминают наблюдатель, а не итератор, но пример все расставит по местам:var list = new List<,int>, {1, 2, 3},
IObservable<,int>, observable = list.
ToObservable(),
observable
.Subscribe(
onNext: n
=>, Console.WriteLine('Processing: {0}', n),
onCompleted: ()
=>, Console.WriteLine('Sequece finished')),

Данный пример не имеет особого смысла, но, например, преобразование в наблюдаемую коллекцию объекта SqlDataReader, который также реализует IEnumerable вполне имело бы смысл.

ПРИМЕЧАНИЕ
Подробнее познакомиться с реактивными расширениями можно в серии статей Ли Кэмпбелла (Lee Campbell) Introduction to Rx.

Применимость

По своему определению, итератор применяется для доступа к содержимому составных объектов, типичным примером которых являются коллекции. Но стоит ли делать итерируемыми бизнес объекты?

Давайте вернемся к вопросу анализа паттернов проектирования. У нас может быть класс PatternsDetector который вполне может реализовывать интерфейс IEnumerable<,DesignPattern>,, что позволит его клиентам перебирать полученные паттерны проектирования. Но вопрос, насколько это отношение корректно?

Я обычно отношусь настороженно к такому подходу. Во-первых, детектор паттернов НЕ ЯВЛЯЕТСЯ коллекцией паттернов. Во-вторых, не вполне понятно, когда именно будет происходить анализ: в конструкторе класса или непосредственно в момент перебора элементов?

Именно поэтому я предпочитаю реализовывать интерфейсы IEnumerable<,T>, только классами, которые по своей природе являются коллекциями элементами, а во всех других случаях делать свойство или метод, которые предоставят доступ к коллекции элементов:class PatternsAnalyzer
{
public PatternsAnalyzer(string source)
{ }
public IEnumerable<,DesignPattern>, Analyze()
{
}
}

ПРИМЕЧАНИЕ
Недавно Эрик Липперт дает похожий совет на StackOverflow.com в ответе на вопрос: Why not inherit from List<,T>,, поясняя, должен ли класс FootballTeam наследовать от List<,Player>,. Эрик советовал аналогичным образом: футбольная команда НЕ ЯВЛЯЕТСЯ списком игроков, поэтому не класс FootballTeam не должен наследовать List<,Player>,. В этом случае гораздо лучше подходит отношение ИМЕЕТ, а значит команда должна содержать список игроков.