Values at Compile Time

Compile-time computations need to operate on values defined as valid at compile time. Here’s what this notion of compile-time values covers:

• Types, which are entities defined at compile time
• Integral constants, defined by using the constexpr keyword or passed to the template class as template parameters.

Unfortunately, types and integral constants are two completely different beasts in C++. Moreover, there is currently no way in C++11/14/17 to specify a template parameter to be either a type or an integral constant.¹ To be able to work with both kinds of values (types and integral constants), we need a way to make both kinds of values homogeneous.

The standard way to do so, which stems from Boost.MPL, is to wrap the value in a type. We can do this by using std::integral_constant, which we can implement roughly as follows:

template<typename T, T Value>
struct integral_constant
{
  using type = T;
  static constexpr T value = Value;
};

This structure is a simple box containing a value. This box’s type is dependent on both the value and the value type, making it unambiguous.² We can later retrieve either the value type through the ::type internal type definition or the numerical value through the ::value constant.

Because integral constants can be turned easily into types, we can consider that the only required flavor of compile-time values is type. This is such a strong proposition that we will define this as one of our basic axioms in metaprogramming.

Functions at Compile Time

We can view runtime functions as mappings between values of some types and results of a given type (which might be void). In a perfect world, such functions would behave the same way as their mathematical, pure equivalents, but in some cases we might need to trigger side effects (like I/O or memory access).

Functions at compile time live in a world where no side effects can occur. They are, by their very nature, pure functions living in a small functional language embedded in C++. As per our first axiom, the only interesting values in metaprogramming are types. Thus, compile-time functions are components that map types to other types.

This statement looks familiar. It is basically the same definition as that for runtime functions, with “values” replaced by “types.” The question now is, how can we specify such a component when it’s clear C++ syntax won’t let us write return float somewhere?

Again, we take advantage of the pioneering work of Boost.MPL by reusing its notion of the metafunction. Quoting from the documentation, a metafunction is “a class or a class template that represents a function invocable at compile-time.” Such classes or class templates follow a simple protocol. The inputs of the metafunctions are passed as template parameters and the returned type is provided as an internal type definition.

A simple metafunction can be written as follows:

template<class T>
struct as_constref
{
  using type = T const&;
};

As its name implies, this metafunction turns a type into a reference to a constant value of said type.³ Invoking a metafunction is just a matter of accessing its internal ::type, as demonstrated here:

using cref = as_constref<float>::type;

This principle has already leaked from MPL into the standard. The type_traits header provides a large number of such metafunctions, supporting for analyzing, creating, or modifying types based on their properties.

Using Pack-Intrinsic Information

Let’s try to make a simple metafunction that operates on a type container by writing a way to access a container’s size:

template<class List> struct size;
 
template<template<class...> class List, class... Elements> 
struct size<List<Elements...>> 
     : std::integral_constant<std::size_t, sizeof...(Elements)> 
{};

Let’s go over this snippet. First, we declare a size structure that takes exactly one template parameter. At this point, the nature of this parameter is unknown; thus, we can’t give size a proper definition. Then, we partially specialize size for all of the types of the form List<Elements...>. The syntax is a bit daunting, so let’s decompose it. The template parameters of this specialization comprise the following:

List

A template template parameter awaiting a template parameter pack as an argument

Elements

A template parameter pack

From those two parameters, we specialize size<Elements...>. We can write this as Elements..., which will trigger an expansion of every type in the pack, which is exactly what List requires in its own parameters. This technique of describing the variadic structure of a type container so that an algorithm can be specified will be our main tool from now on.

Take a look at how we can use this compile-time algorithm and how the compiler interprets this call. Consider the following as we try to evaluate the size of std::tuple<int,float,void>:

constexpr auto s = size<std::tuple<int,float,void>>::value;

By the definition of std::tuple, this call will match the size<List<Elements...>> specialization. Rather trivially, List will be substituted by std::tuple and Elements will be substituted by the parameter pack {int, float, void}. When it is there, the sizeof... operator will be called and will return 3. size will then inherit publicly from std::integral_constant<std::size_t,3> and forward its internal value constant. We could have used any kind of variadic structure instead of a tuple, and the process would have been similar.

Adding and Removing Pack Elements

The next natural step is to try to modify the elements inside a type container. We can do this by using the structural description of a parameter pack. As an example, let’s try to write push_back<List,Element>, which inserts a new element at the end of a given type container.

The implementation starts in a now-familiar way:

template<class List, class New> struct push_back;

As for size, we declare a push_back structure with the desired type interface but no definition. The next step is to specialize this type so that it can match type containers and proceed:

template<template<class...> class List, 
class... Elements, class New>

struct push_back<List<Elements...>, New> 
{
  using type = List<Elements...,New>;
};

As compile-time metaprogramming has no concept of values, our only way to add an element to an existing type container is to rebuild a new one. The algorithm is pretty simple: expand the existing parameter pack inside the container and add one more element at the end. By the definitions of List and ..., this builds a new valid type where the New element has been inserted at the end.

Removal of existing elements in a type container follows a similar reasoning but relies on the recursive structure of the parameter pack. Fear not! As we said earlier, recursion in template metaprogramming is usually ill advised, but here we will only exploit the structure of the parameter pack and we won’t do any loops. Let’s begin with the bare-bones code for a hypothetical remove_front algorithm:

template<class List> struct remove_front;

template<template<class...> class List, class... Elements>
struct remove_front<List<Elements...>>
{
  using type = List</* what goes here??? */>;
};

