Simple C++11 metaprogramming

The wide acceptance of Boost.MPL made C++ metaprogramming seem a solved problem. Perhaps MPL wasn’t ideal, but it was good enough to the point that there wasn’t really a need to seek or produce alternatives.

C++11 changed the playing field. The addition of variadic templates with their associated parameter packs added a compile-time list of types structure directly into the language. Whereas before every metaprogramming library defined its own type list, and MPL defined several, in C++11, type lists are as easy as

and there is hardly a reason to use anything else.

Template aliases are another game changer. Previously, "metafunctions", that is, templates that took one type and produced another, looked like

and were used in the following manner:

In C++11, metafunctions can be template aliases, instead of class templates:

The above example use then becomes

or, if you prefer to be seen as C++11-savvy,

This is a considerable improvement in more complex expressions:

(The example also takes advantage of another C++11 feature - you can now use >> to close templates without it being interpreted as a right shift.)

In addition, template aliases can be passed to template template parameters:

These language improvements allow for C++11 metaprogramming that is substantially different than its idiomatic C++03 equivalent. Boost.MPL is no longer good enough, and something must be done. But what?

Let’s start with the basics. Our basic data structure will be the type list:

Why the mp_ prefix? mp obviously stands for metaprogramming, but could we not have used a namespace?

Indeed we could have. Past experience with Boost.MPL however indicates that name conflicts between our metaprogramming primitives and standard identifiers (such as list) and keywords (such as if, int or true) will be common and will be a source of problems. With a prefix, we avoid all that trouble.

So we have our type list and can put things into it:

but can’t do anything else with it yet. We’ll need a library of primitives that operate on mp_lists. But before we get into that, let’s consider another interesting question first.

Suppose we have our library of primitives that can do things with a mp_list, but some other code hands us a type list that is not an mp_list, such as for example an std::tuple<int, float, void*>, or std::packer<int, float, void*>.

Suppose we need to modify this external list of types in some manner (change the types into pointers, perhaps) and give back the transformed result in the form it was given to us, std::tuple<int*, float*, void**> in the first case and std::packer<int*, float*, void**> in the second.

To do that, we need to first convert std::tuple<int, float, void*> to mp_list<int, float, void*>, apply add_pointer to each element obtaining mp_list<int*, float*, void**>, then convert that back to std::tuple.

These conversion steps are a quite common occurrence, and we’ll write a primitive that helps us perform them, called mp_rename. We want

to give us

and conversely,

to give us

Here is the implementation of mp_rename:

(This pattern of a template alias forwarding to a class template doing the actual work is common; class templates can be specialized, whereas template aliases cannot.)

Note that mp_rename does not treat any list type as special, not even mp_list; it can rename any variadic class template into any other. You could use it to rename std::packer to std::tuple to std::variant (once there is such a thing) and it will happily oblige.

In fact, it can even rename non-variadic class templates, as in the following examples:

There is a limit to the magic; unique_ptr can’t be renamed to shared_ptr:

because unique_ptr<int> is actually unique_ptr<int, std::default_delete<int>> and mp_rename renames it to shared_ptr<int, std::default_delete<int>>, which doesn’t compile. But it still works in many more cases than one would naively expect at first.

With conversions no longer a problem, let’s move on to primitives and define a simple one, mp_size, for practice. We want mp_size<mp_list<T...>> to give us the number of elements in the list, that is, the value of the expression sizeof...(T).

This is relatively straightforward, except for the std::integral_constant. What is it and why do we need it?

std::integral_constant is a standard C++11 type that wraps an integral constant (that is, a compile-time constant integer value) into a type.

Since metaprogramming operates on type lists, which can only hold types, it’s convenient to represent compile-time constants as types. This allows us to treat lists of types and lists of values in a uniform manner. It is therefore idiomatic in metaprogramming to take and return types instead of values, and this is what we have done. If at some later point we want the actual value, we can use the expression mp_size<L>::value to retrieve it.

