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.
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[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.
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 andPred 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.