Do sorted ranges have any special properties?

[Andrei Alexandrescu]

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.

Other ideas?


Thanks,

Andrei