02 — STL Containers¶

#include <vector>

std::vector<int> v;                        // empty
std::vector<int> v2(5, 0);                // size 5, filled with 0
std::vector<int> v3 = {1, 2, 3, 4, 5};   // initializer list
std::vector<int> v4(v3.begin(), v3.end()); // copy from range

// Size and capacity
v3.size();       // 5  — number of elements
v3.capacity();   // >= 5 — allocated slots (implementation-defined)
v3.empty();      // false
v3.resize(8, 0); // extend to size 8, new elements = 0
v3.reserve(100); // allocate memory for 100 elements without changing size
v3.shrink_to_fit(); // release excess capacity

// Element access
v3[2];           // unchecked — UB if out-of-range
v3.at(2);        // checked — throws std::out_of_range
v3.front();      // first element
v3.back();       // last element
v3.data();       // raw pointer to underlying array

// Modifiers
v3.push_back(6);            // add to end
v3.emplace_back(7);         // construct in-place at end (prefer over push_back for objects)
v3.pop_back();              // remove from end
v3.insert(v3.begin()+1, 99); // insert 99 at index 1 — O(n)
v3.erase(v3.begin()+2);     // erase element at index 2 — O(n)
v3.erase(v3.begin(), v3.begin()+2); // erase range [0,2) — O(n)
v3.clear();                 // remove all elements, keep capacity

// 2D vector
std::vector<std::vector<int>> grid(3, std::vector<int>(4, 0)); // 3x4 grid of zeros

// Iteration
for (int x : v3) { /* range-for */ }
for (auto it = v3.begin(); it != v3.end(); ++it) { /* iterator */ }
for (int i = 0; i < (int)v3.size(); ++i) { /* index — cast to int to avoid signed/unsigned warning */ }

// Important: iterator invalidation
// push_back/reserve CAN invalidate ALL iterators if reallocation occurs
// insert/erase invalidate iterators at and after the point of change

#include <deque>

std::deque<int> dq = {1, 2, 3};

dq.push_back(4);    // add to end
dq.push_front(0);   // add to front — O(1)
dq.pop_back();      // remove from end
dq.pop_front();     // remove from front — O(1)

dq[2];              // random access — O(1)
dq.front();         // first element
dq.back();          // last element

// Monotonic deque (sliding window max/min) — see file 08

#include <list>

std::list<int> lst = {1, 2, 3, 4};

lst.push_back(5);
lst.push_front(0);
lst.pop_back();
lst.pop_front();

// Splicing — O(1) move of elements between lists
std::list<int> other = {10, 20};
auto it = std::next(lst.begin(), 2); // iterator to 3rd element
lst.splice(it, other);               // insert all of 'other' before 'it'

lst.remove(3);          // remove all elements equal to 3 — O(n)
lst.remove_if([](int x){ return x % 2 == 0; }); // remove evens
lst.reverse();          // reverse in-place — O(n)
lst.sort();             // merge sort — O(n log n)
lst.unique();           // remove consecutive duplicates (sort first)
lst.merge(other);       // merge two sorted lists — O(n)

#include <array>

std::array<int, 5> a = {1, 2, 3, 4, 5};

a[0];           // unchecked access
a.at(0);        // checked access
a.front();      // first
a.back();       // last
a.size();       // 5 — compile-time constant
a.fill(0);      // set all elements to 0
a.data();       // raw pointer

// Structured binding (C++17)
auto [x1, x2, x3, x4, x5] = a;

// Use in 2D — static allocation, faster than vector<vector>
std::array<std::array<int,4>, 3> mat{};  // 3x4 zero-initialized

#include <set>

std::set<int> s = {3, 1, 4, 1, 5};  // {1, 3, 4, 5} — duplicates dropped

s.insert(2);        // O(log n)
s.erase(3);         // erase by value — O(log n)
s.count(4);         // 0 or 1 for set, 0..n for multiset
s.contains(4);      // C++20 — bool
s.find(4);          // iterator or s.end()
s.size();
s.empty();

