从包中获取所有子文件包 [英] Obtaining all subpacks from a pack

问题描述

PowerSet< Pack< Types ...>> :: type 是给出一个由 Types ... （现在假设静态断言 Types ... 中的每个类型都是不同的）。例如，

  PowerSet< Pack< int，char，double>> :: type 
  
 
 
 
是
  Pack<>，Pack< int>，Pack< char>，Pack< double>，Pack< int，char> ;, Pack< int，double> ;, Pack< char，double> ;, Pack< int，char，double> ;。 
  
 
 
现在，我已经解决了这个练习并测试了它，但我的解决方案很长，听到一些更优雅的想法。我不要求任何人审查我的解决方案，但建议一个新的方法，或许草绘他们的想法与一些伪代码。
 
 
 
如果你想知道，这是我做了什么：首先，我从高中回忆一组N元素有2 ^ N个子集。每个子集对应于
一个N位二进制数，例如001010 ... 01（N个数字长），其中0表示该元素在子集中，1表示
元素不在子集中。因此，000 ... 0将表示空子集，111 ... 1将表示整个集合本身。 
所以使用（模板）序列0,1,2,3，... 2 ^ N-1，我形成了2 ^ N index_sequence's，每个对应于
整数的二进制表示序列index_sequence< 1,1,0,1>将对应于来自该序列的13。然后，那些2 ^ N index_sequence的
中的每一个将被转换为 Pack< Types ...> 的期望的2 ^ N个子集。
 
 
 
我的解决方案相当长，我知道有一个更优雅的方法，而不是上面描述的机械。 
如果你想过一个更好的计划（也许更短，因为它是递归或其他），请张贴你的想法，以便我可以承担
你更好的计划，希望写出一个更短的解。我不希望你写出你的解决方案全部，如果你认为它可能需要
一些时间（除非你想）。但目前，我不能想到另一种方式，而不是我做了。这里是我现在的longish解决方案，如果你想读它：
  #include< iostream& 
 #include< cmath> 
 #include< typeinfo> 
 
 // SubsetFromBinaryDigits< P< Types ...> ;, Is ...> :: type给出P< Types ...&其中1取类型，0不取类型。两个包的大小必须相同。 
 //例如，SubsetFromBinaryDigits< Pack< int，double，char>，1,0,1> :: type给出Pack< int，char> ;. 
 
 template< typename，typename，int ...> struct SubsetFromBinaryDigitsHelper; 
 
 template< template< typename ...>类P，类型名...累加，int ...是> 
 struct SubsetFromBinaryDigitsHelper< P<>，P< Accumulated ...>，Is ...> {
 using type = P< Accumulated ...> ;; 
}; 
 
 template< template< typename ...> class P，typename First，typename ... Rest，typename ... Accumulated，int FirstInt，int ... RestInt> 
 struct SubsetFromBinaryDigitsHelper< P< First，Rest ...>，P< Accumulated ...>，FirstInt，RestInt ...& ：
 std :: conditional< FirstInt == 0，
 SubsetFromBinaryDigitsHelper< P< Rest ...>，P< Accumulated ...> Restint ...>，
 SubsetFromBinaryDigitsHelper< P< Rest ...>，P< Accumulated ...，First>，RestInt ...& 
