STL Quick Reference

A comprehensive reference of every STL container, algorithm, and idiom you actually use in competitive programming.

Quick Revisit

• Containers, algorithms, iterators, strings, math helpers — table format with complexities and a "Gotchas" block beside each.
• Each container's complexity facts and its contest hazards (custom hashing, iterator invalidation, npos, default insertion) are listed separately on purpose: you scan them in different moments.
• Cross-link: Common Templates, DS Selection Guide, 08-ladder-mixed.

Prerequisites: Arrays and Strings

Contents

• 1. Containers
• 2. Pairs & Tuples
• 3. Algorithms
• 4. Iterators
• 5. String Methods
• 6. Math & Numeric Functions
• 7. Useful C++17/20 Features
• 8. Common Patterns
• 9. Contest Cheat Sheet
• What the Code Won't Teach You
• Self-Test

---

1. Containers

vector<T>

The default container. Use it unless you have a specific reason not to.

Operation	Syntax	Time
Construct with size	vector<int> v(n);	$O(n)$
Construct with value	vector<int> v(n, val);	$O(n)$
2D vector	vector<vector<int>> g(n, vector<int>(m, 0));	$O(nm)$
Push back	v.push_back(x);	Amortized $O(1)$
Emplace back	v.emplace_back(args...);	Amortized $O(1)$
Pop back	v.pop_back();	$O(1)$
Random access	v[i] or v.at(i)	$O(1)$
Size	v.size()	$O(1)$
Empty check	v.empty()	$O(1)$
Resize	v.resize(n);	$O(n)$
Clear	v.clear();	$O(n)$
Insert at position	v.insert(v.begin() + i, x);	$O(n)$
Erase at position	v.erase(v.begin() + i);	$O(n)$
Front / Back	v.front(), v.back()	$O(1)$
Assign	v.assign(n, val);	$O(n)$

Gotchas:

• v.size() returns size_t (unsigned). v.size() - 1 when v is empty wraps to $2^{64}-1$. Cast: (int)v.size() - 1 or use ssize(v).
• v.reserve(n) avoids reallocations if you know the final size.
• Erasing from the middle is $O(n)$. If order doesn't matter, swap with back and pop.

// O(1) unordered erase
swap(v[i], v.back());
v.pop_back();

---

string

A vector<char> with extra string operations.

Operation	Syntax	Time
Concatenate	s += t;	$O(|t|)$
Substring	s.substr(pos, len);	$O(len)$
Find	s.find(t);	$O(|s|\cdot |t|)$
Compare	s == t, s < t	$O(min(|s|,|t|))$
Char access	s[i]	$O(1)$
Convert to int	stoi(s), stoll(s)	$O(|s|)$
Int to string	to_string(x)	$O(\log x)$
Erase range	s.erase(pos, len);	$O(|s|)$
Insert	s.insert(pos, t);	$O(|s|+|t|)$

Gotchas:

• s.substr() creates a copy every time. Avoid in tight loops.
• s.find() returns string::npos (not -1) on failure. Check with if (s.find(t) != string::npos).
• Lexicographic comparison with < works directly.

---

array<T, N>

Fixed-size, stack-allocated. Slightly faster than vector for small, known sizes.

Operation	Syntax	Time
Declare	array<int, 3> a = {1, 2, 3};	$O(N)$
Access	a[i]	$O(1)$
Size	a.size()	$O(1)$
Fill	a.fill(0);	$O(N)$

Gotchas:

• Size must be a compile-time constant.
• Unlike C-arrays, array can be returned from functions and compared with ==, <.
• Useful as map keys: map<array<int,2>, int> replaces map<pair<int,int>, int> for tuples.

---

deque<T>

Double-ended queue. $O(1)$ push/pop at both ends.

Operation	Syntax	Time
Push front	dq.push_front(x);	Amortized $O(1)$
Push back	dq.push_back(x);	Amortized $O(1)$
Pop front	dq.pop_front();	$O(1)$
Pop back	dq.pop_back();	$O(1)$
Random access	dq[i]	$O(1)$

Gotchas:

• Higher constant factor than vector. Use vector if you only need back operations.
• Iterators and references invalidated on push/pop (unlike vector back-only ops).
• Useful for BFS on 0-1 weighted graphs (0-1 BFS).

---

stack<T>

LIFO adapter over deque by default.

Operation	Syntax	Time
Push	st.push(x);	$O(1)$
Pop	st.pop();	$O(1)$
Top	st.top()	$O(1)$
Empty	st.empty()	$O(1)$
Size	st.size()	$O(1)$

Gotchas:

• No iteration, no clear, no random access. Use a vector as a stack if you need any of those (push_back/pop_back/back).
• st.pop() returns void, not the element. Read top() first.

---

queue<T>

FIFO adapter over deque by default.

Operation	Syntax	Time
Push	q.push(x);	$O(1)$
Pop	q.pop();	$O(1)$
Front	q.front()	$O(1)$
Back	q.back()	$O(1)$
Empty	q.empty()	$O(1)$
Size	q.size()	$O(1)$

Gotchas:

• Same as stack: pop() returns void.

---

priority_queue<T>

Max-heap by default. This trips people up constantly.

Operation	Syntax	Time
Push	pq.push(x);	$O(\log n)$
Pop	pq.pop();	$O(\log n)$
Top (max)	pq.top()	$O(1)$
Empty	pq.empty()	$O(1)$
Size	pq.size()	$O(1)$

Min-heap:

priority_queue<int, vector<int>, greater<int>> pq;

With pairs (sorts by first element, then second):

