Heterogeneous lookup for unordered containers (P0919R3)

[zoecarver]

Summary

Implements P0919R3.

[zoecarver]

include/__hash_table

36

Not quite sure if this is the correct place for this to go, but didn't want to duplicate code.

include/unordered_map

428

Also not sure if this is where this should go.

test/std/containers/key_equal.fail.cpp

27

These comments describe errors in other files. What line should they go on and how should they be formatted?

[zoecarver]

Friendly ping. I am waiting on this patch to get done before I submit a patch for precalculated hashes (which is mostly done).

[mclow.lists]

In D59886#1472488, @zoecarver wrote:

Friendly ping. I am waiting on this patch to get done before I submit a patch for precalculated hashes (which is mostly done).

Please hold off on the pre-calculated hashes, since I have been informed that there will be a paper discussed in Cologne about reverting that change (removing that feature).

[mclow.lists]

Here's a few nits; I'm still working on the code.

include/unordered_map

176

These all need a comment // C++20

363

// C++20 comments here too

428

This should go in <version>. Then there's a tool to regenerate the version tests.

test/std/containers/key_equal.fail.cpp

27

You just say expected-error@<filename>:<line number> ; and you can use * for the line number (in fact, you should).

[zoecarver]

test/std/containers/hetro_lookups.pass.cpp

1

I will split this into four tests.

test/std/containers/key_equal.fail.cpp

27

Will do.

[zoecarver]

Closing in favor of D87171.

include/__hash_table

 #endif
 
 _LIBCPP_PUSH_MACROS
 #include <__undef_macros>
 
 
 _LIBCPP_BEGIN_NAMESPACE_STD
 
+
+template<class _Hash, class _Pred, class = void>
+struct __key_equal {
+    using type = _Pred;
+};
+
+template<class _Hash, class _Pred>
+struct __key_equal<_Hash, _Pred, typename __void_t<typename _Hash::transparent_key_equal>::type>  {
+    using type = typename _Hash::transparent_key_equal;
+};
+
 template <class _Key, class _Tp>
 struct __hash_value_type;
 
 #ifndef _LIBCPP_CXX03_LANG
 template <class _Tp>
 struct __is_hash_value_type_imp : false_type {};
 
 template <class _Key, class _Value>

include/unordered_map

template <class Key, class T, class Hash = hash<Key>, class Pred = equal_to<Key>,
           class Alloc = allocator<pair<const Key, T>>>
 class unordered_map
 {
 public:
     // types
     typedef Key                                                        key_type;
     typedef T                                                          mapped_type;
     typedef Hash                                                       hasher;
-    typedef Pred                                                       key_equal;
+    typedef see [unord.req]                                            key_equal;
     typedef Alloc                                                      allocator_type;
     typedef pair<const key_type, mapped_type>                          value_type;
     typedef value_type&                                                reference;
     typedef const value_type&                                          const_reference;
     typedef typename allocator_traits<allocator_type>::pointer         pointer;
     typedef typename allocator_traits<allocator_type>::const_pointer   const_pointer;
     typedef typename allocator_traits<allocator_type>::size_type       size_type;
     typedef typename allocator_traits<allocator_type>::difference_type difference_type;
void swap(unordered_map&)
             __is_nothrow_swappable<hasher>::value &&
             __is_nothrow_swappable<key_equal>::value);
 
     hasher hash_function() const;
     key_equal key_eq() const;
 
     iterator       find(const key_type& k);
     const_iterator find(const key_type& k) const;
+    template <class K> iterator       find(const K& k);
+    template <class K> const_iterator find(const K& k) const;
     size_type count(const key_type& k) const;
+    template <class K> size_type count(const K& k) const;
     pair<iterator, iterator>             equal_range(const key_type& k);
     pair<const_iterator, const_iterator> equal_range(const key_type& k) const;
+    template <class K> pair<iterator, iterator>             equal_range(const K& k);
+    template <class K> pair<const_iterator, const_iterator> equal_range(const K& k) const;
 
     mapped_type& operator[](const key_type& k);
     mapped_type& operator[](key_type&& k);
 
     mapped_type&       at(const key_type& k);
     const mapped_type& at(const key_type& k) const;
 
     size_type bucket_count() const noexcept;
