Struggling with implementation of a type list

Question

For educational purposes I want to write my own c++11 based typelist. The bare list looks like this:

template <typename ... Ts> struct type_list;

template <typename T, typename ... Ts>
struct type_list<T, Ts ...> {
    typedef T Head;
    typedef type_list<Ts ...> Tail;
};

template <typename T> struct type_list<T> {
     typedef T Head;
     typedef null_type Tail;
};

I have created a function called front for extracting the first element:

template <typename T> struct front;

template <typename TypeList>
struct front {
    typedef typename TypeList::Head type;
};

Which works as expected, i.e. this code

typedef type_list<int> lst;
typedef type_list<float,int> lst2;
typedef type_list<double,float,int> lst3;
typedef type_list<char,double,float,int> lst4;

std::cout << "front(lst1): " << typeid( front<lst>::type ).name() << std::endl;
std::cout << "front(lst2): " << typeid( front<lst2>::type ).name() << std::endl;
std::cout << "front(lst3): " << typeid( front<lst3>::type ).name() << std::endl;
std::cout << "front(lst4): " << typeid( front<lst4>::type ).name() << std::endl;

produces:

front(lst1): i
front(lst2): f
front(lst3): d
front(lst4): c

Naturally, a back function is the next step, however, I can't seem to get it to work. My code

template <typename T> struct back;

template <typename TypeList>
struct back {
    typedef typename std::conditional<std::is_same<typename TypeList::Tail, null_type>::value,
                      typename TypeList::Head,
                  typename back<typename TypeList::Tail>::type>::type type;
};

does not compile (clang 3.2) [lst is defined as before]:

TypeList.cc:33:71: error: no type named 'Tail' in 'null_type'
  typedef typename std::conditional<std::is_same<typename TypeList::Tail, null_type>::value,
                                                 ~~~~~~~~~~~~~~~~~~~^~~~
TypeList.cc:35:20: note:
  in instantiation of template class 'back<null_type>' requested here
    typename back<typename TypeList::Tail>::type>::type type;
    ^

TypeList.cc:54:44: note:
  in instantiation of template class 'back<type_list<int> >' requested here
    std::cout << "back(lst1): " << typeid( back<lst>::type ).name() << std::endl;
                                           ^
1 error generated.

---

Question

• Why does the std::conditional not trigger?

Answer 1

Improper usage of std::conditional

std::conditonal<condition, true-type, false-type>

Your problem boils down to that both the true- and false-type in std::conditional must yield a valid name, no matter which side the condition picks.

^{Note: There's a proposed solution at the end of this post if a full explanation isn't needed.}

---

Consider the below example:

struct A { typedef int type; };
struct B { /* empty */ };

template<class T>
struct some_trait {
  typedef typename std::conditional<
    /*  condition -> */ std::is_same<T, A>::value,
    /*  true-type -> */ typename T::type,
    /* false-type -> */ void
  >::type result;
};

---

Instantiating some_trait<A> will be perfectly valid, but what happens if we instantiate it with B?

template<>
struct some_trait<B> {
  typedef typename std::conditional<
    std::is_same<B, A>::value,
    typename B::type,  // (A), ill-formed
    void
  >::type result;
};

In the above we are pretending to be a compiler, and we replaced every occurance of T with B, it's not all that hard work but it has raised a very important issue with our primary-template.

When the compiler instantiates some_trait<T> with T = B, the true-type in our std::conditional will be B::type (A).

But since B has no name inside it called type we will get a compiler diagnostic saying that there's something wrong with our code, namely; we are trying to access a name which doesn't exist.

foo.cpp:15:37: error: no type named 'type' in 'B'
    /*  true-type -> */ typename T::type, // (A), ill-formed

---

---

Proposed Solution

There really is no doubt to what we have to do, and to put it in short; prevent our template from accessing names that potentially doesn't exist.

A simple way of doing this is to rely on explicit specialization, instead of using a std::conditional.

Sample implementation of back

template<typename TypeList>
struct back {
  typedef typename back<typename TypeList::Tail>::type type;
};

template<typename T>
struct back<type_list<T>> {
  typedef typename type_list<T>::Head type;
};

^{Note: If the instantiation of template<typename T> struct back; is a type_list with only one parameter, we know we are at the last node.}

Answer 2

The error results from the compiler trying to get a type name for the else part of the conditional even when the conditional evaluates to true.

You can fix that problem by creating a specialization of back.

template <typename T> struct back<type_list<T>>
{
    typedef T type;
};

Of course, then you can simplify the other implementation to

template <typename TypeList> struct back
{
    typedef typename back<typename TypeList::Tail>::type type;
};