An introduction to the 8 main searching algorithms in the C++ standard library, including

`find`

, `find_if`

, `find_if_not`

, `find_first_of`

, `adjacent_find`

, `search_n`

, `search`

, and `find_end`

.Updated

In this lesson, we cover the 8 most useful searching algorithms within the standard library: `find`

, `find_if`

, `find_if_not`

, `find_first_of`

, `adjacent_find`

, `search_n`

, `search`

, and `find_end`

.

All the algorithms in this section are available within the `<algorithm>`

Â header:

`#include <algorithm>`

We use these algorithms to traverse through our containers to find objects, or sequences of objects, in differentÂ ways.

`std::ranges::find()`

The `std::ranges::find()`

algorithm is the basic, bread-and-butter search. We pass it a container and an object weâ€™re looking for in that container. The algorithm returns an iterator to the first element that itÂ finds:

```
#include <algorithm>
#include <iostream>
#include <vector>
int main() {
std::vector Numbers{1, 2, 3, 4, 5};
auto Result{std::ranges::find(Numbers, 3)};
std::cout << "Found a " << *Result
<< " in position "
<< std::distance(Numbers.begin(),
Result);
}
```

`Found a 3 in position 2`

If our object was not found, the algorithm will return an end iterator, which is equivalent to what is returned from calling `end()`

on our inputÂ range.

Therefore, if weâ€™re not sure if our range includes what weâ€™re looking for, we should perform that equality check before we dereference the returnedÂ iterator:

```
#include <algorithm>
#include <iostream>
#include <vector>
int main() {
std::vector Numbers{1, 2, 3, 4, 5};
auto Result{std::ranges::find(Numbers, 6)};
if (Result == Numbers.end()) {
std::cout << "We did not find a 6";
} else {
std::cout << "We found a 6 - safe to "
"dereference";
}
}
```

`We did not find a 6`

As with any range-based algorithm, we can provide our range as an iterator-sentinelÂ pair:

```
#include <algorithm>
#include <vector>
int main() {
std::vector Numbers{1, 2, 3, 4, 5};
std::ranges::find(
Numbers.begin(), Numbers.end(), 3);
}
```

`std::ranges::find()`

, and and every other algorithm we cover in this lesson, has an older variation that works with iterators. These are accessible by excluding the `ranges`

namespace qualifier when calling the functions - for example, we'd replace `std::ranges::find()`

with `std::find()`

:

```
#include <algorithm>
#include <vector>
int main() {
std::vector Numbers{1, 2, 3, 4, 5};
std::find(Numbers.begin(), Numbers.end(), 3);
}
```

For search algorithms to determine if they found what theyâ€™re looking for, they use the equality operator `==`

byÂ default.

As such, for a type to be compatible with the search algorithms, it usually needs to implement thatÂ operator.

Below, we show an example where a user-defined type is beingÂ used:

```
#include <algorithm>
#include <iostream>
#include <vector>
struct MyStruct {
int Value;
bool operator==(const MyStruct& Other) const {
return Value == Other.Value;
}
};
int main() {
std::vector Numbers{MyStruct{1}, MyStruct{2},
MyStruct{3}, MyStruct{4},
MyStruct{5}};
auto Result{
std::ranges::find(Numbers, MyStruct{2})};
std::cout << "Found struct with value "
<< Result->Value;
}
```

`Found struct with value: 2`

Like with most range-based algorithms, we can execute searches on projections of ourÂ inputs.

Below, we project our objects to their absolute value, allowing us to search for `3`

, and find either `3`

or `-3`

:

```
#include <algorithm>
#include <iostream>
#include <vector>
int main() {
std::vector Numbers{-1, 2, -3, 4, -5};
auto Projector{[](int a) {
return std::abs(a);
}};
auto Result{
std::ranges::find(Numbers, 3, Projector)};
std::cout << "Found a " << *Result;
}
```

`Found a -3`

`std::ranges::find_if()`

The `find_if()`

algorithm works similarly to `find()`

. However, instead of doing an equality check using `==`

on each object to determine if it matches an argument. the algorithm instead passes each object into a predicate function that weÂ provide.

