Re: [boost] Ranges

From: David Abrahams (david.abrahams_at_[hidden])
Date: 2002-02-09 14:10:36

----- Original Message -----
From: "Richard Peters" <R.A.Peters_at_[hidden]>

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

This is a great approach; I'm interested.

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

Not quite. Ours holds any type. The type only has to be Incrementable if you
use begin()/end()/find() (the concept requirements for Incrementable are
given in the counting_iterator docs at:
http://www.boost.org/libs/utility/counting_iterator.htm) There are other
functions for accessing the start and finish of the range without using
begin()/end().

One of the things I struggled with when writing half_open_range.hpp was
whether to have begin()/end() return the held object or a counting_iterator
over those values instead. I'm not sure I like the choice I made, since it
doesn't map well onto ranges of iterators.

The basic dillemma is this:

A range of integers is a reasonable concept. An iterator over the range
should return a counting_iterator which wraps the integer.

A range of iterators is a reasonable concept. When iterating over the range,
people normally want an iterator of the same type as held by the range

A counting_iterator over iterators is a reasonable concept.

What I concluded just before I stopped working on half_open_range, was that:

1. The primary accessor functions to the endpoints shouldn't return
counting_iterators (unless of course that was the type parameter to the
range). It's easy enough to build a counting_iterator on the fly with
make_counting_iterator()

2. The accessor functions probably shouldn't be called begin()/end(), since
that has such a strong "iterator" implication and the endpoints might not be
iterators.

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

I think you're already assuming too much. A range does not neccessarily hold
iterators.

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

I don't think that will do, either. What about a range of floats? float
doesn't fulfill the concept requirements for counting_iterator.

> So I think range is a class, not a concept.

I don't understand how you're making that conclusion. Could you spell out
the reasoning in more detail?

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

Agreed.

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

On what basis? I'm not neccessarily arguing, but contentions like this
should come with justification.

> they could also be provided as a free function. You could also doubt
whether
> a range should be an iterator itself.

When did we ever discuss the idea that a range was an iterator?

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

I favor that one.