Re: [boost] Re: Re: Re: rtl (Range Template Library)

From: John Torjo (john.lists_at_[hidden])
Date: 2003-11-20 18:51:41

> 
> Taking the example of a forward range.  All we really need is a starting 
> point (not sure there is a substitute for iterator here) and an 'end test'.

Indeed ;)
Just check out how generated_range works. Exactly like this!
It has a functor and a stopper (which says when the current function should stop).

> 
> By default, a range is a pair of iterators and 'end test' is "current 
> position == end()"
> 
> However, for an example like an istream_range an end test is much better 
> expressed in terms of the underlying stream.  We currently fake this by 
> making a default constructed istream_iterator act as a sentry, but it is a 
> nasty hack.

It is pretty nasty, but still, it works brilliant;)
Anyway, I think that we can always fake an .end() iterator the way I've done in 
generated_range (have a bool 'm_more', which for end() is set to false).

> 
> By removing the condition that all ranges have a valid end() iterator at 
> construction time we open up more potential for forward ranges.

True. So what I think is that besides the existing crange/irange classes, we 
could have a special traversal_range class, which is pretty "fixed".

In other words, you cannot manipulate the begin() and end(). You can only 
increment it until it reaches the end.

However, the simplest implementation will still be with faking an end() 
iterator, to keep the existing algorithms happy;)

> 
> So the requirements on a forward range are:
> Start position is a forward_traversal iterator
> Some test exists to know if the current position can advance

Basically, I thought of something else. How about this:
In the traversal_range, we have *only one* iterator.
The iterator knows when it reaches the end.

This idea came to me after looking at filter_iterator. Because you cannot 
construct a filter_iterator unless you have two iterators (think about it;) ).

> 
> Algorithms where forward traversal ranges are appropriate can be expressed 
> in terms of this simpler interface without ever referring to end() 
> directly.

That is true. But for simplicity's sake (or lets call it, the first 
implementation;) ), we could use a fake .end() ;)
> 
> Insisting on the two-iterator implementation (or even an end() function) 
> seems to overspecify the requirements.

Indeed, but only in this particular case - for traveral_ranges.
> 
> OTOH, I quite agree that random access ranges are going to need both 
 > iterators

so will bidirectional access ranges.

Anyway, the way I see traveral_range right now is like a "weaker" range.

The only algorithms that need refinement are the input iterator algorithms. The 
rest are ok. In fact, for other than input iterator algorithms, it's easier and 
more efficient to write an algorithm in terms of begin and end.
Just think how hard it would be to write a rotate algorithm using a range directly.

For traversal_ranges, I would think of a new type of iterator. One that would 
have a function more() (could be non-member) which returns true while there are 
more elements, and false otherwise (again, look at generated_range).

(this would be IMO the easiest way to make that iterator usable with existing 
algorithms)

Best,
John