Hi everyone ↵
In this lecture we’ll go deeper into STL structures that are **must-know** for competitive programming.↵
↵
---↵
↵
## 1. Iterators & Vectors↵
↵
```cpp↵
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**.↵
↵
```cpp↵
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).↵
↵
```cpp↵
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↵
↵
```cpp↵
sort(v.begin(), v.end());↵
v.erase(unique(v.begin(), v.end()), v.end());↵
```↵
↵
---↵
↵
## 5. `multiset`↵
↵
* Same as `set`, but allows duplicates.↵
↵
```cpp↵
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↵
↵
```cpp↵
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.↵
↵
```cpp↵
map<string,int> mp;↵
↵
mp["apple"] = 5;↵
mp.insert({"banana", 10});↵
↵
for (auto [k, v] : mp) {↵
cout << k << " " << v << "\n";↵
}↵
```↵
to get last element ↵
auto last = m.rbegin(); // reverse iterator points to last element↵
cout << "Last key: " << last->first << ", value: " << last->second << endl;↵
↵
↵
* `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.↵
↵
```cpp↵
priority_queue<int> pq; // max heap↵
pq.push(5);↵
pq.push(2);↵
pq.push(8);↵
↵
cout << pq.top(); // 8↵
pq.pop();↵
```↵
↵
* For **min heap**:↵
↵
```cpp↵
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 **.↵
↵
In this lecture we’ll go deeper into STL structures that are **must-know** for competitive programming.↵
↵
---↵
↵
## 1. Iterators & Vectors↵
↵
```cpp↵
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**.↵
↵
```cpp↵
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).↵
↵
```cpp↵
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↵
↵
```cpp↵
sort(v.begin(), v.end());↵
v.erase(unique(v.begin(), v.end()), v.end());↵
```↵
↵
---↵
↵
## 5. `multiset`↵
↵
* Same as `set`, but allows duplicates.↵
↵
```cpp↵
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↵
↵
```cpp↵
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.↵
↵
```cpp↵
map<string,int> mp;↵
↵
mp["apple"] = 5;↵
mp.insert({"banana", 10});↵
↵
for (auto [k, v] : mp) {↵
cout << k << " " << v << "\n";↵
}↵
```↵
to get last element ↵
auto last = m.rbegin(); // reverse iterator points to last element↵
cout << "Last key: " << last->first << ", value: " << last->second << endl;↵
↵
↵
* `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.↵
↵
```cpp↵
priority_queue<int> pq; // max heap↵
pq.push(5);↵
pq.push(2);↵
pq.push(8);↵
↵
cout << pq.top(); // 8↵
pq.pop();↵
```↵
↵
* For **min heap**:↵
↵
```cpp↵
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 **.↵
↵
