Searching and Counting

Part I · Module 20 · Chapter 20.5 · Searching and Counting

1. find Returns a Position

std::vector<int> v{4, 8, 15, 16, 23, 42};
auto it = std::find(v.begin(), v.end(), 15);
auto no = std::find(v.begin(), v.end(), 99);

find(15)  -> found at index 2, value 15
find(99)  -> absent (it == end())
the end() check is not optional: *no would be UB

std::find returns an iterator, not a boolean and not an index. When the value is absent it returns the range's end(), which is the half-open convention from Chapter 20.1 §4 doing its job: there is always a valid thing to return, and it is always distinguishable from a hit.

So the three idioms are:

bool present = std::find(b, e, x) != e;             // is it there?
auto it = std::find(b, e, x);
if (it != e) use(*it);                              // use it if it is
auto idx = std::find(b, e, x) - b;                  // where is it (random access only)

The != e check is the part that cannot be skipped. Dereferencing the returned iterator without it is undefined behaviour, and for a std::vector it reads the first bytes past the data and usually returns something plausible — the same failure shape as Chapter 20.3 §3.

Note that std::find is a linear scan. On a std::map or std::set it compiles and is O(n) where the member find is O(log n); on an unordered_map it is O(n) where the member is O(1). Chapter 20.2 §12 called this out as the mistake that compiles: a category mismatch is a compile error, an algorithmic mismatch is just slow.

2. find_if and the _if Convention

auto it = std::find_if(v.begin(), v.end(), [](int x){ return x > 20; });
auto n  = std::find_if_not(v.begin(), v.end(), [](int x){ return x < 20; });

first > 20        -> 23 at index 4
first NOT < 20    -> 23 (the same element, stated the other way)

_if means the algorithm takes a predicate instead of a value — Chapter 20.4 §1's convention. find_if_not exists so you can write the positive form of a condition and negate the search rather than writing a negated predicate, which is usually clearer.

A predicate here is anything callable with one element and returning something convertible to bool: a lambda, a function pointer, a function object. Chapter 20.8 covers lambdas properly; for now, note that the predicate should be pure — no side effects, no state — because the number of times an algorithm calls it is generally unspecified.

3. Counting

count(2)                = 3
count_if(even)          = 4

std::count(b, e, x) counts elements equal to x; std::count_if(b, e, p) counts those satisfying p. Both return a signed difference_type, which is worth knowing because comparing it to an unsigned size() is a signed/unsigned comparison and will warn under -Wall.

The common misuse is counting in order to test presence:

if (std::count(b, e, x) > 0)   // scans the WHOLE range
if (std::find(b, e, x) != e)   // stops at the first hit

Both are O(n) worst case, but find stops early and count cannot. Use count when you want the number and find or any_of when you want the answer to a yes/no question.

4. all_of, any_of, none_of — and the Empty Range

any_of(>4)  = 1   all_of(>0) = 1   none_of(>100) = 1
on an EMPTY range: all_of = 1, any_of = 0, none_of = 1

all_of on an empty range is true. That is not a quirk; it is the correct answer to the question being asked. "Every element satisfies P" is a claim about all the elements there are, and when there are none the claim has no counterexample, so it holds. Logicians call it vacuous truth; the standard specifies it; and every implementation agrees.

It is also a real source of bugs, because the natural reading of all_of(begin, end, isValid) is "the data is valid", and on empty input that returns true for data that does not exist. A validation function written as

bool validate(const std::vector<Row>& rows)
{ return std::all_of(rows.begin(), rows.end(), isWellFormed); }

accepts an empty file. If non-emptiness is part of what you mean, say so:

return !rows.empty() && std::all_of(rows.begin(), rows.end(), isWellFormed);

any_of on empty is false and none_of on empty is true, both by the same logic, and both are usually what you want anyway.

5. The Binary-Search Family

Four algorithms, one precondition.

