X-Git-Url: http://git.ipfire.org/?a=blobdiff_plain;f=libstdc%2B%2B-v3%2Finclude%2Fbits%2Fstl_algo.h;h=3d37091a9b4bc4c719316a903750fca43e93eaf9;hb=83ffe9cde7fe0b4deb0d1b54175fd9b19c38179c;hp=753ebb7a09c6bc7c30d4bf3a2cdd0a2e637a0ef4;hpb=85ec4feb11167c9e4489361bf2399a20afbe52c8;p=thirdparty%2Fgcc.git

diff --git a/libstdc++-v3/include/bits/stl_algo.h b/libstdc++-v3/include/bits/stl_algo.h
index 753ebb7a09c6..3d37091a9b4b 100644
--- a/libstdc++-v3/include/bits/stl_algo.h
+++ b/libstdc++-v3/include/bits/stl_algo.h
@@ -1,6 +1,6 @@
 // Algorithm implementation -*- C++ -*-
 
-// Copyright (C) 2001-2018 Free Software Foundation, Inc.
+// Copyright (C) 2001-2023 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
@@ -56,16 +56,22 @@
 #ifndef _STL_ALGO_H
 #define _STL_ALGO_H 1
 
-#include <cstdlib>	     // for rand
 #include <bits/algorithmfwd.h>
+#include <bits/stl_algobase.h>
 #include <bits/stl_heap.h>
-#include <bits/stl_tempbuf.h>  // for _Temporary_buffer
 #include <bits/predefined_ops.h>
 
 #if __cplusplus >= 201103L
 #include <bits/uniform_int_dist.h>
 #endif
 
+#if _GLIBCXX_HOSTED
+# include <bits/stl_tempbuf.h>  // for _Temporary_buffer
+# if (__cplusplus <= 201103L || _GLIBCXX_USE_DEPRECATED)
+#  include <cstdlib>	     // for rand
+# endif
+#endif
+
 // See concept_check.h for the __glibcxx_*_requires macros.
 
 namespace std _GLIBCXX_VISIBILITY(default)
@@ -74,6 +80,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 
   /// Swaps the median value of *__a, *__b and *__c under __comp to *__result
   template<typename _Iterator, typename _Compare>
+    _GLIBCXX20_CONSTEXPR
     void
     __move_median_to_first(_Iterator __result,_Iterator __a, _Iterator __b,
 			   _Iterator __c, _Compare __comp)
@@ -95,75 +102,9 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	std::iter_swap(__result, __b);
     }
 
-  /// This is an overload used by find algos for the Input Iterator case.
-  template<typename _InputIterator, typename _Predicate>
-    inline _InputIterator
-    __find_if(_InputIterator __first, _InputIterator __last,
-	      _Predicate __pred, input_iterator_tag)
-    {
-      while (__first != __last && !__pred(__first))
-	++__first;
-      return __first;
-    }
-
-  /// This is an overload used by find algos for the RAI case.
-  template<typename _RandomAccessIterator, typename _Predicate>
-    _RandomAccessIterator
-    __find_if(_RandomAccessIterator __first, _RandomAccessIterator __last,
-	      _Predicate __pred, random_access_iterator_tag)
-    {
-      typename iterator_traits<_RandomAccessIterator>::difference_type
-	__trip_count = (__last - __first) >> 2;
-
-      for (; __trip_count > 0; --__trip_count)
-	{
-	  if (__pred(__first))
-	    return __first;
-	  ++__first;
-
-	  if (__pred(__first))
-	    return __first;
-	  ++__first;
-
-	  if (__pred(__first))
-	    return __first;
-	  ++__first;
-
-	  if (__pred(__first))
-	    return __first;
-	  ++__first;
-	}
-
-      switch (__last - __first)
-	{
-	case 3:
-	  if (__pred(__first))
-	    return __first;
-	  ++__first;
-	case 2:
-	  if (__pred(__first))
-	    return __first;
-	  ++__first;
-	case 1:
-	  if (__pred(__first))
-	    return __first;
-	  ++__first;
-	case 0:
-	default:
-	  return __last;
-	}
-    }
-
-  template<typename _Iterator, typename _Predicate>
-    inline _Iterator
-    __find_if(_Iterator __first, _Iterator __last, _Predicate __pred)
-    {
-      return __find_if(__first, __last, __pred,
-		       std::__iterator_category(__first));
-    }
-
   /// Provided for stable_partition to use.
   template<typename _InputIterator, typename _Predicate>
+    _GLIBCXX20_CONSTEXPR
     inline _InputIterator
     __find_if_not(_InputIterator __first, _InputIterator __last,
 		  _Predicate __pred)
@@ -177,6 +118,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
   /// remaining range length instead of comparing against an end
   /// iterator.
   template<typename _InputIterator, typename _Predicate, typename _Distance>
