C++ STL: Zero to Hero

Part 0 · Why STL Exists

vector<int> v;        // done. resizes itself. cleans up on its own.

The 5 Pillars of STL

Everything in STL is built from five kinds of building blocks. Memorize these names — every chapter below maps back to them.

Your Very First STL Program

One header unlocks everything:

#include <bits/stdc++.h>   // pulls in the entire STL — perfect for contests
using namespace std;     // so we can write `vector` instead of `std::vector`


int main() {
    vector<int> a = {3, 1, 4, 1, 5, 9, 2, 6};
    sort(a.begin(), a.end());          // algorithm works on iterator range
    for (int x : a) cout << x << ' ';  // 1 1 2 3 4 5 6 9
}

That tiny program touched all five pillars:

• Container: vector<int>
• Iterators: a.begin(), a.end()
• Algorithm: sort()
• Functor: implicit less<int> (the default comparator)
• Adapter: the range-for loop adapts the iterator pair into a clean syntax

Part 1.1 · vector — The Workhorse

Internal model — capacity vs size

A vector keeps a contiguous chunk of memory. Two numbers describe it:

• size() — how many elements you've actually stored.
• capacity() — how much memory has been reserved (≥ size).

When size == capacity and you push_back one more, the vector allocates a bigger block (typically 2× capacity), copies everything over, and frees the old one. This doubling strategy is what makes push_back O(1) amortized.

Declaration & initialization (5 ways)

vector<int> a;                      // empty
vector<int> b(10);                  // 10 zeros
vector<int> c(10, -1);              // 10 copies of -1
vector<int> d = {3, 1, 4, 1, 5};   // from initializer list
vector<int> e(d.begin(), d.end());   // copy from range

The full operation cheat sheet

Three ways to iterate

vector<int> v = {10, 20, 30};


// 1) classic index loop — when you need the index
for (int i = 0; i < (int)v.size(); ++i)
    cout << i << ":" << v[i] << ' ';


// 2) range-based for — cleanest, when you only need the value
for (int x : v) cout << x << ' ';
for (int& x : v) x *= 2;        // note the & — modifies in place


// 3) iterator loop — verbose but very explicit; needed for erase()
for (auto it = v.begin(); it != v.end(); ++it)
    cout << *it << ' ';

2D vectors — vectors of vectors

// a 5×7 grid of zeros
vector<vector<int>> grid(5, vector<int>(7, 0));


grid[2][3] = 42;
int rows = grid.size();
int cols = grid[0].size();

⚠️ Iterator invalidation — the #1 bug source

When a vector grows past its capacity, it reallocates. Every iterator, pointer, and reference into the old memory becomes invalid. Using them is undefined behavior.

vector<int> v = {1, 2, 3};
int& ref = v[0];        // ref points into v's buffer
v.push_back(4);          // vector might reallocate!
cout << ref;             // 💥 might crash or print garbage

Rules:

• push_back / emplace_back / insert / resize / reserve — may invalidate everything if a reallocation happens.
• erase(it) — invalidates it and everything after it.
• pop_back — invalidates only the iterator/reference to the last element.
• operator[] / at() — never invalidate (read-only operations don't reallocate).

The 5 most common beginner mistakes

Part 1.2 · deque — Double-Ended Queue

What it adds over vector

deque<int> dq;
dq.push_back(1);  dq.push_back(2);   // dq: [1, 2]
dq.push_front(0);                       // dq: [0, 1, 2]
cout << dq[1];                            // 1
dq.pop_front();                            // dq: [1, 2]

The killer use-case: sliding window

To find the maximum of every window of size k in an array, you keep a deque of indices in decreasing order of their values. The front is always the current window's max.

// Sliding-window maximum, O(n)
vector<int> slidingMax(vector<int>& a, int k) {
    deque<int> dq;          // stores indices, values strictly decreasing
    vector<int> ans;
    for (int i = 0; i < (int)a.size(); ++i) {
        while (!dq.empty() && dq.front() <= i - k) dq.pop_front();
        while (!dq.empty() && a[dq.back()] < a[i]) dq.pop_back();
        dq.push_back(i);
        if (i >= k - 1) ans.push_back(a[dq.front()]);
    }
    return ans;
}

Part 1.3 · array — Fixed-Size Container

std::array<T, N> is a thin wrapper around a C-style array. The size N is part of the type and known at compile time.

array<int, 5> a = {1, 2, 3, 4, 5};
a.fill(0);            // all zeros
cout << a.size();    // 5  (compile-time known)
for (int x : a) cout << x;

Part 1.4 · list & forward_list — Linked Lists

• list — doubly-linked list. push_front, push_back, insert, erase are all O(1) given an iterator. splice() moves nodes between lists in O(1) without copying — this is the only situation where list truly shines.
• forward_list — singly linked. Smaller per-node memory but you can only iterate forward. Rarely used.

list<int> A = {1, 2, 3};
list<int> B = {10, 20};
auto it = A.begin(); ++it;       // points at 2
A.splice(it, B);                 // A: [1, 10, 20, 2, 3]; B is now empty — O(1)

Part 2.1 · set — Sorted Bag of Unique Elements

What it gives you

• Elements are kept in sorted order (ascending by default).
• No duplicates — inserting an existing element is a no-op.
• All operations are O(log n): insert, erase, find, count.
• Internally a balanced BST (red-black tree).

The full operation table

Working example

set<int> s;
s.insert(5);  s.insert(2);  s.insert(8);  s.insert(2);
// s now contains: {2, 5, 8} — duplicate 2 was ignored


for (int x : s) cout << x << ' ';       // 2 5 8 (sorted)


if (s.find(5) != s.end()) cout << "yes";
if (s.count(5))            cout << "yes";        // equivalent


s.erase(2);                                 // {5, 8}
cout << *s.begin();                          // 5  (smallest)
cout << *s.rbegin();                         // 8  (largest)

lower_bound vs upper_bound — finally explained

This is the most-asked STL question. Both return an iterator into the sorted set. The difference is what they do with elements equal to the query.

set<int> s = {10, 20, 20, 30, 40};   // (set has no dups, so really {10,20,30,40})


s.lower_bound(20);   // → iterator to 20
s.upper_bound(20);   // → iterator to 30
s.lower_bound(25);   // → iterator to 30 (no exact match, returns next ≥)
s.upper_bound(40);   // → s.end()  (nothing strictly greater)

The "find closest" pattern

// Find the element in s closest to x
auto it = s.lower_bound(x);  // first element ≥ x
int best = INT_MAX;
if (it != s.end())            best = min(best, *it - x);
if (it != s.begin()) {
    --it;
    best = min(best, x - *it);
}

Part 2.2 · multiset — Sorted Bag With Duplicates

A multiset is identical to a set except it allows the same value to appear multiple times.

multiset<int> ms;
ms.insert(5);  ms.insert(5);  ms.insert(3);
// ms: {3, 5, 5}
cout << ms.count(5);    // 2 — really counts now (not just 0/1)

⚠️ The classic erase trap

ms.erase(5);                 // removes ALL copies of 5
ms.erase(ms.find(5));      // removes EXACTLY ONE copy

Common use: priority-like structure with random delete

multiset is essentially a heap that also lets you remove arbitrary elements in O(log n) — something a priority_queue can't do.

multiset<int> ms = {3, 1, 4, 1, 5, 9, 2};
int mn = *ms.begin();           // min in O(1)
int mx = *ms.rbegin();          // max in O(1)
ms.erase(ms.find(4));         // delete arbitrary value in O(log n)

Part 2.3 · map — Sorted Phone Book

The basics

map<string, int> age;
age["alice"] = 30;
age["bob"]   = 25;
age["carol"] = 28;


cout << age["bob"];        // 25
age.erase("alice");
cout << age.size();        // 2


for (auto& [name, a] : age)              // C++17 structured binding — beautiful
    cout << name << ":" << a << '\n';     // in alphabetical order!

operator[] vs at() vs find() — pick the right one

if (m[k] == 5)                // 💀 inserts m[k]=0 if k absent!
if (m.count(k) && m[k] == 5)  // ✅ correct

Counting frequencies (the killer use)

map<string, int> freq;
for (string& w : words) freq[w]++;     // auto-creates with 0, then ++


for (auto& [word, c] : freq)
    cout << word << ": " << c << '\n';

map of map (2D mapping)

map<string, map<string, int>> grid;
grid["alice"]["math"] = 95;
grid["alice"]["phys"] = 88;

map vs unordered_map — quick reference

Part 2.4 · multimap — One Key, Many Values

A multimap allows many entries with the same key. operator[] doesn't exist (which value would it return?). You access groups of equal keys via equal_range:

multimap<string, int> mm;
mm.insert({"alice", 95});
mm.insert({"alice", 88});
mm.insert({"bob",   72});


auto [first, last] = mm.equal_range("alice");
for (auto it = first; it != last; ++it)
    cout << it->second << ' ';        // 88 95 (sorted by key, kept in insertion order within key in newer C++)

Part 3 · unordered_set & unordered_map (Hash-based)

The interface mirrors set/map

Same operations, same names — only the complexity and ordering change.

unordered_set<int> us;
us.insert(5);  us.insert(2);  us.insert(8);
if (us.count(5)) cout << "present";
us.erase(2);


unordered_map<string, int> um;
um["alice"] = 30;       // same operator[] as map
um.erase("alice");

Decision: ordered vs unordered

The hash collision worst case

Hash tables are O(1) average. If many keys hash to the same bucket, all those keys live in a chain that must be linearly scanned — operations degrade to O(n).

For random data this never happens. But contest setters know this. They craft inputs that hash to the same bucket on purpose. The result: your O(n log n) solution times out as O(n²).

Quick-fix: hash + a random seed

struct SafeHash {
    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 SEED =
            chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + SEED);
    }
};


