The relation between C++ and C is somewhat of an anomaly; usually abstraction hurts performance, yet C++ code often compiles to a more efficient executable than its C equivalent. Templates deserve a lot of the credit for this, as they allow the compiler to resolve at compile-time much of the abstraction required by modular and maintainable code design. That’s what meta-programming is all about.
In that respect, variadic templates, introduced in C++11, were a major improvement of the language. And with them came a new and extremely useful idiom: meta-sequences. Below I’ll give a demonstration of a problem - initializing an array at compile-time - for which meta-sequences provide a good solution.
Since they are the key idea behind many elegant solutions to various problems, it is not surprising that utilities for using them were included in the standard library (since C++14). It is surprising, though, that the implementation that comes with the STL is sometimes problematic and may require using homemade alternatives (this is the case, for example, in gcc 5.1.0). So I’ll discuss implementation details as well.
Compile-Time Array Initialization
As a simple scenario, consider the problem of initializing a
T is a non-trivially constructible type:
All kinds of runtime hacks (e.g. switching to an array of pointers and constructing its elements in a loop) are obviously evil. For example, they introduce an extra level of indirection that obstructs the optimizer, and they present an unattractive choice between heap allocations or custom allocators.
Luckily, this problem has an easy and decent solution:
where the function
MakeArray will be defined shortly. This code is
evaluated, in compile time, to this:
So the compiler is in a position to eliminate copies, moves and function calls, and generate in-place consturctions wherever possible. As a matter of fact, with this main function -
the entire computation was done by the compiler (using gcc 5.1.0), and the generated assembly code was essentially:
The Function “MakeArray”
So how could a function like
MakeArray be implemented? Using meta-
sequences of course. In C++14
std::integer_sequence became a standard part
of the language, as part of the header
<utility>. Two very useful helpers
are the templates
Here’s an implementation for
MakeArray that uses them:
Let’s look at the first template. The first argument is a callback that
returns elements to be placed in the array (here, it takes an
index as a parameter), and the second argument has no name. This means the
function never uses its value. Only its type matters. The method returns an
array whose elements’ type is the same type returned by the callable given as
the first argument, and whose length is equal to the length of the variadic
The value of
S is deduced from the second, nameless, argument. In fact,
that’s the raison d’etre of that second argument. It has no other purpose. The
index_sequence<> is an empty class, which is nothing more than a
placeholder for the sequence
S. In essence, this is it:
A call for the first template of
MakeArray looks like that:
make_index_sequence is a mechanism for constructing a
sequence such as
index_sequence<0,1,2,3,4,5,6,7,8,9,10,11...,N-1> from the
N. It is used by the second template, whose job is to allow the
user to do the same by simply writing:
And this is it.
That was just one scenario in which meta-sequences shine. There are many others. But I think it’s best not to make this post into a long list of random examples, and it’s likely that later posts will provide real-life scenarios anyway. So instead, let’s go on to discuss some implementation details.
Meta-Enumeration - Take 1
Here’s a naive implementation of
The third line is merely syntactic sugar. The first line defines a template
class that encodes a postfix of the final sequence (
S...) and a parameter
N that counts the missing elements. This class is defined recursively, so that
shorter postfixs are derived from longer postfixs. The second line is a
specialized version of this class for the base case, of a fully spanned sequence
- and it defines the type
typethat encodes the entire sequence, and is accessible (due to inheritance) from all the chain of derived classes.
For example, unrolling $N=4$ get us:
So the type of
index_sequence<0, 1, 2, 3>.
Now the problem with this implementation might be clearer: generation of a sequence of $N$ elements requires an inheritance tree of depth $N$. Furthermore, sequences of different lengths can’t share intermediate instantiations. This could easily make compile time unreasonably long even for moderate $N$s.
Surprisingly, even though there is a better solution at hand - this kind of solution is used by common implementations of the STL!
Meta-Enumeration - Take 2
A faster and a compiler-friendlier approach, is to use concatenation:
Using it has several benefits: it doesn’t require a recursive inheritance, it compiles in $O(\ln n)$ time instead of $O(n)$ and it uses reusable building- blocks for the sequences shareable between different instantiations. Here’s an implementation for concatenation-based sequences via ranges:
And we can now write: