skip to content

In C++, what is the difference between std::vector's size() and capacity(), and what does push_back cost as the vector grows?

level: juniorimportance: must knowfreq 80%

answer

  1. elements held vs room allocated
  2. full buffer means a new block
  3. every element moves across
  4. growth by a factor, cost averaged

basics

~20 s

size() is how many elements a std::vector holds; capacity() is how many fit in its current allocation. push_back is amortized constant: when size reaches capacity it allocates a larger block, transfers every element, then appends.

solid answer

~40 s

`size()` counts the live elements; `capacity()` counts the slots in the current heap block, and `size() <= capacity()` always holds. While there is spare capacity, `push_back` constructs the new element in the next slot in constant time. When the block is full, the vector allocates a larger one, moves or copies every element across, destroys the old elements and frees the old block, which is linear in `size()`. Because the new capacity is a multiple of the old one, those linear steps become rarer as the vector grows, so the standard can promise **amortized constant** time for `push_back`. The multiplier itself is not in the standard: libc++ and libstdc++ both double for single appends, but that is their choice. `clear()` empties the vector and, in both of those libraries, keeps the buffer.

code

cpp · 21 lines
cpp
#include <cstdio>
#include <vector>

struct Particle { float x, y, vx, vy; };

int main() {
    std::vector<Particle> particles;
    std::size_t last = particles.capacity();
    std::printf("start: size=%zu capacity=%zu\n", particles.size(), last);
    for (int i = 0; i < 100; ++i) {
        particles.push_back({0.f, 0.f, 1.f, 1.f});
        if (particles.capacity() != last) {
            last = particles.capacity();
            std::printf("size=%zu -> capacity=%zu\n", particles.size(), last);
        }
    }
    particles.clear();
    std::printf("after clear: size=%zu capacity=%zu\n", particles.size(), particles.capacity());
    particles.shrink_to_fit();
    std::printf("after shrink_to_fit: size=%zu capacity=%zu\n", particles.size(), particles.capacity());
}

go deeper

for a junior

Define size and capacity in one sentence each, say push_back is amortized constant, and describe the full-buffer path: allocate a bigger block, transfer, free the old one.

for a middle

Explain why geometric growth gives amortized constant cost, using the 1 + 2 + 4 + ... < n sum, and why growing by a fixed number of slots would make filling quadratic.

for a senior

Tie reallocation to production symptoms: frame-time spikes when a buffer crosses a capacity boundary, memory held at its high-water mark after a burst, and pointers into the old block dangling.

for a principal

Treat growth as a memory-versus-latency trade: a vector keeps its high-water mark, so decide where buffers are reused across frames, where they are pre-sized, and where memory is handed back.

## Two numbers describe every vector A `std::vector<T>` owns one contiguous heap block. Two member functions describe it: - **`size()`** is how many elements currently exist in the block: live, constructed objects. - **`capacity()`** is how many elements the block can hold before the vector must allocate a new one. The standard defines it as the total number of elements the vector can hold without requiring reallocation. - The invariant is `size() <= capacity()`. The slots between the two are raw storage with no objects in them, so reading or writing `v[size()]` is undefined behaviour even when the capacity is larger. In a particle system, `size()` is the number of live particles this frame, and `capacity()` is how many the current buffer can take before the next allocation. ## What one push_back does Each call to `push_back` (or `emplace_back`) takes one of two paths: 1. **Spare capacity** (`size() < capacity()`): the new element is constructed in the next free slot and `size()` grows by one. Constant time, no allocation. 2. **Full block** (`size() == capacity()`): the vector computes a larger capacity, allocates a new block, transfers the existing elements into it, constructs the new element, destroys the old elements and frees the old block. The transfer moves elements when their move constructor cannot throw and copies them otherwise; that rule belongs with move semantics. This path is linear in `size()`. The second path is also why pointers, references and iterators into the old block stop being valid after a reallocation; the material on iterator invalidation covers those rules. ## Why the average stays constant The standard does not promise that every `push_back` is cheap. It lists `push_back` among the sequence-container operations that take **amortized constant time**: averaged over a long run of calls, the cost per call is bounded by a constant. That promise is what pushes implementations to **geometric growth**. Suppose the capacity doubles whenever it runs out. Filling a vector to n elements then transfers 1 + 2 + 4 + ... + n/2 elements in total, which is less than n. Add the n constructions of the new elements and the whole run costs under 2n element operations, so the cost per call is constant on average. If the vector instead grew by a fixed number of slots, say 16 each time, it would reallocate about n/16 times and transfer roughly n squared over 32 elements in total: quadratic work, which breaks the guarantee. ## The growth factor is the implementation's choice | Library | New capacity when full (read from its source) | Capacities from empty, one push_back at a time | |---|---|---| | libc++ (LLVM) | the larger of `2 * capacity()` and the required size | 1, 2, 4, 8, 16, ... | | libstdc++ (GCC) | `size()` plus the larger of `size()` and the number of new elements | 1, 2, 4, 8, 16, ... | Both libraries happen to double for single appends; the standard names no factor at all. Code that assumes capacity is a power of two, or exactly twice the size, relies on one library's choice. Another standard library may use a different factor and still meet the amortized constant requirement, because any factor above 1 does. ## Operations that change size but not capacity - `clear()` destroys every element. The standard only requires the vector to be `empty()` afterwards; libc++ and libstdc++ both keep the buffer, so `capacity()` does not change. - `pop_back()` and `erase()` destroy elements and shift the tail down; they never reallocate. - `resize(n)` with a smaller n destroys the tail and keeps the buffer. - Memory goes back only through `shrink_to_fit()`, which is a non-binding request, through swapping with a fresh vector, or when the vector is destroyed. That retention is usually what a game loop wants: a particle buffer that grew to 10,000 slots during one explosion keeps those slots, so the next explosion allocates nothing. ## What to say in the interview Give the two definitions, the two paths of `push_back`, the phrase "amortized constant", and the point that the growth factor is an implementation detail. Strong answers add the cost model: an occasional linear-time transfer of the whole vector, which shows up in a frame-time graph as a spike when a particle burst crosses a capacity boundary. That spike is the problem `reserve` exists to solve.

  • Why can't a std::vector simply extend its current block in place when it fills up?
    The allocator interface offers `allocate` and `deallocate` but no operation that grows an existing block, so every growth means a new block plus an element-by-element transfer. That transfer runs each element's move or copy constructor, because a C++ object in general cannot be relocated by copying its bytes. Libraries may use a plain memory copy for types where that is known to be safe, but they still need the new block.
  • Does clear() release a std::vector's memory, and how do you actually give it back?
    `clear()` destroys the elements; the standard only requires the vector to be empty afterwards, and libc++ and libstdc++ both keep the buffer. To release it, call `shrink_to_fit()`, which is a non-binding request, or swap with an empty temporary: `std::vector<Particle>().swap(particles);`. The standard's `swap` exchanges contents and capacity, so the old block leaves with the temporary when it is destroyed.

A team that moves to an office twice the size whenever the current one fills up: each move is expensive and everyone's desk changes address, but moves become rarer as the team grows, so the moving cost per new hire stays small.

  • size() and capacity() are the same number; a vector allocates exactly what it holds
  • Every push_back reallocates and copies the whole vector
  • The C++ standard requires a vector to double its capacity when it runs out
  • clear() frees the vector's memory, so capacity() drops to zero
  • Writing v[size()] is fine as long as it is still below capacity()