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