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

[• Quuxplusone]

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.

[ldionne]

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

[• Quuxplusone]

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]

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]

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.

[• Quuxplusone]

In D112836#3196476, @Quuxplusone wrote:

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. :)

libcxx/include/unordered_map

     const_iterator find(const _K2& __k) const      {return __table_.find(__k);}
 #endif // _LIBCPP_STD_VER > 17
 
     _LIBCPP_INLINE_VISIBILITY
     size_type count(const key_type& __k) const {return __table_.__count_unique(__k);}
 #if _LIBCPP_STD_VER > 17
     template <class _K2, enable_if_t<__is_transparent<hasher, _K2>::value && __is_transparent<key_equal, _K2>::value>* = nullptr>
     _LIBCPP_INLINE_VISIBILITY
-    size_type count(const _K2& __k) const      {return __table_.__count_unique(__k);}
+    size_type count(const _K2& __k) const      {return __table_.__count_multi(__k);}
 #endif // _LIBCPP_STD_VER > 17
 
 #if _LIBCPP_STD_VER > 17
     _LIBCPP_INLINE_VISIBILITY
     bool contains(const key_type& __k) const {return find(__k) != end();}
 
     template <class _K2, enable_if_t<__is_transparent<hasher, _K2>::value && __is_transparent<key_equal, _K2>::value>* = nullptr>
     _LIBCPP_INLINE_VISIBILITY
     bool contains(const _K2& __k) const      {return find(__k) != end();}
 #endif // _LIBCPP_STD_VER > 17
 
     _LIBCPP_INLINE_VISIBILITY
     pair<iterator, iterator>             equal_range(const key_type& __k)
         {return __table_.__equal_range_unique(__k);}
     _LIBCPP_INLINE_VISIBILITY
     pair<const_iterator, const_iterator> equal_range(const key_type& __k) const
         {return __table_.__equal_range_unique(__k);}
 #if _LIBCPP_STD_VER > 17
     template <class _K2, enable_if_t<__is_transparent<hasher, _K2>::value && __is_transparent<key_equal, _K2>::value>* = nullptr>
     _LIBCPP_INLINE_VISIBILITY
     pair<iterator, iterator>             equal_range(const _K2& __k)
-        {return __table_.__equal_range_unique(__k);}
+        {return __table_.__equal_range_multi(__k);}
     template <class _K2, enable_if_t<__is_transparent<hasher, _K2>::value && __is_transparent<key_equal, _K2>::value>* = nullptr>
     _LIBCPP_INLINE_VISIBILITY
     pair<const_iterator, const_iterator> equal_range(const _K2& __k) const
-        {return __table_.__equal_range_unique(__k);}
+        {return __table_.__equal_range_multi(__k);}
 #endif // _LIBCPP_STD_VER > 17
 
     mapped_type& operator[](const key_type& __k);
 #ifndef _LIBCPP_CXX03_LANG
     mapped_type& operator[](key_type&& __k);
 #endif
 
     mapped_type&       at(const key_type& __k);

libcxx/include/unordered_set

#if _LIBCPP_STD_VER > 17
     const_iterator find(const _K2& __k) const      {return __table_.find(__k);}
 #endif // _LIBCPP_STD_VER > 17
 
     _LIBCPP_INLINE_VISIBILITY
     size_type count(const key_type& __k) const {return __table_.__count_unique(__k);}
 #if _LIBCPP_STD_VER > 17
     template <class _K2, enable_if_t<__is_transparent<hasher, _K2>::value && __is_transparent<key_equal, _K2>::value>* = nullptr>
     _LIBCPP_INLINE_VISIBILITY
-    size_type count(const _K2& __k) const      {return __table_.__count_unique(__k);}
+    size_type count(const _K2& __k) const      {return __table_.__count_multi(__k);}
 #endif // _LIBCPP_STD_VER > 17
 
 #if _LIBCPP_STD_VER > 17
     _LIBCPP_INLINE_VISIBILITY
     bool contains(const key_type& __k) const {return find(__k) != end();}
 
     template <class _K2, enable_if_t<__is_transparent<hasher, _K2>::value && __is_transparent<key_equal, _K2>::value>* = nullptr>
     _LIBCPP_INLINE_VISIBILITY
     bool contains(const _K2& __k) const      {return find(__k) != end();}
 #endif // _LIBCPP_STD_VER > 17
 
     _LIBCPP_INLINE_VISIBILITY
     pair<iterator, iterator>             equal_range(const key_type& __k)
         {return __table_.__equal_range_unique(__k);}
     _LIBCPP_INLINE_VISIBILITY
     pair<const_iterator, const_iterator> equal_range(const key_type& __k) const
         {return __table_.__equal_range_unique(__k);}
 #if _LIBCPP_STD_VER > 17
     template <class _K2, enable_if_t<__is_transparent<hasher, _K2>::value && __is_transparent<key_equal, _K2>::value>* = nullptr>
     _LIBCPP_INLINE_VISIBILITY
     pair<iterator, iterator>             equal_range(const _K2& __k)
-        {return __table_.__equal_range_unique(__k);}
+        {return __table_.__equal_range_multi(__k);}
     template <class _K2, enable_if_t<__is_transparent<hasher, _K2>::value && __is_transparent<key_equal, _K2>::value>* = nullptr>
     _LIBCPP_INLINE_VISIBILITY
     pair<const_iterator, const_iterator> equal_range(const _K2& __k) const
-        {return __table_.__equal_range_unique(__k);}
+        {return __table_.__equal_range_multi(__k);}
 #endif // _LIBCPP_STD_VER > 17
 
     _LIBCPP_INLINE_VISIBILITY
     size_type bucket_count() const _NOEXCEPT {return __table_.bucket_count();}
     _LIBCPP_INLINE_VISIBILITY
     size_type max_bucket_count() const _NOEXCEPT {return __table_.max_bucket_count();}
 
     _LIBCPP_INLINE_VISIBILITY

libcxx/test/std/containers/associative/map/map.ops/count_transparent.pass.cpp

 
 // <map>
 
 // class map
 
 // template<typename K>
 //   size_type count(const K& x) const;        // C++14
 
-#include <cassert>
 #include <map>
+#include <cassert>
 #include <utility>
 
 struct Comp {
   using is_transparent = void;
 
   bool operator()(const std::pair<int, int> &lhs,
                   const std::pair<int, int> &rhs) const {
     return lhs < rhs;
   }
 
   bool operator()(const std::pair<int, int> &lhs, int rhs) const {
     return lhs.first < rhs;
   }
 
   bool operator()(int lhs, const std::pair<int, int> &rhs) const {
     return lhs < rhs.first;
   }
 };
 
 int main(int, char**) {
-  std::map<std::pair<int, int>, int, Comp> s{
-      {{2, 1}, 1}, {{1, 2}, 2}, {{1, 3}, 3}, {{1, 4}, 4}, {{2, 2}, 5}};
+  std::map<std::pair<int, int>, int, Comp> m = {
+    {{2, 1}, 1}, {{1, 2}, 2}, {{1, 3}, 3}, {{1, 4}, 4}, {{2, 2}, 5}
+  };
 
-  auto cnt = s.count(1);
+  auto cnt = m.count(1);
   assert(cnt == 3);
 
   return 0;
 }

libcxx/test/std/containers/associative/map/map.ops/equal_range_transparent.pass.cpp

 //===----------------------------------------------------------------------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 
 // UNSUPPORTED: c++03, c++11
 
 // <map>
 
 // class map
 
 // template<typename K>
-//         pair<iterator,iterator>             equal_range(const K& x); // C++14
+//     pair<iterator,iterator>             equal_range(const K& x);        // C++14
 // template<typename K>
-//         pair<const_iterator,const_iterator> equal_range(const K& x) const;
-//         // C++14
+//     pair<const_iterator,const_iterator> equal_range(const K& x) const;  // C++14
 
-#include <cassert>
 #include <map>
+#include <cassert>
 #include <utility>
 
 struct Comp {
   using is_transparent = void;
 
   bool operator()(const std::pair<int, int> &lhs,
                   const std::pair<int, int> &rhs) const {
     return lhs < rhs;
   }
 
   bool operator()(const std::pair<int, int> &lhs, int rhs) const {
     return lhs.first < rhs;
   }
 
   bool operator()(int lhs, const std::pair<int, int> &rhs) const {
     return lhs < rhs.first;
   }
 };
 
 int main(int, char**) {
-  std::map<std::pair<int, int>, int, Comp> s{
-      {{2, 1}, 1}, {{1, 2}, 2}, {{1, 3}, 3}, {{1, 4}, 4}, {{2, 2}, 5}};
+  std::map<std::pair<int, int>, int, Comp> m = {
+    {{2, 1}, 1}, {{1, 2}, 2}, {{1, 3}, 3}, {{1, 4}, 4}, {{2, 2}, 5}
+  };
 
-  auto er = s.equal_range(1);
+  auto er = m.equal_range(1);
   long nels = 0;
 
   for (auto it = er.first; it != er.second; it++) {
     assert(it->first.first == 1);
     nels++;
   }
-
   assert(nels == 3);
 
+  const auto& cm = m;
+  auto cer = cm.equal_range(1);
+  assert(cer.first == er.first);
+  assert(cer.second == er.second);
+
   return 0;
 }

libcxx/test/std/containers/associative/set/count_transparent.pass.cpp

 
 // <set>
 
 // class set
 
 //    template<typename K>
 //        size_type count(const K& x) const;        // C++14
 
-#include <cassert>
 #include <set>
+#include <cassert>
 #include <utility>
 
 struct Comp {
   using is_transparent = void;
 
   bool operator()(const std::pair<int, int> &lhs,
                   const std::pair<int, int> &rhs) const {
     return lhs < rhs;

libcxx/test/std/containers/associative/set/equal_range_transparent.pass.cpp

 //===----------------------------------------------------------------------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 
 // UNSUPPORTED: c++03, c++11
 
 // <set>
 
 // class set
 
 // template<typename K>
 //     pair<iterator,iterator>             equal_range(const K& x);        //
 //     C++14
 // template<typename K>
 //     pair<const_iterator,const_iterator> equal_range(const K& x) const;  //
 //     C++14
 
-#include <cassert>
 #include <set>
+#include <cassert>
 #include <utility>
 
 struct Comp {
   using is_transparent = void;
 
   bool operator()(const std::pair<int, int> &lhs,
                   const std::pair<int, int> &rhs) const {
     return lhs < rhs;
int main(int, char**) {
 
   auto er = s.equal_range(1);
   long nels = 0;
 
   for (auto it = er.first; it != er.second; it++) {
     assert(it->first == 1);
     nels++;
   }
-
   assert(nels == 3);
 
+  const auto& cs = s;
+  auto cer = cs.equal_range(1);
+  assert(cer.first == er.first);
+  assert(cer.second == er.second);
+
   return 0;
 }

libcxx/test/std/containers/unord/unord.map/count_transparent.pass.cpp

+//===----------------------------------------------------------------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+// UNSUPPORTED: c++03, c++11, c++14, c++17
+
+// <unordered_map>
+
+// class unordered_map
+
+// template<typename K>
+//   size_type count(const K& x) const;        // C++20
+
+#include <unordered_map>
+#include <cassert>
+#include <utility>
+
+struct Hash {
+  using is_transparent = void;
+
+  bool operator()(const std::pair<int, int>& x) const {
+    return std::hash<int>()(x.first);
+  }
+  bool operator()(int x) const {
+    return std::hash<int>()(x);
+  }
+};
+
+struct Eq {
+  using is_transparent = void;
+
+  bool operator()(const std::pair<int, int>& lhs,
+                  const std::pair<int, int>& rhs) const {
+    return lhs == rhs;
+  }
+
+  bool operator()(const std::pair<int, int>& lhs, int rhs) const {
+    return lhs.first == rhs;
+  }
+
+  bool operator()(int lhs, const std::pair<int, int>& rhs) const {
+    return lhs == rhs.first;
+  }
+};
+
+int main(int, char**) {
+  std::unordered_map<std::pair<int, int>, int, Hash, Eq> m = {
+    {{2, 1}, 1}, {{1, 2}, 2}, {{1, 3}, 3}, {{1, 4}, 4}, {{2, 2}, 5}
+  };
+
+  auto cnt = m.count(1);
+  assert(cnt == 3);
+
+  return 0;
+}

libcxx/test/std/containers/unord/unord.map/equal_range_transparent.pass.cpp

+//===----------------------------------------------------------------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+// UNSUPPORTED: c++03, c++11, c++14, c++17
+
+// <unordered_map>
+
+// class unordered_map
+
+// template<typename K>
+//     pair<iterator,iterator>             equal_range(const K& x);        // C++20
+// template<typename K>
+//     pair<const_iterator,const_iterator> equal_range(const K& x) const;  // C++20
+
+#include <unordered_map>
+#include <cassert>
+#include <utility>
+
+struct Hash {
+  using is_transparent = void;
+
+  bool operator()(const std::pair<int, int>& x) const {
+    return std::hash<int>()(x.first);
+  }
+  bool operator()(int x) const {
+    return std::hash<int>()(x);
+  }
+};
+
+struct Eq {
+  using is_transparent = void;
+
+  bool operator()(const std::pair<int, int>& lhs,
+                  const std::pair<int, int>& rhs) const {
+    return lhs == rhs;
+  }
+
+  bool operator()(const std::pair<int, int>& lhs, int rhs) const {
+    return lhs.first == rhs;
+  }
+
+  bool operator()(int lhs, const std::pair<int, int>& rhs) const {
+    return lhs == rhs.first;
+  }
+};
+
+int main(int, char**) {
+  std::unordered_map<std::pair<int, int>, int, Hash, Eq> m = {
+    {{2, 1}, 1}, {{1, 2}, 2}, {{1, 3}, 3}, {{1, 4}, 4}, {{2, 2}, 5}
+  };
+
+  auto er = m.equal_range(1);
+  long nels = 0;
+
+  for (auto it = er.first; it != er.second; it++) {
+    assert(it->first.first == 1);
+    nels++;
+  }
+  assert(nels == 3);
+
+  const auto& cm = m;
+  auto cer = cm.equal_range(1);
+  assert(cer.first == er.first);
+  assert(cer.second == er.second);
+
+  return 0;
+}

libcxx/test/std/containers/unord/unord.set/count_transparent.pass.cpp

+//===----------------------------------------------------------------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+// UNSUPPORTED: c++03, c++11, c++14, c++17
+
+// <unordered_set>
+
+// class unordered_set
+
+//    template<typename K>
+//        size_type count(const K& x) const;  // C++20
+
+#include <unordered_set>
+
+#include <cassert>
+#include <utility>
+
+struct Hash {
+  using is_transparent = void;
+
+  bool operator()(const std::pair<int, int>& x) const {
+    return std::hash<int>()(x.first);
+  }
+  bool operator()(int x) const {
+    return std::hash<int>()(x);
+  }
+};
+
+struct Eq {
+  using is_transparent = void;
+
+  bool operator()(const std::pair<int, int>& lhs,
+                  const std::pair<int, int>& rhs) const {
+    return lhs == rhs;
+  }
+
+  bool operator()(const std::pair<int, int>& lhs, int rhs) const {
+    return lhs.first == rhs;
+  }
+
+  bool operator()(int lhs, const std::pair<int, int>& rhs) const {
+    return lhs == rhs.first;
+  }
+};
+
+int main(int, char**) {
+  std::unordered_set<std::pair<int, int>, Hash, Eq> s{{2, 1}, {1, 2}, {1, 3}, {1, 4}, {2, 2}};
+
+  auto cnt = s.count(1);
+  assert(cnt == 3);
+
+  return 0;
+}

libcxx/test/std/containers/unord/unord.set/equal_range_transparent.pass.cpp

+//===----------------------------------------------------------------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+// UNSUPPORTED: c++03, c++11, c++14, c++17
+
+// <unordered_set>
+
+// class unordered_set
+
+// template<typename K>
+//     pair<iterator,iterator>             equal_range(const K& x);        // C++20
+// template<typename K>
+//     pair<const_iterator,const_iterator> equal_range(const K& x) const;  // C++20
+
+#include <unordered_set>
+#include <cassert>
+#include <utility>
+
+struct Hash {
+  using is_transparent = void;
+
+  bool operator()(const std::pair<int, int>& x) const {
+    return std::hash<int>()(x.first);
+  }
+  bool operator()(int x) const {
+    return std::hash<int>()(x);
+  }
+};
+
+struct Eq {
+  using is_transparent = void;
+
+  bool operator()(const std::pair<int, int>& lhs,
+                  const std::pair<int, int>& rhs) const {
+    return lhs == rhs;
+  }
+
+  bool operator()(const std::pair<int, int>& lhs, int rhs) const {
+    return lhs.first == rhs;
+  }
+
+  bool operator()(int lhs, const std::pair<int, int>& rhs) const {
+    return lhs == rhs.first;
+  }
+};
+
+int main(int, char**) {
+  std::unordered_set<std::pair<int, int>, Hash, Eq> s{{2, 1}, {1, 2}, {1, 3}, {1, 4}, {2, 2}};
+
+  auto er = s.equal_range(1);
+  long nels = 0;
+
+  for (auto it = er.first; it != er.second; it++) {
+    assert(it->first == 1);
+    nels++;
+  }
+  assert(nels == 3);
+
+  const auto& cs = s;
+  auto cer = cs.equal_range(1);
+  assert(cer.first == er.first);
+  assert(cer.second == er.second);
+
+  return 0;
+}