Display the source code in std/range/package.d from which this page was generated on github.

If you spot a problem with this page, click here to create a Bugzilla issue.

Quickly fork, edit online, and submit a pull request for this page. Requires a signed-in GitHub account. This works well for small changes. If you'd like to make larger changes you may want to consider using local clone.

Function `std.range.assumeSorted`

Assumes r is sorted by predicate pred and returns the corresponding SortedRange!(pred, R) having r as support. To keep the checking costs low, the cost is Ο(1) in release mode (no checks for sorted-ness are performed). In debug mode, a few random elements of r are checked for sorted-ness. The size of the sample is proportional Ο(log(r.length)). That way, checking has no effect on the complexity of subsequent operations specific to sorted ranges (such as binary search). The probability of an arbitrary unsorted range failing the test is very high (however, an almost-sorted range is likely to pass it). To check for sorted-ness at cost Ο(n), use isSorted.



auto auto assumeSorted(alias pred, R)
(


  R r


)


if (isInputRange!(Unqual!R));

Example

import std.algorithm.comparison : equal;

int[] a = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9];
auto p = assumeSorted(a);

assert(equal(p.lowerBound(4), [0, 1, 2, 3]));
assert(equal(p.lowerBound(5), [0, 1, 2, 3, 4]));
assert(equal(p.lowerBound(6), [0, 1, 2, 3, 4, 5]));
assert(equal(p.lowerBound(6.9), [0, 1, 2, 3, 4, 5, 6]));

Authors

Andrei Alexandrescu, David Simcha, Jonathan M Davis, and Jack Stouffer. Credit for some of the ideas in building this module goes to Leonardo Maffi.

License

Boost License 1.0.