STL Containers

Quick Revisit

• USE WHEN: Choosing a data structure—match required operations to container
• INVARIANT: Container choice determines complexity: vector O(1) access, set O(log n) lookup, unordered_map O(1) amortized
• TIME: varies by container | SPACE: O(n)
• CLASSIC BUG: Using default hash for unordered_map on Codeforces (hackable—use custom hash)
• PRACTICE: ../12-practice-ladders/01-ladder-1100-to-1400.md

Every container a competitive programmer needs—when to reach for each one, how to use it under time pressure, and the gotchas that cause wrong answers and runtime errors on Codeforces.

How to use this file: Read it top-to-bottom as a lesson on first encounter. During contests, jump straight to the Reference Table, Iterator Invalidation Rules, or Contest Cheat Sheet for quick lookup.

Difficulty: [Beginner]Prerequisites: Fast I/O and Pragmas, Arrays and Strings

Historical Origin: The C++ Standard Template Library was designed by Alexander Stepanov and Meng Lee at Hewlett-Packard in 1994, drawing on Stepanov's decades of work in generic programming. Its inclusion in the C++98 standard transformed competitive programming forever—suddenly every contestant had balanced BSTs, heaps, and hash tables at their fingertips.

Real-Life Analogy: STL containers are like kitchen utensils—a chef could cut everything with a single knife, but reaching for the peeler, grater, or mandoline for the right job is what separates a home cook from a professional.

Mnemonic Anchor: "Vectors for Values, Sets for Searching, Maps for Matching, Queues for Queueing"—if you remember nothing else, this covers 90% of contest container choices.

---

Contents

• vector: Your Default Container
• string: Arrays of Characters
• array: Fixed-Size, Stack-Allocated
• pair and tuple
• set and multiset
• map and unordered_map
• priority_queue
• deque: Double-Ended Queue
• stack and queue
• bitset: Bit Manipulation at Scale
• Choosing the Right Container
• C++ STL Reference Table
• "Before You Code" Checklist
• Implementation
• Operations Reference
• Performance Comparison Table
• Iterator Invalidation Rules
• Problem Patterns & Tricks
• "What Would You Do If...?"
• Contest Cheat Sheet
• Common Mistakes & Debugging
• When NOT to Use STL Containers
• "The Mistake That Teaches"
• "Debug This" Exercises
• Self-Test
• Practice Problems
• Further Reading

---

The single most important insight about STL containers is that the choice of container is your algorithm. When you pick set over vector, you're not just choosing a data structure—you're choosing $O(\log n)$ lookups over $O(n)$ scans. The right container makes a brute-force approach pass; the wrong one turns an optimal algorithm into TLE. Before writing a single line of logic, ask: what operations does this problem demand?

If I Had 5 Minutes

1. Default to vector—contiguous memory, cache-friendly, $O(1)$ random access. Use it unless you need something specific.
2. Need sorted uniqueness or $O(\log n)$ lookup? → set / map. Safe, predictable, no hash attack risk.
3. Need $O(1)$ lookup and can handle hashing? → unordered_map with a custom hash (default hash is hackable on CF).
4. Need only min/max? → priority_queue. Don't use set just for this—heaps are faster by a constant factor.
5. Need bulk bit operations? → bitset<N> runs in $O(N/64)$, turning TLE subset-sum into AC.

Rating Progression

CF Rating	What You Should Know
1200	vector, sort, map for frequency counting, basic set usage
1500	multiset sliding window, priority_queue for greedy/Dijkstra, deque for BFS, bitset basics
1800	Custom hash for unordered_map, coordinate compression with sorted vector, lazy deletion in priority_queue, iterator invalidation rules
2100+	Policy-based order_of_key tree, bitset DP optimization ($O(n\cdot S/64)$), rope/implicit treap when STL falls short, constant-factor optimization (array vs map tradeoffs)

See also: Complexity Analysis for understanding when constant factors matter at each rating tier.

---

vector: Your Default Container for Everything

If you don't know what container to use, use vector. It's a dynamic array—contiguous memory, random access in $O(1)$, and amortized $O(1)$ push to the back.

  Memory layout of vector<int> v = {3, 1, 4, 1, 5}:

  +---+---+---+---+---+---+---+---+
  | 3 | 1 | 4 | 1 | 5 |   |   |   |
  +---+---+---+---+---+---+---+---+
  ^                   ^           ^
  begin()          size=5     capacity=8

When a push_back would exceed capacity, the vector allocates a new block (usually 2× the old size), copies everything over, and frees the old memory. This is why push_back is amortized $O(1)$—the occasional copy costs $O(n)$, but averaged over $n$ pushes it's constant.

vector<int> v;                    // empty
vector<int> v(n);                 // n zeros
vector<int> v(n, -1);            // n copies of -1
vector<int> v = {3, 1, 4};       // initializer list

v.push_back(x);                  // append to end
v.emplace_back(x);               // construct in-place (same for int, matters for pairs)
v.pop_back();                    // remove last element
v.back();                        // last element reference
v.size();                        // number of elements (returns size_t!)
v.empty();                       // true if size == 0
v.clear();                       // remove all elements
v.resize(m);                     // resize to m (truncates or fills with 0)
v.reserve(m);                    // pre-allocate capacity (avoids reallocations)

sort(v.begin(), v.end());        // sort ascending
reverse(v.begin(), v.end());     // reverse

2D vectors come up constantly—grids, adjacency lists, DP tables:

vector<vector<int>> grid(n, vector<int>(m, 0));   // n x m grid of zeros
vector<vector<int>> adj(n);                        // adjacency list
adj[u].push_back(v);                               // add edge u -> v

The thing that bites you: vector<bool> is not a real vector. It's a bitfield that packs 8 booleans per byte. You can't take a pointer or reference to its elements. Use vector<char> or bitset instead when you need normal boolean array behavior.

