Struct std.range.SortedRange
Represents a sorted range. In addition to the regular range
primitives, supports additional operations that take advantage of the
ordering, such as merge and binary search. To obtain a SortedRange
from an unsorted range r
, use
sort
which sorts r
in place and returns the
corresponding SortedRange
. To construct a SortedRange
from a range
r
that is known to be already sorted, use assumeSorted
.
struct SortedRange(Range, alias pred, SortedRangeOptions opt = SortedRangeOptions .assumeSorted)
if (isInputRange!Range && !isInstanceOf!(SortedRange, Range));
alias SortedRange(Range, alias pred, SortedRangeOptions opt = SortedRangeOptions .assumeSorted)
= SortedRange!(Unqual!(typeof(Range._input)),pred,opt);
Struct SortedRange
Properties
Name | Type | Description |
---|---|---|
back [get]
|
auto | Range primitives. |
empty [get]
|
bool | Range primitives. |
front [get]
|
auto | Range primitives. |
save [get]
|
auto | Range primitives. |
Methods
Name | Description |
---|---|
contains
(value)
|
Returns true if and only if value can be found in range , which is assumed to be sorted. Performs Ο(log(r )
evaluations of pred .
|
equalRange
(value)
|
Returns the subrange containing all elements e for which both pred(e, value) and pred(value, e) evaluate to false (e.g.,
if pred is "less than", returns the portion of the range with
elements equal to value ). Uses a classic binary search with
interval halving until it finds a value that satisfies the condition,
then uses SearchPolicy to find the left boundary
and SearchPolicy to find the right boundary. These
policies are justified by the fact that the two boundaries are likely
to be near the first found value (i.e., equal ranges are relatively
small). Completes the entire search in Ο(log(n) ) time.
|
groupBy
()
|
Returns a range of subranges of elements that are equivalent according to the sorting relation. |
lowerBound
(value)
|
This function uses a search with policy sp to find the
largest left subrange on which pred(x, value) is true for
all x (e.g., if pred is "less than", returns the portion of
the range with elements strictly smaller than value ). The search
schedule and its complexity are documented in
SearchPolicy .
|
opBinaryRight
(value)
|
Like contains , but the value is specified before the range.
|
opIndex
(i)
|
Range primitives. |
opSlice
(a, b)
|
Range primitives. |
popBack
()
|
Range primitives. |
popFront
()
|
Range primitives. |
release
()
|
Releases the controlled range and returns it. |
trisect
(value)
|
Returns a tuple r such that r[0] is the same as the result
of lowerBound(value) , r[1] is the same as the result of equalRange(value) , and r[2] is the same as the result of upperBound(value) . The call is faster than computing all three
separately. Uses a search schedule similar to equalRange . Completes the entire search in Ο(log(n) ) time.
|
upperBound
(value)
|
This function searches with policy sp to find the largest right
subrange on which pred(value, x) is true for all x
(e.g., if pred is "less than", returns the portion of the range
with elements strictly greater than value ). The search schedule
and its complexity are documented in SearchPolicy .
|
Alias SortedRange
Parameters
Name | Description |
---|
pred
The predicate used to define the sortedness
opt
Controls how strongly the range is checked for sortedness.
Will only be used for RandomAccessRanges
.
Will not be used in CTFE.
Example
import std .algorithm .sorting : sort;
auto a = [ 1, 2, 3, 42, 52, 64 ];
auto r = assumeSorted(a);
assert(r .contains(3));
assert(!(32 in r));
auto r1 = sort!"a > b"(a);
assert(3 in r1);
assert(!r1 .contains(32));
writeln(r1 .release()); // [64, 52, 42, 3, 2, 1]
Example
SortedRange
could accept ranges weaker than random-access, but it
is unable to provide interesting functionality for them. Therefore,
SortedRange
is currently restricted to random-access ranges.
No copy of the original range is ever made. If the underlying range is
changed concurrently with its corresponding SortedRange
in ways
that break its sorted-ness, SortedRange
will work erratically.
import std .algorithm .mutation : swap;
auto a = [ 1, 2, 3, 42, 52, 64 ];
auto r = assumeSorted(a);
assert(r .contains(42));
swap(a[3], a[5]); // illegal to break sortedness of original range
assert(!r .contains(42)); // passes although it shouldn't
Example
SortedRange
can be searched with predicates that do not take
two elements of the underlying range as arguments.
This is useful, if a range of structs is sorted by a member and you want to search in that range by only providing a value for that member.
import std .algorithm .comparison : equal;
static struct S { int i; }
static bool byI(A, B)(A a, B b)
{
static if (is(A == S))
return a .i < b;
else
return a < b .i;
}
auto r = assumeSorted!byI([S(1), S(2), S(3)]);
auto lessThanTwo = r .lowerBound(2);
assert(equal(lessThanTwo, [S(1)]));
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.