P0646R1 Improving the Return Value of Erase-Like Algorithms I

2018-08-21  François Dumont  <fdumont@gcc.gnu.org>

	P0646R1 Improving the Return Value of Erase-Like Algorithms I
	* include/debug/forward_list (forward_list::__remove_return_type):
	Define typedef as size_type or void, according to __cplusplus value.
	(_GLIBCXX_FWDLIST_REMOVE_RETURN_TYPE_TAG): Define macro as abi-tag or
	empty, according to __cplusplus value.
	(_GLIBCXX20_ONLY): Define macro.
	(forward_list::remove, forward_list::unique): Use typedef and macro
	to change return type and add abi-tag for C++2a. Return number of
	removed elements for C++2a.
	(forward_list::remove_if<Pred>, forward_list::unique<BinPred>): Use
	typedef to change return type for C++2a. Return number of removed
	elements for C++2a.
	* include/debug/list (list::__remove_return_type): Define typedef as
	size_type or void, according to __cplusplus value.
	(_GLIBCXX_LIST_REMOVE_RETURN_TYPE_TAG): Define macro as abi-tag or
	empty, according to __cplusplus value.
	(_GLIBCXX20_ONLY): Define macro.
	(list::remove, list::unique): Use typedef and macro to change return
	type and add abi-tag for C++2a. Return number of removed elements for
	C++2a.
	(list::remove_if<Predicate>, list::unique<BinaryPredicate>): Use typedef
	to change return type for C++2a. Return number of removed elements for
	C++2a.

From-SVN: r263752

3 files changed, 199 insertions, 61 deletions

diff --git a/libstdc++-v3/ChangeLog b/libstdc++-v3/ChangeLog
index 7437be1..a7d1166 100644
--- a/libstdc++-v3/ChangeLog
+++ b/libstdc++-v3/ChangeLog
@@ -1,3 +1,29 @@
+2018-08-21  François Dumont  <fdumont@gcc.gnu.org>
+
+	P0646R1 Improving the Return Value of Erase-Like Algorithms I
+	* include/debug/forward_list (forward_list::__remove_return_type):
+	Define typedef as size_type or void, according to __cplusplus value.
+	(_GLIBCXX_FWDLIST_REMOVE_RETURN_TYPE_TAG): Define macro as abi-tag or
+	empty, according to __cplusplus value.
+	(_GLIBCXX20_ONLY): Define macro.
+	(forward_list::remove, forward_list::unique): Use typedef and macro
+	to change return type and add abi-tag for C++2a. Return number of
+	removed elements for C++2a.
+	(forward_list::remove_if<Pred>, forward_list::unique<BinPred>): Use
+	typedef to change return type for C++2a. Return number of removed
+	elements for C++2a.
+	* include/debug/list (list::__remove_return_type): Define typedef as
+	size_type or void, according to __cplusplus value.
+	(_GLIBCXX_LIST_REMOVE_RETURN_TYPE_TAG): Define macro as abi-tag or
+	empty, according to __cplusplus value.
+	(_GLIBCXX20_ONLY): Define macro.
+	(list::remove, list::unique): Use typedef and macro to change return
+	type and add abi-tag for C++2a. Return number of removed elements for
+	C++2a.
+	(list::remove_if<Predicate>, list::unique<BinaryPredicate>): Use typedef
+	to change return type for C++2a. Return number of removed elements for
+	C++2a.
+
 2018-08-21  David Edelsohn  <dje.gcc@gmail.com>
 
 	* testsuite/18_support/new_nothrow.cc: XFAIL on AIX.
diff --git a/libstdc++-v3/include/debug/forward_list b/libstdc++-v3/include/debug/forward_list
index 633af1a..75d4f63 100644
--- a/libstdc++-v3/include/debug/forward_list
+++ b/libstdc++-v3/include/debug/forward_list
@@ -653,70 +653,113 @@ namespace __debug
 		   const_iterator __before, const_iterator __last)
       { splice_after(__pos, std::move(__list), __before, __last); }
 
