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 have object 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 `i`th 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 have has 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`.