[PATCH] PR libstdc++/91620 Implement DR 526 for std::[forward_]list::remove_if/unique

[PATCH] PR libstdc++/91620 Implement DR 526 for std::[forward_]list::remove_if/unique

[François Dumont]

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

Here is the patch to extend DR 526 to forward_list and list remove_if 
and unique.

As the adopted pattern is simpler I also applied it to the remove methods.

     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.

Tested under Linux x86_64 normal and debug modes.

Ok to commit ?

François


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

diff --git a/libstdc++-v3/include/bits/forward_list.tcc b/libstdc++-v3/include/bits/forward_list.tcc
index 088111e3330..70de7e75a43 100644
--- a/libstdc++-v3/include/bits/forward_list.tcc
+++ b/libstdc++-v3/include/bits/forward_list.tcc
@@ -290,30 +290,19 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
     remove(const _Tp& __val) -> __remove_return_type
     {
       size_type __removed __attribute__((__unused__)) = 0;
-      _Node_base* __curr = &this->_M_impl._M_head;
-      _Node_base* __extra = nullptr;
+      forward_list __to_destroy(get_allocator());
 
-      while (_Node* __tmp = static_cast<_Node*>(__curr->_M_next))
-	{
+      auto __prev_it = cbefore_begin();
+      while (_Node* __tmp = static_cast<_Node*>(__prev_it._M_node->_M_next))
 	if (*__tmp->_M_valptr() == __val)
 	  {
-	      if (__tmp->_M_valptr() != std::__addressof(__val))
-		{
-		  this->_M_erase_after(__curr);
+	    __to_destroy.splice_after(__to_destroy.cbefore_begin(),
+				      *this, __prev_it);
 	    _GLIBCXX20_ONLY( __removed++ );
-		  continue;
 	  }
 	else
-		__extra = __curr;
-	    }
-	  __curr = __curr->_M_next;
-	}
+	  ++__prev_it;
 
-      if (__extra)
-	{
-	  this->_M_erase_after(__extra);
-	  _GLIBCXX20_ONLY( __removed++ );
-	}
       return _GLIBCXX20_ONLY( __removed );
     }
 
@@ -324,17 +313,19 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
       remove_if(_Pred __pred) -> __remove_return_type
       {
 	size_type __removed __attribute__((__unused__)) = 0;
-	_Node_base* __curr = &this->_M_impl._M_head;
-	while (_Node* __tmp = static_cast<_Node*>(__curr->_M_next))
-	  {
+	forward_list __to_destroy(get_allocator());
+
+	auto __prev_it = cbefore_begin();
+	while (_Node* __tmp = static_cast<_Node*>(__prev_it._M_node->_M_next))
 	  if (__pred(*__tmp->_M_valptr()))
 	    {
-		this->_M_erase_after(__curr);
+	      __to_destroy.splice_after(__to_destroy.cbefore_begin(),
+					*this, __prev_it);
 	      _GLIBCXX20_ONLY( __removed++ );
 	    }
 	  else
-	      __curr = __curr->_M_next;
-	  }
+	    ++__prev_it;
+
 	return _GLIBCXX20_ONLY( __removed );
       }
 
@@ -348,19 +339,23 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
 	iterator __last = end();
 	if (__first == __last)
 	  return _GLIBCXX20_ONLY(0);
+
+	forward_list __to_destroy(get_allocator());
 	size_type __removed __attribute__((__unused__)) = 0;
 	iterator __next = __first;
 	while (++__next != __last)
 	{
 	  if (__binary_pred(*__first, *__next))
 	    {
-	      erase_after(__first);
+	      __to_destroy.splice_after(__to_destroy.cbefore_begin(),
+					*this, __first);
 	      _GLIBCXX20_ONLY( __removed++ );
 	    }
 	  else
 	    __first = __next;
 	  __next = __first;
 	}
+
 	return _GLIBCXX20_ONLY( __removed );
       }
 
diff --git a/libstdc++-v3/include/bits/list.tcc b/libstdc++-v3/include/bits/list.tcc
index 0ac6654b079..5a6fd5b0824 100644
--- a/libstdc++-v3/include/bits/list.tcc
+++ b/libstdc++-v3/include/bits/list.tcc
@@ -331,10 +331,12 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
     list<_Tp, _Alloc>::
     remove(const value_type& __value)
     {
+#if !_GLIBCXX_USE_CXX11_ABI
       size_type __removed __attribute__((__unused__)) = 0;
+#endif
+      list __to_destroy(get_allocator());
       iterator __first = begin();
       iterator __last = end();
-      iterator __extra = __last;
       while (__first != __last)
 	{
 	  iterator __next = __first;
@@ -344,22 +346,20 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
 	      // _GLIBCXX_RESOLVE_LIB_DEFECTS
 	      // 526. Is it undefined if a function in the standard changes
 	      // in parameters?
-	      if (std::__addressof(*__first) != std::__addressof(__value))
-		{
-		  _M_erase(__first);
+	      __to_destroy.splice(__to_destroy.begin(), *this, __first);
+#if !_GLIBCXX_USE_CXX11_ABI
 	      _GLIBCXX20_ONLY( __removed++ );
+#endif
 	    }
-	      else
-		__extra = __first;
-	    }
+
 	  __first = __next;
 	}
-      if (__extra != __last)
-	{
-	  _M_erase(__extra);
-	  _GLIBCXX20_ONLY( __removed++ );
-	}
+
+#if !_GLIBCXX_USE_CXX11_ABI
 	return _GLIBCXX20_ONLY( __removed );
+#else
+	return _GLIBCXX20_ONLY( __to_destroy.size() );
+#endif
     }
 
   template<typename _Tp, typename _Alloc>
