Skip to content
Tutorials Center
My learning

Topics

C++ Reference ยท Algorithms

C++ std::search and std::adjacent_find

Reference for std::search, search_n, find_end and adjacent_find: finding a subsequence, a run of equal values or the first neighboring pair that matches.

std::find looks for one value. When you need to find a whole subsequence (a pattern of several elements in a row), or a run of equal values, or the first place where two neighbors satisfy some condition, the <algorithm> header has four more tools: std::search, std::search_n, std::find_end and std::adjacent_find.

All of them return an iterator. If nothing matches they return the end of the searched range (last), so you always test the result against last before dereferencing it. They work on any forward iterators, so they handle vector, list, string and plain arrays alike.

C++
auto it = std::search(text.begin(), text.end(), pat.begin(), pat.end());
auto run = std::search_n(v.begin(), v.end(), 3, 0);        // three zeros in a row
auto pair = std::adjacent_find(v.begin(), v.end());        // first two equal neighbors
auto lastHit = std::find_end(v.begin(), v.end(), p.begin(), p.end());

Try it

C++ Finding patterns in a sequence

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with std::cin or std::getline), it gets the next line from this box.

C++ adjacent_find and the C++23 ranges versions

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with std::cin or std::getline), it gets the next line from this box.

Syntax

C++
// subsequence
It1 std::search(It1 first, It1 last, It2 sFirst, It2 sLast);
It1 std::search(It1 first, It1 last, It2 sFirst, It2 sLast, BinaryPred p);
It1 std::search(It1 first, It1 last, const Searcher& searcher);        // C++17

// last occurrence of a subsequence
It1 std::find_end(It1 first, It1 last, It2 sFirst, It2 sLast [, BinaryPred p]);

// n equal values in a row
It std::search_n(It first, It last, Size count, const T& value [, BinaryPred p]);

// first adjacent pair
It std::adjacent_find(It first, It last [, BinaryPred p]);

// C++20 / C++23
std::ranges::search(R1&& r, R2&& pattern, Pred = {}, Proj1 = {}, Proj2 = {});
std::ranges::find_end(...);
std::ranges::search_n(R&& r, count, value, Pred = {}, Proj = {});
std::ranges::adjacent_find(R&& r, Pred = {}, Proj = {});
std::ranges::contains_subrange(R1&& r, R2&& pattern, ...);              // C++23
Name Description
first, last The half-open range [first, last) to search in.
sFirst, sLast The range of the pattern to look for.
count, value For search_n: how many consecutive elements, and the value (or the second argument to the predicate).
p A binary predicate. For search and find_end it compares an element with a pattern element; for adjacent_find it receives two neighbors, in order.
searcher A searcher object such as std::boyer_moore_searcher or std::default_searcher (header <functional>).

Returns: an iterator to the start of the first match (find_end: the last match; adjacent_find: the first element of the first matching pair). If there is no match, last is returned. The ranges versions of search and find_end return a subrange (empty and positioned at last when nothing is found).

Errors / undefined behavior: none for valid ranges. The predicate must not modify the elements.

Usage notes

  • Empty pattern. std::search and std::find_end with an empty pattern return first and last respectively (the standard defines search to return first, and find_end to return last). Check for an empty pattern if that matters.
  • Complexity. search does at most (last - first) * (sLast - sFirst) comparisons, though real inputs are usually much faster. search_n and adjacent_find are linear. In C++17 a searcher (std::boyer_moore_searcher, std::boyer_moore_horspool_searcher) can make long texts faster, at the cost of building tables first.
  • Predicate order. For search the predicate is called as p(textElement, patternElement). For adjacent_find it is called as p(*it, *(it + 1)).
  • adjacent_find is a building block. With the default == it finds duplicates in a sorted range, with std::greater<> it finds the first descent, and adjacent_find(...) == last with std::greater_equal<> is a strictly-increasing check. For "is it sorted?" use std::is_sorted.
  • Strings. For substrings of a std::string, str.find(sub) is usually clearer. Use std::search for other containers and when you need a custom comparison such as ignoring case.
  • Searching for one value is a job for std::find; searching for several alternatives is std::find_first_of.
  • std::ranges::contains and contains_subrange (C++23) return a plain bool, which reads better than comparing an iterator to end().
  • Invalidated by edits. Like every iterator, a returned iterator is invalidated by operations that reallocate or erase, so use it before changing the container.