Unit 7.5 · about 4 h
46 / 324Templates, containers and iterator invalidation
Native APIs commonly expose templates and STL types. Reading their contracts is enough to make bounded changes without learning advanced metaprogramming.
- explain
You can now
- Read a function or class template and identify its type arguments and required operations.
- Explain container choice using contiguity, access complexity and iterator stability.
- Determine which handles survive a vector mutation without dereferencing invalid ones.
Covers
- Templates and generic code at reading depth
- Container, iterator and invalidation contracts
Study, in this order
6 steps
- Function TemplatesAlgoMaster C++
Anatomy of a Function Template; Template Argument Deduction; Explicit Template Arguments; Implicit vs Explicit Instantiation
Depth · Stop at reading instantiation syntax. Distinct instantiations are not a guarantee of distinct emitted machine-code bodies.
- Class TemplatesAlgoMaster C++
Declaring a Class Template; Multiple Type Parameters; Member Functions: In-Class vs Out-of-Class; Member Type Aliases; Nested Types and the typename Keyword
Depth · Skip member templates, friend templates and metaprogramming.
- `std::vector`AlgoMaster C++
Memory Layout: Contiguous Storage; Size vs Capacity; Removing Elements; Accessing Elements;
reserve,shrink_to_fit,resize; Iterator Invalidation; Complexity Summary - IteratorsAlgoMaster C++
The Generalised Pointer through
const_iteratorand Read-Only Access; Iterator InvalidationDepth · Skip reverse, insert and stream adapters for this pass.
- Container contractscppreference
Sequence containers; Associative containers; Unordered associative containers; Iterator invalidation table
- Vector invalidationcppreference
Iterator invalidation table, particularly
reserve,push_back,insertanderase
Focus on
- A template describes compile-time generic code. Identify the operations its body needs from
T, and read the first diagnostic referring to your instantiation before the library backtrace. vector<T>is contiguous for ordinaryT, butvector<bool>is a special case.listprovides different stability guarantees; unordered containers can invalidate iterators on rehash while preserving references to elements.reservechanges capacity, not size. Existing elements remain valid afterreserveonly when no reallocation occurs.- Without reallocation,
push_backstill invalidates the old end iterator;eraseinvalidates handles at and after the erased position. Use the iterator returned byeraseto continue traversal.
Reproduce closed-book
-std=c++20 -O0 -g, write template<class T> T twice(T x) { return x + x; }. Check twice(3) == 6 and twice(2.5) == 5.0, and explain why a type without a suitable + cannot instantiate the body. For vector<int>{1,2,3}, erase begin()+1 and check the resulting values {1,3} and that the returned iterator points to 3. Predict the invalidated handles before running. Force reallocation using reserve(capacity()+1), then reacquire all handles without comparing or dereferencing the old ones.Traps
- An iterator is not necessarily a pointer or random-access. Algorithms impose iterator-category requirements.
- Capacity is allocated space, not a range of constructed elements that
operator[]may access. - A sanitizer's silence does not make an invalidated iterator valid. Its address may still lie in allocated memory.
Practice
AlgoMaster Exercise: Iterators Basics
Exercises 1 to 5, ending with Exercise 5: Refresh an Iterator After Vector Insert
Before Exercise 5, write which handles the insert may invalidate per the cppreference table, then reacquire them.
AlgoMaster Exercise: Function Templates
Exercises 1 to 4: one and two type parameters, an explicit return-type argument, and overload choice
For each template, list the operations its body needs from each type argument.
Self-test
-
A vector has spare capacity. Does
push_backpreserve every iterator?No. Existing element iterators survive without reallocation, but the old past-the-end iterator is invalidated. -
After
reserve(100)on an empty vector, can you writev[0]?No. Its size is still zero. Useresizeorinsertan element first. -
Why can a template definition in a
.cppfile produce a link failure for a caller in another translation unit?The caller may need the definition to instantiate its argument types. Put the definition where it is visible or supply the needed explicit instantiation in a linked translation unit. -
Why use
it = v.erase(it)rather than++itafter erasure?The erased iterator is invalid.erasereturns a valid iterator to the following element, or the new end.
Completion criterion
Stop when
You explain twice's type requirements and the vector erasure result, and correctly classify handles after reserve, push_back, insert, erase and unordered-container rehash.
Leads to
- 7.6 Undefined behavior, sanitizers and debugger evidence Recognize invalidated-handle bugs before investigating a crash.
- stage 03 · Algorithms & Data Structures Choose containers from the operations an algorithm requires.
Resources for this unit
- AlgoMaster C++ Use the sections on compilation, pointers and references, memory, RAII and smart pointers, copy and move, STL containers, templates, errors, concurrency and paired exercises. Skip competitive-programming breadth already covered in Algorithms.
- cppreference Consult language lifetime, object model, value categories, memory model, atomics, containers and iterator invalidation while reading or modifying code.
Also in this section
- C++ Core Guidelines Use the Philosophy, Interfaces, Resource management, Expressions, Containers and concurrency rule groups to review ownership and safety decisions in the native component.
- Clang AddressSanitizer and UndefinedBehaviorSanitizer Compile seeded memory defects with AddressSanitizer and UndefinedBehaviorSanitizer, preserve the reports, repair the root cause and keep regression tests.
- pybind11 documentation Follow First steps and NumPy support to expose one small native function with explicit shape, dtype, stride, ownership, GIL and exception behavior.
- CMake tutorial Use the introductory steps for targets, libraries, testing and install rules. Produce one clean debug build and one optimized build without copied one-off commands.
- Algorithmica - AoS and SoA Read the AoS and SoA experiment for a measured case where keeping each record together wins, the counterpart to a single-field scan.
- `ld.so`: dynamic linker/loader Read DESCRIPTION, Dynamic string tokens and
LD_DEBUGto distinguish link-time symbols from runtime shared-library discovery on Linux. - Memory Layout Transformations Read Overview and Topics through AOS Form and SOA Form for field-wise access and locality trade-offs. Skip Intel array-notation syntax and the LIBOR example.
- GDB manual: Backtraces Use section 8.2 for frame numbers,
bt,bt -fulland optimized-out arguments when inspecting a native failure.