Boost logo

Boost :

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.

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


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

we welcome your suggestions - keen to hear more;)


Boost list run by bdawes at, gregod at, cpdaniel at, john at