public:

operator Simp1eCo11ection*();

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

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

class Iterator { private:

SimpleCollection* collecti on;

Cursor location; Текущая позиция в копии

public:

Iterator(Si mpleCollection* c)

: collection(c), 1ocation(co11ection->First()) {} bool More(); bool Next();

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

Вернемся к итераторам, работающим с исходной коллекцией. Существуют два типа итераторов: относящиеся к внутренней реализации коллекции (например, для приведенного выше класса SimpleCollection) и открытые внешнему миру. Они называются внутренними (internal iterator) и внешними (external iterator) итераторами соответственно.

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

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

Временные внутренние итераторы

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

class ExternalIterator { private:

SimpleCollection collection;

SimpleIterator* my iter; Возвращается коллекцией

public:

ExternalIte rator(Comp1exCo11ection* c) {

InternalIterator* iter = c->Iterator();

while (c->More())

collection += *(c->Next()); delete iter;

my iter = co11ection->Iterator();

bool More() { return my iter->More(); } bool Next() { return my iter->Next() ; }

ComplexColl ection предоставляет внутренний итератор, который существует ровно столько, сколько необходимо для создания копии. SimpleCollection возвращает итератор, используемый для реализации функции More() и Next() внешнего итератора. Конечно, все могло бы выглядеть намного элегантнее, если бы у SimpleCollection был конструктор с аргументом ComplexColl ection или у ComplexCollection - операторная функция преобразования operator Simp1eCo11ection(). Но даже при их отсутствии класс итератора обеспечивает весь необходимый уровень инкапсуляции.

Устойчивые внутренние итераторы

Термин «устойчивый» (persistent) означает, что внутренний итератор существует до тех пор, пока существует внешний итератор (my iter в предыдущем примере). Внутренний итератор может быть переменной класса внешнего итератора, как было показано, а при достаточной осторожности его можно создать как производный класс посредством закрытого наследования. Вариант с закрытым наследованием может выглядеть так:

В файле .h class Collection { public:

class ExternalIterator { public:

virtual bool More() = 0; virtual Foo* Next() = 0;

ExternalIterator* Iterator();

В файле .cpp

Настоящий класс, возвращаемый клиентам class RealExternalIterator

: public ExternalIterator, private InternalIterator

(...);

Co11ection:ExternalIterator* Collection::Iterator()

return new RealExternalIterator(this);

Обладающий локальной областью действия ExternalIterator обеспечивает абстрактный интерфейс, предоставляемый клиенту. Настоящий возвращаемый класс, RealExternalIterator, порожден от Collection: :ExternalIterator посредством открытого наследования, а также (о чем клиент не подозревает) - от SimpleIterator посредством закрытого наследования. Как и в большинстве проблем дизайна С++, закрытое наследование проще реализуется, а делегирование переменной класса оказывается более универсальным. Например, вы можете на полпути заменить переменную, чтобы сцепить несколько внутренних итераторов в одном внешнем.

Фильтрующие итераторы

Одна из проблем, связанных с этой идиомой - реализация функции More(). Предполагается, что функция Next() внешнего итератора может пропустить объект, возвращаемый внутренней функцией Next(). Например, если внутренний итератор возвращает элемент, вставленный после конструирования внешнего итератора, внешний итератор может захотеть пропустить его. Функция More() внутреннего итератора заявляет, что в коллекции еще остались элементы, но при попытке извлечения они благополучно отвергаются функцией Next(). Один из вариантов решения - включить во внутренний итератор функцию «подсматривания» Peek(). Такая функция возвращает то же, что и Next(), но не перемещает курсор к следующей позиции. После такого добавления возникает стопроцентно надежный способ внедрить внутренний итератор во внешний:

class RealExternalIterator : public ExternalIterator { private:

InternalIterator* iter;

bool Accept(Foo*); Фильтрующая функция

public:

RealExternalIterator(Co11ection* c) : iter(c->Iterator()) {} virtual bool More()

while (iter.MoreO) {

if (Accept(iter->Peek())) return true;

(void)iter->Next(); Отвергнуть и переместиться

return false;

virtual Foo* Next() { return iter->Next(); }

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

В особо зловредных коллекциях, чтобы реализовать функцию Peek(), вам придется сохранять копию последнего увиденного объекта, однако в большинстве случаев удается легко выполнить неразрушающее считывание текущей позиции.

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

Временная пометка

Один из простейших фокусов для вставки - временная пометка вставок и итераторов. Если пометка итератора относится к более раннему моменту, чем пометка позиции, итератор пропускает объект в данной позиции. Временную пометку можно реализовать по-разному: буквально (как количество тактов таймера); в виде номера хранящегося где-то в статической переменной класса; или в переменной объекта коллекции.

Удаление обрабатывается аналогично. Если кто-то пытается удалить объект из коллекции, в действительности объект остается на своем месте до исчезновения всех старых итераторов. Текущие клиенты и новые итераторы игнорируют его, а итераторы, сконструированные до удаления, продолжают работать так, словно никто не сообщил им о печальной судьбе объекта. Фактически объект удаляется лишь тогда, когда он заведомо никому не нужен. Мы столкнулись с одним из вопросов сборки мусора, о котором пойдет речь в части 4. Удаленные объекты легко уничтожаются в