Do sorted ranges have any special properties?

[Steven Schveighoffer]

On Sun, 25 Jul 2010 15:44:36 -0400, Tomek Sowiński <just at ask.me> 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.

I think the "range" returned by assumeSorted has a predicate alias in it  
already (which defaults to "a < b")

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

Yeah, that would be good.

The only problem I see with this is that "sortedness" is broken quite  
easily in ways that does not remove the assumeSorted type.  For example,  
if assumeSorted just forwards its underlying range's methods, then given  
an array arr:

auto x = assumeSorted(arr.sort);

x[0] = 999999; // probably no longer sorted

x.find(999999); // probably doesn't work.

And there are other subtle ways to break it in ways that you couldn't even  
program assumeSorted to deal with:

arr[0] = 999999; // how does x detect this?

I feel like assumeSorted is something that's temporary.  It can only be  
used as a parameter or return decoration, but as soon as you assign it to  
a variable, it's gone.  Not sure if that can work.  User-defined  
attributes would be nice here :)

-Steve