Rb_tree constructor optimization

Rb_tree constructor optimization

[François Dumont]

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

Hi

If not told otherwise I'll commit attached patch tomorrow.

Already discussed here:

https://gcc.gnu.org/ml/libstdc++/2017-10/msg00053.html

François


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

diff --git a/libstdc++-v3/include/bits/stl_map.h b/libstdc++-v3/include/bits/stl_map.h
index a4a026e..2b8fd27 100644
--- a/libstdc++-v3/include/bits/stl_map.h
+++ b/libstdc++-v3/include/bits/stl_map.h
@@ -240,8 +240,8 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
 
       /// Allocator-extended move constructor.
       map(map&& __m, const allocator_type& __a)
-      noexcept(is_nothrow_copy_constructible<_Compare>::value
-	       && _Alloc_traits::_S_always_equal())
+      noexcept( noexcept(
+	_Rep_type(std::move(__m._M_t), declval<_Pair_alloc_type>())) )
       : _M_t(std::move(__m._M_t), _Pair_alloc_type(__a)) { }
 
       /// Allocator-extended initialier-list constructor.
diff --git a/libstdc++-v3/include/bits/stl_multimap.h b/libstdc++-v3/include/bits/stl_multimap.h
index fc8f454..b9289ab 100644
--- a/libstdc++-v3/include/bits/stl_multimap.h
+++ b/libstdc++-v3/include/bits/stl_multimap.h
@@ -237,8 +237,8 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
 
       /// Allocator-extended move constructor.
       multimap(multimap&& __m, const allocator_type& __a)
-      noexcept(is_nothrow_copy_constructible<_Compare>::value
-	       && _Alloc_traits::_S_always_equal())
+      noexcept( noexcept(
+	_Rep_type(std::move(__m._M_t), declval<_Pair_alloc_type>())) )
       : _M_t(std::move(__m._M_t), _Pair_alloc_type(__a)) { }
 
       /// Allocator-extended initialier-list constructor.
diff --git a/libstdc++-v3/include/bits/stl_multiset.h b/libstdc++-v3/include/bits/stl_multiset.h
index f41f56c..afaf3b6 100644
--- a/libstdc++-v3/include/bits/stl_multiset.h
+++ b/libstdc++-v3/include/bits/stl_multiset.h
@@ -253,8 +253,8 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
 
       /// Allocator-extended move constructor.
       multiset(multiset&& __m, const allocator_type& __a)
-      noexcept(is_nothrow_copy_constructible<_Compare>::value
-	       && _Alloc_traits::_S_always_equal())
+      noexcept( noexcept(
+	_Rep_type(std::move(__m._M_t), declval<_Key_alloc_type>())) )
       : _M_t(std::move(__m._M_t), _Key_alloc_type(__a)) { }
 
       /// Allocator-extended initialier-list constructor.
diff --git a/libstdc++-v3/include/bits/stl_set.h b/libstdc++-v3/include/bits/stl_set.h
index 2e332ef..fc6d1f7 100644
--- a/libstdc++-v3/include/bits/stl_set.h
+++ b/libstdc++-v3/include/bits/stl_set.h
@@ -257,8 +257,8 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
 
       /// Allocator-extended move constructor.
       set(set&& __x, const allocator_type& __a)
-      noexcept(is_nothrow_copy_constructible<_Compare>::value
-	       && _Alloc_traits::_S_always_equal())
+      noexcept( noexcept(
+	_Rep_type(std::move(__x._M_t), declval<_Key_alloc_type>())) )
       : _M_t(std::move(__x._M_t), _Key_alloc_type(__a)) { }
 
       /// Allocator-extended initialier-list constructor.
diff --git a/libstdc++-v3/include/bits/stl_tree.h b/libstdc++-v3/include/bits/stl_tree.h
index d0a8448..732ac55 100644
--- a/libstdc++-v3/include/bits/stl_tree.h
+++ b/libstdc++-v3/include/bits/stl_tree.h
@@ -715,6 +715,12 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 #else
 	  _Rb_tree_impl(_Rb_tree_impl&&) = default;
 
+	  _Rb_tree_impl(_Rb_tree_impl&& __x, _Node_allocator&& __a)
+	  : _Node_allocator(std::move(__a)),
+	    _Base_key_compare(std::move(__x)),
+	    _Rb_tree_header(std::move(__x))
+	  { }
+
 	  _Rb_tree_impl(const _Key_compare& __comp, _Node_allocator&& __a)
 	  : _Node_allocator(std::move(__a)), _Base_key_compare(__comp)
 	  { }
@@ -955,10 +961,32 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
       _Rb_tree(_Rb_tree&&) = default;
 
       _Rb_tree(_Rb_tree&& __x, const allocator_type& __a)
+      noexcept( noexcept(
+	_Rb_tree(std::move(__x), declval<_Node_allocator>())) )
       : _Rb_tree(std::move(__x), _Node_allocator(__a))
       { }
 
-      _Rb_tree(_Rb_tree&& __x, _Node_allocator&& __a);
+    private:
+      _Rb_tree(_Rb_tree&& __x, _Node_allocator&& __a, true_type)
+      noexcept(is_nothrow_move_constructible<_Rb_tree_impl<_Compare>>::value)
+      : _M_impl(std::move(__x._M_impl), std::move(__a))
+      { }
+
+      _Rb_tree(_Rb_tree&& __x, _Node_allocator&& __a, false_type)
+      : _M_impl(__x._M_impl._M_key_compare, std::move(__a))
+      {
+	if (__x._M_root() != nullptr)
+	  _M_move_data(__x, false_type{});
+      }
+
+    public:
+      _Rb_tree(_Rb_tree&& __x, _Node_allocator&& __a)
+      noexcept( noexcept(
+	_Rb_tree(std::move(__x), std::move(__a),
+		 declval<typename _Alloc_traits::is_always_equal>()) ) )
+      : _Rb_tree(std::move(__x), std::move(__a),
+		 typename _Alloc_traits::is_always_equal{})
+      { }
 #endif
 
       ~_Rb_tree() _GLIBCXX_NOEXCEPT
@@ -1358,22 +1386,22 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
     private:
       // Move elements from container with equal allocator.
       void
-      _M_move_data(_Rb_tree& __x, std::true_type)
+      _M_move_data(_Rb_tree& __x, 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.
       void
-      _M_move_data(_Rb_tree&, std::false_type);
+      _M_move_data(_Rb_tree&, false_type);
 
       // Move assignment from container with equal allocator.
       void
-      _M_move_assign(_Rb_tree&, std::true_type);
+      _M_move_assign(_Rb_tree&, true_type);
 
       // Move assignment from container with possibly non-equal allocator,
       // which might result in a copy not a move.
       void
-      _M_move_assign(_Rb_tree&, std::false_type);
+      _M_move_assign(_Rb_tree&, false_type);
 #endif
 
 #if __cplusplus > 201402L
@@ -1601,23 +1629,12 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 #if __cplusplus >= 201103L
   template<typename _Key, typename _Val, typename _KeyOfValue,
 	   typename _Compare, typename _Alloc>
-    _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
-    _Rb_tree(_Rb_tree&& __x, _Node_allocator&& __a)
-    : _M_impl(__x._M_impl._M_key_compare, std::move(__a))
-    {
-      using __eq = typename _Alloc_traits::is_always_equal;
-      if (__x._M_root() != nullptr)
-	_M_move_data(__x, __eq());
-    }
-
-  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)
+    _M_move_data(_Rb_tree& __x, false_type)
     {
       if (_M_get_Node_allocator() == __x._M_get_Node_allocator())
-	_M_move_data(__x, std::true_type());
+	_M_move_data(__x, true_type());
       else
 	{
 	  _Alloc_node __an(*this);
@@ -1639,7 +1656,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
     {
       clear();
       if (__x._M_root() != nullptr)
-	_M_move_data(__x, std::true_type());
+	_M_move_data(__x, true_type());
       std::__alloc_on_move(_M_get_Node_allocator(),
 			   __x._M_get_Node_allocator());
     }
diff --git a/libstdc++-v3/include/debug/map.h b/libstdc++-v3/include/debug/map.h
index 414b4dc..9edb7dc 100644
--- a/libstdc++-v3/include/debug/map.h
+++ b/libstdc++-v3/include/debug/map.h
@@ -105,8 +105,10 @@ namespace __debug
       : _Base(__m, __a) { }
 
       map(map&& __m, const allocator_type& __a)
+      noexcept( noexcept(_Base(std::move(__m._M_base()), __a)) )
       : _Safe(std::move(__m._M_safe()), __a),
-	_Base(std::move(__m._M_base()), __a) { }
+	_Base(std::move(__m._M_base()), __a)
+      { }
 
       map(initializer_list<value_type> __l, const allocator_type& __a)
       : _Base(__l, __a) { }
diff --git a/libstdc++-v3/include/debug/multimap.h b/libstdc++-v3/include/debug/multimap.h
index 8d6358b..9ee3809 100644
--- a/libstdc++-v3/include/debug/multimap.h
+++ b/libstdc++-v3/include/debug/multimap.h
@@ -105,6 +105,7 @@ namespace __debug
       : _Base(__m, __a) { }
 
       multimap(multimap&& __m, const allocator_type& __a)
+      noexcept( noexcept(_Base(std::move(__m._M_base()), __a)) )
       : _Safe(std::move(__m._M_safe()), __a),
 	_Base(std::move(__m._M_base()), __a) { }
 
diff --git a/libstdc++-v3/include/debug/multiset.h b/libstdc++-v3/include/debug/multiset.h
index 4e1406e..0be14d7 100644
--- a/libstdc++-v3/include/debug/multiset.h
+++ b/libstdc++-v3/include/debug/multiset.h
@@ -104,6 +104,7 @@ namespace __debug
       : _Base(__m, __a) { }
 
       multiset(multiset&& __m, const allocator_type& __a)
+      noexcept( noexcept(_Base(std::move(__m._M_base()), __a)) )
       : _Safe(std::move(__m._M_safe()), __a),
 	_Base(std::move(__m._M_base()), __a) { }
 
diff --git a/libstdc++-v3/include/debug/set.h b/libstdc++-v3/include/debug/set.h
index a886860..7f24a83 100644
--- a/libstdc++-v3/include/debug/set.h
+++ b/libstdc++-v3/include/debug/set.h
@@ -104,6 +104,7 @@ namespace __debug
       : _Base(__x, __a) { }
 
       set(set&& __x, const allocator_type& __a)
+      noexcept( noexcept(_Base(std::move(__x._M_base()), __a)) )
       : _Safe(std::move(__x._M_safe()), __a),
 	_Base(std::move(__x._M_base()), __a) { }
 
diff --git a/libstdc++-v3/testsuite/23_containers/map/cons/noexcept_move_construct.cc b/libstdc++-v3/testsuite/23_containers/map/cons/noexcept_move_construct.cc
index 0041408..8791eb8 100644
--- a/libstdc++-v3/testsuite/23_containers/map/cons/noexcept_move_construct.cc
+++ b/libstdc++-v3/testsuite/23_containers/map/cons/noexcept_move_construct.cc
@@ -23,4 +23,25 @@
 
 typedef std::map<int, int> mtype;
 
-static_assert(std::is_nothrow_move_constructible<mtype>::value, "Error");
+static_assert( std::is_nothrow_move_constructible<mtype>::value,
+	       "noexcept move constructor" );
+static_assert( noexcept( mtype(std::declval<mtype>(),
+		std::declval<const typename mtype::allocator_type&>()) ),
+	       "noexcept move constructor with allocator" );
+
+struct ExceptLess
+{
+  ExceptLess() = default;
+  ExceptLess(const ExceptLess&) /* noexcept */
+  { }
+
+  bool
+  operator()(int l, int r) const
+  { return l < r; }
+};
+
+typedef std::map<int, int, ExceptLess> emtype;
+
+static_assert( !noexcept( emtype(std::declval<emtype>(),
+		std::declval<const typename emtype::allocator_type&>()) ),
+	       "except move constructor with allocator" );
diff --git a/libstdc++-v3/testsuite/23_containers/multimap/cons/noexcept_move_construct.cc b/libstdc++-v3/testsuite/23_containers/multimap/cons/noexcept_move_construct.cc
index 0319a61..9b81666 100644
--- a/libstdc++-v3/testsuite/23_containers/multimap/cons/noexcept_move_construct.cc
+++ b/libstdc++-v3/testsuite/23_containers/multimap/cons/noexcept_move_construct.cc
@@ -23,4 +23,25 @@
 
 typedef std::multimap<int, int> mmtype;
 
-static_assert(std::is_nothrow_move_constructible<mmtype>::value, "Error");
+static_assert( std::is_nothrow_move_constructible<mmtype>::value,
+	       "noexcept move constructor" );
+static_assert( noexcept( mmtype(std::declval<mmtype>(),
+		std::declval<const typename mmtype::allocator_type&>()) ),
+	       "noexcept move constructor with allocator" );
+
+struct ExceptLess
+{
+  ExceptLess() = default;
+  ExceptLess(const ExceptLess&) /* noexcept */
+  { }
+
+  bool
+  operator()(int l, int r) const
+  { return l < r; }
+};
+
+typedef std::multimap<int, int, ExceptLess> emmtype;
+
+static_assert( !noexcept( emmtype(std::declval<emmtype>(),
+		std::declval<const typename emmtype::allocator_type&>()) ),
+	       "except move constructor with allocator" );
diff --git a/libstdc++-v3/testsuite/23_containers/multiset/cons/noexcept_move_construct.cc b/libstdc++-v3/testsuite/23_containers/multiset/cons/noexcept_move_construct.cc
index b1c6dd5..f6dd42c 100644
--- a/libstdc++-v3/testsuite/23_containers/multiset/cons/noexcept_move_construct.cc
+++ b/libstdc++-v3/testsuite/23_containers/multiset/cons/noexcept_move_construct.cc
@@ -23,4 +23,25 @@
 
 typedef std::multiset<int> mstype;
 
-static_assert(std::is_nothrow_move_constructible<mstype>::value, "Error");
+static_assert( std::is_nothrow_move_constructible<mstype>::value,
+	       "noexcept move constructor" );
+static_assert( noexcept( mstype(std::declval<mstype>(),
+		std::declval<const typename mstype::allocator_type&>()) ),
+	       "noexcept move constructor with allocator" );
+
+struct ExceptLess
+{
+  ExceptLess() = default;
+  ExceptLess(const ExceptLess&) /* noexcept */
+  { }
+
+  bool
+  operator()(int l, int r) const
+  { return l < r; }
+};
+
+typedef std::multiset<int, ExceptLess> emstype;
+
+static_assert( !noexcept( emstype(std::declval<emstype>(),
+		std::declval<const typename emstype::allocator_type&>()) ),
+	       "except move constructor with allocator" );
diff --git a/libstdc++-v3/testsuite/23_containers/set/cons/noexcept_move_construct.cc b/libstdc++-v3/testsuite/23_containers/set/cons/noexcept_move_construct.cc
index a7de0ef..0a6f2da 100644
--- a/libstdc++-v3/testsuite/23_containers/set/cons/noexcept_move_construct.cc
+++ b/libstdc++-v3/testsuite/23_containers/set/cons/noexcept_move_construct.cc
@@ -23,4 +23,25 @@
 
 typedef std::set<int> stype;
 
-static_assert(std::is_nothrow_move_constructible<stype>::value, "Error");
+static_assert( std::is_nothrow_move_constructible<stype>::value,
+	       "noexcept move constructor" );
+static_assert( noexcept( stype(std::declval<stype>(),
+		std::declval<const typename stype::allocator_type&>()) ),
+	       "noexcept move constructor with allocator" );
+
+struct ExceptLess
+{
+  ExceptLess() = default;
+  ExceptLess(const ExceptLess&) /* noexcept */
+  { }
+
+  bool
+  operator()(int l, int r) const
+  { return l < r; }
+};
+
+typedef std::set<int, ExceptLess> estype;
+
+static_assert( !noexcept( estype(std::declval<estype>(),
+		std::declval<const typename estype::allocator_type&>()) ),
+	       "except move constructor with allocator" );

Re: Rb_tree constructor optimization

[Ville Voutilainen]

On 1 May 2018 at 22:56, François Dumont <frs.dumont@gmail.com> wrote:
> Hi
>
> If not told otherwise I'll commit attached patch tomorrow.


Commit it where? The 8.1 release is not out yet, so we shouldn't be
pushing new stuff onto trunk yet.
Nor should we push such stuff into the release branch.

Re: Rb_tree constructor optimization

[Jakub Jelinek]

On Wed, May 02, 2018 at 12:23:27AM +0300, Ville Voutilainen wrote:
> On 1 May 2018 at 22:56, François Dumont <frs.dumont@gmail.com> wrote:
> > Hi
> >
> > If not told otherwise I'll commit attached patch tomorrow.
> 
> 
> Commit it where? The 8.1 release is not out yet, so we shouldn't be
> pushing new stuff onto trunk yet.
> Nor should we push such stuff into the release branch.

It is ok to commit stuff to trunk now, just not 8 branch.

	Jakub

Re: Rb_tree constructor optimization

[Ville Voutilainen]

On 2 May 2018 at 00:28, Jakub Jelinek <jakub@redhat.com> wrote:
> On Wed, May 02, 2018 at 12:23:27AM +0300, Ville Voutilainen wrote:
>> On 1 May 2018 at 22:56, François Dumont <frs.dumont@gmail.com> wrote:
>> > Hi
>> >
>> > If not told otherwise I'll commit attached patch tomorrow.
>>
>>
>> Commit it where? The 8.1 release is not out yet, so we shouldn't be
>> pushing new stuff onto trunk yet.
>> Nor should we push such stuff into the release branch.
>
> It is ok to commit stuff to trunk now, just not 8 branch.


All right; given that, the patch still needs maintainer approval,
which it doesn't have yet.

Re: Rb_tree constructor optimization

[Jonathan Wakely]

On 02/05/18 00:47 +0300, Ville Voutilainen wrote:
>On 2 May 2018 at 00:28, Jakub Jelinek <jakub@redhat.com> wrote:
>> On Wed, May 02, 2018 at 12:23:27AM +0300, Ville Voutilainen wrote:
>>> On 1 May 2018 at 22:56, François Dumont <frs.dumont@gmail.com> wrote:
>>> > Hi
>>> >
>>> > If not told otherwise I'll commit attached patch tomorrow.
>>>
>>>
>>> Commit it where? The 8.1 release is not out yet, so we shouldn't be
>>> pushing new stuff onto trunk yet.
>>> Nor should we push such stuff into the release branch.
>>
>> It is ok to commit stuff to trunk now, just not 8 branch.
>
>
>All right; given that, the patch still needs maintainer approval,
>which it doesn't have yet.

Oh, good point - I assumed from François's mail it was something we'd
agreed to commit but not until stage 1.

So it still needs a review then.

Re: Rb_tree constructor optimization

[Jonathan Wakely]

On 01/05/18 21:56 +0200, François Dumont wrote:
>Hi
>
>If not told otherwise I'll commit attached patch tomorrow.

Please do not commit it, see below.

>Already discussed here:
>
>https://gcc.gnu.org/ml/libstdc++/2017-10/msg00053.html

There's no changelog entry with the patch, so to recap, the changes
are:

- noexcept specifications are automatically deduced instead of being
  stated explicitly.
 
- The allocator-extended move constructors get correct exception
  specifications in Debug Mode (consistent with normal mode). This
  should be done anyway, independent of any other changes.

- We avoid a `if (__x._M_root() != nullptr)` branch in the case where
  the allocator-extended move constructor is used with an always-equal
  allocator, right?


Deducing the noexcept specifications probably has a (small?) impact on
compilation speed, as currently the allocator-extended move
constructors have:

-      noexcept(is_nothrow_copy_constructible<_Compare>::value
-	       && _Alloc_traits::_S_always_equal())

After the patch they have to determine the noexcept-ness of the
_Rep_type constructor taking allocator_type, which has to determine
the noexcept-ness of the _Rep_type constructor taking a
_Node_allocator, which has to determine the noexcept-ness of the
constructor it dispatches to depending on _S_always_equal(), which is
simply:

+      noexcept(is_nothrow_move_constructible<_Rb_tree_impl<_Compare>>::value)

So instead of just using that value in the first place we have to
perform three rounds of overload resolution to find the right
constructor and then check its exception specification. And then we
get the wrong answer (see below).

Compilation time for containers is already **much** slower since the
allocator-extended constructors were added for GCC 5.x, despite very
few people ever using those constructors. This patch seems to require
even more work from the compiler to parse constructors nobody uses.


>François
>

>diff --git a/libstdc++-v3/include/bits/stl_map.h b/libstdc++-v3/include/bits/stl_map.h
>index a4a026e..2b8fd27 100644
>--- a/libstdc++-v3/include/bits/stl_map.h
>+++ b/libstdc++-v3/include/bits/stl_map.h
>@@ -240,8 +240,8 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
> 
>       /// Allocator-extended move constructor.
>       map(map&& __m, const allocator_type& __a)
>-      noexcept(is_nothrow_copy_constructible<_Compare>::value
>-	       && _Alloc_traits::_S_always_equal())
>+      noexcept( noexcept(
>+	_Rep_type(std::move(__m._M_t), declval<_Pair_alloc_type>())) )

All these calls to declval need to be qualified to avoid ADL.

It seems strange to have a mix of real values and declval expressions,
rather than:

	_Rep_type(std::declval<_Rep_type>(), std::declval<_Pair_alloc_type>())) )



