Client
ConcreteIterator
CreateIterator()
Aggregate
CreateIterator()
ConcreteAggregate
First()
Next()
IsDone()
CurrentItem()
Iterator
return new ConcreteIterator(this)
Участники
Iterator — итератор:
• определяет интерфейс для доступа и обхода элементов;
Паттерн Iterator (итератор)
305
ConcreteIterator — конкретный итератор:
• реализует интерфейс класса
Iterator
;
• следит за текущей позицией при обходе агрегата;
Aggregate — агрегат:
• определяет интерфейс для создания объекта-итератора;
ConcreteAggregate — конкретный агрегат:
• реализует интерфейс создания итератора и возвращает экземпляр подходящего класса
ConcreteIterator
Отношения
ConcreteIterator отслеживает текущий объект в агрегате и может вычислить идущий за ним.
Результаты
Основные достоинства и недостатки паттерна итератор:
поддержка разных способов обхода агрегата. Сложные агрегаты можно обходить по-разному. Например, для генерации кода и семантических проверок нужно обходить деревья синтаксического разбора. Генератор кода может обходить дерево во внутреннем или прямом порядке. Ите- раторы упрощают изменение алгоритма обхода — достаточно просто за- менить один экземпляр итератора другим. Для поддержки новых видов обхода можно определить и подклассы класса
Iterator
;
упрощение интерфейса класса Aggregate. Наличие интерфейса для об- хода в классе Iterator делает излишним дублирование этого интерфейса в классе
Aggregate
. Тем самым интерфейс агрегата упрощается;
возможность наличия нескольких активных обходов для данного агрега-
та. Итератор следит за инкапсулированным в нем самом состоянием обхода, поэтому одновременно могут существовать несколько обходов агрегата.
Реализация
Существует множество вариантов и альтернативных способов реализации итератора, ниже перечислены наиболее употребительные. Выбор часто зави- сит от управляющих структур, поддерживаемых языком программирования.
Некоторые языки (например, CLU [LG86]) даже поддерживают данный паттерн напрямую.
306 Глава 5. Паттерны поведения
Какой участник управляет итерацией? Важнейший вопрос состоит в том, что управляет итерацией: сам итератор или клиент, который им пользуется. Если итерацией управляет клиент, то итератор называется
внешним, в противном случае —
внутренним1
. Клиенты, применяющие внешний итератор, должны явно
запросить у итератора следующий эле- мент, чтобы двигаться дальше по агрегату. С другой стороны, в случае внутреннего итератора клиент передает итератору некоторую опера- цию, а итератор уже сам применяет эту операцию к каждому посещен- ному во время обхода элементу агрегата.
Внешние итераторы обладают большей гибкостью, чем внутренние.
Например, сравнить две коллекции на равенство с помощью внешнего итератора очень легко, а с помощью внутреннего — практически невоз- можно. Слабые стороны внутренних итераторов наиболее отчетливо проявляются в таких языках, как C++, где нет анонимных функций, замыканий (closure) и продолжений (continuation), как в Smalltalk или
CLOS. С другой стороны, внутренние итераторы проще в использовании, поскольку они вместо вас определяют логику обхода;
что определяет алгоритм обхода? Алгоритм обхода можно определить не только в итераторе. Его может определить сам агрегат и использо- вать итератор только для хранения состояния итерации. Такого рода итератор называется
курсором, поскольку он всего лишь указывает на текущую позицию в агрегате. Клиент вызывает операцию
Next агрегата, передавая ей курсор в качестве аргумента. Операция же
Next изменяет состояние курсора
2
Если за алгоритм обхода отвечает итератор, то для одного и того же агрегата можно использовать разные алгоритмы итерации, и, кроме того, проще применить один алгоритм к разным агрегатам. С другой стороны, алгоритму обхода может понадобиться доступ к закрытым переменным агрегата. Если это так, то перенос алгоритма в итератор нарушает инкап- суляцию агрегата;
насколько итератор устойчив? Модификация агрегата в то время, как совершается его обход, может оказаться опасной. Если при этом до- бавляются или удаляются элементы, то не исключено, что некоторый
1
Грейди Буч (Grady Booch) называет внешние и внутренние итераторы соответственно активными и пассивными [Boo94]. Термины «активный» и «пассивный» относятся к роли клиента, а не к действиям, выполняемым итератором.
2
Курсоры — это
простой пример применения паттерна хранитель; их реализации имеют много общего.
Паттерн Iterator (итератор)
307элемент будет посещен дважды или вообще ни разу. Простое решение — скопировать агрегат и обходить копию, но обычно это слишком дорого.
Устойчивый итератор (robust) гарантирует, что ни вставки, ни удаления не помешают обходу, причем достигается это без копирования агрегата.
Есть много способов реализации устойчивых итераторов. В большинстве из них итератор регистрируется в агрегате. При вставке или удалении агрегат либо корректирует внутреннее состояние всех созданных им итераторов, либо организует внутреннюю информацию так, чтобы обход выполнялся правильно.
В работе Томаса Кофлера (Thomas Kofler) [Kof93] приводится подробное обсуждение реализации итераторов в каркасе ET++. Роберт Мюррей
(Robert Murray) [Mur93] описывает реализацию устойчивых итераторов для класса
List из библиотеки USL Standard Components;
дополнительные операции итератора. Минимальный интерфейс клас- са
Iterator состоит из операций
First
,
Next
,
IsDone и
CurrentItem
1
Впрочем, некоторые дополнительные операции также могут оказаться полезными. Например, упорядоченные агрегаты могут предоставлять операцию
Previous
, переводящую итератор к предыдущему элементу.
Для отсортированных или индексированных коллекций интерес пред- ставляет операция
SkipTo
, которая позиционирует итератор на объект, удовлетворяющий некоторому критерию;
использование полиморфных итераторов в C++. Использование по- лиморфных итераторов сопряжено с определенными затратами. Объ- ект-итератор должен создаваться динамически фабричным методом, поэтому использовать их стоит только тогда, когда есть необходимость в полиморфизме. В противном случае применяйте конкретные итерато- ры, которые вполне можно создавать в стеке.
У полиморфных итераторов есть еще один недостаток: за их удаление отвечает клиент. Здесь открывается большой простор для ошибок, так как очень легко забыть об освобождении созданного в куче объекта-ите- ратора после завершения работы с ним. Особенно велика вероятность этого, если у операции есть несколько точек выхода. А в случае выдачи исключения память, занимаемая объектом-итератором, вообще никогда не будет освобождена.
1
Этот интерфейс можно дополнительно сократить, объединив операции Next, IsDone и CurrentItem в одну, которая будет переходить к следующему объекту и возвращать его. Если обход завершен, то операция вернет специальное значение (например, 0), обозначающее конец итерации.
308 Глава 5. Паттерны поведения
Ситуацию помогает исправить паттерн заместитель (246). Вместо насто- ящего итератора используется его заместитель, память для которого вы- деляется в стеке. Заместитель уничтожает итератор в своем деструкторе, поэтому как только заместитель выходит из области видимости, вместе с ним уничтожается и настоящий итератор. Заместитель гарантирует выполнение надлежащей очистки даже при возникновении исключений.
Это пример применения хорошо известного в C++ принципа «иници- ализации при создании ресурса» [ES90]. В разделе «Пример кода» он проиллюстрирован подробнее;
возможность привилегированного доступа к итераторам. Итератор можно рассматривать как расширение создавшего его агрегата. Итера- тор и агрегат тесно связаны. В C++ такую связь можно выразить, назна- чив итератор
другом своего агрегата. Тогда не нужно определять в агре- гате операции, единственная цель которых — позволить итераторам эффективно выполнить обход.
Однако наличие такого привилегированного доступа может затруднить определение новых способов обхода, так как потребуется изменить интерфейс агрегата, добавив в него нового друга. Для решения этой проблемы класс
Iterator может включать защищенные операции для доступа к важным, но не являющимся открытыми членам агрегата. Под- классы класса Iterator (и
только его подклассы) могут воспользоваться этими защищенными операциями для получения привилегированного доступа к агрегату;
итераторы для составных объектов. Реализовать внешние агрегаты для рекурсивно агрегированных структур (таких, например, которые воз- никают в результате применения паттерна компоновщик (196)) может оказаться затруднительно, поскольку описание положения в структуре иногда охватывает несколько уровней вложенности. Поэтому, чтобы от- следить позицию текущего объекта, внешний итератор должен хранить путь через составной объект
Composite
. Иногда проще воспользовать- ся внутренним итератором. Он
может запомнить текущую позицию, рекурсивно вызывая себя самого, так что путь будет неявно храниться в стеке вызовов.
Если узлы составного объекта
Composite имеют интерфейс для перемеще- ния от узла к его братьям, родителям и потомкам, то итератор курсорного типа может оказаться более достойной альтернативой. Курсору нужно следить только за текущим узлом, а для обхода составного объекта он может положиться на интерфейс этого узла.
Паттерн Iterator (итератор)
309
Составные объекты часто нужно обходить несколькими способами. Са- мые распространенные — это обход в прямом, обратном и внутреннем порядке, а также обход в ширину. Каждый вид обхода может поддержи- ваться отдельным итератором;
пустые итераторы. Пустой итератор
NullIterator представляет собой вырожденный итератор, полезный при обработке граничных условий.
По определению,
NullIterator
всегда считает, что обход завершен, то есть его операция
IsDone неизменно возвращает true
Пустой итератор может упростить обход древовидных структур (напри- мер, объектов
Composite
). В каждой точке обхода у текущего элемента запрашивается итератор для его потомков. Элементы-агрегаты, как обычно, возвращают конкретный итератор, но листовые элементы воз- вращают экземпляр
NullIterator
. Это позволяет реализовать обход всей структуры единообразно.
Пример кода
Рассмотрим простой класс списка
List
, входящего в нашу базовую библио- теку (см. приложение В), и две реализации класса
Iterator
: одну для обхода списка от начала к концу, а другую — от конца к началу (в базовой библио- теке поддерживается только первый способ). Затем будет показано, как пользоваться этими итераторами и как избежать зависимости от конкретной реализации. После этого изменим дизайн, дабы гарантировать корректное удаление итераторов. А в последнем примере мы проиллюстрируем внут- ренний итератор и сравним его с внешним.
Интерфейсы классов List и Iterator. Сначала обсудим ту часть интерфей- са класса
List
, которая имеет отношение к реализации итераторов. Пол- ный интерфейс представлен в приложении В:
template
class List {
public:
List(long size = DEFAULT_LIST_CAPACITY);
long Count() const;
Item& Get(long index) const;
// ...
};
Открытый интерфейс класса
List предоставляет эффективный способ поддержки итераций. Его достаточно для реализации обоих способов обхода. Поэтому нет необходимости предоставлять итераторам привилеги- рованный доступ к внутренней структуре данных. Иными словами, классы
310
Глава 5. Паттерны поведения итераторов не являются друзьями класса
List
. Определим абстрактный класс
Iterator
, в котором будет объявлен интерфейс итератора:
template
class Iterator {
public:
virtual void First() = 0;
virtual void Next() = 0;
virtual bool IsDone() const = 0;
virtual Item CurrentItem() const = 0;
protected:
Iterator();
};
реализации подклассов класса Iterator. Класс
ListIterator является под- классом
Iterator
:
template class ListIterator : public Iterator- { public:
ListIterator(const List- * aList); virtual void First(); virtual void Next(); virtual bool IsDone() const; virtual Item CurrentItem() const; private: const List
- * _list; long _current;
};
Реализация класса
ListIterator достаточно прямолинейна. В нем хра- нится экземпляр
List и индекс текущей позиции в списке
_current
:
template
ListIterator- ::ListIterator (
const List- * aList
) : _list(aList), _current(0) {
}
Операция
First позиционирует итератор на первый элемент списка:
template
void ListIterator- ::First ()
{
_current = 0;
}
Паттерн Iterator (итератор)
311
Операция
Next делает текущим следующий элемент:
template
void ListIterator- ::Next () {
_current++;
}
Операция
IsDone проверяет, относится ли индекс к элементу, находяще- муся в списке:
template
bool ListIterator- ::IsDone () const {
return _current >= _list->Count();
}
Наконец, операция
CurrentItem возвращает элемент, соответствующий текущему индексу. Если итерация уже завершилась, то выдается исклю- чение
IteratorOutOfBounds
:
template
Item ListIterator- ::CurrentItem () const {
if (IsDone()) {
throw IteratorOutOfBounds;
}
return _list->Get(_current);
}
Реализация обратного итератора
ReverseListIterator аналогична рас- смотренной, только его операция
First позиционирует
_current на конец списка, а операция
Next делает текущим предыдущий элемент;
использование итераторов. Предположим, имеется список объектов
Employee
(служащий) и мы хотели бы напечатать информацию обо всех содержащихся в нем служащих. Класс
Employee поддерживает печать с помощью операции
Print
. Для печати списка определим операцию
PrintEmployees
, получающую в аргументе итератор. Она пользуется этим итератором для обхода и вывода содержимого списка:
void PrintEmployees (Iterator& i) {
for (i.First(); !i.IsDone(); i.Next()) {
i.CurrentItem()->Print();
}
}
312
Глава 5. Паттерны поведения
Поскольку у нас есть итераторы для обхода списка от начала к концу и от конца к началу, та же операция может повторно использоваться для вывода списка в обоих направлениях:
List* employees;
// ...
ListIterator forward(employees);
ReverseListIterator backward(employees);
PrintEmployees(forward);
PrintEmployees(backward);
предотвращение привязки к конкретной реализации списка. Рассмотрим, как повлияла бы на код итератора реализация класса
List в виде списка с пропусками. Подкласс
SkipList класса
List должен предоставить ите- ратор
SkipListIterator
, реализующий интерфейс класса
Iterator
. Для эффективной реализации итерации у
SkipListIterator должен быть не только индекс. Но поскольку
SkipListIterator согласуется с интерфей- сом класса
Iterator
, то операцию
PrintEmployees можно использовать и тогда, когда служащие хранятся в списке типа
SkipList
:
SkipList* employees;
// ...
SkipListIterator iterator(employees);
PrintEmployees(iterator);
Такое решение работает, но вообще лучше не привязываться к конкретной реализации списка (например,
SkipList
). Можно рассмотреть абстракт- ный класс
AbstractList ради стандартизации интерфейса списка для различных реализаций. Тогда и
List
, и
SkipList окажутся подклассами
AbstractList
Для поддержки полиморфной итерации класс
AbstractList определяет фабричный метод
CreateIterator
, замещаемый в подклассах, которые возвращают подходящий для себя итератор:
template
class AbstractList {
public:
virtual Iterator- * CreateIterator() const = 0;
// ...
};
Альтернативный вариант — определение общего класса-примеси
Traversable
, в котором определен интерфейс для создания итератора.
Паттерн Iterator (итератор)
313Для поддержки полиморфных итераций агрегированные классы могут являться потомками
Traversable
Класс
List замещает
CreateIterator так, чтобы операция возвращала объект
ListIterator
:
template
Iterator- * List
- ::CreateIterator () const {
return new ListIterator- (this);
}
Теперь можно написать код для вывода списка, который не будет зависеть от конкретного представления списка:
// Известно только то, что объект относится к классу AbstractList
AbstractList* employees;
// ...
Iterator* iterator = employees->CreateIterator();
PrintEmployees(*iterator);
delete iterator;
гарантированное удаление итераторов. Заметим, что
CreateIterator возвращает только что созданный в динамической памяти объект-ите- ратор. Ответственность за его удаление лежит на нас, и если вы забудете это сделать, то возникнет утечка памяти. Чтобы упростить задачу кли- ентам, введем класс
IteratorPtr
, который замещает итератор. Он унич- тожит объект
Iterator при выходе из области видимости.
Объект класса
IteratorPtr всегда создается в стеке
1
. C++ автоматически вызовет его деструктор, который уничтожит реальный итератор. В классе
IteratorPtr операторы operator->
и operator*
перегружены так, что объект этого класса может рассматриваться как указатель на итератор.
Функции класса
IteratorPtr реализуются как встроенные, поэтому они не создают лишних затрат ресурсов:
template
class IteratorPtr {
public:
IteratorPtr(Iterator- * i): _i(i) { }
IteratorPtr() { delete _i; }
Iterator- * operator->() { return _i; }
1
Это можно проверять на этапе компиляции, если объявить операторы new и delete закрытыми. Реализовывать их при этом не надо.
Скачать 6.37 Mb.