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