PowerSet<Pack<Types...>>::type ist, eine Packung von Packungen von allen Untergruppen von Types... (vorerst übernimmt die statische Behauptung, daß jeder Typ in Types... verschieden ist) gebildet, die aus zu geben. Zum Beispielalle subpacks aus einem Pack erhalten
PowerSet<Pack<int, char, double>>::type
ist
Pack<Pack<>, Pack<int>, Pack<char>, Pack<double>, Pack<int, char>, Pack<int, double>, Pack<char, double>, Pack<int, char, double>>
Jetzt sein, habe ich diese Übung gelöst und getestet, aber meine Lösung ist sehr lang und möchte einige elegantere Ideen hören. Ich bitte niemanden, meine Lösung zu überprüfen, sondern schlage eine neue Methode vor, vielleicht skizziere ich ihre Idee mit einem Pseudocode.
Wenn Sie wissen wollten, das ist was ich getan habe: Erstens erinnerte ich mich von der High School, dass ein Satz von N Elementen 2^N Untermengen hat. Jede Teilmenge entspricht einer N-stelligen Binärzahl, z. 001010 ... 01 (N Ziffern lang), wobei 0 bedeutet, dass das Element in der Teilmenge ist und 1 bedeutet, dass das Element nicht in der Teilmenge ist. Somit würde 000 ... 0 die leere Teilmenge darstellen, und 111 ... 1 würde die gesamte Menge selbst repräsentieren. Unter Verwendung der (Muster-) Sequenz 0, 1, 2, 3, ... 2^N-1 bildete I 2^N Indexsequenz, die jeweils der binären Darstellung der ganzen Zahlen in dieser Sequenz, z. index_sequence < 1,1,0,1> würde 13 aus dieser Sequenz entsprechen. Dann wird jeder dieser 2^N index_sequences in die gewünschten 2^N Teilmengen von Pack<Types...> umgewandelt.
Meine Lösung unten ist ziemlich lang, und ich weiß, dass es eine elegantere Methode als die sehr mechanische oben beschriebene gibt. Wenn Sie an einen besseren Plan gedacht haben (vielleicht auch kürzer, weil er eher rekursiv ist oder was auch immer), schreiben Sie bitte Ihre Idee, damit ich Ihren besseren Plan annehmen kann, in der Hoffnung, eine kürzere Lösung auszuarbeiten. Ich erwarte nicht, dass du deine Lösung komplett aussprichst, wenn du denkst, dass es wahrscheinlich eine Weile dauern wird (außer du willst es). Aber momentan kann ich mir keinen anderen Weg vorstellen als das, was ich getan habe. Hier ist meine aktuelle longish Lösung, falls Sie wollen, es zu lesen:
#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();
}
'Nun, ich habe diese Übung gelöst und getestet, aber meine Lösung ist sehr lang und würde gerne etwas elegantere Ideen hören. Dann denke ich, dass CodeReview besser passt. –
Aber ich bitte niemanden, meine Lösung zu überprüfen, sondern eine neue Methode vorzuschlagen. Ich möchte von einem besseren Plan hören und es dann selbst übernehmen. Einige Pseudocode zu sehen, die ihre Ideen zeigen, würde noch besser helfen. Ich weiß nur, dass es einen besseren Weg als oben gibt. Ich habe nur meine Idee (und Lösung) gepostet, damit die Leute an eine bessere Idee denken können. – prestokeys