[boost] Re: boost::filter_iterator Model

From: Bob Bell (belvis_at_[hidden])
Date: 2004-12-10 22:58:59

Thomas Witt wrote:
> Bob Bell wrote:
> 
>> Hi-
>>
>> I was wondering what the rationale was for boost::filter_iterator not 
>> modeling
>> anything more than a forward traversal iterator.
> 
> 
> Cost.
> 
>> Recently I was trying to use
>> filter_iterator in a situation where I needed bidirectional traversal, 
>> but got
>> stymied by this. Is there something about the notion of filtering that 
>> precludes
>> bidirectionality? Or is this something that could be made to work?
> 
> 
> In order to be able to be bidirectional the filter iterator would need 
> at least another member, the beginning of the sequence and another ctor 
> parameter, again the beginning of the sequence.

Is this so that when iterating backwards you can stop before "running off the
beginning?" I'm in the unenviable position of not being able to use boost at
work, but I needed some of the functionality of the iterator library, so I ended
up implementing a subset of it myself. When it came to filter iterators, I
implemented them as bidirectional. Initially, I had the extra iterators you
mention, but I ended up getting rid of them. My reasoning was like this:

Consider this forward loop:

while (b != e) {
   // use *b;
   ++b;
}

Incrementing b will, internally, dereference its base iterator and call its
filter function to determine when it's encountered a new element in the filtered
pseudo-sequence. However, it must be prevented from incrementing past e. So b
also carries a second, "sentinel" base iterator (that must be initialized to the
same sentinel carried by e); when incrementing, if b reaches the sentinel, it
doesn't dereference and test, it just stops. This makes sure that b will 
become equal to e, and the loop will terminate.

Now consider a typical reverse loop, where we decrement backwards through
[b, e):

while (b != e) {
   --e;
   // use *e;
}

No "begin sentinel" is required to make this loop behave as expected. When b is
created, it will point to the first element of the filtered pseudo-sequence;
this means that eventually, e will become equal to b, and the loop will
terminate.

In fact, it seems that without a begin sentinel, uses of b and e are just as
well-defined (or undefined) as equivalent ordinary iterators. For example, for
an ordinary sequence [b, e), --b is well-defined only if there is something
dereferencable there. For a filter iterator lacking a begin sentinel, the same
thing is true.

What do you think?

> This is a non negligible 
> cost that users that are ok with fwd iterators most likely don't want to 
> pay.

If there's still some requirement to have the extra cost for bidirectionality
(i.e., if there's a flaw in my analysis above), I wonder if there isn't some
metaprogramming trickery that could make the cost exist for only those who need
bidirectionality, while those who need only forward iteration don't pay.

Not that I'm volunteering to write it. ;-)

Bob