Determinism with insert in unordered containers

Question

If I insert the same (size and value) elements in two unordered containers, will traversing the containers with two iterators always give the same element in the same position?

If yes, can a (single!) hash function be made to break this determinism ?

Truscott

There are no such guarantees, so you can assume it won't. For instance, it is easy to imagine an implementation where the position of two elements that clash will be determined by the order of insertion. – Lysine

Answer 1

It depends: if you insert the same elements in the same order into two different unordered containers, then the order should be the same across both containers, even though the order itself is unspecified.

The reasoning is a little convoluted: all operations like hash(k) and the reallocations are deterministic. There is no actual quote in the Standard though, but the ability to do a find() in O(1) after an insert() seems to rule out any kind of randomized or otherwise non-deterministic insertion.

However, if you change the order of insertion, then all bets are off because internal reallocations will change the order of elements:

23.2.5 Unordered associative containers [unord.req]

9 The elements of an unordered associative container are organized into buckets. Keys with the same hash code appear in the same bucket. The number of buckets is automatically increased as elements are added to an unordered associative container, so that the average number of elements per bucket is kept below a bound. Rehashing invalidates iterators, changes ordering between elements, and changes which buckets elements appear in, but does not invalidate pointers or references to elements. For unordered_multiset and unordered_multimap, rehashing preserves the relative ordering of equivalent elements.

Goodygoody