Implementing an iterator over combinations of many

I am working on a problem that requires iterating over all combinations of elements of K vectors taken one at a time. So for example for K=2 vectors v1 = [0 1] and v2 = [3 4], I would iterate over (0,3), (0,4), (1,3), (1,4).

Since K is determined at run-time, I cannot use explicit for loops. My current approach is based on this solution that implements an "odometer" incrementing an index for each vector.

#include <vector>
#include <iostream>

int main(int argc, char * argv[])
{
    std::vector<int> v1( {1, 2, 3} );
    std::vector<int> v2( {-2, 5} );
    std::vector<int> v3( {0, 1, 2} );
    std::vector<std::vector<int> > vv( {v1, v2 ,v3} );

    // Iterate combinations of elems in v1, v2, v3, one at a time
    std::vector<std::vector<int>::iterator> vit;
    for (auto& v : vv)
        vit.push_back(v.begin());
    int K = vv.size();
    while (vit[0] != vv[0].end()) 
    {
        std::cout << "Processing combination: ["; 
        for (auto& i : vit)
            std::cout << *i << " ";
        std::cout << "]\n";

        // increment "odometer" by 1
        ++vit[K-1];
        for (int i = K-1; (i > 0) && (vit[i] == vv[i].end()); --i) 
        {
        vit[i] = vv[i].begin();
        ++vit[i-1];
        }
    }

    return 0;
}

Output:

Processing combination: [1 -2 0 ]
Processing combination: [1 -2 1 ]
Processing combination: [1 -2 2 ]
Processing combination: [1 5 0 ]
Processing combination: [1 5 1 ]
Processing combination: [1 5 2 ]
Processing combination: [2 -2 0 ]
Processing combination: [2 -2 1 ]
Processing combination: [2 -2 2 ]
Processing combination: [2 5 0 ]
Processing combination: [2 5 1 ]
Processing combination: [2 5 2 ]
Processing combination: [3 -2 0 ]
Processing combination: [3 -2 1 ]
Processing combination: [3 -2 2 ]
Processing combination: [3 5 0 ]
Processing combination: [3 5 1 ]
Processing combination: [3 5 2 ]

However, this is somewhat messy and requires a lot of boilerplate code that I'd rather move elsewhere for clarity. Ideally I would like to have a custom iterator class, say my_combination_iterator, that would allow me to do things much cleaner, e.g.:

for (my_combination_iterator it = vv.begin(); it != vv.end(); ++it)
    // process combination

So far, I have looked at Boost iterator_facade. But my case seems more complicated than the one in the tutorial since I would need an iterator over a vector of Values as opposed to a single value type to define the required operators for the custom iterator. How could such an iterator be implemented?

Why would you like to use custom iterators? One could instead implement a very simple class that will iterate through all combinations:

class Combinator
{
public:
    Combinator(std::vector<std::vector<int> >& vectors)
        : m_vectors(vectors)
    {
        m_combination.reserve(m_vectors.size());
        for(auto& v : m_vectors)
            m_combination.push_back(v.begin());
    }

    bool next()
    {
        // iterate through vectors in reverse order
        for(long long i = m_vectors.size() - 1; i >= 0; --i)
        {
            std::vector<int>& v = m_vectors[i];
            std::vector<int>::iterator& it = m_combination[i];

            if(++it != v.end())
                return true;
            it = v.begin();
        }
        return false;
    }

    std::vector<std::vector<int>::iterator> combination() const
    {
        return m_combination;
    }

private:
    std::vector<std::vector<int> >& m_vectors; // reference to data
    std::vector<std::vector<int>::iterator> m_combination;
};

Live Demo

UPDATE: If you would still like to use iterators, I suggest iterating over combinations. One can put all the combinations from Combinator into a container and then work with container's own iterators. In my opinion it's a cleaner solution. The only drawback is the extra-memory needed to store all combinations explicitly.