The Fellowship of the STL: C++ Data Structures Every Competitive Programmer Needs

The Quest Begins (The “Why”)

I still remember the first time I tried to solve a graph‑shortest‑path problem on Codeforces. The statement was simple: given a weighted graph with edges of weight 0 or 1, find the shortest distance from node 1 to every other node. My gut told me to use a classic Dijkstra with a priority queue, but the constraints were huge—up to 2 × 10⁵ edges—and my solution kept timing out.

I opened my editor, stared at the unordered_map<pair<int,int>,int> I’d slapped together to store adjacency lists, and felt that familiar dread. Every time I inserted a new edge, the map seemed to hiccup, and the runtime graph looked like a sawtooth. I muttered, “Look, the reality is… I’m missing something obvious.” After a couple of hours of fruitless tweaking, I decided to dig deeper into the STL itself. What I uncovered felt like finding the hidden room in Portal where the cake is a lie—except this time the cake was real, and it made my code fly.

The Revelation (The Insight)

1. unordered_map – The Hidden Power of Custom Hashes & Reserve

Most of us reach for unordered_map when we need O(1) average look‑ups, then move on. What many competitive programmers miss is that the container’s performance hinges on two things you can control: the hash function and the number of buckets.

• Gotcha #1 – No built‑in hash for pair<int,int>
  
  If you try unordered_map<pair<int,int>,int> mp; without providing a hash, the compiler will yell: no matching function for call to ‘std::hashstd::pair<int,int>’. The fix is trivial but easy to overlook: write a small struct that combines the two hashes (e.g., using std::hash<int> and a bit‑shift or a prime multiplier).

• Gotcha #2 – Rehashing kills your runtime
  
  By default, an unordered_map starts with a tiny bucket count and rehashes whenever the load factor exceeds ~1.0. Each rehash allocates a new bucket array and re‑inserts every element—O(n) work that can happen dozens of times while you’re building a large graph. The result? Your seemingly O(m) edge‑insertion loop actually becomes O(m log m) or worse, blowing the time limit.

The fix is two‑fold: supply a decent hash and call reserve(n) (or max_load_factor) before you start inserting. reserve tells the map to allocate enough buckets for n elements, dramatically reducing the chance of a rehash.

2. deque – The Double‑Ended Workhorse That Beats vector at Front Insertions

When I first learned about deque, I thought of it as just a “fancy vector”. I was wrong. The real gem is that deque supports O(1) insertion and removal at both ends, while a vector only gives you O(1) at the back.

• Gotcha #3 – Assuming push_front on a vector is cheap Many CP solutions (especially for 0‑1 BFS or sliding‑window minima) need to push elements to the front of a container. If you reach for vector and call insert(begin(), value), you’re paying O(n) for each operation because everything must be shifted. With deque, push_front is a constant‑time pointer shuffle—no element moves.

The subtlety? Iterators remain valid after push_front/pop_front on a deque (except those pointing to the removed element), whereas vector invalidates all iterators on any insertion that causes a reallocation. Knowing this saves you from hard‑to‑track bugs when you’re juggling iterators in graph algorithms.

Wielding the Power (Code & Examples)

Example 1 – Fast Edge Storage with unordered_map

Before – The struggle

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    cin >> n >> m;
    // WRONG: no hash for pair<int,int>
    unordered_map<pair<int,int>, int> adj; // <-- compile error!
    for (int i = 0; i < m; ++i) {
        int u, v, w;
        cin >> u >> v >> w;
        adj[{u, v}] = w; // would be O(1) if it compiled
    }
    // ... rest of Dijkstra ...
}

The code won’t even compile. After adding a naïve hash, we still see TLE because the map rehashes constantly.

After – The victory

#include <bits/stdc++.h>
using namespace std;

// ---- custom hash for pair<int,int> ----
struct pair_hash {
    size_t operator()(const pair<int,int>& p) const noexcept {
        // simple mixing: (first * 31) ^ second
        return (static_cast<size_t>(p.first) * 31ULL) ^ static_cast<size_t>(p.second);
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    cin >> n >> m;
    // reserve enough buckets for m elements; max_load_factor keeps it tight
    unordered_map<pair<int,int>, int, pair_hash> adj;
    adj.reserve(m * 2);          // roughly double to stay under 0.5 load
    adj.max_load_factor(0.25);   // optional, makes rehashes even rarer

    for (int i = 0; i < m; ++i) {
        int u, v, w;
        cin >> u >> v >> w;
        adj[{u, v}] = w;        // now O(1) amortized, no surprise rehashes
    }
    // ... run 0‑1 BFS or Dijkstra ...
}

Why it matters: The reserve call cuts the number of rehashes from O(m) to practically zero. The custom hash lets us store edges as a single key instead of nesting maps (adj[u][v]). In practice, I’ve seen this shave 30‑50 % off the runtime of dense‑graph problems on tight limits.

Example 2 – 0‑1 BFS with deque

Before – The struggle (using vector as a queue)

cpp
vector<int> dist(n+1, INF);
deque<int> q; // wait, we intended to use a vector!
q.push_back(1);
dist[1] = 0;

while (!q.empty()) {
    int u = q.front(); q.erase(q.begin()); // O(n) shift each pop!
    for (auto [v, w] : adj[u]) {
        if (dist[u] + w < dist[v]) {
            dist[v] = dist[u] + w;
            if (w == 0) q