// Dijkstra-style: min-heap on {dist, node}
priority_queue<pair<int,int>, vector<pair<int,int>>, greater<>> pq;
pq.push({0, src});

Min-heap syntax -- memorize this:

priority_queue<int, vector<int>, greater<int>> pq;  // MIN-heap

The default priority_queue<int> is a MAX-heap. Using the default in Dijkstra (which needs the SMALLEST distance first) produces wrong shortest paths. This is a top-5 most common CF bug.

Alternative: Use priority_queue with negated values: pq.push(-dist) and dist = -pq.top(). Simpler to type but less readable.

Gotchas:

• Default is max-heap. For Dijkstra you need greater<> for min-heap.
• No decrease-key. Standard trick: push duplicates and skip stale entries.
• pq.pop() returns void.
• Building from a vector is $O(n)$: priority_queue pq(v.begin(), v.end());

---

set<T> / multiset<T>

Balanced BST (red-black tree). Sorted order, $O(\log n)$ everything.

Operation	Syntax	Time
Insert	s.insert(x);	$O(\log n)$
Erase by value	s.erase(x);	$O(\log n)$
Erase by iterator	s.erase(it);	Amortized $O(1)$
Find	s.find(x)	$O(\log n)$
Count	s.count(x)	$O(\log n+k)$
Lower bound	s.lower_bound(x)	$O(\log n)$
Upper bound	s.upper_bound(x)	$O(\log n)$
Min element	*s.begin()	$O(1)$
Max element	*s.rbegin()	$O(1)$
Size	s.size()	$O(1)$
Contains (C++20)	s.contains(x)	$O(\log n)$

Gotchas:

• multiset::erase(x) removes all copies of x. To erase one copy: s.erase(s.find(x));
• Use member s.lower_bound(x), not std::lower_bound(s.begin(), s.end(), x) -- the free function is $O(n)$ on sets.
• No random access. Can't do s[i]. Use *next(s.begin(), i) in $O(i)$, but that's slow.
• For order-statistics (find k-th element in $O(\log n)$), use the policy-based tree:

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
typedef tree<int, null_type, less<int>, rb_tree_tag,
             tree_order_statistics_node_update> ordered_set;
// os.find_by_order(k) -> iterator to k-th element (0-indexed)
// os.order_of_key(x)  -> number of elements strictly less than x

---

map<K, V>

Sorted associative container. Same red-black tree as set.

Operation	Syntax	Time
Access / Insert	m[key]	$O(\log n)$
Access (safe)	m.at(key)	$O(\log n)$
Insert	m.insert({k, v});	$O(\log n)$
Erase	m.erase(key);	$O(\log n)$
Find	m.find(key)	$O(\log n)$
Contains (C++20)	m.contains(key)	$O(\log n)$
Lower bound	m.lower_bound(key)	$O(\log n)$
Iterate in order	for (auto& [k, v] : m)	$O(n)$

Gotchas:

• m[key] inserts a default value if key doesn't exist. This can silently grow your map and cause TLE/WA. Use m.find(key) or m.count(key) to check existence.
• Iterating a map gives keys in sorted order. This is useful.

---

unordered_map<K, V> / unordered_set<T>

Hash table. $O(1)$ average, $O(n)$ worst case.

Complexity (average):

Operation	Syntax	Average Time
Access / Insert	m[key]	$O(1)$
Find	m.find(key)	$O(1)$
Erase	m.erase(key)	$O(1)$
Count	m.count(key)	$O(1)$
Contains (C++20)	m.contains(key)	$O(1)$
Reserve	m.reserve(n)	$O(n)$

Contest hazards (separate from complexity — read these before committing to unordered_map on Codeforces):

• Hackable. The default hash for integers can be attacked to force $O(n)$ per operation on Codeforces. Use a custom hash:

struct custom_hash {
    static uint64_t splitmix64(uint64_t x) {
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }
    size_t operator()(uint64_t x) const {
        static const uint64_t FIXED_RANDOM =
            chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }
};
unordered_map<int, int, custom_hash> safe_map;

• Cannot hash pair, vector, etc. by default. Use map or write a custom hash.
• No ordering. If you need sorted iteration, use map.
• reserve() and max_load_factor(0.25) reduce rehashing and collisions.

---

bitset<N>

Fixed-size bit array. $N$ must be a compile-time constant. Operations are $O(N/64)$ -- that 64x speedup matters.

Operation	Syntax	Time
Set bit	bs.set(i); or bs[i] = 1;	$O(1)$
Reset bit	bs.reset(i);	$O(1)$
Flip bit	bs.flip(i);	$O(1)$
Test bit	bs.test(i) or bs[i]	$O(1)$
Count set bits	bs.count()	$O(N/64)$
Any / None / All	bs.any(), bs.none(), bs.all()	$O(N/64)$
Bitwise ops	a & b, a | b, a ^ b	$O(N/64)$
Shift	bs << k, bs >> k	$O(N/64)$
To ulong	bs.to_ulong()	$O(1)$
To string	bs.to_string()	$O(N)$

Gotchas:

• Size must be compile-time constant. For dynamic sizes, use vector<bool> (but it lacks bitwise ops) or manual vector<uint64_t> with bit tricks.
• bitset AND/OR/XOR with another bitset of the same size only.
• Useful for DP optimizations: e.g., knapsack subset-sum in $O(N\cdot S/64)$.
• Shift is useful for convolution-like operations on bitmasks.

---

2. Pairs & Tuples

pair<T1, T2>

