Re: [boost] [Range] initial feedback on return values of algorithms

From: David Abrahams (dave_at_[hidden])
Date: 2006-02-03 16:56:40

Thorsten Ottosen <tottosen_at_[hidden]> writes:

> David Abrahams wrote:
>> Thorsten Ottosen <tottosen_at_[hidden]> writes:
>
> That is true that eg. std::list<T>::size() might be O(1).
>
> But how do you detect that? (A: you can't).

Sure you can; you just look at your implementation and if it is O(1)
you write a specialization of the metafunction (or whatever).

> IIRC, you where one of the people who were very conserned about
> the performance discontinuity induced by boost::size() is its
> original form. I now totally agree that such discontinuities
> are more harmful than useful.

Good.

> Anyway, what issue are you really talking about. I must
> be missing something.

If there's an O(1) size available you can do loop unrolling; otherwise
you have to test the iterators every time through the loop.

>> No, a more general range concept is a property map and two cursors,
>> rather than just two iterators.
>
> Ok, but it still appears to me that you basically replace iterators
> with cursors. 

No, with cursors + a property map.  Cursors don't access data.

> Boost.range is merely a utility layer on top of a more 
> generic fabric. It shouldn't matter what lies underneith. For example, 
> if I write
>
>    boost::unique( rng )
>
> I don't care about if it is cursors or iterators doing the hard work.
>
> Unlike some, I fully support your and Dietmars efforts to develop the 
> cursor/pm abstraction. But I don't see how it is relevant to boost.range 
> right now.

Look at the big picture.  A generalized algorithm suite will be
written in terms of property maps and cursors, not in terms of
iterators.

-- 
Dave Abrahams
Boost Consulting
www.boost-consulting.com