Module 14 — The STL with OOP¶

After this module you can choose the right standard container on evidence, replace hand-written loops with algorithms, and make your own types work everywhere the standard library expects them.

At a glance¶


Prerequisites	Module 13
Estimated study time	8–10 hours
Lab	Lab 14 — STL-driven queries with a complexity justification
Exercises	Three tiers — warm-up, core, challenge
Cognitive levels	L3 Modify → L7 Refactor — exit level L7 Refactor
Self-assessment	Module quiz

Why this module matters¶

By now you have written, by hand, loops that search, count and sort. Those loops are correct — and unnecessary. The standard template library contains tested, optimised, well-documented versions of nearly all of them, written as generic algorithms over iterator ranges.

Using them well requires two skills this module teaches.

The first is choosing a container on evidence. A std::vector and a std::map are not interchangeable conveniences; they have different costs for insert, lookup and iteration, and the right choice follows from the operations the program actually performs. You will learn to state the complexity of what you use, and to justify the choice in one sentence rather than by habit.

The second is making your own types fit in. That means operator< for ordering (Module 5), a hash or comparison for unordered containers, and being aware of what a container requires of the things it stores — including the noexcept move operations from Module 10 that decide whether reallocation copies or moves your objects.

Lambdas tie it together. A predicate written inline at the point of use is far easier to read than a named function three screens away, and it is the reason modern C++ code looks the way it does.

Learning objectives¶

By the end of this module you will be able to:

Name the main standard containers and state which operations each is good at.
Choose a container for a stated access pattern, and justify the choice in terms of the complexity of the operations used.
Explain the difference in behaviour and worst case between the ordered associative containers (map, set) and the unordered ones (unordered_map, unordered_set).
Use iterators to separate an algorithm from the container it operates on, and explain why that separation is the STL's central design.
Replace hand-written loops with standard algorithms (std::sort, std::find, std::find_if, std::count_if, std::accumulate, std::transform, std::for_each, std::any_of), and say why that is an improvement.
Write lambdas as predicates, comparators and callbacks, and explain each capture mode and its consequences.
Explain what a strict weak ordering is, why std::sort requires one, and what goes wrong when a comparator is not one.
Make a custom type usable in a standard container: supply operator< for ordered containers, or a comparison/hash for unordered ones.
Explain what a container requires of an element type, and how noexcept move operations affect reallocation.
Use auto, range-based for and structured bindings idiomatically without hiding important types.
State the complexity of the operations your own code performs, and correct a design that is accidentally quadratic.
Explain what C++20 ranges improve about using algorithms, without depending on them.

Core concepts¶

Standard Template Library (STL) — containers, iterators and algorithms, the library that made generic programming mainstream.
Container — an object that stores and owns other objects. Sequence (vector, deque, list), associative (map, set) and unordered associative (unordered_map, unordered_set), plus adaptors (stack, queue).
std::vector — contiguous storage; fast to iterate and to append to, with occasional reallocation. The default sequence container.
std::map / std::set — ordered, typically a balanced tree; lookup is logarithmic, and iteration is in sorted order.
std::unordered_map / std::unordered_set — hash-based; average constant-time lookup, worst case linear, and no ordering.
Iterator — an object that refers to an element and can move between elements; the interface that lets one algorithm work with many containers.
Iterator category — input, forward, bidirectional, random access. The algorithm's requirements decide which containers it works with.
Algorithm — a function template operating on an iterator range.
Predicate — a callable returning bool, used to select or count elements.
Comparator — a callable that defines ordering.
Lambda — an inline anonymous function object; [capture](parameters) { body }.
Capture — how a lambda takes in surrounding variables: by value [=], by reference [&], or explicitly [x, &y]. A lambda that outlives the things it captured by reference is a dangling-reference bug.
Functors — class types with operator(); what lambdas are sugar for (Module 5).
Strict weak ordering — the requirement std::sort places on a comparator: irreflexive, asymmetric, transitive, and consistent for equivalent elements.
Complexity — how an operation's cost grows with the number of elements. The vocabulary for justifying container and algorithm choices.
Reallocation — std::vector growing its buffer, which moves (or copies) every element. noexcept moves decide which.
Structured bindings (C++17) — for (const auto& [key, value] : map).
Ranges (C++20) — composable algorithm pipelines. Recognised here, not required.

