C++ STL Series · Part 1 of 5

Vectors — Dynamic Arrays Done Right

March 2026 · 12 min read

What is std::vector?

std::vector is the workhorse container of C++. It manages a contiguous block of memory that grows automatically as you push elements. Think of it as a smarter, resizable C array with bounds awareness and RAII cleanup.

#include <vector>
#include <iostream>

int main() {
    std::vector<int> v = {1, 2, 3, 4, 5};
    v.push_back(6);

    for (auto x : v) std::cout << x << " ";
    // Output: 1 2 3 4 5 6
}

Memory Layout & Growth Strategy

A vector stores three pointers internally:

begin — start of allocated block
end (size) — one past the last element
end_cap (capacity) — one past the last allocated slot

When size == capacity and you push_back, the vector allocates a new block (typically 2× the old capacity), copies or moves all elements, and deallocates the old block.

▶ Vector Growth & Reallocation

Watch push_back trigger a reallocation when size hits capacity.

Key insight: The amortized cost of push_back is O(1), but a single push_back during reallocation is O(n). Pre-allocate with reserve() when you know the expected size.

std::vector<int> v;
v.reserve(1000);  // allocate once, no reallocs for 1000 pushes

for (int i = 0; i < 1000; ++i)
    v.push_back(i);

std::cout << "size: " << v.size()         // 1000
          << " cap: "  << v.capacity();    // 1000

Iterator Invalidation

This is where most bugs hide. Any operation that changes a vector's size can invalidate all iterators, pointers, and references to its elements because the underlying memory address might change during reallocation.

std::vector<int> v = {1, 2, 3};
auto it = v.begin();

v.push_back(4);   // ⚠️ 'it' may now be dangling!
// *it is undefined behavior

Safe Patterns

Use indices instead of iterators when doing insertions in a loop.
Re-obtain iterators after any mutating operation.
Prefer reserve() before batch insertions.

Performance Traps

Erasing in the Middle

v.erase(it) shifts all subsequent elements left — O(n). If order doesn't matter, swap the target with the back and pop:

// O(1) unordered erase
std::swap(v[idx], v.back());
v.pop_back();

std::vector<bool> is not a vector

The specialization std::vector<bool> packs bits and returns proxy objects instead of references. Avoid it — use std::vector<char> or std::bitset instead.

emplace_back vs push_back

emplace_back constructs elements in-place, avoiding a temporary copy or move:

struct Point { int x, y; };

std::vector<Point> pts;
pts.push_back(Point{1, 2});  // construct temp, then move
pts.emplace_back(1, 2);      // construct directly in vector memory

Rule of thumb: Use emplace_back when constructing complex objects. For primitives and trivially copyable types, both are equivalent.

Releasing Memory with shrink_to_fit

After removing many elements, the capacity stays high. Call shrink_to_fit() to request the allocator release unused memory.

v.erase(v.begin(), v.begin() + 900);
v.shrink_to_fit();  // capacity now ≈ size

Summary

std::vector gives you contiguous storage with automatic growth.
Always reserve() when the size is predictable.
Watch for iterator invalidation on any size-changing operation.
Prefer emplace_back for non-trivial types.
Avoid std::vector<bool>.