Advanced STL Structures — A Complete Guide

Hi everyone! In this lecture we'll go deeper into STL structures that are must-know for competitive programming.

1. Iterators & Vectors

Iterators are like pointers that let you navigate through containers.

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

auto it = v.begin();           // points to first element
auto end = v.end();            // points AFTER last element

sort(v.begin(), v.end());      // sort entire vector
v.end() - v.begin();           // size of vector

Key Facts

• v.begin() → iterator to first element
• v.end() → iterator AFTER last element (not the last element itself!)
• v.size() = v.end() - v.begin()

Important Trick

Count numbers in range [l, r] = r - l + 1.

This formula appears constantly in: - Binary search problems - Range queries - Coordinate compression

Example: cpp // How many integers from 5 to 10 inclusive? int count = 10 - 5 + 1; // = 6 (which is: 5,6,7,8,9,10)

2. lower_bound & upper_bound

Must use on a sorted container.

vector<int> v = {1, 3, 3, 5, 7, 9};

auto it1 = lower_bound(v.begin(), v.end(), 3);  // first element >= 3
auto it2 = upper_bound(v.begin(), v.end(), 3);  // first element > 3

Visual Example

Array: [1, 3, 3, 5, 7, 9]
              ↑     ↑
       lower_bound(3)  upper_bound(3)

Common Use Cases

Complete Example

vector<int> v = {1, 3, 3, 5, 7, 9};
sort(v.begin(), v.end());  // ensure sorted

// Count numbers in range [3, 7]
int count = upper_bound(v.begin(), v.end(), 7) - 
            lower_bound(v.begin(), v.end(), 3);
// Result: 4 (elements: 3, 3, 5, 7)

3. Binary Search Tree (BST) — Theory

Understanding BSTs helps you understand set and map internals.

Structure

• Each node has: parent, left child, right child
• BST Property: left < parent < right

        5
       / \
      3   8
     / \   \
    1   4   9

Why BST?

Balance Condition

A balanced BST maintains: |size(left) - size(right)| ≤ 1

C++ uses self-balancing BSTs (Red-Black Trees) to guarantee O(log n) operations.

4. set

Stores unique, sorted elements using a balanced BST.

set<int> st;
st.insert(6);
st.insert(3);
st.insert(5);
st.insert(1);
st.insert(3);  // duplicate ignored

for(auto x : st) 
    cout << x << " ";  // Output: 1 3 5 6

Key Operations

set<int> st = {1, 3, 5, 7, 9};

// Search
auto it = st.find(5);          // iterator to 5, or st.end() if not found
if(it != st.end()) {
    cout << "Found: " << *it;
}

// Insert
st.insert(4);                  // O(log n)

// Erase
st.erase(3);                   // erase by value
st.erase(st.find(5));          // erase by iterator

// Min/Max
int min_val = *st.begin();     // smallest element
int max_val = *st.rbegin();    // largest element
// Alternative: *(--st.end())

Important Limitations

No indexing — st[2] does NOT work

No random access — cannot jump to middle element directly

Common Pattern: Make Vector Distinct

vector<int> v = {3, 1, 4, 1, 5, 9, 2, 6, 5};

// Method 1: Using set
set<int> st(v.begin(), v.end());
v.assign(st.begin(), st.end());

// Method 2: sort + unique (faster)
sort(v.begin(), v.end());
v.erase(unique(v.begin(), v.end()), v.end());

5. multiset

Same as set, but allows duplicates.

multiset<int> ms = {1, 2, 3, 4, 4, 4, 5, 5};

ms.insert(4);     // now has 4 copies of 4
ms.erase(4);      // WARNING: erases ALL 4's!

// To erase only ONE occurrence:
ms.erase(ms.find(4));

Critical Difference

multiset<int> ms = {1, 2, 2, 2, 3};

ms.erase(2);              // removes ALL 2's → {1, 3}
ms.erase(ms.find(2));     // removes ONE 2 → {1, 2, 2, 3}

Count Occurrences

multiset<int> ms = {1, 2, 2, 2, 3};
int cnt = ms.count(2);    // O(log n + k), where k = count

Advanced Example: Find Second Greater Element

multiset<int> ms = {1, 3, 5, 7, 9};

