Interview question, part 5

Posted on by Martin

Find the starting position(s) of “runs” (consecutive characters) in the input from left to right.

Example input and output:

Input: 0000000000
Runs: 0

Input: 0101010101
Runs:

Input: 1111111111
Runs: 0

Input: 0110110110
Runs: 1 4 7

Input: 1110000011
Runs: 0 3 8

Input: 0010011010
Runs: 0 3 5

Program ended with exit code: 1

The answer:

Interview question, part 4

Posted on by Martin

I dug up another one from years ago 🙂 This one asked to write a program that:

Prints all binary numbers that do not contain consecutive bits set.

My approach was to brute force over all possible numbers and test each one with a sliding 0b11 bit mask for 2 consecutive bits set.

The answer:

Interview question, part 3

Posted on by Martin

I was given this piece of code to analyze and point out what’s wrong with it:

I was also able to compile and execute this program on my Mac; output from Xcode gives away the answer:

libc++abi.dylib: Pure virtual function called!
Program ended with exit code: 9

Program output.

But why? The constructor of Base calls void bar(), which in turn calls pure virtual void foo() = 0. The Derived overrides foo() so what’s the problem here?
Inside the constructor of Base, the type of this pointer is… Base. So the call to foo() inside bar() resolved to Base version of foo(), which is a pure virtual function lacking implementation. This is illegal and the compiler puts a check inside Base::foo() virtual function table pointing to __cxa_pure_virtual. That in turn calls __pthread_kill terminating the program.

__cxa_pure_virtual disassembly:


UPDATE:

Item #9 From Effective C++.

Related discussion: C++ corner case: You can implement pure virtual functions in the base class.

Interview question, part 2

Posted on by Martin

Another interview question I was asked in the past:

Given only a stack, implement a queue.

I remember thinking at first that it cannot be done! My mind for some reason imagined that I am limited to only one stack. I told the interviewer that I don’t think it can be done with one stack. His response was: I didn’t say anything about having only one stack. That’s when it hit me: if I use two stacks, one for pushing, one for popping, and move the elements between them, it can be done!

When pushing, items go on stack 1. So the bottom of stack 1 is the front of the queue. So how do we get to the bottom element? We pop all the items form stack 1 and push them onto stack 2. This effectively reverses the order of elements and the top of stack 2 becomes the front of the queue. We can then pop off the queue by popping off of stack 2. We do this reversal of elements on every push and pop of the queue. Yea it’s inefficient, but it works 🙂 Honestly I don’t know why you would ever want to implement a queue this way, but nevertheless it was a great interview question!

The answer:

1
2
3

Program output.

Interview question, part 1

Posted on by Martin

When interviewing for a job in the past, I was asked the following question:

Write a multithreaded program that prints a sequence of characters like this: A, B, A, B, A, B… Synchronize properly so it never prints the same character more than once in a row.

Thinking quickly on my feet 🙂 I realized the trick is to use an event object (I will be using this one). But wait, one event object is not enough. The real trick is to use two event objects! Where thread 1 waits on event 1 to be signaled, then prints ‘A’, and finally signals event 2; and repeats the sequence in a loop. Thread 2 waits on event 2, then prints ‘B’, and finally signals event 1. Ditto loop. That should do it!

The answer:

A
B
A
B
A
B

Program output.

Template concepts, sort of

Posted on by Martin

Back to the queue class from previous posts (here and here)… I realized things can be done better: I want the queue to work with move-constructible and move-assignable types as well as copyable types, and do so automatically. This way the push and pop methods can use std::move to insert and remove elements from the queue. I also want it to work with no-throw constructible and assignable types; this way the push and pop methods can take a more optimized path that does not deal with exceptions. So I realized that I need four versions of push and pop methods: 1) copy-constructible, 2) no-throw copy-constructible, 3) move-constructible, 4) no-throw move-constructible. All fine and dandy, but how do we select the right version at compile time based on type T that the queue holds?
In C++20 we will get template concepts that will allow us to do just that sort of selection at compile time. In the meantime we have to make do with std::enable_if (see here) and other type traits.
Finally, for completeness of interface, I want to add a pop method that returns an item rather than taking an output reference parameter, and declares proper noexcept value depending on type T.

Below is the no-throw-movable pop method; it’s declared noexcept and lacks exception handling code (possibly making it faster at runtime):

And here is the new pop method; notice its noexcept value is dependent on which version of pop it uses, and it is deduced at compile time 🙂

Complete listing:

Event objects

Posted on by Martin

