---
title: Шаблоны
tags: cpp, mipt, 3sem, teaching, templates
---

# Пятое занятие
#### 2022-10-01
## Шаблоны

### Идея шаблонов

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

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

Первая же идея использования шаблонов возникает при написании функций.

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

int max(int a, int b) {
    return a > b ? a : b;
}
double max(double a, double b) {
    return a > b ? a : b;
}

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

Синтаксис шаблонов:

template<typename T> // keyword for templates
T mymax(T a, T b) {
    return a > b ? a : b;
}

int main() {
    std::cout << mymax<int>(1, 2) << '\n';
    // class MyClass must have operator '<'
    std::cout << mymax<MyClass>(MyClass(5), MyClass(10)) << '\n';
}

**Замечание 1:** Ключевое слово ```template``` действует только на ближайший блок кода (функцию или класс)

**Замечание 2:** Данные функции будут созданы только при их вызове.

**Замечание 3:** После объявления шаблона может идти только объявление.

**Замечание 4:** Объявление шаблонов возможно только в глобальной видимости, внутри класса или ```namespace```. Внутри функции нельзя объявлять новые шаблоны.

**Примечание 1:** Вместо ```typename``` можно использовать ```class``` по историческим причинам

### Перегрузка шаблонных функций

При перегрузке функций с шаблонами и без можно руководствоваться двумя правилами:

1. Точное соответствие лучше чем приведение типа
2. Частное лучше общего

Пример:

template<typename T, typename U>
void f(T a, U b) {
    std::cout << 1 << '\n';
}

template<typename T>
void f(T a, T b) {
    std::cout << 2 << '\n';
}

void f(int a, int b) {
    std::cout << 3 << '\n';
}

int main() {
    f(1, 1.0f);    // to call first function
    f(1.0f, 1.0f); // to call second function
    f(1, 1);       // to call third function
    f<int>(0.0, 1); // call 2
    f<int>(1, 1.0f); // call 1
    f<int, double>(1, 1.0f); // call 1
    f<int, double>(1.0f, 1); // call 1
    f<>(1.0, 1); // to let compiler decide which version to use (only template functions)
    f(1.0, 1); // to let compiler decide which version to use (template and non-template variants)
}

Пример 2:

template<typename T>
void f(T a) {
    std::cout << 1 << '\n';
}


// if T already has & in type, no more & is added
template<typename T>
void f(T& a) {
    std::cout << 1 << '\n';
}

int main() {
    f(1); // 1
    int x = 0;
    f(x); // CE, ambiguous call
    f<int&>(x); // still CE
}

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

### Шаблонные параметры по умолчанию

Компилятор умеет сам выводить типы, которые надо подставить в шаблон. Но если их количество не совпадает с количеством при вызове, то это вызовет ошибку.

template<typename T, typename U>
void h(T x) {
    U y;
    std::cout << y << '\n';
}

int main() {
    h(0); // CE
    
}

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

template<typename T, typename U = int>
void h(T x) {
    U y;
    std::cout << y << '\n';
}

int main() {
    h(0); // 
    
}

Вполне возможная ситуация:

template<typename T>
class A {
public:    
    A() = default;
    
    // common tempalte consructor
    template<typename U>
    A(U& a) {
        std::cout << 1 << '\n';
    }
    // copy constructor
    A(const A<T>& other) {
        std::cout << 2 << '\n';
    }
};

int main() {
    A<int> s;
    A<int> ss = s; // 1  
}

Такое происходит, так как первая версия предпочтительнее в силу того, что туда можно подставить любой тип.

## Шаблонные классы

Кроме шаблонных функций можно создавать шаблонные классы.

Пример шаблонного класса:

template<typename T>
class MyClass {
    // some code
};

void foo() {
    MyClass<int> tmp; // create templated class
    // some code
}

Кроме того, можно внутри шаблонного класса можно объявить шаблонный внутренний класс или функцию.

Пример шаблонных классов:

template<typename T>
class A {
public:
    T a;
    
    template<typename U>
    void foo(U arg1, T arg2) {
        // some code
    }
    
    template<typename U> // template inner class
    class Inner {
        U b;    
    };
};

template<typename T, typename U>
class S {
    T a;
    U b;
};

Если внутри шаблонного класса объявляется шаблонный класс или метод, то для его определения необходимо дважды указать ключевое слово ```template```.

template<typename T>
class A {
private:
    T a;
public:    
    template<typename U>
    void foo(U arg1, T arg2); // declaration
    
    template<typename U> // template inner class
    class Inner {
        U b;    
    };
};

template<typename T>
template<typename U>
void A<T>::foo(U arg1, T arg2) {
    // some code
}