@@ -371,20 +371,30 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
       iterator __last = end();
       if (__first == __last)
 	return _GLIBCXX20_ONLY( 0 );
+#if !_GLIBCXX_USE_CXX11_ABI
       size_type __removed __attribute__((__unused__)) = 0;
+#endif
+      list __to_destroy(get_allocator());
       iterator __next = __first;
       while (++__next != __last)
 	{
 	  if (*__first == *__next)
 	    {
-	      _M_erase(__next);
+	      __to_destroy.splice(__to_destroy.begin(), *this, __next);
+#if !_GLIBCXX_USE_CXX11_ABI
 	      _GLIBCXX20_ONLY( __removed++ );
+#endif
 	    }
 	  else
 	    __first = __next;
 	  __next = __first;
 	}
+
+#if !_GLIBCXX_USE_CXX11_ABI
       return _GLIBCXX20_ONLY( __removed );
+#else
+      return _GLIBCXX20_ONLY( __to_destroy.size() );
+#endif
     }
 
   template<typename _Tp, typename _Alloc>
@@ -533,7 +543,10 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
       list<_Tp, _Alloc>::
       remove_if(_Predicate __pred)
       {
+#if !_GLIBCXX_USE_CXX11_ABI
 	size_type __removed __attribute__((__unused__)) = 0;
+#endif
+	list __to_destroy(get_allocator());
 	iterator __first = begin();
 	iterator __last = end();
 	while (__first != __last)
@@ -542,12 +555,19 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
 	    ++__next;
 	    if (__pred(*__first))
 	      {
-		_M_erase(__first);
+		__to_destroy.splice(__to_destroy.begin(), *this, __first);
+#if !_GLIBCXX_USE_CXX11_ABI
 		_GLIBCXX20_ONLY( __removed++ );
+#endif
 	      }
 	    __first = __next;
 	  }
+
+#if !_GLIBCXX_USE_CXX11_ABI
 	return _GLIBCXX20_ONLY( __removed );
+#else
+	return _GLIBCXX20_ONLY( __to_destroy.size() );
+#endif
       }
 
   template<typename _Tp, typename _Alloc>
@@ -560,20 +580,30 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
         iterator __last = end();
         if (__first == __last)
 	  return _GLIBCXX20_ONLY(0);
+#if !_GLIBCXX_USE_CXX11_ABI
         size_type __removed __attribute__((__unused__)) = 0;
+#endif
+	list __to_destroy(get_allocator());
         iterator __next = __first;
         while (++__next != __last)
 	  {
 	    if (__binary_pred(*__first, *__next))
 	      {
-		_M_erase(__next);
+		__to_destroy.splice(__to_destroy.begin(), *this, __next);
+#if !_GLIBCXX_USE_CXX11_ABI
 		_GLIBCXX20_ONLY( __removed++ );
+#endif
 	      }
 	    else
 	      __first = __next;
 	    __next = __first;
 	  }
+
+#if !_GLIBCXX_USE_CXX11_ABI
 	return _GLIBCXX20_ONLY( __removed );
+#else
+	return _GLIBCXX20_ONLY( __to_destroy.size() );
+#endif
       }
 
 #undef _GLIBCXX20_ONLY
diff --git a/libstdc++-v3/include/debug/forward_list b/libstdc++-v3/include/debug/forward_list
index f1756ddec9d..9889eb9da83 100644
--- a/libstdc++-v3/include/debug/forward_list
+++ b/libstdc++-v3/include/debug/forward_list
@@ -442,21 +442,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
@@ -681,29 +675,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);
+		_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++ );
-		    continue;
-		  }
-		else
-		  __extra = __old;
-	      }
-	    __old = __x++;
 	      }
 
-	if (__extra != _Base::end())
-	  {
-	    this->_M_erase_after(__extra);
-	    _GLIBCXX20_ONLY( __removed++ );
+	    __old = __x++;
 	  }
 
 	return _GLIBCXX20_ONLY( __removed );
@@ -717,16 +705,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);
+		  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++ );
 		}
-	    else
+
 	      __old = __x++;
+	    }
 
 	  return _GLIBCXX20_ONLY( __removed );
 	}
@@ -743,21 +738,26 @@ 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++;
 	    }
 
diff --git a/libstdc++-v3/include/debug/list b/libstdc++-v3/include/debug/list
index 140546a633e..bc4895405d1 100644
--- a/libstdc++-v3/include/debug/list
+++ b/libstdc++-v3/include/debug/list
@@ -671,36 +671,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);
+		this->_M_invalidate_if(_Equal(__first));
+		__to_destroy.splice(__to_destroy.begin(), _M_base(), __first);
+#if !_GLIBCXX_USE_CXX11_ABI
 		_GLIBCXX20_ONLY( __removed++ );
-		}
-	      else
-		{
-		  __extra = __first;
-		  ++__first;
-		}
-	    else
-	      ++__first;
+#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>
@@ -710,17 +710,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
+	      }
+
+	    __x = __next;
 	  }
-	    else
-	      ++__x;
 
+#if !_GLIBCXX_USE_CXX11_ABI
 	  return _GLIBCXX20_ONLY( __removed );
+#else
+	  return _GLIBCXX20_ONLY( __to_destroy.size() );
+#endif
 	}
 
       _GLIBCXX_LIST_REMOVE_RETURN_TYPE_TAG
@@ -733,21 +747,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>
@@ -760,21 +784,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;
 
+#if !_GLIBCXX_USE_CXX11_ABI
 	return _GLIBCXX20_ONLY( __removed );
