Phobos' std.algorithm module includes search functions that can work on any ranges. It automatically specializes based on type information. Searching a sorted range is faster than an unsorted range.
Searching has a number of different scenarios, each with different methods:
- If you want to know if something is present, use
canFind. - Finding an item generically can be done with the
findfunction. It returns the remainder of the range, with the located item at the front. - When searching for a substring in a string, you can use
haystack.find(boyerMooreFinder(needle)). This uses the Boyer-Moore algorithm which may give better performance. - If you want to know the index where the item is located, use
countUntil. It returns a numeric index into the range, just like theindexOffunction for strings. - Each
findfunction can take a predicate to customize the search operation. - When you know your range is sorted but the type doesn't already prove it, you may call
assumeSortedon it before passing it to the search functions. TheassumeSortedfunction has no runtime cost; it only adds information to the type that is used for compile-time specialization.
The search functions in Phobos make use of the ranges' available features to choose good-fit algorithms. Pass them efficiently implemented ranges with accurate capabilities to get best performance.
The find function returns the remainder of the data because this is the most general behavior; it doesn't need random access, like returning an index, and doesn't require an additional function if you are implementing a function to split a range on a given condition. The find function can work with a basic input range, serving as a foundation to implement whatever you need on top of it, and it will transparently optimize to use more range features if available.