[boost] [Range] more efficient iterators

Subject: [boost] [Range] more efficient iterators
From: Arno Schödl (aschoedl_at_[hidden])
Date: 2008-12-31 05:40:00

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_at_[hidden] 
Technical Director 
 
think-cell Software GmbH · Invalidenstr. 34 · 10115 Berlin, Germany 
http://www.think-cell.com · phone [phone] · toll-free (US) [phone]
Directors: Dr. Markus Hannebauer, Dr. Arno Schoedl · Amtsgericht Charlottenburg, HRB 85229