> :: type {}; 
 
 template< typename，int ...> struct SubsetFromBinaryDigits; 
 
 template< template< typename ...> class P，typename ... Types，int ... Is> 
 struct SubsetFromBinaryDigits< P< Types ...>，Is ...> ：SubsetFromBinaryDigitsHelper< P< Types ...>，P<，Is ...> {}; 
 
 // struct NSubsets< P< Types ...>，IntPacks ...> :: type是一个包包，每个内包是由IntPacks形成的子集。 
 //例如，NSubsets< Pack  // Pack< Pack< char，long，float，Blob，short>，Pack< char，long，float，Blob>，Pack< int，char，long，float，Blob> > 
 
 template< typename，typename，typename ...> struct NSubsetsHelper; 
 
 template< template< typename ...>类P，类型名...类型，类型名...累积> 
 struct NSubsetsHelper< P< Types ...>，P< Accumulated ...>> {
 using type = P< Accumulated ...> ;; 
}; 
 
 template< template< typename ...>类P，类型名...类型，类型名...累积，模板< int ...> class Z，int ... Is，typename ... Rest> 
 struct NSubsetsHelper< P< Types ...>，P< Accumulated ...>，Z< Is ...& ：
 NSubsetsHelper< P< Types ...>，P< Accumulated ...，typename SubsetFromBinaryDigits< P< Types ...> ;, Is ...> :: type> > {}; 
 
 template< typename，typename ...> struct NSubsets; 
 
 template< template< typename ...>类P，类型名...类型，类型名... IntPacks> 
 struct NSubsets< P< Types ...>，IntPacks ...> ：NSubsetsHelper< P< Types ...>，P< Intpacks ...> {}; 
 
 //现在，给定具有N种类型的包，我们将index_sequence< 0,1,2，...，2 ^ N>到一个2 ^ N index_sequence包的包，其中每个
 // index_sequence包的0和1形成整数的二进制表示。例如，如果N = 2，则我们有
 // Pack< index_sequence< 0,0>，index_sequence< 0,1>，index_sequence< 1,0>，index_sequence< 1,1>从这些，我们可以得到
 //功率集，即原始包的所有子集的集合。 
 
 template< int N，int Exponent，int PowerOfTwo> 
 struct LargestPowerOfTwoUpToHelper {
 using type = typename std :: conditional<（PowerOfTwo> N），
 std :: integral_constant< int，Exponent> ;, 
 LargestPowerOfTwoUpToHelper > :: type; 
 static const int value = type :: value; 
}; 
 
模板< int N> 
 struct LargestPowerOfTwoUpTo：std :: integral_constant< int，LargestPowerOfTwoUpToHelper< N，-1,1> :: value> {}; 
 
 constexpr int power（int base，int exponent）{
 return std :: pow（base，exponent）; 
} 
 
 template< int ...> struct index_sequence {}; 
 
 //例如，PreBinaryIndexSequence< 13> :: type是index_sequence< 0,2,3> ;,因为13 = 2 ^ 3 + 2 ^ 2 + 2 ^ 0。 
 template< int N，int ...累计> 
 struct PreBinaryIndexSequence {//可以使用另一个帮助器，因为LargestPowerOfTwoUpToHelper< N，-1,1> ::值被使用两次。 
使用type = typename PreBinaryIndexSequence< N-power（2，LargestPowerOfTwoUpToHelper< N，-1> :: value），LargestPowerOfTwoUpToHelper< N，-1,1 :: value，Accumulated ...& ：类型; 
}; 
 
 template< int ... Accumulated> 
 struct PreBinaryIndexSequence< 0，Accumulated ...> {
 using type = index_sequence< Accumulated ...> ;; 
}; 
 
 //例如，BinaryIndexSequenceHelper< index_sequence<>，index_sequence< 0,2,3>，0,7> :: type是index_sequence< 1,0,1,1,0 ，0,0,0> （第一个索引的位置为0，最后一个索引的位置为7）。 
 template< typename，typename，int，int> struct BinaryIndexSequenceHelper; 
 
 template< template< int ...> class Z，int ... Accumulated，int First，int ... Rest，int Count，int MaxCount> 
 struct BinaryIndexSequenceHelper< Z< Accumulated ...>，Z< First，Rest ...>，Count，MaxCount> ：std :: conditional< First == Count，
 BinaryIndexSequenceHelper< Z< Accumulated ...，1>，Z< Rest ...> ;, Count + 1，MaxCount> ;, 
 BinaryIndexSequenceHelper< Z< ; Accumulated ...，0>，Z< First，Rest ...>，Count + 1，MaxCount> 
