RE: [boost] Re: Boost algorithm library

From: Fernando Cacciola (fcacciola_at_[hidden])
Date: 2001-07-30 08:18:46

----- Original Message -----
From: Aleksey Gurtovoy <alexy_at_[hidden]>
To: <boost_at_[hidden]>
Sent: Saturday, July 28, 2001 6:56 PM
Subject: RE: [boost] Re: Boost algorithm library

> Fernando Cacciola wrote:
> > As the original poster to raise this issue I must say that
> > the problem I was referring to is the case when the
> > algorithm deals with a container and not a range.
> > As I said in a different message, it is not the particular
> > representation of a range what matters. It can be a pair
> > or a single object with explicit begin,end members.
> > What matters is that a container, athough it offsers a range
> > interface, *it is not* a true range itself.
>
> Let me clarify - any standard container is a model of (SGI STL) Container
> concept, that is a refinement of (hypothetical) Range (or Sequence)
concept;
> 'range' (or 'iterator_range') class is a model of Range (Sequence) concept
> too; the only thing that 'range' class and any standard container have in
> common is that they are both models of Sequence.
>
But the Range concept supported by the standard container classes is not as
complete as the Range concept supported by a range class. Specifically, a
range class allows efficient subranging, a container class does not. This is
what I mean when I say that containers are not *true* ranges; they only
support a subset of a complete range interface.

> > The important difference is that the *state* of a range is
> > given by its begin,end values;
>
> State of 'range' object - yes.
>
> > while the *state* of a container is given by the entire sequence
> > (even if it is a subsequence) of elements.
> > Therefore, the value sematics of a container are significantly
> > different from that of a range.
>
> ..class.
>
> >
> > To see why it is so important the fact that a container is
> > not a range, even
> > if it has a range interface, consider the following:
> >
> > (*) This the sort_heap() function from the STL library that
> > ships with my
> > compiler:
> >
> > template <class RandomAccessIterator>
> > void sort_heap (RandomAccessIterator first, RandomAccessIterator last)
> > {
> >    while (last - first > 1)
> >        pop_heap(first, last--);
> > }
> >
> > (*) Now consider how would this look like if the range is
> > encapsulated in a
> > single class.
> >
> > template <class Range>
> > void sort_heap (Range range)
> > {
> >    Range::iterator first = range.begin() ;
> >    Range::iterator last = range.end();
> >    while (last - first > 1)
> >        pop_heap( Range(first, last--) );
> > }
>
> That's an ill-formed implementation of the algorithm, that mixes up the
> notion of 'range' class and Range concept;
>
And I wrote it this way precisely to show that.
My point is that in order to write algorithms to take a single argument we
need a well-defined range class, and that a container class -through its
range interface- only supports part of this.

>the correct implementation would
> be:
>
> template<class Sequence>
> void sort_heap(Sequence& seq)
> {
>     typename sequence_traits<Sequence>::iterator first(seq.begin());
>     typename sequence_traits<Sequence>::iterator last(seq.end());
>     while (last - first > 1)
>         pop_heap(iterator_range(first, last--));
> }
>
> Hope this clarifies things a bit.
>
This shows my point.
You explicitely used a true range class instead of a container to call down
pop_heap().
This is exactly was what I was suggesting.

I didn't meant the the user should not be able to call an algorithm with a
container.
I meant that the library implementer should realize the effect of subranging
in a container object instead of a range object and write the algorithm in
order to account for that. Which is precisly waht you've shown.

Once again: The OP asked for algorithms that should operate directly on
containers. I replied that it can lead to unefficiency, unless true range
classes were introduced. You just shown exactly how a range class would be
actually used.

Fernando Cacciola
Sierra s.r.l.
fcacciola_at_[hidden]
www.gosierra.com