пятница, 11 июня 2010 г.

Итераторы в языке C#. Часть 1

Шаблон проектирования «Итератор» предназначен для последовательного доступа ко всем элементам коллекции (агрегата), не раскрывая ее внутренней структуры. Это один из классических шаблонов проектирования, описанный в знаменитой книги «банды четырех», который подтвердил свою эффективность и жизнеспособность за длительный период применения. Важность и особенности реализации этого шаблона сильно зависят от конкретного языка программирования, но в том или ином виде, он присутствует в большинстве современных языках и библиотеках.

Общий вид шаблона проектирования «Итератор» следующий:

1  
Рисунок 1 – Общий вид шаблона проектирования «Итератор»

В разных языках и средах итераторы поддерживают разную функциональность. Существуют однонаправленные и двунаправленные итераторы, некоторые итераторы позволяют удалять или модифицировать элементы коллекции; в большинстве языков итератор становится недействительным, если после его получения коллекция будет изменена (например, при добавлении или удалении элементов; хотя это зависит не столько от языка, сколько от типа коллекции). Язык C# поддерживает только однонаправленные итераторы, которые не поддерживают ничего кроме получения текущего элемента, перемещения на следующий элемент и перемещение в начало коллекции (причем последняя возможность не является обязательной).

Создание итератора своими руками

Для реализации итератора на языке C# нужно выполнить одно из двух условий. Во-первых, вы можете просто реализовать интерфейс IEnumerable или его «обобщенный» вариант – IEnumerable<T> (*), во-вторых, ваша коллекция может просто содержать метод GetEnumerable, который, в свою очередь возвратит сущность, содержащую свойство Current и метод MoveNext.

ПРИМЕЧАНИЕ
Стандартные идиомы именования, применяемые в языке C# и платформе .NET несколько отличаются от стандартных идиом именования, применяемых в реализации этого шаблона проектирования в других языках и средах. Возможно более уместными названиями были бы такие названия, как Iterable и Iterator, но поскольку можно с увернностью сказать, что менять эти названия никто не станет, вы просто должны понимать, что за интерфейсами IEnumerable и IEnumerator скрывается именно «итерируемая коллекция» и «итератор».

Давайте начнем с менее распространенного варианта, который основан не на реализации интерфейсов IEnumerable или IEnumerable<T>, а на соответствии кода приведенному выше шаблону (реализация итератора с помощью одного из интерфейсов IEnumerable является аналогичной, просто хочется подчеркнуть, что реализация интерфейса IEnumerable не является обязательной):

ПРИМЕЧАНИЕ
Необходимость в сопоставлении с шаблоном (“match the pattern”) потребовалось разработчикам языка C# 1.0 для того, чтобы реализовать типизированные коллекции без использования обобщений (который на тот момент еще не было). Интерфейс IEnumerable возвращает object, а это значит, что было бы невозможно реализовать эффективный итератор по типизированной коллекции целых чисел, поскольку каждый раз при получении элемента коллекции происходила бы упаковка и распаковка текущего элемента.

class CustomContainer
{
    public int this[int idx] { ... }
    public int Count { ... }
    public void Add(int value) { ... }

    public CustomIterator GetEnumerator()
    {
        return new CustomIterator(this);
    }
   
    public struct CustomIterator
    {
        internal CustomIterator(CustomContainer container)
        {
            this.container = container;
            currentIndex = -1;
        }

        public int Current
        {
            get 
            {
                if (currentIndex == -1 ||
                    currentIndex == container.Count)
                {
                    throw new InvalidOperationException();
                }
                return container[currentIndex];
            }
        }

        public bool MoveNext()
        {
            if (currentIndex != container.Count)
            {
                currentIndex++;
            }
            return currentIndex < container.Count;
        }
       
       // При реализации итератора без интерфейса IEnumerator
       // этого метода может и не быть
        public void Reset()
        {
            currentIndex = -1;
        }

        private readonly CustomContainer container;
        private int currentIndex;
}

Пользоваться итераторами в языке C# всегда было просто и удобно; оператор foreach упрощает работу с итераторами, самостоятельно вызывая MoveNext до тех пор, пока эта функция не вернет false:

CustomContainer cc = GetCustomContainer();
foreach (var i in cc)
{
    Console.WriteLine("{0} ", i);
}

Отделение класса итератора от класса коллекции в нашей реализации обусловлено не только принципом единственной ответственности (SRP – Single Responsibility Principle), но и банальным здравым смыслом. Очевидно, что процесс итерирования физически не связан с самой коллекцией, но еще более важным фактором является то, что мы можем использовать более одного объекта итератора для разных, независимых операций перебора элементов, именно поэтому в нашей реализации метод GetEnumerator всегда возвращает новый объект.

ПРИМЕЧАНИЕ
Хотя, как мы увидим позднее, код, генерируемый компилятором не всегда соблюдает подобные принципы. Так, например, если метод «блок итератора» возвращает IEnumerable или IEnumerable<T>, то компилятор сгенерирует класс, который будет одновременно и «коллекцией» и итератором.

Figure2  
Рисунок 2 – Контейнер с двумя объектами итераторами

Для реализации этого шаблона проектирования мы создали вложенный класс, который получает коллекцию в качестве параметра конструктора и сохраняет ее в одном из своих полей, кроме этого, итератор содержит текущий индекс (currentIndex), указывающий на текущий элемент коллекции, который можно получить с помощью свойства Current. Согласно идиоме, принятой в языке C# (точнее в .NET, см. документацию интерфейса IEnumerable), итератор после создания должен указывать на элемент, предшествующий первому элементому коллекции (в нашем случае это означает, что текущий индекс должен равняться -1) и должен указывать на первый элемент коллекции после первого вызова MoveNext. Метод MoveNext должен возвращать true, если перемещение на следующий элемент коллекции выполнено успешно, в противном случае (если мы уже прошли всю коллекцию), этот метод должен возвращать false (при этом итератор должен указывать на элемент, расположенный за последним элементом коллекции). Метод Reset должен возвращать итератор в первоначальное состояние, а обращение к текущему элементу (к свойству Current) в случае, если итератор указывает на некорректный элемент, должно приводить к генерации исключения InvalidOperationException. Итератор также должен позаботиться о том, чтобы после его создания коллекция не была изменена, и в случае обращения к текущему элементу после изменения коллекции, также должно генерироваться исключение InvalidOperationException (это поведение в приведенном выше примере не отражено).

Хотя приведенная выше реализация не является слишком сложной с технической точки зрения, но она достаточно объемная (при учете, что эта реализация не отслеживает изменение коллекции), да и допустить off-by-one ошибки (*) очень просто. Поэтому не удивительно, что далеко не все пользовательские коллекции в C# 1.0 поддерживали этот шаблон проектирования, многие из них просто предоставляли специфический интерфейс доступа к своему содержимому. Также не должно быть удивительным то, что разработчики языка C# упростили этот процесс в будущих версиях языка, в частности, путем введения «блока итераторов» (iterator block), и ключевых слов yield return и yield break.

В следующий раз: решение этой же задачи с помощью блока итераторов (Iterator Blocks).

-------------------------------
(*) Это стандартное название ошибки завышения или занижения на единицу индекса массива (http://en.wikipedia.org/wiki/Off-by-one_error), но я не знаю человеческого и при этом звучного названия этой ошибки на русском языке; вариант, вида «ошибка занижения или завышения на единицу» вообще нельзя назвать

3 комментария:

  1. Если рассмотреть вариант коллекции дерево, где каждый узел знает о всех соседних узлах (т.е. и о Parent узле), то организация самой коллекции будет построена, по сути, на самих итераторах (только больше возможностей чем у IEnumerable). Впрочем, это относится и к связанным спискам. Конечно, итераторы для них будут просто указателями на один элемент, через который MoveNext будет переходить по соответствующей ссылке.
    Для меня всё-таки такой интерфейс не удобен из-за наличия Current'а (для контейнеров связанных объектов нужно дополнительное состояние итератора) и Reset'а. Последний сразу ограничивает применение итераторов для бесконечных и необратимых последовательностей (генераторы последовательности ключей для шифрования, разбор потока данных на сокет и т д).
    Было бы куда проще с вариантом:
    interface IEnumerable<T>
    {
      bool MoveNext(out T next);
    }
    Но из-за того, что C# ориентируется на стэковую VM и out параметр это вовсе не передача указателя на локальную переменную в этом же стэке (как я понимаю), а нечто что останется на стэке (поэтому ему всегда должно присваиваться какое-то значение) после вызова MoveNext, то Current даёт немного больше контроля над доступом к несуществующему элементу (перед или после коллекции). Но вот для Reset-а я не вижу оправданий. Впрочем, как и для foreach'а который требует IEnumerable, а не IEnumerator, чем не позволяет делать:
    var i = collection.GetEnumerator();
    int a = 0, b = 0;
    foreach(var x in i)
    {
      if (x == '\t')
      { break; }
      else
      { ++a; }
    }
    foreach(var y in i)
    {
      ++b;
    }

    P.S. Думаю IEnumerable - еще нормальное название (получить итератор на перечисляемые элементы). А вот IEnumerator, скорее связанно с некрасивым именем IIterator (наличие коллекции под ним, скорее всего, только из-за необходимости реализовать Reset).

    ОтветитьУдалить
  2. 2ony:
    По поводу метода Reset. Да, эта штука в большинстве случаев не реализуется, и, опять же, в большинстве случаев не смущает. Ведь это не мешает нам с вами пользоваться LINQ-ом, в котором этот метод просто кидает исключение NotImplementedException.

    По поводу bool MoveNext(out T next);
    Причина по которой мы обязаны проинициализировать next заключается в том, что "логически" - это второе возвращаемое значение (Кстати, Эрик в одном из своих постов говорил о том, что .net может быть реализован на платформах, где вообще стека нет;) ). Так что здесь все проще. Если бы в языке была встроенная поддержка кортежей (как например в F#), то сигнатура метода могла бы выглядить так:
    Tuple MoveNext().

    (кстати, в F# мы можем использовать именно такой код:
    (b, n) = MoveNext();
    ).

    По поводу примера с foreach-ем. Да, здесь придется перебирать элементы руками. С другой стороны, ведь никто и не пытался получить решение удобное *во всех* случаях. Основная проблема, почему этот код не работает связана с тем, что блок foreach обязательно вызывает Dispose. И это хорошо, поскольку это нужно значительно чаще, чем то, что привели вы, а отсутствие сего выызова может привести к тому, что блок finally итератор не будет вызван. Вот и получается, что блок foreach не умеет делать это просто by design.

    ОтветитьУдалить