unordered_map<long long, int, SafeHash> safe_map;

Part 4.1 · stack — Last In, First Out

The whole interface (only 5 things)

stack<int> st;
st.push(10);   st.push(20);   st.push(30);
cout << st.top();      // 30
st.pop();              // removes 30 (returns void!)
cout << st.size();     // 2
cout << st.empty();    // false

Classic problem: balanced brackets

bool isBalanced(const string& s) {
    stack<char> st;
    for (char c : s) {
        if (c == '(' || c == '[' || c == '{') st.push(c);
        else {
            if (st.empty()) return false;
            char t = st.top(); st.pop();
            if (c == ')' && t != '(') return false;
            if (c == ']' && t != '[') return false;
            if (c == '}' && t != '{') return false;
        }
    }
    return st.empty();
}

Part 4.2 · queue — First In, First Out

queue<int> q;
q.push(10);   q.push(20);   q.push(30);
cout << q.front();    // 10  (oldest)
cout << q.back();     // 30  (newest)
q.pop();             // removes 10 (the front)

The killer use: BFS (breadth-first search)

vector<int> bfs(vector<vector<int>>& g, int src) {
    int n = g.size();
    vector<int> dist(n, -1);
    queue<int> q;
    dist[src] = 0;
    q.push(src);
    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (int v : g[u]) if (dist[v] == -1) {
            dist[v] = dist[u] + 1;
            q.push(v);
        }
    }
    return dist;
}

Part 4.3 · priority_queue — The Heap

Default: max-heap

priority_queue<int> pq;       // MAX-heap by default
pq.push(3);  pq.push(1);  pq.push(5);  pq.push(2);
cout << pq.top();    // 5
pq.pop();
cout << pq.top();    // 3

• push(x), pop() — both O(log n)
• top(), size(), empty() — O(1)
• You cannot iterate or search a priority_queue. If you need that, use multiset.

Three ways to make a min-heap

// Way 1: use greater<> comparator (the standard way)
priority_queue<int, vector<int>, greater<int>> minPQ;


// Way 2: negate values, use max-heap (cheap hack — int only!)
priority_queue<int> tricky;
tricky.push(-x);                       // store -x, top is the smallest x


// Way 3: lambda comparator (verbose but flexible)
auto cmp = [](int a, int b){ return a > b; };
priority_queue<int, vector<int>, decltype(cmp)> minPQ2(cmp);

Custom comparator with pairs

// Min-heap of (distance, node) pairs — for Dijkstra
priority_queue<
    pair<int, int>,
    vector<pair<int, int>>,
    greater<pair<int, int>>
> pq;

The "stale entry" trick (for Dijkstra)

Since priority_queue can't update an element in place, Dijkstra uses a clever trick: push the new (smaller) distance and ignore stale entries when they pop later.

while (!pq.empty()) {
    auto [d, u] = pq.top(); pq.pop();
    if (d > dist[u]) continue;          // stale — ignore
    for (auto& [v, w] : g[u]) {
        if (dist[u] + w < dist[v]) {
            dist[v] = dist[u] + w;
            pq.push({dist[v], v});      // might create stale entry — that's ok
        }
    }
}

Part 5 · Iterators — The Glue of STL

Why iterators exist

STL algorithms don't know what container they're working on. sort doesn't care if you give it a vector, a deque, or a plain C array — it just walks from one iterator to another. That separation is the genius of STL: N containers × M algorithms = N × M combinations, with N + M code.

The half-open range [first, last)

Every STL algorithm takes a pair of iterators: first (start, inclusive) and last (one-past-end, exclusive). This convention has three big benefits:

• An empty range is naturally expressed as first == last.
• last - first directly gives the size.
• You never have to special-case "did I include the last element?".

vector<int> v = {10, 20, 30, 40, 50};


sort(v.begin(), v.end());           // whole range
sort(v.begin(), v.begin() + 3);       // first 3 elements only: [10,20,30)

The 5 iterator categories

Why this matters: some algorithms require random-access iterators. sort() needs random access — that's why you can't sort a list with std::sort. (Use list::sort() member instead.)

begin/end families

// reverse-print without reversing
for (auto it = v.rbegin(); it != v.rend(); ++it)
    cout << *it << ' ';

Iterator arithmetic

auto it = v.begin();
advance(it, 3);                  // move it forward by 3 — works on any iterator
auto nx = next(it);             // returns it+1 without modifying it
auto pv = prev(it);             // returns it-1 (bidirectional+)
int d = distance(v.begin(), it); // how many steps from begin to it

Iterator adapters — the secret weapons

Sometimes you want to write into a container via an algorithm. These adapters wrap a container so you can use it as an output iterator.

vector<int> src = {1, 2, 3};
vector<int> dst;
copy(src.begin(), src.end(), back_inserter(dst));
// dst is now {1, 2, 3}


// transform into a brand-new vector
vector<int> squared;
transform(src.begin(), src.end(), back_inserter(squared),
          [](int x){ return x*x; });
// squared is now {1, 4, 9}

How range-based for actually works

for (int x : v) { ... }


// is exactly equivalent to:
for (auto __it = v.begin(); __it != v.end(); ++__it) {
    int x = *__it;
    ...
}

So range-for works on anything with begin() and end() — including raw arrays, your own classes, and STL containers.

Part 6.1 · Sorting & Ordering Algorithms

sort — the workhorse

sort uses introsort (quicksort + heapsort fallback) — guaranteed O(n log n) worst case.

vector<int> v = {3, 1, 4, 1, 5, 9, 2, 6};


sort(v.begin(), v.end());                // ascending  → 1 1 2 3 4 5 6 9
sort(v.begin(), v.end(), greater<int>()); // descending → 9 6 5 4 3 2 1 1


// Lambda comparator — sort by absolute value
sort(v.begin(), v.end(),
     [](int a, int b){ return abs(a) < abs(b); });


// Sort pairs — by .second descending, then .first ascending
vector<pair<int,int>> pairs;
sort(pairs.begin(), pairs.end(),
     [](auto& a, auto& b){
         if (a.second != b.second) return a.second > b.second;
         return a.first < b.first;
     });

Other sorting flavors

// k-th smallest in O(n) average — much faster than full sort
nth_element(v.begin(), v.begin() + k, v.end());
int kth = v[k];


// Random shuffle — DON'T use random_shuffle, it's deprecated/removed
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
shuffle(v.begin(), v.end(), rng);

Part 6.2 · Searching Algorithms

Linear search family

auto it = find(v.begin(), v.end(), 7);     // returns iterator or end()
if (it != v.end()) cout << *it;


auto e = find_if(v.begin(), v.end(),
                  [](int x){ return x > 100; });    // first element > 100


auto ne = find_if_not(v.begin(), v.end(),
                       [](int x){ return x % 2 == 0; });  // first odd


int n = count(v.begin(), v.end(), 5);            // how many 5s
int e2 = count_if(v.begin(), v.end(),
                  [](int x){ return x % 2 == 0; });    // count evens

Binary search family — for SORTED ranges only

All four are O(log n) on random-access iterators (vector, array). On set/map iterators (bidirectional only) the free functions become O(n) — use the member versions.

vector<int> v = {1, 3, 5, 5, 5, 7, 9};


// Does 5 exist?
bool ok = binary_search(v.begin(), v.end(), 5);   // true


// How many 5s?
auto [lo, hi] = equal_range(v.begin(), v.end(), 5);
int cnt = hi - lo;                                // 3


// Index of first ≥ 4?
auto it = lower_bound(v.begin(), v.end(), 4);
int idx = it - v.begin();                       // 2 (points at 5)

Min/max algorithms

auto mn = *min_element(v.begin(), v.end());
auto mx = *max_element(v.begin(), v.end());
auto [mn2, mx2] = minmax_element(v.begin(), v.end());  // pair of iterators


// With custom comparator: longest string
auto longest = *max_element(words.begin(), words.end(),
    [](auto& a, auto& b){ return a.size() < b.size(); });

Part 6.3 · Modifying Algorithms

copy / fill / replace

vector<int> src = {1,2,3,4,5}, dst(5);
copy(src.begin(), src.end(), dst.begin());


copy_if(src.begin(), src.end(), back_inserter(dst),
        [](int x){ return x % 2 == 0; });


fill(v.begin(), v.end(), 0);            // every element = 0
fill_n(v.begin(), 5, 42);              // first 5 elements = 42


replace(v.begin(), v.end(), 3, 99);     // every 3 → 99
replace_if(v.begin(), v.end(),
           [](int x){return x<0;}, 0);     // negatives → 0

transform — apply a function to every element

// Single range: square every element in place
transform(v.begin(), v.end(), v.begin(),
          [](int x){ return x*x; });


// Two ranges: element-wise add
vector<int> a = {1,2,3}, b = {10,20,30}, c(3);
transform(a.begin(), a.end(), b.begin(), c.begin(),
          [](int x, int y){ return x + y; });
// c = {11, 22, 33}

The erase–remove idiom (the trickiest STL pattern)

remove doesn't actually remove anything — it shifts non-matching elements forward and returns an iterator to the new logical end. You then call erase on the tail to shrink the container.

// Remove all 0s from v
v.erase(remove(v.begin(), v.end(), 0), v.end());


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


// C++20 simplified: std::erase / std::erase_if (one call)
erase(v, 0);
erase_if(v, [](int x){ return x < 0; });

unique — collapse consecutive duplicates

Same idea as remove: must combine with erase, must be on a sorted range to actually remove all duplicates.

vector<int> v = {1, 3, 1, 3, 5};


sort(v.begin(), v.end());
v.erase(unique(v.begin(), v.end()), v.end());
// v is now {1, 3, 5}

Other modifiers

Part 6.4 · Set Operations (on sorted ranges)

These operate on two sorted ranges and produce a sorted result. They work on any container — vector, set, deque — as long as input is sorted.

vector<int> A = {1, 2, 3, 5};
vector<int> B = {2, 4, 5, 6};
vector<int> C;


set_intersection(A.begin(), A.end(),
                 B.begin(), B.end(), back_inserter(C));
// C = {2, 5}


C.clear();
set_union(A.begin(), A.end(),
          B.begin(), B.end(), back_inserter(C));
// C = {1, 2, 3, 4, 5, 6}

Part 6.5 · Numeric Algorithms (<numeric>)

accumulate — sum, product, anything

vector<int> v = {1, 2, 3, 4, 5};
int sum  = accumulate(v.begin(), v.end(), 0);              // 15
int prod = accumulate(v.begin(), v.end(), 1,
                       multiplies<int>());                // 120


// Sum of squares with a lambda
int sq = accumulate(v.begin(), v.end(), 0,
    [](int acc, int x){ return acc + x*x; });          // 55

Other numeric goodies

// Build prefix sums in one line
vector<long long> ps(n+1, 0);
partial_sum(a.begin(), a.end(), ps.begin() + 1);
// ps[i] = a[0] + ... + a[i-1]; query sum(l..r) = ps[r+1] - ps[l]

Part 6.6 · Condition Checkers (all_of, any_of, none_of)

bool allEven  = all_of (v.begin(), v.end(),
                          [](int x){ return x % 2 == 0; });
bool anyZero  = any_of (v.begin(), v.end(),
                          [](int x){ return x == 0; });
bool noneNeg  = none_of(v.begin(), v.end(),
                          [](int x){ return x < 0; });

All three short-circuit (return as soon as the answer is decided). They replace ugly hand-written loops with self-documenting one-liners.

Part 6.7 · Partition Algorithms

partition rearranges a range so that elements satisfying a predicate come first. Returns the iterator to the first element NOT satisfying the predicate.

vector<int> v = {1, 2, 3, 4, 5, 6};
auto mid = partition(v.begin(), v.end(),
                     [](int x){ return x % 2 == 0; });
// v: even elements, then odd elements (order WITHIN groups not preserved)
// mid points to the first odd element

• stable_partition — like partition but preserves relative order within each group.
• partition_point — for an already-partitioned range, returns the boundary in O(log n) (binary search by predicate).
• is_partitioned(first, last, pred) — check whether range is already partitioned by pred.

Part 7 · string — A Sequence Container in Disguise

String-specific operations

string s = "hello world";


size_t p = s.find("world");            // 6
if (p != string::npos) cout << "found at " << p;


string sub = s.substr(6, 5);            // "world"
string rest = s.substr(6);                // "world" (to end)


s.replace(0, 5, "HELLO");                // "HELLO world"
s.insert(5, ", ");                       // "HELLO,  world"
s.erase(5, 2);                          // back to "HELLO world"

Strings + STL algorithms

string s = "banana";


sort(s.begin(), s.end());                   // "aaabnn"
reverse(s.begin(), s.end());                // reverses in place
int as = count(s.begin(), s.end(), 'a');     // 3


// Are they anagrams?
bool anagram(string a, string b) {
    sort(a.begin(), a.end());
    sort(b.begin(), b.end());
    return a == b;
}

String parsing with stringstream

#include <sstream>
string line = "42 7 12 99";
stringstream ss(line);
int x;
vector<int> nums;
while (ss >> x) nums.push_back(x);   // {42, 7, 12, 99}


// Split a CSV line
string csv = "alice,bob,carol";
stringstream ss2(csv);
string token;
vector<string> tokens;
while (getline(ss2, token, ',')) tokens.push_back(token);

Number ↔ string conversion

string s = to_string(3.14);     // "3.140000"
int   n = stoi("42");             // 42
long long ll = stoll("99999999999");
double d = stod("3.14");          // 3.14


// With base (binary, hex, …)
int hex = stoi("ff", nullptr, 16);  // 255

Part 8 · Functors, Lambdas & Custom Comparators

Three ways to write a comparator

// 1) Free function
bool cmp(int a, int b) { return a > b; }
sort(v.begin(), v.end(), cmp);


// 2) Functor — a struct with operator()
struct Cmp {
    bool operator()(int a, int b) const { return a > b; }
};
sort(v.begin(), v.end(), Cmp());


// 3) Lambda — modern, clean, inline
sort(v.begin(), v.end(), [](int a, int b){ return a > b; });

Lambda anatomy

[capture](parameters) -> ReturnType { body }


// Examples
[](int x){ return x*2; }                  // no capture, returns int (deduced)
[&](int x){ count += x; }              // capture all by reference
[=](int x){ return x + offset; }       // capture all by value
[&count](int x){ count += x; }          // capture only `count` by reference
[=, &count](int x){ ... }                // most by value, count by reference

Built-in functor objects (<functional>)

Sorting pairs and structs