+    _GLIBCXX20_CONSTEXPR
     _InputIterator
     __find_if_not_n(_InputIterator __first, _Distance& __len, _Predicate __pred)
     {
@@ -201,6 +143,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 
   template<typename _ForwardIterator1, typename _ForwardIterator2,
 	   typename _BinaryPredicate>
+    _GLIBCXX20_CONSTEXPR
     _ForwardIterator1
     __search(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
 	     _ForwardIterator2 __first2, _ForwardIterator2 __last2,
@@ -217,7 +160,6 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 		__gnu_cxx::__ops::__iter_comp_iter(__predicate, __first2));
 
       // General case.
-      _ForwardIterator2 __p;
       _ForwardIterator1 __current = __first1;
 
       for (;;)
@@ -229,7 +171,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	  if (__first1 == __last1)
 	    return __last1;
 
-	  __p = __p1;
+	  _ForwardIterator2 __p = __p1;
 	  __current = __first1;
 	  if (++__current == __last1)
 	    return __last1;
@@ -253,6 +195,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
   */
   template<typename _ForwardIterator, typename _Integer,
 	   typename _UnaryPredicate>
+    _GLIBCXX20_CONSTEXPR
     _ForwardIterator
     __search_n_aux(_ForwardIterator __first, _ForwardIterator __last,
 		   _Integer __count, _UnaryPredicate __unary_pred,
@@ -285,6 +228,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
   */
   template<typename _RandomAccessIter, typename _Integer,
 	   typename _UnaryPredicate>
+    _GLIBCXX20_CONSTEXPR
     _RandomAccessIter
     __search_n_aux(_RandomAccessIter __first, _RandomAccessIter __last,
 		   _Integer __count, _UnaryPredicate __unary_pred,
@@ -315,6 +259,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 
   template<typename _ForwardIterator, typename _Integer,
 	   typename _UnaryPredicate>
+    _GLIBCXX20_CONSTEXPR
     _ForwardIterator
     __search_n(_ForwardIterator __first, _ForwardIterator __last,
 	       _Integer __count,
@@ -333,6 +278,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
   // find_end for forward iterators.
   template<typename _ForwardIterator1, typename _ForwardIterator2,
 	   typename _BinaryPredicate>
+    _GLIBCXX20_CONSTEXPR
     _ForwardIterator1
     __find_end(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
 	       _ForwardIterator2 __first2, _ForwardIterator2 __last2,
@@ -361,6 +307,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
   // find_end for bidirectional iterators (much faster).
   template<typename _BidirectionalIterator1, typename _BidirectionalIterator2,
 	   typename _BinaryPredicate>
+    _GLIBCXX20_CONSTEXPR
     _BidirectionalIterator1
     __find_end(_BidirectionalIterator1 __first1,
 	       _BidirectionalIterator1 __last1,
@@ -421,6 +368,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
    *  [__first1,__last1-(__last2-__first2))
   */
   template<typename _ForwardIterator1, typename _ForwardIterator2>
+    _GLIBCXX20_CONSTEXPR
     inline _ForwardIterator1
     find_end(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
 	     _ForwardIterator2 __first2, _ForwardIterator2 __last2)
@@ -470,6 +418,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
   */
   template<typename _ForwardIterator1, typename _ForwardIterator2,
 	   typename _BinaryPredicate>
+    _GLIBCXX20_CONSTEXPR
     inline _ForwardIterator1
     find_end(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
 	     _ForwardIterator2 __first2, _ForwardIterator2 __last2,
@@ -504,6 +453,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
    *  @p [__first,__last), and false otherwise.
   */
   template<typename _InputIterator, typename _Predicate>
+    _GLIBCXX20_CONSTEXPR
     inline bool
     all_of(_InputIterator __first, _InputIterator __last, _Predicate __pred)
     { return __last == std::find_if_not(__first, __last, __pred); }
@@ -521,12 +471,13 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
    *  @p [__first,__last), and false otherwise.
   */
   template<typename _InputIterator, typename _Predicate>
+    _GLIBCXX20_CONSTEXPR
     inline bool
     none_of(_InputIterator __first, _InputIterator __last, _Predicate __pred)
     { return __last == _GLIBCXX_STD_A::find_if(__first, __last, __pred); }
 
   /**
-   *  @brief  Checks that a predicate is false for at least an element
+   *  @brief  Checks that a predicate is true for at least one element
    *          of a sequence.
    *  @ingroup non_mutating_algorithms
    *  @param  __first   An input iterator.
@@ -539,6 +490,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
    *  otherwise.
   */
   template<typename _InputIterator, typename _Predicate>
+    _GLIBCXX20_CONSTEXPR
     inline bool
     any_of(_InputIterator __first, _InputIterator __last, _Predicate __pred)
     { return !std::none_of(__first, __last, __pred); }
@@ -554,6 +506,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
    *  such that @p __pred(*i) is false, or @p __last if no such iterator exists.
   */
   template<typename _InputIterator, typename _Predicate>
+    _GLIBCXX20_CONSTEXPR
     inline _InputIterator
     find_if_not(_InputIterator __first, _InputIterator __last,
 		_Predicate __pred)
@@ -578,6 +531,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
    *  do not.
   */
   template<typename _InputIterator, typename _Predicate>
+    _GLIBCXX20_CONSTEXPR
     inline bool
     is_partitioned(_InputIterator __first, _InputIterator __last,
 		   _Predicate __pred)
@@ -599,6 +553,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
    *           and @p none_of(mid, __last, __pred) are both true.
   */
   template<typename _ForwardIterator, typename _Predicate>
+    _GLIBCXX20_CONSTEXPR
     _ForwardIterator
     partition_point(_ForwardIterator __first, _ForwardIterator __last,
 		    _Predicate __pred)
@@ -615,13 +570,11 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	_DistanceType;
 
       _DistanceType __len = std::distance(__first, __last);
-      _DistanceType __half;
-      _ForwardIterator __middle;
 
       while (__len > 0)
 	{
-	  __half = __len >> 1;
-	  __middle = __first;
+	  _DistanceType __half = __len >> 1;
+	  _ForwardIterator __middle = __first;
 	  std::advance(__middle, __half);
 	  if (__pred(*__middle))
 	    {
@@ -638,6 +591,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 
   template<typename _InputIterator, typename _OutputIterator,
 	   typename _Predicate>
+    _GLIBCXX20_CONSTEXPR
     _OutputIterator
     __remove_copy_if(_InputIterator __first, _InputIterator __last,
 		     _OutputIterator __result, _Predicate __pred)
@@ -666,6 +620,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
    *  are copied is unchanged.
   */
   template<typename _InputIterator, typename _OutputIterator, typename _Tp>
+    _GLIBCXX20_CONSTEXPR
     inline _OutputIterator
     remove_copy(_InputIterator __first, _InputIterator __last,
 		_OutputIterator __result, const _Tp& __value)
@@ -699,6 +654,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
   */
   template<typename _InputIterator, typename _OutputIterator,
 	   typename _Predicate>
+    _GLIBCXX20_CONSTEXPR
     inline _OutputIterator
     remove_copy_if(_InputIterator __first, _InputIterator __last,
 		   _OutputIterator __result, _Predicate __pred)
@@ -733,6 +689,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
   */
   template<typename _InputIterator, typename _OutputIterator,
 	   typename _Predicate>
+    _GLIBCXX20_CONSTEXPR
     _OutputIterator
     copy_if(_InputIterator __first, _InputIterator __last,
 	    _OutputIterator __result, _Predicate __pred)
@@ -755,27 +712,19 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
     }
 
   template<typename _InputIterator, typename _Size, typename _OutputIterator>
+    _GLIBCXX20_CONSTEXPR
     _OutputIterator
     __copy_n(_InputIterator __first, _Size __n,
 	     _OutputIterator __result, input_iterator_tag)
     {
-      if (__n > 0)
-	{
-	  while (true)
-	    {
-	      *__result = *__first;
-	      ++__result;
-	      if (--__n > 0)
-		++__first;
-	      else
-		break;
-	    }
-	}
-      return __result;
+      return std::__niter_wrap(__result,
+			       __copy_n_a(__first, __n,
+					  std::__niter_base(__result), true));
     }
 
   template<typename _RandomAccessIterator, typename _Size,
 	   typename _OutputIterator>
+    _GLIBCXX20_CONSTEXPR
     inline _OutputIterator
     __copy_n(_RandomAccessIterator __first, _Size __n,
 	     _OutputIterator __result, random_access_iterator_tag)
@@ -795,6 +744,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
    *  optimizations such as unrolling).
   */
   template<typename _InputIterator, typename _Size, typename _OutputIterator>
+    _GLIBCXX20_CONSTEXPR
     inline _OutputIterator
     copy_n(_InputIterator __first, _Size __n, _OutputIterator __result)
     {
@@ -803,7 +753,14 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
 	    typename iterator_traits<_InputIterator>::value_type>)
 
-      return std::__copy_n(__first, __n, __result,
+      const auto __n2 = std::__size_to_integer(__n);
+      if (__n2 <= 0)
+	return __result;
+
+      __glibcxx_requires_can_increment(__first, __n2);
+      __glibcxx_requires_can_increment(__result, __n2);
+
+      return std::__copy_n(__first, __n2, __result,
 			   std::__iterator_category(__first));
     }
 
@@ -824,6 +781,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
   */
   template<typename _InputIterator, typename _OutputIterator1,
 	   typename _OutputIterator2, typename _Predicate>
+    _GLIBCXX20_CONSTEXPR
     pair<_OutputIterator1, _OutputIterator2>
     partition_copy(_InputIterator __first, _InputIterator __last,
 		   _OutputIterator1 __out_true, _OutputIterator2 __out_false,
@@ -853,26 +811,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 
       return pair<_OutputIterator1, _OutputIterator2>(__out_true, __out_false);
     }
-#endif
-
-  template<typename _ForwardIterator, typename _Predicate>
-    _ForwardIterator
-    __remove_if(_ForwardIterator __first, _ForwardIterator __last,
-		_Predicate __pred)
-    {
-      __first = std::__find_if(__first, __last, __pred);
-      if (__first == __last)
-	return __first;
-      _ForwardIterator __result = __first;
-      ++__first;
-      for (; __first != __last; ++__first)
-	if (!__pred(__first))
-	  {
-	    *__result = _GLIBCXX_MOVE(*__first);
-	    ++__result;
-	  }
-      return __result;
-    }
+#endif // C++11
 
   /**
    *  @brief Remove elements from a sequence.
@@ -892,6 +831,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
    *  are still present, but their value is unspecified.
   */
   template<typename _ForwardIterator, typename _Tp>
+    _GLIBCXX20_CONSTEXPR
     inline _ForwardIterator
     remove(_ForwardIterator __first, _ForwardIterator __last,
 	   const _Tp& __value)
@@ -925,6 +865,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
    *  are still present, but their value is unspecified.
   */
   template<typename _ForwardIterator, typename _Predicate>
+    _GLIBCXX20_CONSTEXPR
     inline _ForwardIterator
     remove_if(_ForwardIterator __first, _ForwardIterator __last,
 	      _Predicate __pred)
@@ -941,6 +882,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
     }
 
   template<typename _ForwardIterator, typename _BinaryPredicate>
+    _GLIBCXX20_CONSTEXPR
     _ForwardIterator
     __adjacent_find(_ForwardIterator __first, _ForwardIterator __last,
 		    _BinaryPredicate __binary_pred)
@@ -958,6 +900,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
     }
 
   template<typename _ForwardIterator, typename _BinaryPredicate>
+    _GLIBCXX20_CONSTEXPR
     _ForwardIterator
     __unique(_ForwardIterator __first, _ForwardIterator __last,
 	     _BinaryPredicate __binary_pred)
@@ -991,6 +934,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
    *  are still present, but their value is unspecified.
   */
   template<typename _ForwardIterator>
+    _GLIBCXX20_CONSTEXPR
     inline _ForwardIterator
     unique(_ForwardIterator __first, _ForwardIterator __last)
     {
@@ -1021,6 +965,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
    *  are still present, but their value is unspecified.
   */
   template<typename _ForwardIterator, typename _BinaryPredicate>
+    _GLIBCXX20_CONSTEXPR
     inline _ForwardIterator
     unique(_ForwardIterator __first, _ForwardIterator __last,
 	   _BinaryPredicate __binary_pred)
@@ -1045,6 +990,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
   */
   template<typename _ForwardIterator, typename _OutputIterator,
 	   typename _BinaryPredicate>
+    _GLIBCXX20_CONSTEXPR
     _OutputIterator
     __unique_copy(_ForwardIterator __first, _ForwardIterator __last,
 		  _OutputIterator __result, _BinaryPredicate __binary_pred,
@@ -1074,6 +1020,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
   */
   template<typename _InputIterator, typename _OutputIterator,
 	   typename _BinaryPredicate>
+    _GLIBCXX20_CONSTEXPR
     _OutputIterator
     __unique_copy(_InputIterator __first, _InputIterator __last,
 		  _OutputIterator __result, _BinaryPredicate __binary_pred,
@@ -1106,6 +1053,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
   */
   template<typename _InputIterator, typename _ForwardIterator,
 	   typename _BinaryPredicate>
+    _GLIBCXX20_CONSTEXPR
     _ForwardIterator
     __unique_copy(_InputIterator __first, _InputIterator __last,
 		  _ForwardIterator __result, _BinaryPredicate __binary_pred,
@@ -1128,6 +1076,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
    *  overloaded for bidirectional iterators.
   */
   template<typename _BidirectionalIterator>
+    _GLIBCXX20_CONSTEXPR
     void
     __reverse(_BidirectionalIterator __first, _BidirectionalIterator __last,
 	      bidirectional_iterator_tag)
@@ -1148,6 +1097,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
    *  overloaded for random access iterators.
   */
   template<typename _RandomAccessIterator>
+    _GLIBCXX20_CONSTEXPR
     void
     __reverse(_RandomAccessIterator __first, _RandomAccessIterator __last,
 	      random_access_iterator_tag)
@@ -1176,6 +1126,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
    *  swaps @p *(__first+i) and @p *(__last-(i+1))
   */
   template<typename _BidirectionalIterator>
+    _GLIBCXX20_CONSTEXPR
     inline void
     reverse(_BidirectionalIterator __first, _BidirectionalIterator __last)
     {
@@ -1203,6 +1154,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
    *  [__result,__result+(__last-__first)) must not overlap.
   */
   template<typename _BidirectionalIterator, typename _OutputIterator>
+    _GLIBCXX20_CONSTEXPR
     _OutputIterator
     reverse_copy(_BidirectionalIterator __first, _BidirectionalIterator __last,
 		 _OutputIterator __result)
@@ -1228,6 +1180,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
    *  It returns the greatest common divisor of two integer values.
   */
   template<typename _EuclideanRingElement>
+    _GLIBCXX20_CONSTEXPR
     _EuclideanRingElement
     __gcd(_EuclideanRingElement __m, _EuclideanRingElement __n)
     {
@@ -1240,11 +1193,11 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
       return __m;
     }
 
-  inline namespace _V2
-  {
+_GLIBCXX_BEGIN_INLINE_ABI_NAMESPACE(_V2)
 
   /// This is a helper function for the rotate algorithm.
   template<typename _ForwardIterator>
+    _GLIBCXX20_CONSTEXPR
     _ForwardIterator
     __rotate(_ForwardIterator __first,
 	     _ForwardIterator __middle,
@@ -1253,7 +1206,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
     {
       if (__first == __middle)
 	return __last;
-      else if (__last  == __middle)
+      else if (__last == __middle)
 	return __first;
 
       _ForwardIterator __first2 = __middle;
@@ -1286,6 +1239,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 
    /// This is a helper function for the rotate algorithm.
   template<typename _BidirectionalIterator>
+    _GLIBCXX20_CONSTEXPR
     _BidirectionalIterator
     __rotate(_BidirectionalIterator __first,
 	     _BidirectionalIterator __middle,
@@ -1298,7 +1252,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 
       if (__first == __middle)
 	return __last;
-      else if (__last  == __middle)
+      else if (__last == __middle)
 	return __first;
 
       std::__reverse(__first,  __middle, bidirectional_iterator_tag());
@@ -1324,6 +1278,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 
   /// This is a helper function for the rotate algorithm.
   template<typename _RandomAccessIterator>
+    _GLIBCXX20_CONSTEXPR
     _RandomAccessIterator
     __rotate(_RandomAccessIterator __first,
 	     _RandomAccessIterator __middle,
@@ -1336,7 +1291,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 
       if (__first == __middle)
 	return __last;
-      else if (__last  == __middle)
+      else if (__last == __middle)
 	return __first;
 
       typedef typename iterator_traits<_RandomAccessIterator>::difference_type
@@ -1430,6 +1385,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
    *  for each @p n in the range @p [0,__last-__first).
   */
   template<typename _ForwardIterator>
+    _GLIBCXX20_CONSTEXPR
     inline _ForwardIterator
     rotate(_ForwardIterator __first, _ForwardIterator __middle,
 	   _ForwardIterator __last)
@@ -1444,7 +1400,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 			   std::__iterator_category(__first));
     }
 
-  } // namespace _V2
+_GLIBCXX_END_INLINE_ABI_NAMESPACE(_V2)
 
   /**
    *  @brief Copy a sequence, rotating its elements.
@@ -1467,6 +1423,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
    *  for each @p n in the range @p [0,__last-__first).
   */
   template<typename _ForwardIterator, typename _OutputIterator>
+    _GLIBCXX20_CONSTEXPR
     inline _OutputIterator
     rotate_copy(_ForwardIterator __first, _ForwardIterator __middle,
 		_ForwardIterator __last, _OutputIterator __result)
@@ -1484,6 +1441,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 
   /// This is a helper function...
   template<typename _ForwardIterator, typename _Predicate>
+    _GLIBCXX20_CONSTEXPR
     _ForwardIterator
     __partition(_ForwardIterator __first, _ForwardIterator __last,
 		_Predicate __pred, forward_iterator_tag)
@@ -1509,6 +1467,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 
   /// This is a helper function...
   template<typename _BidirectionalIterator, typename _Predicate>
+    _GLIBCXX20_CONSTEXPR
     _BidirectionalIterator
     __partition(_BidirectionalIterator __first, _BidirectionalIterator __last,
 		_Predicate __pred, bidirectional_iterator_tag)
@@ -1535,6 +1494,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	}
     }
 
+#if _GLIBCXX_HOSTED
   // partition
 
   /// This is a helper function...
@@ -1601,9 +1561,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 					   __right_len,
 					   __buffer, __buffer_size);
 
-      std::rotate(__left_split, __middle, __right_split);
-      std::advance(__left_split, std::distance(__middle, __right_split));
-      return __left_split;
+      return std::rotate(__left_split, __middle, __right_split);
     }
 
   template<typename _ForwardIterator, typename _Predicate>
@@ -1621,7 +1579,8 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
       typedef typename iterator_traits<_ForwardIterator>::difference_type
 	_DistanceType;
 
-      _Temporary_buffer<_ForwardIterator, _ValueType> __buf(__first, __last);
+      _Temporary_buffer<_ForwardIterator, _ValueType>
+	__buf(__first, std::distance(__first, __last));
       return
 	std::__stable_partition_adaptive(__first, __last, __pred,
 					 _DistanceType(__buf.requested_size()),
@@ -1661,9 +1620,13 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
       return std::__stable_partition(__first, __last,
 				     __gnu_cxx::__ops::__pred_iter(__pred));
     }
+#endif // HOSTED
+
+  /// @cond undocumented
 
   /// This is a helper function for the sort routines.
   template<typename _RandomAccessIterator, typename _Compare>
+    _GLIBCXX20_CONSTEXPR
     void
     __heap_select(_RandomAccessIterator __first,
 		  _RandomAccessIterator __middle,
@@ -1679,6 +1642,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 
   template<typename _InputIterator, typename _RandomAccessIterator,
 	   typename _Compare>
+    _GLIBCXX20_CONSTEXPR
     _RandomAccessIterator
     __partial_sort_copy(_InputIterator __first, _InputIterator __last,
 			_RandomAccessIterator __result_first,
@@ -1714,6 +1678,8 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
       return __result_real_last;
     }
 
+  /// @endcond
+
   /**
    *  @brief Copy the smallest elements of a sequence.
    *  @ingroup sorting_algorithms
@@ -1723,16 +1689,17 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
    *  @param  __result_last    Another random-access iterator.
    *  @return   An iterator indicating the end of the resulting sequence.
    *
-   *  Copies and sorts the smallest N values from the range @p [__first,__last)
-   *  to the range beginning at @p __result_first, where the number of
-   *  elements to be copied, @p N, is the smaller of @p (__last-__first) and
-   *  @p (__result_last-__result_first).
-   *  After the sort if @e i and @e j are iterators in the range
-   *  @p [__result_first,__result_first+N) such that i precedes j then
-   *  *j<*i is false.
-   *  The value returned is @p __result_first+N.
+   *  Copies and sorts the smallest `N` values from the range
+   *  `[__first, __last)` to the range beginning at `__result_first`, where
+   *  the number of elements to be copied, `N`, is the smaller of
+   *  `(__last - __first)` and `(__result_last - __result_first)`.
+   *  After the sort if `i` and `j` are iterators in the range
+   *  `[__result_first,__result_first + N)` such that `i` precedes `j` then
+   *  `*j < *i` is false.
+   *  The value returned is `__result_first + N`.
   */
   template<typename _InputIterator, typename _RandomAccessIterator>
+    _GLIBCXX20_CONSTEXPR
     inline _RandomAccessIterator
     partial_sort_copy(_InputIterator __first, _InputIterator __last,
 		      _RandomAccessIterator __result_first,
@@ -1772,17 +1739,18 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
    *  @param  __comp    A comparison functor.
    *  @return   An iterator indicating the end of the resulting sequence.
    *
-   *  Copies and sorts the smallest N values from the range @p [__first,__last)
-   *  to the range beginning at @p result_first, where the number of
-   *  elements to be copied, @p N, is the smaller of @p (__last-__first) and
-   *  @p (__result_last-__result_first).
-   *  After the sort if @e i and @e j are iterators in the range
-   *  @p [__result_first,__result_first+N) such that i precedes j then
-   *  @p __comp(*j,*i) is false.
-   *  The value returned is @p __result_first+N.
+   *  Copies and sorts the smallest `N` values from the range
+   *  `[__first, __last)` to the range beginning at `result_first`, where
+   *  the number of elements to be copied, `N`, is the smaller of
+   *  `(__last - __first)` and `(__result_last - __result_first)`.
+   *  After the sort if `i` and `j` are iterators in the range
+   *  `[__result_first, __result_first + N)` such that `i` precedes `j` then
+   *  `__comp(*j, *i)` is false.
+   *  The value returned is `__result_first + N`.
   */
   template<typename _InputIterator, typename _RandomAccessIterator,
 	   typename _Compare>
+    _GLIBCXX20_CONSTEXPR
     inline _RandomAccessIterator
     partial_sort_copy(_InputIterator __first, _InputIterator __last,
 		      _RandomAccessIterator __result_first,
@@ -1815,8 +1783,11 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 				__gnu_cxx::__ops::__iter_comp_iter(__comp));
     }
 
+  /// @cond undocumented
+
   /// This is a helper function for the sort routine.
   template<typename _RandomAccessIterator, typename _Compare>
+    _GLIBCXX20_CONSTEXPR
     void
     __unguarded_linear_insert(_RandomAccessIterator __last,
 			      _Compare __comp)
@@ -1836,6 +1807,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 
   /// This is a helper function for the sort routine.
   template<typename _RandomAccessIterator, typename _Compare>
+    _GLIBCXX20_CONSTEXPR
     void
     __insertion_sort(_RandomAccessIterator __first,
 		     _RandomAccessIterator __last, _Compare __comp)
@@ -1859,6 +1831,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 
   /// This is a helper function for the sort routine.
   template<typename _RandomAccessIterator, typename _Compare>
+    _GLIBCXX20_CONSTEXPR
     inline void
     __unguarded_insertion_sort(_RandomAccessIterator __first,
 			       _RandomAccessIterator __last, _Compare __comp)
@@ -1876,6 +1849,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 
   /// This is a helper function for the sort routine.
   template<typename _RandomAccessIterator, typename _Compare>
+    _GLIBCXX20_CONSTEXPR
     void
     __final_insertion_sort(_RandomAccessIterator __first,
 			   _RandomAccessIterator __last, _Compare __comp)
@@ -1892,6 +1866,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 
   /// This is a helper function...
   template<typename _RandomAccessIterator, typename _Compare>
+    _GLIBCXX20_CONSTEXPR
     _RandomAccessIterator
     __unguarded_partition(_RandomAccessIterator __first,
 			  _RandomAccessIterator __last,
@@ -1913,6 +1888,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 
   /// This is a helper function...
   template<typename _RandomAccessIterator, typename _Compare>
+    _GLIBCXX20_CONSTEXPR
     inline _RandomAccessIterator
     __unguarded_partition_pivot(_RandomAccessIterator __first,
 				_RandomAccessIterator __last, _Compare __comp)
@@ -1924,6 +1900,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
     }
 
   template<typename _RandomAccessIterator, typename _Compare>
+    _GLIBCXX20_CONSTEXPR
     inline void
     __partial_sort(_RandomAccessIterator __first,
 		   _RandomAccessIterator __middle,
@@ -1936,6 +1913,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 
   /// This is a helper function for the sort routine.
   template<typename _RandomAccessIterator, typename _Size, typename _Compare>
+    _GLIBCXX20_CONSTEXPR
     void
     __introsort_loop(_RandomAccessIterator __first,
 		     _RandomAccessIterator __last,
@@ -1959,6 +1937,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
   // sort
 
   template<typename _RandomAccessIterator, typename _Compare>
+    _GLIBCXX20_CONSTEXPR
     inline void
     __sort(_RandomAccessIterator __first, _RandomAccessIterator __last,
 	   _Compare __comp)
@@ -1973,6 +1952,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
     }
 
   template<typename _RandomAccessIterator, typename _Size, typename _Compare>
+    _GLIBCXX20_CONSTEXPR
     void
     __introselect(_RandomAccessIterator __first, _RandomAccessIterator __nth,
 		  _RandomAccessIterator __last, _Size __depth_limit,
@@ -1998,27 +1978,29 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
       std::__insertion_sort(__first, __last, __comp);
     }
 
+  /// @endcond
+
   // nth_element
 
   // lower_bound moved to stl_algobase.h
 
   /**
-   *  @brief Finds the first position in which @p __val could be inserted
+   *  @brief Finds the first position in which `__val` could be inserted
    *         without changing the ordering.
    *  @ingroup binary_search_algorithms
-   *  @param  __first   An iterator.
-   *  @param  __last    Another iterator.
+   *  @param  __first   An iterator to the start of a sorted range.
+   *  @param  __last    A past-the-end iterator for the sorted range.
    *  @param  __val     The search term.
    *  @param  __comp    A functor to use for comparisons.
-   *  @return An iterator pointing to the first element <em>not less
-   *           than</em> @p __val, or end() if every element is less
-   *           than @p __val.
+   *  @return An iterator pointing to the first element _not less than_
+   *           `__val`, or `end()` if every element is less than `__val`.
    *  @ingroup binary_search_algorithms
    *
    *  The comparison function should have the same effects on ordering as
    *  the function used for the initial sort.
   */
   template<typename _ForwardIterator, typename _Tp, typename _Compare>
+    _GLIBCXX20_CONSTEXPR
     inline _ForwardIterator
     lower_bound(_ForwardIterator __first, _ForwardIterator __last,
 		const _Tp& __val, _Compare __comp)
@@ -2035,6 +2017,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
     }
 
   template<typename _ForwardIterator, typename _Tp, typename _Compare>
+    _GLIBCXX20_CONSTEXPR
     _ForwardIterator
     __upper_bound(_ForwardIterator __first, _ForwardIterator __last,
 		  const _Tp& __val, _Compare __comp)
@@ -2073,6 +2056,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
    *  @ingroup binary_search_algorithms
   */
   template<typename _ForwardIterator, typename _Tp>
+    _GLIBCXX20_CONSTEXPR
     inline _ForwardIterator
     upper_bound(_ForwardIterator __first, _ForwardIterator __last,
 		const _Tp& __val)
@@ -2103,6 +2087,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
    *  the function used for the initial sort.
   */
   template<typename _ForwardIterator, typename _Tp, typename _Compare>
+    _GLIBCXX20_CONSTEXPR
     inline _ForwardIterator
     upper_bound(_ForwardIterator __first, _ForwardIterator __last,
 		const _Tp& __val, _Compare __comp)
@@ -2120,6 +2105,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 
   template<typename _ForwardIterator, typename _Tp,
 	   typename _CompareItTp, typename _CompareTpIt>
+    _GLIBCXX20_CONSTEXPR
     pair<_ForwardIterator, _ForwardIterator>
     __equal_range(_ForwardIterator __first, _ForwardIterator __last,
 		  const _Tp& __val,
@@ -2174,6 +2160,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
    *  but does not actually call those functions.
   */
   template<typename _ForwardIterator, typename _Tp>
+    _GLIBCXX20_CONSTEXPR
     inline pair<_ForwardIterator, _ForwardIterator>
     equal_range(_ForwardIterator __first, _ForwardIterator __last,
 		const _Tp& __val)
@@ -2210,6 +2197,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
    *  but does not actually call those functions.
   */
   template<typename _ForwardIterator, typename _Tp, typename _Compare>
+    _GLIBCXX20_CONSTEXPR
     inline pair<_ForwardIterator, _ForwardIterator>
     equal_range(_ForwardIterator __first, _ForwardIterator __last,
 		const _Tp& __val, _Compare __comp)
@@ -2243,6 +2231,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
    *  that, use std::find or a container's specialized find member functions.
   */
   template<typename _ForwardIterator, typename _Tp>
+    _GLIBCXX20_CONSTEXPR
     bool
     binary_search(_ForwardIterator __first, _ForwardIterator __last,
 		  const _Tp& __val)
@@ -2276,6 +2265,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
    *  the function used for the initial sort.
   */
   template<typename _ForwardIterator, typename _Tp, typename _Compare>
+    _GLIBCXX20_CONSTEXPR
     bool
     binary_search(_ForwardIterator __first, _ForwardIterator __last,
 		  const _Tp& __val, _Compare __comp)
@@ -2401,36 +2391,46 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	    return __last;
 	}
       else
-	{
-	  std::rotate(__first, __middle, __last);
-	  std::advance(__first, std::distance(__middle, __last));
-	  return __first;
-	}
+	return std::rotate(__first, __middle, __last);
     }
 
   /// This is a helper function for the merge routines.
-  template<typename _BidirectionalIterator, typename _Distance, 
+  template<typename _BidirectionalIterator, typename _Distance,
 	   typename _Pointer, typename _Compare>
     void
     __merge_adaptive(_BidirectionalIterator __first,
 		     _BidirectionalIterator __middle,
 		     _BidirectionalIterator __last,
 		     _Distance __len1, _Distance __len2,
-		     _Pointer __buffer, _Distance __buffer_size,
-		     _Compare __comp)
+		     _Pointer __buffer, _Compare __comp)
     {
-      if (__len1 <= __len2 && __len1 <= __buffer_size)
+      if (__len1 <= __len2)
 	{
 	  _Pointer __buffer_end = _GLIBCXX_MOVE3(__first, __middle, __buffer);
 	  std::__move_merge_adaptive(__buffer, __buffer_end, __middle, __last,
 				     __first, __comp);
 	}
-      else if (__len2 <= __buffer_size)
+      else
 	{
 	  _Pointer __buffer_end = _GLIBCXX_MOVE3(__middle, __last, __buffer);
 	  std::__move_merge_adaptive_backward(__first, __middle, __buffer,
 					      __buffer_end, __last, __comp);
 	}
+    }
+
+  template<typename _BidirectionalIterator, typename _Distance,
+	   typename _Pointer, typename _Compare>
+    void
+    __merge_adaptive_resize(_BidirectionalIterator __first,
+			    _BidirectionalIterator __middle,
+			    _BidirectionalIterator __last,
+			    _Distance __len1, _Distance __len2,
+			    _Pointer __buffer, _Distance __buffer_size,
+			    _Compare __comp)
+    {
+      if (__len1 <= __buffer_size || __len2 <= __buffer_size)
+	std::__merge_adaptive(__first, __middle, __last,
+			      __len1, __len2, __buffer, __comp);
       else
 	{
 	  _BidirectionalIterator __first_cut = __first;
@@ -2458,14 +2458,15 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 
 	  _BidirectionalIterator __new_middle
 	    = std::__rotate_adaptive(__first_cut, __middle, __second_cut,
-				     __len1 - __len11, __len22, __buffer,
-				     __buffer_size);
-	  std::__merge_adaptive(__first, __first_cut, __new_middle, __len11,
-				__len22, __buffer, __buffer_size, __comp);
-	  std::__merge_adaptive(__new_middle, __second_cut, __last,
-				__len1 - __len11,
-				__len2 - __len22, __buffer,
-				__buffer_size, __comp);
+				     _Distance(__len1 - __len11), __len22,
+				     __buffer, __buffer_size);
+	  std::__merge_adaptive_resize(__first, __first_cut, __new_middle,
+				       __len11, __len22,
+				       __buffer, __buffer_size, __comp);
+	  std::__merge_adaptive_resize(__new_middle, __second_cut, __last,
+				       _Distance(__len1 - __len11),
+				       _Distance(__len2 - __len22),
+				       __buffer, __buffer_size, __comp);
 	}
     }
 
@@ -2512,9 +2513,8 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	  __len11 = std::distance(__first, __first_cut);
 	}
 
-      std::rotate(__first_cut, __middle, __second_cut);
-      _BidirectionalIterator __new_middle = __first_cut;
-      std::advance(__new_middle, std::distance(__middle, __second_cut));
+      _BidirectionalIterator __new_middle
+	= std::rotate(__first_cut, __middle, __second_cut);
       std::__merge_without_buffer(__first, __first_cut, __new_middle,
 				  __len11, __len22, __comp);
       std::__merge_without_buffer(__new_middle, __second_cut, __last,
@@ -2539,16 +2539,26 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
       const _DistanceType __len1 = std::distance(__first, __middle);
       const _DistanceType __len2 = std::distance(__middle, __last);
 
+#if _GLIBCXX_HOSTED
       typedef _Temporary_buffer<_BidirectionalIterator, _ValueType> _TmpBuf;
-      _TmpBuf __buf(__first, __last);
+      // __merge_adaptive will use a buffer for the smaller of
+      // [first,middle) and [middle,last).
+      _TmpBuf __buf(__first, std::min(__len1, __len2));
 
-      if (__buf.begin() == 0)
+      if (__builtin_expect(__buf.size() == __buf.requested_size(), true))
+	std::__merge_adaptive
+	  (__first, __middle, __last, __len1, __len2, __buf.begin(), __comp);
+      else if (__builtin_expect(__buf.begin() == 0, false))
 	std::__merge_without_buffer
 	  (__first, __middle, __last, __len1, __len2, __comp);
       else
-	std::__merge_adaptive
+	std::__merge_adaptive_resize
 	  (__first, __middle, __last, __len1, __len2, __buf.begin(),
 	   _DistanceType(__buf.size()), __comp);
+#else
+      std::__merge_without_buffer
+	(__first, __middle, __last, __len1, __len2, __comp);
+#endif
     }
 
   /**
@@ -2685,6 +2695,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 
   template<typename _RandomAccessIterator, typename _Distance,
 	   typename _Compare>
+    _GLIBCXX20_CONSTEXPR
     void
     __chunk_insertion_sort(_RandomAccessIterator __first,
 			   _RandomAccessIterator __last,
@@ -2726,33 +2737,46 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	}
     }
 
-  template<typename _RandomAccessIterator, typename _Pointer,
-	   typename _Distance, typename _Compare>
+  template<typename _RandomAccessIterator, typename _Pointer, typename _Compare>
     void
     __stable_sort_adaptive(_RandomAccessIterator __first,
+			   _RandomAccessIterator __middle,
 			   _RandomAccessIterator __last,
-			   _Pointer __buffer, _Distance __buffer_size,
-			   _Compare __comp)
+			   _Pointer __buffer, _Compare __comp)
+    {
+      std::__merge_sort_with_buffer(__first, __middle, __buffer, __comp);
+      std::__merge_sort_with_buffer(__middle, __last, __buffer, __comp);
+
+      std::__merge_adaptive(__first, __middle, __last,
+			    __middle - __first, __last - __middle,
+			    __buffer, __comp);
+    }
+
+  template<typename _RandomAccessIterator, typename _Pointer,
+	   typename _Distance, typename _Compare>
+    void
+    __stable_sort_adaptive_resize(_RandomAccessIterator __first,
+				  _RandomAccessIterator __last,
+				  _Pointer __buffer, _Distance __buffer_size,
+				  _Compare __comp)
     {
       const _Distance __len = (__last - __first + 1) / 2;
       const _RandomAccessIterator __middle = __first + __len;
       if (__len > __buffer_size)
 	{
-	  std::__stable_sort_adaptive(__first, __middle, __buffer,
-				      __buffer_size, __comp);
-	  std::__stable_sort_adaptive(__middle, __last, __buffer,
-				      __buffer_size, __comp);
+	  std::__stable_sort_adaptive_resize(__first, __middle, __buffer,
+					     __buffer_size, __comp);
+	  std::__stable_sort_adaptive_resize(__middle, __last, __buffer,
+					     __buffer_size, __comp);
+	  std::__merge_adaptive_resize(__first, __middle, __last,
+				       _Distance(__middle - __first),
+				       _Distance(__last - __middle),
+				       __buffer, __buffer_size,
+				       __comp);
 	}
       else
-	{
-	  std::__merge_sort_with_buffer(__first, __middle, __buffer, __comp);
-	  std::__merge_sort_with_buffer(__middle, __last, __buffer, __comp);
-	}
-      std::__merge_adaptive(__first, __middle, __last,
-			    _Distance(__middle - __first),
-			    _Distance(__last - __middle),
-			    __buffer, __buffer_size,
-			    __comp);
+	std::__stable_sort_adaptive(__first, __middle, __last,
+				    __buffer, __comp);
     }
 
   /// This is a helper function for the stable sorting routines.
@@ -2784,21 +2808,20 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 
   template<typename _InputIterator1, typename _InputIterator2,
 	   typename _Compare>
+    _GLIBCXX20_CONSTEXPR
     bool
     __includes(_InputIterator1 __first1, _InputIterator1 __last1,
 	       _InputIterator2 __first2, _InputIterator2 __last2,
 	       _Compare __comp)
     {
       while (__first1 != __last1 && __first2 != __last2)
-	if (__comp(__first2, __first1))
-	  return false;
-	else if (__comp(__first1, __first2))
-	  ++__first1;
-	else
-	  {
-	    ++__first1;
+	{
+	  if (__comp(__first2, __first1))
+	    return false;
+	  if (!__comp(__first1, __first2))
 	    ++__first2;
-	  }
+	  ++__first1;
+	}
 
       return __first2 == __last2;
     }
@@ -2822,6 +2845,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
    *  returned.
   */
   template<typename _InputIterator1, typename _InputIterator2>
+    _GLIBCXX20_CONSTEXPR
     inline bool
     includes(_InputIterator1 __first1, _InputIterator1 __last1,
 	     _InputIterator2 __first2, _InputIterator2 __last2)
@@ -2867,6 +2891,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
   */
   template<typename _InputIterator1, typename _InputIterator2,
 	   typename _Compare>
+    _GLIBCXX20_CONSTEXPR
     inline bool
     includes(_InputIterator1 __first1, _InputIterator1 __last1,
 	     _InputIterator2 __first2, _InputIterator2 __last2,
@@ -2901,6 +2926,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
   // max_element
 
   template<typename _BidirectionalIterator, typename _Compare>
+    _GLIBCXX20_CONSTEXPR
     bool
     __next_permutation(_BidirectionalIterator __first,
 		       _BidirectionalIterator __last, _Compare __comp)
@@ -2950,6 +2976,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
    *  is the largest of the set, the smallest is generated and false returned.
   */
   template<typename _BidirectionalIterator>
+    _GLIBCXX20_CONSTEXPR
     inline bool
     next_permutation(_BidirectionalIterator __first,
 		     _BidirectionalIterator __last)
@@ -2982,6 +3009,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
    *  smallest is generated and false returned.
   */
   template<typename _BidirectionalIterator, typename _Compare>
+    _GLIBCXX20_CONSTEXPR
     inline bool
     next_permutation(_BidirectionalIterator __first,
 		     _BidirectionalIterator __last, _Compare __comp)
@@ -3000,6 +3028,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
     }
 
   template<typename _BidirectionalIterator, typename _Compare>
+    _GLIBCXX20_CONSTEXPR
     bool
     __prev_permutation(_BidirectionalIterator __first,
 		       _BidirectionalIterator __last, _Compare __comp)
@@ -3050,6 +3079,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
    *  returned.
   */
   template<typename _BidirectionalIterator>
+    _GLIBCXX20_CONSTEXPR
     inline bool
     prev_permutation(_BidirectionalIterator __first,
 		     _BidirectionalIterator __last)
@@ -3082,6 +3112,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
    *  the largest is generated and false returned.
   */
   template<typename _BidirectionalIterator, typename _Compare>
+    _GLIBCXX20_CONSTEXPR
     inline bool
     prev_permutation(_BidirectionalIterator __first,
 		     _BidirectionalIterator __last, _Compare __comp)
@@ -3104,6 +3135,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 
   template<typename _InputIterator, typename _OutputIterator,
 	   typename _Predicate, typename _Tp>
+    _GLIBCXX20_CONSTEXPR
     _OutputIterator
     __replace_copy_if(_InputIterator __first, _InputIterator __last,
 		      _OutputIterator __result,
@@ -3132,6 +3164,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
    *  equal to @p __old_value with @p __new_value.
   */
   template<typename _InputIterator, typename _OutputIterator, typename _Tp>
+    _GLIBCXX20_CONSTEXPR
     inline _OutputIterator
     replace_copy(_InputIterator __first, _InputIterator __last,
 		 _OutputIterator __result,
@@ -3167,6 +3200,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
   */
   template<typename _InputIterator, typename _OutputIterator,
 	   typename _Predicate, typename _Tp>
+    _GLIBCXX20_CONSTEXPR
     inline _OutputIterator
     replace_copy_if(_InputIterator __first, _InputIterator __last,
 		    _OutputIterator __result,
@@ -3185,17 +3219,6 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 					      __new_value);
     }
 
-  template<typename _InputIterator, typename _Predicate>
-    typename iterator_traits<_InputIterator>::difference_type
-    __count_if(_InputIterator __first, _InputIterator __last, _Predicate __pred)
-    {
-      typename iterator_traits<_InputIterator>::difference_type __n = 0;
-      for (; __first != __last; ++__first)
-	if (__pred(__first))
-	  ++__n;
-      return __n;
-    }
-
 #if __cplusplus >= 201103L
   /**
    *  @brief  Determines whether the elements of a sequence are sorted.
@@ -3205,6 +3228,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
    *  @return  True if the elements are sorted, false otherwise.
   */
   template<typename _ForwardIterator>
+    _GLIBCXX20_CONSTEXPR
     inline bool
     is_sorted(_ForwardIterator __first, _ForwardIterator __last)
     { return std::is_sorted_until(__first, __last) == __last; }
@@ -3219,12 +3243,14 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
    *  @return  True if the elements are sorted, false otherwise.
   */
   template<typename _ForwardIterator, typename _Compare>
+    _GLIBCXX20_CONSTEXPR
     inline bool
     is_sorted(_ForwardIterator __first, _ForwardIterator __last,
 	      _Compare __comp)
     { return std::is_sorted_until(__first, __last, __comp) == __last; }
 
   template<typename _ForwardIterator, typename _Compare>
+    _GLIBCXX20_CONSTEXPR
     _ForwardIterator
     __is_sorted_until(_ForwardIterator __first, _ForwardIterator __last,
 		      _Compare __comp)
@@ -3248,6 +3274,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
    *           for which the range [__first, i) is sorted.
   */
   template<typename _ForwardIterator>
+    _GLIBCXX20_CONSTEXPR
     inline _ForwardIterator
     is_sorted_until(_ForwardIterator __first, _ForwardIterator __last)
     {
@@ -3272,6 +3299,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
    *           for which the range [__first, i) is sorted.
   */
   template<typename _ForwardIterator, typename _Compare>
+    _GLIBCXX20_CONSTEXPR
     inline _ForwardIterator
     is_sorted_until(_ForwardIterator __first, _ForwardIterator __last,
 		    _Compare __comp)
@@ -3443,38 +3471,15 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 				   __gnu_cxx::__ops::__iter_comp_iter(__comp));
     }
 
-  // N2722 + DR 915.
-  template<typename _Tp>
-    _GLIBCXX14_CONSTEXPR
-    inline _Tp
-    min(initializer_list<_Tp> __l)
-    { return *std::min_element(__l.begin(), __l.end()); }
-
-  template<typename _Tp, typename _Compare>
-    _GLIBCXX14_CONSTEXPR
-    inline _Tp
-    min(initializer_list<_Tp> __l, _Compare __comp)
-    { return *std::min_element(__l.begin(), __l.end(), __comp); }
-
-  template<typename _Tp>
-    _GLIBCXX14_CONSTEXPR
-    inline _Tp
-    max(initializer_list<_Tp> __l)
-    { return *std::max_element(__l.begin(), __l.end()); }
-
-  template<typename _Tp, typename _Compare>
-    _GLIBCXX14_CONSTEXPR
-    inline _Tp
-    max(initializer_list<_Tp> __l, _Compare __comp)
-    { return *std::max_element(__l.begin(), __l.end(), __comp); }
-
   template<typename _Tp>
     _GLIBCXX14_CONSTEXPR
     inline pair<_Tp, _Tp>
     minmax(initializer_list<_Tp> __l)
     {
+      __glibcxx_requires_irreflexive(__l.begin(), __l.end());
       pair<const _Tp*, const _Tp*> __p =
-	std::minmax_element(__l.begin(), __l.end());
+	std::__minmax_element(__l.begin(), __l.end(),
+			      __gnu_cxx::__ops::__iter_less_iter());
       return std::make_pair(*__p.first, *__p.second);
     }
 
@@ -3483,77 +3488,13 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
     inline pair<_Tp, _Tp>
     minmax(initializer_list<_Tp> __l, _Compare __comp)
     {
+      __glibcxx_requires_irreflexive_pred(__l.begin(), __l.end(), __comp);
       pair<const _Tp*, const _Tp*> __p =
-	std::minmax_element(__l.begin(), __l.end(), __comp);
+	std::__minmax_element(__l.begin(), __l.end(),
+			      __gnu_cxx::__ops::__iter_comp_iter(__comp));
       return std::make_pair(*__p.first, *__p.second);
     }
 
-  template<typename _ForwardIterator1, typename _ForwardIterator2,
-	   typename _BinaryPredicate>
-    bool
-    __is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
-		     _ForwardIterator2 __first2, _BinaryPredicate __pred)
-    {
-      // Efficiently compare identical prefixes:  O(N) if sequences
-      // have the same elements in the same order.
-      for (; __first1 != __last1; ++__first1, (void)++__first2)
-	if (!__pred(__first1, __first2))
-	  break;
-
-      if (__first1 == __last1)
-	return true;
-
-      // Establish __last2 assuming equal ranges by iterating over the
-      // rest of the list.
-      _ForwardIterator2 __last2 = __first2;
-      std::advance(__last2, std::distance(__first1, __last1));
-      for (_ForwardIterator1 __scan = __first1; __scan != __last1; ++__scan)
-	{
-	  if (__scan != std::__find_if(__first1, __scan,
-			  __gnu_cxx::__ops::__iter_comp_iter(__pred, __scan)))
-	    continue; // We've seen this one before.
-	  
-	  auto __matches
-	    = std::__count_if(__first2, __last2,
-			__gnu_cxx::__ops::__iter_comp_iter(__pred, __scan));
-	  if (0 == __matches ||
-	      std::__count_if(__scan, __last1,
-			__gnu_cxx::__ops::__iter_comp_iter(__pred, __scan))
-	      != __matches)
-	    return false;
-	}
-      return true;
-    }
-
-  /**
-   *  @brief  Checks whether a permutation of the second sequence is equal
-   *          to the first sequence.
-   *  @ingroup non_mutating_algorithms
-   *  @param  __first1  Start of first range.
-   *  @param  __last1   End of first range.
-   *  @param  __first2  Start of second range.
-   *  @return true if there exists a permutation of the elements in the range
-   *          [__first2, __first2 + (__last1 - __first1)), beginning with 
-   *          ForwardIterator2 begin, such that equal(__first1, __last1, begin)
-   *          returns true; otherwise, returns false.
-  */
-  template<typename _ForwardIterator1, typename _ForwardIterator2>
-    inline bool
-    is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
-		   _ForwardIterator2 __first2)
-    {
-      // concept requirements
-      __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator1>)
-      __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator2>)
-      __glibcxx_function_requires(_EqualOpConcept<
-		typename iterator_traits<_ForwardIterator1>::value_type,
-		typename iterator_traits<_ForwardIterator2>::value_type>)
-      __glibcxx_requires_valid_range(__first1, __last1);
-
-      return std::__is_permutation(__first1, __last1, __first2,
-				   __gnu_cxx::__ops::__iter_equal_to_iter());
-    }
-
   /**
    *  @brief  Checks whether a permutation of the second sequence is equal
    *          to the first sequence.
@@ -3570,6 +3511,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
   */
   template<typename _ForwardIterator1, typename _ForwardIterator2,
 	   typename _BinaryPredicate>
+    _GLIBCXX20_CONSTEXPR
     inline bool
     is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
 		   _ForwardIterator2 __first2, _BinaryPredicate __pred)
