別のvariadicパラメータパックに基づいてvariadicパックの収縮を見つける

Question

静的多次元配列縮小フレームワークで作業していますが、説明するのがやや難しい問題が発生しましたが、私はベストを尽くします。私たちは今、私たちは、私は今、その署名すべき機能contractionを持ってIndices

template<int ... Idx> 
struct Indices {} 

と呼ばれる別のクラスを持っている

Array<double> scalar; 
Array<double,4> vector_of_4s; 
Array<float,2,3> matrix_of_2_by_3; 
// and so on 

としてインスタンス化することができ

template<typename T, int ... dims> 
class Array {} 

N次元配列のクラスがあるとし次のようになります

template<T, int ... Dims, int ... Idx, 
typename std::enable_if<sizeof...(Dims)==sizeof...(Idx),bool>::type=0> 
Array<T,apply_to_dims<Dims...,do_contract<Idx...>>> 
contraction(const Indices<Idx...> &idx, const Array<T,Dims...> &a) 

私はここで構文を取得していないかもしれませんが、返されたArrayは、Indicesというエントリに基づいたディメンションを持っています。 contractionが実行できるものの例を挙げておきます。このコンテキストでは、縮小を意味します。インデックスリスト内のパラメータが等しいの次元が削除されていることに注意してください。

auto arr = contraction(Indices<0,0>, Array<double,3,3>) 
// arr is Array<double> as both indices contract 0==0 

auto arr = contraction(Indices<0,1>, Array<double,3,3>) 
// arr is Array<double,3,3> as no contraction happens here, 0!=1 

auto arr = contraction(Indices<0,1,0>, Array<double,3,4,3>) 
// arr is Array<double,4> as 1st and 3rd indices contract 0==0 

auto arr = contraction(Indices<0,1,0,7,7,2>, Array<double,3,4,3,5,5,6>) 
// arr is Array<double,4,6> as (1st and 3rd, 0==0) and (4th and 5th, 7==7) indices contract 

