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