Bounded<Item, Size> rep; virtual void purge(); virtual void add(const Item&); virtual unsigned int cardinality() const; virtual const Item& itemAt(unsigned int) const; static void* operator new (size_t); static void operator delete(void*, size_t);
};
Основная задача данного класса - завершить протокол, определенный в базовом классе. Часто это означает немного больше, чем простая передача обязанности классу более низкого уровня Bounded, как предлагается в следующей реализации:
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 имеют практически идентичный внешний протокол, а, значит, их функциональные свойства во многом подобны, можно предположить, что и реализация будет схожей. Однако различие во внутреннем представлении классов приводит к существенно различной пространственно-временной семантике. Манипуляции с узлами связанного списка, например, осуществляются очень быстро, однако процедура нахождения нужного элемента будет занимать время порядка
Управление памятью
Задача управления памятью возникает для неограниченных форм реализации. В этом случае разработчик библиотеки должен определить политику выделения и освобождения памяти из кучи при осуществлении операций над узлами. Наивный подход просто использует глобальные функции new и delete, что не может обеспечить достаточной производительности системы. Кроме того, на некоторых компьютерных платформах управление памятью крайне усложнено (например, при наличии сегментированного адресного пространства в некоторых операционных системах персональных компьютеров) и требует разработки специальной стратегии, жестко привязанной к определенной операционной среде. Для нашей библиотеки надо четко выделить подсистему управления памятью.
На рис. 9-5 приведен выбранный для данной библиотеки механизм управления памятью [Историческое замечание: потребовалось около четырех итераций архитектуры библиотеки, чтобы придти именно к этому механизму, который - что не удивительно - оказался самым простым. Предыдущие варианты, от которых мы в конце концов отказались, были недостаточно гибкими, трудными для объяснения и стремились навязать особенности реализации безразличным к ней клиентам]. Рассмотрим сценарий, иллюстрацией которого служит данная диаграмма:
• Клиент (aClient) вызывает операцию добавления (append) для экземпляра класса UnboundedQueue (более точно, экземпляра класса, инстанцированного из UnboundedQueue).
• UnboundedQueue, в свою очередь, передает выполнение операции своему элементу rep, который является экземпляром класса unbounded.
• Unbounded, вызывая свою статическую функцию new, выделяет необходимый объем адресного пространства для размещения нового экземпляра Node.
• Этот экземпляр Node, в свою очередь, делегирует ответственность за выделение памяти своему StorageManager, который доступен классу, инстанцируемому из UnboundedQueue (и, следовательно, классам Unbounded и Node), как аргумент шаблона. StorageManager разделяется всеми экземплярами и служит для обеспечения последовательной политики выделения памяти на уровне класса.
Передавая StorageManager в качестве аргумента всем неограниченным структурам, мы четко отделяем политику организации доступа к памяти от ее реализации и даем пользователям возможность добавлять в программу свои собственные концепции управления памятью, не меняя при этом содержания библиотеки. Это классический пример того, как можно добиться открытости программной системы через инстанцирование, не прибегая к наследованию.
Единственное требование, предъявляемое к вариантам StorageManager, заключается в необходимости сохранения единого протокола. В частности, все они должны содержать открытые функции-члены allocate и deallocate, предназначенные соответственно для выделения и освобождения памяти. Рассмотрим в качестве примера простейший вариант такого класса:
class Unmanaged { public:
static void* allocate(size_t s) {return ::operator new(s);} static void deallocate(void* p, size_t) {::operator delete(p);}
