Module 14 — Concepts and Explanations¶

The library system works. It has encapsulated types, an interface for items, a repository template, honest ownership and designed failure paths — and it still contains hand-written loops: one to find an item, one to count overdue loans, one to collect the titles above a threshold, one to total the days. Each loop is a small program with its own boundary arithmetic and its own place to fix when the requirement changes.

This page is about replacing them, and about the decision that no algorithm can make for you: which container the data belongs in.

The standard library is not a shortcut. It is a set of tested implementations of things you have been writing by hand, with the requirements stated in their names, and the costs documented. Using it well is a design skill: the container is chosen from the operations you perform, and the choice is defended with complexity, not habit.

Every number quoted here was measured on this toolchain by the programs in examples/module-14/.

1. Do I have to write this find loop again?¶

No. Writing the loop is the exceptional case now.

// before: seven lines, one of which is the inclusive/exclusive boundary
const Item* found = nullptr;
for (std::size_t index = 0; index < items.size(); ++index) {
    if (items[index].id == wanted) { found = &items[index]; break; }
}

// after: one line, and the boundary is the algorithm's problem
const auto found = std::find_if(items.begin(), items.end(),
                                [wanted](const Item& item) { return item.id == wanted; });

The same argument applies to each of the four queries the catalogue performs, and examples/module-14/01-algorithms-over-loops/main.cpp runs both versions side by side so the equivalence is demonstrated rather than asserted.

The reason to prefer the algorithm is not that it is shorter:

	Hand-written loop	Standard algorithm
Boundary arithmetic	yours, every time	the algorithm's, once, tested
Intent visible in the call	no — you read the body	yes — the name states it
Complexity	needs reading the body	documented and guaranteed
Changed requirement	edit the loop	change the algorithm's name

begin and end describe a half-open range: [begin, end) — end is one past the last element. That single convention is why every algorithm loops the same way, and why an empty range needs no special case: it is the case where begin == end.

std::vector<int> shelf{11, 22, 33, 44};

for (std::size_t i = 0; i < shelf.size(); ++i) { /* index */ }
for (int value : shelf)                        { /* range-for */ }
for (auto it = shelf.begin(); it != shelf.end(); ++it) { /* iterator */ }

All three visit the same four elements — and only the third generalises, because an algorithm is handed a begin and an end and knows nothing about the container they came from.

2. What is this iterator thing?¶

An iterator is a position in a range that can be moved. It is not a pointer, though for vector it usually is one underneath; it is a concept — a set of operations — and the algorithm is written against the concept:

   algorithm  (find_if, sort, accumulate)
        │  uses: *it, ++it, it != end, and (for some) it + n, <
        ▼
   iterator range  [begin, end)
        │  provided by
        ▼
   container   (vector, list, map, unordered_map, ...)

That gives four useful categories, and they are the reason an algorithm sometimes refuses to compile:

Category	Provides	Containers
Input / output	`*it`, `++it`	streams, inserters
Forward	as above, multi-pass	`forward_list`, unordered containers
Bidirectional	also `--it`	`list`, `map`, `set`
Random access	also `it + n`, `it[n]`, `<`	`vector`, `deque`, `array`, `string`

std::sort needs random access. That is the whole explanation for this, which is what this compiler actually says about std::sort(values.begin(), values.end()) on a std::list<int>:

error: no match for 'operator-' (operand types are 'std::_List_iterator<int>'
       and 'std::_List_iterator<int>')

Read the trail above it, and it names the real subject:

required from 'void std::sort(_RAIter, _RAIter) [with _RAIter = _List_iterator<int>]'
m14-diag.cpp:6:14:   required from here

The snippet was saved as m14-diag.cpp. The library header names above it are the compiler's own files; the only frame you can change is the one naming yours.

A std::list cannot be sorted by std::sort — its iterators cannot jump, and sort computes a distance with last - first — and the fix is the container's own member, list.sort(), which re-links nodes instead of moving elements. The error is about an operation on iterators, not about sorting: read which iterator category is missing, and the fix usually writes itself.

3. Which container should I use?¶

Five families, and the shape of each follows from what it makes cheap:

Container	Layout	Cheap	Expensive
`vector` / `string`	contiguous array	index, iterate, append at the end	insert/erase in the middle; growth invalidates everything
`deque`	blocks	push/pop at both ends	insert/erase in the middle
`list` / `forward_list`	linked nodes	insert/erase anywhere with a known position; iterators survive insertion	no indexing, poor locality, more memory per element
`map` / `set`	balanced tree	ordered iteration, range queries, logarithmic lookup	heap node per element; logarithmic insert
`unordered_map` / `unordered_set`	hash table	average-constant lookup	no order at all; worst case linear

