Report a bug
If you spot a problem with this page, click here to create a Bugzilla issue.
Improve this page
Quickly fork, edit online, and submit a pull request for this page.
Requires a signedin GitHub account. This works well for small changes.
If you'd like to make larger changes you may want to consider using
local clone.
std.algorithm.iteration
This is a submodule of std.algorithm.
It contains generic iteration algorithms.
Function Name  Description 

cache  Eagerly evaluates and caches another range's front. 
cacheBidirectional  As above, but also provides back and popBack. 
chunkBy  chunkBy!((a,b) => a[1] == b[1])([[1, 1], [1, 2], [2, 2], [2, 1]]) returns a range containing 3 subranges: the first with just [1, 1]; the second with the elements [1, 2] and [2, 2]; and the third with just [2, 1]. 
each  each!writeln([1, 2, 3]) eagerly prints the numbers 1, 2 and 3 on their own lines. 
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. 
permutations  Lazily computes all permutations using Heap's algorithm. 
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. 
License:
Authors:
Source: std/algorithm/iteration.d
 auto cache(Range)(Range range) if (isInputRange!Range);
auto cacheBidirectional(Range)(Range range) if (isBidirectionalRange!Range);  cache eagerly evaluates front of range on each construction or call to popFront, to store the result in a cache. The result is then directly returned when front is called, rather than reevaluated.This can be a useful function to place in a chain, after functions that have expensive evaluation, as a lazy alternative to std.array.array. In particular, it can be placed after a call to map, or before a call to filter. cache may provide bidirectional iteration if needed, but since this comes at an increased cost, it must be explicitly requested via the call to cacheBidirectional. Furthermore, a bidirectional cache will evaluate the "center" element twice, when there is only one element left in the range. cache does not provide random access primitives, as cache would be unable to cache the random accesses. If Range provides slicing primitives, then cache will provide the same slicing primitives, but hasSlicing!Cache will not yield true (as the std.range.primitives.hasSlicing trait also checks for random access).Examples:
import std.algorithm.comparison : equal; import std.stdio, std.range; import std.typecons : tuple; ulong counter = 0; double fun(int x) { ++counter; // http://en.wikipedia.org/wiki/Quartic_function return ( (x + 4.0) * (x + 1.0) * (x  1.0) * (x  3.0) ) / 14.0 + 0.5; } // Without cache, with array (greedy) auto result1 = iota(4, 5).map!(a =>tuple(a, fun(a)))() .filter!"a[1]<0"() .map!"a[0]"() .array(); // the values of x that have a negative y are: assert(equal(result1, [3, 2, 2])); // Check how many times fun was evaluated. // As many times as the number of items in both source and result. assert(counter == iota(4, 5).length + result1.length); counter = 0; // Without array, with cache (lazy) auto result2 = iota(4, 5).map!(a =>tuple(a, fun(a)))() .cache() .filter!"a[1]<0"() .map!"a[0]"(); // the values of x that have a negative y are: assert(equal(result2, [3, 2, 2])); // Check how many times fun was evaluated. // Only as many times as the number of items in source. assert(counter == iota(4, 5).length);
Examples:Tip: cache is eager when evaluating elements. If calling front on the underlying range has a side effect, it will be observeable before calling front on the actual cached range. Furtermore, care should be taken composing cache with std.range.take. By placing take before cache, then cache will be "aware" of when the range ends, and correctly stop caching elements when needed. If calling front has no side effect though, placing take after cache may yield a faster range. Either way, the resulting ranges will be equivalent, but maybe not at the same cost or side effects.import std.algorithm.comparison : equal; import std.range; int i = 0; auto r = iota(0, 4).tee!((a){i = a;}, No.pipeOnPop); auto r1 = r.take(3).cache(); auto r2 = r.cache().take(3); assert(equal(r1, [0, 1, 2])); assert(i == 2); //The last "seen" element was 2. The data in cache has been cleared. assert(equal(r2, [0, 1, 2])); assert(i == 3); //cache has accessed 3. It is still stored internally by cache.
 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(a) left to right for all elements a in range. The original ranges are not changed. Evaluation is done lazily.See Also:Examples:
import std.algorithm.comparison : equal; import std.range : chain; 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 each(alias pred = "a")
 Eagerly iterates over r and calls pred over each element.Parameters:
Example:
void deleteOldBackups() { import std.algorithm, std.datetime, std.file; auto cutoff = Clock.currTime()  7.days; dirEntries("", "*~", SpanMode.depth) .filter!(de => de.timeLastModified < cutoff) .each!remove(); }
If the range supports it, the value can be mutated in place. Examples:arr.each!((ref a) => a++); arr.each!"a++";
If no predicate is specified, each will default to doing nothing but consuming the entire range. .front will be evaluated, but this can be avoided by explicitly specifying a predicate lambda with a lazy parameter. each also supports opApplybased iterators, so it will work with e.g. std.parallelism.parallel.See Also:  template filter(alias predicate) if (is(typeof(unaryFun!predicate)))

Implements the higher order filter function.Parameters:
predicate Function to apply to each element of range range Input range of elements Returns:See Also:Examples:import std.algorithm.comparison : equal; import std.math : approxEqual; import std.range; 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.Parameters:
pred Function to apply to each element of range r Bidirectional range of elements Examples:import std.algorithm.comparison : equal; import std.range; 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);
 Group!(pred, Range) group(alias pred = "a == b", Range)(Range r);
 Groups consecutively equivalent elements into a single tuple of the element and the number of its repetitions.Similarly to uniq, group produces a range that iterates over unique consecutive elements of the given range. Each element of this range is a tuple of the element and the number of times it is repeated in the original range. Equivalence of elements is assessed by using the predicate pred, which defaults to "a == b".Parameters:
pred Binary predicate for determining equivalence of two elements. Range r The input range to iterate over. Returns:A range of elements of type Tuple!(ElementType!R, uint), representing each consecutively unique element and its respective number of occurrences in that run. This will be an input range if R is an input range, and a forward range in all other cases.Examples:import std.algorithm.comparison : equal; import std.typecons : tuple, Tuple; 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) ][]));
 auto chunkBy(alias pred, Range)(Range r) if (isInputRange!Range);
 Chunks an input range into subranges of equivalent adjacent elements.Equivalence is defined by the predicate pred, which can be either binary or unary. In the binary form, two range elements a and b are considered equivalent if pred(a,b) is true. In unary form, two elements are considered equivalent if pred(a) == pred(b) is true. This predicate must be an equivalence relation, that is, it must be reflexive (pred(x,x) is always true), symmetric (pred(x,y) == pred(y,x)), and transitive (pred(x,y) && pred(y,z) implies pred(x,z)). If this is not the case, the range returned by chunkBy may assert at runtime or behave erratically.Parameters:
pred Predicate for determining equivalence. Range r The range to be chunked. Returns:With a binary predicate, a range of ranges is returned in which all elements in a given subrange are equivalent under the given predicate. With a unary predicate, a range of tuples is returned, with the tuple consisting of the result of the unary predicate for each subrange, and the subrange itself.Notes: Equivalent elements separated by an intervening nonequivalent element will appear in separate subranges; this function only considers adjacent equivalence. Elements in the subranges will always appear in the same order they appear in the original range.
See Also:group, which collapses adjacent equivalent elements into a single element.Examples:Showing usage with binary predicate:import std.algorithm.comparison : equal; // Grouping by particular attribute of each element: auto data = [ [1, 1], [1, 2], [2, 2], [2, 3] ]; auto r1 = data.chunkBy!((a,b) => a[0] == b[0]); assert(r1.equal!equal([ [[1, 1], [1, 2]], [[2, 2], [2, 3]] ])); auto r2 = data.chunkBy!((a,b) => a[1] == b[1]); assert(r2.equal!equal([ [[1, 1]], [[1, 2], [2, 2]], [[2, 3]] ]));
Examples:Showing usage with unary predicate:import std.algorithm.comparison : equal; import std.typecons : tuple; // Grouping by particular attribute of each element: auto range = [ [1, 1], [1, 1], [1, 2], [2, 2], [2, 3], [2, 3], [3, 3] ]; auto byX = chunkBy!(a => a[0])(range); auto expected1 = [ tuple(1, [[1, 1], [1, 1], [1, 2]]), tuple(2, [[2, 2], [2, 3], [2, 3]]), tuple(3, [[3, 3]]) ]; foreach (e; byX) { assert(!expected1.empty); assert(e[0] == expected1.front[0]); assert(e[1].equal(expected1.front[1])); expected1.popFront(); } auto byY = chunkBy!(a => a[1])(range); auto expected2 = [ tuple(1, [[1, 1], [1, 1]]), tuple(2, [[1, 2], [2, 2]]), tuple(3, [[2, 3], [2, 3], [3, 3]]) ]; foreach (e; byY) { assert(!expected2.empty); assert(e[0] == expected2.front[0]); assert(e[1].equal(expected2.front[1])); expected2.popFront(); }
 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.Parameters:
RoR r An input range of input ranges to be joined. Separator sep A forward range of element(s) to serve as separators in the joined range. Returns:An input range of elements in the joined range. This will be a forward range if both outer and inner ranges of RoR are forward ranges; otherwise it will be only an input range.See Also:std.range.chain, which chains a sequence of ranges with compatible elements into a single range.Examples:import std.algorithm.comparison : equal; 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"));
 template reduce(fun...) if (fun.length >= 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).Returns:the accumulated resultSee Also:Fold (higherorder function) sum is similar to reduce!((a, b) => a + b) that offers precise summing of floating point numbers.
 auto reduce(R)(R r) if (isIterable!R);
 Noseed version. The first element of r is used as the seed's value.For each function f in fun, the corresponding seed type S is Unqual!(typeof(f(e, e))), where e is an element of r: ElementType!R for ranges, and ForeachType!R otherwise. Once S has been determined, then S s = e; and s = f(s, e); must both be legal. If r is empty, an Exception is thrown.
 auto reduce(S, R)(S seed, R r) if (isIterable!R);
 Seed version. The seed should be a single value if fun is a single function. If fun is multiple functions, then seed should be a std.typecons.Tuple, with one field per function in f.
 auto splitter(alias pred = "a == b", Range, Separator)(Range r, Separator s) if (is(typeof(binaryFun!pred(r.front, s)) : bool) && (hasSlicing!Range && hasLength!Range  isNarrowString!Range));
 Lazily 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 fourth overload below).Parameters:
pred The predicate for comparing each element with the separator, defaulting to "a == b". Range r The input range to be split. Must support slicing and .length. Separator s The element to be treated as the separator between range segments to be split. Constraints: The predicate pred needs to accept an element of r and the separator s.
Returns:An input range of the subranges of elements between separators. If r is a forward range or bidirectional range, the returned range will be likewise.See Also:std.regex.splitter for a version that splits using a regular expression defined separator.Examples:import std.algorithm.comparison : equal; 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] ])); w = [ [0], [1], [2] ]; assert(equal(splitter!"a.front == b"(w, 1), [ [[0]], [[2]] ]));
 auto splitter(alias pred = "a == b", Range, Separator)(Range r, Separator s) if (is(typeof(binaryFun!pred(r.front, s.front)) : bool) && (hasSlicing!Range  isNarrowString!Range) && isForwardRange!Separator && (hasLength!Separator  isNarrowString!Separator));
 Similar to the previous overload of splitter, except this one uses 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.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.Parameters:
