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

• Итераторы в C# Часть 2
• Итераторы в C#. Часть 3

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

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

  
Рисунок 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>, то компилятор сгенерирует класс, который будет одновременно и «коллекцией» и итератором.

  
Рисунок 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), но я не знаю человеческого и при этом звучного названия этой ошибки на русском языке; вариант, вида «ошибка занижения или завышения на единицу» вообще нельзя назвать