#include <vector>

std::vector<int> v;                    // empty
std::vector<int> v(10);               // 10 elements, all 0
std::vector<int> v(10, -1);           // 10 elements, all -1
std::vector<int> v{1, 2, 3, 4, 5};   // initializer list

// Access
v[0];          // unchecked (fast, UB if out of bounds)
v.at(0);       // bounds-checked (throws std::out_of_range)
v.front();     // first element
v.back();      // last element
v.data();      // raw pointer to underlying array

// Modification
v.push_back(6);           // add to end — amortized O(1)
v.emplace_back(7);        // construct in-place (avoids copy)
v.pop_back();             // remove last — O(1)
v.insert(v.begin(), 0);   // insert at position — O(n)
v.erase(v.begin() + 2);   // erase at position — O(n)

// Size
v.size();      // current number of elements
v.capacity();  // allocated space (≥ size)
v.empty();     // true if size == 0
v.reserve(100);// pre-allocate (avoid reallocations!)
v.shrink_to_fit(); // release excess capacity
v.clear();     // remove all elements (size=0, capacity unchanged)

#include <set>

std::set<int> s{5, 3, 1, 4, 2};
// s = {1, 2, 3, 4, 5} — automatically sorted

s.insert(6);               // O(log n)
s.erase(3);                // O(log n)
s.count(4);                // 1 (exists) or 0 (doesn't)
s.find(4) != s.end();      // true if found
s.contains(4);             // C++20: cleaner

// Range queries
auto it = s.lower_bound(3);  // iterator to first element ≥ 3
auto it2 = s.upper_bound(3); // iterator to first element > 3

#include <map>

std::map<std::string, int> m;
m["alice"] = 90;
m["bob"] = 85;
m.insert({"charlie", 92});
m.emplace("dave", 88);

// Access
m["alice"];                   // 90 (WARNING: creates entry if key missing!)
m.at("alice");                // 90 (throws if key missing — safer)

// Check existence
if (m.count("alice")) { /* exists */ }
if (m.contains("alice")) { /* C++20 */ }

// Iterate (sorted by key)
for (const auto& [name, score] : m) {
    std::cout << name << ": " << score << "\n";
}

// C++17: insert_or_assign, try_emplace
m.insert_or_assign("alice", 95);  // insert or update
m.try_emplace("eve", 91);         // only insert if not present

struct PairHash {
    size_t operator()(const std::pair<int,int>& p) const {
        auto h1 = std::hash<int>{}(p.first);
        auto h2 = std::hash<int>{}(p.second);
        return h1 ^ (h2 << 32);  // combine hashes
    }
};

std::unordered_set<std::pair<int,int>, PairHash> ps;

#include <stack>
std::stack<int> st;
st.push(1); st.push(2);
st.top();    // 2
st.pop();    // removes 2

#include <queue>
std::queue<int> q;
q.push(1); q.push(2);
q.front();   // 1
q.back();    // 2
q.pop();     // removes 1

#include <queue>

// Max-heap (default)
std::priority_queue<int> pq;
pq.push(3); pq.push(1); pq.push(4);
pq.top();  // 4 (largest)
pq.pop();  // removes 4

// Min-heap
std::priority_queue<int, std::vector<int>, std::greater<int>> min_pq;
min_pq.push(3); min_pq.push(1); min_pq.push(4);
min_pq.top();  // 1 (smallest)

// Custom comparator
auto cmp = [](const auto& a, const auto& b) { return a.cost > b.cost; };
std::priority_queue<Node, std::vector<Node>, decltype(cmp)> pq(cmp);

#include <algorithm>

std::vector<int> v{1, 3, 5, 7, 9, 11};

// Linear search — O(n)
auto it = std::find(v.begin(), v.end(), 7);
if (it != v.end()) { /* found at position (it - v.begin()) */ }

// Binary search — O(log n) — REQUIRES SORTED DATA
bool found = std::binary_search(v.begin(), v.end(), 7);  // true

// Lower/upper bound — O(log n)
auto lb = std::lower_bound(v.begin(), v.end(), 5);  // first ≥ 5 → points to 5
auto ub = std::upper_bound(v.begin(), v.end(), 5);  // first > 5 → points to 7

// Find with predicate
auto it2 = std::find_if(v.begin(), v.end(), [](int x) { return x > 6; });
// points to 7

std::vector<int> v{5, 2, 8, 1, 9};

std::sort(v.begin(), v.end());                     // ascending: {1, 2, 5, 8, 9}
std::sort(v.begin(), v.end(), std::greater<int>()); // descending: {9, 8, 5, 2, 1}

// Custom sort
std::sort(v.begin(), v.end(), [](int a, int b) {
    return abs(a) < abs(b);  // sort by absolute value
});

// Partial sort — only first k elements sorted
std::partial_sort(v.begin(), v.begin() + 3, v.end());

// nth_element — O(n) average, finds the nth element
std::nth_element(v.begin(), v.begin() + 2, v.end());
// v[2] is the median; elements before it are smaller, after are larger

// Stable sort (preserves order of equal elements)
std::stable_sort(v.begin(), v.end());

// Transform
std::vector<int> v{1, 2, 3, 4, 5};
std::vector<int> squared(5);
std::transform(v.begin(), v.end(), squared.begin(), [](int x) { return x * x; });
// squared = {1, 4, 9, 16, 25}

// Fill
std::fill(v.begin(), v.end(), 0);

// Replace
std::replace(v.begin(), v.end(), 0, -1);  // replace all 0s with -1

// Remove-erase idiom (pre-C++20)
v.erase(std::remove(v.begin(), v.end(), 3), v.end());  // remove all 3s

// C++20: cleaner
std::erase(v, 3);                    // remove all 3s
std::erase_if(v, [](int x) { return x < 0; });  // remove negatives

// Unique (remove consecutive duplicates — sort first for all duplicates)
std::sort(v.begin(), v.end());
v.erase(std::unique(v.begin(), v.end()), v.end());

// Reverse & Rotate
std::reverse(v.begin(), v.end());
std::rotate(v.begin(), v.begin() + 2, v.end());  // {3,4,5,1,2}

#include <numeric>

std::vector<int> v{1, 2, 3, 4, 5};

int sum = std::accumulate(v.begin(), v.end(), 0);           // 15
int product = std::accumulate(v.begin(), v.end(), 1, std::multiplies<>());  // 120

// Partial sums (prefix sum)
std::vector<int> prefix(5);
std::partial_sum(v.begin(), v.end(), prefix.begin());  // {1, 3, 6, 10, 15}

// Inner product (dot product)
std::vector<int> w{5, 4, 3, 2, 1};
int dot = std::inner_product(v.begin(), v.end(), w.begin(), 0);  // 35

// Iota (fill with incrementing values)
std::iota(v.begin(), v.end(), 1);  // {1, 2, 3, 4, 5}

// GCD / LCM (C++17)
int g = std::gcd(12, 8);   // 4
int l = std::lcm(12, 8);   // 24

// Min/Max
int mn = *std::min_element(v.begin(), v.end());
int mx = *std::max_element(v.begin(), v.end());
auto [lo, hi] = std::minmax_element(v.begin(), v.end());

std::vector<int> v{3, 1, 4, 1, 5};
std::partial_sum(v.begin(), v.end(), v.begin());
// v = {3, 4, 8, 9, 14}  — modified in-place

std::vector<int> v{3, 1, 4, 1, 5};
std::vector<int> out(v.size());

// Running product
std::partial_sum(v.begin(), v.end(), out.begin(), std::multiplies<>());
// out = {3, 3, 12, 12, 60}

// Running maximum (prefix max)
std::partial_sum(v.begin(), v.end(), out.begin(),
    [](int a, int b) { return std::max(a, b); });
// out = {3, 3, 4, 4, 5}

// Running minimum (prefix min)
std::partial_sum(v.begin(), v.end(), out.begin(),
    [](int a, int b) { return std::min(a, b); });
// out = {3, 1, 1, 1, 1}

// Running XOR
std::partial_sum(v.begin(), v.end(), out.begin(), std::bit_xor<>());
// out = {3, 2, 6, 7, 2}

// Running GCD
std::partial_sum(v.begin(), v.end(), out.begin(),
    [](int a, int b) { return std::gcd(a, b); });

std::vector<int> a{2, 5, 1, 4, 3};
std::vector<int> P(a.size());
std::partial_sum(a.begin(), a.end(), P.begin());
// P = {2, 7, 8, 12, 15}

// Query: sum of a[1..3] = a[1] + a[2] + a[3]
int range_sum = P[3] - P[0];  // 12 - 2 = 10 ✓ (5 + 1 + 4 = 10)

// Query: sum of a[0..2]
int range_sum2 = P[2];  // 8 ✓ (2 + 5 + 1 = 8)

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

// Build difference array
std::vector<int> d(a.size());
std::adjacent_difference(a.begin(), a.end(), d.begin());
// d = {2, 3, -4, 3, -1}

// Recover original
std::vector<int> recovered(a.size());
std::partial_sum(d.begin(), d.end(), recovered.begin());
// recovered = {2, 5, 1, 4, 3} ✓  (original restored)

#include <numeric>
#include <execution>  // for parallel policies

std::vector<int> v{3, 1, 4, 1, 5};
std::vector<int> inc(5), exc(5);

// inclusive_scan: same as partial_sum
std::inclusive_scan(v.begin(), v.end(), inc.begin());
// inc = {3, 4, 8, 9, 14}

// exclusive_scan: excludes current element
std::exclusive_scan(v.begin(), v.end(), exc.begin(), 0);
// exc = {0, 3, 4, 8, 9}

// Parallel inclusive scan (requires associative op)
std::inclusive_scan(std::execution::par, v.begin(), v.end(), inc.begin());