代码之家  ›  专栏  ›  技术社区  ›  mikkola

在多个向量的组合上实现迭代器

  •  1
  • mikkola  · 技术社区  · 9 年前

    我正在研究一个需要迭代所有元素组合的问题 K 每次取一个向量。例如 K=2 向量 v1 = [0 1] v2 = [3 4] ,我会迭代 (0,3), (0,4), (1,3), (1,4)

    K 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而不是单值类型来定义自定义迭代器所需的运算符。

    1 回复  |  直到 9 年前
        1
  •  2
  •   AMA    9 年前

    为什么要使用自定义迭代器?

    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 然后使用容器自己的迭代器。在我看来,这是一个更清洁的解决方案。唯一的缺点是显式存储所有组合所需的额外内存。