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.
↵
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.↵
↵
```cpp↵
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.**↵
↵
```cpp↵
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↵
↵
| Query | Code |↵
|-------|------|↵
| How many numbers **< x** | `lower_bound(v.begin(), v.end(), x) - v.begin()` |↵
| How many numbers **≤ x** | `upper_bound(v.begin(), v.end(), x) - v.begin()` |↵
| How many numbers **≥ x** | `v.end() - lower_bound(v.begin(), v.end(), x)` |↵
| How many numbers **> x** | `v.end() - upper_bound(v.begin(), v.end(), x)` |↵
| Count in range **[L, R]** | `upper_bound(..., R) - lower_bound(..., L)` |↵
↵
### Complete Example↵
↵
```cpp↵
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?↵
↵
| Operation | Array | BST (balanced) | BST (worst case) |↵
|-----------|-------|----------------|------------------|↵
| Search | O(n) | O(log n) | O(n) |↵
| Insert | O(1) | O(log n) | O(n) |↵
| Delete | O(n) | O(log n) | O(n) |↵
↵
### 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.↵
↵
```cpp↵
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↵
↵
```cpp↵
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↵
↵
```cpp↵
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**.↵
↵
```cpp↵
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↵
↵
```cpp↵
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↵
↵
```cpp↵
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↵
↵
```cpp↵
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.↵
↵
```cpp↵
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↵
↵
```cpp↵
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↵
↵
```cpp↵
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↵
↵
```cpp↵
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)↵
↵
```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 **.↵
↵
↵
cout << pq.top(); // 8↵
pq.pop();↵
cout << pq.top(); // 5↵
```↵
↵
### Min Heap↵
↵
```cpp↵
priority_queue<int, vector<int>, greater<int>> pq;↵
↵
pq.push(5);↵
pq.push(2);↵
pq.push(8);↵
↵
cout << pq.top(); // 2↵
```↵
↵
### Custom Comparator↵
↵
```cpp↵
// 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↵
↵
| Structure | Duplicates | Sorted | Access | Insert | Search | Use Case |↵
|-----------|-----------|--------|--------|--------|--------|----------|↵
| `vector` | Yes | No | O(1) | O(1) amortized | O(n) | General purpose |↵
| `set` | No | Yes | O(log n) | O(log n) | O(log n) | Unique elements |↵
| `multiset` | Yes | Yes | O(log n) | O(log n) | O(log n) | Sorted with dupes |↵
| `map` | No (keys) | Yes | O(log n) | O(log n) | O(log n) | Key-value pairs |↵
| `priority_queue` | Yes | Partial | O(1) top | O(log n) | O(n) | Max/min queries |↵
↵
---↵
↵
## Common Patterns↵
↵
### Pattern 1: Frequency Map↵
↵
```cpp↵
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↵
↵
```cpp↵
// 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↵
↵
```cpp↵
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](https://cses.fi/problemset/task/1084) — Two pointers + sorting↵
- [CSES — Concert Tickets](https://cses.fi/problemset/task/1091) — Multiset usage↵
- [CSES — Sum of Two Values](https://cses.fi/problemset/task/1640) — Map or two pointers↵
↵
### Medium↵
- [CSES — Movie Festival](https://cses.fi/problemset/task/1629) — Greedy + sorting↵
- [CSES — Towers](https://cses.fi/problemset/task/1073) — Multiset + greedy↵
- [CSES — Traffic Lights](https://cses.fi/problemset/task/1163) — Set + multiset combo↵
↵
---↵
↵
## Summary↵
↵
| Tool | Superpower |↵
|------|------------|↵
| `lower_bound` / `upper_bound` | Binary search on sorted containers |↵
| `set` | Unique + sorted elements |↵
| `multiset` | Sorted + allows duplicates |↵
| `map` | Key-value pairs, sorted by key |↵
| `priority_queue` | Always access max/min element |↵
↵
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!
