Page MenuHomePhabricator

[libc++] Transparent unordered_foo::count() should use __count_multi.
AbandonedPublic

Authored by Quuxplusone on Oct 29 2021, 10:33 AM.

Details

Reviewers
rarutyun
mclow.lists
ldionne
Group Reviewers
Restricted Project
Summary
An `unordered_set` doesn't contain duplicates of the key_type, but it
may contain "duplicates" in the less-granular equivalence relationship
imposed by the transparent hasher/comparator on non-key_type objects.
The new tests are copied from the existing tests for `set` and `map`.
Thanks to Marshall Clow for highlighting this issue/use-case.

N.B.: I just copied the existing count_transparent.pass.cpp from set... but that gives us both Marshall's count_transparent.pass.cpp and Ruslan's count.transparent.pass.cpp. This is probably a terrible idea, so I'm open to suggestions for new test names.

It might also be a good idea for us to have a "neg test" proving that m.insert({Tuple2{1,2}, 3}) does not use heterogeneous lookup — it deliberately converts Tuple2 into Tuple3 and then looks up the Tuple3 according to the more granular equivalence relation.

Diff Detail

Event Timeline

Quuxplusone requested review of this revision.Oct 29 2021, 10:33 AM
Quuxplusone created this revision.
Herald added 1 blocking reviewer(s): Restricted Project. · View Herald TranscriptOct 29 2021, 10:33 AM
ldionne accepted this revision.Oct 29 2021, 12:28 PM

N.B.: I just copied the existing count_transparent.pass.cpp from set... but that gives us both Marshall's count_transparent.pass.cpp and Ruslan's count.transparent.pass.cpp. This is probably a terrible idea, so I'm open to suggestions for new test names.

Can we rename all count_transparent.pass.cpp tests to count.transparent.pass.cpp, and merge the ones you are adding for the unordered containers with the ones that already exist (Ruslan's)?

FWIW I'm fine with this as-is once we figure out the naming of tests.

libcxx/test/std/containers/associative/set/equal_range_transparent.pass.cpp
16–20
This revision is now accepted and ready to land.Oct 29 2021, 12:28 PM
Quuxplusone planned changes to this revision.Nov 1 2021, 8:52 AM
Quuxplusone marked an inline comment as done.

Actually, now I am much less sure that @mclow.lists's example is supposed to work, even for regular set.
https://godbolt.org/z/PxG5avYv1
The requirements in https://eel.is/c++draft/unord.req seem physically impossible to implement — how can we get a range a_­tran.equal_­range(ke) when those elements are not guaranteed to be stored consecutively in the container? I'll email LWG.

libcxx/test/std/containers/unord/unord.set/equal_range_transparent.pass.cpp
27–30

s/bool/size_t/

rarutyun added a comment.EditedNov 8 2021, 1:43 PM

Thanks for creating the review for this issue. To be honest when implementing this stuff I didn't realize that unique containers may return multiple results in heterogeneous case. Currently I know that because this question is very relevant to the https://wg21.link/P2363 paper.

When thinking about unordered containers we (as authors of mentioned paper) were not able to find the good example for multiple values to be returned. Thus, I believe multiple values are relevant for ordered unique containers only (as @Quuxplusone pointed out) because we don't know the order of elements within unordered container.

Thanks again to keeping me in the loop because, first, it's interesting problem, second, this review might help with some answers for P2363.

Quuxplusone abandoned this revision.Dec 15 2021, 7:45 PM

I convinced myself (quite a while ago now) that the main thrust of this PR was misguided — @kboyarinov's version is correct as written AFAIK. And I don't think my test changes are particularly worth saving either.

I convinced myself (quite a while ago now) that the main thrust of this PR was misguided — @kboyarinov's version is correct as written AFAIK. And I don't think my test changes are particularly worth saving either.

...Er, @rarutyun's version. Whoever it was I meant to tag. Sorry. :)