@@ -3589,6 +3531,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 #if __cplusplus > 201103L
   template<typename _ForwardIterator1, typename _ForwardIterator2,
 	   typename _BinaryPredicate>
+    _GLIBCXX20_CONSTEXPR
     bool
     __is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
 		     _ForwardIterator2 __first2, _ForwardIterator2 __last2,
@@ -3662,6 +3605,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
    *          otherwise, returns false.
   */
   template<typename _ForwardIterator1, typename _ForwardIterator2>
+    _GLIBCXX20_CONSTEXPR
     inline bool
     is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
 		   _ForwardIterator2 __first2, _ForwardIterator2 __last2)
@@ -3690,6 +3634,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
   */
   template<typename _ForwardIterator1, typename _ForwardIterator2,
 	   typename _BinaryPredicate>
+    _GLIBCXX20_CONSTEXPR
     inline bool
     is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
 		   _ForwardIterator2 __first2, _ForwardIterator2 __last2,
@@ -3702,9 +3647,9 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 				   __gnu_cxx::__ops::__iter_comp_iter(__pred));
     }
 
-#if __cplusplus > 201402L
+#if __cplusplus >= 201703L
 
-#define __cpp_lib_clamp 201603
+#define __cpp_lib_clamp 201603L
 
   /**
    *  @brief  Returns the value clamped between lo and hi.
@@ -3712,14 +3657,17 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
    *  @param  __val  A value of arbitrary type.
    *  @param  __lo   A lower limit of arbitrary type.
    *  @param  __hi   An upper limit of arbitrary type.
-   *  @return max(__val, __lo) if __val < __hi or min(__val, __hi) otherwise.
+   *  @retval `__lo` if `__val < __lo`
+   *  @retval `__hi` if `__hi < __val`
+   *  @retval `__val` otherwise.
+   *  @pre `_Tp` is LessThanComparable and `(__hi < __lo)` is false.
    */
   template<typename _Tp>
     constexpr const _Tp&
     clamp(const _Tp& __val, const _Tp& __lo, const _Tp& __hi)
     {
       __glibcxx_assert(!(__hi < __lo));
-      return (__val < __lo) ? __lo : (__hi < __val) ? __hi : __val;
+      return std::min(std::max(__val, __lo), __hi);
     }
 
   /**
@@ -3729,15 +3677,17 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
    *  @param  __lo    A lower limit of arbitrary type.
    *  @param  __hi    An upper limit of arbitrary type.
    *  @param  __comp  A comparison functor.
-   *  @return max(__val, __lo, __comp) if __comp(__val, __hi)
-   *	      or min(__val, __hi, __comp) otherwise.
+   *  @retval `__lo` if `__comp(__val, __lo)`
+   *  @retval `__hi` if `__comp(__hi, __val)`
+   *  @retval `__val` otherwise.
+   *  @pre `__comp(__hi, __lo)` is false.
    */
   template<typename _Tp, typename _Compare>
     constexpr const _Tp&
     clamp(const _Tp& __val, const _Tp& __lo, const _Tp& __hi, _Compare __comp)
     {
       __glibcxx_assert(!__comp(__hi, __lo));
-      return __comp(__val, __lo) ? __lo : __comp(__hi, __val) ? __hi : __val;
+      return std::min(std::max(__val, __lo, __comp), __hi, __comp);
     }
 #endif // C++17
 #endif // C++14
