Do sorted ranges have any special properties?
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).
>>> 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
>>> 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
> 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 = 999999; // probably no longer sorted
> x.find(999999); // probably doesn't work.
I was considering disabling that by having SortedRange's operators
return rvalues instead of lvalues.
> And there are other subtle ways to break it in ways that you couldn't
> even program assumeSorted to deal with:
> arr = 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.
More information about the Digitalmars-d