Template metaprogramming

By , last updated November 7, 2017

As we remember from the C++ templates introduction, the template argument will swallow anything and everything. This chapter is about intermediate to advanced use of templates in C++ and how to restrict the template parameters.

Specialized class templates

Some of the basic properties of class templates, is that they can inherit other class templates. And even so, those class templates can be specialized so they may contain a certain value or a type based on the template parameter. And all template parameters are computed and checked at compile time. This means there is zero run time overhead.

This is also called template metaprogramming.

Factorial

To get a feeling on how C++ template metaprogramming works, we’ll study the factorial example from Wikipedia, and then use some of the newer C++11 features to expand it somewhat.

In mathematics, the factorial of a non-negative integer n, denoted by n!, is the product of all positive integers less than or equal to n. For example, $5! = 5 * 4 * 3 * 2 * 1 = 120$

The mathematical definition is can be looked up at Wikipedia.

Implementation

It’s possible to implement the factorial computation at runtime by using recursion. The compile time computation is similar. While doing recursion, there must be at a minimum a general case, and a specialized stop case.

The general implementation is calculating the factorial for N, by multiplying it with N-1. The stop case is when N = 0, then the result is 1.

Using the algoritmic notation, it’s $N! = N * (N - 1) * (N - 2)$.

The factorial example is an example for doing computation at compile time. Any computation with a constant input and constant output are eligible for compile time computation.

The complete factorial example.

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

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

Using the factorial is straight forward. Specify the factorial you want as a template parameter, and accept that value.

int f5 = factorial<5>::value;

Looking at the disassembly of the running binary, it’s possible to actually see it’s computed at compilation time. Even in Debug.

int f5 = factorial<5>::value;
000000013F20234C  mov         dword ptr [f5],78h
^^^ 78h is 120,
which is 5!

Due to the explosive nature of factorials, the 32-bit and 64-bit limit is reached very quickly.

For 32-bit integers, the limit is 13!, or 1932053504.

For 64-bit integers, the limit is 20!, or 2432902008176640000.

Better factorial example (C++11)

Now we’ve hit some limits with the factorial from the previous section. We’d like to use double for increased range. The precision is not too great a bigger numbers, but the general range is about +/-10^308.

Using double instead of int is easier said than done. The problem using double for compile time computation, is that they are not permitted as a constant template parameter. It’s not possible to use double in enums.

// Illegal code ahead
template<double d> void illegal(){}

// Illegal code ahead
enum illegal_storage : double { d };

With C++11, we can use constexpr and equal initializer to compute double at compilation time.

constexpr is a compile time constant, while equal initializer is initializing a member variable with the equals sign =.

struct Foo {
int a = 0; // Equal initializer
};

The better factorial computation class should:

• Be able to use any type.
• Computed at compile time.

To achieve this, we’ll need to use some C++11 features. With the latest Visual C++ 2015 compiler, support for C++11 is getting more and more mainstream.

To be able to use any type, we’ll have to abandon enum, and use a static member variable. To force the compiler to compute the value at compile time, we need to use the constexpr keyword too.

The better factorial looks like this.

// General case
template<unsigned int n, typename T = unsigned int>
struct fact
{
static constexpr T factorial = n * fact<n - 1, T>::factorial;
};

// Specialized stop case
template<typename T>
struct fact<0, T>
{
static constexpr T factorial = 1;
};

Some sample usages of the above factorial. The following variables f1 and f5 contains the compile time constants of
1!
and
5!
.

constexpr auto f1 = fact<1>::factorial; // Factorial of 1 (1!)
constexpr auto f5 = fact<5>::factorial; // Factorial of 5 (5!)

The disassembly is identical to the previous factorial.

constexpr auto f5 = fact<5>::factorial;
000000013F6F5D46  mov         dword ptr [f5],78h
^^^ 78h is 120,
which is 5!

We can specify a custom type. If not, it will default to unsigned int, in addition to the factorial number.

To use double as storage, specifiy it as an template argument.

constexpr auto d10 = fact<10, double>::factorial;
// d10 is a double with value 3628800

The disassembly is different because we’re using a double as storage.

constexpr auto d5 = fact<5, double>::factorial;
000000013F6F5D4D  movsd       xmm0,mmword ptr
[__real@405e000000000000 (013F6FAC40h)]
000000013F6F5D55  movsd       mmword ptr [d5],xmm0

Advantages to the better factorial.

• Can use any type for T, which supports compile time computation and integer / floating point arithmetic.
• auto will not deduce the factorial to factorial<1>::<unnamed-enum-value>, but the actual type.

Fibonacci sequence

The Fibonacci series is the series where the next number is the sum of the two preceeding numbers.

The series starts with numbers 0, 1, 1, 2, 3, 5, 8 and continues. The task is to make a compile time computation, which computes number N in the series. As with the factorial, there is one generic case, and two special cases.

The generic case is in pseudocode fib(N) = fib(N-1) + fib(N-2).

// General case
template<unsigned int N>
struct fibonacci
{
static constexpr int64_t value =
fibonacci<N - 2>::value +
fibonacci<N - 1>::value;
};

The first special case is the value at position 1, which is 0.

