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