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