Tags: howtos, programming

Every C++ programmer sooner or later happens to stumble over template meta-programming. I was no exception. And suddenly, the old adage applied to me as well: "If all you have is a hammer, everything starts to look like a nail"

A very useful technique from template meta-programming is the concept of type lists. Briefly put, a type list is a list that contains types instead of values. It is thus defined at compile-time already. When might this be useful? In itself, probably never. Except for showing off. But in my opinion, the real utility of type lists unfolds when they are coupled with type switches. A type switch is another—you guessed it—concept from meta-programming. Given a type list, a type switch offers a way for calling a functor with a given type from the type list. The whole point is that the type switch permits the selection of a functor at runtime! Hold on to your hats, gentlefolks! This means I can essentially write something like this:

typedef TypeList<char, short, int, long> IntegerTypes;
Functor f;
TypeSwitch<IntegerTypes> ts;

unsigned int index = 0;
std::cin >> index;

ts( index, f );

The snippet above does not compile yet, but we’ll get there! You can see that we have deferred the decision about which type to use in the functor call. We let a user input at runtime decide about the type. Even though we are using templates. When I first learned about this, it seemed like magic to me. As we all know, any sufficiently analysed magic is indistinguishable from science, though. So, let’s try to get there. Throughout this post, I will include some snippets from real code. You can get the complete project on GitHub.

Type list

There are many ways for designing a type list. I chose a very easy one by limiting my type list to 10 types, which spared me from having to define it recursively. Andrei Alexandrescu has a great article about recursively-defined type lists and their applications. We start out differently, by defining a generic base case first:

struct EmptyType
{
};

template <
    typename T0 = EmptyType,
    typename T1 = EmptyType,
    typename T2 = EmptyType,
    typename T3 = EmptyType,
    typename T4 = EmptyType,
    typename T5 = EmptyType,
    typename T6 = EmptyType,
    typename T7 = EmptyType,
    typename T8 = EmptyType,
    typename T9 = EmptyType
> struct TypeList;

So far, nothing wild is going on. We have an empty type and a template declaration. We shall now use template specialization to refine the type list:

template <
    typename T0,
    typename T1,
    typename T2,
    typename T3,
    typename T4,
    typename T5,
    typename T6,
    typename T7,
    typename T8,
    typename T9
> struct TypeList
{
  typedef T0 head;
  typedef TypeList<T1,T2,T3,T4,T5,T6,T7,T8,T9> tail;

  enum
  {
    length = tail::length + 1
  };
};

This is also not very spectacular. We have a typedef for the head and a reduced type for the tail of the list. We also define a recursive enum. This is allowed because tail refers to a type that is known at compile-time. We are not finished, though. We still need to define a base case, namely that of the fully empty type list:

template <> struct TypeList<
    EmptyType,
    EmptyType,
    EmptyType,
    EmptyType,
    EmptyType,
    EmptyType,
    EmptyType,
    EmptyType,
    EmptyType,
    EmptyType>
{
  enum
  {
    length = 0
  };
};

And there we have it! A simple type list that is utterly useless. Well, we can at least query its size:

typedef TypeList<char, short, int, long> IntegerTypes;
std::cout << IntegerTypes::length << std::endl;

This should yield an output of 4. We can capture this in a nice struct:

template <typename TypeList> struct TypeListLength
{
  enum
  {
    value = TypeList::length
  };
};

This permits us to write TypeListLength<IntegerTypes>::value, making the intent somewhat clearer. Also, it makes writing an access struct easier.

Accessing a type from a type list

A useful operation for the type list would be an access functor. Given an index, we should be able to query the time at that index. If the index is out of range, we refuse to compile. That’s at least one good thing about templates—we catch problems early with very confusing compiler output. Let’s start with an access functor then:

template <
  typename TypeList,
  unsigned int Index,
  unsigned int Step = 0,
  bool Stop = ( Index == Step ),
  bool OutOfRange = ( TypeListLength<TypeList>::value == 0 )
> struct TypeListGet
{
  typedef typename TypeListGet<typename TypeList::tail, Index, Step + 1>::type type;
};

This is only the general case. We have an Index attribute that refers to the desired index in the type list by the client, and some "internal" attributes for keeping track of where we are in the type list.

Now let’s handle the specialization. The first one is easy. If we have reached the end of the type list, we define the struct to be empty. This will result in a compile-time error when a client aims to access an incorrect index:

template <
  typename TypeList,
  unsigned int Index,
  unsigned int Step,
  bool Stop
> struct TypeListGet<
  TypeList,
  Index,
  Step,
  Stop,
  true>
{
  // This is empty by design.
};

