Module 14 — Lab 14: queries as algorithms, and choices with reasons¶

Levels: [L3 Modify → L7 Refactor] · Extends: Lab 13 · Time: 4–5 hours

The scenario¶

The library system works and survives bad input. It also contains eight hand-written loops, four containers chosen by habit, and one query that has become noticeably slow now that the campus has imported its real holdings rather than the ten-item sample.

Two complaints arrived in the same week. The first is from the IT office: "the report that lists everything due tomorrow takes about a minute". The second is from a colleague who read the code: "I cannot tell what any of these loops is for". They are the same complaint about the same design, and this lab is the answer to both: the loops become algorithms, the containers are chosen from the operations they serve, and every choice is written down with its complexity.

★ The deliverable that is marked first is two measurements: the same query at one data size and at ten times that size, before and after the refactor. A complexity argument without numbers is an opinion, and opinions do not survive review.

What you start from¶

Your Lab 13 program. The loops that need replacing are recognisable by their shape:

// 1. find an item by id
for (std::size_t i = 0; i < items_.size(); ++i) {
    if (items_[i].id == id) { return &items_[i]; }
}

// 2. count the items on loan
std::size_t onLoan = 0;
for (std::size_t i = 0; i < items_.size(); ++i) { if (items_[i].onLoan()) { ++onLoan; } }

// 3. total the fines
int total = 0;
for (std::size_t i = 0; i < loans_.size(); ++i) { total += loans_[i].fine(); }

// 4. collect the titles over the limit, in order
std::vector<std::string> titles;
for (std::size_t i = 0; i < items_.size(); ++i) {
    if (items_[i].overdueDays() > limit) { titles.push_back(items_[i].title); }
}
std::sort(titles.begin(), titles.end());

// 5. remove the returned loans
std::vector<Loan> kept;
for (std::size_t i = 0; i < loans_.size(); ++i) {
    if (!loans_[i].returned) { kept.push_back(loans_[i]); }
}
loans_ = kept;

Each is correct. Each also has its own boundary arithmetic, its own temporary container, and no statement of what it costs.

Requirements¶

At least five of these loops replaced by standard algorithms, with the erase-remove idiom where removal happens, and the output unchanged. (Interacts with Module 5: find, count_if and sort need the comparison and equality operators you defined there.)
Two different containers used where their properties genuinely differ, each with a written complexity justification naming the dominant operation. (Interacts with Module 4: the container must not leak into the interface — callers see queries, not the storage.)
Book or Loan usable as a key in an unordered container: operator== and a hash that agrees with it, with the agreement stated in a comment. Then, in one paragraph, answer whether keying by the id instead would have been the better design, and why.
One query returning std::optional where absence is expected, and one operation that throws where it is a failure. (Interacts with Module 13: these are different answers to different problems, and the lab requires both.)
No iterator invalidation anywhere: a written list of the containers you use, their invalidation rules, and the audit of each site that holds an iterator or reference across a possible modification.
Measurements at two data sizes, before and after the refactor, with a sentence interpreting them. Operation counts are preferred to timings; if you time something, say what else the machine was doing and run it more than once.
A written container-choice table: one row per container, the operations performed on it, and the complexity of each.
It builds with no warnings using the course's compile command.

What to deliver¶

The refactored program, with the queries expressed as algorithms.
The measurement table: query, size, work before, work after, ratio.
The container-choice table, with the justification sentence for each container.
The invalidation audit and the capture/lifetime audit, even where they found nothing — an audit that was not performed and an audit that passed look identical in the code, and only the written version can be checked.
One paragraph on a choice you reversed after measuring, because the interesting outcome of this lab is the container you were sure about and the numbers disagreed with.

Self-assessment checklist¶

It builds and runs

[ ] Compiles with g++ -std=c++17 -Wall -Wextra -Werror with no warnings
[ ] Every query returns exactly what it returned before the refactor

It is correct

[ ] Empty, single-element and all-matching inputs behave correctly for every query
[ ] Removal actually removes (the erase-remove idiom is applied, and the size changes)
[ ] The hash agrees with the equality for the key type
[ ] No iterator, pointer or reference is used after a modification that could invalidate it

It is designed

[ ] Every container choice has a sentence with the dominant operation and the complexity
[ ] The container is not part of any public interface — callers ask queries, not storage
[ ] std::optional is used for expected absence and an exception for failure, and I can say which is which and why

It is verified

[ ] Operation counts exist for both versions at two data sizes
[ ] The output before and after the refactor is identical, and I compared it rather than assuming
[ ] I can explain the ratio between the two sizes for each query
[ ] Every stored lambda's captures were audited for lifetime

Common ways this lab goes wrong¶

Symptom	Cause
The refactored query is slower	The algorithm was replaced but the container was not — a scan inside a loop is still quadratic however it is spelled
The removal removes nothing	`remove_if` without `erase`; the size is the tell
A crash that appears only with the professor's data	A pointer or iterator held across a `push_back`: audited in testing, not in code
The report is still slow	An `unordered_map` used for a query that needs order, so the report sorts on every call
Two equal keys behave as different keys	The hash and `==` disagree; see mistake M2 of Misconceptions
`error: no match for 'operator<'`	A custom key type with no ordering — the `map` cannot place it
The measurements are identical before and after	The counter was measuring the wrong thing, or the "before" version was already using the container you moved to
Only one data size was measured	Then nothing has been shown: the ratio is the evidence

Reference solution¶

No solution file is published for this lab. It is a set of queries rewritten as standard algorithms, and the decisions are the work: which algorithm expresses the query, which container the access pattern justifies, and what you measured rather than assumed.

The model code is in examples/module-14/, one program per idea, each already walked through on the concepts page where it is used:

Program	What it models
`01-algorithms-over-loops`	Four queries written as hand-written loops, then as algorithms
`02-erase-remove-and-lookup-outcomes`	Two things the standard library does not do the way the name suggests
`03-container-choice-measured`	The same lookups against four containers, with the numbers
`04-iterator-invalidation`	Invalidation demonstrated in a way that is defined and observable
`05-custom-type-as-key`	What the library demands of a type used as a key
`06-lambdas-captures-and-views`	What a capture captures, and what a view does not own
`07-nested-loop-to-lookup`	The refactor this module's exit level is about

The container-choice table is the part worth comparing against your own, because it is what this lab is really asking for: a choice justified by a measurement.

Continue¶

Previous: Exercises · Next: Challenge problems · Module home: Module 14