Posts Tagged ‘Template Metaprogramming’

This post is basically a meditation on static design choices and code expressivity.

Some days ago I was writing a simple wrapper around std::map supporting a couple of elemental features:

  • succinct syntax for inserting/updating key-value elements, e.g.:

selector<string, int> sel;

sel.at("one") = 1; // insertion

sel.at("two") = 2; // insertion

sel.at("one") = 10; // update

sel.get("one"); // 10

  • mechanism to handle a possible default value if an inexistent key is looked up.

Note that possible means optional and the client should be able to choose either to provide a default value or not. If a default value is not provided, the get() method just throws. From an Object-Oriented standpoint, a simple way to deal with this requirement is to have an interface, say IDefaultValueProvider<T>, and two concrete classes, say ActiveDefaultValueProvider<T> and PassiveDefaultValueProvider<T> (sort of Null Object Pattern).

Our selector<K,T> will store a unique_ptr<IDefaultValueProvider<T>>, passed in the constructor. Something like:


selector<string, int> sel ( make_unique<ActiveDefaultValueProvider<int>(0) );

sel.at("one") = 1; // insertion

sel.get("one"); // 1

sel.get("foo"); // 0 (default)

selector<string, int> sel_nd ( make_unique<PassiveDefaultValueProvider<int>() );
// or just selector<string, int> sel_nd; // default-parameter

sel_nd.get("one"); // throws

Ok this works. How does this implementation cost?

  • we wrote an interface and two concrete classes
  • we need a dynamic allocation (unique_ptr)
  • the selector has to store a unique_ptr
  • defaulted-selector and non-defaulted-selector have the same type

The latter point leads to (probably) the most important issue: we don’t know what will happen when selector.get() is called. Will it throw? Will not? Should we flood our code with plenty of try/catch? To solve this problem we can, for example, change the return value of get(): instead of getting a T&, we can return a pair<bool, T&> where the first element is true if the key exists and the second is the value corresponding to that key (if the key does not exist, T& is binded to a global fake T).

Ugly.

We can do better, but does it make sense? I think no. This problem can be addressed from another perspective: the client must decide which type of selector she wants, if a defaulted one or not. This way the user will know exactly what will happen. When designing classes it is important to discern between static and dynamic abstractions. Think of “configurability”: does it make sense to configure a certain instance of a class at compile-time (e.g. using a template) or at run-time (e.g. reading from a file)? For my simple example, the answer is probably the first.

Ok, how to express this static choice? An idea is to use templates and this is the second part of my meditation: how to communicate our intentions effectively? In particular, what if the readers (e.g. maintainers) of our code are not very familiar with TMP? I’d like to find a middle way combining compactness and clarity.

The problem now is: a selector must be instantiated by providing a template parameter, say either enable_default or disable_default. What we expect:


selector<string, int, enable_default> sel1 (10); // default = 10

selector<string, int, enable_default> sel2; // compile-error (default not provided)

selector<string, int, disable_default> sel3; // ok

selector<string, int, disable_default> sel4 (20); // compile-error

Suppose enable_default and disable_default are boolean flags (respectively, true and false). We have at least two possibilities here:

  • write two specializations (verbose but quite clear)
  • use static_assert and a bit of metaprogramming:
#include <type_traits>

template<typename K, typename T, bool flag>
struct selector
{
  template<typename V>
  selector(V&& pDefault) : default_value(std::forward<V>(pDefault))
  {
    // if (flag == true) OK, else ERROR (and complain)
    static_assert(flag, "Default value unexpected");
  }

  selector() : default_value(1)
  {
    // if (flag == false) OK, else ERROR (and complain)
    static_assert(!flag, "Provide a default value");
  }

private:

   // if (flag == true) T, else char (a fake default)
   typename std::conditional<flag, T, char>::type default_value;

// ... implementation ...
};

