c++ - 在输入向量的笛卡尔积中创建第 n 个元素的元组

Question

我有一个 python 函数，它返回多个输入数组的笛卡尔积中的第 n 个元素

def prod(n, arrs):
    out = []

    for i,arr in enumerate(arrs):
        denom = numpy.prod([ len(p) for p in arrs[i+1:] ], dtype=int)
        idx = n // denom % len(arr)
        out.append( arr[idx] )

    return out

这很好用：

a = [ 1000, 1100, 1200, 1300, 1400 ]
b = [ 1.0, 1.5, 2.0, 2.5, 3.0, 3.5 ]
c = [ -2, -1, 0, 1, 2 ]

for n in range(20, 30):
    i = prod(n, [a, b, c])
    print(n, i)

[1000, 3.0, -2]
[1000, 3.0, -1]
[1000, 3.0, 0]
[1000, 3.0, 1]
[1000, 3.0, 2]
[1000, 3.5, -2]
[1000, 3.5, -1]
[1000, 3.5, 0]
[1000, 3.5, 1]
[1000, 3.5, 2]

现在我想把它翻译成 C++（最大标准 C++-17）

template<typename... Ts>
auto prod(std::size_t n, const std::vector<Ts>&... vs) 
    -> std::tuple<const std::decay_t<typename std::vector<Ts>::value_type>&...>
{
    // template magic here
}

有人可以帮助我使用上述公式构建元组所需的模板魔法吗？

标签： c++c++17template-meta-programmingcartesian-product

Answer 1

首先，为了简单起见，让我们自动推断函数的返回类型。

接下来，索引序列很整洁。有了他们，就可以做到。

使用 C++20，我们可以从 lambda 序列中获取索引。在此之前，我们需要一个额外的功能。

最后，我们必须从最后开始创建索引，要么存储索引，然后以相反的顺序使用它们，要么反转生成的元组。

template <class T, std::size_t... Ns>
static auto prod_impl(std::size_t n, T tuple, std::index_sequence<Ns...>) {
    auto f = [&](auto N){ auto r = n % N; n /= N; return r; };
    auto x = std::forward_as_tuple(std::get<(sizeof...(Ns)) - Ns - 1>(tuple)[f(std::get<(sizeof...(Ns)) - Ns - 1>(tuple).size())]...);
    return std::forward_as_tuple(std::get<(sizeof...(Ns)) - Ns - 1>(x)...);
}

template<class... Ts>
auto prod(std::size_t n, const std::vector<Ts>&... vs) {
    return prod_impl(n, std::forward_as_tuple(vs...), std::make_index_sequence<sizeof...(vs)>());
}

使用索引数组的内部函数的更简单替代方案：

template <class T, std::size_t... Ns>
static auto prod_impl(std::size_t n, T tuple, std::index_sequence<Ns...>) {
    auto f = [&](auto N){ auto r = n % N; n /= N; return r; };
    std::size_t Is[] = { f(std::get<sizeof...(Ns) - Ns - 1>(tuple).size())... , 0};
    return std::forward_as_tuple(std::get<Ns>(tuple)[sizeof...(Ns) - Ns - 1]...);
}