C++ STL Containers Cheat
Sheet for Competitive
Programming
Quick Headers to Include
#include <vector>
#include <deque>
#include <list>
#include <forward_list>
#include <stack>
#include <queue>
#include <priority_queue>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <array>
#include <algorithm> // for sort, binary_search, etc.
1. SEQUENCE CONTAINERS
Vector (Dynamic Array)
// Declaration & Initialization
vector<int> v; // Empty vector
vector<int> v(5); // 5 elements with default value 0
vector<int> v(5, 10); // 5 elements with value 10
vector<int> v = {1, 2, 3, 4, 5}; // Initialize with values
// Access
v[i] // Access by index (no bounds check)
[Link](i) // Access by index (with bounds check)
[Link]() // First element
[Link]() // Last element
// Modification
v.push_back(x) // Add element at end - O(1) amortized
v.pop_back() // Remove last element - O(1)
[Link](it, x) // Insert x at iterator position - O(n)
[Link](it) // Erase element at iterator - O(n)
[Link]() // Remove all elements
// Size & Capacity
[Link]() // Number of elements
[Link]() // Check if empty
[Link](n) // Change size to n
Deque (Double-ended Queue)
// Declaration & Initialization
deque<int> dq;
deque<int> dq = {1, 2, 3, 4, 5};
// All vector operations PLUS:
dq.push_front(x) // Add element at beginning - O(1)
dq.pop_front() // Remove first element - O(1)
// Random access like vector: dq[i], [Link](i)
List (Doubly Linked List)
// Declaration & Initialization
list<int> lst;
list<int> lst = {1, 2, 3, 4, 5};
// Access (NO random access - no [] operator)
[Link]() // First element
[Link]() // Last element
// Modification
lst.push_back(x) // Add at end - O(1)
lst.push_front(x) // Add at beginning - O(1)
lst.pop_back() // Remove from end - O(1)
lst.pop_front() // Remove from beginning - O(1)
[Link](it, x) // Insert at iterator position - O(1)
[Link](it) // Erase at iterator position - O(1)
// Special operations
[Link]() // Sort the list
[Link]() // Remove consecutive duplicates
[Link]() // Reverse the list
Forward List (Singly Linked List)
// Declaration & Initialization
forward_list<int> fl;
forward_list<int> fl = {1, 2, 3, 4, 5};
// Access (NO back(), only front())
[Link]() // First element
// Modification (NO push_back, pop_back)
fl.push_front(x) // Add at beginning - O(1)
fl.pop_front() // Remove from beginning - O(1)
fl.insert_after(it, x) // Insert after iterator - O(1)
fl.erase_after(it) // Erase after iterator - O(1)
// Size (NO size() function)
distance([Link](), [Link]()) // Manual size calculation
Array (Fixed Size)
// Declaration & Initialization
array<int, 5> arr; // Fixed size 5
array<int, 5> arr = {1, 2, 3, 4, 5};
// Same access as vector: arr[i], [Link](i), [Link](), [Link]()
// Size is fixed - no push_back, pop_back, etc.
2. CONTAINER ADAPTERS
Stack (LIFO - Last In First Out)
// Declaration
stack<int> st;
// Operations
[Link](x) // Add element - O(1)
[Link]() // Remove top element - O(1)
[Link]() // Access top element - O(1)
[Link]() // Check if empty
[Link]() // Number of elements
Queue (FIFO - First In First Out)
// Declaration
queue<int> q;
// Operations
[Link](x) // Add element at back - O(1)
[Link]() // Remove front element - O(1)
[Link]() // Access front element - O(1)
[Link]() // Access back element - O(1)
[Link]() // Check if empty
[Link]() // Number of elements
Priority Queue (Max Heap by default)
// Declaration
priority_queue<int> pq; // Max heap (largest at top)
priority_queue<int, vector<int>, greater<int>> pq; // Min heap (smallest at top)
// Operations
[Link](x) // Add element - O(log n)
[Link]() // Remove top element - O(log n)
[Link]() // Access top element - O(1)
[Link]() // Check if empty
[Link]() // Number of elements
3. ASSOCIATIVE CONTAINERS (Sorted,
O(log n) operations)
Set (Unique Sorted Elements)
// Declaration
set<int> s;
set<int> s = {3, 1, 4, 1, 5}; // Stores: {1, 3, 4, 5}
// Operations
[Link](x) // Insert element - O(log n)
[Link](x) // Remove element - O(log n)
[Link](x) // Find element, returns iterator - O(log n)
[Link](x) // Count occurrences (0 or 1) - O(log n)
s.lower_bound(x) // First element >= x - O(log n)
s.upper_bound(x) // First element > x - O(log n)
[Link]() // Check if empty
[Link]() // Number of elements
Multiset (Allows Duplicates)
// Declaration
multiset<int> ms;
multiset<int> ms = {1, 1, 2, 2, 3};
// Same operations as set, but count(x) can return > 1
[Link](x) // Count occurrences - O(log n + count)
Map (Key-Value Pairs, Unique Keys)
// Declaration
map<string, int> m;
map<string, int> m = {{"apple", 1}, {"banana", 2}};
// Operations
m[key] = value // Insert/update - O(log n)
[Link](key) // Access value (throws if key not found) - O(log n)
[Link]({key, value}) // Insert pair - O(log n)
[Link](key) // Remove by key - O(log n)
[Link](key) // Find key, returns iterator - O(log n)
[Link](key) // Check if key exists (0 or 1) - O(log n)
m.lower_bound(key) // First element >= key - O(log n)
m.upper_bound(key) // First element > key - O(log n)
Multimap (Allows Duplicate Keys)
// Declaration
multimap<string, int> mm;
// Same operations as map, but allows duplicate keys
// NO [] operator (since multiple values per key)
[Link](key) // Count occurrences of key - O(log n + count)
4. UNORDERED CONTAINERS (Hash-
based, O(1) average operations)
Unordered Set
// Declaration
unordered_set<int> us;
unordered_set<int> us = {1, 2, 3, 4, 5};
// Operations (similar to set but O(1) average)
[Link](x) // Insert element - O(1) average
[Link](x) // Remove element - O(1) average
[Link](x) // Find element - O(1) average
[Link](x) // Count occurrences (0 or 1) - O(1) average
// NO lower_bound/upper_bound (no ordering)
Unordered Map
// Declaration
unordered_map<string, int> um;
unordered_map<string, int> um = {{"apple", 1}, {"banana", 2}};
// Operations (similar to map but O(1) average)
um[key] = value // Insert/update - O(1) average
[Link](key) // Access value - O(1) average
[Link]({key, value}) // Insert pair - O(1) average
[Link](key) // Remove by key - O(1) average
[Link](key) // Find key - O(1) average
[Link](key) // Check if key exists - O(1) average
// NO lower_bound/upper_bound (no ordering)
5. ITERATORS
Common Iterator Functions
// Getting iterators
[Link]() // Iterator to first element
[Link]() // Iterator to one past last element
[Link]() // Reverse iterator to last element
[Link]() // Reverse iterator to one before first
// Iterator operations
*it // Dereference to get value
it++, ++it // Move to next element
it--, --it // Move to previous element (bidirectional iterators)
it1 == it2 // Compare iterators
it1 != it2 // Compare iterators
// Distance and advance
distance(it1, it2) // Number of elements between iterators
advance(it, n) // Move iterator n positions
next(it, n) // Get iterator n positions ahead
prev(it, n) // Get iterator n positions back
Traversing Containers
// Range-based for loop (C++11+)
for (auto element : container) {
// Process element
}
// Iterator-based loop
for (auto it = [Link](); it != [Link](); ++it) {
// Process *it
}
// For maps/pairs
for (auto& pair : map_container) {
// [Link] = key, [Link] = value
}
6. COMMON ALGORITHMS
Sorting and Searching
#include <algorithm>
// Sorting (requires random access iterator)
sort([Link](), [Link]()); // Ascending order
sort([Link](), [Link](), greater<int>()); // Descending order
// Binary Search (requires sorted range)
binary_search([Link](), [Link](), x); // Returns true/false
lower_bound([Link](), [Link](), x); // Iterator to first >= x
upper_bound([Link](), [Link](), x); // Iterator to first > x
// Finding
find([Link](), [Link](), x); // Find first occurrence
count([Link](), [Link](), x); // Count occurrences
// Min/Max
*min_element([Link](), [Link]()); // Minimum element
*max_element([Link](), [Link]()); // Maximum element
// Reverse
reverse([Link](), [Link]()); // Reverse container
// Unique (requires sorted range)
[Link](unique([Link](), [Link]()), [Link]()); // Remove consecutive duplicates
7. COMPETITIVE PROGRAMMING TIPS
Fast I/O
ios_base::sync_with_stdio(false);
[Link](NULL);
Useful Typedefs
typedef long long ll;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef pair<int, int> pii;
Common Patterns
// Check if element exists
if ([Link](x) != [Link]()) { /* exists */ }
if ([Link](key)) { /* key exists */ }
// Iterate through map
for (auto& p : m) {
int key = [Link];
int value = [Link];
}
// Priority queue with custom comparator
priority_queue<pii, vector<pii>, greater<pii>> pq; // Min heap of pairs
// Set/map with custom comparator
set<int, greater<int>> s; // Descending order
When to Use Which Container?
Vector: Default choice, random access needed Deque: Need insertion/deletion at both ends List: Frequent
insertion/deletion in middle Set/Map: Need sorted unique elements/keys Unordered_set/map: Fast lookup, don't need
ordering Priority_queue: Need to process elements by priority Stack: LIFO operations (DFS, expression evaluation)
Queue: FIFO operations (BFS, level order traversal)
Time Complexities Quick Reference
Vector: Access O(1), Insert/Delete at end O(1), elsewhere O(n)
Deque: Access O(1), Insert/Delete at ends O(1), elsewhere O(n)
List: Access O(n), Insert/Delete anywhere O(1)
Set/Map: All operations O(log n)
Unordered_set/map: All operations O(1) average, O(n) worst case
Priority_queue: Push/Pop O(log n), Top O(1)
