How std::vector Really Works

The sensor log that keeps growing

A weather station receives temperature readings one at a time. The program needs to keep them in order and retrieve any earlier reading by position. A std::vector<int> is a natural representation: contiguous elements, indexed access, and automatic storage management. The interesting question arrives when the next reading does not fit in the current storage.

Suppose a teaching buffer has capacity four and contains four readings: 12, 15, 13 and 16. A fifth reading, 14, cannot be placed beyond that allocation. Something must create more room. The vector may obtain new storage, transfer the existing elements, construct the new element and release the old storage. What looked like one append contains several operations.

This lesson explains that work, what it does to addresses you borrowed earlier, and what it costs over a whole run of appends. The public example is a sensor log; the lab uses scores, tracked objects and a small teaching container. You need module 4's size and capacity, module 7's lifetime, and module 8's ownership distinction.

Size is not capacity

size() is the number of constructed elements the vector contains. capacity() is the number of elements its current storage can accommodate without reallocation. Having capacity eight and size five does not create three extra integers that can legally be read with indexing. The spare area is room for future objects, not already existing vector elements.

reserve(k) requests capacity for at least k elements. It does not change size. resize(k) changes the number of elements, constructing or destroying elements as required. Confusing the two can produce a program that appears to allocate enough memory but then accesses an index outside the vector's element range.

#include <vector>
int main() {
    std::vector<int> readings;
    readings.reserve(7);
    if (!readings.empty() || readings.capacity() < 7) return 1;
    readings.resize(3, 12);
    return readings.size() == 3 && readings[2] == 12 ? 0 : 1;
}

This program checks portable properties. It does not require the implementation to choose capacity exactly seven. A library may allocate more than requested. The standard's guarantees are the appropriate contract for portable code; an observed capacity sequence describes a particular implementation and version.

Rebuilding on every arrival

A naive growing array could allocate exactly one extra element for every append. On the first append it transfers zero old values, on the second one value, on the third two values, and so on. After n appends, the old-element transfers add up to n(n-1)/2. That is quadratic total transfer work in this model.

The waste comes from rebuilding nearly the same prefix repeatedly. The third allocation contains the first two values, the fourth contains those values again, and every later allocation keeps repeating the transfer. A different policy can pay for spare room now and avoid many of these rebuilds later.

One common policy grows geometrically: each new buffer is a fixed multiple of the old one. A teaching container doubles capacity when full, starting at one. It creates capacity one, two, four, eight and so forth.

Keep two statements apart here. The C++ standard requires that push_back on a vector takes amortized constant time. Amortized means averaged over a whole sequence of operations: the total cost of any n appends, divided by n, stays below a fixed constant, even though single appends may be expensive. It is a statement about every sequence, not about lucky inputs. The standard does not say how a library achieves it and names no growth factor. The library this course's lab runs, libc++ 21.1.4, happens to double: a full vector asks for the larger of twice its capacity and the size it needs. Another library may pick another factor, so portable code must not depend on doubling.

Watch one relocation

The safe conceptual order is obtain new storage, construct the required objects there, and only then relinquish the old storage when the transfer succeeds. Releasing the old allocation before reading its elements would access dead storage. Exception safety adds rollback obligations when element construction can fail; the lab's integer teaching container does not attempt them.

The picture shows values, but the ownership proof concerns object lifetimes too. For integers the transfer is straightforward. For a class object, transfer may mean calling a copy or move constructor and later destroying the old object. A vector of resource owners must preserve each element's own ownership contract during this process.

Addresses belong to an allocation

A pointer or reference to a vector element names an object in its current storage. So does an iterator: an object that marks a position in a container, the way readings.begin() marks the first element and readings.end() marks the spot just past the last one. Reallocation invalidates every pointer, reference and iterator to the old elements. Keeping the same numerical index does not keep the same object address. After growth, obtain a fresh borrow if you need to use that position again.

