Re: [boost] lifetime of ranges vs. iterators

From: Giovanni Piero Deretta (gpderetta_at_[hidden])
Date: 2008-09-02 07:40:12

On Tue, Sep 2, 2008 at 8:47 AM, Arno Schödl <aschoedl_at_[hidden]> wrote:
>> 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.

The reason to use a trait it to make it easier to adapt existing
ranges. Also, containers are ranges, but do not have your additional
functions, so you need to explicitly wrap them in iterator_ranges
before wrapping them in another adapter range. With associated_range,
the wrapping comes implicitly for free.

>
> 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:

I'll add some comments inline in the code.

>
> 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;
>   }

Increment is fine. Instead of advance you could have an overloaded
increment that takes a size_t parameter for random access ranges (BTW,
boost.range has increment_{begin|end}).

I think that these functions should all be friend functions, with
reasonable default. The reason is the usual one: adaptability of
existing ranges.

>
>   // 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):

The fact that they are O(N) is not that important. The important thing
is that the stack growth is not exponential.

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

good question. IMHO constness should be completely determined by the
underlying container (if any).

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

what about naming this just 'empty'?

>
>   // 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 )
>   {}

eh, here comes the problem. The assumption that underlying range
supports create_end_tag is a strong one. You can do it in your scheme,
because all ranges are iterator_ranges, but I do not think it works
well in practice.

One (ugly) way out is making support for this tag part of the range
concept i.e. require that associated_range returns a range that
supports it; this rules out std::pair as an associated range. Another
solution is somehow detecting the support for create_end_tag.

<snip>

>
> 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.
>

No no, I see the connection and I sort-of-like the solution. But I
think that having a trait plus customization functions found via ADL
is better. Also, there must be a better (i.e. less ugly) way than
using the create_end_tag.

-- 
gpd