- Title
- Misspecified transitivity of equivalence in §[unord.req.general]
- Status
- new
- Section
- [unord.req.general]
- Submitter
- Thomas Köppe

Created on **2021-10-20.00:00:00**
last changed **1 month ago**

Date: 2021-10-24.08:46:27

**Proposed resolution:**

This wording is relative to N4901.

Modify [unord.req.general] as indicated:

[…]

(11.19) —

`ke`is a value such that(11.19.1) —

`eq(r1, ke) == eq(ke, r1)`,(11.19.2) —

`hf(r1) == hf(ke)`if`eq(r1, ke)`is`true`, and(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`,(11.20) —

`kx`is a value such that(11.20.1) —

`eq(r1, kx) == eq(kx, r1)`,(11.20.2) —

`hf(r1) == hf(kx)`if`eq(r1, kx)`is`true`,(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(11.20.4) —

`kx`is not convertible to either`iterator`or`const_iterator`,

where

`r1`and`r2`are keys of elements in`a_tran`,[…]

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:

"

kxis a value such that […](eq(r1, kx) && eq(r1, r2)) == eq(r2, kx)[…], wherer1andr2are [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.

History | |||
---|---|---|---|

Date | User | Action | Args |

2021-10-23 17:40:08 | admin | set | messages: + msg12187 |

2021-10-20 00:00:00 | admin | create |