std::vector is a growable array that stores its elements contiguously in memory. It's the default sequence container in C++, the first choice for any list of things that can grow or shrink. This chapter covers how vectors lay out memory, the difference between size and capacity, how the growth policy works, the full API (push_back, emplace_back, insert, erase, at, operator[], reserve, resize), iterator invalidation rules, and when to use a vector versus another container. The iterator and algorithm chapters later in this section pick up where this one leaves off.

Three properties make std::vector the right starting point for almost any sequence problem.

First, the elements are laid out contiguously in memory. That's the same layout as a C-style array, which is what the CPU's cache hardware is built to handle. Walking a million ints in a vector is essentially as fast as walking a raw array, because the prefetcher can see the access pattern and pull the next cache line before the read.

Second, indexing is O(1). v[i] is a single pointer-plus-offset operation, identical to a raw array access. There's no traversal, no chasing of pointers, no hash computation. The cost is that inserting in the middle is expensive (everything after the insertion point has to shift), but most code doesn't insert in the middle very often.

Third, the size is dynamic. Unlike a C-style array or std::array, a vector grows as more elements are pushed onto it. It does this by reallocating to a bigger buffer when it runs out of room, copying or moving elements over, and freeing the old buffer. That reallocation is the one cost worth understanding.

Three pushes, no manual memory management, and the elements are stored back-to-back in a single heap buffer the vector owns. The vector's destructor frees that buffer when the variable goes out of scope.

A std::vector<T> object itself usually has three pointers inside it (or equivalently, a pointer plus two sizes): a pointer to the start of the buffer, a pointer to the end of the live elements, and a pointer to the end of the allocated buffer. The elements themselves live on the heap, in one contiguous block.

The cyan box on the stack is the vector object, which is small (typically 24 bytes on a 64-bit system: three pointers, or data, size, capacity). The orange boxes are the live elements stored consecutively on the heap. The teal boxes are slots the vector has allocated but hasn't used yet. That spare room is what lets push_back be cheap most of the time.

Two consequences follow from this layout.

The first is that a vector's data can be passed to any C-style API that takes a T* plus a length. v.data() returns a raw pointer to the first element, and the elements continue in memory up to v.data() + v.size(). That's exactly what read, write, memcpy, and most C numeric libraries want.

The second is that growing the vector beyond its current allocated capacity requires moving everything to a bigger buffer. The vector cannot just "extend" the existing block, because the surrounding heap might already be occupied. It has to allocate a fresh, larger buffer, move (or copy) the elements over, and free the old one. That's the cost quantified next.

These two words mean different things and they're easy to mix up. size() is the number of live elements in the vector. capacity() is the size of the allocated buffer, which is greater than or equal to size(). The gap between them is the room the vector has to grow into before it needs to reallocate.

Capacity jumps in powers of two on libstdc++ (1, 2, 4, 8, 16, ...). The exact growth factor isn't part of the standard, but every mainstream implementation grows geometrically. libstdc++ uses 2x. Microsoft's STL uses 1.5x. libc++ uses 2x. The pattern is the same: when the buffer is full, allocate a bigger one (some factor larger), move elements over, free the old one.

push_back is amortised O(1). Most pushes are constant time (write into the spare slot, bump size by 1). Occasionally a push triggers a reallocation, which is O(n) because every existing element has to move. Geometric growth ensures the total cost over n pushes is O(n), so the average per push is O(1).

