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 a tuple of three ranges `"abc"`, `"de"`, and `"fg"`.
`findSplitAfter`	`findSplitAfter("abcdefg", "de")` returns a tuple of two ranges `"abcde"` and `"fg"`.
`findSplitBefore`	`findSplitBefore("abcdefg", "de")` returns a tuple of 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

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 satisfy `pred`.
`any`	Checks if any of the elements satisfies `pred`. `!any` can be used to verify that none of the elements satisfy `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

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

Authors

Andrei Alexandrescu

License

Boost License 1.0.