Довизначення (overloading) функцій

Довизначення (overloading) функцій

Рекурсія

Рекурсія

Функції можуть викликатися рекурсивно

int gcd (int v1, int v2)

{

return v2? gcd (v2, v1%v2): v1;

}

Рекурсію часто легше записати, ніж ітерацію, але вона може виявитись досить неефективною. Якщо, не думаючи, переписати визначення чисел Фібоначчі в рекурсивну функцію, час обчислень може стати експоненціальним

int BadFib(int n)

{

// Так не варто рахувати!!!

switch (n)

{

case 0:

return 0; break;

case 1:

return 1; break;

default:

return BadFib(n-1)+BadFib(n-2);

}

}

Але це не проблема рекурсії, а проблема неефективної схеми обчислень. Дійсно, підраховуючи n-1-е число Фібоначчі корисно пам’ятати обчислене перед цим n-2-е:

void fib(int &f1, int &f2, int n)

{

int f;

if (n>=2)

{

f=f2; f2+=f1; f1=f;

fib(f1, f2, n-1);

}

}

int Fibonacci (int n)

{

int f0=0, f1=1;

switch (n)

{

case 0:

return f0;break;

case 1:

return f1; break;

default:

fib(f0, f1, n);

return f1;

}

}

Візьмемо дві функції

void DisplayInt(int intParam)

{

cout << "The integer is: " << intParam << "\n";

}

void DisplayString(char *text)

{

cout << "The text is: " << text << "\n";

}

що мають одне й те ж призначення: вивести значення свого аргументу. Але правила типізації вимагають двох різних визначень залежно від типу параметру. Правда, два різних визначення не вимагають двох різних імен функцій. Ми вже давно звикли до вживання одного і того ж символу для позначення, наприклад, операції додавання чисел, векторів, матриць, інтегралів і ще чого завгодно. Так само функції з наведеного прикладу ми можемо позначити спільним іменем

void Display(int intParam)

{

cout << "The integer is: " << intParam << "\n";

}

void Display(char *text)

{

cout << "The text is: " << text << "\n";

}

Їх виклик

Display(a)

буде розпізнаватися за типом параметру. Ясно, що для використання цих функцій нам потрібні будуть обидва прототипи

void Display(int);

void Display(char *);

При необхідності список функцій з одним і тим же іменем може бути розширений шляхом довизначення (overloading) цієї функції для іншого типу параметрів, наприклад,

void Display(double);

Можна визначити декілька функцій для обчислення максимуму

int max (int x, int y) { return x>y? x: y; }

double max (double x, double y) { return x>y? x: y; }

int max (int x, int y, int z) { return max(x, max(y,z));}

Особливо популярним є довизначення стандартних операцій. Наприклад, визначимо структуру точки площини

struct Point{ double x; double y;}

Point operator+(Point u, Point v)

{

Point w;

w.x = u.x + v.x;

w.y = u.y + v.y;

return w;

}

Можна уявити собі декілька сигнатур додавання:

Point operator+(Point, Point);

Point operator+(Point &, Point &);

Point operator+(const Point &, const Point &);

Подумайте, на якому з них зупинитися.

Можна також довизначити порівняння точок на рівність

bool operator==(Point u, Point v)

{

return (u.x == v.x) && (u.y == v.y);

}

нерівність і багато чого іншого.

Наявність багатьох визначень для однієї й тієї ж операції вимагає від компілятора деяких додаткових зусиль для пошуку варіанту, підходящого до кожного конкретного виклику. Певну проблему в цьому пошуку створює можливість неявного зведення типів, наприклад, у виклику Display (’a’).

4.7 Узагальнені функції (function template)

Узагальнені функції (function template)

Інший спосіб наділення однієї функції багатьма реалізаціями полягає у застосуванні узагальнених (generic) функцій. Для цього в С++ використовують так званий механізм шаблонів (template).

Розглянемо, наприклад, функцію swap, визначену нами для цілих чисел. При необхідності ми могли б довизначати її для інших типів, наприклад, дійсних чисел

void rswap(double &x, double &y)

{

double z = x; x=y; y=z;

}

При цьому легко помітити, що дії, які виконуються у функції, не залежать від типів її параметрів. На місці double міг би бути довільний тип, для якого визначена операція присвоєння. Ми могли б уявити собі таке параметричне визначення функції

void rswap(Type &x, Type &y)

{

Type z = x; x=y; y=z;

}

Тепер, правда, в програмі з’явився невизначений об’єкт Type. Залишилося сказати, що це довільний тип. Такого вигляду набуде повне визначення узагальненої функції

template <class Type>

void rswap(Type &x, Type &y)

{

Type z = x; x=y; y=z;

}

Узагальнені функції обробляються компілятором у дуже спеціальний спосіб. Компілятор не в стані побудувати об’єктний код, тому що різні типи даних можуть вимагати різних машинних команд для виконання однієї й тієї ж дії, хоч би й присвоєння. У випадку символу, це буде пересилка одного байту, для цілого — слова, для дійсного подвоєної точності — двох слів. Тому компілятор лише фіксує факт наявності шаблону, створюючи його конкретизації для кожного виклику. Так в контексті

char a, b;

rswap(a, b);

буде згенеровано об’єктний код для перестановки символів, а в контексті

float a, b;

rswap(a, b);

код для перестановки дійсних чисел. Або навіть

Point u, v;

rswap(u, v);

Шаблони можуть накладати певні обмеження на допустиму конкретизації. Якщо ми повернемося до прикладу з максимумом, то одержимо шаблон

template <class Type> Type max(Type x, Type y)

{

return (x>y? x: y);

}

Тут Type вже не будь-який тип, а лише такий, для якого визначено порівняння на нерівність. Компілятор не зможе згенерувати коду для спроби обчислити максимум двох точок

Point u, v, w;

w = max(u, v);

Інша проблема узагальнених функцій викликана складностями з перетворенням типів. Дійсно, один і той же типовий параметр, наприклад, T з попереднього прикладу не може набувати одного значення на місці першого аргументу і іншого на другому місці. Ось приклад, який показує проблеми і шляхи їх вирішення

template <class T> T mymax (T x, T y)

{

cout<<"template ";

return x>y? x: y;

};

Явна функція сильніша за узагальнену

long mymax(long x, long y)

{

cout<<"long ";

return x>y? x: y;

};

При необхідності змішувань типів доведеться користуватися додатковими специфікаціями

inline double mymax (int x, double y)

{

return mymax<double>((double)x, y);

};

Варіанти викликів

cout<<mymax(1,2)<<endl;

cout<<mymax('a','b')<<endl;

cout<<mymax(1l,3l)<<endl;

cout<<mymax(1l,4)<<endl; // error

cout<<mymax<long>(1,5)<<endl; // узагальнена

cout<<mymax<long>(1l,5)<<endl; // явна

cout<<mymax(1,3.14)<<endl;

cout<<mymax(1l,4.14)<<endl;

cout<<mymax('a',1)<<endl; // error

Дата добавления: 2014-01-04