libstdc++: Implement DR 526 on [forward_]list remove_if/unique [PR 91620]

Respect DR 526 in implementation of std::[forward_]list remove/remove_if/unique.
[forward_]list::remove was already implementing it but the implementation has
been modified to generalize the following pattern. All nodes to remove are
collected in an intermediate [forward_]list which purpose is just to be
detroyed once out of scope.

libstdc++-v3/ChangeLog:

	PR libstdc++/91620
	* include/bits/forward_list.tcc (forward_list<>::remove): Collect nodes
	to destroy in an intermediate forward_list.
	(forward_list<>::remove_if, forward_list<>::unique): Likewise.
	* include/bits/list.tcc (list<>::remove, list<>::unique): Likewise.
	(list<>::remove_if): Likewise.
	* include/debug/forward_list (forward_list<>::_M_erase_after): Remove.
	(forward_list<>::erase_after): Adapt.
	(forward_list<>::remove, forward_list<>::remove_if): Collect nodes to
	destroy in an intermediate forward_list.
	(forward_list<>::unique): Likewise.
	* include/debug/list (list<>::remove, list<>::unique): Likewise.
	(list<>::remove_if): Likewise.
	* testsuite/23_containers/forward_list/operations/91620.cc: New test.
	* testsuite/23_containers/list/operations/91620.cc: New test.

2 files changed, 104 insertions, 69 deletions

diff --git a/libstdc++-v3/include/debug/forward_list b/libstdc++-v3/include/debug/forward_list
index fc6bf6359e9..7a00417ccb2 100644
--- a/libstdc++-v3/include/debug/forward_list
+++ b/libstdc++-v3/include/debug/forward_list
@@ -452,21 +452,15 @@ namespace __debug
 	return { _Base::insert_after(__pos.base(), __il), this };
       }
 
-    private:
-      _Base_iterator
-      _M_erase_after(_Base_const_iterator __pos)
-      {
-	_Base_const_iterator __next = std::next(__pos);
-	this->_M_invalidate_if([__next](_Base_const_iterator __it)
-	  { return __it == __next; });
-	return _Base::erase_after(__pos);
-      }
-    public:
       iterator
       erase_after(const_iterator __pos)
       {
 	__glibcxx_check_erase_after(__pos);
-	return { _M_erase_after(__pos.base()), this };
+
+	_Base_const_iterator __next = std::next(__pos.base());
+	this->_M_invalidate_if([__next](_Base_const_iterator __it)
+			       { return __it == __next; });
+	return { _Base::erase_after(__pos.base()), this };
       }
 
       iterator
@@ -691,29 +685,23 @@ namespace __debug
 	  return _Base::remove(__val);
 
 	size_type __removed __attribute__((__unused__)) = 0;
-	_Base_iterator __x = _Base::before_begin();
-	_Base_iterator __old = __x++;
-	_Base_iterator __extra = _Base::end();
-	while (__x != _Base::end())
+	_Base __to_destroy(get_allocator());
+	_Base_const_iterator __x = _Base::cbefore_begin();
+	_Base_const_iterator __old = __x++;
+	while (__x != _Base::cend())
 	  {
 	    if (*__x == __val)
 	      {
-		if (std::__addressof(*__x) != std::__addressof(__val))
-		  {
-		    __x = _M_erase_after(__old);
-		    _GLIBCXX20_ONLY( __removed++ );
-		    continue;
-		  }
-		else
-		  __extra = __old;
+		_Base_const_iterator __next = std::next(__old);
+		this->_M_invalidate_if([__next](_Base_const_iterator __it)
+				       { return __it == __next; });
+		__to_destroy.splice_after(__to_destroy.cbefore_begin(),
+					  _M_base(), __old);
+		__x = __old;
+		_GLIBCXX20_ONLY( __removed++ );
 	      }
-	    __old = __x++;
-	  }
 
-	if (__extra != _Base::end())
-	  {
-	    this->_M_erase_after(__extra);
-	    _GLIBCXX20_ONLY( __removed++ );
+	    __old = __x++;
 	  }
 
 	return _GLIBCXX20_ONLY( __removed );
@@ -727,16 +715,23 @@ namespace __debug
 	    return _Base::remove_if(__pred);
 
 	  size_type __removed __attribute__((__unused__)) = 0;
