Re: [boost] [iterator]counting_iterator::referenceshouldbevalue_type?

Subject: Re: [boost] [iterator]counting_iterator::referenceshouldbevalue_type?
From: Arno Schödl (aschoedl_at_[hidden])
Date: 2009-01-07 05:24:30

> With respect to C++0x, that's correct.

Probably no point implementing something that is incompatible with it.

> I wonder if this means we really are missing an important concept.  It
> seems to me that the requirement to store a temporary iterator is a
> potentially high cost that can be avoided for most iterators, which have
> persistent referents.

On the other hand, there are only few iterator users who care either way. On one side, there is reverse_iterator. On the other there is counting_iterator (but as far as performance is concerned, only those with fat value_types, counting_iterator<int> can return by value) and caching iterators. Among these, IMO, caching iterators are most relevant. Do you see more cases?

>From http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2008/n2807.html#198: "Andy Koenig pointed out that it is possible to rewrite reverse_iterator so that it no longer makes such an assumption." Do you know what he had in mind? I don't see a better solution than what you suggested, storing two iterators. Storing the iterator in decremented form does not work because of begin(). Applying the decrement on demand and storing an extra bool whether this has been done is ugly, does not save much for trivial pointer-sized iterators, and leads to inconsistent behavior for insertions/deletions on the underlying container depending on whether the reverse_iterator has been dereferenced or not.

I don't think introducing another trait is worthwhile unless we have more use cases than reverse_iterator. reverse_iterator::dereference is already slower due to the decrement, which is probably more relevant in practice than the memory, in particular when iterating over data structures such as trees. So for optimum performance, reverse_iterator is already not the way.

--
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