C++ STL Data Structures Every Competitive Programmer Needs – The Matrix Edition

The Quest Begins (The "Why")

I still remember my first ICPC‑style contest. I was cruising through a problem that needed a sliding window minimum, and I slapped a std::vector<int> into the mix, push_back‑ing each new element and erase‑ing the front when the window moved. The code worked on the sample, but when the judge fed it a test with 2 × 10⁵ operations, my solution choked — TLE after TLE. I stared at the terminal, wondering why a simple vector felt like dragging a truck uphill.

That moment kicked off a quiet obsession: what hidden tricks does the C++ STL have that most tutorials gloss over? I dug into reference pages, experimented in late‑night coding sessions, and eventually uncovered a few gems that turned my “slow but correct” solutions into lightning‑fast submissions. If you’ve ever felt like you’re battling a final boss with a wooden sword while everyone else wields a lightsaber, this article is for you.

The Revelation (The Insight)

The STL isn’t just a collection of containers; it’s a toolbox packed with specialty instruments that solve specific problems in O(1) or logarithmic time — if you know where to look. Three features repeatedly saved my runtime, yet they’re surprisingly under‑talked in typical competitive‑programming guides:

1. std::list::splice – moving nodes without allocation or copying
   
   Most programmers reach for std::vector or std::deque when they need a sequence that can grow and shrink. Few realize that a std::list lets you detach a whole range of nodes and insert them elsewhere in constant time, with zero memory traffic. This is a lifesaver for problems that require frequent re‑ordering (e.g., simulating a queue of processes, implementing LRU caches, or juggling adjacency lists in graph algorithms).

2. The std::vector<bool> gotcha – it’s not a real vector of bools
   
   The specialization of vector<bool> stores bits packed into words, returning a proxy reference instead of a genuine bool&. This sounds clever until you try to take the address of an element (&v[i]) or pass it to a function expecting bool*. The compiler will happily let you write code that compiles but crashes at runtime, or worse, silently corrupts data. Knowing when to avoid this trap (or when to exploit the bit‑packed memory savings) can mean the difference between a correct solution and a mysterious WA.

3. std::array – fixed‑size, stack‑allocated, constexpr‑friendly
   
   When the size of a container is known at compile time (think a 10 × 10 grid, a 26‑letter frequency table, or a small DP table), std::array gives you the safety and member functions of a vector without any heap allocation. Because its size is part of the type, it can be used in constexpr contexts, enabling compile‑time preprocessing that shaves off precious milliseconds — especially valuable when the same lookup table is reused across many test cases.

These three insights felt like discovering cheat codes hidden in the game’s source code. Once I internalized them, my solutions went from “just passes” to “dominates the leaderboard.”

Wielding the Power (Code & Examples)

Below I’ll show the “before” (the naïve approach) and the “after” (the STL‑powered version) for each feature, plus the common pitfalls to watch for.

1. std::list::splice – O(1) node relocation

Problem: Maintain a list of active processes where you frequently need to move the front element to the back (round‑robin scheduler).

Before – using std::deque with pop/push:

std::deque<int> q;
while (!tasks.empty()) {
    int cur = tasks.front();
    tasks.pop_front();          // O(1) but involves moving elements internally
    process(cur);
    tasks.push_back(cur);       // O(1) but may trigger reallocation if capacity exceeded
}

Even though each operation is amortized O(1), the deque may shift its internal blocks when it grows, causing cache misses and occasional costly reallocations.

After – using std::list::splice:

std::list<int> lst;                     // doubly‑linked list, true O(1) splice
// … fill lst …

auto it = lst.begin();                  // iterator to front
while (!lst.empty()) {
    int cur = *it;
    process(cur);

    // Move the node pointed to by `it` to the back.
    lst.splice(lst.end(), lst, it);     // O(1), no allocation, no copying
    it = lst.begin();                   // iterator to new front after splice
}

Gotcha: After splice, the iterator it becomes invalid because the node it pointed to has been moved. Re‑assigning it to lst.begin() (or using std::next(it) before the splice) is essential; otherwise you’ll dereference a dangling iterator and invite UB.

2. std::vector<bool> – when to use and when to flee

Problem: Count how many numbers in a range are prime using a bitset‑like structure.

Before – naive vector<char> (wastes memory):

vector<char> isPrime(limit + 1, true);  // 1 byte per entry
for (int p = 2; p * p <= limit; ++p)
    if (isPrime[p])
        for (int64_t i = 1LL * p * p; i <= limit; i += p)
            isPrime[i] = false;

Works fine, but for limit = 10⁷ you allocate ~10 MB — still okay, but in tighter memory limits it adds up.

After – vector<bool> (bit‑packed):

vector<bool> isPrime(limit + 1, true); // ~limit/8 bytes
for (int p = 2; p * p <= limit; ++p)
    if (isPrime[p])
        for (int64_t i = 1LL * p * p; i <= limit; i += p)
            isPrime[i] = false;

Gotcha #1 – address‑of:

bool* ptr = &isPrime[5]; // ERROR: does not compile (returns proxy)

The element type is std::vector<bool>::reference, not bool. To get a raw pointer you must either:

• Use std::vector<char> or std::bitset<N> when you need addressability, or
• Copy the value: bool val = isPrime[5]; (perfectly fine for read‑only checks).

Gotcha #2 – std::fill / algorithms expecting bool*:

fill(isPrime.begin(), isPrime.end(), true); // works because fill uses assignment

Most STL algorithms work because they rely on operator=. However, any algorithm that tries to take the address of an element (e.g., std::copy into a bool* buffer) will break.

When to use it: If you only need to read/write individual bits and never take their address, vector<bool> saves memory dramatically. If you need pointer semantics or plan to pass the data to a C API, stick with vector<char> or std::bitset<N> (the latter has fixed size known at compile time).

3. std::array – compile‑time fixed size

Problem: A DP solution for knapsack where the weight capacity is a small constant (say, C = 100).

Before – vector<int> with runtime allocation:

int C = 100;
vector<int> dp(C + 1, 0);
for (auto [w, v] : items) {
    for (int cap = C; cap >= w; --cap)
        dp[cap] = max(dp[cap], dp[cap - w] + v);
}

Each test case incurs a heap allocation for dp. If you have thousands of test cases, the overhead adds up.

After – std::array (stack allocation, zero runtime overhead):

constexpr int C = 100;
array<int, C + 1> dp{}; // zero‑initialized, lives on the stack
for (auto [w, v] : items) {
    for (int cap = C; cap >= w; --cap)
        dp[cap] = max(dp[cap], dp[cap - w] + v);
}

Because C is a constexpr, the array size is known at compile time, and the compiler places dp directly in the function’s stack frame. No new/delete, no cache‑missy heap traversal.

Gotcha: You cannot change the size after construction. If the capacity varies per test case, you either need a different array size (template metaprogramming) or fall back to a vector. In many CP problems, however, the limits are small constants, making array a perfect fit.

Why This New Power Matters

Mastering these niche STL tricks does more than shave a few milliseconds off your runtime — it changes how you think about data.

• With list::splice, you start seeing problems as node rearrangements rather than costly copies, opening doors to elegant solutions for caches, linked‑list simulations, and even certain graph algorithms where edge lists are frequently reordered.
• Understanding the vector<bool> trap saves you from those frustrating “it works locally but fails on the judge” moments, and it teaches you to question the abstraction level of every container you