Proper vector memory management

Question

I'm making a game and I have a vector of bullets flying around. When the bullet is finished, I do bullets.erase(bullets.begin() + i); Then the bullet disappears. However it does notseem to get rod of the memory. If I create 5000 bullets then create 5,000 more after those die off, memory stays the same, but if I create 5,000 more while those 5000 are flying, it will allocate new space. What do I have to do to actually free up this memory?

Answer 1

The std::vector class automatically manages its internal memory. It will expand to hold as many items as you put into it, but in general it will not shrink on its own as you remove items (although it will of course release the memory when it destructs).

The std::vector has two relevant concepts of "size". First is the "reserved" size, which is how much memory it has allocated from the system to use for storing vector elements. The second is the "used" size, which is how many elements are logically in the vector. Clearly, the reserved size must be at least as large as the used size. You can discover the used size with the size() method (which I'm sure you already know), and you can discover the reserved size using the capacity() method.

Usually, when the used and reserved sizes are the same, and you try to insert a new element, the vector will allocate a new internal buffer of twice the previous reserved size, and copy all of the existing elements into that buffer. This is transparent to you except that it will invalidate any iterators that you are holding. As I noted before, AFAIK, most STL implementations will never shrink the reserved size as a response to an erasure.

Unfortunately, while you can force a vector to increase its reserved size using the reserve() method, this does not work for decreasing the reserved capacity. As far as I can tell, your best bet for effecting a reduction in capacity is to do the following:

std::vector<Bullet>(myVector).swap(myVector);

What this will do is create a temporary vector which is a copy of the original vector (but with the minimum necessary capacity), and then swap the internal buffers of the two vectors. This will cause your original vector to have the same data but a potentially smaller reserved size.

Now, because creating that temporary copy is a relatively expensive operation (i.e. it takes a lot more processor time than normal reads/insertions/deletions), you don't want to do it every time you erase an element. For the same reason, this is why the vector doubles its reserved size rather than increasing it by 1 when you need to exceed the existing size. Therefore, what I would recommend is that after you have erased a relatively large number of elements, and you know you will not be adding that many more any time soon, perform the swap 'trick' above to reduce the capacity.

Finally, you may also want to consider using something other than a std::vector for this. Erasing elements from the middle of a vector, which it seems that you are doing frequently, is a slow operation compared to many other types of data structures (since the vector has to copy all of the subsequent elements back one slot to fill the hole). Which data structure is best for your purposes depends on what else you are doing with the data.