从包中获取所有子包

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's 将转换为所需的 Pack<Types...>.

的 2^N 个子集

我下面的解决方案很长，我知道有一种比上面描述的非常机械的方法更优雅的方法。如果您想到了更好的计划（也许更短，因为它更递归或其他），请 post 您的想法，以便我可以接受你更好的计划，希望能写出一个更短的解决方案。如果您认为可能需要，我不希望您完整地写出您的解决方案一些时间（除非你想）。但目前，除了我所做的，我想不出其他方法。如果您想阅读，这是我当前的较长解决方案：

#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

关键是建立递推关系：

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

其中 w/ A 部分只是指将 A 添加到每个子集中。鉴于此，我们需要三个元函数：Plus，获取两个 Pack 的并集，Prefix，为 Pack 中的每个元素添加类型，最后, PowerSet。三个 Ps，如果你愿意的话。

按照复杂程度递增的顺序。 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<>>;
};

Answer 2

这是我的尝试：

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

Live example

Answer 3

这里的目标是创建一些普遍有用的工具，然后在尽可能少的行中解决 pow。通常有用的类型工具也不是那么笨重。

所以，首先是一个用于类型列表操作的库。

template<class...>struct types{using type=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;

将类型函数 Z 应用于列表的每个元素：

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;

部分模板应用：

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

采用 lhs，并在 rhs 上应用 Z<lhs, *>：

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

解决问题：

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

您可能只注意到一个 non-empty 结构 body。这是因为types有一个using type=types;body，其他人都偷了。

pow被递归定义为尾部的pow，union {{head} union each tail element}。终止案例处理空幂集元素。

live example

concat_t 过于强大，因为我们一次只需要追加 1 个元素。

apply_t 只应用一元函数，因为这样更简洁。但这确实意味着 expand_t 必须写入。你可以写一个和 expand_t 一样短的 apply_t，但是函数式编程中的部分函数应用是一个养成的好习惯。

我不得不将 partial 制作成我喜欢的大约 3 倍大，因为如果我不先在 struct 中解压缩然后再执行 using，clang 似乎会爆炸。

其中一个版本不依赖于为类型使用特定的包。它在几个点上爆炸了。

我希望有一个返回 template 的 using 语法。它会使 expand_t 没有用，因为 partial_z<concat_t, T0> 可能是一个 template，它在其参数前面加上 T0，而不是丑陋的 partial<concat_t, T0>::template apply_t。

Answer 4

使用Eric Niebler's Tiny Meta-Programming 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 接受一个列表列表和一个类型，并生成一个列表，其中包含每个输入列表和每个带有给定类型前缀的输入列表。然后计算幂集只是原始输入列表上 f 的 right fold。

从包中获取所有子包

Obtaining all subpacks from a pack

c++

templates

variadic-templates

c++11