# Do sorted ranges have any special properties?

Andrei Alexandrescu SeeWebsiteForEmail at erdani.org
Mon Jul 26 22:24:15 PDT 2010

```Steven Schveighoffer wrote:
> 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).
>>>
>>> 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")

We just need to do the STL trick of re-exposing the template argument
from within the template:

struct SortedRange(alias _less)
{
alias binaryFun!_less less;
...
}

Clients will use SomeType.less.

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

I was considering disabling that by having SortedRange's operators

> 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?

That's pretty brutal :o).

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

I agree that assumeSorted is somewhat evanescent. I'm still undecided
whether it deserves a place in Phobos or not.

Andrei
```