As you could see in the scheme section, we need 4 primitives to create and manipulate lists:
  • cons - the pair constructor
  • empty - empty list identifier
  • first to access the current element
  • rest to process remaining part of the list in recursive calls

The way to represent those in C++ templates is much simpler than you would think:
class emptytype {};

template <typename HEAD, typename TAIL>
struct typelist {
   typedef HEAD head;
   typedef TAIL tail;
}; 

That's all. Now typelists can be constructed by simply writing:
typelist<char, typelist<int, typelist<std::string, emptytype> > >

We can ease this task, and make it cleaner by serie of macros:
#define TYPELIST_1(T1)                   typelist<T1, nulltype>
#define TYPELIST_2(T1, T2)               typelist<T1, TYPELIST_1(T2)>
#define TYPELIST_3(T1, T2, T3)           typelist<T1, TYPELIST_2(T2, T3)>
#define TYPELIST_4(T1, T2, T3, T4)       typelist<T1, TYPELIST_3(T2, T3, T4)>
#define TYPELIST_5(T1, T2, T3, T4, T5)   typelist<T1, TYPELIST_4(T2, T3, T4, T5)>
// etc.

There are also more elegant ways to construct typelists, which do not use macros at all, but we will go with TYPELIST_X.

Finally we can write our first meta-function to calculate the number of elements in the "list". Just read the following block and let yourself think about it for couple of minutes, before continuing reading :)
/**
 * Recursive calculation of the length of
 * given typelist
 */
template <typename> struct tlist_length;

template <typename HEAD, typename TAIL>
struct tlist_length< typelist<HEAD, TAIL> > {
   enum { value = 1 + tlist_length<TAIL>::value };
};

template <> 
struct tlist_length< nulltype > {
   enum { value = 0 };
};

void test_typelists(void) {
   typedef TYPELIST_5(char, int, std::string, double, unsigned long) tlist;
   std::cout << "Number of types in list: "
                << tlist_length<tlist>::value << std::endl;
}

// The output:
// Number of types in list: 5

Let's analyze this code, as some of the patterns used in this example will follow us through all meta-functions. First we defined an interface for our metafunction in form of
template <typename> struct tlist_length;

This is a "primary" template definition, and rest of templates are "specialized" verions of it.

Following block is the "body" of the recursion:
template <typename HEAD, typename TAIL>
struct tlist_length< typelist<HEAD, TAIL> > {
   enum { value = 1 + tlist_length<TAIL>::value };
}; 

it "recursively calls" tlist_length<TAIL> and uses "retuned value" tlist_length<TAIL>::value to calculate its own value.

Finally we need a termination condition, and for this purpose we've specialized a template for a case of empty list
template <> 
struct tlist_length< nulltype > {
   enum { value = 0 };
}; 


So, from now on you'll be able to read meta-functions as if it was a regular C++ code ;)

Last edited Nov 30, 2007 at 6:22 AM by migo, version 1

Comments

No comments yet.