Display the source code in std/algorithm/searching.d from which this page was generated on github.

If you spot a problem with this page, click here to create a Bugzilla issue.

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.
`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(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

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.
`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.

Aliases

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

Authors

Andrei Alexandrescu

License

Boost License 1.0.