Re: [PATCH 5/5][_Hashtable] Prefer to insert after last node

["François Dumont" <frs.dumont@gmail.com>]

[-- Attachment #1: Type: text/plain, Size: 9581 bytes --]

Here is a new version of this patch.

The previous one had some flaws that were unnoticed by testsuite tests, 
only the performance tests were spotting it. So I'm adding checks on the 
consistency of the unordered containers in this patch.

I also forget to signal that after this patch gnu versioned namespace 
version is supposed to be bump. But I hope it's already the plan because 
of the move to the cxx11 abi in this mode.

Note for reviewer, after application of the patch, a 'git diff -b' is 
much more readable.

And some benches results:

before:

unordered_set_range_insert.cc-thread    hash code NOT cached 2 X 1000000 
inserts individually 19999990 calls      44r   44u    0s 95999760mem    0pf
unordered_set_range_insert.cc-thread    hash code NOT cached 2 X 1000000 
inserts in range 20000000 calls      43r   43u    0s 95999760mem    0pf
unordered_set_range_insert.cc-thread    hash code NOT cached 1000000 X 
inserts individually 19999990 calls      44r   44u 0s  95999760mem    0pf
unordered_set_range_insert.cc-thread    hash code NOT cached 1000000 X 
inserts in range 20000000 calls      43r   43u    0s 95999760mem    0pf
unordered_set_range_insert.cc-thread    hash code cached 2 X 1000000 
inserts individually 10000000 calls      30r   30u    0s 111999328mem    
0pf
unordered_set_range_insert.cc-thread    hash code cached 2 X 1000000 
inserts in range 10000010 calls      33r   32u    0s 111999328mem    0pf
unordered_set_range_insert.cc-thread    hash code cached 1000000 X 
inserts individually 10000000 calls      30r   31u    0s 111999328mem    
0pf
unordered_set_range_insert.cc-thread    hash code cached 1000000 X 
inserts in range 10000010 calls      32r   32u    0s 111999328mem    0pf

after:

unordered_set_range_insert.cc-thread    hash code NOT cached 2 X 1000000 
inserts individually 19999990 calls      44r   44u    0s 95999760mem    0pf
unordered_set_range_insert.cc-thread    hash code NOT cached 2 X 1000000 
inserts in range 10000020 calls      26r   25u    0s 95999760mem    0pf
unordered_set_range_insert.cc-thread    hash code NOT cached 1000000 X 
inserts individually 19999990 calls      43r   44u 0s  95999760mem    0pf
unordered_set_range_insert.cc-thread    hash code NOT cached 1000000 X 
inserts in range 10000020 calls      26r   26u    0s 95999760mem    0pf
unordered_set_range_insert.cc-thread    hash code cached 2 X 1000000 
inserts individually 10000000 calls      35r   35u    0s 111999328mem    
0pf
unordered_set_range_insert.cc-thread    hash code cached 2 X 1000000 
inserts in range 10000010 calls      32r   33u    0s 111999328mem    0pf
unordered_set_range_insert.cc-thread    hash code cached 1000000 X 
inserts individually 10000000 calls      31r   32u    0s 111999328mem    
0pf
unordered_set_range_insert.cc-thread    hash code cached 1000000 X 
inserts in range 10000010 calls      31r   31u    0s 111999328mem    0pf


     libstdc++: [_Hashtable] Prefer to insert after last node

     When inserting an element into an empty bucket we currently insert 
the new node
     after the before-begin node so in first position. The drawback of 
doing this is
     that we are forced to update the bucket that was containing this 
before-begin
     node to point to the newly inserted node. To do so we need at best 
to do a modulo
     to find this bucket and at worst, when hash code is not cached, 
also compute it.

     To avoid this side effect it is better to insert after the last 
node. To do so
     we are introducing a helper type _HintPolicy that has 3 
resposibilities.

     1. When the gnu versioned namespace is used we add a _M_last member 
to _Hashtable,
     _HintPolicy is then in charge of maintaining it. For this purpose 
_HintPolicy is
     using the RAII pattern, it resets the _M_last at destruction level. 
It also maintain
     its own _M_last, all mutable operations are updating it when needed.

     2. When the gnu versioned namespace is not used _HintPolicy will 
still maintain its
     _M_last member using initially the user provided hint if any and if 
it is actually
     the container last node that is to say a dereferenceable node with 
its next node being
     null. All mutable operations can also update the contextual 
_HintPolicy instance
     whenever they detect the last node during their process.

     3. As long as we haven't been able to detect the container last 
node, _HintPolicy
     is used to keep a cache of the before-begin bucket index so that we 
do not need to
     compute it afterward for example in the context of range insertion.

     libstdc++-v3/ChangeLog:

             * include/bits/hashtable.h
[_GLIBCXX_INLINE_VERSION](_Hashtable<>::_M_last): New, the container 
last node.
             (_Hashtable<>::_LastNodeManager): New.
             (_Hashtable<>::_M_get_last(__node_ptr)): New.
(_Hashtable<>::_M_get_last_node_mgr(__node_ptr)): New.
(_Hashtable<>::_M_check_for_last(__node_base_ptr)): New.
             (_Hashtable<>::_M_set_last(__node_ptr)): New.
             (_Hashtable<>::_M_compute_hash_code(__node_ptr, const 
key_type&)): Remove.
(_Hashtable<>::operator=(initializer_list<>)): Adapt to instantiate a 
_HintPolicy.
             (_Hashtable<>::_M_insert_bucket_begin): Add _HintPolicy& 
parameter and use it
             to optimize insertion in an empty bucket.
             (_Hashtable<>::_M_insert_unique_node): Add _HintPolicy& 
parameter.
             (_Hashtable<>::_M_insert_multi_node(__node_ptr, 
__hash_code, __node_ptr)): Replace by...
(_Hashtable<>::_M_insert_multi_node(_HintPolicy&, const key_type&,
             __node_ptr, __node_ptr)): ... this.
(_Hashtable<>::_M_emplace_unique(_HintPolicy&, _Args&&...)): New.
(_Hashtable<>::_M_emplace_multi(_HintPolicy&, _Args&&...)): New.
             (_Hashtable<>::_M_emplace): Adapt to use latters.
             (_Hashtable<>::_M_insert_unique): Add _HintPolicy& parameter.
             (_Hashtable<>::_M_insert_unique_aux): Add _HintPolicy& 
parameter.
             (_Hashtable<>::_M_insert): Adapt to use latter.
             (_Hashtable<>::emplace_hint(const_iterator, _Args&&...)): 
Adapt.
             (_hashtable<>::rehash(size_type)): Adapt.
             (_Hashtable<>::_M_reinsert_node(const_iterator, node_type&&)):
             Add hint parameter, adapt to use it for _HintPolicy 
instantiation.
             (_Hashtable<>::_M_reinsert_node_multi): Likewise.
             (_Hashtable<>::_M_merge_unique): Adapt.
             (_Hashtable<>::_M_rehash): Add _HintPolicy& parameter.
             (_Hashtable<>::_Hashtable<_InputIte>()): Adapt.
             (_Hashtable<>::_M_assign): Call _M_set_last.
             (_Hashtable<>::_M_reset()): Reset _M_last.
(_Hashtable<>::_M_move_assign(_Hashtable&&, true_type)): Move _M_last.
             (_Hashtable<>(_Hashtable&&, __node_alloc_type&&, 
true_type)): Copy _M_last.
             (_Hashtable<>(_Hashtable&&, __node_alloc_type&&, 
false_type)): Copy _M_last.
             (_Hashtable<>::_M_insert_range): Adapt.
             (_Hashtable<>::_M_erase): Call _M_check_for_last.
             (_Hashtable<>::erase): Likewise.
             * include/bits/hashtable_policy.h:
             (_Map_base<>::operator[](const key_type&)): Use hint policy.
             (_Map_base<>::operator[](key_type&&)): Likewise.
             (_Insert_base<>::insert(const_iterator, const 
value_type&)): Likewise using hint.
             (_Insert_base<>::try_emplace): Likewise.
(_Insert_base<>::_M_insert_range<>(_InputIte, _InputIte, true_type)): 
Use hint policy.
(_Insert_base<>::_M_insert_range<>(_InputIte, _InputIte, false_type)): 
Use hint policy.
             (_Insert<>::insert(const_iterator, value_type&&)): Likewise.
             * include/bits/unordered_map.h 
(unordered_map<>::insert(node_type&&)): Pass cend as
             hint.
             (unordered_map<>::insert(const_iterator, node_type&&)): 
Adapt to use hint.
             * include/bits/unordered_set.h 
(unordered_set<>::insert(node_type&&)): Pass cend as
             hint.
             (unordered_set<>::insert(const_iterator, node_type&&)): 
Adapt to use hint.
             * 
testsuite/23_containers/unordered_multimap/insert/hint.cc: Adapt 
implementation
             specific tests.
             * 
testsuite/23_containers/unordered_map/consistency_check.cc: New test case.
             * 
testsuite/23_containers/unordered_multimap/consistency_check.cc: New 
test case.
             * 
testsuite/23_containers/unordered_multiset/consistency_check.cc: New 
test case.
             * 
testsuite/23_containers/unordered_set/consistency_check.cc: New test case.
             * testsuite/libstdc++-prettyprinters/cxx11.cc (main): Adapt 
expectations on element
             order in unordered_map instance.


[-- Attachment #2: hashtable_patch.txt --]
[-- Type: text/plain, Size: 52713 bytes --]

diff --git a/libstdc++-v3/include/bits/hashtable.h b/libstdc++-v3/include/bits/hashtable.h
index aec77c34a58..f92ff196679 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 _LastNodeManager
+      {
+	_Hashtable& _M_htb;
+	__node_ptr _M_last;
+	std::size_t _M_bbegin_index;
+	bool _M_initialized = false;
+
+      public:
+	_LastNodeManager(_Hashtable& __htbl, __node_ptr __last)
+	: _M_htb(__htbl), _M_last(__last)
+	{ }
+
+#if _GLIBCXX_INLINE_VERSION
+	~_LastNodeManager()
+	{ _M_htb._M_last = _M_last; }
+#endif
+
+	void
+	_M_reset()
+	{
+	  _M_last = nullptr;
+	  _M_initialized = false;
+	}
+
+	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()
+	{ return _M_last; }
+
+	void
+	_M_set(__node_ptr __n)
+	{ _M_last = __n; }
+      };
+
       void
       _M_update_bbegin()
       {
@@ -425,6 +478,41 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
       _M_uses_single_bucket() const
       { return _M_uses_single_bucket(_M_buckets); }
 
+      __node_ptr
+      _M_get_last([[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
+      }
+
+      _LastNodeManager
+      _M_get_last_node_mgr(__node_ptr __usr_hint = nullptr)
+      { return _LastNodeManager(*this, _M_get_last(__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
+      }
+
       static constexpr size_t
       __small_size_threshold() noexcept
       {
@@ -612,11 +700,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 __last_mgr = _M_get_last_node_mgr();
+
 	// Do not shrink to keep potential user reservation.
 	if (_M_bucket_count < __l_bkt_count)
-	  rehash(__l_bkt_count);
+	  _M_rehash(__last_mgr, __l_bkt_count);
 
-	_M_insert_range(__l.begin(), __l.end(), __roan);
+	_M_insert_range(__l.begin(), __l.end(), __last_mgr, __roan);
 	return *this;
       }
 
@@ -837,31 +927,61 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	}
 
       // Insert a node at the beginning of a bucket.
-      void
-      _M_insert_bucket_begin(size_type __bkt, __node_ptr __node)
+      static void
+      _S_insert_bucket_begin(_LastNodeManager& __last_mgr,
+			     __node_base_ptr __bbegin_n, __buckets_ptr __buckets,
+			     size_type __bkt, __node_ptr __node)
       {
-	if (_M_buckets[__bkt])
+	__node_base_ptr __prev;
+	if (__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 = __buckets[__bkt];
 	  }
 	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 the last container node, insert after it.
+	    __node_ptr __last = __last_mgr._M_get();
+	    if (__last)
+	      {
+		__prev = __last;
+		__last_mgr._M_set(__node);
+	      }
+	    else
+	      {
+		// The bucket is empty, the new node is inserted at the
+		// beginning of the singly-linked list and the bucket will
+		// contain the before begin node.
+		__prev = __bbegin_n;
+
+		if (__prev->_M_nxt)
+		  {
+		    // We must update former begin bucket that is pointing to
+		    // _M_before_begin.
+		    size_type __bb_bkt = __last_mgr._M_get_bbegin_bkt(
+		      static_cast<__node_ptr>(__prev->_M_nxt));
+		    __buckets[__bb_bkt] = __node;
+		  }
+		else
+		  __last_mgr._M_set(__node);
+
+		__last_mgr._M_store_bbegin_bkt(__bkt);
+	      }
+
+	    __buckets[__bkt] = __prev;
 	  }
+
+	__node->_M_nxt = __prev->_M_nxt;
+	__prev->_M_nxt = __node;
+      }
+
+      void
+      _M_insert_bucket_begin(_LastNodeManager& __last_mgr,
+			     size_type __bkt, __node_ptr __node)
+      {
+	_S_insert_bucket_begin(__last_mgr, &_M_before_begin, _M_buckets,
+			       __bkt, __node);
       }
 
       // Remove the bucket first node
@@ -887,44 +1007,62 @@ _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;
-
       // 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(_LastNodeManager& __last_mgr,
+			    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(_LastNodeManager& __last_mgr, const key_type& __k,
+			   __node_ptr __n, __node_ptr __hash_code_n = nullptr);
 
       template<typename... _Args>
 	std::pair<iterator, bool>
-	_M_emplace(true_type __uks, _Args&&... __args);
+	_M_emplace_unique(_LastNodeManager&, _Args&&... __args);
 
       template<typename... _Args>
 	iterator
-	_M_emplace(false_type __uks, _Args&&... __args)
-	{ return _M_emplace(cend(), __uks, std::forward<_Args>(__args)...); }
+	_M_emplace_multi(_LastNodeManager&, _Args&&... __args);
+
+      template<typename... _Args>
+	std::pair<iterator, bool>
+	_M_emplace(true_type /*__uks*/, _Args&&... __args)
+	{
+	  auto __last_mgr = _M_get_last_node_mgr();
+	  return _M_emplace_unique(__last_mgr, std::forward<_Args>(__args)...);
+	}
+
+      template<typename... _Args>
+	iterator
+	_M_emplace(false_type /*__uks*/, _Args&&... __args)
+	{
+	  auto __last_mgr = _M_get_last_node_mgr();
+	  return _M_emplace_multi(__last_mgr, 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(_LastNodeManager& __last_mgr,
+		   true_type /*__uks*/, _Args&&... __args)
+	{
+	  return _M_emplace_unique(__last_mgr,
+				   std::forward<_Args>(__args)...).first;
+	}
 
       template<typename... _Args>
 	iterator
-	_M_emplace(const_iterator, false_type __uks, _Args&&... __args);
+	_M_emplace(_LastNodeManager& __last_mgr,
+		   false_type /*__uks*/, _Args&&... __args)
+	{ return _M_emplace_multi(__last_mgr, std::forward<_Args>(__args)...); }
 
       template<typename _Kt, typename _Arg, typename _NodeGenerator>
 	std::pair<iterator, bool>
-	_M_insert_unique(_Kt&&, _Arg&&, _NodeGenerator&);
+	_M_insert_unique(_LastNodeManager&, _Kt&&, _Arg&&, _NodeGenerator&);
 
       template<typename _Kt>
 	static __conditional_t<
@@ -944,9 +1082,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(_LastNodeManager& __last_mgr,
+			     _Arg&& __arg, _NodeGenerator& __node_gen)
 	{
-	  return _M_insert_unique(
+	  return _M_insert_unique(__last_mgr,
 	    _S_forward_key(_ExtractKey{}(std::forward<_Arg>(__arg))),
 	    std::forward<_Arg>(__arg), __node_gen);
 	}
@@ -956,9 +1095,10 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	_M_insert(_Arg&& __arg, _NodeGenerator& __node_gen,
 		  true_type /* __uks */)
 	{
+	  auto __last_mgr = _M_get_last_node_mgr();
 	  using __to_value
 	    = __detail::_ConvertToValueType<_ExtractKey, value_type>;
-	  return _M_insert_unique_aux(
+	  return _M_insert_unique_aux(__last_mgr,
 	    __to_value{}(std::forward<_Arg>(__arg)), __node_gen);
 	}
 
@@ -967,32 +1107,35 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	_M_insert(_Arg&& __arg, _NodeGenerator& __node_gen,
 		  false_type __uks)
 	{
+	  auto __last_mgr = _M_get_last_node_mgr();
 	  using __to_value
 	    = __detail::_ConvertToValueType<_ExtractKey, value_type>;
-	  return _M_insert(cend(),
+	  return _M_insert(__last_mgr,
 	    __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(_LastNodeManager& __last_mgr, _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(__last_mgr,
+	    __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(_LastNodeManager& __last_mgr, _Arg&& __arg,
 		  _NodeGenerator&, false_type __uks);
 
       template<typename _InputIterator, typename _NodeGenerator>
 	void
 	_M_insert_range(_InputIterator __first, _InputIterator __last,
-			_NodeGenerator&);
+			_LastNodeManager&, _NodeGenerator&);
 
       size_type
       _M_erase(true_type __uks, const key_type&);
@@ -1014,7 +1157,8 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	iterator
 	emplace_hint(const_iterator __hint, _Args&&... __args)
 	{
-	  return _M_emplace(__hint, __unique_keys{},
+	  auto __last_mgr = _M_get_last_node_mgr(__hint._M_cur);
+	  return _M_emplace(__last_mgr, __unique_keys{},
 			    std::forward<_Args>(__args)...);
 	}
 
@@ -1041,7 +1185,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 __last_mgr = _M_get_last_node_mgr();
+	_M_rehash(__last_mgr, __bkt_count);
+      }
 
       // DR 1189.
       // reserve, if present, comes from _Rehash_base.
@@ -1049,7 +1197,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 +1206,22 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	  {
 	    __glibcxx_assert(get_allocator() == __nh.get_allocator());
 
+	    auto __last_mgr = _M_get_last_node_mgr(__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)
+		  __last_mgr._M_set(__last_n);
 	      }
 
 	    __hash_code __code;
@@ -1086,8 +1242,8 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	      }
 	    else
 	      {
-		__ret.position
-		  = _M_insert_unique_node(__bkt, __code, __nh._M_ptr);
+		__ret.position = _M_insert_unique_node(
+		  __last_mgr, __bkt, __code, __nh._M_ptr);
 		__nh._M_ptr = nullptr;
 		__ret.inserted = true;
 	      }
@@ -1104,10 +1260,9 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 
 	__glibcxx_assert(get_allocator() == __nh.get_allocator());
 
+	auto __last_mgr = _M_get_last_node_mgr(__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 __ret = _M_insert_multi_node(__last_mgr, __k, __nh._M_ptr);
 	__nh._M_ptr = nullptr;
 	return __ret;
       }
@@ -1147,6 +1302,19 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	  return this->_M_hash_code(__k);
 	}
 
+      template<typename _H2>
+	iterator
+	_M_insert_multi_node(const _H2&, _LastNodeManager& __last_mgr,
+			     const key_type& __k, __node_ptr __equi_n,
+			     __node_ptr __n)
+	{
+	  if constexpr (std::is_same_v<_H2, _Hash>)
+	    if constexpr (std::is_empty_v<_Hash>)
+	      return _M_insert_multi_node(__last_mgr, __k, __n, __equi_n);
+
+	  return _M_insert_multi_node(__last_mgr, __k, __n);
+	}
+
     public:
       // Extract a node.
       node_type
@@ -1178,6 +1346,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	      node_type>, "Node types are compatible");
 	  __glibcxx_assert(get_allocator() == __src.get_allocator());
 
+	  auto __last_mgr = _M_get_last_node_mgr();
 	  auto __n_elt = __src.size();
 	  for (auto __i = __src.cbegin(), __end = __src.cend(); __i != __end;)
 	    {
@@ -1186,8 +1355,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 +1371,8 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 			--__n_elt;
 		      continue;
 		    }
+		  else
+		    __last_mgr._M_set(__last_n);
 		}
 
 	      __hash_code __code
@@ -1209,7 +1382,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(
+		    __last_mgr, __bkt, __code, __nh._M_ptr, __n_elt);
 		  __nh._M_ptr = nullptr;
 		  __n_elt = 1;
 		}
@@ -1227,27 +1401,28 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	      node_type>, "Node types are compatible");
 	  __glibcxx_assert(get_allocator() == __src.get_allocator());
 
-	  __node_ptr __hint = nullptr;
+	  auto __last_mgr = _M_get_last_node_mgr();
 	  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 __nh = __src.extract(__pos);
-	      __hint = _M_insert_multi_node(__hint, __code, __nh._M_ptr)._M_cur;
+	      _M_insert_multi_node(__src.hash_function(),
+				   __last_mgr, __k, __pos._M_cur, __nh._M_ptr);
 	      __nh._M_ptr = nullptr;
 	    }
 	}
 #endif // C++17
 
     private:
+      void _M_rehash(_LastNodeManager&, 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(_LastNodeManager&, 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(_LastNodeManager&, size_type __bkt_count, false_type __uks);
     };
 
   // Definitions of class template _Hashtable's out-of-line member functions.
@@ -1308,8 +1483,9 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	    _M_bucket_count = __bkt_count;
 	  }
 
+	auto __last_mgr = _M_get_last_node_mgr();
 	__alloc_node_gen_t __node_gen(*this);
-	_M_insert_range(__f, __l, __node_gen);
+	_M_insert_range(__f, __l, __last_mgr, __node_gen);
       }
 
   template<typename _Key, typename _Value, typename _Alloc,
@@ -1454,6 +1630,8 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 		  _M_buckets[__bkt] = __prev_n;
 		__prev_n = __this_n;
 	      }
+
+	    _M_set_last(__prev_n);
 	  }
 	__catch(...)
 	  {
@@ -1479,6 +1657,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 +1688,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 +1756,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 +1822,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 +2333,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(_LastNodeManager& __last_mgr, _Args&&... __args)
       -> pair<iterator, bool>
       {
 	// First build the node to get access to the hash code
@@ -2156,10 +2342,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 };
+
+	    __last_mgr._M_set(__last_n);
 	  }
 
 	__hash_code __code = this->_M_hash_code(__k);
@@ -2170,7 +2360,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(__last_mgr, __bkt, __code,
+					   __node._M_node);
 	__node._M_node = nullptr;
 	return { __pos, true };
       }
@@ -2183,17 +2374,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(_LastNodeManager& __last_mgr, _Args&&... __args)
       -> iterator
       {
-	// First build the node to get its hash code.
+	// First build the node to get its key and hash code.
 	_Scoped_node __node { this, std::forward<_Args>(__args)...  };
+
 	const key_type& __k = _ExtractKey{}(__node._M_node->_M_v());
+	auto __pos = _M_insert_multi_node(__last_mgr, __k, __node._M_node);
 
-	auto __res = this->_M_compute_hash_code(__hint._M_cur, __k);
-	auto __pos
-	  = _M_insert_multi_node(__res.first, __res.second, __node._M_node);
 	__node._M_node = nullptr;
 	return __pos;
       }
@@ -2205,36 +2394,8 @@ _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>
-    {
-      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) };
-
-	  __hint = nullptr;
-	}
-
-      return { __hint, this->_M_hash_code(__k) };
-    }
-
-  template<typename _Key, typename _Value, typename _Alloc,
-	   typename _ExtractKey, typename _Equal,
-	   typename _Hash, typename _RangeHash, typename _Unused,
-	   typename _RehashPolicy, typename _Traits>
-    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(_LastNodeManager& __last_mgr,
+			  size_type __bkt, __hash_code __code,
 			  __node_ptr __node, size_type __n_elt)
     -> iterator
     {
@@ -2245,7 +2406,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 
       if (__do_rehash.first)
 	{
-	  _M_rehash(__do_rehash.second, true_type{});
+	  _M_rehash(__last_mgr, __do_rehash.second, true_type{});
 	  __bkt = _M_bucket_index(__code);
 	}
 
@@ -2253,7 +2414,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(__last_mgr, __bkt, __node);
       ++_M_element_count;
       return iterator(__node);
     }