template <class Key, class T, class Hash = hash<Key>, class Pred = equal_to<Key>,
           class Alloc = allocator<pair<const Key, T>>>
 class unordered_multimap
 {
 public:
     // types
     typedef Key                                                        key_type;
     typedef T                                                          mapped_type;
     typedef Hash                                                       hasher;
-    typedef Pred                                                       key_equal;
+    typedef see [unord.req]                                            key_equal;
     typedef Alloc                                                      allocator_type;
     typedef pair<const key_type, mapped_type>                          value_type;
     typedef value_type&                                                reference;
     typedef const value_type&                                          const_reference;
     typedef typename allocator_traits<allocator_type>::pointer         pointer;
     typedef typename allocator_traits<allocator_type>::const_pointer   const_pointer;
     typedef typename allocator_traits<allocator_type>::size_type       size_type;
     typedef typename allocator_traits<allocator_type>::difference_type difference_type;
void swap(unordered_multimap&)
             __is_nothrow_swappable<key_equal>::value);
 
     hasher hash_function() const;
     key_equal key_eq() const;
 
     iterator       find(const key_type& k);
     const_iterator find(const key_type& k) const;
     size_type count(const key_type& k) const;
+    template <class K> size_type count(const K& k) const;
     pair<iterator, iterator>             equal_range(const key_type& k);
     pair<const_iterator, const_iterator> equal_range(const key_type& k) const;
+    template <class K> pair<iterator, iterator>             equal_range(const K& k);
+    template <class K> pair<const_iterator, const_iterator> equal_range(const K& k) const;
 
     size_type bucket_count() const noexcept;
     size_type max_bucket_count() const noexcept;
 
     size_type bucket_size(size_type n) const;
     size_type bucket(const key_type& k) const;
 
     local_iterator       begin(size_type n);

 #include <version>
 
 #include <__debug>
 
 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
 #pragma GCC system_header
 #endif
 
+#define __cpp_lib_generic_unordered_lookup
+
 _LIBCPP_BEGIN_NAMESPACE_STD
 
 template <class _Key, class _Cp, class _Hash,
           bool = is_empty<_Hash>::value && !__libcpp_is_final<_Hash>::value>
 class __unordered_map_hasher
     : private _Hash
 {
 public:
template <class _Key, class _Tp, class _Hash = hash<_Key>, class _Pred = equal_to<_Key>,
           class _Alloc = allocator<pair<const _Key, _Tp> > >
 class _LIBCPP_TEMPLATE_VIS unordered_map
 {
 public:
     // types
     typedef _Key                                           key_type;
     typedef _Tp                                            mapped_type;
     typedef _Hash                                          hasher;
-    typedef _Pred                                          key_equal;
+    typedef typename __key_equal<_Hash, _Pred>::type       key_equal;
     typedef _Alloc                                         allocator_type;
     typedef pair<const key_type, mapped_type>              value_type;
     typedef value_type&                                    reference;
     typedef const value_type&                              const_reference;
     static_assert((is_same<value_type, typename allocator_type::value_type>::value),
                   "Invalid allocator::value_type");
     static_assert(sizeof(__diagnose_unordered_container_requirements<_Key, _Hash, _Pred>(0)), "");
 
 private:
     typedef __hash_value_type<key_type, mapped_type>                 __value_type;
     typedef __unordered_map_hasher<key_type, __value_type, hasher>   __hasher;
     typedef __unordered_map_equal<key_type, __value_type, key_equal> __key_equal;
     typedef typename __rebind_alloc_helper<allocator_traits<allocator_type>,
                                                  __value_type>::type __allocator_type;
 
     typedef __hash_table<__value_type, __hasher,
                          __key_equal,  __allocator_type>   __table;
-
     __table __table_;
 
     typedef typename __table::_NodeTypes                   _NodeTypes;
     typedef typename __table::__node_pointer               __node_pointer;
     typedef typename __table::__node_const_pointer         __node_const_pointer;
     typedef typename __table::__node_traits                __node_traits;
     typedef typename __table::__node_allocator             __node_allocator;
     typedef typename __table::__node                       __node;
#endif
     _LIBCPP_INLINE_VISIBILITY
     key_equal key_eq() const
         {return __table_.key_eq().key_eq();}
 
     _LIBCPP_INLINE_VISIBILITY
     iterator       find(const key_type& __k)       {return __table_.find(__k);}
     _LIBCPP_INLINE_VISIBILITY
     const_iterator find(const key_type& __k) const {return __table_.find(__k);}
+    template<class _Kt> _LIBCPP_INLINE_VISIBILITY
+    iterator  find(const _Kt& __k) {return __table_.find(__k);}
+    template<class _Kt> _LIBCPP_INLINE_VISIBILITY
+    const_iterator  find(const _Kt& __k) const {return __table_.find(__k);}
+
     _LIBCPP_INLINE_VISIBILITY
     size_type count(const key_type& __k) const {return __table_.__count_unique(__k);}
+    template<class _Kt> _LIBCPP_INLINE_VISIBILITY
+    size_type count(const _Kt& __k) const {return __table_.__count_unique(__k);}
+
+
     _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);}