+	  _Base __to_destroy(get_allocator());
 	  _Base_iterator __x = _Base::before_begin();
 	  _Base_iterator __old = __x++;
 	  while (__x != _Base::end())
-	    if (__pred(*__x))
-	      {
-		__x = _M_erase_after(__old);
-		_GLIBCXX20_ONLY( __removed++ );
-	      }
-	    else
+	    {
+	      if (__pred(*__x))
+		{
+		  this->_M_invalidate_if([__x](_Base_const_iterator __it)
+					 { return __it == __x; });
+		  __to_destroy.splice_after(__to_destroy.cbefore_begin(),
+					    _M_base(), __old);
+		  __x = __old;
+		  _GLIBCXX20_ONLY( __removed++ );
+		}
+
 	      __old = __x++;
+	    }
 
 	  return _GLIBCXX20_ONLY( __removed );
 	}
@@ -753,22 +748,27 @@ namespace __debug
 	  if (!this->_M_iterators && !this->_M_const_iterators)
 	    return _Base::unique(__binary_pred);
 
-	  _Base_iterator __first = _Base::begin();
-	  _Base_iterator __last = _Base::end();
+	  _Base_const_iterator __first = _Base::cbegin();
+	  _Base_const_iterator __last = _Base::cend();
 	  if (__first == __last)
 	    return _GLIBCXX20_ONLY(0);
 
 	  size_type __removed __attribute__((__unused__)) = 0;
-	  _Base_iterator __next = std::next(__first);
+	  _Base __to_destroy(get_allocator());
+	  _Base_const_iterator __next = std::next(__first);
 	  while (__next != __last)
 	    {
 	      if (__binary_pred(*__first, *__next))
 		{
-		  __next = _M_erase_after(__first);
+		  this->_M_invalidate_if([__next](_Base_const_iterator __it)
+					 { return __it == __next; });
+		  __to_destroy.splice_after(__to_destroy.cbefore_begin(),
+					    _M_base(), __first);
+		  __next = __first;
 		  _GLIBCXX20_ONLY( __removed++ );
 		}
-	      else
-		__first = __next++;
+
+	      __first = __next++;
 	    }
 
 	  return _GLIBCXX20_ONLY( __removed );
diff --git a/libstdc++-v3/include/debug/list b/libstdc++-v3/include/debug/list
index 8f2a8cb0f01..b5652fd9fdc 100644
--- a/libstdc++-v3/include/debug/list
+++ b/libstdc++-v3/include/debug/list
@@ -681,36 +681,36 @@ namespace __debug
 	if (!this->_M_iterators && !this->_M_const_iterators)
 	  return _Base::remove(__value);
 
+#if !_GLIBCXX_USE_CXX11_ABI
 	size_type __removed __attribute__((__unused__)) = 0;
+#endif
+	_Base __to_destroy(get_allocator());
 	_Base_iterator __first = _Base::begin();
 	_Base_iterator __last = _Base::end();
-	_Base_iterator __extra = __last;
 	while (__first != __last)
 	  {
+	    _Base_iterator __next = __first;
+	    ++__next;
 	    if (*__first == __value)
-	      // _GLIBCXX_RESOLVE_LIB_DEFECTS
-	      // 526. Is it undefined if a function in the standard changes
-	      // in parameters?
-	      if (std::__addressof(*__first) != std::__addressof(__value))
-		{
-		  __first = _M_erase(__first);
-		  _GLIBCXX20_ONLY( __removed++ );
-		}
-	      else
-		{
-		  __extra = __first;
-		  ++__first;
-		}
-	    else
-	      ++__first;
-	  }
+	      {
+		// _GLIBCXX_RESOLVE_LIB_DEFECTS
+		// 526. Is it undefined if a function in the standard changes
+		// in parameters?
+		this->_M_invalidate_if(_Equal(__first));
+		__to_destroy.splice(__to_destroy.begin(), _M_base(), __first);
+#if !_GLIBCXX_USE_CXX11_ABI
+		_GLIBCXX20_ONLY( __removed++ );
+#endif
+	      }
 
-	if (__extra != __last)
-	  {
-	    _M_erase(__extra);
-	    _GLIBCXX20_ONLY( __removed++ );
+	    __first = __next;
 	  }
