在許多矢量的組合上實現迭代器

Question

我正在研究一個需要遍歷K矢量元素的所有組合的問題。因此，例如對於K=2載體v1 = [0 1]和v2 = [3 4]，我會遍歷(0,3), (0,4), (1,3), (1,4)。

由於K是在運行時確定的，因此我不能使用顯式for循環。我目前的方法是基於this solution，實現了「里程錶」增加每個向量的索引。

#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 s的迭代器，而不是單個值類型來定義自定義迭代器所需的運算符。 這樣的迭代器如何實現？

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

UPDATE： 如果你仍然想使用迭代器，我建議迭代組合。可以將Combinator中的所有組合放入容器中，然後使用容器自己的迭代器。在我看來，這是一個更乾淨的解決方案。唯一的缺點是顯式存儲所有組合所需的額外內存。