This page is a snapshot from the LWG issues list, see the Library Active Issues List for more information and the meaning of Resolved status.

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

Section: 24.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 24.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 24.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 24.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.