> ## Documentation Index
> Fetch the complete documentation index at: https://resources.devweekends.com/llms.txt
> Use this file to discover all available pages before exploring further.

# STL for Competitive Programming

> Master the C++ Standard Template Library—the competitive programmer's essential toolkit

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

<Note>
  **The CP Mindset**: Don't implement what STL provides. Know what's available, know its complexity, and use it without hesitation.
</Note>

***

## 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

```cpp theme={null}
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

```cpp theme={null}
// 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

```cpp theme={null}
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

```cpp theme={null}
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)

```cpp theme={null}
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

```cpp theme={null}
// 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

```cpp theme={null}
// 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

```cpp theme={null}
#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

```cpp theme={null}
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

```cpp theme={null}
// 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

```cpp theme={null}
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

<CardGroup cols={2}>
  <Card title="Need Fast Lookup?" icon="magnifying-glass">
    * By index → `vector`
    * By key → `unordered_map` (O(1)) or `map` (O(log n))
    * Check existence → `set` or `unordered_set`
  </Card>

  <Card title="Need Ordering?" icon="sort">
    * Sorted iteration → `set`, `map`
    * Quick min/max → `priority_queue`
    * Find closest → `lower_bound`, `upper_bound`
  </Card>

  <Card title="Need Frequency?" icon="hashtag">
    * Count occurrences → `map<T, int>` or `unordered_map<T, int>`
    * With removal → `multiset` (careful with erase!)
  </Card>

  <Card title="Need FIFO/LIFO?" icon="layer-group">
    * Stack → `stack` or `vector`
    * Queue → `queue` or `deque`
    * Both ends → `deque`
  </Card>
</CardGroup>

***

## Common Pitfalls

### Pitfall 1: Iterator Invalidation

```cpp theme={null}
// 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

```cpp theme={null}
// 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

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

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

***

## Key Takeaways

<CardGroup cols={2}>
  <Card title="Know Your Complexities" icon="clock">
    `vector` O(1) access, `set/map` O(log n), `unordered_*` O(1) average.
  </Card>

  <Card title="Use STL Algorithms" icon="wand-magic">
    `sort`, `lower_bound`, `unique`, `accumulate` save time and bugs.
  </Card>

  <Card title="Default to Vector" icon="list">
    Unless you need specific properties, `vector` is usually the best choice.
  </Card>

  <Card title="Careful with Erase" icon="triangle-exclamation">
    Erasing invalidates iterators. Know the patterns.
  </Card>
</CardGroup>

***

## Next Up

<Card title="Chapter 4: Prefix Sum & Difference Arrays" icon="arrow-right" href="/courses/competitive-programming/04-prefix-sum">
  Answer range queries in O(1) and apply updates efficiently with these fundamental techniques.
</Card>