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