Частные копии коллекций

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

class Iterator { private:

Collection collection;

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

Iterator(Co11ection& c)

: collection(c), 1ocation(co11ection.First()) {} bool More();

Foo* Next();

Конструктор итератора с помощью конструктора копий класса Collection создает вторую частную копию коллекции. Перед вами - один из редких случаев, когда действительно имеет значение тот факт, что переменные класса конструируются в порядке их перечисления; объект collection должен быть сконструирован раньше объекта location, в противном случае вам предстоят мучения с отладкой функции First() .

Коллекции объектов или коллекции указателей?

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

template <c1ass Type, int Size>

class Array {

private:

int Size; Количество объектов Type

Type e1ements[size]; Объекты (внутренние) и т.д.

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

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

Упрощение частной коллекции

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

class SimpleCollection; Упрощенный вариант

class ComplexCollection {

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 посредством закрытого наследования. Как и в большинстве проблем дизайна С++, закрытое наследование проще реализуется, а делегирование переменной класса оказывается более универсальным. Например, вы можете на полпути заменить переменную, чтобы сцепить несколько внутренних итераторов в одном внешнем.