ReviseAlgo Logo

Standard Template Library (STL)

std::vector

Dynamic array container

Interview: Most used container

std::vector

std::vector is the most commonly used STL container — a dynamic array with O(1) amortized push_back. Elements are stored contiguously, giving excellent cache performance. When capacity is exceeded, the vector allocates a new larger block (typically 2x), moves all elements, and frees the old block.

Capacity vs Size

size() is the number of elements currently stored. capacity() is the total allocated space. When size == capacity and you push_back, reallocation occurs. Use reserve(n) to pre-allocate when size is known to avoid repeated reallocations.

Iterator Invalidation

Reallocation invalidates ALL iterators, pointers, and references to elements. Insertions in the middle invalidate iterators from the insertion point onward. Erasing elements invalidates iterators from the erased point onward. Always re-obtain iterators after modifying operations.

Interview Corner

Q: What is the difference between push_back and emplace_back?

A: push_back takes a constructed object and copies/moves it into the vector. emplace_back takes constructor arguments and constructs the object directly in the vector's memory — avoiding the temporary. For objects that are expensive to construct, emplace_back is more efficient. For trivial types, the compiler often optimizes them to the same code.

Q: How do you efficiently remove an element from the middle of a vector?

A: Standard erase() is O(n) — it shifts all subsequent elements. If order doesn't matter, use the "swap-and-pop" idiom: swap the target element with the last element, then pop_back(). This is O(1). For removing elements matching a condition, use the erase-remove idiom: v.erase(std::remove_if(v.begin(), v.end(), pred), v.end()).

Common Pitfalls

  • Storing iterators across push_back calls: Any reallocation from push_back invalidates all iterators. Cache the index, not the iterator.
  • Using operator[] without bounds check: Use at() during development — it throws on out-of-bounds access, making bugs visible immediately.

Best Practices

  • Use reserve() when the approximate final size is known to prevent repeated reallocations.
  • Prefer emplace_back over push_back for in-place construction of complex objects.