STL Containers

A practical, interview-focused reference for every STL container you will touch in competitive programming and systems interviews. Every container entry includes the header, a usage cheat sheet, a complete complexity table, gotchas, and a real interview use case.

All examples assume:

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

---

vector<T>

Header: #include <vector>When to use: Default dynamic array. You want this 90% of the time you need a sequence. Cache-friendly, supports random access, and grows on demand.

Basic Usage

vector<int> a;                       // empty
vector<int> b(5);                    // size 5, value 0
vector<int> c(5, 42);                // size 5, all 42
vector<int> d{1, 2, 3, 4};           // initializer list
vector<int> e(d.begin(), d.end());   // from iterators
vector<int> f = d;                   // copy

a.push_back(10);                     // append
a.pop_back();                        // remove last
int x = a[0];                        // unchecked access
int y = a.at(0);                     // throws std::out_of_range if OOB
int first = a.front();               // a[0]
int last  = a.back();                // a[size-1]

a.size();                            // number of elements
a.empty();                           // size == 0
a.clear();                           // size -> 0 (capacity unchanged)
a.resize(10);                        // grow/shrink (new slots zero-initialized)
a.resize(10, -1);                    // grow with fill value
a.reserve(1000);                     // pre-allocate capacity (no size change)
a.capacity();                        // allocated buffer size

a.insert(a.begin() + 2, 99);         // O(n)
a.erase(a.begin() + 2);              // O(n)
a.erase(a.begin() + 1, a.begin()+3); // range erase

for (auto it = a.begin(); it != a.end(); ++it)  { /* forward */ }
for (auto it = a.rbegin(); it != a.rend(); ++it){ /* reverse */ }
for (int x : a)       { /* copy */ }
for (int& x : a)      { /* mutate in place */ }
for (const auto& x : a) { /* no copy */ }

2D Vectors

int m = 3, n = 4;
vector<vector<int>> grid(m, vector<int>(n, 0));   // m x n grid of zeros
grid[1][2] = 7;

// 3D: m x n x p
vector<vector<vector<int>>> cube(m,
    vector<vector<int>>(n, vector<int>(p, 0)));

Complexity

Operation	Time	Notes
push_back	O(1) amortized	Occasional O(n) reallocation
pop_back	O(1)
operator[], at	O(1)	at bounds-checks
front, back	O(1)
insert(pos, x)	O(n)	Shifts tail; O(1) only at end
erase(pos)	O(n)	Shifts tail
clear	O(n)	Destructor per element
resize	O(n)
reserve	O(n)	Only reallocates if new cap > current
size, empty, capacity	O(1)
Iteration	O(n)

Common Gotchas

• Iterator invalidation on reallocation. Any push_back, insert, resize, or reserve that grows capacity invalidates all iterators/pointers/references. Save the size, not iterators, across growth.
• push_back is O(1) amortized, not worst-case. Individual calls may trigger a full copy. If you know the final size, reserve() upfront.
• a[i] on an out-of-bounds index is UB. Use at() while debugging.
• erase returns the iterator to the element after the erased one. Use it when erasing in a loop: it = v.erase(it).
• vector<bool> is a bit-packed specialization. It does not behave like a normal container: auto& b = v[i] gives a proxy, not a real bool&. Prefer vector<char> or bitset if that matters.

Example Interview Use

Sliding window maximum, two-pointer problems, and anything with "array of integers" as input. Also the default backing store for stacks, and for adjacency lists in graphs:

vector<vector<int>> adj(n);          // graph with n vertices
adj[u].push_back(v);                 // add edge u -> v

---

deque<T>

Header: #include <deque>When to use: You need O(1) insertion/deletion at both ends. Great for sliding window problems, BFS where you occasionally push to the front, and as the backing store for stack/queue.

Basic Usage

deque<int> dq;
dq.push_back(1);
dq.push_front(2);        // [2, 1]
dq.pop_back();
dq.pop_front();
int f = dq.front();
int b = dq.back();
int x = dq[0];           // random access supported

Complexity

Operation	Time	Notes
push_back, push_front	O(1) amortized
pop_back, pop_front	O(1)
operator[], at	O(1)	Slightly slower than vector's
insert/erase in middle	O(n)
Iteration	O(n)

Common Gotchas

