viii. STL and Libraries Reference

When to use which part of the C++ standard library, what every operation costs and invalidates, and what the common contest libraries provide. Language-level pitfalls (overflow, comparators, hashing) are in C++ for Competitive Programming; data structures beyond the STL are in the Data Structure Catalog.

Choosing a container

Need	Use	Not
a sequence, random access, append	vector	list (cache misses, 24+ bytes per element)
push / pop at both ends	deque, or a ring buffer on a vector	vector::insert(begin()) ($O(n)$)
LIFO / FIFO only	vector as a stack, queue or a head index on a vector
ordered keys, predecessor / successor, min / max under updates	set / map	unordered_* (no order)
duplicates with order	multiset (erase one copy via erase(find(x)))	multiset::count in a loop ($O(\log n+k)$)
exact lookup only, hot loop	unordered_map with a randomized hash and reserve, or gp_hash_table	default hash<long long> (anti-hash tests)
keys in $[0,n)$	a plain array or vector	any map
$k$-th element / rank in a dynamic set	pb_ds tree, or a Fenwick tree over compressed values	std::distance on set iterators ($O(n)$)
max / min with insertions	priority_queue (max-heap by default)	set when no erase-arbitrary is needed (3x slower)
booleans in bulk, word-parallel operations	bitset<N> (compile-time $N$), vector<char> for plain flags	vector<bool> when you need references
strings	string, string_view for read-only slices	char* arithmetic
iterator stability while inserting	list, set, map	vector, deque

Containers: costs and invalidation

Container	Access	Insert	Erase	Find	Invalidated by insert	Invalidated by erase
vector	$O(1)$	back $O(1{)}^{\ast }$, else $O(n)$	back $O(1)$, else $O(n)$	$O(n)$	all if reallocation, else from the insertion point on	from the erased element on
deque	$O(1)$	ends $O(1)$, else $O(n)$	ends $O(1)$, else $O(n)$	$O(n)$	all iterators (references at the ends stay valid)	ends: only erased; middle: all
list, forward_list	$O(n)$	$O(1)$ at an iterator	$O(1)$	$O(n)$	none	only the erased
set, map, multi*	—	$O(\log n)$ (hinted: $O(1{)}^{\ast }$)	$O(\log n)$, by iterator $O(1{)}^{\ast }$	$O(\log n)$	none	only the erased
unordered_*	—	$O(1{)}^{†}$	$O(1{)}^{†}$	$O(1{)}^{†}$	all iterators on rehash (references stay valid)	only the erased
priority_queue	top $O(1)$	$O(\log n)$	top $O(\log n)$	—	—	—
string	$O(1)$	back $O(1{)}^{\ast }$	back $O(1)$	find $O(nm)$	like vector	like vector
bitset<N>	$O(1)$	—	—	_Find_first, _Find_next $O(N/64)$	—	—

${}^{\ast }$ amortized, ${}^{†}$ expected. Measured memory per element is in the Data Structure Catalog (vector<int> 4 B, set<int> 40 B, unordered_map<int,int> 27 B, plus allocator overhead for node containers).

Algorithms

Algorithm	Cost	Notes
sort	$O(n\log n)$ worst (introsort)	not stable
stable_sort	$O(n\log n)$ with a buffer, $O(n{\log }^{2}n)$ without	merge sort
partial_sort(b, b + k, e)	$O(n\log k)$	smallest $k$, sorted
nth_element(b, b + k, e)	$O(n)$ average	$k$-th smallest in place, smaller ones before it
lower_bound, upper_bound, equal_range, binary_search	$O(\log n)$ comparisons	on random-access ranges; on set use the member functions
partition_point(b, e, pred)	$O(\log n)$	binary search on a predicate: Binary Search
unique + erase	$O(n)$	removes adjacent duplicates: sort first
next_permutation / prev_permutation	$O(n)$ worst, $O(1)$ amortized over all permutations	returns false after the last one; start from sorted
reverse, rotate, shuffle	$O(n)$	shuffle(all(a), rng) with mt19937, never random_shuffle
merge, inplace_merge	$O(n)$ ($O(n\log n)$ in place without a buffer)	merge-sort steps, CDQ
set_union, set_intersection, set_difference, includes	$O(n+m)$	sorted inputs
accumulate(b, e, 0LL)	$O(n)$	the type of the initial value is the type of the sum: 0 overflows
partial_sum, adjacent_difference, inclusive_scan	$O(n)$	prefix sums and differences
iota, fill, count, count_if, find_if, all_of, any_of	$O(n)$
min_element, max_element, minmax_element	$O(n)$	return iterators
gcd, lcm (<numeric>)	$O(\log )$	lcm can overflow; divide first
__builtin_popcountll, __builtin_clzll, __builtin_ctzll, __lg	$O(1)$	clz(0), ctz(0) are undefined
C++20 <bit>: popcount, countl_zero, countr_zero, bit_width, bit_ceil, has_single_bit	$O(1)$	unsigned types only
C++20 ranges: ranges::sort(a), views::iota, views::reverse	same as above	shorter code; std::span for array views

