
On Fri, Sep 5, 2008 at 6:55 PM, David Abrahams <dave@boostpro.com> wrote:
on Fri Sep 05 2008, "Giovanni Piero Deretta" <gpderetta-AT-gmail.com> wrote:
You're completely right about that, and there are even additional reasons that you didn't mention, as I realized a couple days ago. I didn't want to bring it up, though, because it doesn't change the fundamental reality. Just replace strided_iterator by another layer of filter_iterator.
Hum, but as long as an iterator contains only a range, you can always encapsulate it with no space overhead. a filter_iterator<filter_iterator<T* > > has sizeof(T*2) (assuming a stateless predicate), which is optimal.
First of all, there's other kinds of data that's redundant across pairs of iterators in a range hey, like the predicate!
that's not a problem, a filter_range would store the predicate only once.
But let's ignore that for a moment. The range compression formula is:
sizeof(range<X>) == 2*sizeof(X) - sizeof(common_data<X>::type)
so when X is filter_iterator<Y>:
sizeof(X) is 2*sizeof(Y) common_data<X>::type == Y
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) assert(f.begin() == a); assert(f.end() == b); 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 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. 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. 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 :) -- gpd