208

Участники

Iterator (IEnumerator) - Итератор:

Предоставляет интерфейс (набор методов) для доступа к коллекции и обхода элементов.

Concretelterator - Конкретный итератор:

Реализует интерфейс класса Iterator. Следит за позицией текущего элемента при переборе коллекции (Aggregate).

Aggregate (IEnumerable) - Агрегат:

Предоставляет интерфейс коллекции (набор методов) в том числе методы для создания объектаитератора.

ConcreteAggregate - Конкретный агрегат:

Реализует интерфейс коллекции и хранит в себе элементы.

Отношения между участниками

Отношения между классами

Конкретный класс ConcreteAggregate связан связью отношения наследования с абстрактным классом Aggregate и связью отношения зависимости с конкретным классом Concretelterator.

Конкретный класс Concretelterator связан связью отношения наследования с абстрактным классом Iterator и связью отношения ассоциации с конкретным классом ConcreteAggregate.

Отношения между объектами

Concretelterator отслеживает текущий элемент в коллекции (Aggregate) и может вычислить следующий за ним элемент.

Мотивация

Правильно спроектированная коллекция (составной объект), должна предоставлять возможность доступа к своим элементам удобным способом, при этом не раскрывать своего внутреннего устройства (представления). Иногда требуется организовать обход элементов коллекции разными способами. При этом не желательно формировать интерфейс класса List из операций различных вариантов обхода списка (коллекции), даже если все операции можно предусмотреть заранее. Кроме того, иногда требуется, чтобы одновременно имелось несколько вариантов обхода списка.

209

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

Паттерн Iterator рекомендуется использовать, когда:

Требуется организовать доступ к элементам (содержимому) коллекции (агрегированного объекта) без раскрытия устройства (внутреннего представления) коллекции.

Необходимо организовать несколько вариантов обхода коллекции.

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

Результаты

Использование паттерна Iterator предоставляет следующие возможности:

Поддержка различных видов обхода коллекции (агрегата).

Сложные агрегаты (составные объекты – коллекции или контейнеры) можно обходить по-разному. Например, если внутренне устройство коллекции (агрегата) имеет древообразную структуру, требуется организовать правильный обход частей дерева или генерацию новых частей дерева. Итератор может обходить дерево во внутреннем порядке (только части дерева) или в прямом порядке (от корня к листьям). Использование итераторов позволяет организовать динамическую подмену алгоритмов обхода дерева, для этого достаточно заменить один экземпляр итератора другим. Для поддержки новых алгоритмов обхода можно создать новую разновидность итератора.

Итераторы упрощают интерфейс коллекции (агрегата).

Наличие интерфейса (набора методов) для обхода элементов коллекции в классе итератор (Iterator), избавляет от дублирования этого интерфейса непосредственно в классе агрегата (Aggregate), тем самым упрощая интерфейс агрегата.

Для одной коллекции (агрегата), одновременно может быть активно несколько вариантов обхода.

Имеется возможность организации одновременного обращения к элементам коллекции, параллельно из разных потоков. Такие коллекции называются «потокобезопасными коллекциями»

(Concurrency collections), а иногда их называют просто «параллельными коллекциями».

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

Впоставку Microsoft .NET FCL включены готовые решения потокобезопасных коллекций. Пространство имен System.Collections.Concurrent содержит классы потокобезопасных коллекций, такие как: BlockingCollection<T>, ConcurrentBag<T>, ConcurrentDictionary<TKey, TValue>, ConcurrentQueue<T>, ConcurrentStack<T>, OrderablePartitioner<TSource>, Partitioner и Partitioner<TSource>. При построении собственной потокобезопасной коллекции рекомендуется реализовать интерфейс IProducerConsumerCollection<T>, который задает методы для работы с потокобезопасными коллекциями.

210

Реализация

Полезные приемы реализации паттерна Iterator:

Существует несколько способов реализации паттерна итератор. Решение о том, какой способ выбрать, часто зависит от управляющих структур, поддерживаемых языком программирования. Некоторые языки (например, C#) поддерживают реализацию паттерна Iterator в своем синтаксисе (оператор - yield).

Наиболее употребительные варианты реализации паттерна итератор:

•Внешний и внутренний итераторы.

Важнейший вопрос состоит в том, что управляет итерацией - сам итератор или клиент, который пользуется итератором. Если итерацией управляет клиент, то итератор называется внешним (активным), в противном случае если итерация производится автоматически, без участия клиента, итератор называется внутренним (пассивным). Термины «активный» и «пассивный» относятся к роли клиента, а не к действиям, выполняемым итератором. Клиенты, применяющие внешний (активный) итератор, должны явно запрашивать у итератора следующий элемент, чтобы двигаться дальше по коллекции. Напротив, в случае использования внутреннего (пассивного) итератора клиент передает итератору некоторую операцию (или лямбда оператор), а итератор уже сам применяет эту операцию к каждому посещенному во время обхода элементу коллекции. Сильные стороны внутренних (пассивных) итераторов наиболее отчетливо проявляются в таких языках, как C#, где есть анонимные функции, замыкание (closure) и продолжения (continuation). Также, внутренние (пассивные) итераторы проще в использовании, поскольку они легко конфигурируются новой логикой по работе с коллекцией.

Пример работы внутреннего итератора реализованного с использованием оператора yield:

class Program

{

static double Power2(double n)

{

return Math.Pow(n, 2);

}

static void Main()

{

Enumerable enumerable = new Enumerable();

IEnumerable power2List = enumerable.Transform(new Function(Power2));

foreach (var item in power2List)

Console.WriteLine(item);

IEnumerable power3List = enumerable.Transform(n => Math.Pow(n, 3));

foreach (var item in power3List)

Console.WriteLine(item);

}

}

delegate double Function(double arg);

class Enumerable

{

List<double> list = new List<double> { 1, 2, 3, 4 };

public IEnumerable Transform(Function function)

{

foreach (double item in list) yield return function(item);

}

}

См. Пример к главе: \016_Iterator\004_InteralIterator [001]

211

Пример работы внутреннего итератора, реализованного с использованием традиционного подхода:

class Program

{

static double Power2(double n)

{

return Math.Pow(n, 2);

}

static void Main()

{

Enumerable enumerable = new Enumerable();

IEnumerable power2List = enumerable.Transform(new Function(Power2));

foreach (var item in power2List) Console.WriteLine(item);

IEnumerable power3List = enumerable.Transform(n => Math.Pow(n, 3));

foreach (var item in power3List) Console.WriteLine(item);

}

}

delegate double Function(double arg);

public class Enumerable

{

List<double> list = new List<double> { 1, 2, 3, 4 };

public IEnumerable Transform(Function function)

{

return new Enumerator

{

Enumerable = this, Function = function

};

}

// Внутренний (пассивный) итератор. [Nested class] class Enumerator : IEnumerable, IEnumerator

{

public Enumerable Enumerable { get; set; } public Function Function { get; set; } object current;

int position = -1;

bool IEnumerator.MoveNext()

{

if (position < Enumerable.list.Count - 1)

{

position++;

current = Function(Enumerable.list[position]); return true;

}

return false;

}

void IEnumerator.Reset()

{

position = -1;

}

object IEnumerator.Current

{

get { return current; }

}

IEnumerator IEnumerable.GetEnumerator()

{

return this;

}

}

}

См. Пример к главе: \016_Iterator\004_InteralIterator [002]

212

•Итератор – курсор.

Алгоритм обхода коллекции может содержаться не только в итераторе. Алгоритм обхода может находиться непосредственно в коллекции, а коллекция может использовать итератор только для хранения состояния итерации (например, указателя позиции текущего элемента). Такого рода итератор называют курсором, поскольку он всего лишь указывает текущую позицию элемента в коллекции. Клиент может вызывать метод Next коллекции, передавая методу Next в качестве аргумента итератор-курсор. Метод Next в свою очередь состояние итератора-курсора (например, увеличивает значение поля position на один). Если же за алгоритм обхода коллекции отвечает итератор, то для одной и той же коллекции можно использовать разные алгоритмы обхода, а также проще применить один алгоритм обхода к разным коллекциям (полиморфная итерация). Часто бывает так, что для выполнения алгоритма обхода может понадобиться предоставить доступ к закрытым членам коллекции. В таком случае потребуется организовать то перенос алгоритма обхода в итератор, что нарушает инкапсуляцию коллекции. Для сохранения инкапсуляции коллекции можно итератор сделать «nested» классом, вложенным в класс коллекции, что позволит сохранить инкапсуляцию коллекции.

•Устойчивый (робастный) итератор.

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

•Полиморфные итераторы.

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

•Итераторы для коллекций с древообразной структурой.

Реализация внешних (активных) итераторов для рекурсивно агрегированных древообразных структур данных (деревьев) может оказаться затруднительной, так как положение элемента в древообразной структуре данных (дереве) может находиться на нескольких уровнях вложенности (лист, одновременно принадлежащий нескольким ветвям). Поэтому, чтобы отследить позицию текущего элемента, внешний (активный) итератор должен хранить все возможные пути к определенному элементу и исключить повторную обработку такого элемента при обходе дерева. Иногда проще воспользоваться внутренним (пассивным) итератором

Деревья часто приходится обходить несколькими способами. Самые распространенные способы - это обход в прямом порядке (от корня к листьям), обратном порядке (от листьев к корню

– когда у потомков имеются ссылки на родителей), внутреннем порядке (обход отдельной ветки – части дерева), а также обход в ширину (обход элементов на всех ветках дерева, располагающихся на определенном уровне вложенности. Например, если данную книгу представить в виде дерева, то при обходе в ширину читатель будет переходить к каждой главе и читать только раздел «Мотивация»). Каждый вид обхода дерева можно поддержать реализацией отдельного итератора.

•Пустой итератор.

Пустой итератор NullIterator - это вырожденная форма итератора. Пустой итератор NullIterator всегда считает, что обход завершен, то есть его операция IsDone всегда возвращает истину (true). Применение пустого итератора может упростить обход древовидных структур. В каждой точке обхода мы запрашиваем у текущего элемента итератор для его потомков. Ветви дерева обычно, возвращают полноценный итератор, но листовые элементы могут возвращать пустой итератор NullIterator, что позволяет реализовать обход элементов дерева единообразно.

213

В языке C# пустой итератор реализуется при помощи связки операторов yield break. Предлагается рассмотреть создание пустого итератора на примере.

	class Program
	{
	static void Main()		class Enumerable
	{
			{
	Enumerable enumerable	= new Enumerable();
			public IEnumerator GetEnumerator()
	foreach (var item in enumerable)		{
			yield break;
	{
			}
	Console.WriteLine(item);
			}
	}
	}
	}

Для того чтобы понять работу конструкции yield break, желательно посмотреть на код класса итератора, который генерируется конструкцией yield break. Для этого рекомендуется воспользоваться инструментом для обратной инженерии (дизассемблирования) – программой dotPeek от компании JetBrains известной как производителя программы ReSharper.

Для анализа потребуется открыть в программе dotPeek исполняемый файл *.exe содержащий код итератора. В результате дизассемблирования будет представлен следующий код

(для упрощения понимания дизассемблированный код был упрощен):

	class Program		class Enumerable
			{
	{
			public IEnumerator GetEnumerator()
	static void Main()
			{
	{
			return new Enumerator();
	Enumerable enumerable	= new Enumerable();
			}
	foreach (var item in enumerable)		class Enumerator : IEnumerator
	{		{
	Console.WriteLine(item);		bool IEnumerator.MoveNext()
	}		{
	}		return false;
	}		}
			void IEnumerator.Reset()
			{
			throw new NotSupportedException();
			}
			object IEnumerator.Current
			{
			get
			{
			throw new NotSupportedException();
			}
			}
			}
			}

Пустой итератор Enumerator всегда считает, что обход завершен, то есть его операция MoveNext всегда возвращает ложь (false).