<< Пред. стр. 52 (из 121) След. >>
Список литературы по разделу
В этом объявлении говорится, что pf указывает на функцию, которая способна возбуждать только исключения типа string. Как и для объявлений функций, спецификации исключений в разных объявлениях одного и того же указателя не суммируются, они должны быть одинаковыми:
extern void (*pf) ( int ) throw(string);
// ошибка: отсутствует спецификация исключения
void (*pf)( int );
При работе с указателем на функцию со спецификацией исключений есть ограничения на тип указателя, используемого в качестве инициализатора или стоящего в правой части присваивания. Спецификации исключений обоих указателей не обязаны быть идентичными. Однако на указатель-инициализатор она должна накладывать столь же или более строгие ограничения, чем на инициализируемый указатель (или тот, которому присваивается значение). Например:
void recoup( int, int ) throw(exceptionType);
void no_problem() throw();
void doit( int, int ) throw(string, exceptionType);
// правильно: ограничения, накладываемые на спецификации
// исключений recoup() и pf1, одинаковы
void (*pf1)( int, int ) throw(exceptionType) = &recoup;
// правильно: ограничения, накладываемые на спецификацию исключений no_problem(), более строгие,
// чем для pf2
void (*pf2)( ) throw(string) = &no_problem;
// ошибка: ограничения, накладываемые на спецификацию
// исключений doit(), менее строгие, чем для pf3
//
void (*pf3)( int, int ) throw(string) = &doit;
Третья инициализация не имеет смысла. Объявление указателя гарантирует, что pf3 адресует функцию, которая может возбуждать только исключения типа string. Но doit() возбуждает также исключения типа exceptionType. Поскольку она не подходит под ограничения, накладываемые спецификацией исключений pf3, то не может служить корректным инициализатором для pf3, так что компилятор выдает ошибку.
Упражнение 11.9
В коде, разработанном для упражнения 11.8, измените объявление оператора operator[]() в классе IntArray, добавив спецификацию возбуждаемых им исключений. Модифицируйте программу так, чтобы operator[]() возбуждал исключение, не указанное в спецификации. Что при этом происходит?
Упражнение 11.10
Какие исключения может возбуждать функция, если ее спецификация исключений имеет вид throw()? А если у нее нет такой спецификации?
Упражнение 11.11
Какое из следующих присваиваний ошибочно? Почему?
void example() throw(string);
(a) void (*pf1)() = example;
(b) void (*pf2) throw() = example;
11.5. Исключения и вопросы проектирования
С обработкой исключений в программах C++ связано несколько вопросов. Хотя поддержка такой обработки встроена в язык, не стоит использовать ее везде. Обычно она применяется для обмена информацией об ошибках между независимо разработанными частями программы. Например, автор некоторой библиотеки может с помощью исключений сообщать пользователям об ошибках. Если библиотечная функция обнаруживает аномальную ситуацию, которую не способна обработать самостоятельно, она может возбудить исключение для уведомления вызывающей программы.
В нашем примере в библиотеке определен класс iStack и его функции-члены. Разумно предположить, что программист, кодировавший main(), где используется эта библиотека, не разрабатывал ее. Функции-члены класса iStack могут обнаружить, что операция pop() вызвана, когда стек пуст, или что операция push() вызвана, когда стек полон; однако разработчик библиотеки ничего не знал о программе, пользующейся его функциями, так что не мог разрешить проблему локально. Не сумев обработать ошибку внутри функций-членов, мы решили возбуждать исключения, чтобы известить вызывающую программу.
Хотя C++ поддерживает исключения, следует применять и другие методы обработки ошибок (например, возврат кода ошибки) – там, где это более уместно. Однозначного ответа на вопрос: “Когда ошибку следует трактовать как исключение?” не существует. Ответственность за решение о том, что считать исключительной ситуацией, возлагается на разработчика. Исключения – это часть интерфейса библиотеки, и решение о том, какие исключения она возбуждает, – важный аспект ее дизайна. Если библиотека предназначена для использования в программах, которые не должны аварийно завершаться ни при каких обстоятельствах, то она обязана разбираться с аномалиями сама либо извещать о них вызывающую программу, передавая ей управление. Решение о том, какие ошибки следует обрабатывать как исключения, – трудная часть работы по проектированию библиотеки.
В нашем примере с классом iStack вопрос, должна ли функция push() возбуждать исключение, если стек полон, является спорным. Альтернативная и, по мнению многих, лучшая реализация push() – локальное решение проблемы: увеличение размера стека при его заполнении. В конце концов, единственное ограничение – это объем доступной программе памяти. Наше решение о возбуждении исключения при попытке поместить значение в полный стек, по-видимому, непродуманно. Можно переделать функцию-член push(), чтобы она в такой ситуации наращивала стек:
void iStack::push( int value )
{
// если стек полон, увеличить размер вектора
if ( full() )
_stack.resize( 2 * _stack.size() );
_stack[ _top++ ] = value;
}
Аналогично следует ли функции pop() возбуждать исключение при попытке извлечь значение из пустого стека? Интересно отметить, что класс stack из стандартной библиотеки C++ (он рассматривался в главе 6) не возбуждает исключения в такой ситуации. Вместо этого постулируется, что поведение программы при попытке выполнения подобной операции не определено. Разрешить программе продолжать работу при обнаружении некорректного состояния признали возможным. Мы уже упоминали, что в разных библиотеках определены разные исключения. Не существует пригодного для всех случаев ответа на вопрос, что такое исключение.
Не все программы должны беспокоиться по поводу исключений, возбуждаемых библиотечными функциями. Хотя есть системы, для которых простой недопустим и которые, следовательно, должны обрабатывать все исключительные ситуации, не к каждой программе предъявляются такие требования. Обработка исключений предназначена в первую очередь для реализации отказоустойчивых систем. В этом случае решение о том, должна ли программа обрабатывать все исключения, возбуждаемые библиотеками, или может закончить выполнение аварийно, – это трудная часть процесса проектирования.
Еще один аспект проектирования программ заключается в том, что обработка исключений обычно структурирована. Как правило, программа строится из компонентов, и каждый компонент решает сам, какие исключения обрабатывать локально, а какие передавать на верхние уровни. Что мы понимаем под компонентом? Например, система анализа текстовых запросов, рассмотренная в главе 6, может быть разбита на три компонента, или слоя. Первый слой – это стандартная библиотека C++, которая обеспечивает базовые операции над строками, отображениями и т.д. Второй слой – это сама система анализа текстовых запросов, где определены такие функции, как string_caps() и suffix_text(), манипулирующие текстами и использующие стандартную библиотеку как основу. Третий слой – это программа, которая применяет нашу систему. Каждый компонент строится независимо и должен принимать решения о том, какие исключительные ситуации обрабатывать локально, а какие передавать на более высокий уровень.
Не все функции должны уметь обрабатывать исключения. Обычно try-блоки и ассоциированные с ними catch-обработчики применяются в функциях, являющихся точками входа в компонент. Catch-обработчики проектируются так, чтобы перехватывать те исключения, которые не должны попасть на верхние уровни программы. Для этого также используются спецификации исключений (см. раздел 11.4).
Мы расскажем о других аспектах проектирования программ, использующих исключения, в главе 19, после знакомства с классами и иерархиями классов.
12
12. Обобщенные алгоритмы
В нашу реализацию класса Array (см. главу 2) мы включили функции-члены для поддержки операций min(), max() и sort(). Однако в стандартном классе vector эти, на первый взгляд фундаментальные, операции отсутствуют. Для нахождения минимального или максимального значения элементов вектора следует вызвать один из обобщенных алгоритмов. Алгоритмами они называются потому, что реализуют такие распространенные операции, как min(), max(), find() и sort(), а обобщенными (generic) – потому, что применимы к различным контейнерным типам: векторам, спискам, массивам. Контейнер связывается с применяемым к нему обобщенным алгоритмом посредством пары итераторов (мы говорили о них в разделе 6.5), указывающих, какие элементы следует посетить при обходе контейнера. Специальные объекты-функции позволяют переопределить семантику операторов в обобщенных алгоритмах. Итак, в этой главе рассматриваются обобщенные алгоритмы, объекты-функции и итераторы.
12.1. Краткий обзор
Реализация обобщенного алгоритма не зависит от типа контейнера, поэтому одна основанная на шаблонах реализация может работать со всеми контейнерами, а равно и со встроенным типом массива. Рассмотрим алгоритм find(). Если коллекция не отсортирована, то, чтобы найти элемент, требуются лишь следующие общие шаги:
По очереди исследовать каждый элемент.
Если элемент равен искомому значению, то вернуть его позицию в коллекции.
В противном случае анализировать следующий элемент Повторять шаг 2, пока значение не будет найдено либо пока не будет просмотрена вся коллекция.
Если мы достигли конца коллекции и не нашли искомого, то вернуть некоторое значение, показывающее, что нужного элемента нет.
Алгоритм, как мы и утверждали, не зависит ни от типа контейнера, к которому применяется, ни от типа искомого значения, однако для его использования необходимы:
способ обхода коллекции: переход к следующему элементу и распознавание того, что достигнут конец коллекции. При работе с встроенным типом массива мы решаем эту проблему, передавая два аргумента: указатель на первый элемент и число элементов, подлежащих обходу (в случае строк символов в стиле C передавать второй аргумент необязательно, так как конец строки обозначается двоичным нулем);
умение сравнивать каждый элемент контейнера с искомым значением. Обычно это делается с помощью оператора равенства, ассоциированного со значениями типа, или путем передачи указателя на функцию, осуществляющую сравнение;
некоторый обобщенный тип для представления позиции элемента внутри контейнера и специального признака на случай, если элемент не найден. Обычно мы возвращаем индекс элемента либо указатель на него. В ситуации, когда поиск неудачен, возвращается –1 вместо индекса или 0 вместо указателя.
Обобщенные алгоритмы решают первую проблему, обход контейнера, с помощью абстракции итератора – обобщенного указателя, поддерживающего оператор инкремента для доступа к следующему элементу, оператор разыменования для получения его значения и операторы равенства и неравенства для определения того, совпадают ли два итератора. Диапазон, к которому применяется алгоритм, помечается парой итераторов: first адресует первый элемент, а last – тот, который следует за последним. К самому элементу, адресованному итератором last, алгоритм не применяется; он служит стражем, прекращающим обход. Кроме того, last используется как возвращаемое значение с семантикой “отсутствует”. Если же значение получено, то возвращается итератор, помечающий позицию найденного элемента.
Имеется по две версии каждого обобщенного алгоритма: в одной для сравнения применяется оператор равенства, а в другой – объект-функция или указатель на функцию, реализующую сравнение. (Объекты-функции рассматриваются в разделе 12.3.) Вот, например, реализация обобщенного алгоритма find(), в котором используется оператор сравнения для типов хранимых в контейнере элементов:
template < class ForwardIterator, class Type >
ForwardIterator
find( ForwardIterator first, ForwardIterator last, Type value )
{
for ( ; first != last; ++first )
if ( value == *first )
return first;
return last;
}
ForwardIterator (однонаправленный итератор) – это один из пяти категорий итераторов, предопределенных в стандартной библиотеке. Он поддерживает чтение и запись адресуемого элемента. (Все пять категорий рассматриваются в разделе 12.4.)
Алгоритмы достигают независимости от типов за счет того, что никогда не обращаются к элементам контейнера непосредственно; доступ и обход элементов осуществляются только с помощью итераторов. Неизвестны ни фактический тип контейнера, ни даже то, является ли он контейнером или встроенным массивом. Для работы со встроенным типом массива обобщенному алгоритму можно передать не только обычные указатели, но и итераторы. Например, алгоритм find() для встроенного массива элементов типа int можно использовать так:
#include
#include
int main()
{
int search_value;
int ia[ 6 ] = { 27, 210, 12, 47, 109, 83 };
cout << "enter search value: ";
cin >> search_value;
int *presult = find( &ia[0], &ia[6], search_value );
cout << "The value " << search_value
<< ( presult == &ia[6]
? " is not present" : " is present" )
<< endl;
}
Если возвращенный указатель равен адресу &ia[6] (который расположен за последним элементом массива), то поиск оказался безрезультатным, в противном случае значение найдено.
Вообще говоря, при передаче адресов элементов массива обобщенному алгоритму мы можем написать
int *presult = find( &ia[0], &ia[6], search_value );
или
int *presult = find( ia, ia+6, search_value );
Если бы мы хотели ограничиться лишь отрезком массива, то достаточно было бы модифицировать передаваемые алгоритму адреса. Так, при следующем обращении к find() просматриваются только второй и третий элементы (напомним, что элементы массива нумеруются с нуля):
// искать только среди элементов ia[1] и ia[2]
int *presult = find( &ia[1], &ia[3], search_value );
А вот пример использования контейнера типа vector с алгоритмом find():
#include
#include
#include
int main()
{
int search_value;
int ia[ 6 ] = { 27, 210, 12, 47, 109, 83 };
vector vec( ia, ia+6 );
cout << "enter search value: ";
cin >> search_value;
vector::iterator presult;
presult = find( vec.begin(), vec.end(), search_value );
cout << "The value " << search_value
<< ( presult == vec.end()
? " is not present" : " is present" )
<< endl;
}
find() можно применить и к списку:
#include
#include
#include
int main()
{
int search_value;
int ia[ 6 ] = { 27, 210, 12, 47, 109, 83 };
list ilist( ia, ia+6 );
cout << "enter search value: ";
cin >> search_value;
list::iterator presult;
presult = find( ilist.begin(), ilist.end(), search_value );
cout << "The value " << search_value
<< ( presult == ilist.end()
? " is not present" : " is present" )
<< endl;
}
(В следующем разделе мы обсудим построение программы, в которой используются различные обобщенные алгоритмы, а затем рассмотрим объекты-функции. В разделе 12.4 мы подробнее расскажем об итераторах. Развернутое введение в обобщенные алгоритмы – предмет раздела 12.5, а их детальное обсуждение и иллюстрация применения вынесено в Приложение. В конце главы речь пойдет о случаях, когда применение обобщенных алгоритмов неуместно.)
Упражнение 12.1
Обобщенные алгоритмы критикуют за то, что при всей элегантности дизайна проверка корректности возлагается на программиста. Например, если передан неверный итератор или пара итераторов, помечающая неверный диапазон, то поведение программы не определено. Вы согласны с такой критикой? Следует ли оставить применение обобщенных алгоритмов только наиболее квалифицированным специалистам? Может быть, нужно запретить использование потенциально опасных конструкций, таких, как обобщенные алгоритмы, указатели и явные приведения типов?
12.2. Использование обобщенных алгоритмов
Допустим, мы задумали написать книжку для детей и хотим понять, какой словарный состав наиболее подходит для такой цели. Чтобы ответить на этот вопрос, нужно прочитать несколько детских книг, сохранить текст в отдельных векторах строк (см. раздел 6.7) и подвергнуть его следующей обработке:
Создать копию каждого вектора.
Слить все векторы в один.
Отсортировать его в алфавитном порядке.
Удалить все дубликаты.
Снова отсортировать, но уже по длине слов.
Подсчитать число слов, длина которых больше шести знаков (предполагается, что длина – это некоторая мера сложности, по крайней мере, в терминах словаря).
Удалить семантически нейтральные слова (например, союзы and (и), if (если), or (или), but (но) и т.д.).
Напечатать получившийся вектор.
На первый взгляд, задача на целую главу. Но с помощью обобщенных алгоритмов мы решим ее в рамках одного подраздела.
Аргументом нашей функции является вектор из векторов строк. Мы принимаем указатель на него, проверяя, не является ли он нулевым:
#include
#include
typedef vector textwords;
void process_vocab( vector *pvec )
{
if ( ! pvec ) {
// выдать предупредительное сообщение
return;
}
// ...
}
Нужно создать один вектор, включающий все элементы исходных векторов. Это делается с помощью обобщенного алгоритма copy() (для его использования необходимо включить заголовочные файлы algorithm и iterator):
#include
#include
void process_vocab( vector *pvec )
{
// ...
vector< string > texts;
vector::iterator iter = pvec->begin();
for ( ; iter != pvec->end(); ++iter )
copy( (*iter).begin(), (*iter).end(), back_inserter( texts ));
// ...
}
Первыми двумя аргументами алгоритма copy() являются итераторы, ограничивающие диапазон подлежащих копированию элементов. Третий аргумент – это итератор, указывающий на место, куда надо копировать элементы. back_inserter называется адаптером итератора; он позволяет вставлять элементы в конец вектора, переданного ему в качестве аргумента. (Подробнее мы рассмотрим адаптеры итераторов в разделе 12.4.).
Алгоритм unique() удаляет из контейнера дубликаты, расположенные рядом. Если дана последовательность 01123211, то результатом будет 012321, а не 0123. Чтобы получить вторую последовательность, необходимо сначала отсортировать вектор с помощью алгоритма sort(); тогда из последовательности 01111223 получится 0123. (Хотя на самом деле получится 01231223.)
unique() не изменяет размер контейнера. Вместо этого каждый уникальный элемент помещается в очередную свободную позицию, начиная с первой. В нашем примере физический результат – это последовательность 01231223; остаток 1223 – это, так сказать, “отходы” алгоритма. unique() возвращает итератор, указывающий на начало этого остатка. Как правило, этот итератор затем передается алгоритму erase() для удаления ненужных элементов. (Поскольку встроенный массив не поддерживает операции erase(), то семейство алгоритмов unique() в меньшей степени подходит для работы с ним.) Вот соответствующий фрагмент функции:
void process_vocab( vector *pvec )
{
// ...
// отсортировать вектор texts
sort( texts.begin(), texts.end() );
// удалить дубликаты
vector::iterator it;
it = unique( texts.begin(), texts.end() );
texts.erase( it, texts.end() );
// ...
}
Ниже приведен результат печати вектора texts, объединяющего два небольших текстовых файла, после применения sort(), но до применения unique():
a a a a alice alive almost
alternately ancient and and and and and and
and as asks at at beautiful becomes bird
bird blows blue bounded but by calling coat
daddy daddy daddy dark darkened darkening distant each
either emma eternity falls fear fiery fiery flight
flowing for grow hair hair has he heaven,
held her her her her him him home
houses i immeasurable immensity in in in in
inexpressibly is is is it it it its
journeying lands leave leave life like long looks
magical mean more night, no not not not
now now of of on one one one
passion puts quite red rises row same says
she she shush shyly sight sky so so
star star still stone such tell tells tells
that that the the the the the the
the there there thing through time to to
to to trees unravel untamed wanting watch what
when wind with with you you you you
your your
После применения unique() и последующего вызова erase() вектор texts выглядит следующим образом:
a alice alive almost alternately ancient
and as asks at beautiful becomes bird blows
blue bounded but by calling coat daddy dark
darkened darkening distant each either emma eternity falls
fear fiery flight flowing for grow hair has
he heaven, held her him home houses i
immeasurable immensity in inexpressibly is it its journeying
lands leave life like long looks magical mean
more night, no not now of on one
passion puts quite red rises row same says
she shush shyly sight sky so star still
stone such tell tells that the there thing
through time to trees unravel untamed wanting watch
what when wind with you your
Следующая наша задача – отсортировать строки по длине. Для этого мы воспользуемся не алгоритмом sort(), а алгоритмом stable_sort(), который сохраняет относительные положения равных элементов. В результате для элементов равной длины сохраняется алфавитный порядок. Для сортировки по длине мы применим собственную операцию сравнения “меньше”. Один из возможных способов таков:
bool less_than( const string & s1, const string & s2 )
{
return s1.size() < s1.size();
}
void process_vocab( vector *pvec )
{
// ...
// отсортировать элементы вектора texts по длине,
// сохранив также прежний порядок
stable_sort( texts.begin(), texts.end(), less_than );
// ...
}
Нужный результат при этом достигается, но эффективность существенно ниже, чем хотелось бы. less_than() реализована в виде одной инструкции. Обычно она вызывается как встроенная (inline) функция. Но, передавая указатель на нее, мы не даем компилятору сделать ее встроенной. Способ, позволяющий добиться этого, –применение объекта-функции:
// объект-функция - операция реализована с помощью перегрузки
// оператора operator()
class LessThan {
public:
bool operator()( const string & s1, const string & s2 )
{ return s1.size() < s2.size(); }
};
Объект-функция – это класс, в котором перегружен оператор вызова operator(). В теле этого оператора и реализуется логика функции, в данном случае сравнение “меньше”. Определение оператора вызова выглядит странно из-за двух пар скобок. Запись
operator()
говорит компилятору, что мы перегружаем оператор вызова. Вторая пара скобок
( const string & s1, const string & s2 )
задает передаваемые ему формальные параметры. Если сравнить это определение с предыдущим определением функции less_than(), мы увидим, что, за исключением замены less_than на operator(), они совпадают.
Объект-функция определяется так же, как обычный объект класса (правда, в данном случае нам не понадобился конструктор: нет членов, подлежащих инициализации):
LessThan lt;
Для вызова экземпляра перегруженного оператора мы применяем оператор вызова к нашему объекту класса, передавая необходимые аргументы. Например:
string st1( "shakespeare" );
string st2( "marlowe" );
// вызывается lt.operator()( st1, st2 );
bool is_shakespeare_less = lt( st1, st2 );
Ниже показана исправленная функция process_vocab(), в которой алгоритму stable_sort() передается безымянный объект-функция LessThan():
void process_vocab( vector *pvec )
{
// ...
stable_sort( texts.begin(), texts.end(), LessThan() );
// ...
}
Внутри stable_sort() перегруженный оператор вызова подставляется в текст программы как встроенная функция. (В качестве третьего аргумента stable_sort() может принимать как указатель на функцию less_than(), так и объект класса LessThan, поскольку аргументом является параметр-тип шаблона. Подробнее об объектах-функциях мы расскажем в разделе 12.3.)
Вот результат применения stable_sort() к вектору texts:
a i
as at by he in is it no
of on so to and but for has
her him its not now one red row
she sky the you asks bird blue coat
dark each emma fear grow hair held home
life like long mean more puts same says
star such tell that time what when wind
<< Пред. стр. 52 (из 121) След. >>
Список литературы по разделу