How it works...

The only difference to normal map insertions in this recipe was the additional hint iterator. And we spoke about correct and wrong hints.

A correct hint will point to an existing element, which is greater than the element to be inserted so that the newly inserted key will be just before the hint. If this does not apply for the hint the user provided during an insertion, the insert function will fall back to a nonoptimized insertion, yielding O(log(n)) performance again.

For the first insertion, we got the end iterator of the map, because we had no better hint to start with. After installing a "z" in the tree, we knew that installing "y" will insert a new item just in front of the "z", which qualified it to be a correct hint. This applies to "x" as well, if put into the tree after inserting the "y", and so on. This is why it is possible to use the iterator, which was returned by the last insertion for the next insertion.