VVeeccttoorr ((DDyynnaammiicc AArrrraayy))

Internals · Capacity · Iterators · Algorithms · Move Semantics · emplace

C++17 · Advanced Reference

std::vector Internals

How vector works

std::vector<T> owns a contiguous heap-allocated buffer. It tracks two numbers: size (elements in use) and capacity (elements that fit before the next reallocation). When you push_back past capacity, the vector allocates a new buffer (~2× larger), moves all elements, and frees the old one.

Complexity

1.push_back / pop_back — amortized O(1). Occasional O(n) reallocation, but rare.
2.operator[] / at() — O(1) random access.
3.insert / erase at middle — O(n). Shifts all elements after the point.
4.find (unsorted) — O(n). binary_search (sorted) — O(log n).

Iterator invalidation rules

1.push_back / emplace_back — invalidates all iterators if reallocation occurs.
2.insert / erase — invalidates iterators at or after the point of change.
3.reserve — may invalidate all iterators (if reallocation happens).
4.pop_back / resize smaller — only end() and erased elements invalidated.

When in doubt after mutating a vector, re-obtain iterators. Using indices is safer than storing iterators across mutations.

Construction & Access

#include <vector>

// Construction
std::vector<int> a;                     // empty
std::vector<int> b(5);                  // 5 zeros
std::vector<int> c(5, 42);              // {42,42,42,42,42}
std::vector<int> d = {1, 2, 3, 4, 5};  // initializer list
std::vector<int> e(d);                  // copy of d
std::vector<int> f(d.begin(), d.begin()+3); // {1,2,3} — iterator range

// 2D vector
std::vector<std::vector<int>> mat(3, std::vector<int>(4, 0)); // 3×4 zeros

// Access
d[2]          // 2 — unchecked, UB on out-of-bounds
d.at(2)       // 2 — throws std::out_of_range
d.front()     // 1 — first element
d.back()      // 5 — last element
d.data()      // raw int* to internal buffer

vector<int>(n)	n zero-initialized elements.
vector<int>(n, val)	n copies of val.
v[i]	Unchecked — undefined behavior if i >= size(). Fast.
v.at(i)	Bounds-checked — throws std::out_of_range. Use during development/testing.
iterator range ctor	vector<int>(first, last) — copies elements from any iterator range.

Modifying a Vector

std::vector<int> v = {1, 2, 3};

// Add / remove at end (fast — amortized O(1))
v.push_back(4);          // {1,2,3,4}
v.pop_back();            // {1,2,3}
v.emplace_back(4);       // same as push_back but constructs in-place

// Insert / erase (slow — O(n) — shifts elements)
v.insert(v.begin() + 1, 99);   // {1,99,2,3} — insert before index 1
v.erase(v.begin() + 1);        // {1,2,3}    — erase at index 1
v.erase(v.begin()+1, v.begin()+3); // erase range [1,3)

// Clear & resize
v.clear();               // empty, capacity unchanged
v.resize(5);             // size=5, new elements zero-initialized
v.resize(5, 99);         // size=5, new elements = 99
v.assign(3, 0);          // replace contents with {0,0,0}

// ── Erase-remove idiom (remove all matching values) ──────────
#include <algorithm>
v.erase(std::remove(v.begin(), v.end(), 2), v.end());
// C++20: std::erase(v, 2);  — cleaner shorthand

push_back(x)	Copies or moves x to the end. Amortized O(1).
emplace_back(...)	Constructs element in-place from arguments. Avoids the extra move. Prefer for non-trivial types.
insert(it, x)	O(n) — shifts everything after it. Avoid in hot loops.
erase-remove	The standard idiom for removing all elements matching a value or predicate. C++20: std::erase(v, val).

Size vs Capacity

std::vector<int> v;

v.size()       // number of elements currently stored
v.capacity()   // number of elements that fit without reallocation
v.empty()      // true if size() == 0

// ── Reserve — avoid repeated reallocations ───────────────────
v.reserve(1000);        // allocate for 1000 elements upfront
for (int i = 0; i < 1000; i++) v.push_back(i);  // no reallocations

// ── Growth policy ────────────────────────────────────────────
// When capacity is exceeded, vector reallocates to ~2× the current
// capacity and moves all elements. This is why pointers/iterators
// into a vector are invalidated after push_back!
int* ptr = &v[0];
v.push_back(999);   // ⚠ ptr may now be dangling if reallocation occurred

// ── shrink_to_fit ─────────────────────────────────────────────
v.shrink_to_fit();  // hint to release excess capacity (non-binding)

// ── swap trick (guaranteed shrink) ───────────────────────────
std::vector<int>(v).swap(v);   // copy into exact-fit vector, swap

