具有转换的参数包的编译时高效 n 元笛卡尔积

Question

在上一个问题中，给出了有关如何计算参数包的 n 元笛卡尔积的解决方案（参见 , (and here 但对于元组）。基本上，我们考虑以下包装器：

template <class... Types>
struct pack {};

template <class... Packs>
struct pack_product {/* SOMETHING */}

template <class... Packs>
using pack_product_t = typename pack_product<Packs...>::type;

使得 pack_product_t<pack<A0, A1>, pack<B0, B1, B2>, pack<C0, C1>> 产生以下内容：

pack<
    pack<A0, B0, C0>, pack<A0, B0, C1>, 
    pack<A0, B1, C0>, pack<A0, B1, C1>,
    pack<A0, B2, C0>, pack<A0, B2, C1>, 
    pack<A1, B0, C0>, pack<A1, B0, C1>, 
    pack<A1, B1, C0>, pack<A1, B1, C1>,
    pack<A1, B2, C0>, pack<A1, B2, C1>, 
>;

（再次参见 and 的解决方案，即使我认为当输入包之一是空包时它们不能完全工作 pack<>）。这对应于集合 A×B×C={(a0, b0, c0), ..., (a1, b2, c1)} 的 n 元笛卡尔积（从集合论的角度来看，元组的集合）。

重要的一点是，其中一个棘手的部分是只生成两层包，而不是在结果中生成 n 层嵌套包（如 pack<pack<pack<A0, B0>, C0>>, ...>）。

现在我要做的是n元笛卡尔积的组合：

template <template <class> class Function, class... Packs>
struct pack_product_apply {
    using type = /* SOMETHING */
};

template <template <class> class Function, class... Packs>
using pack_product_apply_t = typename pack_product_apply<Function, Packs...>::type;

基本上计算：

pack<
    typename Function<pack<A0, B0, C0>>::type, typename Function<pack<A0, B0, C1>>::type, 
    typename Function<pack<A0, B1, C0>>::type, typename Function<pack<A0, B1, C1>>::type,
    typename Function<pack<A0, B2, C0>>::type, typename Function<pack<A0, B2, C1>>::type, 
    typename Function<pack<A1, B0, C0>>::type, typename Function<pack<A1, B0, C1>>::type, 
    typename Function<pack<A1, B1, C0>>::type, typename Function<pack<A1, B1, C1>>::type,
    typename Function<pack<A1, B2, C0>>::type, typename Function<pack<A1, B2, C1>>::type, 
>;

并且由于 SFINAE 而只是跳过不编译的元素：例如，如果带有 B1 的版本不提供有效的 ::type 结果将只是：

pack<
    typename Function<pack<A0, B0, C0>>::type, typename Function<pack<A0, B0, C1>>::type, 
    typename Function<pack<A0, B2, C0>>::type, typename Function<pack<A0, B2, C1>>::type, 
    typename Function<pack<A1, B0, C0>>::type, typename Function<pack<A1, B0, C1>>::type, 
    typename Function<pack<A1, B2, C0>>::type, typename Function<pack<A1, B2, C1>>::type, 
>;

输入类型函数的例子是：

template <class Pack> 
struct my_type_function;

template <class... Types> 
struct my_type_function<pack<Types...>>: std::common_type<Types...> {};

首先计算笛卡尔积，然后在其结果上应用函数是很简单的。但我有一种感觉（但我可能是错的）从编译器的角度来看它不是最优的。

问题：如何以编译器高效的方式实现pack_product_apply，在计算每个元素时，类型函数将“即时”应用乘积而不是先计算所有元素然后应用函数？

Answer 1

这适用于 O(1) 实例化深度

template<template<typename...> class F, int N, typename...>
struct fn_typelist {};

template<typename...>
struct typelist {};

template<template<typename...> class F, int N, typename... Ts>
typelist<fn_typelist<F, N, Ts>...> layered(typelist<Ts...>);

template<template<typename...> class F, typename... Ts, typename... Us>
auto operator+(fn_typelist<F, sizeof...(Ts) + sizeof...(Us), Ts...>&&,
               fn_typelist<F, sizeof...(Ts) + sizeof...(Us), Us...>&&)
    -> F<Ts..., Us...>;

template<template<typename...> class F, int N, typename... Ts, typename... Us>
auto operator+(const fn_typelist<F, N, Ts...>&,
               const fn_typelist<F, N, Us...>&)
    -> fn_typelist<F, N, Ts..., Us...>;

template<typename... Ts, typename... Us>
auto operator+(typelist<Ts...>, typelist<Us...>)
    -> typelist<Ts..., Us...>;

template<typename T, typename... Us>
auto operator*(typelist<T>, typelist<Us...>)
    -> typelist<decltype(T{} + Us{})...>;

template<typename... Ts, typename TL>
auto operator^(typelist<Ts...>, TL tl)
    -> decltype(((typelist<Ts>{} * tl) + ...));

template<template<typename...> class F, typename... TLs>
using product_apply_t = decltype((layered<F, sizeof...(TLs)>(TLs{}) ^ ...));

然后你使用 as

struct A0;
struct A1;
struct B0;
struct B1;
struct C0;
struct C1;
struct C2;

using t1 = typelist<A0, A1>;
using t2 = typelist<B0, B1>;
using t3 = typelist<C0, C1, C2>;

template<typename...>
struct fn {};

using p1 = product_apply_t<fn, t1, t2>;
using p2 = product_apply_t<fn, t1, t2, t3>;

using expect1 = typelist<fn<A0, B0>,
                         fn<A0, B1>,
                         fn<A1, B0>,
                         fn<A1, B1>>;

using expect2 = typelist<fn<A0, B0, C0>,
                         fn<A0, B0, C1>,
                         fn<A0, B0, C2>,
                         fn<A0, B1, C0>,
                         fn<A0, B1, C1>,
                         fn<A0, B1, C2>,
                         fn<A1, B0, C0>,
                         fn<A1, B0, C1>,
                         fn<A1, B0, C2>,
                         fn<A1, B1, C0>,
                         fn<A1, B1, C1>,
                         fn<A1, B1, C2>>;

static_assert(std::is_same_v<p1, expect1>);
static_assert(std::is_same_v<p2, expect2>);

其中 fn 可以与任何具有合适参数的 class 模板或模板别名交换。

这会实例化第一个 (n-1) 元笛卡尔积，然后在 n-ary 笛卡尔积上应用提供的元函数。不熟悉编译器，我不知道这是否会加快编译时间。

_{实现是神秘的，如果您想询问它，这可能意味着您应该坚持生产包和迭代。或提升。}

Answer 2

这确实是 Boost.Mp11 中的关键见解，您在这里提出的问题与其他问题实际上是同一个问题。

pack_product 正在取一堆 pack 的笛卡尔积并将它们全部变成 pack。那就是：

template <class... Packs>
using pack_product = mp_product<pack, Packs...>;

pack_product_apply 是一回事。或者实际上，pack_product 是 pack_product_apply 的特例，其中您应用于每个列表的函数是 pack:

template <template <class...> class F, class... Packs>
using pack_product_apply = mp_product<F, Packs...>;

也就是说pack_product_apply是mp_product.

现在，您的表述略有不同 - 您想要采用适用于类型列表 (F<L>) 的函数而不是适用于包 (F<Ts...>) 的函数。你仍然可以这样做，只是你需要将一些东西传递给首先对包进行分组的 mp_product （即首先应用 pack 然后 F）：

template <template <class> class F, class... Packs>
using pack_product_apply = mp_product_q<mp_compose<pack, F>, Packs...>;

具有转换的参数包的编译时高效 n 元笛卡尔积

Compile-time efficient n-ary cartesian product of parameter packs with a transformation

c++

cartesian-product

template-meta-programming

variadic-templates

c++20