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