---

  MEMORY LAYOUT: vector vs set vs unordered_map
  ==============================================

  vector<int> v = {3, 1, 4, 1, 5}

  Memory: [3][1][4][1][5]............   <-- contiguous, cache-friendly
           ^              ^
           v.data()       v.data()+5
           |<--- size --->|<-spare->|

  set<int> s = {1, 3, 4, 5}

  Memory:     +---+       +---+
              | 3 |------>| 5 |     <-- tree nodes scattered in heap
              +---+       +---+
             /     \
          +---+   +---+
          | 1 |   | 4 |
          +---+   +---+
          ^  scattered pointers = cache misses

  unordered_map<int,int> m = {{1,a},{5,b},{3,c}}

  Buckets: [*]->[1,a]  [ ]  [*]->[3,c]  [ ]  [*]->[5,b]  [ ]
            ^                 ^                 ^
            hash(1)%6         hash(3)%6         hash(5)%6

Beyond the general-purpose vector, the STL offers a specialized variant for character data.

string: Arrays of Characters with Superpowers

string is essentially vector<char> with a richer interface for text manipulation.

string s = "hello";
s += " world";                   // concatenation
s.substr(1, 3);                  // "ell" (pos, length)
s.find("ll");                    // 2 (index of first match, string::npos if not found)
s.size();                        // 11

// conversion
int x = stoi("42");             // string to int
long long y = stoll("123456789012345");
string t = to_string(42);       // int to string

// character-level
for (char c : s) { ... }        // iterate
sort(s.begin(), s.end());       // sort characters

The thing that bites you: substr takes (position, length), not (start, end). Also, s.find() returns string::npos (a huge number) on failure—not $-1$. Always compare with s.find(...) != string::npos.

---

array: Fixed-Size, Stack-Allocated

std::array wraps a C-style array with STL compatibility. Size is a compile-time constant, so it lives on the stack. Marginally faster than vector for small, fixed sizes.

array<int, 3> a = {1, 2, 3};
a.fill(0);                      // set all elements to 0
sort(a.begin(), a.end());       // works with STL algorithms

In practice, vector or plain C arrays are more common in contests.

---

pair and tuple: Bundling Values Together

pair is the single most-used utility type in competitive programming. Sorting edges by weight, storing (distance, node) in Dijkstra, returning two values from a function—all pair.

pair<int, int> p = {3, 7};
auto [a, b] = p;                // structured binding (C++17)
p.first;                        // 3
p.second;                       // 7

// pairs sort lexicographically: first by .first, then by .second
vector<pair<int,int>> v = {{3,1}, {1,2}, {3,0}};
sort(v.begin(), v.end());       // {{1,2}, {3,0}, {3,1}}

tuple extends this to 3+ values:

tuple<int, int, string> t = {1, 2, "abc"};
auto [x, y, z] = t;            // structured binding
get<0>(t);                      // 1

The thing that bites you: structured bindings (auto [a, b] = ...) require C++17. On older compilers (rare on CF), use tie(a, b) = p; instead.

Trick—negative for reverse sort: Need to sort by first ascending, second descending? Store {a, -b} and sort normally.

---

set and multiset: Ordered Collections

set keeps elements in sorted order using a balanced BST (red-black tree). Every operation—insert, erase, find, lower_bound—is $O(\log n)$.

When this appears: The problem needs dynamic membership checks, nearest-value queries (closest element above or below a threshold), or maintaining sorted order under insertions and deletions.

  set<int> s = {1, 3, 5, 7, 9}:

          5
         / \
        3   7
       /     \
      1       9

set<int> s;
s.insert(5);                     // add element
s.erase(5);                      // remove element by value
s.count(5);                      // 0 or 1 (use as "contains")
s.find(5);                       // iterator (s.end() if not found)
s.lower_bound(4);                // iterator to first element >= 4 (points to 5)
s.upper_bound(5);                // iterator to first element > 5
*s.begin();                      // smallest element
*s.rbegin();                     // largest element

multiset allows duplicates. Same interface, but beware erase:

multiset<int> ms = {1, 3, 3, 5};
ms.erase(3);                     // removes ALL copies of 3! ms = {1, 5}
ms.erase(ms.find(3));            // removes ONE copy of 3.  ms = {1, 3, 5}

The thing that bites you: s.erase(s.find(x)) on a multiset when x is not present calls erase(end())—undefined behavior. Always check find(x) != end() first.

---

map and unordered_map: Key-Value Stores

map is a sorted associative container (balanced BST), $O(\log n)$ per operation.

When this appears: Frequency counting ("how many of each value?"), grouping by key, or associating data with labels that aren't small bounded integers.

map<string, int> m;
m["alice"] = 100;                // insert or update
m["bob"] = 200;
m.count("alice");                // 1 if key exists, 0 otherwise
m.erase("alice");

for (auto [key, val] : m) {     // iterate in sorted key order
    cout << key << " " << val << "\n";
}

unordered_map uses a hash table—average $O(1)$ per operation, but worst case $O(n)$.

unordered_map<int, int> um;
um[42] = 7;                      // same interface as map

When unordered_map Bites Back: Hash Collision Attacks

On Codeforces, people will hack your solution if you use unordered_map with the default hash. The default hash for integers is essentially the identity function, and an adversary can craft inputs where all keys collide into the same bucket, degrading every operation to $O(n)$.

Fix—use a custom hash:

struct custom_hash {
    static uint64_t splitmix64(uint64_t x) {
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }
    size_t operator()(uint64_t x) const {
        static const uint64_t FIXED_RANDOM =
            chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }
};
unordered_map<int, int, custom_hash> safe_map;

Use map by default in contests. Switch to unordered_map + custom hash only when the $\log n$ factor causes TLE.

---

priority_queue: Heaps for Greedy and Dijkstra

A priority_queue is a max-heap by default—top() returns the largest element.

  priority_queue with {9, 5, 7, 1, 3}:

              9
             / \
            5   7
           / \
          1   3

