How Do Vectors Work in C++?
Understand how std::vector works in C++ — contiguous storage, size vs capacity, amortized O(1) append, and O(1) indexed access explained simply.
Expected Interview Answer
A std::vector is a dynamic array that stores elements contiguously in memory and grows automatically, offering O(1) indexed access and amortized O(1) append at the end.
It maintains a size (elements in use) and a capacity (allocated slots). When you push past capacity, the vector allocates a larger block (commonly doubling), copies or moves existing elements over, and frees the old block — which is why append is amortized O(1) rather than always O(1). Because storage is contiguous, indexing is constant time and iteration is cache-friendly, but inserting or erasing in the middle is O(n) since later elements must shift.
- Fast O(1) random access by index
- Amortized O(1) append at the back
- Contiguous, cache-friendly memory layout
- Automatic resizing and memory management
- Works directly with STL algorithms via iterators
AI Mentor Explanation
A vector is like a stadium stand where seats are numbered in one continuous row, so you find seat 42 instantly. When the stand fills up, the ground builds a bigger stand, moves everyone across, and demolishes the old one — the same reallocation a vector does when it outgrows its capacity.
Step-by-Step Explanation
Step 1
Declare and initialize
Create a vector, optionally with initial elements: std::vector<int> v{1, 2, 3}.
Step 2
Access by index
Use v[i] for O(1) unchecked access or v.at(i) for bounds-checked access that throws.
Step 3
Append elements
push_back or emplace_back adds to the end in amortized O(1) time.
Step 4
Understand size vs capacity
size() is elements in use; capacity() is allocated slots — growth reallocates when size exceeds capacity.
Step 5
Iterate or transform
Use range-based for or iterators with STL algorithms; note iterators invalidate after reallocation.
What Interviewer Expects
- Vector is a contiguous dynamic array
- Difference between size and capacity
- Why append is amortized O(1), not always O(1)
- Cost of middle insert/erase is O(n)
- Iterator invalidation on reallocation
Common Mistakes
- Saying push_back is always O(1) instead of amortized
- Confusing size() with capacity()
- Using v[i] without checking bounds and expecting an exception
- Holding onto iterators or pointers after a reallocation
- Assuming middle insertion is cheap like it is for a list
Best Answer (HR Friendly)
“A vector in C++ is a resizable array that keeps items in a row and lets you reach any item instantly by its position. When it fills up, it quietly moves everything into a bigger space, so you never manage memory by hand.”
Code Example
#include <vector>
#include <iostream>
int main() {
std::vector<int> v{10, 20, 30};
v.push_back(40); // amortized O(1) append
std::cout << v[2] << "\n"; // O(1) access -> 30
std::cout << v.at(0) << "\n"; // bounds-checked -> 10
std::cout << "size=" << v.size()
<< " capacity=" << v.capacity() << "\n";
v.reserve(100); // pre-allocate to avoid regrowth
for (int x : v) std::cout << x << ' ';
std::cout << "\n";
return 0;
}Follow-up Questions
- What is the difference between size() and capacity()?
- Why is push_back amortized O(1) instead of O(1)?
- When does reserve() help performance?
- What invalidates vector iterators?
- How does vector differ from std::array and std::list?
MCQ Practice
1. What is the time complexity of accessing vector element by index?
Because a vector stores elements contiguously, indexing computes an address directly in constant time.
2. Why is push_back described as amortized O(1)?
Most appends are O(1); only when capacity is exceeded does it reallocate and copy, and doubling makes that rare, so the average stays O(1).
3. Which method returns the number of elements currently stored?
size() reports elements in use; capacity() reports how many slots are allocated.
Flash Cards
Vector index access complexity? — O(1) — elements are contiguous so the address is computed directly.
size vs capacity? — size() is elements in use; capacity() is allocated slots. Growth reallocates when size exceeds capacity.
Why amortized O(1) append? — Reallocation copies all elements but happens rarely (capacity doubles), so the per-append cost averages to O(1).
What invalidates vector iterators? — Any reallocation (e.g. push_back past capacity) and erasing/inserting elements can invalidate iterators and pointers.