Лекции для студентов

Объектно-ориентированное программирование — Шаблоны функций

Шаблоны функций

Многие алгоритмы не зависят от типа данных, которые они обрабатывают. Например, перестановка двух переменных:

Type x, y, temp;

. . .

temp = x; x = y; y = temp;

будет работать для Type = int, для Type = double и для любого нового типа, определенного в программе с помощью класса. Логика алгоритма одинакова для всех типов данных. Эту ситуацию можно обобщить. Многие алгоритмы допускают отделение метода от данных. Программы, реализующие такие алгоритмы, можно отлаживать для данных одного типа, а затем применять для обработки данных других типов. Функции, реализующие эту возможность, называются параметризованными. Аргументы этих функций определяются с помощью ключевого слова template. Тип, который определяет это ключевое слово, называется шаблоном. Общая форма определения шаблона функции template приведена ниже:

template прототип функции (аргументы)

{

тело функции;

}

Здесь символ Т обозначает тип данных, используемый функцией, прототип функции состоит из типа возвращаемого значения и имени функции. Например, алгоритм перестановки значений двух аргументов можно реализовать следующим образом:

template void swap(Tswp& x, Tswp& y)

{

Tswp temp;

temp = x; x = y; y = temp;

}

void main()

{

int a = 1, b = 2;

double c = 1.1, d = 2.2;

swap(a, b); // Перестановка целых чисел

swap(c, d); // Перестановка чисел с плавающей точкой

}

Таким образом, для объявления шаблона функции, функция описывается стандартным образом, но перед ее прототипом ставится ключевое слово template, за которым следует заключенный в угловые скобки список параметров. Каждый из этих параметров определяется с помощью ключевого слова class, за которым следует идентификатор. Идентификатор служит для замещения имени типа. При вызове функции предполагается, что ключевое слово class в контексте шаблонов означает любой тип, а не только класс.

Например, максимум двух значений типа Т можно вычислять с помощью функции:

template // Ключевое слово и параметр

const T& Max(const T& a, const T& b)

{

return a>b? a:b;

}

void main()

{

int i = 1, j = 2;

float r = 1.1, s = 1.2;

int k = Max(i, j);

float t = Max(r, s);

}

Параметризованные функции могут быть перегружены другими функциями, которые тоже могут быть параметризованы, например:

template const T& Max(const T&, const T&);

template const T& Max(const T*, int);

int Max(int, int);

Для определенных типов эти функции могут быть перегружены (и переопределены) для того, чтобы выполнять (или не выполнять) какие-либо действия, которые функции-шаблоны не выполняют (или выполняют), например:

const char* Max(const char* c, const char* d)

{

// Выполнить действия, специфичные для char*

}

Пример. Параметризованная функция бинарного поиска в отсортированном массиве.

#include

#include

template

int binsearch(Type* x, int count, Type key)

{

int low, high, mid; // Левый, правый и средний элементы

low = 0; high = count — 1;

while (low <= high)

{

mid = (low+high)/2; // Вычисление середины массива

if(key < x[mid]) high = mid — 1; // Если нужный элемент

// находится слева от середины

else if(key > x[mid]) low = mid + 1; // Если справа

else return mid; // Нашли

}

return -1; // Не нашли

}

void main()

{

clrscr(); // Очистка экрана

int nums[] = {1, 2, 3, 5, 7, 11, 13, 17}; // Массив, в котором ищем

cout << "5 находится на " << binsearch(nums, 8, 5)

cout << " месте в массиве.";

getch(); // Ожидание нажатия клавиши

}

Результаты работы программы

5 находится на 3 месте в массиве.

Пример. Приведём параметризованную подпрограмму (функцию) сортировки методом пузырьков и применим ее для упорядочения массива, состоящего из целых чисел, записанных в неупакованном BCD — формате. Ниже следует подпрограмма (функция) сортировки и программа тестирования.

#include

#include

template

void bubble (Type *x, int n) // Сортировка методом пузырьков

{

int i, j;

Type t;

for(i = 1; i < n; i++)

for(j = n-1; j >= i; --j)

{

if(x[j-1] > x[j])

{

t = x[j-1]; x[j-1] = x[j]; x[j] = t;

}

}

}

