Quick Q: shrink_to_fit() vs swap trick

Quick A: Are equivalent, but shrink_to_fit mark the intention.

Recently on SO:

shrink_to_fit() vs swap trick

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

As a result, both approaches should have roughly the same complexity, except that shrink_to_fit more clearly telegraphs the intention and is probably more amenable to compiler optimizations.

Add a Comment

Comments are closed.

Comments (0)

There are currently no comments on this entry.