View source code Display the source code in std/range.d from which this page was generated on github. Improve this page 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. Page wiki View or edit the community-maintained wiki page associated with this page.

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 std.algorithm.sorting.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 described below.

Properties

Name Type Description
empty [get] bool Range primitives.
front [get] ref Range primitives.

Methods

Name Description
popFront Range primitives.
release Releases the controlled range and returns it.

Templates

Name Description
contains 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. See also STL's binary_search.
equalRange 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. See also STL's equal_range.
groupBy Returns a range of subranges of elements that are equivalent according to the sorting relation.
lowerBound 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. See also STL's lower_bound.
trisect 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 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.

Example

import std.algorithm : sort;
auto a = [ 1, 2, 3, 42, 52, 64 ];
auto r = assumeSorted(a);
assert(r.contains(3));
assert(!r.contains(32));
auto r1 = sort!"a > b"(a);
assert(r1.contains(3));
assert(!r1.contains(32));
assert(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 sortedness, SortedRange will work erratically. 

import std.algorithm : 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

Authors

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

License

Boost License 1.0.

Comments