C++ STL Interview Questions

The generic part of the standard library: containers (vector, map, unordered_map...), container adaptors (stack, queue, priority_queue), iterators, algorithms (sort, find, accumulate) and function objects such as lambdas. Algorithms work on iterator ranges, not on containers.

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

int main() {
    vector<int> v = {5, 2, 9, 1};
    sort(v.begin(), v.end());
    auto it = find(v.begin(), v.end(), 9);
    cout << "sorted: ";
    for (int x : v) cout << x << " ";
    cout << "| 9 at index " << (it - v.begin()) << "\n";
}

This prints sorted: 1 2 5 9 | 9 at index 3.

All three add at the end in amortized O(1). Default to vector: one contiguous block beats list even for many middle insertions, because walking a list costs a cache miss per node. Use deque for both ends and list for stable iterators.

std::map keeps sorted keys in a balanced binary search tree (red-black in the major libraries) with O(log n) operations. std::unordered_map is a hash table with no order, O(1) on average and O(n) in the worst case.

Use unordered_map for plain lookups and map for sorted output or lower_bound queries. The hash table visualization shows buckets and collisions.

It prints apple=6 fig=1 pear=3. std::map keeps its keys sorted, so iteration is alphabetical whatever the insertion order, and m["apple"] += 1 adds to the existing value. With std::unordered_map the order would be unspecified.

It prints zero 1. operator[] inserts a value-initialized element when the key is missing, so reading m["missing"] adds the key with value 0.

To look up without inserting, use m.find(key), m.count(key), m.at(key) (throws if missing) or C++20's m.contains(key).

size() is how many elements the vector holds; capacity() is how many fit before it must reallocate. When full, it allocates a block a constant factor larger and moves the elements, so push_back is amortized O(1).

#include <iostream>
#include <vector>

int main() {
    std::vector<int> v;
    size_t last = 0;
    for (int i = 0; i < 20; ++i) {
        v.push_back(i);
        if (v.capacity() != last) {
            last = v.capacity();
            std::cout << last << " ";
        }
    }
    std::cout << "\n";
}

With GCC's libstdc++ this prints 1 2 4 8 16 32; MSVC grows by 1.5 times. Reallocation invalidates every pointer and iterator. See the vector docs.

When a container change leaves an iterator pointing at freed or moved memory; using it is undefined behavior. A vector reallocation invalidates all iterators; in list, map and set only the erased element's. To erase while iterating, continue from the iterator erase returns.

#include <iostream>
#include <vector>
using namespace std;

int main() {
    vector<int> v = {1, 2, 3, 4, 5, 6};
    for (auto it = v.begin(); it != v.end(); ) {
        if (*it % 2 == 0) it = v.erase(it);
        else ++it;
    }
    for (int x : v) cout << x << " ";
    cout << "\n";
}

This prints 1 3 5. More in the iterators docs.

It prints 6 3. std::remove only sees iterators, so it cannot change the size: it shifts the kept elements (1, 3, 4) to the front and returns the new logical end. erase then cuts the leftover tail.

Together that is the erase-remove idiom, v.erase(remove(v.begin(), v.end(), 2), v.end());. C++20's std::erase(v, 2) and std::erase_if do both steps.

It prints 7 1. std::priority_queue is a max-heap by default. For a min-heap pass std::greater<int> as the third template argument, which means also naming the container, vector<int>, as the second.

push and pop are O(log n) and top is O(1). The heap visualization shows a min-heap sifting each value up.

Introsort in GCC's libstdc++ and MSVC (quicksort falling back to heapsort, insertion sort for small ranges), with O(n log n) guaranteed since C++11. It is not stable; use std::stable_sort for that.

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

int main() {
    vector<pair<int, int>> intervals = {{5, 7}, {1, 3}, {2, 4}, {1, 2}};
    sort(intervals.begin(), intervals.end(), [](const auto& a, const auto& b) {
        if (a.first != b.first) return a.first < b.first;
        return a.second < b.second;
    });
    for (auto& [s, e] : intervals) cout << "[" << s << "," << e << "] ";
    cout << "\n";
}

This prints [1,2] [1,3] [2,4] [5,7]. The comparator must be a strict weak ordering, so <= is undefined behavior. The quicksort visualization shows the partition step.

push_back copies or moves an existing object into the vector. emplace_back takes constructor arguments and builds the element in place.

#include <iostream>
#include <vector>
using namespace std;

struct P {
    P(int, int) { cout << "ctor "; }
    P(const P&) { cout << "copy "; }
    P(P&&) noexcept { cout << "move "; }
};

int main() {
    vector<P> v;
    v.reserve(2);
    v.push_back(P(1, 2));
    v.emplace_back(3, 4);
    cout << "\n";
}

This prints ctor move ctor . The trap: emplace_back calls explicit constructors, so v.emplace_back(10) on a vector<vector<int>> adds a vector of ten zeros where push_back(10) would not compile.

It prints 3 1 3. A std::set keeps one copy of each value and stays sorted, so it holds {1, 2, 3}, *s.begin() is 1 and *s.rbegin() is 3.

When order does not matter, std::unordered_set gives O(1) average lookups instead of O(log n).

std::stack (last in, first out) and std::queue (first in, first out) are container adaptors: they wrap another container, std::deque by default, and expose only push, pop, top or front, empty and size. They cannot be iterated, and pop() returns void, so read top() first.

#include <iostream>
#include <stack>
#include <string>
using namespace std;

bool balanced(const string& s) {
    stack<char> st;
    for (char c : s) {
        if (c == '(' || c == '[' || c == '{') { st.push(c); continue; }
        if (st.empty()) return false;
        char open = st.top();
        st.pop();
        if ((c == ')' && open != '(') || (c == ']' && open != '[') || (c == '}' && open != '{'))
            return false;
    }
    return st.empty();
}

int main() {
    cout << balanced("{[()]}") << " " << balanced("([)]") << "\n";
}

This prints 1 0.