Шаблоны — введение в обобщенное программирование

Статья в википедии

Многие алгоритмы могут работать с различными типами данных, например, алгоритм поиска максимума или алгоритм сортировки списка. По сути, реализация такого алгоритма для разных типов (например, реализация функции сортировки массива целых чисел, массива действительных чисел и массива строк) будет выглядеть абсолютно одинаково для всех перечисленных типов. То есть алгоритм сортировки является некоторым “обобщенным” алгоритмом, не привязанным к какому-либо конкретному типу.

Язык программирования C++ позволяет создавать такие “обобщенные алгоритмы”, с использованием абстрактного типа, вместо какого-либо конкретного типа. Вот как это можно сделать при помощи популярных функций:

template <typename T>
T min(T a, T b)
{
    if (a < b)
        return a;
    else
        return b;
}

После этого можно пользоваться указанными функциями для различных типов данных.

Ключевое слово template означает, что данная функция явлется шаблоном. После этого в угловых скобках идет описание параметров шаблона. Как правило, это один или несколько базовых типов, используемых в функции. Описание типа начинается со слова typename, после которого идет идентификатор типа. Например, запиcь template <typename T> обозначает, что это шаблон от одного базового типа, которому дан идентификаторT. Этот идентификатор можно использовать, например, для объявления переменных такого типа внутри функции-шаблона.

Можно также объявлять и структуры данных, являющиеся шаблонами. Например, тип Fraction можно сделать структурой, использующую тип int для представления числителя и знаменателя, а можно использовать тип long long - в этом случае дробь будет занимать больше памяти, зато позволит работать с большими числами. Реализовать шаблон-структуру можно так:

template <typename T>
struct Fraction
{
    T a;
    T b;

    // Конструктор
    Fraction(T x = 1, T y = 0)
    {
        ...
    }
};

Для объявление переменной типа шаблон-структура нужно явно указать базовый тип вот так:

Fraction<int> P;
Fraction<long long> Q;

Несложно понять, что такие структуры данных, как vector, set, map на самом деле являются шаблонами структур. А само название библиотеки STL расшифровывается, как “Standard Template Library” — стандартная библиотека шаблонов.

Упражнения на проектирование простых шаблонов

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

A: Знак числа

Реализуйте шаблон функции

template <typename T>
int sign(T a)

возвращающей знак числа, то есть значение 1, -1 или 0.

B: Алгоритм Евклида

Реализуйте шаблон функции

template <typename T>
T gcd(T a, T b)

возвращающей наибольший общий делитель чисел a и b, в предположении, что T — целочисленный тип, числа a и b неотрицательные и неравны нулю одновременно.

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

C: Обмен

Реализуйте шаблон функции

template <typename T>
void Swap(T & a, T & b)

меняющей значения двух переменных местами.

D: Максимум

Реализуйте шаблон функции

template <typename T>
T Max(vector<T> & a)

возвращающей значение наибольшего элемента в векторе a, в предположении, что вектор a не пуст.

E: Вывод вектора

Реализуйте шаблон оператора << для вывода вектора:

template <typename T>
ostream & operator<<(ostream & out, vector<T> & a)

Элементы вектора разделяются пробелом, конец строки выводить не нужно, после последнего выведенного элемента выводить пробел не нужно.

F: Сортировка вектора

Реализуйте шаблон функции

template <typename T>
void Sort(vector<T> & a)

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