We now have our mp_size, but you may have noticed that there’s an interesting difference between mp_size and mp_rename. Whereas I made a point of mp_rename not treating mp_list as a special case, mp_size very much does:

Is this really necessary? Can we not use the same technique in the implementation of mp_size as we did in mp_rename?

Yes, we very much can, and this improvement allows us to use mp_size on any other type lists, such as std::tuple. It turns mp_size into a truly generic primitive.

This is nice. It is so nice that I’d argue that all our metaprogramming primitives ought to have this property. If someone hands us a type list in the form of an std::tuple, we should be able to operate on it directly, avoiding the conversions to and from mp_list.

So do we no longer have any need for mp_rename? Not quite. Apart from the fact that sometimes we really do need to rename type lists, there is another surprising task for which mp_rename is useful.

To illustrate it, let me introduce the primitive mp_length. It’s similar to mp_size, but while mp_size takes a type list as an argument, mp_length takes a variadic parameter pack and returns its length; or, stated differently, it returns its number of arguments:

How would we implement mp_size in terms of mp_length? One option is to just substitute the implementation of the latter into the former:

but there is another way, much less mundane. Think about what mp_size does. It takes the argument

and returns

Do we already have a primitive that does a similar thing?

(Not much of a choice, is there?)

Indeed we have, and it’s called mp_rename.

I don’t know about you, but I find this technique fascinating. It exploits the structural similarity between a list, L<T...>, and a metafunction "call", F<T...>, and the fact that the language sees the things the same way and allows us to pass the template alias mp_length to mp_rename as if it were an ordinary class template such as mp_list.

(Other metaprogramming libraries provide a dedicated apply primitive for this job. apply<F, L> calls the metafunction F with the contents of the list L. We’ll add an alias mp_apply<F, L> that calls mp_rename<L, F> for readability.)

Let’s revisit the example I gave earlier - someone hands us std::tuple<X, Y, Z> and we need to compute std::tuple<X*, Y*, Z*>. We already have add_pointer:

so we just need to apply it to each element of the input tuple.

The algorithm that takes a function and a list and applies the function to each element is called transform in Boost.MPL and the STL and map in functional languages. We’ll use transform, for consistency with the established C++ practice (map is a data structure in both the STL and Boost.MPL.)

We’ll call our algorithm mp_transform, and mp_transform<F, L> will apply F to each element of L and return the result. Usually, the argument order is reversed and the function comes last. Our reasons to put it at the front will become evident later.

There are many ways to implement mp_transform; the one we’ll pick will make use of another primitive, mp_push_front. mp_push_front<L, T>, as its name implies, adds T as a first element in L:

There is no reason to constrain mp_push_front to a single element though. In C++11, variadic templates should be our default choice, and the implementation of mp_push_front that can take an arbitrary number of elements is almost identical:

On to mp_transform:

This is a straightforward recursive implementation that should be familiar to people with functional programming background.

Can we do better? It turns out that in C++11, we can.

Here we take advantage of the fact that pack expansion is built into the language, so the F<T>... part does all the iteration work for us.

We can now solve our original challenge: given an std::tuple of types, return an std::tuple of pointers to these types:

What if we had a pair of tuples as input, and had to produce the corresponding tuple of pairs? For example, given

we had to produce

We need to take the two lists, represented by tuples in the input, and combine them pairwise by using std::pair. If we think of std::pair as a function F, this task appears very similar to mp_transform, except we need to use a binary function and two lists.

Changing our unary transform algorithm into a binary one isn’t hard:

and we can now do

again exploiting the similarity between metafunctions and ordinary class templates such as std::pair, this time in the other direction; we pass std::pair where mp_transform2 expects a metafunction.

Do we have to use separate transform algorithms for each arity though? If we need a transform algorithm that takes a ternary function and three lists, should we name it mp_transform3? No, this is exactly why we put the function first. We just have to change mp_transform to be variadic:

and then add the unary and binary specializations:

We can also add ternary and further specializations.

Is it possible to implement the truly variadic mp_transform, one that works with an arbitrary number of lists? It is in principle, and I’ll show one possible abridged implementation here for completeness:

