The growable, contiguous array you'll reach for 80% of the time — how it works, the everyday operations, and the one thing about its memory you must understand.
🎯 Pick the right container by reflex — start with the defaultstd::vector<T> is a dynamic array: elements sit in one contiguous block, it grows automatically, and access by index is instant. The official advice is blunt — use vector by default unless you have a concrete reason not to.
A vector is a contiguous, resizable array that owns its elements. "Contiguous" is the superpower: the elements are laid out back-to-back in memory, which is exactly what CPUs and caches love — so iterating a vector is about as fast as it gets.
#include <vector> std::vector<int> v = {10, 20, 30}; // three ints, side by side in memory v.push_back(40); // now {10, 20, 30, 40} std::cout << v[2]; // 30 — instant, O(1) random access
-std=c++17 or newer.vector usually beats a "faster on paper" linked list (std::list) in real benchmarks: the list's nodes are scattered, so every step is a cache miss.You'll use the same dozen members constantly. Here's the working set:
std::vector<std::string> names; // empty names.push_back("Ada"); // append (copies the string in) names.emplace_back("Grace"); // append, constructing in place (often cheaper) names.size(); // 2 — how many elements names.empty(); // false — size()==0 ? names[0]; // "Ada" — fast, NO bounds check names.at(5); // throws std::out_of_range — checked access names.front(); // "Ada" — first names.back(); // "Grace" — last for (const auto& n : names) // range-for: the idiomatic loop std::cout << n << "\n"; names.pop_back(); // remove the last element names.clear(); // remove all; size()==0 (capacity may stay)
[i] vs .at(i)[i] is unchecked (fast; out-of-range is undefined behavior). .at(i) bounds-checks and throws std::out_of_range. Use [] in hot loops you've reasoned about, .at() when an index could be bad.
push_back vs emplace_backpush_back(x) copies/moves an existing object in. emplace_back(args…) constructs the element in place from constructor arguments — skips a temporary. Prefer emplace_back when building objects.
for (const auto& x : v) is the idiomatic way to read every element. The & avoids copies; const says you won't modify. Drop const to mutate in place.
A vector tracks two numbers. size is how many elements you've put in. capacity is how many it can hold before it must grab a bigger block of memory. When push_back would exceed capacity, the vector reallocates: allocates a larger block (typically ~2×), copies/moves every element over, and frees the old one.
push_backs are cheap and the occasional copy averages out to amortized O(1).Two practical consequences:
v.reserve(n) grabs capacity once, up front — turning n growth-reallocations into zero. Big win in loops.v[0] across a push_back.std::vector<int> v; v.reserve(1000); // one allocation, capacity now >= 1000 for (int i = 0; i < 1000; ++i) v.push_back(i); // zero reallocations — all cheap
int& first = v[0]; v.push_back(x); use(first); — if that push_back reallocated, first now points at freed memory. Re-fetch v[0] after any operation that can grow the vector.Source: cppreference — push_back (amortized constant; reallocation invalidates iterators/references).
| Operation | Cost | Notes |
|---|---|---|
v[i], at, front, back | O(1) | random access — the headline feature |
push_back / pop_back | amortized O(1) | occasional realloc averages out |
insert / erase in the middle | O(n) | must shift everything after it |
std::find (unsorted) | O(n) | linear scan — no key lookup (that's map's job) |
| insert/erase at the front | O(n) | shifts all elements — use deque if you need this |
Vector is the default, not the only choice. Its siblings trade contiguity for a different strength:
| Container | Reach for it when… | Cost of its trick |
|---|---|---|
vector | default; growable, index access, iterate fast | slow insert in middle/front |
array<T,N> | fixed size known at compile time; no heap, no growth | size can never change |
deque | fast push/pop at both ends | not one contiguous block; slightly slower indexing |
list | you splice/insert in the middle constantly and never index | cache-unfriendly; usually loses to vector in practice |
std::array deserves a note: it's a thin, zero-overhead wrapper around a C array with a fixed compile-time size N — but it gives you .size(), .at(), range-for, and works with algorithms. Prefer it over raw int a[10].
vector. Switch only when a real access pattern demands it — fixed size → array; both-ends → deque; key lookup → map/unordered_map (Lesson 4). The full selection flowchart lives in the cheat sheet.Source: cppreference — Containers library (sequence containers) · Core Guidelines SL.con.1 — prefer array/vector over C arrays.
size() and capacity()?push_back "amortized O(1)" rather than just O(1)?int& r = v[0]; then call v.push_back(99). What's the risk?std::vector in one sentence?v[i] vs v.at(i)?[i] is unchecked (fast; out-of-range = undefined behavior). .at(i) bounds-checks and throws std::out_of_range.push_back/insert would exceed capacity(). It moves to a bigger block and frees the old one — invalidating all existing iterators, pointers, and references.reserve(n) do and why use it?size().push_back vs emplace_back?push_back inserts an existing object (copy/move); emplace_back(args…) constructs the element in place from constructor args, avoiding a temporary.vector usually beat list in practice?Try: "show me capacity() doubling as I push in a loop", or "when is list actually the right call?" Paste me a snippet and ask whether it has a reallocation bug.