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