The Matrix of C++ STL: Hidden Gems Every Competitive Programmer Needs

The Quest Begins (The "Why")

I still remember the first time I sat down for a Codeforces round, heart pounding, fingers flying over the keyboard. I had a solid grasp of loops, vectors, and the usual sort, but every problem seemed to slip through my grasp because I kept writing the same boilerplate: manually filling a range with numbers, painstakingly checking if a key existed before inserting into a map, or sorting an entire array when I only needed the top k scores.

It felt like I was fighting a boss with only a basic sword while everyone else was wielding enchanted blades. After a few frustrating WA’s, I started digging into the STL documentation—not just the “most used” parts, but the corners that most tutorials gloss over. What I found felt like discovering secret cheat codes.

The Revelation (The Insight)

1. std::iota – The One‑Liner Range Filler

Most of us reach for a for loop when we need a vector of consecutive integers:

// before
vector<int> v(n);
for (int i = 0; i < n; ++i) v[i] = i;

That works, but it’s noisy and easy to slip up (off‑by‑one, wrong type, etc.). Enter std::iota from <numeric>. It takes two iterators and a starting value, then fills the range with incrementally increasing values—no loop needed.

// after
#include <numeric>
vector<int> v(n);
iota(v.begin(), v.end(), 0);   // 0,1,2,...,n-1

Gotcha: iota works with any forward iterator, not just random‑access ones, so you can use it on list, forward_list, or even raw pointers. Just remember to include <numeric>; otherwise the compiler will greet you with a cryptic “undefined reference” error.

2. std::unordered_map::try_emplace – Insert Without Unnecessary Temporaries

The classic pattern for inserting into an unordered_map while avoiding default construction looks like this:

// before
auto it = mp.find(key);
if (it == mp.end()) {
    mp.emplace(key, heavy_object(arg1, arg2));
}

That’s two lookups (one for find, another hidden inside emplace) and it constructs a temporary pair even when the key already exists.

C++17 gave us try_emplace. It does exactly one lookup and only constructs the value if the key is absent. Plus, it forwards arguments directly to the value’s constructor—no extra temporary.

// after
#include <unordered_map>
mp.try_emplace(key, heavy_object(arg1, arg2));

Gotcha: If the key already exists, try_emplace leaves the map untouched and does not evaluate the value arguments at all. This can save you from expensive constructions or even side‑effects (think logging or network calls inside a constructor).

3. std::partial_sort – Sort Only What You Need

Often we need the top k elements (or the k‑smallest) but we still call std::sort on the whole range, which is O(N log N). If k ≪ N, we’re doing extra work.

// before
vector<int> scores = {/* ... */};
sort(scores.begin(), scores.end(), greater<int>());
auto topk = vector<int>(scores.begin(), scores.begin() + k);

std::partial_sort rearranges the range so that the first k elements are the smallest (or largest, with a comparator) and are sorted among themselves; the rest are left in an unspecified but valid state.

// after
#include <algorithm>
partial_sort(scores.begin(), scores.begin() + k, scores.end(), greater<int>());
auto topk = vector<int>(scores.begin(), scores.begin() + k);

Gotcha: The elements after the k‑th position are not sorted; they’re merely partitioned. If you later need the full order, you’ll have to call std::sort again on the remainder—or just accept that you only needed the top k.

---

Wielding the Power (Code & Examples)

Let’s see these three gems in action with a realistic competitive‑programming scenario:

Problem: Given n scores, output the k highest scores in descending order, and also produce a lookup table that maps each score to the number of times it appears (but only for scores that actually appear).

Naïve Approach

vector<int> scores(n);
for (int i = 0; i < n; ++i) cin >> scores[i];

// 1. fill a rank vector (0..n-1) – manual loop
vector<int> rank(n);
for (int i = 0; i < n; ++i) rank[i] = i;

// 2. count frequencies – double lookup
unordered_map<int,int> freq;
for (int s : scores) {
    auto it = freq.find(s);
    if (it == freq.end())
        freq.emplace(s, 1);
    else
        ++it->second;
}

// 3. get top k – full sort
sort(scores.begin(), scores.end(), greater<int>());
vector<int> topk(scores.begin(), scores.begin() + k);

Power‑User Approach

#include <numeric>   // iota
#include <algorithm> // partial_sort
#include <unordered_map>

vector<int> scores(n);
for (int i = 0; i < n; ++i) cin >> scores[i];

// 1. rank vector – one line
vector<int> rank(n);
iota(rank.begin(), rank.end(), 0);   // 0,1,2,...,n-1

// 2. frequency map – try_emplace avoids extra find
unordered_map<int,int> freq;
for (int s : scores) {
    freq.try_emplace(s, 1);          // inserts if absent
    ++freq[s];                       // now safe to increment
}

// 3. top k – partial_sort, no full sort needed
partial_sort(scores.begin(), scores.begin() + k, scores.end(), greater<int>());
vector<int> topk(scores.begin(), scores.begin() + k);

Feel the difference? The code is shorter, clearer, and—more importantly—each step does the minimal amount of work. In a tight time limit, those saved microseconds add up.

---

Why This New Power Matters

Mastering these tucked‑away STL features does more than shave off a few milliseconds; it reshapes how you think about problems.

• iota teaches you to let the library do the boring iteration, freeing mental bandwidth for the algorithmic core.
• try_emplace reminds you that construction can be expensive—sometimes more expensive than the lookup itself—and that the STL gives you a way to avoid it when possible.
• partial_sort is a lesson in laziness: do only the work you truly need, and leave the rest untouched until (if ever) it becomes relevant.

When you start reaching for these tools instinctively, you’ll notice your solutions becoming more elegant, your debugging sessions shorter, and your confidence higher—like finally unlocking that hidden upgrade in a RPG that turns a tough boss fight into a satisfying combo.

---

Your Turn

Pick a recent problem where you wrote a manual loop to generate a sequence, or where you checked a map’s existence before inserting. Refactor it using one (or two) of the tricks above. Drop your before/after snippets in the comments—I’m curious to see how these hidden gems change your approach! Happy coding, and may your compiles be swift and your WA’s few. 🚀