I understand that std::vector::push_back() is amortized O(1) because reallocations happen only occasionally. If I already know the approximate number of elements, I can call reserve(), for example reserve(1'000'000), and avoid repeated growth while inserting.
After that reservation, what work does each push_back() still perform? For a vector, is it essentially just constructing or copying the value into the next available slot and incrementing the size, or can the abstraction add noticeable overhead compared with writing directly into an already allocated array?
How do element type, copying versus move construction, cache behavior, cold memory pages, and exception-safety requirements affect the cost? Also, how different should the generated code and performance be at -O0 compared with -O2 or -O3? I'm interested in understanding the real constant costs rather than only the Big-O classification, ideally with a benchmark or compiler-generated assembly example.
3 Answers
For a vector, optimized code often has little or no meaningful abstraction penalty over a raw buffer. At -O0, the compiler generally emits much more literal code: repeated loads and stores of the vector’s pointer, size, and capacity, plus function-call overhead if the operation is not inlined. At -O2 or -O3, push_back() is usually inlined, the size update can be kept in a register, and bounds or capacity checks may be simplified or removed when the compiler can prove that reserve() is sufficient.
The useful benchmark is to compare reserved push_back(), writes into a correctly constructed pre-sized vector, and raw-array writes for both int and a larger nontrivial type. Use the results from an optimized build and inspect the assembly. Cache misses, memory bandwidth, object construction, and later destruction often matter much more than the increment of vector’s size.
After a successful reserve(), a push_back() normally constructs the new element in the unused storage and increments the vector’s size. For int, that can compile down to a store plus a pointer or size update. With optimization enabled, the size may stay in a register and the loop can become nearly identical to a hand-written array loop.
The difference becomes more important for nontrivial types: constructing, copying, moving, and eventually destroying the object can dominate the bookkeeping. push_back() also has to preserve vector’s invariants and support exception-safe behavior, although much of that is optimized away when the type and surrounding code make it unnecessary.
So for a simple type like int, the main practical differences are probably memory access and construction rather than the size counter itself?
Amortized O(1) only says that growth does not become increasingly expensive over a long sequence. It does not mean every call has zero overhead. Even after reserve(), each insertion still writes to memory, and the destination may be cold in the cache or backed by pages that have not yet been physically touched. The first write to each such page can incur a page fault, which may make a run look like push_back() is slow even though the vector operation is not the real cause.
Comparing push_back() with indexed assignment is only fair if both use the same allocation and construction strategy. For example, resize() creates one million existing elements, while reserve() only obtains uninitialized storage; those choices can touch memory at different times.
That explains why the first pass can behave differently from later passes. The reserved address range may exist, but the operating system still brings pages into physical memory as they are touched.
So a benchmark at -O0 mostly measures unoptimized implementation details, while -O2 or -O3 is more representative of whether vector’s abstraction survives optimization.