C++ STL Deep Dive

vector<int> a;                         // Empty vector
vector<int> b(5);                      // 5 elements, all zero-initialized
vector<int> c(5, -1);                  // 5 elements, all -1
vector<int> d = {1, 2, 3, 4, 5};      // Initializer list
vector<int> e(d);                      // Copy of d
vector<int> f(d.begin(), d.begin()+3); // {1,2,3} — range constructor
 
// 2D vector (n×m filled with 0)
int n = 3, m = 4;
vector<vector<int>> grid(n, vector<int>(m, 0));

#include <bits/stdc++.h>
using namespace std;
 
int main() {
    vector<int> v = {3, 1, 4, 1, 5, 9};
 
    // --- Access ---
    cout << v[0];           // 3 — no bounds check
    cout << v.at(0);        // 3 — throws std::out_of_range if invalid
 
    // --- Modify ---
    v.push_back(2);         // {3,1,4,1,5,9,2}
    v.pop_back();           // {3,1,4,1,5,9}
    v.insert(v.begin(), 0); // {0,3,1,4,1,5,9} — O(n)!
    v.erase(v.begin());     // {3,1,4,1,5,9}   — O(n)!
 
    // --- Info ---
    cout << v.size();       // 6
    cout << v.capacity();   // ≥6 (implementation-defined)
    cout << v.empty();      // 0 (false)
 
    // --- Reserve to avoid reallocations ---
    vector<int> big;
    big.reserve(100000);    // Allocate space upfront — avoids N reallocations
    for (int i = 0; i < 100000; i++) big.push_back(i);
 
    // --- Resize ---
    v.resize(10);           // Extends to size 10, new elements = 0
    v.resize(3);            // Shrinks to first 3 elements
 
    // --- Clear ---
    v.clear();              // v is now empty, but capacity is unchanged
}

vector<int> v = {1, 2, 3, 2, 4, 2, 5};
 
// std::remove shifts non-matching elements to front, returns new end iterator
// v.erase then removes the "garbage" tail
v.erase(remove(v.begin(), v.end(), 2), v.end());
// v = {1, 3, 4, 5}
 
// Remove by condition
v.erase(remove_if(v.begin(), v.end(), [](int x){ return x % 2 == 0; }), v.end());
// Removes all even numbers

// --- Prefix sum array ---
vector<int> arr = {1, 2, 3, 4, 5};
vector<int> prefix(arr.size() + 1, 0);
for (int i = 0; i < (int)arr.size(); i++) {
    prefix[i+1] = prefix[i] + arr[i];
}
// Sum from index l to r (0-indexed, inclusive):
int l = 1, r = 3;
int rangeSum = prefix[r+1] - prefix[l];   // 2+3+4 = 9
 
// --- Adjacency list for graphs ---
int n = 5;  // 5 nodes
vector<vector<int>> adj(n);
adj[0].push_back(1);
adj[0].push_back(2);
adj[1].push_back(3);
 
// --- DP table ---
vector<vector<int>> dp(n, vector<int>(n, 0));
 
// --- Flatten 2D index to 1D ---
int rows = 4, cols = 5;
int idx = row * cols + col;   // 2D → 1D
int r = idx / cols, c = idx % cols;  // 1D → 2D

#include <array>
 
array<int, 5> a = {1, 2, 3, 4, 5};  // Size must be a compile-time constant
array<int, 5> b;                     // Uninitialized (unlike vector!)
b.fill(0);                           // Zero all elements
 
cout << a.size();    // 5 (constexpr)
cout << a[2];        // 3
cout << a.front();   // 1
cout << a.back();    // 5
 
// Works with all STL algorithms
sort(a.begin(), a.end());

// Classic direction arrays — use array or C-style arrays
const int dx[] = {0, 0,  1, -1};
const int dy[] = {1, -1, 0,  0};
// Or
array<int,4> DX = {0, 0, 1, -1};
array<int,4> DY = {1, -1, 0, 0};

#include <deque>
 
deque<int> dq;
 
dq.push_back(3);    // [3]
dq.push_front(1);   // [1, 3]
dq.push_back(5);    // [1, 3, 5]
dq.push_front(0);   // [0, 1, 3, 5]
 
dq.pop_front();     // [1, 3, 5]
dq.pop_back();      // [1, 3]
 
