Инкапсулируйте 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; Истинно, если элемент принадлежит множеству, но не является единственным

bool operator>=(const Element*) const; Истинно, если элемент

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

является единственным элементом множества

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

Оператор << может использоваться в итераторах как синоним функции Next() .

Оператор >> может использоваться как синоним более длинного оператора Set& operator=(Element*) для сдвига новых элементов в коллекцию.

В обоих идиомах оператор должен перегружаться в форме внешней функции, поскольку в левой части оператора находится Element*, а не Set. Идиома >> выглядит наиболее естественно для коллекций, сохраняющих исходный порядок вставки (например, списков).

Мы вернемся к этой теме в части 3 при обсуждении гомоморфных иерархий классов.

Мудрые курсоры и надежность итераторов

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

void InsertBefore(Foo* f); Вставить f перед курсором

void InsertAfter(Foo* f); Вставить f после курсора

void RemoveAt(); Удалить объект в текущей позиции курсора

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

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

Для примера возьмем связанный список и его итератор.

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

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

Если клиент выполнит операцию вставки до с курсором B или вставки после с курсором A, итератор-владелец A увидит вставленный объект, а итератор-владелец B - нет.

Если клиент удалит объект в позиции B, A никогда не увидит этого объекта, хотя тот находился на споем месте, когда итератор-владелец A начал перебор списка.

Если клиент удалит объект произошло удаление.

позиции A, B успеет увидеть этот объект перед тем, как

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

Если A и B ссылаются на общий элемент списка, а один из них этот элемент удалит - Здравствуй, дебаггер!

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

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

Чтобы обеспечить выполнение вставки до/после и удаления, приходится сдвигать элементы массива над позицией вставки или удалять одни элемент выше или ниже. Если на диаграмме удалить элемент в A и сдвинуть все, что находится выше, на одну позицию вниз, B пропустит позицию. Если вставить элемент в A, B увидит один и тот же объект дважды.

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

1 . Итератор должен перебирать объекты коллекции на момент своего конструирования.

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

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