Exploding tuples with fold expressions
Generic programming in C++ has been made much easier with C++11’s addition of
std::tuple. It allows us to store objects of different types in the same container and index them at compile time. Support for algorithms over heterogeneous types like
std::tuple is pretty thin in the standard library, so some programmers tend to pull in dependencies such as the excellent
boost::hana to hide away all the crazy template metaprogramming tricks. I’ll show you how you can use fold expressions to ease the implementation such functions, and I’ll demonstrate a very small abstraction function for rolling your own heterogenous algorithms.
So, say we have a tuple and we want to print out every element of it. If there was a utility to call some function on every element of a tuple, you might use it like this:
The implementation of
for_each would typically rely on the indices trick. This involves generating a compile-time sequence of indices for the tuple, then passing them as variadic non-type template arguments to another template function and expanding the resulting parameter pack. If that all sounds gibberish to you, don’t worry, I’ll explain.
The above code generates the index sequence and passes it on to to the helper function which we’ll define next.
std::index_sequence_for is part of C++14’s1 support for compile-time sequence generation.
std::integer_sequence is the class you pass around, and it comes with a bunch of handy helpers, like
std::make_integer_sequence and the one we used above.
std::index_sequence<0,1,...> is the same as
In case you aren’t familiar with some of the constructs here, I’ll break this code down.
std::get<Idx>(t) gets the
Idxth element from the tuple
f(std::get<Idx>(t)) calls the functor
f with that element.
f(std::get<Idx>(t))... expands the parameter pack
Idx over that expression. So if
for_each is called with
std::index_sequence<0,1,2>, it generates this code:
Hopefully you’ll see that now, when we call this:
std::index_sequence<0,1,2> will be generated in
for_each, everything will be passed on to the helper, and it’ll generate code to call our closure for each element of the tuple.
Unfortunately, that’s not what happens.
Everything is awful
Keen readers might have noticed that I lied in the above section.
f(std::get<Idx>(t))...; does not generate that sequence of calls to
f. In fact, it doesn’t even compile. The problem is that parameter packs can only be expanded in contexts which expect a syntactic list, such as initializers and function call arguments. You can’t just expand them bare in a function body. In C++17, this problem has a nice solution, but prior to that we need to use some pretty horrible hacks. Here’s one possibility which uses
std::initializer_list to create a context in which the parameter pack can be expanded.
The above successfully compiles and runs. The trick is the
, 0 inside the
initializer_list initializer, which evaluates the function call, and uses
0 as the initializer value. The
void() is there just incase some has been perverse enough to call this with types with overloaded
Fold expressions are less awful
As noted above, C++17 has a nicer solution for this in the form of fold expressions. Fold expressions allow the expansion of parameter packs over operators, of which
, is one. With this feature we can write the following code to get rid of our previous hack:
I think you’ll agree that this is a huge improvement.
Even though fold expressions make writing this code easier and less guru-only, the indices trick can still be difficult for beginners. It turns out that we can actually abstract this pattern to give “normal” users access to this power.
Our abstraction function will be called
make_index_dispatcher, and it’ll produce a closure for dispatching indices based on an index sequence size.
The first template takes in an index sequence and returns a closure. This closure takes a functor argument which will be called with a compile-time
std::size_t constant for each index in the parameter pack. The second template just generates the index sequence from the given sequence size.
for_each can now be implemented in a single function without any weird tricks. Here’s a simple implementation:
Here’s a more generic version which uses perfect forwarding (live demo to play with):
There you have it; a generic utility for compile-time dispatching on index-based containers, and the know-how to implement variations yourself. Let me know if you find any uses or improvements for this, or if you have any questions about the nitty-gritty of these techniques.
If you’re stuck with C++11, there are plenty implementations online, or you can just steal one from your favourite standard library implementation. ↩
Let me know what you think of this article on twitter @TartanLlama or leave a comment below!