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

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

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

Подробнее – 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, то мы получим очень похожую картину:

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

Рисунок 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).

Рисунок 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(); // InvalidOperationException

Это поведение коренным образом отличаются от правил коллекций языка С++, поскольку в случае 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>. В этом случае гораздо лучше подходит отношение ИМЕЕТ, а значит команда должна содержать список игроков.

Дополнительные ссылки

1. Programming Stuff. Итераторы в C#. Часть 1.
2. Programming Stuff. Итераторы в C#. Часть 2.
3. Programming Stuff. Итераторы в C#. Часть 3.
4. Programming Stuff. Duck typing или ”так ли прост старина foreach?”.
5. Programming Stuff. Замыкания на переменных цикла в C# 5.0.
6. Programming Stuff. Контракты на платформе .NET.
7. Jon Skeet. Iterator block implementation details.
8. Eric Lippert. Iterator Block, Part One.
9. Eric Lippert. Iterator Block, Part Two: Why no ref or out parameters?

--------------------

Понравилась статья? Вы же знаете, что ею можно поделиться с друзьями/коллегами;) Вам не сложно, а мне будет приятно.