Module 14 — Self-Assessment¶

Ten questions. Part A checks vocabulary; Part B checks that you can predict — which, in a module whose bugs are silent, slow or absent, is the only part that tells you whether you can use this material. Answer on paper, then mark yourself and note which section of Concepts each miss points back to.

Target: ≥ 80%, with every miss explained. Below 60%, redo the invalidation and measurement material before Lab 14.

Part A — Recall and comprehension¶

What does std::remove_if actually do, and what must follow it? (Section 9. It moves the elements to keep to the front and returns the position of the new logical end; erase to that position is what actually removes. Without it, the size is unchanged and the "removed" elements are still in the container.)
Why is a hand-written search loop a worse default than std::find_if, when both are correct? (Section 1. The loop carries its own boundary arithmetic — the inclusive/exclusive decision that is edited wrongly — while the algorithm's half-open range is uniform, tested, and named after the requirement.)
When is std::map a better choice than std::unordered_map? (Section 6. When you need ordered iteration or range queries, or when the guaranteed O(log n) matters more than the usually-faster average O(1).)
What must be true of a type used as a key in an unordered container? (Section 7. It needs equality that means what you intend, and a hash where equal values hash equally — plus, for performance, a well-distributed hash.)
What breaks when == and the hash disagree, and why is there no diagnostic? (Section 7 and mistake M2. Equal keys land in different buckets, so the container behaves as if they were different: lookups miss and duplicates accumulate. Every line is individually valid, and the two halves simply disagree, so nothing the compiler knows about is wrong.)
What does a lambda capture by reference store, and when is that safe? (Section 10. A reference; nothing is owned. It is safe only while the captured variable lives — in practice, until the end of the statement that uses the lambda. Capturing by value is what makes a lambda safe to store or return.)
What does a std::string_view own, and what rule follows? (Section 11. Nothing — it is a pointer and a length. The storage it refers to must outlive it, so a function may return one only when it can name the owner in the same sentence.)

Part B — Prediction and explanation¶

Predict what this prints, and whether the answer is meaningful.

#include <iostream>
#include <vector>

int main() {
    std::vector<int> v{1, 2, 3};
    auto it = v.begin();
    for (int i = 0; i < 100; ++i) { v.push_back(i); }
    std::cout << *it << '\n';
}

Answer. Undefined behaviour, and that is the whole answer: push_back grows the vector, the buffer is replaced, and it refers to storage that no longer belongs to the vector. It may print 1 (if the old buffer is still readable and untouched), print something else, or crash. 1 is a plausible result, not a correct one, and a run that prints 1 proves nothing at all — which is why this bug survives testing and code review.

What is knowable is the cause, from section 5: the capacity sequence is 1,2,4,4,8,... and the buffer is replaced every time the capacity grows, so with 103 elements there have been several replacements by the time *it is read.

The fix is one of the three safe patterns: reserve(103) before the loop, collect the additions and append them afterwards, or index with a loop that re-reads size().

Two books have the same id and different editions. An unordered_map<Book, int> is given an equality that compares only the id, and a hash that uses id, title and edition. Predict the map's size after inserting both, and predict whether a lookup by a third Book with the same id is found.

Answer.

size after inserting four books: 4          (three distinct ids)
lookup of #1 Compilers (ed. 9), which is EQUAL to both compilers:
  NOT FOUND

Two entries where the equality says one, and a lookup that misses for a key the container "holds". The mechanism: the two books hash differently, so they are placed in different buckets, and the container never gets as far as comparing them with the equality. Equal keys must hash equally — that is a correctness requirement, not a performance one, and violating it makes the container's behaviour meaningless rather than slow.

The two fixes: make the hash use exactly the fields the equality uses, or decide the id is the identity and compare only the id (and accept that the two editions are one key). The third, usually better, option is to key by the id: std::unordered_map<int, Book> — the identity is then expressed by the key type, where nothing can disagree with it.

A query takes 2 ms on 10,000 records. Predict its behaviour on 100,000 records if it is linear, and if it is quadratic — then say what you would do before optimising.

Answer. Linear: about 20 ms (ten times the data, ten times the work). Quadratic: about 200 ms (ten times the data, a hundred times the work) — and at a million records it is twenty seconds.

What to do first is measure, not optimise. Count the operations at two sizes: if the work grows tenfold, the design is already linear and any remaining cost is a constant factor; if it grows hundredfold, there is a scan inside a loop, and no constant-factor tuning will help. The module's own measurement makes the point:

n = 1000:  500500 comparison(s)
n = 10000: 50005000 comparison(s)
The data grew 10x. The work grew 99x.

Only after that do you touch the code — and the refactor's evidence is again the same two numbers, plus the demonstration that the answers did not change.

Marking yourself¶

Score	What it means
10–8	Move to Module 15. You can choose a container from a workload and prove the choice
7	Re-read sections 5, 7 and 10, then do exercises C1 and C2
6 or below	Redo the invalidation material and the two-size measurement, then Lab 14 in full

For every miss, write the one sentence that would have led you to the right answer. In this module those sentences are short — did anything modify the container?, do == and the hash agree?, does the capture outlive the lambda? — and they are what you will actually use, months from now, when the compiler has nothing to say and the program is quietly wrong.

Continue¶

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