c++ - 如何迭代两个类似 STL 的容器(笛卡尔积)

Question

我想通过 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 );
  }
}

我的意思是在一个构造中封装 2 个循环(使用 Boost.Foreach、Boost.Range、Boost.Iterator 等)。以下是我想看到的喜欢的内容(这只是想法，并不完全是我想看到的)

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

如何做到这一点？

编辑:顺便说一下，在Python中你可以这样写

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

Answer 1

您可以使用可变参数模板来生成笛卡尔积。下面的代码基于 @zch 的 excellent answer另一个问题。

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

你可以这样调用它:

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

在线output 。

我不太熟悉 Boost.Range，但您可以轻松地调整这对迭代器以使用 Boost 范围。一个缺点是它不会是增量的，并且您必须先生成整个笛卡尔积，然后才能迭代它(您问题中的代码似乎不需要 break )。