Alex Rivera | Logout

Writing an iterator that makes several containers look as one

Asked 2011-07-19T13:33:41.920
23

Consider the following simplified example and desired output:

class A
{
    class combined_iterator
    {
        ????
    }
    typedef ??? t_combined_it;

    t_combined_it begin();
    t_combined_it end();

    std::vector<int> m_Vec1, m_Vect2;
}

A a;
a.m_Vec1.push_back(1);
a.m_Vec2.push_back(2);
for (A::t_combined_it it = a.begin() ; it != a.end() ; it++) {
     std::cout << *it << " ";
}

Output:

1 2 

I think the question is clear from this: how do I write an iterator that makes it look as if two or more other iterators are really just one sequence. So that, in the example, instead of iteration over both m_Vec1 and m_Vec2, I can use an iterator that iterates over first the elements of m_Vec1 and then m_Vec2, transparently.

I found the following question which I think asks the same: Make a c++ iterator that traverses 2 containers . There were no good answers to this question; the solution presented by the original asker seems convoluted, and it is (relatively) memory-intensive.

I tried a naive approach by keeping a std::vector::iterator as a member of my custom iterator, and comparing it to the .end() iterators of each of the sequences being iterated over; however it seems that it is illegal to compare iterators from different containers (where I would have preferred them just to return 'not equal' - maybe that is a direction to go for finding the solution to this problem? I can't think of how to implement it, though).

Where possible and if relevant, I would like to use boost::iterators as I use them elsewhere and I like the homogeneity it provides to my iterator implementations; but of course if someone has an idea without using them, I can work them in myself, so they're not required in that sense.

Edit
Report

2 Answers

20

boost::join is what you're looking for. You can also study the implementation, especially how to derive the lowest common denominator for container traversal, reference and return value types. To quote:

The intention of the join function is to join two ranges into one longer range.

The resultant range will have the lowest common traversal of the two ranges supplied as parameters.

Note that the joined range incurs a performance cost due to the need to check if the end of a range > has been reached internally during traversal.

answered 2011-07-19T14:21:02.487
3

I already implemented something similar for a different question. The implementation is here. The basic idea is the one you approached: storing the two iterator ranges, when you are asked to perform an operation check whether you have completed the iteration in the first range, and use either range.

This is not thread safe by any means, and I have never used that implementation in real code, so there might be issues and bugs and...

answered 2011-07-19T13:52:30.190

Your Answer