Vectors in C++ — std::vector

std::vector is the most-used container in the C++ standard library. It is a dynamic array: it stores elements in a single contiguous block of heap memory, supports random access in O(1), and grows automatically when new elements are pushed in. Understanding how it works internally — and especially how growth, reallocation, and iterator invalidation operate — is essential for writing correct and efficient C++ code.

Before We Begin — The Simplest Possible Example

If you have never used std::vector before, start right here. You only need one header.

#include <vector> #include <iostream> int main() { // 1. Create an empty vector of integers std::vector<int> numbers; // 2. Add elements one by one to the back numbers.push_back(10); numbers.push_back(20); numbers.push_back(30); // 3. Access elements by index — exactly like a plain array std::cout << numbers[0] << "\n"; // 10 std::cout << numbers[1] << "\n"; // 20 std::cout << numbers[2] << "\n"; // 30 // 4. Loop over all elements for (int n : numbers) { std::cout << n << " "; } std::cout << "\n"; // Output: 10 20 30 // 5. Ask the vector how many elements it holds std::cout << numbers.size() << "\n"; // 3 // 6. Remove the last element numbers.pop_back(); std::cout << numbers.size() << "\n"; // 2 // 7. You can also create a vector with initial values directly std::vector<int> scores = {95, 87, 72, 100}; std::cout << scores[3] << "\n"; // 100 }
A std::vector behaves just like an array for reading and writing elements (v[i]), but it can grow automatically as you add elements. You never have to worry about pre-allocating the right size. The rest of this page explains how it does that and how to use it efficiently.

Topics of Discussion

  1. What is std::vector?
  2. Memory model — internal structure
  3. Size vs capacity and growth strategy
  4. Construction and initialisation
  5. Core operations and their complexity
  6. reserve() vs resize()
  7. Iterators and pointer/iterator invalidation
  8. 2D vectors
  9. Move semantics with vectors
  10. std::vector vs raw array vs std::array
  11. Common pitfalls

1. What is std::vector?

std::vector<T> is a contiguous, dynamically resizable array. Its elements are always stored next to each other in memory (like a C array), but unlike a C array its size can change at runtime. The vector object itself is small and lives on the stack (or wherever you declare it); the actual elements live on the heap.

Key guarantees from the standard:

  • Elements are stored in contiguous memory — &v[0] is a valid C-style array pointer.
  • Random access (v[i]) is O(1).
  • push_back is amortised O(1).
  • Insertion and deletion in the middle is O(n) — elements must be shifted.

2. Memory Model — Internal Structure

A std::vector object holds exactly three things:

  • data — a pointer to the heap-allocated element array.
  • size — the number of elements currently stored.
  • capacity — the total number of elements the current allocation can hold before a reallocation is needed.

On a 64-bit system each of those is 8 bytes, so sizeof(std::vector<T>) == 24 bytes regardless of how many elements it contains.

std::vector<int> v = {10, 20, 30} — Memory Layout STACK data pointer → heap size 3 capacity 5 sizeof(vector) = 24 bytes HEAP — contiguous allocation (capacity = 5 slots) 10 [0] 0x1000 20 [1] 0x1004 30 [2] 0x1008 — [3] reserved — [4] reserved size = 3 capacity = 5 All elements are adjacent in memory — address increments by sizeof(T) = 4 bytes

Because elements are contiguous, the compiler can vectorise loops over a std::vector exactly as it would over a C array. The data pointer is the only indirection: once dereferenced, the CPU accesses a flat array and cache prefetchers work perfectly.

What the vector object looks like in code

// Conceptual equivalent of what the standard library stores internally: template <typename T> class vector { T* data_; // pointer to heap array size_t size_; // number of live elements size_t capacity_; // allocated slots // ... allocator + methods }; // On a 64-bit system: std::vector<int> v; std::cout << sizeof(v) << "\n"; // prints 24 // The elements live on the heap, not inside 'v': v.push_back(10); int* raw = v.data(); // pointer to the heap block

3. Size vs Capacity and Growth Strategy

size is how many elements are currently in the vector. capacity is how many elements fit in the current allocation before a new one is needed. capacity >= size always holds.

When push_back is called and size == capacity, the vector must reallocate:

  1. Allocate a new, larger heap block (typically 2× the old capacity, but the factor is implementation-defined).
  2. Move (or copy) every existing element into the new block.
  3. Destroy elements in and deallocate the old block.
  4. Update the internal pointer, size, and capacity.
push_back — Reallocation when size == capacity BEFORE push_back(40) — size=3, capacity=3 (FULL) 10 [0] 20 [1] 30 [2] FULL — reallocation triggered allocate 2× block, move elements, free old block AFTER — size=4, capacity=6 (new allocation, 2× growth) 10 [0] 20 [1] 30 [2] 40 [3] ← new — [4] — [5] size = 4 capacity = 6 (doubled from 3) All pointers, references, and iterators to the old block are now INVALID

Why doubling gives amortised O(1)

Suppose we start with capacity 1 and push n elements. Reallocations happen at sizes 1, 2, 4, 8, …, n. The total copy work across all reallocations is 1 + 2 + 4 + … + n = 2n − 1, so the average cost per push_back is constant — O(1) amortised.

#include <vector> #include <iostream> int main() { std::vector<int> v; for (int i = 0; i < 10; ++i) { v.push_back(i); std::cout << "size=" << v.size() << " cap=" << v.capacity() << '\n'; } } // Typical output (libstdc++ / MSVC may differ slightly): // size=1 cap=1 // size=2 cap=2 // size=3 cap=4 // size=4 cap=4 // size=5 cap=8 // size=6 cap=8 // size=7 cap=8 // size=8 cap=8 // size=9 cap=16 // size=10 cap=16

4. Construction and Initialisation

#include <vector> #include <string> // 1. Default — empty vector, no allocation yet std::vector<int> a; // 2. Fill — 5 elements, all zero-initialised std::vector<int> b(5); // {0, 0, 0, 0, 0} // 3. Fill with value std::vector<int> c(5, 42); // {42, 42, 42, 42, 42} // 4. Initialiser list std::vector<int> d = {1, 2, 3, 4}; // 5. Copy construction — deep copy std::vector<int> e = d; // new heap allocation, elements copied // 6. Move construction — steals the heap buffer std::vector<int> f = std::move(d); // d becomes empty, no copy // 7. Range construction — from any iterators int arr[] = {10, 20, 30}; std::vector<int> g(arr, arr + 3); // 8. Works with any element type std::vector<std::string> names = {"Alice", "Bob", "Carol"};

5. Core Operations and Their Complexity

OperationMethodTime complexityNotes
Random accessv[i] / v.at(i)O(1)at() throws on out-of-range; [] does not
First elementv.front()O(1)UB if empty
Last elementv.back()O(1)UB if empty
Append at backv.push_back(x)O(1) amortisedMay reallocate
Construct at backv.emplace_back(args)O(1) amortisedConstructs in-place, avoids copy
Remove lastv.pop_back()O(1)Does not reallocate
Insert at positionv.insert(it, x)O(n)Shifts all following elements right
Erase at positionv.erase(it)O(n)Shifts all following elements left
Erase rangev.erase(first, last)O(n)Shifts suffix
Clear all elementsv.clear()O(n)Destroys elements; keeps capacity
Number of elementsv.size()O(1)
Current capacityv.capacity()O(1)
Empty checkv.empty()O(1)
Raw pointer to datav.data()O(1)Valid C-array pointer
Shrink allocationv.shrink_to_fit()O(n)Non-binding hint to release excess capacity

push_back vs emplace_back

struct Point { int x, y; Point(int x, int y) : x(x), y(y) {} }; std::vector<Point> pts; // push_back: constructs a temporary Point, then moves it into the vector pts.push_back(Point(1, 2)); // emplace_back: forwards arguments directly to the constructor inside the vector // NO temporary — the object is constructed in-place in the reserved slot pts.emplace_back(3, 4);
Prefer emplace_back when constructing complex objects. For cheap-to-copy primitives like int or double the difference is negligible and the compiler will optimise both identically.

insert and erase — with diagram

std::vector<int> v = {1, 2, 3, 4, 5}; // Insert 99 before index 2: {1, 2, 99, 3, 4, 5} v.insert(v.begin() + 2, 99); // Elements at [2], [3], [4] are shifted right — O(n) // Erase element at index 1: {1, 99, 3, 4, 5} v.erase(v.begin() + 1); // Elements at [2], [3], [4] are shifted left — O(n) // Erase range [1, 3): {1, 4, 5} v.erase(v.begin() + 1, v.begin() + 3);

6. reserve() vs resize()

These two methods look similar but do very different things:

  • reserve(n) — ensures the vector can hold at least n elements without reallocation. It changes capacity only; size is unchanged. No elements are constructed.
  • resize(n) — changes size to n. If n > size, new elements are value-initialised (zero for ints). If n < size, excess elements are destroyed.
std::vector<int> v; // reserve — capacity grows, size stays 0 v.reserve(100); std::cout << v.size() << '\n'; // 0 std::cout << v.capacity() << '\n'; // >= 100 // Now 100 push_backs happen without any reallocation for (int i = 0; i < 100; ++i) v.push_back(i); // resize — size grows, elements initialised to 0 std::vector<int> w; w.resize(5); // {0, 0, 0, 0, 0} w.resize(8, 99); // {0, 0, 0, 0, 0, 99, 99, 99} w.resize(3); // {0, 0, 0} — elements destroyed
Performance pattern: if you know the final size of the vector up front, call reserve(n) before filling it. This eliminates all reallocations and the associated memory copies, halving the constant factor for build-and-fill workloads.

7. Iterators and Iterator Invalidation

Iterating over a vector

std::vector<int> v = {10, 20, 30, 40}; // Range-for (most idiomatic) for (const auto& x : v) std::cout << x << ' '; // Iterator-based for (auto it = v.begin(); it != v.end(); ++it) std::cout << *it << ' '; // Index-based for (size_t i = 0; i < v.size(); ++i) std::cout << v[i] << ' '; // Reverse for (auto it = v.rbegin(); it != v.rend(); ++it) std::cout << *it << ' '; // STL algorithm std::for_each(v.begin(), v.end(), [](int x){ std::cout << x << ' '; });

Iterator invalidation rules

Iterator invalidation is one of the most common sources of bugs with std::vector. An iterator (or pointer, or reference) to a vector element becomes invalid — it may point to garbage or a deallocated address — after certain operations.
OperationIterators / pointers / references invalidated
push_back / emplace_back (causes reallocation)All iterators, pointers, and references to all elements
push_back / emplace_back (no reallocation)None — end iterator is invalidated but element iterators stay valid
insert (causes reallocation)All
insert (no reallocation)Iterator to insertion point and everything after it
eraseIterator to erased element and everything after it
pop_backIterator to the removed last element and end()
clearAll element iterators
resize / reserve (if reallocation)All
Index access, front(), back()None
// WRONG — iterator used after push_back may have reallocated std::vector<int> v = {1, 2, 3}; auto it = v.begin(); // iterator to element 1 v.push_back(4); // may reallocate std::cout << *it; // UNDEFINED BEHAVIOUR — it may be dangling // CORRECT — re-obtain iterator after modifying the vector v.push_back(5); it = v.begin(); // refresh iterator std::cout << *it; // safe: 1 // CORRECT — use index instead of iterator when mutating size_t idx = 0; v.push_back(6); std::cout << v[idx]; // safe: v[0] is always 1

8. 2D Vectors

A vector<vector<T>> is a vector of vectors. Each inner vector is an independent heap allocation — the rows are NOT contiguous with each other in memory.

// Declare a 3×4 grid of zeros int rows = 3, cols = 4; std::vector<std::vector<int>> grid(rows, std::vector<int>(cols, 0)); // Access and modify grid[1][2] = 42; // Iterate for (const auto& row : grid) { for (int val : row) std::cout << val << ' '; std::cout << '\n'; } // Jagged (irregular) — each row can have different length std::vector<std::vector<int>> jagged; jagged.push_back({1}); jagged.push_back({2, 3}); jagged.push_back({4, 5, 6});
vector<vector<int>> — Each row is a separate heap allocation Outer vector (stack) data / size=3 → inner vec array Inner vector objects (heap) row[0] data → row data row[1] data → row data row[2] data → row data Row data (separate heap allocs — NOT adjacent) 1 2 3 4 5 6 7 8 9 Rows are NOT contiguous — each row is at a different heap address For cache-friendly dense matrices use a flat vector<T> of size rows×cols instead
For a dense matrix where all rows have the same length, a flat 1D vector is much better for cache performance. Access element [r][c] as v[r * cols + c].
// Cache-friendly flat matrix — single contiguous allocation int rows = 3, cols = 4; std::vector<int> matrix(rows * cols, 0); // Access element at (r, c) matrix[1 * cols + 2] = 42; // row 1, col 2 // Iterate all elements — perfect for CPU prefetcher for (int r = 0; r < rows; ++r) for (int c = 0; c < cols; ++c) std::cout << matrix[r * cols + c] << ' ';

9. Move Semantics with Vectors

Move semantics (std::move) let you transfer ownership of a vector's heap buffer to another vector in O(1) — no element copying.

std::vector<int> a = {1, 2, 3, 4, 5}; // Move construction — steals a's buffer; a becomes empty std::vector<int> b = std::move(a); // b: {1,2,3,4,5} a: {} (a.data() == nullptr, a.size() == 0) // Move assignment — same idea std::vector<int> c; c = std::move(b); // c: {1,2,3,4,5} b: {} // Return value optimisation (RVO/NRVO) — compiler elides the copy/move entirely std::vector<int> make_vec(int n) { std::vector<int> v(n); std::iota(v.begin(), v.end(), 0); return v; // No copy; compiler constructs directly in the caller's variable } auto v = make_vec(1000); // zero copies
Passing vectors to functions:
  • const std::vector<T>& — read-only access, no copy. Use for most function parameters.
  • std::vector<T>& — modifiable reference to the caller's vector.
  • std::vector<T> (by value) — makes a copy. Use when the function needs its own independent copy or you pass with std::move.
  • std::vector<T>&& (rvalue ref) — explicit move parameter for sink functions.

10. std::vector vs Raw Array vs std::array

PropertyRaw array int[N]std::array<int,N>std::vector<int>
Size known at compile timeYes (fixed)Yes (fixed)No (runtime)
Memory locationStack (or static)Stack (or static)Object on stack, elements on heap
Dynamic resizeNoNoYes
Contiguous elementsYesYesYes
Bounds checkingNoat() yes, [] noat() yes, [] no
Copy / assignNo (decays to pointer)Yes (value semantics)Yes (value semantics)
STL algorithms compatibleVia std::begin/endYesYes
Overhead over raw arrayNoneNone3 pointer-sized fields + heap alloc
Best use caseLow-level C interopFixed-size, stack, constexprGeneral purpose, size unknown at compile time

11. Common Pitfalls

Pitfall 1 — Out-of-bounds access with []

std::vector<int> v = {1, 2, 3}; v[5]; // UNDEFINED BEHAVIOUR — no bounds check v.at(5); // throws std::out_of_range — safe for debugging

Pitfall 2 — Storing a pointer/reference and then modifying the vector

std::vector<int> v = {1, 2, 3}; int& ref = v[0]; // reference to first element v.push_back(4); // may reallocate std::cout << ref; // UNDEFINED BEHAVIOUR — ref is dangling

Pitfall 3 — Not reserving when size is known

// Slow — N reallocations for N pushes from empty std::vector<int> v; for (int i = 0; i < N; ++i) v.push_back(i); // Fast — zero reallocations std::vector<int> v; v.reserve(N); for (int i = 0; i < N; ++i) v.push_back(i);

Pitfall 4 — Erasing inside a range-for loop

// WRONG — erasing while iterating with range-for is undefined for (const auto& x : v) if (x == 3) v.erase(...); // iterator invalidated mid-loop // CORRECT — erase-remove idiom #include <algorithm> v.erase(std::remove(v.begin(), v.end(), 3), v.end()); // CORRECT — erase_if (C++20) std::erase_if(v, [](int x){ return x == 3; });

Pitfall 5 — vector<bool> is not a regular vector

// std::vector<bool> is a special case — it packs bits (1 bit per bool) // This means: operator[] does NOT return a bool& — it returns a proxy object // You cannot take the address of an element, and auto& may not work as expected std::vector<bool> flags = {true, false, true}; auto f = flags[0]; // f is a proxy, not bool& bool* p = &flags[0]; // COMPILE ERROR — cannot take address of proxy // If you need a real array of bools, use: std::vector<uint8_t> flags2 = {1, 0, 1}; // or std::deque<bool>
std::vector<bool> is a well-known design mistake in the standard library. It specialises vector to store bits (1 bit per element instead of 1 byte), which violates the usual container semantics. Unless you specifically need the space optimisation, avoid it.

Practice Tasks

Solve each problem on your own before revealing the solution. All you need is #include <vector> and #include <iostream>.

1Create and inspect a vector.
Create a vector containing the values {3, 7, 1, 4, 9}. Print every element on one line separated by spaces, then print the total number of elements.

#include <vector> #include <iostream> int main() { std::vector<int> v = {3, 7, 1, 4, 9}; for (int x : v) std::cout << x << " "; std::cout << "\n"; // 3 7 1 4 9 std::cout << v.size() << "\n"; // 5 }

2Sum of all elements.
Write a function int sum(const std::vector<int>& v) that returns the sum of all elements. Test it with {1, 2, 3, 4, 5} — the answer should be 15.

#include <vector> #include <iostream> int sum(const std::vector<int>& v) { int total = 0; for (int x : v) total += x; return total; } int main() { std::vector<int> v = {1, 2, 3, 4, 5}; std::cout << sum(v) << "\n"; // 15 }

3Find the maximum value.
Without using any standard library algorithm, write a function that finds and returns the largest value in a non-empty vector. Test with {4, 2, 8, 1, 9, 3} — answer: 9.

#include <vector> #include <iostream> int max_val(const std::vector<int>& v) { int best = v[0]; // start with first element for (size_t i = 1; i < v.size(); ++i) { if (v[i] > best) best = v[i]; } return best; } int main() { std::vector<int> v = {4, 2, 8, 1, 9, 3}; std::cout << max_val(v) << "\n"; // 9 }

4Remove all even numbers.
Start with {1, 2, 3, 4, 5, 6, 7, 8}. Remove every even number using the erase-remove idiom. The result should be {1, 3, 5, 7}.

#include <vector> #include <algorithm> #include <iostream> int main() { std::vector<int> v = {1, 2, 3, 4, 5, 6, 7, 8}; // std::remove shifts non-even elements to the front and returns // an iterator to the new logical end. erase then deletes the rest. v.erase( std::remove_if(v.begin(), v.end(), [](int x){ return x % 2 == 0; }), v.end() ); for (int x : v) std::cout << x << " "; // 1 3 5 7 }

5Reverse a vector in-place.
Reverse the elements of {1, 2, 3, 4, 5} without using std::reverse. Result: {5, 4, 3, 2, 1}.
Hint: swap the first element with the last, then the second with the second-to-last, and so on.

#include <vector> #include <iostream> #include <utility> // std::swap void reverse_vec(std::vector<int>& v) { size_t left = 0; size_t right = v.size() - 1; while (left < right) { std::swap(v[left], v[right]); ++left; --right; } } int main() { std::vector<int> v = {1, 2, 3, 4, 5}; reverse_vec(v); for (int x : v) std::cout << x << " "; // 5 4 3 2 1 }