Module 14 — Exercises¶
Every exercise states its cognitive level, its task, and the observable result that counts as success. Compile with the course's flags, treating a warning as a failure:
Two habits from this module: count operations rather than time them, and print the numbers you are arguing from.
Warm-up [L1 Understand]¶
W1 — Four loops become four algorithms¶
Task. Write these four queries for a std::vector<Loan> as hand-written loops, then replace each
with one standard algorithm, keeping the output identical: the first overdue loan, the number of
overdue loans, the total days overdue, and the titles overdue by more than ten days.
Success looks like. Both versions producing the same four results, and a one-line sentence per
query naming the algorithm and the requirement it put on Loan.
Stuck? Section 1 of Concepts and
examples/module-14/01-algorithms-over-loops/.
W2 — Six operations, two containers each¶
Task. For each operation, name a container you would choose and one you would not, with the reason: look up a member by id; print every loan in due-date order; insert a new loan in the middle of a short list twice a day; find the next ten items due; keep a set of unique titles; store a list that is almost always iterated from front to back.
Success looks like. Twelve answers, each naming the operation's complexity in the chosen container and saying which operation the rejected container would have made expensive.
Stuck? Sections 3 and 4 of Concepts.
W3 — A predicate that captures, twice¶
Task. Write a predicate lambda that keeps loans overdue by more than days days, capturing
days by value. Print the count. Then change days and print the count again. Now write the same
predicate capturing by reference, and do both prints again. Finally: store one of them in a
std::function and call it after the surrounding block has ended.
Success looks like. Four counts that match your prediction, and a sentence saying which of the two predicates is safe to store — and why the other one is not.
Stuck? Section 10 of Concepts.
W4 — Six iterator uses, safe or not¶
Task. Say whether each of these is safe, and give the rule you applied:
auto it = v.begin(); v.push_back(1); std::cout << *it;auto it = v.begin(); if (v.size() > 3) { std::cout << *it; }auto it = m.begin(); m.insert({42, "x"}); std::cout << it->second;forstd::mapfor (std::size_t i = 0; i < v.size(); ++i) { if (i == 2) v.push_back(99); }auto it = l.begin(); l.push_front(0); std::cout << *it;forstd::listfor (auto it = v.begin(); it != v.end();) { it = (*it == 3) ? v.erase(it) : it + 1; }
Success looks like. Six verdicts with the rule quoted from the table, and — for the unsafe ones — the smallest change that makes them safe.
Stuck? Sections 5 of Concepts and Debugging, Move 3.
Core [L3 Modify → L4 Analyze]¶
C1 — Replace a scan with a lookup, and show the counts¶
Task. This function is correct and quadratic. Rewrite it, and prove the improvement:
int totalFine(const std::vector<Loan>& loans, const std::vector<Member>& members) {
int total = 0;
for (const Loan& loan : loans) {
for (const Member& member : members) {
if (member.id == loan.memberId) { total += member.fineFor(loan); break; }
}
}
return total;
}
Success looks like. Identical totals, plus operation counts at n = 1000 and n = 10000 before
and after, and a sentence interpreting the ratios. The rewritten version must not change the function's
signature or its observable behaviour.
Stuck? examples/module-14/07-nested-loop-to-lookup/, and Debugging, Move 2.
C2 — "Fix this": two loops that remove nothing and one that invalidates¶
Task. Three defects in one short program: a remove_if whose elements are all still present
afterwards, a loop that erases while iterating with an iterator it then increments, and a search that
uses an iterator captured before a push_back. Fix all three with the smallest possible changes.
Success looks like. Correct behaviour, and one sentence per fix naming the rule it satisfies (erase needs remove, erase returns the next iterator, reserve or collect first).
Stuck? Section 9 of Concepts and mistakes M4–M5 of Misconceptions.
C3 — Crashes only with large inputs¶
Task. A program works on 100 items and produces garbage on 100,000. The loop below is the suspect. Explain why the size matters, then fix it two different ways:
std::vector<Item> items = load();
std::size_t index = 0;
for (Item* item = &items[0]; item != &items[items.size() - 1]; ++index) {
if (item->needsRestock()) { items.push_back(restockOrder(*item)); }
item = &items[index + 1];
}
Success looks like. A named cause (the pointers into the buffer, and reallocation), the reason the
small input never reallocated (from the capacity sequence in
Concepts), and two fixes
with different trade-offs — for example reserve first, or collect then append.
Stuck? Debugging, Move 3.
C4 — Two containers, one written justification¶
Task. The catalogue needs: lookup by id (thousands of times per run), iteration in title order
(once, for a report), and insertion of a few items per session. Implement the storage twice — once
with std::map, once with a sorted std::vector plus lower_bound — measure both with an operation
counter, and choose.
Success looks like. Two working implementations behind the same interface, the measured counts for each, and one paragraph that names the dominant operation, gives the complexity of both choices, and states the choice with its cost.
Stuck? Section 4 of Concepts, and
examples/module-14/03-container-choice-measured/.
Challenge [L7 Refactor]¶
X1 — Refactor your own worst query¶
Task. Take the least readable or slowest query in your Lab 13 code. Refactor it into standard algorithms, keep the output byte-for-byte identical, and state the complexity of the result.
Success looks like. The same output from a shorter function, the loops gone, a complexity claim for the new version, and a sentence naming what the old version's complexity was — because a refactor that does not change the complexity is a readability improvement, and saying so honestly is part of the exercise.
Stuck? Sections 1 and 13 of Concepts.
X2 — Improve a working query, and prove it with numbers¶
Task. Choose a query from the lab that is correct and slower than it needs to be. Improve it, and demonstrate the improvement with measurements at two data sizes.
Success looks like. A working improvement, operation counts or timings at both sizes for both versions, a sentence interpreting the ratio, and — this is the part that is marked — an honest note on what the improvement cost (memory, an index to keep up to date, more code, a second container).
Stuck? Debugging, Move 1.
How to check yourself¶
- [ ] Every exercise compiles with
-Wall -Wextra -Werror, with no warnings - [ ] Every measurement is an operation count or a timing at two sizes
- [ ] Every container choice has a written sentence with a complexity in it
- [ ] Every comparator was read back for
comp(a, a) == false - [ ] Every iterator was audited against the "did anything modify it?" question
- [ ] Every stored lambda's captures were audited for lifetime