C++ 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.

DreamShaper_v7_hipster_Sidecut_hair_modest_clothes_fully_cloth_0.jpg

Ryan McCombe

Posted 7 months ago

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:

1#include <algorithm>
2

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

Let's get started!

`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:

1#include <algorithm>
2#include <iostream>
3#include <vector>
4
5int main() {
6  std::vector Numbers{1, 2, 3, 4, 5};
7
8  auto Result{std::ranges::find(Numbers, 3)};
9
10  std::cout << "Found a " << *Result
11            << " in position "
12            << std::distance(Numbers.begin(),
13                             Result);
14}
15

1Found a 3 in position 2
2

If our object was not found, the algorithm will return a “past-the-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 compare our iterators before we dereference it:

1#include <algorithm>
2#include <iostream>
3#include <vector>
4
5int main() {
6  std::vector Numbers{1, 2, 3, 4, 5};
7
8  auto Result{std::ranges::find(Numbers, 7)};
9
10  if (Result == Numbers.end()) {
11    std::cout << "We did not find anything";
12  } else {
13    std::cout << "We found something - safe to "
14                 "dereference";
15  }
16}
17

1We did not find anything
2

Iterator-Based Algorithms

This, and every other algorithm in this lesson, has a variant that works directly with iterators instead of ranges. These are accessible by excluding the ranges namespace qualifier when calling the functions - for example, we'd replace std::ranges::find with std::find.

Below, we rewrite the previous example to use std::find instead of std::ranges::find:

1#include <algorithm>
2#include <iostream>
3#include <vector>
4
5int main() {
6  std::vector Numbers{1, 2, 3, 4, 5};
7
8  auto Result{std::find(Numbers.begin(),
9                        Numbers.end(), 3)};
10
11  std::cout << "Found a " << *Result
12            << " in position "
13            << std::distance(Numbers.begin(),
14                             Result);
15}
16

1Found a 3 in position 2
2

Search Algorithms with Custom Types

In order to determine if they found what they’re looking for, search algorithms use the equality operator, ==.

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

Below, we show an example of a custom struct type being used:

1#include <algorithm>
2#include <iostream>
3#include <vector>
4
5struct MyStruct {
6  int Value;
7  bool operator==(const MyStruct& Other) const {
8    return Value == Other.Value;
9  }
10};
11
12int main() {
13  std::vector Numbers{MyStruct{1}, MyStruct{2},
14                      MyStruct{3}, MyStruct{4},
15                      MyStruct{5}};
16
17  auto Result{
18      std::ranges::find(Numbers, MyStruct{2})};
19
20  std::cout << "Found struct with value "
21            << Result->Value;
22}
23

1Found struct with value: 2
2

`std::ranges::find_if`

The find_if algorithm works similarly to find but, instead of doing an equality check on the object, it passes the object into a predicate function that we provide.

If that predicate returns true when passed an object, that object is considered to have matched the search criteria.

Below, we search our range for an even number:

1#include <algorithm>
2#include <iostream>
3#include <vector>
4
5int main() {
6  std::vector Numbers{1, 2, 3, 4, 5};
7
8  auto isEven{[](int x) { return x % 2 == 0; }};
9
10  auto Result{
11      std::ranges::find_if(Numbers, isEven)};
12
13  std::cout << "Found a " << *Result
14            << " in position "
15            << std::distance(Numbers.begin(),
16                             Result);
17}
18

1Found a 2 in position 1
2

Similar to find, find_if will return a past-the-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:

1#include <algorithm>
2#include <iostream>
3#include <vector>
4
5int main() {
6  std::vector Numbers{1, 2, 3, 4, 5, 3};
7
8  auto isEven{[](int x) { return x % 2 == 0; }};
9
10  auto Result{
11      std::ranges::find_if_not(Numbers, isEven)};
12
13  std::cout << "Found a " << *Result
14            << " in position "
15            << std::distance(Numbers.begin(),
16                             Result);
17}
18

1Found a 1 in position 0
2

Similar to the other algorithms, find_if_not will return a past-the-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.

1#include <algorithm>
2#include <iostream>
3#include <vector>
4
5int main() {
6  std::vector Numbers{1, 2, 3, 4, 5};
7  std::vector SearchTerms{0, 5, 1};
8
9  auto Result{std::ranges::find_first_of(
10      Numbers, SearchTerms)};
11
12  std::cout << "Found a " << *Result
13            << " in position "
14            << std::distance(Numbers.begin(),
15                             Result);
16}
17

1Found a 1 in position 0
2

Similar to the other algorithms, find_first_of will return a past-the-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 4s, which the algorithm finds successfully:

1#include <algorithm>
2#include <iostream>
3#include <vector>
4
5int main() {
6  std::vector Numbers{1, 2, 3, 4, 4, 5};
7
8  auto Result{
9      std::ranges::adjacent_find(Numbers)};
10
11  std::cout << "Found two adjacent " << *Result
12            << "s starting at position "
13            << std::distance(Numbers.begin(),
14                             Result);
15}
16

1Found two adjacent 4s starting at position 3
2

adjacent_find will return a past-the-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 arguments:

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 4s. It finds it and returns that sequence as a subrange.

1#include <algorithm>
2#include <iostream>
3#include <vector>
4
5int main() {
6  std::vector Numbers{1, 2, 3, 4, 4, 5};
7
8  auto Result{
9      std::ranges::search_n(Numbers, 2, 4)};
10
11  std::cout << "Found two adjacent 4s starting "
12               "at position "
13            << std::distance(Numbers.begin(),
14                             Result.begin());
15}
16

1Found two adjacent 4s starting at position 3
2

A subrange is an example of a C++ view. We introduced subranges in our introduction to range-based algorithms, and we have a dedicated lesson on views:

Range Based Algorithms and `std::ranges::sort`

Learn how to efficiently work with collections of objects using range-based algorithms in C++

DreamShaper_v7_fantasy_female_space_pirate_Sidecut_hair_black_1.jpg

Standard Library Views

Learn how to create and use views in C++ using examples from std::views

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 comparing iterators. Below, we show two options:

1#include <algorithm>
2#include <iostream>
3#include <vector>
4
5int main() {
6  std::vector Numbers{1, 2, 3, 4, 4, 5};
7
8  auto Result{std::ranges::search_n(Numbers, 3, 4)};
9
10  if (Result.begin() == Result.end()) {
11    std::cout << "Not found\n";
12  }
13  
14  if (Result.begin() == Numbers.end()) {
15    std::cout << "Not found\n";
16  }
17}
18

1Not found
2Not found
3

Depending on the specific type of range it is, we may also have friendlier methods to determine if it is empty. For example, standard library linked lists and vectors have the empty method:

1#include <algorithm>
2#include <iostream>
3#include <vector>
4
5int main() {
6  std::vector Numbers{1, 2, 3, 4, 4, 5};
7
8  auto Result{std::ranges::search_n(Numbers, 3, 4)};
9
10  if (Result.empty()) {
11    std::cout << "Not found\n";
12  }
13}
14

1Not found
2

`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:

1#include <algorithm>
2#include <iostream>
3#include <vector>
4
5int main() {
6  std::vector Numbers{1, 2, 3, 1, 2, 3};
7  std::vector Subsequence{1, 2, 3};
8
9  auto Result{
10      std::ranges::search(Numbers, Subsequence)};
11
12  if (Result.empty()) {
13    std::cout << "Subsequence not found";
14  } else {
15    std::cout << "Found Subsequence: ";
16    for (int& i : Result) {
17      std::cout << i << ", ";
18    }
19    std::cout
20        << "\nSubsequence starts at position "
21        << std::distance(Numbers.begin(),
22                         Result.begin());
23  }
24}
25

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

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:

1#include <algorithm>
2#include <iostream>
3#include <string>
4
5int main() {
6  std::string EmailAddress{"new-user@gmail.com"};
7  std::string SearchString{"@gmail."};
8
9  auto Result{std::ranges::search(EmailAddress,
10                                  SearchString)};
11
12  if (!Result.empty()) {
13    std::cout << "User is using Gmail";
14  }
15}
16

1User is using Gmail
2

Customized Searchers with `std::search` - Boyer-Moore Algorithms

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:

1#include <algorithm>
2#include <functional>
3#include <iostream>
4#include <string>
5
6int main() {
7  std::string EmailAddress{"new-user@gmail.com"};
8  std::string SearchString{"@gmail."};
9
10  std::boyer_moore_searcher Searcher{
11      SearchString.begin(), SearchString.end()};
12
13  auto Result{std::search(EmailAddress.begin(),
14                          EmailAddress.end(),
15                          Searcher)};
16
17  if (Result != EmailAddress.end()) {
18    std::cout << "User is using Gmail";
19  }
20}
21

