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

Question

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 ?

Answer 1

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?

Answer 2

Interesting question. Haven't used unordered associative containers a lot, so I took the chance to search the standard. Here is my interpretation: 23.2.5.6 says

"In containers that support equivalent keys, elements with equivalent keys are adjacent to each other in the iteration order of the container. Thus, although the absolute order of elements in an unordered container is not specified, its elements are grouped into equivalent-key groups such that all elements of each group have equivalent keys."

But then continues with

"Mutating operations on unordered containers shall preserve the relative order of elements within each equivalent-key group unless otherwise specified."

23.2.5.9 then states

"For unordered_multiset and unordered_multimap, rehashing preserves the relative ordering of equivalent elements."

So the order seems to be preserved, because insert does not say that it may change the order of equivalent keys. But then, find is specified as

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

So, it does not defined which element of the equivalent keys ones it returns. Strictly, this may return a random element with given key and still fulfill the specification. Given that equal_range is defined as

Returns a range containing all elements with keys equivalent to k.

*equal_range(k).first could do the job and return the first element inserted with key k.