If that predicate returns `true`

, that object is considered to have satisfied the search criteria, and the `find_if()`

algorithm returns an iterator toÂ it.

Below, we search our range for an evenÂ number:

```
#include <algorithm>
#include <iostream>
#include <vector>
int main() {
std::vector Numbers{1, 2, 3, 4, 5};
auto isEven{[](int x) { return x % 2 == 0; }};
auto Result{
std::ranges::find_if(Numbers, isEven)};
std::cout << "Found a " << *Result
<< " in position "
<< std::distance(Numbers.begin(),
Result);
}
```

`Found a 2 in position 1`

Similar to `find()`

, `find_if()`

will return an end iterator if it doesnâ€™t findÂ anything.

`std::ranges::find_if_not()`

The `find_if_not()`

algorithm is similar to `find_if()`

, except it will find the first element for which the predicate function returns `false`

.

Below, we find the first odd number, by finding the first number for which our `isEven()`

function returns `false`

:

```
#include <algorithm>
#include <iostream>
#include <vector>
int main() {
std::vector Numbers{1, 2, 3, 4, 5, 3};
auto isEven{[](int x) { return x % 2 == 0; }};
auto Result{
std::ranges::find_if_not(Numbers, isEven)};
std::cout << "Found a " << *Result
<< " in position "
<< std::distance(Numbers.begin(),
Result);
}
```

`Found a 1 in position 0`

Similar to the other algorithms, `find_if_not()`

will return an end iterator if it doesnâ€™t findÂ anything.

`std::ranges::find_first_of()`

The `find_first_of()`

algorithm is useful when we want to find any of a range of possibilities. In the below example, we search our collection for any of `0`

, `5`

, or `1`

. As soon as it finds any of those values in the input range, it will return an iterator toÂ it.

```
#include <algorithm>
#include <iostream>
#include <vector>
int main() {
std::vector Numbers{1, 2, 3, 4, 5};
std::vector SearchTerms{0, 5, 1};
auto Result{std::ranges::find_first_of(
Numbers, SearchTerms)};
std::cout << "Found a " << *Result
<< " in position "
<< std::distance(Numbers.begin(),
Result);
}
```

`Found a 1 in position 0`

Similar to the other algorithms, `find_first_of()`

will return an end iterator for the input range if it doesnâ€™t findÂ anything.

`std::ranges::adjacent_find()`

The `adjacent_find()`

algorithm will search our container for the first instance where at least two adjacent objects are equal to each other. It will return an iterator to the first object in theÂ sequence.

In the following example, our input range has two adjacent `4`

s, which the algorithm findsÂ successfully:

```
#include <algorithm>
#include <iostream>
#include <vector>
int main() {
std::vector Numbers{1, 2, 3, 4, 4, 5};
auto Result{
std::ranges::adjacent_find(Numbers)};
std::cout << "Found two adjacent " << *Result
<< "s starting at position "
<< std::distance(Numbers.begin(),
Result);
}
```

`Found two adjacent 4s starting at position 3`

`adjacent_find()`

will return an end iterator if it doesnâ€™t findÂ anything.

`std::ranges::search_n()`

The `search_n()`

algorithm looks for a sequence of elements that match an equality check. As such, it takes 3Â inputs:

- The range to search
- The number of sequential elements to search for
- The object to search for

The following example passes `Numbers`

, `2`

, and `4`

, therefore the algorithm searches `Numbers`

for at least `2`

sequential `4`

s. It finds it and returns that sequence as a **subrange**.

```
#include <algorithm>
#include <iostream>
#include <vector>
int main() {
std::vector Numbers{1, 2, 3, 4, 4, 5};
auto Result{
std::ranges::search_n(Numbers, 2, 4)};
std::cout << "Found two adjacent 4s starting "
"at position "
<< std::distance(Numbers.begin(),
Result.begin());
}
```

`Found two adjacent 4s starting at position 3`

A subrange is an example of a C++ **view**. We introduced these concepts earlier in theÂ course:

If the `search_n()`

algorithm does not find what we asked, the subrange it returns will be an empty range, with its `begin()`

iterator being equal to its `end()`