examples/module-14/03-container-choice-measured/main.cpp performs one lookup against four of these, counting every comparison the key type takes part in:

vector + std::find_if:      1000 comparison(s), 0 hash(es), found = yes
sorted vector + lower_bound:  10 comparison(s), 0 hash(es), found = yes
std::map::find:               18 comparison(s), 0 hash(es), found = yes
std::unordered_map::find:      1 comparison(s), 1 hash(es), found = yes

Four correct answers to the same question, and a factor of a thousand between the slowest and the fastest. Which one is right depends on the mix of operations, not on which is best in isolation:

vector — you iterate a lot, append at the end, and search rarely.
sorted vector — you search a lot by key, the data changes rarely, and you want no per-element overhead. (Sorting once and using lower_bound is often the fastest thing available.)
map — you need sorted iteration or range queries as well as lookup.
unordered_map — lookup dominates and order is irrelevant — and you have a hash that distributes.

A list is rarely the answer in this course. It is the container students reach for when they hear "frequent insertion", and it is usually wrong: the insertion is cheap only when you already have a position, iteration is slower, and every element costs a heap allocation.

4. What does the choice cost?¶

The question to answer, in one sentence you can write next to the declaration:

"Lookups by id dominate and I never need the items in order, so this is an unordered_map: the lookup is a hash plus one comparison instead of a tree walk."

The vocabulary for that sentence:

Operation	`vector`	sorted `vector`	`map`/`set`	`unordered_map`/`set`
Index / access by position	O(1)	O(1)	—	—
Lookup by key	O(n) scan	O(log n)	O(log n)	average O(1), worst O(n)
Insert	amortised O(1) at the end	O(n) (shift)	O(log n)	average O(1)
Erase	O(n)	O(n)	O(log n)	average O(1)
Ordered iteration	O(n) after a sort	O(n)	O(n)	none
Memory per element	smallest	smallest	node overhead	node + table

Two consequences worth stating out loud, because they are what "justify it" means in the lab:

Choosing for one operation can ruin another. A vector that is sorted on every insert makes insertion linear; a map used for the one thing a vector does best (iteration) pays node overhead for nothing.
The default is not a default. std::vector is the right starting point for sequence data, and that is all it is. There is no default container for a keyed lookup — the answer comes from the workload.

5. My program crashed when I added an item inside the loop¶

That is iterator invalidation, and it is the rule that decides container choices more often than performance does:

for (auto it = items.begin(); it != items.end(); ++it) {
    if (it->needsRestock()) {
        items.push_back(...);   // may reallocate: `it` is now dangling
    }
}

The bug is invisible until a reallocation happens, and a reallocation happens only when the capacity is exceeded. That is why it works on the ten-element sample, works in the demo, and fails on the customer's file.

The cause is worth seeing rather than memorising — examples/module-14/04-iterator-invalidation/main.cpp watches the buffer move, without ever dereferencing anything dead:

capacity after each push_back: 1,2,4,4,8,8,8,8,16,16,16,16,16,16,16,16,32
buffer replaced 5 time(s) over 17 insertions, and the SIZE was never larger than 17.
with no reserve:  5 buffer replacement(s)
with reserve(17): 0 buffer replacement(s)

Container	Insertion	Erasure
`vector`, `string`	growth invalidates every pointer, reference and iterator	those at or after the erased element
`deque`	push at either end invalidates iterators; references survive	erase in the middle invalidates all
`list`, `forward_list`, `map`, `set`, `unordered_*`	nothing — nodes do not move	only iterators to the erased element
`unordered_*`	rehash invalidates iterators (references survive)	only the erased element's iterator

Two questions catch almost every case:

Did anything add to or remove from this container between obtaining the iterator and using it?
If it is a vector (or string, or deque), does anything keep a pointer or reference into it across a possible growth?

And three patterns that are safe by construction:

// 1. reserve, when the final size is known: growth cannot happen, so nothing dies
items.reserve(items.size() + additions.size());

// 2. collect first, then apply: the loop has finished before the container changes
std::vector<Item> extras = collectExtras(items);
items.insert(items.end(), extras.begin(), extras.end());

