Patchwork unordered containers: reuse nodes on assignment

login
register
mail settings
Submitter François Dumont
Date July 4, 2013, 8:54 p.m.
Message ID <51D5E0F6.90406@gmail.com>
Download mbox | patch
Permalink /patch/257014/
State New
Headers show

Comments

François Dumont - July 4, 2013, 8:54 p.m.
On 07/01/2013 11:35 PM, Paolo Carlini wrote:
> On 07/01/2013 09:35 PM, François Dumont wrote:
>> This is it indeed, I am surprised this problem is so old, a Standard 
>> issue perhaps ? If not I might add it to my todo list.
> Yesterday I had a look and I think it's just a bug, I found in 
> Bugzilla a duplicate too, and another resolved Jon some time ago.
>
> Paolo.
>
It doesn't seem to be resolved.

And about the patch itself, is it ok ? I only noticed that some lambdas 
I was using didn't need to capture 'this' so I clean it and here is the 
updated version of the patch.

Tested under linux x86_64.

François
Jonathan Wakely - July 4, 2013, 10:28 p.m.
On 4 July 2013 21:54, François Dumont wrote:
>
> And about the patch itself, is it ok ?

Yes, that latest patch is OK, thanks.

It's made me think about the design a bit more though ...

I've been a little uncomfortable for some time with the number of
template parameters that are needed everywhere in hashtable_policy.h.
In most cases they seem necessary, but does the _ReuseOrAllocNode
template really need 10 template parameters?  Couldn't it just be
passed the relevant _Hashtable type? Unfortunately with the current
design it does seem necessary to know the full _Hashtable type, even
though the functionality only really depends on the allocator type
(and node and value types, but they can be obtained from the
allocator.)  That means if I instantiate unordered_set<T, H, P, A> and
unordered_set<T, H2, P2, A> the compiler has to instantiate two
different specializations of _ReuseOrAllocNode (and other code in
_Hashtable) even though it doesn't care about the two function
objects, and the executable is larger.

Would it be possible to separate _M_node_allocator, _M_allocate_node,
_M_deallocate_nodes and _M_deallocate_node into a separate base class
of _Hashtable, and have _ReuseOrAllocNode only depend on that?  That
would allow unordered_set<T, H, P, A> and unordered_set<T, H2, P2, A>
to share more code.
François Dumont - July 5, 2013, 9:29 p.m.
Patch applied.

I also found the number of template parameters painful. Isolating a part 
of the _Hashtable in a base class is a good idea and seems to be the 
solution indeed, I will have a try.

François


On 07/05/2013 12:28 AM, Jonathan Wakely wrote:
> On 4 July 2013 21:54, François Dumont wrote:
>> And about the patch itself, is it ok ?
> Yes, that latest patch is OK, thanks.
>
> It's made me think about the design a bit more though ...
>
> I've been a little uncomfortable for some time with the number of
> template parameters that are needed everywhere in hashtable_policy.h.
> In most cases they seem necessary, but does the _ReuseOrAllocNode
> template really need 10 template parameters?  Couldn't it just be
> passed the relevant _Hashtable type? Unfortunately with the current
> design it does seem necessary to know the full _Hashtable type, even
> though the functionality only really depends on the allocator type
> (and node and value types, but they can be obtained from the
> allocator.)  That means if I instantiate unordered_set<T, H, P, A> and
> unordered_set<T, H2, P2, A> the compiler has to instantiate two
> different specializations of _ReuseOrAllocNode (and other code in
> _Hashtable) even though it doesn't care about the two function
> objects, and the executable is larger.
>
> Would it be possible to separate _M_node_allocator, _M_allocate_node,
> _M_deallocate_nodes and _M_deallocate_node into a separate base class
> of _Hashtable, and have _ReuseOrAllocNode only depend on that?  That
> would allow unordered_set<T, H, P, A> and unordered_set<T, H2, P2, A>
> to share more code.
>

Patch

Index: include/bits/hashtable_policy.h
===================================================================
--- include/bits/hashtable_policy.h	(revision 200571)
+++ include/bits/hashtable_policy.h	(working copy)
@@ -102,6 +102,90 @@ 
       { return std::get<0>(std::forward<_Tp>(__x)); }
   };
 
