C++ Cheat Sheet For Competitive Programming

MUAZHAN

7 min read Jul 01, 2024

C++ Cheat Sheet for Competitive Programming

This cheat sheet provides a concise overview of essential C++ concepts and techniques used in competitive programming.

Data Structures

Arrays:

Declaration: int arr[100]; // Declares an array arr of 100 integers.
Accessing Elements: arr[i] // Accesses the element at index i.
Iteration: for (int i = 0; i < n; i++) { ... } // Iterates over the array.

Vectors:

Declaration: vector<int> v; // Declares an empty vector of integers.
Adding Elements: v.push_back(x); // Adds element x to the end.
Accessing Elements: v[i] // Accesses the element at index i.
Size: v.size(); // Returns the size of the vector.
Iteration: for (int i = 0; i < v.size(); i++) { ... } // Iterates over the vector.

Linked Lists:

Declaration: list<int> l; // Declares an empty list of integers.
Adding Elements: l.push_front(x); // Adds element x to the front.
Adding Elements: l.push_back(x); // Adds element x to the back.
Deleting Elements: l.pop_front(); // Deletes the first element.
Deleting Elements: l.pop_back(); // Deletes the last element.
Iteration: for (auto it = l.begin(); it != l.end(); it++) { ... } // Iterates over the list.

Stacks:

Declaration: stack<int> s; // Declares an empty stack of integers.
Adding Elements: s.push(x); // Pushes element x onto the stack.
Removing Elements: s.pop(); // Removes the top element.
Top Element: s.top(); // Returns the top element without removing it.
Empty Check: s.empty(); // Returns true if the stack is empty.

Queues:

Declaration: queue<int> q; // Declares an empty queue of integers.
Adding Elements: q.push(x); // Adds element x to the back.
Removing Elements: q.pop(); // Removes the front element.
Front Element: q.front(); // Returns the front element without removing it.
Empty Check: q.empty(); // Returns true if the queue is empty.

Sets:

Declaration: set<int> s; // Declares an empty set of integers (sorted).
Adding Elements: s.insert(x); // Adds element x (only if it's not already present).
Deleting Elements: s.erase(x); // Deletes element x.
Membership Check: s.count(x); // Returns 1 if x is present, otherwise 0.
Iteration: for (auto it = s.begin(); it != s.end(); it++) { ... } // Iterates over the set.

Maps:

Declaration: map<string, int> m; // Declares an empty map with keys of type string and values of type integer.
Adding Elements: m["key"] = value; // Adds a key-value pair.
Accessing Elements: m["key"] // Returns the value associated with the key.
Deleting Elements: m.erase("key"); // Deletes the key-value pair associated with the key.
Iteration: for (auto it = m.begin(); it != m.end(); it++) { ... } // Iterates over the map.

Algorithms

Sorting:

sort(begin, end): Sorts the elements in the range [begin, end).
stable_sort(begin, end): Sorts the elements while preserving the relative order of equal elements.

Searching:

binary_search(begin, end, value): Returns true if the value is present in the sorted range [begin, end).
lower_bound(begin, end, value): Returns an iterator to the first element not less than the value.
upper_bound(begin, end, value): Returns an iterator to the first element greater than the value.

Other Useful Algorithms:

min(a, b): Returns the minimum of a and b.
max(a, b): Returns the maximum of a and b.
abs(x): Returns the absolute value of x.
pow(x, y): Returns x raised to the power of y.
sqrt(x): Returns the square root of x.
gcd(a, b): Returns the greatest common divisor of a and b.
lcm(a, b): Returns the least common multiple of a and b.

Input/Output

Input:

cin >> var;: Reads a value from standard input and stores it in var.
getline(cin, str);: Reads a line of text from standard input and stores it in str.

Output:

cout << var;: Prints the value of var to standard output.
endl;: Inserts a newline character to standard output.

Common Techniques

#define Macros: Define constants or short functions.
#include <algorithm>: Provides access to standard algorithms.
#include <iostream>: Provides access to input and output streams.
#include <vector>: Provides access to the vector data structure.
#include <set>: Provides access to the set data structure.
#include <map>: Provides access to the map data structure.
#include <queue>: Provides access to the queue data structure.
#include <stack>: Provides access to the stack data structure.

Example

#include 
#include 
#include 

using namespace std;

int main() {
  int n;
  cin >> n;

  vector v(n);
  for (int i = 0; i < n; i++) {
    cin >> v[i];
  }

  sort(v.begin(), v.end());

  for (int i = 0; i < n; i++) {
    cout << v[i] << " ";
  }
  cout << endl;

  return 0;
}

This code reads a sequence of integers, sorts them using sort, and then prints the sorted sequence.