on Fri Aug 29 2008, Arno Schödl <aschoedl-AT-think-cell.com> wrote:
Wouldn't it be more natural to represent a forward range as a single iterator, with an extra .at_end() check? This would eliminate the problem, because a difference_range would only need two such iterators, not four.
As part of http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2005/n1873.html one of the ideas we discussed extensively was allowing the end iterator of a range to be a different type from the begin iterator. That would allow a sort of "universal end iterator" to be used in situations such as this: struct end { // These definitions are only useful for infinite ranges template <class T> bool operator==(T const&) { return false; } template <class T> bool operator=!(T const&) { return true; } }; Effectively the data representation of the begin iterator would be the same as what you're proposing, plus comparison operators against the universal end type above, but the end iterator type could be empty (and optimized away). That allows a generic description of algorithms that are optimally efficient on pairs of pointers, but could simplify many classes of iterator (ifstream_iterators, for example) where every iterator needs all the information required to detect whether it can advance anyway.
Stacking them naively would have 2^N storage growth, rather than 4^N, and we still don't need to worry about range lifetime.
I've been trying to say that generic algorithms *can't* worry about the range lifetime; they have to assume that the iterators they're passed will not be invalidated before they're destroyed.
For other classes of iterators, the situation is similar. bidirectional ranges have at_end() and at_begin(), and random_access_ranges a size() and an operator[].
Bleah (sorry). Iterators in general shouldn't be burdened with the requirement to know the limits of the sequence, and if you go back and review the class of problems that iterators were "designed" to address, I think you'll see why. Just take a look at the classic quicksort algorithm, for example, or any other divide-and-conquer algorithm. I put "designed" in quotes because concepts are discovered, not designed, but that's a whole different topic.
I know that overthrowing such an established concept as ranges is not terribly popular, but I don't see any other way to combine easy stacking with no worry about lifetimes.
I'm not sure this is as revolutionary as you think. Every other language I've looked at has a get_next()/at_end() iterator abstraction, which is a lot like what you're proposing. My advice: make sure you keep in mind the whole problem domain. You can't understand the reason that C++ iterators are unlike those in other languages without looking at the algorithms. Generic Programming -- it's about the algorithms, baby! -- Dave Abrahams BoostPro Computing http://www.boostpro.com