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
