shrink_to_fit that doesn’t suck

Lesson learned the hard way: trust the implementation to do the right thing! Everything else has been strikethrough’ed because my approach was flowed from the beginning. See the quoted comments at the bottom of this post.

Thanks everyone who commented! Looks like this blogging thing will be a great learning exercise for me 🙂

From https://en.cppreference.com/w/cpp/container/vector/shrink_to_fit

It is a non-binding request to reduce capacity() to size(). It depends on the implementation whether the request is fulfilled.

In other words, it can do absolutely nothing! Now what?
Let’s test programmatically what the implementation of STL is actually doing, and in case it does nothing let’s shrink the vector another way.

The test:

Self explanatory I hope 🙂 we create a vector of 1 std::byte, reserve space for 2 entries, then call shrink_to_fit. Finally we test the capacity; if it’s now 1 instead of 2, the call worked. Great! But what if it failed to shrink the vector?

shrink_to_fit that works:

We first test (once, thanks to static) if shrink_to_fit works, if it does, we invoke it. Otherwise we fallback onto a temporary -> swap trick. This works because the temporary vector created from v will have capacity equal to v‘s size. See here: https://en.wikibooks.org/wiki/More_C%2B%2B_Idioms/Shrink-to-fit

Test of our solution:

Output of the program from my Xcode console:

10
5
Program ended with exit code: 0

Complete listing:

UPDATE!

I shared my blog on Reddit CPP as well as comp.lang.c++ and received many comments about my shrink_to_fit approach:

Ouch 😉 Very constrictive critique of my implementation. Thank you sakarri and Joerg! So I decided to rewrite the initial shrink_to_fit function, here it is:

In this approach we skip the shrink_to_fit_test and go straight to the vector’s call. If it doesn’t do what we want we do the temporary -> swap trick.

Here’s the complete listing again:

Below are some of the comments I received:

Just figured I’d comment on your post about how  shrink_to_fit sucks. It’s your solution that is significantly inferior in every possible way whereas the standard’s approach is optimal. That may seem blunt but it’s worth understanding why.
First your  shrink_to_fit_test is too pessimistic since it assumes that an implementation either always performs the shrink or never performs it when actually the situation is a lot more complex than that. The whole purpose of the standard leaving it up to the implementation is that for small vectors, forcing a  shrink_to_fit potentially wastes a lot more memory than not doing anything at all. The reason is two fold, first because the default allocator doesn’t allocate memory less than 16 bytes to begin with. In other words a vector of 10 bytes takes up just as much memory as a vector of 1 byte so forcing a  shrink_to_fit in that situation doesn’t save you anything. Furthermore with your implementation it actually ends up potentially causing you to waste 4 kilobytes of RAM because your solution forces a new memory allocation and given how virtual memory works, that allocation can result in having to fetch a new page, so you’ve now wasted 4 kilobytes of physical RAM for nothing.
In situations where something like this seems fishy, it’s best to review the literature on the issue to understand why the committee made the decision they did. Sometimes they do screw up, but that’s not the initial conclusion you should jump to. Take a look at how GCC implements  shrink_to_fit, it delegates the operation to the allocator so the allocator can decide whether to carry it out since the allocator knows more about the memory system than  vector does. It also implements the operation in a way that can avoid any reallocation period and it does its best to provide the strong exception guarantee.
The standard didn’t make this part of the STL non-binding so that the people who work incredibly hard to implement it could be lazy, the standard made it non-binding so that if there are potential optimizations that save more memory and consume fewer CPU cycles by avoiding it, the implementation would be free to leverage them. This is explicitly noted in the standard as follows:
Note: The request is non-binding to allow latitude for implementation-specific optimizations. —end note
Basically there is no situation where you would want to use your implementation of  shrink_to_fit over the one provided by the standard library.

In particular, the January 27 posting “shrink_to_fit that doesn’t suck” 
still provides only solutions (to a non-existing problem) that do suck…