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.
Section: 24.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 24.3.8 [deque] synopsis, add:
void shrink_to_fit();
To deque capacity 24.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]