iterator. Both iterators will also be equal to the `end()`

iterator of the inputÂ range.

Therefore, we can check if our search did not find anything by checking for these conditions. Below, we show bothÂ options:

```
#include <algorithm>
#include <iostream>
#include <vector>
int main() {
std::vector Numbers{1, 2, 3, 4, 4, 5};
auto Result{std::ranges::search_n(Numbers, 3, 4)};
if (Result.begin() == Result.end()) {
std::cout << "Not found\n";
}
if (Result.begin() == Numbers.end()) {
std::cout << "Not found\n";
}
}
```

```
Not found
Not found
```

Depending on the specific type of range our view is based on, we may have access to the `empty()`

method, which gives us a friendlier way to check if no results wereÂ found:

```
#include <algorithm>
#include <iostream>
#include <vector>
int main() {
std::vector Numbers{1, 2, 3, 4, 4, 5};
auto Result{std::ranges::search_n(Numbers, 3, 4)};
if (Result.empty()) {
std::cout << "Not found";
}
}
```

`Not found`

`std::ranges::search()`

The `std::ranges::search()`

algorithm searches a range for a specific subrange. In the following example, we search the range `1, 2, 3, 1, 2, 3`

for the subrange `1, 2, 3`

.

The `search()`

algorithm finds the first matching subrange, which begins at position 0 in thisÂ case:

```
#include <algorithm>
#include <iostream>
#include <vector>
int main() {
std::vector Numbers{1, 2, 3, 1, 2, 3};
std::vector Subsequence{1, 2, 3};
auto Result{
std::ranges::search(Numbers, Subsequence)};
if (Result.empty()) {
std::cout << "Subsequence not found";
} else {
std::cout << "Found Subsequence: ";
for (int& i : Result) {
std::cout << i << ", ";
}
std::cout
<< "\nSubsequence starts at position "
<< std::distance(Numbers.begin(),
Result.begin());
}
}
```

```
Found Subsequence: 1, 2, 3,
Subsequence starts at position 0
```

The main use case for searching a range for a subrange comes when working with strings. Standard library strings are also ranges, so are compatible with `search()`

and the other algorithms weâ€™ve shownÂ here.

Below, we use `search()`

to find a string within another string, thereby determining a userâ€™s emailÂ provider:

```
#include <algorithm>
#include <iostream>
#include <string>
int main() {
std::string EmailAddress{"new-user@gmail.com"};
std::string SearchString{"@gmail."};
auto Result{std::ranges::search(EmailAddress,
SearchString)};
if (!Result.empty()) {
std::cout << "User is using Gmail";
}
}
```

`User is using Gmail`

Many string types may support this functionality natively, giving a cleaner API. As of C++23, this includes `std::string`

, which provides the `contains()`

Â method:

```
#include <iostream>
#include <string>
int main() {
std::string EmailAddress{"new-user@gmail.com"};
std::string SearchString{"@gmail."};
auto Result{
EmailAddress.contains(SearchString)};
if (Result) {
std::cout << "User is using Gmail";
}
}
```

`User is using Gmail`

There are many different ways to search through aÂ collection.

The `std::search()`

algorithm accepts an optional additional argument, where we can provide a specific implementation. The standard library also bundles a few options we can useÂ directly:

`std::default_searcher`

(used if we donâ€™t specify a searcher)`std::boyer_moore_searcher`

`std::boyer_moore_horspool_searcher`

All of these algorithms are available by including `<functional>`

Note, the ability to specify a custom searcher is currently restricted to `std::search()`

. It is not available to other algorithms, including `std::ranges::search`

.

The following is an example of how to use the Boyer-MooreÂ searcher:

```
#include <algorithm>
#include <functional>
#include <iostream>
#include <string>
int main() {
std::string EmailAddress{"new-user@gmail.com"};
std::string SearchString{"@gmail."};
std::boyer_moore_searcher Searcher{
SearchString.begin(), SearchString.end()};
auto Result{std::search(EmailAddress.begin(),
EmailAddress.end(),
Searcher)};
if (Result != EmailAddress.end()) {
std::cout << "User is using Gmail";
}
}
```

`User is using Gmail`

