c++ - 在多个 vector 的组合上实现迭代器

Question

我正在处理一个问题，该问题需要一次获取一个 K vector 的所有元素组合。因此，例如对于 K=2 vector v1 = [0 1] 和 v2 = [3 4]，我将迭代 (0,3)、(0,4)、(1,3)、(1,4)。

因为 K 是在运行时确定的，所以我不能使用显式的 for 循环。我目前的方法是基于 this solution它实现了一个“里程表”，为每个 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;
}

输出:

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 ]

但是，这有点困惑并且需要大量样板代码，为了清晰起见，我宁愿将它们移到别处。理想情况下，我希望有一个自定义迭代器类，比如 my_combination_iterator，这将使我能够做的事情更加简洁，例如:

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

到目前为止，我查看了Boost iterator_facade .但我的情况似乎比教程中的情况更复杂，因为我需要一个迭代器来处理 Value 的 vector ，而不是单个值类型来为自定义迭代器定义所需的运算符。如何实现这样的迭代器？

Answer 1

为什么要使用自定义迭代器？人们可以改为实现一个非常简单的类，它将遍历所有组合:

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

更新:如果您仍想使用迭代器，我建议迭代组合。可以将 Combinator 中的所有组合放入容器中，然后使用容器自己的迭代器。在我看来，这是一个更清洁的解决方案。唯一的缺点是显式存储所有组合需要额外的内存。