Operation	Syntax	Time
Construct	pair<int,int> p(1, 2);	$O(1)$
make_pair	auto p = make_pair(1, 2);	$O(1)$
Brace init	pair<int,int> p = {1, 2};	$O(1)$
Access	p.first, p.second	$O(1)$
Structured binding	auto [a, b] = p;	$O(1)$
Compare	p1 < p2 (lexicographic)	$O(1)$

// Pairs compare lexicographically: first by .first, then by .second
pair<int,int> a = {1, 3}, b = {1, 5}, c = {2, 1};
// a < b < c

// Common: store (value, index) and sort
vector<pair<int,int>> vi(n);
for (int i = 0; i < n; i++) vi[i] = {v[i], i};
sort(vi.begin(), vi.end()); // sorted by value, ties broken by index

// Pair as map key / set element -- works out of the box
set<pair<int,int>> s;
s.insert({3, 1});

Gotchas:

• make_pair(1, 2) deduces types. make_pair(1, 2LL) gives pair<int, long long>.
• Pair comparison is lexicographic. To sort by second element, use a custom comparator or store as {second, first}.
• pair<int,int> can be used directly as a graph edge or coordinate.

---

tuple<T...>

Operation	Syntax	Time
Construct	tuple<int,int,int> t(1, 2, 3);	$O(1)$
make_tuple	auto t = make_tuple(1, 2, 3);	$O(1)$
Access	get<0>(t), get<1>(t)	$O(1)$
Structured binding	auto [a, b, c] = t;	$O(1)$
tie	tie(a, b, c) = t;	$O(1)$
Compare	Lexicographic (like pair)	$O(k)$

// tie() for easy multi-variable assignment
int a, b, c;
tie(a, b, c) = make_tuple(10, 20, 30);

// tie() for custom comparison in sort
vector<tuple<int,int,int>> v;
sort(v.begin(), v.end()); // lexicographic by all 3 fields

// Ignore fields with std::ignore
tie(a, ignore, c) = make_tuple(10, 20, 30); // b unchanged

Gotchas:

• get<i>(t) requires a compile-time constant index. No get<variable>(t).
• Prefer pair over tuple for 2 elements -- .first/.second is clearer than get<0>/get<1>.
• Tuples compare lexicographically like pairs but generalized to $k$ elements.
• In CP, prefer struct or array<int,3> over tuple for readability.

---

3. Algorithms

All from <algorithm> or <numeric> (included in <bits/stdc++.h>).

Sorting

Algorithm	Syntax	Time	Stable?
sort	sort(v.begin(), v.end());	$O(n\log n)$	No
stable_sort	stable_sort(v.begin(), v.end());	$O(n\log n)$	Yes
nth_element	nth_element(v.begin(), v.begin()+k, v.end());	$O(n)$ avg	No

// Sort descending
sort(v.begin(), v.end(), greater<int>());

// Sort by custom criterion
sort(v.begin(), v.end(), [](const auto& a, const auto& b) {
    return a.second < b.second; // sort by second element
});

// nth_element: after call, v[k] holds the element that would be at
// position k if sorted. Elements before k are <= v[k], after are >= v[k].
nth_element(v.begin(), v.begin() + k, v.end());

Gotchas:

• sort uses introsort (quicksort + heapsort fallback). Worst case $O(n\log n)$.
• stable_sort uses $O(n)$ extra memory.
• nth_element is $O(n)$ average, $O(n^2)$ worst case. Fine for contests.
• Custom comparator must define strict weak ordering: comp(a, a) must be false. Using <= instead of < causes UB/crash.

---

Binary Search

Algorithm	Syntax	Returns	Time
lower_bound	lower_bound(first, last, val)	Iterator to first $\ge$ val	$O(\log n)$
upper_bound	upper_bound(first, last, val)	Iterator to first $>$ val	$O(\log n)$
binary_search	binary_search(first, last, val)	bool	$O(\log n)$

// Number of elements equal to x in sorted range
int cnt = upper_bound(v.begin(), v.end(), x) - lower_bound(v.begin(), v.end(), x);

// First position where v[i] >= x
int pos = lower_bound(v.begin(), v.end(), x) - v.begin();

// With custom comparator (range must be sorted by same comparator)
lower_bound(v.begin(), v.end(), x, [](int a, int b){ return a < b; });

Gotchas:

• Range must be sorted (by the same comparator you use). Otherwise UB.
• Use s.lower_bound(x) for set/map (member function), not std::lower_bound.
• binary_search only returns bool. Usually useless -- lower_bound gives you the position.

---

Permutations

Algorithm	Syntax	Time
next_permutation	next_permutation(first, last)	$O(n)$
prev_permutation	prev_permutation(first, last)	$O(n)$

// Enumerate all permutations of {1, 2, 3}
vector<int> v = {1, 2, 3};
sort(v.begin(), v.end()); // MUST start sorted for full enumeration
do {
    // process permutation
} while (next_permutation(v.begin(), v.end()));

Gotchas:

• Returns false when it wraps around to the first permutation.
• Sort the range first to get all $n!$ permutations.
• Only feasible for $n\le 8$ or so ($8!=40320$, $10!=3628800$).

---

Sequence Manipulation

Algorithm	Syntax	Time
unique	unique(first, last)	$O(n)$
reverse	reverse(first, last)	$O(n)$
rotate	rotate(first, mid, last)	$O(n)$
fill	fill(first, last, val)	$O(n)$
count	count(first, last, val)	$O(n)$
find	find(first, last, val)	$O(n)$
transform	transform(first, last, out, func)	$O(n)$

