101010 101010 - 2 months ago 10
C++ Question

Is shrink_to_fit the proper way of reducing the capacity a `std::vector` to its size?

In C++11

shrink_to_fit
was introduce to complement certain STL containers (e.g.,
std::vector
,
std::deque
,
std::string
).

Synopsizing, its main functionality is to request the container that is associated to, to reduce its capacity to fit its size. However, this request is non-binding, and the container implementation is free to optimize otherwise and leave the vector with a capacity greater than its size.

Furthermore, in a previous SO question the OP was discouraged from using
shrink_to_fit
to reduce the capacity of his
std::vector
to its size. The reasons not to do so are quoted below:


shrink_to_fit
does nothing or it gives you cache locality issues and it's O(n) to
execute (since you have to copy each item to their new, smaller home).
Usually it's cheaper to leave the slack in memory. @Massa



Could someone be so kind as to address the following questions:


  • Do the arguments in the quotation hold?

  • If yes, what's the proper way of shrinking an STL container's capacity to its size (at least for
    std::vector
    ).

  • And if there's a better way to shrink a container, what's the reason for the existence of
    shrink_to_fit
    after-all?


Answer

Do the arguments in the quotation hold?

Measure and you will know. Are you constrained in memory? Can you figure out the correct size up front? It will be more efficient to reserve than it is to shrink after the fact. In general I am inclined to agree on the premise that most uses are probably fine with the slack.

If yes, what's the proper way of shrinking an STL container's capacity to its size (at least for std::vector).

The comment does not only apply to shrink_to_fit, but to any other way of shrinking. Given that you cannot realloc in place, it involves acquiring a different chunk of memory and copying over there regardless of what mechanism you use for shrinking.

And if there's a better way to shrink a container, what's the reason for the existence of shrink_to_fit after-all?

The request is non-binding, but the alternatives don't have better guarantees. The question is whether shrinking makes sense, if it does, then it makes sense to provide a shring_to_fit operation that can take advantage of the fact that the objects are being moved to a new location. I.e. if the type T has a noexcept(true) move constructor, it will allocate the new memory and move the elements.

While you can achieve the same externally, this interface simplifies the operation. The equivalent to shrink_to_fit in C++03 would have been:

std::vector<T>(current).swap(current);

But the problem with this approach is that when the copy is done to the temporary it does not know that current is going to be replaced, there is nothing that tells the library that it can move the held objects. Note that using std::move(current) would not achieve the desired effect as it would move the whole buffer, maintaining the same capacity().

Implementing this externally would be a bit more cumbersome:

{
   std::vector<T> copy;
   if (noexcept(T(std::move(declval<T>())))) {
      copy.assign(std::make_move_iterator(current.begin()),
                  std::make_move_iterator(current.end()));
   } else {
      copy.assign(current.begin(), current.end());
   }
   copy.swap(current);
}

Assuming that I got the if condition right... which is probably not what you want to write every time that you want this operation.

Comments