calculating factorial using template meta-programming

Question

I do not understand how this piece of code (from Wikipedia) works:

template <int N>
struct Factorial 
{
    enum { value = N * Factorial<N - 1>::value };
};

template <>
struct Factorial<0> 
{
    enum { value = 1 };
};

// Factorial<4>::value == 24
// Factorial<0>::value == 1
void foo()
{
    int x = Factorial<4>::value; // == 24
    int y = Factorial<0>::value; // == 1
}

• What is this weird template that takes <int N>?
• What is this second weird template <>?
• What are the enumerations for?
• What is the advantage of using this rather than normal runtime factorial calculation?
• How often do you people use this? I have been using C++ for a while now, but never used this before. How big a part of C++ was I missing out on?

Thanks!

Answer 1

What is this weird template that takes <int N>?

A template declaration can be made on classes/types, on values and on pointers. You do not usually see this form as defining templates rarely uses constants in the template parameters.

What is this second weird template <>?

The best way to think of a template is to do something similar to what the compiler does: consider the template as a class, where you replace the template parameter with an actual value of that type.

That is, for:

template <int N>
struct Factorial 
{
    enum { value = N * Factorial<N - 1>::value };
};

Factorial<2>::value is equivalent to:

// generated by the compiler when Factorial<2>::value is encountered in code:
struct Factorial2 { enum { value = 2 * Factorial1::value }; };
struct Factorial1 { enum { value = 1 * Factorial0::value }; };
// not generated by compiler, as it was explicitly defined in the code you ask about:
template <> struct Factorial<0> { enum { value = 1 }; }; // defines Factorial<0>

What are the enums for?

They define an enumeration with a const value at compile time, allowing you to write client code like the one in your example.

What is the advantage of using this rather than normal runtime factorial calculation?

The advantage is efficiency. Since the value calculation is expanded on compilation, the runtime cost of Factorial<10>::value is the same as Factorial<1>::value. In the compiled code, they are both constants. If you were to calculate a factorial in performance-critical code and you knew at compile time which value it is, you should either do this, or calculate it offline and define a constant with the precalculated value in your code.

How often do you people use this?

Is the "this" you refer to the recursive computation of a constant? If so, not often.

Is the "this" the definition of constants in templates? Very often :)

Is the "this" the particularization of a template for a specific type? Very Very Very often. I understood that std::vector has a completely separate implementation in some STL implementations (a std::vector<bool> with 8 elements should not need more than 1 byte for storing the values).

I have been using C++ for a while now, but never used this before. How big a part of C++ was I missing out on?

Not necessarily a big part. If you use boost, it is probable that the code you use is implemented using things like this.

Answer 2

• What is this weird template that takes <int N>?

In C++, template arguments can either be types (prefixed with class or typename) or integers (prefixed with int or unsigned int). Here we are in the second case.

• What is this second weird template <>?

template<> struct Factorial<0> is a complete specialization of Factorial class template, which means that 0 is considered a special value to which corresponds its own version of Factorial.

• What are the enums for?

enums are the way to compute values in metaprogramming C++

• What is the advantage of using this rather than normal runtime factorial calculation?

The reason why this code was created in the first place is to create a proof of concept that calculus can be done using metaprogramming. The advantage is that generated code is extremely efficient (calling Factorial<4>::value is equivalent to simply writing "24" in your code.

• How often do you people use this? I have been using C++ for a while now, but never used this before. How big a part of C++ was I missing out on?

Such functionality is rarely achieved using this method, but metaprogramming is used more and more nowadays. See Boost meta-programming library to get a hint of what can be done.

Answer 3

I found this answer by Johannes Schaub - litb on a different question very helpful.

[ I am copy pasting the answer here, assuming Johannes is okay with it. I'll remove the paste if he doesn't like it ]

---

Yes, it is a non-type parameter. You can have several kinds of template parameters

• Type Parameters.
  • Types
  • Templates (only classes, no functions)
• Non-type Parameters
  • Pointers
  • References
  • Integral constant expressions

What you have there is of the last kind. It's a compile time constant (so-called constant expression) and is of type integer or enumeration. After looking it up in the standard, i had to move class templates up into the types section - even though templates are not types. But they are called type-parameters for the purpose of describing those kinds nonetheless. You can have pointers (and also member pointers) and references to objects/functions that have external linkage (those that can be linked to from other object files and whose address is unique in the entire program). Examples:

Template type parameter:

template<typename T>
struct Container {
    T t;
};

// pass type "long" as argument.
Container<long> test;

Template integer parameter:

template<unsigned int S>
struct Vector {
    unsigned char bytes[S];
};

// pass 3 as argument.
Vector<3> test;

Template pointer parameter (passing a pointer to a function)

template<void (*F)()>
struct FunctionWrapper {
    static void call_it() { F(); }
};

// pass address of function do_it as argument.
void do_it() { }
FunctionWrapper<&do_it> test;

Template reference parameter (passing an integer)

template<int &A>
struct SillyExample {
    static void do_it() { A = 10; }
};

// pass flag as argument
int flag;
SillyExample<flag> test;

Template template parameter.

template<template<typename T> class AllocatePolicy>
struct Pool {
    void allocate(size_t n) {
        int *p = AllocatePolicy<int>::allocate(n);
    }
};

// pass the template "allocator" as argument. 
template<typename T>
struct allocator { static T * allocate(size_t n) { return 0; } };
Pool<allocator> test;

A template without any parameters is not possible. But a template without any explicit argument is possible - it has default arguments:

template<unsigned int SIZE = 3>
struct Vector {
    unsigned char buffer[SIZE];
};

Vector<> test;

Syntactically, template<> is reserved to mark an explicit template specialization, instead of a template without parameters:

template<>
struct Vector<3> {
    // alternative definition for SIZE == 3
};

---

Answer 4

What is the advantage of using this rather than normal runtime factorial calculation?

It's faster - theoretically the compiler will expand the set of templates at compile time such that Factorial<n>::value is simply a single constant. In some vanishingly small number of cases, that might make quite a difference.

The down side to it is that it has to be calculated at compile time, so if your n is determined at runtime then you can't use that method.

How often do you people use this? I have been using C++ for a while now, but never used this before. How big a part of C++ was I missing out on?

A case like that, not often at all. Template metaprogramming is potentially very powerful, but the number of cases where this example is useful and important enough for performance are tiny.

But it is a useful technique in C++ since it allows the language to do a lot of powerful tricks that would otherwise be out of reach. I'd venture that it's much more common to take advantage of template metaprogramming that someone else has done for you - eg. Boost uses it quite heavily and can do some very clever things as a result. It's powerful, but can also obfuscate code if not done well.

Answer 5

It's recursion performed by the compiler, where

template <>
struct Factorial<0>
{
}

is exit point of the recursion.

At first Factorial<4> is resolved. There is no specialization of Factorial for the value 4, so the first definition Factorial<> is used. It's value is then calculated with Factorial<3>::value, where the previous step is repeated.

This will go on, until N==1, then for N-1, the specialization Factorial<0> comes into play, where the value is set to 1. The recursion stops here and the compiler can go upwards and calculates the remaining values of Factorial<N>.