#include <cstddef>
#include <vector>
int main() {
    std::vector<int> readings = {12, 15, 13, 16};
    const std::size_t warmest = 3;       // a position
    int* borrowed = &readings[warmest];  // an address
    if (*borrowed != 16) return 1;
    readings.push_back(14);              // may reallocate
    borrowed = &readings[warmest];       // so take it again
    return *borrowed == 16 ? 0 : 2;
}

An index can be a better identifier when positions remain semantically stable. The program above stores position three, appends, and then asks the vector for that position again. This remains valid only if the position still exists and operations have not changed which logical reading occupies it. Inserting or erasing before it shifts positions, so an index is not a universal stable identity.

Appending without reallocation preserves existing element references and pointers, but invalidates the old past-the-end iterator, the one end() returned. Erasing invalidates iterators and references at or after the erased point. Inserting without reallocation invalidates those at or after the insertion point. “No reallocation means no invalidation” is therefore also too broad.

The representation invariant

Appending with spare capacity constructs one new element at the end and increments size. Existing elements remain where they are. Appending when full first establishes a new live prefix in new storage. Once it is safe to commit, the container replaces its old storage responsibility and updates its capacity. The resulting prefix contains the previous sequence followed by the appended value.

A teaching integer container can demonstrate this invariant, but a full std::vector<T> must also keep raw, not yet constructed storage apart from constructed elements, destroy elements one by one, and cope with constructors that throw. Allocating new T[capacity] constructs every slot immediately and requires default construction. It therefore models a simpler container, not all of vector's semantics. State that distinction before treating a small lab implementation as a replacement library.

A custom owning container must also decide what copying means. Default memberwise copying of its raw storage pointer creates two owners of one allocation. Deleting copy operations is appropriate for a limited teaching container. A production value container normally implements independent deep copying and suitable move operations. Correct growth does not by itself make copying correct.

Why occasional expensive appends are affordable

Count one unit for constructing a new integer and one unit for transferring an old integer; allocation itself is not counted. Take a doubling container that starts empty and receives $n\ge 2$ appends. It is full, and therefore grows, exactly when its size is 1, 2, 4 and so on. The last growth happens at size $2^k$, the largest power of two that is at most $n-1$. Each growth transfers every element present, so the transfers total

$$1+2+4+\dots +2^k=2^{k+1}-1\le 2n-3.$$

The last step uses $2^k\le n-1$. Adding the $n$ constructions gives at most $3n-3$ units for any $n$ appends in this model, which is fewer than three units per append. The bound is reached when $n$ is one more than a power of two, just after a growth; for a single append there is nothing to transfer.

One append can still transfer every existing element. Its worst-case cost is linear in the current size. Amortized constant cost means the total work for any sequence is linear in its length; it is not a claim that each individual append has a fixed cost or that random inputs make it fast.

def transfers(n, geometric):
    capacity = size = moved = 0
    for _ in range(n):
        if size == capacity:
            capacity = max(1, 2 * capacity) if geometric else size + 1
            moved += size
        size += 1
    return moved
sizes = (7, 9, 15, 31, 33)
assert [transfers(n, False) for n in sizes] == [21, 36, 105, 465, 528]
assert [transfers(n, True) for n in sizes] == [7, 15, 15, 31, 63]
assert [2 * n - 3 for n in sizes] == [11, 15, 27, 59, 63]
assert transfers(1, True) == 0
for n in range(2, 2000):
    assert transfers(n, False) == n * (n - 1) // 2
    assert transfers(n, True) <= 2 * n - 3
for k in range(10):
    n = 2 ** k + 1
    assert transfers(n, True) == 2 * n - 3

Read the doubling column with care: it is not a smooth function of the number of appends. Nine appends cost as many transfers as fifteen, because the growth at size eight has already been paid for. These numbers belong to the explicit policy above, not a benchmark of the installed standard library. They count element transfers rather than nanoseconds or bytes. For a type whose transfer itself takes nonconstant work, multiply by that cost or choose a more appropriate model.

Reserve once when the size is known

If the final number of readings is known, reserve sufficient capacity once before appending. The subsequent appends do not need reallocation while size remains within that capacity. The reserve call may itself allocate and relocate existing elements, so it should happen before borrowing their addresses.

Calling reserve(size()+1) before every append can recreate the exact-fit problem. A programmer trying to “help” the container can interfere with its growth strategy and obtain quadratic relocation work. Reserve is useful information about a future bound, not a ritual attached to each insertion.

Over-reserving has a different tradeoff: it commits storage that may never hold live elements. A log with an unknown length should normally use the container's growth behavior rather than invent an enormous upper bound. Memory cost matters alongside transfer cost. Shrinking size destroys removed elements but does not promise to reduce capacity.

Copying, moving, and constructing in place

Three calls put a new element at the end. push_back(x) with a named object x copies it, because the caller may still use x. push_back with an rvalue, an expression whose value nothing else will use again, such as a temporary or std::move(x), can move instead: the new element takes over what the old object held. emplace_back takes constructor arguments and builds the new element directly in its destination. None of these removes the need to relocate existing elements when storage is exhausted.

#include <string>
#include <utility>
#include <vector>
int main() {
    std::vector<std::string> stations;
    stations.reserve(3);
    std::string name = "north-ridge";
    stations.push_back(name);             // copy
    if (name != "north-ridge") return 1;
    stations.push_back(std::move(name));  // move
    stations.emplace_back(4, 'x');        // "xxxx", in place
    if (stations.size() != 3) return 2;
    if (stations[1] != "north-ridge") return 3;
    return stations[2] == "xxxx" ? 0 : 4;
}

The first call copies, so name keeps its text and the check after it passes. The second hands the text over: name is still a valid string afterwards, but the program should not rely on what it contains. The third passes 4 and 'x' to a string constructor that runs inside the vector.

Relocation is a separate question: how do the old elements reach the new storage? A standard library built with exceptions enabled moves them when the element's move constructor is declared noexcept, or when the element cannot be copied at all. If the element can be copied and its move might throw, the library copies instead, because a move that failed halfway would leave the old storage damaged with no way back. This is why noexcept and copyability must be discussed together, and why a move-only type with a throwing move is still moved, with a weaker guarantee if it fails.

The lab cannot show you that copy. Its browser compiler is built with exceptions switched off, and libc++ 21.1.4 then always moves on relocation, since nothing can throw. A type without noexcept is moved there and would be copied by the same library in an ordinary build. Marking a move that truly cannot throw as noexcept is what makes the fast path portable.

Moving a whole vector is different again from moving each of its elements: a move-constructed vector takes over the entire storage in constant time, and no element is touched.

A problem that looks different

A timeline editor stores markers, while separate panels remember which marker a user selected. New markers can be inserted before the selected marker or appended after it. What identity should the panels retain: an address, a position, or a separate stable identifier? Explain what changes under each edit before choosing the representation.

Practise

The lab counts capacity changes on vectors it hands you, shows an old address going stale without reading through it, has you finish a small growing container and count its transfers at several sizes, and compares copying, moving and building in place. Its final challenge is a different storage problem with a strict budget of writes. Everything is graded by counting operations, never by timing.

Recap

You can now: distinguish live elements from spare storage, explain relocation, and choose when to reserve or reacquire a borrow.

Invariant: the owned allocation contains a live ordered prefix of size elements, with size at most capacity.

Complexity achieved: with doubling, any $n\ge 2$ appends transfer at most $2n-3$ old elements in the constant-cost element model, so appending is amortized constant; a single relocating append is linear in the current size.

Failure mode: reserve is mistaken for resize, exact-fit growth repeats transfers, or an address survives in a variable after its element was invalidated.

In real software: the standard promises amortized constant push_back and the invalidation rules, and names no growth factor. libc++ 21.1.4 doubles in vector::__recommend, and decides between moving and copying old elements when it relocates them.

Retrieval: from module 8: after auto archive = std::move(editor); on a std::unique_ptr, what does editor hold, and who destroys the document?

Check yourself

1. What is wrong with “every append takes constant time” even when total work is linear?
2. Which borrowers can remain valid after an append with spare capacity, and which cannot?
3. Why does a potentially throwing move not imply that a vector can never move the element?

Original SciMigo course material. C++ examples target C++17.