Chapter 16. Templates and the Standard Library

Learning objectives

After this chapter you should be able to:

Do unaided:

Write a function template and a class template, and explain what the compiler instantiates from each.
Read a g++ template error by finding the first error: line and the required from here line in your own file.
Choose among vector, deque, list, map, unordered_map and set for a stated workload, naming the cost and memory layout that decide it.
Predict which iterators, pointers and references a vector or list operation invalidates, and draw a vector before and after reallocation.
Use standard algorithms with lambdas, including std::erase_if, and explain when a std::string_view dangles.

May delegate:

An STL-based module written from your header by a Writer agent, critiqued by a Reviewer agent and tested by a Tester agent in separate sessions, with you settling disagreements with evidence and making the final call.

Opening case

A composite case, not a real student or course.

Sam has one day of station readings and one evening to compute each sensor's mean, minimum and maximum. The humidity sensor (ID 1002) misbehaved during an afternoon storm: many of its readings came back as -99.0 with the VALID bit clear. Sam asks an agent for a function that removes invalid readings from a std::vector<stn::Reading>. The answer arrives in seconds.

The chapter continues from here.

The loop in this chapter

Open a step to see what it asks of you and how it plays out in the Team phase.

PredictWhich readings Listing 16.10 keeps and which build reports it; traversal times and bytes per reading for the three sequence containers at 10⁶, each with a confidence percentage.

Step 1 of 6 · You, no AI

What you hand in: A written prediction: the output, the memory state, the operation count, and how sure you are.

Why this step: A prediction written before the run is the only way to learn whether your model of the machine is right. A miss is the most useful result there is, because it shows exactly where the model is wrong.

The first prediction is never delegated.

Ask yourself: What will this print, what will memory look like when it ends, and how many operations will it take?

Log the prediction in your work log · Predict in every chapter · ← Predict in Chapter 15 · Predict in Chapter 17 →
WriteBy hand: one sensor's running mean, minimum and maximum, and the max_of template.

Step 2 of 6 · You, no AI

What you hand in: One small piece written by hand, to build the mental model.

Why this step: You can only check what you could have built. Writing a small piece yourself gives you the model you will need to judge the agent's version later.

Ask yourself: Could I write this piece again tomorrow without notes?

Browse the companion code · Write in every chapter · ← Write in Chapter 15 · Write in Chapter 17 →
Specifystats.hpp (Listing 16.12): interface, each container with its reason, ownership, cost budget and the edge cases tests must cover.

Step 3 of 6 · You

What you hand in: The header or class interface, unit tests, a complexity budget and the ownership rules.

Why this step: The specification is the contract the code will be held to. Tests written first, a cost budget and ownership rules turn "looks right" into something you can check.

The ownership and lifetime section of a specification is never delegated.

Ask yourself: Who allocates, who frees, what does it cost, and what input would break it?

Prompt and specification templates · Specify in every chapter · ← Specify in Chapter 15 · Specify in Chapter 17 →
DelegateWriter and Tester in separate sessions from the header, then the Reviewer on header and diff; transcripts saved, rounds counted.

Step 4 of 6 · The agent

What you hand in: The implementation from your specification, or an explanation in the Tutor phase, with the prompts and transcript saved.

Why this step: The agent does the typing; you keep the judgment. Saving the prompts and the transcript makes the delegation something you can audit afterward.

Team Team phase: several agent sessions work in separate roles (Writer, Reviewer, Tester). You direct them and make the final call.

Ask yourself: Did I hand over my specification and tests, and did I save what the agent said?

Prompt templates · Delegate in every chapter · ← Delegate in Chapter 15 · Delegate in Chapter 17 →
AuditTests built three ways; each Reviewer finding confirmed or refuted with a tool; each disagreement settled by a timing run; defects, finder and keep-or-rewrite recorded.

Step 5 of 6 · You and the tools

What you hand in: The Audit Report: tests, sanitizer and Valgrind output, your own cost derivation against a timing plot, the defects found, and a keep-or-rewrite decision.

Why this step: What the agent says is testimony until an instrument confirms it. Tests, sanitizers, Valgrind and a timing plot are evidence.

The final judgment that the code is correct is never delegated.

Ask yourself: What did the sanitizer report, does the timing plot match my derivation, and would I keep this code or rewrite it?

The Audit Report template · Audit in every chapter · ← Audit in Chapter 15 · Audit in Chapter 17 →
Defend"Why this container?" and "which iterator is still valid?" for your own code, with Table 16.2 and your timings.

Step 6 of 6 · You, live

What you hand in: A five-minute oral defense.

Why this step: If you can explain it live, you own it. The oral checks that the understanding is yours and not the agent's.

Ask yourself: Why this bound, what input breaks it, and where is this memory freed?

How the loop works · Defend in every chapter · ← Defend in Chapter 15 · Defend in Chapter 17 →

What agents get wrong here

Patterns observed in agent-written code, to test for, not guarantees. If the agent no longer makes the mistake, your job is to prove it got it right, with the same instrument.