@@ -2265,51 +2426,74 @@ _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(_LastNodeManager& __last_mgr, const key_type& __k,
+			 __node_ptr __node, __node_ptr __equi_n)
     -> iterator
     {
+      // Compute hash code, if needed, so that we do not rehash if it throws.
+      __hash_code __code;
+      __node_base_ptr __prev = nullptr;
+      const size_type __size = size();
+      if (__size <= __small_size_threshold())
+	{
+	  __node_ptr __last_n = nullptr;
+	  __prev = &_M_before_begin;
+	  __node_ptr __n = static_cast<__node_ptr>(__prev->_M_nxt);
+	  for (; __n; __prev = __last_n = __n, __n = __n->_M_next())
+	    {
+	      if (this->_M_key_equals(__k, *__n))
+		{
+		  if (__hash_cached::value)
+		    __code = this->_M_hash_code(*__n);
+
+		  break;
+		}
+	    }
+
+	  if (!__n)
+	    {
+	      __prev = nullptr;
+	      __last_mgr._M_set(__last_n);
+	    }
+	}
+
+      if (!__prev)
+	{
+	  __code = __equi_n
+	    ? this->_M_hash_code(*__equi_n)
+	    : this->_M_hash_code(__k);
+	}
+
       __rehash_guard_t __rehash_guard(_M_rehash_policy);
       std::pair<bool, std::size_t> __do_rehash
 	= _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(__last_mgr, __do_rehash.second, false_type{});
 
       __rehash_guard._M_guarded_obj = nullptr;
       this->_M_store_code(*__node, __code);
-      const key_type& __k = _ExtractKey{}(__node->_M_v());
-      size_type __bkt = _M_bucket_index(__code);
 
-      // 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);
+      size_type __bkt;
+      if (!__prev)
+	{
+	  __bkt = _M_bucket_index(__code);
+	  if (__size > __small_size_threshold())
+	    __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;
-	      }
 	}
       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);