but will omit the primitives that it uses. These are

There is one interesting difference between the recursive mp_transform implementation and the language-based one. mp_transform<add_pointer, std::pair<int, float>> works with the F<T>... implementation and fails with the recursive one, because std::pair is not a real type list and can only hold exactly two types.

Eric Niebler, in his Tiny Metaprogramming Library article, gives the function std::tuple_cat as a kind of a metaprogramming challenge. tuple_cat is a variadic template function that takes a number of tuples and concatenates them into another std::tuple. This is Eric’s solution:

All right, challenge accepted. Let’s see what we can do.

As Eric explains, this implementation relies on the clever trick of packing the input tuples into a tuple, creating two arrays of indices, inner and outer, then indexing the outer tuple with the outer indices and the result, which is one of our input tuples, with the inner indices.

So, for example, if tuple_cat is invoked as

we’ll create the tuple

and then extract the elements of t via

(t2 is empty, so we take nothing from it.)

The first column of integers is the outer array, the second one - the inner array, and these are what we need to compute. But first, let’s deal with the return type of tuple_cat.

The return type of tuple_cat is just the concatenation of the arguments, viewed as type lists. The metaprogramming algorithm that concatenates lists is called meta::concat in Eric Niebler’s Meta library, but I’ll call it mp_append, after its classic Lisp name.

(Lisp is today’s equivalent of Latin. Educated people are supposed to have studied and forgotten it.)

That was fairly easy. There are other ways to implement mp_append, but this one demonstrates how the language does most of the work for us via pack expansion. This is a common theme in C++11.

Note how mp_append returns the same list type as its first argument. Of course, in the case in which no arguments are given, there is no first argument from which to take the type, so I’ve arbitrarily chosen to return an empty mp_list.

We’re now ready with the declaration of tuple_cat:

The reason we need remove_reference is because of the rvalue reference parameters, used to implement perfect forwarding. If the argument is an lvalue, such as for example t1 above, its corresponding type will be a reference to a tuple — std::tuple<int, short, long>& in t1's case. Our primitives do not recognize references to tuples as type lists, so we need to strip them off.

There are two problems with our return type computation though. One, what if tuple_cat is called without any arguments? We return mp_list<> in that case, but the correct result is std::tuple<>.

Two, what if we call tuple_cat with a first argument that is a std::pair? We’ll try to append more elements to std::pair, and it will fail.

We can solve both our problems by using an empty tuple as the first argument to mp_append:

With the return type taken care of, let’s now move on to computing inner. We have

as input and we need to output

which is the concatenation of

Here each tuple is the same size as the input, but is filled with a constant that represents its index in the argument list. The first tuple is filled with 0, the second with 1, the third with 2, and so on.

We can achieve this result if we first compute a list of indices, in our case [0, 1, 2, 3], then use binary mp_transform on the two lists

and a function which takes a list and an integer (in the form of an std::integral_constant) and returns a list that is the same size as the original, but filled with the second argument.

We’ll call this function mp_fill, after std::fill.

Functional programmers will immediately realize that mp_fill is mp_transform with a function that returns a constant, and here’s an implementation along these lines:

Here’s an alternate implementation:

These demonstrate different styles and choosing one over the other is largely a matter of taste here. In the first case, we combine existing primitives; in the second case, we "inline" mp_const and even mp_transform in the body of mp_fill_impl.

Most C++11 programmers will probably find the second implementation easier to read.

We can now mp_fill, but we still need the [0, 1, 2, 3] index sequence. We could write an algorithm mp_iota for that (named after std::iota), but it so happens that C++14 already has a standard way of generating an index sequence, called std::make_index_sequence. Since Eric’s original solution makes use of make_index_sequence, let’s follow his lead.

Technically, this takes us outside of C++11, but make_index_sequence is not hard to implement (if efficiency is not a concern):

We can now obtain an index_sequence<0, 1, 2, 3>:

