C++ Template Meta Programming – Part 1

You may have heard of template meta programming before. It is a technique that uses the features of C++ templates to shift program execution from runtime to compile time. Basically, we are going to trick the compiler into running our code at compile time and then putting the output into our executable.

Let’s look at an example:

#include <iostream>

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

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

int main() {
    std::cout << Factorial<5>::value << std::endl;
    return 0;
}

What does this code do? Well, first we define a templated struct that takes an integer as a parameter.

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

Notice, that inside this struct, we define a field named value. This field is defined to be n times the value field of Factorial<n-1>. We are also using total template specialisation:

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

This means that if we ever specialise the Factorial template with the parameter 0 it will use this version of Factorial that defines the value field to be 1.

So, when we specialise the Factorial template with the parameter 5, the compiler creates the classes Factorial<5>, Factorial<4>, Factorial<3>, Factorial<2>, Factorial<1> and Factorial<0>. Then it computes the value field for each of these classes. The value field for Factorial<0> is 1. The compiler calculates the value field for each successive Factorial<n> by multiply n times the value field of the previous Factorial specialisation. So we have defined a recursion that calculates the factorial of an integer. What is weird is that this calculation happens entirely at compile time. When we run this code, the first six values of the factorial series have already been calculated, and we will just be reading the last value from the code the compiler has created.

We can do exactly the same thing with the Fibonacci numbers:

#include <iostream>

template<int n>
struct Fibonnaci
{
    enum { value =  Fibonnaci<n - 1>::value + Fibonnaci<n - 2>::value };
};

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

template<>
struct Fibonnaci<1>
{
    enum {value = 1};
};

int main() {
    std::cout << Fibonnaci<5>::value << std::endl;
    return 0;
}

So we have seen how to do recursions via template meta programming. Next we will see how to write conditional statements that are evaluated at compile time.