Метаалгоритм вычисления факториала
Это классический пример метапрограммирования на C++. Он демонстрирует три вещи в метаалгоритмах C++: переменные, циклы и альтернативы (ветвления).
#include <iostream>
template<int N>
struct Factorial
{
enum { value = N * Factorial<N-1>::value };
};
template<>
struct Factorial<1>
{
enum { value = 1 };
};
int main()
{
// Example use
const int fact5 = Factorial<5>::value;
std::cout << fact5;
return 0;
}
Константа fact5 в ходе компиляции получает значение 120 - факториал числа 5 (произведение 1*2*3*4*5). Все вычисления происходят именно на стадии компиляции. Цикл организуется рекурсивной подстановкой шаблона Factorial<T>, условие окончания цикла - специализация шаблона Factorial<1>. В качестве переменной цикла используется оператор enum. Приглядитесь к объявлению поля enum { value } в теле цикла - рекурсия и перемножения сидят именно там.
Как работает метацикл
Любой цикл в метапрограмме организуется так, как в этом примере - через рекурсию. Поэтому давайте немного подробнее остановимся на том, какие же действия выполняет компилятор C++ при вычислении факториала.
Итак, исполнение метаалгоритма начинается со строчки
const int fact5 = Factorial<5>::value;
в функции main. К этому времени компилятор знает определение шаблона Factorial<N> и его специализацию (частный случай) Factorial<1>. Для вычисления Factorial<5> подходит только общее определение шаблона, поэтому компилятор подставляет целочисленный аргумент 5 в параметр N шаблона и начинает развертывание описание шаблона, заменяя N везде на 5.
Дойдя до объявления перечисления enum в теле шаблона, компилятор обнаруживает, что первый элемент перечисления определен как произведение параметра N шаблона на константу, определенную как поле шаблона с параметром N-1 (то есть 4). Теперь компилятор должен создать специализацию шаблона Factorial для параметра 4.
Так возникает рекурсия специализаций шаблона Factorial для значений аргумента N равных 5, 4, 3, 2.
Как же прерывается цикл (рекурсия)? Благодаря явно объявленной специализации Factorial<1>. Правила развертывания шаблонов в C++ таковы, что компилятор сам делает специализацию только в том случае, если в программе ему не встретилась явно объявленная специализация. В определении Factorial<1> поле перечисления enum определено как 1, то есть далее продолжать рекурсию не надо.
В итоге, выполнив все подстановки, компилятор получает во время компиляции значение константы fact5 равное 120.
Ограничения на рекурсию
При написании метапрограмм следует помнить, что максимально допустимая глубина рекурсии - вещь неопределенная, для каждой версии компилятора она индивидуальная. Поэтому вполне может статься, что вышеприведенный пример не будет работать вообще, или он не сможет вычислить факториал чисел больше 17 - проверьте самостоятельно.
Скачать пример
Файл factorial.cpp (293 байта)
© Mental Computing 2010