Module contents¶

Section	What it contains
Introduction (this page)	Overview, prerequisites, objectives, concept inventory
Concepts and explanations	Algorithms over loops and the half-open range; iterator categories; the five container families and what each costs; invalidation; ordered versus unordered; your type as a key; hashing; the erase-remove idiom; lambdas and captures; views; `optional` versus exceptions; measuring
Worked examples	Seven programs — four queries written twice, `remove_if` before and after `erase`, one lookup in four containers with every comparison counted, the buffer moving during growth, a key type whose hash lies, captures and ownership, and a quadratic query measured and fixed
Code examples	`examples/module-14/` — seven programs, each with captured output containing the operation counts it argues from
Misconceptions and mistakes	Ten wrong mental models with the measurement that contradicts each, fourteen symptoms, and five worked mistakes with their real compiler messages
Debugging	Measuring instead of guessing: operation counts at two data sizes, finding the scan inside the loop, and the audits for invalidation, captures and hashes
Exercises	Three tiers — from four loops replaced by algorithms to a query refactored with measurements at two sizes
Lab 14	The catalogue's loops become algorithms, two containers are chosen and justified, and a key type is hashed — with a measurement table as the deliverable
Challenge problems	Build an overdue index, refactor a fifteen-line quadratic query for both readability and complexity, and judge three designs for one lookup
Self-assessment	Ten questions, including a prediction about invalidation and one about a key type that lies
Summary	What must be retained, the terms to be able to define, and the checklist
Further reading	Books and official documentation

What you can do after this module¶

Pick a container for a stated workload and justify it in one sentence with a complexity claim.
Replace a hand-written search or sort with the standard algorithm, and know which requirements the element type must satisfy.
Write a correct comparator, and explain what makes it a strict weak ordering.
Use lambdas for predicates and comparators without creating dangling captures.
Make your own class work in std::map or std::unordered_map.
Find and fix a design that became accidentally quadratic.

Where this is used later¶

Strategy and observer patterns in Module 15 are implemented with standard containers, algorithms and callables.
Iterators and algorithms are used again for persistence and searching in the capstone, Module 16.
Complexity reasoning becomes part of the written design justification in the capstone report.

Common mistakes to watch for¶

Symptom	Cause
A comparator crashes `std::sort`, or the result is unsorted	Not a strict weak ordering — for example `<=` instead of `<`, or a comparator that reports two different elements as equivalent inconsistently
`error: no match for 'operator<'`	Using a type in an ordered container or algorithm without defining an ordering
`error: use of deleted function` on `std::map` with a custom key	The key type has no usable comparison
A dangling reference crash when calling a lambda later	The lambda captured a local by reference and outlived it
`unordered_map` is unexpectedly slow	A poor hash, or many collisions; the worst case is linear
Removing elements from a container while iterating invalidates the iterator	Iterator invalidation rules differ per container; collect the matches first, or use the erase-remove idiom
A program is far slower than expected on large data	An accidental linear scan inside a loop (quadratic overall)
Elements are copied rather than moved during `vector` growth	The move constructor is not `noexcept`, so the container must copy

Skills checklist¶

Levels this module works at: [L3 Modify → L7 Refactor] — see How you will learn.

Tick an item only when the evidence exists:

[ ] I can replace a hand-written loop with a standard algorithm — evidence: at least five loops gone from my lab code, with the output compared before and after
[ ] I can justify a container choice with complexity — evidence: two written justifications, each naming the dominant operation
[ ] I can state the invalidation rules for the containers I use — evidence: a written list, audited against every site that holds an iterator or reference
[ ] I can reproduce and explain an invalidation bug — evidence: the capacity sequence and the reallocation count, with the size dependence explained
[ ] I can make my type usable as a key — evidence: one type in an unordered container, with the hash agreeing with the equality, and a sentence on whether keying by the id was better
[ ] I can write and store a lambda safely — evidence: one captured by value and stored, and the dangling case audited rather than run
[ ] I can choose between optional and an exception — evidence: one of each in the lab, with the distinction stated
[ ] I can show an improvement rather than assert one — evidence: operation counts at two data sizes, before and after, with the ratio interpreted

Continue¶

Previous: Module 13 — Exception Handling · Next: Module 15 — SOLID and Design Patterns · All modules: Modules index