+#else
+	return _GLIBCXX20_ONLY( __to_destroy.size() );
+#endif
 	}
 
 #undef _GLIBCXX_LIST_REMOVE_RETURN_TYPE_TAG

Re: [PATCH] PR libstdc++/91620 Implement DR 526 for std::[forward_]list::remove_if/unique

[François Dumont]

Hi

     Isn't it something to fix before gcc 10 release ?

François

On 12/27/19 11:57 AM, François Dumont wrote:
> Here is the patch to extend DR 526 to forward_list and list remove_if 
> and unique.
>
> As the adopted pattern is simpler I also applied it to the remove 
> methods.
>
>     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.
>
> Tested under Linux x86_64 normal and debug modes.
>
> Ok to commit ?
>
> François
>

Re: [PATCH] PR libstdc++/91620 Implement DR 526 for std::[forward_]list::remove_if/unique

[Jonathan Wakely]

On 03/03/20 06:42 +0100, François Dumont wrote:
>Hi
>
>    Isn't it something to fix before gcc 10 release ?

No, I don't think so. It's not a regression.

Re: [PATCH] PR libstdc++/91620 Implement DR 526 for std::[forward_]list::remove_if/unique

[Jonathan Wakely]

On 03/03/20 21:32 +0000, Jonathan Wakely wrote:
>On 03/03/20 06:42 +0100, François Dumont wrote:
>>Hi
>>
>>    Isn't it something to fix before gcc 10 release ?
>
>No, I don't think so. It's not a regression.

(And is not experimental C++20 stuff, and is not just changing tests
or docs).

Re: [PATCH] PR libstdc++/91620 Implement DR 526 for std::[forward_]list::remove_if/unique

[François Dumont]

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

Gentle reminder, this time with tests.

I've added one for list::remove cause I think there was none, for 
forward_list we had remove_freed.cc.

I added
// { dg-options "-g -O0" }

in the new tests otherwise it doesn't fail, that's life with UB. I know 
that it can pass also with those options.

If you prefer we can go without it and let Valgrind detect the issue.

Whatever, once the patch is in place it doesn't fail anymore.

François


On 27/12/19 11:57 am, François Dumont wrote:
> Here is the patch to extend DR 526 to forward_list and list remove_if 
> and unique.
>
> As the adopted pattern is simpler I also applied it to the remove 
> methods.
>
>     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.
>
> Tested under Linux x86_64 normal and debug modes.
>
> Ok to commit ?
>
> François
>


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

diff --git a/libstdc++-v3/include/bits/forward_list.tcc b/libstdc++-v3/include/bits/forward_list.tcc
index c42bdc0fd13..3f94066bd55 100644
--- a/libstdc++-v3/include/bits/forward_list.tcc
+++ b/libstdc++-v3/include/bits/forward_list.tcc
@@ -290,30 +290,19 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
     remove(const _Tp& __val) -> __remove_return_type
     {
       size_type __removed __attribute__((__unused__)) = 0;
-      _Node_base* __curr = &this->_M_impl._M_head;
-      _Node_base* __extra = nullptr;
+      forward_list __to_destroy(get_allocator());
 
-      while (_Node* __tmp = static_cast<_Node*>(__curr->_M_next))
-	{
-	  if (*__tmp->_M_valptr() == __val)
-	    {
-	      if (__tmp->_M_valptr() != std::__addressof(__val))
-		{
-		  this->_M_erase_after(__curr);
-		  _GLIBCXX20_ONLY( __removed++ );
-		  continue;
-		}
-	      else
-		__extra = __curr;
-	    }
-	  __curr = __curr->_M_next;
-	}
+      auto __prev_it = cbefore_begin();
+      while (_Node* __tmp = static_cast<_Node*>(__prev_it._M_node->_M_next))
+	if (*__tmp->_M_valptr() == __val)
+	  {
+	    __to_destroy.splice_after(__to_destroy.cbefore_begin(),
+				      *this, __prev_it);
+	    _GLIBCXX20_ONLY( __removed++ );
+	  }
+	else
+	  ++__prev_it;
 
-      if (__extra)
-	{
-	  this->_M_erase_after(__extra);
-	  _GLIBCXX20_ONLY( __removed++ );
-	}
       return _GLIBCXX20_ONLY( __removed );
     }
 
@@ -324,17 +313,19 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
       remove_if(_Pred __pred) -> __remove_return_type
       {
 	size_type __removed __attribute__((__unused__)) = 0;
-	_Node_base* __curr = &this->_M_impl._M_head;
-	while (_Node* __tmp = static_cast<_Node*>(__curr->_M_next))
-	  {
-	    if (__pred(*__tmp->_M_valptr()))
-	      {
-		this->_M_erase_after(__curr);
-		_GLIBCXX20_ONLY( __removed++ );
-	      }
-	    else
-	      __curr = __curr->_M_next;
-	  }
+	forward_list __to_destroy(get_allocator());
+
+	auto __prev_it = cbefore_begin();
+	while (_Node* __tmp = static_cast<_Node*>(__prev_it._M_node->_M_next))
+	  if (__pred(*__tmp->_M_valptr()))
+	    {
+	      __to_destroy.splice_after(__to_destroy.cbefore_begin(),
+					*this, __prev_it);
+	      _GLIBCXX20_ONLY( __removed++ );
+	    }
+	  else
+	    ++__prev_it;
+
 	return _GLIBCXX20_ONLY( __removed );
       }
 
@@ -348,20 +339,24 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
 	iterator __last = end();
 	if (__first == __last)
 	  return _GLIBCXX20_ONLY(0);
