Does std::unordered_map equality depend on insertion order

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.

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.

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.