shrinking a vector

Question

Hi there,
I've got a problem with my terrain engine (using DirectX).

I'm using a vector to hold the vertices of a detail block. When the block increases in detail, so the vector does.

BUT, when the block decreases its detail, the vector doesn't shrink in size.

So, my question: is there a way to shrink the size of a vector? I did try this:

vertexvector.reserve(16);

Answer 1

The usual trick is to swap with an empty vector:

vector<vertex>(vertexvector.begin(), vertexvector.end()).swap(vertexvector);

Answer 2

If you pop elements from a vector, it does not free memory (because that would invalidate iterators into the container elements). You can copy the vector to a new vector, and then swap that with the original. That will then make it not waste space. The Swap has constant time complexity, because a swap must not invalidate iterators to elements of the vectors swapped: So it has to just exchange the internal buffer pointers.

vector<vertex>(a).swap(a);

It is known as the "Shrink-to-fit" idiom. Incidentally, the next C++ version includes a "shrink_to_fit()" member function for std::vector.

Answer 3

The reserved memory is not reduced when the vector size is reduced because it is generally better for performance. Shrinking the amount of memory reserved by the vector is as expensive as increasing the size of the vector beyond the reserved size, in that it requires:

1. Ask the allocator for a new, smaller memory location,
2. Copy the contents from the old location, and
3. Tell the allocator to free the old memory location.

In some cases, the allocator can resize an allocation in-place, but it's by no means guaranteed.

If you have had a very large change in the size required, and you know that you won't want that vector to expand again (the principal of locality suggests you will, but of course there are exceptions), then you can use litb's suggested swap operation to explicitly shrink your vector:

vector<vertex>(a).swap(a);

Answer 4

See also http://stackoverflow.com/questions/319292/resize-a-vector-down-c