3622. Misspecified transitivity of equivalence in §[unord.req.general]

Section: 23.2.8.1 [unord.req.general] Status: C++23 Submitter: Thomas Köppe Opened: 2021-10-20 Last modified: 2023-11-22

Priority: 2

View all issues with C++23 status.

Discussion:

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, 23.2.8.1 [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.

[2022-01-29; Reflector poll]

Set priority to 2 after reflector poll.

Previous resolution [SUPERSEDED]:

This wording is relative to N4901.

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

   1. […]

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

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

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

      3. (11.19.3) — (eq(r1, ke) && eq(r1, r2)) == eq(r2, ke)eq(ke, r2) is true if eq(ke, r1) && eq(r1, r2) is true,

      where r1 and r2 are keys of elements in a_tran,

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

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

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

      3. (11.20.3) — (eq(r1, kx) && eq(r1, r2)) == eq(r2, kx)eq(kx, r2) is true if eq(kx, r1) && eq(r1, r2) is true, and

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

      where r1 and r2 are keys of elements in a_tran,

   4. […]

[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:

[Issaquah 2023-02-08; LWG]

Move to Immediate for C++23

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

Proposed resolution:

This wording is relative to N4928.

1. Modify 23.2.8.1 [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. […]