std::vector in C++: size, capacity, erase and reallocation

std::vector<T> is C++’s growable array: for any T but bool, its elements sit in one contiguous block, size() is how many it holds and capacity() how many fit. push_back is amortized constant time, but on a full vector it allocates a larger block, moves or copies every element into it and frees the old one, invalidating every iterator, pointer and reference into the vector. Call reserve(n) when you know the count, give the element type a noexcept move constructor so growth moves instead of copying, and remove elements with std::erase or std::erase_if (C++20).

This answer is written for C++17. What came after:

• C++20 adds std::erase, std::erase_if and the signed std::ssize, and makes the members constexpr.
• C++23 adds std::ranges::contains, the members append_range, insert_range and assign_range, and the std::from_range constructor; all four compilers below accepted contains, append_range and from_range in C++23 mode, MSVC with /std:c++23preview.
• C++26 adds std::inplace_vector, a vector of fixed capacity (its first releases), and makes the preconditions of operator[], front, back and pop_back hardened.

Four compilers on three standard libraries built the samples, in C++17 mode unless a line names a later standard: MSVC 19.44 and Clang 19.1 on Microsoft’s STL (Windows x64), GCC 16.2 with libstdc++ and Clang 23.1 with libc++ (Compiler Explorer, Linux x86-64). Nothing was timed: the samples count capacities, allocations, copies and moves, and the growth, reserve(1000), copy-or-move and emplace_back counts were the same built without optimization and with -O2 (/O2 on MSVC).

What changed: elements are removed with v.erase(std::remove(v.begin(), v.end(), x), v.end()) std::erase(v, x).

since C++20

How a std::vector grows: size and capacity

This loop prints the capacity each time it changes over 1,000 push_backs of a sensor sample:

struct Sample {
    int sensor;
    double value;
};
// ...
std::vector<Sample> samples;
std::size_t capacity = samples.capacity();
std::printf("%zu", capacity);  // 0: no block yet
for (int i = 0; i < 1000; ++i) {
    samples.push_back({i, 20.5});
    if (samples.capacity() != capacity) {  // a new block
        capacity = samples.capacity();
        std::printf(" %zu", capacity);
    }
}

On Microsoft’s STL, with MSVC and with Clang 19.1, it printed:

0 1 2 3 4 6 9 13 19 28 42 63 94 141 211 316 474 711 1066
size 1000, capacity 1066

On libstdc++ (GCC 16.2) and libc++ (Clang 23.1):

0 1 2 4 8 16 32 64 128 256 512 1024
size 1000, capacity 1024

The standard requires push_back to take amortized constant time ([sequence.reqmts]) and names no growth factor: the sequences are each library’s. With one push_back at a time, Microsoft’s STL added half the capacity (at least one slot) and the other two doubled it.

libstdc++ and libc++ part when one call adds several elements: an insert of 9 into 8 elements with a capacity of 16 left a capacity of 17 on libstdc++, 32 on libc++ and 24 on Microsoft’s STL. libstdc++ sizes the new block from size(), libc++ from capacity().

Each new block is a reallocation, and a pointer taken before it still holds the old address:

What a reallocation costs, and what reserve saves

Tracked wraps an int, and its copy constructor and noexcept move constructor count their calls; 1,000 of them were pushed without and with a reserve(1000) first:

std::vector<Tracked> samples;
if (reserve_first) {
    samples.reserve(1000);
    ++allocations;
}
for (int i = 0; i < 1000; ++i) {
    std::size_t before = samples.capacity();
    samples.push_back(Tracked(i));
    if (samples.capacity() != before)
        ++allocations;
}

A second program called samples.reserve(samples.size() + 1) before each push_back. The counts, where a block is a change of capacity():

In every row, 1,000 moves are the Tracked(i) temporaries moved into place. The rest is growth, where each reallocation moved the old capacity’s worth: 1 + 2 + 4 + … + 512 = 1,023 on libstdc++ and libc++, 1 + 2 + 3 + 4 + 6 + … + 711 = 2,137 on Microsoft’s STL. A reserve before every push_back is the misuse cppreference’s reserve page warns about: the capacity grows linearly, and here 1,000 allocations moved 499,500 elements. For the same reason, a function that receives a vector by reference should usually not call reserve on it.

reserve also buys stable addresses: after it, no insertion reallocates until the size would pass capacity() ([vector.capacity]), so until then a push_back invalidates no pointer or reference to an element already there.

clang-tidy’s performance-inefficient-vector-operation (19.1.5, from Visual Studio) flags a plain push_back loop with no reserve before it; clang-tidy and the other analyzers are on Toolchain.

When a growing std::vector copies instead of moving

When push_back reallocated, all three libraries moved the elements if their move constructor was noexcept or they could not be copied, and copied them otherwise. The reason is a promise in [vector.modifiers]: if an exception is thrown while inserting a single element at the end “and T is Cpp17CopyInsertable or is_nothrow_move_constructible_v<T> is true, there are no effects.” Four element types were pushed 1,000 times each; the first two differ by one word:

struct NothrowMove {
    NothrowMove() = default;
    NothrowMove(const NothrowMove&) { ++copies; }
    NothrowMove(NothrowMove&&) noexcept { ++moves; }
};
struct ThrowingMove {
    ThrowingMove() = default;
    ThrowingMove(const ThrowingMove&) { ++copies; }
    ThrowingMove(ThrowingMove&&) { ++moves; }  // may throw
};

What push_back growth did, counted as the totals without reserve minus those with reserve(1000):

A move-only type is moved even when its move may throw; if that move throws, the standard leaves the effects unspecified. The promise covers a single element at the end. Each call below reallocated a vector of 8 ThrowingMove elements in a block of 8 (16 for shrink_to_fit), and the counts include the new elements’ own: the move of T(), the four copies of t.

An insert or emplace before the end promises less, and there Microsoft’s STL moved the elements anyway. Mark the move constructor noexcept when it cannot throw: when to mark a move constructor noexcept has the rules and the static_assert that checks it.

What each std::vector member invalidates

A call that reallocates invalidates every iterator, pointer and reference into the vector, end() included. This program shows the block changing under a push_back; it compares data() as an integer and never reads through an old pointer:

// The block's address as a number: compared, never dereferenced.
std::uintptr_t block(const std::vector<Sample>& samples) {
    return reinterpret_cast<std::uintptr_t>(samples.data());
}
// ...
std::uintptr_t before = block(samples);
samples.push_back({4, 21.0});  // full: a new block
std::printf("push_back on a full vector: %s, capacity %zu\n",
            block(samples) == before ? "same block" : "new block",
            samples.capacity());
before = block(samples);
samples.push_back({5, 21.5});  // room left

From four elements in a capacity of 4, libstdc++ and libc++ printed this; Microsoft’s STL printed a capacity of 6 on both lines:

size 4, capacity 4
push_back on a full vector: new block, capacity 8
push_back with room left:   same block, capacity 8

The same test on the other members, each from 8 elements in a capacity of 16, beside the complexity and invalidation rules of the standard and cppreference’s std::vector page:

The std::vector member for each job

std::find, std::find_if, std::sort, std::remove and std::ranges::contains are in <algorithm>; std::erase and std::erase_if for a vector are in <vector>. Finding a sample by its sensor:

auto it = std::find_if(
    samples.begin(), samples.end(),
    [](const Sample& s) { return s.sensor == 4; });
if (it != samples.end())
    std::cout << "sensor 4: " << it->value << '\n';
// ...
auto found = std::ranges::find(samples, 2, &Sample::sensor);  // C++20

It printed sensor 4: 21 and, in C++20 mode, sensor 2: 19.5 on all four. Find, sort, insert, resize and the ends on four readings:

std::vector<double> readings{3.5, 1.5, 2.5, 4.0};
std::printf("size: %zu\n", readings.size());  // the length
auto it = std::find(readings.begin(), readings.end(), 2.5);
if (it != readings.end())
    std::printf("found 2.5 at index %td\n", it - readings.begin());
std::sort(readings.begin(), readings.end());
print("sort:", readings);
readings.insert(readings.begin() + 1, 2.0);
print("insert:", readings);
readings.resize(7);  // new elements are 0.0
print("resize(7):", readings);
std::printf("front %.1f, back %.1f\n", readings.front(),
            readings.back());
readings.pop_back();
print("pop_back:", readings);

All four printed:

size: 4
found 2.5 at index 2
sort:        1.5 2.5 3.5 4.0
insert:      1.5 2.0 2.5 3.5 4.0
resize(7):   1.5 2.0 2.5 3.5 4.0 0.0 0.0
front 1.5, back 0.0
pop_back:    1.5 2.0 2.5 3.5 4.0 0.0

Remove elements: std::erase, std::erase_if and the erase-remove idiom

Because erase returns the next position, a loop that erases as it goes continues from it:

for (auto it = samples.begin(); it != samples.end();) {
    if (it->value < 0.0)         // a failed reading
        it = samples.erase(it);  // the element after it
    else
        ++it;
}

It kept sensors 1 and 4 of five on all four compilers. Each erase assigns every later element one place forward ([vector.modifiers]), so the loop is quadratic in the worst case where std::erase_if is one pass: keep the loop for when each erased element needs work of its own. The C++20 calls:

std::vector<double> readings{1.5, 0.0, 2.5, 0.0, 4.5, 3.0};
std::size_t dropped = std::erase(readings, 0.0);  // C++20
std::size_t hot = std::erase_if(readings,         // C++20
                                [](double r) { return r > 4.0; });

