Название шаблона
Итератор (Iterator).
Тип
Поведенческий шаблон проектирования (Behavioral).
Описание
Шаблон Итератор обеспечивает последовательный доступ ко всем элементам коллекции, не раскрывая при этом её внутренней реализации.
Данный шаблон применяется, если необходимо:
- обеспечить доступ к содержимому объекта без раскрытия его реализации;
- (или) предоставить нескольких способов обхода коллекции;
- (или) реализовать единый интерфейс обхода различных коллекций.
Таким образом, задача Итератора упростить обход и сделать его однообразным для коллекций различных типов. Причем реализация шаблона может находиться как в объекте, представляющим коллекции, так и отдельно от него.
Рассмотрим метод создания отчета для печати. Использование Итератора позволит данному методу не зависеть от деталей реализации коллекции, содержащей исходные данные для его формирования.
Многие языки высокого уровня (C#, C++, F#, PHP) имеют собственную на поддержку Итераторов. Но если стандартных возможностей не достаточно или нужна своя логика обхода элементов, то возможно реализовать данный шаблон самостоятельно. Кроме того, его реализация потребуется и для пользовательских типов коллекций.
Итераторы можно разделить на два вида:
- Внешние – клиент получает экземпляр Итератора и сам запрашивает у него элементы коллекции.
- Внутренние - клиент передает Итератору метод, который вызывается для каждого элемента коллекции.
Определим участников шаблона:
- Интерфейс итератора (IIterator) – определяет методы для доступа к элементам коллекций.
- Итератор (lterator) – реализация Итератора для конкретного типа коллекции.
- Интерфейс составного объекта, коллекции (IContainer) – задает способ получения Итератора клиентом.
- Составной объект, коллекция (Container) – реализация коллекции или фабрики, предоставляющие Итератор.
Поведенческие шаблоны и их отличия
Особенности реализации
Реализация алгоритма обхода коллекции часто располагается в самом Итераторе. Это позволяет создать нескольких вариантов перебора элементов. Другим подходом является его размещение в самой коллекции. При этом Итератор будет содержать только текущее состояние обхода (например, позицию и направление) и называется курсором.
Модификация коллекции во время ее обхода является опасной операцией. Это может привести к тому, что её элемент может быть посещен несколько раз или не посещен вообще. Поэтому выделяют Устойчивые итераторы, которые гарантируют, что изменения коллекции не помешают обходу. Причем это должно достигаться без создания копий коллекции.
Обычно интерфейс Итератора состоит из следующих операций:
- Reset() – устанавливает первый элемент списка в качестве текущего;
- MoveNext() – переход на следующий элемент;
- IsDone – проверяет есть ли еще элементы в коллекции;
- Current – возвращает текущий элемент.
Этот список можно изменять. Например, объединить MoveNext(), IsDone и Current в один метод. Или добавить метод Skip(), позволяющий пропустить заданное число элементов или перейти на заданный. В некоторых случаях может быть полезно свойство содержащее ссылку на предыдущий элемент.
Отдельно стоит отметить Итераторы для древовидных структур, описываемых, например, шаблоном Компоновщик. При этом:
- составные объекты возвращают Итератор для перечня своих потомков;
- части (у которых нет потомков) возвращают вырожденный случай Итератора – NullIterator, который всегда сообщает что обход завершен.
Это позволит разработать Итератор структуры, который будет использовать Итераторы элементов для полного обхода дерева.
Особенности реализации в .NET и C#
В С# поддержка Итераторов реализована на уровне самого языка. В частности
- оператор foreach – организует цикл для перебора элементов коллекции;
- интерфейс IEnumerator – определяет интерфейс Итератора;
- ключевое слово yield – позволяет создавать методы, возвращающие перечисления.
Важно отметить, что C# запрещает изменение коллекции при переборе ее элементов в foreach. Но при этом можно изменять внутреннее состояние самих элементов. Например, следующий код выдает ошибку "error CS1656: Cannot assign to 'item' because it is a 'foreach iteration variable'" на этапе компиляции:
foreach (var item in listItems) {
item = new ListItem();
}
Но ничего не мешает изменять поля внутри элемента вот так:
foreach (var item in docItems) {
item.Text = "New string";
}
Реализация шаблона в общем виде
- определяем тип Итератора (внешний или внутренний) и схему взаимодействия с коллекцией;
- разрабатываем интерфейс Итератора IIterator или берем стандартный;
- реализуем метод или фабрику (IContainer) для создания экземпляров Итератора;
- клиент, используя IContainer, получает экземпляр Итератора и использует его для обхода коллекции не завися от ее типа.
Примеры реализации
Использование стандартных коллекций в C#
Для перебора коллекции в C# используется интерфейс IEnumerator<T>. Его поля:
- Current – свойство, позволяющее получить доступ к текущему элементу;
- MoveNext() – метод, обеспечивающий переход на следующий элемент;
- Reset() – выполнят установку на первый элемент коллекции.
Разработаем демонстрационный класс для хранения данных. Поддержка IComparable потребуется в дальнейшем для использования SortedSet в качестве коллекции.
public class ListItem : IComparable
{
public string Text { get; set; }
#region IComparable Members
int IComparable.CompareTo(object obj)
{
ListItem otherObj = obj as ListItem;
if (otherObj == null) { return -1; }
return this.Text.CompareTo(otherObj.Text);
}
#endregion
}
Теперь создадим метод, который выведет значения всех элементов коллекции. Для этого воспользуемся оператором foreach. Интерфейс IEnumerable<T> предназначен для получения ссылки на IEnumerator<T>. Код цикла будет вызван для каждого элемента коллекции. При этом переменная currentItem при каждом проходе будет указывать на очередной элемент:
public static void Print(IEnumerable<ListItem> items)
{
foreach (ListItem currentItem in items) {
Console.WriteLine(currentItem.Text);
}
}
Осталось проверить в деле. Поэтому создадим две коллекции разного типа:
public static void Execute()
{
var docItems = new List<ListItem>();
docItems.Add(new ListItem() { Text = "1" });
docItems.Add(new ListItem() { Text = "2" });
docItems.Add(new ListItem() { Text = "3" });
Print(docItems);
var docItems2 = new SortedSet<ListItem>();
docItems2.Add(new ListItem() { Text = "3" });
docItems2.Add(new ListItem() { Text = "1" });
docItems2.Add(new ListItem() { Text = "2" });
Print(docItems2);
}
Как видно из исходного кода, реализация метода Print() не зависит от используемой коллекции.
Создание методов, возвращающих коллекции
Для создания методов, возвращающих коллекции элементов, используются два ключевых слова: yield return и yield break. Их присутствие в теле метода сообщает компилятору, что он является блоком итератора. Результат его работы всегда должен быть указан как интерфейс IEnumerable. Это означает, что возвращается коллекция элементов. Наиболее часто подобные решения используются в циклах foreach.
Сам метод вызывается для получения каждого нового значения перечисления. В этом и заключается его главное отличие от готовой коллекции. При этом его локальные переменные сохраняют текущие значения до завершения перечисления. Его признаком могут являться выход из метода без возвращаемого значения или ключевое слово yield break. И в том и в другом случае выполнение цикла прекратится.
Рассмотрим простой пример:
namespace YieldKeywordDemo
{
using System;
using System.Collections;
public class PowerList
{
public IEnumerable Power(int number, int exponent)
{
int valueCounter = 0;
int currentResult = 1;
while (valueCounter++ < exponent) {
currentResult = currentResult * number;
yield return currentResult;
}
}
}
class Program
{
static void Main(string[] args)
{
PowerList demoObj = new PowerList();
// Display powers of 2 up to the exponent 10
foreach (var valuein demoObj.Power(2, 10)) {
Console.Write("{0} ", value);
}
Console.ReadKey(true);
}
}
}
В данном случае метод Power() предоставляет значения степеней от 1 до exponent для заданного числа number. Он будет вызван при каждом проходе цикла foreach. Полученное от него значение будет передано в переменную value, которая используется в теле цикла.
Если заглянуть поглубже, то можно выяснить, что компилятор создает для каждого такого метода свой private sealed класс. При этом он реализует интерфейс IEnumerable. Параметры и переменные исходного метода становятся его публичными полями. Именно поэтому они сохраняют свои значения между вызовами.
Кроме того, исходный код метода Power() будет перемещен в реализацию MoveNext() интерфейса IEnumerable. А вместо него будет подставлен код создания экземпляра нового класса. Можно сказать что компилятор автоматически создал реализацию IEnumerable на основе метода Power().
В сказанном выше очень легко убедиться самостоятельно. Для этого достаточно сначала скомпилировать приведенный выше пример, а затем декомпилировать его обратно. Исходный код будет соответствовать описанному.
Также стоит отметить, что использование foreach не является обязательным условием использования ключевого слова yield. Коллекцию можно перебрать самостоятельно, вызывая метод MoveNext() и используя свойство Current интерфейса IEnumerable.