PowerSet<Pack<Types...>>::type è quello di fornire un pacchetto costituito da pacchetti costituiti da tutti i sottoinsiemi di Types... (per ora assumere l'asserzione statica che ciascun tipo in Types... è distinto). Ad esempio,Ottenere tutti i subpacks da un pacchetto
PowerSet<Pack<int, char, double>>::type
è quello di essere
Pack<Pack<>, Pack<int>, Pack<char>, Pack<double>, Pack<int, char>, Pack<int, double>, Pack<char, double>, Pack<int, char, double>>
Ora, ho risolto questo esercizio e provato, ma la mia soluzione è molto lunga e vorrei sentire qualche idea più elegante. Non sto chiedendo a nessuno di rivedere la mia soluzione, ma suggerire del tutto un nuovo metodo, magari di abbozzare la loro idea con qualche pseudocodice.
Nel caso in cui volessi sapere, questo è quello che ho fatto: in primo luogo, ho ricordato dal liceo che un insieme di elementi N ha 2^N sottoinsiemi. Ogni sottoinsieme corrisponde a un numero binario a N cifre, ad es. 001010 ... 01 (N cifre lunghe), dove 0 significa che l'elemento si trova nel sottoinsieme e 1 significa che l'elemento non è nel sottoinsieme. Quindi 000 ... 0 rappresenterebbe il sottoinsieme vuoto e 111 ... 1 rappresenterebbe l'intero set stesso. Quindi usando la sequenza (modello) 0,1,2,3, ... 2^N-1, ho formato 2^N index_sequence, ciascuno corrispondente alla rappresentazione binaria degli interi in quella sequenza, ad es. index_sequence < 1,1,0,1> corrisponde a 13 di quella sequenza. Quindi ciascuno di questi 2^N index_sequence verrà convertito nei sottoinsiemi 2^N desiderati di Pack<Types...>.
La mia soluzione di seguito è piuttosto lunga, e so che esiste un metodo più elegante rispetto a quello molto meccanico descritto sopra. Se hai pensato a un piano migliore (forse anche più breve perché è più ricorsivo o altro), pubblica la tua idea in modo che io possa assumere il piano migliore, sperando di scrivere una soluzione più breve. Non mi aspetto che tu scriva la tua soluzione per intero se pensi che ci vorrà probabilmente un po 'di tempo (a meno che tu non voglia) . Ma al momento, non riesco a pensare a un altro modo rispetto a quello che ho fatto. Qui è il mio attuale soluzione piuttosto lunga nel caso in cui si vuole leggere:
#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();
}
'Ora, ho risolto questo esercizio e l'ho testato, ma la mia soluzione è molto lunga e vorrei sentire alcune idee più eleganti. Quindi penso che CodeReview possa essere una soluzione migliore. –
Ma non sto chiedendo a nessuno di rivedere la mia soluzione, ma suggerire del tutto un nuovo metodo. Voglio sentire un piano migliore e poi prenderlo da solo. Vedere alcuni pseudocodici che mostrano le loro idee potrebbero aiutare ancora meglio. So solo che c'è un modo migliore di sopra. Ho pubblicato solo la mia idea (e la soluzione) in modo che le persone possano pensare ad un'idea migliore. – prestokeys