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

4 answers

Not. For example, there is no requirement that objects having the same hash be placed in any particular order. In fact, it is generally impossible for an unordered map to do this, because the only information it has access to is the hash value.



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 ++



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.



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.



All Articles