priority_queue<int> pq;          // max-heap
pq.push(5);
pq.push(3);
pq.push(7);
pq.top();                        // 7
pq.pop();                        // removes 7

// min-heap: flip the comparator
priority_queue<int, vector<int>, greater<int>> min_pq;
min_pq.push(5);
min_pq.push(3);
min_pq.top();                    // 3

Custom comparator (e.g., sort by second element of pair):

auto cmp = [](pair<int,int>& a, pair<int,int>& b) {
    return a.second > b.second;  // min by second
};
priority_queue<pair<int,int>, vector<pair<int,int>>, decltype(cmp)> pq(cmp);

Trick—lazy deletion: You can't erase arbitrary elements from a priority_queue. Mark elements as deleted and skip them when popped.

The thing that bites you: It's a max-heap, not min. Someone writes Dijkstra with the default heap, gets WA, and spends 20 minutes confused. Use greater<int> or negate your values.

---

  MAX-HEAP STRUCTURE (priority_queue<int>)
  ========================================

  After push(3), push(7), push(1), push(5), push(9):

          9              Array: [9, 7, 1, 3, 5]
         / \             Index:  0  1  2  3  4
        7    1
       / \               parent(i) = (i-1)/2
      3   5              left(i)   = 2*i + 1
                         right(i)  = 2*i + 2
  top() = 9  (always the max)
  pop()  removes 9, reshuffles:

          7
         / \
        5    1
       /
      3

deque: Double-Ended Queue

deque supports $O(1)$ push/pop at both ends, plus $O(1)$ random access. The tradeoff: it's implemented as a sequence of fixed-size blocks rather than one contiguous buffer, so it's slower than vector in cache-sensitive loops.

  deque memory layout (blocks of 4):

  Block 0         Block 1         Block 2
  +---+---+---+---+---+---+---+---+---+---+
  | . | . | 3 | 1 | 4 | 1 | 5 | 9 | . | . |
  +---+---+---+---+---+---+---+---+---+---+
            ^                   ^
         front()             back()

deque<int> dq;
dq.push_back(x);                // append to back
dq.push_front(x);               // prepend to front
dq.pop_back();
dq.pop_front();
dq.front();                      // first element
dq.back();                       // last element
dq[i];                           // random access O(1)

Reach for deque when you need both ends: 0-1 BFS, sliding window, and monotonic deque problems all land here.

---

  DEQUE INTERNAL STRUCTURE
  ========================

  deque = array of pointers to fixed-size blocks

  Block ptrs:  [*]-->[a][b][c][d]
               [*]-->[e][f][g][h]   <-- random access: O(1)
               [*]-->[i][j][ ][ ]       (block index + offset)

  push_front: fills from right end of a new front block
  push_back:  fills from left end of a new back block

  vs vector:  +--+--+--+--+--+--+--+
              | a| b| c| d| e| f| g|  <-- one contiguous block
              +--+--+--+--+--+--+--+
              push_front = O(n) shift!

stack and queue: Simple Adapters

stack and queue are thin wrappers around deque that enforce LIFO and FIFO discipline respectively.

stack<int> st;
st.push(5);                      // push to top
st.top();                        // peek at top
st.pop();                        // remove from top (returns void!)

queue<int> q;
q.push(5);                       // push to back
q.front();                       // peek at front
q.pop();                         // remove from front (returns void!)

The thing that bites you: pop() returns void. Read the value with top() or front() before calling pop().

---

bitset: Bit Manipulation at Scale

bitset is a fixed-size array of bits. The killer feature: bitwise operations run in $O(n/64)$ instead of $O(n)$ because the processor operates on 64-bit words at a time.

bitset<1000> bs;                 // 1000 bits, all 0
bs[5] = 1;                      // set bit 5
bs.set(10);                     // set bit 10
bs.reset(10);                   // clear bit 10
bs.flip();                      // flip all bits
bs.count();                     // number of 1-bits
bs.any();                       // true if any bit is 1
bs.none();                      // true if all bits are 0

bitset<1000> a, b;
a & b;                           // AND
a | b;                           // OR
a ^ b;                           // XOR
a << 3;                          // left shift by 3
(a & b).count();                 // number of common bits, O(n/64)

The thing that bites you: The size must be a compile-time constant. You can't write bitset<n> where n is a variable—declare a large enough constant instead. See also Bit Manipulation and Bitset Optimization for advanced bitwise techniques.

Trick—subset-sum in $O(n\cdot S/64)$: Use a bitset<MAXSUM> where bit $i$ is 1 if sum $i$ is achievable. For each new value $v$, do bs |= (bs << v).

---

Choosing the Right Container

The reference table tells you what each container does. It won't teach you the decision process for choosing between them under contest pressure. The real skill isn't knowing that set::insert is $O(\log n)$—it's recognizing, in the first 30 seconds of reading a problem, that the problem is a set problem.

  CONTAINER DECISION FLOWCHART
  ============================

  "I need to store elements and..."

  ...look them up by key?
       |
       +-- Keys are bounded integers [0..MAX]?
       |      YES --> plain array int a[MAX]
       |      NO  --> need sorted order?
       |               YES --> map<K,V>
       |               NO  --> unordered_map<K,V> + custom hash
       |
  ...maintain sorted order?
       |
       +-- Need duplicates?
       |      YES --> multiset<T>
       |      NO  --> set<T>
       |
  ...get the max/min fast?
       |
       +-- Only need the top?
       |      YES --> priority_queue<T>
       |      NO  --> multiset<T> (access both ends)
       |
  ...just iterate and do random access?
              |
              +--> vector<T>  (always the default)

