Pull to refresh

Магия шаблонов или вычисление факториала на стадии компиляции

C++
Доброго времени суток, Хабралюди!

Гуру C++, а также люди смыслящие в шаблонном метапрограммировании могут смело пропускать этот топик, ничего нового для себя они здесь не найдут. Однако, если после прочтения заголовка, у вас в голове еще не возникло решение данной задачи (и даже если оно возникло, но не при помощи шаблонов), то милости просим под кат.


Собственно, решение задачи:
#include <iostream>

template<int n>
class Factorial {
public:
    static const int f = Factorial<n - 1>::f * n;
};

template<>
class Factorial<0> {
public:        
    static const int f = 1;
};

int main() {
    std::cout << Factorial<5>::f << std::endl; // 120
}


Давайте разберемся, что к чему. Во-первых, некоторые могут спросить — а почему значение вычисляется на стадии компиляции? Ответ — это основа шаблонов в C++. Специализированный код генерируется на стадии компиляции, в зависимости от того каким типом реально был параметризован шаблон. Суть в том, что если вы используете, например, шаблон функции, которая возвращает минимум двух значений:
template<class T> const T& min(const T& a, const T& b) {
    return (a < b) ? a : b;
}

То если использовать в программе, например:
min(2, 3)

То сгенерируется только специализация для типа int. А если написать, что-то вроде:
min(2.0, 3.0)

То сгенерируется специализация для double.

Теперь, возвращаясь к нашему факториалу, можно понять, что для генерации шаблона Factorial<5> должен сгенерироваться шаблон Factorial<4> и так далее до нуля, где в Factorial<0>::f записывается просто единица (за счет явной специализации template<>). Этот последний шаг останавливает «рекурсивную» генерацию шаблонов, после чего вычисляется само значение факториала. Почему на стадии компиляции? Потому что константа static const int f является константой времени компиляции. Если кто-то не верит в это, можете задать какое-нибудь значение шаблона в качестве длины массива, и наблюдать спокойную компиляцию программы.

В книге Брюса Эккеля Философия С++. Практическое программирование. Приводится следующее решение этой задачи (которое по сути ничем не отличается от вышеописанного):
template<int n>
struct {
    enum {val = Factorial<n - 1> * n};
};

template<>
struct Factorial<0>{
    enum {val = 1};
};


Вообще, такое вычисление факториала является частным случаем шаблонного метапрограммирования. Например, возведение в степень q, целого числа p, можно было бы написать циклом:
int power = 1;
while (q--)
    power *= p;


Но также можно и при помощи шаблонного метапрограммирования:
template<int p, int q>
class Power {
public:
    static const int value = p * Power<p, q - 1>::value;
};

template<int p>
class Power<p, 0> {
public:
    static const int value = 1;
}


Более подробно об этом можно прочесть, например, у Эккеля, в книге Философия С++. Практическое программирование, или у Александреску в книге Современное проектирование на C++.

Спасибо за внимание!
Tags:c++factorialшаблоныtemplateмагия шаблонов
Hubs: C++
Total votes 70: ↑48 and ↓22 +26
Views13.6K

Popular right now

Разработчик C++
from 290,000 to 300,000 ₽ВГТМосква
C++
from 100,000 to 300,000 ₽OvisionСанкт-Петербург
Senior C++ / JS Developer
from 200,000 to 300,000 ₽ZennoLabRemote job
Gameplay UE4 C++ Developer
from 200,000 ₽Omniverse GamesСанкт-Петербург
Python / C++ разработчик
from 150,000 to 230,000 ₽Wunder FundRemote job