Module 14 — Worked Examples¶
Seven programs in examples/module-14/, each folder with its own expected-output.txt. Build any of
them with the course's command:
These programs are unusual in one respect: most of them print numbers. Operation counts, buffer replacements, bucket sizes, sizes before and after. That is deliberate. "The algorithm is faster", "the container is the right choice", "the hash distributes" are all claims, and this module is where a claim has to arrive with evidence attached — which is also what Lab 14 asks for.
Each section gives you something to predict first.
1. The same four queries, written twice¶
examples/module-14/01-algorithms-over-loops/main.cpp
Predict first: the program runs each query as a hand-written loop and then as a standard algorithm. Which of the two versions makes more comparisons when searching a sorted vector of 1024 elements for one value — and by roughly what factor?
Part A–C build the loop-versus-algorithm comparison and the half-open range; Part D shows the library's binary search; Part E counts:
hand-written scan for 1000: 501 comparison(s), found = yes
std::lower_bound: 10 comparison(s) on 1024 elements, found = yes
What to notice. 501 against 10, and both are correct. The reason is not that library code is
mysterious: lower_bound is licensed to halve the range because its name states the precondition
(sorted). The program says the consequence out loud:
Part B also demonstrates the equivalence of the rewrite rather than asserting it, by printing the same answer from both versions of all three queries — count, total, collect:
overdue loans: 3 (loop) vs 3 (count_if)
days overdue: 49 (loop) vs 49 (accumulate)
over 10 days: Databases (loop) vs Databases (copy + sort)
2. remove_if does not remove, and "not found" is not a failure¶
examples/module-14/02-erase-remove-and-lookup-outcomes/main.cpp
Predict first: five loans are held, two of them returned. std::remove_if is called with a
predicate that keeps the open ones. What is the vector's size() immediately afterwards — and what is
in the last two slots?
before: Compilers, Algorithms(returned), Databases, Networks(returned), Operating Systems [size 5]
after remove_if, before erase: Compilers, Databases, Operating Systems, Networks(returned), [size 5]
remove_if returned a position 3 elements in - the new logical end.
after erase: Compilers, Databases, Operating Systems [size 3]
What to notice. The size is unchanged — remove_if has only iterators and cannot change it — and
the elements it was told to remove are still in the vector, pushed to the back. The middle line above
is the one students never see, and it is exactly why the idiom is two calls:
Part C then puts the two lookup styles side by side, with names that say which is which:
find("Algorithms") -> found, returned = yes
find("Astrophysics") -> nothing matched (no exception, no error code to check by mistake)
require("Astrophysics") threw: no loan for title 'Astrophysics'
And Part D lists which standard operations can fail and how — the list to read before writing a
try block, rather than after wondering what to catch.
3. One lookup, four containers, every comparison counted¶
examples/module-14/03-container-choice-measured/main.cpp
Predict first: a 1000-key lookup runs against a vector (scanned), a sorted vector
(lower_bound), a std::map, and an std::unordered_map. Put the four in order of comparisons, and
say which one uses a hash.
vector + std::find_if: 1000 comparison(s), 0 hash(es), found = yes
sorted vector + lower_bound: 10 comparison(s), 0 hash(es), found = yes
std::map::find: 18 comparison(s), 0 hash(es), found = yes
std::unordered_map::find: 1 comparison(s), 1 hash(es), found = yes
What to notice. The scan paid one comparison per element; the binary search and the tree paid
about a dozen for the same answer; the hash map paid one hash and one comparison — but it had to
have a hash, which is a requirement on the key type that a vector never imposed.
Part E is the counterweight, and it is the part people skip:
with a hash that returns 0 for every key:
comparisons for one lookup of the FIRST key: 632
buckets: 1109, load factor: 0.90
comparisons for one lookup of the LAST key: 1 (it is at the front of the chain)
Same container, same correct results, and one lookup walked hundreds of nodes. The two numbers differ because of insertion order, which is the honest summary of a hash table's worst case: it is amortised constant, and the amortisation is the hash's distribution.
4. What invalidation is, watched without triggering it¶
examples/module-14/04-iterator-invalidation/main.cpp
Predict first: a vector is filled with 17 push_back calls. How many times does its buffer get
replaced — and does reserve(17) change that number?
capacity after each push_back: 1,2,4,4,8,8,8,8,16,16,16,16,16,16,16,16,32
buffer replaced 5 time(s) over 17 insertions, and the SIZE was never larger than 17.
with no reserve: 5 buffer replacement(s)
with reserve(17): 0 buffer replacement(s)
What to notice. The program watches the buffer move by comparing data() — and never
dereferences a stale iterator, because that would be undefined behaviour and a demonstration whose
output is undefined cannot be captured or trusted. Part C shows the three patterns that are safe by
construction and gives the reason for each; Part D is the per-container rule table; Part E is the one
that explains why the bug survives review:
5. Your type as a key, and the disagreement that is silent¶
examples/module-14/05-custom-type-as-key/main.cpp
Predict first: a struct with id, title and edition is offered as a key to an
unordered_map whose equality compares only the id and whose hash uses all three fields. Two books
with the same id, different editions, are inserted. How many keys does the map hold afterwards?
equality compares the id only; the hash uses id + title + edition.
size after inserting four books: 4
lookup of #1 Compilers (ed. 9), which is EQUAL to both compilers:
NOT FOUND
What to notice. The container is not slow, and it is not crashing: it is wrong, in a way no compiler, warning level or sanitizer reports. Equal keys must hash equally, and here they do not, so two "equal" records live in different buckets and are never compared.
Part D is the escape hatch that is usually the better design — std::unordered_map<int, Book>, where
the identity is expressed by the key type and nothing can disagree with it — and Part A/B show what
the ordered container requires instead:
iteration order is sorted, and the map did it without being asked:
#1 Compilers (ed. 2) -> 1 copy
#1 Compilers (ed. 3) -> 1 copy
6. Captures, ownership, and views¶
examples/module-14/06-lambdas-captures-and-views/main.cpp
Predict first: a lambda captures an int by value and another captures it by reference. The
variable is changed afterwards. Which lambda's answer changes?
threshold is 3: by value -> 3 item(s) kept, by reference -> 3 item(s) kept
threshold is now 6: by value -> 3 item(s) kept, by reference -> 2 item(s) kept
What to notice. The by-value lambda still uses 3, because it captured a copy; the by-reference one sees 6, because it captured the variable itself. Both are correct — for different intentions — and knowing which you have is the whole skill.
Part C is the one students find surprising, because it is about ownership rather than syntax:
inside the block: use_count = 2, weak expired = no
after the block: weak expired = no
owning() still works: shared catalogue (3 items)
[lifetime] shared catalogue destroyed
A lambda that captures a shared_ptr is an owner: it kept that catalogue alive past the block
that created it, and released it when the std::function was destroyed. Written as
[raw = shared.get()] the same line compiles, owns nothing, and dangles.
Part E prints two snippets that dangle — a stored lambda capturing a local by reference, and a
string_view returned from a function that built a temporary — with the question to answer about
each. It does not run them, and the program says why:
Both are undefined behaviour, so there is no captured output to compare
against - and that is the lesson, not an omission.
7. The query that is quietly quadratic, measured and fixed¶
examples/module-14/07-nested-loop-to-lookup/main.cpp
Predict first: a total is computed for n loans by scanning the member list once per loan. The
data goes from n = 1000 to n = 10000. By what factor does the work grow — and what would a linear
implementation have done?
n = 1000: 500500 comparison(s), total 25000
n = 10000: 50005000 comparison(s), total 250000
The data grew 10x. The work grew 99x.
What to notice. Every part of that code is reasonable: the right operation (find the member), a container that is fine for iteration, a loop that reads well. The cost is the product of two sizes, and nothing in the source says so. After indexing the members once, the same answers arrive with work that grows with the data:
This is the module's exit-level refactor: unchanged behaviour, measured improvement, one sentence of justification. The counts, not a stopwatch, are what make it an argument — they are identical on every machine and every build, so a reader can reproduce them.
Continue¶
Previous: Concepts and explanations · Next: Misconceptions and mistakes · Module home: Module 14