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: 22.2.7.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, 22.2.7.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 22.2.7.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. […]