The same decision laid out as a branching map for those who prefer visual flow:

  +---------------------------+
  | What do you need to do?   |
  +-------------+-------------+
                |
       +--------+--------+--------+--------+--------+
       |        |        |        |        |        |
       v        v        v        v        v        v
  +---------+ +------+ +------+ +------+ +------+ +----------+
  | Lookup  | |Sorted| |Min/  | | FIFO | | LIFO | | Sequence |
  | by key? | |order?| |Max?  | |      | |      | | + random |
  +---------+ +------+ +------+ +------+ +------+ | access?  |
       |        |        |        |        |      +----------+
       v        v        v        v        v           |
  Keys in    Need     Only    queue<T> stack<T>        v
  [0..N]?  dupes?    top?                         vector<T>
   |  |      |  |     |  |
   v  v      v  v     v  v
  YES NO   YES NO   YES NO
   |   |    |   |    |   |
   v   v    v   v    v   v
  int  Need multi  set  pq  multi
  a[N] sort? set       <T> set<T>
       |  |
       v  v
      YES NO
       |   |
       v   v
      map  unordered_map
      <K,V> + custom hash

  QUICK DECISION TABLE
  ====================
  +------------------+----------------------------------+-----------------------+
  | Constraint       | Container Choice                 | Why                   |
  +------------------+----------------------------------+-----------------------+
  | Need sorted?     | set / map                        | Red-black tree O(lgn) |
  | O(1) lookup?     | unordered_set/map + custom hash  | Hash table            |
  | Insertion order? | vector                           | Contiguous memory     |
  | Min/max only?    | priority_queue                   | Binary heap           |
  | FIFO?            | queue                            | Adapter over deque    |
  | LIFO?            | stack                            | Adapter over deque    |
  | Both ends?       | deque                            | O(1) front and back   |
  | Sorted + dupes?  | multiset                         | Allows duplicates     |
  | Bulk bit ops?    | bitset<N>                        | O(N/64) word ops      |
  | Keys in [0..M]?  | plain array                      | 30x faster than map   |
  +------------------+----------------------------------+-----------------------+

Containers are not interchangeable. A map where an array suffices costs you 30× in constant factor. An unordered_map without a custom hash gets you hacked on Codeforces. The code compiles either way—the difference is AC vs TLE or WA.

---

C++ STL Reference Table

Container	Header	Ordered?	Duplicates?	Access	Insert/Erase
vector	<vector>	By index	Yes	$O(1)$	Back: $O(1)$ amort.
string	<string>	By index	Yes	$O(1)$	Back: $O(1)$ amort.
array	<array>	By index	Yes	$O(1)$	N/A (fixed)
deque	<deque>	By index	Yes	$O(1)$	Both ends: $O(1)$
stack	<stack>	LIFO	Yes	Top: $O(1)$	Top: $O(1)$
queue	<queue>	FIFO	Yes	Front: $O(1)$	Back: $O(1)$
priority_queue	<queue>	By priority	Yes	Top: $O(1)$	$O(\log n)$
set	<set>	Sorted	No	$O(\log n)$	$O(\log n)$
multiset	<set>	Sorted	Yes	$O(\log n)$	$O(\log n)$
map	<map>	Sorted keys	No (keys)	$O(\log n)$	$O(\log n)$
unordered_map	<unordered_map>	No	No (keys)	$O(1)$ avg	$O(1)$ avg
bitset	<bitset>	By index	N/A	$O(1)$	$O(1)$

With #include <bits/stdc++.h>, individual headers are irrelevant in contest environments.

---

"Before You Code" Checklist—Container Selection

Before typing a single line, run through this checklist:

• [ ] What are the key operations? List the 2–3 operations your solution needs most: lookup, insert, min/max, iterate in order, random access.
• [ ] What are the constraints? If $n\le {10}^5$, an $O(n\log n)$ set is fine. If $n\le {10}^7$, you may need arrays or bitset.
• [ ] Are keys bounded integers? If values fit in $[0,M]$ for reasonable $M$ ($\le {10}^7$), use a plain array—it's 30× faster than map.
• [ ] Do I need to modify the container during iteration? If yes, prefer set/map (safe erase) over vector/unordered_map (iterator invalidation traps).
• [ ] Is my solution hackable? If using unordered_map on Codeforces, add a custom hash. If using map when an array suffices, verify the constant factor won't cause TLE.

See also: Data Structure Selection Guide for a deeper decision framework.

---

Implementation (Contest-Ready)

Container Cheat Code—Minimal

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

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

    // vector
    int n; cin >> n;
    vector<int> v(n);
    for (auto& x : v) cin >> x;             // Invariant: v[0..i-1] are filled from input
    sort(v.begin(), v.end());

    // set / multiset
    set<int> s(v.begin(), v.end());          // deduplicated sorted
    auto it = s.lower_bound(42);             // first >= 42

    // map
    map<int, int> freq;
    for (int x : v) freq[x]++;

    // priority_queue (min-heap)
    priority_queue<int, vector<int>, greater<int>> pq;
    for (int x : v) pq.push(x);               // Invariant: pq contains all elements pushed so far
    while (!pq.empty()) { cout << pq.top() << " "; pq.pop(); }  // Invariant: outputs in ascending order
    cout << "\n";

    // deque
    deque<int> dq;
    dq.push_front(1);
    dq.push_back(2);

    // stack / queue
    stack<int> st;
    queue<int> q;
    st.push(10); q.push(20);

    // bitset
    bitset<100> bs;
    bs[0] = 1; bs[5] = 1;
    cout << bs.count() << "\n";              // 2

    // pair / tuple
    vector<pair<int,int>> edges;
    edges.emplace_back(3, 7);
    auto [u, w] = edges[0];

    // string
    string s2 = "hello";
    s2 += " world";
    cout << s2.substr(0, 5) << "\n";        // "hello"
}

