the std::vector growth model

A std::vector is C++'s growable array: it stores its elements in a single contiguous block of memory, like a C array, but it can grow as you add elements. That raises an obvious puzzle: contiguous memory has a fixed size, so how can it grow? The answer is that when it runs out of room, it quietly allocates a bigger block, moves the existing elements over, and frees the old one — and the clever part is how often it does this, because doing it on every insertion would be ruinously slow.

Two quantities matter: size (how many elements you have) and capacity (how many it has room for before it must reallocate). When you push_back into a full vector, it does not grow by one — it grows its capacity by a multiplicative factor (commonly doubling, sometimes 1.5x), allocates that larger buffer, moves or copies the elements across, and frees the old buffer. Because the buffer size grows geometrically, the expensive reallocations happen exponentially less often as the vector gets bigger, so the total cost of n push_backs is proportional to n, not n-squared. We say each push_back is amortized constant time: most are a cheap write into spare capacity, and the occasional reallocation, averaged out, adds only a constant per element.

Why it matters: contiguity makes std::vector cache-friendly and as fast to iterate as a raw array, while geometric growth makes appending cheap on average — it is the default container for good reason. The honest consequences of the model are important: a reallocation invalidates all pointers, references, and iterators into the vector (they point into the old, freed buffer), so holding a reference across a push_back is a bug; the amortized-constant cost hides occasional large worst-case spikes (one push_back may move a million elements), which matters for real-time code; and you can avoid the reallocations entirely by calling reserve(n) up front when you know the size, turning many allocations into one.