+  // Functor recycling a pool of nodes and using allocation once the pool is
+  // empty.
+  template<typename _Key, typename _Value, typename _Alloc,
+	   typename _ExtractKey, typename _Equal,
+	   typename _H1, typename _H2, typename _Hash,
+	   typename _RehashPolicy, typename _Traits>
+    struct _ReuseOrAllocNode
+    {
+    private:
+      using __hashtable = _Hashtable<_Key, _Value, _Alloc, _ExtractKey,
+				     _Equal, _H1, _H2, _Hash,
+				     _RehashPolicy, _Traits>;
+      using __val_alloc_type = typename __hashtable::_Value_alloc_type;
+      using __val_alloc_traits = typename __hashtable::_Value_alloc_traits;
+      using __node_alloc_traits = typename __hashtable::_Node_alloc_traits;
+      using __node_type = typename __hashtable::__node_type;
+
+    public:
+      _ReuseOrAllocNode(__node_type* __nodes, __hashtable& __h)
+	: _M_nodes(__nodes), _M_h(__h) { }
+      _ReuseOrAllocNode(const _ReuseOrAllocNode&) = delete;
+
+      ~_ReuseOrAllocNode()
+      { _M_h._M_deallocate_nodes(_M_nodes); }
+
+      template<typename _Arg>
+	__node_type*
+	operator()(_Arg&& __arg) const
+	{
+	  if (_M_nodes)
+	    {
+	      __node_type* __node = _M_nodes;
+	      _M_nodes = _M_nodes->_M_next();
+	      __node->_M_nxt = nullptr;
+	      __val_alloc_type __a(_M_h._M_node_allocator());
+	      __val_alloc_traits::destroy(__a, __node->_M_valptr());
+	      __try
+		{
+		  __val_alloc_traits::construct(__a, __node->_M_valptr(),
+						std::forward<_Arg>(__arg));
+		}
+	      __catch(...)
+		{
+		  __node->~__node_type();
+		  __node_alloc_traits::deallocate(_M_h._M_node_allocator(),
+						  __node, 1);
+		  __throw_exception_again;
+		}
+	      return __node;
+	    }
+	  return _M_h._M_allocate_node(std::forward<_Arg>(__arg));
+	}
+
+    private:
+      mutable __node_type* _M_nodes;
+      __hashtable& _M_h;
+    };
+
+  // Functor similar to the previous one but without any pool of node to recycle.
+  template<typename _Key, typename _Value, typename _Alloc,
+	   typename _ExtractKey, typename _Equal,
+	   typename _H1, typename _H2, typename _Hash,
+	   typename _RehashPolicy, typename _Traits>
+    struct _AllocNode
+    {
+    private:
+      using __hashtable = _Hashtable<_Key, _Value, _Alloc, _ExtractKey,
+				     _Equal, _H1, _H2, _Hash,
+				     _RehashPolicy, _Traits>;
+      using __node_type = typename __hashtable::__node_type;
+
+    public:
+      _AllocNode(__hashtable& __h)
+	: _M_h(__h) { }
+
+      template<typename _Arg>
+	__node_type*
+	operator()(_Arg&& __arg) const
+	{ return _M_h._M_allocate_node(std::forward<_Arg>(__arg)); }
+
+    private:
+      __hashtable& _M_h;
+    };
+
   // Auxiliary types used for all instantiations of _Hashtable nodes
   // and iterators.
 
