on Fri Sep 05 2008, "Giovanni Piero Deretta" <gpderetta-AT-gmail.com> wrote:
Oh! now I see where is where our inpedence mismatch is!. You want to store three pointers in filter_range because you correctly want this transformation to be lossless:
pair<filter_iterator, filter_iterator> a;
filter_range f(a.begin, a.end)
I think you mean filter_range f(a.first, a.second) And I'll assume from what you write below this not adding an additional layer of filtering; it is just storing a.first and a.second (compressed).
assert(f.begin() == a); assert(f.end() == b);
I think you mean assert(f.begin() == a.first); assert(f.end() == a.second);
i.e. the hidden common knowledge of a.begin and a.end of the effective end of underlying range (let's call it real_end) is preserved.
I wasn't motivated by that, actually. Frankly, I don't see why the invariant shouldn't hold even if you store only two pointers. The underlying end iterator would have been advanced to the nearest element satisfying the predicate, or real_end, by the time you try to construct the filter_range. A similar case is: assert( make_filter_range(a, a+len/2).end() == make_filter_range(a+len/2,a+len).begin() ) I don't think even our existing filter_iterator implementation supports that, though ;-). It's not unreasonable to request that all range-limited iterators traversing the same logical range be initialized with the same real_end.
I was naively thinking that, by transforming the pair in a full featured range, I could completely forget about real_end, and only encode to a.begin, a.end. In practice the whole filter_range information would be contained in a.begin, a.end would be completely redundant. The consequence of this is that the range could only shrink and never widen.
I think that's a great insight... for filter_range's iterator redundancy. It won't help with other redundancies, I'm pretty sure. However, they're less likely to occur across levels of stacking than is the sort of range limitation in filter_iterator.
Now, in general an iterator adaptor cannot rely on the fact that can advance the underlying range 'begin' beyond its 'end' , so real_and is effectively completely unecessary. Unfortunately the outside world knows better and can use .base() to extract the underlying iterator and would expect that real_end to be preserved.
Well, now, the underlying iterator is not real_end anyway. base() doesn't help you get it.
Now I see two solution:
- declare that the filter_range is not semantically equivalent to the original iterator pairs, but make the loss of information explicit. In practice this would means that the range could only shrink, but would make it possible to have space efficient abstractions.
- just declare defeat, and concede that you are right :)
Not so fast. You may be able to have your cake and eat it too. -- Dave Abrahams BoostPro Computing http://www.boostpro.com