In this post I’m gonna implement a simple type list along with a set of
basic operations that can be performed on it.
Tuples?
Isn’t it just a tuple? Not really, it’s something simpler than that. Tuple is
a set of values of arbitrary types. Tuples are immutable as well (there’s
std::tuple_cat
with which operations like append and prepend could be implemented
but this will result with a new instance of tuple with extended set of
contents).
In case of typelist, well, it’s just a list of types, without any instances of
these types and without any associated values.
What’s the practical aspect of such list? I don’t really want to spoil the
next post on that topic, but being able to index the type in a list, it’s
possible to implement mappings between indices (or enums) and types.
List type
I’m gonna define a list as a variadic template:
1
2
|
template <typename ... Types>
struct TypeList{};
|
Having this, it’s possible to declare lists.
1
2
3
4
5
6
|
using Integrals = TypeList<uint8_t, uint16_t, uint32_t>;
using RandomTypes = TypeList<int, float, std::string>;
...
|
Basic operations
Head, Tail, Size and Last are probably the most basic operations you
can imagine that can be performed on a list. The first two (Head & Tail)
retrieve the first type in the list and the remainder of the list respectively.
Size will obviously return number of types within the list and Last returns
the last type within the list.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
|
template <typename List>
struct Size;
template <typename ... T>
struct Size<TypeList<T...>> {
static constexpr std::size_t value = sizeof...(T);
};
// ===
template <typename List>
struct Head;
template <typename H, typename ... T>
struct Head<TypeList<H, T...>> {
using type = H;
};
// ===
template <typename List>
struct Tail;
template <typename H, typename ... T>
struct Tail<TypeList<H, T...>> {
using type = TypeList<T...>;
};
// ===
template <typename List>
struct Last;
template <typename T>
struct Last<TypeList<T>> {
using type = T;
};
template <typename H, typename ... T>
struct Last<TypeList<H, T...>> {
using type = typename Last<typename Tail<TypeList<H, T...>>::type>::type;
};
// ===
using List1 = TypeList<int>;
using List2 = TypeList<float, short>;
using List3 = TypeList<int, float, std::string>;
static_assert(std::is_same_v<Head<List1>::type, int>, "");
static_assert(std::is_same_v<Head<List2>::type, float>, "");
static_assert(std::is_same_v<Head<List3>::type, int>, "");
static_assert(Size<List1>::value == 1, "");
static_assert(Size<List2>::value == 2, "");
static_assert(Size<List3>::value == 3, "");
static_assert(std::is_same_v<Last<List1>::type, int>, "");
static_assert(std::is_same_v<Last<List2>::type, short>, "");
static_assert(std::is_same_v<Last<List3>::type, std::string>, "");
|
The only thing worth explaining here is the Last implementation which employs
some recursion. The most basic recursive case is a single element list. Last
element in such list is just the first (or the only) element. The recursion
reduces the list by removing first element in each step until the list is
comprised of a single element only.
List access operations
On top of the basic set of operations, some more convenient ways to access list
contents will be necessary as well. That would be Subscript and Index.
Subscript will return the type at given index and Index will return the
index of the first occurrence of given type within the list.
Subscript
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
|
template <typename List, std::size_t S>
struct Subscript;
template <typename T, typename ... Types>
struct Subscript<TypeList<T, Types...>, 0> {
using type = T;
};
template <typename T, typename ... Types, std::size_t S>
struct Subscript<TypeList<T, Types...>, S> {
using type = typename Subscript<TypeList<Types...>, S - 1>::type;
};
static_assert(std::is_same_v<Subscript<List3, 0>::type, int>, "");
static_assert(std::is_same_v<Subscript<List3, 1>::type, float>, "");
static_assert(std::is_same_v<Subscript<List3, 2>::type, std::string>, "");
|
Again, recursion to the rescue. Zeroth subscript refers to first type in the
list (same as Head), any other one will result in recursive list reduction
until it contains only one element.
Index
Index is a bit more difficult, let’s start with the declaration.
1
2
|
template <typename List, typename T>
struct Index;
|
Index accepts the type list and the type that we want to find the index of.
Recursive base case is when the searched type is the first one on the list.
1
2
3
4
|
template <typename T, typename ... Types>
struct Index<TypeList<T, Types...>, T> {
constexpr static std::size_t value = 0;
};
|
In any other case, similarly as with Subscript or Last the value will
have to be recursively incremented and the type list reduced by one element.
The code won’t compile should you request a type that is not on the list.
1
2
3
4
|
template <typename T1, typename T2, typename ... Types>
struct Index<TypeList<T2, Types...>, T1> {
static constexpr std::size_t value = 1 + Index<TypeList<Types...>, T1>::value;
};
|
Full implementation below, along with some basic test cases:
1
2
3
4
5
6
|
using FourInts = TypeList<int, int, int, int>;
static_assert(Index<List1, int>::value == 0, "");
static_assert(Index<List3, float>::value == 1, "");
static_assert(Index<List3, std::string>::value == 2, "");
static_assert(Index<FourInts, int>::value == 0, "");
|
List modification
To complete the implementation, some routines to extend the list are required.
This will be Prepend and Append which add elements to the front or the back
of the list respectively. In comparison to prior operations, implementation of
these two is very simple.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|
template <typename List, typename T>
struct Append;
template <typename T, typename ...Types>
struct Append<TypeList<Types...>, T> {
using type = TypeList<Types..., T>;
};
template <typename List, typename T>
struct Prepend;
template <typename T, typename ...Types>
struct Prepend<TypeList<Types...>, T> {
using type = TypeList<T, Types...>;
};
|
Having implemented these, it’s now possible to extend any list.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|
using FiveInts = Append<FourInts, int>::type;
using SixInts = Prepend<FiveInts, int>::type;
using ShortLast = Append<List3, short>::type;
using ShortFirst = Prepend<List3, short>::type;
static_assert(Size<FiveInts>::value == 5, "");
static_assert(Size<SixInts>::value == 6, "");
static_assert(Size<ShortFirst>::value == 4, "");
static_assert(Size<ShortLast>::value == 4, "");
static_assert(std::is_same_v<Head<ShortFirst>::type, short>, "");
static_assert(std::is_same_v<Last<ShortLast>::type, short>, "");
|
Complete implementation in a form of a library can be found in my gitlab repo.
This implementation is a stepping stone which I need to discuss some other
concept so, please stay tuned :).