As you can see, we haven’t diverged much from what we’ve seen so far. Now, let’s think about how we can remove the first type of an arbitrary parameter pack so that we can complete our implementation. Let’s enumerate the cases:

List<Elements...>

Contains at least one element (the head) and a potentially empty pack of other types (the tail). In this case, we can write it as List<Head, Tail...>

List<Elements...>

This is empty. In this case, it can be written as List<>.

If we know that a head type exists, we can remove it. If the list is empty, the job is already done. The code then reflects this process:

template<class List> struct remove_front;

template<template<class...> class List
        , class Head, class... Elements>
struct remove_front<List<Head,Elements...>>
{
  using type = List<Elements...>;
};

template<template<class...> class List>
struct remove_front<List<>>
{
  using type = List<>;
};

This introspection of the recursive nature of the parameter pack is another tool in our belt. It has some limitations, given that decomposing a pack into a list of heads and a single tail type is more complex, but it helps us build basic blocks that we can reuse in more complex contexts.

Pack Rewrapping

So far, we’ve dealt mostly with accessing and mutating the parameter pack. Other algorithms might need to work with the enclosing type container.

As an example, let’s write a metafunction that turns an arbitrary type container into a std::tuple. How can we do that? Because the difference between std::tuple<T...> and List<T...> is the enclosing template type, we can just change it, as shown here:

template<class List> struct as_tuple;​

template<template<class..> class List, class... Elements> 
struct as_tuple<List<Elements...>>
{
  using type = std::tuple<Elements...>;
};

But wait: there’s more! Changing the type container to tuple or variant or anything else can actually be generalized by passing the new container type as a parameter. Let’s generalize as_tuple into rename:

struct rename;​

template<template<class..> class Container
        , template<class..> class List
        , class... Elements
        > 
struct rename<Container, List<Elements...>>
{
  using type = Container<Elements...>;
};

The code is rather similar. We use the fact that a template template parameter can be passed naturally to provide rename with its actual target. A sample call can then be as follows:

using my_variant = rename<boost::variant
                         , std::tuple<int,short>
                         >;

Container Transformations

These tools—rewrapping, iteration, and type introspection for type containers—lead us to the final and most interesting metaprograms: container transformations. Such transformations, directly inspired by the STL algorithms, will help introduce the concept of structured metaprogramming.

template<typename L1, typename L2> struct append;

tempate< template<class...> class L1, typename... T1
       , template<class...> class L2, typename... T2
       >
struct append< L1<T1...>, L2<T2...> >
{
  using type = L1<T1...,T2...>;
};

struct remove_ptr
{
  template<typename T> struct apply
  {
    using type = typename std::remove_ptr<T>::type;
  };
};

using no_ptr = remove_ptr::apply<int*>::type;

template<template<class...> class MetaFunction>
struct lambda
{
  struct type
  {
    template<typename Args...> struct apply
    {
      using type = typename MetaFunction<Args...>::type;
    };
  };
};

template<typename List, typename F> struct transform;

template<template<class...> class List,
struct transform<List<Elems...>,F>
{
  using call = typename F::template apply<T>::type;
  using type = List< call<Elems>... >;
};

using no_pointers = transform< meta_list<int*,float**, double>
                             , lambda<std::remove_ptr>
                             >::type;

A Revisited Command Pattern

The command pattern is a behavioral design pattern in which you encapsulate all the information required to execute a command into an object or structure. It’s a great pattern, which in C++ is often written with runtime polymorphism.

Putting aside the tendency of runtime polymorphism to induce the “factory of factories” antipattern, there can be a nonnegligible performance cost induced by vtables because they prevent the compiler from aggressively optimizing and inlining code.

From a strictly software design point of view, it also forces you to relate objects together just because they will go through the same function at some point in time.

If generic programming has taught us anything, it’s that you don’t need to create a relation between objects just to make them use a function.

All you need to do is make the objects share common properties:

struct first_command
{
    std::string operator()(int) { /* something */ }
};

struct second_command
{
    std::string operator()(int) { /* something */ }
};

And have a function that accepts a command:

template <typename Command>
void execute_command(const Command & c, int param)
{
    c(param);
}

To which you will retort, “How do I transmit those commands through a structure, given that I know only at runtime which command to run?”

There are two ways to do it: manually, by using an unrestricted union, or by using a variant such as Boost.Variant. Template metaprogramming comes to the rescue because you can safely list the types of the commands in a type list and build the variant (or the union) from that list.

Not only will the code be more concise and more efficient, but it will also be less error prone: at compile time you will get an error if you forgot to implement a function, and the “pure virtual function call” is therefore impossible.⁴

Compile-Time Serialization

What do we mean by compile-time serialization? When you want to serialize an object, there are a lot of things you already know at compile time—and remember, everything you do at compile time doesn’t need to be done any more at runtime.

That means much faster serialization and more efficient memory usage.

For example, when you want to serialize a std::uint64_t, you know exactly how much memory you need, whereas when you serialize a std::vector<std::uint64_t>, you must read the size of the vector at runtime to know how much memory you need to allocate.

Recursively, it means that if you serialize a structure that is made up strictly of integers, you are able, at compile time, to know exactly how much memory you need, which means you can allocate the required intermediate buffers at compile time.

With template metaprogramming, you can branch, at compile time, the right code for serialization. This means that for every structure for which you are able to exactly compute the memory requirements, you will avoid dynamic memory allocation altogether, yielding great performance improvements and reduced memory usage.