使用迭代器和可变参数模板的笛卡尔积 [英] Cartesian Product using Iterators and Variadic Templates

问题描述

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

I'm trying to create a function to generate the Cartesian product of a variable number of input ranges, using the style of the STL. My basic format is that the function accepts a fixed range and the start of an output range, then a variadic number of bidirectional input iterators.

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

我对 args 的想法是从中制作一个 tuple ，然后遍历该 tuple 以提取元素。这将需要我执行一些基本步骤：

My idea for the args is that I make a tuple out of it, then I iterate through that tuple to extract the elements. This would require me to follow a few basic steps:

1. 从中创建一个元组 args


2. 取消引用新创建的 tuple
中的每个迭代器

3. 按顺序增加元组中的每个迭代器，以便我们获得范围内值的所有可能组合。

1. Make a tuple from args
2. Dereference each iterator in the newly created tuple
3. Increment each iterator in the tuple in sequence, so that we get all possible combinations of the values in the ranges.

详细说明步骤3：如果我们有两组A = {0，1}和B = {2，3}，则笛卡尔积A x B = {（0，2），（0，3），（1、2），（1，3）}。

To elaborate on step 3: if we had two sets A = {0, 1} and B = {2, 3}, the Cartesian product A x B = {(0, 2), (0, 3), (1, 2), (1, 3)}.

我可以像这样进行第一步：

I can do the first step like:

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

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

The second step, I'm not too sure about. I think I will have somehow push_back elements to a temporary tuple, then set *result equal to that temporary tuple. I was a little inspired by the way that ostream accomplishes this, so I think this could come in handy:

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));
}

第三步可能很简单。我可以这样组合：

The third step is probably pretty trivial. I could combine something like this:

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

，其中包含3,000个 for_each的实现方式之一用于此处的元组。

with one of the 3,000 implementations of for_each for a tuple that are on here.

奇怪的是，我没有正确利用为此使用C ++ 14。到目前为止，我的教育完全集中在C ++ 11的较难部分上。

Odds are that I'm not correctly leveraging C++14 for this. My education has been entirely on the less-difficult parts of C++11 so far.

如果您很想推荐我使用 boost :: fusion 为此，谢谢，但是我不想使用它。

If you're tempted to recommend I use boost::fusion for this, thanks, but I would prefer to not use it.

推荐答案

我想出的是：

#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;

}

笛卡尔积函数的签名与您的签名略有不同，但是写一个包装程序应该很简单。

The cartesian_product function has a slightly different signature than yours, but it should be straightforward to write a wrapper.

由于传递的范围可能具有不同的范围，因此'd建议您同时传递开始和 end ，如我的示例。

Since the ranges you pass in may potentially have different extents, I'd suggest you pass both begin and end, as in my example.

这篇关于使用迭代器和可变参数模板的笛卡尔积的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！