+	_M_insert_bucket_begin(__last_mgr, __bkt, __node);
+
       ++_M_element_count;
       return iterator(__node);
     }
@@ -2323,15 +2507,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(_LastNodeManager& __last_mgr, _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 };
+
+	    __last_mgr._M_set(__last_n);
+	  }
 
 	__hash_code __code = this->_M_hash_code_tr(__k);
 	size_type __bkt = _M_bucket_index(__code);
@@ -2346,8 +2536,9 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 				     __node_gen),
 	  this
 	};
+
 	auto __pos
-	  = _M_insert_unique_node(__bkt, __code, __node._M_node);
+	  = _M_insert_unique_node(__last_mgr, __bkt, __code, __node._M_node);
 	__node._M_node = nullptr;
 	return { __pos, true };
       }
@@ -2361,20 +2552,15 @@ _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(_LastNodeManager& __last_mgr, _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 };
-
-	// 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()));
+	_Scoped_node __node { __node_gen(std::forward<_Arg>(__v)), this };
 
-	auto __pos
-	  = _M_insert_multi_node(__res.first, __res.second, __node._M_node);
+	auto __pos = _M_insert_multi_node(
+	  __last_mgr, _ExtractKey{}(__node._M_node->_M_v()), __node._M_node);
 	__node._M_node = nullptr;
 	return __pos;
       }
