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

Некоторые классы итераторов содержат функцию, которая возвращает итератор к началу перебора. Я называю ее функцией возврата, 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;

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

Инкапсулируйте SparseArray::Iterator, превратив его в абстрактный базовый класс, а затем верните производный класс из скрытой реализации NonEmpty() (эта идея также хорошо подходит для классов массива и курсора, поэтому мы разовьем ее в части 3).

Предоставьте дополнительные итераторы, которые включают как пустые, так и непустые ячейки.

Гарантируйте определенный порядок перебора ячеек.

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

Операторы коллекций

Многие коллекции индексируются одним или несколькими способами и хорошо соответствуют оператору [] , однако в нашем обсуждении курсоров и итераторов нигде не выдвигалось требование непременно использовать оператор [] или индексировать коллекцию. Курсор лишь определяет некоторую внутреннюю позицию в коллекции; эта позиция не обязана быть чем-то понятным или представляющим интерес для пользователя. Если убрать из функции Next() аргумент Index&, описанный итератор можно будет с таким же успехом использовать не для массива, а для чего-то совершенно иного.

В большинстве коллекций имеются общие операции. Как и в случае с оператором [] , операторы С++ обычно перегружаются для получения более понятного и удобочитаемого кода. Хотя не существует повсеместного стандарта операторов коллекций, приведенный ниже перечень поможет вам начать ваши собственные разработки. Во всех приведенных операторах сохраняется семантика соответствующих операций с числами.

template <c1ass Element>

class Set {

public:

Set(); Пустое множество

Set(const Set<Element>&); Дублировать множество Set(Element*); Множество с одним исходным элементом

Бинарные операции и операции отношения (множество, множество) (также варианты =, &=, -=, <, <=)

Set<Element> operator(const Set<Element>&) const; Объединение

множеств

Set<Element> operator&(const Set<Element>&) const; Пересечение

Set<Element> operator-(const Set<Element>-) const; Разность

множеств

bool operator>(const Set<Element>&) const; Истинно, если this

является точным надмножеством аргумента bool operator>=(const Set<Element>&) const; Истинно, если this

является надмножеством аргумента bool operator==(const Set<Element>&) const; Истинно, если множества имеют одинаковое содержимое

Бинарные операции и операции отношения (множество, элемент*) (также варианты =, -=)

Set<Element> operator(Element*); Добавить элемент в this

Set<Element> operator-(Element*); this минус элемент

bool operator>(const Element*) const; Истинно, если элемент принадлежит множеству, но не является единственным