|
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;
};
Каждая коллекция может реализовать итератор заново в производном классе, а клиенты по-прежнему
понятия не имеют о том, как происходит перебор и даже какой класс находится по другую сторону
забора. К сожалению, в некоторых коллекциях необходимо предоставить средства, не поддерживаемые
коллекциями других типов (например, ограничение перебираемого диапазона), поэтому такой шаблон
не настолько универсален, как кажется с первого взгляда.
Я называю такие итераторы активными, поскольку для выполнения всей основной работы вызываются
их функции. Ситуация выглядит так, словно кто-то отломил кусок коллекции и вставил его в
переносимый маленький объект. После конструирования такой объект сам знает, что ему делать
дальше.
Пассивные итераторы
На другом фланге стоят итераторы, которые на самом деле не делают ничего существенного. В них
хранится служебная информация, занесенная коллекцией, но перемещение и все остальные операции
выполняются самой коллекцией. Нам понадобятся те же функции — просто из итератора они
Do'stlaringiz bilan baham: |
