Многие алгоритмы могут работать с различными типами данных, например, алгоритм поиска максимума или алгоритм сортировки списка. По сути, реализация такого алгоритма для разных типов (например, реализация функции сортировки массива целых чисел, массива действительных чисел и массива строк) будет выглядеть абсолютно одинаково для всех перечисленных типов. То есть алгоритм сортировки является некоторым “обобщенным” алгоритмом, не привязанным к какому-либо конкретному типу.
Язык программирования 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.
Реализуйте шаблон функции
template <typename T> int sign(T a)
возвращающей знак числа, то есть значение 1, -1 или 0.
Реализуйте шаблон функции
template <typename T> T gcd(T a, T b)
возвращающей наибольший общий делитель чисел a и b, в предположении, что T — целочисленный тип, числа a и b неотрицательные и неравны нулю одновременно.
В этой задаче T может быть и значением типа char
(char тоже целочисленный тип), при этом оператор взятия
остатка от деления для типа char возвращает значение типа int
для аргументов типа char, эти грабли
нужно обойти.
Реализуйте шаблон функции
template <typename T> void Swap(T & a, T & b)
меняющей значения двух переменных местами.
Реализуйте шаблон функции
template <typename T> T Max(vector<T> & a)
возвращающей значение наибольшего элемента в векторе a, в предположении, что вектор a не пуст.
Использование функций из заголовочного файла <algorithm> запрещено.
Реализуйте шаблон оператора << для вывода вектора:
template <typename T> ostream & operator<<(ostream & out, vector<T> & a)
Элементы вектора разделяются пробелом, конец строки выводить не нужно, после последнего выведенного элемента выводить пробел не нужно.
Реализуйте шаблон функции
template <typename T> void Sort(vector<T> & a)
упорядочивающей элементы вектора по неубыванию. Сдайте на проверку эту функцию вместе с оператором вывода, определённом в предыдущей задаче.
Использование функций из заголовочного файла <algorithm> запрещено.