// Default pair sort: by .first asc, then .second asc
vector<pair<int,int>> v;
sort(v.begin(), v.end());


// Custom: by .second ascending, ties broken by .first descending
sort(v.begin(), v.end(), [](auto& a, auto& b){
    if (a.second != b.second) return a.second < b.second;
    return a.first > b.first;
});


// Custom struct
struct Person { string name; int age; };
vector<Person> people;
sort(people.begin(), people.end(), [](const Person& a, const Person& b){
    return a.age < b.age;
});

Custom comparator for set / map

// Set ordered by string length, then lexicographically
struct ByLen {
    bool operator()(const string& a, const string& b) const {
        if (a.size() != b.size()) return a.size() < b.size();
        return a < b;
    }
};
set<string, ByLen> s;

Part 9.1 · bitset — Compact Bit Array

A bitset<N> is a fixed-size array of N bits, packed tight (8 bits per byte). Bitwise operations on bitsets run 64 bits at a time on a 64-bit CPU — that's a free 64× speedup for problems like subset DP.

bitset<100> b;            // 100 bits, all 0
b.set(5);                 // b[5] = 1
b.reset(5);               // b[5] = 0
b.flip();                 // flip all bits
b.flip(3);                // flip just bit 3
bool v = b.test(3);       // or just b[3]
int c = b.count();        // number of set bits (popcount)
bool any = b.any();       // at least one bit set?
bool none = b.none();     // no bits set?


string s = b.to_string();
unsigned long u = b.to_ulong();

Bitwise operations

bitset<8> a("11001100"), b("10101010");
auto _and = a & b;     // 10001000
auto _or  = a | b;     // 11101110
auto _xor = a ^ b;     // 01100110
auto _shl = a << 2;    // 00110000
auto _not = ~a;        // 00110011

The 64× speedup

Suppose you have an N×N adjacency matrix and want to count triangles. Naive: O(N³). With bitsets:

const int N = 2000;
bitset<N> row[N];


long long tri = 0;
for (int i = 0; i < N; ++i)
    for (int j = i+1; j < N; ++j)
        if (row[i][j])
            tri += (row[i] & row[j]).count();   // 64-wide AND in one CPU op
tri /= 3;
// Effective: O(N³ / 64)

Part 9.2 · pair & tuple

pair — two values bundled together

pair<int, string> p = {42, "hello"};
auto p2 = make_pair(10, "world");
cout << p.first << ' ' << p.second;


// C++17 structured bindings — cleaner
auto [num, txt] = p;
cout << num << ' ' << txt;


// Pairs are comparable lexicographically (.first first, then .second)
vector<pair<int,int>> v;
sort(v.begin(), v.end());

tuple — N values bundled together

tuple<int, string, double> t = {1, "hi", 3.14};
cout << get<0>(t);   // 1
cout << get<1>(t);   // "hi"


// Unpack with structured binding
auto [a, b, c] = t;


// Or with tie() — older syntax
int x; string y; double z;
tie(x, y, z) = t;

Tuples are great when a function needs to return multiple values:

tuple<int, int, int> findMinMaxSum(vector<int>& v) {
    int mn = *min_element(v.begin(), v.end());
    int mx = *max_element(v.begin(), v.end());
    int sm = accumulate(v.begin(), v.end(), 0);
    return {mn, mx, sm};
}
auto [mn, mx, sm] = findMinMaxSum(v);

Part 9.3 · numeric_limits — Type Boundaries

Instead of remembering magic constants like 2147483647, ask the type itself:

#include <limits>


int  iMax = numeric_limits<int>::max();             // 2147483647
int  iMin = numeric_limits<int>::min();             // -2147483648
long long llMax = numeric_limits<long long>::max();
double dInf = numeric_limits<double>::infinity();
double eps  = numeric_limits<double>::epsilon();   // smallest representable difference


// Equivalent old-school constants from <climits>
INT_MAX, INT_MIN, LLONG_MAX, LLONG_MIN, UINT_MAX

Part 9.4 · Custom Hash for unordered_map

Two cases where you need a custom hash:

1. You're storing a custom type (struct, pair) — the default hash doesn't know what to do.
2. You're storing built-in types but on Codeforces, where anti-hash test cases can blow up the default hash.

Hashing pairs

struct PairHash {
    size_t operator()(const pair<int, int>& p) const {
        return hash<long long>()(((long long)p.first << 32) | (unsigned)p.second);
    }
};
unordered_map<pair<int, int>, int, PairHash> m;

The bulletproof contest hash (splitmix64 + random seed)

struct SafeHash {
    static uint64_t splitmix64(uint64_t x) {
        x += 0x9e3779b97f4a7c15ULL;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9ULL;
        x = (x ^ (x >> 27)) * 0x94d049bb133111ebULL;
        return x ^ (x >> 31);
    }
    size_t operator()(uint64_t x) const {
        static const uint64_t SEED =
            chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + SEED);
    }
};
unordered_map<long long, int, SafeHash> safe;

