Pull to refresh

Введение в магию шаблонов

Reading time 5 min
Views 28K
Шаблоны в С++ являются средствами метапрограммирования и реализуют полиморфизм времени компиляции. Что это такое?
Это когда мы пишем код с полиморфным поведением, но само поведение определяется на этапе компиляции — т.е., в противовес полиморфизму виртуальных функций, полученный бинарный код уже будет иметь постоянное поведение.

Зачем?


image
Мы используем шаблоны для красоты. Каждый С++ разработчик знает, что такое красота, красота — это когда код компактный, понятный и быстрый.

Мета-магия и неявные интерфейсы


Что такое метопрограмма? Метопрограмма — это программа, результатом работы которой будет другая программа. Для С++ выполнением метапрограмм занимается компилятор, а результатом является бинарный файл.

image

Именно для написания метапрограмм используются шаблоны.
Чем еще отличается полиморфизм шаблонов от полиморфизма виртуальных функций? Если класс обладает явным интрерфейсом, который мы определили в объявлении класса, то далее в программе объекты этого типа могут использоваться в соответствии с этим самым интерфесом. А вот для шаблонов мы используем неявные интерфейсы, т.е. использованием объекта типа мы определяем неявный интерфейс типа, который выведет компилятор при построении метапрограммы.

Первые заклинания: волшебная дубина


image

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

typedef char CHAR;
int main() {
    B<int> b;
    B<char> c;
    B<unsigned char> uc;
    B<signed char> sc;
    B<CHAR> C;
    B<char, 1> c1;
    B<char, 2-1> c21;
    cout << "b=" << typeid(b).name() << endl;
    cout << "c=" << typeid(c).name() << endl;
    cout << "C=" << typeid(C).name() << endl;
    cout << "sc=" << typeid(sc).name() << endl;
    cout << "uc=" << typeid(uc).name() << endl;
    cout << "c1=" << typeid(c1).name() << endl;
    cout << "c21=" << typeid(c21).name() << endl;
    return 0;
}

В выводе программы видно, что типы конкретизаций шаблона разные даже для эквивалентных типов — unsigned char & char. При этом они идентичны для char & CHAR, т.к. typedef не создает тип, а лишь дает ему другое имя. Идентичны они и для выражений 1 и 2-1, т.к. компилятор вычисляет выражения и вместо 2-1 использует 1.

Отсюда и вытекает, что мы не можем использовать для шаблонов раздельную компиляцию без дополнительных проблем:
a.h
#include <iostream>
using namespace std;
template <typename T> class A {
public:
    void f();
};


main.cpp
#include "export.h"
int main() {
    A<int> a;
    a.f();
    return 0;
}


a.cpp
#include "a.h"
template <typename T> void A<T>::f() {
    cout << "A<t>::f" << endl;
}
template class A<int>;


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

Кроме классов существуют и шаблоны функций:
template<typename T> T func(T t, T d) {
    cout << "func" << endl;
};
int main() {
    func('1', 2);
}

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

 inline int func(char c, int i) {
    return func<int>(c, i);
};

Она не несет никаких накладных расходов.

Специализация — это новый уровень


image

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

#include <iostream>
using namespace std;
template<typename T> T func(T t) {
    cout << "func" << endl;
};
template<typename T> T * func(T *t) {
    cout << "func with pointer!" << endl;
};
int main() {
    func(2);
    int i = 2;
    func(&i);
}

Компилятор сам выберет наиболее точно подходящую специализацию, в примере это класс типов “указатель на тип”.

Зловещая магия: рекурсия


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

image

Самый простой и популярный пример — вычисление какого-либо ряда или полинома, скажем, сумма ряда натуральных чисел:

#include <iostream>
using namespace std;
template <int i> int func() {
    return func<i-1>()+i;
};
template <> int func<0>() {
    return 0;
};
int main () {
   cout << func<12>() << endl;
   return 0;
};

Смотрим… Работает! Круто? Увеличим количество итераций до 500:

cout << func<500>() << endl;

Теперь компиляция занимает больше времени, при этом время выполнения программы — константа! Чудеса!

Не делай козу если хотел грозу


Тут есть пара моментов.

image

Максимальная глубина рекурсии по умолчанию ограничена реализацией, для нового gcc это 900, для старых версий он меньше. Параметр
$ g++ recursion.cpp -ftemplate-depth=666666666

снимает это ограничение.

Второй подводный камень — не ждите отчетов об ошибках. Меняем сумму на факториал:

int func() {
    return func<i-1>() * i;
};
template <>  int func<0>() {
    return 1;
};
...
cout << func<500>() << endl;

Получаем некорректный результат, и ни одного предупреждения.

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

Мощные заклинания древних


А можно ли совместить магию наследования с шаблонной магией?

image

Древние используют для этого заклинание CRTP. Идея проста: применить не виртуальное наследование и обеспечить полиморфное поведение с помощью явного приведения типа наследника к типу родителя. Давайте рассмотрим пример использования:

template<typename Filtrator> class FiltratorImpl {
inline void find_message(...) {
  Filtrator* filtrator = static_cast<Filtrator* >(this);
  …
  filtrator->find_and_read_message(info, collection);
}
};
...
class CIFSFiltrator : public FiltratorImpl<CIFSFiltrator> {
...
inline void find_and_read_message(PacketInfo& info) {...}
...
};
class RPCFiltrator : public FiltratorImpl<RPCFiltrator> {
...
inline void find_and_read_message(PacketInfo& info) {...}
...
};

Мы получаем наследуемые inline методы с полиморфным поведением! Кто скажет что это не круто — мой враг навсегда.

Древние также советуют добавлять в конструктор родителя что-то типа того:

static_assert(std::is_member_function_pointer<decltype(&Filtrator::find_and_read_message)>::value)

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

image

Есть еще много тайных техник, древних и не очень. Надеюсь на не скорую встречу /*в аду*/, и да прибудет с вами мощь древних.
Tags:
Hubs:
-3
Comments 11
Comments Comments 11

Articles