std.algorithm
Tutorial on ranges Many functions in this module are parameterized with a function or a predicate. The predicate may be passed either as a function name, a delegate name, a functor name, or a compiletime string. The string may consist of any legal D expression that uses the symbol a (for unary functions) or the symbols a and b (for binary functions). These names will NOT interfere with other homonym symbols in user code because they are evaluated in a different context. The default for all binary comparison predicates is "a == b" for unordered operations and "a < b" for ordered operations.
Example:
int[] a = ...; static bool greater(int a, int b) { return a > b; } sort!(greater)(a); // predicate as alias sort!("a > b")(a); // predicate as string // (no ambiguity with array name) sort(a); // no predicate, "a < b" is implicit
Function Name  Description 

Searching  
all  all!"a > 0"([1, 2, 3, 4]) returns true because all elements are positive 
any  any!"a > 0"([1, 2, 3, 4]) returns true because at least one element is positive 
balancedParens  balancedParens("((1 + 1) / 2)") returns true because the string has balanced parentheses. 
boyerMooreFinder  find("hello world", boyerMooreFinder("or")) returns "orld" using the BoyerMoore algorithm. 
canFind  canFind("hello world", "or") returns true. 
count  Counts elements that are equal to a specified value or satisfy a predicate. count([1, 2, 1], 1) returns 2 and count!"a < 0"([1, 3, 0]) returns 1. 
countUntil  countUntil(a, b) returns the number of steps taken in a to reach b; for example, countUntil("hello!", "o") returns 4. 
commonPrefix  commonPrefix("parakeet", "parachute") returns "para". 
endsWith  endsWith("rocks", "ks") returns true. 
find  find("hello world", "or") returns "orld" using linear search. (For binary search refer to std.range.sortedRange.) 
findAdjacent  findAdjacent([1, 2, 3, 3, 4]) returns the subrange starting with two equal adjacent elements, i.e. [3, 3, 4]. 
findAmong  findAmong("abcd", "qcx") returns "cd" because 'c' is among "qcx". 
findSkip  If a = "abcde", then findSkip(a, "x") returns false and leaves a unchanged, whereas findSkip(a, 'c') advances a to "cde" and returns true. 
findSplit  findSplit("abcdefg", "de") returns the three ranges "abc", "de", and "fg". 
findSplitAfter  findSplitAfter("abcdefg", "de") returns the two ranges "abcde" and "fg". 
findSplitBefore  findSplitBefore("abcdefg", "de") returns the two ranges "abc" and "defg". 
minCount  minCount([2, 1, 1, 4, 1]) returns tuple(1, 3). 
minPos  minPos([2, 3, 1, 3, 4, 1]) returns the subrange [1, 3, 4, 1], i.e., positions the range at the first occurrence of its minimal element. 
mismatch  mismatch("parakeet", "parachute") returns the two ranges "keet" and "chute". 
skipOver  Assume a = "blah". Then skipOver(a, "bi") leaves a unchanged and returns false, whereas skipOver(a, "bl") advances a to refer to "ah" and returns true. 
startsWith  startsWith("hello, world", "hello") returns true. 
until  Lazily iterates a range until a specific value is found. 
Comparison  
among  Checks if a value is among a set of values, e.g. if (v.among(1, 2, 3)) // `v` is 1, 2 or 3 
cmp  cmp("abc", "abcd") is 1, cmp("abc", "aba") is 1, and cmp("abc", "abc") is 0. 
equal  Compares ranges for elementbyelement equality, e.g. equal([1, 2, 3], [1.0, 2.0, 3.0]) returns true. 
levenshteinDistance  levenshteinDistance("kitten", "sitting") returns 3 by using the Levenshtein distance algorithm. 
levenshteinDistanceAndPath  levenshteinDistanceAndPath("kitten", "sitting") returns tuple(3, "snnnsni") by using the Levenshtein distance algorithm. 
max  max(3, 4, 2) returns 4. 
min  min(3, 4, 2) returns 2. 
mismatch  mismatch("oh hi", "ohayo") returns tuple(" hi", "ayo"). 
Iteration  
filter  filter!"a > 0"([1, 1, 2, 0, 3]) iterates over elements 1 and 2. 
filterBidirectional  Similar to filter, but also provides back and popBack at a small increase in cost. 
group  group([5, 2, 2, 3, 3]) returns a range containing the tuples tuple(5, 1), tuple(2, 2), and tuple(3, 2). 
joiner  joiner(["hello", "world!"], "; ") returns a range that iterates over the characters "hello; world!". No new string is created  the existing inputs are iterated. 
map  map!"2 * a"([1, 2, 3]) lazily returns a range with the numbers 2, 4, 6. 
reduce  reduce!"a + b"([1, 2, 3, 4]) returns 10. 
splitter  Lazily splits a range by a separator. 
sum  Same as reduce, but specialized for accurate summation. 
uniq  Iterates over the unique elements in a range, which is assumed sorted. 
Sorting  
completeSort  If a = [10, 20, 30] and b = [40, 6, 15], then completeSort(a, b) leaves a = [6, 10, 15] and b = [20, 30, 40]. The range a must be sorted prior to the call, and as a result the combination std.range.chain(a, b) is sorted. 
isPartitioned  isPartitioned!"a < 0"([1, 2, 1, 0, 2]) returns true because the predicate is true for a portion of the range and false afterwards. 
isSorted  isSorted([1, 1, 2, 3]) returns true. 
makeIndex  Creates a separate index for a range. 
nextPermutation  Computes the next lexicographically greater permutation of a range inplace. 
nextEvenPermutation  Computes the next lexicographically greater even permutation of a range inplace. 
partialSort  If a = [5, 4, 3, 2, 1], then partialSort(a, 3) leaves a[0 .. 3] = [1, 2, 3]. The other elements of a are left in an unspecified order. 
partition  Partitions a range according to a predicate. 
partition3  Partitions a range in three parts (less than, equal, greater than the given pivot). 
schwartzSort  Sorts with the help of the Schwartzian transform. 
sort  Sorts. 
topN  Separates the top elements in a range. 
topNCopy  Copies out the top elements of a range. 
Set operations  
cartesianProduct  Computes Cartesian product of two ranges. 
largestPartialIntersection  Copies out the values that occur most frequently in a range of ranges. 
largestPartialIntersectionWeighted  Copies out the values that occur most frequently (multiplied by pervalue weights) in a range of ranges. 
nWayUnion  Computes the union of a set of sets implemented as a range of sorted ranges. 
setDifference  Lazily computes the set difference of two or more sorted ranges. 
setIntersection  Lazily computes the intersection of two or more sorted ranges. 
setSymmetricDifference  Lazily computes the symmetric set difference of two or more sorted ranges. 
setUnion  Lazily computes the set union of two or more sorted ranges. 
Mutation  
bringToFront  If a = [1, 2, 3] and b = [4, 5, 6, 7], bringToFront(a, b) leaves a = [4, 5, 6] and b = [7, 1, 2, 3]. 
copy  Copies a range to another. If a = [1, 2, 3] and b = new int[5], then copy(a, b) leaves b = [1, 2, 3, 0, 0] and returns b[3 .. $]. 
fill  Fills a range with a pattern, e.g., if a = new int[3], then fill(a, 4) leaves a = [4, 4, 4] and fill(a, [3, 4]) leaves a = [3, 4, 3]. 
initializeAll  If a = [1.2, 3.4], then initializeAll(a) leaves a = [double.init, double.init]. 
move  move(a, b) moves a into b. move(a) reads a destructively. 
moveAll  Moves all elements from one range to another. 
moveSome  Moves as many elements as possible from one range to another. 
remove  Removes elements from a range inplace, and returns the shortened range. 
reverse  If a = [1, 2, 3], reverse(a) changes it to [3, 2, 1]. 
strip  Strips all leading and trailing elements equal to a value, or that satisfy a predicate. If a = [1, 1, 0, 1, 1], then strip(a, 1) and strip!(e => e == 1)(a) returns [0]. 
stripLeft  Strips all leading elements equal to a value, or that satisfy a predicate. If a = [1, 1, 0, 1, 1], then stripLeft(a, 1) and stripLeft!(e => e == 1)(a) returns [0, 1, 1]. 
stripRight  Strips all trailing elements equal to a value, or that satisfy a predicate. If a = [1, 1, 0, 1, 1], then stripRight(a, 1) and stripRight!(e => e == 1)(a) returns [1, 1, 0]. 
swap  Swaps two values. 
swapRanges  Swaps all elements of two ranges. 
uninitializedFill  Fills a range (assumed uninitialized) with a value. 
Source: std/algorithm.d
 template map(fun...) if (fun.length >= 1)

Implements the homonym function (also known as transform) present in many languages of functional flavor. The call map!(fun)(range) returns a range of which elements are obtained by applying fun(x) left to right for all x in range. The original ranges are not changed. Evaluation is done lazily.Examples:
int[] arr1 = [ 1, 2, 3, 4 ]; int[] arr2 = [ 5, 6 ]; auto squares = map!(a => a * a)(chain(arr1, arr2)); assert(equal(squares, [ 1, 4, 9, 16, 25, 36 ]));
Examples:Multiple functions can be passed to map. In that case, the element type of map is a tuple containing one element for each function.auto sums = [2, 4, 6, 8]; auto products = [1, 4, 9, 16]; size_t i = 0; foreach (result; [ 1, 2, 3, 4 ].map!("a + a", "a * a")) { assert(result[0] == sums[i]); assert(result[1] == products[i]); ++i; }
 template reduce(fun...) if (fun.length >= 1)
 auto reduce(Args...)(Args args) if (Args.length > 0 && Args.length <= 2 && isIterable!(Args[$  1]));Implements the homonym function (also known as accumulate, compress, inject, or foldl) present in various programming languages of functional flavor. The call reduce!(fun)(seed, range) first assigns seed to an internal variable result, also called the accumulator. Then, for each element x in range, result = fun(result, x) gets evaluated. Finally, result is returned. The oneargument version reduce!(fun)(range) works similarly, but it uses the first element of the range as the seed (the range must be nonempty). See also: sum is similar to reduce!((a, b) => a + b) that offers precise summing of floating point numbers.Examples:Many aggregate range operations turn out to be solved with reduce quickly and easily. The example below illustrates reduce's remarkable power and flexibility.
import std.math : approxEqual; int[] arr = [ 1, 2, 3, 4, 5 ]; // Sum all elements auto sum = reduce!((a,b) => a + b)(0, arr); assert(sum == 15); // Sum again, using a string predicate with "a" and "b" sum = reduce!"a + b"(0, arr); assert(sum == 15); // Compute the maximum of all elements auto largest = reduce!(max)(arr); assert(largest == 5); // Max again, but with Uniform Function Call Syntax (UFCS) largest = arr.reduce!(max); assert(largest == 5); // Compute the number of odd elements auto odds = reduce!((a,b) => a + (b & 1))(0, arr); assert(odds == 3); // Compute the sum of squares auto ssquares = reduce!((a,b) => a + b * b)(0, arr); assert(ssquares == 55); // Chain multiple ranges into seed int[] a = [ 3, 4 ]; int[] b = [ 100 ]; auto r = reduce!("a + b")(chain(a, b)); assert(r == 107); // Mixing convertible types is fair game, too double[] c = [ 2.5, 3.0 ]; auto r1 = reduce!("a + b")(chain(a, b, c)); assert(approxEqual(r1, 112.5)); // To minimize nesting of parentheses, Uniform Function Call Syntax can be used auto r2 = chain(a, b, c).reduce!("a + b"); assert(approxEqual(r2, 112.5));
Examples:Sometimes it is very useful to compute multiple aggregates in one pass. One advantage is that the computation is faster because the looping overhead is shared. That's why reduce accepts multiple functions. If two or more functions are passed, reduce returns a std.typecons.Tuple object with one member per passedin function. The number of seeds must be correspondingly increased.import std.math : approxEqual, sqrt; double[] a = [ 3.0, 4, 7, 11, 3, 2, 5 ]; // Compute minimum and maximum in one pass auto r = reduce!(min, max)(a); // The type of r is Tuple!(int, int) assert(approxEqual(r[0], 2)); // minimum assert(approxEqual(r[1], 11)); // maximum // Compute sum and sum of squares in one pass r = reduce!("a + b", "a + b * b")(tuple(0.0, 0.0), a); assert(approxEqual(r[0], 35)); // sum assert(approxEqual(r[1], 233)); // sum of squares // Compute average and standard deviation from the above auto avg = r[0] / a.length; auto stdev = sqrt(r[1] / a.length  avg * avg);
 auto sum(R)(R r) if (isInputRange!R && !isInfinite!R && is(typeof(r.front + r.front)));
