C++: библиотека программиста

 
123 
• 
Инкапсулируйте 
SparseArray::Iterator
, превратив его в абстрактный базовый класс, а 
затем верните производный класс из скрытой реализации 
NonEmpty()
(эта идея также хорошо 
подходит для классов массива и курсора, поэтому мы разовьем ее в части 3). 
• 
Предоставьте дополнительные итераторы, которые включают как пустые, так и непустые 
ячейки. 
• 
Гарантируйте определенный порядок перебора ячеек. 
• 
Возвращайте из 
Next()
курсор, а не указатель, чтобы клиенты могли изменять содержимое 
ячейки во время перебора. Если это будет сделано, индекс может храниться в курсоре, поэтому 
отпадает необходимость возвращать его в виде отдельного ссылочного аргумента 
Next()
. 
Операторы коллекций 
Многие коллекции индексируются одним или несколькими способами и хорошо соответствуют 
оператору 
[]
, однако в нашем обсуждении курсоров и итераторов нигде не выдвигалось требование 
непременно использовать оператор 
[]
или индексировать коллекцию. Курсор лишь определяет 
некоторую внутреннюю позицию в коллекции; эта позиция не обязана быть чем-то понятным или 
представляющим интерес для пользователя. Если убрать из функции 
Next()
аргумент 
Index&
, 
описанный итератор можно будет с таким же успехом использовать не для массива, а для чего-то 
совершенно иного. 
В большинстве коллекций имеются общие операции. Как и в случае с оператором 
[]
, операторы С++ 
обычно перегружаются для получения более понятного и удобочитаемого кода. Хотя не существует 
повсеместного стандарта операторов коллекций, приведенный ниже перечень поможет вам начать 
ваши собственные разработки. Во всех приведенных операторах сохраняется семантика 
соответствующих операций с числами. 
template  
class Set { 
public: 
Set(); 
// 
Пустое множество 
Set(const 
Set&); 
// 
Дублировать множество 
Set(Element*); 
// 
Множество с одним исходным элементом 
// 
Бинарные операции и операции отношения (множество, множество) 
// 
(также варианты |=, &=, -=, <, <=) 
Set operator|(const Set&) const; 
// Объединение 
// множеств 
Set operator&(const Set&) const; 
// Пересечение 
Set operator-(const Set-) const; 
// Разность 
// множеств 
bool operator>(const Set&) const; // Истинно, если this 
// 
является точным надмножеством аргумента 
bool operator>=(const Set&) const; // Истинно, если this 
// 
является надмножеством аргумента 
bool operator==(const Set&) const; // Истинно, если множества 
// 
имеют одинаковое содержимое 
// 
Бинарные операции и операции отношения (множество, элемент*) 
// 
(также варианты |=, -=) 
Set 
operator|(Element*); // 
Добавить элемент в this 
Set operator-(Element*); 
// this минус элемент 
bool operator>(const Element*) const; // Истинно, если элемент 
// 
принадлежит множеству, но не является единственным 

---

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

---