3.10 Erasing Duplicates

An important operation on typelists is to erase duplicate values.

The need is to transform a typelist so that each type appears only once. For example, from this:

TYPELIST_6(Widget, Button, Widget, TextField, ScrollBar, Button)

we need to obtain this:

TYPELIST_4(Widget, Button, TextField, ScrollBar)

This processing is a bit more complex, but, as you might guess, we can use Erase to help.

   NoDuplicates
   Input: Typelist TList
   Output: Inner type definition Result
   
   If TList is NullType, then Result is NullType.
   Else
     Apply NoDuplicates to TList::Tail, obtaining a temporary typelist L1.
     Apply Erase to L1 and TList::Head. Obtain L2 as the result.
     Result is a typelist whose head is TList::Head and whose tail is L2.

Here's how this algorithm translates to code:

template <class TList> struct NoDuplicates;





template <> struct NoDuplicates<NullType>


{


   typedef NullType Result;


};





template <class Head, class Tail>


struct NoDuplicates< Typelist<Head, Tail> >


{


private:


   typedef typename NoDuplicates<Tail>::Result L1;


   typedef typename Erase<L1, Head>::Result L2;


public:


   typedef Typelist<Head, L2> Result;


};

Why was Erase enough when EraseAll would have seemed appropriate? We want to remove all duplicates for a type, right? The answer is that Erase is applied after the recursion to NoDuplicates. This means we erase a type from a list that already has no duplicates, so at most one instance of the type to be erased will appear. This recursive programming is quite interesting.