Методология обобщенного программирования

Рекомендации по конкретным разделам курса

Алгоритмы сортировки и поиска подробно описаны в книгах [4, гл. 6-9], [5]. Информацию о конкретных алгоритмах сортировки часто легко найти в сети Интернет с помощью средств поиска и в электронной энциклопедии [6].

Структуры данных, на базе которых строятся контейнеры, описаны в работе [4, гл. 11-14]. 16-ая и 17-ая глава работы [3] также могут быть полезны для изучения контейнеров. Прежде всего они, так же как и глава 19, посвящены контейнерам, реализованным в библиотеке STL.

18-ая глава книги [3] описывает стандартные алгоритмы STL. Значительная часть информации по контейнерам и алгоритмам STL доступна также в MSDN [7].

Работа [3] также полезна для восстановления знания языка программирования C++.

Методология обобщенного программирования [3] была создана Александром Степановым, российско-американским ученым. Основная идея обобщенного программирования состоит в обобщении алгоритмов и классов, обеспечивающем возможность их применения для работы с различными типами данных. Методология обобщенного программирования – основа стандартной библиотеки шаблонов языка C++ (STL).

Рассматриваемые в данном курсе алгоритмы сортировки и поиска и контейнеры данных универсальны. Они могут быть применены для любых типов данных, предъявляя к ним лишь минимальные требования (например, реализация оператора < для сортировки или использования бинарных деревьев поиска). Поэтому мы хотим сделать их программную реализацию столь же универсальной. Именно в этом нам может помочь методология обобщенного программирования.

Почему не интерфейсы?

Мы знаем, что мы можем сортировать массив элементов любого типа, если у этого типа есть оператор <. Первое желание, которое возникает у разработчика с опытом объектно-ориентированного программирования - написать:

class ISortElement

{

virtual bool operator <(const ISortElement& other) const = 0;

};

После этого мы могли бы реализовать функцию

void Sort(ISortElement** ptr_array, int num_elements);

наследовать все типы данных, нуждающиеся в сортировке, от ISortElement, и использовать функцию Sort для их сортировки.

Это решение имеет множество недостатков:

1. Каждый наследник ISortElement должен уметь сравнить себя с любым наследником ISortElement. Эту проблему можно обойти, но не самыми удобными методами (dynamic_cast – динамическая проверка типов).

2. Мы можем попытаться сортировать массив, в котором есть разные наследники ISortElement – не всегда мы хотим этого.

3. Мы не можем сортировать с помощью той же функции массив значений элементарных типов (int, double) или массив объектов, класс которых разработан независимо от нас и не унаследован от ISortElement.

4. Мы вынуждены хранить массив указателей, а не массив элементов (и самостоятельно заботиться о разрушении элементов). Проблема решается умными указателями [3], но все равно неприятна.

Почему возникла эта проблема? Потому, что мы захотели слишком многого.

Мы попытались сделать так, чтобы алгоритм сортировки не знал о типе своих элементов до момента выполнения. На самом деле нам это не нужно. Алгоритм должен знать тип своих элементов – чтобы менять их местами и не пользоваться указателями, чтобы пользоваться их индивидуальными операторами сравнения. Мы не против того, чтобы компилятор отдельно компилировал алгоритм для каждого типа данных. Необходимо только избавиться от copy and paste и сделать так, чтобы разработчик написал алгоритм один раз. Эту проблему и позволяют решить шаблоны C++.

Шаблоны C++

Шаблоны в языке программирования C++ позволяют реализовать алгоритмы универсально, независимо от специфики типов данных, с которыми они работают.

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

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

При обращении к шаблону мы можем явно указывать значение параметров или предоставить компилятору догадаться (если он не догадается – возникнет ошибка).

Рассмотрим пример шаблона – универсальную функцию поиска элемента в массиве. Определение функции:

template < typename T >

int Find(T* ptr_array, int num_elements, T element)

{

int i;

for (i = 0; i < number – 1; i++)

{

if (ptr_array[ i ] == element)

return i;

}

return -1;

}

Использование функции:

double d_array[ 10 ];

int i_array[ 20 ];

…. //ввод данных

int num = Find <double>(d_array, 10, 3.0);

//Мы явно указали тип, с которым работаем

num = Find(i_array, 20, 5) //Можем и не указывать – компилятор догадается,

//что если ему в качестве первого параметра

//дают int* - значит, T=int

При определении функции-шаблона указывается, какие параметры шаблона у нее есть (т.е. чем различаются разные инстанциации функции-шаблона). Параметр шаблона может быть типом данных (обозначается словом class или typename) или целым числом (int). Параметр шаблона имеет имя. Оно может использоваться в тексте функции шаблона. При генерации инстанциации оно будет заменено на реальное значение параметра.

Например, наша функция Find имеет один параметр – тип данных, обозначаемый идентификатором T. Этот идентификатор используется в списке параметров функции (T*, T). Встретив вызов Find <double>, компилятор генерирует инстанциацию шаблона – код вида:

int Find(double* ptr_array, int num_elements, double element)

{

int i;

for (i = 0; i < number – 1; i++)

{

if (ptr_array[ i ] == element)

return i;

}

return -1;

}

Как видите, T всюду заменено на double. Именно такая функция будет вызвана для сортировки массива d_array.

Функция Find может использоваться для поиска элемента в массиве с различным типом элемента. При этом важно, чтобы была возможность проверить, равен ли один элемент данного типа другому (иначе некорректен код ptr_array[ i ] == element). Также важна возможность копирования элементов данного типа. Если Ваш тип элемента – какой-либо сложный класс, Вы должны реализовать для него конструктор копирования и оператор == – и после этого можете использовать шаблон Find для поиска элемента в массиве объектов Вашего класса.

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

Пример создания универсального класса комплексного числа приведен ниже.

Определение класса:

template <typename RealType>

class Complex

{

Complex(RealType r, RealType i)

{

Real = r;

Imag = i;

}

Complex operator+(const Complex& other)

{

Complex result(Real+other.Real, Imag+other.Imag);

return result;

}

…

private:

RealType Real;

RealType Imag;

};

Использование класса:

….

Complex <float> a(3.4, 2.5);

Complex <double> b(3.8, 7.5);

Complex <double> c(1.2, 2.1);

Complex <double> d = b + c;

….

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

Complex <float> a(3.4, 2.5);

компилятор генерирует инстанциацию шаблона Complex для параметра шаблона float – класс приведенного ниже вида.

class Complex

{

Complex(float r, float i)

{

Real = r;

Imag = i;

}

Complex operator+(const Complex& other)

{

Complex result(Real+other.Real, Imag+other.Imag);

return result;

}

…

private:

float Real;

float Imag;

};

В программе создается объект данного класса a. Встретив Complex <double>, компилятор сгенерирует еще одну инстанциацию шаблона и воспользуется ей.

Дата добавления: 2015-01-03