Использование параметризованных функций

Размещено на http://www.allbest.ru/

Использование параметризованных функций

Вероятно, самой важной из новых возможностей C++ является шаблон (template). Причина этого заключается в том, что шаблоны фундаментально изменяют внешнюю сторону программирования. Используя шаблон, вы можете создавать обобщенные спецификации для функций и для классов, которые часто называются параметризованными функциями (generic functions) и параметризованными классами (generic classes). Параметризованная функция определяет общую процедуру, которая может быть применена к данным различных типов. Параметризованный класс определяет общий класс, который может применяться к изменяющимся типам данных. В обоих случаях конкретный тип данных, над которыми выполняется операция, передается в качестве параметра. Как вы можете себе представить, именно это и делает шаблоны чрезвычайно ценным средством. В C++ шаблон функции или класса декларируется с помощью ключевого слова template. Возможно, вы уже знакомы с основными принципами использования ключевого слова template. В этой главе будут рассмотрены некоторые приемы, позволяющие в полной мере использовать преимущества, предоставляемые шаблонами.

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

Для демонстрации возможностей шаблонов мы используем поиск и сортировку - две наиболее широко распространенных в компьютерном мире операции. Алгоритмы поиска и сортировки выбраны нами по трем причинам. Во-первых, они легко преобразуются в форму шаблонов, и, как вы увидите далее, это преобразование существенно повышает их эффективность. Во-вторых, поиск и сортировка используются практически в любой программе, и поэтому чтение этой главы принесет практическую пользу всем программистам, которые в результате этого получат в свое распоряжение разнообразные параметризованные функции поиска и сортировки. Наконец, алгоритмы сортировки представляют собой одну из самых интересных и захватывающих областей науки программирования. Кроме того, эту тему многие не разрабатывают, а принимают на веру. Так, многие программисты используют в своих разработках стандартные библиотечные функции сортировки. Однако, как вы вскоре убедитесь, благодаря использованию шаблонов, на эту важную тему стоит посмотреть свежим взглядом.

Почему следует использовать параметризованные функции

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

DataType temp, x, у;

//…

temp=x;

х=у;

y=temp;

Если не рассматривать случаи, заведомо содержащие внутреннюю ошибку, этот алгоритм работает вне зависимости от фактического значения типа данных DataType. К примеру, алгоритм работает одинаково как при обмене целыми значениями, так и при обмене значениями типа double или long. Таким образом, логика алгоритма одинакова для всех типов данных. Однако, в большинстве языков программирования для обмена данными каждого типа требуется написание новой версии подпрограммы, несмотря на то, что лежащий в ее основе алгоритм остается неизменным. Эту ситуацию можно обобщить. Многие алгоритмы допускают отделение метода от данных. При использовании таких алгоритмов большим преимуществом была бы возможность однократного определения и отладки логики алгоритма, и последующее применение алгоритма к различным типам данных без необходимости перепрограммирования. Это не только для предоставления функции возможностей обработки различных типов данных. Разумеется, использование дополнительного параметра означает генерацию избыточного кода при вызове функции. Параметры функции передаются через стек. Передача каждого параметра генерирует несколько инструкций в машинном коде. Таким образом, каждый дополнительный параметр уменьшает эффективность кода, увеличивая время, требующееся на вызов функции. Если функция вызывается постоянно, это снижение эффективности быстро создаст проблему. Поэтому ранее параметризация функции автоматически означала замедление ее работы. Таким образом, за преимущества, предоставляемые параметризацией функции, приходилось дорого платить.

Для того, чтобы проиллюстрировать дальнейшее обсуждение конкретным примером, рассмотрим хорошо известный образец функции, параметризованной в старом стиле -- функцию qsort(). Как вы, возможно, уже знаете, qsort() является стандартной библиотечной функцией сортировки языка C++. Она выполняет сортировку данных любых типов, используя алгоритм быстрой сортировки. (Далее в данной главе вы узнаете, как реализовать собственную версию алгоритма быстрой сортировки.) Однако, поскольку функция qsort() заимствована из библиотеки стандартного С, она использует устаревший подход к параметризации, основанный на передаче параметров. Прототип функции приведен ниже:

void qsort(void *buf, size_t пит, size_t size,

int (*comp)(const void*, const void*));

Здесь параметр buf является указателем на массив, содержащий данные, которые должны быть отсортированы. Количество сортируемых элементов передается параметром пит. Для поддержки алгоритма сортировки технически необходимыми являются только два параметра. Однако, в целях параметризации функции ей передается параметр size, определяющий размер элемента массива, и параметр сотр, представляющий собой указатель на функцию, осуществляющую сравнение двух элементов. Таким образом, параметризация функции требует добавления двух параметров. Если бы функция использовалась эпизодически, это не являлось бы предметом, достойным обсуждения. Однако, как будет видно из дальнейшего изложения, функция qsort() обычно реализуется как рекурсивная функция, и поэтому наличие дополнительных параметров приводит к значительному снижению ее производительности.

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

