3.7 Searching Typelists

How would you search a typelist for a given type? Let's try to implement an IndexOf algorithm that computes the index of a type in a typelist. If the type is not found, the result will be an invalid value, say - 1. The algorithm is a classic linear search implemented recursively.

   IndexOf
   Inputs: Typelist TList, type T
   Output: Inner compile-time constant value

   If TList is NullType, then value is -1.
   Else
     If the head of TList is T, then value is 0.
     Else
       Compute the result of IndexOf applied to TList's tail and T into a temporary 
         value temp.
       If temp is -1, then value is -1.
       Else value is 1 plus temp.

IndexOf is a relatively simple algorithm. Special care is given to propagate the "not found" value (-1) to the result. We need three specializations—one for each branch in the algorithm. The last branch (value's computation from temp) is a numeric calculation that we carry with the conditional operator ?:. Here's the implementation:

template <class TList, class T> struct IndexOf;





template <class T>


struct IndexOf<NullType, T>


{


   enum { value = -1 };


};





template <class T, class Tail>


struct IndexOf<Typelist<T, Tail>, T>


{


   enum { value = 0 };


};





template <class Head, class Tail, class T>


struct IndexOf<Typelist<Head, Tail>, T>


{


private:


   enum { temp = IndexOf<Tail, T>::value };


public:


   enum { value = temp == -1 ? -1 : 1 + temp };


};