RE: [boost] Re: Boost algorithm library

From: Fernando Cacciola (fcacciola_at_[hidden])
Date: 2001-07-26 10:10:36

----- Original Message -----
From: <helmut.zeisel_at_[hidden]>
To: <boost_at_[hidden]>
Sent: Thursday, July 26, 2001 9:00 AM
Subject: [boost] Re: Boost algorithm library

> --- In boost_at_y..., "Philip Nash" <philip.nash_at_c...> wrote:
> > .. adding to the debate of container interface vs range iterator
> interface:
>
> Just to change the terminology a little:
> IMHO, we have no container interface vs. range interface debate.
> We have just 2 different possible range interfaces.
>
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.
The important difference is that the *state* of a range is given by its
begin,end values; 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.

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

The first thing to notice is that in the case of a container, begin()/end()
are not lvalues. That's why I needed to create a local variable so I can
apply operator -- to shift the end of the range.
With a true range, these would be lvalues so the code would have been even
simpler.

Now, I'm perfectly OK with the code above. I like range classes (such as the
one you presented, or David mentioned); but there is a problem:

Since a container -which is not a range- provides precisely the same range
interface, nothing will prevent a user from calling sort_heap() with a
conainer; but the effect of this will be that the expression
Range(first,last--) will create a whole new container with its elements
duplicated..

(Please, don't tell me that pop_heap() should have the iterator_pair range
representation)

I started this disccusion saying that I wasn't sure about the impact of
designing algorithms that take containers instead of ranges.
The discussions evolved as to which range representation to use. This is not
the issue.
It is OK to use a single range class to specifiy the input range. But this
range class should provide efficient subranging and bidirectionality. This
isn't the case of a container.
I expressed concern about the impact of  a range representation that allow
containers to appear as ranges.

Since a single-class range representation seems to be the concensus, I would
use a range class with lvalue members first,last; not begin,end; so only
true ranges can be feeded into algorithms.

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