std::vector — Four Mechanisms Behind Every push_back()
You have called push_back() a thousand times. But do you know how many times your vector actually reallocated memory to make that happen? Not a thousand. Not even close. About ten. Behind that simple interface, four mechanisms are working together — each one invisible during normal use, each one shaping your performance in ways that push_back() will never tell you about. Exponential growth and amortized O(1) When a vector runs out of capacity, it does not grow by one element. It allocates a new block that is some multiple of the current capacity, copies (or moves) everything over, and frees the old block. ...