// Special case, value 0
template<>
struct fibonacci<0>
{
static constexpr int64_t value = 0;
};

The second special case is the value at position 2, which is 1.

// Special case, value 1
template<>
struct fibonacci<1>
{
static constexpr int64_t value = 1;
};

Changing the int64_t type into a template type is left as an exercise to the reader.

Sample usage.

constexpr auto fib0 = fibonacci<0>::value; // 0
constexpr auto fib1 = fibonacci<1>::value; // 1
constexpr auto fib2 = fibonacci<2>::value; // 1
constexpr auto fib3 = fibonacci<3>::value; // 2
constexpr auto fib4 = fibonacci<4>::value; // 3
constexpr auto fib5 = fibonacci<5>::value; // 5
constexpr auto fib6 = fibonacci<6>::value; // 8

With 64-bit int, the maximum Fibonacci number is the 92th number, which equals to 7540113804746346429. Anything more will overflow.

The assembly show this is a value computed at compile time.

auto fib91 = fibonacci<91>::value;
000000013FF4238C  mov         rax,40ABCFB3C0325745h
000000013FF42396  mov         qword ptr [fib91],rax
auto fib92 = fibonacci<92>::value;
000000013FF4239A  mov         rax,68A3DD8E61ECCFBDh
000000013FF423A4  mov         qword ptr [fib92],rax

Restricting with std::enable_if

After the mathematical introduction with template metaprogramming, the rest of the chapter will focus on useful usage of template metaprogramming.

One of the more powerful, but lesser known uses of the standard library is type_traits. It’s used to do useful stuff at compile time, like enabling a method only if a certain condition is met, or the opposite. It’s quite powerful and it’s usage is straight forward once you get to know it.

All code in this section assumes the header type_traits is included.

#include <type_traits>

The template class std::enable_if is powerful, and it’s designed to be used in conjuction with other template classes in type_traits.

The basic usage is to either enable or disable certain functionality, at compile time.

Consider this function template, it will accept any template parameter.

template<typename T>
void accept_anything(const T param)
{}

Whatever you use as T, your program will compile and build. When you’re creating that method, you may or may not assume certain use cases where certain types are excluded, or it’s limited to certain types. It can be either integral types, floating point types, constant types, pointers, references or universal references.

When those constraints are broken, in the best case you will get a very nasty error message. In the worst case scenario, your code will break silently.

The simplest use case of std::enable_if is accepting all template parameters, like the above method.

// Accept anything, number two
template<typename T>
typename
std::enable_if<true>::type accept_anythine_2(const T param)
{}
//             ^^^^
//             True case, where ::type is available.
//             Default type is void

The following is the opposite case, and this case will not build. std::enable_if have two specializations, where the true case exposes the ::type, while the false case does not expose ::type.

// Unbuildable code ahead. Accepts nothing
template<typename T>
typename
std::enable_if<false>::type accept_nothing(const T param)
{}
//             ^^^^^
//             False case, where ::type is not available.

Using the newly acuired knowledge, it’s possible to create a template class or method where the template type must be int. For this we can use std::is_same. It resides in the same header, type_traits.

// Accept only ints
template<typename T>
typename std::enable_if<            // Start enable_if
std::is_same<int, T>::value     // True/false check
>::type accept_int(const T param)   // Type (void)
{}

// Accept only doubles
template<typename T>
typename std::enable_if<              // Start enable_if
std::is_same<double, T>::value    // True/false check
>::type accept_double(const T param)  // Type (void)
{}

These two methods will only accept either ints (accept_int), or doubles (accept_double).

int i = 0;
double d = 0;

accept_int(i);  // Compiles
accept_int(d);  // Will not compile

It’s also possible to negate with !. If you absolutely don’t like int, we can discriminate int, while accepting any other type.

// Accept anything, except int
template<typename T>
typename std::enable_if<
!std::is_same<int, T>::value        // Negate with !
>::type dont_accept_int(const T param)
{}
int i = 0;
double d = 0;

dont_accept_int(i);     // Will not compile
dont_accept_int(d);     // Compiles

Using the std::is_pointer template, it’s possible to discriminate if the type is pointer or not.

// Accept pointers only
template<typename T>
typename std::enable_if<
std::is_pointer<T>::value           // Accept pointer only
>::type accept_pointer(const T param)
{}

This example is perhaps somewhat contrived, but it starts to show the potential with templates and template metaprogramming.

// Accept either non-pointer integers,
// or void* pointers, and return 42 if so.
template<typename T>
typename std::enable_if<
std::is_same<T, int>::value ||          // Check for int, or
(
std::is_same<void*, T>::value &&    // Is void*, and
std::is_pointer<T>::value           // Is pointer
),
int                                     // Return int
>::type accept_int_or_void_star(const T param)
{
return 42;
}

The usage is as follows.

int i = 0;
int *p = nullptr;
void *vp = nullptr;

accept_int_or_void_star(i);     // Compiles
accept_int_or_void_star(p);     // Will not compile
accept_int_or_void_star(vp);    // Compiles

This just scratches the surface of type_traits and how powerful templates are. Professional Software Developer, doing mostly C++. Connect with Kent on Twitter.