@@ -597,6 +681,7 @@ 
 	   typename _RehashPolicy, typename _Traits>
     struct _Insert_base
     {
+    protected:
       using __hashtable = _Hashtable<_Key, _Value, _Alloc, _ExtractKey,
 				     _Equal, _H1, _H2, _Hash,
 				     _RehashPolicy, _Traits>;
@@ -612,23 +697,34 @@ 
 
       using __unique_keys = typename __hashtable_base::__unique_keys;
       using __ireturn_type = typename __hashtable_base::__ireturn_type;
+      using __node_gen_type = _AllocNode<_Key, _Value, _Alloc, _ExtractKey,
+					 _Equal, _H1, _H2, _Hash,
+					 _RehashPolicy, _Traits>;
 
       __hashtable&
       _M_conjure_hashtable()
       { return *(static_cast<__hashtable*>(this)); }
 
+      template<typename _InputIterator, typename _NodeGetter>
+	void
+	_M_insert_range(_InputIterator __first, _InputIterator __last,
+			const _NodeGetter&);
+
+    public:
       __ireturn_type
       insert(const value_type& __v)
       {
 	__hashtable& __h = _M_conjure_hashtable();
-	return __h._M_insert(__v, __unique_keys());
+	__node_gen_type __node_gen(__h);
+	return __h._M_insert(__v, __node_gen, __unique_keys());
       }
 
       iterator
       insert(const_iterator __hint, const value_type& __v)
       {
 	__hashtable& __h = _M_conjure_hashtable();
-	return __h._M_insert(__hint, __v, __unique_keys());
+	__node_gen_type __node_gen(__h);	
+	return __h._M_insert(__hint, __v, __node_gen, __unique_keys());
       }
 
       void
@@ -637,18 +733,24 @@ 
 
       template<typename _InputIterator>
 	void
-	insert(_InputIterator __first, _InputIterator __last);
+	insert(_InputIterator __first, _InputIterator __last)
+	{
+	  __hashtable& __h = _M_conjure_hashtable();
+	  __node_gen_type __node_gen(__h);
+	  return _M_insert_range(__first, __last, __node_gen);
+	}
     };
 
   template<typename _Key, typename _Value, typename _Alloc,
 	   typename _ExtractKey, typename _Equal,
 	   typename _H1, typename _H2, typename _Hash,
 	   typename _RehashPolicy, typename _Traits>
-    template<typename _InputIterator>
+    template<typename _InputIterator, typename _NodeGetter>
       void
       _Insert_base<_Key, _Value, _Alloc, _ExtractKey, _Equal, _H1, _H2, _Hash,
 		    _RehashPolicy, _Traits>::
-      insert(_InputIterator __first, _InputIterator __last)
+      _M_insert_range(_InputIterator __first, _InputIterator __last,
+		      const _NodeGetter& __node_gen)
       {
 	using __rehash_type = typename __hashtable::__rehash_type;
 	using __rehash_state = typename __hashtable::__rehash_state;
@@ -667,7 +769,7 @@ 
 	  __h._M_rehash(__do_rehash.second, __saved_state);
 
 	for (; __first != __last; ++__first)
-	  __h._M_insert(*__first, __unique_keys());
+	  __h._M_insert(*__first, __node_gen, __unique_keys());
       }
 
   /**
@@ -702,6 +804,7 @@ 
 
       using __unique_keys = typename __base_type::__unique_keys;
       using __hashtable = typename __base_type::__hashtable;
+      using __node_gen_type = typename __base_type::__node_gen_type;
 
       using __base_type::insert;
 
@@ -709,14 +812,17 @@ 
       insert(value_type&& __v)
       {
 	__hashtable& __h = this->_M_conjure_hashtable();
-	return __h._M_insert(std::move(__v), __unique_keys());
+	__node_gen_type __node_gen(__h);
+	return __h._M_insert(std::move(__v), __node_gen, __unique_keys());
       }
 
       iterator
       insert(const_iterator __hint, value_type&& __v)
       {
 	__hashtable& __h = this->_M_conjure_hashtable();
-	return __h._M_insert(__hint, std::move(__v), __unique_keys());
+	__node_gen_type __node_gen(__h);
+	return __h._M_insert(__hint, std::move(__v), __node_gen,
+			     __unique_keys());
       }
     };
 
@@ -739,6 +845,7 @@ 
 
       using __unique_keys = typename __base_type::__unique_keys;
       using __hashtable = typename __base_type::__hashtable;
+      using __node_gen_type = typename __base_type::__node_gen_type;
 
       using __base_type::insert;
 
@@ -746,14 +853,17 @@ 
       insert(value_type&& __v)
       {
 	__hashtable& __h = this->_M_conjure_hashtable();
-	return __h._M_insert(std::move(__v), __unique_keys());
+	__node_gen_type __node_gen(__h);
+	return __h._M_insert(std::move(__v), __node_gen, __unique_keys());
       }
 
       iterator
       insert(const_iterator __hint, value_type&& __v)
       {
 	__hashtable& __h = this->_M_conjure_hashtable();
-	return __h._M_insert(__hint, std::move(__v), __unique_keys());
+	__node_gen_type __node_gen(__h);
+	return __h._M_insert(__hint, std::move(__v), __node_gen,
+			     __unique_keys());
       }
     };
 
@@ -1694,120 +1804,6 @@ 
 	{ }
     };
 
-  /*
-   * Following are functors recyclicing a pool of nodes and using allocation
-   * once the pool is empty.
-   */
-  /// Version using copy semantic through the copy constructor.
-  template<typename _Key, typename _Value, typename _Alloc,
-	   typename _ExtractKey, typename _Equal,
-	   typename _H1, typename _H2, typename _Hash,
-	   typename _RehashPolicy, typename _Traits>
-    struct _ReuseOrAllocNode
-    {
-    private:
-      using __hashtable = _Hashtable<_Key, _Value, _Alloc, _ExtractKey,
-				     _Equal, _H1, _H2, _Hash,
-				     _RehashPolicy, _Traits>;
-      using __val_alloc_type = typename __hashtable::_Value_alloc_type;
-      using __val_alloc_traits = typename __hashtable::_Value_alloc_traits;
-      using __node_alloc_traits = typename __hashtable::_Node_alloc_traits;
-      using __node_type = typename __hashtable::__node_type;
-
-    public:
-      _ReuseOrAllocNode(__node_type* __nodes, __hashtable& __h)
-	: _M_nodes(__nodes), _M_h(__h) { }
-      _ReuseOrAllocNode(const _ReuseOrAllocNode&) = delete;
-
-      ~_ReuseOrAllocNode()
-      { _M_h._M_deallocate_nodes(_M_nodes); }
-
-      __node_type*
-      operator()(const __node_type* __n) const
-      {
-	if (_M_nodes)
-	  {
-	    __node_type* __node = _M_nodes;
-	    _M_nodes = _M_nodes->_M_next();
-	    __node->_M_nxt = nullptr;
-	    __val_alloc_type __a(_M_h._M_node_allocator());
-	    __val_alloc_traits::destroy(__a, __node->_M_valptr());
-	    __try
-	      {
-		__val_alloc_traits::construct(__a, __node->_M_valptr(),
-					      __n->_M_v());
-	      }
-	    __catch(...)
-	      {
-		__node->~__node_type();
-		__node_alloc_traits::deallocate(_M_h._M_node_allocator(),
-						__node, 1);
-		__throw_exception_again;
-	      }
-	    return __node;
-	  }
-	return _M_h._M_allocate_node(__n->_M_v());
-      }
-
-      mutable __node_type* _M_nodes;
-      __hashtable& _M_h;
-    };
-
-  /// Version using move semantic through the move constructor.
-  template<typename _Key, typename _Value, typename _Alloc,
-	   typename _ExtractKey, typename _Equal,
-	   typename _H1, typename _H2, typename _Hash,
-	   typename _RehashPolicy, typename _Traits>
-    struct _MoveReuseOrAllocNode
-    {
-    private:
-      using __hashtable = _Hashtable<_Key, _Value, _Alloc, _ExtractKey,
-				     _Equal, _H1, _H2, _Hash,
-				     _RehashPolicy, _Traits>;
-      using __val_alloc_type = typename __hashtable::_Value_alloc_type;
-      using __val_alloc_traits = typename __hashtable::_Value_alloc_traits;
-      using __node_alloc_traits = typename __hashtable::_Node_alloc_traits;
-      using __node_type = typename __hashtable::__node_type;
-
-    public:
-      _MoveReuseOrAllocNode(__node_type* __nodes, __hashtable& __h)
-	: _M_nodes(__nodes), _M_h(__h) { }
-      _MoveReuseOrAllocNode(const _MoveReuseOrAllocNode&) = delete;
-
-      ~_MoveReuseOrAllocNode()
-      { _M_h._M_deallocate_nodes(_M_nodes); }
-
-      __node_type*
-      operator()(__node_type* __n) const
-      {
-	if (_M_nodes)
-	  {
-	    __node_type* __node = _M_nodes;
-	    _M_nodes = _M_nodes->_M_next();
-	    __node->_M_nxt = nullptr;
-	    __val_alloc_type  __a(_M_h._M_node_allocator());
-	    __val_alloc_traits::destroy(__a, __node->_M_valptr());
-	    __try
-	      {
-		__val_alloc_traits::construct(__a, __node->_M_valptr(),
-					std::move_if_noexcept(__n->_M_v()));
-	      }
-	    __catch(...)
-	      {
-		__node->~__node_type();
-		__node_alloc_traits::deallocate(_M_h._M_node_allocator(),
-						__node, 1);
-		__throw_exception_again;
-	      }
-	    return __node;
-	  }
-	return _M_h._M_allocate_node(std::move_if_noexcept(__n->_M_v()));
-      }
-
-      mutable __node_type* _M_nodes;
-      __hashtable& _M_h;
-    };
-
  //@} hashtable-detail
 _GLIBCXX_END_NAMESPACE_VERSION
 } // namespace __detail
