[prev in list] [next in list] [prev in thread] [next in thread] 

List:       boost
Subject:    [boost]  [Range] more efficient iterators
From:       Arno_Schödl <aschoedl () think-cell ! com>
Date:       2008-12-31 10:40:00
Message-ID: 2B173B138EFF584C846A48D41EFA3B42FF820D () server ! tc ! local
[Download RAW message or body]

Neil,

I promised you more efficient iterator adaptors in an earlier post. I actually got \
stuck, and shelved the problem for now. At least I want to share what I learned since \
I started the implementation. 

First of all, I was wrong framing the problem in the scope of ranges, so RangeEx is \
probably not the place to solve it. The iterators wrapped in a range are not \
restricted to only iterate within the range they are extracted from. In particular, \
the range may be a subrange of a larger range, and its iterators can iterate within \
the larger range. So ranges are just a special case of storing together multiple \
iterators over the same container range.

As we have discussed in the earlier thread, multiple iterators over the same \
container range may contain redundant information. For example, each \
tranform_iterator contains a copy of its function object. I believe this should be \
overcome by being able to divide/recompose an iterator into/from a private and shared \
part. Dave mentioned something like that already.

The other redundancy, which IMO is worse because it grows exponentially with adaptor \
stack size, is information about the begin and end of the underlying range, which is \
needed by some adaptors such as filter_iterator. First of all, regarding the question \
whether the range begin is ever needed, it is not for filter_iterator, but it is for \
union_iterator (interleaving two sorted ranges), so conceptually, knowledge about \
begin and end may both be needed and should be treated conceptually the same.

To solve the problem, an iterator could be tagged as "begin_bounded" and/or \
"end_bounded", similar to traversal categories now. For example, when an iterator is \
"end_bounded", it supports "at_end" and "distance_to_end" (if random access) \
functions. When a filter_iterator is layered over an end-bounded iterator, it can use \
these functions to avoid storing the range end itself. If it is layered on top of a \
non-end-bounded iterator, it must first wrap the iterator into a wrapper that conveys \
end-boundedness (and of course takes end in its constructor). Adaptors expose the \
begin_boundedness/end_boundedness of their underlying iterators if they can do so, \
which brings the savings in storage. 

I have a bit of an implementation for this last part as far as we need it for our \
project, but nothing to write home about, and there may well be still conceptual \
holes in it.

Arno

--
Dr. Arno Schoedl · aschoedl@think-cell.com 
Technical Director 
 
think-cell Software GmbH · Invalidenstr. 34 · 10115 Berlin, Germany 
http://www.think-cell.com · phone +49-30-666473-10 · toll-free (US) +1-800-891-8091
Directors: Dr. Markus Hannebauer, Dr. Arno Schoedl · Amtsgericht Charlottenburg, HRB \
85229

_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost


[prev in list] [next in list] [prev in thread] [next in thread]