Boost logo

Boost :

From: brangdon_at_[hidden]
Date: 2001-10-29 17:00:11

> On Fri, 26 Oct 2001, Ben Cooling wrote:
> As an example of what I'm talking about, here's what the copy
> algorithm would look like:
> --- begin code ---
> template <typename InputIterator, typename OutputIterator,
> typename IterTest>
> OutputIterator copy(InputIterator src, IterTest srcend,
> OutputIterator dst)
> {
> for ( ; !endrange(src,srcend); ++src, ++dst)
> *dst = *src;
> }

This passes the source range as two objects. I would prefer to represent a
range with a single object, as Sean Parent suggested. I think copy should
look more like:

   template <typename InputRange, typename OutputIterator>
   OutputIterator copy( InputRange src, OutputIterator dst ) {
       for ( ; !src.empty(); ++src)
           *dst = *src;

Here InputRange is a "concept", with many possible implementations. One
such is:

   template <typename iterator>
   class IteratorRange {
       // "Iterator pair" methods.
       IteratorRange( iterator first, iterator last ) :
           first_(first), last_(last) {}
       iterator first() const { return first_; }
       iterator last() const { return last_; }
       typedef typename iterator_traits<iterator>::value_type value_type;
       // "Range" methods.
       bool empty() const { return first_ == last_; }
       const value_type &operator*() const { return *first_; }
       value_type &operator*() { return *first_; }
       IteratorRange &operator++() { ++first_; return *this; }
       iterator first_, last_;

This is intended as a straight-forward wrapper for a pair of iterators.
The first few members turn a pair into a range and extract the individual
iterators again, so anything we can do with a pair we can do with this.
The other members support the Range concept. Hopefully, when the inline
functions are expanded, the copy() function will turn into machine code
very like current implementations which pass the range as two objects.

By the way, all this code is just illustration. A real IteratorRange would
need more typedefs, a post-fix increment, etc. I have not tried to compile
it. I have tried to choose names which reflect the current STL, but we
might prefer is_empty() or even at_end() to empty(). Also we might not
want the operator overloading, eg using current() and advance() instead of
operator*() and operator++().

Another implementation of the Range concept might look like:

   template <typename iterator,
          typename iterator_traits<iterator>::value_type sentinal_=0>
   class SentinalRange {
       typedef typename iterator_traits<iterator>::value_type value_type;
       // "Sentinal" methods.
       SentinalRange( iterator first ) : first_(first) {}
       iterator first() const { return first_; }
       value_type sentinal() const { return sentinal_; }
       // "Range" methods.
       bool empty() const { return *first_ == sentinal_; }
       const value_type &operator*() const { return *first_; }
       value_type &operator*() { return *first_; }
       IteratorRange &operator++() { ++first_; return *this; }
       iterator first_;

Here we use a terminating sentinal value instead of the second iterator.
The sentinal might be '\0' for C-strings, NULL for argv-like arrays of
pointers, EOF for stdin, '\n' for lines of text, or whatever. Its value is
known at compile-time, so does not need to be part of the state of
SentinalRange. This means a SentinalRange can be smaller and more
efficient than a pair of iterators.

Other kinds of range are obviously possible. If we need a reference to the
container, it should be included as part of the Range object, not passed
as a parameter by the algorithm. Having a single object instead of two
will halve the overhead; we only need one reference to the container. By
the way, error-checking is easier with a single object too. Eg it's
trivial to assert( !empty() ) in operator++(), or in operator*().

Probably there should be a way of creating a range directly from a
container, eg:

    template <typename container>
    IteratorRange<typename container::iterator> range( container &c ) {
        return IteratorRange<typename container::iterator>(
            c.begin(), c.end() );

I would like to get rid of all those begin()s and end()s from application

I wrote some stuff about this idea in comp.lang.c++.moderated back in May
this year. This link should throw up some of the discussion:

Alternatively, search google groups for the word "sentinal" with author
"Dave Harris".

 -- Dave Harris
(PS Apologies if this is a double-post.)

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