コンパイル時の型の順列P（N、R）

Question

パックにすべての異なる型がある場合、パックのP（N、R）を計算するための作業コードを書いた。

PermutationN<2, P<int, char, bool>> 

P< P<int, char>, P<int, bool>, P<char, int>, P<char, bool>, P<bool, int>, P<bool, char> > 

になることです。しかし、繰り返し要素があるとき、私は間違った結果を取得しています。例えば、

PermutationN<2, P<int, int, char>> 

は

P< P<int, int>, P<int, char>, P<char, int> > 

はここですべての種類が異なる場合のための私の作業コードであるべきです。私はパックに繰り返しタイプがあるときに正しい結果を出すようにそれを適応させる方法に固執しています。どんな助けもありがとう。

#include <iostream> 
#include <type_traits> 

template <typename, typename> struct Merge; 

template <template <typename...> class P, typename... Ts, typename... Us> 
struct Merge<P<Ts...>, P<Us...>> { 
    using type = P<Ts..., Us...>; 
}; 

template <std::size_t N, typename Pack, typename Previous, typename... Output> struct PermutationNHelper; 

template <std::size_t N, template <typename...> class P, typename First, typename... Rest, typename... Prev, typename... Output> 
struct PermutationNHelper<N, P<First, Rest...>, P<Prev...>, Output...> : Merge< 
    typename PermutationNHelper<N-1, P<Prev..., Rest...>, P<>, Output..., First>::type, // P<Prev..., Rest...> are the remaining elements, thus ensuring that the next element chosen will not be First. The new Prev... is empty since we now start at the first element of P<Prev..., Rest...>. 
    typename PermutationNHelper<N, P<Rest...>, P<Prev..., First>, Output...>::type // Using P<Rest...> ensures that the next set of permutations will begin with the type after First, and thus the new Prev... is Prev..., First. 
> {}; 

template <std::size_t N, template <typename...> class P, typename Previous, typename... Output> 
struct PermutationNHelper<N, P<>, Previous, Output...> { 
    using type = P<>; 
}; 

template <template <typename...> class P, typename First, typename... Rest, typename... Prev, typename... Output> 
struct PermutationNHelper<0, P<First, Rest...>, P<Prev...>, Output...> { 
    using type = P<P<Output...>>; 
}; 

template <template <typename...> class P, typename Previous, typename... Output> 
struct PermutationNHelper<0, P<>, Previous, Output...> { 
    using type = P<P<Output...>>; 
}; 

template <typename Pack> struct EmptyPack; 

template <template <typename...> class P, typename... Ts> 
struct EmptyPack<P<Ts...>> { using type = P<>; }; 

template <std::size_t N, typename Pack> 
using PermutationN = typename PermutationNHelper<N, Pack, typename EmptyPack<Pack>::type>::type; 

// Testing 
template <typename...> struct P; 

int main() { 
    std::cout << std::is_same< 
     PermutationN<2, P<int, char, bool>>, 
     P< P<int, char>, P<int, bool>, P<char, int>, P<char, bool>, P<bool, int>, P<bool, char> > 
    >::value << '\n'; // true 

    std::cout << std::is_same< 
     PermutationN<2, P<int, int, int>>, 
     P< P<int, int>, P<int, int>, P<int, int>, P<int, int>, P<int, int>, P<int, int> > 
    >::value << '\n'; // true (but the answer should be P< P<int, int> >. 
} 

N.B.私は単純に上記を実行していないだけで出力からすべてのリピートパックを削除するエレガントな（そして効率的な）ソリューションを探しています（私はすでにそれを行うことができますが、そうでない醜い非効率的な解決策むしろ正しい出力を直接得ることができます。それは私が立ち往生している場所です。

Answer 1

基本的な考え方は、タイプの最初のリストを(type, count)ペアのリストに処理し、そこから作業することです。まず、いくつかのプリミティブ：

template<class, size_t> struct counted_type {}; 
template<class...> struct pack {}; 

私たちの表現はpackcounted_typeのSになるだろう。それを構築するために、我々はそれにタイプを追加できるようにする必要があります。

