diff --git a/libstdc++-v3/include/bits/hashtable.h b/libstdc++-v3/include/bits/hashtable.h
index aec77c34a58..d758b054b00 100644
--- a/libstdc++-v3/include/bits/hashtable.h
+++ b/libstdc++-v3/include/bits/hashtable.h
@@ -403,6 +403,59 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
       // numerous checks in the code to avoid 0 modulus.
       __node_base_ptr		_M_single_bucket	= nullptr;
 
+#if _GLIBCXX_INLINE_VERSION
+      // The last container node to optimize insertion in empty buckets.
+      __node_ptr		_M_last			= nullptr;
+#endif
+
+      class _HintPolicy
+      {
+	_Hashtable& _M_htb;
+	__node_ptr _M_last;
+	std::size_t _M_bbegin_index;
+	bool _M_initialized = false;
+
+      public:
+	_HintPolicy(_Hashtable& __htbl, __node_ptr __last)
+	: _M_htb(__htbl), _M_last(__last)
+	{ }
+
+#if _GLIBCXX_INLINE_VERSION
+	~_HintPolicy()
+	{ _M_htb._M_last = _M_last; }
+#endif
+
+	std::size_t
+	_M_get_bbegin_bkt(__node_ptr __n) const
+	{
+	  if (!_M_initialized)
+	    return _M_htb._M_bucket_index(*__n);
+	  return _M_bbegin_index;
+	}
+
+	void
+	_M_store_bbegin_bkt(std::size_t __bkt)
+	{
+	  _M_bbegin_index = __bkt;
+	  _M_initialized = true;
+	}
+
+	constexpr __node_ptr
+	_M_get_hint()
+	{ return _M_last; }
+
+	void
+	_M_set_last(__node_ptr __n)
+	{ _M_last = __n; }
+
+	void
+	_M_checked_set(__node_ptr __n)
+	{
+	  if (!__n || !__n->_M_nxt)
+	    _M_last = __n;
+	}
+      };
+
       void
       _M_update_bbegin()
       {
@@ -425,6 +478,51 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
       _M_uses_single_bucket() const
       { return _M_uses_single_bucket(_M_buckets); }
 
+      __node_ptr
+      _M_get_hint([[maybe_unused]] __node_ptr __usr_hint = nullptr) const
+      {
+#if _GLIBCXX_INLINE_VERSION
+	return _M_last;
+#else
+	return __usr_hint && !__usr_hint->_M_nxt ? __usr_hint : nullptr;
+#endif
+      }
+
+      _HintPolicy
+      _M_get_hint_policy(__node_ptr __usr_hint = nullptr)
+      { return _HintPolicy(*this, _M_get_hint(__usr_hint)); }
+
+      void
+      _M_check_for_last([[maybe_unused]] __node_base_ptr __prev_n)
+      {
+#if _GLIBCXX_INLINE_VERSION
+	if (!__prev_n->_M_nxt)
+	  {
+	    _M_last = __prev_n == &_M_before_begin
+	      ? nullptr
+	      : static_cast<__node_ptr>(__prev_n);
+	  }
+#endif
+      }
+
+      void
+      _M_set_last([[maybe_unused]] __node_ptr __n)
+      {
+#if _GLIBCXX_INLINE_VERSION
+	_M_last = __n;
+#endif
+      }
+
+      constexpr __node_ptr
+      _M_get_last()
+      {
+#if _GLIBCXX_INLINE_VERSION
+	return _M_last;
+#else
+	return nullptr;
+#endif
+      }
+
       static constexpr size_t
       __small_size_threshold() noexcept
       {
@@ -612,11 +710,13 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	// We consider that all elements of __l are going to be inserted.
 	auto __l_bkt_count = _M_rehash_policy._M_bkt_for_elements(__l.size());
 
+	auto __hint_policy = _M_get_hint_policy();
+
 	// Do not shrink to keep potential user reservation.
 	if (_M_bucket_count < __l_bkt_count)
-	  rehash(__l_bkt_count);
+	  _M_rehash(__hint_policy, __l_bkt_count);
 
-	_M_insert_range(__l.begin(), __l.end(), __roan);
+	_M_insert_range(__l.begin(), __l.end(), __hint_policy, __roan);
 	return *this;
       }
 
@@ -838,30 +938,53 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 
       // Insert a node at the beginning of a bucket.
       void
-      _M_insert_bucket_begin(size_type __bkt, __node_ptr __node)
+      _M_insert_bucket_begin(_HintPolicy& __hint_policy,
+			     size_type __bkt, __node_ptr __node)
       {
+	__node_base_ptr __prev;
 	if (_M_buckets[__bkt])
 	  {
 	    // Bucket is not empty, we just need to insert the new node
 	    // after the bucket before begin.
-	    __node->_M_nxt = _M_buckets[__bkt]->_M_nxt;
-	    _M_buckets[__bkt]->_M_nxt = __node;
+	    __prev = _M_buckets[__bkt];
+	    if (!__prev->_M_nxt)
+	      __hint_policy._M_set_last(__node);
 	  }
 	else
 	  {
-	    // The bucket is empty, the new node is inserted at the
-	    // beginning of the singly-linked list and the bucket will
-	    // contain _M_before_begin pointer.
-	    __node->_M_nxt = _M_before_begin._M_nxt;
-	    _M_before_begin._M_nxt = __node;
-
-	    if (__node->_M_nxt)
-	      // We must update former begin bucket that is pointing to
-	      // _M_before_begin.
-	      _M_buckets[_M_bucket_index(*__node->_M_next())] = __node;
-
-	    _M_buckets[__bkt] = &_M_before_begin;
+	    // If we have a hint, the last container node, insert after.
+	    __node_ptr __hint = __hint_policy._M_get_hint();
+	    if (__hint)
+	      {
+		__prev = __hint;
+		__hint_policy._M_set_last(__node);
+	      }
+	    else
+	      {
+		// The bucket is empty, the new node is inserted at the
+		// beginning of the singly-linked list and the bucket will
+		// contain _M_before_begin pointer.
+		__prev = &_M_before_begin;
+
+		if (__prev->_M_nxt)
+		  {
+		    // We must update former begin bucket that is pointing to
+		    // _M_before_begin.
+		    size_type __bb_bkt = __hint_policy._M_get_bbegin_bkt(
+		      static_cast<__node_ptr>(__prev->_M_nxt));
+		    _M_buckets[__bb_bkt] = __node;
+		  }
+		else
+		  __hint_policy._M_set_last(__node);
+
+		__hint_policy._M_store_bbegin_bkt(__bkt);
+	      }
+
+	    _M_buckets[__bkt] = __prev;
 	  }
+
+	__node->_M_nxt = __prev->_M_nxt;
+	__prev->_M_nxt = __node;
       }
 
       // Remove the bucket first node
@@ -887,44 +1010,76 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
       __node_base_ptr
       _M_get_previous_node(size_type __bkt, __node_ptr __n);
 
-      pair<__node_ptr, __hash_code>
-      _M_compute_hash_code(__node_ptr __hint, const key_type& __k) const;
+      struct _InsertInfo
+      {
+	__node_base_ptr	_M_prev;
+	__node_ptr	_M_equi_n;
+	__hash_code	_M_code;
+      };
+
+      _InsertInfo
+      _M_get_insert_info(_HintPolicy& __hint_policy, const key_type& __k,
+			 __node_ptr __n = nullptr) const;
 
       // Insert node __n with hash code __code, in bucket __bkt if no
       // rehash (assumes no element with same key already present).
       // Takes ownership of __n if insertion succeeds, throws otherwise.
       iterator
-      _M_insert_unique_node(size_type __bkt, __hash_code,
+      _M_insert_unique_node(_HintPolicy& __hint_policy,
+			    size_type __bkt, __hash_code,
 			    __node_ptr __n, size_type __n_elt = 1);
 
-      // Insert node __n with key __k and hash code __code.
+      // Insert node __n after __prev if any.
       // Takes ownership of __n if insertion succeeds, throws otherwise.
       iterator
-      _M_insert_multi_node(__node_ptr __hint,
-			   __hash_code __code, __node_ptr __n);
+      _M_insert_multi_node(_HintPolicy& __hint_policy,
+			   const _InsertInfo& __info, __node_ptr __n);
+
+      template<typename... _Args>
+	std::pair<iterator, bool>
+	_M_emplace_unique(_HintPolicy&, _Args&&... __args);
+
+      template<typename... _Args>
+	iterator
+	_M_emplace_multi(_HintPolicy&, _Args&&... __args);
 
       template<typename... _Args>
 	std::pair<iterator, bool>
-	_M_emplace(true_type __uks, _Args&&... __args);
+	_M_emplace(true_type /*__uks*/, _Args&&... __args)
+	{
+	  auto __hint_policy = _M_get_hint_policy();
+	  return _M_emplace_unique(__hint_policy,
+				   std::forward<_Args>(__args)...);
+	}
 
       template<typename... _Args>
 	iterator
-	_M_emplace(false_type __uks, _Args&&... __args)
-	{ return _M_emplace(cend(), __uks, std::forward<_Args>(__args)...); }
+	_M_emplace(false_type /*__uks*/, _Args&&... __args)
+	{
+	  auto __hint_policy = _M_get_hint_policy();
+	  return _M_emplace_multi(__hint_policy,
+				  std::forward<_Args>(__args)...);
+	}
 
-      // Emplace with hint, useless when keys are unique.
       template<typename... _Args>
 	iterator
-	_M_emplace(const_iterator, true_type __uks, _Args&&... __args)
-	{ return _M_emplace(__uks, std::forward<_Args>(__args)...).first; }
+	_M_emplace(_HintPolicy& __hint_policy,
+		   true_type /*__uks*/, _Args&&... __args)
+	{
+	  return _M_emplace_unique(__hint_policy,
+				   std::forward<_Args>(__args)...).first;
+	}
 
       template<typename... _Args>
 	iterator
-	_M_emplace(const_iterator, false_type __uks, _Args&&... __args);
+	_M_emplace(_HintPolicy& __hint_policy,
+		   false_type /*__uks*/, _Args&&... __args)
+	{ return _M_emplace_multi(__hint_policy, std::forward<_Args>(__args)...); }
 
       template<typename _Kt, typename _Arg, typename _NodeGenerator>
 	std::pair<iterator, bool>
-	_M_insert_unique(_Kt&&, _Arg&&, _NodeGenerator&);
+	_M_insert_unique(_HintPolicy& __hint_policy,
+			 _Kt&&, _Arg&&, _NodeGenerator&);
 
       template<typename _Kt>
 	static __conditional_t<
@@ -944,9 +1099,10 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 
       template<typename _Arg, typename _NodeGenerator>
 	std::pair<iterator, bool>
-	_M_insert_unique_aux(_Arg&& __arg, _NodeGenerator& __node_gen)
+	_M_insert_unique_aux(_HintPolicy& __hint_policy,
+			     _Arg&& __arg, _NodeGenerator& __node_gen)
 	{
-	  return _M_insert_unique(
+	  return _M_insert_unique(__hint_policy,
 	    _S_forward_key(_ExtractKey{}(std::forward<_Arg>(__arg))),
 	    std::forward<_Arg>(__arg), __node_gen);
 	}
@@ -956,9 +1112,10 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	_M_insert(_Arg&& __arg, _NodeGenerator& __node_gen,
 		  true_type /* __uks */)
 	{
+	  auto __hint_policy = _M_get_hint_policy();
 	  using __to_value
 	    = __detail::_ConvertToValueType<_ExtractKey, value_type>;
-	  return _M_insert_unique_aux(
+	  return _M_insert_unique_aux(__hint_policy,
 	    __to_value{}(std::forward<_Arg>(__arg)), __node_gen);
 	}
 
@@ -967,32 +1124,35 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	_M_insert(_Arg&& __arg, _NodeGenerator& __node_gen,
 		  false_type __uks)
 	{
+	  auto __hint_policy = _M_get_hint_policy();
 	  using __to_value
 	    = __detail::_ConvertToValueType<_ExtractKey, value_type>;
-	  return _M_insert(cend(),
+	  return _M_insert(__hint_policy,
 	    __to_value{}(std::forward<_Arg>(__arg)), __node_gen, __uks);
 	}
 
-      // Insert with hint, not used when keys are unique.
+      // Insert with hint when keys are unique.
       template<typename _Arg, typename _NodeGenerator>
 	iterator
-	_M_insert(const_iterator, _Arg&& __arg,
-		  _NodeGenerator& __node_gen, true_type __uks)
+	_M_insert(_HintPolicy& __hint_policy, _Arg&& __arg,
+		  _NodeGenerator& __node_gen, true_type /* __uks */)
 	{
-	  return
-	    _M_insert(std::forward<_Arg>(__arg), __node_gen, __uks).first;
+	  using __to_value
+	    = __detail::_ConvertToValueType<_ExtractKey, value_type>;
+	  return _M_insert_unique_aux(__hint_policy,
+	    __to_value{}(std::forward<_Arg>(__arg)), __node_gen).first;
 	}
 
       // Insert with hint when keys are not unique.
       template<typename _Arg, typename _NodeGenerator>
 	iterator
-	_M_insert(const_iterator, _Arg&&,
+	_M_insert(_HintPolicy& __hint_policy, _Arg&& __arg,
 		  _NodeGenerator&, false_type __uks);
 
       template<typename _InputIterator, typename _NodeGenerator>
 	void
 	_M_insert_range(_InputIterator __first, _InputIterator __last,
-			_NodeGenerator&);
+			_HintPolicy&, _NodeGenerator&);
 
       size_type
       _M_erase(true_type __uks, const key_type&);
@@ -1014,7 +1174,8 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	iterator
 	emplace_hint(const_iterator __hint, _Args&&... __args)
 	{
-	  return _M_emplace(__hint, __unique_keys{},
+	  auto __hint_policy = _M_get_hint_policy(__hint._M_cur);
+	  return _M_emplace(__hint_policy, __unique_keys{},
 			    std::forward<_Args>(__args)...);
 	}
 
@@ -1041,7 +1202,11 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 
       // Set number of buckets keeping it appropriate for container's number
       // of elements.
-      void rehash(size_type __bkt_count);
+      void rehash(size_type __bkt_count)
+      {
+	auto __hint_policy = _M_get_hint_policy();
+	_M_rehash(__hint_policy, __bkt_count);
+      }
 
       // DR 1189.
       // reserve, if present, comes from _Rehash_base.
@@ -1049,7 +1214,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 #if __cplusplus > 201402L
       /// Re-insert an extracted node into a container with unique keys.
       insert_return_type
-      _M_reinsert_node(node_type&& __nh)
+      _M_reinsert_node(const_iterator __hint, node_type&& __nh)
       {
 	insert_return_type __ret;
 	if (__nh.empty())
@@ -1058,14 +1223,22 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	  {
 	    __glibcxx_assert(get_allocator() == __nh.get_allocator());
 
+	    auto __hint_policy = _M_get_hint_policy(__hint._M_cur);
 	    __node_ptr __n = nullptr;
 	    const key_type& __k = __nh._M_key();
 	    const size_type __size = size();
 	    if (__size <= __small_size_threshold())
 	      {
-		for (__n = _M_begin(); __n; __n = __n->_M_next())
-		  if (this->_M_key_equals(__k, *__n))
-		    break;
+		__node_ptr __last_n = nullptr;
+		for (__n = _M_begin(); __n;
+		     __last_n = __n, __n = __n->_M_next())
+		  {
+		    if (this->_M_key_equals(__k, *__n))
+		      break;
+		  }
+
+		if (!__n)
+		  __hint_policy._M_set_last(__last_n);
 	      }
 
 	    __hash_code __code;
@@ -1086,8 +1259,8 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	      }
 	    else
 	      {
-		__ret.position
-		  = _M_insert_unique_node(__bkt, __code, __nh._M_ptr);
+		__ret.position = _M_insert_unique_node(
+		  __hint_policy, __bkt, __code, __nh._M_ptr);
 		__nh._M_ptr = nullptr;
 		__ret.inserted = true;
 	      }
@@ -1104,10 +1277,10 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 
 	__glibcxx_assert(get_allocator() == __nh.get_allocator());
 
+	auto __hint_policy = _M_get_hint_policy(__hint._M_cur);
 	const key_type& __k = __nh._M_key();
-	auto __code = this->_M_hash_code(__k);
-	auto __ret
-	  = _M_insert_multi_node(__hint._M_cur, __code, __nh._M_ptr);
+	auto __info = _M_get_insert_info(__hint_policy, __k);
+	auto __ret = _M_insert_multi_node(__hint_policy, __info, __nh._M_ptr);
 	__nh._M_ptr = nullptr;
 	return __ret;
       }
@@ -1147,6 +1320,18 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	  return this->_M_hash_code(__k);
 	}
 
+      template<typename _H2>
+	_InsertInfo
+	_M_get_insert_info(const _H2&, _HintPolicy& __hint_policy,
+			   __node_ptr __n, const key_type& __k)
+	{
+	  if constexpr (std::is_same_v<_H2, _Hash>)
+	    if constexpr (std::is_empty_v<_Hash>)
+	      return _M_get_insert_info(__hint_policy, __k, __n);
+
+	  return _M_get_insert_info(__hint_policy, __k);
+	}
+
     public:
       // Extract a node.
       node_type
@@ -1178,6 +1363,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	      node_type>, "Node types are compatible");
 	  __glibcxx_assert(get_allocator() == __src.get_allocator());
 
+	  auto __hint_policy = _M_get_hint_policy();
 	  auto __n_elt = __src.size();
 	  for (auto __i = __src.cbegin(), __end = __src.cend(); __i != __end;)
 	    {
@@ -1186,8 +1372,10 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	      const key_type& __k = _ExtractKey{}(*__pos);
 	      if (__size <= __small_size_threshold())
 		{
+		  __node_ptr __last_n = nullptr;
 		  bool __found = false;
-		  for (auto __n = _M_begin(); __n; __n = __n->_M_next())
+		  for (auto __n = _M_begin(); __n;
+		       __last_n = __n, __n = __n->_M_next())
 		    if (this->_M_key_equals(__k, *__n))
 		      {
 			__found = true;
@@ -1200,6 +1388,8 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 			--__n_elt;
 		      continue;
 		    }
+		  else
+		    __hint_policy._M_set_last(__last_n);
 		}
 
 	      __hash_code __code
@@ -1209,7 +1399,8 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 		  || _M_find_node(__bkt, __k, __code) == nullptr)
 		{
 		  auto __nh = __src.extract(__pos);
-		  _M_insert_unique_node(__bkt, __code, __nh._M_ptr, __n_elt);
+		  _M_insert_unique_node(
+		    __hint_policy, __bkt, __code, __nh._M_ptr, __n_elt);
 		  __nh._M_ptr = nullptr;
 		  __n_elt = 1;
 		}
@@ -1227,27 +1418,29 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	      node_type>, "Node types are compatible");
 	  __glibcxx_assert(get_allocator() == __src.get_allocator());
 
-	  __node_ptr __hint = nullptr;
+	  auto __hint_policy = _M_get_hint_policy();
 	  this->reserve(size() + __src.size());
 	  for (auto __i = __src.cbegin(), __end = __src.cend(); __i != __end;)
 	    {
 	      auto __pos = __i++;
 	      const key_type& __k = _ExtractKey{}(*__pos);
-	      __hash_code __code
-		= _M_src_hash_code(__src.hash_function(), __k, *__pos._M_cur);
+	      auto __info = _M_get_insert_info(__src.hash_function(),
+					__hint_policy, __pos._M_cur, __k);
 	      auto __nh = __src.extract(__pos);
-	      __hint = _M_insert_multi_node(__hint, __code, __nh._M_ptr)._M_cur;
+	      _M_insert_multi_node(__hint_policy, __info, __nh._M_ptr);
 	      __nh._M_ptr = nullptr;
 	    }
 	}
 #endif // C++17
 
     private:
+      void _M_rehash(_HintPolicy&, size_type __bkt_count);
+
       // Helper rehash method used when keys are unique.
-      void _M_rehash(size_type __bkt_count, true_type __uks);
+      void _M_rehash(_HintPolicy&, size_type __bkt_count, true_type __uks);
 
       // Helper rehash method used when keys can be non-unique.
-      void _M_rehash(size_type __bkt_count, false_type __uks);
+      void _M_rehash(_HintPolicy&, size_type __bkt_count, false_type __uks);
     };
 
   // Definitions of class template _Hashtable's out-of-line member functions.
@@ -1308,8 +1501,9 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	    _M_bucket_count = __bkt_count;
 	  }
 