> :: type {}; 
 
 //当输入包被清空，但Count仍然小于MaxCount时，使用0填充acccumator包的其余部分。 
 template< template< int ...>类Z，int ...累加，int Count，int MaxCount> 
 struct BinaryIndexSequenceHelper< Z< Accumulated ...>，Z<，Count，MaxCount> ：BinaryIndexSequenceHelper< Z< Accumulated ...，0>，Z<，Count + 1，MaxCount> {}; 
 
 template< template< int ...> class Z，int ... Accumulated，int MaxCount> 
 struct BinaryIndexSequenceHelper< Z< Accumulated ...>，Z<>，MaxCount，MaxCount> {
 using type = Z< Accumulated ...> ;; 
}; 
 
 //最后，BinaryIndexSequence< N>是使用index_sequence的N的二进制表示，例如。 BinaryIndexSequence< 13,7>是index_sequence< 1,0,1,1,0,0,0> ;. 
 template< int N，int NumDigits> 
使用BinaryIndexSequence = typename BinaryIndexSequenceHelper< index_sequence<>，typename PreBinaryIndexSequence< N> :: type，0，NumDigits& 
 
 //现在定义make_index_sequence< N>为index_sequence< 0,1,2，...，N-1> ;. 
 template< int N，int ... Is> 
 struct make_index_sequence_helper：make_index_sequence_helper< N-1，N-1，Is ...> {}; // make_index_sequence_helper< N-1，N-1，Is ...>是从make_index_sequence_helper< N-3，N-3，N-2，N-1，Is ...导出的make_index_sequence_helper< N-2，N-2，N-1，Is ...&从...的索引，其从make_index_sequence_helper< 0,0,1,2，...，N-2，N-1，Is ...& 
 
 template< int ... Is> 
 struct make_index_sequence_helper< 0，Is ...> {
 using type = index_sequence< Is ...> ;; 
}; 
 
模板< int N> 
 using make_index_sequence = typename make_index_sequence_helper< N> :: type; 
 
 //最后，准备定义PowerSet本身。 
 template< typename，typename> struct PowerSetHelper; 
 
 template< template< typename ...> class P，typename ... Types，template< int ...> class Z，int ... Is> 
 struct PowerSetHelper< P< Types ...>，Z< Is ...>> ：NSubsets< P< Types ...>，BinaryIndexSequence< Is，sizeof ...（Types）> ...> {}; 
 
 template< typename> struct PowerSet; 
 
 template< template< typename ...>类P，类型名...类型> 
 struct PowerSet< P< Types ...>> ：PowerSetHelper< P< Types ...>，make_index_sequence< power（2，sizeof ...（Types））> {}; 
 
 // ---------------------------------------- -------------------------------------------------- -------------------------------------------------- --- 
 //测试
 
模板< typename ...> struct Pack {}; 
 
 template< typename Last> 
 struct Pack< Last> {
 static void print（）{std :: cout<< typeid（Last）.name（）<< std :: endl;} 
}; 
 
 template< typename首先，typename ... Rest> 
 struct Pack< First，Rest ...> {
 static void print（）{std :: cout<< typeid（First）.name（）<< ''; Pack< Rest ...> :: print（）;} 
}; 
 
 template< int Last> 
 struct index_sequence< Last> {
 static void print（）{std :: cout<<最后< std :: endl;} 
}; 
 
 template< int First，int ... Rest> 
 struct index_sequence< First，Rest ...> {
 static void print（）{std :: cout<<第一<< ''; index_sequence< Rest ...> :: print（）;} 
}; 
 
 int main（）{
 PowerSet< Pack< int，char，double> 
 powerSet.print（）; 
} 
  
 
 
