Does std::deque release some of its unused chunks of memory?

Question

I know std::vector doesn't reduce its capacity but since std::deque is allocated in chunks, I expect it to free at least some of the chunks that are no longer used.

From what I have searched I am confused as the answer seems to be "no" or "maybe". Does anyone have a concrete answer?

If it does not free its chunks, does anyone know of some other implementation that does this?

I am brainstorming data structures for an application redesign that currently uses linked lists but gives poor performance which is why I am considering a deque. Challenge is my application should run the whole day and it would have tons of deque and each one could grow to be very long, hence I cannot neglect storage use of deque or a vector.

Answer 1

Does anyone have a concrete answer?

The concrete answer is "no ... or maybe".

The language standard doesn't impose any requirements on containers cacheing or releasing cached memory during their lifetime. It is unspecified. It is an implementation detail, which is left up to the implementation.

So, your options are to:

1. test what your standard library's implementation does
2. find another implementation that does what you want
3. write your own

If you decide on 2 or 3, you need a benchmark to tell whether you succeeded anyway, so do 1 first.

Answer 2

I know std::vector doesn't reduce its capacity but since std::deque is allocated in chunks, I expect it to free at least some of the chunks that are no longer used.

[ This is specific to libc++ ]

As a deque shrinks, most of the unused chunks will be freed. The deque will keep (at most) two unused chunks. The reason for this is that when the deque is being used "as a queue", (items are being put on one end and taken off the other end, but the size of the deque is relatively stable), the deque will not need to allocate or free additional chunks.