+	auto __hint_policy = _M_get_hint_policy();
 	__alloc_node_gen_t __node_gen(*this);
-	_M_insert_range(__f, __l, __node_gen);
+	_M_insert_range(__f, __l, __hint_policy, __node_gen);
       }
 
   template<typename _Key, typename _Value, typename _Alloc,
@@ -1454,6 +1648,8 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 		  _M_buckets[__bkt] = __prev_n;
 		__prev_n = __this_n;
 	      }
+
+	    _M_set_last(__prev_n);
 	  }
 	__catch(...)
 	  {
@@ -1479,6 +1675,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
       _M_buckets = &_M_single_bucket;
       _M_before_begin._M_nxt = nullptr;
       _M_element_count = 0;
+      _M_set_last(nullptr);
     }
 
   template<typename _Key, typename _Value, typename _Alloc,
@@ -1509,9 +1706,11 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
       _M_before_begin._M_nxt = __ht._M_before_begin._M_nxt;
       _M_element_count = __ht._M_element_count;
       std::__alloc_on_move(this->_M_node_allocator(), __ht._M_node_allocator());
+      _M_set_last(__ht._M_get_last());
 
       // Fix bucket containing the _M_before_begin pointer that can't be moved.
       _M_update_bbegin();
+
       __ht._M_reset();
     }
 
