std.algorithm.searching.find
- multiple declarations
Function find
Finds an individual element in an input range.
Elements of haystack
are compared with needle
by using predicate
pred
with pred(haystack
.
find
performs Ο(walkLength(haystack)
) evaluations of pred
.
InputRange find(alias pred, InputRange, Element)
(
InputRange haystack,
scope Element needle
)
if (isInputRange!InputRange && is(typeof(binaryFun!pred(haystack .front, needle)) : bool) && !is(typeof(binaryFun!pred(haystack .front, needle .front)) : bool));
InputRange find(alias pred, InputRange)
(
InputRange haystack
)
if (isInputRange!InputRange);
R1 find(alias pred, R1, R2)
(
R1 haystack,
scope R2 needle
)
if (isForwardRange!R1 && isForwardRange!R2 && is(typeof(binaryFun!pred(haystack .front, needle .front)) : bool));
The predicate is passed to binaryFun
, and can either accept a
string, or any callable that can be executed via pred(element, element)
.
To find the last occurrence of needle
in a
bidirectional haystack
,
call find(retro(haystack), needle)
. See std
.
If no needle
is provided, pred(haystack
will be evaluated on each
element of the input range.
If input
is a forward range,
needle
can be a forward range too.
In this case startsWith!pred(haystack, needle)
is evaluated on each evaluation.
Note
find
behaves similar to dropWhile
in other languages.
Complexity
find
performs Ο(walkLength(haystack)
) evaluations of pred
.
There are specializations that improve performance by taking
advantage of bidirectional
or random access
ranges (where possible).
Parameters
Name | Description |
---|---|
pred | The predicate for comparing each element with the needle, defaulting to equality "a == b" .
The negated predicate "a != b" can be used to search instead for the first
element not matching the needle.
|
haystack | The input range searched in. |
needle | The element searched for. |
Returns
haystack
advanced such that the front element is the one searched for;
that is, until binaryFun!pred(haystack
is true
. If no
such position exists, returns an empty haystack
.
See ALso
Example
import std .range .primitives;
auto arr = [1, 2, 4, 4, 4, 4, 5, 6, 9];
writeln(arr .find(4)); // [4, 4, 4, 4, 5, 6, 9]
writeln(arr .find(1)); // arr
writeln(arr .find(9)); // [9]
writeln(arr .find!( (a, b) => a > b)(4)); // [5, 6, 9]
writeln(arr .find!( (a, b) => a < b)(4)); // arr
assert(arr .find(0) .empty);
assert(arr .find(10) .empty);
assert(arr .find(8) .empty);
writeln(find("hello, world", ',')); // ", world"
Example
Case-insensitive find of a string
import std .range .primitives;
import std .uni : toLower;
string[] s = ["Hello", "world", "!"];
writeln(s .find!( (a, b) => toLower(a) == b)("hello")); // s
Example
auto arr = [ 1, 2, 3, 4, 1 ];
writeln(find!("a > 2")(arr)); // [3, 4, 1]
// with predicate alias
bool pred(int x) { return x + 1 > 1.5; }
writeln(find!(pred)(arr)); // arr
Example
import std .container : SList;
import std .range .primitives : empty;
import std .typecons : Tuple;
assert(find("hello, world", "World") .empty);
writeln(find("hello, world", "wo")); // "world"
writeln([1, 2, 3, 4] .find(SList!int(2, 3)[])); // [2, 3, 4]
alias C = Tuple!(int, "x", int, "y");
auto a = [C(1,0), C(2,0), C(3,1), C(4,0)];
writeln(a .find!"a.x == b"([2, 3])); // [C(2, 0), C(3, 1), C(4, 0)]
writeln(a[1 .. $] .find!"a.x == b"([2, 3])); // [C(2, 0), C(3, 1), C(4, 0)]
Function 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.
Tuple!(Range,size_t) find(alias pred, Range, Ranges...)
(
Range haystack,
Ranges needles
)
if (Ranges .length > 1 && is(typeof(startsWith!pred(haystack, needles))));
Parameters
Name | Description |
---|---|
pred | The predicate to use for comparing elements. |
haystack | The target of the search. Must be an input range.
If any of needles is a range with elements comparable to
elements in haystack , then haystack must be a
forward range
such that the search can backtrack.
|
needles | One or more items to search for. Each of needles must
be either comparable to one element in haystack , or be itself a
forward range with elements comparable with elements in
haystack . |
Returns
A tuple containing haystack
positioned to match one of the
needles and also the 1-based index of the matching element in needles
(0 if none of needles
matched, 1 if needles[0]
matched, 2 if needles[1]
matched...). The first needle to be found
will be the one that matches. If multiple needles are found at the
same spot in the range, then the shortest one is the one which matches
(if multiple needles of the same length are found at the same spot (e.g
"a"
and 'a'
), then the left-most of them in the argument list
matches).
The relationship between haystack
and needles
simply means
that one can e.g. search for individual int
s or arrays of int
s in an array of int
s. In addition, if elements are
individually comparable, searches of heterogeneous types are allowed
as well: a double[]
can be searched for an int
or a short[]
, and conversely a long
can be searched for a float
or a double[]
. This makes for efficient searches without the need
to coerce one side of the comparison into the other's side type.
The complexity of the search is Ο(haystack
). (For needles that are individual items, length
is considered to be 1.) The strategy used in searching several
subranges at once maximizes cache usage by moving in haystack
as
few times as possible.
Example
import std .typecons : tuple;
int[] a = [ 1, 4, 2, 3 ];
writeln(find(a, 4)); // [4, 2, 3]
writeln(find(a, [1, 4])); // [1, 4, 2, 3]
writeln(find(a, [1, 3], 4)); // tuple([4, 2, 3], 2)
// Mixed types allowed if comparable
writeln(find(a, 5, [1.2, 3.5], 2.0)); // tuple([2, 3], 3)
Function find
Finds needle
in haystack
efficiently using the
Boyer-Moore method.
RandomAccessRange find(RandomAccessRange, alias pred, InputRange)
(
RandomAccessRange haystack,
scope BoyerMooreFinder!(pred,InputRange) needle
);
Parameters
Name | Description |
---|---|
haystack | A random-access range with length and slicing. |
needle | A BoyerMooreFinder . |
Returns
haystack
advanced such that needle
is a prefix of it (if no
such position exists, returns haystack
advanced to termination).
Example
import std .range .primitives : empty;
int[] a = [ -1, 0, 1, 2, 3, 4, 5 ];
int[] b = [ 1, 2, 3 ];
writeln(find(a, boyerMooreFinder(b))); // [1, 2, 3, 4, 5]
assert(find(b, boyerMooreFinder(a)) .empty);