CODEWITHSUNDEEP
c++c++11unordered-mapunordered-set
user2052436
user2052436

Reputation: 4765

Hint when inserting/emplacing new element into unordered_map/unordered_set

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?

Upvotes: 3

Views: 542

Answers (2)

Jerry Coffin
Jerry Coffin

Reputation: 490653

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).

Summary

I doubt there's any value you can pass that provides any significant advantage (and in testing, I haven't found one that does).

Upvotes: 3

NathanOliver
NathanOliver

Reputation: 181027

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.

Upvotes: 2

Related Questions