Introduction
A typelist is a compile-time collection of types. It is a powerful construct used in metaprogramming to generate code in compile-time. I learned about typelists from Andrei Alexandrescu's book, "Modern C++ Design" [1]. The book gives a definition of typelist, some tools to work with it, and examples of using the list.
With help of this book I was able to use typelists to register Creator functions in C++ Object Factory Pattern, to check the types of function parameters, and even to initialize a combobox in compile-time.
Inherently, the typelist is a template with variable number of template parameters (elements), no matter how you would define it. So when ISO introduced variadic templates in C++ 11, it was very tempting to try to overwrite typelist and related tools using these templates.
Then a gift from Microsoft arrived: Free Visual Studio 2015 Community Edition with the C++ 14 compiler. All needed elements have fallen in place, so I decided to try.
First of all, I have googled the term "typelist." I found the field rather overcrowded. A lot of authors have written about the lists and developed tools to work with them. Naturally, each author used his own name and definition for the typelist, as well as his own set of tools to work with the lists. Of course, all tools worked just fine, and there were plenty of bright and interesting things along the way.
It seemed that the only thing left to me was to gather it all together. I began to work, and it all turned out to be not so simple. Indeed, some tools needed only a name change. But I found no prototypes at all for other tools I needed, and some tools must be overwritten completely.
So here you are going to see the results.
Acknowledgements
You can see that, because of multitude of authors, the question of who said "Aha!" first is very prickly. For example, you introduced a new partial specialization for a borrowed template structure. Without this specialization the borrowed template does not work with your definition of typelist. How will you refer to this thing? What is borrowed and what is new?
Anyway, the inventory of the TypeList's Toolbox was very much influenced by sources I am listing below. If I saw some tool in a source, I was saying to myself, "I will include something similar into my toolbox." But my code was sometimes different. Of course, all tools borrowed from other authors are marked appropriately.
The list of sources I used:
[1]" Modern C++ Design" by Andrei Alexandrescu, Addison-Wesley. Chapter III is dedicated to TypeLists. It was written before C++ 11, but it helped me to set an inventory of a Typelist Toolbox.
[2] <a href="http://fbb-git.github.io/cppannotations/">"C++ Annotations v. 10.3.0</a>" by Frank B. Brokken, Center for Information Technology, University of Groningen, Aug. 16, 2015. It is the web page where you can select the version and download a C++ Annotations pdf file. In the chapter "Advanced Template Use" there are a subchapters "Template TypeList processing" and "Using a TypeList." Basically, the author overwrites Andrei Alexandrescu's tools using variadic templates. I used it for adding tools to the Typelist Toolbox inventory of templates. Also some templates in my Toolbox are borrowed from these chapters as prototypes.
[3] "Meta User Manual" and "Tiny Metaprogramming Library" by Eric Niebler. It is very good and comprehensive library that has typelists (named 'lists') in its data types. I borrowed the definition of the typelist from there. I also used this library as a source to add tools to the Toolbox inventory and as a prototypes for some templates in the Toolbox. I do not know why, but my VC++ compiler in Visual Studio 2015 Community refuses to accept most constructs in the library's LAZY namespace, but I was able to read the code.
[4] "Simple C++ 11 Metaprogramming" by Peter Dimov. I have borrowed templates to convert TypeList to std::tuple and std::tuple to TypeList.
[5] "Effective Modern C++" by Scott Meyers. The first four chapters of this book you can download as a pdf file for free (click for URL here.) These chapters include very helpful information about rules to deduce template parameters. I needed it for writing tool templates and examples of usage of tools.
[6] "Applying Ant Colony Optimization Algorithms to Solve the Traveling Salesman Problem" by geoyar, on CodeProject. It is my article, and I used excerpts from it to show how to use Typelist to register classes with object factory.
Background
Some knowledge of C++ 11 and C++ 14 templates and variadic templates would help. The C++ reference might be very useful. Also you will need C++ 14 compiler. I used Microsoft Visual Studio 2015 Community Visual C++. It is great and it is free.
Using the code
All code is in the header file TypeList.hpp. You have to include it in your project and in your source (.cpp) files. The header includes <type_traits> header from C++14.
All templates are in the namespace "typelist", so you have to include "using namespace typelist;", or to use fully qualified names of templates in your source files.
I named my typelist "tlist." In text below (but not in the code)I also use terms "typelist," "list," and "TypeList." All these terms mean the type "tlist."
First of all, you have to define your specialization of the typelist, like using MyList = tlist<char, int, MyClass>;.
After that you can do what you want and need to do with this list, using tools from the header file.
All the tools are metafunctions - template structures, partially specialized for typelists.
If the result of the operation on the typelist is a type (like a type of a list's element), you access the result by the tool's member 'type' like this:
using type_at_4 = tlist_type_at<4, MyList>::type;
If the result is an integer number (like an index of a type in the typelist), the member 'type' is std::integral constant template. Additional members 'value_type' and 'value' refer to value_type and value of the result and are copies of std::integral_constant template members. All value members are declared as static constexpr value_type value = type::value.
There is a table of all tools in the "TypeList.hpp":>
Table 1. TypeList Tools | Tool | Definitions | Members | Usage | Note |
TypeList Definition
[3] | template <typename... Ts> tlist | type,
size()
| using MyList =
tlist<char, char, int, long, long, int, float, double>;
constexpr auto szMyList = MyList::size();
| type is the TypeList itself
size() returns a number of elements in the list |
| Check whether the List is empty | template <class List> struct tlist_islistempty | type,
value_type
value
| constexpr auto bEmpty = tlist_islistempty<<MyList>::value; | type is std::true_type or std::false_type
value_type is bool
value is true if the list is empty
|
| Check whether the type is a TypeList | template <class List> struct is_list | type,
value_type
value | constexpr auto bIsList = is_list<<MyList>::value; | type is std::integral_constant<bool, value>,
value_type is bool
value is true if the type is TypeList
|
| Check whether a list is the list of lists | template <typename List>
is_listoflists | type,
value_type,
value | constexpr auto bLL =
is_listoflists<MyList>::value | type is std::integral_constant<bool, value>,
value_type is bool,
value is true or false. |
| Access the element by index [2] | template <size_t idx, class List>
struct tlist_type_at
| type
| using type_at_3 =
tlist_type_at<3, MyList>::type; | type is a type of the list's element at the index idx. If index is out of list's bounds, static_assert is raised.
|
| Search a TypeList for the first occurrence of a type T | template <typename T, class List>
struct tlist_index_of
| type,
value_type
value
| constexpr auto idx =
tlist_index_of<<double, MyList>::value; | type is std::integral_constant<int, value>
value_type is int
value is the index of the first occurrence of the type T in the TypeList or -1 if the type is not found
|
| Search a TypeList for the first occurrence of not a Type T | template <typename T, class List>
struct tlist_index_of_not | type,
value_type,
value | constexpr auto idx =
tlist_index_of_not<char, MyList>::value | type is std::integral_constant<int, value>
value_type is int
value is the index of the first occurrence of the type not equal to T in the TypeList or -1 if the TypeList does have only elements of type T or is empty. |
| Get the first element in the TypeList | template <class List>
struct tlist_front
| type
| using front_type = tlist_front<<MyList>::type; | Returns the first element of the List. Raises static_assert if the List is empty
|
| Get the last element in the TypeList | template <class List>
struct tlist_back | type
| using back_type = tlist_back<MyList>::type; | Returns the last element of the List. Raises static_assert if the List is empty
|
| Push an element to front | template <typename T, class List>
struct tlist_push_front | type | using NewList =
tlist_push_front<double, MyList>::type | type is the appended list |
| Push an element to back | template <typename T, class List>
struct tlist_push_back | type | using NewList =
tlist_push_back<long, MyList>::type | type is the appended list |
Remove an element of type T from a list
[2] | template <typename T, class List>
struct tlist_erase_type | type | using NewList =
tlist_erase_type<double, MyList>::type; | Erases first occurrence of the type T from the list. If the type is not in the list, returns the original list. |
Remove the element at the given index
[2] | template <size_t idx, class List>
struct tlist_erase_at | type | using NewList =
tlist_erase_at<3, MyList>::type; | Erases an element at the index idx;
If the index is out of List's bounds, static_assert is raised. |
| Remove the front element from a list | template <class List>
struct tlist_pop_front | type | using NewList = tlist_pop_front<MyList>::type; | type is a the TypeList without the front element (a result might be an empty list) or empty list if called on the empty list |
| Remove the last element from a list | template <class List>
struct tlist_pop_back | type | using NewList = tlist_pop_back<MyList>::type; | type is a the TypeList without the last element (a result might be an empty list) or empty list if called on the empty list |
Remove all elements
of a type T | template <typename T, class List>
struct tlist_erase_all
template <typename T, class List>
struct tlist_deeperase_all | type | using NewList =
tlist_erase_all<char, MyList>::type;
using NewList =
tlist_deeperase_all<char, MyList>::type | If MyList is a list of lists, the first template processes the list's elements as a whole types; the second version removes all types T from each list of a list of lists. |
| Remove all duplicates | template <class List>
struct tlist_erase_dupl
template <class List>
struct tlist_deeperase_dupl | type | using NewList =
tlist_erase_dupl<MyList>::type;
using NewList =
tlist_deeperase_dupl<MyList>::type | If MyList is a list of lists, the first template processes the list's elements as a whole types; the second version removes duplicates from inside the list of lists elements (lists) |
| Remove first k elements from the List | template <size_t k, class List>
struct tlist_erase_firsts | type | using NewList =
tlist_erase_firsts<4, MyList>::type; | Removes maximum k elements from the front of TypeList, Returns an empty list if k ≥ list size.
If k == 0 static_assert is raised |
| Remove last k elements from the List | template <size_t k, class List>
struct tlist_erase_lasts | type | using NewList<4, MyList>::type | Removes maximum k elements from the tail of TypeList, Returns an empty list if k ≥ list size.
If k == 0 static_assert is raised |
| Replace the first occurrence of the element T with the element R | template <typename R, typename T, class List> struct tlist_replace_first | type | using NewList =
tlist_replace_first<long long, float, MyList>::type; | Does nothing if the element T is not in the TypeList |
| Replace the element at index k with the element R | template <size_t k, typename R, class List>
struct tlist_replace_at | type | using NewList =
tlist_replace_at<4, double, MyList>::type; | If the index is out of bounds, static_assert is raised. |
| Replace all occurrences of the element T with the element R | template <typename R, typename T, class List> struct tlist_replace_all
template <typename R, typename T, class List struct tlist_deepreplace_all | type | using NewList =
tlist_replace_all<int, char, MyList>::type
using NewList =
tlist_deepreplace_all<MyList>::type | The first template replaces all occurrences of T
with R; it processes Ts as a whole types. The second template accepts both plain lists and lists of lists. It processes plain lists similar to the first template but if MyList is a list of lists, the second version replaces all elements T inside the list's elements (lists) |
Count all occurrences of the type T
in the TypeList | template <typename T, class List> struct tlist_count_type | type,
value_type
value | constexpr auto occurrence_float =
tlist_count_type<float, MyList>::value; | If the type T is not in the List, value = 0;
type = std::integral_constant<size_t, value>
value_type is size_t |
| Count all occurrences of type T in plain TypeList or inside each element of a list of lists | template <typename T, class List>
struct tlist_deepcount_type | type | using res_cnt =
tlist_deepcount_type<int, MyList>::type | The type is std::integer_constant<size_t, cnt> for a plain TypeList or std::integer_sequence<size_t, cnts...> for a list of lists |
| Get all indexes of a type T in the TypeList | template <typename T, class List> struct tlist_all_idx
template <typename T, class List> struct tlist_all_deepidx | type | using idx_seq = tlist_all_idx<double, MyList>::type;
using idx_seqs = tlist_all_deepidx< long, MyList>::type | The first template processes list's elements as a whole types, and type is std::integer_sequence<size_t, Is...>.
If there are no elements of type T, the sequence is empty.
The second template accepts plain lists and lists of lists. It processes each list of a list of lists as a separate list, and the resulting std::integer_sequences are packed in the TypeList.
For lists of mixed elements that include some lists and other types, the second tool returns the same result as the firs tool. |
| Test whether a list is the list of integer_sequnces | template <class List>
is_listofiseqs | type,
value_type,
value | constexpr auto bLSeq =
is_listofiseqs<MyList>::value | The type is std::integral_constant<bool, value>. |
| Reverse the order of elements in the TypeList | template <class List>
struct tlist_reverse | type | using NewList = tlist_reverse<MyList>::type; | |
| Convert a list of lists into plain TypeList | template <class List>
struct tlist_flatten_list | type | using lst_flattened =
tlist_flatten_list<MyListOfLists>::type | Raises static_assert if the argument is nor list of lists |
| Concatenate TypeLists | template <class... Lists>
struct tlist_concat_lists<Lists...> | type | using NewList =
tlist_concat_lists<List1, List2, List3>::type; | If not all Lists are of type tlist, static_assert is raised. |
Add to the front of a TypeList first k elements from the
front of a second
TypeList | template
<size_t k, class List1, class List2> struct tlist_move_firsts | type | using MyIncreasedList =
tlist_move_firsts<4, MyList1,
MyList2>>::type | A number of elements to transfer must be
> 0; static_assert will be raised other way |
| Split the TypeList at many pivots | template
<class List, size_t... Ls>
struct tlist_split | type | using NewList =
tlist_split<MyList, 2, 3, 1>::type; | Ls... are numbers of elements in new lists. They do not include the number of elements in the last list.
type is a list of resulting lists. In the example of the usage the result is the list of lists of sizes 2, 3, 1, and the rest of MyList elements;
static_assert is raised if sum of the sizes is ≥ the number of elements in the original list. It also is raised if the sequence of sizes includes zeros. |
| Get size of max TypeList's elements | template <class List>
struct tlist_max_type_size
| type,
value_type,
value | constexpr auto max_sz =
tlist_max_type_size<MyList>::value;
| The ftemplate analyzes list's elements as a whole types..
type is std::integral_constant<size_t, sizeof(max element)>, value_type = size_t.
If templates are called on an empty list, value = 0. |
| Get size of max elements in each list of a list of lists | template <class List>
struct tlist_max_type_deep_size | type | using iseq_max_sz = tlist_max_type_deep_size<MyListOfLists>::type; | If templates are called on an empty list, value = 0.
The tool applies the previous template to each list in the list of lists, and packs results into type = std::integer_sequence.
If the argument is not a list of list, but still tlist, the tool works as a previous template
and returns std::integral_constant<size_t, value>. |
| Get the first element of given size | template <size_t k, class List>
struct tlist_firsttype_of_size
template <size_t k, class List>
struct tlist_firsttypedeep_of_size | type | using type_sz_2 =
tlist_type_of_size<2, MyList>::type;
using types_sz_8 =
tlist_firsttypedeep_of_size<8, MyListOfLists>::type | The first template analyzes elements of a list as a whole types; it returns the first type of size k. If there is no such type, type = std::false_type.
The second template has a special treatment for a list of lists: it searches for first elopement of size k inside each list of list of lists, and type is tlist with the types found in each lists If some particular list of list of lists does not have elements of size k, std::false_type is inserted in result. |
| Get all elements of given size k | template <size_t k, class List>
struct tlist_all_types_of_size
template <size_t k, class List> struct tlist_all_typesdeep_of_size | type | using types_of_size_4 =
tlist_all_types_of_size<4, MyList>::type
using types_of_size_4 =
tlist_all_typesdeep_of_size<MyList>::type | The first template analyzes elements of a list as a whole types; it returns the list of types of size k. If there is no types of size k, the result is an empty list..
For the list of lists the second template applies the search to each list in the list of lists; the result is a list of lists of types found. All duplicates are removed from resi;ts. |
Get all types greater or equal to
size k | template
<bool bEqual, size_t k, class List> struct tlist_types_greater
template <bool bEqual, size_t k, class List>
struct tlist_typesdeep_greater | type | using all_types_greater_2 =
tlist_types_greater<true, 2,MyList>::type;
using all_types_greater_4 =
tlist_typesdeep_greater<false, 4, MyList>::type | type is a TypeList of elements of size > k
if bEqual == false or size ≥ k if bEqual == true.
For a list of lists the second template returns a list of lists where the elements of the result are lists of types greater than k in each of elements of original list of lists. All duplicates are erased from the results |
Get all types lesser of equal to
size k | template
<bool bEqual, size_t k, class List>
struct tlist_types>less
template <bool bEqual, size_t k, class List> struct tlist_typesdeep_less | type | using all_types_less_4 =
tlist_types_less<true, 4, MyList>::type
using all_types_less_5 = tlist_typesdeep_less<false, 5, MyList>::type | As in the previous template, but for types of sizes less or equal to k |
Convert TypeList to std::tuple and back
[4] | template <class Src, template<typename...> class Trg>
using convert = typename convert_impl<Src, Trg>::type | | using MyTuple =
convert<MyList, std::tuple;
using MyList =
convert<MyTuple, tlist>; | Borrowed from Peter Dimov [4] |
You have to remember that all these types, value_types, and values are compilation-time entities. You have to add some code to access them in run time, if you want make them visible.
Also keep in mind that if the tool returns a type, a value_type and a value, and you need, for example, both type, and value, it might be wiser first to get the type, that is std::integral_constant, and use its members 'value_type' and 'value' instead of tool's members to avoid extra recursions using the tool again to get value.
The code uses static_assert to prevent use of invalid parameters.
A tool might return an empty TypeList, or empty std::integer_sequence as legitimate results. For example, if you call tlist_all_idx <float, MyList>::type on plain TypeList without such elements, you will get empty std::integer_sequence<size_t> as a result. TypeList can have empty std::integer_sequence as a legitimate element too. So it is up to you to decide how to distinguish them.
And the last thing: tlist_all_idx<element_type, TypeList>::type returns std::integer_sequence of related indexes. tlist_all_idxdeep returns TypeList of std::integer_sequences. Be careful and check the result type if you are not sure what argument was passed.
You will find some tools to work with std::integer_sequence in the file TypeList.hpp.
The example of usage of TypeList Toolbox members is there:
#include "type_traits"
#include "TypeList.hpp"
using namespace std;
using namespace typelist;
int main()
{
using MyTypeList = tlist<char, char, int, long, float, double>; constexpr auto sz = MyTypeList::size();
using type_at_2 = tlist_type_at<2, MyTypeList>::type; constexpr auto bSame = is_same<type_at_2, long >::value;
using type_at_12 = tlist_type_at<12, MyTypeList>::type; return 0;
}
You find more examples in the file "TypeList.cpp."
Points of Interest
To work with the TypeList Toolbox you need the C++ 14 compatible compiler. I have used the following C++14 features:
- typename for parameter pack instead of class in C++ 11
- Extended constexpr keyword
- std::integer_sequence
I used VC++ from Microsoft Visual Studio 2015 Community Edition Update 1. It is free and it is very good
TypeList Definition: Head and Tail or just Parameter Pack?
Andrei Alexandrescu in [1] gave us the following definition of TypeList:
template <class T, class U>
struct TypeList
{
typedef T Head;
typedef U Tail;
};
Of course, it is easy to rewrite it in C++ 14 terms:
template <typename T, typename... Ts>
struct TypeList
{
using Head = T;
using Tail = TypeList<Ts...>;
};
But there is a problem: the TypeList defined in this way cannot be truly empty, it has to include type T at least. If you would try to instantiate TypeList<>, the compiler will complain "there is not enough template parameters."
Andrei has introduced a special type NullType that is always present at the end of the TypeList. It means that the empty list will always have one element. Variadic templates allow us to have truly empty lists because the empty parameter packs are OK. I would like to use a definition of the List without Heads and Tails:
template <typename... Ts>
struct tlist{};
Still there is a minor problem: with this definition you have to have an additional meta function to get a number of elements in the list. If you name this function tlist_size you have to call tlist_sise<MyList>::value to get the number. This is different from a C++ use of function size() to get a number of elements in a STL containers. So I decided to go with STL and borrowed the definition of TypeList from [3]:
template <typename... Ts>
struct tlist
{
using type = tlist;
static constexpr size_t size() noexcept {return sizeof...(Ts);}
};
The member "type" is a sort of syntactic sugar: sometimes it is more convenient to use MyList::type than just MyList.
Please note that now the empty list is a legitimate member of the family, because the parameter pack with zero parameters is allowed.
Keep in mind that the number of elements in the list is sizeof...(Ts), not sizeof(MyList). On my PC sizeof(MyList) = 1 for any tlist.
We still need NullType but not as a mandatory element of TypeList.
General Design Considerations
All tools in TypeList Toolbox are implemented as metafunctions (structure templates.) To get some results we have to iterate over TypeList's elements or element indexes. In metaprogramming (in compile-time) iteration is recursion. Recursion has to stop somewhere. So, for each tool we have to have template definition or declaration and a specializations for recursion and stop conditions.
First, we have to choose between forward declaration of the tool, like template <size_t k, class List> struct tlist_index_of; or definition of an empty class like template <size_t k, class List> struct tlist_type_at {}. We also can use variadic templates from the beginning or declare or define some general template and after that use partial specializations for parameter packs. I find more convenient to declare or define a general template and after that use partial specialized templates for TypeLists.
Because tools in the header, TypeList.hpp are always using template specializations to work with TypeLists, the compiler is trying to instantiate tool's general definition only if the tool is called on a wrong class. We will get error messages, but the messages are different whether we are using declaration or definition.
For example, if we have a class TC that is not a TypeList, and call tlist_type_at<4, TC>::type, the compiler cannot find the specialization for TC and will try to instantiate the general template. It falls, and we will get an error message. For declaration the error message is: "use of undefined type , typelist::tlist_type_at<4,TC>'', and for definition of the empty class it is: "type': is not a member of 'typelist::tlist_type_at<4,TC>."
I like the first message more, so in TypeList.hpp I am mostly using forward declaration of templates before specializations. There are some exceptions. I will discuss then later.
Of course after the first error message you might get more of them, but the very first messages are as described.
Members of the tool structure templates
The next problem is what members we have to provide to access results of applying the tools.
The results are either types as in tlist_type_at or numbers, as in tlist_index_of. With the types all is clear: the type is a type, so the member of the structure template is "type." But how to define a type and a value of a number that is returned by the tool like tlist_index_of. The value must be a compile-time constant. There are two ways to define these constants: static member of the structure/class or enumeration value. Because enum is its own types there might be a problem when you need a type of the returned number. So I chose static member like this:
template <typename... Ts>
struct tlist_index_of<tlist<Ts...>
{
.........................................................
using type = std::integral_constant<size_t, idx>;
using value_type = typename type::value_type;
static constexpr value_type value = type::value;
};
As you see, I am using functionality provided by C++ standard.
If the result of an operation on a TypeList is a type, the tool's member is just that: ' type':
template <size_t k, typename... Ts>
struct tlist_type_at<tlist<Ts...>>
{
. .........................................
using type = .......;
};
Initial Conditions
Sometimes you have to set initial condition for recursion. For example, tlist_type_at might start from the index zero, tlist_split needs an empty list to begin to pack spitted lists. To make developers' life easy, I wrote the implementations of such tools first and wrappers that include these implementations and provide initial types or values and are using these implementation like :
template <size_t idx, typename T class List> struct tlist_index_of_impl ;
......................................
template <typename T, class List>
struct tlist_index_of;
template <typename T, typename H, typename... Ts> struct tlist_index_of<T, tlist<H, Ts...>>
{
using type = typename tlist_index_of_impl<0, T, tlist<H, Ts...>>::type; using value_type = typename type::value_type;
enum {value = value};
};
I am not hiding implementations in a nested namespace (e.g. 'details') or inside wrappers for sake of simplicity.
What if... : Abnormal Situations, static_assert,, the empty list, and empty std::integer_sequence
There never is a guarantee that template arguments you are supplying to a tool are of correct types or values. We have discussed what happen if you call a tool on a class that is not a typelist, but you also could look for an element that does not exist in your TypeList. Or index for the search the list is way beyond the number of elements in the list. Things happen.
Of course, these are mistakes. Sometimes you ask a compiler to do something it just cannot do. For example, you request a compiler to split TypeList with 6 elements into two TypeLists: one with 12 elements and a second with remnants. The compiler has no clue what you really want, and does not know what to do. On this occasion it is appropriate to raise static_assert as I do:
template <size_t k, typename... Ts >
struct tlist_split<k, tlist<Ts...>>
{
std::static_assert(k < sizeof... (Ts), "Pivot point is not inside an original list");
std::static_assert(k != 0, "Nothing to split: the pivot point is at zero");
.....................................................................................
};
A different kind of mistake is when an operation proceeds, but does not deliver an expected result. Let's assume we are trying to get a type at some index and that index is outside of TypeList' s bounds. What to do? We can proceed beginning from index zero, and recurs up to the end of the list. After that we can stop recursion and return some special type like NullType. The result is ambiguous, because NullType is a type and also might be an element of this or other typelists. The other option is to raise static_assert, but it will stop compilation altogether. I decided to follow an example of C++ where reading beyond container's bounds raises run-time assert and choose the second option.
Sometimes all is running just fine but results are not what was expected. For example, you are searching for types of size 4 bytes in your list that has only char's and doubles. No such types are found. The tool returns the empty TypeList. The empty TypeLists, std::integer_sequences, and indexes -1 are legitimate negative results in this Tool Box.
Now let us discuss some particular tools and topics.
What is a size of NullType?
Sometimes you need a special type of size zero, for example, to start recursion with an element of size zero. But any type you define takes some memory. There are no types of size zero in C++.
NullType is a special and is declared as an empty class. On my PC sizeof(NullType) = 1, as is sizeof(tlist<typename... Ts>). So we need some way around. I had to introduce template:
class NullType
{};
template <typename T>
struct Sizeof
{
static constexpr size_t value = std::is_same<T, NullType>::value ? 0 : sizeof(T);
};
Is a type T a TypeList?
To check whether some compile-time type is a TypeList I wrote a variant of well-known template (e.g. see [1], 2.7):
template <typename T>
struct type_to_type
{
using origin = T;
type_to_type() {}
};
template <typename T>
struct is_tlist
{
private:
typedef char (&yes)[1];
typedef char (¬)[2];
template <typename... Ts>
static yes Test(type_to_type<tlist<Ts...>>) {}
static no Test(...) {}
public:
using type = std::integral_constant<bool, sizeof(Test(type_to_type<T>())) == 1>;
using value_type = typename type::value_type;
static constexpr value_type value = type::value;
};
Similar template is to test whether a type is a std::integer_sequence.
Split TypeList into Multiple TypeLists
This tool splits a TypeList into multiple lists. You supply number of elements in spitted lists as a parameter pack of size_t numbers. The pack does not include number of elements in the last list of the result: last list includes remainder of the original list's elements. So the number of elements (lists) in the resulting list of lists is the size of parameter pack plus one. You receive a list of lists as a result (type).
Obviously, the sum of numbers in the parameter pack must be less than the number of elements in the original list because we have to left some non-zero remainder for the last spitted element. Also, the parameter pack cannot include zeros, because zero means an empty list. In context of the list splitting the list with zero length means no splitting at this point, because the pivot point does not change after zero elements would remove from the original list.
If these conditions are not satisfied, we cannot perform the splitting. The tool must raise static_assert.
To work with template arguments, we have to somehow organize them. We do this by inserting arguments in std::integer_sequence<size_t, lengths...>. We provide metafunctions iseq_sum<class ISeq> and iseq_index_of<typename T, T nmb, class ISeq> to check template arguments.
Below is the code.
First, we need a helper that moves first l elements from one list to the end of the second list in the list of two lists:
template <size_t l, class List1, class List2>
struct tlist_move_firsts;
template <typename H, typename... T1s, typename... T2s> struct tlist_move_firsts<1, tlist<T1s...>, tlist<H, T2s...>>
{
using type = tlist<tlist<T1s..., H>, tlist<T2s...>>;
};
template <size_t l, typename H, typename... T1s, typename... T2s> struct tlist_move_firsts<l, tlist<T1s...>, tlist<H, T2s...>>
{
static_assert(l > 0, "Number of elements to transfer must be > 0"); using type = typename tlist_move_firsts<l - 1, tlist<T1s..., H>, tlist<T2s...>>::type;
};
Next, we have to use this helper. The idea is to take an empty list, move the first k elements, as requested by an appropriate template argument, from the original list into the empty list, add the new list to resulting list of list, and repeat this operation with remainders of the original list:
struct tlist_split_impl;
template <size_t l, typename... Lists, typename... Tails> struct tlist_split_impl <std::integer_sequence<size_t, l>, tlist<Lists...>, tlist<Tails...>> {
private:
using lst_split_2 = typename tlist_move_firsts<l, tlist<>, tlist<Tails...>>::type; using first = typename tlist_type_at<0, list_split_2>::type; using second = typename tlist_type_at<1, lst_split_2>::type;
public:
using type = tlist<Lists..., first, second>; };
template <size_t l, size_t... Ls, typename... Lists, typename... Tails> struct tlist_split_impl<std::integer_sequence<size_t, l, Ls...>, tlist<Lists...>, tlist<Tails...>>
{
private:
using lst_split_2 = typename tlist_move_firsts<l, tlist<>, tlist<Tails...>>::type;
using first = typename tlist_type_at<0, lst_split_2>::type; using second = typename tlist_type_at<1, lst_split_2>::type;
using lst_res = tlist<Lists..., first>;
public:
using type = typename tlist_split_impl<std::integer_sequence<size_t, Ls...>, lst_res, second>::type;
};
Here we made a temporary list of two lists with the empty list and remainder of the original list (at first step the remainder is the original list itself.) We transferred first l elements from the remainder of the original list into the empty list. After that we added the first list from the temporary list of two lists to the would be resulting list of lists, and passed the temporary result and new remainder to next step in recursion. To get needed components we used tlist_type_at.
Now it is a time to wrap it all together with initial conditions (empty lists) and argument tests. Please note that you do not have to bother yourself with building std::integer_sequence. You have to provide only set of lengths, the tool will take care about all other things:
template <class List, size_t... Ls> struct tlist_split;
template <typename... Ts, size_t... Ls>
struct tlist_split<tlist<Ts...>, Ls...>
{
using lengths = std::integer_sequence<size_t, Ls...>; using lengths_sum = typename iseq_sum<lengths>::type; static_assert<lengths_sum::value < tlist<Ts...>::size(), "Split: Check sum of component lengths"); ;
static_assert(iseq_index_of<size_t, 0, lengths>::value == -1, "Split: No zero lengths allowed");
using type = typename tlist_split_impl<std::integer_sequence<size_t, Ls...>, tlist<>, tlist<Ts...>>::type;
};
There is an example of applying tlist_split :
using lst_msplit = tlist_split<tlist<char, char, int, long, int, float, float, int, double>, 2,2,3>::type;
constexpr auto bLL =
std::is_same<lst_msplit, tlist<tlist<char, char>, tlist<int, long>, tlist<int, float, float>, tlist<int, double>::value;
Please note that we have introduced a special kind of TypeList, list of lists: all elements of it are lists. Sometimes we will want to do some special processing for this type of lists. I am going to discuss it momentarily.
Erasing elements from TypeList
I am going to discuss some subtleties of working with lists of lists using an example of tool for removing duplicates from TypeList.
In the Toolbox there are several tools to remove elements from TypeLists. The first four are borrowed from [2]: tlist_erase_type, tlist_erase_at, tlist_erase_all, tlist_erase_dupl. The additional four are tlist_pop_front, tlist_pop_back, tlist_erase_firsts, and tlist_erase_lasts.
tlist_pop_front and tlist_pop_back just call tlist_erase_at on index of first(0) or index of last element in the list. tlist_erase_firsts and tlist_erase_lasts are deleting no more than k elements from the front or the tail of the list. They are recursively using tlist_pop_front or tlist_pop_back.
If an index supplied to tlist_erase_at is out of list's bounds, static_assert is raised. Templates that are using tlist_erase_at also might raise it. For example, tlist_pop_front called on an empty list will assert because there is no element at index zero (no element at all.)
These tools are doing just that: Remove an element or elements from the list. But this functionality is not always enough if we have lists of lists.
Let us look at the result of splitting of the list in previous chapter. There are four TypeLists, two of them have duplicate elements inside, char in the first and float in the third. If you want to erase all duplicates in each elements (TypeList) of this list of lists and would call tlist_erase_dupl, the tool will consider elements (lists) of the result as whole entities. It will never go inside these lists. It might be not what you wanted. Of course, you can access each element individually by using tlist_type_at and call tlist_erase_dupl on each list individually. It is rather cumbersome. So I decided to automate this process and similar cases, and to have some universal solution that automatically selects right tool for plain TypeLists or for a lists of lists. For the list of lists it will always look inside the elements of it. On other occasions we will still need to process elements of list of list as whole types. For example, to remove duplicates of lists in the list of lists.
There is a code.
First, we need a tool to remove duplicates from a plain TypeList (borrowed from [2]):
template <class List> struct tlist_erase_dupl;
template <> struct tlist_erase_dupl<tlist<>>
{
using type = tlist<>;
};
template <typename H, typename... Ts>
struct tlist_erase_dupl<tlist<H, Ts...>>
{
private:
using unique_t = typename tlist_erase_dupl<tlist<Ts...>>::type;
using new_t = typename tlist_erase_type<H, unique_t>::type;
public:
using type = typename tlist_push_front<H, new_t>::type;
};
For a list of lists, we will apply this tool to work inside elements of list of lists (if we want to):
template <class List>
struct tlist_erase_dupl_ll
{
using type = tlist<>;
};
template <typename... Hs, typename... ListEls>
struct tlist_erase_dupl_ll<tlist<tlist<Hs...>, ListEls...>>
{
private:
using lst_clean = typename tlist_erase_dupl<tlist<tlist<Hs...>>>::type public:
using type = typename tlist_push_front<lst_clean, typename tlist_erase_dupl_ll<tlist<ListEls...>>::type>::type;
};
It just applies tlist_erase_dupl to each element of a list of lists and pushes the cleaned lists into resulting list of lists.
Now let us assemble a final template:
template <class List>
struct tlist_deeperase_dupl;
template <typename... ListEls>
struct tlist_deeperase_dupl<tlist<ListEls...>>
{
private:
static constexpr bool bLL = is_listoflists<tlist<ListEls...>>::value; public:
using type = typename conditional<bLL, typename tlist_erase_dupl_ll<tlist<ListEls...>>::type, typename tlist_erase_dupl<tlist<ListEls...>>::type>::type; };
The tool automatically selects the right implementation for a plain list and a list of lists. It returns list withot duplicates for a plain TypeList, or a list of lists without duplicates in each elements of it.
There is one problem: std::conditional inside the partial specialization. It was defined in <type_traits> as template <bool B, class T, class F>. The template needs one non-type (bool) and two type arguments to be instantiated. When you call tlist_deeperase_dupl on list of lists, all is working just fine. But for a plain list the compiler cannot find appropriate partial specialization for tlist_erase_dupl_ll for the plain TypeList. So to accommodate the plain list I had to use a definition for general template, not a declaration as elsewhere. It is never executed, because for std::conditional::type, the switch in tlist_deeperase_dupl, always selects the right partial specialization.
And what about processing elements of lists of lists as whole types, not going inside? Well, you have to use the first template explicitly. Call tlist_erase_dupl, not tlist_deeperase_dupl.
You find other 'deep' tools in Table 1 above and in TypeList.hpp.
Replace elements of TypeList
The idea is simple: you iterate over the list and examine the first elements at the inspection points. It the element is of type to be replaced, you replace it, and move to the next point. Below I show how it looks for tlist_replace_all :
template <typename R, typename T, class List> struct tlist_replace_all;;
template <typename T, typename T> struct tlist_replace_all<R, T, tlist<>>
{
using type = tlist<>;
};
template <typename R, typename T, typename... Ts> struct tlist_replace_all<R, T, tlist<T, Ts...>>
{
using type = typename tlist_push_front<R, typename tlist_replace_all<R, T, tlist<Ts...>>::type>::type;
};
template <typename R, typename T, typename H, typename... Ts> struct tlist_replace_all<R, T, tlist<H, Ts...>>
{
using type = typename tlist_push_front<H, typename tlist_replace_all<R, T, tlist<Ts...>>::type>::type;
};
How does the instantiation proceed? Let's assume we have tlist<char, int, long> and we want to replace int with double . As a first step, we apply tlist_replace_all to the entire list. The front of the list is type char. It is not int, so we have to return it to the list. At this step we do not have the list to push this element to front of it. To get it we apply the same template to the reminder of the list, tlist<int,long> again. This time we have found the type to replace, so we have added double to waiting char to be pushed front. Because we still do not have a list to push waiting elements, we apply tlist_replace_all to tlist<long> again.
This time, long is added to types waiting to be pushed front. Now we have a TypeList to operate on: it is an empty list. The specialization for the empty list is instantiated, and it returns the type: the empty list. Now we have a list to push waiting elements into it. The last element waiting to be pushed front is pushed into this empty list. After that the previous element is pushed into resulting list with one element, (long) and so on. In the end, we find ourselves with tlist<char. double, long> .
The process is the same if there are no elements of the type we want to replace in the list. We just get an original list.
If we want to replace all elements of some type inside the elements of a list of lists, we need additional template similar to tlist_deeperase_dupl:
template <typename R, typename T, class List>
struct tliat_replace_all_ll
{
using type = tlist<>; };
template <typename R, typename T, typename... Hs, typename... ListEls>
struct tlist_replace_all_ll<R, T, tlist<tlist<Hs...>, ListEls...>>
{
private:
using lst_replaced = typename tlist_replace_all<R, T, tlist<Hs...>>::type;
public:
using type = typename tlist_push_front<lst_replaced, typename tlist_replace_all_ll<R, T, tlist<ListEls...>>::type>::type;
};
template <typename R, typename T, class List>
struct tlist_deepreplace_all;
template <typename R, typename T, typename... ListEls>
struct tlist_deepreplace_all<R, T, tlist<ListEls...>>
{
private:
static constexpr bool bLL = is_listoflists<tlist<ListEls...>>:value;
public;
using type = std::conditional<bLL, typename tlist_replace_all_ll<R, T, tlist<ListEls...>>::type,
typename tlist_replace_all<R, T, tlist<ListEls...>>::type>::type;
};
There are also tools to replace the first occurrence of a type in a list, and to replace the type at given index. The last tool raises static_assert if it receives an index out of list's bounds, because, obviously, it is an error.
Get all indexes of a type in TypeList
Again, the idea is simple: you iterate over the TypeList and check the types of elements you meet. If the type of this element is of type you are looking for, you add the element's index to a container you are using as index storage.
But what this container might be? It seems that the only candidate C++ 14 gives to us is std::integer_sequence. So, let us to start with empty sequence and add to it the index of element of type we are looking for each time we meet this element in the list. The code is:
template <size_t k, typename T, class List, class IntSeq> struct tlist_all_idx_impl;
template <size_t k, typename T, size_t... Idx> struct tlist_all_idx_impl<k, T, tlist<>, std::integer_sequence<size_t, Ids...>>
{
using type = std::integer_sequence<size_t, Idx...>;
};
template <size_t k, typename T, typename... Ts, size_t... Idx> struct tlist_all_idx_impl<k, T, tlist<T, Ts...>, std::integer_sequence<size_t, Idx...>>
{
using type = typename tlist_all_idx_impl<k + 1, T, tlist<Ts...>, std::integer_sequence<size_t, Idx..., k>>::type;
};
template <size_t k, typename T, typename H, typename... Ts, size_t Idx> struct tlist_all_idx_implt<k, T, tlist<H, Ts...>, std::integer_sequence<size_t, Idx...>>
{
using type = typename tlist_all_idx_impl<k + 1, T, tlist<Ts...>, std::integer_sequence<size_t, Idx...>>::type;
};
template <typename T, class List> struct tlist_all_idx;
template <typename T, typename H, typename... Ts> struct tlist_all_idx<T, tlist<H, Ts...>>
{
using type = typename tlist_all_idx_impl<0, T, tlist<H, Ts...>, std::integer_sequence<size_t>>::type;
};
This tool considers TypeList as a list of whole elements. But what about lists of lists? Again, if we want to get indexes of some type of element inside each list of the list of lists we have to apply apply tlist_all_idx to each element of the list of lists, and pack results in TypeList of integer_sequences :
template <typename T, class Res, class List>
struct tlist_all_idx_ll
{
using type = tlist<std::integer_sequence<size_t>>;};
template <typename T, typename.. Rs, typename...Hs>
struct tlist_all_idx_ll<T, tlist<Rs...>, tlist<tlist<Hs...>>>
{
private:
using iseq = typename tlist_all_idx_impl<0, T, tlist<Hs...>, std::integer_sequence<size_t>>::type;
public:
using type = tlist<Rs..., iseq>;
};
template <typename T, typename... Rs, typename... Hs, typename... ListEls>
struct tlist_all_idx_ll<T, tlist<Rs...>, tlist<tlist<Hs...>, ListEls...>>
{
private:
using iseq = typename tlist_all_idx_impl<0, T, tlist<Rs...>, tlist<Hs....>>::type;
public:
using type = typename tlist_all_idx_ll<T, tlist<Res..., iseq>, tlist<ListEls...>>::type;
};
template <typename T, class List>
struct tlist_all_deepidx;
template <typename T, typename... ListEls>
struct tlist_all_deepidx<T, tlist<ListEls...>>
{
private:
static constexpr bool bLL = is_listoflists<tlist<ListEls...>>::value;
public:
using type = typename conditional<bLL,
typename tlist_all_idx_ll<T, tlist<>, tlist<ListEls...>>::type,
typename tlist_all_idx_impl<0, T, tlist<ListEls...>, std::integer_sequence<size_t>>::type>::type;
};
Again, if you want to treat the list of list as a plain TypeList use tlist_all_idx.
Please pay attention that types the universal (deep) tool returns are different for a plain list and a list of lists. For the plain list it is std::integer_sequence, for the list of list it is tlist<std::integer_sequence...>.
So far, so good. You got your indexes, but how to work with them? I provided a set of tools to work with integer_sequence, all in the header TypeList.hpp:
template <typename T> struct is_iseqtemplate <size_t k, class IntSeq> struct iseq_nmb_attemplate <typename T, T n, class IntSeq> struct iseq_index_oftemplate <class IntSeq> struct iseq_sum (Sum of all elements of the sequence)template <typename T, T nmb, class IntSeq> struct iseq_remove_nmbtemplate <typename T, T nmb, class IntSeq> struct iseq_push_back
Tools for std::integer_sequence
If a tool for std::integer_sequence needs some number as a template argument and this number is not an index, that number must be of the type of the sequence's value type. We might supply a wrong type. I solve this problem by using implementations to do all work, and the lot of static_assert in wrappers to check for erroneous types. Below is an example:
template <size_t idx, typename U, U n, class ISeq> struct iseq_index_of_impl;
template <size_t idx, typename U, U n>
struct iseq_index_of_impl<idx, U, n, std::integer_sequence<U>> {
using type = std::integral_constant<int, -1>;
};
template <size_t idx, typename U, U n, U... Nmbs>> struct iseq_index_of_impl<idx, U, n, std::integer_sequence<U, n, Nmbs...>>
{
using type = std::integral_constant<size_t, n>;
};
template <size_t idx, typename U, U n, U l, U... Nmbs>
struct iseq_index_of_impl<idx, U, n, std::integer_sequence<U, l, Nmbs...>>
{
using type = typename iseq_index_of_impl<idx + 1, U, n, std::integer_sequence<U, Nmbs...>>::type;
};
template <<typename U, U n, class ISeq>
struct iseq_index_of
{
private:
static_assert(is_iseq<ISeq>::value, "Supplied class is not integer_sequence"); using data_type = typename ISeq::value_type;
static_assert(std::is_same<data_type. U>::value, "The number must be of the sequence value_type"); public:
using type = typename iseq_index_of_impl<idx, data_type, n, ISeq>::type;
using value_type = typename type::value_type;
static constexpr value_type value = type::value;
};
using MyISeq = std::integer_sequence<int, 0, -3, 6, 89>; constexpr auto idx_6 = iseq_index_of<MyISeq::value_type, 6, MyISeq>::value;
Of course you could just use the specialization of iseq_index_of_impl. The difference will be in error messages. If you would supply wrong type for the number, for example, long for the sequence of int's the first error message for implementation is "use of undefined type." Assertion in the iseq_index_of will output as a first error message text you have provided.
Convert TypeList to std::tuple
TypeList has no value members inside. You can instantiate it, but there is nothing you can do with it at run time (besides getting its size). Sometimes after working on the list in compile-tine you might want to use its elements (types) in some other classes in run time, e.g. transform it into std::tuple. There is a template from [4]:
template <class Src, template <typename...> class Trg>
struct convert_impl;
template <template<typename...> class Src, typename... Ts, template <typename... > class Trg
struct convert_impl<Src<Ts...>, Trg>
{
using type = Trg<Ts...>;
};
template <class Src, template <typename...> class Trg>
using convert = typename convert_impl<Src, Trg>::type;
using MyList = tlist<char, int, long, float, double, void*>;
using MyTuple = convert<MyList, std::tuple>;
constexpr auto szMyTuple = tuple_size<MyTuple>::value; constexpr auto bLT = is_same<MyTuple, std::tuple<char, int, long, float, double, void*>>::value; MyTuple myTuple;
using RecList = convert<MyTuple, tlist>;
constexpr auto szList = RecList::size(); constexpr auto bTL = is_same<RecList, tlist<char, int, long, float, double, void*>>::value;
Examples of utilizing TypeLists
You find examples of creating class hierarchies from TypeLists in [ 2]. It follows Andrei Alexandrescu path [1].
I will add example of registering classes from TypeList with object factory. The classes are Ant Colony algorithms [6]: CASTravel, CASETravel, CRASTravel, CBWASTravel, CMMASTravel, CACSTravel. Every class has a static member function Register.
First, we define the TypeList:
using AlgTypeList = tlist<CACSTravel, CASETravel, CRASTravel, CBWASTravel, CMMASTravel, CACSTravel>:
We define a template to register classes from TypeList:
template <size_t idx, class List>
struct RegFactoryClasses;
template <typename H, typename... Ts>
struct RegFactoryClasses<0, tlist<H, Ts...>>
{
using Result = H;
static inline void Fn(void)
{
Result::RegisterWithFactory();
}
};
template <size_t k, typename H, typename... Ts>
struct RegFactoryClasses<k, tlist<H, Ts...>>
{
using Result = typename RegFactoryClasses<k-1, tlist<Ts...>>::Result;
static inline void Fn(void)
{
Result::RegisterWithFactory();
RegFactoryClasses<idx - 1, tlist<H, Ts...>>::Fn();
}
};
Now we define:
using RegAlgoritms = RegFactoryClasses<AlgTypeList::size() - 1, AlgTypeList>;
And at run time:
RegAlgoritms::Fn();
What is in the package
As I already noted before, all tool templates are in file TypeList.hpp. The file also contains templates to work with std::integer_sequences. They are used in some TypeList tools. It included in typeListSource.zip.
To play with tools I have provided a file TypeList.cpp. Basically, it defines several TypeLists, applies some tools to them, and checks the results with std::is_same from <type_traits>.
If you build and run this cpp file you will see nothing. All processing is executed in compile-time. Checks also are performed in compile-time. So what use has that cpp file?
I have included a VS 2015 Community Update 1 solution, project files and source files in TypeListProject.zip. You can easily open the solution in VS 2015, build compile the debug configuration of TypeList.exe. You will able to play with tools by setting breakpoints and watching compile-time constants in Watch windows of Visual Studio in debug mode.
I have also included in TypeListProject.zip a doxygen project file, Doxyfile, to make a documentation (Folder Doc). If you want to generate html documentation, download Doxygen from its web site (it is free), start doxywizard.exe, load this file in wizard and after correcting directories of the TypeList.hpp to directories on your PC, run the wizard.
