diff mbox series

Add unordered containers heterogeneous lookup

Message ID 7ec87f53-858e-c4b6-8f71-f48a0bc7dc19@gmail.com
State New
Headers show
Series Add unordered containers heterogeneous lookup | expand

Commit Message

François Dumont Dec. 1, 2020, 7:19 a.m. UTC
Let me know if I need to reference a specific paper or any other 
Standard reference here. Maybe P1690R1 I used here ?

I tried to allow the same partition trick you can have on ordered 
containers (see Partition in tests) even if here elements are not 
ordered so I aren't sure there can be any usage of it.

     libstdc++: Add unordered containers heterogeneous lookup

     Add unordered containers heterogeneous lookup member functions 
find, count, contains and
     equal_range in C++20. Those members are considered for overload 
resolution only if hash and
     equal functors used to instantiate the container have a nested 
is_transparent type.

     libstdc++-v3/ChangeLog:

             * include/bits/stl_tree.h
             (__has_is_transparent, __has_is_transparent_t): Move...
             * include/bits/stl_function.h: ...here.
             * include/bits/hashtable_policy.h 
(_Hash_code_base<>::_M_hash_code):
             Use template key type.
             (_Hashtable_base<>::_M_equals): Likewise.
             * include/bits/hashtable.h (_Hashtable<>::_M_find_tr, 
_Hashtable<>::_M_count_tr,
             _Hashtable<>::_M_equal_range_tr): New member function 
templates to perform
             heterogeneous lookup.
             (_Hashtable<>::_M_find_before_node): Use template key type.
             (_Hashtable<>::_M_find_node): Likewise.
             * include/bits/unordered_map.h (unordered_map::find<>, 
unordered_map::count<>,
             unordered_map::contains<>, unordered_map::equal_range<>): 
New member function
             templates to perform heterogeneous lookup.
             (unordered_multimap::find<>, unordered_multimap::count<>,
             unordered_multimap::contains<>, 
unordered_multimap::equal_range<>): Likewise.
             * include/bits/unordered_set.h (unordered_set::find<>, 
unordered_set::count<>,
             unordered_set::contains<>, unordered_set::equal_range<>): 
Likewise.
             (unordered_multiset::find<>, unordered_multiset::count<>,
             unordered_multiset::contains<>, 
unordered_multiset::equal_range<>): Likewise.
             * include/debug/unordered_map
             (unordered_map::find<>, unordered_map::equal_range<>): 
Likewise.
             (unordered_multimap::find<>, 
unordered_multimap::equal_range<>): Likewise.
             * include/debug/unordered_set
             (unordered_set::find<>, unordered_set::equal_range<>): 
Likewise.
             (unordered_multiset::find<>, 
unordered_multiset::equal_range<>): Likewise.
             * testsuite/23_containers/unordered_map/operations/1.cc: 
New test.
             * 
testsuite/23_containers/unordered_multimap/operations/1.cc: New test.
             * 
testsuite/23_containers/unordered_multiset/operations/1.cc: New test.
             * testsuite/23_containers/unordered_set/operations/1.cc: 
New test.

Tested under Linux x86_64 normal and debug modes.

François
diff mbox series

Patch

diff --git a/libstdc++-v3/include/bits/hashtable.h b/libstdc++-v3/include/bits/hashtable.h
index 6c6c5edde0b..30d4ee58100 100644
--- a/libstdc++-v3/include/bits/hashtable.h
+++ b/libstdc++-v3/include/bits/hashtable.h
@@ -724,6 +724,38 @@  _GLIBCXX_BEGIN_NAMESPACE_VERSION
       std::pair<const_iterator, const_iterator>
       equal_range(const key_type& __k) const;
 
+#if __cplusplus > 201702L
+      template<typename _Kt,
+	       typename = __has_is_transparent_t<_Hash, _Kt>,
+	       typename = __has_is_transparent_t<_Equal, _Kt>>
+	iterator
+	_M_find_tr(const _Kt& __k);
+
+      template<typename _Kt,
+	       typename = __has_is_transparent_t<_Hash, _Kt>,
+	       typename = __has_is_transparent_t<_Equal, _Kt>>
+	const_iterator
+	_M_find_tr(const _Kt& __k) const;
+
+      template<typename _Kt,
+	       typename = __has_is_transparent_t<_Hash, _Kt>,
+	       typename = __has_is_transparent_t<_Equal, _Kt>>
+	size_type
+	_M_count_tr(const _Kt& __k) const;
+
+      template<typename _Kt,
+	       typename = __has_is_transparent_t<_Hash, _Kt>,
+	       typename = __has_is_transparent_t<_Equal, _Kt>>
+	pair<iterator, iterator>
+	_M_equal_range_tr(const _Kt& __k);
+
+      template<typename _Kt,
+	       typename = __has_is_transparent_t<_Hash, _Kt>,
+	       typename = __has_is_transparent_t<_Equal, _Kt>>
+	pair<const_iterator, const_iterator>
+	_M_equal_range_tr(const _Kt& __k) const;
+#endif
+
     private:
       // Bucket index computation helpers.
       size_type
@@ -736,12 +768,13 @@  _GLIBCXX_BEGIN_NAMESPACE_VERSION
 
       // Find and insert helper functions and types
       // Find the node before the one matching the criteria.
+      template<typename _Kt>
 	__node_base_ptr
-      _M_find_before_node(size_type, const key_type&, __hash_code) const;
+	_M_find_before_node(size_type, const _Kt&, __hash_code) const;
 
+      template<typename _Kt>
 	__node_ptr
-      _M_find_node(size_type __bkt, const key_type& __key,
-		   __hash_code __c) const
+	_M_find_node(size_type __bkt, const _Kt& __key, __hash_code __c) const
 	{
 	  __node_base_ptr __before_n = _M_find_before_node(__bkt, __key, __c);
 	  if (__before_n)
@@ -1532,6 +1565,40 @@  _GLIBCXX_BEGIN_NAMESPACE_VERSION
       return const_iterator(_M_find_node(__bkt, __k, __code));
     }
 
+#if __cplusplus > 201703L
+  template<typename _Key, typename _Value, typename _Alloc,
+	   typename _ExtractKey, typename _Equal,
+	   typename _Hash, typename _RangeHash, typename _Unused,
+	   typename _RehashPolicy, typename _Traits>
+    template<typename _Kt, typename, typename>
+      auto
+      _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
+		 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
+      _M_find_tr(const _Kt& __k)
+      -> iterator
+      {
+	__hash_code __code = this->_M_hash_code(__k);
+	std::size_t __bkt = _M_bucket_index(__code);
+	return iterator(_M_find_node(__bkt, __k, __code));
+      }
+
+  template<typename _Key, typename _Value, typename _Alloc,
+	   typename _ExtractKey, typename _Equal,
+	   typename _Hash, typename _RangeHash, typename _Unused,
+	   typename _RehashPolicy, typename _Traits>
+    template<typename _Kt, typename, typename>
+      auto
+      _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
+		 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
+      _M_find_tr(const _Kt& __k) const
+      -> const_iterator
+      {
+	__hash_code __code = this->_M_hash_code(__k);
+	std::size_t __bkt = _M_bucket_index(__code);
+	return const_iterator(_M_find_node(__bkt, __k, __code));
+      }
+#endif
+
   template<typename _Key, typename _Value, typename _Alloc,
 	   typename _ExtractKey, typename _Equal,
 	   typename _Hash, typename _RangeHash, typename _Unused,
