Author: Martin

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:

bool shrink_to_fit_test()
{
    std::vector test_vector(1);
    test_vector.reserve(2);
    test_vector.shrink_to_fit();
    return test_vector.capacity() == 1;
}

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:

template
void shrink_to_fit(std::vector& v)
{
    static bool shrinks = shrink_to_fit_test();
    if(shrinks)
        v.shrink_to_fit();
    else
        std::vector(v).swap(v);
}

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:

int main(int argc, const char * argv[])
{
    std::vector v(5);
    v.reserve(10);
    std::cout << v.capacity() << std::endl;
    shrink_to_fit(v);
    std::cout << v.capacity() << std::endl;
    return 0;
}

Output of the program from my Xcode console:

10
5
Program ended with exit code: 0

Complete listing:

#include 
#include 

bool shrink_to_fit_test()
{
    static std::vector test_vector(1);
    test_vector.reserve(2);
    test_vector.shrink_to_fit();
    return test_vector.capacity() == 1;
}

template
void shrink_to_fit(std::vector& v)
{
    static bool shrinks = shrink_to_fit_test();
    if(shrinks)
        v.shrink_to_fit();
    else
        std::vector(v).swap(v);
}

int main(int argc, const char * argv[])
{
    std::vector v(5);
    v.reserve(10);
    std::cout << v.capacity() << std::endl;
    shrink_to_fit(v);
    std::cout << v.capacity() << std::endl;
    return 0;
}

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:

template
void shrink_to_fit(std::vector& v)
{
    v.shrink_to_fit();
    if(v.capacity() != v.size())
        std::vector(v).swap(v);
}

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:

#include 
#include 

template
void shrink_to_fit(std::vector& v)
{
    v.shrink_to_fit();
    if(v.capacity() != v.size())
        std::vector(v).swap(v);
}

int main(int argc, const char * argv[])
{
    std::vector v(5);
    v.reserve(10);
    std::cout << v.capacity() << std::endl;
    shrink_to_fit(v);
    std::cout << v.capacity() << std::endl;
    return 0;
}

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