Hint when inserting/emplacing new element into unordered_map/unordered_set

Question

If I am inserting a new element (key not present) into std::unordered_map, can I increase performance with emplace_hint? And what value should the hint have?

Often I know that key value (of integral type) is larger than all the keys in the map. Should I use cend as a hint then?

Answer 1

emplace_hint is not really needed when using an unordered container. Unlike a std::map where you have a guaranteed order and using end as the hint would give you constant emplacement, the unordered version already has constant emplacement.

If we look at Table 70 — Unordered associative container requirements (in addition to container) we have

Expects: value_­type is Cpp17EmplaceConstructible into X from args.

Effects: Equivalent to a.emplace( std::forward<​Args>(​args)...). Return value is an iterator pointing to the element with the key equivalent to the newly inserted element. The const_­iterator p is a hint pointing to where the search should start. Implementations are permitted to ignore the hint.

and you can see you aren't even guaranteed that providing a hint will do anything.

The line

The const_­iterator p is a hint pointing to where the search should start

leads me to believe the iterator needs to be at the beginning of the bucket the element would be placed, so end/cend would not be what you want to use.