>       : _M_t(std::move(__m._M_t), _Pair_alloc_type(__a)) { }
> 
>       /// Allocator-extended initialier-list constructor.
>diff --git a/libstdc++-v3/include/bits/stl_multimap.h b/libstdc++-v3/include/bits/stl_multimap.h
>index fc8f454..b9289ab 100644
>--- a/libstdc++-v3/include/bits/stl_multimap.h
>+++ b/libstdc++-v3/include/bits/stl_multimap.h
>@@ -237,8 +237,8 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
> 
>       /// Allocator-extended move constructor.
>       multimap(multimap&& __m, const allocator_type& __a)
>-      noexcept(is_nothrow_copy_constructible<_Compare>::value
>-	       && _Alloc_traits::_S_always_equal())
>+      noexcept( noexcept(
>+	_Rep_type(std::move(__m._M_t), declval<_Pair_alloc_type>())) )
>       : _M_t(std::move(__m._M_t), _Pair_alloc_type(__a)) { }
> 
>       /// Allocator-extended initialier-list constructor.
>diff --git a/libstdc++-v3/include/bits/stl_multiset.h b/libstdc++-v3/include/bits/stl_multiset.h
>index f41f56c..afaf3b6 100644
>--- a/libstdc++-v3/include/bits/stl_multiset.h
>+++ b/libstdc++-v3/include/bits/stl_multiset.h
>@@ -253,8 +253,8 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
> 
>       /// Allocator-extended move constructor.
>       multiset(multiset&& __m, const allocator_type& __a)
>-      noexcept(is_nothrow_copy_constructible<_Compare>::value
>-	       && _Alloc_traits::_S_always_equal())
>+      noexcept( noexcept(
>+	_Rep_type(std::move(__m._M_t), declval<_Key_alloc_type>())) )
>       : _M_t(std::move(__m._M_t), _Key_alloc_type(__a)) { }
> 
>       /// Allocator-extended initialier-list constructor.
>diff --git a/libstdc++-v3/include/bits/stl_set.h b/libstdc++-v3/include/bits/stl_set.h
>index 2e332ef..fc6d1f7 100644
>--- a/libstdc++-v3/include/bits/stl_set.h
>+++ b/libstdc++-v3/include/bits/stl_set.h
>@@ -257,8 +257,8 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
> 
>       /// Allocator-extended move constructor.
>       set(set&& __x, const allocator_type& __a)
>-      noexcept(is_nothrow_copy_constructible<_Compare>::value
>-	       && _Alloc_traits::_S_always_equal())
>+      noexcept( noexcept(
>+	_Rep_type(std::move(__x._M_t), declval<_Key_alloc_type>())) )
>       : _M_t(std::move(__x._M_t), _Key_alloc_type(__a)) { }
> 
>       /// Allocator-extended initialier-list constructor.
>diff --git a/libstdc++-v3/include/bits/stl_tree.h b/libstdc++-v3/include/bits/stl_tree.h
>index d0a8448..732ac55 100644
>--- a/libstdc++-v3/include/bits/stl_tree.h
>+++ b/libstdc++-v3/include/bits/stl_tree.h
>@@ -715,6 +715,12 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
> #else
> 	  _Rb_tree_impl(_Rb_tree_impl&&) = default;
> 
>+	  _Rb_tree_impl(_Rb_tree_impl&& __x, _Node_allocator&& __a)
>+	  : _Node_allocator(std::move(__a)),
>+	    _Base_key_compare(std::move(__x)),
>+	    _Rb_tree_header(std::move(__x))
>+	  { }
>+
> 	  _Rb_tree_impl(const _Key_compare& __comp, _Node_allocator&& __a)
> 	  : _Node_allocator(std::move(__a)), _Base_key_compare(__comp)
> 	  { }
>@@ -955,10 +961,32 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
>       _Rb_tree(_Rb_tree&&) = default;
> 
>       _Rb_tree(_Rb_tree&& __x, const allocator_type& __a)
>+      noexcept( noexcept(
>+	_Rb_tree(std::move(__x), declval<_Node_allocator>())) )
>       : _Rb_tree(std::move(__x), _Node_allocator(__a))
>       { }
> 
>-      _Rb_tree(_Rb_tree&& __x, _Node_allocator&& __a);
>+    private:
>+      _Rb_tree(_Rb_tree&& __x, _Node_allocator&& __a, true_type)
>+      noexcept(is_nothrow_move_constructible<_Rb_tree_impl<_Compare>>::value)

This is wrong.

The result of is_nothrow_move_constructible<_Rb_tree_impl<_Compare>>
depends on this constructor:

  _Rb_tree_impl(_Rb_tree_impl&&) = default;

That constructor depends on the allocator type, which might not be
noexcept, but it's undefined behaviour for it to throw. We don't want
the exception-specification to depend on the allocator, otherwise we
fail this test on the line marked XXX:

template<typename T>
struct Alloc : std::allocator<T>
{
  Alloc() { }
  Alloc(const Alloc&) { }
  template<typename U> Alloc(const Alloc<U>&) { }

  template<typename U> struct rebind { using other = Alloc<U>; };
};

template<typename A>
using Set = std::set<int, std::less<int>, A>;

template<typename A>
  using Test = std::is_nothrow_constructible<Set<A>, Set<A>, A>;

int main()
{
  static_assert(Test<std::allocator<int>>::value, "");
  static_assert(Test<Alloc<int>>::value, "");  // XXX
}


The changes to deduce the exception-specifications seem to make the
code more fragile -- do we really want to make those changes?


>+      : _M_impl(std::move(__x._M_impl), std::move(__a))
>+      { }
>+
>+      _Rb_tree(_Rb_tree&& __x, _Node_allocator&& __a, false_type)
>+      : _M_impl(__x._M_impl._M_key_compare, std::move(__a))
>+      {
>+	if (__x._M_root() != nullptr)
>+	  _M_move_data(__x, false_type{});
>+      }
>+
>+    public:
>+      _Rb_tree(_Rb_tree&& __x, _Node_allocator&& __a)
>+      noexcept( noexcept(
>+	_Rb_tree(std::move(__x), std::move(__a),
>+		 declval<typename _Alloc_traits::is_always_equal>()) ) )
>+      : _Rb_tree(std::move(__x), std::move(__a),
>+		 typename _Alloc_traits::is_always_equal{})
>+      { }
> #endif


>diff --git a/libstdc++-v3/include/debug/map.h b/libstdc++-v3/include/debug/map.h
>index 414b4dc..9edb7dc 100644
>--- a/libstdc++-v3/include/debug/map.h
>+++ b/libstdc++-v3/include/debug/map.h
>@@ -105,8 +105,10 @@ namespace __debug
>       : _Base(__m, __a) { }
> 
>       map(map&& __m, const allocator_type& __a)
>+      noexcept( noexcept(_Base(std::move(__m._M_base()), __a)) )
>       : _Safe(std::move(__m._M_safe()), __a),
>-	_Base(std::move(__m._M_base()), __a) { }
>+	_Base(std::move(__m._M_base()), __a)
>+      { }

This part of the patch is actually a bug fix, making the debug mode
consistent with normal mode.

>diff --git a/libstdc++-v3/testsuite/23_containers/map/cons/noexcept_move_construct.cc b/libstdc++-v3/testsuite/23_containers/map/cons/noexcept_move_construct.cc
>index 0041408..8791eb8 100644
>--- a/libstdc++-v3/testsuite/23_containers/map/cons/noexcept_move_construct.cc
>+++ b/libstdc++-v3/testsuite/23_containers/map/cons/noexcept_move_construct.cc
>@@ -23,4 +23,25 @@
> 
> typedef std::map<int, int> mtype;
> 
>-static_assert(std::is_nothrow_move_constructible<mtype>::value, "Error");
>+static_assert( std::is_nothrow_move_constructible<mtype>::value,
>+	       "noexcept move constructor" );
>+static_assert( noexcept( mtype(std::declval<mtype>(),
>+		std::declval<const typename mtype::allocator_type&>()) ),

This can use std::is_nothrow_constructible

>+	       "noexcept move constructor with allocator" );
>+
>+struct ExceptLess

Please name this "ThrowingLess" instead of "ExceptLess", I think
that's more descriptive.

>+{
>+  ExceptLess() = default;
>+  ExceptLess(const ExceptLess&) /* noexcept */
>+  { }
>+
>+  bool
>+  operator()(int l, int r) const
>+  { return l < r; }
>+};
>+
>+typedef std::map<int, int, ExceptLess> emtype;
>+
>+static_assert( !noexcept( emtype(std::declval<emtype>(),
>+		std::declval<const typename emtype::allocator_type&>()) ),

This can use std::is_nothrow_constructible too.

Same comments for the other tests.

Re: Rb_tree constructor optimization

[François Dumont]

On 02/05/2018 13:49, Jonathan Wakely wrote:
> On 01/05/18 21:56 +0200, François Dumont wrote:
>> Hi
>>
>> If not told otherwise I'll commit attached patch tomorrow.
>
> Please do not commit it, see below.
>
>> Already discussed here:
>>
>> https://gcc.gnu.org/ml/libstdc++/2017-10/msg00053.html
>
> There's no changelog entry with the patch, so to recap, the changes
> are:
>
> - noexcept specifications are automatically deduced instead of being
>  stated explicitly.
Yes, it helps to make sure rb tree code is correct and it avoids usage 
of non-standard _S_always_equal. We could even use std::allocator_traits 
in C++11.
>
> - The allocator-extended move constructors get correct exception
>  specifications in Debug Mode (consistent with normal mode). This
>  should be done anyway, independent of any other changes.
Yes, I realized it after I wrote the tests to validate the noexcept 
qualification.
>
> - We avoid a `if (__x._M_root() != nullptr)` branch in the case where
>  the allocator-extended move constructor is used with an always-equal
>  allocator, right?
Yes, this is consistent with most of the other containers doing the same.
>
>
> Deducing the noexcept specifications probably has a (small?) impact on
> compilation speed, as currently the allocator-extended move
> constructors have:
>
> - noexcept(is_nothrow_copy_constructible<_Compare>::value
> -           && _Alloc_traits::_S_always_equal())
>
> After the patch they have to determine the noexcept-ness of the
> _Rep_type constructor taking allocator_type, which has to determine
> the noexcept-ness of the _Rep_type constructor taking a
> _Node_allocator, which has to determine the noexcept-ness of the
> constructor it dispatches to depending on _S_always_equal(), which is
> simply:
>
> + noexcept(is_nothrow_move_constructible<_Rb_tree_impl<_Compare>>::value)
>
> So instead of just using that value in the first place we have to
> perform three rounds of overload resolution to find the right
> constructor and then check its exception specification. And then we
> get the wrong answer (see below).
>
> Compilation time for containers is already **much** slower since the
> allocator-extended constructors were added for GCC 5.x, despite very
> few people ever using those constructors. This patch seems to require
> even more work from the compiler to parse constructors nobody uses.

I must confess that I didn't consider this aspect of the patch. I just 
wanted the code to be more logical. I even wonder why it wasn't done 
this way, now I know. Could this compilation cost be testable ? Isn't 
the compiler doing this work only if the constructor is being used ? Or 
even just only if it needs to know about the noexcept qualification ?

>
>
>> François
>>
>
>> diff --git a/libstdc++-v3/include/bits/stl_map.h 
>> b/libstdc++-v3/include/bits/stl_map.h
>> index a4a026e..2b8fd27 100644
>> --- a/libstdc++-v3/include/bits/stl_map.h
>> +++ b/libstdc++-v3/include/bits/stl_map.h
>> @@ -240,8 +240,8 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
>>
>>       /// Allocator-extended move constructor.
>>       map(map&& __m, const allocator_type& __a)
>> - noexcept(is_nothrow_copy_constructible<_Compare>::value
>> -           && _Alloc_traits::_S_always_equal())
>> +      noexcept( noexcept(
>> +    _Rep_type(std::move(__m._M_t), declval<_Pair_alloc_type>())) )
>
> All these calls to declval need to be qualified to avoid ADL.
>
> It seems strange to have a mix of real values and declval expressions,
> rather than:
>
>     _Rep_type(std::declval<_Rep_type>(), 
> std::declval<_Pair_alloc_type>())) )
>
     Has std::declval<>() been modified recently ? I think I tried that 
and it was working but after a while it started to fail so I had to 
replace with the other expression. I'll try it again if I eventually 
commit this.
>
>
>>       : _M_t(std::move(__m._M_t), _Pair_alloc_type(__a)) { }
>>
>>       /// Allocator-extended initialier-list constructor.
>> diff --git a/libstdc++-v3/include/bits/stl_multimap.h 
>> b/libstdc++-v3/include/bits/stl_multimap.h
>> index fc8f454..b9289ab 100644
>> --- a/libstdc++-v3/include/bits/stl_multimap.h
>> +++ b/libstdc++-v3/include/bits/stl_multimap.h
>> @@ -237,8 +237,8 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
>>
>>       /// Allocator-extended move constructor.
>>       multimap(multimap&& __m, const allocator_type& __a)
>> - noexcept(is_nothrow_copy_constructible<_Compare>::value
>> -           && _Alloc_traits::_S_always_equal())
>> +      noexcept( noexcept(
>> +    _Rep_type(std::move(__m._M_t), declval<_Pair_alloc_type>())) )
>>       : _M_t(std::move(__m._M_t), _Pair_alloc_type(__a)) { }
>>
>>       /// Allocator-extended initialier-list constructor.
>> diff --git a/libstdc++-v3/include/bits/stl_multiset.h 
>> b/libstdc++-v3/include/bits/stl_multiset.h
>> index f41f56c..afaf3b6 100644
>> --- a/libstdc++-v3/include/bits/stl_multiset.h
>> +++ b/libstdc++-v3/include/bits/stl_multiset.h
>> @@ -253,8 +253,8 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
>>
>>       /// Allocator-extended move constructor.
>>       multiset(multiset&& __m, const allocator_type& __a)
>> - noexcept(is_nothrow_copy_constructible<_Compare>::value
>> -           && _Alloc_traits::_S_always_equal())
>> +      noexcept( noexcept(
>> +    _Rep_type(std::move(__m._M_t), declval<_Key_alloc_type>())) )
>>       : _M_t(std::move(__m._M_t), _Key_alloc_type(__a)) { }
>>
>>       /// Allocator-extended initialier-list constructor.
>> diff --git a/libstdc++-v3/include/bits/stl_set.h 
>> b/libstdc++-v3/include/bits/stl_set.h
>> index 2e332ef..fc6d1f7 100644
>> --- a/libstdc++-v3/include/bits/stl_set.h
>> +++ b/libstdc++-v3/include/bits/stl_set.h
>> @@ -257,8 +257,8 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
>>
>>       /// Allocator-extended move constructor.
>>       set(set&& __x, const allocator_type& __a)
>> - noexcept(is_nothrow_copy_constructible<_Compare>::value
>> -           && _Alloc_traits::_S_always_equal())
>> +      noexcept( noexcept(
>> +    _Rep_type(std::move(__x._M_t), declval<_Key_alloc_type>())) )
>>       : _M_t(std::move(__x._M_t), _Key_alloc_type(__a)) { }
>>
>>       /// Allocator-extended initialier-list constructor.
>> diff --git a/libstdc++-v3/include/bits/stl_tree.h 
>> b/libstdc++-v3/include/bits/stl_tree.h
>> index d0a8448..732ac55 100644
>> --- a/libstdc++-v3/include/bits/stl_tree.h
>> +++ b/libstdc++-v3/include/bits/stl_tree.h
>> @@ -715,6 +715,12 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
>> #else
>>       _Rb_tree_impl(_Rb_tree_impl&&) = default;
>>
>> +      _Rb_tree_impl(_Rb_tree_impl&& __x, _Node_allocator&& __a)
>> +      : _Node_allocator(std::move(__a)),
>> +        _Base_key_compare(std::move(__x)),
>> +        _Rb_tree_header(std::move(__x))
>> +      { }
>> +
>>       _Rb_tree_impl(const _Key_compare& __comp, _Node_allocator&& __a)
>>       : _Node_allocator(std::move(__a)), _Base_key_compare(__comp)
>>       { }
>> @@ -955,10 +961,32 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
>>       _Rb_tree(_Rb_tree&&) = default;
>>
>>       _Rb_tree(_Rb_tree&& __x, const allocator_type& __a)
>> +      noexcept( noexcept(
>> +    _Rb_tree(std::move(__x), declval<_Node_allocator>())) )
>>       : _Rb_tree(std::move(__x), _Node_allocator(__a))
>>       { }
>>
>> -      _Rb_tree(_Rb_tree&& __x, _Node_allocator&& __a);
>> +    private:
>> +      _Rb_tree(_Rb_tree&& __x, _Node_allocator&& __a, true_type)
>> + noexcept(is_nothrow_move_constructible<_Rb_tree_impl<_Compare>>::value)
>
> This is wrong.
>
> The result of is_nothrow_move_constructible<_Rb_tree_impl<_Compare>>
> depends on this constructor:
>
>  _Rb_tree_impl(_Rb_tree_impl&&) = default;
>
> That constructor depends on the allocator type, which might not be
> noexcept, but it's undefined behaviour for it to throw. We don't want
> the exception-specification to depend on the allocator, otherwise we
> fail this test on the line marked XXX:
>
> template<typename T>
> struct Alloc : std::allocator<T>
> {
>  Alloc() { }
>  Alloc(const Alloc&) { }
>  template<typename U> Alloc(const Alloc<U>&) { }
>
>  template<typename U> struct rebind { using other = Alloc<U>; };
> };
>
> template<typename A>
> using Set = std::set<int, std::less<int>, A>;
>
> template<typename A>
>  using Test = std::is_nothrow_constructible<Set<A>, Set<A>, A>;
>
> int main()
> {
>  static_assert(Test<std::allocator<int>>::value, "");
>  static_assert(Test<Alloc<int>>::value, "");  // XXX
> }
>
In my copy of the Standard I see no noexcept qualifications on 
associative container constructors, is it too old ?