but make_index_sequence<4> returns integer_sequence<std::size_t, 0, 1, 2, 3>, which is not a type list. In order to work with it, we need to convert it to a type list, so we’ll introduce a function mp_from_sequence that does that.

We can now compute the two lists that we wanted to transform with mp_fill:

and finish the job of computing inner:

For outer, we again have

as input and we need to output

which is the concatenation of

The difference here is that instead of filling the tuple with a constant value, we need to fill it with increasing values, starting from 0, that is, with the result of make_index_sequence<N>, where N is the number of elements.

The straightforward way to do that is to just define a metafunction F that does what we want, then use mp_transform to apply it to the input:

Well that was easy. Surprisingly easy. The one small annoyance is that we can’t define F inside tuple_cat - templates can’t be defined in functions.

Let’s put everything together.

This almost compiles, except that our inner happens to be a std::tuple, but our helper function expects an mp_list. (outer is already an mp_list, by sheer luck.) We can fix that easily enough.

Let’s define a print_tuple function and see if everything checks out.

Output:

Seems to work. But there’s at least one error left. To see why, replace the first tuple

with a pair:

We now get an error at

because the first element of list3 is an std::pair, which mp_append tries and fails to use as its return type.

There are two ways to fix that. The first one is to apply the same trick we used for the return type, and insert an empty mp_list at the front of list3, which mp_append will use as a return type:

The second way is to just convert all inputs to mp_list:

In both cases, inner will now be an mp_list, so we can omit the mp_rename in the call to tuple_cat_.

We’re done. The results hopefully speak for themselves.

Perhaps by now you’re wondering why this article is called "Simple C++11 metaprogramming", since what we covered so far wasn’t particularly simple.

The relative simplicity of our approach stems from the fact that we’ve not been doing any higher order metaprogramming, that is, we haven’t introduced any primitives that return metafunctions, such as compose, bind, or a lambda library.

I posit that such higher order metaprogramming is, in the majority of cases, not necessary in C++11. Consider, for example, Eric Niebler’s solution given above:

The meta_compose expression takes three other ("quoted") metafunctions and creates a new metafunction that applies them in order. Eric uses this example as motivation to introduce the concept of a "metafunction class" and then to supply various primitives that operate on metafunction classes.

But when we have metafunctions F, G and H, instead of using meta_compose, in C++11 we can just do

and that’s it. The language makes defining composite functions easy, and there is no need for library support. If the functions to be composed are as_typelist_t, std::make_index_sequence and typelist_size_t, we just define

Similarly, if we need a metafunction that will return sizeof(T) < sizeof(U), there is no need to enlist a metaprogramming lambda library as in

We could just define it inline:

Finally, let me show the implementations of mp_count and mp_count_if, for no reason other than I find them interesting. mp_count<L, V> returns the number of occurrences of the type V in the list L; mp_count_if<L, P> counts the number of types in L for which P<T> is true.

As a first step, I’ll implement mp_plus. mp_plus is a variadic (not just binary) metafunction that returns the sum of its arguments.

Now that we have mp_plus, mp_count is just

This is another illustration of the power of parameter pack expansion. It’s a pity that we can’t use pack expansion in mp_plus as well, to obtain

directly. It would have been nice for T::value + ... to have been supported, and it appears that in C++17, it will be.

mp_count_if is similarly straightforward:

at least if we require P to return bool. If not, we’ll have to coerce P<T>::value to 0 or 1, or the count will not be correct.

The last primitive I’ll show is mp_contains. mp_contains<L, V> returns whether the list L contains the type V:

At first sight, this implementation appears horribly naive and inefficient — why would we need to count all the occurrences just to throw that away if we’re only interested in a boolean result — but it’s actually pretty competitive and perfectly usable. We just need to add one slight optimization to mp_plus, the engine behind mp_count and mp_contains:

This cuts the number of template instantiations approximately tenfold.

I have outlined an approach to metaprogramming in C++11 that

Part 2 is now available, in which I show algorithms that allow us to treat type lists as sets, maps, and vectors, and demonstrate various C++11 implementation techniques in the process.