Семантика времени и памяти
Из пяти основных принципов строения библиотеки базовых классов, возможно, наиболее важен механизм, обеспечивающий клиента альтернативной простанственно-временной семантикой внутри каждого семейства классов.
Рассмотрим тот спектр требований, который должен учитываться при разработке библиотеки общего назначения. На рабочей станции, обладающей большим виртуальным адресным пространством, пользователь скорее всего будет расточать память ради более высокого быстродействия. С другой стороны, в некоторых встроенных системах, таких, как спутник или автомобильный мотор, ресурсы памяти часто ограничены, и разработчик вынужден выбирать в качестве рабочих те абстракции, которые используют меньше памяти (например, выделяя место под данные в стеке, а не в "куче"). Ранее мы различили эти две возможности как ограниченную и неограниченную формы соответственно.
Неограниченные формы применимы в тех случаях, когда размер структуры не может быть предсказан, а выделение и утилизация памяти из кучи не приводит ни к потере времени, ни к снижению надежности (как это бывает в некоторых приложениях, критичных по времени) [Некоторые требования к системе могут запретить использование динамически распределяемой памяти. Рассмотрим сердечный импульсный регулятор и возможные фатальные результаты, которые может вызвать сборщик мусора, "проснувшийся" в неподходящий момент. Есть системы с длительным рабочим циклом: в них даже минимальная утечка памяти может дать серьезный кумулятивный эффект; вынужденная перезагрузка системы из-за недостатка памяти может привести к неприемлемой потере функциональности]. Ограниченные формы лучше подходят для работы с небольшими структурами, размер которых достаточно хорошо предсказуем. Учтем также, что динамическое выделение памяти менее терпимо к ошибкам программиста.
Таким образом, все структуры данной библиотеки должны присутствовать в альтернативных вариантах; поэтому нам придется создать два низкоуровневых класса поддержки, Unbounded (неограниченный) и Bounded (ограниченный).
Задачей класса unbounded является поддержка быстро работающего связного списка, элементы которого размещаются в памяти, выделенной из "кучи". Это представление эффективно по скорости, но не по памяти, так как каждый элемент списка должен, кроме своего значения, дополнительно содержать указатель на следующий элемент того же списка. Задача класса Bounded состоит в организации структур на базе массива, что эффективно с точки зрения памяти, но добиться большой производительности трудно, так как, например, при добавлении элемента в середину списка приходится последовательно копировать все последующие (или предыдущие) элементы массива.
Как видно из рис. 9-4, для включения этих классов нижнего уровня в иерархию основных абстракций мы используем агрегацию. Более точно, диаграмма показывает, что мы используем физическое включение по значению с защищенным Доступом, которое означает, что это низкоуровневое представление доступно только подклассам и друзьям. На раннем этапе проектирования мы хотели воспользоваться примесями и сделать unbounded и Bounded защищенными суперклассами.
Рис. 9-4. Ограниченная и неограниченная формы.
Мы в конце концов отказались от такого варианта, так как он достаточно труден для понимания, и к тому же нарушает лакмусов принцип наследования: BoundedQueue, по крайней мере, с точки зрения типа данных, не является частным случаем класса Bounded.
Отметим также, что работа с двумя формами требует присутствия второго аргумента в их шаблоне. Для ограниченной формы - это беззнаковое целое число Size, обозначающее статический размер объекта. Для неограниченной формы - это класс StorageManager, ответственный за политику размещения в памяти. Мы рассмотрим его работу в следующем разделе.
Протокол обоих классов поддержки должен быть, с одной стороны, достаточным для обеспечения работы конкретных подклассов, а с другой стороны, универсальным, чтобы гарантировать выполнение ответственности всех других структур в библиотеке. В целях компактности и быстродействия мы не включили в описание классов Unbounded и Bounded ни одной виртуальной функции.
По этой причине мы не можем объединить их одним суперклассом, несмотря на то, что они имеют общий протокол; кроме того, мы не можем надлежащим образом построить на их базе иерархию подклассов. В данном случае гибкость приносится в жертву производительности. По той же причине мы решаем сделать ряд функций встроенными; хорошими кандидатами на это обычно являются селекторы, особенно те, которые возвращают простые переменные.
Рассмотрим, например, описание класса Bounded:
template<class Item, unsigned int Size>
class Bounded {
public: Bounded();
Bounded(const Bounded<Item, Size>&);
~Bounded();
Bounded<Item, Size>& operator=(const Bounded<Item, Size>&);
int operator==(const Bounded<Item, Size>&) const;
int operator!=(const Bounded<Item, Size>&) const;
const Item& operator[](unsigned int index) const;
Item& operator[](unsigned int index);
void clear();
void insert(const Item&);
void insert(const Item&, unsigned int before);
void append(const Item&);
void append(const Item&, unsigned int after);
void remove(unsigned int at);
void replace(unsigned int at, const Item&);
unsigned int available() const;
unsigned int length() const;
const Item& first() const;
const Item& last() const;
const Item& itemAt(unsigned int) const;
Item& itemAt(unsigned int);
int location(const Item&) const;
static void* operator new(size_t);
static void operator delete(void*, size_t);
protected: Item rep[Size];
unsigned int start;
unsigned int stop;
unsigned int expandLeft(unsigned int from);
unsigned int expandRight(unsigned int from);
void shrinkLeft(unsigned int from);
void shrinkRight(unsigned int from);
};
Объявление класса следует схеме, описанной ранее. Каким образом мы пришли именно к такому решению? Если честно, то на 80% это результат чистого проектирования классов, которое рассматривалось в главе 6. Затем интерфейс дорабатывался в соответствии с результатами пробного использования класса совместно с рядом основных абстракций системы.
Основная трудность при эволюции состояла в идентификации подходящих примитивных операций, которые должны использоваться при работе с набором различных структур.
Сердцем класса является защищенный массив rep постоянного размера Size. Рассмотрим следующее объявление:
Bounded<char, 100U> charSequence;
При создании соответствующего объекта в стеке образуется массив постоянного размера из 100 элементов. Защищенные члены класса start и stop (индексы в этом массиве) указывают начало и конец последовательности. Тем самым мы использовали кольцевой буфер данных. Добавление нового элемента в начало или в конец последовательности не потребует перемещения данных, а добавление элемента в середину массива приводит к копированию не более чем половины его элементов.
Проектирование ограниченного и неограниченного классов поддержки затрагивает также некоторые тонкие вопросы, касающиеся использования ссылок (мы упоминали о них в главе 3). Нам придется еще раз коснуться этой темы, и не только потому, что она имеет прямое отношение к разработке интерфейса параметризованных классов, но и потому, что данные вопросы сами по себе представляют значительный интерес для проектировщика любой более или менее нетривиальной библиотеки.
В C++ ссылки являются механизмом, позволяющим улучшить производительность. Однако пользоваться ими следует предельно осторожно во избежание нарушения корректного доступа к оперативной памяти. В данной библиотеке мы используем ссылки для ускорения работы при передаче аргументов функциям-членам. Это касается, например, класса Bounded, где подобным образом передаются ссылки на объекты классов Bounded и Item. Ссылки, как правило, не используются для передачи примитивных объектов (например, целых чисел в описании функции-члена itemAt) - программа от этого будет работать только медленнее. Кроме того, семантика языка C++ порождает некоторые опасности при манипулировании с временными объектами.
Все наши структуры, однако, содержат в качестве элементов не ссылки, а значения, что исключает возникновение ссылок на временные объекты в стеке при работе программы.
По той же причине мы отказались от хранения указателей на элементы структур, так как это вызывает крайне нестабильное поведение системы при инстанцировании шаблона встроенными типами данных. Подобные вопросы чрезвычайно существенны при проектировании сред разработки, включающих в себя параметризованные классы, так как пользователь может инстанцировать шаблон произвольным типом данных. При использовании ссылок существуют, вообще говоря, три случая, и нам придется при создании библиотеки постараться найти определенный баланс между ними.
Во-первых, встроенные типы данных можно без труда передавать по ссылке и копировать. Объявив типы аргумента постоянными ссылками, можно избежать неприятностей, связанных с появлением временных структур, возникающих при приведении типов [12].
Во-вторых, типы данных, определенные пользователем, также можно передавать по ссылке и копировать, но только в том случае, когда для них определены копирующий конструктор и оператор присваивания. Ссылки можно использовать в полиморфных операциях (передавая объект производного класса вместо объявленного при инстанцировании), но копирование не будет полиморфным. В результате объект будет "срезан" до размеров своего базового класса.
В-третьих, при полиморфном использовании библиотеки встретится инстанцирование шаблонов указателями на базовый класс. Хотя передача указателей по ссылке может и не улучшить производительность, но копирование указателей в представление сохраняет полиморфизм производных объектов.
Например, для класса BoundedQueue мы можем написать следующее:
class Event ... typedef Event* EventPtr;
BoundedQueue<int, 10U> intQueue;
BoundedQueue<Event, 50U> eventQueue1;
BoundedQueue<EventPtr, 100U> eventQueue2;
С помощью объекта класса eventQueue1 можно спокойно создавать очереди событий, однако при добавлении в очередь экземпляра любого подкласса Event произойдет "срезка", и полиморфное поведение такого экземпляра будет потеряно. С другой стороны, объект класса eventQueue2 содержит указатели на объекты класса Event, поэтому проблема "срезки" не возникает.
Наше решение, касающееся хранения внутри структур значений, а не ссылок, предъявляет определенные требования к конструкторам и деструкторам элементов. В частности, классы, используемые для инстанцирования структуры, должны, по крайней мере, иметь конструктор по умолчанию, копирующий конструктор и оператор присваивания. Кроме того, в некоторых случаях элементы не могут быть уничтожены сразу после удаления из структуры. В ограниченной форме, например, элементы (хранящиеся в массивах) не уничтожаются до уничтожения всей структуры.
Посмотрим, как можно использовать класс Bounded при формировании конкретного класса BoundedQueue. Отметим, что абстракция BoundedQueue содержит защищенный элемент rep класса Bounded.
template<class Item, unsigned int Size>
class BoundedQueue : public Queue<Item> {
public: BoundedQueue();
BoundedQueue(const BoundedQueue<Item, Size>&);
virtual ~BoundedQueue();
virtual Queue<Item>& operator=(const Queue<Item>&);
virtual Queue<Item>& operator=(const BoundedQueue<Item,
Size>&);
virtual int operator==(const Queue<Item>&) const;
virtual int operator=(const BoundedQueue<Item, Size>&) const;
int operator!=(const BoundedQueue< Item, Size>&) const;
virtual void clear();
virtual void append(const Item&);
virtual void pop();
virtual void remove(unsigned int at);
virtual unsigned int available() const;
virtual unsigned int length() const;
virtual int isEmpty() const;
virtual const Item& front() const;
virtual int location(const Item&) const;
protected: 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 имеют практически идентичный внешний протокол, а, значит, их функциональные свойства во многом подобны, можно предположить, что и реализация будет схожей. Однако различие во внутреннем представлении классов приводит к существенно различной пространственно-временной семантике. Манипуляции с узлами связанного списка, например, осуществляются очень быстро, однако процедура нахождения нужного элемента будет занимать время порядка O(n). Поэтому наше представление кэширует последний узел, к которому было обращение, в надежде, что следующее обращение будет либо к этому же узлу, либо к его соседям. Схема же, базирующаяся на массивах, дает низкое быстродействие (в худшем случае порядка O(n/2) если элемент расположен в середине массива) при добавлении или удалении элементов, однако обеспечивает высокую скорость поиска (порядка O(1)).
