CODEWITHSUNDEEP
c++unordered-map
Raedwald
Raedwald

Reputation: 48674

Does std::unordered_map equality depend on insertion order

If you create two std::unordered_map containers using the same set of (non equal) key-value pairs, but inserted in a different order (so the containers hold equal elements, but potentially in different orders), are the containers guaranteed to be equal, according to the equality operator (operator==). I'm assuming that the hash-code and equality operators of the container elements satisfy all the required constraints on their implementation.

Upvotes: 36

Views: 6906

Answers (3)

Jerry Coffin
Jerry Coffin

Reputation: 490108

Yes, they're guaranteed to return equal in this case. The specific wording (from N4659, §[unord.req]/12) is:

Two unordered containers a and b compare equal if a.size() == b.size() and, for every equivalent-key group [Ea1, Ea2) obtained from a.equal_range(Ea1), there exists an equivalent-key group [Eb1, Eb2) obtained from b.equal_range(Ea1), such that is_permutation(Ea1, Ea2, Eb1, Eb2) returns true.

So, as long as the keys (and associated values) in one are the same as the other (but possibly in a differently-permuted order), it will compare equal.

Upvotes: 33

acarlstein
acarlstein

Reputation: 1838

Below are quotes from cppreference.com about the std:unordered_map, operator==,!=(std::unordered_map):

The contents of two unordered containers lhs and rhs are equal if the following conditions hold:

  • lhs.size() == rhs.size()
  • each group of equivalent elements [lhs_eq1, lhs_eq2) obtained from lhs.equal_range(lhs_eq1) has a corresponding group of equivalent elements in the other container [rhs_eq1, rhs_eq2) obtained from rhs.equal_range(rhs_eq1), that has the following properties:
    • std::distance(lhs_eq1, lhs_eq2) == std::distance(rhs_eq1, rhs_eq2).
    • std::is_permutation(lhs_eq1, lhs_eq2, rhs_eq1) == true.

Note that:

The behavior is undefined if Key or T are not EqualityComparable.

The behavior is also undefined if Hash and KeyEqual do (until C++20)KeyEqual does (since C++20) not have the same behavior on lhs and rhs or if operator== for Key is not a refinement of the partition into equivalent-key groups introduced by KeyEqual (that is, if two elements that compare equal using operator== fall into different partitions)

Finally, to consider is the complexity:

Proportional to N calls to operator== on value_type, calls to the predicate returned by key_eq, and calls to the hasher returned by hash_function, in the average case, proportional to N2 in the worst case where N is the size of the container.

Therefore, if both unordered maps have the same size, and each key in one of the containers is looked for in the other plus, if it happens to be found then their values are compared then they are the considered the same.

Upvotes: 3

NathanOliver
NathanOliver

Reputation: 180585

From [unord.red]/12

Two unordered containers a and b compare equal if a.size() == b.size() and, for every equivalent-key group [Ea1, Ea2) obtained from a.equal_­range(Ea1), there exists an equivalent-key group [Eb1, Eb2) obtained from b.equal_­range(Ea1), such that is_­permutation(Ea1, Ea2, Eb1, Eb2) returns true. [...]

So, as long as the keys are the same and the size is the same the containers will compare equal no matter what order the keys are in.

Upvotes: 14

Related Questions