The <algorithm> header is split into two broad families. The first family contains the non-modifying algorithms: functions that read a range, ask a question about it, or locate something inside it, without changing any element. They form the backbone of "search and check" code in C++: finding a product by id, counting in-stock items, verifying every order has a valid status, comparing two carts for equality. This chapter covers the most useful ones, the iterator return values they share, and the cost model that makes them O(n) but rarely surprising.

What "Non-Modifying" Means

A non-modifying algorithm walks a range and returns a small piece of information about it. The information might be a single iterator (where the match was found), a count, or a boolean. The range itself is read through const-friendly iterators and never written to.

That guarantee matters in two ways. Calling a non-modifying algorithm on a const container compiles without complaint. And the algorithm is safe to call from multiple threads against the same range, as long as nobody else is writing to it.

Most of these algorithms share a common return convention: when they search for something, they return an iterator. If the search succeeds, the iterator points to the match. If it fails, the iterator equals the end() of the range. The caller compares the result against end() to decide which case happened. That convention is consistent across find, find_if, find_if_not, search, adjacent_find, and mismatch.

All of them run in O(n) in the worst case. None of them assume the range is sorted.

std::find: Locating an Element

std::find(first, last, value) walks the range from first toward last and returns an iterator to the first element that compares equal to value. If no element matches, it returns last.

Output:

The usage pattern is: call find, compare the result to end(), branch on the outcome. Skipping that comparison and dereferencing the result reads past the end of the container, which is undefined behaviour.

std::find compares with operator==, so the element type needs to support equality. For built-in types and std::string, that's automatic. For a user-defined type, define operator== (or use find_if with a predicate).

Output:

The Product comparison only looks at id, so the lookup ignores name. That kind of partial-match equality is a design choice. When the match logic is anything more than "exact value", find_if is often a better fit.

std::find is O(n) in the worst case. For a sorted container with random-access iterators, std::binary_search or std::lower_bound is O(log n).

Quick Check: What does this code print?

<details> <summary>Answer</summary>

missing. The value 99 isn't in the vector, so find returns ids.end(). The comparison against end() is how the absent-element case is detected.

</details>

std::find_if and std::find_if_not

std::find(first, last, value) only handles "equal to value." For anything else, the two predicate-based variants take over.

std::find_if(first, last, pred) returns the first element for which pred(element) is true. std::find_if_not(first, last, pred) returns the first element for which pred(element) is false. Both return last when no such element exists.

Output:

The predicate is any callable that takes one argument and returns something convertible to bool. Lambdas are the common choice, but a regular function pointer or a function object works too. When the predicate is named (isInStock, hasZeroStock), the call site reads almost like English.

The choice between find_if and find_if_not is one of readability. Whichever spelling reads more naturally at the call site usually wins. find_if_not(v.begin(), v.end(), isValid) is clearer than wrapping the predicate in a negating lambda.

Counting: std::count and std::count_if

Two algorithms answer "how many?":

std::count(first, last, value) returns how many elements equal value.
std::count_if(first, last, pred) returns how many elements satisfy pred.

Both return a signed integer type (iterator_traits<It>::difference_type, usually std::ptrdiff_t).

Output:

Counting is easy to write with a hand-rolled loop, but the algorithm form is shorter and signals intent: "I am summarising this range, not modifying it." A reader scanning the function knows what to expect from the name alone.

count and count_if are both O(n) and visit every element. There's no early exit (unlike find, which stops at the first match). If only the existence of a match matters, prefer any_of or find_if.

std::all_of, std::any_of, std::none_of

When the question is "do they all? does any? does none?", use one of these three. Each returns a bool and short-circuits on the first answer it can give.

Algorithm	Returns `true` when
`std::all_of(first, last, pred)`	every element satisfies `pred` (vacuously true on empty range)
`std::any_of(first, last, pred)`	at least one element satisfies `pred` (false on empty range)
`std::none_of(first, last, pred)`	no element satisfies `pred` (vacuously true on empty range)