+
+	forward_list __to_destroy(get_allocator());
 	size_type __removed __attribute__((__unused__)) = 0;
 	iterator __next = __first;
 	while (++__next != __last)
 	{
 	  if (__binary_pred(*__first, *__next))
 	    {
-	      erase_after(__first);
+	      __to_destroy.splice_after(__to_destroy.cbefore_begin(),
+					*this, __first);
 	      _GLIBCXX20_ONLY( __removed++ );
 	    }
 	  else
 	    __first = __next;
 	  __next = __first;
 	}
-        return _GLIBCXX20_ONLY( __removed );
+
+	return _GLIBCXX20_ONLY( __removed );
       }
 
 #undef _GLIBCXX20_ONLY
diff --git a/libstdc++-v3/include/bits/list.tcc b/libstdc++-v3/include/bits/list.tcc
index ce9e983c539..9b664f11454 100644
--- a/libstdc++-v3/include/bits/list.tcc
+++ b/libstdc++-v3/include/bits/list.tcc
@@ -331,10 +331,12 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
     list<_Tp, _Alloc>::
     remove(const value_type& __value)
     {
+#if !_GLIBCXX_USE_CXX11_ABI
       size_type __removed __attribute__((__unused__)) = 0;
+#endif
+      list __to_destroy(get_allocator());
       iterator __first = begin();
       iterator __last = end();
-      iterator __extra = __last;
       while (__first != __last)
 	{
 	  iterator __next = __first;
@@ -344,22 +346,20 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
 	      // _GLIBCXX_RESOLVE_LIB_DEFECTS
 	      // 526. Is it undefined if a function in the standard changes
 	      // in parameters?
-	      if (std::__addressof(*__first) != std::__addressof(__value))
-		{
-		  _M_erase(__first);
-		  _GLIBCXX20_ONLY( __removed++ );
-		}
-	      else
-		__extra = __first;
+	      __to_destroy.splice(__to_destroy.begin(), *this, __first);
+#if !_GLIBCXX_USE_CXX11_ABI
+	      _GLIBCXX20_ONLY( __removed++ );
+#endif
 	    }
+
 	  __first = __next;
 	}
-      if (__extra != __last)
-	{
-	  _M_erase(__extra);
-	  _GLIBCXX20_ONLY( __removed++ );
-	}
-      return _GLIBCXX20_ONLY( __removed );
+
+#if !_GLIBCXX_USE_CXX11_ABI
+	return _GLIBCXX20_ONLY( __removed );
+#else
+	return _GLIBCXX20_ONLY( __to_destroy.size() );
+#endif
     }
 
   template<typename _Tp, typename _Alloc>
@@ -371,20 +371,30 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
       iterator __last = end();
       if (__first == __last)
 	return _GLIBCXX20_ONLY( 0 );
+#if !_GLIBCXX_USE_CXX11_ABI
       size_type __removed __attribute__((__unused__)) = 0;
+#endif
+      list __to_destroy(get_allocator());
       iterator __next = __first;
       while (++__next != __last)
 	{
 	  if (*__first == *__next)
 	    {
-	      _M_erase(__next);
+	      __to_destroy.splice(__to_destroy.begin(), *this, __next);
+#if !_GLIBCXX_USE_CXX11_ABI
 	      _GLIBCXX20_ONLY( __removed++ );
+#endif
 	    }
 	  else
 	    __first = __next;
 	  __next = __first;
 	}
+
+#if !_GLIBCXX_USE_CXX11_ABI
       return _GLIBCXX20_ONLY( __removed );
+#else
+      return _GLIBCXX20_ONLY( __to_destroy.size() );
+#endif
     }
 
   template<typename _Tp, typename _Alloc>
@@ -533,21 +543,31 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
       list<_Tp, _Alloc>::
       remove_if(_Predicate __pred)
       {
+#if !_GLIBCXX_USE_CXX11_ABI
 	size_type __removed __attribute__((__unused__)) = 0;
-        iterator __first = begin();
-        iterator __last = end();
-        while (__first != __last)
+#endif
+	list __to_destroy(get_allocator());
+	iterator __first = begin();
+	iterator __last = end();
+	while (__first != __last)
 	  {
 	    iterator __next = __first;
 	    ++__next;
 	    if (__pred(*__first))
 	      {
-		_M_erase(__first);
+		__to_destroy.splice(__to_destroy.begin(), *this, __first);
+#if !_GLIBCXX_USE_CXX11_ABI
 		_GLIBCXX20_ONLY( __removed++ );
+#endif
 	      }
 	    __first = __next;
 	  }
+
+#if !_GLIBCXX_USE_CXX11_ABI
 	return _GLIBCXX20_ONLY( __removed );
+#else
+	return _GLIBCXX20_ONLY( __to_destroy.size() );
+#endif
       }
 
   template<typename _Tp, typename _Alloc>
@@ -560,20 +580,30 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
         iterator __last = end();
         if (__first == __last)
 	  return _GLIBCXX20_ONLY(0);
+#if !_GLIBCXX_USE_CXX11_ABI
         size_type __removed __attribute__((__unused__)) = 0;
+#endif
+	list __to_destroy(get_allocator());
         iterator __next = __first;
         while (++__next != __last)
 	  {
 	    if (__binary_pred(*__first, *__next))
 	      {
-		_M_erase(__next);
+		__to_destroy.splice(__to_destroy.begin(), *this, __next);
+#if !_GLIBCXX_USE_CXX11_ABI
 		_GLIBCXX20_ONLY( __removed++ );
+#endif
 	      }
 	    else
 	      __first = __next;
 	    __next = __first;
 	  }
+
+#if !_GLIBCXX_USE_CXX11_ABI
 	return _GLIBCXX20_ONLY( __removed );
+#else
+	return _GLIBCXX20_ONLY( __to_destroy.size() );
+#endif
       }
 
 #undef _GLIBCXX20_ONLY
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
diff --git a/libstdc++-v3/testsuite/23_containers/forward_list/operations/91620.cc b/libstdc++-v3/testsuite/23_containers/forward_list/operations/91620.cc
new file mode 100644
index 00000000000..a3127f6ee68
--- /dev/null
+++ b/libstdc++-v3/testsuite/23_containers/forward_list/operations/91620.cc
@@ -0,0 +1,88 @@
+// { dg-do run { target c++11 } }
+// { dg-options "-g -O0" }
+
+//
+// Copyright (C) 2020 Free Software Foundation, Inc.
+//
+// This file is part of the GNU ISO C++ Library.  This library is free
+// software; you can redistribute it and/or modify it under the
+// terms of the GNU General Public License as published by the
+// Free Software Foundation; either version 3, or (at your option)
+// any later version.
+//
+// This library is distributed in the hope that it will be useful,
+// but WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+// GNU General Public License for more details.
+//
+// You should have received a copy of the GNU General Public License along
+// with this library; see the file COPYING3.  If not see
+// <http://www.gnu.org/licenses/>.
+
+#include <forward_list>
+#include <memory>
+#include <testsuite_hooks.h>
+
+struct PredLWG526
+{
+  PredLWG526(int i) : i_(i) {};
+  ~PredLWG526() { i_ = -32767; }
+
+  bool
+  operator() (const PredLWG526& p) const { return p.i_ == i_; }
+
+  bool
+  operator==(int i) const { return i == i_; }
+
+  bool
+  operator() (const PredLWG526& lhs, const PredLWG526& rhs) const
+  {
+    VERIFY( i_ != -32767 );
+    return lhs.i_ == rhs.i_;
+  }
+
+  int i_;
+};
+
+void test01()
+{
+  int a1[] = {1, 2, 1, 3, 5, 8, 11};
+  int a2[] = {2, 3, 5, 8, 11};
+  std::forward_list<PredLWG526> fl(a1, a1 + 7);
+
+  VERIFY( std::distance(fl.begin(), fl.end()) == 7 );
+
+  fl.remove_if(std::cref(fl.front()));
+  VERIFY( std::distance(fl.begin(), fl.end()) == 5 );
+  for (size_t i = 0; !fl.empty(); ++i)
+    {
+      VERIFY( fl.front() == a2[i] );
+      fl.pop_front();
+    }
+}
+
+void test02()
+{
+  int a1[] = {1, 1, 1, 2, 3, 5, 8, 11};
+  int a2[] = {1, 2, 3, 5, 8, 11};
+  std::forward_list<PredLWG526> fl(a1, a1 + 8);
+
+  VERIFY( std::distance(fl.begin(), fl.end()) == 8 );
+
+  auto it = fl.begin();
+  ++it;
+  fl.unique(std::cref(*it));
+  VERIFY( std::distance(fl.begin(), fl.end()) == 6 );
+  for (size_t i = 0; !fl.empty(); ++i)
+    {
+      VERIFY( fl.front() == a2[i] );
+      fl.pop_front();
+    }
+}
+
+int main()
+{
+  test01();
+  test02();
+  return 0;
+}
diff --git a/libstdc++-v3/testsuite/23_containers/list/operations/91620.cc b/libstdc++-v3/testsuite/23_containers/list/operations/91620.cc
new file mode 100644
index 00000000000..64c0998082d
--- /dev/null
+++ b/libstdc++-v3/testsuite/23_containers/list/operations/91620.cc
@@ -0,0 +1,110 @@
+// { dg-do run { target c++11 } }
+// { dg-options "-g -O0" }
+
+//
+// Copyright (C) 2020 Free Software Foundation, Inc.
+//
+// This file is part of the GNU ISO C++ Library.  This library is free
+// software; you can redistribute it and/or modify it under the
+// terms of the GNU General Public License as published by the
+// Free Software Foundation; either version 3, or (at your option)
+// any later version.
+//
+// This library is distributed in the hope that it will be useful,
+// but WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+// GNU General Public License for more details.
+//
+// You should have received a copy of the GNU General Public License along
+// with this library; see the file COPYING3.  If not see
+// <http://www.gnu.org/licenses/>.
+
+#include <list>
+#include <memory>
+#include <testsuite_hooks.h>
+
+struct PredLWG526
+{
+  PredLWG526(int i) : i_(i) {};
+  ~PredLWG526() { i_ = -32767; }
+
+  bool
+  operator() (const PredLWG526& p) const { return p.i_ == i_; }
+
+  bool
+  operator==(int i) const { return i == i_; }
+
+  bool
+  operator()(const PredLWG526& lhs, const PredLWG526& rhs) const
+  {
+    VERIFY( i_ != -32767 );
+    return lhs.i_ == rhs.i_;
+  }
+
+  friend bool
+  operator==(const PredLWG526& lhs, const PredLWG526& rhs)
+  { return lhs.i_ == rhs.i_; }
+
+  int i_;
+};
+
+void test01()
+{
+  int a1[] = {1, 2, 1, 3, 5, 8, 11};
+  int a2[] = {2, 3, 5, 8, 11};
+  std::list<PredLWG526> l(a1, a1 + 7);
+
+  VERIFY( std::distance(l.begin(), l.end()) == 7 );
+
+  l.remove(l.front());
+  VERIFY( std::distance(l.begin(), l.end()) == 5 );
+  for (size_t i = 0; !l.empty(); ++i)
+    {
+      VERIFY( l.front() == a2[i] );
+      l.pop_front();
+    }
+}
+
+void test02()
+{
+  int a1[] = {1, 2, 1, 3, 5, 8, 11};
+  int a2[] = {2, 3, 5, 8, 11};
+  std::list<PredLWG526> l(a1, a1 + 7);
+
+  VERIFY( std::distance(l.begin(), l.end()) == 7 );
+
+  l.remove_if(std::cref(l.front()));
+  VERIFY( std::distance(l.begin(), l.end()) == 5 );
+  for (size_t i = 0; !l.empty(); ++i)
+    {
+      VERIFY( l.front() == a2[i] );
+      l.pop_front();
+    }
+}
+
+void test03()
+{
+  int a1[] = {1, 1, 1, 2, 3, 5, 8, 11};
+  int a2[] = {1, 2, 3, 5, 8, 11};
+  std::list<PredLWG526> l(a1, a1 + 8);
+
+  VERIFY( std::distance(l.begin(), l.end()) == 8 );
+
+  auto it = l.begin();
+  ++it;
+  l.unique(std::cref(*it));
+  VERIFY( std::distance(l.begin(), l.end()) == 6 );
+  for (size_t i = 0; !l.empty(); ++i)
+    {
+      VERIFY( l.front() == a2[i] );
+      l.pop_front();
+    }
+}
+
+int main()
+{
+  test01();
+  test02();
+  test03();
+  return 0;
+}

