How to shrink-to-fit an std::vector in a memory-efficient way?

Question

I would like to 'shrink-to-fit' an std::vector, to reduce its capacity to its exact size, so that additional memory is freed. The standard trick seems to be the one described here:

template< typename T, class Allocator >
void shrink_capacity(std::vector<T,Allocator>& v)
{
   std::vector<T,Allocator>(v.begin(),v.end()).swap(v);
}

The whole point of shrink-to-fit is to save memory, but doesn't this method first create a deep copy and then swaps the instances? So at some point -- when the copy is constructed -- the memory usage is doubled?

If that is the case, is there a more memory-friendly method of shrink-to-fit? (In my case the vector is really big and I cannot afford to have both the original plus a copy of it in memory at any time.)

Answer 1

Well, if you wanted to resize an array, what would you do? You have to create a new one and copy all of the values over - be it individually or with memcpy or whatever. You can't really resize an array in C or C++.

std::vector is pretty much guaranteed to be implemented using an array for its storage (IIRC, the standard does not guarantee that it's an array, but an array is the only thing which can fulfill the various requirements of the API such as how efficient each operation must be; so, in effect, it's guaranteed even if that guarantee isn't explicit). As it's implemented using an array, and you can't resize arrays without copying, you can't resize vectors without copying.

You could, in theory, have a shrink_capacity() function which hid the fact that you had to temporarily more or less double its size requirements, but since std::vector does not currently have such a function, you have to actually make an explicit copy. The swap trick is just a nice way to do that.

If you really care about memory in such a case, what you can do is use pointers (or smart pointers) instead of having the vector hold the objects directly. That may not be entirely desirable, but it would reduce your memory requirements.

Answer 2

If your new size is half of the original, you might be able to get away with placement newing your new vector (or a straight dynaimc array if vector can't do this) into the unused end portion of your old one. Not sure if vector stores info in that area of memory so this would be very hacky and scary. But it's an idea.

Now that I think about it, a memMove() type operation where you copy the information in reverse from the last index used in the original to the back of the unused area in the original would preserve the data. If you made this a placement new of an array you could point it to wherever the new data would have existed in the middle on the original memory area. An in place move per se.