This page is a snapshot from the LWG issues list, see the Library Active Issues List for more information and the meaning of CD1 status.

### 850. Should `shrink_to_fit` apply to `std::deque`?

Section: 22.3.8.3 [deque.capacity] Status: CD1 Submitter: Niels Dekker Opened: 2008-06-05 Last modified: 2016-01-28

Priority: Not Prioritized

View all other issues in [deque.capacity].

View all issues with CD1 status.

Discussion:

Issue 755 added a `shrink_to_fit` function to `std::vector` and `std::string`. It did not yet deal with `std::deque`, because of the fundamental difference between `std::deque` and the other two container types. The need for `std::deque` may seem less evident, because one might think that for this container, the overhead is a small map, and some number of blocks that's bounded by a small constant.

The container overhead can in fact be arbitrarily large (i.e. is not necessarily O(N) where N is the number of elements currently held by the `deque`). As Bill Plauger noted in a reflector message, unless the map of block pointers is shrunk, it must hold at least maxN⁄B pointers where maxN is the maximum of N over the lifetime of the `deque` since its creation. This is independent of how the map is implemented (`vector`-like circular buffer and all), and maxN bears no relation to N, the number of elements it currently holds.

Hervé Brönnimann reports a situation where a `deque` of requests grew very large due to some temporary backup (the front request hanging), and the map of the `deque` grew quite large before getting back to normal. Just to put some color on it, assuming a `deque` with 1K pointer elements in steady regime, that held, at some point in its lifetime, maxN=10M pointers, with one block holding 128 elements, the spine must be at least (maxN ⁄ 128), in that case 100K. In that case, shrink-to-fit would allow to reuse about 100K which would otherwise never be reclaimed in the lifetime of the `deque`.

An added bonus would be that it allows implementations to hang on to empty blocks at the end (but does not care if they do or not). A `shrink_to_fit` would take care of both shrinks, and guarantee that at most O(B) space is used in addition to the storage to hold the N elements and the N⁄B block pointers.

Proposed resolution:

To class template `deque` 22.3.8 [deque] synopsis, add:

>     void shrink_to_fit();

To deque capacity 22.3.8.3 [deque.capacity], add:

>     void shrink_to_fit();

> > Remarks: `shrink_to_fit` is a non-binding request to reduce memory use. [Note: The request is non-binding to allow latitude for implementation-specific optimizations. — end note]