Writing an iterator that makes several containers look as one

Question

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.

score 19 · Accepted Answer · answered Jul 19 '11 at 14:21

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.

Thank you, exactly what I was looking for. Never occurred to me that this would be in boost::range, although in hindsight it makes sense. — Roel, Jul 20 '11 at 08:21

Aasmund Eldhuset · Answer 2 · 2011-07-19T13:42:35.263

8

I think your "naive" approach should work, with the following change: instead of comparing the iterator to the end() of every container, keep a pointer to the current container and compare the iterator only the the current container's end(). When the end has been reached, move on to the next container. That way, you'll never compare the iterator to another container than the one it points to. This will also easily generalize to an arbitrarily-sized collection of collections.

edited Jul 19 '11 at 13:42

answered Jul 19 '11 at 13:36

Aasmund Eldhuset

37,289
4
68
81

And in operator== and such test the current container of each iterator first. – R. Martinho Fernandes Jul 19 '11 at 13:46
1

When I tried this, instead of keeping references to the containers I kept the begin and end iterator of the two ranges. The only advantage is that it is a little more flexible (i.e. you could bind subsequences from each container) – David Rodríguez - dribeas Jul 19 '11 at 13:57
@Martin: What David meant is to keep the begin/end iterators in the combining iterator, which would not have an effect on the use of the iterator - maybe I'm misunderstanding your remark. – Roel Jul 20 '11 at 08:29
@Aasmund: thanks, yes I guess this is the way to go to 'fix' my proposed way, I'm going to check it on my test code when I get home, even if boost::range::join already does what I want - I still want to find out why I thought that wouldn't work since I think I tried something like that too... – Roel Jul 20 '11 at 08:32

score 3 · Answer 3 · answered Jul 19 '11 at 13:46

3

zip_iterator works if you want to iterate two iterators in parallel. If you need to iterate over containers in sequence you can probably implement one using iterator_adaptor.

answered Jul 19 '11 at 13:46

larsmoa

12,604
8
62
85

zip_iterator only works when going over both in parallel, which is not what I want to do. I guess there is a way to do it with iterator_adaptor, my question was *how* :) – Roel Jul 20 '11 at 08:26

score 3 · Answer 4 · edited May 23 '17 at 12:06

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...

edited May 23 '17 at 12:06

Community

1
1

answered Jul 19 '11 at 13:52

David Rodríguez - dribeas

204,818
23
294
489

Thank you, this would work I think, it looks like what I called my 'naive' solution but with the change Aasmund proposed. boost::range::join uses a slightly different approach with a flag though, I'm not quite sure why. – Roel Jul 20 '11 at 08:24

score 1 · Answer 5 · answered Dec 22 '12 at 19:49

1

The answers other people gave only work for joining two ranges, but not an arbitrary number of range.

PStade Oven has a concatenated adaptor for joining any number of ranges; it also has a jointed adaptor for joining 2 ranges, specifically.

You can of course turn the ranges into iterators with begin() and end() if necessary; just make sure the ranges outlast the iterators.

answered Dec 22 '12 at 19:49

user541686

205,094
128
528
886

*but not an arbitrary number* - I suspect that's because `(a, b, c)` is the same as `((a, b), c)`. – c z Feb 06 '23 at 16:12
@cz: the type would become recursive if you tries to use it like that. You can't actually reduce concatenation to pair wise joining. – user541686 Feb 06 '23 at 17:11

score 0 · Answer 6 · answered Jul 19 '11 at 13:52

Aasmund is right. Your approach, though simple should work. But there is much room for optimizing.

Collection Objects are often large, and as so take some time to be iterated through. Especially list's and arrays.

You should consider multithreading so that each collection can be iterated in parallel.

Additionally. You should take the advice of the post you linked to use and use

Boost.MultiIndex

Writing an iterator that makes several containers look as one

6 Answers6

Linked