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() , обратно к правильному типу - и горе ему, если он что-нибудь напутает. Шаблоны изобретались именно для этой цели, так что теперь подобный бред уже нельзя оправдать.

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

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

Возврат в исходную точку

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

Ограничение диапазона

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

class Collection { public:

class Iterator {

public:

Iterator(Key* low, Key* high); И т.д.

И т.д.

В этом фрагменте low и high определяют минимальное и максимальное значение ключа соответственно. More() и Next() пропускают элементы, не входящие в заданный диапазон со включением границ. Другие вариации на эту тему - все элементы больше X , все элементы меньше X и исключение границ (< вместо <=).

Откат

Итераторы также могут поддерживать функцию Previous() для отката на одну позицию, если такая возможность обеспечивается самой коллекцией. Эта функция часто используется вместе с функцией Current(), которая возвращает то, что Next() возвратила при последнем вызове.

Курсоры

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

Итератор абстрактного массива

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

SparseArray.h class ArrayCursor; class SparseArray { friend class ArrayCursor; private:

struct Node {

Index index;

Foo* content;

Node* next;

Node(Index i, Foo* c, Node* n) : index(i), content(c), next(n) {}

Node* cells; public:

class Iterator { private:

Node* next; public:

Iterator(Node* first) : next(first) {} bool More() { return next != NULL; ] Foo* Next(Index& index) {

Foo* object = next->content; index = next->index; next = next->next; return object;

Iterator* NonEmpty() { return new SparseArray::Iterator(ce11s); } SparseArray() : cells(NULL) {} ArrayCursor operator[](Index i);

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)

throw ni1 error;

else

return node->current;

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