Re: [boost] Ranges

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

----- Original Message -----
From: "Richard Peters" <R.A.Peters_at_[hidden]>
To: <boost_at_[hidden]>
Sent: Sunday, February 10, 2002 1:29 PM
Subject: Re: [boost] Ranges

> ----- Original Message -----
> From: "David Abrahams" <david.abrahams_at_[hidden]>
> > ----- Original Message -----
> > From: "Richard Peters" <R.A.Peters_at_[hidden]>
> > >
> > 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?

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

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

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

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

> and not use functions that traverse through the range.

I don't know what you mean by "use functions that traverse through the
range"

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

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

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

> 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)
{
    for (;s != e; ++s)
    {
        f(*s);
    }
}

There are even ranges where the start and end are both integers which will
have problems because of limited precision.

> 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