When it comes to choosing which algorithm to use, there generally is no correct answer. The performance characteristics of different algorithms vary on situational factors, suchÂ as:

- the length of the substring weâ€™re looking for (sometimes called the
)**needle** - the length of text weâ€™re searching for the needle in (sometimes called the
)**haystack** - whether either of those strings is known at compile time

For example, the Boyer-Moore searchers tend to be faster than the default searcher when working with large inputs, like searching through the text of a book. But, they are generally slower when the inputs are smaller strings, like names and emailÂ addresses.

In general, if your code is running in a performance-critical context, the best option is just to try out different options with arguments that are representative of your data, and see what worksÂ best.

`std::ranges::find_end()`

Finally, the `find_end()`

algorithm works in much the same way as `search()`

, except it will search in the opposite direction. That means that `find_end()`

will return the **last** instance of the subsequence weâ€™re searchingÂ for.

Here, we find the last instance of `1, 2, 3`

within our `1, 2, 3, 1, 2, 3`

Â range:

```
#include <algorithm>
#include <iostream>
#include <vector>
int main() {
std::vector Numbers{1, 2, 3, 1, 2, 3};
std::vector Subsequence{1, 2, 3};
auto Result{std::ranges::find_end(Numbers,
Subsequence)};
if (Result.empty()) {
std::cout << "Subsequence not found";
} else {
std::cout << "Found Subsequence: ";
for (int& i : Result) {
std::cout << i << ", ";
}
std::cout
<< "\nSubsequence starts at position "
<< std::distance(Numbers.begin(),
Result.begin());
}
}
```

```
Found Subsequence: 1, 2, 3,
Subsequence starts at position 3
```

Even though `find_end()`

works in reverse, when the subsequence is not found, its behavior is equivalent to `search()`

, returning an empty subrange that begins and ends at the end iterator of our inputÂ range:

```
#include <algorithm>
#include <iostream>
#include <vector>
int main() {
std::vector Numbers{1, 2, 3};
std::vector Subsequence{4, 5, 6};
auto Result{std::ranges::find_end(
Numbers, Subsequence)};
if (Result.empty()) {
std::cout << "Subsequence not found\n";
}
if (Result.end() == Numbers.end()) {
std::cout << "Subsequence not found\n";
}
if (Result.begin() == Result.end()) {
std::cout << "Subsequence not found\n";
}
}
```

```
Subsequence not found
Subsequence not found
Subsequence not found
```

In this lesson, we explored the standard libraryâ€™s search algorithms, from simple searches to working with custom types and comparisonÂ functions.

- Introduced the eight main search algorithms:
`find()`

,`find_if()`

,`find_if_not()`

,`find_first_of()`

,`adjacent_find()`

,`search_n()`

,`search()`

, and`find_end()`

. - Demonstrated the use of
`std::ranges::find()`

for basic search operations and handling cases where the search item is not found. - Explained the difference between range-based algorithms and their iterator-sentinel pair counterparts.
- Covered the requirements for custom types to work with search algorithms, specifically the need for an equality operator
`==`

. - Illustrated the use of projection functions to transform elements before comparison.
- Showcased
`std::ranges::find_if()`

and`std::ranges::find_if_not()`

for conditional searches. - Demonstrated how to use
`std::ranges::find_first_of()`

to find any of a set of possible values. - Explained
`std::ranges::adjacent_find()`

for finding the first pair of adjacent equal elements. - Showed how
`std::ranges::search_n()`

searches for a sequence of repeated elements. - Described
`std::ranges::search()`

for finding subranges and`std::ranges::find_end()`

for finding the last instance of a subsequence. - Discussed the customization of search operations with custom searchers, including the Boyer-Moore algorithm.

Was this lesson useful?

Updated

Lesson Contents### Search Algorithms

An introduction to the 8 main searching algorithms in the C++ standard library, including `find`

, `find_if`

, `find_if_not`

, `find_first_of`

, `adjacent_find`

, `search_n`

, `search`

, and `find_end`

.

This lesson is part of theÂ course:### Professional C++

Comprehensive course covering advanced concepts, and how to use them on large-scale projects.