No, not the type where you subscribe to an event using an interface or a callback. The type where you wait on an event to be signaled, just like Windows Event Objects.
Thanks to many suggestions from the kind people on Reddit’s r/cpp I came up with 2 classes: manual_event that can be waited on, and when signaled stays signaled until it’s reset, unblocking all waiting threads. And auto_event that resets to non-signaled state when signaled, and unblocks only one waiting thread.
The below implementation is far from final and I am open to any suggestions from people experienced in multi-threaded programming.

The usage example:

The event.h:

Class mechanics

Posted on by Martin

A friend asked me to make a post about the mechanics of virtual functions in C++. I thought about it for a few days and decided to write a broader post about several topics dealing with classes and what happens under the hood when we use member functions, inheritance, and virtual functions.

Member functions. You can think of member functions as no different than static members, or functions defined outside the class, except the compiler adds a hidden first parameter this. That’s how a member function is able to operate on an instance of a class. So when you write this:

What you are really getting is this:

A compiler generated C_MemFun with extra parameter of type C*.

Inheritance. Here I want to briefly mention the order in which constructors and destructors are called: if D derives from B and you create an instance of D, the constructors will be executed in order: B’s first, D’s second. So when the control enters D’s constructor, B part of the class has been initialized already. The opposite is true for destructors. When you delete an instance of D, the destructors will be executed in order: D’s first, B’s second. The code at the end of this post will demonstrate it. BTW I’m skipping over virtual and pure virtual destructors in this post since that’s a topic that could easily become its own blog post 😉

Virtual functions. Several things happen when we declare a virtual function: for each class the compiler creates a hidden table called virtual function table. Pointers to virtual functions are stored in this table. Next each instance of a class gets a hidden member variable called virtual function table pointer that, as the name implies, points at the virtual function table for that particular class. So an instance of B has a hidden member pointing at B’s virtual function table, and an instance of D… ditto. When you create virtual functions the compiler generates the following dispatch code:

For an instance of type T called _this_, it does a lookup in the VirtualTablePtr for virtual function number VirtualFuncNum, and calls it with _this_as the first argument plus whatever extra parameters it accepts. Depending on the type of _this_, VirtualTablePtr will point at a different virtual function table and that’s more or less how we get runtime polymorphism in C++ 🙂

Complete listing:

===> Base start <===
BaseConstructor(0x1005845d0, Member1 = 29)
Base(Member1 = 29)::BaseVirtualFunction_1(59)
Base(Member1 = 29)::BaseVirtualFunction_2(52)
BaseDestructor(0x1005845d0)
===> Base end <===

===> Derived start <===
BaseConstructor(0x10060b6a0, Member1 = 52)
DerivedConstructor(0x10060b6a0, Member2 = 80)
Derived(Member1 = 52, Member2 = 80)::DerivedVirtualFunction_1(40)
Derived(Member1 = 52, Member2 = 80)::DerivedVirtualFunction_2(79)
DerivedDestructor(0x10060b6a0)
BaseDestructor(0x10060b6a0)
===> Derived end <===

Program output.

Refactoring std::auto_ptr

Posted on by Martin

A colleague at work was recently tasked with refactoring some legacy code and came across the good old std::auto_ptr. In C++0x it has been deprecated (and later removed outright; I can’t even compile std::auto_ptr code in Visual Studio 2017 nor Xcode 10.1) so it was his job to rewrite it in the modern C++ way. The code that my colleague came across had another problem. Can you spot it?

std::auto_ptr was never meant to hold pointers to arrays. So the code above, assuming it didn’t crash, was leaking memory (regardless of what it holds, std::auto_ptr always calls delete in its destructor; delete[] was needed in the code above).