@@ -1575,6 +1774,9 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
       _M_before_begin(__ht._M_before_begin._M_nxt),
       _M_element_count(__ht._M_element_count),
       _M_rehash_policy(__ht._M_rehash_policy)
+#if _GLIBCXX_INLINE_VERSION
+    , _M_last(__ht._M_last)
+#endif
     {
       // Update buckets if __ht is using its single bucket.
       if (__ht._M_uses_single_bucket())
@@ -1638,6 +1840,8 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	  else
 	    _M_buckets = __ht._M_buckets;
 
+	  _M_set_last(__ht._M_get_last());
+
 	  // Fix bucket containing the _M_before_begin pointer that can't be
 	  // moved.
 	  _M_update_bbegin(__ht._M_begin());
@@ -2147,7 +2351,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
       auto
       _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
 		 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
-      _M_emplace(true_type /* __uks */, _Args&&... __args)
+      _M_emplace_unique(_HintPolicy& __hint_policy, _Args&&... __args)
       -> pair<iterator, bool>
       {
 	// First build the node to get access to the hash code
@@ -2156,10 +2360,14 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	const size_type __size = size();
 	if (__size <= __small_size_threshold())
 	  {
-	    for (auto __it = _M_begin(); __it; __it = __it->_M_next())
-	      if (this->_M_key_equals(__k, *__it))
+	    __node_ptr __last_n = nullptr;
+	    for (auto __n = _M_begin(); __n;
+		 __last_n = __n, __n = __n->_M_next())
+	      if (this->_M_key_equals(__k, *__n))
 		// There is already an equivalent node, no insertion
-		return { iterator(__it), false };
+		return { iterator(__n), false };
+
+	    __hint_policy._M_set_last(__last_n);
 	  }
 
 	__hash_code __code = this->_M_hash_code(__k);
@@ -2170,7 +2378,8 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	    return { iterator(__p), false };
 
 	// Insert the node
-	auto __pos = _M_insert_unique_node(__bkt, __code, __node._M_node);
+	auto __pos = _M_insert_unique_node(__hint_policy, __bkt, __code,
+					   __node._M_node);
 	__node._M_node = nullptr;
 	return { __pos, true };
       }
@@ -2183,17 +2392,15 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
       auto
       _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
 		 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
-      _M_emplace(const_iterator __hint, false_type /* __uks */,
-		 _Args&&... __args)
+      _M_emplace_multi(_HintPolicy& __hint_policy, _Args&&... __args)
       -> iterator
       {
 	// First build the node to get its hash code.
 	_Scoped_node __node { this, std::forward<_Args>(__args)...  };
 	const key_type& __k = _ExtractKey{}(__node._M_node->_M_v());
 
-	auto __res = this->_M_compute_hash_code(__hint._M_cur, __k);
-	auto __pos
-	  = _M_insert_multi_node(__res.first, __res.second, __node._M_node);
+	auto __info = _M_get_insert_info(__hint_policy, __k);
+	auto __pos = _M_insert_multi_node(__hint_policy, __info, __node._M_node);
 	__node._M_node = nullptr;
 	return __pos;
       }
@@ -2205,26 +2412,32 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
     auto
     _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
 	       _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
-    _M_compute_hash_code(__node_ptr __hint, const key_type& __k) const
-    -> pair<__node_ptr, __hash_code>
+    _M_get_insert_info(_HintPolicy& __hint_policy, const key_type& __k,
+		       __node_ptr __equi_n) const
+    -> _InsertInfo
     {
       if (size() <= __small_size_threshold())
 	{
-	  if (__hint)
-	    {
-	      for (auto __it = __hint; __it; __it = __it->_M_next())
-		if (this->_M_key_equals(__k, *__it))
-		  return { __it, this->_M_hash_code(*__it) };
-	    }
-
-	  for (auto __it = _M_begin(); __it != __hint; __it = __it->_M_next())
-	    if (this->_M_key_equals(__k, *__it))
-	      return { __it, this->_M_hash_code(*__it) };
+	  __node_ptr __last_n = nullptr;
+	  __node_base_ptr __prev
+	    = const_cast<__node_base_ptr>(&_M_before_begin);
+	  for (auto __n = static_cast<__node_ptr>(__prev->_M_nxt); __n;
+	       __prev = __last_n = __n, __n = __n->_M_next())
+	    if (this->_M_key_equals(__k, *__n))
+	      return
+		{
+		  __prev, __n,
+		  __hash_cached::value ? this->_M_hash_code(*__n) : 0
+		};
 
-	  __hint = nullptr;
+	  __hint_policy._M_set_last(__last_n);
 	}
 
-      return { __hint, this->_M_hash_code(__k) };
+      return
+	{
+	  nullptr, nullptr,
+	  __equi_n ? this->_M_hash_code(*__equi_n) : this->_M_hash_code(__k)
+	};
     }
 
   template<typename _Key, typename _Value, typename _Alloc,
@@ -2234,7 +2447,8 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
     auto
     _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
 	       _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
-    _M_insert_unique_node(size_type __bkt, __hash_code __code,
+    _M_insert_unique_node(_HintPolicy& __hint_policy,
+			  size_type __bkt, __hash_code __code,
 			  __node_ptr __node, size_type __n_elt)
     -> iterator
     {
@@ -2245,7 +2459,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 
       if (__do_rehash.first)
 	{
-	  _M_rehash(__do_rehash.second, true_type{});
+	  _M_rehash(__hint_policy, __do_rehash.second, true_type{});
 	  __bkt = _M_bucket_index(__code);
 	}
 
@@ -2253,7 +2467,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
       this->_M_store_code(*__node, __code);
 
       // Always insert at the beginning of the bucket.
-      _M_insert_bucket_begin(__bkt, __node);
+      _M_insert_bucket_begin(__hint_policy, __bkt, __node);
       ++_M_element_count;
       return iterator(__node);
     }
@@ -2265,8 +2479,8 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
     auto
     _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
 	       _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
-    _M_insert_multi_node(__node_ptr __hint,
-			 __hash_code __code, __node_ptr __node)
+    _M_insert_multi_node(_HintPolicy& __hint_policy,
+			 const _InsertInfo& __info, __node_ptr __node)
     -> iterator
     {
       __rehash_guard_t __rehash_guard(_M_rehash_policy);
@@ -2274,42 +2488,53 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	= _M_rehash_policy._M_need_rehash(_M_bucket_count, _M_element_count, 1);
 
       if (__do_rehash.first)
-	_M_rehash(__do_rehash.second, false_type{});
+	_M_rehash(__hint_policy, __do_rehash.second, false_type{});
 
       __rehash_guard._M_guarded_obj = nullptr;
+      auto __code = __info._M_code;
       this->_M_store_code(*__node, __code);
       const key_type& __k = _ExtractKey{}(__node->_M_v());
-      size_type __bkt = _M_bucket_index(__code);
+      auto __prev = __info._M_prev;
+      const bool __has_prev = __prev != nullptr;
+      size_type __bkt;
 
       // Find the node before an equivalent one or use hint if it exists and
       // if it is equivalent.
-      __node_base_ptr __prev
-	= __builtin_expect(__hint != nullptr, false)
-	  && this->_M_equals(__k, __code, *__hint)
-	    ? __hint
-	    : _M_find_before_node(__bkt, __k, __code);
+      if (!__has_prev)
+	{
+	  __bkt = _M_bucket_index(__code);
+	  __prev = _M_find_before_node(__bkt, __k, __code);
+	}
 
       if (__prev)
 	{
 	  // Insert after the node before the equivalent one.
 	  __node->_M_nxt = __prev->_M_nxt;
 	  __prev->_M_nxt = __node;
-	  if (__builtin_expect(__prev == __hint, false))
-	    // hint might be the last bucket node, in this case we need to
-	    // update next bucket.
-	    if (__node->_M_nxt
-		&& !this->_M_equals(__k, __code, *__node->_M_next()))
-	      {
-		size_type __next_bkt = _M_bucket_index(*__node->_M_next());
-		if (__next_bkt != __bkt)
-		  _M_buckets[__next_bkt] = __node;
-	      }
+
+	  // __hint might be the last bucket node, in this case we need to
+	  // update next bucket.
+	  if (__has_prev && __node->_M_nxt != __info._M_equi_n)
+	    {
+	      const auto __nxt = __node->_M_next();
+	      if (!this->_M_equals(__k, __code, *__nxt))
+		{
+		  size_type __next_bkt = _M_bucket_index(*__nxt);
+		  if (__next_bkt != _M_bucket_index(__code))
+		    _M_buckets[__next_bkt] = __node;
+		}
+	    }
+
+	  __hint_policy._M_checked_set(__node);
 	}
       else
-	// The inserted node has no equivalent in the hashtable. We must
-	// insert the new node at the beginning of the bucket to preserve
-	// equivalent elements' relative positions.
-	_M_insert_bucket_begin(__bkt, __node);
+	{
+	  // The inserted node has no equivalent in the hashtable. We must
+	  // insert the new node at the beginning of the bucket to preserve
+	  // equivalent elements' relative positions.
+	  _M_insert_bucket_begin(__hint_policy, __bkt, __node);
+	}
+
       ++_M_element_count;
       return iterator(__node);
     }
@@ -2323,15 +2548,21 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
       auto
       _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
 		 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
-      _M_insert_unique(_Kt&& __k, _Arg&& __v,
+      _M_insert_unique(_HintPolicy& __hint_policy, _Kt&& __k, _Arg&& __v,
 		       _NodeGenerator& __node_gen)
       -> pair<iterator, bool>
       {
 	const size_type __size = size();
 	if (__size <= __small_size_threshold())
-	  for (auto __it = _M_begin(); __it; __it = __it->_M_next())
-	    if (this->_M_key_equals_tr(__k, *__it))
-	      return { iterator(__it), false };
+	  {
+	    __node_ptr __last_n = nullptr;
+	    for (auto __n = _M_begin(); __n;
+		 __last_n = __n, __n = __n->_M_next())
+	      if (this->_M_key_equals_tr(__k, *__n))
+		return { iterator(__n), false };
+
+	    __hint_policy._M_set_last(__last_n);
+	  }
 
 	__hash_code __code = this->_M_hash_code_tr(__k);
 	size_type __bkt = _M_bucket_index(__code);
@@ -2346,8 +2577,9 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 				     __node_gen),
 	  this
 	};
+
 	auto __pos
-	  = _M_insert_unique_node(__bkt, __code, __node._M_node);
+	  = _M_insert_unique_node(__hint_policy, __bkt, __code, __node._M_node);
 	__node._M_node = nullptr;
 	return { __pos, true };
       }
@@ -2361,20 +2593,19 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
       auto
       _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
 		 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
-      _M_insert(const_iterator __hint, _Arg&& __v,
-		_NodeGenerator& __node_gen,
-		false_type /* __uks */)
+      _M_insert(_HintPolicy& __hint_policy, _Arg&& __v,
+		_NodeGenerator& __node_gen, false_type /* __uks */)
       -> iterator
       {
 	// First allocate new node so that we don't do anything if it throws.
-	_Scoped_node __node{ __node_gen(std::forward<_Arg>(__v)), this };
+	_Scoped_node __node { __node_gen(std::forward<_Arg>(__v)), this };
 
 	// Second compute the hash code so that we don't rehash if it throws.
-	auto __res = this->_M_compute_hash_code(
-	  __hint._M_cur, _ExtractKey{}(__node._M_node->_M_v()));
-
-	auto __pos
-	  = _M_insert_multi_node(__res.first, __res.second, __node._M_node);
+	auto __info =
+	  _M_get_insert_info(__hint_policy,
+			     _ExtractKey{}(__node._M_node->_M_v()));
+	auto __pos = _M_insert_multi_node(__hint_policy,
+					  __info, __node._M_node);
 	__node._M_node = nullptr;
 	return __pos;
       }
@@ -2388,10 +2619,10 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
       _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
 		 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
       _M_insert_range(_InputIterator __first, _InputIterator __last,
-		      _NodeGenerator& __node_gen)
+		      _HintPolicy& __hint_policy, _NodeGenerator& __node_gen)
       {
 	for (; __first != __last; ++__first)
-	  _M_insert(*__first, __node_gen, __unique_keys{});
+	  _M_insert(__hint_policy, *__first, __node_gen, __unique_keys{});
       }
 
   template<typename _Key, typename _Value, typename _Alloc,
