Итератор – паттерн поведения объектов

Назначение

Предоставляет способ последовательного доступа ко всем элементам составного объекта, не раскрывая его внутреннего представления

Известен также под именем

Cursor (курсор)

Iterator : мотивация

Составной объект, скажем список, должен предоставлять способ доступа к своим элементам, не раскрывая их внутреннюю структуру. Более того, иногда требуется обходить список по-разному, в зависимости от решаемой задачи. Но вряд ли вы захотите засорять интерфейс класса List операциями для различных вариантов обхода, даже если все их можно предвидеть заранее. Кроме того, иногда нужно, чтобы в один и тот же момент было определено несколько активных обходов списка.

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

Например, класс List мог бы предусмотреть класс Listlterator.

Рисунок 35

Прежде чем создавать экземпляр класса Listlterator, необходимо иметь список, подлежащий обходу. С объектом Listlterator вы можете последовательно посетить все элементы списка. Операция CurrentItem возвращает текущий элемент списка, операция First инициализирует текущий элемент первым элементом списка, Next делает текущим следующий элемент, a IsDone проверяет, не оказались ли мы за последним элементом, если да, то обход завершен.

Отделение механизма обхода от объекта List позволяет определять итераторы, реализующие различные стратегии обхода, не перечисляя их в интерфейсе класса List. Например, FilteringListlterator мог бы предоставлять доступ только к тем элементам, которые удовлетворяют условиям фильтрации.

Заметим: между итератором и списком имеется тесная связь, клиент должен иметь информацию, что он обходит именно список, а не какую-то другую агрегированную структуру. Поэтому клиент привязан к конкретному способу агрегирования. Было бы лучше, если бы мы могли изменять класс агрегата, не трогая код клиента. Это можно сделать, обобщив концепцию итератора и рассмотрев полиморфную итерацию.

Например, предположим, что у нас есть еще класс SkipList, реализующий список. Список с пропусками (skiplist) - это вероятностная структура данных, по характеристикам напоминающая сбалансированное дерево. Нам нужно научиться писать код, способный работать с объектами как класса List, так и класса SkipList.

Определим класс AbstractList, в котором объявлен общий интерфейс для манипулирования списками. Еще нам понадобится абстрактный класс Iterator, определяющий общий интерфейс итерации. Затем мы смогли бы определить конкретные подклассы класса Iterator для различных реализаций списка. В результате механизм итерации оказывается не зависящим от конкретных агрегированных классов

Рисунок 36

Остается понять, как создается итератор. Поскольку мы хотим написать код, независящий от конкретных подклассов List, то нельзя просто инстанцировать конкретный класс. Вместо этого мы поручим самим объектам-спискам создавать для себя подходящие итераторы, вот почему потребуется операция Createlterator, посредством которой клиенты смогут запрашивать объект-итератор.

Createlterator - это пример использования паттерна фабричный метод. В данном случае он служит для того, чтобы клиент мог запросить у объекта-списка подходящий итератор. Применение фабричного метода приводит к появлению двух иерархий классов - одной для списков, другой для итераторов. Фабричный метод Createlterator «связывает» эти две иерархии.

Iterator : применимость

Используйте итератор:

• Для доступа к содержимому агрегированных объектов без раскрытия их внутреннего представления.

• Для поддержки нескольких активных обходов одного и того же агрегированного объекта.

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

Iterator : структура

Рисунок 37

Участники

• Iterator – итератор - определяет интерфейс для доступа и обхода элементов;

• Concretelterator - конкретный итератор:
- реализует интерфейс класса Iterator;
- следит за текущей позицией при обходе агрегата;

• Aggregate – агрегат - определяет интерфейс для создания объекта-итератора;

• ConcreteAggregate - конкретный агрегат - реализует интерфейс создания итератора и возвращает экземпляр подходящего класса Concretelterator.

Отношения

Concretelterator отслеживает текущий объект в агрегате и может вычислить идущий за ним.

Iterator : особенности

• Поддерживает различные виды обхода агрегата. Сложные агрегаты можно обходить по-разному. Итераторы упрощают изменение алгоритма обхода - достаточно просто заменить один экземпляр итератора другим. Для поддержки новых видов обхода можно определить и подклассы класса Iterator.

• Итераторы упрощают интерфейс класса-агрегата. Наличие интерфейса для обхода в классе Iterator делает излишним дублирование этого интерфейса в классе Aggregate. Тем самым интерфейс агрегата упрощается;

• Одновременно для данного агрегата может быть активно несколько обходов. Итератор следит за инкапсулированным в нем самом состоянием обхода. Поэтому одновременно разрешается осуществлять несколько обходов агрегата.

Iterator : реализация

Существует множество вариантов реализации итератора. Ниже перечислены наиболее употребительные.

• Какой участник управляет итерацией? Важнейший вопрос состоит в том, что управляет итерацией: сам итератор или клиент, который им пользуется. Если итерацией управляет клиент, то итератор называется внешним, в противном случае - внутренним. Клиенты, применяющие внешний итератор должны явно запрашивать у итератора следующий элемент, чтобы двигаться дальше по агрегату. Напротив, в случае внутреннего итератора клиент передает итератору некоторую операцию, а итератор уже сам применяет эту операцию к каждому посещенному во время обхода элементу агрегата. Внешние итераторы обладают большей гибкостью, чем внутренние. Например, сравнить две коллекции на равенство с помощью внешнего итератора очень легко, а с помощью внутреннего - практически невозможно. Но, с другой стороны, внутренние итераторы проще в использовании, поскольку они вместо вас определяют логику обхода.

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

• Дополнительные операции итератора. Минимальный интерфейс класса Iterator состоит из операций First, Next, IsDone и Currentltem. Но могут оказаться полезными и некоторые дополнительные операции. Например, упорядоченные агрегаты могут предоставлять операцию Previous, позиционирующую итератор на предыдущий элемент. Для отсортированных или индексированных коллекций интерес представляет операция SkipTo, которая позиционирует итератор на объект, удовлетворяющий некоторому критерию.

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

Применение в Java API

Классы коллекций в пакете java.util созданы в соответствии с шаблоном Iterator. Классы этого пакета, реализующие java.util.Collection, определяют внутренние закрытые классы, которые реализуют java.util.Iterator.

Паттерн Mediator.