STL for Competitive & study C++

“The STL is not a library you look up. It is a dialect you speak.”

This file is the subset of the C++ Standard Library you must know reflexively for studies and contest-style problems. It is deliberately narrow. Reading the full <algorithm> header is a lifetime project. Passing an study is a twenty-container problem.

---

The competitive subset

Spend one focused session on each container below. Type five example uses for each, by hand, no autocomplete. If you cannot recall the declaration syntax cold after that, drill again.

Sequence containers

Container	When you reach for it	Complexity gotcha
std::vector<T>	Default. Always.	push_back amortized O(1); insert(begin, ...) is O(n)
std::array<T, N>	Compile-time size known	Stack-allocated; watch overflow on large N
std::deque<T>	Push/pop from both ends	Not contiguous; slower iteration than vector
std::string	Text, obviously	substr copies; use string_view when read-only

Adaptors

Adaptor	Backed by	study use
std::stack<T>	deque by default	Monotonic stack, parentheses, DFS iterative
std::queue<T>	deque	BFS
std::priority_queue<T, Container, Compare>	vector + heap	Dijkstra, top-K, merge-K-sorted

Associative

Container	Backing	Ordered?	Avg lookup	Worst lookup
std::map	RB-tree	Yes	O(log n)	O(log n)
std::set	RB-tree	Yes	O(log n)	O(log n)
std::unordered_map	Hash table	No	O(1)	O(n)
std::unordered_set	Hash table	No	O(1)	O(n)

Utilities you will use every day

• std::pair<A, B> — quick two-tuple. Access with .first / .second.

• std::tuple<...> — more than two. Access with std::get<0>(t) or structured bindings.

• std::bitset<N> — fixed-size bit array, incredibly fast for set operations on small universes (≤ ~10^6).

• std::optional<T> — replaces “return -1 for not found.”

• std::span<T> (C++20) — non-owning view over contiguous memory.

---

priority_queue with a custom comparator (the study classic)

Everyone forgets this syntax. Burn it in.

// Min-heap of ints (the most common need):
std::priority_queue<int, std::vector<int>, std::greater<int>> minHeap;

// Heap of pairs, sort by first ascending (for Dijkstra: {dist, node}):
using P = std::pair<int, int>;
std::priority_queue<P, std::vector<P>, std::greater<P>> pq;

// Custom lambda comparator (C++20, or with decltype pre-20):
auto cmp = [](const std::string& a, const std::string& b) {
    return a.size() > b.size();  // smaller sizes on top
};
std::priority_queue<std::string, std::vector<std::string>, decltype(cmp)> pq2(cmp);

Trap: The comparator’s return value is the opposite of what feels natural. greater<> gives you a min-heap. If you write less<> you get the default max-heap. This has burned every C++ programmer at least once.

---

emplace_back vs push_back

std::vector<std::pair<int, std::string>> v;
v.push_back({1, "hello"});         // constructs a pair, then moves/copies
v.push_back(std::make_pair(1, "hi")); // same story
v.emplace_back(1, "hello");         // constructs the pair in-place, no temp

Rule of thumb: emplace_back when constructing a non-trivial object from its constructor arguments. push_back when you already have the object. In tight loops the difference is measurable; in studies the difference is signal that you know the language.

Trap: emplace_back bypasses explicit constructors and narrowing warnings. It will happily accept arguments that push_back({...}) would reject. Occasionally this hides bugs.

---

lower_bound, upper_bound, equal_range

The binary search primitives most people underuse.

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

auto lb = std::lower_bound(v.begin(), v.end(), 4);  // iterator to first 4
auto ub = std::upper_bound(v.begin(), v.end(), 4);  // iterator to first 5
int idx_lb = lb - v.begin();  // 2
int count_4 = ub - lb;         // 3

// On a std::set / std::map: use the member versions, not std::lower_bound:
std::set<int> s = {1, 3, 5, 7};
auto it = s.lower_bound(4);  // O(log n); std::lower_bound(s.begin(), ...) is O(n)!

Trap: std::lower_bound on a set iterator is O(n) because set iterators are not random-access. Always use set.lower_bound(x) — the member function. This is a real study gotcha.

---

Fast I/O incantation

Drop this at the top of main() for any contest-style problem where input is large.

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);
    // ...
}

Line by line:

• sync_with_stdio(false) — unlinks the C++ streams from C’s stdio. ~5x speedup on heavy I/O.

• cin.tie(nullptr) — stops flushing cout before every cin read. Another 2x on interactive I/O.

Trap: Once you unsync, do not mix printf and cout in the same program. The interleaving is undefined.

---

LeetCode-specific bugs (memorize these; they cost real submissions)

1. long long overflow on multiplication

int a = 100000, b = 100000;
long long product = a * b;         // BUG: overflows int, then widens. product = 100-225

long long product2 = (long long)a * b;  // OK: 2025 2026
long long product3 = 1LL * a * b;       // idiomatic

Any time you multiply two ints, ask: can the result exceed 2^31 - 1 (~2.1B)? If yes, cast one operand to long long before the multiply.

