public inbox for libstdc++@gcc.gnu.org
 help / color / mirror / Atom feed
* libstdc++ PR 57272 Fancy pointer support in Hashtable
@ 2020-04-19 17:31 François Dumont
  2020-05-15 21:12 ` François Dumont
  0 siblings, 1 reply; 10+ messages in thread
From: François Dumont @ 2020-04-19 17:31 UTC (permalink / raw)
  To: libstdc++

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

Here is my work in progress to use allocator pointer type. This type is 
used both as the node pointer and as the buckets pointer.

Rather than adapting _Local_iterator_base like _Node_iterator_base I 
prefer to just make it inherits from _Node_iterator_base. It simplifies 
its implementation and avoids to provided dedicated comparison operators.

Now I wonder if I need to consider Phil Bouchard comment regarding how 
node pointers are being passed, either by value or reference. I already 
chose to pass them as rvalue references in some occasions and even 
lvalue reference like in _M_bucket_index method. Do you think I need to 
continue this way ? Maybe I should use some conditional type, if raw 
pointer we pass by value and otherwise we pass by ref ?

François


[-- Attachment #2: hashtable_ext_ptr.patch --]
[-- Type: text/x-patch, Size: 83210 bytes --]

diff --git a/libstdc++-v3/include/bits/hashtable.h b/libstdc++-v3/include/bits/hashtable.h
index b00319a668b..995a7a568a3 100644
--- a/libstdc++-v3/include/bits/hashtable.h
+++ b/libstdc++-v3/include/bits/hashtable.h
@@ -171,8 +171,9 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	   typename _H1, typename _H2, typename _Hash,
 	   typename _RehashPolicy, typename _Traits>
     class _Hashtable
-    : public __detail::_Hashtable_base<_Key, _Value, _ExtractKey, _Equal,
-				       _H1, _H2, _Hash, _Traits>,
+    : public __detail::_Hashtable_base<_Key, _Value, _Alloc,
+					 _ExtractKey, _Equal,
+					 _H1, _H2, _Hash, _Traits>,
       public __detail::_Map_base<_Key, _Value, _Alloc, _ExtractKey, _Equal,
 				 _H1, _H2, _Hash, _RehashPolicy, _Traits>,
       public __detail::_Insert<_Key, _Value, _Alloc, _ExtractKey, _Equal,
@@ -182,9 +183,9 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
       public __detail::_Equality<_Key, _Value, _Alloc, _ExtractKey, _Equal,
 				 _H1, _H2, _Hash, _RehashPolicy, _Traits>,
       private __detail::_Hashtable_alloc<
-	__alloc_rebind<_Alloc,
-		       __detail::_Hash_node<_Value,
-					    _Traits::__hash_cached::value>>>
+	__alloc_rebind<_Alloc, __detail::_Hash_node<
+	  typename std::allocator_traits<_Alloc>::pointer, _Value,
+				 _Traits::__hash_cached::value>>>
     {
       static_assert(is_same<typename remove_cv<_Value>::type, _Value>::value,
 	  "unordered container must have a non-const, non-volatile value_type");
@@ -195,8 +196,13 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 
       using __traits_type = _Traits;
       using __hash_cached = typename __traits_type::__hash_cached;
-      using __node_type = __detail::_Hash_node<_Value, __hash_cached::value>;
+      using __hashtable_base = __detail::
+			      _Hashtable_base<_Key, _Value, _Alloc, _ExtractKey,
+					      _Equal, _H1, _H2, _Hash, _Traits>;
+
+      using __node_type = typename __hashtable_base::__node_type;
       using __node_alloc_type = __alloc_rebind<_Alloc, __node_type>;
+      using __node_pointer = typename __hashtable_base::__node_pointer;
 
       using __hashtable_alloc = __detail::_Hashtable_alloc<__node_alloc_type>;
 
@@ -206,6 +212,9 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	typename __hashtable_alloc::__node_alloc_traits;
       using __node_base = typename __hashtable_alloc::__node_base;
       using __bucket_type = typename __hashtable_alloc::__bucket_type;
+      using __bucket_pointer = typename __hashtable_alloc::__bucket_pointer;
+      using __bucket_ptr_traits = std::pointer_traits<__bucket_pointer>;
+      using __node_base_ptr_traits = std::pointer_traits<__bucket_type>;
 
     public:
       typedef _Key						key_type;
@@ -232,10 +241,6 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 				       	     __detail::_Identity,
 					     __detail::_Select1st>::type;
 
-      using __hashtable_base = __detail::
-			       _Hashtable_base<_Key, _Value, _ExtractKey,
-					      _Equal, _H1, _H2, _Hash, _Traits>;
-
       using __hash_code_base =  typename __hashtable_base::__hash_code_base;
       using __hash_code =  typename __hashtable_base::__hash_code;
       using __ireturn_type = typename __hashtable_base::__ireturn_type;
@@ -262,8 +267,8 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
       struct _Scoped_node
       {
 	// Take ownership of a node with a constructed element.
-	_Scoped_node(__node_type* __n, __hashtable_alloc* __h)
-	: _M_h(__h), _M_node(__n) { }
+	_Scoped_node(__node_pointer&& __n, __hashtable_alloc* __h)
+	  : _M_h(__h), _M_node(std::move(__n)) { }
 
 	// Allocate a node and construct an element within it.
 	template<typename... _Args>
@@ -279,7 +284,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	_Scoped_node& operator=(const _Scoped_node&) = delete;
 
 	__hashtable_alloc* _M_h;
-	__node_type* _M_node;
+	__node_pointer _M_node;
       };
 
       template<typename _Ht>
@@ -306,7 +311,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
       // Getting a bucket index from a node shall not throw because it is used
       // in methods (erase, swap...) that shall not throw.
       static_assert(noexcept(declval<const __hash_code_base_access&>()
-			     ._M_bucket_index((const __node_type*)nullptr,
+			     ._M_bucket_index(declval<const __node_pointer&>(),
 					      (std::size_t)0)),
 		    "Cache the hash code or qualify your functors involved"
 		    " in hash code and bucket index computation with noexcept");
@@ -361,7 +366,8 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 #endif
 
     private:
-      __bucket_type*		_M_buckets		= &_M_single_bucket;
+      __bucket_pointer		_M_buckets
+	= __bucket_ptr_traits::pointer_to(_M_single_bucket);
       size_type			_M_bucket_count		= 1;
       __node_base		_M_before_begin;
       size_type			_M_element_count	= 0;
@@ -376,8 +382,11 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
       __bucket_type		_M_single_bucket	= nullptr;
 
       bool
-      _M_uses_single_bucket(__bucket_type* __bkts) const
-      { return __builtin_expect(__bkts == &_M_single_bucket, false); }
+      _M_uses_single_bucket(const __bucket_pointer& __bkts) const
+      {
+	return __builtin_expect(std::__to_address(__bkts) == &_M_single_bucket,
+				false);
+      }
 
       bool
       _M_uses_single_bucket() const
@@ -386,20 +395,20 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
       __hashtable_alloc&
       _M_base_alloc() { return *this; }
 
-      __bucket_type*
+      __bucket_pointer
       _M_allocate_buckets(size_type __bkt_count)
       {
 	if (__builtin_expect(__bkt_count == 1, false))
 	  {
 	    _M_single_bucket = nullptr;
-	    return &_M_single_bucket;
+	    return __bucket_ptr_traits::pointer_to(_M_single_bucket);
 	  }
 
 	return __hashtable_alloc::_M_allocate_buckets(__bkt_count);
       }
 
       void
-      _M_deallocate_buckets(__bucket_type* __bkts, size_type __bkt_count)
+      _M_deallocate_buckets(__bucket_pointer __bkts, size_type __bkt_count)
       {
 	if (_M_uses_single_bucket(__bkts))
 	  return;
@@ -413,13 +422,9 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 
       // Gets bucket begin, deals with the fact that non-empty buckets contain
       // their before begin node.
-      __node_type*
+      __node_pointer
       _M_bucket_begin(size_type __bkt) const;
 
-      __node_type*
-      _M_begin() const
-      { return static_cast<__node_type*>(_M_before_begin._M_nxt); }
-
       // Assign *this using another _Hashtable instance. Whether elements
       // are copied or moved depends on the _Ht reference.
       template<typename _Ht>
@@ -523,7 +528,8 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
       _Hashtable&
       operator=(initializer_list<value_type> __l)
       {
-	__reuse_or_alloc_node_gen_t __roan(_M_begin(), *this);
+	__reuse_or_alloc_node_gen_t __roan(std::move(_M_before_begin._M_nxt),
+					   *this);
 	_M_before_begin._M_nxt = nullptr;
 	clear();
 	this->_M_insert_range(__l.begin(), __l.end(), __roan, __unique_keys());
@@ -540,11 +546,11 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
       // Basic container operations
       iterator
       begin() noexcept
-      { return iterator(_M_begin()); }
+      { return iterator(_M_before_begin._M_nxt); }
 
       const_iterator
       begin() const noexcept
-      { return const_iterator(_M_begin()); }
+      { return const_iterator(_M_before_begin._M_nxt); }
 
       iterator
       end() noexcept
@@ -556,7 +562,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 
       const_iterator
       cbegin() const noexcept
-      { return const_iterator(_M_begin()); }
+      { return const_iterator(_M_before_begin._M_nxt); }
 
       const_iterator
       cend() const noexcept
@@ -674,7 +680,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
     protected:
       // Bucket index computation helpers.
       size_type
-      _M_bucket_index(__node_type* __n) const noexcept
+      _M_bucket_index(const __node_pointer& __n) const noexcept
       { return __hash_code_base::_M_bucket_index(__n, _M_bucket_count); }
 
       size_type
@@ -683,45 +689,45 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 
       // Find and insert helper functions and types
       // Find the node before the one matching the criteria.
-      __node_base*
+      __bucket_type
       _M_find_before_node(size_type, const key_type&, __hash_code) const;
 
-      __node_type*
+      __node_pointer
       _M_find_node(size_type __bkt, const key_type& __key,
 		   __hash_code __c) const
       {
-	__node_base* __before_n = _M_find_before_node(__bkt, __key, __c);
+	__bucket_type __before_n = _M_find_before_node(__bkt, __key, __c);
 	if (__before_n)
-	  return static_cast<__node_type*>(__before_n->_M_nxt);
+	  return __before_n->_M_nxt;
 	return nullptr;
       }
 
       // Insert a node at the beginning of a bucket.
       void
-      _M_insert_bucket_begin(size_type, __node_type*);
+      _M_insert_bucket_begin(size_type, __node_pointer);
 
       // Remove the bucket first node
       void
-      _M_remove_bucket_begin(size_type __bkt, __node_type* __next_n,
+      _M_remove_bucket_begin(size_type __bkt, __node_pointer __next_n,
 			     size_type __next_bkt);
 
       // Get the node before __n in the bucket __bkt
-      __node_base*
-      _M_get_previous_node(size_type __bkt, __node_base* __n);
+      __bucket_type
+      _M_get_previous_node(size_type __bkt, const __node_pointer& __n);
 
       // Insert node __n with key __k and 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(const key_type& __k, size_type __bkt,
-			    __hash_code __code, __node_type* __n,
+			    __hash_code __code, __node_pointer __n,
 			    size_type __n_elt = 1);
 
       // Insert node __n with key __k and hash code __code.
       // Takes ownership of __n if insertion succeeds, throws otherwise.
       iterator
-      _M_insert_multi_node(__node_type* __hint, const key_type& __k,
-			   __hash_code __code, __node_type* __n);
+      _M_insert_multi_node(__node_pointer __hint, const key_type& __k,
+			   __hash_code __code, __node_pointer __n);
 
       template<typename... _Args>
 	std::pair<iterator, bool>
@@ -778,7 +784,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
       _M_erase(false_type, const key_type&);
 
       iterator
-      _M_erase(size_type __bkt, __node_base* __prev_n, __node_type* __n);
+      _M_erase(size_type __bkt, __bucket_type __prev_n, __node_pointer __n);
 
     public:
       // Emplace
@@ -838,7 +844,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	    const key_type& __k = __nh._M_key();
 	    __hash_code __code = this->_M_hash_code(__k);
 	    size_type __bkt = _M_bucket_index(__k, __code);
-	    if (__node_type* __n = _M_find_node(__bkt, __k, __code))
+	    if (__node_pointer __n = _M_find_node(__bkt, __k, __code))
 	      {
 		__ret.node = std::move(__nh);
 		__ret.position = iterator(__n);
@@ -874,15 +880,15 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 
     private:
       node_type
-      _M_extract_node(size_t __bkt, __node_base* __prev_n)
+      _M_extract_node(size_t __bkt, __bucket_type __prev_n)
       {
-	__node_type* __n = static_cast<__node_type*>(__prev_n->_M_nxt);
+	__node_pointer __n = __prev_n->_M_nxt;
 	if (__prev_n == _M_buckets[__bkt])
-	  _M_remove_bucket_begin(__bkt, __n->_M_next(),
-	     __n->_M_nxt ? _M_bucket_index(__n->_M_next()) : 0);
+	  _M_remove_bucket_begin(__bkt, __n->_M_nxt,
+	     __n->_M_nxt ? _M_bucket_index(__n->_M_nxt) : 0);
 	else if (__n->_M_nxt)
 	  {
-	    size_type __next_bkt = _M_bucket_index(__n->_M_next());
+	    size_type __next_bkt = _M_bucket_index(__n->_M_nxt);
 	    if (__next_bkt != __bkt)
 	      _M_buckets[__next_bkt] = __prev_n;
 	  }
@@ -910,7 +916,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	node_type __nh;
 	__hash_code __code = this->_M_hash_code(__k);
 	std::size_t __bkt = _M_bucket_index(__k, __code);
-	if (__node_base* __prev_node = _M_find_before_node(__bkt, __k, __code))
+	if (__bucket_type __prev_node = _M_find_before_node(__bkt, __k, __code))
 	  __nh = _M_extract_node(__bkt, __prev_node);
 	return __nh;
       }
@@ -981,10 +987,10 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
     _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
 	       _H1, _H2, _Hash, _RehashPolicy, _Traits>::
     _M_bucket_begin(size_type __bkt) const
-    -> __node_type*
+    -> __node_pointer
     {
-      __node_base* __n = _M_buckets[__bkt];
-      return __n ? static_cast<__node_type*>(__n->_M_nxt) : nullptr;
+      __bucket_type __n = _M_buckets[__bkt];
+      return __n ? __n->_M_nxt : nullptr;
     }
 
   template<typename _Key, typename _Value,
@@ -1058,7 +1064,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	      && __this_alloc != __that_alloc)
 	    {
 	      // Replacement allocator cannot free existing storage.
-	      this->_M_deallocate_nodes(_M_begin());
+	      this->_M_deallocate_nodes(_M_before_begin._M_nxt);
 	      _M_before_begin._M_nxt = nullptr;
 	      _M_deallocate_buckets();
 	      _M_buckets = nullptr;
@@ -1099,7 +1105,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 		 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
       _M_assign_elements(_Ht&& __ht)
       {
-	__bucket_type* __former_buckets = nullptr;
+	__bucket_pointer __former_buckets = nullptr;
 	std::size_t __former_bucket_count = _M_bucket_count;
 	const __rehash_state& __former_state = _M_rehash_policy._M_state();
 
@@ -1118,7 +1124,8 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	    __hashtable_base::operator=(std::forward<_Ht>(__ht));
 	    _M_element_count = __ht._M_element_count;
 	    _M_rehash_policy = __ht._M_rehash_policy;
-	    __reuse_or_alloc_node_gen_t __roan(_M_begin(), *this);
+	    __reuse_or_alloc_node_gen_t
+	      __roan(std::move(_M_before_begin._M_nxt), *this);
 	    _M_before_begin._M_nxt = nullptr;
 	    _M_assign(std::forward<_Ht>(__ht), __roan);
 	    if (__former_buckets)
@@ -1150,7 +1157,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 		 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
       _M_assign(_Ht&& __ht, const _NodeGenerator& __node_gen)
       {
-	__bucket_type* __buckets = nullptr;
+	__bucket_pointer __buckets = nullptr;
 	if (!_M_buckets)
 	  _M_buckets = __buckets = _M_allocate_buckets(_M_bucket_count);
 
@@ -1161,16 +1168,17 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 
 	    // First deal with the special first node pointed to by
 	    // _M_before_begin.
-	    __node_type* __ht_n = __ht._M_begin();
-	    __node_type* __this_n
+	    __node_pointer __ht_n = __ht._M_before_begin._M_nxt;
+	    __node_pointer __this_n
 	      = __node_gen(__fwd_value_for<_Ht>(__ht_n->_M_v()));
 	    this->_M_copy_code(__this_n, __ht_n);
 	    _M_before_begin._M_nxt = __this_n;
-	    _M_buckets[_M_bucket_index(__this_n)] = &_M_before_begin;
+	    _M_buckets[_M_bucket_index(__this_n)] =
+	      __node_base_ptr_traits::pointer_to(_M_before_begin);
 
 	    // Then deal with other nodes.
-	    __node_base* __prev_n = __this_n;
-	    for (__ht_n = __ht_n->_M_next(); __ht_n; __ht_n = __ht_n->_M_next())
+	    __node_pointer __prev_n = __this_n;
+	    for (__ht_n = __ht_n->_M_nxt; __ht_n; __ht_n = __ht_n->_M_nxt)
 	      {
 		__this_n = __node_gen(__fwd_value_for<_Ht>(__ht_n->_M_v()));
 		__prev_n->_M_nxt = __this_n;
@@ -1202,7 +1210,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
       _M_rehash_policy._M_reset();
       _M_bucket_count = 1;
       _M_single_bucket = nullptr;
-      _M_buckets = &_M_single_bucket;
+      _M_buckets = __bucket_ptr_traits::pointer_to(_M_single_bucket);
       _M_before_begin._M_nxt = nullptr;
       _M_element_count = 0;
     }
@@ -1216,26 +1224,28 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	       _H1, _H2, _Hash, _RehashPolicy, _Traits>::
     _M_move_assign(_Hashtable&& __ht, true_type)
     {
-      this->_M_deallocate_nodes(_M_begin());
+      this->_M_deallocate_nodes(_M_before_begin._M_nxt);
       _M_deallocate_buckets();
       __hashtable_base::operator=(std::move(__ht));
       _M_rehash_policy = __ht._M_rehash_policy;
       if (!__ht._M_uses_single_bucket())
-	_M_buckets = __ht._M_buckets;
+	_M_buckets = std::move(__ht._M_buckets);
       else
 	{
-	  _M_buckets = &_M_single_bucket;
-	  _M_single_bucket = __ht._M_single_bucket;
+	  _M_buckets = __bucket_ptr_traits::pointer_to(_M_single_bucket);
+	  _M_single_bucket = std::move(__ht._M_single_bucket);
 	}
+
       _M_bucket_count = __ht._M_bucket_count;
-      _M_before_begin._M_nxt = __ht._M_before_begin._M_nxt;
+      _M_before_begin._M_nxt = std::move(__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());
 
       // Fix buckets containing the _M_before_begin pointers that can't be
       // moved.
-      if (_M_begin())
-	_M_buckets[_M_bucket_index(_M_begin())] = &_M_before_begin;
+      if (_M_before_begin._M_nxt)
+	_M_buckets[_M_bucket_index(_M_before_begin._M_nxt)] =
+	  __node_base_ptr_traits::pointer_to(_M_before_begin);
       __ht._M_reset();
     }
 
@@ -1290,23 +1300,24 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
       __map_base(__ht),
       __rehash_base(__ht),
       __hashtable_alloc(std::move(__ht._M_base_alloc())),
-      _M_buckets(__ht._M_buckets),
+      _M_buckets(std::move(__ht._M_buckets)),
       _M_bucket_count(__ht._M_bucket_count),
-      _M_before_begin(__ht._M_before_begin._M_nxt),
+      _M_before_begin(std::move(__ht._M_before_begin._M_nxt)),
       _M_element_count(__ht._M_element_count),
       _M_rehash_policy(__ht._M_rehash_policy)
     {
       // Update, if necessary, buckets if __ht is using its single bucket.
-      if (__ht._M_uses_single_bucket())
+      if (std::__to_address(_M_buckets) == &__ht._M_single_bucket)
 	{
-	  _M_buckets = &_M_single_bucket;
-	  _M_single_bucket = __ht._M_single_bucket;
+	  _M_buckets = __bucket_ptr_traits::pointer_to(_M_single_bucket);
+	  _M_single_bucket = std::move(__ht._M_single_bucket);
 	}
 
       // Update, if necessary, bucket pointing to before begin that hasn't
       // moved.
-      if (_M_begin())
-	_M_buckets[_M_bucket_index(_M_begin())] = &_M_before_begin;
+      if (_M_before_begin._M_nxt)
+	_M_buckets[_M_bucket_index(_M_before_begin._M_nxt)] =
+	  __node_base_ptr_traits::pointer_to(_M_before_begin);
 
       __ht._M_reset();
     }
@@ -1322,7 +1333,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
       __map_base(__ht),
       __rehash_base(__ht),
       __hashtable_alloc(__node_alloc_type(__a)),
-      _M_buckets(),
+      _M_buckets(nullptr),
       _M_bucket_count(__ht._M_bucket_count),
       _M_element_count(__ht._M_element_count),
       _M_rehash_policy(__ht._M_rehash_policy)
@@ -1351,17 +1362,18 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	{
 	  if (__ht._M_uses_single_bucket())
 	    {
-	      _M_buckets = &_M_single_bucket;
-	      _M_single_bucket = __ht._M_single_bucket;
+	      _M_buckets = __bucket_ptr_traits::pointer_to(_M_single_bucket);
+	      _M_single_bucket = std::move(__ht._M_single_bucket);
 	    }
 	  else
-	    _M_buckets = __ht._M_buckets;
+	    _M_buckets = std::move(__ht._M_buckets);
 
-	  _M_before_begin._M_nxt = __ht._M_before_begin._M_nxt;
+	  _M_before_begin._M_nxt = std::move(__ht._M_before_begin._M_nxt);
 	  // Update, if necessary, bucket pointing to before begin that hasn't
 	  // moved.
-	  if (_M_begin())
-	    _M_buckets[_M_bucket_index(_M_begin())] = &_M_before_begin;
+	  if (_M_before_begin._M_nxt)
+	    _M_buckets[_M_bucket_index(_M_before_begin._M_nxt)] =
+	      __node_base_ptr_traits::pointer_to(_M_before_begin);
 	  __ht._M_reset();
 	}
       else
@@ -1413,13 +1425,14 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	  if (!__x._M_uses_single_bucket())
 	    {
 	      _M_buckets = __x._M_buckets;
-	      __x._M_buckets = &__x._M_single_bucket;
+	      __x._M_buckets =
+		__bucket_ptr_traits::pointer_to(__x._M_single_bucket);
 	    }
 	}
       else if (__x._M_uses_single_bucket())
 	{
 	  __x._M_buckets = _M_buckets;
-	  _M_buckets = &_M_single_bucket;
+	  _M_buckets = __bucket_ptr_traits::pointer_to(_M_single_bucket);
 	}	
       else
 	std::swap(_M_buckets, __x._M_buckets);
@@ -1431,12 +1444,13 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 
       // Fix buckets containing the _M_before_begin pointers that can't be
       // swapped.
-      if (_M_begin())
-	_M_buckets[_M_bucket_index(_M_begin())] = &_M_before_begin;
+      if (_M_before_begin._M_nxt)
+	_M_buckets[_M_bucket_index(_M_before_begin._M_nxt)] =
+	  __node_base_ptr_traits::pointer_to(_M_before_begin);
 
-      if (__x._M_begin())
-	__x._M_buckets[__x._M_bucket_index(__x._M_begin())]
-	  = &__x._M_before_begin;
+      if (__x._M_before_begin._M_nxt)
+	__x._M_buckets[__x._M_bucket_index(__x._M_before_begin._M_nxt)]
+	  = __node_base_ptr_traits::pointer_to(__x._M_before_begin);
     }
 
   template<typename _Key, typename _Value,
@@ -1451,7 +1465,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
     {
       __hash_code __code = this->_M_hash_code(__k);
       std::size_t __bkt = _M_bucket_index(__k, __code);
-      __node_type* __p = _M_find_node(__bkt, __k, __code);
+      __node_pointer __p = _M_find_node(__bkt, __k, __code);
       return __p ? iterator(__p) : end();
     }
 
@@ -1467,7 +1481,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
     {
       __hash_code __code = this->_M_hash_code(__k);
       std::size_t __bkt = _M_bucket_index(__k, __code);
-      __node_type* __p = _M_find_node(__bkt, __k, __code);
+      __node_pointer __p = _M_find_node(__bkt, __k, __code);
       return __p ? const_iterator(__p) : end();
     }
 
@@ -1483,12 +1497,12 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
     {
       __hash_code __code = this->_M_hash_code(__k);
       std::size_t __bkt = _M_bucket_index(__k, __code);
-      __node_type* __p = _M_bucket_begin(__bkt);
+      __node_pointer __p = _M_bucket_begin(__bkt);
       if (!__p)
 	return 0;
 
       std::size_t __result = 0;
-      for (;; __p = __p->_M_next())
+      for (;; __p = __p->_M_nxt)
 	{
 	  if (this->_M_equals(__k, __code, __p))
 	    ++__result;
@@ -1497,7 +1511,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	    // found a non-equivalent value after an equivalent one it
 	    // means that we won't find any new equivalent value.
 	    break;
-	  if (!__p->_M_nxt || _M_bucket_index(__p->_M_next()) != __bkt)
+	  if (!__p->_M_nxt || _M_bucket_index(__p->_M_nxt) != __bkt)
 	    break;
 	}
       return __result;
@@ -1515,14 +1529,14 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
     {
       __hash_code __code = this->_M_hash_code(__k);
       std::size_t __bkt = _M_bucket_index(__k, __code);
-      __node_type* __p = _M_find_node(__bkt, __k, __code);
+      __node_pointer __p = _M_find_node(__bkt, __k, __code);
 
       if (__p)
 	{
-	  __node_type* __p1 = __p->_M_next();
+	  __node_pointer __p1 = __p->_M_nxt;
 	  while (__p1 && _M_bucket_index(__p1) == __bkt
 		 && this->_M_equals(__k, __code, __p1))
-	    __p1 = __p1->_M_next();
+	    __p1 = __p1->_M_nxt;
 
 	  return std::make_pair(iterator(__p), iterator(__p1));
 	}
@@ -1542,14 +1556,14 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
     {
       __hash_code __code = this->_M_hash_code(__k);
       std::size_t __bkt = _M_bucket_index(__k, __code);
-      __node_type* __p = _M_find_node(__bkt, __k, __code);
+      __node_pointer __p = _M_find_node(__bkt, __k, __code);
 
       if (__p)
 	{
-	  __node_type* __p1 = __p->_M_next();
+	  __node_pointer __p1 = __p->_M_nxt;
 	  while (__p1 && _M_bucket_index(__p1) == __bkt
 		 && this->_M_equals(__k, __code, __p1))
-	    __p1 = __p1->_M_next();
+	    __p1 = __p1->_M_nxt;
 
 	  return std::make_pair(const_iterator(__p), const_iterator(__p1));
 	}
@@ -1568,19 +1582,18 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	       _H1, _H2, _Hash, _RehashPolicy, _Traits>::
     _M_find_before_node(size_type __bkt, const key_type& __k,
 			__hash_code __code) const
-    -> __node_base*
+    -> __bucket_type
     {
-      __node_base* __prev_p = _M_buckets[__bkt];
+      __bucket_type __prev_p = _M_buckets[__bkt];
       if (!__prev_p)
 	return nullptr;
 
-      for (__node_type* __p = static_cast<__node_type*>(__prev_p->_M_nxt);;
-	   __p = __p->_M_next())
+      for (__node_pointer __p = __prev_p->_M_nxt;; __p = __p->_M_nxt)
 	{
 	  if (this->_M_equals(__k, __code, __p))
 	    return __prev_p;
 
-	  if (!__p->_M_nxt || _M_bucket_index(__p->_M_next()) != __bkt)
+	  if (!__p->_M_nxt || _M_bucket_index(__p->_M_nxt) != __bkt)
 	    break;
 	  __prev_p = __p;
 	}
@@ -1594,7 +1607,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
     void
     _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
 	       _H1, _H2, _Hash, _RehashPolicy, _Traits>::
-    _M_insert_bucket_begin(size_type __bkt, __node_type* __node)
+    _M_insert_bucket_begin(size_type __bkt, __node_pointer __node)
     {
       if (_M_buckets[__bkt])
 	{
@@ -1613,8 +1626,9 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	  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;
+	    _M_buckets[_M_bucket_index(__node->_M_nxt)] = __node;
+	  _M_buckets[__bkt] =
+	    __node_base_ptr_traits::pointer_to(_M_before_begin);
 	}
     }
 
@@ -1625,7 +1639,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
     void
     _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
 	       _H1, _H2, _Hash, _RehashPolicy, _Traits>::
-    _M_remove_bucket_begin(size_type __bkt, __node_type* __next,
+    _M_remove_bucket_begin(size_type __bkt, __node_pointer __next,
 			   size_type __next_bkt)
     {
       if (!__next || __next_bkt != __bkt)
@@ -1636,7 +1650,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	    _M_buckets[__next_bkt] = _M_buckets[__bkt];
 
 	  // Second update before begin node if necessary
-	  if (&_M_before_begin == _M_buckets[__bkt])
+	  if (&_M_before_begin == std::__to_address(_M_buckets[__bkt]))
 	    _M_before_begin._M_nxt = __next;
 	  _M_buckets[__bkt] = nullptr;
 	}
@@ -1649,10 +1663,10 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
     auto
     _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
 	       _H1, _H2, _Hash, _RehashPolicy, _Traits>::
-    _M_get_previous_node(size_type __bkt, __node_base* __n)
-    -> __node_base*
+    _M_get_previous_node(size_type __bkt, const __node_pointer& __n)
+    -> __bucket_type
     {
-      __node_base* __prev_n = _M_buckets[__bkt];
+      __bucket_type __prev_n = _M_buckets[__bkt];
       while (__prev_n->_M_nxt != __n)
 	__prev_n = __prev_n->_M_nxt;
       return __prev_n;
@@ -1674,7 +1688,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	const key_type& __k = this->_M_extract()(__node._M_node->_M_v());
 	__hash_code __code = this->_M_hash_code(__k);
 	size_type __bkt = _M_bucket_index(__k, __code);
-	if (__node_type* __p = _M_find_node(__bkt, __k, __code))
+	if (__node_pointer __p = _M_find_node(__bkt, __k, __code))
 	  // There is already an equivalent node, no insertion
 	  return std::make_pair(iterator(__p), false);
 
@@ -1714,7 +1728,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
     _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
 	       _H1, _H2, _Hash, _RehashPolicy, _Traits>::
     _M_insert_unique_node(const key_type& __k, size_type __bkt,
-			  __hash_code __code, __node_type* __node,
+			  __hash_code __code, __node_pointer __node,
 			  size_type __n_elt)
     -> iterator
     {
@@ -1744,8 +1758,8 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
     auto
     _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
 	       _H1, _H2, _Hash, _RehashPolicy, _Traits>::
-    _M_insert_multi_node(__node_type* __hint, const key_type& __k,
-			 __hash_code __code, __node_type* __node)
+    _M_insert_multi_node(__node_pointer __hint, const key_type& __k,
+			 __hash_code __code, __node_pointer __node)
     -> iterator
     {
       const __rehash_state& __saved_state = _M_rehash_policy._M_state();
@@ -1760,7 +1774,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 
       // Find the node before an equivalent one or use hint if it exists and
       // if it is equivalent.
-      __node_base* __prev
+      __bucket_type __prev
 	= __builtin_expect(__hint != nullptr, false)
 	  && this->_M_equals(__k, __code, __hint)
 	    ? __hint
@@ -1774,9 +1788,9 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	    // 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()))
+		&& !this->_M_equals(__k, __code, __node->_M_nxt))
 	      {
-		size_type __next_bkt = _M_bucket_index(__node->_M_next());
+		size_type __next_bkt = _M_bucket_index(__node->_M_nxt);
 		if (__next_bkt != __bkt)
 		  _M_buckets[__next_bkt] = __node;
 	      }
@@ -1807,7 +1821,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	__hash_code __code = this->_M_hash_code(__k);
 	size_type __bkt = _M_bucket_index(__k, __code);
 
-	if (__node_type* __node = _M_find_node(__bkt, __k, __code))
+	if (__node_pointer __node = _M_find_node(__bkt, __k, __code))
 	  return { iterator(__node), false };
 
 	_Scoped_node __node{ __node_gen(std::forward<_Arg>(__v)), this };
@@ -1853,14 +1867,13 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
     erase(const_iterator __it)
     -> iterator
     {
-      __node_type* __n = __it._M_cur;
-      std::size_t __bkt = _M_bucket_index(__n);
+      std::size_t __bkt = _M_bucket_index(__it._M_cur);
 
       // Look for previous node to unlink it from the erased one, this
       // is why we need buckets to contain the before begin to make
       // this search fast.
-      __node_base* __prev_n = _M_get_previous_node(__bkt, __n);
-      return _M_erase(__bkt, __prev_n, __n);
+      __bucket_type __prev_n = _M_get_previous_node(__bkt, __it._M_cur);
+      return _M_erase(__bkt, __prev_n, __it._M_cur);
     }
 
   template<typename _Key, typename _Value,
@@ -1870,21 +1883,21 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
     auto
     _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
 	       _H1, _H2, _Hash, _RehashPolicy, _Traits>::
-    _M_erase(size_type __bkt, __node_base* __prev_n, __node_type* __n)
+    _M_erase(size_type __bkt, __bucket_type __prev_n, __node_pointer __n)
     -> iterator
     {
       if (__prev_n == _M_buckets[__bkt])
-	_M_remove_bucket_begin(__bkt, __n->_M_next(),
-	   __n->_M_nxt ? _M_bucket_index(__n->_M_next()) : 0);
+	_M_remove_bucket_begin(__bkt, __n->_M_nxt,
+	   __n->_M_nxt ? _M_bucket_index(__n->_M_nxt) : 0);
       else if (__n->_M_nxt)
 	{
-	  size_type __next_bkt = _M_bucket_index(__n->_M_next());
+	  size_type __next_bkt = _M_bucket_index(__n->_M_nxt);
 	  if (__next_bkt != __bkt)
 	    _M_buckets[__next_bkt] = __prev_n;
 	}
 
       __prev_n->_M_nxt = __n->_M_nxt;
-      iterator __result(__n->_M_next());
+      iterator __result(__n->_M_nxt);
       this->_M_deallocate_node(__n);
       --_M_element_count;
 
@@ -1905,13 +1918,12 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
       std::size_t __bkt = _M_bucket_index(__k, __code);
 
       // Look for the node before the first matching node.
-      __node_base* __prev_n = _M_find_before_node(__bkt, __k, __code);
+      __bucket_type __prev_n = _M_find_before_node(__bkt, __k, __code);
       if (!__prev_n)
 	return 0;
 
       // We found a matching node, erase it.
-      __node_type* __n = static_cast<__node_type*>(__prev_n->_M_nxt);
-      _M_erase(__bkt, __prev_n, __n);
+      _M_erase(__bkt, __prev_n, __prev_n->_M_nxt);
       return 1;
     }
 
@@ -1929,7 +1941,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
       std::size_t __bkt = _M_bucket_index(__k, __code);
 
       // Look for the node before the first matching node.
-      __node_base* __prev_n = _M_find_before_node(__bkt, __k, __code);
+      __bucket_type __prev_n = _M_find_before_node(__bkt, __k, __code);
       if (!__prev_n)
 	return 0;
 
@@ -1939,12 +1951,12 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
       // We use one loop to find all matching nodes and another to deallocate
       // them so that the key stays valid during the first loop. It might be
       // invalidated indirectly when destroying nodes.
-      __node_type* __n = static_cast<__node_type*>(__prev_n->_M_nxt);
-      __node_type* __n_last = __n;
+      __node_pointer __n = __prev_n->_M_nxt;
+      __node_pointer __n_last = __n;
       std::size_t __n_last_bkt = __bkt;
       do
 	{
-	  __n_last = __n_last->_M_next();
+	  __n_last = __n_last->_M_nxt;
 	  if (!__n_last)
 	    break;
 	  __n_last_bkt = _M_bucket_index(__n_last);
@@ -1955,7 +1967,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
       size_type __result = 0;
       do
 	{
-	  __node_type* __p = __n->_M_next();
+	  __node_pointer __p = __n->_M_nxt;
 	  this->_M_deallocate_node(__n);
 	  __n = __p;
 	  ++__result;
@@ -1981,22 +1993,22 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
     erase(const_iterator __first, const_iterator __last)
     -> iterator
     {
-      __node_type* __n = __first._M_cur;
-      __node_type* __last_n = __last._M_cur;
+      __node_pointer __n = __first._M_cur;
+      __node_pointer __last_n = __last._M_cur;
       if (__n == __last_n)
 	return iterator(__n);
 
       std::size_t __bkt = _M_bucket_index(__n);
 
-      __node_base* __prev_n = _M_get_previous_node(__bkt, __n);
+      __bucket_type __prev_n = _M_get_previous_node(__bkt, __n);
       bool __is_bucket_begin = __n == _M_bucket_begin(__bkt);
       std::size_t __n_bkt = __bkt;
       for (;;)
 	{
 	  do
 	    {
-	      __node_type* __tmp = __n;
-	      __n = __n->_M_next();
+	      __node_pointer __tmp = __n;
+	      __n = __n->_M_nxt;
 	      this->_M_deallocate_node(__tmp);
 	      --_M_element_count;
 	      if (!__n)
@@ -2027,8 +2039,8 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	       _H1, _H2, _Hash, _RehashPolicy, _Traits>::
     clear() noexcept
     {
-      this->_M_deallocate_nodes(_M_begin());
-      __builtin_memset(_M_buckets, 0, _M_bucket_count * sizeof(__bucket_type));
+      this->_M_deallocate_nodes(_M_before_begin._M_nxt);
+      std::fill_n(_M_buckets, _M_bucket_count, nullptr);
       _M_element_count = 0;
       _M_before_begin._M_nxt = nullptr;
     }
@@ -2088,20 +2100,22 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	       _H1, _H2, _Hash, _RehashPolicy, _Traits>::
     _M_rehash_aux(size_type __bkt_count, true_type)
     {
-      __bucket_type* __new_buckets = _M_allocate_buckets(__bkt_count);
-      __node_type* __p = _M_begin();
+      __bucket_pointer __new_buckets = _M_allocate_buckets(__bkt_count);
+      auto __before_begin_ptr =
+	__node_base_ptr_traits::pointer_to(_M_before_begin);
+      __node_pointer __p = _M_before_begin._M_nxt;
       _M_before_begin._M_nxt = nullptr;
       std::size_t __bbegin_bkt = 0;
       while (__p)
 	{
-	  __node_type* __next = __p->_M_next();
+	  __node_pointer __next = __p->_M_nxt;
 	  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;
+	      __new_buckets[__bkt] = __before_begin_ptr;
 	      if (__p->_M_nxt)
 		__new_buckets[__bbegin_bkt] = __p;
 	      __bbegin_bkt = __bkt;
@@ -2132,16 +2146,18 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
     {
       __bucket_type* __new_buckets = _M_allocate_buckets(__bkt_count);
 
-      __node_type* __p = _M_begin();
+      auto __before_begin_ptr =
+	__node_base_ptr_traits::pointer_to(_M_before_begin);
+      __node_pointer __p = _M_before_begin._M_nxt;
       _M_before_begin._M_nxt = nullptr;
       std::size_t __bbegin_bkt = 0;
       std::size_t __prev_bkt = 0;
-      __node_type* __prev_p = nullptr;
+      __node_pointer __prev_p{};
       bool __check_bucket = false;
 
       while (__p)
 	{
-	  __node_type* __next = __p->_M_next();
+	  __node_pointer __next = __p->_M_nxt;
 	  std::size_t __bkt
 	    = __hash_code_base::_M_bucket_index(__p, __bkt_count);
 
@@ -2169,7 +2185,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 		  if (__prev_p->_M_nxt)
 		    {
 		      std::size_t __next_bkt
-			= __hash_code_base::_M_bucket_index(__prev_p->_M_next(),
+			= __hash_code_base::_M_bucket_index(__prev_p->_M_nxt,
 							    __bkt_count);
 		      if (__next_bkt != __prev_bkt)
 			__new_buckets[__next_bkt] = __prev_p;
@@ -2181,7 +2197,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 		{
 		  __p->_M_nxt = _M_before_begin._M_nxt;
 		  _M_before_begin._M_nxt = __p;
-		  __new_buckets[__bkt] = &_M_before_begin;
+		  __new_buckets[__bkt] = __before_begin_ptr;
 		  if (__p->_M_nxt)
 		    __new_buckets[__bbegin_bkt] = __p;
 		  __bbegin_bkt = __bkt;
@@ -2200,7 +2216,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
       if (__check_bucket && __prev_p->_M_nxt)
 	{
 	  std::size_t __next_bkt
-	    = __hash_code_base::_M_bucket_index(__prev_p->_M_next(),
+	    = __hash_code_base::_M_bucket_index(__prev_p->_M_nxt,
 						__bkt_count);
 	  if (__next_bkt != __prev_bkt)
 	    __new_buckets[__next_bkt] = __prev_p;
diff --git a/libstdc++-v3/include/bits/hashtable_policy.h b/libstdc++-v3/include/bits/hashtable_policy.h
index ef120134914..35de9eaf2b0 100644
--- a/libstdc++-v3/include/bits/hashtable_policy.h
+++ b/libstdc++-v3/include/bits/hashtable_policy.h
@@ -52,7 +52,7 @@ namespace __detail
    *  @ingroup unordered_associative_containers
    *  @{
    */
-  template<typename _Key, typename _Value,
+  template<typename _Key, typename _Value, typename _Alloc,
 	   typename _ExtractKey, typename _Equal,
 	   typename _H1, typename _H2, typename _Hash, typename _Traits>
     struct _Hashtable_base;
@@ -107,24 +107,24 @@ namespace __detail
       using __hashtable_alloc = _Hashtable_alloc<__node_alloc_type>;
       using __node_alloc_traits =
 	typename __hashtable_alloc::__node_alloc_traits;
-      using __node_type = typename __hashtable_alloc::__node_type;
+      using __node_pointer = typename __hashtable_alloc::__node_pointer;
 
     public:
-      _ReuseOrAllocNode(__node_type* __nodes, __hashtable_alloc& __h)
-      : _M_nodes(__nodes), _M_h(__h) { }
+      _ReuseOrAllocNode(__node_pointer&& __nodes, __hashtable_alloc& __h)
+      : _M_nodes(std::move(__nodes)), _M_h(__h) { }
       _ReuseOrAllocNode(const _ReuseOrAllocNode&) = delete;
 
       ~_ReuseOrAllocNode()
       { _M_h._M_deallocate_nodes(_M_nodes); }
 
       template<typename _Arg>
-	__node_type*
+	__node_pointer
 	operator()(_Arg&& __arg) const
 	{
 	  if (_M_nodes)
 	    {
-	      __node_type* __node = _M_nodes;
-	      _M_nodes = _M_nodes->_M_next();
+	      __node_pointer __node = _M_nodes;
+	      _M_nodes = _M_nodes->_M_nxt;
 	      __node->_M_nxt = nullptr;
 	      auto& __a = _M_h._M_node_allocator();
 	      __node_alloc_traits::destroy(__a, __node->_M_valptr());
@@ -144,7 +144,7 @@ namespace __detail
 	}
 
     private:
-      mutable __node_type* _M_nodes;
+      mutable __node_pointer _M_nodes;
       __hashtable_alloc& _M_h;
     };
 
@@ -155,14 +155,14 @@ namespace __detail
     {
     private:
       using __hashtable_alloc = _Hashtable_alloc<_NodeAlloc>;
-      using __node_type = typename __hashtable_alloc::__node_type;
+      using __node_pointer = typename __hashtable_alloc::__node_pointer;
 
     public:
       _AllocNode(__hashtable_alloc& __h)
       : _M_h(__h) { }
 
       template<typename _Arg>
-	__node_type*
+	__node_pointer
 	operator()(_Arg&& __arg) const
 	{ return _M_h._M_allocate_node(std::forward<_Arg>(__arg)); }
 
@@ -211,22 +211,25 @@ namespace __detail
    *  nodes also store a hash code. In some cases (e.g. strings) this
    *  may be a performance win.
    */
-  struct _Hash_node_base
-  {
-    _Hash_node_base* _M_nxt;
+  template<typename _NodePtr>
+    struct _Hash_node_base
+    {
+      _NodePtr _M_nxt;
 
-    _Hash_node_base() noexcept : _M_nxt() { }
+      _Hash_node_base() noexcept : _M_nxt(nullptr) { }
 
-    _Hash_node_base(_Hash_node_base* __next) noexcept : _M_nxt(__next) { }
-  };
+      template<typename _Ptr>
+	_Hash_node_base(_Ptr&& __next) noexcept
+	: _M_nxt(std::forward<_Ptr>(__next)) { }
+    };
 
   /**
    *  struct _Hash_node_value_base
    *
    *  Node type with the value to store.
    */
-  template<typename _Value>
-    struct _Hash_node_value_base : _Hash_node_base
+  template<typename _NodePtr, typename _Value>
+    struct _Hash_node_value_base : _Hash_node_base<_NodePtr>
     {
       typedef _Value value_type;
 
@@ -252,7 +255,7 @@ namespace __detail
   /**
    *  Primary template struct _Hash_node.
    */
-  template<typename _Value, bool _Cache_hash_code>
+  template<typename _Ptr, typename _Value, bool _Cache_hash_code>
     struct _Hash_node;
 
   /**
@@ -260,14 +263,14 @@ namespace __detail
    *
    *  Base class is __detail::_Hash_node_value_base.
    */
-  template<typename _Value>
-    struct _Hash_node<_Value, true> : _Hash_node_value_base<_Value>
+  template<typename _Ptr, typename _Value>
+    struct _Hash_node<_Ptr, _Value, true>
+    : _Hash_node_value_base<__ptr_rebind<_Ptr, _Hash_node<_Ptr, _Value, true>>,
+			    _Value>
     {
-      std::size_t  _M_hash_code;
+      using __node_pointer = __ptr_rebind<_Ptr, _Hash_node>;
 
-      _Hash_node*
-      _M_next() const noexcept
-      { return static_cast<_Hash_node*>(this->_M_nxt); }
+      std::size_t  _M_hash_code;
     };
 
   /**
@@ -275,69 +278,66 @@ namespace __detail
    *
    *  Base class is __detail::_Hash_node_value_base.
    */
-  template<typename _Value>
-    struct _Hash_node<_Value, false> : _Hash_node_value_base<_Value>
-    {
-      _Hash_node*
-      _M_next() const noexcept
-      { return static_cast<_Hash_node*>(this->_M_nxt); }
-    };
+  template<typename _Ptr, typename _Value>
+    struct _Hash_node<_Ptr, _Value, false>
+    : _Hash_node_value_base<__ptr_rebind<_Ptr, _Hash_node<_Ptr, _Value, false>>,
+			    _Value>
+    { using __node_pointer = __ptr_rebind<_Ptr, _Hash_node>; };
 
   /// Base class for node iterators.
-  template<typename _Value, bool _Cache_hash_code>
+  template<typename _NodePtr>
     struct _Node_iterator_base
     {
-      using __node_type = _Hash_node<_Value, _Cache_hash_code>;
+      using __node_type = typename std::pointer_traits<_NodePtr>::element_type;
 
-      __node_type*  _M_cur;
+      _NodePtr _M_cur;
 
-      _Node_iterator_base(__node_type* __p) noexcept
+      _Node_iterator_base(_NodePtr __p) noexcept
       : _M_cur(__p) { }
+      _Node_iterator_base() noexcept
+      : _Node_iterator_base(nullptr) { }
 
       void
       _M_incr() noexcept
-      { _M_cur = _M_cur->_M_next(); }
-    };
+      { _M_cur = _M_cur->_M_nxt; }
 
-  template<typename _Value, bool _Cache_hash_code>
-    inline bool
-    operator==(const _Node_iterator_base<_Value, _Cache_hash_code>& __x,
-	       const _Node_iterator_base<_Value, _Cache_hash_code >& __y)
-    noexcept
-    { return __x._M_cur == __y._M_cur; }
+      friend inline bool
+      operator==(const _Node_iterator_base& __x, const _Node_iterator_base& __y)
+      noexcept
+      { return __x._M_cur == __y._M_cur; }
 
-  template<typename _Value, bool _Cache_hash_code>
-    inline bool
-    operator!=(const _Node_iterator_base<_Value, _Cache_hash_code>& __x,
-	       const _Node_iterator_base<_Value, _Cache_hash_code>& __y)
-    noexcept
-    { return __x._M_cur != __y._M_cur; }
+      friend inline bool
+      operator!=(const _Node_iterator_base& __x, const _Node_iterator_base& __y)
+      noexcept
+      { return __x._M_cur != __y._M_cur; }
+    };
 
   /// Node iterators, used to iterate through all the hashtable.
-  template<typename _Value, bool __constant_iterators, bool __cache>
+  template<typename _NodePtr, bool __constant_iterators>
     struct _Node_iterator
-    : public _Node_iterator_base<_Value, __cache>
+    : public _Node_iterator_base<_NodePtr>
     {
     private:
-      using __base_type = _Node_iterator_base<_Value, __cache>;
+      using __base_type = _Node_iterator_base<_NodePtr>;
       using __node_type = typename __base_type::__node_type;
 
     public:
-      typedef _Value					value_type;
-      typedef std::ptrdiff_t				difference_type;
-      typedef std::forward_iterator_tag			iterator_category;
+      typedef typename __node_type::value_type	value_type;
+      typedef typename std::pointer_traits<_NodePtr>::difference_type
+						difference_type;
+      typedef std::forward_iterator_tag		iterator_category;
 
       using pointer = typename std::conditional<__constant_iterators,
-						const _Value*, _Value*>::type;
+				  const value_type*, value_type*>::type;
 
       using reference = typename std::conditional<__constant_iterators,
-						  const _Value&, _Value&>::type;
+				  const value_type&, value_type&>::type;
 
       _Node_iterator() noexcept
-      : __base_type(0) { }
+      : __base_type(nullptr) { }
 
       explicit
-      _Node_iterator(__node_type* __p) noexcept
+      _Node_iterator(_NodePtr __p) noexcept
       : __base_type(__p) { }
 
       reference
@@ -365,31 +365,32 @@ namespace __detail
     };
 
   /// Node const_iterators, used to iterate through all the hashtable.
-  template<typename _Value, bool __constant_iterators, bool __cache>
+  template<typename _NodePtr, bool __constant_iterators>
     struct _Node_const_iterator
-    : public _Node_iterator_base<_Value, __cache>
+    : public _Node_iterator_base<_NodePtr>
     {
     private:
-      using __base_type = _Node_iterator_base<_Value, __cache>;
+      using __base_type = _Node_iterator_base<_NodePtr>;
       using __node_type = typename __base_type::__node_type;
 
     public:
-      typedef _Value					value_type;
-      typedef std::ptrdiff_t				difference_type;
-      typedef std::forward_iterator_tag			iterator_category;
+      typedef typename __node_type::value_type	value_type;
+      typedef typename std::pointer_traits<_NodePtr>::difference_type
+						difference_type;
+      typedef std::forward_iterator_tag		iterator_category;
 
-      typedef const _Value*				pointer;
-      typedef const _Value&				reference;
+      typedef const value_type*			pointer;
+      typedef const value_type&			reference;
 
       _Node_const_iterator() noexcept
-      : __base_type(0) { }
+      : __base_type(nullptr) { }
 
       explicit
-      _Node_const_iterator(__node_type* __p) noexcept
+      _Node_const_iterator(_NodePtr __p) noexcept
       : __base_type(__p) { }
 
-      _Node_const_iterator(const _Node_iterator<_Value, __constant_iterators,
-			   __cache>& __x) noexcept
+      _Node_const_iterator(const _Node_iterator<_NodePtr,
+			   __constant_iterators>& __x) noexcept
       : __base_type(__x._M_cur) { }
 
       reference
@@ -662,17 +663,17 @@ namespace __detail
 		     _H1, _H2, _Hash, _RehashPolicy, _Traits, true>
     {
     private:
-      using __hashtable_base = __detail::_Hashtable_base<_Key, _Pair,
+      using __hashtable_base = __detail::_Hashtable_base<_Key, _Pair, _Alloc,
 							 _Select1st,
 							_Equal, _H1, _H2, _Hash,
-							  _Traits>;
+							 _Traits>;
 
       using __hashtable = _Hashtable<_Key, _Pair, _Alloc,
 				     _Select1st, _Equal,
 				     _H1, _H2, _Hash, _RehashPolicy, _Traits>;
 
       using __hash_code = typename __hashtable_base::__hash_code;
-      using __node_type = typename __hashtable_base::__node_type;
+      using __node_pointer = typename __hashtable_base::__node_pointer;
 
     public:
       using key_type = typename __hashtable_base::key_type;
@@ -706,7 +707,7 @@ namespace __detail
       __hashtable* __h = static_cast<__hashtable*>(this);
       __hash_code __code = __h->_M_hash_code(__k);
       std::size_t __bkt = __h->_M_bucket_index(__k, __code);
-      if (__node_type* __node = __h->_M_find_node(__bkt, __k, __code))
+      if (__node_pointer __node = __h->_M_find_node(__bkt, __k, __code))
 	return __node->_M_v().second;
 
       typename __hashtable::_Scoped_node __node {
@@ -733,7 +734,7 @@ namespace __detail
       __hashtable* __h = static_cast<__hashtable*>(this);
       __hash_code __code = __h->_M_hash_code(__k);
       std::size_t __bkt = __h->_M_bucket_index(__k, __code);
-      if (__node_type* __node = __h->_M_find_node(__bkt, __k, __code))
+      if (__node_pointer __node = __h->_M_find_node(__bkt, __k, __code))
 	return __node->_M_v().second;
 
       typename __hashtable::_Scoped_node __node {
@@ -760,7 +761,7 @@ namespace __detail
       __hashtable* __h = static_cast<__hashtable*>(this);
       __hash_code __code = __h->_M_hash_code(__k);
       std::size_t __bkt = __h->_M_bucket_index(__k, __code);
-      __node_type* __p = __h->_M_find_node(__bkt, __k, __code);
+      __node_pointer __p = __h->_M_find_node(__bkt, __k, __code);
 
       if (!__p)
 	__throw_out_of_range(__N("_Map_base::at"));
@@ -779,7 +780,7 @@ namespace __detail
       const __hashtable* __h = static_cast<const __hashtable*>(this);
       __hash_code __code = __h->_M_hash_code(__k);
       std::size_t __bkt = __h->_M_bucket_index(__k, __code);
-      __node_type* __p = __h->_M_find_node(__bkt, __k, __code);
+      __node_pointer __p = __h->_M_find_node(__bkt, __k, __code);
 
       if (!__p)
 	__throw_out_of_range(__N("_Map_base::at"));
@@ -802,7 +803,8 @@ namespace __detail
 				     _Equal, _H1, _H2, _Hash,
 				     _RehashPolicy, _Traits>;
 
-      using __hashtable_base = _Hashtable_base<_Key, _Value, _ExtractKey,
+      using __hashtable_base = _Hashtable_base<_Key, _Value, _Alloc,
+					       _ExtractKey,
 					       _Equal, _H1, _H2, _Hash,
 					       _Traits>;
 
@@ -813,7 +815,7 @@ namespace __detail
 
       using __unique_keys = typename __hashtable_base::__unique_keys;
       using __ireturn_type = typename __hashtable_base::__ireturn_type;
-      using __node_type = _Hash_node<_Value, _Traits::__hash_cached::value>;
+      using __node_type = typename __hashtable_base::__node_type;
       using __node_alloc_type = __alloc_rebind<_Alloc, __node_type>;
       using __node_gen_type = _AllocNode<__node_alloc_type>;
 
@@ -948,7 +950,8 @@ namespace __detail
 					_Equal, _H1, _H2, _Hash,
 					_RehashPolicy, _Traits>;
 
-      using __hashtable_base = _Hashtable_base<_Key, _Value, _ExtractKey,
+      using __hashtable_base = _Hashtable_base<_Key, _Value, _Alloc,
+					       _ExtractKey,
 					       _Equal, _H1, _H2, _Hash,
 					       _Traits>;
 
@@ -1144,9 +1147,9 @@ namespace __detail
    *  Base class for local iterators, used to iterate within a bucket
    *  but not between buckets.
    */
-  template<typename _Key, typename _Value, typename _ExtractKey,
-	   typename _H1, typename _H2, typename _Hash,
-	   bool __cache_hash_code>
+  template<typename _Key, typename _Value, typename _Alloc,
+	   typename _ExtractKey, typename _H1, typename _H2, typename _Hash,
+	   typename _NodePtr, bool __cache_hash_code>
     struct _Local_iterator_base;
 
   /**
@@ -1169,26 +1172,30 @@ namespace __detail
    *
    *  Primary template is unused except as a hook for specializations.
    */
-  template<typename _Key, typename _Value, typename _ExtractKey,
+  template<typename _Key, typename _Value, typename _Alloc,
+	   typename _ExtractKey,
 	   typename _H1, typename _H2, typename _Hash,
 	   bool __cache_hash_code>
     struct _Hash_code_base;
 
   /// Specialization: ranged hash function, no caching hash codes.  H1
   /// and H2 are provided but ignored.  We define a dummy hash code type.
-  template<typename _Key, typename _Value, typename _ExtractKey,
-	   typename _H1, typename _H2, typename _Hash>
-    struct _Hash_code_base<_Key, _Value, _ExtractKey, _H1, _H2, _Hash, false>
+  template<typename _Key, typename _Value, typename _Alloc,
+	   typename _ExtractKey, typename _H1, typename _H2, typename _Hash>
+    struct _Hash_code_base<_Key, _Value, _Alloc, _ExtractKey, _H1, _H2,
+			   _Hash, false>
     : private _Hashtable_ebo_helper<0, _ExtractKey>,
       private _Hashtable_ebo_helper<1, _Hash>
     {
     private:
       using __ebo_extract_key = _Hashtable_ebo_helper<0, _ExtractKey>;
       using __ebo_hash = _Hashtable_ebo_helper<1, _Hash>;
+      using __pointer = typename std::allocator_traits<_Alloc>::pointer;
 
     protected:
       typedef void* 					__hash_code;
-      typedef _Hash_node<_Value, false>			__node_type;
+      typedef _Hash_node<__pointer, _Value, false>	__node_type;
+      using __node_pointer = typename __node_type::__node_pointer;
 
       // We need the default constructor for the local iterators and _Hashtable
       // default constructor.
@@ -1208,17 +1215,17 @@ namespace __detail
       { return _M_ranged_hash()(__k, __bkt_count); }
 
       std::size_t
-      _M_bucket_index(const __node_type* __p, std::size_t __bkt_count) const
+      _M_bucket_index(const __node_pointer& __p, std::size_t __bkt_count) const
 	noexcept( noexcept(declval<const _Hash&>()(declval<const _Key&>(),
 						   (std::size_t)0)) )
       { return _M_ranged_hash()(_M_extract()(__p->_M_v()), __bkt_count); }
 
       void
-      _M_store_code(__node_type*, __hash_code) const
+      _M_store_code(const __node_pointer&, __hash_code) const
       { }
 
       void
-      _M_copy_code(__node_type*, const __node_type*) const
+      _M_copy_code(const __node_pointer&, const __node_pointer&) const
       { }
 
       void
@@ -1242,16 +1249,17 @@ namespace __detail
   /// Specialization: ranged hash function, cache hash codes.  This
   /// combination is meaningless, so we provide only a declaration
   /// and no definition.
-  template<typename _Key, typename _Value, typename _ExtractKey,
-	   typename _H1, typename _H2, typename _Hash>
-    struct _Hash_code_base<_Key, _Value, _ExtractKey, _H1, _H2, _Hash, true>;
+  template<typename _Key, typename _Value, typename _Alloc,
+	   typename _ExtractKey, typename _H1, typename _H2, typename _Hash>
+    struct _Hash_code_base<_Key, _Value, _Alloc, _ExtractKey, _H1, _H2,
+			   _Hash, true>;
 
   /// Specialization: hash function and range-hashing function, no
   /// caching of hash codes.
   /// Provides typedef and accessor required by C++ 11.
-  template<typename _Key, typename _Value, typename _ExtractKey,
-	   typename _H1, typename _H2>
-    struct _Hash_code_base<_Key, _Value, _ExtractKey, _H1, _H2,
+  template<typename _Key, typename _Value, typename _Alloc,
+	   typename _ExtractKey, typename _H1, typename _H2>
+    struct _Hash_code_base<_Key, _Value, _Alloc, _ExtractKey, _H1, _H2,
 			   _Default_ranged_hash, false>
     : private _Hashtable_ebo_helper<0, _ExtractKey>,
       private _Hashtable_ebo_helper<1, _H1>,
@@ -1261,10 +1269,7 @@ namespace __detail
       using __ebo_extract_key = _Hashtable_ebo_helper<0, _ExtractKey>;
       using __ebo_h1 = _Hashtable_ebo_helper<1, _H1>;
       using __ebo_h2 = _Hashtable_ebo_helper<2, _H2>;
-
-      // Gives the local iterator implementation access to _M_bucket_index().
-      friend struct _Local_iterator_base<_Key, _Value, _ExtractKey, _H1, _H2,
-					 _Default_ranged_hash, false>;
+      using __pointer = typename std::allocator_traits<_Alloc>::pointer;
 
     public:
       typedef _H1 					hasher;
@@ -1275,7 +1280,13 @@ namespace __detail
 
     protected:
       typedef std::size_t 				__hash_code;
-      typedef _Hash_node<_Value, false>			__node_type;
+      typedef _Hash_node<__pointer, _Value, false>	__node_type;
+      using __node_pointer = typename __node_type::__node_pointer;
+
+      // Gives the local iterator implementation access to _M_bucket_index().
+      friend struct _Local_iterator_base<_Key, _Value, _Alloc, _ExtractKey,
+					 _H1, _H2, _Default_ranged_hash,
+					 __node_pointer, false>;
 
       // We need the default constructor for the local iterators and _Hashtable
       // default constructor.
@@ -1300,18 +1311,18 @@ namespace __detail
       { return _M_h2()(__c, __bkt_count); }
 
       std::size_t
-      _M_bucket_index(const __node_type* __p, std::size_t __bkt_count) const
+      _M_bucket_index(const __node_pointer& __p, std::size_t __bkt_count) const
 	noexcept( noexcept(declval<const _H1&>()(declval<const _Key&>()))
 		  && noexcept(declval<const _H2&>()((__hash_code)0,
 						    (std::size_t)0)) )
       { return _M_h2()(_M_h1()(_M_extract()(__p->_M_v())), __bkt_count); }
 
       void
-      _M_store_code(__node_type*, __hash_code) const
+      _M_store_code(const __node_pointer&, __hash_code) const
       { }
 
       void
-      _M_copy_code(__node_type*, const __node_type*) const
+      _M_copy_code(const __node_pointer&, const __node_pointer&) const
       { }
 
       void
@@ -1336,22 +1347,19 @@ namespace __detail
   /// Specialization: hash function and range-hashing function,
   /// caching hash codes.  H is provided but ignored.  Provides
   /// typedef and accessor required by C++ 11.
-  template<typename _Key, typename _Value, typename _ExtractKey,
-	   typename _H1, typename _H2>
-    struct _Hash_code_base<_Key, _Value, _ExtractKey, _H1, _H2,
+  template<typename _Key, typename _Value, typename _Alloc,
+	   typename _ExtractKey, typename _H1, typename _H2>
+    struct _Hash_code_base<_Key, _Value, _Alloc, _ExtractKey, _H1, _H2,
 			   _Default_ranged_hash, true>
     : private _Hashtable_ebo_helper<0, _ExtractKey>,
       private _Hashtable_ebo_helper<1, _H1>,
       private _Hashtable_ebo_helper<2, _H2>
     {
     private:
-      // Gives the local iterator implementation access to _M_h2().
-      friend struct _Local_iterator_base<_Key, _Value, _ExtractKey, _H1, _H2,
-					 _Default_ranged_hash, true>;
-
       using __ebo_extract_key = _Hashtable_ebo_helper<0, _ExtractKey>;
       using __ebo_h1 = _Hashtable_ebo_helper<1, _H1>;
       using __ebo_h2 = _Hashtable_ebo_helper<2, _H2>;
+      using __pointer = typename std::allocator_traits<_Alloc>::pointer;
 
     public:
       typedef _H1 					hasher;
@@ -1362,7 +1370,13 @@ namespace __detail
 
     protected:
       typedef std::size_t 				__hash_code;
-      typedef _Hash_node<_Value, true>			__node_type;
+      typedef _Hash_node<__pointer, _Value, true>	__node_type;
+      using __node_pointer = typename __node_type::__node_pointer;
+
+      // Gives the local iterator implementation access to _M_h2().
+      friend struct _Local_iterator_base<_Key, _Value, _Alloc, _ExtractKey,
+					 _H1, _H2, _Default_ranged_hash,
+					 __node_pointer, true>;
 
       // We need the default constructor for _Hashtable default constructor.
       _Hash_code_base() = default;
@@ -1385,17 +1399,18 @@ namespace __detail
       { return _M_h2()(__c, __bkt_count); }
 
       std::size_t
-      _M_bucket_index(const __node_type* __p, std::size_t __bkt_count) const
+      _M_bucket_index(const __node_pointer& __p, std::size_t __bkt_count) const
 	noexcept( noexcept(declval<const _H2&>()((__hash_code)0,
 						 (std::size_t)0)) )
       { return _M_h2()(__p->_M_hash_code, __bkt_count); }
 
       void
-      _M_store_code(__node_type* __n, __hash_code __c) const
+      _M_store_code(const __node_pointer& __n, __hash_code __c) const
       { __n->_M_hash_code = __c; }
 
       void
-      _M_copy_code(__node_type* __to, const __node_type* __from) const
+      _M_copy_code(const __node_pointer& __to,
+		   const __node_pointer& __from) const
       { __to->_M_hash_code = __from->_M_hash_code; }
 
       void
@@ -1418,46 +1433,44 @@ namespace __detail
     };
 
   /// Partial specialization used when nodes contain a cached hash code.
-  template<typename _Key, typename _Value, typename _ExtractKey,
-	   typename _H1, typename _H2, typename _Hash>
-    struct _Local_iterator_base<_Key, _Value, _ExtractKey,
-				_H1, _H2, _Hash, true>
+  template<typename _Key, typename _Value, typename _Alloc,
+	   typename _ExtractKey, typename _H1, typename _H2,
+	   typename _Hash, typename _NodePtr>
+    struct _Local_iterator_base<_Key, _Value, _Alloc, _ExtractKey,
+				_H1, _H2, _Hash, _NodePtr, true>
     : private _Hashtable_ebo_helper<0, _H2>
+    , public _Node_iterator_base<_NodePtr>
     {
     protected:
       using __base_type = _Hashtable_ebo_helper<0, _H2>;
-      using __hash_code_base = _Hash_code_base<_Key, _Value, _ExtractKey,
+      using __base_node_iter = _Node_iterator_base<_NodePtr>;
+      using __hash_code_base = _Hash_code_base<_Key, _Value, _Alloc, _ExtractKey,
 					       _H1, _H2, _Hash, true>;
 
       _Local_iterator_base() = default;
-      _Local_iterator_base(const __hash_code_base& __base,
-			   _Hash_node<_Value, true>* __p,
+      _Local_iterator_base(const __hash_code_base& __base, _NodePtr __p,
 			   std::size_t __bkt, std::size_t __bkt_count)
-      : __base_type(__base._M_h2()),
-	_M_cur(__p), _M_bucket(__bkt), _M_bucket_count(__bkt_count) { }
+	: __base_type(__base._M_h2()), __base_node_iter(__p)
+	, _M_bucket(__bkt), _M_bucket_count(__bkt_count) { }
 
       void
       _M_incr()
       {
-	_M_cur = _M_cur->_M_next();
-	if (_M_cur)
+	__base_node_iter::_M_incr();
+	if (this->_M_cur)
 	  {
 	    std::size_t __bkt
-	      = __base_type::_M_get()(_M_cur->_M_hash_code,
-					   _M_bucket_count);
+	      = __base_type::_M_get()(this->_M_cur->_M_hash_code,
+				      _M_bucket_count);
 	    if (__bkt != _M_bucket)
-	      _M_cur = nullptr;
+	      this->_M_cur = nullptr;
 	  }
       }
 
-      _Hash_node<_Value, true>*  _M_cur;
       std::size_t _M_bucket;
       std::size_t _M_bucket_count;
 
     public:
-      const void*
-      _M_curr() const { return _M_cur; }  // for equality ops
-
       std::size_t
       _M_get_bucket() const { return _M_bucket; }  // for debug mode
     };
@@ -1493,29 +1506,33 @@ namespace __detail
       _M_h() const { return reinterpret_cast<const _Tp*>(this); }
     };
 
-  template<typename _Key, typename _Value, typename _ExtractKey,
-	   typename _H1, typename _H2, typename _Hash>
-    using __hash_code_for_local_iter
-      = _Hash_code_storage<_Hash_code_base<_Key, _Value, _ExtractKey,
-					   _H1, _H2, _Hash, false>>;
+  template<typename _Key, typename _Value, typename _Alloc,
+	   typename _ExtractKey, typename _H1, typename _H2,
+	   typename _Hash>
+    using __hash_code_for_local_iter =
+      _Hash_code_storage<_Hash_code_base<_Key, _Value, _Alloc, _ExtractKey,
+					 _H1, _H2, _Hash, false>>;
 
   // Partial specialization used when hash codes are not cached
-  template<typename _Key, typename _Value, typename _ExtractKey,
-	   typename _H1, typename _H2, typename _Hash>
-    struct _Local_iterator_base<_Key, _Value, _ExtractKey,
-				_H1, _H2, _Hash, false>
-    : __hash_code_for_local_iter<_Key, _Value, _ExtractKey, _H1, _H2, _Hash>
+  template<typename _Key, typename _Value, typename _Alloc,
+	   typename _ExtractKey, typename _H1, typename _H2,
+	   typename _Hash, typename _NodePtr>
+    struct _Local_iterator_base<_Key, _Value, _Alloc, _ExtractKey,
+				_H1, _H2, _Hash, _NodePtr, false>
+    : __hash_code_for_local_iter<_Key, _Value, _Alloc, _ExtractKey,
+				 _H1, _H2, _Hash>
+    , public _Node_iterator_base<_NodePtr>
     {
     protected:
-      using __hash_code_base = _Hash_code_base<_Key, _Value, _ExtractKey,
-					       _H1, _H2, _Hash, false>;
+      using __hash_code_base = _Hash_code_base<_Key, _Value, _Alloc,
+				_ExtractKey, _H1, _H2, _Hash, false>;
+      using __node_iter_base = _Node_iterator_base<_NodePtr>;
 
       _Local_iterator_base() : _M_bucket_count(-1) { }
 
-      _Local_iterator_base(const __hash_code_base& __base,
-			   _Hash_node<_Value, false>* __p,
+      _Local_iterator_base(const __hash_code_base& __base, _NodePtr __p,
 			   std::size_t __bkt, std::size_t __bkt_count)
-      : _M_cur(__p), _M_bucket(__bkt), _M_bucket_count(__bkt_count)
+      : __node_iter_base(__p), _M_bucket(__bkt), _M_bucket_count(__bkt_count)
       { _M_init(__base); }
 
       ~_Local_iterator_base()
@@ -1525,7 +1542,7 @@ namespace __detail
       }
 
       _Local_iterator_base(const _Local_iterator_base& __iter)
-      : _M_cur(__iter._M_cur), _M_bucket(__iter._M_bucket),
+      : __node_iter_base(__iter._M_cur), _M_bucket(__iter._M_bucket),
         _M_bucket_count(__iter._M_bucket_count)
       {
 	if (_M_bucket_count != -1)
@@ -1537,7 +1554,7 @@ namespace __detail
       {
 	if (_M_bucket_count != -1)
 	  _M_destroy();
-	_M_cur = __iter._M_cur;
+	this->_M_cur = __iter._M_cur;
 	_M_bucket = __iter._M_bucket;
 	_M_bucket_count = __iter._M_bucket_count;
 	if (_M_bucket_count != -1)
@@ -1548,17 +1565,16 @@ namespace __detail
       void
       _M_incr()
       {
-	_M_cur = _M_cur->_M_next();
-	if (_M_cur)
+	__node_iter_base::_M_incr();
+	if (this->_M_cur)
 	  {
-	    std::size_t __bkt = this->_M_h()->_M_bucket_index(_M_cur,
+	    std::size_t __bkt = this->_M_h()->_M_bucket_index(this->_M_cur,
 							      _M_bucket_count);
 	    if (__bkt != _M_bucket)
-	      _M_cur = nullptr;
+	      this->_M_cur = nullptr;
 	  }
       }
 
-      _Hash_node<_Value, false>*  _M_cur;
       std::size_t _M_bucket;
       std::size_t _M_bucket_count;
 
@@ -1570,42 +1586,22 @@ namespace __detail
       _M_destroy() { this->_M_h()->~__hash_code_base(); }
 
     public:
-      const void*
-      _M_curr() const { return _M_cur; }  // for equality ops and debug mode
-
       std::size_t
       _M_get_bucket() const { return _M_bucket; }  // for debug mode
     };
 
-  template<typename _Key, typename _Value, typename _ExtractKey,
-	   typename _H1, typename _H2, typename _Hash, bool __cache>
-    inline bool
-    operator==(const _Local_iterator_base<_Key, _Value, _ExtractKey,
-					  _H1, _H2, _Hash, __cache>& __x,
-	       const _Local_iterator_base<_Key, _Value, _ExtractKey,
-					  _H1, _H2, _Hash, __cache>& __y)
-    { return __x._M_curr() == __y._M_curr(); }
-
-  template<typename _Key, typename _Value, typename _ExtractKey,
-	   typename _H1, typename _H2, typename _Hash, bool __cache>
-    inline bool
-    operator!=(const _Local_iterator_base<_Key, _Value, _ExtractKey,
-					  _H1, _H2, _Hash, __cache>& __x,
-	       const _Local_iterator_base<_Key, _Value, _ExtractKey,
-					  _H1, _H2, _Hash, __cache>& __y)
-    { return __x._M_curr() != __y._M_curr(); }
-
   /// local iterators
-  template<typename _Key, typename _Value, typename _ExtractKey,
-	   typename _H1, typename _H2, typename _Hash,
+  template<typename _Key, typename _Value, typename _Alloc,
+	   typename _ExtractKey, typename _H1, typename _H2,
+	   typename _Hash, typename _NodePtr,
 	   bool __constant_iterators, bool __cache>
     struct _Local_iterator
-    : public _Local_iterator_base<_Key, _Value, _ExtractKey,
-				  _H1, _H2, _Hash, __cache>
+    : public _Local_iterator_base<_Key, _Value, _Alloc, _ExtractKey,
+				  _H1, _H2, _Hash, _NodePtr, __cache>
     {
     private:
-      using __base_type = _Local_iterator_base<_Key, _Value, _ExtractKey,
-					       _H1, _H2, _Hash, __cache>;
+      using __base_type = _Local_iterator_base<_Key, _Value, _Alloc,
+			_ExtractKey, _H1, _H2, _Hash, _NodePtr, __cache>;
       using __hash_code_base = typename __base_type::__hash_code_base;
     public:
       typedef _Value					value_type;
@@ -1621,7 +1617,7 @@ namespace __detail
       _Local_iterator() = default;
 
       _Local_iterator(const __hash_code_base& __base,
-		      _Hash_node<_Value, __cache>* __n,
+		      _NodePtr __n,
 		      std::size_t __bkt, std::size_t __bkt_count)
       : __base_type(__base, __n, __bkt, __bkt_count)
       { }
@@ -1651,16 +1647,17 @@ namespace __detail
     };
 
   /// local const_iterators
-  template<typename _Key, typename _Value, typename _ExtractKey,
-	   typename _H1, typename _H2, typename _Hash,
+  template<typename _Key, typename _Value, typename _Alloc,
+	   typename _ExtractKey, typename _H1, typename _H2,
+	   typename _Hash, typename _NodePtr,
 	   bool __constant_iterators, bool __cache>
     struct _Local_const_iterator
-    : public _Local_iterator_base<_Key, _Value, _ExtractKey,
-				  _H1, _H2, _Hash, __cache>
+    : public _Local_iterator_base<_Key, _Value, _Alloc, _ExtractKey,
+				  _H1, _H2, _Hash, _NodePtr, __cache>
     {
     private:
-      using __base_type = _Local_iterator_base<_Key, _Value, _ExtractKey,
-					       _H1, _H2, _Hash, __cache>;
+      using __base_type = _Local_iterator_base<_Key, _Value, _Alloc,
+			_ExtractKey, _H1, _H2, _Hash, _NodePtr, __cache>;
       using __hash_code_base = typename __base_type::__hash_code_base;
 
     public:
@@ -1673,15 +1670,14 @@ namespace __detail
       _Local_const_iterator() = default;
 
       _Local_const_iterator(const __hash_code_base& __base,
-			    _Hash_node<_Value, __cache>* __n,
+			    _NodePtr __n,
 			    std::size_t __bkt, std::size_t __bkt_count)
       : __base_type(__base, __n, __bkt, __bkt_count)
       { }
 
-      _Local_const_iterator(const _Local_iterator<_Key, _Value, _ExtractKey,
-						  _H1, _H2, _Hash,
-						  __constant_iterators,
-						  __cache>& __x)
+      _Local_const_iterator(const _Local_iterator<_Key, _Value, _Alloc,
+			    _ExtractKey, _H1, _H2, _Hash, _NodePtr,
+			    __constant_iterators, __cache>& __x)
       : __base_type(__x)
       { }
 
@@ -1719,13 +1715,14 @@ namespace __detail
    *    - __detail::_Hash_code_base
    *    - __detail::_Hashtable_ebo_helper
    */
-  template<typename _Key, typename _Value,
+  template<typename _Key, typename _Value, typename _Alloc,
 	   typename _ExtractKey, typename _Equal,
-	   typename _H1, typename _H2, typename _Hash, typename _Traits>
-  struct _Hashtable_base
-  : public _Hash_code_base<_Key, _Value, _ExtractKey, _H1, _H2, _Hash,
-			   _Traits::__hash_cached::value>,
-    private _Hashtable_ebo_helper<0, _Equal>
+	   typename _H1, typename _H2, typename _Hash,
+	   typename _Traits>
+    struct _Hashtable_base
+    : public _Hash_code_base<_Key, _Value, _Alloc, _ExtractKey, _H1, _H2, _Hash,
+			     _Traits::__hash_cached::value>
+    , private _Hashtable_ebo_helper<0, _Equal>
   {
   public:
     typedef _Key					key_type;
@@ -1739,31 +1736,28 @@ namespace __detail
     using __constant_iterators = typename __traits_type::__constant_iterators;
     using __unique_keys = typename __traits_type::__unique_keys;
 
-    using __hash_code_base = _Hash_code_base<_Key, _Value, _ExtractKey,
+    using __hash_code_base = _Hash_code_base<_Key, _Value, _Alloc, _ExtractKey,
 					     _H1, _H2, _Hash,
 					     __hash_cached::value>;
 
     using __hash_code = typename __hash_code_base::__hash_code;
     using __node_type = typename __hash_code_base::__node_type;
+    using __node_pointer = typename __hash_code_base::__node_pointer;
 
-    using iterator = __detail::_Node_iterator<value_type,
-					      __constant_iterators::value,
-					      __hash_cached::value>;
+    using iterator = __detail::_Node_iterator<__node_pointer,
+					      __constant_iterators::value>;
 
-    using const_iterator = __detail::_Node_const_iterator<value_type,
-						   __constant_iterators::value,
-						   __hash_cached::value>;
+    using const_iterator = __detail::_Node_const_iterator<__node_pointer,
+						   __constant_iterators::value>;
 
-    using local_iterator = __detail::_Local_iterator<key_type, value_type,
-						  _ExtractKey, _H1, _H2, _Hash,
-						  __constant_iterators::value,
-						     __hash_cached::value>;
+    using local_iterator = __detail::_Local_iterator<key_type, value_type, _Alloc,
+			_ExtractKey, _H1, _H2, _Hash, __node_pointer,
+			__constant_iterators::value, __hash_cached::value>;
 
-    using const_local_iterator = __detail::_Local_const_iterator<key_type,
-								 value_type,
-					_ExtractKey, _H1, _H2, _Hash,
-					__constant_iterators::value,
-					__hash_cached::value>;
+    using const_local_iterator = __detail::_Local_const_iterator<
+			key_type, value_type, _Alloc,
+			_ExtractKey, _H1, _H2, _Hash, __node_pointer,
+			__constant_iterators::value, __hash_cached::value>;
 
     using __ireturn_type = typename std::conditional<__unique_keys::value,
 						     std::pair<iterator, bool>,
@@ -1779,11 +1773,11 @@ namespace __detail
        { return true; }
       };
 
-    template<typename _Ptr2>
-      struct _Equal_hash_code<_Hash_node<_Ptr2, true>>
+    template<typename _Ptr2, typename _Value2>
+    struct _Equal_hash_code<_Hash_node<_Ptr2, _Value2, true>>
       {
        static bool
-       _S_equals(__hash_code __c, const _Hash_node<_Ptr2, true>& __n)
+       _S_equals(__hash_code __c, const _Hash_node<_Ptr2, _Value2, true>& __n)
        { return __c == __n._M_hash_code; }
       };
 
@@ -1795,7 +1789,7 @@ namespace __detail
     { }
 
     bool
-    _M_equals(const _Key& __k, __hash_code __c, __node_type* __n) const
+    _M_equals(const _Key& __k, __hash_code __c, const __node_pointer& __n) const
     {
       static_assert(__is_invocable<const _Equal&, const _Key&, const _Key&>{},
 	  "key equality predicate must be invocable with two arguments of "
@@ -1854,8 +1848,8 @@ namespace __detail
 	      _H1, _H2, _Hash, _RehashPolicy, _Traits, true>::
     _M_equal(const __hashtable& __other) const
     {
-      using __node_base = typename __hashtable::__node_base;
-      using __node_type = typename __hashtable::__node_type;
+      using __bucket_type = typename __hashtable::__bucket_type;
+      using __node_pointer = typename __hashtable::__node_pointer;
       const __hashtable* __this = static_cast<const __hashtable*>(this);
       if (__this->size() != __other.size())
 	return false;
@@ -1863,18 +1857,17 @@ namespace __detail
       for (auto __itx = __this->begin(); __itx != __this->end(); ++__itx)
 	{
 	  std::size_t __ybkt = __other._M_bucket_index(__itx._M_cur);
-	  __node_base* __prev_n = __other._M_buckets[__ybkt];
+	  __bucket_type __prev_n = __other._M_buckets[__ybkt];
 	  if (!__prev_n)
 	    return false;
 
-	  for (__node_type* __n = static_cast<__node_type*>(__prev_n->_M_nxt);;
-	       __n = __n->_M_next())
+	  for (__node_pointer __n = __prev_n->_M_nxt;; __n = __n->_M_nxt)
 	    {
 	      if (__n->_M_v() == *__itx)
 		break;
 
 	      if (!__n->_M_nxt
-		  || __other._M_bucket_index(__n->_M_next()) != __ybkt)
+		  || __other._M_bucket_index(__n->_M_nxt) != __ybkt)
 		return false;
 	    }
 	}
@@ -1906,8 +1899,8 @@ namespace __detail
 	      _H1, _H2, _Hash, _RehashPolicy, _Traits, false>::
     _M_equal(const __hashtable& __other) const
     {
-      using __node_base = typename __hashtable::__node_base;
-      using __node_type = typename __hashtable::__node_type;
+      using __bucket_type = typename __hashtable::__bucket_type;
+      using __node_pointer = typename __hashtable::__node_pointer;
       const __hashtable* __this = static_cast<const __hashtable*>(this);
       if (__this->size() != __other.size())
 	return false;
@@ -1923,19 +1916,19 @@ namespace __detail
 	    ++__x_count;
 
 	  std::size_t __ybkt = __other._M_bucket_index(__itx._M_cur);
-	  __node_base* __y_prev_n = __other._M_buckets[__ybkt];
+	  __bucket_type __y_prev_n = __other._M_buckets[__ybkt];
 	  if (!__y_prev_n)
 	    return false;
 
-	  __node_type* __y_n = static_cast<__node_type*>(__y_prev_n->_M_nxt);
-	  for (;; __y_n = __y_n->_M_next())
+	  __node_pointer __y_n = __y_prev_n->_M_nxt;
+	  for (;; __y_n = __y_n->_M_nxt)
 	    {
 	      if (__this->key_eq()(_ExtractKey()(__y_n->_M_v()),
 				   _ExtractKey()(*__itx)))
 		break;
 
 	      if (!__y_n->_M_nxt
-		  || __other._M_bucket_index(__y_n->_M_next()) != __ybkt)
+		  || __other._M_bucket_index(__y_n->_M_nxt) != __ybkt)
 		return false;
 	    }
 
@@ -1973,11 +1966,13 @@ namespace __detail
       using __value_alloc_traits = typename __node_alloc_traits::template
 	rebind_traits<typename __node_type::value_type>;
 
-      using __node_base = __detail::_Hash_node_base;
-      using __bucket_type = __node_base*;      
+      using __node_pointer = typename __node_alloc_traits::pointer;
+      using __node_base = __detail::_Hash_node_base<__node_pointer>;
+      using __bucket_type = __ptr_rebind<__node_pointer, __node_base>;
       using __bucket_alloc_type =
 	__alloc_rebind<__node_alloc_type, __bucket_type>;
       using __bucket_alloc_traits = std::allocator_traits<__bucket_alloc_type>;
+      using __bucket_pointer = typename __bucket_alloc_traits::pointer;
 
       _Hashtable_alloc() = default;
       _Hashtable_alloc(const _Hashtable_alloc&) = default;
@@ -1998,27 +1993,27 @@ namespace __detail
 
       // Allocate a node and construct an element within it.
       template<typename... _Args>
-	__node_type*
+	__node_pointer
 	_M_allocate_node(_Args&&... __args);
 
       // Destroy the element within a node and deallocate the node.
       void
-      _M_deallocate_node(__node_type* __n);
+      _M_deallocate_node(__node_pointer __n);
 
       // Deallocate a node.
       void
-      _M_deallocate_node_ptr(__node_type* __n);
+      _M_deallocate_node_ptr(__node_pointer __n);
 
       // Deallocate the linked list of nodes pointed to by __n.
       // The elements within the nodes are destroyed.
       void
-      _M_deallocate_nodes(__node_type* __n);
+      _M_deallocate_nodes(__node_pointer __n);
 
-      __bucket_type*
+      __bucket_pointer
       _M_allocate_buckets(std::size_t __bkt_count);
 
       void
-      _M_deallocate_buckets(__bucket_type*, std::size_t __bkt_count);
+      _M_deallocate_buckets(__bucket_pointer, std::size_t __bkt_count);
     };
 
   // Definitions of class template _Hashtable_alloc's out-of-line member
@@ -2027,17 +2022,16 @@ namespace __detail
     template<typename... _Args>
       auto
       _Hashtable_alloc<_NodeAlloc>::_M_allocate_node(_Args&&... __args)
-      -> __node_type*
+      -> __node_pointer
       {
 	auto __nptr = __node_alloc_traits::allocate(_M_node_allocator(), 1);
-	__node_type* __n = std::__to_address(__nptr);
 	__try
 	  {
-	    ::new ((void*)__n) __node_type;
+	    ::new ((void*)std::__to_address(__nptr)) __node_type;
 	    __node_alloc_traits::construct(_M_node_allocator(),
-					   __n->_M_valptr(),
+					   __nptr->_M_valptr(),
 					   std::forward<_Args>(__args)...);
-	    return __n;
+	    return __nptr;
 	  }
 	__catch(...)
 	  {
@@ -2048,55 +2042,51 @@ namespace __detail
 
   template<typename _NodeAlloc>
     void
-    _Hashtable_alloc<_NodeAlloc>::_M_deallocate_node(__node_type* __n)
+    _Hashtable_alloc<_NodeAlloc>::_M_deallocate_node(__node_pointer __nptr)
     {
-      __node_alloc_traits::destroy(_M_node_allocator(), __n->_M_valptr());
-      _M_deallocate_node_ptr(__n);
+      __node_alloc_traits::destroy(_M_node_allocator(), __nptr->_M_valptr());
+      _M_deallocate_node_ptr(__nptr);
     }
 
   template<typename _NodeAlloc>
     void
-    _Hashtable_alloc<_NodeAlloc>::_M_deallocate_node_ptr(__node_type* __n)
+    _Hashtable_alloc<_NodeAlloc>::_M_deallocate_node_ptr(__node_pointer __nptr)
     {
-      typedef typename __node_alloc_traits::pointer _Ptr;
-      auto __ptr = std::pointer_traits<_Ptr>::pointer_to(*__n);
-      __n->~__node_type();
-      __node_alloc_traits::deallocate(_M_node_allocator(), __ptr, 1);
+      __nptr->~__node_type();
+      __node_alloc_traits::deallocate(_M_node_allocator(), __nptr, 1);
     }
 
   template<typename _NodeAlloc>
     void
-    _Hashtable_alloc<_NodeAlloc>::_M_deallocate_nodes(__node_type* __n)
+    _Hashtable_alloc<_NodeAlloc>::_M_deallocate_nodes(__node_pointer __nptr)
     {
-      while (__n)
+      while (__nptr)
 	{
-	  __node_type* __tmp = __n;
-	  __n = __n->_M_next();
+	  __node_pointer __tmp = __nptr;
+	  __nptr = __nptr->_M_nxt;
 	  _M_deallocate_node(__tmp);
 	}
     }
 
   template<typename _NodeAlloc>
-    typename _Hashtable_alloc<_NodeAlloc>::__bucket_type*
+    auto
     _Hashtable_alloc<_NodeAlloc>::_M_allocate_buckets(std::size_t __bkt_count)
+    -> __bucket_pointer
     {
       __bucket_alloc_type __alloc(_M_node_allocator());
 
       auto __ptr = __bucket_alloc_traits::allocate(__alloc, __bkt_count);
-      __bucket_type* __p = std::__to_address(__ptr);
-      __builtin_memset(__p, 0, __bkt_count * sizeof(__bucket_type));
-      return __p;
+      std::fill_n(__ptr, __bkt_count, nullptr);
+      return __ptr;
     }
 
   template<typename _NodeAlloc>
     void
-    _Hashtable_alloc<_NodeAlloc>::_M_deallocate_buckets(__bucket_type* __bkts,
+    _Hashtable_alloc<_NodeAlloc>::_M_deallocate_buckets(__bucket_pointer __bkts,
 							std::size_t __bkt_count)
     {
-      typedef typename __bucket_alloc_traits::pointer _Ptr;
-      auto __ptr = std::pointer_traits<_Ptr>::pointer_to(*__bkts);
       __bucket_alloc_type __alloc(_M_node_allocator());
-      __bucket_alloc_traits::deallocate(__alloc, __ptr, __bkt_count);
+      __bucket_alloc_traits::deallocate(__alloc, __bkts, __bkt_count);
     }
 
  //@} hashtable-detail
diff --git a/libstdc++-v3/include/debug/unordered_map b/libstdc++-v3/include/debug/unordered_map
index 7be1d2ee952..41f169168aa 100644
--- a/libstdc++-v3/include/debug/unordered_map
+++ b/libstdc++-v3/include/debug/unordered_map
@@ -621,7 +621,7 @@ namespace __debug
 	  [__victim](_Base_const_iterator __it) { return __it == __victim; });
 	this->_M_invalidate_local_if(
 	  [__victim](_Base_const_local_iterator __it)
-	  { return __it._M_curr() == __victim._M_cur; });
+	  { return __it == __victim; });
       }
 
       _Base_iterator
@@ -1227,7 +1227,7 @@ namespace __debug
 	  [__victim](_Base_const_iterator __it) { return __it == __victim; });
 	this->_M_invalidate_local_if(
 	  [__victim](_Base_const_local_iterator __it)
-	  { return __it._M_curr() == __victim._M_cur; });
+	  { return __it == __victim; });
       }
 
       _Base_iterator
diff --git a/libstdc++-v3/include/debug/unordered_set b/libstdc++-v3/include/debug/unordered_set
index 9941bbe1c24..65539b75350 100644
--- a/libstdc++-v3/include/debug/unordered_set
+++ b/libstdc++-v3/include/debug/unordered_set
@@ -506,7 +506,7 @@ namespace __debug
 	  [__victim](_Base_const_iterator __it) { return __it == __victim; });
 	this->_M_invalidate_local_if(
 	  [__victim](_Base_const_local_iterator __it)
-	  { return __it._M_curr() == __victim._M_cur; });
+	  { return __it == __victim; });
       }
 
       _Base_iterator
@@ -1066,7 +1066,7 @@ namespace __debug
 	  [__victim](_Base_const_iterator __it) { return __it == __victim; });
 	this->_M_invalidate_local_if(
 	  [__victim](_Base_const_local_iterator __it)
-	  { return __it._M_curr() == __victim._M_cur; });
+	  { return __it == __victim; });
       }
 
       _Base_iterator
diff --git a/libstdc++-v3/testsuite/23_containers/unordered_set/allocator/ext_ptr.cc b/libstdc++-v3/testsuite/23_containers/unordered_set/allocator/ext_ptr.cc
index f6b908ac03e..6026aeff140 100644
--- a/libstdc++-v3/testsuite/23_containers/unordered_set/allocator/ext_ptr.cc
+++ b/libstdc++-v3/testsuite/23_containers/unordered_set/allocator/ext_ptr.cc
@@ -17,8 +17,7 @@
 
 // This test fails to compile since C++17 (see xfail-if below) so we can only
 // do a "run" test for C++11 and C++14, and a "compile" test for C++17 and up.
-// { dg-do run { target { c++11_only || c++14_only } } }
-// { dg-do compile { target c++17 } }
+// { dg-do run { target c++11 } }
 
 #include <unordered_set>
 #include <memory>
@@ -26,15 +25,22 @@
 #include <testsuite_allocator.h>
 
 struct T { int i; };
-bool operator==(const T& l, const T& r) { return l.i == r.i; }
-struct H { std::size_t operator()(const T& t) const noexcept { return t.i; }
+
+bool operator==(const T& l, const T& r)
+{ return l.i == r.i; }
+
+struct H
+{
+  std::size_t
+  operator()(const T& t) const noexcept
+  { return t.i; }
 };
-struct E : std::equal_to<T> { };
+
+struct E : std::equal_to<T>
+{ };
 
 using __gnu_test::CustomPointerAlloc;
 
-// { dg-xfail-if "node reinsertion assumes raw pointers" { c++17 } }
-// TODO when removing this xfail change the test back to "dg-do run".
 template class std::unordered_set<T, H, E, CustomPointerAlloc<T>>;
 
 void test01()

^ permalink raw reply	[flat|nested] 10+ messages in thread

end of thread, other threads:[~2021-06-10 17:22 UTC | newest]

Thread overview: 10+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2020-04-19 17:31 libstdc++ PR 57272 Fancy pointer support in Hashtable François Dumont
2020-05-15 21:12 ` François Dumont
2020-09-28 20:37   ` François Dumont
2020-10-20 11:04     ` Jonathan Wakely
2020-10-20 17:26       ` François Dumont
2020-11-01 21:48       ` François Dumont
2020-11-02 14:11         ` Jonathan Wakely
2020-11-02 21:33           ` François Dumont
2021-01-11 18:10           ` François Dumont
2021-06-10 17:22           ` François Dumont

This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).