Title
Equality can be defined when Hash function objects have different behaviour
Status
resolved
Section
[unord.req]
Submitter
Daniel James

Created on 2016-11-24.00:00:00 last changed 73 months ago

Messages

Date: 2018-03-18.23:10:06

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

Date: 2018-03-17.00:00:00

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

Date: 2017-01-27.00:00:00

[ 2017-01-27 Telecon ]

This is a design issue; send to LEWG

Date: 2016-11-24.00:00:00

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"

History
Date User Action Args
2018-03-18 23:10:06adminsetmessages: + msg9757
2018-03-18 23:10:06adminsetstatus: lewg -> resolved
2017-01-30 15:17:53adminsetmessages: + msg8807
2017-01-30 15:17:53adminsetstatus: new -> lewg
2016-12-10 13:34:59adminsetmessages: + msg8710
2016-11-24 00:00:00admincreate