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