This is more readable and clearer than lots of enable_if and other tricks. But we can do much better by using Policy-Based Design and   moving the (single) point of variation to real classes (our policies). We’ll get rid of static_asserts and std::conditional.

This is a possible draft:

template<typename T>
struct disable_default
{
  T& get_default()
  {
    throw 1;
  }

  const T& get_default() const
  {
    throw 1;
  }
};

template<typename T>
struct enable_default
{
  template<typename Value>
  enable_default(Value&& def_value) : default_value(std::forward<Value>(def_value))
  {
  }

  const T& get_default() const
  {
     return default_value;
  }

  T& get_default()
  {
     return default_value;
  }

private:
  T default_value;
};

template<typename K, typename T, template <typename> class default_policy = enable_default>
struct selector : public default_policy<T>
{

 using typename default_policy<T>::get_default;

 template<typename Value>
 selector(Value&& def_value) : default_policy<T>(std::forward<Value>(def_value))
 {
 }

 selector()
 {
 }

 T& select(const K& key)
 {
   return const_cast<T&>(static_cast<const selector*>(this)->select(key));
 }

 const T& select(const K& key) const
 {
   auto it = selector_map.find(key);
   if ( it != end(selector_map) )
   {
      return it->second;
   }
   else
   {
      return get_default();
   }
 }

//... other stuff omitted here ...

private:
   std::map<K,T> selector_map;
};

Let’s see how to instantiate selectors:

selector<string, int, enable_default> def_selector(0);

//...

selector<string, int, disable_default> ndef_selector;

A possible (and a bit different) code is on ideone.

A couple of notes:

  • the policy is a “template template parameter” to avoid redundancy
  • a constructor is not generated if not used (e.g. using enable_default, the empty ctor is not generated at all)

The mechanism is clear because it is sort of driven by design: enable_default wants to be constructed with an argument, then the host class (the selector) just forwards its constructor parameter to the base class. If the user does not provide a parameter, the code simply does not compile. If the code is not easy to read yet, put a static_assert (or a comment) to clarify our intentions, but I think it’s not needed.

My final note about this meditation is: template metaprogramming aims to be clear and helpful instead of tricky and painful. We have lots of possible solutions, more or less complicated. Policy-Based Design is not only a usage of templates, but also a tool for specifying constraints, class rules, and (static) abstractions. It helps to express choices by (static) design.

I conclude with a question for you about expressivity/clarity: given, for example, this code I wrote in a previous post to force the user to pass an rvalue-reference:


// [1] (does not compile on VC2010)
template<typename T>
auto make_move_on_copy(T&& aValue)
 -> typename enable_if<is_rvalue_reference<decltype(aValue)>::value, move_on_copy<T>>::type
{
    return move_on_copy<T>(move(aValue));
}

// [2]
template<typename T>
move_on_copy<T> make_move_on_copy(T&& aValue)
{
   static_assert(is_rvalue_reference<decltype(aValue)>::value, "parameter should be an rvalue");
   return move_on_copy<T>(move(aValue));
}

I think SFINAE here is overused, whereas static_assert is easier and more readable. Which do you prefer?

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!

[Edit]

When I wrote this post it was longer and more complicated than now. Thanks to Davide Di Gennaro for showing me that this approach was simpler than I thought!

[/Edit]

The curiously recurring template pattern (CRTP) is a C++ idiom in which a class X derives from a class template instantiation using X itself as template argument [Wikipedia]. Its general form is pretty easy:

template <typename T>
struct Base
{
    // ...
};

struct Derived : Base<Derived>
{
    // ...
};

Typically, this pattern is used for static polymorphism (aka, simulated dynamic binding) as well as code injectio: inside Base’s methods you can take advantage of the fact that T derives from Base, then you can static_cast the this pointer to T*:

template <typename T>
struct Base
{
    void interface()
    {
        // ...
        static_cast<T*>(this)->implementation();
        // ...
    }
};

struct Derived : Base<Derived>
{
    void implementation();
};

