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.