So how do we refactor legacy std::auto_ptr code into modern C++? The answer is std::unique_ptr(https://en.cppreference.com/w/cpp/memory/unique_ptr). A std::auto_ptr holding a pointer to a single object of type T, in modern C++, becomes:

std::make_unique can forward constructor parameters to T::T, like this:

And an array of T’s of size N becomes:

Note that for std::make_unique to be able to create an array of T’s, T must have a T::T() (default constructor; or a constructor with all parameters having default values: T::T(int x = 0)).

Fast semaphore

Posted on by Martin

I received an interesting piece of code during my recent discussion about the blocking queue: a fast semaphore implementation. The fast_semaphore class uses a regular C++ semaphore as fallback for waiting and unblocking the thread(s) while doing its magic using an atomic variable and memory fences of the new C++ memory model (see here and here).

I present to you, my shortened version of, Fast-Semaphore by Joe Seigh; C++ Implementation by Chris Thomasson:

Better blocking queue

Posted on by Martin

In the previous post we discussed a multi-threaded blocking queue who’s implementation was lacking: it was not exception safe. It left the semaphore counts wrongly modified in the presence of exceptions emitted by T’s copy constructor or assignment operator.

Below is a corrected void push(const T item) method:

In the corrected version we first catch any exception possibly emitted by T’s copy constructor then adjust back the open-slot semaphore. Since the push operation failed the number of open and full slots has not changed. Finally we re-throw the exception.

Below is a corrected void pop(T item) method:

In the corrected version we first catch any exception possibly emitted by T’s assignment operator then adjust back the full-slot semaphore. Since the pop operation failed the number of open and full slots has not changed. Finally we re-throw the exception.

We now have a robust queue template class that can handle misbehaving T’s 🙂

Blocking queue

Posted on by Martin

Where produce-consumer pattern is present it is often the case that one is faster that the other: a parsing producer reads records faster than a processing consumer; a disk reading producer is faster than network sending consumer.
Producer and consumer often communicate by queues: the producer will put items on a queue while the consumer will pop items off a queue. What happens when the queue becomes full, or empty? One approach of the producer is to try to put an item on a queue and if it’s full yield the thread and repeat. Similarly the consumer can try to pop an item off a queue and if it’s empty, ditto. This approach of try-fail-yield can unnecessarily burn CPU cycles in tight loops that constantly try to put or pop items off a queue.
Another approach is to temporarily grow the queue, but that doesn’t scale well. When do we stop growing? And once we stop we have to fall back onto the try-fail-yield method.

What if we could implement a blocking queue: a queue who’s put operation blocks when the queue if full, and unblocks only when another thread pops an item off the queue. Similarly a queue who’s pop operation blocks when the queue is empty, and unblocks only when another thread puts an item on the queue. An example of using such a queue would look like this (notice a fast producer and slow consumer in the code below):

Notice no try-fail-yield code in the example above. The put operation of the fast producer simply blocks until the slow consumer makes more room on the queue. The output of the program is as we expect; the fast producer fills up the queue then blocks, a second later the consumer starts to slowly pop items of the queue; they go in tandem for a while until the producer exits and the consumer drains the queue:

push v = 1
push v = 2
push v = 3
push v = 4
push v = 5
pop  v = 1
push v = 6
pop  v = 2
push v = 7
pop  v = 3
push v = 8
pop  v = 4
push v = 9
pop  v = 5
push v = 10
pop  v = 6
pop  v = 7
pop  v = 8
pop  v = 9
pop  v = 10
Program ended with exit code: 1

The trick to implementing such a queue is the ability to count both open and full slots of the queue, and block. A semaphore is a perfect mechanism to do just that 🙂 In fact we need two semaphores: one to count the open slots, and another to count the full slots. The open-slot semaphore starts with a count equal to the size of the queue. The full-slot semaphore starts with a count of zero. A push operation waits on the open-slot semaphore and signals the full-slot semaphore. A pop operation waits on the full-slot semaphore and signals the open-slot semaphore.

The blocking queue implementation below uses Boost semaphores to count and std::mutex to protect the critical section. In the next post I will show how to make it safe in the presence of exceptions; currently it misbehaves if T’s copy constructor or assignment operator throw (it assumes T’s destructor will never throw).

queue.h

P.S. It was suggested to me that the use of boost::interprocess::interprocess_semaphore is a heavy-handed approach. I agree. I only used it to keep the example code small and uncluttered with more utility classes. In production you should have a lightweight semaphore class that uses a mutex and a condition variable. Like this 🙂 …

RAII

Posted on by Martin

I know the topic of RAII has been blogged about plenty of times before. Still, I want to present to you my take on it 🙂 Recently I created a policy-based generic RAII template for holding various types of resources (pointers, file handles, mutexes, etc). The nice thing about my implementation is that in order to acquire and release a new type of a resource you only have to define simple Acquire and Release policy template classes and plug them as parameters to the RAII template. Here’s how you can use it with std::mutex:

In the code above we declare 2 policy classes: LockPolicy which calls .lock(); on type T, and UnlockPolicy which calls .unlock(); on type T. Next we declare scope_lock to be a template which will hold type T by reference and apply LockPolicy::Execute(T t); and UnlockPolicy::Execute(T t); in the constructor and destructor of RAII. This way we can use scope_lock with any object that has .lock(); and .unlock(); methods.

As an exercise in writing policy classes let’s use RAII template to hold and automatically delete or delete[] pointers and pointers to arrays:

First we need a policy that does nothing; let’s call it NoOpPolicy. That is because nothing needs to happen to a pointer in the constructor of RAII; it’s already allocated. Next we declare two policies: PointerReleasePolicy which calls delete on type T, and ArrayReleasePolicy which calls delete[] on type T. Finally we define ptr_handle_t to be a RAII template which holds a pointer to T, applies NoOpPolicy::Execute(T t); in its constructor and PointerReleasePolicy::Execute(T t); in its destructor. We do the same for arr_ptr_handle_t except using ArrayReleasePolicy.

Complete listing:

L1 cache lines

Posted on by Martin

Herb Sutter gave an interesting talk titled Machine Architecture: Things Your Programming Language Never Told You:

In it he gives a tiny yet very interesting example of code that illustrates hardware destructive interference: how the size of L1 cache line and improper data layout can negatively affect performance of your code.
The example program allocates two int’s on the heap one right next to the other. It then starts two threads; each thread reads and writes to one of the int’s location. Let’s do just that, 100’000’000 times and see how long it takes:

Duration: 4338.55 ms

Let us now do the same exact thing, except this time we’ll space the int’s apart, by… you guessed it, L1 cache line size (64 bytes on Intel and AMD x64 chips):

Duration: 1219.50 ms

The same code now runs 4 times faster. What happens is that the L1 caches of the CPU cores no longer have to be synchronized every time we write to a memory location.

Lesson here is that data layout in memory matters. If you must run multiple threads that perform work and write to memory locations, make sure those memory locations are separated by L1 cache line size. C++17 helps us with that: Hardware Constructive and Destructive Interference Size.

Complete listing:

Sorting and locality

Posted on by Martin

Let’s look at two standard data structures: std::vector and std::list and what happens to the performance of traveling them sequentially once they are sorted.

In this example we will generate a std::vector and std::list of 10,000,000 randomly generated int values. We will then travel them sequentially using std::accumulate and measure the time it took. Finally we will sort both data structures and repeat the sequential access.

Below are the durations captured on my 2012 MacBook Pro 2.3 GHz Intel Core i7. The code was compiled with maximum optimizations using latest GCC, Apple Clang, and LLVM compilers available for Mac OS:

GCC -Ofast -march=native -lstdc++
List duration 31.795 ms
Sorted list duration 970.679 ms
Vector duration 0.011 ms
Sorted vector duration 0.005 ms

Apple CLANG -Ofast -march=native -lc++
List duration 29.112 ms
Sorted list duration 996.429 ms
Vector duration 0.004 ms
Sorted vector duration 0.004 ms

LLVM CLANG -Ofast -march=native -lc++
List duration 27.358 ms
Sorted list duration 1014.641 ms
Vector duration 0.005 ms
Sorted vector duration 0.005 ms

Let’s talk about the std::vector first. The time to run std::accumulate on unsorted and sorted vector is virtually the same. Why? Because std::vector is a data structure laid out continuously in memory. Regardless of what we do to it the locality of elements is always present. By accessing Nth element the CPU brings into L1 cache N+1,…,N+M elements; up to a cache line size (64 bytes on Intel and AMD x64 chips).

What about the std::list? Why such a performance penalty after sorting?
Remember how a doubly-linked list (usually how std::list is implemented) is laid out in memory: nodes containing data elements with pointers to previous and next node. By sorting it me moved the nodes all over the heap; effectively randomizing its layout on the heap and making each node’s next and previous pointers point in random places. The process of sorting destroyed whatever locality may have been there when the list was first created.

Lesson here is to carefully choose your containers. If you are going to sort them and later access them sequentially then std::vector is the clear winner.

Complete listing:

AoS vs SoA performance

Posted on by Martin

There is an interesting set of articles at Fluent{C++} discussing AoS vs SoA.
I decided to do my own performance test: to iterate and accumulate data over an array of 10,000,000 structures that describe a person:

Versus a structure of arrays of the same data:

Below are the numbers measured on my 2012 MacBook Pro 2.3 GHz Intel Core i7. The code was compiled with maximum optimizations using latest GCC, Apple Clang, and LLVM compilers available for Mac OS:

GCC -Ofast -march=native -lstdc++
AoS duration 108.039 ms
SoA duration 42.228 ms


Apple CLANG -Ofast -march=native -lc++
AoS duration 64.001 ms
SoA duration 24.916 ms


LLVM CLANG -Ofast -march=native -lc++
AoS duration 67.579 ms
SoA duration 22.620 ms


Conclusion: locality of reference matters 🙂

Complete listing:


P.S. I had to do the sum += and return sum; hack. Otherwise the compilers kept optimizing away the averageXXX calls!

What happens when we “new”

Posted on by Martin

Let us take a look at what the C++ compiler generates for us when we use the keywords new, new[], delete, and delete[](I will skip over std::nothrow versions in this post).

new

When you write this:

The compiler really generates this:

First, using operator new the memory for T is allocated. If the allocation fails it will throw std::bad_alloc exception. Next (line 4) the object of type T is being constructed in the memory address t2 (this is called placement new). This however may fail due to T’s constructor throwing an exception. The language guarantees that if that happens, the allocated memory will be freed. The code in line 6 will catch any exception emitted by T’s constructor. Line 8 will then free the memory, and finally line 9 will re-throw the exception.

delete

This one-liner:

Becomes this:

In line 1 T’s destructor is called, and in line 2 the memory is freed using operator delete. All is good until T’s destructor throws an exception. Noticed the lack of try-catch block? If T’s destructor throws, line 2 will never be executed. This is a memory leak and reason why you should never throw exceptions from destructors; see Effective C++ by Scott Meyers, Item #8.

new[]

Things are about to get interesting. This innocent looking snippet of code:

Becomes (gasp), more or less 😉 , this:

So what happens when we allocate an array of objects on the heap? Where do we store the number of objects allocated which needs to be referenced later when deleting the array?
The compiler will generate code that allocates enough space for HOW_MANY instances of T, plus sizeof(size_t) bytes to store the number of objects created and will place the object count at offset 0 of the allocated memory block. Moreover the language guarantees that it will either allocate and construct ALL instances of T, or none. So what happens if halfway through constructing the objects in the array one of the constructors throws an exception? The compiler will generate proper cleanup code to deal with this scenario. This is what the above code illustrates. Let’s go through it line by line.
Line 1 allocates enough space for HOW_MANY objects plus sizeof(size_t) bytes for the number of objects in the array.
Line 2 stores the number of objects at offset 0 of the memory block.
Line 3 advances the pointer t4 by sizeof(size_t) bytes to where the first T will be created.
Line 4 is the loop inside which we’ll be creating the instances of T one by one.
Line 8 creates an instance of T at the right memory location inside the array using placement new (same as when constructing a single instance of T).
Line 10 catches any possible exception from T’s constructor and begins the cleanup block of partially constructed array.
Line 12 defines the loop that will destroy all instances of T created up to the point of exception being thrown.
Line 13 calls the destructor of T.
Line 14 moves the pointer t4 back by sizeof(size_t) bytes to the beginning of the memory block allocated for the array.
Line 15 frees the previously allocated memory block.
Line 16, after having done all the cleanup, re-throws the exception.

delete[]

The following array delete statement:

Is turned into something like this:

The compiler now has to generate code to first destroy all the instances of T stored in the array before deallocating the memory. After allocating the array of T’s the t4 pointed at the first object in the array, not at the beginning of the memory block. That’s why…
Line 1 subtracts sizeof(size_t) bytes from t4 and retrieves the number of objects in the array.
Line 2 starts the loop that will call every T’s destructor.
Line 3 destroys each instance of T.
Line 4 moves the t4 pointer back by sizeof(size_t) bytes to point at the beginning of the memory block.
Line 5, after all T’s have been destroyed, frees the memory block.
Due to a lack of try-catch block the same principle of not throwing exceptions from destructors applies here as well.

Complete listing:

enum to string, take 2

Posted on by Martin

Thanks to Sebastian Mestre (who commented on my previous post) I learned something new today 🙂 The X macro makes the enum to string code much… well, perhaps not cleaner, but shorter 😉 It also solves the problem of having to update the code in 2 places: 1st in the enum itself, 2nd in the enum to string map.
Without further ado I present to you the X macro:

And the complete implementation goes something like this:

In this version we only have to update the MY_ENUM macro. The rest is taken care of by the preprocessor.


UPDATE

Here’s the same approach that works with strongly typed enums:


UPDATE 2

Here’s the same approach that works with strongly typed enums, custom enum values, and enum values outside of the defined ones:

enum to string

Posted on by Martin

A fellow engineer at work asked me today how to convert an enum to a string value. This is what I came up with:

MyEnumToString function has a static map of MyEnum to const char*. In the assert it checks that the MyEnum::SIZE is equal to the size of the map: so you don’t forget to update the map when you update MyEnum with a new entry 😉

For larger enums would unordered_map be a better choice for the mapping data structure in terms of performance? Probably.


UPDATE

Several people on here and reddit suggested that the use of std::map or even std::unordered_map is an overkill. I agree. Though it is a must for non continuous enums (ones that do not start at 0 and do not increment by 1). Below is an updated MyEnumToString function which offers much faster conversion. It uses std::array to hold the string values.

shrink_to_fit that doesn’t suck

Posted on by 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:

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…