-      void
+    private:
+#if __cplusplus > 201703L
+      using __remove_return_type = size_type;
+# define _GLIBCXX_FWDLIST_REMOVE_RETURN_TYPE_TAG \
+      __attribute__((__abi_tag__("__cxx20")))
+# define _GLIBCXX20_ONLY(__expr) __expr
+#else
+      using __remove_return_type = void;
+# define _GLIBCXX_FWDLIST_REMOVE_RETURN_TYPE_TAG
+# define _GLIBCXX20_ONLY(__expr)
+#endif
+
+    public:
+      _GLIBCXX_FWDLIST_REMOVE_RETURN_TYPE_TAG
+      __remove_return_type
       remove(const _Tp& __val)
       {
+	if (!this->_M_iterators && !this->_M_const_iterators)
+	  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())
 	  {
 	    if (*__x == __val)
-	      __x = _M_erase_after(__old);
-	    else
-	      __old = __x++;
+	      {
+		if (std::__addressof(*__x) != std::__addressof(__val))
+		  {
+		    __x = _M_erase_after(__old);
+		    _GLIBCXX20_ONLY( __removed++ );
+		    continue;
+		  }
+		else
+		  __extra = __old;
+	      }
+	    __old = __x++;
 	  }
+
+	if (__extra != _Base::end())
+	  {
+	    this->_M_erase_after(__extra);
+	    _GLIBCXX20_ONLY( __removed++ );
+	  }
+
+	return _GLIBCXX20_ONLY( __removed );
       }
 
       template<typename _Pred>
-	void
+	__remove_return_type
 	remove_if(_Pred __pred)
 	{
+	  if (!this->_M_iterators && !this->_M_const_iterators)
+	    return _Base::remove_if(__pred);
+
+	  size_type __removed __attribute__((__unused__)) = 0;
 	  _Base_iterator __x = _Base::before_begin();
 	  _Base_iterator __old = __x++;
 	  while (__x != _Base::end())
-	    {
-	      if (__pred(*__x))
+	    if (__pred(*__x))
+	      {
 		__x = _M_erase_after(__old);
-	      else
-		__old = __x++;
-	    }
+		_GLIBCXX20_ONLY( __removed++ );
+	      }
+	    else
+	      __old = __x++;
+
+	  return _GLIBCXX20_ONLY( __removed );
 	}
 
-      void
+      _GLIBCXX_FWDLIST_REMOVE_RETURN_TYPE_TAG
+      __remove_return_type
       unique()
-      {
-	_Base_iterator __first = _Base::begin();
-	_Base_iterator __last = _Base::end();
-	if (__first == __last)
-	  return;
-	_Base_iterator __next = std::next(__first);
-	while (__next != __last)
-	  {
-	    if (*__first == *__next)
-	      __next = _M_erase_after(__first);
-	    else
-	      __first = __next++;
-	  }
-      }
+      { return unique(std::equal_to<_Tp>()); }
 
       template<typename _BinPred>
-	void
+	__remove_return_type
 	unique(_BinPred __binary_pred)
 	{
+	  if (!this->_M_iterators && !this->_M_const_iterators)
+	    return _Base::unique(__binary_pred);
+
 	  _Base_iterator __first = _Base::begin();
 	  _Base_iterator __last = _Base::end();
 	  if (__first == __last)
-	    return;
+	    return _GLIBCXX20_ONLY(0);
+
+	  size_type __removed __attribute__((__unused__)) = 0;
 	  _Base_iterator __next = std::next(__first);
 	  while (__next != __last)
 	    {
 	      if (__binary_pred(*__first, *__next))
-		__next = _M_erase_after(__first);
+		{
+		  __next = _M_erase_after(__first);
+		  _GLIBCXX20_ONLY( __removed++ );
+		}
 	      else
 		__first = __next++;
 	    }
+
+	  return _GLIBCXX20_ONLY( __removed );
 	}
 
