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


Семантика времени и памяти - часть 7


template<class Item, unsigned int Size>

unsigned int BoundedQueue<Item, Size>::length() const


{

return rep.length();

}

Отметим, что в описание класса BoundedQueue включены некоторые дополнительные операции, которых нет в его суперклассе. Добавлен селектор available, возвращающий количество свободных элементов в структуре (вычисляется как разность Size - length()). Эта операция не включена в описание базового класса главным образом из-за того, что для неограниченной модели вычисление свободного места не очень осмысленно. Мы также переопределили оператор присваивания и проверку равенства. Как уже отмечалось ранее, это позволяет применить более эффективные алгоритмы по сравнению с базовым классом, так как подклассы лучше знают, что и как делать. Добавленные операторы new и delete определены в защищенной части класса, чтобы лишить клиентов возможности произвольно динамически размещать экземпляры BoundedQueue (что согласуется со статической семантикой этой конкретной формы).

Класс Unbounded имеет, в существенном, тот же протокол, что и класс Bounded, однако его реализация совершенно другая.

template<class Item, class StorageManager>


class Unbounded {
public:
...
protected: Node<Item, StorageManager>* rep;
Node<Item, StorageManager>* last;
unsigned int size;
Node<Item, StorageManager>* cache;
unsigned int cacheIndex;

};

Форма Unbounded реализует очередь как связный список узлов, где узел (Node) реализован следующим образом:

template<class Item, class StorageManager>


class Node {
public: Node(const Item& i,
Node<Item, StorageManager>* previous, Node<Item, StorageManager>* next);
Item item;
Node<Item, StorageManager>* previous;
Node<Item, StorageManager>* next;
static void* operator new(size_t);
static void operator delete(void*, size_t);

};

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

Помня, что классы Bounded и Unbounded имеют практически идентичный внешний протокол, а, значит, их функциональные свойства во многом подобны, можно предположить, что и реализация будет схожей. Однако различие во внутреннем представлении классов приводит к существенно различной пространственно-временной семантике. Манипуляции с узлами связанного списка, например, осуществляются очень быстро, однако процедура нахождения нужного элемента будет занимать время порядка O(n). Поэтому наше представление кэширует последний узел, к которому было обращение, в надежде, что следующее обращение будет либо к этому же узлу, либо к его соседям. Схема же, базирующаяся на массивах, дает низкое быстродействие (в худшем случае порядка O(n/2) если элемент расположен в середине массива) при добавлении или удалении элементов, однако обеспечивает высокую скорость поиска (порядка O(1)).




Начало  Назад  Вперед



Книжный магазин