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

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

---