@@ -1561,6 +1628,37 @@  _GLIBCXX_BEGIN_NAMESPACE_VERSION
       return __result;
     }
 
+#if __cplusplus > 201703L
+  template<typename _Key, typename _Value, typename _Alloc,
+	   typename _ExtractKey, typename _Equal,
+	   typename _Hash, typename _RangeHash, typename _Unused,
+	   typename _RehashPolicy, typename _Traits>
+    template<typename _Kt, typename, typename>
+      auto
+      _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
+		 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
+      _M_count_tr(const _Kt& __k) const
+      -> size_type
+      {
+	__hash_code __code = this->_M_hash_code(__k);
+	std::size_t __bkt = _M_bucket_index(__code);
+	auto __n = _M_find_node(__bkt, __k, __code);
+	if (!__n)
+	  return 0;
+
+	// All equivalent values are next to each other, if we find a
+	// non-equivalent value after an equivalent one it means that we won't
+	// find any new equivalent value.
+	iterator __it(__n);
+	size_type __result = 1;
+	for (++__it; __it._M_cur && this->_M_equals(__k, __code, *__it._M_cur);
+	     ++__it)
+	  ++__result;
+
+	return __result;
+      }
+#endif
+
   template<typename _Key, typename _Value, typename _Alloc,
 	   typename _ExtractKey, typename _Equal,
 	   typename _Hash, typename _RangeHash, typename _Unused,
@@ -1615,16 +1713,75 @@  _GLIBCXX_BEGIN_NAMESPACE_VERSION
       return { __beg, __ite };
     }
 
+#if __cplusplus > 201703L
+  template<typename _Key, typename _Value, typename _Alloc,
+	   typename _ExtractKey, typename _Equal,
+	   typename _Hash, typename _RangeHash, typename _Unused,
+	   typename _RehashPolicy, typename _Traits>
+    template<typename _Kt, typename, typename>
+      auto
+      _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
+		 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
+      _M_equal_range_tr(const _Kt& __k)
+      -> pair<iterator, iterator>
+      {
+	__hash_code __code = this->_M_hash_code(__k);
+	std::size_t __bkt = _M_bucket_index(__code);
+	auto __n = _M_find_node(__bkt, __k, __code);
+	iterator __ite(__n);
+	if (!__n)
+	  return { __ite, __ite };
+
+	// All equivalent values are next to each other, if we find a
+	// non-equivalent value after an equivalent one it means that we won't
+	// find any new equivalent value.
+	auto __beg = __ite++;
+	while (__ite._M_cur && this->_M_equals(__k, __code, *__ite._M_cur))
+	  ++__ite;
+
+	return { __beg, __ite };
+      }
+
+  template<typename _Key, typename _Value, typename _Alloc,
+	   typename _ExtractKey, typename _Equal,
+	   typename _Hash, typename _RangeHash, typename _Unused,
+	   typename _RehashPolicy, typename _Traits>
+    template<typename _Kt, typename, typename>
+      auto
+      _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
+		 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
+      _M_equal_range_tr(const _Kt& __k) const
+      -> pair<const_iterator, const_iterator>
+      {
+	__hash_code __code = this->_M_hash_code(__k);
+	std::size_t __bkt = _M_bucket_index(__code);
+	auto __n = _M_find_node(__bkt, __k, __code);
+	const_iterator __ite(__n);
+	if (!__n)
+	  return { __ite, __ite };
+
+	// All equivalent values are next to each other, if we find a
+	// non-equivalent value after an equivalent one it means that we won't
+	// find any new equivalent value.
+	auto __beg = __ite++;
+	while (__ite._M_cur && this->_M_equals(__k, __code, *__ite._M_cur))
+	  ++__ite;
+
+	return { __beg, __ite };
+      }
+#endif
+
   // Find the node before the one whose key compares equal to k in the bucket
   // bkt. Return nullptr if no node is found.
   template<typename _Key, typename _Value, typename _Alloc,
 	   typename _ExtractKey, typename _Equal,
 	   typename _Hash, typename _RangeHash, typename _Unused,
 	   typename _RehashPolicy, typename _Traits>
+    template<typename _Kt>
       auto
       _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
 		 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