Why it works: splitmix64 spreads bits chaotically, and the per-run random SEED means the contest setter can't precompute a colliding input set.

Part 10 · The Contest-Ready Master Template

Full starter (paste at top of every solution)

#include <bits/stdc++.h>
using namespace std;


// ── shorthand types ───────────────────────────────────────
using ll  = long long;
using ull = unsigned long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using vi  = vector<int>;
using vll = vector<ll>;
using vpii = vector<pii>;
using vvi = vector<vi>;


// ── shorthand macros ──────────────────────────────────────
#define all(x)  (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define sz(x)   (int)(x).size()
#define pb      push_back
#define eb      emplace_back


const int INF = 1e9 + 7;
const ll  LINF = 1e18;


int main() {
    ios_base::sync_with_stdio(false);   // fast I/O
    cin.tie(nullptr);


    // solve here
    return 0;
}

The 20 most-used one-liners

"I need X → use Y" decision table

Part 11 · 15 Worked Problems — The Hero Path

Each problem shows the thinking, the STL choice, the full solution, and the complexity. Read in order — they get progressively harder.

P1 · Count distinct elements

STL: sort + unique  or  set.

int distinct1(vector<int> v) {
    sort(v.begin(), v.end());
    return unique(v.begin(), v.end()) - v.begin();   // O(n log n)
}
int distinct2(vector<int>& v) {
    return set<int>(v.begin(), v.end()).size();      // O(n log n)
}

P2 · Frequency map

Given a list of strings, print each unique word and its count.

unordered_map<string, int> freq;
for (string& w : words) ++freq[w];
for (auto& [w, c] : freq) cout << w << ' ' << c << '\n';
// Time: O(n) average. Use map if you need sorted output.

P3 · Two Sum

Given a[] and target T, find indices i, j with a[i]+a[j]=T.

unordered_map<int, int> seen;          // value → index
for (int i = 0; i < (int)a.size(); ++i) {
    int need = T - a[i];
    if (seen.count(need)) return {seen[need], i};
    seen[a[i]] = i;
}
// Time: O(n) average

P4 · Sliding window maximum

Maximum of every k-sized window. Classic deque application — see Part 1.2.

P5 · Balanced brackets

Already solved in Part 4.1 with stack.

P6 · Next greater element

For each element, find the index of the next strictly greater element on its right.

vector<int> nextGreater(vector<int>& a) {
    int n = a.size();
    vector<int> ans(n, -1);
    stack<int> st;                       // indices, decreasing values
    for (int i = 0; i < n; ++i) {
        while (!st.empty() && a[st.top()] < a[i]) {
            ans[st.top()] = i;
            st.pop();
        }
        st.push(i);
    }
    return ans;
}
// Time: O(n)

P7 · K-th largest element

// Approach 1: nth_element — O(n) average
int kthLargest1(vector<int>& v, int k) {
    nth_element(v.begin(), v.begin() + (k-1), v.end(), greater<int>());
    return v[k-1];
}


// Approach 2: min-heap of size k — O(n log k), uses O(k) memory
int kthLargest2(vector<int>& v, int k) {
    priority_queue<int, vector<int>, greater<int>> pq;
    for (int x : v) {
        pq.push(x);
        if ((int)pq.size() > k) pq.pop();
    }
    return pq.top();
}

P8 · Meeting rooms — minimum rooms needed

Given start/end times of meetings, find the maximum number of overlapping meetings.

int minRooms(vector<pair<int,int>>& mtgs) {
    vector<pair<int,int>> ev;     // (time, +1 for start, -1 for end)
    for (auto& [s, e] : mtgs) {
        ev.push_back({s, +1});
        ev.push_back({e, -1});         // end-events sort first (–1 < +1) → no overcount
    }
    sort(ev.begin(), ev.end());
    int cur = 0, best = 0;
    for (auto& [t, d] : ev) {
        cur += d;
        best = max(best, cur);
    }
    return best;
}
// Time: O(n log n)

P9 · LRU cache concept

Constant-time get/put with eviction of least-recently-used: combine list (for ordering) with unordered_map (for lookup).

class LRUCache {
    int cap;
    list<pair<int,int>> ord;                                  // (key, val), MRU at front
    unordered_map<int, list<pair<int,int>>::iterator> mp;
public:
    LRUCache(int c) : cap(c) {}
    int get(int k) {
        if (!mp.count(k)) return -1;
        ord.splice(ord.begin(), ord, mp[k]);              // O(1) move to front
        return mp[k]->second;
    }
    void put(int k, int v) {
        if (mp.count(k)) ord.erase(mp[k]);
        ord.push_front({k, v});
        mp[k] = ord.begin();
        if ((int)ord.size() > cap) {
            mp.erase(ord.back().first);
            ord.pop_back();
        }
    }
};

P10 · Anagram groups