Index: include/bits/hashtable.h
===================================================================
--- include/bits/hashtable.h	(revision 200571)
+++ include/bits/hashtable.h	(working copy)
@@ -239,6 +239,11 @@ 
 					    _Equal, _H1, _H2, _Hash,
 					    _RehashPolicy, _Traits>;
 
+      using __reuse_or_alloc_node_type =
+	__detail::_ReuseOrAllocNode<_Key, _Value, _Alloc,
+				    _ExtractKey, _Equal, _H1, _H2, _Hash,
+				    _RehashPolicy, _Traits>;
+
       // Metaprogramming for picking apart hash caching.
       template<typename _Cond>
 	using __if_hash_cached = __or_<__not_<__hash_cached>, _Cond>;
@@ -284,7 +289,6 @@ 
 		    "Cache the hash code or make functors involved in hash code"
 		    " and bucket index computation copy assignable");
 
-    public:
       template<typename _Keya, typename _Valuea, typename _Alloca,
 	       typename _ExtractKeya, typename _Equala,
 	       typename _H1a, typename _H2a, typename _Hasha,
@@ -308,17 +312,16 @@ 
       template<typename _Keya, typename _Valuea, typename _Alloca,
 	       typename _ExtractKeya, typename _Equala,
 	       typename _H1a, typename _H2a, typename _Hasha,
-	       typename _RehashPolicya, typename _Traitsa,
-	       bool _IsCopyAssignable>
+	       typename _RehashPolicya, typename _Traitsa>
 	friend struct __detail::_ReuseOrAllocNode;
 
       template<typename _Keya, typename _Valuea, typename _Alloca,
 	       typename _ExtractKeya, typename _Equala,
 	       typename _H1a, typename _H2a, typename _Hasha,
-	       typename _RehashPolicya, typename _Traitsa,
-	       bool _IsMoveAssignable>
-	friend struct __detail::_MoveReuseOrAllocNode;
+	       typename _RehashPolicya, typename _Traitsa>
+	friend struct __detail::_AllocNode;
 
+    public:
       using size_type = typename __hashtable_base::size_type;
       using difference_type = typename __hashtable_base::difference_type;
 
@@ -394,9 +397,9 @@ 
       _M_begin() const
       { return static_cast<__node_type*>(_M_before_begin()._M_nxt); }
 
-      template<typename _UnaryOp>
+      template<typename _NodeGenerator>
 	void
-	_M_assign(const _Hashtable&, const _UnaryOp&);
+	_M_assign(const _Hashtable&, const _NodeGenerator&);
 
       void
       _M_move_assign(_Hashtable&&, std::true_type);
@@ -487,8 +490,10 @@ 
       _Hashtable&
       operator=(initializer_list<value_type> __l)
       {
+	__reuse_or_alloc_node_type __roan(_M_begin(), *this);
+	_M_before_begin()._M_nxt = nullptr;
 	clear();
-	this->insert(__l.begin(), __l.end());
+	this->_M_insert_range(__l.begin(), __l.end(), __roan);
 	return *this;
       }
 
@@ -701,25 +706,33 @@ 
 	iterator
 	_M_emplace(const_iterator, std::false_type, _Args&&... __args);
 
-      template<typename _Arg>
+      template<typename _Arg, typename _NodeGenerator>
 	std::pair<iterator, bool>
-	_M_insert(_Arg&&, std::true_type);
+	_M_insert(_Arg&&, const _NodeGenerator&, std::true_type);
 
-      template<typename _Arg>
+      template<typename _Arg, typename _NodeGenerator>
 	iterator