>
> The changes to deduce the exception-specifications seem to make the
> code more fragile -- do we really want to make those changes?
Considering all your feedbacks I would say no. I'll rework it then.
>
>
>> +      : _M_impl(std::move(__x._M_impl), std::move(__a))
>> +      { }
>> +
>> +      _Rb_tree(_Rb_tree&& __x, _Node_allocator&& __a, false_type)
>> +      : _M_impl(__x._M_impl._M_key_compare, std::move(__a))
>> +      {
>> +    if (__x._M_root() != nullptr)
>> +      _M_move_data(__x, false_type{});
>> +      }
>> +
>> +    public:
>> +      _Rb_tree(_Rb_tree&& __x, _Node_allocator&& __a)
>> +      noexcept( noexcept(
>> +    _Rb_tree(std::move(__x), std::move(__a),
>> +         declval<typename _Alloc_traits::is_always_equal>()) ) )
>> +      : _Rb_tree(std::move(__x), std::move(__a),
>> +         typename _Alloc_traits::is_always_equal{})
>> +      { }
>> #endif
>
>
>> diff --git a/libstdc++-v3/include/debug/map.h 
>> b/libstdc++-v3/include/debug/map.h
>> index 414b4dc..9edb7dc 100644
>> --- a/libstdc++-v3/include/debug/map.h
>> +++ b/libstdc++-v3/include/debug/map.h
>> @@ -105,8 +105,10 @@ namespace __debug
>>       : _Base(__m, __a) { }
>>
>>       map(map&& __m, const allocator_type& __a)
>> +      noexcept( noexcept(_Base(std::move(__m._M_base()), __a)) )
>>       : _Safe(std::move(__m._M_safe()), __a),
>> -    _Base(std::move(__m._M_base()), __a) { }
>> +    _Base(std::move(__m._M_base()), __a)
>> +      { }
>
> This part of the patch is actually a bug fix, making the debug mode
> consistent with normal mode.
>
>> diff --git 
>> a/libstdc++-v3/testsuite/23_containers/map/cons/noexcept_move_construct.cc 
>> b/libstdc++-v3/testsuite/23_containers/map/cons/noexcept_move_construct.cc 
>>
>> index 0041408..8791eb8 100644
>> --- 
>> a/libstdc++-v3/testsuite/23_containers/map/cons/noexcept_move_construct.cc
>> +++ 
>> b/libstdc++-v3/testsuite/23_containers/map/cons/noexcept_move_construct.cc
>> @@ -23,4 +23,25 @@
>>
>> typedef std::map<int, int> mtype;
>>
>> -static_assert(std::is_nothrow_move_constructible<mtype>::value, 
>> "Error");
>> +static_assert( std::is_nothrow_move_constructible<mtype>::value,
>> +           "noexcept move constructor" );
>> +static_assert( noexcept( mtype(std::declval<mtype>(),
>> +        std::declval<const typename mtype::allocator_type&>()) ),
>
> This can use std::is_nothrow_constructible
>
>> +           "noexcept move constructor with allocator" );
>> +
>> +struct ExceptLess
>
> Please name this "ThrowingLess" instead of "ExceptLess", I think
> that's more descriptive.
>
>> +{
>> +  ExceptLess() = default;
>> +  ExceptLess(const ExceptLess&) /* noexcept */
>> +  { }
>> +
>> +  bool
>> +  operator()(int l, int r) const
>> +  { return l < r; }
>> +};
>> +
>> +typedef std::map<int, int, ExceptLess> emtype;
>> +
>> +static_assert( !noexcept( emtype(std::declval<emtype>(),
>> +        std::declval<const typename emtype::allocator_type&>()) ),
>
> This can use std::is_nothrow_constructible too.
>
> Same comments for the other tests

Ok

Re: Rb_tree constructor optimization

[François Dumont]

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

Here is the rework of this patch.


On 02/05/2018 13:49, Jonathan Wakely wrote:
> There's no changelog entry with the patch, so to recap, the changes
> are:
>
> - noexcept specifications are automatically deduced instead of being
>  stated explicitly.

I simplified this part, it is not deduced anymore except for Debug mode 
relying on Normal mode qualifications.

>
> - The allocator-extended move constructors get correct exception
>  specifications in Debug Mode (consistent with normal mode). This
>  should be done anyway, independent of any other changes.
I kept this untouch.
>
> - We avoid a `if (__x._M_root() != nullptr)` branch in the case where
>  the allocator-extended move constructor is used with an always-equal
>  allocator, right?
Kept too.
>
> Compilation time for containers is already **much** slower since the
> allocator-extended constructors were added for GCC 5.x, despite very
> few people ever using those constructors. This patch seems to require
> even more work from the compiler to parse constructors nobody uses. 
I restore direct qualifications.

> diff --git a/libstdc++-v3/include/bits/stl_map.h 
> b/libstdc++-v3/include/bits/stl_map.h
>> index a4a026e..2b8fd27 100644
>> --- a/libstdc++-v3/include/bits/stl_map.h
>> +++ b/libstdc++-v3/include/bits/stl_map.h
>> @@ -240,8 +240,8 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
>>
>>       /// Allocator-extended move constructor.
>>       map(map&& __m, const allocator_type& __a)
>> - noexcept(is_nothrow_copy_constructible<_Compare>::value
>> -           && _Alloc_traits::_S_always_equal())
>> +      noexcept( noexcept(
>> +    _Rep_type(std::move(__m._M_t), declval<_Pair_alloc_type>())) )
>
> All these calls to declval need to be qualified to avoid ADL.
>
> It seems strange to have a mix of real values and declval expressions,
> rather than:
>
>     _Rep_type(std::declval<_Rep_type>(), 
> std::declval<_Pair_alloc_type>())) )
I add std:: qualitification and generalized usage.
>
>>
>> -      _Rb_tree(_Rb_tree&& __x, _Node_allocator&& __a);
>> +    private:
>> +      _Rb_tree(_Rb_tree&& __x, _Node_allocator&& __a, true_type)
>> + noexcept(is_nothrow_move_constructible<_Rb_tree_impl<_Compare>>::value)
>
> This is wrong.

As stated previously I removed this but based on this remark I also 
change the _Rb_tree_impl() qualification so that it doesn't depend 
anymore on allocator default constructor qualification.

I've added a test for that too.
> This can use std::is_nothrow_constructible
>
Indeed.
>> +           "noexcept move constructor with allocator" );
>> +
>> +struct ExceptLess
>
> Please name this "ThrowingLess" instead of "ExceptLess", I think
> that's more descriptive.
I prefered "not_noexcept" prefix cause those operators are not throwing 
anything neither.

Tested under Linux x86_64, ok to commit ?

     * include/bits/stl_tree.h
     (_Rb_tree_impl()):
     Remove is_nothrow_default_constructible<_Node_allocator> from noexcept
     qualification.
     (_Rb_tree_impl(_Rb_tree_impl&&, _Node_allocator&&)): New.
     (_Rb_tree(_Rb_tree&&, _Node_allocator&&, std::true_type)): New, use 
latter.
     (_Rb_tree(_Rb_tree&&, _Node_allocator&&, std::false_type)): New.
     (_Rb_tree(_Rb_tree&&, _Node_allocator&&)): Adapt, use latters.
     * include/debug/map.h
     (map(map&&, const_allocator_type&)): Add noexcept qualitication.
     * include/debug/multimap.h
     (multimap(multimap&&, const_allocator_type&)): Add noexcept 
qualification.
     * include/debug/set.h
     (set(set&&, const_allocator_type&)): Add noexcept qualitication.
     * include/debug/multiset.h
     (multiset(multiset&&, const_allocator_type&)): Add noexcept 
qualification.
     * testsuite/23_containers/map/cons/noexcept_default_construct.cc:
     Add checks.
     * testsuite/23_containers/map/cons/noexcept_move_construct.cc:
     Add checks.
     * testsuite/23_containers/multimap/cons/noexcept_default_construct.cc:
     Add checks.
     * testsuite/23_containers/multimap/cons/noexcept_move_construct.cc:
     Add checks.
     * testsuite/23_containers/multiset/cons/noexcept_default_construct.cc:
     Add checks.
     * testsuite/23_containers/multiset/cons/noexcept_move_construct.cc:
     Add checks.
     * testsuite/23_containers/set/cons/noexcept_default_construct.cc:
     Add checks.
     * testsuite/23_containers/set/cons/noexcept_move_construct.cc:
     Add checks.

François


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

diff --git a/libstdc++-v3/include/bits/stl_tree.h b/libstdc++-v3/include/bits/stl_tree.h
index d0a8448..9e59259 100644
--- a/libstdc++-v3/include/bits/stl_tree.h
+++ b/libstdc++-v3/include/bits/stl_tree.h
@@ -698,8 +698,8 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 
 	  _Rb_tree_impl()
            _GLIBCXX_NOEXCEPT_IF(
-		is_nothrow_default_constructible<_Node_allocator>::value
-		&& is_nothrow_default_constructible<_Base_key_compare>::value )
+	    // is_nothrow_default_constructible<_Node_allocator>::value &&
+	    is_nothrow_default_constructible<_Base_key_compare>::value )
 	  : _Node_allocator()
 	  { }
 
@@ -715,6 +715,12 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 #else
 	  _Rb_tree_impl(_Rb_tree_impl&&) = default;
 
+	  _Rb_tree_impl(_Rb_tree_impl&& __x, _Node_allocator&& __a)
+	  : _Node_allocator(std::move(__a)),
+	    _Base_key_compare(std::move(__x)),
+	    _Rb_tree_header(std::move(__x))
+	  { }
+
 	  _Rb_tree_impl(const _Key_compare& __comp, _Node_allocator&& __a)
 	  : _Node_allocator(std::move(__a)), _Base_key_compare(__comp)
 	  { }
@@ -958,7 +964,27 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
       : _Rb_tree(std::move(__x), _Node_allocator(__a))
       { }
 
-      _Rb_tree(_Rb_tree&& __x, _Node_allocator&& __a);
+    private:
+      _Rb_tree(_Rb_tree&& __x, _Node_allocator&& __a, true_type)
+      noexcept(is_nothrow_default_constructible<_Compare>::value)
+      : _M_impl(std::move(__x._M_impl), std::move(__a))
+      { }
+
+      _Rb_tree(_Rb_tree&& __x, _Node_allocator&& __a, false_type)
+      : _M_impl(__x._M_impl._M_key_compare, std::move(__a))
+      {
+	if (__x._M_root() != nullptr)
+	  _M_move_data(__x, false_type{});
+      }
+
+    public:
+      _Rb_tree(_Rb_tree&& __x, _Node_allocator&& __a)
+      noexcept( noexcept(
+	_Rb_tree(std::declval<_Rb_tree>(), std::declval<_Node_allocator>(),
+		 std::declval<typename _Alloc_traits::is_always_equal>())) )
+      : _Rb_tree(std::move(__x), std::move(__a),
+		 typename _Alloc_traits::is_always_equal{})
+      { }
 #endif
 
       ~_Rb_tree() _GLIBCXX_NOEXCEPT
@@ -1358,22 +1384,22 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
     private:
       // Move elements from container with equal allocator.
       void
