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)); assert(r1.release() == [ 64, 52, 42, 3, 2, 1 ]);
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
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)]));
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.