The Amortized Bargain
You call push_back() a thousand times. As Gracjan Olbinski’s breakdown on isocpp.org notes, the vector reallocates roughly ten times. The math behind that number is the first mechanism, and it is worth understanding precisely.
std::vector grows exponentially, not linearly. Each time the current capacity is exhausted, the implementation allocates a new, larger buffer, moves all existing elements into it, and releases the old one. With a growth factor of 2, a vector starting at capacity 1 follows the sequence: 1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024. Ten reallocations to hold a thousand elements.
The amortized cost argument is a classic application of the potential method. Assign each element a credit of 2 units when it is first inserted. One credit pays for the insertion itself; the other is saved. When a reallocation doubles the capacity, every element that existed before the reallocation still holds its saved credit, which pays for its own move. Total work across all insertions: O(n). Cost per insertion: amortized O(1).
The C++ standard mandates this behavior in its sequence container requirements: push_back must run in amortized constant time. The standard does not specify the growth factor, leaving it to each implementation.
Why the Growth Factor Is Not Arbitrary
GCC’s libstdc++ and Clang’s libc++ both use a factor of 2. MSVC’s STL uses 1.5. The difference has a concrete effect on memory reuse that becomes visible at scale.
With a factor of 2, the sequence of allocation sizes is: 1, 2, 4, 8, 16, 32. By the time the vector needs to allocate 32 bytes, it has freed allocations totaling 1 + 2 + 4 + 8 + 16 = 31 bytes. That sum is always one short of the next required size. A memory allocator tracking freed blocks cannot satisfy the next allocation from previously freed memory, because the cumulative freed size never catches up to the next required size. Memory usage grows monotonically with a factor-of-2 strategy.
With a factor smaller than 2, the series converges differently. Growth factors below 2 let the cumulative freed memory eventually exceed the size of the next allocation, making it theoretically possible for an allocator to reuse that freed memory. MSVC’s choice of 1.5 reflects this reasoning. Whether any real allocator takes advantage of this depends on the allocator implementation and usage pattern, but the headroom exists with 1.5 where it provably never exists with 2.
The trade-off is reallocation frequency. A factor of 1.5 means more reallocations than 2 for the same sequence of inserts. You can observe this directly:
#include <vector>
#include <iostream>
int main() {
std::vector<int> v;
size_t last_cap = 0;
int reallocs = 0;
for (int i = 0; i < 1000; ++i) {
v.push_back(i);
if (v.capacity() != last_cap) {
std::cout << "capacity: " << v.capacity() << "\n";
last_cap = v.capacity();
++reallocs;
}
}
std::cout << "reallocs: " << reallocs << "\n";
}On GCC with libstdc++, the capacity sequence hits: 1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024. Ten reallocations. On MSVC, the 1.5x factor produces a longer sequence with smaller jumps: 1, 2, 3, 4, 6, 9, 13, 19, 28, 42, 63, 94, 141, 211, 316, 474, 711, 1066. Seventeen reallocations for the same thousand-element sequence, but smaller peak allocations at each step.
For workloads that build a vector once and then read it for a long time, 1.5 reduces peak memory overhead. For workloads that insert continuously, 1.5 increases the reallocation cost. Neither factor is universally correct; they encode different priorities.
Contiguity as a Performance Baseline
std::vector stores its elements in a single contiguous allocation. The performance consequences of this are significant enough that most of C++‘s container ecosystem is defined in relation to it.
Modern CPUs access memory in cache lines, typically 64 bytes. When you read one element of a vector<int>, the CPU loads a 64-byte chunk containing fifteen adjacent int values alongside it. Sequential iteration over a vector hits every loaded cache line fully and benefits from hardware prefetching: the CPU recognizes the sequential access pattern and loads the next cache line before the code asks for it.
std::list provides no such guarantee. List nodes are scattered across heap allocations wherever the allocator found free space. Each traversal step is a pointer dereference into an unpredictable address. Cache misses accumulate. For large collections with sequential access patterns, the difference between vector and list is often an order of magnitude in wall-clock time, even though both are O(n) for traversal. Bjarne Stroustrup has made this point repeatedly in his FAQ and public talks, noting that the overhead of pointer indirection in linked structures makes them practical only in specialized cases like frequent mid-sequence insertion where iterator stability is required.
std::deque stores elements in fixed-size chunks and maintains a pointer map to those chunks. Sequential access still involves indirect jumps between chunk boundaries. Better than list, but the contiguity guarantee is partial.
The contiguity of std::vector is what makes the amortized reallocation cost worthwhile. Paying O(n) up front at each reallocation step produces a layout that O(n) sequential reads can exploit fully. Fine-grained allocation through a linked structure avoids reallocation entirely but forfeits the cache behavior on every subsequent access.
The noexcept Trap
This is the mechanism most likely to cause unexpected behavior in production, and the one least likely to be caught by testing because it fires only during reallocation.
During reallocation, std::vector must move all existing elements into the new buffer while maintaining the strong exception guarantee: the operation must either succeed completely or leave the vector in its original state. If an exception is thrown partway through the move, the vector cannot leave elements half-moved; it must be restorable to its pre-reallocation state.
Move constructors can, in principle, throw. If the move of element k throws after elements 0 through k-1 have already been moved to the new buffer, those elements cannot be moved back. Their original slots hold moved-from objects in an unspecified state. Restoring the vector would require moving them back, which might also throw. The strong guarantee is unachievable with throwing moves.
The solution in the standard is std::move_if_noexcept. During reallocation, if an element’s move constructor is marked noexcept, the vector moves it. If the move constructor can throw, and the type is copyable, the vector copies it instead. Copies preserve the original; if a copy throws, the original elements are still intact and the operation fails cleanly.
The detection mechanism is std::is_nothrow_move_constructible_v<T>. If this trait returns false and the type has a copy constructor, every reallocation silently copies all elements rather than moving them.
struct WithoutNoexcept {
std::vector<int> data;
// No noexcept: vector will COPY this type during reallocation.
WithoutNoexcept(WithoutNoexcept&& other) : data(std::move(other.data)) {}
WithoutNoexcept(const WithoutNoexcept& other) : data(other.data) {
std::cout << "copied during reallocation\n";
}
};
struct WithNoexcept {
std::vector<int> data;
// noexcept: vector will MOVE this type during reallocation.
WithNoexcept(WithNoexcept&& other) noexcept : data(std::move(other.data)) {}
WithNoexcept(const WithNoexcept& other) : data(other.data) {
std::cout << "copied during reallocation\n";
}
};
int main() {
std::vector<WithoutNoexcept> a;
for (int i = 0; i < 10; ++i) a.push_back(WithoutNoexcept{});
// Prints "copied during reallocation" multiple times
std::vector<WithNoexcept> b;
for (int i = 0; i < 10; ++i) b.push_back(WithNoexcept{});
// Prints nothing: moves are used
}For types like std::string or std::unique_ptr, where the move constructor is implicitly noexcept, this is handled automatically. For custom types that manage resources manually, forgetting noexcept on the move constructor is a silent performance regression that appears only during reallocation, which happens infrequently enough that profiling often misses it entirely.
The compiler-generated move constructor for a class is noexcept if and only if all base classes and members have noexcept move constructors. For a class wrapping standard library types, the default is usually correct. For a class with manual heap ownership or a resource handle, the noexcept annotation must be added explicitly.
Clang-Tidy includes a check for this: performance-noexcept-move-constructor. Running it on an existing codebase occasionally surfaces types that have been silently copying on reallocation for years without anyone noticing, since the behavior is functionally correct and only shows up as a latency anomaly during insert-heavy workloads.
What reserve() Changes
All four mechanisms interact with reserve(). Calling v.reserve(n) before a series of insertions pre-allocates capacity for at least n elements, preventing any reallocation below that threshold. It does not change size(). Elements in the reserved region are not constructed; the capacity is simply available.
For cases where the final size is known or can be estimated, reserve() eliminates the amortized reallocation cost entirely. It also sidesteps the growth factor debate and avoids the noexcept issue, since no reallocation occurs during the subsequent push_backs.
std::vector<MyType> v;
v.reserve(1000); // One allocation; no copies or moves during the following inserts
for (int i = 0; i < 1000; ++i) {
v.emplace_back(i);
}shrink_to_fit() does the inverse, requesting that the implementation reduce capacity() to match size(). The standard marks this as a non-binding request, but most implementations honor it. It triggers a reallocation and a move of all elements, so the noexcept behavior applies here as well: a type without a noexcept move constructor will have all its elements copied on shrink_to_fit(), not moved.
The four mechanisms described in Olbinski’s article are worth understanding together because they interact. The growth factor determines how often the noexcept behavior fires. Contiguity is what makes the amortized reallocation cost worth paying, because the resulting layout is cache-friendly in a way that fine-grained allocation cannot match. Knowing each mechanism in isolation is useful; understanding how they compose is what informs concrete decisions about when to use reserve(), when to annotate move constructors with noexcept, and when to reach for a different container.