Re: [boost] Cycle Iterator Adapter (was: Re: Help with iterator helpers)

From: David Abrahams (david.abrahams_at_[hidden])
Date: 2002-02-01 09:00:25

----- Original Message -----
From: <nbecker_at_[hidden]>
To: <boost_at_[hidden]>
Sent: Friday, February 01, 2002 8:41 AM
Subject: Re: [boost] Cycle Iterator Adapter (was: Re: Help with iterator
helpers)

> Sorry, I realize I should clarify this.  The problem is the
> desired behaviour of a cirular container is ambiguous.  If I tell you
> to copy (a, b, c), and a > b (base iterator), what do I really want?
> The interpretation I used is that I want you to iterate starting at a
> and continuing to b.  This means that
>
> distance (a, b) = (b - a) >= 0 ? (b - a) : (b - a + sizeof
> (container))
>
> However, I can see that  a different interpretation is also valid.
> With this interpretation, the distance (a, b) is signed, and in this
> case we can only use data from 1/2 of the container at a time.  In
> other words, copy (a, b, c) would only be able to copy at most 1/2 of
> the container.
>
> Note that if you do nothing, and inherit the default policy, you will
> get neither of these behaviours.  You get a behaviour that I think is
> not useful.
>
> I think in most cases it is the first behaviour that I would want from
> my circular containters.  This means that I know when I write
> copy (a, b, c), that b is always logically ahead of a.

I agree in principle. However, you might ask Matt Austern for a copy of his
paper on "segmented iterators". A circular buffer iterator is one example;
deque iterators are another. It buys a lot to divide up algorithms on these
iterators into contiguous sub-segments. I believe Dietmar Kuehl has been
talking about taking advantage of some of this information in his standard
library implementation.

-Dave