@@ -2388,10 +2574,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)
+		      _LastNodeManager& __last_mgr, _NodeGenerator& __node_gen)
       {
 	for (; __first != __last; ++__first)
-	  _M_insert(*__first, __node_gen, __unique_keys{});
+	  _M_insert(__last_mgr, *__first, __node_gen, __unique_keys{});
       }
 
   template<typename _Key, typename _Value, typename _Alloc,
@@ -2438,7 +2624,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 +2733,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 +2783,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 +2801,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 +2811,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
     void
     _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
 	       _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
-    rehash(size_type __bkt_count)
+    _M_rehash(_LastNodeManager& __last_mgr, size_type __bkt_count)
     {
       __rehash_guard_t __rehash_guard(_M_rehash_policy);
       __bkt_count
@@ -2631,7 +2821,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 
       if (__bkt_count != _M_bucket_count)
 	{
-	  _M_rehash(__bkt_count, __unique_keys{});
+	  _M_rehash(__last_mgr, __bkt_count, __unique_keys{});
 	  __rehash_guard._M_guarded_obj = nullptr;
 	}
     }
@@ -2644,32 +2834,22 @@ _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(_LastNodeManager& __last_mgr,
+	      size_type __bkt_count, true_type /* __uks */)
     {
-      __buckets_ptr __new_buckets = _M_allocate_buckets(__bkt_count);
       __node_ptr __p = _M_begin();
+      __node_base_ptr __bbegin_n = &_M_before_begin;
+
+      __buckets_ptr __new_buckets = _M_allocate_buckets(__bkt_count);
       _M_before_begin._M_nxt = nullptr;
-      std::size_t __bbegin_bkt = 0;
+      __last_mgr._M_reset();
       while (__p)
 	{
 	  __node_ptr __next = __p->_M_next();
 	  std::size_t __bkt
 	    = __hash_code_base::_M_bucket_index(*__p, __bkt_count);
-	  if (!__new_buckets[__bkt])
-	    {
-	      __p->_M_nxt = _M_before_begin._M_nxt;
-	      _M_before_begin._M_nxt = __p;
-	      __new_buckets[__bkt] = &_M_before_begin;
-	      if (__p->_M_nxt)
-		__new_buckets[__bbegin_bkt] = __p;
-	      __bbegin_bkt = __bkt;
-	    }
-	  else
-	    {
-	      __p->_M_nxt = __new_buckets[__bkt]->_M_nxt;
-	      __new_buckets[__bkt]->_M_nxt = __p;
-	    }
-
+	  _S_insert_bucket_begin(__last_mgr, __bbegin_n, __new_buckets,
+				 __bkt, __p);
 	  __p = __next;
 	}
 
@@ -2687,16 +2867,18 @@ _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(_LastNodeManager& __last_mgr,
+	      size_type __bkt_count, false_type /* __uks */)
     {
-      __buckets_ptr __new_buckets = _M_allocate_buckets(__bkt_count);
       __node_ptr __p = _M_begin();
-      _M_before_begin._M_nxt = nullptr;
-      std::size_t __bbegin_bkt = 0;
+      __node_base_ptr __bbegin_n = &_M_before_begin;
       std::size_t __prev_bkt = 0;
       __node_ptr __prev_p = nullptr;
       bool __check_bucket = false;
 
+      __buckets_ptr __new_buckets = _M_allocate_buckets(__bkt_count);
+      _M_before_begin._M_nxt = nullptr;
+      __last_mgr._M_reset();
       while (__p)
 	{
 	  __node_ptr __next = __p->_M_next();
@@ -2711,6 +2893,9 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	      __p->_M_nxt = __prev_p->_M_nxt;
 	      __prev_p->_M_nxt = __p;
 
+	      if (!__p->_M_nxt)
+		__last_mgr._M_set(__p);
+
 	      // Inserting after a node in a bucket require to check that we
 	      // haven't change the bucket last node, in this case next
 	      // bucket containing its before begin node must be updated. We
@@ -2728,28 +2913,17 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 		    {
 		      std::size_t __next_bkt
 			= __hash_code_base::_M_bucket_index(
-			  *__prev_p->_M_next(), __bkt_count);
+			    *__prev_p->_M_next(), __bkt_count);
 		      if (__next_bkt != __prev_bkt)
 			__new_buckets[__next_bkt] = __prev_p;
 		    }
 		  __check_bucket = false;
 		}
 
-	      if (!__new_buckets[__bkt])
-		{
-		  __p->_M_nxt = _M_before_begin._M_nxt;
-		  _M_before_begin._M_nxt = __p;
-		  __new_buckets[__bkt] = &_M_before_begin;
-		  if (__p->_M_nxt)
-		    __new_buckets[__bbegin_bkt] = __p;
-		  __bbegin_bkt = __bkt;
-		}
-	      else
-		{
-		  __p->_M_nxt = __new_buckets[__bkt]->_M_nxt;
-		  __new_buckets[__bkt]->_M_nxt = __p;
-		}
+	      _S_insert_bucket_begin(__last_mgr, __bbegin_n, __new_buckets,
+				     __bkt, __p);
 	    }
