std::unordered_map insert with hint

Question

std::map has an insert method that takes a "hint" iterator that will reduce the insertion time from log(n) to constant time if the hint is correct. Its pretty obvious how this would work, since the container could just make sure the newly added item has a key that is less than the hint and has a key that is greater than the item before the hint. Otherwise the hint was wrong and it performs a normal insert.

std::unordered_map also has a similar insert with hint function. What, if anything, does the hint do? Its not obvious to me how another a "hint" iterator could be used to speed up a hash map insertion.

If it is used, what is an appropriate "hint". In std::map, the hint is typically found by calling lower_bound on the map.

Answer 1

It is an interface compatibility issue. Basically, the design is done considering the interface of std::map.

In other words, for std::unordered_map it does not differ a hint is provided or not.

Additional Information from the comments here:

The interface compatibility is very important because being able to quickly/easily switch between map and unordered_map provides the valuable flexibility of painlessly transition since performance is often the deciding factor in choosing one over the other.

Answer 2

The hint allows the unordered map implementation to do a value compare first to see if the hint works. This avoids having to do the hash function which can be more costly than a compare operation.