Cartesian Product using Iterators and Variadic Templates

Question

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

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. 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.

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

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

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

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.

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

Answer 1

In C++17, we get std::apply(). A possible C++14 implementation is found on that link. We can then implement fmap for a tuple as:

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

With that:

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

Answer 2

Here's what I've come up with:

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

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