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