template<class T, class CT> struct do_push; 
template<class T, class...Ts, size_t... Is> 
struct do_push<T, pack<counted_type<Ts, Is>...>>{ 
    using type = std::conditional_t<std::disjunction_v<std::is_same<Ts, T>...>, 
     pack<counted_type<Ts, Is + (std::is_same_v<Ts, T>? 1 : 0)>...>, 
     pack<counted_type<Ts, Is>..., counted_type<T, 1>> 
     >; 
}; 
template<class T, class CT> using push = typename do_push<T, CT>::type; 

タイプがすでにある場合は、我々は数に1を追加します。それ以外の場合はcounted_type<T, 1>を追加します。

し、後でそれを使用する、我々はそれからタイプを削除できるようにする必要があります：

template<class T, class CT> struct do_pop; 
template<class T, class...Ts, std::size_t... Is> 
struct do_pop<T, pack<counted_type<Ts, Is>...>>{ 
    using type = remove<counted_type<T, 0>, 
         pack<counted_type<Ts, Is - (std::is_same_v<Ts, T>? 1 : 0)>...>>; 
}; 

template<class T, class CT> using pop = typename do_pop<T, CT>::type; 

remove<T, pack<Ts...>>は、それが存在する場合は、Ts...からTの最初のインスタンスを削除し、そして得られたパックを返します。 （Tが存在しない場合、パックは変更されずに返されます）。 （むしろ退屈な）実装は、読者の練習として残されています。

pushで、私たちは簡単なタイプのpackからpackcounted_typeのSを構築することができます。

template<class P, class CT = pack<> > 
struct count_types_imp { using type = CT; }; 

template<class CT, class T, class... Ts> 
struct count_types_imp<pack<T, Ts...>, CT> 
     : count_types_imp<pack<Ts...>, push<T, CT>> {}; 

template<class P> 
using count_types = typename count_types_imp<P>::type; 

は今、実際の実装は、通常、これはと1つのテンプレートで行うことができ

template<class T> struct identity { using type = T; }; 

template <std::size_t N, typename CT, typename = pack<> > struct PermutationNHelper; 

// Workaround for GCC's partial ordering failure 
template <std::size_t N, class CT, class> struct PermutationNHelper1; 

template <std::size_t N, class... Types, std::size_t... Counts, class... Current > 
struct PermutationNHelper1<N, pack<counted_type<Types, Counts>...>, pack<Current...>> { 
    // The next item can be anything in Types... 
    // We append it to Current... and pop it from the list of types, then 
    // recursively generate the remaining items 
    // Do this for every type in Types..., and concatenate the result. 
    using type = concat< 
     typename PermutationNHelper<N-1, pop<Types, pack<counted_type<Types, Counts>...>>, 
            pack<Current..., Types>>::type... 
     >; 
}; 


template <std::size_t N, class... Types, std::size_t... Counts, class... Current > 
struct PermutationNHelper<N, pack<counted_type<Types, Counts>...>, pack<Current...>> { 
    using type = typename std::conditional_t< 
        N == 0, 
        identity<pack<pack<Current...>>>, 
        PermutationNHelper1<N, pack<counted_type<Types, Counts>...>, 
              pack<Current...>> 
        >::type; 
    // Note that we don't attempt to evaluate PermutationNHelper1<...>::type 
    // until we are sure that N > 0 
}; 


template <std::size_t N, typename Pack> 
using PermutationN = typename PermutationNHelper<N, count_types<Pack>>::type; 

です2つの部分的な特殊化（1つはN> 0、もう1つはN == 0）ですが、GCCの部分的な順序付けはバグが多いので、私はconditionalで明示的にディスパッチします。実際にPermutationNHelper1のパック展開を評価するとNが0になるとひどく爆発するので、間違いなく間接指定して爆発を防ぐために、PermutationNHelper1という名前が付けられています。

concatは、Merge（よく、typename Merge<...>::type）の可変的なバージョンです。この実装は、読者の練習として残されています。