auto sum(R, E)(R r, E seed) if (isInputRange!R && !isInfinite!R && is(typeof(seed = seed + r.front)));  Sums elements of r, which must be a finite input range. Although conceptually sum(r) is equivalent to reduce!((a, b) => a + b)(0, r), sum uses specialized algorithms to maximize accuracy, as follows.
 If ElementType!R is a floatingpoint type and R is a randomaccess range with length and slicing, then sum uses the pairwise summation algorithm.
 If ElementType!R is a floatingpoint type and R is a finite input range (but not a randomaccess range with slicing), then sum uses the Kahan summation algorithm.
 In all other cases, a simple element by element addition is done.
 void fill(Range, Value)(Range range, Value filler) if (isInputRange!Range && is(typeof(range.front = filler)));
 Fills range with a filler.Examples:
int[] a = [ 1, 2, 3, 4 ]; fill(a, 5); assert(a == [ 5, 5, 5, 5 ]);
 void fill(Range1, Range2)(Range1 range, Range2 filler) if (isInputRange!Range1 && (isForwardRange!Range2  isInputRange!Range2 && isInfinite!Range2) && is(typeof(Range1.init.front = Range2.init.front)));
 Fills range with a pattern copied from filler. The length of range does not have to be a multiple of the length of filler. If filler is empty, an exception is thrown.Examples:
int[] a = [ 1, 2, 3, 4, 5 ]; int[] b = [ 8, 9 ]; fill(a, b); assert(a == [ 8, 9, 8, 9, 8 ]);
 void uninitializedFill(Range, Value)(Range range, Value filler) if (isInputRange!Range && hasLvalueElements!Range && is(typeof(range.front = filler)));
 Fills a range with a value. Assumes that the range does not currently contain meaningful content. This is of interest for structs that define copy constructors (for all other types, fill and uninitializedFill are equivalent).uninitializedFill will only operate on ranges that expose references to its members and have assignable elements.
Example:
struct S { ... } S[] s = (cast(S*) malloc(5 * S.sizeof))[0 .. 5]; uninitializedFill(s, 42); assert(s == [ 42, 42, 42, 42, 42 ]);
 void initializeAll(Range)(Range range) if (isInputRange!Range && hasLvalueElements!Range && hasAssignableElements!Range);
 Initializes all elements of a range with their .init value. Assumes that the range does not currently contain meaningful content.initializeAll will operate on ranges that expose references to its members and have assignable elements, as well as on (mutable) strings.
Example:
struct S { ... } S[] s = (cast(S*) malloc(5 * S.sizeof))[0 .. 5]; initializeAll(s); assert(s == [ 0, 0, 0, 0, 0 ]);
 template filter(alias pred) if (is(typeof(unaryFun!pred)))

Implements the homonym function present in various programming languages of functional flavor. The call filter!(predicate)(range) returns a new range only containing elements x in range for which predicate(x) is true.Examples:
import std.math : approxEqual; int[] arr = [ 1, 2, 3, 4, 5 ]; // Sum all elements auto small = filter!(a => a < 3)(arr); assert(equal(small, [ 1, 2 ])); // Sum again, but with Uniform Function Call Syntax (UFCS) auto sum = arr.filter!(a => a < 3); assert(equal(sum, [ 1, 2 ])); // In combination with chain() to span multiple ranges int[] a = [ 3, 2, 400 ]; int[] b = [ 100, 101, 102 ]; auto r = chain(a, b).filter!(a => a > 0); assert(equal(r, [ 3, 400, 100, 102 ])); // Mixing convertible types is fair game, too double[] c = [ 2.5, 3.0 ]; auto r1 = chain(c, a, b).filter!(a => cast(int) a != a); assert(approxEqual(r1, [ 2.5 ]));
 template filterBidirectional(alias pred)

Similar to filter, except it defines a bidirectional range. There is a speed disadvantage  the constructor spends time finding the last element in the range that satisfies the filtering condition (in addition to finding the first one). The advantage is that the filtered range can be spanned from both directions. Also, std.range.retro can be applied against the filtered range.Examples:
int[] arr = [ 1, 2, 3, 4, 5 ]; auto small = filterBidirectional!("a < 3")(arr); static assert(isBidirectionalRange!(typeof(small))); assert(small.back == 2); assert(equal(small, [ 1, 2 ])); assert(equal(retro(small), [ 2, 1 ])); // In combination with chain() to span multiple ranges int[] a = [ 3, 2, 400 ]; int[] b = [ 100, 101, 102 ]; auto r = filterBidirectional!("a > 0")(chain(a, b)); assert(r.back == 102);
 void move(T)(ref T source, ref T target);
T move(T)(ref T source);  Moves source into target via a destructive copy.
 Range2 moveAll(Range1, Range2)(Range1 src, Range2 tgt) if (isInputRange!Range1 && isInputRange!Range2 && is(typeof(move(src.front, tgt.front))));
 For each element a in src and each element b in tgt in lockstep in increasing order, calls move(a, b). Returns the leftover portion of tgt. Throws an exception if there is not enough room in tgt to accommodate all of src.
Preconditions: walkLength(src) <= walkLength(tgt)
 Tuple!(Range1, Range2) moveSome(Range1, Range2)(Range1 src, Range2 tgt) if (isInputRange!Range1 && isInputRange!Range2 && is(typeof(move(src.front, tgt.front))));
 For each element a in src and each element b in tgt in lockstep in increasing order, calls move(a, b). Stops when either src or tgt have been exhausted. Returns the leftover portions of the two ranges.
 pure nothrow @trusted void swap(T)(ref T lhs, ref T rhs) if (isBlitAssignable!T && !is(typeof(lhs.proxySwap(rhs))));
 Swaps lhs and rhs. The instances lhs and rhs are moved in memory, without ever calling opAssign, nor any other function. T need not be assignable at all to be swapped.If lhs and rhs reference the same instance, then nothing is done. lhs and rhs must be mutable. If T is a struct or union, then its fields must also all be (recursivelly) mutable.
 template forward(args...)
 Forwards function arguments with saving refness.Examples:
class C { static int foo(int n) { return 1; } static int foo(ref int n) { return 2; } } int bar()(auto ref int x) { return C.foo(forward!x); } assert(bar(1) == 1); int i; assert(bar(i) == 2);
Examples:void foo(int n, ref string s) { s = null; foreach (i; 0..n) s ~= "Hello"; } // forwards all arguments which are bound to parameter tuple void bar(Args...)(auto ref Args args) { return foo(forward!args); } // forwards all arguments with swapping order void baz(Args...)(auto ref Args args) { return foo(forward!args[$/2..$], forward!args[0..$/2]); } string s; bar(1, s); assert(s == "Hello"); baz(s, 2); assert(s == "HelloHello");
 auto splitter(Range, Separator)(Range r, Separator s) if (is(typeof(ElementType!Range.init == Separator.init)) && (hasSlicing!Range && hasLength!Range  isNarrowString!Range));
 Splits a range using an element as a separator. This can be used with any narrow string type or sliceable range type, but is most popular with string types.Two adjacent separators are considered to surround an empty element in the split range. Use filter!(a => !a.empty) on the result to compress empty elements. If the empty range is given, the result is a range with one empty element. If a range with one separator is given, the result is a range with two empty elements. If splitting a string on whitespace and token compression is desired, consider using splitter without specifying a separator (see overload below). See also splitter">std.regex.splitter for a version that splits using a regular expression defined separator.Examples:
assert(equal(splitter("hello world", ' '), [ "hello", "", "world" ])); int[] a = [ 1, 2, 0, 0, 3, 0, 4, 5, 0 ]; int[][] w = [ [1, 2], [], [3], [4, 5], [] ]; assert(equal(splitter(a, 0), w)); a = [ 0 ]; assert(equal(splitter(a, 0), [ (int[]).init, (int[]).init ])); a = [ 0, 1 ]; assert(equal(splitter(a, 0), [ [], [1] ]));
 auto splitter(Range, Separator)(Range r, Separator s) if (is(typeof(Range.init.front == Separator.init.front) : bool) && (hasSlicing!Range  isNarrowString!Range) && isForwardRange!Separator && (hasLength!Separator  isNarrowString!Separator));
auto splitter(alias isTerminator, Range)(Range input) if (isForwardRange!Range && is(typeof(unaryFun!isTerminator(input.front))));  Splits a range using another range as a separator. This can be used with any narrow string type or sliceable range type, but is most popular with string types.
 auto splitter(C)(C[] s) if (isSomeChar!C);
 Lazily splits the string s into words, using whitespace as the delimiter.This function is string specific and, contrary to splitter!(std.uni.isWhite), runs of whitespace will be merged together (no empty tokens will be produced).Examples:
auto a = " a bcd ef gh "; assert(equal(splitter(a), ["a", "bcd", "ef", "gh"][]));
 auto joiner(RoR, Separator)(RoR r, Separator sep) if (isInputRange!RoR && isInputRange!(ElementType!RoR) && isForwardRange!Separator && is(ElementType!Separator : ElementType!(ElementType!RoR)));
auto joiner(RoR)(RoR r) if (isInputRange!RoR && isInputRange!(ElementType!RoR));  Lazily joins a range of ranges with a separator. The separator itself is a range. If you do not provide a separator, then the ranges are joined directly without anything in between them.Examples:
import std.conv : text; debug(std_algorithm) scope(success) writeln("unittest @", __FILE__, ":", __LINE__, " done."); static assert(isInputRange!(typeof(joiner([""], "")))); static assert(isForwardRange!(typeof(joiner([""], "")))); assert(equal(joiner([""], "xyz"), ""), text(joiner([""], "xyz"))); assert(equal(joiner(["", ""], "xyz"), "xyz"), text(joiner(["", ""], "xyz"))); assert(equal(joiner(["", "abc"], "xyz"), "xyzabc")); assert(equal(joiner(["abc", ""], "xyz"), "abcxyz")); assert(equal(joiner(["abc", "def"], "xyz"), "abcxyzdef")); assert(equal(joiner(["Mary", "has", "a", "little", "lamb"], "..."), "Mary...has...a...little...lamb")); assert(equal(joiner(["abc", "def"]), "abcdef"));
 auto uniq(alias pred = "a == b", Range)(Range r) if (isInputRange!Range && is(typeof(binaryFun!pred(r.front, r.front)) == bool));
 Iterates unique consecutive elements of the given range (functionality akin to the uniq system utility). Equivalence of elements is assessed by using the predicate pred, by default "a == b". If the given range is bidirectional, uniq also yields a bidirectional range.Examples:
int[] arr = [ 1, 2, 2, 2, 2, 3, 4, 4, 4, 5 ]; assert(equal(uniq(arr), [ 1, 2, 3, 4, 5 ][]));
 struct Group(alias pred, R) if (isInputRange!R);
Group!(pred, Range) group(alias pred = "a == b", Range)(Range r);  Similarly to uniq, group iterates unique consecutive elements of the given range. The element type is Tuple!(ElementType!R, uint) because it includes the count of equivalent elements seen. Equivalence of elements is assessed by using the predicate pred, by default "a == b".Examples:
int[] arr = [ 1, 2, 2, 2, 2, 3, 4, 4, 4, 5 ]; assert(equal(group(arr), [ tuple(1, 1u), tuple(2, 4u), tuple(3, 1u), tuple(4, 3u), tuple(5, 1u) ][]));
 InputRange find(alias pred = "a == b", InputRange, Element)(InputRange haystack, Element needle) if (isInputRange!InputRange && is(typeof(binaryFun!pred(haystack.front, needle)) : bool));
 Finds an individual element in an input range. Elements of haystack are compared with needle by using predicate pred. Performs Ο(walkLength(haystack)) evaluations of pred.To find the last occurrence of needle in haystack, call find(retro(haystack), needle). See std.range.retro.Parameters:
InputRange haystack The range searched in. Element needle The element searched for. Constraints: isInputRange!InputRange && is(typeof(binaryFun!pred(haystack.front, needle) : bool))
Returns:haystack advanced such that binaryFun!pred(haystack.front, needle) is true (if no such position exists, returns haystack after exhaustion).SeeAlso:Examples:import std.container : SList; assert(find("hello, world", ',') == ", world"); assert(find([1, 2, 3, 5], 4) == []); assert(equal(find(SList!int(1, 2, 3, 4, 5)[], 4), SList!int(4, 5)[])); assert(find!"a > b"([1, 2, 3, 5], 2) == [3, 5]); auto a = [ 1, 2, 3 ]; assert(find(a, 5).empty); // not found assert(!find(a, 2).empty); // found // Caseinsensitive find of a string string[] s = [ "Hello", "world", "!" ]; assert(!find!("toLower(a) == b")(s, "hello").empty);
 R1 find(alias pred = "a == b", R1, R2)(R1 haystack, R2 needle) if (isForwardRange!R1 && isForwardRange!R2 && is(typeof(binaryFun!pred(haystack.front, needle.front)) : bool) && !isRandomAccessRange!R1);
 Finds a forward range in another. Elements are compared for equality. Performs Ο(walkLength(haystack) * walkLength(needle)) comparisons in the worst case. Specializations taking advantage of bidirectional or random access (where present) may accelerate search depending on the statistics of the two ranges' content.Parameters:
R1 haystack The range searched in. R2 needle The range searched for. Constraints: isForwardRange!R1 && isForwardRange!R2 && is(typeof(binaryFun!pred(haystack.front, needle.front) : bool))
Returns:haystack advanced such that needle is a prefix of it (if no such position exists, returns haystack advanced to termination).Examples:import std.container : SList; assert(find("hello, world", "World").empty); assert(find("hello, world", "wo") == "world"); assert([1, 2, 3, 4].find(SList!int(2, 3)[]) == [2, 3, 4]);
 Tuple!(Range, size_t) find(alias pred = "a == b", Range, Ranges...)(Range haystack, Ranges needles) if (Ranges.length > 1 && is(typeof(startsWith!pred(haystack, needles))));
struct BoyerMooreFinder(alias pred, Range);
BoyerMooreFinder!(binaryFun!pred, Range) boyerMooreFinder(alias pred = "a == b", Range)(Range needle) if (isRandomAccessRange!Range  isSomeString!Range);  Finds two or more needles into a haystack. The predicate pred is used throughout to compare elements. By default, elements are compared for equality.BoyerMooreFinder allocates GC memory.Parameters:
Range haystack The target of the search. Must be an input range. If any of needles is a range with elements comparable to elements in haystack, then haystack must be a forward range such that the search can backtrack. Ranges needles One or more items to search for. Each of needles must be either comparable to one element in haystack, or be itself a forward range with elements comparable with elements in haystack. Returns:A tuple containing haystack positioned to match one of the needles and also the 1based index of the matching element in needles (0 if none of needles matched, 1 if needles[0] matched, 2 if needles[1] matched...). The first needle to be found will be the one that matches. If multiple needles are found at the same spot in the range, then the shortest one is the one which matches (if multiple needles of the same length are found at the same spot (e.g "a" and 'a'), then the leftmost of them in the argument list matches). The relationship between haystack and needles simply means that one can e.g. search for individual ints or arrays of ints in an array of ints. In addition, if elements are individually comparable, searches of heterogeneous types are allowed as well: a double[] can be searched for an int or a short[], and conversely a long can be searched for a float or a double[]. This makes for efficient searches without the need to coerce one side of the comparison into the other's side type. The complexity of the search is Ο(haystack.length * max(needles.length)). (For needles that are individual items, length is considered to be 1.) The strategy used in searching several subranges at once maximizes cache usage by moving in haystack as few times as possible.Examples:int[] a = [ 1, 4, 2, 3 ]; assert(find(a, 4) == [ 4, 2, 3 ]); assert(find(a, [ 1, 4 ]) == [ 1, 4, 2, 3 ]); assert(find(a, [ 1, 3 ], 4) == tuple([ 4, 2, 3 ], 2)); // Mixed types allowed if comparable assert(find(a, 5, [ 1.2, 3.5 ], 2.0) == tuple([ 2, 3 ], 3));
 InputRange find(alias pred, InputRange)(InputRange haystack) if (isInputRange!InputRange);
 Advances the input range haystack by calling haystack.popFront until either pred(haystack.front), or haystack.empty. Performs Ο(haystack.length) evaluations of pred.To find the last element of a bidirectional haystack satisfying pred, call find!(pred)(retro(haystack)). See std.range.retro.SeeAlso:Examples:
auto arr = [ 1, 2, 3, 4, 1 ]; assert(find!("a > 2")(arr) == [ 3, 4, 1 ]); // with predicate alias bool pred(int x) { return x + 1 > 1.5; } assert(find!(pred)(arr) == arr);
 bool findSkip(alias pred = "a == b", R1, R2)(ref R1 haystack, R2 needle) if (isForwardRange!R1 && isForwardRange!R2 && is(typeof(binaryFun!pred(haystack.front, needle.front))));
 If needle occurs in haystack, positions haystack right after the first occurrence of needle and returns true. Otherwise, leaves haystack as is and returns false.Examples:
string s = "abcdef"; assert(findSkip(s, "cd") && s == "ef"); s = "abcdef"; assert(!findSkip(s, "cxd") && s == "abcdef"); s = "abcdef"; assert(findSkip(s, "def") && s.empty);
 auto findSplit(alias pred = "a == b", R1, R2)(R1 haystack, R2 needle) if (isForwardRange!R1 && isForwardRange!R2);
auto findSplitBefore(alias pred = "a == b", R1, R2)(R1 haystack, R2 needle) if (isForwardRange!R1 && isForwardRange!R2);
auto findSplitAfter(alias pred = "a == b", R1, R2)(R1 haystack, R2 needle) if (isForwardRange!R1 && isForwardRange!R2);  These functions find the first occurrence of needle in haystack and then split haystack as follows.findSplit returns a tuple result containing three ranges. result[0] is the portion of haystack before needle, result[1] is the portion of haystack that matches needle, and result[2] is the portion of haystack after the match. If needle was not found, result[0] comprehends haystack entirely and result[1] and result[2] are empty. findSplitBefore returns a tuple result containing two ranges. result[0] is the portion of haystack before needle, and result[1] is the balance of haystack starting with the match. If needle was not found, result[0] comprehends haystack entirely and result[1] is empty. findSplitAfter returns a tuple result containing two ranges. result[0] is the portion of haystack up to and including the match, and result[1] is the balance of haystack starting after the match. If needle was not found, result[0] is empty and result[1] is haystack. In all cases, the concatenation of the returned ranges spans the entire haystack. If haystack is a randomaccess range, all three components of the tuple have the same type as haystack. Otherwise, haystack must be a forward range and the type of result[0] and result[1] is the same as std.range.takeExactly.Examples:
auto a = "Carl Sagan Memorial Station"; auto r = findSplit(a, "Velikovsky"); assert(r[0] == a); assert(r[1].empty); assert(r[2].empty); r = findSplit(a, " "); assert(r[0] == "Carl"); assert(r[1] == " "); assert(r[2] == "Sagan Memorial Station"); auto r1 = findSplitBefore(a, "Sagan"); assert(r1[0] == "Carl ", r1[0]); assert(r1[1] == "Sagan Memorial Station"); auto r2 = findSplitAfter(a, "Sagan"); assert(r2[0] == "Carl Sagan"); assert(r2[1] == " Memorial Station");
 ptrdiff_t countUntil(alias pred = "a == b", R, Rs...)(R haystack, Rs needles) if (isForwardRange!R && Rs.length > 0 && isForwardRange!(Rs[0]) == isInputRange!(Rs[0]) && is(typeof(startsWith!pred(haystack, needles[0]))) && (Rs.length == 1  is(typeof(countUntil!pred(haystack, needles[1..$])))));
ptrdiff_t countUntil(alias pred = "a == b", R, N)(R haystack, N needle) if (isInputRange!R && is(typeof(binaryFun!pred(haystack.front, needle)) : bool));  Returns the number of elements which must be popped from the front of haystack before reaching an element for which startsWith!pred(haystack, needles) is true. If startsWith!pred(haystack, needles) is not true for any element in haystack, then 1 is returned.needles may be either an element or a range.Examples:
assert(countUntil("hello world", "world") == 6); assert(countUntil("hello world", 'r') == 8); assert(countUntil("hello world", "programming") == 1); assert(countUntil("日本語", "本語") == 1); assert(countUntil("日本語", '語') == 2); assert(countUntil("日本語", "五") == 1); assert(countUntil("日本語", '五') == 1); assert(countUntil([0, 7, 12, 22, 9], [12, 22]) == 2); assert(countUntil([0, 7, 12, 22, 9], 9) == 4); assert(countUntil!"a > b"([0, 7, 12, 22, 9], 20) == 3);
 ptrdiff_t countUntil(alias pred, R)(R haystack) if (isInputRange!R && is(typeof(unaryFun!pred(haystack.front)) : bool));
 Returns the number of elements which must be popped from haystack before pred(haystack.front) is true.Examples:
import std.ascii : isDigit; import std.uni : isWhite; assert(countUntil!(std.uni.isWhite)("hello world") == 5); assert(countUntil!(std.ascii.isDigit)("hello world") == 1); assert(countUntil!"a > 20"([0, 7, 12, 22, 9]) == 3);
 enum OpenRight: int;
 Interval option specifier for until (below) and others.
 struct Until(alias pred, Range, Sentinel) if (isInputRange!Range);
Until!(pred, Range, Sentinel) until(alias pred = "a == b", Range, Sentinel)(Range range, Sentinel sentinel, OpenRight openRight = OpenRight.yes) if (!is(Sentinel == OpenRight));
Until!(pred, Range, void) until(alias pred, Range)(Range range, OpenRight openRight = OpenRight.yes);  Lazily iterates range until value sentinel is found, at which point it stops.Examples:
int[] a = [ 1, 2, 4, 7, 7, 2, 4, 7, 3, 5]; assert(equal(a.until(7), [1, 2, 4][])); assert(equal(a.until(7, OpenRight.no), [1, 2, 4, 7][]));
 uint startsWith(alias pred = "a == b", Range, Needles...)(Range doesThisStart, Needles withOneOfThese) if (isInputRange!Range && Needles.length > 1 && is(typeof(.startsWith!pred(doesThisStart, withOneOfThese[0])) : bool) && is(typeof(.startsWith!pred(doesThisStart, withOneOfThese[1..$])) : uint));
bool startsWith(alias pred = "a == b", R1, R2)(R1 doesThisStart, R2 withThis) if (isInputRange!R1 && isInputRange!R2 && is(typeof(binaryFun!pred(doesThisStart.front, withThis.front)) : bool));
bool startsWith(alias pred = "a == b", R, E)(R doesThisStart, E withThis) if (isInputRange!R && is(typeof(binaryFun!pred(doesThisStart.front, withThis)) : bool));  If the range doesThisStart starts with any of the withOneOfThese ranges or elements, returns 1 if it starts with withOneOfThese[0], 2 if it starts with withOneOfThese[1], and so on. If none match, returns 0. In the case where doesThisStart starts with multiple of the ranges or elements in withOneOfThese, then the shortest one matches (if there are two which match which are of the same length (e.g. "a" and 'a'), then the leftmost of them in the argument list matches).Examples:
assert(startsWith("abc", "")); assert(startsWith("abc", "a")); assert(!startsWith("abc", "b")); assert(startsWith("abc", 'a', "b") == 1); assert(startsWith("abc", "b", "a") == 2); assert(startsWith("abc", "a", "a") == 1); assert(startsWith("abc", "ab", "a") == 2); assert(startsWith("abc", "x", "a", "b") == 2); assert(startsWith("abc", "x", "aa", "ab") == 3); assert(startsWith("abc", "x", "aaa", "sab") == 0); assert(startsWith("abc", "x", "aaa", "a", "sab") == 3);
 bool skipOver(alias pred = "a == b", R1, R2)(ref R1 r1, R2 r2) if (is(typeof(binaryFun!pred(r1.front, r2.front))));
 If startsWith(r1, r2), consume the corresponding elements off r1 and return true. Otherwise, leave r1 unchanged and return false.Examples:
auto s1 = "Hello world"; assert(!skipOver(s1, "Ha")); assert(s1 == "Hello world"); assert(skipOver(s1, "Hell") && s1 == "o world"); string[] r1 = ["abc", "def", "hij"]; dstring[] r2 = ["abc"d]; assert(!skipOver!((a, b) => a.equal(b))(r1, ["def"d])); assert(r1 == ["abc", "def", "hij"]); assert(skipOver!((a, b) => a.equal(b))(r1, r2)); assert(r1 == ["def", "hij"]);
 bool skipOver(alias pred = "a == b", R, E)(ref R r, E e) if (is(typeof(binaryFun!pred(r.front, e))));
 Checks whether a range starts with an element, and if so, consume that element off r and return true. Otherwise, leave r unchanged and return false.Examples:
auto s1 = "Hello world"; assert(!skipOver(s1, 'a')); assert(s1 == "Hello world"); assert(skipOver(s1, 'H') && s1 == "ello world"); string[] r = ["abc", "def", "hij"]; dstring e = "abc"d; assert(!skipOver!((a, b) => a.equal(b))(r, "def"d)); assert(r == ["abc", "def", "hij"]); assert(skipOver!((a, b) => a.equal(b))(r, e)); assert(r == ["def", "hij"]);
 uint endsWith(alias pred = "a == b", Range, Needles...)(Range doesThisEnd, Needles withOneOfThese) if (isBidirectionalRange!Range && Needles.length > 1 && is(typeof(.endsWith!pred(doesThisEnd, withOneOfThese[0])) : bool) && is(typeof(.endsWith!pred(doesThisEnd, withOneOfThese[1..$])) : uint));
bool endsWith(alias pred = "a == b", R1, R2)(R1 doesThisEnd, R2 withThis) if (isBidirectionalRange!R1 && isBidirectionalRange!R2 && is(typeof(binaryFun!pred(doesThisEnd.back, withThis.back)) : bool));
bool endsWith(alias pred = "a == b", R, E)(R doesThisEnd, E withThis) if (isBidirectionalRange!R && is(typeof(binaryFun!pred(doesThisEnd.back, withThis)) : bool));  The reciprocal of startsWith.Examples:
assert(endsWith("abc", "")); assert(!endsWith("abc", "b")); assert(endsWith("abc", "a", 'c') == 2); assert(endsWith("abc", "c", "a") == 1); assert(endsWith("abc", "c", "c") == 1); assert(endsWith("abc", "bc", "c") == 2); assert(endsWith("abc", "x", "c", "b") == 2); assert(endsWith("abc", "x", "aa", "bc") == 3); assert(endsWith("abc", "x", "aaa", "sab") == 0); assert(endsWith("abc", "x", "aaa", 'c', "sab") == 3);
 auto commonPrefix(alias pred = "a == b", R1, R2)(R1 r1, R2 r2) if (isForwardRange!R1 && isInputRange!R2 && !isNarrowString!R1 && is(typeof(binaryFun!pred(r1.front, r2.front))));
 Returns the common prefix of two ranges.If the first argument is a string, then the result is a slice of r1 which contains the characters that both ranges start with. For all other types, the type of the result is the same as the result of takeExactly(r1, n), where n is the number of elements that both ranges start with.SeeAlso:Examples:
assert(commonPrefix("hello, world", "hello, there") == "hello, ");
 Range findAdjacent(alias pred = "a == b", Range)(Range r) if (isForwardRange!Range);
 Advances r until it finds the first two adjacent elements a, b that satisfy pred(a, b). Performs Ο(r.length) evaluations of pred.SeeAlso:Examples:
int[] a = [ 11, 10, 10, 9, 8, 8, 7, 8, 9 ]; auto r = findAdjacent(a); assert(r == [ 10, 10, 9, 8, 8, 7, 8, 9 ]); auto p = findAdjacent!("a < b")(a); assert(p == [ 7, 8, 9 ]);
 Range1 findAmong(alias pred = "a == b", Range1, Range2)(Range1 seq, Range2 choices) if (isInputRange!Range1 && isForwardRange!Range2);
 Advances seq by calling seq.popFront until either find!(pred)(choices, seq.front) is true, or seq becomes empty. Performs Ο(seq.length * choices.length) evaluations of pred.SeeAlso:Examples:
int[] a = [ 1, 0, 1, 2, 3, 4, 5 ]; int[] b = [ 3, 1, 2 ]; assert(findAmong(a, b) == a[2 .. $]);
 size_t count(alias pred = "a == b", Range, E)(Range haystack, E needle) if (isInputRange!Range && !isInfinite!Range && is(typeof(binaryFun!pred(haystack.front, needle)) : bool));
size_t count(alias pred = "a == b", R1, R2)(R1 haystack, R2 needle) if (isForwardRange!R1 && !isInfinite!R1 && isForwardRange!R2 && is(typeof(binaryFun!pred(haystack.front, needle.front)) : bool));
size_t count(alias pred = "true", R)(R haystack) if (isInputRange!R && !isInfinite!R && is(typeof(unaryFun!pred(haystack.front)) : bool));  The first version counts the number of elements x in r for which pred(x, value) is true. pred defaults to equality. Performs Ο(haystack.length) evaluations of pred.The second version returns the number of times needle occurs in haystack. Throws an exception if needle.empty, as the count of the empty range in any range would be infinite. Overlapped counts are not considered, for example count("aaa", "aa") is 1, not 2. The third version counts the elements for which pred(x) is true. Performs Ο(haystack.length) evaluations of pred.Examples:
import std.uni : toLower; // count elements in range int[] a = [ 1, 2, 4, 3, 2, 5, 3, 2, 4 ]; assert(count(a, 2) == 3); assert(count!("a > b")(a, 2) == 5); // count range in range assert(count("abcadfabf", "ab") == 2); assert(count("ababab", "abab") == 1); assert(count("ababab", "abx") == 0); // fuzzy count range in range assert(count!((a, b) => std.uni.toLower(a) == std.uni.toLower(b))("AbcAdFaBf", "ab") == 2); // count predicate in range assert(count!("a > 1")(a) == 8);
 bool balancedParens(Range, E)(Range r, E lPar, E rPar, size_t maxNestingLevel = size_t.max) if (isInputRange!Range && is(typeof(r.front == lPar)));
 Checks whether r has "balanced parentheses", i.e. all instances of lPar are closed by corresponding instances of rPar. The parameter maxNestingLevel controls the nesting level allowed. The most common uses are the default or 0. In the latter case, no nesting is allowed.Examples:
auto s = "1 + (2 * (3 + 1 / 2)"; assert(!balancedParens(s, '(', ')')); s = "1 + (2 * (3 + 1) / 2)"; assert(balancedParens(s, '(', ')')); s = "1 + (2 * (3 + 1) / 2)"; assert(!balancedParens(s, '(', ')', 0)); s = "1 + (2 * 3 + 1) / (2  5)"; assert(balancedParens(s, '(', ')', 0));
 template equal(alias pred = "a == b")
 Compares two ranges for equality, as defined by predicate pred (which is == by default).Examples:
import std.math : approxEqual; import std.algorithm : equal; int[] a = [ 1, 2, 4, 3 ]; assert(!equal(a, a[1..$])); assert(equal(a, a)); // different types double[] b = [ 1.0, 2, 4, 3]; assert(!equal(a, b[1..$])); assert(equal(a, b)); // predicated: ensure that two vectors are approximately equal double[] c = [ 1.005, 2, 4, 3]; assert(equal!approxEqual(b, c));
Examples:Tip: equal can itself be used as a predicate to other functions. This can be very useful when the element type of a range is itself a range. In particular, equal can be its own predicate, allowing range of range (of range...) comparisons.import std.algorithm : equal; import std.range : iota, chunks; assert(equal!(equal!equal)( [[[0, 1], [2, 3]], [[4, 5], [6, 7]]], iota(0, 8).chunks(2).chunks(2) ));
 bool equal(Range1, Range2)(Range1 r1, Range2 r2) if (isInputRange!Range1 && isInputRange!Range2 && is(typeof(binaryFun!pred(r1.front, r2.front))));
 Returns true if and only if the two ranges compare equal element for element, according to binary predicate pred. The ranges may have different element types, as long as pred(a, b) evaluates to bool for a in r1 and b in r2. Performs Ο(min(r1.length, r2.length)) evaluations of pred.SeeAlso:
 int cmp(alias pred = "a < b", R1, R2)(R1 r1, R2 r2) if (isInputRange!R1 && isInputRange!R2 && !(isSomeString!R1 && isSomeString!R2));
 Performs threeway lexicographical comparison on two input ranges according to predicate pred. Iterating r1 and r2 in lockstep, cmp compares each element e1 of r1 with the corresponding element e2 in r2. If binaryFun!pred(e1, e2), cmp returns a negative value. If binaryFun!pred(e2, e1), cmp returns a positive value. If one of the ranges has been finished, cmp returns a negative value if r1 has fewer elements than r2, a positive value if r1 has more elements than r2, and 0 if the ranges have the same number of elements.
 MinType!T min(T...)(T args) if (T.length >= 2);
 Returns the minimum of the passedin values.
 MaxType!T max(T...)(T args) if (T.length >= 2);
 Returns the maximum of the passedin values.Examples:
