Under the Hood

Alex Stepanov — the creator of the STL — had a simple litmus test for any programming language: Look at how it implements swap. Three lines. The simplest function imaginable. But what C++ lets those three lines become is a beautiful piece of engineering. The test: a smooth gradient of implementations Stepanov’s point was not about swap itself. It was about generic programming. You define what swap means — exchange the values of two objects. Then you ask the language: can you give me a smooth gradient of implementations, from the most generic to the most specialized, without losing efficiency at any level? ...

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. ...