
Boost : 
From: Aleksey Gurtovoy (alexy_at_[hidden])
Date: 20010728 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 illformed 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
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk