Is the order of two identical unordered_maps the same?
In other words, if I populate two unordered_map
or unordered_set
, objects with exactly the same content and the same hashing function will iterate over them, giving the same sequence of key / value pairs?
If so, what are the conditions for this (for example, the same hashing function, the same keys, not necessarily the same values).
source to share
In this case, the behavior is undefined. So, in some situations the sequence will be the same, in others it will be different. You cannot be sure of anything. The types you mentioned are called disordered for a reason. Using them as ordered is very very bad and extremely dangerous style.
You may find that your compiler behaves in a certain way that you would like to use. But you cannot be sure. You don't have to be sure! You don't know what conditions are causing this compiler behavior. You can never be sure that any change in the compiler version will not change your behavior.
What is simply forbidden in other languages is not specified in C / C ++. But you should also take it as taboo.
See the c-faq on the undefined behavior issue. This concept is common to all C / C ++
source to share
Ok first I'll quote MSDN :
The actual order of items in the controlled sequence depends on the hash function, compare function, insertion order, maximum load factor, and the current number of buckets. You cannot predict the order of items in a controlled sequence at all. However, you can always be sure that any subset of elements that have an equivalent ordering are contiguous in a controlled sequence.
The above quote is the same for unordered_map
and unordered_set
, and since the name implies no sequence is specified, however they mention that the equivalent keys are contiguous.
source to share
If you want a guaranteed order, this is not for you. In fact, if you're basically going to be iterating over, is unordered_map/set
n't the data structure for you.
For iteration, a std::map
will turn out to be a better data structure, since gonig from one node to the next will be less algorithmically complex. And the iteration order for objects in is std::map
guaranteed by the spec (and is actually a defining property of the structure itself). (This is all assuming you are using the same comparison operator, obviously). In std::map
no part hashing.
Suffice it to say, it sounds like you are barking up the wrong tree here. unordered_map
should usually be used for benefits like O (1) rather than storing a list of objects and then iterating over them. This should definitely not be used if you are trying to get a deterministic iteration order.
source to share