std.algorithm.searching.find
- multiple declarations
Function find
Finds an element e
of an input range
where pred(e)
is true
.
find
behaves similarly todropWhile
in other languages.- To find the *last* matching element in a
bidirectional
haystack
, callfind!pred(retro(haystack))
. Seestd
..range .retro
InputRange find(alias pred, InputRange)
(
InputRange haystack
)
if (isInputRange!InputRange);
Complexity
Parameters
Name | Description |
---|---|
pred | The predicate to match an element. |
haystack | The input range searched in. |
Returns
haystack
advanced such that the front element satisfies pred
.
If no such element exists, returns an empty haystack
.
Example
auto arr = [ 1, 2, 3, 4, 1 ];
writeln(find!("a > 2")(arr)); // [3, 4, 1]
// with predicate alias
bool pred(int e) => e + 1 > 1.5;
writeln(find!(pred)(arr)); // arr
Function find
Finds an individual element in an input range.
Elements of haystack
are compared with needle
by using predicate
pred
with pred(haystack
.
The predicate is passed to binaryFun
, and can either accept a
string, or any callable that can be executed via pred(element, element)
.
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));
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));
If haystack
is a forward range,
needle
can be a forward range too.
In this case startsWith!pred(haystack, needle)
is evaluated on each evaluation.
"a != b"
.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" . |
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!((e, n) => e > n)(4)); // [5, 6, 9]
writeln(arr .find!((e, n) => e < n)(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!((e, n) => toLower(e) == n)("hello")); // s
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, Needles...)
(
Range haystack,
Needles needles
)
if (Needles .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);