Container Cheat Code—Explained

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

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

    int n; cin >> n;
    vector<int> v(n);
    for (auto& x : v) cin >> x;             // read by reference to fill

    sort(v.begin(), v.end());                // O(n log n)
    auto it = lower_bound(v.begin(), v.end(), 42);  // first element >= 42
    int idx = it - v.begin();                // convert iterator to index

    map<int, int> freq;
    for (int x : v) freq[x]++;              // operator[] creates entry with 0 if missing

    set<int> s(v.begin(), v.end());          // construct from range: deduplicated + sorted
    if (s.count(42)) cout << "found\n";      // O(log n), returns 0 or 1

    multiset<int> ms(v.begin(), v.end());
    auto pos = ms.find(v[0]);
    if (pos != ms.end()) ms.erase(pos);     // erase ONE copy (iterator, not value!)

    // default is MAX-heap. For min-heap, use greater<int>
    priority_queue<int, vector<int>, greater<int>> pq;
    for (int x : v) pq.push(x);             // O(log n) per push
    while (!pq.empty()) {
        cout << pq.top() << " ";             // O(1) peek, then O(log n) pop
        pq.pop();
    }

    deque<int> dq;
    dq.push_front(1);                        // O(1) -- works at both ends
    dq.push_back(2);

    bitset<100001> reachable;
    reachable[0] = 1;                        // sum 0 is achievable
    for (int x : v)
        reachable |= (reachable << x);       // subset-sum in O(n * MAXSUM / 64)

    // sort by first ascending, second descending: negate second
    vector<pair<int,int>> events;
    for (int i = 0; i < n; i++)
        events.push_back({v[i], -i});
    sort(events.begin(), events.end());
}

---

Operations Reference

Use this table during contests to sanity-check complexity before you commit to a container.

Operation	vector	deque	set/multiset	map	unordered_map	priority_queue
push_back/push	$O(1)$*	$O(1)$*	--	--	--	$O(\log n)$
push_front	$O(n)$	$O(1)$*	--	--	--	--
pop/pop_back	$O(1)$	$O(1)$	--	--	--	$O(\log n)$
operator[]	$O(1)$	$O(1)$	--	$O(\log n)$	$O(1)$ avg	--
insert	$O(n)$	$O(n)$	$O(\log n)$	$O(\log n)$	$O(1)$ avg	--
erase(pos/key)	$O(n)$	$O(n)$	$O(\log n)$	$O(\log n)$	$O(1)$ avg	--
find/count	$O(n)$	$O(n)$	$O(\log n)$	$O(\log n)$	$O(1)$ avg	--
lower_bound	$O(\log n)$(*)	--	$O(\log n)$	$O(\log n)$	--	--
top/front/back	$O(1)$	$O(1)$	--	--	--	$O(1)$

Amortized. ()On sorted vector only. unordered_map worst case is $O(n)$ for all ops.

---

Performance Comparison Table: Average and Worst Case

Average-case numbers look great on paper; worst-case numbers are what actually matter under adversarial inputs. This table covers both.

Container	insert avg	insert worst	find avg	find worst	erase avg	erase worst	iterate all	memory overhead
vector	$O(1)$* back; $O(n)$ mid	$O(n)$	$O(n)$	$O(n)$	$O(n)$	$O(n)$	$O(n)$, cache-friendly	Low (~1.5x used)
deque	$O(1)$ ends; $O(n)$ mid	$O(n)$	$O(n)$	$O(n)$	$O(n)$	$O(n)$	$O(n)$, moderate cache	Moderate (block ptrs)
list	$O(1)$ at iterator	$O(1)$	$O(n)$	$O(n)$	$O(1)$ at iterator	$O(1)$	$O(n)$, cache-hostile	High (2 ptrs/node)
set	$O(\log n)$	$O(\log n)$	$O(\log n)$	$O(\log n)$	$O(\log n)$	$O(\log n)$	$O(n)$, cache-hostile	High (3 ptrs/node)
unordered_set	$O(1)$	$O(n)$ rehash	$O(1)$	$O(n)$	$O(1)$	$O(n)$	$O(n+buckets)$	High (buckets + nodes)
map	$O(\log n)$	$O(\log n)$	$O(\log n)$	$O(\log n)$	$O(\log n)$	$O(\log n)$	$O(n)$, cache-hostile	High (3 ptrs/node)
unordered_map	$O(1)$	$O(n)$ rehash	$O(1)$	$O(n)$	$O(1)$	$O(n)$	$O(n+buckets)$	High (buckets + nodes)
priority_queue	$O(\log n)$	$O(\log n)$	N/A	N/A	N/A (top only)	$O(\log n)$	N/A	Low (vector-backed)
stack	$O(1)$	$O(1)$*	N/A	N/A	$O(1)$ top	$O(1)$	N/A	Low (deque-backed)
queue	$O(1)$	$O(1)$*	N/A	N/A	$O(1)$ front	$O(1)$	N/A	Low (deque-backed)

* Amortized $O(1)$; occasional reallocation costs $O(n)$.

Key takeaway: set/map give guaranteed $O(\log n)$—no worst-case blowup. unordered_* containers are faster on average but vulnerable to adversarial inputs on Codeforces. When in doubt, prefer the ordered variant.

Pattern Fingerprint: $n\le {10}^6$ with frequent lookups → unordered_map + custom hash. $n\le {10}^5$ with lookups → map is safe enough.

---

Iterator Invalidation Rules: Complete Reference

Iterator invalidation is behind some of the most baffling runtime errors in competitive programming—a single dangling iterator can cause crashes, wrong answers, or worst of all, correct behavior on your machine but RE on the judge.

Container	insert invalidates	erase invalidates
vector	All if reallocation; else from insertion point onward	From erased position onward
deque	All (both iterators and references)	All (inserting/erasing at ends only invalidates the end iterator)
list	None	Only the erased element's iterator
set / multiset	None	Only the erased element's iterator
map / multimap	None	Only the erased element's iterator
unordered_set / unordered_map	All if rehash occurs; else none	Only the erased element's iterator

Iterator Invalidation: The Danger in Code

Danger 1: Erasing from a vector while iterating

// BUG: iterator invalidated after erase, skips elements
vector<int> v = {1, 2, 3, 4, 5};
for (auto it = v.begin(); it != v.end(); ++it) {
    if (*it % 2 == 0) v.erase(it);  // iterator invalidated!
}

