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

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

Гуру 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++.

Спасибо за внимание!