Do sorted ranges have any special properties?

[Lutger]

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

I think the best justification is not in Phobos alone, but having a standard way 
of signaling that a range is sorted. If this is not in Phobos, other authors 
will have to use their own ways of communicating this precondition to the 
client. sortedness is general and useful enough.
 
> 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

I agree with Tomek Sowinski here, only the predicate is needed and perhaps a way 
of retrieving the original range. A small assumeSorted range seems more 
consistent with the general ranges approach.