skip to content

Vectors and Arrays

std::vector grows geometrically, reserve avoids reallocation, and std::array lives inline. Interviewers ask what push_back costs and why vector is the default container.

on this pageshow

explore

questions

6

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()
open as a page

In C++, what does std::array give you over a built-in C array, and how does it differ from std::vector?

level: juniorimportance: must knowfreq 68%

basics

~20 s

std::array<T, N> wraps a fixed-size C array: it does not decay to a pointer, can be copied and returned, and offers size(), at() and iterators. Unlike std::vector, its size is fixed at compile time and its elements live inline.

open as a page

In C++, what do std::vector's reserve, resize and shrink_to_fit each change, and when does reserving before a loop pay off?

level: middleimportance: must knowfreq 70%

basics

~20 s

reserve(n) raises capacity to at least n without creating elements; resize(n) changes size, constructing or destroying elements; shrink_to_fit asks, without obligation, to drop unused capacity. Reserve before a loop whose final count you know, so the loop never reallocates.

open as a page

In C++, how does std::vector::emplace_back differ from push_back, and when is emplace_back no faster or even riskier?

level: middleimportance: should knowfreq 62%

basics

~20 s

push_back takes an element-type object, building a temporary if needed and moving it in; emplace_back forwards arguments to a constructor and builds the element in place. With an existing object they do the same work, and emplace_back can call explicit constructors.

open as a page

In C++, why can worker threads writing different indices of a std::vector<bool> still race, and what else makes it unlike other vectors?

level: seniorimportance: should knowfreq 45%

basics

~20 s

std::vector<bool> is a specialization that packs flags into bits, so operator[] returns a proxy object instead of bool&. Neighbouring flags share a word, so concurrent writes to different indices can race, and bool&, bool* and data() are unavailable.

open as a page

As a C++ lead, would you make std::vector the default container in your guidelines, and which exceptions would you write into that rule?

level: principalimportance: should knowfreq 40%

basics

~20 s

Yes: std::vector is contiguous, cache-friendly and simple, so it should be the default sequence. Write exceptions for fixed sizes (std::array, C++26 std::inplace_vector), stable element addresses, front insertion, keyed lookup and packed bools, each backed by a stated reason or a measurement.

open as a page