**Примечание 1:** Шаблон с несколькими аргументами не то же самое что шаблон внутри шаблона

**Примечание 2:** При вызове шаблонной функции из шаблонного класса необязательно указывать шаблонные параметры явно.

Пример:

template<typename T>
class A {
private:
    T a;
public:
    template<typename U>
    void foo(U arg1, T arg2); // declaration
    
};

template<typename T>
template<typename U>
void A<T>::foo(U arg1, T arg2) {
    // some code
}

int main() {
    A<int> a;
    a.foo(1.5f, 1); // OK, first arg is float
    a.foo(1, "abc"); // CE, can't cast "abc" to int
}

### Шаблонные переменные

С С++14 появилась возможность создавать шаблонные переменные

Пример шаблонной переменной:

template<typename T>
double pi = 3.14;

template<typename T>
T pi = 3.14;

### Шаблонные alias

С С++11 есть возможность определять шаблонные ```alias```.

Пример:

template<typename T>
using umap = std::unordered_map<T, T>;

## Специализация шаблонов

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

**Примечание 1:** Для функций возможна только полная специализация, т.е. версия функции с меньшим количеством шаблонных параметров считается новой, а не специализацией существующей.

### Специализация шаблонных классов

Пример написания специализации шаблонного класса:

template<typename T>
class S {
    T x;
};

template<>
class S<int> {
    int x;    
};

**Примечание 1:** Объявлять специализации можно только после объявления общей версии шаблона

### Специализация функций

Шаблонные функции тоже можно специализировать

template<typename T>
void f(T x) {
    std::cout << 1 << '\n';
}

template<>
void f(int x) {
    std::cout << 2 << '\n';
}

int main() {
    f(0); // 2
}

Однако, при добавлении обычной версии без шаблона с параметром ```int``` будет выбрана именно эта версия.

template<typename T>
void f(T x) {
    std::cout << 1 << '\n';
}

template<>
void f(int x) {
    std::cout << 2 << '\n';
}

void f(int x) {
    std::cout << 3 << '\n';
}

int main() {
    f(0); // 3
}

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

### Порядок важен*

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

Пример 1:

template<typename T, typename U>
void f(T x, U y) {
    std::cout << 1 << '\n';
}

template<>
void f(int x, int y) {
    std::cout << 2 << '\n';
}

template<typename T>
void f(T x, T y) {
    std::cout << 3 << '\n';
}

int main() {
    f(0); // 3
}

Пример 2:

template<typename T, typename U>
void f(T x, U y) {
    std::cout << 1 << '\n';
}


template<typename T>
void f(T x, T y) {
    std::cout << 3 << '\n';
}

template<>
void f(int x, int y) {
    std::cout << 2 << '\n';
}

int main() {
    f(0); // 2
}

Пример 3:

template<typename T>
void f(T x, T y) {
    std::cout << 3 << '\n';
}

template<typename T, typename U>
void f(T x, U y) {
    std::cout << 1 << '\n';
}

template<>
void f(int x, int y) {
    std::cout << 2 << '\n';
}

int main() {
    f(0); // 2
}

### Частичная специализация шаблонов

В отличие от функций для классов возможна частичная специализация.

template<typename T, typename U>
class MyClass {
public:
    void f() {
        std::cout << 1 << '\n';
    }    
};

// partial specialization
template<typename T, typename U>
class MyClass<T&, U&> {
public:
    void f() {
        std::cout << 2 << '\n';
    }
};

// partial specialization
template<typename T>
class MyClass<T, T> {
public:
    void f() {
        std::cout << 3 << '\n';
    }    
};

int main() {
    MyClass<int, double> s;
    s.f(); // 1
    MyClass<int&, double&> ss;
    ss.f(); // 2
    MyClass<int, int> sss;
    sss.f(); // 3
    MyClass<int&, int&> ssss;
    ssss.f(); // CE
}

## Non-type шаблоны

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

template<typename T, size_t N>
class array {
  T a[N];
};

template<typename T, *T P>
class MyClass {
  
};

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

#include <iostream>
#include <array>

int f(int x) {
  return x * x;
}

int main() {
  std::array<int, 5> arr0;  // OK
  const int x = 5;
  std::array<int, x> arr1;  // OK, the second parameter is known before compilation
  const int y = f(2);
  std::array<int, y> arr2;  // CE, the second parameter need a calculation in run-time
 }

Значение шаблонного параметра должно быть зафиксировано в *момент компиляции*!

### Вычисления во время компиляции*

Покажем на примере вычисления чисел Фибоначчи как можно использовать шаблонные классы

#include <iostream>

template<int N>
struct Fibonacci {
  static const long long value = Fibonacci<N - 1>::value + Fibonacci<N - 2>::value
};