This short post is not about CRTP in general – for this read, for example, Wikipedia – here I’ll show how to use this pattern for polymorphic method chaining. Briefly: each method returns an object (possibly the current object itself), allowing the calls to be chained together in a single statement (a typical use – the named-parameter idiom – here “Learn how to support named parameters in C++“).

Suppose you have to write a trivial printer class looking like this:

class Printer
{
public:
      Printer(ostream& pstream) : m_stream(pstream) {}

      template <typename T>
      void print(T&& t) { m_stream << t; }

      template <typename T>
      void println(T&& t) { m_stream << t << endl; }
private:
      ostream& m_stream;
};

I’m used to be lazy and I get tired writing code like this (suppose I may not use the operator<<):

Printer printer(cout);
printer.print("Message");
printer.print(105);
printer.println(objectHavingOutOperator);

So I change a couple of things in the Printer class:

class Printer
{
public:
      Printer(ostream& pstream) : m_stream(pstream) {}

      template <typename T>
      Printer& print(T&& t) { m_stream << t; return *this; }

      template <typename T>
      Printer& println(T&& t) { m_stream << t << endl; return *this; }
private:
      ostream& m_stream;
};

Then we write:

Printer(cout).print("Message").print(105).println(objectHavingOutOperator);

Ok, that’s good but what if I create some classes deriving from Printer? Chaining is lost, isn’t it? That’s because the return type of both print and println is Printer&, ever.

A simple way to maintain the chain consists in using CRTP:

template <typename ConcretePrinter>
class Printer
{
public:
      Printer(ostream& pstream) : m_stream(pstream) {}

      template <typename T>
      ConcretePrinter& print(T&& t)
      {
          m_stream << t;
          return static_cast<ConcretePrinter&>(*this);
      }

      template <typename T>
      ConcretePrinter& println(T&& t)
      {
          m_stream << t << endl;
          return static_cast<ConcretePrinter&>(*this);
      }
private:
      ostream& m_stream;
};

class CoutPrinter : public Printer<CoutPrinter>
{
public:
     CoutPrinter() : Printer(cout) {}

     CoutPrinter& SetConsoleColor(Color c) { ... return *this; }
};

... client code ...

CoutPrinter().print("Hello ").SetConsoleColor(Color.red).println("Printer!");

This approach does not allow using a Printer class directly (sans a deriving class, due to CRTP). To evade this requirement, I suggest you to provide another base printer, like this:

class BasePrinter : public Printer<BasePrinter>
{
public:
    BasePrinter(ostream& stream) : Printer(stream) {}
};

This way you can use the Printer directly:

BasePrinter(cout).print("Hello ").println("Printer");

In general, for a longer hierarchy:

// Base class
template <typename T>
struct Base
{
 T& BaseMethod()
 {
    return static_cast<T&>(*this);
 }
};

// Inherits from Base
template <typename T>
struct Child : public Base<T>
{
 T& ChildMethod()
 {
    return static_cast<T&>(*this);
 }
};

// Inherits from Child
template <typename T>
struct ChildChild : public Child<T>
{
 ChainingReturnType& ChildChildMethod()
 {
    return static_cast<T&>(*this);
 }
};

...

Chaining works at compile-time because it uses the static type of the objects involved.

What I don’t like is the number of classes we generate to use directly all the bases: we have to define an alter-ego for each of them – and introducing a new level of indirection could be verbose:

template<typename T>
struct Base
{
   Base(...suppose some parameters...) : ... {}

   //some methods
};

struct Base_User : public Base<Base_User>
{
   Base_User(...) //...must construct Base...
   // sort of duplicated code
};

template<typename T>
struct Derived : Base<T>
{
   Derived(...suppose some parameters...) //...must construct Base & itself...

   // other methods
};

struct Derived_User : public Derived<Derived_User>
{
   Derived_User(...) //...must construct Derived...
   // sort of duplicated code
};

