RE: [boost] Re: Boost algorithm library

From: Aleksey Gurtovoy (alexy_at_[hidden])
Date: 2001-07-28 16:56:06

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. 

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

Aleksey