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