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.
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
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.
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
// 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::searchandstd::find_endwith an empty pattern returnfirstandlastrespectively (the standard definessearchto returnfirst, andfind_endto returnlast). Check for an empty pattern if that matters. - Complexity.
searchdoes at most(last - first) * (sLast - sFirst)comparisons, though real inputs are usually much faster.search_nandadjacent_findare 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
searchthe predicate is called asp(textElement, patternElement). Foradjacent_findit is called asp(*it, *(it + 1)). adjacent_findis a building block. With the default==it finds duplicates in a sorted range, withstd::greater<>it finds the first descent, andadjacent_find(...) == lastwithstd::greater_equal<>is a strictly-increasing check. For "is it sorted?" usestd::is_sorted.- Strings. For substrings of a
std::string,str.find(sub)is usually clearer. Usestd::searchfor 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 isstd::find_first_of. std::ranges::containsandcontains_subrange(C++23) return a plainbool, which reads better than comparing an iterator toend().- Invalidated by edits. Like every iterator, a returned iterator is invalidated by operations that reallocate or erase, so use it before changing the container.