+
+#if !_GLIBCXX_USE_CXX11_ABI
 	return _GLIBCXX20_ONLY( __removed );
+#else
+	return _GLIBCXX20_ONLY( __to_destroy.size() );
+#endif
       }
 
       template<class _Predicate>
@@ -720,17 +720,31 @@ namespace __debug
 	  if (!this->_M_iterators && !this->_M_const_iterators)
 	    return _Base::remove_if(__pred);
 
+#if !_GLIBCXX_USE_CXX11_ABI
 	  size_type __removed __attribute__((__unused__)) = 0;
+#endif
+	  _Base __to_destroy(get_allocator());
 	  for (_Base_iterator __x = _Base::begin(); __x != _Base::end(); )
+	  {
+	    _Base_iterator __next = __x;
+	    ++__next;
 	    if (__pred(*__x))
 	      {
-		__x = _M_erase(__x);
+		this->_M_invalidate_if(_Equal(__x));
+		__to_destroy.splice(__to_destroy.begin(), _M_base(), __x);
+#if !_GLIBCXX_USE_CXX11_ABI
 		_GLIBCXX20_ONLY( __removed++ );
+#endif
 	      }
-	    else
-	      ++__x;
 
+	    __x = __next;
+	  }
+
+#if !_GLIBCXX_USE_CXX11_ABI
 	  return _GLIBCXX20_ONLY( __removed );
+#else
+	  return _GLIBCXX20_ONLY( __to_destroy.size() );
+#endif
 	}
 
       _GLIBCXX_LIST_REMOVE_RETURN_TYPE_TAG
@@ -743,21 +757,31 @@ namespace __debug
 	if (empty())
 	  return _GLIBCXX20_ONLY(0);
 
+#if !_GLIBCXX_USE_CXX11_ABI
         size_type __removed __attribute__((__unused__)) = 0;
+#endif
+	_Base __to_destroy(get_allocator());
 	_Base_iterator __first = _Base::begin();
 	_Base_iterator __last = _Base::end();
 	_Base_iterator __next = __first;
 	while (++__next != __last)
 	  if (*__first == *__next)
 	    {
-	      _M_erase(__next);
+	      this->_M_invalidate_if(_Equal(__next));
+	      __to_destroy.splice(__to_destroy.begin(), _M_base(), __next);
 	      __next = __first;
+#if !_GLIBCXX_USE_CXX11_ABI
 	      _GLIBCXX20_ONLY( __removed++ );
+#endif
 	    }
 	  else
 	    __first = __next;
 
+#if !_GLIBCXX_USE_CXX11_ABI
 	return _GLIBCXX20_ONLY( __removed );
+#else
+	return _GLIBCXX20_ONLY( __to_destroy.size() );
+#endif
       }
 
       template<class _BinaryPredicate>
@@ -770,21 +794,32 @@ namespace __debug
 	  if (empty())
 	    return _GLIBCXX20_ONLY(0);
 
+
+#if !_GLIBCXX_USE_CXX11_ABI
 	  size_type __removed __attribute__((__unused__)) = 0;
+#endif
+	  _Base __to_destroy(get_allocator());
 	  _Base_iterator __first = _Base::begin();
 	  _Base_iterator __last = _Base::end();
-	  _Base_iterator __next = __first;;
+	  _Base_iterator __next = __first;
 	  while (++__next != __last)
 	    if (__binary_pred(*__first, *__next))
 	      {
-		_M_erase(__next);
+		this->_M_invalidate_if(_Equal(__next));
+		__to_destroy.splice(__to_destroy.begin(), _M_base(), __next);
 		__next = __first;
+#if !_GLIBCXX_USE_CXX11_ABI
 		_GLIBCXX20_ONLY( __removed++ );
+#endif
 	      }
 	    else
 	      __first = __next;
 
-	  return _GLIBCXX20_ONLY( __removed );
+#if !_GLIBCXX_USE_CXX11_ABI
+	return _GLIBCXX20_ONLY( __removed );
+#else
+	return _GLIBCXX20_ONLY( __to_destroy.size() );
+#endif
 	}
 
 #undef _GLIBCXX_LIST_REMOVE_RETURN_TYPE_TAG