int a = 5; short b = 6; double c = 2; auto d = max(a, b); assert(is(typeof(d) == int)); assert(d == 6); auto e = min(a, b, c); assert(is(typeof(e) == double)); assert(e == 2);
 Tuple!(ElementType!Range, size_t) minCount(alias pred = "a < b", Range)(Range range) if (isInputRange!Range && !isInfinite!Range && is(typeof(binaryFun!pred(range.front, range.front))));
 Returns the minimum element of a range together with the number of occurrences. The function can actually be used for counting the maximum or any other ordering predicate (that's why maxCount is not provided).Examples:
import std.conv : text; debug(std_algorithm) scope(success) writeln("unittest @", __FILE__, ":", __LINE__, " done."); int[] a = [ 2, 3, 4, 1, 2, 4, 1, 1, 2 ]; // Minimum is 1 and occurs 3 times assert(minCount(a) == tuple(1, 3)); // Maximum is 4 and occurs 2 times assert(minCount!("a > b")(a) == tuple(4, 2));
 Range minPos(alias pred = "a < b", Range)(Range range) if (isForwardRange!Range && !isInfinite!Range && is(typeof(binaryFun!pred(range.front, range.front))));
 Returns the position of the minimum element of forward range range, i.e. a subrange of range starting at the position of its smallest element and with the same ending as range. The function can actually be used for finding the maximum or any other ordering predicate (that's why maxPos is not provided).Examples:
int[] a = [ 2, 3, 4, 1, 2, 4, 1, 1, 2 ]; // Minimum is 1 and first occurs in position 3 assert(minPos(a) == [ 1, 2, 4, 1, 1, 2 ]); // Maximum is 4 and first occurs in position 2 assert(minPos!("a > b")(a) == [ 4, 1, 2, 4, 1, 1, 2 ]);
 Tuple!(Range1, Range2) mismatch(alias pred = "a == b", Range1, Range2)(Range1 r1, Range2 r2) if (isInputRange!Range1 && isInputRange!Range2);
 Sequentially compares elements in r1 and r2 in lockstep, and stops at the first mismatch (according to pred, by default equality). Returns a tuple with the reduced ranges that start with the two mismatched values. Performs Ο(min(r1.length, r2.length)) evaluations of pred.SeeAlso:Examples:
int[] x = [ 1, 5, 2, 7, 4, 3 ]; double[] y = [ 1.0, 5, 2, 7.3, 4, 8 ]; auto m = mismatch(x, y); assert(m[0] == x[3 .. $]); assert(m[1] == y[3 .. $]);
 enum EditOp: char;
 Encodes edit operations necessary to transform one sequence into another. Given sequences s (source) and t (target), a sequence of EditOp encodes the steps that need to be taken to convert s into t. For example, if s = "cat" and "cars", the minimal sequence that transforms s into t is: skip two characters, replace 't' with 'r', and insert an 's'. Working with edit operations is useful in applications such as spellcheckers (to find the closest word to a given misspelled word), approximate searches, diffstyle programs that compute the difference between files, efficient encoding of patches, DNA sequence analysis, and plagiarism detection.
 size_t levenshteinDistance(alias equals = "a == b", Range1, Range2)(Range1 s, Range2 t) if (isForwardRange!Range1 && isForwardRange!Range2);
 Returns the Levenshtein distance between s and t. The Levenshtein distance computes the minimal amount of edit operations necessary to transform s into t. Performs Ο(s.length * t.length) evaluations of equals and occupies Ο(s.length * t.length) storage.Allocates GC memory.Examples:
import std.uni : toUpper; assert(levenshteinDistance("cat", "rat") == 1); assert(levenshteinDistance("parks", "spark") == 2); assert(levenshteinDistance("kitten", "sitting") == 3); assert(levenshteinDistance!((a, b) => std.uni.toUpper(a) == std.uni.toUpper(b)) ("parks", "SPARK") == 2);
 Tuple!(size_t, EditOp[]) levenshteinDistanceAndPath(alias equals = "a == b", Range1, Range2)(Range1 s, Range2 t) if (isForwardRange!Range1 && isForwardRange!Range2);
 Returns the Levenshtein distance and the edit path between s and t.Allocates GC memory.Examples:
string a = "Saturday", b = "Sunday"; auto p = levenshteinDistanceAndPath(a, b); assert(p[0] == 3); assert(equal(p[1], "nrrnsnnn"));
 Range2 copy(Range1, Range2)(Range1 source, Range2 target) if (isInputRange!Range1 && isOutputRange!(Range2, ElementType!Range1));
 Copies the content of source into target and returns the remaining (unfilled) part of target.
Preconditions: target shall have enough room to accomodate source.
SeeAlso:Examples:int[] a = [ 1, 5 ]; int[] b = [ 9, 8 ]; int[] c = new int[a.length + b.length + 10]; auto d = copy(b, copy(a, c)); assert(c[0 .. a.length + b.length] == a ~ b); assert(d.length == 10);
Examples:As long as the target range elements support assignment from source range elements, different types of ranges are accepted.float[] a = [ 1.0f, 5 ]; double[] b = new double[a.length]; auto d = copy(a, b);
Examples:To copy at most n elements from range a to range b, you may want to use copy(take(a, n), b). To copy those elements from range a that satisfy predicate pred to range b, you may want to use copy(a.filter!(pred), b).int[] a = [ 1, 5, 8, 9, 10, 1, 2, 0 ]; auto b = new int[a.length]; auto c = copy(a.filter!(a => (a & 1) == 1), b); assert(b[0 .. $  c.length] == [ 1, 5, 9, 1 ]);
Examples:std.range.retro can be used to achieve behavior similar to STL's copy_backward'.import std.algorithm, std.range; int[] src = [1, 2, 4]; int[] dst = [0, 0, 0, 0, 0]; copy(src.retro, dst.retro); assert(dst == [0, 0, 1, 2, 4]);
 Tuple!(Range1, Range2) swapRanges(Range1, Range2)(Range1 r1, Range2 r2) if (isInputRange!Range1 && isInputRange!Range2 && hasSwappableElements!Range1 && hasSwappableElements!Range2 && is(ElementType!Range1 == ElementType!Range2));
 Swaps all elements of r1 with successive elements in r2. Returns a tuple containing the remainder portions of r1 and r2 that were not swapped (one of them will be empty). The ranges may be of different types but must have the same element type and support swapping.Examples:
int[] a = [ 100, 101, 102, 103 ]; int[] b = [ 0, 1, 2, 3 ]; auto c = swapRanges(a[1 .. 3], b[2 .. 4]); assert(c[0].empty && c[1].empty); assert(a == [ 100, 2, 3, 103 ]); assert(b == [ 0, 1, 101, 102 ]);
 void reverse(Range)(Range r) if (isBidirectionalRange!Range && !isRandomAccessRange!Range && hasSwappableElements!Range);
void reverse(Range)(Range r) if (isRandomAccessRange!Range && hasLength!Range);  Reverses r inplace. Performs r.length / 2 evaluations of swap.SeeAlso:Examples:
int[] arr = [ 1, 2, 3 ]; reverse(arr); assert(arr == [ 3, 2, 1 ]);
 void reverse(Char)(Char[] s) if (isNarrowString!(Char[]) && !is(Char == const) && !is(Char == immutable));
 Reverses r inplace, where r is a narrow string (having elements of type char or wchar). UTF sequences consisting of multiple code units are preserved properly.Examples:
char[] arr = "hello\U00010143\u0100\U00010143".dup; reverse(arr); assert(arr == "\U00010143\u0100\U00010143olleh");
 Range strip(Range, E)(Range range, E element) if (isBidirectionalRange!Range && is(typeof(range.front == element) : bool));
Range strip(alias pred, Range)(Range range) if (isBidirectionalRange!Range && is(typeof(pred(range.back)) : bool));
Range stripLeft(Range, E)(Range range, E element) if (isInputRange!Range && is(typeof(range.front == element) : bool));
Range stripLeft(alias pred, Range)(Range range) if (isInputRange!Range && is(typeof(pred(range.front)) : bool));
Range stripRight(Range, E)(Range range, E element) if (isBidirectionalRange!Range && is(typeof(range.back == element) : bool));
Range stripRight(alias pred, Range)(Range range) if (isBidirectionalRange!Range && is(typeof(pred(range.back)) : bool));  The strip group of functions allow stripping of either leading, trailing, or both leading and trailing elements.The stripLeft function will strip the front of the range, the stripRight function will strip the back of the range, while the strip function will strip both the front and back of the range. Note that the strip and stripRight functions require the range to be a BidirectionalRange range. All of these functions come in two varieties: one takes a target element, where the range will be stripped as long as this element can be found. The other takes a lambda predicate, where the range will be stripped as long as the predicate returns true.Examples:Strip leading and trailing elements equal to the target element.
assert(" foobar ".strip(' ') == "foobar"); assert("00223.444500".strip('0') == "223.4445"); assert("ëëêéüŗōpéêëë".strip('ë') == "êéüŗōpéê"); assert([1, 1, 0, 1, 1].strip(1) == [0]); assert([0.0, 0.01, 0.01, 0.0].strip(0).length == 2);
Examples:Strip leading and trailing elements while the predicate returns true.assert(" foobar ".strip!(a => a == ' ')() == "foobar"); assert("00223.444500".strip!(a => a == '0')() == "223.4445"); assert("ëëêéüŗōpéêëë".strip!(a => a == 'ë')() == "êéüŗōpéê"); assert([1, 1, 0, 1, 1].strip!(a => a == 1)() == [0]); assert([0.0, 0.01, 0.5, 0.6, 0.01, 0.0].strip!(a => a < 0.4)().length == 2);
Examples:Strip leading elements equal to the target element.assert(" foobar ".stripLeft(' ') == "foobar "); assert("00223.444500".stripLeft('0') == "223.444500"); assert("ůůűniçodêéé".stripLeft('ů') == "űniçodêéé"); assert([1, 1, 0, 1, 1].stripLeft(1) == [0, 1, 1]); assert([0.0, 0.01, 0.01, 0.0].stripLeft(0).length == 3);
Examples:Strip leading elements while the predicate returns true.assert(" foobar ".stripLeft!(a => a == ' ')() == "foobar "); assert("00223.444500".stripLeft!(a => a == '0')() == "223.444500"); assert("ůůűniçodêéé".stripLeft!(a => a == 'ů')() == "űniçodêéé"); assert([1, 1, 0, 1, 1].stripLeft!(a => a == 1)() == [0, 1, 1]); assert([0.0, 0.01, 0.10, 0.5, 0.6].stripLeft!(a => a < 0.4)().length == 2);
Examples:Strip trailing elements equal to the target element.assert(" foobar ".stripRight(' ') == " foobar"); assert("00223.444500".stripRight('0') == "00223.4445"); assert("ùniçodêéé".stripRight('é') == "ùniçodê"); assert([1, 1, 0, 1, 1].stripRight(1) == [1, 1, 0]); assert([0.0, 0.01, 0.01, 0.0].stripRight(0).length == 3);
Examples:Strip trailing elements while the predicate returns true.assert(" foobar ".stripRight!(a => a == ' ')() == " foobar"); assert("00223.444500".stripRight!(a => a == '0')() == "00223.4445"); assert("ùniçodêéé".stripRight!(a => a == 'é')() == "ùniçodê"); assert([1, 1, 0, 1, 1].stripRight!(a => a == 1)() == [1, 1, 0]); assert([0.0, 0.01, 0.10, 0.5, 0.6].stripRight!(a => a > 0.4)().length == 3);
 size_t bringToFront(Range1, Range2)(Range1 front, Range2 back) if (isInputRange!Range1 && isForwardRange!Range2);
 The bringToFront function has considerable flexibility and usefulness. It can rotate elements in one buffer left or right, swap buffers of equal length, and even move elements across disjoint buffers of different types and different lengths.bringToFront takes two ranges front and back, which may be of different types. Considering the concatenation of front and back one unified range, bringToFront rotates that unified range such that all elements in back are brought to the beginning of the unified range. The relative ordering of elements in front and back, respectively, remains unchanged. Performs Ο(max(front.length, back.length)) evaluations of swap.
Preconditions: Either front and back are disjoint, or back is reachable from front and front is not reachable from back.
Returns:The number of elements brought to the front, i.e., the length of back.SeeAlso:Examples:Examples:The front range may actually "step over" the back range. This is very useful with forward ranges that cannot compute comfortably rightbounded subranges like arr[0 .. 4] above. In the example below, r2 is a right subrange of r1.import std.container : SList; auto list = SList!(int)(4, 5, 6, 7, 1, 2, 3); auto r1 = list[]; auto r2 = list[]; popFrontN(r2, 4); assert(equal(r2, [ 1, 2, 3 ])); bringToFront(r1, r2); assert(equal(list[], [ 1, 2, 3, 4, 5, 6, 7 ]));
Examples:Elements can be swapped across ranges of different types:import std.container : SList; auto list = SList!(int)(4, 5, 6, 7); auto vec = [ 1, 2, 3 ]; bringToFront(list[], vec); assert(equal(list[], [ 1, 2, 3, 4 ])); assert(equal(vec, [ 5, 6, 7 ]));
 enum SwapStrategy: int;
 Defines the swapping strategy for algorithms that need to swap elements in a range (such as partition and sort). The strategy concerns the swapping of elements that are not the core concern of the algorithm. For example, consider an algorithm that sorts [ "abc", "b", "aBc" ] according to toUpper(a) < toUpper(b). That algorithm might choose to swap the two equivalent strings "abc" and "aBc". That does not affect the sorting since both [ "abc", "aBc", "b" ] and [ "aBc", "abc", "b" ] are valid outcomes.Some situations require that the algorithm must NOT ever change the relative ordering of equivalent elements (in the example above, only [ "abc", "aBc", "b" ] would be the correct result). Such algorithms are called stable. If the ordering algorithm may swap equivalent elements discretionarily, the ordering is called unstable. Yet another class of algorithms may choose an intermediate tradeoff by being stable only on a welldefined subrange of the range. There is no established terminology for such behavior; this library calls it semistable. Generally, the stable ordering strategy may be more costly in time and/or space than the other two because it imposes additional constraints. Similarly, semistable may be costlier than unstable. As (semi)stability is not needed very often, the ordering algorithms in this module parameterized by SwapStrategy all choose SwapStrategy.unstable as the default.
 unstable
 Allows freely swapping of elements as long as the output satisfies the algorithm's requirements.
 semistable
 In algorithms partitioning ranges in two, preserve relative ordering of elements only to the left of the partition point.
 stable
 Preserve the relative ordering of elements to the largest extent allowed by the algorithm's requirements.
 Range remove(SwapStrategy s = SwapStrategy.stable, Range, Offset...)(Range range, Offset offset) if (s != SwapStrategy.stable && isBidirectionalRange!Range && hasLvalueElements!Range && hasLength!Range && Offset.length >= 1);
 Eliminates elements at given offsets from range and returns the shortened range. In the simplest call, one element is removed.
int[] a = [ 3, 5, 7, 8 ]; assert(remove(a, 1) == [ 3, 7, 8 ]); assert(a == [ 3, 7, 8, 8 ]);
In the case above the element at offset 1 is removed and remove returns the range smaller by one element. The original array has remained of the same length because all functions in std.algorithm only change content, not topology. The value 8 is repeated because std.algorithm.move was invoked to move elements around and on integers move simply copies the source to the destination. To replace a with the effect of the removal, simply assign a = remove(a, 1). The slice will be rebound to the shorter array and the operation completes with maximal efficiency. Multiple indices can be passed into remove. In that case, elements at the respective indices are all removed. The indices must be passed in increasing order, otherwise an exception occurs.int[] a = [ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 ]; assert(remove(a, 1, 3, 5) == [ 0, 2, 4, 6, 7, 8, 9, 10 ]);
(Note how all indices refer to slots in the original array, not in the array as it is being progressively shortened.) Finally, any combination of integral offsets and tuples composed of two integral offsets can be passed in.int[] a = [ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 ]; assert(remove(a, 1, tuple(3, 5), 9) == [ 0, 2, 6, 7, 8, 10 ]);
In this case, the slots at positions 1, 3, 4, and 9 are removed from the array. The tuple passes in a range closed to the left and open to the right (consistent with builtin slices), e.g. tuple(3, 5) means indices 3 and 4 but not 5. If the need is to remove some elements in the range but the order of the remaining elements does not have to be preserved, you may want to pass SwapStrategy.unstable to remove.int[] a = [ 0, 1, 2, 3 ]; assert(remove!(SwapStrategy.unstable)(a, 1) == [ 0, 3, 2 ]);
In the case above, the element at slot 1 is removed, but replaced with the last element of the range. Taking advantage of the relaxation of the stability requirement, remove moved elements from the end of the array over the slots to be removed. This way there is less data movement to be done which improves the execution time of the function. The function remove works on any forward range. The moving strategy is (listed from fastest to slowest): If s == SwapStrategy.unstable && isRandomAccessRange!Range && hasLength!Range && hasLvalueElements!Range, then elements are moved from the end of the range into the slots to be filled. In this case, the absolute minimum of moves is performed.
 Otherwise, if s == SwapStrategy.unstable && isBidirectionalRange!Range && hasLength!Range && hasLvalueElements!Range, then elements are still moved from the end of the range, but time is spent on advancing between slots by repeated calls to range.popFront.
 Otherwise, elements are moved incrementally towards the front of range; a given element is never moved several times, but more elements are moved than in the previous cases.
 Range remove(alias pred, SwapStrategy s = SwapStrategy.stable, Range)(Range range) if (isBidirectionalRange!Range && hasLvalueElements!Range);
 Reduces the length of the bidirectional range range by removing elements that satisfy pred. If s = SwapStrategy.unstable, elements are moved from the right end of the range over the elements to eliminate. If s = SwapStrategy.stable (the default), elements are moved progressively to front such that their relative order is preserved. Returns the filtered range.Examples:
static immutable base = [1, 2, 3, 2, 4, 2, 5, 2]; int[] arr = base[].dup; // using a stringbased predicate assert(remove!("a == 2")(arr) == [ 1, 3, 4, 5 ]); // The original array contents have been modified, // so we need to reset it to its original state. // The length is unmodified however. arr[] = base[]; // using a lambda predicate assert(remove!(a => a == 2)(arr) == [ 1, 3, 4, 5 ]);
 Range partition(alias predicate, SwapStrategy ss = SwapStrategy.unstable, Range)(Range r) if (ss == SwapStrategy.stable && isRandomAccessRange!Range  ss != SwapStrategy.stable && isForwardRange!Range);
 Partitions a range in two using pred as a predicate. Specifically, reorders the range r = [left, right) using swap such that all elements i for which pred(i) is true come before all elements j for which pred(j) returns false.Performs Ο(r.length) (if unstable or semistable) or Ο(r.length * log(r.length)) (if stable) evaluations of less and swap. The unstable version computes the minimum possible evaluations of swap (roughly half of those performed by the semistable version).Returns:The right part of r after partitioning. If ss == SwapStrategy.stable, partition preserves the relative ordering of all elements a, b in r for which pred(a) == pred(b). If ss == SwapStrategy.semistable, partition preserves the relative ordering of all elements a, b in the left part of r for which pred(a) == pred(b).SeeAlso:Examples:
import std.conv : text; auto Arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]; auto arr = Arr.dup; static bool even(int a) { return (a & 1) == 0; } // Partition arr such that even numbers come first auto r = partition!(even)(arr); // Now arr is separated in evens and odds. // Numbers may have become shuffled due to instability assert(r == arr[5 .. $]); assert(count!(even)(arr[0 .. 5]) == 5); assert(find!(even)(r).empty); // Can also specify the predicate as a string. // Use 'a' as the predicate argument name arr[] = Arr[]; r = partition!(q{(a & 1) == 0})(arr); assert(r == arr[5 .. $]); // Now for a stable partition: arr[] = Arr[]; r = partition!(q{(a & 1) == 0}, SwapStrategy.stable)(arr); // Now arr is [2 4 6 8 10 1 3 5 7 9], and r points to 1 assert(arr == [2, 4, 6, 8, 10, 1, 3, 5, 7, 9] && r == arr[5 .. $]); // In case the predicate needs to hold its own state, use a delegate: arr[] = Arr[]; int x = 3; // Put stuff greater than 3 on the left bool fun(int a) { return a > x; } r = partition!(fun, SwapStrategy.semistable)(arr); // Now arr is [4 5 6 7 8 9 10 2 3 1] and r points to 2 assert(arr == [4, 5, 6, 7, 8, 9, 10, 2, 3, 1] && r == arr[7 .. $]);
 bool isPartitioned(alias pred, Range)(Range r) if (isForwardRange!Range);
 Returns true if r is partitioned according to predicate pred.Examples:
int[] r = [ 1, 3, 5, 7, 8, 2, 4, ]; assert(isPartitioned!"a & 1"(r));
 auto partition3(alias less = "a < b", SwapStrategy ss = SwapStrategy.unstable, Range, E)(Range r, E pivot) if (ss == SwapStrategy.unstable && isRandomAccessRange!Range && hasSwappableElements!Range && hasLength!Range && is(typeof(binaryFun!less(r.front, pivot)) == bool) && is(typeof(binaryFun!less(pivot, r.front)) == bool) && is(typeof(binaryFun!less(r.front, r.front)) == bool));
 Rearranges elements in r in three adjacent ranges and returns them. The first and leftmost range only contains elements in r less than pivot. The second and middle range only contains elements in r that are equal to pivot. Finally, the third and rightmost range only contains elements in r that are greater than pivot. The lessthan test is defined by the binary function less.Examples:
auto a = [ 8, 3, 4, 1, 4, 7, 4 ]; auto pieces = partition3(a, 4); assert(pieces[0] == [ 1, 3 ]); assert(pieces[1] == [ 4, 4, 4 ]); assert(pieces[2] == [ 8, 7 ]);
 void topN(alias less = "a < b", SwapStrategy ss = SwapStrategy.unstable, Range)(Range r, size_t nth) if (isRandomAccessRange!Range && hasLength!Range);
 Reorders the range r using swap such that r[nth] refers to the element that would fall there if the range were fully sorted. In addition, it also partitions r such that all elements e1 from r[0] to r[nth] satisfy !less(r[nth], e1), and all elements e2 from r[nth] to r[r.length] satisfy !less(e2, r[nth]). Effectively, it finds the nth smallest (according to less) elements in r. Performs an expected Ο(r.length) (if unstable) or Ο(r.length * log(r.length)) (if stable) evaluations of less and swap.If n >= r.length, the algorithm has no effect.SeeAlso:Examples:
int[] v = [ 25, 7, 9, 2, 0, 5, 21 ]; auto n = 4; topN!"a < b"(v, n); assert(v[n] == 9);
 void topN(alias less = "a < b", SwapStrategy ss = SwapStrategy.unstable, Range1, Range2)(Range1 r1, Range2 r2) if (isRandomAccessRange!Range1 && hasLength!Range1 && isInputRange!Range2 && is(ElementType!Range1 == ElementType!Range2));
 Stores the smallest elements of the two ranges in the lefthand range.Examples:
int[] a = [ 5, 7, 2, 6, 7 ]; int[] b = [ 2, 1, 5, 6, 7, 3, 0 ]; topN(a, b); sort(a); assert(a == [0, 1, 2, 2, 3]);
 SortedRange!(Range, less) sort(alias less = "a < b", SwapStrategy ss = SwapStrategy.unstable, Range)(Range r) if ((ss == SwapStrategy.unstable && (hasSwappableElements!Range  hasAssignableElements!Range)  ss != SwapStrategy.unstable && hasAssignableElements!Range) && isRandomAccessRange!Range && hasSlicing!Range && hasLength!Range);
 Sorts a randomaccess range according to the predicate less. Performs Ο(r.length * log(r.length)) evaluations of less. Stable sorting requires hasAssignableElements!Range to be true.sort returns a std.range.SortedRange over the original range, which functions that can take advantage of sorted data can then use to know that the range is sorted and adjust accordingly. The std.range.SortedRange is a wrapper around the original range, so both it and the original range are sorted, but other functions won't know that the original range has been sorted, whereas they can know that std.range.SortedRange has been sorted. The predicate is expected to satisfy certain rules in order for sort to behave as expected  otherwise, the program may fail on certain inputs (but not others) when not compiled in release mode, due to the cursory assumeSorted check. Specifically, sort expects less(a,b) && less(b,c) to imply less(a,c) (transitivity), and, conversely, !less(a,b) && !less(b,c) to imply !less(a,c). Note that the default predicate ("a < b") does not always satisfy these conditions for floating point types, because the expression will always be false when either a or b is NaN.Returns:The initial range wrapped as a SortedRange with the predicate binaryFun!less.
Algorithms: en.wikipedia.org/wiki/Introsort is used for unstable sorting and Timsort is used for stable sorting. Each algorithm has benefits beyond stability. Introsort is generally faster but Timsort may achieve greater speeds on data with low entropy or if predicate calls are expensive. Introsort performs no allocations whereas Timsort will perform one or more allocations per call. Both algorithms have Ο(n log n) worstcase time complexity.
SeeAlso:Examples:int[] array = [ 1, 2, 3, 4 ]; // sort in descending order sort!("a > b")(array); assert(array == [ 4, 3, 2, 1 ]); // sort in ascending order sort(array); assert(array == [ 1, 2, 3, 4 ]); // sort with a delegate bool myComp(int x, int y) @safe pure nothrow { return x > y; } sort!(myComp)(array); assert(array == [ 4, 3, 2, 1 ]);
Examples:// Showcase stable sorting string[] words = [ "aBc", "a", "abc", "b", "ABC", "c" ]; sort!("toUpper(a) < toUpper(b)", SwapStrategy.stable)(words); assert(words == [ "a", "aBc", "abc", "ABC", "b", "c" ]);
 template multiSort(less...)

Sorts a range by multiple keys. The call multiSort!("a.id < b.id", "a.date > b.date")(r) sorts the range r by id ascending, and sorts elements that have the same id by date descending. Such a call is equivalent to sort!"a.id != b.id ? a.id < b.id : a.date > b.date"(r), but multiSort is faster because it does fewer comparisons (in addition to being more convenient).Examples:
static struct Point { int x, y; } auto pts1 = [ Point(0, 0), Point(5, 5), Point(0, 1), Point(0, 2) ]; auto pts2 = [ Point(0, 0), Point(0, 1), Point(0, 2), Point(5, 5) ]; multiSort!("a.x < b.x", "a.y < b.y", SwapStrategy.unstable)(pts1); assert(pts1 == pts2);
 SortedRange!(R, (a, b) => binaryFun!less(unaryFun!transform(a), unaryFun!transform(b))) schwartzSort(alias transform, alias less = "a < b", SwapStrategy ss = SwapStrategy.unstable, R)(R r) if (isRandomAccessRange!R && hasLength!R);
 Sorts a range using an algorithm akin to the Schwartzian transform, also known as the decoratesortundecorate pattern in Python and Lisp. (Not to be confused with the other Schwartz.) This function is helpful when the sort comparison includes an expensive computation. The complexity is the same as that of the corresponding sort, but schwartzSort evaluates transform only r.length times (less than half when compared to regular sorting). The usage can be best illustrated with an example.Examples:
uint hashFun(string) { ... expensive computation ... } string[] array = ...; // Sort strings by hash, slow sort!((a, b) => hashFun(a) < hashFun(b))(array); // Sort strings by hash, fast (only computes arr.length hashes): schwartzSort!(hashFun, "a < b")(array);
The schwartzSort function might require less temporary data and be faster than the Perl idiom or the decoratesortundecorate idiom present in Python and Lisp. This is because sorting is done inplace and only minimal extra data (one array of transformed elements) is created. To check whether an array was sorted and benefit of the speedup of Schwartz sorting, a function schwartzIsSorted is not provided because the effect can be achieved by calling isSorted!less(map!transform(r)).Returns:The initial range wrapped as a SortedRange with the predicate (a, b) => binaryFun!less(transform(a), transform(b)).  void partialSort(alias less = "a < b", SwapStrategy ss = SwapStrategy.unstable, Range)(Range r, size_t n) if (isRandomAccessRange!Range && hasLength!Range && hasSlicing!Range);
 Reorders the randomaccess range r such that the range r[0 .. mid] is the same as if the entire r were sorted, and leaves the range r[mid .. r.length] in no particular order. Performs Ο(r.length * log(mid)) evaluations of pred. The implementation simply calls topN!(less, ss)(r, n) and then sort!(less, ss)(r[0 .. n]).Examples:
int[] a = [ 9, 8, 7, 6, 5, 4, 3, 2, 1, 0 ]; partialSort(a, 5); assert(a[0 .. 5] == [ 0, 1, 2, 3, 4 ]);
 void completeSort(alias less = "a < b", SwapStrategy ss = SwapStrategy.unstable, Range1, Range2)(SortedRange!(Range1, less) lhs, Range2 rhs) if (hasLength!Range2 && hasSlicing!Range2);
 Sorts the randomaccess range chain(lhs, rhs) according to predicate less. The lefthand side of the range lhs is assumed to be already sorted; rhs is assumed to be unsorted. The exact strategy chosen depends on the relative sizes of lhs and rhs. Performs Ο(lhs.length + rhs.length * log(rhs.length)) (best case) to Ο((lhs.length + rhs.length) * log(lhs.length + rhs.length)) (worstcase) evaluations of swap.Examples:
int[] a = [ 1, 2, 3 ]; int[] b = [ 4, 0, 6, 5 ]; completeSort(assumeSorted(a), b); assert(a == [ 0, 1, 2 ]); assert(b == [ 3, 4, 5, 6 ]);
 bool isSorted(alias less = "a < b", Range)(Range r) if (isForwardRange!Range);
 Checks whether a forward range is sorted according to the comparison operation less. Performs Ο(r.length) evaluations of less.Examples:
int[] arr = [4, 3, 2, 1]; assert(!isSorted(arr)); sort(arr); assert(isSorted(arr)); sort!("a > b")(arr); assert(isSorted!("a > b")(arr));
 SortedRange!(RangeIndex, (a, b) => binaryFun!less(*a, *b)) makeIndex(alias less = "a < b", SwapStrategy ss = SwapStrategy.unstable, Range, RangeIndex)(Range r, RangeIndex index) if (isForwardRange!Range && isRandomAccessRange!RangeIndex && is(ElementType!RangeIndex : ElementType!Range*));
void makeIndex(alias less = "a < b", SwapStrategy ss = SwapStrategy.unstable, Range, RangeIndex)(Range r, RangeIndex index) if (isRandomAccessRange!Range && !isInfinite!Range && isRandomAccessRange!RangeIndex && !isInfinite!RangeIndex && isIntegral!(ElementType!RangeIndex));  Computes an index for r based on the comparison less. The index is a sorted array of pointers or indices into the original range. This technique is similar to sorting, but it is more flexible because (1) it allows "sorting" of immutable collections, (2) allows binary search even if the original collection does not offer random access, (3) allows multiple indexes, each on a different predicate, and (4) may be faster when dealing with large objects. However, using an index may also be slower under certain circumstances due to the extra indirection, and is always larger than a sortingbased solution because it needs space for the index in addition to the original collection. The complexity is the same as sort's.The first overload of makeIndex writes to a range containing pointers, and the second writes to a range containing offsets. The first overload requires Range to be a forward range, and the latter requires it to be a randomaccess range. makeIndex overwrites its second argument with the result, but never reallocates it.Returns:The pointerbased version returns a SortedRange wrapper over index, of type SortedRange!(RangeIndex, (a, b) => binaryFun!less(*a, *b)) thus reflecting the ordering of the index. The indexbased version returns void because the ordering relation involves not only index but also r.Throws:If the second argument's length is less than that of the range indexed, an exception is thrown.Examples:
immutable(int[]) arr = [ 2, 3, 1, 5, 0 ]; // index using pointers auto index1 = new immutable(int)*[arr.length]; makeIndex!("a < b")(arr, index1); assert(isSorted!("*a < *b")(index1)); // index using offsets auto index2 = new size_t[arr.length]; makeIndex!("a < b")(arr, index2); assert(isSorted! ((size_t a, size_t b){ return arr[a] < arr[b];}) (index2));
 enum SortOutput: int;
 Specifies whether the output of certain algorithm is desired in sorted format.
 template canFind(alias pred = "a == b")
 Convenience function. Like find, but only returns whether or not the search was successful.Examples:
assert(canFind([0, 1, 2, 3], 2) == true); assert(canFind([0, 1, 2, 3], [1, 2], [2, 3])); assert(canFind([0, 1, 2, 3], [1, 2], [2, 3]) == 1); assert(canFind([0, 1, 2, 3], [1, 7], [2, 3])); assert(canFind([0, 1, 2, 3], [1, 7], [2, 3]) == 2); assert(canFind([0, 1, 2, 3], 4) == false); assert(!canFind([0, 1, 2, 3], [1, 3], [2, 4])); assert(canFind([0, 1, 2, 3], [1, 3], [2, 4]) == 0);
 bool canFind(Range)(Range haystack) if (is(typeof(find!pred(haystack))));
 Returns true if and only if any value v found in the input range range satisfies the predicate pred. Performs (at most) Ο(haystack.length) evaluations of pred.
 bool canFind(Range, Element)(Range haystack, Element needle) if (is(typeof(find!pred(haystack, needle))));
 Returns true if and only if needle can be found in range. Performs Ο(haystack.length) evaluations of pred.
 size_t canFind(Range, Ranges...)(Range haystack, Ranges needles) if (Ranges.length > 1 && allSatisfy!(isForwardRange, Ranges) && is(typeof(find!pred(haystack, needles))));
 Returns the 1based index of the first needle found in haystack. If no needle is found, then 0 is returned.So, if used directly in the condition of an if statement or loop, the result will be true if one of the needles is found and false if none are found, whereas if the result is used elsewhere, it can either be cast to bool for the same effect or used to get which needle was found first without having to deal with the tuple that LREF find returns for the same operation.
 template any(alias pred = "a")
 Checks if any of the elements verifies pred. !any can be used to verify that none of the elements verify pred.Examples:
import std.ascii : isWhite; assert( all!(any!isWhite)(["a a", "b b"])); assert(!any!(all!isWhite)(["a a", "b b"]));
Examples:any can also be used without a predicate, if its items can be evaluated to true or false in a conditional statement. !any can be a convenient way to quickly test that none of the elements of a range evaluate to true.int[3] vals1 = [0, 0, 0]; assert(!any(vals1[])); //none of vals1 evaluate to true int[3] vals2 = [2, 0, 2]; assert( any(vals2[])); assert(!all(vals2[])); int[3] vals3 = [3, 3, 3]; assert( any(vals3[])); assert( all(vals3[]));
 template all(alias pred = "a")
 Checks if all of the elements verify pred.Examples:
assert( all!"a & 1"([1, 3, 5, 7, 9])); assert(!all!"a & 1"([1, 2, 3, 5, 7, 9]));
Examples:  TRange topNCopy(alias less = "a < b", SRange, TRange)(SRange source, TRange target, SortOutput sorted = SortOutput.no) if (isInputRange!SRange && isRandomAccessRange!TRange && hasLength!TRange && hasSlicing!TRange);
 Copies the top n elements of the input range source into the randomaccess range target, where n = target.length. Elements of source are not touched. If sorted is true, the target is sorted. Otherwise, the target respects the heap property.Examples:
int[] a = [ 10, 16, 2, 3, 1, 5, 0 ]; int[] b = new int[3]; topNCopy(a, b, SortOutput.yes); assert(b == [ 0, 1, 2 ]);
 struct SetUnion(alias less = "a < b", Rs...) if (allSatisfy!(isInputRange, Rs));
SetUnion!(less, Rs) setUnion(alias less = "a < b", Rs...)(Rs rs);  Lazily computes the union of two or more ranges rs. The ranges are assumed to be sorted by less. Elements in the output are not unique; the length of the output is the sum of the lengths of the inputs. (The length member is offered if all ranges also have length.) The element types of all ranges must have a common type.Examples:
int[] a = [ 1, 2, 4, 5, 7, 9 ]; int[] b = [ 0, 1, 2, 4, 7, 8 ]; int[] c = [ 10 ]; assert(setUnion(a, b).length == a.length + b.length); assert(equal(setUnion(a, b), [0, 1, 1, 2, 2, 4, 4, 5, 7, 7, 8, 9][])); assert(equal(setUnion(a, c, b), [0, 1, 1, 2, 2, 4, 4, 5, 7, 7, 8, 9, 10][])); static assert(isForwardRange!(typeof(setUnion(a, b))));
 struct SetIntersection(alias less = "a < b", Rs...) if (Rs.length >= 2 && allSatisfy!(isInputRange, Rs) && !is(CommonType!(staticMap!(ElementType, Rs)) == void));
SetIntersection!(less, Rs) setIntersection(alias less = "a < b", Rs...)(Rs ranges) if (Rs.length >= 2 && allSatisfy!(isInputRange, Rs) && !is(CommonType!(staticMap!(ElementType, Rs)) == void));  Lazily computes the intersection of two or more input ranges ranges. The ranges are assumed to be sorted by less. The element types of the ranges must have a common type.Examples:
int[] a = [ 1, 2, 4, 5, 7, 9 ]; int[] b = [ 0, 1, 2, 4, 7, 8 ]; int[] c = [ 0, 1, 4, 5, 7, 8 ]; assert(equal(setIntersection(a, a), a)); assert(equal(setIntersection(a, b), [1, 2, 4, 7])); assert(equal(setIntersection(a, b, c), [1, 4, 7]));
 struct SetDifference(alias less = "a < b", R1, R2) if (isInputRange!R1 && isInputRange!R2);
SetDifference!(less, R1, R2) setDifference(alias less = "a < b", R1, R2)(R1 r1, R2 r2);  Lazily computes the difference of r1 and r2. The two ranges are assumed to be sorted by less. The element types of the two ranges must have a common type.Examples:
int[] a = [ 1, 2, 4, 5, 7, 9 ]; int[] b = [ 0, 1, 2, 4, 7, 8 ]; assert(equal(setDifference(a, b), [5, 9][])); static assert(isForwardRange!(typeof(setDifference(a, b))));
 struct SetSymmetricDifference(alias less = "a < b", R1, R2) if (isInputRange!R1 && isInputRange!R2);
SetSymmetricDifference!(less, R1, R2) setSymmetricDifference(alias less = "a < b", R1, R2)(R1 r1, R2 r2);  Lazily computes the symmetric difference of r1 and r2, i.e. the elements that are present in exactly one of r1 and r2. The two ranges are assumed to be sorted by less, and the output is also sorted by less. The element types of the two ranges must have a common type.Examples:
int[] a = [ 1, 2, 4, 5, 7, 9 ]; int[] b = [ 0, 1, 2, 4, 7, 8 ]; assert(equal(setSymmetricDifference(a, b), [0, 5, 8, 9][])); static assert(isForwardRange!(typeof(setSymmetricDifference(a, b))));
 struct NWayUnion(alias less, RangeOfRanges);
NWayUnion!(less, RangeOfRanges) nWayUnion(alias less = "a < b", RangeOfRanges)(RangeOfRanges ror);  Computes the union of multiple sets. The input sets are passed as a range of ranges and each is assumed to be sorted by less. Computation is done lazily, one union element at a time. The complexity of one popFront operation is Ο(log(ror.length)). However, the length of ror decreases as ranges in it are exhausted, so the complexity of a full pass through NWayUnion is dependent on the distribution of the lengths of ranges contained within ror. If all ranges have the same length n (worst case scenario), the complexity of a full pass through NWayUnion is Ο(n * ror.length * log(ror.length)), i.e., log(ror.length) times worse than just spanning all ranges in turn. The output comes sorted (unstably) by less.
Warning: Because NWayUnion does not allocate extra memory, it will leave ror modified. Namely, NWayUnion assumes ownership of ror and discretionarily swaps and advances elements of it. If you want ror to preserve its contents after the call, you may want to pass a duplicate to NWayUnion (and perhaps cache the duplicate in between calls).
Examples:double[][] a = [ [ 1, 4, 7, 8 ], [ 1, 7 ], [ 1, 7, 8], [ 4 ], [ 7 ], ]; auto witness = [ 1, 1, 1, 4, 4, 7, 7, 7, 7, 8, 8 ]; assert(equal(nWayUnion(a), witness));
 void largestPartialIntersection(alias less = "a < b", RangeOfRanges, Range)(RangeOfRanges ror, Range tgt, SortOutput sorted = SortOutput.no);
 Given a range of sorted forward ranges ror, copies to tgt the elements that are common to most ranges, along with their number of occurrences. All ranges in ror are assumed to be sorted by less. Only the most frequent tgt.length elements are returned.
Example:
// Figure which number can be found in most arrays of the set of // arrays below. double[][] a = [ [ 1, 4, 7, 8 ], [ 1, 7 ], [ 1, 7, 8], [ 4 ], [ 7 ], ]; auto b = new Tuple!(double, uint)[1]; largestPartialIntersection(a, b); // First member is the item, second is the occurrence count assert(b[0] == tuple(7.0, 4u));
7.0 is the correct answer because it occurs in 4 out of the 5 inputs, more than any other number. The second member of the resulting tuple is indeed 4 (recording the number of occurrences of 7.0). If more of the topfrequent numbers are needed, just create a larger tgt range. In the example above, creating b with length 2 yields tuple(1.0, 3u) in the second position. The function largestPartialIntersection is useful for e.g. searching an inverted index for the documents most likely to contain some terms of interest. The complexity of the search is Ο(n * log(tgt.length)), where n is the sum of lengths of all input ranges. This approach is faster than keeping an associative array of the occurrences and then selecting its top items, and also requires less memory (largestPartialIntersection builds its result directly in tgt and requires no extra memory).Warning: Because largestPartialIntersection does not allocate extra memory, it will leave ror modified. Namely, largestPartialIntersection assumes ownership of ror and discretionarily swaps and advances elements of it. If you want ror to preserve its contents after the call, you may want to pass a duplicate to largestPartialIntersection (and perhaps cache the duplicate in between calls).
 void largestPartialIntersectionWeighted(alias less = "a < b", RangeOfRanges, Range, WeightsAA)(RangeOfRanges ror, Range tgt, WeightsAA weights, SortOutput sorted = SortOutput.no);
 Similar to largestPartialIntersection, but associates a weight with each distinct element in the intersection.
Example:
// Figure which number can be found in most arrays of the set of // arrays below, with specific perelement weights double[][] a = [ [ 1, 4, 7, 8 ], [ 1, 7 ], [ 1, 7, 8], [ 4 ], [ 7 ], ]; auto b = new Tuple!(double, uint)[1]; double[double] weights = [ 1:1.2, 4:2.3, 7:1.1, 8:1.1 ]; largestPartialIntersectionWeighted(a, b, weights); // First member is the item, second is the occurrence count assert(b[0] == tuple(4.0, 2u));
The correct answer in this case is 4.0, which, although only appears two times, has a total weight 4.6 (three times its weight 2.3). The value 7 is weighted with 1.1 and occurs four times for a total weight 4.4.  bool nextPermutation(alias less = "a<b", BidirectionalRange)(ref BidirectionalRange range) if (isBidirectionalRange!BidirectionalRange && hasSwappableElements!BidirectionalRange);
 Permutes range inplace to the next lexicographically greater permutation.The predicate less defines the lexicographical ordering to be used on the range. If the range is currently the lexicographically greatest permutation, it is permuted back to the least permutation and false is returned. Otherwise, true is returned. One can thus generate all permutations of a range by sorting it according to less, which produces the lexicographically least permutation, and then calling nextPermutation until it returns false. This is guaranteed to generate all distinct permutations of the range exactly once. If there are N elements in the range and all of them are unique, then N! permutations will be generated. Otherwise, if there are some duplicated elements, fewer permutations will be produced.
// Enumerate all permutations int[] a = [1,2,3,4,5]; do { // use the current permutation and // proceed to the next permutation of the array. } while (nextPermutation(a));
Returns:false if the range was lexicographically the greatest, in which case the range is reversed back to the lexicographically smallest permutation; otherwise returns true.Examples:// Step through all permutations of a sorted array in lexicographic order int[] a = [1,2,3]; assert(nextPermutation(a) == true); assert(a == [1,3,2]); assert(nextPermutation(a) == true); assert(a == [2,1,3]); assert(nextPermutation(a) == true); assert(a == [2,3,1]); assert(nextPermutation(a) == true); assert(a == [3,1,2]); assert(nextPermutation(a) == true); assert(a == [3,2,1]); assert(nextPermutation(a) == false); assert(a == [1,2,3]);
Examples:// Step through permutations of an array containing duplicate elements: int[] a = [1,1,2]; assert(nextPermutation(a) == true); assert(a == [1,2,1]); assert(nextPermutation(a) == true); assert(a == [2,1,1]); assert(nextPermutation(a) == false); assert(a == [1,1,2]);
 bool nextEvenPermutation(alias less = "a<b", BidirectionalRange)(ref BidirectionalRange range) if (isBidirectionalRange!BidirectionalRange && hasSwappableElements!BidirectionalRange);
 Permutes range inplace to the next lexicographically greater even permutation.The predicate less defines the lexicographical ordering to be used on the range. An even permutation is one which is produced by swapping an even number of pairs of elements in the original range. The set of even permutations is distinct from the set of all permutations only when there are no duplicate elements in the range. If the range has N unique elements, then there are exactly N!/2 even permutations. If the range is already the lexicographically greatest even permutation, it is permuted back to the least even permutation and false is returned. Otherwise, true is returned, and the range is modified inplace to be the lexicographically next even permutation. One can thus generate the even permutations of a range with unique elements by starting with the lexicographically smallest permutation, and repeatedly calling nextEvenPermutation until it returns false.
// Enumerate even permutations int[] a = [1,2,3,4,5]; do { // use the current permutation and // proceed to the next even permutation of the array. } while (nextEvenPermutation(a));
One can also generate the odd permutations of a range by noting that permutations obey the rule that even + even = even, and odd + even = odd. Thus, by swapping the last two elements of a lexicographically least range, it is turned into the first odd permutation. Then calling nextEvenPermutation on this first odd permutation will generate the next even permutation relative to this odd permutation, which is actually the next odd permutation of the original range. Thus, by repeatedly calling nextEvenPermutation until it returns false, one enumerates the odd permutations of the original range.// Enumerate odd permutations int[] a = [1,2,3,4,5]; swap(a[$2], a[$1]); // a is now the first odd permutation of [1,2,3,4,5] do { // use the current permutation and // proceed to the next odd permutation of the original array // (which is an even permutation of the first odd permutation). } while (nextEvenPermutation(a));
Warning: Since even permutations are only distinct from all permutations when the range elements are unique, this function assumes that there are no duplicate elements under the specified ordering. If this is not true, some permutations may fail to be generated. When the range has nonunique elements, you should use nextPermutation instead.
Returns:false if the range was lexicographically the greatest, in which case the range is reversed back to the lexicographically smallest permutation; otherwise returns true.Examples:// Step through even permutations of a sorted array in lexicographic order int[] a = [1,2,3]; assert(nextEvenPermutation(a) == true); assert(a == [2,3,1]); assert(nextEvenPermutation(a) == true); assert(a == [3,1,2]); assert(nextEvenPermutation(a) == false); assert(a == [1,2,3]);
Examples:Even permutations are useful for generating coordinates of certain geometric shapes. Here's a nontrivial example:import std.math : sqrt; // Print the 60 vertices of a uniform truncated icosahedron (soccer ball) enum real Phi = (1.0 + sqrt(5.0)) / 2.0; // Golden ratio real[][] seeds = [ [0.0, 1.0, 3.0*Phi], [1.0, 2.0+Phi, 2.0*Phi], [Phi, 2.0, Phi^^3] ]; size_t n; foreach (seed; seeds) { // Loop over even permutations of each seed do { // Loop over all sign changes of each permutation size_t i; do { // Generate all possible sign changes for (i=0; i < seed.length; i++) { if (seed[i] != 0.0) { seed[i] = seed[i]; if (seed[i] < 0.0) break; } } n++; } while (i < seed.length); } while (nextEvenPermutation(seed)); } assert(n == 60);
 auto cartesianProduct(R1, R2)(R1 range1, R2 range2);
auto cartesianProduct(R1, R2, RR...)(R1 range1, R2 range2, RR otherRanges);  Lazily computes the Cartesian product of two or more ranges. The product is a range of tuples of elements from each respective range.The conditions for the tworange case are as follows: If both ranges are finite, then one must be (at least) a forward range and the other an input range. If one range is infinite and the other finite, then the finite range must be a forward range, and the infinite range can be an input range. If both ranges are infinite, then both must be forward ranges. When there are more than two ranges, the above conditions apply to each adjacent pair of ranges.Examples:
auto N = sequence!"n"(0); // the range of natural numbers auto N2 = cartesianProduct(N, N); // the range of all pairs of natural numbers // Various arbitrary number pairs can be found in the range in finite time. assert(canFind(N2, tuple(0, 0))); assert(canFind(N2, tuple(123, 321))); assert(canFind(N2, tuple(11, 35))); assert(canFind(N2, tuple(279, 172)));
Examples:auto B = [ 1, 2, 3 ]; auto C = [ 4, 5, 6 ]; auto BC = cartesianProduct(B, C); foreach (n; [[1, 4], [2, 4], [3, 4], [1, 5], [2, 5], [3, 5], [1, 6], [2, 6], [3, 6]]) { assert(canFind(BC, tuple(n[0], n[1]))); }
Examples:auto A = [ 1, 2, 3 ]; auto B = [ 'a', 'b', 'c' ]; auto C = [ "x", "y", "z" ]; auto ABC = cartesianProduct(A, B, C); assert(ABC.equal([ tuple(1, 'a', "x"), tuple(2, 'a', "x"), tuple(3, 'a', "x"), tuple(1, 'b', "x"), tuple(2, 'b', "x"), tuple(3, 'b', "x"), tuple(1, 'c', "x"), tuple(2, 'c', "x"), tuple(3, 'c', "x"), tuple(1, 'a', "y"), tuple(2, 'a', "y"), tuple(3, 'a', "y"), tuple(1, 'b', "y"), tuple(2, 'b', "y"), tuple(3, 'b', "y"), tuple(1, 'c', "y"), tuple(2, 'c', "y"), tuple(3, 'c', "y"), tuple(1, 'a', "z"), tuple(2, 'a', "z"), tuple(3, 'a', "z"), tuple(1, 'b', "z"), tuple(2, 'b', "z"), tuple(3, 'b', "z"), tuple(1, 'c', "z"), tuple(2, 'c', "z"), tuple(3, 'c', "z"), ]));
 uint among(alias pred = (a, b) => a == b, Value, Values...)(Value value, Values values) if (Values.length != 0);
template among(values...) if (isExpressionTuple!values)  Find value among values, returning the 1based index of the first matching value in values, or 0 if value is not among values. The predicate pred is used to compare values, and uses equality by default.SeeAlso:std.algorithm.find for finding a value in a range.Examples:
assert(3.among(1, 42, 24, 3, 2)); if (auto pos = "bar".among("foo", "bar", "baz")) assert(pos == 2); else assert(false); // 42 is larger than 24 assert(42.among!((lhs, rhs) => lhs > rhs)(43, 24, 100) == 2);
Examples:Alternatively, values can be passed at compiletime, allowing for a more efficient search, but one that only supports matching on equality:assert(3.among!(2, 3, 4)); assert("bar".among!("foo", "bar", "baz") == 2);