解决方案
 p> 
 
 
 模板< typename，typename> struct Append; 
 
 template< typename ... Ts，typename T> 
 struct Append< Pack< Ts ...>，T> 
 {
使用type = Pack< Ts ...，T> ;; 
}; 
 
 template< typename，typename T = Pack< Pack<>>> 
 struct PowerPack 
 {
使用type = T; 
}; 
 
 template< typename T，typename ... Ts，typename ... Us> 
 struct PowerPack< Pack< T，Ts ...>，Pack< Us ...> 
：PowerPack< Pack< Ts ...>，Pack< Us ...，typename Append< Us，T> :: type ...> 
 {
}; 
  
  活动示例  
 
PowerSet<Pack<Types...>>::type is to give a pack consisting of packs formed by all subsets of Types... (for now assume the static assertion that every type in Types... are distinct).  For example,
PowerSet<Pack<int, char, double>>::type
is to be
Pack<Pack<>, Pack<int>, Pack<char>, Pack<double>, Pack<int, char>, Pack<int, double>, Pack<char, double>, Pack<int, char, double>>
Now, I've solved this exercise and tested it, but my solution is very long and would like to hear some more elegant ideas.  I'm not asking anyone to review my solution, but suggest a new method altogether, perhaps sketch their idea with some pseudocode.

In case you wanted to know, this is what I did:  First, I recalled from high school that a set of N elements has 2^N subsets.  Each subset corresponds to
an N-digit binary number, e.g. 001010...01 (N digits long), where 0 means that the element is in the subset and 1 means that
the element is not in the subset.  Thus 000...0 would represent the empty subset, and 111...1 would represent the entire set itself.
So using the (template) sequence 0,1,2,3,...2^N-1, I formed 2^N index_sequence's, each corresponding to the binary representation of the
integers in that sequence, e.g. index_sequence<1,1,0,1> would correspond to 13 from that sequence.  Then each of those 2^N index_sequence's
will be converted to the desired 2^N subsets of Pack<Types...>.

My solution below is quite long, and I know that there is a more elegant method than the very mechanical one described above.
If you've thought of a better plan (perhaps shorter too because it is more recursive or whatever), please post your idea so that I can take on
your better plan, hoping to write out a shorter solution.  I don't expect you to write out your solution in full if you think it will probably take
some time (unless you want to).  But currently, I can't think of another way than what I've done.  Here is my current longish solution in case you want to read it:
#include <iostream>
#include <cmath>
#include <typeinfo>

// SubsetFromBinaryDigits<P<Types...>, Is...>::type gives the sub-pack of P<Types...> where 1 takes the type and 0 does not take the type.  The size of the two packs must be the same.
// For example, SubsetFromBinaryDigits<Pack<int, double, char>, 1,0,1>::type gives Pack<int, char>.

template <typename, typename, int...> struct SubsetFromBinaryDigitsHelper;

template <template <typename...> class P, typename... Accumulated, int... Is>
struct SubsetFromBinaryDigitsHelper<P<>, P<Accumulated...>, Is...> {
    using type = P<Accumulated...>;
};

template <template <typename...> class P, typename First, typename... Rest, typename... Accumulated, int FirstInt, int... RestInt>
struct SubsetFromBinaryDigitsHelper<P<First, Rest...>, P<Accumulated...>, FirstInt, RestInt...> :
    std::conditional<FirstInt == 0,
        SubsetFromBinaryDigitsHelper<P<Rest...>, P<Accumulated...>, RestInt...>,
        SubsetFromBinaryDigitsHelper<P<Rest...>, P<Accumulated..., First>, RestInt...>
    >::type {};

template <typename, int...> struct SubsetFromBinaryDigits;

template <template <typename...> class P, typename... Types, int... Is>
struct SubsetFromBinaryDigits<P<Types...>, Is...> : SubsetFromBinaryDigitsHelper<P<Types...>, P<>, Is...> {};