// Bound tricks — critical for CP
s.lower_bound(x);  // first element >= x
s.upper_bound(x);  // first element > x

// Find largest element <= x
auto it = s.upper_bound(x);
if (it != s.begin()) {
    --it;
    int largest_leq_x = *it;
}

// Find smallest element >= x
auto it2 = s.lower_bound(x);
if (it2 != s.end()) {
    int smallest_geq_x = *it2;
}

// Erase a range
s.erase(s.lower_bound(3), s.upper_bound(7)); // erase all in [3,7]

// Reverse iteration
for (auto it = s.rbegin(); it != s.rend(); ++it) { /* descending */ }

// --- multiset ---
std::multiset<int> ms = {1, 2, 2, 3, 3, 3};

ms.count(3);           // 3
ms.erase(ms.find(2));  // erase exactly ONE occurrence of 2
ms.erase(2);           // erases ALL occurrences of 2 — be careful!

// Descending set using greater<>
std::set<int, std::greater<int>> desc_set = {3, 1, 4, 1, 5};
// Iteration: 5 4 3 1

// Lambda comparator (need decltype in template arg)
auto cmp = [](const std::string& a, const std::string& b) {
    return a.size() < b.size() || (a.size() == b.size() && a < b);
};
std::set<std::string, decltype(cmp)> str_set(cmp);
str_set.insert("banana");
str_set.insert("fig");
str_set.insert("apple");  // sorted by length, then lexicographically

// Custom struct comparator — must be strict weak ordering
struct ByCost {
    bool operator()(const std::pair<int,int>& a, const std::pair<int,int>& b) const {
        return a.second < b.second; // sort by second element
    }
};
std::set<std::pair<int,int>, ByCost> cost_set;

// Comparator in sort()
std::sort(v.begin(), v.end(), [](int a, int b){ return a > b; });

#include <map>

std::map<std::string, int> freq;

freq["apple"] = 3;                    // insert or update
freq.insert({"banana", 2});           // insert (no-op if key exists)
freq.emplace("cherry", 1);            // construct in-place
freq["date"];                         // inserts key "date" with value 0 if not present!

// Safe access without inserting
if (freq.count("apple"))  { int v = freq["apple"]; }
if (auto it = freq.find("apple"); it != freq.end()) { int v = it->second; }

freq.erase("banana");                 // erase by key
freq.erase(freq.begin());             // erase by iterator

// Iteration — key-value pairs in sorted key order
for (auto& [key, val] : freq) {
    std::cout << key << ": " << val << "\n";
}

// Bound tricks on map
auto lo = freq.lower_bound("b");   // first key >= "b"
auto hi = freq.upper_bound("c");   // first key > "c"

// --- multimap ---
std::multimap<int, std::string> mm;
mm.insert({1, "one"});
mm.insert({1, "uno"});  // duplicate key allowed

// Iterate all values for a key
auto [beg, end] = mm.equal_range(1);
for (auto it = beg; it != end; ++it) {
    std::cout << it->second << "\n";
}

#include <unordered_set>
#include <unordered_map>

std::unordered_set<int> us = {1, 2, 3};
us.insert(4);
us.erase(2);
us.count(3);       // 0 or 1
us.contains(3);    // C++20

std::unordered_map<std::string, int> um;
um["hello"] = 1;
um.count("hello"); // 1
um.erase("hello");

// Bucket API — useful for performance tuning
um.reserve(1000);            // pre-allocate for 1000 elements
um.max_load_factor(0.25);    // lower load factor = fewer collisions
um.bucket_count();           // number of buckets
um.load_factor();            // elements / buckets

// Custom hash for unordered containers
struct PairHash {
    size_t operator()(const std::pair<int,int>& p) const {
        // Combine hashes — shift+XOR is common in CP
        return std::hash<int>{}(p.first) ^ (std::hash<int>{}(p.second) << 32);
    }
};
std::unordered_map<std::pair<int,int>, int, PairHash> pair_map;

#include <chrono>

struct SafeHash {
    static uint64_t splitmix64(uint64_t x) {
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }

    size_t operator()(uint64_t x) const {
        // Seed with current time to randomize per-run
        static const uint64_t FIXED_RANDOM =
            std::chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }
};

// Usage — drop-in replacement for default unordered_map
std::unordered_map<int, int, SafeHash> safe_map;
std::unordered_set<int, SafeHash> safe_set;

#include <stack>
#include <queue>

// --- stack (LIFO, backed by deque by default) ---
std::stack<int> stk;
stk.push(1);
stk.push(2);
stk.top();      // 2 — peek without removing
stk.pop();      // remove top (no return value!)
stk.empty();
stk.size();

// Back with vector for better cache performance
std::stack<int, std::vector<int>> vec_stack;

// --- queue (FIFO, backed by deque) ---
std::queue<int> q;
q.push(1);
q.push(2);
q.front();      // 1 — peek front
q.back();       // 2 — peek back
q.pop();        // remove front
q.empty();

// --- priority_queue (max-heap by default) ---
std::priority_queue<int> pq;            // max-heap
pq.push(3);
pq.push(1);
pq.push(4);
pq.top();       // 4 — maximum element
pq.pop();       // remove maximum

// Min-heap — two idioms
std::priority_queue<int, std::vector<int>, std::greater<int>> min_pq;

// Negate values trick for min-heap with default pq
// pq.push(-val) then use -pq.top()

// Custom comparator for pairs (min-heap by first element)
using T = std::pair<int,int>;
std::priority_queue<T, std::vector<T>, std::greater<T>> pair_pq;
pair_pq.push({1, 100});
pair_pq.push({3, 50});
pair_pq.top(); // {1, 100} — smallest first

// Dijkstra-style: {dist, node}
std::priority_queue<std::pair<int,int>,
                    std::vector<std::pair<int,int>>,
                    std::greater<std::pair<int,int>>> dijkstra_pq;

#include <bitset>

const int N = 1000;
std::bitset<N> bs;                  // all zeros
std::bitset<N> bs2(0b1011);        // from integer literal
std::bitset<N> bs3("1010011");     // from string (rightmost = bit 0)

bs.set(5);          // set bit 5 to 1
bs.reset(5);        // set bit 5 to 0
bs.flip(5);         // toggle bit 5
bs.flip();          // toggle all bits
bs.set();           // set all bits to 1
bs.reset();         // set all bits to 0

bs[3];              // access bit 3 (unchecked)
bs.test(3);         // access bit 3 (checked — throws if out of range)

bs.count();         // number of set bits (popcount)
bs.any();           // true if any bit is set
bs.none();          // true if no bit is set
bs.all();           // true if all bits are set
bs.size();          // N — number of bits

// Bitwise operations — all O(N/64) using 64-bit words
bs & bs2;           // AND
bs | bs2;           // OR
bs ^ bs2;           // XOR
~bs;                // NOT
bs << 3;            // left shift
bs >> 3;            // right shift

// Convert to/from
bs.to_string();     // "000...1010011"
bs.to_ulong();      // unsigned long (UB if value doesn't fit)
bs.to_ullong();     // unsigned long long

// Bitset DP trick: count paths, subset queries in O(N^2/64)
// Example: dp[i] = bitset of reachable states from i
std::bitset<1001> dp[1001];
// dp[i] |= (dp[j] << cost[j][i]) for transitions

#include <string>
#include <string_view>

std::string s = "hello world";

// Access
s[0];               // 'h' — unchecked
s.at(0);            // 'h' — checked
s.front();          // 'h'
s.back();           // 'd'
s.data();           // const char* (null-terminated since C++11)
s.c_str();          // const char* (guaranteed null-terminated)

// Size
s.size();           // 11
s.length();         // 11 — identical to size()
s.empty();          // false

// Modification
s += " there";          // append
s.append("!");          // append
s.push_back('!');       // append single char
s.pop_back();           // remove last char
s.insert(5, ",");       // insert at position
s.erase(5, 1);          // erase 1 char at position 5
s.replace(0, 5, "hi");  // replace range with new string
s.clear();

