Notes › C++
C++ STL Cheat Sheet
The Standard Template Library gives containers, algorithms and iterators. For DSA and competitive programming, knowing it well saves time and bugs.
#include <bits/stdc++.h> // all standard headers (fine for practice/contests)
using namespace std;
vector — dynamic array
vector<int> v; // empty
vector<int> a(5, 0); // 5 zeros
vector<vector<int>> g(n, vector<int>(m, -1)); // 2-D, n × m
v.push_back(3); v.emplace_back(4);
v.pop_back(); v.back(); v.front(); v.size(); v.empty();
v.insert(v.begin() + 1, 9); // O(n)
v.erase(v.begin()); // O(n)
v.clear();
sort(v.begin(), v.end()); // ascending
sort(v.rbegin(), v.rend()); // descending
reverse(v.begin(), v.end());
Access O(1), push_back O(1) amortised. v.reserve(n) avoids repeated reallocations.
pair and tuple
pair<int, string> p = {1, "a"}; p.first; p.second;
auto [id, name] = p; // structured binding (C++17)
vector<pair<int,int>> e; sort(e.begin(), e.end()); // sorts by first, then second
string
string s = "codify";
s.size(); s.substr(1, 3); // "odi" (start, length)
s.find("dif"); // index or string::npos
s += "!"; s.push_back('x');
reverse(s.begin(), s.end());
to_string(42); stoi("42"); stoll("123456789012"); // conversions
substr copies → O(length). Use += instead of s = s + t in loops.
stack, queue, deque
stack<int> st; st.push(1); st.top(); st.pop(); // LIFO
queue<int> q; q.push(1); q.front(); q.pop(); // FIFO
deque<int> d; d.push_front(1); d.push_back(2); d.pop_front(); d[0];
All O(1). pop() returns nothing — read top()/front() first.
priority_queue — heap
priority_queue<int> maxH; // max-heap (default)
priority_queue<int, vector<int>, greater<int>> minH; // min-heap
priority_queue<pair<int,int>, vector<pair<int,int>>, greater<>> pq; // Dijkstra: {dist, node}
maxH.push(5); maxH.top(); maxH.pop();
push/pop O(log n), top O(1).
set and multiset — sorted, balanced BST
set<int> s = {5, 1, 3};
s.insert(4); s.erase(3); s.count(5); s.find(1) != s.end();
*s.begin(); *s.rbegin(); // min, max
auto it = s.lower_bound(4); // first >= 4
auto jt = s.upper_bound(4); // first > 4
multiset<int> ms; // allows duplicates
ms.erase(ms.find(x)); // remove ONE copy (ms.erase(x) removes all!)
insert/erase/find O(log n). Use s.lower_bound(x), not lower_bound(s.begin(), s.end(), x) — the free function is O(n) on sets.
map — sorted key → value
map<string, int> m;
m["apple"]++; // creates the key with 0 if missing!
m.count("x"); m.find("x");
for (auto& [k, v] : m) cout << k << ' ' << v << '\n'; // sorted by key
m.erase("apple");
O(log n). m[key] inserts a default — use find/count just to check.
unordered_set / unordered_map — hash tables
Same interface, O(1) average, O(n) worst case, no order. Prefer them for counting and lookups; use map/set when you need order or lower_bound.
unordered_map<int, int> freq;
for (int x : a) freq[x]++;
freq.reserve(1 << 20); // fewer rehashes
Iterators
begin(), end() (one past the last), rbegin(), prev(it), next(it), distance(a, b). With auto: for (auto it = m.begin(); it != m.end(); ++it).
must-knows
sort(a.begin(), a.end()); // O(n log n)
stable_sort(...); // keeps equal elements in order
binary_search(a.begin(), a.end(), x); // needs sorted input
lower_bound(a.begin(), a.end(), x) - a.begin(); // index of first >= x
upper_bound(...) // first > x
*max_element(a.begin(), a.end()); *min_element(...);
accumulate(a.begin(), a.end(), 0LL); // sum (0LL avoids overflow!)
count(a.begin(), a.end(), x);
next_permutation(a.begin(), a.end()); // next lexicographic permutation
a.erase(unique(a.begin(), a.end()), a.end()); // remove duplicates (sort first)
fill(a.begin(), a.end(), 0);
iota(a.begin(), a.end(), 0); // 0, 1, 2, …
__gcd(a, b); gcd(a, b); // C++17 <numeric>
Custom comparators
sort(v.begin(), v.end(), [](const auto& x, const auto& y) {
if (x.second != y.second) return x.second > y.second; // by second, descending
return x.first < y.first; // then by first
});
The comparator must be a strict weak ordering: return false for equal elements (use <, never <=), or sort can crash.
For a set/priority_queue of structs, define operator< or pass a comparator type.
Complexity summary
| Container | Insert | Delete | Find | Order |
|---|---|---|---|---|
| vector | O(1)* end | O(1) end | O(n) | insertion |
| deque | O(1) both ends | O(1) both ends | O(n) | insertion |
| set / map | O(log n) | O(log n) | O(log n) | sorted |
| unordered_set / map | O(1) avg | O(1) avg | O(1) avg | none |
| priority_queue | O(log n) | O(log n) top | top O(1) | heap |
Common pitfalls
intoverflow: uselong longfor sums and products (1LL * a * b).v.size() - 1is unsigned → huge when the vector is empty; cast toint.- Passing big vectors by value → copies; use
const vector<int>&. - Fast I/O:
ios::sync_with_stdio(false); cin.tie(nullptr);and'\n'instead ofendl.
Interview one-liners
- set/map are red-black trees (sorted, O(log n)); unordered_ are hash tables (O(1) avg).
- priority_queue is a max-heap by default; use
greater<>for a min-heap. lower_bound= first ≥ x,upper_bound= first > x.- Related: C++ docs, C++ cheat sheet, Pointers & References in C++.