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

 
117 
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 всевозможных индексов в поисках 

---

 118 
какой-то тысячи используемых? Знаю, знаю, ваш RISC-компьютер прогоняет бесконечный цикл за 
семь секунд, но давайте мыслить реально. Если для коллекции существует оптимальный способ 
обращаться только к используемым элементам, мы должны предоставить его в распоряжение клиента. 
Но помните, клиент ничего не знает о внутреннем строении наших коллекций; собственно, именно для 
этого мы изобретали курсоры. Добро пожаловать в удивительный и безумный мир итераторов 
(iterators) — классов, предназначенных для перебора коллекций! Удивительный — поскольку 
итераторы просто решают многие проблемы проектирования. Безумный — поскольку два про-
граммиста C++ ни за что не придут к общему мнению о том, какие же идиомы должны использоваться 
в реализации итераторов. 
Активные итераторы 
Активным называется итератор, который сам перемещается к следующей позиции. 
class Collection { 
public: 
class 
Iterator 
{ 
public: 
bool 
More(); 
Foo* 
Next(); 
}; 
Collection::Iterator* 
Iterate(); // 
Создает итератор 
}; 
Collection::Iterator* iter = collection->Iterator(); 
while (iter.More()) 
f(iter.Next()); 
Как правило, итераторы относятся к конкретным коллекциям; по этой причине они часто объявляются 
в виде вложенных классов. Функция 
Моrе()
возвращает 
true
, если в коллекции имеется следующий 
элемент в порядке перебора, и 
false
— в противном случае. Функция 
Next()
возвращает следующий 
элемент и перемещает итератор к следующей позиции. 
Если вы готовы пойти на дополнительные расходы, связанные с виртуальными функциями, итератор 
также можно реализовать в виде универсального шаблона, работающего с любыми коллекциями. 
template  
class Iterator { 
// Подходит для любых коллекций и типов 
public: 
virtual bool More() = 0; 
virtual Type* Next() = 0; 
}; 
Каждая коллекция может реализовать итератор заново в производном классе, а клиенты по-прежнему 
понятия не имеют о том, как происходит перебор и даже какой класс находится по другую сторону 
забора. К сожалению, в некоторых коллекциях необходимо предоставить средства, не поддерживаемые 
коллекциями других типов (например, ограничение перебираемого диапазона), поэтому такой шаблон 
не настолько универсален, как кажется с первого взгляда. 
Я называю такие итераторы активными, поскольку для выполнения всей основной работы вызываются 
их функции. Ситуация выглядит так, словно кто-то отломил кусок коллекции и вставил его в 
переносимый маленький объект. После конструирования такой объект сам знает, что ему делать 
дальше. 
Пассивные итераторы 
На другом фланге стоят итераторы, которые на самом деле не делают ничего существенного. В них 
хранится служебная информация, занесенная коллекцией, но перемещение и все остальные операции 
выполняются самой коллекцией. Нам понадобятся те же функции — просто из итератора они 

---