// FIX: use erase-remove idiom
v.erase(remove_if(v.begin(), v.end(),
    [](int x) { return x % 2 == 0; }), v.end());

Danger 2: Inserting into a vector invalidates saved iterators

vector<int> v = {1, 2, 3};
auto it = v.begin() + 1;  // points to 2
v.push_back(4);            // may reallocate!
cout << *it;               // UNDEFINED BEHAVIOR: it may be dangling

Danger 3: Modifying an unordered_map during iteration

unordered_map<int, int> m = {{1,10}, {2,20}, {3,30}};
for (auto it = m.begin(); it != m.end(); ++it) {
    if (it->second < 25)
        m.erase(it);  // it is invalidated, ++it is UB!
}

// FIX: use post-increment before erase
for (auto it = m.begin(); it != m.end(); ) {
    // Invariant: it is a valid iterator to a not-yet-examined element
    if (it->second < 25)
        it = m.erase(it);  // C++11: erase returns next valid iterator
    else
        ++it;
}

Safe pattern for set/map: Since only the erased iterator is invalidated, the classic it = s.erase(it) pattern works perfectly—which is one reason set/map are often safer when you need to modify the container during iteration.

See also: Debugging and Stress Testing for techniques to catch iterator invalidation bugs with AddressSanitizer.

---

Problem Patterns & Tricks

Knowing the API is table stakes. The real contest skill is recognizing which container a problem demands in the first 30 seconds of reading. Each pattern below pairs a problem shape with the container that solves it—and names the fingerprint cue that triggers the match.

Pattern 1—Coordinate Compression with Sorted vector

Values up to ${10}^9$ but only relative order matters? Compress to ranks $0,1,\dots ,k-1$:

vector<int> vals(v.begin(), v.end());
sort(vals.begin(), vals.end());
vals.erase(unique(vals.begin(), vals.end()), vals.end());
// Invariant: after this loop, each v[i] holds its rank in [0, vals.size())
for (int& x : v)
    x = lower_bound(vals.begin(), vals.end(), x) - vals.begin();

Pattern Fingerprint: values up to ${10}^9$ but only $n\le 2\cdot {10}^5$ distinct → coordinate compression with sorted vector.

Problems: CF 1311D — Three Integers, CSES — Josephus Problem II

Pattern 2—Sliding Window Max/Min with multiset

Maintain a multiset of the current window. Min is *ms.begin(), max is *ms.rbegin(). Always erase by iterator, not value.

multiset<int> ms;
for (int i = 0; i < n; i++) {
    // Invariant: ms contains exactly v[max(0,i-k+1)..i]
    ms.insert(v[i]);
    if (i >= k) ms.erase(ms.find(v[i - k]));  // shrink window to size k
    if (i >= k - 1) cout << *ms.rbegin() << " ";
}

Pattern Fingerprint: sliding window of size $k$ + need min/max/median → multiset with careful erase-by-iterator.

Problems: CF 1918C — XOR-distance, CSES — Sliding Median

Pattern 3—Custom Sort with pair

Sort by end time, break ties by start? Store {end, start} and sort. Descending? Negate the value.

vector<pair<int,int>> seg(n);
for (auto& [l, r] : seg) cin >> l >> r;
sort(seg.begin(), seg.end(), [](auto& a, auto& b) {
    return a.second < b.second;
});

Pattern Fingerprint: "sort by X, break ties by Y" → store as pair<X, Y> and leverage lexicographic sort.

Problems: CF 1472D — Even-Odd Game

Pattern 4—Frequency Counting with map

map<int, int> freq;
for (int x : v) freq[x]++;   // Invariant: freq[x] == count of x in elements processed so far
int max_freq = 0;
for (auto [val, cnt] : freq) max_freq = max(max_freq, cnt);  // Invariant: max_freq is the maximum frequency seen so far

Pattern Fingerprint: "how many pairs with property X?" → frequency map on a transformed key.

Problems: CF 1520D — Same Differences

Pattern 5—Subset Sum with bitset

Classic DP subset sum in $O(n\cdot S)$ becomes $O(n\cdot S/64)$ with bitset—often the difference between TLE and AC.

bitset<100001> dp;
dp[0] = 1;
for (int x : v) dp |= (dp << x);
cout << (dp[target] ? "YES" : "NO") << "\n";

Pattern Fingerprint: "is sum $S$ achievable?" with small $S$ → bitset DP in $O(n\cdot S/64)$.

Problems: CF 1516C — Baby Ehab Partitions Again

Pattern 6—Dijkstra with priority_queue

Min-heap of {distance, node}. Pair comparison sorts by distance first—so the closest unvisited node always surfaces at top().

vector<long long> dist(n, LLONG_MAX);
priority_queue<pair<long long,int>, vector<pair<long long,int>>,
               greater<>> pq;
dist[src] = 0;
pq.push({0, src});
while (!pq.empty()) {
    auto [d, u] = pq.top(); pq.pop();
    if (d > dist[u]) continue;
    for (auto [v, w] : adj[u])
        if (dist[u] + w < dist[v])
            pq.push({dist[v] = dist[u] + w, v});
}

Pattern Fingerprint: weighted shortest path with non-negative edges → priority_queue min-heap + lazy deletion.

Problems: CSES — Shortest Routes I

---

"What Would You Do If...?" Container Scenario Challenges

Scenario 1: You need to maintain a dynamic collection where you frequently insert elements, delete the minimum, and delete arbitrary elements by value. Which container?

Answer: multiset<int>. It gives $O(\log n)$ insert, *ms.begin() for min, and ms.erase(ms.find(x)) for arbitrary deletion. A priority_queue can't do arbitrary deletion—you'd have to fake it with the lazy deletion hack, which is messier.

Scenario 2: You have $n\le 5\cdot {10}^6$ integers in $[0,{10}^7]$. You need to count distinct values. Which container?

Answer: A plain bool visited[10000001] array—not set, not unordered_set. With $5\cdot {10}^6$ elements, tree-based containers are too slow by constant factor and hash tables waste memory. The array uses 10 MB and runs in $O(n)$ with perfect cache behavior.

