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@think-cell.com Technical Director think-cell Software GmbH · Invalidenstr. 34 · 10115 Berlin, Germany http://www.think-cell.com · phone +49-30-666473-10 · toll-free (US) +1-800-891-8091 Directors: Dr. Markus Hannebauer, Dr. Arno Schoedl · Amtsgericht Charlottenburg, HRB 85229