-	_M_insert(_Arg&& __arg, std::false_type __uk)
-	{ return _M_insert(cend(), std::forward<_Arg>(__arg), __uk); }
+	_M_insert(_Arg&& __arg, const _NodeGenerator& __node_gen,
+		  std::false_type __uk)
+	{
+	  return _M_insert(cend(), std::forward<_Arg>(__arg), __node_gen,
+			   __uk);
+	}
 
       // Insert with hint, not used when keys are unique.
-      template<typename _Arg>
+      template<typename _Arg, typename _NodeGenerator>
 	iterator
-	_M_insert(const_iterator, _Arg&& __arg, std::true_type __uk)
-	{ return _M_insert(std::forward<_Arg>(__arg), __uk).first; }
+	_M_insert(const_iterator, _Arg&& __arg, const _NodeGenerator& __node_gen,
+		  std::true_type __uk)
+	{
+	  return
+	    _M_insert(std::forward<_Arg>(__arg), __node_gen, __uk).first;
+	}
 
       // Insert with hint when keys are not unique.
-      template<typename _Arg>
+      template<typename _Arg, typename _NodeGenerator>
 	iterator
-	_M_insert(const_iterator, _Arg&&, std::false_type);
+	_M_insert(const_iterator, _Arg&&, const _NodeGenerator&, std::false_type);
 
       size_type
       _M_erase(std::true_type, const key_type&);
@@ -1029,12 +1042,11 @@ 
 	    __hashtable_base::operator=(__ht);
 	    _M_element_count = __ht._M_element_count;
 	    _M_rehash_policy = __ht._M_rehash_policy;
-	    __detail::_ReuseOrAllocNode<_Key, _Value, _Alloc, _ExtractKey,
-					_Equal, _H1, _H2, _Hash,
-					_RehashPolicy, _Traits>
-	      __roan(_M_begin(), *this);
+	    __reuse_or_alloc_node_type __roan(_M_begin(), *this);
 	    _M_before_begin()._M_nxt = nullptr;
-	    _M_assign(__ht, __roan);
+	    _M_assign(__ht, 
+		      [&__roan](const __node_type* __n)
+		      { return __roan(__n->_M_v()); });
 	    if (__former_buckets)
 	      _M_deallocate_buckets(__former_buckets, __former_bucket_count);
 	  }
@@ -1059,11 +1071,11 @@ 
 	   typename _Alloc, typename _ExtractKey, typename _Equal,
 	   typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
 	   typename _Traits>
-    template<typename _UnaryOp>
+    template<typename _NodeGenerator>
       void
       _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
 		 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
