Template metaprogramming VIII: A Rough Whimper of Insanity
Posted by: nico on 
Jun 3rd, 2010 | 
Filed under: 
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 tha 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 recursivly. 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 spetialization:
-
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 to types. We can use partial template spetialization 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.
Add A Comment