«другом» которого она является.
Несмотря на то что объявление дружественной функции выполняется внутри
класса, ее определение должно быть сделано за его пределами.
Объявление дружественной функции может быть сделано в закрытой или от-крытой части класса.
Указатель this не передается дружественной функции.
Функцию можно сделать «другом» нескольких классов.
Если функция является «другом» нескольких классов, то ее объявление необходимо поместить во всех этих классах.
Если класс объявлен «другом» другого класса, то все функции-члены этого
класса могут получить доступ к закрытым членам класса, содержащего объявление дружественного класса.
Перегруженная операторная функция может быть объявлена дружественной
для повышения ее универсальности.
Дружественные функции нарушают систему типов C++, поэтому использовать
их следует как можно реже и с осторожностью.
Если конструктор объявлен с ключевым словом explicit, компилятор не может
использовать его для выполнения неявных преобразований.
Если член данных const-объекта должен оставаться изменяемым, включите в его
определение ключевое слово mutable.
Расширенные возможности C++
255
Пространство имен действует как контейнер для связанных типов
namespace
{
class A { } ;
class B { } ;
}
Пространство имен можно разбить на несколько файлов, поскольку оно является
логическим контейнером.
Допустимы вложенные пространства имен.
Типы данных могут иметь одинаковые имена, если они принадлежат разным
пространствам имен.
Пространства имен могут иметь псевдонимы, к примеру:
namespace s = std ;
Существуют два способа доступа к имени в пространстве имен:
• через оператор ::;
• при помощи ключевого слова using.
Можно получить тип объекта во время выполнения программы, используя оператор typeid.
Оператор typeid может использоваться с объектом, указателем, переменной или
выражением, например typeid ( 45 ), typeid ( ptr ), typeid ( *ptr ).
Тип, возвращаемый typeid, можно сравнить с другим возвращаемым типом, используя операторы == и !=:
if ( typid ( 45 ) == typeid ( i ) )
Следующие преобразования типов происходят неявным образом:
• Расширяющие преобразования, в частности присвоение целого типа (int) двойному (double).
• Присвоение адреса объекта производного класса указателю на базовый класс.
Эксплицитное (явное) преобразование можно выполнять при помощи четырех
операторов приведения типов:
• static_cast;
• dynamic_cast;
• const_cast;
• reinterpret_cast.
static_cast применяется для:
• преобразований ограничивающего типа;
• преобразований указателя к пустому типу (void*) для отображения адреса
массива.
256
Глава 9
dynamic_cast применяется для преобразования указателей с приведением вниз.
При использовании dynamic_cast во время работы программы можно проверить, является ли преобразование безопасным.
const_cast применяется для преобразования константных объектов в некон-стантные и наоборот.
reinterpret_cast применяется для:
• преобразования указателя в целое число и наоборот;
• преобразования между несвязанными типами указателей.
И этот вид приведения небезопасен.
'.* ' и '->*' называются операторами указателей на члены класса.
'.* ' и '->*' используются для одновременного доступа и разыменования.
'.* ' и '->*' могут применяться для доступа к открытым функциям-членам класса.
Шаблоны
Вместо того, чтобы переписывать и сопровождать набор
похожих функций или классов, работающих с различными
типами данных, можно создать обобщенные функции/классы
и позволить компилятору заниматься выбором конкретных
версий. В этой главе мы рассмотрим, как это реализуется
258
Глава 10
Шаблоны функций
• Что происходит во время компиляции?
Шаблоны функций для пользовательских типов
Еще одна шаблонная функция
• Явная специализация обобщенной функции
Функция с набором обобщенных типов
Шаблоны и макросы
Сортировка на основе шаблона
Шаблоны классов
Шаблон класса связного списка
Полезные советы по шаблонам
Вариативные шаблоны
Области применения шаблонов
Упражнения
Важное
Шаблоны
259
аблоны представляют собой механизм, позволяющий применять одну
функцию или класс для обработки широкого диапазона различных типов
Шданных. При помощи шаблонов мы можем создать единый общий класс
или функцию, которые работают с данными многих типов, вместо того, чтобы создавать отдельный класс/функцию для каждого из этих типов. Применительно
к функциям они называются шаблонами функций (обобщенными функциями), а применительно к классам — шаблонами классов (обобщенными классами). Сначала мы рассмотрим шаблоны функций, а затем перейдем к шаблонам классов.
Шаблоны функций
Допустим, мы хотим написать функцию, возвращающую наименьшее значение
двух переданных ей чисел. Это будет очень простая функция: если числовые параметры имеют разные типы в разных вызовах, нам придется написать несколько
перегруженных версий:
// int-специализация min
int myMin ( int a, int b )
{
return ( a < b ) ? a : b ;
}
// long-специализация min
long myMin ( float a, float b )
{
return ( a < b ) ? a : b ;
}
// char-специализация min
char myMin ( char a, char b )
{
return ( a < b ) ? a : b ;
}
// etc...
У такого подхода выявляется три недостатка:
Приходится многократно повторять один и тот же код в разных функциях.
Набор версий одной функции занимает больше дискового пространства.
Если мы решим внести изменение в одну функцию, мы должны помнить о том, чтобы сделать аналогичные изменения во всех остальных версиях этой функции.
Таким образом, сопровождение программы становится утомительным делом.
Вот бы написать одну такую функцию, работающую с различными типами данных!
Именно для этого и предназначены шаблоны функций.
В следующей программе показано, как написать обобщенную функцию myMin( ), принимающую в качестве аргументов любой встроенный тип данных. Мы обращаемся к этой функции из main( ), передавая ей различные типы данных.
260
Глава 10
#include <iostream>
using namespace std ;
template < class T > T myMin ( T a, T b )
{
return ( a < b ) ? a : b ;
}
int main( )
{
int i = 10, j = 20 ;
cout << myMin ( i, j ) << endl ;
float a = 3.14f, b = -6.28f ;
cout << myMin ( a, b ) << endl ;
char ch = 'A', dh = 'Z' ;
cout << myMin ( ch, dh ) << endl ;
double d = 1.1, e = 1.11 ;
cout << myMin ( d, e ) << endl << endl ;
return 0 ;
}
И вот какие результаты генерирует эта программа:
10
-6.28
A
1.1
Как видите, функция myMin( ) теперь работает с разными типами данных, которые
мы передаем ей в качестве аргументов. Разве это не многократное использование
программного кода? Да, но иного типа. Наследование и отношения включения
позволяют повторно использовать объектный код, а шаблоны — исходный код.
Шаблоны могут значительно уменьшить размер исходного кода и повысить его
гибкость без снижения безопасности.
Давайте теперь разберемся, что придает обобщенной функции гибкость для работы
с различными типами данных. Перед нами определение функции myMin( ): template < class T > T mymin ( T a, T b )
{
return ( a < b ) ? a : b ;
}
Данная синтаксическая конструкция называется шаблоном функции. В шаблоне
функции тип данных может быть представлен «заполнителем» (в нашем случае T), могущим обозначать любой тип. У имени T нет никакого особенного значения.
Шаблоны
261
Вместо него мы можем воспользоваться любым другим именем, будь то type, mytype и т. п. Такой элемент, как T, называют обобщенным параметром. Везде, где
в определении функции обычно записывается конкретный тип данных, такой как
int, мы подставляем обобщенный параметр шаблона, т. е. T.
Что происходит во время компиляции?
Сам по себе просмотр шаблона функции не побуждает компилятор к каким-либо
конкретным действиям, помимо его запоминания для применения в будущем. Компилятор не может сгенерировать какой-либо код, поскольку пока что неизвестно, с каким типом данных будет работать функция. Генерация кода происходит, когда
функция фактически вызывается из программы с помощью таких операторов, как
cout << endl << myMin ( i, j ) ;
Встречая такой вызов функции, компилятор понимает, что задействуется тип int, поскольку это тип аргументов переменных i и j. Тогда он генерирует специализацию (конкретную версию) myMin( ) для типа int, заменяя каждый T на int. Эту
процедуру нередко называют реализацией (instantiating) шаблонной функции.
Компилятор также заменяет вызов myMin(i, j) вызовом только что порожденной
функции.
Аналогичным образом выражение myMin(a, b) побуждает компилятор сгенерировать специализацию myMin( ) для типа float, а затем к ней обратиться. Точно так
же вызов myMin(d, e) генерирует конкретную версию функции, обрабатывающую
тип double. Заметьте, что компилятор генерирует только одну версию myMin( ) для каждого типа данных независимо от количества вызовов, сделанных для этого
типа.
Помогают ли шаблоны экономить память? Не совсем, поскольку даже когда мы
используем шаблоны, генерируются четыре функции (для int, float, char и double).
Преимущество лишь в том, что нам не нужно эти функции создавать и сопровождать. Компилятор создает их из нашей обобщённой версии. Это сокращает и упрощает текст программы. Еще одно преимущество заключается в том, что, если мы
хотим модифицировать нашу функцию, нам потребуется внести изменения лишь
в одной части программы, а не в четырех разных частях.
Шаблоны функций
для пользовательских типов
Функция myMin( ) может работать даже с пользовательскими типами данных, такими как Date, при условии, что в классе Date перегружен оператор «меньше» (<) для сравнения двух объектов Date. Нам также потребуется предоставить функцию
перегруженного оператора >> для вывода дат (устройство и работа такой функции
уже обсуждались в главе 8). Проиллюстрируем вышесказанное:
#include <iostream>
using namespace std ;
262
Глава 10
class Date
{
private :
int day, mon, year ;
public :
Date ( int d, int m, int y )
{
day = d ;mon = m ;year = y ;
}
int operator < ( Date dt )
{
if ( year < dt.year )
return 1 ;
if ( year == dt.year && mon < dt.mon )
return 1 ;
if ( year == dt.year && mon == dt.mon && day < dt.day ) return 1 ;
return 0 ;
}
friend ostream& operator << ( ostream &o, Date &dt ) ;
} ;
ostream& operator << ( ostream &o, Date &dt )
{
o << dt.day << "/" << dt.mon << "/" << dt.year ; return o ;
}
template < class T > T myMin ( T a, T b )
{
return ( a < b ) ? a : b ;
}
int main( )
{
int i = 10, j = 20 ;
cout << myMin ( i, j ) << endl ;
Date dt1 ( 17, 11, 62 ), dt2 ( 23, 12, 65 ) ;
cout << myMin ( dt1, dt2 ) << endl << endl ;
return 0 ;
}
Еще одна шаблонная функция
Для закрепления материала спроектируем еще одну обобщенную функцию, в которой производится изменение значения (это еще называется свопингом) двух переменных:
Шаблоны
263
#include <iostream>
using namespace std ;
class Date
{
private :
int day, mon, year ;
public :
Date ( int d = 0, int m = 0, int y = 0 )
{
day = d ;mon = m ;year = y ;
}
friend ostream& operator << ( ostream &o, Date &dt ) ;
} ;
ostream& operator << ( ostream &o, Date &dt )
{
o << dt.day << "/" << dt.mon << "/" << dt.year ; return o ;
}
template < class T >
void mySwap ( T &a, T &b )
{
T c ;
c = a ;
a = b ;
b = c ;
}
int main( )
{
int i = 10, j = 20 ;
mySwap ( i, j ) ;
cout << i << "\t" << j << endl ;
char ch = 'A', dh = 'Z' ;
mySwap ( ch, dh ) ;
cout << ch << "\t" << dh << endl ; Date dt1 ( 17, 11, 62 ), dt2 ( 23, 12, 65 ) ;
mySwap ( dt1, dt2 ) ;
cout << dt1 << "\t" << dt2 << endl ; return 0 ;
}
В программе определяется шаблон функции с именем mySwap( ). Из этой обобщенной функции компилятор генерирует специализации, меняющие местами зна-
264
Глава 10
чения переменных типа int, char и Date. В конструкторе класса Date для аргументов мы задействовали значения по умолчанию. Это требуется для создания объектов класса Date в функции mySwap( ), когда она вызывается для свопинга значений
двух таких объектов.
Заметьте, что стандартные преобразования типов не применяются к шаблонам
функций. Когда встречается вызов обобщенной функции, компилятор сначала про-сматривает существующие экземпляры в поиске «точного совпадения» предоставленных параметров.
В случае неудачи он пытается сгенерировать новый экземпляр, соответствующий
критериям «точного совпадения». Если и это не удается, то компилятор выдает
ошибку.
Явная специализация обобщенной функции
Что если мы хотим, чтобы функция вела себя одинаково для всех типов данных, кроме одного?
В таком случае мы можем переопределить шаблон функции для данного конкретного типа. Нам просто потребуется предоставить конкретную версию функции для
этого типа:
void mySwap ( double a, double b )
{
// место для кода
}
Такое объявление позволяет определить отдельную функцию для переменных типа
double. Как и к прочим нешаблонным функциям, здесь применимы стандартные
средства преобразования типов (к примеру, преобразование переменной типа float в double).
Функция с набором обобщенных типов
Возможно создать шаблонную функцию, принимающую во время вызова несколько обобщенных типов аргументов, что проиллюстрировано в следующей короткой
программе:
#include <iostream>
using namespace std ;
template < class T, class S, class Z > void fun ( T a, S b, Z c )
{
cout << a << endl << b << endl << c << endl ;
}
int main( )
{
int i = 10 ;
Шаблоны
265
float j = 3.14f ;
char ch = 'A' ;
fun ( i, j, ch ) ;
return 0 ;
}
Вы, должно быть, заметили, что в этой программе синтаксис шаблонной функции
чуть-чуть отличается от предыдущих примеров. Мы поместили ключевое слово
template и собственно объявление функции в одну строку:
template < class T, class S, class Z > void fun ( T a, S b, Z c ) Это никак не связано с тем, что обобщенной функции передается несколько аргументов. С тем же успехом мы могли бы применить многострочную запись в программах, приведенных выше:
template < class T, class S, class Z > void
fun ( T a, S b, Z c )
Шаблоны и макросы
Во многих отношениях шаблоны действуют как макросы препроцессора, заменяя
аргумент шаблона заданным типом. Тем не менее существует множество различий
между макросом, таким как
# define min( i, j ) ( ( i ) < ( j ) ? ( i ) : ( j ) )
и схожей обобщенной функцией
template < class T >
T min ( T i, T j )
{
return ( i < j ) ? i : j ) ;
}
Приведенный выше макрос также выполняет простую замену текста и, следовательно, может обрабатывать любой тип данных. Однако у него есть ряд недостатков:
Макрос развертывается без проверки типов.
При этом не указывается тип возвращаемого значения, и потому компилятор не
может определить, присваиваем ли мы его несовместимой переменной.
В макросе параметры i и j оцениваются дважды. Если у некоторого параметра
имеется постинкрементная переменная, приращение значения будет произведено два раза.
При развертывании макросов препроцессором сообщения об ошибках компилятора будут относиться к развернутому макросу, а не к самому определению макроса, что затрудняет поиск ошибок.
Одним словом, макросы сильно уступают шаблонам.
266
Глава 10
Сортировка на основе шаблона
Давайте теперь разработаем функцию сортировки выборкой (selection sort) на
основе шаблона, которая сможет сортировать массивы как стандартных, так и
пользовательских типов.
Для этого мы определили класс Date, содержащий функцию перегруженного оператора для сравнения двух объектов Date с целью установить, какой из них больше
другого. И реализуем дружественную функцию для отображения объекта Date:
#include <iostream>
using namespace std ;
class Date
{
private :
int day, mon, year ;
public :
Date ( int d = 0, int m = 0, int y = 0 )
{
day = d ;
mon = m ;
year = y ;
}
int operator > ( Date dt )
{
if ( year > dt.year )
return 1 ;
if ( year == dt.year && mon > dt.mon )
return 1 ;
if ( year == dt.year && mon == dt.mon && day > dt.day ) return 1 ;
return 0 ;
}
friend ostream& operator << ( ostream &o, Date &dt ) ;
} ;
ostream& operator << ( ostream &o, Date &dt )
{
o << dt.day << "/" << dt.mon << "/" << dt.year ; return o ;
}
template < class T >
void selectionSort ( T a[ ], int sz )
{
T temp ;
Шаблоны
267
for ( int i = 0 ;i < sz - 1 ;i++ )
{
for ( int j = i + 1 ;j < sz ;j++ )
{
if ( a[ i ] > a[ j ] )
{
temp = a[ i ] ;
a[ i ] = a[ j ] ;
a[ j ] = temp ;
}
}
}
}
int main( )
{
int arr[ ] = { -12, 23, 14, 0, 245, 78 , 66, -9 } ;
Date dtarr[ ] = {
Date ( 17, 11, 62 ), Date ( 23, 12, 65 ),
Date ( 12, 12, 78 ), Date ( 23, 10, 69 )
} ;
int i ;
selectionSort ( arr, 8 ) ;
for ( i = 0 ;i < 8 ;i++ )
cout << arr[ i ] << endl ;
cout << endl << endl ;
selectionSort ( dtarr, 4 ) ;
for ( i = 0 ;i < 4 ;i++ )
cout << dtarr[ i ] << endl ;
return 0 ;
}
Мы не станем здесь обсуждать работу алгоритма сортировки выборкой. Эта тема
достаточно подробно рассматривается в учебных курсах по структурам данных.
Наша с вами цель — понять, как написать шаблон функции, способный работать
как со встроенными, так и с пользовательскими типами данных.
Шаблоны классов
Концепция шаблонов распространяется и на классы. Шаблоны классов (или обобщенные классы) обычно используются для классов хранения данных. Такие классы
также называют контейнерными классами.
Вспомните, как в главе 6 мы разработали класс Stack для ведения LIFO-списка.
Однако он мог хранить данные лишь одного встроенного типа, например целые
268
Глава 10
числа. Для хранения в стеке данных типа float нам пришлось бы определить совершенно новый класс. Из этого следует, что для каждого нового типа данных, подлежащих сохранению, должен быть создан новый класс стека. Не лучше ли написать единую спецификацию класса, которая работала бы для всех типов? Лучше, конечно.
Следующая программа продемонстрирует такой обобщенный класс в действии:
#include <iostream>
using namespace std ;
const int MAX = 10 ;
template < class T > class Stack
{
private :
T stk[ MAX ] ;
int top ;
public :
Stack( )
{
top = -1 ;
}
void push ( T data )
{
if ( top == MAX - 1 )
cout << "Стек переполнен" << endl ;
else
{
top++ ;
stk[ top ] = data ;
}
}
T pop( )
{
if ( top == -1 )
{
cout << "Стек пуст" << endl ;
return NULL ;
}
else
{
T data = stk[ top ] ;
top-- ;
return data ;
}
}
} ;
Шаблоны
269
class Complex
{
private :
float real, imag ;
public :
Complex ( float r = 0.0, float i = 0.0 )
{
real = r ;
imag = i ;
}
friend ostream& operator << ( ostream &o, Complex &c ) ;
} ;
ostream& operator << ( ostream &o, Complex &c )
{
o << "( " << c.real << ", " << c.imag << " )" ; return o ;
}
int main( )
{
Stack < int > s1 ;
s1.push ( 10 ) ;
s1.push ( 20 ) ;
s1.push ( 30 ) ;
cout << s1.pop( ) << endl ;
cout << s1.pop( ) << endl ;
cout << s1.pop( ) << endl ;
Stack < float > s2 ;
s2.push ( 3.14f ) ;
s2.push ( 6.28f ) ;
s2.push ( 8.98f ) ;
cout << s2.pop( ) << endl ;
cout << s2.pop( ) << endl ;
cout << s2.pop( ) << endl ;
Complex c1 ( 1.5f, 2.5f ), c2 ( 3.5f, 4.5f ), c3 ( 1.2f, 0.6f ) ;
Stack < Complex > s3 ;
s3.push ( c1 ) ;
s3.push ( c2 ) ;
s3.push ( c3 ) ;
cout << s3.pop( ) << endl ;
cout << s3.pop( ) << endl ;
cout << s3.pop( ) << endl ;
return 0 ;
}
270
Глава 10
Здесь мы создали три стека — s1, s2 и s3 — и поместили в каждый из них по три
значения. Затем мы извлекли значения из трех стеков и отобразили их на экране.
В результате выполнения этой программы получим:
30
20
10
8.98
6.28
3.14
( 1.2, 0.6 )
( 3.5, 4.5 )
( 1.5, 2.5 )
Можно заметить, что порядок, в котором элементы извлекаются из стека, полностью противоположен порядку, в котором они были в него помещены.
Способ создания обобщенного класса аналогичен тому, что применяется для создания обобщенной функции. Ключевое слово template и < class T > свидетельствуют
о том, что весь класс будет шаблоном.
template < class T > class stack
{
// данные и функции-члены с использованием аргумента шаблона T
} ;
Затем «заполнитель» шаблона T используется в каждой части спецификации класса, где есть ссылка на тип массива stk.
Таких частей три:
Определение stk.
Тип аргумента функции push( ).
Тип возвращаемого значения функции pop( ).
Мы также объявили класс с именем Complex, а затем работали с объектами этого
класса, помещая их в стек и извлекая их из него. Это доказывает, что мы также можем создавать стеки пользовательских объектов из обобщенного класса. Чтобы
иметь возможность отображать объекты класса Complex при помощи cout, мы
перегрузили оператор <<.
Как мы уже знаем, создание экземпляра обобщенной функции происходит при ее
вызове. В отличие от этого, классы создаются путем определения объекта с использованием аргументов шаблона. К примеру
Stack < int > s1 ;
создает объект s1 — стек, предназначенный для хранения чисел целого типа. Компилятор резервирует область памяти для данных этого объекта, используя тип int везде, где в спецификации класса появляется аргумент шаблона T. Он также резервирует место для компонентных функций (если они еще не были помещены в па-
Шаблоны
271
мять другим объектом типа Stack < int >). Эти функции-члены также работают исключительно с типом int.
Когда мы создаем объект Stack, в котором хранятся единицы другого типа, скажем, вещественного, то создается пространство для данных, а также новый набор функций-членов, которые работают с этим типом.
Как и в случае с обычными классами, можно ли не определять функции-члены
обобщенного класса за его пределами? Да, это возможно, но для этого, как показано ниже, требуется другая форма записи:
template < class T >
void Stack < T > :: push ( T data )
{
if ( top == MAX - 1 )
cout << endl << "Стек переполнен" ;
else
{
top++ ;
stk[ top ] = data ;
}
}
Обратите внимание на тот факт, что выражение template < class T > должно пред-шествовать не только определению класса, но и каждой компонентной функции, определенной за пределами класса. Имя Stack < T > используется для обозначения
класса, членом которого является функция push( ).
Шаблон класса связного списка
Давайте теперь при помощи шаблонов спроектируем класс связного списка (linked list class) общего назначения. При помощи такого обобщенного класса можно легко
сопровождать связный список чисел целого или вещественного типа, или же связный список пользовательского типа данных с именем Employee (Сотрудник).
Допустим, что пользовательский тип данных хранит сведения об имени (name), возрасте (age) и зарплате (salary) сотрудника. Классу Employee потребуются две
компонентные функции — конструктор и перегруженный оператор <<.
Ниже я привожу набросок программы, реализующей обобщенный класс для поддержки двух связных списков — одного для целых чисел и другого для данных
о сотрудниках. Вы можете попытаться самостоятельно разработать функции класса
LinkedList и класса Employee.
#include <string>
#include <iostream>
using namespace std ;
class Employee
{
272
Глава 10
private :
string name ;
int age ;
float sal ;
public :
Employee ( string n = "", int a = 0, float s = 0.0 ) ;
friend ostream& operator << ( ostream& s, emp& e ) ;
} ;
template < class T > class LinkList
{
private :
struct node
{
T data ;
node *link ;
} *p ;
public :
LinkList ( ) ;
~ LinkList ( ) ;
void append ( T ) ;
void addAtBeg ( T ) ;
void addAfter ( int, T ) ;
void del ( int ) ;
void display( ) ;
int count( ) ;
} ;
int main( )
{
LinkList < int > l1 ;
cout << "Число элементов в связном списке = " << l1.count( ) << endl ; l1.append ( 11 ) ;
l1.append ( 22 ) ;
l1.append ( 33 ) ;
l1.append ( 44 ) ;
l1.append ( 55 ) ;
l1.append ( 66 ) ;
l1.addAtBeg ( 100 ) ;
l1.addAtBeg ( 200 ) ;
l1.addAfter ( 3, 333 ) ;
l1.addAfter ( 6, 444 ) ;
l1.display( ) ;
cout << "Число элементов в связном списке = " << l1.count( ) << endl ; l1.del ( 200 ) ;
l1.del ( 66 ) ;
l1.del ( 0 ) ;
l1.del ( 333 ) ;
Шаблоны
273
l1.display( ) ;
cout << "Число элементов в связном списке = " << l1.count( ) << endl ; LinkList < Employee > l2 ;
cout << "Число элементов в связном списке = " << l2.count( ) << endl ; Employee e1 ( "Sanjay", 23, 1100.00 ) ;
Employee e2 ( "Rahul", 33, 3500.00 ) ;
Employee e3 ( "Rakesh", 24, 2400.00 ) ;
Employee e4 ( "Sanket", 25, 2500.00 ) ;
Employee e5 ( "Sandeep", 26, 2600.00 ) ;
l2.append ( e1 ) ;
l2.append ( e2 ) ;
l2.append ( e3 ) ;l2.append ( e4 ) ;
l2.append ( e5 ) ;l2.display( ) ;
l2.del ( 3 ) ;
l2.display( ) ;
cout << "Число элементов в связном списке = " << l2.count( ) << endl ; l2.addAtBeg ( e5 ) ;
l2.display( ) ;
l2.addAfter ( 3, e1 ) ;
l2.display( ) ;
cout << "Число элементов в связном списке = " << l2.count( ) << endl ; return 0 ;
}
Полезные советы по шаблонам
Позвольте мне теперь дать несколько практических советов.
При объявлении обобщенной функции или класса мы можем заменить ключевое
слово class на ключевое слово typename, как показано ниже.
template < typename T >
void selectionSort ( T a[ ], int sz )
{
// ваш код
}
template < typename T > class Stack
{
// ваш код
} ;
Имя обобщенного класса (к примеру, Stack) в разных контекстах оформляется
по-разному. Так, в спецификации класса это просто имя, как в
class Stack {
} ;
274
Глава 10
Для функций-членов, определенных вне класса, это имя класса плюс имя аргумента шаблона, как в
void Stack < T > :: push ( T data ) {
}
Ну и наконец, когда вы определяете фактические объекты для хранения определенного типа данных, это имя класса плюс этот конкретный тип, как в
Stack < float > s1 ; // объект типа Stack <float>
Применение нужной формы записи в нужном контексте требует постоянного
внимания. Легко забыть добавить < T > или < float > к элементу Stack. Компилятор не терпит таких ошибок.
Будьте аккуратны с синтаксисом, когда компонентная функция возвращает значение собственного класса. Допустим, мы определили обобщенный класс с именем Sample. Если функция-член fun( ) этого класса возвращает тип Sample, и мы должны определить эту функцию за пределами обобщенного класса, нам
нужно использовать Sample < T > для возвращаемого типа, а перед ним оператор разрешения контекста, как показано ниже:
Sample < T > Sample < T > :: fun ( Sample s )
{
}
С другой стороны, имя класса, применяемое в качестве типа аргумента функции, не должно включать элемент < T >.
Аргументы шаблона могут принимать значения по умолчанию. Затем значения
этих аргументов становятся константами времени компиляции для этого конкретного экземпляра шаблона. Приведем пример:
template < class T, int max = 50 > class Stack
{
private :
T arr[ max ] ;
} ;
Этот обобщенный класс можно задействовать при помощи таких операторов, как
Stack < int, 10 > s1 ; // может хранить 10 целых чисел в стеке
Stack < float > s2 ; // может хранить 50 чисел вещественного типа в стеке
Как и в случае функций с исходными значениями для аргументов, здесь также
значения по умолчанию могут быть присвоены конечным аргументам списка
аргументов шаблона.
Мы можем наследовать новый шаблон от существующего. Например,
template < class T >
class NewSample : public Sample < T >
{
} ;
Шаблоны
275
Всякий раз, когда создается экземпляр шаблона, код в теле шаблона генерирует-ся заново. Если некоторая часть функционала шаблона не зависит от типа данных, ее можно переместить в общий базовый класс, чтобы не воспроизводить
этот код лишний раз.
Шаблоны следует применять при создании типобезопасного класса коллекции, способного обрабатывать данные любого типа.
Вариативные шаблоны
Вариативный шаблон — это обобщенная функция или класс, поддерживающий
произвольное количество аргументов. В следующей программе продемонстрировано, как при помощи обобщенной функции с переменным числом аргументов получить сумму переданных ей аргументов:
#include <iostream>
using namespace std ;
template < class T > double getSum ( T t )
{
return t ;
}
template < class T, class... S > double getSum ( T first, S ... rest )
{
return first + getSum ( rest... ) ;
}
int main( )
{
double s1 = getSum ( 10, 20, 30 ) ;
double s2 = getSum ( 1.5, 2.5, 3.5, 4.5 ) ;
double s3 = getSum ( 10, 2.5, 20, 3.5 ) ;
cout << s1 << "\t" << s2 << "\t" << s3 << endl ;
}
В теле основной функции мы обращаемся к getSum( ) с произвольным количеством
аргументов. При каждом вызове ожидается, что функция getSum( ) вернет значение
типа double, представляющее сумму переданных ей аргументов. Интересно, что
у нас есть две реализации обобщенной функции getSum( ). Первая получает лишь
один аргумент, тогда как второй передается переменное число аргументов. Обратите внимание на использование многоточий ( ... ) и их положение во второй реализации.
template < class T, class... S > double getSum ( T first, S... rest )
{
return first + getSum ( rest... ) ;
}
276
Глава 10
Многоточие используется вариативной функцией в различных формах записи: Выражение class... S представляет несколько типов, которые можно обозначить
как S1, S2, S3 и т. д. S часто называют пакетом параметров, подразумевая под
этим набор типов.
Выражение S... rest указывает на то, что функция getSum( ) рассчитана на получение нескольких аргументов разных типов, кроме первого аргумента типа T.
Выражение rest... указывает на то, что функция getSum( ) будет вызываться
рекурсивно, принимая значения, содержащиеся в rest.
Посмотрим теперь, как будут работать рекурсивные вызовы. Первая версия
getSum( ) является основной, а вторая — рекурсивной. Первая версия принимает
один аргумент T, тогда как вторая — один или несколько аргументов T и S.
Вызов getSum ( 10, 20, 30 ) развертывается следующим образом:
getSum ( 10, 20, 30 ) ;
10 + getSum ( 20, 30 ) ;
10 + ( 20 + getSum (30 ) ) ;
10 + ( 20 + getSum ( 30 ) ) ;
В первых трех обращениях вызывается рекурсивная версия getSum( ), тогда как
при последнем вызове задействуется основная версия.
Области применения шаблонов
Теперь мы знаем, что обобщенная функция/класс представляет собой семейство
функций/классов. Полезность шаблонов для программистов на C++ трудно пере-оценить. Они часто применяются в крупных базах исходного кода с целью многократного использования и повышения гибкости программ.
Стандартная библиотека C++ предоставляет множество ценных классов шаблонов.
Среди них:
Классы «умных указателей», способствующих предотвращению утечек памяти
и недействительных ссылок.
Классы библиотеки iostream, позволяющие осуществлять ввод-вывод на C++.
В дополнение к этому стандартная библиотека шаблонов (STL) содержит множество классов для эффективного и элегантного управления коллекциями различных
типов. Библиотека STL подробно обсуждается в главе 12.
1. Укажите, верны ли следующие утверждения:
От обобщенного класса можно наследовать новый класс.
Если есть обобщенная функция с именем max( ), то конкретная ее версия будет
создана при вызове max( ) с новым типом.
Шаблоны
277
Компилятор генерирует лишь одну версию обобщенной функции для каждого
типа данных, независимо от количества вызовов, сделанных для этого типа.
Применение шаблонов экономит память.
Мы можем задать явную специализацию обобщенной функции для определенного типа данных.
Обобщенная функция может принимать несколько типов аргументов.
Шаблоны типобезопасны, а макросы нет.
Обобщенные классы, как правило, применяются для контейнерных классов.
Функция-член обобщенного класса может быть определена за его пределами.
Аргументы шаблона могут принимать значения по умолчанию.
При определении обобщенной функции следует использовать форму записи
template < class T >, а при определении обобщенного класса — template
< typename T >.
Параметр обобщенной функции (обычно обозначаемый как T, S, Z и т. п.) может
использоваться для указания обобщенных типов функции, для указания типа
возвращаемого значения и для объявления переменных в теле функции.
Имена параметров шаблона в определениях шаблона должны быть уникальными.
Посредством одного сегмента кода шаблоны позволяют обозначить весь диапазон вызываемых родственных перегруженных функций или весь диапазон родственных классов.
Все конкретные версии, сгенерированные из обобщенной функции, имеют одинаковое имя.
2. Решите следующие задачи:
Разработайте обобщенную функцию для проверки обобщенного класса LinkedList, рассмотренного в этой главе. Вызовите эту обобщенную функцию из main( ).
Составьте программу, реализующую бинарное дерево в качестве обобщенного
класса.
Составьте программу для реализации двусвязного списка в качестве обобщенного класса.
Напишите обобщенную функцию с переменным числом аргументов, отобра-
жающую переменное количество переданных ей параметров.
Напишите вариативную обобщенную функцию с переменным количеством
аргументов, вычисляющую выражение x + x2 + ( x2 )2 + ( ( x2 )2 ) 2 + ...
278
Глава 10
Шаблоны являются средством многократного использования на уровне исходного кода, тогда как наследование и отношения включения — средствами многократного использования на уровне объектного кода.
Можно создавать обобщенные функции, а также обобщенные классы.
Шаблон функции/класса можно использовать с любым встроенным или пользовательским типом данных.
Форма записи определения и вызова обобщенной функции:
// определение обобщенной функции
template < class T >
// либо
template < typename T > void printArray ( T[ ] arr )
{
..
}
// вызов обобщенной функции
int intarr[ ] = { 10, -2, 37, 42, 15 } ;
printArray ( intarr ) ;
Обобщенная функция может принимать несколько типов, к примеру
template < class T, class S, class Z >
void printTypes ( T a, S b, Z c )
{
..
}
Форма записи для применения и определения обобщенного класса:
// применение обобщенного класса
stack < int > s1 ;
s1.push ( 10 ) ;
// определение обобщенного класса
template < class T > class Stack
{
..
}
Можно разработать вариативный шаблон функции или класса, поддерживающий произвольное количество аргументов.
Обработка исключений
Недостаточно проектировать программы, работающие
с идеальными входными данными и идеальной средой. Следует
предвидеть все ситуации, в которых что-то может пойти
не так, и включить в программу набор мер по их преодолению.
В этой главе объясняется, как создавать такие надежные
программы при помощи механизма обработки исключений C++
280
Глава 11
Обработка исключений в C++
Работа с библиотечными классами исключений
• Библиотечные исключения при создании очереди
• Еще один пример
Полезные советы
Спецификация исключений
Необработанные исключения
Интеллектуальные указатели и динамические контейнеры
Упражнения
Важное
Обработка исключений
281
рограммирование — не зря называют искусством. Независимо от того, насколько вы уверены в своих способностях и знаниях, некоторые вещи в хо-Пде разработки программы могут пойти совершенно не так, как вы предполагали. Не обходится без опечаток, ошибок компиляции, ошибок компоновки, ошибок времени выполнения. С первыми тремя типами ошибок справиться относительно легко. Но когда ошибки возникают во время выполнения программы, она
должна уметь адекватно на них реагировать. В настоящей главе обсуждается, как
бороться с такими типами ошибок.
Ошибки, возникающие во время выполнения программы, называются исключениями (или исключительными ситуациями). Причины возникновения исключений
весьма многочисленны. Вот лишь некоторые из них, наиболее распространенные: Нехватка памяти.
Невозможность открыть файл.
Выход за границы массива.
Попытка инициализировать объект недопустимым значением.
Деление на ноль.
Переполнение стека.
Арифметическое переполнение или исчезновение порядка.
Попытка использовать неназначенную ссылку.
Невозможность подключения к серверу.
Когда возникают такие исключительные ситуации, программист должен выбрать
стратегию, согласно которой он будет их обрабатывать. Стратегии могут заклю-чаться в отображении сообщений об ошибках на экране, или отображении диалого-вого окна в случае среды с графическим пользовательским интерфейсом, или
запросе у пользователя предоставления более качественных данных, или журнали-ровании сообщения об ошибке в файле, или просто в завершении выполнения программы.
Обработка исключений в C++
C++ обеспечивает системный, объектно-ориентированный подход к обработке
ошибок во время выполнения. Механизм обработки исключений C++ зиждется на
трех ключевых словах — throw, catch и try. Разберемся в их назначении.
Допустим, что во время выполнения функции (глобальной или компонентной) возникает ошибка. Нам нужно сообщить об этом, выполнив следующие два шага: Создание объекта-исключения (exception object) и сохранение в нем информации об исключительной ситуации.
Генерирование объекта-исключения посредством ключевого слова throw.
Место, откуда вызывается объект-исключение, называется точкой выброса. Объект-исключение можно создать из готовых классов исключений, предоставляемых
282
Глава 11
стандартной библиотекой C++. Эти классы исключений представляют собой различные исключительные ситуации. В частности, один из классов исключений
представляет ситуацию арифметического переполнения, другой — результат арифметического выхода за пределы допустимого диапазона и т. п. Все эти классы
являются производными от базового класса с именем exception.
На рис. 11.1 представлена иерархия классов исключений, доступных в стандартной
библиотеке.
Рис. 11.1. Иерархия классов исключений стандартной библиотеки C++
Если мы допускаем возможность возникновения исключительной ситуации, отлич-ной от тех, что представлены в этих классах исключений, то мы можем определить
свой собственный класс исключений, создать объект этого класса, а затем вызвать
этот объект, чтобы сообщить об ошибке. Давайте для начала сфокусируемся на
библиотечных классах исключений, а затем перейдем к пользовательским исклю-чениям.
Код в приложении, ожидающий возникновения исключения во время выполнения, заключен в try-блок. Когда возникает исключение и создается объект-исключение, управление перехватывается другим разделом кода в приложении, именуемым
обработчиком исключений или catch-блоком. Таким образом, ошибки времени выполнения, сгенерированные в try-блоке, перехватываются catch-блоком. Передача
управления (часто называемая распространением) из места возникновения исключения в try-блоке в место его обработки (т. е. в catch-блок) выполняется средой
выполнения C++.
Заметьте, что код, не ожидающий возникновения исключения, не обязательно размещать в try-блоке.
В следующем фрагменте программного кода показана организация try- и catch-блоков. Это не рабочая программа, но она наглядно демонстрирует, где и как размещаются различные элементы механизма обработки исключений.
class Sample
{
public :
void fun( )
Обработка исключений
283
{
// ваш код
if ( some error occurs ) // если возникает некая ошибка
{
// из этой точки выброса выдается исключение
// оно будет перехвачено catch-блоком
throw overflow_error ( .. ) ;
}
}
} ;
int main( )
{
// try-блок
try
{
Sample s ;
s.fun( ) ;
}
catch ( overflow_error &e ) // обработчик исключений или catch-блок
{
// код, обрабатывающий перехваченное исключение
}
return 0 ;
}
Здесь Sample::fun( ) является функцией, в которой может возникнуть ошибка времени выполнения. По этой причине вызов fun( ) помещен в try-блок. Если ошибки
переполнения не возникнет, функция fun( ) отработает в штатном режиме и вернет
управление. Если же во время выполнения функции fun( ) действительно возникает
исключение, то будет сгенерирован объект-исключение класса overflow_error.
Если ниже точки выброса или ниже вызова fun( ) в теле main( ) размещены другие
инструкции, они не будут выполнены, поскольку после создания объекта-исключения try-блок перестает действовать.
Выброшенный объект-исключение перехватывается в catch-блоке, следующим непосредственно за try-блоком. При перехвате выброшенного исключения программный код может сделать две вещи:
Выполнить поэтапное завершение работы программы.
Исправить условия, по причине которых возникла исключительная ситуация, и продолжить выполнение.
Эти два варианта проиллюстрированы на рис. 11.2.
После выполнения catch-блока управление переходит к операторам, расположен-ным ниже этого блока, при условии что в catch-блоке отсутствуют инструкции
return или exit( ).
284
Глава 11
Рис. 11.2. Механизм обработки исключений С++
Работа
с библиотечными классами исключений
Как показано на рис. 11.1, все классы исключений стандартной библиотеки порож-дены классом exception. Класс этот был объявлен в заголовочном файле ′exception′, тогда как logic_error и runtime_error — в файле ′ stdexcept′.
Список классов, представленный на рис. 11.1, далеко не полный — существуют
и другие классы исключений, связанные с ошибками в распределении памяти, использовании интеллектуальных указателей, файловой системы и т. п. Давайте
составим небольшую программу, использующую некоторые из этих классов исключений:
#include <iostream>
#include <fstream>
#include <string>
#include <exception>
using namespace std ;
int main( )
{
try
Обработка исключений
285
{
ifstream infile ( "Sample.cpp" ) ;
if ( !infile )
throw runtime_error ( "Не удалось открыть файл" ) ;
string str1 ( "Yankee" ) ;
string str2 ( "Doodle" ) ;
str1.append ( str2, 7, 3 ) ;
cout << str1 << endl ;
}
catch ( logic_error &le )
{
cout << le.what( ) ;
}
catch ( runtime_error &rte )
{
cout << rte.what( ) ;
}
}
В try-блоке программа пытается совершить два действия — открыть файл для чтения и дописать часть строки str2 в конец строки str1. Если файл успешно открыт, программа продолжает добавлять строки. В противном случае создается и выбра-сывается объект-исключение runtime_error. Как только объект выброшен, try-блок
прекращает свое действие. Это исключение перехватывается вторым catch-блоком, и на экране отображается сообщение «Не удалось открыть файл», хранящееся
в объекте runtime_error. Поскольку выброшенный объект перехватывается по
ссылке, копия этого объекта не создается.
Если управление достигает процедуры добавления, программа пытается извлечь из
«Doodle» три символа, начиная с седьмого символа, и добавить их к «Yankee». Поскольку в слове «Doodle» всего шесть букв, не может быть и речи об извлечении
7, 8 и 9-го символов. Поэтому функция append( ) генерирует исключение
out_of_range. Это исключение перехватывается первым catch-блоком. Заметьте, что мы перехватили его при помощи ссылки logic_error, а не ссылки out_of_range.
Это стало возможным благодаря тому, что logic_error является родительским классом для out_of_range. Таким образом, logic_error — это ссылка с приведением
вверх. С ее помощью мы обращаемся к методу what( ) для вывода сообщения об
ошибке «недопустимая позиция в строке». Почему вознкает это сообщение? Дело
в том, что когда процедура добавления символов генерирует объект out_of_range, это сообщение сохраняется в объекте-исключении, который затем извлекается
с помощью функции what( ).
Теперь разберем, в чем разница между logic_error и runtime_error. Ряд ошибок
обнаруживается до выполнения программы. К примеру, операция деления на ноль.
При возникновении таких исключений должен быть вызван объект logic_error.
И напротив, существуют ошибки, которые обнаруживаются лишь во время выполнения программы, такие как открытие файла для чтения. В таких случаях должны
выдаваться исключения класса runtime_error.
286
Глава 11
Библиотечные исключения при создании очереди
А теперь давайте воплотим механизм обработки исключений в программе, которая
поддерживает структуру данных очереди (или FIFO-списка). Мы задействуем
обработку исключений для сообщения об ошибках в двух следующих ситуациях: При попытке сохранить в очереди больше объектов, чем она может вместить.
При попытке удалить объект из пустой очереди.
Ниже приведен листинг программы:
#include <iostream>
#include <exception>
using namespace std ;
#define MAX 4
class Queue
{
private :
int arr[ MAX ] ;
int front, rear ;
public :
Queue( )
{
front = -1 ;
rear = -1 ;
}
void addQ ( int item )
{
if ( rear == MAX - 1 )
throw exception ( "Очередь переполнена" ) ;
rear++ ;
arr[ rear ] = item ;
if ( front == -1 )
front = 0 ;
}
int delQ( )
{
int data ;
if ( front == -1 )
throw exception ( "Очередь пуста" ) ;
data = arr[ front ] ;if ( front == rear )
front = rear = -1 ;else
front++ ;
Обработка исключений
287
return data ;
}
} ;
int main( )
{
Queue q ;
try
{
q.addQ ( 11 ) ;
q.addQ ( 12 ) ;
q.addQ ( 13 ) ;
q.addQ ( 14 ) ;
q.addQ ( 15 ) ; // очередь переполнена ;
i = q.delQ( ) ;
cout << "Удаленный элемент = " << i << endl ; i = q.delQ( ) ;
cout << "Удаленный элемент = " << i << endl ; i = q.delQ( ) ;
cout << "Удаленный элемент = " << i << endl ; i = q.delQ( ) ;
cout << "Удаленный элемент = " << i << endl ; i = q.delQ( ) ; //очередь пуста ;
cout << "Удаленный элемент = " << i << endl ;
}
catch ( exception &err )
{
cout << endl << err.what( ) << endl ;
}
return 0 ;
}
В нашей программе имеется класс Queue, содержащий методы addQ( ) и delQ( ) для добавления элементов в очередь и их удаления. Члены данных front и rear служат для отслеживания начала и конца очереди.
При выполнении addQ( ) существует вероятность того, что массив, в котором хранятся элементы очереди, окажется заполнен и не сможет принимать новые элементы. В то же время при вызове delQ( ) не исключено, что мы попытаемся удалить
элемент из уже пустой очереди. И в том и в другом случае возникнет исключительная ситуация.
Поскольку при обращениях к addQ( ) и delQ( ) могут возникать исключения, их
вызовы заключены в try-блок в основной функции main( ). Мы специально сделали
вместимость очереди небольшой, чтобы было проще вызвать исключение при добавлении/удалении ее элементов.
При возникновении исключительной ситуации создается новый объект-исключение, при этом его конструктору передается соответствующее сообщение. Чтобы
288
Глава 11
иметь возможность использовать класс исключений из стандартной библиотеки, мы подключили заголовочный файл ′exception′. Создав объект-исключение, мы используем ключевое слово throw, чтобы его выбросить.
Этот выброшенный объект-исключение перехватывается в catch-блоке по ссылке, благодаря чему не создается лишняя копия объекта, что позволяет избежать дубли-рования и сэкономить память. Теперь, когда управление перешло к catch-блоку
(срок действия try-блока истекает при возникновении первого исключения), выполняются уже его инструкции. В нашей программе мы просто отображаем сообщение, хранящееся в объекте-исключении, обратившись к его методу what( ).
Если мы попытаемся удалить элемент из пустой очереди, будет выполнен анало-гичный набор действий, в чем можно убедиться, закомментировав серию вызовов
addq( ).
Подытожим вышесказанное:
Код выполняется в штатном режиме за пределами try-блока.
Управление переходит к try-блоку.
Инструкция в try-блоке вызывает ошибку в функции-члене.
Функция-член создает объект-исключение.
Функция-член выбрасывает объект-исключение.
Управление передается обработчику исключения (catch-блоку), следующему за
try-блоком.
Исключение обрабатывается в catch-последовательности.
Оцените чистоту этой процедуры — она позволяет отделить код, обнаруживающий
исключения, от кода, который их обрабатывает. Как следствие, исключение, вы-званное одним и тем же фрагментом кода, может обрабатываться разными клиен-тами по-разному, путем написания соответствующего кода в соответствующих
catch-последовательностях.
Еще один пример
Когда мы выделяем память при помощи оператора new, существует риск того, что
объем памяти, который мы пытаемся выделить, недоступен. В таком случае функция оператора new выдает исключение с именем bad_alloc. В следующей небольшой программе показано, как перехватить это исключение:
#include <iostream>
#include <new>
using namespace std ;
int main( )
{
long *p[ 100 ] ;
Обработка исключений
289
try
{
for ( int i = 0 ;
i < 100 ;i++ )
{
p[ i ] = new long[ 50000000 ] ;
cout << i << "Размещен массив типа long" << endl ;
}
}
catch ( bad_alloc &e )
{
cout << " Ошибка выделения памяти: " << e.what( ) << endl ;
}
}
Здесь мы пытаемся выделить 100 массивов, каждый из которых содержит
50 000 000 длинных целых чисел. Когда я запустил эту программу, то исключение
возникло после выделения шести таких массивов, после шестого цикла. В зависимости от объема оперативной памяти на вашем компьютере и доступного дискового пространства для виртуальной памяти у вас может получиться другой результат.
Мы подключили заголовочный файл ′new′, т. к. он содержит объявление класса исключений bad_alloc. Выброшенное исключение было перехвачено, а затем сгене-рировано сообщение с типом исключения, возвращаемым методом what( ).
Вместо этого при желании мы можем настроить собственный обработчик, которому будет передано управление при возникновении ошибки выделения памяти. Как
это сделать, показано в следующей программе:
#include <iostream>
#include <new>
using namespace std ;
void my_allochandler( )
{
cout << "Ошибка выделения памяти" << endl ;
abort( ) ;
}
int main( )
{
long *p[ 100 ] ;
set_new_handler ( my_allochandler ) ;
for ( int i = 0 ;
i < 100 ;i++ )
{
p[ i ] = new long[ 50000000 ] ;
cout << i << "Выделен массив длинных чисел" << endl ;
}
}
290
Глава 11
При помощи метода set_new_handler( ), объявленного в заголовочном файле ′new′, можно настроить my_allochandler( ) в качестве функции, которая будет вызываться
при сбое выделения памяти. Эта пользовательская функция-обработчик не должна
ни получать, ни возвращать никаких значений. В ней мы просто отображаем сообщение об ошибке и завершаем программу, вызвав функцию abort( ).
Работа
с пользовательскими классами исключений
В программе из предыдущего раздела мы просто отображаем на экране сообщение
о возникшем исключении. Временами этого недостаточно. В частности, нам могут
потребоваться дополнительные сведения о контексте, в котором произошла ошибка. Для этого необходимо включить больше информации в объект-исключение.
Сделать это можно, создав собственный класс исключений, что продемонстрировано в следующей программе:
#include <iostream>
#include <exception>
using namespace std ;
#define MAX 4
class Queue
{
private :
int arr[ MAX ] ;
int front, rear ;
public :
Queue( )
{
front = -1 ;
rear = -1 ;
}
void addQ ( int item )
{
if ( rear == MAX - 1 )
throw exception ( "Очередь переполнена" ) ;
rear++ ;
arr[ rear ] = item ;
if ( front == -1 )
front = 0 ;
}
int delQ( )
{
int data ;
Обработка исключений
291
if ( front == -1 )
throw exception ( "Очередь пуста" ) ;
data = arr[ front ] ;
if ( front == rear )
front = rear = -1 ;
else
front++ ;
return data ;
}
} ;
int main( )
{
Queue q ;
try
{
q.addQ ( 11 ) ;
q.addQ ( 12 ) ;
q.addQ ( 13 ) ;
q.addQ ( 14 ) ;
ddQ ( 15 ) ; // очередь переполнена
int i ;
i = q.delQ( ) ;
cout << "Удаленный элемент = " << i << endl ; i = q.delQ( ) ;
cout << "Удаленный элемент = " << i << endl ; i = q.delQ( ) ;
cout << "Удаленный элемент = " << i << endl ; i = q.delQ( ) ;
cout << "Удаленный элемент = " << i << endl ; i = q.delQ( ) ; //очередь пуста
cout << "Удаленный элемент = " << i << endl ; catch ( exception &err )
}
{
cout << endl << err.what( ) << endl ;
}
return 0 ;
}
Здесь мы создали собственный класс исключений QueueExcetion, произведя его от
класса exception стандартной библиотеки. Когда возникает исключение, и программа готова сгенерировать объект-исключение, мы вызываем конструктор класса
QueueException и передаем ему строку с ошибкой, front (начало) и rear (конец).
Чтобы соединить эти данные в одну строку, конструктор выводит их в объект
292
Глава 11
ostrstream. Для завершения строки используется не endl, как обычно, а ends. При
вызове метода what( ) из catch-блока он извлекает строку из объекта ostrstream и возвращает ее. Затем эта строка отправляется в cerr вместо cout. Это рекомен-дуемый метод, позволяющий при необходимости перенаправить поток cerr (стандартная ошибка) в файл.
Полезные советы
Теперь, когда мы разобрали несколько программ, использующих обработку исключений, пришло время практических рекомендаций:
Не обязательно размещать инструкцию, вызывающую исключение, непосредственно в try-блоке. Она может также располагаться в функции, вызываемой из
try-блока.
Try-блоки могут быть вложенными. Если при выбрасывании исключения внут-ренний try-блок не имеет соответствующего catch-блока, то catch-инструкции
внешнего try-блока проверяются на предмет совпадения. Этот прием известен
как раскрутка стека.
У одного try-блока может быть более одного обработчика исключений, как показано ниже.
try
{
// код, потенциально генерирующий исключения
}
catch ( exceptiontype1 id1 )
{
// обработка исключений типа type1
}
catch ( exceptiontype2 id2 )
{
// обработка исключений типа type2
}
Такие структуры позволяют дифференцировать исключения по типам.
При выдаче исключения catch-выражения проверяются в порядке их следования. Как только обнаруживается совпадение, то исключение считается обрабо-танным и дальнейший поиск прекращается.
Не перехватывайте все исключения в объекте класса exception. Безусловно, это
сработает, поскольку exception является базовым классом, из которого порож-дены практически все остальные классы исключений. Чем дискретнее catch-блок, тем точнее обработка исключений.
Не размещайте catch-инструкцию, перехватывающую объект базового класса, перед catch-инструкцией, перехватывающей объект производного класса. Иначе
catch-инструкция базового класса перехватит все объекты классов, производных
Обработка исключений
293
от этого базового класса, а catch-инструкция производного класса никогда не
будет выполняться.
Можно написать универсальный catch-блок, используя следующий синтаксис: catch ( ... )
{
}
Такую конструкцию нередко называют catch-блоком по умолчанию. Его следует
применять в качестве замыкающей catch-инструкции в catch-последова-
тельности.
Не рекомендуется прописывать универсальный catch-блок и не совершать в нем
никаких действий. Это все равно что перехватить исключение и проигнорировать его.
Не используйте обработку исключений в чисто косметических целях. Она должна служить для исправления исключительной ситуации или выполнения поэтап-ного завершения программы.
Составляя библиотеку классов для сторонних пользователей, следует предвос-хитить потенциальные источники проблем для программ, в которых она будет
задействована. На всех соответствующих участках кода следует генерировать
исключения.
При написании программы, использующей библиотеку классов, необходимо
предусмотреть try- и catch-блоки для всех исключений, выдаваемых данной
библиотекой.
Исключения создают дополнительную нагрузку с точки зрения размера программы и (при возникновении исключения) скорости ее исполнения. Поэтому
обработкой исключений не следует злоупотреблять. Сделайте ее максимально
продуманной — не слишком громоздкой, но и не слишком краткой.
Спецификация исключений
Функция может явным образом обозначить, какие исключения она может генерировать. Это делается с помощью спецификации исключений или списка типов гене-рируемых исключений (throw-list). Указав такой список, пользователь этой функции
может перехватывать их при помощи одного или нескольких catch-блоков. После
указания функция не может генерировать никаких других исключений, кроме
перечисленных в списке. Вот несколько примеров:
// может генерировать любое исключение
void closeAccount ( ) ;
// не может генерировать никаких исключений
void openAccount ( ) throw ( ) ;
void openAccount( ) noexcept ; // применимо к C++ 17
294
Глава 11
// может генерировать стандартное исключение
void fun( ) throw ( overflow_error ) ;
// может генерировать пользовательские исключения
bool withdraw ( int no ) throw ( InsufficientFundsExc, InvalidAccnoExc ) ; Заметьте, что функция может генерировать либо объекты-исключения из классов
исключений, упомянутых в списке типов исключений, либо объекты, созданные из
производных от них классов с открытым наследованием.
Необработанные исключения
Если функция генерирует исключение, отличное от упомянутых в списке исключений, то вызывается предопределенная функция с именем unexpected( ). Эта функция вызывает функцию terminate( ), которая, в свою очередь, вызывает функцию
abort( ) для аварийного завершения программы.
Если мы хотим, чтобы вместо предопределенных вызывалась наша версия функций
unexpected( ) или terminate( ), то необходимо настроить их, как показано в следующей программе:
#include <iostream>
#include <exception>
using namespace std ;
class Exception1 { } ;
class Exception2 { } ;
class Exception3 { } ;
void my_terminate( )
{
cout << "Вызов моей версии terminate( )" << endl ; abort( ) ;
}
void my_unexpected( )
{
cout << "Вызов моей версии unexpected( )" << endl ; throw ; // повторное генерирование Exception3
}
void fun( ) throw ( Exception1, Exception2 )
{
throw Exception3( ) ;
}
int main( )
{
set_unexpected ( my_unexpected ) ;
set_terminate ( my_terminate ) ;
Обработка исключений
295
try
{
cout << "В try-блоке" << endl ;
fun( ) ;
}
catch ( Exception1 e )
{
cout << "Перехвачено Exception1" << endl ;
}
catch ( Exception2 e )
{
cout << "Перехвачено Exception2" << endl ;
}
}
Когда функция fun( ) генерирует Exception3, это исключение не может быть перехвачено в основной функции main( ), поскольку в ее теле отсутствует соответствующий catch-блок. В итоге вызывается функция unexpected( ). Однако при помощи set_unexpceted( ) мы снабдили программу нашей версией этой функции. Поэтому управление переходит к my_unexpected( ). Здесь мы повторно генерируем
Exception3, используя пустой оператор throw. На этот раз вызывается функция
my_terminate( ), т. к. мы настроили ее при помощи set_terminate( ). Эта функция
просто отображает сообщение и завершает выполнение программы вызовом
abort( ).
Обратите внимание, что прототипы нашей функции-обработчика должны выглядеть следующим образом:
void my_unexpected( ) ; // ничего не принимает, ничего не возвращает
void my_terminate( ) ; // ничего не принимает, ничего не возвращает
Интеллектуальные указатели
и динамические контейнеры
При динамическом создании и разрушении объектов регулярно возникает общий
набор проблем, которые мы и обсудим ниже.
Утечка памяти. Происходит, когда мы выделяем память, но забываем ее освободить. К примеру, когда в приведенном ниже фрагменте кода управление возвращается из функции fun( ), происходит утечка памяти, поскольку p разрушается, но
объект, на который он указывает, остается в памяти, и мы не можем до него доб-раться:
void fun( )
{
Sample *p ;
p = new Sample ; // создаем объект
p -> show( ) ; // используем объект
}
296
Глава 11
Висячий указатель (или же указатель на несуществующий объект). Если два
указателя адресуют один и тот же объект и один из указателей используется для
удаления объекта, то этот объект будет разрушен, но второй указатель продолжит
на него указывать. Так, в следующем фрагменте кода p2 становится висячим указателем, когда управление возвращается из функции fun( ):
void fun( )
{
Sample *p1, *p2 ;
p1 = new Sample ; // создаем объект
p2 = p1 ; // копируем указатель
p1 -> show( ) ; // используем объект
delete p1 ; // удаляем объект при помощи указателя p1
}
Повторное удаление объекта. Если дважды удалить динамически размещенный объект, второе удаление приведет к неопределенному поведению. Может произойти что угодно, вплоть до сбоя программы.
void fun( )
{
Sample *p ;
p = new Sample ; // создаем объект
p -> show( ) ; // используем объект
delete p ; // удаляем объект
delete p ; // пытаемся повторно удалить объект – неопределенное поведение
}
Некорректное удаление массива. Массив, размещенный при помощи оператора new[ ], следует удалять при помощи оператора delete[ ]. В следующем фрагменте кода мы воспользовались delete вместо delete[ ]. В результате деструктор
вызывается лишь для первого объекта в массиве, что приводит к утечке памяти.
void fun( )
{
Sample *p ;
p = new Sample[ 10 ] ; // создаем 10 объектов, вызываем конструктор 10 раз
p[ 0 ] -> show( ) ; // используем объект с индексом 0
p[ 1 ] -> show( ) ; // используем объект с индексом 1
delete p ; // удаляем только первый объект, вызываем деструктор лишь один раз
}
Во избежание этих проблем, вызванных обычными (не интеллектуальными) указателями, было предложено вообще отказаться от использования операторов new, new[ ], delete и delete[ ]. Вместо них рекомендуется использовать одно из следующих средств:
Интеллектуальные указатели, такие как unique_ptr< >, shared_ptr< > и
weak_ptr< >.
Динамические контейнеры, такие как vector<>, set< > и пр.
Все они доступны в виде обобщенных классов стандартной библиотеки C++.
Обработка исключений
297
Интеллектуальный указатель, получаемый путем перегрузки операторов * и ->, ведет себя как простой указатель, но при этом выполняет некоторую обработку.
Объект, созданный с его помощью, всегда будет разрушен надлежащим образом, не вызывая утечки памяти.
При использовании динамических контейнеров не требуется явным образом задействовать интеллектуальные указатели unique_ptr, shared_ptr, weak_ptr. Вполне
естественно, что использование динамических контейнеров является предпочти-тельным способом выделения и удаления ресурсов в современном программировании на C++. Поэтому мы не станем углубляться в тему интеллектуальных указателей, а перейдем в следующей главе к подробному рассмотрению динамических
контейнеров.
1. Укажите, верны ли следующие утверждения:
Механизм обработки исключений предназначен для работы с ошибками времени компиляции.
Необходимо объявить класс исключения в теле класса, в котором будет генери-роваться исключение.
Необходимо перехватывать все сгенерированные исключения.
На один try-блок может приходиться несколько catch-блоков.
Обработчик исключений и catch-блок — это одно и то же.
При выбрасывании исключения вызывается конструктор класса исключения.
Try-блоки не могут быть вложенными.
Механизм обработки исключений гарантирует корректное разрушение объекта.
2. Решите следующие задачи:
Реализуйте механизм обработки исключений для класса Stack, сообщающий об
ошибках, связанных с переполненным и пустым стеком.
Разработайте класс Customer, содержащий имя (name), номер счета (accountno) и текущий баланс (balance) в качестве членов данных. Создайте 5 объектов этого класса. Реализуйте функцию withdraw( ), осуществляющую снятие суммы
с определенного счета. Эта функция должна генерировать исключение с именем
BankException, если после снятия суммы баланс на счете становится ниже
1000 рублей. В catch-блоке укажите сведения о клиенте, инициировавшем не-удачную транзакцию.
298
Глава 11
При создании и выполнении программы на C++ ошибки могут возникать на трех
разных этапах:
• В ходе компиляции: сообщается компилятором, действие — исправление
программного кода.
• В ходе компоновки: сообщается компилятором, действие — исправление
#include-инструкций.
• В ходе выполнения (программы): сообщается средой выполнения С++ (C++
Runtime), действие — перехват и обработка на лету.
Примеры ошибок времени выполнения:
• Связанные с памятью — переполнение стека / динамической памяти, выход
за границы массива.
• Связанные с арифметическими вычислениями — деление на ноль, переполнение или исчезновение порядка.
• Прочие — попытка использовать неприсвоенную ссылку, открыть ненайден-ный файл.
При выполнении метода, вызванного из клиентского кода, может возникнуть
исключительная ситуация. В таком случае следует:
• Поместить информацию об исключении в объект.
• Сгенерировать объект-исключение.
Два варианта действия при генерировании объекта-исключения:
• Перехватить объект в клиентском коде.
• Передать его дальше.
Если объект-исключение передается дальше, то его перехватывает обработчик
исключений по умолчанию и выполняет аварийное завершение программы.
Перехватив объект-исключение в клиентском коде, мы можем либо осуществить
поэтапное завершение программы, либо исправить исключительную ситуацию
и продолжить ее выполнение.
Два способа создания объектов-исключений:
• Из классов исключений стандартной библиотеки C++.
• Из пользовательских классов исключений.
Преимущества обработки исключений объектно-ориентированным способом:
• В объекты-исключения можно поместить больше сведений.
• Передача объектов-исключений вызывающей стороне управляется средой
выполнения C++.
Обработка исключений
299
Каким образом C++ упрощает обработку объектно-ориентированных исключений:
• Предоставляя ключевые слова — try, catch, finally, throw, throws.
• Предоставляя библиотечные классы исключений.
• Позволяя методам анонсировать возможность исключения.
Как пользоваться try- и catch-блоками:
• try-блок — поместите в него код, в котором, по вашим предположениям, может возникнуть исключение.
• catch-блок — перехватывайте в нем выброшенное исключение. Этот блок
должен следовать непосредственно за try-блоком.
При возникновении исключения управление переходит к catch-блоку. После
выполнения catch-инструкций управление переходит к следующей строке после
catch-блока(ов), при отсутствии в catch-последовательности команд return или
throw.
try-блок:
• Может быть вложен в другой try-блок.
• Если у вложенного try-блока нет своего обработчика исключений, то проверяются на совпадение catch-инструкции внешнего try-блока.
catch-блок:
• Для одного try-блока допускается наличие нескольких catch-блоков.
• На каждое выданное исключение срабатывает лишь один catch-блок.
• Важен порядок catch-блоков — от производных к базовым.
Советы по обработке исключений:
• Не перехватывайте исключение лишь для того, чтобы проигнорировать его.
• Не перехватывайте все исключения при помощи класса ′exception′, старайтесь
дифференцировать исключения по типам.
• Сделайте обработку исключений в вашей программе максимально продуманной — не слишком громоздкой и не слишком краткой.
Используйте интеллектуальные указатели или динамические контейнеры вместо
операторов new, new[ ], delete и delete[ ].
Стандартная библиотека шаблонов
Помимо средств объектно-ориентированного
программирования, именно мощная стандартная библиотека
шаблонов (Standard Template Library, STL) делает C++
таким популярным среди программистов,
стремящихся создавать надежные и производительные
программы. Материал этой главы составляют
ключевые компоненты библиотеки STL
302
Глава 12
Стандартная библиотека шаблонов
Компоненты библиотеки STL
• Контейнеры
• Итераторы
• Алгоритмы
Вектор (vector)
• Другие операции
Вектор объектов класса Point
Список (list)
Множество (set) и мультимножество (multi-set)
Отображение (map) и мультиотображение (multi-map)
Стек (stack)
Очередь (queue)
• Объект-функция
Упражнения
Важное
Стандартная библиотека шаблонов
303
иблиотека STL предоставляет шаблонные классы и функции общего назначения, реализующие множество популярных и широко распространенных
Балгоритмов и структур данных. Первоначально STL была отдельной библиотекой, однако теперь она объединена со стандартной библиотекой C++. И хотя
в отрасли по-прежнему используется аббревиатура STL, в стандартной документа-ции к C++ она упоминается как стандартная библиотека. Поскольку теперь это
часть стандартной библиотеки, для ее использования не требуется скачивать ее отдельно. В этой главе обсуждаются различные компоненты STL и демонстрируется
их применение в программах на C++.
Стандартная библиотека шаблонов
Архитектура STL была разработана Александром Степановым и Менг Ли в лабора-ториях Hewlett Packard в Пало-Альто (Калифорния). При создании программ на
C++ нередко нужна та или иная структура данных для их обработки. Вместо того, чтобы создавать и поддерживать эти структуры данных самостоятельно, мы можем
воспользоваться готовыми классами библиотеки STL. Данный подход имеет следующие преимущества:
Реализация каждой структуры данных, такой как связный список, очередь
с приоритетом, ассоциативный массив и т. п., требует значительных трудоза-трат.
Многие структуры данных требуют нетривиального использования указателей.
Небольшое упущение или недосмотр может привести к нарушениям доступа
к памяти и ее утечкам.
Используя стандартную библиотеку шаблонов, можно сконцентрироваться на
проблеме, которую требуется решить, и предоставить STL обработку данных.
Допустим, что в крупном проекте программистам, работающим над разными
задачами, необходима единая структура данных. Если они решат создать классы
для индивидуальной обработки этих структур данных, код станет трудно изменять, поддерживать и отлаживать. Более того, такое решение стимулирует скорее изобретение давно изобретенного, а не многократное использование.
Таким образом, использование библиотеки STL способствует многократному использованию кода и может значительно сэкономить время разработки, трудозатра-ты и бюджет, а также сократить сроки тестирования и отладки.
Стандартная библиотека шаблонов была задумана и разработана для повышения
производительности и гибкости. Кроме того, все классы в STL основаны на шаблонах. Следовательно, их можно повторно использовать для работы как со стандарт-ными, так и с пользовательскими типами данных. Такая расширяемость библиотеки
STL является еще одной причиной ее популярности среди программистов.
304
Глава 12
Компоненты STL
Ядро стандартной библиотеки шаблонов включает три основные составляющие —
контейнеры, итераторы и алгоритмы.
Так, контейнеры STL представляют собой структурные объекты, способные
хранить другие объекты практически любого типа данных.
Итераторы STL применяются для работы с элементами STL-контейнера.
И наконец, алгоритмы библиотеки STL используются для обработки структур
данных.
К примеру, контейнер STL, именуемый vector, можно использовать для хранения
ряда целых чисел в виде динамического массива. Итератор можно использовать для
обхода этого массива в прямом или обратном направлении; а алгоритм STL, называемый sort( ), можно задействовать для сортировки элементов объекта vector.
Обратите внимание на тот факт, что управление контейнерами при помощи итераторов не только обеспечивает удобство, но и в сочетании с алгоритмами делает
программу выразительной, гибкой и производительной. Давайте теперь подробно
рассмотрим различные компоненты библиотеки STL.
Контейнеры
Классы контейнеров подразделяются на три категории в зависимости от способа
расположения элементов:
Последовательные контейнеры: представляют собой линейные структуры данных, такие как vector (вектор, динамический массив), deque (двусторонняя очередь, дек) и list (список).
Ассоциативные контейнеры: позволяют эффективно находить нужные значения
на основе заданных ключей. Такие контейнеры могут хранить наборы значений
или пары ключ-значение. В частности, к ним относятся set (множество), multiset (мультимножество), map (отображение) и multimap (мультиотображение).
Производные контейнеры: Это ограниченные версии последовательных контейнеров. Их часто называют контейнеры-адаптеры. К ним относятся stack (стек), queue (очередь) и priority_queue (очередь с приоритетом).
В табл. 12.1 приведены отличительные особенности каждого из классов контейнеров.
Таблица 12.1. Различные классы контейнеров
Контейнер Описание
vector
Вставка/удаление в конце массива. Прямой доступ к любому элементу
deque
Вставка/удаление в начале/конце. Прямой доступ к любому элементу
list
Двусвязный список. Вставка/удаление в любом месте
Стандартная библиотека шаблонов
305
Таблица 12.1 (окончание)
Контейнер Описание
set
Уникальные элементы. Используется сбалансированное дерево двоичного
поиска (BST). Быстрый поиск
multiset
Допускаются дубликаты. Быстрый поиск
map
Уникальные пары «ключ-значение». Используется сбалансированный BST.
Быстрый поиск по ключам
multumap
Допускаются дубликаты. Пары «ключ-значение». Быстрый поиск по ключам
stack LIFO-список
queue FIFO-список
priority_queue
Элемент с наивысшим приоритетом становится первым элементом
Кроме контейнеров, указанных в табл. 12.1, библиотека STL также предоставляет
следующие специализированные контейнеры:
Массив в виде связанных списков.
bitset (битовое множество) для хранения наборов значений флагов.
valarray (числовой массив) для выполнения математических векторных операций.
Итераторы
Как следует из самого названия, итераторы позволяют циклически опрашивать все
элементы контейнера и выполнять над ним операции ввода-вывода. Итераторы ин-капсулируют механизм, применяемый для доступа к элементам контейнера. В различных итераторах могут быть реализованы одна или несколько из этих возможностей. Ниже приведен список итераторов и их поведение.
Входной итератор:
• Считывает элемент из контейнера.
• Опрашивает элементы от начала до конца, по одному элементу за раз.
• Поддерживает только однопроходные алгоритмы.
Выходной итератор:
• Записывает элемент в контейнер.
• Опрашивает элементы только от начала до конца, по элементу за раз.
• Поддерживает только однопроходные алгоритмы.
Однонаправленный итератор:
• Считывает/записывает элемент из/в контейнер.
• Опрашивает элементы только от начала до конца, по элементу за раз.
• Поддерживает только однопроходные алгоритмы.
306
Глава 12
Двунаправленный итератор:
• Считывает/записывает элемент из/в контейнер.
• Опрашивает элементы в обоих направлениях, по элементу за раз.
• Поддерживает многопроходные алгоритмы.
Итератор прямого доступа:
• Считывает/записывает элемент из/в контейнер.
• Опрашивает элементы в обоих направлениях, с пропуском многих элементов
одновременно.
• Поддерживает многопроходные алгоритмы.
Обратите внимание, что среди всех перечисленных видов итератор прямого доступа выглядит самым функциональным. В разных контейнерах реализованы разные
виды итераторов. На основе итератора, поддерживаемого контейнером, определяются его возможности чтения/записи/перемещения по элементам. Ниже приведен
список, в котором указаны итераторы, поддерживаемые различными контейнерами: Вектор, дек — прямой доступ.
Список, множество, мультимножество, отображение, мультиотображение —
двунаправленные.
Стек, очередь, очередь с приоритетом — без поддержки итераторов.
Помимо разновидностей, указанных выше, итераторы могут быть константными
(например, const_iterator) или неконстантными. Константные итераторы могут
опрашивать элементы контейнера, но не могут их изменять. Кроме того, некон-стантные итераторы нельзя использовать с константными объектами-контейнерами.
Алгоритмы
Алгоритмы библиотеки STL — это шаблонные функции, которые выполняют общие операции, такие как вставка, удаление, поиск, сортировка и сравнение элементов или целых контейнеров. Некоторые алгоритмы могут изменять содержимое
контейнера (например, delete( )), а некоторые — нет (к примеру, find( )). Стандартная библиотека шаблонов предоставляет множество алгоритмов. Их применение
может сэкономить массу времени и усилий.
Алгоритмы задействуют итераторы для доступа к элементам контейнера. Алгоритмы нередко возвращают итераторы, указывающие на результаты алгоритмов. Каждый алгоритм имеет минимальные требования к типам итераторов, которые можно
с ним использовать.
Возможность применения контейнера с конкретным алгоритмом зависит от типа
итератора, поддерживаемого контейнером. Контейнеры, поддерживающие итераторы прямого доступа, можно использовать со всеми алгоритмами библиотеки
STL.
Стандартная библиотека шаблонов
307
Поскольку алгоритмы предоставляются как автономные функции, а не как часть
классов контейнеров, можно также создавать собственные алгоритмы и научить их
работать с различными типами контейнеров.
Разобравшись с различными составляющими библиотеки STL, приступим к написанию программ, использующих эти компоненты.
Вектор (vector)
Контейнер vector (вектор) напоминает массив C++ в том смысле, что он содержит
объекты одного и того же типа, и к каждому из этих объектов можно получить доступ по отдельности. Вектор определен как обобщенный класс, поэтому его можно
использовать для хранения объектов любого типа. К примеру:
vector <int> vec_int ; // может хранить целые числа
vector <Sample> vec_obj ; // может хранить объекты Sample
Vector-контейнеры «умнее» массивов C++, т. к. они могут динамически увеличи-ваться по мере добавления к ним элементов. Вектор всегда занимает непрерывные
области памяти; для него предоставляется итератор прямого доступа. Рассмотрим
программу, которая выполняет различные операции над vector-контейнером.
#include <vector>
#include <iostream>
using namespace std ;
int main( )
{
vector <int> v1 ;
vector <int>::iterator itr1 ;
for ( int i = 0 ; i <= 5 ; ++i )
v1.push_back ( 5 * i ) ;
cout << "Vector v1:" << endl ;
for ( itr1 = v1.begin( ) ; itr1 != v1.end( ) ; ++itr1 )
cout << *itr1 << endl ;
vector <int> v2 { 10, 20, 30, 40, 50 } ;
cout << "Vector v2:" << endl ;
for ( auto itr2 = v2.begin( ) ;
itr2 != v2.end( ) ; ++itr2 )
cout << *itr2 << endl ;
vector <int> v3 { 10, 20, 30, 40, 50 } ;
cout << "Vector v3:" << endl ;
for ( auto num : v3 )
cout << num << endl ;
308
Глава 12
return 0 ;
}
Наша программа создает три вектора целочисленного типа. Так, мы сохраняем пять
целых чисел в v1, вызвав функцию push_back( ), а v2 и v3 инициализируются на
месте. Затем мы производим циклический опрос этих векторов, используя три цикла for, каждый из которых становится проще, чем предыдущий.
В первом for-цикле мы вызываем метод begin( ) для получения объекта итератора.
Цикл продолжается до тех пор, пока itr1 не достигает конца vector-контейнера, который определяется путем сравнения itr1 с результатом v1.end( ), возвращающего
итератор, указывающий позицию за последним элементом вектора. Если itr1 равен
этому значению, значит, достигнут конец вектора. В теле цикла мы воспользовались *itr1 для получения значения текущего элемента вектора. Команда itr1++
перемещает итератор на следующий элемент.
Во втором for-цикле мы используем ключевое слово auto. Поэтому нам не нужно
определять тип itr2. Он выводится компилятором из контекста, в котором он задействован.
Третий for-цикл — это цикл нового типа. При каждой итерации цикла num принимает следующее значение в vector-контейнере.
Другие операции
Кроме сохранения элементов и их опроса, над контейнером vector можно выполнять множество других операций. Они продемонстрированы в следующем фрагменте кода и снабжены пояснительными комментариями.
vector<int> v ;
// store elements v.push_back ( 18 ) ;v.push_back ( 29 ) ;
v.push_back ( -4 ) ;v.push_back ( 12 ) ;v.push_back ( 44 ) ;
// доступ к элементам
cout << "Начальный элемент: " << v.front( ) << endl ; cout << "Элемент во второй позиции: " << v.at ( 2 ) << endl ; cout << "Элемент в конце: " << v.back( ) << endl ;
// замена элементов
vector <int>::iterator itr ;itr = v.begin( ) ;
*itr = 35 ;
vec [ 2 ] = 20 ;itr += 4 ;
*itr = 99 ;
// вставка элемента
itr = v.begin( ) ;v.insert ( itr, 25 ) ;
// удаление элемента
itr = v.begin( ) ;
itr += 2 ;v.erase ( vitr ) ;
Стандартная библиотека шаблонов
309
// удаление элементов из вектора
v.pop_back( ) ;
v.pop_back( ) ;
// размер и емкость
cout << v.size( ) << endl ; // текущее кол-во элементов в векторе
cout << v.max_size( ) << endl ; // макс. кол-во элементов, которое может содержать
вектор
cout << v.capacity( ) << endl ; // кол-во элементов до необходимости увеличения
емкости вектора
v.resize (100 ) ; // увеличение размера до 100
// очистка элементов вектора
v.clear( ) ;
// проверка, является ли вектор пустым
bool b = v.empty( ) ;
Вектор объектов класса Point
При помощи vector-контейнера мы также можем управлять массивом пользовательских объектов Point (двухмерные координаты точки), что продемонстрировано
в следующем листинге:
#include <vector>
#include <iostream>
using namespace std ;
class Point
{
private :
int x, y ;
public :
Point ( int xx = 0 , int yy = 0 )
{
x = xx ;
y = yy ;
}
friend ostream & operator << ( ostream &o, Point &p ) ;
} ;
ostream & operator << ( ostream &o, Point &p )
{
o << "(" << p.x << ", " << p.y << ")" << endl ; return o ;
}
int main( )
{
vector <Point> vp1 ;
310
Глава 12
for ( int i = 0 ;i < 5 ;i ++ )
vp1.push_back ( Point ( i + 1, i + 1 ) ) ;
cout << "Вектор vp1:" << endl ;for ( auto itr : vp1 ) cout << itr ;
cout << "Начало: " ;cout << vp1.front( ) ;
cout << "Конец: " ;cout << vp1.back( ) ;
vector <Point>::reverse_iterator ritr ;
cout << "Обратный вектор vp1:" << endl ;
for ( ritr = vp1.rbegin( ) ;ritr != vp1.rend( ) ;ritr++ )
cout << *ritr ;
cout << "Размер vp1: " << vp1.size( ) << endl ; vector <Point> vp2 ;
vp2.assign ( vp1.begin( ) , vp1.begin( ) + 3 ) ;
cout << "Вектор vp2:" << endl ;for ( auto itr : vp2 ) cout << itr ;
}
Программа генерирует следующие результаты:
Вектор vp1:
(1, 1)
(2, 2)
(3, 3)
(4, 4)
(5, 5)
Начало: (1, 1)
Конец: (5, 5)
Обратный вектор vp1:
(5, 5)
(4, 4)
(3, 3)
(2, 2)
(1, 1)
Размер vp1: 5
Вектор vp2:
(1, 1)
(2, 2)
В этой программе мы сначала объявили класс Point, содержащий конструктор и
дружественную функцию, отображающую объект Point. Затем в for-цикле в теле
основной функции мы создали пять объектов Point и добавили их в вектор vp, вызвав функцию push_back( ) класса vector. Затем при помощи итератора мы опросили вектор, отображая значения всех объектов класса Point, в нем присутствующих.
Стандартная библиотека шаблонов
311
Мы также получили доступ к элементам в начале и в конце вектора, используя
методы front( ) и back( ). Обратный обход был выполнен при помощи reverse_
iterator. Размер контейнера возвращается функцией size( ). В заключение мы создали еще один вектор vp2 и скопировали в него первые три элемента vp1, а затем
опросили вектор vp2 от начала до конца.
Список (list)
Контейнер list (список) воплощает классическую структуру данных с двунаправ-ленным последовательным доступом. Так, в отличие от массива C++ или вектора
библиотеки STL, элементы списка не поддерживают прямой доступ. List-контейнер
реализован как двусвязный список для поддержки двунаправленных итераторов.
Каждый элемент списка содержит указатель на предыдущий и последующий элементы. Списки следует применять в тех случаях, когда необходимо часто вставлять
или удалять элементы из середины списка. Рассмотрим программу, выполняющую
различные действия с контейнером list.
#include <iostream>
#include <list>
using namespace std ;
int main( )
{
list <int> ls ;
// добавление элементов в список
ls.push_back ( 12 ) ;
ls.push_front ( 34 ) ;
ls.push_back ( 19 ) ;
ls.push_front ( 44 ) ;
ls.push_back ( 31 ) ;
ls.push_front ( 2 ) ;
ls.push_back ( 29 ) ;
ls.push_front ( -8 ) ;
// отображение элементов списка
cout << "Элементы списка: " << endl;
for ( auto litr : ls )
cout << litr << " " ;
cout << endl ;
cout << "Начальный элемент: " << ls.front( ) << endl ; cout << "Конечный элемент: " << ls.back( ) << endl ;
// удаление двух элементов из начала и конца
ls.pop_back( ) ;
312
Глава 12
ls.pop_back( ) ;
ls.pop_front( ) ;
ls.pop_front( ) ;
// отображение элементов списка
cout << "Список после удаления: "
<< endl ;for ( auto litr : ls )
cout << litr << " " ;
cout << endl ;
// вставка элементов
list<int>::iterator litr ;litr = ls.end( ) ;
litr-- ;
ls.insert ( litr, -20 ) ;
litr-- ;
litr-- ;
ls.insert ( litr, 67 ) ;
litr++ ;
ls.insert ( litr, 33 ) ;
cout << "Список после вставки: " << endl ;
for ( auto litr : ls )
cout << litr << " " ;
cout << endl ;
// очистка элемента
litr = ls.begin( ) ;
ls.erase ( litr ) ;
cout << "Список после очистки первого элемента: " << endl ; for ( auto litr : ls )
cout << litr << " " ;
cout << endl ;
// перестановка элементов в обратном порядке
ls.reverse( ) ;
cout << "Реверсированный список: " << endl ;
for ( auto litr : ls )
cout << litr << " " ;
cout << endl ;
// сортировка элементов списка
ls.sort( ) ;
cout << "Список, отсортированный по возрастанию: " << endl ; for ( auto litr : ls )
cout << litr << " " ;
cout << endl ;
Стандартная библиотека шаблонов
313
// Сортировка списка по убыванию
ls.sort ( greater <int> ( ) ) ;
cout << "Список, отсортированный по убыванию: " << endl ; for ( auto litr : ls )
cout << litr << " " ;
cout << endl ;
ls.clear( ) ;
}
В этой программе мы создаем связный список целых чисел. Для вставки элементов
в конец/начало списка мы вызываем методы push_back( ) и push_front( ). После
вставок методы front( ) и back( ) отображают элемент на первой и последней позиции списка соответственно. Вызываемые затем методы pop_back( ) и pop_front( ) удаляют элемент в конце и начале списка.
У списка есть двунаправленный итератор. Прямой доступ к элементам списка не
поддерживается. По этой причине список не поддерживает операцию индексирова-ния [ ]. Так, чтобы вставить элемент на 6-ю позицию (в список из семи элементов), мы использовали команду litr = ls.end( ), которая возвращает итератор, ссылаю-щийся на элемент в 7-й позиции. Затем мы декрементировали значение итератора
на единицу, чтобы litr ссылался на элемент на 6-й позиции. Далее метод insert( ) добавляет в эту позицию элемент -20. Аналогичные шаги выполняются для вставки
элемента в 3-ю и 5-ю позиции.
Метод erase( ) очищает элемент, на который ссылается итератор litr, тогда как метод clear( ) удаляет все элементы из списка. Все элементы списка можно перестро-ить в обратном порядке при помощи метода reverse( ).
Функция алгоритма сортировки не поддерживается списком. В то же время для
контейнера list предусмотрена функция-член sort( ), сортирующая список по возрастанию/убыванию.
Множество (set)
и мультимножество (multi-set)
Это ассоциативные контейнеры, элементы которых содержат уникальные значения, при этом мультимножество допускает дублирование элементов. Размер этих контейнеров может меняться во время выполнения. Они всегда упорядочены в порядке
возрастания или убывания. Обе разновидности поддерживают двунаправленные
итераторы. Давайте посмотрим, как множество и мультимножество можно задействовать в коде:
#include <iostream>
#include <algorithm>
#include <set>
using namespace std ;
314
Глава 12
int main( )
{
set<int> s1 { 1, 12, -13, 44, 15, 6 } ;
set<int, less<int> > s2 { 11, 32, -3, 14, 5, 12 } ;
set<int, greater<int> > s3 { -3, 2, 4, 19, 11, 30 } ;
set<int, less<int> > s4, s5, s6, s7 ;
cout <<"s1: " ;
for ( auto sitr : s1 )
cout << sitr << " " ;
cout << endl ;
cout <<"s2: " ;
for ( auto sitr : s2 )
cout << sitr << " " ;
cout << endl ;
cout <<"s3: " ;
for ( auto sitr : s3 )
cout << sitr << " " ;
cout << endl ;
set<int>::iterator sitr ;
// поиск элемента
int num ;
cout << "Введите число для поиска: " ;
cin >> num ;
sitr = find ( s1.begin( ), s1.end( ), num ) ;
if ( sitr != s1.end( ) )
cout << num << " найдено в s1" << endl ; else
cout << num << " не найдено в s1" << endl ;
// проверка на идентичность данных в set1 и set2
bool b = includes ( s1.begin( ), s1.end( ), s2.begin( ), s2.end( ) ) ; if ( b )
cout << "s1 и s2 идентичны" << endl ;
else
cout << "s1 и s2 не идентичны" << endl ;
// объединение двух множеств
set_union ( s1.begin( ), s1.end( ), s2.begin( ), s2.end( ),
inserter ( s4, s4.begin( ) ) ) ;
cout << "Объединение s1 и s2: " << endl ;
for ( auto sitr : s4 )
cout << sitr << " " ;
cout << endl ;
Стандартная библиотека шаблонов
315
// получение общих элементов двух множеств
set_intersection ( s1.begin( ), s1.end( ), s2.begin( ), s2.end( ),
inserter ( s5, s5.begin( ) ) ) ;
cout << "Общее у s1 и s2: " << endl ;for ( auto sitr : s5 ) cout << sitr << " " ;
cout << endl ;
// получение элементов s1, которых нет в s2
set_difference ( s1.begin( ), s1.end( ), s2.begin( ), s2.end( ),
inserter ( s6, s6.begin( ) ) ) ;
cout << "Разное у s1 и s2: " << endl ;
for ( auto sitr : s6 )
cout << sitr << " " ;
cout << endl ;
// получение симметрической разности для s1 и s2
set_symmetric_difference ( s1.begin( ), s1.end( ), s2.begin( ), s2.end( ), inserter ( s7, s7.begin( ) ) ) ;
cout << "Симметрическая разность между s1 и s2: " << endl ; for ( auto sitr : s7 )
cout << sitr << " " ;
cout << endl ;
multiset <int, greater<int> > ms1 { 2, 3, 11, -6, 11, 2 } ; multiset <int, greater<int> > ms2 { 8, 10, 11, 8, 3, 12 } ; multiset <int, greater<int> > ms3 ;
multiset <int>::iterator msitr ;
// отображение элементов мультимножеств
cout << "ms1: " ;
for ( auto msitr : ms1 ) cout << msitr << " " ; cout << endl ;
cout << "ms2: " ;
for ( auto msitr : ms2 )
cout << msitr << " " ;
cout << endl ;
// объединение двух мультимножеств
set_union ( ms1.begin( ), ms1.end( ),
ms2.begin( ), ms2.end( ), inserter ( ms3, ms3.begin( ) ) ) ;
cout << "Объединение ms1 и ms2: " << endl ;
for ( auto msitr : ms3 )
cout << msitr << " " ;
cout << endl ;
}
316
Глава 12
Программа генерирует следующие результаты:
s1: -13 1 6 12 15 44
s2: -3 5 11 12 14 32
s3: 30 19 11 4 2 -3
Введите число для поиска: 67
67 не найдено в s1
s1 и s2 не идентичны
Объединение s1 и s2:
-13 -3 1 5 6 11 12 14 15 32 44
Общее у s1 и s2:
12
Разное у s1 и s2:
-13 1 6 15 44
Симметрическая разность между s1 и s2:
-13 -3 1 5 6 11 14 15 32 44
ms1: 11 11 3 2 2 -6
ms2: 12 11 10 8 8 3
Объединение ms1 и ms2:
12 11 11 11 10 8 8 3 3 2 2 -6
Для начала мы создали множества s1, s2 и s3 для хранения целых чисел. Методы
less<int> или greater<int>, участвующие в определении s2 и s3, являются предопределенными функциями алгоритма, которые гарантируют, что элементы во множестве представлены в порядке возрастания/убывания. По умолчанию задан порядок по возрастанию, как и в случае с s1.
Множества опрашиваются при помощи неявного итератора sitr. Его тип выводится
из контекста. Метод find( ) применяется для поиска элемента во множестве, а метод
include( ) — для проверки тождественности двух множеств.
Множества s4, s5, s6 и s7 остаются пустыми во время объявления. Позднее в них
сохраняются результаты различных действий над множествами s1 и s2. Так, осуществляются следующие операции:
set_union( ) : Объединяет элементы в s1 и s2
set_intersection( ) : Выдает различающиеся элементы в s1 и s2
set_difference( ) : Выдает элементы s1, отсутствующие в s2
set_symmetric_difference( ): Выдает элементы s1, отсутствующие в s2, и наоборот
Шаблонная функция inserter( ) копирует результат операций, выполненных выше-указанными функциями, во множество, переданное ей как аргумент.
В этой программе мы также задействовали мультимножество целых чисел, которые
могут содержать дубликаты или несколько значений одного ключа. Методы find( ), empty( ), set_union( ) и другие работают с мультимножеством точно таким же образом, как они работают со множеством.
Стандартная библиотека шаблонов
317
Отображение (map)
и мультиотображение (multi-map)
Отображение (map) хранит пары значений, где каждая пара состоит из объекта-ключа и объекта-значения.
Объектом-ключом могут быть данные встроенных типов, таких как string, int, float, или любой другой объект пользовательского класса. Этот объект содержит
ключ, по которому осуществляется поиск. Объект-значение хранит дополнительные данные. Объект-значение обычно хранит числа или строки, однако может
хранить и объекты других классов. К примеру, если ключ отображения содержит
слово, то значением может быть длина слова, количество его повторов или даже
его значение.
Данные отображения всегда организованы в порядке сортировки по ключам, который определяется соответствующим методом при создании отображения. Элементами отображения всегда являются уникальные пары «ключ-значение». Мультиотображение (multimap), с другой стороны, позволяет хранить неуникальные
пары «ключ-значение». Теперь посмотрим, как воплотить отображение и мультиотображение в программном коде.
#include <iostream>
#include <map>
#include <string>
using namespace std ;
int main( )
{
map <string, int> m1 {
{ "Rahul", 645 },
{ "Aditi", 555 },
{ "Salil", 455 },
{ "Vibha", 470 },
{ "Beena", 378 }
} ;
// отображение данных
cout << "Всего элементов в m1: " << m1.size( ) << endl ; cout << "Элементов в отображении m1: " << endl ; for ( auto mitr : m1 )
cout << "Имя: " << mitr.first
<< " Баллы: " << mitr.second << endl ;
// добавление новой пары «ключ-значение»
m1 [ "Dinesh" ] = 333 ;
// изменение значения существующего ключа
m1 [ "Beena" ] = 555 ;
318
Глава 12
// еще один способ добавить пару «ключ-значение»
pair<string, int> p ;
p.first = "Shailesh" ;
p.second = 665 ;
m1.insert ( p ) ;
cout << "Новое отображение" << endl ;
for ( auto mitr : m1 )
cout << "Имя: " << mitr.first
<< " Баллы: " << mitr.second << endl ;
// поиск отображения для заданного студента
string str ;
cout << "Введите имя студента для поиска: " ;
cin >> str ;
map <string, int>::iterator mitr ;
mitr = m1.find ( str ) ;
if ( mitr != m1.end( ) )
cout << mitr->first << " набрал "
<< mitr->second << " баллов" << endl ; else
cout << "Студент с таким именем не найден!" << endl ; multimap <string, int> m2 ;
copy ( m1.begin( ), m1.end( ), inserter ( m2, m2.begin( ) ) ) ;
p.first = "Dinesh" ;
p.second = 665 ;m2.insert ( p ) ;
cout << "Мультиотображение:" << endl ;
for ( auto mitr : m2 )
cout << "Имя: " << mitr.first
<< " Баллы: " << mitr.second << endl ;
}
В этой программе мы создали отображение для хранения имен студентов (ключ) и
баллов (значение). Элементы отображения упорядочены в алфавитном порядке по
именам.
Мы отобразили элементы, хранящиеся в m1, при помощи цикла с использованием
неявного итератора. Инструкция для вывода данных имеет несколько отличный
характер.
Нам необходимо использовать mitr.first для вывода значения ключа и mitr.second для вывода связанного с ним значения.
Существуют два способа вставить в отображение новые пары «ключ-значение» —
при помощи оператора [ ] или путем вызова метода insert( ) с передачей ему пары
«ключ-значение» в качестве аргумента. Оператором [ ] также можно воспользоваться для изменения существующего значения.
Стандартная библиотека шаблонов
319
Метод find( ) используется для поиска указанного ключа. Если ключ найден, то
отображаются оценки, полученные студентом, в противном случае выводится соответствующее сообщение.
В этой же программе мы создали мультиотображение m2. Затем, воспользовавшись
методом copy( ), мы скопировали все элементы m1 в m2. Мультиотображение не
поддерживает оператор [ ]. Поэтому для добавления элементов в мультиотображение мы создали объект p шаблонного класса pair. Затем мы обратились к методу
insert( ) для вставки пары p в мультиотображение m2. Заметьте, что добавленная
пара дублирует существующую запись, что поддерживается мультиотображением.
И наконец, при помощи for-цикла мы вывели элементы, хранящиеся в m2.
Стек (stack)
Стек (stack) представляет собой последовательный контейнер, обеспечивающий
вставку и удаление элементов лишь с одного конца. Так, элементы стека добавля-ются и извлекаются по принципу LIFO (Last In First Out) «последним пришел —
первым ушел». Следующая программа демонстрирует функции управления стеком
целых чисел:
#include <iostream>
#include <stack>
using namespace std ;
void main( )
{
stack<int> stk ;
// вставка элементов в стек
stk.push ( 16 ) ;
stk.push ( 10 ) ;
stk.push ( 19 ) ;
stk.push ( -3 ) ;
stk.push ( 22 ) ;
stk.push ( 18 ) ;
int sz = stk.size( ) ;
cout << "Стек содержит " << sz << " элементов" << endl ;
// удаление элементов из стека
while ( !stk.empty( ) )
{
int i = stk.top( ) ;
cout << i << " " ;
stk.pop( ) ;
}
}
320
Глава 12
В этой программе мы создали стек целых чисел. После создания объекта stk мы
добавляем элементы в стек посредством метода push( ). Функция size( ) возвращает
общее количество элементов в стеке. Метод top( ) возвращает элемент, находящий-ся на вершине стека. Мы вызываем этот метод в while-цикле, который выполняется
до тех пор, пока стек не окажется пустым. Мы проверяем это условие при помощи
функции empty( ). После отображения элемента на вершине стека для его удаления
вызывается метод pop( ).
Стек может быть реализован при помощи вектора, списка или двусторонней очереди (deque). Можно указать тип базового контейнера в качестве второго параметра в конструкторе стека, как показано ниже:
stack<int, vector<int>> stk ;
По умолчанию в качестве базового контейнера используется класс deque.
Очередь (queue)
Очередь (queue) реализуется в программном коде так же, как и стек. В частности, если мы хотим создать очередь целых чисел в виде связного списка, тогда инструкция для объявления такой очереди будет следующей:
queue <int, list<int>> q ;
где q — это контейнер типа queue, задействованный в качестве связного списка
целых чисел. Такие методы, как size( ), front( ), empty( ), действуют таким же образом, как и в случае со стеком. Поэтому я предложил бы вам самим написать программу для управления очередью целых чисел.
Допустим, есть ряд заданий, которые должен обрабатывать процессор. У каждого
задания есть имя и номер приоритета. Чем меньше номер приоритета, тем выше
приоритет задания. Задания эти должны быть переданы процессору в порядке их
приоритета. Достичь этого можно при помощи контейнера priority_queue (очередь
с приоритетом), как показано ниже:
#include <iostream>
#include <queue>
#include <string>
#include <vector>
using namespace std ;
class Task
{
private :
string pname ;
int ppri ;
public :
Task ( string n, int pr )
{
pname = n ;ppri = pr ;
}
Стандартная библиотека шаблонов
321
friend class PrioritizeTasks ;
friend ostream& operator << ( ostream &s, Task &t ) ;
} ;
ostream& operator << ( ostream &o, Task &t )
{
o << "Процесс: " << t.pname << " Приоритет: " << t.ppri << endl ; return ( o ) ;
}
class PrioritizeTasks
{
public :
int operator( ) ( const Task &t1, const Task &t2 )
{
return t1.ppri > t2.ppri ;
}
} ;
int main( )
{
priority_queue<Task, vector<Task>, PrioritizeTasks> pq ; Task tarr[ ] = {
Task ( "SWAP", 4 ), Task ( "PRNT", 17 ),
Task ( "WORD", 5 ), Task ( "COPY", 3 ),
Task ( "RENM", 6 ), Task ( "DELT", 18 ),
Task ( "CRET", 1 ), Task ( "DUMP", 9 )
} ;
for ( auto t : tarr )
pq.push ( t ) ;
Task tk ;
while ( !pq.empty( ) )
{
tk = pq.top( ) ;
cout << tk ;
pq.pop( ) ;
}
}
В этой программе мы сконструировали объект pq класса priority_queue, применив
следующую инструкцию:
priority_queue <Task, vector<Task>, PrioritizeTasks> pq ; Vector-контейнер pq хранит объекты Task класса Task. Помимо этого, в объявлении
указывается, что класс PrioritizeTasks предоставляет функцию для определения порядка, в котором задачи должны помещаться в очередь с приоритетом.
После создания массива tarr, содержащего объекты класса Task, при помощи for-цикла мы добавляем эти объекты в очередь с приоритетом pq, обращаясь к методу
322
Глава 12
push( ). При добавлении объектов в pq вызывается функция перегруженного оператора ( ) (которая является функцией-членом класса PrioritizeTasks). Эта функция
сравнивает приоритеты двух объектов t1 и t2, возвращая 0 или 1. Заметьте, что
PrioritizeClass объявлен как друг класса Task, поскольку функция перегруженного
оператора ( ) должна обращаться к его закрытым членам.
После создания очереди с приоритетом мы отображаем ее содержимое в цикле, вызывая top( ) для доступа к отдельному элементу и pop( ) для его удаления из очереди.
Объект-функция
Объект-функция, или функциональный объект — это класс, реализующий перегруженный оператор ( ). В нашей программе таким объектом-функцией является
PrioritizeTask. Он также известен как оператор обращения (call operator). Функциональный объект предпочтительнее, чем вызов функции, в двух отношениях, поскольку он:
Может содержать члены данных.
Может использоваться как обобщенный параметр.
В частности, объекты-функции применяются в качестве критерия сортировки контейнеров.
К примеру, в следующем объявлении
multiset <int, less<int> > ms1 { 2, 3, 11, -6, 11, 2 } ; less является функциональным объектом. Он возвращает «истинно» (true), если
первый параметр меньше второго параметра. Поскольку контейнер set хранит свои
элементы в отсортированном порядке, ему нужен способ сравнения двух элементов. Сравнение осуществляется при помощи объекта-функции less.
При желании можно задать собственные критерии сортировки, создав функциональный объект и указав его в списке шаблонов для контейнера, как показано
ниже:
multiset <int, myfunctor<int> > ms1 { 2, 3, 11, -6, 11, 2 } ; Кроме того, объекты-функции широко применяются в алгоритмах. Например, рассмотрим следующий алгоритм с использованием remove_if( ):
remove_if ( v.begin( ), v.end( ) , IsOdd ) ;
Здесь IsOdd является функциональным объектом. Если элемент в векторе v окажется нечетным, он будет удален из вектора. Ниже приведена полная реализация
такого решения:
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std ;
Стандартная библиотека шаблонов
323
class IsOdd
{
public :
bool operator ( ) ( int num )
{
return ( ( num % 2 ) == 1 ) ;
}
} ;
int main( )
{
vector <int> v { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 } ;
vector <int>::iterator pend ;
vector <int>::iterator q ;
pend = remove_if ( v.begin( ), v.end( ), IsOdd( ) ) ;
for ( q = v.begin( ) ;
q != pend ;++q )
cout << *q << endl ;
}
1. Укажите, верны ли следующие утверждения:
STL означает стандартный язык программирования.
Алгоритмы библиотеки STL используются для создания наборов стандартных
и пользовательских типов данных.
Функция push_back( ) применяется для удаления элемента в конце вектора.
Стек и очередь являются адаптерами контейнеров.
Множество и мультимножество — это разновидности ассоциативных контейнеров.
2. Решите следующие задачи:
Составьте программу для подсчета количества вхождений слова в текстовом
файле.
Составьте программу для управления стеком строк.
Составьте программу для ведения телефонной книги, содержащей имена або-нентов и номера телефонов. Предусмотрите возможность поиска по имени або-нента либо по номеру телефона.
Составьте программу, применяющую алгоритм сортировки к набору строк, хра-нящихся в векторе.
324
Глава 12
Для хранения, извлечения и управления несколькими числами/строками можно
использовать массивы.
У массивов есть два существенных недостатка:
• У них отсутствует механизм организации данных различными способами, такими как пары «ключ-значение», упорядоченные множества и т. п.
• У них нет средств доступа к данным в порядке очередности, сортировки
и т. п.
Вместо массивов следует использовать стандартную библиотеку шаблонов
(STL).
Преимущества применения библиотеки STL:
• Высокоэффективная, созданная экспертами, проверенная временем.
• Содержит готовые классы для большинства структур данных, что позволяет
сосредоточиться не на их построении, а на самой программе.
• Позволяет расширять классы в соответствии с нашими потребностями.
Три ключевых компонента библиотеки STL:
• Контейнеры — хранение данных.
• Итераторы — обход элементов контейнера.
• Алгоритмы — выполнение различных операций над элементами контейнера.
Типы контейнеров:
• Последовательные — vector (вектор), deque (двусторонняя очередь, дек), list (список).
• Ассоциативные — set (множество), multiset (мультимножество), map (отображение) и multimap (мультиотображение).
• Контейнеры-адаптеры — stack (стек), queue (очередь) и priority_queue (очередь с приоритетом).
• Прочие — bitset (битовое множество), valarray (числовой массив).
Типы итераторов:
• Входной итератор.
• Выходной итератор.
• Однонаправленный итератор.
• Двунаправленный итератор.
• Итератор прямого доступа.
Стандартная библиотека шаблонов
325
Разные контейнеры поддерживают различные типы итераторов.
Константные итераторы могут изменять элементы контейнера, неконстантные — нет.
Алгоритмы — обобщенные функции, выполняющие стандартные операции, такие как вставка, удаление, поиск, сортировка и сравнение элементов или целых
контейнеров.
Объект-функция или функциональный объект — это класс, реализующий перегруженный оператор ( ).
326
Глава 12
Предметный указатель
Кому-то нравится читать справочную информацию,
кому-то нет. Но все любят «быструю помощь».
Этот указатель поможет вам ее получить
Предметный указатель
329
B
I
bad( ) 216
ifstream
basic_fstream 202
◊ get( ) 204
basic_ifstream 202
◊ eof( ) 204
basic_istream 192
iostream 189, 190, 191
basic_ofstream 202
◊ istream 192
basic_ostream 192
◊ ostream 194
basic_streambuf 192
◊ класс 196
istrstream 211
C
◊ ostrstream 211
catch 32, 39, 281
◊ catch-блок 282, 292
M
cin 40, 202
main( ) 102, 166
const
◊ const_iterator 306
◊
N
возврат значений 57
◊ задать данные 75
new 117, 120, 121
◊ переменные 52
◊ спецификатор 52, 55, 165
◊
O
ссылки 54
◊ указатели 53
ofstream 208
◊ универсальный спецификатор 124
◊ write( ) 208
◊ функции-члены 57
ostream 209
const_cast 39, 248
ostrstream 211
cout 40, 189, 191, 194, 202, 204, 212
P
D
private 145, 146
delete 39, 117, 121, 180, 296, 306
dynamic_cast 246
R
E
reinterpret_cast 248
endl 41
S
eof( ) 216
explicit 39
strstream 211
◊ istrstream 211
F
strstreams 211
fail( ) 216
W
failbit 216
write( ) 208
G
get( ) 193
getline( ) 193
good( ) 216
330 Предметный
указатель
А
◊ тип float 34
◊ тип int 34
Абстракция 25
Деструктор 94, 121
◊ операций ввода-вывода 190
◊ виртуальные деструкторы 179
Архитектура STL 303
Динамическая идентификация типа 242
◊ алгоритмы 306
Динамические контейнеры 296
◊ итераторы 305
◊ компоненты STL 304
И
◊ контейнеры, итераторы и алгоритмы 304
Инкапсуляция 29, 33
В
Инстант См. Объект класса
Использование оператора разрешения
Ввод-вывод 189
контекста 240
◊ Unicode 195
◊ библиотека iostream 190
К
◊ в файл 202
◊ записей 206
Класс 29, 34, 89
◊ манипуляторы потоков 196
◊ complex 95, 214
◊ обработка ошибок ввода-вывода 215
◊ index 98, 143
◊ общепринятые требования к системе
◊ абстрактный 168
ввода/вывода 189
◊ базовый (родительский) 30, 151
◊ объектов 213
◊ интерфейс класса 90
◊ пользовательский манипулятор 199
◊ клиентский код 102
◊ потоки 190
◊ код реализации класса 103
◊ работа с файлом 203
◊ объект класса 122
◊ символьный 203
◊ объявление класса 102
◊ строк 205
◊ отношения принадлежности 227
◊ строковые потоки 211
◊ пользовательский 30
Вектор-контейнер (vector) 307
◊ порядок перечисления классов 157
◊ класс point 309
◊ производный (дочерний) 30, 151
Взаимодействие с файловой системой 217
Ключевые слова
Выделение данных
◊ auto 43
◊ стек 149
◊ explicit 234
Выделение памяти 117
◊ mutable 236
◊ VPTR 171
◊ private 90, 102
◊ VTABLE 171
◊ public 90, 102
◊ динамическое выделение памяти 117
◊ using 241
◊ для массивов и структур 118
Комментарии 38
◊ для объектов 120
Компилятор 71, 80, 131, 171
◊ статическое выделение памяти 117
Конструктор 92, 121, 131, 136, 179
◊ стек 117
◊ с одним аргументом 136
◊ копирования 126, 129
Д
М
Данные
◊ пользовательский тип 130
Многократное использование 32
◊ простой (встроенный) типа 130
Множество (set) и мультимножество
◊ скрытие данных 90
(multi-set) 313
◊
Мультиотображение (multimap) 317
тип bool 58
◊ тип complex 78
Предметный указатель
331
Н
◊ доступа к члену класса 91
◊ разрешения контекста 240
Нарезка объекта См. Срезание объекта
Организация программы 102
Наследование
◊ компиляция и сборка 106
◊ private (закрытое) 154
◊ поэтапная разработка 158
◊ protected (защищенное) 154
Особенности С++
◊ public (открытое) 154
◊ ввод и вывод 40
Наследование 30, 34, 35, 143
◊ возвращение значения по ссылке 51
◊ базовый и производный классы 143
◊ вывод типов 43
◊ виды 154
◊ динамическая инициализация 43
◊ конструкторы 151
◊ динамическое объявление переменных
◊ многоуровневое 155
42
◊ множественное 156
◊ комментарии 39
◊ одиночное 154
◊ неименованные объединения
◊ предупреждение 157
и перечисления 44
◊ применение 149
◊ приведение типов 45
Неструктурные языки программирования
◊ пустой указатель (void) 46
23
◊
◊ синтаксис 43
недостатки 24
◊ ссылки 47
Новые ключевые слова 39
◊ типы обращений к функциям 48
О
Отношения включения 31, 34, 35, 143, 227
Отображение (map) 317
Очередь-контейнер (queue) 320
Обобщенная функция
◊
◊ объект-функция 322
специализация 264
Обработка исключений 32, 281
◊ библиотечные классы исключений 284
П
◊ висячий указатель 296
◊
Полиморфизм 31, 35, 165, 167
иерархия классов исключений 282
◊
Преобразование данных 129
некорректное удаление массива 296
◊
◊ в исходном объекте 132
необработанные исключения 294
◊
◊ в целевом объекте 134
обработчик исключений 282
◊
◊ между встроенными типами 129
объект-исключение 281
◊
◊
повторное удаление объекта 296
между встроенными
◊
и пользовательскими типами 130
пользовательские классы исключений
◊
290
между различными пользовательскими
◊ спецификация исключений 293
типами данных 132
◊
Приведение типов 244
точка выброса 281
◊
Пространство имен 237
утечка памяти 295
◊ namespace 237
Объект 27, 28, 34
◊
◊
память 100
глобальное 237
◊
◊
характеристики 33
псевдоним пространства имен 238
ООП 23, 26, 34, 35, 189
◊ способы применения 240
◊ истоки 23
Прямой доступ 208
◊ концепции 28
◊ характеристики 26
Р
Оператор
◊ (.) 91
Режимы открытия файла 210
◊ ++ 98
◊ :: 46
332 Предметный
указатель
С
◊ деструктор 94
◊ дружественная (friend) 81, 229
Связывание
◊ исходные значения для аргументов 72
◊ динамическое 169
◊ конструктор 93
◊ позднее 168
◊ неявный конструктор 94
◊ статистическое 169
◊ особенности перегрузки функций 74
◊ функций 168
◊ перегрузка операторов 76, 86
Сериализация 214
◊ перегрузка функций 73, 165
Скрытие данных 29, 35
◊ прототип 71, 72
Список-контейнер (list) 311
◊ синтаксис возвращаемого типа 81
Срезание объекта 177
◊ статическая (static) 81, 123
Стек-контейнер (stack) 319
◊ строгая проверка типов 71
Структура 89, 101
◊
◊ чистая виртуальная функция 167
разница между структурой и классом 102
◊ экземплярная (instance) 81
Структурное программирование 24
◊ характеристики 24
Счетчик count 123
Ш
У
Шаблоны 32, 34, 35, 143
◊ вариативные 275
◊ для пользовательских типов 261
Указатель
◊
◊ классов 267
const 53
◊
◊ макросы 265
this 97, 100, 230
◊
◊ области применения 276
интеллектуальный 295
◊
◊ полезные советы 273
на члены классов 171, 249
Унарный оператор
◊ связного списка 271
◊ перегрузка 98
◊ сортировка 266
◊ сортировка на основе шаблона 266
Ф
◊ стандартная библиотека 276
◊ шаблонов 303
Функции
◊ функций 259
◊ встраиваемые 79, 86
◊ функция с набором типов 264
◊ перегрузка операторов 165
◊ связывание функций 168
Э
◊ функции-члены (компонентные
функции, методы) 27, 91
Экземпляр 91
Функция
◊ виртуальная (virtual) 81, 165, 169, 176
◊ вызовы перегруженной операторной
функции 100