The growth-factor choice matters more than it looks. A factor of 2 is simple but slightly wasteful: when reallocation happens, the new buffer can't reuse the old buffer's memory range (the old range is half the new range, so the heap can't extend in place). A factor between 1 and 2 (Microsoft picked 1.5) allows the new buffer to potentially reuse freed older buffers. The trade-off is academic for most code; the point is that both factors achieve the amortised O(1) guarantee.

There are several ways to make a vector. Pick the one that matches what you know at construction time.

A subtle trap lives in constructors 2 and 3. std::vector<int> b(5) makes a vector of five zeros. std::vector<int> d{5} (brace-init with one value) makes a vector of one element whose value is 5. The two-argument forms behave the same way: c(4, 99) is four nines, c{4, 99} is {4, 99}. The difference is that round-brace (...) calls the constructor with positional arguments, while brace-init {...} always prefers the initializer-list constructor when one matches. This is one of the few places where C++'s uniform initialisation has visibly different behaviour from the round-brace form. Most codebases pick a convention and stick with it.

push_back appends one element to the end. It's the workhorse.

emplace_back constructs the element in place at the end of the vector, forwarding its arguments to the element's constructor. It avoids the temporary that push_back would otherwise need.

Both end up constructing one Product, but for the push_back path the compiler may need an extra move (depending on optimisations). With emplace_back, the arguments are forwarded straight to the Product constructor and the object is built directly in the vector's storage. For trivial types it doesn't matter; for types with expensive construction it's a measurable win.

insert adds elements at a given position. The position is specified by an iterator.

vector::insert(pos, x) is O(n) when pos is not at the end, because every element from pos to the end has to shift by one slot. insert(begin(), x) is the worst case. For fast front insertion, use std::deque instead.

There are several overloads of insert: a single value, n copies of a value, a range of iterators, and (since C++11) an initializer list.

pop_back removes the last element. It does not return the element; to keep the value, read back() first.

erase removes an element or a range, given iterators.

vector::erase(pos) is O(n) for the same reason insert is: every element after pos shifts down by one. Erasing from the end (or using pop_back) is O(1).

clear removes every element. The capacity is not reduced; the vector keeps its buffer.

That capacity-retention behaviour is deliberate. For refilling the vector right after clearing it, re-allocating the buffer is wasted work. To release the memory, call shrink_to_fit() after clear(), or move from a fresh empty vector (the "swap trick").

operator[] does an unchecked indexed read or write. It does not verify that the index is in range. Out-of-range access is undefined behaviour.

at(i) does a checked read. If i is out of range, it throws std::out_of_range. The cost is a comparison on every access.

When to use which? operator[] is the right default. The index is usually valid because of the surrounding loop, an explicit check, or the algorithm's invariants. Using at everywhere just to "be safe" adds a comparison per access that the compiler can rarely eliminate. Use at when the index comes from untrusted input that hasn't been validated, or when the cost of being wrong is large enough to warrant the check.

front() and back() return references to the first and last elements. Calling either on an empty vector is undefined behaviour, so check empty() first when in doubt.

data() returns a raw pointer to the underlying contiguous buffer. It's how you hand a vector's storage to a C API. The pointer remains valid until the next reallocation.

data() is one of the reasons std::vector bridges modern C++ and C. Pass buf.data() and buf.size() and almost any C function works.

These three methods control the buffer directly.

reserve(n) ensures the capacity is at least n. If the current capacity is smaller, the vector reallocates to size n. If the current capacity is already at least n, reserve does nothing. It does not change size().

reserve is the right tool when the final size is known in advance. Avoiding ten reallocations by calling reserve(N) once is one of the most common and effective vector optimisations. The pushes themselves stay amortised O(1) either way, but the constant factor matters when N is large.

reserve(n) reallocates exactly once (if needed). Without reserve, growing from 0 to n elements via push_back reallocates roughly log2(n) times. The total work is the same in big-O terms, but reserve does it in one allocation instead of a dozen.

shrink_to_fit() is a non-binding request to release unused capacity. The implementation may or may not honour it. Usually it reallocates to a buffer of size size().

resize(n) changes the size. If n > size(), new elements are default-constructed (or initialised to a value you supply) and capacity grows if needed. If n < size(), the trailing elements are destroyed and capacity is unchanged.

resize sets the size explicitly. reserve pre-allocates room without changing what the vector contains. They are different operations and serve different purposes.

A vector iterator is essentially a pointer into the buffer. When the buffer moves (reallocation) or shifts (insert/erase in the middle), iterators stop pointing where expected.

The rules are precise.

The most common bug is holding an iterator across a push_back that triggers reallocation.

If the initial capacity of v is 3 (common after brace initialisation), the push_back reallocates, and it is left pointing at freed memory. Reading through it is undefined behaviour. The program might print 1, might print garbage, might crash.

The fix is simple: don't hold iterators across operations that can reallocate, or re-obtain the iterator after the operation.

A common idiom for erase-in-a-loop is to use the iterator that erase returns. erase returns an iterator to the element after the erased one, allowing iteration to continue.

The pattern: when erasing, take the return value of erase and use it as the new iterator. When not erasing, advance with ++it. Crucially, do not put ++it in the for-header, because that would skip the element right after every erased one.

Erasing elements one at a time in a loop is O(n^2) on a vector, because each erase is O(n). For removing a predicate-matching subset, the idiomatic approach is the erase-remove idiom: v.erase(std::remove_if(v.begin(), v.end(), pred), v.end());. That's O(n) total, even though it looks like more work. The algorithm chapters cover std::remove_if in detail.

Three idioms, each with its place.

The range-based for loop is sugar for the iterator loop: the compiler rewrites it to use begin() and end(). Prefer it for readability. Drop to the indexed form when the index is needed for logic (printing slot numbers, looking up a parallel array). Use explicit iterators when handing them to an algorithm like std::sort or std::find. Iterators get their dedicated chapters later in this section.

The big-O behaviour of the common operations, in one table.

swap deserves a moment. Swapping two vectors doesn't move any element; it just swaps the three internal pointers (data, size, capacity). That's why the "swap trick" for releasing memory is std::vector<T>().swap(v);. A fresh empty vector is created, swapped with v, and then destroyed at the end of the expression, taking the original buffer with it.

shrink_to_fit is the more readable alternative. The swap trick is mostly a relic from before C++11 added shrink_to_fit, but you'll still see it in older codebases.

std::vector is the default sequence container. Use it unless there's a specific reason not to.

Use vector when:

Use something else when:

The choice "vector vs list" causes the most confusion. The textbook answer is "use list when inserting in the middle, because list insert is O(1)". The realistic answer is "use vector almost always, because list traversal is so cache-unfriendly that even O(1) inserts can lose to vector's O(n) shifts for small to medium n". Measure before reaching for list.

A small running example that touches the major operations: build a cart, total it, sort by price, and remove out-of-stock items.

reserve avoids reallocation during the four emplace_back calls. emplace_back constructs each CartItem in place. std::accumulate from <numeric> walks the iterators to compute the total. std::sort reorders the vector. std::remove_if paired with erase is the canonical pattern for removing matching elements in O(n) instead of repeated O(n) erases. The whole program is six STL operations, and every one of them is a few words of code.