Using copy-swap trick instead of shrink_to_fit() on std::vector CXX-W2027

shrink_to_fit() and the copy-swap trick are two ways to reduce the capacity of a std::vector container in C++.

The copy-swap trick was used prior to the introduction of shrink_to_fit(). It involves swapping the vector with a temporary copy of itself that has the minimum required capacity, thereby releasing the extra memory. However, the swap trick isn’t actually constant-time.

The cost of performing the actual swap is indeed O(1), but then there’s the cost of the std::vector destructor firing and cleaning up all the allocated space.

That can potentially have cost Ω(n) if the underlying objects have nontrivial destructors, since the std::vector needs to go and invoke those destructors.

There’s also the cost of invoking the copy constructors for all the elements stored in the initial vector, which is similarly Ω(n).

shrink_to_fit() is a member function of std::vector that was introduced in C++11. It reduces the capacity of the vector to the minimum required capacity, thereby releasing the extra memory.

It is more efficient than the copy-swap trick because it doesn’t require copying the vector. However, it is "not" guaranteed to reduce the capacity to the minimum required capacity.

Bad practice

#include <vector>

int main() {
    std::vector<int> v = {1, 2, 3, 4, 5};
    std::vector<int>(v).swap(v);
    return 0;
}

Recommended

#include <vector>

int main() {
    std::vector<int> v = {1, 2, 3, 4, 5};
    v.shrink_to_fit();
    return 0;
}