C++ Metaprogramming Calculating Factorials
Example
Factorials can be computed at compile-time using template metaprogramming techniques.
#include <iostream>
template<unsigned int n>
struct factorial
{
enum
{
value = n * factorial<n - 1>::value
};
};
template<>
struct factorial<0>
{
enum { value = 1 };
};
int main()
{
std::cout << factorial<7>::value << std::endl; // prints "5040"
}
factorial is a struct, but in template metaprogramming it is treated as a template metafunction. By convention, template metafunctions are evaluated by checking a particular member, either ::type for metafunctions that result in types, or ::value for metafunctions that generate values.
In the above code, we evaluate the factorial metafunction by instantiating the template with the parameters we want to pass, and using ::value to get the result of the evaluation.
The metafunction itself relies on recursively instantiating the same metafunction with smaller values. The factorial<0> specialization represents the terminating condition. Template metaprogramming has most of the restrictions of a functional programming language, so recursion is the primary "looping" construct.
Since template metafunctions execute at compile time, their results can be used in contexts that require compile-time values. For example:
int my_array[factorial<5>::value];
Automatic arrays must have a compile-time defined size. And the result of a metafunction is a compile-time constant, so it can be used here.
Limitation: Most of the compilers won't allow recursion depth beyond a limit. For example, g++ compiler by default limits recursion depeth to 256 levels. In case of g++, programmer can set recursion depth using -ftemplate-depth-X option.
C++11
Since C++11, the std::integral_constant template can be used for this kind of template computation:
#include <iostream>
#include <type_traits>
template<long long n>
struct factorial :
std::integral_constant<long long, n * factorial<n - 1>::value> {};
template<>
struct factorial<0> :
std::integral_constant<long long, 1> {};
int main()
{
std::cout << factorial<7>::value << std::endl; // prints "5040"
}
Additionally, constexpr functions become a cleaner alternative.
#include <iostream>
constexpr long long factorial(long long n)
{
return (n == 0) ? 1 : n * factorial(n - 1);
}
int main()
{
char test[factorial(3)];
std::cout << factorial(7) << '\n';
}
The body of factorial() is written as a single statement because in C++11 constexpr functions can only use a quite limited subset of the language.
C++14
Since C++14, many restrictions for constexpr functions have been dropped and they can now be written much more conveniently:
constexpr long long factorial(long long n)
{
if (n == 0)
return 1;
else
return n * factorial(n - 1);
}
Or even:
constexpr long long factorial(int n)
{
long long result = 1;
for (int i = 1; i <= n; ++i) {
result *= i;
}
return result;
}
C++17
Since c++17 one can use fold expression to calculate factorial:
#include <iostream>
#include <utility>
template <class T, T N, class I = std::make_integer_sequence<T, N>>
struct factorial;
template <class T, T N, T... Is>
struct factorial<T,N,std::index_sequence<T, Is...>> {
static constexpr T value = (static_cast<T>(1) * ... * (Is + 1));
};
int main() {
std::cout << factorial<int, 5>::value << std::endl;
}
