Does a std::vector hold only the exact number of elements it needs or extra space?

Question

So the standard says that a vector holds all of its elements in a continuous array of memory. Further, a std::vector will resize whenever it needs to be resized, up or down. Re-sizing and maintaining all of your memory in one continuous block means you need to maloc new memory of the new size then copy all of your data over to it -> O(n).

My understanding was that the standard solved this problem much like how hashtables solve collisions by re-sizing when a certain percent of its buckets were full. IE a vector when initialized will grab enough memory so that it can add items to the vector without having to expand to a larger array and then copy all of its data over until after enough calls it will resize yet again. Is this the case? When does the vector actually grab more memory/resize and then copy its elements over and how does it maintain the run times mentioned in Questions About Running time if it is resizing each push and erase?

Answer 1

The vector does not reallocate the contiguous area of memory it uses for its value every time a value is added or removed from the vector. A typical implementation of a vector grows the actual allocated memory for the vector by a factor of two when needed; and does not release the allocated space when the vector shrinks.

There's a std::vector method called reserve(). It does not change the actual size of the vector, the vector still contains the same number of elements, but it "reserves" the vector so that it can grow to hold up to the given number of elements, without actually resizing. So, if the vector currently has eight elements, reserve(12) grows the vector large enough so that no resizing will be needed if four additional elements are added to the vector (it's allowed to reserve even more space, if it feels like it, you're only guaranteed that the vector can grow to size 12 without resizing).

The std::vector automatically uses reserve() whenever the vector actually needs more space; as I mentioned typically by doubling the allocated space for the vector. So, if the vector has eight elements, and no more available space, the next attempt to insert an element reserves the vector for 16 values, before actually inserting a new value.

Because the vector's size growth logarithmically, and only occasionally, when there's a need for it, it can be shown that the complexity of insertion of a single value into a vector is constant amortized time.