Временная пометка

Один из простейших фокусов для вставки - временная пометка вставок и итераторов. Если пометка итератора относится к более раннему моменту, чем пометка позиции, итератор пропускает объект в данной позиции. Временную пометку можно реализовать по-разному: буквально (как количество тактов таймера); в виде номера хранящегося где-то в статической переменной класса; или в переменной объекта коллекции.

Удаление обрабатывается аналогично. Если кто-то пытается удалить объект из коллекции, в

действительности объект остается на своем месте до исчезновения всех старых итераторов. Текущие

клиенты и новые итераторы игнорируют его, а итераторы, сконструированные до удаления,

продолжают работать так, словно никто не сообщил им о печальной судьбе объекта. Фактически объект удаляется лишь тогда, когда он заведомо никому не нужен. Мы столкнулись с одним из вопросов сборки мусора, о котором пойдет речь в части 4. Удаленные объекты легко уничтожаются в процессе сохранения коллекции на носителе информации или в любой момент при отсутствии активных итераторов и курсоров.

Иногда объект может находиться сразу как во вставленном, так и в удаленном состоянии; вставка произошла после того, как итератор был сконструирован, а удаление - до уничтожения итератора. В сущности, для каждого объекта можно вести целый журнал вставок и удалений, если для этих событий хватит жизненного срока вашего итератора. Для ведения такого журнала подходят многие различные структуры данных. Эта побочная тема достаточно интересна, хотя она и не имеет особого отношения к рассматриваемым идиомам С++. Чтобы обеспечить необходимый уровень инкапсуляции, мы внесем некоторые изменения в концепцию внутреннего итератора из предыдущего раздела.

Класс временных меток

Следующий класс инкапсулирует временные пометки. Его можно модифицировать, чтобы вместо последовательного счетчика использовались показания системных часов - для клиента это глубоко безразлично. Обратите внимание: конструктор копий и оператор = не перегружаются. При передаче 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);

};

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

Способы внутренней реализации

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

Внешний итератор с временной пометкой

Внешний итератор представляет собой тривиальную оболочку для только что описанного внутреннего итератора:

class RealExternalIterator : public ExternalIterator {

private:

InternalIterator* iter;

Timestamp my_time; // Время конструирования 'this'

bool Accept(Foo*); // Фильтрующая функция

public:

RealExternalIterator(Collection* c) : iter(c->Iterator()) {}

virtual bool More() {

while (iter.More(my_time)) {

if (Accept(iter->Peek(my_time)))

return true;

(void)iter->Next(my_time);

}

return false;

}

virtual Foo* Next() { return iter->Next(my_time); }

};

Безаргументный конструктор Timestamp использует для пометки текущее время. Во многих ситуациях функция Accept() всегда возвращает true, и ее можно убрать.