pred The predicate for comparing each element with the separator, defaulting to "a == b". Range r The input range to be split. Separator s The forward range to be treated as the separator between segments of r to be split. Constraints: The predicate pred needs to accept an element of r and an element of s.
Returns:An input range of the subranges of elements between separators. If r is a forward range or bidirectional range, the returned range will be likewise.See Also:std.regex.splitter for a version that splits using a regular expression defined separator.Examples:import std.algorithm.comparison : equal; assert(equal(splitter("hello world", " "), [ "hello", "world" ])); int[] a = [ 1, 2, 0, 0, 3, 0, 4, 5, 0 ]; int[][] w = [ [1, 2], [3, 0, 4, 5, 0] ]; assert(equal(splitter(a, [0, 0]), w)); a = [ 0, 0 ]; assert(equal(splitter(a, [0, 0]), [ (int[]).init, (int[]).init ])); a = [ 0, 0, 1 ]; assert(equal(splitter(a, [0, 0]), [ [], [1] ]));
 auto splitter(alias isTerminator, Range)(Range input) if (isForwardRange!Range && is(typeof(unaryFun!isTerminator(input.front))));
 Similar to the previous overload of splitter, except this one does not use a separator. Instead, the predicate is an unary function on the input range's element type.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.Parameters:
isTerminator The predicate for deciding where to split the range. Range input The input range to be split. Constraints: The predicate isTerminator needs to accept an element of input.
Returns:An input range of the subranges of elements between separators. If input is a forward range or bidirectional range, the returned range will be likewise.See Also:std.regex.splitter for a version that splits using a regular expression defined separator.Examples:import std.algorithm.comparison : equal; assert(equal(splitter!"a == ' '"("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"(a), w)); a = [ 0 ]; assert(equal(splitter!"a == 0"(a), [ (int[]).init, (int[]).init ])); a = [ 0, 1 ]; assert(equal(splitter!"a == 0"(a), [ [], [1] ])); w = [ [0], [1], [2] ]; assert(equal(splitter!"a.front == 1"(w), [ [[0]], [[2]] ]));
 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).Parameters:
C[] s The string to be split. Returns:An input range of slices of the original string split by whitespace.Examples:import std.algorithm.comparison : equal; auto a = " a bcd ef gh "; assert(equal(splitter(a), ["a", "bcd", "ef", "gh"][]));
 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 std.range.primitives.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.
 auto uniq(alias pred = "a == b", Range)(Range r) if (isInputRange!Range && is(typeof(binaryFun!pred(r.front, r.front)) == bool));
 Lazily 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.Parameters:
pred Predicate for determining equivalence between range elements. Range r An input range of elements to filter. Returns:An input range of consecutively unique elements in the original range. If r is also a forward range or bidirectional range, the returned range will be likewise.Examples:import std.algorithm.mutation : copy; import std.algorithm.comparison : equal; int[] arr = [ 1, 2, 2, 2, 2, 3, 4, 4, 4, 5 ]; assert(equal(uniq(arr), [ 1, 2, 3, 4, 5 ][])); // Filter duplicates inplace using copy arr.length = arr.uniq().copy(arr).length; assert(arr == [ 1, 2, 3, 4, 5 ]); // Note that uniqueness is only determined consecutively; duplicated // elements separated by an intervening different element will not be // eliminated: assert(equal(uniq([ 1, 1, 2, 1, 1, 3, 1]), [1, 2, 1, 3, 1]));
 Permutations!Range permutations(Range)(Range r) if (isRandomAccessRange!Range && hasLength!Range);
 Lazily computes all permutations of r using Heap's algorithm.Returns:A forward range the elements of which are an std.range.indexed view into r.See Also:Examples:
import std.algorithm.comparison : equal; import std.range : iota; assert(equal!equal(iota(3).permutations, [[0, 1, 2], [1, 0, 2], [2, 0, 1], [0, 2, 1], [1, 2, 0], [2, 1, 0]]));