Efficiently modifying the keys of std::map items

Since the std::map data structure maps from keys to values in a way that the keys are always unique and sorted, it is of crucial value that users cannot modify the keys of map nodes that are already inserted. In order to prevent the user from modifying the key items of perfectly sorted map nodes, the const qualifier is added to the key type.

This kind of restriction is perfectly sane because it makes it harder for the user to use std::map the wrong way. But what shall we do if we really need to change the keys of some map items?

Prior to C++17, we had to remove the items of which we need to change the key value from the tree, in order to reinsert them. The downside of this approach is that this always needlessly reallocates some memory, which sounds bad in terms of performance.

Since C++17, we can remove and reinsert map nodes without any reallocation of memory. We will see how that works in this recipe. 

 

How to do it...

We implement a little...