1User is using Gmail
2

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:

1#include <algorithm>
2#include <iostream>
3#include <vector>
4
5int main() {
6  std::vector Numbers{1, 2, 3, 1, 2, 3};
7  std::vector Subsequence{1, 2, 3};
8
9  auto Result{std::ranges::find_end(Numbers,
10                                    Subsequence)};
11
12  if (Result.empty()) {
13    std::cout << "Subsequence not found";
14  } else {
15    std::cout << "Found Subsequence: ";
16    for (int& i : Result) {
17      std::cout << i << ", ";
18    }
19    std::cout
20        << "\nSubsequence starts at position "
21        << std::distance(Numbers.begin(),
22                         Result.begin());
23  }
24}
25

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

Even though find_end works in reverse, when the subsequence is not found, its behavior is equivalent to search, returning a subrange that begins and ends at the past-the-end iterator of our input range:

1#include <algorithm>
2#include <iostream>
3#include <vector>
4
5int main() {
6  std::vector Numbers{1, 2, 3};
7  std::vector Subsequence{4, 5, 6};
8
9  auto Result{std::ranges::find_end(Numbers,
10                                    Subsequence)};
11
12  if (Result.end() == Numbers.end()) {
13    std::cout << "Subsequence not found\n";
14  }
15
16  if (Result.begin() == Result.end()) {
17    std::cout << "Subsequence not found\n";
18  }
19}
20

1Subsequence not found
2Subsequence not found
3

Was this lesson useful?

Ryan McCombe

Posted 7 months ago

This lesson is part of the course:

Professional C++

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

Whirlwind Tour of C++ Basics

Memory Management

Templates

Arrays and Linked Lists

Standard Library Data Structures

Working with Functions

Iterators and Algorithms

Standard Library Algorithms

61. C++ 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.

Exceptions and Error Handling

Objects, Classes and Modules

Strings and Streams

Files and Serialization

This lesson is part of the course:

Professional C++

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

Free, unlimited access!

This course includes:

106 Lessons
550+ Code Samples
96% Positive Reviews
Regularly Updated
Help and FAQ

Next Lesson

Binary Search in C++

Learn the advantages and restrictions of Binary Search, and then implement it using the two main C++ standard library algorithms: binary_search and lower_range

DreamShaper_v7_queen_Sidecut_hair_modest_clothes_fully_clothed_1.jpg

Contact|Privacy Policy|Terms of Use

C++ Search Algorithms

Professional C++

Ryan McCombe

std::ranges::find

Iterator-Based Algorithms

Search Algorithms with Custom Types

std::ranges::find_if

std::ranges::find_if_not

std::ranges::find_first_of

std::ranges::adjacent_find

std::ranges::search_n

Range Based Algorithms and std::ranges::sort

Standard Library Views

std::ranges::search

Customized Searchers with std::search - Boyer-Moore Algorithms

std::ranges::find_end

Was this lesson useful?

Ryan McCombe

Professional C++

Whirlwind Tour of C++ Basics

Memory Management

Templates

Arrays and Linked Lists

Standard Library Data Structures

Working with Functions

Iterators and Algorithms

Standard Library Algorithms

61.

C++ Search Algorithms

Exceptions and Error Handling

Objects, Classes and Modules

Strings and Streams

Files and Serialization

Professional C++

This course includes:

Binary Search in C++

`std::ranges::find`

`std::ranges::find_if`

`std::ranges::find_if_not`

`std::ranges::find_first_of`

`std::ranges::adjacent_find`

`std::ranges::search_n`

Range Based Algorithms and `std::ranges::sort`

`std::ranges::search`

Customized Searchers with `std::search` - Boyer-Moore Algorithms

`std::ranges::find_end`