• Memory is not contiguous. You cannot pass &dq[0] to a C API expecting a flat array.
• Slower than vector in practice for push_back-only workloads. Use vector unless you actually need front-end ops.
• Inserting in the middle invalidates all iterators (but references may survive on some implementations — don't rely on it).

Example Interview Use

Sliding window maximum with a monotonic deque: maintain indices in decreasing order of values, pop from back when a larger value arrives, pop from front when the index falls out of the window.

deque<int> dq;
for (int i = 0; i < n; ++i) {
    while (!dq.empty() && a[dq.back()] <= a[i]) dq.pop_back();
    dq.push_back(i);
    if (dq.front() <= i - k) dq.pop_front();
    if (i >= k - 1) cout << a[dq.front()] << ' ';
}

---

list<T>

Header: #include <list>When to use: Rarely in interviews. The one legitimate case is when you need O(1) splice between lists and stable iterators/pointers under arbitrary insertions and removals — this is the only STL container where neither insert nor erase invalidates any iterator other than the one erased. This is exactly what you want for LRU cache design.

Basic Usage

list<int> L{1, 2, 3, 4};
L.push_back(5);
L.push_front(0);
L.pop_back();
L.pop_front();

auto it = L.begin(); ++it; ++it;
L.insert(it, 99);        // insert before iterator
L.erase(it);             // O(1)

list<int> other{100, 200};
L.splice(L.begin(), other);          // move all of `other` to front of L in O(1)
L.splice(L.end(), other, other.begin()); // move single node

Complexity

Operation	Time	Notes
push_front, push_back, pop_front, pop_back	O(1)
insert, erase at iterator	O(1)
splice	O(1)	For a single element or whole list
find / lookup by value	O(n)	No random access
size	O(1)	Since C++11
operator[]	does not exist	No random access

Common Gotchas

• Worst cache locality of any STL container. Each node is a separate heap allocation. Linear scans are dramatically slower than vector in practice even though both are "O(n)".
• No random access. You cannot do L[3]; you must iterate.
• Most "list" problems in interviews want vector instead. The exception is LRU cache.

Example Interview Use

LRU cache: store nodes in a list<pair<Key, Value>> and keep a unordered_map<Key, list_iterator>. Every access does O(1) lookup then splice to the front. The iterator stays valid across splices.

---

string

Header: #include <string>When to use: Text data, any problem where input is characters. string is effectively a vector<char> with extra string-specific operations and small-string optimization.

Basic Usage

string s = "hello";
string t(5, 'x');                // "xxxxx"
string u = s + " world";         // concat
s += '!';                        // append char
s.push_back('?');                // same

s.size();                        // same as length()
s[0];                            // 'h'
s.substr(1, 3);                  // "ell" — (start, length)
s.substr(2);                     // "llo" — (start to end)

s.find("ll");                    // index or string::npos
s.find('x');                     // index or string::npos
s.rfind("l");                    // last occurrence
if (s.find("zz") == string::npos) { /* not found */ }

s.compare("help");               // <0, 0, >0
s == "hello";                    // lexicographic
s < "world";                     // works

const char* c = s.c_str();       // null-terminated C string

// Conversions
int n         = stoi("42");
long long ll  = stoll("10000000000");
double d      = stod("3.14");
string sx     = to_string(42);
string sy     = to_string(3.14);

Complexity

Operation	Time	Notes
operator[], at, front, back	O(1)
push_back, pop_back	O(1) amortized
+=, append	O(m)	m = length added
s + t	O(n+m)	Builds new string
substr(pos, len)	O(len)	Copies
find, rfind	O(n*m)	Naive search
size, empty	O(1)
insert, erase in middle	O(n)

Common Gotchas

• s.find(x) returns string::npos (which is size_t(-1) = huge number) when not found. Comparing to -1 with a signed int will misbehave. Always compare to string::npos.
• substr(pos, len) copies. In tight loops, prefer string_view (C++17) to avoid allocation.
• stoi throws on bad input (std::invalid_argument) and overflow (std::out_of_range). Wrap in try/catch if input isn't trusted.
• + creates a new string each call. For repeated concatenation, use += or ostringstream, or reserve upfront.

Example Interview Use

Palindrome checks, anagram grouping, string parsing, KMP pattern matching. The find/substr pair shows up constantly.

// Split by delimiter
vector<string> split(const string& s, char d) {
    vector<string> out;
    string cur;
    for (char c : s) {
        if (c == d) { out.push_back(cur); cur.clear(); }
        else cur += c;
    }
    out.push_back(cur);
    return out;
}

---

array<T, N>

Header: #include <array>When to use: Fixed-size sequence known at compile time. Zero overhead over a C-array, but with proper STL semantics (.size(), iterators, copyable, usable with algorithms).

Basic Usage

array<int, 5> a = {1, 2, 3, 4, 5};
a[0] = 10;
a.size();              // 5 (compile-time constant)
sort(a.begin(), a.end());

array<array<int, 3>, 2> grid = {{{1,2,3}, {4,5,6}}};

Complexity

Operation	Time	Notes
operator[], at, front, back	O(1)
size, empty	O(1)	compile-time
Iteration	O(N)

When to pick array over alternatives

You want...	Use
Fixed size, stack-allocated, zero overhead	array<T, N>
Dynamic size	vector<T>
Raw C interop only	C-array T[N]

Interview Tip

In problems with small fixed dimensions (chessboards, dice, 26 lowercase letters), array<int, 26> is cleaner and faster than vector<int>(26).

---

stack<T>

Header: #include <stack>When to use: LIFO — parentheses matching, monotonic stacks, DFS on iterative code, expression evaluation.

Basic Usage

stack<int> st;
st.push(1);
st.push(2);
st.top();        // 2
st.pop();        // returns void! Use top() first.
st.size();
st.empty();

Complexity

Operation	Time	Notes
push, pop, top, size, empty	O(1)

Common Gotchas

• pop() returns void. You must call top() first to read the element, then pop() to remove.
• Default backing container is deque<T>. You can swap in a vector: stack<int, vector<int>> — usually a bit faster.

Example Interview Use

Next greater element (monotonic stack):

vector<int> nge(vector<int>& a) {
    int n = a.size();
    vector<int> res(n, -1);
    stack<int> st;                     // stores indices
    for (int i = 0; i < n; ++i) {
        while (!st.empty() && a[st.top()] < a[i]) {
            res[st.top()] = a[i];
            st.pop();
        }
        st.push(i);
    }
    return res;
}

---

queue<T>

Header: #include <queue>When to use: FIFO — BFS, level-order traversal, scheduling.

Basic Usage

queue<int> q;
q.push(1);
q.push(2);
q.front();    // 1
q.back();     // 2
q.pop();      // removes front, returns void
q.size();
q.empty();

Complexity

Operation	Time	Notes
push, pop, front, back, size, empty	O(1)

Example Interview Use

BFS on a grid:

queue<pair<int,int>> q;
q.push({sr, sc});
vis[sr][sc] = true;
while (!q.empty()) {
    auto [r, c] = q.front(); q.pop();
    for (auto [dr, dc] : dirs) {
        int nr = r + dr, nc = c + dc;
        if (inb(nr, nc) && !vis[nr][nc]) {
            vis[nr][nc] = true;
            q.push({nr, nc});
        }
    }
}

---

priority_queue<T>

Header: #include <queue>When to use: You want the largest (or smallest) element out first. Top-K problems, Dijkstra, A*, scheduling, merge-k-sorted-lists.

Basic Usage

// Max-heap (default)
priority_queue<int> maxh;
maxh.push(3); maxh.push(1); maxh.push(5);
maxh.top();       // 5
maxh.pop();

// Min-heap
priority_queue<int, vector<int>, greater<int>> minh;
minh.push(3); minh.push(1); minh.push(5);
minh.top();       // 1

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

// Custom comparator via struct
struct Cmp {
    bool operator()(int a, int b) const { return a > b; }  // min-heap
};
priority_queue<int, vector<int>, Cmp> pq2;

Complexity

Operation	Time	Notes
push	O(log n)
pop	O(log n)
top	O(1)
size, empty	O(1)
Construction from range	O(n)	Use range constructor

Common Gotchas

• priority_queue has no begin()/end(). You cannot iterate it. Pop elements out one by one if you need them all.
• Comparator semantics are inverted. less<T> gives a max-heap; greater<T> gives a min-heap. The comparator defines "lower priority".
• No decrease-key operation. For Dijkstra, push the new distance and skip stale entries when you pop them (if (d > dist[u]) continue;).
• No random access to underlying container without a hack (inherit and expose c).

Example Interview Use

Top K largest elements:

vector<int> topK(vector<int>& a, int k) {
    priority_queue<int, vector<int>, greater<int>> minh;   // min-heap of size k
    for (int x : a) {
        minh.push(x);
        if ((int)minh.size() > k) minh.pop();
    }
    vector<int> out;
    while (!minh.empty()) { out.push_back(minh.top()); minh.pop(); }
    return out;                  // ascending; reverse for descending
}

Dijkstra:

vector<long long> dijkstra(int s, vector<vector<pair<int,int>>>& g) {
    int n = g.size();
    vector<long long> dist(n, LLONG_MAX);
    dist[s] = 0;
    priority_queue<pair<long long,int>,
                   vector<pair<long long,int>>,
                   greater<>> pq;
    pq.push({0, s});
    while (!pq.empty()) {
        auto [d, u] = pq.top(); pq.pop();
        if (d > dist[u]) continue;           // stale
        for (auto [v, w] : g[u])
            if (d + w < dist[v]) {
                dist[v] = d + w;
                pq.push({dist[v], v});
            }
    }
    return dist;
}

---

set<T>

Header: #include <set>When to use: You need a sorted collection of unique elements with fast lookup and the ability to query "what's the next element greater than x?" (lower_bound/upper_bound). Backed by a red-black tree.

Basic Usage

set<int> s;
s.insert(3); s.insert(1); s.insert(2); s.insert(1); // duplicate ignored
s.size();         // 3
s.count(2);       // 1 (or 0)
s.find(2);        // iterator or s.end()
s.erase(2);       // by value
s.erase(s.find(2));  // by iterator (O(1) amortized given the iterator)

auto it = s.lower_bound(2);   // first element >= 2
auto it2 = s.upper_bound(2);  // first element > 2

for (int x : s) cout << x << ' ';   // ascending order
for (auto it = s.rbegin(); it != s.rend(); ++it) /* descending */;

Complexity

Operation	Time	Notes
insert	O(log n)
erase(value) / erase(iter)	O(log n) / O(1) amortized
find, count	O(log n)
lower_bound, upper_bound	O(log n)
begin, end, size, empty	O(1)
Full iteration	O(n)

Common Gotchas

• You cannot modify elements in place — mutating them would break the tree order. Erase and re-insert instead.
• Iteration is ordered. That's the whole point of using set instead of unordered_set.
• count returns only 0 or 1 for set. For multiset it can be higher.
• prev(s.upper_bound(x)) gives the largest element <= x (if one exists — check it != s.begin() first).

Example Interview Use

"Given a stream of integers, after each insertion print the closest existing value to the newly inserted element."

set<int> seen;
for (int x : stream) {
    auto it = seen.lower_bound(x);
    int best = INT_MAX;
    if (it != seen.end()) best = min(best, abs(*it - x));
    if (it != seen.begin()) best = min(best, abs(*prev(it) - x));
    cout << best << '\n';
    seen.insert(x);
}

---

multiset<T>

Header: #include <set>When to use: Same as set but allows duplicates. Useful for sliding-window medians, sweep-line problems, and "running top-k" scenarios.

Basic Usage

multiset<int> ms;
ms.insert(5); ms.insert(5); ms.insert(3);
ms.count(5);             // 2
ms.erase(5);             // removes ALL 5s
ms.insert(5); ms.insert(5);
ms.erase(ms.find(5));    // removes ONE 5

Complexity

Operation	Time	Notes
insert	O(log n)
erase(value)	O(log n + k)	k = count of value
erase(iter)	O(1) amortized
find, count	O(log n)	count is O(log n + k) in practice
lower_bound, upper_bound	O(log n)

Common Gotchas

• erase(value) removes every occurrence. Use erase(find(value)) to remove exactly one. This is the most-made mistake with multiset.
• equal_range gives all copies of a value.

Example Interview Use

Sliding window median via two multisets (or one multiset + iterator to the median).

---

map<K, V>

Header: #include <map>When to use: Sorted key-value store with fast lookup. Also the right pick whenever you need "give me the entry with the smallest key >= k" — order-based queries.

Basic Usage

map<string, int> cnt;
cnt["apple"] = 3;                    // insert or assign
cnt["apple"]++;                      // now 4
cnt.at("apple");                     // throws if missing
cnt.insert({"pear", 1});
cnt.emplace("kiwi", 2);              // constructs in-place

cnt.erase("pear");
auto it = cnt.find("apple");
if (it != cnt.end()) cout << it->second;

cnt.count("apple");                  // 0 or 1
cnt.contains("apple");               // C++20

auto lo = cnt.lower_bound("b");      // first key >= "b"
auto hi = cnt.upper_bound("b");      // first key > "b"

for (auto& [k, v] : cnt) cout << k << '=' << v << '\n';  // key-sorted

Complexity

Operation	Time	Notes
insert, emplace	O(log n)
erase(key) / erase(iter)	O(log n) / O(1) amortized
operator[], at, find, count	O(log n)
lower_bound, upper_bound	O(log n)
Iteration	O(n)	Key-sorted order

Common Gotchas

• m[key] inserts a default-constructed value if the key is missing. This is the #1 bug. To merely check existence, use find(), count(), or contains() (C++20).
• at(key) throws std::out_of_range if the key is missing. Use it for read-only lookups where you're sure.
• operator[] is not const. const map<K,V>& m; m[k]; won't compile.
• Iterating invalidates nothing except an iterator to an erased element. You can safely erase(it++) in a loop.

Example Interview Use

Interval scheduling, timeline problems, "find the event just before time t":

map<int, string> events;
events[10] = "A"; events[25] = "B"; events[42] = "C";

int t = 30;
auto it = events.upper_bound(t);
if (it != events.begin()) {
    --it;
    cout << "last event at " << it->first << " was " << it->second;
}

---

multimap<K, V>

Header: #include <map>When to use: Same as map but allows multiple values per key. Relatively rare in interviews — usually map<K, vector<V>> is cleaner.

Basic Usage

multimap<string, int> mm;
mm.insert({"a", 1});
mm.insert({"a", 2});
mm.insert({"b", 3});

auto [lo, hi] = mm.equal_range("a");
for (auto it = lo; it != hi; ++it) cout << it->second << ' '; // 1 2

Complexity

Operation	Time	Notes
insert	O(log n)
erase(key)	O(log n + k)	removes all matches
erase(iter)	O(1) amortized
equal_range	O(log n)

Common Gotchas

• No operator[], since the mapping isn't unique.
• Iterating a specific key requires equal_range.

---

unordered_set<T>

Header: #include <unordered_set>When to use: You need O(1) average membership testing and don't care about order.

Basic Usage

unordered_set<int> u;
u.insert(3); u.insert(1); u.insert(3);  // {1, 3}
u.count(3);        // 1
u.find(3);         // iterator or u.end()
u.erase(3);
u.size();

Complexity

Operation	Time (avg)	Time (worst)	Notes
insert, erase, find, count	O(1)	O(n)	Hash collisions
Iteration	O(n + buckets)

Custom Types

struct Point { int x, y; bool operator==(const Point&) const = default; };

struct PointHash {
    size_t operator()(const Point& p) const noexcept {
        return hash<long long>()( ((long long)p.x << 32) ^ (unsigned)p.y );
    }
};

unordered_set<Point, PointHash> seen;

Common Gotchas

• Worst-case O(n) per operation when the hash collides. In adversarial contexts (Codeforces hack tests), use a randomized hash:

struct FastHash {
    size_t operator()(long long x) const noexcept {
        static const size_t r = chrono::steady_clock::now().time_since_epoch().count();
        x ^= r; x ^= x >> 33; x *= 0xff51afd7ed558ccdULL;
        x ^= x >> 33; x *= 0xc4ceb9fe1a85ec53ULL;
        return x ^ (x >> 33);
    }
};
unordered_set<long long, FastHash> s;

• No lower_bound/upper_bound. Unordered containers do not support ordered queries.

Example Interview Use

"Has this element been seen before?" Two-sum, cycle detection, duplicate checks.

---

unordered_map<K, V>

Header: #include <unordered_map>When to use: Hash map. Default choice for O(1) key-value lookup when you don't need key order.

Basic Usage

unordered_map<string, int> f;
f["a"] = 1;
f.emplace("b", 2);     // avoids constructing the pair twice
++f["c"];              // inserts 0, then increments
f.count("a");          // 0 or 1
f.erase("a");

for (auto& [k, v] : f) cout << k << '=' << v << '\n';  // unspecified order

Complexity

Operation	Time (avg)	Time (worst)	Notes
insert, emplace	O(1)	O(n)
operator[], find, count, erase	O(1)	O(n)
Iteration	O(n + buckets)

Common Gotchas

• unordered_map<pair<int,int>, V> does not compile — there is no default hash for pair. Provide a custom hasher:

struct PairHash {
    size_t operator()(const pair<int,int>& p) const noexcept {
        return hash<long long>()( ((long long)p.first << 32) ^ (unsigned)p.second );
    }
};
unordered_map<pair<int,int>, int, PairHash> m;

• operator[] inserts on a missing key (same as ordered map). Use find or count to check without inserting.
• emplace is faster than insert({k, v}) because it constructs the pair in place.
• Iteration order is unspecified and may differ between runs or after rehashing.
• Huge maps benefit from reserve(expected_size) to avoid rehashing during fills.

Example Interview Use

Two-sum, group-anagrams, character frequency counting, memoization.

// Memoized DP
unordered_map<long long, long long> memo;
function<long long(int,int)> solve = [&](int i, int j) -> long long {
    long long key = (long long)i * 100000 + j;
    auto it = memo.find(key);
    if (it != memo.end()) return it->second;
    // ... compute ans ...
    return memo[key] = ans;
};

---

unordered_multiset<T> and unordered_multimap<K, V>

Header: #include <unordered_set>, #include <unordered_map>When to use: Hash containers that allow duplicates. Uncommon in interviews — you usually want unordered_map<K, int> (a count map) instead of unordered_multiset<K>.

Basic Usage

unordered_multiset<int> ms;
ms.insert(5); ms.insert(5);
ms.count(5);             // 2
ms.erase(5);             // removes ALL 5s
ms.insert(5); ms.insert(5);
ms.erase(ms.find(5));    // removes ONE

unordered_multimap<string,int> mm;
mm.insert({"a", 1});
mm.insert({"a", 2});
auto [lo, hi] = mm.equal_range("a");

Complexity

Operation	Time (avg)	Notes
insert	O(1)
erase(value)	O(k)	k = occurrences
erase(iter)	O(1)
count, find, equal_range	O(1) + O(k)

Interview Tip

Almost always, unordered_map<K, int> used as a frequency table is simpler and faster than unordered_multiset<K>.

---

bitset<N>

Header: #include <bitset>When to use: Fixed-size array of bits, known at compile time. Space-efficient (1 bit per element) and supports fast bulk bitwise ops — often beats vector<bool> by a large margin.

Basic Usage

bitset<16> b;                    // all zeros
bitset<16> c(0b1010);            // from integer
bitset<16> d("1100");            // from string

b.set(3);                        // b[3] = 1
b.reset(3);                      // b[3] = 0
b.flip(3);                       // toggle
b.set();                         // all 1s
b.reset();                       // all 0s
b.flip();                        // invert all

b[0] = 1;
bool x = b.test(0);              // bounds-checked

b.count();                       // number of set bits (popcount)
b.size();                        // N (compile-time)
b.any(); b.none(); b.all();

b.to_string();                   // "0000...0001001"
b.to_ulong();                    // throws if doesn't fit
b.to_ullong();

bitset<16> e = b & c;            // bitwise ops
b |= c; b ^= c; b <<= 2; b >>= 1;

Complexity

Operation	Time	Notes
set, reset, flip, test, []	O(1)	Single bit
set(), reset(), flip() (whole)	O(N / 64)	Packs into words
count	O(N / 64)	Hardware popcount per word
&, `	, ^, <<, >>`	O(N / 64)
to_string	O(N)

Common Gotchas

• Size is compile-time. bitset<N> requires N to be a constant expression. For runtime size, use vector<bool> or boost::dynamic_bitset.
• to_ulong / to_ullong throws if the value doesn't fit.
• Order in to_string: index 0 is the rightmost character (least significant bit on the right, like a number).

Example Interview Use

Sieve of Eratosthenes up to 10^8:

const int N = 100000000;
bitset<N+1> isPrime;
isPrime.set();
isPrime[0] = isPrime[1] = 0;
for (int i = 2; (long long)i*i <= N; ++i)
    if (isPrime[i])
        for (int j = i*i; j <= N; j += i)
            isPrime[j] = 0;

Subset-sum DP with bitmask — shift the "reachable sums" set by w and OR it in; one operation covers all previous sums in parallel:

bitset<10001> dp;
dp[0] = 1;
for (int w : weights) dp |= (dp << w);
// dp[s] == 1 iff sum s is reachable

---

Quick picker

Need	Pick
Dynamic array	vector<T>
Fixed-size array	array<T, N>
Push/pop both ends	deque<T>
O(1) splicing, stable iterators	list<T>
LIFO	stack<T>
FIFO	queue<T>
Top-K / heap	priority_queue<T>
Unique sorted	set<T>
Sorted with dups	multiset<T>
Key-value, sorted, ordered queries	map<K, V>
Key-value, duplicates allowed	multimap<K, V>
Unique, O(1) lookup	unordered_set<T>
Key-value, O(1) lookup	unordered_map<K, V>
Packed bits, compile-time size	bitset<N>