Appendix A: C++ Quick Reference

This appendix is your cheat sheet. Keep it handy during practice sessions. Everything here has been covered in the book; this is the condensed reference form.

A.1 The Competition Template

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

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    // freopen("problem.in", "r", stdin);   // uncomment for file I/O (use actual problem name)
    // freopen("problem.out", "w", stdout);  // uncomment for file I/O

    // Your code here

    return 0;
}

A.2 Common Data Types

Safe maximum values:

INT_MAX   = 2,147,483,647   ≈ 2.1 × 10^9
LLONG_MAX = 9,223,372,036,854,775,807 ≈ 9.2 × 10^18

A.3 STL Containers — Operations Cheat Sheet

vector<T>

vector<int> v;              // empty
vector<int> v(n, 0);        // n zeros
vector<int> v = {1,2,3};    // from list

v.push_back(x);     // add to end — O(1) amortized
v.pop_back();       // remove last — O(1)
v[i]                // access index i — O(1)
v.front()           // first element
v.back()            // last element
v.size()            // number of elements
v.empty()           // true if empty
v.clear()           // remove all
v.resize(k, val)    // resize to k, fill new with val
v.insert(v.begin()+i, x)  // insert at index i — O(n)
v.erase(v.begin()+i)      // remove at index i — O(n)

pair<A,B>

pair<int,int> p = {3, 5};
p.first             // 3
p.second            // 5
make_pair(a, b)     // create pair
// Comparison: by .first, then .second

map<K,V>

map<string,int> m;
m[key] = val;           // insert/update — O(log n)
m[key]                  // access (creates if absent!) — O(log n)
m.find(key)             // iterator; .end() if not found — O(log n)
m.count(key)            // 0 or 1 — O(log n)
m.erase(key)            // remove — O(log n)
m.size()                // number of entries
for (auto &[k,v] : m)   // iterate in sorted key order

set<T>

set<int> s;
s.insert(x)             // add — O(log n)
s.erase(x)              // remove all x — O(log n)
s.count(x)              // 0 or 1 — O(log n)
s.find(x)               // iterator — O(log n)
s.lower_bound(x)        // first element >= x
s.upper_bound(x)        // first element > x
*s.begin()              // minimum element
*s.rbegin()             // maximum element

stack<T>

stack<int> st;
st.push(x)      // push — O(1)
st.pop()        // pop (no return!) — O(1)
st.top()        // peek at top — O(1)
st.empty()      // true if empty
st.size()       // count

queue<T>

queue<int> q;
q.push(x)       // enqueue — O(1)
q.pop()         // dequeue (no return!) — O(1)
q.front()       // front element — O(1)
q.back()        // back element — O(1)
q.empty()
q.size()

priority_queue<T> (max-heap)

priority_queue<int> pq;                               // max-heap
priority_queue<int, vector<int>, greater<int>> pq2;   // min-heap

pq.push(x)      // insert — O(log n)
pq.pop()        // remove top — O(log n)
pq.top()        // view top (max) — O(1)
pq.empty()
pq.size()

unordered_map<K,V> / unordered_set<T>

Same interface as map/set, but O(1) average (no ordered iteration).

A.4 STL Algorithms Cheat Sheet

// All assume #include <bits/stdc++.h>

// SORT
sort(v.begin(), v.end());                          // ascending
sort(v.begin(), v.end(), greater<int>());          // descending
sort(v.begin(), v.end(), [](int a, int b){...});   // custom

// BINARY SEARCH (requires sorted container)
binary_search(v.begin(), v.end(), x)               // bool: exists?
lower_bound(v.begin(), v.end(), x)                 // iterator to first >= x
upper_bound(v.begin(), v.end(), x)                 // iterator to first > x

// MIN/MAX
min(a, b)               // minimum of two
max(a, b)               // maximum of two
min({a, b, c})          // minimum of many (C++11)
*min_element(v.begin(), v.end())   // min of container
*max_element(v.begin(), v.end())   // max of container

// ACCUMULATE
accumulate(v.begin(), v.end(), 0LL)   // sum (use 0LL for long long)

