STL for Competitive Programming

Why STL is Essential

The C++ STL provides battle-tested, optimized implementations of common data structures and algorithms. Using STL effectively can be the difference between solving a problem in 5 minutes vs 30 minutes.

The CP Mindset: Don’t implement what STL provides. Know what’s available, know its complexity, and use it without hesitation.

Containers Cheat Sheet

When to Use What

Need	Container	Operations
Dynamic array	`vector<T>`	O(1) push_back, O(1) access
LIFO stack	`stack<T>`	O(1) push, pop, top
FIFO queue	`queue<T>`	O(1) push, pop, front
Sorted unique keys	`set<T>`	O(log n) insert, find, erase
Sorted with duplicates	`multiset<T>`	O(log n) operations
Key-value (sorted)	`map<K,V>`	O(log n) operations
Key-value (fast)	`unordered_map<K,V>`	O(1) average
Min/max element	`priority_queue<T>`	O(log n) push, O(1) top
Double-ended	`deque<T>`	O(1) front/back operations

Vector: Your Default Container

Essential Operations

vector<int> v;                    // Empty vector
vector<int> v(n);                 // n elements, default initialized (0)
vector<int> v(n, val);            // n elements, all = val
vector<int> v = {1, 2, 3};        // Initializer list
vector<vector<int>> v(n, vector<int>(m, 0));  // n x m 2D vector

// Adding elements
v.push_back(x);                   // Add to end: O(1) amortized
v.emplace_back(x);                // More efficient for objects
v.pop_back();                     // Remove last: O(1)

// Access
v[i];                             // Access by index: O(1) (no bounds check)
v.at(i);                          // Access with bounds check
v.front();                        // First element
v.back();                         // Last element

// Size
v.size();                         // Number of elements
v.empty();                        // Check if empty
v.clear();                        // Remove all elements

// Iteration
for (int x : v) { }               // Range-based for
for (int& x : v) { x++; }         // Modify elements
for (int i = 0; i < v.size(); i++) { }  // Index-based

Vector Patterns

// Read n integers
int n; cin >> n;
vector<int> a(n);
for (int& x : a) cin >> x;

// Reverse
reverse(a.begin(), a.end());
// or
reverse(all(a));  // Using macro

// Sort
sort(all(a));                     // Ascending
sort(all(a), greater<int>());     // Descending

// Remove duplicates from sorted vector
a.erase(unique(all(a)), a.end());

// Find element
auto it = find(all(a), x);
if (it != a.end()) {
    int idx = it - a.begin();
}

// Binary search (on sorted vector)
bool found = binary_search(all(a), x);
auto it = lower_bound(all(a), x);  // First >= x
auto it = upper_bound(all(a), x);  // First > x

Set and Map: Sorted Containers

Set Operations

set<int> s;

// Insert: O(log n)
s.insert(5);
s.insert(3);
s.insert(5);  // Ignored, already exists
// s = {3, 5}

// Check existence: O(log n)
if (s.count(5)) { }       // Returns 0 or 1
if (s.find(5) != s.end()) { }

// Erase: O(log n)
s.erase(5);               // By value
s.erase(s.begin());       // By iterator

// Bounds (powerful!)
auto it = s.lower_bound(4);  // First >= 4, returns iterator to 5
auto it = s.upper_bound(4);  // First > 4, returns iterator to 5

// Min/Max
*s.begin();               // Minimum
*s.rbegin();              // Maximum (or *prev(s.end()))

// Iterate (sorted order)
for (int x : s) { }

Map Operations

map<string, int> m;

// Insert/Update: O(log n)
m["apple"] = 5;
m["banana"]++;            // Inserts with value 0, then increments

// Access: O(log n)
cout << m["apple"];       // 5
cout << m["cherry"];      // Creates entry with value 0!

// Check existence first
if (m.count("apple")) { }
if (m.find("apple") != m.end()) { }

// Safe access
auto it = m.find("apple");
if (it != m.end()) {
    cout << it->second;  // Value
}

// Iterate (sorted by key)
for (auto& [key, value] : m) {
    cout << key << ": " << value << '\n';
}

// Erase
m.erase("apple");

Multiset (Allows Duplicates)

