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

From: John Torjo (john.lists_at_[hidden])
Date: 2003-11-20 13:11:22

AlisdairM wrote:

> John Torjo <john.lists_at_[hidden]> wrote in
> news:3FBBFFD9.4000601_at_[hidden]: 
> 
> 
>>Now that I think about it, a range concept does not even need to be so
>>complicated. As explained above (in the original message):
>>- a range is a pair of iterators
>>- it has typedefs for value_type,pointer,reference
>>   (no const_pointer,no const_reference)
>>- it's got begin() and end()
>>- it's got an operator bool() that returns true if the
>>   range is non-empty.
> 
> 
> I have been on the verge of my own 'range' library for a while now, and 
> have finally freed up enough time to get started on it.  I will certainly 
> look into your proposal, but I'm not entirely happy with the formulation 
> above.
> 
> In particular, range as a concept should not specify that a range is a pair 
> of iterators.  This will be a common implementation, but should not be the 

I think specifying that it contains two iterators is fine. Anyway, it has member 
functions begin() and end() ;)

> only one.  Some motivating examples:
> 
> i/  Containers should automatically be valid ranges.  Therefore it is 

Containers are automatically valid ranges, but only for the purpose of algorithms.
Indeed you make a valid point: we need two separate definitions: one for the 
concept of range taken by an algorithm, and one for our range traversal class.
Right?

> reasonable to expect a range to return iterators from begin()/end(), but 
> they may be implicit rather than data.
> 
> ii/ ranges will need classifying similar to iterators, eg forward traversal 
> ranges, random access ranges.  A forward range might be expressed by a 
> single iterator and a terminate condition.  (eg istream_range)  Default 

I don't agree here. A forward range still has two iterators.
The fact that you don't have to deal with them directly, that's the added bonus ;)

What we thought is the range inherits everything from the underlying iterator. 
If we have an input iterator, we get an input range. If we get a forward 
iterator, we get a forward range; etc.

> constructing iterators to act as end() sentries always struct me as odd, so 
> I would like to take this requirement out of an initial pass.

I'm not sure I understand. The way we see ranges is still as a pair of 
iterators. There still must be a begin() and an end(), for us to have a range. 
How you implement end() internally it's still up to you (the implementor of the 
iterator class).

You should note the fact that if we take out the requirement of a range being a 
pair of iterators, how could you use it in algorithms?

Anyway, I do see your point. Indeed, some ranges would be much simpler if 
regarded as only that - a range (no iterators, just a range).
In such a case, you'll only be able to forward traverse it.

Now, after some thinking this could be a great idea. Just think of how 
filter_iterator is implemented. The filter_iterator *necessary* needs two 
iterators. Creating the filtered_range from filter_iterator stores 4 iterators 
internally (two of them not being used).
So, we could have a special range class, a class only for forward traversal.
This will create a special kind of range: traversal_range.

Then, for each STL algorithm that takes only input iterators, we'll need to 
create our own special version, that will take a traversal_range.

Come to think of it again, it's a brilliant idea!

> 
> Likewise, the test for empty ranges should be to call an empty() function.  
> This way standard containers continue to make conforming ranges.

That's an interesting idea. We can add that.
But I still like having operator bool().

> 
> 
> 
> The other part of the range library I was planning was range_adaptors along 
> the lines of iterator adaptors.  With transform_range and filter_range, you 
> can cut down on the number of algorithms that actually need supporting (eg. 
> filter_range reduces the need for many [but not all] _if algorithms)

Indeed, a lot of STL algorithms could be ignored altogether.
However, we implemented all STL algorithms, so that the user has a choice - to 
use the adaptors, or raw algorithms.

You say "[but not all]" - is there a specific algorithm you had in mind?

> 
> 
> Finally, as pointed out elsewhere, lightweight ranges make ideal return 
> values from functions.  eg: a map might have keys/values member functions 
> returning some sort of transform_range, or following container_traits lead 
> these could even be free functions.
> 

Indeed;)

> 
> I am keen to look into your actual proposal asap, but probably not till 
> weekend :¬ (
> 

we welcome your suggestions - keen to hear more;)

Best,
John