// unique: removes consecutive duplicates, returns new logical end
sort(v.begin(), v.end());
v.erase(unique(v.begin(), v.end()), v.end()); // sorted unique

// rotate: moves [mid, last) to front
// {1,2,3,4,5} with mid = begin+2 -> {3,4,5,1,2}
rotate(v.begin(), v.begin() + 2, v.end());

// transform: apply function to each element
transform(v.begin(), v.end(), v.begin(), [](int x){ return x * 2; });

Gotchas:

• unique only removes consecutive duplicates. Sort first for true uniqueness.
• unique returns an iterator to the new end. You must erase the tail.
• find returns end() if not found. Always check.

---

Numeric Algorithms

All from <numeric>.

Algorithm	Syntax	Time
accumulate	accumulate(first, last, init)	$O(n)$
partial_sum	partial_sum(first, last, out)	$O(n)$
iota	iota(first, last, start)	$O(n)$
reduce	reduce(first, last, init)	$O(n)$

// Sum of vector (use 0LL to avoid int overflow!)
long long sum = accumulate(v.begin(), v.end(), 0LL);

// Prefix sum array
vector<int> prefix(n);
partial_sum(v.begin(), v.end(), prefix.begin());
// prefix[i] = v[0] + v[1] + ... + v[i]

// Fill with 0, 1, 2, ..., n-1
vector<int> idx(n);
iota(idx.begin(), idx.end(), 0);

// Sort indices by value (indirect sort)
sort(idx.begin(), idx.end(), [&](int a, int b){
    return v[a] < v[b];
});

Gotchas:

• accumulate(v.begin(), v.end(), 0) -- the 0 is int. If your values sum to $>2^{31}$, use 0LL. This is a classic bug.
• reduce is like accumulate but unordered (for parallelism). In contests, accumulate is more common.

---

Min / Max

Algorithm	Syntax	Time
min_element	min_element(first, last)	$O(n)$
max_element	max_element(first, last)	$O(n)$
minmax_element	minmax_element(first, last)	$O(n)$
min / max	min(a, b), max({a, b, c})	$O(1)$ / $O(k)$
clamp	clamp(v, lo, hi)	$O(1)$

int mx = *max_element(v.begin(), v.end());
auto [lo, hi] = *minmax_element(v.begin(), v.end()); // C++17 structured binding

// clamp: returns value clamped to [lo, hi]
int x = clamp(val, 0, 100); // equivalent to max(0, min(val, 100))

Gotchas:

• min_element / max_element return iterators, not values. Dereference with *.
• min(a, b) requires same type. min(1, 1LL) won't compile -- use min(1LL, 1LL) or min<long long>(1, 1LL).

---

Predicates

Algorithm	Syntax	Time
all_of	all_of(first, last, pred)	$O(n)$
any_of	any_of(first, last, pred)	$O(n)$
none_of	none_of(first, last, pred)	$O(n)$
find_if	find_if(first, last, pred)	$O(n)$
find_if_not	find_if_not(first, last, pred)	$O(n)$
count_if	count_if(first, last, pred)	$O(n)$

// Check if all elements are positive
bool ok = all_of(v.begin(), v.end(), [](int x){ return x > 0; });

// Find first even element
auto it = find_if(v.begin(), v.end(), [](int x){ return x % 2 == 0; });
if (it != v.end()) cout << *it;

// Count elements greater than 10
int cnt = count_if(v.begin(), v.end(), [](int x){ return x > 10; });

---

Remove & Erase

Algorithm	Syntax	Time
remove	remove(first, last, val)	$O(n)$
remove_if	remove_if(first, last, pred)	$O(n)$
remove_copy_if	remove_copy_if(first, last, out, pred)	$O(n)$

// Erase-remove idiom: remove all zeros from vector
v.erase(remove(v.begin(), v.end(), 0), v.end());

// Remove elements matching predicate
v.erase(remove_if(v.begin(), v.end(), [](int x){ return x < 0; }), v.end());

// C++20: simpler syntax
erase(v, 0);                                          // remove all zeros
erase_if(v, [](int x){ return x < 0; });              // remove negatives

Gotchas:

• remove does NOT resize the container. It shifts elements and returns the new logical end. You MUST call erase after.
• C++20 std::erase / std::erase_if (free functions) handle this correctly in one call.

---

Set Operations (on Sorted Ranges)

All require sorted input ranges. Output goes to an output iterator.

Algorithm	What it computes	Time
set_union	$A\cup B$	$O(n+m)$
set_intersection	$A\cap B$	$O(n+m)$
set_difference	$A\setminus B$	$O(n+m)$
set_symmetric_difference	$A\mathrm{△}B$	$O(n+m)$
includes	Is $B\subseteq A$?	$O(n+m)$
merge	Merge two sorted ranges	$O(n+m)$
inplace_merge	Merge two sorted halves in-place	$O(n)$ with buffer

vector<int> a = {1, 2, 3, 5, 8};
vector<int> b = {2, 5, 7, 8, 9};
vector<int> result;

// Union: {1, 2, 3, 5, 7, 8, 9}
set_union(a.begin(), a.end(), b.begin(), b.end(), back_inserter(result));

// Intersection: {2, 5, 8}
result.clear();
set_intersection(a.begin(), a.end(), b.begin(), b.end(), back_inserter(result));

// Difference (in a but not b): {1, 3}
result.clear();
set_difference(a.begin(), a.end(), b.begin(), b.end(), back_inserter(result));

// Check if b is subset of a
bool sub = includes(a.begin(), a.end(), b.begin(), b.end()); // false

Gotchas:

• Both ranges must be sorted. Otherwise UB.
• These work on any sorted range (vectors, arrays), not just std::set.
• Output must have enough space -- use back_inserter(result).
• merge requires output range disjoint from inputs.
• For std::set containers, use the container's member functions instead.

---

Heap Operations

Manual heap control over a range (vector). The STL heap is a max-heap.

Algorithm	Syntax	Time
make_heap	make_heap(first, last)	$O(n)$
push_heap	push_heap(first, last)	$O(\log n)$
pop_heap	pop_heap(first, last)	$O(\log n)$
sort_heap	sort_heap(first, last)	$O(n\log n)$
is_heap	is_heap(first, last)	$O(n)$

vector<int> v = {3, 1, 4, 1, 5, 9};
make_heap(v.begin(), v.end());       // v is now a max-heap: [9, 5, 4, 1, 1, 3]

// Push: add element, then restore heap
v.push_back(7);
push_heap(v.begin(), v.end());       // 7 bubbles up to correct position

// Pop: move max to back, then remove
pop_heap(v.begin(), v.end());        // max (9) moved to v.back()
int top = v.back();                  // top = 9
v.pop_back();                        // remove it

Gotchas:

• push_heap assumes [first, last-1) is already a valid heap, and the new element is at last-1.
• pop_heap moves the max to the back -- it does NOT remove it. You must pop_back().
• Usually priority_queue is simpler. Use raw heap ops when you need direct access to the underlying vector (e.g., for decrease-key simulation).

---

Partition

Algorithm	Syntax	Time
partition	partition(first, last, pred)	$O(n)$
stable_partition	stable_partition(first, last, pred)	$O(n)$
partition_point	partition_point(first, last, pred)	$O(\log n)$
is_partitioned	is_partitioned(first, last, pred)	$O(n)$

// Move all even elements to the front
auto mid = partition(v.begin(), v.end(), [](int x){ return x % 2 == 0; });
// [even elements... | odd elements...]
//                    ^ mid points here

// partition_point: binary search on a partitioned range
// Requires: pred(x) is true for all x before the partition point
auto pp = partition_point(v.begin(), v.end(), [](int x){ return x < 10; });

Gotchas:

• partition does NOT preserve relative order. Use stable_partition if order matters.
• partition_point requires the range to already be partitioned by the predicate. It's essentially lower_bound generalized to predicates.

---

Sort Checks & Copy

Algorithm	Syntax	Time
is_sorted	is_sorted(first, last)	$O(n)$
is_sorted_until	is_sorted_until(first, last)	$O(n)$
copy	copy(first, last, out)	$O(n)$
copy_if	copy_if(first, last, out, pred)	$O(n)$
swap	swap(a, b)	$O(1)$
swap_ranges	swap_ranges(first1, last1, first2)	$O(n)$
equal	equal(first1, last1, first2)	$O(n)$

// Check if sorted
if (is_sorted(v.begin(), v.end())) { /* already sorted */ }

// Copy positive elements to another vector
vector<int> pos;
copy_if(v.begin(), v.end(), back_inserter(pos), [](int x){ return x > 0; });

---

4. Iterators

Iterator Types

Type	Capabilities	Containers
Random Access	+n, -n, [], <	vector, deque, array, string
Bidirectional	++, --	set, map, multiset, list
Forward	++ only	unordered_set, unordered_map

begin / end / rbegin / rend

  begin()                          end()
    |                                |
    v                                v
  +----+----+----+----+----+----+
  | a0 | a1 | a2 | a3 | a4 | a5 |
  +----+----+----+----+----+----+
                                 ^    ^
                                 |    |
                           rbegin()  rend()
                        (reverse)   (reverse)

// Forward iteration
for (auto it = v.begin(); it != v.end(); ++it) { /* *it */ }

// Reverse iteration
for (auto it = v.rbegin(); it != v.rend(); ++it) { /* *it */ }

// Range-for (preferred)
for (auto& x : v) { /* x */ }

// Range-for with index
for (int i = 0; auto& x : v) { /* use i and x */ i++; } // C++20

Iterator Arithmetic

// Random access iterators only
auto it = v.begin() + 5;       // jump to index 5
int dist = it2 - it1;          // distance between iterators
bool cmp = it1 < it2;          // compare positions

// All iterators
advance(it, n);                // move it forward by n (backward if n < 0 for bidir)
auto it2 = next(it);           // next element (doesn't modify it)
auto it3 = next(it, 3);        // 3 elements ahead
auto it4 = prev(it);           // previous element
int d = distance(first, last); // number of steps from first to last

Gotchas:

• std::distance(s.begin(), it) on set is $O(n)$, not $O(1)$.
• advance modifies the iterator in place. next/prev return a new iterator.
• next(v.end()) is UB. Always check bounds.

---

5. String Methods

Beyond the basics in the Containers section. All from std::string.

Method	Syntax	Returns	Time
substr	s.substr(pos, len)	New string	$O(len)$
find	s.find(t, pos)	Index or npos	$O(n\cdot m)$
rfind	s.rfind(t, pos)	Last occurrence	$O(n\cdot m)$
find_first_of	s.find_first_of("aeiou")	First char in set	$O(n\cdot k)$
find_last_of	s.find_last_of("aeiou")	Last char in set	$O(n\cdot k)$
find_first_not_of	s.find_first_not_of(" \t")	First char NOT in set	$O(n\cdot k)$
compare	s.compare(t)	<0, 0, >0	$O(n)$
starts_with	s.starts_with("abc")	bool	$O(k)$ (C++20)
ends_with	s.ends_with("xyz")	bool	$O(k)$ (C++20)
contains	s.contains("abc")	bool	$O(n)$ (C++23)
c_str	s.c_str()	const char*	$O(1)$
stoi / stoll	stoi(s), stoll(s)	int / long long	$O(n)$
to_string	to_string(42)	"42"	$O(\log n)$

