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