I understand that std::vector::push_back() is amortized O(1) because occasional reallocations are spread across many insertions. If I already know the approximate size and call reserve(1'000'000), repeated reallocations should not occur. In that case, what work does each push_back() still perform? Is it essentially placement of the new element followed by incrementing the size, or can it be noticeably more expensive than writing directly into an allocated array? How do element construction, copying or moving, cache behavior, and page faults affect the cost? Also, how different are the results at -O0 compared with -O2 or -O3? I'm interested in the practical machine-level cost rather than just the asymptotic complexity.
4 Answers
With enough capacity, push_back() normally has a very small fixed cost: it checks that capacity remains, constructs or moves the element into the next uninitialized slot, and increments the vector’s size. For an int or another trivial type, an optimized compiler can often keep the size in a register and reduce the loop to something almost identical to indexed writes. With a nontrivial type, construction, copying or moving, and eventual destruction can dominate the bookkeeping. reserve() prevents growth reallocations, but it does not make element construction free.
Big-O does not describe the constant cost of each operation, so a linear loop can still spend most of its time in a cheap O(1) operation when it does little else. Cache and memory behavior often matter more than incrementing the size counter. The first write to a memory page can cause a page fault or cache miss, and those costs may show up next to push_back() in a profile even though they are really costs of touching newly allocated memory. The allocator and page-mapping behavior can also differ between reserve(), resize(), and other allocation patterns.
That explains why a benchmark can make push_back() look slow even when its own bookkeeping is minimal: the loop may be paying for cold pages and cache misses as it reaches new memory.
Direct indexed assignment is not always an equivalent comparison. If you resize the vector first, every element already exists and v[i] = value performs assignment. push_back() instead constructs a new element in uninitialized storage, which may call a constructor or move constructor. For ints, the difference after optimization is often tiny; for a large struct or a type with expensive constructors, the object operation is the real cost. If you want to compare fairly, compare push_back() with placement construction or with writes into storage having the same object-lifetime semantics.
Optimization level makes a major difference. At -O0, the compiler usually emits explicit loads and stores for the vector object, size, and capacity checks, so the abstraction can look much more expensive. At -O2 or -O3, inlining, constant propagation, register allocation, and loop optimizations can eliminate or hide much of that overhead. The best test is to benchmark optimized builds, prevent the result from being optimized away, use representative types, and inspect the generated assembly. For a reserved vector of ints, optimized push_back() will often be very close to a raw sequential store, while the difference can remain meaningful for nontrivial types or poorly optimized code.
So the important distinction is that reserve() allocates raw capacity, while push_back() still starts the lifetime of an object in each slot. For trivial types that may be nearly free, but for larger or more complicated objects it can be substantial.