Template metaprogramming: list of types and recursive templates

[Mark Stijnman]

I am trying to teach myself template metaprogramming and I have been
trying to create lists of related types. I am however stuck when I want
to make a template that gives me the last type in a list. I started by
using a linked list of types with templates like:

struct MyClass1 {};
struct MyClass2 {};
struct MyClass3 {};

struct NullType {};

template <typename T>
struct Link {
typedef NullType next_type;
};

template <>
struct Link<MyClass1> {
typedef MyClass2 next_type;
};

template <>
struct Link<MyClass2> {
typedef MyClass3 next_type;
};

etc.

I have also devised a simple template to check if a particular template
has a next type or not:

template <typename T>
struct IsNullType {
enum { value = false };
};
template <>
struct IsNullType<NullType> {
enum { value = true };
};

template <typename T>
struct HasNext
{
typedef typename Link<T>::next_type next;
enum { value = !IsNullType<next>::value };
};

Next I wanted to make a template that will give me the last element in
the list, i.e
Last<MyClass1>::type would be a typedef for MyClass3 in the example
above. What I am looking for is something equivalent to the following
pseudo-code:

type Last(input_type) {
if (has_next(input_type)) return Last(input_type->next);
else return input_type;
}

This suggests the need for recursive templates. Unfortunately, I can't
seem to get the syntax right. Can anybody point me back in the right
direction? I am aware that there are libraries that have already solved
this, like the Boost mpl, but I am more interested in the general
techniques involved to tackle something like this than a recommendation
of which library to use to solve this particular problem. Any help will
be greatly appreciated.

best regards Mark

 

[Howard Hinnant]

I am trying to teach myself template metaprogramming and I have been
trying to create lists of related types. I am however stuck when I want
to make a template that gives me the last type in a list. I started by
using a linked list of types with templates like:

struct MyClass1 {};
struct MyClass2 {};
struct MyClass3 {};

struct NullType {};

template <typename T>
struct Link {
typedef NullType next_type;
};

template <>
struct Link<MyClass1> {
typedef MyClass2 next_type;
};

template <>
struct Link<MyClass2> {
typedef MyClass3 next_type;
};

etc.

I have also devised a simple template to check if a particular template
has a next type or not:

template <typename T>
struct IsNullType {
enum { value = false };
};
template <>
struct IsNullType<NullType> {
enum { value = true };
};

template <typename T>
struct HasNext
{
typedef typename Link<T>::next_type next;
enum { value = !IsNullType<next>::value };
};

Next I wanted to make a template that will give me the last element in
the list, i.e
Last<MyClass1>::type would be a typedef for MyClass3 in the example
above. What I am looking for is something equivalent to the following
pseudo-code:

type Last(input_type) {
if (has_next(input_type)) return Last(input_type->next);
else return input_type;
}

This suggests the need for recursive templates. Unfortunately, I can't
seem to get the syntax right. Can anybody point me back in the right
direction? I am aware that there are libraries that have already solved
this, like the Boost mpl, but I am more interested in the general
techniques involved to tackle something like this than a recommendation
of which library to use to solve this particular problem. Any help will
be greatly appreciated.

Maybe something along the lines of:

template <class T, bool = HasNext<T>::value>
struct Last
{
typedef Link<T>::next_type;
};

template <class T>
struct Last<T, false>
{
typedef T next_type;
};

However I see no way to program First. The problem is that given a
Link<T>, there is only a way to find the next_type, and not this type.
You might try including someting along the lines of:

template <typename T>
struct Link {
typedef T this_type;
typedef NullType next_type;
};

-Howard

 

[Mark Stijnman]

Maybe something along the lines of:

template <class T, bool = HasNext<T>::value>
struct Last
{
typedef Link<T>::next_type;
};

template <class T>
struct Last<T, false>
{
typedef T next_type;
};

Thanks, but unfortunately, that will only give you the next type in the
list if there is any, or the type itself if there is not. It will not
recursively traverse the whole list until the end. I've tried several
variants that all boil down to something along the lines of:

template <typename T>
struct Last
{
typedef If<HasNext<T>::value, Last<Link<T>::next_type>::type,
T>::type type;
};

using a standard If<bool, typename Ta, typename Tb> template, but this
gives all sorts of compile errors, most of which seem to have to do

However I see no way to program First. The problem is that given a
Link<T>, there is only a way to find the next_type, and not this type.
You might try including someting along the lines of:

template <typename T>
struct Link {
typedef T this_type;
typedef NullType next_type;
};

-Howard

For now, I do not have a requirement to find the first element in the
list from a random link. But if I would, I would indeed need to
redefine the Link template. The list of types I have defined is
basically the equivalent of a singly linked list. "First" would require
one to define a doubly linked list. It would still require me to define
a recursive template. But as said, I have no need for it as yet.

 

[Tom Widmer]

Thanks, but unfortunately, that will only give you the next type in the
list if there is any, or the type itself if there is not. It will not
recursively traverse the whole list until the end. I've tried several
variants that all boil down to something along the lines of:

template <typename T>
struct Last
{
typedef If<HasNext<T>::value, Last<Link<T>::next_type>::type,
T>::type type;
};

using a standard If<bool, typename Ta, typename Tb> template, but this
gives all sorts of compile errors, most of which seem to have to do
with the fact that I use Last<T>::type before I have actually completed
defining it. So more specifically, I am looking for a way around this.

In your Last template, note that the Last recursion is instantiated even
if the If chooses the other branch, so you have an infinite recursion I
think. To get around that, you can introduce delayed instantiation:

template <typename T>
struct Identity
{
typedef T type;
};

template <typename T>
struct Last
{
typedef typename If<
HasNext<T>::value,

>::type::type type;

};

Tom

 

[Tom Widmer]

template <typename T>
struct Last
{
typedef typename If<
HasNext<T>::value,

};

Whoops, I got the If backwards. Should be:

template <typename T>
struct Last
{
typedef typename If<
HasNext<T>::value,

>::type::type type;

};

Tom

 

[Mark Stijnman]

Whoops, I got the If backwards. Should be:

template <typename T>
struct Last
{
typedef typename If<
HasNext<T>::value,

};

Tom

Thanks, this was quite enlightning. I had already realized at some
point that the none-chosen branch was also instantized, had forgotten
about it by the time I posted my original post, and realized it again
yesterday, but I would never have come up with the idea to circumvent
it by using this delayed evaluation trick. Many thanks for pointing
this one out, I'm sure it will come in handy in other circumstances as
well

I also found a different solution yesterday. I planned to post it, so
people with similar questions will be able to find more through google
than I did. I just hadn't gotten around to do that yet, so I'll do it
now. My solution also solves it by stopping the recursion on the
not-taken branch (when HasNext is false), but I did it by defining a
template specialization for Last on NullType:

template <typename T>
struct Last {
typedef typename Link<T>::next_type next;
typedef typename Last<next>::type last;
typedef typename If<HasNext<T>::value, last, T>::type type;
};

template <>
struct Last<NullType> {
typedef NullType type;
};

Note that I split up the nested templates into smaller steps, it seems
my compiler likes that better (g++ 3.3 and 4.0) - or I am just not
understanding all of templates syntax yet, which is also highly
possible At any rate, I don't think that this solution is any worse
or better than the solution given by Tom Widmer.