void main()

{

clrscr(); // Очистка экрана

int i;

int nums[] = {10, 12, 11, 3, 5, 12, 10}; // Исходный массив

cout << "Исходный массив: ";

for(i = 0; i < 7; i++) cout << nums[i] << " ";

cout << '\n';

bubble (nums, 7); // Сортировка

cout << "Отсортированный массив: ";

for(i = 0; i < 7; i++) cout << nums[i] << " ";

getch(); // Ожидание нажатия клавиши

}

Результаты работы программы

Исходный массив: 10 12 11 3 5 12 10

Отсортированный массив: 3 5 10 10 11 12 12

В неупакованном BCD-формате старшим байтом представляется знак, младшая цифра числа записывается как нулевой элемент массива, следующая цифра — первый элемент массива и т.д.

Например, число 123 представляется байтами:

a[0] = ‘3’, a[1] = ‘2’, a[2] = ‘1’, a[n-1] = ‘-’.

Здесь n — количество разрядов числа.

Приведём пример программы для сортировки чисел, представленных в формате BCD. Для этого к параметризированной подпрограмме сортировки добавим определение класса чисел BCD и необходимые операции присваивания и сравнения. Получим следующий текст:

#include

#include

#include

template

void bubble (Type *x, int n) // Сортировка методом пузырьков

{

int i, j;

Type t;

for(i = 1; i < n; i++)

for(j = n-1; j >= i; --j)

{

if(x[j-1] > x[j])

{

t = x[j-1]; x[j-1] = x[j]; x[j] = t;

}

}

}

// Класс BCD чисел

class Bcd

{

// Недоступные элементы класса

static int n; // Максимальный размер BCD чисел

char *a; // Массив под BCD число

public:

// Общедоступные элементы класса

// Перегрузка оператора =

void operator = (char *b);

// Перегрузка оператора >

int operator > (Bcd x);

void show(); // Вывод BCD числа на экран

};

// Перегрузка оператора =

void Bcd::operator = (char *b)

{

int i;

a = new char[n]; // Выделение памяти под BCD число

for(i = 0; i < n; i++)

a[i] = '0'; // Инициализация его нулями

i = strlen(b); // Определение длины присваиваемого числа

int k = i — 1; // Запоминаем её

// Копирование знака числа

if(b[0] == '+' || b[0] == '-')

{

i--;

a[n — 1] = b[0];

}

else a[n — 1] = '+';

// Копирование самого числа

for(int j = 0; j < i; j++) a[j] = b[k — j];

}

// Перегрузка оператора >

int Bcd::operator > (Bcd x)

{

int i = 0;

// Если первое число положительное,

// а второе — отрицательное, то первое больше

if(this->a[n-1] == '+' && x.a[n-1] == '-') return 1;

// Если первое число отрицательное,

// а второе — положительное, то первое меньше

if(this->a[n-1] == '-' && x.a[n-1] == '+') return 0;

// Сравнение по отдельным цифрам

for(i = 1; i < n; i++)

{

if(this->a[n — 1 — i] > x.a[n — 1 — i])

{

if(x.a[n — 1] == '+') return 1;

else return 0;

}

else if(this->a[n — 1 — i] < x.a[n — 1 — i])

{

if(x.a[n — 1] == '+') return 0;

else return 1;

}

}

return 0;

}

// Вывод BCD числа на экран

void Bcd::show()

{

// Создание вспомогательной строки

char *str;

str = new char[n+1]; // Выделение под неё памяти

str[0] = a[n-1]; // Копирование знака

str[n] = '\0'; // Постановка конечного нуля

// Копирование цифр

int i;

for(i=n-2; i>=0; i--) str[n-i-1] = a[i];

// Вывод строки на экран

cout << str;

delete str; // Освобождение памяти

}

Теперь вызываем параметризованную функцию для сортировки массива Bcd:

int Bcd::n = 15; // Максимальная длина BCD числа

void main()

