TypeList и Крестики-нолики21.04.2014 14:49
Захотелось, наконец-то (!), попробовать variadic templates, так как до сих пор привязан к 10й студии, где ничего этого нету. А чтобы долго не думать, где же можно бесполезно использовать variadic templates, пришла идея попробовать, как будет выглядеть Typelist. Для тех, кто ещё не знает, что это такое, я постараюсь объяснять по ходу дела, а тем, кому это скучно — может сразу пролистать вниз — попробуем написать подобие крестиков-ноликов с использованием Typelist.Итак, 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;
};
Типичный TypeList представляет собой «голову»(Head) и «хвост»(Tail), который в свою очередь также является списком типов. Использование:
typedef TypeList floating_point_types;
Раньше, без С++11, это выглядело так: Старый TypeList
template
struct typelist
{
typedef H head;
typedef T tail;
};
typedef typelist > floating_point_types;
И макросы в помощь:
#define TYPELIST_1(T1) typelist
#define TYPELIST_2(T1, T2) typelist
#define TYPELIST_3(T1, T2, T3) typelist
…
#define TYPELIST_50…
Но теперь, благодаря variadic templates, можно избавиться и от макросов, и от ограничения на количество типов в списке.Собственно говоря интересным является то, как работать со списком типов, как определить операции над ним и что это даёт в конечном итоге (кому интересно более детальное описание и кто ещё не видел Modern C++ Design — советую почитать — не важно, что это 2001 год!).Итак, как видно, я определил вспомогательный тип internal: Void, который будет работать, как сигнальный флажок и говорить, что список типов пуст (как минимум, для случая, когда пользователь не указал ничего: TypeList<>, или, когда со списка удалено все элементы). Начнём с начала: 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>
{
};
Здесь видно почти всё, что нам нужно, для определения других операций. Как видно, сначала мы определяем «костяк»: тип IsEmpty параметризован одним типом. По сути, это «функция», принимающая один аргумент. Поскольку тип TL означает — «любой тип», мы делаем полную специализацию шаблона для случая с пустым списком: TypeList(можно было бы и просто TypeList<> или, как раз для этого, я определил тип EmptyTypeList) и частичную специализацию, которая работает — «для любого списка типов». Таким образом, наша «функция» определена только для списка типов. В новом стандарте появились такие удобные штуки, как std: integral_constant, которые очень сильно упрощают жизнь: в случае с struct IsEmpty: std: true_type, IsEmpty имеет член класса value, ряд typedef-ов и оператор преобразования в bool.Как это использовать ?:
typedef TypeList TL1;
std: cout << std::boolalpha << IsEmpty:: value << " " << IsEmpty() << std::endl;
Пустой ли список мы имеем определяет следующее выражение:
std::is_same:: Head, internal: Void>:: value &&
IsEmpty:: Tail>:: value
дословно — «список пуст, если его голова — это вспомогательный тип, обозначающий void И если его хвост также является пустым списком». Как видно, здесь используется рекурсия, которую, как раз и останавливает, полная специализация шаблона для пустого списка.Дальше: Contains
Contains
template
struct Contains:
std: false_type
{
};
template
struct Contains:
std: false_type
{
};
template
struct Contains>:
std: integral_constant:: Head, T>:: value ||
Contains:: Tail>:: value
>
{
};
Contains определяет есть ли указанный тип T внутри списка типов TL. Использование: Использование:
typedef TypeList TL;
std: cout << std::boolalpha << Contains:: value << " " << Contains>() << std::endl;
Снова же: «если голова списка это наш тип T, то T есть внутри списка, а иначе — посмотреть, есть ли T в хвосте списка».Частичная специализация — мере предосторожности — а вдруг кто-то воспользуется нашим типом internal::Void?Length
Length
template
struct Length:
std: integral_constant
{
};
template
struct Length>:
std: integral_constant>:: value
? 0
: 1 + Length:: Tail>:: value>
{
};
Если список пуст — длина нулевая, а иначе — это единица (потому что присутствует «голова»(Head)) + длина хвоста:
typedef TypeList TL;
std: cout << Length:: value << " " << Length() << std::endl;
TypeAt
template
struct TypeAt
{
typedef internal: Void type;
};
— возвращает тип по индексу, почти, как массив. Реализация — первый заход (меняем тип N на int):
//template
//struct TypeAt>
//{
// typedef typename std: conditional:: Head,
// typename TypeAt:: Tail>:: type>:: type type;
//};
— всё будет прекрасно работать, но! — хотелось бы быть предупреждённым, если указан слишком большой индекс. Можно бы было выкрутиться и с текущей реализацией, но здесь нужно учитывать то, что шаблон должен быть корректно инстанцирован для случая N=-1. Поэтому идём другим путём:
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;
};
— голова имеет нулевой индекс, а для других случаев — будем одновременно уменьшать индекс на единицу и «съедать» кусочек хвоста (передвигаемся слева на право), пока не сможем отнять — индекс нулевой, а текущая голова и есть нужный нам тип! Использование:
typedef TypeList TL2;
static_assert (std: is_same:: type, short>:: value, «Something wrong!»);
Вывод списка
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;
}
Эти функции помогают аккуратно вывести обычные списки типов и вложенные, например:
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 и Add
Append, Add
Функции добавления в конец списка, с маленькой разницей:
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;
};
При использовании Append со списком типов в первом аргументе происходит «разложение» на составные. Т.е.:
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}В первом случае длина результата — 2, тогда как во втором — 3, так как добавляемый список типов «разложился» на компоненты.RemoveAll
Удаление элементов
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;
};
Удаление делается так: С пустого списка мы ничего не можем удалить
Если у нас список с одним элементом (только голова) — то вернуть пустой список, если тип головы совпадает с заданным или ничего не изменять в противном случае
Для всех остальных случаев — удалить элементы с хвоста и если тип головы не совпадает с заданным типом — добавить её до результата удаления
Важно то, что, поскольку при удалении с хвоста мы сгрупировали результат в другой список типов, при объединении, используется Append, который «раскручивает» назад сгруппированный список типов.Использование:
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}Можно написать ещё одну версию RemoveAll, которая будет удалять со второго списка типов все те, которые есть в первом. Но! В таком случае ее нельзя использовать для списков, которые содержат другие списки:
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;
//};
Пример:
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;
};
Функция, которая удаляет дубликаты: С пустого списка мы ничего не можем удалить
Удаляем такие же элементы, как и голова из хвоста
Рекурсивно вызываем функцию для хвоста
Объединяем голову с результатом
Пример:
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
Позиция типа в списке
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>
{
};
Несколько вещей: — Constants — для констант. В нашем случае только для константы, которая говорит о том, что элемент не найден (constexp не поддерживается в моей студии, поэтому UINT_MAX)— internal: FindHelper — собственно говоря, «штука», которая ищет тип в списке, который точно (!) этот тип содержит (дополнительный параметр IndexFrom — начальное значение отсчёта, совсем не нужная вещь:) — рассчитана на случай, когда нужно будет задавать с какой позиции начинать поиск)
Снова же — ничего замысловатого — если указанный тип и тип головы списка совпадает — тогда индекс — нулевой, а иначе — переместится вправо на 1цу и сделать то же самое для хвоста списка.Пример:
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;
};
«Вырезает» указанную часть списка: С пустого списка мы ничего не можем взять
Когда указанные начало (IndexBegin) и конец (IndexEnd) совпадают, то это аналогично операции TypeAt
Начиная с конца указанного диапазона, взять элемент и добавить к результату рекурсивного вызова (в котором конец указанного диапазона уменьшается на 1цу)
Пример:
typedef TypeList TL;
std: cout << TL() << std::endl;
std::cout << Slice<2, 6, TL>:: type () << std::endl;
std::cout << CutTo<2, TL>:: type () << std::endl;
std::cout << CutFrom<8, TL>:: type () << std::endl;
{double float float double int char char int char}{float double int char char}{double float float}{char}Replace
Replace
template
struct Replace
{
};
template
struct Replace<0, NewValue, TypeList>
{
typedef typename Append:: Tail, TypeList>:: type type;
};
template
struct Replace>
{
private:
typedef TypeList TL;
typedef std: integral_constant:: value — 1> AtEndWorkAround;
public:
typedef typename std: conditional<
AtEndWorkAround::value,
typename internal::ReplaceEnd:: type,
typename internal: ReplaceMiddle:: type
>:: type type;
};
Заменяет тип в указанной позиции (Index) на другой (NewValue): Замена первого элемента: Это Head
Cоздать с NewValue список типов к которому добавить «хвост»(т.е. всё кроме первого элемента — «головы»)
Замена последнего элемента: Последний элемент имеет индекс Index — 1
«Вырезать» список от начала и до последнего элемента, не включая его (т.е. до Index — 2)
К результату добавить NewValue
Остальные случаи: Взять список от 0 до Index — 1 — Begin
Взять список от Index + 1 до конца — End
Объеденить три части: Begin + NewValue + End
Пример:
typedef TypeList TLR;
std: cout << TLR() << std::endl;
std::cout << Replace<0, double, TLR>:: type () << std::endl;
{int char float}{double char float}
ReplaceType
ReplaceType
namespace internal {
template
struct ReplaceTypeHelper
{
typedef EmptyTypeList type;
};
template
struct ReplaceTypeHelper>
{
private:
typedef TypeList TL;
public:
typedef typename Replace:: value, NewValue, TL>:: type type;
};
} // internal
// Will replace first founded @OldValue
template
struct ReplaceType
{
};
template
struct ReplaceType>
{
private:
typedef TypeList TL;
typedef std: integral_constant:: value == Constants: npos: value
> NotFound;
public:
typedef typename std: conditional<
NotFound::value,
TL,
typename internal::ReplaceTypeHelper<
NotFound::value,
OldValue,
NewValue,
TL
>:: type
>:: type type;
};
Аналогично Replace, только сначала нужно найти позицию (Find)
Пример:
typedef TypeList TLR;
std: cout << TLR() << std::endl;
std::cout << ReplaceType:: type () << std::endl;
{int char float}{int double float}
Крестики-нолики
Создадим поле, обычно 3×3:
// Empty field
struct E
{
};
struct O
{
};
struct X
{
};
enum { ROWS = 3, COLUMNS = 3 };
// RepeatT создаёт список типов,
// который состоит из N элементов типа T
typedef RepeatT:: type Row;
typedef RepeatT:: type Field;
Т.е. поле — это список рядков (Важно *), а рядок — это список ячеек.Получается, что-то такое: Пример полей
std: cout << Field() << std::endl;
{
{struct E struct E struct E}
{struct E struct E struct E}
{struct E struct E struct E}
}
И, когда COLUMNS = 4:
{
{struct E struct E struct E struct E}
{struct E struct E struct E struct E}
{struct E struct E struct E struct E}
}
Определим функции для изменения состояния:
Изменение состояния поля
template
struct FigureAt
{
private:
typedef typename TypeAt:: type CurrentRow;
public:
typedef typename TypeAt:: type type;
};
template
struct ReplaceAt
{
private:
typedef typename TypeAt:: type OldRow;
typedef typename Replace:: type NewRow;
public:
typedef typename Replace:: type type;
};
Например:
Как это выглядит
typedef ReplaceAt<1, 1, X, Field>:: type Field2;
typedef ReplaceAt<2, 1, X, Field2>:: type Field3;
{
{struct E struct E struct E struct E}
{struct E struct X struct E struct E}
{struct E struct X struct E struct E}
}
Поле есть, выставлять значения мы умеем — нужно как-то определять есть ли победитель? Для начала — простой случай: победил тот, кто выстроил или ряд, или столбик (по диагонали не будем считать сейчас). Т.е. на входе у насть есть масив рядочков (столбиков) и если среди них присутствует хотя бы один, полность выстроенный одним знаком (крестиком, ноликом) рядочек (столбик), то этот знак победил! Итак:
template
struct IsWin
{
// Определяем рядок или столбик победителя
typedef typename RepeatT:: type WinRow;
typedef typename RepeatT:: type WinColumn;
// Если есть хотя бы один рядок или столбик победителя
static const bool value = Contains:: value ||
// Field — это список рядков, ReconfigureField -
// превращает список рядков в список столбиков
Contains:: type>:: value;
};
Взглянем на ReconfigureField:
ReconfigureField
namespace internal {
template
struct ColumnTypeHelper
{
typedef typename Add<
typename FigureAt:: type,
typename ColumnTypeHelper:: type
>:: type type;
};
template
struct ColumnTypeHelper
{
typedef typename Add:: type, CurrentColumnType>:: type type;
};
} // internal
template
struct ColumnType
{
typedef typename internal: ColumnTypeHelper:: type type;
};
namespace internal {
template
struct ReconfigureFieldHelper
{
typedef typename Add<
typename ColumnType:: type,
typename ReconfigureFieldHelper:: type
>:: type type;
};
template
struct ReconfigureFieldHelper<0, NewF, F>
{
typedef typename Add<
typename ColumnType<0, F>:: type,
NewF
>:: type type;
};
} // internal
template
struct ReconfigureField
{
typedef typename internal: ReconfigureFieldHelper<
COLUMNS - 1, EmptyTypeList, F>:: type type;
};
Что ReconfigureField делает на практике (это хорошо видно, когда количество столбиков и рядочков неодинаково):
ReconfigureField: результат
typedef ReplaceAt<1, 1, X, Field>:: type Field2;
typedef ReplaceAt<2, 1, X, Field2>:: type Field3;
std: cout << Field3() << std::endl;
std::cout << ReconfigureField:: type () << std::endl;
{
{struct E struct E struct E struct E}
{struct E struct X struct E struct E}
{struct E struct X struct E struct E}
}
{
{struct E struct E struct E}
{struct E struct X struct X}
{struct E struct E struct E}
{struct E struct E struct E}
}
Т.е. 1 столбик становится 1 рядком, 2й столбик — 2 м и т.д. — это всё, что нужно, чтобы найти столбик победителя на поле, что мы и делаем:
Contains:: type>:: value
Можно ещё поизвращаться, но я устал. В конце-концов:
typedef ReplaceAt<1, 1, X, Field>:: type Field2;
typedef ReplaceAt<2, 1, X, Field2>:: type Field3;
typedef ReplaceAt<0, 1, X, Field3>:: type Field4;
std: cout << std::boolalpha << IsWin:: value << std::endl;
std::cout << std::boolalpha << IsWin:: value << std::endl;
std::cout << std::boolalpha << IsWin:: value << std::endl;
// Вывод
false
false
true
Спасибо за внимание!
© Habrahabr.ru
