C++11 introduces the concept of range-based for loop to iterate over data structures such as STL containers:
vector<int> aVector {1, 2, 3, 4, 5};
for (auto i : aVector)
{
cout << i << " ";
}
Thanks to lambda expressions, the code above may be considered just a syntactical simplification to:
for_each( begin(aVector), end(aVector), [](int i)
{
cout << i << " ";
});
Looking at this code, how is it possible to iterate over more than one container at the same time? I mean something like this:
list<float> aList {6.1, 7.2, 8.3, 9.4, 10.5};
for_each( aVector, aList, [](int i, float f)
{
cout << i << " " << f << endl;
});
We could use smart libraries such as Boost.Fusion to achieve similar results, but suppose we cannot use anything but C++11 capabilities.
Here I’m going to show you a possbile way to iterate over several ranges with the same syntax of for_each. Along the way, some reusable utilities will be presented.
To start, this is the simplest implementation of for_each you can find:
template<typename InputIterator, typename Callable>
Callable for_each(InputIterator begin, InputIterator end, Callable fn)
{
for( ; begin != end; ++begin)
{
fn (*begin);
}
return fn;
}
My idea is to employ a couple of tuples: the first containing all the begin-InputIterators, the second containing all the end-InputIterators. For instance:
vector<int> aVector;
list<float> aList;
map<string, int> aMap;
auto begins = make_tuple(begin(aVector), begin(aList), begin(aMap));
auto ends = make_tuple(end(aVector), end(aList), end(aMap));
// i-th range: [get<i>(begins), get<i>(ends)]
So, for_each_multi has the following signature:
template<typename Tuple, typename Callable>
Callable for_each_multi(Tuple begins, Tuple ends, Callable fn);
Considering the simplest for_each implementation, we need three basic building bricks:
- check that begin != end (for each [begin, end] range)
- ++begin (for each begin)
- fn (*begin) (simultaneously for each begin)
Good news: 1 and 2 fall in the same support function that I called visit_tuple. This is just an “apply to all” for tuples that applies a function to each element of a tuple. Generalizing, visit_tuple receives any number N of tuples and a callable object having a function call operator which accepts N parameters.
For example, if we call visit_tuple with one tuple, the function call operator will be required to be single-argument; otherwise, passing two tuples, a two-arguments function call operator will be needed, etc.
My implementation is a bit verbose but I find it more readable. visit_tuple uses a support struct that makes the recursion and goes through each element of the tuple(s):
// visit_tuple
template<typename Callable, typename Head, typename... Tail>
Callable visit_tuple(Callable f, Head&& aTuple, Tail&& ...aTail)
{
const size_t size = std::tuple_size<typename std::remove_reference<Head>::type>::value-1;
visit_tuple_ws<size>::visit(f, aTuple, aTail...);
return f;
}
// support struct to iterate over the tuple(s)
template<size_t size>
struct visit_tuple_ws
{
template<typename Callable, typename Head, typename... Tail>
static void visit(Callable& f, Head& aTuple, Tail& ...aTail)
{
visit_tuple_ws<size-1>::visit(f, aTuple, aTail...);
f(std::get<size>(aTuple), std::get<size>(aTail)...);
}
};
// stop recursion here
template<>
struct visit_tuple_ws<0u>
{
template<typename Callable, typename Head, typename... Tail>
static void visit(Callable& f, Head& aTuple, Tail& ...aTail)
{
f(std::get<0>(aTuple), std::get<0>(aTail)...);
}
};
I know there are several ways to make this code less verbose (maybe the support struct can be eliminated), I repeat this style may be more readable in some contexts.
Just for trying, printing a tuple is probably the easiest usage of this function. The code is straightforward:
struct Printer
{
// generic function call operator
template<typename T>
void operator()(T&& t)
{
cout << t << " ";
}
};
// print!
visit_tuple( Printer(), make_tuple(1, 5.0, "Hello") );
Being first-class objects, functors can be passed to and returned from functions (maintaing a state). Let’s write a simple functor that checks begin != end:
struct CheckBeginEnd
{
CheckBeginEnd() : BeginIsNotEnd(true) {}
template<typename T>
void operator()(T&& begin, T&& end)
{
BeginIsNotEnd &= (begin != end);
}
bool BeginIsNotEnd;
};
Incrementing is even simpler:
struct Increment
{
template <typename T>
void operator()(T&& t)
{
++t;
}
};
So we completed the first part of for_each_multi:
// for_each_multi
template<typename Tuple, typename Callable>
Callable for_each_multi(Tuple begins, Tuple ends, Callable fn)
{
for ( ; visit_tuple(CheckBeginEnd(), begins, ends).BeginIsNotEnd;
visit_tuple(Increment(), begins) )
{...apply...}
return fn;
}
The “apply” part of the algorithm is a bit more difficult because it requires tuple unpacking. The problem is general and the solution I propose can be reused. Unpacking is presented below:
Basically, given a function Fn and a tuple, an unpacker is able to call Fn passing the content of the tuple as parameters.
Our case is slightly different because we need to dereference each parameter before passing it to Fn. This fact encouraged me to be more generic, as you’re going to discover.
So, is it clear why we need unpacking? If no, suppose to have these ranges and this lambda:
auto begins = make_tuple(begin(aVector), begin(aList));
auto ends = make_tuple(end(aVector), end(aList));
auto fn = [](int anInt, float aFloat) { ... }
At some point we’ll have to call something like:
fn ( get<0>(begins), get<1>(begins) )
We need to call fn using begins’ content as parameter. Generalizing:
auto begins = make_tuple(begin(aVector), begin(aList), ...);
auto ends = make_tuple(end(aVector), end(aList), ...);
auto fn = [](int anInt, float aFloat, ...) { ... }
...
fn ( get<0>(begins), get<1>(begins), ..., get<size-1>(begins) )
And this is precisely the unpacker job!
To Write an unpacker, the role of variadics is pivotal. Consider what this trivial piece of code does:
template<size_t S, typename T>
void apply_one_element(T&& aTuple)
{
my_function( std::get<S>(aTuple) );
}
Calls my_function passing the S-th element of aTuple as parameter. This can be generalized to:
template<size_t ...S, typename T>
void apply_more_element(T&& aTuple)
{
my_function( std::get<S>(aTuple) ... );
}
apply_more_element<0u, 1u, 2u> ( make_tuple(1, 2.0, "hello") );
The last line could be considered expanded to:
template<0u, 1u, 2u, typename T>
void apply_more_element(T&& aTuple)
{
my_function( std::get<0u>(aTuple), std::get<1u>(aTuple), std::get<2u>(aTuple) );
}
If it was (sort of) automatic, it would be exactly what we need: we want a way to generate the size_t sequence from 0 to tuple_size – 1.
This can be done using a couple of support types: one that carries the sequence around and another one that generates it. The former is simple:
template<size_t ...>
struct sequence {};
So a possible unpacker may be written like:
struct Unpack
{
template< typename Callable, typename Tuple, size_t ...S >
static void unpackAndApply(Tuple&& tuple, Callable& fn, sequence<S...> )
{
fn(std::get<S>(tuple) ...);
}
};
sequence<S…> is used just to carry around the size_t sequence. Now, the harder part. How to generate sequence<S…>? For example: given tuple<int, float, string>, we want to create sequence<0, 1, 2>.
A possible implementation is:
template<size_t N, size_t ...S>
struct generate : generate<N-1u, N-1u, S...> {};
template<size_t ...S>
struct generate<0u, S...>
{
typedef sequence<S...> type;
};
Considering N=3, I hope the idea will become clearer through this figure:
If you have understood the transition from generate<2,2> to generate<1,1,2> then you have won!
The last part of for_each_multi consists of the apply_tuple function:
// apply_tuple
template<typename Unpacker, typename Tuple, typename Callable>
void apply_tuple(Tuple&& tuple, Callable&& fn)
{
const int size = std::tuple_size<typename std::remove_reference<Tuple>::type>::value;
Unpacker::apply( std::forward<Tuple>(tuple), std::forward<Callable>(fn), typename generate<size>::type() );
}
The Unpacker template parameter is just a sort of policy that handles how the parameters are passed to the callable object. In our case, we have to implement a sort of “dereferencer unpacker”:
struct Dereference
{
template< typename Callable, typename Tuple, size_t ...S >
static void apply(Tuple&& tuple, Callable& fn, sequence<S...> )
{
fn(*std::get<S>(tuple) ...); // aka fn(*it)
}
};
And finally for_each_multi takes this form:
// for_each_multi
template<typename Tuple, typename Callable>
Callable for_each_multi(Tuple begins, Tuple ends, Callable fn)
{
for ( ; visit_tuple(CheckBeginEnd(), begins, ends).BeginIsNotEnd;
visit_tuple(Increment(), begins) )
{
apply_tuple<Dereference>(begins, fn);
}
return fn;
}
An example of usage:
vector<int> aVector {1, 2, 3, 4};
array<string, 4> anArray("one", "two", "three", "four");
for_each_multi(
make_tuple(begin(aVector), begin(anArray),
make_tuple(end(aVector), end(anArray),
[](int i, const string& s)
{
cout << i << " is " << s << endl;
}
);
To reduce verbiage, if you need to iterate over full ranges (e.g. begin-end) , I propose a couple of possible utilities:
// begins tuple
template<typename Head, typename ...Tail>
auto begins(Head&& head, Tail&& ...tail)
-> decltype(make_tuple(begin(head), begin(tail)...))
{
return make_tuple(begin(head), begin(tail)...);
}
// ends tuple
template<typename Head, typename ...Tail>
auto ends(Head&& head, Tail&& ...tail)
-> decltype(make_tuple(end(head), end(tail)...))
{
return make_tuple(end(head), end(tail)...);
}
Followed by:
#define ON(...) begins(__VA_ARGS__), ends(__VA_ARGS__)
Now we can write:
for_each_multi( ON(aVector, anArray), [](int i, const string& s)
{
cout << i << " is " << s << endl;
}
);
Without adding any support functions nor macros, another version (that I like a bit less because you have to put the callable before the containers) could be:
template<typename Callable, typename Head, typename... Tail>
Callable for_each_multi(Callable fn, Head&& head, Tail&& ...tail)
{
return for_each_multi(
std::make_tuple(begin(head), begin(tail)...),
std::make_tuple(end(head), end(tail)...),
fn);
}
...
for_each_multi([](int i, const string& s)
{
cout << i << " is " << s << endl;
}, aVector, anArray);
As usual, my code is on ideone (just a note: begin/end non-members are not supported so I had to use .begin()/.end() member-functions).
It’s presumable the existence of other smarter (and shorter) ways to accomplish the same target, but I hope this post can be useful to play a bit with tuples and variadics. At least I enjoyed a lot writing this stuff!
...
}
