2008/9/4 David Abrahams <dave@boostpro.com>:
But iterators like filter_iterator that need to know iteration boundaries, can store a range instead of an iterator, so they can benefit from the compression.
Oh, I totally missed that; sorry! Let's see...
strided_iterator<int*,5> stores range<int*>
sizeof(range<int*>) == 2*sizeof(int*)
filter_iterator<strided_iterator<int*,5> > stores range<strided_iterator<int*,5> >
range<strided_iterator<int*,5> > is represented as
unique_data<strided_iterator<int*,5> >::type start; unique_data<strided_iterator<int*,5> >::type finish; common_data<strided_iterator<int*,5> >::type common;
unique_data<strided_iterator<int*,5> >::type == int* common_data<strided_iterator<int*,5> >::type == int*
so its size is 3*sizeof(int*)
?? Did I get that right?
If so, it seems like there's still redundant storage. finish and common will be representing essentially the same information. If I were to write a filter_strided_iterator adapter and apply it to int*, it would have the size of 2 int*s. a
What information is contained in common that is not also contained in finish (i've never implemented a strided iterator, I'm trying to understand) ?
My point is that there is essentially the same information in common and finish, but that you can't eliminate it because the abstractions don't allow it. A strided_iterator implementation and test are attached.
Hum, I have been thinking about this for a while, and the more I think about it, the more it seems to me that that strided_iterator implementation is not optimal. Again, I've never needed one, so I'm not sure about the use case. I'll try to reconstruct the problems from the hints you left in this thread: Basically a strided iterator is an adaptor that visit every Nth element in a range, where N is a compile time constant. From your implementation I gather that the underlying range must be a random access range. A straight forward implementation is a thin wrapper around a random access iterator, you just replace operators ++ and -- with +=N (with similar changes for operators + and -). The problem is that you want to visit ranges whose size is not an even multiple of N, the above scheme wouldn't work, because before comparison with endpoint, you would have already moved the iterator beyond that end point. If the endpoint is one past the end of the base range, you have UB. The solution used in your implementation is to actually store the unstrided endpoint and position the internal iterator at that end point if the next increment would go beyond the boundary. This requires a conditional branch in increment, and makes the semantics of the iterator a bit surprising: you have to know the boundaries of the iteration when you construct the begin iterator and two iterators over the same underlying sequence with same stride and phase, but constructed with different end positions, will actually be iterating with diffent ranges (one iterator can't reach the end position of the other iterator). Now, the obvious solution is not to store the end position but instead to use a base+offset representation which are only combined together at dereference time. The member functions become: void incement() { //similar thing for decrement offset += N; } void advance(distance_type n) { offset += n * N; } reference dereference() const { return base[offset]; } distance_type distance_to(filter_iterator rhs) { return ((base - rhs.base) + (offset - rhs.offset)) / N ; // I might have got the sign wrong } [ in fact, searching the archives, it seems you are aware of this implementation, so I guess there is some problems I'm missing if you didn't use it] Assuming sizeof(size_t) == sizeof(void*), the size of this iterator is the same as the size of your implementation. Now a base and range size are the only informations you need to reconstruct begin and end begin.base = range.base; begin.offset= 0; end.base = range.base; end.offset = range.lenght; Thus sizeof(strided_range) can be sizeof(void*)*2 which is optimal. This doesn't of course prove that storing a range would lead to optimal representation for all iterator adaptors, but at least is enough for guaranteeing an optimal (in term of space) filter_iterator<strided_iterator>. Am I missing something? -- gpd