C++ Reference ยท Algorithms
The std::find and std::find_if algorithms
Reference for C++ std::find, find_if and find_if_not: linear search in a range, the returned iterator, the end() check and the ranges versions.
std::find walks a range from front to back and returns an iterator to the first element equal to a given value. If nothing matches, it returns the end iterator you passed in, so you must always compare the result with that end before dereferencing it. std::find_if does the same with a predicate instead of a value, and std::find_if_not finds the first element for which the predicate is false.
All three are linear searches: they work on any input range and need no ordering. For sorted data prefer binary_search and lower_bound, and for keys of a map or set use the container's own find, which is much faster.
auto it = std::find(v.begin(), v.end(), 42); if (it != v.end()) { /* found at it - v.begin() */ }
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
template<class InputIt, class T> InputIt find(InputIt first, InputIt last, const T& value); template<class InputIt, class Pred> InputIt find_if(InputIt first, InputIt last, Pred pred); template<class InputIt, class Pred> InputIt find_if_not(InputIt first, InputIt last, Pred pred);
| Name | Description |
|---|---|
first, last |
The half-open range [first, last) to search. |
value |
Compared with each element using ==. |
pred |
Called with an element; returns something convertible to bool. |
Returns: an iterator to the first match, or last if there is none.
Errors / undefined behavior: dereferencing the returned iterator when it equals last is undefined behavior. The two iterators must belong to the same range, with last reachable from first.
Usage notes
- Always test against
end()before using the result. Forgetting this is the most common bug withfind. - Complexity: at most
last - firstcomparisons or predicate calls, so O(n). The predicate versions stop at the first match. - Index from iterator:
it - v.begin()works for random-access containers; for others usestd::distance. - Prefer member
findonstd::set,std::mapand the unordered containers: it uses the container's structure and runs in O(log n) or O(1) on average. - Strings:
std::string::findalso searches for substrings and returnsnposinstead of an iterator. - C++20 ranges:
std::ranges::find,find_ifandfind_if_nottake a whole range and an optional projection.std::ranges::contains(C++23) answers "is it there?" without an iterator. - Parallel overloads: the legacy algorithms accept an execution policy as the first argument; see execution policies.
- Last occurrence: use
std::find_endor search backwards with reverse iterators (rbegin()).