// Find all occurrences of substring
string s = "abcabcabc", t = "abc";
size_t pos = 0;
while ((pos = s.find(t, pos)) != string::npos) {
    cout << pos << " "; // 0 3 6
    pos++;
}

// Check if string contains only digits
bool digits = s.find_first_not_of("0123456789") == string::npos;

// Split string by delimiter (no built-in split!)
stringstream ss(line);
string token;
while (getline(ss, token, ',')) {
    tokens.push_back(token);
}

// Character case conversion
for (char& c : s) c = tolower(c); // from <cctype>
for (char& c : s) c = toupper(c);

// Convert char to/from digit
int d = c - '0';     // char '3' -> int 3
char c = d + '0';    // int 3 -> char '3'

Gotchas:

• s.find() returns string::npos (which is (size_t)-1) on failure. Always check != string::npos.
• s.substr(pos, len) creates a copy. In tight loops, use iterators or string_view instead.
• stoi("abc") throws std::invalid_argument. In CP, input is usually valid, so this is fine.
• tolower/toupper from <cctype> take unsigned char. Technically tolower((unsigned char)c) is correct, but tolower(c) works in practice for ASCII.

---

6. Math & Numeric Functions

From <cmath>, <cstdlib>, and <numeric>.

Function	Header	Syntax	Returns	Notes
abs	<cstdlib>	abs(x)	Absolute value	See gotcha below
fabs	<cmath>	fabs(x)	double abs	For floating-point
sqrt	<cmath>	sqrt(x)	$\sqrt{x}$	Returns double
cbrt	<cmath>	cbrt(x)	$\sqrt[3]{x}$	Returns double
pow	<cmath>	pow(base, exp)	$bas{e}^{exp}$	Floating-point!
log	<cmath>	log(x)	$\ln (x)$	Natural log
log2	<cmath>	log2(x)	${\log }_2(x)$	Base-2 log
log10	<cmath>	log10(x)	${\log }_{10}(x)$	Base-10 log
ceil	<cmath>	ceil(x)	$\lceil x\rceil$	Returns double
floor	<cmath>	floor(x)	$\lfloor x\rfloor$	Returns double
round	<cmath>	round(x)	Nearest int	Returns double
gcd	<numeric>	gcd(a, b)	GCD	C++17
lcm	<numeric>	lcm(a, b)	LCM	C++17
__gcd	built-in	__gcd(a, b)	GCD	GCC extension
__lg	built-in	__lg(x)	$\lfloor {\log }_2(x)\rfloor$	GCC, $x>0$

// Integer abs -- the classic gotcha
int a = abs(-5);          // OK, uses <cstdlib>
long long b = abs(-5LL);  // DANGER: may call int version!
long long c = llabs(-5LL); // Safe
long long d = abs((long long)-5); // Also works with <cstdlib>
// Safest: just write your own
// long long myabs(long long x) { return x < 0 ? -x : x; }

// Integer ceiling division (without floating point)
// ceil(a / b) for positive a, b:
long long ceil_div = (a + b - 1) / b;  // classic
long long ceil_div2 = (a - 1) / b + 1; // equivalent, avoids overflow if a+b overflows

// Integer square root (careful with floating-point!)
long long isqrt(long long n) {
    long long r = (long long)sqrt((double)n);
    while (r * r > n) r--;
    while ((r + 1) * (r + 1) <= n) r++;
    return r;
}

// Floor log base 2 (bit trick)
int floorlog2 = __lg(x);        // GCC built-in, x > 0
int floorlog2b = 63 - __builtin_clzll(x);  // equivalent for long long

// pow is floating-point -- DO NOT use for integer exponentiation
// Use your own:
long long power(long long base, long long exp, long long mod) {
    long long result = 1;
    base %= mod;
    while (exp > 0) {
        if (exp & 1) result = result * base % mod;
        base = base * base % mod;
        exp >>= 1;
    }
    return result;
}

Gotchas:

• abs() for long long: <cstdlib> provides abs(long long) in C++11+, but some compilers resolve abs(-5LL) to the int overload. Use llabs() or cast explicitly.
• pow(10, 18) returns a double -- it will lose precision for large integers. Never use pow for integer powers. Write a loop or use binary exponentiation.
• sqrt(n) for large $n$ can be off by 1 due to floating-point. Always verify: check both r*r <= n and (r+1)*(r+1) > n.
• ceil(x) and floor(x) return double. Cast to long long with care.
• __lg(0) is undefined. __builtin_clz(0) is also UB.
• gcd(0, 0) returns 0. lcm(a, b) can overflow -- compute as a / gcd(a, b) * b.

---

7. Useful C++17/20 Features

Structured Bindings (C++17)

// Pairs
auto [a, b] = make_pair(1, 2);

// Maps
for (auto& [key, val] : mp) {
    cout << key << " " << val << "\n";
}

// Tuples
auto [x, y, z] = make_tuple(1, 2, 3);

// With set insert (check if insertion happened)
auto [it, inserted] = s.insert(42);

gcd / lcm (C++17)

#include <numeric>
int g = gcd(12, 8);        // 4
long long l = lcm(12LL, 8LL);  // 24
// lcm can overflow -- use long long or compute as a / gcd(a,b) * b