vector<vector<string>> anagrams(vector<string>& v) {
    map<string, vector<string>> g;
    for (string& w : v) {
        string key = w;
        sort(key.begin(), key.end());
        g[key].push_back(w);
    }
    vector<vector<string>> ans;
    for (auto& [k, group] : g) ans.push_back(group);
    return ans;
}

P11 · Merge K sorted arrays

vector<int> mergeK(vector<vector<int>>& arrs) {
    // (value, which array, index within that array)
    using T = tuple<int, int, int>;
    priority_queue<T, vector<T>, greater<T>> pq;
    for (int i = 0; i < (int)arrs.size(); ++i)
        if (!arrs[i].empty()) pq.push({arrs[i][0], i, 0});
    vector<int> ans;
    while (!pq.empty()) {
        auto [val, ai, idx] = pq.top(); pq.pop();
        ans.push_back(val);
        if (idx + 1 < (int)arrs[ai].size())
            pq.push({arrs[ai][idx+1], ai, idx+1});
    }
    return ans;
}
// Time: O(N log K) where N = total elements, K = number of arrays

P12 · Count inversions (merge-sort based)

long long inversions(vector<int>& a, int l, int r) {
    if (r - l <= 1) return 0;
    int m = (l + r) / 2;
    long long ans = inversions(a, l, m) + inversions(a, m, r);
    vector<int> tmp;
    int i = l, j = m;
    while (i < m && j < r) {
        if (a[i] <= a[j]) tmp.push_back(a[i++]);
        else { tmp.push_back(a[j++]); ans += m - i; }
    }
    while (i < m) tmp.push_back(a[i++]);
    while (j < r) tmp.push_back(a[j++]);
    copy(tmp.begin(), tmp.end(), a.begin() + l);
    return ans;
}
// Time: O(n log n)

P13 · Range frequency queries (offline-style)

For each value, store the sorted positions where it occurs. Query "how many v in [L,R]?" with two binary searches.

unordered_map<int, vector<int>> pos;
for (int i = 0; i < n; ++i) pos[a[i]].push_back(i);


int freqInRange(int v, int L, int R) {
    auto& p = pos[v];
    return upper_bound(p.begin(), p.end(), R)
         - lower_bound(p.begin(), p.end(), L);
}
// Per query: O(log n)

P14 · Subset enumeration with bitset

// Iterate all subsets of {0..n-1}
for (int mask = 0; mask < (1 << n); ++mask) {
    bitset<32> b(mask);
    cout << b << "  popcount=" << b.count() << '\n';
}


// Iterate only the proper subsets of a given mask m (Gosper-style)
for (int sub = m; sub; sub = (sub - 1) & m) { ... }

P15 · BFS with visited (queue + unordered_set)

int shortestPath(unordered_map<int, vector<int>>& g, int src, int tgt) {
    queue<pair<int, int>> q;          // (node, distance)
    unordered_set<int> vis;
    q.push({src, 0});
    vis.insert(src);
    while (!q.empty()) {
        auto [u, d] = q.front(); q.pop();
        if (u == tgt) return d;
        for (int v : g[u]) if (!vis.count(v)) {
            vis.insert(v);
            q.push({v, d+1});
        }
    }
    return -1;
}

Part 12 · Complexity Reference Tables

Sequence containers

Associative containers

Adapters

Algorithms

Part 12.2 · Top 15 Beginner Mistakes

1. Comparing signed loop var to v.size(). size() is unsigned — i < v.size() - 1 wraps around when v is empty. Fix: cast to (int).
2. Using std::lower_bound on a set or map. O(n)! Fix: use the member function s.lower_bound(x) for O(log n).
3. Forgetting remove doesn't actually remove. Fix: the erase–remove idiom: v.erase(remove(...), v.end());
4. map[k] just to check if k exists. Inserts a default value! Fix: use m.count(k) or m.find(k).
5. multiset.erase(value) removes all copies. Fix: ms.erase(ms.find(value)) for one.
6. accumulate(v.begin(), v.end(), 0) overflowing on long longs. Fix: use 0LL (or (long long)0).
7. Iterating and erasing simultaneously. Iterator gets invalidated. Fix: use the return value of erase() or the erase–remove idiom.
8. Storing iterators/references after push_back. Reallocation invalidates them. Fix: reserve up front, or store indices.
9. Using list "because O(1) insert sounds good". Cache misses kill it. Fix: use vector by default.
10. stack.pop() returning the top. It returns void. Fix: read top first, then pop.
11. Using unordered_map<long long,…> on Codeforces without custom hash. Anti-hash test cases blow up to O(n²). Fix: Part 9.4.
12. Comparator returning true for equal elements. Violates strict weak ordering — UB. Fix: use <, never <=.
13. Forgetting cin.tie(nullptr) + sync_with_stdio(false). Slow I/O turns AC into TLE. Fix: always at the top of main.
14. Returning auto from a function with multiple return paths of different types. Compiler error or surprising deduction. Fix: declare an explicit return type.
15. Treating nth_element as a sort. It only places ONE element in its sorted spot. The rest is unordered.