Autocoder

C++ STL Interview Questions

Last updated 2026-11-19

The Standard Template Library is what most C++ coding-round solutions are built from, so interviewers use it to test whether you understand what each container really costs. The questions below focus on complexity guarantees, iterator invalidation, ordering rules and the algorithms you reach for under time pressure.

A good STL answer names the underlying data structure, states the complexity, and mentions the one gotcha. For example, std::map is a balanced tree with O(log n) operations in key order, and indexing it with operator[] inserts a default element when the key is missing. Practise saying all three. For problem solving with these containers, see how to crack a DSA coding round.

CoversContainers, iterators, algorithms, functors
FocusComplexity and invalidation
StandardC++17 and C++20

Quick reference: container costs

Traps interviewers like

Erasing inside a loop, relying on unordered_map order, calling operator[] on a const map, and sorting with a comparator that is not a strict weak ordering are the four traps behind most STL bug questions. A comparator using <= can crash std::sort, not just misorder results.

C++ STL Interview Questions: questions with worked answers

  1. 1

    What are the three main parts of the STL?

    easy

    Containers (vector, list, map, set, unordered_map, stack, queue and so on) store data. Algorithms (sort, find, lower_bound, accumulate, next_permutation) operate on ranges. Iterators are the glue: they give algorithms a uniform way to traverse any container without knowing its type. Function objects and lambdas customise algorithm behaviour. C++20 ranges add composable views on top of the same idea.

  2. 2

    How does std::vector grow, and what is its push_back complexity?

    easy

    A vector keeps a contiguous buffer with a size and a capacity. When size reaches capacity, push_back allocates a larger buffer (commonly double or 1.5 times), moves or copies every element and frees the old one. That makes one push_back O(n) but the amortised cost O(1). Because storage moves, all iterators, pointers and references into the vector are invalidated on reallocation. reserve(n) allocates up front to avoid it, and shrink_to_fit() only requests a reduction.

  3. 3

    What is the difference between size and capacity, and between clear and shrink_to_fit?

    medium

    size is the number of elements; capacity is how many fit before reallocation. clear() destroys all elements and sets size to 0 but keeps the capacity, so memory is not returned. shrink_to_fit() is a non-binding request to reduce capacity to size. The classic idiom to actually release memory is swapping with an empty vector: std::vector<int>().swap(v). resize(n) changes size, value-initialising new elements, while reserve(n) changes capacity only.

  4. 4

    map versus unordered_map: how do you choose?

    medium

    std::map is a balanced binary search tree: O(log n) operations, iteration in sorted key order, supports lower_bound and range queries, and iterators stay valid across inserts. std::unordered_map is a hash table: O(1) average but O(n) worst case with collisions, no order, and rehashing invalidates iterators (references to elements stay valid). Choose map when you need ordering or range queries or worst-case guarantees, unordered_map for fast lookup by key. Keys must be hashable and equality-comparable for the latter, and a custom type needs a std::hash specialisation.

  5. 5

    What does map::operator[] do when the key is absent, and how do you avoid the side effect?

    medium

    It inserts the key with a value-initialised mapped value (0 for int) and returns a reference to it, so merely reading m[k] grows the map. It also cannot be used on a const map. Use find() or count() (or contains() in C++20) to test, at() to throw std::out_of_range on a missing key, and try_emplace or insert_or_assign (C++17) for explicit insertion semantics.

    cpp
    std::map<std::string,int> m;
    if (m["a"] == 0) {}             // inserts "a" -> 0
    std::cout << m.size();          // 1
    auto it = m.find("b");          // no insertion
    if (it == m.end()) std::cout << "absent";
  6. 6

    How do you erase elements from a vector while iterating? Show the safe patterns.

    medium

    erase invalidates the erased iterator and all after it for a vector, so "for (auto it = v.begin(); it != v.end(); ++it) if (...) v.erase(it);" is a bug. Use the return value of erase, which is the next valid iterator, or the erase-remove idiom, which is O(n) overall rather than O(n squared). C++20 provides std::erase_if(v, pred) that does it in one call.

    cpp
    // erase-remove
    v.erase(std::remove_if(v.begin(), v.end(), [](int x){ return x % 2 == 0; }), v.end());
    // C++20
    std::erase_if(v, [](int x){ return x % 2 == 0; });
    // manual loop
    for (auto it = v.begin(); it != v.end();) it = (*it < 0) ? v.erase(it) : it + 1;
  7. 7

    Which operations invalidate iterators in vector, list, map and unordered_map?

    medium

    vector: any reallocation invalidates everything; insert or erase invalidates from the change point onward. deque: insert or erase in the middle invalidates all; push at the ends invalidates iterators but not references. list and forward_list: only the erased element is invalidated. map and set: only erased elements. unordered_map: a rehash invalidates iterators but not references or pointers to elements; erase invalidates just that element. Interviewers usually probe vector and unordered_map.

  8. 8

    How does priority_queue work, and how do you make a min-heap or a custom ordering?

    medium

    std::priority_queue is a container adaptor over a vector using push_heap and pop_heap, so push and pop are O(log n) and top is O(1). The default comparator is std::less, which yields a max-heap. For a min-heap pass std::greater and the underlying container. For a custom type supply a comparator where "less" means lower priority. It has no iteration or decrease-key, so for Dijkstra you push duplicates and skip stale entries.

    cpp
    std::priority_queue<int, std::vector<int>, std::greater<int>> minHeap;
    minHeap.push(5); minHeap.push(1); minHeap.push(3);
    // top() == 1
    using P = std::pair<int,int>;           // (dist, node)
    std::priority_queue<P, std::vector<P>, std::greater<P>> pq;
  9. 9

    What is the difference between set, multiset, and unordered_set, and how do you count duplicates?

    medium

    set stores unique keys in sorted order (O(log n)). multiset allows duplicates, also sorted; erase(key) removes all copies, while erase(iterator) removes one. unordered_set stores unique keys by hash in O(1) average. To count duplicates in a stream use unordered_map<T,int> with ++m[x], or multiset::count(x) which is O(log n + k) for k copies.

  10. 10

    Explain lower_bound and upper_bound and give the complexity.

    medium

    Both require a sorted range. lower_bound returns the first element not less than the value (>= x); upper_bound returns the first element greater than it (> x). Their difference is the count of equal elements, and equal_range returns both. They are O(log n) comparisons on random-access iterators (O(n) steps otherwise). On std::set and std::map, call the member functions rather than the std:: algorithm: the member version uses the tree and is logarithmic, while the free function walks bidirectional iterators linearly.

    cpp
    std::vector<int> v = {1, 2, 2, 2, 5, 9};
    auto lo = std::lower_bound(v.begin(), v.end(), 2); // index 1
    auto hi = std::upper_bound(v.begin(), v.end(), 2); // index 4
    int count = hi - lo;                                // 3
  11. 11

    Why can a sort comparator using <= crash std::sort?

    hard

    std::sort requires a strict weak ordering: irreflexive (comp(a,a) is false), asymmetric and transitive. A comparator using <= returns true for equal elements, violating irreflexivity. The introsort partition loops can then run past the range ends, causing out-of-bounds access, an infinite loop or a segmentation fault, typically on inputs with many equal values. Use < and break ties explicitly when sorting by multiple keys, or use std::tie for lexicographic comparison.

    cpp
    std::sort(v.begin(), v.end(), [](const P& a, const P& b){
        return std::tie(a.age, a.name) < std::tie(b.age, b.name);
    });
  12. 12

    What is the difference between std::sort and std::stable_sort, and partial_sort or nth_element?

    medium

    std::sort is introsort, O(n log n) worst case, not stable, so equal elements may be reordered. std::stable_sort preserves the relative order of equal elements, O(n log n) with extra memory or O(n log^2 n) without. partial_sort(first, mid, last) puts the smallest k elements sorted in front in O(n log k). nth_element places the k-th element where it would be in sorted order, with smaller ones before and larger after, in O(n) average, which is the standard way to get a median or top-k without a full sort.

  13. 13

    How do you remove duplicates from a vector?

    medium

    Sort, then use std::unique, which moves duplicates to the end and returns the new logical end, and erase the tail. This is O(n log n) and changes order. To preserve first-occurrence order, track seen values in an unordered_set while copying, O(n) average with extra space. unique only removes consecutive duplicates, so forgetting to sort first is the common bug.

    cpp
    std::sort(v.begin(), v.end());
    v.erase(std::unique(v.begin(), v.end()), v.end());
  14. 14

    When would you use deque, list or array instead of vector?

    easy

    Use deque when you need O(1) push and pop at both ends, as in a sliding-window or BFS queue. Use list when you need stable iterators and cheap splicing or insertion at known positions, which is rare because cache locality makes vector faster for most sizes. Use std::array for fixed-size, stack-allocated, compile-time-sized data, and std::vector otherwise. vector<bool> is a packed specialisation whose operator[] returns a proxy, so avoid it when you need real references.

  15. 15

    What does emplace do compared with insert on a map?

    medium

    insert takes a ready value_type (pair<const K,V>) and emplace constructs it in place from arguments. Both do nothing if the key already exists. emplace may construct the node first and then discard it on a duplicate. try_emplace (C++17) only constructs the value if the key is absent and never moves from your arguments on failure, and insert_or_assign overwrites an existing value. For counting, ++m[k] is simplest.

  16. 16

    How do you iterate a map and modify values? What do structured bindings give you?

    medium

    Elements are pair<const Key, Value>: the key is const and the value can be changed through a reference. Iterate with "for (auto& [k, v] : m)" (C++17 structured bindings) so you modify in place rather than copying. Writing "for (auto p : m)" copies each pair and changes are lost, a frequent bug. Use const auto& when you only read.

    cpp
    std::map<std::string,int> m{{"a",1},{"b",2}};
    for (auto& [k, v] : m) v *= 10;   // modifies
    for (auto p : m) p.second = 0;    // modifies a copy only

Frequently asked questions

Is STL allowed in coding rounds?

Most online judges and company tests allow the C++ standard library. A few interviews ask you to implement a structure yourself, so know both.

Which STL topics matter most for placements?

vector, map, unordered_map, set, priority_queue, sort with a comparator and lower_bound cover the vast majority of problems.

Why is unordered_map sometimes slower than map?

Poor hashing or adversarial keys cause collisions and O(n) worst case, and rehashing costs time. For integers, a custom hash helps on judges that attack the default.

Where can I practise problems that use these containers?

Start from hashing and map patterns and heap questions, then solve a few timed problems.

Related guides

More in Programming Language Interview Questions by Language

See all in this section