Объектно-ориентированный анализ и проектирование с примерами приложений на С++

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

Управление памятью

Задача управления памятью возникает для неограниченных форм реализации. В этом случае разработчик библиотеки должен определить политику выделения и освобождения памяти из кучи при осуществлении операций над узлами. Наивный подход просто использует глобальные функции new и delete, что не может обеспечить достаточной производительности системы. Кроме того, на некоторых компьютерных платформах управление памятью крайне усложнено (например, при наличии сегментированного адресного пространства в некоторых операционных системах персональных компьютеров) и требует разработки специальной стратегии, жестко привязанной к определенной операционной среде. Для нашей библиотеки надо четко выделить подсистему управления памятью.

На рис. 9-5 приведен выбранный для данной библиотеки механизм управления памятью [Историческое замечание: потребовалось около четырех итераций архитектуры библиотеки, чтобы придти именно к этому механизму, который - что не удивительно - оказался самым простым. Предыдущие варианты, от которых мы в конце концов отказались, были недостаточно гибкими, трудными для объяснения и стремились навязать особенности реализации безразличным к ней клиентам]. Рассмотрим сценарий, иллюстрацией которого служит данная диаграмма:

• Клиент (aClient) вызывает операцию добавления (append) для экземпляра класса UnboundedQueue (более точно, экземпляра класса, инстанцированного из UnboundedQueue).

• UnboundedQueue, в свою очередь, передает выполнение операции своему элементу rep, который является экземпляром класса unbounded.

• Unbounded, вызывая свою статическую функцию new, выделяет необходимый объем адресного пространства для размещения нового экземпляра Node.

• Этот экземпляр Node, в свою очередь, делегирует ответственность за выделение памяти своему StorageManager, который доступен классу, инстанцируемому из UnboundedQueue (и, следовательно, классам Unbounded и Node), как аргумент шаблона. StorageManager разделяется всеми экземплярами и служит для обеспечения последовательной политики выделения памяти на уровне класса.

 

Рис. 9-5. Механизм управления памятью.

Передавая 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);}

private:

Unmanaged() {} Unmanaged(Unmanaged&) {} void operator=(Unmanaged&) {} void operator==(Unmanaged&) {} void operator!=(Unmanaged&) {}

};

Обратите внимание на идиому, которая применяется, чтобы пользователь не мог копировать, присваивать и сравнивать экземпляры данного класса.