Problems where this bites: LeetCode 50 (Pow(x, n)), LC 43 (Multiply Strings), LC 1922 (Count Good Numbers), and anything with grid coordinates ≥ 46000.

2. unordered_map DoS on adversarial inputs

LeetCode has, historically, had test cases specifically designed to force unordered_map<int, ...> into worst-case O(n) per operation via hash collisions. Your O(n) solution TLEs while the map<int, ...> version passes.

Defense:

// Option 1: use std::map (O(log n) but adversary-proof)
std::map<int, int> m;

// Option 2: custom hash with random seed
struct custom_hash {
    static uint64_t splitmix64(uint64_t x) {
        x += 0x<phone_number_or_numberic_id_or_random_id_8>;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }
    size_t operator()(uint64_t x) const {
        static const uint64_t seed =
            std::chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + seed);
    }
};
std::unordered_map<int, int, custom_hash> safe_map;

Drop the custom hash into your template. Use it any time your unordered_map solution TLEs mysteriously on the last two test cases.

3. auto& vs auto in range-for

std::vector<std::string> v = {"a", "b", "c"};

for (auto s : v) s += "!";        // BUG: modifies a copy
for (auto& s : v) s += "!";       // OK: modifies v
for (const auto& s : v) print(s); // OK: read-only, no copy

for (auto [k, val] : mp) { ... }        // structured binding copy
for (const auto& [k, val] : mp) { ... } // structured binding by ref (preferred)

Rule: default to const auto&. Use auto& only when you mean to mutate. Bare auto in range-for is almost always a silent performance bug on large containers.

4. Integer division truncation vs floor for negatives

(-7) / 2   // == -3 in C++ (truncated toward zero), not -4 (floor)
(-7) % 2   // == -1, not +1

Python’s // is floor. C++’s / is truncation. Any problem involving negative-index modular arithmetic (e.g., Josephus variants, cyclic array wraps) needs ((x % n) + n) % n.

5. size_t underflow in reverse loops

std::vector<int> v = {1, 2, 3};
for (size_t i = v.size() - 1; i >= 0; --i) { ... }  // INFINITE LOOP
// v.size() is size_t (unsigned). When i = 0, --i wraps to SIZE_MAX.

for (int i = (int)v.size() - 1; i >= 0; --i) { ... }  // OK
for (auto it = v.rbegin(); it != v.rend(); ++it) { ... }  // idiomatic

6. Modifying container while iterating

for (auto it = m.begin(); it != m.end(); ++it) {
    if (bad(it->second)) m.erase(it);  // BUG: invalidates it
}

// Correct idiom (pre-C++20):
for (auto it = m.begin(); it != m.end(); ) {
    if (bad(it->second)) it = m.erase(it);
    else ++it;
}

// C++20:
std::erase_if(m, [](const auto& kv) { return bad(kv.second); });

---

<algorithm> shortlist for studies

Do not memorize the whole header. Do memorize these:

std::sort(v.begin(), v.end());
std::sort(v.begin(), v.end(), std::greater<>());  // descending
std::reverse(v.begin(), v.end());
std::accumulate(v.begin(), v.end(), 0LL);         // note the 0LL for long long sum
std::min_element(v.begin(), v.end());             // returns iterator
std::max_element(v.begin(), v.end());
std::count(v.begin(), v.end(), x);
std::count_if(v.begin(), v.end(), pred);
std::find(v.begin(), v.end(), x);
std::binary_search(v.begin(), v.end(), x);        // requires sorted
std::unique(v.begin(), v.end());                  // requires sorted; use with erase
std::next_permutation(v.begin(), v.end());        // for permutation generation
std::gcd(a, b);   // C++17, <numeric>
std::lcm(a, b);   // C++17, <numeric>

The erase-unique idiom:

std::sort(v.begin(), v.end());
v.erase(std::unique(v.begin(), v.end()), v.end());  // dedupe in place

---

String manipulation cheatsheet

std::string s = "hello world";
s.substr(6);           // "world"
s.substr(0, 5);        // "hello"
s.find("world");       // 6, or std::string::npos
s.rfind("l");          // 9
std::stoi("42");       // 42; stol, stoll for wider types
std::to_string(42);    // "42"
std::isalpha(c);       // in <cctype>; also isdigit, isspace, tolower, toupper

// Split on delimiter (C++ has no builtin; here is the idiom):
std::vector<std::string> split(const std::string& s, char delim) {
    std::vector<std::string> out;
    std::string tok;
    std::stringstream ss(s);
    while (std::getline(ss, tok, delim)) out.push_back(tok);
    return out;
}

Trap: std::string::npos is size_t(-1), not -1. Compare with == std::string::npos, not == -1.

---

What most people get wrong

They think STL fluency is about knowing every algorithm in <algorithm>. It is not. It is about knowing the twenty containers and algorithms above so well that you never think about them. Fluent speakers of a language do not consult grammar tables mid-sentence. Fluent STL users do not consult cppreference mid-problem.

Drill: pick five problems from tomorrow’s session and solve each twice. Once with any STL you want, then again forcing yourself to use emplace_back, structured bindings, and const auto&. The second pass is where fluency is built.

---

Nav: ← Phase 2 README · NeetCode 150 roadmap →