Door April 21, 2014 at 14:17

TypeList and Tic Tac Toe

I finally wanted to (!) Try it variadic templates, because it is still tied to the 10th studio, where there is none of this. And so as not to think for a long time about where it is useless to use variadic templates, the idea came up to try what Typelist would 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 - try to write a kind of tic-tac-toe using Typelist.
So TypeList:

Typelist

namespace internal {
struct Void
{
};
} // internal
template
struct TypeList
{
    typedef internal::Void Head;
    typedef internal::Void Tail;
};
typedef TypeList<> EmptyTypeList;
template
struct TypeList
{
    typedef H Head;
    typedef TypeList Tail;
};

A typical one TypeListis a “head” ( Head) and a “tail” ( Tail), which in turn is also a list of types. Using:

typedef TypeList floating_point_types;

Previously, without C ++ 11, it looked like this:

Old TypeList

template 
struct typelist
{
    typedef H head;
    typedef T tail;
};
typedef typelist > floating_point_types;

And macros to help:

#define TYPELIST_1(T1) typelist
#define TYPELIST_2(T1, T2) typelist
#define TYPELIST_3(T1, T2, T3) typelist
...
#define TYPELIST_50...

But now, thanks to it variadic templates, you can get rid of macros and the restriction on the number of types in the list.
Actually, interesting is how to work with a list of types, how to define operations on it and what it gives in the end (who are interested in a more detailed description and who have not seen Modern C ++ Design - I advise you to read - it does not matter that this is 2001! )
So, as you can see, I defined a helper type internal::Voidthat will work as a signal flag and say that the list of types is empty (at least for the case when the user did not specify anything:, TypeList<>or when all elements are removed from the list). Start over:

Isempty

Isempty

template
struct IsEmpty :
    std::true_type
{
};
template<>
struct IsEmpty> :
    std::true_type
{
};
template
struct IsEmpty> :
    std::integral_constant::Head, internal::Void>::value &&
        IsEmpty::Tail>::value>
{
};

Here you can see almost everything we need to define other operations. As you can see, we first define the “backbone”: the type is IsEmptyparameterized by one type. In essence, it is a “function” that takes one argument. Since type TLmeans “any type”, we do a full specialization of the template for the case with an empty list: (it could be simple or just for that, I defined the type ) and a partial specialization that works - “for any list of types” . Thus, our “function” is defined only for a list of types. Convenient things like std :: integral_constant have appeared in the new standard , which greatly simplify life: in the case of , it has a class member , a series of s and a conversion operator toTypeListTypeList<>EmptyTypeListstruct IsEmpty : std::true_typeIsEmptyvaluetypedefbool.
How to use it ?:

typedef TypeList TL1;
std::cout << std::boolalpha << IsEmpty::value << " " << IsEmpty() << std::endl;

Whether we have an empty list defines the following expression:

std::is_same::Head, internal::Void>::value &&
IsEmpty::Tail>::value

literally - "the list is empty if its head is an auxiliary type, indicating voidAnd if its tail is also an empty list." As you can see, recursion is used here, which just stops the full specialization of the template for an empty list.
Further:

Containers

Containers

template
struct Contains :
    std::false_type
{
};
template
struct Contains :
    std::false_type
{
};
template
struct Contains> :
    std::integral_constant::Head, T>::value ||
        Contains::Tail>::value
        >
{
};

Containsdetermines if the specified type is Tinside the type list TL. Usage:

Usage:

typedef TypeList TL;
std::cout << std::boolalpha << Contains::value << " " << Contains>() << std::endl;

Again: "if the head of the list is our type T, that Tis, inside the list, otherwise, see if there is Ta tail in the list."
Partial specialization - precautionary measures - what if someone uses our type internal::Void?

Length

Length

template
struct Length :
    std::integral_constant
{
};
template
struct Length> :
    std::integral_constant>::value
            ? 0
            : 1 + Length::Tail>::value>
{
};

