A function should ask for the MINIMUM it needs.
Fewer dependencies = easier to change.
Fowler's advice:
"Most of the time you should ignore performance during refactoring. Finish refactoring first, then do performance tuning afterwards."
"Making the implicit explicit"
Instead of memorizing rules:
Okay, here is the C++ Competitive Programming Cheatsheet again, presented in Markdown format. You can copy this content and paste it into a document editor (like Google Docs, MS Word, or an online Markdown editor) to format it as you like and then save or print it as a PDF.
Your essential quick reference for common methods, data structures, and algorithms.
Header: <iostream>, <iomanip> (for precision)
Fast I/O Setup (Recommended for speed):
std::ios_base::sync_with_stdio(false); // Unties C++ streams from C stdio
std::cin.tie(NULL); // Unties cin from cout (prevents flushing cout before cin reads)
// Use '\n' instead of std::endl for newlines (endl flushes, which can be slow)
Basic I/O: std::cin >> var;, std::cout << var << '\n';
Floating-Point Precision:
std::cout << std::fixed << std::setprecision(X) << float_var << '\n'; // X decimal places
<string>, <cctype>)Declaration/Initialization: std::string s = "hello";
Length: s.length(), s.size()
Access: s[i] (character at index i)
Substring: s.substr(pos, len) (e.g., s.substr(1, 3) for "ell" from "hello")
Find Substring/Char: s.find(target)
Returns std::string::npos if not found.
Returns starting index if found.
Example: if (s.find("abc") != std::string::npos)
Concatenation: s += other_s; or s.append(other_s);
String to Number:
std::stoi(str), std::stoll(str) (to int, long long)
std::stod(str) (to double)
Number to String: std::to_string(num)
Character Properties (<cctype>):
isalpha(char c): true if alphabetic
isdigit(char c): true if digit
islower(char c), isupper(char c): true if lowercase/uppercase
isspace(char c): true if whitespace
tolower(char c), toupper(char c): convert case
<vector>) - Dynamic ArraysDeclaration:
std::vector<int> v;
std::vector<int> v(size); (size, elements default-initialized)
std::vector<int> v(size, value); (size, all elements value)
Add/Remove: v.push_back(element);, v.pop_back(); (removes last)
Size/Empty: v.size();, v.empty();
Access: v[i];
Clear: v.clear(); (removes all elements)
Iterators: v.begin();, v.end(); (points one past the last element)
<algorithm>, <numeric>) - Essential for Arrays/VectorsSorting: std::sort(v.begin(), v.end());
Reverse sort: std::sort(v.begin(), v.end(), std::greater<int>());
Min/Max Values: std::min(a, b);, std::max(a, b);
Min/Max Element in Range: *std::min_element(v.begin(), v.end()); (returns iterator, dereference for value)
Reverse: std::reverse(v.begin(), v.end());
Sum (<numeric>): std::accumulate(v.begin(), v.end(), 0LL); (0LL for long long sum)
Find Value: std::find(v.begin(), v.end(), value); (returns iterator, v.end() if not found)
Binary Search (on sorted range):
std::binary_search(v.begin(), v.end(), value); (returns bool)
std::lower_bound(v.begin(), v.end(), value); (iterator to first element ! < value)
std::upper_bound(v.begin(), v.end(), value); (iterator to first element > value)
Count occurrences: upper_bound(v.begin(), v.end(), val) - lower_bound(v.begin(), v.end(), val);
Remove Duplicates (from sorted range):
v.erase(std::unique(v.begin(), v.end()), v.end());
std::pair<T1, T2> (<utility>): Stores two values. p.first, p.second.
Example: std::pair<int, int> coords = {10, 20};
std::map<Key, Value> (<map>) - Ordered Key-Value:
map_name[key] = value;
map_name.count(key); (returns 0 or 1)
map_name.find(key) != map_name.end();
std::set<T> (<set>) - Ordered Unique Elements:
set_name.insert(element);
set_name.count(element); (returns 0 or 1)
std::unordered_map<Key, Value> (<unordered_map>) - Unordered Key-Value (Hash Map):
Faster average case (O(1)) than map (O(log N)). Use when order isn't needed.
umap_name[key] = value;
umap_name.count(key);
std::unordered_set<T> (<unordered_set>) - Unordered Unique Elements (Hash Set):
Faster average case (O(1)) than set (O(log N)). Use when order isn't needed.
uset_name.insert(element);
uset_name.count(element);
std::queue<T> (<queue>) - FIFO:
q.push(element);, q.front();, q.pop();
q.empty();, q.size();
std::priority_queue<T> (<queue>) - Max Heap (Default):
pq.push(element);, pq.top();, pq.pop();
Min-Heap: std::priority_queue<int, std::vector<int>, std::greater<int>> min_pq;
std::stack<T> (<stack>) - LIFO:
s.push(element);, s.top();, s.pop();
s.empty();, s.size();
std::deque<T> (<deque>) - Double-Ended Queue:
Efficient insertions/deletions at both ends: dq.push_front(), dq.push_back(), etc.
<cmath>, <numeric>)Absolute Value: std::abs(num); (for int, float, double, etc.)
Square Root: std::sqrt(num);
Power: std::pow(base, exponent);
Rounding: std::floor(x);, std::ceil(x);, std::round(x);
GCD/LCM (<numeric>, C++17+): std::gcd(a, b);, std::lcm(a, b);
Pre-computation: Calculate fixed data/tables once at the start of the program (outside test case loop).
Two Pointers: Efficiently iterate through arrays/strings, typically sorted (e.g., finding pairs, merging).
Sliding Window: Optimal for finding max/min sum/properties of a fixed-size or variable-size contiguous subarray/substring.
Binary Search:
On a sorted array/vector to find an element or its position.
On the answer space if the property you're looking for is monotonic (e.g., "is it possible to achieve X?").
Recursion / Backtracking: For exploring all possible solutions (e.g., permutations, combinations, subsets, N-Queens).
Dynamic Programming (DP): Solving problems by breaking them into smaller, overlapping subproblems and storing results to avoid redundant calculations. Requires careful definition of states and transitions.
Greedy Algorithms: Making the locally optimal choice at each step hoping it leads to a global optimum. (Prove correctness or use only when clear).
Graph Traversal:
BFS (Breadth-First Search): Uses a std::queue. Good for shortest paths on unweighted graphs, level-order traversal.
DFS (Depth-First Search): Uses recursion or a std::stack. Good for connectivity, cycle detection, topological sort.
Disjoint Set Union (DSU) / Union-Find: For managing sets of elements partitioned into disjoint subsets (e.g., connected components).
Prefix Sums: Pre-calculate sums of prefixes of an array to answer range sum queries quickly.
Bit Manipulation: Using bitwise operators (&, |, ^, ~, <<, >>) for efficient checks, toggles, or set operations (e.g., (1 << i) for 2i).
Read Problem Carefully: Understand constraints, edge cases, input/output formats, time/memory limits.
const Correctness: Use const for variables/parameters that won't change.
Type Aliases: using ll = long long;, using ld = long double; for brevity and clarity.
Function Decomposition: Break down large problems into smaller, testable functions.
Test Edge Cases: Consider empty inputs, single elements, max/min values, identical values.
Modular Arithmetic: For problems involving large numbers and modulo operations. Remember (a + b) % M = ((a % M) + (b % M)) % M; etc.
Integer Overflow: Be mindful of int limits (2times109) and use long long for larger sums/products.
Floating-Point Precision: Be careful with double comparisons (abs(a - b) < EPSILON).