|
129
Фильтрующие итераторы
Одна из проблем, связанных с этой идиомой — реализация функции
More()
. Предполагается, что
функция
Next()
внешнего итератора может пропустить объект, возвращаемый внутренней функцией
Next()
. Например, если внутренний итератор возвращает элемент, вставленный после
конструирования внешнего итератора, внешний итератор может захотеть пропустить его. Функция
More()
внутреннего итератора заявляет, что в коллекции еще остались элементы, но при попытке
извлечения они благополучно отвергаются функцией
Next()
. Один из вариантов решения — включить
во внутренний итератор функцию «подсматривания»
Peek()
. Такая функция возвращает то же, что и
Next()
, но не перемещает курсор к следующей позиции. После такого добавления возникает
стопроцентно надежный способ внедрить внутренний итератор во внешний:
class RealExternalIterator : public ExternalIterator {
private:
InternalIterator*
iter;
bool
Accept(Foo*);
//
Фильтрующая функция
public:
RealExternalIterator(Collection* c) : iter(c->Iterator()) {}
virtual bool More()
{
while (iter.More()) {
if
(Accept(iter->Peek()))
return
true;
(void)iter->Next();
//
Отвергнуть и переместиться
}
return
false;
}
virtual Foo* Next() { return iter->Next(); }
};
Каждый раз, когда клиент вызывает
More()
(в том числе и в начале цикла), внутренний итератор
перемещается вперед до тех пор, пока не наткнется на элемент, который удовлетворяет фильтрующей
функции
Accept()
внешнего итератора.
В особо зловредных коллекциях, чтобы реализовать функцию
Peek()
, вам придется сохранять копию
последнего увиденного объекта, однако в большинстве случаев удается легко выполнить
неразрушающее считывание текущей позиции.
Разумеется, возможности этой методики не ограничиваются затенением итераторов. Ее можно
применять в любой ситуации, когда внешний итератор отвергает часть объектов, возвращаемых
внутренним. Например, функция
Accept()
может накладывать ограничения для запроса к базе
данных.
Временная пометка
Один из простейших фокусов для вставки — временная пометка вставок и итераторов. Если пометка
итератора относится к более раннему моменту, чем пометка позиции, итератор пропускает объект в
данной позиции. Временную пометку можно реализовать по-разному: буквально (как количество
тактов таймера); в виде номера хранящегося где-то в статической переменной класса; или в
переменной объекта коллекции.
Удаление обрабатывается аналогично. Если кто-то пытается удалить объект из коллекции, в
действительности объект остается на своем месте до исчезновения всех старых итераторов. Текущие
клиенты и новые итераторы игнорируют его, а итераторы, сконструированные до удаления,
продолжают работать так, словно никто не сообщил им о печальной судьбе объекта. Фактически
объект удаляется лишь тогда, когда он заведомо никому не нужен. Мы столкнулись с одним из
вопросов сборки мусора, о котором пойдет речь в части 4. Удаленные объекты легко уничтожаются в
130
процессе сохранения коллекции на носителе информации или в любой момент при отсутствии
активных итераторов и курсоров.
Иногда объект может находиться сразу как во вставленном, так и в удаленном состоянии; вставка
произошла после того, как итератор был сконструирован, а удаление — до уничтожения итератора. В
сущности, для каждого объекта можно вести целый журнал вставок и удалений, если для этих событий
хватит жизненного срока вашего итератора. Для ведения такого журнала подходят многие различные
структуры данных. Эта побочная тема достаточно интересна, хотя она и не имеет особого отношения к
рассматриваемым идиомам С++. Чтобы обеспечить необходимый уровень инкапсуляции, мы внесем
некоторые изменения в концепцию внутреннего итератора из предыдущего раздела.
Класс временных меток
Следующий класс инкапсулирует временные пометки. Его можно модифицировать, чтобы вместо
последовательного счетчика использовались показания системных часов — для клиента это глубоко
безразлично. Обратите внимание: конструктор копий и оператор
=
не перегружаются. При передаче
Timestamp
по значению создается временный объект
Timestamp
с тем же временем, что и в исходном
объекте, а в случае присваивания одного
Timestamp
другому левосторонний объект приобретает ту же
метку, что и правосторонний.
class Timestamp {
private:
static
int
last_time;
//
Используется для присваивания числа
int
stamp;
public:
Timestamp() : stamp(++last_time) {}
bool operator>(Timestamp ts) { return stamp > ts.stamp; }
bool operator>=(Timestamp ts) { return stamp >= ts.stamp; }
bool operator<(Timestamp ts) { return stamp < ts.stamp; }
bool operator<=(Timestamp ts) { return stamp <= ts.stamp; }
bool operator==(Timestamp ts) { return stamp == ts.stamp; }
bool operator!=(Timestamp ts) { return stamp != ts.stamp; }
};
Внутренний итератор с временной пометкой
Внутренний итератор также необходимо модифицировать, чтобы он учитывал присутствие временных
пометок. Соответствующие фрагменты интерфейса приведены ниже. Подробности реализации в
значительной мере определяются структурами данных коллекции:
class InternalIterator {
public:
bool
More(Timestamp
as_of);
Foo*
Next(Timestamp
as_of);
bool
Peek(Timestamp
as_of);
};
Внутренний итератор будет пропускать объекты, отсутствовавшие в коллекции в указанное время.
Способы внутренней реализации
Один из возможных путей реализации такого поведения — связать с каждой позицией коллекции
вектор временных пометок, в котором самый старый элемент будет соответствовать исходной вставке,
а последующие элементы — поочередно описывать последующие вставки и удаления. Если вектор
содержит нечетное количество элементов, объект в настоящее время находится в коллекции, а первый
элемент вектора относится к моменту последней вставки. Если число элементов четное, объект
отсутствует в коллекции, а первый элемент описывает момент последнего удаления. В процессе
уплотнения коллекции уплотняются и журналы удалений — в них остается лишь момент последней
Do'stlaringiz bilan baham: |
