std.algorithm.searching.find - multiple declarations

Prototype

Range1 find(Range1, alias pred, Range2)(
  Range1 haystack,
  BoyerMooreFinder!(pred,Range2) needle
);

Parameters

Returns

haystack advanced such that needle is a prefix of it (if no such position exists, returns haystack advanced to termination).

Example

int[] a = [ -1, 0, 1, 2, 3, 4, 5 ];
int[] b = [ 1, 2, 3 ];

assert(find(a, boyerMooreFinder(b)) == [ 1, 2, 3, 4, 5 ]);
assert(find(b, boyerMooreFinder(a)).empty);

Performs Ο(walkLength(haystack) * walkLength(needle)) comparisons in the worst case. There are specializations that improve performance by taking advantage of bidirectional or random access in the given ranges (where possible), depending on the statistics of the two ranges' content.

Prototype

R1 find(alias pred, R1, R2)(
  R1 haystack,
  R2 needle
)
if (isForwardRange!R1 && isForwardRange!R2 && is(typeof(binaryFun!pred(haystack.front, needle.front)) : bool) && !isRandomAccessRange!R1);

Parameters

Returns

haystack advanced such that needle is a prefix of it (if no such position exists, returns haystack advanced to termination).

Example

import std.container : SList;

assert(find("hello, world", "World").empty);
assert(find("hello, world", "wo") == "world");
assert([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)];
assert(a.find!"a.x == b"([2, 3]) == [C(2,0), C(3,1), C(4,0)]);
assert(a[1 .. $].find!"a.x == b"([2, 3]) == [C(2,0), C(3,1), C(4,0)]);

To find the last element of a bidirectional haystack satisfying pred, call find!(pred)(retro(haystack)). See std.range.retro.

Prototype

InputRange find(alias pred, InputRange)(
  InputRange haystack
)
if (isInputRange!InputRange);

Parameters

Returns

haystack advanced such that the front element is the one searched for; that is, until binaryFun!pred(haystack.front, needle) is true. If no such position exists, returns an empty haystack.

See Also

STL's find_if

Example

auto arr = [ 1, 2, 3, 4, 1 ];
assert(find!("a > 2")(arr) == [ 3, 4, 1 ]);

// with predicate alias
bool pred(int x) { return x + 1 > 1.5; }
assert(find!(pred)(arr) == arr);

To find the last occurrence of needle in haystack, call find(retro(haystack), needle). See std.range.retro.

Prototype

InputRange find(alias pred, InputRange, Element)(
  InputRange haystack,
  Element needle
)
if (isInputRange!InputRange && is(typeof(binaryFun!pred(haystack.front, needle)) : bool));

Parameters

Constraints

isInputRange!InputRange && is(typeof(binaryFun!pred(haystack.front, needle) : bool))

Returns

haystack advanced such that the front element is the one searched for; that is, until binaryFun!pred(haystack.front, needle) is true. If no such position exists, returns an empty haystack.

See Also

STL's find

Example

import std.algorithm.comparison : equal;
import std.container : SList;

assert(find("hello, world", ',') == ", world");
assert(find([1, 2, 3, 5], 4) == []);
assert(equal(find(SList!int(1, 2, 3, 4, 5)[], 4), SList!int(4, 5)[]));
assert(find!"a > b"([1, 2, 3, 5], 2) == [3, 5]);

auto a = [ 1, 2, 3 ];
assert(find(a, 5).empty);       // not found
assert(!find(a, 2).empty);      // found

// Case-insensitive find of a string
string[] s = [ "Hello", "world", "!" ];
assert(!find!("toLower(a) == b")(s, "hello").empty);

Prototype

Tuple!(Range,size_t) find(alias pred, Range, Ranges...)(
  Range haystack,
  Ranges needles
)
if (Ranges.length > 1 && is(typeof(startsWith!pred(haystack, needles))));

Parameters

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 ints or arrays of ints in an array of ints. 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.length * max(needles.length)). (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

int[] a = [ 1, 4, 2, 3 ];
assert(find(a, 4) == [ 4, 2, 3 ]);
assert(find(a, [ 1, 4 ]) == [ 1, 4, 2, 3 ]);
assert(find(a, [ 1, 3 ], 4) == tuple([ 4, 2, 3 ], 2));
// Mixed types allowed if comparable
assert(find(a, 5, [ 1.2, 3.5 ], 2.0) == tuple([ 2, 3 ], 3));