C++ / Магия шаблонов или вычисление факториала на стадии компиляции
C++ / Магия шаблонов или вычисление факториала на стадии компиляции
Доброго времени суток, Хабралюди!
Гуру C++, а также люди смыслящие в шаблонном метапрограммировании могут смело пропускать этот топик, ничего нового для себя они здесь не найдут. Однако, если после прочтения заголовка, у вас в голове еще не возникло решение данной задачи (и даже если оно возникло, но не при помощи шаблонов), то милости просим под кат.
Собственно, решение задачи:
#include
template
class Factorial {
public:
static const int f = Factorial::f * n;
};
template<>
class Factorial<0> {
public:
static const int f = 1;
};
int main() {
std::cout << Factorial<5>::f << std::endl; // 120
}
Давайте разберемся, что к чему. Во-первых, некоторые могут спросить - а почему значение вычисляется на стадии компиляции? Ответ - это основа шаблонов в C++. Специализированный код генерируется на стадии компиляции, в зависимости от того каким типом реально был параметризован шаблон. Суть в том, что если вы используете, например, шаблон функции, которая возвращает минимум двух значений:
template const T& min(const T& a, const T& b) {
return (a < b) ? a : b;
}
То если использовать в программе, например:
min(2, 3)
То сгенерируется только специализация для типа int. А если написать, что-то вроде:
min(2.0, 3.0)
Или
min(2.0, 3)
То сгенерируется специализация для double.
Теперь, возвращаясь к нашему факториалу, можно понять, что для генерации шаблона Factorial<5> должен сгенерироваться шаблон Factorial<4> и так далее до нуля, где в Factorial<0>::f записывается просто единица (за счет явной специализации template<>). Этот последний шаг останавливает «рекурсивную» генерацию шаблонов, после чего вычисляется само значение факториала. Почему на стадии компиляции? Потому что константа static const int f является константой времени компиляции. Если кто-то не верит в это, можете задать какое-нибудь значение шаблона в качестве длины массива, и наблюдать спокойную компиляцию программы.
В книге Брюса Эккеля Философия С++. Практическое программирование. Приводится следующее решение этой задачи (которое по сути ничем не отличается от вышеописанного):
template
struct {
enum {val = Factorial * n};
};
template<>
struct Factorial<0>{
enum {val = 1};
};
Вообще, такое вычисление факториала является частным случаем шаблонного метапрограммирования. Например, возведение в степень q, целого числа p, можно было бы написать циклом:
int power = 1;
while (q--)
power *= p;
Но также можно и при помощи шаблонного метапрограммирования:
template
class Power {
public:
static const int value = p * Power
::value;
};
template
class Power
{
public:
static const int value = 1;
}
Более подробно об этом можно прочесть, например, у Эккеля, в книге Философия С++. Практическое программирование, или у Александреску в книге Современное проектирование на C++.
Спасибо за внимание!
Original source: habrahabr.ru (comments).