@@ -2438,7 +2669,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
       iterator __result(__n->_M_next());
       this->_M_deallocate_node(__n);
       --_M_element_count;
-
+      _M_check_for_last(__prev_n);
       return __result;
     }
 
@@ -2547,7 +2778,9 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	_M_remove_bucket_begin(__bkt, __n_last, __n_last_bkt);
       else if (__n_last_bkt != __bkt)
 	_M_buckets[__n_last_bkt] = __prev_n;
+
       __prev_n->_M_nxt = __n_last;
+      _M_check_for_last(__prev_n);
       return __result;
     }
 
@@ -2595,6 +2828,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
       if (__n && (__n_bkt != __bkt || __is_bucket_begin))
 	_M_buckets[__n_bkt] = __prev_n;
       __prev_n->_M_nxt = __n;
+      _M_check_for_last(__prev_n);
       return iterator(__n);
     }
 
@@ -2612,6 +2846,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 		       _M_bucket_count * sizeof(__node_base_ptr));
       _M_element_count = 0;
       _M_before_begin._M_nxt = nullptr;
+      _M_set_last(nullptr);
     }
 
   template<typename _Key, typename _Value, typename _Alloc,
@@ -2621,7 +2856,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
     void
     _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
 	       _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
-    rehash(size_type __bkt_count)
+    _M_rehash(_HintPolicy& __hint_policy, size_type __bkt_count)
     {
       __rehash_guard_t __rehash_guard(_M_rehash_policy);
       __bkt_count
@@ -2631,7 +2866,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 
       if (__bkt_count != _M_bucket_count)
 	{
-	  _M_rehash(__bkt_count, __unique_keys{});
+	  _M_rehash(__hint_policy, __bkt_count, __unique_keys{});
 	  __rehash_guard._M_guarded_obj = nullptr;
 	}
     }
