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. minElement([3, 4, 1, 2]) returns 2.
maxIndex Index of the maximal element of a range. maxElement([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.
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.

Functions

Name Description
balancedParens 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 Sets up Boyer-Moore matching for use with find below. By default, elements are compared for equality.
commonPrefix Returns the common prefix of two ranges.
count 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 Counts elements in the given forward range until the given predicate is true for one of the given needles.
countUntil Similar to the previous overload of countUntil, except that this one evaluates only the predicate pred.
endsWith Checks if the given range ends with (one of) the given needle(s). The reciprocal of startsWith.
find 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.
find Advances the input range haystack by calling haystack.popFront until either pred(haystack.front), or haystack.empty. Performs Ο(haystack.length) evaluations of pred.
find Finds the first occurrence of a forward range in another forward range.
find 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 Finds needle in haystack efficiently using the Boyer-Moore method.
findAdjacent Advances r until it finds the first two adjacent elements a, b that satisfy pred(a, b). Performs Ο(r.length) evaluations of pred.
findAmong Searches the given range for an element that matches one of the given choices.
findSkip Finds needle in haystack and positions haystack right after the first occurrence of needle.
findSplit These functions find the first occurrence of needle in haystack and then split haystack as follows.
findSplitAfter These functions find the first occurrence of needle in haystack and then split haystack as follows.
findSplitBefore These functions find the first occurrence of needle in haystack and then split haystack as follows.
maxCount 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 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 Computes the index of the first occurrence of range's maximum element.
maxPos 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 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 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 Computes the index of the first occurrence of range's minimum element.
minPos 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.
skipOver Skip over the initial portion of the first given range that matches the second range, or if no second range is given skip over the elements that fullfil pred. Do nothing if there is no match.
skipOver Skip over the first element of the given range if it matches the given element, otherwise do nothing.
startsWith 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 Lazily iterates range until the element e for which pred(e, sentinel) is true.

Structs

Name Description
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

Name Description
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.

Aliases

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

Authors

Andrei Alexandrescu

License

Boost License 1.0.

Comments