В контейнерных классах часто приходится выделять память. Иногда бывает необходимо (или просто удобно) дать пользователю возможность выбирать из нескольких вариантов выделения памяти, а также позволить ему задавать свой вариант. Это можно сделать несколькими способами. Один из способов состоит в том, что определяется шаблон типа для создания нового класса, в интерфейс которого входит описание соответствующего контейнера и класса, производящего выделение памяти по способу, описанному в $$6.7.2: template<class T, class A> class Controlled_container: public Container<T>, private A { //... void some_function() { //... T* p = new(A::operator new(sizeof(T))) T; //... } //... }; Шаблон типа здесь необходим, поскольку мы создаем контейнерный класс. Наследование от Container<T> нужно, чтобы класс Controlled_container можно было использовать как контейнерный класс. Шаблон типа с параметром A позволит нам использовать различные функции размещения: class Shared: public Arena { /*... */ }; class Fast_allocator { /*... */ }; Controlled_container<Process_descriptor,Shared> ptbl; Controlled_container<Node,Fast_allocator> tree; Controlled_container<Personell_record,Persistent> payroll; Это универсальный способ предоставлять производным классам содержательную информацию о реализации. Его положительными качествами являются систематичность и возможность использовать функции-подстановки. Для этого способа характерны необычно длинные имена. Впрочем, как обычно, typedef позволяет задать синонимы для слишком длинных имен типов: typedef Controlled_container<Personell_record,Persistent> pp_record; pp_record payroll; Обычно шаблон типа для создания такого класса как pp_record используют только в том случае, когда добавляемая информация по реализации достаточно существенна, чтобы не вносить ее в производный класс ручным программированием. Примером такого шаблона может быть общий (возможно, для некоторых библиотек стандартный) шаблонный класс Comparator ($$8.4.2), а также нетривиальные (возможно, стандартные для некоторых библиотек) классы Allocator (классы для выделения памяти). Отметим, что построение производных классов в таких примерах идет по "основному проспекту", который определяет интерфейс с пользователем (в нашем примере это Container). Но есть и "боковые улицы", задающие детали реализации.
Ассоциативный массив
Из всех универсальных невстроенных типов самым полезным, по всей видимости, является ассоциативный массив. Его часто называют таблицей (map), а иногда словарем, и он хранит пары значений. Имея одно из значений, называемое ключом, можно получить доступ к другому, называемому просто значением. Ассоциативный массив можно представлять как массив, в котором индекс не обязан быть целым: template<class K, class V> class Map { //... public: V& operator[](const K&); // найти V, соответствующее K // и вернуть ссылку на него //... }; Здесь ключ типа K обозначает значение типа V. Предполагается, что ключи можно сравнивать с помощью операций == и <, так что массив можно хранить в упорядоченном виде. Отметим, что класс Map отличается от типа assoc из $$7.8 тем, что для него нужна операция "меньше чем", а не функция хэширования. Приведем простую программу подсчета слов, в которой используются шаблон Map и тип String: #include <String.h> #include <iostream.h> #include "Map.h" int main() { Map<String,int> count; String word; while (cin >> word) count[word]++; for (Mapiter<String,int> p = count.first(); p; p++) cout << p.value() << '\t' << p.key() << '\n'; return 0; } Мы используем тип String для того, чтобы не беспокоиться о выделении памяти и переполнении ее, о чем приходится помнить, используя тип char*. Итератор Mapiter нужен для выбора по порядку всех значений массива. Итерация в Mapiter задается как имитация работы с указателями. Если входной поток имеет вид It was new. It was singular. It was simple. It must succeed. программа выдаст 4 It 1 must 1 new. 1 simple. 1 singular. 1 succeed. 3 was. Конечно, определить ассоциативный массив можно многими способами, а, имея определение Map и связанного с ним класса итератора, мы можем предложить много способов для их реализации. Здесь выбран тривиальный способ реализации. Используется линейный поиск, который не подходит для больших массивов. Естественно, рассчитанная на коммерческое применение реализация будет создаваться, исходя из требований быстрого поиска и компактности представления (см. упражнение 4 из $$8.9). Мы используем список с двойной связью Link: template<class K, class V> class Map; template<class K, class V> class Mapiter; template<class K, class V> class Link { friend class Map<K,V>; friend class Mapiter<K,V>; private: const K key; V value; Link* pre; Link* suc; Link(const K& k, const V& v): key(k), value(v) { } ~Link() { delete suc; } // рекурсивное удаление всех // объектов в списке }; Каждый объект Link содержит пару (ключ, значение). Классы описаны в Link как друзья, и это гарантирует, что объекты Link можно создавать, работать с ними и уничтожать только с помощью соответствующих классов итератора и Map. Обратите внимание на предварительные описания шаблонных классов Map и Mapiter. Шаблон Map можно определить так: template<class K, class V> class Map { friend class Mapiter<K,V>; Link<K,V>* head; Link<K,V>* current; V def_val; K def_key; int sz; void find(const K&); void init() { sz = 0; head = 0; current = 0; } public: Map() { init(); } Map(const K& k, const V& d): def_key(k), def_val(d) { init(); } ~Map() { delete head; } // рекурсивное удаление // всех объектов в списке Map(const Map&); Map& operator= (const Map&); V& operator[] (const K&); int size() const { return sz; } void clear() { delete head; init(); } void remove(const K& k); // функции для итерации Mapiter<K,V> element(const K& k) { (void) operator[](k); // сделать k текущим элементом return Mapiter<K,V>(this,current); } Mapiter<K,V> first(); Mapiter<K,V> last(); }; Элементы хранятся в упорядоченном списке с дойной связью. Для простоты ничего не делается для ускорения поиска (см. упражнение 4 из $$8.9). Ключевой здесь является функция operator[](): template<class K, class V> V& Map<K,V>::operator[] (const K& k) { if (head == 0) { current = head = new Link<K,V>(k,def_val); current->pre = current->suc = 0; return current->value; } Link<K,V>* p = head; for (;;) { if (p->key == k) { // найдено current = p; return current->value; } if (k < p->key) { // вставить перед p (в начало) current = new Link<K,V>(k,def_val); current->pre = p->pre; current->suc = p; if (p == head) // текущий элемент становится начальным head = current; else p->pre->suc = current; p->pre = current; return current->value; } Link<K,V>* s = p->suc; if (s == 0) { // вставить после p (в конец) current = new Link<K,V>(k,def_val); current->pre = p; current->suc = 0; p->suc = current; return current->value; } p = s; } } Операция индексации возвращает ссылку на значение, которое соответствует заданному как параметр ключу. Если такое значение не найдено, возвращается новый элемент со стандартным значением. Это позволяет использовать операцию индексации в левой части присваивания. Стандартные значения для ключей и значений устанавливаются конструкторами Map. В операции индексации определяется значение current, используемое итераторами. Реализация остальных функций-членов оставлена в качестве упражнения: template<class K, class V> void Map<K,V>::remove(const K& k) { // см. упражнение 2 из $$8.10 } template<class K, class V> Map<K,V>::Map(const Map<K,V>& m) { // копирование таблицы Map и всех ее элементов } template<class K, class V> Map& Map<K,V>::operator=(const Map<K,V>& m) { // копирование таблицы Map и всех ее элементов } Теперь нам осталось только определить итерацию. В классе Map есть функции-члены first(), last() и element(const K&), которые возвращают итератор, установленный соответственно на первый, последний или задаваемый ключом-параметром элемент. Сделать это можно, поскольку элементы хранятся в упорядоченном по ключам виде. Итератор Mapiter для Map определяется так: template<class K, class V> class Mapiter { friend class Map<K,V>; Map<K,V>* m; Link<K,V>* p; Mapiter(Map<K,V>* mm, Link<K,V>* pp) { m = mm; p = pp; } public: Mapiter() { m = 0; p = 0; } Mapiter(Map<K,V>& mm); operator void*() { return p; } const K& key(); V& value(); Mapiter& operator--(); // префиксная void operator--(int); // постфиксная Mapiter& operator++(); // префиксная void operator++(int); // постфиксная }; После позиционирования итератора функции key() и value() из Mapiter выдают ключ и значение того элемента, на который установлен итератор. template<class K, class V> const K& Mapiter<K,V>::key() { if (p) return p->key; else return m->def_key; } template<class K, class V> V& Mapiter<K,V>::value() { if (p) return p->value; else return m->def_val; } По аналогии с указателями определены операции ++ и -- для продвижения по элементам Map вперед и назад: Mapiter<K,V>& Mapiter<K,V>::operator--() //префиксный декремент { if (p) p = p->pre; return *this; } void Mapiter<K,V>::operator--(int) // постфиксный декремент { if (p) p = p->pre; } Mapiter<K,V>& Mapiter<K,V>::operator++() // префиксный инкремент { if (p) p = p->suc; return *this; } void Mapiter<K,V>::operator++(int) // постфиксный инкремент { if (p) p = p->suc; } Постфиксные операции определены так, что они не возвращают никакого значения. Дело в том, что затраты на создание и передачу нового объекта Mapiter на каждом шаге итерации значительны, а польза от него будет не велика. Объект Mapiter можно инициализировать так, чтобы он был установлен на начало Map: template<class K, class V> Mapiter<K,V>::Mapiter(Map<K,V>& mm) { m == &mm; p = m->head; } Операция преобразования operator void*() возвращает нуль, если итератор не установлен на элемент Map, и ненулевое значение иначе. Значит можно проверять итератор iter, например, так: void f(Mapiter<const char*, Shape*>& iter) { //... if (iter) { // установлен на элемент таблицы } else { // не установлен на элемент таблицы } //... } Аналогичный прием используется для контроля потоковых операций ввода-вывода в $$10.3.2. Если итератор не установлен на элемент таблицы, его функции key() и value() возвращают ссылки на стандартные объекты. Если после всех этих определений вы забыли их назначение, можно привести еще одну небольшую программу, использующую таблицу Map. Пусть входной поток является списком пар значений следующего вида: hammer 2 nail 100 saw 3 saw 4 hammer 7 nail 1000 nail 250 Нужно отсортировать список так, чтобы значения, соответствующие одному предмету, складывались, и напечатать получившийся список вместе с итоговым значением: hammer 9 nail 1350 saw 7 ------------------- total 1366 Вначале напишем функцию, которая читает входные строки и заносит предметы с их количеством в таблицу. Ключом в этой таблице является первое слово строки: template<class K, class V> void readlines(Map<K,V>&key) { K word; while (cin >> word) { V val = 0; if (cin >> val) key[word] +=val; else return; } } Теперь можно написать простую программу, вызывающую функцию readlines() и печатающую получившуюся таблицу: main() { Map<String,int> tbl("nil",0); readlines(tbl); int total = 0; for (Mapiter<String,int> p(tbl); p; ++p) { int val = p.value(); total +=val; cout << p.key() << '\t' << val << '\n'; } cout << "--------------------\n"; cout << "total\t" << total << '\n'; }
Упражнения
1. (*2) Определите семейство списков с двойной связью, которые будут двойниками списков с одной связью, определенных в $$8.3. 2. (*3) Определите шаблон типа String, параметром которого является тип символа. Покажите как его можно использовать не только для обычных символов, но и для гипотетического класса lchar, который представляет символы не из английского алфавита или расширенный набор символов. Нужно постараться так определить String, чтобы пользователь не заметил ухудшения характеристик программы по памяти и времени или в удобстве по сравнению с обычным строковым классом. 3. (*1.5) Определите класс Record (запись) с двумя членами-данными: count (количество) и price (цена). Упорядочите вектор из таких записей по каждому из членов. При этом нельзя изменять функцию сортировки и шаблон Vector. 4. (*2) Завершите определения шаблонного класса Map, написав недостающие функции-члены. 5. (*2) Задайте другую реализацию Map из $$8.8, используя списочный класс с двойной связью. 6. (*2.5) Задайте другую реализацию Map из $$8.8, используя сбалансированное дерево. Такие деревья описаны в $$6.2.3 книги Д. Кнут "Искусство программирования для ЭВМ" т.1, "Мир", 1978 [K]. 7. (*2) Сравните качество двух реализаций Map. В первой используется класс Link со своей собственной функцией размещения, а во второй - без нее. 8. (*3) Сравните производительность программы подсчета слов из $$8.8 и такой же программы, не использующей класса Map. Операции ввода-вывода должны одинаково использоваться в обеих программах. Сравните несколько таких программ, использующих разные варианты класса Map, в том числе и класс из вашей библиотеки, если он там есть. 9. (*2.5) С помощью класса Map реализуйте топологическую сортировку. Она описана в [K] т.1, стр. 323-332. (см. упражнение 6). 10. (*2) Модифицируйте программу из $$8.8 так, чтобы она работала правильно для длинных имен и для имен, содержащих пробелы (например, "thumb back"). 11. (*2) Определите шаблон типа для чтения различных видов строк, например, таких (предмет, количество, цена). 12. (*2) Определите класс Sort из $$8.4.5, использующий сортировку по методу Шелла. Покажите как можно задать метод сортировки с помощью параметра шаблона. Алгоритм сортировки описан в [K] т.3, $$5.2.1 (см. упражнение 6). 13. (*1) Измените определения Map и Mapiter так, чтобы постфиксные операции ++ и -- возвращали объект Mapiter. 14. (*1.5) Используйте шаблоны типа в стиле модульного программирования, как это было показано в $$8.4.5 и напишите функцию сортировки, рассчитанную сразу на Vector<T> и T[].
* ГЛАВА 9
Я прервал вас, поэтому не прерывайте меня. - Уинстон Черчилл В этой главе описан механизм обработки особых ситуаций и некоторые, основывающиеся на нем, способы обработки ошибок. Механизм состоит в запуске особой ситуации, которую должен перехватить специальный обработчик. Описываются правила перехвата особых ситуаций и правила реакции на неперехваченные и неожиданные особые ситуации. Целые группы особых ситуаций можно определить как производные классы. Описывается способ, использующий деструкторы и обработку особых ситуаций, который обеспечивает надежное и скрытое от пользователя управление ресурсами.
Обработка ошибок
Создатель библиотеки способен обнаружить динамические ошибки, но не представляет какой в общем случае должна быть реакция на них. Пользователь библиотеки способен написать реакцию на такие ошибки, но не в силах их обнаружить. Если бы он мог, то сам разобрался бы с ошибками в своей программе, и их не пришлось бы выявлять в библиотечных функциях. Для решения этой проблемы в язык введено понятие особой ситуации Ь. Ь Только недавно комитетом по стандартизации С++ особые ситуации были включены в стандарт языка, но на время написания этой книги они еще не вошли в большинство реализаций. Суть этого понятия в том, что функция, которая обнаружила ошибку и не может справиться с нею, запускает особую ситуацию, рассчитывая, что устранить проблему можно в той функции, которая прямо или опосредованно вызывала первую. Если функция рассчитана на обработку ошибок некоторого вида, она может указать это явно, как готовность перехватить данную особую ситуацию. Рассмотрим в качестве примера как для класса Vector можно представлять и обрабатывать особые ситуации, вызванные выходом за границу массива: class Vector { int* p; int sz; public: class Range { }; // класс для особой ситуации int& operator[](int i); //... }; Предполагается, что объекты класса Range будут использоваться как особые ситуации, и запускать их можно так: int& Vector::operator[](int i) { if (0<=i && i<sz) return p[i]; throw Range(); } Если в функции предусмотрена реакция на ошибку недопустимого значения индекса, то ту часть функции, в которой эти ошибки будут перехватываться, надо поместить в оператор try. В нем должен быть и обработчик особой ситуации: void f(Vector& v) { //... try { do_something(v); // содержательная часть, работающая с v } catch (Vector::Range) { // обработчик особой ситуации Vector::Range // если do_something() завершится неудачно, // нужно как-то среагировать на это // сюда мы попадем только в том случае, когда // вызов do_something() приведет к вызову Vector::operator[]() // из-за недопустимого значения индекса } //... } Обработчиком особой ситуации называется конструкция catch (/*... */) { //... } Ее можно использовать только сразу после блока, начинающегося служебным словом try, или сразу после другого обработчика особой ситуации. Служебным является и слово catch. После него идет в скобках описание, которое используется аналогично описанию формальных параметров функции, а именно, в нем задается тип объектов, на которые рассчитан обработчик, и, возможно, имена параметров (см. $$9.3). Если в do_something() или в любой вызванной из нее функции произойдет ошибка индекса (на любом объекте Vector), то обработчик перехватит особую ситуацию и будет выполняться часть, обрабатывающая ошибку. Например, определения следующих функций приведут к запуску обработчика в f(): void do_something() { //... crash(v); //... } void crash(Vector& v) { v[v.size()+10]; // искусственно вызываем ошибку индекса } Процесс запуска и перехвата особой ситуации предполагает просмотр цепочки вызовов от точки запуска особой ситуации до функции, в которой она перехватывается. При этом восстанавливается состояние стека, соответствующее функции, перехватившей ошибку, и при проходе по всей цепочке вызовов для локальных объектов функций из этой цепочки вызываются деструкторы. Подробно это описано в $$9.4. Если при просмотре всей цепочки вызовов, начиная с запустившей особую ситуацию функции, не обнаружится подходящий обработчик, то программа завершается. Подробно это описано в $$9.7. Если обработчик перехватил особую ситуацию, то она будет обрабатываться и другие, рассчитанные на эту ситуацию, обработчики не будут рассматриваться. Иными словами, активирован будет только тот обработчик, который находится в самой последней вызывавшейся функции, содержащей соответствующие обработчики. В нашем примере функция f() перехватит Vector::Range, поэтому эту особую ситуацию нельзя перехватить ни в какой вызывающей f() функции: int ff(Vector& v) { try { f(v); // в f() будет перехвачена Vector::Range } catch (Vector::Range) { // значит сюда мы никогда не попадем //... } }