If you want to avoid repeating code (e.g. construction) in _User classes you can employ the idea I showed in a previous version of this post: instead of deriving from Base, Base_User is just a typedef of Base using a special type (NoCRTP) as a template parameter. This type either “enables or disables” the usage of CRTP. The code can seem complicated but it’s simpler than you think:

// trivial type-selector

template<bool, typename T, typename U>
struct select_
{
   typedef T type;
};

template<typename T, typename U>
struct select_<false, T, U>
{
   typedef U type;
};

// just a placeholder
struct NoCrtp;

// support macro
#define CRTP_TYPE(who) typename select_ < is_same<T, NoCrtp>::value, who, T>::type

// another way to realize polymorphic chaining
template<typename T>
struct Base
{
   // if (T == NoCrtp)
   //   CrtpType = Base ("disable" CRTP)
   // else
   //   CrtpType = T ("enable" CRTP)
   typedef CRTP_TYPE(Base) CrtpType;

   CrtpType& chain()
   {
      //...
      return static_cast<CrtpType&>(*this);
   }
};

typedef Base<NoCrtp> Base_User; // no duplication

template<typename T>
struct Derived : public Base<CRTP_TYPE(Derived<T>)>
{
   typedef CRTP_TYPE(Derived) CrtpType;

   CrtpType& chain_derived()
   {
     //...
    return static_cast<CrtpTyep&>(*this);
   }
};

typedef Derived<NoCrtp> Derived_User; // no duplication

...

This machinery is a bit more complicated to understand but it can avoid duplication. Choose the implementation that fits your needs.

In summary: method chaining may be elegant and useful. Its power is damped if inheritance is involved so I suggest to employ CRTP, “champion of static polymorphism” which can support method chaining, avoiding you to write lots of code. If you have more than a couple of classes your codebase may be more verbose, but don’t be afraid of this idiom, it can be a valuable ally!

A template is a way to generate code. C++ supports generic programming through the template mechanism, which allows defining parameterized classes and functions, over a set of types, functions or constants. Templates together with other C++ features constitute a Turing-complete (e.g. a queue automata), compile-time sublanguage of C++.

For example:

template <typename One, typename Two>
struct Pair
{
 One first;
 Two second;
};

Providing arguments to a template, instantiates (at compile-time) the template with those arguments:

Pair<float,int> myNumericalPair;
 // One = float
 // Two = int

This produces something like this:

struct Pair
{
 float first;
 int second;
};

Remember that template classes (and functions) are not generated if not used, then the following code is correct (but clearly immoral!):


template <typename T>
struct MyTemplateClass {
	void functionThatWorksWithInt() {
		cout << "Just a ping on cout!" << endl;
	}

	void functionThatDoesNotWorkWithInt() {
		member.function(); // int does not have "nested functions"!
	}

	T member;
};
//...
MyTemplateClass<int> mtc; // ok
mtc.functionThatWorksWithInt(); // ok

In the code above, the function functionThatDoesNotWorkWithInt is never called by mct so the code is correct! This is a caveat, be careful. I’m going to face with this problem at the end of this post.

Another important feature is template specialization: given a template with one or more parameters we can provide special versions of the template where some of the parameters are fixed. There are two types of specializations: full (when all the arguments are specialized) and partial (when arguments have particular structure):

/* Primary template */
template<typename T>  class Set
{
    // e.g. Use a binary tree
};

/* Full specialization */
template <> class Set<char>
{
    // e.g. Use a bit vector
};

/* Partial specialzation */
template <typename T>  class Set<T*>
{
    // e.g Use a hash table
};

When we have more than one parameter, we can specialize a subset of the types:

/* general version */
template<typename T, typename U> class A { ... };

/* specialization on T */
template<typename U> class A<int,U> { ... };

/* specialization on both */
template<> class A<int,int> { ... };

A<double, double> a;  // uses general version
A<int, double> b;     // uses first specialization
A<int, int> a;        // uses second specialization

