The STL Cheatsheet¶

The standard library is where a beginner's loop goes to be replaced by something correct, tested and faster. This sheet is the container choice table, the algorithms you actually use, and the two traps that bite hardest: comparators and iterator invalidation.

Pairs with Module 14 — The STL with OOP

Choosing a container¶

Container	Lookup	Insert/erase	Order	Use when
`std::vector<T>`	O(1) by index, O(n) by value	O(1) at the end amortised; O(n) elsewhere	Insertion	The default. Almost everything
`std::deque<T>`	O(1) by index	O(1) at both ends	Insertion	You push and pop at both ends
`std::list<T>`	O(n)	O(1) with an iterator	Insertion	You hold iterators and splice often — rare
`std::map<K,V>` / `std::set<T>`	O(log n)	O(log n)	Sorted by key	Ordered iteration, ranges, `lower_bound`
`std::unordered_map<K,V>` / `unordered_set<T>`	O(1) average, O(n) worst	O(1) average	None	Fast lookup, order irrelevant
`std::array<T,N>`	O(1)	Fixed size	—	A fixed-size buffer with no allocation
`std::string`	like `vector<char>`	—	—	Text

Say why, out loud. "I used std::map because the report must be printed in key order" is a design statement. "I used a map" is a habit.

The algorithms worth memorising¶

#include <algorithm>
#include <numeric>

std::sort(v.begin(), v.end());                                   // needs operator< or a comparator
std::sort(v.begin(), v.end(), [](const T& a, const T& b) { return a.cost() > b.cost(); });
std::find_if(v.begin(), v.end(), [id](const T& t) { return t.id() == id; });
std::count_if(v.begin(), v.end(), [](const T& t) { return t.active(); });
std::any_of(v.begin(), v.end(), pred);     std::all_of(...);     std::none_of(...);
std::min_element(...); std::max_element(...);
std::accumulate(v.begin(), v.end(), 0);                          // <numeric>
std::transform(v.begin(), v.end(), out.begin(), [](const T& t) { return t.name(); });
std::remove_if(v.begin(), v.end(), pred);                        // see erase-remove below
std::unique(v.begin(), v.end());                                 // only after sorting!
std::set_intersection(a.begin(), a.end(), b.begin(), b.end(), std::back_inserter(out));

Erasing by predicate needs two steps in C++17 — std::erase_if is C++20 and not available here:

v.erase(std::remove_if(v.begin(), v.end(), pred), v.end());      // erase-remove idiom

Lambdas, in one table¶

Capture	Meaning
`[]`	Nothing — no access to surrounding variables
`[x]`	`x` by value (a copy, fixed at creation)
`[&x]`	`x` by reference — must outlive the lambda's use
`[=]` / `[&]`	Everything by value / by reference. Prefer naming what you use
`[this]`	The enclosing object's members. The lambda outliving the object is a dangling bug

auto byCheapest = [](const Item& a, const Item& b) { return a.price() < b.price(); };
std::sort(items.begin(), items.end(), byCheapest);

A comparator must be a strict weak ordering: comp(a, a) must be false for every a, and the relation must be transitive. A comparator using <= violates the first and makes std::sort read out of bounds — a crash with no relation to the comparator's apparent meaning.

Ordered containers, the operations that earn them¶

std::map<std::string, int> counts;
counts["ada"] += 1;                                  // inserts if absent — see the warning
if (auto it = counts.find("ada"); it != counts.end()) { use(it->second); }   // C++17 if-init

auto lo = counts.lower_bound("b");                   // first key >= "b"
auto hi = counts.upper_bound("d");                   // first key >  "d"
for (auto it = lo; it != hi; ++it) { use(it->first, it->second); }

operator[] inserts. A query written with [] mutates the container — the classic bug in a "count the words" program, where asking for a missing key silently adds it. Use find or at.

Iterating a map:

for (const auto& [key, value] : counts) { std::cout << key << ' ' << value << '\n'; }  // C++17

Iterator invalidation — memorise this column¶

Action	Invalidates
`vector::push_back` that grows the buffer	Everything into that vector, including pointers and references
`vector::insert`/`erase`	Everything at or after the point of change
`map`/`set`/`unordered_*` insert	Nothing (iterators stay valid)
`map`/`set` erase	Only the erased element
`unordered_map` rehash (on insert)	All iterators; references and pointers to elements survive

items.reserve(n);            // stops the growth-invalidation if n is known in advance

A reference or pointer to a vector element that survives a push_back is not safe, and the symptom is a wrong value or a crash far from the cause.

Two more rules¶

std::vector<bool> is not a vector of bool. It is a bitset with proxy references, so auto b = vb[0] gives a proxy rather than a bool. Use std::deque<bool> or std::vector<char> when you need a real container of booleans.

Prefer values in containers, ownership in smart pointers when polymorphic. A std::vector<std::unique_ptr<Base>> is the polymorphic container; a std::vector<Base> silently slices. See Polymorphism.

Complexity, for the choices you actually make¶

Operation	`vector`	`map`	`unordered_map`
Access by index	O(1)	—	—
Find by key	O(n)	O(log n)	O(1) average
Insert	O(1) amortised at the end	O(log n)	O(1) average
Erase	O(n)	O(log n)	O(1) average
Sorted iteration	O(n log n) to sort first	O(n)	O(n log n) to sort first

State the complexity of your hot path in a comment or your design note. It is one of the cheapest marks in the course and one of the most commonly skipped.

Checklist¶

[ ] Is every container choice justified against one alternative?
[ ] Are lookups done with find/at, not operator[] in a query?
[ ] Is every comparator a strict weak ordering (no <=)?
[ ] Are iterators kept across a push_back? (If yes: why?)
[ ] Are the algorithms doing the work that a hand-written loop would do?
[ ] Is std::vector the default, and is there a measured reason it was not used?