Std :: queue should I shrink to fit?

Question

I am considering using std::queue (with std::deque ) for a FIFO structure.

In the queue data structure, data is only pushed into the back and appears in front. Thus, the memory in front after the ascent of an element will never be used.

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

So, should you consider freeing up memory on the front panel, which will never be used again?

Answer 1

The queue does not require shrink_to_fit if it is used in normal mode. std::vector shrink_to_fit designed for situations where vector content has decreased by a huge amount, so it actually makes sense to call a (rather expensive) redistribution to free up this huge amount of memory. In the general case, it is not required if the vector has a short lifetime or if its size does not change too much.

Having said that a std::deque is a different kind of beast. Usually it consists of fixed size memory blocks. If you remove many elements from deque, chunks that no longer contain any elements can / will be freed. Thus, the biggest memory overhead you can get at any time is slightly smaller than the block size, for example. if the queue contains only two elements: one at the end of the fragment, the second at the beginning of the next fragment. Thus, std::deque::shrink_to_fit can only move deque elements in such a way that it releases exactly one piece, which is not a large gain (a typical implementation has a block size of several kilobytes).

These are very general statements that may not apply in critical memory situations. But as standard containers, neither vector nor deque are clearly intended for use in such extreme situations. If the memory area is a problem in that part of the program where you are using the queue, you can use another data structure.

Answer 2

The std::deque memory allocation characteristics are determined by the implementation. The standard has no special requirements for when memory is allocated or freed before deque . Asymptotic requirements for implementation, removal, and access to performance lead to specific implementations. But there can be many changes.

Generally speaking, if you select enough things from the deque front, memory will be freed.