Re: [PATCH] PR libstdc++/91620 Implement DR 526 for std::[forward_]list::remove_if/unique

[Jonathan Wakely]

On 27/12/19 11:57 +0100, François Dumont wrote:
>Here is the patch to extend DR 526 to forward_list and list remove_if 
>and unique.
>
>As the adopted pattern is simpler I also applied it to the remove methods.
>
>    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.
>
>Tested under Linux x86_64 normal and debug modes.
>
>Ok to commit ?
>
>François
>


>diff --git a/libstdc++-v3/include/bits/forward_list.tcc b/libstdc++-v3/include/bits/forward_list.tcc
>index 088111e3330..70de7e75a43 100644
>--- a/libstdc++-v3/include/bits/forward_list.tcc
>+++ b/libstdc++-v3/include/bits/forward_list.tcc
>@@ -290,30 +290,19 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
>     remove(const _Tp& __val) -> __remove_return_type
>     {
>       size_type __removed __attribute__((__unused__)) = 0;
>-      _Node_base* __curr = &this->_M_impl._M_head;
>-      _Node_base* __extra = nullptr;
>+      forward_list __to_destroy(get_allocator());
> 
>-      while (_Node* __tmp = static_cast<_Node*>(__curr->_M_next))
>-	{
>+      auto __prev_it = cbefore_begin();
>+      while (_Node* __tmp = static_cast<_Node*>(__prev_it._M_node->_M_next))
> 	if (*__tmp->_M_valptr() == __val)
> 	  {
>-	      if (__tmp->_M_valptr() != std::__addressof(__val))
>-		{
>-		  this->_M_erase_after(__curr);
>+	    __to_destroy.splice_after(__to_destroy.cbefore_begin(),
>+				      *this, __prev_it);
> 	    _GLIBCXX20_ONLY( __removed++ );
>-		  continue;
> 	  }
> 	else
>-		__extra = __curr;
>-	    }
>-	  __curr = __curr->_M_next;
>-	}
>+	  ++__prev_it;
> 
>-      if (__extra)
>-	{
>-	  this->_M_erase_after(__extra);
>-	  _GLIBCXX20_ONLY( __removed++ );
>-	}
>       return _GLIBCXX20_ONLY( __removed );
>     }
> 
>@@ -324,17 +313,19 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
>       remove_if(_Pred __pred) -> __remove_return_type
>       {
> 	size_type __removed __attribute__((__unused__)) = 0;
>-	_Node_base* __curr = &this->_M_impl._M_head;
>-	while (_Node* __tmp = static_cast<_Node*>(__curr->_M_next))
>-	  {
>+	forward_list __to_destroy(get_allocator());
>+
>+	auto __prev_it = cbefore_begin();
>+	while (_Node* __tmp = static_cast<_Node*>(__prev_it._M_node->_M_next))
> 	  if (__pred(*__tmp->_M_valptr()))
> 	    {
>-		this->_M_erase_after(__curr);
>+	      __to_destroy.splice_after(__to_destroy.cbefore_begin(),
>+					*this, __prev_it);
> 	      _GLIBCXX20_ONLY( __removed++ );
> 	    }
> 	  else
>-	      __curr = __curr->_M_next;
>-	  }
>+	    ++__prev_it;
>+
> 	return _GLIBCXX20_ONLY( __removed );
>       }
> 
>@@ -348,19 +339,23 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
> 	iterator __last = end();
> 	if (__first == __last)
> 	  return _GLIBCXX20_ONLY(0);
>+
>+	forward_list __to_destroy(get_allocator());
> 	size_type __removed __attribute__((__unused__)) = 0;
> 	iterator __next = __first;
> 	while (++__next != __last)
> 	{
> 	  if (__binary_pred(*__first, *__next))
> 	    {
>-	      erase_after(__first);
>+	      __to_destroy.splice_after(__to_destroy.cbefore_begin(),
>+					*this, __first);
> 	      _GLIBCXX20_ONLY( __removed++ );
> 	    }
> 	  else
> 	    __first = __next;
> 	  __next = __first;
> 	}
>+
> 	return _GLIBCXX20_ONLY( __removed );
>       }
> 
>diff --git a/libstdc++-v3/include/bits/list.tcc b/libstdc++-v3/include/bits/list.tcc
>index 0ac6654b079..5a6fd5b0824 100644
>--- a/libstdc++-v3/include/bits/list.tcc
>+++ b/libstdc++-v3/include/bits/list.tcc
>@@ -331,10 +331,12 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
>     list<_Tp, _Alloc>::
>     remove(const value_type& __value)
>     {
>+#if !_GLIBCXX_USE_CXX11_ABI
>       size_type __removed __attribute__((__unused__)) = 0;
>+#endif
>+      list __to_destroy(get_allocator());
>       iterator __first = begin();
>       iterator __last = end();
>-      iterator __extra = __last;
>       while (__first != __last)
> 	{
> 	  iterator __next = __first;
>@@ -344,22 +346,20 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
> 	      // _GLIBCXX_RESOLVE_LIB_DEFECTS
> 	      // 526. Is it undefined if a function in the standard changes
> 	      // in parameters?
>-	      if (std::__addressof(*__first) != std::__addressof(__value))
>-		{
>-		  _M_erase(__first);
>+	      __to_destroy.splice(__to_destroy.begin(), *this, __first);
>+#if !_GLIBCXX_USE_CXX11_ABI
> 	      _GLIBCXX20_ONLY( __removed++ );
>+#endif

The point of the _GLIBCXX20_ONLY macro was to avoid cluttering this
function with #ifdef directives. If it's going to be full of #ifdef
now anyway, there's no real benefit to using _GLIBCXX20_ONLY.

This could now be:

#if __cplusplus > 201703L && ! _GLIBCXX_USE_CXX11_ABI
	      __removed++;
#endif

and so on.

> 	    }
>-	      else
>-		__extra = __first;
>-	    }
>+
> 	  __first = __next;
> 	}
>-      if (__extra != __last)
>-	{
>-	  _M_erase(__extra);
>-	  _GLIBCXX20_ONLY( __removed++ );
>-	}
>+
>+#if !_GLIBCXX_USE_CXX11_ABI
> 	return _GLIBCXX20_ONLY( __removed );
>+#else
>+	return _GLIBCXX20_ONLY( __to_destroy.size() );
>+#endif