-      _M_assign(const _Hashtable& __ht, const _UnaryOp& __node_getter)
+      _M_assign(const _Hashtable& __ht, const _NodeGenerator& __node_gen)
       {
 	__bucket_type* __buckets = nullptr;
 	if (!_M_buckets)
@@ -1077,7 +1089,7 @@ 
 	    // 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_getter(__ht_n);
+	    __node_type* __this_n = __node_gen(__ht_n);
 	    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();
@@ -1086,7 +1098,7 @@ 
 	    __node_base* __prev_n = __this_n;
 	    for (__ht_n = __ht_n->_M_next(); __ht_n; __ht_n = __ht_n->_M_next())
 	      {
-		__this_n = __node_getter(__ht_n);
+		__this_n = __node_gen(__ht_n);
 		__prev_n->_M_nxt = __this_n;
 		this->_M_copy_code(__this_n, __ht_n);
 		size_type __bkt = _M_bucket_index(__this_n);
@@ -1181,12 +1193,11 @@ 
 	      __hashtable_base::operator=(std::move(__ht));
 	      _M_element_count = __ht._M_element_count;
 	      _M_rehash_policy = __ht._M_rehash_policy;
-	      __detail::_MoveReuseOrAllocNode<_Key, _Value, _Alloc, _ExtractKey,
-					      _Equal, _H1, _H2, _Hash,
-					      _RehashPolicy, _Traits>
-		__mroan(_M_begin(), *this);
+	      __reuse_or_alloc_node_type __roan(_M_begin(), *this);
 	      _M_before_begin()._M_nxt = nullptr;
-	      _M_assign(__ht, __mroan);
+	      _M_assign(__ht,
+			[&__roan](__node_type* __n)
+			{ return __roan(std::move_if_noexcept(__n->_M_v())); });
 	      __ht.clear();
 	    }
 	  __catch(...)
@@ -1534,11 +1545,13 @@ 
       __node_base* __prev_p = _M_buckets[__n];
       if (!__prev_p)
 	return nullptr;
-      __node_type* __p = static_cast<__node_type*>(__prev_p->_M_nxt);
-      for (;; __p = __p->_M_next())
+
+      for (__node_type* __p = static_cast<__node_type*>(__prev_p->_M_nxt);;
+	   __p = __p->_M_next())
 	{
 	  if (this->_M_equals(__k, __code, __p))
 	    return __prev_p;
+
 	  if (!__p->_M_nxt || _M_bucket_index(__p->_M_next()) != __n)
 	    break;
 	  __prev_p = __p;
@@ -1796,14 +1809,14 @@ 
 	   typename _Alloc, typename _ExtractKey, typename _Equal,
 	   typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
 	   typename _Traits>
-    template<typename _Arg>
+    template<typename _Arg, typename _NodeGenerator>
       std::pair<typename _Hashtable<_Key, _Value, _Alloc,
 				    _ExtractKey, _Equal, _H1,
 				    _H2, _Hash, _RehashPolicy,
 				    _Traits>::iterator, bool>
       _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
 		 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
-      _M_insert(_Arg&& __v, std::true_type)
+      _M_insert(_Arg&& __v, const _NodeGenerator& __node_gen, std::true_type)
       {
 	const key_type& __k = this->_M_extract()(__v);
 	__hash_code __code = this->_M_hash_code(__k);
@@ -1813,7 +1826,7 @@ 
 	if (__n)
 	  return std::make_pair(iterator(__n), false);
 
-	__n = _M_allocate_node(std::forward<_Arg>(__v));
+	__n = __node_gen(std::forward<_Arg>(__v));
 	return std::make_pair(_M_insert_unique_node(__bkt, __code, __n), true);
       }
 
@@ -1822,20 +1835,22 @@ 
 	   typename _Alloc, typename _ExtractKey, typename _Equal,
 	   typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
 	   typename _Traits>
-    template<typename _Arg>
+    template<typename _Arg, typename _NodeGenerator>
       typename _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
 			  _H1, _H2, _Hash, _RehashPolicy,
 			  _Traits>::iterator
       _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
 		 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
-      _M_insert(const_iterator __hint, _Arg&& __v, std::false_type)
+      _M_insert(const_iterator __hint, _Arg&& __v,
+		const _NodeGenerator& __node_gen,
+		std::false_type)
       {
 	// First compute the hash code so that we don't do anything if it
 	// throws.
 	__hash_code __code = this->_M_hash_code(this->_M_extract()(__v));
 
 	// Second allocate new node so that we don't rehash if it throws.
-	__node_type* __node = _M_allocate_node(std::forward<_Arg>(__v));
+	__node_type* __node = __node_gen(std::forward<_Arg>(__v));
 
 	return _M_insert_multi_node(__hint._M_cur, __code, __node);
       }
Index: testsuite/23_containers/unordered_set/not_default_constructible_hash_neg.cc
===================================================================
--- testsuite/23_containers/unordered_set/not_default_constructible_hash_neg.cc	(revision 200571)
+++ testsuite/23_containers/unordered_set/not_default_constructible_hash_neg.cc	(working copy)
@@ -19,7 +19,7 @@ 
 // with this library; see the file COPYING3.  If not see
 // <http://www.gnu.org/licenses/>.
 
-// { dg-error "default constructible" "" { target *-*-* } 271 }
+// { dg-error "default constructible" "" { target *-*-* } 276 }
 
 #include <unordered_set>
 
Index: testsuite/23_containers/unordered_set/instantiation_neg.cc
===================================================================
--- testsuite/23_containers/unordered_set/instantiation_neg.cc	(revision 200571)
+++ testsuite/23_containers/unordered_set/instantiation_neg.cc	(working copy)
@@ -19,7 +19,7 @@ 
 // with this library; see the file COPYING3.  If not see
 // <http://www.gnu.org/licenses/>.
 
-// { dg-error "with noexcept" "" { target *-*-* } 253 }
+// { dg-error "with noexcept" "" { target *-*-* } 258 }
 
 #include <unordered_set>