@@ -2644,9 +2879,11 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
     void
     _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
 	       _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
-    _M_rehash(size_type __bkt_count, true_type /* __uks */)
+    _M_rehash(_HintPolicy& __hint_policy,
+	      size_type __bkt_count, true_type /* __uks */)
     {
       __buckets_ptr __new_buckets = _M_allocate_buckets(__bkt_count);
+      __node_ptr __prev_p = nullptr;
       __node_ptr __p = _M_begin();
       _M_before_begin._M_nxt = nullptr;
       std::size_t __bbegin_bkt = 0;
@@ -2670,12 +2907,14 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	      __new_buckets[__bkt]->_M_nxt = __p;
 	    }
 
+	  __prev_p = __p;
 	  __p = __next;
 	}
 
       _M_deallocate_buckets();
       _M_bucket_count = __bkt_count;
       _M_buckets = __new_buckets;
+      __hint_policy._M_set_last(__prev_p);
     }
 
   // Rehash when there can be equivalent elements, preserve their relative
@@ -2687,7 +2926,8 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
     void
     _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
 	       _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
-    _M_rehash(size_type __bkt_count, false_type /* __uks */)
+    _M_rehash(_HintPolicy& __hint_policy,
+	      size_type __bkt_count, false_type /* __uks */)
     {
       __buckets_ptr __new_buckets = _M_allocate_buckets(__bkt_count);
       __node_ptr __p = _M_begin();
@@ -2750,6 +2990,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 		  __new_buckets[__bkt]->_M_nxt = __p;
 		}
 	    }
+
 	  __prev_p = __p;
 	  __prev_bkt = __bkt;
 	  __p = __next;
@@ -2767,6 +3008,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
       _M_deallocate_buckets();
       _M_bucket_count = __bkt_count;
       _M_buckets = __new_buckets;
+      __hint_policy._M_set_last(__prev_p);
     }
 
 #if __cplusplus > 201402L
diff --git a/libstdc++-v3/include/bits/hashtable_policy.h b/libstdc++-v3/include/bits/hashtable_policy.h
index 9f775522cff..c8905f59289 100644
--- a/libstdc++-v3/include/bits/hashtable_policy.h
+++ b/libstdc++-v3/include/bits/hashtable_policy.h
@@ -848,8 +848,9 @@ namespace __detail
 	std::tuple<const key_type&>(__k),
 	std::tuple<>()
       };
-      auto __pos
-	= __h->_M_insert_unique_node(__bkt, __code, __node._M_node);
+      auto __hint_policy = __h->_M_get_hint_policy();
+      auto __pos =  __h->_M_insert_unique_node(__hint_policy, __bkt, __code,
+					       __node._M_node);
       __node._M_node = nullptr;
       return __pos->second;
     }
@@ -875,8 +876,9 @@ namespace __detail
 	std::forward_as_tuple(std::move(__k)),
 	std::tuple<>()
       };
