TypeList и Крестики-нолики / Хабр

Захотелось, наконец-то(!), попробовать variadic templates, так как до сих пор привязан к 10й студии, где ничего этого нету. А чтобы долго не думать, где же можно бесполезно использовать variadic templates, пришла идея попробовать, как будет выглядеть Typelist. Для тех, кто ещё не знает, что это такое, я постараюсь объяснять по ходу дела, а тем, кому это скучно — может сразу пролистать вниз — попробуем написать подобие крестиков-ноликов с использованием Typelist.
Итак, 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;
};

Типичный TypeList представляет собой «голову»(Head) и «хвост»(Tail), который в свою очередь также является списком типов. Использование:

typedef TypeList<float, double, long double> floating_point_types;

Раньше, без С++11, это выглядело так:

Старый TypeList

template <class H, class T>
struct typelist
{
    typedef H head;
    typedef T tail;
};

typedef typelist<float, typelist<double, long double> > floating_point_types;

И макросы в помощь:

#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...

Но теперь, благодаря variadic templates, можно избавиться и от макросов, и от ограничения на количество типов в списке.
Собственно говоря интересным является то, как работать со списком типов, как определить операции над ним и что это даёт в конечном итоге(кому интересно более детальное описание и кто ещё не видел Modern C++ Design — советую почитать — не важно, что это 2001 год!).
Итак, как видно, я определил вспомогательный тип internal::Void, который будет работать, как сигнальный флажок и говорить, что список типов пуст(как минимум, для случая, когда пользователь не указал ничего: TypeList<>, или, когда со списка удалено все элементы). Начнём с начала:

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>
{
};

Здесь видно почти всё, что нам нужно, для определения других операций. Как видно, сначала мы определяем «костяк»: тип IsEmpty параметризован одним типом. По сути, это «функция», принимающая один аргумент. Поскольку тип TL означает — «любой тип», мы делаем полную специализацию шаблона для случая с пустым списком: TypeList<internal::Void, internal::Void>(можно было бы и просто TypeList<> или, как раз для этого, я определил тип EmptyTypeList) и частичную специализацию, которая работает — «для любого списка типов». Таким образом, наша «функция» определена только для списка типов. В новом стандарте появились такие удобные штуки, как std::integral_constant, которые очень сильно упрощают жизнь: в случае с struct IsEmpty : std::true_type, IsEmpty имеет член класса value, ряд typedef-ов и оператор преобразования в bool.
Как это использовать ?:

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

Пустой ли список мы имеем определяет следующее выражение:

std::is_same<typename TypeList<Args...>::Head, internal::Void>::value &&
IsEmpty<typename TypeList<Args...>::Tail>::value

дословно — «список пуст, если его голова — это вспомогательный тип, обозначающий void И если его хвост также является пустым списком». Как видно, здесь используется рекурсия, которую, как раз и останавливает, полная специализация шаблона для пустого списка.
Дальше:

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 определяет есть ли указанный тип T внутри списка типов TL. Использование:

Использование:

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;

Снова же: «если голова списка это наш тип T, то T есть внутри списка, а иначе — посмотреть, есть ли T в хвосте списка».
Частичная специализация — мере предосторожности — а вдруг кто-то воспользуется нашим типом 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>
{
};

Если список пуст — длина нулевая, а иначе — это единица(потому что присутствует «голова»(Head)) + длина хвоста:

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;
};

— возвращает тип по индексу, почти, как массив. Реализация — первый заход(меняем тип N на 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;
//};

— всё будет прекрасно работать, но! — хотелось бы быть предупреждённым, если указан слишком большой индекс. Можно бы было выкрутиться и с текущей реализацией, но здесь нужно учитывать то, что шаблон должен быть корректно инстанцирован для случая N=-1. Поэтому идём другим путём:

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;
};

— голова имеет нулевой индекс, а для других случаев — будем одновременно уменьшать индекс на единицу и «съедать» кусочек хвоста(передвигаемся слева на право), пока не сможем отнять — индекс нулевой, а текущая голова и есть нужный нам тип! Использование:

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

Вывод списка

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;
}

Эти функции помогают аккуратно вывести обычные списки типов и вложенные, например:

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 и Add

Append, Add

Функции добавления в конец списка, с маленькой разницей:


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;
};

При использовании Append со списком типов в первом аргументе происходит «разложение» на составные. Т.е.:

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}
В первом случае длина результата — 2, тогда как во втором — 3, так как добавляемый список типов «разложился» на компоненты.

RemoveAll

Удаление элементов

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;
};

Удаление делается так:

С пустого списка мы ничего не можем удалить
Если у нас список с одним элементом(только голова) — то вернуть пустой список, если тип головы совпадает с заданным или ничего не изменять в противном случае
Для всех остальных случаев — удалить элементы с хвоста и е��ли тип головы не совпадает с заданным типом — добавить её до результата удаления

Важно то, что, поскольку при удалении с хвоста мы сгрупировали результат в другой список типов, при объединении, используется Append, который «раскручивает» назад сгруппированный список типов.
Использование:

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}

Можно написать ещё одну версию RemoveAll, которая будет удалять со второго списка типов все те, которые есть в первом. Но! В таком случае ее нельзя использовать для списков, которые содержат другие списки:

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;    
//};

Пример:

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;
};

Функция, которая удаляет дубликаты:

С пустого списка мы ничего не можем удалить
Удаляем такие же элементы, как и голова из хвоста
Рекурсивно вызываем функцию для хвоста
Объединяем голову с результатом

Пример:

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

Позиция типа в списке

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>
{
};

Несколько вещей:
— Constants — для констант. В нашем случае только для константы, которая говорит о том, что элемент не найден(constexp не поддерживается в моей студии, поэтому UINT_MAX)
— internal::FindHelper — собственно говоря, «штука», которая ищет тип в списке, который точно(!) этот тип содержит(дополнительный параметр IndexFrom — начальное значение отсчёта, совсем не нужная вещь:) — рассчитана на случай, когда нужно будет задавать с какой позиции начинать поиск)

Снова же — ничего замысловат��го — если указанный тип и тип головы списка совпадает — тогда индекс — нулевой, а иначе — переместится вправо на 1цу и сделать то же самое для хвоста списка.
Пример:

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;
};

«Вырезает» указанную часть списка:

С пустого списка мы ничего не можем взять
Когда указанные начало(IndexBegin) и конец(IndexEnd) совпадают, то это аналогично операции TypeAt
Начиная с конца указанного диапазона, взять элемент и добавить к результату рекурсивного вызова(в котором конец указанного диапазона уменьшается на 1цу)