Remember where were we last time? We had this code to define a list:
struct NIL {
typedef NIL Head;
typedef NIL Tail;
};
template <typename H, typename T=NIL> struct Lst {
typedef H Head;
typedef T Tail;
};
template <int N> struct 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 <typename LST> struct Length {
typedef typename LST::Tail Tail;
static const unsigned int tail_length = Length< Tail >::result;
static const unsigned int result = 1 + tail_length;
};
template <> struct Length <NIL> {
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:
template <typename LST> struct Length {
static const unsigned int result = 1 + Length< typename LST::Tail >::result;
};
template <> struct Length {
static const unsigned int result = 0;
};
The rest of the "basic" list-operations are quite similar, but I'll leave that for another post.
Thank you Stéphane Michaut for pointing out typos and bugs in the code listings