std.algorithm
This module is a port of a growing fragment of the algorithm header in Alexander Stepanov's Standard Template Library.Author:
Andrei Alexandrescu
- void swap(T)(ref T lhs, ref T rhs);
- Swaps lhs and rhs.
- template partition(alias compare)
- Implements C.A.R. Hoare's
partition algorithm. Specifically, reorders the range [left, right) such that everything strictly smaller
(according to the predicate compare) than *mid
is to the left of the returned pointer, and everything else is at the
right of the returned pointer.
Precondition:
left == mid && mid == right || left <= mid && mid < right.
Returns:
If left == right, returns left. Otherwise, return a value p such that the following three conditions are simultaneously true:- *p == *mid
- compare(*p1, *p) for all p1 in [left, p)
- !compare(*p2, *p) for all p2 in [p, right)
Example:
auto a = [3, 3, 2].dup; p = partition!(less)(a.ptr, a.ptr, a.ptr + a.length); assert(p == a.ptr + 1 && a == [2, 3, 3]);
- template partition(T)
- T partition(T left, T mid, T right);
- template nthElement(alias compare)
- Reorders the range [b, e) such that
nth points to the element that would fall there if the
range were fully sorted. Effectively, it finds the nth smallest
(according to compare) element in the range [b,
e).
Example:
auto v = ([ 25, 7, 9, 2, 0, 5, 21 ]).dup; auto n = 4; nthElement!(less)(v.ptr, v.ptr + n, v.ptr + v.length); assert(v[n] == 9);
- template nthElement(T)
- void nthElement(T b, T nth, T e);
- void reverse(T)(T range);
- Reverses range in-place.
- template sort(alias comp)
- Sorts a random-access range according to predicate comp,
which must be a function name.
Example:
int[] array = ([ 1, 2, 3, 4 ]).dup; sort!(greater)(array); assert(array == [ 4, 3, 2, 1 ]); bool myComp(int x, int y) { return x < y; } sort!(myComp)(array); assert(array == [ 1, 2, 3, 4 ]);
- template sort(invariant(char)[] comp)
- Sorts a random-access range according to predicate comp,
expressed as a string. The string can use the names "a" and "b" for
the two elements being compared.
Example:
int[] array = ([ 1, 2, 3, 4 ]).dup; sort!("a > b")(array); assert(array == [ 4, 3, 2, 1 ]);
- template isSorted(alias comp)
- Checks whether a random-access range is sorted according to the
comparison operation comp.
Example:
int[] arr = ([4, 3, 2, 1]).dup; assert(!isSorted!(less)(arr)); sort!(less)(arr); assert(isSorted!(less)(arr));