[boost] [filter_iterator] Problem with --iter when applied to first satisfying location

From: Ford, Rich (Rich.Ford_at_[hidden])
Date: 2007-04-06 16:28:53

There is a problem with the filter_iterator decrement operation if the
iterator is currently referencing the first object that satisfies the
predicate. In that case the base iterator is decremented until the
predicate is satisfied, but since none of the locations back to the
beginning satisfy the predicate eventually the base decrement operation
is applied to the begin() of the container resulting in undefined
behavior.

 

I see these possible solutions.

 

1. Don't allow operator-- on filter_iterators. Require that you use the
filter_iterator on a reverse_iterator so that the end condition can be
properly checked.

 

2. One could require the constructors to specify not only the end of the
base sequence, but also the beginning. Then the filter decrement
operator could check for the beginning and not attempt to back up beyond
it. This seems somewhat of a pain for the user. The decrement operator
could set the result to end() if this situation occurred (or perhaps
leave it at begin()).

 

3. There is a nicer solution if the base iterator class is circular. A
circular iterator class is one where:

- ++(end()) is legal and yields begin(), i.e. you can increment end() to
get back to the beginning()

- --(begin()) is legal and yields end(), i.e. you can decrement begin()
to get back to end().

 

In case #3, the filter_iterator could be changed so that when
decrementing it also checked for end() when skipping over elements not
satisfying the predicate. The result of applying --x when x is the first
element in the container satisfying the predicate is end().

 

Perhaps a new kind of concept, circular_iterator_concept, should be
defined, and a new circular_filter_iterator defined which would have
this behavior on a base circular_iterator.

 

I think circular lists are not an uncommon implementation of containers
so this might be applicable more than one would expect.

 

In case you haven't guessed, I have a structure where I have defined my
increment and decrement to satisfy this circular requirement.

 

I've made the small changes needed in a copy of filter_iterator which
I've renamed to circular_filter_iterator. I've tested this out and it
works. I'm attaching a copy for those who might be interested.

 

Rich