Do sorted ranges have any special properties?

[Tomek Sowiński]

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.

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.

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.

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

 
Tomek