Boost logo

Boost :

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.


> 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

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.


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