diff mbox

Rb tree node recycling patch

Message ID 52BDC728.2060309@gmail.com
State New
Headers show

Commit Message

François Dumont Dec. 27, 2013, 6:30 p.m. UTC 
Hi

     Here is a patch to add recycling of Rb tree nodes when possible.

     I replaced the _Rb_tree::_M_move_assign with a move assignment 
operator to benefit from:
- move of elements when the whole data structure cannot be moved
- faster data structure cloning rather than full regeneration of the 
tree when _M_move_assign was failing

     Note that this patch contains also a cleanup of a useless template 
parameter _Is_pod_comparator on _Rb_tree_impl. If you want to apply it 
quickly for 4.9 do not hesitate.

     I haven't done any specific test for this feature, existing ones 
looks good enough to me. If you want me to add some I will when back 
from vacation. I am mostly submitting this patch to show you that I 
worked on it and you do not need to do it yourself.

2013-12-27  François Dumont <fdumont@gcc.gnu.org>

     * include/bits/stl_tree.h (_Rb_tree_reuse_or_alloc_node<>): New.
     (_Rb_tree_alloc_node<>): Likewise.
     (_Rb_tree<>::_M_clone_node): Made template to take a node
     generator.
     (_Rb_tree_impl<>): Remove unused _Is_pod_comparator template
     value.
     (_Rb_tree<>::_M_move_assign): Replace by...
     (_Rb_tree<>::operator(_Rb_tree&&)): ...this.
     (_Rb_tree_impl<>::_M_reset): New.
     (_Rb_tree<>::_M_insert_): Add node generator parameter.
     (_Rb_tree<>::_M_copy): Add overload taking a node generator.
     (_Rb_tree<>::_M_insert_unique_): Add node generator parameter.
     (_Rb_tree<>::_M_insert_equal_): Add node generator parameter.
     (_Rb_tree<>::_M_assign_unique): New.
     (_Rb_tree<>::_M_assign_equal): New.
     (_Rb_tree<>): Adapt to use _Rb_tree_impl<>::_M_reset and reuse
     nodes as much as possible.
     * include/bits/stl_set.h (set<>::operator=(set<>&&): Adapt to use
     _Rb_tree move assignment operator.
     (set<>::operator=(initializer_list<>)): Adapt to use
     _Rb_tree<>::_M_assign_unique.
     * include/bits/stl_multiset.h
     (multiset<>::operator=(multiset<>&&)): Adapt to use
     _Rb_tree move assignment operator.
     (multiset<>::operator=(initializer_list<>)): Adapt to use
     _Rb_tree<>::_M_assign_equal.
     * include/bits/stl_map.h (map<>::operator=(map<>&&): Adapt to use
     _Rb_tree move assignment operator.
     (map<>::operator=(initializer_list<>)): Adapt to use
     _Rb_tree<>::_M_assign_unique.
     * include/bits/stl_multimap.h
     (multimap<>::operator=(multimap<>&&)): Adapt to use
     _Rb_tree move assignment operator.
     (multimap<>::operator=(initializer_list<>)): Adapt to use
     _Rb_tree<>::_M_assign_equal.

Tested under Linux x86_64.

Happy new year.

François

Comments

Christopher Jefferson Jan. 3, 2014, 11:57 a.m. UTC | #1 
Personally, I consider the testing insufficent, although the testing
was already insufficient! Note that this is my opinion, don't assume I
talk for all of libstdc++!

After I broke std::nth_element in 4.8.2 (woops), I am of the view that
the libstdc++ testsuite is defficient -- many code paths are never
tested. The nth_element breakage should really have been picked up,
about 1/3 of all random invocations of nth_element failed!

You could be "inspired" by the code I wrote for algorithms, it is in
testsuite/util/testsuite_containergen.h. The basic idea is I make sure
to generate special cases (size 0 containers, containers containing
only a single value repeated), and then a range of containers of
various different sizes.

I realise suggesting this is probably as much work as your patch, and
you shouldn't assume this is required, but I think it would improve
the testsuite. If you do go down this route, then be sure to reduce
your test's size for simulators. You can look at for example at my new
tests which feature:

// { dg-options "-std=gnu++11" }
// { dg-options "-std=gnu++11 -DSIMULATOR_TEST" { target simulator } }

Which enables the macro SIMULATOR_TEST on simulators, where I do much
less testing (else the tester takes too long.


On 27 December 2013 18:30, François Dumont <frs.dumont@gmail.com> wrote:
> Hi
>
>     Here is a patch to add recycling of Rb tree nodes when possible.
>
>     I replaced the _Rb_tree::_M_move_assign with a move assignment operator
> to benefit from:
> - move of elements when the whole data structure cannot be moved
> - faster data structure cloning rather than full regeneration of the tree
> when _M_move_assign was failing
>
>     Note that this patch contains also a cleanup of a useless template
> parameter _Is_pod_comparator on _Rb_tree_impl. If you want to apply it
> quickly for 4.9 do not hesitate.
>
>     I haven't done any specific test for this feature, existing ones looks
> good enough to me. If you want me to add some I will when back from
> vacation. I am mostly submitting this patch to show you that I worked on it
> and you do not need to do it yourself.
>
> 2013-12-27  François Dumont <fdumont@gcc.gnu.org>
>
>     * include/bits/stl_tree.h (_Rb_tree_reuse_or_alloc_node<>): New.
>     (_Rb_tree_alloc_node<>): Likewise.
>     (_Rb_tree<>::_M_clone_node): Made template to take a node
>     generator.
>     (_Rb_tree_impl<>): Remove unused _Is_pod_comparator template
>     value.
>     (_Rb_tree<>::_M_move_assign): Replace by...
>     (_Rb_tree<>::operator(_Rb_tree&&)): ...this.
>     (_Rb_tree_impl<>::_M_reset): New.
>     (_Rb_tree<>::_M_insert_): Add node generator parameter.
>     (_Rb_tree<>::_M_copy): Add overload taking a node generator.
>     (_Rb_tree<>::_M_insert_unique_): Add node generator parameter.
>     (_Rb_tree<>::_M_insert_equal_): Add node generator parameter.
>     (_Rb_tree<>::_M_assign_unique): New.
>     (_Rb_tree<>::_M_assign_equal): New.
>     (_Rb_tree<>): Adapt to use _Rb_tree_impl<>::_M_reset and reuse
>     nodes as much as possible.
>     * include/bits/stl_set.h (set<>::operator=(set<>&&): Adapt to use
>     _Rb_tree move assignment operator.
>     (set<>::operator=(initializer_list<>)): Adapt to use
>     _Rb_tree<>::_M_assign_unique.
>     * include/bits/stl_multiset.h
>     (multiset<>::operator=(multiset<>&&)): Adapt to use
>     _Rb_tree move assignment operator.
>     (multiset<>::operator=(initializer_list<>)): Adapt to use
>     _Rb_tree<>::_M_assign_equal.
>     * include/bits/stl_map.h (map<>::operator=(map<>&&): Adapt to use
>     _Rb_tree move assignment operator.
>     (map<>::operator=(initializer_list<>)): Adapt to use
>     _Rb_tree<>::_M_assign_unique.
>     * include/bits/stl_multimap.h
>     (multimap<>::operator=(multimap<>&&)): Adapt to use
>     _Rb_tree move assignment operator.
>     (multimap<>::operator=(initializer_list<>)): Adapt to use
>     _Rb_tree<>::_M_assign_equal.
>
> Tested under Linux x86_64.
>
> Happy new year.
>
> François
>
François Dumont Jan. 3, 2014, 6:40 p.m. UTC | #2 
Thanks for your feedback.

     I considered my patch enough tested because it impacts basic 
operations on the Rb tree containers. There are also a number of tests 
that are normally dedicated to exception safety but that has the 
advantage of challenging numerous containers operations in a generic way 
and with some randomness. I have already enhance those tests adding 
checks on memory leaks. It is the biggest issue that could occur with 
this patch. I will add some tests to this framework to cover the newly 
introduced C++11 allocator aware methods.

     To really know how bad or good is the testsuite we should also work 
on test coverage computation but that's a big subject, perhaps for a GSOC...

François


On 01/03/2014 12:57 PM, Christopher Jefferson wrote:
> Personally, I consider the testing insufficent, although the testing
> was already insufficient! Note that this is my opinion, don't assume I
> talk for all of libstdc++!
>
> After I broke std::nth_element in 4.8.2 (woops), I am of the view that
> the libstdc++ testsuite is defficient -- many code paths are never
> tested. The nth_element breakage should really have been picked up,
> about 1/3 of all random invocations of nth_element failed!
>
> You could be "inspired" by the code I wrote for algorithms, it is in
> testsuite/util/testsuite_containergen.h. The basic idea is I make sure
> to generate special cases (size 0 containers, containers containing
> only a single value repeated), and then a range of containers of
> various different sizes.
>
> I realise suggesting this is probably as much work as your patch, and
> you shouldn't assume this is required, but I think it would improve
> the testsuite. If you do go down this route, then be sure to reduce
> your test's size for simulators. You can look at for example at my new
> tests which feature:
>
> // { dg-options "-std=gnu++11" }
> // { dg-options "-std=gnu++11 -DSIMULATOR_TEST" { target simulator } }
>
> Which enables the macro SIMULATOR_TEST on simulators, where I do much
> less testing (else the tester takes too long.
>
>
> On 27 December 2013 18:30, François Dumont <frs.dumont@gmail.com> wrote:
>> Hi
>>
>>      Here is a patch to add recycling of Rb tree nodes when possible.
>>
>>      I replaced the _Rb_tree::_M_move_assign with a move assignment operator
>> to benefit from:
>> - move of elements when the whole data structure cannot be moved
>> - faster data structure cloning rather than full regeneration of the tree
>> when _M_move_assign was failing
>>
>>      Note that this patch contains also a cleanup of a useless template
>> parameter _Is_pod_comparator on _Rb_tree_impl. If you want to apply it
>> quickly for 4.9 do not hesitate.
>>
>>      I haven't done any specific test for this feature, existing ones looks
>> good enough to me. If you want me to add some I will when back from
>> vacation. I am mostly submitting this patch to show you that I worked on it
>> and you do not need to do it yourself.
>>
>> 2013-12-27  François Dumont <fdumont@gcc.gnu.org>
>>
>>      * include/bits/stl_tree.h (_Rb_tree_reuse_or_alloc_node<>): New.
>>      (_Rb_tree_alloc_node<>): Likewise.
>>      (_Rb_tree<>::_M_clone_node): Made template to take a node
>>      generator.
>>      (_Rb_tree_impl<>): Remove unused _Is_pod_comparator template
>>      value.
>>      (_Rb_tree<>::_M_move_assign): Replace by...
>>      (_Rb_tree<>::operator(_Rb_tree&&)): ...this.
>>      (_Rb_tree_impl<>::_M_reset): New.
>>      (_Rb_tree<>::_M_insert_): Add node generator parameter.
>>      (_Rb_tree<>::_M_copy): Add overload taking a node generator.
>>      (_Rb_tree<>::_M_insert_unique_): Add node generator parameter.
>>      (_Rb_tree<>::_M_insert_equal_): Add node generator parameter.
>>      (_Rb_tree<>::_M_assign_unique): New.
>>      (_Rb_tree<>::_M_assign_equal): New.
>>      (_Rb_tree<>): Adapt to use _Rb_tree_impl<>::_M_reset and reuse
>>      nodes as much as possible.
>>      * include/bits/stl_set.h (set<>::operator=(set<>&&): Adapt to use
>>      _Rb_tree move assignment operator.
>>      (set<>::operator=(initializer_list<>)): Adapt to use
>>      _Rb_tree<>::_M_assign_unique.
>>      * include/bits/stl_multiset.h
>>      (multiset<>::operator=(multiset<>&&)): Adapt to use
>>      _Rb_tree move assignment operator.
>>      (multiset<>::operator=(initializer_list<>)): Adapt to use
>>      _Rb_tree<>::_M_assign_equal.
>>      * include/bits/stl_map.h (map<>::operator=(map<>&&): Adapt to use
>>      _Rb_tree move assignment operator.
>>      (map<>::operator=(initializer_list<>)): Adapt to use
>>      _Rb_tree<>::_M_assign_unique.
>>      * include/bits/stl_multimap.h
>>      (multimap<>::operator=(multimap<>&&)): Adapt to use
>>      _Rb_tree move assignment operator.
>>      (multimap<>::operator=(initializer_list<>)): Adapt to use
>>      _Rb_tree<>::_M_assign_equal.
>>
>> Tested under Linux x86_64.
>>
>> Happy new year.
>>
>> François
>>
Jonathan Wakely Jan. 8, 2014, 11:58 a.m. UTC | #3 
On 27 December 2013 18:30, François Dumont wrote:
> Hi
>
>     Here is a patch to add recycling of Rb tree nodes when possible.

The change looks good, but it is not a bug fix, so I don't think it's
suitable for Stage 3.  Please re-submit this after 4.9 is released
when we are in Stage 1 again, thanks.
Paolo Carlini Jan. 8, 2014, 1:34 p.m. UTC | #4 
Hi,

On 12/27/2013 07:30 PM, François Dumont wrote:
> Note that this patch contains also a cleanup of a useless template 
> parameter _Is_pod_comparator on _Rb_tree_impl.
The useless parameter is a remnant of an attempt at exploiting the EBO 
for _Rb_tree_impl. At some point Benjamin got a patch from a contributor 
but then had to quickly revert it just in time for the ABI freeze 
because it didn't work. Evrything is recorded in the mailing list. 
Anyway, whatever we do now (more exactly, post 4.9) let's make sure we 
don't break the ABI inadvertently, or, if we actually decide do that, we 
should reconsider the EBO.

About the node recycling idea itself, we got a closely related Bugzilla. 
Is it *exactly* the same issue, or not? Please double check.

Paolo.
Paolo Carlini Jan. 8, 2014, 1:54 p.m. UTC | #5 
On 01/08/2014 02:34 PM, Paolo Carlini wrote:
> Hi,
>
> On 12/27/2013 07:30 PM, François Dumont wrote:
>> Note that this patch contains also a cleanup of a useless template 
>> parameter _Is_pod_comparator on _Rb_tree_impl.
> The useless parameter is a remnant of an attempt at exploiting the EBO 
> for _Rb_tree_impl. At some point Benjamin got a patch from a 
> contributor but then had to quickly revert it just in time for the ABI 
> freeze because it didn't work. Evrything is recorded in the mailing 
> list. Anyway, whatever we do now (more exactly, post 4.9) let's make 
> sure we don't break the ABI inadvertently, or, if we actually decide 
> do that, we should reconsider the EBO.

This ChangeLog entry:

2004-03-25  Dhruv Matani  <dhruvbird@gmx.net>

    * include/bits/stl_tree.h: Introduced a new class _Rb_tree_impl, ...

has the original EBO idea, which in fact we didn't deliver.

Paolo.
François Dumont Jan. 9, 2014, 9:59 p.m. UTC | #6 
On 01/08/2014 02:34 PM, Paolo Carlini wrote:
> Hi,
>
> On 12/27/2013 07:30 PM, François Dumont wrote:
>> Note that this patch contains also a cleanup of a useless template 
>> parameter _Is_pod_comparator on _Rb_tree_impl.
> The useless parameter is a remnant of an attempt at exploiting the EBO 
> for _Rb_tree_impl. At some point Benjamin got a patch from a 
> contributor but then had to quickly revert it just in time for the ABI 
> freeze because it didn't work. Evrything is recorded in the mailing 
> list. Anyway, whatever we do now (more exactly, post 4.9) let's make 
> sure we don't break the ABI inadvertently, or, if we actually decide 
> do that, we should reconsider the EBO.
>
> About the node recycling idea itself, we got a closely related 
> Bugzilla. Is it *exactly* the same issue, or not? Please double check.
>
> Paolo.
> .
>
Could you point me to the bugzilla entry you are mentioning ?

François
Paolo Carlini Jan. 9, 2014, 10:37 p.m. UTC | #7 
Hi

> Could you point me to the bugzilla entry you are mentioning ?

libstdc++/29988

Thanks,
Paolo
diff mbox

Patch

Index: include/bits/stl_set.h
===================================================================
--- include/bits/stl_set.h	(revision 206214)
+++ include/bits/stl_set.h	(working copy)
@@ -277,15 +277,7 @@ 
       set&
       operator=(set&& __x) noexcept(_Alloc_traits::_S_nothrow_move())
       {
-	if (!_M_t._M_move_assign(__x._M_t))
-	  {
-	    // The rvalue's allocator cannot be moved and is not equal,
-	    // so we need to individually move each element.
-	    clear();
-	    insert(std::__make_move_if_noexcept_iterator(__x._M_t.begin()),
-		   std::__make_move_if_noexcept_iterator(__x._M_t.end()));
-	    __x.clear();
-	  }
+	_M_t = std::move(__x._M_t);
       	return *this;
       }
 
@@ -303,8 +295,7 @@ 
       set&
       operator=(initializer_list<value_type> __l)
       {
-	this->clear();
-	this->insert(__l.begin(), __l.end());
+	_M_t._M_assign_unique(__l.begin(), __l.end());
 	return *this;
       }
 #endif
Index: include/bits/stl_multiset.h
===================================================================
--- include/bits/stl_multiset.h	(revision 206214)
+++ include/bits/stl_multiset.h	(working copy)
@@ -274,15 +274,7 @@ 
       multiset&
       operator=(multiset&& __x) noexcept(_Alloc_traits::_S_nothrow_move())
       {
-	if (!_M_t._M_move_assign(__x._M_t))
-	  {
-	    // The rvalue's allocator cannot be moved and is not equal,
-	    // so we need to individually move each element.
-	    clear();
-	    insert(std::__make_move_if_noexcept_iterator(__x._M_t.begin()),
-		   std::__make_move_if_noexcept_iterator(__x._M_t.end()));
-	    __x.clear();
-	  }
+	_M_t = std::move(__x._M_t);
 	return *this;
       }
 
@@ -300,8 +292,7 @@ 
       multiset&
       operator=(initializer_list<value_type> __l)
       {
-	this->clear();
-	this->insert(__l.begin(), __l.end());
+	_M_t._M_assign_equal(__l.begin(), __l.end());
 	return *this;
       }
 #endif
Index: include/bits/stl_map.h
===================================================================
--- include/bits/stl_map.h	(revision 206214)
+++ include/bits/stl_map.h	(working copy)
@@ -307,15 +307,7 @@ 
       map&
       operator=(map&& __x) noexcept(_Alloc_traits::_S_nothrow_move())
       {
-	if (!_M_t._M_move_assign(__x._M_t))
-	  {
-	    // The rvalue's allocator cannot be moved and is not equal,
-	    // so we need to individually move each element.
-	    clear();
-	    insert(std::__make_move_if_noexcept_iterator(__x.begin()),
-		   std::__make_move_if_noexcept_iterator(__x.end()));
-	    __x.clear();
-	  }
+	_M_t = std::move(__x._M_t);
 	return *this;
       }
 
@@ -333,8 +325,7 @@ 
       map&
       operator=(initializer_list<value_type> __l)
       {
-	this->clear();
-	this->insert(__l.begin(), __l.end());
+	_M_t._M_assign_unique(__l.begin(), __l.end());
 	return *this;
       }
 #endif
Index: include/bits/stl_multimap.h
===================================================================
--- include/bits/stl_multimap.h	(revision 206214)
+++ include/bits/stl_multimap.h	(working copy)
@@ -301,15 +301,7 @@ 
       multimap&
       operator=(multimap&& __x) noexcept(_Alloc_traits::_S_nothrow_move())
       {
-	if (!_M_t._M_move_assign(__x._M_t))
-	  {
-	    // The rvalue's allocator cannot be moved and is not equal,
-	    // so we need to individually move each element.
-	    clear();
-	    insert(std::__make_move_if_noexcept_iterator(__x.begin()),
-		   std::__make_move_if_noexcept_iterator(__x.end()));
-	    __x.clear();
-	  }
+	_M_t = std::move(__x._M_t);
 	return *this;
       }
 
@@ -327,8 +319,7 @@ 
       multimap&
       operator=(initializer_list<value_type> __l)
       {
-	this->clear();
-	this->insert(__l.begin(), __l.end());
+	_M_t._M_assign_equal(__l.begin(), __l.end());
 	return *this;
       }
 #endif
Index: include/bits/stl_tree.h
===================================================================
--- include/bits/stl_tree.h	(revision 206214)
+++ include/bits/stl_tree.h	(working copy)
@@ -330,6 +330,110 @@ 
                const _Rb_tree_const_iterator<_Val>& __y) _GLIBCXX_NOEXCEPT
     { return __x._M_node != __y._M_node; }
 
+  // Functor recycling a pool of nodes and using allocation once the pool is
+  // empty.
+  template<typename _RbTree>
+    struct _Rb_tree_reuse_or_alloc_node
+    {
+    private:
+      typedef _RbTree __rb_tree;
+      typedef _Rb_tree_node<typename _RbTree::value_type> __node_type;
+
+    public:
+      _Rb_tree_reuse_or_alloc_node(const _Rb_tree_node_base& __header,
+				   __rb_tree& __t)
+	: _M_root(__header._M_parent), _M_nodes(__header._M_right), _M_t(__t)
+      {
+	if (_M_root)
+	  _M_root->_M_parent = 0;
+	else
+	  _M_nodes = 0;
+      }
+
+      ~_Rb_tree_reuse_or_alloc_node()
+      { _M_t._M_erase(static_cast<__node_type*>(_M_root)); }
+
+      template<typename _Arg>
+	__node_type*
+#if __cplusplus < 201103L
+	operator()(const _Arg& __arg) const
+#else
+	operator()(_Arg&& __arg) const
+#endif
+	{
+	  __node_type* __node = static_cast<__node_type*>(_M_extract());
+	  if (__node)
+	    {
+	      _M_t._M_destroy_node(__node);
+	      _M_t._M_construct_node(__node, _GLIBCXX_FORWARD(_Arg, __arg));
+	      return __node;
+	    }
+	  return _M_t._M_create_node(_GLIBCXX_FORWARD(_Arg, __arg));
+	}
+
+    private:
+      typedef _Rb_tree_node_base __node_base;
+
+      __node_base*
+      _M_extract() const
+      {
+	if (!_M_nodes)
+	  return _M_nodes;
+
+	__node_base* __node = _M_nodes;
+	_M_nodes = _M_nodes->_M_parent;
+	if (_M_nodes)
+	  {
+	    if (_M_nodes->_M_right == __node)
+	      {
+		_M_nodes->_M_right = 0;
+
+		if (_M_nodes->_M_left)
+		  {
+		    _M_nodes = _M_nodes->_M_left;
+
+		    while (_M_nodes->_M_right)
+		      _M_nodes = _M_nodes->_M_right;
+		  }
+	      }
+	    else // __node is on the left.
+	      _M_nodes->_M_left = 0;
+	  }
+	else
+	  _M_root = 0;
+
+	return __node;
+      }
+
+      mutable __node_base* _M_root;
+      mutable __node_base* _M_nodes;
+      _RbTree& _M_t;
+    };
+
+  // Functor similar to the previous one but without any pool of node to recycle.
+  template<typename _RbTree>
+    struct _Rb_tree_alloc_node
+    {
+    private:
+      typedef _Rb_tree_node<typename _RbTree::value_type> __node_type;
+
+    public:
+      _Rb_tree_alloc_node(_RbTree& __t)
+	: _M_t(__t) { }
+
+      template<typename _Arg>
+	__node_type*
+#if __cplusplus < 201103L
+	operator()(const _Arg& __arg) const
+#else
+	operator()(_Arg&& __arg) const
+#endif
+	{ return _M_t._M_create_node(_GLIBCXX_FORWARD(_Arg, __arg)); }
+
+    private:
+      _RbTree& _M_t;
+    };
+
   void
   _Rb_tree_insert_and_rebalance(const bool __insert_left,
                                 _Rb_tree_node_base* __x,
@@ -349,6 +453,12 @@ 
         rebind<_Rb_tree_node<_Val> >::other _Node_allocator;
 
       typedef __gnu_cxx::__alloc_traits<_Node_allocator> _Alloc_traits;
+      template<typename _RT>
+	friend struct _Rb_tree_alloc_node;
+      typedef _Rb_tree_alloc_node<_Rb_tree> __alloc_node_t;
+      template<typename _RT>
+	friend struct _Rb_tree_reuse_or_alloc_node;
+      typedef _Rb_tree_reuse_or_alloc_node<_Rb_tree> __reuse_or_alloc_node_t;
 
     protected:
       typedef _Rb_tree_node_base* 		_Base_ptr;
@@ -389,44 +499,55 @@ 
       { _Alloc_traits::deallocate(_M_get_Node_allocator(), __p, 1); }
 
 #if __cplusplus < 201103L
-      _Link_type
-      _M_create_node(const value_type& __x)
+      void
+      _M_construct_node(_Link_type __node, const value_type& __x)
       {
-	_Link_type __tmp = _M_get_node();
 	__try
-	  { get_allocator().construct(__tmp->_M_valptr(), __x); }
+	  { get_allocator().construct(__node->_M_valptr(), __x); }
 	__catch(...)
 	  {
-	    _M_put_node(__tmp);
+	    _M_put_node(__node);
 	    __throw_exception_again;
 	  }
+      }
+
+      _Link_type
+      _M_create_node(const value_type& __x)
+      {
+	_Link_type __tmp = _M_get_node();
+	_M_construct_node(__tmp, __x);
 	return __tmp;
       }
 
       void
       _M_destroy_node(_Link_type __p)
-      {
-	get_allocator().destroy(__p->_M_valptr());
-	_M_put_node(__p);
-      }
+      { get_allocator().destroy(__p->_M_valptr()); }
 #else
       template<typename... _Args>
-        _Link_type
-        _M_create_node(_Args&&... __args)
+	void
+	_M_construct_node(_Link_type __node, _Args&&... __args)
 	{
-	  _Link_type __tmp = _M_get_node();
 	  __try
 	    {
-	      ::new(__tmp) _Rb_tree_node<_Val>;
+	      ::new(__node) _Rb_tree_node<_Val>();
 	      _Alloc_traits::construct(_M_get_Node_allocator(),
-				       __tmp->_M_valptr(),
+				       __node->_M_valptr(),
 				       std::forward<_Args>(__args)...);
 	    }
 	  __catch(...)
 	    {
-	      _M_put_node(__tmp);
+	      __node->~_Rb_tree_node<_Val>();
+	      _M_put_node(__node);
 	      __throw_exception_again;
 	    }
+	}
+
+      template<typename... _Args>
+        _Link_type
+        _M_create_node(_Args&&... __args)
+	{
+	  _Link_type __tmp = _M_get_node();
+	  _M_construct_node(__tmp, std::forward<_Args>(__args)...);
 	  return __tmp;
 	}
 
@@ -435,23 +556,29 @@ 
       {
 	_Alloc_traits::destroy(_M_get_Node_allocator(), __p->_M_valptr());
 	__p->~_Rb_tree_node<_Val>();
-	_M_put_node(__p);
       }
 #endif
 
-      _Link_type
-      _M_clone_node(_Const_Link_type __x)
+      void
+      _M_drop_node(_Link_type __p) _GLIBCXX_NOEXCEPT
       {
-	_Link_type __tmp = _M_create_node(*__x->_M_valptr());
-	__tmp->_M_color = __x->_M_color;
-	__tmp->_M_left = 0;
-	__tmp->_M_right = 0;
-	return __tmp;
+	_M_destroy_node(__p);
+	_M_put_node(__p);
       }
 
+      template<typename _NodeGen>
+	_Link_type
+	_M_clone_node(_Link_type __x, const _NodeGen& __node_gen)
+	{
+	  _Link_type __tmp = __node_gen(*__x->_M_valptr());
+	  __tmp->_M_color = __x->_M_color;
+	  __tmp->_M_left = 0;
+	  __tmp->_M_right = 0;
+	  return __tmp;
+	}
+
     protected:
-      template<typename _Key_compare, 
-	       bool _Is_pod_comparator = __is_pod(_Key_compare)>
+      template<typename _Key_compare>
         struct _Rb_tree_impl : public _Node_allocator
         {
 	  _Key_compare		_M_key_compare;
@@ -475,6 +602,15 @@ 
 	  { _M_initialize(); }
 #endif
 
+	  void
+	  _M_reset()
+	  {
+	    this->_M_header._M_parent = 0;
+	    this->_M_header._M_left = &this->_M_header;
+	    this->_M_header._M_right = &this->_M_header;
+	    this->_M_node_count = 0;
+	  }
+
 	private:
 	  void
 	  _M_initialize()
@@ -514,11 +650,11 @@ 
       { return this->_M_impl._M_header._M_right; }
 
       _Link_type
-      _M_begin() _GLIBCXX_NOEXCEPT
+      _M_begin() const _GLIBCXX_NOEXCEPT
       { return static_cast<_Link_type>(this->_M_impl._M_header._M_parent); }
 
       _Const_Link_type
-      _M_begin() const _GLIBCXX_NOEXCEPT
+      _M_cbegin() const _GLIBCXX_NOEXCEPT
       {
 	return static_cast<_Const_Link_type>
 	  (this->_M_impl._M_header._M_parent);
@@ -529,7 +665,7 @@ 
       { return static_cast<_Link_type>(&this->_M_impl._M_header); }
 
       _Const_Link_type
-      _M_end() const _GLIBCXX_NOEXCEPT
+      _M_cend() const _GLIBCXX_NOEXCEPT
       { return static_cast<_Const_Link_type>(&this->_M_impl._M_header); }
 
       static const_reference
@@ -603,9 +739,9 @@ 
 				   const key_type& __k);
 
 #if __cplusplus >= 201103L
-      template<typename _Arg>
+      template<typename _Arg, typename _NodeGen>
         iterator
-        _M_insert_(_Base_ptr __x, _Base_ptr __y, _Arg&& __v);
+	_M_insert_(_Base_ptr __x, _Base_ptr __y, _Arg&& __v, const _NodeGen&);
 
       iterator
       _M_insert_node(_Base_ptr __x, _Base_ptr __y, _Link_type __z);
@@ -624,9 +760,10 @@ 
       iterator
       _M_insert_equal_lower_node(_Link_type __z);
 #else
-      iterator
-      _M_insert_(_Base_ptr __x, _Base_ptr __y,
-		 const value_type& __v);
+      template<typename _NodeGen>
+	iterator
+	_M_insert_(_Base_ptr __x, _Base_ptr __y,
+		   const value_type& __v, const _NodeGen&);
 
       // _GLIBCXX_RESOLVE_LIB_DEFECTS
       // 233. Insertion hints in associative containers.
@@ -637,8 +774,13 @@ 
       _M_insert_equal_lower(const value_type& __x);
 #endif
 
+      template<typename _NodeGen>
+	_Link_type
+	_M_copy(_Link_type __x, _Link_type __p, const _NodeGen&);
+
       _Link_type
-      _M_copy(_Const_Link_type __x, _Link_type __p);
+      _M_copy(_Link_type __x, _Link_type __p)
+      { return _M_copy(__x, __p, __alloc_node_t(*this)); }
 
       void
       _M_erase(_Link_type __x);
@@ -688,7 +830,7 @@ 
       _Rb_tree(const _Rb_tree& __x, const allocator_type& __a)
       : _M_impl(__x._M_impl._M_key_compare, _Node_allocator(__a))
       {
-	if (__x._M_root() != 0)
+	if (__x._M_root() != nullptr)
 	  {
 	    _M_root() = _M_copy(__x._M_begin(), _M_end());
 	    _M_leftmost() = _S_minimum(_M_root());
@@ -789,14 +931,30 @@ 
         iterator
         _M_insert_equal(_Arg&& __x);
 
-      template<typename _Arg>
+      template<typename _Arg, typename _NodeGen>
         iterator
-        _M_insert_unique_(const_iterator __position, _Arg&& __x);
+	_M_insert_unique_(const_iterator __pos, _Arg&& __x, const _NodeGen&);
 
       template<typename _Arg>
-        iterator
-        _M_insert_equal_(const_iterator __position, _Arg&& __x);
+	iterator
+	_M_insert_unique_(const_iterator __pos, _Arg&& __x)
+	{
+	  return _M_insert_unique_(__pos, std::forward<_Arg>(__x),
+				   __alloc_node_t(*this));
+	}
 
+      template<typename _Arg, typename _NodeGen>
+	iterator
+	_M_insert_equal_(const_iterator __pos, _Arg&& __x, const _NodeGen&);
+
+      template<typename _Arg>
+	iterator
+	_M_insert_equal_(const_iterator __pos, _Arg&& __x)
+	{
+	  return _M_insert_equal_(__pos, std::forward<_Arg>(__x),
+				  __alloc_node_t(*this));
+	}
+
       template<typename... _Args>
 	pair<iterator, bool>
 	_M_emplace_unique(_Args&&... __args);
@@ -819,11 +977,22 @@ 
       iterator
       _M_insert_equal(const value_type& __x);
 
+      template<typename _NodeGen>
+	iterator
+	_M_insert_unique_(const_iterator __pos, const value_type& __x,
+			  const _NodeGen&);
+
       iterator
-      _M_insert_unique_(const_iterator __position, const value_type& __x);
+      _M_insert_unique_(const_iterator __pos, const value_type& __x)
+      { return _M_insert_unique_(__pos, __x, __alloc_node_t(*this)); }
 
+      template<typename _NodeGen>
+	iterator
+	_M_insert_equal_(const_iterator __pos, const value_type& __x,
+			 const _NodeGen&);
       iterator
-      _M_insert_equal_(const_iterator __position, const value_type& __x);
+      _M_insert_equal_(const_iterator __pos, const value_type& __x)
+      { return _M_insert_equal_(__pos, __x, __alloc_node_t(*this)); }
 #endif
 
       template<typename _InputIterator>
@@ -903,10 +1072,7 @@ 
       clear() _GLIBCXX_NOEXCEPT
       {
         _M_erase(_M_begin());
-        _M_leftmost() = _M_end();
-        _M_root() = 0;
-        _M_rightmost() = _M_end();
-        _M_impl._M_node_count = 0;
+	_M_impl._M_reset();
       }
 
       // Set operations.
@@ -925,7 +1091,7 @@ 
 
       const_iterator
       lower_bound(const key_type& __k) const
-      { return _M_lower_bound(_M_begin(), _M_end(), __k); }
+      { return _M_lower_bound(_M_cbegin(), _M_cend(), __k); }
 
       iterator
       upper_bound(const key_type& __k)
@@ -933,7 +1099,7 @@ 
 
       const_iterator
       upper_bound(const key_type& __k) const
-      { return _M_upper_bound(_M_begin(), _M_end(), __k); }
+      { return _M_upper_bound(_M_cbegin(), _M_cend(), __k); }
 
       pair<iterator, iterator>
       equal_range(const key_type& __k);
@@ -946,8 +1112,16 @@ 
       __rb_verify() const;
 
 #if __cplusplus >= 201103L
-      bool
-      _M_move_assign(_Rb_tree&);
+      _Rb_tree&
+      operator=(_Rb_tree&&) noexcept(_Alloc_traits::_S_nothrow_move());
+
+      template<typename _Iterator>
+	void
+	_M_assign_unique(_Iterator, _Iterator);
+
+      template<typename _Iterator>
+	void
+	_M_assign_equal(_Iterator, _Iterator);
 #endif
     };
 
@@ -1013,12 +1187,15 @@ 
     _Rb_tree(_Rb_tree&& __x, _Node_allocator&& __a)
     : _M_impl(__x._M_impl._M_key_compare, std::move(__a))
     {
-      if (__x._M_root() != 0)
+      if (__x._M_root() != nullptr)
 	{
 	  if (!_Alloc_traits::_S_always_equal()
 	      && __x._M_get_Node_allocator() != __a)
 	    {
-	      _M_root() = _M_copy(__x._M_begin(), _M_end());
+	      __alloc_node_t __an(*this);
+	      _M_root() = _M_copy(__x._M_begin(), _M_end(),
+				  [&__an](value_type& __val)
+				  { return __an(std::move_if_noexcept(__val)); });
 	      _M_leftmost() = _S_minimum(_M_root());
 	      _M_rightmost() = _S_maximum(_M_root());
 	      _M_impl._M_node_count = __x._M_impl._M_node_count;
@@ -1029,49 +1206,83 @@ 
 	      _M_leftmost() = __x._M_leftmost();
 	      _M_rightmost() = __x._M_rightmost();
 	      _M_root()->_M_parent = _M_end();
+	      this->_M_impl._M_node_count = __x._M_impl._M_node_count;
 
-	      __x._M_root() = 0;
-	      __x._M_leftmost() = __x._M_end();
-	      __x._M_rightmost() = __x._M_end();
-
-	      this->_M_impl._M_node_count = __x._M_impl._M_node_count;
-	      __x._M_impl._M_node_count = 0;
+	      __x._M_impl._M_reset();
 	    }
 	}
     }
 
   template<typename _Key, typename _Val, typename _KeyOfValue,
            typename _Compare, typename _Alloc>
-    bool
+    _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>&
     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
-    _M_move_assign(_Rb_tree& __x)
+    operator=(_Rb_tree&& __x)
+    noexcept(_Alloc_traits::_S_nothrow_move())
     {
       if (_Alloc_traits::_S_propagate_on_move_assign()
 	  || _Alloc_traits::_S_always_equal()
 	  || _M_get_Node_allocator() == __x._M_get_Node_allocator())
 	{
 	  clear();
-	  if (__x._M_root() != 0)
+	  if (__x._M_root() != nullptr)
 	    {
 	      _M_root() = __x._M_root();
 	      _M_leftmost() = __x._M_leftmost();
 	      _M_rightmost() = __x._M_rightmost();
 	      _M_root()->_M_parent = _M_end();
+	      this->_M_impl._M_node_count = __x._M_impl._M_node_count;
 
-	      __x._M_root() = 0;
-	      __x._M_leftmost() = __x._M_end();
-	      __x._M_rightmost() = __x._M_end();
-
-	      this->_M_impl._M_node_count = __x._M_impl._M_node_count;
-	      __x._M_impl._M_node_count = 0;
+	      __x._M_impl._M_reset();
 	    }
 	  if (_Alloc_traits::_S_propagate_on_move_assign())
 	    std::__alloc_on_move(_M_get_Node_allocator(),
 				 __x._M_get_Node_allocator());
-	  return true;
+	  return *this;
 	}
-      return false;
+
+      // Try to move each node reusing existing nodes and copying __x nodes
+      // structure.
+      __reuse_or_alloc_node_t __roan(this->_M_impl._M_header, *this);
+      _M_impl._M_reset();
+      if (__x._M_root() != nullptr)
+	{
+	  _M_root() = _M_copy(__x._M_begin(), _M_end(),
+			      [&__roan](value_type& __val)
+			      { return __roan(std::move_if_noexcept(__val)); });
+	  _M_leftmost() = _S_minimum(_M_root());
+	  _M_rightmost() = _S_maximum(_M_root());
+	  _M_impl._M_node_count = __x._M_impl._M_node_count;
+	  __x.clear();
+	}
+      return *this;
     }
+
+  template<typename _Key, typename _Val, typename _KeyOfValue,
+           typename _Compare, typename _Alloc>
+    template<typename _Iterator>
+      void
+      _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
+      _M_assign_unique(_Iterator __first, _Iterator __last)
+      {
+	__reuse_or_alloc_node_t __roan(this->_M_impl._M_header, *this);
+	_M_impl._M_reset();
+	for (; __first != __last; ++__first)
+	  _M_insert_unique_(end(), *__first, __roan);
+      }
+
+  template<typename _Key, typename _Val, typename _KeyOfValue,
+           typename _Compare, typename _Alloc>
+    template<typename _Iterator>
+      void
+      _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
+      _M_assign_equal(_Iterator __first, _Iterator __last)
+      {
+	__reuse_or_alloc_node_t __roan(this->_M_impl._M_header, *this);
+	_M_impl._M_reset();
+	for (; __first != __last; ++__first)
+	  _M_insert_equal_(end(), *__first, __roan);
+      }
 #endif
 
   template<typename _Key, typename _Val, typename _KeyOfValue,
@@ -1083,7 +1294,6 @@ 
       if (this != &__x)
 	{
 	  // Note that _Key may be a constant type.
-	  clear();
 #if __cplusplus >= 201103L
 	  if (_Alloc_traits::_S_propagate_on_copy_assign())
 	    {
@@ -1092,14 +1302,19 @@ 
 	      if (!_Alloc_traits::_S_always_equal()
 		  && __this_alloc != __that_alloc)
 		{
+		  // Replacement allocator cannot free existing storage, we need
+		  // to erase nodes first.
+		  clear();
 		  std::__alloc_on_copy(__this_alloc, __that_alloc);
 		}
 	    }
 #endif
+	__reuse_or_alloc_node_t __roan(this->_M_impl._M_header, *this);
+	  _M_impl._M_reset();
 	  _M_impl._M_key_compare = __x._M_impl._M_key_compare;
 	  if (__x._M_root() != 0)
 	    {
-	      _M_root() = _M_copy(__x._M_begin(), _M_end());
+	      _M_root() = _M_copy(__x._M_begin(), _M_end(), __roan);
 	      _M_leftmost() = _S_minimum(_M_root());
 	      _M_rightmost() = _S_maximum(_M_root());
 	      _M_impl._M_node_count = __x._M_impl._M_node_count;
@@ -1111,27 +1326,31 @@ 
   template<typename _Key, typename _Val, typename _KeyOfValue,
            typename _Compare, typename _Alloc>
 #if __cplusplus >= 201103L
-    template<typename _Arg>
+    template<typename _Arg, typename _NodeGen>
+#else
+    template<typename _NodeGen>
 #endif
-    typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
-    _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
+      typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
+      _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
+      _M_insert_(_Base_ptr __x, _Base_ptr __p,
 #if __cplusplus >= 201103L
-    _M_insert_(_Base_ptr __x, _Base_ptr __p, _Arg&& __v)
+		 _Arg&& __v,
 #else
-    _M_insert_(_Base_ptr __x, _Base_ptr __p, const _Val& __v)
+		 const _Val& __v,
 #endif
-    {
-      bool __insert_left = (__x != 0 || __p == _M_end()
-			    || _M_impl._M_key_compare(_KeyOfValue()(__v),
-						      _S_key(__p)));
+		 const _NodeGen& __node_gen)
+      {
+	bool __insert_left = (__x != 0 || __p == _M_end()
+			      || _M_impl._M_key_compare(_KeyOfValue()(__v),
+							_S_key(__p)));
 
-      _Link_type __z = _M_create_node(_GLIBCXX_FORWARD(_Arg, __v));
+	_Link_type __z = __node_gen(_GLIBCXX_FORWARD(_Arg, __v));
 
-      _Rb_tree_insert_and_rebalance(__insert_left, __z, __p,
-				    this->_M_impl._M_header);
-      ++_M_impl._M_node_count;
-      return iterator(__z);
-    }
+	_Rb_tree_insert_and_rebalance(__insert_left, __z, __p,
+				      this->_M_impl._M_header);
+	++_M_impl._M_node_count;
+	return iterator(__z);
+      }
 
   template<typename _Key, typename _Val, typename _KeyOfValue,
            typename _Compare, typename _Alloc>
@@ -1183,40 +1402,41 @@ 
     }
 
   template<typename _Key, typename _Val, typename _KoV,
-           typename _Compare, typename _Alloc>
-    typename _Rb_tree<_Key, _Val, _KoV, _Compare, _Alloc>::_Link_type
-    _Rb_tree<_Key, _Val, _KoV, _Compare, _Alloc>::
-    _M_copy(_Const_Link_type __x, _Link_type __p)
-    {
-      // Structural copy.  __x and __p must be non-null.
-      _Link_type __top = _M_clone_node(__x);
-      __top->_M_parent = __p;
+	   typename _Compare, typename _Alloc>
+    template<typename _NodeGen>
+      typename _Rb_tree<_Key, _Val, _KoV, _Compare, _Alloc>::_Link_type
+      _Rb_tree<_Key, _Val, _KoV, _Compare, _Alloc>::
+      _M_copy(_Link_type __x, _Link_type __p, const _NodeGen& __node_gen)
+      {
+	// Structural copy. __x and __p must be non-null.
+	_Link_type __top = _M_clone_node(__x, __node_gen);
+	__top->_M_parent = __p;
 
-      __try
-	{
-	  if (__x->_M_right)
-	    __top->_M_right = _M_copy(_S_right(__x), __top);
-	  __p = __top;
-	  __x = _S_left(__x);
+	__try
+	  {
+	    if (__x->_M_right)
+	      __top->_M_right = _M_copy(_S_right(__x), __top, __node_gen);
+	    __p = __top;
+	    __x = _S_left(__x);
 
-	  while (__x != 0)
-	    {
-	      _Link_type __y = _M_clone_node(__x);
-	      __p->_M_left = __y;
-	      __y->_M_parent = __p;
-	      if (__x->_M_right)
-		__y->_M_right = _M_copy(_S_right(__x), __y);
-	      __p = __y;
-	      __x = _S_left(__x);
-	    }
-	}
-      __catch(...)
-	{
-	  _M_erase(__top);
-	  __throw_exception_again;
-	}
-      return __top;
-    }
+	    while (__x != 0)
+	      {
+		_Link_type __y = _M_clone_node(__x, __node_gen);
+		__p->_M_left = __y;
+		__y->_M_parent = __p;
+		if (__x->_M_right)
+		  __y->_M_right = _M_copy(_S_right(__x), __y, __node_gen);
+		__p = __y;
+		__x = _S_left(__x);
+	      }
+	  }
+	__catch(...)
+	  {
+	    _M_erase(__top);
+	    __throw_exception_again;
+	  }
+	return __top;
+      }
 
   template<typename _Key, typename _Val, typename _KeyOfValue,
            typename _Compare, typename _Alloc>
@@ -1229,7 +1449,7 @@ 
 	{
 	  _M_erase(_S_right(__x));
 	  _Link_type __y = _S_left(__x);
-	  _M_destroy_node(__x);
+	  _M_drop_node(__x);
 	  __x = __y;
 	}
     }
@@ -1338,8 +1558,8 @@ 
     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
     equal_range(const _Key& __k) const
     {
-      _Const_Link_type __x = _M_begin();
-      _Const_Link_type __y = _M_end();
+      _Const_Link_type __x = _M_cbegin();
+      _Const_Link_type __y = _M_cend();
       while (__x != 0)
 	{
 	  if (_M_impl._M_key_compare(_S_key(__x), __k))
@@ -1377,10 +1597,9 @@ 
 	      _M_leftmost() = __t._M_leftmost();
 	      _M_rightmost() = __t._M_rightmost();
 	      _M_root()->_M_parent = _M_end();
+	      _M_impl._M_node_count = __t._M_impl._M_node_count;
 	      
-	      __t._M_root() = 0;
-	      __t._M_leftmost() = __t._M_end();
-	      __t._M_rightmost() = __t._M_end();
+	      __t._M_impl._M_reset();
 	    }
 	}
       else if (__t._M_root() == 0)
@@ -1389,10 +1608,9 @@ 
 	  __t._M_leftmost() = _M_leftmost();
 	  __t._M_rightmost() = _M_rightmost();
 	  __t._M_root()->_M_parent = __t._M_end();
+	  __t._M_impl._M_node_count = _M_impl._M_node_count;
 	  
-	  _M_root() = 0;
-	  _M_leftmost() = _M_end();
-	  _M_rightmost() = _M_end();
+	  _M_impl._M_reset();
 	}
       else
 	{
@@ -1402,9 +1620,9 @@ 
 	  
 	  _M_root()->_M_parent = _M_end();
 	  __t._M_root()->_M_parent = __t._M_end();
+	  std::swap(this->_M_impl._M_node_count, __t._M_impl._M_node_count);
 	}
       // No need to swap header's color as it does not change.
-      std::swap(this->_M_impl._M_node_count, __t._M_impl._M_node_count);
       std::swap(this->_M_impl._M_key_compare, __t._M_impl._M_key_compare);
 
       _Alloc_traits::_S_on_swap(_M_get_Node_allocator(),
@@ -1483,9 +1701,12 @@ 
 	= _M_get_insert_unique_pos(_KeyOfValue()(__v));
 
       if (__res.second)
-	return _Res(_M_insert_(__res.first, __res.second,
-			       _GLIBCXX_FORWARD(_Arg, __v)),
-		    true);
+	{
+	  __alloc_node_t __an(*this);
+	  return _Res(_M_insert_(__res.first, __res.second,
+				 _GLIBCXX_FORWARD(_Arg, __v), __an),
+		      true);
+	}
 
       return _Res(iterator(static_cast<_Link_type>(__res.first)), false);
     }
@@ -1505,7 +1726,9 @@ 
     {
       pair<_Base_ptr, _Base_ptr> __res
 	= _M_get_insert_equal_pos(_KeyOfValue()(__v));
-      return _M_insert_(__res.first, __res.second, _GLIBCXX_FORWARD(_Arg, __v));
+      __alloc_node_t __an(*this);
+      return _M_insert_(__res.first, __res.second,
+			_GLIBCXX_FORWARD(_Arg, __v), __an);
     }
 
   template<typename _Key, typename _Val, typename _KeyOfValue,
@@ -1570,22 +1793,27 @@ 
   template<typename _Key, typename _Val, typename _KeyOfValue,
            typename _Compare, typename _Alloc>
 #if __cplusplus >= 201103L
-    template<typename _Arg>
+    template<typename _Arg, typename _NodeGen>
+#else
+    template<typename _NodeGen>
 #endif
-    typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
-    _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
+      typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
+      _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
+      _M_insert_unique_(const_iterator __position,
 #if __cplusplus >= 201103L
-    _M_insert_unique_(const_iterator __position, _Arg&& __v)
+			_Arg&& __v,
 #else
-    _M_insert_unique_(const_iterator __position, const _Val& __v)
+			const _Val& __v,
 #endif
+			const _NodeGen& __node_gen)
     {
       pair<_Base_ptr, _Base_ptr> __res
 	= _M_get_insert_hint_unique_pos(__position, _KeyOfValue()(__v));
 
       if (__res.second)
 	return _M_insert_(__res.first, __res.second,
-			  _GLIBCXX_FORWARD(_Arg, __v));
+			  _GLIBCXX_FORWARD(_Arg, __v),
+			  __node_gen);
       return iterator(static_cast<_Link_type>(__res.first));
     }
 
@@ -1647,25 +1875,30 @@ 
   template<typename _Key, typename _Val, typename _KeyOfValue,
            typename _Compare, typename _Alloc>
 #if __cplusplus >= 201103L
-    template<typename _Arg>
+    template<typename _Arg, typename _NodeGen>
+#else
+    template<typename _NodeGen>
 #endif
-    typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
-    _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
+      typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
+      _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
+      _M_insert_equal_(const_iterator __position,
 #if __cplusplus >= 201103L
-    _M_insert_equal_(const_iterator __position, _Arg&& __v)
+		       _Arg&& __v,
 #else
-    _M_insert_equal_(const_iterator __position, const _Val& __v)
+		       const _Val& __v,
 #endif
-    {
-      pair<_Base_ptr, _Base_ptr> __res
-	= _M_get_insert_hint_equal_pos(__position, _KeyOfValue()(__v));
+		       const _NodeGen& __node_gen)
+      {
+	pair<_Base_ptr, _Base_ptr> __res
+	  = _M_get_insert_hint_equal_pos(__position, _KeyOfValue()(__v));
 
-      if (__res.second)
-	return _M_insert_(__res.first, __res.second,
-			  _GLIBCXX_FORWARD(_Arg, __v));
+	if (__res.second)
+	  return _M_insert_(__res.first, __res.second,
+			    _GLIBCXX_FORWARD(_Arg, __v),
+			    __node_gen);
 
-      return _M_insert_equal_lower(_GLIBCXX_FORWARD(_Arg, __v));
-    }
+	return _M_insert_equal_lower(_GLIBCXX_FORWARD(_Arg, __v));
+      }
 
 #if __cplusplus >= 201103L
   template<typename _Key, typename _Val, typename _KeyOfValue,
@@ -1734,12 +1967,12 @@ 
 	    if (__res.second)
 	      return _Res(_M_insert_node(__res.first, __res.second, __z), true);
 	
-	    _M_destroy_node(__z);
+	    _M_drop_node(__z);
 	    return _Res(iterator(static_cast<_Link_type>(__res.first)), false);
 	  }
 	__catch(...)
 	  {
-	    _M_destroy_node(__z);
+	    _M_drop_node(__z);
 	    __throw_exception_again;
 	  }
       }
@@ -1760,7 +1993,7 @@ 
 	  }
 	__catch(...)
 	  {
-	    _M_destroy_node(__z);
+	    _M_drop_node(__z);
 	    __throw_exception_again;
 	  }
       }
@@ -1781,12 +2014,12 @@ 
 	    if (__res.second)
 	      return _M_insert_node(__res.first, __res.second, __z);
 
-	    _M_destroy_node(__z);
+	    _M_drop_node(__z);
 	    return iterator(static_cast<_Link_type>(__res.first));
 	  }
 	__catch(...)
 	  {
-	    _M_destroy_node(__z);
+	    _M_drop_node(__z);
 	    __throw_exception_again;
 	  }
       }
@@ -1811,7 +2044,7 @@ 
 	  }
 	__catch(...)
 	  {
-	    _M_destroy_node(__z);
+	    _M_drop_node(__z);
 	    __throw_exception_again;
 	  }
       }
@@ -1824,8 +2057,9 @@ 
       _Rb_tree<_Key, _Val, _KoV, _Cmp, _Alloc>::
       _M_insert_unique(_II __first, _II __last)
       {
+	__alloc_node_t __an(*this);
 	for (; __first != __last; ++__first)
-	  _M_insert_unique_(end(), *__first);
+	  _M_insert_unique_(end(), *__first, __an);
       }
 
   template<typename _Key, typename _Val, typename _KoV,
@@ -1835,8 +2069,9 @@ 
       _Rb_tree<_Key, _Val, _KoV, _Cmp, _Alloc>::
       _M_insert_equal(_II __first, _II __last)
       {
+	__alloc_node_t __an(*this);
 	for (; __first != __last; ++__first)
-	  _M_insert_equal_(end(), *__first);
+	  _M_insert_equal_(end(), *__first, __an);
       }
 
   template<typename _Key, typename _Val, typename _KeyOfValue,
@@ -1849,7 +2084,7 @@ 
 	static_cast<_Link_type>(_Rb_tree_rebalance_for_erase
 				(const_cast<_Base_ptr>(__position._M_node),
 				 this->_M_impl._M_header));
-      _M_destroy_node(__y);
+      _M_drop_node(__y);
       --_M_impl._M_node_count;
     }
 
@@ -1908,7 +2143,7 @@ 
     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
     find(const _Key& __k) const
     {
-      const_iterator __j = _M_lower_bound(_M_begin(), _M_end(), __k);
+      const_iterator __j = _M_lower_bound(_M_cbegin(), _M_cend(), __k);
       return (__j == end()
 	      || _M_impl._M_key_compare(__k, 
 					_S_key(__j._M_node))) ? end() : __j;