Getting everything ready for you…

Loading courses, problems and your progress. This takes just a moment.

0s

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

Interview one-liners

More C++ notes