The other specialization is straightforward as well. In case Index and Step coincide, the Stop attribute is set to true. This means we have found our desired type and it is at the very beginning of the type list. Hence:

template <
  typename TypeList,
  unsigned int Index,
  unsigned int Step,
  bool OutOfRange
> struct TypeListGet<
  TypeList,
  Index,
  Step,
  true,
  OutOfRange>
{
  typedef typename TypeList::head type;
};

Now our demo program may become slightly more involved:

#include "type_list.hh"

#include <iostream>
#include <typeinfo>

int main( int, char** )
{
  typedef TypeList<char, short, int, long> IntegerTypeList;

  std::cout << IntegerTypeList::length << "\n";

  std::cout << "The type list has a length of " << TypeListLength<IntegerTypeList>::value << std::endl
            << "The first type is " << typeid( TypeListGet<IntegerTypeList, 0>::type ).name() << std::endl
            << "The second type is " << typeid( TypeListGet<IntegerTypeList, 1>::type ).name() << std::endl
            << "The third type is " << typeid( TypeListGet<IntegerTypeList, 2>::type ).name() << std::endl
            << "The fourth type is " << typeid( TypeListGet<IntegerTypeList, 3>::type ).name() << std::endl;

  return 0;
}

The output should read like this:

The type list has a length of 4
The first type is c
The second type is s
The third type is i
The fourth type is l

Still not terribly useful, but somewhat cool, I guess.

The type switch

Now let’s add the magic. Given a functor that provides a templated operator()(), we want to call it with a type that is selected at runtime using an index. The generalized case is very ugly here because we do not know the return type of the functor beforehand. Lucky for us, C++11 offers the decltype specifier:

template <
  typename TypeList,
  unsigned int Index = 0,
  bool Stop = ( Index == TypeListLength<TypeList>::value )
> struct TypeSwitch
{
  template <class Functor> decltype( Functor().template operator()<typename TypeListGet<TypeList, Index>::type>() ) operator()( unsigned int i, Functor f )
  {
    if( i == Index )
      return f.template operator()<typename TypeListGet<TypeList, Index>::type>();
    else
    {
      TypeSwitch<TypeList, Index + 1> next;
      return next.operator()( i, f );
    }
  }
};

The decltype ensures that we get the proper return type of the functor for the current type at the requested index of the type list. If we have not found the proper index yet, we create a new type switch (with adjusted index) and recurse.

Now the only thing that is left to handle is the when the index goes out of bounds. Here, we can use a specialization with a fixed value for the Stop attribute. Recall that it is set when the index is equal to the length of the type list, i.e. upon encountering the first invalid index.

template <
  typename TypeList,
  unsigned int Index
> struct TypeSwitch<
  TypeList,
  Index,
  true>
{
  template <class Functor> decltype( Functor().template operator()<EmptyType>() ) operator()( unsigned int /* i */, Functor /* f */ )
  {
    throw std::runtime_error( "Index is out of range" );
  }
};

And that’s it. We may now use such cool constructions as the following:

#include "type_list.hh"
#include "type_switch.hh"

#include <iostream>
#include <typeinfo>

struct Functor
{
  template <class T> void operator()()
  {
    std::cout << "Called with the following type: " << typeid(T).name() << std::endl;
  }
};

int main( int, char** )
{
  typedef TypeList<char, bool> MyTypes;

  Functor f;
  TypeSwitch<MyTypes> ts;

  for( unsigned int i = 0; i < TypeListLength<MyTypes>::value; i++ )
    ts( i, f );

  try
  {
    ts( 42, f );
  }
  catch( std::runtime_error& e )
  {
    std::cerr << "Oops, this type does not exist: " << e.what() << std::endl;
  }

  return 0;
}

This results in the following output:

Called with the following type: c
Called with the following type: b
Oops, this type does not exist: Index is out of range

OK, maybe the program is not completely useful. In general, type switches can be very useful, though. I have used it in the past to loop over pre-defined types for volume data. The functor in this case simply checked whether it was possible to load volume data of a fixed size with a given type. If so, we knew that we had identified the right type. The advantage of this approach is that it naturally scales with the number of types we define. We do not have to resort to ugly dynamic_cast constructions or something like that.

If you want to learn more, I can only recommend the books by Andrei Alexandrescu. If you are a bit like me, please also take JWZ’s law into account:

Some people, when confronted with a problem, think "I know, I’ll use regular expressions template meta-programming." Now they have two problems.

Enjoy your templates!

I want the code

Sure, you can have it. It’s on GitHub and licensed under an MIT license.