PowerSet<Pack<Types...>>::type
是给出一个由所有子集组成的包组成的包Types...
(现在假设静态断言中的每个类型Types...
是不同的)。例如,
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>>
现在,我已经解决了这个练习并对其进行了测试,但是我的解决方案很长,希望听到一些更优雅的想法。我并不是要求任何人审查我的解决方案,而是建议一种新的方法,也许用一些伪代码勾勒出他们的想法。
如果你想知道,这就是我所做的:首先,我回忆起高中时的情况,一组 N 个元素有 2^N 个子集。每个子集对应于
N 位二进制数,例如001010...01(N 位长),其中 0 表示该元素在子集中,1 表示该元素在子集中
该元素不在子集中。因此 000...0 代表空子集,111...1 代表整个集合本身。
因此,使用(模板)序列 0,1,2,3,...2^N-1,我形成了 2^N 个索引序列,每个索引序列对应于
该序列中的整数,例如index_sequence 将对应于该序列中的 13。然后这 2^N 个索引序列中的每一个
将被转换为所需的 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();
}