Default associative containers constructors/destructor/assignment

Default associative containers constructors/destructor/assignment

[François Dumont]

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

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


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

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>

Re: Default associative containers constructors/destructor/assignment

[François Dumont]

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

Re: Default associative containers constructors/destructor/assignment

[Jonathan Wakely]

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.

Re: Default associative containers constructors/destructor/assignment

[François Dumont]

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

On 17/11/2016 18:52, Jonathan Wakely wrote:
>
> On 28/10/16 21:42 +0200, François Dumont wrote:
>
>> +  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?

I simply consider it was not a problem as, as you noticed, it is not used.

>
> 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.
Ok, I'll add a default copy constructor for consistency like this:

       // Copy constructor added for consistency with C++98 mode.
       _Rb_tree_key_compare(const _Rb_tree_compare&) = default;

>
>> +    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().

I thought it was ok to do this additional operation for the sake of 
reusing _M_initialize(). I was compenciating it by avoiding default 
initialization when there is something to move.

>
> 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;
>    }
>
Yes, looks nice, adopted.

Talking about _M_color I just realize that move semantic doesn't copy 
_M_color. Shouldn't we capture it along with all the other _M_header 
information ?

>
>> @@ -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?

The purpose of this patch is to rely more on compiler especially in 
regards to the noexcept qualifications. This is why I started isolating 
each ressource in its own class in charge of its specificities. And I 
leave to the compiler the work of combining those types. However I also 
wanted to limit the impact of this patch on the _Rb_tree and still be 
able to use things like this->_M_impl._M_node_count or 
this->_M_impl._M_header. So the usage of inheritance.

>
>> -      _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.
>
Ok, adopted in the attached new version of the patch.

Tested under x86_64 Linux, ok to commit ?

For info, I would like to propose another bunch of simplifications of 
_Rb_tree, see other patch attached. Do you want me to propose it in 
another mail ?

François




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

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..8de5e31 100644
--- a/libstdc++-v3/include/bits/stl_tree.h
+++ b/libstdc++-v3/include/bits/stl_tree.h
@@ -137,6 +137,80 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
     }
   };
 
+  // Helper type offering value initialization guarantee 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
+      // Copy constructor added for consistency with C++98 mode.
+      _Rb_tree_key_compare(const _Rb_tree_key_compare&) = default;
+
+      _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_header._M_color = _S_red;
+      _M_reset();
+    }
+
+#if __cplusplus >= 201103L
+    _Rb_tree_header(_Rb_tree_header&& __x) noexcept
+    {
+      if (__x._M_header._M_parent != nullptr)
+	_M_move_data(__x);
+      else
+	{
+	  _M_header._M_color = _S_red;
+	  _M_reset();
+	}
+    }
+#endif
+
+    void
+    _M_move_data(_Rb_tree_header& __from)
+    {
+      _M_header._M_parent = __from._M_header._M_parent;
+      _M_header._M_left = __from._M_header._M_left;
+      _M_header._M_right = __from._M_header._M_right;
+      _M_header._M_parent->_M_parent = &_M_header;
+      _M_node_count = __from._M_node_count;
+
+      __from._M_reset();
+    }
+
+    void
+    _M_reset()
+    {
+      _M_header._M_parent = 0;
+      _M_header._M_left = &_M_header;
+      _M_header._M_right = &_M_header;
+      _M_node_count = 0;
+    }
+  };
+
   template<typename _Val>
     struct _Rb_tree_node : public _Rb_tree_node_base
     {
@@ -599,50 +673,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 +900,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 +928,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))
@@ -1278,7 +1326,8 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
     private:
       // Move elements from container with equal allocator.
       void
-      _M_move_data(_Rb_tree&, std::true_type);
+      _M_move_data(_Rb_tree& __x, std::true_type)
+      { _M_impl._M_move_data(__x._M_impl); }
 
       // Move elements from container with possibly non-equal allocator,
       // which might result in a copy not a move.
@@ -1533,25 +1582,6 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
            typename _Compare, typename _Alloc>
     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;