-      auto __pos
-	= __h->_M_insert_unique_node(__bkt, __code, __node._M_node);
+      auto __hint_policy = __h->_M_get_hint_policy();
+      auto __pos = __h->_M_insert_unique_node(__hint_policy, __bkt, __code,
+					      __node._M_node);
       __node._M_node = nullptr;
       return __pos->second;
     }
@@ -964,13 +966,14 @@ namespace __detail
       insert(const_iterator __hint, const value_type& __v)
       {
 	__hashtable& __h = _M_conjure_hashtable();
-	__node_gen_type __node_gen(__h);	
-	return __h._M_insert(__hint, __v, __node_gen, __unique_keys{});
+	auto __hint_policy = __h._M_get_hint_policy(__hint._M_cur);
+	__node_gen_type __node_gen(__h);
+	return __h._M_insert(__hint_policy, __v, __node_gen, __unique_keys{});
       }
 
       template<typename _KType, typename... _Args>
 	std::pair<iterator, bool>
-	try_emplace(const_iterator, _KType&& __k, _Args&&... __args)
+	try_emplace(const_iterator __hint, _KType&& __k, _Args&&... __args)
 	{
 	  __hashtable& __h = _M_conjure_hashtable();
 	  auto __code = __h._M_hash_code(__k);
@@ -984,8 +987,9 @@ namespace __detail
 	    std::forward_as_tuple(std::forward<_KType>(__k)),
 	    std::forward_as_tuple(std::forward<_Args>(__args)...)
 	    };
-	  auto __it
-	    = __h._M_insert_unique_node(__bkt, __code, __node._M_node);
+	  auto __hint_policy = __h._M_get_hint_policy(__hint._M_cur);
+	  auto __it = __h._M_insert_unique_node(__hint_policy, __bkt, __code,
+						__node._M_node);
 	  __node._M_node = nullptr;
 	  return { __it, true };
 	}
@@ -1013,8 +1017,9 @@ namespace __detail
 		      true_type /* __uks */)
       {
 	__hashtable& __h = _M_conjure_hashtable();
+	auto __hint_policy = __h._M_get_hint_policy();
 	__node_gen_type __node_gen(__h);
-	__h._M_insert_range(__first, __last, __node_gen);
+	__h._M_insert_range(__first, __last, __hint_policy, __node_gen);
       }
 
   template<typename _Key, typename _Value, typename _Alloc,
@@ -1037,6 +1042,7 @@ namespace __detail
 	  return;
 
 	__hashtable& __h = _M_conjure_hashtable();