Output:

The empty-range behaviour follows the mathematical quantifier rules. all_of on an empty range returns true, mirroring how "for all" works on the empty set. any_of on an empty range returns false. none_of on an empty range returns true. Code that treats an empty cart as a special case should account for this.

Output:

Short-circuiting matters for performance. any_of stops at the first true. all_of stops at the first false. none_of stops at the first true. On a million-element range where the answer is decidable in the first ten elements, the call returns after ten predicate evaluations.

Quick Check: Which algorithm should validate that every cart item has a non-zero quantity?

A) std::all_of with quantity > 0
B) std::any_of with quantity == 0
C) std::count_if with quantity > 0

<details> <summary>Answer</summary>

A. all_of(quantity > 0) returns true exactly when every item passes the check. Option B (any_of(quantity == 0)) returns true if a zero is found, which is the inverse of what's wanted. Option C produces a count, which then requires comparing it to the size, adding an extra step.

</details>

std::for_each: Side-Effects Without Storage

std::for_each(first, last, fn) calls fn(element) for every element in the range. It's the only algorithm in the non-modifying family whose function may have side effects, like printing or accumulating into a captured variable.

Output:

for_each is non-modifying with respect to the range elements: the function receives a copy or a const reference (depending on how the parameter is declared). It can mutate captured state outside the range, but the range itself isn't changed.

Modern C++ usually prefers a range-based for loop over for_each for side effects. The range-based form reads better:

for_each is useful in two specific cases: when the loop body is already a named function (no need to wrap it in a lambda), and when chaining algorithms together where each step is an algorithm call. For accumulation specifically, use std::accumulate from <numeric>.

std::equal and std::mismatch

std::equal(first1, last1, first2) returns true if the two ranges are element-by-element equal. The first range is bounded by first1 and last1; the second is assumed to be at least as long.

Output:

The three-argument form has a subtle hazard: the second range is assumed to be at least as long as the first. If cartB were shorter, the algorithm would read past its end, which is undefined behaviour. C++14 added a four-argument overload that takes a second last and is safe even when the lengths differ:

The four-argument form returns false immediately if the lengths differ, then does the element comparison. Use this version in any new code.

Output:

std::mismatch(first1, last1, first2) is the diagnostic version. It walks both ranges in parallel and stops at the first position where the elements differ, returning a std::pair of iterators pointing to the two mismatched elements. If the ranges are equal up to the end of the first, the pair contains last1 and the corresponding position in the second range.

Output:

mismatch answers "tell me where they diverge" comparisons. It's useful for test assertions, diff tooling, and validation against expected sequences.

equal and mismatch both accept an optional binary predicate as a last argument, for cases where operator== isn't the right comparison. A common use is comparing floating-point ranges with an epsilon tolerance.

std::search and std::adjacent_find

std::search(first1, last1, first2, last2) looks for the first occurrence of the subsequence [first2, last2) inside [first1, last1). It returns an iterator to the start of the match, or last1 if the subsequence isn't found.

Output:

search is a generalisation of substring search. It works on any range, not just strings. The default implementation is a naive O(n * m) search where n is the haystack size and m is the needle size; for most inputs that's plenty fast. C++17 added std::boyer_moore_searcher and std::boyer_moore_horspool_searcher for cases where a smarter algorithm matters.

std::adjacent_find(first, last) looks for the first pair of adjacent equal elements. It returns an iterator to the first element of the pair, or last if no adjacent duplicates exist.

Output:

The "adjacent" qualifier is important. adjacent_find only spots back-to-back duplicates. For all duplicates regardless of position, sort the range first or build a hash set during a manual pass. adjacent_find also accepts a binary predicate, which makes it useful for "find the first point where the sequence stops being monotone":

Output:

The predicate runs against each adjacent pair (prev, next), and the algorithm stops at the first pair for which it returns true. That's a compact way to phrase "where does this trend break?" without writing the loop by hand.

Comparison with Modifying Algorithms

