TypeList and Tic Tac Toe
I wanted, finally (!), To try out the
So,
A typical
Previously, without C ++ 11, it looked like this:
But now, thanks to the
As a matter of fact, it is interesting how to work with the list of types, how to define operations on it and what it ultimately gives (who is interested in a more detailed description and who hasn’t yet seen Modern C ++ Design - I advise you to read - it doesn’t matter that this is 2001! ).
So, apparently, I defined the auxiliary type
Here you can see almost everything we need to define other operations. As you can see, first we define the “backbone”: the type
How to use it?:
Whether the empty list we have defines the following expression:
literally - “the list is empty if its head is an auxiliary type denoting
Farther:
Using:
Again: “if the head of the list is our type
Partial specialization - a precautionary measure - what if someone takes advantage of our type
If the list is empty, the length is zero, otherwise it is one (because there is a “head”) + tail length:
- returns type by index, almost as an array. Implementation - first run (change type
- everything will work fine, but! - I would like to be warned if the index is too large. It would be possible to get out with the current implementation, but here it is necessary to take into account that the template must be correctly instantiated for the case
- the head has a zero index, and for other cases - we will simultaneously reduce the index by one and “eat” a piece of tail (we move from left to right) until we can take away - the index is zero, and the current head is the type we need! Using:
These functions help to accurately display the usual type lists and nested ones, for example:
When using
In the first case, the length of the result is 2, while in the second - 3, since the added list of types has “decomposed” into components.
Removal is done like this:
It is important that, because when deleting from the tail we grouped the result into another type list, when we combine, we use
Using:
You can write another version of
')
Example:
Function that removes duplicates:
Example:
A few things:
-
-
Again - nothing intricate - if the specified type and type of the head of the list are the same - then the index is zero, otherwise it will move to the right by 1ts and do the same for the tail of the list.
Example:
"Cuts" the specified part of the list:
variadic templates , as it is still tied to the 10th studio, where there is nothing like that. And in order not to think for a long time, where it is useless to use the variadic templates, I got the idea to try what Typelist will look like . For those who still do not know what it is, I will try to explain along the way, and for those who are bored - can immediately scroll down - we will try to write Typelist -tac-toe using Typelist .So,
TypeList :Typelist
namespace internal { struct Void { }; } // internal template<typename ...Args> struct TypeList { typedef internal::Void Head; typedef internal::Void Tail; }; typedef TypeList<> EmptyTypeList; template<typename H, typename ...T> struct TypeList<H, T...> { typedef H Head; typedef TypeList<T...> Tail; }; A typical
TypeList is a “head” ( Head ) and a “tail” ( Tail ), which in turn is also a list of types. Using: typedef TypeList<float, double, long double> floating_point_types; Previously, without C ++ 11, it looked like this:
Old typelist
And macros to help:
template <class H, class T> struct typelist { typedef H head; typedef T tail; }; typedef typelist<float, typelist<double, long double> > floating_point_types; And macros to help:
#define TYPELIST_1(T1) typelist<T1, null_typelist> #define TYPELIST_2(T1, T2) typelist<T1, TYPELIST_1(T2) > #define TYPELIST_3(T1, T2, T3) typelist<T1, TYPELIST_2(T2, T3) > ... #define TYPELIST_50... But now, thanks to the
variadic templates , you can get rid of both macros and the number of types in the list.As a matter of fact, it is interesting how to work with the list of types, how to define operations on it and what it ultimately gives (who is interested in a more detailed description and who hasn’t yet seen Modern C ++ Design - I advise you to read - it doesn’t matter that this is 2001! ).
So, apparently, I defined the auxiliary type
internal::Void , which will work as a signal flag and say that the list of types is empty (at least for the case when the user has not specified anything: TypeList<> , or when removed all items). Start over:IsEmpty
IsEmpty
template<typename TL> struct IsEmpty : std::true_type { }; template<> struct IsEmpty<TypeList<internal::Void, internal::Void>> : std::true_type { }; template<typename ...Args> struct IsEmpty<TypeList<Args...>> : std::integral_constant<bool, std::is_same<typename TypeList<Args...>::Head, internal::Void>::value && IsEmpty<typename TypeList<Args...>::Tail>::value> { }; Here you can see almost everything we need to define other operations. As you can see, first we define the “backbone”: the type
IsEmpty parameterized by one type. In essence, this is a “function” that takes one argument. Since the TL type means “any type”, we do a full specialization of the template for the case with an empty list: TypeList<internal::Void, internal::Void> (one could just TypeList<> or, just for this, I defined the type of EmptyTypeList ) and the partial specialization that works - “for any type list”. Thus, our “function” is defined only for the type list. In the new standard, such convenient things as std :: integral_constant appeared that greatly simplify life: in the case of struct IsEmpty : std::true_type , IsEmpty has a member of the value class, a number of typedef and a conversion operator to bool .How to use it?:
typedef TypeList<int> TL1; std::cout << std::boolalpha << IsEmpty<TL1>::value << " " << IsEmpty<EmptyTypeList>() << std::endl; Whether the empty list we have defines the following expression:
std::is_same<typename TypeList<Args...>::Head, internal::Void>::value && IsEmpty<typename TypeList<Args...>::Tail>::value literally - “the list is empty if its head is an auxiliary type denoting
void And if its tail is also an empty list”. As you can see, it uses recursion, which, just stops, the full specialization of the template for an empty list.Farther:
Contains
Contains
template<typename T, typename TL> struct Contains : std::false_type { }; template<typename ...Args> struct Contains<internal::Void, Args...> : std::false_type { }; template<typename T, typename ...Args> struct Contains<T, TypeList<Args...>> : std::integral_constant<bool, std::is_same<typename TypeList<Args...>::Head, T>::value || Contains<T, typename TypeList<Args...>::Tail>::value > { }; Contains determines if the specified type T inside the TL type list. Using:Using:
typedef TypeList<double, float, float, double, int, char, char, int, char> TL; std::cout << std::boolalpha << Contains<char, TL>::value << " " << Contains<float, TypeList<double>>() << std::endl; Again: “if the head of the list is our type
T , then T is inside the list, otherwise it is to see if there is T in the tail of the list”.Partial specialization - a precautionary measure - what if someone takes advantage of our type
internal::Void ?Length
Length
template<typename TL> struct Length : std::integral_constant<unsigned int, 0> { }; template<typename ...Args> struct Length<TypeList<Args...>> : std::integral_constant<unsigned int, IsEmpty<TypeList<Args...>>::value ? 0 : 1 + Length<typename TypeList<Args...>::Tail>::value> { }; If the list is empty, the length is zero, otherwise it is one (because there is a “head”) + tail length:
typedef TypeList<double, float, float, double, int, char, char, int, char> TL; std::cout << Length<TL>::value << " " << Length<EmptyTypeList>() << std::endl; Typeat
template<unsigned int N, typename TL> struct TypeAt { typedef internal::Void type; }; - returns type by index, almost as an array. Implementation - first run (change type
N to int ): //template<int N, typename ...Args> //struct TypeAt<N, TypeList<Args...>> //{ // typedef typename std::conditional<N == 0, // typename TypeList<Args...>::Head, // typename TypeAt<N - 1, typename TypeList<Args...>::Tail>::type>::type type; //}; - everything will work fine, but! - I would like to be warned if the index is too large. It would be possible to get out with the current implementation, but here it is necessary to take into account that the template must be correctly instantiated for the case
N=-1 . Therefore, we go another way: template<typename ...Args> struct TypeAt<0, TypeList<Args...>> { typedef typename TypeList<Args...>::Head type; }; template<unsigned int N, typename ...Args> struct TypeAt<N, TypeList<Args...>> { static_assert(N < Length<TypeList<Args...>>::value, "N is too big"); typedef typename TypeAt<N - 1, typename TypeList<Args...>::Tail>::type type; }; - the head has a zero index, and for other cases - we will simultaneously reduce the index by one and “eat” a piece of tail (we move from left to right) until we can take away - the index is zero, and the current head is the type we need! Using:
typedef TypeList<char, short> TL2; static_assert(std::is_same<TypeAt<1, TL2>::type, short>::value, "Something wrong!"); List output
operator <<
// std::ostream& operator<<(std::ostream& ostr, EmptyTypeList) { ostr << "{}"; return ostr; } template<typename TL> void PrintTypeListHelper(TL, std::ostream& ostr) { } template<typename T> void PrintTypeListHead(T, std::ostream& ostr) { ostr << typeid(T).name(); } template<typename ...Args> void PrintTypeListHead(TypeList<Args...> tl, std::ostream& ostr) { ostr << tl; } template<typename Head, typename ...Args> void PrintTypeListHelper(TypeList<Head, Args...>, std::ostream& ostr) { PrintTypeListHead(Head(), ostr); if(!IsEmpty<TypeList<Args...>>::value) { ostr << ' '; PrintTypeListHelper<Args...>(TypeList<Args...>(), ostr); } } template<typename ...Args> std::ostream& operator<<(std::ostream& ostr, TypeList<Args...> tl) { ostr << '{'; PrintTypeListHelper(tl, ostr); ostr << '}'; return ostr; } These functions help to accurately display the usual type lists and nested ones, for example:
typedef TypeList<double, float, float, double, int, char, char, int, char> TL; std::cout << TL() << std::endl; typedef TypeList<TL2, double, TL2> TL10; std::cout << TL10() << std::endl; {double float float double int char char int char}
{{char short} double {char short}}
Append and Add
Append, Add
The functions of adding to the end of the list, with a small difference:
template<typename TOrTL2, typename TL> struct Append { }; template<typename T, typename ...Args> struct Append<T, TypeList<Args...>> { typedef TypeList<Args..., T> type; }; template<typename ...Args1, typename ...Args2> struct Append<TypeList<Args1...>, TypeList<Args2...>> { typedef TypeList<Args2..., Args1...> type; }; template<typename T, typename TL> struct Add { }; template<typename T, typename ...Args> struct Add<T, TypeList<Args...>> { typedef TypeList<Args..., T> type; }; When using
Append with the list of types in the first argument, a “decomposition” into composite ones occurs. Those.: typedef TypeList<int> TL1; typedef TypeList<char, short> TL2; std::cout << TL1() << ", " << TL2() << std::endl; std::cout << Add<TL2, TL1>::type() << ", " << Append<TL2, TL1>::type() << std::endl; {int}, {char short}{int {char short}}, {int char short}In the first case, the length of the result is 2, while in the second - 3, since the added list of types has “decomposed” into components.
RemoveAll
Deleting items
template<typename TOrTL2, typename TL> struct RemoveAll { }; template<typename T, typename ...Args> struct RemoveAll<T, TypeList<Args...>> { private: typedef typename RemoveAll<T, typename TypeList<Args...>::Tail>::type Removed; typedef typename TypeList<Args...>::Head Head; public: typedef typename std::conditional< std::is_same<Head, T>::value, Removed, typename Append<Removed, TypeList<Head>>::type >::type type; }; template<typename T, typename Head> struct RemoveAll<T, TypeList<Head>> { typedef typename std::conditional< std::is_same<Head, T>::value, EmptyTypeList, TypeList<Head>>::type type; }; template<typename T> struct RemoveAll<T, EmptyTypeList> { typedef EmptyTypeList type; }; Removal is done like this:
- We can delete nothing from the empty list
- If we have a list with one element (head only), then return an empty list if the type of head is the same as the specified one or do not change anything otherwise
- For all other cases - remove items from the tail and if the head type does not match the specified type - add it before the removal result
It is important that, because when deleting from the tail we grouped the result into another type list, when we combine, we use
Append , which “spins up” the grouped type list back.Using:
typedef TypeList<double, float, float, double, int, char, char, int, char> TL; std::cout << TL() << std::endl; std::cout << RemoveAll<char, TL>::type() << std::endl; {double float float double int char char int char}{double float float double int int}You can write another version of
RemoveAll , which will remove from the second list of types all those that are in the first. But! In this case, it cannot be used for lists that contain other lists:')
RemoveAll v2
//template<typename Head2, typename ...Args1> //struct RemoveAll<TypeList<Head2>, TypeList<Args1...>> //{ // typedef typename RemoveAll<Head2, TypeList<Args1...>>::type type; //}; // //template<typename ...Args1> //struct RemoveAll<EmptyTypeList, TypeList<Args1...>> //{ // typedef TypeList<Args1...> type; //}; // //template<typename ...Args2, typename ...Args1> //struct RemoveAll<TypeList<Args2...>, TypeList<Args1...>> //{ //private: // typedef TypeList<Args2...> TL2; // typedef TypeList<Args1...> TL1; // // typedef typename RemoveAll<typename TL2::Tail, TL1>::type Removed; // typedef typename TL2::Head Head2; // //public: // typedef typename std::conditional< // Contains<Head2, Removed>::value, // typename RemoveAll<Head2, Removed>::type, // TL1 // >::type type; //}; Example:
typedef TypeList<double, float, float, double, int, char, char, int, char> TL; typedef TypeList<char, double> TL2; std::cout << TL() << std::endl; std::cout << RemoveAll<TL2, TL>::type() << std::endl; {double float float double int char char int char}{float float int int}RemoveDuplicates
RemoveDuplicates
template<typename TL> struct RemoveDuplicates { }; template<> struct RemoveDuplicates<EmptyTypeList> { typedef EmptyTypeList type; }; template<typename ...Args> struct RemoveDuplicates<TypeList<Args...>> { private: typedef TypeList<Args...> TL; typedef typename RemoveAll<typename TL::Head, typename TL::Tail>::type HeadRemovedFromTail; typedef typename RemoveDuplicates<HeadRemovedFromTail>::type TailWithoutDuplicates; public: typedef typename Append<TailWithoutDuplicates, TypeList<typename TL::Head>>::type type; }; Function that removes duplicates:
- We can delete nothing from the empty list
- Remove the same elements as the head from the tail
- Recursively call a function for the tail.
- Combine the head with the result
Example:
typedef TypeList<double, float, float, double, int, char, char, int, char> TL; std::cout << TL() << std::endl; std::cout << RemoveDuplicates<TL>::type() << std::endl; {double float float double int char char int char}{double float int char}Find
Position type in the list
struct Constants { typedef std::integral_constant<unsigned int, UINT_MAX> npos; }; namespace internal { template<typename T, unsigned int IndexFrom, typename TL> struct FindHelper : std::integral_constant<unsigned int, 0> { }; template<typename T, unsigned int IndexFrom> struct FindHelper<T, IndexFrom, EmptyTypeList> : std::integral_constant<unsigned int, 0> { }; template<typename T, unsigned int IndexFrom, typename ...Args> struct FindHelper<T, IndexFrom, TypeList<Args...>> : std::integral_constant<unsigned int, std::is_same<typename TypeList<Args...>::Head, T>::value ? IndexFrom : IndexFrom + 1 + FindHelper<T, IndexFrom, typename TypeList<Args...>::Tail>::value> { }; } // internal template<typename T, typename TL> struct Find { }; template<typename T> struct Find<T, EmptyTypeList> : Constants::npos { }; template<typename ...Args> struct Find<internal::Void, TypeList<Args...>> : Constants::npos { }; template<typename T, typename ...Args> struct Find<T, TypeList<Args...>> : std::integral_constant<unsigned int, Contains<T, TypeList<Args...>>::value ? internal::FindHelper<T, 0, TypeList<Args...>>::value : Constants::npos::value> { }; A few things:
-
Constants - for constants. In our case, only for the constant, which says that the item was not found (constexp is not supported in my studio, therefore UINT_MAX )-
internal::FindHelper - strictly speaking, the “thing” that searches for a type in the list that exactly (!) Contains this type (the additional parameter IndexFrom is the initial value of the counting, a completely unnecessary thing :) - designed for the case when ask where to start the search)Again - nothing intricate - if the specified type and type of the head of the list are the same - then the index is zero, otherwise it will move to the right by 1ts and do the same for the tail of the list.
Example:
typedef TypeList<double, float, float, double, int, char, char, int, char> TL; std::cout << std::boolalpha << std::is_same<TypeAt<Find<double, TL>::value, TL>::type, double>() << std::endl; Slice
Slice
namespace internal { template<unsigned int IndexBegin, unsigned int IndexEnd, typename TL> struct SliceHelper { }; template<unsigned int IndexBegin, unsigned int IndexEnd> struct SliceHelper<IndexBegin, IndexEnd, EmptyTypeList> { typedef EmptyTypeList type; }; template<unsigned int IndexBegin, typename ...Args> struct SliceHelper<IndexBegin, IndexBegin, TypeList<Args...>> { typedef TypeList<typename TypeAt<IndexBegin, TypeList<Args...>>::type> type; }; template<unsigned int IndexBegin, unsigned int IndexEnd, typename ...Args> struct SliceHelper<IndexBegin, IndexEnd, TypeList<Args...>> { private: static_assert(IndexEnd >= IndexBegin, "Invalid range"); typedef TypeList<Args...> TL; public: typedef typename Add< typename TypeAt<IndexEnd, TL>::type, typename SliceHelper<IndexBegin, IndexEnd - 1, TL>::type >::type type; }; } // internal template<unsigned int IndexBegin, unsigned int IndexAfterEnd, typename TL> struct Slice { }; template<unsigned int IndexBegin, unsigned int IndexEnd, typename ...Args> struct Slice<IndexBegin, IndexEnd, TypeList<Args...>> { typedef typename internal::SliceHelper<IndexBegin, IndexEnd, TypeList<Args...>>::type type; }; template<unsigned int Index, typename TL> struct CutTo { }; template<unsigned int Index, typename ...Args> struct CutTo<Index, TypeList<Args...>> { typedef typename Slice<0, Index, TypeList<Args...>>::type type; }; template<unsigned int Index, typename TL> struct CutFrom { }; template<unsigned int Index, typename ...Args> struct CutFrom<Index, TypeList<Args...>> { private: typedef TypeList<Args...> TL; public: typedef typename Slice<Index, Length<TL>::value - 1, TL>::type type; }; "Cuts" the specified part of the list:
- From the empty list we can not take anything
- When the specified beginning (
IndexBegin) and end (IndexEnd) are the same, it is similar to theTypeAtoperationTypeAt
Starting from the end of the specified range, take the element and add to the result of the recursive call (in which the end of the specified range is reduced by 1)
Thanks for attention!
Source: https://habr.com/ru/post/220217/
All Articles