c ++ 11 — Компилятор Intel C ++ очень медленно компилирует рекурсивные результаты decltype

Вот удар в этом. Вместо парного сравнения каждого из элементов я сортирую список типов, а затем использую уникальный алгоритм, чтобы выяснить, есть ли дубликаты.

Я реализовал сортировку слиянием типов, потому что это было весело. Вероятно, наивная сортировка пузырей будет лучше работать на разумном количестве аргументов. Обратите внимание, что небольшая работа позволит нам выполнить сортировку слиянием в длинных списках и специализироваться на пузырьковых сортировках (или даже вставках) в коротких списках. Я не для написания шаблона быстрой сортировки.

Это дает мне логическое значение времени компиляции, которое говорит, есть ли дубликаты в списке. Затем я могу использовать enable_if, чтобы выбрать, какую перегрузку я собираюсь использовать.

Обратите внимание, что в вашем решении использовалось n ^ 2 слоя рекурсии шаблона, на каждом из которых возвращаемый тип требует оценки типа более простого класса на 1 шаг, а затем возвращаемый тип также требует того же! Если запоминание компилятором Intel не удается, вы говорите об экспоненциальном объеме работы.

Я дополнил несколько ваших уроков помощниками. Я сделал твой LabelNameнаследовать от std::integral_constant, поэтому я легко компилирую время доступа к их значению. Это делает сортировку кода немного проще. Я также выставил enum из повторяющихся и уникальных возвращаемых значений, так что я могу сделать простой printf отладка по результату.

Большая часть этой работы — написание сортировки слиянием — есть ли стандартная сортировка типа времени компиляции, которую мы могли бы использовать?

#include <type_traits>
#include <iostream>

template <typename... T> struct TypeList { };

// NOTE THIS CHANGE:
template <char C> struct LabelName:std::integral_constant<char, C> {};

template <typename... T> class UniqueExpression
{
// Contains implementation details in actual code
public:
enum { is_unique = true };
};

template <typename... T> class RepeatedExpression
{
// Contains implementation details in actual code
public:
enum { is_unique = false };
};

// A compile time merge sort for types
// Split takes a TypeList<>, and sticks the even
// index types into Left and odd into Right
template<typename T>
struct Split;
template<>
struct Split<TypeList<>>
{
typedef TypeList<> Left;
typedef TypeList<> Right;
};
template<typename T>
struct Split<TypeList<T>>
{
typedef TypeList<T> Left;
typedef TypeList<> Right;
};

// Prepends First into the TypeList List.
template<typename First, typename List>
struct Prepend;
template<typename First, typename... ListContents>
struct Prepend<First,TypeList<ListContents...>>
{
typedef TypeList<First, ListContents...> type;
};

template<typename First, typename Second, typename... Tail>
struct Split<TypeList<First, Second, Tail...>>
{
typedef typename Prepend< First, typename Split<TypeList<Tail...>>::Left>::type Left;
typedef typename Prepend< Second, typename Split<TypeList<Tail...>>::Right>::type Right;
};

