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.

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.length)`) 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.gallopBackwards` to find the left boundary and `SearchPolicy.gallop` 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.

License

Boost License 1.0.

API Documentation

Struct std.range.SortedRange

Struct SortedRange

Properties

Methods

Alias SortedRange

Parameters

pred

opt

Example

Example

Example

Authors

License

Struct `std.range.SortedRange`