-      _M_move_data(_Rb_tree& __x, std::true_type)
+      _M_move_data(_Rb_tree& __x, 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.
       void
-      _M_move_data(_Rb_tree&, std::false_type);
+      _M_move_data(_Rb_tree&, false_type);
 
       // Move assignment from container with equal allocator.
       void
-      _M_move_assign(_Rb_tree&, std::true_type);
+      _M_move_assign(_Rb_tree&, true_type);
 
       // Move assignment from container with possibly non-equal allocator,
       // which might result in a copy not a move.
       void
-      _M_move_assign(_Rb_tree&, std::false_type);
+      _M_move_assign(_Rb_tree&, false_type);
 #endif
 
 #if __cplusplus > 201402L
@@ -1601,23 +1627,12 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 #if __cplusplus >= 201103L
   template<typename _Key, typename _Val, typename _KeyOfValue,
 	   typename _Compare, typename _Alloc>
-    _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
-    _Rb_tree(_Rb_tree&& __x, _Node_allocator&& __a)
-    : _M_impl(__x._M_impl._M_key_compare, std::move(__a))
-    {
-      using __eq = typename _Alloc_traits::is_always_equal;
-      if (__x._M_root() != nullptr)
-	_M_move_data(__x, __eq());
-    }
-
-  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)
+    _M_move_data(_Rb_tree& __x, false_type)
     {
       if (_M_get_Node_allocator() == __x._M_get_Node_allocator())
-	_M_move_data(__x, std::true_type());
+	_M_move_data(__x, true_type());
       else
 	{
 	  _Alloc_node __an(*this);
@@ -1639,7 +1654,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
     {
       clear();
       if (__x._M_root() != nullptr)
-	_M_move_data(__x, std::true_type());
+	_M_move_data(__x, true_type());
       std::__alloc_on_move(_M_get_Node_allocator(),
 			   __x._M_get_Node_allocator());
     }
diff --git a/libstdc++-v3/include/debug/map.h b/libstdc++-v3/include/debug/map.h
index 414b4dc..7a4e2bf 100644
--- a/libstdc++-v3/include/debug/map.h
+++ b/libstdc++-v3/include/debug/map.h
@@ -105,6 +105,7 @@ namespace __debug
       : _Base(__m, __a) { }
 
       map(map&& __m, const allocator_type& __a)
+      noexcept( noexcept(_Base(std::move(__m._M_base()), __a)) )
       : _Safe(std::move(__m._M_safe()), __a),
 	_Base(std::move(__m._M_base()), __a) { }
 
diff --git a/libstdc++-v3/include/debug/multimap.h b/libstdc++-v3/include/debug/multimap.h
index 8d6358b..9ee3809 100644
--- a/libstdc++-v3/include/debug/multimap.h
+++ b/libstdc++-v3/include/debug/multimap.h
@@ -105,6 +105,7 @@ namespace __debug
       : _Base(__m, __a) { }
 
       multimap(multimap&& __m, const allocator_type& __a)
+      noexcept( noexcept(_Base(std::move(__m._M_base()), __a)) )
       : _Safe(std::move(__m._M_safe()), __a),
 	_Base(std::move(__m._M_base()), __a) { }
 
diff --git a/libstdc++-v3/include/debug/multiset.h b/libstdc++-v3/include/debug/multiset.h
index 4e1406e..0be14d7 100644
--- a/libstdc++-v3/include/debug/multiset.h
+++ b/libstdc++-v3/include/debug/multiset.h
@@ -104,6 +104,7 @@ namespace __debug
       : _Base(__m, __a) { }
 
       multiset(multiset&& __m, const allocator_type& __a)
+      noexcept( noexcept(_Base(std::move(__m._M_base()), __a)) )
       : _Safe(std::move(__m._M_safe()), __a),
 	_Base(std::move(__m._M_base()), __a) { }
 
diff --git a/libstdc++-v3/include/debug/set.h b/libstdc++-v3/include/debug/set.h
index a886860..7f24a83 100644
--- a/libstdc++-v3/include/debug/set.h
+++ b/libstdc++-v3/include/debug/set.h
@@ -104,6 +104,7 @@ namespace __debug
       : _Base(__x, __a) { }
 
       set(set&& __x, const allocator_type& __a)
+      noexcept( noexcept(_Base(std::move(__x._M_base()), __a)) )
       : _Safe(std::move(__x._M_safe()), __a),
 	_Base(std::move(__x._M_base()), __a) { }
 
diff --git a/libstdc++-v3/testsuite/23_containers/map/cons/noexcept_default_construct.cc b/libstdc++-v3/testsuite/23_containers/map/cons/noexcept_default_construct.cc
index 4b9e119..7658916 100644
--- a/libstdc++-v3/testsuite/23_containers/map/cons/noexcept_default_construct.cc
+++ b/libstdc++-v3/testsuite/23_containers/map/cons/noexcept_default_construct.cc
@@ -30,3 +30,19 @@ struct cmp
 
 using mtype2 = std::map<int, int, cmp>;
 static_assert( !std::is_nothrow_default_constructible<mtype2>::value, "Error");
+
+template<typename _Tp>
+  struct not_noexcept_cons_alloc : std::allocator<_Tp>
+  {
+    not_noexcept_cons_alloc() /* noexcept */
+    { }
+
+    template<typename _Tp1>
+      struct rebind
+      { typedef not_noexcept_cons_alloc<_Tp1> other; };
+  };
+
+using mtype3 = std::map<int, int, std::less<int>,
+			not_noexcept_cons_alloc<std::pair<const int, int>>>;
+
+static_assert(std::is_nothrow_default_constructible<mtype3>::value, "Error");
diff --git a/libstdc++-v3/testsuite/23_containers/map/cons/noexcept_move_construct.cc b/libstdc++-v3/testsuite/23_containers/map/cons/noexcept_move_construct.cc
index 0041408..723a63f 100644
--- a/libstdc++-v3/testsuite/23_containers/map/cons/noexcept_move_construct.cc
+++ b/libstdc++-v3/testsuite/23_containers/map/cons/noexcept_move_construct.cc
@@ -23,4 +23,25 @@
 
 typedef std::map<int, int> mtype;
 
-static_assert(std::is_nothrow_move_constructible<mtype>::value, "Error");
+static_assert( std::is_nothrow_move_constructible<mtype>::value,
+	       "noexcept move constructor" );
+static_assert( std::is_nothrow_constructible<mtype,
+	       mtype&&, const typename mtype::allocator_type&>::value,
+	       "noexcept move constructor with allocator" );
+
+struct not_noexcept_less
+{
+  not_noexcept_less() = default;
+  not_noexcept_less(const not_noexcept_less&) /* noexcept */
+  { }
+
+  bool
+  operator()(int l, int r) const
+  { return l < r; }
+};
+
+typedef std::map<int, int, not_noexcept_less> emtype;
+
+static_assert( !std::is_nothrow_constructible<emtype, emtype&&,
+	       const typename emtype::allocator_type&>::value,
+	       "except move constructor with allocator" );
diff --git a/libstdc++-v3/testsuite/23_containers/multimap/cons/noexcept_default_construct.cc b/libstdc++-v3/testsuite/23_containers/multimap/cons/noexcept_default_construct.cc
index 9873770..e83cd87 100644
--- a/libstdc++-v3/testsuite/23_containers/multimap/cons/noexcept_default_construct.cc
+++ b/libstdc++-v3/testsuite/23_containers/multimap/cons/noexcept_default_construct.cc
@@ -30,3 +30,19 @@ struct cmp
 
 using mtype2 = std::multimap<int, int, cmp>;
 static_assert( !std::is_nothrow_default_constructible<mtype2>::value, "Error");
+
+template<typename _Tp>
+  struct not_noexcept_cons_alloc : std::allocator<_Tp>
+  {
+    not_noexcept_cons_alloc() /* noexcept */
+    { }
+
+    template<typename _Tp1>
+      struct rebind
+      { typedef not_noexcept_cons_alloc<_Tp1> other; };
+  };
+
+using mtype3 = std::multimap<int, int, std::less<int>,
+			not_noexcept_cons_alloc<std::pair<const int, int>>>;
+
+static_assert(std::is_nothrow_default_constructible<mtype3>::value, "Error");
diff --git a/libstdc++-v3/testsuite/23_containers/multimap/cons/noexcept_move_construct.cc b/libstdc++-v3/testsuite/23_containers/multimap/cons/noexcept_move_construct.cc
index 0319a61..1612b0d 100644
--- a/libstdc++-v3/testsuite/23_containers/multimap/cons/noexcept_move_construct.cc
+++ b/libstdc++-v3/testsuite/23_containers/multimap/cons/noexcept_move_construct.cc
@@ -23,4 +23,25 @@
 
 typedef std::multimap<int, int> mmtype;
 
-static_assert(std::is_nothrow_move_constructible<mmtype>::value, "Error");
+static_assert( std::is_nothrow_move_constructible<mmtype>::value,
+	       "noexcept move constructor" );
+static_assert( std::is_nothrow_constructible<mmtype,
+	       mmtype&&, const typename mmtype::allocator_type&>::value,
+	       "noexcept move constructor with allocator" );
+
+struct not_noexcept_less
+{
+  not_noexcept_less() = default;
+  not_noexcept_less(const not_noexcept_less&) /* noexcept */
+  { }
+
+  bool
+  operator()(int l, int r) const
+  { return l < r; }
+};
+
+typedef std::multimap<int, int, not_noexcept_less> emmtype;
+
+static_assert( !std::is_nothrow_constructible<emmtype, emmtype&&,
+	       const typename emmtype::allocator_type&>::value,
+	       "except move constructor with allocator" );
diff --git a/libstdc++-v3/testsuite/23_containers/multiset/cons/noexcept_default_construct.cc b/libstdc++-v3/testsuite/23_containers/multiset/cons/noexcept_default_construct.cc
index 963e3d1..4c465f0 100644
--- a/libstdc++-v3/testsuite/23_containers/multiset/cons/noexcept_default_construct.cc
+++ b/libstdc++-v3/testsuite/23_containers/multiset/cons/noexcept_default_construct.cc
@@ -30,3 +30,19 @@ struct cmp
 
 using stype2 = std::multiset<int, cmp>;
 static_assert( !std::is_nothrow_default_constructible<stype2>::value, "Error");
+
+template<typename _Tp>
+  struct not_noexcept_cons_alloc : std::allocator<_Tp>
+  {
+    not_noexcept_cons_alloc() /* noexcept */
+    { }
+
+    template<typename _Tp1>
+      struct rebind
+      { typedef not_noexcept_cons_alloc<_Tp1> other; };
+  };
+
+using stype3 = std::multiset<int, std::less<int>,
+			     not_noexcept_cons_alloc<int>>;
+
+static_assert(std::is_nothrow_default_constructible<stype3>::value, "Error");
diff --git a/libstdc++-v3/testsuite/23_containers/multiset/cons/noexcept_move_construct.cc b/libstdc++-v3/testsuite/23_containers/multiset/cons/noexcept_move_construct.cc
index b1c6dd5..4ef5127 100644
--- a/libstdc++-v3/testsuite/23_containers/multiset/cons/noexcept_move_construct.cc
+++ b/libstdc++-v3/testsuite/23_containers/multiset/cons/noexcept_move_construct.cc
@@ -23,4 +23,25 @@
 
 typedef std::multiset<int> mstype;
 
-static_assert(std::is_nothrow_move_constructible<mstype>::value, "Error");
+static_assert( std::is_nothrow_move_constructible<mstype>::value,
+	       "noexcept move constructor" );
+static_assert( std::is_nothrow_constructible<mstype,
+	       mstype&&, const typename mstype::allocator_type&>::value,
+	       "noexcept move constructor with allocator" );
+
+struct not_noexcept_less
+{
+  not_noexcept_less() = default;
+  not_noexcept_less(const not_noexcept_less&) /* noexcept */
+  { }
+
+  bool
+  operator()(int l, int r) const
+  { return l < r; }
+};
+
+typedef std::multiset<int, not_noexcept_less> emstype;
+
+static_assert( !std::is_nothrow_constructible<emstype, emstype&&,
+	       const typename emstype::allocator_type&>::value,
+	       "except move constructor with allocator" );
diff --git a/libstdc++-v3/testsuite/23_containers/set/cons/noexcept_default_construct.cc b/libstdc++-v3/testsuite/23_containers/set/cons/noexcept_default_construct.cc
index 882a12c..51a3db5 100644
--- a/libstdc++-v3/testsuite/23_containers/set/cons/noexcept_default_construct.cc
+++ b/libstdc++-v3/testsuite/23_containers/set/cons/noexcept_default_construct.cc
@@ -30,3 +30,19 @@ struct cmp
 
 using stype2 = std::set<int, cmp>;
 static_assert( !std::is_nothrow_default_constructible<stype2>::value, "Error");
+
+template<typename _Tp>
+  struct not_noexcept_cons_alloc : std::allocator<_Tp>
+  {
+    not_noexcept_cons_alloc() /* noexcept */
+    { }
+
+    template<typename _Tp1>
+      struct rebind
+      { typedef not_noexcept_cons_alloc<_Tp1> other; };
+  };
+
+using stype3 = std::set<int, std::less<int>,
+			not_noexcept_cons_alloc<int>>;
+
+static_assert(std::is_nothrow_default_constructible<stype3>::value, "Error");
diff --git a/libstdc++-v3/testsuite/23_containers/set/cons/noexcept_move_construct.cc b/libstdc++-v3/testsuite/23_containers/set/cons/noexcept_move_construct.cc
index a7de0ef..942400e 100644
--- a/libstdc++-v3/testsuite/23_containers/set/cons/noexcept_move_construct.cc
+++ b/libstdc++-v3/testsuite/23_containers/set/cons/noexcept_move_construct.cc
@@ -23,4 +23,25 @@
 
 typedef std::set<int> stype;
 
-static_assert(std::is_nothrow_move_constructible<stype>::value, "Error");
+static_assert( std::is_nothrow_move_constructible<stype>::value,
+	       "noexcept move constructor" );
+static_assert( std::is_nothrow_constructible<stype,
+	       stype&&, const typename stype::allocator_type&>::value,
+	       "noexcept move constructor with allocator" );
+
+struct not_noexcept_less
+{
+  not_noexcept_less() = default;
+  not_noexcept_less(const not_noexcept_less&) /* noexcept */
+  { }
+
+  bool
+  operator()(int l, int r) const
+  { return l < r; }
+};
+
+typedef std::set<int, not_noexcept_less> estype;
+
+static_assert( !std::is_nothrow_constructible<estype, estype&&,
+	       const typename estype::allocator_type&>::value,
+	       "except move constructor with allocator" );

Re: Rb_tree constructor optimization

[Jonathan Wakely]

On 06/05/18 16:06 +0200, François Dumont wrote:
>Here is the rework of this patch.
>
>
>On 02/05/2018 13:49, Jonathan Wakely wrote:
>>There's no changelog entry with the patch, so to recap, the changes
>>are:
>>
>>- noexcept specifications are automatically deduced instead of being
>> stated explicitly.
>
>I simplified this part, it is not deduced anymore except for Debug 
>mode relying on Normal mode qualifications.
>
>>
>>- The allocator-extended move constructors get correct exception
>> specifications in Debug Mode (consistent with normal mode). This
>> should be done anyway, independent of any other changes.
>I kept this untouch.
>>
>>- We avoid a `if (__x._M_root() != nullptr)` branch in the case where
>> the allocator-extended move constructor is used with an always-equal
>> allocator, right?
>Kept too.
>>
>>Compilation time for containers is already **much** slower since the
>>allocator-extended constructors were added for GCC 5.x, despite very
>>few people ever using those constructors. This patch seems to require
>>even more work from the compiler to parse constructors nobody uses.
>I restore direct qualifications.
>
>>diff --git a/libstdc++-v3/include/bits/stl_map.h 
>>b/libstdc++-v3/include/bits/stl_map.h
>>>index a4a026e..2b8fd27 100644
>>>--- a/libstdc++-v3/include/bits/stl_map.h
>>>+++ b/libstdc++-v3/include/bits/stl_map.h
>>>@@ -240,8 +240,8 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
>>>
>>>      /// Allocator-extended move constructor.
>>>      map(map&& __m, const allocator_type& __a)
>>>- noexcept(is_nothrow_copy_constructible<_Compare>::value
>>>-           && _Alloc_traits::_S_always_equal())
>>>+      noexcept( noexcept(
>>>+    _Rep_type(std::move(__m._M_t), declval<_Pair_alloc_type>())) )
>>
>>All these calls to declval need to be qualified to avoid ADL.
>>
>>It seems strange to have a mix of real values and declval expressions,
>>rather than:
>>
>>    _Rep_type(std::declval<_Rep_type>(), 
>>std::declval<_Pair_alloc_type>())) )
>I add std:: qualitification and generalized usage.
>>
>>>
>>>-      _Rb_tree(_Rb_tree&& __x, _Node_allocator&& __a);
>>>+    private:
>>>+      _Rb_tree(_Rb_tree&& __x, _Node_allocator&& __a, true_type)
>>>+ noexcept(is_nothrow_move_constructible<_Rb_tree_impl<_Compare>>::value)
>>
>>This is wrong.
>
>As stated previously I removed this but based on this remark I also 
>change the _Rb_tree_impl() qualification so that it doesn't depend 
>anymore on allocator default constructor qualification.
>
>I've added a test for that too.
>>This can use std::is_nothrow_constructible
>>
>Indeed.
>>>+           "noexcept move constructor with allocator" );
>>>+
>>>+struct ExceptLess
>>
>>Please name this "ThrowingLess" instead of "ExceptLess", I think
>>that's more descriptive.
>I prefered "not_noexcept" prefix cause those operators are not 
>throwing anything neither.
>
>Tested under Linux x86_64, ok to commit ?
>
>    * include/bits/stl_tree.h
>    (_Rb_tree_impl()):
>    Remove is_nothrow_default_constructible<_Node_allocator> from noexcept
>    qualification.
>    (_Rb_tree_impl(_Rb_tree_impl&&, _Node_allocator&&)): New.
>    (_Rb_tree(_Rb_tree&&, _Node_allocator&&, std::true_type)): New, 
>use latter.
>    (_Rb_tree(_Rb_tree&&, _Node_allocator&&, std::false_type)): New.
>    (_Rb_tree(_Rb_tree&&, _Node_allocator&&)): Adapt, use latters.
>    * include/debug/map.h
>    (map(map&&, const_allocator_type&)): Add noexcept qualitication.
>    * include/debug/multimap.h
>    (multimap(multimap&&, const_allocator_type&)): Add noexcept 
>qualification.
>    * include/debug/set.h
>    (set(set&&, const_allocator_type&)): Add noexcept qualitication.
>    * include/debug/multiset.h
>    (multiset(multiset&&, const_allocator_type&)): Add noexcept 
>qualification.
>    * testsuite/23_containers/map/cons/noexcept_default_construct.cc:
>    Add checks.
>    * testsuite/23_containers/map/cons/noexcept_move_construct.cc:
>    Add checks.
>    * testsuite/23_containers/multimap/cons/noexcept_default_construct.cc:
>    Add checks.
>    * testsuite/23_containers/multimap/cons/noexcept_move_construct.cc:
>    Add checks.
>    * testsuite/23_containers/multiset/cons/noexcept_default_construct.cc:
>    Add checks.
>    * testsuite/23_containers/multiset/cons/noexcept_move_construct.cc:
>    Add checks.
>    * testsuite/23_containers/set/cons/noexcept_default_construct.cc:
>    Add checks.
>    * testsuite/23_containers/set/cons/noexcept_move_construct.cc:
>    Add checks.
>
>François
>

>diff --git a/libstdc++-v3/include/bits/stl_tree.h b/libstdc++-v3/include/bits/stl_tree.h
>index d0a8448..9e59259 100644
>--- a/libstdc++-v3/include/bits/stl_tree.h
>+++ b/libstdc++-v3/include/bits/stl_tree.h
>@@ -698,8 +698,8 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
> 
> 	  _Rb_tree_impl()
>            _GLIBCXX_NOEXCEPT_IF(
>-		is_nothrow_default_constructible<_Node_allocator>::value
>-		&& is_nothrow_default_constructible<_Base_key_compare>::value )
>+	    // is_nothrow_default_constructible<_Node_allocator>::value &&
>+	    is_nothrow_default_constructible<_Base_key_compare>::value )
> 	  : _Node_allocator()
> 	  { }

This part wasn't in the previous patch and seems wrong:
https://cplusplus.github.io/LWG/issue2455

Re: Rb_tree constructor optimization

[François Dumont]

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

