On Tue, Sep 2, 2008 at 8:47 AM, Arno Schödl <aschoedl@think-cell.com> 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