This page is a snapshot from the LWG issues list, see the Library Active Issues List for more information and the meaning of C++23 status.
Section: 24.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, 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)
[…], wherer1
andr2
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.
Modify 24.2.8.1 [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)
ifeq(r1, ke)
istrue
, and(11.19.3) —
(eq(r1, ke) && eq(r1, r2)) == eq(r2, ke)
eq(ke, r2)
istrue
ifeq(ke, r1) && eq(r1, r2)
istrue
,where
r1
andr2
are keys of elements ina_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)
ifeq(r1, kx)
istrue
,(11.20.3) —
(eq(r1, kx) && eq(r1, r2)) == eq(r2, kx)
eq(kx, r2)
istrue
ifeq(kx, r1) && eq(r1, r2)
istrue
, and(11.20.4) —
kx
is not convertible to eitheriterator
orconst_iterator
,where
r1
andr2
are keys of elements ina_tran
,[…]
[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:
eq(r1, ke)
is true
and eq(r1, r2)
is true
then eq(r2, ke)
is true
.
eq(r1, ke)
is true
and eq(r2, ke)
is true
then eq(r1, r2)
is true
In a table:
eq(r1, ke) | eq(r1, r2) | eq(r2, ke) | OK? |
---|---|---|---|
T | T | T | Y |
T | T | F | N |
T | F | T | N |
T | F | F | Y |
F | T | T | N |
F | T | F | Y |
F | F | T | Y |
F | F | F | Y |
[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.
Modify 24.2.8.1 [unord.req.general] as indicated:
[…]
(10.20) —
ke
is a value such that
(10.20.1) —
eq(r1, ke) == eq(ke, r1)
,(10.20.2) —
hf(r1) == hf(ke)
ifeq(r1, ke)
istrue
, and(10.20.3) —
if any two of(eq(r1, ke) && eq(r1, r2)) == eq(r2, ke)
eq(r1, ke)
,eq(r2, ke)
andeq(r1, r2)
aretrue
, then all three aretrue
,where
r1
andr2
are keys of elements ina_tran
,(10.21) —
kx
is a value such that
(10.21.1) —
eq(r1, kx) == eq(kx, r1)
,(10.21.2) —
hf(r1) == hf(kx)
ifeq(r1, kx)
istrue
,(10.21.3) —
if any two of(eq(r1, kx) && eq(r1, r2)) == eq(r2, kx)
eq(r1, kx)
,eq(r2, kx)
andeq(r1, r2)
aretrue
, then all three aretrue
, and(10.21.4) —
kx
is not convertible to eitheriterator
orconst_iterator
,where
r1
andr2
are keys of elements ina_tran
,[…]