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

any reason you cannot just put the above in a reusable function? — stijn, May 22 '13 at 08:30
It shouldn't be that hard: Store a tuple of beginnings and a tuple of endings, use a running tuple as the actual iterator that you increase lexicographically. — Kerrek SB, May 22 '13 at 08:35
then write functions for those as well - even if you go with something like Kerrek's (pretty good) suggestion, you'll want to do that in a function else you'll be repeating yourself if you want to reuse it. — stijn, May 22 '13 at 08:37
@KerrekSB - Thank you. It sounds interesting, but I'm afraid I don't understand clearly. — Loom, May 22 '13 at 08:51
@KerrekSB Such forwarding iterators aren't as simple as they should be, since when incrementing internally, you have to know when you reach the end. The fact that you cannot know that from your single iterator is a major design flaw in the STL, and causes no end of problems. — James Kanze, May 22 '13 at 08:52
@JamesKanze: What I meant is that the "single iterator" stores the constant begin- and end-tuples. (I'm not sure about it being a "design flaw". How would you do it instead? Ranges?) — Kerrek SB, May 22 '13 at 08:55
@KerrekSB I understand that. Your derived iterators just become that much more complex. I encountered the same problem when I needed a filtering iterator, and boost::iterator is often heavier and more difficult to use because of it as well: when calling the constructor, you'll have to pass it four iterators, rather than just two, and of course, you'll need to construct two iterators for the iteration. In sum, thanks to the poor design of the STL, you're passing a total of 8 arguments, instead of just 2. — James Kanze, May 22 '13 at 08:59
@KerrekSB Iterators and ranges are a staple topic in the chat these days! — Luc Danton, May 22 '13 at 09:06
@KerrekSB My in house iterators all support the GoF idiom (as well as STL), so I can implement filtering on them easily. Otherwise, I use the Boost iterators, and pay the price in added complexity, because I'm usually iterating over a standard container. Needing _two_ instances to define a range is a major design flaw, but we have to live with it. — James Kanze, May 22 '13 at 09:20
Can you use C++11? `for(auto&& x : v1) for(auto&& y : v2) do_something(x, y);` is pretty concise and can be wrapped in a function for the "single construct" requirement. — Xeo, May 22 '13 at 09:39

score 3 · Answer 1 · edited May 23 '17 at 12:05

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

Note that you can also use `detail::insert_tuples` (perhaps with better name) to directly iterate through cross product without creating a vector. Just provide body of your loop as lambda. — zch, May 24 '13 at 22:53
@zch yes good point, although it is more like a ranged for loop than an iterator (with operator++, operator* and an end() iterator). How would you e.g. interrupt the loop based on some runtime condition? — TemplateRex, May 27 '13 at 07:35
yes, the question was about for loops. There are ways to get interruption like using exceptions or changing the code to stop when lambda returns `false`, but I agree they are not perfect. — zch, May 27 '13 at 11:17
A `cartesian_iterator` could be constructed from 2 `std::pair*` parameters (pointing to the begin/end pairs of the first and last factor in the cartesian product). Such an iterator stores 3 tuples of `N` iterators each: one for the current state, and 2 for the first and last element of the cartesian product. The `operator*` of an iterator simply dereferences all the iterators inside the tuple. `operator++` increments from the least to the most significant by comparing to the corresponding end iterator, or resetting to the corresponding begin iterator. It's similar to `std:next_permutation`. — TemplateRex, May 27 '13 at 11:44

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

1 Answers1