Пример

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

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

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

class Dictionary {

public:

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

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

~Dictionary();

Dictionary& operator=(const Dictionary&);

void AddEntry(void* key, void* value);

bool At(void* key, void*& value);

void RemoveEntry(void* key);

typedef void* Slot; // Настоящее объявление надежно спрятано

Slot First(); // Возвращает Slot для перебора

// Эквивалент нашей функции "Peek"

bool GetCurrent(Slot slot, void*& key, void*& value);

// Эквивалент нашей функции "Next"

bool GetNext(Slot& slot, void*& key, void*& value);

};

Функция AddEntry() заносит в словарь новое значение с заданным ключом. Если ключ уже

существует для другого значения, значение заменяется новым. Функция At() возвращает логический код, который показывает, присутствует ли ключ в словаре; если присутствует, функция возвращает true и value (значение, соответствующее данному ключу). Функция RemoveEntry() удаляет ключ и связанное с ним значение. Функция First() возвращает пассивный итератор, направленный таким образом, чтобы первый вызов GetNext() возвратил первый элемент словаря. Функция GetCurrent() возвращает пару ключ/значение, находящуюся в текущей позиции Slot. Функция GetNext() возвращает пару ключ/значение и перемещает итератор к следующему элементу. Единственное отличие между этими функциями заключается в перемещении логической позиции после получения объекта. Мы воспользуемся словарем следующим образом: ключом будет объект, хранящийся в нашем наборе, а значением этого ключа - журнал вставок/удалений для данного объекта.

Класс журнала

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

class History {

public:

History(); // Пустой журнал

void Insert(Timestamp); // Вставка в заданное время

void Remove(Timestamp); // Удаление в заданное время

bool Exists(Timestamp); // В заданное время

bool Exists(); // В настоящий момент

};

Функция Exists(Timestamp) возвращает true, если в заданное время последней операцией была

вставка, и false - если последней операцией было удаление или до этого времени вообще не было операций. Безаргументная функция Exists() является синонимом для Exists(Timestamp) с очень большим значением времени - то есть до настоящего момента.

Абстрактный базовый класс

Класс набора делится на две части: абстрактный базовый класс, работающий с void*, и производный параметризованный класс, в который добавлена безопасность типов. Абстрактный базовый класс выглядит так:

// В файле Set.h

class SetBase : private Dictionary {

friend class InternalIterator;

protected:

SetBase(); // Чтобы класс был абстрактным

public:

class Iterator { // Базовый класс внешнего итератора

public:

virtual bool More() = 0;

virtual Type* Next() = 0;

};

};

Iterator* SetBase::ProvideIterator()

{

return new InternalIterator(this);

}

void SetBase::AddObject(void* entry)

{

void* v;

History* h;

if (At(entry, v)) { // Уже есть - проверить время

h = (History*)v;

if (!h->Exists()) // Необходимо выполнить вставку

h->Insert(Timestamp());

}

else { // Еще нет

h = new History;

h->Insert(Timestamp());

AddEntry(entry, h);

}

}

void SetBase::RemoveObject(void* entry)

{

void* v;

History* h;

if (At(entry, v)) { // Уже есть - проверить время

h = (History*)v;

if (h->Exists()) // Необходимо выполнить удаление

h->Remove(Timestamp());

}

}

bool SetBase::Exists(void* entry, Timestamp ts)

{

void* v;

return At(entry, v) && ((History*)v)->Exists(ts);

}

bool SetBase::Exists(void* entry)

{

void* v;

return At(entry, v) && ((History*)v)->Exists();

}

Существуют и другие возможности, которые можно было добавить, но и показанного вполне хватит для демонстрации рассматриваемой методики.

Внутренний итератор

Чтобы реализовать функцию ProvideIterator(), мы создаем как нетипизированный внутренний

итератор, ограниченный файлом .cpp и производный от SetBase::Iterator, так и внешний - в виде параметризованной, безопасной по отношению к типам оболочки. Ниже приведен код внутреннего итератора, объявленного статически (то есть локального по отношению к файлу .cpp). Вся логика временных пометок спрятана в реализации этого класса.

// В файле set.cpp

class InternalIterator : public SetBase::Iterator {

private:

Dictionary* dictionary;

Dictionary::Slot* slot; // Текущая позиция

Timestamp my_time; // Время рождения данного итератора

public:

InternalIterator(Dictionary* d)

: dictionary(d), slot(d->First()), my_time() {}

virtual bool More();

virtual void* Next();

};

bool InternalIterator::More()

{

void* key;

void* h;

if (!dictionary->GetCurrent(slot, key, h))

return false; // позиция выходит за текущие границы

do

if (((History*)h)->Exists(my_time))

return true;

while (dictionary->GetNext(slot, key, h));

return false;

}

void* InternalIterator::Next()

{

void* key;

void* key1;

void* h;

// Предполагается, что клиент сначала вызвал More(),

// поэтому объект GetNext() не устарел

dictionary->GetCurrent(slot, key, h);

dictionary->GetNext(slot, key1, h);

return key;

}

Параметризованная оболочка, безопасная по отношению к типам

Наконец, в приведенном ниже параметризованном классе все становится безопасным по отношению к типам и начинает радовать глаз. Внешний итератор представляет собой параметризованную оболочку для внутреннего итератора, предоставляемого SetBase.

template <class Type>

class Set : private SetBase {

public:

// Безаргументный конструктор - подходит

// Конструктор копий по умолчанию - подходит

// Оператор = по умолчанию - тоже подходит

Set<Type>& operator+=(Type* object)

{ AddObject(object); return *this; }

Set<Type>& operator-=(Type* object)

{ RemoveObject(object); return *this; }

bool operator>=(Type* object)

{ return Exists(object); }

class Iterator {

private:

SetBase::Iterator* iter;

public:

Iterator(Set&* i) : iter(s.ProvideIterator()) {}

bool More() { return iter->More(); }

Type* Next() { return (Type*)(iter->Next()); }

};

Iterator* ProvideIterator()

{ return new Set::Iterator(*this); }

};

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

Set::Iterator iter(aSet);

Такой вариант работает вполне нормально, однако он не соответствует обычной идиоме возвращения итератора из коллекции. Заслуживает внимания и другой вариант: сделать SetBase переменной класса вместо закрытого базового класса. Это позволит вам упрятать SetBase в файл .cpp, чтобы клиент никогда не видел его. Для этого в шаблоне Set придется определить конструкторы и оператор =, но все остальные модификации шаблона будут простыми и незамысловатыми.