cout << dq.front(); // 1
cout << dq.back();  // 3
cout << dq[0];      // 1 — O(1) random access
cout << dq.size();  // 2

// Monotonic deque — sliding window maximum (preview of Chapter 9)
deque<int> monoDeque;  // Stores indices
// Maintains decreasing order of values

#include <list>
 
list<int> l = {1, 2, 3, 4, 5};
 
l.push_back(6);     // [1,2,3,4,5,6]
l.push_front(0);    // [0,1,2,3,4,5,6]
l.pop_back();       // [0,1,2,3,4,5]
l.pop_front();      // [1,2,3,4,5]
 
auto it = l.begin();
advance(it, 2);         // Move iterator forward 2 steps (O(n) for list)
l.insert(it, 99);       // [1,2,99,3,4,5] — O(1) once we have the iterator
l.erase(it);            // Removes the element at it — O(1)
 
l.reverse();            // Reverses in-place — O(n)
l.sort();               // Sorts in-place — O(n log n) — must use member sort!
l.unique();             // Removes consecutive duplicates
 
// For range-based for:
for (int x : l) cout << x << " ";

#include <map>
 
map<string, int> freq;
 
// --- Insert ---
freq["apple"] = 3;               // Assignment (inserts if not present)
freq["banana"] = 1;
freq.insert({"cherry", 5});      // Insert pair
freq.emplace("date", 2);         // Construct in-place (preferred)
 
// --- Access ---
cout << freq["apple"];           // 3 — inserts with default value if missing!
cout << freq.at("apple");        // 3 — throws std::out_of_range if missing
 
// Warning: operator[] is DANGEROUS for lookup — creates entry if key not found!
if (freq.count("elderberry")) {  // ✅ Safe check first
    cout << freq["elderberry"];
}
 
// --- Find ---
auto it = freq.find("banana");
if (it != freq.end()) {
    cout << it->first;           // "banana"
    cout << it->second;          // 1
}
 
// --- Iteration (always sorted by key) ---
for (auto& [key, val] : freq) {
    cout << key << ": " << val << "\n";
}
// Output: apple:3, banana:1, cherry:5, date:2 (alphabetical)
 
// --- Erase ---
freq.erase("apple");             // Remove by key
freq.erase(freq.begin());        // Remove by iterator
 
// --- Size ---
cout << freq.size();             // Number of entries
cout << freq.empty();            // Is it empty?
 
// --- Count (0 or 1 since no duplicates) ---
cout << freq.count("banana");    // 1 (exists), 0 (not found)

map<int, string> m = {{1,"a"},{3,"b"},{5,"c"},{7,"d"},{10,"e"}};
 
// lower_bound(k): first key >= k
auto lo = m.lower_bound(4);    // Points to {5,"c"}
cout << lo->first;             // 5
 
// upper_bound(k): first key > k
auto hi = m.upper_bound(5);    // Points to {7,"d"}
cout << hi->first;             // 7
 
// Find range [3, 7]
auto from = m.lower_bound(3);  // {3,"b"}
auto to   = m.upper_bound(7);  // Points past {7,"d"} → to {10,"e"}
for (auto it = from; it != to; ++it) {
    cout << it->first << " ";  // 3 5 7
}

multimap<int, string> mm;
mm.insert({1, "one"});
mm.insert({1, "uno"});    // Duplicate key allowed!
mm.insert({2, "two"});
 
cout << mm.count(1);      // 2
 
// Iterate all values for a key
auto [lo, hi] = mm.equal_range(1);
for (auto it = lo; it != hi; ++it) {
    cout << it->second << " ";  // "one" "uno"
}

#include <set>
 
set<int> s = {5, 1, 4, 2, 3};  // Stored as: {1, 2, 3, 4, 5}
 
s.insert(3);                    // Already exists — no change
s.insert(6);                    // {1, 2, 3, 4, 5, 6}
s.erase(4);                     // {1, 2, 3, 5, 6}
 
cout << s.count(3);             // 1 (exists)
cout << s.count(4);             // 0 (not found)
 
auto it = s.find(3);
if (it != s.end()) cout << *it; // 3
 
// Lower/upper bound
auto lo = s.lower_bound(3);     // Iterator to 3
auto hi = s.upper_bound(5);     // Iterator past 5 (points to 6)
 
// Iteration — always sorted
for (int x : s) cout << x << " ";  // 1 2 3 5 6
 
// Min and max in O(log n)
cout << *s.begin();             // 1 (smallest)
cout << *s.rbegin();            // 6 (largest)

// --- Check duplicates efficiently ---
vector<int> nums = {1, 2, 3, 2, 4};
set<int> seen(nums.begin(), nums.end());
bool hasDuplicate = seen.size() != nums.size();  // true
 
// --- Ordered unique elements ---
set<int> unique_set(v.begin(), v.end());
 
// --- k-th smallest element (not built in, but we can count) ---
// For frequent k-th queries, use an Order Statistics Tree or sorted vector
 
// --- Find closest value in a set ---
set<int> s = {1, 5, 10, 20};
int target = 7;
auto it = s.lower_bound(target);   // ≥ target: points to 10
// Check predecessor
if (it != s.begin()) {
    auto prev_it = prev(it);       // 5
    // Compare *prev_it and *it with target
}

multiset<int> ms = {1, 2, 2, 3, 3, 3};
cout << ms.count(3);     // 3
 
ms.erase(ms.find(3));    // ✅ Removes only ONE occurrence of 3
ms.erase(3);             // ❌ Removes ALL occurrences of 3!

#include <unordered_map>
 
unordered_map<string, int> freq;
 
// --- Insert / Update ---
freq["apple"]++;               // Inserts with 0, then increments
freq["banana"] = 5;
freq.insert({"cherry", 3});
freq.emplace("date", 2);
 
// --- Access ---
cout << freq["apple"];         // 1 (use carefully — inserts if absent!)
auto it = freq.find("banana");
if (it != freq.end()) {
    cout << it->second;        // 5
}
 
// --- Check existence ---
cout << freq.count("apple");   // 1 (exists), 0 (absent)
cout << freq.contains("apple"); // C++20: true/false
 
// --- Erase ---
freq.erase("apple");
 
// --- Iteration (order not guaranteed) ---
for (auto& [key, val] : freq) {
    cout << key << ": " << val << "\n";
}
 
// --- Useful info ---
cout << freq.size();           // Number of entries
cout << freq.load_factor();    // Elements / Buckets
freq.reserve(1000);            // Pre-size to avoid rehashing

vector<int> nums = {1, 2, 2, 3, 3, 3, 4};
unordered_map<int, int> cnt;
for (int x : nums) cnt[x]++;
// cnt = {1:1, 2:2, 3:3, 4:1}
 
// Find element with max frequency
int maxFreq = 0, maxElem = -1;
for (auto& [elem, freq] : cnt) {
    if (freq > maxFreq) {
        maxFreq = freq;
        maxElem = elem;
    }
}
// maxElem = 3, maxFreq = 3

#include <unordered_set>
 
unordered_set<int> s;
 
s.insert(1);
s.insert(2);
s.insert(1);         // Duplicate — ignored
 
cout << s.count(1);  // 1
cout << s.count(5);  // 0
 
s.erase(2);
 
// --- Pattern: O(1) duplicate detection ---
vector<int> nums = {1, 2, 3, 4, 5, 3};
unordered_set<int> seen;
for (int x : nums) {
    if (seen.count(x)) {
        cout << x << " is a duplicate\n";
        break;
    }
    seen.insert(x);
}
 
// --- Pattern: Two Sum ---
vector<int> arr = {2, 7, 11, 15};
int target = 9;
unordered_set<int> visited;
for (int x : arr) {
    if (visited.count(target - x)) {
        cout << "Found: " << x << " and " << target - x << "\n";
    }
    visited.insert(x);
}

#include <stack>
 
stack<int> st;
 
st.push(1);         // [1]
st.push(2);         // [1, 2]
st.push(3);         // [1, 2, 3]
 
cout << st.top();   // 3 (last pushed)
st.pop();           // [1, 2] — removes top, returns void
cout << st.top();   // 2
cout << st.size();  // 2
cout << st.empty(); // false
 
// Warning: Always check empty() before top() or pop()!
while (!st.empty()) {
    cout << st.top();
    st.pop();
}

// Iterative DFS on a graph
stack<int> dfsStack;
vector<bool> visited(n, false);
 
dfsStack.push(start);
while (!dfsStack.empty()) {
    int node = dfsStack.top();
    dfsStack.pop();
    if (visited[node]) continue;
    visited[node] = true;
    // process node
    for (int neighbor : adj[node]) {
        if (!visited[neighbor])
            dfsStack.push(neighbor);
    }
}

// Find the Next Greater Element for each position
vector<int> nums = {2, 1, 2, 4, 3};
int n = nums.size();
vector<int> nge(n, -1);    // Next Greater Element (-1 if none)
 
stack<int> st;             // Stores indices
for (int i = 0; i < n; i++) {
    while (!st.empty() && nums[st.top()] < nums[i]) {
        nge[st.top()] = nums[i];
        st.pop();
    }
    st.push(i);
}
// nge = [4, 2, 4, -1, -1]

#include <queue>
 
queue<int> q;
 
q.push(1);          // [1]
q.push(2);          // [1, 2]
q.push(3);          // [1, 2, 3]
 
cout << q.front();  // 1 (first in)
cout << q.back();   // 3 (last in)
q.pop();            // Removes front → [2, 3]
cout << q.front();  // 2
cout << q.size();   // 2
cout << q.empty();  // false

// BFS on a graph — finds shortest path in unweighted graph
vector<int> bfs(int start, int n, vector<vector<int>>& adj) {
    vector<int> dist(n, -1);
    queue<int> q;
 
    dist[start] = 0;
    q.push(start);
 
    while (!q.empty()) {
        int node = q.front();
        q.pop();
 
        for (int neighbor : adj[node]) {
            if (dist[neighbor] == -1) {      // Not visited
                dist[neighbor] = dist[node] + 1;
                q.push(neighbor);
            }
        }
    }
    return dist;
}

#include <queue>
 
// --- MAX-HEAP (default) ---
priority_queue<int> maxPQ;
maxPQ.push(3);
maxPQ.push(1);
maxPQ.push(4);
maxPQ.push(1);
maxPQ.push(5);
 
cout << maxPQ.top();   // 5 (largest)
maxPQ.pop();
cout << maxPQ.top();   // 4
 
// --- MIN-HEAP using greater<T> ---
priority_queue<int, vector<int>, greater<int>> minPQ;
minPQ.push(3);
minPQ.push(1);
minPQ.push(4);
 
cout << minPQ.top();   // 1 (smallest)
 
// --- Pairs in priority_queue (sorted by first element) ---
priority_queue<pair<int,int>> pq;  // Max by first element
pq.push({3, 10});
pq.push({1, 20});
pq.push({5, 5});
 
auto [dist, node] = pq.top();  // {5, 5}
pq.pop();

// Min-heap ordered by second element of pair
auto cmp = [](const pair<int,int>& a, const pair<int,int>& b) {
    return a.second > b.second;  // Note: > for min-heap
};
priority_queue<pair<int,int>,
               vector<pair<int,int>>,
               decltype(cmp)> customPQ(cmp);
 
customPQ.push({1, 30});
customPQ.push({2, 10});
customPQ.push({3, 20});
 
cout << customPQ.top().second;   // 10 (minimum second value)

vector<int> dijkstra(int src, int n, vector<vector<pair<int,int>>>& adj) {
    vector<int> dist(n, INT_MAX);
    priority_queue<pair<int,int>,
                   vector<pair<int,int>>,
                   greater<>> minPQ;  // {distance, node}
 
    dist[src] = 0;
    minPQ.push({0, src});
 
    while (!minPQ.empty()) {
        auto [d, u] = minPQ.top();
        minPQ.pop();
 
        if (d > dist[u]) continue;  // Stale entry
 
        for (auto [w, v] : adj[u]) {
            if (dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                minPQ.push({dist[v], v});
            }
        }
    }
    return dist;
}

#include <string>
 
string s = "hello world";
 
// --- Size & Access ---
cout << s.length();          // 11 (or s.size() — same)
cout << s.empty();           // false
cout << s[0];                // 'h'
cout << s.front();           // 'h'
cout << s.back();            // 'd'
 
// --- Modification ---
s.push_back('!');            // "hello world!"
s.pop_back();                // "hello world"
s += " again";               // "hello world again"
s.append(" more");           // "hello world again more"
s.insert(5, " dear");        // Inserts at index 5
s.erase(5, 5);               // Erases 5 characters starting at index 5
s.replace(0, 5, "bye");      // Replaces first 5 chars with "bye"
 
// --- Substring ---
string sub = s.substr(0, 5);  // First 5 characters
string end = s.substr(6);     // From index 6 to end
 
// --- Search ---
size_t pos = s.find("world");     // First occurrence, npos if not found
size_t rpos = s.rfind("l");       // Last occurrence of 'l'
if (pos != string::npos) {
    cout << "Found at " << pos;
}
 
// Find first character in/not in a set
size_t p1 = s.find_first_of("aeiou");    // First vowel
size_t p2 = s.find_first_not_of("aeiou"); // First non-vowel
 
// --- Comparison ---
if (s == "hello") { ... }
if (s < "world") { ... }   // Lexicographic
int cmp = s.compare("hello");  // 0 if equal, <0 if less, >0 if greater
 
// --- Conversion ---
string ns = to_string(42);      // "42"
int n = stoi("42");              // 42
long long ll = stoll("123456789012");
 
// --- Case manipulation ---
for (char& c : s) c = tolower(c);   // To lowercase
for (char& c : s) c = toupper(c);   // To uppercase
 
// --- Reverse ---
reverse(s.begin(), s.end());
 
// --- Split by delimiter (no built-in — use this pattern) ---
string line = "a,b,c,d";
vector<string> parts;
stringstream ss(line);
string token;
while (getline(ss, token, ',')) {
    parts.push_back(token);
}
// parts = {"a", "b", "c", "d"}

// --- Palindrome check ---
bool isPalindrome(const string& s) {
    int l = 0, r = s.size() - 1;
    while (l < r) {
        if (s[l] != s[r]) return false;
        l++; r--;
    }
    return true;
}
 
// --- Anagram check ---
bool isAnagram(const string& s, const string& t) {
    if (s.size() != t.size()) return false;
    int freq[26] = {};
    for (char c : s) freq[c - 'a']++;
    for (char c : t) freq[c - 'a']--;
    for (int f : freq) if (f != 0) return false;
    return true;
}
 
// --- Build string efficiently (avoid O(n²) concatenation) ---
// ❌ Slow: O(n²) due to repeated allocation
string result = "";
for (int i = 0; i < n; i++) result += chars[i];
 
// ✅ Fast: use ostringstream or reserve
string result;
result.reserve(n);   // Reserve space upfront
for (int i = 0; i < n; i++) result += chars[i];   // Now O(n) amortized

#include <string_view>
 
// string_view is a lightweight, read-only reference to a string
// No copying — very fast for function parameters
 
void printPrefix(string_view sv, int len) {
    cout << sv.substr(0, len);  // No copy!
}
 
string s = "hello world";
printPrefix(s, 5);    // "hello"
printPrefix("hello world", 5);  // Works with string literals too
 
// Use string_view for read-only string parameters instead of const string&
// It can be constructed from both std::string and char* without copying

vector<int> v = {1, 2, 3, 4, 5};
 
// --- Forward iteration ---
for (auto it = v.begin(); it != v.end(); ++it) {
    cout << *it << " ";    // Dereference to get value
}
 
// --- Reverse iteration ---
for (auto it = v.rbegin(); it != v.rend(); ++it) {
    cout << *it << " ";    // 5 4 3 2 1
}
 
// --- Const iterators (read-only) ---
for (auto it = v.cbegin(); it != v.cend(); ++it) {
    // *it = 10;  ← ❌ Compile error: can't modify through const_iterator
}
 
// --- Iterator arithmetic (random-access only) ---
auto it = v.begin();
it += 2;               // Advance 2 steps: points to 3
cout << *it;           // 3
cout << *(it + 1);     // 4
cout << it - v.begin();// 2 (index)
 
// --- Useful iterator functions ---
auto mid = v.begin();
advance(mid, v.size()/2);      // advance() works for ALL iterators (O(n) for non-RA)
 
auto next_it = next(v.begin(), 2);      // Returns iterator 2 steps ahead
auto prev_it = prev(v.end(), 1);        // Returns iterator 1 step back
auto gap = distance(v.begin(), v.end()); // = 5 (O(n) for non-RA, O(1) for RA)

vector<int> v = {3, 1, 4, 1, 5, 9, 2, 6};
 
// Sort the entire vector
sort(v.begin(), v.end());
 
// Sort only elements from index 2 to 5 (inclusive)
sort(v.begin() + 2, v.begin() + 6);
 
// Find element
auto it = find(v.begin(), v.end(), 5);
if (it != v.end()) cout << "Found at index " << distance(v.begin(), it);
 
// Lower bound on sorted range
sort(v.begin(), v.end());
auto lb = lower_bound(v.begin(), v.end(), 4);  // First element >= 4
cout << *lb;    // 4
cout << distance(v.begin(), lb);    // Index of first ≥4 element

vector<int> src = {1, 2, 3};
vector<int> dst = {10, 20, 30};
 
// back_inserter: calls push_back
copy(src.begin(), src.end(), back_inserter(dst));
// dst = {10, 20, 30, 1, 2, 3}
 
// front_inserter: calls push_front (for deque/list)
deque<int> dq = {4, 5, 6};
copy(src.begin(), src.end(), front_inserter(dq));
// dq = {3, 2, 1, 4, 5, 6}

vector<int> v = {5, 3, 1, 4, 2};
 
// --- std::sort — O(n log n), NOT stable ---
sort(v.begin(), v.end());                    // Ascending: {1,2,3,4,5}
sort(v.begin(), v.end(), greater<int>());    // Descending: {5,4,3,2,1}
sort(v.begin(), v.end(), [](int a, int b) { return a > b; }); // Same
 
// --- std::stable_sort — O(n log n), STABLE (preserves equal element order) ---
vector<pair<int,int>> pairs = {{3,1},{1,2},{3,2},{1,1}};
stable_sort(pairs.begin(), pairs.end());  // Stable by first element
 
// --- std::partial_sort — Sort only the first k elements: O(n log k) ---
partial_sort(v.begin(), v.begin() + 3, v.end());  // First 3 are sorted
 
// --- std::nth_element — Partition such that v[k] is what it would be: O(n) avg ---
nth_element(v.begin(), v.begin() + 2, v.end());  // v[2] is the median
 
// --- std::sort on custom struct ---
struct Job { int start, end, weight; };
vector<Job> jobs = {{0,6,60},{1,4,20},{3,5,30},{3,8,30}};
sort(jobs.begin(), jobs.end(), [](const Job& a, const Job& b) {
    return a.end < b.end;   // Sort by end time (Greedy interval scheduling)
});

vector<int> v = {1, 2, 3, 4, 5, 6, 7, 8};
 
// --- binary_search: returns true/false only ---
cout << binary_search(v.begin(), v.end(), 5);  // true
cout << binary_search(v.begin(), v.end(), 9);  // false
 
// --- lower_bound: first element >= target ---
auto lb = lower_bound(v.begin(), v.end(), 4);
cout << *lb;                        // 4
cout << lb - v.begin();             // Index: 3
 
// --- upper_bound: first element > target ---
auto ub = upper_bound(v.begin(), v.end(), 4);
cout << *ub;                        // 5
cout << ub - v.begin();             // Index: 4
 
// --- Count occurrences of a value in sorted array ---
vector<int> sv = {1, 2, 2, 2, 3, 4};
int count = upper_bound(sv.begin(), sv.end(), 2)
          - lower_bound(sv.begin(), sv.end(), 2);  // 3
 
// --- equal_range: returns {lower_bound, upper_bound} ---
auto [lo, hi] = equal_range(sv.begin(), sv.end(), 2);
int cnt = hi - lo;   // 3

// In competitive programming, lower_bound on a sorted vector
// gives you the index of the first element >= x.
// Very useful for coordinate compression and LIS (O(n log n)).
 
// Coordinate compression example:
vector<int> arr = {100, 200, 50, 300, 50};
vector<int> sorted_unique = arr;
sort(sorted_unique.begin(), sorted_unique.end());
sorted_unique.erase(unique(sorted_unique.begin(), sorted_unique.end()),
                    sorted_unique.end());
// sorted_unique = {50, 100, 200, 300}
 
// Map each value to 0-indexed rank
for (int& x : arr) {
    x = lower_bound(sorted_unique.begin(), sorted_unique.end(), x)
        - sorted_unique.begin();
}
// arr = {1, 2, 0, 3, 0}

vector<int> v = {1, 2, 3, 4, 5, 3, 2};
 
// --- find: first occurrence — O(n) ---
auto it = find(v.begin(), v.end(), 3);   // Points to first 3
 
// --- find_if: first matching condition ---
auto it2 = find_if(v.begin(), v.end(), [](int x){ return x > 3; });
cout << *it2;   // 4
 
// --- count: number of occurrences ---
cout << count(v.begin(), v.end(), 3);   // 2
 
// --- count_if: count matching condition ---
cout << count_if(v.begin(), v.end(), [](int x){ return x % 2 == 0; });  // 3
 
// --- min/max element ---
cout << *min_element(v.begin(), v.end());  // 1
cout << *max_element(v.begin(), v.end());  // 5
 
auto [minIt, maxIt] = minmax_element(v.begin(), v.end());
cout << *minIt << " " << *maxIt;           // 1 5
 
// --- Boolean queries ---
bool allPos  = all_of(v.begin(), v.end(), [](int x){ return x > 0; });   // true
bool anyEven = any_of(v.begin(), v.end(), [](int x){ return x % 2 == 0; }); // true
bool noneNeg = none_of(v.begin(), v.end(), [](int x){ return x < 0; });  // true

vector<int> v = {1, 2, 3, 4, 5};
 
// --- reverse --- O(n)
reverse(v.begin(), v.end());    // {5,4,3,2,1}
 
// --- fill: set all elements to a value ---
fill(v.begin(), v.end(), 0);    // {0,0,0,0,0}
fill(v.begin(), v.begin()+3, -1);  // First 3 become -1
 
// --- iota: fill with incrementing values ---
iota(v.begin(), v.end(), 1);    // {1,2,3,4,5} (starting from 1)
 
// --- transform: apply function to each element ---
transform(v.begin(), v.end(), v.begin(), [](int x){ return x * 2; });
// v = {2,4,6,8,10}
 
// Transform two ranges into one
vector<int> a = {1,2,3}, b = {4,5,6}, res(3);
transform(a.begin(), a.end(), b.begin(), res.begin(),
          [](int x, int y){ return x + y; });
// res = {5,7,9}
 
// --- replace ---
replace(v.begin(), v.end(), 4, 99);  // Replace all 4s with 99
 
// --- unique: remove consecutive duplicates (sort first!) ---
vector<int> dup = {1,1,2,2,3,3,1};
sort(dup.begin(), dup.end());        // {1,1,1,2,2,3,3}
auto newEnd = unique(dup.begin(), dup.end());  // {1,2,3,?,?,?,?}
dup.erase(newEnd, dup.end());        // {1,2,3}
 
// --- rotate ---
vector<int> r = {1,2,3,4,5};
rotate(r.begin(), r.begin()+2, r.end());  // {3,4,5,1,2} (rotate left by 2)
 
// --- copy ---
vector<int> src = {1,2,3}, dst(3);
copy(src.begin(), src.end(), dst.begin());
 
// --- shuffle ---
vector<int> deck(52);
iota(deck.begin(), deck.end(), 0);
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
shuffle(deck.begin(), deck.end(), rng);

#include <numeric>
 
vector<int> v = {1, 2, 3, 4, 5};
 
// --- accumulate: sum (or any fold operation) ---
int sum = accumulate(v.begin(), v.end(), 0);         // 15
int product = accumulate(v.begin(), v.end(), 1,
              [](int acc, int x){ return acc * x; });  // 120
 
// --- partial_sum: running totals ---
vector<int> ps(v.size());
partial_sum(v.begin(), v.end(), ps.begin());  // {1,3,6,10,15}
 
// --- gcd / lcm (C++17) ---
cout << __gcd(12, 8);         // 4 — classic C way
cout << gcd(12, 8);           // 4 — C++17 <numeric>
cout << lcm(4, 6);            // 12 — C++17 <numeric>

vector<int> v = {1, 2, 3};
 
// --- next_permutation: advances to next lexicographic permutation ---
do {
    for (int x : v) cout << x;
    cout << "\n";
} while (next_permutation(v.begin(), v.end()));
// Prints all 6 permutations: 123, 132, 213, 231, 312, 321
 
// --- prev_permutation: goes to previous permutation ---
vector<int> w = {3, 2, 1};
prev_permutation(w.begin(), w.end());  // {3, 1, 2}
 
// Warning: next_permutation starts from current arrangement — sort first for all perms
sort(v.begin(), v.end());
do { ... } while (next_permutation(v.begin(), v.end()));

#include <utility>
 
// Construction
pair<int, string> p1 = {42, "hello"};
pair<int, string> p2 = make_pair(42, "hello");  // Same
auto p3 = make_pair(42, "hello");               // auto deduction
 
// Access
cout << p1.first;   // 42
cout << p1.second;  // "hello"
 
// Structured binding (C++17)
auto [num, str] = p1;
 
