xref: /netbsd-src/external/gpl3/gcc.old/dist/libstdc++-v3/include/bits/stl_algo.h (revision 8feb0f0b7eaff0608f8350bbfa3098827b4bb91b)
1 // Algorithm implementation -*- C++ -*-
2 
3 // Copyright (C) 2001-2020 Free Software Foundation, Inc.
4 //
5 // This file is part of the GNU ISO C++ Library.  This library is free
6 // software; you can redistribute it and/or modify it under the
7 // terms of the GNU General Public License as published by the
8 // Free Software Foundation; either version 3, or (at your option)
9 // any later version.
10 
11 // This library is distributed in the hope that it will be useful,
12 // but WITHOUT ANY WARRANTY; without even the implied warranty of
13 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
14 // GNU General Public License for more details.
15 
16 // Under Section 7 of GPL version 3, you are granted additional
17 // permissions described in the GCC Runtime Library Exception, version
18 // 3.1, as published by the Free Software Foundation.
19 
20 // You should have received a copy of the GNU General Public License and
21 // a copy of the GCC Runtime Library Exception along with this program;
22 // see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
23 // <http://www.gnu.org/licenses/>.
24 
25 /*
26  *
27  * Copyright (c) 1994
28  * Hewlett-Packard Company
29  *
30  * Permission to use, copy, modify, distribute and sell this software
31  * and its documentation for any purpose is hereby granted without fee,
32  * provided that the above copyright notice appear in all copies and
33  * that both that copyright notice and this permission notice appear
34  * in supporting documentation.  Hewlett-Packard Company makes no
35  * representations about the suitability of this software for any
36  * purpose.  It is provided "as is" without express or implied warranty.
37  *
38  *
39  * Copyright (c) 1996
40  * Silicon Graphics Computer Systems, Inc.
41  *
42  * Permission to use, copy, modify, distribute and sell this software
43  * and its documentation for any purpose is hereby granted without fee,
44  * provided that the above copyright notice appear in all copies and
45  * that both that copyright notice and this permission notice appear
46  * in supporting documentation.  Silicon Graphics makes no
47  * representations about the suitability of this software for any
48  * purpose.  It is provided "as is" without express or implied warranty.
49  */
50 
51 /** @file bits/stl_algo.h
52  *  This is an internal header file, included by other library headers.
53  *  Do not attempt to use it directly. @headername{algorithm}
54  */
55 
56 #ifndef _STL_ALGO_H
57 #define _STL_ALGO_H 1
58 
59 #include <cstdlib>	     // for rand
60 #include <bits/algorithmfwd.h>
61 #include <bits/stl_heap.h>
62 #include <bits/stl_tempbuf.h>  // for _Temporary_buffer
63 #include <bits/predefined_ops.h>
64 
65 #if __cplusplus >= 201103L
66 #include <bits/uniform_int_dist.h>
67 #endif
68 
69 // See concept_check.h for the __glibcxx_*_requires macros.
70 
_GLIBCXX_VISIBILITY(default)71 namespace std _GLIBCXX_VISIBILITY(default)
72 {
73 _GLIBCXX_BEGIN_NAMESPACE_VERSION
74 
75   /// Swaps the median value of *__a, *__b and *__c under __comp to *__result
76   template<typename _Iterator, typename _Compare>
77     _GLIBCXX20_CONSTEXPR
78     void
79     __move_median_to_first(_Iterator __result,_Iterator __a, _Iterator __b,
80 			   _Iterator __c, _Compare __comp)
81     {
82       if (__comp(__a, __b))
83 	{
84 	  if (__comp(__b, __c))
85 	    std::iter_swap(__result, __b);
86 	  else if (__comp(__a, __c))
87 	    std::iter_swap(__result, __c);
88 	  else
89 	    std::iter_swap(__result, __a);
90 	}
91       else if (__comp(__a, __c))
92 	std::iter_swap(__result, __a);
93       else if (__comp(__b, __c))
94 	std::iter_swap(__result, __c);
95       else
96 	std::iter_swap(__result, __b);
97     }
98 
99   /// Provided for stable_partition to use.
100   template<typename _InputIterator, typename _Predicate>
101     _GLIBCXX20_CONSTEXPR
102     inline _InputIterator
103     __find_if_not(_InputIterator __first, _InputIterator __last,
104 		  _Predicate __pred)
105     {
106       return std::__find_if(__first, __last,
107 			    __gnu_cxx::__ops::__negate(__pred),
108 			    std::__iterator_category(__first));
109     }
110 
111   /// Like find_if_not(), but uses and updates a count of the
112   /// remaining range length instead of comparing against an end
113   /// iterator.
114   template<typename _InputIterator, typename _Predicate, typename _Distance>
115     _GLIBCXX20_CONSTEXPR
116     _InputIterator
117     __find_if_not_n(_InputIterator __first, _Distance& __len, _Predicate __pred)
118     {
119       for (; __len; --__len,  (void) ++__first)
120 	if (!__pred(__first))
121 	  break;
122       return __first;
123     }
124 
125   // set_difference
126   // set_intersection
127   // set_symmetric_difference
128   // set_union
129   // for_each
130   // find
131   // find_if
132   // find_first_of
133   // adjacent_find
134   // count
135   // count_if
136   // search
137 
138   template<typename _ForwardIterator1, typename _ForwardIterator2,
139 	   typename _BinaryPredicate>
140     _GLIBCXX20_CONSTEXPR
141     _ForwardIterator1
142     __search(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
143 	     _ForwardIterator2 __first2, _ForwardIterator2 __last2,
144 	     _BinaryPredicate  __predicate)
145     {
146       // Test for empty ranges
147       if (__first1 == __last1 || __first2 == __last2)
148 	return __first1;
149 
150       // Test for a pattern of length 1.
151       _ForwardIterator2 __p1(__first2);
152       if (++__p1 == __last2)
153 	return std::__find_if(__first1, __last1,
154 		__gnu_cxx::__ops::__iter_comp_iter(__predicate, __first2));
155 
156       // General case.
157       _ForwardIterator1 __current = __first1;
158 
159       for (;;)
160 	{
161 	  __first1 =
162 	    std::__find_if(__first1, __last1,
163 		__gnu_cxx::__ops::__iter_comp_iter(__predicate, __first2));
164 
165 	  if (__first1 == __last1)
166 	    return __last1;
167 
168 	  _ForwardIterator2 __p = __p1;
169 	  __current = __first1;
170 	  if (++__current == __last1)
171 	    return __last1;
172 
173 	  while (__predicate(__current, __p))
174 	    {
175 	      if (++__p == __last2)
176 		return __first1;
177 	      if (++__current == __last1)
178 		return __last1;
179 	    }
180 	  ++__first1;
181 	}
182       return __first1;
183     }
184 
185   // search_n
186 
187   /**
188    *  This is an helper function for search_n overloaded for forward iterators.
189   */
190   template<typename _ForwardIterator, typename _Integer,
191 	   typename _UnaryPredicate>
192     _GLIBCXX20_CONSTEXPR
193     _ForwardIterator
194     __search_n_aux(_ForwardIterator __first, _ForwardIterator __last,
195 		   _Integer __count, _UnaryPredicate __unary_pred,
196 		   std::forward_iterator_tag)
197     {
198       __first = std::__find_if(__first, __last, __unary_pred);
199       while (__first != __last)
200 	{
201 	  typename iterator_traits<_ForwardIterator>::difference_type
202 	    __n = __count;
203 	  _ForwardIterator __i = __first;
204 	  ++__i;
205 	  while (__i != __last && __n != 1 && __unary_pred(__i))
206 	    {
207 	      ++__i;
208 	      --__n;
209 	    }
210 	  if (__n == 1)
211 	    return __first;
212 	  if (__i == __last)
213 	    return __last;
214 	  __first = std::__find_if(++__i, __last, __unary_pred);
215 	}
216       return __last;
217     }
218 
219   /**
220    *  This is an helper function for search_n overloaded for random access
221    *  iterators.
222   */
223   template<typename _RandomAccessIter, typename _Integer,
224 	   typename _UnaryPredicate>
225     _GLIBCXX20_CONSTEXPR
226     _RandomAccessIter
227     __search_n_aux(_RandomAccessIter __first, _RandomAccessIter __last,
228 		   _Integer __count, _UnaryPredicate __unary_pred,
229 		   std::random_access_iterator_tag)
230     {
231       typedef typename std::iterator_traits<_RandomAccessIter>::difference_type
232 	_DistanceType;
233 
234       _DistanceType __tailSize = __last - __first;
235       _DistanceType __remainder = __count;
236 
237       while (__remainder <= __tailSize) // the main loop...
238 	{
239 	  __first += __remainder;
240 	  __tailSize -= __remainder;
241 	  // __first here is always pointing to one past the last element of
242 	  // next possible match.
243 	  _RandomAccessIter __backTrack = __first;
244 	  while (__unary_pred(--__backTrack))
245 	    {
246 	      if (--__remainder == 0)
247 		return (__first - __count); // Success
248 	    }
249 	  __remainder = __count + 1 - (__first - __backTrack);
250 	}
251       return __last; // Failure
252     }
253 
254   template<typename _ForwardIterator, typename _Integer,
255 	   typename _UnaryPredicate>
256     _GLIBCXX20_CONSTEXPR
257     _ForwardIterator
258     __search_n(_ForwardIterator __first, _ForwardIterator __last,
259 	       _Integer __count,
260 	       _UnaryPredicate __unary_pred)
261     {
262       if (__count <= 0)
263 	return __first;
264 
265       if (__count == 1)
266 	return std::__find_if(__first, __last, __unary_pred);
267 
268       return std::__search_n_aux(__first, __last, __count, __unary_pred,
269 				 std::__iterator_category(__first));
270     }
271 
272   // find_end for forward iterators.
273   template<typename _ForwardIterator1, typename _ForwardIterator2,
274 	   typename _BinaryPredicate>
275     _GLIBCXX20_CONSTEXPR
276     _ForwardIterator1
277     __find_end(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
278 	       _ForwardIterator2 __first2, _ForwardIterator2 __last2,
279 	       forward_iterator_tag, forward_iterator_tag,
280 	       _BinaryPredicate __comp)
281     {
282       if (__first2 == __last2)
283 	return __last1;
284 
285       _ForwardIterator1 __result = __last1;
286       while (1)
287 	{
288 	  _ForwardIterator1 __new_result
289 	    = std::__search(__first1, __last1, __first2, __last2, __comp);
290 	  if (__new_result == __last1)
291 	    return __result;
292 	  else
293 	    {
294 	      __result = __new_result;
295 	      __first1 = __new_result;
296 	      ++__first1;
297 	    }
298 	}
299     }
300 
301   // find_end for bidirectional iterators (much faster).
302   template<typename _BidirectionalIterator1, typename _BidirectionalIterator2,
303 	   typename _BinaryPredicate>
304     _GLIBCXX20_CONSTEXPR
305     _BidirectionalIterator1
306     __find_end(_BidirectionalIterator1 __first1,
307 	       _BidirectionalIterator1 __last1,
308 	       _BidirectionalIterator2 __first2,
309 	       _BidirectionalIterator2 __last2,
310 	       bidirectional_iterator_tag, bidirectional_iterator_tag,
311 	       _BinaryPredicate __comp)
312     {
313       // concept requirements
314       __glibcxx_function_requires(_BidirectionalIteratorConcept<
315 				  _BidirectionalIterator1>)
316       __glibcxx_function_requires(_BidirectionalIteratorConcept<
317 				  _BidirectionalIterator2>)
318 
319       typedef reverse_iterator<_BidirectionalIterator1> _RevIterator1;
320       typedef reverse_iterator<_BidirectionalIterator2> _RevIterator2;
321 
322       _RevIterator1 __rlast1(__first1);
323       _RevIterator2 __rlast2(__first2);
324       _RevIterator1 __rresult = std::__search(_RevIterator1(__last1), __rlast1,
325 					      _RevIterator2(__last2), __rlast2,
326 					      __comp);
327 
328       if (__rresult == __rlast1)
329 	return __last1;
330       else
331 	{
332 	  _BidirectionalIterator1 __result = __rresult.base();
333 	  std::advance(__result, -std::distance(__first2, __last2));
334 	  return __result;
335 	}
336     }
337 
338   /**
339    *  @brief  Find last matching subsequence in a sequence.
340    *  @ingroup non_mutating_algorithms
341    *  @param  __first1  Start of range to search.
342    *  @param  __last1   End of range to search.
343    *  @param  __first2  Start of sequence to match.
344    *  @param  __last2   End of sequence to match.
345    *  @return   The last iterator @c i in the range
346    *  @p [__first1,__last1-(__last2-__first2)) such that @c *(i+N) ==
347    *  @p *(__first2+N) for each @c N in the range @p
348    *  [0,__last2-__first2), or @p __last1 if no such iterator exists.
349    *
350    *  Searches the range @p [__first1,__last1) for a sub-sequence that
351    *  compares equal value-by-value with the sequence given by @p
352    *  [__first2,__last2) and returns an iterator to the __first
353    *  element of the sub-sequence, or @p __last1 if the sub-sequence
354    *  is not found.  The sub-sequence will be the last such
355    *  subsequence contained in [__first1,__last1).
356    *
357    *  Because the sub-sequence must lie completely within the range @p
358    *  [__first1,__last1) it must start at a position less than @p
359    *  __last1-(__last2-__first2) where @p __last2-__first2 is the
360    *  length of the sub-sequence.  This means that the returned
361    *  iterator @c i will be in the range @p
362    *  [__first1,__last1-(__last2-__first2))
363   */
364   template<typename _ForwardIterator1, typename _ForwardIterator2>
365     _GLIBCXX20_CONSTEXPR
366     inline _ForwardIterator1
367     find_end(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
368 	     _ForwardIterator2 __first2, _ForwardIterator2 __last2)
369     {
370       // concept requirements
371       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator1>)
372       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator2>)
373       __glibcxx_function_requires(_EqualOpConcept<
374 	    typename iterator_traits<_ForwardIterator1>::value_type,
375 	    typename iterator_traits<_ForwardIterator2>::value_type>)
376       __glibcxx_requires_valid_range(__first1, __last1);
377       __glibcxx_requires_valid_range(__first2, __last2);
378 
379       return std::__find_end(__first1, __last1, __first2, __last2,
380 			     std::__iterator_category(__first1),
381 			     std::__iterator_category(__first2),
382 			     __gnu_cxx::__ops::__iter_equal_to_iter());
383     }
384 
385   /**
386    *  @brief  Find last matching subsequence in a sequence using a predicate.
387    *  @ingroup non_mutating_algorithms
388    *  @param  __first1  Start of range to search.
389    *  @param  __last1   End of range to search.
390    *  @param  __first2  Start of sequence to match.
391    *  @param  __last2   End of sequence to match.
392    *  @param  __comp    The predicate to use.
393    *  @return The last iterator @c i in the range @p
394    *  [__first1,__last1-(__last2-__first2)) such that @c
395    *  predicate(*(i+N), @p (__first2+N)) is true for each @c N in the
396    *  range @p [0,__last2-__first2), or @p __last1 if no such iterator
397    *  exists.
398    *
399    *  Searches the range @p [__first1,__last1) for a sub-sequence that
400    *  compares equal value-by-value with the sequence given by @p
401    *  [__first2,__last2) using comp as a predicate and returns an
402    *  iterator to the first element of the sub-sequence, or @p __last1
403    *  if the sub-sequence is not found.  The sub-sequence will be the
404    *  last such subsequence contained in [__first,__last1).
405    *
406    *  Because the sub-sequence must lie completely within the range @p
407    *  [__first1,__last1) it must start at a position less than @p
408    *  __last1-(__last2-__first2) where @p __last2-__first2 is the
409    *  length of the sub-sequence.  This means that the returned
410    *  iterator @c i will be in the range @p
411    *  [__first1,__last1-(__last2-__first2))
412   */
413   template<typename _ForwardIterator1, typename _ForwardIterator2,
414 	   typename _BinaryPredicate>
415     _GLIBCXX20_CONSTEXPR
416     inline _ForwardIterator1
417     find_end(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
418 	     _ForwardIterator2 __first2, _ForwardIterator2 __last2,
419 	     _BinaryPredicate __comp)
420     {
421       // concept requirements
422       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator1>)
423       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator2>)
424       __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
425 	    typename iterator_traits<_ForwardIterator1>::value_type,
426 	    typename iterator_traits<_ForwardIterator2>::value_type>)
427       __glibcxx_requires_valid_range(__first1, __last1);
428       __glibcxx_requires_valid_range(__first2, __last2);
429 
430       return std::__find_end(__first1, __last1, __first2, __last2,
431 			     std::__iterator_category(__first1),
432 			     std::__iterator_category(__first2),
433 			     __gnu_cxx::__ops::__iter_comp_iter(__comp));
434     }
435 
436 #if __cplusplus >= 201103L
437   /**
438    *  @brief  Checks that a predicate is true for all the elements
439    *          of a sequence.
440    *  @ingroup non_mutating_algorithms
441    *  @param  __first   An input iterator.
442    *  @param  __last    An input iterator.
443    *  @param  __pred    A predicate.
444    *  @return  True if the check is true, false otherwise.
445    *
446    *  Returns true if @p __pred is true for each element in the range
447    *  @p [__first,__last), and false otherwise.
448   */
449   template<typename _InputIterator, typename _Predicate>
450     _GLIBCXX20_CONSTEXPR
451     inline bool
452     all_of(_InputIterator __first, _InputIterator __last, _Predicate __pred)
453     { return __last == std::find_if_not(__first, __last, __pred); }
454 
455   /**
456    *  @brief  Checks that a predicate is false for all the elements
457    *          of a sequence.
458    *  @ingroup non_mutating_algorithms
459    *  @param  __first   An input iterator.
460    *  @param  __last    An input iterator.
461    *  @param  __pred    A predicate.
462    *  @return  True if the check is true, false otherwise.
463    *
464    *  Returns true if @p __pred is false for each element in the range
465    *  @p [__first,__last), and false otherwise.
466   */
467   template<typename _InputIterator, typename _Predicate>
468     _GLIBCXX20_CONSTEXPR
469     inline bool
470     none_of(_InputIterator __first, _InputIterator __last, _Predicate __pred)
471     { return __last == _GLIBCXX_STD_A::find_if(__first, __last, __pred); }
472 
473   /**
474    *  @brief  Checks that a predicate is true for at least one element
475    *          of a sequence.
476    *  @ingroup non_mutating_algorithms
477    *  @param  __first   An input iterator.
478    *  @param  __last    An input iterator.
479    *  @param  __pred    A predicate.
480    *  @return  True if the check is true, false otherwise.
481    *
482    *  Returns true if an element exists in the range @p
483    *  [__first,__last) such that @p __pred is true, and false
484    *  otherwise.
485   */
486   template<typename _InputIterator, typename _Predicate>
487     _GLIBCXX20_CONSTEXPR
488     inline bool
489     any_of(_InputIterator __first, _InputIterator __last, _Predicate __pred)
490     { return !std::none_of(__first, __last, __pred); }
491 
492   /**
493    *  @brief  Find the first element in a sequence for which a
494    *          predicate is false.
495    *  @ingroup non_mutating_algorithms
496    *  @param  __first  An input iterator.
497    *  @param  __last   An input iterator.
498    *  @param  __pred   A predicate.
499    *  @return   The first iterator @c i in the range @p [__first,__last)
500    *  such that @p __pred(*i) is false, or @p __last if no such iterator exists.
501   */
502   template<typename _InputIterator, typename _Predicate>
503     _GLIBCXX20_CONSTEXPR
504     inline _InputIterator
505     find_if_not(_InputIterator __first, _InputIterator __last,
506 		_Predicate __pred)
507     {
508       // concept requirements
509       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
510       __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
511 	      typename iterator_traits<_InputIterator>::value_type>)
512       __glibcxx_requires_valid_range(__first, __last);
513       return std::__find_if_not(__first, __last,
514 				__gnu_cxx::__ops::__pred_iter(__pred));
515     }
516 
517   /**
518    *  @brief  Checks whether the sequence is partitioned.
519    *  @ingroup mutating_algorithms
520    *  @param  __first  An input iterator.
521    *  @param  __last   An input iterator.
522    *  @param  __pred   A predicate.
523    *  @return  True if the range @p [__first,__last) is partioned by @p __pred,
524    *  i.e. if all elements that satisfy @p __pred appear before those that
525    *  do not.
526   */
527   template<typename _InputIterator, typename _Predicate>
528     _GLIBCXX20_CONSTEXPR
529     inline bool
530     is_partitioned(_InputIterator __first, _InputIterator __last,
531 		   _Predicate __pred)
532     {
533       __first = std::find_if_not(__first, __last, __pred);
534       if (__first == __last)
535 	return true;
536       ++__first;
537       return std::none_of(__first, __last, __pred);
538     }
539 
540   /**
541    *  @brief  Find the partition point of a partitioned range.
542    *  @ingroup mutating_algorithms
543    *  @param  __first   An iterator.
544    *  @param  __last    Another iterator.
545    *  @param  __pred    A predicate.
546    *  @return  An iterator @p mid such that @p all_of(__first, mid, __pred)
547    *           and @p none_of(mid, __last, __pred) are both true.
548   */
549   template<typename _ForwardIterator, typename _Predicate>
550     _GLIBCXX20_CONSTEXPR
551     _ForwardIterator
552     partition_point(_ForwardIterator __first, _ForwardIterator __last,
553 		    _Predicate __pred)
554     {
555       // concept requirements
556       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
557       __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
558 	      typename iterator_traits<_ForwardIterator>::value_type>)
559 
560       // A specific debug-mode test will be necessary...
561       __glibcxx_requires_valid_range(__first, __last);
562 
563       typedef typename iterator_traits<_ForwardIterator>::difference_type
564 	_DistanceType;
565 
566       _DistanceType __len = std::distance(__first, __last);
567 
568       while (__len > 0)
569 	{
570 	  _DistanceType __half = __len >> 1;
571 	  _ForwardIterator __middle = __first;
572 	  std::advance(__middle, __half);
573 	  if (__pred(*__middle))
574 	    {
575 	      __first = __middle;
576 	      ++__first;
577 	      __len = __len - __half - 1;
578 	    }
579 	  else
580 	    __len = __half;
581 	}
582       return __first;
583     }
584 #endif
585 
586   template<typename _InputIterator, typename _OutputIterator,
587 	   typename _Predicate>
588     _GLIBCXX20_CONSTEXPR
589     _OutputIterator
590     __remove_copy_if(_InputIterator __first, _InputIterator __last,
591 		     _OutputIterator __result, _Predicate __pred)
592     {
593       for (; __first != __last; ++__first)
594 	if (!__pred(__first))
595 	  {
596 	    *__result = *__first;
597 	    ++__result;
598 	  }
599       return __result;
600     }
601 
602   /**
603    *  @brief Copy a sequence, removing elements of a given value.
604    *  @ingroup mutating_algorithms
605    *  @param  __first   An input iterator.
606    *  @param  __last    An input iterator.
607    *  @param  __result  An output iterator.
608    *  @param  __value   The value to be removed.
609    *  @return   An iterator designating the end of the resulting sequence.
610    *
611    *  Copies each element in the range @p [__first,__last) not equal
612    *  to @p __value to the range beginning at @p __result.
613    *  remove_copy() is stable, so the relative order of elements that
614    *  are copied is unchanged.
615   */
616   template<typename _InputIterator, typename _OutputIterator, typename _Tp>
617     _GLIBCXX20_CONSTEXPR
618     inline _OutputIterator
619     remove_copy(_InputIterator __first, _InputIterator __last,
620 		_OutputIterator __result, const _Tp& __value)
621     {
622       // concept requirements
623       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
624       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
625 	    typename iterator_traits<_InputIterator>::value_type>)
626       __glibcxx_function_requires(_EqualOpConcept<
627 	    typename iterator_traits<_InputIterator>::value_type, _Tp>)
628       __glibcxx_requires_valid_range(__first, __last);
629 
630       return std::__remove_copy_if(__first, __last, __result,
631 	__gnu_cxx::__ops::__iter_equals_val(__value));
632     }
633 
634   /**
635    *  @brief Copy a sequence, removing elements for which a predicate is true.
636    *  @ingroup mutating_algorithms
637    *  @param  __first   An input iterator.
638    *  @param  __last    An input iterator.
639    *  @param  __result  An output iterator.
640    *  @param  __pred    A predicate.
641    *  @return   An iterator designating the end of the resulting sequence.
642    *
643    *  Copies each element in the range @p [__first,__last) for which
644    *  @p __pred returns false to the range beginning at @p __result.
645    *
646    *  remove_copy_if() is stable, so the relative order of elements that are
647    *  copied is unchanged.
648   */
649   template<typename _InputIterator, typename _OutputIterator,
650 	   typename _Predicate>
651     _GLIBCXX20_CONSTEXPR
652     inline _OutputIterator
653     remove_copy_if(_InputIterator __first, _InputIterator __last,
654 		   _OutputIterator __result, _Predicate __pred)
655     {
656       // concept requirements
657       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
658       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
659 	    typename iterator_traits<_InputIterator>::value_type>)
660       __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
661 	    typename iterator_traits<_InputIterator>::value_type>)
662       __glibcxx_requires_valid_range(__first, __last);
663 
664       return std::__remove_copy_if(__first, __last, __result,
665 				   __gnu_cxx::__ops::__pred_iter(__pred));
666     }
667 
668 #if __cplusplus >= 201103L
669   /**
670    *  @brief Copy the elements of a sequence for which a predicate is true.
671    *  @ingroup mutating_algorithms
672    *  @param  __first   An input iterator.
673    *  @param  __last    An input iterator.
674    *  @param  __result  An output iterator.
675    *  @param  __pred    A predicate.
676    *  @return   An iterator designating the end of the resulting sequence.
677    *
678    *  Copies each element in the range @p [__first,__last) for which
679    *  @p __pred returns true to the range beginning at @p __result.
680    *
681    *  copy_if() is stable, so the relative order of elements that are
682    *  copied is unchanged.
683   */
684   template<typename _InputIterator, typename _OutputIterator,
685 	   typename _Predicate>
686     _GLIBCXX20_CONSTEXPR
687     _OutputIterator
688     copy_if(_InputIterator __first, _InputIterator __last,
689 	    _OutputIterator __result, _Predicate __pred)
690     {
691       // concept requirements
692       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
693       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
694 	    typename iterator_traits<_InputIterator>::value_type>)
695       __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
696 	    typename iterator_traits<_InputIterator>::value_type>)
697       __glibcxx_requires_valid_range(__first, __last);
698 
699       for (; __first != __last; ++__first)
700 	if (__pred(*__first))
701 	  {
702 	    *__result = *__first;
703 	    ++__result;
704 	  }
705       return __result;
706     }
707 
708   template<typename _InputIterator, typename _Size, typename _OutputIterator>
709     _GLIBCXX20_CONSTEXPR
710     _OutputIterator
711     __copy_n_a(_InputIterator __first, _Size __n, _OutputIterator __result)
712     {
713       if (__n > 0)
714 	{
715 	  while (true)
716 	    {
717 	      *__result = *__first;
718 	      ++__result;
719 	      if (--__n > 0)
720 		++__first;
721 	      else
722 		break;
723 	    }
724 	}
725       return __result;
726     }
727 
728   template<typename _CharT, typename _Size>
729     __enable_if_t<__is_char<_CharT>::__value, _CharT*>
730     __copy_n_a(istreambuf_iterator<_CharT, char_traits<_CharT>>,
731 	       _Size, _CharT*);
732 
733   template<typename _InputIterator, typename _Size, typename _OutputIterator>
734     _GLIBCXX20_CONSTEXPR
735     _OutputIterator
736     __copy_n(_InputIterator __first, _Size __n,
737 	     _OutputIterator __result, input_iterator_tag)
738     {
739       return std::__niter_wrap(__result,
740 			       __copy_n_a(__first, __n,
741 					  std::__niter_base(__result)));
742     }
743 
744   template<typename _RandomAccessIterator, typename _Size,
745 	   typename _OutputIterator>
746     _GLIBCXX20_CONSTEXPR
747     inline _OutputIterator
748     __copy_n(_RandomAccessIterator __first, _Size __n,
749 	     _OutputIterator __result, random_access_iterator_tag)
750     { return std::copy(__first, __first + __n, __result); }
751 
752   /**
753    *  @brief Copies the range [first,first+n) into [result,result+n).
754    *  @ingroup mutating_algorithms
755    *  @param  __first  An input iterator.
756    *  @param  __n      The number of elements to copy.
757    *  @param  __result An output iterator.
758    *  @return  result+n.
759    *
760    *  This inline function will boil down to a call to @c memmove whenever
761    *  possible.  Failing that, if random access iterators are passed, then the
762    *  loop count will be known (and therefore a candidate for compiler
763    *  optimizations such as unrolling).
764   */
765   template<typename _InputIterator, typename _Size, typename _OutputIterator>
766     _GLIBCXX20_CONSTEXPR
767     inline _OutputIterator
768     copy_n(_InputIterator __first, _Size __n, _OutputIterator __result)
769     {
770       // concept requirements
771       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
772       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
773 	    typename iterator_traits<_InputIterator>::value_type>)
774 
775       const auto __n2 = std::__size_to_integer(__n);
776       if (__n2 <= 0)
777 	return __result;
778 
779       __glibcxx_requires_can_increment(__first, __n2);
780       __glibcxx_requires_can_increment(__result, __n2);
781 
782       return std::__copy_n(__first, __n2, __result,
783 			   std::__iterator_category(__first));
784     }
785 
786   /**
787    *  @brief Copy the elements of a sequence to separate output sequences
788    *         depending on the truth value of a predicate.
789    *  @ingroup mutating_algorithms
790    *  @param  __first   An input iterator.
791    *  @param  __last    An input iterator.
792    *  @param  __out_true   An output iterator.
793    *  @param  __out_false  An output iterator.
794    *  @param  __pred    A predicate.
795    *  @return   A pair designating the ends of the resulting sequences.
796    *
797    *  Copies each element in the range @p [__first,__last) for which
798    *  @p __pred returns true to the range beginning at @p out_true
799    *  and each element for which @p __pred returns false to @p __out_false.
800   */
801   template<typename _InputIterator, typename _OutputIterator1,
802 	   typename _OutputIterator2, typename _Predicate>
803     _GLIBCXX20_CONSTEXPR
804     pair<_OutputIterator1, _OutputIterator2>
805     partition_copy(_InputIterator __first, _InputIterator __last,
806 		   _OutputIterator1 __out_true, _OutputIterator2 __out_false,
807 		   _Predicate __pred)
808     {
809       // concept requirements
810       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
811       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator1,
812 	    typename iterator_traits<_InputIterator>::value_type>)
813       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator2,
814 	    typename iterator_traits<_InputIterator>::value_type>)
815       __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
816 	    typename iterator_traits<_InputIterator>::value_type>)
817       __glibcxx_requires_valid_range(__first, __last);
818 
819       for (; __first != __last; ++__first)
820 	if (__pred(*__first))
821 	  {
822 	    *__out_true = *__first;
823 	    ++__out_true;
824 	  }
825 	else
826 	  {
827 	    *__out_false = *__first;
828 	    ++__out_false;
829 	  }
830 
831       return pair<_OutputIterator1, _OutputIterator2>(__out_true, __out_false);
832     }
833 #endif // C++11
834 
835   template<typename _ForwardIterator, typename _Predicate>
836     _GLIBCXX20_CONSTEXPR
837     _ForwardIterator
838     __remove_if(_ForwardIterator __first, _ForwardIterator __last,
839 		_Predicate __pred)
840     {
841       __first = std::__find_if(__first, __last, __pred);
842       if (__first == __last)
843 	return __first;
844       _ForwardIterator __result = __first;
845       ++__first;
846       for (; __first != __last; ++__first)
847 	if (!__pred(__first))
848 	  {
849 	    *__result = _GLIBCXX_MOVE(*__first);
850 	    ++__result;
851 	  }
852       return __result;
853     }
854 
855   /**
856    *  @brief Remove elements from a sequence.
857    *  @ingroup mutating_algorithms
858    *  @param  __first  An input iterator.
859    *  @param  __last   An input iterator.
860    *  @param  __value  The value to be removed.
861    *  @return   An iterator designating the end of the resulting sequence.
862    *
863    *  All elements equal to @p __value are removed from the range
864    *  @p [__first,__last).
865    *
866    *  remove() is stable, so the relative order of elements that are
867    *  not removed is unchanged.
868    *
869    *  Elements between the end of the resulting sequence and @p __last
870    *  are still present, but their value is unspecified.
871   */
872   template<typename _ForwardIterator, typename _Tp>
873     _GLIBCXX20_CONSTEXPR
874     inline _ForwardIterator
875     remove(_ForwardIterator __first, _ForwardIterator __last,
876 	   const _Tp& __value)
877     {
878       // concept requirements
879       __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
880 				  _ForwardIterator>)
881       __glibcxx_function_requires(_EqualOpConcept<
882 	    typename iterator_traits<_ForwardIterator>::value_type, _Tp>)
883       __glibcxx_requires_valid_range(__first, __last);
884 
885       return std::__remove_if(__first, __last,
886 		__gnu_cxx::__ops::__iter_equals_val(__value));
887     }
888 
889   /**
890    *  @brief Remove elements from a sequence using a predicate.
891    *  @ingroup mutating_algorithms
892    *  @param  __first  A forward iterator.
893    *  @param  __last   A forward iterator.
894    *  @param  __pred   A predicate.
895    *  @return   An iterator designating the end of the resulting sequence.
896    *
897    *  All elements for which @p __pred returns true are removed from the range
898    *  @p [__first,__last).
899    *
900    *  remove_if() is stable, so the relative order of elements that are
901    *  not removed is unchanged.
902    *
903    *  Elements between the end of the resulting sequence and @p __last
904    *  are still present, but their value is unspecified.
905   */
906   template<typename _ForwardIterator, typename _Predicate>
907     _GLIBCXX20_CONSTEXPR
908     inline _ForwardIterator
909     remove_if(_ForwardIterator __first, _ForwardIterator __last,
910 	      _Predicate __pred)
911     {
912       // concept requirements
913       __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
914 				  _ForwardIterator>)
915       __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
916 	    typename iterator_traits<_ForwardIterator>::value_type>)
917       __glibcxx_requires_valid_range(__first, __last);
918 
919       return std::__remove_if(__first, __last,
920 			      __gnu_cxx::__ops::__pred_iter(__pred));
921     }
922 
923   template<typename _ForwardIterator, typename _BinaryPredicate>
924     _GLIBCXX20_CONSTEXPR
925     _ForwardIterator
926     __adjacent_find(_ForwardIterator __first, _ForwardIterator __last,
927 		    _BinaryPredicate __binary_pred)
928     {
929       if (__first == __last)
930 	return __last;
931       _ForwardIterator __next = __first;
932       while (++__next != __last)
933 	{
934 	  if (__binary_pred(__first, __next))
935 	    return __first;
936 	  __first = __next;
937 	}
938       return __last;
939     }
940 
941   template<typename _ForwardIterator, typename _BinaryPredicate>
942     _GLIBCXX20_CONSTEXPR
943     _ForwardIterator
944     __unique(_ForwardIterator __first, _ForwardIterator __last,
945 	     _BinaryPredicate __binary_pred)
946     {
947       // Skip the beginning, if already unique.
948       __first = std::__adjacent_find(__first, __last, __binary_pred);
949       if (__first == __last)
950 	return __last;
951 
952       // Do the real copy work.
953       _ForwardIterator __dest = __first;
954       ++__first;
955       while (++__first != __last)
956 	if (!__binary_pred(__dest, __first))
957 	  *++__dest = _GLIBCXX_MOVE(*__first);
958       return ++__dest;
959     }
960 
961   /**
962    *  @brief Remove consecutive duplicate values from a sequence.
963    *  @ingroup mutating_algorithms
964    *  @param  __first  A forward iterator.
965    *  @param  __last   A forward iterator.
966    *  @return  An iterator designating the end of the resulting sequence.
967    *
968    *  Removes all but the first element from each group of consecutive
969    *  values that compare equal.
970    *  unique() is stable, so the relative order of elements that are
971    *  not removed is unchanged.
972    *  Elements between the end of the resulting sequence and @p __last
973    *  are still present, but their value is unspecified.
974   */
975   template<typename _ForwardIterator>
976     _GLIBCXX20_CONSTEXPR
977     inline _ForwardIterator
978     unique(_ForwardIterator __first, _ForwardIterator __last)
979     {
980       // concept requirements
981       __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
982 				  _ForwardIterator>)
983       __glibcxx_function_requires(_EqualityComparableConcept<
984 		     typename iterator_traits<_ForwardIterator>::value_type>)
985       __glibcxx_requires_valid_range(__first, __last);
986 
987       return std::__unique(__first, __last,
988 			   __gnu_cxx::__ops::__iter_equal_to_iter());
989     }
990 
991   /**
992    *  @brief Remove consecutive values from a sequence using a predicate.
993    *  @ingroup mutating_algorithms
994    *  @param  __first        A forward iterator.
995    *  @param  __last         A forward iterator.
996    *  @param  __binary_pred  A binary predicate.
997    *  @return  An iterator designating the end of the resulting sequence.
998    *
999    *  Removes all but the first element from each group of consecutive
1000    *  values for which @p __binary_pred returns true.
1001    *  unique() is stable, so the relative order of elements that are
1002    *  not removed is unchanged.
1003    *  Elements between the end of the resulting sequence and @p __last
1004    *  are still present, but their value is unspecified.
1005   */
1006   template<typename _ForwardIterator, typename _BinaryPredicate>
1007     _GLIBCXX20_CONSTEXPR
1008     inline _ForwardIterator
1009     unique(_ForwardIterator __first, _ForwardIterator __last,
1010 	   _BinaryPredicate __binary_pred)
1011     {
1012       // concept requirements
1013       __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
1014 				  _ForwardIterator>)
1015       __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
1016 		typename iterator_traits<_ForwardIterator>::value_type,
1017 		typename iterator_traits<_ForwardIterator>::value_type>)
1018       __glibcxx_requires_valid_range(__first, __last);
1019 
1020       return std::__unique(__first, __last,
1021 			   __gnu_cxx::__ops::__iter_comp_iter(__binary_pred));
1022     }
1023 
1024   /**
1025    *  This is an uglified
1026    *  unique_copy(_InputIterator, _InputIterator, _OutputIterator,
1027    *              _BinaryPredicate)
1028    *  overloaded for forward iterators and output iterator as result.
1029   */
1030   template<typename _ForwardIterator, typename _OutputIterator,
1031 	   typename _BinaryPredicate>
1032     _GLIBCXX20_CONSTEXPR
1033     _OutputIterator
1034     __unique_copy(_ForwardIterator __first, _ForwardIterator __last,
1035 		  _OutputIterator __result, _BinaryPredicate __binary_pred,
1036 		  forward_iterator_tag, output_iterator_tag)
1037     {
1038       // concept requirements -- iterators already checked
1039       __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
1040 	  typename iterator_traits<_ForwardIterator>::value_type,
1041 	  typename iterator_traits<_ForwardIterator>::value_type>)
1042 
1043       _ForwardIterator __next = __first;
1044       *__result = *__first;
1045       while (++__next != __last)
1046 	if (!__binary_pred(__first, __next))
1047 	  {
1048 	    __first = __next;
1049 	    *++__result = *__first;
1050 	  }
1051       return ++__result;
1052     }
1053 
1054   /**
1055    *  This is an uglified
1056    *  unique_copy(_InputIterator, _InputIterator, _OutputIterator,
1057    *              _BinaryPredicate)
1058    *  overloaded for input iterators and output iterator as result.
1059   */
1060   template<typename _InputIterator, typename _OutputIterator,
1061 	   typename _BinaryPredicate>
1062     _GLIBCXX20_CONSTEXPR
1063     _OutputIterator
1064     __unique_copy(_InputIterator __first, _InputIterator __last,
1065 		  _OutputIterator __result, _BinaryPredicate __binary_pred,
1066 		  input_iterator_tag, output_iterator_tag)
1067     {
1068       // concept requirements -- iterators already checked
1069       __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
1070 	  typename iterator_traits<_InputIterator>::value_type,
1071 	  typename iterator_traits<_InputIterator>::value_type>)
1072 
1073       typename iterator_traits<_InputIterator>::value_type __value = *__first;
1074       __decltype(__gnu_cxx::__ops::__iter_comp_val(__binary_pred))
1075 	__rebound_pred
1076 	= __gnu_cxx::__ops::__iter_comp_val(__binary_pred);
1077       *__result = __value;
1078       while (++__first != __last)
1079 	if (!__rebound_pred(__first, __value))
1080 	  {
1081 	    __value = *__first;
1082 	    *++__result = __value;
1083 	  }
1084       return ++__result;
1085     }
1086 
1087   /**
1088    *  This is an uglified
1089    *  unique_copy(_InputIterator, _InputIterator, _OutputIterator,
1090    *              _BinaryPredicate)
1091    *  overloaded for input iterators and forward iterator as result.
1092   */
1093   template<typename _InputIterator, typename _ForwardIterator,
1094 	   typename _BinaryPredicate>
1095     _GLIBCXX20_CONSTEXPR
1096     _ForwardIterator
1097     __unique_copy(_InputIterator __first, _InputIterator __last,
1098 		  _ForwardIterator __result, _BinaryPredicate __binary_pred,
1099 		  input_iterator_tag, forward_iterator_tag)
1100     {
1101       // concept requirements -- iterators already checked
1102       __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
1103 	  typename iterator_traits<_ForwardIterator>::value_type,
1104 	  typename iterator_traits<_InputIterator>::value_type>)
1105       *__result = *__first;
1106       while (++__first != __last)
1107 	if (!__binary_pred(__result, __first))
1108 	  *++__result = *__first;
1109       return ++__result;
1110     }
1111 
1112   /**
1113    *  This is an uglified reverse(_BidirectionalIterator,
1114    *                              _BidirectionalIterator)
1115    *  overloaded for bidirectional iterators.
1116   */
1117   template<typename _BidirectionalIterator>
1118     _GLIBCXX20_CONSTEXPR
1119     void
1120     __reverse(_BidirectionalIterator __first, _BidirectionalIterator __last,
1121 	      bidirectional_iterator_tag)
1122     {
1123       while (true)
1124 	if (__first == __last || __first == --__last)
1125 	  return;
1126 	else
1127 	  {
1128 	    std::iter_swap(__first, __last);
1129 	    ++__first;
1130 	  }
1131     }
1132 
1133   /**
1134    *  This is an uglified reverse(_BidirectionalIterator,
1135    *                              _BidirectionalIterator)
1136    *  overloaded for random access iterators.
1137   */
1138   template<typename _RandomAccessIterator>
1139     _GLIBCXX20_CONSTEXPR
1140     void
1141     __reverse(_RandomAccessIterator __first, _RandomAccessIterator __last,
1142 	      random_access_iterator_tag)
1143     {
1144       if (__first == __last)
1145 	return;
1146       --__last;
1147       while (__first < __last)
1148 	{
1149 	  std::iter_swap(__first, __last);
1150 	  ++__first;
1151 	  --__last;
1152 	}
1153     }
1154 
1155   /**
1156    *  @brief Reverse a sequence.
1157    *  @ingroup mutating_algorithms
1158    *  @param  __first  A bidirectional iterator.
1159    *  @param  __last   A bidirectional iterator.
1160    *  @return   reverse() returns no value.
1161    *
1162    *  Reverses the order of the elements in the range @p [__first,__last),
1163    *  so that the first element becomes the last etc.
1164    *  For every @c i such that @p 0<=i<=(__last-__first)/2), @p reverse()
1165    *  swaps @p *(__first+i) and @p *(__last-(i+1))
1166   */
1167   template<typename _BidirectionalIterator>
1168     _GLIBCXX20_CONSTEXPR
1169     inline void
1170     reverse(_BidirectionalIterator __first, _BidirectionalIterator __last)
1171     {
1172       // concept requirements
1173       __glibcxx_function_requires(_Mutable_BidirectionalIteratorConcept<
1174 				  _BidirectionalIterator>)
1175       __glibcxx_requires_valid_range(__first, __last);
1176       std::__reverse(__first, __last, std::__iterator_category(__first));
1177     }
1178 
1179   /**
1180    *  @brief Copy a sequence, reversing its elements.
1181    *  @ingroup mutating_algorithms
1182    *  @param  __first   A bidirectional iterator.
1183    *  @param  __last    A bidirectional iterator.
1184    *  @param  __result  An output iterator.
1185    *  @return  An iterator designating the end of the resulting sequence.
1186    *
1187    *  Copies the elements in the range @p [__first,__last) to the
1188    *  range @p [__result,__result+(__last-__first)) such that the
1189    *  order of the elements is reversed.  For every @c i such that @p
1190    *  0<=i<=(__last-__first), @p reverse_copy() performs the
1191    *  assignment @p *(__result+(__last-__first)-1-i) = *(__first+i).
1192    *  The ranges @p [__first,__last) and @p
1193    *  [__result,__result+(__last-__first)) must not overlap.
1194   */
1195   template<typename _BidirectionalIterator, typename _OutputIterator>
1196     _GLIBCXX20_CONSTEXPR
1197     _OutputIterator
1198     reverse_copy(_BidirectionalIterator __first, _BidirectionalIterator __last,
1199 		 _OutputIterator __result)
1200     {
1201       // concept requirements
1202       __glibcxx_function_requires(_BidirectionalIteratorConcept<
1203 				  _BidirectionalIterator>)
1204       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
1205 		typename iterator_traits<_BidirectionalIterator>::value_type>)
1206       __glibcxx_requires_valid_range(__first, __last);
1207 
1208       while (__first != __last)
1209 	{
1210 	  --__last;
1211 	  *__result = *__last;
1212 	  ++__result;
1213 	}
1214       return __result;
1215     }
1216 
1217   /**
1218    *  This is a helper function for the rotate algorithm specialized on RAIs.
1219    *  It returns the greatest common divisor of two integer values.
1220   */
1221   template<typename _EuclideanRingElement>
1222     _GLIBCXX20_CONSTEXPR
1223     _EuclideanRingElement
1224     __gcd(_EuclideanRingElement __m, _EuclideanRingElement __n)
1225     {
1226       while (__n != 0)
1227 	{
1228 	  _EuclideanRingElement __t = __m % __n;
1229 	  __m = __n;
1230 	  __n = __t;
1231 	}
1232       return __m;
1233     }
1234 
1235   inline namespace _V2
1236   {
1237 
1238   /// This is a helper function for the rotate algorithm.
1239   template<typename _ForwardIterator>
1240     _GLIBCXX20_CONSTEXPR
1241     _ForwardIterator
1242     __rotate(_ForwardIterator __first,
1243 	     _ForwardIterator __middle,
1244 	     _ForwardIterator __last,
1245 	     forward_iterator_tag)
1246     {
1247       if (__first == __middle)
1248 	return __last;
1249       else if (__last == __middle)
1250 	return __first;
1251 
1252       _ForwardIterator __first2 = __middle;
1253       do
1254 	{
1255 	  std::iter_swap(__first, __first2);
1256 	  ++__first;
1257 	  ++__first2;
1258 	  if (__first == __middle)
1259 	    __middle = __first2;
1260 	}
1261       while (__first2 != __last);
1262 
1263       _ForwardIterator __ret = __first;
1264 
1265       __first2 = __middle;
1266 
1267       while (__first2 != __last)
1268 	{
1269 	  std::iter_swap(__first, __first2);
1270 	  ++__first;
1271 	  ++__first2;
1272 	  if (__first == __middle)
1273 	    __middle = __first2;
1274 	  else if (__first2 == __last)
1275 	    __first2 = __middle;
1276 	}
1277       return __ret;
1278     }
1279 
1280    /// This is a helper function for the rotate algorithm.
1281   template<typename _BidirectionalIterator>
1282     _GLIBCXX20_CONSTEXPR
1283     _BidirectionalIterator
1284     __rotate(_BidirectionalIterator __first,
1285 	     _BidirectionalIterator __middle,
1286 	     _BidirectionalIterator __last,
1287 	      bidirectional_iterator_tag)
1288     {
1289       // concept requirements
1290       __glibcxx_function_requires(_Mutable_BidirectionalIteratorConcept<
1291 				  _BidirectionalIterator>)
1292 
1293       if (__first == __middle)
1294 	return __last;
1295       else if (__last == __middle)
1296 	return __first;
1297 
1298       std::__reverse(__first,  __middle, bidirectional_iterator_tag());
1299       std::__reverse(__middle, __last,   bidirectional_iterator_tag());
1300 
1301       while (__first != __middle && __middle != __last)
1302 	{
1303 	  std::iter_swap(__first, --__last);
1304 	  ++__first;
1305 	}
1306 
1307       if (__first == __middle)
1308 	{
1309 	  std::__reverse(__middle, __last,   bidirectional_iterator_tag());
1310 	  return __last;
1311 	}
1312       else
1313 	{
1314 	  std::__reverse(__first,  __middle, bidirectional_iterator_tag());
1315 	  return __first;
1316 	}
1317     }
1318 
1319   /// This is a helper function for the rotate algorithm.
1320   template<typename _RandomAccessIterator>
1321     _GLIBCXX20_CONSTEXPR
1322     _RandomAccessIterator
1323     __rotate(_RandomAccessIterator __first,
1324 	     _RandomAccessIterator __middle,
1325 	     _RandomAccessIterator __last,
1326 	     random_access_iterator_tag)
1327     {
1328       // concept requirements
1329       __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
1330 				  _RandomAccessIterator>)
1331 
1332       if (__first == __middle)
1333 	return __last;
1334       else if (__last == __middle)
1335 	return __first;
1336 
1337       typedef typename iterator_traits<_RandomAccessIterator>::difference_type
1338 	_Distance;
1339       typedef typename iterator_traits<_RandomAccessIterator>::value_type
1340 	_ValueType;
1341 
1342       _Distance __n = __last   - __first;
1343       _Distance __k = __middle - __first;
1344 
1345       if (__k == __n - __k)
1346 	{
1347 	  std::swap_ranges(__first, __middle, __middle);
1348 	  return __middle;
1349 	}
1350 
1351       _RandomAccessIterator __p = __first;
1352       _RandomAccessIterator __ret = __first + (__last - __middle);
1353 
1354       for (;;)
1355 	{
1356 	  if (__k < __n - __k)
1357 	    {
1358 	      if (__is_pod(_ValueType) && __k == 1)
1359 		{
1360 		  _ValueType __t = _GLIBCXX_MOVE(*__p);
1361 		  _GLIBCXX_MOVE3(__p + 1, __p + __n, __p);
1362 		  *(__p + __n - 1) = _GLIBCXX_MOVE(__t);
1363 		  return __ret;
1364 		}
1365 	      _RandomAccessIterator __q = __p + __k;
1366 	      for (_Distance __i = 0; __i < __n - __k; ++ __i)
1367 		{
1368 		  std::iter_swap(__p, __q);
1369 		  ++__p;
1370 		  ++__q;
1371 		}
1372 	      __n %= __k;
1373 	      if (__n == 0)
1374 		return __ret;
1375 	      std::swap(__n, __k);
1376 	      __k = __n - __k;
1377 	    }
1378 	  else
1379 	    {
1380 	      __k = __n - __k;
1381 	      if (__is_pod(_ValueType) && __k == 1)
1382 		{
1383 		  _ValueType __t = _GLIBCXX_MOVE(*(__p + __n - 1));
1384 		  _GLIBCXX_MOVE_BACKWARD3(__p, __p + __n - 1, __p + __n);
1385 		  *__p = _GLIBCXX_MOVE(__t);
1386 		  return __ret;
1387 		}
1388 	      _RandomAccessIterator __q = __p + __n;
1389 	      __p = __q - __k;
1390 	      for (_Distance __i = 0; __i < __n - __k; ++ __i)
1391 		{
1392 		  --__p;
1393 		  --__q;
1394 		  std::iter_swap(__p, __q);
1395 		}
1396 	      __n %= __k;
1397 	      if (__n == 0)
1398 		return __ret;
1399 	      std::swap(__n, __k);
1400 	    }
1401 	}
1402     }
1403 
1404    // _GLIBCXX_RESOLVE_LIB_DEFECTS
1405    // DR 488. rotate throws away useful information
1406   /**
1407    *  @brief Rotate the elements of a sequence.
1408    *  @ingroup mutating_algorithms
1409    *  @param  __first   A forward iterator.
1410    *  @param  __middle  A forward iterator.
1411    *  @param  __last    A forward iterator.
1412    *  @return  first + (last - middle).
1413    *
1414    *  Rotates the elements of the range @p [__first,__last) by
1415    *  @p (__middle - __first) positions so that the element at @p __middle
1416    *  is moved to @p __first, the element at @p __middle+1 is moved to
1417    *  @p __first+1 and so on for each element in the range
1418    *  @p [__first,__last).
1419    *
1420    *  This effectively swaps the ranges @p [__first,__middle) and
1421    *  @p [__middle,__last).
1422    *
1423    *  Performs
1424    *   @p *(__first+(n+(__last-__middle))%(__last-__first))=*(__first+n)
1425    *  for each @p n in the range @p [0,__last-__first).
1426   */
1427   template<typename _ForwardIterator>
1428     _GLIBCXX20_CONSTEXPR
1429     inline _ForwardIterator
1430     rotate(_ForwardIterator __first, _ForwardIterator __middle,
1431 	   _ForwardIterator __last)
1432     {
1433       // concept requirements
1434       __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
1435 				  _ForwardIterator>)
1436       __glibcxx_requires_valid_range(__first, __middle);
1437       __glibcxx_requires_valid_range(__middle, __last);
1438 
1439       return std::__rotate(__first, __middle, __last,
1440 			   std::__iterator_category(__first));
1441     }
1442 
1443   } // namespace _V2
1444 
1445   /**
1446    *  @brief Copy a sequence, rotating its elements.
1447    *  @ingroup mutating_algorithms
1448    *  @param  __first   A forward iterator.
1449    *  @param  __middle  A forward iterator.
1450    *  @param  __last    A forward iterator.
1451    *  @param  __result  An output iterator.
1452    *  @return   An iterator designating the end of the resulting sequence.
1453    *
1454    *  Copies the elements of the range @p [__first,__last) to the
1455    *  range beginning at @result, rotating the copied elements by
1456    *  @p (__middle-__first) positions so that the element at @p __middle
1457    *  is moved to @p __result, the element at @p __middle+1 is moved
1458    *  to @p __result+1 and so on for each element in the range @p
1459    *  [__first,__last).
1460    *
1461    *  Performs
1462    *  @p *(__result+(n+(__last-__middle))%(__last-__first))=*(__first+n)
1463    *  for each @p n in the range @p [0,__last-__first).
1464   */
1465   template<typename _ForwardIterator, typename _OutputIterator>
1466     _GLIBCXX20_CONSTEXPR
1467     inline _OutputIterator
1468     rotate_copy(_ForwardIterator __first, _ForwardIterator __middle,
1469 		_ForwardIterator __last, _OutputIterator __result)
1470     {
1471       // concept requirements
1472       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
1473       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
1474 		typename iterator_traits<_ForwardIterator>::value_type>)
1475       __glibcxx_requires_valid_range(__first, __middle);
1476       __glibcxx_requires_valid_range(__middle, __last);
1477 
1478       return std::copy(__first, __middle,
1479 		       std::copy(__middle, __last, __result));
1480     }
1481 
1482   /// This is a helper function...
1483   template<typename _ForwardIterator, typename _Predicate>
1484     _GLIBCXX20_CONSTEXPR
1485     _ForwardIterator
1486     __partition(_ForwardIterator __first, _ForwardIterator __last,
1487 		_Predicate __pred, forward_iterator_tag)
1488     {
1489       if (__first == __last)
1490 	return __first;
1491 
1492       while (__pred(*__first))
1493 	if (++__first == __last)
1494 	  return __first;
1495 
1496       _ForwardIterator __next = __first;
1497 
1498       while (++__next != __last)
1499 	if (__pred(*__next))
1500 	  {
1501 	    std::iter_swap(__first, __next);
1502 	    ++__first;
1503 	  }
1504 
1505       return __first;
1506     }
1507 
1508   /// This is a helper function...
1509   template<typename _BidirectionalIterator, typename _Predicate>
1510     _GLIBCXX20_CONSTEXPR
1511     _BidirectionalIterator
1512     __partition(_BidirectionalIterator __first, _BidirectionalIterator __last,
1513 		_Predicate __pred, bidirectional_iterator_tag)
1514     {
1515       while (true)
1516 	{
1517 	  while (true)
1518 	    if (__first == __last)
1519 	      return __first;
1520 	    else if (__pred(*__first))
1521 	      ++__first;
1522 	    else
1523 	      break;
1524 	  --__last;
1525 	  while (true)
1526 	    if (__first == __last)
1527 	      return __first;
1528 	    else if (!bool(__pred(*__last)))
1529 	      --__last;
1530 	    else
1531 	      break;
1532 	  std::iter_swap(__first, __last);
1533 	  ++__first;
1534 	}
1535     }
1536 
1537   // partition
1538 
1539   /// This is a helper function...
1540   /// Requires __first != __last and !__pred(__first)
1541   /// and __len == distance(__first, __last).
1542   ///
1543   /// !__pred(__first) allows us to guarantee that we don't
1544   /// move-assign an element onto itself.
1545   template<typename _ForwardIterator, typename _Pointer, typename _Predicate,
1546 	   typename _Distance>
1547     _ForwardIterator
1548     __stable_partition_adaptive(_ForwardIterator __first,
1549 				_ForwardIterator __last,
1550 				_Predicate __pred, _Distance __len,
1551 				_Pointer __buffer,
1552 				_Distance __buffer_size)
1553     {
1554       if (__len == 1)
1555 	return __first;
1556 
1557       if (__len <= __buffer_size)
1558 	{
1559 	  _ForwardIterator __result1 = __first;
1560 	  _Pointer __result2 = __buffer;
1561 
1562 	  // The precondition guarantees that !__pred(__first), so
1563 	  // move that element to the buffer before starting the loop.
1564 	  // This ensures that we only call __pred once per element.
1565 	  *__result2 = _GLIBCXX_MOVE(*__first);
1566 	  ++__result2;
1567 	  ++__first;
1568 	  for (; __first != __last; ++__first)
1569 	    if (__pred(__first))
1570 	      {
1571 		*__result1 = _GLIBCXX_MOVE(*__first);
1572 		++__result1;
1573 	      }
1574 	    else
1575 	      {
1576 		*__result2 = _GLIBCXX_MOVE(*__first);
1577 		++__result2;
1578 	      }
1579 
1580 	  _GLIBCXX_MOVE3(__buffer, __result2, __result1);
1581 	  return __result1;
1582 	}
1583 
1584       _ForwardIterator __middle = __first;
1585       std::advance(__middle, __len / 2);
1586       _ForwardIterator __left_split =
1587 	std::__stable_partition_adaptive(__first, __middle, __pred,
1588 					 __len / 2, __buffer,
1589 					 __buffer_size);
1590 
1591       // Advance past true-predicate values to satisfy this
1592       // function's preconditions.
1593       _Distance __right_len = __len - __len / 2;
1594       _ForwardIterator __right_split =
1595 	std::__find_if_not_n(__middle, __right_len, __pred);
1596 
1597       if (__right_len)
1598 	__right_split =
1599 	  std::__stable_partition_adaptive(__right_split, __last, __pred,
1600 					   __right_len,
1601 					   __buffer, __buffer_size);
1602 
1603       return std::rotate(__left_split, __middle, __right_split);
1604     }
1605 
1606   template<typename _ForwardIterator, typename _Predicate>
1607     _ForwardIterator
1608     __stable_partition(_ForwardIterator __first, _ForwardIterator __last,
1609 		       _Predicate __pred)
1610     {
1611       __first = std::__find_if_not(__first, __last, __pred);
1612 
1613       if (__first == __last)
1614 	return __first;
1615 
1616       typedef typename iterator_traits<_ForwardIterator>::value_type
1617 	_ValueType;
1618       typedef typename iterator_traits<_ForwardIterator>::difference_type
1619 	_DistanceType;
1620 
1621       _Temporary_buffer<_ForwardIterator, _ValueType>
1622 	__buf(__first, std::distance(__first, __last));
1623       return
1624 	std::__stable_partition_adaptive(__first, __last, __pred,
1625 					 _DistanceType(__buf.requested_size()),
1626 					 __buf.begin(),
1627 					 _DistanceType(__buf.size()));
1628     }
1629 
1630   /**
1631    *  @brief Move elements for which a predicate is true to the beginning
1632    *         of a sequence, preserving relative ordering.
1633    *  @ingroup mutating_algorithms
1634    *  @param  __first   A forward iterator.
1635    *  @param  __last    A forward iterator.
1636    *  @param  __pred    A predicate functor.
1637    *  @return  An iterator @p middle such that @p __pred(i) is true for each
1638    *  iterator @p i in the range @p [first,middle) and false for each @p i
1639    *  in the range @p [middle,last).
1640    *
1641    *  Performs the same function as @p partition() with the additional
1642    *  guarantee that the relative ordering of elements in each group is
1643    *  preserved, so any two elements @p x and @p y in the range
1644    *  @p [__first,__last) such that @p __pred(x)==__pred(y) will have the same
1645    *  relative ordering after calling @p stable_partition().
1646   */
1647   template<typename _ForwardIterator, typename _Predicate>
1648     inline _ForwardIterator
1649     stable_partition(_ForwardIterator __first, _ForwardIterator __last,
1650 		     _Predicate __pred)
1651     {
1652       // concept requirements
1653       __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
1654 				  _ForwardIterator>)
1655       __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
1656 	    typename iterator_traits<_ForwardIterator>::value_type>)
1657       __glibcxx_requires_valid_range(__first, __last);
1658 
1659       return std::__stable_partition(__first, __last,
1660 				     __gnu_cxx::__ops::__pred_iter(__pred));
1661     }
1662 
1663   /// This is a helper function for the sort routines.
1664   template<typename _RandomAccessIterator, typename _Compare>
1665     _GLIBCXX20_CONSTEXPR
1666     void
1667     __heap_select(_RandomAccessIterator __first,
1668 		  _RandomAccessIterator __middle,
1669 		  _RandomAccessIterator __last, _Compare __comp)
1670     {
1671       std::__make_heap(__first, __middle, __comp);
1672       for (_RandomAccessIterator __i = __middle; __i < __last; ++__i)
1673 	if (__comp(__i, __first))
1674 	  std::__pop_heap(__first, __middle, __i, __comp);
1675     }
1676 
1677   // partial_sort
1678 
1679   template<typename _InputIterator, typename _RandomAccessIterator,
1680 	   typename _Compare>
1681     _GLIBCXX20_CONSTEXPR
1682     _RandomAccessIterator
1683     __partial_sort_copy(_InputIterator __first, _InputIterator __last,
1684 			_RandomAccessIterator __result_first,
1685 			_RandomAccessIterator __result_last,
1686 			_Compare __comp)
1687     {
1688       typedef typename iterator_traits<_InputIterator>::value_type
1689 	_InputValueType;
1690       typedef iterator_traits<_RandomAccessIterator> _RItTraits;
1691       typedef typename _RItTraits::difference_type _DistanceType;
1692 
1693       if (__result_first == __result_last)
1694 	return __result_last;
1695       _RandomAccessIterator __result_real_last = __result_first;
1696       while (__first != __last && __result_real_last != __result_last)
1697 	{
1698 	  *__result_real_last = *__first;
1699 	  ++__result_real_last;
1700 	  ++__first;
1701 	}
1702 
1703       std::__make_heap(__result_first, __result_real_last, __comp);
1704       while (__first != __last)
1705 	{
1706 	  if (__comp(__first, __result_first))
1707 	    std::__adjust_heap(__result_first, _DistanceType(0),
1708 			       _DistanceType(__result_real_last
1709 					     - __result_first),
1710 			       _InputValueType(*__first), __comp);
1711 	  ++__first;
1712 	}
1713       std::__sort_heap(__result_first, __result_real_last, __comp);
1714       return __result_real_last;
1715     }
1716 
1717   /**
1718    *  @brief Copy the smallest elements of a sequence.
1719    *  @ingroup sorting_algorithms
1720    *  @param  __first   An iterator.
1721    *  @param  __last    Another iterator.
1722    *  @param  __result_first   A random-access iterator.
1723    *  @param  __result_last    Another random-access iterator.
1724    *  @return   An iterator indicating the end of the resulting sequence.
1725    *
1726    *  Copies and sorts the smallest N values from the range @p [__first,__last)
1727    *  to the range beginning at @p __result_first, where the number of
1728    *  elements to be copied, @p N, is the smaller of @p (__last-__first) and
1729    *  @p (__result_last-__result_first).
1730    *  After the sort if @e i and @e j are iterators in the range
1731    *  @p [__result_first,__result_first+N) such that i precedes j then
1732    *  *j<*i is false.
1733    *  The value returned is @p __result_first+N.
1734   */
1735   template<typename _InputIterator, typename _RandomAccessIterator>
1736     _GLIBCXX20_CONSTEXPR
1737     inline _RandomAccessIterator
1738     partial_sort_copy(_InputIterator __first, _InputIterator __last,
1739 		      _RandomAccessIterator __result_first,
1740 		      _RandomAccessIterator __result_last)
1741     {
1742 #ifdef _GLIBCXX_CONCEPT_CHECKS
1743       typedef typename iterator_traits<_InputIterator>::value_type
1744 	_InputValueType __attribute__((__unused__));
1745       typedef typename iterator_traits<_RandomAccessIterator>::value_type
1746 	_OutputValueType __attribute__((__unused__));
1747 #endif
1748 
1749       // concept requirements
1750       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
1751       __glibcxx_function_requires(_ConvertibleConcept<_InputValueType,
1752 				  _OutputValueType>)
1753       __glibcxx_function_requires(_LessThanOpConcept<_InputValueType,
1754 						     _OutputValueType>)
1755       __glibcxx_function_requires(_LessThanComparableConcept<_OutputValueType>)
1756       __glibcxx_requires_valid_range(__first, __last);
1757       __glibcxx_requires_irreflexive(__first, __last);
1758       __glibcxx_requires_valid_range(__result_first, __result_last);
1759 
1760       return std::__partial_sort_copy(__first, __last,
1761 				      __result_first, __result_last,
1762 				      __gnu_cxx::__ops::__iter_less_iter());
1763     }
1764 
1765   /**
1766    *  @brief Copy the smallest elements of a sequence using a predicate for
1767    *         comparison.
1768    *  @ingroup sorting_algorithms
1769    *  @param  __first   An input iterator.
1770    *  @param  __last    Another input iterator.
1771    *  @param  __result_first   A random-access iterator.
1772    *  @param  __result_last    Another random-access iterator.
1773    *  @param  __comp    A comparison functor.
1774    *  @return   An iterator indicating the end of the resulting sequence.
1775    *
1776    *  Copies and sorts the smallest N values from the range @p [__first,__last)
1777    *  to the range beginning at @p result_first, where the number of
1778    *  elements to be copied, @p N, is the smaller of @p (__last-__first) and
1779    *  @p (__result_last-__result_first).
1780    *  After the sort if @e i and @e j are iterators in the range
1781    *  @p [__result_first,__result_first+N) such that i precedes j then
1782    *  @p __comp(*j,*i) is false.
1783    *  The value returned is @p __result_first+N.
1784   */
1785   template<typename _InputIterator, typename _RandomAccessIterator,
1786 	   typename _Compare>
1787     _GLIBCXX20_CONSTEXPR
1788     inline _RandomAccessIterator
1789     partial_sort_copy(_InputIterator __first, _InputIterator __last,
1790 		      _RandomAccessIterator __result_first,
1791 		      _RandomAccessIterator __result_last,
1792 		      _Compare __comp)
1793     {
1794 #ifdef _GLIBCXX_CONCEPT_CHECKS
1795       typedef typename iterator_traits<_InputIterator>::value_type
1796 	_InputValueType __attribute__((__unused__));
1797       typedef typename iterator_traits<_RandomAccessIterator>::value_type
1798 	_OutputValueType __attribute__((__unused__));
1799 #endif
1800 
1801       // concept requirements
1802       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
1803       __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
1804 				  _RandomAccessIterator>)
1805       __glibcxx_function_requires(_ConvertibleConcept<_InputValueType,
1806 				  _OutputValueType>)
1807       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
1808 				  _InputValueType, _OutputValueType>)
1809       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
1810 				  _OutputValueType, _OutputValueType>)
1811       __glibcxx_requires_valid_range(__first, __last);
1812       __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
1813       __glibcxx_requires_valid_range(__result_first, __result_last);
1814 
1815       return std::__partial_sort_copy(__first, __last,
1816 				      __result_first, __result_last,
1817 				__gnu_cxx::__ops::__iter_comp_iter(__comp));
1818     }
1819 
1820   /// This is a helper function for the sort routine.
1821   template<typename _RandomAccessIterator, typename _Compare>
1822     _GLIBCXX20_CONSTEXPR
1823     void
1824     __unguarded_linear_insert(_RandomAccessIterator __last,
1825 			      _Compare __comp)
1826     {
1827       typename iterator_traits<_RandomAccessIterator>::value_type
1828 	__val = _GLIBCXX_MOVE(*__last);
1829       _RandomAccessIterator __next = __last;
1830       --__next;
1831       while (__comp(__val, __next))
1832 	{
1833 	  *__last = _GLIBCXX_MOVE(*__next);
1834 	  __last = __next;
1835 	  --__next;
1836 	}
1837       *__last = _GLIBCXX_MOVE(__val);
1838     }
1839 
1840   /// This is a helper function for the sort routine.
1841   template<typename _RandomAccessIterator, typename _Compare>
1842     _GLIBCXX20_CONSTEXPR
1843     void
1844     __insertion_sort(_RandomAccessIterator __first,
1845 		     _RandomAccessIterator __last, _Compare __comp)
1846     {
1847       if (__first == __last) return;
1848 
1849       for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i)
1850 	{
1851 	  if (__comp(__i, __first))
1852 	    {
1853 	      typename iterator_traits<_RandomAccessIterator>::value_type
1854 		__val = _GLIBCXX_MOVE(*__i);
1855 	      _GLIBCXX_MOVE_BACKWARD3(__first, __i, __i + 1);
1856 	      *__first = _GLIBCXX_MOVE(__val);
1857 	    }
1858 	  else
1859 	    std::__unguarded_linear_insert(__i,
1860 				__gnu_cxx::__ops::__val_comp_iter(__comp));
1861 	}
1862     }
1863 
1864   /// This is a helper function for the sort routine.
1865   template<typename _RandomAccessIterator, typename _Compare>
1866     _GLIBCXX20_CONSTEXPR
1867     inline void
1868     __unguarded_insertion_sort(_RandomAccessIterator __first,
1869 			       _RandomAccessIterator __last, _Compare __comp)
1870     {
1871       for (_RandomAccessIterator __i = __first; __i != __last; ++__i)
1872 	std::__unguarded_linear_insert(__i,
1873 				__gnu_cxx::__ops::__val_comp_iter(__comp));
1874     }
1875 
1876   /**
1877    *  @doctodo
1878    *  This controls some aspect of the sort routines.
1879   */
1880   enum { _S_threshold = 16 };
1881 
1882   /// This is a helper function for the sort routine.
1883   template<typename _RandomAccessIterator, typename _Compare>
1884     _GLIBCXX20_CONSTEXPR
1885     void
1886     __final_insertion_sort(_RandomAccessIterator __first,
1887 			   _RandomAccessIterator __last, _Compare __comp)
1888     {
1889       if (__last - __first > int(_S_threshold))
1890 	{
1891 	  std::__insertion_sort(__first, __first + int(_S_threshold), __comp);
1892 	  std::__unguarded_insertion_sort(__first + int(_S_threshold), __last,
1893 					  __comp);
1894 	}
1895       else
1896 	std::__insertion_sort(__first, __last, __comp);
1897     }
1898 
1899   /// This is a helper function...
1900   template<typename _RandomAccessIterator, typename _Compare>
1901     _GLIBCXX20_CONSTEXPR
1902     _RandomAccessIterator
1903     __unguarded_partition(_RandomAccessIterator __first,
1904 			  _RandomAccessIterator __last,
1905 			  _RandomAccessIterator __pivot, _Compare __comp)
1906     {
1907       while (true)
1908 	{
1909 	  while (__comp(__first, __pivot))
1910 	    ++__first;
1911 	  --__last;
1912 	  while (__comp(__pivot, __last))
1913 	    --__last;
1914 	  if (!(__first < __last))
1915 	    return __first;
1916 	  std::iter_swap(__first, __last);
1917 	  ++__first;
1918 	}
1919     }
1920 
1921   /// This is a helper function...
1922   template<typename _RandomAccessIterator, typename _Compare>
1923     _GLIBCXX20_CONSTEXPR
1924     inline _RandomAccessIterator
1925     __unguarded_partition_pivot(_RandomAccessIterator __first,
1926 				_RandomAccessIterator __last, _Compare __comp)
1927     {
1928       _RandomAccessIterator __mid = __first + (__last - __first) / 2;
1929       std::__move_median_to_first(__first, __first + 1, __mid, __last - 1,
1930 				  __comp);
1931       return std::__unguarded_partition(__first + 1, __last, __first, __comp);
1932     }
1933 
1934   template<typename _RandomAccessIterator, typename _Compare>
1935     _GLIBCXX20_CONSTEXPR
1936     inline void
1937     __partial_sort(_RandomAccessIterator __first,
1938 		   _RandomAccessIterator __middle,
1939 		   _RandomAccessIterator __last,
1940 		   _Compare __comp)
1941     {
1942       std::__heap_select(__first, __middle, __last, __comp);
1943       std::__sort_heap(__first, __middle, __comp);
1944     }
1945 
1946   /// This is a helper function for the sort routine.
1947   template<typename _RandomAccessIterator, typename _Size, typename _Compare>
1948     _GLIBCXX20_CONSTEXPR
1949     void
1950     __introsort_loop(_RandomAccessIterator __first,
1951 		     _RandomAccessIterator __last,
1952 		     _Size __depth_limit, _Compare __comp)
1953     {
1954       while (__last - __first > int(_S_threshold))
1955 	{
1956 	  if (__depth_limit == 0)
1957 	    {
1958 	      std::__partial_sort(__first, __last, __last, __comp);
1959 	      return;
1960 	    }
1961 	  --__depth_limit;
1962 	  _RandomAccessIterator __cut =
1963 	    std::__unguarded_partition_pivot(__first, __last, __comp);
1964 	  std::__introsort_loop(__cut, __last, __depth_limit, __comp);
1965 	  __last = __cut;
1966 	}
1967     }
1968 
1969   // sort
1970 
1971   template<typename _RandomAccessIterator, typename _Compare>
1972     _GLIBCXX20_CONSTEXPR
1973     inline void
1974     __sort(_RandomAccessIterator __first, _RandomAccessIterator __last,
1975 	   _Compare __comp)
1976     {
1977       if (__first != __last)
1978 	{
1979 	  std::__introsort_loop(__first, __last,
1980 				std::__lg(__last - __first) * 2,
1981 				__comp);
1982 	  std::__final_insertion_sort(__first, __last, __comp);
1983 	}
1984     }
1985 
1986   template<typename _RandomAccessIterator, typename _Size, typename _Compare>
1987     _GLIBCXX20_CONSTEXPR
1988     void
1989     __introselect(_RandomAccessIterator __first, _RandomAccessIterator __nth,
1990 		  _RandomAccessIterator __last, _Size __depth_limit,
1991 		  _Compare __comp)
1992     {
1993       while (__last - __first > 3)
1994 	{
1995 	  if (__depth_limit == 0)
1996 	    {
1997 	      std::__heap_select(__first, __nth + 1, __last, __comp);
1998 	      // Place the nth largest element in its final position.
1999 	      std::iter_swap(__first, __nth);
2000 	      return;
2001 	    }
2002 	  --__depth_limit;
2003 	  _RandomAccessIterator __cut =
2004 	    std::__unguarded_partition_pivot(__first, __last, __comp);
2005 	  if (__cut <= __nth)
2006 	    __first = __cut;
2007 	  else
2008 	    __last = __cut;
2009 	}
2010       std::__insertion_sort(__first, __last, __comp);
2011     }
2012 
2013   // nth_element
2014 
2015   // lower_bound moved to stl_algobase.h
2016 
2017   /**
2018    *  @brief Finds the first position in which @p __val could be inserted
2019    *         without changing the ordering.
2020    *  @ingroup binary_search_algorithms
2021    *  @param  __first   An iterator.
2022    *  @param  __last    Another iterator.
2023    *  @param  __val     The search term.
2024    *  @param  __comp    A functor to use for comparisons.
2025    *  @return An iterator pointing to the first element <em>not less
2026    *           than</em> @p __val, or end() if every element is less
2027    *           than @p __val.
2028    *  @ingroup binary_search_algorithms
2029    *
2030    *  The comparison function should have the same effects on ordering as
2031    *  the function used for the initial sort.
2032   */
2033   template<typename _ForwardIterator, typename _Tp, typename _Compare>
2034     _GLIBCXX20_CONSTEXPR
2035     inline _ForwardIterator
2036     lower_bound(_ForwardIterator __first, _ForwardIterator __last,
2037 		const _Tp& __val, _Compare __comp)
2038     {
2039       // concept requirements
2040       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
2041       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2042 	typename iterator_traits<_ForwardIterator>::value_type, _Tp>)
2043       __glibcxx_requires_partitioned_lower_pred(__first, __last,
2044 						__val, __comp);
2045 
2046       return std::__lower_bound(__first, __last, __val,
2047 				__gnu_cxx::__ops::__iter_comp_val(__comp));
2048     }
2049 
2050   template<typename _ForwardIterator, typename _Tp, typename _Compare>
2051     _GLIBCXX20_CONSTEXPR
2052     _ForwardIterator
2053     __upper_bound(_ForwardIterator __first, _ForwardIterator __last,
2054 		  const _Tp& __val, _Compare __comp)
2055     {
2056       typedef typename iterator_traits<_ForwardIterator>::difference_type
2057 	_DistanceType;
2058 
2059       _DistanceType __len = std::distance(__first, __last);
2060 
2061       while (__len > 0)
2062 	{
2063 	  _DistanceType __half = __len >> 1;
2064 	  _ForwardIterator __middle = __first;
2065 	  std::advance(__middle, __half);
2066 	  if (__comp(__val, __middle))
2067 	    __len = __half;
2068 	  else
2069 	    {
2070 	      __first = __middle;
2071 	      ++__first;
2072 	      __len = __len - __half - 1;
2073 	    }
2074 	}
2075       return __first;
2076     }
2077 
2078   /**
2079    *  @brief Finds the last position in which @p __val could be inserted
2080    *         without changing the ordering.
2081    *  @ingroup binary_search_algorithms
2082    *  @param  __first   An iterator.
2083    *  @param  __last    Another iterator.
2084    *  @param  __val     The search term.
2085    *  @return  An iterator pointing to the first element greater than @p __val,
2086    *           or end() if no elements are greater than @p __val.
2087    *  @ingroup binary_search_algorithms
2088   */
2089   template<typename _ForwardIterator, typename _Tp>
2090     _GLIBCXX20_CONSTEXPR
2091     inline _ForwardIterator
2092     upper_bound(_ForwardIterator __first, _ForwardIterator __last,
2093 		const _Tp& __val)
2094     {
2095       // concept requirements
2096       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
2097       __glibcxx_function_requires(_LessThanOpConcept<
2098 	_Tp, typename iterator_traits<_ForwardIterator>::value_type>)
2099       __glibcxx_requires_partitioned_upper(__first, __last, __val);
2100 
2101       return std::__upper_bound(__first, __last, __val,
2102 				__gnu_cxx::__ops::__val_less_iter());
2103     }
2104 
2105   /**
2106    *  @brief Finds the last position in which @p __val could be inserted
2107    *         without changing the ordering.
2108    *  @ingroup binary_search_algorithms
2109    *  @param  __first   An iterator.
2110    *  @param  __last    Another iterator.
2111    *  @param  __val     The search term.
2112    *  @param  __comp    A functor to use for comparisons.
2113    *  @return  An iterator pointing to the first element greater than @p __val,
2114    *           or end() if no elements are greater than @p __val.
2115    *  @ingroup binary_search_algorithms
2116    *
2117    *  The comparison function should have the same effects on ordering as
2118    *  the function used for the initial sort.
2119   */
2120   template<typename _ForwardIterator, typename _Tp, typename _Compare>
2121     _GLIBCXX20_CONSTEXPR
2122     inline _ForwardIterator
2123     upper_bound(_ForwardIterator __first, _ForwardIterator __last,
2124 		const _Tp& __val, _Compare __comp)
2125     {
2126       // concept requirements
2127       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
2128       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2129 	_Tp, typename iterator_traits<_ForwardIterator>::value_type>)
2130       __glibcxx_requires_partitioned_upper_pred(__first, __last,
2131 						__val, __comp);
2132 
2133       return std::__upper_bound(__first, __last, __val,
2134 				__gnu_cxx::__ops::__val_comp_iter(__comp));
2135     }
2136 
2137   template<typename _ForwardIterator, typename _Tp,
2138 	   typename _CompareItTp, typename _CompareTpIt>
2139     _GLIBCXX20_CONSTEXPR
2140     pair<_ForwardIterator, _ForwardIterator>
2141     __equal_range(_ForwardIterator __first, _ForwardIterator __last,
2142 		  const _Tp& __val,
2143 		  _CompareItTp __comp_it_val, _CompareTpIt __comp_val_it)
2144     {
2145       typedef typename iterator_traits<_ForwardIterator>::difference_type
2146 	_DistanceType;
2147 
2148       _DistanceType __len = std::distance(__first, __last);
2149 
2150       while (__len > 0)
2151 	{
2152 	  _DistanceType __half = __len >> 1;
2153 	  _ForwardIterator __middle = __first;
2154 	  std::advance(__middle, __half);
2155 	  if (__comp_it_val(__middle, __val))
2156 	    {
2157 	      __first = __middle;
2158 	      ++__first;
2159 	      __len = __len - __half - 1;
2160 	    }
2161 	  else if (__comp_val_it(__val, __middle))
2162 	    __len = __half;
2163 	  else
2164 	    {
2165 	      _ForwardIterator __left
2166 		= std::__lower_bound(__first, __middle, __val, __comp_it_val);
2167 	      std::advance(__first, __len);
2168 	      _ForwardIterator __right
2169 		= std::__upper_bound(++__middle, __first, __val, __comp_val_it);
2170 	      return pair<_ForwardIterator, _ForwardIterator>(__left, __right);
2171 	    }
2172 	}
2173       return pair<_ForwardIterator, _ForwardIterator>(__first, __first);
2174     }
2175 
2176   /**
2177    *  @brief Finds the largest subrange in which @p __val could be inserted
2178    *         at any place in it without changing the ordering.
2179    *  @ingroup binary_search_algorithms
2180    *  @param  __first   An iterator.
2181    *  @param  __last    Another iterator.
2182    *  @param  __val     The search term.
2183    *  @return  An pair of iterators defining the subrange.
2184    *  @ingroup binary_search_algorithms
2185    *
2186    *  This is equivalent to
2187    *  @code
2188    *    std::make_pair(lower_bound(__first, __last, __val),
2189    *                   upper_bound(__first, __last, __val))
2190    *  @endcode
2191    *  but does not actually call those functions.
2192   */
2193   template<typename _ForwardIterator, typename _Tp>
2194     _GLIBCXX20_CONSTEXPR
2195     inline pair<_ForwardIterator, _ForwardIterator>
2196     equal_range(_ForwardIterator __first, _ForwardIterator __last,
2197 		const _Tp& __val)
2198     {
2199       // concept requirements
2200       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
2201       __glibcxx_function_requires(_LessThanOpConcept<
2202 	typename iterator_traits<_ForwardIterator>::value_type, _Tp>)
2203       __glibcxx_function_requires(_LessThanOpConcept<
2204 	_Tp, typename iterator_traits<_ForwardIterator>::value_type>)
2205       __glibcxx_requires_partitioned_lower(__first, __last, __val);
2206       __glibcxx_requires_partitioned_upper(__first, __last, __val);
2207 
2208       return std::__equal_range(__first, __last, __val,
2209 				__gnu_cxx::__ops::__iter_less_val(),
2210 				__gnu_cxx::__ops::__val_less_iter());
2211     }
2212 
2213   /**
2214    *  @brief Finds the largest subrange in which @p __val could be inserted
2215    *         at any place in it without changing the ordering.
2216    *  @param  __first   An iterator.
2217    *  @param  __last    Another iterator.
2218    *  @param  __val     The search term.
2219    *  @param  __comp    A functor to use for comparisons.
2220    *  @return  An pair of iterators defining the subrange.
2221    *  @ingroup binary_search_algorithms
2222    *
2223    *  This is equivalent to
2224    *  @code
2225    *    std::make_pair(lower_bound(__first, __last, __val, __comp),
2226    *                   upper_bound(__first, __last, __val, __comp))
2227    *  @endcode
2228    *  but does not actually call those functions.
2229   */
2230   template<typename _ForwardIterator, typename _Tp, typename _Compare>
2231     _GLIBCXX20_CONSTEXPR
2232     inline pair<_ForwardIterator, _ForwardIterator>
2233     equal_range(_ForwardIterator __first, _ForwardIterator __last,
2234 		const _Tp& __val, _Compare __comp)
2235     {
2236       // concept requirements
2237       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
2238       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2239 	typename iterator_traits<_ForwardIterator>::value_type, _Tp>)
2240       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2241 	_Tp, typename iterator_traits<_ForwardIterator>::value_type>)
2242       __glibcxx_requires_partitioned_lower_pred(__first, __last,
2243 						__val, __comp);
2244       __glibcxx_requires_partitioned_upper_pred(__first, __last,
2245 						__val, __comp);
2246 
2247       return std::__equal_range(__first, __last, __val,
2248 				__gnu_cxx::__ops::__iter_comp_val(__comp),
2249 				__gnu_cxx::__ops::__val_comp_iter(__comp));
2250     }
2251 
2252   /**
2253    *  @brief Determines whether an element exists in a range.
2254    *  @ingroup binary_search_algorithms
2255    *  @param  __first   An iterator.
2256    *  @param  __last    Another iterator.
2257    *  @param  __val     The search term.
2258    *  @return True if @p __val (or its equivalent) is in [@p
2259    *  __first,@p __last ].
2260    *
2261    *  Note that this does not actually return an iterator to @p __val.  For
2262    *  that, use std::find or a container's specialized find member functions.
2263   */
2264   template<typename _ForwardIterator, typename _Tp>
2265     _GLIBCXX20_CONSTEXPR
2266     bool
2267     binary_search(_ForwardIterator __first, _ForwardIterator __last,
2268 		  const _Tp& __val)
2269     {
2270       // concept requirements
2271       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
2272       __glibcxx_function_requires(_LessThanOpConcept<
2273 	_Tp, typename iterator_traits<_ForwardIterator>::value_type>)
2274       __glibcxx_requires_partitioned_lower(__first, __last, __val);
2275       __glibcxx_requires_partitioned_upper(__first, __last, __val);
2276 
2277       _ForwardIterator __i
2278 	= std::__lower_bound(__first, __last, __val,
2279 			     __gnu_cxx::__ops::__iter_less_val());
2280       return __i != __last && !(__val < *__i);
2281     }
2282 
2283   /**
2284    *  @brief Determines whether an element exists in a range.
2285    *  @ingroup binary_search_algorithms
2286    *  @param  __first   An iterator.
2287    *  @param  __last    Another iterator.
2288    *  @param  __val     The search term.
2289    *  @param  __comp    A functor to use for comparisons.
2290    *  @return  True if @p __val (or its equivalent) is in @p [__first,__last].
2291    *
2292    *  Note that this does not actually return an iterator to @p __val.  For
2293    *  that, use std::find or a container's specialized find member functions.
2294    *
2295    *  The comparison function should have the same effects on ordering as
2296    *  the function used for the initial sort.
2297   */
2298   template<typename _ForwardIterator, typename _Tp, typename _Compare>
2299     _GLIBCXX20_CONSTEXPR
2300     bool
2301     binary_search(_ForwardIterator __first, _ForwardIterator __last,
2302 		  const _Tp& __val, _Compare __comp)
2303     {
2304       // concept requirements
2305       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
2306       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2307 	_Tp, typename iterator_traits<_ForwardIterator>::value_type>)
2308       __glibcxx_requires_partitioned_lower_pred(__first, __last,
2309 						__val, __comp);
2310       __glibcxx_requires_partitioned_upper_pred(__first, __last,
2311 						__val, __comp);
2312 
2313       _ForwardIterator __i
2314 	= std::__lower_bound(__first, __last, __val,
2315 			     __gnu_cxx::__ops::__iter_comp_val(__comp));
2316       return __i != __last && !bool(__comp(__val, *__i));
2317     }
2318 
2319   // merge
2320 
2321   /// This is a helper function for the __merge_adaptive routines.
2322   template<typename _InputIterator1, typename _InputIterator2,
2323 	   typename _OutputIterator, typename _Compare>
2324     void
2325     __move_merge_adaptive(_InputIterator1 __first1, _InputIterator1 __last1,
2326 			  _InputIterator2 __first2, _InputIterator2 __last2,
2327 			  _OutputIterator __result, _Compare __comp)
2328     {
2329       while (__first1 != __last1 && __first2 != __last2)
2330 	{
2331 	  if (__comp(__first2, __first1))
2332 	    {
2333 	      *__result = _GLIBCXX_MOVE(*__first2);
2334 	      ++__first2;
2335 	    }
2336 	  else
2337 	    {
2338 	      *__result = _GLIBCXX_MOVE(*__first1);
2339 	      ++__first1;
2340 	    }
2341 	  ++__result;
2342 	}
2343       if (__first1 != __last1)
2344 	_GLIBCXX_MOVE3(__first1, __last1, __result);
2345     }
2346 
2347   /// This is a helper function for the __merge_adaptive routines.
2348   template<typename _BidirectionalIterator1, typename _BidirectionalIterator2,
2349 	   typename _BidirectionalIterator3, typename _Compare>
2350     void
2351     __move_merge_adaptive_backward(_BidirectionalIterator1 __first1,
2352 				   _BidirectionalIterator1 __last1,
2353 				   _BidirectionalIterator2 __first2,
2354 				   _BidirectionalIterator2 __last2,
2355 				   _BidirectionalIterator3 __result,
2356 				   _Compare __comp)
2357     {
2358       if (__first1 == __last1)
2359 	{
2360 	  _GLIBCXX_MOVE_BACKWARD3(__first2, __last2, __result);
2361 	  return;
2362 	}
2363       else if (__first2 == __last2)
2364 	return;
2365 
2366       --__last1;
2367       --__last2;
2368       while (true)
2369 	{
2370 	  if (__comp(__last2, __last1))
2371 	    {
2372 	      *--__result = _GLIBCXX_MOVE(*__last1);
2373 	      if (__first1 == __last1)
2374 		{
2375 		  _GLIBCXX_MOVE_BACKWARD3(__first2, ++__last2, __result);
2376 		  return;
2377 		}
2378 	      --__last1;
2379 	    }
2380 	  else
2381 	    {
2382 	      *--__result = _GLIBCXX_MOVE(*__last2);
2383 	      if (__first2 == __last2)
2384 		return;
2385 	      --__last2;
2386 	    }
2387 	}
2388     }
2389 
2390   /// This is a helper function for the merge routines.
2391   template<typename _BidirectionalIterator1, typename _BidirectionalIterator2,
2392 	   typename _Distance>
2393     _BidirectionalIterator1
2394     __rotate_adaptive(_BidirectionalIterator1 __first,
2395 		      _BidirectionalIterator1 __middle,
2396 		      _BidirectionalIterator1 __last,
2397 		      _Distance __len1, _Distance __len2,
2398 		      _BidirectionalIterator2 __buffer,
2399 		      _Distance __buffer_size)
2400     {
2401       _BidirectionalIterator2 __buffer_end;
2402       if (__len1 > __len2 && __len2 <= __buffer_size)
2403 	{
2404 	  if (__len2)
2405 	    {
2406 	      __buffer_end = _GLIBCXX_MOVE3(__middle, __last, __buffer);
2407 	      _GLIBCXX_MOVE_BACKWARD3(__first, __middle, __last);
2408 	      return _GLIBCXX_MOVE3(__buffer, __buffer_end, __first);
2409 	    }
2410 	  else
2411 	    return __first;
2412 	}
2413       else if (__len1 <= __buffer_size)
2414 	{
2415 	  if (__len1)
2416 	    {
2417 	      __buffer_end = _GLIBCXX_MOVE3(__first, __middle, __buffer);
2418 	      _GLIBCXX_MOVE3(__middle, __last, __first);
2419 	      return _GLIBCXX_MOVE_BACKWARD3(__buffer, __buffer_end, __last);
2420 	    }
2421 	  else
2422 	    return __last;
2423 	}
2424       else
2425 	return std::rotate(__first, __middle, __last);
2426     }
2427 
2428   /// This is a helper function for the merge routines.
2429   template<typename _BidirectionalIterator, typename _Distance,
2430 	   typename _Pointer, typename _Compare>
2431     void
2432     __merge_adaptive(_BidirectionalIterator __first,
2433 		     _BidirectionalIterator __middle,
2434 		     _BidirectionalIterator __last,
2435 		     _Distance __len1, _Distance __len2,
2436 		     _Pointer __buffer, _Distance __buffer_size,
2437 		     _Compare __comp)
2438     {
2439       if (__len1 <= __len2 && __len1 <= __buffer_size)
2440 	{
2441 	  _Pointer __buffer_end = _GLIBCXX_MOVE3(__first, __middle, __buffer);
2442 	  std::__move_merge_adaptive(__buffer, __buffer_end, __middle, __last,
2443 				     __first, __comp);
2444 	}
2445       else if (__len2 <= __buffer_size)
2446 	{
2447 	  _Pointer __buffer_end = _GLIBCXX_MOVE3(__middle, __last, __buffer);
2448 	  std::__move_merge_adaptive_backward(__first, __middle, __buffer,
2449 					      __buffer_end, __last, __comp);
2450 	}
2451       else
2452 	{
2453 	  _BidirectionalIterator __first_cut = __first;
2454 	  _BidirectionalIterator __second_cut = __middle;
2455 	  _Distance __len11 = 0;
2456 	  _Distance __len22 = 0;
2457 	  if (__len1 > __len2)
2458 	    {
2459 	      __len11 = __len1 / 2;
2460 	      std::advance(__first_cut, __len11);
2461 	      __second_cut
2462 		= std::__lower_bound(__middle, __last, *__first_cut,
2463 				     __gnu_cxx::__ops::__iter_comp_val(__comp));
2464 	      __len22 = std::distance(__middle, __second_cut);
2465 	    }
2466 	  else
2467 	    {
2468 	      __len22 = __len2 / 2;
2469 	      std::advance(__second_cut, __len22);
2470 	      __first_cut
2471 		= std::__upper_bound(__first, __middle, *__second_cut,
2472 				     __gnu_cxx::__ops::__val_comp_iter(__comp));
2473 	      __len11 = std::distance(__first, __first_cut);
2474 	    }
2475 
2476 	  _BidirectionalIterator __new_middle
2477 	    = std::__rotate_adaptive(__first_cut, __middle, __second_cut,
2478 				     __len1 - __len11, __len22, __buffer,
2479 				     __buffer_size);
2480 	  std::__merge_adaptive(__first, __first_cut, __new_middle, __len11,
2481 				__len22, __buffer, __buffer_size, __comp);
2482 	  std::__merge_adaptive(__new_middle, __second_cut, __last,
2483 				__len1 - __len11,
2484 				__len2 - __len22, __buffer,
2485 				__buffer_size, __comp);
2486 	}
2487     }
2488 
2489   /// This is a helper function for the merge routines.
2490   template<typename _BidirectionalIterator, typename _Distance,
2491 	   typename _Compare>
2492     void
2493     __merge_without_buffer(_BidirectionalIterator __first,
2494 			   _BidirectionalIterator __middle,
2495 			   _BidirectionalIterator __last,
2496 			   _Distance __len1, _Distance __len2,
2497 			   _Compare __comp)
2498     {
2499       if (__len1 == 0 || __len2 == 0)
2500 	return;
2501 
2502       if (__len1 + __len2 == 2)
2503 	{
2504 	  if (__comp(__middle, __first))
2505 	    std::iter_swap(__first, __middle);
2506 	  return;
2507 	}
2508 
2509       _BidirectionalIterator __first_cut = __first;
2510       _BidirectionalIterator __second_cut = __middle;
2511       _Distance __len11 = 0;
2512       _Distance __len22 = 0;
2513       if (__len1 > __len2)
2514 	{
2515 	  __len11 = __len1 / 2;
2516 	  std::advance(__first_cut, __len11);
2517 	  __second_cut
2518 	    = std::__lower_bound(__middle, __last, *__first_cut,
2519 				 __gnu_cxx::__ops::__iter_comp_val(__comp));
2520 	  __len22 = std::distance(__middle, __second_cut);
2521 	}
2522       else
2523 	{
2524 	  __len22 = __len2 / 2;
2525 	  std::advance(__second_cut, __len22);
2526 	  __first_cut
2527 	    = std::__upper_bound(__first, __middle, *__second_cut,
2528 				 __gnu_cxx::__ops::__val_comp_iter(__comp));
2529 	  __len11 = std::distance(__first, __first_cut);
2530 	}
2531 
2532       _BidirectionalIterator __new_middle
2533 	= std::rotate(__first_cut, __middle, __second_cut);
2534       std::__merge_without_buffer(__first, __first_cut, __new_middle,
2535 				  __len11, __len22, __comp);
2536       std::__merge_without_buffer(__new_middle, __second_cut, __last,
2537 				  __len1 - __len11, __len2 - __len22, __comp);
2538     }
2539 
2540   template<typename _BidirectionalIterator, typename _Compare>
2541     void
2542     __inplace_merge(_BidirectionalIterator __first,
2543 		    _BidirectionalIterator __middle,
2544 		    _BidirectionalIterator __last,
2545 		    _Compare __comp)
2546     {
2547       typedef typename iterator_traits<_BidirectionalIterator>::value_type
2548 	  _ValueType;
2549       typedef typename iterator_traits<_BidirectionalIterator>::difference_type
2550 	  _DistanceType;
2551 
2552       if (__first == __middle || __middle == __last)
2553 	return;
2554 
2555       const _DistanceType __len1 = std::distance(__first, __middle);
2556       const _DistanceType __len2 = std::distance(__middle, __last);
2557 
2558       typedef _Temporary_buffer<_BidirectionalIterator, _ValueType> _TmpBuf;
2559       _TmpBuf __buf(__first, __len1 + __len2);
2560 
2561       if (__buf.begin() == 0)
2562 	std::__merge_without_buffer
2563 	  (__first, __middle, __last, __len1, __len2, __comp);
2564       else
2565 	std::__merge_adaptive
2566 	  (__first, __middle, __last, __len1, __len2, __buf.begin(),
2567 	   _DistanceType(__buf.size()), __comp);
2568     }
2569 
2570   /**
2571    *  @brief Merges two sorted ranges in place.
2572    *  @ingroup sorting_algorithms
2573    *  @param  __first   An iterator.
2574    *  @param  __middle  Another iterator.
2575    *  @param  __last    Another iterator.
2576    *  @return  Nothing.
2577    *
2578    *  Merges two sorted and consecutive ranges, [__first,__middle) and
2579    *  [__middle,__last), and puts the result in [__first,__last).  The
2580    *  output will be sorted.  The sort is @e stable, that is, for
2581    *  equivalent elements in the two ranges, elements from the first
2582    *  range will always come before elements from the second.
2583    *
2584    *  If enough additional memory is available, this takes (__last-__first)-1
2585    *  comparisons.  Otherwise an NlogN algorithm is used, where N is
2586    *  distance(__first,__last).
2587   */
2588   template<typename _BidirectionalIterator>
2589     inline void
2590     inplace_merge(_BidirectionalIterator __first,
2591 		  _BidirectionalIterator __middle,
2592 		  _BidirectionalIterator __last)
2593     {
2594       // concept requirements
2595       __glibcxx_function_requires(_Mutable_BidirectionalIteratorConcept<
2596 	    _BidirectionalIterator>)
2597       __glibcxx_function_requires(_LessThanComparableConcept<
2598 	    typename iterator_traits<_BidirectionalIterator>::value_type>)
2599       __glibcxx_requires_sorted(__first, __middle);
2600       __glibcxx_requires_sorted(__middle, __last);
2601       __glibcxx_requires_irreflexive(__first, __last);
2602 
2603       std::__inplace_merge(__first, __middle, __last,
2604 			   __gnu_cxx::__ops::__iter_less_iter());
2605     }
2606 
2607   /**
2608    *  @brief Merges two sorted ranges in place.
2609    *  @ingroup sorting_algorithms
2610    *  @param  __first   An iterator.
2611    *  @param  __middle  Another iterator.
2612    *  @param  __last    Another iterator.
2613    *  @param  __comp    A functor to use for comparisons.
2614    *  @return  Nothing.
2615    *
2616    *  Merges two sorted and consecutive ranges, [__first,__middle) and
2617    *  [middle,last), and puts the result in [__first,__last).  The output will
2618    *  be sorted.  The sort is @e stable, that is, for equivalent
2619    *  elements in the two ranges, elements from the first range will always
2620    *  come before elements from the second.
2621    *
2622    *  If enough additional memory is available, this takes (__last-__first)-1
2623    *  comparisons.  Otherwise an NlogN algorithm is used, where N is
2624    *  distance(__first,__last).
2625    *
2626    *  The comparison function should have the same effects on ordering as
2627    *  the function used for the initial sort.
2628   */
2629   template<typename _BidirectionalIterator, typename _Compare>
2630     inline void
2631     inplace_merge(_BidirectionalIterator __first,
2632 		  _BidirectionalIterator __middle,
2633 		  _BidirectionalIterator __last,
2634 		  _Compare __comp)
2635     {
2636       // concept requirements
2637       __glibcxx_function_requires(_Mutable_BidirectionalIteratorConcept<
2638 	    _BidirectionalIterator>)
2639       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2640 	    typename iterator_traits<_BidirectionalIterator>::value_type,
2641 	    typename iterator_traits<_BidirectionalIterator>::value_type>)
2642       __glibcxx_requires_sorted_pred(__first, __middle, __comp);
2643       __glibcxx_requires_sorted_pred(__middle, __last, __comp);
2644       __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
2645 
2646       std::__inplace_merge(__first, __middle, __last,
2647 			   __gnu_cxx::__ops::__iter_comp_iter(__comp));
2648     }
2649 
2650 
2651   /// This is a helper function for the __merge_sort_loop routines.
2652   template<typename _InputIterator, typename _OutputIterator,
2653 	   typename _Compare>
2654     _OutputIterator
2655     __move_merge(_InputIterator __first1, _InputIterator __last1,
2656 		 _InputIterator __first2, _InputIterator __last2,
2657 		 _OutputIterator __result, _Compare __comp)
2658     {
2659       while (__first1 != __last1 && __first2 != __last2)
2660 	{
2661 	  if (__comp(__first2, __first1))
2662 	    {
2663 	      *__result = _GLIBCXX_MOVE(*__first2);
2664 	      ++__first2;
2665 	    }
2666 	  else
2667 	    {
2668 	      *__result = _GLIBCXX_MOVE(*__first1);
2669 	      ++__first1;
2670 	    }
2671 	  ++__result;
2672 	}
2673       return _GLIBCXX_MOVE3(__first2, __last2,
2674 			    _GLIBCXX_MOVE3(__first1, __last1,
2675 					   __result));
2676     }
2677 
2678   template<typename _RandomAccessIterator1, typename _RandomAccessIterator2,
2679 	   typename _Distance, typename _Compare>
2680     void
2681     __merge_sort_loop(_RandomAccessIterator1 __first,
2682 		      _RandomAccessIterator1 __last,
2683 		      _RandomAccessIterator2 __result, _Distance __step_size,
2684 		      _Compare __comp)
2685     {
2686       const _Distance __two_step = 2 * __step_size;
2687 
2688       while (__last - __first >= __two_step)
2689 	{
2690 	  __result = std::__move_merge(__first, __first + __step_size,
2691 				       __first + __step_size,
2692 				       __first + __two_step,
2693 				       __result, __comp);
2694 	  __first += __two_step;
2695 	}
2696       __step_size = std::min(_Distance(__last - __first), __step_size);
2697 
2698       std::__move_merge(__first, __first + __step_size,
2699 			__first + __step_size, __last, __result, __comp);
2700     }
2701 
2702   template<typename _RandomAccessIterator, typename _Distance,
2703 	   typename _Compare>
2704     _GLIBCXX20_CONSTEXPR
2705     void
2706     __chunk_insertion_sort(_RandomAccessIterator __first,
2707 			   _RandomAccessIterator __last,
2708 			   _Distance __chunk_size, _Compare __comp)
2709     {
2710       while (__last - __first >= __chunk_size)
2711 	{
2712 	  std::__insertion_sort(__first, __first + __chunk_size, __comp);
2713 	  __first += __chunk_size;
2714 	}
2715       std::__insertion_sort(__first, __last, __comp);
2716     }
2717 
2718   enum { _S_chunk_size = 7 };
2719 
2720   template<typename _RandomAccessIterator, typename _Pointer, typename _Compare>
2721     void
2722     __merge_sort_with_buffer(_RandomAccessIterator __first,
2723 			     _RandomAccessIterator __last,
2724 			     _Pointer __buffer, _Compare __comp)
2725     {
2726       typedef typename iterator_traits<_RandomAccessIterator>::difference_type
2727 	_Distance;
2728 
2729       const _Distance __len = __last - __first;
2730       const _Pointer __buffer_last = __buffer + __len;
2731 
2732       _Distance __step_size = _S_chunk_size;
2733       std::__chunk_insertion_sort(__first, __last, __step_size, __comp);
2734 
2735       while (__step_size < __len)
2736 	{
2737 	  std::__merge_sort_loop(__first, __last, __buffer,
2738 				 __step_size, __comp);
2739 	  __step_size *= 2;
2740 	  std::__merge_sort_loop(__buffer, __buffer_last, __first,
2741 				 __step_size, __comp);
2742 	  __step_size *= 2;
2743 	}
2744     }
2745 
2746   template<typename _RandomAccessIterator, typename _Pointer,
2747 	   typename _Distance, typename _Compare>
2748     void
2749     __stable_sort_adaptive(_RandomAccessIterator __first,
2750 			   _RandomAccessIterator __last,
2751 			   _Pointer __buffer, _Distance __buffer_size,
2752 			   _Compare __comp)
2753     {
2754       const _Distance __len = (__last - __first + 1) / 2;
2755       const _RandomAccessIterator __middle = __first + __len;
2756       if (__len > __buffer_size)
2757 	{
2758 	  std::__stable_sort_adaptive(__first, __middle, __buffer,
2759 				      __buffer_size, __comp);
2760 	  std::__stable_sort_adaptive(__middle, __last, __buffer,
2761 				      __buffer_size, __comp);
2762 	}
2763       else
2764 	{
2765 	  std::__merge_sort_with_buffer(__first, __middle, __buffer, __comp);
2766 	  std::__merge_sort_with_buffer(__middle, __last, __buffer, __comp);
2767 	}
2768       std::__merge_adaptive(__first, __middle, __last,
2769 			    _Distance(__middle - __first),
2770 			    _Distance(__last - __middle),
2771 			    __buffer, __buffer_size,
2772 			    __comp);
2773     }
2774 
2775   /// This is a helper function for the stable sorting routines.
2776   template<typename _RandomAccessIterator, typename _Compare>
2777     void
2778     __inplace_stable_sort(_RandomAccessIterator __first,
2779 			  _RandomAccessIterator __last, _Compare __comp)
2780     {
2781       if (__last - __first < 15)
2782 	{
2783 	  std::__insertion_sort(__first, __last, __comp);
2784 	  return;
2785 	}
2786       _RandomAccessIterator __middle = __first + (__last - __first) / 2;
2787       std::__inplace_stable_sort(__first, __middle, __comp);
2788       std::__inplace_stable_sort(__middle, __last, __comp);
2789       std::__merge_without_buffer(__first, __middle, __last,
2790 				  __middle - __first,
2791 				  __last - __middle,
2792 				  __comp);
2793     }
2794 
2795   // stable_sort
2796 
2797   // Set algorithms: includes, set_union, set_intersection, set_difference,
2798   // set_symmetric_difference.  All of these algorithms have the precondition
2799   // that their input ranges are sorted and the postcondition that their output
2800   // ranges are sorted.
2801 
2802   template<typename _InputIterator1, typename _InputIterator2,
2803 	   typename _Compare>
2804     _GLIBCXX20_CONSTEXPR
2805     bool
2806     __includes(_InputIterator1 __first1, _InputIterator1 __last1,
2807 	       _InputIterator2 __first2, _InputIterator2 __last2,
2808 	       _Compare __comp)
2809     {
2810       while (__first1 != __last1 && __first2 != __last2)
2811 	if (__comp(__first2, __first1))
2812 	  return false;
2813 	else if (__comp(__first1, __first2))
2814 	  ++__first1;
2815 	else
2816 	  {
2817 	    ++__first1;
2818 	    ++__first2;
2819 	  }
2820 
2821       return __first2 == __last2;
2822     }
2823 
2824   /**
2825    *  @brief Determines whether all elements of a sequence exists in a range.
2826    *  @param  __first1  Start of search range.
2827    *  @param  __last1   End of search range.
2828    *  @param  __first2  Start of sequence
2829    *  @param  __last2   End of sequence.
2830    *  @return  True if each element in [__first2,__last2) is contained in order
2831    *  within [__first1,__last1).  False otherwise.
2832    *  @ingroup set_algorithms
2833    *
2834    *  This operation expects both [__first1,__last1) and
2835    *  [__first2,__last2) to be sorted.  Searches for the presence of
2836    *  each element in [__first2,__last2) within [__first1,__last1).
2837    *  The iterators over each range only move forward, so this is a
2838    *  linear algorithm.  If an element in [__first2,__last2) is not
2839    *  found before the search iterator reaches @p __last2, false is
2840    *  returned.
2841   */
2842   template<typename _InputIterator1, typename _InputIterator2>
2843     _GLIBCXX20_CONSTEXPR
2844     inline bool
2845     includes(_InputIterator1 __first1, _InputIterator1 __last1,
2846 	     _InputIterator2 __first2, _InputIterator2 __last2)
2847     {
2848       // concept requirements
2849       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
2850       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
2851       __glibcxx_function_requires(_LessThanOpConcept<
2852 	    typename iterator_traits<_InputIterator1>::value_type,
2853 	    typename iterator_traits<_InputIterator2>::value_type>)
2854       __glibcxx_function_requires(_LessThanOpConcept<
2855 	    typename iterator_traits<_InputIterator2>::value_type,
2856 	    typename iterator_traits<_InputIterator1>::value_type>)
2857       __glibcxx_requires_sorted_set(__first1, __last1, __first2);
2858       __glibcxx_requires_sorted_set(__first2, __last2, __first1);
2859       __glibcxx_requires_irreflexive2(__first1, __last1);
2860       __glibcxx_requires_irreflexive2(__first2, __last2);
2861 
2862       return std::__includes(__first1, __last1, __first2, __last2,
2863 			     __gnu_cxx::__ops::__iter_less_iter());
2864     }
2865 
2866   /**
2867    *  @brief Determines whether all elements of a sequence exists in a range
2868    *  using comparison.
2869    *  @ingroup set_algorithms
2870    *  @param  __first1  Start of search range.
2871    *  @param  __last1   End of search range.
2872    *  @param  __first2  Start of sequence
2873    *  @param  __last2   End of sequence.
2874    *  @param  __comp    Comparison function to use.
2875    *  @return True if each element in [__first2,__last2) is contained
2876    *  in order within [__first1,__last1) according to comp.  False
2877    *  otherwise.  @ingroup set_algorithms
2878    *
2879    *  This operation expects both [__first1,__last1) and
2880    *  [__first2,__last2) to be sorted.  Searches for the presence of
2881    *  each element in [__first2,__last2) within [__first1,__last1),
2882    *  using comp to decide.  The iterators over each range only move
2883    *  forward, so this is a linear algorithm.  If an element in
2884    *  [__first2,__last2) is not found before the search iterator
2885    *  reaches @p __last2, false is returned.
2886   */
2887   template<typename _InputIterator1, typename _InputIterator2,
2888 	   typename _Compare>
2889     _GLIBCXX20_CONSTEXPR
2890     inline bool
2891     includes(_InputIterator1 __first1, _InputIterator1 __last1,
2892 	     _InputIterator2 __first2, _InputIterator2 __last2,
2893 	     _Compare __comp)
2894     {
2895       // concept requirements
2896       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
2897       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
2898       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2899 	    typename iterator_traits<_InputIterator1>::value_type,
2900 	    typename iterator_traits<_InputIterator2>::value_type>)
2901       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2902 	    typename iterator_traits<_InputIterator2>::value_type,
2903 	    typename iterator_traits<_InputIterator1>::value_type>)
2904       __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp);
2905       __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp);
2906       __glibcxx_requires_irreflexive_pred2(__first1, __last1, __comp);
2907       __glibcxx_requires_irreflexive_pred2(__first2, __last2, __comp);
2908 
2909       return std::__includes(__first1, __last1, __first2, __last2,
2910 			     __gnu_cxx::__ops::__iter_comp_iter(__comp));
2911     }
2912 
2913   // nth_element
2914   // merge
2915   // set_difference
2916   // set_intersection
2917   // set_union
2918   // stable_sort
2919   // set_symmetric_difference
2920   // min_element
2921   // max_element
2922 
2923   template<typename _BidirectionalIterator, typename _Compare>
2924     _GLIBCXX20_CONSTEXPR
2925     bool
2926     __next_permutation(_BidirectionalIterator __first,
2927 		       _BidirectionalIterator __last, _Compare __comp)
2928     {
2929       if (__first == __last)
2930 	return false;
2931       _BidirectionalIterator __i = __first;
2932       ++__i;
2933       if (__i == __last)
2934 	return false;
2935       __i = __last;
2936       --__i;
2937 
2938       for(;;)
2939 	{
2940 	  _BidirectionalIterator __ii = __i;
2941 	  --__i;
2942 	  if (__comp(__i, __ii))
2943 	    {
2944 	      _BidirectionalIterator __j = __last;
2945 	      while (!__comp(__i, --__j))
2946 		{}
2947 	      std::iter_swap(__i, __j);
2948 	      std::__reverse(__ii, __last,
2949 			     std::__iterator_category(__first));
2950 	      return true;
2951 	    }
2952 	  if (__i == __first)
2953 	    {
2954 	      std::__reverse(__first, __last,
2955 			     std::__iterator_category(__first));
2956 	      return false;
2957 	    }
2958 	}
2959     }
2960 
2961   /**
2962    *  @brief  Permute range into the next @e dictionary ordering.
2963    *  @ingroup sorting_algorithms
2964    *  @param  __first  Start of range.
2965    *  @param  __last   End of range.
2966    *  @return  False if wrapped to first permutation, true otherwise.
2967    *
2968    *  Treats all permutations of the range as a set of @e dictionary sorted
2969    *  sequences.  Permutes the current sequence into the next one of this set.
2970    *  Returns true if there are more sequences to generate.  If the sequence
2971    *  is the largest of the set, the smallest is generated and false returned.
2972   */
2973   template<typename _BidirectionalIterator>
2974     _GLIBCXX20_CONSTEXPR
2975     inline bool
2976     next_permutation(_BidirectionalIterator __first,
2977 		     _BidirectionalIterator __last)
2978     {
2979       // concept requirements
2980       __glibcxx_function_requires(_BidirectionalIteratorConcept<
2981 				  _BidirectionalIterator>)
2982       __glibcxx_function_requires(_LessThanComparableConcept<
2983 	    typename iterator_traits<_BidirectionalIterator>::value_type>)
2984       __glibcxx_requires_valid_range(__first, __last);
2985       __glibcxx_requires_irreflexive(__first, __last);
2986 
2987       return std::__next_permutation
2988 	(__first, __last, __gnu_cxx::__ops::__iter_less_iter());
2989     }
2990 
2991   /**
2992    *  @brief  Permute range into the next @e dictionary ordering using
2993    *          comparison functor.
2994    *  @ingroup sorting_algorithms
2995    *  @param  __first  Start of range.
2996    *  @param  __last   End of range.
2997    *  @param  __comp   A comparison functor.
2998    *  @return  False if wrapped to first permutation, true otherwise.
2999    *
3000    *  Treats all permutations of the range [__first,__last) as a set of
3001    *  @e dictionary sorted sequences ordered by @p __comp.  Permutes the current
3002    *  sequence into the next one of this set.  Returns true if there are more
3003    *  sequences to generate.  If the sequence is the largest of the set, the
3004    *  smallest is generated and false returned.
3005   */
3006   template<typename _BidirectionalIterator, typename _Compare>
3007     _GLIBCXX20_CONSTEXPR
3008     inline bool
3009     next_permutation(_BidirectionalIterator __first,
3010 		     _BidirectionalIterator __last, _Compare __comp)
3011     {
3012       // concept requirements
3013       __glibcxx_function_requires(_BidirectionalIteratorConcept<
3014 				  _BidirectionalIterator>)
3015       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
3016 	    typename iterator_traits<_BidirectionalIterator>::value_type,
3017 	    typename iterator_traits<_BidirectionalIterator>::value_type>)
3018       __glibcxx_requires_valid_range(__first, __last);
3019       __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
3020 
3021       return std::__next_permutation
3022 	(__first, __last, __gnu_cxx::__ops::__iter_comp_iter(__comp));
3023     }
3024 
3025   template<typename _BidirectionalIterator, typename _Compare>
3026     _GLIBCXX20_CONSTEXPR
3027     bool
3028     __prev_permutation(_BidirectionalIterator __first,
3029 		       _BidirectionalIterator __last, _Compare __comp)
3030     {
3031       if (__first == __last)
3032 	return false;
3033       _BidirectionalIterator __i = __first;
3034       ++__i;
3035       if (__i == __last)
3036 	return false;
3037       __i = __last;
3038       --__i;
3039 
3040       for(;;)
3041 	{
3042 	  _BidirectionalIterator __ii = __i;
3043 	  --__i;
3044 	  if (__comp(__ii, __i))
3045 	    {
3046 	      _BidirectionalIterator __j = __last;
3047 	      while (!__comp(--__j, __i))
3048 		{}
3049 	      std::iter_swap(__i, __j);
3050 	      std::__reverse(__ii, __last,
3051 			     std::__iterator_category(__first));
3052 	      return true;
3053 	    }
3054 	  if (__i == __first)
3055 	    {
3056 	      std::__reverse(__first, __last,
3057 			     std::__iterator_category(__first));
3058 	      return false;
3059 	    }
3060 	}
3061     }
3062 
3063   /**
3064    *  @brief  Permute range into the previous @e dictionary ordering.
3065    *  @ingroup sorting_algorithms
3066    *  @param  __first  Start of range.
3067    *  @param  __last   End of range.
3068    *  @return  False if wrapped to last permutation, true otherwise.
3069    *
3070    *  Treats all permutations of the range as a set of @e dictionary sorted
3071    *  sequences.  Permutes the current sequence into the previous one of this
3072    *  set.  Returns true if there are more sequences to generate.  If the
3073    *  sequence is the smallest of the set, the largest is generated and false
3074    *  returned.
3075   */
3076   template<typename _BidirectionalIterator>
3077     _GLIBCXX20_CONSTEXPR
3078     inline bool
3079     prev_permutation(_BidirectionalIterator __first,
3080 		     _BidirectionalIterator __last)
3081     {
3082       // concept requirements
3083       __glibcxx_function_requires(_BidirectionalIteratorConcept<
3084 				  _BidirectionalIterator>)
3085       __glibcxx_function_requires(_LessThanComparableConcept<
3086 	    typename iterator_traits<_BidirectionalIterator>::value_type>)
3087       __glibcxx_requires_valid_range(__first, __last);
3088       __glibcxx_requires_irreflexive(__first, __last);
3089 
3090       return std::__prev_permutation(__first, __last,
3091 				     __gnu_cxx::__ops::__iter_less_iter());
3092     }
3093 
3094   /**
3095    *  @brief  Permute range into the previous @e dictionary ordering using
3096    *          comparison functor.
3097    *  @ingroup sorting_algorithms
3098    *  @param  __first  Start of range.
3099    *  @param  __last   End of range.
3100    *  @param  __comp   A comparison functor.
3101    *  @return  False if wrapped to last permutation, true otherwise.
3102    *
3103    *  Treats all permutations of the range [__first,__last) as a set of
3104    *  @e dictionary sorted sequences ordered by @p __comp.  Permutes the current
3105    *  sequence into the previous one of this set.  Returns true if there are
3106    *  more sequences to generate.  If the sequence is the smallest of the set,
3107    *  the largest is generated and false returned.
3108   */
3109   template<typename _BidirectionalIterator, typename _Compare>
3110     _GLIBCXX20_CONSTEXPR
3111     inline bool
3112     prev_permutation(_BidirectionalIterator __first,
3113 		     _BidirectionalIterator __last, _Compare __comp)
3114     {
3115       // concept requirements
3116       __glibcxx_function_requires(_BidirectionalIteratorConcept<
3117 				  _BidirectionalIterator>)
3118       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
3119 	    typename iterator_traits<_BidirectionalIterator>::value_type,
3120 	    typename iterator_traits<_BidirectionalIterator>::value_type>)
3121       __glibcxx_requires_valid_range(__first, __last);
3122       __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
3123 
3124       return std::__prev_permutation(__first, __last,
3125 				__gnu_cxx::__ops::__iter_comp_iter(__comp));
3126     }
3127 
3128   // replace
3129   // replace_if
3130 
3131   template<typename _InputIterator, typename _OutputIterator,
3132 	   typename _Predicate, typename _Tp>
3133     _GLIBCXX20_CONSTEXPR
3134     _OutputIterator
3135     __replace_copy_if(_InputIterator __first, _InputIterator __last,
3136 		      _OutputIterator __result,
3137 		      _Predicate __pred, const _Tp& __new_value)
3138     {
3139       for (; __first != __last; ++__first, (void)++__result)
3140 	if (__pred(__first))
3141 	  *__result = __new_value;
3142 	else
3143 	  *__result = *__first;
3144       return __result;
3145     }
3146 
3147   /**
3148    *  @brief Copy a sequence, replacing each element of one value with another
3149    *         value.
3150    *  @param  __first      An input iterator.
3151    *  @param  __last       An input iterator.
3152    *  @param  __result     An output iterator.
3153    *  @param  __old_value  The value to be replaced.
3154    *  @param  __new_value  The replacement value.
3155    *  @return   The end of the output sequence, @p result+(last-first).
3156    *
3157    *  Copies each element in the input range @p [__first,__last) to the
3158    *  output range @p [__result,__result+(__last-__first)) replacing elements
3159    *  equal to @p __old_value with @p __new_value.
3160   */
3161   template<typename _InputIterator, typename _OutputIterator, typename _Tp>
3162     _GLIBCXX20_CONSTEXPR
3163     inline _OutputIterator
3164     replace_copy(_InputIterator __first, _InputIterator __last,
3165 		 _OutputIterator __result,
3166 		 const _Tp& __old_value, const _Tp& __new_value)
3167     {
3168       // concept requirements
3169       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
3170       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
3171 	    typename iterator_traits<_InputIterator>::value_type>)
3172       __glibcxx_function_requires(_EqualOpConcept<
3173 	    typename iterator_traits<_InputIterator>::value_type, _Tp>)
3174       __glibcxx_requires_valid_range(__first, __last);
3175 
3176       return std::__replace_copy_if(__first, __last, __result,
3177 			__gnu_cxx::__ops::__iter_equals_val(__old_value),
3178 					      __new_value);
3179     }
3180 
3181   /**
3182    *  @brief Copy a sequence, replacing each value for which a predicate
3183    *         returns true with another value.
3184    *  @ingroup mutating_algorithms
3185    *  @param  __first      An input iterator.
3186    *  @param  __last       An input iterator.
3187    *  @param  __result     An output iterator.
3188    *  @param  __pred       A predicate.
3189    *  @param  __new_value  The replacement value.
3190    *  @return   The end of the output sequence, @p __result+(__last-__first).
3191    *
3192    *  Copies each element in the range @p [__first,__last) to the range
3193    *  @p [__result,__result+(__last-__first)) replacing elements for which
3194    *  @p __pred returns true with @p __new_value.
3195   */
3196   template<typename _InputIterator, typename _OutputIterator,
3197 	   typename _Predicate, typename _Tp>
3198     _GLIBCXX20_CONSTEXPR
3199     inline _OutputIterator
3200     replace_copy_if(_InputIterator __first, _InputIterator __last,
3201 		    _OutputIterator __result,
3202 		    _Predicate __pred, const _Tp& __new_value)
3203     {
3204       // concept requirements
3205       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
3206       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
3207 	    typename iterator_traits<_InputIterator>::value_type>)
3208       __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
3209 	    typename iterator_traits<_InputIterator>::value_type>)
3210       __glibcxx_requires_valid_range(__first, __last);
3211 
3212       return std::__replace_copy_if(__first, __last, __result,
3213 				__gnu_cxx::__ops::__pred_iter(__pred),
3214 					      __new_value);
3215     }
3216 
3217 #if __cplusplus >= 201103L
3218   /**
3219    *  @brief  Determines whether the elements of a sequence are sorted.
3220    *  @ingroup sorting_algorithms
3221    *  @param  __first   An iterator.
3222    *  @param  __last    Another iterator.
3223    *  @return  True if the elements are sorted, false otherwise.
3224   */
3225   template<typename _ForwardIterator>
3226     _GLIBCXX20_CONSTEXPR
3227     inline bool
3228     is_sorted(_ForwardIterator __first, _ForwardIterator __last)
3229     { return std::is_sorted_until(__first, __last) == __last; }
3230 
3231   /**
3232    *  @brief  Determines whether the elements of a sequence are sorted
3233    *          according to a comparison functor.
3234    *  @ingroup sorting_algorithms
3235    *  @param  __first   An iterator.
3236    *  @param  __last    Another iterator.
3237    *  @param  __comp    A comparison functor.
3238    *  @return  True if the elements are sorted, false otherwise.
3239   */
3240   template<typename _ForwardIterator, typename _Compare>
3241     _GLIBCXX20_CONSTEXPR
3242     inline bool
3243     is_sorted(_ForwardIterator __first, _ForwardIterator __last,
3244 	      _Compare __comp)
3245     { return std::is_sorted_until(__first, __last, __comp) == __last; }
3246 
3247   template<typename _ForwardIterator, typename _Compare>
3248     _GLIBCXX20_CONSTEXPR
3249     _ForwardIterator
3250     __is_sorted_until(_ForwardIterator __first, _ForwardIterator __last,
3251 		      _Compare __comp)
3252     {
3253       if (__first == __last)
3254 	return __last;
3255 
3256       _ForwardIterator __next = __first;
3257       for (++__next; __next != __last; __first = __next, (void)++__next)
3258 	if (__comp(__next, __first))
3259 	  return __next;
3260       return __next;
3261     }
3262 
3263   /**
3264    *  @brief  Determines the end of a sorted sequence.
3265    *  @ingroup sorting_algorithms
3266    *  @param  __first   An iterator.
3267    *  @param  __last    Another iterator.
3268    *  @return  An iterator pointing to the last iterator i in [__first, __last)
3269    *           for which the range [__first, i) is sorted.
3270   */
3271   template<typename _ForwardIterator>
3272     _GLIBCXX20_CONSTEXPR
3273     inline _ForwardIterator
3274     is_sorted_until(_ForwardIterator __first, _ForwardIterator __last)
3275     {
3276       // concept requirements
3277       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
3278       __glibcxx_function_requires(_LessThanComparableConcept<
3279 	    typename iterator_traits<_ForwardIterator>::value_type>)
3280       __glibcxx_requires_valid_range(__first, __last);
3281       __glibcxx_requires_irreflexive(__first, __last);
3282 
3283       return std::__is_sorted_until(__first, __last,
3284 				    __gnu_cxx::__ops::__iter_less_iter());
3285     }
3286 
3287   /**
3288    *  @brief  Determines the end of a sorted sequence using comparison functor.
3289    *  @ingroup sorting_algorithms
3290    *  @param  __first   An iterator.
3291    *  @param  __last    Another iterator.
3292    *  @param  __comp    A comparison functor.
3293    *  @return  An iterator pointing to the last iterator i in [__first, __last)
3294    *           for which the range [__first, i) is sorted.
3295   */
3296   template<typename _ForwardIterator, typename _Compare>
3297     _GLIBCXX20_CONSTEXPR
3298     inline _ForwardIterator
3299     is_sorted_until(_ForwardIterator __first, _ForwardIterator __last,
3300 		    _Compare __comp)
3301     {
3302       // concept requirements
3303       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
3304       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
3305 	    typename iterator_traits<_ForwardIterator>::value_type,
3306 	    typename iterator_traits<_ForwardIterator>::value_type>)
3307       __glibcxx_requires_valid_range(__first, __last);
3308       __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
3309 
3310       return std::__is_sorted_until(__first, __last,
3311 				    __gnu_cxx::__ops::__iter_comp_iter(__comp));
3312     }
3313 
3314   /**
3315    *  @brief  Determines min and max at once as an ordered pair.
3316    *  @ingroup sorting_algorithms
3317    *  @param  __a  A thing of arbitrary type.
3318    *  @param  __b  Another thing of arbitrary type.
3319    *  @return A pair(__b, __a) if __b is smaller than __a, pair(__a,
3320    *  __b) otherwise.
3321   */
3322   template<typename _Tp>
3323     _GLIBCXX14_CONSTEXPR
3324     inline pair<const _Tp&, const _Tp&>
3325     minmax(const _Tp& __a, const _Tp& __b)
3326     {
3327       // concept requirements
3328       __glibcxx_function_requires(_LessThanComparableConcept<_Tp>)
3329 
3330       return __b < __a ? pair<const _Tp&, const _Tp&>(__b, __a)
3331 		       : pair<const _Tp&, const _Tp&>(__a, __b);
3332     }
3333 
3334   /**
3335    *  @brief  Determines min and max at once as an ordered pair.
3336    *  @ingroup sorting_algorithms
3337    *  @param  __a  A thing of arbitrary type.
3338    *  @param  __b  Another thing of arbitrary type.
3339    *  @param  __comp  A @link comparison_functors comparison functor @endlink.
3340    *  @return A pair(__b, __a) if __b is smaller than __a, pair(__a,
3341    *  __b) otherwise.
3342   */
3343   template<typename _Tp, typename _Compare>
3344     _GLIBCXX14_CONSTEXPR
3345     inline pair<const _Tp&, const _Tp&>
3346     minmax(const _Tp& __a, const _Tp& __b, _Compare __comp)
3347     {
3348       return __comp(__b, __a) ? pair<const _Tp&, const _Tp&>(__b, __a)
3349 			      : pair<const _Tp&, const _Tp&>(__a, __b);
3350     }
3351 
3352   template<typename _ForwardIterator, typename _Compare>
3353     _GLIBCXX14_CONSTEXPR
3354     pair<_ForwardIterator, _ForwardIterator>
3355     __minmax_element(_ForwardIterator __first, _ForwardIterator __last,
3356 		     _Compare __comp)
3357     {
3358       _ForwardIterator __next = __first;
3359       if (__first == __last
3360 	  || ++__next == __last)
3361 	return std::make_pair(__first, __first);
3362 
3363       _ForwardIterator __min{}, __max{};
3364       if (__comp(__next, __first))
3365 	{
3366 	  __min = __next;
3367 	  __max = __first;
3368 	}
3369       else
3370 	{
3371 	  __min = __first;
3372 	  __max = __next;
3373 	}
3374 
3375       __first = __next;
3376       ++__first;
3377 
3378       while (__first != __last)
3379 	{
3380 	  __next = __first;
3381 	  if (++__next == __last)
3382 	    {
3383 	      if (__comp(__first, __min))
3384 		__min = __first;
3385 	      else if (!__comp(__first, __max))
3386 		__max = __first;
3387 	      break;
3388 	    }
3389 
3390 	  if (__comp(__next, __first))
3391 	    {
3392 	      if (__comp(__next, __min))
3393 		__min = __next;
3394 	      if (!__comp(__first, __max))
3395 		__max = __first;
3396 	    }
3397 	  else
3398 	    {
3399 	      if (__comp(__first, __min))
3400 		__min = __first;
3401 	      if (!__comp(__next, __max))
3402 		__max = __next;
3403 	    }
3404 
3405 	  __first = __next;
3406 	  ++__first;
3407 	}
3408 
3409       return std::make_pair(__min, __max);
3410     }
3411 
3412   /**
3413    *  @brief  Return a pair of iterators pointing to the minimum and maximum
3414    *          elements in a range.
3415    *  @ingroup sorting_algorithms
3416    *  @param  __first  Start of range.
3417    *  @param  __last   End of range.
3418    *  @return  make_pair(m, M), where m is the first iterator i in
3419    *           [__first, __last) such that no other element in the range is
3420    *           smaller, and where M is the last iterator i in [__first, __last)
3421    *           such that no other element in the range is larger.
3422   */
3423   template<typename _ForwardIterator>
3424     _GLIBCXX14_CONSTEXPR
3425     inline pair<_ForwardIterator, _ForwardIterator>
3426     minmax_element(_ForwardIterator __first, _ForwardIterator __last)
3427     {
3428       // concept requirements
3429       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
3430       __glibcxx_function_requires(_LessThanComparableConcept<
3431 	    typename iterator_traits<_ForwardIterator>::value_type>)
3432       __glibcxx_requires_valid_range(__first, __last);
3433       __glibcxx_requires_irreflexive(__first, __last);
3434 
3435       return std::__minmax_element(__first, __last,
3436 				   __gnu_cxx::__ops::__iter_less_iter());
3437     }
3438 
3439   /**
3440    *  @brief  Return a pair of iterators pointing to the minimum and maximum
3441    *          elements in a range.
3442    *  @ingroup sorting_algorithms
3443    *  @param  __first  Start of range.
3444    *  @param  __last   End of range.
3445    *  @param  __comp   Comparison functor.
3446    *  @return  make_pair(m, M), where m is the first iterator i in
3447    *           [__first, __last) such that no other element in the range is
3448    *           smaller, and where M is the last iterator i in [__first, __last)
3449    *           such that no other element in the range is larger.
3450   */
3451   template<typename _ForwardIterator, typename _Compare>
3452     _GLIBCXX14_CONSTEXPR
3453     inline pair<_ForwardIterator, _ForwardIterator>
3454     minmax_element(_ForwardIterator __first, _ForwardIterator __last,
3455 		   _Compare __comp)
3456     {
3457       // concept requirements
3458       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
3459       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
3460 	    typename iterator_traits<_ForwardIterator>::value_type,
3461 	    typename iterator_traits<_ForwardIterator>::value_type>)
3462       __glibcxx_requires_valid_range(__first, __last);
3463       __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
3464 
3465       return std::__minmax_element(__first, __last,
3466 				   __gnu_cxx::__ops::__iter_comp_iter(__comp));
3467     }
3468 
3469   // N2722 + DR 915.
3470   template<typename _Tp>
3471     _GLIBCXX14_CONSTEXPR
3472     inline _Tp
3473     min(initializer_list<_Tp> __l)
3474     { return *std::min_element(__l.begin(), __l.end()); }
3475 
3476   template<typename _Tp, typename _Compare>
3477     _GLIBCXX14_CONSTEXPR
3478     inline _Tp
3479     min(initializer_list<_Tp> __l, _Compare __comp)
3480     { return *std::min_element(__l.begin(), __l.end(), __comp); }
3481 
3482   template<typename _Tp>
3483     _GLIBCXX14_CONSTEXPR
3484     inline _Tp
3485     max(initializer_list<_Tp> __l)
3486     { return *std::max_element(__l.begin(), __l.end()); }
3487 
3488   template<typename _Tp, typename _Compare>
3489     _GLIBCXX14_CONSTEXPR
3490     inline _Tp
3491     max(initializer_list<_Tp> __l, _Compare __comp)
3492     { return *std::max_element(__l.begin(), __l.end(), __comp); }
3493 
3494   template<typename _Tp>
3495     _GLIBCXX14_CONSTEXPR
3496     inline pair<_Tp, _Tp>
3497     minmax(initializer_list<_Tp> __l)
3498     {
3499       pair<const _Tp*, const _Tp*> __p =
3500 	std::minmax_element(__l.begin(), __l.end());
3501       return std::make_pair(*__p.first, *__p.second);
3502     }
3503 
3504   template<typename _Tp, typename _Compare>
3505     _GLIBCXX14_CONSTEXPR
3506     inline pair<_Tp, _Tp>
3507     minmax(initializer_list<_Tp> __l, _Compare __comp)
3508     {
3509       pair<const _Tp*, const _Tp*> __p =
3510 	std::minmax_element(__l.begin(), __l.end(), __comp);
3511       return std::make_pair(*__p.first, *__p.second);
3512     }
3513 
3514   /**
3515    *  @brief  Checks whether a permutation of the second sequence is equal
3516    *          to the first sequence.
3517    *  @ingroup non_mutating_algorithms
3518    *  @param  __first1  Start of first range.
3519    *  @param  __last1   End of first range.
3520    *  @param  __first2  Start of second range.
3521    *  @param  __pred    A binary predicate.
3522    *  @return true if there exists a permutation of the elements in
3523    *          the range [__first2, __first2 + (__last1 - __first1)),
3524    *          beginning with ForwardIterator2 begin, such that
3525    *          equal(__first1, __last1, __begin, __pred) returns true;
3526    *          otherwise, returns false.
3527   */
3528   template<typename _ForwardIterator1, typename _ForwardIterator2,
3529 	   typename _BinaryPredicate>
3530     _GLIBCXX20_CONSTEXPR
3531     inline bool
3532     is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
3533 		   _ForwardIterator2 __first2, _BinaryPredicate __pred)
3534     {
3535       // concept requirements
3536       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator1>)
3537       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator2>)
3538       __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
3539 	    typename iterator_traits<_ForwardIterator1>::value_type,
3540 	    typename iterator_traits<_ForwardIterator2>::value_type>)
3541       __glibcxx_requires_valid_range(__first1, __last1);
3542 
3543       return std::__is_permutation(__first1, __last1, __first2,
3544 				   __gnu_cxx::__ops::__iter_comp_iter(__pred));
3545     }
3546 
3547 #if __cplusplus > 201103L
3548   template<typename _ForwardIterator1, typename _ForwardIterator2,
3549 	   typename _BinaryPredicate>
3550     _GLIBCXX20_CONSTEXPR
3551     bool
3552     __is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
3553 		     _ForwardIterator2 __first2, _ForwardIterator2 __last2,
3554 		     _BinaryPredicate __pred)
3555     {
3556       using _Cat1
3557 	= typename iterator_traits<_ForwardIterator1>::iterator_category;
3558       using _Cat2
3559 	= typename iterator_traits<_ForwardIterator2>::iterator_category;
3560       using _It1_is_RA = is_same<_Cat1, random_access_iterator_tag>;
3561       using _It2_is_RA = is_same<_Cat2, random_access_iterator_tag>;
3562       constexpr bool __ra_iters = _It1_is_RA() && _It2_is_RA();
3563       if (__ra_iters)
3564 	{
3565 	  auto __d1 = std::distance(__first1, __last1);
3566 	  auto __d2 = std::distance(__first2, __last2);
3567 	  if (__d1 != __d2)
3568 	    return false;
3569 	}
3570 
3571       // Efficiently compare identical prefixes:  O(N) if sequences
3572       // have the same elements in the same order.
3573       for (; __first1 != __last1 && __first2 != __last2;
3574 	  ++__first1, (void)++__first2)
3575 	if (!__pred(__first1, __first2))
3576 	  break;
3577 
3578       if (__ra_iters)
3579 	{
3580 	  if (__first1 == __last1)
3581 	    return true;
3582 	}
3583       else
3584 	{
3585 	  auto __d1 = std::distance(__first1, __last1);
3586 	  auto __d2 = std::distance(__first2, __last2);
3587 	  if (__d1 == 0 && __d2 == 0)
3588 	    return true;
3589 	  if (__d1 != __d2)
3590 	    return false;
3591 	}
3592 
3593       for (_ForwardIterator1 __scan = __first1; __scan != __last1; ++__scan)
3594 	{
3595 	  if (__scan != std::__find_if(__first1, __scan,
3596 			__gnu_cxx::__ops::__iter_comp_iter(__pred, __scan)))
3597 	    continue; // We've seen this one before.
3598 
3599 	  auto __matches = std::__count_if(__first2, __last2,
3600 		__gnu_cxx::__ops::__iter_comp_iter(__pred, __scan));
3601 	  if (0 == __matches
3602 	      || std::__count_if(__scan, __last1,
3603 			__gnu_cxx::__ops::__iter_comp_iter(__pred, __scan))
3604 	      != __matches)
3605 	    return false;
3606 	}
3607       return true;
3608     }
3609 
3610   /**
3611    *  @brief  Checks whether a permutaion of the second sequence is equal
3612    *          to the first sequence.
3613    *  @ingroup non_mutating_algorithms
3614    *  @param  __first1  Start of first range.
3615    *  @param  __last1   End of first range.
3616    *  @param  __first2  Start of second range.
3617    *  @param  __last2   End of first range.
3618    *  @return true if there exists a permutation of the elements in the range
3619    *          [__first2, __last2), beginning with ForwardIterator2 begin,
3620    *          such that equal(__first1, __last1, begin) returns true;
3621    *          otherwise, returns false.
3622   */
3623   template<typename _ForwardIterator1, typename _ForwardIterator2>
3624     _GLIBCXX20_CONSTEXPR
3625     inline bool
3626     is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
3627 		   _ForwardIterator2 __first2, _ForwardIterator2 __last2)
3628     {
3629       __glibcxx_requires_valid_range(__first1, __last1);
3630       __glibcxx_requires_valid_range(__first2, __last2);
3631 
3632       return
3633 	std::__is_permutation(__first1, __last1, __first2, __last2,
3634 			      __gnu_cxx::__ops::__iter_equal_to_iter());
3635     }
3636 
3637   /**
3638    *  @brief  Checks whether a permutation of the second sequence is equal
3639    *          to the first sequence.
3640    *  @ingroup non_mutating_algorithms
3641    *  @param  __first1  Start of first range.
3642    *  @param  __last1   End of first range.
3643    *  @param  __first2  Start of second range.
3644    *  @param  __last2   End of first range.
3645    *  @param  __pred    A binary predicate.
3646    *  @return true if there exists a permutation of the elements in the range
3647    *          [__first2, __last2), beginning with ForwardIterator2 begin,
3648    *          such that equal(__first1, __last1, __begin, __pred) returns true;
3649    *          otherwise, returns false.
3650   */
3651   template<typename _ForwardIterator1, typename _ForwardIterator2,
3652 	   typename _BinaryPredicate>
3653     _GLIBCXX20_CONSTEXPR
3654     inline bool
3655     is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
3656 		   _ForwardIterator2 __first2, _ForwardIterator2 __last2,
3657 		   _BinaryPredicate __pred)
3658     {
3659       __glibcxx_requires_valid_range(__first1, __last1);
3660       __glibcxx_requires_valid_range(__first2, __last2);
3661 
3662       return std::__is_permutation(__first1, __last1, __first2, __last2,
3663 				   __gnu_cxx::__ops::__iter_comp_iter(__pred));
3664     }
3665 
3666 #if __cplusplus > 201402L
3667 
3668 #define __cpp_lib_clamp 201603
3669 
3670   /**
3671    *  @brief  Returns the value clamped between lo and hi.
3672    *  @ingroup sorting_algorithms
3673    *  @param  __val  A value of arbitrary type.
3674    *  @param  __lo   A lower limit of arbitrary type.
3675    *  @param  __hi   An upper limit of arbitrary type.
3676    *  @return max(__val, __lo) if __val < __hi or min(__val, __hi) otherwise.
3677    */
3678   template<typename _Tp>
3679     constexpr const _Tp&
3680     clamp(const _Tp& __val, const _Tp& __lo, const _Tp& __hi)
3681     {
3682       __glibcxx_assert(!(__hi < __lo));
3683       return (__val < __lo) ? __lo : (__hi < __val) ? __hi : __val;
3684     }
3685 
3686   /**
3687    *  @brief  Returns the value clamped between lo and hi.
3688    *  @ingroup sorting_algorithms
3689    *  @param  __val   A value of arbitrary type.
3690    *  @param  __lo    A lower limit of arbitrary type.
3691    *  @param  __hi    An upper limit of arbitrary type.
3692    *  @param  __comp  A comparison functor.
3693    *  @return max(__val, __lo, __comp) if __comp(__val, __hi)
3694    *	      or min(__val, __hi, __comp) otherwise.
3695    */
3696   template<typename _Tp, typename _Compare>
3697     constexpr const _Tp&
3698     clamp(const _Tp& __val, const _Tp& __lo, const _Tp& __hi, _Compare __comp)
3699     {
3700       __glibcxx_assert(!__comp(__hi, __lo));
3701       return __comp(__val, __lo) ? __lo : __comp(__hi, __val) ? __hi : __val;
3702     }
3703 #endif // C++17
3704 #endif // C++14
3705 
3706 #ifdef _GLIBCXX_USE_C99_STDINT_TR1
3707   /**
3708    *  @brief Generate two uniformly distributed integers using a
3709    *         single distribution invocation.
3710    *  @param  __b0    The upper bound for the first integer.
3711    *  @param  __b1    The upper bound for the second integer.
3712    *  @param  __g     A UniformRandomBitGenerator.
3713    *  @return  A pair (i, j) with i and j uniformly distributed
3714    *           over [0, __b0) and [0, __b1), respectively.
3715    *
3716    *  Requires: __b0 * __b1 <= __g.max() - __g.min().
3717    *
3718    *  Using uniform_int_distribution with a range that is very
3719    *  small relative to the range of the generator ends up wasting
3720    *  potentially expensively generated randomness, since
3721    *  uniform_int_distribution does not store leftover randomness
3722    *  between invocations.
3723    *
3724    *  If we know we want two integers in ranges that are sufficiently
3725    *  small, we can compose the ranges, use a single distribution
3726    *  invocation, and significantly reduce the waste.
3727   */
3728   template<typename _IntType, typename _UniformRandomBitGenerator>
3729     pair<_IntType, _IntType>
3730     __gen_two_uniform_ints(_IntType __b0, _IntType __b1,
3731 			   _UniformRandomBitGenerator&& __g)
3732     {
3733       _IntType __x
3734 	= uniform_int_distribution<_IntType>{0, (__b0 * __b1) - 1}(__g);
3735       return std::make_pair(__x / __b1, __x % __b1);
3736     }
3737 
3738   /**
3739    *  @brief Shuffle the elements of a sequence using a uniform random
3740    *         number generator.
3741    *  @ingroup mutating_algorithms
3742    *  @param  __first   A forward iterator.
3743    *  @param  __last    A forward iterator.
3744    *  @param  __g       A UniformRandomNumberGenerator (26.5.1.3).
3745    *  @return  Nothing.
3746    *
3747    *  Reorders the elements in the range @p [__first,__last) using @p __g to
3748    *  provide random numbers.
3749   */
3750   template<typename _RandomAccessIterator,
3751 	   typename _UniformRandomNumberGenerator>
3752     void
3753     shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last,
3754 	    _UniformRandomNumberGenerator&& __g)
3755     {
3756       // concept requirements
3757       __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
3758 	    _RandomAccessIterator>)
3759       __glibcxx_requires_valid_range(__first, __last);
3760 
3761       if (__first == __last)
3762 	return;
3763 
3764       typedef typename iterator_traits<_RandomAccessIterator>::difference_type
3765 	_DistanceType;
3766 
3767       typedef typename std::make_unsigned<_DistanceType>::type __ud_type;
3768       typedef typename std::uniform_int_distribution<__ud_type> __distr_type;
3769       typedef typename __distr_type::param_type __p_type;
3770 
3771       typedef typename remove_reference<_UniformRandomNumberGenerator>::type
3772 	_Gen;
3773       typedef typename common_type<typename _Gen::result_type, __ud_type>::type
3774 	__uc_type;
3775 
3776       const __uc_type __urngrange = __g.max() - __g.min();
3777       const __uc_type __urange = __uc_type(__last - __first);
3778 
3779       if (__urngrange / __urange >= __urange)
3780         // I.e. (__urngrange >= __urange * __urange) but without wrap issues.
3781       {
3782 	_RandomAccessIterator __i = __first + 1;
3783 
3784 	// Since we know the range isn't empty, an even number of elements
3785 	// means an uneven number of elements /to swap/, in which case we
3786 	// do the first one up front:
3787 
3788 	if ((__urange % 2) == 0)
3789 	{
3790 	  __distr_type __d{0, 1};
3791 	  std::iter_swap(__i++, __first + __d(__g));
3792 	}
3793 
3794 	// Now we know that __last - __i is even, so we do the rest in pairs,
3795 	// using a single distribution invocation to produce swap positions
3796 	// for two successive elements at a time:
3797 
3798 	while (__i != __last)
3799 	{
3800 	  const __uc_type __swap_range = __uc_type(__i - __first) + 1;
3801 
3802 	  const pair<__uc_type, __uc_type> __pospos =
3803 	    __gen_two_uniform_ints(__swap_range, __swap_range + 1, __g);
3804 
3805 	  std::iter_swap(__i++, __first + __pospos.first);
3806 	  std::iter_swap(__i++, __first + __pospos.second);
3807 	}
3808 
3809 	return;
3810       }
3811 
3812       __distr_type __d;
3813 
3814       for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i)
3815 	std::iter_swap(__i, __first + __d(__g, __p_type(0, __i - __first)));
3816     }
3817 #endif
3818 
3819 #endif // C++11
3820 
3821 _GLIBCXX_BEGIN_NAMESPACE_ALGO
3822 
3823   /**
3824    *  @brief Apply a function to every element of a sequence.
3825    *  @ingroup non_mutating_algorithms
3826    *  @param  __first  An input iterator.
3827    *  @param  __last   An input iterator.
3828    *  @param  __f      A unary function object.
3829    *  @return   @p __f
3830    *
3831    *  Applies the function object @p __f to each element in the range
3832    *  @p [first,last).  @p __f must not modify the order of the sequence.
3833    *  If @p __f has a return value it is ignored.
3834   */
3835   template<typename _InputIterator, typename _Function>
3836     _GLIBCXX20_CONSTEXPR
3837     _Function
3838     for_each(_InputIterator __first, _InputIterator __last, _Function __f)
3839     {
3840       // concept requirements
3841       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
3842       __glibcxx_requires_valid_range(__first, __last);
3843       for (; __first != __last; ++__first)
3844 	__f(*__first);
3845       return __f; // N.B. [alg.foreach] says std::move(f) but it's redundant.
3846     }
3847 
3848 #if __cplusplus >= 201703L
3849   /**
3850    *  @brief Apply a function to every element of a sequence.
3851    *  @ingroup non_mutating_algorithms
3852    *  @param  __first  An input iterator.
3853    *  @param  __n      A value convertible to an integer.
3854    *  @param  __f      A unary function object.
3855    *  @return   `__first+__n`
3856    *
3857    *  Applies the function object `__f` to each element in the range
3858    *  `[first, first+n)`.  `__f` must not modify the order of the sequence.
3859    *  If `__f` has a return value it is ignored.
3860   */
3861   template<typename _InputIterator, typename _Size, typename _Function>
3862     _GLIBCXX20_CONSTEXPR
3863     _InputIterator
3864     for_each_n(_InputIterator __first, _Size __n, _Function __f)
3865     {
3866       auto __n2 = std::__size_to_integer(__n);
3867       using _Cat = typename iterator_traits<_InputIterator>::iterator_category;
3868       if constexpr (is_base_of_v<random_access_iterator_tag, _Cat>)
3869 	{
3870 	  if (__n2 <= 0)
3871 	    return __first;
3872 	  auto __last = __first + __n2;
3873 	  std::for_each(__first, __last, std::move(__f));
3874 	  return __last;
3875 	}
3876       else
3877 	{
3878 	  while (__n2-->0)
3879 	    {
3880 	      __f(*__first);
3881 	      ++__first;
3882 	    }
3883 	  return __first;
3884 	}
3885     }
3886 #endif // C++17
3887 
3888   /**
3889    *  @brief Find the first occurrence of a value in a sequence.
3890    *  @ingroup non_mutating_algorithms
3891    *  @param  __first  An input iterator.
3892    *  @param  __last   An input iterator.
3893    *  @param  __val    The value to find.
3894    *  @return   The first iterator @c i in the range @p [__first,__last)
3895    *  such that @c *i == @p __val, or @p __last if no such iterator exists.
3896   */
3897   template<typename _InputIterator, typename _Tp>
3898     _GLIBCXX20_CONSTEXPR
3899     inline _InputIterator
3900     find(_InputIterator __first, _InputIterator __last,
3901 	 const _Tp& __val)
3902     {
3903       // concept requirements
3904       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
3905       __glibcxx_function_requires(_EqualOpConcept<
3906 		typename iterator_traits<_InputIterator>::value_type, _Tp>)
3907       __glibcxx_requires_valid_range(__first, __last);
3908       return std::__find_if(__first, __last,
3909 			    __gnu_cxx::__ops::__iter_equals_val(__val));
3910     }
3911 
3912   /**
3913    *  @brief Find the first element in a sequence for which a
3914    *         predicate is true.
3915    *  @ingroup non_mutating_algorithms
3916    *  @param  __first  An input iterator.
3917    *  @param  __last   An input iterator.
3918    *  @param  __pred   A predicate.
3919    *  @return   The first iterator @c i in the range @p [__first,__last)
3920    *  such that @p __pred(*i) is true, or @p __last if no such iterator exists.
3921   */
3922   template<typename _InputIterator, typename _Predicate>
3923     _GLIBCXX20_CONSTEXPR
3924     inline _InputIterator
3925     find_if(_InputIterator __first, _InputIterator __last,
3926 	    _Predicate __pred)
3927     {
3928       // concept requirements
3929       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
3930       __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
3931 	      typename iterator_traits<_InputIterator>::value_type>)
3932       __glibcxx_requires_valid_range(__first, __last);
3933 
3934       return std::__find_if(__first, __last,
3935 			    __gnu_cxx::__ops::__pred_iter(__pred));
3936     }
3937 
3938   /**
3939    *  @brief  Find element from a set in a sequence.
3940    *  @ingroup non_mutating_algorithms
3941    *  @param  __first1  Start of range to search.
3942    *  @param  __last1   End of range to search.
3943    *  @param  __first2  Start of match candidates.
3944    *  @param  __last2   End of match candidates.
3945    *  @return   The first iterator @c i in the range
3946    *  @p [__first1,__last1) such that @c *i == @p *(i2) such that i2 is an
3947    *  iterator in [__first2,__last2), or @p __last1 if no such iterator exists.
3948    *
3949    *  Searches the range @p [__first1,__last1) for an element that is
3950    *  equal to some element in the range [__first2,__last2).  If
3951    *  found, returns an iterator in the range [__first1,__last1),
3952    *  otherwise returns @p __last1.
3953   */
3954   template<typename _InputIterator, typename _ForwardIterator>
3955     _GLIBCXX20_CONSTEXPR
3956     _InputIterator
3957     find_first_of(_InputIterator __first1, _InputIterator __last1,
3958 		  _ForwardIterator __first2, _ForwardIterator __last2)
3959     {
3960       // concept requirements
3961       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
3962       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
3963       __glibcxx_function_requires(_EqualOpConcept<
3964 	    typename iterator_traits<_InputIterator>::value_type,
3965 	    typename iterator_traits<_ForwardIterator>::value_type>)
3966       __glibcxx_requires_valid_range(__first1, __last1);
3967       __glibcxx_requires_valid_range(__first2, __last2);
3968 
3969       for (; __first1 != __last1; ++__first1)
3970 	for (_ForwardIterator __iter = __first2; __iter != __last2; ++__iter)
3971 	  if (*__first1 == *__iter)
3972 	    return __first1;
3973       return __last1;
3974     }
3975 
3976   /**
3977    *  @brief  Find element from a set in a sequence using a predicate.
3978    *  @ingroup non_mutating_algorithms
3979    *  @param  __first1  Start of range to search.
3980    *  @param  __last1   End of range to search.
3981    *  @param  __first2  Start of match candidates.
3982    *  @param  __last2   End of match candidates.
3983    *  @param  __comp    Predicate to use.
3984    *  @return   The first iterator @c i in the range
3985    *  @p [__first1,__last1) such that @c comp(*i, @p *(i2)) is true
3986    *  and i2 is an iterator in [__first2,__last2), or @p __last1 if no
3987    *  such iterator exists.
3988    *
3989 
3990    *  Searches the range @p [__first1,__last1) for an element that is
3991    *  equal to some element in the range [__first2,__last2).  If
3992    *  found, returns an iterator in the range [__first1,__last1),
3993    *  otherwise returns @p __last1.
3994   */
3995   template<typename _InputIterator, typename _ForwardIterator,
3996 	   typename _BinaryPredicate>
3997     _GLIBCXX20_CONSTEXPR
3998     _InputIterator
3999     find_first_of(_InputIterator __first1, _InputIterator __last1,
4000 		  _ForwardIterator __first2, _ForwardIterator __last2,
4001 		  _BinaryPredicate __comp)
4002     {
4003       // concept requirements
4004       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
4005       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
4006       __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
4007 	    typename iterator_traits<_InputIterator>::value_type,
4008 	    typename iterator_traits<_ForwardIterator>::value_type>)
4009       __glibcxx_requires_valid_range(__first1, __last1);
4010       __glibcxx_requires_valid_range(__first2, __last2);
4011 
4012       for (; __first1 != __last1; ++__first1)
4013 	for (_ForwardIterator __iter = __first2; __iter != __last2; ++__iter)
4014 	  if (__comp(*__first1, *__iter))
4015 	    return __first1;
4016       return __last1;
4017     }
4018 
4019   /**
4020    *  @brief Find two adjacent values in a sequence that are equal.
4021    *  @ingroup non_mutating_algorithms
4022    *  @param  __first  A forward iterator.
4023    *  @param  __last   A forward iterator.
4024    *  @return   The first iterator @c i such that @c i and @c i+1 are both
4025    *  valid iterators in @p [__first,__last) and such that @c *i == @c *(i+1),
4026    *  or @p __last if no such iterator exists.
4027   */
4028   template<typename _ForwardIterator>
4029     _GLIBCXX20_CONSTEXPR
4030     inline _ForwardIterator
4031     adjacent_find(_ForwardIterator __first, _ForwardIterator __last)
4032     {
4033       // concept requirements
4034       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
4035       __glibcxx_function_requires(_EqualityComparableConcept<
4036 	    typename iterator_traits<_ForwardIterator>::value_type>)
4037       __glibcxx_requires_valid_range(__first, __last);
4038 
4039       return std::__adjacent_find(__first, __last,
4040 				  __gnu_cxx::__ops::__iter_equal_to_iter());
4041     }
4042 
4043   /**
4044    *  @brief Find two adjacent values in a sequence using a predicate.
4045    *  @ingroup non_mutating_algorithms
4046    *  @param  __first         A forward iterator.
4047    *  @param  __last          A forward iterator.
4048    *  @param  __binary_pred   A binary predicate.
4049    *  @return   The first iterator @c i such that @c i and @c i+1 are both
4050    *  valid iterators in @p [__first,__last) and such that
4051    *  @p __binary_pred(*i,*(i+1)) is true, or @p __last if no such iterator
4052    *  exists.
4053   */
4054   template<typename _ForwardIterator, typename _BinaryPredicate>
4055     _GLIBCXX20_CONSTEXPR
4056     inline _ForwardIterator
4057     adjacent_find(_ForwardIterator __first, _ForwardIterator __last,
4058 		  _BinaryPredicate __binary_pred)
4059     {
4060       // concept requirements
4061       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
4062       __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
4063 	    typename iterator_traits<_ForwardIterator>::value_type,
4064 	    typename iterator_traits<_ForwardIterator>::value_type>)
4065       __glibcxx_requires_valid_range(__first, __last);
4066 
4067       return std::__adjacent_find(__first, __last,
4068 			__gnu_cxx::__ops::__iter_comp_iter(__binary_pred));
4069     }
4070 
4071   /**
4072    *  @brief Count the number of copies of a value in a sequence.
4073    *  @ingroup non_mutating_algorithms
4074    *  @param  __first  An input iterator.
4075    *  @param  __last   An input iterator.
4076    *  @param  __value  The value to be counted.
4077    *  @return   The number of iterators @c i in the range @p [__first,__last)
4078    *  for which @c *i == @p __value
4079   */
4080   template<typename _InputIterator, typename _Tp>
4081     _GLIBCXX20_CONSTEXPR
4082     inline typename iterator_traits<_InputIterator>::difference_type
4083     count(_InputIterator __first, _InputIterator __last, const _Tp& __value)
4084     {
4085       // concept requirements
4086       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
4087       __glibcxx_function_requires(_EqualOpConcept<
4088 	    typename iterator_traits<_InputIterator>::value_type, _Tp>)
4089       __glibcxx_requires_valid_range(__first, __last);
4090 
4091       return std::__count_if(__first, __last,
4092 			     __gnu_cxx::__ops::__iter_equals_val(__value));
4093     }
4094 
4095   /**
4096    *  @brief Count the elements of a sequence for which a predicate is true.
4097    *  @ingroup non_mutating_algorithms
4098    *  @param  __first  An input iterator.
4099    *  @param  __last   An input iterator.
4100    *  @param  __pred   A predicate.
4101    *  @return   The number of iterators @c i in the range @p [__first,__last)
4102    *  for which @p __pred(*i) is true.
4103   */
4104   template<typename _InputIterator, typename _Predicate>
4105     _GLIBCXX20_CONSTEXPR
4106     inline typename iterator_traits<_InputIterator>::difference_type
4107     count_if(_InputIterator __first, _InputIterator __last, _Predicate __pred)
4108     {
4109       // concept requirements
4110       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
4111       __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
4112 	    typename iterator_traits<_InputIterator>::value_type>)
4113       __glibcxx_requires_valid_range(__first, __last);
4114 
4115       return std::__count_if(__first, __last,
4116 			     __gnu_cxx::__ops::__pred_iter(__pred));
4117     }
4118 
4119   /**
4120    *  @brief Search a sequence for a matching sub-sequence.
4121    *  @ingroup non_mutating_algorithms
4122    *  @param  __first1  A forward iterator.
4123    *  @param  __last1   A forward iterator.
4124    *  @param  __first2  A forward iterator.
4125    *  @param  __last2   A forward iterator.
4126    *  @return The first iterator @c i in the range @p
4127    *  [__first1,__last1-(__last2-__first2)) such that @c *(i+N) == @p
4128    *  *(__first2+N) for each @c N in the range @p
4129    *  [0,__last2-__first2), or @p __last1 if no such iterator exists.
4130    *
4131    *  Searches the range @p [__first1,__last1) for a sub-sequence that
4132    *  compares equal value-by-value with the sequence given by @p
4133    *  [__first2,__last2) and returns an iterator to the first element
4134    *  of the sub-sequence, or @p __last1 if the sub-sequence is not
4135    *  found.
4136    *
4137    *  Because the sub-sequence must lie completely within the range @p
4138    *  [__first1,__last1) it must start at a position less than @p
4139    *  __last1-(__last2-__first2) where @p __last2-__first2 is the
4140    *  length of the sub-sequence.
4141    *
4142    *  This means that the returned iterator @c i will be in the range
4143    *  @p [__first1,__last1-(__last2-__first2))
4144   */
4145   template<typename _ForwardIterator1, typename _ForwardIterator2>
4146     _GLIBCXX20_CONSTEXPR
4147     inline _ForwardIterator1
4148     search(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
4149 	   _ForwardIterator2 __first2, _ForwardIterator2 __last2)
4150     {
4151       // concept requirements
4152       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator1>)
4153       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator2>)
4154       __glibcxx_function_requires(_EqualOpConcept<
4155 	    typename iterator_traits<_ForwardIterator1>::value_type,
4156 	    typename iterator_traits<_ForwardIterator2>::value_type>)
4157       __glibcxx_requires_valid_range(__first1, __last1);
4158       __glibcxx_requires_valid_range(__first2, __last2);
4159 
4160       return std::__search(__first1, __last1, __first2, __last2,
4161 			   __gnu_cxx::__ops::__iter_equal_to_iter());
4162     }
4163 
4164   /**
4165    *  @brief Search a sequence for a matching sub-sequence using a predicate.
4166    *  @ingroup non_mutating_algorithms
4167    *  @param  __first1     A forward iterator.
4168    *  @param  __last1      A forward iterator.
4169    *  @param  __first2     A forward iterator.
4170    *  @param  __last2      A forward iterator.
4171    *  @param  __predicate  A binary predicate.
4172    *  @return   The first iterator @c i in the range
4173    *  @p [__first1,__last1-(__last2-__first2)) such that
4174    *  @p __predicate(*(i+N),*(__first2+N)) is true for each @c N in the range
4175    *  @p [0,__last2-__first2), or @p __last1 if no such iterator exists.
4176    *
4177    *  Searches the range @p [__first1,__last1) for a sub-sequence that
4178    *  compares equal value-by-value with the sequence given by @p
4179    *  [__first2,__last2), using @p __predicate to determine equality,
4180    *  and returns an iterator to the first element of the
4181    *  sub-sequence, or @p __last1 if no such iterator exists.
4182    *
4183    *  @see search(_ForwardIter1, _ForwardIter1, _ForwardIter2, _ForwardIter2)
4184   */
4185   template<typename _ForwardIterator1, typename _ForwardIterator2,
4186 	   typename _BinaryPredicate>
4187     _GLIBCXX20_CONSTEXPR
4188     inline _ForwardIterator1
4189     search(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
4190 	   _ForwardIterator2 __first2, _ForwardIterator2 __last2,
4191 	   _BinaryPredicate  __predicate)
4192     {
4193       // concept requirements
4194       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator1>)
4195       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator2>)
4196       __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
4197 	    typename iterator_traits<_ForwardIterator1>::value_type,
4198 	    typename iterator_traits<_ForwardIterator2>::value_type>)
4199       __glibcxx_requires_valid_range(__first1, __last1);
4200       __glibcxx_requires_valid_range(__first2, __last2);
4201 
4202       return std::__search(__first1, __last1, __first2, __last2,
4203 			   __gnu_cxx::__ops::__iter_comp_iter(__predicate));
4204     }
4205 
4206   /**
4207    *  @brief Search a sequence for a number of consecutive values.
4208    *  @ingroup non_mutating_algorithms
4209    *  @param  __first  A forward iterator.
4210    *  @param  __last   A forward iterator.
4211    *  @param  __count  The number of consecutive values.
4212    *  @param  __val    The value to find.
4213    *  @return The first iterator @c i in the range @p
4214    *  [__first,__last-__count) such that @c *(i+N) == @p __val for
4215    *  each @c N in the range @p [0,__count), or @p __last if no such
4216    *  iterator exists.
4217    *
4218    *  Searches the range @p [__first,__last) for @p count consecutive elements
4219    *  equal to @p __val.
4220   */
4221   template<typename _ForwardIterator, typename _Integer, typename _Tp>
4222     _GLIBCXX20_CONSTEXPR
4223     inline _ForwardIterator
4224     search_n(_ForwardIterator __first, _ForwardIterator __last,
4225 	     _Integer __count, const _Tp& __val)
4226     {
4227       // concept requirements
4228       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
4229       __glibcxx_function_requires(_EqualOpConcept<
4230 	    typename iterator_traits<_ForwardIterator>::value_type, _Tp>)
4231       __glibcxx_requires_valid_range(__first, __last);
4232 
4233       return std::__search_n(__first, __last, __count,
4234 			     __gnu_cxx::__ops::__iter_equals_val(__val));
4235     }
4236 
4237 
4238   /**
4239    *  @brief Search a sequence for a number of consecutive values using a
4240    *         predicate.
4241    *  @ingroup non_mutating_algorithms
4242    *  @param  __first        A forward iterator.
4243    *  @param  __last         A forward iterator.
4244    *  @param  __count        The number of consecutive values.
4245    *  @param  __val          The value to find.
4246    *  @param  __binary_pred  A binary predicate.
4247    *  @return The first iterator @c i in the range @p
4248    *  [__first,__last-__count) such that @p
4249    *  __binary_pred(*(i+N),__val) is true for each @c N in the range
4250    *  @p [0,__count), or @p __last if no such iterator exists.
4251    *
4252    *  Searches the range @p [__first,__last) for @p __count
4253    *  consecutive elements for which the predicate returns true.
4254   */
4255   template<typename _ForwardIterator, typename _Integer, typename _Tp,
4256 	   typename _BinaryPredicate>
4257     _GLIBCXX20_CONSTEXPR
4258     inline _ForwardIterator
4259     search_n(_ForwardIterator __first, _ForwardIterator __last,
4260 	     _Integer __count, const _Tp& __val,
4261 	     _BinaryPredicate __binary_pred)
4262     {
4263       // concept requirements
4264       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
4265       __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
4266 	    typename iterator_traits<_ForwardIterator>::value_type, _Tp>)
4267       __glibcxx_requires_valid_range(__first, __last);
4268 
4269       return std::__search_n(__first, __last, __count,
4270 		__gnu_cxx::__ops::__iter_comp_val(__binary_pred, __val));
4271     }
4272 
4273 #if __cplusplus > 201402L
4274   /** @brief Search a sequence using a Searcher object.
4275    *
4276    *  @param  __first        A forward iterator.
4277    *  @param  __last         A forward iterator.
4278    *  @param  __searcher     A callable object.
4279    *  @return @p __searcher(__first,__last).first
4280   */
4281   template<typename _ForwardIterator, typename _Searcher>
4282     _GLIBCXX20_CONSTEXPR
4283     inline _ForwardIterator
4284     search(_ForwardIterator __first, _ForwardIterator __last,
4285 	   const _Searcher& __searcher)
4286     { return __searcher(__first, __last).first; }
4287 #endif
4288 
4289   /**
4290    *  @brief Perform an operation on a sequence.
4291    *  @ingroup mutating_algorithms
4292    *  @param  __first     An input iterator.
4293    *  @param  __last      An input iterator.
4294    *  @param  __result    An output iterator.
4295    *  @param  __unary_op  A unary operator.
4296    *  @return   An output iterator equal to @p __result+(__last-__first).
4297    *
4298    *  Applies the operator to each element in the input range and assigns
4299    *  the results to successive elements of the output sequence.
4300    *  Evaluates @p *(__result+N)=unary_op(*(__first+N)) for each @c N in the
4301    *  range @p [0,__last-__first).
4302    *
4303    *  @p unary_op must not alter its argument.
4304   */
4305   template<typename _InputIterator, typename _OutputIterator,
4306 	   typename _UnaryOperation>
4307     _GLIBCXX20_CONSTEXPR
4308     _OutputIterator
4309     transform(_InputIterator __first, _InputIterator __last,
4310 	      _OutputIterator __result, _UnaryOperation __unary_op)
4311     {
4312       // concept requirements
4313       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
4314       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
4315 	    // "the type returned by a _UnaryOperation"
4316 	    __typeof__(__unary_op(*__first))>)
4317       __glibcxx_requires_valid_range(__first, __last);
4318 
4319       for (; __first != __last; ++__first, (void)++__result)
4320 	*__result = __unary_op(*__first);
4321       return __result;
4322     }
4323 
4324   /**
4325    *  @brief Perform an operation on corresponding elements of two sequences.
4326    *  @ingroup mutating_algorithms
4327    *  @param  __first1     An input iterator.
4328    *  @param  __last1      An input iterator.
4329    *  @param  __first2     An input iterator.
4330    *  @param  __result     An output iterator.
4331    *  @param  __binary_op  A binary operator.
4332    *  @return   An output iterator equal to @p result+(last-first).
4333    *
4334    *  Applies the operator to the corresponding elements in the two
4335    *  input ranges and assigns the results to successive elements of the
4336    *  output sequence.
4337    *  Evaluates @p
4338    *  *(__result+N)=__binary_op(*(__first1+N),*(__first2+N)) for each
4339    *  @c N in the range @p [0,__last1-__first1).
4340    *
4341    *  @p binary_op must not alter either of its arguments.
4342   */
4343   template<typename _InputIterator1, typename _InputIterator2,
4344 	   typename _OutputIterator, typename _BinaryOperation>
4345     _GLIBCXX20_CONSTEXPR
4346     _OutputIterator
4347     transform(_InputIterator1 __first1, _InputIterator1 __last1,
4348 	      _InputIterator2 __first2, _OutputIterator __result,
4349 	      _BinaryOperation __binary_op)
4350     {
4351       // concept requirements
4352       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
4353       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
4354       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
4355 	    // "the type returned by a _BinaryOperation"
4356 	    __typeof__(__binary_op(*__first1,*__first2))>)
4357       __glibcxx_requires_valid_range(__first1, __last1);
4358 
4359       for (; __first1 != __last1; ++__first1, (void)++__first2, ++__result)
4360 	*__result = __binary_op(*__first1, *__first2);
4361       return __result;
4362     }
4363 
4364   /**
4365    *  @brief Replace each occurrence of one value in a sequence with another
4366    *         value.
4367    *  @ingroup mutating_algorithms
4368    *  @param  __first      A forward iterator.
4369    *  @param  __last       A forward iterator.
4370    *  @param  __old_value  The value to be replaced.
4371    *  @param  __new_value  The replacement value.
4372    *  @return   replace() returns no value.
4373    *
4374    *  For each iterator @c i in the range @p [__first,__last) if @c *i ==
4375    *  @p __old_value then the assignment @c *i = @p __new_value is performed.
4376   */
4377   template<typename _ForwardIterator, typename _Tp>
4378     _GLIBCXX20_CONSTEXPR
4379     void
4380     replace(_ForwardIterator __first, _ForwardIterator __last,
4381 	    const _Tp& __old_value, const _Tp& __new_value)
4382     {
4383       // concept requirements
4384       __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
4385 				  _ForwardIterator>)
4386       __glibcxx_function_requires(_EqualOpConcept<
4387 	    typename iterator_traits<_ForwardIterator>::value_type, _Tp>)
4388       __glibcxx_function_requires(_ConvertibleConcept<_Tp,
4389 	    typename iterator_traits<_ForwardIterator>::value_type>)
4390       __glibcxx_requires_valid_range(__first, __last);
4391 
4392       for (; __first != __last; ++__first)
4393 	if (*__first == __old_value)
4394 	  *__first = __new_value;
4395     }
4396 
4397   /**
4398    *  @brief Replace each value in a sequence for which a predicate returns
4399    *         true with another value.
4400    *  @ingroup mutating_algorithms
4401    *  @param  __first      A forward iterator.
4402    *  @param  __last       A forward iterator.
4403    *  @param  __pred       A predicate.
4404    *  @param  __new_value  The replacement value.
4405    *  @return   replace_if() returns no value.
4406    *
4407    *  For each iterator @c i in the range @p [__first,__last) if @p __pred(*i)
4408    *  is true then the assignment @c *i = @p __new_value is performed.
4409   */
4410   template<typename _ForwardIterator, typename _Predicate, typename _Tp>
4411     _GLIBCXX20_CONSTEXPR
4412     void
4413     replace_if(_ForwardIterator __first, _ForwardIterator __last,
4414 	       _Predicate __pred, const _Tp& __new_value)
4415     {
4416       // concept requirements
4417       __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
4418 				  _ForwardIterator>)
4419       __glibcxx_function_requires(_ConvertibleConcept<_Tp,
4420 	    typename iterator_traits<_ForwardIterator>::value_type>)
4421       __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
4422 	    typename iterator_traits<_ForwardIterator>::value_type>)
4423       __glibcxx_requires_valid_range(__first, __last);
4424 
4425       for (; __first != __last; ++__first)
4426 	if (__pred(*__first))
4427 	  *__first = __new_value;
4428     }
4429 
4430   /**
4431    *  @brief Assign the result of a function object to each value in a
4432    *         sequence.
4433    *  @ingroup mutating_algorithms
4434    *  @param  __first  A forward iterator.
4435    *  @param  __last   A forward iterator.
4436    *  @param  __gen    A function object taking no arguments and returning
4437    *                 std::iterator_traits<_ForwardIterator>::value_type
4438    *  @return   generate() returns no value.
4439    *
4440    *  Performs the assignment @c *i = @p __gen() for each @c i in the range
4441    *  @p [__first,__last).
4442   */
4443   template<typename _ForwardIterator, typename _Generator>
4444     _GLIBCXX20_CONSTEXPR
4445     void
4446     generate(_ForwardIterator __first, _ForwardIterator __last,
4447 	     _Generator __gen)
4448     {
4449       // concept requirements
4450       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
4451       __glibcxx_function_requires(_GeneratorConcept<_Generator,
4452 	    typename iterator_traits<_ForwardIterator>::value_type>)
4453       __glibcxx_requires_valid_range(__first, __last);
4454 
4455       for (; __first != __last; ++__first)
4456 	*__first = __gen();
4457     }
4458 
4459   /**
4460    *  @brief Assign the result of a function object to each value in a
4461    *         sequence.
4462    *  @ingroup mutating_algorithms
4463    *  @param  __first  A forward iterator.
4464    *  @param  __n      The length of the sequence.
4465    *  @param  __gen    A function object taking no arguments and returning
4466    *                 std::iterator_traits<_ForwardIterator>::value_type
4467    *  @return   The end of the sequence, @p __first+__n
4468    *
4469    *  Performs the assignment @c *i = @p __gen() for each @c i in the range
4470    *  @p [__first,__first+__n).
4471    *
4472    * If @p __n is negative, the function does nothing and returns @p __first.
4473   */
4474   // _GLIBCXX_RESOLVE_LIB_DEFECTS
4475   // DR 865. More algorithms that throw away information
4476   // DR 426. search_n(), fill_n(), and generate_n() with negative n
4477   template<typename _OutputIterator, typename _Size, typename _Generator>
4478     _GLIBCXX20_CONSTEXPR
4479     _OutputIterator
4480     generate_n(_OutputIterator __first, _Size __n, _Generator __gen)
4481     {
4482       // concept requirements
4483       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
4484 	    // "the type returned by a _Generator"
4485 	    __typeof__(__gen())>)
4486 
4487       typedef __decltype(std::__size_to_integer(__n)) _IntSize;
4488       for (_IntSize __niter = std::__size_to_integer(__n);
4489 	   __niter > 0; --__niter, (void) ++__first)
4490 	*__first = __gen();
4491       return __first;
4492     }
4493 
4494   /**
4495    *  @brief Copy a sequence, removing consecutive duplicate values.
4496    *  @ingroup mutating_algorithms
4497    *  @param  __first   An input iterator.
4498    *  @param  __last    An input iterator.
4499    *  @param  __result  An output iterator.
4500    *  @return   An iterator designating the end of the resulting sequence.
4501    *
4502    *  Copies each element in the range @p [__first,__last) to the range
4503    *  beginning at @p __result, except that only the first element is copied
4504    *  from groups of consecutive elements that compare equal.
4505    *  unique_copy() is stable, so the relative order of elements that are
4506    *  copied is unchanged.
4507    *
4508    *  _GLIBCXX_RESOLVE_LIB_DEFECTS
4509    *  DR 241. Does unique_copy() require CopyConstructible and Assignable?
4510    *
4511    *  _GLIBCXX_RESOLVE_LIB_DEFECTS
4512    *  DR 538. 241 again: Does unique_copy() require CopyConstructible and
4513    *  Assignable?
4514   */
4515   template<typename _InputIterator, typename _OutputIterator>
4516     _GLIBCXX20_CONSTEXPR
4517     inline _OutputIterator
4518     unique_copy(_InputIterator __first, _InputIterator __last,
4519 		_OutputIterator __result)
4520     {
4521       // concept requirements
4522       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
4523       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
4524 	    typename iterator_traits<_InputIterator>::value_type>)
4525       __glibcxx_function_requires(_EqualityComparableConcept<
4526 	    typename iterator_traits<_InputIterator>::value_type>)
4527       __glibcxx_requires_valid_range(__first, __last);
4528 
4529       if (__first == __last)
4530 	return __result;
4531       return std::__unique_copy(__first, __last, __result,
4532 				__gnu_cxx::__ops::__iter_equal_to_iter(),
4533 				std::__iterator_category(__first),
4534 				std::__iterator_category(__result));
4535     }
4536 
4537   /**
4538    *  @brief Copy a sequence, removing consecutive values using a predicate.
4539    *  @ingroup mutating_algorithms
4540    *  @param  __first        An input iterator.
4541    *  @param  __last         An input iterator.
4542    *  @param  __result       An output iterator.
4543    *  @param  __binary_pred  A binary predicate.
4544    *  @return   An iterator designating the end of the resulting sequence.
4545    *
4546    *  Copies each element in the range @p [__first,__last) to the range
4547    *  beginning at @p __result, except that only the first element is copied
4548    *  from groups of consecutive elements for which @p __binary_pred returns
4549    *  true.
4550    *  unique_copy() is stable, so the relative order of elements that are
4551    *  copied is unchanged.
4552    *
4553    *  _GLIBCXX_RESOLVE_LIB_DEFECTS
4554    *  DR 241. Does unique_copy() require CopyConstructible and Assignable?
4555   */
4556   template<typename _InputIterator, typename _OutputIterator,
4557 	   typename _BinaryPredicate>
4558     _GLIBCXX20_CONSTEXPR
4559     inline _OutputIterator
4560     unique_copy(_InputIterator __first, _InputIterator __last,
4561 		_OutputIterator __result,
4562 		_BinaryPredicate __binary_pred)
4563     {
4564       // concept requirements -- predicates checked later
4565       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
4566       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
4567 	    typename iterator_traits<_InputIterator>::value_type>)
4568       __glibcxx_requires_valid_range(__first, __last);
4569 
4570       if (__first == __last)
4571 	return __result;
4572       return std::__unique_copy(__first, __last, __result,
4573 			__gnu_cxx::__ops::__iter_comp_iter(__binary_pred),
4574 				std::__iterator_category(__first),
4575 				std::__iterator_category(__result));
4576     }
4577 
4578 #if _GLIBCXX_HOSTED
4579   /**
4580    *  @brief Randomly shuffle the elements of a sequence.
4581    *  @ingroup mutating_algorithms
4582    *  @param  __first   A forward iterator.
4583    *  @param  __last    A forward iterator.
4584    *  @return  Nothing.
4585    *
4586    *  Reorder the elements in the range @p [__first,__last) using a random
4587    *  distribution, so that every possible ordering of the sequence is
4588    *  equally likely.
4589   */
4590   template<typename _RandomAccessIterator>
4591     inline void
4592     random_shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last)
4593     {
4594       // concept requirements
4595       __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
4596 	    _RandomAccessIterator>)
4597       __glibcxx_requires_valid_range(__first, __last);
4598 
4599       if (__first != __last)
4600 	for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i)
4601 	  {
4602 	    // XXX rand() % N is not uniformly distributed
4603 	    _RandomAccessIterator __j = __first
4604 					+ std::rand() % ((__i - __first) + 1);
4605 	    if (__i != __j)
4606 	      std::iter_swap(__i, __j);
4607 	  }
4608     }
4609 #endif
4610 
4611   /**
4612    *  @brief Shuffle the elements of a sequence using a random number
4613    *         generator.
4614    *  @ingroup mutating_algorithms
4615    *  @param  __first   A forward iterator.
4616    *  @param  __last    A forward iterator.
4617    *  @param  __rand    The RNG functor or function.
4618    *  @return  Nothing.
4619    *
4620    *  Reorders the elements in the range @p [__first,__last) using @p __rand to
4621    *  provide a random distribution. Calling @p __rand(N) for a positive
4622    *  integer @p N should return a randomly chosen integer from the
4623    *  range [0,N).
4624   */
4625   template<typename _RandomAccessIterator, typename _RandomNumberGenerator>
4626     void
4627     random_shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last,
4628 #if __cplusplus >= 201103L
4629 		   _RandomNumberGenerator&& __rand)
4630 #else
4631 		   _RandomNumberGenerator& __rand)
4632 #endif
4633     {
4634       // concept requirements
4635       __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
4636 	    _RandomAccessIterator>)
4637       __glibcxx_requires_valid_range(__first, __last);
4638 
4639       if (__first == __last)
4640 	return;
4641       for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i)
4642 	{
4643 	  _RandomAccessIterator __j = __first + __rand((__i - __first) + 1);
4644 	  if (__i != __j)
4645 	    std::iter_swap(__i, __j);
4646 	}
4647     }
4648 
4649 
4650   /**
4651    *  @brief Move elements for which a predicate is true to the beginning
4652    *         of a sequence.
4653    *  @ingroup mutating_algorithms
4654    *  @param  __first   A forward iterator.
4655    *  @param  __last    A forward iterator.
4656    *  @param  __pred    A predicate functor.
4657    *  @return  An iterator @p middle such that @p __pred(i) is true for each
4658    *  iterator @p i in the range @p [__first,middle) and false for each @p i
4659    *  in the range @p [middle,__last).
4660    *
4661    *  @p __pred must not modify its operand. @p partition() does not preserve
4662    *  the relative ordering of elements in each group, use
4663    *  @p stable_partition() if this is needed.
4664   */
4665   template<typename _ForwardIterator, typename _Predicate>
4666     _GLIBCXX20_CONSTEXPR
4667     inline _ForwardIterator
4668     partition(_ForwardIterator __first, _ForwardIterator __last,
4669 	      _Predicate   __pred)
4670     {
4671       // concept requirements
4672       __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
4673 				  _ForwardIterator>)
4674       __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
4675 	    typename iterator_traits<_ForwardIterator>::value_type>)
4676       __glibcxx_requires_valid_range(__first, __last);
4677 
4678       return std::__partition(__first, __last, __pred,
4679 			      std::__iterator_category(__first));
4680     }
4681 
4682 
4683   /**
4684    *  @brief Sort the smallest elements of a sequence.
4685    *  @ingroup sorting_algorithms
4686    *  @param  __first   An iterator.
4687    *  @param  __middle  Another iterator.
4688    *  @param  __last    Another iterator.
4689    *  @return  Nothing.
4690    *
4691    *  Sorts the smallest @p (__middle-__first) elements in the range
4692    *  @p [first,last) and moves them to the range @p [__first,__middle). The
4693    *  order of the remaining elements in the range @p [__middle,__last) is
4694    *  undefined.
4695    *  After the sort if @e i and @e j are iterators in the range
4696    *  @p [__first,__middle) such that i precedes j and @e k is an iterator in
4697    *  the range @p [__middle,__last) then *j<*i and *k<*i are both false.
4698   */
4699   template<typename _RandomAccessIterator>
4700     _GLIBCXX20_CONSTEXPR
4701     inline void
4702     partial_sort(_RandomAccessIterator __first,
4703 		 _RandomAccessIterator __middle,
4704 		 _RandomAccessIterator __last)
4705     {
4706       // concept requirements
4707       __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
4708 	    _RandomAccessIterator>)
4709       __glibcxx_function_requires(_LessThanComparableConcept<
4710 	    typename iterator_traits<_RandomAccessIterator>::value_type>)
4711       __glibcxx_requires_valid_range(__first, __middle);
4712       __glibcxx_requires_valid_range(__middle, __last);
4713       __glibcxx_requires_irreflexive(__first, __last);
4714 
4715       std::__partial_sort(__first, __middle, __last,
4716 			  __gnu_cxx::__ops::__iter_less_iter());
4717     }
4718 
4719   /**
4720    *  @brief Sort the smallest elements of a sequence using a predicate
4721    *         for comparison.
4722    *  @ingroup sorting_algorithms
4723    *  @param  __first   An iterator.
4724    *  @param  __middle  Another iterator.
4725    *  @param  __last    Another iterator.
4726    *  @param  __comp    A comparison functor.
4727    *  @return  Nothing.
4728    *
4729    *  Sorts the smallest @p (__middle-__first) elements in the range
4730    *  @p [__first,__last) and moves them to the range @p [__first,__middle). The
4731    *  order of the remaining elements in the range @p [__middle,__last) is
4732    *  undefined.
4733    *  After the sort if @e i and @e j are iterators in the range
4734    *  @p [__first,__middle) such that i precedes j and @e k is an iterator in
4735    *  the range @p [__middle,__last) then @p *__comp(j,*i) and @p __comp(*k,*i)
4736    *  are both false.
4737   */
4738   template<typename _RandomAccessIterator, typename _Compare>
4739     _GLIBCXX20_CONSTEXPR
4740     inline void
4741     partial_sort(_RandomAccessIterator __first,
4742 		 _RandomAccessIterator __middle,
4743 		 _RandomAccessIterator __last,
4744 		 _Compare __comp)
4745     {
4746       // concept requirements
4747       __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
4748 	    _RandomAccessIterator>)
4749       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
4750 	    typename iterator_traits<_RandomAccessIterator>::value_type,
4751 	    typename iterator_traits<_RandomAccessIterator>::value_type>)
4752       __glibcxx_requires_valid_range(__first, __middle);
4753       __glibcxx_requires_valid_range(__middle, __last);
4754       __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
4755 
4756       std::__partial_sort(__first, __middle, __last,
4757 			  __gnu_cxx::__ops::__iter_comp_iter(__comp));
4758     }
4759 
4760   /**
4761    *  @brief Sort a sequence just enough to find a particular position.
4762    *  @ingroup sorting_algorithms
4763    *  @param  __first   An iterator.
4764    *  @param  __nth     Another iterator.
4765    *  @param  __last    Another iterator.
4766    *  @return  Nothing.
4767    *
4768    *  Rearranges the elements in the range @p [__first,__last) so that @p *__nth
4769    *  is the same element that would have been in that position had the
4770    *  whole sequence been sorted. The elements either side of @p *__nth are
4771    *  not completely sorted, but for any iterator @e i in the range
4772    *  @p [__first,__nth) and any iterator @e j in the range @p [__nth,__last) it
4773    *  holds that *j < *i is false.
4774   */
4775   template<typename _RandomAccessIterator>
4776     _GLIBCXX20_CONSTEXPR
4777     inline void
4778     nth_element(_RandomAccessIterator __first, _RandomAccessIterator __nth,
4779 		_RandomAccessIterator __last)
4780     {
4781       // concept requirements
4782       __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
4783 				  _RandomAccessIterator>)
4784       __glibcxx_function_requires(_LessThanComparableConcept<
4785 	    typename iterator_traits<_RandomAccessIterator>::value_type>)
4786       __glibcxx_requires_valid_range(__first, __nth);
4787       __glibcxx_requires_valid_range(__nth, __last);
4788       __glibcxx_requires_irreflexive(__first, __last);
4789 
4790       if (__first == __last || __nth == __last)
4791 	return;
4792 
4793       std::__introselect(__first, __nth, __last,
4794 			 std::__lg(__last - __first) * 2,
4795 			 __gnu_cxx::__ops::__iter_less_iter());
4796     }
4797 
4798   /**
4799    *  @brief Sort a sequence just enough to find a particular position
4800    *         using a predicate for comparison.
4801    *  @ingroup sorting_algorithms
4802    *  @param  __first   An iterator.
4803    *  @param  __nth     Another iterator.
4804    *  @param  __last    Another iterator.
4805    *  @param  __comp    A comparison functor.
4806    *  @return  Nothing.
4807    *
4808    *  Rearranges the elements in the range @p [__first,__last) so that @p *__nth
4809    *  is the same element that would have been in that position had the
4810    *  whole sequence been sorted. The elements either side of @p *__nth are
4811    *  not completely sorted, but for any iterator @e i in the range
4812    *  @p [__first,__nth) and any iterator @e j in the range @p [__nth,__last) it
4813    *  holds that @p __comp(*j,*i) is false.
4814   */
4815   template<typename _RandomAccessIterator, typename _Compare>
4816     _GLIBCXX20_CONSTEXPR
4817     inline void
4818     nth_element(_RandomAccessIterator __first, _RandomAccessIterator __nth,
4819 		_RandomAccessIterator __last, _Compare __comp)
4820     {
4821       // concept requirements
4822       __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
4823 				  _RandomAccessIterator>)
4824       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
4825 	    typename iterator_traits<_RandomAccessIterator>::value_type,
4826 	    typename iterator_traits<_RandomAccessIterator>::value_type>)
4827       __glibcxx_requires_valid_range(__first, __nth);
4828       __glibcxx_requires_valid_range(__nth, __last);
4829       __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
4830 
4831       if (__first == __last || __nth == __last)
4832 	return;
4833 
4834       std::__introselect(__first, __nth, __last,
4835 			 std::__lg(__last - __first) * 2,
4836 			 __gnu_cxx::__ops::__iter_comp_iter(__comp));
4837     }
4838 
4839   /**
4840    *  @brief Sort the elements of a sequence.
4841    *  @ingroup sorting_algorithms
4842    *  @param  __first   An iterator.
4843    *  @param  __last    Another iterator.
4844    *  @return  Nothing.
4845    *
4846    *  Sorts the elements in the range @p [__first,__last) in ascending order,
4847    *  such that for each iterator @e i in the range @p [__first,__last-1),
4848    *  *(i+1)<*i is false.
4849    *
4850    *  The relative ordering of equivalent elements is not preserved, use
4851    *  @p stable_sort() if this is needed.
4852   */
4853   template<typename _RandomAccessIterator>
4854     _GLIBCXX20_CONSTEXPR
4855     inline void
4856     sort(_RandomAccessIterator __first, _RandomAccessIterator __last)
4857     {
4858       // concept requirements
4859       __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
4860 	    _RandomAccessIterator>)
4861       __glibcxx_function_requires(_LessThanComparableConcept<
4862 	    typename iterator_traits<_RandomAccessIterator>::value_type>)
4863       __glibcxx_requires_valid_range(__first, __last);
4864       __glibcxx_requires_irreflexive(__first, __last);
4865 
4866       std::__sort(__first, __last, __gnu_cxx::__ops::__iter_less_iter());
4867     }
4868 
4869   /**
4870    *  @brief Sort the elements of a sequence using a predicate for comparison.
4871    *  @ingroup sorting_algorithms
4872    *  @param  __first   An iterator.
4873    *  @param  __last    Another iterator.
4874    *  @param  __comp    A comparison functor.
4875    *  @return  Nothing.
4876    *
4877    *  Sorts the elements in the range @p [__first,__last) in ascending order,
4878    *  such that @p __comp(*(i+1),*i) is false for every iterator @e i in the
4879    *  range @p [__first,__last-1).
4880    *
4881    *  The relative ordering of equivalent elements is not preserved, use
4882    *  @p stable_sort() if this is needed.
4883   */
4884   template<typename _RandomAccessIterator, typename _Compare>
4885     _GLIBCXX20_CONSTEXPR
4886     inline void
4887     sort(_RandomAccessIterator __first, _RandomAccessIterator __last,
4888 	 _Compare __comp)
4889     {
4890       // concept requirements
4891       __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
4892 	    _RandomAccessIterator>)
4893       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
4894 	    typename iterator_traits<_RandomAccessIterator>::value_type,
4895 	    typename iterator_traits<_RandomAccessIterator>::value_type>)
4896       __glibcxx_requires_valid_range(__first, __last);
4897       __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
4898 
4899       std::__sort(__first, __last, __gnu_cxx::__ops::__iter_comp_iter(__comp));
4900     }
4901 
4902   template<typename _InputIterator1, typename _InputIterator2,
4903 	   typename _OutputIterator, typename _Compare>
4904     _GLIBCXX20_CONSTEXPR
4905     _OutputIterator
4906     __merge(_InputIterator1 __first1, _InputIterator1 __last1,
4907 	    _InputIterator2 __first2, _InputIterator2 __last2,
4908 	    _OutputIterator __result, _Compare __comp)
4909     {
4910       while (__first1 != __last1 && __first2 != __last2)
4911 	{
4912 	  if (__comp(__first2, __first1))
4913 	    {
4914 	      *__result = *__first2;
4915 	      ++__first2;
4916 	    }
4917 	  else
4918 	    {
4919 	      *__result = *__first1;
4920 	      ++__first1;
4921 	    }
4922 	  ++__result;
4923 	}
4924       return std::copy(__first2, __last2,
4925 		       std::copy(__first1, __last1, __result));
4926     }
4927 
4928   /**
4929    *  @brief Merges two sorted ranges.
4930    *  @ingroup sorting_algorithms
4931    *  @param  __first1  An iterator.
4932    *  @param  __first2  Another iterator.
4933    *  @param  __last1   Another iterator.
4934    *  @param  __last2   Another iterator.
4935    *  @param  __result  An iterator pointing to the end of the merged range.
4936    *  @return   An output iterator equal to @p __result + (__last1 - __first1)
4937    *            + (__last2 - __first2).
4938    *
4939    *  Merges the ranges @p [__first1,__last1) and @p [__first2,__last2) into
4940    *  the sorted range @p [__result, __result + (__last1-__first1) +
4941    *  (__last2-__first2)).  Both input ranges must be sorted, and the
4942    *  output range must not overlap with either of the input ranges.
4943    *  The sort is @e stable, that is, for equivalent elements in the
4944    *  two ranges, elements from the first range will always come
4945    *  before elements from the second.
4946   */
4947   template<typename _InputIterator1, typename _InputIterator2,
4948 	   typename _OutputIterator>
4949     _GLIBCXX20_CONSTEXPR
4950     inline _OutputIterator
4951     merge(_InputIterator1 __first1, _InputIterator1 __last1,
4952 	  _InputIterator2 __first2, _InputIterator2 __last2,
4953 	  _OutputIterator __result)
4954     {
4955       // concept requirements
4956       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
4957       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
4958       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
4959 	    typename iterator_traits<_InputIterator1>::value_type>)
4960       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
4961 	    typename iterator_traits<_InputIterator2>::value_type>)
4962       __glibcxx_function_requires(_LessThanOpConcept<
4963 	    typename iterator_traits<_InputIterator2>::value_type,
4964 	    typename iterator_traits<_InputIterator1>::value_type>)
4965       __glibcxx_requires_sorted_set(__first1, __last1, __first2);
4966       __glibcxx_requires_sorted_set(__first2, __last2, __first1);
4967       __glibcxx_requires_irreflexive2(__first1, __last1);
4968       __glibcxx_requires_irreflexive2(__first2, __last2);
4969 
4970       return _GLIBCXX_STD_A::__merge(__first1, __last1,
4971 				     __first2, __last2, __result,
4972 				     __gnu_cxx::__ops::__iter_less_iter());
4973     }
4974 
4975   /**
4976    *  @brief Merges two sorted ranges.
4977    *  @ingroup sorting_algorithms
4978    *  @param  __first1  An iterator.
4979    *  @param  __first2  Another iterator.
4980    *  @param  __last1   Another iterator.
4981    *  @param  __last2   Another iterator.
4982    *  @param  __result  An iterator pointing to the end of the merged range.
4983    *  @param  __comp    A functor to use for comparisons.
4984    *  @return   An output iterator equal to @p __result + (__last1 - __first1)
4985    *            + (__last2 - __first2).
4986    *
4987    *  Merges the ranges @p [__first1,__last1) and @p [__first2,__last2) into
4988    *  the sorted range @p [__result, __result + (__last1-__first1) +
4989    *  (__last2-__first2)).  Both input ranges must be sorted, and the
4990    *  output range must not overlap with either of the input ranges.
4991    *  The sort is @e stable, that is, for equivalent elements in the
4992    *  two ranges, elements from the first range will always come
4993    *  before elements from the second.
4994    *
4995    *  The comparison function should have the same effects on ordering as
4996    *  the function used for the initial sort.
4997   */
4998   template<typename _InputIterator1, typename _InputIterator2,
4999 	   typename _OutputIterator, typename _Compare>
5000     _GLIBCXX20_CONSTEXPR
5001     inline _OutputIterator
5002     merge(_InputIterator1 __first1, _InputIterator1 __last1,
5003 	  _InputIterator2 __first2, _InputIterator2 __last2,
5004 	  _OutputIterator __result, _Compare __comp)
5005     {
5006       // concept requirements
5007       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
5008       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
5009       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5010 	    typename iterator_traits<_InputIterator1>::value_type>)
5011       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5012 	    typename iterator_traits<_InputIterator2>::value_type>)
5013       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5014 	    typename iterator_traits<_InputIterator2>::value_type,
5015 	    typename iterator_traits<_InputIterator1>::value_type>)
5016       __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp);
5017       __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp);
5018       __glibcxx_requires_irreflexive_pred2(__first1, __last1, __comp);
5019       __glibcxx_requires_irreflexive_pred2(__first2, __last2, __comp);
5020 
5021       return _GLIBCXX_STD_A::__merge(__first1, __last1,
5022 				__first2, __last2, __result,
5023 				__gnu_cxx::__ops::__iter_comp_iter(__comp));
5024     }
5025 
5026   template<typename _RandomAccessIterator, typename _Compare>
5027     inline void
5028     __stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last,
5029 		  _Compare __comp)
5030     {
5031       typedef typename iterator_traits<_RandomAccessIterator>::value_type
5032 	_ValueType;
5033       typedef typename iterator_traits<_RandomAccessIterator>::difference_type
5034 	_DistanceType;
5035 
5036       typedef _Temporary_buffer<_RandomAccessIterator, _ValueType> _TmpBuf;
5037       _TmpBuf __buf(__first, std::distance(__first, __last));
5038 
5039       if (__buf.begin() == 0)
5040 	std::__inplace_stable_sort(__first, __last, __comp);
5041       else
5042 	std::__stable_sort_adaptive(__first, __last, __buf.begin(),
5043 				    _DistanceType(__buf.size()), __comp);
5044     }
5045 
5046   /**
5047    *  @brief Sort the elements of a sequence, preserving the relative order
5048    *         of equivalent elements.
5049    *  @ingroup sorting_algorithms
5050    *  @param  __first   An iterator.
5051    *  @param  __last    Another iterator.
5052    *  @return  Nothing.
5053    *
5054    *  Sorts the elements in the range @p [__first,__last) in ascending order,
5055    *  such that for each iterator @p i in the range @p [__first,__last-1),
5056    *  @p *(i+1)<*i is false.
5057    *
5058    *  The relative ordering of equivalent elements is preserved, so any two
5059    *  elements @p x and @p y in the range @p [__first,__last) such that
5060    *  @p x<y is false and @p y<x is false will have the same relative
5061    *  ordering after calling @p stable_sort().
5062   */
5063   template<typename _RandomAccessIterator>
5064     inline void
5065     stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last)
5066     {
5067       // concept requirements
5068       __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
5069 	    _RandomAccessIterator>)
5070       __glibcxx_function_requires(_LessThanComparableConcept<
5071 	    typename iterator_traits<_RandomAccessIterator>::value_type>)
5072       __glibcxx_requires_valid_range(__first, __last);
5073       __glibcxx_requires_irreflexive(__first, __last);
5074 
5075       _GLIBCXX_STD_A::__stable_sort(__first, __last,
5076 				    __gnu_cxx::__ops::__iter_less_iter());
5077     }
5078 
5079   /**
5080    *  @brief Sort the elements of a sequence using a predicate for comparison,
5081    *         preserving the relative order of equivalent elements.
5082    *  @ingroup sorting_algorithms
5083    *  @param  __first   An iterator.
5084    *  @param  __last    Another iterator.
5085    *  @param  __comp    A comparison functor.
5086    *  @return  Nothing.
5087    *
5088    *  Sorts the elements in the range @p [__first,__last) in ascending order,
5089    *  such that for each iterator @p i in the range @p [__first,__last-1),
5090    *  @p __comp(*(i+1),*i) is false.
5091    *
5092    *  The relative ordering of equivalent elements is preserved, so any two
5093    *  elements @p x and @p y in the range @p [__first,__last) such that
5094    *  @p __comp(x,y) is false and @p __comp(y,x) is false will have the same
5095    *  relative ordering after calling @p stable_sort().
5096   */
5097   template<typename _RandomAccessIterator, typename _Compare>
5098     inline void
5099     stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last,
5100 		_Compare __comp)
5101     {
5102       // concept requirements
5103       __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
5104 	    _RandomAccessIterator>)
5105       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5106 	    typename iterator_traits<_RandomAccessIterator>::value_type,
5107 	    typename iterator_traits<_RandomAccessIterator>::value_type>)
5108       __glibcxx_requires_valid_range(__first, __last);
5109       __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
5110 
5111       _GLIBCXX_STD_A::__stable_sort(__first, __last,
5112 				    __gnu_cxx::__ops::__iter_comp_iter(__comp));
5113     }
5114 
5115   template<typename _InputIterator1, typename _InputIterator2,
5116 	   typename _OutputIterator,
5117 	   typename _Compare>
5118     _GLIBCXX20_CONSTEXPR
5119     _OutputIterator
5120     __set_union(_InputIterator1 __first1, _InputIterator1 __last1,
5121 		_InputIterator2 __first2, _InputIterator2 __last2,
5122 		_OutputIterator __result, _Compare __comp)
5123     {
5124       while (__first1 != __last1 && __first2 != __last2)
5125 	{
5126 	  if (__comp(__first1, __first2))
5127 	    {
5128 	      *__result = *__first1;
5129 	      ++__first1;
5130 	    }
5131 	  else if (__comp(__first2, __first1))
5132 	    {
5133 	      *__result = *__first2;
5134 	      ++__first2;
5135 	    }
5136 	  else
5137 	    {
5138 	      *__result = *__first1;
5139 	      ++__first1;
5140 	      ++__first2;
5141 	    }
5142 	  ++__result;
5143 	}
5144       return std::copy(__first2, __last2,
5145 		       std::copy(__first1, __last1, __result));
5146     }
5147 
5148   /**
5149    *  @brief Return the union of two sorted ranges.
5150    *  @ingroup set_algorithms
5151    *  @param  __first1  Start of first range.
5152    *  @param  __last1   End of first range.
5153    *  @param  __first2  Start of second range.
5154    *  @param  __last2   End of second range.
5155    *  @param  __result  Start of output range.
5156    *  @return  End of the output range.
5157    *  @ingroup set_algorithms
5158    *
5159    *  This operation iterates over both ranges, copying elements present in
5160    *  each range in order to the output range.  Iterators increment for each
5161    *  range.  When the current element of one range is less than the other,
5162    *  that element is copied and the iterator advanced.  If an element is
5163    *  contained in both ranges, the element from the first range is copied and
5164    *  both ranges advance.  The output range may not overlap either input
5165    *  range.
5166   */
5167   template<typename _InputIterator1, typename _InputIterator2,
5168 	   typename _OutputIterator>
5169     _GLIBCXX20_CONSTEXPR
5170     inline _OutputIterator
5171     set_union(_InputIterator1 __first1, _InputIterator1 __last1,
5172 	      _InputIterator2 __first2, _InputIterator2 __last2,
5173 	      _OutputIterator __result)
5174     {
5175       // concept requirements
5176       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
5177       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
5178       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5179 	    typename iterator_traits<_InputIterator1>::value_type>)
5180       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5181 	    typename iterator_traits<_InputIterator2>::value_type>)
5182       __glibcxx_function_requires(_LessThanOpConcept<
5183 	    typename iterator_traits<_InputIterator1>::value_type,
5184 	    typename iterator_traits<_InputIterator2>::value_type>)
5185       __glibcxx_function_requires(_LessThanOpConcept<
5186 	    typename iterator_traits<_InputIterator2>::value_type,
5187 	    typename iterator_traits<_InputIterator1>::value_type>)
5188       __glibcxx_requires_sorted_set(__first1, __last1, __first2);
5189       __glibcxx_requires_sorted_set(__first2, __last2, __first1);
5190       __glibcxx_requires_irreflexive2(__first1, __last1);
5191       __glibcxx_requires_irreflexive2(__first2, __last2);
5192 
5193       return _GLIBCXX_STD_A::__set_union(__first1, __last1,
5194 				__first2, __last2, __result,
5195 				__gnu_cxx::__ops::__iter_less_iter());
5196     }
5197 
5198   /**
5199    *  @brief Return the union of two sorted ranges using a comparison functor.
5200    *  @ingroup set_algorithms
5201    *  @param  __first1  Start of first range.
5202    *  @param  __last1   End of first range.
5203    *  @param  __first2  Start of second range.
5204    *  @param  __last2   End of second range.
5205    *  @param  __result  Start of output range.
5206    *  @param  __comp    The comparison functor.
5207    *  @return  End of the output range.
5208    *  @ingroup set_algorithms
5209    *
5210    *  This operation iterates over both ranges, copying elements present in
5211    *  each range in order to the output range.  Iterators increment for each
5212    *  range.  When the current element of one range is less than the other
5213    *  according to @p __comp, that element is copied and the iterator advanced.
5214    *  If an equivalent element according to @p __comp is contained in both
5215    *  ranges, the element from the first range is copied and both ranges
5216    *  advance.  The output range may not overlap either input range.
5217   */
5218   template<typename _InputIterator1, typename _InputIterator2,
5219 	   typename _OutputIterator, typename _Compare>
5220     _GLIBCXX20_CONSTEXPR
5221     inline _OutputIterator
5222     set_union(_InputIterator1 __first1, _InputIterator1 __last1,
5223 	      _InputIterator2 __first2, _InputIterator2 __last2,
5224 	      _OutputIterator __result, _Compare __comp)
5225     {
5226       // concept requirements
5227       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
5228       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
5229       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5230 	    typename iterator_traits<_InputIterator1>::value_type>)
5231       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5232 	    typename iterator_traits<_InputIterator2>::value_type>)
5233       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5234 	    typename iterator_traits<_InputIterator1>::value_type,
5235 	    typename iterator_traits<_InputIterator2>::value_type>)
5236       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5237 	    typename iterator_traits<_InputIterator2>::value_type,
5238 	    typename iterator_traits<_InputIterator1>::value_type>)
5239       __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp);
5240       __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp);
5241       __glibcxx_requires_irreflexive_pred2(__first1, __last1, __comp);
5242       __glibcxx_requires_irreflexive_pred2(__first2, __last2, __comp);
5243 
5244       return _GLIBCXX_STD_A::__set_union(__first1, __last1,
5245 				__first2, __last2, __result,
5246 				__gnu_cxx::__ops::__iter_comp_iter(__comp));
5247     }
5248 
5249   template<typename _InputIterator1, typename _InputIterator2,
5250 	   typename _OutputIterator,
5251 	   typename _Compare>
5252     _GLIBCXX20_CONSTEXPR
5253     _OutputIterator
5254     __set_intersection(_InputIterator1 __first1, _InputIterator1 __last1,
5255 		       _InputIterator2 __first2, _InputIterator2 __last2,
5256 		       _OutputIterator __result, _Compare __comp)
5257     {
5258       while (__first1 != __last1 && __first2 != __last2)
5259 	if (__comp(__first1, __first2))
5260 	  ++__first1;
5261 	else if (__comp(__first2, __first1))
5262 	  ++__first2;
5263 	else
5264 	  {
5265 	    *__result = *__first1;
5266 	    ++__first1;
5267 	    ++__first2;
5268 	    ++__result;
5269 	  }
5270       return __result;
5271     }
5272 
5273   /**
5274    *  @brief Return the intersection of two sorted ranges.
5275    *  @ingroup set_algorithms
5276    *  @param  __first1  Start of first range.
5277    *  @param  __last1   End of first range.
5278    *  @param  __first2  Start of second range.
5279    *  @param  __last2   End of second range.
5280    *  @param  __result  Start of output range.
5281    *  @return  End of the output range.
5282    *  @ingroup set_algorithms
5283    *
5284    *  This operation iterates over both ranges, copying elements present in
5285    *  both ranges in order to the output range.  Iterators increment for each
5286    *  range.  When the current element of one range is less than the other,
5287    *  that iterator advances.  If an element is contained in both ranges, the
5288    *  element from the first range is copied and both ranges advance.  The
5289    *  output range may not overlap either input range.
5290   */
5291   template<typename _InputIterator1, typename _InputIterator2,
5292 	   typename _OutputIterator>
5293     _GLIBCXX20_CONSTEXPR
5294     inline _OutputIterator
5295     set_intersection(_InputIterator1 __first1, _InputIterator1 __last1,
5296 		     _InputIterator2 __first2, _InputIterator2 __last2,
5297 		     _OutputIterator __result)
5298     {
5299       // concept requirements
5300       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
5301       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
5302       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5303 	    typename iterator_traits<_InputIterator1>::value_type>)
5304       __glibcxx_function_requires(_LessThanOpConcept<
5305 	    typename iterator_traits<_InputIterator1>::value_type,
5306 	    typename iterator_traits<_InputIterator2>::value_type>)
5307       __glibcxx_function_requires(_LessThanOpConcept<
5308 	    typename iterator_traits<_InputIterator2>::value_type,
5309 	    typename iterator_traits<_InputIterator1>::value_type>)
5310       __glibcxx_requires_sorted_set(__first1, __last1, __first2);
5311       __glibcxx_requires_sorted_set(__first2, __last2, __first1);
5312       __glibcxx_requires_irreflexive2(__first1, __last1);
5313       __glibcxx_requires_irreflexive2(__first2, __last2);
5314 
5315       return _GLIBCXX_STD_A::__set_intersection(__first1, __last1,
5316 				     __first2, __last2, __result,
5317 				     __gnu_cxx::__ops::__iter_less_iter());
5318     }
5319 
5320   /**
5321    *  @brief Return the intersection of two sorted ranges using comparison
5322    *  functor.
5323    *  @ingroup set_algorithms
5324    *  @param  __first1  Start of first range.
5325    *  @param  __last1   End of first range.
5326    *  @param  __first2  Start of second range.
5327    *  @param  __last2   End of second range.
5328    *  @param  __result  Start of output range.
5329    *  @param  __comp    The comparison functor.
5330    *  @return  End of the output range.
5331    *  @ingroup set_algorithms
5332    *
5333    *  This operation iterates over both ranges, copying elements present in
5334    *  both ranges in order to the output range.  Iterators increment for each
5335    *  range.  When the current element of one range is less than the other
5336    *  according to @p __comp, that iterator advances.  If an element is
5337    *  contained in both ranges according to @p __comp, the element from the
5338    *  first range is copied and both ranges advance.  The output range may not
5339    *  overlap either input range.
5340   */
5341   template<typename _InputIterator1, typename _InputIterator2,
5342 	   typename _OutputIterator, typename _Compare>
5343     _GLIBCXX20_CONSTEXPR
5344     inline _OutputIterator
5345     set_intersection(_InputIterator1 __first1, _InputIterator1 __last1,
5346 		     _InputIterator2 __first2, _InputIterator2 __last2,
5347 		     _OutputIterator __result, _Compare __comp)
5348     {
5349       // concept requirements
5350       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
5351       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
5352       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5353 	    typename iterator_traits<_InputIterator1>::value_type>)
5354       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5355 	    typename iterator_traits<_InputIterator1>::value_type,
5356 	    typename iterator_traits<_InputIterator2>::value_type>)
5357       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5358 	    typename iterator_traits<_InputIterator2>::value_type,
5359 	    typename iterator_traits<_InputIterator1>::value_type>)
5360       __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp);
5361       __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp);
5362       __glibcxx_requires_irreflexive_pred2(__first1, __last1, __comp);
5363       __glibcxx_requires_irreflexive_pred2(__first2, __last2, __comp);
5364 
5365       return _GLIBCXX_STD_A::__set_intersection(__first1, __last1,
5366 				__first2, __last2, __result,
5367 				__gnu_cxx::__ops::__iter_comp_iter(__comp));
5368     }
5369 
5370   template<typename _InputIterator1, typename _InputIterator2,
5371 	   typename _OutputIterator,
5372 	   typename _Compare>
5373     _GLIBCXX20_CONSTEXPR
5374     _OutputIterator
5375     __set_difference(_InputIterator1 __first1, _InputIterator1 __last1,
5376 		     _InputIterator2 __first2, _InputIterator2 __last2,
5377 		     _OutputIterator __result, _Compare __comp)
5378     {
5379       while (__first1 != __last1 && __first2 != __last2)
5380 	if (__comp(__first1, __first2))
5381 	  {
5382 	    *__result = *__first1;
5383 	    ++__first1;
5384 	    ++__result;
5385 	  }
5386 	else if (__comp(__first2, __first1))
5387 	  ++__first2;
5388 	else
5389 	  {
5390 	    ++__first1;
5391 	    ++__first2;
5392 	  }
5393       return std::copy(__first1, __last1, __result);
5394     }
5395 
5396   /**
5397    *  @brief Return the difference of two sorted ranges.
5398    *  @ingroup set_algorithms
5399    *  @param  __first1  Start of first range.
5400    *  @param  __last1   End of first range.
5401    *  @param  __first2  Start of second range.
5402    *  @param  __last2   End of second range.
5403    *  @param  __result  Start of output range.
5404    *  @return  End of the output range.
5405    *  @ingroup set_algorithms
5406    *
5407    *  This operation iterates over both ranges, copying elements present in
5408    *  the first range but not the second in order to the output range.
5409    *  Iterators increment for each range.  When the current element of the
5410    *  first range is less than the second, that element is copied and the
5411    *  iterator advances.  If the current element of the second range is less,
5412    *  the iterator advances, but no element is copied.  If an element is
5413    *  contained in both ranges, no elements are copied and both ranges
5414    *  advance.  The output range may not overlap either input range.
5415   */
5416   template<typename _InputIterator1, typename _InputIterator2,
5417 	   typename _OutputIterator>
5418     _GLIBCXX20_CONSTEXPR
5419     inline _OutputIterator
5420     set_difference(_InputIterator1 __first1, _InputIterator1 __last1,
5421 		   _InputIterator2 __first2, _InputIterator2 __last2,
5422 		   _OutputIterator __result)
5423     {
5424       // concept requirements
5425       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
5426       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
5427       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5428 	    typename iterator_traits<_InputIterator1>::value_type>)
5429       __glibcxx_function_requires(_LessThanOpConcept<
5430 	    typename iterator_traits<_InputIterator1>::value_type,
5431 	    typename iterator_traits<_InputIterator2>::value_type>)
5432       __glibcxx_function_requires(_LessThanOpConcept<
5433 	    typename iterator_traits<_InputIterator2>::value_type,
5434 	    typename iterator_traits<_InputIterator1>::value_type>)
5435       __glibcxx_requires_sorted_set(__first1, __last1, __first2);
5436       __glibcxx_requires_sorted_set(__first2, __last2, __first1);
5437       __glibcxx_requires_irreflexive2(__first1, __last1);
5438       __glibcxx_requires_irreflexive2(__first2, __last2);
5439 
5440       return _GLIBCXX_STD_A::__set_difference(__first1, __last1,
5441 				   __first2, __last2, __result,
5442 				   __gnu_cxx::__ops::__iter_less_iter());
5443     }
5444 
5445   /**
5446    *  @brief  Return the difference of two sorted ranges using comparison
5447    *  functor.
5448    *  @ingroup set_algorithms
5449    *  @param  __first1  Start of first range.
5450    *  @param  __last1   End of first range.
5451    *  @param  __first2  Start of second range.
5452    *  @param  __last2   End of second range.
5453    *  @param  __result  Start of output range.
5454    *  @param  __comp    The comparison functor.
5455    *  @return  End of the output range.
5456    *  @ingroup set_algorithms
5457    *
5458    *  This operation iterates over both ranges, copying elements present in
5459    *  the first range but not the second in order to the output range.
5460    *  Iterators increment for each range.  When the current element of the
5461    *  first range is less than the second according to @p __comp, that element
5462    *  is copied and the iterator advances.  If the current element of the
5463    *  second range is less, no element is copied and the iterator advances.
5464    *  If an element is contained in both ranges according to @p __comp, no
5465    *  elements are copied and both ranges advance.  The output range may not
5466    *  overlap either input range.
5467   */
5468   template<typename _InputIterator1, typename _InputIterator2,
5469 	   typename _OutputIterator, typename _Compare>
5470     _GLIBCXX20_CONSTEXPR
5471     inline _OutputIterator
5472     set_difference(_InputIterator1 __first1, _InputIterator1 __last1,
5473 		   _InputIterator2 __first2, _InputIterator2 __last2,
5474 		   _OutputIterator __result, _Compare __comp)
5475     {
5476       // concept requirements
5477       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
5478       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
5479       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5480 	    typename iterator_traits<_InputIterator1>::value_type>)
5481       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5482 	    typename iterator_traits<_InputIterator1>::value_type,
5483 	    typename iterator_traits<_InputIterator2>::value_type>)
5484       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5485 	    typename iterator_traits<_InputIterator2>::value_type,
5486 	    typename iterator_traits<_InputIterator1>::value_type>)
5487       __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp);
5488       __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp);
5489       __glibcxx_requires_irreflexive_pred2(__first1, __last1, __comp);
5490       __glibcxx_requires_irreflexive_pred2(__first2, __last2, __comp);
5491 
5492       return _GLIBCXX_STD_A::__set_difference(__first1, __last1,
5493 				   __first2, __last2, __result,
5494 				   __gnu_cxx::__ops::__iter_comp_iter(__comp));
5495     }
5496 
5497   template<typename _InputIterator1, typename _InputIterator2,
5498 	   typename _OutputIterator,
5499 	   typename _Compare>
5500     _GLIBCXX20_CONSTEXPR
5501     _OutputIterator
5502     __set_symmetric_difference(_InputIterator1 __first1,
5503 			       _InputIterator1 __last1,
5504 			       _InputIterator2 __first2,
5505 			       _InputIterator2 __last2,
5506 			       _OutputIterator __result,
5507 			       _Compare __comp)
5508     {
5509       while (__first1 != __last1 && __first2 != __last2)
5510 	if (__comp(__first1, __first2))
5511 	  {
5512 	    *__result = *__first1;
5513 	    ++__first1;
5514 	    ++__result;
5515 	  }
5516 	else if (__comp(__first2, __first1))
5517 	  {
5518 	    *__result = *__first2;
5519 	    ++__first2;
5520 	    ++__result;
5521 	  }
5522 	else
5523 	  {
5524 	    ++__first1;
5525 	    ++__first2;
5526 	  }
5527       return std::copy(__first2, __last2,
5528 		       std::copy(__first1, __last1, __result));
5529     }
5530 
5531   /**
5532    *  @brief  Return the symmetric difference of two sorted ranges.
5533    *  @ingroup set_algorithms
5534    *  @param  __first1  Start of first range.
5535    *  @param  __last1   End of first range.
5536    *  @param  __first2  Start of second range.
5537    *  @param  __last2   End of second range.
5538    *  @param  __result  Start of output range.
5539    *  @return  End of the output range.
5540    *  @ingroup set_algorithms
5541    *
5542    *  This operation iterates over both ranges, copying elements present in
5543    *  one range but not the other in order to the output range.  Iterators
5544    *  increment for each range.  When the current element of one range is less
5545    *  than the other, that element is copied and the iterator advances.  If an
5546    *  element is contained in both ranges, no elements are copied and both
5547    *  ranges advance.  The output range may not overlap either input range.
5548   */
5549   template<typename _InputIterator1, typename _InputIterator2,
5550 	   typename _OutputIterator>
5551     _GLIBCXX20_CONSTEXPR
5552     inline _OutputIterator
5553     set_symmetric_difference(_InputIterator1 __first1, _InputIterator1 __last1,
5554 			     _InputIterator2 __first2, _InputIterator2 __last2,
5555 			     _OutputIterator __result)
5556     {
5557       // concept requirements
5558       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
5559       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
5560       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5561 	    typename iterator_traits<_InputIterator1>::value_type>)
5562       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5563 	    typename iterator_traits<_InputIterator2>::value_type>)
5564       __glibcxx_function_requires(_LessThanOpConcept<
5565 	    typename iterator_traits<_InputIterator1>::value_type,
5566 	    typename iterator_traits<_InputIterator2>::value_type>)
5567       __glibcxx_function_requires(_LessThanOpConcept<
5568 	    typename iterator_traits<_InputIterator2>::value_type,
5569 	    typename iterator_traits<_InputIterator1>::value_type>)
5570       __glibcxx_requires_sorted_set(__first1, __last1, __first2);
5571       __glibcxx_requires_sorted_set(__first2, __last2, __first1);
5572       __glibcxx_requires_irreflexive2(__first1, __last1);
5573       __glibcxx_requires_irreflexive2(__first2, __last2);
5574 
5575       return _GLIBCXX_STD_A::__set_symmetric_difference(__first1, __last1,
5576 					__first2, __last2, __result,
5577 					__gnu_cxx::__ops::__iter_less_iter());
5578     }
5579 
5580   /**
5581    *  @brief  Return the symmetric difference of two sorted ranges using
5582    *  comparison functor.
5583    *  @ingroup set_algorithms
5584    *  @param  __first1  Start of first range.
5585    *  @param  __last1   End of first range.
5586    *  @param  __first2  Start of second range.
5587    *  @param  __last2   End of second range.
5588    *  @param  __result  Start of output range.
5589    *  @param  __comp    The comparison functor.
5590    *  @return  End of the output range.
5591    *  @ingroup set_algorithms
5592    *
5593    *  This operation iterates over both ranges, copying elements present in
5594    *  one range but not the other in order to the output range.  Iterators
5595    *  increment for each range.  When the current element of one range is less
5596    *  than the other according to @p comp, that element is copied and the
5597    *  iterator advances.  If an element is contained in both ranges according
5598    *  to @p __comp, no elements are copied and both ranges advance.  The output
5599    *  range may not overlap either input range.
5600   */
5601   template<typename _InputIterator1, typename _InputIterator2,
5602 	   typename _OutputIterator, typename _Compare>
5603     _GLIBCXX20_CONSTEXPR
5604     inline _OutputIterator
5605     set_symmetric_difference(_InputIterator1 __first1, _InputIterator1 __last1,
5606 			     _InputIterator2 __first2, _InputIterator2 __last2,
5607 			     _OutputIterator __result,
5608 			     _Compare __comp)
5609     {
5610       // concept requirements
5611       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
5612       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
5613       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5614 	    typename iterator_traits<_InputIterator1>::value_type>)
5615       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5616 	    typename iterator_traits<_InputIterator2>::value_type>)
5617       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5618 	    typename iterator_traits<_InputIterator1>::value_type,
5619 	    typename iterator_traits<_InputIterator2>::value_type>)
5620       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5621 	    typename iterator_traits<_InputIterator2>::value_type,
5622 	    typename iterator_traits<_InputIterator1>::value_type>)
5623       __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp);
5624       __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp);
5625       __glibcxx_requires_irreflexive_pred2(__first1, __last1, __comp);
5626       __glibcxx_requires_irreflexive_pred2(__first2, __last2, __comp);
5627 
5628       return _GLIBCXX_STD_A::__set_symmetric_difference(__first1, __last1,
5629 				__first2, __last2, __result,
5630 				__gnu_cxx::__ops::__iter_comp_iter(__comp));
5631     }
5632 
5633   template<typename _ForwardIterator, typename _Compare>
5634     _GLIBCXX14_CONSTEXPR
5635     _ForwardIterator
5636     __min_element(_ForwardIterator __first, _ForwardIterator __last,
5637 		  _Compare __comp)
5638     {
5639       if (__first == __last)
5640 	return __first;
5641       _ForwardIterator __result = __first;
5642       while (++__first != __last)
5643 	if (__comp(__first, __result))
5644 	  __result = __first;
5645       return __result;
5646     }
5647 
5648   /**
5649    *  @brief  Return the minimum element in a range.
5650    *  @ingroup sorting_algorithms
5651    *  @param  __first  Start of range.
5652    *  @param  __last   End of range.
5653    *  @return  Iterator referencing the first instance of the smallest value.
5654   */
5655   template<typename _ForwardIterator>
5656     _GLIBCXX14_CONSTEXPR
5657     _ForwardIterator
5658     inline min_element(_ForwardIterator __first, _ForwardIterator __last)
5659     {
5660       // concept requirements
5661       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
5662       __glibcxx_function_requires(_LessThanComparableConcept<
5663 	    typename iterator_traits<_ForwardIterator>::value_type>)
5664       __glibcxx_requires_valid_range(__first, __last);
5665       __glibcxx_requires_irreflexive(__first, __last);
5666 
5667       return _GLIBCXX_STD_A::__min_element(__first, __last,
5668 				__gnu_cxx::__ops::__iter_less_iter());
5669     }
5670 
5671   /**
5672    *  @brief  Return the minimum element in a range using comparison functor.
5673    *  @ingroup sorting_algorithms
5674    *  @param  __first  Start of range.
5675    *  @param  __last   End of range.
5676    *  @param  __comp   Comparison functor.
5677    *  @return  Iterator referencing the first instance of the smallest value
5678    *  according to __comp.
5679   */
5680   template<typename _ForwardIterator, typename _Compare>
5681     _GLIBCXX14_CONSTEXPR
5682     inline _ForwardIterator
5683     min_element(_ForwardIterator __first, _ForwardIterator __last,
5684 		_Compare __comp)
5685     {
5686       // concept requirements
5687       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
5688       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5689 	    typename iterator_traits<_ForwardIterator>::value_type,
5690 	    typename iterator_traits<_ForwardIterator>::value_type>)
5691       __glibcxx_requires_valid_range(__first, __last);
5692       __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
5693 
5694       return _GLIBCXX_STD_A::__min_element(__first, __last,
5695 				__gnu_cxx::__ops::__iter_comp_iter(__comp));
5696     }
5697 
5698   template<typename _ForwardIterator, typename _Compare>
5699     _GLIBCXX14_CONSTEXPR
5700     _ForwardIterator
5701     __max_element(_ForwardIterator __first, _ForwardIterator __last,
5702 		  _Compare __comp)
5703     {
5704       if (__first == __last) return __first;
5705       _ForwardIterator __result = __first;
5706       while (++__first != __last)
5707 	if (__comp(__result, __first))
5708 	  __result = __first;
5709       return __result;
5710     }
5711 
5712   /**
5713    *  @brief  Return the maximum element in a range.
5714    *  @ingroup sorting_algorithms
5715    *  @param  __first  Start of range.
5716    *  @param  __last   End of range.
5717    *  @return  Iterator referencing the first instance of the largest value.
5718   */
5719   template<typename _ForwardIterator>
5720     _GLIBCXX14_CONSTEXPR
5721     inline _ForwardIterator
5722     max_element(_ForwardIterator __first, _ForwardIterator __last)
5723     {
5724       // concept requirements
5725       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
5726       __glibcxx_function_requires(_LessThanComparableConcept<
5727 	    typename iterator_traits<_ForwardIterator>::value_type>)
5728       __glibcxx_requires_valid_range(__first, __last);
5729       __glibcxx_requires_irreflexive(__first, __last);
5730 
5731       return _GLIBCXX_STD_A::__max_element(__first, __last,
5732 				__gnu_cxx::__ops::__iter_less_iter());
5733     }
5734 
5735   /**
5736    *  @brief  Return the maximum element in a range using comparison functor.
5737    *  @ingroup sorting_algorithms
5738    *  @param  __first  Start of range.
5739    *  @param  __last   End of range.
5740    *  @param  __comp   Comparison functor.
5741    *  @return  Iterator referencing the first instance of the largest value
5742    *  according to __comp.
5743   */
5744   template<typename _ForwardIterator, typename _Compare>
5745     _GLIBCXX14_CONSTEXPR
5746     inline _ForwardIterator
5747     max_element(_ForwardIterator __first, _ForwardIterator __last,
5748 		_Compare __comp)
5749     {
5750       // concept requirements
5751       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
5752       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5753 	    typename iterator_traits<_ForwardIterator>::value_type,
5754 	    typename iterator_traits<_ForwardIterator>::value_type>)
5755       __glibcxx_requires_valid_range(__first, __last);
5756       __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
5757 
5758       return _GLIBCXX_STD_A::__max_element(__first, __last,
5759 				__gnu_cxx::__ops::__iter_comp_iter(__comp));
5760     }
5761 
5762 #if __cplusplus >= 201402L
5763   /// Reservoir sampling algorithm.
5764   template<typename _InputIterator, typename _RandomAccessIterator,
5765            typename _Size, typename _UniformRandomBitGenerator>
5766     _RandomAccessIterator
5767     __sample(_InputIterator __first, _InputIterator __last, input_iterator_tag,
5768 	     _RandomAccessIterator __out, random_access_iterator_tag,
5769 	     _Size __n, _UniformRandomBitGenerator&& __g)
5770     {
5771       using __distrib_type = uniform_int_distribution<_Size>;
5772       using __param_type = typename __distrib_type::param_type;
5773       __distrib_type __d{};
5774       _Size __sample_sz = 0;
5775       while (__first != __last && __sample_sz != __n)
5776 	{
5777 	  __out[__sample_sz++] = *__first;
5778 	  ++__first;
5779 	}
5780       for (auto __pop_sz = __sample_sz; __first != __last;
5781 	  ++__first, (void) ++__pop_sz)
5782 	{
5783 	  const auto __k = __d(__g, __param_type{0, __pop_sz});
5784 	  if (__k < __n)
5785 	    __out[__k] = *__first;
5786 	}
5787       return __out + __sample_sz;
5788     }
5789 
5790   /// Selection sampling algorithm.
5791   template<typename _ForwardIterator, typename _OutputIterator, typename _Cat,
5792            typename _Size, typename _UniformRandomBitGenerator>
5793     _OutputIterator
5794     __sample(_ForwardIterator __first, _ForwardIterator __last,
5795 	     forward_iterator_tag,
5796 	     _OutputIterator __out, _Cat,
5797 	     _Size __n, _UniformRandomBitGenerator&& __g)
5798     {
5799       using __distrib_type = uniform_int_distribution<_Size>;
5800       using __param_type = typename __distrib_type::param_type;
5801       using _USize = make_unsigned_t<_Size>;
5802       using _Gen = remove_reference_t<_UniformRandomBitGenerator>;
5803       using __uc_type = common_type_t<typename _Gen::result_type, _USize>;
5804 
5805       if (__first == __last)
5806 	return __out;
5807 
5808       __distrib_type __d{};
5809       _Size __unsampled_sz = std::distance(__first, __last);
5810       __n = std::min(__n, __unsampled_sz);
5811 
5812       // If possible, we use __gen_two_uniform_ints to efficiently produce
5813       // two random numbers using a single distribution invocation:
5814 
5815       const __uc_type __urngrange = __g.max() - __g.min();
5816       if (__urngrange / __uc_type(__unsampled_sz) >= __uc_type(__unsampled_sz))
5817         // I.e. (__urngrange >= __unsampled_sz * __unsampled_sz) but without
5818 	// wrapping issues.
5819         {
5820 	  while (__n != 0 && __unsampled_sz >= 2)
5821 	    {
5822 	      const pair<_Size, _Size> __p =
5823 		__gen_two_uniform_ints(__unsampled_sz, __unsampled_sz - 1, __g);
5824 
5825 	      --__unsampled_sz;
5826 	      if (__p.first < __n)
5827 		{
5828 		  *__out++ = *__first;
5829 		  --__n;
5830 		}
5831 
5832 	      ++__first;
5833 
5834 	      if (__n == 0) break;
5835 
5836 	      --__unsampled_sz;
5837 	      if (__p.second < __n)
5838 		{
5839 		  *__out++ = *__first;
5840 		  --__n;
5841 		}
5842 
5843 	      ++__first;
5844 	    }
5845         }
5846 
5847       // The loop above is otherwise equivalent to this one-at-a-time version:
5848 
5849       for (; __n != 0; ++__first)
5850 	if (__d(__g, __param_type{0, --__unsampled_sz}) < __n)
5851 	  {
5852 	    *__out++ = *__first;
5853 	    --__n;
5854 	  }
5855       return __out;
5856     }
5857 
5858 #if __cplusplus > 201402L
5859 #define __cpp_lib_sample 201603
5860   /// Take a random sample from a population.
5861   template<typename _PopulationIterator, typename _SampleIterator,
5862            typename _Distance, typename _UniformRandomBitGenerator>
5863     _SampleIterator
5864     sample(_PopulationIterator __first, _PopulationIterator __last,
5865 	   _SampleIterator __out, _Distance __n,
5866 	   _UniformRandomBitGenerator&& __g)
5867     {
5868       using __pop_cat = typename
5869 	std::iterator_traits<_PopulationIterator>::iterator_category;
5870       using __samp_cat = typename
5871 	std::iterator_traits<_SampleIterator>::iterator_category;
5872 
5873       static_assert(
5874 	  __or_<is_convertible<__pop_cat, forward_iterator_tag>,
5875 		is_convertible<__samp_cat, random_access_iterator_tag>>::value,
5876 	  "output range must use a RandomAccessIterator when input range"
5877 	  " does not meet the ForwardIterator requirements");
5878 
5879       static_assert(is_integral<_Distance>::value,
5880 		    "sample size must be an integer type");
5881 
5882       typename iterator_traits<_PopulationIterator>::difference_type __d = __n;
5883       return _GLIBCXX_STD_A::
5884 	__sample(__first, __last, __pop_cat{}, __out, __samp_cat{}, __d,
5885 		 std::forward<_UniformRandomBitGenerator>(__g));
5886     }
5887 #endif // C++17
5888 #endif // C++14
5889 
5890 _GLIBCXX_END_NAMESPACE_ALGO
5891 _GLIBCXX_END_NAMESPACE_VERSION
5892 } // namespace std
5893 
5894 #endif /* _STL_ALGO_H */
5895