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

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

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

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

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

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

class ExternalIterator {

private:

SimpleCollection collection;

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

public:

ExternalIterator(ComplexCollection* c)

{

InternalIterator* iter = c->Iterator();

while (c->More())

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

delete iter;

my_iter = collection->Iterator();

}

bool More() { return my_iter->More(); }

bool Next() { return my_iter->Next(); }

};

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

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

Термин «устойчивый» (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

(...);

Collection: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(Collection* c) : iter(c->Iterator()) {}

virtual bool More()

{

while (iter.More()) {

if (Accept(iter->Peek()))

return true;

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