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>?

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 2

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

---