Re: [boost] lifetime of ranges vs. iterators

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

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

We can also use a trait. Keep in mind though that from a client's standpoint, both classes are really equivalent. In fact, if you instantiate an iterator_range for one of the associated_range::iterators, you really want the associated_range because it is more efficient. Likewise, the corresponding sub_range should really derive from associated_range. In our company's library, sub_range is a trait so that sub_range( transform_range ).base() returns the base subrange. I see iterator_range along similar lines, with the semantics mattering more than the implementation.

This issue is somewhat of a side-track, though.

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

Fine with me. I am not so familiar with the boost.range stuff.

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

The current implementation runs its recursion on the range, which I find quite straightforward. So I wouldn't want to eliminate them. Renaming or replacing with free functions is fine.

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

I think you are right. I did not check what iterator_range does, it probably does the right thing.

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

> what about naming this just 'empty'?

Shame on me:-)

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

The other ctor that takes two ranges is just as special. If we can assume NRVO, it would be pretty easy to replace them with a free factory function template. That way, all special iterator_range members I introduced could be turned into free functions.

-Arno

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