The one page to keep open: which header, which container, how fast, which algorithm — plus the idioms worth memorizing. Built to be skimmed and printed.
📌 Headers · complexity · selection · algorithms · idioms#include| Header | Gives you |
|---|---|
<vector> <array> <deque> <list> | sequence containers |
<map> <set> | map/multimap, set/multiset (ordered) |
<unordered_map> <unordered_set> | hashed associative containers |
<stack> <queue> | stack; queue & priority_queue |
<string> <string_view> | std::string; non-owning string_view |
<algorithm> | sort, find, transform, count_if, min/max_element, … |
<numeric> | accumulate, reduce, iota, inner_product |
<ranges> | std::ranges::* algorithms & views (C++20) |
<memory> | unique_ptr, shared_ptr, weak_ptr, make_* |
<functional> | std::function, greater/less, bind |
<utility> <tuple> | pair, move, swap; tuple |
<optional> <variant> <any> | vocabulary types (C++17) |
<iostream> <sstream> <fstream> | console, string, and file streams |
<format> <print> | std::format (C++20), std::print (C++23) |
<thread> <mutex> <atomic> <future> | concurrency primitives |
vector — growable, contiguous, O(1) index. Start here.
array<T,N> — compile-time size, no heap.
deque — O(1) push/pop front & back.
unordered_map (default) · map if you need sorted keys.
unordered_set (default) · set if sorted.
stack / queue / priority_queue.
| Container | Access | Insert/Erase | Find by value/key | Ordered? |
|---|---|---|---|---|
vector | O(1) index | O(1) amortized at end · O(n) middle | O(n) | insertion |
array | O(1) index | — (fixed) | O(n) | insertion |
deque | O(1) index | O(1) both ends · O(n) middle | O(n) | insertion |
list | O(n) | O(1) with an iterator | O(n) | insertion |
map / set | — | O(log n) | O(log n) | sorted |
unordered_map / set | — | O(1) avg · O(n) worst | O(1) avg | no |
priority_queue | O(1) top | O(log n) push/pop | — | heap |
Tie-breaker: when two containers fit, prefer the contiguous one (vector) — cache locality usually wins the hidden constant factor.
<algorithm> / <numeric>)| Goal | Call |
|---|---|
| Sort (asc / custom) | sort(b,e) · sort(b,e,cmp) · stable_sort |
| Find first match | find(b,e,x) · find_if(b,e,pred) → iterator or e |
| Count matches | count(b,e,x) · count_if(b,e,pred) |
| Any / all / none match | any_of · all_of · none_of (b,e,pred) |
| Min / max element | min_element(b,e) · max_element(b,e) → iterator |
| Map each element | transform(b,e,out,fn) (out = back_inserter(v)) |
| Sum / product | accumulate(b,e,init[,op]) — init sets the type! |
| Fill 0,1,2,… | iota(b,e,0) |
| Remove matching | v.erase(remove_if(b,e,pred), e) · C++20 erase_if(v,pred) |
| Search a sorted range | binary_search(b,e,x) · lower_bound (O(log n)) |
| Top-K without full sort | nth_element · partial_sort |
C++20 ranges: drop the b,e pair — std::ranges::sort(v), std::ranges::find(v,x), and pipe views with v | std::views::filter(p) | std::views::transform(f).
unique_ptr | shared_ptr | weak_ptr | |
|---|---|---|---|
| Ownership | exactly one | shared (ref-counted) | none (observes) |
| Copyable? | no (move-only) | yes (count++) | yes |
| Overhead | none (= raw ptr) | control block + atomic count | references control block |
| Make with | make_unique<T>() | make_shared<T>() | from a shared_ptr |
| Use it for | the default owner | genuinely shared | break cycles; lock() to use |
Rule: prefer unique_ptr; shared_ptr only when ownership is truly shared; never naked new/delete. A non-owning parameter is just a raw T*/T&.
// iterate (read-only, no copies) for (const auto& x : v) { ... } // iterate a map / unpack a pair or tuple for (const auto& [key, val] : m) { ... } // count word frequencies (operator[] auto-inserts 0) std::unordered_map<std::string,int> f; for (auto& w : words) ++f[w]; // existence check WITHOUT inserting if (m.contains(k)) { ... } // C++20 if (m.find(k) != m.end()) { ... } // any standard // reserve before a known-size fill (avoids reallocations) v.reserve(n); // min-heap priority_queue std::priority_queue<int, std::vector<int>, std::greater<>> pq; // sort descending / by field std::sort(v.begin(), v.end(), [](auto& a, auto& b){ return a > b; }); // "maybe a value" return std::optional<int> r = parse(s); int n = r.value_or(0); // split a line into ints std::istringstream iss(line); int a,b,c; iss >> a >> b >> c; // own heap memory safely auto w = std::make_unique<Widget>(); // protect shared data { std::scoped_lock lk(m); /* critical section */ } // run in parallel, collect result auto fut = std::async(std::launch::async, work); auto result = fut.get();
Pair it with the glossary for definitions, and run any snippet on godbolt.org. Ask your teacher to expand any row into a worked example.