Partial specialization does not apply to functions:

template <typename T, typename U>  T fun(U obj) {...}

// the following is illegal
template <typename U>  void fun<void, U>(U obj) {...}

// the following is legal (overloading)
template <typename T> T fun(Window obj) {...}

The parameters of a template can be constant numbers (they are known at compile-time) instead of types (and we can also specialize on certain numbers):

template<unsigned n>
struct Num {
     static const unsigned num = n;
};

Num<5> x;
Num<8> y;

cout << x.num << endl; // prints 5
cout << y.num << endl; // prints 8

We have all the key concepts to talk about Metaprogramming: a metaprogram is a program that produces or manipulates constructs of a target language. Specifically, a template metaprogram is a C++ program that uses templates to generate customized C++ code at compile-time.

Why would I ever want to do this? You rebut.

TMP has a great numbers of benefits. The most obvious reason  to rely on a metaprogram is that by dong as much work as possible before the resulting program starts, we get faster (but sometims “bigger”) programs. A subtler but perhaps more important argument for using a metaprogram is that the result of the computation can interact more deeply with the target language. For example, the brace-enclosed actions in a YACC grammar can contain arbitrary C/C++ code to be executed as part of the generated parser. That’s only possbile because the actions are processed during grammar compilation and passed on to the target C/C++ compiler.

Instead of doing computation at runtime or compile time, we could just do it by hand. A good metaprogram can outstrip this by enabling a more expressive and reusable code, narrowing human errors and improving the code maintenance process.

Ok, I can believe you, but when is metaprogramming appropriate? In their excellent book, Abrahams  and Gurtovoy – C++ Template Metaprogramming: Concepts, Tools and Techniques from Boost and Beyond – say that if any three of the following conditions apply then a metaprogrammed solution can be appropriate:

  • You want the code to be expressed in terms of the abstractions of the problem domain.
  • You would otherwise have to write a great deal of boilerplate implementation code.
  • You need to choose component implementations based on the properties of their type parameters.
  • You want to take advantage of valuable properties of generic programming in C++ such as static type checking and behavioral customization, without loss of efficiency.
  • You want to do it all within the C++ language, without an external tool or custom source code generator.

Stop talking, let’s write some code! I’ll show you a simple metaprogram. Note that the code generation engine embedded in the C++ compiler can actually make some calculation by using recursion – to learn TMP, the functional metaprogrammer in you should pipe up!

Here is how to compute the factorial:

template<int n>
struct Fact {
    enum { value = n * Fact::value };
};

template <>
struct Fact {
    enum { value = 1 };
};

cout << Fact<5>::value << endl;

The key trick is to combine specialization with integral parameters. The specialization “stops” the recursion (the base case).

TMP is a programming world (I said, C++ TMP is a programming language, just like C++) then there exist several techniques and usages.

If you want to deeply learn TMP, I suggest you to read a handful of books:

  • C++ Template Metaprogramming: Concepts, Tools and Techniques from Boost and Beyond – it employs boost metaprogramming library (MPL) – a very good and widespread library.
  • Modern C++ Design: Generic Programming and Design Patterns Applied (by Andrei Alexandrescu) – it employs Loki (TMP library written by Alexandrescu). This book is a must-have.
  • C++ Templates: The Complete Guide (by Vandevoorde and Josuttis) – a very good book, it provides complete and accurate information on using templates.

Let’s write other metaprograms!

Sometimes you need to detect if two generic types A and B are in a relationship of convertibility, say A is convertible to B. We know that sizeof() is a compile-time mechanism of C/C++ to compute the size of a type (since it is done at compile-time, its argument is not actually executed at run-time, but it is only evaluated). For example, if the argument contains a function call, it only checks its (return) type:

int myIntFunction();
sizeof(myIntFunction()); // equivalent to sizeof(int)

We can define two types of different sizes:

