# Template metaprogramming VIII: A Rough Whimper of Insanity

**Posted:**June 3, 2010

**Filed under:**C++, Templates Leave a comment

Remember last time? We learned how to get the lenght of a list. This time I’ll introduce some more of these basic ops. Let’s begin with “Nth”: getting the Nth element of a list; which, remember, in this case is a type, not a concrete element. This means the Nth element will be something like int, char, const char*, not 1, 2 or 3. We introduced a trick to get around this limitation before using a template <int>, go there to refresh your memory if needed.

So, what would the coloquial definition of “Nth” be? I’d put it like “The operation Nth for a list equals the head of the list for N = 0 and Nth (minus one) of the tail otherwise”. A little bit more formally:

Nth(0, lst) <- lst.head Nth(n, lst) <- Nth(n-1, lst.tail)

Translating this to C++ should be a breeze to you now. Try it, I’ll wait. Read? OK, this is MY answer:

template <typename LST, int N> struct Nth { typedef typename LST::Tail Tail; typedef typename Nth<Tail, N-1>::result result; }; template <typename LST> struct Nth<LST, 0> { typedef typename LST::head result; };

Though the structure is very similar to the previous “basic operation”, getting the length of a list, the concept is quite different. This time we’re defining a return type recursively. Anyway, it was too easy indeed, let’s try a more complex operation now.

How can we check if an element exists on a list? Seems easy enough, an element is included in a list if the head equals the element itself or if the element is included in the tail. In the pseudo language I just invented:

Includes(lst.head, lst) <- true Includes(e, lst) <- Includes(e, lst.tail)

Looks easy, right? Well, there’s a bug there, can you spot it? Yeah, we’re missing the false condition. We should add a third specialization:

Includes(lst.head, lst) <- true Includes(e, NIL) <- false Includes(e, lst) <- Includes(e, lst.tail)

Again, let’s translate the pseudocode to C++. Try it, I’ll wait. Read? OK, this is MY answer:

template <class Elm, class Lst> struct Includes { typedef typename LST::head Head; typedef typename LST::tail Tail; static const bool found = (Elm == Head); static const bool found_tail = Includes<Elm, Tail>::result; static const bool result = found || found_tail; }; template <class Elm> struct Includes <Elm, NIL> { static const bool result = false; };

Looks nice, doesn’t it? Too bad it won’t work, you can’t compare two types. What would (int == char) mean in C++? We need a helper there, some kind of trick to compare two types. We can use partial template specialization again:

template <class X, class Y> struct Eq { static const bool result = false; } template <class X> struct Eq<X, X> { static const bool result = true; }

With this little struct now we can write our include operation this way:

template <class Elm, class Lst> struct Includes { static const bool result = Eq<Elm, typename LST::head>::result || Includes<Elm, typename LST::tail>::result; }; template <class Elm> struct Includes<Elm, NIL> { static const bool result = false; };

Very esoteric looking, the right mix of Haskel, C++ and booze to ensure job security for life. Next time we’ll find a way to search for the position of an element, a somewhat more complicated task.