Scenario 3: You're implementing 0-1 BFS (edges with weight 0 or 1). Which container replaces the standard BFS queue?

Answer: deque<int>. Push weight-0 neighbors to the front, weight-1 neighbors to the back. This gives $O(V+E)$ shortest paths without a priority queue. See Binary Search for related optimization techniques.

---

Contest Cheat Sheet

+------------------------------------------------------------------+
|  STL CONTAINERS  --  Quick Selection Guide                       |
+------------------------------------------------------------------+
|                                                                  |
|  Need dynamic array?             -> vector<int>                  |
|  Need key-value store?           -> map<K,V>  (safe default)     |
|  Need fast key-value?            -> unordered_map + custom hash  |
|  Need sorted unique elements?    -> set<int>                     |
|  Need sorted with duplicates?    -> multiset<int>                |
|  Need min/max quickly?           -> priority_queue               |
|  Need both ends?                 -> deque<int>                   |
|  Need LIFO?                      -> stack<int>                   |
|  Need FIFO?                      -> queue<int>                   |
|  Need bulk bit operations?       -> bitset<N>                    |
|                                                                  |
|  COMMON TRAPS:                                                   |
|    - pq is MAX-heap. Min: greater<int> or negate values          |
|    - multiset.erase(val) kills ALL copies. Use erase(find(val))  |
|    - pop() returns void. Read top()/front() FIRST                |
|    - vector<bool> is special. Use vector<char> instead            |
|    - unordered_map default hash is hackable on CF                |
|                                                                  |
|  COMPLEXITY QUICK REF:                                           |
|    vector/deque/stack/queue ops:  O(1) amortized                 |
|    set/map/multiset ops:          O(log n)                       |
|    unordered_map ops:             O(1) avg, O(n) worst           |
|    priority_queue push/pop:       O(log n), top: O(1)            |
|    bitset bulk ops:               O(n/64)                        |
+------------------------------------------------------------------+

---

Common Mistakes & Debugging

Iterator Invalidation

The rules vary significantly by container—see the Iterator Invalidation Rules reference table above for the full breakdown. The safe universal pattern for erasing during iteration:

// CORRECT: erase returns next valid iterator (set, map, unordered_map)
for (auto it = s.begin(); it != s.end(); )
    if (*it % 2 == 0) it = s.erase(it);
    else ++it;

// For vector: use the erase-remove idiom instead of manual iteration
v.erase(remove_if(v.begin(), v.end(), [](int x){ return x % 2 == 0; }), v.end());

vector<bool> Is Not a Real vector

It packs bits. auto x = v[0] gives a proxy object, not a bool&. Use vector<char> for normal boolean array behavior.

multiset erase(value) Removes ALL Copies

This is the most common multiset bug in contests.

multiset<int> ms = {3, 3, 3, 5};
ms.erase(3);                     // ms = {5}       -- all 3s gone!
ms.erase(ms.find(3));            // ms = {3, 3, 5} -- only one 3 removed

unordered_map Worst Case

With the default hash, an adversary can force $O(n)$ per operation on Codeforces. Always use the custom hash from the map section, or just use map.

priority_queue Is a Max-Heap

priority_queue<int> pq;
pq.push(1); pq.push(5); pq.push(3);
pq.top();   // 5, not 1!
// for min-heap: priority_queue<int, vector<int>, greater<int>>

Empty Container Access Is Undefined Behavior

// WRONG:
stack<int> st;
cout << st.top();                // undefined behavior (crash)

// CORRECT:
if (!st.empty()) cout << st.top();

Mental Traps

"I know this container, so I'll use it everywhere." People learn map first and reach for it when a plain array suffices. Or they learn set and use it when sort + unique on a vector is 10× faster. Familiarity is comfortable; correctness is what you need. Ask "what operations does this problem actually require?" before your fingers move.

  THE FAMILIARITY TRAP
  ====================

  You learned:    map<int,int>
  You should use: int cnt[MAXV]

  Performance gap (bounded integer keys):
  +------+------+------+------+------+------+
  | map  | #### | #### | #### | #### | #### |  ~150ns/op
  +------+------+------+------+------+------+
  |array | #    |      |      |      |      |  ~5ns/op
  +------+------+------+------+------+------+
         30x slower -- same Big-O, very different wall-clock

"Unordered is always faster than ordered."unordered_map has $O(1)$ average but $O(n)$ worst case. On Codeforces, adversarial inputs exploit the default hash to force that worst case. map at $O(\log n)$ is safer and usually fast enough. Don't optimize prematurely—optimize correctly.

"priority_queue gives me sorted access." It gives you only the top element. You can't iterate, and you can't peek at the second element. Popping everything to observe sorted order destroys the queue. If you need both extremum access and iteration, use multiset.

---

When NOT to Use STL Containers

STL containers are not always the answer. Here are the cases where they're genuinely too slow or too heavy, and what to reach for instead.

When $n>{10}^6$ and you're using map or set: The $O(\log n)$ per operation with roughly 200 ns constant factor means roughly $4\cdot {10}^8$ ns for $2\cdot {10}^6$ operations—borderline TLE territory. Use arrays with Coordinate Compression instead.

When you need order-statistic operations (k-th element):set can't find "the k-th smallest" efficiently. You need a policy-based tree (__gnu_pbds::tree) or a Segment Tree on compressed values.

When unordered_map with $n>{10}^6$ causes memory issues: Each unordered_map entry carries 50–70 bytes of overhead. At ${10}^7$ entries, that's 500+ MB. Use open-addressing hash (e.g., gp_hash_table from pb_ds) or a plain array.

