从包中获取所有子包

Question

PowerSet<Pack<Types...>>::type是给出一个由所有子集形成的包组成的包Types...(现在假设静态断言,每个类型Types...都是不同的).例如,

PowerSet<Pack<int, char, double>>::type

是的

Pack<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,每个都对应于该序列中整数的二进制表示,例如index_sequence <1,1 ,0,1>将对应于该序列中的13.然后将那些2 ^ N index_sequence中的每一个转换为期望的2 ^ N个子集Pack<Types...>.

我的解决方案很长,我知道有一种比上面描述的机械方法更优雅的方法.如果你想到了一个更好的计划(也许更短,因为它更加递归或其他),请发表您的想法,以便我可以采取更好的计划,希望写出更短的解决方案.如果您认为可能需要一些时间(除非您愿意),我不希望您完整地写出您的解决方案.但是目前,我想不出比我做的更好的方式了.这是我目前的长期解决方案,如果你想阅读它:

#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();
}

Answer 1

这是我的尝试:

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...>>
{
};

实例

Answer 2

关键是要建立一个递归关系:

PowerSet of {A, B, C}
== (PowerSet of {B,C}) U (PowerSet of {B,C} w/ A)

其中w/ A部分仅仅指的是加入A到每一个子集.鉴于此,我们需要三个元函数:Plus,将两个Packs 的并集Prefix,添加一个类型到a中的每个元素Pack,最后,PowerSet.三P,如果你愿意的话.

按复杂程度递增.Plus把包装装在一起:

template <typename A, typename B> struct Plus;

template <typename... A, typename... B>
struct Plus<Pack<A...>, Pack<B...>> {
    using type = Pack<A..., B...>;
};

前缀只是用于Plus添加Pack<A>到所有内容:

template <typename A, typename P> struct Prefix;

template <typename A, typename... P>
struct Prefix<A, Pack<P...> >
{
    using type = Pack<typename Plus<Pack<A>, P>::type...>;
};

然后PowerSet是复发的直接翻译:

template <typename P> struct PowerSet;

template <typename T0, typename... T>
struct PowerSet<Pack<T0, T...>>
{
    using rest = typename PowerSet<Pack<T...>>::type;
    using type = typename Plus<rest,
                               typename Prefix<T0, rest>::type
                               >::type;
};

template <>
struct PowerSet<Pack<>>
{
    using type = Pack<Pack<>>;
};