Страница:
итератор.
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[].
Я прервал вас, поэтому не прерывайте меня.
- Уинстон Черчилл
В этой главе описан механизм обработки особых ситуаций и некоторые,
основывающиеся на нем, способы обработки ошибок. Механизм состоит
в запуске особой ситуации, которую должен перехватить специальный
обработчик. Описываются правила перехвата особых ситуаций и
правила реакции на неперехваченные и неожиданные особые ситуации.
Целые группы особых ситуаций можно определить как производные
классы. Описывается способ, использующий деструкторы и обработку
особых ситуаций, который обеспечивает надежное и скрытое от
пользователя управление ресурсами.
Создатель библиотеки способен обнаружить динамические ошибки, но не
представляет какой в общем случае должна быть реакция на них.
Пользователь библиотеки способен написать реакцию на такие ошибки,
но не в силах их обнаружить. Если бы он мог, то сам разобрался бы
с ошибками в своей программе, и их не пришлось бы выявлять
в библиотечных функциях. Для решения этой проблемы в язык введено
понятие особой ситуации Ь.
Ь Только недавно комитетом по стандартизации С++ особые ситуации были
включены в стандарт языка, но на время написания этой книги они еще
не вошли в большинство реализаций.
Суть этого понятия в том, что функция, которая обнаружила ошибку и не
может справиться с нею, запускает особую ситуацию, рассчитывая, что
устранить проблему можно в той функции, которая прямо или опосредованно
вызывала первую. Если функция рассчитана на обработку ошибок некоторого
вида, она может указать это явно, как готовность перехватить данную
особую ситуацию.
Рассмотрим в качестве примера как для класса 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) { // значит сюда мы никогда не попадем
// ...
}
}
Наш способ обработки ошибок по многим параметрам выгодно отличается от
более традиционных способов. Перечислим, что может сделать операция
индексации Vector::operator[]() при обнаружении недопустимого значения
индекса:
[1] завершить программу;
[2] возвратить значение, трактуемое как "ошибка";
[3] возвратить нормальное значение и оставить программу в
неопределенном состоянии;
[4] вызвать функцию, заданную для реакции на такую ошибку.
Вариант [1] ("завершить программу") реализуется по умолчанию в том
случае, когда особая ситуация не была перехвачена. Для большинства
ошибок можно и нужно обеспечить лучшую реакцию.
Вариант [2] ("возвратить значение "ошибка"") можно реализовать
не всегда, поскольку не всегда удается определить значение "ошибка".
Так, в нашем примере любое целое является допустимым значением для
результата операции индексации. Если можно выделить такое особое
значение, то часто этот вариант все равно оказывается неудобным,
поскольку проверять на это значение приходится при каждом вызове. Так
можно легко удвоить размер программы. Поэтому для обнаружения всех
ошибок этот вариант редко используется последовательно.
Вариант [3] ("оставить программу в неопределенном состоянии")
имеет тот недостаток, что вызывавшая функция может не заметить
ненормального состояния программы. Например, во многих функциях
стандартной библиотеки С для сигнализации об ошибке устанавливается
соответствующее значение глобальной переменной errno. Однако,
в программах пользователя обычно нет достаточно последовательного
контроля errno, и в результате возникают наведенные ошибки,
вызванные тем, что стандартные функции возвращают не то значение.
Кроме того, если в программе есть параллельные вычисления,
использование одной глобальной переменной для сигнализации о разных
ошибках неизбежно приведет к катастрофе.
Обработка особых ситуаций не предназначалась для тех случаев,
на которые рассчитан вариант [4] ( "вызвать функцию реакции на
ошибку"). Отметим, однако, что если особые ситуации не предусмотрены,
то вместо функции реакции на ошибку можно как раз использовать
только один из трех перечисленных вариантов. Обсуждение функций
реакций и особых ситуацией будет продолжено в $$9.4.3.
Механизм особых ситуаций успешно заменяет традиционные
способы обработки ошибок в тех случаях, когда последние являются
неполным, некрасивым или чреватым ошибками решением. Этот механизм
позволяет явно отделить часть программы, в которой обрабатываются
ошибки, от остальной ее части, тем самым программа становится более
понятной и с ней проще работать различным сервисным программам.
Свойственный этому механизму регулярный способ обработки ошибок
упрощает взаимодействие между раздельно написанными частями
программы.
В этом способе обработки ошибок есть для программирующих на С
новый момент: стандартная реакция на ошибку (особенно на ошибку
в библиотечной функции) состоит в завершении программы. Традиционной
была реакция продолжать программу в надежде, что она как-то
завершится сама. Поэтому способ, базирующийся на особых ситуациях,
делает программу более "хрупкой" в том смысле, что требуется
больше усилий и внимания для ее нормального выполнения. Но это все-таки
лучше, чем получать неверные результаты на более поздней стадии
развития программы (или получать их еще позже, когда программу
сочтут завершенной и передадут ничего не подозревающему пользователю).
Если завершение программы является неприемлемой реакцией, можно
смоделировать традиционную реакцию с помощью перехвата всех особых
ситуаций или всех особых ситуаций, принадлежащих специальному
классу ($$9.3.2).
Механизм особых ситуаций можно рассматривать как динамический
аналог механизма контроля типов и проверки неоднозначности
на стадии трансляции. При таком подходе более важной становится
стадия проектирования программы, и требуется большая поддержка
процесса выполнения программы, чем для программ на С. Однако,
в результате получится более предсказуемая программа, ее будет проще
встроить в программную систему, она будет понятнее другим программистам и
с ней проще будет работать различным сервисным программам. Можно
сказать, что механизм особых ситуаций поддерживает,
подобно другим средствам С++, "хороший" стиль программирования,
который в таких языках, как С, можно применять только не в полном
объеме и на неформальном уровне.
Все же надо сознавать, что обработка ошибок остается трудной
задачей, и, хотя механизм особых ситуаций более строгий,
чем традиционные способы, он все равно недостаточно структурирован
по сравнению с конструкциями, допускающими только локальную передачу
управления.
"Особая ситуация" - одно из тех понятий, которые имеют разный смысл
для разных людей. В С++ механизм особых ситуаций предназначен для
обработки ошибок. В частности, он предназначен для обработки ошибок
в программах, состоящих из независимо создаваемых компонентов.
Этот механизм рассчитан на особые ситуации, возникающие только при
последовательном выполнении программы (например, контроль границ
массива). Асинхронные особые ситуации такие, например, как прерывания
от клавиатуры, нельзя непосредственно обрабатывать с помощью этого
механизма. В различных системах существуют другие механизмы,
например, сигналы, но они здесь не рассматриваются, поскольку зависят
от конкретной системы.
Механизм особых ситуаций является конструкцией с нелокальной
передачей управления и его можно рассматривать как вариант оператора
return. Поэтому особые ситуации можно использовать для целей, никак
не связанных с обработкой ошибок ($$9.5). Все-таки основным
назначением механизма особых ситуаций и темой этой главы будет
обработка ошибок и создание устойчивых к ошибкам программ.
Естественно, в программе возможны несколько различных динамических
ошибок. Эти ошибки можно сопоставить с особыми ситуациями, имеющими
различные имена. Так, в классе Vector обычно приходится выявлять
и сообщать об ошибках двух видов: ошибки диапазона и ошибки,
вызванные неподходящим для конструктора параметром:
class Vector {
int* p;
int sz;
public:
enum { max = 32000 };
class Range { }; // особая ситуация индекса
class Size { }; // особая ситуация "неверный размер"
Vector(int sz);
int& operator[](int i);
// ...
};
Как было сказано, операция индексации запускает особую ситуацию
Range, если ей задан выходящий из диапазона значений индекс.
Конструктор запускает особую ситуацию Size, если ему задан
недопустимый размер вектора:
Vector::Vector(int sz)
{
if (sz<0 || max<sz) throw Size();
// ...
}
Пользователь класса Vector может различить эти две особые ситуации,
если в проверяемом блоке (т.е. в блоке оператора try) укажет
обработчики для обеих ситуаций:
void f()
{
try {
use_vectors();
}
catch (Vector::Range) {
// ...
}
catch (Vector::Size) {
// ...
}
}
В зависимости от особой ситуации будет выполняться соответствующий
обработчик. Если управление дойдет до конца операторов обработчика,
следующим будет выполняться оператор, который идет после списка
обработчиков:
void f()
{
try {
use_vectors();
}
catch (Vector::Range) {
// исправить индекс и
// попробовать опять:
f();
}
catch (Vector::Size) {
cerr << "Ошибка в конструкторе Vector::Size";
exit(99);
}
// сюда мы попадем, если вообще не было особых ситуаций
// или после обработки особой ситуации Range
}
Список обработчиков напоминает переключатель, но здесь в теле
обработчика операторы break не нужны. Синтаксис списка обработчиков
отличен от синтаксиса вариантов case переключателя частично по
этой причине, частично потому, чтобы показать, что каждый
обработчик определяет свою область видимости (см. $$9.8).
Не обязательно все особые ситуации перехватывать в одной функции:
void f1()
{
try {
f2(v);
}
catch (Vector::Size) {
// ...
}
}
void f2(Vector& v)
{
try {
use_vectors();
}
catch (Vector::Range) {
// ...
}
}
Здесь f2() перехватит особую ситуацию Range, возникающую в
use_vectors(), а особая ситуация Size будет оставлена для f1().
С точки зрения языка особая ситуация считается обработанной сразу
при входе в тело ее обработчика. Поэтому все особые ситуации,
запускаемые при выполнении этого обработчика, должны обрабатываться
в функциях, вызвавших ту функцию, которая содержит проверяемый блок.
Значит в следующем примере не возникнет бесконечного цикла:
try {
// ...
}
catch (input_overflow) {
// ...
throw input_overflow();
}
Здесь input_overflow (переполнение при вводе) - имя глобального класса.
Обработчики особых ситуаций могут быть вложенными:
try {
// ...
}
catch (xxii) {
try {
// сложная реакция
}
catch (xxii) {
// ошибка в процессе сложной реакции
}
}
Однако, такая вложенность редко бывает нужна в обычных программах,
и чаще всего она является свидетельством плохого стиля.
Особая ситуация перехватывается благодаря своему типу. Однако,
запускается ведь не тип, а объект. Если нам нужно передать некоторую
информацию из точки запуска в обработчик, то для этого ее следует
поместить в запускаемый объект. Например, допустим нужно знать
значение индекса, выходящее за границы диапазона:
class Vector {
// ...
public:
class Range {
public:
int index;
Range(int i) : index(i) { }
};
// ...
int& operator[](int i)
// ...
};
int Vector::operator[](int i)
{
if (o<=i && i <sz) return p[i];
throw Range(i);
}
Чтобы исследовать недопустимое значение индекса, в обработчике
нужно дать имя объекту, представляющему особую ситуацию:
void f(Vector& v)
{
// ...
try {
do_something(v);
}
catch (Vector::Range r ) {
cerr << "недопустимый индекс" << r.index << '\n';
// ...
}
// ...
}
Конструкция в скобках после служебного слова catch является по сути
описанием и она аналогична описанию формального параметра функции.
В ней указывается каким может быть тип параметра (т.е. особой
ситуации) и может задаваться имя для фактической, т.е. запущенной,
особой ситуации. Вспомним, что в шаблонах типов у нас был выбор
для именования особых ситуаций. В каждом созданном по шаблону классе
был свой класс особой ситуации:
template<class T> class Allocator {
// ...
class Exhausted { }
// ...
T* get();
};
void f(Allocator<int>& ai, Allocator<double>& ad)
{
try {
// ...
}
catch (Allocator<int>::Exhausted) {
// ...
}
catch (Allocator<double>::Exhausted) {
// ...
}
}
С другой стороны, особая ситуация может быть общей для всех
созданных по шаблону классов:
class Allocator_Exhausted { };
template<class T> class Allocator {
// ...
T* get();
};
void f(Allocator<int>& ai, Allocator<double>& ad)
{
try {
// ...
}
catch (Allocator_Exhausted) {
// ...
}
}
Какой способ задания особой ситуации предпочтительней, сказать трудно.
Выбор зависит от назначения рассматриваемого шаблона.
Особые ситуации естественным образом разбиваются на семейства.
Действительно, логично представлять семейство Matherr, в которое
входят Overflow (переполнение), Underflow (потеря значимости) и
некоторые другие особые ситуации. Семейство Matherr образуют
особые ситуации, которые могут запускать математические функции
стандартной библиотеки.
Один из способов задания такого семейства сводится к определению
Matherr как типа, возможные значения которого включают Overflow и
все остальные:
enum { Overflow, Underflow, Zerodivide, /* ... */ };
try {
// ...
}
catch (Matherr m) {
switch (m) {
case Overflow:
// ...
case Underflow:
// ...
// ...
}
// ...
}
Другой способ предполагает использование наследования и виртуальных
функций, чтобы не вводить переключателя по значению поля типа.
Наследование помогает описать семейства особых ситуаций:
class Matherr { };
class Overflow: public Matherr { };
class Underflow: public Matherr { };
class Zerodivide: public Matherr { };
// ...
Часто бывает так, что нужно обработать особую ситуацию Matherr
не зависимо от того, какая именно ситуация из этого семейства
произошла. Наследование позволяет сделать это просто:
try {
// ...
}
catch (Overflow) {
// обработка Overflow или любой производной ситуации
}
catch (Matherr) {
// обработка любой отличной от Overflow ситуации
}
В этом примере Overflow разбирается отдельно, а все другие особые
ситуации из Matherr разбираются как один общий случай. Конечно,
функция, содержащая catch (Matherr), не будет знать какую именно
особую ситуацию она перехватывает. Но какой бы она ни была, при
входе в обработчик передаваемая ее копия будет Matherr. Обычно это
как раз то, что нужно. Если это не так, особую ситуацию можно
перехватить по ссылке (см. $$9.3.2).
Иерархическое упорядочивание особых ситуаций может играть важную
роль для создания ясной структуры программы. Действительно, пусть
такое упорядочивание отсутствует, и нужно обработать все особые
ситуации стандартной библиотеки математических функций. Для этого
придется до бесконечности перечислять все возможные особые ситуации:
try {
// ...
}
catch (Overflow) { /* ... */ }
catch (Underflow) { /* ... */ }
catch (Zerodivide) { /* ... */ }
// ...
Это не только утомительно, но и опасно, поскольку можно забыть
какую-нибудь особую ситуацию. Кроме того, необходимость перечислить
в проверяемом блоке все особые ситуации практически гарантирует,
что, когда семейство особых ситуаций библиотеки расширится, в
программе пользователя возникнет ошибка. Это значит, что при
введении новой особой ситуации в библиотеки математических функций
придется перетранслировать все части программы, которые содержат
обработчики всех особых ситуаций из Matherr. В общем случае такая
перетрансляция неприемлема. Часто даже нет возможности найти
все требующие перетрансляции части программы. Если такая
возможность есть, нельзя требовать, чтобы всегда был
доступен исходной текст любой части большой программы, или чтобы у нас
были права изменять любую часть большой программы, исходный текст
которой мы имеем. На самом деле, пользователь не должен думать
о внутреннем устройстве библиотек. Все эти проблемы перетрансляции
и сопровождения могут привести к тому, что после создания
первой версии библиотеки будет нельзя вводить в ней новые
особые ситуации. Но такое решение не подходит практически для всех
библиотек.
Все эти доводы говорят за то, что особые ситуации нужно
определять как иерархию классов (см. также $$9.6.1). Это, в свою
очередь, означает, что особые ситуации могут быть членами нескольких
групп:
class network_file_err // ошибки файловой системы в сети
: public network_err, // ошибки сети
public file_system_err { // ошибки файловой системы
// ...
};
Особую ситуацию network_file_err можно перехватить в функциях,
обрабатывающих особые ситуации сети:
void f()
{
try {
// какие-то операторы
}
catch (network_err) {
// ...
}
}
Ее также можно перехватить в функциях, обрабатывающих особые ситуации
файловой системы:
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[].
Я прервал вас, поэтому не прерывайте меня.
- Уинстон Черчилл
В этой главе описан механизм обработки особых ситуаций и некоторые,
основывающиеся на нем, способы обработки ошибок. Механизм состоит
в запуске особой ситуации, которую должен перехватить специальный
обработчик. Описываются правила перехвата особых ситуаций и
правила реакции на неперехваченные и неожиданные особые ситуации.
Целые группы особых ситуаций можно определить как производные
классы. Описывается способ, использующий деструкторы и обработку
особых ситуаций, который обеспечивает надежное и скрытое от
пользователя управление ресурсами.
Создатель библиотеки способен обнаружить динамические ошибки, но не
представляет какой в общем случае должна быть реакция на них.
Пользователь библиотеки способен написать реакцию на такие ошибки,
но не в силах их обнаружить. Если бы он мог, то сам разобрался бы
с ошибками в своей программе, и их не пришлось бы выявлять
в библиотечных функциях. Для решения этой проблемы в язык введено
понятие особой ситуации Ь.
Ь Только недавно комитетом по стандартизации С++ особые ситуации были
включены в стандарт языка, но на время написания этой книги они еще
не вошли в большинство реализаций.
Суть этого понятия в том, что функция, которая обнаружила ошибку и не
может справиться с нею, запускает особую ситуацию, рассчитывая, что
устранить проблему можно в той функции, которая прямо или опосредованно
вызывала первую. Если функция рассчитана на обработку ошибок некоторого
вида, она может указать это явно, как готовность перехватить данную
особую ситуацию.
Рассмотрим в качестве примера как для класса 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) { // значит сюда мы никогда не попадем
// ...
}
}
Наш способ обработки ошибок по многим параметрам выгодно отличается от
более традиционных способов. Перечислим, что может сделать операция
индексации Vector::operator[]() при обнаружении недопустимого значения
индекса:
[1] завершить программу;
[2] возвратить значение, трактуемое как "ошибка";
[3] возвратить нормальное значение и оставить программу в
неопределенном состоянии;
[4] вызвать функцию, заданную для реакции на такую ошибку.
Вариант [1] ("завершить программу") реализуется по умолчанию в том
случае, когда особая ситуация не была перехвачена. Для большинства
ошибок можно и нужно обеспечить лучшую реакцию.
Вариант [2] ("возвратить значение "ошибка"") можно реализовать
не всегда, поскольку не всегда удается определить значение "ошибка".
Так, в нашем примере любое целое является допустимым значением для
результата операции индексации. Если можно выделить такое особое
значение, то часто этот вариант все равно оказывается неудобным,
поскольку проверять на это значение приходится при каждом вызове. Так
можно легко удвоить размер программы. Поэтому для обнаружения всех
ошибок этот вариант редко используется последовательно.
Вариант [3] ("оставить программу в неопределенном состоянии")
имеет тот недостаток, что вызывавшая функция может не заметить
ненормального состояния программы. Например, во многих функциях
стандартной библиотеки С для сигнализации об ошибке устанавливается
соответствующее значение глобальной переменной errno. Однако,
в программах пользователя обычно нет достаточно последовательного
контроля errno, и в результате возникают наведенные ошибки,
вызванные тем, что стандартные функции возвращают не то значение.
Кроме того, если в программе есть параллельные вычисления,
использование одной глобальной переменной для сигнализации о разных
ошибках неизбежно приведет к катастрофе.
Обработка особых ситуаций не предназначалась для тех случаев,
на которые рассчитан вариант [4] ( "вызвать функцию реакции на
ошибку"). Отметим, однако, что если особые ситуации не предусмотрены,
то вместо функции реакции на ошибку можно как раз использовать
только один из трех перечисленных вариантов. Обсуждение функций
реакций и особых ситуацией будет продолжено в $$9.4.3.
Механизм особых ситуаций успешно заменяет традиционные
способы обработки ошибок в тех случаях, когда последние являются
неполным, некрасивым или чреватым ошибками решением. Этот механизм
позволяет явно отделить часть программы, в которой обрабатываются
ошибки, от остальной ее части, тем самым программа становится более
понятной и с ней проще работать различным сервисным программам.
Свойственный этому механизму регулярный способ обработки ошибок
упрощает взаимодействие между раздельно написанными частями
программы.
В этом способе обработки ошибок есть для программирующих на С
новый момент: стандартная реакция на ошибку (особенно на ошибку
в библиотечной функции) состоит в завершении программы. Традиционной
была реакция продолжать программу в надежде, что она как-то
завершится сама. Поэтому способ, базирующийся на особых ситуациях,
делает программу более "хрупкой" в том смысле, что требуется
больше усилий и внимания для ее нормального выполнения. Но это все-таки
лучше, чем получать неверные результаты на более поздней стадии
развития программы (или получать их еще позже, когда программу
сочтут завершенной и передадут ничего не подозревающему пользователю).
Если завершение программы является неприемлемой реакцией, можно
смоделировать традиционную реакцию с помощью перехвата всех особых
ситуаций или всех особых ситуаций, принадлежащих специальному
классу ($$9.3.2).
Механизм особых ситуаций можно рассматривать как динамический
аналог механизма контроля типов и проверки неоднозначности
на стадии трансляции. При таком подходе более важной становится
стадия проектирования программы, и требуется большая поддержка
процесса выполнения программы, чем для программ на С. Однако,
в результате получится более предсказуемая программа, ее будет проще
встроить в программную систему, она будет понятнее другим программистам и
с ней проще будет работать различным сервисным программам. Можно
сказать, что механизм особых ситуаций поддерживает,
подобно другим средствам С++, "хороший" стиль программирования,
который в таких языках, как С, можно применять только не в полном
объеме и на неформальном уровне.
Все же надо сознавать, что обработка ошибок остается трудной
задачей, и, хотя механизм особых ситуаций более строгий,
чем традиционные способы, он все равно недостаточно структурирован
по сравнению с конструкциями, допускающими только локальную передачу
управления.
"Особая ситуация" - одно из тех понятий, которые имеют разный смысл
для разных людей. В С++ механизм особых ситуаций предназначен для
обработки ошибок. В частности, он предназначен для обработки ошибок
в программах, состоящих из независимо создаваемых компонентов.
Этот механизм рассчитан на особые ситуации, возникающие только при
последовательном выполнении программы (например, контроль границ
массива). Асинхронные особые ситуации такие, например, как прерывания
от клавиатуры, нельзя непосредственно обрабатывать с помощью этого
механизма. В различных системах существуют другие механизмы,
например, сигналы, но они здесь не рассматриваются, поскольку зависят
от конкретной системы.
Механизм особых ситуаций является конструкцией с нелокальной
передачей управления и его можно рассматривать как вариант оператора
return. Поэтому особые ситуации можно использовать для целей, никак
не связанных с обработкой ошибок ($$9.5). Все-таки основным
назначением механизма особых ситуаций и темой этой главы будет
обработка ошибок и создание устойчивых к ошибкам программ.
Естественно, в программе возможны несколько различных динамических
ошибок. Эти ошибки можно сопоставить с особыми ситуациями, имеющими
различные имена. Так, в классе Vector обычно приходится выявлять
и сообщать об ошибках двух видов: ошибки диапазона и ошибки,
вызванные неподходящим для конструктора параметром:
class Vector {
int* p;
int sz;
public:
enum { max = 32000 };
class Range { }; // особая ситуация индекса
class Size { }; // особая ситуация "неверный размер"
Vector(int sz);
int& operator[](int i);
// ...
};
Как было сказано, операция индексации запускает особую ситуацию
Range, если ей задан выходящий из диапазона значений индекс.
Конструктор запускает особую ситуацию Size, если ему задан
недопустимый размер вектора:
Vector::Vector(int sz)
{
if (sz<0 || max<sz) throw Size();
// ...
}
Пользователь класса Vector может различить эти две особые ситуации,
если в проверяемом блоке (т.е. в блоке оператора try) укажет
обработчики для обеих ситуаций:
void f()
{
try {
use_vectors();
}
catch (Vector::Range) {
// ...
}
catch (Vector::Size) {
// ...
}
}
В зависимости от особой ситуации будет выполняться соответствующий
обработчик. Если управление дойдет до конца операторов обработчика,
следующим будет выполняться оператор, который идет после списка
обработчиков:
void f()
{
try {
use_vectors();
}
catch (Vector::Range) {
// исправить индекс и
// попробовать опять:
f();
}
catch (Vector::Size) {
cerr << "Ошибка в конструкторе Vector::Size";
exit(99);
}
// сюда мы попадем, если вообще не было особых ситуаций
// или после обработки особой ситуации Range
}
Список обработчиков напоминает переключатель, но здесь в теле
обработчика операторы break не нужны. Синтаксис списка обработчиков
отличен от синтаксиса вариантов case переключателя частично по
этой причине, частично потому, чтобы показать, что каждый
обработчик определяет свою область видимости (см. $$9.8).
Не обязательно все особые ситуации перехватывать в одной функции:
void f1()
{
try {
f2(v);
}
catch (Vector::Size) {
// ...
}
}
void f2(Vector& v)
{
try {
use_vectors();
}
catch (Vector::Range) {
// ...
}
}
Здесь f2() перехватит особую ситуацию Range, возникающую в
use_vectors(), а особая ситуация Size будет оставлена для f1().
С точки зрения языка особая ситуация считается обработанной сразу
при входе в тело ее обработчика. Поэтому все особые ситуации,
запускаемые при выполнении этого обработчика, должны обрабатываться
в функциях, вызвавших ту функцию, которая содержит проверяемый блок.
Значит в следующем примере не возникнет бесконечного цикла:
try {
// ...
}
catch (input_overflow) {
// ...
throw input_overflow();
}
Здесь input_overflow (переполнение при вводе) - имя глобального класса.
Обработчики особых ситуаций могут быть вложенными:
try {
// ...
}
catch (xxii) {
try {
// сложная реакция
}
catch (xxii) {
// ошибка в процессе сложной реакции
}
}
Однако, такая вложенность редко бывает нужна в обычных программах,
и чаще всего она является свидетельством плохого стиля.
Особая ситуация перехватывается благодаря своему типу. Однако,
запускается ведь не тип, а объект. Если нам нужно передать некоторую
информацию из точки запуска в обработчик, то для этого ее следует
поместить в запускаемый объект. Например, допустим нужно знать
значение индекса, выходящее за границы диапазона:
class Vector {
// ...
public:
class Range {
public:
int index;
Range(int i) : index(i) { }
};
// ...
int& operator[](int i)
// ...
};
int Vector::operator[](int i)
{
if (o<=i && i <sz) return p[i];
throw Range(i);
}
Чтобы исследовать недопустимое значение индекса, в обработчике
нужно дать имя объекту, представляющему особую ситуацию:
void f(Vector& v)
{
// ...
try {
do_something(v);
}
catch (Vector::Range r ) {
cerr << "недопустимый индекс" << r.index << '\n';
// ...
}
// ...
}
Конструкция в скобках после служебного слова catch является по сути
описанием и она аналогична описанию формального параметра функции.
В ней указывается каким может быть тип параметра (т.е. особой
ситуации) и может задаваться имя для фактической, т.е. запущенной,
особой ситуации. Вспомним, что в шаблонах типов у нас был выбор
для именования особых ситуаций. В каждом созданном по шаблону классе
был свой класс особой ситуации:
template<class T> class Allocator {
// ...
class Exhausted { }
// ...
T* get();
};
void f(Allocator<int>& ai, Allocator<double>& ad)
{
try {
// ...
}
catch (Allocator<int>::Exhausted) {
// ...
}
catch (Allocator<double>::Exhausted) {
// ...
}
}
С другой стороны, особая ситуация может быть общей для всех
созданных по шаблону классов:
class Allocator_Exhausted { };
template<class T> class Allocator {
// ...
T* get();
};
void f(Allocator<int>& ai, Allocator<double>& ad)
{
try {
// ...
}
catch (Allocator_Exhausted) {
// ...
}
}
Какой способ задания особой ситуации предпочтительней, сказать трудно.
Выбор зависит от назначения рассматриваемого шаблона.
Особые ситуации естественным образом разбиваются на семейства.
Действительно, логично представлять семейство Matherr, в которое
входят Overflow (переполнение), Underflow (потеря значимости) и
некоторые другие особые ситуации. Семейство Matherr образуют
особые ситуации, которые могут запускать математические функции
стандартной библиотеки.
Один из способов задания такого семейства сводится к определению
Matherr как типа, возможные значения которого включают Overflow и
все остальные:
enum { Overflow, Underflow, Zerodivide, /* ... */ };
try {
// ...
}
catch (Matherr m) {
switch (m) {
case Overflow:
// ...
case Underflow:
// ...
// ...
}
// ...
}
Другой способ предполагает использование наследования и виртуальных
функций, чтобы не вводить переключателя по значению поля типа.
Наследование помогает описать семейства особых ситуаций:
class Matherr { };
class Overflow: public Matherr { };
class Underflow: public Matherr { };
class Zerodivide: public Matherr { };
// ...
Часто бывает так, что нужно обработать особую ситуацию Matherr
не зависимо от того, какая именно ситуация из этого семейства
произошла. Наследование позволяет сделать это просто:
try {
// ...
}
catch (Overflow) {
// обработка Overflow или любой производной ситуации
}
catch (Matherr) {
// обработка любой отличной от Overflow ситуации
}
В этом примере Overflow разбирается отдельно, а все другие особые
ситуации из Matherr разбираются как один общий случай. Конечно,
функция, содержащая catch (Matherr), не будет знать какую именно
особую ситуацию она перехватывает. Но какой бы она ни была, при
входе в обработчик передаваемая ее копия будет Matherr. Обычно это
как раз то, что нужно. Если это не так, особую ситуацию можно
перехватить по ссылке (см. $$9.3.2).
Иерархическое упорядочивание особых ситуаций может играть важную
роль для создания ясной структуры программы. Действительно, пусть
такое упорядочивание отсутствует, и нужно обработать все особые
ситуации стандартной библиотеки математических функций. Для этого
придется до бесконечности перечислять все возможные особые ситуации:
try {
// ...
}
catch (Overflow) { /* ... */ }
catch (Underflow) { /* ... */ }
catch (Zerodivide) { /* ... */ }
// ...
Это не только утомительно, но и опасно, поскольку можно забыть
какую-нибудь особую ситуацию. Кроме того, необходимость перечислить
в проверяемом блоке все особые ситуации практически гарантирует,
что, когда семейство особых ситуаций библиотеки расширится, в
программе пользователя возникнет ошибка. Это значит, что при
введении новой особой ситуации в библиотеки математических функций
придется перетранслировать все части программы, которые содержат
обработчики всех особых ситуаций из Matherr. В общем случае такая
перетрансляция неприемлема. Часто даже нет возможности найти
все требующие перетрансляции части программы. Если такая
возможность есть, нельзя требовать, чтобы всегда был
доступен исходной текст любой части большой программы, или чтобы у нас
были права изменять любую часть большой программы, исходный текст
которой мы имеем. На самом деле, пользователь не должен думать
о внутреннем устройстве библиотек. Все эти проблемы перетрансляции
и сопровождения могут привести к тому, что после создания
первой версии библиотеки будет нельзя вводить в ней новые
особые ситуации. Но такое решение не подходит практически для всех
библиотек.
Все эти доводы говорят за то, что особые ситуации нужно
определять как иерархию классов (см. также $$9.6.1). Это, в свою
очередь, означает, что особые ситуации могут быть членами нескольких
групп:
class network_file_err // ошибки файловой системы в сети
: public network_err, // ошибки сети
public file_system_err { // ошибки файловой системы
// ...
};
Особую ситуацию network_file_err можно перехватить в функциях,
обрабатывающих особые ситуации сети:
void f()
{
try {
// какие-то операторы
}
catch (network_err) {
// ...
}
}
Ее также можно перехватить в функциях, обрабатывающих особые ситуации
файловой системы: