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

From: Thorsten Ottosen (tottosen_at_[hidden])
Date: 2006-02-03 15:33:00

David Abrahams wrote:
> Thorsten Ottosen <tottosen_at_[hidden]> writes:
> 
> 
>>David Abrahams wrote:
>>
>>>Thorsten Ottosen <tottosen_at_[hidden]> writes:
>>
>>>>>There is also the issue of O(1) size, for which you have not got
>>>>>support in your concept hierarchy.  
>>>>
>>>>Did I forget to mention this? Anyway, size() is now O(1). If you want
>>>>a generic version, dictance(rng) is supplied instead.
>>>
>>>
>>>That's not what I mean.  Is there a way to distinguish, at
>>>compile-time, a range that has support for O(1) size from one that
>>>does not?  One needs that for important "benefit and
>>>beauty"-destroying optimzations that you dislike so.
>>
>>ok, if range_category<R>::type is convertible to 
>>std::random_access_iterator_tag, then you may call boost::size(rng)
> 
> 
> There are non-random-access ranges/containers that have O(1) size.

That is true that eg. std::list<T>::size() might be O(1).

But how do you detect that? (A: you can't).

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.

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

>>>>>And then there's property maps.
>>>>
>>>>How do they relate to this?
>>>
>>>
>>>They're an important part of a generalized range concept.
>>
>>perhaps, but its hard for me to see how and why they are it.
>>how do you imagine that property maps would affect the
>>interface of range-based algorithms?
>>
>>isn't range concepts orthogonal to PMs?
> 
> 
> 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. 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.

-Thorsten