View source code
Display the source code in std/algorithm/searching.d from which this page was generated on github.
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 signed-in GitHub account. This works well for small changes. If you'd like to make larger changes you may want to consider using local clone.

Module std.algorithm.searching

This is a submodule of std.algorithm. It contains generic searching algorithms.

Cheat Sheet
Function Name Description
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 Boyer-Moore 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 "de" 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).
maxCount maxCount([2, 4, 1, 4, 1]) returns tuple(4, 2).
minElement Selects the minimal element of a range. minElement([3, 4, 1, 2]) returns 1.
maxElement Selects the maximal element of a range. maxElement([3, 4, 1, 2]) returns 4.
minIndex Index of the minimal element of a range. minIndex([3, 4, 1, 2]) returns 2.
maxIndex Index of the maximal element of a range. maxIndex([3, 4, 1, 2]) returns 1.
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.
maxPos maxPos([2, 3, 1, 3, 4, 1]) returns the subrange [4, 1], i.e., positions the range at the first occurrence of its maximal element.
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.

Functions

NameDescription
balancedParens(r, lPar, rPar, maxNestingLevel) 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.
boyerMooreFinder(needle) Sets up Boyer-Moore matching for use with find below. By default, elements are compared for equality.
commonPrefix(r1, r2) Returns the common prefix of two ranges.
count(haystack, needle) 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.
countUntil(haystack, needles) Counts elements in the given forward range until the given predicate is true for one of the given needles.
endsWith(doesThisEnd, withOneOfThese) Checks if the given range ends with (one of) the given needle(s). The reciprocal of startsWith.
find(haystack, needle) Finds an individual element in an input range. Elements of haystack are compared with needle by using predicate pred with pred(haystack.front, needle). find performs Ο(walkLength(haystack)) evaluations of pred.
find(haystack, needles) Finds two or more needles into a haystack. The predicate pred is used throughout to compare elements. By default, elements are compared for equality.
find(haystack, needle) Finds needle in haystack efficiently using the Boyer-Moore method.
findAdjacent(r) Advances r until it finds the first two adjacent elements a, b that satisfy pred(a, b). Performs Ο(r.length) evaluations of pred.
findAmong(seq, choices) Searches the given range for an element that matches one of the given choices.
findSkip(haystack, needle) Finds needle in haystack and positions haystack right after the first occurrence of needle.
findSplit(haystack, needle) These functions find the first occurrence of needle in haystack and then split haystack as follows.
findSplitAfter(haystack, needle) These functions find the first occurrence of needle in haystack and then split haystack as follows.
findSplitBefore(haystack, needle) These functions find the first occurrence of needle in haystack and then split haystack as follows.
maxCount(range) Computes the minimum (respectively maximum) of range along with its number of occurrences. Formally, the minimum is a value x in range such that pred(a, x) is false for all values a in range. Conversely, the maximum is a value x in range such that pred(x, a) is false for all values a in range (note the swapped arguments to pred).
maxElement(r) Iterates the passed range and returns the maximal element. A custom mapping function can be passed to map. In other languages this is sometimes called argmax.
maxIndex(range) Computes the index of the first occurrence of range's maximum element.
maxPos(range) Computes a subrange of range starting at the first occurrence of range's minimum (respectively maximum) and with the same ending as range, or the empty range if range itself is empty.
minCount(range) Computes the minimum (respectively maximum) of range along with its number of occurrences. Formally, the minimum is a value x in range such that pred(a, x) is false for all values a in range. Conversely, the maximum is a value x in range such that pred(x, a) is false for all values a in range (note the swapped arguments to pred).
minElement(r) Iterates the passed range and returns the minimal element. A custom mapping function can be passed to map. In other languages this is sometimes called argmin.
minIndex(range) Computes the index of the first occurrence of range's minimum element.
minPos(range) Computes a subrange of range starting at the first occurrence of range's minimum (respectively maximum) and with the same ending as range, or the empty range if range itself is empty.
startsWith(doesThisStart, withOneOfThese) Checks whether the given input range starts with (one of) the given needle(s) or, if no needles are given, if its front element fulfils predicate pred.
until(range, sentinel, openRight) Lazily iterates range until the element e for which pred(e, sentinel) is true.

Structs

NameDescription
BoyerMooreFinder Sets up Boyer-Moore matching for use with find below. By default, elements are compared for equality.
Until Lazily iterates range until the element e for which pred(e, sentinel) is true.

Templates

NameDescription
all Checks if all of the elements verify pred.
any Checks if any of the elements verifies pred. !any can be used to verify that none of the elements verify pred. This is sometimes called exists in other languages.
canFind Convenience function. Like find, but only returns whether or not the search was successful.
skipOver Skip over the initial portion of the first given range (haystack) that matches any of the additionally given ranges (needles) fully, or if no second range is given skip over the elements that fulfill pred. Do nothing if there is no match.

Aliases

NameTypeDescription
OpenRight Flag!("openRight") Interval option specifier for until (below) and others.

Authors

Andrei Alexandrescu

License

Boost License 1.0.