std::map insert() hint location: difference between c++98 and c++11

The C++98 specification is a defect in the standard. See the discussion in LWG issue 233 and N1780.

Recall that lower_bound returns an iterator to the first element with key not less than the specified key, while upper_bound returns an iterator to the first element with key greater than the specified key. If there is no key equivalent to the specified key in the container, then lower_bound and upper_bound return the same thing - an iterator to the element that would be after the key if it were in the map.

So, in other words, your current code already works correctly under the C++11 spec, and in fact would be wrong under C++98's defective specification.

Yes, it will affect the complexity. Giving the correct hint will make insert() have amortized constant complexity, while giving and incorrect hint will force the map to search for the position from the beginning, giving logarithmic complexity. Basically, a good hint makes the insertion happen in constant time, no matter how big your map is; with a bad hint the insertion will be slower on larger maps.

The solution is, apparently, to search for the hint with upper_bound instead of lower_bound.