C++ Cheatsheet

 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.

---

C++ Competitive Programming Cheatsheet

Your essential quick reference for common methods, data structures, and algorithms.

---

I. Standard Library Essentials

A. Input/Output (I/O)

• Header: <iostream>, <iomanip> (for precision)

• Fast I/O Setup (Recommended for speed):

  C++

  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:

  C++

  std::cout << std::fixed << std::setprecision(X) << float_var << '\n'; // X decimal places
  

B. Strings (<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

C. Vectors (<vector>) - Dynamic Arrays

• Declaration:

  • 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)

D. Algorithms (<algorithm>, <numeric>) - Essential for Arrays/Vectors

• Sorting: 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());

E. Common Data Structures

• 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.

F. Math (<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);

---

II. Common Algorithm Patterns & Techniques

• 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).

---

III. Good Practices & Habits

• 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).

---