Re: [Boost-users] Boost range iterator pointing to wrong element

Subject: Re: [Boost-users] Boost range iterator pointing to wrong element
From: Nathan Ridge (zeratul976_at_[hidden])
Date: 2013-10-09 02:52:24

>> struct to_include {
>> bool operator()(const std::pair<bool,int>& x) {
>> return x.first;
>> }
>> };
> [...]
>> /* reverse and then filter */
>> auto rf = container_cpy | reversed | filtered(to_include());
>> auto rf_it1 = rf.begin();
>> auto rf_it2 = std::next(rf_it1);
>> rf_it2->first = false;
>
> This is just a guess, but it strikes me as potentially dodgy to retain
> iterators to a filtered sequence after modifying the result of the
> filter predicate on that sequence. (This seems like something that
> would invalidate iterators, just like certain collection modifications do.)

Gavin is right. Filtered ranges assume that the value of the
predicate on sequence elements does not change during the 
iterator's lifetime. You are breaking that assumption, and so
anything can happen.

(I can't find any documentation about this assumption, 
however. We should probably add some.)

If you're wondering how the result that you're seeing comes
about, it's like this:

  - reverse_iterator stores an iterator of the underlying
    range not to the element it is pointing to, but to the
    next position. This is because there is a past-the-end
    iterator but not a before-the-begin one, so we need
    the begin() of the reversed range to store the end()
    of the underlying range, which, being the past-the-end
    iterator, is one position ahead of what the begin() of
    the reversed range is actually pointing to, which is
    the last actual element)
      - so reverse_iterator's dereference operator calls
        prior() on the stored underlying iterator to get the
        underlying iterator we actually want to dereference.
  - filter_iterator simply stores an iterator of the 
    underlying type to the element it is pointing to
      - so filter_iterator's dereference operator just
        dereferences the underlying iterator.
  - When the outer range is the reversed range, you
    dereference the reverse_iterator, which calls prior() 
    on the filter_iterator.
      - prior() on a filter_iterator walks the range backwards
        until an element matching the predicate is found.
        since you've modified the (0, 2) element so it no
        longer matches the predicate, it skips it and goes
        on to the (1, 1) element, which is what you rr
  - When the outer range is the filtered range, you
    dereference the filter_iterator which just derefernces
    the underlying reverse_iterator. No calls to the
    predicate are made, and (0, 2) element is returned.

So to sum it up, the difference is referring to the current
element of the filtered range in one case, and referring
to the next element and calling prior() to get at the
current element in the other case. The two are equivalent
under the assumption that the predicate's value does not
change while you're iterating.

Regards,
Nate