If the list is empty, the length is zero, otherwise it is one (because there is a “head” ( Head)) + tail length:

typedef TypeList TL;
std::cout << Length::value << " " << Length() << std::endl;

Typeat

template
struct TypeAt
{
    typedef internal::Void type;
};

- returns the type by index, almost like an array. Implementation - the first call (change the type Nto int):

//template
//struct TypeAt>
//{    
//    typedef typename std::conditional::Head,
//        typename TypeAt::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 we must take into account the fact that the template must be correctly instantiated for the case N=-1. Therefore, we go the other way:

template
struct TypeAt<0, TypeList>
{
    typedef typename TypeList::Head type;
};
template
struct TypeAt>
{
    static_assert(N < Length>::value, "N is too big");
    typedef typename TypeAt::Tail>::type type;
};

- the head has a zero index, and for other cases - we will simultaneously decrease the index by one and “eat” a piece of the tail (we move from left to right) until we can take it away - the index is zero, and the current head is the type we need! Using:

typedef TypeList TL2;
static_assert(std::is_same::type, short>::value, "Something wrong!");

List output

operator <<

// Пустой список
std::ostream& operator<<(std::ostream& ostr, EmptyTypeList)
{
	ostr << "{}";
	return ostr;
}
template
void PrintTypeListHelper(TL, std::ostream& ostr)
{
}
template
void PrintTypeListHead(T, std::ostream& ostr)
{
	ostr << typeid(T).name();
}
template
void PrintTypeListHead(TypeList tl, std::ostream& ostr)
{
	ostr << tl;
}
template
void PrintTypeListHelper(TypeList, std::ostream& ostr)
{
	PrintTypeListHead(Head(), ostr);
	if(!IsEmpty>::value)
	{
		ostr << ' ';
		PrintTypeListHelper(TypeList(), ostr);
	}
}
template
std::ostream& operator<<(std::ostream& ostr, TypeList tl)
{
	ostr << '{';
	PrintTypeListHelper(tl, ostr);
	ostr << '}';
	return ostr;
}

These functions help to accurately display regular type lists and nested ones, for example:

typedef TypeList TL;
std::cout << TL() << std::endl;
typedef TypeList 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

Functions of adding to the end of the list, with a small difference:


template
struct Append
{
};
template
struct Append>
{
    typedef TypeList type;
};
template
struct Append, TypeList>
{
    typedef TypeList type;
};
template
struct Add
{
};
template
struct Add>
{
	typedef TypeList type;
};

When used Appendwith a list of types in the first argument, "decomposition" into components occurs. Those.:

typedef TypeList TL1;
typedef TypeList TL2;
std::cout << TL1() << ", " << TL2() << std::endl;
std::cout << Add::type() << ", " << Append::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 it is 3, since the added list of types “decomposed” into components.

Removeall

Delete items

template
struct RemoveAll
{
};
template
struct RemoveAll>
{
private:
    typedef typename RemoveAll::Tail>::type Removed;
    typedef typename TypeList::Head Head;
public:
    typedef typename std::conditional<
        std::is_same::value,
        Removed,
        typename Append>::type
        >::type type;
};
template
struct RemoveAll>
{
    typedef typename std::conditional<
        std::is_same::value,
        EmptyTypeList,
        TypeList>::type type;
};
template
struct RemoveAll
{
    typedef EmptyTypeList type;
};

Removal is done like this:

We cannot delete anything from the empty list
If we have a list with one element (only the head), then return an empty list if the type of the head matches the specified one or change nothing otherwise
For all other cases - remove elements from the tail, and if the head type does not match the specified type - add it before the delete result

The important thing is that when we removed the result from the tail we grouped the result into another list of types, when combined, it is used Appendthat “unwinds” the grouped list of types back.
Using:

typedef TypeList TL;
std::cout << TL() << std::endl;
std::cout << RemoveAll::type() << std::endl;

{double float float double int char char int char}
{double float float double int int}

