Misspecified transitivity of equivalence in §[unord.req.general]
Thomas Köppe

Created on 2021-10-20.00:00:00 last changed 10 months ago


Date: 2022-01-29.22:29:35

Proposed resolution:

This wording is relative to N4901.

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

Date: 2022-01-15.00:00:00

[ 2022-01-29; Reflector poll ]

Set priority to 2 after reflector poll.

Date: 2021-10-24.12:04:41

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.

Date User Action Args
2022-01-29 22:29:35adminsetmessages: + msg12290
2021-10-23 17:40:08adminsetmessages: + msg12187
2021-10-20 00:00:00admincreate