shrinking a vector

Question

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);

Johannes Schaub - litb · Answer 1 · 2009-02-25T16:42:50.993

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.

score 8 · Accepted Answer · answered Feb 25 '09 at 16:11

8

The usual trick is to swap with an empty vector:

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

answered Feb 25 '09 at 16:11

David Thornley

56,304
9
91
158

It's not clear to me if these are STL vectors. If so, vector.resize(n) also works. – Joao da Silva Feb 25 '09 at 16:18
2

@João: not the same, resize is not required to actually release the memory if the new size is smaller. – user83255 May 22 '09 at 15:00
@user83255 old post but even a new vector is not required to have a 0 space. I saw an implementation that started with non 0 offset. – bashrc Oct 08 '18 at 05:03

score 6 · Answer 3 · answered Feb 25 '09 at 16:16

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:

Ask the allocator for a new, smaller memory location,
Copy the contents from the old location, and
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);

score 1 · Answer 4 · edited May 23 '17 at 12:13

There is a member function for this, shrink_to_fit. Its more efficient than most other methods since it will only allocate new memory and copy if there is a need. The details are discussed here, Is shrink_to_fit the proper way of reducing the capacity a `std::vector` to its size?

If you don't mind the libc allocation functions realloc is even more efficient, it wont copy the data on a shrink, just mark the extra memory as free, and if you grow the memory and there is memory free after it will mark the needed memory as used and not copy either. Be careful though, you are moving out of C++ stl templates into C void pointers and need to understand how pointers and memory management works, its frowned upon by many now adays as a source for bugs and memory leaks.

shrinking a vector

4 Answers4

Linked