Using an iterator, reference or pointer after the container changed

How to catch it -D_GLIBCXX_DEBUG; -D_GLIBCXX_SANITIZE_VECTOR in the ASan build; inputs that erase twice in a row or reallocate

Section 16.3.1 · AddressSanitizer

A string_view that outlives its owner

How to catch it ASan on paths that reach it; name the owner of every view returned, stored or captured

Section 16.3.2 · AddressSanitizer, Your own trace

A container chosen by habit, with no reason or measurement

How to catch it A one-line reason per container in the spec; timing at 10⁴ to 10⁶ at -O2

Section 16.3.3 · Timing and log-log plots

What the chapter covers

16.1 The concept, by hand
- 16.1.1 Function templates and instantiation
- 16.1.2 Class templates
- 16.1.3 Reading template errors
- 16.1.4 Six containers, six memory layouts
- 16.1.5 Iterators
- 16.1.6 Invalidation
- 16.1.7 Algorithms and lambdas
- 16.1.8 std::string_view and lifetimes
16.2 Predict and check
16.3 What agents get wrong here
- 16.3.1 Using an iterator after the container changed
- 16.3.2 The dangling string_view
- 16.3.3 The container nobody questioned
16.4 Working with the agent
- 16.4.1 One round, and a disagreement
16.5 Lab: Per-sensor statistics with containers you chose
16.6 Defend it

Cost thread

This chapter's cost question is the container choice itself, on station data. Table 16.6 is the traversal half of the lab: summing 10⁶ values, and heap bytes per reading measured with mallinfo2 (a glibc call that reports heap use) before and after building each container (same machine and method as Table 16.4).

Summary

A template is a pattern the compiler turns into real functions or classes, one per type used, at compile time; it costs compile time and code size, not run time, and is checked only for the types actually used.
A g++ template error has a fixed shape: the first error: line, the required from here line in your file, and the types in [with ...].
The six containers differ in memory layout, and layout decides cost: the same O(n) traversal of a scattered list was about 100 times slower than of a vector.
Erasing from a vector inside a range-based for loop is undefined behavior. It passed a one-invalid-reading test, was caught by -D_GLIBCXX_DEBUG at the first bad increment and by ASan only with -D_GLIBCXX_SANITIZE_VECTOR; std::erase_if does the job in one O(n) pass.
Algorithms with lambdas make each step short, not right. A std::string_view owns nothing and dangles when its owner dies; g++ 13 did not warn, and ASan caught it at run time.
In the Team phase a Writer, a Reviewer and a Tester work in separate sessions from your header, and you settle their disagreements with measurements.

Key terms

template: a pattern for a function or class with type parameters, from which the compiler generates real code.
function template: a template that generates functions, such as max_of<T>.
class template: a template that generates classes, such as std::vector<T>.
instantiation: the compiler generating a real function or class from a template for specific arguments.
template argument deduction: the compiler working out template parameters from the argument types at a call.
concept: a C++20 named requirement on a template parameter, checked at the call site.
container: a standard class template that owns a collection of elements and manages their memory.
sequence container: a container that keeps insertion order (vector, deque, list).
associative container: a container that arranges elements by key (map, set, unordered_map).
iterator: an object that marks a position in a container and can move to the next.
iterator category: what an iterator can do in constant time (random access, bidirectional, forward).
invalidation: a container operation leaving an iterator, pointer or reference no longer referring to a valid element.
singular iterator: an iterator that refers to no element, such as one invalidated by erase.
debug containers: libstdc++'s checked containers, enabled with -D_GLIBCXX_DEBUG, which stop on use of an invalidated iterator.
container-overflow: an ASan report of access to a vector's unused capacity, enabled with -D_GLIBCXX_SANITIZE_VECTOR.
lambda: an unnamed function written where it is used.
capture list: a lambda's square brackets, naming the locals it copies or refers to.
erase-remove idiom: std::remove_if followed by one erase of the tail; std::erase_if does both in C++20.
std::string_view: a non-owning pointer and length referring to characters owned elsewhere.
small string optimization: storing short strings inside the std::string object rather than on the heap.

Companion code

7 files for this chapter, compiled with the book's flags.

Read the code Download ch16.zip

Connections

Where this chapter and another point to each other most often.

Chapter 8: Growable Arrays and Linked Lists: The Cost of Growth
He asks two questions: "What does the range-based for loop keep between iterations?" and "What does erase do to the readings after the one it removes?" Sam knows the second answer from Chapter 8: they shift one slot left.
Chapter 12: Moving to C++: Is It Really C++?
Chapter 12 introduced std::vector for basic use; here you learn what it costs and when it betrays you.
Chapter 18: Hash Tables, Exceptions, and the Search Study
An unordered_map stores nodes too, reached through buckets chosen by a hash of the key; Chapter 18 builds one.
Chapter 19: Directing a Team of Agents
Chapter 19 develops the full method for dividing work and judging reviews; this section sets up the smallest team that works.

See it on the map

16 Templates and the Standard Library