Template magic or factorial computing at compilation stage

Good day, Habralyudi!

The C ++ guru, as well as people who know template metaprogramming, can safely skip this topic, they will not find anything new for themselves here. However, if after reading the headline, you still haven’t got a solution to this problem (and even if it arose, but not with the help of templates), then you are welcome under cat.


Actually, the solution to the problem:

#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
}

Let's see what's what. Firstly, some may ask - why is the value computed at the compilation stage? The answer is the basis of templates in C ++. Specialized code is generated at the compilation stage, depending on what type the template was actually parameterized. The bottom line is that if you use, for example, a function template that returns a minimum of two values:

template const T& min(const T& a, const T& b) {
    return (a < b) ? a : b;
}

Then if used in a program, for example:

min(2, 3)

That only specialization for type int is generated . And if you write, something like:

min(2.0, 3.0)

That generates a specialization for double .

Now, returning to our factorial, we can understand that in order to generate the Factorial <5> template, the Factorial <4> template must be generated and so on to zero, where just one is written in Factorial <0> :: f (due to the explicit specialization of template < > ). This last step stops the "recursive" generation of templates, after which the factorial value itself is calculated. Why at compilation stage? Because the constant static const int f is a compile time constant. If someone does not believe in this, you can set some value of the template as the length of the array, and observe a quiet compilation of the program.

In Bruce Eckel's book Philosophy of C ++. Practical programming. The following solution to this problem is given (which essentially does not differ from the above):

template
struct {
    enum {val = Factorial * n};
};
template<>
struct Factorial<0>{
    enum {val = 1};
};

In general, such a factorial calculation is a special case of template metaprogramming. For example, raising to a power q, an integer p, could be written in a loop:

int power = 1;
while (q--)
    power *= p;

But it is also possible with the help of template metaprogramming:

template
class Power {
public:
    static const int value = p * Power::value;
};
template
class Power {
public:
    static const int value = 1;
}

You can read more about this, for example, with Eckel, in the book Philosophy C ++. Practical programming , or in Alexandrescu's book Modern Design in C ++ .

Thanks for attention!