+
 	  __prev_p = __p;
 	  __prev_bkt = __bkt;
 	  __p = __next;
diff --git a/libstdc++-v3/include/bits/hashtable_policy.h b/libstdc++-v3/include/bits/hashtable_policy.h
index 9f775522cff..69ef84ad519 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 __last_mgr = __h->_M_get_last_node_mgr();
+      auto __pos =  __h->_M_insert_unique_node(__last_mgr, __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 __last_mgr = __h->_M_get_last_node_mgr();
+      auto __pos = __h->_M_insert_unique_node(__last_mgr, __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 __last_mgr = __h._M_get_last_node_mgr(__hint._M_cur);
+	__node_gen_type __node_gen(__h);
+	return __h._M_insert(__last_mgr, __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 __last_mgr = __h._M_get_last_node_mgr(__hint._M_cur);
+	  auto __it = __h._M_insert_unique_node(__last_mgr, __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 __last_mgr = __h._M_get_last_node_mgr();
 	__node_gen_type __node_gen(__h);
-	__h._M_insert_range(__first, __last, __node_gen);
+	__h._M_insert_range(__first, __last, __last_mgr, __node_gen);
       }
 
   template<typename _Key, typename _Value, typename _Alloc,
@@ -1037,6 +1042,7 @@ namespace __detail
 	  return;
 
 	__hashtable& __h = _M_conjure_hashtable();
+	auto __last_mgr = __h._M_get_last_node_mgr();
 	__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(__last_mgr, __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, __last_mgr, __node_gen);
       }
 
   /**
@@ -1102,8 +1108,9 @@ namespace __detail
       insert(const_iterator __hint, value_type&& __v)
       {
 	__hashtable& __h = this->_M_conjure_hashtable();
+	auto __last_mgr = __h._M_get_last_node_mgr(__hint._M_cur);
 	__node_gen_type __node_gen(__h);
-	return __h._M_insert(__hint, std::move(__v), __node_gen,
+	return __h._M_insert(__last_mgr, 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 __last_mgr = __h._M_get_last_node_mgr(__hint._M_cur);
+	  return __h._M_emplace(__last_mgr, __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_map/consistency_check.cc b/libstdc++-v3/testsuite/23_containers/unordered_map/consistency_check.cc
new file mode 100644
index 00000000000..bac37c39a83
--- /dev/null
+++ b/libstdc++-v3/testsuite/23_containers/unordered_map/consistency_check.cc
@@ -0,0 +1,108 @@
+// { dg-do run { target c++11 } }
+
+#include <string>
+#include <sstream>
+#include <vector>
+#include <unordered_map>
+
+#include <testsuite_hooks.h>
+
+namespace
+{
+  const int nb_elements = 2000;
+
+  template<typename _ElemType>
+  void check(const std::unordered_map<_ElemType, int>& us)
+    {
+      VERIFY( std::distance(us.begin(), us.end()) == us.size() );
+      std::size_t bkt_elems_count = 0;
+      for (std::size_t i = 0; i != us.bucket_count(); ++i)
+	{
+	  if (us.bucket_size(i) == 0)
+	    continue;
+
+	  bkt_elems_count += us.bucket_size(i);
+	  for (auto lit = us.begin(i); lit != us.end(i); ++lit)
+	    {
+	      VERIFY( us.bucket(lit->first) == i );
+	    }
+	}
+
+      VERIFY( bkt_elems_count == us.size() );
+    }
+
+  template<typename _ElemType>
+    void run(const std::vector<_ElemType>& elems, bool with_copy)
+    {
+      std::unordered_map<_ElemType, int> um;
+      check(um);
+
+      for (int i = 0; i != nb_elements; ++i)
+	{
+	  um.insert({ elems[i], i });
+	  check(um);
+	}
+
+      if (with_copy)
+	{
+	  std::unordered_map<_ElemType, int>(um).swap(um);
+	  check(um);
+	}
+
+      for (int i = nb_elements - 1; i >= 0; --i)
+	{
+	  auto it = um.find(elems[i]);
+	  if (it != um.end())
+	    {
+	      um.erase(it);
+	      check(um);
+	    }
+	}
+
+      um.insert({ elems[0], 0 });
+      check(um);
+
+      for (int i = nb_elements - 1; i >= 0; --i)
+	{
+	  um.insert({ elems[i], i });
+	  check(um);
+	}
+
+      for (int j = nb_elements - 1; j >= 0; --j)
+	{
+	  um.erase(elems[j]);
+	  check(um);
+	}
+    }
+}
+
+int main()
+{
+  {
+    std::vector<int> elems;
+    elems.reserve(nb_elements);
+    for (int i = 0; i != nb_elements; ++i)
+      elems.push_back(i);
+
+    run(elems, false);
+    run(elems, true);
+  }
+
+  {
+    std::vector<std::string> elems;
+    {
+      elems.reserve(nb_elements);
+      for (int i = 0; i != nb_elements; ++i)
+	{
+	  std::ostringstream ostr;
+	  ostr << "string #" << i << ' ' << std::string(1000, 'a' + i);
+	  elems.push_back(ostr.str());
+	}
+    }
+
+    run(elems, false);
+    run(elems, true);
+  }
+
+  return 0;
+}
diff --git a/libstdc++-v3/testsuite/23_containers/unordered_multimap/consistency_check.cc b/libstdc++-v3/testsuite/23_containers/unordered_multimap/consistency_check.cc
new file mode 100644
index 00000000000..c4f26553d8a
--- /dev/null
+++ b/libstdc++-v3/testsuite/23_containers/unordered_multimap/consistency_check.cc
@@ -0,0 +1,111 @@
+// { dg-do run { target c++11 } }
+
+#include <string>
+#include <sstream>
+#include <vector>
+#include <unordered_map>
+
+#include <testsuite_hooks.h>
+
+namespace
+{
+  const int nb_elements = 1000;
+  const int nb_copies = 5;
+
+  template<typename _ElemType>
+  void check(const std::unordered_multimap<_ElemType, int>& um)
+    {
+      VERIFY( std::distance(um.begin(), um.end()) == um.size() );
+      std::size_t bkt_elems_count = 0;
+      for (std::size_t i = 0; i != um.bucket_count(); ++i)
+	{
+	  if (um.bucket_size(i) == 0)
+	    continue;
+
+	  bkt_elems_count += um.bucket_size(i);
+	  for (auto lit = um.begin(i); lit != um.end(i); ++lit)
+	    {
+	      VERIFY( um.bucket(lit->first) == i );
+	    }
+	}
+
+      VERIFY( bkt_elems_count == um.size() );
+    }
+
+  template<typename _ElemType>
+    void run(const std::vector<_ElemType>& elems, bool with_copy)
+    {
+      std::unordered_multimap<_ElemType, int> um;
+      um.max_load_factor(nb_copies);
+      check(um);
+
+      for (int h = 0; h != nb_copies; ++h)
+	for (int i = 0; i != nb_elements; ++i)
+	  {
+	    um.insert({ elems[i], i + i * h });
+	    check(um);
+	  }
+
+      if (with_copy)
+	{
+	  std::unordered_multimap<_ElemType, int>(um).swap(um);
+	  check(um);
+	}
+
+      for (int i = nb_elements - 1; i >= 0; --i)
+	{
+	  auto it = um.find(elems[i]);
+	  if (it != um.end())
+	    {
+	      um.erase(it);
+	      check(um);
+	    }
+	}
+
+      um.insert({ elems[0], 0 });
+      check(um);
+
+      for (int i = nb_elements - 1; i >= 0; --i)
+	{
+	  um.insert({ elems[i], i });
+	  check(um);
+	}
+
+      for (int j = nb_elements - 1; j >= 0; --j)
+	{
+	  um.erase(elems[j]);
+	  check(um);
+	}
+    }
+}
+
+int main()
+{
+  {
+    std::vector<int> elems;
+    elems.reserve(nb_elements);
+    for (int i = 0; i != nb_elements; ++i)
+      elems.push_back(i);
+
+    run(elems, false);
+    run(elems, true);
+  }
+
+  {
+    std::vector<std::string> elems;
+    {
+      elems.reserve(nb_elements);
+      for (int i = 0; i != nb_elements; ++i)
+	{
+	  std::ostringstream ostr;
+	  ostr << "string #" << i << ' ' << std::string(1000, 'a' + i);
+	  elems.push_back(ostr.str());
+	}
+    }
+
+    run(elems, false);
+    run(elems, true);
+  }
+
+  return 0;
+}
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()
diff --git a/libstdc++-v3/testsuite/23_containers/unordered_multiset/consistency_check.cc b/libstdc++-v3/testsuite/23_containers/unordered_multiset/consistency_check.cc
new file mode 100644
index 00000000000..f463a2cee1d
--- /dev/null
+++ b/libstdc++-v3/testsuite/23_containers/unordered_multiset/consistency_check.cc
@@ -0,0 +1,110 @@
+// { dg-do run { target c++11 } }
+
+#include <string>
+#include <sstream>
+#include <vector>
+#include <unordered_set>
+
+#include <testsuite_hooks.h>
+
+namespace
+{
+  const int nb_elements = 1000;
+  const int nb_copies = 5;
+
+  template<typename _ElemType>
+    void check(const std::unordered_multiset<_ElemType>& us)
+    {
+      VERIFY( std::distance(us.begin(), us.end()) == us.size() );
+      std::size_t bkt_elems_count = 0;
+      for (std::size_t i = 0; i != us.bucket_count(); ++i)
+	{
+	  if (us.bucket_size(i) == 0)
+	    continue;
+
+	  bkt_elems_count += us.bucket_size(i);
+	  for (auto lit = us.begin(i); lit != us.end(i); ++lit)
+	    {
+	      VERIFY( us.bucket(*lit) == i );
+	    }
+	}
+
+      VERIFY( bkt_elems_count == us.size() );
+    }
+
+  template<typename _ElemType>
+    void run(const std::vector<_ElemType>& elems, bool with_copy)
+    {
+      std::unordered_multiset<_ElemType> us;
+      us.max_load_factor(nb_copies);
+      check(us);
+
+      for (int h = 0; h != nb_copies; ++h)
+	for (int i = 0; i != nb_elements; ++i)
+	  {
+	    us.insert(elems[i]);
+	    check(us);
+	  }
+
+      if (with_copy)
+	{
+	  std::unordered_multiset<_ElemType>(us).swap(us);
+	  check(us);
+	}
+
+      for (int i = nb_elements - 1; i >= 0; --i)
+	{
+	  auto it = us.find(elems[i]);
+	  if (it != us.end())
+	    {
+	      us.erase(it);
+	      check(us);
+	    }
+	}
+
+      us.insert(elems[0]);
+      check(us);
+      for (int i = nb_elements - 1; i >= 0; --i)
+	{
+	  us.insert(elems[i]);
+	  check(us);
+	}
+
+      for (int j = nb_elements - 1; j >= 0; --j)
+	{
+	  us.erase(elems[j]);
+	  check(us);
+	}
+    }
+}
+
+int main()
+{
+  {
+    std::vector<int> elems;
+    elems.reserve(nb_elements);
+    for (int i = 0; i != nb_elements; ++i)
+      elems.push_back(i);
+
+    run(elems, false);
+    run(elems, true);
+  }
+
+  {
+    std::vector<std::string> elems;
+    {
+      elems.reserve(nb_elements);
+      for (int i = 0; i != nb_elements; ++i)
+	{
+	  std::ostringstream ostr;
+	  ostr << "string #" << i << ' ' << std::string(1000, 'a' + i);
+	  elems.push_back(ostr.str());
+	}
+    }
+
+    run(elems, false);
+    run(elems, true);
+  }
+
+  return 0;
+}
diff --git a/libstdc++-v3/testsuite/23_containers/unordered_set/consistency_check.cc b/libstdc++-v3/testsuite/23_containers/unordered_set/consistency_check.cc
new file mode 100644
index 00000000000..70581c557ad
--- /dev/null
+++ b/libstdc++-v3/testsuite/23_containers/unordered_set/consistency_check.cc
@@ -0,0 +1,107 @@
+// { dg-do run { target c++11 } }
+
+#include <string>
+#include <sstream>
+#include <vector>
+#include <unordered_set>
+
+#include <testsuite_hooks.h>
+
+namespace
+{
+  const int nb_elements = 2000;
+
+  template<typename _ElemType>
+    void check(const std::unordered_set<_ElemType>& us)
+    {
+      VERIFY( std::distance(us.begin(), us.end()) == us.size() );
+      std::size_t bkt_elems_count = 0;
+      for (std::size_t i = 0; i != us.bucket_count(); ++i)
+	{
+	  if (us.bucket_size(i) == 0)
+	    continue;
+
+	  bkt_elems_count += us.bucket_size(i);
+	  for (auto lit = us.begin(i); lit != us.end(i); ++lit)
+	    {
+	      VERIFY( us.bucket(*lit) == i );
+	    }
+	}
+
+      VERIFY( bkt_elems_count == us.size() );
+    }
+
+  template<typename _ElemType>
+    void run(const std::vector<_ElemType>& elems, bool with_copy)
+    {
+      std::unordered_set<_ElemType> us;
+      check(us);
+
+      for (int i = 0; i != nb_elements; ++i)
+	{
+	  us.insert(elems[i]);
+	  check(us);
+	}
+
+      if (with_copy)
+	{
+	  std::unordered_set<_ElemType>(us).swap(us);
+	  check(us);
+	}
+
+      for (int i = nb_elements - 1; i >= 0; --i)
+	{
+	  auto it = us.find(elems[i]);
+	  if (it != us.end())
+	    {
+	      us.erase(it);
+	      check(us);
+	    }
+	}
+
+      us.insert(elems[0]);
+      check(us);
+      for (int i = nb_elements - 1; i >= 0; --i)
+	{
+	  us.insert(elems[i]);
+	  check(us);
+	}
+
+      for (int j = nb_elements - 1; j >= 0; --j)
+	{
+	  us.erase(elems[j]);
+	  check(us);
+	}
+    }
+}
+
+int main()
+{
+  {
+    std::vector<int> elems;
+    elems.reserve(nb_elements);
+    for (int i = 0; i != nb_elements; ++i)
+      elems.push_back(i);
+
+    run(elems, false);
+    run(elems, true);
+  }
+
+  {
+    std::vector<std::string> elems;
+    {
+      elems.reserve(nb_elements);
+      for (int i = 0; i != nb_elements; ++i)
+	{
+	  std::ostringstream ostr;
+	  ostr << "string #" << i << ' ' << std::string(1000, 'a' + i);
+	  elems.push_back(ostr.str());
+	}
+    }
+
+    run(elems, false);
+    run(elems, true);
+  }
+
+  return 0;
+}
diff --git a/libstdc++-v3/testsuite/libstdc++-prettyprinters/cxx11.cc b/libstdc++-v3/testsuite/libstdc++-prettyprinters/cxx11.cc
index 0f1736a1550..4b16354a26b 100644
--- a/libstdc++-v3/testsuite/libstdc++-prettyprinters/cxx11.cc
+++ b/libstdc++-v3/testsuite/libstdc++-prettyprinters/cxx11.cc
@@ -103,10 +103,10 @@ main()
   std::unordered_map<int, std::string> uom;
   uom[5] = "three";
   uom[3] = "seven";
-// { dg-final { regexp-test uom {std::(__debug::)?unordered_map with 2 elements = {\[3\] = "seven", \[5\] = "three"}} } }
+// { dg-final { regexp-test uom {std::(__debug::)?unordered_map with 2 elements = {\[5\] = "three", \[3\] = "seven"}} } }
 
   std::unordered_map<int, std::string> &ruom = uom;
-// { dg-final { regexp-test ruom {std::(__debug::)?unordered_map with 2 elements = {\[3\] = "seven", \[5\] = "three"}} } }
+// { dg-final { regexp-test ruom {std::(__debug::)?unordered_map with 2 elements = {\[5\] = "three", \[3\] = "seven"}} } }
 
   std::unordered_multimap<int, std::string> uomm;
   uomm.insert(std::pair<int, std::string> (5, "three"));