Boost logo

Boost :

From: Steven Watanabe (watanabesj_at_[hidden])
Date: 2008-09-01 14:37:05


David Abrahams wrote:
> on Mon Sep 01 2008, "Giovanni Piero Deretta" <> wrote:
>> Need to think about it. Could you give a practical example of an
>> iterator adapter needing three iterators?
> E.g., a bidirectional filtered_iterator needs to be prevented from
> stepping off both ends of the underlying data to avoid undefined
> behavior.

Do we really have to worry about stepping off the beginning?
I mean, you aren't allowed to decrement the iterator at the
beginning of a range, anyway, and if you decrement any other
iterator, the predicate is guaranteed to stop it before it goes
off the beginning.

> On the other hand, you shouldn't have to pay for those endpoint
> comparisons all the time, which tells me that something may be wrong
> with the design.

Hmm. Iterating over a range using a filtered_iterator
on an underlying range of size n for which the predicate
is true on m elements results in m + n + 2 comparisons
of the underlying iterator and n calls to the predicate.

A hand-coded loop

for(; begin != end; ++begin) {
    if(f(*begin)) {
        // do stuff

uses only n + 1 iterator comparisons.

I'm not sure how often this is significant, but
the only way I can see to avoid it is
to combine the iterator increment and comparison
into a single step.

In Christ,
Steven Watanabe

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