C++ STL for Coding Interviews: The Complete Cheat Sheet

C++ is the most popular language for competitive programming and a common choice in Indian DSA rounds, mainly because the STL gives you balanced trees, heaps and hash tables in one line. But the STL also has sharp edges: a member function that is O(log n) next to a free function that is O(n), an operator[] that silently inserts, a heap whose comparator reads backwards. This cheat sheet covers what you need for interviews and nothing you do not, with every snippet compiled and run under GCC 12 with -std=c++17.

If you have not yet picked a language, read Java vs Python vs C++ for DSA first. If you use Java, the companion page is the Java Collections cheat sheet.

Setup and Fast I/O

#include <bits/stdc++.h>     // GCC only: pulls in the whole standard library
using namespace std;

int main() {
    ios::sync_with_stdio(false);   // decouple from C stdio
    cin.tie(nullptr);              // don't flush cout before every cin
    // ...
}

In interviews on a shared editor, bits/stdc++.h and using namespace std are fine; say once that production code would include specific headers. For online assessments with large input, the two I/O lines matter. Also prefer '\n' over endl: endl flushes the stream every time and can turn 10⁶ lines of output into a TLE.

vector: The Default Container

vector<int> a;                          // empty
vector<int> b(n, -1);                   // n copies of -1
vector<vector<int>> grid(rows, vector<int>(cols, 0));   // 2D grid
vector<int> c = {5, 3, 8, 1, 3};

a.push_back(4);        // amortised O(1)
a.emplace_back(4);     // constructs in place; same for ints, nicer for pairs/structs
a.pop_back();          // O(1), no return value
a.back(); a.front();   // undefined behaviour if empty
a.reserve(1000000);    // avoid repeated reallocations when size is known
a.insert(a.begin() + i, x);   // O(n): shifts elements
a.erase(a.begin() + i);       // O(n)

sort(c.begin(), c.end());                         // ascending
sort(c.rbegin(), c.rend());                       // descending
sort(c.begin(), c.end(), greater<int>());         // also descending
c.erase(unique(c.begin(), c.end()), c.end());     // dedupe (after sorting)

// remove all even numbers: erase-remove idiom, O(n)
c.erase(remove_if(c.begin(), c.end(), [](int x) { return x % 2 == 0; }), c.end());

Key facts: random access is O(1); insert and erase anywhere except the end are O(n). unique only removes adjacent duplicates and does not shrink the vector by itself, hence the erase. Any reallocation (from push_back beyond capacity) invalidates all iterators, pointers and references into the vector, a classic source of heisenbugs when you hold &v[0] and keep pushing.

Pass vectors to helpers by reference (const vector<int>& or vector<int>&). Passing by value copies the whole thing on every call, which turns an O(n) recursion into O(n²) memory traffic and is a frequent TLE cause in DFS.

string Operations You Will Use

string s = "interview";
s.size();                 // 9
s.substr(2, 4);           // "terv": (pos, LENGTH), not (start, end); O(length)
s.find("view");           // 5; returns string::npos if absent
s.push_back('!');         // amortised O(1)
s += "abc";               // appends in place
s = s + 'c';              // builds a NEW string: O(n) each time, avoid in loops
reverse(s.begin(), s.end());
stoi("123"); stoll("9000000000"); to_string(45);
string t(5, 'x');         // "xxxxx"
// character tricks
int idx = ch - 'a';       // 0..25 for lowercase
isdigit(ch); isalpha(ch); tolower(ch); toupper(ch);

The substr(pos, len) signature trips up people coming from Java and Python, where the second argument is an end index. And substr copies, so calling it inside a loop over all positions is O(n²) even if the loop looks linear. For read-only slices in C++17, string_view avoids the copy.

pair, tuple and Structured Bindings

pair<int, string> p = {30, "Asha"};
p.first; p.second;
// pairs compare lexicographically: first, then second
vector<pair<int, string>> people = {{30, "Asha"}, {25, "Ravi"}, {30, "Bina"}};
sort(people.begin(), people.end());   // (25,Ravi) (30,Asha) (30,Bina)

for (auto& [age, name] : people)       // C++17 structured bindings
    cout << name << ' ' << age << '\n';

tuple<int, int, int> t = {1, 2, 3};
auto [x, y, z] = t;

Lexicographic comparison of pairs is why you can push {distance, node} into a heap without writing a comparator. Structured bindings make graph code dramatically more readable: for (auto [v, w] : adj[u]) beats adj[u][i].first.

<algorithm> and <numeric> Essentials

vector<int> v = {1, 3, 5, 8};
auto it = lower_bound(v.begin(), v.end(), 4);   // points to 5
int pos = it - v.begin();                        // 2
// count of elements in [lo, hi] in a sorted vector:
int cnt = upper_bound(v.begin(), v.end(), hi) - lower_bound(v.begin(), v.end(), lo);

vector<int> perm = {1, 2, 3};
do { /* use perm */ } while (next_permutation(perm.begin(), perm.end()));  // 6 times

