[boost] Re: cycle_iterator update

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?