-    }
-
-  template<typename _Key, typename _Val, typename _KeyOfValue,
-           typename _Compare, typename _Alloc>
-    void
-    _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
     _M_move_data(_Rb_tree& __x, std::false_type)
     {
       if (_M_get_Node_allocator() == __x._M_get_Node_allocator())
@@ -1966,26 +1996,10 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
       if (_M_root() == 0)
 	{
 	  if (__t._M_root() != 0)
-	    {
-	      _M_root() = __t._M_root();
-	      _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_impl._M_reset();
-	    }
+	    _M_impl._M_move_data(__t._M_impl);
 	}
       else if (__t._M_root() == 0)
-	{
-	  __t._M_root() = _M_root();
-	  __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_impl._M_reset();
-	}
+	__t._M_impl._M_move_data(_M_impl);
       else
 	{
 	  std::swap(_M_root(),__t._M_root());

[-- Attachment #3: rbtree_simplifications.patch --]
[-- Type: text/x-patch, Size: 3561 bytes --]

diff --git a/libstdc++-v3/include/bits/stl_tree.h b/libstdc++-v3/include/bits/stl_tree.h
index 8de5e31..1bfbfa7 100644
--- a/libstdc++-v3/include/bits/stl_tree.h
+++ b/libstdc++-v3/include/bits/stl_tree.h
@@ -861,11 +861,22 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	_Link_type
 	_M_copy(_Const_Link_type __x, _Base_ptr __p, _NodeGen&);
 
+      template<typename _NodeGen>
+	_Link_type
+	_M_copy(const _Rb_tree& __x, _NodeGen& __gen)
+	{
+	  _Link_type __root = _M_copy(__x._M_begin(), _M_end(), __gen);
+	  _M_leftmost() = _S_minimum(__root);
+	  _M_rightmost() = _S_maximum(__root);
+	  _M_impl._M_node_count = __x._M_impl._M_node_count;
+	  return __root;
+	}
+
       _Link_type
-      _M_copy(_Const_Link_type __x, _Base_ptr __p)
+      _M_copy(const _Rb_tree& __x)
       {
 	_Alloc_node __an(*this);
-	return _M_copy(__x, __p, __an);
+	return _M_copy(__x, __an);
       }
 
       void
@@ -903,12 +914,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
       : _M_impl(__x._M_impl)
       {
 	if (__x._M_root() != 0)
-	  {
-	    _M_root() = _M_copy(__x._M_begin(), _M_end());
-	    _M_leftmost() = _S_minimum(_M_root());
-	    _M_rightmost() = _S_maximum(_M_root());
-	    _M_impl._M_node_count = __x._M_impl._M_node_count;
-	  }
+	  _M_root() = _M_copy(__x);
       }
 
 #if __cplusplus >= 201103L
@@ -920,12 +926,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
       : _M_impl(__x._M_impl._M_key_compare, _Node_allocator(__a))
       {
 	if (__x._M_root() != nullptr)
-	  {
-	    _M_root() = _M_copy(__x._M_begin(), _M_end());
-	    _M_leftmost() = _S_minimum(_M_root());
-	    _M_rightmost() = _S_maximum(_M_root());
-	    _M_impl._M_node_count = __x._M_impl._M_node_count;
-	  }
+	  _M_root() = _M_copy(__x);
       }
 
       _Rb_tree(_Rb_tree&&) = default;
@@ -1595,10 +1596,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	      auto& __val = const_cast<value_type&>(__cval);
 	      return __an(std::move_if_noexcept(__val));
 	    };
-	  _M_root() = _M_copy(__x._M_begin(), _M_end(), __lbd);
-	  _M_leftmost() = _S_minimum(_M_root());
-	  _M_rightmost() = _S_maximum(_M_root());
-	  _M_impl._M_node_count = __x._M_impl._M_node_count;
+	  _M_root() = _M_copy(__x, __lbd);
 	}
     }
 
@@ -1636,10 +1634,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	      auto& __val = const_cast<value_type&>(__cval);
 	      return __roan(std::move_if_noexcept(__val));
 	    };
-	  _M_root() = _M_copy(__x._M_begin(), _M_end(), __lbd);
-	  _M_leftmost() = _S_minimum(_M_root());
-	  _M_rightmost() = _S_maximum(_M_root());
-	  _M_impl._M_node_count = __x._M_impl._M_node_count;
+	  _M_root() = _M_copy(__x, __lbd);
 	  __x.clear();
 	}
     }
@@ -1653,10 +1648,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	     && is_nothrow_move_assignable<_Compare>::value)
     {
       _M_impl._M_key_compare = std::move(__x._M_impl._M_key_compare);
-      constexpr bool __move_storage =
-	  _Alloc_traits::_S_propagate_on_move_assign()
-	  || _Alloc_traits::_S_always_equal();
-      _M_move_assign(__x, __bool_constant<__move_storage>());
+      _M_move_assign(__x, __bool_constant<_Alloc_traits::_S_nothrow_move()>());
       return *this;
     }
 
@@ -1716,12 +1708,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	  _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(), __roan);
-	      _M_leftmost() = _S_minimum(_M_root());
-	      _M_rightmost() = _S_maximum(_M_root());
-	      _M_impl._M_node_count = __x._M_impl._M_node_count;
-	    }
+	    _M_root() = _M_copy(__x, __roan);
 	}
 
       return *this;

Re: Default associative containers constructors/destructor/assignment

[Jonathan Wakely]

On 20/11/16 19:14 +0100, François Dumont wrote:
>Talking about _M_color I just realize that move semantic doesn't copy 
>_M_color. Shouldn't we capture it along with all the other _M_header 
>information ?

Is it needed? I think the current code does the right thing, doesn't
it? I'd prefer not to change it without a testcase showing why we need
to.

>>Am I missing some other reason that inheritance is used here?
>
>The purpose of this patch is to rely more on compiler especially in 
>regards to the noexcept qualifications. This is why I started 
>isolating each ressource in its own class in charge of its 
>specificities. And I leave to the compiler the work of combining those 
>types. However I also wanted to limit the impact of this patch on the 
>_Rb_tree and still be able to use things like 
>this->_M_impl._M_node_count or this->_M_impl._M_header. So the usage 
>of inheritance.

OK.

I think I've convinced myself that using inheritance here can't alter
the layout in any way (I was worried about reuse of tail padding, for
example).

>Tested under x86_64 Linux, ok to commit ?

OK for trunk.

>For info, I would like to propose another bunch of simplifications of 
>_Rb_tree, see other patch attached. Do you want me to propose it in 
>another mail ?

The patch is safe enough for stage 3, so please go ahead and commit
that one too, but we need to stop refactoring these things now. Any
more changes like this need to wait for stage 1.

Thanks for this work.

Re: Default associative containers constructors/destructor/assignment

[François Dumont]

On 06/12/2016 12:54, Jonathan Wakely wrote:
> On 20/11/16 19:14 +0100, François Dumont wrote:
>> Talking about _M_color I just realize that move semantic doesn't copy 
>> _M_color. Shouldn't we capture it along with all the other _M_header 
>> information ?
>
> Is it needed? I think the current code does the right thing, doesn't
> it? I'd prefer not to change it without a testcase showing why we need
> to.

I was hoping you knew it. So I kept it unchanged and will add to my TODO 
to check this.

Committed now.

François

Re: Default associative containers constructors/destructor/assignment

[Jonathan Wakely]

On 08/12/16 21:40 +0100, François Dumont wrote:
>On 06/12/2016 12:54, Jonathan Wakely wrote:
>>On 20/11/16 19:14 +0100, François Dumont wrote:
>>>Talking about _M_color I just realize that move semantic doesn't 
>>>copy _M_color. Shouldn't we capture it along with all the other 
>>>_M_header information ?
>>
>>Is it needed? I think the current code does the right thing, doesn't
>>it? I'd prefer not to change it without a testcase showing why we need
>>to.
>
>I was hoping you knew it. So I kept it unchanged and will add to my 
>TODO to check this.

I think it's OK already :-)

>Committed now.

Thanks!