Параметры и тип возврата
Вернемся к задаче, сформулированной в начале данного раздела. Как использовать указатели на функции для сортировки элементов? Мы можем передать в алгоритм сортировки указатель на функцию, которая выполняет сравнение:
int sort( string*, string*,
int (*)( const string &, const string & ) );
И в этом случае директива typedef помогает сделать объявление sort() более понятным:
// Использование директивы typedef делает
// объявление sort() более понятным
typedef int ( *PFI2S )( const string &, const string & );
int sort( string*, string*, PFI2S );
Поскольку в большинстве случаев употребляется функция lexicoCompare, можно использовать значение параметра по умолчанию:
// значение по умолчанию для третьего параметра
int lexicoCompare( const string &, const string & );
int sort( string*, string*, PFI2S = lexicoCompare );
Определение sort() выглядит следующим образом:
1 void sort( string *sl, string *s2,
2 PFI2S compare = lexicoCompare )
3 {
4 // условие окончания рекурсии
5 if ( si < s2 ) {
6 string elem = *s1;
7 string *1ow = s1;
8 string *high = s2 + 1;
9
10 for (;;) {
11 while ( compare ( *++1ow, elem ) < 0 && low < s2) ;
12 while ( compare( elem, *--high ) < 0 && high > s1)
14 if ( low < high )
15 1ow->swap(*high);
16 else break;
17 } // end, for(;;)
18
19 s1->swap(*high);
20 sort( s1, high - 1 );
21 sort( high +1, s2 );
22 } // end, if ( si < s2 )
23 }
sort() реализует алгоритм быстрой сортировки Хоара (C.A.R.Hoare). Рассмотрим ее определение детально. Она сортирует элементы массива от s1 до s2. Это рекурсивная функция, которая вызывает сама себя для последовательно уменьшающихся подмассивов. Рекурсия окончится тогда, когда s1 и s2 укажут на один и тот же элемент или s1 будет располагаться после s2 (строка 5).
elem (строка 6) является разделяющим элементом. Все элементы, меньшие чем elem, перемещаются влево от него, а большие– вправо. Теперь массив разбит на две части. sort() рекурсивно вызывается для каждой из них (строки 20-21).
Цикл for(;;) проводит разделение (строки 10-17). На каждой итерации цикла индекс low увеличивается до первого элемента, большего или равного elem (строка 11). Аналогично high уменьшается до последнего элемента, меньшего или равного elem (строка 12). Когда low становится равным или большим high, мы выходим из цикла, в противном случае нужно поменять местами значения элементов и начать новую итерацию (строки 14-16). Хотя элементы разделены, elem все еще остается первым в массиве. swap() в строке 19 ставит его на место до рекурсивного вызова sort() для двух частей массива.
Сравнение производится вызовом функции, на которую указывает compare (строки 11-12). Чтобы поменять элементы массива местами, используется операция swap() с аргументами типа string, представленная в разделе 6.11.
Вот как выглядит main(), в которой применяется наша функция сортировки:
#include <iostream>
#include <string>
// это должно бы находиться в заголовочном файле
int lexicoCompare( const string &, const string & );
int sizeCompare( const string &, const string & );
typedef int (*PFI)( const string &, const string & );
void sort( string *, string *, PFI=lexicoCompare );
string as[10] = { "a", "light", "drizzle", "was", "falling",
"when", "they", "left", "the", "museum" };
int main() {
// вызов sort() с значением по умолчанию параметра compare
sort( as, as + sizeof(as)/sizeof(as[0]) - 1 );
// выводим результат сортировки
for ( int i = 0; i < sizeof(as)/sizeof(as[0]); ++i )
cout << as[ i ].c_str() << "\n\t";
}
Результат работы программы:
"a"
"drizzle"
"falling"
"left"
"light"
"museum"
"the"
"they"
"was"
"when"
Параметр функции автоматически приводится к типу указателя на функцию:
// typedef представляет собой тип функции
typedef int functype( const string &, const string & );
void sort( string *, string *, functype );
sort() рассматривается компилятором как объявленная в виде
void sort( string *, string *,
int (*)( const string &, const string & ) );
Два этих объявления sort() эквивалентны.
Заметим, что, помимо использования в качестве параметра, указатель на функцию может быть еще и типом возвращаемого значения. Например:
int (*ff( int ))( int*, int );
ff() объявляется как функция, имеющая один параметр типа int и возвращающая указатель на функцию типа
int (*)( int*, int );
И здесь использование директивы typedef делает объявление понятнее. Объявив PF с помощью typedef, мы видим, что ff() возвращает указатель на функцию:
// Использование директивы typedef делает
// объявления более понятными
typedef int (*PF)( int*, int );
PF ff( int );
Типом возвращаемого значения функции не может быть тип функции. В этом случае выдается ошибка компиляции. Например, нельзя объявить ff() таким образом:
// typedef представляет собой тип функции
typedef int func( int*, int );
func ff( int ); // ошибка: тип возврата ff() - функция
