View source code
Display the source code in std/algorithm/searching.d from which this page was generated on github.
Report a bug
If you spot a problem with this page, click here to create a Bugzilla issue.
Improve this page
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.

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. Performs Ο(walkLength(haystack)) evaluations of pred.

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,
  scope Element needle
)
if (isInputRange!InputRange && is(typeof(binaryFun!pred(haystack.front, needle)) : bool));

Parameters

NameDescription
pred The predicate for comparing each element with the needle, defaulting to "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.

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;
import std.range;
import std.range.primitives : empty;

auto arr = assumeSorted!"a < b"([1, 2, 4, 4, 4, 4, 5, 6, 9]);
writeln(find(arr, 4)); // assumeSorted!"a < b"([4, 4, 4, 4, 5, 6, 9])
writeln(find(arr, 1)); // arr
writeln(find(arr, 9)); // assumeSorted!"a < b"([9])
writeln(find!"a > b"(arr, 4)); // assumeSorted!"a < b"([5, 6, 9])
writeln(find!"a < b"(arr, 4)); // arr
assert(find(arr, 0).empty());
assert(find(arr, 10).empty());
assert(find(arr, 8).empty());

auto r = assumeSorted!"a > b"([10, 7, 3, 1, 0, 0]);
writeln(find(r, 3)); // assumeSorted!"a > b"([3, 1, 0, 0])
writeln(find!"a > b"(r, 8)); // r
writeln(find!"a < b"(r, 5)); // assumeSorted!"a > b"([3, 1, 0, 0])

writeln(find("hello, world", ',')); // ", world"
writeln(find([1, 2, 3, 5], 4)); // []
assert(equal(find(SList!int(1, 2, 3, 4, 5)[], 4), SList!int(4, 5)[]));
writeln(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);

Function find

Advances the input range haystack by calling haystack.popFront until either pred(haystack.front), or haystack.empty. Performs Ο(haystack.length) evaluations of pred.

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

find behaves similar to dropWhile in other languages.

Prototype

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

Parameters

NameDescription
pred The predicate for determining if a given element is the one being searched for.
haystack The input range to search in.

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 ];
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

Function find

Finds the first occurrence of a forward range in another forward range.

Performs Ο(walkLength(haystack) * walkLength(needle)) comparisons in the worst case. There are specializations that improve performance by taking advantage of bidirectional range 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,
  scope R2 needle
)
if (isForwardRange!R1 && isForwardRange!R2 && is(typeof(binaryFun!pred(haystack.front, needle.front)) : bool));

Parameters

NameDescription
pred The predicate to use for comparing respective elements from the haystack and the needle. Defaults to simple equality "a == b".
haystack The forward range searched in.
needle The forward range searched for.

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;
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.

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

NameDescription
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 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

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.

Prototype

RandomAccessRange find(RandomAccessRange, alias pred, InputRange)(
  RandomAccessRange haystack,
  scope BoyerMooreFinder!(pred,InputRange) needle
);

Parameters

NameDescription
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);

Authors

Andrei Alexandrescu

License

Boost License 1.0.

Comments