template<>
struct Fibonacci<1> {
  static const long long value = 1;
};

template<>
struct Fibonacci<0> {
  static const long long value = 0;
};

int main() {
  std::cout << Fibonacci<23> << "\n";
  return 0;
}

Если попытаться скомпилировать код без специализации шаблонов для 0 и 1, то получим выход за максимальное количество шагов рекурсии. Это получается из-за того, что на этапе компиляции компилятор пытается вычислить значения чисел Фибоначчи для каждого N и переместить их в статическое поле памяти.
Если же специализировать шаблоны начальными значениями, то программа скомпилируется и на этапе компиляции будут уже известны числа Фибоначчи
Ограничение на шаблонную рекурсию можно изменить, если передать в компилятор флаг `-ftemplate-depth 100`. Это изменит глубину шаблонной рекурсии до 100 (по умолчанию 900).

## Шаблонные параметры шаблонов

В качестве шаблонов могут выступать шаблоны. Синтаксис следующий:

#include <iostream>
#include <array>

template<typename T, template<typename> class Container>
struct Stack {
  Container<T> c;
};

int main() {
  Stack<int, std::array> s;
}

## Инстанцирование классов

Рассмотрим шаблонное наследование

template<typename T>
struct Base {
  int x;
};

template<typename T>
struct Derived: Base<T> {
  void f() {
    std::cout << x << '\n';
  }
};

Данный код скомпилируется с ошибкой. Компилятор не понимает в какой именно из копии шаблонов нужно взять `x`. Для явного указания можно воспользоваться `this` или же `Base<T>::x`

Компилятор собирает шаблонный код в два этапа: в момент *мета* обработки кода (проверка корректности выражений) и в момент подстановки шаблонных значений.

template<typename T>
struct Danger {
  int a[N];
};

template<typename T, int N>
struct S {
  void f() {
    Danger<N> d;
  }
  
  void g() {
    Danger<-1> d;
  }
};

Если явно не объявить использование класса `S`, то компилятор не выдаст ошибки. С *мета* точки зрения код класса `S` является корректным как для шаблона. Если же начать объявлять такой объект (а точнее подставлять шаблонные значения для класса), то компилятор выдаст ошибку при попытке вызова метода `g()`.
Пока метод не вызван, он **не истанцируется**. Ленивое инстанцирование шаблонов.
При объявлении указателя на шаблонный класс (или же ссылки) компилятор лишь проверяет корректность переданных шаблонных параметров, но не инстанцирует поля и методы класса.
Можно использовать объявленные шаблонные классы без их реализации для создания соответствующих указателей и ссылок.

template<typename T, int N>  // incomplete type
struct S;

int main() {
  S<int, -1>* ptr = nullptr;
  return 0;
}

Так называемые неполные типы.

## Шаблоны с переменным количеством аргументов

Шаблоны могут принимать переменное количество аргументов. Это позволяет написать свой собственный `print`.

#include <iostream>

template<typename Head>
void print(const Head& head) {
  std::cout << head << "\n";
}

template<typename Head, typename ...Tail>
void print(const Head& head, Tail... tail) {
  std::cout << head << '\t';
  print(tail...);
}


template<typename T, int N>  // incomplete type
struct S;

int main() {
  print(12, "abc", "ichi");
  return 0;
}

В данном случае `Tail` является представителем переменного числа аргументов, пакет переменного числа параметров.
Переменное число параметров распаковывается с помощью последующего троеточия.

Размер пакета можно узнать с помощью `sizeof...()`. В качестве аргумента передается пакет (например, `Tail`).

Рассмотрим еще один пример использование шаблонов для определения одинаковых типов:

#include <iostream>

template<typename T, typename U>
struct is_same {
  static const bool value = false;
};

template<typename T>
struct is_same<T, T> {
  static const bool value = true;
};

template<typename First, typename Second, typename ...Tail>
struct is_homogeneous {
  static const bool value = std::is_same<First, Second>::value && is_homogeneous<Second, Tail...>::value;
};

template<typename T, typename U>
struct is_homogeneous<T, U> {
  static const bool value = is_same<T, U>::value;
};

int main() {
  std::cout << is_homogeneous<int, int, int>::value << std::endl;
  std::cout << is_homogeneous<int, char, int>::value << std::endl;
  return 0;
}

## Задание

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

*Шаблон* кода:

template<typename Field, size_t M, size_t N>
class Matrix {
  
};

template<typename Field, size_t M, size_t N, size_t K>
Matrix<Field, M, N> operator*(const Matrix<Field, M, N>& lha, const Matrix<Field, N, K>& rha) {
  
}

Сохранять в `classwork05/matrix.cpp`