// Search
s.find("world");        // position or std::string::npos
s.rfind("l");           // last occurrence
s.find_first_of("aeiou"); // first vowel
s.find_last_of("aeiou");  // last vowel
s.find_first_not_of(" \t\n"); // first non-whitespace

// Substrings
s.substr(0, 5);         // "hello" — copies! O(k)
s.compare(other);       // <0, 0, >0

// Conversions
std::to_string(42);         // int -> string
std::stoi("123");           // string -> int
std::stoll("1234567890123"); // string -> long long
std::stod("3.14");          // string -> double

// --- string_view (C++17) — zero-copy read-only reference ---
std::string_view sv = s;            // view into s
std::string_view sv2(s.data(), 5);  // view first 5 chars

sv.substr(0, 5);    // returns string_view — no allocation!
sv.remove_prefix(2); // advance start pointer
sv.remove_suffix(1); // retreat end pointer
sv.starts_with("he"); // C++20
sv.ends_with("lo");   // C++20

// CAUTION: string_view does not own memory — never return a string_view
// to a local string's data (dangling reference)
std::string_view bad() {
    std::string local = "hello";
    return local;  // ← dangling! local is destroyed on return
}

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;

// Order-statistics tree — supports order_of_key and find_by_order
// Equivalent to: set with O(log n) rank and select
typedef tree<int, null_type, std::less<int>,
             rb_tree_tag, tree_order_statistics_node_update>
        ordered_set;

ordered_set os;
os.insert(3);
os.insert(1);
os.insert(4);
os.insert(1); // duplicate — use pair<int,int> to allow duplicates

os.order_of_key(4);    // 2 — number of elements strictly less than 4
*os.find_by_order(0);  // 1 — 0-indexed element by rank
os.find_by_order(os.size()-1); // iterator to maximum element

// Multiset simulation: store {val, unique_id} pairs
ordered_set mos; // type: tree<pair<int,int>, null_type, less<pair<int,int>>, ...>
int id = 0;
// mos.insert({val, id++});
// mos.order_of_key({val, INT_MAX}); // count of elements <= val

// Erase
os.erase(os.find(3)); // erase one element

// Policy-based hash table (faster than unordered_map for integers)
gp_hash_table<int, int> ht;
ht.insert({1, 100});
ht[1]; // access

// 1. Frequency map
std::map<int, int> freq;
for (int x : arr) freq[x]++;

// 2. Coordinate compression
std::vector<int> vals = arr;             // copy
std::sort(vals.begin(), vals.end());
vals.erase(std::unique(vals.begin(), vals.end()), vals.end()); // remove duplicates
// compress: index of x in vals
auto compress = [&](int x) {
    return (int)(std::lower_bound(vals.begin(), vals.end(), x) - vals.begin());
};

// 3. Sliding window with multiset (maintain sorted window)
std::multiset<int> window;
for (int r = 0; r < n; r++) {
    window.insert(arr[r]);
    if ((int)window.size() > k) window.erase(window.find(arr[r-k]));
    // window.begin() = min, window.rbegin() = max
}

// 4. Two-sum with unordered_set
std::unordered_set<int> seen;
for (int x : arr) {
    if (seen.count(target - x)) { /* found pair */ }
    seen.insert(x);
}

// 5. Stack-based monotonic structure (NGE — Next Greater Element)
std::stack<int> stk;
std::vector<int> nge(n, -1);
for (int i = 0; i < n; i++) {
    while (!stk.empty() && arr[stk.top()] < arr[i]) {
        nge[stk.top()] = arr[i];
        stk.pop();
    }
    stk.push(i);
}

// 6. BFS queue idiom
std::queue<int> bfsq;
std::vector<bool> visited(n, false);
bfsq.push(start);
visited[start] = true;
while (!bfsq.empty()) {
    int u = bfsq.front(); bfsq.pop();
    for (int v : adj[u]) {
        if (!visited[v]) { visited[v] = true; bfsq.push(v); }
    }
}