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

1. Iterators & Vectors

auto it = v.begin();    // pointer to first element
sort(v.begin(), v.end());

v.begin();              // first element
v.end();                // points AFTER last element
v.end() - v.begin();    // size of vector

Important trick: Count numbers in range [l, r] = r - l + 1. This often appears in binary search problems.

2. lower_bound & upper_bound

Must use on a sorted container.

auto it = lower_bound(v.begin(), v.end(), x); 
// first element >= x

auto it = upper_bound(v.begin(), v.end(), x); 
// first element > x

Use cases

• How many numbers < x → lower_bound - v.begin()
• How many numbers ≤ x → upper_bound - v.begin()
• How many numbers ≥ x → v.size() - (lower_bound - v.begin())
• Count in range [L, R]:

cpp upper_bound(v.begin(), v.end(), R) - lower_bound(v.begin(), v.end(), L);

3. Binary Search Tree (BST)

• Each node has parent, left child, right child.
• Left < parent < right.
• Searching in normal array = O(n).
• In BST = average O(log n), worst O(n) if unbalanced.
• Balanced BST keeps: |size(left) - size(right)| ≤ 1.

4. set

• Stores unique, sorted elements.
• Implemented using balanced BST → all operations O(log n).

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

for (auto x : st) cout << x << "\n"; // no indexing!

Functions

• st.find(x) → iterator or st.end()
• st.erase(x) → erase by key
• st.erase(st.find(x)) → erase by iterator
• *st.begin() → min element
• *st.rbegin() or *(--st.end()) → max element

No indexing like st[2].

Make vector distinct

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.erase(4);            // erase *all* 4’s
ms.erase(ms.find(5));   // erase one 5

Example: find second greater element

multiset<int> ms;

int secondGreater(int x) {
    auto it = ms.upper_bound(x); 
    if (it == ms.end()) return -1;
    it = ms.upper_bound(*it); 
    if (it == ms.end()) return -1;
    return *it;
}

6. map

• Stores key → value, sorted by key.
• Default value = 0 for integers.

map<string,int> mp;

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

for (auto [k, v] : mp) {
    cout << k << " " << v << "\n";
}

• lower_bound & upper_bound work on keys.
• No need to predefine size.

7. priority_queue

• Like a stack, but always keeps elements sorted inside.
• Default = max heap.

priority_queue<int> pq;  // max heap
pq.push(5);
pq.push(2);
pq.push(8);

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

• For min heap:

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

Summary

• lower_bound / upper_bound → binary search helpers.
• set → distinct + sorted.
• multiset → sorted + allows duplicates.
• map → key-value pairs, sorted by key.
• priority_queue → max/min heap.

These STL tools = **competitive programming superpowers **.