How to iterate over two STL-like containers (Cartesian product)

Question

I'd like to reduce the following with BOOST

typedef std::vector<int>::const_iterator Iterator;

for(Iterator i = v1.begin(), ie = v1.end(); i != ie; ++i) {
  for(Iterator j = v2.begin(), je = v2.end(); j != je; ++j) {
    doSomething( *i, *j );
  }
}

I mean to encapsulate 2 loops in a single construct (with Boost.Foreach, Boost.Range, Boost.Iterator, etc.). The following likes that I'd like to see (It's just idea, not exact what I want to see)

BOOST_FOREACH(boost::tuple<int,int> &p, ..._range(v1, v2)) {
  doSomething(p.get<0>(), p.get<1>());
}

How it can be done?

EDIT: By the way, in python you can write just

for (x1,x2,x3) in (l1,l2,l3):
print "do something with", x1, x2, x3

Answer 1

You could use variadic templates to generate the Cartesian product. The code below is baesd on @zch 's excellent answer to another question.

#include <tuple>                        // make_tuple, tuple
#include <utility>                      // pair
#include <vector>                       // vector

namespace detail {

// the lambda is fully bound with one element from each of the ranges
template<class Op>
void insert_tuples(Op op)
{
        // evaluating the lambda will insert the currently bound tuple
        op();
}

// "peal off" the first range from the remaining tuple of ranges
template<class Op, class InputIterator1, class... InputIterator2>
void insert_tuples(Op op, std::pair<InputIterator1, InputIterator1> head, std::pair<InputIterator2, InputIterator2>... tail)
{
        // "peal off" the elements from the first of the remaining ranges
        // NOTE: the recursion will effectively generate the multiple nested for-loops
        for (auto it = head.first; it != head.second; ++it) {
                // bind the first free variable in the lambda, and
                // keep one free variable for each of the remaining ranges
                detail::insert_tuples(
                        [=](InputIterator2... elems) mutable { op(it, elems...); },
                        tail...
                );
        }
}

}       // namespace detail

// convert a tuple of ranges to the range of tuples representing the Cartesian product
template<class OutputIterator, class... InputIterator>
void cartesian_product(OutputIterator result, std::pair<InputIterator, InputIterator>... dimensions)
{
        detail::insert_tuples(
                 [=](InputIterator... elems) mutable { *result++ = std::make_tuple(*elems...); },
                 dimensions...
        );
}

You can call it like this:

 int main() 
 {
    bool b[] = { false, true };
    int i[] = { 0, 1 };
    std::string s[] = { "Hello", "World" };

    std::vector< std::tuple<bool, int, std::string> > cp = {
            std::make_tuple(false, 0, "Hello") ,
            std::make_tuple(false, 0, "World"),
            std::make_tuple(false, 1, "Hello"),
            std::make_tuple(false, 1, "World"),
            std::make_tuple(true,  0, "Hello"),
            std::make_tuple(true,  0, "World"),
            std::make_tuple(true,  1, "Hello"),
            std::make_tuple(true,  1, "World")
    };

    std::vector< std::tuple<bool, int, std::string> > result;
    cartesian_product(
            std::back_inserter(result),
            std::make_pair(std::begin(b), std::end(b)),
            std::make_pair(std::begin(i), std::end(i)),
            std::make_pair(std::begin(s), std::end(s))
    );

    std::cout << std::boolalpha << (result==cp) << "\n";

    // now use a single flat loop over result to do your own thing
    for (auto t: result) {
        std::cout << std::get<0>(t) << ", ";
        std::cout << std::get<1>(t) << ", ";
        std::cout << std::get<2>(t) << "\n";
    }
}   

Online output.

I'm not all that familiar with Boost.Range, but you could easily adapt the pair of iterators to use Boost ranges instead. One disadvantage is that it will not be incremental, and you will have to generate the entire Cartesian product up front before you can iterate over it (the code in your question doesn't seem to need a break though).