// 3. use what erase RETURNS: never step from an iterator that died
for (auto it = items.begin(); it != items.end();) {
    it = it->withdrawn() ? items.erase(it) : std::next(it);
}

6. Ordered or unordered?¶

map and unordered_map answer the same lookup question and are not interchangeable:

std::map<std::string, int> ordered;               // stays sorted; O(log n) lookup
std::unordered_map<std::string, int> hashed;      // no order;   average O(1) lookup

map when you need order. "All loans due in the next week" is a range query, and a map can answer it by walking a subtree. An unordered_map can only scan everything.
unordered_map when you need speed and nothing else. The measurement in section 3 is the argument: one comparison instead of a tree walk.
map when the worst case matters. A hash table's guarantee is average; with a bad hash it is linear. A tree's O(log n) holds always. For a system with a hard latency requirement, the weaker guarantee that always holds can be worth more than the faster one that usually holds.
Neither when the data is small and changes rarely. A sorted vector beats both on lookup speed and on memory, because there is no node per element and no hashing — and lower_bound on it is the same binary search the tree performs.

7. Can I use my own type as a key?¶

Both containers will accept your type, and each has a requirement:

std::map<Book, int> stock;                                // needs operator<
std::unordered_map<Book, int, BookHash> stock;            // needs operator== and a hash

operator< must be a strict weak ordering: a < a is false for every a; if a < b then !(b < a); and the relation is transitive. Equivalence — !(a < b) && !(b < a) — is what a map treats as "the same key", which is why a comparator that treats two distinct books as equivalent silently loses one of them.

For the unordered container the rule that catches people is not about speed at all:

Objects that compare equal must hash equally.

The failure mode when they do not is not a crash. It is this, from examples/module-14/05-custom-type-as-key/main.cpp:

equality compares the id only; the hash uses id + title + edition.
size after inserting four books: 4          <- but three of them are "equal"
lookup of #1 Compilers (ed. 9), which is EQUAL to both compilers:
  NOT FOUND

Four inserts where the equality says there should be three, and a lookup that misses for a key the container is supposed to hold. No compiler, warning level or sanitizer reports it, because every line is individually valid; the two halves simply disagree. The fixes are to make the hash use exactly the fields the equality uses, or to decide that the extra fields are not part of the identity and say so in the equality.

The third answer is often the right one: if one book per id is the domain rule, then the key is the id.

std::unordered_map<int, Book> byId;      // the identity is in the key type, where nothing can disagree

That choice eliminates the hash entirely, documents the domain rule in the type, and is faster to write. It is only wrong if the domain really does allow two editions of one id to coexist — which is a question for the design, not for the container.

8. What makes a good hash?¶

Three properties, in order of importance:

Deterministic — the same value must hash the same way every time it is called, including across runs (which is why hashing identity or time is a bug).
Consistent with == — equal values hash equally. This is a correctness requirement.
Well distributed — different values should land in different buckets. This is a performance requirement, and the one that turns O(1) into O(n):

with a hash that returns 0 for every key:
  comparisons for one lookup of the FIRST key: 632
  buckets: 1109, load factor: 0.90
  comparisons for one lookup of the LAST key:  1  (it is at the front of the chain)

Correct answers, and one of them walked hundreds of nodes. bucket_count(), bucket(key) and load_factor() are the tools for checking distribution, and composing hashes — seed ^= h(next) + 0x9e3779b9u + (seed << 6) + (seed >> 2) — is the usual way to combine fields, because a plain + makes many distinct records collide.

9. How do I remove elements that match a condition?¶

std::remove_if does not remove. It cannot: it has iterators, and iterators cannot change a container's size. What it does is move the elements to keep to the front and return the position that is the new logical end:

before:            Compilers, Algorithms(returned), Databases, Networks(returned), Operating Systems   [size 5]
after remove_if, before erase: Compilers, Databases, Operating Systems, Networks(returned),   [size 5]
after erase:       Compilers, Databases, Operating Systems   [size 3]

So the idiom is two calls, and the second is the one that does the deleting:

loans.erase(std::remove_if(loans.begin(), loans.end(),
                           [](const Loan& loan) { return loan.returned; }),
            loans.end());

Read it as one sentence: "collapse the keepers to the front, then destroy from there to the end." The removal is stable — the kept elements keep their relative order — which is why the idiom is preferred to a hand-written swap-and-pop.

10. How do I pass behaviour to an algorithm?¶

