Подробнее о стандартном преобразовании
Имеется пять видов стандартных преобразований, а именно:
1. преобразования целых типов: приведение от целого типа или перечисления к любому другому целому типу (исключая трансформации, которые выше были отнесены к категории расширения типов);
2. преобразования типов с плавающей точкой: приведение от любого типа с плавающей точкой к любому другому типу с плавающей точкой (исключая трансформации, которые выше были отнесены к категории расширения типов);
3. преобразования между целым типом и типом с плавающей точкой: приведение от любого типа с плавающей точкой к любому целому типу или наоборот;
4. преобразования указателей: приведение целого значения 0 к типу указателя или трансформация указателя любого типа в тип void*;
5. преобразования в тип bool: приведение от любого целого типа, типа с плавающей точкой, перечислимого типа или указательного типа к типу bool.
Вот несколько примеров:
extern void print( void* );
extern void print( double );
int main() {
int i;
print( i ); // соответствует print( double );
// i подвергается стандартному преобразованию из int в double
print( &i ); // соответствует print( void* );
// &i подвергается стандартному преобразованию
// из int* в void*
return 0;
}
Преобразования, относящиеся к группам 1, 2 и 3, потенциально опасны, так как целевой тип может и не обеспечивать представления всех значений исходного. Например, с помощью float нельзя адекватно представить все значения типа int. Именно по этой причине трансформации, входящие в эти группы, отнесены к категории стандартных преобразований, а не расширений типов.
int i;
void calc( float );
int main() {
calc( i ); // стандартное преобразование между целым типом и типом с
// плавающей точкой потенциально опасно в зависимости от
// значения i
return 0;
}
При вызове функции calc() применяется стандартное преобразование из целого типа int в тип с плавающей точкой float. В зависимости от значения переменной i может оказаться, что его нельзя сохранить в типе float без потери точности.
Предполагается, что все стандартные изменения требуют одного объема работы. Например, преобразование из char в unsigned char не более приоритетно, чем из char в double. Близость типов не принимается во внимание. Если две устоявших функции требуют для установления соответствия стандартной трансформации фактического аргумента, то вызов считается неоднозначным и помечается компилятором как ошибка. Например, если даны две перегруженные функции:
extern void manip( long );
extern void manip( float );
то следующий вызов неоднозначен:
int main() {
manip( 3.14 ); // ошибка: неоднозначность
// manip( float ) не лучше, чем manip( int )
return 0;
}
Константа 3.14 имеет тип double. С помощью того или иного стандартного преобразования соответствие может быть установлено с любой из перегруженных функций. Поскольку есть две трансформации, приводящие к цели, вызов считается неоднозначным. Ни одно преобразование не имеет преимущества над другим. Программист может разрешить неоднозначность либо путем явного приведения типа:
manip ( static_cast<long>( 3.14 ) ); // manip( long )
либо используя суффикс, обозначающий, что константа принадлежит к типу float:
manip ( 3.14F ) ); // manip( float )
Вот еще несколько примеров неоднозначных вызовов, которые помечаются как ошибки, поскольку соответствуют нескольким перегруженным функциям:
extern void farith( unsigned int );
extern void farith( float );
int main() {
// каждый из последующих вызовов неоднозначен
farith( 'a' ); // аргумент имеет тип char
farith( 0 ); // аргумент имеет тип int
farith( 2uL ); // аргумент имеет тип unsigned long
farith( 3.14159 ); // аргумент имеет тип double
farith( true ); // аргумент имеет тип bool
}
Стандартные преобразования указателей иногда противоречат интуиции. В частности, значение 0 приводится к указателю на любой тип; полученный таким образом указатель называется нулевым. Значение 0 может быть представлено как константное выражение целого типа:
void set(int*);
int main() {
// преобразование указателя из 0 в int* применяется к аргументам
// в обоих вызовах
set( 0L );
set( 0x00 );
return 0;
}
Константное выражение 0L (значение 0 типа long int) и константное выражение 0x00 (шестнадцатеричное целое значение 0) имеют целый тип и потому могут быть преобразованы в нулевой указатель типа int*.
Но поскольку перечисления не относятся к целым типам, элемент, равный 0, не приводим к типу указателя:
enum EN { zr = 0 };
set( zr ); // ошибка: zr нельзя преобразовать в тип int*
Вызов функции set() является ошибкой, так как не существует преобразования между значением zr элемента перечисления и формальным параметром типа int*, хотя zr равно 0.
Следует отметить, что константное выражение 0 имеет тип int. Для его приведения к типу указателя требуется стандартное преобразование. Если в множестве перегруженных функций есть функция с формальным параметром типа int, то именно в ее пользу будет разрешена перегрузка в случае, когда фактический аргумент равен 0:
void print( int );
void print( void * );
void set( const char * );
void set( char * );
int main () {
print( 0 ); // вызывается print( int );
set( 0 ); // неоднозначность
return 0;
}
При вызове print(int) имеет место точное соответствие, тогда как для вызова print(void*) необходимо приведение значения 0 к типу указателя. Поскольку соответствие лучше преобразования, для разрешения этого вызова выбирается функция print(int). Обращение к set() неоднозначно, так как 0 соответствует формальным параметрам обеих перегруженных функций за счет применения стандартной трансформации. Раз обе функции одинаково хороши, фиксируется неоднозначность.
Последнее из возможных преобразований указателя позволяет привести указатель любого типа к типу void*, поскольку void* – это родовой указатель на любой тип данных. Вот несколько примеров:
#include <string>
extern void reset( void * );
void func( int *pi, string *ps ) {
// ...
reset( pi ); // преобразование указателя: int* в void*
/// ...
reset( ps ); // преобразование указателя: string* в void*
}
Только указатели на типы данных могут быть приведены к типу void* с помощью стандартного преобразования, с указателями на функции так поступать нельзя:
typedef int (*PFV)();
extern PFV testCases[10]; // массив указателей на функции
extern void reset( void * );
int main() {
// ...
reset( textCases[0] ); // ошибка: нет стандартного преобразования
// между int(*)() и void*
return 0;
}
Подробнее о точном соответствии
Самый простой случай возникает тогда, когда типы фактических аргументов совпадают с типами формальных параметров. Например, есть две показанные ниже перегруженные функции max(). Тогда каждый из вызовов max() точно соответствует одному из объявлений:
int max( int, int );
double max( double, double );
int i1;
void calc( double d1 ) {
max( 56, i1 ); // точно соответствует max( int, int );
max( d1, 66.9 ); // точно соответствует max( double, double );
}
Перечислимый тип точно соответствует только определенным в нем элементам перечисления, а также объектам, которые объявлены как принадлежащие к этому типу:
enum Tokens { INLINE = 128; VIRTUAL = 129; };
Tokens curTok = INLINE;
enum Stat { Fail, Pass };
extern void ff( Tokens );
extern void ff( Stat );
extern void ff( int );
int main() {
ff( Pass ); // точно соответствует ff( Stat )
ff( 0 ); // точно соответствует ff( int )
ff( curTok ); // точно соответствует ff( Tokens )
// ...
}
Выше уже упоминалось, что фактический аргумент может точно соответствовать формальному параметру, даже если для приведения их типов необходимо некоторое тривиальное преобразование, первое из которых – преобразование l-значения в r-значение. Под l-значением понимается объект, удовлетворяющий следующим условиям:
можно получить адрес объекта;
можно получить значение объекта;
это значение легко модифицировать (если только в объявлении объекта нет спецификатора const).
Напротив, r-значение – это выражение, значение которого вычисляется, или выражение, обозначающее временный объект, для которого нельзя получить адрес и значение которого нельзя модифицировать. Вот простой пример:
int calc( int );
int main() {
int lval, res;
lval = 5; // lvalue: lval; rvalue: 5
res = calc( lval );
// lvalue: res
// rvalue: временный объект для хранения значения,
// возвращаемого функцией calc()
return 0;
}
В первом операторе присваивания переменная lval – это l-значение, а литерал 5 – r-значение. Во втором операторе присваивания res – это l-значение, а временный объект, в котором хранится результат, возвращаемый функцией calc(), – это r-значение.
В некоторых ситуациях в контексте, где ожидается значение, можно использовать выражение, представляющее собой l-значение:
int obj1;
int obj2;
int main() {
// ...
int local = obj1 + obj2;
return 0;
}
Здесь obj1 и obj2 – это l-значения. Однако для выполнения сложения в функции main() из переменных obj1 и obj2 извлекаются их значения. Действие, состоящее в извлечении значения объекта, представленного выражением вида l-значение, называется преобразованием l-значения в r-значение.
Когда функция ожидает аргумент, переданный по значению, то в случае, если аргумент является l-значением, выполняется его преобразование в r-значение:
#include <string>
string color( "purple" );
void print( string );
int main() {
print( color ); // точное соответствие: преобразование lvalue
// в rvalue
return 0;
}
Так как аргумент в вызове print(color) передается по значению, то производится преобразование l-значения в r-значение для извлечения значения color и передачи его в функцию с прототипом print(string). Однако несмотря на то, что такое приведение имело место, считается, что фактический аргумент color точно соответствует объявлению print(string).
При вызове функций не всегда требуется применять к аргументам подобное преобразование. Ссылка представляет собой l-значение; если у функции есть параметр-ссылка, то при вызове функция получает l-значение. Поэтому к фактическому аргументу, которому соответствует формальный параметр-ссылка, описанное преобразование не применяется. Например, пусть объявлена такая функция:
#include <list>
void print( list<int> & );
В вызове ниже li – это l-значение, представляющее объект list<int>, передаваемый функции print():
list<int> li(20);
int main() {
// ...
print( li ); // точное соответствие: нет преобразования lvalue в
// rvalue
return 0;
}
Сопоставление li с параметром-ссылкой считается точным соответствием.
Второе преобразование, при котором все же фиксируется точное соответствие, – это преобразование массива в указатель. Как уже отмечалось в разделе 7.3, параметр функции никогда не имеет тип массива, трансформируясь вместо этого в указатель на его первый элемент. Аналогично фактический аргумент типа массива из NT (где N – число элементов в массиве, а T – тип каждого элемента) всегда приводится к типу указателя на T. Такое преобразование типа фактического аргумента и называется преобразованием массива в указатель. Несмотря на это, считается, что фактический аргумент точно соответствует формальному параметру типа “указатель на T”. Например:
int ai[3];
void putValues(int *);
int main() {
// ...
putValues(ai); // точное соответствие: преобразование массива в
// указатель
return 0;
}
Перед вызовом функции putValues() массив преобразуется в указатель, в результате чего фактический аргумент ai (массив из трех целых) приводится к указателю на int. Хотя формальным параметром функции putValues() является указатель и фактический аргумент при вызове преобразован, между ними устанавливается точное соответствие.
При установлении точного соответствия допустимо также преобразование функции в указатель. (Оно упоминалось в разделе 7.9.) Как и параметр-массив, параметр-функция становится указателем на функцию. Фактический аргумент типа “функция” также автоматически приводится к типу указателя на функцию. Такое преобразование типа фактического аргумента и называется преобразованием функции в указатель. Хотя трансформация производится, считается, что фактический аргумент точно соответствует формальному параметру. Например:
int lexicoCompare( const string &, const string & );
typedef int (*PFI)( const string &, const string & );
void sort( string *, string *, PFI );
string as[10];
int main()
{
// ...
sort( as,
as + sizeof(as)/sizeof(as[0] - 1 ),
lexicoCompare // точное соответствие
// преобразование функции в указатель
);
return 0;
}
Перед вызовом sort() применяется преобразование функции в указатель, которое приводит аргумент lexicoCompare от типа “функция” к типу “указатель на функцию”. Хотя формальным параметром функции является указатель, а фактическим – имя функции и, следовательно, было произведено преобразование функции в указатель, считается, что фактический аргумент точно третьему формальному параметру функции sort().
Последнее из перечисленных выше – это преобразование спецификаторов. Оно относится только к указателям и заключается в добавлении спецификаторов const или volatile (или обоих) к типу, который адресует данный указатель:
int a[5] = { 4454, 7864, 92, 421, 938 };
int *pi = a;
bool is_equal( const int * , const int * );
void func( int *parm ) {
// точное соответствие между pi и parm: преобразование спецификаторов
if ( is_equal( pi, parm ) )
// ...
return 0;
}
Перед вызовом функции is_equal() фактические аргументы pi и parm преобразуются из типа “указатель на int” в тип “указатель на const int”. Эта трансформация заключается в добавлении спецификатора const к адресуемому типу, поэтому относится к категории преобразований спецификаторов. Несмотря на то, что функция ожидает получить два указателя на const int, а фактические аргументы являются указателями на int, считается, что точное соответствие между формальными и фактическими параметрами функции is_equal() установлено.
Преобразование спецификаторов применимо только к типу, который адресует указатель. Оно не употребляется в случае, когда формальный параметр имеет спецификатор const или volatile, а фактический аргумент – нет.
extern void takeCI( const int );
int main() {
int ii = ...;
takeCI(ii); // преобразование спецификаторов не применяется
return 0;
}
Хотя формальный параметр функции takeCI() имеет тип const int, а вызывается она с аргументом ii типа int, преобразование спецификаторов не производится: есть точное соответствие между фактическим аргументом и формальным параметром.
Все сказанное верно и для случая, когда аргумент является указателем, а спецификаторы const или volatile относятся к этому указателю:
extern void init( int *const );
extern int *pi;
int main() {
// ...
init(pi); // преобразование спецификаторов не применяется
return 0;
}
Спецификатор const при формальном параметре функции init() относится к самому указателю, а не к типу, который он адресует. Поэтому компилятор при анализе преобразований, которые должны быть применены к фактическому аргументу, не учитывает этот спецификатор. К аргументу pi не применяется преобразование спецификатора: считается, что этот аргумент и формальный параметр точно соответствуют друг другу.
Первые три из рассмотренных преобразований (l-значения в r-значение, массива в указатель и функции в указатель) часто называют трансформациями l-значений. (В разделе 9.4 мы увидим, что хотя и трансформации l-значений, и преобразования спецификаторов относятся к категории преобразований, не нарушающих точного соответствия, его степень считается выше в случае, когда необходима лишь первая трансформация. В следующем разделе мы поговорим об этом несколько подробнее.)
Точное соответствие можно установить принудительно, воспользовавшись явным приведением типов. Например, если есть две перегруженные функции:
extern void ff(int);
extern void ff(void *);
то вызов
ff( 0xffbc ); // вызывается ff(int)
будет точно соответствовать ff(int), хотя литерал 0xffbc записан в виде шестнадцатеричной константы. Программист может заставить компилятор вызвать функцию ff(void *), если явно выполнит операцию приведения типа:
ff( reinterpret_cast<void *>(0xffbc) ); // вызывается ff(void*)
Если к фактическому аргументу применяется такое приведение, то он приобретает тип, в который преобразуется. Явные приведения типов помогают в управлении процессом разрешения перегрузки. Например, если при разрешении перегрузки получается неоднозначный результат (фактические аргументы одинаково хорошо соответствуют двум или более устоявшим функциям), то для устранения неоднозначности можно применить явное приведение типа, заставив компилятор выбрать конкретную функцию.
Поиск и извлечение элемента отображения
Оператор взятия индекса является простейшим способом извлечения элемента. Например:
// map<string,int> word_count;
int count = word_count[ "wrinkles" ];
Однако этот способ работает так, как надо, только при условии, что запрашиваемый ключ действительно содержится в отображении. Иначе оператор взятия индекса поместит в отображение элемент с таким ключом. В данном случае в word_count занесется пара
string( "wrinkles" ), 0
Класс map предоставляет две операции для того, чтобы выяснить, содержится ли в нем определенное значение ключа.
count(keyValue): функция-член count() возвращает количество элементов с данным ключом. (Для отображения оно равно только 0 или 1). Если count() вернула 1, мы можем смело использовать индексацию:
int count = 0;
if ( word_count.count( "wrinkles" ))
count = word_count[ "wrinkles" ];
find(keyValue): функция-член find() возвращает итератор, указывающий на элемент, если ключ найден, и итератор end() в противном случае. Например:
int count = 0;
map<string,int>::iterator it = word_count.find( "wrinkles" );
if ( it != word_count.end() )
count = (*it).second;
Значением итератора является указатель на объект pair, в котором first содержит ключ, а second – значение. (Мы вернемся к этому в следующем подразделе.)
Поиск элемента
Две операции, позволяющие отыскать в наборе определенное значение,– это find() и count(). find() возвращает итератор, указывающий на найденный элемент, или значение, равное end(), если он отсутствует. count() возвращает 1 при наличии элемента и 0 в противном случае. Добавим проверку на существование в функцию build_word_map():
if ( exclusion_set.count( textword ))
continue;
// добавим отсутствующее слово
ПОО и члены пространства имен
Как уже было сказано, определение пространства имен может состоять из разрозненных частей и размещаться в разных файлах. Следовательно, член пространства разрешено объявлять во многих файлах. Например:
// primer.h
namespace cplusplus_primer {
// ...
void inverse( matrix & );
}
// usel.C
#include "primer.h"
// объявление cplusplus_primer::inverse() в use1.C
// use2.C
#include "primer.h"
// объявление cplusplus_primer::inverse() в use2.C
Объявление cplusplus::inverse() в primer.h ссылается на одну и ту же функцию в обоих исходных файлах use1.C и use2.C.
Член пространства имен является глобальной сущностью, хотя его имя квалифицировано. Требование ПОО (правило одного определения, см. раздел 8.2) распространяется и на него. Чтобы удовлетворить этому требованию, программы, в которых используются пространства имен, обычно организуют следующим образом:
1. Объявления функций и объектов, являющихся членами пространства имен, помещают в заголовочный файл, который включается в каждый исходный файл, где они используются.
// ---- primer.h ----
namespace cplusplus_primer {
class matrix { /* ... */ };
// объявления функций
extern matrix operator+ ( const matrix &m1, const matrix &m2 );
extern void inverse( matrix & );
// объявления объектов
extern bool error_state;
}
2. Определения этих членов помещают в исходный файл, содержащий реализацию:
// ---- primer.C ----
#include "primer.h"
namespace cplusplus_primer {
// определения функций
void inverse( matrix & )
{ /* ... */ }
matrix operator+ ( const matrix &ml, const matrix &m2 )
{ /" ... */ }
// определения объектов
bool error_state = false;
}
Для объявления объекта без его определения используется ключевое слово extern, как и в случае такого объявления в глобальной области видимости.
Порядок выполнения инструкций
По умолчанию инструкции программы выполняются одна за другой, последовательно. В программе
int main()
{
readIn();
sort();
compact();
print();
return 0;
}
первой будет выполнена инструкция readIn(), за ней sort(), compact() и наконец print().
Однако представим себе ситуацию, когда количество продаж невелико: оно равно 1 или даже 0. Вряд ли стоит вызывать функции sort() и compact() для такого случая. Но вывести результат все-таки нужно, поэтому функцию print() следует вызывать в любом случае. Для этого случая мы можем использовать условную инструкцию if. Нам придется переписать функцию readIn() так, чтобы она возвращала количество прочитанных записей:
// readIn() возвращает количество прочитанных записей
// возвращаемое значение имеет тип int
int readIn() { ... }
// ...
int main()
{
int count = readIn();
// если количество записей больше 1,
// то вызвать sort() и compact()
if ( count > 1 ) {
sort();
compact();
}
if ( count == 0 )
cout << "Продаж не было\n";
else
print();
return 0;
}
Первая инструкция if обеспечивает условное выполнение блока программы: функции sort() и compact() вызываются только в том случае, если count больше 1. Согласно второй инструкции if на терминал выводится сообщение “Продаж не было”, если условие истинно, т.е. значение count равно 0. Если же это условие ложно, производится вызов функции print(). (Детальное описание инструкции if приводится в разделе 5.3.)
Другим распространенным способом непоследовательного выполнения программы является итерация, или инструкция цикла. Такая инструкция предписывает повторять блок программы до тех пор, пока некоторое условие не изменится с true на false. Например:
int main()
{
int iterations = 0;
bool continue_loop = true;
while ( continue_loop != false )
{
iterations++;
cout << "Цикл был выполнен " << iterations << "раз\n";
if ( iterations == 5 )
continue_loop = false;
}
return 0;
}
В этом надуманном примере цикл while выполняется пять раз, до тех пор пока переменная iterations не получит значение 5 и переменная continue_loop не станет равной false. Инструкция
iterations++;
увеличивает значение переменной iterations на единицу. (Инструкции цикла детально рассматриваются в главе 5.)
Порядок вызова конструкторов и деструкторов
Виртуальные базовые классы всегда конструируются перед невиртуальными, вне зависимости от их расположения в иерархии наследования. Например, в приведенной иерархии у класса TeddyBear (плюшевый мишка) есть два виртуальных базовых: непосредственный– ToyAnimal (игрушечное животное) и экземпляр ZooAnimal, от которого унаследован класс Bear:
class Character { ... }; // персонаж
class BookCharacter : public Character { ... };
// литературный персонаж
class ToyAnimal { ... }; // игрушка
class TeddyBear : public BookCharacter,
public Bear, public virtual ToyAnimal
{ ... };
Эта иерархия изображена на рис. 18.5, где виртуальное наследование показано пунктирной стрелкой, а невиртуальное – сплошной.
Character ZooAnimal ToyAnimal
BookCharacter Bear
TeddyBear
¾¾> невиртуальное наследование
- - - -> виртуальноe наследование
Рис. 18.5. Иерархия виртуального наследования класса TeddyBear
Непосредственные базовые классы просматриваются в порядке их объявления при поиске среди них виртуальных. В нашем примере сначала анализируется поддерево наследования BookCharacter, затем Bear и наконец ToyAnimal. Каждое поддерево обходится в глубину, т.е. поиск начинается с корневого класса и продвигается вниз. Так, для поддерева BookCharacter сначала просматривается Character, а затем BookCharacter. Для поддерева Bear – ZooAnimal, а потом Bear.
При описанном алгоритме поиска порядок вызова конструкторов виртуальных базовых классов для TeddyBear таков: ZooAnimal, потом ToyAnimal.
После того как вызваны конструкторы виртуальных базовых классов , настает черед конструкторов невиртуальных, которые вызываются в порядке объявления: BookCharacter, затем Bear. Перед выполнением конструктора BookCharacter вызывается конструктор его базового класса Character.
Если имеется объявление:
TeddyBear Paddington;
то последовательность вызова конструкторов базовых классов будет такой:
ZooAnimal(); // виртуальный базовый класс Bear
ToyAnimal(); // непосредственный виртуальный базовый класс
Character(); // невиртуальный базовый класс BookCharacter
BookCharacter(); // непосредственный невиртуальный базовый класс
Bear(); // непосредственный невиртуальный базовый класс
TeddyBear(); // ближайший производный класс
причем за инициализацию ZooAnimal и ToyAnimal отвечает TeddyBear – ближайший производный класс объекта Paddington.
Порядок вызова копирующих конструкторов при почленной инициализации (и копирующих операторов присваивания при почленном присваивании) такой же. Гарантируется, что деструкторы вызываются в последовательности, обратной вызову конструкторов.
Порождение класса, контролирующего выход за границы массива
В функции try_array() из раздела 16.13, предназначенной для тестирования нашей предыдущей реализации шаблона класса Array, есть две инструкции:
int index = iA.find( find_val );
Type value = iA[ index ];
find() возвращает индекс первого вхождения значения find_val или -1, если значение в массиве не найдено. Этот код некорректен, поскольку в нем не проверяется, что не была возвращена -1. Поскольку -1 находится за границей массива, то каждая инициализация value может привести к ошибке. Поэтому мы создадим подтип Array, который будет контролировать выход за границы массива, – Array_RC и поместим его определение в заголовочный файл Array_RC.h:
#ifndef ARRAY_RC_H
#define ARRAY_RC_H
#include "Array.h"
template <class Type>
class Array_RC : public virtual Array<Type> {
public:
Array_RC( int sz = ArraySize )
: Array<Type>( sz ) {}
Array_RC( const Array_RC& r );
Array_RC( const Type *ar, int sz );
Type& operator[]( int ix );
};
#endif
Внутри определения производного класса каждая ссылка на спецификатор типа шаблона базового должна быть квалифицирована списком формальных параметров:
Array_RC( int sz = ArraySize )
: Array<Type>( sz ) {}
Такая запись неправильна:
// ошибка: Array - это не спецификатор типа
Array_RC( int sz = ArraySize ) : Array( sz ) {}
Единственное отличие поведения класса Array_RC от базового состоит в том, что оператор взятия индекса контролирует выход за границы массива. Во всех остальных отношениях можно воспользоваться уже имеющейся реализацией шаблона класса Array. Напомним, однако, что конструкторы не наследуются, поэтому в Array_RC определен собственный набор из трех конструкторов. Мы сделали класс Array_RC виртуальным наследником класса Array, поскольку предвидели необходимость множественного наследования.
Вот полная реализация функций-членов Array_RC, находящаяся в файле Array_RC.C (определения функций класса Array помещены в заголовочный файл Array.C, поскольку мы пользуемся моделью конкретизации шаблонов с включением, описанной в разделе 16.18):
#include "Array_RC.h"
#include "Array.C"
#include <assert.h>
template <class Type>
Array_RC<Type>::Array_RC( const Array_RC<Type> &r )
: Array<Type>( r ) {}
template <class Type>
Array_RC<Type>::Array_RC( const Type *ar, int sz )
: Array<Type>( ar, sz ) {}
template <class Type>
Type &Array_RC<Type>::operator[]( int ix ) {
assert( ix >= 0 && ix < Array<Type>::_size );
return ia[ ix ];
}
Мы квалифицировали обращения к членам базового класса Array, например к _size, чтобы предотвратить просмотр Array до момента конкретизации шаблона:
Array<Type>::_size;
Мы достигаем этого, включая в обращение параметр шаблона. Таким образом, имена в определении Array_RC разрешаются тогда, когда определяется шаблон (за исключением имен, явно зависящих от его параметра). Если встречается неквалифицированное имя _size, то компилятор должен найти его определение, если только это имя не зависит явно от параметра шаблона. Мы сделали имя _size зависящим от параметра шаблона, предварив его именем базового класса Array<Type>. Теперь компилятор не будет пытаться разрешить имя _size до момента конкретизации шаблона. (В определении класса Array_Sort мы приведем другие примеры использования подобных приемов.)
Каждая конкретизация Array_RC порождает экземпляр класса Array. Например:
Array_RC<string> sa;
конкретизирует параметром string как шаблон Array_RC, так и шаблон Array. Приведенная ниже программа вызывает try_array() (реализацию см. в разделе 16.13), передавая ей объекты подтипа Array_RC. Если все сделано правильно, то выходы за границы массивы будут замечены:
#include "Array_RC.C"
#include "try_array.C"
int main()
{
static int ia[] = { 12,7,14,9,128,17,6,3,27,5 };
cout << "конкретизация шаблона класса Array_RC<int>\n";
try_array( iA );
return 0;
}
После компиляции и запуска программа печатает следующее:
конкретизация шаблона класса Array_RC<int>
try_array: начальные значения массива
( 10 )< 12, 7, 14, 9, 128, 17
6, 3, 27, 5 >
try_array: после присваиваний
( 10 )< 128, 7, 14, 9, 128, 128
6, 3, 27, 3 >
try_array: почленная инициализация
( 10 )< 12, 7, 14, 9, 128, 128
6, 3, 27, 3 >
try_array: после почленного копирования
( 10 )< 12, 7, 128, 9, 128, 128
6, 3, 27, 3 >
try_array: после вызова grow
( 10 )< 12, 7, 128, 9, 128, 128
6, 3, 27, 3, 0, 0
0, 0, 0, 0 >
искомое значение: 5 возвращенный индекс: -1
Assertion failed: ix >= 0 && ix < _size
Порождение класса отсортированного массива
Вторая наша специализация класса Array– отсортированный подтип Array_Sort. Мы поместим его определение в заголовочный файл Array_S.h:
#ifndef ARRAY_S_H_
#define ARRAY_S_H_
#include "Array.h"
template <class Type>
class Array_Sort : public virtual Array<Type> {
protected:
void set_bit() { dirty_bit = true; }
void clear_bit() { dirty_bit = false; }
void check_bit() {
if ( dirty_bit ) {
sort( 0, Array<Type>::_size-1 );
clear_bit();
}
}
public:
Array_Sort( const Array_Sort& );
Array_Sort( int sz = Array<Type>::ArraySize )
: Array<Type>( sz )
{ clear_bit(); }
Array_Sort( const Type* arr, int sz )
: Array<Type>( arr, sz )
{ sort( 0,Array<Type>::_size-1 ); clear_bit(); }
Type& operator[]( int ix )
{ set_bit(); return ia[ ix ]; }
void print( ostream& os = cout ) const
{ check_bit(); Array<Type>::print( os ); }
Type min() { check_bit(); return ia[ 0 ]; }
Type max() { check_bit(); return ia[ Array<Type>::_size-1 ]; }
bool is_dirty() const { return dirty_bit; }
int find( Type );
void grow();
protected:
bool dirty_bit;
};
#endif
Array_Sort включает дополнительный член – dirty_bit. Если он установлен в true, то не гарантируется, что массив по-прежнему отсортирован. Предоставляется также ряд вспомогательных функций доступа: is_dirty() возвращает значение dirty_bit; set_bit() устанавливает dirty_bit в true; clear_bit() сбрасывает dirty_bit в false; check_bit() пересортировывает массив, если dirty_bit равно true, после чего сбрасывает его в false. Все операции, которые потенциально могут перевести массив в неотсортированное состояние, вызывают set_bit().
При каждом обращении к шаблону Array необходимо указывать полный список параметров.
Array_Sort( const Array_Sort<Type> &as )
а не
template <class Type>
Array_Sort<Type>::
Array_Sort<Type>( // ошибка: это не спецификатор типа
поскольку второе вхождение Array_Sort синтаксически является именем функции, а не спецификатором типа.
Есть две причины, по которым правильна такая запись:
if ( as.is_dirty() )
sort( 0, _size );
а не просто
as.check_bit();
Первая причина связана с типизацией: check_bit() – это неконстантная функция-член, которая модифицирует объект класса. В качестве аргумента передается ссылка на константный объект. Применение check_bit() к аргументу as нарушает его константность и потому воспринимается компилятором как ошибка.
Вторая причина: копирующий конструктор рассматривает массив, ассоциированный с as, только для того, чтобы выяснить, нуждается ли вновь созданный объект класса Array_Sort в сортировке. Напомним, однако, что член dirty_bit нового объекта еще не инициализирован. К началу выполнения тела конструктора Array_Sort инициализированы только члены ia и _size, унаследованные от класса Array. Этот конструктор должен с помощью clear_bit() задать начальные значения дополнительных членов и, вызвав sort(), обеспечить специальное поведение подтипа. Конструктор Array_Sort можно было бы инициализировать и по-другому:
// альтернативная реализация
template <class Type>
Array_Sort<Type>::
Array_Sort( const Array_Sort<Type> &as )
: Array<Type>( as )
{
dirty_bit = as.dirty_bit;
clear_bit();
}
Ниже приведена реализация функции-члена grow().1 Наша стратегия состоит в том, чтобы воспользоваться имеющейся в базовом классе Array реализацией для выделения дополнительной памяти, а затем пересортировать элементы и сбросить dirty_bit:
template <class Type>
void Array_Sort<Type>::grow()
{
Array<Type>::grow();
sort( 0, Array<Type>::_size-1 );
clear_bit();
}
Так выглядит реализация двоичного поиска в функции-члене find() класса Array_Sort:
template <class Type>
int Array_Sort<Type>::find( const Type &val )
{
int low = 0;
int high = Array<Type>::_size-1;
check_bit();
while ( low <= high ) {
int mid = ( low + high )/2;
if ( val == ia[ mid ] )
return mid;
if ( val < ia[ mid ] )
high = mid-1;
else low = mid+1;
}
return -1;
}
Протестируем нашу реализацию класса Array_Sort с помощью функции try_array(). Показанная ниже программа тестирует шаблон этого класса для конкретизаций типами int и string:
#include "Array_S.C"
#include "try_array.C"
#include <string>
main()
{
static int ia[ 10 ] = { 12,7,14,9,128,17,6,3,27,5 };
static string sa[ 7 ] = {
"Eeyore", "Pooh", "Tigger",
"Piglet", "Owl", "Gopher", "Heffalump"
};
Array_Sort<int> iA( ia,10 );
Array_Sort<string> SA( sa,7 );
cout << "конкретизация класса Array_Sort<int>"
<< endl;
try_array( iA );
cout << "конкретизация класса Array_Sort<string>"
<< endl;
try_array( SA );
return 0;
}
При конкретизации типом string после компиляции и запуска программа печатает следующий текст (обратите внимание, что попытка вывести элемент с индексом -1 заканчивается крахом):
конкретизация класса Array_Sort<string>
try_array: начальные значения массива
( 7 )< Eeyore, Gopher, Heffalump, Owl, Piglet, Pooh
Tigger >
try_array: после присваиваний
( 7 )< Eeyore, Gopher, Owl, Piglet, Pooh, Pooh
Pooh >
try_array: почленная инициализация
( 7 )< Eeyore, Gopher, Owl, Piglet, Pooh, Pooh
Pooh >
try_array: после почленного копирования
( 7 )< Eeyore, Piglet, Owl, Piglet, Pooh, Pooh
Pooh >
try_array: после вызова grow
( 7 )< <empty>, <empty>, <empty>, <empty>, Eeyore, Owl
Piglet, Piglet, Pooh, Pooh, Pooh >
искомое значение: Tigger возвращенный индекс: -1
Memory fault (coredump)
После почленного копирования массив не отсортирован, поскольку виртуальная функция вызывалась через объект, а не через указатель или ссылку. Как было сказано в разделе 17.5, в таком случае вызывается экземпляр функции из класса именно этого объекта, а не того подтипа, который может находиться в переменной. Поэтому функция sort() никогда не будет вызвана через объект Array. (Разумеется, мы реализовали такое поведение только в целях демонстрации.)
Построение набора стоп-слов
Отображение состоит из пар ключ/значение. Множество (set), напротив, содержит неупорядоченную совокупность ключей. Например, бизнесмен может составить “черный список” bad_checks, содержащий имена лиц, в течение последних двух лет присылавших фальшивые чеки. Множество полезно тогда, когда нужно узнать, содержится ли определенное значение в списке. Скажем, наш бизнесмен, принимая чек от кого-либо, может проверить, есть ли его имя в bad_checks.
Для нашей поисковой системы мы построим набор стоп-слов– слов, имеющих семантически нейтральное значение (артикли, союзы, предлоги), таких, как the, and, into, with, but
и т.д. (это улучшает качество системы, однако мы уже не сможем найти первое предложение из знаменитого монолога Гамлета: “To be or not to be?”). Прежде чем добавлять слово к word_map, проверим, не содержится ли оно в списке стоп-слов. Если содержится, проигнорируем его.
Потоковые итераторы
Стандартная библиотека предоставляет средства для работы потоковых итераторов чтения и записи совместно со стандартными контейнерами и обобщенными алгоритмами. Класс istream_iterator поддерживает итераторные операции с классом istream или одним из производных от него, например ifstream для работы с потоком ввода из файла. Аналогично ostream_iterator поддерживает итераторные операции с классом ostream или одним из производных от него, например ofstream для работы с потоком вывода в файл. Для использования любого из этих итераторов следует включить заголовочный файл
#include <iterator>
В следующей программе мы пользуемся потоковым итератором чтения для получения из стандартного ввода последовательности целых чисел в вектор, а затем применяем потоковый итератор записи в качестве целевого в обобщенном алгоритме unique_copy():
#include <iostream>
#include <iterator>
#include <algorithm>
#include <vector>
#include <functional>
/*
* вход:
* 23 109 45 89 6 34 12 90 34 23 56 23 8 89 23
*
* выход:
* 109 90 89 56 45 34 23 12 8 6
*/
int main()
{
istream_iterator< int > input( cin );
istream_iterator< int > end_of_stream;
vector<int> vec;
copy ( input, end_of_stream, inserter( vec, vec.begin() ));
sort( vec.begin(), vec.end(), greater<int>() );
ostream_iterator< int > output( cout, " " );
unique_copy( vec.begin(), vec.end(), output );
}
Повторное возбуждение исключения
Может оказаться так, что в одном предложении catch не удалось полностью обработать исключение. Выполнив некоторые корректирующие действия, catch-обработчик может решить, что дальнейшую обработку следует поручить функции, расположенной “выше” в цепочке вызовов. Передать исключение другому catch-обработчику можно с помощью повторного возбуждения исключения. Для этой цели в языке предусмотрена конструкция
throw;
которая вновь генерирует объект-исключение. Повторное возбуждение возможно только внутри составной инструкции, являющейся частью catch-обработчика:
catch ( exception eObj ) {
if ( canHandle( eObj ) )
// обработать исключение
return;
else
// повторно возбудить исключение, чтобы его перехватил другой
// catch-обработчик
throw;
}
При повторном возбуждении новый объект-исключение не создается. Это имеет значение, если catch-обработчик модифицирует объект, прежде чем возбудить исключение повторно. В следующем фрагменте исходный объект-исключение не изменяется. Почему?
enum EHstate { noErr, zeroOp, negativeOp, severeError };
void calculate( int op ) {
try {
// исключение, возбужденное mathFunc(), имеет значение zeroOp
mathFunc( op );
}
catch ( EHstate eObj ) {
// что-то исправить
// пытаемся модифицировать объект-исключение
eObj = severeErr;
// предполагалось, что повторно возбужденное исключение будет
// иметь значение severeErr
throw;
}
}
Так как eObj не является ссылкой, то catch-обработчик получает копию объекта-исключения, так что любые модификации eObj относятся к локальной копии и не отражаются на исходном объекте-исключении, передаваемом при повторном возбуждении. Таким образом, переданный далее объект по-прежнему имеет тип zeroOp.
Чтобы модифицировать исходный объект-исключение, в объявлении исключения внутри catch-обработчика должна фигурировать ссылка:
catch ( EHstate &eObj ) {
// модифицируем объект-исключение
eObj = severeErr;
// повторно возбужденное исключение имеет значение severeErr
throw;
}
Теперь eObj ссылается на объект-исключение, созданный выражением throw, так что все изменения относятся непосредственно к исходному объекту. Поэтому при повторном возбуждении исключения далее передается модифицированный объект.
Таким образом, другая причина для объявления ссылки в catch-обработчике заключается в том, что сделанные внутри обработчика модификации объекта-исключения в таком случае будут видны при повторном возбуждении исключения. (Третья причина будет рассмотрена в разделе 19.2, где мы расскажем, как catch-обработчик вызывает виртуальные функции класса.)
для начинающих” произошло довольно много
Между выходом второго и третьего издания “С++ для начинающих” произошло довольно много событий. Одним из самых значительных стало появление международного стандарта. Он не только добавил в язык С++ новые возможности, среди которых обработка исключений, идентификация типов во время выполнения, пространство имен, встроенный булевский тип данных, новый синтаксис приведения типов, но также существенно изменил и расширил имеющиеся – шаблоны, механизм классов, поддерживающий объектную и объектно-ориентированную парадигму программирования, вложенные типы и разрешение перегруженных функций. Еще более важным событием стало включение в состав стандарта С++ обширной библиотеки, содержащей, в частности, то, что ранее называлось Standard Template Library (STL). В эту стандартную библиотеку входят новый тип string, последовательные и ассоциативные контейнеры, такие, как vector, list, map, set, и обширный набор обобщенных алгоритмов, которые могут применяться ко всем этим типам данных. Появилось не просто много нового материала, нуждающегося в описании, но фактически изменился сам способ мышления при программировании на С++. Короче говоря, можно считать, что С++ изобретен заново, поэтому третье издание нашей книги “C++ для начинающих” полностью переработано.
В третьем издании не только коренным образом поменялся наш подход к С++, изменились и авторы. Прежде всего, авторский коллектив удвоился и стал интернациональным, хотя корни его по-прежнему на североамериканском континенте: Стен (Stan) американец, а Жози (Josйe) канадка. Двойное авторство отражает деление сообщества программистов С++ на две части: Стен в настоящее время занимается разработкой приложений на C++ в области трехмерной графики и анимации для Walt Disney Feature Animation, а Жози принимает участие в развитии самого языка С++, являясь председателем рабочей группы по ядру языка в комитете по стандартизации и одним из разработчиков компилятора С++ в IBM Canada Laboratory.
Стен работает над С++ с 1984 года. Он был одним из членов первоначальной команды, трудившейся в Bell Laboratories под руководством Бьерна Страуструпа (Bjarne Stroustrup), изобретателя языка. Стен принимал участие в разработке cfront, оригинальной реализации С, с версии 1.1 в 1986 году до версии 3.0, и возглавлял проект при работе над версиями 2.1 и 3.0. После этого он работал под началом Страуструпа над проектом, посвященным исследованиям объектной модели программной среды разработки на C++.
Жози – член команды, работающей над компилятором С++ в IBM Canada Laboratory на протяжении восьми лет. С 1990 года она входит в состав комитета по стандартизации. Три года она была вице-президентом комитета и четыре года – председателем рабочей группы по ядру языка.
Третье издание “C++ для начинающих” существенно переработано, что отражает не только развитие и расширение языка, но и изменения во взглядах и опыте авторов книги.
Предметный указатель
[1] Во время написания этой книги не все компиляторы С++ поддерживали пространства имен. Если ваш компилятор таков, откажитесь от данной директивы. Большинство программ, приводимых нами, используют компиляторы, не поддерживающие пространство имен, поэтому директива using в них отсутствует.
[2] Как было сказано ранее, не все компиляторы поддерживают пространства имен, поэтому эта разница проявляется только для последних версий компиляторов.
[3] Объявление функции inline – это всего лишь подсказка компилятору. Однако компилятор не всегда может сделать функцию встроенной, существуют некоторые ограничения. Подробнее об этом сказано в разделе 7.6.
[4] Вот как выглядит общее решение этой проблемы:
Example2( elemType nval = elemType() ) " _val( nval ) {}
[5] На самом деле для указателей на функции это не совсем так: они отличаются от указателей на данные (см. раздел 7.9).
[6] STL расшифровывается как Standard Template Library. До появления стандартной библиотеки С++ классы vector, string и другие, а также обобщенные алгоритмы входили в отдельную библиотеку с названием STL.
[7] Проверку на неравенство 0 можно опустить. Полностью эквивалентна приведенной и более употребима следующая запись: ptr && *ptr.
[8] До принятия стандарта языка С++ видимость объектов, определенных внутри круглых скобок for, простиралась на весь блок или функцию, содержащую данную инструкцию. Например, употребление двух циклов for внутри одного блока
{
// верно для стандарта С++
// в предыдущих версиях C++ - ошибка: ival определена дважды
for (int ival = 0; ival < size; ++iva1 ) // ...
for (int ival = size-1; ival > 0; ival ) // ...
}
в ранних версиях языка вызывало ошибку: ival определена дважды. В стандарте С++ данный текст синтаксически правилен, так как каждый экземпляр ival является локальным для своего блока.
[9] Замечание. Для упрощения программы мы требуем, чтобы каждое слово было отделено пробелом от скобок и логических операторов. Таким образом, запросы вида
(War || Rights)
Civil&&(War||Rights)
не будут поняты нашей системой. Хотя удобство пользователей не должно приноситься в жертву простоте реализации, мы считаем, что в данном случае можно смириться с таким ограничением.
[10] Иллюстрация Елены Дрискилл (Elena Driskill).
[11] Отметим, что deque не поддерживает операцию reserve()
[12] Существующие на сегодняшний день реализации не поддерживают шаблоны с параметрами по умолчанию. Второй параметр – allocator – инкапсулирует способы выделения и освобождения памяти. В С++ он имеет значение по умолчанию, и его задавать не обязательно. Стандартная реализация использует операторы new и delete. Применение распределителя памяти преследует две цели: упростить реализацию контейнеров путем отделения всех деталей, касающихся работы с памятью, и позволить программисту при желании реализовать собственную стратегию выделения памяти. Определения объектов для компилятора, не поддерживающего значения по умолчанию параметров шаблонов, выглядят следующим образом:
vector< string, allocator > svec;
list< int, allocator > ilist;
[13] Если функция-член push_front() используется часто, следует применять тип deque, а не vector: в deque эта операция реализована наиболее эффективно.
[14] Последняя форма insert() требует, чтобы компилятор работал с шаблонами функций-членов. Если ваш компилятор еще не поддерживает это свойство стандарта С++, то оба контейнера должны быть одного типа, например два списка или два вектора, содержащих элементы одного типа.
[15] Программа компилировалась компилятором, не поддерживающим значений параметров по умолчанию шаблонов. Поэтому нам пришлось явно указать аллокатор:
vector<string,allocator> *lines_of_text;
Для компилятора, полностью соответствующего стандарту С++, достаточно отметить тип элементов:
vector<string> *lines_of_text;
[16] Конечно, в английском языке существуют исключения из правил. Наш эвристический алгоритм превратит crises (множ. число от crisis – прим. перев.) в cris. Ошибочка!
[17] Таким образом, как мы видим, определения встроенных функций могут встретиться в программе несколько раз! – Прим. ред.
[18] Полный текст реализации класса CommandOpt можно найти на Web-сайте издательства Addison-Wesley.
1. Если имеющийся у Вас компилятор пока не поддерживает параметр шаблонов по умолчанию, то конструктору istream_iterator необходимо будет явно передать также и второй аргумент: тип difference_type, способный хранить результат вычитания двух итераторов контейнера, куда помещаются элементы. Например, в разделе 12.2 при изучении программы, которая должна транслироваться компилятором, не поддерживающим параметры шаблонов по умолчанию, мы писали:
typedef vector<string,allocator>::difference_type diff_type
istream_iterator< string, diff_type > input_set1( infile1 ), eos;
istream_iterator< string, diff_type > input_set2( infile2 );
Если бы компилятор полностью удовлетворял стандарту C++, достаточно было бы написать так:
istream_iterator< string > input_set1( infile1 ), eos;
istream_iterator< string > input_set2( infile2 );
1 Более подробное обсуждение этой темы с примерами и приблизительными оценками производительности см. в [LIPPMAN96a].
2 В реальной программе мы объявили бы член _name как имеющий тип string. Здесь он объявлен как C-строка, чтобы отложить рассмотрение вопроса об инициализации членов класса до раздела 14.4.
3 Для тех, кто раньше программировал на C: приведенное выше определение класса Account на C выглядело бы так:
typedef struct {
char *_name;
unsigned int _acct_nmbr;
double _balance;
} Account;
4 См. статью Джерри Шварца в [LIPPMAN96b], где приводится дискуссия по этому поводу и описывается решение, остающееся пока наиболее распространенным.
5 Сигнатура ассоциированного конструктора имеет следующий смысл. Копирующий конструктор применяет некоторое значение к каждому элементу по очереди. Задавая в качестве второго аргумента объект класса, мы делаем создание временного объекта излишним:
explicit vector( size_type n, const T& value=T(), const Allocator&=Allocator());
1 Напомним, что для упрощения реализации необходимо, чтобы между любыми двумя словами, включая скобки и операторы запроса, был пробел. В реальной системе такое требование вряд ли разумно, но мы полагаем, что для вводного курсе, каковым является наша книга, это вполне приемлемо.
2 В объявлении унаследованной виртуальной функции, например eval(), в производном классе ключевое слово virtual необязательно. Компилятор делает правильное заключение на основе сравнения с прототипом функции.
3 Увы! Правые скобки не распознаются, пока OrQuery не выведет все ассоциированное с ним частичное решение.
[19]
Полный текст программы можно найти на FTP-сайте издательства Addison-Wesley по адресу, указанному на задней стороне обложки.
1 Здесь есть потенциальная опасность появления висячей ссылки, если пользователь сохранит адрес какого-либо элемента исходного массива перед тем, как grow() скопирует массив в новую область памяти. См. статью Тома Каргилла в [LIPPMAN96b].
1 Кроме того, программист может устанавливать и сбрасывать флаги состояния формата с помощью функций-членов setf() и unsetf(). Мы их рассматривать не будем; исчерпывающие ответы на вопросы, относящиеся к этой теме, можно получить в [STROUSTRUP97].
Предопределенные объекты-функции
Предопределенные объекты-функции подразделяются на арифметические, логические и сравнительные. Каждый объект– это шаблон класса, параметризованный типами операндов. Для использования любого из них необходимо включить заголовочный файл:
#include <functional>
Например, объект-функция, поддерживающий сложение, – это шаблон класса с именем plus. Для определения экземпляра, способного складывать два целых числа, нужно написать:
#include <functional>
plus< int > intAdd;
Для выполнения операции сложения мы применяем перегруженный оператор вызова к intAdd точно так же, как и к классу AddImage в предыдущем разделе:
int ival1 = 10, ival2 = 20;
// эквивалентно int sum = ival1 + ival2;
int sum = intAdd( ival1, ival2 );
Реализация шаблона класса plus вызывает оператор сложения, ассоциированный с типом своего параметра – int. Этот и другие предопределенные объекты-функции применяются прежде всего в качестве аргументов обобщенных алгоритмов и обычно замещают подразумеваемую по умолчанию операцию. Например, по умолчанию алгоритм sort() располагает элементы контейнера в порядке возрастания с помощью оператора “меньше” базового типа. Для сортировки по убыванию мы передаем предопределенный шаблон класса greater, который вызывает оператор “больше”:
vector< string > svec;
// ...
sort( svec.begin(), svec.end(), greater<string>() );
Предопределенные объекты-функции перечислены в следующих разделах и разбиты на категории: арифметические, логические и сравнительные. Применение каждого из них иллюстрируется как в качестве именованного, так и в качестве безымянного объекта, передаваемого функции. Мы пользуемся следующими определениями объектов, включая и определение простого класса (перегрузка операторов подробно рассматривается в главе 15):
class Int {
public:
Int( int ival = 0 ) : _val( ival ) {}
int operator-() { return -_val; }
int operator%(int ival) { return -_val % ival; }
bool operator<(int ival) { return -_val < ival; }
bool operator!() { return -_val == 0; }
private:
int _val;
};
vector< string > svec;
string sval1, sval2, sres;
complex cval1, cval2, cres;
int ival1, ival2, ires;
Int Ival1, Ival2, Ires;
double dval1, dval2, dres;
Кроме того, мы определяем два шаблона функций, которым передаем различные безымянные объекты-функции:
template <class FuncObject, class Type>
Type UnaryFunc( FuncObject fob, const Type &val )
{ return fob( val ); }
template <class FuncObject, class Type>
Type BinaryFunc( FuncObject fob,
const Type &val1, const Type &val2 )
{ return fob( val1, val2 ); }
Преобразования типов
Представим себе следующий оператор присваивания:
int ival = 0;
// обычно компилируется с предупреждением
ival = 3.541 + 3;
В результате ival получит значение 6. Вот что происходит: мы складываем литералы разных типов– 3.541 типа double и 3 типа int. C++ не может непосредственно сложить подобные операнды, сначала ему нужно привести их к одному типу. Для этого существуют правила преобразования арифметических типов. Общий принцип таков: перейти от операнда меньшего типа к большему, чтобы не потерять точность вычислений.
В нашем случае целое значение 3 трансформируется в тип double, и только после этого производится сложение. Такое преобразование выполняется независимо от желания программиста, поэтому оно получило название неявного преобразования типов.
Результат сложения двух чисел типа double тоже имеет тип double. Значение равно 6.541. Теперь его нужно присвоить переменной ival. Типы переменной и результата 6.541 не совпадают, следовательно, тип этого значения приводится к типу переменной слева от знака равенства. В нашем случае это int. Преобразование double в int производится автоматически, отбрасыванием дробной части (а не округлением). Таким образом, 6.541 превращается в 6, и этот результат присваивается переменной ival. Поскольку при таком преобразовании может быть потеряна точность, большинство компиляторов выдают предупреждение.
Так как компилятор не округляет числа при преобразовании double в int, при необходимости мы должны позаботиться об этом сами. Например:
double dva1 = 8.6;
int iva1 = 5;
ival += dva1 + 0.5; // преобразование с округлением
При желании мы можем произвести явное преобразование типов:
// инструкция компилятору привести double к int
ival = static_cast< int >( 3.541 ) + 3;
В этом примере мы явно даем указание компилятору привести величину 3.541 к типу int, а не следовать правилам по умолчанию.
В этом разделе мы детально обсудим вопросы и неявного (как в первом примере), и явного преобразования типов (как во втором).
Преобразования типов аргументов *
На втором шаге процесса разрешения перегрузки функции компилятор идентифицирует и ранжирует преобразования, которые следует применить к каждому фактическому аргументу вызванной функции для приведения его к типу соответствующего формального параметра любой из устоявших функций. Ранжирование может дать один из трех возможных результатов:
точное соответствие. Тип фактического аргумента точно соответствует типу формального параметра. Например, если в множестве перегруженных функций print() есть такие:
void print( unsigned int );
void print( const char* );
void print( char );
то каждый из следующих трех вызовов дает точное соответствие:
unsigned int a;
print( 'a' ); // соответствует print( char );
print( "a" ); // соответствует print( const char* );
print( a ); // соответствует print( unsigned int );
соответствие с
преобразованием типа. Тип фактического аргумента не соответствует типу формального параметра, но может быть преобразован в него:
void ff( char );
ff( 0 ); // аргумент типа int приводится к типу char
отсутствие соответствия. Тип фактического аргумента не может быть приведен к типу формального параметра в объявлении функции, поскольку необходимого преобразования не существует. Для каждого из следующих двух вызовов функции print() соответствия нет:
// функции print() объявлены так же, как и выше
int *ip;
class SmallInt { /* ... */ };
SmallInt si;
print( ip ); // ошибка: нет соответствия
print( si ); // ошибка: нет соответствия
Для установления точного соответствия тип фактического аргумента необязательно должен совпадать с типом формального параметра. К аргументу могут быть применены некоторые тривиальные преобразования, а именно:
преобразование l-значения в r-значение;
преобразование массива в указатель;
преобразование функции в указатель;
преобразования спецификаторов.
(Подробнее они рассмотрены ниже.)
Категория соответствия с преобразованием типа является наиболее сложной. Необходимо рассмотреть несколько видов такого приведения: расширение типов
(promotions), стандартные преобразования и определенные пользователем преобразования. (Расширения типов и стандартные преобразования изучаются в этой главе. Определенные пользователем преобразования будут представлены позднее, после детального рассмотрения классов; они выполняются конвертером, функцией-членом, которая позволяет определить в классе собственный набор “стандартных” трансформаций. В главе 15 мы познакомимся с такими конвертерами и с тем, как они влияют на разрешение перегрузки функций.)
При выборе лучшей из устоявших функций для данного вызова компилятор ищет функцию, для которой применяемые к фактическим аргументам преобразования являются “наилучшими”. Преобразования типов ранжируются следующим образом: точное соответствие лучше расширения типа, расширение типа лучше стандартного преобразования, а оно, в свою очередь, лучше определенного пользователем преобразования. Мы еще вернемся к ранжированию в разделе 9.4, а пока на простых примерах покажем, как оно помогает выбрать наиболее подходящую функцию.
Обобщенные алгоритмы в алфавитном порядке
В этом приложении мы рассмотрим все алгоритмы. Мы решили расположить их в алфавитном порядке (за небольшими исключениями), чтобы проще было найти нужный. Каждый алгоритм представлен в следующем виде: сначала описывается прототип функции, затем сам алгоритм, причем особое внимание уделяется интуитивно неочевидным особенностям, и, наконец, приводится пример программы, показывающий, как можно данный алгоритм использовать.
Первыми двумя аргументами всех обобщенных алгоритмов (естественно, не без исключений) является пара итераторов, обычно first и last, обозначающих диапазон элементов внутри контейнера или встроенного массива, над которым работает алгоритм. Этот диапазон (часто называемый интервалом с включенной левой границей), как правило, записывается в виде:
// следует читать: включая first и все последующие
// элементы до last, но не включая сам last
[ first, last )
Это означает, что диапазон начинается с first и заканчивается last, однако сам элемент last не включается. Если
first == last
то говорят, что диапазон пуст.
К паре итераторов предъявляется такое требование: last должен быть достижим, если начать с first и последовательно применять оператор инкремента. Однако компилятор не может проверить выполнение данного ограничения. Если требование не будет выполнено, поведение программы не определено; обычно это заканчивается ее крахом и дампом памяти.
В объявлении каждого алгоритма подразумевается минимальная поддержка, которую должны обеспечить итераторы (краткое обсуждение пяти категорий итераторов см. в разделе 12.4). Например, алгоритм find(), реализующий однопроходный обход контейнера и выполняющий только чтение, требует итератора чтения InputIterator. Ему также можно передать одно- или двунаправленный итератор или итератор с произвольным доступом. Однако передача итератора записи приведет к ошибке. Не гарантируется, что подобные ошибки (при передаче итератора неподходящей категории) будут обнаружены компилятором, поскольку категории итераторов– это не сами типы, а лишь параметры, которыми конкретизируется шаблон функции.
Некоторые алгоритмы существуют в нескольких вариантах: в одном используется тот или иной встроенный оператор, а в другом – объект-функция или указатель на функцию, реализующие альтернативу этому оператору. Например, алгоритм unique() по умолчанию сравнивает соседние элементы контейнера с помощью оператора равенства, определенного в классе, к которому данные элементы принадлежат. Но если в этом классе нет оператора равенства или мы хотим сравнивать элементы иным способом, то можем передать объект-функцию или указатель на функцию, поддерживающую нужную семантику. Есть и такие алгоритмы, которые выполняют похожие действия, но имеют различные имена. Так, имена предикатных версий алгоритмов всегда заканчиваются на _if, скажем find_if(). Например, есть вариант алгоритма replace(), где используется встроенный оператор равенства, и вариант с именем replace_if(), которому передается предикатный объект-функция или указатель на функцию-предикат.
Алгоритмы, модифицирующие контейнер, обычно также существуют в двух вариантах: один осуществляет модификацию по месту, а второй возвращает копию с внесенными изменениями. Так, есть алгоритмы replace() и replace_copy(). Однако вариант с копированием (его имя всегда содержит слово _copy) имеется не для каждого алгоритма, модифицирующего контейнер. К примеру, для алгоритмов sort() его нет. В таких случаях, если нужно, чтобы алгоритм работал с копией, мы должны создать ее самостоятельно и передать в качестве аргумента.
Для использования любого обобщенного алгоритма в программу необходимо включить заголовочный файл
#include <algorithm>
Для употребления любого из четырех численных алгоритмов: adjacent_difference(), accumulate(), inner_product() и partial_sum() – нужно включить также файл
#include <numeric>
Приведенные в этом Приложении примеры программ, в которых используются алгоритмы и различные контейнерные типы, отражают существующую на момент написания книги реализацию. Применение библиотеки ввода/вывода iostream следует соглашениям, установленным до принятия стандарта; скажем, в программу включается заголовочный файл iostream.h, а не iostream. Шаблоны не поддерживают аргументы по умолчанию. Чтобы программа работала на системе, имеющейся у вас, возможно, придется изменить некоторые объявления.
Другое, более подробное, чем в этой книге, описание обобщенных алгоритмов можно найти в работе [MUSSER96], правда, оно несколько отстает от окончательного варианта стандартной библиотеки C++.
Применение наследования в C++
При использовании наследования указатель или ссылка на тип базового класса способен адресовать объект любого производного от него класса. Возможность манипулировать такими указателями или ссылками независимо от фактического типа адресуемого объекта называется полиморфизмом. В этой главе мы рассмотрим три функции языка, обеспечивающие специальную поддержку полиморфизма. Сначала мы познакомимся с идентификацией типов во время выполнения (RTTI– Run-time Type Identification), которая позволяет программе узнать истинный производный тип объекта, адресованного ссылкой или указателем на тип базового класса. Затем расскажем о влиянии наследования на обработку исключений: покажем, как можно определять их в виде иерархии классов и как обработчики для типа базового класса могут перехватывать исключения производных типов. В конце главы мы вернемся к правилам разрешения перегрузки функций и посмотрим, как наследование влияет на то, какие преобразования типов можно применять к аргументам функции, и на выбор наилучшей из устоявших.
Пример множественного виртуального наследования *
Мы продемонстрируем определение и использование множественного виртуального наследования, реализовав иерархию шаблонов классов Array (см. раздел 2.4) на основе шаблона Array (см. главу 16), модифицированного так, чтобы он стал конкретным базовым классом. Перед тем как приступать к реализации, поговорим о взаимосвязях между шаблонами классов и наследованием.
Конкретизированный экземпляр такого шаблона может выступать в роли явного базового класса:
class IntStack : private Array<int> {};
Разрешается также произвести его от не шаблонного базового класса:
class Base {};
template <class Type>
class Derived : public Base {};
Шаблон может выступать одновременно в роли базового и производного классов:
template <class Type>
class Array_RC : public virtual Array<Type> {};
В первом примере конкретизированный типом int шаблон Array служит закрытым базовым классом для не шаблонного IntStack. Во втором примере не шаблонный Base служит базовым для любого класса, конкретизированного из шаблона Derived. В третьем примере любой конкретизированный из шаблона Array_RC класс является производным от класса, конкретизированного из шаблона Array. Так, инструкция
Array_RC<int> ia;
конкретизирует экземпляры шаблонов Array и Array_RC.
Кроме того, сам параметр-шаблон может служить базовым классом [MURRAY93]:
template < typename Type >
class Persistent : public Type { ... };
в данном примере определяется производный устойчивый (persistent) подтип для любого конкретизированного типа. Как отмечает Мюррей (Murray), на Type налагается неявное ограничение: он должен быть типом класса. Например, инструкция
Persistent< int > pi; // ошибка
приводит к ошибке компиляции, поскольку встроенный тип не может быть объектом наследования.
Шаблон, выступающий в роли базового класса, должен квалифицироваться полным списком параметров. Если имеется определение:
template <class T> class Base {};
то необходимо писать:
template < class Type >
class Derived : public Base<Type> {};
Такая запись неправильна:
// ошибка: Base - это шаблон,
// так что должны быть заданы его аргументы
template < class Type >
class Derived : public Base {};
В следующем разделе шаблон Array, определенный в главе 16, выступает в роли виртуального базового класса для подтипа Array, контролирующего выход за границы массива; для отсортированного подтипа Array; для подтипа Array, который обладает обоими указанными свойствами. Однако первоначальное определение шаблона класса Array для наследования не подходит:
все его члены и вспомогательные функции объявлены закрытыми, а не защищенными;
ни одна из зависящих от типа функций-членов, скажем оператор взятия индекса, не объявлена виртуальной.
Означает ли это, что наша первоначальная реализация была неправильной? Нет. Она была верной на том уровне понимания, которым мы тогда обладали. При реализации шаблона класса Array мы еще не осознали необходимость специализированных подтипов. Теперь, однако, определение шаблона придется изменить так (реализации функций-членов при этом останутся теми же):
#ifndef ARRAY_H
#define ARRAY_H
#include <iostream>
// необходимо для опережающего объявления operator<<
template <class Type> class Array;
template <class Type> ostream&
operator<<( ostream &, Array<Type> & );
template <class Type>
class Array {
static const int ArraySize = 12;
public:
explicit Array( int sz = ArraySize ) { init( 0, sz ); }
Array( const Type *ar, int sz ) { init( ar, sz ); }
Array( const Array &iA ) { init( iA.ia, iA.size()); }
virtual ~Array() { delete[] ia; }
Array& operator=( const Array & );
int size() const { return _size; }
virtual void grow();
virtual void print( ostream& = cout );
Type at( int ix ) const { return ia[ ix ]; }
virtual Type& operator[]( int ix ) { return ia[ix]; }
virtual void sort( int,int );
virtual int find( Type );
virtual Type min();
virtual Type max();
protected:
void swap( int, int );
void init( const Type*, int );
int _size;
Type *ia;
};
#endif
Одна из проблем, связанных с таким переходом к полиморфизму, заключается в том, что реализация оператора взятия индекса перестала быть встроенной и сводится теперь к значительно более дорогому вызову виртуальной функции. Так, в следующей функции, на какой бы тип она ни ссылалась, было бы достаточно встроенного чтения элемента:
int find( const Array< int > &ia, int value )
{
for ( int ix = 0; ix < ia.size(); ++ix )
// а теперь вызов виртуальной функции
if ( ia[ ix ] == value )
return ix;
return -1;
}
Для повышения производительности мы включили встроенную функцию-член at(),обеспечивающую прямое чтение элемента.
реализация класса Stack
Описывая операции инкремента и декремента, для иллюстрации применения их префиксной и постфиксной формы мы ввели понятие стека. Данная глава завершается примером реализации класса iStack– стека, позволяющего хранить элементы типа int.
Как уже было сказано, с этой структурой возможны две основные операции – поместить элемент (push) и извлечь (pop) его. Другие операции позволяют получить информацию о текущем состоянии стека – пуст он (empty()) или полон (full()), сколько элементов в нем содержится (size()). Для начала наш стек будет предназначен лишь для элементов типа int. Вот объявление нашего класса:
#include <vector>
class iStack {
public:
iStack( int capacity )
: _stack( capacity ), _top( 0 ) {}
bool pop( int &va1ue );
boot push( int value );
bool full();
bool empty();
void display();
int size();
private:
int _top;
vector< int > _stack;
};
В данном случае мы используем вектор фиксированного размера: для иллюстрации использования префиксных и постфиксных операций инкремента и декремента этого достаточно. (В главе 6 мы модифицируем наш стек, придав ему возможность динамически меняться.)
Элементы стека хранятся в векторе _stack. Переменная _top содержит индекс первой свободной ячейки стека. Этот индекс одновременно представляет количество заполненных ячеек. Отсюда реализация функции size(): она должна просто возвращать текущее значение _top.
inline int iStack::size() { return _top; };
empty() возвращает true, если _top равняется 0; full() возвращает true, если _top равен _stack.size()-1 (напомним, что индексация вектора начинается с 0, поэтому мы должны вычесть 1).
inline bool iStack::empty() { return _top ? false : true; }
inline bool iStack::full() {
return _top < _stack.size()-l ? false : true;
}
Вот реализация функций pop() и push(). Мы добавили операторы вывода в каждую из них, чтобы следить за ходом выполнения:
bool iStack::pop( int &top_va1ue ) {
if ( empty() )
return false;
top_value = _stack[ --_top ];
cout << "iStack::pop(): " << top_value << endl;
return true;
}
bool iStack::push( int value ) {
cout << "iStack::push( " << value << " )\n";
if ( full() )
return false;
_stack[ _top++ ] = value;
return true;
}
Прежде чем протестировать наш стек на примере, добавим функцию display(), которая позволит напечатать его содержимое. Для пустого стека она выведет:
( 0 )
Для стека из четырех элементов – 0, 1, 2 и 3 – результатом функции display() будет:
( 4 )( bot: 0 1 2 3 :top )
Вот реализация функции display():
void iStack::display() {
cout << "( " << size() << " )( bot: ";
for ( int ix = 0; ix < _top; ++ix )
cout << _stack[ ix ] << " ";
cout << " :top )\n";
}
А вот небольшая программа для проверки нашего стека. Цикл for выполняется 50 раз. Четное значение (2, 4, 6, 8 и т.д.) помещается в стек. На каждой итерации, кратной 5 (5, 10, 15...), распечатывается текущее содержимое стека. На итерациях, кратных 10 (10, 20, 30...), из стека извлекаются два элемента и его содержимое распечатывается еще раз.
#inc1ude <iostream>
#inc1ude "iStack.h"
int main() {
iStack stack( 32 ) ;
stack.display();
for ( int ix = 1; ix < 51; ++ix )
{
if ( ix%2 == 0 )
stack.push( ix );
if ( ix%5 == 0 )
stack.display();
if ( ix%10 == 0 ) {
int dummy;
stack.pop( dummy ); stack.pop( dummy );
stack.display();
}
}
Вот результат работы программы:
( 0 )( bot: :top )
iStack push( 2 )
iStack push( 4 )
( 2 )( bot: 2 4 :top )
iStack push( 6 )
iStack push( 8 )
iStack push ( 10 )
( 5 )( bot: 2 4 6 8 10 :top )
iStack pop(): 10
iStack pop(): 8
( 3 )( bot: 2 4 6 :top )
iStack push( 12 )
iStack push( 14 )
( 5 )( bot: 2 4 6 12 14 :top )
iStack::push( 16 )
iStack::push( 18 )
iStack::push( 20 )
( 8 )( bot: 2 4 6 12 14 16 18 20 :top )
iStack::pop(): 20
iStack::pop(): 18
( 6 )( bot: 2 4 6 12 14 16 :top )
iStack::push( 22 )
iStack::push( 24 )
( 8 )( bot: 2 4 6 12 14 16 22 24 :top )
iStack::push( 26 )
iStack::push( 28 )
iStack::push( 30 )
( 11 )( bot: 2 4 6 12 14 16 22 24 26 28 30 :top )
iStack::pop(): 30
iStack::pop(): 28
( 9 )( bot: 2 4 6 12 14 16 22 24 26 :top )
iStack::push( 32 )
iStack::push( 34 )
( 11 )( bot: 2 4 6 12 14 16 22 24 26 32 34 :top )
iStack::push( 36 )
iStack::push( 38 )
iStack::push( 40 )
( 14 )( bot: 2 4 6 12 14 16 22 24 26 32 34 36 38 40 :top )
iStack::рор(): 40
iStack::popQ: 38
( 12 )( bot: 2 4 6 12 14 16 22 24 26 32 34 36 :top )
iStack::push( 42 )
iStack::push( 44 )
( 14 )( bot: 2 4 6 12 14 16 22 24 26 32 34 36 42 44 :top )
iStack::push( 46 )
iStack::push( 48 )
iStack::push( 50 )
( 17 )( bot: 2 4 6 12 14 16 22 24 26 32 34 36 42 44 46 48 50 :top )
iStack::pop(): 50
iStack::pop(): 48
( 15 )( bot: 2 4 6 12 14 16 22 24 26 32 34 36 42 44 46 :top )
Упражнение 4.23
Иногда требуется операция peek(), которая возвращает значение элемента на вершине стека без извлечения самого элемента. Реализуйте функцию peek() и добавьте к программе main() проверку работоспособности этой функции.
Упражнение 4.24
В чем вы видите два основных недостатка реализации класса iStack? Как их можно исправить?
Пример шаблона функции
В этом разделе приводится пример, показывающий, как можно определять и использовать шаблоны функций. Здесь определяется шаблон sort(), который затем применяется для сортировки элементов массива. Сам массив представлен шаблоном класса Array (см. раздел 2.5). Таким образом, шаблоном sort() можно пользоваться для сортировки массивов элементов любого типа.
В главе 6 мы видели, что в стандартной библиотеке C++ определен контейнерный тип vector, который ведет себя во многом аналогично типу Array. В главе 12 рассматриваются обобщенные алгоритмы, способные манипулировать контейнерами, описанными в главе 6. Один из таких алгоритмов, sort(), служит для сортировки содержимого вектора. В этом разделе мы определим собственный “обобщенный алгоритм sort()” для манипулирования классом Array, упрощенной версии алгоритма из стандартной библиотеки C++.
Шаблон функции sort() для шаблона класса Array определен следующим образом:
template <class elemType>
void sort( Array<elemType> &array, int low, int high ) {
if ( low < high ) {
int lo = low;
int hi = high + 1;
elemType elem = array[lo];
for (;;) {
while ( min( array[++lo], elem ) != elem && lo < high ) ;
while ( min( array[--hi], elem ) == elem && hi > low ) ;
if (lo < hi)
swap( array, lo, hi );
else break;
}
swap( array, low, hi );
sort( array, low, hi-1 );
sort( array, hi+1, high );
}
}
В sort() используются две вспомогательные функции: min() и swap(). Обе они должны определяться как шаблоны, чтобы иметь возможность обрабатывать любые типы фактических аргументов, с которыми может быть конкретизирован шаблон sort(). min() определена как шаблон функции для поиска минимального из двух значений любого типа:
template <class Type>
Type min( Type a, Type b ) {
return a < b ? a : b;
}
swap() – шаблон функции для перестановки двух элементов массива любого типа:
template <class elemType>
void swap( Array<elemType> &array, int i, int j )
{
elemType tmp = array[ i ];
array[ i ] = array[ j ];
array[ j ] = tmp;
}
Убедиться в том, что функция sort() действительно работает, можно с помощью отображения содержимого массива после сортировки. Поскольку функция display() должна обрабатывать любой массив, конкретизированный из шаблона класса Array, ее тоже следует определить как шаблон:
#include <iostream>
template <class elemType>
void display( Array<elemType> &array )
{ //формат отображения: < 0 1 2 3 4 5 >
cout << "< ";
for ( int ix = 0; ix < array.size(); ++ix )
cout << array[ix] << " ";
cout << ">\n";
}
В этом примере мы пользуемся моделью компиляции с включением и помещаем шаблоны всех функций в заголовочный файл Array.h вслед за объявлением шаблона класса Array.
Следующий шаг – написание функции для тестирования этих шаблонов. В sort() поочередно передаются массивы элементов типа double, типа int и массив строк. Вот текст программы:
#include <iostream>
#include <string>
#include "Array.h"
double da[10] = {
26.7, 5.7, 37.7, 1.7, 61.7, 11.7, 59.7,
15.7, 48.7, 19.7 };
int ia[16] = {
503, 87, 512, 61, 908, 170, 897, 275, 653,
426, 154, 509, 612, 677, 765, 703 };
string sa[11] = {
"a", "heavy", "snow", "was", "falling", "when",
"they", "left", "the", "police", "station" };
int main() {
// вызвать конструктор для инициализации arrd
Array<double> arrd( da, sizeof(da)/sizeof(da[0]) );
// вызвать конструктор для инициализации arri
Array<int> arri( ia, sizeof(ia)/sizeof(ia[0]) );
// вызвать конструктор для инициализации arrs
Array<string> arrs( sa, sizeof(sa)/sizeof(sa[0]) );
cout << "sort array of doubles (size == "
<< arrd.size() << ")" << endl;
sort(arrd, 0, arrd.size()-1 );
display(arrd);
cout << "sort array of ints (size == "
<< arri.size() << ")" << endl;
sort(arri, 0, arri.size()-1 );
display(arri);
cout << "sort array of strings (size == "
<< arrs.size() << ")" << endl;
sort(arrs, 0, arrs.size()-1 );
display(arrs);
return 0;
}
Если скомпилировать и запустить программу, то она напечатает следующее (эти строки искусственно разбиты на небольшие части):
sort array of doubles (size == 10)
< 1.7 5.7 11.7 14.9 15.7 19.7 26.7
37.7 48.7 59.7 61.7 >
sort array of ints (size == 16)
< 61 87 154 170 275 426 503 509 512
612 653 677 703 765 897 908 >
sort array of strings (size == 11)
< "a" "falling" "heavy" "left" "police" "snow"
"station" "the" "they" "was" "when" >
В числе обобщенных алгоритмов, имеющихся в стандартной библиотеке C++ (и в главе 12), вы найдете также функции min() и swap(). В главе 12 мы покажем, как их использовать.
Пример связанного списка
Мы завершали главы 3 и 4 примерами для введения читателя в механизм классов С++. В конце этого раздела мы покажем, как разработать класс, представляющий собой односвязный список. (В главе 6 мы рассмотрим двусвязный список, являющийся частью стандартной библиотеки.) Если вы в первый раз читаете эту книгу, то можете пропустить данный раздел и вернуться к нему после чтения главы 13. (Для усвоения этого материала нужно представлять себе механизм классов С++, конструкторы, деструкторы и т.д. Если вы плохо знаете классы, но все же хотите продолжить чтение данного раздела, мы рекомендуем прочесть пункты 2.3 и 3.15.
Список представляет собой последовательность элементов, каждый из которых содержит значение некоторого типа и адрес следующего элемента (причем для последнего из них адрес может быть нулевым). К любой такой последовательности всегда можно добавить еще один элемент (хотя реальная попытка подобного добавления может закончиться неудачно, если отведенная программе свободная память исчерпана). Список, в котором нет ни одного элемента, называется пустым.
Какие операции должен поддерживать список? Добавление (insert), удаление (remove) и поиск (find) определенных элементов. Кроме того, можно запрашивать размер списка (size), распечатывать его содержимое (display), проверять равенство двух списков. Мы покажем также, как инвертировать (reverse) и сцеплять (concatenate) списки.
Простейшая реализация операции size() перебирает все элементы, подсчитывая их количество. Более сложная реализация сохраняет размер как член данных; она намного эффективнее, однако требует некоторого усложнения операций insert() и remove() для поддержки размера в актуальном состоянии.
Мы выбрали второй вариант реализации функции size() и храним размер списка в члене данных. Мы предполагаем, что пользователи будут достаточно часто применять эту операцию, поэтому ее необходимо реализовать как можно более эффективно.
(Одним из преимуществ отделения открытого интерфейса от скрытой реализации является то, что если наше предположение окажется неверным, мы сможем переписать реализацию, сохранив открытый интерфейс – в данном случае тип возвращаемого значения и набор параметров функции size() – и программы, использующие эту функцию, не нужно будет модифицировать.)
Операция insert() в общем случае принимает два параметра: указатель на один из элементов списка и новое значение, которое вставляется после указанного элемента. Например, для списка
1 1 2 3 8
вызов
mylist.insert (pointer_to_3, 5);
изменит наш список так:
1 1 2 3 5 8
Чтобы обеспечить подобную возможность, нам необходимо дать пользователю способ получения адреса определенного элемента. Одним из способов может быть использование функции find() – нахождение элемента с определенным значением:
pointer_to_3 = mylist.find( 3 );
find() принимает в качестве параметра значение из списка. Если элемент с таким значением найден, то возвращается его адрес, иначе find() возвращает 0.
Может быть два специальных случая вставки элемента: в начало и в конец списка. Для этого требуется только задание значения:
insert_front( value );
1nsert_end( value );
Предусмотрим следующие операции удаления элемента с заданным значением, первого элемента и всех элементов списка:
remove( value );
remove_front();
remove_all();
Функция display() распечатывает размер списка и все его элементы. Пустой список можно представить в виде:
(0)( )
а список из семи элементов как:
(7) ( 0 1 1 2 3 5 8 )
reverse() меняет порядок элементов на противоположный. После вызова
mylist.reverse();
предыдущий список выглядит таким образом:
(7) ( 8 5 3 2 1 1 0 )
Конкатенация добавляет элементы второго списка в конец первого. Например, для двух списков:
(4)( 0 1 1 2 ) // listl
(4)( 2 3 5 8 ) // list2
операция
listl.concat( list2 );
превращает list1 в
(8) ( 0 1 1 2 2 3 5 8 )
Чтобы сделать из этого списка последовательность чисел Фибоначчи, мы можем воспользоваться функцией remove():
listl.remove( 2 );
Мы определили поведение нашего списка, теперь можно приступать к реализации. Пусть список (list) и элемент списка (list_item) будут представлены двумя разными классами. (Ограничимся теми элементами, которые способны хранить только целые значения. Отсюда названия наших классов – ilist и ilist_item.)
Наш список содержит следующие члены: _at_front – адрес первого элемента, _at_end – адрес последнего элемента и _size – количество элементов. При определении объекта типа ilist все три члена должны быть инициализированы 0. Это обеспечивается конструктором по умолчанию:
class ilist_item;
class ilist {
public:
// конструктор по умолчанию
ilist() : _at_front( 0 ),
_at_end( 0 ), _size( 0 ) {}
// ...
private:
ilist_item *_at_front;
ilist_item *_at_end;
int _size;
};
Теперь мы можем определять объекты типа ilist, например:
ilist mylist;
но пока ничего больше. Добавим возможность запрашивать размер списка. Включим объявление функции size() в открытый интерфейс списка и определим эту функцию так:
inline int ilist::size() { return _size; }
Теперь мы можем использовать:
int size = mylist.size();
Пока не будем позволять присваивать один список другому и инициализировать один список другим (впоследствии мы реализуем и это, причем такие изменения не потребуют модификации пользовательских программ). Объявим копирующий конструктор и копирующий оператор присваивания в закрытой части определения списка без их реализации. Теперь определение класса ilist выглядит таким образом:
class ilist {
public:
// определения не показаны
ilist();
int size();
// ...
private:
// запрещаем инициализацию
// и присваивание одного списка другому
ilist( const ilist& );
ilist& operator=( const ilist& );
// данные-члены без изменения
};
Обе строки следующей программы вызовут ошибки компиляции, потому что функция main() не может обращаться к закрытым членам класса ilist:
int main()
{
ilist yourlist( mylist ); // ошибка
mylist = mylist; // ошибка
}
Следующий шаг – вставка элемента, для представления которого мы выбрали отдельный класс:
class ilist_item {
public:
// ...
private:
int _value;
ilist_item *_next;
};
Член _value хранит значение, а _next – адрес следующего элемента или 0.
Конструктор ilist_item требует задания значения и необязательного параметра – адреса существующего объекта ilist_item. Если этот адрес задан, то создаваемый объект ilist_item будет помещен в список после указанного. Например, для списка
0 1 1 2 5
вызов конструктора
ilist_item ( 3, pointer_to_2 );
модифицирует последовательность так:
0 1 1 2 3 5
Вот реализация ilist_item. (Напомним, что второй параметр конструктора является необязательным. Если пользователь не задал второй аргумент при вызове конструктора, по умолчанию употребляется 0. Значение по умолчанию указывается в объявлении функции, а не в ее определении; это поясняется в главе 7.)
class ilist_item {
public:
ilist_item( int value, ilist_-item *item_to_link_to = 0 );
// ...
};
inline
ilist_item::
ilist_item( int value, ilist_item *item )
: _value( value )
{
if ( item )
_next = 0;
else {
_next = item->_next;
item->_next = this;
}
Операция insert() в общем случае работает с двумя параметрами – значением и адресом элемента, после которого производится вставка. Наш первый вариант реализации имеет два недочета. Сможете ли вы их найти?
inline void
ilist::
insert( ilist_item *ptr, int value )
{
new ilist_item( value, ptr );
++_size;
}
Одна из проблем заключается в том, что указатель не проверяется на нулевое значение. Мы обязаны распознать и обработать такую ситуацию, иначе это приведет к краху программы во время исполнения. Как реагировать на нулевой указатель? Можно аварийно закончить выполнение, вызвав стандартную функцию abort(), объявленную в заголовочном файле cstdlib:
#include <cstdlib>
// ...
if ( ! ptr )
abort();
Кроме того, можно использовать макрос assert(). Это также приведет к аварийному завершению, но с выводом диагностического сообщения:
#include <cassert>
// ...
assert( ptr != 0 );
Третья возможность – возбудить исключение:
if ( ! ptr )
throw "Panic: ilist::insert(): ptr == O";
В общем случае желательно избегать аварийного завершения программы: в такой ситуации мы заставляем пользователя беспомощно сидеть и ждать, пока служба поддержки обнаружит и исправит ошибку.
Если мы не можем продолжать выполнение там, где обнаружена ошибка, лучшим решением будет возбуждение исключения: оно передает управление вызвавшей программе в надежде, что та сумеет выйти из положения.
Мы же поступим совсем другим способом: рассмотрим передачу нулевого указателя как запрос на вставку элемента перед первым в списке:
if ( ! ptr )
insert_front( value );
Второй изъян в нашей версии можно назвать философским. Мы реализовали size() и _size как пробный вариант, который может впоследствии измениться. Если мы преобразуем функции size() таким образом, что она будет просто пересчитывать элементы списка, член _size перестанет быть нужным. Написав:
++_size;
мы тесно связали реализацию insert() с текущей конструкцией алгоритма пересчета элементов списка. Если мы изменим алгоритм, нам придется переписывать эту функцию, как и insert_front(), insert_end() и все операции удаления из списка. Вместо того чтобы распространять детали текущей реализации на разные функции класса, лучше инкапсулировать их в паре:
inline void ilist::bump_up_size() { ++_size; }
inline void ilist::bump_down_size() { --_size; }
Поскольку мы объявили эти функции встроенными, эффективность не пострадала. Вот окончательный вариант insert():
inline void
ilist::
insert( ilist_item *ptr, int value )
if ( !ptr )
insert_front( value );
else {
bump_up_size();
new ilist_item( value, ptr );
}
}
Реализация функций insert_front() и insert_end() достаточно очевидна. В каждой из них мы должны предусмотреть случай, когда список пуст.
inline void
ilist::
insert_front( int value )
{
ilist_item *ptr = new ilist_item( value );
if ( !_at_front )
_at_front = _at_end = ptr;
else {
ptr->next( _at_front );
_at_front = ptr;
}
bump_up_size();
}
inl-ine void
ilist::
insert_end( int value )
{
if ( !_at_end )
_at_end = _at_front = new ilist_item( value );
else _at_end = new ilist_item( value, _at_end );
bump_up_s-ize();
}
find() ищет значение в списке. Если элемент с указанным значением найден, возвращается его адрес, иначе find() возвращает 0. Реализация find()выглядит так:
ilist_item*
ilist::
find( int value )
{
ilist_item *ptr = _at_front;
while ( ptr )
{
if ( ptr->value() == value )
break;
ptr = ptr->next();
}
return ptr;
}
Функцию find() можно использовать следующим образом:
ilist_item *ptr = mylist.find( 8 );
mylist.insert( ptr, some_value );
или в более компактной записи:
mylist.insert( mylist.find( 8 ), some_value );
Перед тем как тестировать операции вставки элементов, нам нужно написать функцию display(), которая поможет нам при отладке. Алгоритм display() достаточно прост: печатаем все элементы, с первого до последнего. Можете ли вы сказать, где в данной реализации ошибка?
// не работает правильно!
for ( ilist_item *iter = _at_front; // начнем с первого
iter != _at_end; // пока не последний
++iter ) // возьмем следующий
cout << iter->value() << ' ';
// теперь напечатаем последний
cout << iter->value();
Список – это не массив, его элементы не занимают непрерывную область памяти. Инкремент итератора
++iter;
вовсе не сдвигает его на следующий элемент списка. Вместо этого он указывает на место в памяти, непосредственно следующее за данным элементом, а там может быть все что угодно. Для изменения значения итератора нужно воспользоваться членом _next объекта ilist_item:
iter = iter->_next;
Мы инкапсулировали доступ к членам ilist_item набором встраиваемых функций. Определение класса ilist_item теперь выглядит так:
class ilist_item {
public:
ilist_item( int value, ilist_item *item_to_link_to = 0 );
int value() { return _value; }
iilst_item* next() { return _next; }
void next( ilist_item *link ) { _next = link; }
void value( int new_value ) { _value = new_value; }
private:
int _value;
ilist_item *_next;
};
Вот определение функции display(), использующее последнюю реализацию класса ilist_item:
#include <iostream>
class ilist {
public:
void display( ostream &os = cout );
// ...
};
void ilist::
display( ostream &os )
{
os << "\n( " << _size << " )( ";
ilist_item *ptr = _at_front;
while ( ptr ) {
os << ptr->value() << " ";
ptr = ptr->next();
}
os << ")\n";
}
Тестовую программу для нашего класса ilist в его текущей реализации можно представить таким образом:
#include <iostream>
#include "ilist.h"
int main()
{
ilist mylist;
for ( int ix = 0; ix < 10; ++ix ) {
mylist.insert_front( ix );
mylist.insert_end( ix );
}
cout <<
"Ok: после insert_front() и insert_end()\n";
mylist.display();
ilist_item *it = mylist.find( 8 );
cout << "\n"
<< "Ищем значение 8: нашли?"
<< ( it ? " да!\n" : " нет!\n" );
mylist.insert( it, 1024 );
cout << "\n" <<
"Вставка элемента 1024 после 8\n";
mylist.display();
int elem_cnt = mylist.remove( 8 );
cout << "\n"
<< "Удалено " << elem_cnt
<< " элемент(ов) со значением 8\n";
mylist.display();
cout << "\n" << "Удален первый элемент\n";
mylist.remove_front(); mylist.display();
cout << "\n" << "Удалены все элементы\n";
mylist.remove_all(); mylist.display();
}
Результат работы программы:
Ok: после insert_front() и insert_end()
(20)( 9 8 7 6 5 4 3 2 1 0 0 1 2 3 4 5 6 7 8 9 )
Ищем значение 8: нашли? да!
Вставка элемента 1024 после 8
( 21 )( 9 8 1024 7 6 5 4 3 2 1 0 0 1 2 3 4 5 6 7 8 9 )
Удалено 2 элемент(ов) со значением 8
( 19 )( 9 1024 7 6 5 4 3 2 1 0 0 1 2 3 4 5 6 7 9 )
Удален первый элемент
( 18 )( 1024 7 6 5 4 3 2 1 0 0 1 2 3 4 5 6 7 9 )
Удалены все элементы
( 0 )( )
Помимо вставки элементов, необходима возможность их удаления. Мы реализуем три таких операции:
void remove_front();
void remove_all ();
int remove( int value );
Вот как выглядит реализация remove_front():
inline void
i1ist::
remove_front()
{
if ( _at_front ) {
ilist_item *ptr = _at_front;
_at_front = _at_front->next();
bump_down_size() ;
delete ptr;
}
}
remove_all() вызывает remove_front() до тех пор, пока все элементы не будут удалены:
void ilist::
remove_all()
{
while ( _at_front )
remove_front();
_size = 0;
_at_front = _at_end = 0;
}
Общая функция remove() также использует remove_front() для обработки специального случая, когда удаляемый элемент (элементы) находится в начале списка. Для удаления из середины списка используется итерация. У элемента, предшествующего удаляемому, необходимо модифицировать указатель _next. Вот реализация функции:
int ilist::
remove( int value )
{
ilist_item *plist = _at_front;
int elem_cnt = 0;
while ( plist && plist->value() == value )
{
plist = plist->next();
remove_front();
++elem_cnt;
}
if ( ! plist )
return elem_cnt;
ilist_item *prev = plist;
plist = plist->next();
while ( plist ) {
if ( plist->value() == value ) {
prev->next( plist->next() );
delete plist;
++elem_cnt;
bump_down_size();
plist = prev->next();
if ( ! plist ) {
_at_end = prev;
return elem_cnt;
}
}
else {
prev = plist;
plist = plist->next();
}
return elem_cnt;
}
Следующая программа проверяет работу операций в четырех случаях: когда удаляемые элементы расположены в конце списка, удаляются все элементы, таких элементов нет или они находятся и в начале, и в конце списка.
#include <iostream>
#include "ilist.h"
int main()
{
ilist mylist;
cout << "\n-----------------------------------------------\n"
<< "тест #1: - элементы в конце\n"
<< "-----------------------------------------------\n";
mylist.insert_front( 1 ); mylist.insert_front( 1 );
mylist.insert_front( 1 );
my1ist.insert_front( 2 ); mylist.insert_front( 3 );
my1ist.insert_front( 4 );
mylist.display();
int elem_cnt = mylist.remove( 1 );
cout << "\n" << "Удалено " << elem_cnt
<< " элемент(ов) со значением 1\n";
mylist.display();
mylist.remove_all();
cout << "\n-----------------------------------------------\n"
<< "тест #2: - элементы в начале\n"
<< "-----------------------------------------------\n";
mylist.insert_front( 1 ); mylist.insert_front( 1 );
mylist.insert_front( 1 );
mylist.display();
elem_cnt = mylist.remove( 1 );
cout << "\n" << "Удалено " << elem_cnt
<< " элемент(ов) со значением 1\n";
mylist.display();
mylist.remove_all () ;
cout << "\n-----------------------------------------------\n"
<< "тест #3: - элементов нет в списке\n"
<< "-----------------------------------------------\n";
mylist.insert_front( 0 ); mylist.insert_front( 2 );
mylist.insert_front( 4 );
mylist.display();
elem_cnt = mylist.remove( 1 );
cout << "\n" << "Удалено " << elem_cnt
<< " элемент(ов) со значением 1\n";
mylist.display();
mylist.remove_all () ;
cout << "\n-----------------------------------------------\n"
<< "тест #4: - элементы в конце и в начале\n"
<< "-----------------------------------------------\n";
my1ist.insert_front( 1 ); mylist.insert_front( 1 );
my1ist.insert_front( 1 );
my1ist.insert_front( 0 ); mylist.insert_front( 2 );
my1ist.insert_front( 4 );
mylist.insert_front( 1 ); my1ist.insert_front( 1 );
mylist.insert_front( 1 );
mylist.display() ;
elem_cnt = mylist.remove( 1 );
cout << "\n" << "Удалено " << elem_cnt
<< " элемент(ов) со значением 1\n";
mylist.display();
}
Результат работы программы:
-----------------------------------------------
тест #1: - элементы в конце
-----------------------------------------------
( 6 )( 4 3 2 1 1 1 )
Удалено 3 элемент(ов) со значением 1
( 3 )( 4 3 2 )
-----------------------------------------------
тест #2: - элементы в начале
-----------------------------------------------
( 3 )( 1 1 1 )
Удалено 3 элемент(ов) со значением 1
( 0 )( )
-----------------------------------------------
тест #3: - элементов нет в списке
-----------------------------------------------
( 3 )( 4 2 0 )
Удалено 0 элемент(ов) со значением 1
( 3 )( 4 2 0 )
-----------------------------------------------
тест #4: - элементы в конце и в начале
-----------------------------------------------
(9 )( 1 1 1 4 2 0 1 1 1 )
Удалено 6 элемент(ов) со значением 1
( 3 )( 4 2 0 )
Последние две операции, которые мы хотим реализовать, – конкатенация двух списков (добавление одного списка в конец другого) и инверсия (изменение порядка элементов на противоположный). Первый вариант concat() содержит ошибку. Сможете ли вы ее найти?
void ilist::concat( const ilist &i1 ) {
if ( ! _at_end )
_at_front = i1._at_front;
else _at_end->next( i1._at_front );
_at_end = i1._at_end;
}
Проблема состоит в том, что теперь два объекта ilist содержат последовательность одних и тех же элементов. Изменение одного из списков, например вызов операций insert() и remove(), отражается на другом, приводя его в рассогласованное состояние. Простейший способ обойти эту проблему – скопировать каждый элемент второго списка. Сделаем это при помощи функции insert_end():
void ilist::
concat( const ilist &i1 )
{
i1ist_item *ptr = i1._at_front;
while ( ptr ) {
insert_end( ptr->value() );
ptr = ptr->next();
}
}
Вот реализация функции reverse():
void
ilist::
reverse()
{
ilist_item *ptr = _at_front;
ilist_item *prev = 0;
_at_front = _at_end;
_at_end = ptr;
while ( ptr != _at_front )
{
ilist_item *tmp = ptr->next();
ptr->next( prev );
prev = ptr;
ptr = tmp;
}
_at_front->next( prev );
}
Тестовая программа для проверки этих операций выглядит так:
#include <iostream>
#include "ilist.h"
int main()
{
ilist mylist;
for ( int ix = 0; ix < 10; ++ix )
{ mylist.insert_front( ix ); }
mylist.display();
cout << "\n" << "инвертирование списка\n";
mylist.reverse(); mylist.display();
ilist mylist_too;
mylist_too.insert_end(0); mylist_too.insert_end(1);
mylist_too.insert_end(1); mylist_too.insert_end(2);
mylist_too.insert_end(3); mylist_too.insert_end(5);
cout << "\n" << "mylist_too:\n";
mylist_too.display();
mylist.concat( mylist_too );
cout << "\n"
<< "mylist после concat с mylist_too:\n";
mylist.disp1ay();
}
Результат работы программы:
( 10 ) ( 9 8 7 6 5 4 3 2 1 0 )
инвертирование списка
( 10 ) ( 0 1 2 3 4 5 6 7 8 9 )
mylist_too:
( 6 )( 0 1 1 2 3 5 )
mylist после concat с mylist_too:
( 16 ) ( 0 1 2 3 4 5 6 7 8 9 0 1 1 2 3 5 )
С одной стороны, задачу можно считать выполненной: мы не только реализовали все запланированные функции, но и проверили их работоспособность. С другой стороны, мы не обеспечили всех операций, которые необходимы для практического использования списка.
Одним из главных недостатков является то, что у пользователя нет способа перебирать элементы списка и он не может обойти это ограничение, поскольку реализация от него скрыта. Другим недостатком является отсутствие поддержки операций инициализации одного списка другим и присваивания одного списка другому. Мы сознательно не стали их реализовывать в первой версии, но теперь начнем улучшать наш класс.
Для реализации первой операции инициализации необходимо определить копирующий конструктор. Поведение такого конструктора, построенного компилятором по умолчанию, совершенно неправильно для нашего класса (как, собственно, и для любого класса, содержащего указатель в качестве члена), именно поэтому мы с самого начала запретили его использование. Лучше уж полностью лишить пользователя какой-либо операции, чем допустить возможные ошибки. (В разделе 14.5 объясняется, почему действия копирующего конструктора по умолчанию в подобных случаях неверны.) Вот реализация конструктора, использующая функцию insert_end():
ilist::ilist( const ilist &rhs )
{
ilist_item *pt = rhs._at_front;
while ( pt ) {
insert_end( pt->value() );
pt = pt->next();
}
}
Оператор присваивания должен сначала вызвать remove_all(), а затем с помощью insert_end() вставить все элементы второго списка. Поскольку эта операция повторяется в обеих функциях, вынесем ее в отдельную функцию insert_all():
void ilist::insert_all ( const ilist &rhs )
{
ilist_item *pt = rhs._at_front;
while ( pt ) {
insert_end( pt->value() );
pt = pt->next();
}
}
после чего копирующий конструктор и оператор присваивания можно реализовать так:
inline ilist::ilist( const ilist &rhs )
: _at_front( 0 ), _at_end( 0 )
{ insert_all ( rhs ); }
inline ilist&
ilist::operator=( const ilist &rhs ) {
remove_all();
insert_all( rhs );
return *this;
}
Теперь осталось обеспечить пользователя возможностью путешествовать по списку, например с помощью доступа к члену _at_front:
ilist_item *ilist::front() { return _at_front(); }
После этого можно применить ilist_item::next(), как мы делали в функциях-членах:
ilist_item *pt = mylist.front();
while ( pt ) {
do_something( pt->value() );
pt = pt->next();
}
Хотя это решает проблему, лучше поступить иначе: реализовать общую концепцию прохода по элементам контейнера. В данном разделе мы расскажем об использовании цикла такого вида:
for ( ilist_item *iter = mylist.init_iter();
iter;
iter = mylist.next_iter() )
do_something( iter->value() );
(В разделе 2.8 мы уже касались понятия итератора. В главах 6 и 12 будут рассмотрены итераторы для имеющихся в стандартной библиотеке контейнерных типов и обобщенных алгоритмов.)
Наш итератор представляет собой несколько больше, чем просто указатель. Он должен уметь запоминать текущий элемент, возвращать следующий и определять, когда все элементы кончились. По умолчанию итератор инициализируется значением _at_front, однако пользователь может задать в качестве начального любой элемент списка. next_iter() возвращает следующий элемент или 0, если элементов больше нет. Для реализации пришлось ввести дополнительный член класса:
class ilist {
public:
// ...
init_iter( ilist_item *it = 0 );
private:
//...
ilist_item *_current;
};
init_iter() выглядит так:
inline ilist_item*
ilist::init_iter( i1ist_item *it )
{
return _current = it ? it : _at_front;
}
next_iter() перемещает указатель _current на следующий элемент и возвращает его адрес, если элементы не кончились. В противном случае он возвращает 0 и устанавливает _current в 0. Его реализацию можно представить следующим образом:
inline ilist_item*
ilist::
next_iter()
{
ilist_item *next = _current
? _current = _current->next()
: _current;
return next;
}
Если элемент, на который указывает _current, удален, могут возникнуть проблемы. Их преодолевают модификацией кода функций remove() и remove_front(): они должны проверять значение _current. Если он указывает на удаляемый элемент, функции изменят его так, чтобы он адресовал следующий элемент либо был равен 0, когда удаляемый элемент – последний в списке или список стал пустым. Модифицированная remove_front() выглядит так:
inline void
ilist::remove_front()
{
if ( _at_front ) {
ilist_item *ptr = _at_front;
_at_front = _at_front->next();
// _current не должен указывать на удаленный элемент
if ( _current == ptr )
_current = _at_front;
bump_down_size();
delete ptr;
}
}
Вот модифицированный фрагмент кода remove():
while ( plist ) {
if ( plist->value() == value )
{
prev->next( plist->next() );
if ( _current == plist )
_current = prev->next();
Что произойдет, если элемент будет вставлен перед тем, на который указывает _current? Значение _current не изменяется. Пользователь должен начать проход по списку с помощью вызова init_iter(), чтобы новый элемент попал в число перебираемых. При инициализации списка другим и при присваивании значение _current не копируется, а сбрасывается в 0.
Тестовая программа для проверки работы копирующего конструктора и оператора присваивания выглядит так::
#include <iostream>
#include "ilist.h"
int main()
{
ilist mylist;
for ( int ix = 0; ix < 10; ++ix ) {
mylist.insert_front( ix );
mylist.insert_end( ix );
}
cout << "\n" << "Применение init_iter() и next_iter() "
<< "для обхода всех элементов списка:\n";
ilist_item *iter;
for ( iter = mylist.init_iter();
iter; iter = mylist.next_iter() )
cout << iter->value() << " ";
cout << "\n" << "Применение копирующего конструктора\n";
ilist mylist2( mylist );
mylist.remove_all();
for ( iter = mylist2.init_iter();
iter; iter = mylist2.next_iter() )
cout << iter->value() << " ";
cout << "\n" << "Применение копирующего оператора присваивания\n";
mylist = mylist2;
for ( iter = mylist.init_iter();
iter; iter = mylist.next_iter() )
cout << iter->value() << " ";
cout << "\n";
}
Результат работы программы:
Применение init_iter() и next_iter() для обхода всех элементов списка:
9 8 7 6 5 4 3 2 1 0 0 1 2 3 4 5 6 7 8 9
Применение копирующего конструктора
9 8 7 6 5 4 3 2 1 0 0 1 2 3 4 5 6 7 8 9
Применение копирующего оператора присваивания
9 8 7 6 5 4 3 2 1 0 0 1 2 3 4 5 6 7 8 9
Приоритеты
Приоритеты операций задают последовательность вычислений в сложном выражении. Например, какое значение получит ival?
int ival = 6 + 3 * 4 / 2 + 2;
Если вычислять операции слева направо, получится 20. Среди других возможных результатов будут 9, 14 и 36. Правильный ответ: 14.
В С++ умножение и деление имеют более высокий приоритет, чем сложение, поэтому они будут вычислены раньше. Их собственные приоритеты равны, поэтому умножение и деление будут вычисляться слева направо. Таким образом, порядок вычисления данного выражения таков:
1. 3 * 4 => 12
2. 12 / 2 => 6
3. 6 + 6 => 12
4. 12 + 2 => 14
Следующая конструкция ведет себя не так, как можно было бы ожидать. Приоритет операции присваивания меньше, чем операции сравнения:
while ( ch = nextChar() != '\n' )
Программист хотел присвоить переменной ch значение, а затем проверить, равно ли оно символу новой строки. Однако на самом деле выражение сначала сравнивает значение, полученное от nextChar(), с '\n', и результат – true или false – присваивает переменной ch.
Приоритеты операций можно изменить с помощью скобок. Выражения в скобках вычисляются в первую очередь. Например:
4 * 5 + 7 * 2 ==> 34
4 * ( 5 + 7 * 2 ) ==> 76
4 * ( (5 + 7) * 2 ) ==> 96
Вот как с помощью скобок исправить поведение предыдущего примера:
while ( (ch = nextChar()) != '\n' )
Операторы обладают и приоритетом, и ассоциативностью. Оператор присваивания правоассоциативен, поэтому вычисляется справа налево:
ival = jval = kva1 = lval
Сначала kval получает значение lval, затем jval – значение результата этого присваивания, и в конце концов ival получает значение jval .
Арифметические операции, наоборот, левоассоциативны. Следовательно, в выражении
ival + jval + kva1 + 1va1
сначала складываются ival и jval, потом к результату прибавляется kval, а затем и lval.
В таблице 4.4 приведен полный список операторов С++ в порядке уменьшения их приоритета. Операторы внутри одной секции таблицы имеют равные приоритеты. Все операторы некоторой секции имеют более высокий приоритет, чем операторы из секций, следующих за ней. Так, операции умножения и деления имеют одинаковый приоритет, и он выше приоритета любой из операций сравнения.
Упражнение 4.18
Каков порядок вычисления следующих выражений? При ответе используйте таблицу 4.4.
(a) ! ptr == ptr->next
(b) ~ uc ^ 0377 & ui << 4
(c) ch = buf[ bp++ ] != '\n'
Упражнение 4.19
Все три выражения из предыдущего упражнения вычисляются не в той последовательности, какую, по-видимому, хотел задать программист. Расставьте скобки так, чтобы реализовать его первоначальный замысел.
Упражнение 4.20
Следующие выражения вызывают ошибку компиляции из-за неправильно понятого приоритета операций. Объясните, как их исправить, используя таблицу 4.4.
(a) int i = doSomething(), 0;
(b) cout << ival % 2 ? "odd" : "even";
Таблица 4.4. Приоритеты операций
|
Оператор |
Значение |
Использование |
|
|
:: |
Глобальная область видимости |
::name |
|
|
:: |
Область видимости класса |
class::name |
|
|
:: |
Область видимости пространства имен |
namespace::name |
|
|
. |
Доступ к члену |
object.member |
|
|
-> |
Доступ к члену по указателю |
pointer->member |
|
|
[] |
Взятие индекса |
variable[expr] |
|
|
() |
Вызов функции |
name(expr_list) |
|
|
() |
Построение значения |
type(expr_list) |
|
|
++ |
постфиксный инкремент |
lvalue++ |
|
|
-- |
постфиксный декремент |
lvalue-- |
|
|
typeid |
идентификатор типа |
typeid(type) |
|
|
typeid |
идентификатор типа выражения |
typeid(expr) |
|
|
const_cast |
преобразование типа |
const_cast<type>(expr) |
|
|
dynamic_cast |
преобразование типа |
dynamic_cast<type>(expr) |
|
|
reinterpret_cast |
приведение типа |
reinterpret_cast<type> (expr) |
|
|
static_cast |
приведение типа |
static_cast<type>(expr) |
|
|
sizeof |
размер объекта |
sizeof expr |
|
|
sizeof |
размер типа |
sizeof( type) |
|
|
++ |
префиксный инкремент |
++lvalue |
|
|
-- |
префиксный декремент |
--lvalue |
|
|
~ |
побитовое НЕ |
~expr |
|
|
! |
логическое НЕ |
!expr |
|
|
- |
унарный минус |
-expr |
|
|
+ |
унарный плюс |
+expr |
|
|
* |
разыменование |
*expr |
|
|
& |
адрес |
&expr |
|
|
() |
приведение типа |
(type)expr |
|
|
new |
выделение памяти |
new type |
|
|
new |
выделение памяти и инициализация |
new type(exprlist) |
|
|
new |
выделение памяти |
new (exprlist) type(exprlist) |
|
|
new |
выделение памяти под массив |
все формы |
|
|
delete |
освобождение памяти |
все формы |
|
|
delete |
освобождение памяти из-под массива |
все формы |
|
|
->* |
доступ к члену классу по указателю |
pointer-> *pointer_to_member |
|
|
.* |
доступ к члену класса по указателю |
object.*pointer_to_member |
|
|
* |
умножение |
expr * expr |
|
|
/ |
деление |
expr / expr |
|
|
% |
деление по модулю |
expr % expr |
|
|
+ |
сложение |
expr + expr |
|
|
- |
вычитание |
expr - expr |
|
|
<< |
сдвиг влево |
expr << expr |
|
|
>> |
сдвиг вправо |
expr >> expr |
|
|
< |
меньше |
expr < expr |
|
|
<= |
меньше или равно |
expr <= expr |
|
|
> |
больше |
expr > expr |
|
|
>= |
больше или равно |
expr >= expr |
|
|
== |
равно |
expr == expr |
|
|
!= |
не равно |
expr != expr |
|
|
& |
побитовое И |
expr & expr |
|
|
^ |
побитовое ИСКЛЮЧАЮЩЕЕ ИЛИ |
expr ^ expr |
|
|
| |
побитовое ИЛИ |
expr | expr |
|
|
&& |
логическое И |
expr && expr |
|
|
|| |
логическое ИЛИ |
expr || expr |
|
|
?: |
условный оператор |
expr ? expr * expr |
|
|
= |
присваивание |
l-значение = expr |
|
|
=, *=, /=, %=, +=, -=, <<=, >>=, &=, |=, ^= |
составное присваивание |
l-значение += expr и т.д. |
|
|
throw |
возбуждение исключения |
throw expr |
|
|
, |
запятая |
expr, expr |
Присваивание и обмен
Что происходит, если мы присваиваем один контейнер другому? Оператор присваивания копирует элементы из контейнера, стоящего справа, в контейнер, стоящий слева от знака равенства. А если эти контейнеры имеют разный размер? Например:
// svecl содержит 10 элементов
// svec2 содержит 24 элемента
// после присваивания оба содержат по 24 элемента
svecl = svec2;
Контейнер-адресат (svec1) теперь содержит столько же элементов, сколько контейнер-источник (svec2). 10 элементов, изначально содержавшихся в svec1, удаляются (для каждого из них вызывается деструктор класса string).
Функция обмена swap() может рассматриваться как дополнение к операции присваивания. Когда мы пишем:
svecl.swap( svec2 );
svec1 после вызова функции содержит 24 элемента, которые он получил бы в результате присваивания:
svecl = svec2;
но зато теперь svec2 получает 10 элементов, ранее находившихся в svec1. Контейнеры “обмениваются” своим содержимым.
Приводим слова к стандартной форме
Одной из проблем при разработке текстовых поисковых систем является необходимость распознавать слова в различных словоформах, такие, как cry, cries и cried, baby и babies, и, что гораздо проще, написанные заглавными и строчными буквами, например home и Home. Первая задача, распознавание словоформ, слишком сложна, поэтому мы приведем здесь ее заведомо неполное решение. Сначала заменим все прописные буквы строчными:
void
strip_caps( vector<string,allocator> *words )
{
vector<string,allocator>::iterator iter=words->begin() ;
vector<string,allocator>::iterator iter_end=words->end() ;
string caps( "ABCDEFGHIJKLMNOPQRSTUVWXYZ" );
while ( iter != iter_end ) {
string::size_type pos = 0;
while (( pos = (*iter).find_first_of( caps, pos ))
!= string::npos )
(*iter)[ pos ] = to1ower( (*iter)[pos] );
++iter;
}
}
Функция
to1ower( (*iter)[pos] );
входит в стандартную библиотеку С. Она заменяет прописную букву соответствующей ей строчной. Для использования tolower() необходимо включить заголовочный файл:
#include <ctype.h>
(В этом файле объявлены и другие функции, такие, как isalpha(), isdigit(), ispunct(), isspace(), toupper(). Полное описание этих функций см. [PLAUGER92]. Стандартная библиотека С++ включает класс ctype, который инкапсулирует всю функциональность стандартной библиотеки Си, а также набор функций, не являющихся членами, например toupper(), tolower() и т.д. Для их использования нужно включить заголовочный файл
#include <locale>
Однако наша реализация компилятора еще не поддерживала класс ctype, и нам пришлось использовать стандартную библиотеку Си.)
Проблема словоформ слишком сложна для того, чтобы пытаться решить ее в общем виде. Но даже самый примитивный вариант способен значительно улучшить работу нашей поисковой системы. Все, что мы сделаем в данном направлении, – удалим букву 's' на концах слов:
void suffix_text( vector<string,allocator> *words )
{
vector<string,allocator>::iterator
iter = words->begin(),
iter_end = words->end();
while ( iter != iter_end ) {
// оставим слова короче трех букв как есть
if ( (*iter).size() <= 3 )
{ ++iter; continue; }
if ( (*iter)[ (*iter).size()-1 ] == 's' )
suffix_s( *iter );
// здесь мы могли бы обработать суффиксы
// ed, ing, 1y
++iter;
}
}
Слова из трех и менее букв мы пропускаем. Это позволяет оставить без изменения, например, has, its, is и т.д., однако слова tv и tvs мы не сможем распознать как одинаковые.
Если слово кончается на "ies", как babies и cries, необходимо заменить "ies" на "y":
string::size_type pos() = word.size()-3;
string ies( "ies" );
if ( ! word.compare( pos3, 3, ies )) {
word.replace( pos3, 3, 1, 'у' );
return;
}
compare() возвращает 0, если две строки равны. Первый аргумент, pos3, обозначает начальную позицию, второй – длину сравниваемой подстроки (в нашем случае 3). Третий аргумент, ies, – строка-эталон. (На самом деле существует шесть вариантов функции compare(). Остальные мы покажем в следующем разделе.)
replace() заменяет подстроку набором символов. В данном случае мы заменяем подстроку "ies" длиной в 3 символа единичным символом 'y'. (Имеется десять перегруженных вариантов функции replace(). В следующем разделе мы коснемся остальных вариантов.)
Если слово заканчивается на "ses", как promises или purposes, нужно удалить суффикс "es"[16]:
string ses( "ses" );
if ( ! word.compare( pos3, 3, ses )) {
word.erase( pos3+l, 2 );
return;
}
Если слово кончается на "ous", как oblivious, fulvous, cretaceous, или на "is", как genesis, mimesis, hepatitis, мы не будем изменять его. (Наша система несовершенна. Например, в слове kiwis надо убрать последнее 's'.) Пропустим и слова, оканчивающиеся на "ius" (genius) или на "ss" (hiss, lateness, less). Нам поможет вторая форма функции compare():
string::size_type spos = 0;
string::size_type pos3 = word.size()-3;
// "ous", "ss", "is", "ius"
string suffixes( "oussisius" );
if ( ! word.compare( pos3, 3, suffixes, spos, 3 ) || // ous
! word.compare( pos3, 3, suffixes, spos+6, 3 ) || // ius
! word.compare( pos3+l, 2, suffixes, spos+2, 2 ) || // ss
! word.compare( pos3+l, 2, suffixes, spos+4, 2 ) ) // is
return;
В противном случае удалим последнее 's':
// удалим последнее 's'
word.erase( pos3+2 );
Имена собственные, например Pythagoras, Brahms, Burne-Jones, не подпадают под общие правила. Этот случай мы оставим как упражнение для читателя, когда будем рассказывать об ассоциативных контейнерах.
Но прежде чем перейти к ним, рассмотрим оставшиеся строковые операции.
Упражнение 6.17
Наша программа не умеет обрабатывать суффиксы ed (surprised), ly (surprisingly) и ing (surprisingly). Реализуйте одну из функций для этого случая:
(a) suffix_ed() (b) suffix_ly() (c) suffix_ing()
Программа на языке C++
В С++ действие называется выражением, а выражение, заканчивающееся точкой с запятой, – инструкцией. Инструкция – это атомарная часть С++ программы, которой в программе на С++ соответствует предложение естественного языка. Вот примеры инструкций С++:
int book_count = 0;
book_count = books_on_shelf + books_on_order;
cout << "значение переменной book_count: " << book_count;
Первая из приведенных инструкций является инструкцией объявления. book_count можно назвать идентификатором, символической переменной (или просто переменной) или объектом. Переменной соответствует область в памяти компьютера, соотнесенная с определенным именем (в данном случае book_count), в которой хранится значение типа (в нашем случае целого). 0 – это константа. Переменная book_count инициализирована значением 0.
Вторая инструкция – присваивание. Она помещает в область памяти, отведенную переменной book_count, результат сложения двух других переменных – books_on_shelf и books_on_order. Предполагается, что эти две целочисленные переменные определены где-то ранее в программе и им присвоены некоторые значения.
Третья инструкция является инструкцией вывода. cout – это выходной поток, направленный на терминал, << – оператор вывода. Эта инструкция выводит в cout – то есть на терминал – сначала символьную константу, заключенную в двойные кавычки ("значение переменной book_count: "), затем значение, содержащееся в области памяти, отведенном под переменную book_count. В результате выполнения данной инструкции мы получим на терминале сообщение:
значение переменной book_count: 11273
если значение book_count равно 11273 в данной точке выполнения программы.
Инструкции часто объединяются в именованные группы, называемые функциями. Так, группа инструкций, необходимых для чтения исходного файла, объединена в функцию readIn(). Аналогичным образом инструкции для выполнения оставшихся подзадач сгруппированы в функции sort(), compact() и print().
В каждой С++ программе должна быть ровно одна функция с именем main(). Вот как может выглядеть эта функция для нашего алгоритма:
int main()
{
readIn();
sort();
compact();
print();
return 0;
}
Исполнение программы начинается с выполнения первой инструкции функции main(), в нашем случае – вызовом функции readIn(). Затем одна за другой исполняются все дальнейшие инструкции, и, выполнив последнюю инструкцию функции main(), программа заканчивает работу.
Функция состоит их четырех частей: типа возвращаемого значения, имени, списка параметров и тела функции. Первые три части составляют прототип функции.
Список параметров заключается в круглые скобки и может содержать ноль или более параметров, разделенных запятыми. Тело функции содержит последовательность исполняемых инструкций и ограничено фигурными скобками.
В нашем примере тело функции main() содержит вызовы функций readIn(), sort(), compact() и print(). Последней выполняется инструкция
return 0;
Инструкция return обеспечивает механизм завершения работы функции. Если оператор return сопровождается некоторым значением (в данном примере 0), это значение становится возвращаемым значением функции. В нашем примере возвращаемое значение 0 говорит об успешном выполнении функции main(). (Стандарт С++ предусматривает, что функция main() возвращает 0 по умолчанию, если оператор return не использован явно.)
Давайте закончим нашу программу, чтобы ее можно было откомпилировать и выполнить. Во-первых, мы должны определить функции readIn(), sort(), compact() и print(). Для начала вполне подойдут заглушки:
void readIn() { cout << "readIn()\n"; }
void sort() { cout << "sort()\n"; }
void compact() { cout << "compact()\n"; }
void print() { cout << "print ()\n"; }
Тип void используется, чтобы обозначить функцию, которая не возвращает никакого значения. Наши заглушки не производят никаких полезных действий, они только выводят на терминал сообщения о том, что были вызваны. Впоследствии мы заменим их на реальные функции, выполняющие нужную нам работу.
Пошаговый метод написания программ позволяет справляться с неизбежными ошибками. Попытаться заставить работать сразу всю программу – слишком сложное занятие.
Имя файла с текстом программы, или исходного файла, как правило, состоит из двух частей: собственно имени (например, bookstore) и расширения, записываемого после точки. Расширение, в соответствии с принятыми соглашениями, служит для определения назначения файла. Файл bookstore.h является заголовочным файлом
для С или С++ программы. (Необходимо отметить, что стандартные заголовочные файлы С++ являются исключением из правила: у них нет расширения.)
Файл bookstore.c является исходным файлом для нашей С программы. В операционной системе UNIX, где строчные и прописные буквы в именах файлов различаются, расширение .C обозначает исходный текст С++ программы, и в файле bookstore.C располагается исходный текст С++.
В других операционных системах, в частности в DOS, где строчные и прописные буквы не различаются, разные реализации могут использовать разные соглашения для обозначения исходных файлов С++. Чаще всего употребляются расширения .cpp и .cxx: bookstore.cpp, bookstore.cxx.
Заголовочные файлы С++ программ также могут иметь разные расширения в разных реализациях (и это одна из причин того, что стандартные заголовочные файлы С++ не имеют расширения). Расширения, используемые в конкретной реализации компилятора С++, указаны в поставляемой вместе с ним документации.
Итак, создадим текст законченной С++ программы (используя любой текстовый редактор):
#include <iostream>
using namespace std;
void readIn() { cout << "readIn()\n"; }
void sort() { cout << "sort()\n"; }
void compact() { cout << "compact()\n"; }
void print() { cout << "print ()\n"; }
int main() {
readIn();
sort();
compact();
print();
return 0;
}
Здесь iostream – стандартный заголовочный файл библиотеки ввода/вывода (обратите внимание: у него нет расширения). Эта библиотека содержит информацию о потоке cout, используемом в нашей программе. #include является директивой препроцессора, заставляющей включить в нашу программу текст из заголовочного файла iostream. (Директивы препроцессора рассматриваются в разделе 1.3.)
Непосредственно за директивой препроцессора
#include <iostream>
следует инструкция
using namespace std;
Эта инструкция называется директивой using. Имена, используемые в стандартной библиотеке С++ (такие, как cout), объявлены в пространстве имен std и невидимы в нашей программе до тех пор, пока мы явно не сделаем их видимыми, для чего и применяется данная директива. (Подробнее о пространстве имен говорится в разделах 2.7 и 8.5.)[1]
После того как исходный текст программы помещен в файл, скажем prog1.C, мы должны откомпилировать его. В UNIX для этого выполняется следующая команда:
$ CC prog1.C
Здесь $ представляет собой приглашение командной строки. CC – команда вызова компилятора С++, принятая в большинстве UNIX-систем. Команды вызова компилятора могут быть разными в разных системах.
Одной из задач, выполняемых компилятором в процессе обработки исходного файла, является проверка правильности программы. Компилятор не может обнаружить смысловые ошибки, однако он может найти формальные ошибки в тексте программы. Существует два типа формальных ошибок:
синтаксические ошибки. Программист может допустить “грамматические”, с точки зрения языка С++, ошибки. Например:
int main( { // ошибка – пропущена ')'
readIn(): // ошибка – недопустимый символ ':'
sort();
compact();
print();
return 0 // ошибка – пропущен символ ';'
}
ошибки типизации. С каждой переменной и константой в С++ сопоставлен некоторый тип. Например, число 10 – целого типа. Строка "hello", заключенная в двойные кавычки, имеет символьный тип. Если функция ожидает получить в качестве параметра целое значение, а получает символьную строку, компилятор рассматривает это как ошибку типизации.
Сообщение об ошибке содержит номер строки и краткое описание. Полезно просматривать список ошибок, начиная с первой, потому что одна-единственная ошибка может вызвать цепную реакцию, появление “наведенных” ошибок. Исправление этой единственной ошибки приведет и к исчезновению остальных. После исправления синтаксических ошибок программу нужно перекомпилировать.
После проверки на правильность компилятор переводит исходный текст в объектный код, который может быть понят и исполнен компьютером. Эту фазу работы компилятора называют генерацией кода.
В результате успешной компиляции образуется выполняемый файл. Если запустить выполняемый файл, полученный в результате компиляции нашей программы, на терминале появится следующий текст:
readIn()
sort()
compact()
print()
В С++ набор основных типов данных – это целый и вещественный числовые типы, символьный тип и логический, или булевский. Каждый тип обозначается своим ключевым словом. Любой объект программы ассоциируется с некоторым типом. Например:
int age = 10;
double price = 19.99;
char delimiter = ' ';
bool found = false;
Здесь определены четыре объекта: age, price, delimiter, found, имеющие соответственно типы целый, вещественный с двойной точностью, символьный и логический. Каждый объект инициализирован константой – целым числом 10, вещественным числом 19.99, символом пробела и логическим значением false.
Между основными типами данных может осуществляться неявное преобразование типов. Если переменной age, имеющей тип int, присвоить константу типа double, например:
age = 33.333;
то значением переменной age станет целое число 33. (Стандартные преобразования типов, а также общие проблемы преобразования типов рассматриваются в разделе 4.14.)
Стандартная библиотека С++ расширяет базовый набор типов, добавляя к ним такие типы, как строка, комплексное число, вектор, список. Примеры:
// заголовочный файл с определением типа string
#include <string>
string current_chapter = "Начинаем";
// заголовочный файл с определением типа vector
#include <vector>
vector<string> chapter_titles(20);
Здесь current_chapter – объект типа string, инициализированный константой "Начинаем". Переменная chapter_titles – вектор из 20 элементов строкового типа. Несколько необычный синтаксис выражения
vector<string>
сообщает компилятору о необходимости создать вектор, содержащий объекты типа string. Для того чтобы определить вектор из 20 целых значений, необходимо написать:
vector<int> ivec(20);
Никакой язык, никакие стандартные библиотеки не способны обеспечить нас всеми типами данных, которые могут потребоваться. Взамен современные языки программирования предоставляют механизм создания новых типов данных. В С++ для этого служит механизм классов. Все расширенные типы данных из стандартной библиотеки С++, такие как строка, комплексное число, вектор, список, являются классами, написанными на С++. Классами являются и объекты из библиотеки ввода/вывода.
Механизм классов – одна из самых главных особенностей языка С++, и в главе 2 мы рассмотрим его очень подробно.
Пространства имен и шаблоны функций *
Как и любое другое глобальное определение, шаблон функции может быть помещен в пространство имен (см. обсуждение пространств имен в разделах 8.5 и 8.6). Мы получили бы ту же семантику, если бы определили шаблон в глобальной области видимости, скрыв его имя внутри пространства имен. При использовании вне этого пространства необходимо либо квалифицировать имя шаблона именем пространства имен, либо использовать using-объявление:
// ---- primer.h ----
namespace cplusplus_primer {
// определение шаблона скрыто в пространстве имен
template <class Type>
Type min( Type* array, int size ) { /* ... */ }
}
// ---- user.C ----
#include <primer.h>
int ai[4] = { 12, 8, 73, 45 };
int main() {
int size = sizeof(ai) / sizeof(ai[0]);
// ошибка: функция min() не найдена
min( &ai[0], size );
using cplusplus_primer::min; // using-объявление
// правильно: относится к min() в пространстве имен cplusplus_primer
min( &ai[0], size );
}
Что произойдет, если наша программа использует шаблон, определенный в пространстве имен, и мы хотим предоставить для него специализацию? (Явные специализации шаблонов рассматривались в разделе 10.6.) Допустим, мы хотим использовать шаблон min(), определенный в cplusplus_primer, для нахождения минимального значения в массиве объектов типа SmallInt. Однако мы осознаем, что имеющееся определение шаблона не вполне подходит, поскольку сравнение в нем выглядит так:
if ( array[i] < min_val )
В этой инструкции два объекта класса SmallInt сравниваются с помощью оператора <. Но этот оператор неприменим к объектам, если только не перегружен в классе SmallInt (мы покажем, как определять перегруженные операторы в главе 15). Предположим, что мы хотели бы определить специализацию шаблона min(), чтобы она пользовалась функцией compareLess() для сравнения двух подобных объектов. Вот ее объявление:
// функция сравнения объектов SmallInt
// возвращает true, если parm1 меньше parm2
bool compareLess( const SmallInt &parm1, const SmallInt &parm2 );
Как должно выглядеть определение этой функции? Чтобы ответить на этот вопрос, необходимо познакомиться с определением класса SmallInt более подробно. Данный класс позволяет определять объекты, которые хранят тот же диапазон значений, что и 8-разрядный тип unsigned char, т.е. от 0 до 255. Дополнительная функциональность состоит в том, что класс перехватывает ошибки переполнения и потери значимости. Во всем остальном он должен вести себя точно так же, как unsigned char. Определение SmallInt выглядит следующим образом:
class SmallInt {
public:
SmallInt( int ival ) : value( ival ) {}
friend bool compareLess( const SmallInt &, const SmallInt & );
private:
int value; // член
};
В этом классе есть один закрытый член value, в котором хранится значение объекта типа SmallInt. Класс также содержит конструктор с параметром ival:
// конструктор класса SmallInt
SmallInt( int ival ) : value( ival ) {}
Его единственное назначение – инициализировать член класса value значением ival.
Вот теперь можно ответить на ранее поставленный вопрос: как должна быть определена функция compareLess()? Она будет сравнивать члены value переданных ей аргументов типа SmallInt:
// возвращает true, если parm1 меньше parm2
bool compareLess( const SmallInt &parm1, const SmallInt &parm2 ) {
return parm1.value < parm2.value;
}
Заметим, однако, что член value является закрытым. Как может глобальная функция обратиться к закрытому члену, не нарушив инкапсуляции класса SmallInt и не вызвав тем самым ошибку компиляции? Если вы посмотрите на определение класса SmallInt, то заметите, что глобальная функция compareLess() объявлена как дружественная (friend). Если функция объявлена таким образом, то ей доступны закрытые члены класса. (Друзья классов рассматриваются в разделе 15.2.)
Теперь мы готовы определить специализацию шаблона min(). Она следующим образом использует функцию compareLess().
// специализация min() для массива объектов SmallInt
template<> SmallInt min<smallInt>( SmallInt* array, int size )
{
SmallInt min_val = array[0];
for (int i = 1; i < size; ++i)
// при сравнении используется функция compareLess()
if ( compareLess( array[i], min_val ) )
min_val = array[i];
print( "Minimum value found: " );
print( min_val );
return min_val;
}
Где мы должны объявить эту специализацию? Предположим, что здесь:
// ---- primer.h ----
namespace cplusplus_primer {
// определение шаблона скрыто в пространстве имен
template <class Type>
Type min( Type* array, int size ) { /* ... */ }
}
// ---- user.h ----
class SmallInt { /* ... */ };
void print( const SmallInt & );
bool compareLess( const SmallInt &, const SmallInt & );
// ---- user.C ----
#include <primer.h>
#include "user.h"
// ошибка: это не специализация для cplusplus_primer::min()
template<> SmallInt min<smallInt>( SmallInt* array, int size )
{ /* ... */ }
// ...
К сожалению, этот код не работает. Явная специализация шаблона функции должна быть объявлена в том пространстве имен, где определен порождающий шаблон. Поэтому мы обязаны определить специализацию min() в пространстве cplusplus_primer. В нашей программе это можно сделать двумя способами.
Напомним, что определения пространства имен не обязательно непрерывны. Мы можем повторно открыть пространство имен cplusplus_primer для добавления специализации:
// ---- user.C ----
#include <primer.h>
#include "user.h"
namespace cplusplus_primer {
// специализация для cplusplus_primer::min()
template<> SmallInt min<smallInt>( SmallInt* array, int size )
{ /* ... */ }
}
SmallInt asi[4];
int main() {
// задать значения элементов массива asi с помощью функции-члена set()
using cplusplus_primer::min; // using-объявление
int size = sizeof(asi) / sizeof(SmallInt);
// конкретизируется min(SmallInt*,int)
min( &asi[0], size );
}
Можно определить специализацию так, как мы определяем любой другой член пространства имен вне определения самого пространства: квалифицировав имя члена именем объемлющего пространства.
// ---- user.C ----
#include <primer.h>
#include "user.h"
// специализация для cplusplus_primer::min()
// имя специализации квалифицируется
namespace {
template<> SmallInt cplusplus_primer::
min<smallInt>( SmallInt* array, int size )
{ /* ... */ }
// ...
Если вы, пользуясь библиотекой, содержащей определения шаблонов, захотите написать их специализации, то должны будете удостовериться, что их определения помещены в то же пространство имен, что и определения исходных шаблонов.
Упражнение 10.15
Поместим содержимое заголовочного файла <exercise.h> из упражнения 10.14 в пространство имен cplusplus_primer. Как надо изменить функцию main(), чтобы она могла конкретизировать шаблон max(), находящийся в cplusplus_primer?
Упражнение 10.16
Снова обращаясь к упражнению 10.14, предположим, что содержимое заголовочного файла <exercise.h> помещено в пространство имен cplusplus_primer. Допустим, мы хотим специализировать шаблон функции max() для массивов объектов класса LongDouble. Нужно, чтобы специализация шаблона использовала функцию compareGreater() для сравнения двух объектов класса LongDouble, объявленную как:
// функция сравнения объектов класса LongDouble
// возвращает true, если parm1 больше parm2
bool compareGreater( const LongDouble &parm1,
const LongDouble &parm2 );
Определение класса LongDouble выглядит следующим образом:
class LongDouble {
public:
LongDouble(double dval) : value(ival) {}
friend bool compareGreater( const LongDouble &,
const LongDouble & );
private:
double value;
};
Напишите определение функции compareGreater() и специализацию max(), в которой эта функция используется. Напишите также функцию main(), которая задает элементы массива ad, а затем вызывает специализацию max(), доставляющую его максимальный элемент. Значения, которыми инициализируется массив ad, должны быть получены чтением из стандартного ввода cin.
Пространства имен и шаблоны классов
Как и любое определение в глобальной области видимости, определение шаблона класса можно поместить внутрь пространства имен. (Пространства имен рассматривались в разделах 8.5 и 8.6.) Наш шаблон будет скрыт в данном пространстве имен; лишь в этом отличие от ситуации, когда шаблон определен в глобальной области видимости. При употреблении вне пространства имя шаблона следует либо квалифицировать его именем, либо воспользоваться using-объявлением:
#include <iostream>
#include <cstdlib>
namespace cplusplus_primer {
template <class Type>
class Queue { // ...
};
template <class Type>
Type Queue<Type>::remove()
{
// ...
}
}
Если имя Queue шаблона класса используется вне пространства имен cplusplus_primer, то оно должно быть квалифицировано этим именем или введено с помощью using-объявления. Во всех остальных отношениях шаблон Queue используется так, как описано выше: конкретизируется, может иметь функции-члены, статические члены, вложенные типы и т.д. Например:
int main() {
using cplusplus_primer Queue; // using-объявление
// ссылается на шаблон класса в пространстве имен cplusplus_primer
Queue<int> *p_qi = new Queue<int>;
// ...
p_qi->remove();
}
Шаблон cplusplus_primer::Queue<int> конкретизируется, так как использован в выражении new:
... = new Queue<int>;
p_qi – это указатель на тип класса cplusplus_primer::Queue<int>. Когда он применяется для адресации функции-члена remove(), то речь идет о члене именно этого конкретизированного экземпляра класса.
Объявление шаблона класса в пространстве имен влияет также на объявления специализаций и частичных специализаций шаблона класса и его членов (см. разделы 16.9 и 16.10). Такая специализация должна быть объявлена в том же пространстве имен, где и общий шаблон.
В следующем примере в пространстве имен cplusplus_primer объявляются специализации типа класса Queue<char *> и функции-члена remove() класса Queue<double>:
#include <iostream>
#include <cstdlib>
namespace cplusplus_primer {
template <class Type>
class Queue { ... };
template <class Type>
Type Queue<Type>::remove() { ... }
// объявление специализации
// для cplusplus_primer::Queue<char *>
template<> class Queue<char*> { ... };
// объявление специализации
// для функции-члена cplusplus_primer::Queue<double>::remove()
template<> double Queue<double>::remove() { ... }
}
Хотя специализации являются членами cplusplus_primer, их определения в этом пространстве отсутствуют. Определить специализацию шаблона можно и вне пространства имен при условии, что определение будет находиться в некотором пространстве, объемлющем cplusplus_primer, и имя специализации будет квалифицировано его именем :
namespace cplusplus_primer
{
// определение Queue и его функций-членов
}
// объявление специализации
// cplusplus_primer::Queue<char*>
template<> class cplusplus_primer::Queue<char*> { ... };
// объявление специализации функции-члена
// cplusplus_primer::Queue<double>::remove()
template<> double cplusplus_primer::Queue<double>::remove()
{ ... }
Объявления специализаций класса cplusplus_primer::Queue<char*> и функции-члена remove() для класса cplusplus_primer::Queue<double> находятся в глобальной области видимости. Поскольку такая область содержит пространство имен cplusplus_primer, а имена специализаций квалифицированы его именем, то определения специализаций для шаблона Queue вполне законны.
Простые и составные инструкции
Простейшей формой является пустая инструкция. Вот как она выглядит:
; // пустая инструкция
Пустая инструкция используется там, где синтаксис С++ требует употребления инструкции, а логика программы– нет. Например, в следующем цикле while, копирующем одну строку в другую, все необходимые действия производятся внутри круглых скобок (условной части инструкции). Однако согласно правилам синтаксиса С++ после while должна идти инструкция. Поскольку нам нечего поместить сюда (вся работа уже выполнена), приходится оставить это место пустым:
while ( *string++ = inBuf++ )
; // пустая инструкция
Случайное появление лишней пустой инструкции не вызывает ошибки компиляции. Например, такая строка
ival = dval + sval;; // правильно: лишняя пустая инструкция
состоит из двух инструкций – сложения двух величин с присваиванием результата переменной ival и пустой.
Простая инструкция состоит из выражения, за которым следует точка с запятой. Например:
// простые инструкции
int ival = 1024; // инструкция определения переменной
ival; // выражение
ival + 5; // еще одно выражение
ival = ival +5; // присваивание
Условные инструкции и инструкции цикла синтаксически требуют употребления единственной инструкции, связанной с ними. Однако, как правило, этого недостаточно. В таких случаях употребляются составные инструкции – последовательность простых, заключенная в фигурные скобки:
if ( ival0 > ival1 ) {
// составная инструкция, состоящая
// из объявления и двух присваиваний
int temp = ivalO;
ivalO = ival1;
ival1 = temp;
}
Составная инструкция может употребляться там же, где простая, и не нуждается в завершающей точке с запятой.
Пустая составная инструкция эквивалентна пустой простой. Приведенный выше пример с пустой инструкцией можно переписать так:
while ( *string++ = *inBuf++ )
{} // пустая инструкция
Составную инструкцию, содержащую определения переменных, часто называют блоком. Блок задает локальную область видимости в программе – идентификаторы, объявленные внутри блока (как temp в предыдущем примере), видны только в нем. (Блоки, области видимости и время жизни объектов рассматриваются в главе 8.)
Прототип функции
Прототип функции описывает ее интерфейс и состоит из типа возвращаемого функцией значения, имени и списка параметров. В данном разделе мы детально рассмотрим эти характеристики.
Проверка типов формальных параметров
Функция gcd() объявлена следующим образом:
int gcd( int, int );
Объявление говорит о том, что имеется два параметра типа int. Список формальных параметров предоставляет компилятору информацию, с помощью которой тот может проверить типы передаваемых функции фактических аргументов.
Что будет, если попытаться вызвать функцию gcd() с аргументами типа char*?
gcd( "hello", "world" );
А если передать этой функции не два аргумента, а только один? Или больше двух? Что случится, если потеряется запятая между числами 24 и 312?
gcd( 24312 );
Единственное разумное поведение компилятора– сообщение об ошибке, поскольку попытка выполнить такую программу чревата весьма серьезными последствиями. С++ действительно не пропустит подобные вызовы. Текст сообщения будет выглядеть примерно так:
// gcd( "hello", "world" )
error: invalid argument types ( const char *, const char * ) --
expecting ( int, int )
ошибка: неверные типы аргументов ( const char *, const char * ) --
ожидается ( int, int )
// gcd( 24312 )
error: missing value for second argument
ошибка: пропущено значение второго аргумента
А если вызвать эту функцию с аргументами типа double? Должен ли этот вызов расцениваться как ошибочный?
gcd( 3.14, 6.29 );
Как было сказано в разделе 4.14, значение типа double может быть преобразовано в int. Следовательно, считать такой вызов ошибочным было бы слишком сурово. Вместо этого аргументы неявно преобразуются в int (отбрасыванием дробной части) и таким образом требования, налагаемые на типы параметров, выполняются. Поскольку при подобном преобразовании возможна потеря точности, хороший компилятор выдаст предупреждение. Вызов превращается в
gcd( 3, 6 );
что дает в результате 3.
С++ является строго типизированным языком. Компилятор проверяет аргументы на соответствие типов в каждом вызове функции. Если тип фактического аргумента не соответствует типу формального параметра, то производится попытка неявного преобразования. Если же это оказывается невозможным или число аргументов неверно, компилятор выдает сообщение об ошибке. Именно поэтому функция должна быть объявлена до того, как программа впервые обратится к ней: без объявления компилятор не обладает информацией для проверки типов.
Пропуск аргумента при вызове или передача аргумента неуказанного типа часто служили источником ошибок в языке С. Теперь такие погрешности обнаруживаются на этапе компиляции.
Упражнение 7.1
Какие из следующих прототипов функций содержат ошибки? Объясните.
(a) set( int *, int );
(b) void func();
(c) string error( int );
(d) arr[10] sum( int *, int );
Упражнение 7.2
Напишите прототипы для следующих функций:
Функция с именем compare, имеющая два параметра типа ссылки на класс matrix и возвращающая значение типа bool.
Функция с именем extract без параметров, возвращающая контейнер set для хранения значений типа int. (Контейнерный тип set описывался в разделе 6.13.)
Упражнение 7.3
Имеются объявления функций:
double calc( double );
int count( const string &, char );
void sum( vector<int> &, int );
vector<int> vec( 10 );
Какие из следующих вызовов содержат ошибки и почему?
(a) calc( 23.4, 55.1 );
(b) count( "abcda", 'a' );
(c) sum( vec, 43.8 );
(d) calc( 66 );
Псевдонимы пространства имен
Псевдоним пространства имен
используется для задания короткого синонима имени пространства. Например, длинное имя
namespace International_Business_Machines
{ /* ... */ }
может быть ассоциировано с более коротким синонимом:
namespace IBM = International_Business_Machines;
Объявление псевдонима начинается ключевым словом namespace, за которым следует короткий псевдоним, а за ним– знак равенства и исходное полное имя пространства. Если полное имя не соответствует никакому известному пространству, это ошибка.
Псевдоним может относиться и к вложенному пространству имен. Вспомним слишком длинное определение функции func() выше:
#include "primer.h"
// трудно читать!
void func( cplusplus_primer::MatrixLib::matrix &m )
{
// ...
cplusplLis_primer::MatrixLib::inverse( m );
return m;
}
Разрешается задать псевдоним для обозначения вложенного cplusplLis_primer::MatrixLib, сделав определение функции более удобным для восприятия:
#include "primer.h"
// более короткий псевдоним
namespace mlib = cplusplus_primer::MatrixLib;
// читать проще!
void func( mlib::matrix &m )
{
// ...
mlib::inverse( m );
return m;
}
Одно пространство имен может иметь несколько взаимозаменяемых псевдонимов. Например, если псевдоним Lib ссылается на cplusplus_primer, то определение функции func()
может выглядеть и так:
// псевдоним alias относится к пространству имен cplusplus_primer
namespace alias = Lib;
void func( cplusplus_primer::matrix &m ) {
// ...
alias::inverse( m );
return m;
}
Работа с указателями на члены класса
К указателям на члены класса можно обращаться только с помощью конкретного объекта или указателя на объект типа класса. Для этого применяется любой из двух операторов доступа (.* для объектов класса и ссылок на них или ->* для указателей). Например, так вызывается функция-член через указатель на нее:
int (Screen::*pmfi)() = &Screen::height;
Screen& (Screen::*pmfS)( const Screen& ) = &Screen::copy;
Screen myScreen, *bufScreen;
// прямой вызов функции-члена
if ( myScreen.height() == bufScreen->height() )
bufScreen->copy( myScreen );
// эквивалентный вызов по указателю
if ( (myScreen.*pmfi)() == (bufScreen->*pmfi)() )
(bufScreen->*pmfS)( myScreen );
Вызовы
(myScreen.*pmfi)()
(bufScreen->*pmfi)();
требуют скобок, поскольку приоритет оператора вызова () выше, чем приоритет взятия указателя на функцию-член. Без скобок
myScreen.*pmfi()
интерпретируется как
myScreen.*(pmfi())
Это означает вызов функции pmfi() и привязку возвращенного ей значения к оператору (.*). Разумеется, тип pmfi не поддерживает такого использования, так что компилятор выдаст сообщение об ошибке.
Указатели на данные-члены используются аналогично:
typedef short Screen::*ps_Screen;
Screen myScreen, *tmpScreen = new Screen( 10, 10 );
ps_Screen pH = &Screen::_height;
ps_Screen pW = &Screen::_width;
tmpScreen->*pH = myScreen.*pH;
tmpScreen->*pW = myScreen.*pW;
Приведем реализацию функции-члена repeat(), которую мы обсуждали в начале этого раздела. Теперь она будет принимать указатель на функцию-член:
typedef Screen& (Screen::Action)();
Screen& Screen::repeat( Action op, int times )
{
for ( int i = 0; i < times; ++i )
(this->*op)();
return *this;
}
Параметр op – это указатель на функцию-член, которая должна вызываться times раз.
Если бы нужно было задать значения аргументов по умолчанию, то объявление repeat() выглядело бы следующим образом:
class Screen {
public:
Screen &repeat( Action = &Screen::forward, int = 1 );
// ...
};
А ее вызовы так:
Screen myScreen;
myScreen.repeat(); // repeat( &Screen::forward, 1 );
myScreen.repeat( &Screen::down, 20 );
Определим таблицу указателей. В следующем примере Menu – это таблица указателей на функции- члены класса Screen, которые реализуют перемещение курсора. CursorMovements – перечисление, элементами которого являются номера в таблице Menu.
Action::Menu() = {
&Screen::home,
&Screen::forward,
&Screen::back,
&Screen::up,
&Screen::down,
&Screen::end
};
enum CursorMovements {
HOME, FORWARD, BACK, UP, DOWN, END
};
Можно определить перегруженную функцию-член move(), которая принимает параметр CursorMovements и использует таблицу Menu для вызова указанной функции-члена. Вот ее реализация:
Screen& Screen::move( CursorMovements cm )
{
( this->*Menu[ cm ] )();
return *this;
}
У оператора взятия индекса ([]) приоритет выше, чем у оператора указателя на функцию-член (->*). Первая инструкция в move() сначала по индексу выбирает из таблицы Menu нужную функцию-член, которая и вызывается с помощью указателя this и оператора указателя на функцию-член. move() можно применять в интерактивной программе, где пользователь выбирает вид перемещения курсора из отображаемого на экране меню.
Ранжирование последовательностей определенных пользователем преобразований
Фактический аргумент функции может быть неявно приведен к типу формального параметра с помощью последовательности определенных пользователем преобразований. Как это влияет на разрешение перегрузки? Например, если имеется следующий вызов calc(), то какая функция будет вызвана?
class SmallInt {
public:
SmallInt( int );
};
extern void calc( double );
extern void calc( SmallInt );
int ival;
int main() {
calc( ival ); // какая calc() вызывается?
}
Выбирается функция, формальные параметры которой лучше всего соответствуют типам фактических аргументов. Она называется лучшим соответствием или наилучшей из устоявших функций. Для выбора такой функции неявные преобразования, примененные к фактическим аргументам, подвергаются ранжированию. Лучшей из устоявших считается та, для которой примененные к аргументам изменения не хуже, чем для любой другой устоявшей, а хотя бы для одного аргумента они лучше, чем для всех остальных функций.
Последовательность стандартных преобразований всегда лучше последовательности определенных пользователем преобразований. Так, при вызове calc() из примера выше обе функции calc() являются устоявшими. calc(double) устояла потому, что существует стандартное преобразование типа фактического аргумента int в тип формального параметра double, а calc(SmallInt) – потому, что имеется определенное пользователем преобразование из int в SmallInt, которое использует конструктор SmallInt(int). Следовательно, наилучшей из устоявших функций будет calc(double).
А как сравниваются две последовательности определенных пользователем преобразований? Если в них используются разные конвертеры или разные конструкторы, то обе такие последовательности считаются одинаково хорошими:
class Number {
public:
operator SmallInt();
operator int();
// ...
};
extern void calc( int );
extern void calc( SmallInt );
extern Number num;
calc( num ); // ошибка: неоднозначность
Устоявшими окажутся и calc(int), и calc(SmallInt); первая – поскольку конвертер Number::operator int()преобразует фактический аргумент типа Number в формальный параметр типа int, а вторая потому, что конвертер Number::operator SmallInt() преобразует фактический аргумент типа Number в формальный параметр типа SmallInt. Так как последовательности определенных пользователем преобразований всегда имеют одинаковый ранг, то компилятор не может выбрать, какая из них лучше. Таким образом, этот вызов функции неоднозначен и приводит к ошибке компиляции.
Есть способ разрешить неоднозначность, указав преобразование явно:
// явное указание преобразования устраняет неоднозначность
calc( static_cast< int >( num ) );
Явное приведение типов заставляет компилятор преобразовать аргумент num в тип int с помощью конвертера Number::operator int(). Фактический аргумент тогда будет иметь тип int, что точно соответствует функции calc(int), которая и выбирается в качестве наилучшей.
Допустим, в классе Number не определен конвертер Number::operator int(). Будет ли тогда вызов
// определен только Number::operator SmallInt()
calc( num ); // по-прежнему неоднозначен?
по-прежнему неоднозначен? Вспомните, что в SmallInt также есть конвертер, способный преобразовать значение типа SmallInt в int.
class SmallInt {
public:
operator int();
// ...
};
Можно предположить, что функция calc() вызывается, если сначала преобразовать фактический аргумент num из типа Number в тип SmallInt с помощью конвертера Number::operator SmallInt(), а затем результат привести к типу int с помощью SmallInt::operator SmallInt(). Однако это не так. Напомним, что в последовательность определенных пользователем преобразований может входит несколько стандартных преобразований, но лишь одно пользовательское. Если конвертер Number::operator int() не определен, то функция calc(int) не считается устоявшей, поскольку не существует неявного преобразования из типа фактического аргумента num в тип формального параметра int.
Поэтому в отсутствие конвертера Number::operator int() единственной устоявшей функцией будет calc(SmallInt), в пользу которой и разрешается вызов.
Если в двух последовательностях определенных пользователем преобразований употребляется один и тот же конвертер, то выбор наилучшей зависит от последовательности стандартных преобразований, выполняемых после его вызова:
class SmallInt {
public:
operator int();
// ...
};
void manip( int );
void manip( char );
SmallInt si ( 68 );
main() {
manip( si ); // вызывается manip( int )
}
Как manip(int), так и manip(char) являются устоявшими функциями; первая – потому, что конвертер SmallInt::operator int() преобразует фактический аргумент типа SmallInt в тип формального параметра int, а вторая – потому, что тот же конвертер преобразует SmallInt в int, после чего результат с помощью стандартного преобразования приводится к типу char. Последовательности определенных пользователем преобразований выглядят так:
manip(int) : operator int()->точное соответствие
manip(int) : operator int()->стандартное преобразование
Поскольку в обеих последовательностях используется один и тот же конвертер, то для определения лучшей из них анализируется ранг последовательности стандартных преобразований. Так как точное соответствие лучше преобразования, то наилучшей из устоявших будет функция manip(int).
Подчеркнем, что такой критерий выбора принимается только тогда, когда в обеих последовательностях определенных пользователем преобразований применяется один и тот же конвертер. Этим наш пример отличается от приведенных в конце раздела 15.9, где мы показывали, как компилятор выбирает пользовательское преобразование некоторого значения в данный целевой тип: исходный и целевой типы были фиксированы, и компилятору приходилось выбирать между различными определенными пользователем преобразованиями одного типа в другой. Здесь же рассматриваются две разных функции с разными типами формальных параметров, и целевые типы отличаются. Если для двух разных типов параметров нужны различные определенные пользователем преобразования, то предпочесть один тип другому возможно только в том случае, когда в обеих последовательностях используется один и тот же конвертер. Если это не так, то для выбора наилучшего целевого типа оцениваются стандартные преобразования, следующие за применением конвертера. Например:
class SmallInt {
public:
operator int();
operator float();
// ...
};
void compute( float );
void compute( char );
SmallInt si ( 68 );
main() {
compute( si ); // неоднозначность
}
И compute(float), и compute(int) – устоявшие функции. compute(float) – потому, что конвертер SmallInt::operator float()преобразует аргумент типа SmallInt в тип параметра float, а compute(char) – потому, что SmallInt::operator int() преобразует аргумент типа SmallInt в тип int, после чего результат стандартно приводится к типу char. Таким образом, имеются последовательности:
compute(float) : operator float()->точное соответствие
compute(char) : operator char()->стандартное преобразование
Поскольку в них применяются разные конвертеры, то невозможно определить, у какой функции формальные параметры лучше соответствуют вызову. Для выбора лучшей из двух ранг последовательности стандартных преобразований не используется. Вызов помечается компилятором как неоднозначный.
Упражнение 15.12
В классах стандартной библиотеки C++ нет определений конвертеров, а большинство конструкторов, принимающих один параметр, объявлены явными. Однако определено множество перегруженных операторов. Как вы думаете, почему при проектировании было принято такое решение?
Упражнение 15.13
Почему перегруженный оператор ввода для класса SmallInt, определенный в начале этого раздела, реализован не так:
istream& operator>>( istream &is, SmallInt &si )
{
return ( is >> is.value );
}
Упражнение 15.14
Приведите возможные последовательности определенных пользователем преобразований для следующих инициализаций. Каким будет результат каждой инициализации?
class LongDouble {
operator double();
operator float();
};
extern LongDouble ldObj;
(a) int ex1 = ldObj;
(b) float ex2 = ldObj;
Упражнение 15.15
Назовите три множества функций-кандидатов, рассматриваемых при разрешении перегрузки функции в случае, когда хотя бы один ее аргумент имеет тип класса.
Упражнение 15.16
Какая из функций calc() выбирается в качестве наилучшей из устоявших в данном случае? Покажите последовательности преобразований, необходимых для вызова каждой функции, и объясните, почему одна из них лучше другой.
class LongDouble {
public:
LongDouble( double );
// ...
};
extern void calc( int );
extern void calc( LongDouble );
double dval;
int main() {
calc( dval ); // какая функция?
}
Раскрутка стека
Поиск catch-обработчикадля возбужденного исключения происходит следующим образом. Когда выражение throw находится в try-блоке, все ассоциированные с ним предложения catch исследуются с точки зрения того, могут ли они обработать исключение. Если подходящее предложение catch найдено, то исключение обрабатывается. В противном случае поиск продолжается в вызывающей функции. Предположим, что вызов функции, выполнение которой прекратилось в результате исключения, погружен в try-блок; в такой ситуации исследуются все предложения catch, ассоциированные с этим блоком. Если один из них может обработать исключение, то процесс заканчивается. В противном случае переходим к следующей по порядку вызывающей функции. Этот поиск последовательно проводится во всей цепочке вложенных вызовов. Как только будет найдено подходящее предложение, управление передается в соответствующий обработчик.
В нашем примере первая функция, для которой нужен catch-обработчик,– это функция-член pop() класса iStack. Поскольку выражение throw внутри pop() не находится в try-блоке, то программа покидает pop(), не обработав исключение. Следующей рассматривается функция, вызвавшая pop(), то есть main(). Вызов pop() внутри main() находится в try-блоке, и далее исследуется, может ли хотя бы одно ассоциированное с ним предложение catch обработать исключение. Поскольку обработчик исключения popOnEmpty имеется, то управление попадает в него.
Процесс, в результате которого программа последовательно покидает составные инструкции и определения функций в поисках предложения catch, способного обработать возникшее исключение, называется раскруткой стека. По мере раскрутки прекращают существование локальные объекты, объявленные в составных инструкциях и определениях функций, из которых произошел выход. C++ гарантирует, что во время описанного процесса вызываются деструкторы локальных объектов классов, хотя они исчезают из-за возбужденного исключения. (Подробнее мы поговорим об этом в главе 19.)
Если в программе нет предложения catch, способного обработать исключение, оно остается необработанным. Но исключение – это настолько серьезная ошибка, что программа не может продолжать выполнение. Поэтому, если обработчик не найден, вызывается функция terminate() из стандартной библиотеки C++. По умолчанию terminate() активизирует функцию abort(), которая аномально завершает программу. (В большинстве ситуаций вызов abort() оказывается вполне приемлемым решением. Однако иногда необходимо переопределить действия, выполняемые функцией terminate(). Как это сделать, рассказывается в книге [STROUSTRUP97].)
Вы уже, наверное, заметили, что обработка исключений и вызов функции во многом похожи. Выражение throw ведет себя аналогично вызову, а предложение catch чем-то напоминает определение функции. Основная разница между этими двумя механизмами заключается в том, что информация, необходимая для вызова функции, доступна во время компиляции, а для обработки исключений – нет. Обработка исключений в C++ требует языковой поддержки во время выполнения. Например, для обычного вызова функции компилятору в точке активизации уже известно, какая из перегруженных функций будет вызвана. При обработке же исключения компилятор не знает, в какой функции находится catch-обработчик и откуда возобновится выполнение программы. Функция terminate() предоставляет механизм времени выполнения, который извещает пользователя о том, что подходящего обработчика не нашлось.
Раскрутка стека и вызов деструкторов
Когда возбуждается исключение, поиск его catch-обработчика– раскрутка стека – начинается с функции, возбудившей исключение, и продолжается вверх по цепочке вложенных вызовов (см. раздел 11.3).
Во время раскрутки поочередно происходят аномальные выходы из просмотренных функций. Если функция захватила некоторый ресурс (например, открыла файл или выделила из хипа память), он в таком случае не освобождается.
Существует прием, позволяющий решить эту проблему. Всякий раз, когда во время поиска обработчика происходит выход из составной инструкции или блока, где определен некоторый локальный объект, для этого объекта автоматически вызывается деструктор. (Локальные объекты рассматривались в разделе 8.1.)
Например, следующий класс инкапсулирует выделение памяти для массива целых в конструкторе и ее освобождение в деструкторе:
class PTR {
public:
PTR() { ptr = new int[ chunk ]; }
~PTR { delete[] ptr; }
private:
int *ptr;
};
Локальный объект такого типа создается в функции manip() перед вызовом mathFunc():
void manip( int parm ) {
PTR localPtr;
// ...
mathFunc( parm ); // возбуждает исключение divideByZero
// ...
}
Если mathFunc() возбуждает исключение типа divideByZero, то начинается раскрутка стека. В процессе поиска подходящего catch-обработчика проверяется и функция manip(). Поскольку вызов mathFunc() не заключен в try-блок, то manip() нужного обработчика не содержит. Поэтому стек раскручивается дальше по цепочке вызовов. Но перед выходом из manip() с необработанным исключением процесс раскрутки уничтожает все объекты типа классов, которые локальны в ней и были созданы до вызова mathFunc(). Таким образом, локальный объект localPtr уничтожается до того, как поиск пойдет дальше, а следовательно, память, на которую он указывает, будет освобождена и утечки не произойдет.
Поэтому говорят, что процесс обработки исключений в C++ поддерживает технику программирования, основной принцип которой можно сформулировать так: “захват ресурса – это инициализация; освобождение ресурса – это уничтожение”. Если ресурс реализован в виде класса и, значит, действия по его захвату сосредоточены в конструкторе, а действия по освобождению – в деструкторе (как, например, в классе PTR выше), то локальный для функции объект такого класса автоматически уничтожается при выходе из функции в результате необработанного исключения. Действия, которые должны быть выполнены для освобождения ресурса, не будут пропущены при раскрутке стека, если они инкапсулированы в деструкторы, вызываемые для локальных объектов.
Класс auto_ptr, определенный в стандартной библиотеке (см. раздел 8.4), ведет себя почти так же, как наш класс PTR. Это средство для инкапсуляции выделения памяти в конструкторе и ее освобождения в деструкторе. Если для выделения одиночного объекта из хипа используется auto_ptr, то гарантируется, что при выходе из составной инструкции или функции из-за необработанного исключения память будет освобождена.
Разработка перегруженных операторов
Операторы присваивания, взятия адреса и оператор “запятая” имеют предопределенный смысл, если операндами являются объекты типа класса. Но их можно и перегружать. Семантика всех остальных операторов, когда они применяются к таким операндам, должна быть явно задана разработчиком. Выбор предоставляемых операторов зависит от ожидаемого использования класса.
Начинать следует с определения его открытого интерфейса. Набор открытых функций-членов формируется с учетом операций, которые класс должен предоставлять пользователям. Затем принимается решение, какие функции стоит реализовать в виде перегруженных операторов.
После определения открытого интерфейса класса проверьте, есть ли логическое соответствие между операциями и операторами:
isEmpty() становится оператором “ЛОГИЧЕСКОЕ НЕ”, operator!().
isEqual() становится оператором равенства, operator==().
copy() становится оператором присваивания, operator=().
У каждого оператора есть некоторая естественная семантика. Так, бинарный + всегда ассоциируется со сложением, а его отображение на аналогичную операцию с классом может оказаться удобной и краткой нотацией. Например, для матричного типа сложение двух матриц является вполне подходящим расширением бинарного плюса.
Примером неправильного использования перегрузки операторов является определение operator+() как операции вычитания, что бессмысленно: не согласующаяся с интуицией семантика опасна.
Такой оператор одинаково хорошо поддерживает несколько различных интерпретаций. Безупречно четкое и обоснованное объяснение того, что делает operator+(), вряд ли устроит пользователей класса String, полагающих, что он служит для конкатенации строк. Если семантика перегруженного оператора неочевидна, то лучше его не предоставлять.
Эквивалентность семантики составного оператора и соответствующей последовательности простых операторов для встроенных типов (например, эквивалентность оператора +, за которым следует =, и составного оператора +=) должна быть явно поддержана и для класса. Предположим, для String определены как operator+(), так и operator=() для поддержки операций конкатенации и почленного копирования:
String s1( "C" );
String s2( "++" );
s1 = s1 + s2; // s1 == "C++"
Но этого недостаточно
для поддержки составного оператора присваивания
s1 += s2;
Его следует определить явно, так, чтобы он поддерживал ожидаемую семантику.
Упражнение 15.1
Почему при выполнении следующего сравнения не вызывается перегруженный оператор operator==(const String&, const String&):
"cobble" == "stone"
Упражнение 15.2
Напишите перегруженные операторы неравенства, которые могут быть использованы в таких сравнениях:
String != String
String != С-строка
C-строка != String
Объясните, почему вы решили реализовать один или несколько операторов.
Упражнение 15.3
Выявите те функции-члены класса Screen, реализованного в главе 13 (разделы 13.3, 13.4 и 13.6), которые можно перегружать.
Упражнение 15.4
Объясните, почему перегруженные операторы ввода и вывода, определенные для класса String из раздела 3.15, объявлены как глобальные функции, а не функции-члены.
Упражнение 15.5
Реализуйте перегруженные операторы ввода и вывода для класса Screen из главы 13.
Разрешение имен в области видимости класса
Конечно, имена, используемые в области видимости класса, не обязаны быть именами членов класса. В процессе разрешения в этой области ведется поиск имен, объявленных и в других областях. Если имя, употребленное в области видимости класса, не разрешается именем члена класса, то компилятор ищет его в областях, включающих определение класса или члена. В этом подразделе мы покажем, как разрешаются имена, встречающиеся в области видимости класса.
Имя, использованное внутри определения класса (за исключением определений встроенных функций-членов и аргументов по умолчанию), разрешается следующим образом:
1. Просматриваются объявления членов класса, появляющиеся перед употреблением имени.
2. Если на шаге 1 разрешение не привело к успеху, то просматриваются объявления в пространстве имен перед определением класса. Напомним, что глобальная область видимости – это тоже область видимости пространства имен. (О пространствах имен речь шла в разделе 8.5.)
Например:
typedef double Money;
class Account {
// ...
private:
static Money _interestRate;
static Money initInterest();
// ...
};
Сначала компилятор ищет объявление Money в области видимости класса Account. При этом учитываются только те объявления, которые встречаются перед использованием Money. Поскольку таких объявлений нет, далее поиск ведется в глобальной области видимости. Объявление глобального typedef Money найдено, именно этот тип и используется в объявлениях _interestRate и initInterest().
Имя, встретившееся в определении функции-члена класса, разрешается следующим образом:
1. Сначала просматриваются объявления в локальных областях видимости функции-члена. (О локальных областях видимости и локальных объявлениях говорилось в разделе 8.1.)
2. Если шаг 1 не привел к успеху, то просматриваются объявления для всех членов класса.
3. Если и этого оказалось недостаточно, просматриваются объявления в пространстве имен перед определением функции-члена.
class Screen {
public:
// ...
void setHeight( int );
private:
short _height;
};
int verify(int);
void Screen::setHeight( int var ) {
// var: относится к параметру
// _height: относится к члену класса
// verify: относится к глобальной функции
_height = verify( var );
}
Обратите внимание, что объявление глобальной функции verify() невидимо до определения класса Screen. Однако на третьем шаге разрешения имени просматриваются объявления в областях видимости пространств имен, видимые перед определением члена, поэтому нужное объявление обнаруживается.
Имя, встретившееся в определении статического члена класса, разрешается следующим образом:
1. Просматриваются объявления всех членов класса.
2. Если шаг 1 не привел к успеху, то просматриваются объявления, расположенные в областях видимости пространств имен перед определением статического члена, а не только предшествующие определению класса.
Упражнение 13.18
Назовите те части программы, которые находятся в области видимости класса.
Упражнение 13.19
Назовите те части программы, которые находятся в области видимости класса и для которых при разрешении имен просматривается полная область (т.е. принимаются во внимание все члены, объявленные в теле класса).
Упражнение 13.20
К каким объявлениям относится имя Type при использовании в теле класса Exersise и в определении его функции-члена setVal()? (Напоминаем, что разные вхождения могут относиться к разным объявлениям.) К каким объявлениям относится имя initVal при употреблении в определении функции-члена setVal()?
typedef int Type;
Type initVal();
class Exercise {
public:
// ...
typedef double Type;
Type setVal( Type );
Type initVal();
private:
int val;
};
Type Exercise::setVal( Type parm ) {
val = parm + initVal();
}
Определение функции-члена setVal() ошибочно. Можете ли вы сказать, почему? Внесите необходимые изменения, чтобы в классе Exercise использовался глобальный typedef Type и глобальная функция initVal().
Разрешение имен в области видимости вложенного класса
Посмотрим, как разрешаются имена в определениях вложенного класса и его членов.
Имя, встречающееся в определении вложенного класса (кроме тех, которые употребляются во встроенных функциях-членах и аргументах по умолчанию) разрешается следующим образом:
1. Просматриваются члены вложенного класса, расположенные перед употреблением имени.
2. Если шаг 1 не привел к успеху, то просматриваются объявления членов объемлющего класса, расположенные перед употреблением имени.
3. Если и этого недостаточно, то просматриваются объявления, расположенные в области видимости пространства имен перед определением вложенного класса.
Например:
enum ListStatus { Good, Empty, Corrupted };
class List {
public:
// ...
private:
class ListItem {
public:
// Смотрим в:
// 1) List::ListItem
// 2) List
// 3) глобальной области видимости
ListStatus status; // относится к глобальному перечислению
// ...
};
// ...
};
Сначала компилятор ищет объявление ListStatus в области видимости класса ListItem. Поскольку его там нет, поиск продолжается в области видимости List, а затем в глобальной. При этом во всех трех областях просматриваются только объявления, предшествующие использованию ListStatus. В конце концов находится глобальное объявление перечисления ListStatus – оно и будет типом, использованным в объявлении status.
Если вложенный класс ListItem определен в глобальной области видимости, вне тела объемлющего класса List, то все члены List уже были объявлены:
class List {
private:
class ListItem {
//...
public:
enum ListStatus { Good, Empty, Corrupted };
// ...
};
class List::ListItem {
public:
// Смотрим в:
// 1) List::ListItem
// 2) List
// 3) глобальной области видимости
ListStatus status; // относится к глобальному перечислению
// ...
};
При разрешении имени ListStatus сначала просматривается область видимости класса ListItem. Поскольку там его нет, поиск продолжается в области видимости List. Так как полное определение класса List уже встречалось, просматриваются все члены этого класса. Вложенное перечисление ListStatus найдено несмотря даже на то, что оно объявлено после объявления ListItem. Таким образом, status объявляется как указатель на данное перечисление в классе List. Если бы в List не было члена с таким именем, поиск был бы продолжен в глобальной области видимости среди тех объявлений, которые предшествуют определению класса ListItem.
Имя, встретившееся в определении функции- члена вложенного класса, разрешается следующим образом:
1. Сначала просматриваются локальные области видимости функции-члена.
2. Если шаг 1 не привел к успеху, то просматриваются объявления всех членов вложенного класса.
3. Если имя еще не найдено, то просматриваются объявления всех членов объемлющего класса.
4. Если и этого недостаточно, то просматриваются объявления, появляющиеся в области видимости пространства имен перед определением функции-члена.
Какое объявление относится к имени list в определении функции-члена check_status() в следующем фрагменте кода:
class List {
public:
enum ListStatus { Good, Empty, Corrupted };
// ...
private:
class ListItem {
public:
void check_status();
ListStatus status; // правильно
//...
};
ListItem *list;
};
int list = 0;
void List::ListItem::check_status()
{
int value = list; // какой list?
}
Весьма вероятно, что при использовании list внутри check_status() программист имел в виду глобальный объект:
и value, и глобальный объект list имеют тип int. Член List::list объявлен как указатель и не может быть присвоен value без явного приведения типа;
ListItem не имеет прав доступа к закрытым членам объемлющего класса, в частности list;
list – это нестатический член, и обращение к нему в функциях-членах ListItem должно производиться через объект, указатель или ссылку.
Однако, несмотря на все это, имя list, встречающееся в функции-члене check_status(), разрешается в пользу члена list класса List. Напоминаем, что если имя не найдено в области видимости вложенного ListItem, то далее просматривается область видимости объемлющего класса, а не глобальная. Член list в List скрывает глобальный объект. А так как использование указателя list в check_status() недопустимо, то выводится сообщение об ошибке.
Права доступа и совместимость типов проверяются только после того, как имя разрешено. Если при этом обнаруживается ошибка, то выдается сообщение о ней и дальнейший поиск объявления, которое было бы лучше согласовано с именем, уже не производится. Для доступа к глобальному объекту list следует использовать оператор разрешения области видимости:
void List::ListItem::check_status()
{
int value = ::list; // правильно
}
Если бы функция-член check_status() была определена как встроенная в теле класса ListItem, то последнее объявление привело бы к выдаче сообщения об ошибке из-за того, что имя list не объявлено в глобальной области видимости:
class List {
public:
// ...
private:
class ListItem {
public:
// ошибка: нет видимого объявления для ::list
void check_status() { int value = ::lis; }
//...
};
ListItem *list;
// ...
};
int list = 0;
Глобальный объект list объявлен после определения класса List. Во встроенной функции-члене, определенной внутри тела класса, рассматриваются только те глобальные объявления, которые были видны перед определением объемлющего класса. Если же определение check_status() следует за определением List, то рассматриваются глобальные объявления, расположенные перед ним, поэтому будет найдено глобальное определение объекта list.
Упражнение 13.21
В главе 11 был приведен пример программы, использующей класс iStack. Измените его, объявив классы исключений pushOnFull и popOnEmpty открытыми вложенными в iStack. Модифицируйте соответствующим образом определение класса iStack и его функций-членов, а также определение main().
Разрешение имен в определениях шаблонов *
Внутри определения шаблона смысл некоторых конструкций может различаться в зависимости от конкретизации, тогда как смысл других всегда остается неизменным. Главную роль играет наличие в конструкции формального параметра шаблона:
template <typename Type>
Type min( Type* array, int size )
{
Type min_val = array[0];
for (int i = 1; i < size; ++i)
if ( array[i] < min_val )
min_val = array[i];
print( "Minimum value found: ");
print( min_val );
return min_val;
}
В функции min() типы переменных array и min_val зависят от фактического типа, которым будет заменен Type при конкретизации шаблона, тогда как тип переменной size останется int при любом типе параметра шаблона. Следовательно, типы array и min_val в разных конкретизациях различны. Поэтому мы говорим, что типы этих переменных зависят от параметра шаблона, тогда как тип size от него не зависит.
Так как тип min_val неизвестен, то неизвестна и операция, которая будет использоваться при появлении min_val в выражении. Например, какая функция print() будет вызвана при обращении print(min_val)? С типом аргумента int? Или float? Будет ли вызов ошибочным, поскольку не существует функции, которая может быть вызвана с аргументом того же типа, что и min_val? Принимая все это во внимание, мы говорим, что и вызов print(min_val) зависит от параметра шаблона.
Такие вопросы не возникают для тех конструкций внутри min(), которые не зависят от параметров шаблона. Например, всегда известно, какая функция должна быть вызвана для print( "Minimum value found: "). Это функция печати строк символов. В данном случае print() остается одной и той же при любой конкретизации шаблона, то есть не зависит от его параметров.
В главе 7 мы видели, что в C++ функция должна быть объявлена до ее вызова. Нужно ли объявлять функцию, вызываемую внутри шаблона, до того, как компилятор увидит его определение? Должны ли мы объявить функцию print() в предыдущем примере до определения шаблона min()? Ответ зависит от особенностей имени, на которое мы ссылаемся. Конструкцию, не зависящую от параметров шаблона, следует объявить перед ее использованием в шаблоне. Представленное выше определение шаблона функции min() некорректно. Поскольку вызов
print( "Minimum value found: ");
не зависит от параметров шаблона, то функция print() для печати строк символов должна быть объявлена до использования. Чтобы исправить эту ошибку, можно поместить объявление print() перед определением min():
// ---- primer.h ----
// это объявление необходимо:
// внутри min() вызывается print( const char * )
void print( const char * );
template <typename Type>
Type min( Type* array, int size ) {
// ...
print( "Minimum value found: ");
print( min_val );
return min_val;
}
С другой стороны, объявление функции print(), используемой для печати min_val, пока не нужно, так как еще неизвестно, какую конкретно функцию надо искать. Мы не знаем, какая функция print() будет вызвана при обращении print(min_val), пока тип min_val не станет известным.
Когда же должна быть объявлена функция print(), вызываемая при обращении print(min_val)? До конкретизации шаблона. Например:
#include <primer.h>
void print( int );
int ai[4] = {12, 8, 73, 45 };
int main() {
int size = sizeof(ai) / sizeof(int);
// конкретизируется min( int*, int )
min( &ai[0], size );
}
main() вызывает конкретизированную из шаблона функцию min(int*,int). В этой реализации Type заменено int, и тип переменной min_val, следовательно, равен int. Поэтому при обращении print(min_val) вызывается функция с аргументом типа int. Именно тогда, когда конкретизируется min(int*,int), становится известно, что при втором вызове аргумент print() имеет тип int. В этот момент такая функция должна быть видима. Если бы функция print(int) не была объявлена до конкретизации min(int*,int), то компилятор выдал бы сообщение об ошибке.
Поэтому разрешение имен в определении шаблона происходит в два этапа. Сначала разрешаются имена, не зависящие от его параметров, а затем, при конкретизации, – имена, зависящие от параметров.
Но зачем нужны два шага? Почему бы, например, не разрешать все имена при конкретизации?
Если вы проектируете шаблон функции, то, вероятно, хотели бы сохранить контроль над тем, когда разрешаются имена в его определении. Предположим, что шаблон min() – это часть библиотеки, в которой определены и другие шаблоны и функции. Желательно, чтобы реализации min() по возможности использовали другие компоненты нашей же библиотеки. В предыдущем примере интерфейс библиотеки определен в заголовочном файле <primer.h>. Как объявление функции print(const char*), так и определение функции min() являются частями интерфейса. Мы хотим, чтобы конкретизации шаблона min() пользовались функцией print() из нашей библиотеки. Первый этап разрешения имени это гарантирует. Если имя, использованное в определении шаблона, не зависит от его параметров, то оно обязательно будет относиться к компоненту внутри библиотеки, т.е. к тому объявлению, которое включено в один пакет с этим определением в заголовочном файле <primer.h>.
На самом деле автор шаблона должен позаботиться о том, чтобы были объявлены все имена, использованные в определениях и не зависящие от параметров. Если этого нет, то определение шаблона вызовет ошибку. При конкретизации шаблона компилятор ее не исправляет:
// ---- primer.h ----
template <typename Type>
Type min( Type* array, int size )
{
Type min_val = array[0];
// ...
// ошибка: функция print( const char* ) не найдена
print( "Minimum value found: " );
// правильно: зависит от параметра шаблона
print( min_val );
// ...
}
// ---- user.C ----
#include <primer.h>
// это объявление print( const char* ) игнорируется
void print( const char* );
void print( int );
int ai[4] = {12, 8, 73, 45 };
int main() {
int size = sizeof(ai) / sizeof(int);
// конкретизируется min( int*, int )
min( &ai[0], size );
}
Объявление функции print( const char* ) в файле user.C невидимо в том месте, где появляется определение шаблона. Однако оно видимо там, где конкретизируется шаблон min(int*,int), но это объявление не рассматривается при компиляции вызова print("Minimum value found: "), так как последний не зависит от параметров шаблона. Если некоторая конструкция в определении шаблона не зависит от его параметров, то имена разрешаются в контексте самого определения, и результат разрешения в дальнейшем не пересматривается. Поэтому на программиста возлагается ответственность за то, чтобы объявления имен, встречающихся в определении, были включены в интерфейс библиотеки вместе с шаблоном.
А теперь предположим, что библиотека была написана кем-то другим, а мы ее пользователи, которым доступен интерфейс, определенный в заголовочном файле <primer.h>. Иногда нужно, чтобы объекты и функции, определенные в нашей программе, учитывались при конкретизации шаблона из библиотеки. Допустим, мы определили в своей программе класс SmallInt и хотели бы конкретизировать функцию min() из библиотеки <primer.h> для получения минимального значения в массиве объектов типа SmallInt.
При конкретизации шаблона min() для массива объектов типа SmallInt вместо аргумента шаблона Type подставляется тип SmallInt. Следовательно, min_val в конкретизированной функции min() имеет тот же тип. Тогда как разрешится вызов функции print(min_val)?
// ---- user.h ----
class SmallInt { /* ... */ }
void print( const SmallInt & );
// ---- user.C ----
#include <primer.h>
#include "user.h"
SmallInt asi[4];
int main() {
// задать значения элементов массива asi
// конкретизируется min( SmallInt*, int )
// int size = sizeof(asi) / sizeof(SmallInt);
min( &asi[0], size );
}
Это нормально: мы хотим, чтобы учитывалась именно наша функция print(const SmallInt &). Рассмотрения функций, определенных в библиотеке <primer.h>, недостаточно. Второй шаг разрешения имени гарантирует, что если имя, использованное в определении, зависит от параметров шаблона, то принимаются во внимание имена, объявленные в контексте конкретизации. Поэтому можно быть уверенным, что функции, умеющие манипулировать объектами типа SmallInt, попадут в поле зрения компилятора при анализе шаблона, которому в качестве аргумента передан тип SmallInt.
Место в программе, где происходит конкретизация шаблона, называется точкой конкретизации. Знание этой точки важно потому, что она определяет, какие объявления учитывает компилятор для имен, зависящих от параметров шаблона. Такая точка всегда находится в области видимости пространства имен и следует за функцией, внутри которой произошла конкретизация. Например, точка конкретизации min(SmallInt*,int) расположена сразу после функции main() в области видимости пространства имен:
// ...
int main() {
// ...
// использование min(SmallInt*,int)
min( &asi[0], size );
}
// точка конкретизации min(SmallInt*,int)
// как будто объявление конкретизированной функции выглядит так:
SmallInt min( SmallInt* array, int size )
{ /* ... */ }
Но что, если конкретизация шаблона случается в одном исходном файле несколько раз? Где тогда будет точка конкретизации? Вы можете спросить: “А какая, собственно, разница?” В нашем примере для SmallInt разница есть, поскольку объявление функции print(const SmallInt &) должно появиться перед точкой конкретизации min(SmallInt*,int):
#include <primer.h>
void another();
SmallInt asi[4];
int main() {
// задать значения элементов массива asi
int size = sizeof(asi) / sizeof(SmallInt);
min( &asi[0], size );
another();
// ...
}
// точка конкретизации здесь?
void another() {
int size = sizeof(asi) / sizeof(SmallInt);
min( &asi[0], size );
}
// или здесь?
В действительности точка конкретизации находится после определения каждой функции, в которой используется конкретизированный экземпляр. Компилятор может выбрать любую из этих точек, чтобы конкретизировать в ней шаблон. Отсюда следует, что при организации кода программы надо быть внимательным и помещать все объявления, необходимые для разрешения имен, зависящих от параметров некоторого шаблона, перед первой точкой. Поэтому разумно поместить их в заголовочный файл, который включается перед любой возможной конкретизацией шаблона:
#include <primer.h>
// user.h содержит объявления, необходимые при конкретизации
#include "user.h"
void another();
SmallInt asi[4];
int main() {
// ...
}
// первая точка конкретизации min(SmallInt*,int)
void another() {
// ...
}
// вторая точка конкретизации min(SmallInt*,int)
А если конкретизация шаблона происходит в нескольких файлах? Например, что будет, если функция another() находится в другом файле, нежели main()? Тогда точка конкретизации есть в каждом файле, где используется конкретизированная из шаблона функция. Компилятор свободен в выборе любой из них, так что нам снова придется проявить аккуратность и включить файл "user.h" во все исходные файлы, где используются конкретизированные функции. Тем самым гарантируется, что реализация min(SmallInt*,int) будет ссылаться именно на нашу функцию print(const SmallInt &) вне зависимости от того, какую из точек конкретизации выберет компилятор.
Упражнение 10.13
Назовите два шага разрешения имени в определениях шаблона. Объясните, каким образом первый шаг отвечает потребностям разработчика библиотеки, а второй обеспечивает гибкость, необходимую пользователям шаблонов.
Упражнение 10.14
На какие объявления ссылаются имена display и SIZE в реализации max(LongDouble*,SIZE)?
// ---- exercise.h ----
void display( const void* );
typedef unsigned int SIZE;
template <typename Type>
Type max( Type* array, SIZE size )
{
Type max_val = array[0];
for ( SIZE i = 1; i < size; ++i )
if ( array[i] > max_val )
max_val = array[i];
display( "Maximum value found: " );
display( max_val );
return max_val;
}
// ---- user.h ----
class LongDouble { /* ... */ };
void display( const LongDouble & );
void display( const char * );
typedef int SIZE;
// ---- user.C ----
#include <exercize.h>
#include "user.h"
LongDouble ad[7];
int main() {
// задать значения элементов массива ad
// конкретизируется max( LongDouble*, SIZE )
SIZE size = sizeof(ad) / sizeof(LongDouble);
max( &ad[0], size );
}
Разрешение имен в шаблонах классов *
При обсуждении разрешения имен в шаблонах функций (см. раздел 10.9) мы уже говорили о том, что этот процесс выполняется в два шага. Так же разрешаются имена и в определениях шаблонов классов и их членов. Каждый шаг относится к разным видам имен: первый– к тем, которые имеют один и тот же смысл во всех экземплярах шаблона, а второй – к тем, которые потенциально могут иметь разный смысл в разных экземплярах. Рассмотрим несколько примеров, где используется функция-член remove() шаблона класса Queue:
// Queue.h:
#include <iostream>
#include <cstdlib>
// определение класса Queue
template <class Type>
Type Queue<Type>::remove() {
if ( is_empty() ) {
cerr << "remove() вызвана для пустой очереди\n";
exit(-1);
}
QueueItem<Type> *pt = front;
front = front->next;
Type retval = pt->item;
delete pt;
cout << "удалено значение: ";
cout << retval << endl;
return retval;
}
В выражении
cout << retval << endl;
переменная retval имеет тип Type, и ее фактический тип неизвестен до конкретизации функции-члена remove(). То, какой оператор operator<<() будет выбран, зависит от фактического типа retval, подставленного вместо Type. При разных конкретизациях remove() могут вызываться разные operator<<(). Поэтому мы говорим, что выбранный оператор вывода зависит от параметра шаблона.
Однако для вызова функции exit() ситуация иная. Ее фактическим аргументом является литерал, значение которого одинаково при всех конкретизациях remove(). Поскольку при обращении к функции не используются аргументы, типы которых зависят от параметра шаблона Type, гарантируется, что всегда будет вызываться exit(), объявленная в заголовочном файле cstdlib. По той же причине в выражении
cout << "удалено значение: ";
всегда вызывается глобальный оператор
ostream& operator<<( ostream &, const char * );
Аргумент "удалено значение: " – это C-строка символов, и ее тип не зависит от параметра шаблона Type. Поэтому в любом конкретизированном экземпляре remove()употребление operator<<() имеет одинаковый смысл. Один и тот же смысл во всех конкретизациях шаблона имеют те конструкции, которые не зависят от параметров шаблона.
Таким образом, два шага разрешения имени в определениях шаблонов классов или их членов состоят в следующем:
Имена, не зависящие от параметров шаблона, разрешаются во время его определения.
Имена, зависящие от параметров шаблона, разрешаются во время его конкретизации.
Такой подход удовлетворяет требованиям как разработчика класса, так и его пользователя. Например, разработчикам необходимо управлять процессом разрешения имен. Если шаблон класса входит в состав библиотеки, в которой определены также другие шаблоны и функции, то желательно, чтобы при конкретизации шаблона класса и его членов по возможности применялись именно библиотечные компоненты. Это гарантирует первый шаг разрешения имени. Если использованное в определении шаблона имя не зависит от параметров шаблона, то оно разрешается в результате просмотра всех объявлений, видимых в заголовочном файле, включенном перед определением шаблона.
Разработчик класса должен позаботиться о том, чтобы были видимы объявления всех не зависящих от параметров шаблона имен, употребленных в его определении. Если объявление такого имени не найдено, то определение шаблона считается ошибочным. Если бы перед определением функции-члена remove() в шаблоне класса Queue не были включены файлы iostream и cstdlib, то в выражении
cout << "удалено значение: ";
и при компиляции вызова функции exit() были бы обнаружены ошибки.
Второй шаг разрешения имени необходим, если поиск производится среди функций и операторов, зависящих от типа, которым конкретизирован шаблон. Например, если шаблон класса Queue конкретизируется типом класса LongDouble (см. раздел 16.9), то желательно, чтобы внутри функции-члена remove()в следующем выражении
cout << retval << endl;
вызывался оператор operator<<(), ассоциированный с классом LongDouble:
#include "Queue.h"
#include "ldouble.h"
// содержит:
// class LongDouble { ... };
// ostream& operator<<( ostream &, const LongDouble & );
int main() {
// конкретизация Queue<LongDouble>
Queue<LongDouble> *qld = new Queue<LongDouble>;
// конкретизация Queue<LongDouble>::remove()
// вызывает оператор вывода для LongDouble
qld->remove();
// ...
}
Место в программе, где происходит конкретизация шаблона, называется точкой конкретизации. Она определяет, какие объявления принимаются компилятором во внимание для имен, зависящих от параметров шаблона.
Точка конкретизации шаблона всегда находится в области видимости пространства имен и непосредственно предшествует объявлению или определению, которое ссылается на конкретизированный экземпляр. Точка конкретизации функции-члена или статического члена шаблона класса всегда следует непосредственно за объявлением или определением, которое ссылается на конкретизированный член.
В предыдущем примере точка конкретизации Queue<LongDouble> находится перед main(), и при разрешении зависящих от параметров имен, которые используются в определении шаблона Queue, компилятор просматривает все объявления до этой точки. Аналогично при таком разрешении в определении remove() компилятор просматривает все объявления до точки конкретизации, расположенной после main().
Как отмечалось в разделе 16.2, шаблон конкретизируется, если он используется в контексте, требующем полного определения класса. Члены шаблона не конкретизируются автоматически вместе с ним, а лишь тогда, когда сами используются в программе. Поэтому точка конкретизации шаблона класса может не совпадать с точками конкретизации его членов, да и сами члены могут конкретизироваться в разных точках. Чтобы избежать ошибок, объявления имен, упоминаемых в определениях шаблона и его членов, рекомендуется помещать в заголовочные файлы, включая их перед первой конкретизацией шаблона класса или любого из его членов.
Разрешение перегрузки и функции-члены *
Функции-члены также могут быть перегружены, и в этом случае тоже применяется процедура разрешения перегрузки для выбора наилучшей из устоявших. Такое разрешение очень похоже на аналогичную процедуру для обычных функций и состоит из тех же трех шагов:
1. Отбор функций-кандидатов.
2. Отбор устоявших функций.
3. Выбор наилучшей из устоявших функции.
Однако есть небольшие различия в алгоритмах формирования множества кандидатов и отбора устоявших функций-членов. Эти различия мы и рассмотрим в настоящем разделе.
Разрешение перегрузки и наследование *
Наследование классов оказывает влияние на все аспекты разрешения перегрузки функций (см. раздел 9.2). Напомним, что эта процедура состоит из трех шагов:
1. Отбор функций-кандидатов.
2. Отбор устоявших функций.
3. Выбор наилучшей из устоявших функции.
Отбор функций-кандидатов зависит от наследования потому, что на этом шаге принимаются во внимание функции, ассоциированные с базовыми классами, – как их функции-члены, так и функции, объявленные в тех же пространствах имен, где определены базовые классы. Отбор устоявших функций также зависит от наследования, поскольку множество преобразований формальных параметров функции в фактические аргументы расширяется пользовательскими преобразованиями. Кроме того, наследование оказывает влияние на ранжирование последовательностей трансформаций аргументов, а значит, и на выбор наилучшей из устоявших функции. В данном разделе мы рассмотрим влияние наследования на эти три шага разрешения перегрузки более подробно.
Разрешение перегрузки и операторы *
В классах могут быть объявлены перегруженные операторы и конвертеры. Предположим, при инициализации встретился оператор сложения:
SomeClass sc;
int iobj = sc + 3;
Как компилятор решает, что следует сделать: вызвать перегруженный оператор для класса SomeClass или конвертировать операнд sc во встроенный тип, а затем уже воспользоваться встроенным оператором?
Ответ зависит от множества перегруженных операторов и конвертеров, определенных в SomeClass. При выборе оператора для выполнения сложения применяется процесс разрешения перегрузки функции. В данном разделе мы расскажем, как этот процесс позволяет выбрать нужный оператор, когда операндами являются объекты типа класса.
При разрешении перегрузки используется все та же процедура из трех шагов, представленная в разделе 9.2:
1. Отбор функций-кандидатов.
2. Отбор устоявших функций.
3. Выбор наилучшей из устоявших функции.
Рассмотрим эти шаги более детально.
Разрешение перегрузки функции не применяется, если все операнды имеют встроенные типы. В таком случае гарантированно употребляется встроенный оператор. (Использование операторов с операндами встроенных типов описано в главе 4.) Например:
class SmallInt {
public:
SmallInt( int );
};
SmallInt operator+ ( const SmallInt &, const SmallInt & );
void func() {
int i1, i2;
int i3 = i1 + i2;
}
Поскольку операнды i1 и i2 имеют тип int, а не тип класса, то при сложении используется встроенный оператор +. Перегруженный operator+(const SmallInt &, const SmallInt &) игнорируется, хотя операнды можно привести к типу SmallInt с помощью определенного пользователем преобразования в виде конструктора SmallInt(int). Описанный ниже процесс разрешения перегрузки в таких ситуациях не применяется.
Кроме того, разрешение перегрузки для операторов употребляется только в случае использования операторного синтаксиса:
void func() {
SmallInt si(98);
int iobj = 65;
int res = si + iobj; // использован операторный синтаксис
}
Если вместо этого использовать синтаксис вызова функции:
int res = operator+( si, iobj ); // синтаксис вызова функции
то применяется процедура разрешения перегрузки для функций в пространстве имен (см. раздел 15.10). Если же использован синтаксис вызова функции-члена:
// синтаксис вызова функции-члена
int res = si.operator+( iobj );
то работает соответствующая процедура для функций-членов (см. раздел 15.11).
Разрешение перегрузки при конкретизации *
В предыдущем разделе мы видели, что шаблон функции может быть перегружен. Кроме того, допускается использование одного и того же имени для шаблона и обычной функции:
// шаблон функции
template <class Type>
Type sum( Type, int ) { /* ... */ }
// обычная функция (не шаблон)
double sum( double, double );
Когда программа обращается к sum(), вызов разрешается либо в пользу конкретизированного экземпляра шаблона, либо в пользу обычной функции – это зависит от того, какая функция лучше соответствует фактическим аргументам. (Для решения такой проблемы применяется процесс разрешения перегрузки, описанный в главе 9.) Рассмотрим следующий пример:
void calc( int ii, double dd ) {
// что будет вызвано: конкретизированный экземпляр шаблона
// или обычная функция?
sum( dd, ii );
}
Будет ли при обращении к sum(dd,ii) вызвана функция, конкретизированная из шаблона, или обычная функция? Чтобы ответить на этот вопрос, выполним по шагам процедуру разрешения перегрузки. Первый шаг заключается в построении множества функций-кандидатов состоящего из одноименных вызванной функций, объявления которых видны в точке вызова.
Если существует шаблон функции и на основе фактических аргументов вызова из него может быть конкретизирована функция, то она будет являться кандидатом. Так ли это на самом деле, зависит от результата процесса вывода аргументов шаблона. (Этот процесс описан в разделе 10.3.) В предыдущем примере для вывода значения аргумента Type шаблона используется фактический аргумент функции dd. Тип выведенного аргумента оказывается равным double, и к множеству функций-кандидатов добавляется функция sum(double, int). Таким образом, для данного вызова имеются два кандидата: конкретизированная из шаблона функция sum(double, int) и обычная функция sum(double, double).
После того как функции, конкретизированные из шаблона, включены в множество кандидатов, процесс вывода аргументов шаблона продолжается как обычно.
Второй шаг процедуры разрешения перегрузки заключается в выборе устоявших функций из множества кандидатов. Напомним, что устоявшей называется функция, для которой существуют преобразования типов, приводящие каждый фактический аргумент функции к типу соответствующего формального параметра. (В разделе 9.3 описаны преобразования типов, применимые к фактическим аргументам функции.) Нужные трансформации существуют как для конкретизированной функции sum(double, int), так и для обычной функции sum(double, double). Следовательно, обе они являются устоявшими.
Проведем ранжирование преобразований типов, примененных к фактическим аргументам для выбора наилучшей из устоявших функций. В нашем примере оно происходит следующим образом:
Для конкретизированной из шаблона функции sum(double, int):
для первого фактического аргумента как сам этот аргумент, так и формальный параметр имеют тип double, т.е. мы видим точное соответствие;
для второго фактического аргумента как сам аргумент, так и формальный параметр имеют тип int, т.е. снова точное соответствие.
Для обычной функции sum(double, double):
для первого фактического аргумента как сам этот аргумент, так и формальный параметр имеют тип double – точное соответствие;
для второго фактического аргумента сам этот аргумент имеет тип int, а формальный параметр – тип double, т.е. необходимо стандартное преобразование между целым и плавающим типами.
Если рассматривать только первый аргумент, то обе функции одинаково хороши. Однако для второго аргумента конкретизированная из шаблона функция лучше. Поэтому наиболее подходящей (лучшей из устоявших) считается функция sum(double, int).
Функция, конкретизированная из шаблона, включается в множество кандидатов только тогда, когда процесс вывода аргументов завершается успешно. Неудачное завершение в данном случае не является ошибкой, но кандидатом функция считаться не будет. Предположим, что шаблон функции sum() объявлен следующим образом:
// шаблон функции
template <class T>
int sum( T*, int ) { ... }
Для описанного вызова функции вывод аргументов шаблона будет неудачным, так как фактический аргумент типа double не может соответствовать формальному параметру типа T*. Поскольку для данного вызова и данного шаблона конкретизировать функцию невозможно, в множество кандидатов ничего не добавляется, т.е. единственным его элементом останется обычная функция sum(double, double). Именно она вызывается при обращении, и ее второй фактический аргумент приводится к типу double.
А если вывод аргументов шаблона завершается удачно, но для них есть явная специализация? Тогда именно она, а не функция, конкретизированная из обобщенного шаблона, попадает в множество кандидатов. Например:
// определение шаблона функции
template <class Type> Type sum( Type, int ) { /* ... */ }
// явная специализация для Type == double
template<> double sum<double>( double,int );
// обычная функция
double sum( double, double );
void manip( int ii, double dd ) {
// вызывается явная специализация шаблона sum<double>()
sum( dd, ii );
}
При обращении к sum() внутри manip() в процессе вывода аргументов шаблона обнаруживается, что функция sum(double,int), конкретизированная из обобщенного шаблона, должна быть добавлена к множеству кандидатов. Но для нее имеется явная специализация, которая и становится кандидатом. На более поздних стадиях анализа выясняется, что эта специализация дает наилучшее соответствие фактическим аргументам вызова, так что разрешение перегрузки завершается в ее пользу.
Явные специализации шаблона не включаются в множество кандидатов автоматически. Лишь в том случае, когда вывод аргументов завершается успешно, компилятор будет рассматривать явные специализации данного шаблона:
// определение шаблона функции
template <class Type>
Type min( Type, Type ) { /* ... */ }
// явная специализация для Type == double
template<> double min<double>( double, double );
void manip( int ii, double dd ) {
// ошибка: вывод аргументов шаблона неудачен,
// нет функций-кандидатов для данного вызова
min( dd, ii );
}
Шаблон функции min() специализирован для аргумента double. Однако эта специализация не попадает в множество функций-кандидатов. Процесс вывода для вызова min() завершился неудачно, поскольку аргументы шаблона, выведенные для Type на основе разных фактических аргументов функции, оказались различными: для первого аргумента выводится тип double, а для второго – int. Поскольку вывести аргументы не удалось, в множество кандидатов никакая функция не добавляется, и специализация min(double, double) игнорируется. Так как других функций-кандидатов нет, вызов считается ошибочным.
Как отмечалось в разделе 10.6, тип возвращаемого значения и список формальных параметров обычной функции может точно соответствовать аналогичным атрибутам функции, конкретизированной из шаблона. В следующем примере min(int,int) – это обычная функция, а не специализация шаблона min(), поскольку, как вы, вероятно, помните, объявление специализации должно начинаться с template<>:
// объявление шаблона функции
template <class T>
T min( T, T );
// обычная функция min(int,int)
int min( int, int ) { }
Вызов может точно соответствовать как обычной функции, так и функции, конкретизированной из шаблона. В следующем примере оба аргумента в min(ai[0],99) имеют тип int. Для этого вызова есть две устоявших функции: обычная min(int,int) и конкретизированная из шаблона функция с тем же типом возвращаемого значения и списком параметров:
int ai[4] = { 22, 33, 44, 55 };
int main() {
// вызывается обычная функция min( int, int )
min( ai[0], 99 );
}
Однако такой вызов не является неоднозначным. Обычной функции, если она существует, всегда отдается предпочтение, поскольку она реализована явно, так что перегрузка разрешается в пользу обычной функции min(int,int).
Если перегрузка разрешилась таким образом, то изменений уже не будет: если позже обнаружится, что в программе нет определения этой функции, компилятор не станет конкретизировать ее тело из шаблона. Вместо этого на этапе сборки мы получим ошибку. В следующем примере программа вызывает, но не определяет обычную функцию min(int,int), и редактор связей выдает сообщение об ошибке:
// шаблон функции
template <class T>
T min( T, T ) { ... }
// это обычная функция, не определенная в программе
int min( int, int );
int ai[4] = { 22, 33, 44, 55 };
int main() {
// ошибка сборки: min( int, int ) не определена
min( ai[0], 99 );
}
Зачем определять обычную функцию, если ее тип возвращаемого значения и список параметров соответствуют функции, конкретизированной из шаблона? Вспомните, что при вызове конкретизированной функции к ее фактическим аргументам в ходе вывода аргументов шаблона можно применять только ограниченное множество преобразований. Если же объявлена обычная функция, то для приведения типов аргументов допустимы любые трансформации, так как типы формальных параметров обычной функции фиксированы. Рассмотрим пример, показывающий, зачем может потребоваться объявить обычную функцию.
Предположим, что мы хотим определить специализацию шаблона функции min<int>(int,int). Нужно, чтобы именно эта функция вызывалась при обращении к min() с аргументами любых целых типов, пусть даже неодинаковых. Из-за ограничений, наложенных на преобразования типов, при передаче фактических аргументов разных типов функция min<int>(int,int) не будет конкретизирована из шаблона. Мы могли бы заставить компилятор выполнить конкретизацию, явно задав аргументы шаблона, однако решение, при котором не требуется модифицировать каждый вызов, предпочтительнее. Определив обычную функцию, мы добьемся того, что программа будет вызывать специальную версию min(int,int) для любых фактических аргументов целых типов без явного указания аргументов шаблона:
// определение шаблона функции
template <class Type>
Type min( Type t1, Type t2 ) { ... }
int ai[4] = { 22, 33, 44, 55 };
short ss = 88;
void call_instantiation() {
// ошибка: для этого вызова нет функции-кандидата
min( ai[0], ss );
}
// обычная функция
int min( int a1, int a2 ) {
min<int>( a1, a2 );
}
int main() {
call_instantiation() {
// вызывается обычная функция
min( ai[0], ss );
}
Для вызова min(ai[0],ss) из call_instantiation нет ни одной функции-кандидата. Попытка сгенерировать ее из шаблона min() провалится, поскольку для аргумента шаблона Type из фактических аргументов функции выводятся два разных значения. Следовательно, такой вызов ошибочен. Однако при обращении к min(ai[0],ss) внутри main() видимо объявление обычной функции min(int, int). Тип первого фактического аргумента этой функции точно соответствует типу формального параметра, а второй аргумент может быть преобразован в тип формального параметра с помощью расширения типа. Поскольку для второго вызова устояла только данная функция, то она и вызывается.
Разобравшись с разрешением перегрузки функций, конкретизированных из шаблонов, специализацией шаблонов функций и обычных функций с тем же именем, подытожим все, что мы об этом рассказали:
1. Построить множество функций-кандидатов.
Рассматриваются шаблоны функций с тем же именем, что и вызванная. Если аргументы шаблона выведены из фактических аргументов функции успешно, то в множество функций-кандидатов включается либо конкретизированный шаблон, либо специализация шаблона для выведенных аргументов, если она существует.
2. Построить множество устоявших функций (см. раздел 9.3).
В множестве функций-кандидатов остаются только функции, которые можно вызвать с данными фактическими аргументами.
3. Ранжировать преобразования типов (см. раздел 9.3).
a. Если есть только одна функция, вызвать именно ее.
b. Если вызов неоднозначен, удалить из множества устоявших функции, конкретизированные из шаблонов.
4. Разрешить перегрузку, рассматривая среди всех устоявших только обычные функции (см. раздел 9.3).
a. Если есть только одна функция, вызвать именно ее.
b. В противном случае вызов неоднозначен.
Проиллюстрируем эти шаги на примере. Предположим, есть два объявления – шаблона функции и обычной функции. Оба принимают аргументы типа double:
template <class Type>
Type max( Type, Type ) { ... }
// обычная функция
double max( double, double );
А вот три вызова max(). Можете ли вы сказать, какая функция будет вызвана в каждом случае?
int main() {
int ival;
double dval;
float fd;
// ival, dval и fd присваиваются значения
max( 0, ival );
max( 0.25, dval );
max( 0, fd );
}
Рассмотрим последовательно все три вызова:
1. max(0,ival). Оба аргумента имеют тип int. Для вызова есть два кандидата: конкретизированная из шаблона функция max(int, int) и обычная функция max(double, double). Конкретизированная функция точно соответствует фактическим аргументам, поэтому она и вызывается;
2. max(0.25,double). Оба аргумента имеют тип double. Для вызова есть два кандидата: конкретизированная из шаблона max(double, double) и обычная max(double, double). Вызов неоднозначен, поскольку точно соответствует обеим функциям. Правило 3b говорит, что в таком случае выбирается обычная функция;.
3. max(0,fd). Аргументы имеют тип int и float соответственно. Для вызова существует только один кандидат: обычная функция max(double, double). Вывод аргументов шаблона заканчивается неудачей, так как значения типа Type, выведенные из разных фактических аргументов функции, различны. Поэтому в множество кандидатов конкретизированная из шаблона функция не попадает. Обычная же функция устояла, поскольку существуют преобразования типов фактических аргументов в типы формальных параметров; она и выбирается. Если бы обычная функция не была объявлена, вызов закончился бы ошибкой.
А если бы мы определили еще одну обычную функцию для max()? Например:
template <class T> T max( T, T ) { ... }
// две обычные функции
char max( char, char );
double max( double, double );
Будет ли в таком случае третий вызов разрешен по-другому? Да.
int main() {
float fd;
// в пользу какой функции разрешается вызов?
max( 0, fd );
}
Правило 3b говорит, что, поскольку вызов неоднозначен, следует рассматривать только обычные функции. Ни одна из них не считается наилучшей из устоявших, так как преобразования типов фактических аргументов одинаково плохи: в обоих случаях для установления соответствия требуется стандартная трансформация. Таким образом, вызов неоднозначен, и компилятор сообщает об ошибке.
Упражнение 10.11
Вернемся к представленному ранее примеру:
template <class Type>
Type max( Type, Type ) { ... }
double max( double, double );
int main() {
int ival;
double dval;
float fd;
max( 0, ival );
max( 0.25, dval );
max( 0, fd );
}
Добавим в множество объявлений в глобальной области видимости следующую специализацию шаблона функции:
template <> char max<char>* char, char ) { ... }
Составьте список кандидатов и устоявших функций для каждого вызова max() внутри main().
Предположим, что в main() добавлен следующий вызов:
int main() {
// ...
max( 0, 'j' );
}
В пользу какой функции он будет разрешен? Почему?
Упражнение 10.12
Предположим, что есть следующее множество определений и специализаций шаблонов, а также объявления переменных и функций:
int i; unsigned int ui;
char str[24]; int ia[24];
template <class T> T calc( T*, int );
template <class T> T calc( T, T );
template<> chat calc( char*. int );
double calc( double, double );
Выясните, какая функция или конкретизированный шаблон вызывается в каждом из показанных ниже случаев. Для каждого вызова перечислите функции-кандидаты и устоявшие функции; объясните, какая из устоявших функций будет наилучшей.
(a) cslc( str, 24 ); (d) calc( i, ui );
(b) calc( is, 24 ); (e) calc( ia, ui );
(c) calc( ia[0], 1 ); (f) calc( &i, i );
Реализация объекта-функции
При реализации программы в разделе 12.2 нам уже приходилось определять ряд объектов-функций. В этом разделе мы изучим необходимые шаги и возможные вариации при определении класса объекта-функции. (В главе 13 определение класса рассматривается детально; в главе 15 обсуждается перегрузка операторов.)
В самой простой форме определение класса объекта-функции сводится к перегрузке оператора вызова. Вот, например, унарный объект-функция, определяющий, что некоторое значение меньше или равно 10:
// простейшая форма класса объекта-функции
class less_equal_ten {
public:
bool operator() ( int val )
{ return val <= 10; }
};
Теперь такой объект-функцию можно использовать точно так же, как предопределенный. Вызов алгоритма count_if() с помощью нашего объекта-функции выглядит следующим образом:
count_if( vec.begin(), vec.end(), less_equal_ten() );
Разумеется, возможности этого класса весьма ограничены. Попробуем применить отрицатель, чтобы подсчитать, сколько в контейнере элементов, больших 10:
count_if( vec.begin(), vec.end(),
not1(less_equal_then ()));
или обобщить реализацию, разрешив пользователю задавать значение, с которым надо сравнивать каждый элемент контейнера. Для этого достаточно ввести в класс член для хранения такого значения и реализовать конструктор, инициализирующий данный член указанной пользователем величиной:
class less_equal_value {
public:
less_equal_value( int val ) : _val( val ) {}
bool operator() ( int val ) { return val <= _val; }
private:
int _val;
};
Новый объект-функция применяется для задания произвольного целого значения. Например, при следующем вызове подсчитывается число элементов, меньших или равных 25:
count_if( vec.begin(), vec.end(), less_equal_value( 25 ));
Разрешается реализовать класс и без конструктора, если параметризовать его значением, с которым производится сравнение:
template < int _val >
class less_equal_value {
public:
bool operator() ( int val ) { return val <= _val; }
};
Вот как надо было бы вызвать такой класс для подсчета числа элементов, меньших или равных 25:
count_if( vec.begin(), vec.end(), less_equal_value<25>());
(Другие примеры определения собственных объектов-функций можно найти в Приложении.)
Упражнение 12.4
Используя предопределенные объекты-функции и адаптеры, создайте объекты-функции для решения следующих задач:
(a) Найти все значения, большие или равные 1024.
(b) Найти все строки, не равные "pooh".
(c) Умножить все значения на 2.
Упражнение 12.5
Определите объект-функцию для возврата среднего из трех объектов. Определите функцию для выполнения той же операции. Приведите примеры использования каждого объекта непосредственно и путем передачи его функции. Покажите, в чем сходство и различие этих решений.
Регистровые автоматические объекты
Автоматические объекты, интенсивно используемые в функции, можно объявить с ключевым словом register, тогда компилятор будет их загружать в машинные регистры. Если же это невозможно, объекты останутся в основной памяти. Индексы массивов и указатели, встречающиеся в циклах, – хорошие кандидаты в регистровые объекты.
for ( register int ix =0; ix < sz; ++-ix ) // ...
for ( register int *p = array ; p < arraySize; ++p ) // ...
Параметры также можно объявлять как регистровые переменные:
bool find( register int *pm, int Val ) {
while ( *pm )
if ( *pm++ == Val ) return true;
return false;
}
Их активное использование может заметно увеличить скорость выполнения функции.
Указание ключевого слова register – только подсказка компилятору. Некоторые компиляторы игнорируют такой запрос, применяя специальные алгоритмы для определения наиболее подходящих кандидатов на размещение в свободных регистрах.
Поскольку компилятор учитывает архитектуру машины, на которой будет выполняться программа, он зачастую может принять более обоснованное решение об использовании машинных регистров.
Рекурсия
Функция, которая прямо или косвенно вызывает сама себя, называется рекурсивной. Например:
int rgcd( int vl, int v2 )
{
if ( v2 != 0 )
return rgcd( v2, vl%v2 );
return vl;
}
Такая функция обязательно должна определять условие окончания, в противном случае рекурсия будет продолжаться бесконечно. Подобную ошибку так иногда и называют– бесконечная рекурсия. Для rgcd() условием окончания является равенство нулю остатка.
Вызов
rgcd( 15, 123 );
возвращает 3 (см. табл. 7.1).
Таблица 7.1. Трассировка вызова rgcd (15,123)
| vl | v2 | return | |||
| 15 | 123 | rgcd(123,15) | |||
| 123 | 15 | rgcd(15,3) | |||
| 15 | 3 | rgcd(3,0) | |||
| 3 | 0 | 3 |
Последний вызов,
rgcd(3,0);
удовлетворяет условию окончания. Функция возвращает наибольший общий делитель, он же возвращается и каждым предшествующим вызовом. Говорят, что значение всплывает
(percolates) вверх, пока управление не вернется в функцию, вызвавшую rgcd() в первый раз.
Рекурсивные функции обычно выполняются медленнее, чем их нерекурсивные (итеративные) аналоги. Это связано с затратами времени на вызов функции. Однако, как правило, они компактнее и понятнее.
Приведем пример. Факториалом числа n является произведение натуральных чисел от 1 до n. Так, факториал 5 равен 120: 1 ´ 2 ´ 3 ´ 4 ´ 5 = 120.
Вычислять факториал удобно с помощью рекурсивной функции:
unsigned long
factorial( int val ) {
if ( val > 1 )
return val * factorial( val-1 );
return 1;
}
Рекурсия обрывается по достижении val значения 1.
Упражнение 7.12
Перепишите factorial() как итеративную функцию.
Упражнение 7.13
Что произойдет, если условием окончания factorial() будет следующее:
if ( val != 0 )