vector<int> pre(5);
iota(pre.begin(), pre.end(), 1);                    // 1 2 3 4 5
partial_sum(pre.begin(), pre.end(), pre.begin());   // 1 3 6 10 15

next_permutation only enumerates all permutations if you start from the sorted order. nth_element is a quickselect and the cleanest O(n) average answer to "Kth largest element" if the interviewer allows library calls; be ready to implement quickselect or a heap yourself.

map vs unordered_map (and Their Traps)

unordered_map<string, int> freq;
for (const string& w : words) freq[w]++;     // [] default-inits to 0, so ++ works

if (freq.count("z")) { }                      // membership: does NOT insert
auto it = freq.find("z");                     // one lookup, reuse the iterator
if (it != freq.end()) it->second++;

int z = freq["z"];                            // INSERTS "z" -> 0 as a side effect!

// erase while iterating (works for map and unordered_map)
for (auto it2 = m.begin(); it2 != m.end(); ) {
    if (shouldRemove(it2->first)) it2 = m.erase(it2);
    else ++it2;
}

Hashing a pair or a grid cell

unordered_map<pair<int,int>, int> does not compile because there is no standard hash for pair. Either use map, encode the pair as one integer (r * cols + c, or ((long long)r << 32) | c), or supply a hash:

struct PairHash {
    size_t operator()(const pair<int,int>& p) const {
        return hash<long long>()(((long long)p.first << 32) ^ (unsigned int)p.second);
    }
};
unordered_map<pair<int,int>, int, PairHash> cell;
cell[{1, 2}] = 5;

Anti-hash tests on competitive platforms

GCC's integer hash is the identity function, so on Codeforces-style judges people craft inputs that put every key in the same bucket, making each operation O(n). Interviews do not do this, but some online assessments reuse contest problems. The standard fix is a randomised splitmix64 hash:

struct SplitMix {
    static uint64_t splitmix64(uint64_t x) {
        x += 0x9e3779b97f4a7c15ULL;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9ULL;
        x = (x ^ (x >> 27)) * 0x94d049bb133111ebULL;
        return x ^ (x >> 31);
    }
    size_t operator()(uint64_t x) const {
        static const uint64_t SEED = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + SEED);
    }
};
unordered_map<long long, int, SplitMix> safe;

The hashing problems guide covers which interview problems these maps solve.

set and multiset: Ordered Sets With Superpowers

set<int> st = {10, 20, 30};
st.insert(15); st.erase(20);              // O(log n)
auto it = st.lower_bound(15);             // MEMBER function: O(log n), points to 15
auto gt = st.upper_bound(30);             // == st.end()
int smallest = *st.begin();
int largest  = *st.rbegin();              // or *prev(st.end())
// predecessor of x (largest element < x), if any:
auto p = st.lower_bound(x);
if (p != st.begin()) { --p; /* *p is the predecessor */ }

multiset<int> ms = {1, 2, 2, 2, 3};
ms.erase(ms.find(2));     // removes ONE 2  -> count(2) == 2
ms.erase(2);              // removes ALL 2s -> count(2) == 0

Ordered sets solve a whole class of problems that otherwise need a balanced BST: "closest value to x seen so far" (Contains Duplicate III), the calendar booking problems (My Calendar I and II), and running medians with two multisets. They are also the cleanest way to implement Dijkstra with decrease-key: erase the old {dist, node} and insert the new one.

priority_queue: Heaps, Min-Heaps and Custom Order

priority_queue<int> maxh;                                  // max-heap (default)
priority_queue<int, vector<int>, greater<int>> minh;     // min-heap
maxh.push(4); maxh.top(); maxh.pop();                      // O(log n), O(1), O(log n)

// heap of pairs ordered by .second ascending (min on top), via lambda
auto cmp = [](const pair<int,int>& a, const pair<int,int>& b) {
    return a.second > b.second;
};
priority_queue<pair<int,int>, vector<pair<int,int>>, decltype(cmp)> pq(cmp);

// heap of structs via a comparator struct
struct Task { int priority; string name; };
struct TaskCmp {
    bool operator()(const Task& a, const Task& b) const {
        if (a.priority != b.priority) return a.priority < b.priority;  // higher priority on top
        return a.name > b.name;                                       // then smaller name on top
    }
};
priority_queue<Task, vector<Task>, TaskCmp> tasks;

The reversal rule: the heap's top is the element that is "greatest" under your comparator. So a < b means max-heap and a > b means min-heap. With sort, the same a < b sorts ascending. If you remember one sentence: priority_queue's comparator answers "should a sit below b?"

There is no decrease-key, no iteration and no erase of arbitrary elements. For Dijkstra, push duplicates and skip stale entries ("lazy deletion"):

vector<long long> dijkstra(int n, const vector<vector<pair<int,int>>>& adj, int src) {
    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;            // stale entry
        for (auto [v, w] : adj[u]) {
            if (dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                pq.push({dist[v], v});
            }
        }
    }
    return dist;
}

