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

The Quest Begins (The "Why")

I still remember my first ICPC‑style contest. I was cruising through a problem that needed a dynamic median, and I reached for a priority_queue like a trusty sword. I popped the top, pushed the next value, and felt like I’d solved it—until the judge returned Wrong Answer. After hours of staring at the output, I realized I’d been throwing away half the data every time I popped. I needed a way to peek inside the heap without destroying it. That moment felt like facing a boss that kept respawning unless I discovered its hidden weakness.

If you’ve ever felt stuck because the STL seemed to hide its true power, you’re not alone. Many competitive programmers treat containers as black boxes, missing the subtle knobs that turn a good solution into a blazing‑fast one. Let’s embark on a short quest to uncover three surprising STL features that most devs overlook—complete with gotchas, practical use‑cases, and the code that turns frustration into victory.

The Revelation (The Insight)

1. Priority Queue’s Secret Container

Most tutorials show priority_queue as a “give me the max/min” tool. The gotcha? The standard interface doesn’t let you iterate over its elements. You can only pop the top, which destroys the heap.

Why it matters: In algorithms like Dijkstra with a decrease‑key trick, or when you need to dump the heap for debugging, you really want to look at all elements without losing them.

The hidden feature: priority_queue stores its data in a protected container (vector<T> c by default). By inheriting from it, you gain access to that container and can iterate, clear, or even re‑heapify manually.

template<class T, class Container = std::vector<T>,
         class Compare = std::less<typename Container::value_type>>
class inspectable_pq : public std::priority_queue<T, Container, Compare> {
public:
    using std::priority_queue<T, Container, Compare>::c; // expose the underlying container

    // Example: peek at all elements in sorted order (non‑destructive)
    std::vector<T> sorted_snapshot() const {
        auto temp = c;                 // copy the internal container
        std::sort(temp.begin(), temp.end(),
                  typename std::priority_queue<T, Container, Compare>::value_compare());
        return temp;
    }

    // Example: clear without popping one‑by‑one
    void fast_clear() { c.clear(); }
};

Gotcha: If you forget to expose c, you’ll keep trying to access a private member and get a cryptic compiler error. The inheritance trick is the cleanest way to stay within the language rules while still getting the low‑level view you need.

2. Unordered Map’s Reserve & Load‑Factor Control

unordered_map feels magical—average O(1) insert/lookup. The surprise? Its performance can collapse if you let it rehash too often. Each rehash allocates a new bucket array and re‑inserts every element, which can turn a linear‑time solution into a quadratic nightmare on large inputs.

Why it matters: In contests where you insert hundreds of thousands of keys (think frequency counting or graph edge maps), uncontrolled rehashing is a silent time‑killer.

The hidden feature: You can pre‑allocate buckets with reserve(n) and tune the maximum load factor via max_load_factor(z). Doing this once up front tells the hash table exactly how much space it’ll need, eliminating almost all rehashes.

std::unordered_map<int, int> freq;
freq.reserve(200'000);          // space for ~200k elements
freq.max_load_factor(0.7);      // keep chains short (default is 1.0)

for (int i = 0; i < n; ++i) {
    ++freq[read_int()];
}

Gotcha: Many developers call reserve after they’ve already inserted a bunch of items, which triggers a rehash anyway. The call must happen before the first insert (or after a clear() if you reuse the map). Also, setting max_load_factor too low wastes memory; too high brings back long chains. A value around 0.7–0.9 works well for most CP problems.

3. Vector’s Capacity Tricks – Shrink‑to‑Fit & the Swap Idiom

vector is the workhorse of competitive programming: contiguous, cache‑friendly, and fast. The surprise? clear() does not release its allocated memory. The capacity stays exactly what it was, which can waste megabytes when you reuse a vector for multiple test cases.

Why it matters: When solving multiple test cases in a single program, leftover capacity can balloon memory usage and even cause a limit‑exceeded error on strict judges.

The hidden feature: Two techniques let you truly shrink a vector:

• shrink_to_fit() (C++11) – a non‑binding request to reduce capacity to size.
• The classic swap trick: vector<T>().swap(v); – creates an empty temporary and swaps its internal storage with v, forcing the old buffer to be deallocated.

std::vector<int> v;
v.reserve(1'000'000);          // pretend we needed a huge buffer once
// … use v …
v.clear();                     // size == 0, capacity still 1'000'000

// Option 1: ask nicely (may or may not shrink)
v.shrink_to_fit();             // capacity now close to 0 (implementation‑dependent)

// Option 2: force a shrink (guaranteed)
std::vector<int>().swap(v);    // v is now empty with zero capacity

Gotcha: Relying solely on shrink_to_fit() can leave you surprised if the implementation chooses not to shrink (it’s allowed). The swap trick is the portable, guaranteed way to reclaim memory—just remember it involves an extra move/temporary, which is negligible compared to the saved memory in CP scenarios.

Wielding the Power (Code & Examples)

Let’s see these ideas in a realistic snippet: a multi‑test‑case problem that counts frequencies, finds the k‑th largest element, and needs to reset structures fast.

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

// ---- inspectable priority queue (max‑heap) ----
template<class T, class Container = std::vector<T>,
         class Compare = std::less<typename Container::value_type>>
class inspectable_pq : public std::priority_queue<T, Container, Compare> {
public:
    using std::priority_queue<T, Container, Compare>::c;
    vector<T> sorted_snapshot() const {
        auto tmp = c;
        sort(tmp.begin(), tmp.end(),
             typename std::priority_queue<T, Container, Compare>::value_compare());
        return tmp;
    }
    void fast_clear() { c.clear(); }
};

void solve_one_case() {
    int n, k; cin >> n >> k;
    inspectable_pq<int> maxHeap;          // we’ll keep the k smallest values here
    unordered_map<int, int> freq;
    freq.reserve(n * 2);
    freq.max_load_factor(0.8);

    for (int i = 0; i < n; ++i) {
        int x; cin >> x;
        ++freq[x];
        maxHeap.push(x);
        if ((int)maxHeap.size() > k) maxHeap.pop(); // keep only k smallest
    }

    // Example use of the inspectable heap: debug print of the k smallest
    auto smallest = maxHeap.sorted_snapshot();
    cerr << "K smallest values: ";
    for (int v : smallest) cerr << v << ' ';
    cerr << '\n';

    // Find the element with frequency >= threshold (just as an example)
    int threshold = (n + 1) / 2;
    int answer = -1;
    for (auto [val, cnt] : freq) {
        if (cnt >= threshold) { answer = val; break; }
    }
    cout << answer << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T; cin >> T;
    while (T--) {