Ranges

From: Richard Peters (R.A.Peters_at_[hidden])
Date: 2002-02-09 13:21:26

I'd like to work on classes for representing ranges. Therefore, I'd like to
start a discussion on what a range should do, what the specs are, etc. Is
there enough interest in boost to do this?

There already has been done a lot of work on ranges, amongst:
-the file <boost/half_open_range.hpp> made by Jeremy Siek and David
Abrahams. I shall refer to this one as [JSDA]
-the zipfile range.zip containing range.hpp by Daryle Walker, [DW]
 see http://groups.yahoo.com/group/boost/files/2000/range.zip
-the file range.hpp by myself, Richard Peters, [RP]
 see http://groups.yahoo.com/group/boost/files/range/

I've got a few discussion points:

1 What should a range be?
A range holds a begin and an end, and specifies the list of values [begin,
end) or [*begin, *end). The type of those 'things' can be different: in
[JSDA], it's a counting_iterator<any value>, in [DW], it can be any value,
in [RP], it's a class that models ForwardIterator. In [RP], the range models
a real iterator. [RP] only supports retrieval of values through [*begin,
*end) as begin and end always return iterators.

2 Should a range be a class or a concept?
All three examples make range a class. I think the range's behaviour is
determined by the iterators it holds. For iterators, you need a concept, so
that you can for example make a counting_iterator, that still fits the
criteria. For ranges, you just fill in the counting_iterator as template
parameter. So I think range is a class, not a concept. Because an iterator
determines the behaviour of a range, my opinion is that a range class should
hold iterators provided by a template parameter, and not a counting_iterator
as in [JSDA]. [RP] needs a template parameter that models a forward
iterator, [DW] does not, so that you can provide plain values. In [RP] you
would have to give a counting_iterator, but that doesn't hurt performance
AFAICS.

3 Could you make a concept range so that the containers model the concept?
I don't think so. A container owns its elements, therefore when the
container is const, its elements are const. Copying a container takes linear
time. A range doesn't own its elements, so when the range is const, its
elements aren't necessarily const. Copying a range takes constant time.
(Part of this is said in an email from Fernando Cacciola sent on Monday,
July 30, 2001 2:18 PM to boost)

4 What operations should a range class support?
All three support begin() and end(). [JSDA] and [DW] support functions like
contains() and find(). [JSDA] and [RP] support front(), back(), size(),
empty(). [RP] supports pop_front(), pop_back(), operators *, ++, --, [], +,
+=. The operators in [RP] are provided to make the range handle like its
iterator begin().
I doubt functions like contains() and find() should be in the range class,
they could also be provided as a free function. You could also doubt whether
a range should be an iterator itself.

5 What can be done with the range [begin, +inf)
This idea was taken from Peter Dimov, email sent Thursday, July 26, 2001
4:13 PM to boost.
Some algorithms, like copy, take a non-ending range. Currently, in the STL
you would provide the start only. What are the options?
- Don't bring this in the ranges, just continue to pass a single iterator
copy(range From, iterator To)
- Introduce support into the range class, but this might give too many
problems. You must satisfy: emty() == false, size() == inf, begin() !=
end(), and for random access iterators, begin() < end(). I have no idea how
to maintain the last requirement, without support from iterators.
- Use a special end-iterator. There are two suboptions:
  -- A little support from range class. Instead of 1 template parameter
specifying both begin() and end() types, you have 2 template parameters,
possibly different for begin() and end(). The begin() returns the normal
iterator, the end() the special iterator.
  -- No support from range class. You just use range<I> where I is a special
iterator<Base> that passes operators like != on to the iterator Base when
it's filled, and returns special values when the iterator isn't filled. for
range.begin(), you'd use a filled iterator, for range.end(), an empty one.
The last one is my favorite. The range class can be kept much simpler, while
in the cases that you really need an infinite end, an iterator is provided.
You can't possibly make an iterator pointing to an infinite element in
std::set, but then, you can't copy past the end of std::set. For numbers, as
in counting_iterator, you make an iterator holding the max value. For
output_iterators, you make new output_iterators that can hold an infinite
value.
Another option could be to not make the assumption that begin <= end or even
that end is valid for some functions. You put the output_iterator in begin()
and leave end() empty. As the range in [RP] is an iterator itself, you can
use it as output iterator. This way, you end up with functions like
copy(range From, iterator To), which still works with two ranges.

---
Richard Peters
Eindhoven University of Technology