shrink_to_fit apply to std::deque?Section: 23.3.5.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 23.3.5 [deque] synopsis, add:
void shrink_to_fit();
To deque capacity 23.3.5.3 [deque.capacity], add:
void shrink_to_fit();Remarks:
shrink_to_fitis a non-binding request to reduce memory use. [Note: The request is non-binding to allow latitude for implementation-specific optimizations. — end note]