c++ - 使用迭代器和可变参数模板的笛卡尔积

Question

我正在尝试创建一个函数，以使用 STL 的样式生成可变数量的输入范围的笛卡尔积。我的基本格式是函数接受固定范围和输出范围的开始，然后是可变数量的双向输入迭代器。

template <
    typename BidirectionalIterator,
    typename OutputIterator,
    typename... Args
>
void cartesian_product(
    BidirectionalIterator first,
    BidirectionalIterator last,
    OutputIterator result,
    Args&&... args
);

我对 args 的想法是从中创建一个 tuple，然后遍历该 tuple 以提取元素。这需要我遵循几个基本步骤:

1. 从 args 生成一个 tuple
2. 取消引用新创建的元组中的每个迭代器
3. 按顺序递增 tuple 中的每个迭代器，以便我们获得范围内值的所有可能组合。

详细说明第 3 步:如果我们有两个集合 A = {0, 1} 和 B = {2, 3}，笛卡尔积 A x B = {(0, 2), (0, 3), (1, 2), (1, 3)}.

我可以像这样做第一步:

auto arg_tuple = std::make_tuple(std::forward<Args>(args)...);

第二步，我不太确定。我想我会以某种方式将 push_back 元素添加到临时元组，然后将 *result 设置为等于该临时元组。 ostream 实现这一点的方式给我带来了一些启发，所以我认为这可能会派上用场:

template <typename Tuple, typename T>
auto operator<<(const Tuple &lhs, const T &rhs)
    -> decltype(std::tuple_cat(lhs, std::make_tuple(rhs)))
{
    return std::tuple_cat(lhs, std::make_tuple(rhs));
}

第三步可能非常简单。我可以结合这样的东西:

template <typename T>
auto pre_increment(T &x) -> decltype(++x) {
    return ++x;
}

for_each 的 3,000 个实现之一用于此处的 tuple。

很可能我没有正确地利用 C++14 来做这件事。到目前为止，我的教育完全集中在 C++11 中难度较低的部分。

如果你想推荐我为此使用 boost::fusion，谢谢，但我宁愿不使用它。

Answer 1

在 C++17 中，我们得到 std::apply() .在该链接上找到了可能的 C++14 实现。然后我们可以为 tuple 实现 fmap 如下:

template <class Tuple, class F>
auto fmap(Tuple&& tuple, F f) {
    return apply([=](auto&&... args){
        return std::forward_as_tuple(f(std::forward<decltype(args)>(args))...);
    }, std::forward<Tuple>(tuple));
}

有了那个:

auto deref_all = fmap(iterators, [](auto it) -> decltype(auto) { return *it; });
auto incr_all = fmap(iterators, [](auto it) { return ++it; });