std::queue should I shrink to fit? [closed]

Question

I am considering to use std::queue(with std::deque) for FIFO structure.

In queue data structure, data only pushed in the back and popped in the front. Therefore, the memory in the front after popping an element will never be used.

I remember that std::vector does not release the memory until I explicitly call shrink_to_fit method. What about std::deque?

So, should I consider releasing the memory in the front which will never be used again?

Answer 1

The memory allocation characteristics of std::deque are implementation defined. The standard has no specific requirement on when memory is allocated or released as far as deques are concerned. The asymptotic requirements on insertion, deletion, and access performance force implementations along certain lines. But there can be much variation within that.

Generally speaking, if you pop enough things from the front of a deque, a memory deallocation will happen.

Answer 2

You don't exactly need a shrink_to_fit for a queue, if it is used normally. std::vector's shrink_to_fit is meant for situations where the vector content has diminished by a huge amount, so that it actually has a benefit to call the (rather costly) reallocation in order to free that huge amount of memory. It is in general not needed if the vector has a short lifetime or if its size does not vary too much.

Having said that, a std::deque is a different kind of beast. It typically consists of fixed-size chunks of memory. If you erase lots of elements from the deque, the chunks that no longer contain any elements can/will be deallocated. So the biggest memory overhead you can have at any time is a bit under twice the chunk size, e.g. if the queue contains only two elements, one at the end of a chunk, the second at the start of the next chunk. Therefore, std::deque::shrink_to_fit can only move the elements of the deque in a way that frees exactly one chunk, wich is not a big gain (iirc a typical implementation has a chunk size of a few kb).

These are very general statements that might not apply in memory critical situations. But as standard containers, neither vector not deque are explicitly designed to be used in such exetreme situations. If memory footprint is an issue in the part of the program where you use the queue, you might want to use yet another data structure.