Factorials can be computed at compile-time using template metaprogramming techniques.
https://codeeval.dev/gist/ff346afecaaadfe112531619f21eadeb
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.
Since C++11, the std::integral_constant
template can be used for this kind of template computation:
https://codeeval.dev/gist/f5300f79d9c581e1a4ae2e727061e50d
Additionally, constexpr
functions become a cleaner alternative.
https://codeeval.dev/gist/93075d85b13e1cc6b4618d7f64f7a4f8
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.
Since C++14, many restrictions for constexpr
functions have been dropped and they can now be written much more conveniently:
https://codeeval.dev/gist/c5bbe7f6683fc0b215d7c3bf19ddf4d2
Or even:
https://codeeval.dev/gist/a11e241abab84cac0e57dc4d70696401
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;
}