Proposed resolution:

This wording is relative to N4618.

1. Change [unord.req] as indicated:

   -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. For unordered_set and unordered_map, the complexity of operator== (i.e., the number of calls to the == operator of the value_type, to the predicate returned by key_eq(), and to the hasher returned by hash_function()) is proportional to N in the average case and to N² in the worst case, where N is a.size(). For unordered_multiset and unordered_multimap, the complexity of operator== is proportional to ∑ E_i² in the average case and to N² in the worst case, where N is a.size(), and E_i is the size of the ith equivalent-key group in a. However, if the respective elements of each corresponding pair of equivalent-key groups Ea_i and Eb_i are arranged in the same order (as is commonly the case, e.g., if a and b are unmodified copies of the same container), then the average-case complexity for unordered_multiset and unordered_multimap becomes proportional to N (but worst-case complexity remains 𝒪(N²), e.g., for a pathologically bad hash function). The behavior of a program that uses operator== or operator!= on unordered containers is undefined unless the Hash and Pred function objects respectively havehas the same behavior for both containers and the equality comparison operator for Key is a refinement(footnote 258) of the partition into equivalent-key groups produced by Pred.

[ 2018-3-17 Resolved by P0809R0, which was adopted in Jacksonville. ]

[ 2017-01-27 Telecon ]

This is a design issue; send to LEWG

In [unord.req] paragraph 12, it says that the behaviour of operator== is undefined unless the Hash and Pred function objects respectively have the same behaviour. This makes comparing containers with randomized hashes with different seeds undefined behaviour, but I think that's a valid use case. It's not much more difficult to support it when the Hash function objects behave differently. I did a little testing and both libstdc++ and libc++ appear to support this correctly.

I suggest changing the appropriate sentence in [unord.req] paragraph 12: "The behavior of a program that uses operator== or operator!= on unordered containers is undefined unless the Hash and Pred function objects respectively haveobject has the same behavior for both containers and the equality comparison operator for Key is a refinement"