clamp (C++17)

int x = clamp(val, lo, hi); // = max(lo, min(val, hi))

reduce (C++17)

// Like accumulate, but operation order is unspecified (allows parallelism)
long long s = reduce(v.begin(), v.end(), 0LL);

// With custom operation
long long prod = reduce(v.begin(), v.end(), 1LL, multiplies<>());

Ranges (C++20, brief)

#include <ranges>
namespace rv = std::ranges::views;

// Sort without .begin()/.end()
ranges::sort(v);
ranges::sort(v, greater<>());

// Lazy views -- no copies
auto evens = v | rv::filter([](int x){ return x % 2 == 0; });
auto squares = v | rv::transform([](int x){ return x * x; });

// Take / drop
auto first5 = v | rv::take(5);
auto rest = v | rv::drop(3);

// Reverse
auto rev = v | rv::reverse;

// Chaining
auto result = v | rv::filter([](int x){ return x > 0; })
                | rv::transform([](int x){ return x * 2; })
                | rv::take(10);

// ranges::min, ranges::max
int mn = ranges::min(v);
int mx = ranges::max(v);

Gotchas:

• Ranges views are lazy -- they don't produce a container. To materialize, use a loop or convert manually.
• Compiler support varies. Fine on CF (GCC 13+), but test locally.
• ranges::sort(v) is cleaner than sort(v.begin(), v.end()) but functionally identical.

---

Common Patterns

Frequency Map

// Count occurrences of each element
map<int, int> freq;
for (int x : v) freq[x]++;

// Or with unordered_map for O(1) average
unordered_map<int, int, custom_hash> freq;
for (int x : v) freq[x]++;

// Find most frequent element
auto it = max_element(freq.begin(), freq.end(),
    [](const auto& a, const auto& b){ return a.second < b.second; });
int mode = it->first;

Sorted Unique

// Remove duplicates from a vector
sort(v.begin(), v.end());
v.erase(unique(v.begin(), v.end()), v.end());

Coordinate Compression

vector<int> vals = v; // copy
sort(vals.begin(), vals.end());
vals.erase(unique(vals.begin(), vals.end()), vals.end());

// Compress: map each value to its rank
for (int& x : v) {
    x = lower_bound(vals.begin(), vals.end(), x) - vals.begin();
}
// Now v[i] is in [0, vals.size())

Custom Comparators

// Lambda comparator for sort
sort(v.begin(), v.end(), [](int a, int b) {
    return a > b; // descending
});

// Struct comparator for priority_queue
struct Cmp {
    bool operator()(const pair<int,int>& a, const pair<int,int>& b) const {
        return a.first > b.first; // min-heap by first element
    }
};
priority_queue<pair<int,int>, vector<pair<int,int>>, Cmp> pq;

// Comparator for set (custom ordering)
auto cmp = [](int a, int b) { return abs(a) < abs(b); };
set<int, decltype(cmp)> s(cmp);

Lambda with Capture

// Capture by reference (most common in CP)
int threshold = 10;
auto pred = [&](int x) { return x > threshold; };
int cnt = count_if(v.begin(), v.end(), pred);

// Recursive lambda (C++20 style -- needs explicit this)
// Pre-C++20: use function<> or pass lambda to itself
auto dfs = [&](auto&& self, int u, int p) -> void {
    for (int w : adj[u]) {
        if (w != p) self(self, w, u);
    }
};
dfs(dfs, root, -1);

Reading Input Fast

// Disable sync for fast I/O -- put at top of main()
ios::sync_with_stdio(false);
cin.tie(nullptr);

// Read a vector
int n; cin >> n;
vector<int> v(n);
for (auto& x : v) cin >> x;

// Read pairs / edges
vector<pair<int,int>> edges(m);
for (auto& [u, v] : edges) cin >> u >> v;

Adjacency List from Edges

int n, m;
cin >> n >> m;
vector<vector<int>> adj(n + 1);
for (int i = 0; i < m; i++) {
    int u, v;
    cin >> u >> v;
    adj[u].push_back(v);
    adj[v].push_back(u); // omit for directed
}

---

Contest Cheat Sheet

+-------------------------------------------------------+
| STL COMPLETE REFERENCE                                |
+-------------------------------------------------------+
| CONTAINERS                                            |
|   vector    - default, O(1) back, O(n) mid            |
|   set/map   - sorted, O(log n) everything             |
|   unord_map - O(1) avg, USE CUSTOM HASH on CF         |
|   pq        - max-heap default, greater<> for min     |
|   bitset<N> - O(N/64) bitwise, compile-time size      |
|   pair      - {first,second}, lexicographic compare    |
+-------------------------------------------------------+
| ALGORITHMS                                            |
|   sort(all(v))          nth_element for O(n) median   |
|   lower_bound/upper_bound on sorted range             |
|   accumulate(all(v), 0LL)  <-- 0LL not 0!            |
|   unique after sort, then erase tail                  |
|   all_of/any_of/none_of  with lambda predicate        |
|   set_union/set_intersection on sorted vectors        |
+-------------------------------------------------------+
| STRINGS                                               |
|   s.find(t) returns npos on failure -- always check   |
|   stoi(s)/to_string(n) for conversions                |
|   tolower(c)/toupper(c) from <cctype>                 |
+-------------------------------------------------------+
| MATH                                                  |
|   abs(long long) -- use llabs() to be safe            |
|   ceil_div: (a + b - 1) / b                           |
|   isqrt: sqrt() then adjust +/- 1                     |
|   pow() is FLOAT -- use binary exp for integers       |
|   __lg(x) = floor(log2(x)), x > 0                    |
+-------------------------------------------------------+
| TRAPS                                                 |
|   v.size()-1 when empty  ->  use ssize(v) or cast     |
|   multiset.erase(x) erases ALL  ->  erase(find(x))   |
|   map[key] inserts default  ->  use find/count        |
|   min(int, long long) won't compile  ->  match types  |
|   comp must be strict: < not <=                       |
|   remove() doesn't resize -- must erase() after       |
+-------------------------------------------------------+

