在编译时的类型的排列P（N，R） [英] Permutation P(N,R) of types in compile time
问题描述
<$ c>我已经为包装计算P（N，R） $ c> PermutationN< 2，P< int，char，bool>>
为
P < P< int，char>，P< int，bool>，P< char，int>，P< char，bool> ;, P< bool，int& >
但是当有重复元素时，我得到错误的结果。例如，
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 ...>类P，类型名... Ts，类型名... Us>
struct Merge< P< Ts ...>，P< Us ...>> {
using type = P< Ts ...，Us ...> ;;
}
template< std :: size_t N，typename Pack，typename上一个，typename ...输出> struct PermutationNHelper;
template< std :: size_t N，template< typename ...> class P，typename First，typename ... Rest，typename ... Prev，typename ...输出>
struct PermutationNHelper< N，P< First，Rest ...>，P< Prev ...>，Output ...& ：Merge<
typename PermutationNHelper< N-1，P< Prev ...，Rest ...>，P，输出...，First> :: type，// P< Prev ...， Rest ...>是剩余元素，从而确保选择的下一个元素不是First。新的Prev ...是空的，因为我们现在从P
> {};
template< std :: size_t N，template< typename ...>类P，类型名称上一个，类型名称...输出>
struct PermutationNHelper< N，P<>，Previous，Output ...> {
using type = P<> ;;
}
template< template< typename ...> class P，typename First，typename ... Rest，typename ... Prev，typename ...输出>
struct PermutationNHelper< 0，P< First，Rest ...>，P< Prev ...>，Output ...& {
using type = P< P< Output ...>> ;;
}
template< template< typename ...>类P，类型名称上一个，类型名称...输出>
struct PermutationNHelper< 0，P<>，Previous，Output ...> {
using type = P< P< Output ...>> ;;
}
template< typename Pack> struct EmptyPack;
template< template< typename ...>类P，类型名... Ts>
struct EmptyPack< P< Ts ...>> {using type = P<> };
template< std :: size_t N，typename Pack>
使用PermutationN = typename PermutationNHelper< N，Pack，typename EmptyPack< Pack> :: type> :: type;
//测试
模板< 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& >
> :: value<< '\\\
'; // 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& >
> :: value<< '\\\
'; // true（但答案应该是P >。
}
$ b我正在寻找一个优雅（和高效）的解决方案，不简单地执行上面的，然后只是从输出中删除所有重复包（我已经可以做，但拒绝写一个这样丑陋，
解决方案是一个非常有效的解决方案，它可以解决问题的核心问题，
基本思想是将初始的类型列表处理成（type，count）对的列表，然后从那里开始工作。首先， p>
template< class，size_t> struct counted_type {};
template< class ...> struct pack {};
我们的代表将是 pack 要创建它，我们需要能够为它添加一个类型：
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> ...>> {
使用type = std :: conditional_t< std :: disjunction_v< std :: is_same< Ts，T& ; ...>，
pack< counting_type< Ts，Is +（std :: is_same_v< Ts，T> 1：0）> ...> ;,
pack< counting_type< Ts，Is> ...，counting_type< T，1>
> ;;
}
template< class T，class CT>使用push = typename do_push< T，CT> :: type;
如果类型已经存在，否则我们会附加 counted_type< T，1> 。
可以从中删除类型：
模板< 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& ，Is - （std :: is_same_v 1：0）> ...>>
}
template< class T，class CT> using pop = typename do_pop< T，CT> :: type;
remove< T，pack< Ts ...> / code>从 Ts ... 中删除 T 的第一个实例，如果存在，则结果包（如果 T 不存在，则包将不更改地返回）。
通过 push ，我们可以轻松地构建一个 pack of calculate_type / p>
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;
现在，实际的实现是
template< class T> struct identity {using type = T; };
template< std :: size_t N，typename CT，typename = pack<> > struct PermutationNHelper;
// GCC部分排序失败的解决方法
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 ...> {
//下一个项目可以是Types ...
//我们将它追加到Current ...并从类型列表中弹出，然后
//递归生成剩余的项目
//为Types ...中的每个类型执行此操作，并连接结果。
using type = concat<
typename PermutationNHelper< N-1，pop< Types，pack< counted_type< Types，Counts> ...>>，
pack< Current ...，Types> ..
> ;;
}
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;
//注意，我们不试图评估PermutationNHelper1< ...> :: type
//直到我们确定N> 0
};
template< std :: size_t N，typename Pack>
使用PermutationN = typename PermutationNHelper< N，count_types< Pack>> :: type;
通常这可以在一个模板中使用两个部分专门化来完成（一个用于N> 0，另一个用于N == 0），但是GCC的部分顺序是有错误的，所以我明确调用 conditional 。实际上评估 PermutationNHelper1 中的包扩展等于0将会爆炸，所以令人难以想象的名为<$ c $
concat 引入一个额外级别的间接引用$ c>只是您的合并（well， typename Merge< ...> :: type ）。该实现留给读者作为练习。
I've written a working code for computing P(N,R) for packs when the pack has all different types, e.g.
PermutationN<2, P<int, char, bool>>
is to be
P< P<int, char>, P<int, bool>, P<char, int>, P<char, bool>, P<bool, int>, P<bool, char> >
But when there are repeat elements, I'm getting the wrong results. For example,
PermutationN<2, P<int, int, char>>
should be
P< P<int, int>, P<int, char>, P<char, int> >
Here is my working code for when all the types are different. I'm stuck on how to adapt it so that it gives correct results when there are repeated types in the pack. Any help would be appreciated.
#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. I'm looking for an elegant (and efficient) solution that does not simply carry out the above and then merely remove all repeat packs from the output (I can already do that but refuse to write up such an ugly, inefficient solution that does not tackle the heart of the problem), but rather get the correct output directly. That's where I'm stuck.
The basic idea is to process the initial list of types into a list of (type, count) pairs, and work from there. First, some primitives:
template<class, size_t> struct counted_type {};
template<class...> struct pack {};
Our representation is going to be a pack of counted_types. To build it, we need to be able to add a type to it:
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;
If the type is already there, we add 1 to the count; otherwise we append a counted_type<T, 1>.
And to use it later, we'll need to be able to remove a type from it:
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...>> removes the first instance of T from Ts..., if it exists, and returns the resulting pack (if T doesn't exist, the pack is returned unchanged). The (rather boring) implementation is left as an exercise to the reader.
With push we can easily build a pack of counted_types from a pack of types:
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;
Now, the actual implementation is
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;
Normally this can be done in one template with two partial specializations (one for N > 0 and one for N == 0), but GCC's partial ordering is buggy, so I dispatched explicitly with conditional. Actually evaluating the pack expansion in PermutationNHelper1 with N equal to 0 will explode horribly, so the unimaginatively named PermutationNHelper1 is introduced to provide an extra level of indirection and prevent the explosion.
concat is just a variadic version of your Merge (well, typename Merge<...>::type). The implementation is left as an exercise to the reader.
这篇关于在编译时的类型的排列P（N，R）的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
