Knowing the new insertion hint semantics of std::map::insert

Looking up items in an std::map takes O(log(n)) time. This is the same for inserting new items, because the position where to insert them must be looked up. Naive insertion of M new items would thus take O(M * log(n)) time.

In order to make this more efficient, std::map insertion functions accept an optional insertion hint parameter. The insertion hint is basically an iterator, which points near the future position of the item that is to be inserted. If the hint is correct, then we get amortizedO(1) insertion time.

How to do it...

In this section, we will insert multiple items into an std::map, and use insertion hints for that, in order to reduce the number of lookups.

1. We are mapping strings to numbers, so we need the header files included for std::map and std::string.

      #include <iostream>
      #include <map>
      #include <string>

2. The next step is to instantiate a map, which already contains some example characters...