class ArrayCursor { friend class SparseArray; private:

SparseArray& array;

Index index;

SparseArray::Node* node; ArrayCursor(SparseArray& arr, Index i)

: array(arr), index(i), node(NULL) {} ArrayCursor(SparseArray& arr, SparseArray::Node* n)

: array(arr), node(n), index(n->index) {}

public:

ArrayCursor& operator=(Foo* foo);

operator Foo*() { return node != NULL ? node->content : NULL; }; Foo* operator->()

if (node = NULL)

Инициировать исключение

else

return node->contents;

Foo* foo = array[Index(17, 29)]; Работает

array[Index(17, 29)]->MemberOfFoo(); Тоже работает

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

Что-то знакомое

Взгляните еще раз на класс ArrayCursor. Он представляет собой объект, который косвенно ссылается на Foo, имеет операторную функцию operator Foo*() и перегруженный оператор ->, позволяющий обращаться к членам Foo через курсор. Выглядит знакомо? Так и должно быть. Курсоры на самом деле представляют собой следующее поколение умных указателей. Все, что говорилось об умных указателях в трех последних главах, легко распространяется и на курсоры. И наоборот, изучение курсорологии помогает расширить некоторые концепции умных указателей. Перегружая оператор = для умного указателя, вы сумеете избежать многих неприятных проблем. Например, вспомните концепцию кэширующего указателя, который в последний момент считывал объект с диска в операторе ->. Подобная перегрузка оператора присваивания нередко очищает программу и избавляет код от ненужных технических деталей. Другой полезный прием - привязка умного указателя к некоторой структуре данных (подобно тому, как ArrayCursor привязывался к классу SparseArray). Такое гармоничное объединение идей проектирования является хорошим признаком - мы приближаемся к неуловимой высшей истине C++. Чем более передовыми идиомами вы пользуетесь, тем больше возникает сходства.

Итераторы

Итак, мы можем работать с любым отдельным элементом коллекции. Как насчет того, чтобы перебрать все элементы? Тупой перебор в цикле for не поможет:

for (int i = 0; i < ... чего?

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

какой-то тысячи используемых? Знаю, знаю, ваш 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();