sorted   {4,8,15,16,23,42}: binary_search(23) = 1
lower_bound(16) -> index 3   upper_bound(16) -> index 4
equal_range(16) -> [3,4), 1 match(es)
lower_bound(20) -> 23 (first NOT LESS than 20; 20 is absent)

binary_search(b, e, x) returns a bool. That is all it returns, which is why it is less useful than it looks — if you want the element you need one of the others.

lower_bound(b, e, x) returns an iterator to the first element not less than x. If x is present, that is the first occurrence of x; if not, it is the insertion point that keeps the range sorted. The measured lower_bound(20) -> 23 is the important case: 20 is absent, and the answer is the next value up rather than end(). That is the nearest-key query Chapter 19.5 §7 measured a tree answering and a hash being unable to.

upper_bound(b, e, x) returns an iterator to the first element strictly greater than x.

equal_range(b, e, x) returns both as a pair, so [first, second) is every element equal to x and second - first is how many.

All four are O(log n) in comparisons on a random-access range. On a bidirectional range — a std::set, say — they still work but perform O(n) iterator increments to get to the midpoints, so the member find/lower_bound is the right call there.

To find an element and know you found it, lower_bound plus one check is the idiom:

auto it = std::lower_bound(b, e, x);
bool found = it != e && *it == x;       // lower_bound alone does not tell you

6. The Precondition, Measured

The standard requires the range to be sorted with respect to the same comparator. It does not require the implementation to check, and no implementation does, because checking would be O(n) and defeat the purpose.

Here are the same six values, unsorted, with every one of them present:

unsorted {42,4,23,8,16,15}
is_sorted = 0
binary_search( 4) = false   find( 4) = true    <-- WRONG
binary_search( 8) = false   find( 8) = true    <-- WRONG
binary_search(15) = false   find(15) = true    <-- WRONG
binary_search(16) = false   find(16) = true    <-- WRONG
binary_search(23) = false   find(23) = true    <-- WRONG
binary_search(42) = false   find(42) = true    <-- WRONG
6 of 6 lookups were WRONG. Every value IS present; binary_search
said otherwise for 6 of them, and the program exited 0.

Six of six wrong. Not approximately right, not right for the lucky values — every single lookup reported absent for a value that was in the container, while an ordinary std::find over the same data found all six. The program exited 0 and printed no diagnostic.

This is a different kind of failure from Chapter 20.3's. That one was undefined behaviour that happened to look fine; this one is not undefined behaviour at all. Calling binary_search on unsorted input violates a precondition, so the standard says the result is unspecified — the algorithm is permitted to return anything, and what it returns is whatever its halving logic arrives at. It is a well-defined computation producing a meaningless answer.

Which means no sanitizer will ever catch it, because there is nothing wrong with the memory. The only defence is to establish the precondition.

7. The Guard

assert(std::is_sorted(v.begin(), v.end()));

std::is_sorted is O(n) — one pass comparing each element with its predecessor. That is cheap against the O(n log n) sort it protects and cheap against the O(log n) searches it makes meaningful, and in a debug build it costs nothing in release.

std::is_sorted_until returns an iterator to the first element that breaks the ordering, which is what you want in a diagnostic rather than a boolean:

auto bad = std::is_sorted_until(v.begin(), v.end());
if (bad != v.end())
    std::printf("unsorted at index %ld: %d follows %d\n",
                (long)(bad - v.begin()), *bad, *(bad - 1));

Two structural defences are better than the guard where they apply. If the data is keyed and modified over time, use a std::map or std::set, which cannot be unsorted — Chapter 19.5 §2 measured iteration always coming back in key order. If the data has a build phase and a query phase, sort once at the end of the build and treat the container as immutable afterwards, which is Chapter 19.7 §6's sorted-vector pattern.

And the same precondition applies to the set algorithms — set_union, set_intersection, set_difference, set_symmetric_difference, includes, merge — all of which require both inputs sorted. Chapter 20.10 §6 uses set_difference and sorts both inputs immediately before.

8. Searching Structs by a Member

