Re: [boost] lifetime of ranges vs. iterators

From: Arno Schödl (aschoedl_at_[hidden])
Date: 2008-09-02 02:47:34

> Enough for today. Maybe tomorrow I'll get some idea.

Let me try:

First of all, associated_range has the semantics of "[efficiently (who wouldn't want that?)] holds pair of iterators of certain type". This is the same semantics as iterator_range. The existing iterator_ranges are the default implementation of associated_range, and the associate_ranges we want to implement are specialized iterator_ranges for certain types of iterators. The two types are the same. So let's use this iterator_range throughout, since we already have it.

To eliminate quadratic running times, we must eliminate any linear-space expansion of function parameters. To do this, let's introduce some helper functions that make an iterator_range look like an iterator. Since we just discovered the dual life of iterator_range as associated_range, I will add them to iterator_range:

template< class I >
class iterator_range {
   ...other iterator_range stuff...

   // regular copy ctor for begin iterator

   ////////////////////////////////////
   // associated_range interface

   // end iterator ctor
   iterator_range( iterator_range const& range, create_end_tag ) 
   : m_begin( range.m_end ), m_end( range.m_end )
   {}

   // ctor from pair of ranges
   iterator_range( iterator_range const& b, iterator_range const& e ) 
   : m_begin( b.m_begin ), m_end( e.m_begin )
   {}

   // the names are chosen to reflect the function in iterators
   // they are meaningless when interpreted in range terms
   void increment() { // could be called "transform_to_rest" or simply "rest"?
      ++m_begin;
   }

   // TODO: check traversal_category whether this is allowed
   // Not needed by the forward filter_iterator below, but
   // would be used by bidirectional filter_iterator.
   void decrement() { // but what do we call this then?
      --m_begin;
   }

   // The three following helpers are optional. 
   // [actually I am not so sure, I have not tried to eliminate them]
   // They could be implented via
   // begin/end, but begin/end is still O(N) because it needs to copy the whole stack.
   // If the compiler can optimize away trivial forwards, these functions 
   // are O(1):

   // TODO: do we have to do anything about constness?
   reference dereference() const { // could be called "front"
      return *m_begin;
   }

   bool equal( iterator_range const& range ) const {
      return m_begin==range.m_begin;
   }

   bool at_end() const {
      return m_begin==m_end;
   }

   // TODO: advance, distance_to if traversal_category.
   // I first thought we never need them, but my company has a concat_range
   // that probably needs them. Would have to look in detail...
};

Now we implement iterator_range on filter_iterator:

template< class I, class F > class filter_iterator<I,F>;

template< class I, class F >
class iterator_range< filter_iterator<I,F> > {
private:
   iterator_range<I> m_range;
   F m_f;

   void skip_filter() {
      while( !m_range.at_end() && !m_f( m_range.dereference() ) ) {
         m_range.increment();
      }
   }

public:
   ////////////////////////////////////
   // associated_range interface

  // end iterator ctor
   iterator_range( iterator_range const& range, create_end_tag ) 
   : m_range( range.m_range, create_end_tag() ), m_f( range.m_f )
   {}

   // ctor from pair of ranges
   iterator_range(iterator_range<I,F> const& b, iterator_range<I,F> const& e ) 
   : m_range( b.m_range, e.m_range ), m_f( b.m_f )
   {}

   // the names are chosen to reflect the function in iterators
   // they are meaningless when interpreted in range terms
   void increment() {
      m_range.increment();
      skip_filter();
   }

   // TODO: decrement to be bidirectional

   // TODO: do we have to do anything about constness?
   reference dereference() const {
      return m_range.dereference();
   }

   bool equal( iterator_range const& range ) const {
      return m_range.equal( range.m_range );
   }

   ////// end of associated_range interface /////

   // ctor from underlying range
   iterator_range(iterator_range<I> const& range, F f ) 
   : m_range( range.m_range ), m_f( f )
   {
      skip_filter();
   }

   // ctor from underlying iterators
   iterator_range(I const& b, I const& e, F const& f ) 
   : m_range( b, e ), m_f( f )
   {
      skip_filter();
   }

   // ctor from own iterators
   iterator_range(filter_iterator<I,F> const& b, filter_iterator<I,F> const& e ) 
   : m_range( b.m_range.m_range, e.m_range.m_range ), m_f( b.m_range.m_f )
   {}

   // copy ctor
   iterator_range( iterator_range const& range ) 
   : m_range( range.m_range ), m_f( range.m_f )
   {}

   filter_iterator<I,F> begin() const {
      return filter_iterator<I,F>( *this );
   }

   filter_iterator<I,F> end() const {
      return filter_iterator<I,F>( *this, create_end_tag );
   }
};

The filter_iterator is reduced to a mere shell around the range:

template< class I, class F >
class filter_iterator<I,F> {
   typedef iterator_range< filter_iterator<I,F> > myrange_t;

   myrange_t m_range;

   // copy ctor trivial

   // ctor from range
   filter_iterator( myrange_t const& range ) 
   : m_range( range )
   {}
   
   // ctor from end range
   filter_iterator( myrange_t const& range, create_end_tag ) 
   : m_range( range, create_end_tag() )
   {}

   void increment() {
      m_range.increment();
   }

   reference dereference() const {
      return m_range.dereference();
   }

   bool equal( filter_iterator const& it ) const {
      return m_range.equal( it.m_range );
   }
};

If you are uncomfortable with the design because you don't see the connection to what you [Giovanni] proposed earlier: I believe that I really made little active choices in the design. I merely eliminated long parameter lists that give quadratic running times by pushing the parameters through the stack, through all the other functors, all the way into the base case.

--
Dr. Arno Schoedl · aschoedl_at_[hidden] 
Technical Director 
 
think-cell Software GmbH · Invalidenstr. 34 · 10115 Berlin, Germany 
http://www.think-cell.com · phone [phone] · toll-free (US) [phone]
Directors: Dr. Markus Hannebauer, Dr. Arno Schoedl · Amtsgericht Charlottenburg, HRB 85229