More C++ Idioms/Shrink-to-fit

Shrink-to-fit

Intent

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

Also Known As

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

Motivation

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

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 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.

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) 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);

Solution in C++11

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().

Related Idioms

• Clear-and-minimize
• Non-throwing swap

References

• Programming Languages — C++ draft standard.