int secondGreater(int x) {
    auto it = ms.upper_bound(x);    // first element > x
    if(it == ms.end()) return -1;   // no element > x
    
    it = ms.upper_bound(*it);       // second element > x
    if(it == ms.end()) return -1;   // only one element > x
    
    return *it;
}

// Example: secondGreater(3) → 7

6. map

Stores key → value pairs, sorted by key.

map<string, int> mp;

mp["apple"] = 5;
mp["banana"] = 10;
mp.insert({"cherry", 15});

for(auto [key, value] : mp) {
    cout << key << " → " << value << "\n";
}
// Output (sorted by key):
// apple → 5
// banana → 10
// cherry → 15

Key Operations

map<string, int> mp;

// Access (creates if doesn't exist)
mp["apple"] = 5;
cout << mp["banana"];       // 0 (default value)

// Check existence
if(mp.find("apple") != mp.end()) {
    cout << "Found";
}
// Or:
if(mp.count("apple")) {
    cout << "Found";
}

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

// First and last elements
auto first = mp.begin();
cout << first->first << " → " << first->second;

auto last = mp.rbegin();  // reverse iterator
cout << last->first << " → " << last->second;

lower_bound and upper_bound on Maps

map<int, string> mp = {{1,"a"}, {5,"b"}, {9,"c"}};

auto it = mp.lower_bound(4);   // iterator to {5,"b"}
auto it2 = mp.upper_bound(5);  // iterator to {9,"c"}

Note: These work on keys, not values.

Default Values

map<int, int> freq;
freq[5]++;     // freq[5] starts at 0, becomes 1

map<int, vector<int>> adj;
adj[3].push_back(7);  // creates empty vector first

7. priority_queue

A heap that keeps elements sorted. Always access the largest (or smallest) element in O(1).

Max Heap (Default)

priority_queue<int> pq;  // max heap

pq.push(5);
pq.push(2);
pq.push(8);
pq.push(1);

cout << pq.top();  // 8
pq.pop();
cout << pq.top();  // 5

Min Heap

priority_queue<int, vector<int>, greater<int>> pq;

pq.push(5);
pq.push(2);
pq.push(8);

cout << pq.top();  // 2

Custom Comparator

// Sort pairs by second element
priority_queue
    pair<int,int>, 
    vector<pair<int,int>>, 
    greater<pair<int,int>>
> pq;

pq.push({1, 10});
pq.push({2, 5});
pq.push({3, 15});

auto top = pq.top();  // {2, 5} (smallest second element)

When to Use

• Dijkstra's algorithm → min heap of distances
• Greedy problems → always process smallest/largest element
• Event simulation → process events in time order

Comparison Table

Common Patterns

Pattern 1: Frequency Map

map<int, int> freq;
for(int x : arr) 
    freq[x]++;

// Find most frequent
int max_freq = 0;
for(auto [val, cnt] : freq)
    max_freq = max(max_freq, cnt);

Pattern 2: Sliding Window with Set

// Find if any subarray of size k has all distinct elements
set<int> window;
for(int i = 0; i < n; i++) {
    window.insert(arr[i]);
    if(i >= k) window.erase(arr[i-k]);
    
    if(window.size() == k) {
        cout << "Found at " << i-k+1;
    }
}

Pattern 3: Lower Bound for Closest Element

set<int> st = {1, 5, 10, 15, 20};
int x = 12;

auto it = st.lower_bound(x);

int closest;
if(it == st.end()) {
    closest = *prev(it);  // all elements < x
} else if(it == st.begin()) {
    closest = *it;        // all elements >= x
} else {
    // Check both neighbors
    int right = *it;
    int left = *prev(it);
    closest = (x - left < right - x) ? left : right;
}

Practice Problems

Easy

• CSES — Apartments — Two pointers + sorting
• CSES — Concert Tickets — Multiset usage
• CSES — Sum of Two Values — Map or two pointers

Medium

• CSES — Movie Festival — Greedy + sorting
• CSES — Towers — Multiset + greedy
• CSES — Traffic Lights — Set + multiset combo

Summary

These STL tools are competitive programming superpowers.

Master them, and you'll solve problems faster and cleaner than ever before.

Next topics to explore: - Unordered containers (unordered_set, unordered_map) - Custom comparators for set and priority_queue - STL algorithms (next_permutation, accumulate, partial_sum)

Questions? Drop them in the comments!