@@ -3853,7 +3803,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
       for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i)
 	std::iter_swap(__i, __first + __d(__g, __p_type(0, __i - __first)));
     }
-#endif
+#endif // USE C99_STDINT
 
 #endif // C++11
 
@@ -3872,6 +3822,7 @@ _GLIBCXX_BEGIN_NAMESPACE_ALGO
    *  If @p __f has a return value it is ignored.
   */
   template<typename _InputIterator, typename _Function>
+    _GLIBCXX20_CONSTEXPR
     _Function
     for_each(_InputIterator __first, _InputIterator __last, _Function __f)
     {
@@ -3883,6 +3834,46 @@ _GLIBCXX_BEGIN_NAMESPACE_ALGO
       return __f; // N.B. [alg.foreach] says std::move(f) but it's redundant.
     }
 
+#if __cplusplus >= 201703L
+  /**
+   *  @brief Apply a function to every element of a sequence.
+   *  @ingroup non_mutating_algorithms
+   *  @param  __first  An input iterator.
+   *  @param  __n      A value convertible to an integer.
+   *  @param  __f      A unary function object.
+   *  @return   `__first+__n`
+   *
+   *  Applies the function object `__f` to each element in the range
+   *  `[first, first+n)`.  `__f` must not modify the order of the sequence.
+   *  If `__f` has a return value it is ignored.
+  */
+  template<typename _InputIterator, typename _Size, typename _Function>
+    _GLIBCXX20_CONSTEXPR
+    _InputIterator
+    for_each_n(_InputIterator __first, _Size __n, _Function __f)
+    {
+      auto __n2 = std::__size_to_integer(__n);
+      using _Cat = typename iterator_traits<_InputIterator>::iterator_category;
+      if constexpr (is_base_of_v<random_access_iterator_tag, _Cat>)
+	{
+	  if (__n2 <= 0)
+	    return __first;
+	  auto __last = __first + __n2;
+	  std::for_each(__first, __last, std::move(__f));
+	  return __last;
+	}
+      else
+	{
+	  while (__n2-->0)
+	    {
+	      __f(*__first);
+	      ++__first;
+	    }
+	  return __first;
+	}
+    }
+#endif // C++17
+
   /**
    *  @brief Find the first occurrence of a value in a sequence.
    *  @ingroup non_mutating_algorithms
@@ -3893,6 +3884,7 @@ _GLIBCXX_BEGIN_NAMESPACE_ALGO
    *  such that @c *i == @p __val, or @p __last if no such iterator exists.
   */
   template<typename _InputIterator, typename _Tp>
