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

From: Thorsten Ottosen (tottosen_at_[hidden])
Date: 2006-02-03 18:57:54

David Abrahams wrote:
> 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).

Well, I don't personally have access to all the implementations.
This seems like overkill.

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

You mean Duff's device?

Do we have tests on all our platforms that suggests that Duffing
leads to faster code? I was told that Duffing could actually
hurt a modern optimizer.

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

And how does it affect the return type of range_based algorithms other
than replacing iterator_range with cursor_range? I still don't see the 
relevance until we have an established cursor/pm library.

-Thorsten