Although this becomes pretty ugly:

#if __cplusplus > 201703L
# if _GLIBCXX_USE_CXX11_ABI
	return __to_destroy.size();
# else
	return __removed;
# endif
#endif

So maybe _GLIBCXX20_ONLY is still worthwhile.

The other alternative would be to define a new type right at the start
which keeps count if needed:

#if __cplusplus > 201703L && ! _GLIBCXX_USE_CXX11_ABI
   struct _VictimList : list
   {
     void splice(list::iterator __p, list& __x, list::iterator __i)
     {
       list::splice(__p, __x, __i);
       ++_M_size;
     }
     size_type size() const { return _M_size; }
     size_type _M_size = 0;
   } __to_destroy;
#else
   list __to_destroy;
#endif

   // ...

   return _GLIBCXX20_ONLY(__to_destroy.size());

With this the only conditional compilation is at the start of the
function and the one use of _GLIBCXX20_ONLY at the end. The rest of
the function body has no #if or macros at all.

Your patch is OK for master. We can revisit it later to tidy it up.

Thanks.

Re: [PATCH] PR libstdc++/91620 Implement DR 526 for std::[forward_]list::remove_if/unique

[Jonathan Wakely]

On 11/08/20 10:11 +0100, Jonathan Wakely wrote:
>On 27/12/19 11:57 +0100, François Dumont wrote:
>>Here is the patch to extend DR 526 to forward_list and list 
>>remove_if and unique.
>>
>>As the adopted pattern is simpler I also applied it to the remove methods.
>>
>>    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.
>>
>>Tested under Linux x86_64 normal and debug modes.
>>
>>Ok to commit ?
>>
>>François
>>
>
>
>>diff --git a/libstdc++-v3/include/bits/forward_list.tcc b/libstdc++-v3/include/bits/forward_list.tcc
>>index 088111e3330..70de7e75a43 100644
>>--- a/libstdc++-v3/include/bits/forward_list.tcc
>>+++ b/libstdc++-v3/include/bits/forward_list.tcc
>>@@ -290,30 +290,19 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
>>    remove(const _Tp& __val) -> __remove_return_type
>>    {
>>      size_type __removed __attribute__((__unused__)) = 0;
>>-      _Node_base* __curr = &this->_M_impl._M_head;
>>-      _Node_base* __extra = nullptr;
>>+      forward_list __to_destroy(get_allocator());
>>
>>-      while (_Node* __tmp = static_cast<_Node*>(__curr->_M_next))
>>-	{
>>+      auto __prev_it = cbefore_begin();
>>+      while (_Node* __tmp = static_cast<_Node*>(__prev_it._M_node->_M_next))
>>	if (*__tmp->_M_valptr() == __val)
>>	  {
>>-	      if (__tmp->_M_valptr() != std::__addressof(__val))
>>-		{
>>-		  this->_M_erase_after(__curr);
>>+	    __to_destroy.splice_after(__to_destroy.cbefore_begin(),
>>+				      *this, __prev_it);
>>	    _GLIBCXX20_ONLY( __removed++ );
>>-		  continue;
>>	  }
>>	else
>>-		__extra = __curr;
>>-	    }
>>-	  __curr = __curr->_M_next;
>>-	}
>>+	  ++__prev_it;
>>
>>-      if (__extra)
>>-	{
>>-	  this->_M_erase_after(__extra);
>>-	  _GLIBCXX20_ONLY( __removed++ );
>>-	}
>>      return _GLIBCXX20_ONLY( __removed );
>>    }
>>
>>@@ -324,17 +313,19 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
>>      remove_if(_Pred __pred) -> __remove_return_type
>>      {
>>	size_type __removed __attribute__((__unused__)) = 0;
>>-	_Node_base* __curr = &this->_M_impl._M_head;
>>-	while (_Node* __tmp = static_cast<_Node*>(__curr->_M_next))
>>-	  {
>>+	forward_list __to_destroy(get_allocator());
>>+
>>+	auto __prev_it = cbefore_begin();
>>+	while (_Node* __tmp = static_cast<_Node*>(__prev_it._M_node->_M_next))
>>	  if (__pred(*__tmp->_M_valptr()))
>>	    {
>>-		this->_M_erase_after(__curr);
>>+	      __to_destroy.splice_after(__to_destroy.cbefore_begin(),
>>+					*this, __prev_it);
>>	      _GLIBCXX20_ONLY( __removed++ );
>>	    }
>>	  else
>>-	      __curr = __curr->_M_next;
>>-	  }
>>+	    ++__prev_it;
>>+
>>	return _GLIBCXX20_ONLY( __removed );
>>      }
>>
>>@@ -348,19 +339,23 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
>>	iterator __last = end();
>>	if (__first == __last)
>>	  return _GLIBCXX20_ONLY(0);
>>+
>>+	forward_list __to_destroy(get_allocator());
>>	size_type __removed __attribute__((__unused__)) = 0;
>>	iterator __next = __first;
>>	while (++__next != __last)
>>	{
>>	  if (__binary_pred(*__first, *__next))
>>	    {
>>-	      erase_after(__first);
>>+	      __to_destroy.splice_after(__to_destroy.cbefore_begin(),
>>+					*this, __first);
>>	      _GLIBCXX20_ONLY( __removed++ );
>>	    }
>>	  else
>>	    __first = __next;
>>	  __next = __first;
>>	}
>>+
>>	return _GLIBCXX20_ONLY( __removed );
>>      }
>>
>>diff --git a/libstdc++-v3/include/bits/list.tcc b/libstdc++-v3/include/bits/list.tcc
>>index 0ac6654b079..5a6fd5b0824 100644
>>--- a/libstdc++-v3/include/bits/list.tcc
>>+++ b/libstdc++-v3/include/bits/list.tcc
>>@@ -331,10 +331,12 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
>>    list<_Tp, _Alloc>::
>>    remove(const value_type& __value)
>>    {
>>+#if !_GLIBCXX_USE_CXX11_ABI
>>      size_type __removed __attribute__((__unused__)) = 0;
>>+#endif
>>+      list __to_destroy(get_allocator());
>>      iterator __first = begin();
>>      iterator __last = end();
>>-      iterator __extra = __last;
>>      while (__first != __last)
>>	{
>>	  iterator __next = __first;
>>@@ -344,22 +346,20 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
>>	      // _GLIBCXX_RESOLVE_LIB_DEFECTS
>>	      // 526. Is it undefined if a function in the standard changes
>>	      // in parameters?
>>-	      if (std::__addressof(*__first) != std::__addressof(__value))
>>-		{
>>-		  _M_erase(__first);
>>+	      __to_destroy.splice(__to_destroy.begin(), *this, __first);
>>+#if !_GLIBCXX_USE_CXX11_ABI
>>	      _GLIBCXX20_ONLY( __removed++ );
>>+#endif
>
>The point of the _GLIBCXX20_ONLY macro was to avoid cluttering this
>function with #ifdef directives. If it's going to be full of #ifdef
>now anyway, there's no real benefit to using _GLIBCXX20_ONLY.
>
>This could now be:
>
>#if __cplusplus > 201703L && ! _GLIBCXX_USE_CXX11_ABI
>	      __removed++;
>#endif
>
>and so on.
>
>>	    }
>>-	      else
>>-		__extra = __first;
>>-	    }
>>+
>>	  __first = __next;
>>	}
>>-      if (__extra != __last)
>>-	{
>>-	  _M_erase(__extra);
>>-	  _GLIBCXX20_ONLY( __removed++ );
>>-	}
>>+
>>+#if !_GLIBCXX_USE_CXX11_ABI
>>	return _GLIBCXX20_ONLY( __removed );
>>+#else
>>+	return _GLIBCXX20_ONLY( __to_destroy.size() );
>>+#endif
>
>Although this becomes pretty ugly:
>
>#if __cplusplus > 201703L
># if _GLIBCXX_USE_CXX11_ABI
>	return __to_destroy.size();
># else
>	return __removed;
># endif
>#endif
>
>So maybe _GLIBCXX20_ONLY is still worthwhile.
>
>The other alternative would be to define a new type right at the start
>which keeps count if needed:
>
>#if __cplusplus > 201703L && ! _GLIBCXX_USE_CXX11_ABI
>  struct _VictimList : list
>  {
>    void splice(list::iterator __p, list& __x, list::iterator __i)
>    {
>      list::splice(__p, __x, __i);
>      ++_M_size;
>    }
>    size_type size() const { return _M_size; }
>    size_type _M_size = 0;
>  } __to_destroy;
>#else
>  list __to_destroy;
>#endif
>
>  // ...
>
>  return _GLIBCXX20_ONLY(__to_destroy.size());
>
>With this the only conditional compilation is at the start of the
>function and the one use of _GLIBCXX20_ONLY at the end. The rest of
>the function body has no #if or macros at all.
>
>Your patch is OK for master. We can revisit it later to tidy it up.

Oops, I meant to reply to the patch with tests of course, not the
original one. Please do commit the tests.