Boost logo

Boost :

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

Boost list run by bdawes at, gregod at, cpdaniel at, john at