Module 14 — Summary¶

The essentials¶

The standard library is the default, not the luxury. Containers, iterators and algorithms are already written, tested and documented; a hand-written loop is the exceptional case now.
begin and end are a half-open range — end is one past the last element — and that single convention is why every algorithm loops uniformly and why an empty range needs no special case.
An iterator is a position, and its category is part of the contract. std::sort needs random access, so it refuses a list; the error names the missing operation (operator-) and the fix names the container (list.sort()).
Choose the container from the operations you perform, and write the sentence: lookups dominate and I never need order, so this is an unordered_map — a hash plus one comparison instead of a tree walk. Measured on this toolchain, one 1000-key lookup costs 1000 comparisons by scan, 10 with lower_bound, 18 in a map, and 1 hash plus 1 comparison in an unordered_map.
Complexity is the vocabulary of the justification, and a measured operation count is the evidence. Two data sizes, not one: 10x the data producing 99x the work is a diagnosis, and a single size is not.
Iterator invalidation is per container. vector and string invalidate everything when they grow — five buffer replacements in seventeen push_back calls — while node-based containers invalidate nothing on insertion. The question that catches it: did anything modify this container since I obtained the iterator?
remove_if does not remove. It moves the keepers to the front and returns the new logical end; erase does the removing. Read the idiom as one sentence: collapse, then destroy from there on.
Lambdas capture what the capture list says, and nothing else. The list is the closure's data: [x] owns a copy, [&x] owns a reference, [sp] shares ownership of a shared_ptr (and visibly keeps the object alive), [p] owns only the pointer.
Capture by value when the lambda is stored, returned or called later. A dangling reference capture compiles silently and fails elsewhere.
A string_view owns nothing. It is cheap to pass and dangerous to return: a function may return one only when it can name the owner in the same sentence.
Your type must satisfy the container's requirement: < for ordered containers, == plus an agreeing hash for unordered ones. When == and the hash disagree, the container is not slow — it is wrong, silently: four keys where the equality says three, and a lookup that misses.
std::optional for expected absence, exceptions for failure — the same judgement as Module 13, now applied to the library's own operations (at throws, operator[] does not).
Accidental quadratic behaviour is a combination, not a line. The right operation applied to the wrong structure inside another operation — neither half wrong on its own, which is why every small test passes.

The one-sentence version¶

Hand your data to the standard library, choose the container from the operations you actually perform, and let measurements — not habit — decide which of two correct implementations ships.

Terms you must now be able to define¶

container · sequence container · associative container · unordered container · iterator · iterator category · half-open range · algorithm · predicate · comparator · strict weak ordering · lambda · capture · closure · functor · complexity · amortised · iterator invalidation · erase-remove idiom · hash · bucket · load factor · std::optional · std::string_view · structured binding · accidentally quadratic · operation count

All of them are defined in the glossary under this module.

Before you move on¶

[ ] At least five hand-written loops replaced by algorithms, with the output compared rather than assumed
[ ] Two container choices justified in writing, each with the dominant operation and its complexity
[ ] A custom key type used in an unordered container, with the hash agreeing with the equality
[ ] The invalidation rules written down and audited against my own code
[ ] One std::optional and one throwing operation, with the distinction stated
[ ] Measurements at two data sizes, before and after, with the ratio interpreted
[ ] Every stored lambda's captures audited for lifetime; no returned string_view without a named owner
[ ] Quiz score ≥ 80%, and every miss explained
[ ] At least one challenge problem attempted — including the three-way container judgement
[ ] Skills checklist ticked, with the evidence for each item

Where this goes next¶

Module 15 — SOLID and Design Patterns is implemented with exactly what this module taught: factories that return unique_ptr into containers of interfaces, strategies held as std::function or as polymorphic objects, observers stored in a vector whose iteration rules you now know, and adapters whose conversions are now a projection rather than a loop. Two of the most common pattern bugs in student code are this module's bugs wearing a design pattern's name: an observer list modified during notification, and a strategy whose captured state outlives its scope.

Module 16 — Capstone requires the written complexity justification, the two-size measurement and the container-choice table as part of its design documentation. A capstone that cannot say why its catalogue is a map rather than an unordered_map has not finished the design — and the numbers you produced here are what that section is written from.

Continue¶

Previous: Self-assessment · Next: Module 15 — SOLID and Design Patterns · Module home: Module 14