When priority_queue needs decrease-key:priority_queue has no decrease-key operation. For algorithms that need it (like Prim's MST), use set as a heap (erase + reinsert) or fall back to lazy deletion.

When bitset size must be dynamic:bitset<N> requires compile-time $N$. For a dynamic-size bitset, use vector<uint64_t> with manual bit manipulation.

When cache performance matters critically:set, map, and list scatter pointer-based nodes across the heap—catastrophic for CPU cache. For read-heavy workloads, a sorted vector with lower_bound often beats set despite worse asymptotic insert cost.

---

"The Mistake That Teaches": A Debugging Story

The scene: CF Round #800, Problem D. Twenty minutes left.

You need to process $2\cdot {10}^5$ queries, each asking "how many elements less than $x$?" on a dynamic collection. multiset is sorted, so distance(ms.begin(), ms.lower_bound(x)) should give the count in $O(\log n)$, right?

The submission: TLE.

Here's why. distance() on a multiset iterator is $O(n)$, not $O(\log n)$. A balanced BST doesn't support random access—you can't jump to the k-th node; you walk link by link. Your solution looks like $O(n\log n)$ but runs like $O(n^2)$, and the compiler never said a word.

The fix: Use order_of_key() from a policy-based tree, or maintain a BIT/Fenwick Tree on compressed values to answer rank queries in $O(\log n)$.

The lesson: std::distance is $O(1)$ for random-access iterators (vector, deque) but $O(n)$ for bidirectional iterators (set, map, list). The distinction never appears in a compilation error. Know it cold.

---

"Debug This" Exercises

Find the bug in each snippet. Answers are below the fold.

Bug 1: The Vanishing Elements

vector<int> v = {1, 2, 3, 4, 5, 6};
for (int i = 0; i < v.size(); i++) {
    if (v[i] % 2 == 0) {
        v.erase(v.begin() + i);
    }
}
// Expected: {1, 3, 5}
// Actual: ???

Bug 2: The Silent Wrong Answer

multiset<int> ms = {5, 3, 5, 1, 5};
int count = 0;
while (ms.count(5) > 0) {
    ms.erase(5);
    count++;
}
cout << count << endl;
// Expected: 3  (there are three 5s)
// Actual: ???

Bug 3: The Mysterious TLE

unordered_map<int, int> freq;
int n; cin >> n;
for (int i = 0; i < n; i++) {
    int x; cin >> x;
    freq[x]++;
}
// Works on local machine, TLE on Codeforces with n = 2*10^5
// Why?

Bug 4: The Infinite Loop

set<int> s = {1, 2, 3, 4, 5};
for (auto it = s.begin(); it != s.end(); ++it) {
    s.insert(*it * 2);
}

Answers (click to reveal)

Bug 1: After erasing index i, element i+1 shifts to index i, but the loop increments i—skipping it. Result: {1, 3, 5, 6} (6 is never removed). Fix: Decrement i after erase, iterate backwards, or use the erase-remove idiom.

Bug 2: ms.erase(5) removes all copies of 5 at once, so the loop runs only once. count is 1, not 3. Fix: Use ms.erase(ms.find(5)) to remove one copy at a time.

Bug 3: Default hash is hackable. An adversary crafts inputs where all keys collide, making every freq[x]++ take $O(n)$ time → $O(n^2)$ total. Fix: Use custom_hash (see the map section) or switch to map.

Bug 4: Inserting *it * 2 into the set creates new elements the iterator hasn't reached yet. For values like 1→2, 2→4, 4→8, … the set grows without bound. Fix: Collect new elements in a separate container and insert after the loop.

---

Self-Test

• [ ] Without references, name 3 containers with O(1) random access and 3 with O(log n) insert.
• [ ] Write the one-line fix for multiset::erase(val) removing all copies instead of one.
• [ ] Explain why vector<bool> is dangerous and what to use instead.
• [ ] Declare a min-heap priority_queue from memory—get the template arguments right.
• [ ] Given keys in [0, 10^6], explain the performance difference between array and unordered_map.
• [ ] Write a custom hash for unordered_map<int,int> that prevents hash collision attacks.
• [ ] State which containers invalidate all iterators on insert vs only the erased iterator.

---

Practice Problems

Work through these roughly in order. For more graded practice, see Practice Ladder 1100–1400.

#	Problem	Source	Difficulty	Key Containers
1	Distinct Numbers	CSES	Easy	set
2	Even-Odd Game	CF 1472D	Easy (1200)	priority_queue, sort
3	Same Differences	CF 1520D	Easy (1200)	map frequency counting
4	Concert Tickets	CSES	Medium	multiset, upper_bound
5	Sliding Median	CSES	Medium	multiset sliding window
6	Room Allocation	CSES	Medium	priority_queue, greedy
7	Baby Ehab Partitions Again	CF 1516C	Medium (1700)	bitset subset sum
8	Shortest Routes I	CSES	Medium	priority_queue Dijkstra
9	Josephus Problem II	CSES	Hard	set with order statistics
10	Array Partition	CF 1741D	Medium (1500)	set, prefix max/suffix min
11	Potions	CF 1526C2	Medium (1600)	priority_queue, greedy
12	Treasure Chest	CF 1837D	Medium-Hard (1800)	map, binary search
13	Range Set Query	CSES	Medium-Hard	set, last-occurrence tracking
14	Xenia and Bit Operations	CF 339D	Medium-Hard (1700)	bitset, segment tree
15	Magic Powder - 2	CF 670D2	Hard (1900)	map, binary search

---

Further Reading

• C++ STL Containers — cppreference — definitive reference for every container
• Blowing up unordered_map — CF Blog by neal — the hash collision attack explained
• C++ Tricks — CF Blog by competitive — useful STL tips for contests
• USACO Guide — Built-in Data Structures — beginner-friendly overview
• cp-algorithms — Data Structures — advanced techniques built on these containers

---

What to Solve Next

• STL Algorithms—sort, lower_bound, next_permutation, and the algorithm toolkit that makes these containers truly powerful.
• Data Structures chapter—segment trees, Fenwick trees, and the structures you build on top of STL containers.
• Practice Ladder 1100–1400—graded problems that drill container choice under contest pressure.