The article suggests that an std::vector allocates just barely enough memory to hold its elements. No real implementation (from GNU, clang or MSoft) works that

The article suggests that an std::vector allocates just barely enough memory to hold its elements. No real implementation (from GNU, clang or MSoft) works that way, because it would make a loop like for (const auto& value : some_container) my_vector.push_back(value); quadratic in the number of elements. To get linear time, when a reallocation occurs extra memory has to be allocated; we might double the allocated storage each time, or use Fibonacci numbers and get about a 1.6 ratio. An early implementation of Microsoft Foundation Classes (pre-STL) had this bug: repeatedly appending one character at a time to a string had quadratic cost, because they got this wrong. I used to include a version of this as an interview question: how do you grow a dynamically allocated buffer, and what happens if you do it wrong. It's true that if you know exactly how many elements you need you can reserve that space in one call. But doing this wrong (always allocating exactly what you need, no spare capacity) can sometimes increase the number of allocations you need.