diff mbox

Default associative containers constructors/destructor/assignment

Message ID 87049605-cb4e-a451-01f7-4cf106dd0633@gmail.com
State New
Headers show

Commit Message

François Dumont Oct. 28, 2016, 7:42 p.m. UTC
Hi

     Here is the patch to default all other associative containers 
operations that can be defaulted.

     To do so I introduce a _Rb_tree_key_compare type that take care of 
value initialization of compare functor. It also make sure that functor 
is copied rather than move in move constructor with necessary noexcept 
qualification.

     I also introduce _Rb_tree_header to take care of the initialization 
of the _Rb_tree_node_base used in the container header and of 
_M_node_count. I also use it to implement the move semantic and so 
default also _Rb_tree_impl move construtor.

     I also propose a solution for the FIXME regarding documentation of 
container destructor, I used C++11 default declaration. I don't have 
necessary tools to generate Doxygen doc but I am confident that it 
should work fine. I had to simplify doc for operations that are now 
defaulted.


     * include/bits/stl_map.h (map(const map&)): Make default.
     (map(map&&)): Likewise.
     (~map()): Likewise.
     (operator=(const map&)): Likewise.
     * include/bits/stl_multimap.h (multimap(const multimap&)): Make 
default.
     (multimap(multimap&&)): Likewise.
     (~multimap()): Likewise.
     (operator=(const multimap&)): Likewise.
     * include/bits/stl_set.h (set(const set&)): Make default.
     (set(set&&)): Likewise.
     (~set()): Likewise.
     (operator=(const set&)): Likewise.
     * include/bits/stl_multiset.h (multiset(const multiset&)): Make 
default.
     (multiset(multiset&&)): Likewise.
     (~multiset()): Likewise.
     (operator=(const multiset&)): Likewise.
     * include/bits/stl_tree.h (_Rb_tree_key_compare<>): New.
     (_Rb_tree_header): New.
     (_Rb_tree_impl): Inherit from latter.
     (_Rb_tree_impl()): Make default.
     (_Rb_tree_impl(const _Rb_tree_impl&)): New.
     (_Rb_tree_impl(_Rb_tree_impl&&)): New, default.
     (_Rb_tree_impl::_M_reset): Move...
     (_Rb_tree_header::_M_reset): ...here.
     (_Rb_tree_impl::_M_initialize): Move...
     (_Rb_tree_header::_M_initialize): ...here.
     (_Rb_tree(_Rb_tree&&)): Make default.
     (_Rb_tree_header::_M_move_data(_Rb_tree_header&)): New.
     (_Rb_tree<>::_M_move_data(_Rb_tree&, true_type)): Use latter.

     Tested under Linux x86_64, ok to commit ?

François

Comments

François Dumont Nov. 14, 2016, 8:34 p.m. UTC | #1
Any feedback regarding this patch ?

François

On 02/11/2016 22:37, François Dumont wrote:
> Hi

>

>     Here is an updated proposal, I realized that the newly introduced 

> _M_move_data can be also used in the swap implementation.

>

>     Let me know if you prefer without it or not.

>

> François

>

>

> On 28/10/2016 21:42, François Dumont wrote:

>> Hi

>>

>>     Here is the patch to default all other associative containers 

>> operations that can be defaulted.

>>

>>     To do so I introduce a _Rb_tree_key_compare type that take care 

>> of value initialization of compare functor. It also make sure that 

>> functor is copied rather than move in move constructor with necessary 

>> noexcept qualification.

>>

>>     I also introduce _Rb_tree_header to take care of the 

>> initialization of the _Rb_tree_node_base used in the container header 

>> and of _M_node_count. I also use it to implement the move semantic 

>> and so default also _Rb_tree_impl move construtor.

>>

>>     I also propose a solution for the FIXME regarding documentation 

>> of container destructor, I used C++11 default declaration. I don't 

>> have necessary tools to generate Doxygen doc but I am confident that 

>> it should work fine. I had to simplify doc for operations that are 

>> now defaulted.

>>

>>

>>     * include/bits/stl_map.h (map(const map&)): Make default.

>>     (map(map&&)): Likewise.

>>     (~map()): Likewise.

>>     (operator=(const map&)): Likewise.

>>     * include/bits/stl_multimap.h (multimap(const multimap&)): Make 

>> default.

>>     (multimap(multimap&&)): Likewise.

>>     (~multimap()): Likewise.

>>     (operator=(const multimap&)): Likewise.

>>     * include/bits/stl_set.h (set(const set&)): Make default.

>>     (set(set&&)): Likewise.

>>     (~set()): Likewise.

>>     (operator=(const set&)): Likewise.

>>     * include/bits/stl_multiset.h (multiset(const multiset&)): Make 

>> default.

>>     (multiset(multiset&&)): Likewise.

>>     (~multiset()): Likewise.

>>     (operator=(const multiset&)): Likewise.

>>     * include/bits/stl_tree.h (_Rb_tree_key_compare<>): New.

>>     (_Rb_tree_header): New.

>>     (_Rb_tree_impl): Inherit from latter.

>>     (_Rb_tree_impl()): Make default.

>>     (_Rb_tree_impl(const _Rb_tree_impl&)): New.

>>     (_Rb_tree_impl(_Rb_tree_impl&&)): New, default.

>>     (_Rb_tree_impl::_M_reset): Move...

>>     (_Rb_tree_header::_M_reset): ...here.

>>     (_Rb_tree_impl::_M_initialize): Move...

>>     (_Rb_tree_header::_M_initialize): ...here.

>>     (_Rb_tree(_Rb_tree&&)): Make default.

>>     (_Rb_tree_header::_M_move_data(_Rb_tree_header&)): New.

>>     (_Rb_tree<>::_M_move_data(_Rb_tree&, true_type)): Use latter.

>>

>>     Tested under Linux x86_64, ok to commit ?

>>

>> François

>>

>
Jonathan Wakely Nov. 17, 2016, 5:52 p.m. UTC | #2
On 28/10/16 21:42 +0200, François Dumont wrote:
>       /**

>        *  @brief  %Map move constructor.

>-       *  @param  __x  A %map of identical element and allocator types.

>        *

>-       *  The newly-created %map contains the exact contents of @a __x.

>-       *  The contents of @a __x are a valid, but unspecified %map.

>+       *  The newly-created %map contains the exact contents of the moved

>+       *  instance. The moved instance is a valid, but unspecified, %map.


This comment isn't true, because non-propagating or non-equal
allocators can force elements to be copied, but that's unrelated to
your patch.

There are no problems with the changes to the map and set containers,
but I have some comments on the _Rb_tree changes. Overall I like the
change.

>diff --git a/libstdc++-v3/include/bits/stl_tree.h b/libstdc++-v3/include/bits/stl_tree.h

>index 0bc5f4b..126087e 100644

>--- a/libstdc++-v3/include/bits/stl_tree.h

>+++ b/libstdc++-v3/include/bits/stl_tree.h

>@@ -137,6 +137,81 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION

>     }

>   };

> 

>+  // Helper type offering value initialization guaranty on the compare functor.


Spelling: "guarantee"

>+  template<typename _Key_compare>

>+    struct _Rb_tree_key_compare

>+    {

>+      _Key_compare		_M_key_compare;

>+

>+      _Rb_tree_key_compare()

>+      _GLIBCXX_NOEXCEPT_IF(

>+	is_nothrow_default_constructible<_Key_compare>::value)

>+      : _M_key_compare()

>+      { }

>+

>+      _Rb_tree_key_compare(const _Key_compare& __comp)

>+      : _M_key_compare(__comp)

>+      { }

>+

>+#if __cplusplus >= 201103L

>+      _Rb_tree_key_compare(_Rb_tree_key_compare&& __x)

>+	noexcept(is_nothrow_copy_constructible<_Key_compare>::value)

>+      : _M_key_compare(__x._M_key_compare)

>+      { }

>+#endif


This constructor makes the type move-only (i.e.  non-copyable) in
C++11 and later. It's copyable in C++98. Is that what you want?

Adding defaulted copy operations would fix that. Even if we don't
actually need those copy operations, I'm uncomfortable with it being
copyable in C++98 and non-copyable otherwise.

>+    void

>+    _M_reset()

>+    {

>+      _M_initialize();

>+      _M_node_count = 0;

>+    }


This introduces a small change in behaviour, because _M_reset() now
does _M_header._M_color = _S_red, which it didn't do before. That
store is redundant. It could be avoided by just doing the three
assignments in _M_reset() instead of calling _M_initialize().

And we could remove _M_initialize() entirely, and remove the redundant
mem-initializers for _M_node_count (because it's set my _M_reset and
_M_move_data anyway):

    _Rb_tree_header() _GLIBCXX_NOEXCEPT
    {
      _M_reset();
      _M_header._M_color = _S_red;
    }

#if __cplusplus >= 201103L
    _Rb_tree_header(_Rb_tree_header&& __x) noexcept
    {
      if (__x._M_header._M_parent != nullptr)
       _M_move_data(__x);
      else
        {
          _M_reset();
          _M_header._M_color = _S_red;
        }
    }

    void
    _M_move_data(_Rb_tree_header& __x)
    {
      _M_header._M_parent = __x._M_header._M_parent;
      _M_header._M_left = __x._M_header._M_left;
      _M_header._M_right = __x._M_header._M_right;
      _M_header._M_parent->_M_parent = &_M_header;
      _M_node_count = __x._M_node_count;

      __x._M_reset();
    }
#endif

    void
    _M_reset()
    {
      _M_header._M_parent = 0;
      _M_header._M_left = &_M_header;
      _M_header._M_right = &_M_header;
      _M_node_count = 0;
    }


>@@ -599,50 +674,31 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION

>       // Unused _Is_pod_comparator is kept as it is part of mangled name.

>       template<typename _Key_compare,

> 	       bool /* _Is_pod_comparator */ = __is_pod(_Key_compare)>

>-        struct _Rb_tree_impl : public _Node_allocator

>+        struct _Rb_tree_impl

>+	: public _Node_allocator

>+	, public _Rb_tree_key_compare<_Key_compare>

>+	, public _Rb_tree_header


Do these need to be base classes, rather than data members?

We derive from the allocator to benefit from the empty base-class
optimization, but that isn't relevant for the _Rb_tree_key_compare and
_Rb_tree_header types. It *could* be relevant for the comparison
function, but would be an ABI change. We could do that ABI change
conditionally, for gnu-versioned-namespace builds, but that's still
possible using data members (e.g. have a data member that derives from
the comparison function and contains the header node and/or node count
members).

Making them data members would simply mean restoring the function
_Rb_tree_impl::_M_reset() and making it call reset on the member:

     void
     _M_reset() { _M_header._M_reset(); }

The minor convenience of inheriting this function from a base class
doesn't seem worth the stronger coupling that comes from using
inheritance.

Am I missing some other reason that inheritance is used here?

>-	  _Rb_tree_impl(const _Key_compare& __comp, const _Node_allocator& __a)

>-	  : _Node_allocator(__a), _M_key_compare(__comp), _M_header(),

>-	    _M_node_count(0)

>-	  { _M_initialize(); }


Please mention the removal of this constructor in the changelog.

>@@ -1534,19 +1583,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION

>     void

>     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::

>     _M_move_data(_Rb_tree& __x, std::true_type)

>-    {

>-      _M_root() = __x._M_root();

>-      _M_leftmost() = __x._M_leftmost();

>-      _M_rightmost() = __x._M_rightmost();

>-      _M_root()->_M_parent = _M_end();

>-

>-      __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;

>-    }

>+    { _M_impl._M_move_data(__x._M_impl); }


This function could be moved into the class body, or just have
'inline' added to its definition.
diff mbox

Patch

diff --git a/libstdc++-v3/include/bits/stl_map.h b/libstdc++-v3/include/bits/stl_map.h
index dea7d5b..bbd0a97 100644
--- a/libstdc++-v3/include/bits/stl_map.h
+++ b/libstdc++-v3/include/bits/stl_map.h
@@ -185,25 +185,22 @@  _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
 
       /**
        *  @brief  %Map copy constructor.
-       *  @param  __x  A %map of identical element and allocator types.
        *
-       *  The newly-created %map uses a copy of the allocator object used
-       *  by @a __x (unless the allocator traits dictate a different object).
+       *  Whether the allocator is copied depends on the allocator traits.
        */
+#if __cplusplus < 201103L
       map(const map& __x)
       : _M_t(__x._M_t) { }
+#else
+      map(const map&) = default;
 
-#if __cplusplus >= 201103L
       /**
        *  @brief  %Map move constructor.
-       *  @param  __x  A %map of identical element and allocator types.
        *
-       *  The newly-created %map contains the exact contents of @a __x.
-       *  The contents of @a __x are a valid, but unspecified %map.
+       *  The newly-created %map contains the exact contents of the moved
+       *  instance. The moved instance is a valid, but unspecified, %map.
        */
-      map(map&& __x)
-      noexcept(is_nothrow_copy_constructible<_Compare>::value)
-      : _M_t(std::move(__x._M_t)) { }
+      map(map&&) = default;
 
       /**
        *  @brief  Builds a %map from an initializer_list.
@@ -284,31 +281,31 @@  _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
 	: _M_t(__comp, _Pair_alloc_type(__a))
         { _M_t._M_insert_unique(__first, __last); }
 
-      // FIXME There is no dtor declared, but we should have something
-      // generated by Doxygen.  I don't know what tags to add to this
-      // paragraph to make that happen:
+#if __cplusplus >= 201103L
       /**
        *  The dtor only erases the elements, and note that if the elements
        *  themselves are pointers, the pointed-to memory is not touched in any
        *  way.  Managing the pointer is the user's responsibility.
        */
+      ~map() = default;
+#endif
 
       /**
        *  @brief  %Map assignment operator.
-       *  @param  __x  A %map of identical element and allocator types.
-       *
-       *  All the elements of @a __x are copied.
        *
        *  Whether the allocator is copied depends on the allocator traits.
        */
+#if __cplusplus < 201103L
       map&
       operator=(const map& __x)
       {
 	_M_t = __x._M_t;
 	return *this;
       }
+#else
+      map&
+      operator=(const map&) = default;
 
-#if __cplusplus >= 201103L
       /// Move assignment operator.
       map&
       operator=(map&&) = default;
diff --git a/libstdc++-v3/include/bits/stl_multimap.h b/libstdc++-v3/include/bits/stl_multimap.h
index 7e86b76..a5f775b 100644
--- a/libstdc++-v3/include/bits/stl_multimap.h
+++ b/libstdc++-v3/include/bits/stl_multimap.h
@@ -182,25 +182,23 @@  _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
 
       /**
        *  @brief  %Multimap copy constructor.
-       *  @param  __x  A %multimap of identical element and allocator types.
        *
-       *  The newly-created %multimap uses a copy of the allocator object used
-       *  by @a __x (unless the allocator traits dictate a different object).
+       *  Whether the allocator is copied depends on the allocator traits.
        */
+#if __cplusplus < 201103L
       multimap(const multimap& __x)
       : _M_t(__x._M_t) { }
+#else
+      multimap(const multimap&) = default;
 
-#if __cplusplus >= 201103L
       /**
        *  @brief  %Multimap move constructor.
-       *  @param   __x  A %multimap of identical element and allocator types.
        *
-       *  The newly-created %multimap contains the exact contents of @a __x.
-       *  The contents of @a __x are a valid, but unspecified %multimap.
+       *  The newly-created %multimap contains the exact contents of the
+       *  moved instance. The moved instance is a valid, but unspecified
+       *  %multimap.
        */
-      multimap(multimap&& __x)
-      noexcept(is_nothrow_copy_constructible<_Compare>::value)
-      : _M_t(std::move(__x._M_t)) { }
+      multimap(multimap&&) = default;
 
       /**
        *  @brief  Builds a %multimap from an initializer_list.
@@ -278,31 +276,31 @@  _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
 	: _M_t(__comp, _Pair_alloc_type(__a))
         { _M_t._M_insert_equal(__first, __last); }
 
-      // FIXME There is no dtor declared, but we should have something generated
-      // by Doxygen.  I don't know what tags to add to this paragraph to make
-      // that happen:
+#if __cplusplus >= 201103L
       /**
        *  The dtor only erases the elements, and note that if the elements
        *  themselves are pointers, the pointed-to memory is not touched in any
        *  way. Managing the pointer is the user's responsibility.
        */
+      ~multimap() = default;
+#endif
 
       /**
        *  @brief  %Multimap assignment operator.
-       *  @param  __x  A %multimap of identical element and allocator types.
-       *
-       *  All the elements of @a __x are copied.
        *
        *  Whether the allocator is copied depends on the allocator traits.
        */
+#if __cplusplus < 201103L
       multimap&
       operator=(const multimap& __x)
       {
 	_M_t = __x._M_t;
 	return *this;
       }
+#else
+      multimap&
+      operator=(const multimap&) = default;
 
-#if __cplusplus >= 201103L
       /// Move assignment operator.
       multimap&
       operator=(multimap&&) = default;
diff --git a/libstdc++-v3/include/bits/stl_multiset.h b/libstdc++-v3/include/bits/stl_multiset.h
index 7fe2fbd..8a83b17 100644
--- a/libstdc++-v3/include/bits/stl_multiset.h
+++ b/libstdc++-v3/include/bits/stl_multiset.h
@@ -194,25 +194,23 @@  _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
 
       /**
        *  @brief  %Multiset copy constructor.
-       *  @param  __x  A %multiset of identical element and allocator types.
        *
-       *  The newly-created %multiset uses a copy of the allocator object used
-       *  by @a __x (unless the allocator traits dictate a different object).
+       *  Whether the allocator is copied depends on the allocator traits.
        */
+#if __cplusplus < 201103L
       multiset(const multiset& __x)
       : _M_t(__x._M_t) { }
+#else
+      multiset(const multiset&) = default;
 
-#if __cplusplus >= 201103L
      /**
        *  @brief  %Multiset move constructor.
-       *  @param  __x  A %multiset of identical element and allocator types.
        *
-       *  The newly-created %multiset contains the exact contents of @a __x.
-       *  The contents of @a __x are a valid, but unspecified %multiset.
+       *  The newly-created %multiset contains the exact contents of the
+       *  moved instance. The moved instance is a valid, but unspecified
+       *  %multiset.
        */
-      multiset(multiset&& __x)
-      noexcept(is_nothrow_copy_constructible<_Compare>::value)
-      : _M_t(std::move(__x._M_t)) { }
+      multiset(multiset&&) = default;
 
       /**
        *  @brief  Builds a %multiset from an initializer_list.
@@ -256,24 +254,31 @@  _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
 		 const allocator_type& __a)
 	: _M_t(_Compare(), _Key_alloc_type(__a))
         { _M_t._M_insert_equal(__first, __last); }
+
+      /**
+       *  The dtor only erases the elements, and note that if the elements
+       *  themselves are pointers, the pointed-to memory is not touched in any
+       *  way. Managing the pointer is the user's responsibility.
+       */
+      ~multiset() = default;
 #endif
 
       /**
        *  @brief  %Multiset assignment operator.
-       *  @param  __x  A %multiset of identical element and allocator types.
-       *
-       *  All the elements of @a __x are copied.
        *
        *  Whether the allocator is copied depends on the allocator traits.
        */
+#if __cplusplus < 201103L
       multiset&
       operator=(const multiset& __x)
       {
 	_M_t = __x._M_t;
 	return *this;
       }
+#else
+      multiset&
+      operator=(const multiset&) = default;
 
-#if __cplusplus >= 201103L
       /// Move assignment operator.
       multiset&
       operator=(multiset&&) = default;
diff --git a/libstdc++-v3/include/bits/stl_set.h b/libstdc++-v3/include/bits/stl_set.h
index 5ed9672..db1e031 100644
--- a/libstdc++-v3/include/bits/stl_set.h
+++ b/libstdc++-v3/include/bits/stl_set.h
@@ -199,25 +199,22 @@  _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
 
       /**
        *  @brief  %Set copy constructor.
-       *  @param  __x  A %set of identical element and allocator types.
        *
-       *  The newly-created %set uses a copy of the allocator object used
-       *  by @a __x (unless the allocator traits dictate a different object).
+       *  Whether the allocator is copied depends on the allocator traits.
        */
+#if __cplusplus < 201103L
       set(const set& __x)
       : _M_t(__x._M_t) { }
+#else
+      set(const set&) = default;
 
-#if __cplusplus >= 201103L
      /**
        *  @brief %Set move constructor
-       *  @param __x  A %set of identical element and allocator types.
        *
-       *  The newly-created %set contains the exact contents of @a x.
-       *  The contents of @a x are a valid, but unspecified %set.
+       *  The newly-created %set contains the exact contents of the moved
+       *  instance. The moved instance is a valid, but unspecified, %set.
        */
-      set(set&& __x)
-      noexcept(is_nothrow_copy_constructible<_Compare>::value)
-      : _M_t(std::move(__x._M_t)) { }
+      set(set&&) = default;
 
       /**
        *  @brief  Builds a %set from an initializer_list.
@@ -261,24 +258,31 @@  _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
 	    const allocator_type& __a)
 	: _M_t(_Compare(), _Key_alloc_type(__a))
         { _M_t._M_insert_unique(__first, __last); }
+
+      /**
+       *  The dtor only erases the elements, and note that if the elements
+       *  themselves are pointers, the pointed-to memory is not touched in any
+       *  way. Managing the pointer is the user's responsibility.
+       */
+      ~set() = default;
 #endif
 
       /**
        *  @brief  %Set assignment operator.
-       *  @param  __x  A %set of identical element and allocator types.
-       *
-       *  All the elements of @a __x are copied.
        *
        *  Whether the allocator is copied depends on the allocator traits.
        */
+#if __cplusplus < 201103L
       set&
       operator=(const set& __x)
       {
 	_M_t = __x._M_t;
 	return *this;
       }
+#else
+      set&
+      operator=(const set&) = default;
 
-#if __cplusplus >= 201103L
       /// Move assignment operator.
       set&
       operator=(set&&) = default;
diff --git a/libstdc++-v3/include/bits/stl_tree.h b/libstdc++-v3/include/bits/stl_tree.h
index 0bc5f4b..126087e 100644
--- a/libstdc++-v3/include/bits/stl_tree.h
+++ b/libstdc++-v3/include/bits/stl_tree.h
@@ -137,6 +137,81 @@  _GLIBCXX_BEGIN_NAMESPACE_VERSION
     }
   };
 
+  // Helper type offering value initialization guaranty on the compare functor.
+  template<typename _Key_compare>
+    struct _Rb_tree_key_compare
+    {
+      _Key_compare		_M_key_compare;
+
+      _Rb_tree_key_compare()
+      _GLIBCXX_NOEXCEPT_IF(
+	is_nothrow_default_constructible<_Key_compare>::value)
+      : _M_key_compare()
+      { }
+
+      _Rb_tree_key_compare(const _Key_compare& __comp)
+      : _M_key_compare(__comp)
+      { }
+
+#if __cplusplus >= 201103L
+      _Rb_tree_key_compare(_Rb_tree_key_compare&& __x)
+	noexcept(is_nothrow_copy_constructible<_Key_compare>::value)
+      : _M_key_compare(__x._M_key_compare)
+      { }
+#endif
+    };
+
+  // Helper type to manage default initialization of node count and header.
+  struct _Rb_tree_header
+  {
+    _Rb_tree_node_base	_M_header;
+    size_t		_M_node_count; // Keeps track of size of tree.
+
+    _Rb_tree_header() _GLIBCXX_NOEXCEPT
+    : _M_node_count(0)
+    { _M_initialize(); }
+
+#if __cplusplus >= 201103L
+    _Rb_tree_header(_Rb_tree_header&& __x) noexcept
+      : _M_node_count(0)
+    {
+      if (__x._M_header._M_parent != nullptr)
+	_M_move_data(__x);
+      else
+	_M_initialize();
+    }
+
+    void
+    _M_move_data(_Rb_tree_header& __x)
+    {
+      _M_header._M_parent = __x._M_header._M_parent;
+      _M_header._M_left = __x._M_header._M_left;
+      _M_header._M_right = __x._M_header._M_right;
+      _M_header._M_parent->_M_parent = &_M_header;
+      _M_node_count = __x._M_node_count;
+
+      __x._M_reset();
+    }
+#endif
+
+    void
+    _M_reset()
+    {
+      _M_initialize();
+      _M_node_count = 0;
+    }
+
+  private:
+    void
+    _M_initialize()
+    {
+      _M_header._M_color = _S_red;
+      _M_header._M_parent = 0;
+      _M_header._M_left = &_M_header;
+      _M_header._M_right = &_M_header;
+    }
+  };
+
   template<typename _Val>
     struct _Rb_tree_node : public _Rb_tree_node_base
     {
@@ -599,50 +674,31 @@  _GLIBCXX_BEGIN_NAMESPACE_VERSION
       // Unused _Is_pod_comparator is kept as it is part of mangled name.
       template<typename _Key_compare,
 	       bool /* _Is_pod_comparator */ = __is_pod(_Key_compare)>
-        struct _Rb_tree_impl : public _Node_allocator
+        struct _Rb_tree_impl
+	: public _Node_allocator
+	, public _Rb_tree_key_compare<_Key_compare>
+	, public _Rb_tree_header
         {
-	  _Key_compare		_M_key_compare;
-	  _Rb_tree_node_base	_M_header;
-	  size_type		_M_node_count; // Keeps track of size of tree.
+	  typedef _Rb_tree_key_compare<_Key_compare> _Base_key_compare;
 
+#if __cplusplus < 201103L
 	  _Rb_tree_impl()
-	  _GLIBCXX_NOEXCEPT_IF(
-	    is_nothrow_default_constructible<_Node_allocator>::value
-	    && is_nothrow_default_constructible<_Key_compare>::value)
-	  : _Node_allocator(), _M_key_compare(), _M_header(),
-	    _M_node_count(0)
-	  { _M_initialize(); }
+	  { }
+#else
+	  _Rb_tree_impl() = default;
+#endif
 
-	  _Rb_tree_impl(const _Key_compare& __comp, const _Node_allocator& __a)
-	  : _Node_allocator(__a), _M_key_compare(__comp), _M_header(),
-	    _M_node_count(0)
-	  { _M_initialize(); }
+	  _Rb_tree_impl(const _Rb_tree_impl& __x)
+	  : _Node_allocator(_Alloc_traits::_S_select_on_copy(__x))
+	  , _Base_key_compare(__x._M_key_compare)
+	  { }
 
 #if __cplusplus >= 201103L
+	  _Rb_tree_impl(_Rb_tree_impl&&) = default;
 	  _Rb_tree_impl(const _Key_compare& __comp, _Node_allocator&& __a)
-	  : _Node_allocator(std::move(__a)), _M_key_compare(__comp),
-	    _M_header(), _M_node_count(0)
-	  { _M_initialize(); }
+	  : _Node_allocator(std::move(__a)), _Base_key_compare(__comp)
+	  { }
 #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()
-	  {
-	    this->_M_header._M_color = _S_red;
-	    this->_M_header._M_parent = 0;
-	    this->_M_header._M_left = &this->_M_header;
-	    this->_M_header._M_right = &this->_M_header;
-	  }
 	};
 
       _Rb_tree_impl<_Compare> _M_impl;
@@ -845,8 +901,7 @@  _GLIBCXX_BEGIN_NAMESPACE_VERSION
       : _M_impl(__comp, _Node_allocator(__a)) { }
 
       _Rb_tree(const _Rb_tree& __x)
-      : _M_impl(__x._M_impl._M_key_compare,
-	        _Alloc_traits::_S_select_on_copy(__x._M_get_Node_allocator()))
+      : _M_impl(__x._M_impl)
       {
 	if (__x._M_root() != 0)
 	  {
@@ -874,13 +929,7 @@  _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	  }
       }
 
-      _Rb_tree(_Rb_tree&& __x)
-      : _M_impl(__x._M_impl._M_key_compare,
-		std::move(__x._M_get_Node_allocator()))
-      {
-	if (__x._M_root() != 0)
-	  _M_move_data(__x, std::true_type());
-      }
+      _Rb_tree(_Rb_tree&&) = default;
 
       _Rb_tree(_Rb_tree&& __x, const allocator_type& __a)
       : _Rb_tree(std::move(__x), _Node_allocator(__a))
@@ -1534,19 +1583,7 @@  _GLIBCXX_BEGIN_NAMESPACE_VERSION
     void
     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
     _M_move_data(_Rb_tree& __x, std::true_type)
-    {
-      _M_root() = __x._M_root();
-      _M_leftmost() = __x._M_leftmost();
-      _M_rightmost() = __x._M_rightmost();
-      _M_root()->_M_parent = _M_end();
-
-      __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;
-    }
+    { _M_impl._M_move_data(__x._M_impl); }
 
   template<typename _Key, typename _Val, typename _KeyOfValue,
            typename _Compare, typename _Alloc>