// Comparison: lexicographic (by first, then second)
pair<int,int> a = {1, 3};
pair<int,int> b = {1, 5};
cout << (a < b);    // true (same first, compare second)
 
// Common DSA usage
vector<pair<int,int>> edges;     // Weighted graph edges: {weight, node}
map<int, pair<int,int>> coords;  // Map from id to (x,y) coordinate
priority_queue<pair<int,int>, vector<pair<int,int>>, greater<>> minPQ;

#include <tuple>
 
// Construction
tuple<int, string, double> t1 = {1, "hello", 3.14};
auto t2 = make_tuple(1, "hello", 3.14);
 
// Access — by index (compile-time!)
cout << get<0>(t1);   // 1
cout << get<1>(t1);   // "hello"
cout << get<2>(t1);   // 3.14
 
// Structured binding (C++17) — much cleaner
auto [id, name, score] = t1;
 
// Comparison: lexicographic
tuple<int,int,int> a = {1, 2, 3};
tuple<int,int,int> b = {1, 2, 4};
cout << (a < b);   // true
 
// DSA usage: edges with source, destination, weight
vector<tuple<int,int,int>> edges;  // {u, v, weight}
edges.emplace_back(0, 1, 5);
edges.emplace_back(1, 2, 3);
 
// Sort edges by weight (for Kruskal's MST)
sort(edges.begin(), edges.end(), [](const auto& a, const auto& b) {
    return get<2>(a) < get<2>(b);
});

#include <optional>
 
// Represents a value that may or may not be present
optional<int> findFirst(const vector<int>& v, int target) {
    for (int i = 0; i < (int)v.size(); i++) {
        if (v[i] == target) return i;   // Return found index
    }
    return nullopt;   // Return "nothing"
}
 
auto result = findFirst({3, 1, 4, 1, 5}, 4);
if (result.has_value()) {
    cout << result.value();   // 2
    // Or shorthand:
    cout << *result;          // 2
}

// ❌ Wrong: using <= instead of < causes undefined behavior in sort!
sort(v.begin(), v.end(), [](int a, int b) { return a <= b; });
 
// ✅ Correct: strict <
sort(v.begin(), v.end(), [](int a, int b) { return a < b; });

// Sort by multiple criteria
struct Student {
    string name;
    int grade;
    double gpa;
};
vector<Student> students;
 
// Sort: by grade descending, then gpa descending, then name ascending
sort(students.begin(), students.end(), [](const Student& a, const Student& b) {
    if (a.grade != b.grade) return a.grade > b.grade;  // Grade desc
    if (a.gpa != b.gpa)     return a.gpa > b.gpa;      // GPA desc
    return a.name < b.name;                             // Name asc
});
 
// Shorthand using tie (lexicographic)
sort(students.begin(), students.end(), [](const Student& a, const Student& b) {
    return tie(b.grade, b.gpa, a.name) < tie(a.grade, a.gpa, b.name);
    //     ^ swapped for desc          ^ normal for asc
});

// Custom-ordered set
auto cmp = [](int a, int b) { return abs(a) < abs(b); };  // Sort by absolute value
set<int, decltype(cmp)> absSet(cmp);
absSet.insert(-3);
absSet.insert(1);
absSet.insert(-2);
// Iteration order: 1, -2, -3 (by absolute value)
 
// Custom-keyed map (key comparison)
struct Point { int x, y; };
auto ptCmp = [](const Point& a, const Point& b) {
    return a.x < b.x || (a.x == b.x && a.y < b.y);
};
map<Point, string, decltype(ptCmp)> ptMap(ptCmp);

// MAX-heap (default behavior):
// priority_queue<int> is equivalent to:
priority_queue<int, vector<int>, less<int>> maxPQ;
// less<int>(a, b) = a < b: elements where a < b → b is on top
 
// MIN-heap:
priority_queue<int, vector<int>, greater<int>> minPQ;
// greater<int>(a, b) = a > b: elements where a > b → b is on top (b is smaller)
 
// Custom: min-heap ordered by distance (first element of pair)
auto distCmp = [](const pair<int,int>& a, const pair<int,int>& b) {
    return a.first > b.first;   // a "less than" b when a.first > b.first
                                // → b (smaller distance) ends up on top
};
priority_queue<pair<int,int>,
               vector<pair<int,int>>,
               decltype(distCmp)> distMinPQ(distCmp);