Nicolás Brailovsky

Template metaprogramming VII: The Enemy Within

Posted by: nico on date

May 27th, 2010 | filed

Filed under: Templates

Submit to HN

Remember where were we last time? We had this code to define a list:

struct NIL {
typedef NIL Head;
typedef NIL Tail;
};
template struct LST {
typedef H Head;
typedef T Tail;
};
template Int{ static const int result = N; };
typedef Lst< Int<1>, Lst< Int<2>, Lst< Int<3> > > > OneTwoThree;

Now, to increase our template-foo, let’s practice some basic operations. The same operations you would implement to practice your skill any other functional language. If I remember correctly these where useful when learning Haskel: getting a list’s lenght, getting the Nth element, appending and preppending elements… that sort of stuff.

Let’s start with the most basic: getting the length of a list. We don’t really have a for loop so using recursion is the only way. It gets easier if we think again on our definition of list: “think of a list as tuple, two elements, the first (called head) will be the first element of the list and the second element as another list or a NIL object”. Whit this definition of a list, then it’s length turns to be 1 (the head) + the length of the remaining list (the tail), with a special case for the length of a NIL object which should always be 0. In template-speak:

template struct Length {
typedef typename LST::Tail Tail;
static const unsigned int tail_lenth = Length< Tail >::result;
static const unsigned int result = 1 + tail_length;
};
template <> struct Length {
static const unsigned int result = 0;
};

I know. You are thinking “wait, what?”. Well, even for this basic case we need to use some esoteric language features:

typename is needed to tell the compiler LST::Tail is a type and not a static variable (like Length::result is). Did you remember that from chapter IV?
We have to use recursive templates, but you probably already figured that out. You should remember this from chapter II.
We can provide a spetialization of a template. You should also remember this from chapter II.

Obviously, you can write it this way too: