Re: [boost] Ranges

From: Richard Peters (R.A.Peters_at_[hidden])
Date: 2002-02-09 15:03:44

----- Original Message -----
From: "David Abrahams" <david.abrahams_at_[hidden]>
>
> ----- 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.

ok, this was what I meant with counting_iterator<any value>

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

yes. but you could use counting_iterator<int> when iterating over integers.
It's an interesting idea, though.

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

I like the begin() and end(), because they're already used a lot. Their name
indicates what they are.
I'd like to think endpoints are really iterators, sometimes the iterators
just iterate over integers. In that case, integer is just the value_type of
the iterator.

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

see above, my humble opinion is that you iterate over values, you do that
with iterators. btw, when you do something like copy(from, to), *to.begin()
should be valid if you use functions like begin, end. if you use an integer
instead of counting_iterator<int>, that would not be possible AFAICS.

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

hmm... yes that's right... I think however, that the aim of these ranges
(half open ranges) is different than ranges of floats. Ranges of float could
be made in many different ways, closed, open, half open, half closed. They
might need a seperate set of classes, or we would have to think of a way
making ranges be one of the other variants. I think however that that would
be too difficult.
Making another iterator_adaptor (value_iterator?) that takes everything as
value_type, could be a solution to get a half-open range of floats.

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

There is a single class, not a set of classes that have all the same
operations, typedefs, etc. That single class would be usefull in all cases,
so there's no need for other classes. With iterators for example, there are
a lot of different classes, all having same operations, etc. So in that
case, an iterator is a concept with a lot of models.

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

I'm sorry for not explaining myself. I meant, such functions should maybe
provided as seperate function, like the functions in <algorithm> aren't in
containers, either.
As I read it back now, I see that my wordings are a bit too offensive.
English is not my native language, and I sometimes have difficulties
explaining exactly what I mean. My appologies for this.

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

This remark was about my own range class, that behaves like its iterator
begin(). It was a doubt about if that is a good design decision. It could
have its benefits, but maybe it's just confusing. So basically, I have
doubts about my own class :)

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

---
Richard Peters
Eindhoven University of Technology