multiset<int> ms;
ms.insert(5);
ms.insert(5);
ms.insert(3);
// ms = {3, 5, 5}

ms.count(5);              // Returns 2
ms.erase(5);              // Erases ALL 5s!
ms.erase(ms.find(5));     // Erases ONE 5

Priority Queue: Heap

Basic Usage

// Max heap (default)
priority_queue<int> pq;
pq.push(3);
pq.push(1);
pq.push(4);
pq.top();   // 4 (maximum)
pq.pop();   // Removes 4

// Min heap
priority_queue<int, vector<int>, greater<int>> minPq;
minPq.push(3);
minPq.push(1);
minPq.push(4);
minPq.top();  // 1 (minimum)

// With pairs (compares by first, then second)
priority_queue<pair<int, int>> pq;
pq.push({5, 1});
pq.push({3, 2});
pq.top();  // {5, 1}

Pattern: Dijkstra’s Algorithm

// Min heap for shortest paths
priority_queue<pii, vector<pii>, greater<pii>> pq;
pq.push({0, start});  // {distance, node}

while (!pq.empty()) {
    auto [d, u] = pq.top();
    pq.pop();
    
    if (d > dist[u]) continue;  // Already processed
    
    for (auto [v, w] : adj[u]) {
        if (dist[u] + w < dist[v]) {
            dist[v] = dist[u] + w;
            pq.push({dist[v], v});
        }
    }
}

Algorithms Header

Sorting

#include <algorithm>

vector<int> a = {3, 1, 4, 1, 5};

// Sort ascending
sort(all(a));  // {1, 1, 3, 4, 5}

// Sort descending
sort(all(a), greater<int>());  // {5, 4, 3, 1, 1}

// Custom comparator
sort(all(a), [](int x, int y) {
    return x > y;  // Descending
});

// Sort pairs by second element
vector<pair<int, int>> v = {{1, 3}, {2, 1}, {3, 2}};
sort(all(v), [](auto& a, auto& b) {
    return a.second < b.second;
});
// v = {{2, 1}, {3, 2}, {1, 3}}

// Partial sort (first k elements)
partial_sort(a.begin(), a.begin() + k, a.end());

// Nth element (find kth smallest, O(n) average)
nth_element(a.begin(), a.begin() + k, a.end());
// a[k] is now the (k+1)th smallest

Binary Search

vector<int> a = {1, 2, 3, 4, 5};  // Must be sorted!

// Check if exists
binary_search(all(a), 3);  // true

// Lower bound: first >= target
auto it = lower_bound(all(a), 3);  // Points to 3
int idx = it - a.begin();  // Index 2

// Upper bound: first > target
auto it = upper_bound(all(a), 3);  // Points to 4
int idx = it - a.begin();  // Index 3

// Count occurrences
int count = upper_bound(all(a), x) - lower_bound(all(a), x);

// Find range of equal elements
auto [lo, hi] = equal_range(all(a), 3);

Other Useful Algorithms

// Min/Max
*min_element(all(a));           // Minimum value
*max_element(all(a));           // Maximum value
auto [mn, mx] = minmax_element(all(a));

// Sum
accumulate(all(a), 0);          // Sum (start from 0)
accumulate(all(a), 0LL);        // Use long long for large sums

// Count
count(all(a), x);               // Count occurrences of x
count_if(all(a), [](int x) { return x > 0; });

// Reverse
reverse(all(a));

// Rotate
rotate(a.begin(), a.begin() + k, a.end());  // Left rotate by k

// Unique (remove consecutive duplicates)
a.erase(unique(all(a)), a.end());  // Works on sorted array

// Next/Prev permutation
do {
    // Process current permutation
} while (next_permutation(all(a)));

// Fill
fill(all(a), 0);
fill(arr, arr + n, 0);  // For C-style arrays

// GCD/LCM (C++17)
__gcd(a, b);           // GCD
gcd(a, b);             // C++17
lcm(a, b);             // C++17

String Operations

string s = "hello";

// Basics
s.size();                // or s.length()
s.empty();
s[0];                    // 'h'
s.front();               // 'h'
s.back();                // 'o'

// Modification
s.push_back('!');        // "hello!"
s.pop_back();            // "hello"
s += " world";           // "hello world"