// struct NSubsets<P<Types...>, IntPacks...>::type is a pack of packs, with each inner pack being the subset formed by the IntPacks.
// For example, NSubsets< Pack<int, char, long, Object, float, double, Blob, short>, index_sequence<0,1,1,0,1,0,1,1>, index_sequence<0,1,1,0,1,0,1,0>, index_sequence<1,1,1,0,1,0,1,0> >::type will give
// Pack< Pack<char, long, float, Blob, short>, Pack<char, long, float, Blob>, Pack<int, char, long, float, Blob> >

template <typename, typename, typename...> struct NSubsetsHelper;

template <template <typename...> class P, typename... Types, typename... Accumulated>
struct NSubsetsHelper<P<Types...>, P<Accumulated...>> {
    using type = P<Accumulated...>;
};

template <template <typename...> class P, typename... Types, typename... Accumulated, template <int...> class Z, int... Is, typename... Rest>
struct NSubsetsHelper<P<Types...>, P<Accumulated...>, Z<Is...>, Rest...> :
    NSubsetsHelper<P<Types...>, P<Accumulated..., typename SubsetFromBinaryDigits<P<Types...>, Is...>::type>, Rest...> {};

template <typename, typename...> struct NSubsets;

template <template <typename...> class P, typename... Types, typename... IntPacks>
struct NSubsets<P<Types...>, IntPacks...> : NSubsetsHelper<P<Types...>, P<>, IntPacks...> {};

// Now, given a pack with N types, we transform index_sequence<0,1,2,...,2^N> to a pack of 2^N index_sequence packs, with the 0's and 1's of each
// index_sequence pack forming the binary representation of the integer.  For example, if N = 2, then we have
// Pack<index_sequence<0,0>, index_sequence<0,1>, index_sequence<1,0>, index_sequence<1,1>>.  From these, we can get the
// power set, i.e. the set of all subsets of the original pack.

template <int N, int Exponent, int PowerOfTwo>
struct LargestPowerOfTwoUpToHelper {
    using type = typename std::conditional<(PowerOfTwo > N),
        std::integral_constant<int, Exponent>,
        LargestPowerOfTwoUpToHelper<N, Exponent + 1, 2 * PowerOfTwo>
    >::type;
    static const int value = type::value;
};

template <int N>
struct LargestPowerOfTwoUpTo : std::integral_constant<int, LargestPowerOfTwoUpToHelper<N, -1, 1>::value> {};

constexpr int power (int base, int exponent) {
    return std::pow (base, exponent);
}

template <int...> struct index_sequence {};

// For example, PreBinaryIndexSequence<13>::type is to be index_sequence<0,2,3>, since 13 = 2^3 + 2^2 + 2^0.
template <int N, int... Accumulated>
struct PreBinaryIndexSequence {  // Could use another helper, since LargestPowerOfTwoUpToHelper<N, -1, 1>::value is being used twice.
    using type = typename PreBinaryIndexSequence<N - power(2, LargestPowerOfTwoUpToHelper<N, -1, 1>::value), LargestPowerOfTwoUpToHelper<N, -1, 1>::value, Accumulated...>::type;
};

template <int... Accumulated>
struct PreBinaryIndexSequence<0, Accumulated...> {
    using type = index_sequence<Accumulated...>;
};

// For example, BinaryIndexSequenceHelper<index_sequence<>, index_sequence<0,2,3>, 0, 7>::type is to be index_sequence<1,0,1,1,0,0,0,0> (the first index with position 0, and the last index is position 7).
template <typename, typename, int, int> struct BinaryIndexSequenceHelper;

template <template <int...> class Z, int... Accumulated, int First, int... Rest, int Count, int MaxCount>
struct BinaryIndexSequenceHelper<Z<Accumulated...>, Z<First, Rest...>, Count, MaxCount> : std::conditional<First == Count,
        BinaryIndexSequenceHelper<Z<Accumulated..., 1>, Z<Rest...>, Count + 1, MaxCount>,
        BinaryIndexSequenceHelper<Z<Accumulated..., 0>, Z<First, Rest...>, Count + 1, MaxCount>
    >::type {};

