Posts Tagged ‘multi-type dispatching’

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!