The non-modifying algorithms answer questions about a range; the modifying ones change it. Both families share the iterator-based interface, but the contracts they offer their callers are different.

Aspect	Non-modifying	Modifying
Writes to range	No	Yes (in-place) or to destination
Works on `const` container	Yes	No (for in-place); destination must be writable
Thread-safe with concurrent readers	Yes	No
Return type	iterator, count, or `bool`	iterator one past last written
Examples	`find`, `count_if`, `all_of`, `equal`	`transform`, `replace`, `remove`, `copy`

The distinction matters when reading code: seeing std::find_if in a function signals the input range is being inspected, not changed. Seeing std::transform signals it's being rewritten. The algorithm name itself documents the intent, as long as the algorithms are used for what their names suggest.

Quick Check: Which of these calls would fail to compile on a const std::vector<int>&?

A) std::find(v.begin(), v.end(), 42)
B) std::count_if(v.begin(), v.end(), pred)
C) std::transform(v.begin(), v.end(), v.begin(), pred)

<details> <summary>Answer</summary>

C. std::transform writes to its destination, and v.begin() on a const vector returns a const_iterator, which doesn't support writing. The non-modifying find (A) and count_if (B) only read, so they compile fine.

</details>

A Practical Validation Routine

The algorithms compose well into validation logic. The function below checks an order summary against a small set of business rules using only non-modifying algorithms.

Output:

Each rule is one algorithm call. The function reads as a list of checks. Compare that against a hand-rolled loop that walks the lines once and tries to handle every rule inside the body. The algorithm version is longer in total lines, but every line says exactly one thing.

Interview Questions

Q1: What does `std::find` return when the value isn't present, and why does it work that way?

It returns the last iterator that was passed in (the end of the range). The convention exists because there's no way to return "nothing" through an iterator type: any iterator value is a position in the range, and last is the one position guaranteed to be reachable without dereferencing anything. The caller compares the result against end() to detect failure, which is the same pattern used by every search-style algorithm in <algorithm>.

Q2: When would you use `std::find_if` instead of `std::find`?

When the match criterion is anything other than "equal to a fixed value." find compares with operator==, which is fine for "find this exact id." find_if takes a predicate, so it handles "find the first in-stock product", "find the first price over $50", or "find the first order whose status is one of these three values." A common refactor is starting with find against a constructed sentinel object, realising the comparison is awkward, and switching to find_if with a clearer predicate.

Q3: What's the difference between `std::all_of` and a manual loop that returns `false` on the first failure?

Behaviourally, none. all_of short-circuits at the first element for which the predicate returns false, just like the manual loop would. The differences are in readability and intent: all_of(begin, end, pred) declares "every element must satisfy this" at the call site, while a loop with if (!pred(x)) return false; makes the reader work out the same intent from the body. The algorithm form also handles the empty-range edge case correctly (returns true) without an explicit check.

Q4: Why does the three-argument form of `std::equal` exist if it's potentially unsafe, and which form should you prefer in new code?

The three-argument form was the original C++98 design and pre-dates the four-argument overload added in C++14. It exists for backward compatibility and for cases where the caller has externally verified that the second range is at least as long as the first. In new code, prefer the four-argument form equal(first1, last1, first2, last2), which handles unequal-length ranges safely by returning false instead of reading past the end of the shorter range.

Q5: How does `std::adjacent_find` differ from a hypothetical `find_duplicate` algorithm?

adjacent_find only finds duplicates that sit next to each other in the range. If the range is {1, 2, 1, 3}, it returns end() because no two adjacent elements are equal. A general "find any duplicate" algorithm would need to track all elements seen so far, which is O(n) extra space or O(n log n) time after sorting. The standard library doesn't provide that algorithm directly; the usual workaround is to sort the range and then call adjacent_find, or to insert each element into a std::unordered_set and look for the first collision.

Exercises

Exercise 1: Given a vector of product ids, write a program that uses std::find to check whether product 318 is in the cart, and print either "in cart" or "not in cart".

Expected Output: