libstdc++
stl_algo.h
Go to the documentation of this file.
1 // Algorithm implementation -*- C++ -*-
2 
3 // Copyright (C) 2001-2015 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,
339  forward_iterator_tag, forward_iterator_tag,
340  _BinaryPredicate __comp)
341  {
342  if (__first2 == __last2)
343  return __last1;
344 
345  _ForwardIterator1 __result = __last1;
346  while (1)
347  {
348  _ForwardIterator1 __new_result
349  = std::__search(__first1, __last1, __first2, __last2, __comp);
350  if (__new_result == __last1)
351  return __result;
352  else
353  {
354  __result = __new_result;
355  __first1 = __new_result;
356  ++__first1;
357  }
358  }
359  }
360 
361  // find_end for bidirectional iterators (much faster).
362  template<typename _BidirectionalIterator1, typename _BidirectionalIterator2,
363  typename _BinaryPredicate>
364  _BidirectionalIterator1
365  __find_end(_BidirectionalIterator1 __first1,
366  _BidirectionalIterator1 __last1,
367  _BidirectionalIterator2 __first2,
368  _BidirectionalIterator2 __last2,
369  bidirectional_iterator_tag, bidirectional_iterator_tag,
370  _BinaryPredicate __comp)
371  {
372  // concept requirements
373  __glibcxx_function_requires(_BidirectionalIteratorConcept<
374  _BidirectionalIterator1>)
375  __glibcxx_function_requires(_BidirectionalIteratorConcept<
376  _BidirectionalIterator2>)
377 
378  typedef reverse_iterator<_BidirectionalIterator1> _RevIterator1;
379  typedef reverse_iterator<_BidirectionalIterator2> _RevIterator2;
380 
381  _RevIterator1 __rlast1(__first1);
382  _RevIterator2 __rlast2(__first2);
383  _RevIterator1 __rresult = std::__search(_RevIterator1(__last1), __rlast1,
384  _RevIterator2(__last2), __rlast2,
385  __comp);
386 
387  if (__rresult == __rlast1)
388  return __last1;
389  else
390  {
391  _BidirectionalIterator1 __result = __rresult.base();
392  std::advance(__result, -std::distance(__first2, __last2));
393  return __result;
394  }
395  }
396 
397  /**
398  * @brief Find last matching subsequence in a sequence.
399  * @ingroup non_mutating_algorithms
400  * @param __first1 Start of range to search.
401  * @param __last1 End of range to search.
402  * @param __first2 Start of sequence to match.
403  * @param __last2 End of sequence to match.
404  * @return The last iterator @c i in the range
405  * @p [__first1,__last1-(__last2-__first2)) such that @c *(i+N) ==
406  * @p *(__first2+N) for each @c N in the range @p
407  * [0,__last2-__first2), or @p __last1 if no such iterator exists.
408  *
409  * Searches the range @p [__first1,__last1) for a sub-sequence that
410  * compares equal value-by-value with the sequence given by @p
411  * [__first2,__last2) and returns an iterator to the __first
412  * element of the sub-sequence, or @p __last1 if the sub-sequence
413  * is not found. The sub-sequence will be the last such
414  * subsequence contained in [__first1,__last1).
415  *
416  * Because the sub-sequence must lie completely within the range @p
417  * [__first1,__last1) it must start at a position less than @p
418  * __last1-(__last2-__first2) where @p __last2-__first2 is the
419  * length of the sub-sequence. This means that the returned
420  * iterator @c i will be in the range @p
421  * [__first1,__last1-(__last2-__first2))
422  */
423  template<typename _ForwardIterator1, typename _ForwardIterator2>
424  inline _ForwardIterator1
425  find_end(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
426  _ForwardIterator2 __first2, _ForwardIterator2 __last2)
427  {
428  // concept requirements
429  __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator1>)
430  __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator2>)
431  __glibcxx_function_requires(_EqualOpConcept<
432  typename iterator_traits<_ForwardIterator1>::value_type,
433  typename iterator_traits<_ForwardIterator2>::value_type>)
434  __glibcxx_requires_valid_range(__first1, __last1);
435  __glibcxx_requires_valid_range(__first2, __last2);
436 
437  return std::__find_end(__first1, __last1, __first2, __last2,
438  std::__iterator_category(__first1),
439  std::__iterator_category(__first2),
440  __gnu_cxx::__ops::__iter_equal_to_iter());
441  }
442 
443  /**
444  * @brief Find last matching subsequence in a sequence using a predicate.
445  * @ingroup non_mutating_algorithms
446  * @param __first1 Start of range to search.
447  * @param __last1 End of range to search.
448  * @param __first2 Start of sequence to match.
449  * @param __last2 End of sequence to match.
450  * @param __comp The predicate to use.
451  * @return The last iterator @c i in the range @p
452  * [__first1,__last1-(__last2-__first2)) such that @c
453  * predicate(*(i+N), @p (__first2+N)) is true for each @c N in the
454  * range @p [0,__last2-__first2), or @p __last1 if no such iterator
455  * exists.
456  *
457  * Searches the range @p [__first1,__last1) for a sub-sequence that
458  * compares equal value-by-value with the sequence given by @p
459  * [__first2,__last2) using comp as a predicate and returns an
460  * iterator to the first element of the sub-sequence, or @p __last1
461  * if the sub-sequence is not found. The sub-sequence will be the
462  * last such subsequence contained in [__first,__last1).
463  *
464  * Because the sub-sequence must lie completely within the range @p
465  * [__first1,__last1) it must start at a position less than @p
466  * __last1-(__last2-__first2) where @p __last2-__first2 is the
467  * length of the sub-sequence. This means that the returned
468  * iterator @c i will be in the range @p
469  * [__first1,__last1-(__last2-__first2))
470  */
471  template<typename _ForwardIterator1, typename _ForwardIterator2,
472  typename _BinaryPredicate>
473  inline _ForwardIterator1
474  find_end(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
475  _ForwardIterator2 __first2, _ForwardIterator2 __last2,
476  _BinaryPredicate __comp)
477  {
478  // concept requirements
479  __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator1>)
480  __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator2>)
481  __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
482  typename iterator_traits<_ForwardIterator1>::value_type,
483  typename iterator_traits<_ForwardIterator2>::value_type>)
484  __glibcxx_requires_valid_range(__first1, __last1);
485  __glibcxx_requires_valid_range(__first2, __last2);
486 
487  return std::__find_end(__first1, __last1, __first2, __last2,
488  std::__iterator_category(__first1),
489  std::__iterator_category(__first2),
490  __gnu_cxx::__ops::__iter_comp_iter(__comp));
491  }
492 
493 #if __cplusplus >= 201103L
494  /**
495  * @brief Checks that a predicate is true for all the elements
496  * of a sequence.
497  * @ingroup non_mutating_algorithms
498  * @param __first An input iterator.
499  * @param __last An input iterator.
500  * @param __pred A predicate.
501  * @return True if the check is true, false otherwise.
502  *
503  * Returns true if @p __pred is true for each element in the range
504  * @p [__first,__last), and false otherwise.
505  */
506  template<typename _InputIterator, typename _Predicate>
507  inline bool
508  all_of(_InputIterator __first, _InputIterator __last, _Predicate __pred)
509  { return __last == std::find_if_not(__first, __last, __pred); }
510 
511  /**
512  * @brief Checks that a predicate is false for all the elements
513  * of a sequence.
514  * @ingroup non_mutating_algorithms
515  * @param __first An input iterator.
516  * @param __last An input iterator.
517  * @param __pred A predicate.
518  * @return True if the check is true, false otherwise.
519  *
520  * Returns true if @p __pred is false for each element in the range
521  * @p [__first,__last), and false otherwise.
522  */
523  template<typename _InputIterator, typename _Predicate>
524  inline bool
525  none_of(_InputIterator __first, _InputIterator __last, _Predicate __pred)
526  { return __last == _GLIBCXX_STD_A::find_if(__first, __last, __pred); }
527 
528  /**
529  * @brief Checks that a predicate is false for at least an element
530  * of a sequence.
531  * @ingroup non_mutating_algorithms
532  * @param __first An input iterator.
533  * @param __last An input iterator.
534  * @param __pred A predicate.
535  * @return True if the check is true, false otherwise.
536  *
537  * Returns true if an element exists in the range @p
538  * [__first,__last) such that @p __pred is true, and false
539  * otherwise.
540  */
541  template<typename _InputIterator, typename _Predicate>
542  inline bool
543  any_of(_InputIterator __first, _InputIterator __last, _Predicate __pred)
544  { return !std::none_of(__first, __last, __pred); }
545 
546  /**
547  * @brief Find the first element in a sequence for which a
548  * predicate is false.
549  * @ingroup non_mutating_algorithms
550  * @param __first An input iterator.
551  * @param __last An input iterator.
552  * @param __pred A predicate.
553  * @return The first iterator @c i in the range @p [__first,__last)
554  * such that @p __pred(*i) is false, or @p __last if no such iterator exists.
555  */
556  template<typename _InputIterator, typename _Predicate>
557  inline _InputIterator
558  find_if_not(_InputIterator __first, _InputIterator __last,
559  _Predicate __pred)
560  {
561  // concept requirements
562  __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
563  __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
564  typename iterator_traits<_InputIterator>::value_type>)
565  __glibcxx_requires_valid_range(__first, __last);
566  return std::__find_if_not(__first, __last,
567  __gnu_cxx::__ops::__pred_iter(__pred));
568  }
569 
570  /**
571  * @brief Checks whether the sequence is partitioned.
572  * @ingroup mutating_algorithms
573  * @param __first An input iterator.
574  * @param __last An input iterator.
575  * @param __pred A predicate.
576  * @return True if the range @p [__first,__last) is partioned by @p __pred,
577  * i.e. if all elements that satisfy @p __pred appear before those that
578  * do not.
579  */
580  template<typename _InputIterator, typename _Predicate>
581  inline bool
582  is_partitioned(_InputIterator __first, _InputIterator __last,
583  _Predicate __pred)
584  {
585  __first = std::find_if_not(__first, __last, __pred);
586  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>
824  pair<_OutputIterator1, _OutputIterator2>
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  inline namespace _V2
1241  {
1242 
1243  /// This is a helper function for the rotate algorithm.
1244  template<typename _ForwardIterator>
1245  _ForwardIterator
1246  __rotate(_ForwardIterator __first,
1247  _ForwardIterator __middle,
1248  _ForwardIterator __last,
1249  forward_iterator_tag)
1250  {
1251  if (__first == __middle)
1252  return __last;
1253  else if (__last == __middle)
1254  return __first;
1255 
1256  _ForwardIterator __first2 = __middle;
1257  do
1258  {
1259  std::iter_swap(__first, __first2);
1260  ++__first;
1261  ++__first2;
1262  if (__first == __middle)
1263  __middle = __first2;
1264  }
1265  while (__first2 != __last);
1266 
1267  _ForwardIterator __ret = __first;
1268 
1269  __first2 = __middle;
1270 
1271  while (__first2 != __last)
1272  {
1273  std::iter_swap(__first, __first2);
1274  ++__first;
1275  ++__first2;
1276  if (__first == __middle)
1277  __middle = __first2;
1278  else if (__first2 == __last)
1279  __first2 = __middle;
1280  }
1281  return __ret;
1282  }
1283 
1284  /// This is a helper function for the rotate algorithm.
1285  template<typename _BidirectionalIterator>
1286  _BidirectionalIterator
1287  __rotate(_BidirectionalIterator __first,
1288  _BidirectionalIterator __middle,
1289  _BidirectionalIterator __last,
1290  bidirectional_iterator_tag)
1291  {
1292  // concept requirements
1293  __glibcxx_function_requires(_Mutable_BidirectionalIteratorConcept<
1294  _BidirectionalIterator>)
1295 
1296  if (__first == __middle)
1297  return __last;
1298  else if (__last == __middle)
1299  return __first;
1300 
1301  std::__reverse(__first, __middle, bidirectional_iterator_tag());
1302  std::__reverse(__middle, __last, bidirectional_iterator_tag());
1303 
1304  while (__first != __middle && __middle != __last)
1305  {
1306  std::iter_swap(__first, --__last);
1307  ++__first;
1308  }
1309 
1310  if (__first == __middle)
1311  {
1312  std::__reverse(__middle, __last, bidirectional_iterator_tag());
1313  return __last;
1314  }
1315  else
1316  {
1317  std::__reverse(__first, __middle, bidirectional_iterator_tag());
1318  return __first;
1319  }
1320  }
1321 
1322  /// This is a helper function for the rotate algorithm.
1323  template<typename _RandomAccessIterator>
1324  _RandomAccessIterator
1325  __rotate(_RandomAccessIterator __first,
1326  _RandomAccessIterator __middle,
1327  _RandomAccessIterator __last,
1328  random_access_iterator_tag)
1329  {
1330  // concept requirements
1331  __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
1332  _RandomAccessIterator>)
1333 
1334  if (__first == __middle)
1335  return __last;
1336  else if (__last == __middle)
1337  return __first;
1338 
1339  typedef typename iterator_traits<_RandomAccessIterator>::difference_type
1340  _Distance;
1341  typedef typename iterator_traits<_RandomAccessIterator>::value_type
1342  _ValueType;
1343 
1344  _Distance __n = __last - __first;
1345  _Distance __k = __middle - __first;
1346 
1347  if (__k == __n - __k)
1348  {
1349  std::swap_ranges(__first, __middle, __middle);
1350  return __middle;
1351  }
1352 
1353  _RandomAccessIterator __p = __first;
1354  _RandomAccessIterator __ret = __first + (__last - __middle);
1355 
1356  for (;;)
1357  {
1358  if (__k < __n - __k)
1359  {
1360  if (__is_pod(_ValueType) && __k == 1)
1361  {
1362  _ValueType __t = _GLIBCXX_MOVE(*__p);
1363  _GLIBCXX_MOVE3(__p + 1, __p + __n, __p);
1364  *(__p + __n - 1) = _GLIBCXX_MOVE(__t);
1365  return __ret;
1366  }
1367  _RandomAccessIterator __q = __p + __k;
1368  for (_Distance __i = 0; __i < __n - __k; ++ __i)
1369  {
1370  std::iter_swap(__p, __q);
1371  ++__p;
1372  ++__q;
1373  }
1374  __n %= __k;
1375  if (__n == 0)
1376  return __ret;
1377  std::swap(__n, __k);
1378  __k = __n - __k;
1379  }
1380  else
1381  {
1382  __k = __n - __k;
1383  if (__is_pod(_ValueType) && __k == 1)
1384  {
1385  _ValueType __t = _GLIBCXX_MOVE(*(__p + __n - 1));
1386  _GLIBCXX_MOVE_BACKWARD3(__p, __p + __n - 1, __p + __n);
1387  *__p = _GLIBCXX_MOVE(__t);
1388  return __ret;
1389  }
1390  _RandomAccessIterator __q = __p + __n;
1391  __p = __q - __k;
1392  for (_Distance __i = 0; __i < __n - __k; ++ __i)
1393  {
1394  --__p;
1395  --__q;
1396  std::iter_swap(__p, __q);
1397  }
1398  __n %= __k;
1399  if (__n == 0)
1400  return __ret;
1401  std::swap(__n, __k);
1402  }
1403  }
1404  }
1405 
1406  // _GLIBCXX_RESOLVE_LIB_DEFECTS
1407  // DR 488. rotate throws away useful information
1408  /**
1409  * @brief Rotate the elements of a sequence.
1410  * @ingroup mutating_algorithms
1411  * @param __first A forward iterator.
1412  * @param __middle A forward iterator.
1413  * @param __last A forward iterator.
1414  * @return first + (last - middle).
1415  *
1416  * Rotates the elements of the range @p [__first,__last) by
1417  * @p (__middle - __first) positions so that the element at @p __middle
1418  * is moved to @p __first, the element at @p __middle+1 is moved to
1419  * @p __first+1 and so on for each element in the range
1420  * @p [__first,__last).
1421  *
1422  * This effectively swaps the ranges @p [__first,__middle) and
1423  * @p [__middle,__last).
1424  *
1425  * Performs
1426  * @p *(__first+(n+(__last-__middle))%(__last-__first))=*(__first+n)
1427  * for each @p n in the range @p [0,__last-__first).
1428  */
1429  template<typename _ForwardIterator>
1430  inline _ForwardIterator
1431  rotate(_ForwardIterator __first, _ForwardIterator __middle,
1432  _ForwardIterator __last)
1433  {
1434  // concept requirements
1435  __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
1436  _ForwardIterator>)
1437  __glibcxx_requires_valid_range(__first, __middle);
1438  __glibcxx_requires_valid_range(__middle, __last);
1439 
1440  return std::__rotate(__first, __middle, __last,
1441  std::__iterator_category(__first));
1442  }
1443 
1444  } // namespace _V2
1445 
1446  /**
1447  * @brief Copy a sequence, rotating its elements.
1448  * @ingroup mutating_algorithms
1449  * @param __first A forward iterator.
1450  * @param __middle A forward iterator.
1451  * @param __last A forward iterator.
1452  * @param __result An output iterator.
1453  * @return An iterator designating the end of the resulting sequence.
1454  *
1455  * Copies the elements of the range @p [__first,__last) to the
1456  * range beginning at @result, rotating the copied elements by
1457  * @p (__middle-__first) positions so that the element at @p __middle
1458  * is moved to @p __result, the element at @p __middle+1 is moved
1459  * to @p __result+1 and so on for each element in the range @p
1460  * [__first,__last).
1461  *
1462  * Performs
1463  * @p *(__result+(n+(__last-__middle))%(__last-__first))=*(__first+n)
1464  * for each @p n in the range @p [0,__last-__first).
1465  */
1466  template<typename _ForwardIterator, typename _OutputIterator>
1467  inline _OutputIterator
1468  rotate_copy(_ForwardIterator __first, _ForwardIterator __middle,
1469  _ForwardIterator __last, _OutputIterator __result)
1470  {
1471  // concept requirements
1472  __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
1473  __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
1474  typename iterator_traits<_ForwardIterator>::value_type>)
1475  __glibcxx_requires_valid_range(__first, __middle);
1476  __glibcxx_requires_valid_range(__middle, __last);
1477 
1478  return std::copy(__first, __middle,
1479  std::copy(__middle, __last, __result));
1480  }
1481 
1482  /// This is a helper function...
1483  template<typename _ForwardIterator, typename _Predicate>
1484  _ForwardIterator
1485  __partition(_ForwardIterator __first, _ForwardIterator __last,
1486  _Predicate __pred, forward_iterator_tag)
1487  {
1488  if (__first == __last)
1489  return __first;
1490 
1491  while (__pred(*__first))
1492  if (++__first == __last)
1493  return __first;
1494 
1495  _ForwardIterator __next = __first;
1496 
1497  while (++__next != __last)
1498  if (__pred(*__next))
1499  {
1500  std::iter_swap(__first, __next);
1501  ++__first;
1502  }
1503 
1504  return __first;
1505  }
1506 
1507  /// This is a helper function...
1508  template<typename _BidirectionalIterator, typename _Predicate>
1509  _BidirectionalIterator
1510  __partition(_BidirectionalIterator __first, _BidirectionalIterator __last,
1511  _Predicate __pred, bidirectional_iterator_tag)
1512  {
1513  while (true)
1514  {
1515  while (true)
1516  if (__first == __last)
1517  return __first;
1518  else if (__pred(*__first))
1519  ++__first;
1520  else
1521  break;
1522  --__last;
1523  while (true)
1524  if (__first == __last)
1525  return __first;
1526  else if (!bool(__pred(*__last)))
1527  --__last;
1528  else
1529  break;
1530  std::iter_swap(__first, __last);
1531  ++__first;
1532  }
1533  }
1534 
1535  // partition
1536 
1537  /// This is a helper function...
1538  /// Requires __first != __last and !__pred(__first)
1539  /// and __len == distance(__first, __last).
1540  ///
1541  /// !__pred(__first) allows us to guarantee that we don't
1542  /// move-assign an element onto itself.
1543  template<typename _ForwardIterator, typename _Pointer, typename _Predicate,
1544  typename _Distance>
1545  _ForwardIterator
1546  __stable_partition_adaptive(_ForwardIterator __first,
1547  _ForwardIterator __last,
1548  _Predicate __pred, _Distance __len,
1549  _Pointer __buffer,
1550  _Distance __buffer_size)
1551  {
1552  if (__len == 1)
1553  return __first;
1554 
1555  if (__len <= __buffer_size)
1556  {
1557  _ForwardIterator __result1 = __first;
1558  _Pointer __result2 = __buffer;
1559 
1560  // The precondition guarantees that !__pred(__first), so
1561  // move that element to the buffer before starting the loop.
1562  // This ensures that we only call __pred once per element.
1563  *__result2 = _GLIBCXX_MOVE(*__first);
1564  ++__result2;
1565  ++__first;
1566  for (; __first != __last; ++__first)
1567  if (__pred(__first))
1568  {
1569  *__result1 = _GLIBCXX_MOVE(*__first);
1570  ++__result1;
1571  }
1572  else
1573  {
1574  *__result2 = _GLIBCXX_MOVE(*__first);
1575  ++__result2;
1576  }
1577 
1578  _GLIBCXX_MOVE3(__buffer, __result2, __result1);
1579  return __result1;
1580  }
1581 
1582  _ForwardIterator __middle = __first;
1583  std::advance(__middle, __len / 2);
1584  _ForwardIterator __left_split =
1585  std::__stable_partition_adaptive(__first, __middle, __pred,
1586  __len / 2, __buffer,
1587  __buffer_size);
1588 
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 
1595  if (__right_len)
1596  __right_split =
1597  std::__stable_partition_adaptive(__right_split, __last, __pred,
1598  __right_len,
1599  __buffer, __buffer_size);
1600 
1601  std::rotate(__left_split, __middle, __right_split);
1602  std::advance(__left_split, std::distance(__middle, __right_split));
1603  return __left_split;
1604  }
1605 
1606  template<typename _ForwardIterator, typename _Predicate>
1607  _ForwardIterator
1608  __stable_partition(_ForwardIterator __first, _ForwardIterator __last,
1609  _Predicate __pred)
1610  {
1611  __first = std::__find_if_not(__first, __last, __pred);
1612 
1613  if (__first == __last)
1614  return __first;
1615 
1616  typedef typename iterator_traits<_ForwardIterator>::value_type
1617  _ValueType;
1618  typedef typename iterator_traits<_ForwardIterator>::difference_type
1619  _DistanceType;
1620 
1621  _Temporary_buffer<_ForwardIterator, _ValueType> __buf(__first, __last);
1622  return
1623  std::__stable_partition_adaptive(__first, __last, __pred,
1624  _DistanceType(__buf.requested_size()),
1625  __buf.begin(),
1626  _DistanceType(__buf.size()));
1627  }
1628 
1629  /**
1630  * @brief Move elements for which a predicate is true to the beginning
1631  * of a sequence, preserving relative ordering.
1632  * @ingroup mutating_algorithms
1633  * @param __first A forward iterator.
1634  * @param __last A forward iterator.
1635  * @param __pred A predicate functor.
1636  * @return An iterator @p middle such that @p __pred(i) is true for each
1637  * iterator @p i in the range @p [first,middle) and false for each @p i
1638  * in the range @p [middle,last).
1639  *
1640  * Performs the same function as @p partition() with the additional
1641  * guarantee that the relative ordering of elements in each group is
1642  * preserved, so any two elements @p x and @p y in the range
1643  * @p [__first,__last) such that @p __pred(x)==__pred(y) will have the same
1644  * relative ordering after calling @p stable_partition().
1645  */
1646  template<typename _ForwardIterator, typename _Predicate>
1647  inline _ForwardIterator
1648  stable_partition(_ForwardIterator __first, _ForwardIterator __last,
1649  _Predicate __pred)
1650  {
1651  // concept requirements
1652  __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
1653  _ForwardIterator>)
1654  __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
1655  typename iterator_traits<_ForwardIterator>::value_type>)
1656  __glibcxx_requires_valid_range(__first, __last);
1657 
1658  return std::__stable_partition(__first, __last,
1659  __gnu_cxx::__ops::__pred_iter(__pred));
1660  }
1661 
1662  /// This is a helper function for the sort routines.
1663  template<typename _RandomAccessIterator, typename _Compare>
1664  void
1665  __heap_select(_RandomAccessIterator __first,
1666  _RandomAccessIterator __middle,
1667  _RandomAccessIterator __last, _Compare __comp)
1668  {
1669  std::__make_heap(__first, __middle, __comp);
1670  for (_RandomAccessIterator __i = __middle; __i < __last; ++__i)
1671  if (__comp(__i, __first))
1672  std::__pop_heap(__first, __middle, __i, __comp);
1673  }
1674 
1675  // partial_sort
1676 
1677  template<typename _InputIterator, typename _RandomAccessIterator,
1678  typename _Compare>
1679  _RandomAccessIterator
1680  __partial_sort_copy(_InputIterator __first, _InputIterator __last,
1681  _RandomAccessIterator __result_first,
1682  _RandomAccessIterator __result_last,
1683  _Compare __comp)
1684  {
1685  typedef typename iterator_traits<_InputIterator>::value_type
1686  _InputValueType;
1687  typedef iterator_traits<_RandomAccessIterator> _RItTraits;
1688  typedef typename _RItTraits::difference_type _DistanceType;
1689 
1690  if (__result_first == __result_last)
1691  return __result_last;
1692  _RandomAccessIterator __result_real_last = __result_first;
1693  while (__first != __last && __result_real_last != __result_last)
1694  {
1695  *__result_real_last = *__first;
1696  ++__result_real_last;
1697  ++__first;
1698  }
1699 
1700  std::__make_heap(__result_first, __result_real_last, __comp);
1701  while (__first != __last)
1702  {
1703  if (__comp(__first, __result_first))
1704  std::__adjust_heap(__result_first, _DistanceType(0),
1705  _DistanceType(__result_real_last
1706  - __result_first),
1707  _InputValueType(*__first), __comp);
1708  ++__first;
1709  }
1710  std::__sort_heap(__result_first, __result_real_last, __comp);
1711  return __result_real_last;
1712  }
1713 
1714  /**
1715  * @brief Copy the smallest elements of a sequence.
1716  * @ingroup sorting_algorithms
1717  * @param __first An iterator.
1718  * @param __last Another iterator.
1719  * @param __result_first A random-access iterator.
1720  * @param __result_last Another random-access iterator.
1721  * @return An iterator indicating the end of the resulting sequence.
1722  *
1723  * Copies and sorts the smallest N values from the range @p [__first,__last)
1724  * to the range beginning at @p __result_first, where the number of
1725  * elements to be copied, @p N, is the smaller of @p (__last-__first) and
1726  * @p (__result_last-__result_first).
1727  * After the sort if @e i and @e j are iterators in the range
1728  * @p [__result_first,__result_first+N) such that i precedes j then
1729  * *j<*i is false.
1730  * The value returned is @p __result_first+N.
1731  */
1732  template<typename _InputIterator, typename _RandomAccessIterator>
1733  inline _RandomAccessIterator
1734  partial_sort_copy(_InputIterator __first, _InputIterator __last,
1735  _RandomAccessIterator __result_first,
1736  _RandomAccessIterator __result_last)
1737  {
1738  typedef typename iterator_traits<_InputIterator>::value_type
1739  _InputValueType;
1740  typedef typename iterator_traits<_RandomAccessIterator>::value_type
1741  _OutputValueType;
1742  typedef typename iterator_traits<_RandomAccessIterator>::difference_type
1743  _DistanceType;
1744 
1745  // concept requirements
1746  __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
1747  __glibcxx_function_requires(_ConvertibleConcept<_InputValueType,
1748  _OutputValueType>)
1749  __glibcxx_function_requires(_LessThanOpConcept<_InputValueType,
1750  _OutputValueType>)
1751  __glibcxx_function_requires(_LessThanComparableConcept<_OutputValueType>)
1752  __glibcxx_requires_valid_range(__first, __last);
1753  __glibcxx_requires_valid_range(__result_first, __result_last);
1754 
1755  return std::__partial_sort_copy(__first, __last,
1756  __result_first, __result_last,
1757  __gnu_cxx::__ops::__iter_less_iter());
1758  }
1759 
1760  /**
1761  * @brief Copy the smallest elements of a sequence using a predicate for
1762  * comparison.
1763  * @ingroup sorting_algorithms
1764  * @param __first An input iterator.
1765  * @param __last Another input iterator.
1766  * @param __result_first A random-access iterator.
1767  * @param __result_last Another random-access iterator.
1768  * @param __comp A comparison functor.
1769  * @return An iterator indicating the end of the resulting sequence.
1770  *
1771  * Copies and sorts the smallest N values from the range @p [__first,__last)
1772  * to the range beginning at @p result_first, where the number of
1773  * elements to be copied, @p N, is the smaller of @p (__last-__first) and
1774  * @p (__result_last-__result_first).
1775  * After the sort if @e i and @e j are iterators in the range
1776  * @p [__result_first,__result_first+N) such that i precedes j then
1777  * @p __comp(*j,*i) is false.
1778  * The value returned is @p __result_first+N.
1779  */
1780  template<typename _InputIterator, typename _RandomAccessIterator,
1781  typename _Compare>
1782  inline _RandomAccessIterator
1783  partial_sort_copy(_InputIterator __first, _InputIterator __last,
1784  _RandomAccessIterator __result_first,
1785  _RandomAccessIterator __result_last,
1786  _Compare __comp)
1787  {
1788  typedef typename iterator_traits<_InputIterator>::value_type
1789  _InputValueType;
1790  typedef typename iterator_traits<_RandomAccessIterator>::value_type
1791  _OutputValueType;
1792  typedef typename iterator_traits<_RandomAccessIterator>::difference_type
1793  _DistanceType;
1794 
1795  // concept requirements
1796  __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
1797  __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
1798  _RandomAccessIterator>)
1799  __glibcxx_function_requires(_ConvertibleConcept<_InputValueType,
1800  _OutputValueType>)
1801  __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
1802  _InputValueType, _OutputValueType>)
1803  __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
1804  _OutputValueType, _OutputValueType>)
1805  __glibcxx_requires_valid_range(__first, __last);
1806  __glibcxx_requires_valid_range(__result_first, __result_last);
1807 
1808  return std::__partial_sort_copy(__first, __last,
1809  __result_first, __result_last,
1810  __gnu_cxx::__ops::__iter_comp_iter(__comp));
1811  }
1812 
1813  /// This is a helper function for the sort routine.
1814  template<typename _RandomAccessIterator, typename _Compare>
1815  void
1816  __unguarded_linear_insert(_RandomAccessIterator __last,
1817  _Compare __comp)
1818  {
1819  typename iterator_traits<_RandomAccessIterator>::value_type
1820  __val = _GLIBCXX_MOVE(*__last);
1821  _RandomAccessIterator __next = __last;
1822  --__next;
1823  while (__comp(__val, __next))
1824  {
1825  *__last = _GLIBCXX_MOVE(*__next);
1826  __last = __next;
1827  --__next;
1828  }
1829  *__last = _GLIBCXX_MOVE(__val);
1830  }
1831 
1832  /// This is a helper function for the sort routine.
1833  template<typename _RandomAccessIterator, typename _Compare>
1834  void
1835  __insertion_sort(_RandomAccessIterator __first,
1836  _RandomAccessIterator __last, _Compare __comp)
1837  {
1838  if (__first == __last) return;
1839 
1840  for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i)
1841  {
1842  if (__comp(__i, __first))
1843  {
1844  typename iterator_traits<_RandomAccessIterator>::value_type
1845  __val = _GLIBCXX_MOVE(*__i);
1846  _GLIBCXX_MOVE_BACKWARD3(__first, __i, __i + 1);
1847  *__first = _GLIBCXX_MOVE(__val);
1848  }
1849  else
1851  __gnu_cxx::__ops::__val_comp_iter(__comp));
1852  }
1853  }
1854 
1855  /// This is a helper function for the sort routine.
1856  template<typename _RandomAccessIterator, typename _Compare>
1857  inline void
1858  __unguarded_insertion_sort(_RandomAccessIterator __first,
1859  _RandomAccessIterator __last, _Compare __comp)
1860  {
1861  for (_RandomAccessIterator __i = __first; __i != __last; ++__i)
1863  __gnu_cxx::__ops::__val_comp_iter(__comp));
1864  }
1865 
1866  /**
1867  * @doctodo
1868  * This controls some aspect of the sort routines.
1869  */
1870  enum { _S_threshold = 16 };
1871 
1872  /// This is a helper function for the sort routine.
1873  template<typename _RandomAccessIterator, typename _Compare>
1874  void
1875  __final_insertion_sort(_RandomAccessIterator __first,
1876  _RandomAccessIterator __last, _Compare __comp)
1877  {
1878  if (__last - __first > int(_S_threshold))
1879  {
1880  std::__insertion_sort(__first, __first + int(_S_threshold), __comp);
1881  std::__unguarded_insertion_sort(__first + int(_S_threshold), __last,
1882  __comp);
1883  }
1884  else
1885  std::__insertion_sort(__first, __last, __comp);
1886  }
1887 
1888  /// This is a helper function...
1889  template<typename _RandomAccessIterator, typename _Compare>
1890  _RandomAccessIterator
1891  __unguarded_partition(_RandomAccessIterator __first,
1892  _RandomAccessIterator __last,
1893  _RandomAccessIterator __pivot, _Compare __comp)
1894  {
1895  while (true)
1896  {
1897  while (__comp(__first, __pivot))
1898  ++__first;
1899  --__last;
1900  while (__comp(__pivot, __last))
1901  --__last;
1902  if (!(__first < __last))
1903  return __first;
1904  std::iter_swap(__first, __last);
1905  ++__first;
1906  }
1907  }
1908 
1909  /// This is a helper function...
1910  template<typename _RandomAccessIterator, typename _Compare>
1911  inline _RandomAccessIterator
1912  __unguarded_partition_pivot(_RandomAccessIterator __first,
1913  _RandomAccessIterator __last, _Compare __comp)
1914  {
1915  _RandomAccessIterator __mid = __first + (__last - __first) / 2;
1916  std::__move_median_to_first(__first, __first + 1, __mid, __last - 1,
1917  __comp);
1918  return std::__unguarded_partition(__first + 1, __last, __first, __comp);
1919  }
1920 
1921  template<typename _RandomAccessIterator, typename _Compare>
1922  inline void
1923  __partial_sort(_RandomAccessIterator __first,
1924  _RandomAccessIterator __middle,
1925  _RandomAccessIterator __last,
1926  _Compare __comp)
1927  {
1928  std::__heap_select(__first, __middle, __last, __comp);
1929  std::__sort_heap(__first, __middle, __comp);
1930  }
1931 
1932  /// This is a helper function for the sort routine.
1933  template<typename _RandomAccessIterator, typename _Size, typename _Compare>
1934  void
1935  __introsort_loop(_RandomAccessIterator __first,
1936  _RandomAccessIterator __last,
1937  _Size __depth_limit, _Compare __comp)
1938  {
1939  while (__last - __first > int(_S_threshold))
1940  {
1941  if (__depth_limit == 0)
1942  {
1943  std::__partial_sort(__first, __last, __last, __comp);
1944  return;
1945  }
1946  --__depth_limit;
1947  _RandomAccessIterator __cut =
1948  std::__unguarded_partition_pivot(__first, __last, __comp);
1949  std::__introsort_loop(__cut, __last, __depth_limit, __comp);
1950  __last = __cut;
1951  }
1952  }
1953 
1954  // sort
1955 
1956  template<typename _RandomAccessIterator, typename _Compare>
1957  inline void
1958  __sort(_RandomAccessIterator __first, _RandomAccessIterator __last,
1959  _Compare __comp)
1960  {
1961  if (__first != __last)
1962  {
1963  std::__introsort_loop(__first, __last,
1964  std::__lg(__last - __first) * 2,
1965  __comp);
1966  std::__final_insertion_sort(__first, __last, __comp);
1967  }
1968  }
1969 
1970  template<typename _RandomAccessIterator, typename _Size, typename _Compare>
1971  void
1972  __introselect(_RandomAccessIterator __first, _RandomAccessIterator __nth,
1973  _RandomAccessIterator __last, _Size __depth_limit,
1974  _Compare __comp)
1975  {
1976  while (__last - __first > 3)
1977  {
1978  if (__depth_limit == 0)
1979  {
1980  std::__heap_select(__first, __nth + 1, __last, __comp);
1981  // Place the nth largest element in its final position.
1982  std::iter_swap(__first, __nth);
1983  return;
1984  }
1985  --__depth_limit;
1986  _RandomAccessIterator __cut =
1987  std::__unguarded_partition_pivot(__first, __last, __comp);
1988  if (__cut <= __nth)
1989  __first = __cut;
1990  else
1991  __last = __cut;
1992  }
1993  std::__insertion_sort(__first, __last, __comp);
1994  }
1995 
1996  // nth_element
1997 
1998  // lower_bound moved to stl_algobase.h
1999 
2000  /**
2001  * @brief Finds the first position in which @p __val could be inserted
2002  * without changing the ordering.
2003  * @ingroup binary_search_algorithms
2004  * @param __first An iterator.
2005  * @param __last Another iterator.
2006  * @param __val The search term.
2007  * @param __comp A functor to use for comparisons.
2008  * @return An iterator pointing to the first element <em>not less
2009  * than</em> @p __val, or end() if every element is less
2010  * than @p __val.
2011  * @ingroup binary_search_algorithms
2012  *
2013  * The comparison function should have the same effects on ordering as
2014  * the function used for the initial sort.
2015  */
2016  template<typename _ForwardIterator, typename _Tp, typename _Compare>
2017  inline _ForwardIterator
2018  lower_bound(_ForwardIterator __first, _ForwardIterator __last,
2019  const _Tp& __val, _Compare __comp)
2020  {
2021  typedef typename iterator_traits<_ForwardIterator>::value_type
2022  _ValueType;
2023 
2024  // concept requirements
2025  __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
2026  __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2027  _ValueType, _Tp>)
2028  __glibcxx_requires_partitioned_lower_pred(__first, __last,
2029  __val, __comp);
2030 
2031  return std::__lower_bound(__first, __last, __val,
2032  __gnu_cxx::__ops::__iter_comp_val(__comp));
2033  }
2034 
2035  template<typename _ForwardIterator, typename _Tp, typename _Compare>
2036  _ForwardIterator
2037  __upper_bound(_ForwardIterator __first, _ForwardIterator __last,
2038  const _Tp& __val, _Compare __comp)
2039  {
2040  typedef typename iterator_traits<_ForwardIterator>::difference_type
2041  _DistanceType;
2042 
2043  _DistanceType __len = std::distance(__first, __last);
2044 
2045  while (__len > 0)
2046  {
2047  _DistanceType __half = __len >> 1;
2048  _ForwardIterator __middle = __first;
2049  std::advance(__middle, __half);
2050  if (__comp(__val, __middle))
2051  __len = __half;
2052  else
2053  {
2054  __first = __middle;
2055  ++__first;
2056  __len = __len - __half - 1;
2057  }
2058  }
2059  return __first;
2060  }
2061 
2062  /**
2063  * @brief Finds the last position in which @p __val could be inserted
2064  * without changing the ordering.
2065  * @ingroup binary_search_algorithms
2066  * @param __first An iterator.
2067  * @param __last Another iterator.
2068  * @param __val The search term.
2069  * @return An iterator pointing to the first element greater than @p __val,
2070  * or end() if no elements are greater than @p __val.
2071  * @ingroup binary_search_algorithms
2072  */
2073  template<typename _ForwardIterator, typename _Tp>
2074  inline _ForwardIterator
2075  upper_bound(_ForwardIterator __first, _ForwardIterator __last,
2076  const _Tp& __val)
2077  {
2078  typedef typename iterator_traits<_ForwardIterator>::value_type
2079  _ValueType;
2080 
2081  // concept requirements
2082  __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
2083  __glibcxx_function_requires(_LessThanOpConcept<_Tp, _ValueType>)
2084  __glibcxx_requires_partitioned_upper(__first, __last, __val);
2085 
2086  return std::__upper_bound(__first, __last, __val,
2087  __gnu_cxx::__ops::__val_less_iter());
2088  }
2089 
2090  /**
2091  * @brief Finds the last position in which @p __val could be inserted
2092  * without changing the ordering.
2093  * @ingroup binary_search_algorithms
2094  * @param __first An iterator.
2095  * @param __last Another iterator.
2096  * @param __val The search term.
2097  * @param __comp A functor to use for comparisons.
2098  * @return An iterator pointing to the first element greater than @p __val,
2099  * or end() if no elements are greater than @p __val.
2100  * @ingroup binary_search_algorithms
2101  *
2102  * The comparison function should have the same effects on ordering as
2103  * the function used for the initial sort.
2104  */
2105  template<typename _ForwardIterator, typename _Tp, typename _Compare>
2106  inline _ForwardIterator
2107  upper_bound(_ForwardIterator __first, _ForwardIterator __last,
2108  const _Tp& __val, _Compare __comp)
2109  {
2110  typedef typename iterator_traits<_ForwardIterator>::value_type
2111  _ValueType;
2112 
2113  // concept requirements
2114  __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
2115  __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2116  _Tp, _ValueType>)
2117  __glibcxx_requires_partitioned_upper_pred(__first, __last,
2118  __val, __comp);
2119 
2120  return std::__upper_bound(__first, __last, __val,
2121  __gnu_cxx::__ops::__val_comp_iter(__comp));
2122  }
2123 
2124  template<typename _ForwardIterator, typename _Tp,
2125  typename _CompareItTp, typename _CompareTpIt>
2126  pair<_ForwardIterator, _ForwardIterator>
2127  __equal_range(_ForwardIterator __first, _ForwardIterator __last,
2128  const _Tp& __val,
2129  _CompareItTp __comp_it_val, _CompareTpIt __comp_val_it)
2130  {
2131  typedef typename iterator_traits<_ForwardIterator>::difference_type
2132  _DistanceType;
2133 
2134  _DistanceType __len = std::distance(__first, __last);
2135 
2136  while (__len > 0)
2137  {
2138  _DistanceType __half = __len >> 1;
2139  _ForwardIterator __middle = __first;
2140  std::advance(__middle, __half);
2141  if (__comp_it_val(__middle, __val))
2142  {
2143  __first = __middle;
2144  ++__first;
2145  __len = __len - __half - 1;
2146  }
2147  else if (__comp_val_it(__val, __middle))
2148  __len = __half;
2149  else
2150  {
2151  _ForwardIterator __left
2152  = std::__lower_bound(__first, __middle, __val, __comp_it_val);
2153  std::advance(__first, __len);
2154  _ForwardIterator __right
2155  = std::__upper_bound(++__middle, __first, __val, __comp_val_it);
2156  return pair<_ForwardIterator, _ForwardIterator>(__left, __right);
2157  }
2158  }
2159  return pair<_ForwardIterator, _ForwardIterator>(__first, __first);
2160  }
2161 
2162  /**
2163  * @brief Finds the largest subrange in which @p __val could be inserted
2164  * at any place in it without changing the ordering.
2165  * @ingroup binary_search_algorithms
2166  * @param __first An iterator.
2167  * @param __last Another iterator.
2168  * @param __val The search term.
2169  * @return An pair of iterators defining the subrange.
2170  * @ingroup binary_search_algorithms
2171  *
2172  * This is equivalent to
2173  * @code
2174  * std::make_pair(lower_bound(__first, __last, __val),
2175  * upper_bound(__first, __last, __val))
2176  * @endcode
2177  * but does not actually call those functions.
2178  */
2179  template<typename _ForwardIterator, typename _Tp>
2180  inline pair<_ForwardIterator, _ForwardIterator>
2181  equal_range(_ForwardIterator __first, _ForwardIterator __last,
2182  const _Tp& __val)
2183  {
2184  typedef typename iterator_traits<_ForwardIterator>::value_type
2185  _ValueType;
2186 
2187  // concept requirements
2188  __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
2189  __glibcxx_function_requires(_LessThanOpConcept<_ValueType, _Tp>)
2190  __glibcxx_function_requires(_LessThanOpConcept<_Tp, _ValueType>)
2191  __glibcxx_requires_partitioned_lower(__first, __last, __val);
2192  __glibcxx_requires_partitioned_upper(__first, __last, __val);
2193 
2194  return std::__equal_range(__first, __last, __val,
2195  __gnu_cxx::__ops::__iter_less_val(),
2196  __gnu_cxx::__ops::__val_less_iter());
2197  }
2198 
2199  /**
2200  * @brief Finds the largest subrange in which @p __val could be inserted
2201  * at any place in it without changing the ordering.
2202  * @param __first An iterator.
2203  * @param __last Another iterator.
2204  * @param __val The search term.
2205  * @param __comp A functor to use for comparisons.
2206  * @return An pair of iterators defining the subrange.
2207  * @ingroup binary_search_algorithms
2208  *
2209  * This is equivalent to
2210  * @code
2211  * std::make_pair(lower_bound(__first, __last, __val, __comp),
2212  * upper_bound(__first, __last, __val, __comp))
2213  * @endcode
2214  * but does not actually call those functions.
2215  */
2216  template<typename _ForwardIterator, typename _Tp, typename _Compare>
2217  inline pair<_ForwardIterator, _ForwardIterator>
2218  equal_range(_ForwardIterator __first, _ForwardIterator __last,
2219  const _Tp& __val, _Compare __comp)
2220  {
2221  typedef typename iterator_traits<_ForwardIterator>::value_type
2222  _ValueType;
2223 
2224  // concept requirements
2225  __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
2226  __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2227  _ValueType, _Tp>)
2228  __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2229  _Tp, _ValueType>)
2230  __glibcxx_requires_partitioned_lower_pred(__first, __last,
2231  __val, __comp);
2232  __glibcxx_requires_partitioned_upper_pred(__first, __last,
2233  __val, __comp);
2234 
2235  return std::__equal_range(__first, __last, __val,
2236  __gnu_cxx::__ops::__iter_comp_val(__comp),
2237  __gnu_cxx::__ops::__val_comp_iter(__comp));
2238  }
2239 
2240  /**
2241  * @brief Determines whether an element exists in a range.
2242  * @ingroup binary_search_algorithms
2243  * @param __first An iterator.
2244  * @param __last Another iterator.
2245  * @param __val The search term.
2246  * @return True if @p __val (or its equivalent) is in [@p
2247  * __first,@p __last ].
2248  *
2249  * Note that this does not actually return an iterator to @p __val. For
2250  * that, use std::find or a container's specialized find member functions.
2251  */
2252  template<typename _ForwardIterator, typename _Tp>
2253  bool
2254  binary_search(_ForwardIterator __first, _ForwardIterator __last,
2255  const _Tp& __val)
2256  {
2257  typedef typename iterator_traits<_ForwardIterator>::value_type
2258  _ValueType;
2259 
2260  // concept requirements
2261  __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
2262  __glibcxx_function_requires(_LessThanOpConcept<_Tp, _ValueType>)
2263  __glibcxx_requires_partitioned_lower(__first, __last, __val);
2264  __glibcxx_requires_partitioned_upper(__first, __last, __val);
2265 
2266  _ForwardIterator __i
2267  = std::__lower_bound(__first, __last, __val,
2268  __gnu_cxx::__ops::__iter_less_val());
2269  return __i != __last && !(__val < *__i);
2270  }
2271 
2272  /**
2273  * @brief Determines whether an element exists in a range.
2274  * @ingroup binary_search_algorithms
2275  * @param __first An iterator.
2276  * @param __last Another iterator.
2277  * @param __val The search term.
2278  * @param __comp A functor to use for comparisons.
2279  * @return True if @p __val (or its equivalent) is in @p [__first,__last].
2280  *
2281  * Note that this does not actually return an iterator to @p __val. For
2282  * that, use std::find or a container's specialized find member functions.
2283  *
2284  * The comparison function should have the same effects on ordering as
2285  * the function used for the initial sort.
2286  */
2287  template<typename _ForwardIterator, typename _Tp, typename _Compare>
2288  bool
2289  binary_search(_ForwardIterator __first, _ForwardIterator __last,
2290  const _Tp& __val, _Compare __comp)
2291  {
2292  typedef typename iterator_traits<_ForwardIterator>::value_type
2293  _ValueType;
2294 
2295  // concept requirements
2296  __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
2297  __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2298  _Tp, _ValueType>)
2299  __glibcxx_requires_partitioned_lower_pred(__first, __last,
2300  __val, __comp);
2301  __glibcxx_requires_partitioned_upper_pred(__first, __last,
2302  __val, __comp);
2303 
2304  _ForwardIterator __i
2305  = std::__lower_bound(__first, __last, __val,
2306  __gnu_cxx::__ops::__iter_comp_val(__comp));
2307  return __i != __last && !bool(__comp(__val, *__i));
2308  }
2309 
2310  // merge
2311 
2312  /// This is a helper function for the __merge_adaptive routines.
2313  template<typename _InputIterator1, typename _InputIterator2,
2314  typename _OutputIterator, typename _Compare>
2315  void
2316  __move_merge_adaptive(_InputIterator1 __first1, _InputIterator1 __last1,
2317  _InputIterator2 __first2, _InputIterator2 __last2,
2318  _OutputIterator __result, _Compare __comp)
2319  {
2320  while (__first1 != __last1 && __first2 != __last2)
2321  {
2322  if (__comp(__first2, __first1))
2323  {
2324  *__result = _GLIBCXX_MOVE(*__first2);
2325  ++__first2;
2326  }
2327  else
2328  {
2329  *__result = _GLIBCXX_MOVE(*__first1);
2330  ++__first1;
2331  }
2332  ++__result;
2333  }
2334  if (__first1 != __last1)
2335  _GLIBCXX_MOVE3(__first1, __last1, __result);
2336  }
2337 
2338  /// This is a helper function for the __merge_adaptive routines.
2339  template<typename _BidirectionalIterator1, typename _BidirectionalIterator2,
2340  typename _BidirectionalIterator3, typename _Compare>
2341  void
2342  __move_merge_adaptive_backward(_BidirectionalIterator1 __first1,
2343  _BidirectionalIterator1 __last1,
2344  _BidirectionalIterator2 __first2,
2345  _BidirectionalIterator2 __last2,
2346  _BidirectionalIterator3 __result,
2347  _Compare __comp)
2348  {
2349  if (__first1 == __last1)
2350  {
2351  _GLIBCXX_MOVE_BACKWARD3(__first2, __last2, __result);
2352  return;
2353  }
2354  else if (__first2 == __last2)
2355  return;
2356 
2357  --__last1;
2358  --__last2;
2359  while (true)
2360  {
2361  if (__comp(__last2, __last1))
2362  {
2363  *--__result = _GLIBCXX_MOVE(*__last1);
2364  if (__first1 == __last1)
2365  {
2366  _GLIBCXX_MOVE_BACKWARD3(__first2, ++__last2, __result);
2367  return;
2368  }
2369  --__last1;
2370  }
2371  else
2372  {
2373  *--__result = _GLIBCXX_MOVE(*__last2);
2374  if (__first2 == __last2)
2375  return;
2376  --__last2;
2377  }
2378  }
2379  }
2380 
2381  /// This is a helper function for the merge routines.
2382  template<typename _BidirectionalIterator1, typename _BidirectionalIterator2,
2383  typename _Distance>
2384  _BidirectionalIterator1
2385  __rotate_adaptive(_BidirectionalIterator1 __first,
2386  _BidirectionalIterator1 __middle,
2387  _BidirectionalIterator1 __last,
2388  _Distance __len1, _Distance __len2,
2389  _BidirectionalIterator2 __buffer,
2390  _Distance __buffer_size)
2391  {
2392  _BidirectionalIterator2 __buffer_end;
2393  if (__len1 > __len2 && __len2 <= __buffer_size)
2394  {
2395  if (__len2)
2396  {
2397  __buffer_end = _GLIBCXX_MOVE3(__middle, __last, __buffer);
2398  _GLIBCXX_MOVE_BACKWARD3(__first, __middle, __last);
2399  return _GLIBCXX_MOVE3(__buffer, __buffer_end, __first);
2400  }
2401  else
2402  return __first;
2403  }
2404  else if (__len1 <= __buffer_size)
2405  {
2406  if (__len1)
2407  {
2408  __buffer_end = _GLIBCXX_MOVE3(__first, __middle, __buffer);
2409  _GLIBCXX_MOVE3(__middle, __last, __first);
2410  return _GLIBCXX_MOVE_BACKWARD3(__buffer, __buffer_end, __last);
2411  }
2412  else
2413  return __last;
2414  }
2415  else
2416  {
2417  std::rotate(__first, __middle, __last);
2418  std::advance(__first, std::distance(__middle, __last));
2419  return __first;
2420  }
2421  }
2422 
2423  /// This is a helper function for the merge routines.
2424  template<typename _BidirectionalIterator, typename _Distance,
2425  typename _Pointer, typename _Compare>
2426  void
2427  __merge_adaptive(_BidirectionalIterator __first,
2428  _BidirectionalIterator __middle,
2429  _BidirectionalIterator __last,
2430  _Distance __len1, _Distance __len2,
2431  _Pointer __buffer, _Distance __buffer_size,
2432  _Compare __comp)
2433  {
2434  if (__len1 <= __len2 && __len1 <= __buffer_size)
2435  {
2436  _Pointer __buffer_end = _GLIBCXX_MOVE3(__first, __middle, __buffer);
2437  std::__move_merge_adaptive(__buffer, __buffer_end, __middle, __last,
2438  __first, __comp);
2439  }
2440  else if (__len2 <= __buffer_size)
2441  {
2442  _Pointer __buffer_end = _GLIBCXX_MOVE3(__middle, __last, __buffer);
2443  std::__move_merge_adaptive_backward(__first, __middle, __buffer,
2444  __buffer_end, __last, __comp);
2445  }
2446  else
2447  {
2448  _BidirectionalIterator __first_cut = __first;
2449  _BidirectionalIterator __second_cut = __middle;
2450  _Distance __len11 = 0;
2451  _Distance __len22 = 0;
2452  if (__len1 > __len2)
2453  {
2454  __len11 = __len1 / 2;
2455  std::advance(__first_cut, __len11);
2456  __second_cut
2457  = std::__lower_bound(__middle, __last, *__first_cut,
2458  __gnu_cxx::__ops::__iter_comp_val(__comp));
2459  __len22 = std::distance(__middle, __second_cut);
2460  }
2461  else
2462  {
2463  __len22 = __len2 / 2;
2464  std::advance(__second_cut, __len22);
2465  __first_cut
2466  = std::__upper_bound(__first, __middle, *__second_cut,
2467  __gnu_cxx::__ops::__val_comp_iter(__comp));
2468  __len11 = std::distance(__first, __first_cut);
2469  }
2470 
2471  _BidirectionalIterator __new_middle
2472  = std::__rotate_adaptive(__first_cut, __middle, __second_cut,
2473  __len1 - __len11, __len22, __buffer,
2474  __buffer_size);
2475  std::__merge_adaptive(__first, __first_cut, __new_middle, __len11,
2476  __len22, __buffer, __buffer_size, __comp);
2477  std::__merge_adaptive(__new_middle, __second_cut, __last,
2478  __len1 - __len11,
2479  __len2 - __len22, __buffer,
2480  __buffer_size, __comp);
2481  }
2482  }
2483 
2484  /// This is a helper function for the merge routines.
2485  template<typename _BidirectionalIterator, typename _Distance,
2486  typename _Compare>
2487  void
2488  __merge_without_buffer(_BidirectionalIterator __first,
2489  _BidirectionalIterator __middle,
2490  _BidirectionalIterator __last,
2491  _Distance __len1, _Distance __len2,
2492  _Compare __comp)
2493  {
2494  if (__len1 == 0 || __len2 == 0)
2495  return;
2496 
2497  if (__len1 + __len2 == 2)
2498  {
2499  if (__comp(__middle, __first))
2500  std::iter_swap(__first, __middle);
2501  return;
2502  }
2503 
2504  _BidirectionalIterator __first_cut = __first;
2505  _BidirectionalIterator __second_cut = __middle;
2506  _Distance __len11 = 0;
2507  _Distance __len22 = 0;
2508  if (__len1 > __len2)
2509  {
2510  __len11 = __len1 / 2;
2511  std::advance(__first_cut, __len11);
2512  __second_cut
2513  = std::__lower_bound(__middle, __last, *__first_cut,
2514  __gnu_cxx::__ops::__iter_comp_val(__comp));
2515  __len22 = std::distance(__middle, __second_cut);
2516  }
2517  else
2518  {
2519  __len22 = __len2 / 2;
2520  std::advance(__second_cut, __len22);
2521  __first_cut
2522  = std::__upper_bound(__first, __middle, *__second_cut,
2523  __gnu_cxx::__ops::__val_comp_iter(__comp));
2524  __len11 = std::distance(__first, __first_cut);
2525  }
2526 
2527  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 
2554  typedef _Temporary_buffer<_BidirectionalIterator, _ValueType> _TmpBuf;
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>
3297  _GLIBCXX14_CONSTEXPR
3298  inline pair<const _Tp&, const _Tp&>
3299  minmax(const _Tp& __a, const _Tp& __b)
3300  {
3301  // concept requirements
3302  __glibcxx_function_requires(_LessThanComparableConcept<_Tp>)
3303 
3304  return __b < __a ? pair<const _Tp&, const _Tp&>(__b, __a)
3305  : pair<const _Tp&, const _Tp&>(__a, __b);
3306  }
3307 
3308  /**
3309  * @brief Determines min and max at once as an ordered pair.
3310  * @ingroup sorting_algorithms
3311  * @param __a A thing of arbitrary type.
3312  * @param __b Another thing of arbitrary type.
3313  * @param __comp A @link comparison_functors comparison functor @endlink.
3314  * @return A pair(__b, __a) if __b is smaller than __a, pair(__a,
3315  * __b) otherwise.
3316  */
3317  template<typename _Tp, typename _Compare>
3318  _GLIBCXX14_CONSTEXPR
3319  inline pair<const _Tp&, const _Tp&>
3320  minmax(const _Tp& __a, const _Tp& __b, _Compare __comp)
3321  {
3322  return __comp(__b, __a) ? pair<const _Tp&, const _Tp&>(__b, __a)
3323  : pair<const _Tp&, const _Tp&>(__a, __b);
3324  }
3325 
3326  template<typename _ForwardIterator, typename _Compare>
3327  _GLIBCXX14_CONSTEXPR
3328  pair<_ForwardIterator, _ForwardIterator>
3329  __minmax_element(_ForwardIterator __first, _ForwardIterator __last,
3330  _Compare __comp)
3331  {
3332  _ForwardIterator __next = __first;
3333  if (__first == __last
3334  || ++__next == __last)
3335  return std::make_pair(__first, __first);
3336 
3337  _ForwardIterator __min{}, __max{};
3338  if (__comp(__next, __first))
3339  {
3340  __min = __next;
3341  __max = __first;
3342  }
3343  else
3344  {
3345  __min = __first;
3346  __max = __next;
3347  }
3348 
3349  __first = __next;
3350  ++__first;
3351 
3352  while (__first != __last)
3353  {
3354  __next = __first;
3355  if (++__next == __last)
3356  {
3357  if (__comp(__first, __min))
3358  __min = __first;
3359  else if (!__comp(__first, __max))
3360  __max = __first;
3361  break;
3362  }
3363 
3364  if (__comp(__next, __first))
3365  {
3366  if (__comp(__next, __min))
3367  __min = __next;
3368  if (!__comp(__first, __max))
3369  __max = __first;
3370  }
3371  else
3372  {
3373  if (__comp(__first, __min))
3374  __min = __first;
3375  if (!__comp(__next, __max))
3376  __max = __next;
3377  }
3378 
3379  __first = __next;
3380  ++__first;
3381  }
3382 
3383  return std::make_pair(__min, __max);
3384  }
3385 
3386  /**
3387  * @brief Return a pair of iterators pointing to the minimum and maximum
3388  * elements in a range.
3389  * @ingroup sorting_algorithms
3390  * @param __first Start of range.
3391  * @param __last End of range.
3392  * @return make_pair(m, M), where m is the first iterator i in
3393  * [__first, __last) such that no other element in the range is
3394  * smaller, and where M is the last iterator i in [__first, __last)
3395  * such that no other element in the range is larger.
3396  */
3397  template<typename _ForwardIterator>
3398  _GLIBCXX14_CONSTEXPR
3399  inline pair<_ForwardIterator, _ForwardIterator>
3400  minmax_element(_ForwardIterator __first, _ForwardIterator __last)
3401  {
3402  // concept requirements
3403  __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
3404  __glibcxx_function_requires(_LessThanComparableConcept<
3405  typename iterator_traits<_ForwardIterator>::value_type>)
3406  __glibcxx_requires_valid_range(__first, __last);
3407 
3408  return std::__minmax_element(__first, __last,
3409  __gnu_cxx::__ops::__iter_less_iter());
3410  }
3411 
3412  /**
3413  * @brief Return a pair of iterators pointing to the minimum and maximum
3414  * elements in a range.
3415  * @ingroup sorting_algorithms
3416  * @param __first Start of range.
3417  * @param __last End of range.
3418  * @param __comp Comparison functor.
3419  * @return make_pair(m, M), where m is the first iterator i in
3420  * [__first, __last) such that no other element in the range is
3421  * smaller, and where M is the last iterator i in [__first, __last)
3422  * such that no other element in the range is larger.
3423  */
3424  template<typename _ForwardIterator, typename _Compare>
3425  _GLIBCXX14_CONSTEXPR
3426  inline pair<_ForwardIterator, _ForwardIterator>
3427  minmax_element(_ForwardIterator __first, _ForwardIterator __last,
3428  _Compare __comp)
3429  {
3430  // concept requirements
3431  __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
3432  __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
3433  typename iterator_traits<_ForwardIterator>::value_type,
3434  typename iterator_traits<_ForwardIterator>::value_type>)
3435  __glibcxx_requires_valid_range(__first, __last);
3436 
3437  return std::__minmax_element(__first, __last,
3438  __gnu_cxx::__ops::__iter_comp_iter(__comp));
3439  }
3440 
3441  // N2722 + DR 915.
3442  template<typename _Tp>
3443  _GLIBCXX14_CONSTEXPR
3444  inline _Tp
3445  min(initializer_list<_Tp> __l)
3446  { return *std::min_element(__l.begin(), __l.end()); }
3447 
3448  template<typename _Tp, typename _Compare>
3449  _GLIBCXX14_CONSTEXPR
3450  inline _Tp
3451  min(initializer_list<_Tp> __l, _Compare __comp)
3452  { return *std::min_element(__l.begin(), __l.end(), __comp); }
3453 
3454  template<typename _Tp>
3455  _GLIBCXX14_CONSTEXPR
3456  inline _Tp
3457  max(initializer_list<_Tp> __l)
3458  { return *std::max_element(__l.begin(), __l.end()); }
3459 
3460  template<typename _Tp, typename _Compare>
3461  _GLIBCXX14_CONSTEXPR
3462  inline _Tp
3463  max(initializer_list<_Tp> __l, _Compare __comp)
3464  { return *std::max_element(__l.begin(), __l.end(), __comp); }
3465 
3466  template<typename _Tp>
3467  _GLIBCXX14_CONSTEXPR
3468  inline pair<_Tp, _Tp>
3469  minmax(initializer_list<_Tp> __l)
3470  {
3471  pair<const _Tp*, const _Tp*> __p =
3472  std::minmax_element(__l.begin(), __l.end());
3473  return std::make_pair(*__p.first, *__p.second);
3474  }
3475 
3476  template<typename _Tp, typename _Compare>
3477  _GLIBCXX14_CONSTEXPR
3478  inline pair<_Tp, _Tp>
3479  minmax(initializer_list<_Tp> __l, _Compare __comp)
3480  {
3481  pair<const _Tp*, const _Tp*> __p =
3482  std::minmax_element(__l.begin(), __l.end(), __comp);
3483  return std::make_pair(*__p.first, *__p.second);
3484  }
3485 
3486  template<typename _ForwardIterator1, typename _ForwardIterator2,
3487  typename _BinaryPredicate>
3488  bool
3489  __is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
3490  _ForwardIterator2 __first2, _BinaryPredicate __pred)
3491  {
3492  // Efficiently compare identical prefixes: O(N) if sequences
3493  // have the same elements in the same order.
3494  for (; __first1 != __last1; ++__first1, ++__first2)
3495  if (!__pred(__first1, __first2))
3496  break;
3497 
3498  if (__first1 == __last1)
3499  return true;
3500 
3501  // Establish __last2 assuming equal ranges by iterating over the
3502  // rest of the list.
3503  _ForwardIterator2 __last2 = __first2;
3504  std::advance(__last2, std::distance(__first1, __last1));
3505  for (_ForwardIterator1 __scan = __first1; __scan != __last1; ++__scan)
3506  {
3507  if (__scan != std::__find_if(__first1, __scan,
3508  __gnu_cxx::__ops::__iter_comp_iter(__pred, __scan)))
3509  continue; // We've seen this one before.
3510 
3511  auto __matches
3512  = std::__count_if(__first2, __last2,
3513  __gnu_cxx::__ops::__iter_comp_iter(__pred, __scan));
3514  if (0 == __matches ||
3515  std::__count_if(__scan, __last1,
3516  __gnu_cxx::__ops::__iter_comp_iter(__pred, __scan))
3517  != __matches)
3518  return false;
3519  }
3520  return true;
3521  }
3522 
3523  /**
3524  * @brief Checks whether a permutation of the second sequence is equal
3525  * to the first sequence.
3526  * @ingroup non_mutating_algorithms
3527  * @param __first1 Start of first range.
3528  * @param __last1 End of first range.
3529  * @param __first2 Start of second range.
3530  * @return true if there exists a permutation of the elements in the range
3531  * [__first2, __first2 + (__last1 - __first1)), beginning with
3532  * ForwardIterator2 begin, such that equal(__first1, __last1, begin)
3533  * returns true; otherwise, returns false.
3534  */
3535  template<typename _ForwardIterator1, typename _ForwardIterator2>
3536  inline bool
3537  is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
3538  _ForwardIterator2 __first2)
3539  {
3540  // concept requirements
3541  __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator1>)
3542  __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator2>)
3543  __glibcxx_function_requires(_EqualOpConcept<
3544  typename iterator_traits<_ForwardIterator1>::value_type,
3545  typename iterator_traits<_ForwardIterator2>::value_type>)
3546  __glibcxx_requires_valid_range(__first1, __last1);
3547 
3548  return std::__is_permutation(__first1, __last1, __first2,
3549  __gnu_cxx::__ops::__iter_equal_to_iter());
3550  }
3551 
3552  /**
3553  * @brief Checks whether a permutation of the second sequence is equal
3554  * to the first sequence.
3555  * @ingroup non_mutating_algorithms
3556  * @param __first1 Start of first range.
3557  * @param __last1 End of first range.
3558  * @param __first2 Start of second range.
3559  * @param __pred A binary predicate.
3560  * @return true if there exists a permutation of the elements in
3561  * the range [__first2, __first2 + (__last1 - __first1)),
3562  * beginning with ForwardIterator2 begin, such that
3563  * equal(__first1, __last1, __begin, __pred) returns true;
3564  * otherwise, returns false.
3565  */
3566  template<typename _ForwardIterator1, typename _ForwardIterator2,
3567  typename _BinaryPredicate>
3568  inline bool
3569  is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
3570  _ForwardIterator2 __first2, _BinaryPredicate __pred)
3571  {
3572  // concept requirements
3573  __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator1>)
3574  __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator2>)
3575  __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
3576  typename iterator_traits<_ForwardIterator1>::value_type,
3577  typename iterator_traits<_ForwardIterator2>::value_type>)
3578  __glibcxx_requires_valid_range(__first1, __last1);
3579 
3580  return std::__is_permutation(__first1, __last1, __first2,
3581  __gnu_cxx::__ops::__iter_comp_iter(__pred));
3582  }
3583 
3584 #if __cplusplus > 201103L
3585  template<typename _ForwardIterator1, typename _ForwardIterator2,
3586  typename _BinaryPredicate>
3587  bool
3588  __is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
3589  _ForwardIterator2 __first2, _ForwardIterator2 __last2,
3590  _BinaryPredicate __pred)
3591  {
3592  using _Cat1
3593  = typename iterator_traits<_ForwardIterator1>::iterator_category;
3594  using _Cat2
3595  = typename iterator_traits<_ForwardIterator2>::iterator_category;
3596  using _It1_is_RA = is_same<_Cat1, random_access_iterator_tag>;
3597  using _It2_is_RA = is_same<_Cat2, random_access_iterator_tag>;
3598  constexpr bool __ra_iters = _It1_is_RA() && _It2_is_RA();
3599  if (__ra_iters)
3600  {
3601  auto __d1 = std::distance(__first1, __last1);
3602  auto __d2 = std::distance(__first2, __last2);
3603  if (__d1 != __d2)
3604  return false;
3605  }
3606 
3607  // Efficiently compare identical prefixes: O(N) if sequences
3608  // have the same elements in the same order.
3609  for (; __first1 != __last1 && __first2 != __last2;
3610  ++__first1, ++__first2)
3611  if (!__pred(__first1, __first2))
3612  break;
3613 
3614  if (__ra_iters)
3615  {
3616  if (__first1 == __last1)
3617  return true;
3618  }
3619  else
3620  {
3621  auto __d1 = std::distance(__first1, __last1);
3622  auto __d2 = std::distance(__first2, __last2);
3623  if (__d1 == 0 && __d2 == 0)
3624  return true;
3625  if (__d1 != __d2)
3626  return false;
3627  }
3628 
3629  for (_ForwardIterator1 __scan = __first1; __scan != __last1; ++__scan)
3630  {
3631  if (__scan != std::__find_if(__first1, __scan,
3632  __gnu_cxx::__ops::__iter_comp_iter(__pred, __scan)))
3633  continue; // We've seen this one before.
3634 
3635  auto __matches = std::__count_if(__first2, __last2,
3636  __gnu_cxx::__ops::__iter_comp_iter(__pred, __scan));
3637  if (0 == __matches
3638  || std::__count_if(__scan, __last1,
3639  __gnu_cxx::__ops::__iter_comp_iter(__pred, __scan))
3640  != __matches)
3641  return false;
3642  }
3643  return true;
3644  }
3645 
3646  /**
3647  * @brief Checks whether a permutaion of the second sequence is equal
3648  * to the first sequence.
3649  * @ingroup non_mutating_algorithms
3650  * @param __first1 Start of first range.
3651  * @param __last1 End of first range.
3652  * @param __first2 Start of second range.
3653  * @param __last2 End of first range.
3654  * @return true if there exists a permutation of the elements in the range
3655  * [__first2, __last2), beginning with ForwardIterator2 begin,
3656  * such that equal(__first1, __last1, begin) returns true;
3657  * otherwise, returns false.
3658  */
3659  template<typename _ForwardIterator1, typename _ForwardIterator2>
3660  inline bool
3661  is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
3662  _ForwardIterator2 __first2, _ForwardIterator2 __last2)
3663  {
3664  __glibcxx_requires_valid_range(__first1, __last1);
3665  __glibcxx_requires_valid_range(__first2, __last2);
3666 
3667  return
3668  std::__is_permutation(__first1, __last1, __first2, __last2,
3669  __gnu_cxx::__ops::__iter_equal_to_iter());
3670  }
3671 
3672  /**
3673  * @brief Checks whether a permutation of the second sequence is equal
3674  * to the first sequence.
3675  * @ingroup non_mutating_algorithms
3676  * @param __first1 Start of first range.
3677  * @param __last1 End of first range.
3678  * @param __first2 Start of second range.
3679  * @param __last2 End of first range.
3680  * @param __pred A binary predicate.
3681  * @return true if there exists a permutation of the elements in the range
3682  * [__first2, __last2), beginning with ForwardIterator2 begin,
3683  * such that equal(__first1, __last1, __begin, __pred) returns true;
3684  * otherwise, returns false.
3685  */
3686  template<typename _ForwardIterator1, typename _ForwardIterator2,
3687  typename _BinaryPredicate>
3688  inline bool
3689  is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
3690  _ForwardIterator2 __first2, _ForwardIterator2 __last2,
3691  _BinaryPredicate __pred)
3692  {
3693  __glibcxx_requires_valid_range(__first1, __last1);
3694  __glibcxx_requires_valid_range(__first2, __last2);
3695 
3696  return std::__is_permutation(__first1, __last1, __first2, __last2,
3697  __gnu_cxx::__ops::__iter_comp_iter(__pred));
3698  }
3699 #endif
3700 
3701 #ifdef _GLIBCXX_USE_C99_STDINT_TR1
3702  /**
3703  * @brief Shuffle the elements of a sequence using a uniform random
3704  * number generator.
3705  * @ingroup mutating_algorithms
3706  * @param __first A forward iterator.
3707  * @param __last A forward iterator.
3708  * @param __g A UniformRandomNumberGenerator (26.5.1.3).
3709  * @return Nothing.
3710  *
3711  * Reorders the elements in the range @p [__first,__last) using @p __g to
3712  * provide random numbers.
3713  */
3714  template<typename _RandomAccessIterator,
3715  typename _UniformRandomNumberGenerator>
3716  void
3717  shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last,
3718  _UniformRandomNumberGenerator&& __g)
3719  {
3720  // concept requirements
3721  __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
3722  _RandomAccessIterator>)
3723  __glibcxx_requires_valid_range(__first, __last);
3724 
3725  if (__first == __last)
3726  return;
3727 
3728  typedef typename iterator_traits<_RandomAccessIterator>::difference_type
3729  _DistanceType;
3730 
3731  typedef typename std::make_unsigned<_DistanceType>::type __ud_type;
3732  typedef typename std::uniform_int_distribution<__ud_type> __distr_type;
3733  typedef typename __distr_type::param_type __p_type;
3734  __distr_type __d;
3735 
3736  for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i)
3737  std::iter_swap(__i, __first + __d(__g, __p_type(0, __i - __first)));
3738  }
3739 #endif
3740 
3741 #endif // C++11
3742 
3743 _GLIBCXX_END_NAMESPACE_VERSION
3744 
3745 _GLIBCXX_BEGIN_NAMESPACE_ALGO
3746 
3747  /**
3748  * @brief Apply a function to every element of a sequence.
3749  * @ingroup non_mutating_algorithms
3750  * @param __first An input iterator.
3751  * @param __last An input iterator.
3752  * @param __f A unary function object.
3753  * @return @p __f (std::move(@p __f) in C++0x).
3754  *
3755  * Applies the function object @p __f to each element in the range
3756  * @p [first,last). @p __f must not modify the order of the sequence.
3757  * If @p __f has a return value it is ignored.
3758  */
3759  template<typename _InputIterator, typename _Function>
3760  _Function
3761  for_each(_InputIterator __first, _InputIterator __last, _Function __f)
3762  {
3763  // concept requirements
3764  __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
3765  __glibcxx_requires_valid_range(__first, __last);
3766  for (; __first != __last; ++__first)
3767  __f(*__first);
3768  return _GLIBCXX_MOVE(__f);
3769  }
3770 
3771  /**
3772  * @brief Find the first occurrence of a value in a sequence.
3773  * @ingroup non_mutating_algorithms
3774  * @param __first An input iterator.
3775  * @param __last An input iterator.
3776  * @param __val The value to find.
3777  * @return The first iterator @c i in the range @p [__first,__last)
3778  * such that @c *i == @p __val, or @p __last if no such iterator exists.
3779  */
3780  template<typename _InputIterator, typename _Tp>
3781  inline _InputIterator
3782  find(_InputIterator __first, _InputIterator __last,
3783  const _Tp& __val)
3784  {
3785  // concept requirements
3786  __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
3787  __glibcxx_function_requires(_EqualOpConcept<
3788  typename iterator_traits<_InputIterator>::value_type, _Tp>)
3789  __glibcxx_requires_valid_range(__first, __last);
3790  return std::__find_if(__first, __last,
3791  __gnu_cxx::__ops::__iter_equals_val(__val));
3792  }
3793 
3794  /**
3795  * @brief Find the first element in a sequence for which a
3796  * predicate is true.
3797  * @ingroup non_mutating_algorithms
3798  * @param __first An input iterator.
3799  * @param __last An input iterator.
3800  * @param __pred A predicate.
3801  * @return The first iterator @c i in the range @p [__first,__last)
3802  * such that @p __pred(*i) is true, or @p __last if no such iterator exists.
3803  */
3804  template<typename _InputIterator, typename _Predicate>
3805  inline _InputIterator
3806  find_if(_InputIterator __first, _InputIterator __last,
3807  _Predicate __pred)
3808  {
3809  // concept requirements
3810  __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
3811  __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
3812  typename iterator_traits<_InputIterator>::value_type>)
3813  __glibcxx_requires_valid_range(__first, __last);
3814 
3815  return std::__find_if(__first, __last,
3816  __gnu_cxx::__ops::__pred_iter(__pred));
3817  }
3818 
3819  /**
3820  * @brief Find element from a set in a sequence.
3821  * @ingroup non_mutating_algorithms
3822  * @param __first1 Start of range to search.
3823  * @param __last1 End of range to search.
3824  * @param __first2 Start of match candidates.
3825  * @param __last2 End of match candidates.
3826  * @return The first iterator @c i in the range
3827  * @p [__first1,__last1) such that @c *i == @p *(i2) such that i2 is an
3828  * iterator in [__first2,__last2), or @p __last1 if no such iterator exists.
3829  *
3830  * Searches the range @p [__first1,__last1) for an element that is
3831  * equal to some element in the range [__first2,__last2). If
3832  * found, returns an iterator in the range [__first1,__last1),
3833  * otherwise returns @p __last1.
3834  */
3835  template<typename _InputIterator, typename _ForwardIterator>
3836  _InputIterator
3837  find_first_of(_InputIterator __first1, _InputIterator __last1,
3838  _ForwardIterator __first2, _ForwardIterator __last2)
3839  {
3840  // concept requirements
3841  __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
3842  __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
3843  __glibcxx_function_requires(_EqualOpConcept<
3844  typename iterator_traits<_InputIterator>::value_type,
3845  typename iterator_traits<_ForwardIterator>::value_type>)
3846  __glibcxx_requires_valid_range(__first1, __last1);
3847  __glibcxx_requires_valid_range(__first2, __last2);
3848 
3849  for (; __first1 != __last1; ++__first1)
3850  for (_ForwardIterator __iter = __first2; __iter != __last2; ++__iter)
3851  if (*__first1 == *__iter)
3852  return __first1;
3853  return __last1;
3854  }
3855 
3856  /**
3857  * @brief Find element from a set in a sequence using a predicate.
3858  * @ingroup non_mutating_algorithms
3859  * @param __first1 Start of range to search.
3860  * @param __last1 End of range to search.
3861  * @param __first2 Start of match candidates.
3862  * @param __last2 End of match candidates.
3863  * @param __comp Predicate to use.
3864  * @return The first iterator @c i in the range
3865  * @p [__first1,__last1) such that @c comp(*i, @p *(i2)) is true
3866  * and i2 is an iterator in [__first2,__last2), or @p __last1 if no
3867  * such iterator exists.
3868  *
3869 
3870  * Searches the range @p [__first1,__last1) for an element that is
3871  * equal to some element in the range [__first2,__last2). If
3872  * found, returns an iterator in the range [__first1,__last1),
3873  * otherwise returns @p __last1.
3874  */
3875  template<typename _InputIterator, typename _ForwardIterator,
3876  typename _BinaryPredicate>
3877  _InputIterator
3878  find_first_of(_InputIterator __first1, _InputIterator __last1,
3879  _ForwardIterator __first2, _ForwardIterator __last2,
3880  _BinaryPredicate __comp)
3881  {
3882  // concept requirements
3883  __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
3884  __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
3885  __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
3886  typename iterator_traits<_InputIterator>::value_type,
3887  typename iterator_traits<_ForwardIterator>::value_type>)
3888  __glibcxx_requires_valid_range(__first1, __last1);
3889  __glibcxx_requires_valid_range(__first2, __last2);
3890 
3891  for (; __first1 != __last1; ++__first1)
3892  for (_ForwardIterator __iter = __first2; __iter != __last2; ++__iter)
3893  if (__comp(*__first1, *__iter))
3894  return __first1;
3895  return __last1;
3896  }
3897 
3898  /**
3899  * @brief Find two adjacent values in a sequence that are equal.
3900  * @ingroup non_mutating_algorithms
3901  * @param __first A forward iterator.
3902  * @param __last A forward iterator.
3903  * @return The first iterator @c i such that @c i and @c i+1 are both
3904  * valid iterators in @p [__first,__last) and such that @c *i == @c *(i+1),
3905  * or @p __last if no such iterator exists.
3906  */
3907  template<typename _ForwardIterator>
3908  inline _ForwardIterator
3909  adjacent_find(_ForwardIterator __first, _ForwardIterator __last)
3910  {
3911  // concept requirements
3912  __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
3913  __glibcxx_function_requires(_EqualityComparableConcept<
3914  typename iterator_traits<_ForwardIterator>::value_type>)
3915  __glibcxx_requires_valid_range(__first, __last);
3916 
3917  return std::__adjacent_find(__first, __last,
3918  __gnu_cxx::__ops::__iter_equal_to_iter());
3919  }
3920 
3921  /**
3922  * @brief Find two adjacent values in a sequence using a predicate.
3923  * @ingroup non_mutating_algorithms
3924  * @param __first A forward iterator.
3925  * @param __last A forward iterator.
3926  * @param __binary_pred A binary predicate.
3927  * @return The first iterator @c i such that @c i and @c i+1 are both
3928  * valid iterators in @p [__first,__last) and such that
3929  * @p __binary_pred(*i,*(i+1)) is true, or @p __last if no such iterator
3930  * exists.
3931  */
3932  template<typename _ForwardIterator, typename _BinaryPredicate>
3933  inline _ForwardIterator
3934  adjacent_find(_ForwardIterator __first, _ForwardIterator __last,
3935  _BinaryPredicate __binary_pred)
3936  {
3937  // concept requirements
3938  __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
3939  __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
3940  typename iterator_traits<_ForwardIterator>::value_type,
3941  typename iterator_traits<_ForwardIterator>::value_type>)
3942  __glibcxx_requires_valid_range(__first, __last);
3943 
3944  return std::__adjacent_find(__first, __last,
3945  __gnu_cxx::__ops::__iter_comp_iter(__binary_pred));
3946  }
3947 
3948  /**
3949  * @brief Count the number of copies of a value in a sequence.
3950  * @ingroup non_mutating_algorithms
3951  * @param __first An input iterator.
3952  * @param __last An input iterator.
3953  * @param __value The value to be counted.
3954  * @return The number of iterators @c i in the range @p [__first,__last)
3955  * for which @c *i == @p __value
3956  */
3957  template<typename _InputIterator, typename _Tp>
3958  inline typename iterator_traits<_InputIterator>::difference_type
3959  count(_InputIterator __first, _InputIterator __last, const _Tp& __value)
3960  {
3961  // concept requirements
3962  __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
3963  __glibcxx_function_requires(_EqualOpConcept<
3964  typename iterator_traits<_InputIterator>::value_type, _Tp>)
3965  __glibcxx_requires_valid_range(__first, __last);
3966 
3967  return std::__count_if(__first, __last,
3968  __gnu_cxx::__ops::__iter_equals_val(__value));
3969  }
3970 
3971  /**
3972  * @brief Count the elements of a sequence for which a predicate is true.
3973  * @ingroup non_mutating_algorithms
3974  * @param __first An input iterator.
3975  * @param __last An input iterator.
3976  * @param __pred A predicate.
3977  * @return The number of iterators @c i in the range @p [__first,__last)
3978  * for which @p __pred(*i) is true.
3979  */
3980  template<typename _InputIterator, typename _Predicate>
3981  inline typename iterator_traits<_InputIterator>::difference_type
3982  count_if(_InputIterator __first, _InputIterator __last, _Predicate __pred)
3983  {
3984  // concept requirements
3985  __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
3986  __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
3987  typename iterator_traits<_InputIterator>::value_type>)
3988  __glibcxx_requires_valid_range(__first, __last);
3989 
3990  return std::__count_if(__first, __last,
3991  __gnu_cxx::__ops::__pred_iter(__pred));
3992  }
3993 
3994  /**
3995  * @brief Search a sequence for a matching sub-sequence.
3996  * @ingroup non_mutating_algorithms
3997  * @param __first1 A forward iterator.
3998  * @param __last1 A forward iterator.
3999  * @param __first2 A forward iterator.
4000  * @param __last2 A forward iterator.
4001  * @return The first iterator @c i in the range @p
4002  * [__first1,__last1-(__last2-__first2)) such that @c *(i+N) == @p
4003  * *(__first2+N) for each @c N in the range @p
4004  * [0,__last2-__first2), or @p __last1 if no such iterator exists.
4005  *
4006  * Searches the range @p [__first1,__last1) for a sub-sequence that
4007  * compares equal value-by-value with the sequence given by @p
4008  * [__first2,__last2) and returns an iterator to the first element
4009  * of the sub-sequence, or @p __last1 if the sub-sequence is not
4010  * found.
4011  *
4012  * Because the sub-sequence must lie completely within the range @p
4013  * [__first1,__last1) it must start at a position less than @p
4014  * __last1-(__last2-__first2) where @p __last2-__first2 is the
4015  * length of the sub-sequence.
4016  *
4017  * This means that the returned iterator @c i will be in the range
4018  * @p [__first1,__last1-(__last2-__first2))
4019  */
4020  template<typename _ForwardIterator1, typename _ForwardIterator2>
4021  inline _ForwardIterator1
4022  search(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
4023  _ForwardIterator2 __first2, _ForwardIterator2 __last2)
4024  {
4025  // concept requirements
4026  __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator1>)
4027  __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator2>)
4028  __glibcxx_function_requires(_EqualOpConcept<
4029  typename iterator_traits<_ForwardIterator1>::value_type,
4030  typename iterator_traits<_ForwardIterator2>::value_type>)
4031  __glibcxx_requires_valid_range(__first1, __last1);
4032  __glibcxx_requires_valid_range(__first2, __last2);
4033 
4034  return std::__search(__first1, __last1, __first2, __last2,
4035  __gnu_cxx::__ops::__iter_equal_to_iter());
4036  }
4037 
4038  /**
4039  * @brief Search a sequence for a matching sub-sequence using a predicate.
4040  * @ingroup non_mutating_algorithms
4041  * @param __first1 A forward iterator.
4042  * @param __last1 A forward iterator.
4043  * @param __first2 A forward iterator.
4044  * @param __last2 A forward iterator.
4045  * @param __predicate A binary predicate.
4046  * @return The first iterator @c i in the range
4047  * @p [__first1,__last1-(__last2-__first2)) such that
4048  * @p __predicate(*(i+N),*(__first2+N)) is true for each @c N in the range
4049  * @p [0,__last2-__first2), or @p __last1 if no such iterator exists.
4050  *
4051  * Searches the range @p [__first1,__last1) for a sub-sequence that
4052  * compares equal value-by-value with the sequence given by @p
4053  * [__first2,__last2), using @p __predicate to determine equality,
4054  * and returns an iterator to the first element of the
4055  * sub-sequence, or @p __last1 if no such iterator exists.
4056  *
4057  * @see search(_ForwardIter1, _ForwardIter1, _ForwardIter2, _ForwardIter2)
4058  */
4059  template<typename _ForwardIterator1, typename _ForwardIterator2,
4060  typename _BinaryPredicate>
4061  inline _ForwardIterator1
4062  search(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
4063  _ForwardIterator2 __first2, _ForwardIterator2 __last2,
4064  _BinaryPredicate __predicate)
4065  {
4066  // concept requirements
4067  __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator1>)
4068  __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator2>)
4069  __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
4070  typename iterator_traits<_ForwardIterator1>::value_type,
4071  typename iterator_traits<_ForwardIterator2>::value_type>)
4072  __glibcxx_requires_valid_range(__first1, __last1);
4073  __glibcxx_requires_valid_range(__first2, __last2);
4074 
4075  return std::__search(__first1, __last1, __first2, __last2,
4076  __gnu_cxx::__ops::__iter_comp_iter(__predicate));
4077  }
4078 
4079  /**
4080  * @brief Search a sequence for a number of consecutive values.
4081  * @ingroup non_mutating_algorithms
4082  * @param __first A forward iterator.
4083  * @param __last A forward iterator.
4084  * @param __count The number of consecutive values.
4085  * @param __val The value to find.
4086  * @return The first iterator @c i in the range @p
4087  * [__first,__last-__count) such that @c *(i+N) == @p __val for
4088  * each @c N in the range @p [0,__count), or @p __last if no such
4089  * iterator exists.
4090  *
4091  * Searches the range @p [__first,__last) for @p count consecutive elements
4092  * equal to @p __val.
4093  */
4094  template<typename _ForwardIterator, typename _Integer, typename _Tp>
4095  inline _ForwardIterator
4096  search_n(_ForwardIterator __first, _ForwardIterator __last,
4097  _Integer __count, const _Tp& __val)
4098  {
4099  // concept requirements
4100  __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
4101  __glibcxx_function_requires(_EqualOpConcept<
4102  typename iterator_traits<_ForwardIterator>::value_type, _Tp>)
4103  __glibcxx_requires_valid_range(__first, __last);
4104 
4105  return std::__search_n(__first, __last, __count,
4106  __gnu_cxx::__ops::__iter_equals_val(__val));
4107  }
4108 
4109 
4110  /**
4111  * @brief Search a sequence for a number of consecutive values using a
4112  * predicate.
4113  * @ingroup non_mutating_algorithms
4114  * @param __first A forward iterator.
4115  * @param __last A forward iterator.
4116  * @param __count The number of consecutive values.
4117  * @param __val The value to find.
4118  * @param __binary_pred A binary predicate.
4119  * @return The first iterator @c i in the range @p
4120  * [__first,__last-__count) such that @p
4121  * __binary_pred(*(i+N),__val) is true for each @c N in the range
4122  * @p [0,__count), or @p __last if no such iterator exists.
4123  *
4124  * Searches the range @p [__first,__last) for @p __count
4125  * consecutive elements for which the predicate returns true.
4126  */
4127  template<typename _ForwardIterator, typename _Integer, typename _Tp,
4128  typename _BinaryPredicate>
4129  inline _ForwardIterator
4130  search_n(_ForwardIterator __first, _ForwardIterator __last,
4131  _Integer __count, const _Tp& __val,
4132  _BinaryPredicate __binary_pred)
4133  {
4134  // concept requirements
4135  __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
4136  __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
4137  typename iterator_traits<_ForwardIterator>::value_type, _Tp>)
4138  __glibcxx_requires_valid_range(__first, __last);
4139 
4140  return std::__search_n(__first, __last, __count,
4141  __gnu_cxx::__ops::__iter_comp_val(__binary_pred, __val));
4142  }
4143 
4144 
4145  /**
4146  * @brief Perform an operation on a sequence.
4147  * @ingroup mutating_algorithms
4148  * @param __first An input iterator.
4149  * @param __last An input iterator.
4150  * @param __result An output iterator.
4151  * @param __unary_op A unary operator.
4152  * @return An output iterator equal to @p __result+(__last-__first).
4153  *
4154  * Applies the operator to each element in the input range and assigns
4155  * the results to successive elements of the output sequence.
4156  * Evaluates @p *(__result+N)=unary_op(*(__first+N)) for each @c N in the
4157  * range @p [0,__last-__first).
4158  *
4159  * @p unary_op must not alter its argument.
4160  */
4161  template<typename _InputIterator, typename _OutputIterator,
4162  typename _UnaryOperation>
4163  _OutputIterator
4164  transform(_InputIterator __first, _InputIterator __last,
4165  _OutputIterator __result, _UnaryOperation __unary_op)
4166  {
4167  // concept requirements
4168  __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
4169  __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
4170  // "the type returned by a _UnaryOperation"
4171  __typeof__(__unary_op(*__first))>)
4172  __glibcxx_requires_valid_range(__first, __last);
4173 
4174  for (; __first != __last; ++__first, ++__result)
4175  *__result = __unary_op(*__first);
4176  return __result;
4177  }
4178 
4179  /**
4180  * @brief Perform an operation on corresponding elements of two sequences.
4181  * @ingroup mutating_algorithms
4182  * @param __first1 An input iterator.
4183  * @param __last1 An input iterator.
4184  * @param __first2 An input iterator.
4185  * @param __result An output iterator.
4186  * @param __binary_op A binary operator.
4187  * @return An output iterator equal to @p result+(last-first).
4188  *
4189  * Applies the operator to the corresponding elements in the two
4190  * input ranges and assigns the results to successive elements of the
4191  * output sequence.
4192  * Evaluates @p
4193  * *(__result+N)=__binary_op(*(__first1+N),*(__first2+N)) for each
4194  * @c N in the range @p [0,__last1-__first1).
4195  *
4196  * @p binary_op must not alter either of its arguments.
4197  */
4198  template<typename _InputIterator1, typename _InputIterator2,
4199  typename _OutputIterator, typename _BinaryOperation>
4200  _OutputIterator
4201  transform(_InputIterator1 __first1, _InputIterator1 __last1,
4202  _InputIterator2 __first2, _OutputIterator __result,
4203  _BinaryOperation __binary_op)
4204  {
4205  // concept requirements
4206  __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
4207  __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
4208  __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
4209  // "the type returned by a _BinaryOperation"
4210  __typeof__(__binary_op(*__first1,*__first2))>)
4211  __glibcxx_requires_valid_range(__first1, __last1);
4212 
4213  for (; __first1 != __last1; ++__first1, ++__first2, ++__result)
4214  *__result = __binary_op(*__first1, *__first2);
4215  return __result;
4216  }
4217 
4218  /**
4219  * @brief Replace each occurrence of one value in a sequence with another
4220  * value.
4221  * @ingroup mutating_algorithms
4222  * @param __first A forward iterator.
4223  * @param __last A forward iterator.
4224  * @param __old_value The value to be replaced.
4225  * @param __new_value The replacement value.
4226  * @return replace() returns no value.
4227  *
4228  * For each iterator @c i in the range @p [__first,__last) if @c *i ==
4229  * @p __old_value then the assignment @c *i = @p __new_value is performed.
4230  */
4231  template<typename _ForwardIterator, typename _Tp>
4232  void
4233  replace(_ForwardIterator __first, _ForwardIterator __last,
4234  const _Tp& __old_value, const _Tp& __new_value)
4235  {
4236  // concept requirements
4237  __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
4238  _ForwardIterator>)
4239  __glibcxx_function_requires(_EqualOpConcept<
4240  typename iterator_traits<_ForwardIterator>::value_type, _Tp>)
4241  __glibcxx_function_requires(_ConvertibleConcept<_Tp,
4242  typename iterator_traits<_ForwardIterator>::value_type>)
4243  __glibcxx_requires_valid_range(__first, __last);
4244 
4245  for (; __first != __last; ++__first)
4246  if (*__first == __old_value)
4247  *__first = __new_value;
4248  }
4249 
4250  /**
4251  * @brief Replace each value in a sequence for which a predicate returns
4252  * true with another value.
4253  * @ingroup mutating_algorithms
4254  * @param __first A forward iterator.
4255  * @param __last A forward iterator.
4256  * @param __pred A predicate.
4257  * @param __new_value The replacement value.
4258  * @return replace_if() returns no value.
4259  *
4260  * For each iterator @c i in the range @p [__first,__last) if @p __pred(*i)
4261  * is true then the assignment @c *i = @p __new_value is performed.
4262  */
4263  template<typename _ForwardIterator, typename _Predicate, typename _Tp>
4264  void
4265  replace_if(_ForwardIterator __first, _ForwardIterator __last,
4266  _Predicate __pred, const _Tp& __new_value)
4267  {
4268  // concept requirements
4269  __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
4270  _ForwardIterator>)
4271  __glibcxx_function_requires(_ConvertibleConcept<_Tp,
4272  typename iterator_traits<_ForwardIterator>::value_type>)
4273  __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
4274  typename iterator_traits<_ForwardIterator>::value_type>)
4275  __glibcxx_requires_valid_range(__first, __last);
4276 
4277  for (; __first != __last; ++__first)
4278  if (__pred(*__first))
4279  *__first = __new_value;
4280  }
4281 
4282  /**
4283  * @brief Assign the result of a function object to each value in a
4284  * sequence.
4285  * @ingroup mutating_algorithms
4286  * @param __first A forward iterator.
4287  * @param __last A forward iterator.
4288  * @param __gen A function object taking no arguments and returning
4289  * std::iterator_traits<_ForwardIterator>::value_type
4290  * @return generate() returns no value.
4291  *
4292  * Performs the assignment @c *i = @p __gen() for each @c i in the range
4293  * @p [__first,__last).
4294  */
4295  template<typename _ForwardIterator, typename _Generator>
4296  void
4297  generate(_ForwardIterator __first, _ForwardIterator __last,
4298  _Generator __gen)
4299  {
4300  // concept requirements
4301  __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
4302  __glibcxx_function_requires(_GeneratorConcept<_Generator,
4303  typename iterator_traits<_ForwardIterator>::value_type>)
4304  __glibcxx_requires_valid_range(__first, __last);
4305 
4306  for (; __first != __last; ++__first)
4307  *__first = __gen();
4308  }
4309 
4310  /**
4311  * @brief Assign the result of a function object to each value in a
4312  * sequence.
4313  * @ingroup mutating_algorithms
4314  * @param __first A forward iterator.
4315  * @param __n The length of the sequence.
4316  * @param __gen A function object taking no arguments and returning
4317  * std::iterator_traits<_ForwardIterator>::value_type
4318  * @return The end of the sequence, @p __first+__n
4319  *
4320  * Performs the assignment @c *i = @p __gen() for each @c i in the range
4321  * @p [__first,__first+__n).
4322  *
4323  * _GLIBCXX_RESOLVE_LIB_DEFECTS
4324  * DR 865. More algorithms that throw away information
4325  */
4326  template<typename _OutputIterator, typename _Size, typename _Generator>
4327  _OutputIterator
4328  generate_n(_OutputIterator __first, _Size __n, _Generator __gen)
4329  {
4330  // concept requirements
4331  __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
4332  // "the type returned by a _Generator"
4333  __typeof__(__gen())>)
4334 
4335  for (__decltype(__n + 0) __niter = __n;
4336  __niter > 0; --__niter, ++__first)
4337  *__first = __gen();
4338  return __first;
4339  }
4340 
4341  /**
4342  * @brief Copy a sequence, removing consecutive duplicate values.
4343  * @ingroup mutating_algorithms
4344  * @param __first An input iterator.
4345  * @param __last An input iterator.
4346  * @param __result An output iterator.
4347  * @return An iterator designating the end of the resulting sequence.
4348  *
4349  * Copies each element in the range @p [__first,__last) to the range
4350  * beginning at @p __result, except that only the first element is copied
4351  * from groups of consecutive elements that compare equal.
4352  * unique_copy() is stable, so the relative order of elements that are
4353  * copied is unchanged.
4354  *
4355  * _GLIBCXX_RESOLVE_LIB_DEFECTS
4356  * DR 241. Does unique_copy() require CopyConstructible and Assignable?
4357  *
4358  * _GLIBCXX_RESOLVE_LIB_DEFECTS
4359  * DR 538. 241 again: Does unique_copy() require CopyConstructible and
4360  * Assignable?
4361  */
4362  template<typename _InputIterator, typename _OutputIterator>
4363  inline _OutputIterator
4364  unique_copy(_InputIterator __first, _InputIterator __last,
4365  _OutputIterator __result)
4366  {
4367  // concept requirements
4368  __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
4369  __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
4370  typename iterator_traits<_InputIterator>::value_type>)
4371  __glibcxx_function_requires(_EqualityComparableConcept<
4372  typename iterator_traits<_InputIterator>::value_type>)
4373  __glibcxx_requires_valid_range(__first, __last);
4374 
4375  if (__first == __last)
4376  return __result;
4377  return std::__unique_copy(__first, __last, __result,
4378  __gnu_cxx::__ops::__iter_equal_to_iter(),
4379  std::__iterator_category(__first),
4380  std::__iterator_category(__result));
4381  }
4382 
4383  /**
4384  * @brief Copy a sequence, removing consecutive values using a predicate.
4385  * @ingroup mutating_algorithms
4386  * @param __first An input iterator.
4387  * @param __last An input iterator.
4388  * @param __result An output iterator.
4389  * @param __binary_pred A binary predicate.
4390  * @return An iterator designating the end of the resulting sequence.
4391  *
4392  * Copies each element in the range @p [__first,__last) to the range
4393  * beginning at @p __result, except that only the first element is copied
4394  * from groups of consecutive elements for which @p __binary_pred returns
4395  * true.
4396  * unique_copy() is stable, so the relative order of elements that are
4397  * copied is unchanged.
4398  *
4399  * _GLIBCXX_RESOLVE_LIB_DEFECTS
4400  * DR 241. Does unique_copy() require CopyConstructible and Assignable?
4401  */
4402  template<typename _InputIterator, typename _OutputIterator,
4403  typename _BinaryPredicate>
4404  inline _OutputIterator
4405  unique_copy(_InputIterator __first, _InputIterator __last,
4406  _OutputIterator __result,
4407  _BinaryPredicate __binary_pred)
4408  {
4409  // concept requirements -- predicates checked later
4410  __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
4411  __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
4412  typename iterator_traits<_InputIterator>::value_type>)
4413  __glibcxx_requires_valid_range(__first, __last);
4414 
4415  if (__first == __last)
4416  return __result;
4417  return std::__unique_copy(__first, __last, __result,
4418  __gnu_cxx::__ops::__iter_comp_iter(__binary_pred),
4419  std::__iterator_category(__first),
4420  std::__iterator_category(__result));
4421  }
4422 
4423  /**
4424  * @brief Randomly shuffle the elements of a sequence.
4425  * @ingroup mutating_algorithms
4426  * @param __first A forward iterator.
4427  * @param __last A forward iterator.
4428  * @return Nothing.
4429  *
4430  * Reorder the elements in the range @p [__first,__last) using a random
4431  * distribution, so that every possible ordering of the sequence is
4432  * equally likely.
4433  */
4434  template<typename _RandomAccessIterator>
4435  inline void
4436  random_shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last)
4437  {
4438  // concept requirements
4439  __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
4440  _RandomAccessIterator>)
4441  __glibcxx_requires_valid_range(__first, __last);
4442 
4443  if (__first != __last)
4444  for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i)
4445  {
4446  // XXX rand() % N is not uniformly distributed
4447  _RandomAccessIterator __j = __first
4448  + std::rand() % ((__i - __first) + 1);
4449  if (__i != __j)
4450  std::iter_swap(__i, __j);
4451  }
4452  }
4453 
4454  /**
4455  * @brief Shuffle the elements of a sequence using a random number
4456  * generator.
4457  * @ingroup mutating_algorithms
4458  * @param __first A forward iterator.
4459  * @param __last A forward iterator.
4460  * @param __rand The RNG functor or function.
4461  * @return Nothing.
4462  *
4463  * Reorders the elements in the range @p [__first,__last) using @p __rand to
4464  * provide a random distribution. Calling @p __rand(N) for a positive
4465  * integer @p N should return a randomly chosen integer from the
4466  * range [0,N).
4467  */
4468  template<typename _RandomAccessIterator, typename _RandomNumberGenerator>
4469  void
4470  random_shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last,
4471 #if __cplusplus >= 201103L
4472  _RandomNumberGenerator&& __rand)
4473 #else
4474  _RandomNumberGenerator& __rand)
4475 #endif
4476  {
4477  // concept requirements
4478  __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
4479  _RandomAccessIterator>)
4480  __glibcxx_requires_valid_range(__first, __last);
4481 
4482  if (__first == __last)
4483  return;
4484  for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i)
4485  {
4486  _RandomAccessIterator __j = __first + __rand((__i - __first) + 1);
4487  if (__i != __j)
4488  std::iter_swap(__i, __j);
4489  }
4490  }
4491 
4492 
4493  /**
4494  * @brief Move elements for which a predicate is true to the beginning
4495  * of a sequence.
4496  * @ingroup mutating_algorithms
4497  * @param __first A forward iterator.
4498  * @param __last A forward iterator.
4499  * @param __pred A predicate functor.
4500  * @return An iterator @p middle such that @p __pred(i) is true for each
4501  * iterator @p i in the range @p [__first,middle) and false for each @p i
4502  * in the range @p [middle,__last).
4503  *
4504  * @p __pred must not modify its operand. @p partition() does not preserve
4505  * the relative ordering of elements in each group, use
4506  * @p stable_partition() if this is needed.
4507  */
4508  template<typename _ForwardIterator, typename _Predicate>
4509  inline _ForwardIterator
4510  partition(_ForwardIterator __first, _ForwardIterator __last,
4511  _Predicate __pred)
4512  {
4513  // concept requirements
4514  __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
4515  _ForwardIterator>)
4516  __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
4517  typename iterator_traits<_ForwardIterator>::value_type>)
4518  __glibcxx_requires_valid_range(__first, __last);
4519 
4520  return std::__partition(__first, __last, __pred,
4521  std::__iterator_category(__first));
4522  }
4523 
4524 
4525  /**
4526  * @brief Sort the smallest elements of a sequence.
4527  * @ingroup sorting_algorithms
4528  * @param __first An iterator.
4529  * @param __middle Another iterator.
4530  * @param __last Another iterator.
4531  * @return Nothing.
4532  *
4533  * Sorts the smallest @p (__middle-__first) elements in the range
4534  * @p [first,last) and moves them to the range @p [__first,__middle). The
4535  * order of the remaining elements in the range @p [__middle,__last) is
4536  * undefined.
4537  * After the sort if @e i and @e j are iterators in the range
4538  * @p [__first,__middle) such that i precedes j and @e k is an iterator in
4539  * the range @p [__middle,__last) then *j<*i and *k<*i are both false.
4540  */
4541  template<typename _RandomAccessIterator>
4542  inline void
4543  partial_sort(_RandomAccessIterator __first,
4544  _RandomAccessIterator __middle,
4545  _RandomAccessIterator __last)
4546  {
4547  // concept requirements
4548  __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
4549  _RandomAccessIterator>)
4550  __glibcxx_function_requires(_LessThanComparableConcept<
4551  typename iterator_traits<_RandomAccessIterator>::value_type>)
4552  __glibcxx_requires_valid_range(__first, __middle);
4553  __glibcxx_requires_valid_range(__middle, __last);
4554 
4555  std::__partial_sort(__first, __middle, __last,
4556  __gnu_cxx::__ops::__iter_less_iter());
4557  }
4558 
4559  /**
4560  * @brief Sort the smallest elements of a sequence using a predicate
4561  * for comparison.
4562  * @ingroup sorting_algorithms
4563  * @param __first An iterator.
4564  * @param __middle Another iterator.
4565  * @param __last Another iterator.
4566  * @param __comp A comparison functor.
4567  * @return Nothing.
4568  *
4569  * Sorts the smallest @p (__middle-__first) elements in the range
4570  * @p [__first,__last) and moves them to the range @p [__first,__middle). The
4571  * order of the remaining elements in the range @p [__middle,__last) is
4572  * undefined.
4573  * After the sort if @e i and @e j are iterators in the range
4574  * @p [__first,__middle) such that i precedes j and @e k is an iterator in
4575  * the range @p [__middle,__last) then @p *__comp(j,*i) and @p __comp(*k,*i)
4576  * are both false.
4577  */
4578  template<typename _RandomAccessIterator, typename _Compare>
4579  inline void
4580  partial_sort(_RandomAccessIterator __first,
4581  _RandomAccessIterator __middle,
4582  _RandomAccessIterator __last,
4583  _Compare __comp)
4584  {
4585  // concept requirements
4586  __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
4587  _RandomAccessIterator>)
4588  __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
4589  typename iterator_traits<_RandomAccessIterator>::value_type,
4590  typename iterator_traits<_RandomAccessIterator>::value_type>)
4591  __glibcxx_requires_valid_range(__first, __middle);
4592  __glibcxx_requires_valid_range(__middle, __last);
4593 
4594  std::__partial_sort(__first, __middle, __last,
4595  __gnu_cxx::__ops::__iter_comp_iter(__comp));
4596  }
4597 
4598  /**
4599  * @brief Sort a sequence just enough to find a particular position.
4600  * @ingroup sorting_algorithms
4601  * @param __first An iterator.
4602  * @param __nth Another iterator.
4603  * @param __last Another iterator.
4604  * @return Nothing.
4605  *
4606  * Rearranges the elements in the range @p [__first,__last) so that @p *__nth
4607  * is the same element that would have been in that position had the
4608  * whole sequence been sorted. The elements either side of @p *__nth are
4609  * not completely sorted, but for any iterator @e i in the range
4610  * @p [__first,__nth) and any iterator @e j in the range @p [__nth,__last) it
4611  * holds that *j < *i is false.
4612  */
4613  template<typename _RandomAccessIterator>
4614  inline void
4615  nth_element(_RandomAccessIterator __first, _RandomAccessIterator __nth,
4616  _RandomAccessIterator __last)
4617  {
4618  // concept requirements
4619  __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
4620  _RandomAccessIterator>)
4621  __glibcxx_function_requires(_LessThanComparableConcept<
4622  typename iterator_traits<_RandomAccessIterator>::value_type>)
4623  __glibcxx_requires_valid_range(__first, __nth);
4624  __glibcxx_requires_valid_range(__nth, __last);
4625 
4626  if (__first == __last || __nth == __last)
4627  return;
4628 
4629  std::__introselect(__first, __nth, __last,
4630  std::__lg(__last - __first) * 2,
4631  __gnu_cxx::__ops::__iter_less_iter());
4632  }
4633 
4634  /**
4635  * @brief Sort a sequence just enough to find a particular position
4636  * using a predicate for comparison.
4637  * @ingroup sorting_algorithms
4638  * @param __first An iterator.
4639  * @param __nth Another iterator.
4640  * @param __last Another iterator.
4641  * @param __comp A comparison functor.
4642  * @return Nothing.
4643  *
4644  * Rearranges the elements in the range @p [__first,__last) so that @p *__nth
4645  * is the same element that would have been in that position had the
4646  * whole sequence been sorted. The elements either side of @p *__nth are
4647  * not completely sorted, but for any iterator @e i in the range
4648  * @p [__first,__nth) and any iterator @e j in the range @p [__nth,__last) it
4649  * holds that @p __comp(*j,*i) is false.
4650  */
4651  template<typename _RandomAccessIterator, typename _Compare>
4652  inline void
4653  nth_element(_RandomAccessIterator __first, _RandomAccessIterator __nth,
4654  _RandomAccessIterator __last, _Compare __comp)
4655  {
4656  // concept requirements
4657  __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
4658  _RandomAccessIterator>)
4659  __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
4660  typename iterator_traits<_RandomAccessIterator>::value_type,
4661  typename iterator_traits<_RandomAccessIterator>::value_type>)
4662  __glibcxx_requires_valid_range(__first, __nth);
4663  __glibcxx_requires_valid_range(__nth, __last);
4664 
4665  if (__first == __last || __nth == __last)
4666  return;
4667 
4668  std::__introselect(__first, __nth, __last,
4669  std::__lg(__last - __first) * 2,
4670  __gnu_cxx::__ops::__iter_comp_iter(__comp));
4671  }
4672 
4673  /**
4674  * @brief Sort the elements of a sequence.
4675  * @ingroup sorting_algorithms
4676  * @param __first An iterator.
4677  * @param __last Another iterator.
4678  * @return Nothing.
4679  *
4680  * Sorts the elements in the range @p [__first,__last) in ascending order,
4681  * such that for each iterator @e i in the range @p [__first,__last-1),
4682  * *(i+1)<*i is false.
4683  *
4684  * The relative ordering of equivalent elements is not preserved, use
4685  * @p stable_sort() if this is needed.
4686  */
4687  template<typename _RandomAccessIterator>
4688  inline void
4689  sort(_RandomAccessIterator __first, _RandomAccessIterator __last)
4690  {
4691  // concept requirements
4692  __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
4693  _RandomAccessIterator>)
4694  __glibcxx_function_requires(_LessThanComparableConcept<
4695  typename iterator_traits<_RandomAccessIterator>::value_type>)
4696  __glibcxx_requires_valid_range(__first, __last);
4697 
4698  std::__sort(__first, __last, __gnu_cxx::__ops::__iter_less_iter());
4699  }
4700 
4701  /**
4702  * @brief Sort the elements of a sequence using a predicate for comparison.
4703  * @ingroup sorting_algorithms
4704  * @param __first An iterator.
4705  * @param __last Another iterator.
4706  * @param __comp A comparison functor.
4707  * @return Nothing.
4708  *
4709  * Sorts the elements in the range @p [__first,__last) in ascending order,
4710  * such that @p __comp(*(i+1),*i) is false for every iterator @e i in the
4711  * range @p [__first,__last-1).
4712  *
4713  * The relative ordering of equivalent elements is not preserved, use
4714  * @p stable_sort() if this is needed.
4715  */
4716  template<typename _RandomAccessIterator, typename _Compare>
4717  inline void
4718  sort(_RandomAccessIterator __first, _RandomAccessIterator __last,
4719  _Compare __comp)
4720  {
4721  // concept requirements
4722  __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
4723  _RandomAccessIterator>)
4724  __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
4725  typename iterator_traits<_RandomAccessIterator>::value_type,
4726  typename iterator_traits<_RandomAccessIterator>::value_type>)
4727  __glibcxx_requires_valid_range(__first, __last);
4728 
4729  std::__sort(__first, __last, __gnu_cxx::__ops::__iter_comp_iter(__comp));
4730  }
4731 
4732  template<typename _InputIterator1, typename _InputIterator2,
4733  typename _OutputIterator, typename _Compare>
4734  _OutputIterator
4735  __merge(_InputIterator1 __first1, _InputIterator1 __last1,
4736  _InputIterator2 __first2, _InputIterator2 __last2,
4737  _OutputIterator __result, _Compare __comp)
4738  {
4739  while (__first1 != __last1 && __first2 != __last2)
4740  {
4741  if (__comp(__first2, __first1))
4742  {
4743  *__result = *__first2;
4744  ++__first2;
4745  }
4746  else
4747  {
4748  *__result = *__first1;
4749  ++__first1;
4750  }
4751  ++__result;
4752  }
4753  return std::copy(__first2, __last2,
4754  std::copy(__first1, __last1, __result));
4755  }
4756 
4757  /**
4758  * @brief Merges two sorted ranges.
4759  * @ingroup sorting_algorithms
4760  * @param __first1 An iterator.
4761  * @param __first2 Another iterator.
4762  * @param __last1 Another iterator.
4763  * @param __last2 Another iterator.
4764  * @param __result An iterator pointing to the end of the merged range.
4765  * @return An iterator pointing to the first element <em>not less
4766  * than</em> @e val.
4767  *
4768  * Merges the ranges @p [__first1,__last1) and @p [__first2,__last2) into
4769  * the sorted range @p [__result, __result + (__last1-__first1) +
4770  * (__last2-__first2)). Both input ranges must be sorted, and the
4771  * output range must not overlap with either of the input ranges.
4772  * The sort is @e stable, that is, for equivalent elements in the
4773  * two ranges, elements from the first range will always come
4774  * before elements from the second.
4775  */
4776  template<typename _InputIterator1, typename _InputIterator2,
4777  typename _OutputIterator>
4778  inline _OutputIterator
4779  merge(_InputIterator1 __first1, _InputIterator1 __last1,
4780  _InputIterator2 __first2, _InputIterator2 __last2,
4781  _OutputIterator __result)
4782  {
4783  // concept requirements
4784  __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
4785  __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
4786  __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
4787  typename iterator_traits<_InputIterator1>::value_type>)
4788  __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
4789  typename iterator_traits<_InputIterator2>::value_type>)
4790  __glibcxx_function_requires(_LessThanOpConcept<
4791  typename iterator_traits<_InputIterator2>::value_type,
4792  typename iterator_traits<_InputIterator1>::value_type>)
4793  __glibcxx_requires_sorted_set(__first1, __last1, __first2);
4794  __glibcxx_requires_sorted_set(__first2, __last2, __first1);
4795 
4796  return _GLIBCXX_STD_A::__merge(__first1, __last1,
4797  __first2, __last2, __result,
4798  __gnu_cxx::__ops::__iter_less_iter());
4799  }
4800 
4801  /**
4802  * @brief Merges two sorted ranges.
4803  * @ingroup sorting_algorithms
4804  * @param __first1 An iterator.
4805  * @param __first2 Another iterator.
4806  * @param __last1 Another iterator.
4807  * @param __last2 Another iterator.
4808  * @param __result An iterator pointing to the end of the merged range.
4809  * @param __comp A functor to use for comparisons.
4810  * @return An iterator pointing to the first element "not less
4811  * than" @e val.
4812  *
4813  * Merges the ranges @p [__first1,__last1) and @p [__first2,__last2) into
4814  * the sorted range @p [__result, __result + (__last1-__first1) +
4815  * (__last2-__first2)). Both input ranges must be sorted, and the
4816  * output range must not overlap with either of the input ranges.
4817  * The sort is @e stable, that is, for equivalent elements in the
4818  * two ranges, elements from the first range will always come
4819  * before elements from the second.
4820  *
4821  * The comparison function should have the same effects on ordering as
4822  * the function used for the initial sort.
4823  */
4824  template<typename _InputIterator1, typename _InputIterator2,
4825  typename _OutputIterator, typename _Compare>
4826  inline _OutputIterator
4827  merge(_InputIterator1 __first1, _InputIterator1 __last1,
4828  _InputIterator2 __first2, _InputIterator2 __last2,
4829  _OutputIterator __result, _Compare __comp)
4830  {
4831  // concept requirements
4832  __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
4833  __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
4834  __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
4835  typename iterator_traits<_InputIterator1>::value_type>)
4836  __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
4837  typename iterator_traits<_InputIterator2>::value_type>)
4838  __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
4839  typename iterator_traits<_InputIterator2>::value_type,
4840  typename iterator_traits<_InputIterator1>::value_type>)
4841  __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp);
4842  __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp);
4843 
4844  return _GLIBCXX_STD_A::__merge(__first1, __last1,
4845  __first2, __last2, __result,
4846  __gnu_cxx::__ops::__iter_comp_iter(__comp));
4847  }
4848 
4849  template<typename _RandomAccessIterator, typename _Compare>
4850  inline void
4851  __stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last,
4852  _Compare __comp)
4853  {
4854  typedef typename iterator_traits<_RandomAccessIterator>::value_type
4855  _ValueType;
4856  typedef typename iterator_traits<_RandomAccessIterator>::difference_type
4857  _DistanceType;
4858 
4859  typedef _Temporary_buffer<_RandomAccessIterator, _ValueType> _TmpBuf;
4860  _TmpBuf __buf(__first, __last);
4861 
4862  if (__buf.begin() == 0)
4863  std::__inplace_stable_sort(__first, __last, __comp);
4864  else
4865  std::__stable_sort_adaptive(__first, __last, __buf.begin(),
4866  _DistanceType(__buf.size()), __comp);
4867  }
4868 
4869  /**
4870  * @brief Sort the elements of a sequence, preserving the relative order
4871  * of equivalent elements.
4872  * @ingroup sorting_algorithms
4873  * @param __first An iterator.
4874  * @param __last Another iterator.
4875  * @return Nothing.
4876  *
4877  * Sorts the elements in the range @p [__first,__last) in ascending order,
4878  * such that for each iterator @p i in the range @p [__first,__last-1),
4879  * @p *(i+1)<*i is false.
4880  *
4881  * The relative ordering of equivalent elements is preserved, so any two
4882  * elements @p x and @p y in the range @p [__first,__last) such that
4883  * @p x<y is false and @p y<x is false will have the same relative
4884  * ordering after calling @p stable_sort().
4885  */
4886  template<typename _RandomAccessIterator>
4887  inline void
4888  stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last)
4889  {
4890  // concept requirements
4891  __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
4892  _RandomAccessIterator>)
4893  __glibcxx_function_requires(_LessThanComparableConcept<
4894  typename iterator_traits<_RandomAccessIterator>::value_type>)
4895  __glibcxx_requires_valid_range(__first, __last);
4896 
4897  _GLIBCXX_STD_A::__stable_sort(__first, __last,
4898  __gnu_cxx::__ops::__iter_less_iter());
4899  }
4900 
4901  /**
4902  * @brief Sort the elements of a sequence using a predicate for comparison,
4903  * preserving the relative order of equivalent elements.
4904  * @ingroup sorting_algorithms
4905  * @param __first An iterator.
4906  * @param __last Another iterator.
4907  * @param __comp A comparison functor.
4908  * @return Nothing.
4909  *
4910  * Sorts the elements in the range @p [__first,__last) in ascending order,
4911  * such that for each iterator @p i in the range @p [__first,__last-1),
4912  * @p __comp(*(i+1),*i) is false.
4913  *
4914  * The relative ordering of equivalent elements is preserved, so any two
4915  * elements @p x and @p y in the range @p [__first,__last) such that
4916  * @p __comp(x,y) is false and @p __comp(y,x) is false will have the same
4917  * relative ordering after calling @p stable_sort().
4918  */
4919  template<typename _RandomAccessIterator, typename _Compare>
4920  inline void
4921  stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last,
4922  _Compare __comp)
4923  {
4924  // concept requirements
4925  __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
4926  _RandomAccessIterator>)
4927  __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
4928  typename iterator_traits<_RandomAccessIterator>::value_type,
4929  typename iterator_traits<_RandomAccessIterator>::value_type>)
4930  __glibcxx_requires_valid_range(__first, __last);
4931 
4932  _GLIBCXX_STD_A::__stable_sort(__first, __last,
4933  __gnu_cxx::__ops::__iter_comp_iter(__comp));
4934  }
4935 
4936  template<typename _InputIterator1, typename _InputIterator2,
4937  typename _OutputIterator,
4938  typename _Compare>
4939  _OutputIterator
4940  __set_union(_InputIterator1 __first1, _InputIterator1 __last1,
4941  _InputIterator2 __first2, _InputIterator2 __last2,
4942  _OutputIterator __result, _Compare __comp)
4943  {
4944  while (__first1 != __last1 && __first2 != __last2)
4945  {
4946  if (__comp(__first1, __first2))
4947  {
4948  *__result = *__first1;
4949  ++__first1;
4950  }
4951  else if (__comp(__first2, __first1))
4952  {
4953  *__result = *__first2;
4954  ++__first2;
4955  }
4956  else
4957  {
4958  *__result = *__first1;
4959  ++__first1;
4960  ++__first2;
4961  }
4962  ++__result;
4963  }
4964  return std::copy(__first2, __last2,
4965  std::copy(__first1, __last1, __result));
4966  }
4967 
4968  /**
4969  * @brief Return the union of two sorted ranges.
4970  * @ingroup set_algorithms
4971  * @param __first1 Start of first range.
4972  * @param __last1 End of first range.
4973  * @param __first2 Start of second range.
4974  * @param __last2 End of second range.
4975  * @return End of the output range.
4976  * @ingroup set_algorithms
4977  *
4978  * This operation iterates over both ranges, copying elements present in
4979  * each range in order to the output range. Iterators increment for each
4980  * range. When the current element of one range is less than the other,
4981  * that element is copied and the iterator advanced. If an element is
4982  * contained in both ranges, the element from the first range is copied and
4983  * both ranges advance. The output range may not overlap either input
4984  * range.
4985  */
4986  template<typename _InputIterator1, typename _InputIterator2,
4987  typename _OutputIterator>
4988  inline _OutputIterator
4989  set_union(_InputIterator1 __first1, _InputIterator1 __last1,
4990  _InputIterator2 __first2, _InputIterator2 __last2,
4991  _OutputIterator __result)
4992  {
4993  // concept requirements
4994  __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
4995  __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
4996  __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
4997  typename iterator_traits<_InputIterator1>::value_type>)
4998  __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
4999  typename iterator_traits<_InputIterator2>::value_type>)
5000  __glibcxx_function_requires(_LessThanOpConcept<
5001  typename iterator_traits<_InputIterator1>::value_type,
5002  typename iterator_traits<_InputIterator2>::value_type>)
5003  __glibcxx_function_requires(_LessThanOpConcept<
5004  typename iterator_traits<_InputIterator2>::value_type,
5005  typename iterator_traits<_InputIterator1>::value_type>)
5006  __glibcxx_requires_sorted_set(__first1, __last1, __first2);
5007  __glibcxx_requires_sorted_set(__first2, __last2, __first1);
5008 
5009  return _GLIBCXX_STD_A::__set_union(__first1, __last1,
5010  __first2, __last2, __result,
5011  __gnu_cxx::__ops::__iter_less_iter());
5012  }
5013 
5014  /**
5015  * @brief Return the union of two sorted ranges using a comparison functor.
5016  * @ingroup set_algorithms
5017  * @param __first1 Start of first range.
5018  * @param __last1 End of first range.
5019  * @param __first2 Start of second range.
5020  * @param __last2 End of second range.
5021  * @param __comp The comparison functor.
5022  * @return End of the output range.
5023  * @ingroup set_algorithms
5024  *
5025  * This operation iterates over both ranges, copying elements present in
5026  * each range in order to the output range. Iterators increment for each
5027  * range. When the current element of one range is less than the other
5028  * according to @p __comp, that element is copied and the iterator advanced.
5029  * If an equivalent element according to @p __comp is contained in both
5030  * ranges, the element from the first range is copied and both ranges
5031  * advance. The output range may not overlap either input range.
5032  */
5033  template<typename _InputIterator1, typename _InputIterator2,
5034  typename _OutputIterator, typename _Compare>
5035  inline _OutputIterator
5036  set_union(_InputIterator1 __first1, _InputIterator1 __last1,
5037  _InputIterator2 __first2, _InputIterator2 __last2,
5038  _OutputIterator __result, _Compare __comp)
5039  {
5040  // concept requirements
5041  __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
5042  __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
5043  __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5044  typename iterator_traits<_InputIterator1>::value_type>)
5045  __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5046  typename iterator_traits<_InputIterator2>::value_type>)
5047  __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5048  typename iterator_traits<_InputIterator1>::value_type,
5049  typename iterator_traits<_InputIterator2>::value_type>)
5050  __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5051  typename iterator_traits<_InputIterator2>::value_type,
5052  typename iterator_traits<_InputIterator1>::value_type>)
5053  __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp);
5054  __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp);
5055 
5056  return _GLIBCXX_STD_A::__set_union(__first1, __last1,
5057  __first2, __last2, __result,
5058  __gnu_cxx::__ops::__iter_comp_iter(__comp));
5059  }
5060 
5061  template<typename _InputIterator1, typename _InputIterator2,
5062  typename _OutputIterator,
5063  typename _Compare>
5064  _OutputIterator
5065  __set_intersection(_InputIterator1 __first1, _InputIterator1 __last1,
5066  _InputIterator2 __first2, _InputIterator2 __last2,
5067  _OutputIterator __result, _Compare __comp)
5068  {
5069  while (__first1 != __last1 && __first2 != __last2)
5070  if (__comp(__first1, __first2))
5071  ++__first1;
5072  else if (__comp(__first2, __first1))
5073  ++__first2;
5074  else
5075  {
5076  *__result = *__first1;
5077  ++__first1;
5078  ++__first2;
5079  ++__result;
5080  }
5081  return __result;
5082  }
5083 
5084  /**
5085  * @brief Return the intersection of two sorted ranges.
5086  * @ingroup set_algorithms
5087  * @param __first1 Start of first range.
5088  * @param __last1 End of first range.
5089  * @param __first2 Start of second range.
5090  * @param __last2 End of second range.
5091  * @return End of the output range.
5092  * @ingroup set_algorithms
5093  *
5094  * This operation iterates over both ranges, copying elements present in
5095  * both ranges in order to the output range. Iterators increment for each
5096  * range. When the current element of one range is less than the other,
5097  * that iterator advances. If an element is contained in both ranges, the
5098  * element from the first range is copied and both ranges advance. The
5099  * output range may not overlap either input range.
5100  */
5101  template<typename _InputIterator1, typename _InputIterator2,
5102  typename _OutputIterator>
5103  inline _OutputIterator
5104  set_intersection(_InputIterator1 __first1, _InputIterator1 __last1,
5105  _InputIterator2 __first2, _InputIterator2 __last2,
5106  _OutputIterator __result)
5107  {
5108  // concept requirements
5109  __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
5110  __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
5111  __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5112  typename iterator_traits<_InputIterator1>::value_type>)
5113  __glibcxx_function_requires(_LessThanOpConcept<
5114  typename iterator_traits<_InputIterator1>::value_type,
5115  typename iterator_traits<_InputIterator2>::value_type>)
5116  __glibcxx_function_requires(_LessThanOpConcept<
5117  typename iterator_traits<_InputIterator2>::value_type,
5118  typename iterator_traits<_InputIterator1>::value_type>)
5119  __glibcxx_requires_sorted_set(__first1, __last1, __first2);
5120  __glibcxx_requires_sorted_set(__first2, __last2, __first1);
5121 
5122  return _GLIBCXX_STD_A::__set_intersection(__first1, __last1,
5123  __first2, __last2, __result,
5124  __gnu_cxx::__ops::__iter_less_iter());
5125  }
5126 
5127  /**
5128  * @brief Return the intersection of two sorted ranges using comparison
5129  * functor.
5130  * @ingroup set_algorithms
5131  * @param __first1 Start of first range.
5132  * @param __last1 End of first range.
5133  * @param __first2 Start of second range.
5134  * @param __last2 End of second range.
5135  * @param __comp The comparison functor.
5136  * @return End of the output range.
5137  * @ingroup set_algorithms
5138  *
5139  * This operation iterates over both ranges, copying elements present in
5140  * both ranges in order to the output range. Iterators increment for each
5141  * range. When the current element of one range is less than the other
5142  * according to @p __comp, that iterator advances. If an element is
5143  * contained in both ranges according to @p __comp, the element from the
5144  * first range is copied and both ranges advance. The output range may not
5145  * overlap either input range.
5146  */
5147  template<typename _InputIterator1, typename _InputIterator2,
5148  typename _OutputIterator, typename _Compare>
5149  inline _OutputIterator
5150  set_intersection(_InputIterator1 __first1, _InputIterator1 __last1,
5151  _InputIterator2 __first2, _InputIterator2 __last2,
5152  _OutputIterator __result, _Compare __comp)
5153  {
5154  // concept requirements
5155  __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
5156  __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
5157  __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5158  typename iterator_traits<_InputIterator1>::value_type>)
5159  __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5160  typename iterator_traits<_InputIterator1>::value_type,
5161  typename iterator_traits<_InputIterator2>::value_type>)
5162  __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5163  typename iterator_traits<_InputIterator2>::value_type,
5164  typename iterator_traits<_InputIterator1>::value_type>)
5165  __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp);
5166  __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp);
5167 
5168  return _GLIBCXX_STD_A::__set_intersection(__first1, __last1,
5169  __first2, __last2, __result,
5170  __gnu_cxx::__ops::__iter_comp_iter(__comp));
5171  }
5172 
5173  template<typename _InputIterator1, typename _InputIterator2,
5174  typename _OutputIterator,
5175  typename _Compare>
5176  _OutputIterator
5177  __set_difference(_InputIterator1 __first1, _InputIterator1 __last1,
5178  _InputIterator2 __first2, _InputIterator2 __last2,
5179  _OutputIterator __result, _Compare __comp)
5180  {
5181  while (__first1 != __last1 && __first2 != __last2)
5182  if (__comp(__first1, __first2))
5183  {
5184  *__result = *__first1;
5185  ++__first1;
5186  ++__result;
5187  }
5188  else if (__comp(__first2, __first1))
5189  ++__first2;
5190  else
5191  {
5192  ++__first1;
5193  ++__first2;
5194  }
5195  return std::copy(__first1, __last1, __result);
5196  }
5197 
5198  /**
5199  * @brief Return the difference of two sorted ranges.
5200  * @ingroup set_algorithms
5201  * @param __first1 Start of first range.
5202  * @param __last1 End of first range.
5203  * @param __first2 Start of second range.
5204  * @param __last2 End of second range.
5205  * @return End of the output range.
5206  * @ingroup set_algorithms
5207  *
5208  * This operation iterates over both ranges, copying elements present in
5209  * the first range but not the second in order to the output range.
5210  * Iterators increment for each range. When the current element of the
5211  * first range is less than the second, that element is copied and the
5212  * iterator advances. If the current element of the second range is less,
5213  * the iterator advances, but no element is copied. If an element is
5214  * contained in both ranges, no elements are copied and both ranges
5215  * advance. The output range may not overlap either input range.
5216  */
5217  template<typename _InputIterator1, typename _InputIterator2,
5218  typename _OutputIterator>
5219  inline _OutputIterator
5220  set_difference(_InputIterator1 __first1, _InputIterator1 __last1,
5221  _InputIterator2 __first2, _InputIterator2 __last2,
5222  _OutputIterator __result)
5223  {
5224  // concept requirements
5225  __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
5226  __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
5227  __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5228  typename iterator_traits<_InputIterator1>::value_type>)
5229  __glibcxx_function_requires(_LessThanOpConcept<
5230  typename iterator_traits<_InputIterator1>::value_type,
5231  typename iterator_traits<_InputIterator2>::value_type>)
5232  __glibcxx_function_requires(_LessThanOpConcept<
5233  typename iterator_traits<_InputIterator2>::value_type,
5234  typename iterator_traits<_InputIterator1>::value_type>)
5235  __glibcxx_requires_sorted_set(__first1, __last1, __first2);
5236  __glibcxx_requires_sorted_set(__first2, __last2, __first1);
5237 
5238  return _GLIBCXX_STD_A::__set_difference(__first1, __last1,
5239  __first2, __last2, __result,
5240  __gnu_cxx::__ops::__iter_less_iter());
5241  }
5242 
5243  /**
5244  * @brief Return the difference of two sorted ranges using comparison
5245  * functor.
5246  * @ingroup set_algorithms
5247  * @param __first1 Start of first range.
5248  * @param __last1 End of first range.
5249  * @param __first2 Start of second range.
5250  * @param __last2 End of second range.
5251  * @param __comp The comparison functor.
5252  * @return End of the output range.
5253  * @ingroup set_algorithms
5254  *
5255  * This operation iterates over both ranges, copying elements present in
5256  * the first range but not the second in order to the output range.
5257  * Iterators increment for each range. When the current element of the
5258  * first range is less than the second according to @p __comp, that element
5259  * is copied and the iterator advances. If the current element of the
5260  * second range is less, no element is copied and the iterator advances.
5261  * If an element is contained in both ranges according to @p __comp, no
5262  * elements are copied and both ranges advance. The output range may not
5263  * overlap either input range.
5264  */
5265  template<typename _InputIterator1, typename _InputIterator2,
5266  typename _OutputIterator, typename _Compare>
5267  inline _OutputIterator
5268  set_difference(_InputIterator1 __first1, _InputIterator1 __last1,
5269  _InputIterator2 __first2, _InputIterator2 __last2,
5270  _OutputIterator __result, _Compare __comp)
5271  {
5272  // concept requirements
5273  __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
5274  __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
5275  __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5276  typename iterator_traits<_InputIterator1>::value_type>)
5277  __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5278  typename iterator_traits<_InputIterator1>::value_type,
5279  typename iterator_traits<_InputIterator2>::value_type>)
5280  __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5281  typename iterator_traits<_InputIterator2>::value_type,
5282  typename iterator_traits<_InputIterator1>::value_type>)
5283  __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp);
5284  __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp);
5285 
5286  return _GLIBCXX_STD_A::__set_difference(__first1, __last1,
5287  __first2, __last2, __result,
5288  __gnu_cxx::__ops::__iter_comp_iter(__comp));
5289  }
5290 
5291  template<typename _InputIterator1, typename _InputIterator2,
5292  typename _OutputIterator,
5293  typename _Compare>
5294  _OutputIterator
5295  __set_symmetric_difference(_InputIterator1 __first1,
5296  _InputIterator1 __last1,
5297  _InputIterator2 __first2,
5298  _InputIterator2 __last2,
5299  _OutputIterator __result,
5300  _Compare __comp)
5301  {
5302  while (__first1 != __last1 && __first2 != __last2)
5303  if (__comp(__first1, __first2))
5304  {
5305  *__result = *__first1;
5306  ++__first1;
5307  ++__result;
5308  }
5309  else if (__comp(__first2, __first1))
5310  {
5311  *__result = *__first2;
5312  ++__first2;
5313  ++__result;
5314  }
5315  else
5316  {
5317  ++__first1;
5318  ++__first2;
5319  }
5320  return std::copy(__first2, __last2,
5321  std::copy(__first1, __last1, __result));
5322  }
5323 
5324  /**
5325  * @brief Return the symmetric difference of two sorted ranges.
5326  * @ingroup set_algorithms
5327  * @param __first1 Start of first range.
5328  * @param __last1 End of first range.
5329  * @param __first2 Start of second range.
5330  * @param __last2 End of second range.
5331  * @return End of the output range.
5332  * @ingroup set_algorithms
5333  *
5334  * This operation iterates over both ranges, copying elements present in
5335  * one range but not the other in order to the output range. Iterators
5336  * increment for each range. When the current element of one range is less
5337  * than the other, that element is copied and the iterator advances. If an
5338  * element is contained in both ranges, no elements are copied and both
5339  * ranges advance. The output range may not overlap either input range.
5340  */
5341  template<typename _InputIterator1, typename _InputIterator2,
5342  typename _OutputIterator>
5343  inline _OutputIterator
5344  set_symmetric_difference(_InputIterator1 __first1, _InputIterator1 __last1,
5345  _InputIterator2 __first2, _InputIterator2 __last2,
5346  _OutputIterator __result)
5347  {
5348  // concept requirements
5349  __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
5350  __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
5351  __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5352  typename iterator_traits<_InputIterator1>::value_type>)
5353  __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5354  typename iterator_traits<_InputIterator2>::value_type>)
5355  __glibcxx_function_requires(_LessThanOpConcept<
5356  typename iterator_traits<_InputIterator1>::value_type,
5357  typename iterator_traits<_InputIterator2>::value_type>)
5358  __glibcxx_function_requires(_LessThanOpConcept<
5359  typename iterator_traits<_InputIterator2>::value_type,
5360  typename iterator_traits<_InputIterator1>::value_type>)
5361  __glibcxx_requires_sorted_set(__first1, __last1, __first2);
5362  __glibcxx_requires_sorted_set(__first2, __last2, __first1);
5363 
5364  return _GLIBCXX_STD_A::__set_symmetric_difference(__first1, __last1,
5365  __first2, __last2, __result,
5366  __gnu_cxx::__ops::__iter_less_iter());
5367  }
5368 
5369  /**
5370  * @brief Return the symmetric difference of two sorted ranges using
5371  * comparison functor.
5372  * @ingroup set_algorithms
5373  * @param __first1 Start of first range.
5374  * @param __last1 End of first range.
5375  * @param __first2 Start of second range.
5376  * @param __last2 End of second range.
5377  * @param __comp The comparison functor.
5378  * @return End of the output range.
5379  * @ingroup set_algorithms
5380  *
5381  * This operation iterates over both ranges, copying elements present in
5382  * one range but not the other in order to the output range. Iterators
5383  * increment for each range. When the current element of one range is less
5384  * than the other according to @p comp, that element is copied and the
5385  * iterator advances. If an element is contained in both ranges according
5386  * to @p __comp, no elements are copied and both ranges advance. The output
5387  * range may not overlap either input range.
5388  */
5389  template<typename _InputIterator1, typename _InputIterator2,
5390  typename _OutputIterator, typename _Compare>
5391  inline _OutputIterator
5392  set_symmetric_difference(_InputIterator1 __first1, _InputIterator1 __last1,
5393  _InputIterator2 __first2, _InputIterator2 __last2,
5394  _OutputIterator __result,
5395  _Compare __comp)
5396  {
5397  // concept requirements
5398  __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
5399  __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
5400  __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5401  typename iterator_traits<_InputIterator1>::value_type>)
5402  __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5403  typename iterator_traits<_InputIterator2>::value_type>)
5404  __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5405  typename iterator_traits<_InputIterator1>::value_type,
5406  typename iterator_traits<_InputIterator2>::value_type>)
5407  __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5408  typename iterator_traits<_InputIterator2>::value_type,
5409  typename iterator_traits<_InputIterator1>::value_type>)
5410  __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp);
5411  __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp);
5412 
5413  return _GLIBCXX_STD_A::__set_symmetric_difference(__first1, __last1,
5414  __first2, __last2, __result,
5415  __gnu_cxx::__ops::__iter_comp_iter(__comp));
5416  }
5417 
5418  template<typename _ForwardIterator, typename _Compare>
5419  _GLIBCXX14_CONSTEXPR
5420  _ForwardIterator
5421  __min_element(_ForwardIterator __first, _ForwardIterator __last,
5422  _Compare __comp)
5423  {
5424  if (__first == __last)
5425  return __first;
5426  _ForwardIterator __result = __first;
5427  while (++__first != __last)
5428  if (__comp(__first, __result))
5429  __result = __first;
5430  return __result;
5431  }
5432 
5433  /**
5434  * @brief Return the minimum element in a range.
5435  * @ingroup sorting_algorithms
5436  * @param __first Start of range.
5437  * @param __last End of range.
5438  * @return Iterator referencing the first instance of the smallest value.
5439  */
5440  template<typename _ForwardIterator>
5441  _GLIBCXX14_CONSTEXPR
5442  _ForwardIterator
5443  inline min_element(_ForwardIterator __first, _ForwardIterator __last)
5444  {
5445  // concept requirements
5446  __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
5447  __glibcxx_function_requires(_LessThanComparableConcept<
5448  typename iterator_traits<_ForwardIterator>::value_type>)
5449  __glibcxx_requires_valid_range(__first, __last);
5450 
5451  return _GLIBCXX_STD_A::__min_element(__first, __last,
5452  __gnu_cxx::__ops::__iter_less_iter());
5453  }
5454 
5455  /**
5456  * @brief Return the minimum element in a range using comparison functor.
5457  * @ingroup sorting_algorithms
5458  * @param __first Start of range.
5459  * @param __last End of range.
5460  * @param __comp Comparison functor.
5461  * @return Iterator referencing the first instance of the smallest value
5462  * according to __comp.
5463  */
5464  template<typename _ForwardIterator, typename _Compare>
5465  _GLIBCXX14_CONSTEXPR
5466  inline _ForwardIterator
5467  min_element(_ForwardIterator __first, _ForwardIterator __last,
5468  _Compare __comp)
5469  {
5470  // concept requirements
5471  __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
5472  __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5473  typename iterator_traits<_ForwardIterator>::value_type,
5474  typename iterator_traits<_ForwardIterator>::value_type>)
5475  __glibcxx_requires_valid_range(__first, __last);
5476 
5477  return _GLIBCXX_STD_A::__min_element(__first, __last,
5478  __gnu_cxx::__ops::__iter_comp_iter(__comp));
5479  }
5480 
5481  template<typename _ForwardIterator, typename _Compare>
5482  _GLIBCXX14_CONSTEXPR
5483  _ForwardIterator
5484  __max_element(_ForwardIterator __first, _ForwardIterator __last,
5485  _Compare __comp)
5486  {
5487  if (__first == __last) return __first;
5488  _ForwardIterator __result = __first;
5489  while (++__first != __last)
5490  if (__comp(__result, __first))
5491  __result = __first;
5492  return __result;
5493  }
5494 
5495  /**
5496  * @brief Return the maximum element in a range.
5497  * @ingroup sorting_algorithms
5498  * @param __first Start of range.
5499  * @param __last End of range.
5500  * @return Iterator referencing the first instance of the largest value.
5501  */
5502  template<typename _ForwardIterator>
5503  _GLIBCXX14_CONSTEXPR
5504  inline _ForwardIterator
5505  max_element(_ForwardIterator __first, _ForwardIterator __last)
5506  {
5507  // concept requirements
5508  __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
5509  __glibcxx_function_requires(_LessThanComparableConcept<
5510  typename iterator_traits<_ForwardIterator>::value_type>)
5511  __glibcxx_requires_valid_range(__first, __last);
5512 
5513  return _GLIBCXX_STD_A::__max_element(__first, __last,
5514  __gnu_cxx::__ops::__iter_less_iter());
5515  }
5516 
5517  /**
5518  * @brief Return the maximum element in a range using comparison functor.
5519  * @ingroup sorting_algorithms
5520  * @param __first Start of range.
5521  * @param __last End of range.
5522  * @param __comp Comparison functor.
5523  * @return Iterator referencing the first instance of the largest value
5524  * according to __comp.
5525  */
5526  template<typename _ForwardIterator, typename _Compare>
5527  _GLIBCXX14_CONSTEXPR
5528  inline _ForwardIterator
5529  max_element(_ForwardIterator __first, _ForwardIterator __last,
5530  _Compare __comp)
5531  {
5532  // concept requirements
5533  __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
5534  __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5535  typename iterator_traits<_ForwardIterator>::value_type,
5536  typename iterator_traits<_ForwardIterator>::value_type>)
5537  __glibcxx_requires_valid_range(__first, __last);
5538 
5539  return _GLIBCXX_STD_A::__max_element(__first, __last,
5540  __gnu_cxx::__ops::__iter_comp_iter(__comp));
5541  }
5542 
5543 _GLIBCXX_END_NAMESPACE_ALGO
5544 } // namespace std
5545 
5546 #endif /* _STL_ALGO_H */
void swap(_Tp &, _Tp &) noexcept(__and_< is_nothrow_move_constructible< _Tp >, is_nothrow_move_assignable< _Tp >>::value)
Swaps two values.
Definition: move.h:176
constexpr int __lg(int __n)
This is a helper function for the sort routines and for random.tcc.
void iter_swap(_ForwardIterator1 __a, _ForwardIterator2 __b)
Swaps the contents of two iterators.
Definition: stl_algobase.h:120
_RandomAccessIterator __unguarded_partition(_RandomAccessIterator __first, _RandomAccessIterator __last, _RandomAccessIterator __pivot, _Compare __comp)
This is a helper function...
Definition: stl_algo.h:1891
_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
void __unguarded_insertion_sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
This is a helper function for the sort routine.
Definition: stl_algo.h:1858
void __merge_without_buffer(_BidirectionalIterator __first, _BidirectionalIterator __middle, _BidirectionalIterator __last, _Distance __len1, _Distance __len2, _Compare __comp)
This is a helper function for the merge routines.
Definition: stl_algo.h:2488
_ForwardIterator __search_n_aux(_ForwardIterator __first, _ForwardIterator __last, _Integer __count, _UnaryPredicate __unary_pred, std::forward_iterator_tag)
Definition: stl_algo.h:257
void advance(_InputIterator &__i, _Distance __n)
A generalization of pointer arithmetic.
_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:1546
_ForwardIterator2 swap_ranges(_ForwardIterator1 __first1, _ForwardIterator1 __last1, _ForwardIterator2 __first2)
Swap the elements of two sequences.
Definition: stl_algobase.h:166
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:1935
Forward iterators support a superset of input iterator operations.
Marking output iterators.
_ForwardIterator rotate(_ForwardIterator __first, _ForwardIterator __middle, _ForwardIterator __last)
Rotate the elements of a sequence.
Definition: stl_algo.h:1431
void __heap_select(_RandomAccessIterator __first, _RandomAccessIterator __middle, _RandomAccessIterator __last, _Compare __comp)
This is a helper function for the sort routines.
Definition: stl_algo.h:1665
_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:2385
_GLIBCXX14_CONSTEXPR pair< _ForwardIterator, _ForwardIterator > minmax_element(_ForwardIterator __first, _ForwardIterator __last, _Compare __comp)
Return a pair of iterators pointing to the minimum and maximum elements in a range.
Definition: stl_algo.h:3427
void __merge_adaptive(_BidirectionalIterator __first, _BidirectionalIterator __middle, _BidirectionalIterator __last, _Distance __len1, _Distance __len2, _Pointer __buffer, _Distance __buffer_size, _Compare __comp)
This is a helper function for the merge routines.
Definition: stl_algo.h:2427
_RandomAccessIterator __unguarded_partition_pivot(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
This is a helper function...
Definition: stl_algo.h:1912
_GLIBCXX14_CONSTEXPR const _Tp & max(const _Tp &, const _Tp &)
This does what you think it does.
Definition: stl_algobase.h:219
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:2342
_GLIBCXX14_CONSTEXPR const _Tp & min(const _Tp &, const _Tp &)
This does what you think it does.
Definition: stl_algobase.h:195
_OutputIterator __unique_copy(_ForwardIterator __first, _ForwardIterator __last, _OutputIterator __result, _BinaryPredicate __binary_pred, forward_iterator_tag, output_iterator_tag)
Definition: stl_algo.h:1046
void __unguarded_linear_insert(_RandomAccessIterator __last, _Compare __comp)
This is a helper function for the sort routine.
Definition: stl_algo.h:1816
_ForwardIterator __partition(_ForwardIterator __first, _ForwardIterator __last, _Predicate __pred, forward_iterator_tag)
This is a helper function...
Definition: stl_algo.h:1485
_InputIterator __find_if_not(_InputIterator __first, _InputIterator __last, _Predicate __pred)
Provided for stable_partition to use.
Definition: stl_algo.h:168
_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
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
_EuclideanRingElement __gcd(_EuclideanRingElement __m, _EuclideanRingElement __n)
Definition: stl_algo.h:1229
_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
_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:3806
_GLIBCXX14_CONSTEXPR pair< const _Tp &, const _Tp & > minmax(const _Tp &, const _Tp &)
Determines min and max at once as an ordered pair.
Definition: stl_algo.h:3299
Marking input iterators.
_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
iterator_traits< _Iter >::iterator_category __iterator_category(const _Iter &)
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:2316
Struct holding two objects of arbitrary type.
Definition: stl_pair.h:96
_GLIBCXX14_CONSTEXPR _ForwardIterator min_element(_ForwardIterator __first, _ForwardIterator __last, _Compare __comp)
Return the minimum element in a range using comparison functor.
Definition: stl_algo.h:5467
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
iterator_traits< _InputIterator >::difference_type distance(_InputIterator __first, _InputIterator __last)
A generalization of pointer arithmetic.
Random-access iterators support a superset of bidirectional iterator operations.
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
Bidirectional iterators support a superset of forward iterator operations.
void __reverse(_BidirectionalIterator __first, _BidirectionalIterator __last, bidirectional_iterator_tag)
Definition: stl_algo.h:1129
_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
Uniform discrete distribution for random numbers. A discrete random distribution on the range with e...
Definition: random.h:1665
void __insertion_sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
This is a helper function for the sort routine.
Definition: stl_algo.h:1835
_GLIBCXX14_CONSTEXPR _ForwardIterator max_element(_ForwardIterator __first, _ForwardIterator __last, _Compare __comp)
Return the maximum element in a range using comparison functor.
Definition: stl_algo.h:5529
ISO C++ entities toplevel namespace is std.
void __final_insertion_sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
This is a helper function for the sort routine.
Definition: stl_algo.h:1875
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