使用迭代器和Variadic模板的笛卡尔积

Question

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

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

我的想法args是我从中做出一个tuple,然后我遍历它tuple以提取元素.这需要我遵循几个基本步骤:

1. 做一个tuple来自args
2. 取消引用新创建的每个迭代器 tuple
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;
}

在这里有3000个实现中for_each的一个tuple.

可能的是,我没有正确地利用C++ 14.到目前为止,我的教育完全依赖于C++ 11中较不困难的部分.

如果你很想推荐我使用boost::fusion它,谢谢,但我宁愿不使用它.

Answer 1

这是我想出的：

#include <iostream>
#include <tuple>
#include <vector>

template <typename T, typename B>
bool increment(const B& begins, std::pair<T,T>& r) {
  ++r.first;
  if (r.first == r.second) return true;
  return false;
}
template <typename T, typename... TT, typename B>
bool increment(const B& begins, std::pair<T,T>& r, std::pair<TT,TT>&... rr) {
  ++r.first;
  if (r.first == r.second) {
    r.first = std::get<std::tuple_size<B>::value-sizeof...(rr)-1>(begins);
    return increment(begins,rr...);
  }
  return false;
}

template <typename OutputIterator, typename... Iter>
void cartesian_product(
  OutputIterator out,
  std::pair<Iter,Iter>... ranges
) {
  const auto begins = std::make_tuple(ranges.first...);
  for (;;) {
    out = { *ranges.first... };
    if (increment(begins, ranges...)) break;
  }
}

struct foo {
  int i;
  char c;
  float f;
};

int main(int argc, char* argv[]) {

  std::vector<int> ints { 1, 2, 3 };
  std::vector<char> chars { 'a', 'b', 'c' };
  std::vector<float> floats { 1.1, 2.2, 3.3 };

  std::vector<foo> product;

  cartesian_product(
    std::back_inserter(product),
    std::make_pair(ints.begin(), ints.end()),
    std::make_pair(chars.begin(), chars.end()),
    std::make_pair(floats.begin(), floats.end())
  );

  for (const auto& x : product)
    std::cout << x.i << ' ' << x.c << ' ' << x.f << std::endl;

}

该cartesian_product函数的签名与您的稍有不同，但编写包装器应该很简单。

由于您传入的范围可能具有不同的范围，因此我建议您同时传递begin和end，如我的示例中所示。