You can write another version RemoveAllthat 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
//struct RemoveAll, TypeList>
//{
//    typedef typename RemoveAll>::type type;
//};
//
//template
//struct RemoveAll>
//{
//    typedef TypeList type;
//};
//
//template
//struct RemoveAll, TypeList>
//{
//private:
//    typedef TypeList TL2;
//    typedef TypeList TL1;
//    
//    typedef typename RemoveAll::type Removed;
//    typedef typename TL2::Head Head2;
//    
//public:
//    typedef typename std::conditional<
//        Contains::value,
//        typename RemoveAll::type,
//        TL1
//        >::type type;    
//};

Example:

typedef TypeList TL;
typedef TypeList TL2;
std::cout << TL() << std::endl;
std::cout << RemoveAll::type() << std::endl;

{double float float double int char char int char}
{float float int int}

RemoveDuplicates

RemoveDuplicates

template
struct RemoveDuplicates
{
};
template<>
struct RemoveDuplicates
{
    typedef EmptyTypeList type;
};
template
struct RemoveDuplicates>
{
private:
    typedef TypeList TL;
    typedef typename RemoveAll::type HeadRemovedFromTail;
    typedef typename RemoveDuplicates::type TailWithoutDuplicates;
public:
    typedef typename Append>::type type;
};

Function that removes duplicates:

We cannot delete anything from the empty list
We 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 TL;
std::cout << TL() << std::endl;
std::cout << RemoveDuplicates::type() << std::endl;

{double float float double int char char int char}
{double float int char}

Find

Type position in list

struct Constants
{
    typedef std::integral_constant npos;
};
namespace internal {
template
struct FindHelper :
    std::integral_constant
{
};
template
struct FindHelper :
    std::integral_constant
{
};
template
struct FindHelper> :
    std::integral_constant::Head, T>::value
        ? IndexFrom
        : IndexFrom + 1 + FindHelper::Tail>::value>
{
};
} // internal
template
struct Find
{
};
template
struct Find :
    Constants::npos
{
};
template
struct Find> :
    Constants::npos
{
};
template
struct Find> :
    std::integral_constant>::value
        ? internal::FindHelper>::value
        : Constants::npos::value>
{
};

A few things:
- Constants- for constants. In our case, only for a constant that says that the element was not found (constexp is not supported in my studio, therefore UINT_MAX)
- internal::FindHelper- in fact, a “thing” that looks for a type in a list that exactly (!) Contains this type ( an additional parameter IndexFrom- the initial value of the reference, not at all necessary thing :) - is designed for the case when you need to specify from what position to start the search)

Again - nothing complicated - if the specified type and the type of the head of the list matches - then the index is zero, otherwise - move right by 1tsu and do the same sa mine for tail list.
Example:

typedef TypeList TL;
std::cout << std::boolalpha << std::is_same::value, TL>::type, double>() << std::endl;

Slice

Slice

namespace internal {
template
struct SliceHelper
{
};
template
struct SliceHelper
{
    typedef EmptyTypeList type;
};
template
struct SliceHelper>
{
    typedef TypeList>::type> type;
};
template
struct SliceHelper>
{
private:
    static_assert(IndexEnd >= IndexBegin, "Invalid range");
    typedef TypeList TL;
public:
    typedef typename Add<
        typename TypeAt::type,
        typename SliceHelper::type
        >::type type;
};
} // internal
template
struct Slice
{
};
template
struct Slice>
{
    typedef typename internal::SliceHelper>::type type;
};
template
struct CutTo
{
};
template
struct CutTo>
{
    typedef typename Slice<0, Index, TypeList>::type type;
};
template
struct CutFrom
{
};
template
struct CutFrom>
{
private:
    typedef TypeList TL;
public:
    typedef typename Slice::value - 1, TL>::type type;
};

"Cuts" the specified part of the list:

We can’t take anything from an empty list
When the specified beginning ( IndexBegin) and end ( IndexEnd) coincide, then this is similar to the operation TypeAt
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 decreases by 1cu)

Tags: