C++ STL Syntax for DSA

vector<int> a;                        // empty
vector<int> b(5, 0);                  // [0, 0, 0, 0, 0]
vector<int> c = {3, 1, 2};            // initializer list
int r = 3, col = 4;
vector<vector<int>> g(r, vector<int>(col, -1)); // 3 x 4 grid, all -1
int arr[4] = {};                      // plain C array, all 0
cout << c.size() << " " << g.size() << " " << g[0].size(); // 3 3 4

vector<int> v;
v.push_back(1);
v.push_back(2);
v.emplace_back(3);           // constructs in place: [1, 2, 3]
cout << v.back() << " ";     // 3
v.pop_back();                // [1, 2]
vector<pair<int, int>> ps;
ps.emplace_back(4, 5);       // no make_pair needed
cout << v.size();            // 2

vector<int> v;
cout << v.empty() << " " << v.size() << "\n";  // 1 0
// for (int i = 0; i < v.size() - 1; i++)      // BUG: size() - 1 wraps around
int n = v.size();                              // cast to int once
for (int i = 0; i < n - 1; i++) {}             // safe
cout << n - 1;                                 // -1

vector<int> v = {4, 5, 6};
for (int i = 0; i < (int)v.size(); i++) cout << v[i] << " "; // 4 5 6
for (int x : v) x *= 2;                 // copies: v unchanged
for (auto& x : v) x *= 2;               // references: v = [8, 10, 12]
for (const auto& x : v) cout << x << " "; // 8 10 12

vector<int> dist(4);
fill(dist.begin(), dist.end(), INT_MAX);   // all INT_MAX
vector<int> v = {1, 2, 3};
v.resize(5);                               // [1, 2, 3, 0, 0]
v.resize(2);                               // [1, 2]
v.assign(3, 7);                            // [7, 7, 7]
vector<vector<int>> memo(3, vector<int>(3, -1)); // 2D: fill at construction
cout << v[0] + v[2] << " " << memo[2][2];  // 14 -1

vector<int> v = {5, 2, 9, 1};
sort(v.begin(), v.end());           // [1, 2, 5, 9]
reverse(v.begin(), v.end());        // [9, 5, 2, 1]
sort(v.begin(), v.begin() + 2);     // first two only: [5, 9, 2, 1]
cout << v[0] << " " << v[1];        // 5 9

vector<int> v = {3, 7, 2};
int sum = accumulate(v.begin(), v.end(), 0);            // 12
long long big = accumulate(v.begin(), v.end(), 0LL);    // sums in long long
int mx = *max_element(v.begin(), v.end());              // 7
int idx = min_element(v.begin(), v.end()) - v.begin();  // 2 (index of the min)
cout << sum << " " << big << " " << mx << " " << idx;   // 12 12 7 2

vector<int> parent(5);
iota(parent.begin(), parent.end(), 0);     // [0, 1, 2, 3, 4] (DSU init)
vector<int> v = {1, 2, 2, 3};
cout << count(v.begin(), v.end(), 2) << " "; // 2
auto it = find(v.begin(), v.end(), 3);
if (it != v.end()) cout << it - v.begin();   // 3 (its index)

string s = "code";
cout << s.size() << " " << s.length() << " " << s[0] << "\n"; // 4 4 c
s[0] = 'C';                    // "Code"
s += "rs";                     // "Coders"
s.push_back('!');              // "Coders!"
s.pop_back();                  // "Coders"
cout << s << " " << s.back();  // Coders s

string s = "interview";
cout << s.substr(5, 3) << "\n";   // vie  (start 5, length 3)
cout << s.substr(5) << "\n";      // view (to the end)
int i = 0, j = 5;                 // want the half-open range [i, j)
cout << s.substr(i, j - i);       // inter

string s = "banana";
cout << s.find("an") << " ";       // 1
cout << s.find("an", 2) << " ";    // 3 (search from index 2)
cout << s.rfind('a') << " ";       // 5 (last match)
if (s.find("xyz") == string::npos) cout << "missing"; // missing

int n = stoi("42");
long long big = stoll("9000000000");
string s = to_string(n + 1);       // "43"
int d = '7' - '0';                 // 7
char ch = '0' + 5;                 // '5'
cout << s << " " << big + 1 << " " << d << " " << ch; // 43 9000000001 7 5

string s = "abca";
vector<int> freq(26, 0);
for (char c : s) freq[c - 'a']++;          // 'a' -> 0, 'b' -> 1, ...
cout << freq[0] << " " << freq[2] << "\n"; // 2 1
char next = 'a' + 1;                       // 'b'
cout << next << " " << (int)'A';           // b 65

string s = "A1b!";
for (char c : s) {
    if (isdigit(c)) cout << "digit ";
    else if (isalpha(c)) cout << (char)tolower(c) << " ";
    else cout << "other ";
}                                                // a digit b other
cout << (bool)isalnum('z') << " " << (char)toupper('q'); // 1 Q

string s = "stack";
string r(s.rbegin(), s.rend());     // reversed copy: "kcats"
reverse(s.begin(), s.end());        // in place: "kcats"
string t = "listen";
sort(t.begin(), t.end());           // "eilnst"
cout << s << " " << t << " " << r;  // kcats eilnst kcats

stringstream ss("the quick  brown fox");
string word;
vector<string> words;
while (ss >> word) words.push_back(word);   // split on whitespace
cout << words.size() << "\n";               // 4
stringstream ss2("a,b,,c");
string tok;
while (getline(ss2, tok, ',')) cout << "[" << tok << "]"; // [a][b][][c]

string a = "apple", b = "apricot";
cout << (a == b) << " " << (a < b) << "\n";  // 0 1
cout << (a.compare(b) < 0) << "\n";          // 1
string c = "Zoo";
cout << (c < a);                             // 1

unordered_map<string, int> m;
m["a"] = 1;                  // insert or overwrite
m.insert({"b", 2});          // insert only if the key is new
m.insert({"a", 99});         // ignored: "a" already exists
cout << m["a"] << " ";       // 1
cout << m["zzz"] << " ";     // 0  <- this line just inserted "zzz"!
cout << m.size();            // 3

unordered_map<int, int> m = {{1, 10}, {2, 20}};
if (m.count(1)) cout << "has1 ";         // has1
auto it = m.find(2);
if (it != m.end()) cout << it->second;   // 20  (it->first is the key)
// C++20: if (m.contains(1)) ...

unordered_map<int, int> m = {{1, 10}, {2, 20}, {3, 30}};
cout << m.erase(2) << " ";           // 1 (one key removed)
auto it = m.find(3);
if (it != m.end()) m.erase(it);      // by iterator
cout << m.size() << " " << m.count(2); // 1 0

map<string, int> m = {{"b", 2}, {"a", 1}};
for (auto& [k, v] : m) cout << k << "=" << v << " "; // a=1 b=2
for (auto& p : m) p.second *= 10;    // older style: p.first / p.second
cout << m["b"];                       // 20

vector<int> nums = {3, 1, 3, 2, 3};
unordered_map<int, int> freq;
for (int x : nums) freq[x]++;
cout << freq[3] << " " << freq[2] << " " << freq.size(); // 3 1 3

vector<string> words = {"eat", "tea", "tan", "ate"};
unordered_map<string, vector<string>> groups;
for (auto& w : words) {
    string key = w;
    sort(key.begin(), key.end());
    groups[key].push_back(w);
}
cout << groups["aet"].size() << " " << groups.size(); // 3 2

map<int, string> m = {{10, "a"}, {20, "b"}, {30, "c"}};
auto it = m.lower_bound(15);            // first key >= 15
cout << it->first << " ";               // 20
it = m.upper_bound(20);                 // first key > 20
cout << it->first << " ";               // 30
auto f = m.upper_bound(25);             // floor(25): step back once
if (f != m.begin()) cout << prev(f)->first; // 20

map<int, int> m = {{5, 1}, {1, 2}, {9, 3}};
cout << m.begin()->first << " ";       // 1 (smallest)
cout << prev(m.end())->first << " ";   // 9 (largest)
cout << m.rbegin()->first << "\n";     // 9 (same thing)
m.erase(m.begin());                    // pop the smallest
cout << m.begin()->first;              // 5

unordered_set<int> s;
auto [it, added] = s.insert(5);
cout << added << " ";              // 1 (new)
cout << s.insert(5).second << " "; // 0 (duplicate ignored)
cout << s.count(5) << " ";         // 1
s.erase(5);
cout << s.size();                  // 0

vector<int> v = {3, 1, 3, 2, 1};
unordered_set<int> seen(v.begin(), v.end());   // 3 distinct values
set<int> ordered(v.begin(), v.end());          // {1, 2, 3}
cout << seen.size() << " " << *ordered.begin() << " "; // 3 1
sort(v.begin(), v.end());
v.erase(unique(v.begin(), v.end()), v.end());  // [1, 2, 3]
cout << v.size();                              // 3

set<int> s = {40, 10, 30, 20};
cout << *s.begin() << " " << *s.rbegin() << " "; // 10 40
auto it = s.lower_bound(25);                     // first value >= 25
cout << *it << " ";                              // 30
s.erase(s.begin());                              // remove smallest
cout << *s.begin();                              // 20

