2831. Equality can be defined when Hash function objects have different behaviour

Section: 23.2.8 [unord.req] Status: Resolved Submitter: Daniel James Opened: 2016-11-24 Last modified: 2020-09-06

Priority: Not Prioritized

View other active issues in [unord.req].

View all other issues in [unord.req].

View all issues with Resolved status.

Discussion:

In 23.2.8 [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 23.2.8 [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"

[2017-01-27 Telecon]

This is a design issue; send to LEWG

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

Proposed resolution:

This wording is relative to N4618.

  1. Change 23.2.8 [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 N2 in the worst case, where N is a.size(). For unordered_multiset and unordered_multimap, the complexity of operator== is proportional to ∑ Ei2 in the average case and to N2 in the worst case, where N is a.size(), and Ei is the size of the ith equivalent-key group in a. However, if the respective elements of each corresponding pair of equivalent-key groups Eai and Ebi 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 𝒪(N2), 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.