Do sorted ranges have any special properties?

[Andrei Alexandrescu]

Tomek Sowin'ski wrote:
> Andrei Alexandrescu wrote:
> 
>> I'm trying to find justifications for keeping assumeSorted and friends
>> within Phobos. Background: assumeSorted(r) where r is some range returns
>> a value that wraps r and clarifies to the caller that it can assume r
>> has been sorted.
>>
>> The obvious use case in Phobos is that find(haystack, needle) can
>> proceed faster if haystack == assumeSorted(something).
>>
>> The nicest way to go about this is to make the type returned by
>> assumeSorted a kind of "range with benefits". That is, it would
>> implement all range primitives, plus a few more primitives that are
>> advantageous for sorted ranges. Question is: what are those? What kind
>> of cool primitives could a sorted range define?
>>
>> Here are a few I can think of:
>>
>> find -> uses binary search if random-access, or at least early stopping
>> otherwise.
>>
>> minElement -> r.front
>>
>> maxElement -> r.back
>>
>> topN -> essentially does nothing
>>
>> median -> r[r.length / 2]
>>
>> Such functions could have free counterparts in std.algorithm. The free
>> functions check whether the range already implements the fast functions
>> and uses them transparently if present. So then we have e.g. find()
>> which works in linear time for most ranges, but logarithmic time on
>> random-access sorted ranges.
> 
> Sort of trivial, but I'd like to see the predicate with which it's sorted.

Thanks for your feedback. Yah, that's a given.

> Also, I can't stop thinking that it's stand-alone find()'s job utilize 
> whatever features the range has (be it random access, sortedness, or 
> anything else) to execute fast, not the passed in range's.

Good point, though that reintroduces the question of comparing find's 
predicate with SortedRange's predicate.

> Checking for a member find() sounds good but doesn't have anything specific 
> to do with the range being sorted. Any range could define its find() to 
> special-case on its structure.

And that's not bad I think. If the range feels it has defined enough 
structure to implement fast find, maybe find should defer to it. I'm 
unclear about the best strategy here.

> BTW, would it be a big deal if sort() returned assumeSorted!Range? Many uses 
> are a re-sort + binary search combo.

Yah, that would be great.


Andrei