On 11/05/2018 14:16, Jonathan Wakely wrote:
> On 06/05/18 16:06 +0200, François Dumont wrote:
>> Here is the rework of this patch.
>>
>>
>> On 02/05/2018 13:49, Jonathan Wakely wrote:
>>> There's no changelog entry with the patch, so to recap, the changes
>>> are:
>>>
>>> - noexcept specifications are automatically deduced instead of being
>>>  stated explicitly.
>>
>> I simplified this part, it is not deduced anymore except for Debug 
>> mode relying on Normal mode qualifications.
>>
>>>
>>> - The allocator-extended move constructors get correct exception
>>>  specifications in Debug Mode (consistent with normal mode). This
>>>  should be done anyway, independent of any other changes.
>> I kept this untouch.
>>>
>>> - We avoid a `if (__x._M_root() != nullptr)` branch in the case where
>>>  the allocator-extended move constructor is used with an always-equal
>>>  allocator, right?
>> Kept too.
>>>
>>> Compilation time for containers is already **much** slower since the
>>> allocator-extended constructors were added for GCC 5.x, despite very
>>> few people ever using those constructors. This patch seems to require
>>> even more work from the compiler to parse constructors nobody uses.
>> I restore direct qualifications.
>>
>>> diff --git a/libstdc++-v3/include/bits/stl_map.h 
>>> b/libstdc++-v3/include/bits/stl_map.h
>>>> index a4a026e..2b8fd27 100644
>>>> --- a/libstdc++-v3/include/bits/stl_map.h
>>>> +++ b/libstdc++-v3/include/bits/stl_map.h
>>>> @@ -240,8 +240,8 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
>>>>
>>>>       /// Allocator-extended move constructor.
>>>>       map(map&& __m, const allocator_type& __a)
>>>> - noexcept(is_nothrow_copy_constructible<_Compare>::value
>>>> -           && _Alloc_traits::_S_always_equal())
>>>> +      noexcept( noexcept(
>>>> +    _Rep_type(std::move(__m._M_t), declval<_Pair_alloc_type>())) )
>>>
>>> All these calls to declval need to be qualified to avoid ADL.
>>>
>>> It seems strange to have a mix of real values and declval expressions,
>>> rather than:
>>>
>>>     _Rep_type(std::declval<_Rep_type>(), 
>>> std::declval<_Pair_alloc_type>())) )
>> I add std:: qualitification and generalized usage.
>>>
>>>>
>>>> -      _Rb_tree(_Rb_tree&& __x, _Node_allocator&& __a);
>>>> +    private:
>>>> +      _Rb_tree(_Rb_tree&& __x, _Node_allocator&& __a, true_type)
>>>> + 
>>>> noexcept(is_nothrow_move_constructible<_Rb_tree_impl<_Compare>>::value)
>>>
>>> This is wrong.
>>
>> As stated previously I removed this but based on this remark I also 
>> change the _Rb_tree_impl() qualification so that it doesn't depend 
>> anymore on allocator default constructor qualification.
>>
>> I've added a test for that too.
>>> This can use std::is_nothrow_constructible
>>>
>> Indeed.
>>>> +           "noexcept move constructor with allocator" );
>>>> +
>>>> +struct ExceptLess
>>>
>>> Please name this "ThrowingLess" instead of "ExceptLess", I think
>>> that's more descriptive.
>> I prefered "not_noexcept" prefix cause those operators are not 
>> throwing anything neither.
>>
>> Tested under Linux x86_64, ok to commit ?
>>
>>     * include/bits/stl_tree.h
>>     (_Rb_tree_impl()):
>>     Remove is_nothrow_default_constructible<_Node_allocator> from 
>> noexcept
>>     qualification.
>>     (_Rb_tree_impl(_Rb_tree_impl&&, _Node_allocator&&)): New.
>>     (_Rb_tree(_Rb_tree&&, _Node_allocator&&, std::true_type)): New, 
>> use latter.
>>     (_Rb_tree(_Rb_tree&&, _Node_allocator&&, std::false_type)): New.
>>     (_Rb_tree(_Rb_tree&&, _Node_allocator&&)): Adapt, use latters.
>>     * include/debug/map.h
>>     (map(map&&, const_allocator_type&)): Add noexcept qualitication.
>>     * include/debug/multimap.h
>>     (multimap(multimap&&, const_allocator_type&)): Add noexcept 
>> qualification.
>>     * include/debug/set.h
>>     (set(set&&, const_allocator_type&)): Add noexcept qualitication.
>>     * include/debug/multiset.h
>>     (multiset(multiset&&, const_allocator_type&)): Add noexcept 
>> qualification.
>>     * testsuite/23_containers/map/cons/noexcept_default_construct.cc:
>>     Add checks.
>>     * testsuite/23_containers/map/cons/noexcept_move_construct.cc:
>>     Add checks.
>>     * 
>> testsuite/23_containers/multimap/cons/noexcept_default_construct.cc:
>>     Add checks.
>>     * testsuite/23_containers/multimap/cons/noexcept_move_construct.cc:
>>     Add checks.
>>     * 
>> testsuite/23_containers/multiset/cons/noexcept_default_construct.cc:
>>     Add checks.
>>     * testsuite/23_containers/multiset/cons/noexcept_move_construct.cc:
>>     Add checks.
>>     * testsuite/23_containers/set/cons/noexcept_default_construct.cc:
>>     Add checks.
>>     * testsuite/23_containers/set/cons/noexcept_move_construct.cc:
>>     Add checks.
>>
>> François
>>
>
>> diff --git a/libstdc++-v3/include/bits/stl_tree.h 
>> b/libstdc++-v3/include/bits/stl_tree.h
>> index d0a8448..9e59259 100644
>> --- a/libstdc++-v3/include/bits/stl_tree.h
>> +++ b/libstdc++-v3/include/bits/stl_tree.h
>> @@ -698,8 +698,8 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
>>
>>       _Rb_tree_impl()
>>            _GLIBCXX_NOEXCEPT_IF(
>> - is_nothrow_default_constructible<_Node_allocator>::value
>> -        && is_nothrow_default_constructible<_Base_key_compare>::value )
>> +        // is_nothrow_default_constructible<_Node_allocator>::value &&
>> + is_nothrow_default_constructible<_Base_key_compare>::value )
>>       : _Node_allocator()
>>       { }
>
> This part wasn't in the previous patch and seems wrong:
> https://cplusplus.github.io/LWG/issue2455
>
Yes, I must have been tired when I decided to do such a thing.

Here it is again even more simplified. Should I backport the Debug mode 
fix to 8 branch ?

     * include/bits/stl_tree.h
     (_Rb_tree_impl(_Rb_tree_impl&&, _Node_allocator&&)): New.
     (_Rb_tree(_Rb_tree&&, _Node_allocator&&, true_type)): New, use latter.
     (_Rb_tree(_Rb_tree&&, _Node_allocator&&, false_type)): New.
     (_Rb_tree(_Rb_tree&&, _Node_allocator&&)): Adapt, use latters.
     * include/debug/map.h
     (map(map&&, const_allocator_type&)): Add noexcept qualitication.
     * include/debug/multimap.h
     (multimap(multimap&&, const_allocator_type&)): Add noexcept 
qualification.
     * include/debug/set.h
     (set(set&&, const_allocator_type&)): Add noexcept qualitication.
     * include/debug/multiset.h
     (multiset(multiset&&, const_allocator_type&)): Add noexcept 
qualification.
     * testsuite/23_containers/map/cons/noexcept_default_construct.cc:
     Add checks.
     * testsuite/23_containers/map/cons/noexcept_move_construct.cc:
     Add checks.
     * testsuite/23_containers/multimap/cons/noexcept_default_construct.cc:
     Add checks.
     * testsuite/23_containers/multimap/cons/noexcept_move_construct.cc:
     Add checks.
     * testsuite/23_containers/multiset/cons/noexcept_default_construct.cc:
     Add checks.
     * testsuite/23_containers/multiset/cons/noexcept_move_construct.cc:
     Add checks.
     * testsuite/23_containers/set/cons/noexcept_default_construct.cc:
     Add checks.
     * testsuite/23_containers/set/cons/noexcept_move_construct.cc:
     Add checks.

Ok to commit ?

François


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

diff --git a/libstdc++-v3/include/bits/stl_tree.h b/libstdc++-v3/include/bits/stl_tree.h
index d0a8448..85f190a 100644
--- a/libstdc++-v3/include/bits/stl_tree.h
+++ b/libstdc++-v3/include/bits/stl_tree.h
@@ -715,6 +715,12 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 #else
 	  _Rb_tree_impl(_Rb_tree_impl&&) = default;
 
+	  _Rb_tree_impl(_Rb_tree_impl&& __x, _Node_allocator&& __a)
+	  : _Node_allocator(std::move(__a)),
+	    _Base_key_compare(std::move(__x)),
+	    _Rb_tree_header(std::move(__x))
+	  { }
+
 	  _Rb_tree_impl(const _Key_compare& __comp, _Node_allocator&& __a)
 	  : _Node_allocator(std::move(__a)), _Base_key_compare(__comp)
 	  { }
@@ -958,7 +964,27 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
       : _Rb_tree(std::move(__x), _Node_allocator(__a))
       { }
 
-      _Rb_tree(_Rb_tree&& __x, _Node_allocator&& __a);
+    private:
+      _Rb_tree(_Rb_tree&& __x, _Node_allocator&& __a, true_type)
+      noexcept(is_nothrow_default_constructible<_Compare>::value)
+      : _M_impl(std::move(__x._M_impl), std::move(__a))
+      { }
+
+      _Rb_tree(_Rb_tree&& __x, _Node_allocator&& __a, false_type)
+      : _M_impl(__x._M_impl._M_key_compare, std::move(__a))
+      {
+	if (__x._M_root() != nullptr)
+	  _M_move_data(__x, false_type{});
+      }
+
+    public:
+      _Rb_tree(_Rb_tree&& __x, _Node_allocator&& __a)
+      noexcept( noexcept(
+	_Rb_tree(std::declval<_Rb_tree>(), std::declval<_Node_allocator>(),
+		 std::declval<typename _Alloc_traits::is_always_equal>())) )
+      : _Rb_tree(std::move(__x), std::move(__a),
+		 typename _Alloc_traits::is_always_equal{})
+      { }
 #endif
 
       ~_Rb_tree() _GLIBCXX_NOEXCEPT
@@ -1358,22 +1384,22 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
     private:
       // Move elements from container with equal allocator.
       void
