7

我正在为由任意数量的char标签参数化的表达式编写模板。

给定一个参数列表，工厂函数根据是否有两个相同类型的参数或它们是否唯一来返回不同类型的表达式。

一个具体的例子：假设这A是一个“可标记”的对象，其operator()重载以产生一个?Expression<...>. 让我们a, b, ...声明为标签LabelName<'a'>, LabelName<'b'>, ...。ThenA(a,b,c,d)会产生 a UniqueExpression<'a','b','c','d'>，而A(a,c,b,c)会产生 a RepeatedExpression<'a','c','b','c'>。

为了实现这一点，我必须用和定义?Expression的工厂函数。此外，必须级联到另一个，直到元程序完成对参数的递归并且最终确定返回类型。作为说明，我已经为工厂方法隔离了一个相当少的代码。autodecltypedecltypedecltype

template <typename... T> struct TypeList { };
template <char C> struct LabelName { };

template <typename... T> class UniqueExpression
{
    // Contains implementation details in actual code
};

template <typename... T> class RepeatedExpression
{
    // Contains implementation details in actual code
};

class ExpressionFactory {
private:
    template <char _C, typename... T, typename... _T>
    static UniqueExpression<T...>
    _do_build(TypeList<T...>,
              TypeList<LabelName<_C>>,
              TypeList<>,
              TypeList<_T...>)
    {
        return UniqueExpression<T...> ();
    }

    template <char _C, typename... T, typename... _T1, typename... _T2, typename... _T3>
    static RepeatedExpression<T...>
    _do_build(TypeList<T...>,
              TypeList<LabelName<_C>, _T1...>, 
              TypeList<LabelName<_C>, _T2...>,
              TypeList<_T3...>)

    {
        return RepeatedExpression<T...> ();
    }

    template <char _C1, char _C2, typename... T, typename... _T1, typename... _T2, typename... _T3>
    static auto
    _do_build(TypeList<T...>,
              TypeList<LabelName<_C1>, _T1...>, 
              TypeList<LabelName<_C2>, _T2...>,
              TypeList<_T3...>)
    -> decltype(_do_build(TypeList<T...>(),
                          TypeList<LabelName<_C1>, _T1...>(),
                          TypeList<_T2...>(),
                          TypeList<_T3..., LabelName<_C2>>()))
    {
        return _do_build(TypeList<T...>(),
                         TypeList<LabelName<_C1>, _T1...>(),
                         TypeList<_T2...>(),
                         TypeList<_T3..., LabelName<_C2>>());
    }

    template <char _C1, char _C2, typename... T, typename... _T1, typename... _T2>
    static auto
    _do_build(TypeList<T...>,
              TypeList<LabelName<_C1>, LabelName<_C2>, _T1...>, 
              TypeList<>,
              TypeList<LabelName<_C2>, _T2...>)
    -> decltype(_do_build(TypeList<T...>(),
                          TypeList<LabelName<_C2>, _T1...>(),
                          TypeList<_T2...>(),
                          TypeList<>()))
    {
        return _do_build(TypeList<T...>(),
                         TypeList<LabelName<_C2>, _T1...>(),
                         TypeList<_T2...>(),
                         TypeList<>());
    }

public:
    template <char C, typename... T>
    static auto
    build_expression(LabelName<C>, T...)
    -> decltype(_do_build(TypeList<LabelName<C>, T...>(),
                          TypeList<LabelName<C>, T...>(),
                          TypeList<T...>(),
                          TypeList<>()))
    {
        return _do_build(TypeList<LabelName<C>, T...>(),
                         TypeList<LabelName<C>, T...>(),
                         TypeList<T...>(),
                         TypeList<>());
    }
};

可以像这样在程序中调用工厂：（在实际程序中，有另一个重载的类operator()调用工厂）

int main()
{
    LabelName<'a'> a;
    LabelName<'b'> b;
    ...
    LabelName<'j'> j;

    auto expr = ExpressionFactory::build_expression(a,b,c,d,e,f,g,h,i,j);

    // Perhaps do some cool stuff with expr

    return 0;
}

上述代码按预期工作，并由 GCC 和 Intel 编译器正确编译。现在，我知道编译器会花费更多时间来执行递归模板推导，因为我会增加我使用的标签数量。

在我的计算机上，如果build_expression用一个参数调用，那么 GCC 4.7.1 平均需要大约 0.26 秒来编译。5 个参数的编译时间可延长至 0.29 秒左右，10 个参数的编译时间可延长至 0.62 秒。这都是完全合理的。

英特尔编译器的情况完全不同。ICPC 13.0.1 在 0.35 秒内编译单参数代码，编译时间对于最多四个参数几乎保持不变。在 5 个参数时，编译时间达到 12 秒，在 6 个参数时，编译时间超过 9600 秒（即超过 2 小时 40 分钟）。不用说，我还没有等待足够长的时间来找出编译七参数版本需要多长时间。

两个问题立刻浮现在脑海：

  • 英特尔编译器是否特别以递归编译速度慢而著称decltype？

  • 有没有办法以对编译器更友好的方式重写此代码以达到相同的效果？

4

1 回答 1

3

这是一个尝试。我没有对每个元素进行成对比较，而是对类型列表进行排序，然后使用脑死亡的独特算法来查看是否有任何重复项。

我在类型上实现了归并排序，因为它很有趣。可能在合理数量的参数上，一个简单的冒泡排序会更好。请注意，一些工作将使我们能够对长列表进行合并排序，并专门针对短列表进行冒泡排序（甚至插入排序）。我不适合编写模板快速排序。

这给了我一个编译时间布尔值，表示列表中是否有重复项。然后我可以使用 enable_if 来选择我要使用的重载。

请注意，您的解决方案涉及 n^2 层模板递归，在每个阶段，返回类型都需要评估 1 步更简单类的类型，然后返回的类型也需要相同！如果英特尔编译器记忆失败，那么您正在谈论指数级的工作量。

我用一些助手扩充了你的一些课程。我让你LabelName的 s 继承自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”。在做一些不平凡的事情时，给你的类型名起有意义的名字。

这如何在英特尔上编译？

于 2012-11-11T17:13:21.473 回答