reserve(n)	Pre-allocates capacity for n elements. Prevents reallocations when final size is known. Does not change size().
resize(n)	Changes size() to n. Adds zero-initialized elements if growing; destroys elements if shrinking.
shrink_to_fit()	Non-binding hint to release excess capacity. Use after large removals to reclaim memory.
reallocation	Invalidates ALL pointers, references, and iterators into the vector. Call reserve() upfront to prevent.

Always reserve() when the final size is known. Without it, a vector of 1M elements will reallocate ~20 times. With reserve(1'000'000) — zero reallocations.

Iterators & Invalidation

std::vector<int> v = {10, 20, 30, 40, 50};

// Iterator types
auto it  = v.begin();   // iterator to first element
auto end = v.end();     // iterator past the last element
auto rit = v.rbegin();  // reverse iterator — points to last element

// Dereferencing and arithmetic
*it         // 10
*(it + 2)   // 30
it[2]       // 30 — random access iterator supports []

// Loop with iterator
for (auto it = v.begin(); it != v.end(); ++it) {
  std::cout << *it << " ";
}

// ── Iterator invalidation — the silent killer ─────────────────
auto saved = v.begin() + 2;   // points to 30
v.push_back(60);               // ⚠ may reallocate — saved is dangling!
v.insert(v.begin(), 0);        // all iterators invalidated

// Safe pattern: re-obtain iterator after mutation
// Or: use indices instead of iterators when modifying

begin() / end()	Forward iterators. end() is past-the-last — never dereference it.
rbegin() / rend()	Reverse iterators. rbegin() points to the last element.
cbegin() / cend()	Const iterators — cannot modify elements through them.
invalidation	Any operation that changes capacity (push_back, insert, reserve) may invalidate all iterators.

Use indices when mutating.Iterators are invalidated by reallocation. An index into v remains valid as long as you don't erase elements before it.

Vectors & Algorithms

#include <algorithm>
#include <numeric>

std::vector<int> v = {3, 1, 4, 1, 5, 9, 2, 6};

// Sort
std::sort(v.begin(), v.end());              // ascending: {1,1,2,3,4,5,6,9}
std::sort(v.begin(), v.end(), std::greater<int>()); // descending

// Search (requires sorted for binary search)
bool found = std::binary_search(v.begin(), v.end(), 4);
auto it = std::lower_bound(v.begin(), v.end(), 4);  // first ≥ 4

// Min / max element
auto minIt = std::min_element(v.begin(), v.end());  // iterator
auto maxIt = std::max_element(v.begin(), v.end());

// Accumulate
int sum = std::accumulate(v.begin(), v.end(), 0);   // 31
int product = std::accumulate(v.begin(), v.end(), 1, std::multiplies<int>());

// Unique (removes consecutive duplicates — sort first)
std::sort(v.begin(), v.end());
v.erase(std::unique(v.begin(), v.end()), v.end());  // {1,2,3,4,5,6,9}

// Partition
auto mid = std::partition(v.begin(), v.end(), [](int x){ return x % 2 == 0; });

lower_bound	Binary search on a sorted range — returns iterator to first element ≥ value. O(log n).
unique	Removes consecutive duplicates. Sort first to remove all duplicates globally.
partition	Reorders so elements matching predicate come first. Returns iterator to first non-matching element.
iota	Fills range with sequentially increasing values: 0,1,2,… Use for index generation.

Move Semantics & emplace

// Moving a vector — O(1), no element copies
std::vector<int> a = {1, 2, 3, 4, 5};
std::vector<int> b = std::move(a);  // b owns the data; a is now empty
a.empty();   // true — a was moved-from

// emplace_back vs push_back
struct Point { double x, y; };
std::vector<Point> pts;

pts.push_back({1.0, 2.0});           // constructs Point, then moves into vector
pts.emplace_back(1.0, 2.0);          // constructs Point directly in vector — no move

// Moving out of a vector element
std::vector<std::string> words = {"hello", "world"};
std::string s = std::move(words[0]); // s="hello", words[0] is valid but unspecified
// words[0] is in a valid but unspecified state — don't read it

// Returning a vector from a function — RVO applies, no copy
std::vector<int> makeRange(int n) {
  std::vector<int> v(n);
  std::iota(v.begin(), v.end(), 0);  // fill with 0,1,...,n-1
  return v;   // NRVO — no copy or move in practice
}

std::move(v)	Transfers ownership of the buffer in O(1). The moved-from vector is left empty and valid.
emplace_back	Forwards constructor arguments directly — constructs in-place, no temporary object.
moved-from state	A moved-from vector is in a valid but unspecified state. You can clear() or reassign it safely.
return vector	NRVO applies — returning a local vector is free. Don't std::move the return value.