May the STL Be With You: C++ Data Structures Every Competitive Programmer Needs

The Quest Begins (The "Why")

I still remember the first time I tried to solve a graph problem on Codeforces. My code was a tangled mess of vectors, manual heap tricks, and a lot of push_back/pop_back gymnastics. After three failed submissions I was staring at the screen, feeling like Frodo staring at Mount Doom—the destination was visible, but every step seemed to sap my strength. I knew there had to be a better way, a set of tools that would let me focus on the algorithm instead of wrestling with the language. That’s when I dove back into the C++ STL, not just to copy‑paste snippets, but to uncover the hidden gems most tutorials skim over.

What I found felt like discovering a secret shortcut in Mario Kart—a boost pad that launches you ahead of the pack without you even realizing you hit it. Let’s grab those power‑ups together.

The Revelation (The Insight)

1. Min‑Heaps Aren’t Just a Myth

Most of us learn that std::priority_queue gives you a max‑heap out of the box. Need the smallest element on top? The usual answer is “negate the values” or “write your own heap.” Yeah, that works, but it’s noisy and error‑prone.

Gotcha: The priority queue’s template actually takes three parameters: the element type, the underlying container (default std::vector<T>), and the comparison functor (default std::less<T>). If you swap the comparator to std::greater<>, you get a true min‑heap—no sign‑flipping required.

Why this trips people up: you have to remember to include <functional> for greater<>, and you must explicitly specify the container type if you want to be extra clear (though the default works). Forget either, and the compiler will greet you with a cryptic error about “no type mismatch.

Practical use case: Dijkstra’s algorithm. You need to repeatedly extract the vertex with the smallest tentative distance. A min‑heap makes each extraction O(log V) and keeps the code clean.

#include <queue>
#include <vector>
#include <functional>   // for greater<>
#include <iostream>

int main() {
    // Min‑heap of integers
    std::priority_queue<int, std::vector<int>, std::greater<int>> pq;

    pq.push(5);
    pq.push(2);
    pq.push(9);

    while (!pq.empty()) {
        std::cout << pq.top() << ' ';   // prints 2 5 9
        pq.pop();
    }
    // Output: 2 5 9
}

See? No negating, no extra wrapper struct—just a clean, readable heap that gives you the smallest element first.

2. Unordered Maps: Reserve Your Space, Avoid the Rehash Dragon

std::unordered_map is the go‑to hash table for O(1) average look‑ups. Yet many competitive programmers watch their solutions slow down mysteriously on large test cases. The culprit? Repeated rehashing as the map grows.

Gotcha: By default, an unordered_map starts with a small number of buckets and rehashes whenever the load factor exceeds its max_load_factor() (usually 1.0). Each rehash allocates a new bucket array and re‑inserts every element—an O(n) operation that can happen dozens of times in a tight loop.

The fix is simple: call reserve(n) before you start inserting, where n is an upper bound on the number of elements you expect. This pre‑allocates enough buckets to keep the load factor low, dramatically cutting rehashes.

Practical use case: Counting frequencies in an array of up to 200 000 integers.

#include <unordered_map>
#include <vector>
#include <iostream>

int main() {
    std::vector<int> data = { /* 200k random numbers */ };
    std::unordered_map<int, int> freq;

    // Reserve space for 200k entries (a bit more to be safe)
    freq.reserve(250000);

    for (int x : data) {
        ++freq[x];   // O(1) average, no rehash spikes
    }

    // Now freq is ready for fast queries
    std::cout << "Count of 42: " << freq[42] << '\n';
}

If you forget reserve, you might still pass the tests on small inputs, but on the maximum constraints you’ll see a noticeable slowdown—sometimes enough to turn an AC into a TLE.

3. Emplace, Don’t Just Push

std::vector::push_back is convenient, but it forces the compiler to create a temporary object, then move (or copy) it into the vector. For complex types—like structs with multiple fields or strings—this extra move can add up.

Gotcha: emplace_back constructs the element in‑place inside the vector’s storage, eliminating the temporary altogether. The syntax looks almost identical, but you pass the constructor arguments directly.

Many developers stick with push_back out of habit, missing a free performance win, especially when the vector grows large in a tight loop (think of building a graph adjacency list).

Practical use case: Building an adjacency list for a graph where each edge is a small struct.

#include <vector>
#include <iostream>

struct Edge {
    int to;
    int weight;
    Edge(int t, int w) : to(t), weight(w) {}
};

int main() {
    std::vector<Edge> graph[100001];   // adjacency list for up to 1e5 nodes

    int m; std::cin >> m;   // number of edges
    for (int i = 0; i < m; ++i) {
        int u, v, w;
        std::cin >> u >> v >> w;
        // Before: graph[u].push_back(Edge(v, w));
        // After:
        graph[u].emplace_back(v, w);   // constructs Edge directly in the vector
    }

    // Use graph as needed...
    std::cout << "First edge from node 1: to=" << graph[1][0].to
              << ", weight=" << graph[1][0].weight << '\n';
}

The difference is subtle but real: emplace_back avoids the temporary Edge object, saving both time and, in tight memory limits, a few precious bytes.

Why This New Power Matters

Mastering these three nuances turns you from a coder who writes solutions into a craftsman who designs them.

• A min‑heap lets you express greedy and shortest‑path algorithms naturally, reducing bugs caused by manual sign tricks.
• Pre‑reserving your hash tables keeps your algorithm’s complexity truly O(1) per operation, turning potential TLEs into clean ACs.
• Using emplace_back removes unnecessary moves, which is especially valuable when your data structures are heavy or when you’re pushing millions of elements.

Together, they shave off milliseconds that add up over dozens of test cases, and they make your code easier to read—future you (and your teammates) will thank you when you revisit that graph solution months later.

Your Turn: The Challenge

Pick a problem you’ve solved before that relied on a manual max‑heap workaround or a frequency map that felt sluggish. Refactor it using a std::priority_queue<std::greater<>>, reserve your unordered_map, and swap any push_back for emplace_back. Run it on the largest test case you can find and note the difference.

Did you feel the boost? Drop your before/after times in the comments—I’d love to hear how much faster your quest became!

Happy coding, and may the STL be with you! 🚀