Retrieving all subpackages from a package

Question

PowerSet<Pack<Types...>>::type is a package consisting of packages formed by all subsets of Types... (now suppose the static statement that each type from Types... different). For instance,

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

should be

 Pack<Pack<>, Pack<int>, Pack<char>, Pack<double>, Pack<int, char>, Pack<int, double>, Pack<char, double>, Pack<int, char, double>> 

Now I have solved this exercise and tested it, but my decision is very long and I would like to hear more elegant ideas. I do not ask anyone to look at my solution, but I propose a new method as a whole, perhaps to outline my idea with some pseudocode.

If you would like to know, this is what I did: firstly, I recalled from high school that a set of N elements has 2 ^ N subsets. Each subset corresponds to an N-bit binary number, for example. 001010 ... 01 (N digits), where 0 means that the element is in a subset, and 1 means that the element is not in the subset. Thus, 000 ... 0 will represent an empty subset, and 111 ... 1 will represent the entire set. Thus, using the (template) sequence 0,1,2,3, ... 2 ^ N-1, I formed 2 ^ N index_sequence, each of which corresponds to the binary representation of integers in this sequence, for example. index_sequence <1,1,0,1> will correspond to 13 of this sequence. Then, each of these 2 ^ N index_sequence will be converted to the required 2 ^ N subsets of Pack<Types...> .

My solution below is quite long, and I know that there is a more elegant method than the one described above. If you thought of a better plan (perhaps shorter because it is more recursive or some other), please post your idea so that I can accept your better plan, hoping to write a shorter solution. I do not expect you to write your decision completely if you think it will probably take some time (if you do not want to). But at present, I cannot think of anything other than what I did. Here is my current long solution if 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 and 1 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, ie 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, eg 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

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

Living example

Answer 2

The key is to establish a recurrence relation:

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

where the part of w/ A simply means adding A to each subset. Given this, we need three metafiles: Plus , to accept the union of the two Pack s, Prefix , to add a type to each item in the Pack and finally PowerSet . Three P s if you want.

In increasing order of difficulty. Plus just sticks the packages together:

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

The prefix simply uses Plus to add Pack<A> to everything:

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

And then PowerSet is a direct translation of the repetition:

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

Answer 3

Cheating with Eric Nibler Tiny Metaprogram Library ( DEMO ):

 template <typename...Ts> using Pack = meta::list<Ts...>; template <typename Sets, typename Element> using f = meta::concat< Sets, meta::transform< Sets, meta::bind_back<meta::quote<meta::push_front>, Element> >>; template <typename List> using PowerSet = meta::foldr<List, Pack<Pack<>>, meta::quote<f>>; 

f takes a list of lists and one type and creates a list containing a list of input lists, and each of the input lists with the specified type. The syntax calculation is just the right shift f compared to the original input list.

Answer 4

The goal here is to create some useful tools and then pow solution in a few lines. Usually a useful type of tool is not so bulky.

So, first a library for manipulating a list of types.

 template<class...>struct types{using type=types;}; 

Concatenated lists of two types:

 template<class types1,class types2>struct concat; template<class...types1,class...types2>struct concat< types<types1...>, types<types2...> >:types<types1...,types2...>{}; template<class A,class B>using concat_t=typename concat<A,B>::type; 

Apply a function of type Z to each element of the list:

 template<template<class...>class Z, class types> struct apply; template<template<class...>class Z, class...Ts> struct apply<Z,types<Ts...>>: types< Z<Ts>... > {}; template<template<class...>class Z, class types> using apply_t=typename apply<Z,types>::type; 

partial use of templates:

 template<template<class...>class Z, class T> struct partial { template<class... Ts> struct apply:Z<T,Ts...> {}; template<class... Ts> using apply_t=typename apply<Ts...>::type; }; 

take lhs and apply Z<lhs, *> to rhs:

 template<template<class, class...>class Z, class lhs, class types> using expand_t=apply_t<partial<Z,lhs>::template apply_t, types>; 

solve the problem of:

 template<class T>struct pow; // fail if not given a package template<>struct pow<types<>>:types<types<>>{}; template<class T>using pow_t=typename pow<T>::type; template<class T0,class...Ts>struct pow<types<T0,Ts...>>: concat_t< expand_t< concat_t, types<T0>, pow_t<types<Ts...>> >, pow_t<types<Ts...>> > {}; 

you can notice only one non-empty body of the structure. This is because types has a body using type=types; and everyone else just steals it.

pow defined recursively as tail pow, union {{head} joins each tail element}. The trailing register processes the empty power gain element.

living example

concat_t is overly powerful since we only need to add one element at a time.

apply_t only applies unary functions because it is cleaner. But that means expand_t to be written. You can write apply_t , which is about as short as expand_t includes, but a partial function application in functional programming is a good habit.

I needed to make partial about 3 times bigger than what I liked, since clang seems to explode if I don't decompress into a struct first and then do using .

One version did not depend on the use of a specific package for types. It exploded at several points.

I would like to have a using syntax that returned template . This would make expand_t not useful, since partial_z<concat_t, T0> could be a template that adds T0 to its argument instead of partial<concat_t, T0>::template apply_t , which is ugly.