Re: [boost] Ranges

From: David Abrahams (david.abrahams_at_[hidden])
Date: 2002-02-11 14:13:39

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

> > > I'd love to see if there is a mid-way between iterator ranges and
> general
> > > (half-open?) ranges.
> >
> > Why compromise?
>
> I thought that with 'it seems like a win to shoot for the generalized
model'
> you meant to make a general class that works with both values and
iterators.

Yes.

> Why would it be a compromise if the class would support both?

A general half-open range does support both. A "mid-way between iterator
ranges and general ranges" is a compromise which would come with limitations
or ugly design warts.

> And I do not
> see why the generalid model would be the value_range and not the
> iterator_range.

Because you can't neccessarily iterate over everything that makes sense as a
range. Iteration is a discrete concept but ranges can be continuous.

> I think my iterator_range is perfectly capable of being a
> value_range. Could you give an example when it isn't?

All of my examples with floating point endpoints break down if iterators are
required.

> Could you give an
> example of real code that makes a value_range and that also works properly
> when loaded with iterators?

I don't know what you mean by this. I don't know what you have in mind when
you say "value_range", but a generalized range should be able to hold
iterators or other appropriate types.

> And could you give a list of functions that would be needed with a
> value_range (intersection and so)? This last question is probably not
> interesting for what the basis of ranges should be, value or iterator, but
> I'd like to have an indication about what value_ranges should be able to
do.

just look at half_open_range.hpp. Most, if not all, of the operations I want
are in there.

> > > Shall we name them iterator_range and value_range while
> > > discussing, to make the distinction where necessary?
> > > On a sidenote, IMHO iterator_ranges are more important _to the stl_
> > > because all algorithms work with two iterators where they actually
mean
> > > a range.
> >
> > AFAICT iterator ranges are completely useless to the STL because there
are
> > no algorithms that will do anything with them.
>
> That's a problem of the STL :) They say 'give a begin and an end' where
they
> mean 'give a range'. My aim is to provide a solution for this problem.

Fine; iterator_ranges are more important to what you'd like the STL to be.
BTW, you will have overloading problems if you try to define versions of
those functions which work with ranges because some of the functions already
take an optional predicate or UnaryFunction object.

> When
> we've got a range class that handles iterators well, it's quite trivial to
> write a <boost/range/algorithm.hpp> that creates a range-taking algorithm
> for all standard algorithms. Every library that wants to support these
kind
> of ranges, can make those functions too.
> Wouldn't it be wonderful if we can do for_each(range(container),
> some_function) instead of for_each(container.begin(), container.end(),
> some_function)? Especially when we don't have just the container, but a
very
> long indirection. I found this example in code of my own:
> for_each(Message.User.LoggedIn->Channels.begin(),
> Message.User.LoggedIn->Channels.end(), ....
> and compare it to:
> for_each(range(Message.User.LoggedIn->Channels), ...

Yes, of course it would. I don't see how that makes it sensible to /require/
iterators for all range endpoints.

> > size() shouldn't make that assumption - it should subtract the start
from
> > the end if the values are numeric, and use distance if they're
iterators.
>
> I thought of making size() return the number of elements in the range.
> Another function, like distance(), could subtract the start from the end.
> The exact names of the function aren't really important right now. I used
> size() because it's the established name in containers.

OK.

> > > In the case of the value_range, you could store the value in
> > > counting_iterators, so that you can iterator over the range.
> >
> > You can't do that unless the values are Incrementable. Why impose
> arbitrary
> > limitations?
>
> You use counting_iterator to hold the values in the half_open_range. I
just
> used it here because of that. Now that I think of it better, why would you
> store it in a counting_iterator? You usually don't need to iterate over
> values in a value_range. And in the case that you do want to iterate over
> the values, you might not just want to increase the value, for example
when
> you'd like to iterate over the range of fractions [1/4, 7/4) with taking
> steps of 1/4. You don't want operator++ there.

Exactly. That's why tying ranges to iterators makes no sense.

> > > My preference is to make an iterator_range:
> > > If you only need to store values specifying [begin, end), you can
> > > fill in a counting_iterator or something like that
> >
> > That sounds like a bit of hand-waving to me.
>
> Could you explain what you mean? I don't understand you.

By saying "you can fill in a counting_iterator *or something like that*"
(emphasis mine), you are glossing over the hard problem of ranges that can't
be iterated over.

> Actually, when making a value_range out of an iterator_range, you can
store
> the values in a value_iterator, see below.
>
> > > and not use functions that traverse through the range.
> >
> > I don't know what you mean by "use functions that traverse through the
> > range"
>
> Functions like getting the number of elements, getting an iterator to the
> start,

Why distinguish "getting an iterator to the start" from "getting the start"?

> ... Everything that has to do with breaking up the range in a finite
> number of values, and iterating through those values.

OK.

> > > An iterator doesn't necessarily traverse through ranges. They are used
> > > that way, but we could see iterators as just pointing at/holding
values.
> >
> > How do you reach that conclusion? Even the most trivial iterators (input
> > iterator/output iterator) include traversal as a fundamental part of
their
> > definition.
>
> It's not a conclusion. We could create a hypothetical iterator
> value_iterator that supports operator* to return the value. It doesn't
> support operator++. Input_iterator is an extension of that value_iterator,
> and thus not the most trivial iterator. The value_iterator can be used in
an
> iterator_range to hold any kind of value, and because of the missing
> operator++ it can't be used in many algorithms, and that's just the
> behaviour that is desired. Take for example the float range again. The
> value_range can hold the floats, but you can't pass the range to copy (my
> copy, not the std:: one), because the value_iterator doesn't model
> input_iterator.

Why require this layer that includes an indirection operator when storing
values directly would do just as well? You also require this new "iterator"
concept that doesn't even iterate. It seems crazy to stretch the definition
of "iterator" in this way without a good reason; AFAICT you are doing it
just so your argument that all ranges contain "iterators" doesn't fold up.
Woudn't it make sense to re-evaluate your position resorting to such extreme
measures?

> > > Seen in
> > > that way, a iterator_range is a range pointing out the two boundary
> > > values. And there we have iterator_range being a value_range.
> >
> > That's a whole extra layer of unneccessary complication.
>
> Why?

Because you don't need a non-iterating iterator shell in order to make
ranges of non-iterable values useful. If I haven't been able to make that
clear to you by now, I give up trying.

> > > I see a problem with starting out with value_ranges. Suppose: -we
> > > have a value_range, specifing the range [0, 5). -we have generalised
> > > the value_range so that it support some iterator operations. -we have
a
> > > value_range, holding two iterators, the two iterators specify the
range
> > > [0, 5). [--end suppose] Then, we want to copy both ranges to a
> > > destination. They both hold [0, 5) so you'd expect that copy works
> > > on both.
> >
> > No I wouldn't. std::copy takes iterators, not integers. If you want to
> copy
> > consecutive integers from a half_open_range<int>, I'd expect to use
> >
> >     copy(make_counting_iterator(r.begin()),
> make_counting_iterator(r.end()),
> > dest)
> >
> > or something similar. Whether the accessors should be called begin/end
is
> a
> > separate issue.
>
> When using copy, I expect to see a copy function like:
>
>     copy(range From, iterator To)

If you really want to use that function to generate a sequence of
consecutive integers in To, I don't see any problem with requiring that From
is a range of counting_iterators.

> > The iterator range based on floating values is senseless because few
> > algorithms will be able to successfully iterate over the range [0, 4.5).
> > This is almost certainly going to crash:
> >
> > template <class II, class F>
> > void for_each(II s, II e, F f)
> >
> > There are even ranges where the start and end are both integers which
will
> > have problems because of limited precision.
>
> Yes. But when you use range with value_iterators, you can't use for_each.

I don't think anyone will accept a concept called xxx_iterator which doesn't
iterate.

-Dave