Объектно-ориентированное проектирование с примерами

       

Классы поддержки


При реализации класса, ответственного за манипуляции с текстовыми строками, мы столкнулись с тем, что возможностей, предоставляемых классами поддержки 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. Классы поддержки.


Содержание раздела