Построение параметризованных функций сортировки

Сортировка (sorting) - это процесс, позволяющий упорядочить множество подобных данных в возрастающем или убывающем порядке. Сортировка представляет собой один из наиболее приятных с интеллектуальной точки зрения алгоритмов, поскольку процесс хорошо определен. Алгоритмы сортировки хорошо исследованы и изучены. К сожалению, по этой причине сортировку иногда принимают как некую данность. Фактически, когда возникает необходимость в сортировке данных, большинство программистов просто используют стандартную функцию сортировки, имеющуюся в библиотеке, которая поставляется с их компилятором, и больше об этом не задумываются. Однако, как вы увидите далее, различные подходы к сортировке обладают различными характеристиками. Хотя некоторые методы в среднем могут быть лучше других, ни один из методов не будет идеальным для всех ситуаций. Поэтому каждый программист должен иметь в своем распоряжении несколько различных типов сортировки. То, что теперь эти методы могут быть реализованы в виде параметризованных функций, еще более усиливает их значимость.

Пузырьковая сортировка

Самым известным (и самым скверным) методом сортировки является пузырьковый метод. Его популярность является следствием запоминающегося названия и простоты. Однако, в общем случае это -- самый худший из всех когда-либо изобретенных методов.

Пузырьковая сортировка основана на методе перестановок. Ее смысл заключается в постоянном сравнении смежных элементов и при необходимости -- их перестановке. Элементы массива в этом методе уподобляются всплывающим пузырькам в резервуаре с водой -- каждый из них достигает своего уровня. Для начала реализуем не параметризованную форму пузырьковой сортировки. Таким образом вы сможете лучше понять принципы работы этого алгоритма. Нижеприведенная программа содержит не параметризованную версию пузырьковой сортировки, которая может использоваться для сортировки символьных массивов.

Простейшая реализация пузырьковой сортировки для символов

#include <iostream.h>

ttinclude <string.h>

void bubble(char *item, int count);

main()

{

char str[] = "dcab";

bubble(str, (int) strlen(str));

cout « "Отсортированная строка: " « str « endl;

return 0;

}

Простая версия пузырьковой сортировки void bubble(char *item, int count)

