The building blocks of C++ template meta-programming are usually `struct`

s without any data members encapsulating a value stored in an `enum`

. As a simple example consider

This can be used to store an integer as a plain value. It has no address at run-time, since it is not a data member. Storing and retrieving the value is done as follows:

Storing and retrieving values is not very exciting, but actually computing something using types *is*. The simplest way to do so is to exploit recursive definition of types. An instructive example is the Fibonacci sequence:

Compiling the above will throw errors at us, because the compiler gets stuck in an infinite recursion. This is clearly reflected in the error message, where it shows the compiler quits at depth 256:

Note the overflow in the template parameter, which happens because `size_t`

is unsigned.

To stop the recursion, we must implement a base case for x = 0 and x = 1. This is done via specialization:

Now the compiler does its job and evaluates `Fibonacci<10>::value`

to 55, which happens to be the tenth Fibonacci number.

## Primality test using template meta-programming

A trivial primality test for a number p, is to do a linear scan over the numbers 2 to p - 1 and check whether p is divisible by none of them. Of course there are all kinds of improvements to make, but for the sake of simplicity we will not pursue these. The primality test is implemented using the following recursion

The specialization `PrimalityTest<p, 1>`

guarantees the compiler will not get stuck in infinite recursion limbo. Furthermore, any prime number is of course divisible by 1, so `PrimalityTest<p, 1>::value == 1`

. For any other `i`

the value of `PrimalityTest<p, i>::value`

will be 1 if `p`

is neither divisible by `i`

nor by any number less than `i`

. The latter part is handled recursively.

To call the primality test we can create another struct that does exactly this:

It simply states that a number `p`

is prime if it is not divisible by any number smaller than `p`

. A quick sanity check shows that this indeed works:

As a concluding remark for this section, a very handy tool to do compile-time testing is `static_assert(bool_constexpr, message)`

which arrived in C++11. Not only can it be used for testing, but as well to convince yourself it is really the compiler which evaluates an expression. In our example we can use it as follows:

## A modern alternative in C++14

Template meta-programming is very powerful, yet as a programming language it generates an enormous cognitive load. Although it sometimes has the looks of a quite mature functional programming language, it also gives the feeling of abuse of what probably is a C++ by-product. Indeed, historically Turing-completeness of the templating system was not a goal, but a welcome surprise.

To make life easier, C++11 introduced the notion of `constexpr`

functions and variables. This identifier tells the compiler that the value of the function or variable can be evaluated at compile-time. As a simple example, our recursive Fibonacci function can be implemented as a one-liner `constexpr`

function:

This piece of code is almost indistinguishable from the code you would normally write in C++, except for its overdone compactness and recursive inefficiency.

A more efficient implementation would be non-recursive:

However, this piece of code only compiles in C++14. Why? In C++11 `constexpr`

functions cannot contain variable declarations and should in fact be as simple as a return statement. C++14 has greatly extended the allowed contents of a `constexpr`

function body, which makes it possible to write code identical to what you would write for run-time functions.

## A compile-time prime sieve for counting prime numbers

As a final example to appreciate the beauty and extend of what `constexpr`

can do, let’s implement a compile-time prime counting function using the sieve of Eratosthenes. The function `count_primes<N>()`

returns the number of primes strictly smaller than `N`

. Using some well-known prime sieving trickery, a relatively efficient implementation is:

Let’s throw some compile-time tests at it for `N`

as large as 10000:

The above code compiles just fine, which can only mean that *the compiler can count prime numbers efficiently in just 22 human-readable lines of code*.

Unfortunately we cannot pass `N`

as a function parameter rather than a template parameter, as `bool is_prime[N]`

would then be interpreted as a variable-sized object.

### Can we improve further? What are the limitations?

One idea is to use STL algorithms to initialize the array with `true`

as values. The problem however is that `std::fill`

is not (and probably will never be) a `constexpr`

function. This is because it will resort to `memset`

to initialize the memory whenever it can.

We could also try to use `std::array`

as an abstraction, but this has a `constexpr`

implementation for `operator[](size_t) const`

only from C++17 onwards. At the time of writing this seems not implemented in Clang 8.0.

A very obvious limitation is of course the possibility of a stack overflow for large values of N, but compile-time computations of that magnitude make probably little sense.

## Concluding remarks

C++ has come a long way from the discovery of template meta-programming to the very versatile `constexpr`

identifier. Even if you’re sceptical about its practical usefulness (which you shouldn’t), the power of the language and in particular its compiler can leave you stunned.