A lambda is a class with an operator(), written inline (Module 5's functor), and its capture list is that class's data members. Everything surprising follows:

Capture	The closure stores	Consequence
`[x]`	a copy of `x`	the lambda owns its data; safe to store and call later
`[&x]`	a reference to `x`	nothing is owned: safe only while `x` lives
`[p]` where `p` is a pointer	the pointer	owning the pointer is not owning the pointee
`[sp]` where `sp` is a `shared_ptr`	a copy of the smart pointer	the lambda is an owner, and keeps the object alive

threshold is 3:      by value -> 3 kept, by reference -> 3 kept
threshold is now 6:  by value -> 3 kept, by reference -> 2 kept

The by-value lambda still uses 3: it captured a copy at the moment it was defined. That is exactly what makes it safe to store, return, or hand to a thread — and exactly what makes it useless if you meant to track a changing value.

inside the block: use_count = 2, weak expired = no
after the block:  weak expired = no
owning() still works: shared catalogue (3 items)

That is a shared_ptr capture keeping an object alive past the block that created it. The same line written as [raw = shared.get()] compiles identically, owns nothing, and would be a dangling pointer the moment the block ended.

Two rules, and they cover the whole subject:

Capture by value when the lambda outlives the scope, or when you want the value as it was.
Capture by reference only when the lambda is used within the lifetime of what it captures — typically passed straight into an algorithm on the next line.

11. What is `std::string_view` for, and what does it not own?¶

A std::string_view is a pointer and a length: a view of characters owned by somebody else.

void printTitle(std::string_view title);      // no copy, works with string, char*, literal

It owns nothing, which is what makes it cheap and what imposes the one obligation: the storage it points at must outlive it. These two compile and look the same, and only one is correct:

const std::string owned = "catalogue-of-items";
const std::string_view safe = owned;                            // fine: `owned` outlives `safe`

std::string_view dangerous = firstTitle();                      // a view of a destroyed local

The compiler tracks the view's lifetime, not the storage's. So a function that returns a string_view must be able to name the owner in the same sentence; if it cannot, it returns std::string.

12. When is "not found" not a failure?¶

When it is an expected outcome, and then it is a value, not an exception:

std::optional<Loan> find(const std::string& title) const;    // expected absence
const Loan& require(const std::string& title) const;         // failure: throws

find answers "is this here?" — a legitimate no, handled in one line at the call site.
require answers "give me this" — which cannot be satisfied, and whose caller cannot continue.

Both are in the same class, and naming them differently is the design. This is Module 13's judgement applied to the standard library, whose own operations draw the same line: at throws, operator[] does not; find_if returns end, std::stoi throws.

13. Should I optimise this?¶

Not until you have measured, and this module's exit level is about the measurement:

hand-written scan for 1000: 501 comparison(s), found = yes
std::lower_bound:            10 comparison(s) on 1024 elements, found = yes

The instrument here is the operation count, and it is usually better than a stopwatch: it does not depend on the machine, on background load, or on whether the compiler inlined something. A count of comparisons, algorithms performed or bytes copied is a repeatable measurement, and repeatable is what an argument needs.

What to look for, in order:

A scan inside a loop — the quadratic that grew out of a correct linear design. Measure at two data sizes: if the time grows fourfold when the data doubles, it is quadratic, and no constant factor is going to save it.
The wrong container — a list used for iteration, an unordered_map used for ordering, a vector scanned where an index would do.
Copies you did not intend — elements passed by value, std::string parameters that could be string_view, a container returned by value in a loop.
Everything else — and only with a measurement. Guessing which of two correct implementations is faster is how projects get slower.

Checkpoint¶

Answer these before moving on. The section is given for each.

What does std::remove_if actually do, and what must follow it? (section 9)
Why does end being "one past the last element" matter? (section 1)
Name one thing vector is better at than list, and one thing list is better at. (section 3)
Give the one-sentence justification for choosing unordered_map over map. Then give the sentence that would make the opposite choice right. (sections 3 and 6)
A vector is modified between obtaining an iterator and using it. What are you allowed to assume? (section 5 — in the general case, nothing)
What must be true of a type used as a key in an unordered container? (section 7)
What breaks when == and the hash disagree, and why is it silent? (section 7)
What does a lambda capture by reference store, and when is that safe? (section 10)
What does a string_view own, and what rule follows? (section 11)
Name one situation where the standard library is not automatically the faster choice. (section 13)

Next: Worked examples — six programs, each with numbers in it rather than a summary of numbers.