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?
I'e done some testing, and from what I saw, it looked like the hint was completely ignored by std::unordered_map. I couldn't find any value to pass to it that seemed to provide any advantage at all.
The standard explicitly gives implementations of the unordered collections to ignore the hint passed to emplace_hint, and I think most (if not all) normally do. The specification doesn't really say whether you should be passing an iterator to the value being inserted (if there is one) or to one past it (like you would with the ordered associative collections). Given that it's hash-based, an iterator to near the correct insertion point is probably useless. As such, for it to have any hope of doing any good, it probably needs to be an iterator to the actual insertion point (e.g., one that has the same key as you're inserting, if you try to insert a duplicate).
I doubt there's any value you can pass that provides any significant advantage (and in testing, I haven't found one that does).
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_typeis Cpp17EmplaceConstructible intoXfromargs.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. Theconst_iteratorpis 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_iteratorpis 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.
cendas a hint then? – um ... that thing is unordered