Proposed resolution:

This wording is relative to N4928.

1. Modify [unord.req.general] as indicated:

   1. […]

   2. (10.20) — ke is a value such that

      1. (10.20.1) — eq(r1, ke) == eq(ke, r1),

      2. (10.20.2) — hf(r1) == hf(ke) if eq(r1, ke) is true, and

      3. (10.20.3) — (eq(r1, ke) && eq(r1, r2)) == eq(r2, ke)if any two of eq(r1, ke), eq(r2, ke) and eq(r1, r2) are true, then all three are true,

      where r1 and r2 are keys of elements in a_tran,

   3. (10.21) — kx is a value such that

      1. (10.21.1) — eq(r1, kx) == eq(kx, r1),

      2. (10.21.2) — hf(r1) == hf(kx) if eq(r1, kx) is true,

      3. (10.21.3) — (eq(r1, kx) && eq(r1, r2)) == eq(r2, kx)if any two of eq(r1, kx), eq(r2, kx) and eq(r1, r2) are true, then all three are true, and

      4. (10.21.4) — kx is not convertible to either iterator or const_iterator,

      where r1 and r2 are keys of elements in a_tran,

   4. […]

[ 2023-02-13 Approved at February 2023 meeting in Issaquah. Status changed: Immediate → WP. ]

[ Issaquah 2023-02-08; LWG ]

Move to Immediate for C++23

[ 2022-02-07 Tim comments and provides updated wording ]

For heterogeneous lookup on unordered containers to work properly, we need all keys comparing equal to the transparent key to be grouped together. Since the only keys guaranteed to be so grouped are the ones that are equal according to eq, we cannot allow eq(r1, r2) == false but eq(r1, ke) == true && eq(r2, ke) == true. The one-way transitivity of equality is insufficient.

We need both of the following:

• if eq(r1, ke) is true and eq(r1, r2) is true then eq(r2, ke) is true.
• if eq(r1, ke) is true and eq(r2, ke) is true then eq(r1, r2) is true

In a table:

[ 2022-01-29; Reflector poll ]

Set priority to 2 after reflector poll.

The paper P2077R3 ("Heterogeneous erasure overloads for associative containers") adds a new variable kx with specific meaning for use in the Table of Unordered Associative Container Requirements, [unord.req.general] p11, which is meant to stand for an equivalence class of heterogeneous values that can be compared with container keys.

One property required of kx is transitivity of equality/equivalence, but this is currently specified as:

"kx is a value such that […] (eq(r1, kx) && eq(r1, r2)) == eq(r2, kx) […], where r1 and r2 are [any] keys".

But this doesn't seem right. Transitivity means that eq(r1, kx) && eq(r1, r2) being true implies eq(r2, kx) being true, but it does not imply that both sides are equal in general. In particular, eq(r2, kx) can be true even when eq(r1, kx) && eq(r1, r2) is false.

More abstractly, equality is transitive, but inequality is not.

The new wording appears to have been copied from the pre-existing wording for the variable "ke", which suffers from the same problem, and so we propose to fix both cases.