C++ STL interview questions, with answers

The questions, with answers

1. 1.What are the main STL containers, and how do you choose one?

   In short: Default to std::vector; use std::deque for fast insertion at both ends, std::list only for frequent splicing, std::map or std::set for sorted keys, and their unordered versions for fast lookup.

   Sequence containers keep elements in the order you put them: vector stores them contiguously, which makes indexing O(1) and iteration cache-friendly, and appending amortised O(1); deque adds cheap insertion at the front; list and forward_list give O(1) insertion anywhere you already hold an iterator, at the cost of a heap allocation per element and poor locality. Associative containers keep elements by key: map and set are balanced trees with sorted iteration and O(log n) operations, while unordered_map and unordered_set are hash tables with average O(1) lookups and no order. Container adaptors, stack, queue and priority_queue, wrap a sequence container to offer a narrower interface. In practice vector wins more often than big-O suggests, because contiguous memory is so fast to walk.

   std::vector<int> v{5, 1, 4};
   std::deque<int> d(v.begin(),
       v.end());
   d.push_front(9);
   std::set<int> s(v.begin(),
       v.end());
   std::cout << d.front() << ' '
       << *s.begin();
   // 9 1

2. 2.What is the difference between a vector's size and its capacity?

   In short: size is the number of elements it holds; capacity is how many fit before it must reallocate, and growing geometrically is what makes push_back amortised O(1).

   A vector allocates more storage than it uses, so that most push_back calls just construct an element in spare space. When size reaches capacity, the vector allocates a larger block, typically 1.5 or 2 times bigger depending on the library, moves or copies the elements across, and frees the old block. Because the capacity grows geometrically, the total copying over n pushes is proportional to n, so each push costs O(1) on average even though an individual push can be O(n). reserve(n) allocates up front when you know the final size, which avoids repeated reallocations and keeps pointers stable while you stay within it, and shrink_to_fit asks, without a guarantee, for spare capacity to be released.

   std::vector<int> v;
   v.reserve(100);
   for (int i = 0; i < 5; i++)
       v.push_back(i);
   std::cout << v.size() << ' '
       << (v.capacity() >= 100);
   // 5 1

3. 3.What is iterator invalidation in the C++ STL?

   In short: An operation that moves or removes elements can leave existing iterators, pointers and references to them dangling; using one afterwards is undefined behaviour, and each container documents which operations invalidate what.

   An iterator is often a pointer in disguise, so when a container moves its elements, iterators into the old storage point at freed memory. For vector, any reallocation, which push_back can trigger, invalidates every iterator, and erase or insert invalidates those at and after the position. For deque, inserting at either end invalidates iterators but not references. For list, map and set, insertion invalidates nothing and erase only affects the erased element. The classic bug is erasing inside a loop that goes on to increment the erased iterator; the fix is to use the iterator that erase returns, as below, or, when removing many elements from a vector, std::erase_if in C++20.

   std::vector<int> v{1, 2, 3, 4};
   auto it = v.begin();
   while (it != v.end()) {
       if (*it % 2 == 0)
           it = v.erase(it);
       else
           ++it;
   }
   std::cout << v.size() << v[1];
   // 23

4. 4.What is the difference between std::map and std::unordered_map?

   In short: map is a sorted balanced tree with O(log n) operations and ordered iteration; unordered_map is a hash table with average O(1) operations, a possible O(n) worst case and no order.

   std::map keeps keys in sorted order, usually as a red-black tree, so lookups, insertions and erasures are O(log n), iteration visits keys in order, and lower_bound and upper_bound answer range questions. Its keys need only a strict weak ordering, operator< by default. std::unordered_map hashes keys into buckets, so operations are O(1) on average but degrade to O(n) when many keys collide, iteration order is unspecified and can change after a rehash, and keys need std::hash and ==, which user-defined types must supply. For counting, caching and lookup by key where order does not matter, unordered_map is usually faster; when you need sorted output, ranges or a predictable worst case, use map.

   std::map<std::string, int> m;
   m["pear"] = 3;
   m["apple"] = 5;
   std::cout << m.begin()->first;
   std::unordered_map<
       std::string, int> u{
       {"kiwi", 2}};
   std::cout << ' '
       << u.count("kiwi");
   // apple 1

5. 5.What is the difference between emplace_back and push_back?

   In short: push_back takes an object and copies or moves it into the container; emplace_back takes constructor arguments and builds the element in place, avoiding the temporary.

   v.push_back({"A1", 3}) first builds a temporary Order from the braces and then moves it into the vector's storage. v.emplace_back("A1", 3) forwards the arguments to Order's constructor, which builds the element directly in the vector's memory, so there is no temporary and no move, as the constructor trace below shows. The difference matters for types that are expensive or impossible to move, and it lets you add elements whose constructor takes several arguments without naming the type. The caveat is that emplace_back uses direct initialisation, so it can call explicit constructors that push_back would reject, which occasionally hides a mistake; for an object you already have, the two are equivalent.

   struct Order {
       Order(std::string, int) {
           std::cout << "build ";
       }
       Order(Order&&) noexcept {
           std::cout << "moved ";
       }
   };
   
   int main() {
       std::vector<Order> v;
       v.reserve(2);
       v.push_back({"A1", 3});
       v.emplace_back("A2", 5);
   }
   // build moved build

6. 6.How do you sort with a custom order in C++, and what must the comparator guarantee?

   In short: Pass a comparator, usually a lambda, returning true when its first argument should come before its second; it must be a strict weak ordering, or std::sort's behaviour is undefined.

   std::sort, std::set and std::map all accept a comparison that answers 'does a go before b?'. The comparator must behave like <: false for equal elements, so never write <=, and consistent, so that if a comes before b and b before c then a comes before c. Violating those rules is undefined behaviour and can crash std::sort. To sort by several keys, compare tuples, std::tie(a.x, a.y) < std::tie(b.x, b.y), which gives a lexicographic order. std::sort is not stable, so equal elements may be reordered; std::stable_sort keeps them in their original order, which matters when sorting by one key after another, as below.

   struct Emp {
       std::string name;
       int dept;
   };
   
   int main() {
       std::vector<Emp> v{
           {"Ravi", 2},
           {"Asha", 1},
           {"Kiran", 2}};
       auto cmp = [](const Emp& a,
           const Emp& b) {
           return a.dept < b.dept;
       };
       std::stable_sort(v.begin(),
           v.end(), cmp);
       for (auto& [n, d] : v)
           std::cout << n << ' ';
   }
   // Asha Ravi Kiran

7. 7.Why is std::vector<bool> considered a problem?

   In short: It is a specialisation that packs bools into bits, so operator[] returns a proxy object instead of a bool&, and it does not behave like a normal container of bool.

   To save space, the standard specialises vector<bool> to store one bit per element. There is no way to form a reference to a single bit, so v[i] returns a proxy object of type std::vector<bool>::reference that converts to bool and can be assigned to. That breaks generic code: auto x = v[0]; gives a proxy that still refers into the vector, as below, bool& r = v[0]; does not compile, and you cannot take a bool* to an element or pass the data to an API that expects a contiguous array of bool. Its operations can also be slower because of the bit manipulation. When you need a real container of bools, use std::vector<char>, std::deque<bool>, or std::bitset when the size is fixed.

   std::vector<bool> v{true};
   auto x = v[0];
   v[0] = false;
   std::cout << bool(x);
   // 0

How the diagnostic asks it

One question from the C++ bank, exactly as a sitting would show it. The bank has 4 on stl containers & algorithms and 30 across C++.

std::map<std::string, int> m;
if (m["a"] == 0)
    std::cout << "zero ";
std::cout << m.size();