They returned 2 and 1 and left 1.5 2.5 3.0 on all four. In C++17 mode all four rejected both (GCC: 'erase' is not a member of 'std'), and the erase-remove idiom does the same in two steps:

auto first = std::remove(readings.begin(), readings.end(), 0.0);
auto dropped = readings.end() - first;  // how many go
readings.erase(first, readings.end());
readings.erase(std::remove_if(readings.begin(), readings.end(),
                              [](double r) { return r > 4.0; }),
               readings.end());

It left the same three readings.

push_back or emplace_back

emplace_back builds the element in place from constructor arguments; push_back takes a finished one. A Tracked built from a sensor id and a reading, counting its copies and moves, was added six ways to a vector with room reserved. All four printed:

push_back(s)                    copies 1, moves 0
emplace_back(s)                 copies 1, moves 0
push_back(Tracked(2, 21.0))     copies 0, moves 1
emplace_back(Tracked(2, 21.0))  copies 0, moves 1
push_back({3, 21.5})            copies 0, moves 1
emplace_back(3, 21.5)           copies 0, moves 0

For an lvalue and for a temporary the two do the same work; emplace_back saves the move only when it receives the constructor’s arguments. clang-tidy 19.1.5’s modernize-use-emplace flagged the three calls that pass a Tracked or braces, and --fix rewrote each to pass the constructor’s arguments.

• emplace_back returns a reference to the new element since C++17: double& added = readings.emplace_back(2.5); built in C++17 mode on all four and failed in C++14 mode.
• On an aggregate such as Sample, which declares no constructor, samples.emplace_back(2, 21.0) needs C++20, which initializes aggregates from parentheses (P0960R3). All four rejected it in C++17 mode (MSVC: C2661: 'Sample::Sample': no overloaded function takes 2 arguments); samples.push_back({1, 20.5}) builds in both.

emplace_back also calls explicit constructors, which push_back does not:

std::vector<std::vector<double>> rows;
rows.emplace_back(10);  // calls the explicit vector(size_type)

All four printed rows: 1, rows[0].size(): 10: one row of ten elements, where rows.push_back(10) does not compile on any of them. Only MSVC’s note says why: the constructor “is declared ‘explicit’”.

v[i] or at(), braces, and std::vector<bool>

v[i] with i >= size() is undefined behavior through C++23. C++26 makes n < size() a hardened precondition of operator[] (P3471R4): a contract violation on a hardened implementation, undefined behavior otherwise. front(), back() and pop_back() on an empty vector are undefined behavior too, and C++26 makes “a.empty() is false” a hardened precondition of each. None of the three libraries tested defines __cpp_lib_hardened_vector, even in C++26 mode; the switches that turn on each library’s own checks are tested, on a span, in does std::span check bounds.

at(i) throws std::out_of_range when i >= size(), with each library’s own what(), so catch the type:

Declarations that read alike, and what std::vector<bool> does differently:

All four agreed on every row. b differs from a because list-initialization tries the std::initializer_list constructors first ([over.match.list]). The standard does not require std::vector<bool> to store an array of bool and recommends bits instead ([vector.bool.pspc]); libstdc++ declares void data() = delete;, and the other two libraries have no data() at all.

Passing a vector, and when not to use one

The Core Guidelines’ SL.con.2 makes std::vector the default container “unless you have a reason to use a different container”. The reasons:

Why a read-only parameter is a reference and a returned vector a value is in pass by value or const reference. std::inplace_vector never grows past its capacity:

std::inplace_vector<double, 4> window;  // C++26: 4 slots, no heap
for (double r : {3.5, 1.5, 2.5, 4.0})
    window.push_back(r);
if (!window.try_push_back(3.0))  // full: no throw
    std::printf("try_push_back: full\n");
try {
    window.push_back(3.0);  // full: throws
} catch (const std::bad_alloc&) {
    std::printf("push_back: std::bad_alloc\n");
}

GCC 16.2 in C++26 mode printed both lines. MSVC 19.44, Clang 19.1 on Microsoft’s STL and Clang 23.1 with libc++ have no <inplace_vector> (MSVC: fatal error C1083).

Before you ship code that grows a vector:

1. reserve(n) once, before the loop, when you know n; not reserve(size() + 1) before each push_back.
2. A noexcept move constructor on a copyable element type, or each reallocation by push_back, emplace_back, reserve or resize copies it.
3. After a call that may reallocate, take iterators, pointers and references again, and after an insert or erase those at or after its position; in an erase loop, it = v.erase(it).
4. std::erase or std::erase_if (C++20) to remove by value or by condition; the erase-remove idiom before C++20.
5. at(i) where an index may be out of range: v[i] there is undefined behavior.

More answers about what code costs are in Performance.