Re: [boost] Generalized iterator ranges

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 {
   public:
       // "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; }
       
   private:
       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 {
   public:
       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; }
       
   private:
       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 
code.

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:

http://groups.google.com/groups?q=msgid:memo.20010513002833.16417B%40brang
don.madasafish.com

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

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