How to release memory from std::deque?

Question

I'm using a std::deque to store a fairly large number of objects. If I remove a bunch of those objects, it appears to me that its memory usage does not decrease, in a similar fashion to std::vector.

Is there a way to reduce it? I know that in a vector you have to use the 'swap trick', which I assume would work here too, but I'd rather avoid that since it would require copying all the elements left in the container (and thus requires that you have enough memory to store every object twice). I'm not intimately familiar with the implementation of deque, but my understanding of it is that it might be possible to achieve such a thing without lots of copies (whereas with a vector it's clearly not).

I'm using the VC++ (Dinkumware) STL, if that makes any difference.

Answer 1

There is no way to do this directly in a std::deque. However, it's easy to do by using a temporary (which is basically what happens in a std::vector when you shrink it's capacity).

Here is a good article on std::deque, comparing it to std::vector. The very bottom shows a clean way to swap out and shrink a vector, which works the same with deque.

Answer 2

The memory size of a deque might or might not shrink. When and How this happens is implementation specific. Unfortunately you don't have much manual control over this since deques lack even capacity() or reserve().

I'd suggest swap() if you indeed detect memory release isn't being performed at your convenience.

An intimate knowledge of deque memory management may probably be gained from Dikum website (this is your current implementation, right?)

Answer 3

As added information to this:

In C++0x/C++11, deque (and several other containers) has a new function called "shrink_to_fit" which will remove the excess items and basically align capacity() == size()

Answer 4

std::deque will return memory to its allocator. Often this allocator won't return the memory to the OS. In such cases, it appears as if memory is not "released". Good memory leak detectors will be satisfied as soon as memory is returned to the allocator, and understand that not all memory is released by free().