[boost] Re: Boost Iterable Range Library update (v1.5)

From: David Abrahams (dave_at_[hidden])
Date: 2004-11-11 09:48:11

"Richard Peters" <r.a.peters_at_[hidden]> writes:

> David Abrahams writes:
>> > "Robert Ramey" <ramey <at> rrsd.com> wrote in message
>> > news:cmrl55$hng$1 <at> sea.gmane.org...
>> > >
>> > > I agree that iterators aren't that easy or intuitive to work with.  So
> our
>> > > motivations have much in common.  My view is that iterators can be
> made
>> > > easier to work with without changing their fundamental character and
>> > > without
>> > > the need to introduce what I see as a new concept (ranges) that is
> "almost
>> > > the same" as an existing concept - pair of iterators.
>>
>> Like Robert I am uncomfortable with a
>> range concept that has iteration capabilities.
>> For one thing, standard containers don't
>> satisfy that concept, and it seems to me
>> that a container ought to be a range without
>> any special adaptation.  Furthermore
>> I have doubts about how well this "range/iterator"
>> concept maps onto bidirectional
>> and random access.  That said...
>
> I think it will be very difficult to have the standard containers
> satisfy a range concept. 

It's difficult to have standard containers satisfy *your* range
concept.  That's exactly my point.

> Containers hold elements, and provide
> access to them via iterators. Those two iterators model a
> range. Algorithms like for_each take that range, and process the
> items element by element, by using the first element, and 
> shrinking the range by incrementing the first iterator. When you
  ^^^^^^^^^^^^^^^^^^^
This is the part that you added to "everyone else's" idea of what a
range should be.

> view a container as a range, you can't shrink the range without
> deleting elements. 

Right.  So don't shrink anything.

> This would mean that when passing a container to
> an algorithm that that algorithm either deletes items or has to copy
> the container. Ranges live at the level of iterators, providing
> access. They do not live at the level of containers, which store
> elements. Therefore, I think a container does not need to satisfy
> the range concept.

That's just needlessly inconvenient.  Unless you think people should
be writing a lot of hand-coded loops instead of using algorithms,
you're optimizing for the wrong case.  Traversal should be done, for
the most part, by libraries.  Libraries can afford to touch iterators.

> If I were allowed to make changes to the standard library, I would add a
> member function 

Yet another place where you'd impede genericity.  How would built-in
arrays fit into the picture?

> range() to containers, returning some range object holding a
> begin and an end: Containers hold objects, and provide access to them by
> representing those objects as a range. The range provides access to
> individual elements using iterators. Of course, changes to the standard
> library are not considered here. A make_range(container), however, comes
> very close to this, and seems like a good solution to me.

But oh, so unneccessary.

> As to the iteration capabilities: What would we loose if the iteration
> capabilities are removed? Are for-loops the only place that would be
> significantly changed?
>
>     for ( crange<some_array_type> r(some_array); r; ++r)
>          do_something( *r, some_data);

      boost::for_each(some_array, bind(do_something, _1, some_data))

> I think this syntax is a bit too short anyway. 

Why would you want to make it longer?

> What about adding member functions empty(), size(), front(), back()?
>
>     for ( crange<some_array_type> r(some_array); !r.empty(); ...)
>          do_something( r.front(), some_data);
>
> Looks nice enough, IMHO. 

Worse and worse, IMO.

> This leaves only the problem of shrinking the range at the
> start. What do you think about range.begin() (non-const version)
> returning a reference to its begin iterator? Then ++r.begin() would
> be the equivalent of the current ++r. Similarly end() can return a
> reference, making shortening the range at the end possible.

Iteration should mutate anything but iterators, IMO.  I'd hate to
think that I couldn't store a range in some object and then iterate
over it without modifying it.

> Another option I thought of was using pop_front(), but this has the
> disadvantage that it doesn't do exactly what is says: it does resemble
> list's pop_front, but no element is really erased.

All these problems go away if you don't try to get ranges to solve
the BOOST_FOR_EACH problem. http://www.nwcpp.org/Meetings/2004/01.html

-- 
Dave Abrahams
Boost Consulting
http://www.boost-consulting.com