typedef char OneByte;
class TwoBytes { char dummy[2]; };

Now take a breath and read:

template<typename T, typename U>
class Conversion {
     typedef char OneByte;
     class TwoBytes { char dummy[2]; };
     static OneByte Test(U);
     static TwoBytes Test(...);
     static T MakeT();
public:
     enum { exists = sizeof(Test(MakeT())) == sizeof(OneByte) };
};

What’s happened?

Keep calm.

We have two template parameters: T and U. There is a simple MakeT() function which type is T. We have also two functions Test(): the first takes one of the template arguments (U) and the other everything (…).

Intuitively, if we invoke MakeT() when T = U then the type of MakeT() is U. At this point, we get the “sizeof” Test(U) (because we just have a Test(U) function) and this returns OneByte. Then the left-hand side is equal to the right-hand side of the last expression, so the enum exists is 1 (aka true).

The key point is to understand if the compiler can automatically convert T to U. If so, it will use Test(U), otherwise Test(…)Test(U) and Test(…) have different types with different sizes, then the final equality expresses if the conversion takes place.

On the wake of the factorial example, here it is another recursive metaprogram. The idea is to compute the sum of the squares of the first n natural numbers. Let’s start with the metafunction (class-template as a function) that computes the square of a number. It’s quite simple but remember that it has to compute values at compile-time:

template<int n>
struct Square
{
	enum { RET = n*n };
};

Ok, that was easy. Now we have to use this metafunction inside another metafunction! We have to employ this metafunction as a template parameter. The syntax is a little bit more complicated but don’t be scared:

template <int n, template<int> class F>
class MyClassWithMetafunction { ... };

This means that MyClassWithMetafunction receives an int (n) and a class (F) that receives an int. No more. Here it is the remaining code:

// metafunction as "template parameter"
template <int n, template<int> class F>
struct Accumulate
{
	enum { RET = Accumulate::RET + F::RET };
};

template <template<int> class F>
struct Accumulate<0, F>
{
	enum { RET = F::RET };
};

Accumulate<0,F> is the usual base case that stops the recursion. At each step, Accumulate sums the result of the metafunction applied to the current n and goes on with the recursion. Wake up the functional programmer in you, he’ll understand better!

Are you fed up with TMP?! Let me show you the last example and I stop. I promise!

Sometimes we would like to know if a type has a certain function. Generally this is called Interface Checking. This (also) deal with problems I pointed out at the beginning, talking about int and mysterious code that compiles though ints don’t have nested functions (just because these functions were not called)! Suppose we have a class MyClonable that has a Clone() function:

class MyClonable {
public:
	MyClonable* Clone() const { ... }
};

We want to write a metaprogram to verify if a type has this function. To do this, a good idea is to separate the concept of checking by confining it into a separate class.

template <typename T>
class HasClone
{
public:
	HasClone() { void (*p)() = Constraints; }

	static void Constraints()
	{
		T* (T::*test)() const = &T::Clone;
	}

};

template <typename T>
class InterfaceCheck : HasClone<T> {};

InterfaceCheck<MyClonable> c; // if MyClonable didn't have Clone then this would be a compilation error

First thing to undestand: we use a “base” class (HasClone<T>) to encapsulate the checking, when we construct the base class we execute its constructor that declares a pointer to the Constraints function. Setting up this little inheritance is also convenient to force the compiler to always instantiate HasClone<T> and then check the “constraints” it brings along.

Constraints does the trick (still at compile-time): it declares a pointer to the Clone member function of the template parameter (T), but if this function does not exist, all the evil spirits wil jump out to catch you because you’ll have a compilation error. Don’t get confused with all those pointer definitions, the code is easier than you think!

I hope this post can be useful to intrigue you about metaprogramming. I heartly recommend you to write your codes, starting with simple examples (the factorial is a good start). Then you can read one of the books I mentioned before. And don’t forget to wake up the functional programmer in you!