This page is a snapshot from the LWG issues list, see the Library Active Issues List for more information and the meaning of New status.

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

Section: 24.2.8.1 [unord.req.general] Status: New Submitter: Thomas Köppe Opened: 2021-10-20 Last modified: 2021-10-24

Priority: 2

View all issues with New 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, 24.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.

Proposed resolution:

This wording is relative to N4901.

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