Real data is rarely a range of integers.

struct Txn { unsigned addr; int latency; const char* kind; };
std::vector<Txn> t{{0x1000,12,"RD"},{0x2000,31,"WR"},{0x3000,8,"RD"},{0x4000,55,"WR"}};

first latency > 30: addr 0x2000 latency 31 kind WR
max_element by latency: addr 0x4000 latency 55
minmax_element: 8 .. 55 in ONE pass
count_if(kind==RD) = 2

std::max_element and std::min_element take a comparator and return an iterator to the extreme element — the element, not the value, which is what you want when you need the rest of the record. std::minmax_element returns both in a single pass, which matters when the range is large or the comparator is expensive: two separate calls do 2n comparisons where one does roughly 1.5n.

Note what the comparator is: [](const Txn& a, const Txn& b){ return a.latency < b.latency; } — a less-than over the field you are ordering by, exactly as Chapter 20.6 §1 requires for sort. max_element with a > comparator returns the minimum, which is a confusing way to write it.

9. Subsequences and Neighbours

search({4,5,6}) -> index 3
adjacent_find -> first repeat at index 1 (value 2)

std::search(h1, h2, n1, n2) finds the first occurrence of one range inside another and returns an iterator to its start, or h2 if absent. It is the substring search generalised to any element type.

std::adjacent_find(b, e) finds the first pair of equal neighbours; with a predicate it finds the first pair satisfying it, which is how you locate the first decrease in a sequence or the first gap in a series of timestamps.

std::mismatch(b1, e1, b2, e2) returns the first position at which two ranges differ, as a pair of iterators — and this is much more useful than std::equal when the answer is "no", because it tells you where. Chapter 20.10 §6 uses it to locate the first divergence between two result sets at index 237.

std::find_first_of finds the first element that appears in a second range, and std::find_end finds the last occurrence of a subsequence.

10. The Searching Table

11. What to Actually Do

• Check != end() before dereferencing what find returned.
• Use find or any_of for presence, count only when you want the number. count cannot stop early.
• Remember all_of on empty is true. Add !empty() && when non-emptiness is part of the requirement.
• Guard every binary search with std::is_sorted in debug builds, or guarantee the order structurally.
• Use lower_bound + *it == x when you need the element, not binary_search, which only returns a bool.
• Use is_sorted_until in the diagnostic, so the message names the offending index.
• Use the member find on associative containers. std::find compiles and is a linear scan.
• Use minmax_element rather than two calls.
• Use mismatch rather than equal when a failure needs to be reported.
• Keep predicates pure. The number of calls is unspecified.
• Sort both inputs immediately before any set algorithm, where the reader can see it.

12. Mistakes Worth Making Once

binary_search on unsorted data. Measured 6 of 6 wrong, exit 0, no diagnostic, and no sanitizer will ever help.

all_of as a validation function. Returns true for the empty file.

Dereferencing find's result without the end() check. Reads past the data and usually returns something plausible.

std::find on a std::map. Compiles, is O(n), and the member is O(log n).

count(x) > 0 to test presence. Scans the whole range where find stops at the first hit.

Expecting lower_bound to tell you whether the value is present. It returns an insertion point; you still need *it == x.

max_element with a > comparator. Returns the minimum, and reads as if it should not.

A predicate with side effects. The call count is unspecified, so a counter inside one measures nothing reliable.

13. Interview Relevance

The frozen curriculum marks this chapter High, and the binary-search precondition is a favourite because it separates people who have read the requirements from people who have used the function.

"What does binary_search require?" A sorted range, with no check performed. The strong answer quotes the consequence: on unsorted data holding every value, all six lookups returned false while find found all six, and the program exited 0.

"What is the difference between find and binary_search?" find is a linear scan with no precondition returning an iterator; binary_search is O(log n), requires sorted input, and returns only a bool. The follow-up is what to use when you need the element — lower_bound plus an equality check.

