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
>> design
>> 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[].
>
> Neal,
>
> 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(),
> v.end());
>
> // Ends one past the 6th element:
> cycle_facade<...> e = make_cycle_facade(v.begin()+7, v.begin(),
> v.end());
>
> 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?