Posts Tagged ‘tuple’

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:

  1. check that begin != end (for each [begin, end] range)
  2. ++begin (for each begin)
  3. 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:

unpack

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:

generate

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!

Since C++11, std namespace includes a generalization of pair: tuple, that is a heterogeneous fixed-size collection of values – std::tuple is  the standardization of the boost tuple library. Tuples are convenient in exactly what you expect: packing types. A couple of examples are: making it easy to define functions that return more than one value and emulating variadics – if your compiler does not support them.

In this post I’m going to discuss another worthwhile usage of tuples that I call multi-type dispatching.

Recalling my previous post about policies, I showed a simple logger class with two policies: filtering and outputting. Filtering was based on function template specializations, something like this:


struct ErrorFilter
{
     // pass nothing by default
     template<typename Severity>
     bool Filter() { return false; }
};

// Specialization -> Let pass errors
template<>
bool ErrorFilter::Filter<Error>() { return true; }

I promised another approach, with no specializations. This is based on tuples as well as a bit of metaprogramming. The idea pertains to a general concept. Suppose I have a function:

template <typename T>;
void function()
{
    ... something ...
}

and suppose I want to specialize it not only for T=int but also for T=float and T=double, and I want to provide the same implementation to all of them. Probably the simplest solution is forwarding:

template <>
void function<int>()
{
    ... something ...
}

template <>
void function<double>()
{
    function<int>(); // forward
}

template <>
void function<float>()
{
    function<int>(); // forward
}

This solution leads to code duplication. And what if we have:

template <typename T>
void function(T t)
{
    ... something ...
}

If we use forwarding then we have troubles with types:

template <>
void function<int>(int i)
{
    ... something ...
}

template <>
void function<double>(double d)
{
    function<int>(d); // forward to int??
}

template <>
void function<float>(float f)
{
    function<int>(f); // forward to int??
}

This solution seems not to be good. I would like an illegal code like this:

// illegal
template <typename T>
void function<int | float | double>(T t)
{
    ... called with either T=int, float or double ...
}

A filter could be an illegal class like this:

// illegal
class MultiFilter
{
    template<typename T>
    bool Filter() { return false; }

    template <>
    bool Filter<Error | Info>() { return true; }
}

To code a legal solution we can employ tuples. We use a tuple to pack types we want to “specialize togheter”, then we dispatch the input type T depending on its presence in that tuple. The bad news is that std::tuple does not have an “exists” member-function (nor a not-member function), the good news is that implementing that metafunction – a metafunction is either a class template (all of whose parameters are types) or a class with a publicly accessible nested result type (or const value) – is easy. Let’s start with it:

// needed for is_same
#include <type_traits>
#include <tuple>

using namespace std;

// this should be an inner and private metafunction of exists_type
// I put here for clarity
template<typename T, typename Tuple, const int index>
struct exists_type_index
{
    static const bool value =
        is_same < T, typename tuple_element<index, Tuple>::type >::value ||
                  exists_type_index<T, Tuple, index-1>::value;
};

// stop the recursion when reach the first element
template<typename T, typename Tuple>
struct exists_type_index<T, Tuple, 0>
{
    static const bool value = is_same < T, typename tuple_element<0, Tuple>::type >::value;
};

// exists_type metafunction (clients call this)
template<typename T, typename Tuple>
struct exists_type
{
    static const bool value = exists_type_index<T, Tuple, tuple_size<Tuple>::value-1>::value;
};

exists_type<T, Tuple> checks if an element of the same type of T exists in Tuple. It uses a support metafunction (exists_type_index) that does the work recursively: if the current type is the same as T then the bool value is true, otherwise the recursion goes on. When the current index is 0, the recursion stops. I borrowed these from the standard:

  • tuple_size<Tuple> to get the number of elements in Tuple,
  • tuple_element<N, Tuple> to get the N-th type in Tuple,
  • is_same to check if two types are the same.

Note that the job is performed at compile time. We can use exists_type this way:

tuple<int, float, string> tt;

exists_type<float, decltype(tt)>::value;  // 1
exists_type<double, decltype(tt)>::value; // 0
exists_type<string, decltype(tt)>::value; // 1

Now we can employ this utlity for dispatching. Take a deep breath here:

template<bool b>
struct Executor
{
 template<typename T>
 static void execute(T&&)
 {
    cout << "General case" << endl;
 }
};

template<>
struct Executor <true>
{
 template<typename T>
 static void execute(T&&)
 {
    cout << "Specific case" << endl;
 }
};

// clients call this
template<typename Tuple>
struct MultiTypeDispatcher
{
 template<typename T>
 void function( T&& t )
 {
      Executor<exists_type<T, Tuple>::value>::execute(forward<T>(t));
 }
};

// client code:
MultiTypeDispatcher< tuple<int, float, string> > dispatcher;

dispatcher.function(string("hello!")); // Specific case!
dispatcher.function(1.0f); // Specific case!
dispatcher.function(1.0); // General case!

I introduced the proverbial level of indirection and a bit of metaprogramming: the MultiTypeDispatcher uses the correct version of Executor depending on the compile-time-obtained boolean value. Using the example above: string is in the tuple, so the MultiTypeDispatcher will use Executor<true>; conversely, 1.0 is a double that is not in the tuple so Executor<false> (general case) will be used.

This approach carries several advantages:

  • no code duplication
  • which version of Executor::execute will be called is deduced at compile-time
  • flexibility (just change tuple’s contents)
  • function’s parameter type is not lost

Our logger example is a very special case because it does not need an executor at all:

template<typename Tuple>
struct MultiFilter
{
   template<typename T>
   bool Filter()
   {
       // just a check will suffice
       // (because the filtering has a trivial logic)
       return exists_type<T, Tuple>::value;
   }
};

// client code

typedef MultiFilter< tuple<Error, Info> > MyFilter;

SillyLogger<MyFilter, OStreamPolicy> logger(cout);

logger.Log<Generic>("Not Logged");
logger.Log<Info>(string("Logged!"));
logger.Log<Error>(1.0);

Another little suggestion: instead of using a bool as Executor’s template parameter, use an int. The reason is for extensibility: it doesn’t hurt to use an int, and doing so allows additional alternative implementations to be added easily in the future as needed (suppose your dispatcher will use more than one tuple or another trickier logic).

We can finally obtain a similar effect of the illegal code I wrote before. This approach can be also useful when you need to generate the same implementation to several functions that accept only certain types. The sole difference with the Dispatcher-Executor machinery is that the primary template of Executor does not define its member-function execute:

template<int i>
struct Executor
{}; // empty

template<>
struct Executor <1>
{
 // defined only here
 template<typename T>
 static void execute(T&&)
 {
    cout << "Specific case" << endl;
 }
};

// client code
MultiTypeDispatcher< tuple<int, float, string> > dispatcher;

dispatcher.function(string("hello")); // Specific case!
dispatcher.function(1.0f); // Specific case!
dispatcher.function(1.0); // ops, compile-time error!

The last line tried to call Executor<0>::execute that does not exist! It’s simple, isn’t it?!

This code is here.

To conclude, tuples are important for grouping types (and values) as well as for metaprogramming jobs (like typelists, but typelists do not contain values); the standard provides all the basic bricks to operate on them – e.g. tuple traversal can be performed at compile-time – and building more complex components is feasible (e.g. exists_type). Never underestimate their potential!