7

任意の数のcharラベルでパラメーター化された式のテンプレートを作成しています。

引数リストを指定すると、ファクトリ関数は、同じ型の 2 つの引数があるかどうか、またはそれらが一意であるかどうかに応じて、異なる型の式を返します。

具体的な例:を生成するためAにオーバーロードされた「ラベル付け可能な」オブジェクトであるとします。ラベルとして宣言してみましょう。次に、を生成しますが、代わりに を生成します。operator()?Expression<...>a, b, ...LabelName<'a'>, LabelName<'b'>, ...A(a,b,c,d)UniqueExpression<'a','b','c','d'>A(a,c,b,c)RepeatedExpression<'a','c','b','c'>

?Expressionこれを実現するには、のファクトリー関数をautoとで定義する必要がありdecltypeました。さらに、メタプログラムが引数の再帰を終了し、戻り値の型が最終的に決定されるまで、decltype他のものにカスケードする必要があります。decltype実例として、ファクトリ メソッドのかなり最小限のコードを分離しました。

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は、 が 1 つの引数で呼び出された場合、GCC 4.7.1 のコンパイルには平均で約 0.26 秒かかります。コンパイル時間は、引数が 5 つの場合は約 0.29 秒、引数が 10 の場合は 0.62 秒になります。これはすべて完全に合理的です。

Intel コンパイラの場合は話が大きく異なります。ICPC 13.0.1 は 1 引数のコードを 0.35 秒でコンパイルし、コンパイル時間は最大 4 つの引数までほぼ一定です。引数が 5 つの場合、コンパイル時間は最大 12 秒になり、引数が 6 つの場合は、9600 秒を超えます (つまり、2 時間 40 分以上)。言うまでもなく、私は 7 引数バージョンのコンパイルにかかる時間を知るのに十分な時間待ちませんでした。

すぐに次の 2 つの質問が思い浮かびます。

  • Intel コンパイラは、特に再帰的なコンパイルが遅いことが知られていますdecltypeか?

  • おそらくコンパイラにとってより使いやすい方法で同じ効果を達成するために、このコードを書き直す方法はありますか?

4

1 に答える 1

3

ここでそれを突き刺します。各要素のペアごとの比較を行う代わりに、タイプのリストを並べ替えてから、脳死した独自のアルゴリズムを使用して、重複があるかどうかを確認します。

楽しかったので、型にマージソートを実装しました。おそらく、単純なバブルソートは、妥当な数の引数でうまく機能するでしょう。ちょっとした作業で、長いリストでマージ ソートを実行し、短いリストでバブル ソート (または挿入ソート) に特化できることに注意してください。テンプレートのクイックソートを書くつもりはありません。

これにより、リストに重複があるかどうかを示すコンパイル時のブール値が得られます。その後、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" を使用するのと同じです。自明ではないことをするときは、型名に意味のある名前を付けてください。

これはインテルでどのようにコンパイルされますか?

于 2012-11-11T17:13:21.473 に答える