Boost logo

Boost :

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?

Boost list run by bdawes at, gregod at, cpdaniel at, john at