+    _GLIBCXX20_CONSTEXPR
     inline _InputIterator
     find(_InputIterator __first, _InputIterator __last,
 	 const _Tp& __val)
@@ -3917,6 +3909,7 @@ _GLIBCXX_BEGIN_NAMESPACE_ALGO
    *  such that @p __pred(*i) is true, or @p __last if no such iterator exists.
   */
   template<typename _InputIterator, typename _Predicate>
+    _GLIBCXX20_CONSTEXPR
     inline _InputIterator
     find_if(_InputIterator __first, _InputIterator __last,
 	    _Predicate __pred)
@@ -3948,6 +3941,7 @@ _GLIBCXX_BEGIN_NAMESPACE_ALGO
    *  otherwise returns @p __last1.
   */
   template<typename _InputIterator, typename _ForwardIterator>
+    _GLIBCXX20_CONSTEXPR
     _InputIterator
     find_first_of(_InputIterator __first1, _InputIterator __last1,
 		  _ForwardIterator __first2, _ForwardIterator __last2)
@@ -3989,6 +3983,7 @@ _GLIBCXX_BEGIN_NAMESPACE_ALGO
   */
   template<typename _InputIterator, typename _ForwardIterator,
 	   typename _BinaryPredicate>
+    _GLIBCXX20_CONSTEXPR
     _InputIterator
     find_first_of(_InputIterator __first1, _InputIterator __last1,
 		  _ForwardIterator __first2, _ForwardIterator __last2,
@@ -4020,6 +4015,7 @@ _GLIBCXX_BEGIN_NAMESPACE_ALGO
    *  or @p __last if no such iterator exists.
   */
   template<typename _ForwardIterator>
+    _GLIBCXX20_CONSTEXPR
     inline _ForwardIterator
     adjacent_find(_ForwardIterator __first, _ForwardIterator __last)
     {
@@ -4045,6 +4041,7 @@ _GLIBCXX_BEGIN_NAMESPACE_ALGO
    *  exists.
   */
   template<typename _ForwardIterator, typename _BinaryPredicate>
+    _GLIBCXX20_CONSTEXPR
     inline _ForwardIterator
     adjacent_find(_ForwardIterator __first, _ForwardIterator __last,
 		  _BinaryPredicate __binary_pred)
@@ -4070,6 +4067,7 @@ _GLIBCXX_BEGIN_NAMESPACE_ALGO
    *  for which @c *i == @p __value
   */
   template<typename _InputIterator, typename _Tp>
+    _GLIBCXX20_CONSTEXPR
     inline typename iterator_traits<_InputIterator>::difference_type
     count(_InputIterator __first, _InputIterator __last, const _Tp& __value)
     {
@@ -4093,6 +4091,7 @@ _GLIBCXX_BEGIN_NAMESPACE_ALGO
    *  for which @p __pred(*i) is true.
   */
   template<typename _InputIterator, typename _Predicate>
+    _GLIBCXX20_CONSTEXPR
     inline typename iterator_traits<_InputIterator>::difference_type
     count_if(_InputIterator __first, _InputIterator __last, _Predicate __pred)
     {
@@ -4133,6 +4132,7 @@ _GLIBCXX_BEGIN_NAMESPACE_ALGO
    *  @p [__first1,__last1-(__last2-__first2))
   */
   template<typename _ForwardIterator1, typename _ForwardIterator2>
+    _GLIBCXX20_CONSTEXPR
     inline _ForwardIterator1
     search(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
 	   _ForwardIterator2 __first2, _ForwardIterator2 __last2)
@@ -4173,6 +4173,7 @@ _GLIBCXX_BEGIN_NAMESPACE_ALGO
   */
   template<typename _ForwardIterator1, typename _ForwardIterator2,
 	   typename _BinaryPredicate>
+    _GLIBCXX20_CONSTEXPR
     inline _ForwardIterator1
     search(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
 	   _ForwardIterator2 __first2, _ForwardIterator2 __last2,
@@ -4207,6 +4208,7 @@ _GLIBCXX_BEGIN_NAMESPACE_ALGO
    *  equal to @p __val.
   */
   template<typename _ForwardIterator, typename _Integer, typename _Tp>
+    _GLIBCXX20_CONSTEXPR
     inline _ForwardIterator
     search_n(_ForwardIterator __first, _ForwardIterator __last,
 	     _Integer __count, const _Tp& __val)
@@ -4241,6 +4243,7 @@ _GLIBCXX_BEGIN_NAMESPACE_ALGO
   */
   template<typename _ForwardIterator, typename _Integer, typename _Tp,
 	   typename _BinaryPredicate>
+    _GLIBCXX20_CONSTEXPR
     inline _ForwardIterator
     search_n(_ForwardIterator __first, _ForwardIterator __last,
 	     _Integer __count, const _Tp& __val,
@@ -4256,7 +4259,7 @@ _GLIBCXX_BEGIN_NAMESPACE_ALGO
 		__gnu_cxx::__ops::__iter_comp_val(__binary_pred, __val));
     }
 
-#if __cplusplus > 201402L
+#if __cplusplus >= 201703L
   /** @brief Search a sequence using a Searcher object.
    *
    *  @param  __first        A forward iterator.
@@ -4265,6 +4268,7 @@ _GLIBCXX_BEGIN_NAMESPACE_ALGO
    *  @return @p __searcher(__first,__last).first
   */
   template<typename _ForwardIterator, typename _Searcher>
+    _GLIBCXX20_CONSTEXPR
     inline _ForwardIterator
     search(_ForwardIterator __first, _ForwardIterator __last,
 	   const _Searcher& __searcher)
@@ -4289,6 +4293,7 @@ _GLIBCXX_BEGIN_NAMESPACE_ALGO
   */
   template<typename _InputIterator, typename _OutputIterator,
 	   typename _UnaryOperation>
+    _GLIBCXX20_CONSTEXPR
     _OutputIterator
     transform(_InputIterator __first, _InputIterator __last,
 	      _OutputIterator __result, _UnaryOperation __unary_op)
@@ -4326,6 +4331,7 @@ _GLIBCXX_BEGIN_NAMESPACE_ALGO
   */
   template<typename _InputIterator1, typename _InputIterator2,
 	   typename _OutputIterator, typename _BinaryOperation>
+    _GLIBCXX20_CONSTEXPR
     _OutputIterator
     transform(_InputIterator1 __first1, _InputIterator1 __last1,
 	      _InputIterator2 __first2, _OutputIterator __result,
@@ -4354,10 +4360,11 @@ _GLIBCXX_BEGIN_NAMESPACE_ALGO
    *  @param  __new_value  The replacement value.
    *  @return   replace() returns no value.
    *
-   *  For each iterator @c i in the range @p [__first,__last) if @c *i ==
-   *  @p __old_value then the assignment @c *i = @p __new_value is performed.
+   *  For each iterator `i` in the range `[__first,__last)` if
+   *  `*i == __old_value` then the assignment `*i = __new_value` is performed.
   */
   template<typename _ForwardIterator, typename _Tp>
+    _GLIBCXX20_CONSTEXPR
     void
     replace(_ForwardIterator __first, _ForwardIterator __last,
 	    const _Tp& __old_value, const _Tp& __new_value)
@@ -4386,10 +4393,11 @@ _GLIBCXX_BEGIN_NAMESPACE_ALGO
    *  @param  __new_value  The replacement value.
    *  @return   replace_if() returns no value.
    *
-   *  For each iterator @c i in the range @p [__first,__last) if @p __pred(*i)
-   *  is true then the assignment @c *i = @p __new_value is performed.
+   *  For each iterator `i` in the range `[__first,__last)` if `__pred(*i)`
+   *  is true then the assignment `*i = __new_value` is performed.
   */
   template<typename _ForwardIterator, typename _Predicate, typename _Tp>
+    _GLIBCXX20_CONSTEXPR
     void
     replace_if(_ForwardIterator __first, _ForwardIterator __last,
 	       _Predicate __pred, const _Tp& __new_value)
@@ -4414,14 +4422,14 @@ _GLIBCXX_BEGIN_NAMESPACE_ALGO
    *  @ingroup mutating_algorithms
    *  @param  __first  A forward iterator.
    *  @param  __last   A forward iterator.
-   *  @param  __gen    A function object taking no arguments and returning
-   *                 std::iterator_traits<_ForwardIterator>::value_type
+   *  @param  __gen    A function object callable with no arguments.
    *  @return   generate() returns no value.
    *
-   *  Performs the assignment @c *i = @p __gen() for each @c i in the range
-   *  @p [__first,__last).
+   *  Performs the assignment `*i = __gen()` for each `i` in the range
+   *  `[__first, __last)`.
   */
   template<typename _ForwardIterator, typename _Generator>
+    _GLIBCXX20_CONSTEXPR
     void
     generate(_ForwardIterator __first, _ForwardIterator __last,
 	     _Generator __gen)
@@ -4442,17 +4450,19 @@ _GLIBCXX_BEGIN_NAMESPACE_ALGO
    *  @ingroup mutating_algorithms
    *  @param  __first  A forward iterator.
    *  @param  __n      The length of the sequence.
-   *  @param  __gen    A function object taking no arguments and returning
-   *                 std::iterator_traits<_ForwardIterator>::value_type
-   *  @return   The end of the sequence, @p __first+__n
+   *  @param  __gen    A function object callable with no arguments.
+   *  @return   The end of the sequence, i.e., `__first + __n`
    *
-   *  Performs the assignment @c *i = @p __gen() for each @c i in the range
-   *  @p [__first,__first+__n).
+   *  Performs the assignment `*i = __gen()` for each `i` in the range
+   *  `[__first, __first + __n)`.
    *
-   *  _GLIBCXX_RESOLVE_LIB_DEFECTS
-   *  DR 865. More algorithms that throw away information
+   * If `__n` is negative, the function does nothing and returns `__first`.
   */
+  // _GLIBCXX_RESOLVE_LIB_DEFECTS
+  // DR 865. More algorithms that throw away information
+  // DR 426. search_n(), fill_n(), and generate_n() with negative n
   template<typename _OutputIterator, typename _Size, typename _Generator>
+    _GLIBCXX20_CONSTEXPR
     _OutputIterator
     generate_n(_OutputIterator __first, _Size __n, _Generator __gen)
     {
@@ -4461,7 +4471,8 @@ _GLIBCXX_BEGIN_NAMESPACE_ALGO
 	    // "the type returned by a _Generator"
 	    __typeof__(__gen())>)
 
-      for (__decltype(__n + 0) __niter = __n;
+      typedef __decltype(std::__size_to_integer(__n)) _IntSize;
+      for (_IntSize __niter = std::__size_to_integer(__n);
 	   __niter > 0; --__niter, (void) ++__first)
 	*__first = __gen();
       return __first;
@@ -4475,20 +4486,18 @@ _GLIBCXX_BEGIN_NAMESPACE_ALGO
    *  @param  __result  An output iterator.
    *  @return   An iterator designating the end of the resulting sequence.
    *
-   *  Copies each element in the range @p [__first,__last) to the range
-   *  beginning at @p __result, except that only the first element is copied
+   *  Copies each element in the range `[__first, __last)` to the range
+   *  beginning at `__result`, except that only the first element is copied
    *  from groups of consecutive elements that compare equal.
-   *  unique_copy() is stable, so the relative order of elements that are
+   *  `unique_copy()` is stable, so the relative order of elements that are
    *  copied is unchanged.
-   *
-   *  _GLIBCXX_RESOLVE_LIB_DEFECTS
-   *  DR 241. Does unique_copy() require CopyConstructible and Assignable?
-   *  
-   *  _GLIBCXX_RESOLVE_LIB_DEFECTS
-   *  DR 538. 241 again: Does unique_copy() require CopyConstructible and 
-   *  Assignable?
-  */
+   */
+  // _GLIBCXX_RESOLVE_LIB_DEFECTS
+  // DR 241. Does unique_copy() require CopyConstructible and Assignable?
+  // DR 538. 241 again: Does unique_copy() require CopyConstructible and
+  // Assignable?
   template<typename _InputIterator, typename _OutputIterator>
+    _GLIBCXX20_CONSTEXPR
     inline _OutputIterator
     unique_copy(_InputIterator __first, _InputIterator __last,
 		_OutputIterator __result)
@@ -4518,18 +4527,18 @@ _GLIBCXX_BEGIN_NAMESPACE_ALGO
    *  @param  __binary_pred  A binary predicate.
    *  @return   An iterator designating the end of the resulting sequence.
    *
-   *  Copies each element in the range @p [__first,__last) to the range
-   *  beginning at @p __result, except that only the first element is copied
-   *  from groups of consecutive elements for which @p __binary_pred returns
+   *  Copies each element in the range `[__first, __last)` to the range
+   *  beginning at `__result`, except that only the first element is copied
+   *  from groups of consecutive elements for which `__binary_pred` returns
    *  true.
-   *  unique_copy() is stable, so the relative order of elements that are
+   *  `unique_copy()` is stable, so the relative order of elements that are
    *  copied is unchanged.
-   *
-   *  _GLIBCXX_RESOLVE_LIB_DEFECTS
-   *  DR 241. Does unique_copy() require CopyConstructible and Assignable?
-  */
+   */
+  // _GLIBCXX_RESOLVE_LIB_DEFECTS
+  // DR 241. Does unique_copy() require CopyConstructible and Assignable?
   template<typename _InputIterator, typename _OutputIterator,
 	   typename _BinaryPredicate>
+    _GLIBCXX20_CONSTEXPR
     inline _OutputIterator
     unique_copy(_InputIterator __first, _InputIterator __last,
 		_OutputIterator __result,
@@ -4549,6 +4558,7 @@ _GLIBCXX_BEGIN_NAMESPACE_ALGO
 				std::__iterator_category(__result));
     }
 
+#if __cplusplus <= 201103L || _GLIBCXX_USE_DEPRECATED
 #if _GLIBCXX_HOSTED
   /**
    *  @brief Randomly shuffle the elements of a sequence.
@@ -4557,11 +4567,16 @@ _GLIBCXX_BEGIN_NAMESPACE_ALGO
    *  @param  __last    A forward iterator.
    *  @return  Nothing.
    *
-   *  Reorder the elements in the range @p [__first,__last) using a random
+   *  Reorder the elements in the range `[__first, __last)` using a random
    *  distribution, so that every possible ordering of the sequence is
    *  equally likely.
+   *
+   *  @deprecated
+   *  Since C++14 `std::random_shuffle` is not part of the C++ standard.
+   *  Use `std::shuffle` instead, which was introduced in C++11.
   */
   template<typename _RandomAccessIterator>
+    _GLIBCXX14_DEPRECATED_SUGGEST("std::shuffle")
     inline void
     random_shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last)
     {
@@ -4580,7 +4595,6 @@ _GLIBCXX_BEGIN_NAMESPACE_ALGO
 	      std::iter_swap(__i, __j);
 	  }
     }
-#endif
 
   /**
    *  @brief Shuffle the elements of a sequence using a random number
@@ -4591,12 +4605,17 @@ _GLIBCXX_BEGIN_NAMESPACE_ALGO
    *  @param  __rand    The RNG functor or function.
    *  @return  Nothing.
    *
-   *  Reorders the elements in the range @p [__first,__last) using @p __rand to
-   *  provide a random distribution. Calling @p __rand(N) for a positive
-   *  integer @p N should return a randomly chosen integer from the
-   *  range [0,N).
+   *  Reorders the elements in the range `[__first, __last)` using `__rand`
+   *  to provide a random distribution. Calling `__rand(N)` for a positive
+   *  integer `N` should return a randomly chosen integer from the
+   *  range `[0, N)`.
+   *
+   *  @deprecated
+   *  Since C++14 `std::random_shuffle` is not part of the C++ standard.
+   *  Use `std::shuffle` instead, which was introduced in C++11.
   */
   template<typename _RandomAccessIterator, typename _RandomNumberGenerator>
+    _GLIBCXX14_DEPRECATED_SUGGEST("std::shuffle")
     void
     random_shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last,
 #if __cplusplus >= 201103L
@@ -4619,7 +4638,8 @@ _GLIBCXX_BEGIN_NAMESPACE_ALGO
 	    std::iter_swap(__i, __j);
 	}
     }
-
+#endif // HOSTED
+#endif // C++11 || USE_DEPRECATED
 
   /**
    *  @brief Move elements for which a predicate is true to the beginning
@@ -4628,15 +4648,16 @@ _GLIBCXX_BEGIN_NAMESPACE_ALGO
    *  @param  __first   A forward iterator.
    *  @param  __last    A forward iterator.
    *  @param  __pred    A predicate functor.
-   *  @return  An iterator @p middle such that @p __pred(i) is true for each
-   *  iterator @p i in the range @p [__first,middle) and false for each @p i
-   *  in the range @p [middle,__last).
+   *  @return  An iterator `middle` such that `__pred(i)` is true for each
+   *  iterator `i` in the range `[__first, middle)` and false for each `i`
+   *  in the range `[middle, __last)`.
    *
-   *  @p __pred must not modify its operand. @p partition() does not preserve
+   *  `__pred` must not modify its operand. `partition()` does not preserve
    *  the relative ordering of elements in each group, use
-   *  @p stable_partition() if this is needed.
+   *  `stable_partition()` if this is needed.
   */
   template<typename _ForwardIterator, typename _Predicate>
+    _GLIBCXX20_CONSTEXPR
     inline _ForwardIterator
     partition(_ForwardIterator __first, _ForwardIterator __last,
 	      _Predicate   __pred)
@@ -4661,15 +4682,17 @@ _GLIBCXX_BEGIN_NAMESPACE_ALGO
    *  @param  __last    Another iterator.
    *  @return  Nothing.
    *
-   *  Sorts the smallest @p (__middle-__first) elements in the range
-   *  @p [first,last) and moves them to the range @p [__first,__middle). The
-   *  order of the remaining elements in the range @p [__middle,__last) is
-   *  undefined.
-   *  After the sort if @e i and @e j are iterators in the range
-   *  @p [__first,__middle) such that i precedes j and @e k is an iterator in
-   *  the range @p [__middle,__last) then *j<*i and *k<*i are both false.
+   *  Sorts the smallest `(__middle - __first)` elements in the range
+   *  `[first, last)` and moves them to the range `[__first, __middle)`. The
+   *  order of the remaining elements in the range `[__middle, __last)` is
+   *  unspecified.
+   *  After the sort if `i` and `j` are iterators in the range
+   *  `[__first, __middle)` such that `i` precedes `j` and `k` is an iterator
+   *  in the range `[__middle, __last)` then `*j < *i` and `*k < *i` are
+   *  both false.
   */
   template<typename _RandomAccessIterator>
+    _GLIBCXX20_CONSTEXPR
     inline void
     partial_sort(_RandomAccessIterator __first,
 		 _RandomAccessIterator __middle,
@@ -4698,16 +4721,17 @@ _GLIBCXX_BEGIN_NAMESPACE_ALGO
    *  @param  __comp    A comparison functor.
    *  @return  Nothing.
    *
-   *  Sorts the smallest @p (__middle-__first) elements in the range
-   *  @p [__first,__last) and moves them to the range @p [__first,__middle). The
-   *  order of the remaining elements in the range @p [__middle,__last) is
-   *  undefined.
-   *  After the sort if @e i and @e j are iterators in the range
-   *  @p [__first,__middle) such that i precedes j and @e k is an iterator in
-   *  the range @p [__middle,__last) then @p *__comp(j,*i) and @p __comp(*k,*i)
-   *  are both false.
+   *  Sorts the smallest `(__middle - __first)` elements in the range
+   *  `[__first, __last)` and moves them to the range `[__first, __middle)`.
+   *  The order of the remaining elements in the range `[__middle, __last)` is
+   *  unspecified.
+   *  After the sort if `i` and `j` are iterators in the range
+   *  `[__first, __middle)` such that `i` precedes `j` and `k` is an iterator
+   *  in the range `[__middle, __last)` then `*__comp(j, *i)` and
+   *  `__comp(*k, *i)` are both false.
   */
   template<typename _RandomAccessIterator, typename _Compare>
+    _GLIBCXX20_CONSTEXPR
     inline void
     partial_sort(_RandomAccessIterator __first,
 		 _RandomAccessIterator __middle,
@@ -4736,14 +4760,15 @@ _GLIBCXX_BEGIN_NAMESPACE_ALGO
    *  @param  __last    Another iterator.
    *  @return  Nothing.
    *
-   *  Rearranges the elements in the range @p [__first,__last) so that @p *__nth
+   *  Rearranges the elements in the range `[__first, __last)` so that `*__nth`
    *  is the same element that would have been in that position had the
-   *  whole sequence been sorted. The elements either side of @p *__nth are
-   *  not completely sorted, but for any iterator @e i in the range
-   *  @p [__first,__nth) and any iterator @e j in the range @p [__nth,__last) it
-   *  holds that *j < *i is false.
+   *  whole sequence been sorted. The elements either side of `*__nth` are
+   *  not completely sorted, but for any iterator `i` in the range
+   *  `[__first, __nth)` and any iterator `j` in the range `[__nth, __last)` it
+   *  holds that `*j < *i` is false.
   */
   template<typename _RandomAccessIterator>
+    _GLIBCXX20_CONSTEXPR
     inline void
     nth_element(_RandomAccessIterator __first, _RandomAccessIterator __nth,
 		_RandomAccessIterator __last)
@@ -4775,14 +4800,15 @@ _GLIBCXX_BEGIN_NAMESPACE_ALGO
    *  @param  __comp    A comparison functor.
    *  @return  Nothing.
    *
-   *  Rearranges the elements in the range @p [__first,__last) so that @p *__nth
+   *  Rearranges the elements in the range `[__first, __last)` so that `*__nth`
    *  is the same element that would have been in that position had the
-   *  whole sequence been sorted. The elements either side of @p *__nth are
-   *  not completely sorted, but for any iterator @e i in the range
-   *  @p [__first,__nth) and any iterator @e j in the range @p [__nth,__last) it
-   *  holds that @p __comp(*j,*i) is false.
+   *  whole sequence been sorted. The elements either side of `*__nth` are
+   *  not completely sorted, but for any iterator `i` in the range
+   *  `[__first, __nth)` and any iterator `j` in the range `[__nth, __last)`
+   *  it holds that `__comp(*j, *i)` is false.
   */
   template<typename _RandomAccessIterator, typename _Compare>
+    _GLIBCXX20_CONSTEXPR
     inline void
     nth_element(_RandomAccessIterator __first, _RandomAccessIterator __nth,
 		_RandomAccessIterator __last, _Compare __comp)
@@ -4812,14 +4838,15 @@ _GLIBCXX_BEGIN_NAMESPACE_ALGO
    *  @param  __last    Another iterator.
    *  @return  Nothing.
    *
-   *  Sorts the elements in the range @p [__first,__last) in ascending order,
-   *  such that for each iterator @e i in the range @p [__first,__last-1),  
-   *  *(i+1)<*i is false.
+   *  Sorts the elements in the range `[__first, __last)` in ascending order,
+   *  such that for each iterator `i` in the range `[__first, __last - 1)`,
+   *  `*(i+1) < *i` is false.
    *
    *  The relative ordering of equivalent elements is not preserved, use
-   *  @p stable_sort() if this is needed.
+   *  `stable_sort()` if this is needed.
   */
   template<typename _RandomAccessIterator>
+    _GLIBCXX20_CONSTEXPR
     inline void
     sort(_RandomAccessIterator __first, _RandomAccessIterator __last)
     {
@@ -4842,14 +4869,15 @@ _GLIBCXX_BEGIN_NAMESPACE_ALGO
    *  @param  __comp    A comparison functor.
    *  @return  Nothing.
    *
-   *  Sorts the elements in the range @p [__first,__last) in ascending order,
-   *  such that @p __comp(*(i+1),*i) is false for every iterator @e i in the
-   *  range @p [__first,__last-1).
+   *  Sorts the elements in the range `[__first, __last)` in ascending order,
+   *  such that `__comp(*(i+1), *i)` is false for every iterator `i` in the
+   *  range `[__first, __last - 1)`.
    *
    *  The relative ordering of equivalent elements is not preserved, use
-   *  @p stable_sort() if this is needed.
+   *  `stable_sort()` if this is needed.
   */
   template<typename _RandomAccessIterator, typename _Compare>
+    _GLIBCXX20_CONSTEXPR
     inline void
     sort(_RandomAccessIterator __first, _RandomAccessIterator __last,
 	 _Compare __comp)
@@ -4868,6 +4896,7 @@ _GLIBCXX_BEGIN_NAMESPACE_ALGO
 
   template<typename _InputIterator1, typename _InputIterator2,
 	   typename _OutputIterator, typename _Compare>
+    _GLIBCXX20_CONSTEXPR
     _OutputIterator
     __merge(_InputIterator1 __first1, _InputIterator1 __last1,
 	    _InputIterator2 __first2, _InputIterator2 __last2,
@@ -4899,8 +4928,8 @@ _GLIBCXX_BEGIN_NAMESPACE_ALGO
    *  @param  __last1   Another iterator.
    *  @param  __last2   Another iterator.
    *  @param  __result  An iterator pointing to the end of the merged range.
-   *  @return         An iterator pointing to the first element <em>not less
-   *                  than</em> @e val.
+   *  @return   An output iterator equal to @p __result + (__last1 - __first1)
+   *            + (__last2 - __first2).
    *
    *  Merges the ranges @p [__first1,__last1) and @p [__first2,__last2) into
    *  the sorted range @p [__result, __result + (__last1-__first1) +
@@ -4912,6 +4941,7 @@ _GLIBCXX_BEGIN_NAMESPACE_ALGO
   */
   template<typename _InputIterator1, typename _InputIterator2,
 	   typename _OutputIterator>
+    _GLIBCXX20_CONSTEXPR
     inline _OutputIterator
     merge(_InputIterator1 __first1, _InputIterator1 __last1,
 	  _InputIterator2 __first2, _InputIterator2 __last2,
@@ -4946,8 +4976,8 @@ _GLIBCXX_BEGIN_NAMESPACE_ALGO
    *  @param  __last2   Another iterator.
    *  @param  __result  An iterator pointing to the end of the merged range.
    *  @param  __comp    A functor to use for comparisons.
-   *  @return         An iterator pointing to the first element "not less
-   *                  than" @e val.
+   *  @return   An output iterator equal to @p __result + (__last1 - __first1)
+   *            + (__last2 - __first2).
    *
    *  Merges the ranges @p [__first1,__last1) and @p [__first2,__last2) into
    *  the sorted range @p [__result, __result + (__last1-__first1) +
@@ -4962,6 +4992,7 @@ _GLIBCXX_BEGIN_NAMESPACE_ALGO
   */
   template<typename _InputIterator1, typename _InputIterator2,
 	   typename _OutputIterator, typename _Compare>
+    _GLIBCXX20_CONSTEXPR
     inline _OutputIterator
     merge(_InputIterator1 __first1, _InputIterator1 __last1,
 	  _InputIterator2 __first2, _InputIterator2 __last2,
@@ -4997,14 +5028,27 @@ _GLIBCXX_BEGIN_NAMESPACE_ALGO
       typedef typename iterator_traits<_RandomAccessIterator>::difference_type
 	_DistanceType;
 
-      typedef _Temporary_buffer<_RandomAccessIterator, _ValueType> _TmpBuf;
-      _TmpBuf __buf(__first, __last);
+      if (__first == __last)
+	return;
 
-      if (__buf.begin() == 0)
+#if _GLIBCXX_HOSTED
+      typedef _Temporary_buffer<_RandomAccessIterator, _ValueType> _TmpBuf;
+      // __stable_sort_adaptive sorts the range in two halves,
+      // so the buffer only needs to fit half the range at once.
+      _TmpBuf __buf(__first, (__last - __first + 1) / 2);
+
+      if (__builtin_expect(__buf.requested_size() == __buf.size(), true))
+	std::__stable_sort_adaptive(__first,
+				    __first + _DistanceType(__buf.size()),
+				    __last, __buf.begin(), __comp);
+      else if (__builtin_expect(__buf.begin() == 0, false))
 	std::__inplace_stable_sort(__first, __last, __comp);
       else
-	std::__stable_sort_adaptive(__first, __last, __buf.begin(),
-				    _DistanceType(__buf.size()), __comp);
+	std::__stable_sort_adaptive_resize(__first, __last, __buf.begin(),
+					   _DistanceType(__buf.size()), __comp);
+#else
+      std::__inplace_stable_sort(__first, __last, __comp);
+#endif
     }
 
   /**
@@ -5079,6 +5123,7 @@ _GLIBCXX_BEGIN_NAMESPACE_ALGO
   template<typename _InputIterator1, typename _InputIterator2,
 	   typename _OutputIterator,
 	   typename _Compare>
+    _GLIBCXX20_CONSTEXPR
     _OutputIterator
     __set_union(_InputIterator1 __first1, _InputIterator1 __last1,
 		_InputIterator2 __first2, _InputIterator2 __last2,
@@ -5129,6 +5174,7 @@ _GLIBCXX_BEGIN_NAMESPACE_ALGO
   */
   template<typename _InputIterator1, typename _InputIterator2,
 	   typename _OutputIterator>
+    _GLIBCXX20_CONSTEXPR
     inline _OutputIterator
     set_union(_InputIterator1 __first1, _InputIterator1 __last1,
 	      _InputIterator2 __first2, _InputIterator2 __last2,
@@ -5179,6 +5225,7 @@ _GLIBCXX_BEGIN_NAMESPACE_ALGO
   */
   template<typename _InputIterator1, typename _InputIterator2,
 	   typename _OutputIterator, typename _Compare>
+    _GLIBCXX20_CONSTEXPR
     inline _OutputIterator
     set_union(_InputIterator1 __first1, _InputIterator1 __last1,
 	      _InputIterator2 __first2, _InputIterator2 __last2,
@@ -5210,6 +5257,7 @@ _GLIBCXX_BEGIN_NAMESPACE_ALGO
   template<typename _InputIterator1, typename _InputIterator2,
 	   typename _OutputIterator,
 	   typename _Compare>
+    _GLIBCXX20_CONSTEXPR
     _OutputIterator
     __set_intersection(_InputIterator1 __first1, _InputIterator1 __last1,
 		       _InputIterator2 __first2, _InputIterator2 __last2,
@@ -5250,6 +5298,7 @@ _GLIBCXX_BEGIN_NAMESPACE_ALGO
   */
   template<typename _InputIterator1, typename _InputIterator2,
 	   typename _OutputIterator>
+    _GLIBCXX20_CONSTEXPR
     inline _OutputIterator
     set_intersection(_InputIterator1 __first1, _InputIterator1 __last1,
 		     _InputIterator2 __first2, _InputIterator2 __last2,
@@ -5299,6 +5348,7 @@ _GLIBCXX_BEGIN_NAMESPACE_ALGO
   */
   template<typename _InputIterator1, typename _InputIterator2,
 	   typename _OutputIterator, typename _Compare>
+    _GLIBCXX20_CONSTEXPR
     inline _OutputIterator
     set_intersection(_InputIterator1 __first1, _InputIterator1 __last1,
 		     _InputIterator2 __first2, _InputIterator2 __last2,
@@ -5328,6 +5378,7 @@ _GLIBCXX_BEGIN_NAMESPACE_ALGO
   template<typename _InputIterator1, typename _InputIterator2,
 	   typename _OutputIterator,
 	   typename _Compare>
+    _GLIBCXX20_CONSTEXPR
     _OutputIterator
     __set_difference(_InputIterator1 __first1, _InputIterator1 __last1,
 		     _InputIterator2 __first2, _InputIterator2 __last2,
@@ -5372,6 +5423,7 @@ _GLIBCXX_BEGIN_NAMESPACE_ALGO
   */
   template<typename _InputIterator1, typename _InputIterator2,
 	   typename _OutputIterator>
+    _GLIBCXX20_CONSTEXPR
     inline _OutputIterator
     set_difference(_InputIterator1 __first1, _InputIterator1 __last1,
 		   _InputIterator2 __first2, _InputIterator2 __last2,
@@ -5423,6 +5475,7 @@ _GLIBCXX_BEGIN_NAMESPACE_ALGO
   */
   template<typename _InputIterator1, typename _InputIterator2,
 	   typename _OutputIterator, typename _Compare>
+    _GLIBCXX20_CONSTEXPR
     inline _OutputIterator
     set_difference(_InputIterator1 __first1, _InputIterator1 __last1,
 		   _InputIterator2 __first2, _InputIterator2 __last2,
@@ -5452,6 +5505,7 @@ _GLIBCXX_BEGIN_NAMESPACE_ALGO
   template<typename _InputIterator1, typename _InputIterator2,
 	   typename _OutputIterator,
 	   typename _Compare>
+    _GLIBCXX20_CONSTEXPR
     _OutputIterator
     __set_symmetric_difference(_InputIterator1 __first1,
 			       _InputIterator1 __last1,
@@ -5502,6 +5556,7 @@ _GLIBCXX_BEGIN_NAMESPACE_ALGO
   */
   template<typename _InputIterator1, typename _InputIterator2,
 	   typename _OutputIterator>
+    _GLIBCXX20_CONSTEXPR
     inline _OutputIterator
     set_symmetric_difference(_InputIterator1 __first1, _InputIterator1 __last1,
 			     _InputIterator2 __first2, _InputIterator2 __last2,
@@ -5553,6 +5608,7 @@ _GLIBCXX_BEGIN_NAMESPACE_ALGO
   */
   template<typename _InputIterator1, typename _InputIterator2,
 	   typename _OutputIterator, typename _Compare>
+    _GLIBCXX20_CONSTEXPR
     inline _OutputIterator
     set_symmetric_difference(_InputIterator1 __first1, _InputIterator1 __last1,
 			     _InputIterator2 __first2, _InputIterator2 __last2,
@@ -5711,6 +5767,49 @@ _GLIBCXX_BEGIN_NAMESPACE_ALGO
 				__gnu_cxx::__ops::__iter_comp_iter(__comp));
     }
 
+#if __cplusplus >= 201103L
+  // N2722 + DR 915.
+  template<typename _Tp>
+    _GLIBCXX14_CONSTEXPR
+    inline _Tp
+    min(initializer_list<_Tp> __l)
+    {
+      __glibcxx_requires_irreflexive(__l.begin(), __l.end());
+      return *_GLIBCXX_STD_A::__min_element(__l.begin(), __l.end(),
+	  __gnu_cxx::__ops::__iter_less_iter());
+    }
+
+  template<typename _Tp, typename _Compare>
+    _GLIBCXX14_CONSTEXPR
+    inline _Tp
+    min(initializer_list<_Tp> __l, _Compare __comp)
+    {
+      __glibcxx_requires_irreflexive_pred(__l.begin(), __l.end(), __comp);
+      return *_GLIBCXX_STD_A::__min_element(__l.begin(), __l.end(),
+	  __gnu_cxx::__ops::__iter_comp_iter(__comp));
+    }
+
+  template<typename _Tp>
+    _GLIBCXX14_CONSTEXPR
+    inline _Tp
+    max(initializer_list<_Tp> __l)
+    {
+      __glibcxx_requires_irreflexive(__l.begin(), __l.end());
+      return *_GLIBCXX_STD_A::__max_element(__l.begin(), __l.end(),
+	  __gnu_cxx::__ops::__iter_less_iter());
+    }
+
+  template<typename _Tp, typename _Compare>
+    _GLIBCXX14_CONSTEXPR
+    inline _Tp
+    max(initializer_list<_Tp> __l, _Compare __comp)
+    {
+      __glibcxx_requires_irreflexive_pred(__l.begin(), __l.end(), __comp);
+      return *_GLIBCXX_STD_A::__max_element(__l.begin(), __l.end(),
+	  __gnu_cxx::__ops::__iter_comp_iter(__comp));
+    }
+#endif // C++11
+
 #if __cplusplus >= 201402L
   /// Reservoir sampling algorithm.
   template<typename _InputIterator, typename _RandomAccessIterator,
@@ -5754,6 +5853,9 @@ _GLIBCXX_BEGIN_NAMESPACE_ALGO
       using _Gen = remove_reference_t<_UniformRandomBitGenerator>;
       using __uc_type = common_type_t<typename _Gen::result_type, _USize>;
 
+      if (__first == __last)
+	return __out;
+
       __distrib_type __d{};
       _Size __unsampled_sz = std::distance(__first, __last);
       __n = std::min(__n, __unsampled_sz);
@@ -5805,7 +5907,7 @@ _GLIBCXX_BEGIN_NAMESPACE_ALGO
     }
 
 #if __cplusplus > 201402L
-#define __cpp_lib_sample 201603
+#define __cpp_lib_sample 201603L
   /// Take a random sample from a population.
   template<typename _PopulationIterator, typename _SampleIterator,
            typename _Distance, typename _UniformRandomBitGenerator>