---

What the Code Won't Teach You

Insights drawn from reflection notes

STL performance is not uniform. vector<int> access is cache-friendly and fast. set<int> access involves tree traversal with pointer chasing -- much slower per operation despite the same $O(\log n)$ complexity. For performance-critical inner loops, prefer vectors (even with manual sorting) over sets.

Custom comparators are a correctness minefield. A comparator for std::sort must be a strict weak ordering: irreflexive, asymmetric, transitive. Using <= instead of < triggers undefined behavior -- usually a crash or infinite loop in sort. The rule: always use < (strictly less), never <=.

The size()-1 trap kills silently. v.size() returns size_t (unsigned). When v is empty, v.size() - 1 wraps to $2^{64}-1$. This creates an astronomically large loop bound. Always cast: (int)v.size() - 1 or use C++20's ssize(v).

  STL PERFORMANCE HIERARCHY (operations per second, rough):

  ┌────────────────────────────────────────────────┐
  │  Fastest                                       │
  │  ┌──────────────────────────────────────┐      │
  │  │  int arr[N]     ~10⁹ ops/sec        │      │
  │  │  vector<int>    ~10⁹ ops/sec        │      │
  │  └──────────────────────────────────────┘      │
  │  ┌──────────────────────────────────────┐      │
  │  │  deque<int>     ~5x10⁸ ops/sec      │      │
  │  │  bitset<N>      ~10¹⁰ bit ops/sec   │      │
  │  └──────────────────────────────────────┘      │
  │  ┌──────────────────────────────────────┐      │
  │  │  unordered_map  ~10⁸ ops/sec (avg)  │      │
  │  └──────────────────────────────────────┘      │
  │  ┌──────────────────────────────────────┐      │
  │  │  set / map      ~5x10⁷ ops/sec      │      │
  │  └──────────────────────────────────────┘      │
  │  Slowest                                       │
  └────────────────────────────────────────────────┘

  In tight loops (Mo's, sweep line):
  array >> unordered_map >> map
  The difference is often AC vs TLE.

  CONTAINER SELECTION DECISION TREE:

  Need to store elements?
       │
       ├── Need random access by index?
       │   ├── Size known at compile time?  -> array<T,N>
       │   └── Size dynamic?                -> vector<T>
       │
       ├── Need fast push/pop at BOTH ends?
       │   └── deque<T>
       │
       ├── Need sorted unique elements?
       │   ├── Need k-th element / rank?   -> PBDS ordered_set
       │   └── Otherwise?                  -> set<T>
       │
       ├── Need sorted with duplicates?
       │   └── multiset<T>
       │
       ├── Need key->value mapping?
       │   ├── Need ordering?              -> map<K,V>
       │   └── Need speed?                 -> unordered_map<K,V>
       │                                     (+ custom hash on CF!)
       │
       └── Need min/max always available?
           ├── Max-heap?  -> priority_queue<T>
           └── Min-heap?  -> priority_queue<T, vector<T>, greater<T>>

Mental Traps

Integrated from reflection notes

Trap: "STL functions work on any container."

std::sort requires random-access iterators -- works on vector, array, deque. Does NOT work on std::list or std::set. Similarly, std::binary_search works on sorted ranges but NOT on set -- use set::find or set::lower_bound instead.

Trap: "endl is the same as \n."

endl flushes the stream. "\n" doesn't. With fast I/O, endl can slow output by 100x. Always use "\n" unless you explicitly need a flush.

Trap: "Iterator invalidation doesn't happen to me."

push_back during vector iteration can reallocate and invalidate ALL iterators. Erasing from a vector while iterating causes undefined behavior. Always check invalidation rules.

Trap: "Using map for frequency counting."

For integer keys in range $[0,N)$ with $N\le {10}^6$: int cnt[N] is 10-100x faster than unordered_map<int,int>. This matters in Mo's algorithm and similar tight loops.

Trap: "std::set supports rank queries."

Problem D needs a sorted container with rank queries. You reach for std::set, write the solution, then realize set has no 'find k-th element.' You waste 20 minutes trying workarounds before switching to policy-based ordered_set. Know your containers' limits before the contest: std::set has lower_bound/upper_bound but no O(log n) k-th selection -- for that you need __gnu_pbds::tree with find_by_order / order_of_key.

---

Self-Test

Drawn from reflection notes

• [ ] Write from memory the declaration of a min-heap priority_queue and a max-heap priority_queue. This should be instant -- no looking.

• [ ] Explain iterator invalidation for std::vector: which operations invalidate iterators? What's the safe pattern for erasing multiple elements?

• [ ] ms.erase(x) vs ms.erase(ms.find(x)) on a multiset -- what does each do? When would you use each? Getting this wrong causes silent bugs.

• [ ] State the complexity of: std::sort on vector(n), lower_bound on sorted vector(n), set::lower_bound on set(n), unordered_map::find average and worst case.

• [ ] Write a custom comparator for std::sort that sorts pairs (int, int) by second element descending, ties broken by first ascending. Verify it satisfies strict weak ordering (<, not <=).