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.