{

clrscr(); // Очистка экрана

Bcd x[10]; // Создание массива bcd чисел

// Инициализация BCD чисел

x[0] = "1234"; x[1] = "924"; x[2] = "-92"; x[3] = "0";

x[4] = "-1"; x[5] = "10"; x[6] = "12"; x[7] = "1";

x[8] = "-2"; x[9] = "12345";

// Вывод неотсортированного массива

cout << "Неотсортированные BCD числа:\n";

for(int i = 0; i < 10; i++)

{

x[i].show();

cout << '\n';

}

bubble(x, 10); // Сортировка методом пузырьков

// Вывод отсортированного массива

cout << "Отсортированные BCD числа:\n";

for(i = 0; i < 10; i++)

{

x[i].show();

cout << '\n';

}

getch(); // Ожидание нажатия клавиши

}

Результаты работы программы

Неотсортированные BCD числа:

+00000000001234

+00000000000924

-00000000000092

+00000000000000

-00000000000001

+00000000000010

+00000000000012

+00000000000001

-00000000000002

+00000000012345

Отсортированные BCD числа:

-00000000000092

-00000000000002

-00000000000001

+00000000000000

+00000000000001

+00000000000010

+00000000000012

+00000000000924

+00000000001234

+00000000012345

Пример. Рассмотрим параметризованную подпрограмму (функцию) сортировки методом выбора. Сначала находим наименьший элемент массива и переставляем его с первым элементом. Затем из оставшихся элементов находим наименьший и переставляем его со вторым элементом и т.д. Для того чтобы не переставлять элемент сам с собой в том случае, когда он уже является наименьшим среди элементов подмассива, определим переменную exchange, которая будет равна 0, если перестановки не нужны. Получим следующую подпрограмму:

template

void select(Type *x, int count)

{

int i, j, k, exchange;

Type t;

for(i=0; i

{

exchange=0;

k=i; t=x[i];

for(j=i+1; j

{

if(x[j]

{

k=j; t=x[j]; exchange=1;

}

}

if(exchange)

{

x[k]=x[i]; x[i]=t;

}

}

}

Вызов подпрограммы осуществляется слудующим образом :

int nums[] = {1, 3, 8, -1, 12, -1, 15};

Select(nums, 7);

Пример. Рассмотрим параметризованную функцию быстрой сортировки Хоара. Алгоритм быстрой сортировки опирается на идею разбиения массива на две части с последующим рекурсивным применением подпрограммы сортировки к каждой из этих частей. Перед разбиением выбирается некоторый элемент массива, значение которого называется компарандом.

Все элементы, значения которых меньше компаранда, переносятся в левую часть массива, а элементы, имеющие большее значение — в правую часть. Затем этот же процесс повторяется для каждой из частей. И так до тех пор, пока массив не будет отсортирован. Ниже приведён текст программы.

#include //библиотека потокового ввода-вывода

#include //библиотека консольного ввода-вывода

//параметризованная функция быстрой сортировки Хоара

template

void qs(Type *a, int left, int right)

{

int i, j; //левая и правая границы массива

Type x, y;

i = left; j = right;

x = a[(left+right)/2]; //определим "центр" массива

do

{

//произведём поиск элементов для перестановки

while(a[i]

while(xleft) j--;

if(i<=j)

{

//выполняем перестановку

y=a[i]; a[i]=a[j]; a[j]=y;

i++; j--;

}

}

while(i<=j);

if(left

if(i

}

//основная программа

void main()

{

int i;

int nums[]={5, 10, 12, 3, 8, 9, 2, 1}; //массив чисел для сортировки

clrscr();

cout<<"Входные данные (неотсортированный массив):\n";

for(i=0; i<8; i++) cout << nums[i] << " ";

qs(nums, 0, 7); //вызов подпрограммы сортировки

cout<<"\nВыходные данные (отсортированный массив):\n";

for(i=0; i<8; i++) cout << nums[i] << " ";//вывод результатов на экран

}

Результаты работы программы

Входные данные (неотсортированный массив):

5 10 12 3 8 9 2 1

Выходные данные (отсортированный массив):

1 2 3 5 8 9 10 12