Классы поддержки
При реализации класса, ответственного за манипуляции с текстовыми строками, мы столкнулись с тем, что возможностей, предоставляемых классами поддержки Bounded и Unbounded, явно недостаточно. Ограниченная форма, в частности, оказывается неэффективной для работы со строками с точки зрения памяти, так как мы должны инстанцировать эту форму в расчете на максимально возможную строку, и следовательно понапрасну расходовать память на более коротких строках. Неограниченная форма, в свою очередь, неэффективна с точки зрения быстродействия: поиск элемента в строке может потребовать последовательного перебора всех элементов связного списка. По этим причинам нам пришлось разработать третий, "динамический" вариант:
Структура хранится в "куче" в виде массива, длина которого может уменьшаться или увеличиваться.
Соответствующий класс поддержки Dynamic представляет собой промежуточный вариант по отношению к ограниченному и неограниченному классам, обеспечивающий быстродействие ограниченной формы (возможно прямое индексирование элементов) и эффективность хранения данных, присущую неограниченной форме (память выделяется только под реально существующие элементы).
Ввиду того, что протокол данного класса идентичен протоколу классов Bounded и Unbounded, добавление к библиотеке нового механизма не составит большого труда. Мы должны создать по три новых класса для каждого семейства (например, DynamicString, GuardedDynamicString и SynchronizedDynamicString). Таким образом, мы вводим следующий класс поддержки:
template<class Item, class StorageManager>
class Dynamic {
public: Dynamic(unsigned int chunkSize);
protected: Item* rep;
unsigned int size;
unsigned int totalChunks;
unsigned int chunkSize;
unsigned int start;
unsigned int stop;
void resize(unsigned int currentLength,
unsigned int newLength, int preserve - 1);
unsigned int expandLeft(unsigned int from);
unsigned int expandRight(unsigned int from);
void shrinkLeft(unsigned int from);
void shrinkRight(unsigned int from);
};
Последовательности разбиваются на блоки в соответствии с аргументом конструктора chunkSize. Таким образом, клиент может регулировать размер будущего объекта.
Из интерфейса видно, что класс Dynamic имеет много общего с классами Bounded и Unbounded. Отличия в реализации трех типов классов каждого семейства будут минимальны.
Займемся теперь классом ассоциативных массивов. Его реализация потребует новой переработки ограниченной, динамической и неограниченной форм. В частности, поиск элемента в ассоциативном массиве требует слишком много времени, если его приходится вести перебором всех элементов. Но производительность можно значительно увеличить, используя открытые хеш-таблицы.
Абстракция открытой хеш-таблицы проста. Таблица представляет собой массив последовательностей, которые называются клетками. Помещая в таблицу новый элемент, мы сначала генерируем хеш-код по этому элементу, а затем используем код для выбора клетки, куда будет помещен элемент. Таким образом, открытая хеш-таблица делит длинную последовательность на несколько более коротких, что значительно ускоряет поиск.
Соответствующую абстракцию можно определить следующим образом:
template<class Item, class Value, unsigned int Buckets, class Container>
class Table {
public: Table(unsigned int (*hash)(const Item&));
void setHashFunction(unsigned int (*hash)(const Item&));
void clear();
int bind(const Item&, const Value&);
int rebind(const Item&, const Value&);
int unbind(const Item&);
Container* bucket(unsigned int bucket);
unsigned int extent() const;
int isBound(const Item&) const;
const Value* valueOf(const Item&) const;
const Container *const bucket(unsigned int bucket) const;
protected: Container rep[Buckets];
};
Использование класса Container в качестве аргумента шаблона позволяет применить абстракцию хеш-таблицы вне зависимости от типа конкретной последовательности.
Рассмотрим в качестве примера ( сильно упрощенное) объявление неограниченного ассоциативного массива, построенного на базе классов Table и Unbounded:
template<class Item, class Value, unsigned int Buckets,
class StorageManager>
class UnboundedMap : public Map<Item, Value> {
public: UnboundedMap();
virtual int bind(const Item&, const Value&);
virtual int rebind(const Item&, const Value&);
virtual int unbind(const Item&);
protected: Table<Item, Value, Buckets, Unbounded<Pair<Item, Value>, StorageManager>> rep;
};
В данном случае мы истанцируем класс Table контейнером unbounded. Рис. 9-12 иллюстрирует схему взаимодействия этих классов.
В качестве свидетельства общей применимости этой абстракции мы можем использовать класс Table при реализации классов множеств и наборов.
Рис. 9-12. Классы поддержки.