auto arr = contraction(Indices<10,10,2,3>, Array<double,5,6,4,4> 
// should not compile as contraction between 1st and 2nd arguments 
// requested but dimensions don't match 5!=6 

// The parameters of Indices really do not matter as long as 
// we can identify contractions. They are typically expressed as enums, I,J,K... 

だから、本質的に、両方とも同じサイズでなければならないIdx...とDims...所与、Idx...の値そのチェックは、それらが発生する位置を取得し、Dims...に対応するエントリ（位置）を取り外し、等しいです。これは基本的にtensor contraction ruleです。配列収縮の

ルール：

1. 指標のパラメータの数や配列の次元/ランクが同じである必要があり、すなわちsizeof...(Idx)==sizeof...(Dims)
2. 一対一がありますIdxとDimsの場合、つまり、Indices<0,1,2>とArray<double,4,5,6>の場合、0は4に、1は5とにそれぞれ割り当てられますは6にマップされます。
3. Idxに同じ/等しい値がある場合、我々はIndices<0,0,3>とArray<double,4,4,6>を有する場合Dimsの対応する寸法は、例えば、消えるべきである意味、収縮を意味し、0==0及びこれらの値がどのているにマップ対応する寸法例えば、Indices<0,0,3>とArray<double,4,5,6>が不可能である、4と4両方が消滅する必要があり、Idxが同じ値を有する場合に得られた配列は、Array<double,6>
4. であるべきであるが、対応するDimsは、コンパイル時エラーがトリガされるべきであり、一致しません4!=5と同様に、Indices<0,1,0>4!=6とすることはできません。
5. 異なる次元の配列では収縮が起こりません。たとえば、Array<double,4,5,6>はどのような方法でも収縮することはできません。
6. 複数のペア、トリプレット、四つ組など、例えばIndices<0,0,0,0,1,1,4,3,3,7,7,7>ため、限りも一致対応DimsとしてIdxに許可された入力配列がArray<double,2,2,2,2,3,3,6,2,2,3,3,3>た所与、Array<double,6>に収縮あろう。

この機能を実現するには、私のメタプログラムの知識はそれほどのものではありませんが、私が正しい方向に私を誘導するという目的を明確にしたかったと思います。

Answer 1

これは混乱ですが、あなたがしたいことをしていると思います。これにはかなり単純化がありますが、これはテストに合格する最初のパスです。これは収縮を実装するのではなく、そのタイプを決定するだけであることに注意してください。それがあなたが必要としていないものならば、私は事前に謝罪します。ここで

#include <type_traits> 

template <std::size_t...> 
struct Indices {}; 

template <typename, std::size_t...> 
struct Array {}; 

// Count number of 'i' in 'rest...', base case 
template <std::size_t i, std::size_t... rest> 
struct Count : std::integral_constant<std::size_t, 0> 
{}; 

// Count number of 'i' in 'rest...', inductive case 
template <std::size_t i, std::size_t j, std::size_t... rest> 
struct Count<i, j, rest...> : 
    std::integral_constant<std::size_t, 
          Count<i, rest...>::value + ((i == j) ? 1 : 0)> 
{}; 

// Is 'i' contained in 'rest...'? 
template <std::size_t i, std::size_t... rest> 
struct Contains : 
    std::integral_constant<bool, (Count<i, rest...>::value > 0)> 
{}; 


// Accumulation of counts of indices in all, base case 
template <typename All, typename Remainder, 
      typename AccIdx, typename AccCount> 
struct Counts { 
    using indices = AccIdx; 
    using counts = AccCount; 
}; 

// Accumulation of counts of indices in all, inductive case 
template <std::size_t... all, std::size_t i, std::size_t... rest, 
      std::size_t... indices, std::size_t... counts> 
struct Counts<Indices<all...>, Indices<i, rest...>, 
       Indices<indices...>, Indices<counts...>> 
    : std::conditional<Contains<i, indices...>::value, 
         Counts<Indices<all...>, Indices<rest...>, 
           Indices<indices...>, 
           Indices<counts...>>, 
         Counts<Indices<all...>, Indices<rest...>, 
           Indices<indices..., i>, 
           Indices<counts..., 
             Count<i, all...>::value>>>::type 
{}; 

// Get value in From that matched the first value of Idx that matched idx 
template <std::size_t idx, typename Idx, typename From> 
struct First : std::integral_constant<std::size_t, 0> 
{}; 
template <std::size_t i, std::size_t j, std::size_t k, 
      std::size_t... indices, std::size_t... values> 
struct First<i, Indices<j, indices...>, Indices<k, values...>> 
    : std::conditional<i == j, 
         std::integral_constant<std::size_t, k>, 
         First<i, Indices<indices...>, 
          Indices<values...>>>::type 
{}; 

// Return whether all values in From that match Idx being idx are tgt 
template <std::size_t idx, std::size_t tgt, typename Idx, typename From> 
struct AllMatchTarget : std::true_type 
{}; 
template <std::size_t idx, std::size_t tgt, 
      std::size_t i, std::size_t j, 
      std::size_t... indices, std::size_t... values> 
struct AllMatchTarget<idx, tgt, 
         Indices<i, indices...>, Indices<j, values...>> 
    : std::conditional<i == idx && j != tgt, std::false_type, 
         AllMatchTarget<idx, tgt, Indices<indices...>, 
             Indices<values...>>>::type 
{}; 

/* Generate the dimensions, given the counts, indices, and values */ 
template <typename Counts, typename Indices, 
      typename AllIndices, typename Values, typename Accum> 
struct GenDims; 

template <typename A, typename V, typename R> 
struct GenDims<Indices<>, Indices<>, A, V, R> { 
    using type = R; 
}; 
template <typename T, std::size_t i, std::size_t c, 
      std::size_t... counts, std::size_t... indices, 
      std::size_t... dims, typename AllIndices, typename Values> 
struct GenDims<Indices<c, counts...>, Indices<i, indices...>, 
       AllIndices, Values, Array<T, dims...>> 
{ 
    static constexpr auto value = First<i, AllIndices, Values>::value; 
    static_assert(AllMatchTarget<i, value, AllIndices, Values>::value, 
        "Index doesn't correspond to matching dimensions"); 
    using type = typename GenDims< 
     Indices<counts...>, Indices<indices...>, 
     AllIndices, Values, 
     typename std::conditional<c == 1, 
            Array<T, dims..., value>, 
            Array<T, dims...>>::type>::type; 
}; 

/* Put it all together */ 
template <typename I, typename A> 
struct ContractionType; 

template <typename T, std::size_t... indices, std::size_t... values> 
struct ContractionType<Indices<indices...>, Array<T, values...>> { 
    static_assert(sizeof...(indices) == sizeof...(values), 
        "Number of indices and dimensions do not match"); 
    using counts = Counts<Indices<indices...>, 
          Indices<indices...>, 
          Indices<>, Indices<>>; 
    using type = typename GenDims<typename counts::counts, 
            typename counts::indices, 
            Indices<indices...>, Indices<values...>, 
            Array<T>>::type; 
}; 

static_assert(std::is_same<typename 
       ContractionType<Indices<0, 0>, Array<double, 3, 3>>::type, 
       Array<double>>::value, ""); 
static_assert(std::is_same<typename 
       ContractionType<Indices<0, 1>, Array<double, 3, 3>>::type, 
       Array<double, 3, 3>>::value, ""); 
static_assert(std::is_same<typename 
       ContractionType<Indices<0, 1, 0>, Array<double, 3, 4, 3>>::type, 
       Array<double, 4>>::value, ""); 
static_assert(std::is_same<typename 
       ContractionType<Indices<0, 1, 0, 7, 7, 2>, 
       Array<double, 3, 4, 3, 5, 5, 6>>::type, 
       Array<double, 4, 6>>::value, ""); 

// Errors appropriately when uncommented 
/* static_assert(std::is_same<typename */ 
/*    ContractionType<Indices<10,10, 2, 3>, */ 
/*    Array<double, 5,6,4,4>>::type, */ 
/*    Array<double>::value, ""); */ 

はここで何が起こっているかの説明を、以下：

• まず私はCounts、ユニークインデックス（Counts::indices）と各インデックスがに表示された回数のリストを使用して、生成します配列（Counts::counts）。
• 次に、私はインデックスを歩き、Countsから数えます。そして、各インデックスについて、カウントが1ならば、私は値を累積して再帰します。さもなければ、私は累積された値を渡して再帰します。

static_assertはGenDimsであり、一致するすべてのディメンションが同じであることを確認します。

Answer 2

実際のチェックを行うconstexpr機能の束は：

// is ind[i] unique in ind? 
template<size_t N> 
constexpr bool is_uniq(const int (&ind)[N], size_t i, size_t cur = 0){ 
    return cur == N ? true : 
      (cur == i || ind[cur] != ind[i]) ? is_uniq(ind, i, cur + 1) : false; 
} 

// For every i where ind[i] == index, is dim[i] == dimension? 
template<size_t N> 
constexpr bool check_all_eq(int index, int dimension, 
          const int (&ind)[N], const int (&dim)[N], size_t cur = 0) { 
    return cur == N ? true : 
      (ind[cur] != index || dim[cur] == dimension) ? 
       check_all_eq(index, dimension, ind, dim, cur + 1) : false; 
} 

// if position i should be contracted away, return -1, otherwise return dim[i]. 
// triggers a compile-time error when used in a constant expression on mismatch. 
template<size_t N> 
constexpr int calc(size_t i, const int (&ind)[N], const int (&dim)[N]){ 
    return is_uniq(ind, i) ? dim[i] : 
      check_all_eq(ind[i], dim[i], ind, dim) ? -1 : throw "dimension mismatch"; 
} 

今、私たちは-1 Sを取り除くための方法が必要です：

template<class Ind, class... Inds> 
struct concat { using type = Ind; }; 
template<int... I1, int... I2, class... Inds> 
struct concat<Indices<I1...>, Indices<I2...>, Inds...> 
    : concat<Indices<I1..., I2...>, Inds...> {}; 

// filter out all instances of I from Is..., 
// return the rest as an Indices  
template<int I, int... Is> 
struct filter 
    : concat<typename std::conditional<Is == I, Indices<>, Indices<Is>>::type...> {}; 

は、それらを使用します。

template<class Ind, class Arr, class Seq> 
struct contraction_impl; 

template<class T, int... Ind, int... Dim, size_t... Seq> 
struct contraction_impl<Indices<Ind...>, Array<T, Dim...>, std::index_sequence<Seq...>>{ 
    static constexpr int ind[] = { Ind... }; 
    static constexpr int dim[] = { Dim... }; 
    static constexpr int result[] = {calc(Seq, ind, dim)...}; 

    template<int... Dims> 
    static auto unpack_helper(Indices<Dims...>) -> Array<T, Dims...>; 

    using type = decltype(unpack_helper(typename filter<-1, result[Seq]...>::type{})); 
}; 


template<class T, int ... Dims, int ... Idx, 
typename std::enable_if<sizeof...(Dims)==sizeof...(Idx),bool>::type=0> 
typename contraction_impl<Indices<Idx...>, Array<T,Dims...>, 
          std::make_index_sequence<sizeof...(Dims)>>::type 
contraction(const Indices<Idx...> &idx, const Array<T,Dims...> &a); 

を

make_index_sequenceを除くすべてがC++ 11です。あなたはそれについてのすばらしい実装を見つけることができます。