vector<int> compressRanks(const vector<ll>& a) {            // rank of each value among the distinct values
    vector<ll> v(a); sort(all(v)); v.erase(unique(all(v)), v.end());
    vector<int> r(sz(a));
    for (int i = 0; i < sz(a); i++) r[i] = int(lower_bound(all(v), a[i]) - v.begin());
    return r;
}
 
ll countInRange(const vector<ll>& sorted, ll lo, ll hi) {   // how many values lie in [lo, hi]
    return upper_bound(all(sorted), hi) - lower_bound(all(sorted), lo);
}
 
vector<int> argsortStable(const vector<ll>& a) {           // indices by value, ties by index
    vector<int> p(sz(a)); iota(all(p), 0);
    stable_sort(all(p), [&](int i, int j) { return a[i] < a[j]; });
    return p;
}
 
ll kthSmallest(vector<ll> a, int k) {                      // 0-based k
    nth_element(a.begin(), a.begin() + k, a.end());
    return a[k];
}
 
vector<ll> sortedIntersection(const vector<ll>& a, const vector<ll>& b) {   // a, b sorted
    vector<ll> c; set_intersection(all(a), all(b), back_inserter(c));
    return c;
}

Proof: the idioms, and next_permutation is O(1) amortized

Compression. After sort and unique, v lists the distinct values increasingly, so lower_bound finds each value’s position, which is its rank. countInRange: in a sorted array, lower_bound(lo) is the first index with value $\ge$ lo and upper_bound(hi) the first with value $>$ hi; the elements between are exactly those in $[lo,hi]$. argsortStable: stable_sort keeps equal keys in input order, and the input is $0,1,\dots$, so ties are ordered by index. kthSmallest: nth_element places at position $k$ the element that would be there after sorting. Intersection: set_intersection walks both sorted ranges once, emitting common elements (with multiplicity $\min$).

next_permutation. One call finds the longest non-increasing suffix, swaps its predecessor with the next larger element of the suffix and reverses the suffix: cost $O(1+L)$ where $L$ is the length of that suffix. The last $j$ elements are strictly decreasing in exactly a $\frac{1}{j!}$ fraction of all permutations, so over all $n!$ calls the average of $L$ is ${\sum }_{j\ge 1}P(L\ge j)={\sum }_{j\ge 1}\frac{1}{j!}<e-1$: $O(1)$ amortized per call. Checked against brute force on random inputs.

Policy-based data structures (__gnu_pbds)

Structure	Declaration	Extra operations
order-statistics tree	tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>	find_by_order(k) ($k$-th, 0-based), order_of_key(x) (count $<x$), $O(\log n)$
multiset version	key pair<T, int> with a unique counter, or less_equal<T> (breaks find / erase)
hash table	gp_hash_table<K, V, Hash> (open addressing), cc_hash_table (chaining)	usually 2–3x faster than unordered_map; still needs a randomized hash
priority queue	__gnu_pbds::priority_queue<T, Cmp, pairing_heap_tag>	join (meld), modify (decrease-key) through point iterators
rope (<ext/rope>)	__gnu_cxx::rope<T>	$O(\log n)$ insert / erase / substring; persistence by copy

Details and examples: Ordered Set and PBDS. pb_ds is a GCC extension: it does not exist on MSVC or Clang with libc++.

Contest libraries and what each is good for

Library	Contents	Best for
KACTL (KTH team notebook)	contest (template, hash, stress-test scripts), mathematics, data-structures (OrderStatisticTree, HashMap, SegmentTree, LazySegmentTree, Treap, LineContainer, RMQ, MoQueries), numerical (FFT, NTT, FFT mod, polynomial roots, Simplex, Gaussian elimination, determinant), number-theory (Miller–Rabin, Pollard rho, ModSqrt, CRT, phi), combinatorial, graph (Dinic, push-relabel, min-cost flow, Hungarian, general matching, SCC, 2-SAT, link-cut tree, HLD, dominator tree), geometry (Point, convex hull, polygon tools, 3D hull, Delaunay), strings (KMP, Z, Manacher, suffix array, suffix tree, Aho–Corasick, hashing), various	ICPC: fits the 25-page reference limit, every file is short and tested; adapt by removing what the team never uses and adding the team’s own snippets
AtCoder Library (ACL)	modint, convolution (NTT, convolution_ll), fenwick_tree, segtree, lazy_segtree, dsu, maxflow, mcf_graph, scc_graph, two_sat, string (suffix_array, lcp_array, z_algorithm), math (pow_mod, inv_mod, crt, floor_sum)	AtCoder (preinstalled); a clean, well-tested API to copy into Codeforces solutions
Library Checker (yosupo)	a judge with one problem per algorithm (convolution, polynomial ops, matching, …)	verifying your own templates
ei1333 library, Nyaan’s library	very broad, heavily verified libraries (polynomials, graphs, data structures)	looking up an implementation of an advanced algorithm
cp-algorithms (e-maxx)	articles with code for most classical algorithms	learning an algorithm with proofs
the owner’s template	the personal template repository	see 🐬 Templates

Rules of thumb: know your library’s interfaces before the contest; never paste code you cannot debug; for ICPC, keep the notebook organised by chapter and include the complexity and pitfalls of every snippet.

Related notes

• C++ for Competitive Programming
• Containers, Hashing and Choosing a Structure
• Ordered Set and PBDS
• Data Structure Catalog
• 🐬 Templates