+	auto __hint_policy = __h._M_get_hint_policy();
 	__rehash_guard_t __rehash_guard(__h._M_rehash_policy);
 	__pair_type __do_rehash
 	  = __h._M_rehash_policy._M_need_rehash(__h._M_bucket_count,
@@ -1044,11 +1050,11 @@ namespace __detail
 						__n_elt);
 
 	if (__do_rehash.first)
-	  __h._M_rehash(__do_rehash.second, __uks);
+	  __h._M_rehash(__hint_policy, __do_rehash.second, __uks);
 
 	__rehash_guard._M_guarded_obj = nullptr;
 	__node_gen_type __node_gen(__h);
-	__h._M_insert_range(__first, __last, __node_gen);
+	__h._M_insert_range(__first, __last, __hint_policy, __node_gen);
       }
 
   /**
@@ -1102,8 +1108,9 @@ namespace __detail
       insert(const_iterator __hint, value_type&& __v)
       {
 	__hashtable& __h = this->_M_conjure_hashtable();
+	auto __hint_policy = __h._M_get_hint_policy(__hint._M_cur);
 	__node_gen_type __node_gen(__h);
-	return __h._M_insert(__hint, std::move(__v), __node_gen,
+	return __h._M_insert(__hint_policy, std::move(__v), __node_gen,
 			     __unique_keys{});
       }
     };
@@ -1153,7 +1160,8 @@ namespace __detail
 	insert(const_iterator __hint, _Pair&& __v)
 	{
 	  __hashtable& __h = this->_M_conjure_hashtable();
-	  return __h._M_emplace(__hint, __unique_keys{},
+	  auto __hint_policy = __h._M_get_hint_policy(__hint._M_cur);
+	  return __h._M_emplace(__hint_policy, __unique_keys{},
 				std::forward<_Pair>(__v));
 	}
    };
diff --git a/libstdc++-v3/include/bits/unordered_map.h b/libstdc++-v3/include/bits/unordered_map.h
index 1c99a83bc1e..e5df97c9229 100644
--- a/libstdc++-v3/include/bits/unordered_map.h
+++ b/libstdc++-v3/include/bits/unordered_map.h
@@ -443,12 +443,12 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
       /// Re-insert an extracted node.
       insert_return_type
       insert(node_type&& __nh)
-      { return _M_h._M_reinsert_node(std::move(__nh)); }
+      { return _M_h._M_reinsert_node(cend(), std::move(__nh)); }
 
       /// Re-insert an extracted node.
       iterator
-      insert(const_iterator, node_type&& __nh)
-      { return _M_h._M_reinsert_node(std::move(__nh)).position; }
+      insert(const_iterator __hint, node_type&& __nh)
+      { return _M_h._M_reinsert_node(__hint, std::move(__nh)).position; }
 #endif // C++17
 
 #ifdef __glibcxx_unordered_map_try_emplace // C++ >= 17 && HOSTED
diff --git a/libstdc++-v3/include/bits/unordered_set.h b/libstdc++-v3/include/bits/unordered_set.h
index f3b0c078baa..915cd4fb700 100644
--- a/libstdc++-v3/include/bits/unordered_set.h
+++ b/libstdc++-v3/include/bits/unordered_set.h
@@ -504,12 +504,12 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
       /// Re-insert an extracted node.
       insert_return_type
       insert(node_type&& __nh)
-      { return _M_h._M_reinsert_node(std::move(__nh)); }
+      { return _M_h._M_reinsert_node(cend(), std::move(__nh)); }
 
       /// Re-insert an extracted node.
       iterator
-      insert(const_iterator, node_type&& __nh)
-      { return _M_h._M_reinsert_node(std::move(__nh)).position; }
+      insert(const_iterator __hint, node_type&& __nh)
+      { return _M_h._M_reinsert_node(__hint, std::move(__nh)).position; }
 #endif // C++17
 
       ///@{
diff --git a/libstdc++-v3/testsuite/23_containers/unordered_multimap/insert/hint.cc b/libstdc++-v3/testsuite/23_containers/unordered_multimap/insert/hint.cc
index d0ed60c6799..1db71b8f30b 100644
--- a/libstdc++-v3/testsuite/23_containers/unordered_multimap/insert/hint.cc
+++ b/libstdc++-v3/testsuite/23_containers/unordered_multimap/insert/hint.cc
@@ -40,11 +40,12 @@ void test01()
   VERIFY( it2 != m.end() );
   VERIFY( it2 != it1 );
   VERIFY( it2->second == 2 );
-  VERIFY( it2 == std::next(it1) );
+  VERIFY( std::next(it2) == it1 );
 
+  it1 = it2;
   Pair p(0, 1);
   it2 = m.insert(it1, p);
-  VERIFY( it2 == std::next(it1) );
+  VERIFY( std::next(it2) == it1 );
 }
 
 struct hasher
@@ -71,13 +72,13 @@ void test02()
   VERIFY( m.bucket_size(m.bucket(it3->first)) == 1 );
 
   auto it4 = m.insert(it1, Pair(0, 1));
-  VERIFY( it4 == std::next(it1) );
+  VERIFY( std::next(it4) == it1 );
   VERIFY( m.bucket_size(m.bucket(it1->first)) == 3 );
   VERIFY( m.bucket_size(m.bucket(it3->first)) == 1 );
 
   Pair p(1, 1);
   it4 = m.insert(it2, p);
-  VERIFY( it4 == std::next(it2) );
+  VERIFY( std::next(it4) == it2 );
   VERIFY( m.bucket_size(m.bucket(it1->first)) == 4 );
   auto range = m.equal_range(0);
   VERIFY( std::distance(range.first, range.second) == 2 );
@@ -104,11 +105,12 @@ void test03()
   VERIFY( it2 != m.end() );
   VERIFY( it2 != it1 );
   VERIFY( it2->second == 2 );
-  VERIFY( it2 == std::next(it1) );
+  VERIFY( std::next(it2) == it1 );
 
+  it1 = it2;
   Pair p(0, 1);
   it2 = m.emplace_hint(it1, p);
-  VERIFY( it2 == std::next(it1) );
+  VERIFY( std::next(it2) == it1 );
 }
 
 int main()
