What is a Vector in C++?
Understand std::vector in C++: contiguous storage, amortized O(1) push_back, capacity vs size, and how reallocation invalidates iterators.
Expected Interview Answer
A `std::vector` is a dynamic, contiguous array container from the STL that can grow and shrink at runtime while providing fast, cache-friendly random access to its elements.
Internally, a vector maintains a contiguous heap-allocated buffer along with a size and capacity; when `push_back` exceeds current capacity, it allocates a larger buffer (typically doubling), moves or copies existing elements over, and frees the old buffer, which is why capacity growth is amortized O(1) even though an individual reallocation is O(n). Random access via `operator[]` is O(1) because elements sit contiguously in memory, but inserting or erasing in the middle is O(n) because subsequent elements must shift. Because it manages its own heap memory and frees it in its destructor, `std::vector` is itself a RAII wrapper, so you rarely need raw `new`/`delete` for dynamic arrays anymore. Reallocation invalidates existing iterators, pointers, and references into the vector, a common source of subtle bugs.
- Contiguous memory gives fast, cache-friendly iteration
- O(1) random access via index
- Amortized O(1) push_back due to capacity doubling
- RAII-managed, no manual memory cleanup required
- Drop-in replacement for raw dynamic arrays with STL algorithm support
AI Mentor Explanation
A vector is like a team bus with numbered seats in a single row, letting the coach reach any player instantly by seat number rather than walking down the aisle. When the squad grows beyond the bus's current seats, the team doesn't add one seat at a time — they swap to a bigger bus and reseat everyone at once, which is costly that one time but rare overall.
Step-by-Step Explanation
Step 1
Declare and populate
Create with `std::vector<T> v;` and add elements with `push_back` or `emplace_back`.
Step 2
Contiguous storage
Elements live in one contiguous heap buffer, giving O(1) indexed access via `operator[]`.
Step 3
Capacity vs size
`size()` is the element count; `capacity()` is the allocated buffer's room, which can exceed size.
Step 4
Reallocate on growth
When `push_back` exceeds capacity, the vector allocates a larger buffer (typically 2x), moves elements over, and frees the old buffer.
Step 5
Watch iterator invalidation
Reallocation, insertion, or erasure can invalidate existing iterators, pointers, and references into the vector.
Step 6
Use `reserve` to optimize
Call `reserve(n)` up front when the final size is known to avoid repeated reallocations.
What Interviewer Expects
- Explains vector as a dynamic, contiguous array with automatic resizing
- Understands the difference between `size()` and `capacity()`
- Knows push_back is amortized O(1), insert/erase in the middle is O(n)
- Mentions iterator/reference invalidation on reallocation
- Knows `reserve()` can avoid unnecessary reallocations
Common Mistakes
- Believing push_back is always O(1) without understanding amortization
- Using a stale iterator or pointer after a reallocation
- Choosing `vector` for frequent middle-insertions instead of `list` or `deque`
- Confusing `size()` with `capacity()`
- Not calling `reserve()` when the final size is known upfront
Best Answer (HR Friendly)
“A vector is a flexible, resizable list in C++ that stores items in order and lets you access any item instantly by position, similar to a row of labeled boxes that can expand when it runs out of room. It's one of the most commonly used tools for storing collections of data.”
Code Example
#include <vector>
#include <iostream>
int main() {
std::vector<int> v;
v.reserve(4); // pre-allocate to avoid extra reallocations
for (int i = 1; i <= 4; ++i) {
v.push_back(i * 10);
}
std::cout << "Size: " << v.size() << ", Capacity: " << v.capacity() << "\n";
std::cout << "Element at index 2: " << v[2] << "\n"; // 30
v.push_back(50); // exceeds reserved capacity -> may reallocate
std::cout << "New size: " << v.size() << "\n"; // 5
return 0;
}Follow-up Questions
- What is the difference between `size()` and `capacity()` in a vector?
- Why is `push_back` described as amortized O(1)?
- When does a vector invalidate its iterators or references?
- How does `std::vector` compare to `std::list` for insertions in the middle?
- What does `reserve()` do and when should you call it?
MCQ Practice
1. What is the time complexity of accessing an element by index in `std::vector`?
Because vector elements are stored contiguously, `operator[]` computes the address directly, giving O(1) access.
2. What typically happens when `push_back` exceeds a vector's current capacity?
Vectors handle growth by allocating a new, larger buffer, transferring existing elements, and releasing the old memory, giving amortized O(1) push_back.
3. What can invalidate iterators or pointers into a `std::vector`?
Any operation that reallocates the vector's buffer, or shifts elements via insertion/erasure, can invalidate existing iterators, pointers, and references.
Flash Cards
What is `std::vector`? — A dynamic, contiguous array container that resizes automatically and provides O(1) indexed access.
What is the time complexity of `push_back`? — Amortized O(1) due to capacity doubling on growth.
What invalidates a vector's iterators? — Reallocation from growth, or shifting from insertion/erasure in the middle.
What does `reserve(n)` do? — Pre-allocates capacity for at least `n` elements, avoiding repeated reallocations during growth.