// FILL
fill(v.begin(), v.end(), x)           // fill all with x
memset(arr, 0, sizeof(arr))           // zero a C-array (fast)

// REVERSE
reverse(v.begin(), v.end())           // reverse in place

// COUNT
count(v.begin(), v.end(), x)          // count occurrences of x

// UNIQUE (removes consecutive duplicates — sort first!)
auto it = unique(v.begin(), v.end());
v.erase(it, v.end());

// SWAP
swap(a, b)              // swap two values

// PERMUTATION (useful for brute force)
sort(v.begin(), v.end());
do {
    // process current permutation
} while (next_permutation(v.begin(), v.end()));

// GCD / LCM (C++17)
gcd(a, b)                           // GCD — std::gcd from <numeric>
lcm(a, b)                           // LCM — std::lcm from <numeric>
// Legacy (pre-C++17): __gcd(a, b)  // still works but prefer std::gcd

A.5 Time Complexity Reference Table

Visual: Complexity vs N Reference

The color-coded table above gives an at-a-glance feasibility check. When reading a problem, find N in the columns and your algorithm's complexity in the rows to see if it will pass within 1 second.

A.6 Common Pitfalls

Integer Overflow

// WRONG
int a = 1e9, b = 1e9;
int product = a * b;  // overflow!

// CORRECT
long long product = (long long)a * b;

// WRONG
int n = 1e5;
int arr[n * n];  // n*n = 10^10, way too large

// Check: if any intermediate value might exceed 2 × 10^9, use long long

Off-by-One

// WRONG: accesses arr[n]
for (int i = 0; i <= n; i++) cout << arr[i];

// CORRECT
for (int i = 0; i < n; i++) cout << arr[i];   // 0-indexed
for (int i = 1; i <= n; i++) cout << arr[i];  // 1-indexed

// Prefix sum: P[i] = sum of first i elements
// Query sum from L to R (1-indexed): P[R] - P[L-1]
// NOT P[R] - P[L]  ← off by one!

Modifying Container While Iterating

// WRONG
for (auto it = s.begin(); it != s.end(); ++it) {
    if (*it % 2 == 0) s.erase(it);  // iterator invalidated!
}

// CORRECT
set<int> toErase;
for (int x : s) if (x % 2 == 0) toErase.insert(x);
for (int x : toErase) s.erase(x);

map Creating Entries on Access

map<string,int> m;
if (m["missing_key"])  // creates "missing_key" with value 0!

// CORRECT: check first
if (m.count("missing_key") && m["missing_key"])  // safe
// Or:
auto it = m.find("missing_key");
if (it != m.end() && it->second) { ... }

Double Comparison

double a = 0.1 + 0.2;
if (a == 0.3)  // might be false due to floating point!

// CORRECT: use epsilon comparison
const double EPS = 1e-9;
if (abs(a - 0.3) < EPS) { ... }

Stack Overflow from Deep Recursion

// DFS on large graphs can cause stack overflow
// For trees with N = 10^5 nodes in a line (like a chain), recursion depth = 10^5
// Fix: increase stack size, or use iterative DFS

// On Linux/Mac, increase stack:
// ulimit -s unlimited
// Or compile with: g++ -DLOCAL ... and set stack size manually

A.7 Useful #define and typedef

// Common shortcuts (personal taste — don't overdo it)
typedef long long ll;
typedef pair<int,int> pii;
typedef vector<int> vi;

#define pb push_back
#define all(v) (v).begin(), (v).end()
#define sz(v) ((int)(v).size())

// Example usage:
ll x = 1e18;
pii p = {3, 5};
vi v = {1, 2, 3};
sort(all(v));

A.8 C++17 Useful Features

// Structured bindings — unpack pairs/tuples cleanly
auto [x, y] = make_pair(3, 5);
for (auto [key, val] : mymap) { ... }

// If with initializer
if (auto it = m.find(key); it != m.end()) {
    // use it->second
}

// __gcd and gcd
int g = gcd(12, 8);   // C++17: use std::gcd from <numeric>
int l = lcm(4, 6);    // C++17: use std::lcm from <numeric>

// Compile with: g++ -std=c++17 -O2 -o sol sol.cpp