какой-то тысячи используемых? Знаю, знаю, ваш RISC-компьютер прогоняет бесконечный цикл за семь секунд, но давайте мыслить реально. Если для коллекции существует оптимальный способ обращаться только к используемым элементам, мы должны предоставить его в распоряжение клиента. Но помните, клиент ничего не знает о внутреннем строении наших коллекций; собственно, именно для этого мы изобретали курсоры. Добро пожаловать в удивительный и безумный мир итераторов (iterators) - классов, предназначенных для перебора коллекций! Удивительный - поскольку итераторы просто решают многие проблемы проектирования. Безумный - поскольку два программиста C++ ни за что не придут к общему мнению о том, какие же идиомы должны использоваться в реализации итераторов.

Активные итераторы

Активным называется итератор, который сам перемещается к следующей позиции. class Collection { public:

class Iterator { public:

bool More(); Foo* Next();

Co11ection::Iterator* Iterate(); Создает итератор

Co11ection::Iterator* iter = co11ection->Iterator(); while (iter.MoreO) f(iter.Next());

Как правило, итераторы относятся к конкретным коллекциям; по этой причине они часто объявляются в виде вложенных классов. Функция Моrе() возвращает true, если в коллекции имеется следующий элемент в порядке перебора, и false - в противном случае. Функция Next() возвращает следующий элемент и перемещает итератор к следующей позиции.

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

template <c1ass Type>

class Iterator { Подходит для любых коллекций и типов public:

virtual bool More() = 0;

virtual Type* Next() = 0;

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

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

Пассивные итераторы

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

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

class Iterator; class Collection { public:

Iterator* Iterate(); Возвращает пассивный итератор bool More(Iterator*); Foo* Next(Iterator*);

Iterator* iter = co11ection->Iterate(); while (co11ection->More(iter)) f(co11ection->Next(iter));

Такие итераторы называются пассивными, поскольку сами по себе они не выполняют никаких действий и предназначены лишь для хранения служебной информации.

Что лучше?

Выбор между активными и пассивными итераторами в основном зависит от стиля, но я предпочитаю активные итераторы по нескольким причинам:

• Законченный класс итератора проще использовать повторно, чем пару функций большого класса.

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

• Пассивные итераторы не имеют открытого интерфейса, однако клиентские объекты видят их через адреса. Это выглядит довольно странно.

• При равенстве всех остальных показателей я обычно предпочитаю активные итераторы, поскольку они обеспечивают лучшую инкапсуляцию.

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

Убогие, но распространенные варианты

Вряд ли вы встретите в коммерческих библиотеках классов итераторы именно в таком виде. У каждого находится свой подход к этой теме. Ниже перечислены некоторые варианты, которые часто встречаются в странствиях по С++, с краткими комментариями по поводу их достоинств и недостатков.

Мономорфные активные итераторы вне области действия

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

class Collection { ... }; class CollectionIterator { private:

Collection* coll; public:

Co11ectionIterator(Co11ection* coll); bool More(); Foo* Next();

CollectionIterator iter(collection); Создать итератор

while (iter.MoreO) f(iter.Next());

Просто удивительно, что всего несколько строк программы порождает столько проблем:

• При использовании класса, производного от Collection, каждый клиент должен знать, какие новые классы итераторов должны использоваться вместо старого CollectionIterator.

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

• Занесение итераторов в стек противоречит некоторым стратегиям многопоточности, рассматриваемым в следующей главе.

• Многократное использование такого кода - задача мерзкая.

Учитывая все это, будет намного, намного лучше попросить класс коллекции: «Пожалуйста, сэр, сделайте мне итератор» вместо того, чтобы самому создавать его в стеке. Невзирая на все проблемы, этот тип итераторов часто встречается в коммерческих библиотеках классов.

Пассивные итераторы типа void*

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

typedef void* AprilInParis; class Collection { public:

AprilInParis Iterate(); Возвращает загримированный void* bool More(AprilInParis&); Foo* Next(AprilInParis&);

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

Нетипизированные значения функции Next()

Многие классы итераторов пишутся в обобщенной форме для типа void* или какого-то абстрактного базового класса. Клиент должен сам приводить значение, возвращаемое функцией Next(), обратно к правильному типу - и горе ему, если он что-нибудь напутает. Шаблоны изобретались именно для этой цели, так что теперь подобный бред уже нельзя оправдать.

Лучшие варианты

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