Pattern Magic or Factorial Calculation at Compile Stage

Good day, Habraludi!

C ++ C ++ gurus, as well as people who understand conceptual metaprogramming, can safely skip this topic, they will not find anything new for themselves here. However, if after reading the title, you have not yet had a solution to this problem in your head (and even if it arose, but not using templates), then you are welcome under cat.


Actually, the solution of the problem:

#include <iostream> template<int n> class Factorial { public: static const int f = Factorial<n - 1>::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. First, some may ask - why is the value calculated at the compilation stage? The answer is the basis of patterns in C ++. Specialized code is generated at the compilation stage, depending on what type of template was actually parameterized. The bottom line is that if you use, for example, a function template that returns at least two values:

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

So if used in the program, for example:

 min(2, 3) 

That will only generate specialization for the type int . And if you write something like:

 min(2.0, 3.0) 

This will generate specialization for double .

Now, returning to our factorial, it can be understood that to generate the Factorial <5> template, the Factorial <4> template should be generated and so on to zero, where only one is recorded in Factorial <0> :: f (due to the explicit specialization of template < > ). This last step stops the “recursive” generation of patterns, after which the factorial value itself is calculated. Why at compile time? Because the constant static const int f is a compile time constant. If someone does not believe in it, you can specify a template value as the length of the array, and observe a calm compilation of the program.

In Bruce Ekkel's book Philosophy C ++. Practical programming . The following solution to this problem (which in essence is no different from the one described above) is given:

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

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

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

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

 template<int p, int q> class Power { public: static const int value = p * Power<p, q - 1>::value; }; template<int p> class Power<p, 0> { public: static const int value = 1; } 

You can read about this in more detail, for example, in Ekkel, in the book Philosophy C ++. Practical programming , or Alexandrescu in the book Modern Design in C ++ .

Thanks for attention!