c++unordered-setunordered-multiset

Does std::unordered_multiset::find function return the first inserted element between two values with same hash value


Saying we have std::unordered_multiset with two values mapping the same hash value, is there any guarantees by the c++ standard that a find will return the first inserted element ?


Solution

  • I'm assuming your question is about two keys that not only generate the same hash value, but also compare equal using the equality predicate supplied to the unordered_multiset. unordered_multiset::find will only use the hash value to initially locate the bucket within which to search, but after that the search is done using the equality predicate.

    §23.2.5 [unord.req] Table 103 — Unordered associative container requirements

    b.find(k)

    Returns an iterator pointing to an element with key equivalent to k, or b.end() if no such element exists.

    No additional requirements for find() are placed upon the unordered_multi* containers. This means implementations are not required that unordered_multiset::find return an iterator to the first inserted element. But then again, if the two (or more) keys are truly equivalent, why would you care?