Building compilation type lists one by one (C ++)

Question

I want to compile a list (actually: a set) of types at compile time by adding types one by one. Something like that:

struct HeadOfList; struct Item1; [ addToList<Item1, HeadOfList> ] struct Item2; [ addToList<Item2, HeadOfList> ] 

I don't care how the list is stored. I am thinking of something like this:

 template<typename T> struct NextInList { typedef void type; }; template<> struct NextInList<HeadOfList> { typedef Item1 type; }; template<> struct NextInList<Item1> { typedef Item2 type; }; template<> struct NextInList<Item2> { typedef Item3 type; }; 

but a boost::mpl::list just as good. The type order is also irrelevant, I just want them to be able to go through them and add new elements to them.

I have a bad idea about this, because such a construction will mean that, for example, LastElementOf<MyList>::type will be compiled for different types at different points in the source file (before and after adding a new element), and it seems fictitious to me. However, this is exactly what I want now.

Do you think this is possible? Allowed C ++ 11.

Update: I just want to add that I do not know the last element added to the list when adding a new element, but I know the list itself (for example, the head of the list)

Answer 1

After consultation with comp.lang.C ++. moderated I came up with the code described in detail below. The PushBack() macro is used to add new items to the list, you can PushBack() over items using the Next() macro, and the last item can be recognized from the fact that its "next item" by itself. So, a very simple code example:

 struct A {}; namespace NS1 { struct B {}; struct C {}; struct D {}; // building up the compile-time list struct Head; PushBack(Head, A); PushBack(Head, B); } PushBack(NS1::Head, NS1::C); namespace NS1 { PushBack(Head, D); } // iterate through the list namespace NS2 { // end of the list reached (recognized from PrevItem == Item) template <class ListId, class Item> void print(Wrapper<Item>, Wrapper<Item>) {} // process Item and advance to the next element template <class ListId, class PrevItem, class Item> void print(Wrapper<PrevItem>, Wrapper<Item>) { cout << typeid(Item).name() << endl; print<ListId>(Wrapper<Item>(), Wrapper< Next(ListId, Item) >()); } } 

A more detailed example, which also contains an iterator, to facilitate the use of the list, can be found here or here .

The most important part of the "library":

 /// Helper class to wrap incomplete types and avoid instantiation of T template<class T> struct Wrapper {}; namespace CTList { /// The front of compile-time lists struct Nil {}; } /// Compile-time list helper template< typename ListId, typename Item > Item NextInListHelper( ::Wrapper<ListId>, ::Wrapper<Item> ); /// The last element of the list #define Back(ListId) \ decltype( NextInListHelper( ::Wrapper<ListId>(), ::Wrapper<\ decltype( NextInListHelper( ::Wrapper<ListId>(), ::Wrapper<\ decltype( NextInListHelper( ::Wrapper<ListId>(), ::Wrapper<\ decltype( NextInListHelper( ::Wrapper<ListId>(), ::Wrapper<\ decltype( NextInListHelper( ::Wrapper<ListId>(), ::Wrapper<\ decltype( NextInListHelper( ::Wrapper<ListId>(), ::Wrapper<\ decltype( NextInListHelper( ::Wrapper<ListId>(), ::Wrapper<\ decltype( NextInListHelper( ::Wrapper<ListId>(), ::Wrapper<\ decltype( NextInListHelper( ::Wrapper<ListId>(), ::Wrapper<\ decltype( NextInListHelper( ::Wrapper<ListId>(), ::Wrapper<\ CTList::Nil \ >())) \ >())) \ >())) \ >())) \ >())) \ >())) \ >())) \ >())) \ >())) \ >())) /// Add a new element (type) to the list #define PushBack( ListId, item) \ item NextInListHelper( ::Wrapper< ListId >, ::Wrapper< Back(ListId) > ) /// The next element in the ('ListId') list after 'item' #define Next(ListId, item) decltype(NextInListHelper(::Wrapper<ListId>(), ::Wrapper<item>() )) 

It uses NextInListHelper function NextInListHelper and the Dependent (Name) Look-up argument to write the list. The last item in the list can be referenced using the Back macro.

The first element of the list can be accessed: Next(ListId, CTList::Nil) , the last element of the list can be recognized from the fact that it is like its next element ( LastItem == Next(ListId, LastItem) ).

I tested it only with gcc 4.6.3, but it should be fully compatible with C ++ 11.

A few words about the solution:

• in this form, it can process lists of types up to 10 elements, but this can be expanded by adding additional lines to the Back() macro
• a list can contain a type only once
• the optional ListId type used in NextInListHelper declarations allows you to allow types to be contained in multiple lists at once
• Wrapper used to avoid the actual implementation of list item types and to support incomplete types like ListId
• PushBack() "calls" must be in the ListId ( NS1 ) or Wrapper (global scope) namespace
• List processing can be placed in any namespace ( NS2 )