C++11 STL Reference

// Constructors & basics
vector<int> v;                    // empty
vector<int> v(n);                 // size n, initialized to 0
vector<int> v(n, val);            // size n, all elements = val
vector<int> v{1, 2, 3};           // init list
vector<vector<int>> grid(m, vector<int>(n, 0));  // 2D array

// Core operations
v.push_back(x);                   // append
v.emplace_back(x);                // same as push_back (C++11)
v.pop_back();                     // remove last
v.back();                         // last element
v.front();                        // first element
v.size();                         // length
v.empty();                        // is empty?
v.clear();                        // remove all
v[i];                             // random access
v.at(i);                          // random access with bounds check

// Modification
v.resize(n);                      // resize to n (new elements = 0)
v.resize(n, val);                 // resize to n, new elements = val
v.insert(v.begin() + i, x);       // insert x at position i
v.erase(v.begin() + i);           // remove element at i
v.erase(v.begin() + i, v.begin() + j);  // remove [i, j)
v.assign(n, val);                 // set all to val

// Iteration
for (int i = 0; i < v.size(); ++i) v[i];
for (auto &x : v) x;              // reference, can modify
for (const auto &x : v) x;        // const reference

// Operations
v.reserve(n);                     // pre-allocate capacity (doesn't change size)
swap(v1, v2);                     // O(1) swap

// Constructors
string s = "hello";
string s(n, 'a');                 // n copies of 'a'
string s{...};

// Core operations
s.size();                         // length
s.length();                       // same as size()
s.empty();                        // is empty?
s[i];                             // character access (no bounds check)
s.back();                         // last character
s.front();                        // first character
s.push_back(c);                   // append character
s.pop_back();                     // remove last character
s += "world";                     // concatenate
s = "x" + s + "y";                // string concatenation

// Substring & search
s.substr(pos);                    // from pos to end
s.substr(pos, len);               // from pos, length len (NOT pos, end!)
s.find(str);                      // find first occurrence of str; npos if not found
s.find(str, pos);                 // find from pos onward
s.rfind(str);                     // find last occurrence
size_t idx = s.find("world");
if (idx != string::npos) { ... }  // check if found

// Character operations
for (char c : s) c;
for (int i = 0; i < s.size(); ++i) s[i];
c - 'a';                          // convert char to 0-25
(char)('a' + 0);                  // convert 0-25 back to char

// Conversions
string s = to_string(42);         // int to string
int x = stoi(s);                  // string to int
long long y = stoll(s);           // string to long long
double d = stod(s);               // string to double

// Manipulation
reverse(s.begin(), s.end());      // reverse in-place
sort(s.begin(), s.end());         // sort characters
s.erase(pos);                     // erase from pos to end
s.erase(pos, len);                // erase len chars starting at pos

// pair
pair<int, int> p = {3, 5};
pair<int, string> p = make_pair(1, "hello");
int x = p.first;
int y = p.second;

// Comparison: pairs compare lexicographically
pair<int, int> a = {1, 2}, b = {1, 3};
if (a < b) { ... }               // true: first equal, second < third

// In containers (sorted by first, then second)
set<pair<int, int>> s;
s.insert({1, 2});

// tuple (C++11)
tuple<int, string, double> t = make_tuple(1, "x", 3.14);
int a = get<0>(t);
string b = get<1>(t);
double c = get<2>(t);

// Comparison: lexicographic by default
tuple<int, int> t1 = {1, 2}, t2 = {1, 3};
if (t1 < t2) { ... }

// stack
stack<int> st;
st.push(x);                       // add to top
int t = st.top();                 // peek at top
st.pop();                         // remove from top (no return value)
st.empty();
st.size();

// queue
queue<int> q;
q.push(x);                        // add to back
int f = q.front();                // peek at front
q.pop();                          // remove from front
q.empty();
q.size();

// deque (double-ended queue)
deque<int> dq;
dq.push_back(x);                  // O(1)
dq.push_front(x);                 // O(1)
dq.pop_back();                    // O(1)
dq.pop_front();                   // O(1)
dq.back();
dq.front();
dq[i];                            // random access!
dq.size();

// Typical BFS
queue<int> q;
q.push(start);
while (!q.empty()) {
    int u = q.front();
    q.pop();
    // process u...
}

// max-heap (default)
priority_queue<int> pq;
pq.push(x);                       // add element
int mx = pq.top();                // peek at max
pq.pop();                         // remove max
pq.empty();
pq.size();

// min-heap
priority_queue<int, vector<int>, greater<int>> pq;
pq.push(x);
int mn = pq.top();                // peek at min
pq.pop();

// Custom comparator (struct with operator())
struct Cmp {
    bool operator()(const int &a, const int &b) const {
        return a > b;             // min-heap (inverted: > means "a is smaller")
    }
};
priority_queue<int, vector<int>, Cmp> pq;

// With pairs: default sorts by first, then second
priority_queue<pair<int, int>> pq;  // max-heap on first
pq.push({2, "a"});
pq.push({1, "b"});
auto [p, q] = pq.top();  // INVALID in C++11! Use .first, .second

// C++11-compliant way
pair<int, string> top = pq.top();
int dist = top.first;
string name = top.second;
pq.pop();

// Custom struct for top-k by value
struct Person {
    int val;
    string name;
};
struct PersonCmp {
    bool operator()(const Person &a, const Person &b) const {
        return a.val > b.val;     // min-heap (inverted)
    }
};
priority_queue<Person, vector<Person>, PersonCmp> pq;

// set
set<int> s;
s.insert(x);                      // add element
s.erase(x);                       // remove by value (all instances in multiset!)
s.erase(s.find(x));               // remove one instance
s.count(x);                       // 1 if found, 0 if not
s.find(x);                        // iterator if found, s.end() if not
s.empty();
s.size();

// min/max
int mn = *s.begin();              // smallest
int mx = *s.rbegin();             // largest
s.clear();

// Iteration (sorted order)
for (auto it = s.begin(); it != s.end(); ++it) {
    int x = *it;
}
for (const auto &x : s) { ... }

// Searching
auto it = s.lower_bound(x);       // first element >= x
auto it = s.upper_bound(x);       // first element > x
int cnt = s.upper_bound(x) - s.lower_bound(x);  // count of x in set (0 or 1)

// Iterator navigation
auto it = s.find(x);
if (it != s.end()) {
    auto next = next(it);         // next element
    auto prev = prev(it);         // previous element
}

// multiset (same as set, but allows duplicates)
multiset<int> ms;
ms.insert(5);
ms.insert(5);
ms.insert(5);
ms.count(5);                      // returns 3
ms.erase(5);                      // removes ALL 3!
ms.erase(ms.find(5));             // removes ONE

// Custom comparator (default is operator<, i.e., ascending)
set<int, greater<int>> s;         // descending

// map
map<int, string> m;
m[key] = value;                   // insert or update (inserts default if missing!)
m.insert({key, value});           // insert; no update
m.erase(key);                     // remove by key
m.count(key);                     // 1 or 0
m.find(key);                      // iterator or m.end()
m.empty();
m.size();

// Access (read-only to avoid insertion)
auto it = m.find(key);
if (it != m.end()) {
    string val = it->second;
}

// Iteration (sorted by key)
for (auto &p : m) {
    int key = p.first;
    string val = p.second;
}
for (auto it = m.begin(); it != m.end(); ++it) {
    int key = it->first;
    string val = it->second;
}

// Searching
auto it = m.lower_bound(key);     // first key >= key
auto it = m.upper_bound(key);     // first key > key

// multimap (same interface, allows duplicate keys)
multimap<int, string> mm;
mm.insert({1, "a"});
mm.insert({1, "b"});
auto range = mm.equal_range(1);   // pair of iterators [lower, upper)
for (auto it = range.first; it != range.second; ++it) {
    // all values for key 1
}

// unordered_set
unordered_set<int> s;
s.insert(x);
s.erase(x);
s.count(x);                       // 1 or 0
s.find(x);
s.empty();
s.size();

// unordered_map
unordered_map<int, string> m;
m[key] = value;                   // O(1) average
m.find(key);                      // O(1) average
m.erase(key);
m.count(key);

// Iteration (no guaranteed order)
for (const auto &x : s) { ... }
for (auto &p : m) {
    int key = p.first;
    string val = p.second;
}

// Custom hash for pair<int, int> (common in contests)
struct PairHash {
    size_t operator()(const pair<int, int> &p) const {
        return hash<long long>()(((long long)p.first << 32) | (long long)p.second);
    }
};
unordered_set<pair<int, int>, PairHash> s;

// Or use map if pair hashing is annoying
map<pair<int, int>, int> m;       // ordered, but works

// Iterator basics
vector<int> v = {1, 2, 3};
auto it = v.begin();              // forward iterator to first
auto it = v.end();                // forward iterator to one-past-last (don't dereference!)

// Bidirectional iterators (set, map, deque, list)
set<int> s;
auto it = s.begin();
auto it = s.rbegin();             // reverse iterator

// Random-access iterators (vector, deque, string)
vector<int> v;
v[i];                             // direct access
auto it = v.begin() + 5;          // move forward 5 positions
auto dist = v.end() - v.begin();  // distance O(1) for vector

// Iterator operations
advance(it, k);                   // move iterator k steps (O(k) for list, O(1) for deque/vector)
int dist = distance(it1, it2);    // distance between two iterators
auto next_it = next(it);          // iterator to next element (doesn't modify it)
auto prev_it = prev(it);          // iterator to previous element
it = prev(it);                    // move backward

// Loops
for (auto it = v.begin(); it != v.end(); ++it) {
    int x = *it;                  // dereference
}

// Remove-erase idiom
v.erase(remove(v.begin(), v.end(), val), v.end());  // remove all val
vector<int> new_v;
copy_if(v.begin(), v.end(), back_inserter(new_v), [](int x) { return x > 0; });

// Sorting
sort(v.begin(), v.end());         // O(n log n) average
sort(v.begin(), v.end(), greater<int>());  // descending
sort(v.begin(), v.end(), [](int a, int b) { return a > b; });

// Sorting pairs: default by first, then second
vector<pair<int, string>> v;
sort(v.begin(), v.end());         // ascending by first, then second

// Stable sort (preserves relative order of equal elements)
stable_sort(v.begin(), v.end());  // O(n log n)

// Searching (on sorted ranges)
bool found = binary_search(v.begin(), v.end(), x);  // O(log n)
auto it = lower_bound(v.begin(), v.end(), x);  // first >= x, O(log n)
auto it = upper_bound(v.begin(), v.end(), x);  // first > x, O(log n)

// Other utilities
reverse(v.begin(), v.end());      // O(n)
int mx = *max_element(v.begin(), v.end());    // O(n)
int mn = *min_element(v.begin(), v.end());    // O(n)
int sum = accumulate(v.begin(), v.end(), 0); // O(n), third arg is initial value
int cnt = count(v.begin(), v.end(), x);       // count x, O(n)
auto it = find(v.begin(), v.end(), x);       // find first x, O(n)

// Permutations
next_permutation(v.begin(), v.end());  // next lexicographic permutation, O(n)
prev_permutation(v.begin(), v.end());  // previous, O(n)

// Fill & initialize
fill(v.begin(), v.end(), val);        // set all to val, O(n)
iota(v.begin(), v.end(), 0);          // fill with 0, 1, 2, ... (C++11), O(n)

// Math
int g = __gcd(a, b);                  // GCD (not in std::, use __gcd or roll your own)
int minv = min(a, b);
int maxv = max(a, b);
auto res = minmax(a, b);              // pair<T,T> with min and max

// Lambda basics (C++11)
auto f = [](int x) { return x * 2; };
f(5);                             // 10

// Captures: [&] all by ref, [=] all by value, [x] specific
vector<int> v = {1, 2, 3};
int target = 5;
int cnt = count_if(v.begin(), v.end(), [&](int x) { return x < target; });

// Sort with lambda (works in algorithms)
sort(v.begin(), v.end(), [](int a, int b) { return a > b; });  // descending

// With return type (sometimes needed)
auto f = [](int x) -> int { return x * 2; };

// For custom comparators in set/map/pq, prefer functors (not lambdas)
// Reason: set/map need comparator type at compile-time
struct Cmp {
    bool operator()(int a, int b) const { return a > b; }
};
set<int, Cmp> s;
priority_queue<int, vector<int>, Cmp> pq;

// But lambdas work fine in sort, count_if, find_if, etc.
vector<pair<int, int>> v = {{1, 5}, {2, 3}};
sort(v.begin(), v.end(), [](const pair<int,int> &a, const pair<int,int> &b) {
    return a.second < b.second;
});

// Builtin functions (gcc/clang)
int x = 12;  // binary: 1100
__builtin_popcount(x);            // number of 1-bits: 2
__builtin_ctz(x);                 // count trailing zeros: 2
__builtin_clz(x);                 // count leading zeros (in 32-bit int): 28

// 64-bit versions
long long y = 12LL;
__builtin_popcountll(y);          // popcount for long long
__builtin_ctzll(y);               // trailing zeros for long long
__builtin_clzll(y);               // leading zeros for long long

// Useful bit tricks
x & -x;                           // isolate lowest set bit: (x & -x) == 12 & -12 == 4
x & (x - 1);                      // clear lowest set bit: 12 & 11 == 8
(1 << k);                         // 2^k
(1LL << k);                       // 2^k for large k (avoid overflow)
(1 << 30) - 1;                    // set lowest 30 bits
x >> k;                           // right shift (divide by 2^k)
x << k;                           // left shift (multiply by 2^k)

// Manual bit operations
bool get_bit(int x, int k) { return (x >> k) & 1; }
int set_bit(int x, int k) { return x | (1 << k); }
int clear_bit(int x, int k) { return x & ~(1 << k); }
int toggle_bit(int x, int k) { return x ^ (1 << k); }

// Check if power of 2
(x > 0) && ((x & (x - 1)) == 0);

// Integer limits
INT_MAX;                          // 2^31 - 1 = 2147483647
INT_MIN;                          // -2^31 = -2147483648
LLONG_MAX;                        // 2^63 - 1
LLONG_MIN;                        // -2^63

// Or use numeric_limits (C++11)
numeric_limits<int>::max();       // same as INT_MAX
numeric_limits<int>::min();       // same as INT_MIN
numeric_limits<long long>::max();

// Absolute value
abs(x);                           // int
llabs(x);                         // long long (or abs in <cstdlib>)
abs(-5);                          // 5

// Power (beware floating point)
pow(2.0, 10);                     // 1024.0 (returns double, not exact for large ints)
// Better: roll your own for ints
long long power(long long a, int b) {
    long long res = 1;
    while (b--) res *= a;
    return res;
}

// Floating-point output
cout << fixed << setprecision(10) << 3.14159;  // prints "3.1415900000"

// Fast I/O
ios_base::sync_with_stdio(false);
cin.tie(NULL);

// Overflow check
if (a > LLONG_MAX / b) { /* overflow would occur */ }
// Or cast to long long before multiplying
long long prod = (long long)a * b;