On Mon, Sep 1, 2008 at 8:37 PM, Steven Watanabe <watanabesj@gmail.com> wrote:
AMDG
David Abrahams wrote:
on Mon Sep 01 2008, "Giovanni Piero Deretta" <gpderetta-AT-gmail.com> wrote:
Need to think about it. Could you give a practical example of an iterator adapter needing three iterators?
E.g., a bidirectional filtered_iterator needs to be prevented from stepping off both ends of the underlying data to avoid undefined behavior.
Do we really have to worry about stepping off the beginning? I mean, you aren't allowed to decrement the iterator at the beginning of a range, anyway, and if you decrement any other iterator, the predicate is guaranteed to stop it before it goes off the beginning.
That's right! It can only be one of three cases: or the range is empty and you can't move at all; or you are at the beginning and you can't go back anyway; or it exist at least one element before the current one such as the predicate is true. It's so obvious that I never though of it. <ashamed/> ... and in fact boost::filter_iterator only holds the current and end iterator.
On the other hand, you shouldn't have to pay for those endpoint comparisons all the time, which tells me that something may be wrong with the design.
Hmm. Iterating over a range using a filtered_iterator on an underlying range of size n for which the predicate is true on m elements results in m + n + 2 comparisons of the underlying iterator and n calls to the predicate.
A hand-coded loop
for(; begin != end; ++begin) { if(f(*begin)) { // do stuff } }
uses only n + 1 iterator comparisons.
I'm not sure how often this is significant, but the only way I can see to avoid it is to combine the iterator increment and comparison into a single step.
for filter_iteator at least, I guess that the badly predictable 'if' will dominate over everything else. -- gpd