{

register int a, b;

char t;

for(a=l; a<count; ++a)

for(b=count-l; b>=a; --b) {

if(item[b-l] > item[b]) {

Перестановка значений

t=item[b-l];

item[b-l] = item[b];

item[b] = t;

}



В функции bubble( ), item представляет собой указатель на массив символов, который должен подвергнуться сортировке, а параметр count представляет собой количество элементов массива. Метод пузырьковой сортировки управляется двумя вложенными циклами. При условии, что массив содержит count элементов, внешний цикл вызывает сканирование массива count--1 раз. Это гарантирует, что даже в наихудшем случае после завершения функции каждый элемент будет находиться на своем месте. Внутренний цикл фактически выполняет сравнения и перестановки. (Несколько усовершенствованная версия пузырьковой сортировки завершается, если перестановок не происходит, но данная версия выполняет сравнение на каждом проходе через внутренний цикл.) Эту версию пузырьковой сортировки можно использовать для сортировки массива символов в восходящем порядке.

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

Исходный массив	d с a b
проход 1	a d с b
проход 2	a b d с
проход 3	abed

Анализируя алгоритмы сортировки, вы должны определить, сколько сравнений и перестановок будет выполнено в лучшем, в среднем и в наихудшем случае. Для алгоритма пузырьковой сортировки количество выполняемых сравнений всегда одинаково, так как оба цикла for повторяются указанное количество раз вне зависимости от того, отсортирован список или нет. Это означает, что при пузырьковой сортировке всегда выполняется

1/2(n²-n)



сравнений, где n -- количество сортируемых элементов. Эта формула следует из того факта, что внешний цикл выполняется п-1 раз, а внутренний -- n/2 раз. Перемножив эти значения, получаем вышеприведенную формулу.

В наилучшем случае (если список уже отсортирован) количество перестановок равно нулю. Количество перестановок в среднем и в худшем случаях равны соответственно:

В среднем случае

3/4(n²-n)

В худшем случае

3/2(n²-n)

Объяснение того, как получены эти формулы, выходит за рамки этой книги, однако, вы можете интуитивно предположить, что по мере того, как снижается степень упорядоченности списка, количество неупорядоченных элементов, нуждающихся в перестановке, приближается к числу выполняемых сравнений.

Пузырьковая сортировка называется п-квадратичным алгоритмом, так как время его выполнения пропорционально квадрату количества элементов сортируемого массива. Алгоритм чрезвычайно неэффективен при работе с большими массивами, так как время выполнения непосредственно связано с количеством выполняемых сравнений и перестановок. Пренебрежем временем, занимаемым на перестановку элемента, позиция которого не соответствует его значению, и допустим, что одна операция сравнения занимает 0.001 секунды. Тогда сортировка десяти элементов займет примерно 0.05 секунды, для 100 элементов потребуется уже около 5 секунд, а для 1000 элементов это время возрастет уже до 500 секунд. Сортировка 100000 элементов (небольшой телефонный справочник) займет 5000000 секунд или около 1400 часов - только представьте себе -целых два месяца непрерывной сортировки! На рис. 1.1 показана зависимость времени выполнения от размеров сортируемого массива.

Рис. 1.1. Время выполнения пузырьковой сортировки находится в квадратичной зависимости от размера сортируемого массива

Преобразовать не параметризованную версию пузырьковой сортировки в шаблон достаточно просто. Для этого необходимо параметризовать тип сортируемых данных. Ниже приведена параметризованная версия пузырьковой сортировки:

Параметризованная реализация пузырьковой сортировки

#include <iostream.h>

tinclude <string.h>

template <class Stype> void bubble(Stype *item, int count);

main()

{

//сортировка массива символов

char str[] = "dcab";

bubble(str, (int) strlen(str));

cout « "Отсортированная строка: " « str « endl;

//сортировка массива целых чисел

int nums[] = {5, 7, 3, 9, 5, 1, 8};

int i;

bubble(nums, 7);

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

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

return 0;

}

//Параметризованная версия пузырьковой сортировки

template <class Stype> void bubble(Stype *item, int count) {

register int a, b;

Stype t;

for(a=l; a<count; ++a)

for(b=count-l; b>=a; --b) {

if(item[b-l] > item[b]) {

//Перестановка значений t=item[b-l];

item[b-l] = item[b];

item[b] = t;

}

Как видите, теперь тип сортируемых данных указывается с помощью параметризованного типа Stype. Кроме того, в пределах функции bubble() временная переменная t также декларируется как принадлежащая к типу Stype. В функции mainQ при каждом вызове параметризованной функции bubbleQ компилятором генерируется ее экземпляр, соответствующий типу сортируемых данных. Так, в первом случае генерируется сортировка массива символов. Во втором случае порождается функция сортировки массива целых. Важно понимать, что в каждом конкретном случае компилятор замещает шаблон Stype фактически используемым типом данных. Таким образом, для каждого типа данных порождается своя функция сортировки. Именно поэтому параметризованную функцию алгоритма пузырьковой сортировки можно применять к данным любого типа. Прежде, чем продолжать, попробуйте поэкспериментировать и отсортируйте, скажем, массив чисел типа double.

Исследование параметризованных классов

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

Наиболее широкое применение шаблоны классов находят при создании контейнерных классов. Фактически, как было указано в главе 1, создание контейнерных классов является одной из основных причин, по которым были введены в употребление шаблоны. Контейнерными классами в общем случае называются классы, в которых хранятся организованные данные. Например, массивы и связные списки являются контейнерами. Преимущество, даваемое определением параметризованных контейнерных классов, заключается в том, что как только логика, необходимая для поддержки контейнера, определена, он может применяться к любым типам данных без необходимости его переписывания. Благодаря этому, один раз написанный и отлаженный контейнерный класс можно использовать повторно. Например, параметризованный контейнер связного списка можно использовать для построения списков, содержащих почтовые адреса, заглавия книг или названия автомобильных запчастей. Поскольку контейнерные классы имеют исключительно важное значение, как практическое, так и историческое, мы рассмотрим возможности шаблонов классов на их примере.

В этой главе мы рассмотрим пять основных типов контейнеров:

1. Ограниченный ("защищенный") массив

2. Очередь а Стек

3. Связный список

4. Бинарное дерево

Каждый из этих контейнеров выполняет конкретные операции сохранения и извлечения над заданной информацией и полученными запросами. В частности, все они могут сохранять и извлекать элемент (где элемент представляет собой одну информационную единицу). Все остальные разделы данной главы посвящены построению параметризованных версий этих контейнеров.

Ограниченные массивы

Простейшим примером контейнерного класса является ограниченный или "защищенный" массив. Как вы знаете, в C++ во время выполнения кода можно выйти за границу массива (или не дойти до нее) без генерации сообщений об ошибках времени выполнения. Хотя эта возможность позволяет C++ генерировать исключительно быстрый исполняемый код, но одновременно с этим она служит источником ошибок и доводила до исступления программистов еще с момента изобретения C++ (и его предшественника С). Однако, эту проблему можно успешно решить. Для этого необходимо создать класс, который содержит массив, и разрешить доступ к массиву только через перегруженный индексирующий оператор [ ]. В функции operator[ ]( ) вы можете перехватывать индекс, выходящий за рамки диапазона массива. Поскольку механизм проверки границ будет одинаков для всех типов данных, имеет смысл создание параметризованного ограниченного массива, который вы сможете использовать каждый раз, когда вам потребуется "защищенный" массив. Как вы увидите далее, ограниченный параметризованный массив является простейшим, но, несмотря на это, одним из наиболее полезных контейнерных классов.

Как уже упоминалось, построение ограниченного параметризованного массива требует перегрузки оператора [ ]. Если вы еще не знакомы с перегрузкой этого оператора, вам поможет материал следующего раздела.

Перегрузка оператора [ ]

В C++ оператор [ ] при перегрузке считается бинарным оператором [ ] может быть перегружен только функцией-членом. Общая форма функции-члена operator[ ]( ) приведена ниже:

type class-name::operator[](int index) {

//...

}

Чисто технически, параметр не обязательно должен принадлежать к типу int однако, функции operator[ ]( ), как правило, используются для обеспечения индексации массивов, а для этого обычно используются целые значения, Как правило, функция operator[ ]( ) возвращает значение того же типа, что и тип данных, хранящихся в индексируемом массиве.

Принцип работы оператора [ ] проще всего понять на примере объекта с именем ob, проиндексированного следующим образом: ob[9]

Индекс этого массива будет транслироваться в следующий вызов функции operator[ ]( ): operator[](9)

Таким образом, выражение, используемое в качестве оператора индексации, передается функции operator[ ]( ) как явный параметр. Указатель this будет указывать на ob, объект, сгенерировавший этот вызов.

Функцию operator[ ]( ) можно разработать таким образом, чтобы оператор [] можно было использовать как в левой, так и в правой части оператора присваивания. Для этого следует определить возвращаемое значение функции operator[ ]( ) как ссылку и возвращать ссылку на указанный элемент массива. В этом случае будут корректны следующие типы утверждений:

пузырьковый сортировка параметризированный массив

ob[9] = 10;

x = ob[9];

Построение параметризованного ограниченного массива

Нижеприведенная программа создает параметризованный ограниченный массив и иллюстрирует его использование. Обратите внимание, что функция operator[]( ) возвращает ссылку, которая позволяет использовать ее в любой части утверждения присваивания.

//Параметризованный ограниченный массив #include <iostream.h>

#include <stdlib.h>

// Параметризованный класс ограниченного массива template <class Atype> class atype {

Atype *a;

int length; public:

atype(int size);

~atype() {delete [] a;} Atype &operator[](int I);

};

//Конструктор для atype

template <class Atype> atype<AType>::atype(int size)

{

50

register int i;

length = size;

a = new Atype[size]; // Динамическое выделение области хранения

if(!a) {

cout « "Невозможно выделить массив.\n" ; exit(1);

}

// Инициализация нулем

for(i = 0; i<size; i++) a[i] = 0;

}

//Обеспечение диапазона проверки для atype

template <class Atype> Atype &atype<AType>::operator[](int i) {

if (i<0 || i > length -1) {

cout « "\nЗначение с индексом " ;

cout « i « " выходит за пределы диапазона. \n"; exit (1) ;

}

return a[i];

}

main() {

atype<int> intob(20); //массив целых

atype<double> doubleob(10); //массив переменных типа

// double

int i;

cout « "Массив целых: ";

for (I = 0; I < 20; I++) intob[I] = I;

for (I = 0; I<20; I++) cout « intob[I] « " ";

cout « endl;

cout « "Double array: ";

for (I = 0; I < 20; I ++) doubleob[I] = (double) i *

3.14;

for (I = 0; I<20; I++) cout « doubleob[I] « “ ”

cout « endl;

intob[45] = 100; // generates run-time error

return 0; }

Эта программа реализует параметризованный тип защищенного массива, а затем демонстрирует его использование, создавая массив целых и массив переменных типа double. (Можно попытаться создавать и массивы других типов.) Как показывает этот пример, параметризованные классы позволяют один раз написать и отладить код, который после этого можно использовать с данными любых типов без необходимости его дальнейшей переработки для каждого конкретного приложения.

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

Размещено на Allbest.ru