-    _M_find_before_node(size_type __bkt, const key_type& __k,
+      _M_find_before_node(size_type __bkt, const _Kt& __k,
 			  __hash_code __code) const
       -> __node_base_ptr
       {
diff --git a/libstdc++-v3/include/bits/hashtable_policy.h b/libstdc++-v3/include/bits/hashtable_policy.h
index 28372979c87..340aaede50c 100644
--- a/libstdc++-v3/include/bits/hashtable_policy.h
+++ b/libstdc++-v3/include/bits/hashtable_policy.h
@@ -1211,10 +1211,11 @@  namespace __detail
       _Hash_code_base() = default;
       _Hash_code_base(const _Hash& __hash) : __ebo_hash(__hash) { }
 
+      template<typename _Kt>
 	__hash_code
-      _M_hash_code(const _Key& __k) const
+	_M_hash_code(const _Kt& __k) const
 	{
-	static_assert(__is_invocable<const _Hash&, const _Key&>{},
+	  static_assert(__is_invocable<const _Hash&, const _Kt&>{},
 	    "hash function must be invocable with an argument of key type");
 	  return _M_hash()(__k);
 	}
@@ -1597,11 +1598,14 @@  namespace __detail
       : __hash_code_base(__hash), _EqualEBO(__eq)
       { }
 
+      template<typename _Kt>
 	bool
-      _M_equals(const _Key& __k, __hash_code __c,
-		const _Hash_node_value<_Value, __hash_cached::value>& __n) const
+	_M_equals(const _Kt& __k, __hash_code __c,
+		  const _Hash_node_value<_Value,
+					 __hash_cached::value>& __n) const
 	{
-	static_assert(__is_invocable<const _Equal&, const _Key&, const _Key&>{},
+	  static_assert(
+	    __is_invocable<const _Equal&, const _Kt&, const _Key&>{},
 	    "key equality predicate must be invocable with two arguments of "
 	    "key type");
 	  return _S_equals(__c, __n) && _M_eq()(__k, _ExtractKey{}(__n._M_v()));
diff --git a/libstdc++-v3/include/bits/stl_function.h b/libstdc++-v3/include/bits/stl_function.h
index 77f8ccb051a..37dab358558 100644
--- a/libstdc++-v3/include/bits/stl_function.h
+++ b/libstdc++-v3/include/bits/stl_function.h
@@ -1385,6 +1385,21 @@  _GLIBCXX_BEGIN_NAMESPACE_VERSION
 
   /** @}  */
 
+#if __cplusplus >= 201402L
+  template<typename _Func, typename _SfinaeType, typename = __void_t<>>
+    struct __has_is_transparent
+    { };
+
+  template<typename _Func, typename _SfinaeType>
+    struct __has_is_transparent<_Func, _SfinaeType,
+				__void_t<typename _Func::is_transparent>>
+    { typedef void type; };
+
+  template<typename _Func, typename _SfinaeType>
+    using __has_is_transparent_t
+      = typename __has_is_transparent<_Func, _SfinaeType>::type;
+#endif
+
 _GLIBCXX_END_NAMESPACE_VERSION
 } // namespace
 
diff --git a/libstdc++-v3/include/bits/stl_tree.h b/libstdc++-v3/include/bits/stl_tree.h
index a51d6da4ae8..3f854ace63b 100644
--- a/libstdc++-v3/include/bits/stl_tree.h
+++ b/libstdc++-v3/include/bits/stl_tree.h
@@ -415,21 +415,6 @@  _GLIBCXX_BEGIN_NAMESPACE_VERSION
   _Rb_tree_rebalance_for_erase(_Rb_tree_node_base* const __z,
 			       _Rb_tree_node_base& __header) throw ();
 
-#if __cplusplus >= 201402L
-  template<typename _Cmp, typename _SfinaeType, typename = __void_t<>>
-    struct __has_is_transparent
-    { };
-
-  template<typename _Cmp, typename _SfinaeType>
-    struct __has_is_transparent<_Cmp, _SfinaeType,
-				__void_t<typename _Cmp::is_transparent>>
-    { typedef void type; };
-
-  template<typename _Cmp, typename _SfinaeType>
-    using __has_is_transparent_t
-      = typename __has_is_transparent<_Cmp, _SfinaeType>::type;
-#endif
-
 #if __cplusplus > 201402L
   template<typename _Tree1, typename _Cmp2>
     struct _Rb_tree_merge_helper { };
diff --git a/libstdc++-v3/include/bits/unordered_map.h b/libstdc++-v3/include/bits/unordered_map.h
index 1aaa1a1a6ee..1a7bee28857 100644
--- a/libstdc++-v3/include/bits/unordered_map.h
+++ b/libstdc++-v3/include/bits/unordered_map.h
@@ -868,11 +868,26 @@  _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
       find(const key_type& __x)
       { return _M_h.find(__x); }
 
+#if __cplusplus > 201703L
+      template<typename _Kt>
+	auto
+	find(const _Kt& __x) -> decltype(_M_h._M_find_tr(__x))
+	{ return _M_h._M_find_tr(__x); }
+#endif
+
       const_iterator
       find(const key_type& __x) const
       { return _M_h.find(__x); }
+
+#if __cplusplus > 201703L
+      template<typename _Kt>
+	auto
+	find(const _Kt& __x) const -> decltype(_M_h._M_find_tr(__x))
+	{ return _M_h._M_find_tr(__x); }
+#endif
       //@}
 
+      //@{
       /**
        *  @brief  Finds the number of elements.
        *  @param  __x  Key to count.
@@ -887,6 +902,15 @@  _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
       { return _M_h.count(__x); }
 
 #if __cplusplus > 201703L
+      template<typename _Kt>
+	auto
+	count(const _Kt& __x) const -> decltype(_M_h._M_count_tr(__x))
+	{ return _M_h._M_count_tr(__x); }
+#endif
+      //@}
+
+#if __cplusplus > 201703L
+      //@{
       /**
        *  @brief  Finds whether an element with the given key exists.
        *  @param  __x  Key of elements to be located.
@@ -895,6 +919,13 @@  _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
       bool
       contains(const key_type& __x) const
       { return _M_h.find(__x) != _M_h.end(); }
+
+      template<typename _Kt>
+	auto
+	contains(const _Kt& __x) const
+	-> decltype(_M_h._M_find_tr(__x), void(), true)
+	{ return _M_h._M_find_tr(__x) != _M_h.end(); }
+      //@}
 #endif
 
       //@{
@@ -910,9 +941,25 @@  _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
       equal_range(const key_type& __x)
       { return _M_h.equal_range(__x); }
 
+#if __cplusplus > 201703L
+      template<typename _Kt>
+	auto
+	equal_range(const _Kt& __x)
+	-> decltype(_M_h._M_equal_range_tr(__x))
+	{ return _M_h._M_equal_range_tr(__x); }
+#endif
+
       std::pair<const_iterator, const_iterator>
       equal_range(const key_type& __x) const
       { return _M_h.equal_range(__x); }
+
+#if __cplusplus > 201703L
+      template<typename _Kt>
+	auto
+	equal_range(const _Kt& __x) const
+	-> decltype(_M_h._M_equal_range_tr(__x))
+	{ return _M_h._M_equal_range_tr(__x); }
+#endif
       //@}
 
       //@{
@@ -1764,11 +1811,26 @@  _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
       find(const key_type& __x)
       { return _M_h.find(__x); }
 
+#if __cplusplus > 201703L
+      template<typename _Kt>
+	auto
+	find(const _Kt& __x) -> decltype(_M_h._M_find_tr(__x))
+	{ return _M_h._M_find_tr(__x); }
+#endif
+
       const_iterator
       find(const key_type& __x) const
       { return _M_h.find(__x); }
+
+#if __cplusplus > 201703L
+      template<typename _Kt>
+	auto
+	find(const _Kt& __x) const -> decltype(_M_h._M_find_tr(__x))
+	{ return _M_h._M_find_tr(__x); }
+#endif
       //@}
 
+      //@{
       /**
        *  @brief  Finds the number of elements.
        *  @param  __x  Key to count.
@@ -1779,6 +1841,15 @@  _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
       { return _M_h.count(__x); }
 
 #if __cplusplus > 201703L
+      template<typename _Kt>
+	auto
+	count(const _Kt& __x) const -> decltype(_M_h._M_count_tr(__x))
+	{ return _M_h._M_count_tr(__x); }
+#endif
+      //@}
+
+#if __cplusplus > 201703L
+      //@{
       /**
        *  @brief  Finds whether an element with the given key exists.
        *  @param  __x  Key of elements to be located.
@@ -1787,6 +1858,13 @@  _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
       bool
       contains(const key_type& __x) const
       { return _M_h.find(__x) != _M_h.end(); }
+
+      template<typename _Kt>
+	auto
+	contains(const _Kt& __x) const
+	-> decltype(_M_h._M_find_tr(__x), void(), true)
+	{ return _M_h._M_find_tr(__x) != _M_h.end(); }
+      //@}
 #endif
 
       //@{
@@ -1800,9 +1878,25 @@  _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
       equal_range(const key_type& __x)
       { return _M_h.equal_range(__x); }
 
+#if __cplusplus > 201703L
+      template<typename _Kt>
+	auto
+	equal_range(const _Kt& __x)
+	-> decltype(_M_h._M_equal_range_tr(__x))
+	{ return _M_h._M_equal_range_tr(__x); }
+#endif
+
       std::pair<const_iterator, const_iterator>
       equal_range(const key_type& __x) const
       { return _M_h.equal_range(__x); }
+
+#if __cplusplus > 201703L
+      template<typename _Kt>
+	auto
+	equal_range(const _Kt& __x) const
+	-> decltype(_M_h._M_equal_range_tr(__x))
+	{ return _M_h._M_equal_range_tr(__x); }
+#endif
       //@}
 
       // bucket interface.
diff --git a/libstdc++-v3/include/bits/unordered_set.h b/libstdc++-v3/include/bits/unordered_set.h
index 6cbfcb1f0b6..f5391e1bdf2 100644
--- a/libstdc++-v3/include/bits/unordered_set.h
+++ b/libstdc++-v3/include/bits/unordered_set.h
@@ -650,11 +650,28 @@  _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
       find(const key_type& __x)
       { return _M_h.find(__x); }
 
+#if __cplusplus > 201703L
+      template<typename _Kt>
+	auto
+	find(const _Kt& __k)
+	-> decltype(_M_h._M_find_tr(__k))
+	{ return _M_h._M_find_tr(__k); }
+#endif
+
       const_iterator
       find(const key_type& __x) const
       { return _M_h.find(__x); }
+
+#if __cplusplus > 201703L
+      template<typename _Kt>
+	auto
+	find(const _Kt& __k) const
+	-> decltype(_M_h._M_find_tr(__k))
+	{ return _M_h._M_find_tr(__k); }
+#endif
       //@}
 
+      //@{
       /**
        *  @brief  Finds the number of elements.
        *  @param  __x  Element to located.
@@ -669,6 +686,16 @@  _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
       { return _M_h.count(__x); }
 
 #if __cplusplus > 201703L
+      template<typename _Kt>
+	auto
+	count(const _Kt& __k) const
+	-> decltype(_M_h._M_count_tr(__k))
+	{ return _M_h._M_count_tr(__k); }
+#endif
+      //@}
+
+#if __cplusplus > 201703L
+      //@{
       /**
        *  @brief  Finds whether an element with the given key exists.
        *  @param  __x  Key of elements to be located.
@@ -677,6 +704,13 @@  _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
       bool
       contains(const key_type& __x) const
       { return _M_h.find(__x) != _M_h.end(); }
+
+      template<typename _Kt>
+	auto
+	contains(const _Kt& __k) const
+	-> decltype(_M_h._M_find_tr(__k), void(), true)
+	{ return _M_h._M_find_tr(__k) != _M_h.end(); }
+      //@}
 #endif
 
       //@{
@@ -692,9 +726,25 @@  _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
       equal_range(const key_type& __x)
       { return _M_h.equal_range(__x); }
 
+#if __cplusplus > 201703L
+      template<typename _Kt>
+	auto
+	equal_range(const _Kt& __k)
+	-> decltype(_M_h._M_equal_range_tr(__k))
+	{ return _M_h._M_equal_range_tr(__k); }
+#endif
+
       std::pair<const_iterator, const_iterator>
       equal_range(const key_type& __x) const
       { return _M_h.equal_range(__x); }
+
+#if __cplusplus > 201703L
+      template<typename _Kt>
+	auto
+	equal_range(const _Kt& __k) const
+	-> decltype(_M_h._M_equal_range_tr(__k))
+	{ return _M_h._M_equal_range_tr(__k); }
+#endif
       //@}
 
       // bucket interface.
@@ -1450,11 +1500,28 @@  _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
       find(const key_type& __x)
       { return _M_h.find(__x); }
 
+#if __cplusplus > 201703L
+      template<typename _Kt>
+	auto
+	find(const _Kt& __x)
+	-> decltype(_M_h._M_find_tr(__x))
+	{ return _M_h._M_find_tr(__x); }
+#endif
+
       const_iterator
       find(const key_type& __x) const
       { return _M_h.find(__x); }
+
+#if __cplusplus > 201703L
+      template<typename _Kt>
+	auto
+	find(const _Kt& __x) const
+	-> decltype(_M_h._M_find_tr(__x))
+	{ return _M_h._M_find_tr(__x); }
+#endif
       //@}
 
+      //@{
       /**
        *  @brief  Finds the number of elements.
        *  @param  __x  Element to located.
@@ -1465,6 +1532,15 @@  _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
       { return _M_h.count(__x); }
 
 #if __cplusplus > 201703L
+      template<typename _Kt>
+	auto
+	count(const _Kt& __x) const -> decltype(_M_h._M_count_tr(__x))
+	{ return _M_h._M_count_tr(__x); }
+#endif
+      //@}
+
+#if __cplusplus > 201703L
+      //@{
       /**
        *  @brief  Finds whether an element with the given key exists.
        *  @param  __x  Key of elements to be located.
@@ -1473,6 +1549,13 @@  _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
       bool
       contains(const key_type& __x) const
       { return _M_h.find(__x) != _M_h.end(); }
+
+      template<typename _Kt>
+	auto
+	contains(const _Kt& __x) const
+	-> decltype(_M_h._M_find_tr(__x), void(), true)
+	{ return _M_h._M_find_tr(__x) != _M_h.end(); }
+      //@}
 #endif
 
       //@{
@@ -1486,9 +1569,25 @@  _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
       equal_range(const key_type& __x)
       { return _M_h.equal_range(__x); }
 
+#if __cplusplus > 201703L
+      template<typename _Kt>
+	auto
+	equal_range(const _Kt& __x)
+	-> decltype(_M_h._M_equal_range_tr(__x))
+	{ return _M_h._M_equal_range_tr(__x); }
+#endif
+
       std::pair<const_iterator, const_iterator>
       equal_range(const key_type& __x) const
       { return _M_h.equal_range(__x); }
+
+#if __cplusplus > 201703L
+      template<typename _Kt>
+	auto
+	equal_range(const _Kt& __x) const
+	-> decltype(_M_h._M_equal_range_tr(__x))
+	{ return _M_h._M_equal_range_tr(__x); }
+#endif
       //@}
 
       // bucket interface.
diff --git a/libstdc++-v3/include/debug/unordered_map b/libstdc++-v3/include/debug/unordered_map
index bae179b58ac..a9f7452f841 100644
--- a/libstdc++-v3/include/debug/unordered_map
+++ b/libstdc++-v3/include/debug/unordered_map
@@ -545,10 +545,28 @@  namespace __debug
       find(const key_type& __key)
       { return { _Base::find(__key), this }; }
 
+#if __cplusplus > 201703L
+      template<typename _Kt,
+	       typename = std::__has_is_transparent_t<_Hash, _Kt>,
+	       typename = std::__has_is_transparent_t<_Pred, _Kt>>
+	iterator
+	find(const _Kt& __k)
+	{ return { _Base::find(__k), this }; }
+#endif
+
       const_iterator
       find(const key_type& __key) const
       { return { _Base::find(__key), this }; }
 
+#if __cplusplus > 201703L
+      template<typename _Kt,
+	       typename = std::__has_is_transparent_t<_Hash, _Kt>,
+	       typename = std::__has_is_transparent_t<_Pred, _Kt>>
+	const_iterator
+	find(const _Kt& __k) const
+	{ return { _Base::find(__k), this }; }
+#endif
+
       std::pair<iterator, iterator>
       equal_range(const key_type& __key)
       {
@@ -556,6 +574,18 @@  namespace __debug
 	return { { __res.first, this }, { __res.second, this } };
       }
 
+#if __cplusplus > 201703L
+      template<typename _Kt,
+	       typename = std::__has_is_transparent_t<_Hash, _Kt>,
+	       typename = std::__has_is_transparent_t<_Pred, _Kt>>
+	std::pair<iterator, iterator>
+	equal_range(const _Kt& __k)
+	{
+	  auto __res = _Base::equal_range(__k);
+	  return { { __res.first, this }, { __res.second, this } };
+	}
+#endif
+
       std::pair<const_iterator, const_iterator>
       equal_range(const key_type& __key) const
       {
@@ -563,6 +593,18 @@  namespace __debug
 	return { { __res.first, this }, { __res.second, this } };
       }
 
+#if __cplusplus > 201703L
+      template<typename _Kt,
+	       typename = std::__has_is_transparent_t<_Hash, _Kt>,
+	       typename = std::__has_is_transparent_t<_Pred, _Kt>>
+	std::pair<const_iterator, const_iterator>
+	equal_range(const _Kt& __k) const
+	{
+	  auto __res = _Base::equal_range(__k);
+	  return { { __res.first, this }, { __res.second, this } };
+	}
+#endif
+
       size_type
       erase(const key_type& __key)
       {
@@ -1157,10 +1199,28 @@  namespace __debug
       find(const key_type& __key)
       { return { _Base::find(__key), this }; }
 
+#if __cplusplus > 201703L
+      template<typename _Kt,
+	       typename = std::__has_is_transparent_t<_Hash, _Kt>,
+	       typename = std::__has_is_transparent_t<_Pred, _Kt>>
+	iterator
+	find(const _Kt& __k)
+	{ return { _Base::find(__k), this }; }
+#endif
+
       const_iterator
       find(const key_type& __key) const
       { return { _Base::find(__key), this }; }
 
+#if __cplusplus > 201703L
+      template<typename _Kt,
+	       typename = std::__has_is_transparent_t<_Hash, _Kt>,
+	       typename = std::__has_is_transparent_t<_Pred, _Kt>>
+	const_iterator
+	find(const _Kt& __k) const
+	{ return { _Base::find(__k), this }; }
+#endif
+
       std::pair<iterator, iterator>
       equal_range(const key_type& __key)
       {
@@ -1168,6 +1228,18 @@  namespace __debug
 	return { { __res.first, this }, { __res.second, this } };
       }
 
+#if __cplusplus > 201703L
+      template<typename _Kt,
+	       typename = std::__has_is_transparent_t<_Hash, _Kt>,
+	       typename = std::__has_is_transparent_t<_Pred, _Kt>>
+	std::pair<iterator, iterator>
+	equal_range(const _Kt& __k)
+	{
+	  auto __res = _Base::equal_range(__k);
+	  return { { __res.first, this }, { __res.second, this } };
+	}
+#endif
+
       std::pair<const_iterator, const_iterator>
       equal_range(const key_type& __key) const
       {
@@ -1175,6 +1247,18 @@  namespace __debug
 	return { { __res.first, this }, { __res.second, this } };
       }
 
+#if __cplusplus > 201703L
+      template<typename _Kt,
+	       typename = std::__has_is_transparent_t<_Hash, _Kt>,
+	       typename = std::__has_is_transparent_t<_Pred, _Kt>>
+	std::pair<const_iterator, const_iterator>
+	equal_range(const _Kt& __k) const
+	{
+	  auto __res = _Base::equal_range(__k);
+	  return { { __res.first, this }, { __res.second, this } };
+	}
+#endif
+
       size_type
       erase(const key_type& __key)
       {
diff --git a/libstdc++-v3/include/debug/unordered_set b/libstdc++-v3/include/debug/unordered_set
index 97e6a74ebb4..6b7cb8b5108 100644
--- a/libstdc++-v3/include/debug/unordered_set
+++ b/libstdc++-v3/include/debug/unordered_set
@@ -430,10 +430,28 @@  namespace __debug
       find(const key_type& __key)
       { return { _Base::find(__key), this }; }
 
+#if __cplusplus > 201703L
+      template<typename _Kt,
+	       typename = std::__has_is_transparent_t<_Hash, _Kt>,
+	       typename = std::__has_is_transparent_t<_Pred, _Kt>>
+	iterator
+	find(const _Kt& __k)
+	{ return { _Base::find(__k), this }; }
+#endif
+
       const_iterator
       find(const key_type& __key) const
       { return { _Base::find(__key), this }; }
 
+#if __cplusplus > 201703L
+      template<typename _Kt,
+	       typename = std::__has_is_transparent_t<_Hash, _Kt>,
+	       typename = std::__has_is_transparent_t<_Pred, _Kt>>
+	const_iterator
+	find(const _Kt& __k) const
+	{ return { _Base::find(__k), this }; }
+#endif
+
       std::pair<iterator, iterator>
       equal_range(const key_type& __key)
       {
@@ -441,6 +459,18 @@  namespace __debug
 	return { { __res.first, this }, { __res.second, this } };
       }
 
+#if __cplusplus > 201703L
+      template<typename _Kt,
+	       typename = std::__has_is_transparent_t<_Hash, _Kt>,
+	       typename = std::__has_is_transparent_t<_Pred, _Kt>>
+	std::pair<iterator, iterator>
+	equal_range(const _Kt& __k)
+	{
+	  auto __res = _Base::equal_range(__k);
+	  return { { __res.first, this }, { __res.second, this } };
+	}
+#endif
+
       std::pair<const_iterator, const_iterator>
       equal_range(const key_type& __key) const
       {
@@ -448,6 +478,18 @@  namespace __debug
 	return { { __res.first, this }, { __res.second, this } };
       }
 
+#if __cplusplus > 201703L
+      template<typename _Kt,
+	       typename = std::__has_is_transparent_t<_Hash, _Kt>,
+	       typename = std::__has_is_transparent_t<_Pred, _Kt>>
+	std::pair<const_iterator, const_iterator>
+	equal_range(const _Kt& __k) const
+	{
+	  auto __res = _Base::equal_range(__k);
+	  return { { __res.first, this }, { __res.second, this } };
+	}
+#endif
+
       size_type
       erase(const key_type& __key)
       {
@@ -1002,10 +1044,28 @@  namespace __debug
       find(const key_type& __key)
       { return { _Base::find(__key), this }; }
 
+#if __cplusplus > 201703L
+      template<typename _Kt,
+	       typename = std::__has_is_transparent_t<_Hash, _Kt>,
+	       typename = std::__has_is_transparent_t<_Pred, _Kt>>
+	iterator
+	find(const _Kt& __k)
+	{ return { _Base::find(__k), this }; }
+#endif
+
       const_iterator
       find(const key_type& __key) const
       { return { _Base::find(__key), this }; }
 
+#if __cplusplus > 201703L
+      template<typename _Kt,
+	       typename = std::__has_is_transparent_t<_Hash, _Kt>,
+	       typename = std::__has_is_transparent_t<_Pred, _Kt>>
+	const_iterator
+	find(const _Kt& __k) const
+	{ return { _Base::find(__k), this }; }
+#endif
+
       std::pair<iterator, iterator>
       equal_range(const key_type& __key)
       {
@@ -1013,6 +1073,18 @@  namespace __debug
 	return { { __res.first, this }, { __res.second, this } };
       }
 
+#if __cplusplus > 201703L
+      template<typename _Kt,
+	       typename = std::__has_is_transparent_t<_Hash, _Kt>,
+	       typename = std::__has_is_transparent_t<_Pred, _Kt>>
+	std::pair<iterator, iterator>
+	equal_range(const _Kt& __k)
+	{
+	  auto __res = _Base::equal_range(__k);
+	  return { { __res.first, this }, { __res.second, this } };
+	}
+#endif
+
       std::pair<const_iterator, const_iterator>
       equal_range(const key_type& __key) const
       {
@@ -1020,6 +1092,18 @@  namespace __debug
 	return { { __res.first, this }, { __res.second, this } };
       }
 
+#if __cplusplus > 201703L
+      template<typename _Kt,
+	       typename = std::__has_is_transparent_t<_Hash, _Kt>,
+	       typename = std::__has_is_transparent_t<_Pred, _Kt>>
+	std::pair<const_iterator, const_iterator>
+	equal_range(const _Kt& __k) const
+	{
+	  auto __res = _Base::equal_range(__k);
+	  return { { __res.first, this }, { __res.second, this } };
+	}
+#endif
+
       size_type
       erase(const key_type& __key)
       {
diff --git a/libstdc++-v3/testsuite/23_containers/unordered_map/operations/1.cc b/libstdc++-v3/testsuite/23_containers/unordered_map/operations/1.cc
new file mode 100644
index 00000000000..df9dcd62478
--- /dev/null
+++ b/libstdc++-v3/testsuite/23_containers/unordered_map/operations/1.cc
@@ -0,0 +1,168 @@ 
+// Copyright (C) 2020 Free Software Foundation, Inc.
+//
+// This file is part of the GNU ISO C++ Library.  This library is free
+// software; you can redistribute it and/or modify it under the
+// terms of the GNU General Public License as published by the
+// Free Software Foundation; either version 3, or (at your option)
+// any later version.
+
+// This library is distributed in the hope that it will be useful,
+// but WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+// GNU General Public License for more details.
+
+// You should have received a copy of the GNU General Public License along
+// with this library; see the file COPYING3.  If not see
+// <http://www.gnu.org/licenses/>.
+
+// { dg-do run { target c++20 } }
+
+#include <unordered_map>
+#include <testsuite_hooks.h>
+
+struct Equal
+{
+  typedef void is_transparent;
+
+  bool operator()(int i, long l) const { return i == l; }
+  bool operator()(long l, int i) const { return l == i; }
+  bool operator()(int i, int j) const { ++count; return i == j; }
+
+  static int count;
+};
+
+int Equal::count = 0;
+
+struct Hash
+{
+  typedef void is_transparent;
+
+  std::size_t operator()(int i) const { ++count; return i; }
+  std::size_t operator()(long l) const { return l; }
+
+  static int count;
+};
+
+int Hash::count = 0;
+
+using test_type = std::unordered_map<int, char, Hash, Equal>;
+
+test_type x{ { 1, '2' }, { 3, '4' } };
+const test_type& cx = x;
+
+void
+test01()
+{
+  Hash::count = 0;
+  Equal::count = 0;
+
+  VERIFY( x.contains(1L) );
+
+  auto it = x.find(1L);
+  VERIFY( it != x.end() && it->second == '2' );
+  it = x.find(2L);
+  VERIFY( it == x.end() );
+
+  auto cit = cx.find(3L);
+  VERIFY( cit != cx.end() && cit->second == '4' );
+  cit = cx.find(2L);
+  VERIFY( cit == cx.end() );
+
+  VERIFY( Hash::count == 0 );
+  VERIFY( Equal::count == 0 );
+
+  static_assert(std::is_same<decltype(it), test_type::iterator>::value,
+      "find returns iterator");
+  static_assert(std::is_same<decltype(cit), test_type::const_iterator>::value,
+      "const find returns const_iterator");
+}
+
+void
+test02()
+{
+  Hash::count = 0;
+  Equal::count = 0;
+
+  auto n = x.count(1L);
+  VERIFY( n == 1 );
+  n = x.count(2L);
+  VERIFY( n == 0 );
+
+  auto cn = cx.count(3L);
+  VERIFY( cn == 1 );
+  cn = cx.count(2L);
+  VERIFY( cn == 0 );
+
+  VERIFY( Hash::count == 0 );
+  VERIFY( Equal::count == 0 );
+}
+
+void
+test03()
+{
+  Hash::count = 0;
+  Equal::count = 0;
+
+  auto it = x.equal_range(1L);
+  VERIFY( it.first != it.second && it.first->second == '2' );
+  it = x.equal_range(2L);
+  VERIFY( it.first == it.second && it.first == x.end() );
+
+  auto cit = cx.equal_range(1L);
+  VERIFY( cit.first != cit.second && cit.first->second == '2' );
+  cit = cx.equal_range(2L);
+  VERIFY( cit.first == cit.second && cit.first == cx.end() );
+
+  VERIFY( Hash::count == 0 );
+  VERIFY( Equal::count == 0 );
+
+  using pair = std::pair<test_type::iterator, test_type::iterator>;
+  static_assert(std::is_same<decltype(it), pair>::value,
+      "equal_range returns pair<iterator, iterator>");
+  using cpair = std::pair<test_type::const_iterator, test_type::const_iterator>;
+  static_assert(std::is_same<decltype(cit), cpair>::value,
+      "const equal_range returns pair<const_iterator, const_iterator>");
+}
+
+void
+test04()
+{
+  struct E
+  {
+    bool operator()(int l, int r) const { return l == r; }
+
+    struct Partition { };
+
+    bool operator()(int l, Partition) const { return l < 6; }
+    bool operator()(Partition, int r) const { return 3 < r; }
+
+    using is_transparent = void;
+  };
+
+  struct H
+  {
+    size_t
+    operator()(int x) const
+    { return 0; }
+
+    size_t
+    operator()(E::Partition) const
+    { return 0; }
+
+    using is_transparent = void;
+  };
+
+  std::unordered_map<int, int, H, E> m{ {1,0}, {2,0}, {3,0}, {4, 0}, {5, 0} };
+
+  auto n = m.count(E::Partition{});
+  VERIFY( n == 2 );
+}
+
+int
+main()
+{
+  test01();
+  test02();
+  test03();
+  test04();
+}
diff --git a/libstdc++-v3/testsuite/23_containers/unordered_multimap/operations/1.cc b/libstdc++-v3/testsuite/23_containers/unordered_multimap/operations/1.cc
new file mode 100644
index 00000000000..28d8233076b
--- /dev/null
+++ b/libstdc++-v3/testsuite/23_containers/unordered_multimap/operations/1.cc
@@ -0,0 +1,135 @@ 
+// Copyright (C) 2020 Free Software Foundation, Inc.
+//
+// This file is part of the GNU ISO C++ Library.  This library is free
+// software; you can redistribute it and/or modify it under the
+// terms of the GNU General Public License as published by the
+// Free Software Foundation; either version 3, or (at your option)
+// any later version.
+
+// This library is distributed in the hope that it will be useful,
+// but WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+// GNU General Public License for more details.
+
+// You should have received a copy of the GNU General Public License along
+// with this library; see the file COPYING3.  If not see
+// <http://www.gnu.org/licenses/>.
+
+// { dg-do run { target c++20 } }
+
+#include <unordered_map>
+#include <testsuite_hooks.h>
+
+struct Equal
+{
+  typedef void is_transparent;
+
+  bool operator()(int i, long l) const { return i == l; }
+  bool operator()(long l, int i) const { return l == i; }
+  bool operator()(int i, int j) const { ++count; return i == j; }
+
+  static int count;
+};
+
+int Equal::count = 0;
+
+struct Hash
+{
+  typedef void is_transparent;
+
+  std::size_t operator()(int i) const { ++count; return i; }
+  std::size_t operator()(long l) const { return l; }
+
+  static int count;
+};
+
+int Hash::count = 0;
+
+using test_type = std::unordered_multimap<int, char, Hash, Equal>;
+
+test_type x{ { 1, '2' }, { 3, '4' }, { 3, '5' } };
+const test_type& cx = x;
+
+void
+test01()
+{
+  Hash::count = 0;
+  Equal::count = 0;
+
+  VERIFY( x.contains(1L) );
+
+  auto it = x.find(1L);
+  VERIFY( it != x.end() && it->second == '2' );
+  it = x.find(2L);
+  VERIFY( it == x.end() );
+
+  auto cit = cx.find(3L);
+  VERIFY( cit != cx.end() && cit->second == '5' );
+  cit = cx.find(2L);
+  VERIFY( cit == cx.end() );
+
+  VERIFY( Hash::count == 0 );
+  VERIFY( Equal::count == 0 );
+
+  static_assert(std::is_same<decltype(it), test_type::iterator>::value,
+      "find returns iterator");
+  static_assert(std::is_same<decltype(cit), test_type::const_iterator>::value,
+      "const find returns const_iterator");
+}
+
+void
+test02()
+{
+  Hash::count = 0;
+  Equal::count = 0;
+
+  auto n = x.count(1L);
+  VERIFY( n == 1 );
+  n = x.count(2L);
+  VERIFY( n == 0 );
+
+  auto cn = cx.count(3L);
+  VERIFY( cn == 2 );
+  cn = cx.count(2L);
+  VERIFY( cn == 0 );
+
+  VERIFY( Hash::count == 0 );
+  VERIFY( Equal::count == 0 );
+}
+
+void
+test03()
+{
+  Hash::count = 0;
+  Equal::count = 0;
+
+  auto it = x.equal_range(1L);
+  VERIFY( it.first != it.second && it.first->second == '2' );
+  it = x.equal_range(2L);
+  VERIFY( it.first == it.second && it.first == x.end() );
+
+  auto cit = cx.equal_range(3L);
+  VERIFY( cit.first != cit.second && cit.first->second == '5' );
+  VERIFY( std::distance(cit.first, cit.second) == 2 );
+  cit = cx.equal_range(2L);
+  VERIFY( cit.first == cit.second && cit.first == cx.end() );
+
+  VERIFY( Hash::count == 0 );
+  VERIFY( Equal::count == 0 );
+
+  using pair = std::pair<test_type::iterator, test_type::iterator>;
+  static_assert(std::is_same<decltype(it), pair>::value,
+      "equal_range returns pair<iterator, iterator>");
+  using cpair = std::pair<test_type::const_iterator, test_type::const_iterator>;
+  static_assert(std::is_same<decltype(cit), cpair>::value,
+      "const equal_range returns pair<const_iterator, const_iterator>");
+}
+
+
+int
+main()
+{
+  test01();
+  test02();
+  test03();
+}
diff --git a/libstdc++-v3/testsuite/23_containers/unordered_multiset/operations/1.cc b/libstdc++-v3/testsuite/23_containers/unordered_multiset/operations/1.cc
new file mode 100644
index 00000000000..98a1c5b68de
--- /dev/null
+++ b/libstdc++-v3/testsuite/23_containers/unordered_multiset/operations/1.cc
@@ -0,0 +1,135 @@ 
+// Copyright (C) 2020 Free Software Foundation, Inc.
+//
+// This file is part of the GNU ISO C++ Library.  This library is free
+// software; you can redistribute it and/or modify it under the
+// terms of the GNU General Public License as published by the
+// Free Software Foundation; either version 3, or (at your option)
+// any later version.
+
+// This library is distributed in the hope that it will be useful,
+// but WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+// GNU General Public License for more details.
+
+// You should have received a copy of the GNU General Public License along
+// with this library; see the file COPYING3.  If not see
+// <http://www.gnu.org/licenses/>.
+
+// { dg-do run { target c++20 } }
+
+#include <unordered_set>
+#include <testsuite_hooks.h>
+
+struct Equal
+{
+  typedef void is_transparent;
+
+  bool operator()(int i, long l) const { return i == l; }
+  bool operator()(long l, int i) const { return l == i; }
+  bool operator()(int i, int j) const { ++count; return i == j; }
+
+  static int count;
+};
+
+int Equal::count = 0;
+
+struct Hash
+{
+  typedef void is_transparent;
+
+  std::size_t operator()(int i) const { ++count; return i; }
+  std::size_t operator()(long l) const { return l; }
+
+  static int count;
+};
+
+int Hash::count = 0;
+
+using test_type = std::unordered_multiset<int, Hash, Equal>;
+
+test_type x{ 1, 3, 3, 5 };
+const test_type& cx = x;
+
+void
+test01()
+{
+  Hash::count = 0;
+  Equal::count = 0;
+
+  VERIFY( x.contains(1L) );
+
+  auto it = x.find(1L);
+  VERIFY( it != x.end() && *it == 1 );
+  it = x.find(2L);
+  VERIFY( it == x.end() );
+
+  auto cit = cx.find(3L);
+  VERIFY( cit != cx.end() && *cit == 3 );
+  cit = cx.find(2L);
+  VERIFY( cit == cx.end() );
+
+  VERIFY( Hash::count == 0 );
+  VERIFY( Equal::count == 0 );
+
+  static_assert(std::is_same<decltype(it), test_type::iterator>::value,
+      "find returns iterator");
+  static_assert(std::is_same<decltype(cit), test_type::const_iterator>::value,
+      "const find returns const_iterator");
+}
+
+void
+test02()
+{
+  Hash::count = 0;
+  Equal::count = 0;
+
+  auto n = x.count(1L);
+  VERIFY( n == 1 );
+  n = x.count(2L);
+  VERIFY( n == 0 );
+
+  auto cn = cx.count(3L);
+  VERIFY( cn == 2 );
+  cn = cx.count(2L);
+  VERIFY( cn == 0 );
+
+  VERIFY( Hash::count == 0 );
+  VERIFY( Equal::count == 0 );
+}
+
+void
+test03()
+{
+  Hash::count = 0;
+  Equal::count = 0;
+
+  auto it = x.equal_range(1L);
+  VERIFY( it.first != it.second && *it.first == 1 );
+  it = x.equal_range(2L);
+  VERIFY( it.first == it.second && it.first == x.end() );
+
+  auto cit = cx.equal_range(3L);
+  VERIFY( cit.first != cit.second && *cit.first == 3 );
+  VERIFY( std::distance(cit.first, cit.second) == 2 );
+  cit = cx.equal_range(2L);
+  VERIFY( cit.first == cit.second && cit.first == cx.end() );
+
+  VERIFY( Hash::count == 0 );
+  VERIFY( Equal::count == 0 );
+
+  using pair = std::pair<test_type::iterator, test_type::iterator>;
+  static_assert(std::is_same<decltype(it), pair>::value,
+      "equal_range returns pair<iterator, iterator>");
+  using cpair = std::pair<test_type::const_iterator, test_type::const_iterator>;
+  static_assert(std::is_same<decltype(cit), cpair>::value,
+      "const equal_range returns pair<const_iterator, const_iterator>");
+}
+
+
+int
+main()
+{
+  test01();
+  test02();
+  test03();
+}
diff --git a/libstdc++-v3/testsuite/23_containers/unordered_set/operations/1.cc b/libstdc++-v3/testsuite/23_containers/unordered_set/operations/1.cc
new file mode 100644
index 00000000000..3498198ff6e
--- /dev/null
+++ b/libstdc++-v3/testsuite/23_containers/unordered_set/operations/1.cc
@@ -0,0 +1,186 @@ 
+// Copyright (C) 2020 Free Software Foundation, Inc.
+//
+// This file is part of the GNU ISO C++ Library.  This library is free
+// software; you can redistribute it and/or modify it under the
+// terms of the GNU General Public License as published by the
+// Free Software Foundation; either version 3, or (at your option)
+// any later version.
+
+// This library is distributed in the hope that it will be useful,
+// but WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+// GNU General Public License for more details.
+
+// You should have received a copy of the GNU General Public License along
+// with this library; see the file COPYING3.  If not see
+// <http://www.gnu.org/licenses/>.
+
+// { dg-do run { target c++20 } }
+
+#include <unordered_set>
+#include <testsuite_hooks.h>
+
+struct Equal
+{
+  typedef void is_transparent;
+
+  bool operator()(int i, long l) const { return i == l; }
+  bool operator()(long l, int i) const { return l == i; }
+  bool operator()(int i, int j) const { ++count; return i == j; }
+
+  static int count;
+};
+
+int Equal::count = 0;
+
+struct Hash
+{
+  typedef void is_transparent;
+
+  std::size_t operator()(int i) const { ++count; return i; }
+  std::size_t operator()(long l) const { return l; }
+
+  static int count;
+};
+
+int Hash::count = 0;
+
+using test_type = std::unordered_set<int, Hash, Equal>;
+
+test_type x{ 1, 3, 5 };
+const test_type& cx = x;
+
+void
+test01()
+{
+  Hash::count = 0;
+  Equal::count = 0;
+
+  VERIFY( x.contains(1L) );
+
+  auto it = x.find(1L);
+  VERIFY( it != x.end() && *it == 1 );
+  it = x.find(2L);
+  VERIFY( it == x.end() );
+
+  auto cit = cx.find(3L);
+  VERIFY( cit != cx.end() && *cit == 3 );
+  cit = cx.find(2L);
+  VERIFY( cit == cx.end() );
+
+  VERIFY( Hash::count == 0 );
+  VERIFY( Equal::count == 0 );
+
+  static_assert(std::is_same<decltype(it), test_type::iterator>::value,
+      "find returns iterator");
+  static_assert(std::is_same<decltype(cit), test_type::const_iterator>::value,
+      "const find returns const_iterator");
+}
+
+void
+test02()
+{
+  Hash::count = 0;
+  Equal::count = 0;
+
+  auto n = x.count(1L);
+  VERIFY( n == 1 );
+  n = x.count(2L);
+  VERIFY( n == 0 );
+
+  auto cn = cx.count(3L);
+  VERIFY( cn == 1 );
+  cn = cx.count(2L);
+  VERIFY( cn == 0 );
+
+  VERIFY( Hash::count == 0 );
+  VERIFY( Equal::count == 0 );
+}
+
+void
+test03()
+{
+  Hash::count = 0;
+  Equal::count = 0;
+
+  auto it = x.equal_range(1L);
+  VERIFY( it.first != it.second && *it.first == 1 );
+  it = x.equal_range(2L);
+  VERIFY( it.first == it.second && it.first == x.end() );
+
+  auto cit = cx.equal_range(1L);
+  VERIFY( cit.first != cit.second && *cit.first == 1 );
+  cit = cx.equal_range(2L);
+  VERIFY( cit.first == cit.second && cit.first == cx.end() );
+
+  VERIFY( Hash::count == 0 );
+  VERIFY( Equal::count == 0 );
+
+  using pair = std::pair<test_type::iterator, test_type::iterator>;
+  static_assert(std::is_same<decltype(it), pair>::value,
+      "equal_range returns pair<iterator, iterator>");
+  using cpair = std::pair<test_type::const_iterator, test_type::const_iterator>;
+  static_assert(std::is_same<decltype(cit), cpair>::value,
+      "const equal_range returns pair<const_iterator, const_iterator>");
+}
+
+void
+test04()
+{
+  // https://gcc.gnu.org/ml/libstdc++/2015-01/msg00176.html
+  // Verify the new function template overloads do not cause problems
+  // when the comparison function is not transparent.
+  struct I
+  {
+    int i;
+    operator int() const { return i; }
+  };
+
+  std::unordered_set<int> s;
+  I i = { };
+  s.find(i);
+}
+
+void
+test05()
+{
+  struct E
+  {
+    bool operator()(int l, int r) const { return l == r; }
+
+    struct Partition { };
+
+    bool operator()(int l, Partition) const { return l < 6; }
+    bool operator()(Partition, int r) const { return r > 3; }
+
+    using is_transparent = void;
+  };
+
+  struct H
+  {
+    size_t
+    operator()(int x) const
+    { return (size_t)(x / 10); }
+
+    size_t
+    operator()(E::Partition) const
+    { return 0; }
+
+    using is_transparent = void;
+  };
+
+  std::unordered_set<int, H, E> s{ 1, 2, 3, 4, 5 };
+
+  auto n = s.count(E::Partition{});
+  VERIFY( n == 2 );
+}
+
+int
+main()
+{
+  test01();
+  test02();
+  test03();
+  test04();
+  test05();
+}