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).
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.
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 needle in haystack efficiently using the Boyer-Moore method.
find	Finds the first occurrence of a forward range in another forward range.
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 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	Finds two or more needles into a haystack. The predicate pred is used throughout to compare elements. By default, elements are compared for equality.
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.
minCount
minPos
skipOver	Skip over the initial portion of the first given range that matches the second range, or 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).
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.

Enums

Name	Description
OpenRight	Interval option specifier for until (below) and others.

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.
canFind	Convenience function. Like find, but only returns whether or not the search was successful.

Authors

Andrei Alexandrescu

License

Boost License 1.0.

Comments