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!

Herl

#388742 – Lawrencelawrencium

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.

Defelice

Non-type template parameters are not limited to integers. They can be any integral or enumeration type, pointer to object or pointer to function, reference to object or reference to function, or pointer to member. – Downfall

@Benoît: I don't know much about templates, but shouldn't it be template <0> struct Factorial instead of template <> struct Factorial<0> in the second case? – Herl

@Benoît: Also, what is the use of enum the way it is used? – Herl

Type <strike>arguments</strike> parameters cannot be prefixed by struct. Doing so will declare a non-type parameter: template<struct A> struct H { }; is ill-formed because the non-type parameter is of class-type. – Hedgehop

@R Samuel: You forgot templates. There's template template arguments. – Preprandial

@Lazer: No, template <> struct Factorial<0> really is the correct syntax. No further explanation, this is just the way the syntax for a specialization was specified. – Preprandial

"calling Factorial<4>::value is equivalent to calling a function that simply returns 24" Actually it has even less overhead than a function call. It's equivalent to using an enum value that has been defined to be 24, which is basically equivalent to just writing int value = 24; directly. – Aubyn

@Benoît: I removed the code formatting and made it quotes instead, which seems easier to read for me. I hope that's Ok with you. – Preprandial

Benoit, you really should fix whats allowed for parameters - see §14.1/4. Also, as sepp2k hints, an enum is a compile-time constant and as such very different from a function call. – Economics

How is it possible that 2 structs with identical name can establish without any compilation error? – Yorgos

@Nguaial you may want to take a look at Substitution failure is not an error (SFINAE) – Menadione

@Nguaial: Your mistake is thinking there are two structs. There is actually only one, or many potential structs (one for each legal int value), depending on how you look at it (really, there is one template, with many possible instantiations of it). All but one of the many potential structs is defined by the definition templated on int n; one of them is an explicit specialization of that template for the case of n == 0. Any time templates get involved you have many (often theoretically infinite) structs with the same name; that's why C++ name-mangling is so much more complex than C's. – Lachish

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.

Prowel

The multiplication is still executed at runtime. Only the preparation of the operation was made at compile time. – Emmott

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

---

Herl

If you want to link to a related answer, use comments for that. Don't just copy/paste the full answer without any additions by yourself. – Economics

Answer 4

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

Synchrocyclotron

Answer 5

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.

Karyogamy