可变参数模板的 N 元笛卡尔积

Question

我正在尝试计算可变参数模板的 n 元笛卡尔积，到目前为止我还没有找到适用于 n 元情况的优雅方法（一元和二元很容易，见下文）。

这是调查的当前状态。为了方便起见，我引入了一个 pack<Types...> 来存储可变参数模板。然后是一些实用函数和助手：

// Preamble
#include <iostream>
#include <type_traits> 

// Helper function to display the result
template <class...> void print() {std::cout << __PRETTY_FUNCTION__ << "\n";}

// Pack to hold variadic templates
template <class...> struct pack {};

// Sum of packs
template <class...> 
struct pack_sum;
// Sum of packs: single pack specialization
template <class... Types> 
struct pack_sum<pack<Types...>> {
    using type = pack<Types...>;
};
// Sum of packs: n-ary recursive specialization
template <class... Types1, class... Types2, class... Packs>
struct pack_sum<pack<Types1...>, pack<Types2...>, Packs...> {
    using type = typename pack_sum<pack<Types1..., Types2...>, Packs...>::type;
};

基于此，我可以介绍我的笛卡尔积（一元和二进制版本）：

// Cartesian product of packs
template <class...>
struct pack_product;
// Cartesian product of packs: single empty pack specialization
template <>
struct pack_product<pack<>> {
    using type = pack<>;
};
// Cartesian product of packs: empty pack specialization
template <class... Types2, class... Packs>
struct pack_product<pack<>, pack<Types2...>, Packs...> {
    using type = typename pack_product<pack<>, Packs...>::type;
};
// Cartesian product of packs: unary specialization
template <class... Types>
struct pack_product<pack<Types...>> {
    using type = pack<pack<Types>...>;
};
// Cartesian product of packs: binary specialization
template <class Type1, class... Types1, class... Types2>
struct pack_product<pack<Type1, Types1...>, pack<Types2...>> {
    using type = typename pack_sum<
        pack<pack<Type1, Types2>...>,
        typename pack_product<pack<Types1...>, pack<Types2...>>::type
    >::type;
};

我可以用它来测试：

// Test
int main(int argc, char* argv[]) {
    // Packs
    using empty_pack = pack<>;
    using char_pack = pack<signed char, char, unsigned char>;
    using int_pack = pack<int, unsigned int>;
    using float_pack = pack<float, double, long double>;
    // Tests
    print<typename pack_product<empty_pack>::type>();
    print<typename pack_product<char_pack>::type>();
    print<typename pack_product<empty_pack, char_pack>::type>();
    print<typename pack_product<char_pack, empty_pack>::type>();
    print<typename pack_product<char_pack, float_pack>::type>();
}

完整的功能代码在这里：https://godbolt.org/z/Pv15W95EK

输出：

typename pack_product<
    pack<signed char, char, unsigned char>, 
    pack<float, double, long double>
>::type

是：

pack<
    pack<signed char, float>, 
    pack<signed char, double>, 
    pack<signed char, long double>, 
    pack<char, float>, 
    pack<char, double>, 
    pack<char, long double>, 
    pack<unsigned char, float>, 
    pack<unsigned char, double>, 
    pack<unsigned char, long double> 
>

符合预期。

现在，问题：

我正在寻找 n 元版本，但它避免了嵌套包，因此：

pack_product<pack<A1, A2>, pack<B1, B2>, pack<C1, C2>>

给出以下结果：

pack<
    pack<A1, B1, C1>, pack<A1, B1, C2>, pack<A1, B2, C1>, pack<A1, B2, C2>,
    pack<A2, B1, C1>, pack<A2, B1, C2>, pack<A2, B2, C1>, pack<A2, B2, C2>
>

和不是某种：

pack<
    pack<A1, pack<B1, C1>>, pack<A1, pack<B1, C2>>, pack<A1, pack<B2, C1>>, pack<A1, pack<B2, C2>>,
    pack<A2, pack<B1, C1>>, pack<A2, pack<B1, C2>>, pack<A2, pack<B2, C1>>, pack<A2, pack<B2, C2>>,
>

问题： 在搜索时，我发现非常丑陋的版本似乎可以工作，但我想要尽可能干净和优雅的东西，以尽量减少辅助结构和专业化的数量。如果 n 元专业化涵盖了二进制版本，那是一个加号，但我不确定这是否可能。非常欢迎任何帮助:)

注意： 我正在寻找的东西的可能专业化是，但这只是一个建议：

template <class Type1, class... Types1, class... Types2, class... Pack>
struct pack_product<pack<Type1, Types1...>, pack<Types2...>, Pack...> {
     using type = /* THE THING I'M LOOKING FOR */
};

Answer 1

NOTE: A possible specialization for the thing I'm looking for would be, but that is just a suggestion:

对于n-ary版本，你只需要递归二进制版本，因为pack_product<a, b, c>等同于pack_product<pack_product<a, b>, c>

// Cartesian product of packs: n-ary specialization
template <class Type1, class... Types1, class... Types2, class... Pack>
struct pack_product<pack<Type1, Types1...>, pack<Types2...>, Pack...> {
  using type = typename pack_product<typename pack_sum<
    pack<pack<Type1, Types2>...>,
    typename pack_product<pack<Types1...>, pack<Types2...>>::type
  >::type, Pack...>::type;
};

但是，这会产生

{pack<pack<pack<signed char, float>, int>, pack<pack<signed char, float>, unsigned int>, ...}

为了移除嵌套包，可以对 binary/n-arg 专业化

执行部分专业化

// Cartesian product of packs: binary specialization for nested packs
template <class... Types, class... Types1, class... Types2>
struct pack_product<pack<pack<Types...>, Types1...>, pack<Types2...>> {
  using type = typename pack_sum<
    pack<pack<Types..., Types2>...>,
    typename pack_product<pack<Types1...>, pack<Types2...>>::type
  >::type;
};

Demo

可变参数模板的 N 元笛卡尔积

N-ary cartesian product of variadic templates

c++

recursion

cartesian-product

template-meta-programming

c++20