Re: [boost] lifetime of ranges vs. iterators

From: Arno Schödl (aschoedl_at_[hidden])
Date: 2008-09-01 17:35:58

I fixed filter_range::begin() and filter_range::end() as you said. iterator::equal was still exponential, but can be fixed by only comparing begin(). I think the exponential cases are now gone.

Most things are still quadratic in the stack size, though... end() for example constructs a parameter of size N-1, which to be constructed, must construct a parameter of size N-2 and so on. NRVO does not help, as far as I understand it. You would need "upward" NRVO, constructing parameters right into the respective members. Instead of passing a pointer to the function where it wants the return value to be constructed (NRVO), the caller would need to get a pointer from the callee where the callee wants its parameters constructed. I don't think compilers do that, at least not reliably enough to build a whole paradigm on it:-(

> [btw, for long chains of filter and map iterators it is not really a
> problem because you can always transform them exactly to one each of
> map and filter iterator]

That's why the problem occurred to me looking at difference_iterator.
 
------

struct both_end {};

template<class Iter, class F>
struct filter_iterator : iterator_facade<blah,blah...> {  
  filter_iterator(associated_range<Iter>::type const& rng, F f ) :
   m_range(rng), m_f(f) {}

  filter_iterator(iter e, F f, both_end ) :
   m_range(e,e), m_f(f) {} // if m_range takes e by value, e is expanded twice here, but no more, so no problem
private:
  void increment() {
      while(!m_f(front(m_range))
            m_range = rest(m_range); 
              // = associated_range<Iter>::type( next( m_range.begin() ), m_range.end() ) 
              // o.k., only recurses on m_range.begin()
  }

  reference dereference() const {
     // problem: front(x) is defined as *begin(x);
     // what if the reference returned by
     // begin(m_range) is invalidated when the
     // iterator goes out of scope? Yes, it
     // happens and I got bitten at least once.
     // We need a trait.
     return front(m_range);
  }

  bool equal(filter_iterator const&rhs) {
        return begin(rhs.m_range) == begin(m_range);
         // BAD:        && end(rhs.m_range) == end(m_range);
  }

   associated_range<Iter>::type m_range;
   F m_f; // use compressed pair here
};

template<class R, class F>
struct filter_range {
  typedef filter_iterator<range_iterator<R>::type, F> iterator;

  iterator begin() const{
       return iterator(m_range, m_f);
  }

  iterator end() const{
       return iterator(end(m_range), m_f, both_end() );
  }

   R m_range;
   F m_f;  // use compressed pair
};

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