[boost] Re: filter_iterator not bidirectional ?

From: David Abrahams (dave_at_[hidden])
Date: 2003-05-07 06:54:09

Sylvain Pion <Sylvain.Pion_at_[hidden]> writes:

> On Tue, May 06, 2003 at 08:48:51PM -0400, David Abrahams wrote:
>> > I was wondering why the filter_iterator could not be made
>> > bidirectional when the base iterator is as well.
>> 
>> It could, for a (rather high) price.
>> 
>> > Is it because it would have to store the "begin" iterator ?
>> > Actually I am wondering whether it should have to store the begin iterator
>> > even in this case.
>> 
>> Yes, it would.
>> 
>> > Would it be possible to make filter_iterator support operator-- ?
>> 
>> Yes it would.  It seems like a fun project for someone so inclined ;-)
>> Do you need this functionality for something, or are you just curious?
>
> I need it.  I have independently implemented a version of it in CGAL
> quite some time ago, and I'm comparing it to Boost's version now.
> Mine has to be bidirectional, so I store the "begin" base iterator.
>
> But I was wondering if I could do without, because the only reason for storing
> the begin base iterator is just to detect when the user calls operator-- on the
> begin() of the resulting filter iterator.
> But is this something which really has to be guarded against, or is this just
> something which can be left unspecified (i.e. it's a user bug) ?

Oh, maybe you're right and it can be left unspecified.

The reason one needs an end iterator is that it's important to avoid
stepping off the end when initializing an iterator whose filter
causes it to traverse an empty range.  In particular, it has to be
possible to represent the end iterator for some filtered range.

Jeremy, what do you think?

-- 
Dave Abrahams
Boost Consulting
www.boost-consulting.com