+#undef _GLIBCXX_FWDLIST_REMOVE_RETURN_TYPE_TAG
+#undef _GLIBCXX20_ONLY
+
       void
       merge(forward_list&& __list)
       {
diff --git a/libstdc++-v3/include/debug/list b/libstdc++-v3/include/debug/list
index e37ebf1..80fa304 100644
--- a/libstdc++-v3/include/debug/list
+++ b/libstdc++-v3/include/debug/list
@@ -641,66 +641,135 @@ namespace __debug
       { splice(__position, std::move(__x), __first, __last); }
 #endif
 
-      void
+    private:
+#if __cplusplus > 201703L
+      typedef size_type __remove_return_type;
+# define _GLIBCXX_LIST_REMOVE_RETURN_TYPE_TAG \
+      __attribute__((__abi_tag__("__cxx20")))
+# define _GLIBCXX20_ONLY(__expr) __expr
+#else
+      typedef void __remove_return_type;
+# define _GLIBCXX_LIST_REMOVE_RETURN_TYPE_TAG
+# define _GLIBCXX20_ONLY(__expr)
+#endif
+
+    public:
+      _GLIBCXX_LIST_REMOVE_RETURN_TYPE_TAG
+      __remove_return_type
       remove(const _Tp& __value)
       {
-	for (_Base_iterator __x = _Base::begin(); __x != _Base::end(); )
+	if (!this->_M_iterators && !this->_M_const_iterators)
+	  return _Base::remove(__value);
+
+	size_type __removed __attribute__((__unused__)) = 0;
+	_Base_iterator __first = _Base::begin();
+	_Base_iterator __last = _Base::end();
+	_Base_iterator __extra = __last;
+	while (__first != __last)
 	  {
-	    if (*__x == __value)
-	      __x = _M_erase(__x);
+	    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
-	      ++__x;
+	      ++__first;
 	  }
+
+	if (__extra != __last)
+	  {
+	    _M_erase(__extra);
+	    _GLIBCXX20_ONLY( __removed++ );
+	  }
+	return _GLIBCXX20_ONLY( __removed );
       }
 
       template<class _Predicate>
-	void
+	__remove_return_type
 	remove_if(_Predicate __pred)
 	{
+	  if (!this->_M_iterators && !this->_M_const_iterators)
+	    return _Base::remove_if(__pred);
+
+	  size_type __removed __attribute__((__unused__)) = 0;
 	  for (_Base_iterator __x = _Base::begin(); __x != _Base::end(); )
-	    {
-	      if (__pred(*__x))
+	    if (__pred(*__x))
+	      {
 		__x = _M_erase(__x);
-	      else
-		++__x;
-	    }
+		_GLIBCXX20_ONLY( __removed++ );
+	      }
+	    else
+	      ++__x;
+
+	  return _GLIBCXX20_ONLY( __removed );
 	}
 
-      void
+      _GLIBCXX_LIST_REMOVE_RETURN_TYPE_TAG
+      __remove_return_type
       unique()
       {
+	if (!this->_M_iterators && !this->_M_const_iterators)
+	  return _Base::unique();
+
+	if (empty())
+	  return _GLIBCXX20_ONLY(0);
+
+        size_type __removed __attribute__((__unused__)) = 0;
 	_Base_iterator __first = _Base::begin();
 	_Base_iterator __last = _Base::end();
-	if (__first == __last)
-	  return;
-	_Base_iterator __next = __first; ++__next;
-	while (__next != __last)
-	  {
-	    if (*__first == *__next)
-	      __next = _M_erase(__next);
-	    else
-	      __first = __next++;
-	  }
+	_Base_iterator __next = __first;
+	while (++__next != __last)
+	  if (*__first == *__next)
+	    {
+	      _M_erase(__next);
+	      __next = __first;
+	      _GLIBCXX20_ONLY( __removed++ );
+	    }
+	  else
+	    __first = __next;
+
+	return _GLIBCXX20_ONLY( __removed );
       }
 
       template<class _BinaryPredicate>
-	void
+	__remove_return_type
 	unique(_BinaryPredicate __binary_pred)
 	{
+	  if (!this->_M_iterators && !this->_M_const_iterators)
+	    return _Base::unique(__binary_pred);
+
+	  if (empty())
+	    return _GLIBCXX20_ONLY(0);
+
+	  size_type __removed __attribute__((__unused__)) = 0;
 	  _Base_iterator __first = _Base::begin();
 	  _Base_iterator __last = _Base::end();
-	  if (__first == __last)
-	    return;
-	  _Base_iterator __next = __first; ++__next;
-	  while (__next != __last)
-	    {
-	      if (__binary_pred(*__first, *__next))
-		__next = _M_erase(__next);
-	      else
-		__first = __next++;
-	    }
+	  _Base_iterator __next = __first;;
+	  while (++__next != __last)
+	    if (__binary_pred(*__first, *__next))
+	      {
+		_M_erase(__next);
+		__next = __first;
+		_GLIBCXX20_ONLY( __removed++ );
+	      }
+	    else
+	      __first = __next;
+
+	  return _GLIBCXX20_ONLY( __removed );
 	}
 
+#undef _GLIBCXX_LIST_REMOVE_RETURN_TYPE_TAG
+#undef _GLIBCXX20_ONLY
+
       void
 #if __cplusplus >= 201103L
       merge(list&& __x)