Фильтрующие итераторы

Одна из проблем, связанных с этой идиомой - реализация функции More() . Предполагается, что функция Next() внешнего итератора может пропустить объект, возвращаемый внутренней функцией Next(). Например, если внутренний итератор возвращает элемент, вставленный после конструирования внешнего итератора, внешний итератор может захотеть пропустить его. Функция More() внутреннего итератора заявляет, что в коллекции еще остались элементы, но при попытке извлечения они благополучно отвергаются функцией Next(). Один из вариантов решения - включить во внутренний итератор функцию подсматривания Peek(). Такая функция возвращает то же, что и Next() , но не перемещает курсор к следующей позиции. После такого добавления возникает стопроцентно надежный способ внедрить внутренний итератор во внешний:

class RealExternalIterator : public ExternalIterator { private:

InternalIterator* iter;

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

public:

RealExternalIterator(Co11ection* c) : iter(c->Iterator()) {} virtual bool More()

while (iter.MoreO) {

if (Accept(iter->Peek())) return true;

(void)iter->Next(); Отвергнуть и переместиться

return false;

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

Каждый раз, когда клиент вызывает More() (в том числе и в начале цикла), внутренний итератор перемещается вперед до тех пор, пока не наткнется на элемент, который удовлетворяет фильтрующей функции Accept() внешнего итератора.

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

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

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

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

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

процессе сохранения коллекции на носителе информации или в любой момент при отсутствии активных итераторов и курсоров.

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

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

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

class Timestamp { private:

static int 1ast time; Используется для присваивания числа int stamp; public:

Timestamp() : stamp(++1ast 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(Co11ection* 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, и ее можно убрать.

Пример

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

Ненадежный коммерческий класс словаря

В реальном мире редко приходится начинать с пустого места. Обычно в вашем распоряжении уже имеются готовые классы коллекций. Даже если они работают не совсем так, как хочется, по крайней мере они избавят вас от нудного переписывания любимых глав из книг Кнута при реализации базовых структур данных. В том же реальном мире эти классы обычно не обращают особого внимания на проблему надежности итераторов, так что наш пример никак не назовешь абстрактным. Для пущего реализма мы будем считать, что коллекция представляет собой словарь, который индексирует значение типа void* и возвращает void* в качестве ключа. Имеется пассивный итератор Slot, реальная структура которого спрятана глубоко внутри класса словаря. Открытый интерфейс выглядит так:

class Dictionary { public:

Dictionary(); Создает пустой словарь

Dictionary(const Dictionary&); Конструктор копий ~Dictionary();

Dictionary& operator=(const Dictionary&); void AddEntry(void* key, void* value);