// When the input pack is emptied, but Count is still less than MaxCount, fill the rest of the acccumator pack with 0's.
template <template <int...> class Z, int... Accumulated, int Count, int MaxCount>
struct BinaryIndexSequenceHelper<Z<Accumulated...>, Z<>, Count, MaxCount> : BinaryIndexSequenceHelper<Z<Accumulated..., 0>, Z<>, Count + 1, MaxCount> {};

template <template <int...> class Z, int... Accumulated, int MaxCount>
struct BinaryIndexSequenceHelper<Z<Accumulated...>, Z<>, MaxCount, MaxCount> {
    using type = Z<Accumulated...>;
};

// At last, BinaryIndexSequence<N> is the binary representation of N using index_sequence, e.g. BinaryIndexSequence<13,7> is index_sequence<1,0,1,1,0,0,0>.
template <int N, int NumDigits>
using BinaryIndexSequence = typename BinaryIndexSequenceHelper<index_sequence<>, typename PreBinaryIndexSequence<N>::type, 0, NumDigits>::type;

// Now define make_index_sequence<N> to be index_sequence<0,1,2,...,N-1>.
template <int N, int... Is>
struct make_index_sequence_helper : make_index_sequence_helper<N-1, N-1, Is...> {};  // make_index_sequence_helper<N-1, N-1, Is...> is derived from make_index_sequence_helper<N-2, N-2, N-1, Is...>, which is derived from make_index_sequence_helper<N-3, N-3, N-2, N-1, Is...>, which is derived from ... which is derived from make_index_sequence_helper<0, 0, 1, 2, ..., N-2, N-1, Is...>

template <int... Is>
struct make_index_sequence_helper<0, Is...> {
    using type = index_sequence<Is...>;
};

template <int N>
using make_index_sequence = typename make_index_sequence_helper<N>::type;

// Finally, ready to define PowerSet itself.
template <typename, typename> struct PowerSetHelper;

template <template <typename...> class P, typename... Types, template <int...> class Z, int... Is>
struct PowerSetHelper<P<Types...>, Z<Is...>> : NSubsets< P<Types...>, BinaryIndexSequence<Is, sizeof...(Types)>... > {};

template <typename> struct PowerSet;

template <template <typename...> class P, typename... Types>
struct PowerSet<P<Types...>> : PowerSetHelper<P<Types...>, make_index_sequence<power(2, sizeof...(Types))>> {};

// -----------------------------------------------------------------------------------------------------------------------------------------------
// Testing

template <typename...> struct Pack {};

template <typename Last>
struct Pack<Last> {
    static void print() {std::cout << typeid(Last).name() << std::endl;}
};

template <typename First, typename ... Rest>
struct Pack<First, Rest...> {
    static void print() {std::cout << typeid(First).name() << ' ';  Pack<Rest...>::print();}
};

template <int Last>
struct index_sequence<Last> {
    static void print() {std::cout << Last << std::endl;}
};

template <int First, int ... Rest>
struct index_sequence<First, Rest...> {
    static void print() {std::cout << First << ' ';  index_sequence<Rest...>::print();}
};

int main() {
    PowerSet<Pack<int, char, double>>::type powerSet;
    powerSet.print();
}

解决方案
Here's my attempt:
template<typename,typename> struct Append;

template<typename...Ts,typename T>
struct Append<Pack<Ts...>,T>
{
    using type = Pack<Ts...,T>;
};

template<typename,typename T=Pack<Pack<>>>
struct PowerPack
{
    using type = T;
};

template<typename T,typename...Ts,typename...Us>
struct PowerPack<Pack<T,Ts...>,Pack<Us...>>
    : PowerPack<Pack<Ts...>,Pack<Us...,typename Append<Us,T>::type...>>
{
};
Live example

                        
这篇关于从包中获取所有子文件包的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！