// Substring
s.substr(0, 5);          // "hello" (pos, len)
s.substr(6);             // "world" (pos to end)

// Find
s.find("world");         // 6 (position, or string::npos if not found)
s.find('o');             // 4

// Compare
s < "hi";                // true (lexicographic)
s == "hello world";      // true

// Convert
to_string(123);          // "123"
stoi("123");             // 123
stoll("123456789012");   // 123456789012LL

// Reverse
reverse(all(s));

Pattern Recognition: Choosing the Right Container

Need Fast Lookup?

By index → vector
By key → unordered_map (O(1)) or map (O(log n))
Check existence → set or unordered_set

Need Ordering?

Sorted iteration → set, map
Quick min/max → priority_queue
Find closest → lower_bound, upper_bound

Need Frequency?

Count occurrences → map<T, int> or unordered_map<T, int>
With removal → multiset (careful with erase!)

Need FIFO/LIFO?

Stack → stack or vector
Queue → queue or deque
Both ends → deque

Common Pitfalls

Pitfall 1: Iterator Invalidation

// WRONG: Erasing while iterating
for (auto it = s.begin(); it != s.end(); it++) {
    if (*it == target) {
        s.erase(it);  // Iterator invalidated!
    }
}

// CORRECT
for (auto it = s.begin(); it != s.end(); ) {
    if (*it == target) {
        it = s.erase(it);  // erase returns next valid iterator
    } else {
        it++;
    }
}

Pitfall 2: Modifying Map While Iterating

// WRONG
for (auto& [k, v] : m) {
    if (v == 0) m.erase(k);  // Undefined behavior
}

// CORRECT: Collect keys first
vector<int> toRemove;
for (auto& [k, v] : m) {
    if (v == 0) toRemove.push_back(k);
}
for (int k : toRemove) m.erase(k);

Pitfall 3: Using [] on Non-Existent Key

map<int, int> m;
if (m[5] > 0) { }  // Creates m[5] = 0!

// CORRECT
if (m.count(5) && m[5] > 0) { }

Key Takeaways

Know Your Complexities

vector O(1) access, set/map O(log n), unordered_* O(1) average.

Use STL Algorithms

sort, lower_bound, unique, accumulate save time and bugs.

Default to Vector

Unless you need specific properties, vector is usually the best choice.

Careful with Erase

Erasing invalidates iterators. Know the patterns.

Next Up

Chapter 4: Prefix Sum & Difference Arrays

Answer range queries in O(1) and apply updates efficiently with these fundamental techniques.

​STL for Competitive Programming

​Why STL is Essential

​Containers Cheat Sheet

​When to Use What

​Vector: Your Default Container

​Essential Operations

​Vector Patterns

​Set and Map: Sorted Containers

​Set Operations

​Map Operations

​Multiset (Allows Duplicates)

​Priority Queue: Heap

​Basic Usage

​Pattern: Dijkstra’s Algorithm

​Algorithms Header

​Sorting

​Binary Search

​Other Useful Algorithms

​String Operations

​Pattern Recognition: Choosing the Right Container

Need Fast Lookup?

Need Ordering?

Need Frequency?

Need FIFO/LIFO?

​Common Pitfalls

​Pitfall 1: Iterator Invalidation

​Pitfall 2: Modifying Map While Iterating

​Pitfall 3: Using [] on Non-Existent Key

​Key Takeaways

Know Your Complexities

Use STL Algorithms

Default to Vector

Careful with Erase

​Next Up

Chapter 4: Prefix Sum & Difference Arrays

STL for Competitive Programming

Why STL is Essential

Containers Cheat Sheet

When to Use What

Vector: Your Default Container

Essential Operations

Vector Patterns

Set and Map: Sorted Containers

Set Operations

Map Operations

Multiset (Allows Duplicates)

Priority Queue: Heap

Basic Usage

Pattern: Dijkstra’s Algorithm

Algorithms Header

Sorting

Binary Search

Other Useful Algorithms

String Operations

Pattern Recognition: Choosing the Right Container

Common Pitfalls

Pitfall 1: Iterator Invalidation

Pitfall 2: Modifying Map While Iterating

Pitfall 3: Using [] on Non-Existent Key

Key Takeaways

Next Up