-      _M_move_data(_Rb_tree& __x, std::true_type)
+      _M_move_data(_Rb_tree& __x, 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.
       void
-      _M_move_data(_Rb_tree&, std::false_type);
+      _M_move_data(_Rb_tree&, false_type);
 
       // Move assignment from container with equal allocator.
       void
-      _M_move_assign(_Rb_tree&, std::true_type);
+      _M_move_assign(_Rb_tree&, true_type);
 
       // Move assignment from container with possibly non-equal allocator,
       // which might result in a copy not a move.
       void
-      _M_move_assign(_Rb_tree&, std::false_type);
+      _M_move_assign(_Rb_tree&, false_type);
 #endif
 
 #if __cplusplus > 201402L
@@ -1601,23 +1627,12 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 #if __cplusplus >= 201103L
   template<typename _Key, typename _Val, typename _KeyOfValue,
 	   typename _Compare, typename _Alloc>
-    _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
-    _Rb_tree(_Rb_tree&& __x, _Node_allocator&& __a)
-    : _M_impl(__x._M_impl._M_key_compare, std::move(__a))
-    {
-      using __eq = typename _Alloc_traits::is_always_equal;
-      if (__x._M_root() != nullptr)
-	_M_move_data(__x, __eq());
-    }
-
-  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)
+    _M_move_data(_Rb_tree& __x, false_type)
     {
       if (_M_get_Node_allocator() == __x._M_get_Node_allocator())
-	_M_move_data(__x, std::true_type());
+	_M_move_data(__x, true_type());
       else
 	{
 	  _Alloc_node __an(*this);
@@ -1639,7 +1654,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
     {
       clear();
       if (__x._M_root() != nullptr)
-	_M_move_data(__x, std::true_type());
+	_M_move_data(__x, true_type());
       std::__alloc_on_move(_M_get_Node_allocator(),
 			   __x._M_get_Node_allocator());
     }
diff --git a/libstdc++-v3/include/debug/map.h b/libstdc++-v3/include/debug/map.h
index 3f0649a..23966ba 100644
--- a/libstdc++-v3/include/debug/map.h
+++ b/libstdc++-v3/include/debug/map.h
@@ -105,6 +105,7 @@ namespace __debug
       : _Base(__m, __a) { }
 
       map(map&& __m, const allocator_type& __a)
+      noexcept( noexcept(_Base(std::move(__m._M_base()), __a)) )
       : _Safe(std::move(__m._M_safe()), __a),
 	_Base(std::move(__m._M_base()), __a) { }
 
diff --git a/libstdc++-v3/include/debug/multimap.h b/libstdc++-v3/include/debug/multimap.h
index e709eb7..8054984 100644
--- a/libstdc++-v3/include/debug/multimap.h
+++ b/libstdc++-v3/include/debug/multimap.h
@@ -105,6 +105,7 @@ namespace __debug
       : _Base(__m, __a) { }
 
       multimap(multimap&& __m, const allocator_type& __a)
+      noexcept( noexcept(_Base(std::move(__m._M_base()), __a)) )
       : _Safe(std::move(__m._M_safe()), __a),
 	_Base(std::move(__m._M_base()), __a) { }
 
diff --git a/libstdc++-v3/include/debug/multiset.h b/libstdc++-v3/include/debug/multiset.h
index 461f4f6..6e4c1b0 100644
--- a/libstdc++-v3/include/debug/multiset.h
+++ b/libstdc++-v3/include/debug/multiset.h
@@ -104,6 +104,7 @@ namespace __debug
       : _Base(__m, __a) { }
 
       multiset(multiset&& __m, const allocator_type& __a)
+      noexcept( noexcept(_Base(std::move(__m._M_base()), __a)) )
       : _Safe(std::move(__m._M_safe()), __a),
 	_Base(std::move(__m._M_base()), __a) { }
 
diff --git a/libstdc++-v3/include/debug/set.h b/libstdc++-v3/include/debug/set.h
index 2ac8f1c..571cc47 100644
--- a/libstdc++-v3/include/debug/set.h
+++ b/libstdc++-v3/include/debug/set.h
@@ -104,6 +104,7 @@ namespace __debug
       : _Base(__x, __a) { }
 
       set(set&& __x, const allocator_type& __a)
+      noexcept( noexcept(_Base(std::move(__x._M_base()), __a)) )
       : _Safe(std::move(__x._M_safe()), __a),
 	_Base(std::move(__x._M_base()), __a) { }
 
diff --git a/libstdc++-v3/testsuite/23_containers/map/cons/noexcept_default_construct.cc b/libstdc++-v3/testsuite/23_containers/map/cons/noexcept_default_construct.cc
index 4b9e119..e5c924d 100644
--- a/libstdc++-v3/testsuite/23_containers/map/cons/noexcept_default_construct.cc
+++ b/libstdc++-v3/testsuite/23_containers/map/cons/noexcept_default_construct.cc
@@ -30,3 +30,19 @@ struct cmp
 
 using mtype2 = std::map<int, int, cmp>;
 static_assert( !std::is_nothrow_default_constructible<mtype2>::value, "Error");
+
+template<typename _Tp>
+  struct not_noexcept_cons_alloc : std::allocator<_Tp>
+  {
+    not_noexcept_cons_alloc() /* noexcept */
+    { }
+
+    template<typename _Tp1>
+      struct rebind
+      { typedef not_noexcept_cons_alloc<_Tp1> other; };
+  };
+
+using mtype3 = std::map<int, int, std::less<int>,
+			not_noexcept_cons_alloc<std::pair<const int, int>>>;
+
+static_assert(!std::is_nothrow_default_constructible<mtype3>::value, "Error");
diff --git a/libstdc++-v3/testsuite/23_containers/map/cons/noexcept_move_construct.cc b/libstdc++-v3/testsuite/23_containers/map/cons/noexcept_move_construct.cc
index 0041408..723a63f 100644
--- a/libstdc++-v3/testsuite/23_containers/map/cons/noexcept_move_construct.cc
+++ b/libstdc++-v3/testsuite/23_containers/map/cons/noexcept_move_construct.cc
@@ -23,4 +23,25 @@
 
 typedef std::map<int, int> mtype;
 
-static_assert(std::is_nothrow_move_constructible<mtype>::value, "Error");
+static_assert( std::is_nothrow_move_constructible<mtype>::value,
+	       "noexcept move constructor" );
+static_assert( std::is_nothrow_constructible<mtype,
+	       mtype&&, const typename mtype::allocator_type&>::value,
+	       "noexcept move constructor with allocator" );
+
+struct not_noexcept_less
+{
+  not_noexcept_less() = default;
+  not_noexcept_less(const not_noexcept_less&) /* noexcept */
+  { }
+
+  bool
+  operator()(int l, int r) const
+  { return l < r; }
+};
+
+typedef std::map<int, int, not_noexcept_less> emtype;
+
+static_assert( !std::is_nothrow_constructible<emtype, emtype&&,
+	       const typename emtype::allocator_type&>::value,
+	       "except move constructor with allocator" );
diff --git a/libstdc++-v3/testsuite/23_containers/multimap/cons/noexcept_default_construct.cc b/libstdc++-v3/testsuite/23_containers/multimap/cons/noexcept_default_construct.cc
index 9873770..62f5d60 100644
--- a/libstdc++-v3/testsuite/23_containers/multimap/cons/noexcept_default_construct.cc
+++ b/libstdc++-v3/testsuite/23_containers/multimap/cons/noexcept_default_construct.cc
@@ -30,3 +30,19 @@ struct cmp
 
 using mtype2 = std::multimap<int, int, cmp>;
 static_assert( !std::is_nothrow_default_constructible<mtype2>::value, "Error");
+
+template<typename _Tp>
+  struct not_noexcept_cons_alloc : std::allocator<_Tp>
+  {
+    not_noexcept_cons_alloc() /* noexcept */
+    { }
+
+    template<typename _Tp1>
+      struct rebind
+      { typedef not_noexcept_cons_alloc<_Tp1> other; };
+  };
+
+using mtype3 = std::multimap<int, int, std::less<int>,
+			not_noexcept_cons_alloc<std::pair<const int, int>>>;
+
+static_assert(!std::is_nothrow_default_constructible<mtype3>::value, "Error");
diff --git a/libstdc++-v3/testsuite/23_containers/multimap/cons/noexcept_move_construct.cc b/libstdc++-v3/testsuite/23_containers/multimap/cons/noexcept_move_construct.cc
index 0319a61..1612b0d 100644
--- a/libstdc++-v3/testsuite/23_containers/multimap/cons/noexcept_move_construct.cc
+++ b/libstdc++-v3/testsuite/23_containers/multimap/cons/noexcept_move_construct.cc
@@ -23,4 +23,25 @@
 
 typedef std::multimap<int, int> mmtype;
 
-static_assert(std::is_nothrow_move_constructible<mmtype>::value, "Error");
+static_assert( std::is_nothrow_move_constructible<mmtype>::value,
+	       "noexcept move constructor" );
+static_assert( std::is_nothrow_constructible<mmtype,
+	       mmtype&&, const typename mmtype::allocator_type&>::value,
+	       "noexcept move constructor with allocator" );
+
+struct not_noexcept_less
+{
+  not_noexcept_less() = default;
+  not_noexcept_less(const not_noexcept_less&) /* noexcept */
+  { }
+
+  bool
+  operator()(int l, int r) const
+  { return l < r; }
+};
+
+typedef std::multimap<int, int, not_noexcept_less> emmtype;
+
+static_assert( !std::is_nothrow_constructible<emmtype, emmtype&&,
+	       const typename emmtype::allocator_type&>::value,
+	       "except move constructor with allocator" );
diff --git a/libstdc++-v3/testsuite/23_containers/multiset/cons/noexcept_default_construct.cc b/libstdc++-v3/testsuite/23_containers/multiset/cons/noexcept_default_construct.cc
index 963e3d1..8e49168 100644
--- a/libstdc++-v3/testsuite/23_containers/multiset/cons/noexcept_default_construct.cc
+++ b/libstdc++-v3/testsuite/23_containers/multiset/cons/noexcept_default_construct.cc
@@ -30,3 +30,19 @@ struct cmp
 
 using stype2 = std::multiset<int, cmp>;
 static_assert( !std::is_nothrow_default_constructible<stype2>::value, "Error");
+
+template<typename _Tp>
+  struct not_noexcept_cons_alloc : std::allocator<_Tp>
+  {
+    not_noexcept_cons_alloc() /* noexcept */
+    { }
+
+    template<typename _Tp1>
+      struct rebind
+      { typedef not_noexcept_cons_alloc<_Tp1> other; };
+  };
+
+using stype3 = std::multiset<int, std::less<int>,
+			     not_noexcept_cons_alloc<int>>;
+
+static_assert(!std::is_nothrow_default_constructible<stype3>::value, "Error");
diff --git a/libstdc++-v3/testsuite/23_containers/multiset/cons/noexcept_move_construct.cc b/libstdc++-v3/testsuite/23_containers/multiset/cons/noexcept_move_construct.cc
index b1c6dd5..4ef5127 100644
--- a/libstdc++-v3/testsuite/23_containers/multiset/cons/noexcept_move_construct.cc
+++ b/libstdc++-v3/testsuite/23_containers/multiset/cons/noexcept_move_construct.cc
@@ -23,4 +23,25 @@
 
 typedef std::multiset<int> mstype;
 
-static_assert(std::is_nothrow_move_constructible<mstype>::value, "Error");
+static_assert( std::is_nothrow_move_constructible<mstype>::value,
+	       "noexcept move constructor" );
+static_assert( std::is_nothrow_constructible<mstype,
+	       mstype&&, const typename mstype::allocator_type&>::value,
+	       "noexcept move constructor with allocator" );
+
+struct not_noexcept_less
+{
+  not_noexcept_less() = default;
+  not_noexcept_less(const not_noexcept_less&) /* noexcept */
+  { }
+
+  bool
+  operator()(int l, int r) const
+  { return l < r; }
+};
+
+typedef std::multiset<int, not_noexcept_less> emstype;
+
+static_assert( !std::is_nothrow_constructible<emstype, emstype&&,
+	       const typename emstype::allocator_type&>::value,
+	       "except move constructor with allocator" );
diff --git a/libstdc++-v3/testsuite/23_containers/set/cons/noexcept_default_construct.cc b/libstdc++-v3/testsuite/23_containers/set/cons/noexcept_default_construct.cc
index 882a12c..d3dc98d 100644
--- a/libstdc++-v3/testsuite/23_containers/set/cons/noexcept_default_construct.cc
+++ b/libstdc++-v3/testsuite/23_containers/set/cons/noexcept_default_construct.cc
@@ -30,3 +30,19 @@ struct cmp
 
 using stype2 = std::set<int, cmp>;
 static_assert( !std::is_nothrow_default_constructible<stype2>::value, "Error");
+
+template<typename _Tp>
+  struct not_noexcept_cons_alloc : std::allocator<_Tp>
+  {
+    not_noexcept_cons_alloc() /* noexcept */
+    { }
+
+    template<typename _Tp1>
+      struct rebind
+      { typedef not_noexcept_cons_alloc<_Tp1> other; };
+  };
+
+using stype3 = std::set<int, std::less<int>,
+			not_noexcept_cons_alloc<int>>;
+
+static_assert(!std::is_nothrow_default_constructible<stype3>::value, "Error");
diff --git a/libstdc++-v3/testsuite/23_containers/set/cons/noexcept_move_construct.cc b/libstdc++-v3/testsuite/23_containers/set/cons/noexcept_move_construct.cc
index a7de0ef..942400e 100644
--- a/libstdc++-v3/testsuite/23_containers/set/cons/noexcept_move_construct.cc
+++ b/libstdc++-v3/testsuite/23_containers/set/cons/noexcept_move_construct.cc
@@ -23,4 +23,25 @@
 
 typedef std::set<int> stype;
 
-static_assert(std::is_nothrow_move_constructible<stype>::value, "Error");
+static_assert( std::is_nothrow_move_constructible<stype>::value,
+	       "noexcept move constructor" );
+static_assert( std::is_nothrow_constructible<stype,
+	       stype&&, const typename stype::allocator_type&>::value,
+	       "noexcept move constructor with allocator" );
+
+struct not_noexcept_less
+{
+  not_noexcept_less() = default;
+  not_noexcept_less(const not_noexcept_less&) /* noexcept */
+  { }
+
+  bool
+  operator()(int l, int r) const
+  { return l < r; }
+};
+
+typedef std::set<int, not_noexcept_less> estype;
+
+static_assert( !std::is_nothrow_constructible<estype, estype&&,
+	       const typename estype::allocator_type&>::value,
+	       "except move constructor with allocator" );

Re: Rb_tree constructor optimization

[Jonathan Wakely]

On 15/05/18 07:30 +0200, François Dumont wrote:
>Here it is again even more simplified. Should I backport the Debug 
>mode fix to 8 branch ?

Yes, please do backport the include/debug/* changes.


>    * include/bits/stl_tree.h
>    (_Rb_tree_impl(_Rb_tree_impl&&, _Node_allocator&&)): New.
>    (_Rb_tree(_Rb_tree&&, _Node_allocator&&, true_type)): New, use latter.
>    (_Rb_tree(_Rb_tree&&, _Node_allocator&&, false_type)): New.
>    (_Rb_tree(_Rb_tree&&, _Node_allocator&&)): Adapt, use latters.
>    * include/debug/map.h
>    (map(map&&, const_allocator_type&)): Add noexcept qualitication.
>    * include/debug/multimap.h
>    (multimap(multimap&&, const_allocator_type&)): Add noexcept 
>qualification.
>    * include/debug/set.h
>    (set(set&&, const_allocator_type&)): Add noexcept qualitication.
>    * include/debug/multiset.h
>    (multiset(multiset&&, const_allocator_type&)): Add noexcept 
>qualification.
>    * testsuite/23_containers/map/cons/noexcept_default_construct.cc:
>    Add checks.
>    * testsuite/23_containers/map/cons/noexcept_move_construct.cc:
>    Add checks.
>    * testsuite/23_containers/multimap/cons/noexcept_default_construct.cc:
>    Add checks.
>    * testsuite/23_containers/multimap/cons/noexcept_move_construct.cc:
>    Add checks.
>    * testsuite/23_containers/multiset/cons/noexcept_default_construct.cc:
>    Add checks.
>    * testsuite/23_containers/multiset/cons/noexcept_move_construct.cc:
>    Add checks.
>    * testsuite/23_containers/set/cons/noexcept_default_construct.cc:
>    Add checks.
>    * testsuite/23_containers/set/cons/noexcept_move_construct.cc:
>    Add checks.
>
>Ok to commit ?

Yes, OK for trunk - thanks.

Re: Rb_tree constructor optimization

[Jonathan Wakely]

On 17/05/18 16:10 +0100, Jonathan Wakely wrote:
>On 15/05/18 07:30 +0200, François Dumont wrote:
>>Here it is again even more simplified. Should I backport the Debug 
>>mode fix to 8 branch ?
>
>Yes, please do backport the include/debug/* changes.
>
>
>>    * include/bits/stl_tree.h
>>    (_Rb_tree_impl(_Rb_tree_impl&&, _Node_allocator&&)): New.
>>    (_Rb_tree(_Rb_tree&&, _Node_allocator&&, true_type)): New, use latter.
>>    (_Rb_tree(_Rb_tree&&, _Node_allocator&&, false_type)): New.
>>    (_Rb_tree(_Rb_tree&&, _Node_allocator&&)): Adapt, use latters.
>>    * include/debug/map.h
>>    (map(map&&, const_allocator_type&)): Add noexcept qualitication.
>>    * include/debug/multimap.h
>>    (multimap(multimap&&, const_allocator_type&)): Add noexcept 
>>qualification.
>>    * include/debug/set.h
>>    (set(set&&, const_allocator_type&)): Add noexcept qualitication.
>>    * include/debug/multiset.h
>>    (multiset(multiset&&, const_allocator_type&)): Add noexcept 
>>qualification.
>>    * testsuite/23_containers/map/cons/noexcept_default_construct.cc:
>>    Add checks.
>>    * testsuite/23_containers/map/cons/noexcept_move_construct.cc:
>>    Add checks.
>>    * testsuite/23_containers/multimap/cons/noexcept_default_construct.cc:
>>    Add checks.
>>    * testsuite/23_containers/multimap/cons/noexcept_move_construct.cc:
>>    Add checks.
>>    * testsuite/23_containers/multiset/cons/noexcept_default_construct.cc:
>>    Add checks.
>>    * testsuite/23_containers/multiset/cons/noexcept_move_construct.cc:
>>    Add checks.
>>    * testsuite/23_containers/set/cons/noexcept_default_construct.cc:
>>    Add checks.
>>    * testsuite/23_containers/set/cons/noexcept_move_construct.cc:
>>    Add checks.
>>
>>Ok to commit ?
>
>Yes, OK for trunk - thanks.
>
>

I'm seeing lots of new testsuite failures after this commit, see
https://gcc.gnu.org/ml/gcc-testresults/2018-05/msg02025.html

Re: Rb_tree constructor optimization

[H.J. Lu]

On Fri, May 18, 2018 at 6:45 PM, Jonathan Wakely <jwakely@redhat.com> wrote:
> On 17/05/18 16:10 +0100, Jonathan Wakely wrote:
>>
>> On 15/05/18 07:30 +0200, François Dumont wrote:
>>>
>>> Here it is again even more simplified. Should I backport the Debug mode
>>> fix to 8 branch ?
>>
>>
>> Yes, please do backport the include/debug/* changes.
>>
>>
>>>     * include/bits/stl_tree.h
>>>     (_Rb_tree_impl(_Rb_tree_impl&&, _Node_allocator&&)): New.
>>>     (_Rb_tree(_Rb_tree&&, _Node_allocator&&, true_type)): New, use
>>> latter.
>>>     (_Rb_tree(_Rb_tree&&, _Node_allocator&&, false_type)): New.
>>>     (_Rb_tree(_Rb_tree&&, _Node_allocator&&)): Adapt, use latters.
>>>     * include/debug/map.h
>>>     (map(map&&, const_allocator_type&)): Add noexcept qualitication.
>>>     * include/debug/multimap.h
>>>     (multimap(multimap&&, const_allocator_type&)): Add noexcept
>>> qualification.
>>>     * include/debug/set.h
>>>     (set(set&&, const_allocator_type&)): Add noexcept qualitication.
>>>     * include/debug/multiset.h
>>>     (multiset(multiset&&, const_allocator_type&)): Add noexcept
>>> qualification.
>>>     * testsuite/23_containers/map/cons/noexcept_default_construct.cc:
>>>     Add checks.
>>>     * testsuite/23_containers/map/cons/noexcept_move_construct.cc:
>>>     Add checks.
>>>     *
>>> testsuite/23_containers/multimap/cons/noexcept_default_construct.cc:
>>>     Add checks.
>>>     * testsuite/23_containers/multimap/cons/noexcept_move_construct.cc:
>>>     Add checks.
>>>     *
>>> testsuite/23_containers/multiset/cons/noexcept_default_construct.cc:
>>>     Add checks.
>>>     * testsuite/23_containers/multiset/cons/noexcept_move_construct.cc:
>>>     Add checks.
>>>     * testsuite/23_containers/set/cons/noexcept_default_construct.cc:
>>>     Add checks.
>>>     * testsuite/23_containers/set/cons/noexcept_move_construct.cc:
>>>     Add checks.
>>>
>>> Ok to commit ?
>>
>>
>> Yes, OK for trunk - thanks.
>>
>>
>
> I'm seeing lots of new testsuite failures after this commit, see
> https://gcc.gnu.org/ml/gcc-testresults/2018-05/msg02025.html
>
>

I opened:

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=85845

-- 
H.J.

Re: Rb_tree constructor optimization

[François Dumont]

On 17/05/18 16:10 +0100, Jonathan Wakely wrote:
>>> On 15/05/18 07:30 +0200, François Dumont wrote:
>>>> Here it is again even more simplified. Should I backport the Debug mode
>>>> fix to 8 branch ?
>>>
>>> Yes, please do backport the include/debug/* changes.
>>>

Now backported.

François

Re: Rb_tree constructor optimization

[François Dumont]

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

Hi

     Any feedback regarding this patch ?

Thanks,
François

On 14/09/2017 22:04, François Dumont wrote:
> I realized there was no test on the noexcept qualification of the move 
> constructor with allocator.
>
> I added some and found out that patch was missing a noexcept 
> qualification at _Rb_tree level.
>
> Here is the updated patch fully tested, ok to commit ?
>
> François
>
>
> On 13/09/2017 21:57, François Dumont wrote:
>> On 08/09/2017 17:50, Jonathan Wakely wrote:
>>>
>>> Since we know __a == __x.get_allocator() we could just do:
>>>
>>>      _Rb_tree(_Rb_tree&& __x, _Node_allocator&&, true_type)
>>> noexcept(is_nothrow_move_constructible<_Rb_tree_impl<_Compare>>::value)
>>>      : _M_impl(std::move(__x._M_impl))
>>>      { }
>>>
>>> This means we don't need the new constructor.
>>
>>     You want to consider that a always equal allocator is stateless 
>> and so that the provided allocator rvalue reference do not need to be 
>> moved. IMHO you can have allocator with state that do not participate 
>> in comparison like some monitoring info.
>>
>>     I'm not confortable with that and prefer to keep current behavior 
>> so I propose this new patch considering all your other remarks.
>>
>>     I change noexcept qualification on [multi]map/set constructors to 
>> just rely on _Rep_type constructor noexcept qualification to not 
>> duplicate it.
>>
>> François
>>
>>
>
>
>


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

diff --git a/libstdc++-v3/include/bits/stl_map.h b/libstdc++-v3/include/bits/stl_map.h
index bad6020..e343f04 100644
--- a/libstdc++-v3/include/bits/stl_map.h
+++ b/libstdc++-v3/include/bits/stl_map.h
@@ -235,8 +235,8 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
 
       /// Allocator-extended move constructor.
       map(map&& __m, const allocator_type& __a)
-      noexcept(is_nothrow_copy_constructible<_Compare>::value
-	       && _Alloc_traits::_S_always_equal())
+      noexcept( noexcept(
+	_Rep_type(declval<_Rep_type>(), declval<_Pair_alloc_type>())) )
       : _M_t(std::move(__m._M_t), _Pair_alloc_type(__a)) { }
 
       /// Allocator-extended initialier-list constructor.
diff --git a/libstdc++-v3/include/bits/stl_multimap.h b/libstdc++-v3/include/bits/stl_multimap.h
index 6f5cb7a..8c7ae2c 100644
--- a/libstdc++-v3/include/bits/stl_multimap.h
+++ b/libstdc++-v3/include/bits/stl_multimap.h
@@ -232,8 +232,8 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
 
       /// Allocator-extended move constructor.
       multimap(multimap&& __m, const allocator_type& __a)
-      noexcept(is_nothrow_copy_constructible<_Compare>::value
-	       && _Alloc_traits::_S_always_equal())
+      noexcept( noexcept(
+	_Rep_type(declval<_Rep_type>(), declval<_Pair_alloc_type>())) )
       : _M_t(std::move(__m._M_t), _Pair_alloc_type(__a)) { }
 
       /// Allocator-extended initialier-list constructor.
diff --git a/libstdc++-v3/include/bits/stl_multiset.h b/libstdc++-v3/include/bits/stl_multiset.h
index 517e77e..9ab4ab7 100644
--- a/libstdc++-v3/include/bits/stl_multiset.h
+++ b/libstdc++-v3/include/bits/stl_multiset.h
@@ -244,8 +244,8 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
 
       /// Allocator-extended move constructor.
       multiset(multiset&& __m, const allocator_type& __a)
-      noexcept(is_nothrow_copy_constructible<_Compare>::value
-	       && _Alloc_traits::_S_always_equal())
+      noexcept( noexcept(
+	_Rep_type(declval<_Rep_type>(), declval<_Key_alloc_type>())) )
       : _M_t(std::move(__m._M_t), _Key_alloc_type(__a)) { }
 
       /// Allocator-extended initialier-list constructor.
diff --git a/libstdc++-v3/include/bits/stl_set.h b/libstdc++-v3/include/bits/stl_set.h
index e804a7c..6b64bcd 100644
--- a/libstdc++-v3/include/bits/stl_set.h
+++ b/libstdc++-v3/include/bits/stl_set.h
@@ -248,8 +248,8 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
 
       /// Allocator-extended move constructor.
       set(set&& __x, const allocator_type& __a)
-      noexcept(is_nothrow_copy_constructible<_Compare>::value
-	       && _Alloc_traits::_S_always_equal())
+      noexcept( noexcept(
+	_Rep_type(declval<_Rep_type>(), declval<_Key_alloc_type>())) )
       : _M_t(std::move(__x._M_t), _Key_alloc_type(__a)) { }
 
       /// Allocator-extended initialier-list constructor.
diff --git a/libstdc++-v3/include/bits/stl_tree.h b/libstdc++-v3/include/bits/stl_tree.h
index c2417f1..ebfc3f9 100644
--- a/libstdc++-v3/include/bits/stl_tree.h
+++ b/libstdc++-v3/include/bits/stl_tree.h
@@ -704,6 +704,12 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 #else
 	  _Rb_tree_impl(_Rb_tree_impl&&) = default;
 
+	  _Rb_tree_impl(_Rb_tree_impl&& __x, _Node_allocator&& __a)
+	  : _Node_allocator(std::move(__a)),
+	    _Base_key_compare(std::move(__x)),
+	    _Rb_tree_header(std::move(__x))
+	  { }
+
 	  _Rb_tree_impl(const _Key_compare& __comp, _Node_allocator&& __a)
 	  : _Node_allocator(std::move(__a)), _Base_key_compare(__comp)
 	  { }
@@ -944,10 +950,32 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
       _Rb_tree(_Rb_tree&&) = default;
 
       _Rb_tree(_Rb_tree&& __x, const allocator_type& __a)
+      noexcept( noexcept(
+	_Rb_tree(declval<_Rb_tree>(), declval<_Node_allocator>())) )
       : _Rb_tree(std::move(__x), _Node_allocator(__a))
       { }
 
-      _Rb_tree(_Rb_tree&& __x, _Node_allocator&& __a);
+    private:
+      _Rb_tree(_Rb_tree&& __x, _Node_allocator&& __a, true_type)
+      noexcept(is_nothrow_move_constructible<_Rb_tree_impl<_Compare>>::value)
+      : _M_impl(std::move(__x._M_impl), std::move(__a))
+      { }
+
+      _Rb_tree(_Rb_tree&& __x, _Node_allocator&& __a, false_type)
+      : _M_impl(__x._M_impl._M_key_compare, std::move(__a))
+      {
+	if (__x._M_root() != nullptr)
+	  _M_move_data(__x, false_type{});
+      }
+
+    public:
+      _Rb_tree(_Rb_tree&& __x, _Node_allocator&& __a)
+      noexcept( noexcept(
+	_Rb_tree(declval<_Rb_tree>(), declval<_Node_allocator>(),
+		 declval<typename _Alloc_traits::is_always_equal>()) ) )
+      : _Rb_tree(std::move(__x), std::move(__a),
+		 typename _Alloc_traits::is_always_equal{})
+      { }
 #endif
 
       ~_Rb_tree() _GLIBCXX_NOEXCEPT
@@ -1347,22 +1375,22 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
     private:
       // Move elements from container with equal allocator.
       void
-      _M_move_data(_Rb_tree& __x, std::true_type)
+      _M_move_data(_Rb_tree& __x, 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.
       void
-      _M_move_data(_Rb_tree&, std::false_type);
+      _M_move_data(_Rb_tree&, false_type);
 
       // Move assignment from container with equal allocator.
       void
-      _M_move_assign(_Rb_tree&, std::true_type);
+      _M_move_assign(_Rb_tree&, true_type);
 
       // Move assignment from container with possibly non-equal allocator,
       // which might result in a copy not a move.
       void
-      _M_move_assign(_Rb_tree&, std::false_type);
+      _M_move_assign(_Rb_tree&, false_type);
 #endif
 
 #if __cplusplus > 201402L
@@ -1590,23 +1618,12 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 #if __cplusplus >= 201103L
   template<typename _Key, typename _Val, typename _KeyOfValue,
 	   typename _Compare, typename _Alloc>
-    _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
-    _Rb_tree(_Rb_tree&& __x, _Node_allocator&& __a)
-    : _M_impl(__x._M_impl._M_key_compare, std::move(__a))
-    {
-      using __eq = typename _Alloc_traits::is_always_equal;
-      if (__x._M_root() != nullptr)
-	_M_move_data(__x, __eq());
-    }
-
-  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)
+    _M_move_data(_Rb_tree& __x, false_type)
     {
       if (_M_get_Node_allocator() == __x._M_get_Node_allocator())
-	_M_move_data(__x, std::true_type());
+	_M_move_data(__x, true_type());
       else
 	{
 	  _Alloc_node __an(*this);
@@ -1628,7 +1645,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
     {
       clear();
       if (__x._M_root() != nullptr)
-	_M_move_data(__x, std::true_type());
+	_M_move_data(__x, true_type());
       std::__alloc_on_move(_M_get_Node_allocator(),
 			   __x._M_get_Node_allocator());
     }
diff --git a/libstdc++-v3/testsuite/23_containers/map/cons/noexcept_move_construct.cc b/libstdc++-v3/testsuite/23_containers/map/cons/noexcept_move_construct.cc
index b172df7..97c1a47 100644
--- a/libstdc++-v3/testsuite/23_containers/map/cons/noexcept_move_construct.cc
+++ b/libstdc++-v3/testsuite/23_containers/map/cons/noexcept_move_construct.cc
@@ -23,4 +23,25 @@
 
 typedef std::map<int, int> mtype;
 
-static_assert(std::is_nothrow_move_constructible<mtype>::value, "Error");
+static_assert( std::is_nothrow_move_constructible<mtype>::value,
+	       "noexcept move constructor" );
+static_assert( noexcept( mtype(std::declval<mtype>(),
+		std::declval<const typename mtype::allocator_type&>()) ),
+	       "noexcept move constructor with allocator" );
+
+struct ExceptLess
+{
+  ExceptLess() = default;
+  ExceptLess(const ExceptLess&) /* noexcept */
+  { }
+
+  bool
+  operator()(int l, int r) const
+  { return l < r; }
+};
+
+typedef std::map<int, int, ExceptLess> emtype;
+
+static_assert( !noexcept( emtype(std::declval<emtype>(),
+		std::declval<const typename emtype::allocator_type&>()) ),
+	       "except move constructor with allocator" );
diff --git a/libstdc++-v3/testsuite/23_containers/multimap/cons/noexcept_move_construct.cc b/libstdc++-v3/testsuite/23_containers/multimap/cons/noexcept_move_construct.cc
index 03ef459..9acfbb5 100644
--- a/libstdc++-v3/testsuite/23_containers/multimap/cons/noexcept_move_construct.cc
+++ b/libstdc++-v3/testsuite/23_containers/multimap/cons/noexcept_move_construct.cc
@@ -23,4 +23,25 @@
 
 typedef std::multimap<int, int> mmtype;
 
-static_assert(std::is_nothrow_move_constructible<mmtype>::value, "Error");
+static_assert( std::is_nothrow_move_constructible<mmtype>::value,
+	       "noexcept move constructor" );
+static_assert( noexcept( mmtype(std::declval<mmtype>(),
+		std::declval<const typename mmtype::allocator_type&>()) ),
+	       "noexcept move constructor with allocator" );
+
+struct ExceptLess
+{
+  ExceptLess() = default;
+  ExceptLess(const ExceptLess&) /* noexcept */
+  { }
+
+  bool
+  operator()(int l, int r) const
+  { return l < r; }
+};
+
+typedef std::multimap<int, int, ExceptLess> emmtype;
+
+static_assert( !noexcept( emmtype(std::declval<emmtype>(),
+		std::declval<const typename emmtype::allocator_type&>()) ),
+	       "except move constructor with allocator" );
diff --git a/libstdc++-v3/testsuite/23_containers/multiset/cons/noexcept_move_construct.cc b/libstdc++-v3/testsuite/23_containers/multiset/cons/noexcept_move_construct.cc
index 49878e0..adc7a72 100644
--- a/libstdc++-v3/testsuite/23_containers/multiset/cons/noexcept_move_construct.cc
+++ b/libstdc++-v3/testsuite/23_containers/multiset/cons/noexcept_move_construct.cc
@@ -23,4 +23,25 @@
 
 typedef std::multiset<int> mstype;
 
-static_assert(std::is_nothrow_move_constructible<mstype>::value, "Error");
+static_assert( std::is_nothrow_move_constructible<mstype>::value,
+	       "noexcept move constructor" );
+static_assert( noexcept( mstype(std::declval<mstype>(),
+		std::declval<const typename mstype::allocator_type&>()) ),
+	       "noexcept move constructor with allocator" );
+
+struct ExceptLess
+{
+  ExceptLess() = default;
+  ExceptLess(const ExceptLess&) /* noexcept */
+  { }
+
+  bool
+  operator()(int l, int r) const
+  { return l < r; }
+};
+
+typedef std::multiset<int, ExceptLess> emstype;
+
+static_assert( !noexcept( emstype(std::declval<emstype>(),
+		std::declval<const typename emstype::allocator_type&>()) ),
+	       "except move constructor with allocator" );
diff --git a/libstdc++-v3/testsuite/23_containers/set/cons/noexcept_move_construct.cc b/libstdc++-v3/testsuite/23_containers/set/cons/noexcept_move_construct.cc
index 95b5100..0e1f2fa 100644
--- a/libstdc++-v3/testsuite/23_containers/set/cons/noexcept_move_construct.cc
+++ b/libstdc++-v3/testsuite/23_containers/set/cons/noexcept_move_construct.cc
@@ -23,4 +23,25 @@
 
 typedef std::set<int> stype;
 
-static_assert(std::is_nothrow_move_constructible<stype>::value, "Error");
+static_assert( std::is_nothrow_move_constructible<stype>::value,
+	       "noexcept move constructor" );
+static_assert( noexcept( stype(std::declval<stype>(),
+		std::declval<const typename stype::allocator_type&>()) ),
+	       "noexcept move constructor with allocator" );
+
+struct ExceptLess
+{
+  ExceptLess() = default;
+  ExceptLess(const ExceptLess&) /* noexcept */
+  { }
+
+  bool
+  operator()(int l, int r) const
+  { return l < r; }
+};
+
+typedef std::set<int, ExceptLess> estype;
+
+static_assert( !noexcept( estype(std::declval<estype>(),
+		std::declval<const typename estype::allocator_type&>()) ),
+	       "except move constructor with allocator" );

Re: Rb_tree constructor optimization

[François Dumont]

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

I realized there was no test on the noexcept qualification of the move 
constructor with allocator.

I added some and found out that patch was missing a noexcept 
qualification at _Rb_tree level.

Here is the updated patch fully tested, ok to commit ?

François


On 13/09/2017 21:57, François Dumont wrote:
> On 08/09/2017 17:50, Jonathan Wakely wrote:
>>
>> Since we know __a == __x.get_allocator() we could just do:
>>
>>      _Rb_tree(_Rb_tree&& __x, _Node_allocator&&, true_type)
>> noexcept(is_nothrow_move_constructible<_Rb_tree_impl<_Compare>>::value)
>>      : _M_impl(std::move(__x._M_impl))
>>      { }
>>
>> This means we don't need the new constructor.
>
>     You want to consider that a always equal allocator is stateless 
> and so that the provided allocator rvalue reference do not need to be 
> moved. IMHO you can have allocator with state that do not participate 
> in comparison like some monitoring info.
>
>     I'm not confortable with that and prefer to keep current behavior 
> so I propose this new patch considering all your other remarks.
>
>     I change noexcept qualification on [multi]map/set constructors to 
> just rely on _Rep_type constructor noexcept qualification to not 
> duplicate it.
>
> François
>
>




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

diff --git a/libstdc++-v3/include/bits/stl_map.h b/libstdc++-v3/include/bits/stl_map.h
index 0e8a98a..cdd2e7c 100644
--- a/libstdc++-v3/include/bits/stl_map.h
+++ b/libstdc++-v3/include/bits/stl_map.h
@@ -235,8 +235,8 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
 
       /// Allocator-extended move constructor.
       map(map&& __m, const allocator_type& __a)
-      noexcept(is_nothrow_copy_constructible<_Compare>::value
-	       && _Alloc_traits::_S_always_equal())
+      noexcept( noexcept(
+	_Rep_type(declval<_Rep_type>(), declval<_Pair_alloc_type>())) )
       : _M_t(std::move(__m._M_t), _Pair_alloc_type(__a)) { }
 
       /// Allocator-extended initialier-list constructor.
diff --git a/libstdc++-v3/include/bits/stl_multimap.h b/libstdc++-v3/include/bits/stl_multimap.h
index 7e3cea4..d32104d 100644
--- a/libstdc++-v3/include/bits/stl_multimap.h
+++ b/libstdc++-v3/include/bits/stl_multimap.h
@@ -232,8 +232,8 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
 
       /// Allocator-extended move constructor.
       multimap(multimap&& __m, const allocator_type& __a)
-      noexcept(is_nothrow_copy_constructible<_Compare>::value
-	       && _Alloc_traits::_S_always_equal())
+      noexcept( noexcept(
+	_Rep_type(declval<_Rep_type>(), declval<_Pair_alloc_type>())) )
       : _M_t(std::move(__m._M_t), _Pair_alloc_type(__a)) { }
 
       /// Allocator-extended initialier-list constructor.
diff --git a/libstdc++-v3/include/bits/stl_multiset.h b/libstdc++-v3/include/bits/stl_multiset.h
index 517e77e..9ab4ab7 100644
--- a/libstdc++-v3/include/bits/stl_multiset.h
+++ b/libstdc++-v3/include/bits/stl_multiset.h
@@ -244,8 +244,8 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
 
       /// Allocator-extended move constructor.
       multiset(multiset&& __m, const allocator_type& __a)
-      noexcept(is_nothrow_copy_constructible<_Compare>::value
-	       && _Alloc_traits::_S_always_equal())
+      noexcept( noexcept(
+	_Rep_type(declval<_Rep_type>(), declval<_Key_alloc_type>())) )
       : _M_t(std::move(__m._M_t), _Key_alloc_type(__a)) { }
 
       /// Allocator-extended initialier-list constructor.
diff --git a/libstdc++-v3/include/bits/stl_set.h b/libstdc++-v3/include/bits/stl_set.h
index e804a7c..6b64bcd 100644
--- a/libstdc++-v3/include/bits/stl_set.h
+++ b/libstdc++-v3/include/bits/stl_set.h
@@ -248,8 +248,8 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
 
       /// Allocator-extended move constructor.
       set(set&& __x, const allocator_type& __a)
-      noexcept(is_nothrow_copy_constructible<_Compare>::value
-	       && _Alloc_traits::_S_always_equal())
+      noexcept( noexcept(
+	_Rep_type(declval<_Rep_type>(), declval<_Key_alloc_type>())) )
       : _M_t(std::move(__x._M_t), _Key_alloc_type(__a)) { }
 
       /// Allocator-extended initialier-list constructor.
diff --git a/libstdc++-v3/include/bits/stl_tree.h b/libstdc++-v3/include/bits/stl_tree.h
index c2417f1..ebfc3f9 100644
--- a/libstdc++-v3/include/bits/stl_tree.h
+++ b/libstdc++-v3/include/bits/stl_tree.h
@@ -704,6 +704,12 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 #else
 	  _Rb_tree_impl(_Rb_tree_impl&&) = default;
 
+	  _Rb_tree_impl(_Rb_tree_impl&& __x, _Node_allocator&& __a)
+	  : _Node_allocator(std::move(__a)),
+	    _Base_key_compare(std::move(__x)),
+	    _Rb_tree_header(std::move(__x))
+	  { }
+
 	  _Rb_tree_impl(const _Key_compare& __comp, _Node_allocator&& __a)
 	  : _Node_allocator(std::move(__a)), _Base_key_compare(__comp)
 	  { }
@@ -944,10 +950,32 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
       _Rb_tree(_Rb_tree&&) = default;
 
       _Rb_tree(_Rb_tree&& __x, const allocator_type& __a)
+      noexcept( noexcept(
+	_Rb_tree(declval<_Rb_tree>(), declval<_Node_allocator>())) )
       : _Rb_tree(std::move(__x), _Node_allocator(__a))
       { }
 
-      _Rb_tree(_Rb_tree&& __x, _Node_allocator&& __a);
+    private:
+      _Rb_tree(_Rb_tree&& __x, _Node_allocator&& __a, true_type)
+      noexcept(is_nothrow_move_constructible<_Rb_tree_impl<_Compare>>::value)
+      : _M_impl(std::move(__x._M_impl), std::move(__a))
+      { }
+
+      _Rb_tree(_Rb_tree&& __x, _Node_allocator&& __a, false_type)
+      : _M_impl(__x._M_impl._M_key_compare, std::move(__a))
+      {
+	if (__x._M_root() != nullptr)
+	  _M_move_data(__x, false_type{});
+      }
+
+    public:
+      _Rb_tree(_Rb_tree&& __x, _Node_allocator&& __a)
+      noexcept( noexcept(
+	_Rb_tree(declval<_Rb_tree>(), declval<_Node_allocator>(),
+		 declval<typename _Alloc_traits::is_always_equal>()) ) )
+      : _Rb_tree(std::move(__x), std::move(__a),
+		 typename _Alloc_traits::is_always_equal{})
+      { }
 #endif
 
       ~_Rb_tree() _GLIBCXX_NOEXCEPT
@@ -1347,22 +1375,22 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
     private:
       // Move elements from container with equal allocator.
       void
-      _M_move_data(_Rb_tree& __x, std::true_type)
+      _M_move_data(_Rb_tree& __x, 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.
       void
-      _M_move_data(_Rb_tree&, std::false_type);
+      _M_move_data(_Rb_tree&, false_type);
 
       // Move assignment from container with equal allocator.
       void
-      _M_move_assign(_Rb_tree&, std::true_type);
+      _M_move_assign(_Rb_tree&, true_type);
 
       // Move assignment from container with possibly non-equal allocator,
       // which might result in a copy not a move.
       void
-      _M_move_assign(_Rb_tree&, std::false_type);
+      _M_move_assign(_Rb_tree&, false_type);
 #endif
 
 #if __cplusplus > 201402L
@@ -1590,23 +1618,12 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 #if __cplusplus >= 201103L
   template<typename _Key, typename _Val, typename _KeyOfValue,
 	   typename _Compare, typename _Alloc>
-    _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
-    _Rb_tree(_Rb_tree&& __x, _Node_allocator&& __a)
-    : _M_impl(__x._M_impl._M_key_compare, std::move(__a))
-    {
-      using __eq = typename _Alloc_traits::is_always_equal;
-      if (__x._M_root() != nullptr)
-	_M_move_data(__x, __eq());
-    }
-
-  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)
+    _M_move_data(_Rb_tree& __x, false_type)
     {
       if (_M_get_Node_allocator() == __x._M_get_Node_allocator())
-	_M_move_data(__x, std::true_type());
+	_M_move_data(__x, true_type());
       else
 	{
 	  _Alloc_node __an(*this);
@@ -1628,7 +1645,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
     {
       clear();
       if (__x._M_root() != nullptr)
-	_M_move_data(__x, std::true_type());
+	_M_move_data(__x, true_type());
       std::__alloc_on_move(_M_get_Node_allocator(),
 			   __x._M_get_Node_allocator());
     }
diff --git a/libstdc++-v3/testsuite/23_containers/map/cons/noexcept_move_construct.cc b/libstdc++-v3/testsuite/23_containers/map/cons/noexcept_move_construct.cc
index b172df7..97c1a47 100644
--- a/libstdc++-v3/testsuite/23_containers/map/cons/noexcept_move_construct.cc
+++ b/libstdc++-v3/testsuite/23_containers/map/cons/noexcept_move_construct.cc
@@ -23,4 +23,25 @@
 
 typedef std::map<int, int> mtype;
 
-static_assert(std::is_nothrow_move_constructible<mtype>::value, "Error");
+static_assert( std::is_nothrow_move_constructible<mtype>::value,
+	       "noexcept move constructor" );
+static_assert( noexcept( mtype(std::declval<mtype>(),
+		std::declval<const typename mtype::allocator_type&>()) ),
+	       "noexcept move constructor with allocator" );
+
+struct ExceptLess
+{
+  ExceptLess() = default;
+  ExceptLess(const ExceptLess&) /* noexcept */
+  { }
+
+  bool
+  operator()(int l, int r) const
+  { return l < r; }
+};
+
+typedef std::map<int, int, ExceptLess> emtype;
+
+static_assert( !noexcept( emtype(std::declval<emtype>(),
+		std::declval<const typename emtype::allocator_type&>()) ),
+	       "except move constructor with allocator" );
diff --git a/libstdc++-v3/testsuite/23_containers/multimap/cons/noexcept_move_construct.cc b/libstdc++-v3/testsuite/23_containers/multimap/cons/noexcept_move_construct.cc
index 03ef459..9acfbb5 100644
--- a/libstdc++-v3/testsuite/23_containers/multimap/cons/noexcept_move_construct.cc
+++ b/libstdc++-v3/testsuite/23_containers/multimap/cons/noexcept_move_construct.cc
@@ -23,4 +23,25 @@
 
 typedef std::multimap<int, int> mmtype;
 
-static_assert(std::is_nothrow_move_constructible<mmtype>::value, "Error");
+static_assert( std::is_nothrow_move_constructible<mmtype>::value,
+	       "noexcept move constructor" );
+static_assert( noexcept( mmtype(std::declval<mmtype>(),
+		std::declval<const typename mmtype::allocator_type&>()) ),
+	       "noexcept move constructor with allocator" );
+
+struct ExceptLess
+{
+  ExceptLess() = default;
+  ExceptLess(const ExceptLess&) /* noexcept */
+  { }
+
+  bool
+  operator()(int l, int r) const
+  { return l < r; }
+};
+
+typedef std::multimap<int, int, ExceptLess> emmtype;
+
+static_assert( !noexcept( emmtype(std::declval<emmtype>(),
+		std::declval<const typename emmtype::allocator_type&>()) ),
+	       "except move constructor with allocator" );
diff --git a/libstdc++-v3/testsuite/23_containers/multiset/cons/noexcept_move_construct.cc b/libstdc++-v3/testsuite/23_containers/multiset/cons/noexcept_move_construct.cc
index 49878e0..adc7a72 100644
--- a/libstdc++-v3/testsuite/23_containers/multiset/cons/noexcept_move_construct.cc
+++ b/libstdc++-v3/testsuite/23_containers/multiset/cons/noexcept_move_construct.cc
@@ -23,4 +23,25 @@
 
 typedef std::multiset<int> mstype;
 
-static_assert(std::is_nothrow_move_constructible<mstype>::value, "Error");
+static_assert( std::is_nothrow_move_constructible<mstype>::value,
+	       "noexcept move constructor" );
+static_assert( noexcept( mstype(std::declval<mstype>(),
+		std::declval<const typename mstype::allocator_type&>()) ),
+	       "noexcept move constructor with allocator" );
+
+struct ExceptLess
+{
+  ExceptLess() = default;
+  ExceptLess(const ExceptLess&) /* noexcept */
+  { }
+
+  bool
+  operator()(int l, int r) const
+  { return l < r; }
+};
+
+typedef std::multiset<int, ExceptLess> emstype;
+
+static_assert( !noexcept( emstype(std::declval<emstype>(),
+		std::declval<const typename emstype::allocator_type&>()) ),
+	       "except move constructor with allocator" );
diff --git a/libstdc++-v3/testsuite/23_containers/set/cons/noexcept_move_construct.cc b/libstdc++-v3/testsuite/23_containers/set/cons/noexcept_move_construct.cc
index 95b5100..0e1f2fa 100644
--- a/libstdc++-v3/testsuite/23_containers/set/cons/noexcept_move_construct.cc
+++ b/libstdc++-v3/testsuite/23_containers/set/cons/noexcept_move_construct.cc
@@ -23,4 +23,25 @@
 
 typedef std::set<int> stype;
 
-static_assert(std::is_nothrow_move_constructible<stype>::value, "Error");
+static_assert( std::is_nothrow_move_constructible<stype>::value,
+	       "noexcept move constructor" );
+static_assert( noexcept( stype(std::declval<stype>(),
+		std::declval<const typename stype::allocator_type&>()) ),
+	       "noexcept move constructor with allocator" );
+
+struct ExceptLess
+{
+  ExceptLess() = default;
+  ExceptLess(const ExceptLess&) /* noexcept */
+  { }
+
+  bool
+  operator()(int l, int r) const
+  { return l < r; }
+};
+
+typedef std::set<int, ExceptLess> estype;
+
+static_assert( !noexcept( estype(std::declval<estype>(),
+		std::declval<const typename estype::allocator_type&>()) ),
+	       "except move constructor with allocator" );

Re: Rb_tree constructor optimization

[François Dumont]

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

On 08/09/2017 17:50, Jonathan Wakely wrote:
>
> Since we know __a == __x.get_allocator() we could just do:
>
>      _Rb_tree(_Rb_tree&& __x, _Node_allocator&&, true_type)
> noexcept(is_nothrow_move_constructible<_Rb_tree_impl<_Compare>>::value)
>      : _M_impl(std::move(__x._M_impl))
>      { }
>
> This means we don't need the new constructor.

     You want to consider that a always equal allocator is stateless and 
so that the provided allocator rvalue reference do not need to be moved. 
IMHO you can have allocator with state that do not participate in 
comparison like some monitoring info.

     I'm not confortable with that and prefer to keep current behavior 
so I propose this new patch considering all your other remarks.

     I change noexcept qualification on [multi]map/set constructors to 
just rely on _Rep_type constructor noexcept qualification to not 
duplicate it.

François



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

diff --git a/libstdc++-v3/include/bits/stl_map.h b/libstdc++-v3/include/bits/stl_map.h
index 0e8a98a..cdd2e7c 100644
--- a/libstdc++-v3/include/bits/stl_map.h
+++ b/libstdc++-v3/include/bits/stl_map.h
@@ -235,8 +235,8 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
 
       /// Allocator-extended move constructor.
       map(map&& __m, const allocator_type& __a)
-      noexcept(is_nothrow_copy_constructible<_Compare>::value
-	       && _Alloc_traits::_S_always_equal())
+      noexcept( noexcept(
+	_Rep_type(declval<_Rep_type>(), declval<_Pair_alloc_type>())) )
       : _M_t(std::move(__m._M_t), _Pair_alloc_type(__a)) { }
 
       /// Allocator-extended initialier-list constructor.
diff --git a/libstdc++-v3/include/bits/stl_multimap.h b/libstdc++-v3/include/bits/stl_multimap.h
index 7e3cea4..d32104d 100644
--- a/libstdc++-v3/include/bits/stl_multimap.h
+++ b/libstdc++-v3/include/bits/stl_multimap.h
@@ -232,8 +232,8 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
 
       /// Allocator-extended move constructor.
       multimap(multimap&& __m, const allocator_type& __a)
-      noexcept(is_nothrow_copy_constructible<_Compare>::value
-	       && _Alloc_traits::_S_always_equal())
+      noexcept( noexcept(
+	_Rep_type(declval<_Rep_type>(), declval<_Pair_alloc_type>())) )
       : _M_t(std::move(__m._M_t), _Pair_alloc_type(__a)) { }
 
       /// Allocator-extended initialier-list constructor.
diff --git a/libstdc++-v3/include/bits/stl_multiset.h b/libstdc++-v3/include/bits/stl_multiset.h
index 517e77e..9ab4ab7 100644
--- a/libstdc++-v3/include/bits/stl_multiset.h
+++ b/libstdc++-v3/include/bits/stl_multiset.h
@@ -244,8 +244,8 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
 
       /// Allocator-extended move constructor.
       multiset(multiset&& __m, const allocator_type& __a)
-      noexcept(is_nothrow_copy_constructible<_Compare>::value
-	       && _Alloc_traits::_S_always_equal())
+      noexcept( noexcept(
+	_Rep_type(declval<_Rep_type>(), declval<_Key_alloc_type>())) )
       : _M_t(std::move(__m._M_t), _Key_alloc_type(__a)) { }
 
       /// Allocator-extended initialier-list constructor.
diff --git a/libstdc++-v3/include/bits/stl_set.h b/libstdc++-v3/include/bits/stl_set.h
index e804a7c..6b64bcd 100644
--- a/libstdc++-v3/include/bits/stl_set.h
+++ b/libstdc++-v3/include/bits/stl_set.h
@@ -248,8 +248,8 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
 
       /// Allocator-extended move constructor.
       set(set&& __x, const allocator_type& __a)
-      noexcept(is_nothrow_copy_constructible<_Compare>::value
-	       && _Alloc_traits::_S_always_equal())
+      noexcept( noexcept(
+	_Rep_type(declval<_Rep_type>(), declval<_Key_alloc_type>())) )
       : _M_t(std::move(__x._M_t), _Key_alloc_type(__a)) { }
 
       /// Allocator-extended initialier-list constructor.
diff --git a/libstdc++-v3/include/bits/stl_tree.h b/libstdc++-v3/include/bits/stl_tree.h
index c2417f1..7aacc24 100644
--- a/libstdc++-v3/include/bits/stl_tree.h
+++ b/libstdc++-v3/include/bits/stl_tree.h
@@ -704,6 +704,12 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 #else
 	  _Rb_tree_impl(_Rb_tree_impl&&) = default;
 
+	  _Rb_tree_impl(_Rb_tree_impl&& __x, _Node_allocator&& __a)
+	  : _Node_allocator(std::move(__a)),
+	    _Base_key_compare(std::move(__x)),
+	    _Rb_tree_header(std::move(__x))
+	  { }
+
 	  _Rb_tree_impl(const _Key_compare& __comp, _Node_allocator&& __a)
 	  : _Node_allocator(std::move(__a)), _Base_key_compare(__comp)
 	  { }
@@ -947,7 +953,25 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
       : _Rb_tree(std::move(__x), _Node_allocator(__a))
       { }
 
-      _Rb_tree(_Rb_tree&& __x, _Node_allocator&& __a);
+    private:
+      _Rb_tree(_Rb_tree&& __x, _Node_allocator&& __a, true_type)
+      : _M_impl(std::move(__x._M_impl), std::move(__a))
+      { }
+
+      _Rb_tree(_Rb_tree&& __x, _Node_allocator&& __a, false_type)
+      : _M_impl(__x._M_impl._M_key_compare, std::move(__a))
+      {
+	if (__x._M_root() != nullptr)
+	  _M_move_data(__x, false_type{});
+      }
+
+    public:
+      _Rb_tree(_Rb_tree&& __x, _Node_allocator&& __a)
+      noexcept(is_nothrow_move_constructible<_Rb_tree_impl<_Compare>>::value
+	       && _Alloc_traits::_S_always_equal())
+      : _Rb_tree(std::move(__x), std::move(__a),
+		 typename _Alloc_traits::is_always_equal{})
+      { }
 #endif
 
       ~_Rb_tree() _GLIBCXX_NOEXCEPT
@@ -1347,22 +1371,22 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
     private:
       // Move elements from container with equal allocator.
       void
-      _M_move_data(_Rb_tree& __x, std::true_type)
+      _M_move_data(_Rb_tree& __x, 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.
       void
-      _M_move_data(_Rb_tree&, std::false_type);
+      _M_move_data(_Rb_tree&, false_type);
 
       // Move assignment from container with equal allocator.
       void
-      _M_move_assign(_Rb_tree&, std::true_type);
+      _M_move_assign(_Rb_tree&, true_type);
 
       // Move assignment from container with possibly non-equal allocator,
       // which might result in a copy not a move.
       void
-      _M_move_assign(_Rb_tree&, std::false_type);
+      _M_move_assign(_Rb_tree&, false_type);
 #endif
 
 #if __cplusplus > 201402L
@@ -1590,23 +1614,12 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 #if __cplusplus >= 201103L
   template<typename _Key, typename _Val, typename _KeyOfValue,
 	   typename _Compare, typename _Alloc>
-    _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
-    _Rb_tree(_Rb_tree&& __x, _Node_allocator&& __a)
-    : _M_impl(__x._M_impl._M_key_compare, std::move(__a))
-    {
-      using __eq = typename _Alloc_traits::is_always_equal;
-      if (__x._M_root() != nullptr)
-	_M_move_data(__x, __eq());
-    }
-
-  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)
+    _M_move_data(_Rb_tree& __x, false_type)
     {
       if (_M_get_Node_allocator() == __x._M_get_Node_allocator())
-	_M_move_data(__x, std::true_type());
+	_M_move_data(__x, true_type());
       else
 	{
 	  _Alloc_node __an(*this);
@@ -1628,7 +1641,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
     {
       clear();
       if (__x._M_root() != nullptr)
-	_M_move_data(__x, std::true_type());
+	_M_move_data(__x, true_type());
       std::__alloc_on_move(_M_get_Node_allocator(),
 			   __x._M_get_Node_allocator());
     }

Re: Rb_tree constructor optimization

[Jonathan Wakely]

On 28/08/17 21:12 +0200, François Dumont wrote:
>Hi
>
>    Here is the always equal allocator optimization for associative 
>containers.
>
>    Tested under Linux x86_64.
>
>    * include/bits/stl_tree.h
>    (_Rb_tree_impl(_Rb_tree_impl&&, _Node_allocator&&)): New.
>    (_Rb_tree(_Rb_tree&&, _Node_allocator&&, std::true_type)): New.
>    (_Rb_tree(_Rb_tree&&, _Node_allocator&&, std::false_type)): Likewise.
>    (_Rb_tree(_Rb_tree&&, _Node_allocator&&)): Adapt, use latters.
>
>    Ok to apply ?
>
>François
>
>

>diff --git a/libstdc++-v3/include/bits/stl_tree.h b/libstdc++-v3/include/bits/stl_tree.h
>index c2417f1..f7d34e3 100644
>--- a/libstdc++-v3/include/bits/stl_tree.h
>+++ b/libstdc++-v3/include/bits/stl_tree.h
>@@ -704,6 +704,12 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
> #else
> 	  _Rb_tree_impl(_Rb_tree_impl&&) = default;
> 
>+	  _Rb_tree_impl(_Rb_tree_impl&& __x, _Node_allocator&& __a) noexcept

This is an unconditional noexcept, but ...

>+	    : _Node_allocator(std::move(__a)),
>+	      _Base_key_compare(std::move(__x)),

This constructor has a conditional noexcept. That's a bug.

>+	      _Rb_tree_header(std::move(__x))
>+	  { }

However, I don't think we need this new constructor anyway, see below.

> 	  _Rb_tree_impl(const _Key_compare& __comp, _Node_allocator&& __a)
> 	  : _Node_allocator(std::move(__a)), _Base_key_compare(__comp)
> 	  { }
>@@ -947,7 +953,18 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
>       : _Rb_tree(std::move(__x), _Node_allocator(__a))
>       { }
> 
>-      _Rb_tree(_Rb_tree&& __x, _Node_allocator&& __a);
>+    private:
>+      _Rb_tree(_Rb_tree&& __x, _Node_allocator&& __a, std::true_type) noexcept

This noexcept should be conditional.

>+      : _M_impl(std::move(__x._M_impl), std::move(__a))
>+      { }

Since we know __a == __x.get_allocator() we could just do:

      _Rb_tree(_Rb_tree&& __x, _Node_allocator&&, true_type)
      noexcept(is_nothrow_move_constructible<_Rb_tree_impl<_Compare>>::value)
      : _M_impl(std::move(__x._M_impl))
      { }

This means we don't need the new constructor.

Or equivalently, just delegate to the move constructor:

      _Rb_tree(_Rb_tree&& __x, _Node_allocator&&, true_type)
      noexcept(is_nothrow_move_constructible<_Rb_tree>::value)
      : _Rb_tree(std::move(__x))
      { }

>+      _Rb_tree(_Rb_tree&& __x, _Node_allocator&& __a, std::false_type);
>+
>+    public:
>+      _Rb_tree(_Rb_tree&& __x, _Node_allocator&& __a)
>+      : _Rb_tree(std::move(__x), std::move(__a),
>+		 typename _Alloc_traits::is_always_equal{})
>+      { }
> #endif
> 
>       ~_Rb_tree() _GLIBCXX_NOEXCEPT
>@@ -1591,12 +1608,11 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
>   template<typename _Key, typename _Val, typename _KeyOfValue,
> 	   typename _Compare, typename _Alloc>
>     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
>-    _Rb_tree(_Rb_tree&& __x, _Node_allocator&& __a)
>+    _Rb_tree(_Rb_tree&& __x, _Node_allocator&& __a, std::false_type __eq)
>     : _M_impl(__x._M_impl._M_key_compare, std::move(__a))
>     {
>-      using __eq = typename _Alloc_traits::is_always_equal;
>       if (__x._M_root() != nullptr)
>-	_M_move_data(__x, __eq());
>+	_M_move_data(__x, __eq);
>     }

I think this constructor is simple enough that it should be defined
in-class, so it's inline.

There's no need to qualify true_type and false_type with the std
namespace (I don't know why some of the existing code does that).

Rb_tree constructor optimization

[François Dumont]

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

Hi

     Here is the always equal allocator optimization for associative 
containers.

     Tested under Linux x86_64.

     * include/bits/stl_tree.h
     (_Rb_tree_impl(_Rb_tree_impl&&, _Node_allocator&&)): New.
     (_Rb_tree(_Rb_tree&&, _Node_allocator&&, std::true_type)): New.
     (_Rb_tree(_Rb_tree&&, _Node_allocator&&, std::false_type)): Likewise.
     (_Rb_tree(_Rb_tree&&, _Node_allocator&&)): Adapt, use latters.

     Ok to apply ?

François



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

diff --git a/libstdc++-v3/include/bits/stl_tree.h b/libstdc++-v3/include/bits/stl_tree.h
index c2417f1..f7d34e3 100644
--- a/libstdc++-v3/include/bits/stl_tree.h
+++ b/libstdc++-v3/include/bits/stl_tree.h
@@ -704,6 +704,12 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 #else
 	  _Rb_tree_impl(_Rb_tree_impl&&) = default;
 
+	  _Rb_tree_impl(_Rb_tree_impl&& __x, _Node_allocator&& __a) noexcept
+	    : _Node_allocator(std::move(__a)),
+	      _Base_key_compare(std::move(__x)),
+	      _Rb_tree_header(std::move(__x))
+	  { }
+
 	  _Rb_tree_impl(const _Key_compare& __comp, _Node_allocator&& __a)
 	  : _Node_allocator(std::move(__a)), _Base_key_compare(__comp)
 	  { }
@@ -947,7 +953,18 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
       : _Rb_tree(std::move(__x), _Node_allocator(__a))
       { }
 
-      _Rb_tree(_Rb_tree&& __x, _Node_allocator&& __a);
+    private:
+      _Rb_tree(_Rb_tree&& __x, _Node_allocator&& __a, std::true_type) noexcept
+      : _M_impl(std::move(__x._M_impl), std::move(__a))
+      { }
+
+      _Rb_tree(_Rb_tree&& __x, _Node_allocator&& __a, std::false_type);
+
+    public:
+      _Rb_tree(_Rb_tree&& __x, _Node_allocator&& __a)
+      : _Rb_tree(std::move(__x), std::move(__a),
+		 typename _Alloc_traits::is_always_equal{})
+      { }
 #endif
 
       ~_Rb_tree() _GLIBCXX_NOEXCEPT
@@ -1591,12 +1608,11 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
   template<typename _Key, typename _Val, typename _KeyOfValue,
 	   typename _Compare, typename _Alloc>
     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
-    _Rb_tree(_Rb_tree&& __x, _Node_allocator&& __a)
+    _Rb_tree(_Rb_tree&& __x, _Node_allocator&& __a, std::false_type __eq)
     : _M_impl(__x._M_impl._M_key_compare, std::move(__a))
     {
-      using __eq = typename _Alloc_traits::is_always_equal;
       if (__x._M_root() != nullptr)
-	_M_move_data(__x, __eq());
+	_M_move_data(__x, __eq);
     }
 
   template<typename _Key, typename _Val, typename _KeyOfValue,