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.

  1. struct SortedRange(Range, alias pred = "a < b", SortedRangeOptions opt = SortedRangeOptions.assumeSorted)
  2. template SortedRange(Range, alias pred = "a < b", SortedRangeOptions opt = SortedRangeOptions.assumeSorted)
    template SortedRange (
    Range
    alias pred = "a < b"
    SortedRangeOptions opt = SortedRangeOptions.assumeSorted
    ) if (
    isInstanceOf!(SortedRange, Range)
    ) {}

Examples

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)]));

Meta