multiset<int> ms = {5, 5, 5, 7};
ms.erase(ms.find(5));        // removes ONE 5
cout << ms.count(5) << " ";  // 2
ms.erase(5);                 // removes ALL remaining 5s
cout << ms.size();           // 1

priority_queue<int> pq;
for (int x : {3, 9, 1}) pq.push(x);
cout << pq.top() << " ";              // 9
pq.pop();                             // removes 9, returns nothing
cout << pq.top() << " " << pq.size(); // 3 2

priority_queue<int, vector<int>, greater<int>> pq;
for (int x : {3, 9, 1}) pq.push(x);
while (!pq.empty()) {
    cout << pq.top() << " ";   // 1 3 9
    pq.pop();
}

// {distance, node}
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq;
pq.push({5, 1});
pq.push({2, 3});
pq.push({2, 0});
auto [d, u] = pq.top();      // smallest distance, ties by node
cout << d << " " << u;       // 2 0

// min-heap on .second
auto cmp = [](const pair<int, int>& a, const pair<int, int>& b) {
    return a.second > b.second;
};
priority_queue<pair<int, int>, vector<pair<int, int>>, decltype(cmp)> pq(cmp);
pq.push({1, 50});
pq.push({2, 10});
pq.push({3, 30});
cout << pq.top().first;     // 2 (smallest .second)

vector<int> nums = {4, 1, 7, 3, 8, 5};
int k = 3;
priority_queue<int, vector<int>, greater<int>> pq;
for (int x : nums) {
    pq.push(x);
    if ((int)pq.size() > k) pq.pop();  // drop the smallest
}
cout << pq.top();                      // 5 (3rd largest)

stack<int> st;
st.push(1);
st.push(2);
cout << st.top() << " ";               // 2
st.pop();
cout << st.top() << " " << st.size();  // 1 1

queue<int> q;
q.push(1); q.push(2); q.push(3);
cout << q.front() << " " << q.back() << " "; // 1 3
q.pop();                                     // removes 1
cout << q.front();                           // 2

vector<vector<int>> adj = {{1, 2}, {3}, {3}, {}};  // node -> neighbours
vector<int> dist(adj.size(), -1);
queue<int> q;
q.push(0); dist[0] = 0;
while (!q.empty()) {
    int u = q.front(); q.pop();
    for (int v : adj[u])
        if (dist[v] == -1) { dist[v] = dist[u] + 1; q.push(v); }
}
cout << dist[3];   // 2

deque<int> dq = {2, 3};
dq.push_front(1);   // [1, 2, 3]
dq.push_back(4);    // [1, 2, 3, 4]
dq.pop_front();     // [2, 3, 4]
dq.pop_back();      // [2, 3]
cout << dq.front() << " " << dq.back() << " " << dq[0]; // 2 3 2

vector<int> a = {1, 3, -1, -3, 5, 3};
int k = 3;
deque<int> dq;                                                  // indices
for (int i = 0; i < (int)a.size(); i++) {
    if (!dq.empty() && dq.front() <= i - k) dq.pop_front();    // left the window
    while (!dq.empty() && a[dq.back()] <= a[i]) dq.pop_back(); // can never win
    dq.push_back(i);
    if (i >= k - 1) cout << a[dq.front()] << " ";              // 3 3 5 5
}

vector<int> v = {5, -2, 3, -8};
sort(v.begin(), v.end(), [](int a, int b) { return abs(a) < abs(b); });
// [-2, 3, 5, -8]
vector<int> score = {30, 10, 20}, idx = {0, 1, 2};
sort(idx.begin(), idx.end(), [&](int i, int j) { return score[i] < score[j]; });
cout << v[0] << " " << idx[0] << " " << idx[2];  // -2 1 0

vector<int> v = {2, 9, 4};
sort(v.begin(), v.end(), greater<int>());                     // [9, 4, 2]
sort(v.rbegin(), v.rend());                                   // also descending
sort(v.begin(), v.end(), [](int a, int b) { return a > b; }); // same again
cout << v[0] << " " << v[2];                                  // 9 2

vector<pair<int, int>> p = {{2, 5}, {1, 9}, {2, 1}};
sort(p.begin(), p.end());          // [(1,9), (2,1), (2,5)]
sort(p.begin(), p.end(), [](auto& a, auto& b) { return a.second < b.second; });
// by second: [(2,1), (2,5), (1,9)]
cout << p[0].first << " " << p[2].second;  // 2 9

vector<pair<string, int>> s = {{"bob", 2}, {"amy", 1}, {"cat", 2}};
stable_sort(s.begin(), s.end(), [](auto& a, auto& b) { return a.second < b.second; });
for (auto& [name, g] : s) cout << name << " ";   // amy bob cat

struct Job {
    int start, end;
    bool operator<(const Job& o) const { return end < o.end; } // by end time
};
vector<Job> jobs = {{1, 9}, {2, 4}, {3, 6}};
sort(jobs.begin(), jobs.end());
cout << jobs[0].end << " " << jobs[2].end;   // 4 9

vector<int> v = {7, 2, 9, 4, 1};
int k = 2;                                      // 0-based: 3rd smallest
nth_element(v.begin(), v.begin() + k, v.end());
cout << v[k];                                   // 4

vector<int> v = {1, 3, 3, 3, 8};
cout << binary_search(v.begin(), v.end(), 3) << "\n";    // 1 (found)
int lo = lower_bound(v.begin(), v.end(), 3) - v.begin(); // 1
int hi = upper_bound(v.begin(), v.end(), 3) - v.begin(); // 4
cout << lo << " " << hi << " " << hi - lo;               // 1 4 3

pair<int, string> p = {1, "one"};
auto q = make_pair(2, string("two"));
cout << p.first << " " << q.second << "\n";  // 1 two
cout << (p < q);                             // 1

tuple<int, int, string> t = {3, 4, "x"};
cout << get<0>(t) << " " << get<2>(t) << "\n"; // 3 x
auto [a, b, c] = t;                            // C++17
int x, y;
tie(x, y) = make_pair(7, 8);
cout << a + b << " " << x << " " << y;         // 7 7 8

struct ListNode {
    int val; ListNode* next;
    ListNode(int x) : val(x), next(nullptr) {}
};
ListNode dummy(0);                  // lives on the stack
ListNode* tail = &dummy;
for (int x : {1, 2, 3}) { tail->next = new ListNode(x); tail = tail->next; }
ListNode* head = dummy.next;        // the real head
for (ListNode* cur = head; cur; cur = cur->next) cout << cur->val << " "; // 1 2 3

struct TreeNode {
    int val; TreeNode *left, *right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
TreeNode* root = new TreeNode(1);
root->left = new TreeNode(2);
root->left->left = new TreeNode(3);
function<int(TreeNode*)> height = [&](TreeNode* n) {
    return n ? 1 + max(height(n->left), height(n->right)) : 0;
};
cout << height(root);   // 3

int a = INT_MAX;                    // 2147483647
long long prod = 1LL * a * 2;       // promote first
// int bad = a * 2;                 // overflow: undefined behaviour
cout << INT_MIN << " " << prod << "\n"; // -2147483648 4294967294
cout << LLONG_MAX;                  // 9223372036854775807

const int MOD = 1e9 + 7;
long long x = 1;
for (int i = 0; i < 40; i++) x = x * 2 % MOD;   // 2^40 mod MOD
cout << x << "\n";                              // 511620083
int a = 3, b = 5;
cout << ((a - b) % MOD + MOD) % MOD;            // 1000000005

int x = 12;                               // binary 1100
cout << __builtin_popcount(x) << " ";     // 2 (set bits)
cout << __builtin_ctz(x) << " ";          // 2 (trailing zeros)
cout << (x & (x - 1)) << " ";             // 8 (lowest set bit cleared)
cout << (x & -x) << " ";                  // 4 (lowest set bit alone)
cout << ((x >> 2) & 1) << " " << (1 << 3); // 1 8

int a = 4, b = 9, c = 1;
cout << min({a, b, c}) << " " << max({a, b, c}) << " "; // 1 9
swap(a, b);                                   // a = 9, b = 4
cout << a << " ";                             // 9
long long big = 5;
// max(big, 3) does not compile: long long vs int
cout << max(big, 3LL) << " " << abs(-7);      // 5 7

cout << gcd(12, 18) << " " << lcm(4, 6) << " ";  // 6 12
int g = 0;
for (int x : {8, 12, 20}) g = gcd(g, x);        // gcd of a list
cout << g;                                       // 4

ios::sync_with_stdio(false);   // unhook from C stdio
cin.tie(nullptr);              // don't flush cout before every cin
int n = 0;
cin >> n;
vector<int> a(n);
for (auto& x : a) cin >> x;
cout << a.size() << "\n";      // n

auto y = 5LL;                 // long long
auto s = string("hi");        // string
vector<int> v = {1, 2, 3};
for (auto it = v.begin(); it != v.end(); ++it) *it += 1; // [2, 3, 4]
auto add = [&](int d) { for (auto& e : v) e += d; };
add(10);                                                 // [12, 13, 14]
cout << v[0] << " " << sizeof(y) << " " << s.size();     // 12 8 2