+    template<class _Kt>_LIBCPP_INLINE_VISIBILITY
+    pair<iterator, iterator>             equal_range(const _Kt& __k)
+        {return __table_.__equal_range_unique(__k);}
+    template<class _Kt>_LIBCPP_INLINE_VISIBILITY
+    pair<const_iterator, const_iterator> equal_range(const _Kt& __k) const
+        {return __table_.__equal_range_unique(__k);}
 
     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);
     const mapped_type& at(const key_type& __k) const;
template <class _Key, class _Tp, class _Hash = hash<_Key>, class _Pred = equal_to<_Key>,
           class _Alloc = allocator<pair<const _Key, _Tp> > >
 class _LIBCPP_TEMPLATE_VIS unordered_multimap
 {
 public:
     // types
     typedef _Key                                           key_type;
     typedef _Tp                                            mapped_type;
     typedef _Hash                                          hasher;
-    typedef _Pred                                          key_equal;
+    typedef typename __key_equal<_Hash, _Pred>::type       key_equal;
     typedef _Alloc                                         allocator_type;
     typedef pair<const key_type, mapped_type>              value_type;
     typedef value_type&                                    reference;
     typedef const value_type&                              const_reference;
     static_assert((is_same<value_type, typename allocator_type::value_type>::value),
                   "Invalid allocator::value_type");
     static_assert(sizeof(__diagnose_unordered_container_requirements<_Key, _Hash, _Pred>(0)), "");
 
#endif
     _LIBCPP_INLINE_VISIBILITY
     key_equal key_eq() const
         {return __table_.key_eq().key_eq();}
 
     _LIBCPP_INLINE_VISIBILITY
     iterator       find(const key_type& __k)       {return __table_.find(__k);}
     _LIBCPP_INLINE_VISIBILITY
     const_iterator find(const key_type& __k) const {return __table_.find(__k);}
+    template<class _Kt> _LIBCPP_INLINE_VISIBILITY
+    iterator  find(const _Kt& __k) {return __table_.find(__k);}
+    template<class _Kt> _LIBCPP_INLINE_VISIBILITY
+    const_iterator  find(const _Kt& __k) const {return __table_.find(__k);}
+
     _LIBCPP_INLINE_VISIBILITY
-    size_type count(const key_type& __k) const {return __table_.__count_multi(__k);}
+    size_type count(const key_type& __k) const {return __table_.__count_unique(__k);}
+    template<class _Kt> _LIBCPP_INLINE_VISIBILITY
+    size_type count(const _Kt& __k) const {return __table_.__count_unique(__k);}
+
+
     _LIBCPP_INLINE_VISIBILITY
     pair<iterator, iterator>             equal_range(const key_type& __k)
-        {return __table_.__equal_range_multi(__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_multi(__k);}
+        {return __table_.__equal_range_unique(__k);}
+    template<class _Kt>_LIBCPP_INLINE_VISIBILITY
+    pair<iterator, iterator>             equal_range(const _Kt& __k)
+        {return __table_.__equal_range_unique(__k);}
+    template<class _Kt>_LIBCPP_INLINE_VISIBILITY
+    pair<const_iterator, const_iterator> equal_range(const _Kt& __k) const
+        {return __table_.__equal_range_unique(__k);}
 
     _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

include/unordered_set

template <class Value, class Hash = hash<Value>, class Pred = equal_to<Value>,
           class Alloc = allocator<Value>>
 class unordered_set
 {
 public:
     // types
     typedef Value                                                      key_type;
     typedef key_type                                                   value_type;
     typedef Hash                                                       hasher;
-    typedef Pred                                                       key_equal;
+    typedef see [unord.req]                                            key_equal;
     typedef Alloc                                                      allocator_type;
     typedef value_type&                                                reference;
     typedef const value_type&                                          const_reference;
     typedef typename allocator_traits<allocator_type>::pointer         pointer;
     typedef typename allocator_traits<allocator_type>::const_pointer   const_pointer;
     typedef typename allocator_traits<allocator_type>::size_type       size_type;
     typedef typename allocator_traits<allocator_type>::difference_type difference_type;
 
void swap(unordered_set&)
                  noexcept(swap(declval<hasher&>(), declval<hasher&>())) &&
                  noexcept(swap(declval<key_equal&>(), declval<key_equal&>()))); // C++17
 
     hasher hash_function() const;
     key_equal key_eq() const;
 
     iterator       find(const key_type& k);
     const_iterator find(const key_type& k) const;
+    template <class K> iterator       find(const K& k);
+    template <class K> const_iterator find(const K& k) const;
     size_type count(const key_type& k) const;
+    template <class K> size_type count(const K& k) const;
     pair<iterator, iterator>             equal_range(const key_type& k);
     pair<const_iterator, const_iterator> equal_range(const key_type& k) const;
+    template <class K> pair<iterator, iterator>             equal_range(const K& k);
+    template <class K> pair<const_iterator, const_iterator> equal_range(const K& k) const;
 
     size_type bucket_count() const noexcept;
     size_type max_bucket_count() const noexcept;
 
     size_type bucket_size(size_type n) const;
     size_type bucket(const key_type& k) const;
 
     local_iterator       begin(size_type n);
template <class Value, class Hash = hash<Value>, class Pred = equal_to<Value>,
           class Alloc = allocator<Value>>
 class unordered_multiset
 {
 public:
     // types
     typedef Value                                                      key_type;
     typedef key_type                                                   value_type;
     typedef Hash                                                       hasher;
-    typedef Pred                                                       key_equal;
+    typedef see [unord.req]                                            key_equal;
     typedef Alloc                                                      allocator_type;
     typedef value_type&                                                reference;
     typedef const value_type&                                          const_reference;
     typedef typename allocator_traits<allocator_type>::pointer         pointer;
     typedef typename allocator_traits<allocator_type>::const_pointer   const_pointer;
     typedef typename allocator_traits<allocator_type>::size_type       size_type;
     typedef typename allocator_traits<allocator_type>::difference_type difference_type;
 
void swap(unordered_multiset&)
                  noexcept(swap(declval<hasher&>(), declval<hasher&>())) &&
                  noexcept(swap(declval<key_equal&>(), declval<key_equal&>()))); // C++17
 
     hasher hash_function() const;
     key_equal key_eq() const;
 
     iterator       find(const key_type& k);
     const_iterator find(const key_type& k) const;
+    template <class K> iterator       find(const K& k);
+    template <class K> const_iterator find(const K& k) const;
     size_type count(const key_type& k) const;
+    template <class K> size_type count(const K& k) const;
     pair<iterator, iterator>             equal_range(const key_type& k);
     pair<const_iterator, const_iterator> equal_range(const key_type& k) const;
+    template <class K> pair<iterator, iterator>             equal_range(const K& k);
+    template <class K> pair<const_iterator, const_iterator> equal_range(const K& k) const;
 
     size_type bucket_count() const noexcept;
     size_type max_bucket_count() const noexcept;
 
     size_type bucket_size(size_type n) const;
     size_type bucket(const key_type& k) const;
 
     local_iterator       begin(size_type n);

 #include <version>
 
 #include <__debug>
 
 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
 #pragma GCC system_header
 #endif
 
+#define __cpp_lib_generic_unordered_lookup
+
 _LIBCPP_BEGIN_NAMESPACE_STD
 
 template <class _Value, class _Hash, class _Pred, class _Alloc>
 class unordered_multiset;
 
 template <class _Value, class _Hash = hash<_Value>, class _Pred = equal_to<_Value>,
           class _Alloc = allocator<_Value> >
 class _LIBCPP_TEMPLATE_VIS unordered_set
 {
 public:
     // types
     typedef _Value                                                     key_type;
     typedef key_type                                                   value_type;
     typedef _Hash                                                      hasher;
-    typedef _Pred                                                      key_equal;
+    typedef typename __key_equal<_Hash, _Pred>::type                   key_equal;
     typedef _Alloc                                                     allocator_type;
     typedef value_type&                                                reference;
     typedef const value_type&                                          const_reference;
     static_assert((is_same<value_type, typename allocator_type::value_type>::value),
                   "Invalid allocator::value_type");
     static_assert(sizeof(__diagnose_unordered_container_requirements<_Value, _Hash, _Pred>(0)), "");
 
 private:
#endif
     hasher hash_function() const {return __table_.hash_function();}
     _LIBCPP_INLINE_VISIBILITY
     key_equal key_eq() const {return __table_.key_eq();}
 
     _LIBCPP_INLINE_VISIBILITY
     iterator       find(const key_type& __k)       {return __table_.find(__k);}
     _LIBCPP_INLINE_VISIBILITY
     const_iterator find(const key_type& __k) const {return __table_.find(__k);}
+    template<class _Kt> _LIBCPP_INLINE_VISIBILITY
+    iterator  find(const _Kt& __k) {return __table_.find(__k);}
+    template<class _Kt> _LIBCPP_INLINE_VISIBILITY
+    const_iterator  find(const _Kt& __k) const {return __table_.find(__k);}
+
     _LIBCPP_INLINE_VISIBILITY
     size_type count(const key_type& __k) const {return __table_.__count_unique(__k);}
+    template<class _Kt> _LIBCPP_INLINE_VISIBILITY
+    size_type count(const _Kt& __k) const {return __table_.__count_unique(__k);}
+
+
     _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);}
+    template<class _Kt>_LIBCPP_INLINE_VISIBILITY
+    pair<iterator, iterator>             equal_range(const _Kt& __k)
+        {return __table_.__equal_range_unique(__k);}
+    template<class _Kt>_LIBCPP_INLINE_VISIBILITY
+    pair<const_iterator, const_iterator> equal_range(const _Kt& __k) const
+        {return __table_.__equal_range_unique(__k);}
 
     _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
     size_type bucket_size(size_type __n) const {return __table_.bucket_size(__n);}
template <class _Value, class _Hash = hash<_Value>, class _Pred = equal_to<_Value>,
           class _Alloc = allocator<_Value> >
 class _LIBCPP_TEMPLATE_VIS unordered_multiset
 {
 public:
     // types
     typedef _Value                                                     key_type;
     typedef key_type                                                   value_type;
     typedef _Hash                                                      hasher;
-    typedef _Pred                                                      key_equal;
+    typedef typename __key_equal<_Hash, _Pred>::type                   key_equal;
     typedef _Alloc                                                     allocator_type;
     typedef value_type&                                                reference;
     typedef const value_type&                                          const_reference;
     static_assert((is_same<value_type, typename allocator_type::value_type>::value),
                   "Invalid allocator::value_type");
     static_assert(sizeof(__diagnose_unordered_container_requirements<_Value, _Hash, _Pred>(0)), "");
 
 private:
#endif
     hasher hash_function() const {return __table_.hash_function();}
     _LIBCPP_INLINE_VISIBILITY
     key_equal key_eq() const {return __table_.key_eq();}
 
     _LIBCPP_INLINE_VISIBILITY
     iterator       find(const key_type& __k)       {return __table_.find(__k);}
     _LIBCPP_INLINE_VISIBILITY
     const_iterator find(const key_type& __k) const {return __table_.find(__k);}
+    template<class _Kt> _LIBCPP_INLINE_VISIBILITY
+    iterator  find(const _Kt& __k) {return __table_.find(__k);}
+    template<class _Kt> _LIBCPP_INLINE_VISIBILITY
+    const_iterator  find(const _Kt& __k) const {return __table_.find(__k);}
+
     _LIBCPP_INLINE_VISIBILITY
-    size_type count(const key_type& __k) const {return __table_.__count_multi(__k);}
+    size_type count(const key_type& __k) const {return __table_.__count_unique(__k);}
+    template<class _Kt> _LIBCPP_INLINE_VISIBILITY
+    size_type count(const _Kt& __k) const {return __table_.__count_unique(__k);}
+
+
     _LIBCPP_INLINE_VISIBILITY
     pair<iterator, iterator>             equal_range(const key_type& __k)
-        {return __table_.__equal_range_multi(__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_multi(__k);}
+        {return __table_.__equal_range_unique(__k);}
+    template<class _Kt>_LIBCPP_INLINE_VISIBILITY
+    pair<iterator, iterator>             equal_range(const _Kt& __k)
+        {return __table_.__equal_range_unique(__k);}
+    template<class _Kt>_LIBCPP_INLINE_VISIBILITY
+    pair<const_iterator, const_iterator> equal_range(const _Kt& __k) const
+        {return __table_.__equal_range_unique(__k);}
 
     _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
     size_type bucket_size(size_type __n) const {return __table_.bucket_size(__n);}

test/std/containers/hetro_lookups.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
+//
+//===----------------------------------------------------------------------===//
+
+#include <unordered_map>
+#include <unordered_set>
+#include <functional>
+#include <cassert>
+#include "test_macros.h"
+
+// <unordered_map>
+// <unordered_set>
+
+using namespace std;
+
+struct custom_hash
+{
+    using transparent_key_equal = equal_to<double>;
+    size_t operator()(int i) const   { return (double)i; }
+};
+
+template<class T, class P, class... U>
+void test_container_lookups(U... args)
+{
+    T u;
+    P pairs[] = {args...};
+
+    for (auto& x: pairs) u.insert(x);
+
+    assert(u.find(1.0) != u.end());
+    assert(u.count(2.0) != 0);
+
+    auto range = u.equal_range(2.0);
+    assert(range.first != range.second);
+}
+
+int main ()
+{
+    test_container_lookups<unordered_map<int, int, custom_hash>, pair<int, int>>(make_pair(0, -0),
+        make_pair(1, -1),
+        make_pair(2, -2),
+        make_pair(2, -3));
+    test_container_lookups<unordered_multimap<int, int, custom_hash>, pair<int, int>>(make_pair(0, -0),
+        make_pair(1, -1),
+        make_pair(2, -2),
+        make_pair(2, -3));
+    test_container_lookups<unordered_set<int, custom_hash>, int>(
+        0, 1, 2, 2);
+    test_container_lookups<unordered_multiset<int, custom_hash>, int>(
+        0, 1, 2, 2);
+
+    return 0;
+}
 No newline at end of file

test/std/containers/key_equal.fail.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
+//
+//===----------------------------------------------------------------------===//
+
+#include <unordered_map>
+#include <functional>
+#include <cassert>
+#include "test_macros.h"
+
+// <unordered_map>
+// <unordered_set>
+
+using namespace std;
+
+struct custom_hash
+{
+    using transparent_key_equal = equal_to<double>;
+};
+
+
+int main ()
+{
+    // expected-error {{type 'const custom_hash' does not provide a call operator}}
+    // expected-error {{static_assert failed due to requirement '__check_hash_requirements<int, custom_hash>::value' "the specified hash does not meet the Hash requirements"}}
+    unordered_map<int, int, custom_hash> u = {
+            {0, -0},
+            {1, -1},
+            {2, -2}
+    };
+
+    return 0;
+}
 No newline at end of file

test/std/containers/key_equal.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
+//
+//===----------------------------------------------------------------------===//
+
+#include <unordered_map>
+#include <unordered_set>
+#include <functional>
+#include <cassert>
+#include "test_macros.h"
+
+// <unordered_map>
+// <unordered_set>
+
+using namespace std;
+
+struct custom_hash
+{
+    using transparent_key_equal = equal_to<double>;
+    size_t operator()(int i) const { return i; }
+};
+
+template<class T, class U>
+void test_key_equal()
+{
+    ASSERT_SAME_TYPE(typename T::key_equal, custom_hash::transparent_key_equal);
+    ASSERT_SAME_TYPE(typename U::key_equal, equal_to<int>);
+}
+
+int main ()
+{
+    test_key_equal<unordered_map<int, int, custom_hash>, unordered_map<int, int>>();
+    test_key_equal<unordered_multimap<int, int, custom_hash>, unordered_multimap<int, int>>();
+    test_key_equal<unordered_set<int, custom_hash>, unordered_set<int>>();
+    test_key_equal<unordered_multiset<int, custom_hash>, unordered_multiset<int>>();
+
+    return 0;
+}
 No newline at end of file