Total cost is O((V + E) log E). More heap patterns (top-K, merge K lists, two-heap median) are in the heap interview problems guide, and the shortest-path variants in Dijkstra, Bellman-Ford and Floyd-Warshall.

stack, queue and deque

stack<int> s;  s.push(1); s.top(); s.pop(); s.empty();
queue<int> q;  q.push(1); q.front(); q.back(); q.pop();
deque<int> dq; dq.push_back(1); dq.push_front(0); dq.pop_back(); dq.pop_front();
dq.front(); dq.back(); dq[i];      // O(1) random access too

pop() returns void on all three: read top() or front() first. Calling top() or pop() on an empty stack is undefined behaviour, not an exception, so guard with empty(). deque is the right structure for the monotonic queue in Sliding Window Maximum and for 0-1 BFS. A vector used as a stack (push_back/back/pop_back) is equally fine and lets you iterate, which helps in problems like Asteroid Collision.

Custom Comparators: Rules That Prevent Crashes

Sorting by a custom rule is everywhere in interviews: intervals by start, people by height descending then k ascending, strings by custom concatenation order in Largest Number.

// sort by age descending, then name ascending
sort(people.begin(), people.end(), [](const auto& a, const auto& b) {
    if (a.first != b.first) return a.first > b.first;
    return a.second < b.second;
});

// struct with operator< works with sort, set, map and priority_queue
struct Interval {
    int start, end;
    bool operator<(const Interval& o) const {
        return start != o.start ? start < o.start : end < o.end;
    }
};

• Strict weak ordering: comp(a, a) must be false. Writing a.x <= b.x violates this and is undefined behaviour; with many equal keys, GCC's sort can read past the array and crash.
• Take parameters by const reference to avoid copying strings or vectors on every comparison.
• In a set or map, the comparator defines equality. If your comparator only compares start, two intervals with the same start are "equal" and the second insert is silently dropped. Compare every field that distinguishes elements.

Bits and Numeric Helpers

__builtin_popcount(13);       // 3   (unsigned int)
__builtin_popcountll(x);      // for long long; popcount on a long long truncates
__builtin_ctz(x);             // trailing zeros; undefined for x == 0
__builtin_clz(x);             // leading zeros; undefined for x == 0
gcd(12, 18); lcm(4, 6);       // C++17 <numeric>: 6 and 12
bitset<8> b(5);               // 00000101, b.count() == 2, b[0] == 1
LLONG_MAX; INT_MAX; INT_MIN;  // <climits>

The __builtin functions are GCC/Clang extensions, which is what almost every judge uses. C++20 adds portable std::popcount in <bit>. See bit manipulation tricks for how these are used.

STL Complexity Table

list::splice plus an unordered_map of iterators is the textbook C++ implementation of LRU cache; the LRU cache walkthrough shows it in full.

STL Pitfalls That Fail Hidden Test Cases

1. Unsigned size underflow. v.size() is unsigned. If v is empty, v.size() - 1 is a huge number and for (int i = 0; i < v.size() - 1; i++) runs off the end. Write i + 1 < (int)v.size().
2. accumulate with int init. accumulate(v.begin(), v.end(), 0) sums in int even for a vector<long long>. Use 0LL.
3. int overflow in products. int a = 1e5, b = 1e5; long long c = a * b; overflows before the assignment. Write 1LL * a * b.
4. map[] inserting during lookup. Grows the map, can change iteration, and breaks size() logic.
5. multiset erase by value. Removes every copy.
6. Free lower_bound on set. O(n).
7. Non-strict comparator. Undefined behaviour in sort; dropped elements in set.
8. Iterator invalidation. Erasing from a vector or pushing beyond capacity invalidates iterators; erasing from a map invalidates only the erased iterator, so use the return value of erase.
9. Vectors passed by value in recursive DFS or backtracking.
10. endl in hot loops. Flushes every line.
11. abs on long long. Use llabs or std::abs with the right overload; C abs(int) truncates.
12. Recursion depth. DFS on a path of 10⁵+ nodes may overflow the stack on some judges; convert to an explicit stack if depth can be that large.

What Interviewers Probe About the STL

Interviewers rarely test STL trivia directly, but they notice fluency and they ask about cost. Expect questions like:

• "What is the complexity of that line?" after you call s.find, substr, erase or insert in a loop. Know which ones are O(n).
• "Why map and not unordered_map?" Have a reason: ordering, range queries, or worst-case guarantees.
• "How is priority_queue implemented?" A binary heap stored in a vector, with push_heap/pop_heap. Building from n elements is O(n).
• "Implement it without the library." Be ready to write a heap, a hash-free solution, or quickselect instead of nth_element, especially for problems like Kth Largest.
• "What happens on equal keys?" In comparators, sets and multisets.

For the language questions asked outside DSA rounds (virtual functions, RAII, smart pointers, move semantics), see the C++ interview questions guide.

Frequently Asked Questions

Pranjal Jain

Ex-Microsoft SDE · IIT Kanpur · Founder of Prepflix. Helps engineers crack startup and product company interviews across India.