From: Neal D. Becker (ndbecker2_at_[hidden])
Date: 2004-04-14 13:21:49
Roland Richter wrote:
>> Here is an update to cycle_iterator. This is based on the original
>> by Gennadiy Rozental. After fairly extensive performance testing I am
>> getting good results (compared to my old implementation which was
>> hand-written, not based on boost iterators), after adding operator.
> one important issue I came across:
> Say I have a collection, and I want to iterate over all its elements.
> For some reason, I don't want to do it from first to last, but I want
> to start at the 7th element, iterate to the end, jump back to the
> beginning, continue, and finish at the 6th element. Sounds like a
> case for cycle_iterator, right? Here we go:
> vector<int> v(10);
> // Begins at 7th element:
> cycle_facade<...> b = make_cycle_facade(v.begin()+7, v.begin(),
> // Ends one past the 6th element:
> cycle_facade<...> e = make_cycle_facade(v.begin()+7, v.begin(),
> I guess you already see the problem: the loop
> for( cycle_facade<...> it = b; it != e; ++it )
> // do something
> is exited immediately, since b and e here are considered _equal_ (which
> is not what we intended).
> My solution back then was to keep an internal counter which counts how
> often the iterator got "past the end". In the case above, b would have
> a counter of 0, whereas e got past the end once, i.e. the counter is 1.
> Hence, b and e are no longer equal.
> You might want to check out cyclic_iterator in boost/view from the
> CVS Sandbox (and yes, it also uses the new iterator_adaptors).
> I am aware that this might not be relevant in your case; yet, I'd like
> to hear your opinion on this "equality" problem.
Very interesting stuff. I guess the problem I am addressing is a little
different. If you want to cirularly iterate over an existing container,
you're right, there is a problem of what to do with end(). My problem is
slightly different - I am free to just allocate one extra element in the
container. The constructor Ring(size_t n) will allocate a container of
size n+1. Problem solved. Answer is you have no business asking to
iterate over the whole container, you can only iterate over 1 less.
Still I'm very interested in your approach, but I have some questions.
1) The constructors I used take 3 arguments, the begin, end, and current
position. I don't see how this would work with only 2 arguments. If I do:
make_iterator (v.begin()+2, v.end())
then this iterator will be associated with the incorrect size, right?
2) If I have a Ring class, it needs a copy constructor. This copies the
underlying container, then needs to setup a new iterator. It is desirable
to be able to:
a) get the state of the old iterator
b) construct a new iterator with this state
If you look at my Ring and iterator, you see that iterator has a function
"offset" that basically retrieves the original state information, and the 3
arg constructor allows setting the state. Do you think something similar
is needed for you implementation?
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk