Re: [boost] Ranges

From: Richard Peters (R.A.Peters_at_[hidden])
Date: 2002-02-11 13:31:25

----- Original Message -----
From: "David Abrahams"
> From: "Richard Peters"
> > From: "David Abrahams"
> > > From: "Richard Peters"
> > > >
> > > Your aim, AFAICS, is to make iterator ranges. Mine was to make
> > > generalized half-open ranges. Since iterator ranges are just a subset
> > > of generalized ranges, it seems like a win to shoot for the
generalized
> > > model.
> >
> > Yes, I realize that difference in our aims now. My aim is to provide a
> > way to coveniently work with ranges of iterators, and easily make ranges
> > from containers. I'd like to end
> > up with the possibility of doing for_each(SomeVector, ...)
> > 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.
Why would it be a compromise if the class would support both? And I do not
see why the generalid model would be the value_range and not the
iterator_range. I think my iterator_range is perfectly capable of being a
value_range. Could you give an example when it isn't? Could you give an
example of real code that makes a value_range and that also works properly
when loaded with iterators?
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.

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

> > Ok, so we'd like to make a general half-open class. Let's start all
over.
> > I see two options here:
> > - Make an iterator_range and make it work with values too. This could be
> > done by loading a counting_iterator or some other sort of iterator that
can
> > hold any valuetype into the iterators. If the iterator is not
traversable,
> > some functions like size() would not be present, but that doesn't
matter.
> > - Make a value_range and make it work with iterators. In that case, the
> > valuetype is iterator, and there would be functions like size() that
> assume
> > the valuetype is an iterator.
>
> 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.

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

> > 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.
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, ... Everything that has to do with breaking up the range in a finite
number of values, and iterating through those values.

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

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

template<class ValueIterator> class iterator_range {
    ValueIterator m_begin;
    ValueIterator m_end;
    typename .....<ValueIterator>... value_type;
public:
    value_type front()   { return *m_begin; }
};

template<class Value, class ValueHolder = value_iterator<value> > class
value_range: public iterator_range<ValueHolder> {
};

value_range<int> TheValueRange(0, 5);
value_range<float> AnotherValueRange(0.4, 15.2);

This isn't complicated IMHO.
See for a more complete example
http://groups.yahoo.com/group/boost/files/range/iterator_range.hpp
and
http://groups.yahoo.com/group/boost/files/range/iterator_range_test.cpp

The output of this program is:
ValueRange start: 0 end: 5 difference: 5
FloadRange start: 3.5 end: 8.3 difference: 4.8
IteratorRange start: 0 end: 5 difference: 5 size: 5
Container: 0 1 2 3 4

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

This function would be part of a possibly future <boost/range/algorithm.hpp>
I expect it to fail when the range held by From isn't made of a finite
number of elements, and where the iterators thus do not support operator++.
In other words, it fails when range holds iterators that only model
value_iterator.

> > However, either
> > copy dereferences the valuetype, then it can copy the value_range
holding
> > the iterators, but it can't copy the value_range holding just the
values, or
> > copy doesn't derefernce the valuetype, in that case copy works on the
> > value_range holding the values, but it doesn't work on the value_range
> > holding the iterators.
> >
> > I see a problem with starting out with iterator_range, but this time I
have
> > a solution. Suppose -we want a range of floating point values, [0,
5). -we
> > have two members begin() and end(), begin() returns an iterator holding
the
> > float 0, end() returns an iterator holding the float 5. -we have two
members
> > of iterator_range, front() return *begin() and back() returning
> > *prior(end()). [--end suppose] Then, what does back() return? normally,
it
> > would return 4. In floating point types, however, 4.5 would still be in
[0,
> > 5). What we actually want is to make back() returning *end(). Why? We
> > actually have the range [0, 5] where the last value isn't in the range.
> > Implementations that know this, query the back() and keep in mind that
this
> > value doesn't belong to the range, but everything less does.
> > Possible solution: In half open ranges, we can not guarantee that
> > *prior(end()) is the last value. We can guarantee however, that when
end()
> > is dereferenceable, that *end() is the least upper bound of the range.
We
> > could change the behaviour of back() in the following way: reference
> > back(bool Open = true) { return *(end() - (difference_type)Open);
> > Implementations of algorithms can now specify: -I want an open range, -I
> > want an open range where end() is dereferenceable, -I want a closed
range.
> > The first case is the most common one, just calls back(). The second and
> > third one call back(false), where the second one takes into account that
the
> > value actually doesn't belong to the range. Front() could be modified
the
> > same way, then we have the choice of treating the iterator_range as
closed,
> > open, half-open or half-closed.
>
> 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.

> > Value_range doesn't have this problem, because you can already just
access
> > the first and last value. It's up to implementations to treat this as
> > closed, open, half-open or half-closed.
> >
> > I hope your favorite is still to first make a value_range and to make
that
> > one work with iterators. That would mean we have a more thorough
research of
> > both possibilities and we'll end up with a better solution :)
>
> That still makes a lot more sense to me.
>
> -Dave

---
Richard Peters
Eindhoven University of Technology