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 true for at least one element
475  * of a sequence.
476  * @ingroup non_mutating_algorithms
477  * @param __first An input iterator.
478  * @param __last An input iterator.
479  * @param __pred A predicate.
480  * @return True if the check is true, false otherwise.
481  *
482  * Returns true if an element exists in the range @p
483  * [__first,__last) such that @p __pred is true, and false
484  * otherwise.
485  */
486  template<typename _InputIterator, typename _Predicate>
487  _GLIBCXX20_CONSTEXPR
488  inline bool
489  any_of(_InputIterator __first, _InputIterator __last, _Predicate __pred)
490  { return !std::none_of(__first, __last, __pred); }
491 
492  /**
493  * @brief Find the first element in a sequence for which a
494  * predicate is false.
495  * @ingroup non_mutating_algorithms
496  * @param __first An input iterator.
497  * @param __last An input iterator.
498  * @param __pred A predicate.
499  * @return The first iterator @c i in the range @p [__first,__last)
500  * such that @p __pred(*i) is false, or @p __last if no such iterator exists.
501  */
502  template<typename _InputIterator, typename _Predicate>
503  _GLIBCXX20_CONSTEXPR
504  inline _InputIterator
505  find_if_not(_InputIterator __first, _InputIterator __last,
506  _Predicate __pred)
507  {
508  // concept requirements
509  __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
510  __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
512  __glibcxx_requires_valid_range(__first, __last);
513  return std::__find_if_not(__first, __last,
514  __gnu_cxx::__ops::__pred_iter(__pred));
515  }
516 
517  /**
518  * @brief Checks whether the sequence is partitioned.
519  * @ingroup mutating_algorithms
520  * @param __first An input iterator.
521  * @param __last An input iterator.
522  * @param __pred A predicate.
523  * @return True if the range @p [__first,__last) is partioned by @p __pred,
524  * i.e. if all elements that satisfy @p __pred appear before those that
525  * do not.
526  */
527  template<typename _InputIterator, typename _Predicate>
528  _GLIBCXX20_CONSTEXPR
529  inline bool
530  is_partitioned(_InputIterator __first, _InputIterator __last,
531  _Predicate __pred)
532  {
533  __first = std::find_if_not(__first, __last, __pred);
534  if (__first == __last)
535  return true;
536  ++__first;
537  return std::none_of(__first, __last, __pred);
538  }
539 
540  /**
541  * @brief Find the partition point of a partitioned range.
542  * @ingroup mutating_algorithms
543  * @param __first An iterator.
544  * @param __last Another iterator.
545  * @param __pred A predicate.
546  * @return An iterator @p mid such that @p all_of(__first, mid, __pred)
547  * and @p none_of(mid, __last, __pred) are both true.
548  */
549  template<typename _ForwardIterator, typename _Predicate>
550  _GLIBCXX20_CONSTEXPR
551  _ForwardIterator
552  partition_point(_ForwardIterator __first, _ForwardIterator __last,
553  _Predicate __pred)
554  {
555  // concept requirements
556  __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
557  __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
559 
560  // A specific debug-mode test will be necessary...
561  __glibcxx_requires_valid_range(__first, __last);
562 
564  _DistanceType;
565 
566  _DistanceType __len = std::distance(__first, __last);
567 
568  while (__len > 0)
569  {
570  _DistanceType __half = __len >> 1;
571  _ForwardIterator __middle = __first;
572  std::advance(__middle, __half);
573  if (__pred(*__middle))
574  {
575  __first = __middle;
576  ++__first;
577  __len = __len - __half - 1;
578  }
579  else
580  __len = __half;
581  }
582  return __first;
583  }
584 #endif
585 
586  template<typename _InputIterator, typename _OutputIterator,
587  typename _Predicate>
588  _GLIBCXX20_CONSTEXPR
589  _OutputIterator
590  __remove_copy_if(_InputIterator __first, _InputIterator __last,
591  _OutputIterator __result, _Predicate __pred)
592  {
593  for (; __first != __last; ++__first)
594  if (!__pred(__first))
595  {
596  *__result = *__first;
597  ++__result;
598  }
599  return __result;
600  }
601 
602  /**
603  * @brief Copy a sequence, removing elements of a given value.
604  * @ingroup mutating_algorithms
605  * @param __first An input iterator.
606  * @param __last An input iterator.
607  * @param __result An output iterator.
608  * @param __value The value to be removed.
609  * @return An iterator designating the end of the resulting sequence.
610  *
611  * Copies each element in the range @p [__first,__last) not equal
612  * to @p __value to the range beginning at @p __result.
613  * remove_copy() is stable, so the relative order of elements that
614  * are copied is unchanged.
615  */
616  template<typename _InputIterator, typename _OutputIterator, typename _Tp>
617  _GLIBCXX20_CONSTEXPR
618  inline _OutputIterator
619  remove_copy(_InputIterator __first, _InputIterator __last,
620  _OutputIterator __result, const _Tp& __value)
621  {
622  // concept requirements
623  __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
624  __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
626  __glibcxx_function_requires(_EqualOpConcept<
628  __glibcxx_requires_valid_range(__first, __last);
629 
630  return std::__remove_copy_if(__first, __last, __result,
631  __gnu_cxx::__ops::__iter_equals_val(__value));
632  }
633 
634  /**
635  * @brief Copy a sequence, removing elements for which a predicate is true.
636  * @ingroup mutating_algorithms
637  * @param __first An input iterator.
638  * @param __last An input iterator.
639  * @param __result An output iterator.
640  * @param __pred A predicate.
641  * @return An iterator designating the end of the resulting sequence.
642  *
643  * Copies each element in the range @p [__first,__last) for which
644  * @p __pred returns false to the range beginning at @p __result.
645  *
646  * remove_copy_if() is stable, so the relative order of elements that are
647  * copied is unchanged.
648  */
649  template<typename _InputIterator, typename _OutputIterator,
650  typename _Predicate>
651  _GLIBCXX20_CONSTEXPR
652  inline _OutputIterator
653  remove_copy_if(_InputIterator __first, _InputIterator __last,
654  _OutputIterator __result, _Predicate __pred)
655  {
656  // concept requirements
657  __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
658  __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
660  __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
662  __glibcxx_requires_valid_range(__first, __last);
663 
664  return std::__remove_copy_if(__first, __last, __result,
665  __gnu_cxx::__ops::__pred_iter(__pred));
666  }
667 
668 #if __cplusplus >= 201103L
669  /**
670  * @brief Copy the elements of a sequence for which a predicate is true.
671  * @ingroup mutating_algorithms
672  * @param __first An input iterator.
673  * @param __last An input iterator.
674  * @param __result An output iterator.
675  * @param __pred A predicate.
676  * @return An iterator designating the end of the resulting sequence.
677  *
678  * Copies each element in the range @p [__first,__last) for which
679  * @p __pred returns true to the range beginning at @p __result.
680  *
681  * copy_if() is stable, so the relative order of elements that are
682  * copied is unchanged.
683  */
684  template<typename _InputIterator, typename _OutputIterator,
685  typename _Predicate>
686  _GLIBCXX20_CONSTEXPR
687  _OutputIterator
688  copy_if(_InputIterator __first, _InputIterator __last,
689  _OutputIterator __result, _Predicate __pred)
690  {
691  // concept requirements
692  __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
693  __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
695  __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
697  __glibcxx_requires_valid_range(__first, __last);
698 
699  for (; __first != __last; ++__first)
700  if (__pred(*__first))
701  {
702  *__result = *__first;
703  ++__result;
704  }
705  return __result;
706  }
707 
708  template<typename _InputIterator, typename _Size, typename _OutputIterator>
709  _GLIBCXX20_CONSTEXPR
710  _OutputIterator
711  __copy_n_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,
1240  forward_iterator_tag)
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,
1282  bidirectional_iterator_tag)
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,
1321  random_access_iterator_tag)
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 
1332  typedef typename iterator_traits<_RandomAccessIterator>::difference_type
1333  _Distance;
1334  typedef typename iterator_traits<_RandomAccessIterator>::value_type
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  _GLIBCXX20_CONSTEXPR
3858  _InputIterator
3859  for_each_n(_InputIterator __first, _Size __n, _Function __f)
3860  {
3861  auto __n2 = std::__size_to_integer(__n);
3862  using _Cat = typename iterator_traits<_InputIterator>::iterator_category;
3863  if constexpr (is_base_of_v<random_access_iterator_tag, _Cat>)
3864  {
3865  if (__n2 <= 0)
3866  return __first;
3867  auto __last = __first + __n2;
3868  std::for_each(__first, __last, std::move(__f));
3869  return __last;
3870  }
3871  else
3872  {
3873  while (__n2-->0)
3874  {
3875  __f(*__first);
3876  ++__first;
3877  }
3878  return __first;
3879  }
3880  }
3881 #endif // C++17
3882 
3883  /**
3884  * @brief Find the first occurrence of a value in a sequence.
3885  * @ingroup non_mutating_algorithms
3886  * @param __first An input iterator.
3887  * @param __last An input iterator.
3888  * @param __val The value to find.
3889  * @return The first iterator @c i in the range @p [__first,__last)
3890  * such that @c *i == @p __val, or @p __last if no such iterator exists.
3891  */
3892  template<typename _InputIterator, typename _Tp>
3893  _GLIBCXX20_CONSTEXPR
3894  inline _InputIterator
3895  find(_InputIterator __first, _InputIterator __last,
3896  const _Tp& __val)
3897  {
3898  // concept requirements
3899  __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
3900  __glibcxx_function_requires(_EqualOpConcept<
3902  __glibcxx_requires_valid_range(__first, __last);
3903  return std::__find_if(__first, __last,
3904  __gnu_cxx::__ops::__iter_equals_val(__val));
3905  }
3906 
3907  /**
3908  * @brief Find the first element in a sequence for which a
3909  * predicate is true.
3910  * @ingroup non_mutating_algorithms
3911  * @param __first An input iterator.
3912  * @param __last An input iterator.
3913  * @param __pred A predicate.
3914  * @return The first iterator @c i in the range @p [__first,__last)
3915  * such that @p __pred(*i) is true, or @p __last if no such iterator exists.
3916  */
3917  template<typename _InputIterator, typename _Predicate>
3918  _GLIBCXX20_CONSTEXPR
3919  inline _InputIterator
3920  find_if(_InputIterator __first, _InputIterator __last,
3921  _Predicate __pred)
3922  {
3923  // concept requirements
3924  __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
3925  __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
3927  __glibcxx_requires_valid_range(__first, __last);
3928 
3929  return std::__find_if(__first, __last,
3930  __gnu_cxx::__ops::__pred_iter(__pred));
3931  }
3932 
3933  /**
3934  * @brief Find element from a set in a sequence.
3935  * @ingroup non_mutating_algorithms
3936  * @param __first1 Start of range to search.
3937  * @param __last1 End of range to search.
3938  * @param __first2 Start of match candidates.
3939  * @param __last2 End of match candidates.
3940  * @return The first iterator @c i in the range
3941  * @p [__first1,__last1) such that @c *i == @p *(i2) such that i2 is an
3942  * iterator in [__first2,__last2), or @p __last1 if no such iterator exists.
3943  *
3944  * Searches the range @p [__first1,__last1) for an element that is
3945  * equal to some element in the range [__first2,__last2). If
3946  * found, returns an iterator in the range [__first1,__last1),
3947  * otherwise returns @p __last1.
3948  */
3949  template<typename _InputIterator, typename _ForwardIterator>
3950  _GLIBCXX20_CONSTEXPR
3951  _InputIterator
3952  find_first_of(_InputIterator __first1, _InputIterator __last1,
3953  _ForwardIterator __first2, _ForwardIterator __last2)
3954  {
3955  // concept requirements
3956  __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
3957  __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
3958  __glibcxx_function_requires(_EqualOpConcept<
3961  __glibcxx_requires_valid_range(__first1, __last1);
3962  __glibcxx_requires_valid_range(__first2, __last2);
3963 
3964  for (; __first1 != __last1; ++__first1)
3965  for (_ForwardIterator __iter = __first2; __iter != __last2; ++__iter)
3966  if (*__first1 == *__iter)
3967  return __first1;
3968  return __last1;
3969  }
3970 
3971  /**
3972  * @brief Find element from a set in a sequence using a predicate.
3973  * @ingroup non_mutating_algorithms
3974  * @param __first1 Start of range to search.
3975  * @param __last1 End of range to search.
3976  * @param __first2 Start of match candidates.
3977  * @param __last2 End of match candidates.
3978  * @param __comp Predicate to use.
3979  * @return The first iterator @c i in the range
3980  * @p [__first1,__last1) such that @c comp(*i, @p *(i2)) is true
3981  * and i2 is an iterator in [__first2,__last2), or @p __last1 if no
3982  * such iterator exists.
3983  *
3984 
3985  * Searches the range @p [__first1,__last1) for an element that is
3986  * equal to some element in the range [__first2,__last2). If
3987  * found, returns an iterator in the range [__first1,__last1),
3988  * otherwise returns @p __last1.
3989  */
3990  template<typename _InputIterator, typename _ForwardIterator,
3991  typename _BinaryPredicate>
3992  _GLIBCXX20_CONSTEXPR
3993  _InputIterator
3994  find_first_of(_InputIterator __first1, _InputIterator __last1,
3995  _ForwardIterator __first2, _ForwardIterator __last2,
3996  _BinaryPredicate __comp)
3997  {
3998  // concept requirements
3999  __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
4000  __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
4001  __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
4004  __glibcxx_requires_valid_range(__first1, __last1);
4005  __glibcxx_requires_valid_range(__first2, __last2);
4006 
4007  for (; __first1 != __last1; ++__first1)
4008  for (_ForwardIterator __iter = __first2; __iter != __last2; ++__iter)
4009  if (__comp(*__first1, *__iter))
4010  return __first1;
4011  return __last1;
4012  }
4013 
4014  /**
4015  * @brief Find two adjacent values in a sequence that are equal.
4016  * @ingroup non_mutating_algorithms
4017  * @param __first A forward iterator.
4018  * @param __last A forward iterator.
4019  * @return The first iterator @c i such that @c i and @c i+1 are both
4020  * valid iterators in @p [__first,__last) and such that @c *i == @c *(i+1),
4021  * or @p __last if no such iterator exists.
4022  */
4023  template<typename _ForwardIterator>
4024  _GLIBCXX20_CONSTEXPR
4025  inline _ForwardIterator
4026  adjacent_find(_ForwardIterator __first, _ForwardIterator __last)
4027  {
4028  // concept requirements
4029  __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
4030  __glibcxx_function_requires(_EqualityComparableConcept<
4032  __glibcxx_requires_valid_range(__first, __last);
4033 
4034  return std::__adjacent_find(__first, __last,
4035  __gnu_cxx::__ops::__iter_equal_to_iter());
4036  }
4037 
4038  /**
4039  * @brief Find two adjacent values in a sequence using a predicate.
4040  * @ingroup non_mutating_algorithms
4041  * @param __first A forward iterator.
4042  * @param __last A forward iterator.
4043  * @param __binary_pred A binary predicate.
4044  * @return The first iterator @c i such that @c i and @c i+1 are both
4045  * valid iterators in @p [__first,__last) and such that
4046  * @p __binary_pred(*i,*(i+1)) is true, or @p __last if no such iterator
4047  * exists.
4048  */
4049  template<typename _ForwardIterator, typename _BinaryPredicate>
4050  _GLIBCXX20_CONSTEXPR
4051  inline _ForwardIterator
4052  adjacent_find(_ForwardIterator __first, _ForwardIterator __last,
4053  _BinaryPredicate __binary_pred)
4054  {
4055  // concept requirements
4056  __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
4057  __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
4060  __glibcxx_requires_valid_range(__first, __last);
4061 
4062  return std::__adjacent_find(__first, __last,
4063  __gnu_cxx::__ops::__iter_comp_iter(__binary_pred));
4064  }
4065 
4066  /**
4067  * @brief Count the number of copies of a value in a sequence.
4068  * @ingroup non_mutating_algorithms
4069  * @param __first An input iterator.
4070  * @param __last An input iterator.
4071  * @param __value The value to be counted.
4072  * @return The number of iterators @c i in the range @p [__first,__last)
4073  * for which @c *i == @p __value
4074  */
4075  template<typename _InputIterator, typename _Tp>
4076  _GLIBCXX20_CONSTEXPR
4077  inline typename iterator_traits<_InputIterator>::difference_type
4078  count(_InputIterator __first, _InputIterator __last, const _Tp& __value)
4079  {
4080  // concept requirements
4081  __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
4082  __glibcxx_function_requires(_EqualOpConcept<
4084  __glibcxx_requires_valid_range(__first, __last);
4085 
4086  return std::__count_if(__first, __last,
4087  __gnu_cxx::__ops::__iter_equals_val(__value));
4088  }
4089 
4090  /**
4091  * @brief Count the elements of a sequence for which a predicate is true.
4092  * @ingroup non_mutating_algorithms
4093  * @param __first An input iterator.
4094  * @param __last An input iterator.
4095  * @param __pred A predicate.
4096  * @return The number of iterators @c i in the range @p [__first,__last)
4097  * for which @p __pred(*i) is true.
4098  */
4099  template<typename _InputIterator, typename _Predicate>
4100  _GLIBCXX20_CONSTEXPR
4101  inline typename iterator_traits<_InputIterator>::difference_type
4102  count_if(_InputIterator __first, _InputIterator __last, _Predicate __pred)
4103  {
4104  // concept requirements
4105  __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
4106  __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
4108  __glibcxx_requires_valid_range(__first, __last);
4109 
4110  return std::__count_if(__first, __last,
4111  __gnu_cxx::__ops::__pred_iter(__pred));
4112  }
4113 
4114  /**
4115  * @brief Search a sequence for a matching sub-sequence.
4116  * @ingroup non_mutating_algorithms
4117  * @param __first1 A forward iterator.
4118  * @param __last1 A forward iterator.
4119  * @param __first2 A forward iterator.
4120  * @param __last2 A forward iterator.
4121  * @return The first iterator @c i in the range @p
4122  * [__first1,__last1-(__last2-__first2)) such that @c *(i+N) == @p
4123  * *(__first2+N) for each @c N in the range @p
4124  * [0,__last2-__first2), or @p __last1 if no such iterator exists.
4125  *
4126  * Searches the range @p [__first1,__last1) for a sub-sequence that
4127  * compares equal value-by-value with the sequence given by @p
4128  * [__first2,__last2) and returns an iterator to the first element
4129  * of the sub-sequence, or @p __last1 if the sub-sequence is not
4130  * found.
4131  *
4132  * Because the sub-sequence must lie completely within the range @p
4133  * [__first1,__last1) it must start at a position less than @p
4134  * __last1-(__last2-__first2) where @p __last2-__first2 is the
4135  * length of the sub-sequence.
4136  *
4137  * This means that the returned iterator @c i will be in the range
4138  * @p [__first1,__last1-(__last2-__first2))
4139  */
4140  template<typename _ForwardIterator1, typename _ForwardIterator2>
4141  _GLIBCXX20_CONSTEXPR
4142  inline _ForwardIterator1
4143  search(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
4144  _ForwardIterator2 __first2, _ForwardIterator2 __last2)
4145  {
4146  // concept requirements
4147  __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator1>)
4148  __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator2>)
4149  __glibcxx_function_requires(_EqualOpConcept<
4152  __glibcxx_requires_valid_range(__first1, __last1);
4153  __glibcxx_requires_valid_range(__first2, __last2);
4154 
4155  return std::__search(__first1, __last1, __first2, __last2,
4156  __gnu_cxx::__ops::__iter_equal_to_iter());
4157  }
4158 
4159  /**
4160  * @brief Search a sequence for a matching sub-sequence using a predicate.
4161  * @ingroup non_mutating_algorithms
4162  * @param __first1 A forward iterator.
4163  * @param __last1 A forward iterator.
4164  * @param __first2 A forward iterator.
4165  * @param __last2 A forward iterator.
4166  * @param __predicate A binary predicate.
4167  * @return The first iterator @c i in the range
4168  * @p [__first1,__last1-(__last2-__first2)) such that
4169  * @p __predicate(*(i+N),*(__first2+N)) is true for each @c N in the range
4170  * @p [0,__last2-__first2), or @p __last1 if no such iterator exists.
4171  *
4172  * Searches the range @p [__first1,__last1) for a sub-sequence that
4173  * compares equal value-by-value with the sequence given by @p
4174  * [__first2,__last2), using @p __predicate to determine equality,
4175  * and returns an iterator to the first element of the
4176  * sub-sequence, or @p __last1 if no such iterator exists.
4177  *
4178  * @see search(_ForwardIter1, _ForwardIter1, _ForwardIter2, _ForwardIter2)
4179  */
4180  template<typename _ForwardIterator1, typename _ForwardIterator2,
4181  typename _BinaryPredicate>
4182  _GLIBCXX20_CONSTEXPR
4183  inline _ForwardIterator1
4184  search(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
4185  _ForwardIterator2 __first2, _ForwardIterator2 __last2,
4186  _BinaryPredicate __predicate)
4187  {
4188  // concept requirements
4189  __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator1>)
4190  __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator2>)
4191  __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
4194  __glibcxx_requires_valid_range(__first1, __last1);
4195  __glibcxx_requires_valid_range(__first2, __last2);
4196 
4197  return std::__search(__first1, __last1, __first2, __last2,
4198  __gnu_cxx::__ops::__iter_comp_iter(__predicate));
4199  }
4200 
4201  /**
4202  * @brief Search a sequence for a number of consecutive values.
4203  * @ingroup non_mutating_algorithms
4204  * @param __first A forward iterator.
4205  * @param __last A forward iterator.
4206  * @param __count The number of consecutive values.
4207  * @param __val The value to find.
4208  * @return The first iterator @c i in the range @p
4209  * [__first,__last-__count) such that @c *(i+N) == @p __val for
4210  * each @c N in the range @p [0,__count), or @p __last if no such
4211  * iterator exists.
4212  *
4213  * Searches the range @p [__first,__last) for @p count consecutive elements
4214  * equal to @p __val.
4215  */
4216  template<typename _ForwardIterator, typename _Integer, typename _Tp>
4217  _GLIBCXX20_CONSTEXPR
4218  inline _ForwardIterator
4219  search_n(_ForwardIterator __first, _ForwardIterator __last,
4220  _Integer __count, const _Tp& __val)
4221  {
4222  // concept requirements
4223  __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
4224  __glibcxx_function_requires(_EqualOpConcept<
4226  __glibcxx_requires_valid_range(__first, __last);
4227 
4228  return std::__search_n(__first, __last, __count,
4229  __gnu_cxx::__ops::__iter_equals_val(__val));
4230  }
4231 
4232 
4233  /**
4234  * @brief Search a sequence for a number of consecutive values using a
4235  * predicate.
4236  * @ingroup non_mutating_algorithms
4237  * @param __first A forward iterator.
4238  * @param __last A forward iterator.
4239  * @param __count The number of consecutive values.
4240  * @param __val The value to find.
4241  * @param __binary_pred A binary predicate.
4242  * @return The first iterator @c i in the range @p
4243  * [__first,__last-__count) such that @p
4244  * __binary_pred(*(i+N),__val) is true for each @c N in the range
4245  * @p [0,__count), or @p __last if no such iterator exists.
4246  *
4247  * Searches the range @p [__first,__last) for @p __count
4248  * consecutive elements for which the predicate returns true.
4249  */
4250  template<typename _ForwardIterator, typename _Integer, typename _Tp,
4251  typename _BinaryPredicate>
4252  _GLIBCXX20_CONSTEXPR
4253  inline _ForwardIterator
4254  search_n(_ForwardIterator __first, _ForwardIterator __last,
4255  _Integer __count, const _Tp& __val,
4256  _BinaryPredicate __binary_pred)
4257  {
4258  // concept requirements
4259  __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
4260  __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
4262  __glibcxx_requires_valid_range(__first, __last);
4263 
4264  return std::__search_n(__first, __last, __count,
4265  __gnu_cxx::__ops::__iter_comp_val(__binary_pred, __val));
4266  }
4267 
4268 #if __cplusplus > 201402L
4269  /** @brief Search a sequence using a Searcher object.
4270  *
4271  * @param __first A forward iterator.
4272  * @param __last A forward iterator.
4273  * @param __searcher A callable object.
4274  * @return @p __searcher(__first,__last).first
4275  */
4276  template<typename _ForwardIterator, typename _Searcher>
4277  _GLIBCXX20_CONSTEXPR
4278  inline _ForwardIterator
4279  search(_ForwardIterator __first, _ForwardIterator __last,
4280  const _Searcher& __searcher)
4281  { return __searcher(__first, __last).first; }
4282 #endif
4283 
4284  /**
4285  * @brief Perform an operation on a sequence.
4286  * @ingroup mutating_algorithms
4287  * @param __first An input iterator.
4288  * @param __last An input iterator.
4289  * @param __result An output iterator.
4290  * @param __unary_op A unary operator.
4291  * @return An output iterator equal to @p __result+(__last-__first).
4292  *
4293  * Applies the operator to each element in the input range and assigns
4294  * the results to successive elements of the output sequence.
4295  * Evaluates @p *(__result+N)=unary_op(*(__first+N)) for each @c N in the
4296  * range @p [0,__last-__first).
4297  *
4298  * @p unary_op must not alter its argument.
4299  */
4300  template<typename _InputIterator, typename _OutputIterator,
4301  typename _UnaryOperation>
4302  _GLIBCXX20_CONSTEXPR
4303  _OutputIterator
4304  transform(_InputIterator __first, _InputIterator __last,
4305  _OutputIterator __result, _UnaryOperation __unary_op)
4306  {
4307  // concept requirements
4308  __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
4309  __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
4310  // "the type returned by a _UnaryOperation"
4311  __typeof__(__unary_op(*__first))>)
4312  __glibcxx_requires_valid_range(__first, __last);
4313 
4314  for (; __first != __last; ++__first, (void)++__result)
4315  *__result = __unary_op(*__first);
4316  return __result;
4317  }
4318 
4319  /**
4320  * @brief Perform an operation on corresponding elements of two sequences.
4321  * @ingroup mutating_algorithms
4322  * @param __first1 An input iterator.
4323  * @param __last1 An input iterator.
4324  * @param __first2 An input iterator.
4325  * @param __result An output iterator.
4326  * @param __binary_op A binary operator.
4327  * @return An output iterator equal to @p result+(last-first).
4328  *
4329  * Applies the operator to the corresponding elements in the two
4330  * input ranges and assigns the results to successive elements of the
4331  * output sequence.
4332  * Evaluates @p
4333  * *(__result+N)=__binary_op(*(__first1+N),*(__first2+N)) for each
4334  * @c N in the range @p [0,__last1-__first1).
4335  *
4336  * @p binary_op must not alter either of its arguments.
4337  */
4338  template<typename _InputIterator1, typename _InputIterator2,
4339  typename _OutputIterator, typename _BinaryOperation>
4340  _GLIBCXX20_CONSTEXPR
4341  _OutputIterator
4342  transform(_InputIterator1 __first1, _InputIterator1 __last1,
4343  _InputIterator2 __first2, _OutputIterator __result,
4344  _BinaryOperation __binary_op)
4345  {
4346  // concept requirements
4347  __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
4348  __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
4349  __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
4350  // "the type returned by a _BinaryOperation"
4351  __typeof__(__binary_op(*__first1,*__first2))>)
4352  __glibcxx_requires_valid_range(__first1, __last1);
4353 
4354  for (; __first1 != __last1; ++__first1, (void)++__first2, ++__result)
4355  *__result = __binary_op(*__first1, *__first2);
4356  return __result;
4357  }
4358 
4359  /**
4360  * @brief Replace each occurrence of one value in a sequence with another
4361  * value.
4362  * @ingroup mutating_algorithms
4363  * @param __first A forward iterator.
4364  * @param __last A forward iterator.
4365  * @param __old_value The value to be replaced.
4366  * @param __new_value The replacement value.
4367  * @return replace() returns no value.
4368  *
4369  * For each iterator @c i in the range @p [__first,__last) if @c *i ==
4370  * @p __old_value then the assignment @c *i = @p __new_value is performed.
4371  */
4372  template<typename _ForwardIterator, typename _Tp>
4373  _GLIBCXX20_CONSTEXPR
4374  void
4375  replace(_ForwardIterator __first, _ForwardIterator __last,
4376  const _Tp& __old_value, const _Tp& __new_value)
4377  {
4378  // concept requirements
4379  __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
4380  _ForwardIterator>)
4381  __glibcxx_function_requires(_EqualOpConcept<
4383  __glibcxx_function_requires(_ConvertibleConcept<_Tp,
4385  __glibcxx_requires_valid_range(__first, __last);
4386 
4387  for (; __first != __last; ++__first)
4388  if (*__first == __old_value)
4389  *__first = __new_value;
4390  }
4391 
4392  /**
4393  * @brief Replace each value in a sequence for which a predicate returns
4394  * true with another value.
4395  * @ingroup mutating_algorithms
4396  * @param __first A forward iterator.
4397  * @param __last A forward iterator.
4398  * @param __pred A predicate.
4399  * @param __new_value The replacement value.
4400  * @return replace_if() returns no value.
4401  *
4402  * For each iterator @c i in the range @p [__first,__last) if @p __pred(*i)
4403  * is true then the assignment @c *i = @p __new_value is performed.
4404  */
4405  template<typename _ForwardIterator, typename _Predicate, typename _Tp>
4406  _GLIBCXX20_CONSTEXPR
4407  void
4408  replace_if(_ForwardIterator __first, _ForwardIterator __last,
4409  _Predicate __pred, const _Tp& __new_value)
4410  {
4411  // concept requirements
4412  __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
4413  _ForwardIterator>)
4414  __glibcxx_function_requires(_ConvertibleConcept<_Tp,
4416  __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
4418  __glibcxx_requires_valid_range(__first, __last);
4419 
4420  for (; __first != __last; ++__first)
4421  if (__pred(*__first))
4422  *__first = __new_value;
4423  }
4424 
4425  /**
4426  * @brief Assign the result of a function object to each value in a
4427  * sequence.
4428  * @ingroup mutating_algorithms
4429  * @param __first A forward iterator.
4430  * @param __last A forward iterator.
4431  * @param __gen A function object taking no arguments and returning
4432  * std::iterator_traits<_ForwardIterator>::value_type
4433  * @return generate() returns no value.
4434  *
4435  * Performs the assignment @c *i = @p __gen() for each @c i in the range
4436  * @p [__first,__last).
4437  */
4438  template<typename _ForwardIterator, typename _Generator>
4439  _GLIBCXX20_CONSTEXPR
4440  void
4441  generate(_ForwardIterator __first, _ForwardIterator __last,
4442  _Generator __gen)
4443  {
4444  // concept requirements
4445  __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
4446  __glibcxx_function_requires(_GeneratorConcept<_Generator,
4448  __glibcxx_requires_valid_range(__first, __last);
4449 
4450  for (; __first != __last; ++__first)
4451  *__first = __gen();
4452  }
4453 
4454  /**
4455  * @brief Assign the result of a function object to each value in a
4456  * sequence.
4457  * @ingroup mutating_algorithms
4458  * @param __first A forward iterator.
4459  * @param __n The length of the sequence.
4460  * @param __gen A function object taking no arguments and returning
4461  * std::iterator_traits<_ForwardIterator>::value_type
4462  * @return The end of the sequence, @p __first+__n
4463  *
4464  * Performs the assignment @c *i = @p __gen() for each @c i in the range
4465  * @p [__first,__first+__n).
4466  *
4467  * If @p __n is negative, the function does nothing and returns @p __first.
4468  */
4469  // _GLIBCXX_RESOLVE_LIB_DEFECTS
4470  // DR 865. More algorithms that throw away information
4471  // DR 426. search_n(), fill_n(), and generate_n() with negative n
4472  template<typename _OutputIterator, typename _Size, typename _Generator>
4473  _GLIBCXX20_CONSTEXPR
4474  _OutputIterator
4475  generate_n(_OutputIterator __first, _Size __n, _Generator __gen)
4476  {
4477  // concept requirements
4478  __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
4479  // "the type returned by a _Generator"
4480  __typeof__(__gen())>)
4481 
4482  typedef __decltype(std::__size_to_integer(__n)) _IntSize;
4483  for (_IntSize __niter = std::__size_to_integer(__n);
4484  __niter > 0; --__niter, (void) ++__first)
4485  *__first = __gen();
4486  return __first;
4487  }
4488 
4489  /**
4490  * @brief Copy a sequence, removing consecutive duplicate values.
4491  * @ingroup mutating_algorithms
4492  * @param __first An input iterator.
4493  * @param __last An input iterator.
4494  * @param __result An output iterator.
4495  * @return An iterator designating the end of the resulting sequence.
4496  *
4497  * Copies each element in the range @p [__first,__last) to the range
4498  * beginning at @p __result, except that only the first element is copied
4499  * from groups of consecutive elements that compare equal.
4500  * unique_copy() is stable, so the relative order of elements that are
4501  * copied is unchanged.
4502  *
4503  * _GLIBCXX_RESOLVE_LIB_DEFECTS
4504  * DR 241. Does unique_copy() require CopyConstructible and Assignable?
4505  *
4506  * _GLIBCXX_RESOLVE_LIB_DEFECTS
4507  * DR 538. 241 again: Does unique_copy() require CopyConstructible and
4508  * Assignable?
4509  */
4510  template<typename _InputIterator, typename _OutputIterator>
4511  _GLIBCXX20_CONSTEXPR
4512  inline _OutputIterator
4513  unique_copy(_InputIterator __first, _InputIterator __last,
4514  _OutputIterator __result)
4515  {
4516  // concept requirements
4517  __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
4518  __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
4520  __glibcxx_function_requires(_EqualityComparableConcept<
4522  __glibcxx_requires_valid_range(__first, __last);
4523 
4524  if (__first == __last)
4525  return __result;
4526  return std::__unique_copy(__first, __last, __result,
4527  __gnu_cxx::__ops::__iter_equal_to_iter(),
4528  std::__iterator_category(__first),
4529  std::__iterator_category(__result));
4530  }
4531 
4532  /**
4533  * @brief Copy a sequence, removing consecutive values using a predicate.
4534  * @ingroup mutating_algorithms
4535  * @param __first An input iterator.
4536  * @param __last An input iterator.
4537  * @param __result An output iterator.
4538  * @param __binary_pred A binary predicate.
4539  * @return An iterator designating the end of the resulting sequence.
4540  *
4541  * Copies each element in the range @p [__first,__last) to the range
4542  * beginning at @p __result, except that only the first element is copied
4543  * from groups of consecutive elements for which @p __binary_pred returns
4544  * true.
4545  * unique_copy() is stable, so the relative order of elements that are
4546  * copied is unchanged.
4547  *
4548  * _GLIBCXX_RESOLVE_LIB_DEFECTS
4549  * DR 241. Does unique_copy() require CopyConstructible and Assignable?
4550  */
4551  template<typename _InputIterator, typename _OutputIterator,
4552  typename _BinaryPredicate>
4553  _GLIBCXX20_CONSTEXPR
4554  inline _OutputIterator
4555  unique_copy(_InputIterator __first, _InputIterator __last,
4556  _OutputIterator __result,
4557  _BinaryPredicate __binary_pred)
4558  {
4559  // concept requirements -- predicates checked later
4560  __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
4561  __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
4563  __glibcxx_requires_valid_range(__first, __last);
4564 
4565  if (__first == __last)
4566  return __result;
4567  return std::__unique_copy(__first, __last, __result,
4568  __gnu_cxx::__ops::__iter_comp_iter(__binary_pred),
4569  std::__iterator_category(__first),
4570  std::__iterator_category(__result));
4571  }
4572 
4573 #if _GLIBCXX_HOSTED
4574  /**
4575  * @brief Randomly shuffle the elements of a sequence.
4576  * @ingroup mutating_algorithms
4577  * @param __first A forward iterator.
4578  * @param __last A forward iterator.
4579  * @return Nothing.
4580  *
4581  * Reorder the elements in the range @p [__first,__last) using a random
4582  * distribution, so that every possible ordering of the sequence is
4583  * equally likely.
4584  */
4585  template<typename _RandomAccessIterator>
4586  inline void
4587  random_shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last)
4588  {
4589  // concept requirements
4590  __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
4591  _RandomAccessIterator>)
4592  __glibcxx_requires_valid_range(__first, __last);
4593 
4594  if (__first != __last)
4595  for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i)
4596  {
4597  // XXX rand() % N is not uniformly distributed
4598  _RandomAccessIterator __j = __first
4599  + std::rand() % ((__i - __first) + 1);
4600  if (__i != __j)
4601  std::iter_swap(__i, __j);
4602  }
4603  }
4604 #endif
4605 
4606  /**
4607  * @brief Shuffle the elements of a sequence using a random number
4608  * generator.
4609  * @ingroup mutating_algorithms
4610  * @param __first A forward iterator.
4611  * @param __last A forward iterator.
4612  * @param __rand The RNG functor or function.
4613  * @return Nothing.
4614  *
4615  * Reorders the elements in the range @p [__first,__last) using @p __rand to
4616  * provide a random distribution. Calling @p __rand(N) for a positive
4617  * integer @p N should return a randomly chosen integer from the
4618  * range [0,N).
4619  */
4620  template<typename _RandomAccessIterator, typename _RandomNumberGenerator>
4621  void
4622  random_shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last,
4623 #if __cplusplus >= 201103L
4624  _RandomNumberGenerator&& __rand)
4625 #else
4626  _RandomNumberGenerator& __rand)
4627 #endif
4628  {
4629  // concept requirements
4630  __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
4631  _RandomAccessIterator>)
4632  __glibcxx_requires_valid_range(__first, __last);
4633 
4634  if (__first == __last)
4635  return;
4636  for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i)
4637  {
4638  _RandomAccessIterator __j = __first + __rand((__i - __first) + 1);
4639  if (__i != __j)
4640  std::iter_swap(__i, __j);
4641  }
4642  }
4643 
4644 
4645  /**
4646  * @brief Move elements for which a predicate is true to the beginning
4647  * of a sequence.
4648  * @ingroup mutating_algorithms
4649  * @param __first A forward iterator.
4650  * @param __last A forward iterator.
4651  * @param __pred A predicate functor.
4652  * @return An iterator @p middle such that @p __pred(i) is true for each
4653  * iterator @p i in the range @p [__first,middle) and false for each @p i
4654  * in the range @p [middle,__last).
4655  *
4656  * @p __pred must not modify its operand. @p partition() does not preserve
4657  * the relative ordering of elements in each group, use
4658  * @p stable_partition() if this is needed.
4659  */
4660  template<typename _ForwardIterator, typename _Predicate>
4661  _GLIBCXX20_CONSTEXPR
4662  inline _ForwardIterator
4663  partition(_ForwardIterator __first, _ForwardIterator __last,
4664  _Predicate __pred)
4665  {
4666  // concept requirements
4667  __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
4668  _ForwardIterator>)
4669  __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
4671  __glibcxx_requires_valid_range(__first, __last);
4672 
4673  return std::__partition(__first, __last, __pred,
4674  std::__iterator_category(__first));
4675  }
4676 
4677 
4678  /**
4679  * @brief Sort the smallest elements of a sequence.
4680  * @ingroup sorting_algorithms
4681  * @param __first An iterator.
4682  * @param __middle Another iterator.
4683  * @param __last Another iterator.
4684  * @return Nothing.
4685  *
4686  * Sorts the smallest @p (__middle-__first) elements in the range
4687  * @p [first,last) and moves them to the range @p [__first,__middle). The
4688  * order of the remaining elements in the range @p [__middle,__last) is
4689  * undefined.
4690  * After the sort if @e i and @e j are iterators in the range
4691  * @p [__first,__middle) such that i precedes j and @e k is an iterator in
4692  * the range @p [__middle,__last) then *j<*i and *k<*i are both false.
4693  */
4694  template<typename _RandomAccessIterator>
4695  _GLIBCXX20_CONSTEXPR
4696  inline void
4697  partial_sort(_RandomAccessIterator __first,
4698  _RandomAccessIterator __middle,
4699  _RandomAccessIterator __last)
4700  {
4701  // concept requirements
4702  __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
4703  _RandomAccessIterator>)
4704  __glibcxx_function_requires(_LessThanComparableConcept<
4706  __glibcxx_requires_valid_range(__first, __middle);
4707  __glibcxx_requires_valid_range(__middle, __last);
4708  __glibcxx_requires_irreflexive(__first, __last);
4709 
4710  std::__partial_sort(__first, __middle, __last,
4711  __gnu_cxx::__ops::__iter_less_iter());
4712  }
4713 
4714  /**
4715  * @brief Sort the smallest elements of a sequence using a predicate
4716  * for comparison.
4717  * @ingroup sorting_algorithms
4718  * @param __first An iterator.
4719  * @param __middle Another iterator.
4720  * @param __last Another iterator.
4721  * @param __comp A comparison functor.
4722  * @return Nothing.
4723  *
4724  * Sorts the smallest @p (__middle-__first) elements in the range
4725  * @p [__first,__last) and moves them to the range @p [__first,__middle). The
4726  * order of the remaining elements in the range @p [__middle,__last) is
4727  * undefined.
4728  * After the sort if @e i and @e j are iterators in the range
4729  * @p [__first,__middle) such that i precedes j and @e k is an iterator in
4730  * the range @p [__middle,__last) then @p *__comp(j,*i) and @p __comp(*k,*i)
4731  * are both false.
4732  */
4733  template<typename _RandomAccessIterator, typename _Compare>
4734  _GLIBCXX20_CONSTEXPR
4735  inline void
4736  partial_sort(_RandomAccessIterator __first,
4737  _RandomAccessIterator __middle,
4738  _RandomAccessIterator __last,
4739  _Compare __comp)
4740  {
4741  // concept requirements
4742  __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
4743  _RandomAccessIterator>)
4744  __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
4747  __glibcxx_requires_valid_range(__first, __middle);
4748  __glibcxx_requires_valid_range(__middle, __last);
4749  __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
4750 
4751  std::__partial_sort(__first, __middle, __last,
4752  __gnu_cxx::__ops::__iter_comp_iter(__comp));
4753  }
4754 
4755  /**
4756  * @brief Sort a sequence just enough to find a particular position.
4757  * @ingroup sorting_algorithms
4758  * @param __first An iterator.
4759  * @param __nth Another iterator.
4760  * @param __last Another iterator.
4761  * @return Nothing.
4762  *
4763  * Rearranges the elements in the range @p [__first,__last) so that @p *__nth
4764  * is the same element that would have been in that position had the
4765  * whole sequence been sorted. The elements either side of @p *__nth are
4766  * not completely sorted, but for any iterator @e i in the range
4767  * @p [__first,__nth) and any iterator @e j in the range @p [__nth,__last) it
4768  * holds that *j < *i is false.
4769  */
4770  template<typename _RandomAccessIterator>
4771  _GLIBCXX20_CONSTEXPR
4772  inline void
4773  nth_element(_RandomAccessIterator __first, _RandomAccessIterator __nth,
4774  _RandomAccessIterator __last)
4775  {
4776  // concept requirements
4777  __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
4778  _RandomAccessIterator>)
4779  __glibcxx_function_requires(_LessThanComparableConcept<
4781  __glibcxx_requires_valid_range(__first, __nth);
4782  __glibcxx_requires_valid_range(__nth, __last);
4783  __glibcxx_requires_irreflexive(__first, __last);
4784 
4785  if (__first == __last || __nth == __last)
4786  return;
4787 
4788  std::__introselect(__first, __nth, __last,
4789  std::__lg(__last - __first) * 2,
4790  __gnu_cxx::__ops::__iter_less_iter());
4791  }
4792 
4793  /**
4794  * @brief Sort a sequence just enough to find a particular position
4795  * using a predicate for comparison.
4796  * @ingroup sorting_algorithms
4797  * @param __first An iterator.
4798  * @param __nth Another iterator.
4799  * @param __last Another iterator.
4800  * @param __comp A comparison functor.
4801  * @return Nothing.
4802  *
4803  * Rearranges the elements in the range @p [__first,__last) so that @p *__nth
4804  * is the same element that would have been in that position had the
4805  * whole sequence been sorted. The elements either side of @p *__nth are
4806  * not completely sorted, but for any iterator @e i in the range
4807  * @p [__first,__nth) and any iterator @e j in the range @p [__nth,__last) it
4808  * holds that @p __comp(*j,*i) is false.
4809  */
4810  template<typename _RandomAccessIterator, typename _Compare>
4811  _GLIBCXX20_CONSTEXPR
4812  inline void
4813  nth_element(_RandomAccessIterator __first, _RandomAccessIterator __nth,
4814  _RandomAccessIterator __last, _Compare __comp)
4815  {
4816  // concept requirements
4817  __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
4818  _RandomAccessIterator>)
4819  __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
4822  __glibcxx_requires_valid_range(__first, __nth);
4823  __glibcxx_requires_valid_range(__nth, __last);
4824  __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
4825 
4826  if (__first == __last || __nth == __last)
4827  return;
4828 
4829  std::__introselect(__first, __nth, __last,
4830  std::__lg(__last - __first) * 2,
4831  __gnu_cxx::__ops::__iter_comp_iter(__comp));
4832  }
4833 
4834  /**
4835  * @brief Sort the elements of a sequence.
4836  * @ingroup sorting_algorithms
4837  * @param __first An iterator.
4838  * @param __last Another iterator.
4839  * @return Nothing.
4840  *
4841  * Sorts the elements in the range @p [__first,__last) in ascending order,
4842  * such that for each iterator @e i in the range @p [__first,__last-1),
4843  * *(i+1)<*i is false.
4844  *
4845  * The relative ordering of equivalent elements is not preserved, use
4846  * @p stable_sort() if this is needed.
4847  */
4848  template<typename _RandomAccessIterator>
4849  _GLIBCXX20_CONSTEXPR
4850  inline void
4851  sort(_RandomAccessIterator __first, _RandomAccessIterator __last)
4852  {
4853  // concept requirements
4854  __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
4855  _RandomAccessIterator>)
4856  __glibcxx_function_requires(_LessThanComparableConcept<
4858  __glibcxx_requires_valid_range(__first, __last);
4859  __glibcxx_requires_irreflexive(__first, __last);
4860 
4861  std::__sort(__first, __last, __gnu_cxx::__ops::__iter_less_iter());
4862  }
4863 
4864  /**
4865  * @brief Sort the elements of a sequence using a predicate for comparison.
4866  * @ingroup sorting_algorithms
4867  * @param __first An iterator.
4868  * @param __last Another iterator.
4869  * @param __comp A comparison functor.
4870  * @return Nothing.
4871  *
4872  * Sorts the elements in the range @p [__first,__last) in ascending order,
4873  * such that @p __comp(*(i+1),*i) is false for every iterator @e i in the
4874  * range @p [__first,__last-1).
4875  *
4876  * The relative ordering of equivalent elements is not preserved, use
4877  * @p stable_sort() if this is needed.
4878  */
4879  template<typename _RandomAccessIterator, typename _Compare>
4880  _GLIBCXX20_CONSTEXPR
4881  inline void
4882  sort(_RandomAccessIterator __first, _RandomAccessIterator __last,
4883  _Compare __comp)
4884  {
4885  // concept requirements
4886  __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
4887  _RandomAccessIterator>)
4888  __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
4891  __glibcxx_requires_valid_range(__first, __last);
4892  __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
4893 
4894  std::__sort(__first, __last, __gnu_cxx::__ops::__iter_comp_iter(__comp));
4895  }
4896 
4897  template<typename _InputIterator1, typename _InputIterator2,
4898  typename _OutputIterator, typename _Compare>
4899  _GLIBCXX20_CONSTEXPR
4900  _OutputIterator
4901  __merge(_InputIterator1 __first1, _InputIterator1 __last1,
4902  _InputIterator2 __first2, _InputIterator2 __last2,
4903  _OutputIterator __result, _Compare __comp)
4904  {
4905  while (__first1 != __last1 && __first2 != __last2)
4906  {
4907  if (__comp(__first2, __first1))
4908  {
4909  *__result = *__first2;
4910  ++__first2;
4911  }
4912  else
4913  {
4914  *__result = *__first1;
4915  ++__first1;
4916  }
4917  ++__result;
4918  }
4919  return std::copy(__first2, __last2,
4920  std::copy(__first1, __last1, __result));
4921  }
4922 
4923  /**
4924  * @brief Merges two sorted ranges.
4925  * @ingroup sorting_algorithms
4926  * @param __first1 An iterator.
4927  * @param __first2 Another iterator.
4928  * @param __last1 Another iterator.
4929  * @param __last2 Another iterator.
4930  * @param __result An iterator pointing to the end of the merged range.
4931  * @return An output iterator equal to @p __result + (__last1 - __first1)
4932  * + (__last2 - __first2).
4933  *
4934  * Merges the ranges @p [__first1,__last1) and @p [__first2,__last2) into
4935  * the sorted range @p [__result, __result + (__last1-__first1) +
4936  * (__last2-__first2)). Both input ranges must be sorted, and the
4937  * output range must not overlap with either of the input ranges.
4938  * The sort is @e stable, that is, for equivalent elements in the
4939  * two ranges, elements from the first range will always come
4940  * before elements from the second.
4941  */
4942  template<typename _InputIterator1, typename _InputIterator2,
4943  typename _OutputIterator>
4944  _GLIBCXX20_CONSTEXPR
4945  inline _OutputIterator
4946  merge(_InputIterator1 __first1, _InputIterator1 __last1,
4947  _InputIterator2 __first2, _InputIterator2 __last2,
4948  _OutputIterator __result)
4949  {
4950  // concept requirements
4951  __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
4952  __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
4953  __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
4955  __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
4957  __glibcxx_function_requires(_LessThanOpConcept<
4960  __glibcxx_requires_sorted_set(__first1, __last1, __first2);
4961  __glibcxx_requires_sorted_set(__first2, __last2, __first1);
4962  __glibcxx_requires_irreflexive2(__first1, __last1);
4963  __glibcxx_requires_irreflexive2(__first2, __last2);
4964 
4965  return _GLIBCXX_STD_A::__merge(__first1, __last1,
4966  __first2, __last2, __result,
4967  __gnu_cxx::__ops::__iter_less_iter());
4968  }
4969 
4970  /**
4971  * @brief Merges two sorted ranges.
4972  * @ingroup sorting_algorithms
4973  * @param __first1 An iterator.
4974  * @param __first2 Another iterator.
4975  * @param __last1 Another iterator.
4976  * @param __last2 Another iterator.
4977  * @param __result An iterator pointing to the end of the merged range.
4978  * @param __comp A functor to use for comparisons.
4979  * @return An output iterator equal to @p __result + (__last1 - __first1)
4980  * + (__last2 - __first2).
4981  *
4982  * Merges the ranges @p [__first1,__last1) and @p [__first2,__last2) into
4983  * the sorted range @p [__result, __result + (__last1-__first1) +
4984  * (__last2-__first2)). Both input ranges must be sorted, and the
4985  * output range must not overlap with either of the input ranges.
4986  * The sort is @e stable, that is, for equivalent elements in the
4987  * two ranges, elements from the first range will always come
4988  * before elements from the second.
4989  *
4990  * The comparison function should have the same effects on ordering as
4991  * the function used for the initial sort.
4992  */
4993  template<typename _InputIterator1, typename _InputIterator2,
4994  typename _OutputIterator, typename _Compare>
4995  _GLIBCXX20_CONSTEXPR
4996  inline _OutputIterator
4997  merge(_InputIterator1 __first1, _InputIterator1 __last1,
4998  _InputIterator2 __first2, _InputIterator2 __last2,
4999  _OutputIterator __result, _Compare __comp)
5000  {
5001  // concept requirements
5002  __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
5003  __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
5004  __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5006  __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5008  __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5011  __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp);
5012  __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp);
5013  __glibcxx_requires_irreflexive_pred2(__first1, __last1, __comp);
5014  __glibcxx_requires_irreflexive_pred2(__first2, __last2, __comp);
5015 
5016  return _GLIBCXX_STD_A::__merge(__first1, __last1,
5017  __first2, __last2, __result,
5018  __gnu_cxx::__ops::__iter_comp_iter(__comp));
5019  }
5020 
5021  template<typename _RandomAccessIterator, typename _Compare>
5022  inline void
5023  __stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last,
5024  _Compare __comp)
5025  {
5026  typedef typename iterator_traits<_RandomAccessIterator>::value_type
5027  _ValueType;
5028  typedef typename iterator_traits<_RandomAccessIterator>::difference_type
5029  _DistanceType;
5030 
5031  typedef _Temporary_buffer<_RandomAccessIterator, _ValueType> _TmpBuf;
5032  _TmpBuf __buf(__first, std::distance(__first, __last));
5033 
5034  if (__buf.begin() == 0)
5035  std::__inplace_stable_sort(__first, __last, __comp);
5036  else
5037  std::__stable_sort_adaptive(__first, __last, __buf.begin(),
5038  _DistanceType(__buf.size()), __comp);
5039  }
5040 
5041  /**
5042  * @brief Sort the elements of a sequence, preserving the relative order
5043  * of equivalent elements.
5044  * @ingroup sorting_algorithms
5045  * @param __first An iterator.
5046  * @param __last Another iterator.
5047  * @return Nothing.
5048  *
5049  * Sorts the elements in the range @p [__first,__last) in ascending order,
5050  * such that for each iterator @p i in the range @p [__first,__last-1),
5051  * @p *(i+1)<*i is false.
5052  *
5053  * The relative ordering of equivalent elements is preserved, so any two
5054  * elements @p x and @p y in the range @p [__first,__last) such that
5055  * @p x<y is false and @p y<x is false will have the same relative
5056  * ordering after calling @p stable_sort().
5057  */
5058  template<typename _RandomAccessIterator>
5059  inline void
5060  stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last)
5061  {
5062  // concept requirements
5063  __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
5064  _RandomAccessIterator>)
5065  __glibcxx_function_requires(_LessThanComparableConcept<
5067  __glibcxx_requires_valid_range(__first, __last);
5068  __glibcxx_requires_irreflexive(__first, __last);
5069 
5070  _GLIBCXX_STD_A::__stable_sort(__first, __last,
5071  __gnu_cxx::__ops::__iter_less_iter());
5072  }
5073 
5074  /**
5075  * @brief Sort the elements of a sequence using a predicate for comparison,
5076  * preserving the relative order of equivalent elements.
5077  * @ingroup sorting_algorithms
5078  * @param __first An iterator.
5079  * @param __last Another iterator.
5080  * @param __comp A comparison functor.
5081  * @return Nothing.
5082  *
5083  * Sorts the elements in the range @p [__first,__last) in ascending order,
5084  * such that for each iterator @p i in the range @p [__first,__last-1),
5085  * @p __comp(*(i+1),*i) is false.
5086  *
5087  * The relative ordering of equivalent elements is preserved, so any two
5088  * elements @p x and @p y in the range @p [__first,__last) such that
5089  * @p __comp(x,y) is false and @p __comp(y,x) is false will have the same
5090  * relative ordering after calling @p stable_sort().
5091  */
5092  template<typename _RandomAccessIterator, typename _Compare>
5093  inline void
5094  stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last,
5095  _Compare __comp)
5096  {
5097  // concept requirements
5098  __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
5099  _RandomAccessIterator>)
5100  __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5103  __glibcxx_requires_valid_range(__first, __last);
5104  __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
5105 
5106  _GLIBCXX_STD_A::__stable_sort(__first, __last,
5107  __gnu_cxx::__ops::__iter_comp_iter(__comp));
5108  }
5109 
5110  template<typename _InputIterator1, typename _InputIterator2,
5111  typename _OutputIterator,
5112  typename _Compare>
5113  _GLIBCXX20_CONSTEXPR
5114  _OutputIterator
5115  __set_union(_InputIterator1 __first1, _InputIterator1 __last1,
5116  _InputIterator2 __first2, _InputIterator2 __last2,
5117  _OutputIterator __result, _Compare __comp)
5118  {
5119  while (__first1 != __last1 && __first2 != __last2)
5120  {
5121  if (__comp(__first1, __first2))
5122  {
5123  *__result = *__first1;
5124  ++__first1;
5125  }
5126  else if (__comp(__first2, __first1))
5127  {
5128  *__result = *__first2;
5129  ++__first2;
5130  }
5131  else
5132  {
5133  *__result = *__first1;
5134  ++__first1;
5135  ++__first2;
5136  }
5137  ++__result;
5138  }
5139  return std::copy(__first2, __last2,
5140  std::copy(__first1, __last1, __result));
5141  }
5142 
5143  /**
5144  * @brief Return the union of two sorted ranges.
5145  * @ingroup set_algorithms
5146  * @param __first1 Start of first range.
5147  * @param __last1 End of first range.
5148  * @param __first2 Start of second range.
5149  * @param __last2 End of second range.
5150  * @param __result Start of output range.
5151  * @return End of the output range.
5152  * @ingroup set_algorithms
5153  *
5154  * This operation iterates over both ranges, copying elements present in
5155  * each range in order to the output range. Iterators increment for each
5156  * range. When the current element of one range is less than the other,
5157  * that element is copied and the iterator advanced. If an element is
5158  * contained in both ranges, the element from the first range is copied and
5159  * both ranges advance. The output range may not overlap either input
5160  * range.
5161  */
5162  template<typename _InputIterator1, typename _InputIterator2,
5163  typename _OutputIterator>
5164  _GLIBCXX20_CONSTEXPR
5165  inline _OutputIterator
5166  set_union(_InputIterator1 __first1, _InputIterator1 __last1,
5167  _InputIterator2 __first2, _InputIterator2 __last2,
5168  _OutputIterator __result)
5169  {
5170  // concept requirements
5171  __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
5172  __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
5173  __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5175  __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5177  __glibcxx_function_requires(_LessThanOpConcept<
5180  __glibcxx_function_requires(_LessThanOpConcept<
5183  __glibcxx_requires_sorted_set(__first1, __last1, __first2);
5184  __glibcxx_requires_sorted_set(__first2, __last2, __first1);
5185  __glibcxx_requires_irreflexive2(__first1, __last1);
5186  __glibcxx_requires_irreflexive2(__first2, __last2);
5187 
5188  return _GLIBCXX_STD_A::__set_union(__first1, __last1,
5189  __first2, __last2, __result,
5190  __gnu_cxx::__ops::__iter_less_iter());
5191  }
5192 
5193  /**
5194  * @brief Return the union of two sorted ranges using a comparison functor.
5195  * @ingroup set_algorithms
5196  * @param __first1 Start of first range.
5197  * @param __last1 End of first range.
5198  * @param __first2 Start of second range.
5199  * @param __last2 End of second range.
5200  * @param __result Start of output range.
5201  * @param __comp The comparison functor.
5202  * @return End of the output range.
5203  * @ingroup set_algorithms
5204  *
5205  * This operation iterates over both ranges, copying elements present in
5206  * each range in order to the output range. Iterators increment for each
5207  * range. When the current element of one range is less than the other
5208  * according to @p __comp, that element is copied and the iterator advanced.
5209  * If an equivalent element according to @p __comp is contained in both
5210  * ranges, the element from the first range is copied and both ranges
5211  * advance. The output range may not overlap either input range.
5212  */
5213  template<typename _InputIterator1, typename _InputIterator2,
5214  typename _OutputIterator, typename _Compare>
5215  _GLIBCXX20_CONSTEXPR
5216  inline _OutputIterator
5217  set_union(_InputIterator1 __first1, _InputIterator1 __last1,
5218  _InputIterator2 __first2, _InputIterator2 __last2,
5219  _OutputIterator __result, _Compare __comp)
5220  {
5221  // concept requirements
5222  __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
5223  __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
5224  __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5226  __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5228  __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5231  __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5234  __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp);
5235  __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp);
5236  __glibcxx_requires_irreflexive_pred2(__first1, __last1, __comp);
5237  __glibcxx_requires_irreflexive_pred2(__first2, __last2, __comp);
5238 
5239  return _GLIBCXX_STD_A::__set_union(__first1, __last1,
5240  __first2, __last2, __result,
5241  __gnu_cxx::__ops::__iter_comp_iter(__comp));
5242  }
5243 
5244  template<typename _InputIterator1, typename _InputIterator2,
5245  typename _OutputIterator,
5246  typename _Compare>
5247  _GLIBCXX20_CONSTEXPR
5248  _OutputIterator
5249  __set_intersection(_InputIterator1 __first1, _InputIterator1 __last1,
5250  _InputIterator2 __first2, _InputIterator2 __last2,
5251  _OutputIterator __result, _Compare __comp)
5252  {
5253  while (__first1 != __last1 && __first2 != __last2)
5254  if (__comp(__first1, __first2))
5255  ++__first1;
5256  else if (__comp(__first2, __first1))
5257  ++__first2;
5258  else
5259  {
5260  *__result = *__first1;
5261  ++__first1;
5262  ++__first2;
5263  ++__result;
5264  }
5265  return __result;
5266  }
5267 
5268  /**
5269  * @brief Return the intersection of two sorted ranges.
5270  * @ingroup set_algorithms
5271  * @param __first1 Start of first range.
5272  * @param __last1 End of first range.
5273  * @param __first2 Start of second range.
5274  * @param __last2 End of second range.
5275  * @param __result Start of output range.
5276  * @return End of the output range.
5277  * @ingroup set_algorithms
5278  *
5279  * This operation iterates over both ranges, copying elements present in
5280  * both ranges in order to the output range. Iterators increment for each
5281  * range. When the current element of one range is less than the other,
5282  * that iterator advances. If an element is contained in both ranges, the
5283  * element from the first range is copied and both ranges advance. The
5284  * output range may not overlap either input range.
5285  */
5286  template<typename _InputIterator1, typename _InputIterator2,
5287  typename _OutputIterator>
5288  _GLIBCXX20_CONSTEXPR
5289  inline _OutputIterator
5290  set_intersection(_InputIterator1 __first1, _InputIterator1 __last1,
5291  _InputIterator2 __first2, _InputIterator2 __last2,
5292  _OutputIterator __result)
5293  {
5294  // concept requirements
5295  __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
5296  __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
5297  __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5299  __glibcxx_function_requires(_LessThanOpConcept<
5302  __glibcxx_function_requires(_LessThanOpConcept<
5305  __glibcxx_requires_sorted_set(__first1, __last1, __first2);
5306  __glibcxx_requires_sorted_set(__first2, __last2, __first1);
5307  __glibcxx_requires_irreflexive2(__first1, __last1);
5308  __glibcxx_requires_irreflexive2(__first2, __last2);
5309 
5310  return _GLIBCXX_STD_A::__set_intersection(__first1, __last1,
5311  __first2, __last2, __result,
5312  __gnu_cxx::__ops::__iter_less_iter());
5313  }
5314 
5315  /**
5316  * @brief Return the intersection of two sorted ranges using comparison
5317  * functor.
5318  * @ingroup set_algorithms
5319  * @param __first1 Start of first range.
5320  * @param __last1 End of first range.
5321  * @param __first2 Start of second range.
5322  * @param __last2 End of second range.
5323  * @param __result Start of output range.
5324  * @param __comp The comparison functor.
5325  * @return End of the output range.
5326  * @ingroup set_algorithms
5327  *
5328  * This operation iterates over both ranges, copying elements present in
5329  * both ranges in order to the output range. Iterators increment for each
5330  * range. When the current element of one range is less than the other
5331  * according to @p __comp, that iterator advances. If an element is
5332  * contained in both ranges according to @p __comp, the element from the
5333  * first range is copied and both ranges advance. The output range may not
5334  * overlap either input range.
5335  */
5336  template<typename _InputIterator1, typename _InputIterator2,
5337  typename _OutputIterator, typename _Compare>
5338  _GLIBCXX20_CONSTEXPR
5339  inline _OutputIterator
5340  set_intersection(_InputIterator1 __first1, _InputIterator1 __last1,
5341  _InputIterator2 __first2, _InputIterator2 __last2,
5342  _OutputIterator __result, _Compare __comp)
5343  {
5344  // concept requirements
5345  __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
5346  __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
5347  __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5349  __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5352  __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5355  __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp);
5356  __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp);
5357  __glibcxx_requires_irreflexive_pred2(__first1, __last1, __comp);
5358  __glibcxx_requires_irreflexive_pred2(__first2, __last2, __comp);
5359 
5360  return _GLIBCXX_STD_A::__set_intersection(__first1, __last1,
5361  __first2, __last2, __result,
5362  __gnu_cxx::__ops::__iter_comp_iter(__comp));
5363  }
5364 
5365  template<typename _InputIterator1, typename _InputIterator2,
5366  typename _OutputIterator,
5367  typename _Compare>
5368  _GLIBCXX20_CONSTEXPR
5369  _OutputIterator
5370  __set_difference(_InputIterator1 __first1, _InputIterator1 __last1,
5371  _InputIterator2 __first2, _InputIterator2 __last2,
5372  _OutputIterator __result, _Compare __comp)
5373  {
5374  while (__first1 != __last1 && __first2 != __last2)
5375  if (__comp(__first1, __first2))
5376  {
5377  *__result = *__first1;
5378  ++__first1;
5379  ++__result;
5380  }
5381  else if (__comp(__first2, __first1))
5382  ++__first2;
5383  else
5384  {
5385  ++__first1;
5386  ++__first2;
5387  }
5388  return std::copy(__first1, __last1, __result);
5389  }
5390 
5391  /**
5392  * @brief Return the difference of two sorted ranges.
5393  * @ingroup set_algorithms
5394  * @param __first1 Start of first range.
5395  * @param __last1 End of first range.
5396  * @param __first2 Start of second range.
5397  * @param __last2 End of second range.
5398  * @param __result Start of output range.
5399  * @return End of the output range.
5400  * @ingroup set_algorithms
5401  *
5402  * This operation iterates over both ranges, copying elements present in
5403  * the first range but not the second in order to the output range.
5404  * Iterators increment for each range. When the current element of the
5405  * first range is less than the second, that element is copied and the
5406  * iterator advances. If the current element of the second range is less,
5407  * the iterator advances, but no element is copied. If an element is
5408  * contained in both ranges, no elements are copied and both ranges
5409  * advance. The output range may not overlap either input range.
5410  */
5411  template<typename _InputIterator1, typename _InputIterator2,
5412  typename _OutputIterator>
5413  _GLIBCXX20_CONSTEXPR
5414  inline _OutputIterator
5415  set_difference(_InputIterator1 __first1, _InputIterator1 __last1,
5416  _InputIterator2 __first2, _InputIterator2 __last2,
5417  _OutputIterator __result)
5418  {
5419  // concept requirements
5420  __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
5421  __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
5422  __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5424  __glibcxx_function_requires(_LessThanOpConcept<
5427  __glibcxx_function_requires(_LessThanOpConcept<
5430  __glibcxx_requires_sorted_set(__first1, __last1, __first2);
5431  __glibcxx_requires_sorted_set(__first2, __last2, __first1);
5432  __glibcxx_requires_irreflexive2(__first1, __last1);
5433  __glibcxx_requires_irreflexive2(__first2, __last2);
5434 
5435  return _GLIBCXX_STD_A::__set_difference(__first1, __last1,
5436  __first2, __last2, __result,
5437  __gnu_cxx::__ops::__iter_less_iter());
5438  }
5439 
5440  /**
5441  * @brief Return the difference of two sorted ranges using comparison
5442  * functor.
5443  * @ingroup set_algorithms
5444  * @param __first1 Start of first range.
5445  * @param __last1 End of first range.
5446  * @param __first2 Start of second range.
5447  * @param __last2 End of second range.
5448  * @param __result Start of output range.
5449  * @param __comp The comparison functor.
5450  * @return End of the output range.
5451  * @ingroup set_algorithms
5452  *
5453  * This operation iterates over both ranges, copying elements present in
5454  * the first range but not the second in order to the output range.
5455  * Iterators increment for each range. When the current element of the
5456  * first range is less than the second according to @p __comp, that element
5457  * is copied and the iterator advances. If the current element of the
5458  * second range is less, no element is copied and the iterator advances.
5459  * If an element is contained in both ranges according to @p __comp, no
5460  * elements are copied and both ranges advance. The output range may not
5461  * overlap either input range.
5462  */
5463  template<typename _InputIterator1, typename _InputIterator2,
5464  typename _OutputIterator, typename _Compare>
5465  _GLIBCXX20_CONSTEXPR
5466  inline _OutputIterator
5467  set_difference(_InputIterator1 __first1, _InputIterator1 __last1,
5468  _InputIterator2 __first2, _InputIterator2 __last2,
5469  _OutputIterator __result, _Compare __comp)
5470  {
5471  // concept requirements
5472  __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
5473  __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
5474  __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5476  __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5479  __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5482  __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp);
5483  __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp);
5484  __glibcxx_requires_irreflexive_pred2(__first1, __last1, __comp);
5485  __glibcxx_requires_irreflexive_pred2(__first2, __last2, __comp);
5486 
5487  return _GLIBCXX_STD_A::__set_difference(__first1, __last1,
5488  __first2, __last2, __result,
5489  __gnu_cxx::__ops::__iter_comp_iter(__comp));
5490  }
5491 
5492  template<typename _InputIterator1, typename _InputIterator2,
5493  typename _OutputIterator,
5494  typename _Compare>
5495  _GLIBCXX20_CONSTEXPR
5496  _OutputIterator
5497  __set_symmetric_difference(_InputIterator1 __first1,
5498  _InputIterator1 __last1,
5499  _InputIterator2 __first2,
5500  _InputIterator2 __last2,
5501  _OutputIterator __result,
5502  _Compare __comp)
5503  {
5504  while (__first1 != __last1 && __first2 != __last2)
5505  if (__comp(__first1, __first2))
5506  {
5507  *__result = *__first1;
5508  ++__first1;
5509  ++__result;
5510  }
5511  else if (__comp(__first2, __first1))
5512  {
5513  *__result = *__first2;
5514  ++__first2;
5515  ++__result;
5516  }
5517  else
5518  {
5519  ++__first1;
5520  ++__first2;
5521  }
5522  return std::copy(__first2, __last2,
5523  std::copy(__first1, __last1, __result));
5524  }
5525 
5526  /**
5527  * @brief Return the symmetric difference of two sorted ranges.
5528  * @ingroup set_algorithms
5529  * @param __first1 Start of first range.
5530  * @param __last1 End of first range.
5531  * @param __first2 Start of second range.
5532  * @param __last2 End of second range.
5533  * @param __result Start of output range.
5534  * @return End of the output range.
5535  * @ingroup set_algorithms
5536  *
5537  * This operation iterates over both ranges, copying elements present in
5538  * one range but not the other in order to the output range. Iterators
5539  * increment for each range. When the current element of one range is less
5540  * than the other, that element is copied and the iterator advances. If an
5541  * element is contained in both ranges, no elements are copied and both
5542  * ranges advance. The output range may not overlap either input range.
5543  */
5544  template<typename _InputIterator1, typename _InputIterator2,
5545  typename _OutputIterator>
5546  _GLIBCXX20_CONSTEXPR
5547  inline _OutputIterator
5548  set_symmetric_difference(_InputIterator1 __first1, _InputIterator1 __last1,
5549  _InputIterator2 __first2, _InputIterator2 __last2,
5550  _OutputIterator __result)
5551  {
5552  // concept requirements
5553  __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
5554  __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
5555  __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5557  __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5559  __glibcxx_function_requires(_LessThanOpConcept<
5562  __glibcxx_function_requires(_LessThanOpConcept<
5565  __glibcxx_requires_sorted_set(__first1, __last1, __first2);
5566  __glibcxx_requires_sorted_set(__first2, __last2, __first1);
5567  __glibcxx_requires_irreflexive2(__first1, __last1);
5568  __glibcxx_requires_irreflexive2(__first2, __last2);
5569 
5570  return _GLIBCXX_STD_A::__set_symmetric_difference(__first1, __last1,
5571  __first2, __last2, __result,
5572  __gnu_cxx::__ops::__iter_less_iter());
5573  }
5574 
5575  /**
5576  * @brief Return the symmetric difference of two sorted ranges using
5577  * comparison functor.
5578  * @ingroup set_algorithms
5579  * @param __first1 Start of first range.
5580  * @param __last1 End of first range.
5581  * @param __first2 Start of second range.
5582  * @param __last2 End of second range.
5583  * @param __result Start of output range.
5584  * @param __comp The comparison functor.
5585  * @return End of the output range.
5586  * @ingroup set_algorithms
5587  *
5588  * This operation iterates over both ranges, copying elements present in
5589  * one range but not the other in order to the output range. Iterators
5590  * increment for each range. When the current element of one range is less
5591  * than the other according to @p comp, that element is copied and the
5592  * iterator advances. If an element is contained in both ranges according
5593  * to @p __comp, no elements are copied and both ranges advance. The output
5594  * range may not overlap either input range.
5595  */
5596  template<typename _InputIterator1, typename _InputIterator2,
5597  typename _OutputIterator, typename _Compare>
5598  _GLIBCXX20_CONSTEXPR
5599  inline _OutputIterator
5600  set_symmetric_difference(_InputIterator1 __first1, _InputIterator1 __last1,
5601  _InputIterator2 __first2, _InputIterator2 __last2,
5602  _OutputIterator __result,
5603  _Compare __comp)
5604  {
5605  // concept requirements
5606  __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
5607  __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
5608  __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5610  __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5612  __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5615  __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5618  __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp);
5619  __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp);
5620  __glibcxx_requires_irreflexive_pred2(__first1, __last1, __comp);
5621  __glibcxx_requires_irreflexive_pred2(__first2, __last2, __comp);
5622 
5623  return _GLIBCXX_STD_A::__set_symmetric_difference(__first1, __last1,
5624  __first2, __last2, __result,
5625  __gnu_cxx::__ops::__iter_comp_iter(__comp));
5626  }
5627 
5628  template<typename _ForwardIterator, typename _Compare>
5629  _GLIBCXX14_CONSTEXPR
5630  _ForwardIterator
5631  __min_element(_ForwardIterator __first, _ForwardIterator __last,
5632  _Compare __comp)
5633  {
5634  if (__first == __last)
5635  return __first;
5636  _ForwardIterator __result = __first;
5637  while (++__first != __last)
5638  if (__comp(__first, __result))
5639  __result = __first;
5640  return __result;
5641  }
5642 
5643  /**
5644  * @brief Return the minimum element in a range.
5645  * @ingroup sorting_algorithms
5646  * @param __first Start of range.
5647  * @param __last End of range.
5648  * @return Iterator referencing the first instance of the smallest value.
5649  */
5650  template<typename _ForwardIterator>
5651  _GLIBCXX14_CONSTEXPR
5652  _ForwardIterator
5653  inline min_element(_ForwardIterator __first, _ForwardIterator __last)
5654  {
5655  // concept requirements
5656  __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
5657  __glibcxx_function_requires(_LessThanComparableConcept<
5659  __glibcxx_requires_valid_range(__first, __last);
5660  __glibcxx_requires_irreflexive(__first, __last);
5661 
5662  return _GLIBCXX_STD_A::__min_element(__first, __last,
5663  __gnu_cxx::__ops::__iter_less_iter());
5664  }
5665 
5666  /**
5667  * @brief Return the minimum element in a range using comparison functor.
5668  * @ingroup sorting_algorithms
5669  * @param __first Start of range.
5670  * @param __last End of range.
5671  * @param __comp Comparison functor.
5672  * @return Iterator referencing the first instance of the smallest value
5673  * according to __comp.
5674  */
5675  template<typename _ForwardIterator, typename _Compare>
5676  _GLIBCXX14_CONSTEXPR
5677  inline _ForwardIterator
5678  min_element(_ForwardIterator __first, _ForwardIterator __last,
5679  _Compare __comp)
5680  {
5681  // concept requirements
5682  __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
5683  __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5686  __glibcxx_requires_valid_range(__first, __last);
5687  __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
5688 
5689  return _GLIBCXX_STD_A::__min_element(__first, __last,
5690  __gnu_cxx::__ops::__iter_comp_iter(__comp));
5691  }
5692 
5693  template<typename _ForwardIterator, typename _Compare>
5694  _GLIBCXX14_CONSTEXPR
5695  _ForwardIterator
5696  __max_element(_ForwardIterator __first, _ForwardIterator __last,
5697  _Compare __comp)
5698  {
5699  if (__first == __last) return __first;
5700  _ForwardIterator __result = __first;
5701  while (++__first != __last)
5702  if (__comp(__result, __first))
5703  __result = __first;
5704  return __result;
5705  }
5706 
5707  /**
5708  * @brief Return the maximum element in a range.
5709  * @ingroup sorting_algorithms
5710  * @param __first Start of range.
5711  * @param __last End of range.
5712  * @return Iterator referencing the first instance of the largest value.
5713  */
5714  template<typename _ForwardIterator>
5715  _GLIBCXX14_CONSTEXPR
5716  inline _ForwardIterator
5717  max_element(_ForwardIterator __first, _ForwardIterator __last)
5718  {
5719  // concept requirements
5720  __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
5721  __glibcxx_function_requires(_LessThanComparableConcept<
5723  __glibcxx_requires_valid_range(__first, __last);
5724  __glibcxx_requires_irreflexive(__first, __last);
5725 
5726  return _GLIBCXX_STD_A::__max_element(__first, __last,
5727  __gnu_cxx::__ops::__iter_less_iter());
5728  }
5729 
5730  /**
5731  * @brief Return the maximum element in a range using comparison functor.
5732  * @ingroup sorting_algorithms
5733  * @param __first Start of range.
5734  * @param __last End of range.
5735  * @param __comp Comparison functor.
5736  * @return Iterator referencing the first instance of the largest value
5737  * according to __comp.
5738  */
5739  template<typename _ForwardIterator, typename _Compare>
5740  _GLIBCXX14_CONSTEXPR
5741  inline _ForwardIterator
5742  max_element(_ForwardIterator __first, _ForwardIterator __last,
5743  _Compare __comp)
5744  {
5745  // concept requirements
5746  __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
5747  __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5750  __glibcxx_requires_valid_range(__first, __last);
5751  __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
5752 
5753  return _GLIBCXX_STD_A::__max_element(__first, __last,
5754  __gnu_cxx::__ops::__iter_comp_iter(__comp));
5755  }
5756 
5757 #if __cplusplus >= 201402L
5758  /// Reservoir sampling algorithm.
5759  template<typename _InputIterator, typename _RandomAccessIterator,
5760  typename _Size, typename _UniformRandomBitGenerator>
5761  _RandomAccessIterator
5762  __sample(_InputIterator __first, _InputIterator __last, input_iterator_tag,
5763  _RandomAccessIterator __out, random_access_iterator_tag,
5764  _Size __n, _UniformRandomBitGenerator&& __g)
5765  {
5766  using __distrib_type = uniform_int_distribution<_Size>;
5767  using __param_type = typename __distrib_type::param_type;
5768  __distrib_type __d{};
5769  _Size __sample_sz = 0;
5770  while (__first != __last && __sample_sz != __n)
5771  {
5772  __out[__sample_sz++] = *__first;
5773  ++__first;
5774  }
5775  for (auto __pop_sz = __sample_sz; __first != __last;
5776  ++__first, (void) ++__pop_sz)
5777  {
5778  const auto __k = __d(__g, __param_type{0, __pop_sz});
5779  if (__k < __n)
5780  __out[__k] = *__first;
5781  }
5782  return __out + __sample_sz;
5783  }
5784 
5785  /// Selection sampling algorithm.
5786  template<typename _ForwardIterator, typename _OutputIterator, typename _Cat,
5787  typename _Size, typename _UniformRandomBitGenerator>
5788  _OutputIterator
5789  __sample(_ForwardIterator __first, _ForwardIterator __last,
5791  _OutputIterator __out, _Cat,
5792  _Size __n, _UniformRandomBitGenerator&& __g)
5793  {
5794  using __distrib_type = uniform_int_distribution<_Size>;
5795  using __param_type = typename __distrib_type::param_type;
5796  using _USize = make_unsigned_t<_Size>;
5799 
5800  if (__first == __last)
5801  return __out;
5802 
5803  __distrib_type __d{};
5804  _Size __unsampled_sz = std::distance(__first, __last);
5805  __n = std::min(__n, __unsampled_sz);
5806 
5807  // If possible, we use __gen_two_uniform_ints to efficiently produce
5808  // two random numbers using a single distribution invocation:
5809 
5810  const __uc_type __urngrange = __g.max() - __g.min();
5811  if (__urngrange / __uc_type(__unsampled_sz) >= __uc_type(__unsampled_sz))
5812  // I.e. (__urngrange >= __unsampled_sz * __unsampled_sz) but without
5813  // wrapping issues.
5814  {
5815  while (__n != 0 && __unsampled_sz >= 2)
5816  {
5817  const pair<_Size, _Size> __p =
5818  __gen_two_uniform_ints(__unsampled_sz, __unsampled_sz - 1, __g);
5819 
5820  --__unsampled_sz;
5821  if (__p.first < __n)
5822  {
5823  *__out++ = *__first;
5824  --__n;
5825  }
5826 
5827  ++__first;
5828 
5829  if (__n == 0) break;
5830 
5831  --__unsampled_sz;
5832  if (__p.second < __n)
5833  {
5834  *__out++ = *__first;
5835  --__n;
5836  }
5837 
5838  ++__first;
5839  }
5840  }
5841 
5842  // The loop above is otherwise equivalent to this one-at-a-time version:
5843 
5844  for (; __n != 0; ++__first)
5845  if (__d(__g, __param_type{0, --__unsampled_sz}) < __n)
5846  {
5847  *__out++ = *__first;
5848  --__n;
5849  }
5850  return __out;
5851  }
5852 
5853 #if __cplusplus > 201402L
5854 #define __cpp_lib_sample 201603
5855  /// Take a random sample from a population.
5856  template<typename _PopulationIterator, typename _SampleIterator,
5857  typename _Distance, typename _UniformRandomBitGenerator>
5858  _SampleIterator
5859  sample(_PopulationIterator __first, _PopulationIterator __last,
5860  _SampleIterator __out, _Distance __n,
5861  _UniformRandomBitGenerator&& __g)
5862  {
5863  using __pop_cat = typename
5865  using __samp_cat = typename
5867 
5868  static_assert(
5869  __or_<is_convertible<__pop_cat, forward_iterator_tag>,
5870  is_convertible<__samp_cat, random_access_iterator_tag>>::value,
5871  "output range must use a RandomAccessIterator when input range"
5872  " does not meet the ForwardIterator requirements");
5873 
5874  static_assert(is_integral<_Distance>::value,
5875  "sample size must be an integer type");
5876 
5877  typename iterator_traits<_PopulationIterator>::difference_type __d = __n;
5878  return _GLIBCXX_STD_A::
5879  __sample(__first, __last, __pop_cat{}, __out, __samp_cat{}, __d,
5880  std::forward<_UniformRandomBitGenerator>(__g));
5881  }
5882 #endif // C++17
5883 #endif // C++14
5884 
5885 _GLIBCXX_END_NAMESPACE_ALGO
5886 _GLIBCXX_END_NAMESPACE_VERSION
5887 } // namespace std
5888 
5889 #endif /* _STL_ALGO_H */
constexpr _EuclideanRingElement __gcd(_EuclideanRingElement __m, _EuclideanRingElement __n)
Definition: stl_algo.h:1219
_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:5762
constexpr int __lg(int __n)
This is a helper function for the sort routines and for random.tcc.
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
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
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
constexpr void __insertion_sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
This is a helper function for the sort routine.
Definition: stl_algo.h:1839
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
constexpr _InputIterator __find_if_not(_InputIterator __first, _InputIterator __last, _Predicate __pred)
Provided for stable_partition to use.
Definition: stl_algo.h:103
constexpr _ForwardIterator __partition(_ForwardIterator __first, _ForwardIterator __last, _Predicate __pred, forward_iterator_tag)
This is a helper function...
Definition: stl_algo.h:1481
constexpr iterator_traits< _InputIterator >::difference_type distance(_InputIterator __first, _InputIterator __last)
A generalization of pointer arithmetic.
_T1 first
The first member.
Definition: stl_pair.h:217
constexpr _RandomAccessIterator __unguarded_partition(_RandomAccessIterator __first, _RandomAccessIterator __last, _RandomAccessIterator __pivot, _Compare __comp)
This is a helper function...
Definition: stl_algo.h:1898
constexpr _ForwardIterator __search_n_aux(_ForwardIterator __first, _ForwardIterator __last, _Integer __count, _UnaryPredicate __unary_pred, std::forward_iterator_tag)
Definition: stl_algo.h:194
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
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
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
Bidirectional iterators support a superset of forward iterator operations.
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
constexpr _ForwardIterator max_element(_ForwardIterator __first, _ForwardIterator __last, _Compare __comp)
Return the maximum element in a range using comparison functor.
Definition: stl_algo.h:5742
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
Marking output iterators.
_T2 second
The second member.
Definition: stl_pair.h:218
constexpr _ForwardIterator min_element(_ForwardIterator __first, _ForwardIterator __last, _Compare __comp)
Return the minimum element in a range using comparison functor.
Definition: stl_algo.h:5678
typename common_type< _Tp...>::type common_type_t
Alias template for common_type.
Definition: type_traits:2562
_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
constexpr void __unguarded_linear_insert(_RandomAccessIterator __last, _Compare __comp)
This is a helper function for the sort routine.
Definition: stl_algo.h:1819
constexpr iterator_traits< _Iter >::iterator_category __iterator_category(const _Iter &)
constexpr void iter_swap(_ForwardIterator1 __a, _ForwardIterator2 __b)
Swaps the contents of two iterators.
Definition: stl_algobase.h:152
constexpr const _Tp & max(const _Tp &, const _Tp &)
This does what you think it does.
Definition: stl_algobase.h:254
constexpr void advance(_InputIterator &__i, _Distance __n)
A generalization of pointer arithmetic.
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
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
typename remove_reference< _Tp >::type remove_reference_t
Alias template for remove_reference.
Definition: type_traits:1635
Random-access iterators support a superset of bidirectional iterator operations.
Uniform discrete distribution for random numbers. A discrete random distribution on the range with e...
Marking input iterators.
constexpr _ForwardIterator is_sorted_until(_ForwardIterator __first, _ForwardIterator __last, _Compare __comp)
Determines the end of a sorted sequence using comparison functor.
Definition: stl_algo.h:3294
_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
common_type
Definition: type_traits:2215
constexpr _RandomAccessIterator __unguarded_partition_pivot(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
This is a helper function...
Definition: stl_algo.h:1920
Traits class for iterators.
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
_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
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
Struct holding two objects of arbitrary type.
Definition: stl_pair.h:211
constexpr _ForwardIterator2 swap_ranges(_ForwardIterator1 __first1, _ForwardIterator1 __last1, _ForwardIterator2 __first2)
Swap the elements of two sequences.
Definition: stl_algobase.h:201
constexpr const _Tp & min(const _Tp &, const _Tp &)
This does what you think it does.
Definition: stl_algobase.h:230
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
constexpr std::remove_reference< _Tp >::type && move(_Tp &&__t) noexcept
Convert a value to an rvalue.
Definition: move.h:101
constexpr _InputIterator __find_if(_InputIterator __first, _InputIterator __last, _Predicate __pred, input_iterator_tag)
This is an overload used by find algos for the Input Iterator case.
constexpr _OutputIterator __unique_copy(_ForwardIterator __first, _ForwardIterator __last, _OutputIterator __result, _BinaryPredicate __binary_pred, forward_iterator_tag, output_iterator_tag)
Definition: stl_algo.h:1029
constexpr void __reverse(_BidirectionalIterator __first, _BidirectionalIterator __last, bidirectional_iterator_tag)
Definition: stl_algo.h:1115
Forward iterators support a superset of input iterator operations.
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
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
typename make_unsigned< _Tp >::type make_unsigned_t
Alias template for make_unsigned.
Definition: type_traits:1965