Pointers and References to Vector Elements

When you add elements to a vector one at a time with push_back(), it can look as though the vector simply stretches to make room. Underneath, the vector is managing a block of memory. The question of how much memory it has set aside is separate from the question of how many elements it currently holds. This article is about that second question. Once you can tell the two apart, the behavior of growing a vector stops looking like magic.

The mechanisms that make growing a vector work are two names you should keep in mind: capacity(), which reports how much room the vector has, and reserve(), which makes room for more elements. The rest of this article shows how these two cooperate with push_back().

Think of the vector's memory as a row of slots. Size tells you how many slots hold real elements, counting from the front. Capacity tells you how many slots the vector has set aside in total. The difference between them is the reserved space that is still unused. That unused space is what lets the next few push_back() calls be cheap.

The rule that capacity is never smaller than size follows from what the two numbers mean. Size counts elements that are stored, and those elements must sit inside the block the vector has allocated. So the block can never hold fewer slots than the number of elements placed in it.

The source describes a growth rule for this model: an empty vector starts with capacity 8, and the capacity doubles after that. Using only that rule, we can trace what happens when we call push_back() repeatedly on an empty vector. The table below is a generated trace built from that rule.

Notice that the pattern of cheap calls punctuated by occasional expensive ones continues as the vector grows. Because the capacity doubles, the expensive calls become rarer as the number of elements increases. Each reallocation pays for the room that will serve many later calls.

The standard library's push_back() can be understood in terms of two operations: capacity() and reserve(). Its logic has a fixed order. First, push_back() asks whether there is room for one more element. Only if there is not does it call reserve() to make more. Then it places the new value into the next free slot. The check guards the whole operation, so the expensive path runs only when capacity is insufficient.

When this condition is true, there is no room for the new element, so reserve() is called. When it is false, the element goes straight into existing space. This is why most push_back() calls are cheap. The check itself does not allocate anything; it only compares two numbers.

Reallocation is where pointers and references to elements become a concern. Suppose you save a pointer to an element, then a push_back() forces the vector to allocate a bigger block. The elements are moved into that new block. The saved pointer still records the old location, and that location no longer holds the vector's elements. The source's description of the move, that the old block is no longer where the vector's elements live, is the reason this matters.

Because push_back() already grows the vector by doubling, calling reserve() is not required for correctness. It is useful when you know roughly how many elements you will add. Reserving that room up front means the allocation and move steps happen once, instead of at several growth points along the way.

Reserving is unnecessary when the vector will hold only a few elements, because the doubling rule already keeps reallocations rare. It is worth doing when the element count is known in advance and the cost of repeated moves would matter.