Menu
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 ?
986
The order in an std::unordered_set<T> is, well, unordered. However, assuming a deterministic hash is used and the same order of insert operations is done, different runs of a program will have the elements in the same order.
Unlike with lists, we cannot insert an element at a given index, since sets are unordered containers, meaning elements have not a particular position inside a set.
7 Answers. Show activity on this post. The main difference is that if you iterate through an ordered container by incrementing the iterator, you'll visit the elements of the container in the order of the keys. That doesn't necessarily hold for unordered containers.
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.
51
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