// Merges the sorted TypeList<>s Left and Right to the end of TypeList<> MergeList
template< typename Left, typename Right, typename MergedList=TypeList<> >
struct Merge;
template<typename MergedList>
struct Merge< TypeList<>, TypeList<>, MergedList >
{
typedef MergedList type;
};
template<typename L1, typename... Left, typename... Merged>
struct Merge< TypeList<L1, Left...>, TypeList<>, TypeList<Merged... >>
{
typedef TypeList<Merged..., L1, Left...> type;
};
template<typename R1, typename... Right, typename... Merged>
struct Merge< TypeList<>, TypeList<R1, Right...>, TypeList<Merged...> >
{
typedef TypeList<Merged..., R1, Right...> type;
};
template<typename L1, typename... Left, typename R1, typename... Right, typename... Merged>
struct Merge< TypeList<L1, Left...>, TypeList<R1, Right...>, TypeList<Merged...>>
{
template<bool LeftIsSmaller, typename LeftList, typename RightList, typename MergedList>
struct MergeHelper;

template<typename FirstLeft, typename... LeftTail, typename FirstRight, typename... RightTail, typename... MergedElements>
struct MergeHelper< true, TypeList<FirstLeft, LeftTail...>, TypeList<FirstRight, RightTail...>, TypeList<MergedElements...> >
{
typedef typename Merge< TypeList<LeftTail...>, TypeList< FirstRight, RightTail... >, TypeList< MergedElements..., FirstLeft > >::type type;
};
template<typename FirstLeft, typename... LeftTail, typename FirstRight, typename... RightTail, typename... MergedElements>
struct MergeHelper< false, TypeList<FirstLeft, LeftTail...>, TypeList<FirstRight, RightTail...>, TypeList<MergedElements...> >
{
typedef typename Merge< TypeList<FirstLeft, LeftTail...>, TypeList<RightTail... >, TypeList< MergedElements..., FirstRight > >::type type;
};

typedef typename MergeHelper< (L1::value < R1::value), TypeList<L1, Left...>, TypeList<R1, Right...>, TypeList<Merged...> >::type type;
};

// Takes a TypeList<T...> and sorts it via a merge sort:
template<typename List>
struct MergeSort;
template<>
struct MergeSort<TypeList<>>
{
typedef TypeList<> type;
};
template<typename T>
struct MergeSort<TypeList<T>>
{
typedef TypeList<T> type;
};
template<typename First, typename Second, typename... T>
struct MergeSort<TypeList<First, Second, T...>>
{
typedef Split<TypeList<First, Second, T...>> InitialSplit;
typedef typename MergeSort< typename InitialSplit::Left >::type Left;
typedef typename MergeSort< typename InitialSplit::Right >::type Right;
typedef typename Merge< Left, Right >::type type;
};

// Sorts a TypeList<T..>:
template<typename List>
struct Sort: MergeSort<List> {};

// Checks sorted TypeList<T...> SortedList for adjacent duplicate types
// return value is in value
template<typename SortedList>
struct Unique;

template<> struct Unique< TypeList<> >:std::true_type {};
template<typename T> struct Unique< TypeList<T> >:std::true_type {};

template<typename First, typename Second, typename... Tail>
struct Unique< TypeList< First, Second, Tail... > >
{
enum
{
value = (!std::is_same<First, Second>::value) &&
Unique< TypeList<Second, Tail...> >::value
};
};

// value is true iff there is a repeated type in Types...
template<typename... Types>
struct RepeatedType
{
typedef TypeList<Types...> MyListOfTypes;

typedef typename Sort< MyListOfTypes >::type MyListOfTypesSorted;
enum
{
value = !Unique< MyListOfTypesSorted >::value
};
};

// A struct that creates an rvalue trivial constructed type
// of any type requested.
struct ProduceRequestedType
{
template<typename Result>
operator Result() { return Result(); };
};

struct ExpressionFactory {
template<typename... T>
typename std::enable_if<
!RepeatedType<T...>::value,
UniqueExpression<T...>
>::type
build_expression(T...) const
{
return ProduceRequestedType();
};
template<typename... T>
typename std::enable_if<
RepeatedType<T...>::value,
RepeatedExpression<T...>
>::type
build_expression(T...) const
{
return ProduceRequestedType();
};
};

// Simple testing code for above:
int main()
{
auto foo1 = ExpressionFactory().build_expression( LabelName<'a'>(), LabelName<'b'>(), LabelName<'a'>() );
typedef decltype(foo1) foo1Type;
if (foo1Type::is_unique)
std::cout << "foo1 is unique\n";
else
std::cout << "foo1 is repeated\n";

auto foo2 = ExpressionFactory().build_expression( LabelName<'q'>(), LabelName<'a'>(), LabelName<'b'>(), LabelName<'d'>(), LabelName<'t'>(), LabelName<'z'>() );
typedef decltype(foo2) foo2Type;
if (foo2Type::is_unique)
std::cout << "foo2 is unique\n";
else
std::cout << "foo2 is repeated\n";
}

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

Как это компилируется на Intel?