"What does lower_bound return when the value is absent?" The insertion point — the first element not less than the value. Measured, lower_bound(20) on a range without 20 returned 23.

"What does all_of return for an empty range?" True. Being able to say why — a universal claim with no counterexample — and to name the resulting bug class is a strong answer.

"How would you find all elements equal to a key in a sorted range?" equal_range, which returns both bounds; measured as [3,4) with one match.

"How do you locate where two sequences differ?" std::mismatch, not std::equal, because equal only tells you that they differ.

14. What You Should Be Able to Say Now

• That find returns an iterator and end() means absent, and that the check is mandatory.
• That _if takes a predicate, and that predicates should be pure because the call count is unspecified.
• That all_of on an empty range is true, why, and what bug that creates.
• The four binary-search algorithms, what each returns, and that all four require sorted input.
• That lower_bound returns an insertion point, so presence needs *it == x.
• That 6 of 6 binary searches were wrong on unsorted data containing every value, with exit 0.
• That this is a violated precondition rather than undefined behaviour, so no sanitizer can ever catch it.
• That std::is_sorted is one O(n) pass and is_sorted_until names the offending position.
• That std::find on an associative container is a linear scan where the member is logarithmic.

15. Exercises

Exercise 1 — the precondition. Reproduce §6. Then shuffle the same six values ten different ways and record how many lookups are wrong for each permutation. Find a permutation where binary_search is right about everything.

Exercise 2 — the guard. Add assert(std::is_sorted(...)) and confirm it fires. Then replace it with is_sorted_until and print the offending index and its two values.

Exercise 3 — vacuous truth. Write a validation function with all_of and show it accepting empty input. Fix it, then write the same function with none_of over a negated predicate and state which reads better.

Exercise 4 — find versus count. Time count(x) > 0 against find(x) != end() for a value at the start, the middle and the end of a million-element range. Explain all three results.

Exercise 5 — lower_bound as insertion point. Write a function that inserts into a sorted vector keeping it sorted, using only lower_bound and insert. Then measure how its cost grows with n.

Exercise 6 — the record, not the value. Given a vector of structs, find the one with the highest latency and print its address and kind. Do it with max_element and then with sort, and say why one is O(n) and the other O(n log n).

Exercise 7 — one pass. Instrument a comparator with a counter and compare the call counts of min_element + max_element against minmax_element.

Exercise 8 — mismatch. Given two 10,000-element vectors differing at one position, report the index and both values using mismatch. Then do it with equal and explain what extra work that needs.

16. Summary

• find returns an iterator; end() means absent, and dereferencing without the check is undefined behaviour.
• _if takes a predicate, which should be pure because the number of calls is unspecified.
• Measured: count(2) = 3 and count_if(even) = 4; count cannot stop early, so find or any_of answers presence.
• Measured: all_of on an empty range is TRUE — vacuous truth — so a validation built on it accepts empty input.
• Four binary-search algorithms, one precondition: sorted input, unchecked. binary_search returns only a bool; lower_bound returns the insertion point; upper_bound the first greater; equal_range both.
• Measured: lower_bound(20) on a range without 20 returned 23 — the nearest-key answer.
• Measured on unsorted data containing every value: 6 of 6 binary_search lookups returned false while find returned true for all six. Exit 0, no diagnostic.
• That is a violated precondition, not undefined behaviour, so no sanitizer can ever detect it — the defence is is_sorted, or a container that cannot be unsorted.
• The set algorithms carry the same precondition on both inputs.
• Measured: minmax_element gets both extremes in one pass; mismatch reports where two ranges differ, which equal cannot.

The precondition in §6 was about the data being ordered. Chapter 20.6 is about the thing that establishes and defines that order: the comparator. It covers sort and its partial and stable relatives, the measured size at which std::sort stops preserving the order of equal elements, and the requirement a comparator must satisfy — along with what happens when it does not, which is the one piece of undefined behaviour in this module that every tool on the machine catches loudly, including an assertion that names the cause in plain English.