More C++ Idioms/Shrink-to-fit

From Wikibooks, open books for an open world
Jump to navigation Jump to search

Shrink-to-fit
[edit | edit source]

Intent[edit | edit source]

Minimize the capacity of a container just enough to hold existing range.

Also Known As[edit | edit source]

"Swap-To-Fit", introduced by Scott Meyers in his book "Effective STL".

Motivation[edit | edit source]

Standard library containers often allocate more memory than the actual number of elements in them. Such a policy results in an optimization of saving some allocations when a container grows in size. On the other hand, when size of the container reduces, there is often leftover capacity in the container. The leftover capacity of the container can be unnecessary wastage of memory resources. Shrink-to-fit idiom has been developed to reduce the extra capacity to a minimum required capacity and thereby saving memory resources.

Solution and Sample Code[edit | edit source]

Shrink-to-fit idiom is as simple as the one given below.

std::vector<int> v;
//v is swapped with its temporary copy, which is capacity optimal
std::vector<int>(v).swap(v);

The first half of the statement, std::vector<int>(v), creates a temporary vector of integers and it is guaranteed[1] to allocate memory just enough to hold all the elements in the parameter, v. The second half of the statement swaps the temporary vector with v using the non-throwing swap member function. swap() is very efficient, amounting to little more than swapping pointers between the vectors. After swapping, the temporary goes out of scope and deletes the memory originally held by v, whereas v retains the memory allocated by the temporary, so it has just enough to hold the original elements in v.

  1. ISO/IEC 14882:1998 does not appear to document this behavior of the copy constructor. Where is this behavior guaranteed?

A more reliable solution (notably for std::string, which may be implemented using reference counting, but also for std::vector, whose copy-constructor might copy the other vector's excess capacity[1]) is to use the "range constructor" instead of the copy constructor:

std::vector<int> v;
//v is swapped with its temporary copy, which is capacity optimal
std::vector<int>(v.begin(), v.end()).swap(v);
  1. http://www.aristeia.com/BookErrata/estl1e-errata.html (search for "string(s.begin(), s.end()).swap(s)")

Solution in C++11[edit | edit source]

In C++11 some containers declare such idiom as function shrink_to_fit(), e.g. vector, deque, basic_string. shrink_to_fit() is a non-binding request to reduce capacity() to size().

Known Uses[edit | edit source]

Related Idioms[edit | edit source]

References[edit | edit source]