STLdoc
STLdocumentation
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
stl_algo.h
Go to the documentation of this file.
1 // Algorithm implementation -*- C++ -*-
2 
3 // Copyright (C) 2001-2013 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 
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 
64 #if __cplusplus >= 201103L
65 #include <random> // for std::uniform_int_distribution
66 #include <functional> // for std::bind
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 
76  template<typename _Iterator>
77  void
78  __move_median_to_first(_Iterator __result, _Iterator __a,
79  _Iterator __b, _Iterator __c)
80  {
81  // concept requirements
82  __glibcxx_function_requires(_LessThanComparableConcept<
83  typename iterator_traits<_Iterator>::value_type>)
84 
85  if (*__a < *__b)
86  {
87  if (*__b < *__c)
88  std::iter_swap(__result, __b);
89  else if (*__a < *__c)
90  std::iter_swap(__result, __c);
91  else
92  std::iter_swap(__result, __a);
93  }
94  else if (*__a < *__c)
95  std::iter_swap(__result, __a);
96  else if (*__b < *__c)
97  std::iter_swap(__result, __c);
98  else
99  std::iter_swap(__result, __b);
100  }
101 
103  template<typename _Iterator, typename _Compare>
104  void
105  __move_median_to_first(_Iterator __result, _Iterator __a,
106  _Iterator __b, _Iterator __c,
107  _Compare __comp)
108  {
109  // concept requirements
110  __glibcxx_function_requires(_BinaryFunctionConcept<_Compare, bool,
111  typename iterator_traits<_Iterator>::value_type,
112  typename iterator_traits<_Iterator>::value_type>)
113 
114  if (__comp(*__a, *__b))
115  {
116  if (__comp(*__b, *__c))
117  std::iter_swap(__result, __b);
118  else if (__comp(*__a, *__c))
119  std::iter_swap(__result, __c);
120  else
121  std::iter_swap(__result, __a);
122  }
123  else if (__comp(*__a, *__c))
124  std::iter_swap(__result, __a);
125  else if (__comp(*__b, *__c))
126  std::iter_swap(__result, __c);
127  else
128  std::iter_swap(__result, __b);
129  }
130 
131  // for_each
132 
134  template<typename _InputIterator, typename _Tp>
135  inline _InputIterator
136  __find(_InputIterator __first, _InputIterator __last,
137  const _Tp& __val, input_iterator_tag)
138  {
139  while (__first != __last && !(*__first == __val))
140  ++__first;
141  return __first;
142  }
143 
145  template<typename _InputIterator, typename _Predicate>
146  inline _InputIterator
147  __find_if(_InputIterator __first, _InputIterator __last,
148  _Predicate __pred, input_iterator_tag)
149  {
150  while (__first != __last && !bool(__pred(*__first)))
151  ++__first;
152  return __first;
153  }
154 
156  template<typename _RandomAccessIterator, typename _Tp>
157  _RandomAccessIterator
158  __find(_RandomAccessIterator __first, _RandomAccessIterator __last,
159  const _Tp& __val, random_access_iterator_tag)
160  {
161  typename iterator_traits<_RandomAccessIterator>::difference_type
162  __trip_count = (__last - __first) >> 2;
163 
164  for (; __trip_count > 0; --__trip_count)
165  {
166  if (*__first == __val)
167  return __first;
168  ++__first;
169 
170  if (*__first == __val)
171  return __first;
172  ++__first;
173 
174  if (*__first == __val)
175  return __first;
176  ++__first;
177 
178  if (*__first == __val)
179  return __first;
180  ++__first;
181  }
182 
183  switch (__last - __first)
184  {
185  case 3:
186  if (*__first == __val)
187  return __first;
188  ++__first;
189  case 2:
190  if (*__first == __val)
191  return __first;
192  ++__first;
193  case 1:
194  if (*__first == __val)
195  return __first;
196  ++__first;
197  case 0:
198  default:
199  return __last;
200  }
201  }
202 
204  template<typename _RandomAccessIterator, typename _Predicate>
205  _RandomAccessIterator
206  __find_if(_RandomAccessIterator __first, _RandomAccessIterator __last,
207  _Predicate __pred, random_access_iterator_tag)
208  {
209  typename iterator_traits<_RandomAccessIterator>::difference_type
210  __trip_count = (__last - __first) >> 2;
211 
212  for (; __trip_count > 0; --__trip_count)
213  {
214  if (__pred(*__first))
215  return __first;
216  ++__first;
217 
218  if (__pred(*__first))
219  return __first;
220  ++__first;
221 
222  if (__pred(*__first))
223  return __first;
224  ++__first;
225 
226  if (__pred(*__first))
227  return __first;
228  ++__first;
229  }
230 
231  switch (__last - __first)
232  {
233  case 3:
234  if (__pred(*__first))
235  return __first;
236  ++__first;
237  case 2:
238  if (__pred(*__first))
239  return __first;
240  ++__first;
241  case 1:
242  if (__pred(*__first))
243  return __first;
244  ++__first;
245  case 0:
246  default:
247  return __last;
248  }
249  }
250 
252  template<typename _InputIterator, typename _Predicate>
253  inline _InputIterator
254  __find_if_not(_InputIterator __first, _InputIterator __last,
255  _Predicate __pred, input_iterator_tag)
256  {
257  while (__first != __last && bool(__pred(*__first)))
258  ++__first;
259  return __first;
260  }
261 
263  template<typename _RandomAccessIterator, typename _Predicate>
264  _RandomAccessIterator
265  __find_if_not(_RandomAccessIterator __first, _RandomAccessIterator __last,
266  _Predicate __pred, random_access_iterator_tag)
267  {
268  typename iterator_traits<_RandomAccessIterator>::difference_type
269  __trip_count = (__last - __first) >> 2;
270 
271  for (; __trip_count > 0; --__trip_count)
272  {
273  if (!bool(__pred(*__first)))
274  return __first;
275  ++__first;
276 
277  if (!bool(__pred(*__first)))
278  return __first;
279  ++__first;
280 
281  if (!bool(__pred(*__first)))
282  return __first;
283  ++__first;
284 
285  if (!bool(__pred(*__first)))
286  return __first;
287  ++__first;
288  }
289 
290  switch (__last - __first)
291  {
292  case 3:
293  if (!bool(__pred(*__first)))
294  return __first;
295  ++__first;
296  case 2:
297  if (!bool(__pred(*__first)))
298  return __first;
299  ++__first;
300  case 1:
301  if (!bool(__pred(*__first)))
302  return __first;
303  ++__first;
304  case 0:
305  default:
306  return __last;
307  }
308  }
309 
311  template<typename _InputIterator, typename _Predicate>
312  inline _InputIterator
313  __find_if_not(_InputIterator __first, _InputIterator __last,
314  _Predicate __pred)
315  {
316  return std::__find_if_not(__first, __last, __pred,
317  std::__iterator_category(__first));
318  }
319 
323  template<typename _InputIterator, typename _Predicate, typename _Distance>
324  _InputIterator
325  __find_if_not_n(_InputIterator __first, _Distance& __len, _Predicate __pred)
326  {
327  for (; __len; --__len, ++__first)
328  if (!bool(__pred(*__first)))
329  break;
330  return __first;
331  }
332 
333  // set_difference
334  // set_intersection
335  // set_symmetric_difference
336  // set_union
337  // for_each
338  // find
339  // find_if
340  // find_first_of
341  // adjacent_find
342  // count
343  // count_if
344  // search
345 
351  template<typename _ForwardIterator, typename _Integer, typename _Tp>
352  _ForwardIterator
353  __search_n(_ForwardIterator __first, _ForwardIterator __last,
354  _Integer __count, const _Tp& __val,
355  std::forward_iterator_tag)
356  {
357  __first = _GLIBCXX_STD_A::find(__first, __last, __val);
358  while (__first != __last)
359  {
360  typename iterator_traits<_ForwardIterator>::difference_type
361  __n = __count;
362  _ForwardIterator __i = __first;
363  ++__i;
364  while (__i != __last && __n != 1 && *__i == __val)
365  {
366  ++__i;
367  --__n;
368  }
369  if (__n == 1)
370  return __first;
371  if (__i == __last)
372  return __last;
373  __first = _GLIBCXX_STD_A::find(++__i, __last, __val);
374  }
375  return __last;
376  }
377 
383  template<typename _RandomAccessIter, typename _Integer, typename _Tp>
384  _RandomAccessIter
385  __search_n(_RandomAccessIter __first, _RandomAccessIter __last,
386  _Integer __count, const _Tp& __val,
387  std::random_access_iterator_tag)
388  {
389 
390  typedef typename std::iterator_traits<_RandomAccessIter>::difference_type
391  _DistanceType;
392 
393  _DistanceType __tailSize = __last - __first;
394  _DistanceType __remainder = __count;
395 
396  while (__remainder <= __tailSize) // the main loop...
397  {
398  __first += __remainder;
399  __tailSize -= __remainder;
400  // __first here is always pointing to one past the last element of
401  // next possible match.
402  _RandomAccessIter __backTrack = __first;
403  while (*--__backTrack == __val)
404  {
405  if (--__remainder == 0)
406  return (__first - __count); // Success
407  }
408  __remainder = __count + 1 - (__first - __backTrack);
409  }
410  return __last; // Failure
411  }
412 
413  // search_n
414 
421  template<typename _ForwardIterator, typename _Integer, typename _Tp,
422  typename _BinaryPredicate>
423  _ForwardIterator
424  __search_n(_ForwardIterator __first, _ForwardIterator __last,
425  _Integer __count, const _Tp& __val,
426  _BinaryPredicate __binary_pred, std::forward_iterator_tag)
427  {
428  while (__first != __last && !bool(__binary_pred(*__first, __val)))
429  ++__first;
430 
431  while (__first != __last)
432  {
433  typename iterator_traits<_ForwardIterator>::difference_type
434  __n = __count;
435  _ForwardIterator __i = __first;
436  ++__i;
437  while (__i != __last && __n != 1 && bool(__binary_pred(*__i, __val)))
438  {
439  ++__i;
440  --__n;
441  }
442  if (__n == 1)
443  return __first;
444  if (__i == __last)
445  return __last;
446  __first = ++__i;
447  while (__first != __last
448  && !bool(__binary_pred(*__first, __val)))
449  ++__first;
450  }
451  return __last;
452  }
453 
460  template<typename _RandomAccessIter, typename _Integer, typename _Tp,
461  typename _BinaryPredicate>
462  _RandomAccessIter
463  __search_n(_RandomAccessIter __first, _RandomAccessIter __last,
464  _Integer __count, const _Tp& __val,
465  _BinaryPredicate __binary_pred, std::random_access_iterator_tag)
466  {
467 
468  typedef typename std::iterator_traits<_RandomAccessIter>::difference_type
469  _DistanceType;
470 
471  _DistanceType __tailSize = __last - __first;
472  _DistanceType __remainder = __count;
473 
474  while (__remainder <= __tailSize) // the main loop...
475  {
476  __first += __remainder;
477  __tailSize -= __remainder;
478  // __first here is always pointing to one past the last element of
479  // next possible match.
480  _RandomAccessIter __backTrack = __first;
481  while (__binary_pred(*--__backTrack, __val))
482  {
483  if (--__remainder == 0)
484  return (__first - __count); // Success
485  }
486  __remainder = __count + 1 - (__first - __backTrack);
487  }
488  return __last; // Failure
489  }
490 
491  // find_end for forward iterators.
492  template<typename _ForwardIterator1, typename _ForwardIterator2>
493  _ForwardIterator1
494  __find_end(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
495  _ForwardIterator2 __first2, _ForwardIterator2 __last2,
496  forward_iterator_tag, forward_iterator_tag)
497  {
498  if (__first2 == __last2)
499  return __last1;
500  else
501  {
502  _ForwardIterator1 __result = __last1;
503  while (1)
504  {
505  _ForwardIterator1 __new_result
506  = _GLIBCXX_STD_A::search(__first1, __last1, __first2, __last2);
507  if (__new_result == __last1)
508  return __result;
509  else
510  {
511  __result = __new_result;
512  __first1 = __new_result;
513  ++__first1;
514  }
515  }
516  }
517  }
518 
519  template<typename _ForwardIterator1, typename _ForwardIterator2,
520  typename _BinaryPredicate>
521  _ForwardIterator1
522  __find_end(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
523  _ForwardIterator2 __first2, _ForwardIterator2 __last2,
524  forward_iterator_tag, forward_iterator_tag,
525  _BinaryPredicate __comp)
526  {
527  if (__first2 == __last2)
528  return __last1;
529  else
530  {
531  _ForwardIterator1 __result = __last1;
532  while (1)
533  {
534  _ForwardIterator1 __new_result
535  = _GLIBCXX_STD_A::search(__first1, __last1, __first2,
536  __last2, __comp);
537  if (__new_result == __last1)
538  return __result;
539  else
540  {
541  __result = __new_result;
542  __first1 = __new_result;
543  ++__first1;
544  }
545  }
546  }
547  }
548 
549  // find_end for bidirectional iterators (much faster).
550  template<typename _BidirectionalIterator1, typename _BidirectionalIterator2>
551  _BidirectionalIterator1
552  __find_end(_BidirectionalIterator1 __first1,
553  _BidirectionalIterator1 __last1,
554  _BidirectionalIterator2 __first2,
555  _BidirectionalIterator2 __last2,
556  bidirectional_iterator_tag, bidirectional_iterator_tag)
557  {
558  // concept requirements
559  __glibcxx_function_requires(_BidirectionalIteratorConcept<
560  _BidirectionalIterator1>)
561  __glibcxx_function_requires(_BidirectionalIteratorConcept<
562  _BidirectionalIterator2>)
563 
564  typedef reverse_iterator<_BidirectionalIterator1> _RevIterator1;
565  typedef reverse_iterator<_BidirectionalIterator2> _RevIterator2;
566 
567  _RevIterator1 __rlast1(__first1);
568  _RevIterator2 __rlast2(__first2);
569  _RevIterator1 __rresult = _GLIBCXX_STD_A::search(_RevIterator1(__last1),
570  __rlast1,
571  _RevIterator2(__last2),
572  __rlast2);
573 
574  if (__rresult == __rlast1)
575  return __last1;
576  else
577  {
578  _BidirectionalIterator1 __result = __rresult.base();
579  std::advance(__result, -std::distance(__first2, __last2));
580  return __result;
581  }
582  }
583 
584  template<typename _BidirectionalIterator1, typename _BidirectionalIterator2,
585  typename _BinaryPredicate>
586  _BidirectionalIterator1
587  __find_end(_BidirectionalIterator1 __first1,
588  _BidirectionalIterator1 __last1,
589  _BidirectionalIterator2 __first2,
590  _BidirectionalIterator2 __last2,
591  bidirectional_iterator_tag, bidirectional_iterator_tag,
592  _BinaryPredicate __comp)
593  {
594  // concept requirements
595  __glibcxx_function_requires(_BidirectionalIteratorConcept<
596  _BidirectionalIterator1>)
597  __glibcxx_function_requires(_BidirectionalIteratorConcept<
598  _BidirectionalIterator2>)
599 
600  typedef reverse_iterator<_BidirectionalIterator1> _RevIterator1;
601  typedef reverse_iterator<_BidirectionalIterator2> _RevIterator2;
602 
603  _RevIterator1 __rlast1(__first1);
604  _RevIterator2 __rlast2(__first2);
605  _RevIterator1 __rresult = std::search(_RevIterator1(__last1), __rlast1,
606  _RevIterator2(__last2), __rlast2,
607  __comp);
608 
609  if (__rresult == __rlast1)
610  return __last1;
611  else
612  {
613  _BidirectionalIterator1 __result = __rresult.base();
614  std::advance(__result, -std::distance(__first2, __last2));
615  return __result;
616  }
617  }
618 
645  template<typename _ForwardIterator1, typename _ForwardIterator2>
646  inline _ForwardIterator1
647  find_end(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
648  _ForwardIterator2 __first2, _ForwardIterator2 __last2)
649  {
650  // concept requirements
651  __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator1>)
652  __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator2>)
653  __glibcxx_function_requires(_EqualOpConcept<
654  typename iterator_traits<_ForwardIterator1>::value_type,
655  typename iterator_traits<_ForwardIterator2>::value_type>)
656  __glibcxx_requires_valid_range(__first1, __last1);
657  __glibcxx_requires_valid_range(__first2, __last2);
658 
659  return std::__find_end(__first1, __last1, __first2, __last2,
660  std::__iterator_category(__first1),
661  std::__iterator_category(__first2));
662  }
663 
692  template<typename _ForwardIterator1, typename _ForwardIterator2,
693  typename _BinaryPredicate>
694  inline _ForwardIterator1
695  find_end(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
696  _ForwardIterator2 __first2, _ForwardIterator2 __last2,
697  _BinaryPredicate __comp)
698  {
699  // concept requirements
700  __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator1>)
701  __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator2>)
702  __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
703  typename iterator_traits<_ForwardIterator1>::value_type,
704  typename iterator_traits<_ForwardIterator2>::value_type>)
705  __glibcxx_requires_valid_range(__first1, __last1);
706  __glibcxx_requires_valid_range(__first2, __last2);
707 
708  return std::__find_end(__first1, __last1, __first2, __last2,
709  std::__iterator_category(__first1),
710  std::__iterator_category(__first2),
711  __comp);
712  }
713 
714 #if __cplusplus >= 201103L
715 
727  template<typename _InputIterator, typename _Predicate>
728  inline bool
729  all_of(_InputIterator __first, _InputIterator __last, _Predicate __pred)
730  { return __last == std::find_if_not(__first, __last, __pred); }
731 
744  template<typename _InputIterator, typename _Predicate>
745  inline bool
746  none_of(_InputIterator __first, _InputIterator __last, _Predicate __pred)
747  { return __last == _GLIBCXX_STD_A::find_if(__first, __last, __pred); }
748 
762  template<typename _InputIterator, typename _Predicate>
763  inline bool
764  any_of(_InputIterator __first, _InputIterator __last, _Predicate __pred)
765  { return !std::none_of(__first, __last, __pred); }
766 
777  template<typename _InputIterator, typename _Predicate>
778  inline _InputIterator
779  find_if_not(_InputIterator __first, _InputIterator __last,
780  _Predicate __pred)
781  {
782  // concept requirements
783  __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
784  __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
785  typename iterator_traits<_InputIterator>::value_type>)
786  __glibcxx_requires_valid_range(__first, __last);
787  return std::__find_if_not(__first, __last, __pred);
788  }
789 
800  template<typename _InputIterator, typename _Predicate>
801  inline bool
802  is_partitioned(_InputIterator __first, _InputIterator __last,
803  _Predicate __pred)
804  {
805  __first = std::find_if_not(__first, __last, __pred);
806  return std::none_of(__first, __last, __pred);
807  }
808 
818  template<typename _ForwardIterator, typename _Predicate>
819  _ForwardIterator
820  partition_point(_ForwardIterator __first, _ForwardIterator __last,
821  _Predicate __pred)
822  {
823  // concept requirements
824  __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
825  __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
826  typename iterator_traits<_ForwardIterator>::value_type>)
827 
828  // A specific debug-mode test will be necessary...
829  __glibcxx_requires_valid_range(__first, __last);
830 
831  typedef typename iterator_traits<_ForwardIterator>::difference_type
832  _DistanceType;
833 
834  _DistanceType __len = std::distance(__first, __last);
835  _DistanceType __half;
836  _ForwardIterator __middle;
837 
838  while (__len > 0)
839  {
840  __half = __len >> 1;
841  __middle = __first;
842  std::advance(__middle, __half);
843  if (__pred(*__middle))
844  {
845  __first = __middle;
846  ++__first;
847  __len = __len - __half - 1;
848  }
849  else
850  __len = __half;
851  }
852  return __first;
853  }
854 #endif
855 
856 
871  template<typename _InputIterator, typename _OutputIterator, typename _Tp>
872  _OutputIterator
873  remove_copy(_InputIterator __first, _InputIterator __last,
874  _OutputIterator __result, const _Tp& __value)
875  {
876  // concept requirements
877  __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
878  __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
879  typename iterator_traits<_InputIterator>::value_type>)
880  __glibcxx_function_requires(_EqualOpConcept<
881  typename iterator_traits<_InputIterator>::value_type, _Tp>)
882  __glibcxx_requires_valid_range(__first, __last);
883 
884  for (; __first != __last; ++__first)
885  if (!(*__first == __value))
886  {
887  *__result = *__first;
888  ++__result;
889  }
890  return __result;
891  }
892 
908  template<typename _InputIterator, typename _OutputIterator,
909  typename _Predicate>
910  _OutputIterator
911  remove_copy_if(_InputIterator __first, _InputIterator __last,
912  _OutputIterator __result, _Predicate __pred)
913  {
914  // concept requirements
915  __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
916  __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
917  typename iterator_traits<_InputIterator>::value_type>)
918  __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
919  typename iterator_traits<_InputIterator>::value_type>)
920  __glibcxx_requires_valid_range(__first, __last);
921 
922  for (; __first != __last; ++__first)
923  if (!bool(__pred(*__first)))
924  {
925  *__result = *__first;
926  ++__result;
927  }
928  return __result;
929  }
930 
931 #if __cplusplus >= 201103L
932 
947  template<typename _InputIterator, typename _OutputIterator,
948  typename _Predicate>
949  _OutputIterator
950  copy_if(_InputIterator __first, _InputIterator __last,
951  _OutputIterator __result, _Predicate __pred)
952  {
953  // concept requirements
954  __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
955  __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
956  typename iterator_traits<_InputIterator>::value_type>)
957  __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
958  typename iterator_traits<_InputIterator>::value_type>)
959  __glibcxx_requires_valid_range(__first, __last);
960 
961  for (; __first != __last; ++__first)
962  if (__pred(*__first))
963  {
964  *__result = *__first;
965  ++__result;
966  }
967  return __result;
968  }
969 
970 
971  template<typename _InputIterator, typename _Size, typename _OutputIterator>
972  _OutputIterator
973  __copy_n(_InputIterator __first, _Size __n,
974  _OutputIterator __result, input_iterator_tag)
975  {
976  if (__n > 0)
977  {
978  while (true)
979  {
980  *__result = *__first;
981  ++__result;
982  if (--__n > 0)
983  ++__first;
984  else
985  break;
986  }
987  }
988  return __result;
989  }
990 
991  template<typename _RandomAccessIterator, typename _Size,
992  typename _OutputIterator>
993  inline _OutputIterator
994  __copy_n(_RandomAccessIterator __first, _Size __n,
995  _OutputIterator __result, random_access_iterator_tag)
996  { return std::copy(__first, __first + __n, __result); }
997 
1011  template<typename _InputIterator, typename _Size, typename _OutputIterator>
1012  inline _OutputIterator
1013  copy_n(_InputIterator __first, _Size __n, _OutputIterator __result)
1014  {
1015  // concept requirements
1016  __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
1017  __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
1018  typename iterator_traits<_InputIterator>::value_type>)
1019 
1020  return std::__copy_n(__first, __n, __result,
1021  std::__iterator_category(__first));
1022  }
1023 
1039  template<typename _InputIterator, typename _OutputIterator1,
1040  typename _OutputIterator2, typename _Predicate>
1041  pair<_OutputIterator1, _OutputIterator2>
1042  partition_copy(_InputIterator __first, _InputIterator __last,
1043  _OutputIterator1 __out_true, _OutputIterator2 __out_false,
1044  _Predicate __pred)
1045  {
1046  // concept requirements
1047  __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
1048  __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator1,
1049  typename iterator_traits<_InputIterator>::value_type>)
1050  __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator2,
1051  typename iterator_traits<_InputIterator>::value_type>)
1052  __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
1053  typename iterator_traits<_InputIterator>::value_type>)
1054  __glibcxx_requires_valid_range(__first, __last);
1055 
1056  for (; __first != __last; ++__first)
1057  if (__pred(*__first))
1058  {
1059  *__out_true = *__first;
1060  ++__out_true;
1061  }
1062  else
1063  {
1064  *__out_false = *__first;
1065  ++__out_false;
1066  }
1067 
1068  return pair<_OutputIterator1, _OutputIterator2>(__out_true, __out_false);
1069  }
1070 #endif
1071 
1089  template<typename _ForwardIterator, typename _Tp>
1090  _ForwardIterator
1091  remove(_ForwardIterator __first, _ForwardIterator __last,
1092  const _Tp& __value)
1093  {
1094  // concept requirements
1095  __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
1096  _ForwardIterator>)
1097  __glibcxx_function_requires(_EqualOpConcept<
1098  typename iterator_traits<_ForwardIterator>::value_type, _Tp>)
1099  __glibcxx_requires_valid_range(__first, __last);
1100 
1101  __first = _GLIBCXX_STD_A::find(__first, __last, __value);
1102  if(__first == __last)
1103  return __first;
1104  _ForwardIterator __result = __first;
1105  ++__first;
1106  for(; __first != __last; ++__first)
1107  if(!(*__first == __value))
1108  {
1109  *__result = _GLIBCXX_MOVE(*__first);
1110  ++__result;
1111  }
1112  return __result;
1113  }
1114 
1132  template<typename _ForwardIterator, typename _Predicate>
1133  _ForwardIterator
1134  remove_if(_ForwardIterator __first, _ForwardIterator __last,
1135  _Predicate __pred)
1136  {
1137  // concept requirements
1138  __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
1139  _ForwardIterator>)
1140  __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
1141  typename iterator_traits<_ForwardIterator>::value_type>)
1142  __glibcxx_requires_valid_range(__first, __last);
1143 
1144  __first = _GLIBCXX_STD_A::find_if(__first, __last, __pred);
1145  if(__first == __last)
1146  return __first;
1147  _ForwardIterator __result = __first;
1148  ++__first;
1149  for(; __first != __last; ++__first)
1150  if(!bool(__pred(*__first)))
1151  {
1152  *__result = _GLIBCXX_MOVE(*__first);
1153  ++__result;
1154  }
1155  return __result;
1156  }
1157 
1172  template<typename _ForwardIterator>
1173  _ForwardIterator
1174  unique(_ForwardIterator __first, _ForwardIterator __last)
1175  {
1176  // concept requirements
1177  __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
1178  _ForwardIterator>)
1179  __glibcxx_function_requires(_EqualityComparableConcept<
1180  typename iterator_traits<_ForwardIterator>::value_type>)
1181  __glibcxx_requires_valid_range(__first, __last);
1182 
1183  // Skip the beginning, if already unique.
1184  __first = _GLIBCXX_STD_A::adjacent_find(__first, __last);
1185  if (__first == __last)
1186  return __last;
1187 
1188  // Do the real copy work.
1189  _ForwardIterator __dest = __first;
1190  ++__first;
1191  while (++__first != __last)
1192  if (!(*__dest == *__first))
1193  *++__dest = _GLIBCXX_MOVE(*__first);
1194  return ++__dest;
1195  }
1196 
1212  template<typename _ForwardIterator, typename _BinaryPredicate>
1213  _ForwardIterator
1214  unique(_ForwardIterator __first, _ForwardIterator __last,
1215  _BinaryPredicate __binary_pred)
1216  {
1217  // concept requirements
1218  __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
1219  _ForwardIterator>)
1220  __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
1221  typename iterator_traits<_ForwardIterator>::value_type,
1222  typename iterator_traits<_ForwardIterator>::value_type>)
1223  __glibcxx_requires_valid_range(__first, __last);
1224 
1225  // Skip the beginning, if already unique.
1226  __first = _GLIBCXX_STD_A::adjacent_find(__first, __last, __binary_pred);
1227  if (__first == __last)
1228  return __last;
1229 
1230  // Do the real copy work.
1231  _ForwardIterator __dest = __first;
1232  ++__first;
1233  while (++__first != __last)
1234  if (!bool(__binary_pred(*__dest, *__first)))
1235  *++__dest = _GLIBCXX_MOVE(*__first);
1236  return ++__dest;
1237  }
1238 
1244  template<typename _ForwardIterator, typename _OutputIterator>
1245  _OutputIterator
1246  __unique_copy(_ForwardIterator __first, _ForwardIterator __last,
1247  _OutputIterator __result,
1248  forward_iterator_tag, output_iterator_tag)
1249  {
1250  // concept requirements -- taken care of in dispatching function
1251  _ForwardIterator __next = __first;
1252  *__result = *__first;
1253  while (++__next != __last)
1254  if (!(*__first == *__next))
1255  {
1256  __first = __next;
1257  *++__result = *__first;
1258  }
1259  return ++__result;
1260  }
1261 
1267  template<typename _InputIterator, typename _OutputIterator>
1268  _OutputIterator
1269  __unique_copy(_InputIterator __first, _InputIterator __last,
1270  _OutputIterator __result,
1271  input_iterator_tag, output_iterator_tag)
1272  {
1273  // concept requirements -- taken care of in dispatching function
1274  typename iterator_traits<_InputIterator>::value_type __value = *__first;
1275  *__result = __value;
1276  while (++__first != __last)
1277  if (!(__value == *__first))
1278  {
1279  __value = *__first;
1280  *++__result = __value;
1281  }
1282  return ++__result;
1283  }
1284 
1290  template<typename _InputIterator, typename _ForwardIterator>
1291  _ForwardIterator
1292  __unique_copy(_InputIterator __first, _InputIterator __last,
1293  _ForwardIterator __result,
1294  input_iterator_tag, forward_iterator_tag)
1295  {
1296  // concept requirements -- taken care of in dispatching function
1297  *__result = *__first;
1298  while (++__first != __last)
1299  if (!(*__result == *__first))
1300  *++__result = *__first;
1301  return ++__result;
1302  }
1303 
1310  template<typename _ForwardIterator, typename _OutputIterator,
1311  typename _BinaryPredicate>
1312  _OutputIterator
1313  __unique_copy(_ForwardIterator __first, _ForwardIterator __last,
1314  _OutputIterator __result, _BinaryPredicate __binary_pred,
1315  forward_iterator_tag, output_iterator_tag)
1316  {
1317  // concept requirements -- iterators already checked
1318  __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
1319  typename iterator_traits<_ForwardIterator>::value_type,
1320  typename iterator_traits<_ForwardIterator>::value_type>)
1321 
1322  _ForwardIterator __next = __first;
1323  *__result = *__first;
1324  while (++__next != __last)
1325  if (!bool(__binary_pred(*__first, *__next)))
1326  {
1327  __first = __next;
1328  *++__result = *__first;
1329  }
1330  return ++__result;
1331  }
1332 
1339  template<typename _InputIterator, typename _OutputIterator,
1340  typename _BinaryPredicate>
1341  _OutputIterator
1342  __unique_copy(_InputIterator __first, _InputIterator __last,
1343  _OutputIterator __result, _BinaryPredicate __binary_pred,
1344  input_iterator_tag, output_iterator_tag)
1345  {
1346  // concept requirements -- iterators already checked
1347  __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
1348  typename iterator_traits<_InputIterator>::value_type,
1349  typename iterator_traits<_InputIterator>::value_type>)
1350 
1351  typename iterator_traits<_InputIterator>::value_type __value = *__first;
1352  *__result = __value;
1353  while (++__first != __last)
1354  if (!bool(__binary_pred(__value, *__first)))
1355  {
1356  __value = *__first;
1357  *++__result = __value;
1358  }
1359  return ++__result;
1360  }
1361 
1368  template<typename _InputIterator, typename _ForwardIterator,
1369  typename _BinaryPredicate>
1370  _ForwardIterator
1371  __unique_copy(_InputIterator __first, _InputIterator __last,
1372  _ForwardIterator __result, _BinaryPredicate __binary_pred,
1373  input_iterator_tag, forward_iterator_tag)
1374  {
1375  // concept requirements -- iterators already checked
1376  __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
1377  typename iterator_traits<_ForwardIterator>::value_type,
1378  typename iterator_traits<_InputIterator>::value_type>)
1379 
1380  *__result = *__first;
1381  while (++__first != __last)
1382  if (!bool(__binary_pred(*__result, *__first)))
1383  *++__result = *__first;
1384  return ++__result;
1385  }
1386 
1392  template<typename _BidirectionalIterator>
1393  void
1394  __reverse(_BidirectionalIterator __first, _BidirectionalIterator __last,
1395  bidirectional_iterator_tag)
1396  {
1397  while (true)
1398  if (__first == __last || __first == --__last)
1399  return;
1400  else
1401  {
1402  std::iter_swap(__first, __last);
1403  ++__first;
1404  }
1405  }
1406 
1412  template<typename _RandomAccessIterator>
1413  void
1414  __reverse(_RandomAccessIterator __first, _RandomAccessIterator __last,
1415  random_access_iterator_tag)
1416  {
1417  if (__first == __last)
1418  return;
1419  --__last;
1420  while (__first < __last)
1421  {
1422  std::iter_swap(__first, __last);
1423  ++__first;
1424  --__last;
1425  }
1426  }
1427 
1440  template<typename _BidirectionalIterator>
1441  inline void
1442  reverse(_BidirectionalIterator __first, _BidirectionalIterator __last)
1443  {
1444  // concept requirements
1445  __glibcxx_function_requires(_Mutable_BidirectionalIteratorConcept<
1446  _BidirectionalIterator>)
1447  __glibcxx_requires_valid_range(__first, __last);
1448  std::__reverse(__first, __last, std::__iterator_category(__first));
1449  }
1450 
1467  template<typename _BidirectionalIterator, typename _OutputIterator>
1468  _OutputIterator
1469  reverse_copy(_BidirectionalIterator __first, _BidirectionalIterator __last,
1470  _OutputIterator __result)
1471  {
1472  // concept requirements
1473  __glibcxx_function_requires(_BidirectionalIteratorConcept<
1474  _BidirectionalIterator>)
1475  __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
1476  typename iterator_traits<_BidirectionalIterator>::value_type>)
1477  __glibcxx_requires_valid_range(__first, __last);
1478 
1479  while (__first != __last)
1480  {
1481  --__last;
1482  *__result = *__last;
1483  ++__result;
1484  }
1485  return __result;
1486  }
1487 
1492  template<typename _EuclideanRingElement>
1493  _EuclideanRingElement
1494  __gcd(_EuclideanRingElement __m, _EuclideanRingElement __n)
1495  {
1496  while (__n != 0)
1497  {
1498  _EuclideanRingElement __t = __m % __n;
1499  __m = __n;
1500  __n = __t;
1501  }
1502  return __m;
1503  }
1504 
1506  template<typename _ForwardIterator>
1507  void
1508  __rotate(_ForwardIterator __first,
1509  _ForwardIterator __middle,
1510  _ForwardIterator __last,
1511  forward_iterator_tag)
1512  {
1513  if (__first == __middle || __last == __middle)
1514  return;
1515 
1516  _ForwardIterator __first2 = __middle;
1517  do
1518  {
1519  std::iter_swap(__first, __first2);
1520  ++__first;
1521  ++__first2;
1522  if (__first == __middle)
1523  __middle = __first2;
1524  }
1525  while (__first2 != __last);
1526 
1527  __first2 = __middle;
1528 
1529  while (__first2 != __last)
1530  {
1531  std::iter_swap(__first, __first2);
1532  ++__first;
1533  ++__first2;
1534  if (__first == __middle)
1535  __middle = __first2;
1536  else if (__first2 == __last)
1537  __first2 = __middle;
1538  }
1539  }
1540 
1542  template<typename _BidirectionalIterator>
1543  void
1544  __rotate(_BidirectionalIterator __first,
1545  _BidirectionalIterator __middle,
1546  _BidirectionalIterator __last,
1547  bidirectional_iterator_tag)
1548  {
1549  // concept requirements
1550  __glibcxx_function_requires(_Mutable_BidirectionalIteratorConcept<
1551  _BidirectionalIterator>)
1552 
1553  if (__first == __middle || __last == __middle)
1554  return;
1555 
1556  std::__reverse(__first, __middle, bidirectional_iterator_tag());
1557  std::__reverse(__middle, __last, bidirectional_iterator_tag());
1558 
1559  while (__first != __middle && __middle != __last)
1560  {
1561  std::iter_swap(__first, --__last);
1562  ++__first;
1563  }
1564 
1565  if (__first == __middle)
1566  std::__reverse(__middle, __last, bidirectional_iterator_tag());
1567  else
1568  std::__reverse(__first, __middle, bidirectional_iterator_tag());
1569  }
1570 
1572  template<typename _RandomAccessIterator>
1573  void
1574  __rotate(_RandomAccessIterator __first,
1575  _RandomAccessIterator __middle,
1576  _RandomAccessIterator __last,
1577  random_access_iterator_tag)
1578  {
1579  // concept requirements
1580  __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
1581  _RandomAccessIterator>)
1582 
1583  if (__first == __middle || __last == __middle)
1584  return;
1585 
1586  typedef typename iterator_traits<_RandomAccessIterator>::difference_type
1587  _Distance;
1588  typedef typename iterator_traits<_RandomAccessIterator>::value_type
1589  _ValueType;
1590 
1591  _Distance __n = __last - __first;
1592  _Distance __k = __middle - __first;
1593 
1594  if (__k == __n - __k)
1595  {
1596  std::swap_ranges(__first, __middle, __middle);
1597  return;
1598  }
1599 
1600  _RandomAccessIterator __p = __first;
1601 
1602  for (;;)
1603  {
1604  if (__k < __n - __k)
1605  {
1606  if (__is_pod(_ValueType) && __k == 1)
1607  {
1608  _ValueType __t = _GLIBCXX_MOVE(*__p);
1609  _GLIBCXX_MOVE3(__p + 1, __p + __n, __p);
1610  *(__p + __n - 1) = _GLIBCXX_MOVE(__t);
1611  return;
1612  }
1613  _RandomAccessIterator __q = __p + __k;
1614  for (_Distance __i = 0; __i < __n - __k; ++ __i)
1615  {
1616  std::iter_swap(__p, __q);
1617  ++__p;
1618  ++__q;
1619  }
1620  __n %= __k;
1621  if (__n == 0)
1622  return;
1623  std::swap(__n, __k);
1624  __k = __n - __k;
1625  }
1626  else
1627  {
1628  __k = __n - __k;
1629  if (__is_pod(_ValueType) && __k == 1)
1630  {
1631  _ValueType __t = _GLIBCXX_MOVE(*(__p + __n - 1));
1632  _GLIBCXX_MOVE_BACKWARD3(__p, __p + __n - 1, __p + __n);
1633  *__p = _GLIBCXX_MOVE(__t);
1634  return;
1635  }
1636  _RandomAccessIterator __q = __p + __n;
1637  __p = __q - __k;
1638  for (_Distance __i = 0; __i < __n - __k; ++ __i)
1639  {
1640  --__p;
1641  --__q;
1642  std::iter_swap(__p, __q);
1643  }
1644  __n %= __k;
1645  if (__n == 0)
1646  return;
1647  std::swap(__n, __k);
1648  }
1649  }
1650  }
1651 
1673  template<typename _ForwardIterator>
1674  inline void
1675  rotate(_ForwardIterator __first, _ForwardIterator __middle,
1676  _ForwardIterator __last)
1677  {
1678  // concept requirements
1679  __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
1680  _ForwardIterator>)
1681  __glibcxx_requires_valid_range(__first, __middle);
1682  __glibcxx_requires_valid_range(__middle, __last);
1683 
1684  typedef typename iterator_traits<_ForwardIterator>::iterator_category
1685  _IterType;
1686  std::__rotate(__first, __middle, __last, _IterType());
1687  }
1688 
1709  template<typename _ForwardIterator, typename _OutputIterator>
1710  _OutputIterator
1711  rotate_copy(_ForwardIterator __first, _ForwardIterator __middle,
1712  _ForwardIterator __last, _OutputIterator __result)
1713  {
1714  // concept requirements
1715  __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
1716  __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
1717  typename iterator_traits<_ForwardIterator>::value_type>)
1718  __glibcxx_requires_valid_range(__first, __middle);
1719  __glibcxx_requires_valid_range(__middle, __last);
1720 
1721  return std::copy(__first, __middle,
1722  std::copy(__middle, __last, __result));
1723  }
1724 
1726  template<typename _ForwardIterator, typename _Predicate>
1727  _ForwardIterator
1728  __partition(_ForwardIterator __first, _ForwardIterator __last,
1729  _Predicate __pred, forward_iterator_tag)
1730  {
1731  if (__first == __last)
1732  return __first;
1733 
1734  while (__pred(*__first))
1735  if (++__first == __last)
1736  return __first;
1737 
1738  _ForwardIterator __next = __first;
1739 
1740  while (++__next != __last)
1741  if (__pred(*__next))
1742  {
1743  std::iter_swap(__first, __next);
1744  ++__first;
1745  }
1746 
1747  return __first;
1748  }
1749 
1751  template<typename _BidirectionalIterator, typename _Predicate>
1752  _BidirectionalIterator
1753  __partition(_BidirectionalIterator __first, _BidirectionalIterator __last,
1754  _Predicate __pred, bidirectional_iterator_tag)
1755  {
1756  while (true)
1757  {
1758  while (true)
1759  if (__first == __last)
1760  return __first;
1761  else if (__pred(*__first))
1762  ++__first;
1763  else
1764  break;
1765  --__last;
1766  while (true)
1767  if (__first == __last)
1768  return __first;
1769  else if (!bool(__pred(*__last)))
1770  --__last;
1771  else
1772  break;
1773  std::iter_swap(__first, __last);
1774  ++__first;
1775  }
1776  }
1777 
1778  // partition
1779 
1783  template<typename _ForwardIterator, typename _Predicate, typename _Distance>
1784  _ForwardIterator
1785  __inplace_stable_partition(_ForwardIterator __first,
1786  _Predicate __pred, _Distance __len)
1787  {
1788  if (__len == 1)
1789  return __first;
1790  _ForwardIterator __middle = __first;
1791  std::advance(__middle, __len / 2);
1792  _ForwardIterator __left_split =
1793  std::__inplace_stable_partition(__first, __pred, __len / 2);
1794  // Advance past true-predicate values to satisfy this
1795  // function's preconditions.
1796  _Distance __right_len = __len - __len / 2;
1797  _ForwardIterator __right_split =
1798  std::__find_if_not_n(__middle, __right_len, __pred);
1799  if (__right_len)
1800  __right_split = std::__inplace_stable_partition(__middle,
1801  __pred,
1802  __right_len);
1803  std::rotate(__left_split, __middle, __right_split);
1804  std::advance(__left_split, std::distance(__middle, __right_split));
1805  return __left_split;
1806  }
1807 
1814  template<typename _ForwardIterator, typename _Pointer, typename _Predicate,
1815  typename _Distance>
1816  _ForwardIterator
1817  __stable_partition_adaptive(_ForwardIterator __first,
1818  _ForwardIterator __last,
1819  _Predicate __pred, _Distance __len,
1820  _Pointer __buffer,
1821  _Distance __buffer_size)
1822  {
1823  if (__len <= __buffer_size)
1824  {
1825  _ForwardIterator __result1 = __first;
1826  _Pointer __result2 = __buffer;
1827  // The precondition guarantees that !__pred(*__first), so
1828  // move that element to the buffer before starting the loop.
1829  // This ensures that we only call __pred once per element.
1830  *__result2 = _GLIBCXX_MOVE(*__first);
1831  ++__result2;
1832  ++__first;
1833  for (; __first != __last; ++__first)
1834  if (__pred(*__first))
1835  {
1836  *__result1 = _GLIBCXX_MOVE(*__first);
1837  ++__result1;
1838  }
1839  else
1840  {
1841  *__result2 = _GLIBCXX_MOVE(*__first);
1842  ++__result2;
1843  }
1844  _GLIBCXX_MOVE3(__buffer, __result2, __result1);
1845  return __result1;
1846  }
1847  else
1848  {
1849  _ForwardIterator __middle = __first;
1850  std::advance(__middle, __len / 2);
1851  _ForwardIterator __left_split =
1852  std::__stable_partition_adaptive(__first, __middle, __pred,
1853  __len / 2, __buffer,
1854  __buffer_size);
1855  // Advance past true-predicate values to satisfy this
1856  // function's preconditions.
1857  _Distance __right_len = __len - __len / 2;
1858  _ForwardIterator __right_split =
1859  std::__find_if_not_n(__middle, __right_len, __pred);
1860  if (__right_len)
1861  __right_split =
1862  std::__stable_partition_adaptive(__right_split, __last, __pred,
1863  __right_len,
1864  __buffer, __buffer_size);
1865  std::rotate(__left_split, __middle, __right_split);
1866  std::advance(__left_split, std::distance(__middle, __right_split));
1867  return __left_split;
1868  }
1869  }
1870 
1888  template<typename _ForwardIterator, typename _Predicate>
1889  _ForwardIterator
1890  stable_partition(_ForwardIterator __first, _ForwardIterator __last,
1891  _Predicate __pred)
1892  {
1893  // concept requirements
1894  __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
1895  _ForwardIterator>)
1896  __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
1897  typename iterator_traits<_ForwardIterator>::value_type>)
1898  __glibcxx_requires_valid_range(__first, __last);
1899 
1900  __first = std::__find_if_not(__first, __last, __pred);
1901 
1902  if (__first == __last)
1903  return __first;
1904  else
1905  {
1906  typedef typename iterator_traits<_ForwardIterator>::value_type
1907  _ValueType;
1908  typedef typename iterator_traits<_ForwardIterator>::difference_type
1909  _DistanceType;
1910 
1911  _Temporary_buffer<_ForwardIterator, _ValueType> __buf(__first,
1912  __last);
1913  if (__buf.size() > 0)
1914  return
1915  std::__stable_partition_adaptive(__first, __last, __pred,
1916  _DistanceType(__buf.requested_size()),
1917  __buf.begin(),
1918  _DistanceType(__buf.size()));
1919  else
1920  return
1921  std::__inplace_stable_partition(__first, __pred,
1922  _DistanceType(__buf.requested_size()));
1923  }
1924  }
1925 
1927  template<typename _RandomAccessIterator>
1928  void
1929  __heap_select(_RandomAccessIterator __first,
1930  _RandomAccessIterator __middle,
1931  _RandomAccessIterator __last)
1932  {
1933  std::make_heap(__first, __middle);
1934  for (_RandomAccessIterator __i = __middle; __i < __last; ++__i)
1935  if (*__i < *__first)
1936  std::__pop_heap(__first, __middle, __i);
1937  }
1938 
1940  template<typename _RandomAccessIterator, typename _Compare>
1941  void
1942  __heap_select(_RandomAccessIterator __first,
1943  _RandomAccessIterator __middle,
1944  _RandomAccessIterator __last, _Compare __comp)
1945  {
1946  std::make_heap(__first, __middle, __comp);
1947  for (_RandomAccessIterator __i = __middle; __i < __last; ++__i)
1948  if (__comp(*__i, *__first))
1949  std::__pop_heap(__first, __middle, __i, __comp);
1950  }
1951 
1952  // partial_sort
1953 
1972  template<typename _InputIterator, typename _RandomAccessIterator>
1973  _RandomAccessIterator
1974  partial_sort_copy(_InputIterator __first, _InputIterator __last,
1975  _RandomAccessIterator __result_first,
1976  _RandomAccessIterator __result_last)
1977  {
1978  typedef typename iterator_traits<_InputIterator>::value_type
1979  _InputValueType;
1980  typedef typename iterator_traits<_RandomAccessIterator>::value_type
1981  _OutputValueType;
1982  typedef typename iterator_traits<_RandomAccessIterator>::difference_type
1983  _DistanceType;
1984 
1985  // concept requirements
1986  __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
1987  __glibcxx_function_requires(_ConvertibleConcept<_InputValueType,
1988  _OutputValueType>)
1989  __glibcxx_function_requires(_LessThanOpConcept<_InputValueType,
1990  _OutputValueType>)
1991  __glibcxx_function_requires(_LessThanComparableConcept<_OutputValueType>)
1992  __glibcxx_requires_valid_range(__first, __last);
1993  __glibcxx_requires_valid_range(__result_first, __result_last);
1994 
1995  if (__result_first == __result_last)
1996  return __result_last;
1997  _RandomAccessIterator __result_real_last = __result_first;
1998  while(__first != __last && __result_real_last != __result_last)
1999  {
2000  *__result_real_last = *__first;
2001  ++__result_real_last;
2002  ++__first;
2003  }
2004  std::make_heap(__result_first, __result_real_last);
2005  while (__first != __last)
2006  {
2007  if (*__first < *__result_first)
2008  std::__adjust_heap(__result_first, _DistanceType(0),
2009  _DistanceType(__result_real_last
2010  - __result_first),
2011  _InputValueType(*__first));
2012  ++__first;
2013  }
2014  std::sort_heap(__result_first, __result_real_last);
2015  return __result_real_last;
2016  }
2017 
2038  template<typename _InputIterator, typename _RandomAccessIterator, typename _Compare>
2039  _RandomAccessIterator
2040  partial_sort_copy(_InputIterator __first, _InputIterator __last,
2041  _RandomAccessIterator __result_first,
2042  _RandomAccessIterator __result_last,
2043  _Compare __comp)
2044  {
2045  typedef typename iterator_traits<_InputIterator>::value_type
2046  _InputValueType;
2047  typedef typename iterator_traits<_RandomAccessIterator>::value_type
2048  _OutputValueType;
2049  typedef typename iterator_traits<_RandomAccessIterator>::difference_type
2050  _DistanceType;
2051 
2052  // concept requirements
2053  __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
2054  __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
2055  _RandomAccessIterator>)
2056  __glibcxx_function_requires(_ConvertibleConcept<_InputValueType,
2057  _OutputValueType>)
2058  __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2059  _InputValueType, _OutputValueType>)
2060  __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2061  _OutputValueType, _OutputValueType>)
2062  __glibcxx_requires_valid_range(__first, __last);
2063  __glibcxx_requires_valid_range(__result_first, __result_last);
2064 
2065  if (__result_first == __result_last)
2066  return __result_last;
2067  _RandomAccessIterator __result_real_last = __result_first;
2068  while(__first != __last && __result_real_last != __result_last)
2069  {
2070  *__result_real_last = *__first;
2071  ++__result_real_last;
2072  ++__first;
2073  }
2074  std::make_heap(__result_first, __result_real_last, __comp);
2075  while (__first != __last)
2076  {
2077  if (__comp(*__first, *__result_first))
2078  std::__adjust_heap(__result_first, _DistanceType(0),
2079  _DistanceType(__result_real_last
2080  - __result_first),
2081  _InputValueType(*__first),
2082  __comp);
2083  ++__first;
2084  }
2085  std::sort_heap(__result_first, __result_real_last, __comp);
2086  return __result_real_last;
2087  }
2088 
2090  template<typename _RandomAccessIterator>
2091  void
2092  __unguarded_linear_insert(_RandomAccessIterator __last)
2093  {
2094  typename iterator_traits<_RandomAccessIterator>::value_type
2095  __val = _GLIBCXX_MOVE(*__last);
2096  _RandomAccessIterator __next = __last;
2097  --__next;
2098  while (__val < *__next)
2099  {
2100  *__last = _GLIBCXX_MOVE(*__next);
2101  __last = __next;
2102  --__next;
2103  }
2104  *__last = _GLIBCXX_MOVE(__val);
2105  }
2106 
2108  template<typename _RandomAccessIterator, typename _Compare>
2109  void
2110  __unguarded_linear_insert(_RandomAccessIterator __last,
2111  _Compare __comp)
2112  {
2113  typename iterator_traits<_RandomAccessIterator>::value_type
2114  __val = _GLIBCXX_MOVE(*__last);
2115  _RandomAccessIterator __next = __last;
2116  --__next;
2117  while (__comp(__val, *__next))
2118  {
2119  *__last = _GLIBCXX_MOVE(*__next);
2120  __last = __next;
2121  --__next;
2122  }
2123  *__last = _GLIBCXX_MOVE(__val);
2124  }
2125 
2127  template<typename _RandomAccessIterator>
2128  void
2129  __insertion_sort(_RandomAccessIterator __first,
2130  _RandomAccessIterator __last)
2131  {
2132  if (__first == __last)
2133  return;
2134 
2135  for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i)
2136  {
2137  if (*__i < *__first)
2138  {
2139  typename iterator_traits<_RandomAccessIterator>::value_type
2140  __val = _GLIBCXX_MOVE(*__i);
2141  _GLIBCXX_MOVE_BACKWARD3(__first, __i, __i + 1);
2142  *__first = _GLIBCXX_MOVE(__val);
2143  }
2144  else
2145  std::__unguarded_linear_insert(__i);
2146  }
2147  }
2148 
2150  template<typename _RandomAccessIterator, typename _Compare>
2151  void
2152  __insertion_sort(_RandomAccessIterator __first,
2153  _RandomAccessIterator __last, _Compare __comp)
2154  {
2155  if (__first == __last) return;
2156 
2157  for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i)
2158  {
2159  if (__comp(*__i, *__first))
2160  {
2161  typename iterator_traits<_RandomAccessIterator>::value_type
2162  __val = _GLIBCXX_MOVE(*__i);
2163  _GLIBCXX_MOVE_BACKWARD3(__first, __i, __i + 1);
2164  *__first = _GLIBCXX_MOVE(__val);
2165  }
2166  else
2167  std::__unguarded_linear_insert(__i, __comp);
2168  }
2169  }
2170 
2172  template<typename _RandomAccessIterator>
2173  inline void
2174  __unguarded_insertion_sort(_RandomAccessIterator __first,
2175  _RandomAccessIterator __last)
2176  {
2177  typedef typename iterator_traits<_RandomAccessIterator>::value_type
2178  _ValueType;
2179 
2180  for (_RandomAccessIterator __i = __first; __i != __last; ++__i)
2181  std::__unguarded_linear_insert(__i);
2182  }
2183 
2185  template<typename _RandomAccessIterator, typename _Compare>
2186  inline void
2187  __unguarded_insertion_sort(_RandomAccessIterator __first,
2188  _RandomAccessIterator __last, _Compare __comp)
2189  {
2190  typedef typename iterator_traits<_RandomAccessIterator>::value_type
2191  _ValueType;
2192 
2193  for (_RandomAccessIterator __i = __first; __i != __last; ++__i)
2194  std::__unguarded_linear_insert(__i, __comp);
2195  }
2196 
2201  enum { _S_threshold = 16 };
2202 
2204  template<typename _RandomAccessIterator>
2205  void
2206  __final_insertion_sort(_RandomAccessIterator __first,
2207  _RandomAccessIterator __last)
2208  {
2209  if (__last - __first > int(_S_threshold))
2210  {
2211  std::__insertion_sort(__first, __first + int(_S_threshold));
2212  std::__unguarded_insertion_sort(__first + int(_S_threshold), __last);
2213  }
2214  else
2215  std::__insertion_sort(__first, __last);
2216  }
2217 
2219  template<typename _RandomAccessIterator, typename _Compare>
2220  void
2221  __final_insertion_sort(_RandomAccessIterator __first,
2222  _RandomAccessIterator __last, _Compare __comp)
2223  {
2224  if (__last - __first > int(_S_threshold))
2225  {
2226  std::__insertion_sort(__first, __first + int(_S_threshold), __comp);
2227  std::__unguarded_insertion_sort(__first + int(_S_threshold), __last,
2228  __comp);
2229  }
2230  else
2231  std::__insertion_sort(__first, __last, __comp);
2232  }
2233 
2235  template<typename _RandomAccessIterator, typename _Tp>
2236  _RandomAccessIterator
2237  __unguarded_partition(_RandomAccessIterator __first,
2238  _RandomAccessIterator __last, const _Tp& __pivot)
2239  {
2240  while (true)
2241  {
2242  while (*__first < __pivot)
2243  ++__first;
2244  --__last;
2245  while (__pivot < *__last)
2246  --__last;
2247  if (!(__first < __last))
2248  return __first;
2249  std::iter_swap(__first, __last);
2250  ++__first;
2251  }
2252  }
2253 
2255  template<typename _RandomAccessIterator, typename _Tp, typename _Compare>
2256  _RandomAccessIterator
2257  __unguarded_partition(_RandomAccessIterator __first,
2258  _RandomAccessIterator __last,
2259  const _Tp& __pivot, _Compare __comp)
2260  {
2261  while (true)
2262  {
2263  while (__comp(*__first, __pivot))
2264  ++__first;
2265  --__last;
2266  while (__comp(__pivot, *__last))
2267  --__last;
2268  if (!(__first < __last))
2269  return __first;
2270  std::iter_swap(__first, __last);
2271  ++__first;
2272  }
2273  }
2274 
2276  template<typename _RandomAccessIterator>
2277  inline _RandomAccessIterator
2278  __unguarded_partition_pivot(_RandomAccessIterator __first,
2279  _RandomAccessIterator __last)
2280  {
2281  _RandomAccessIterator __mid = __first + (__last - __first) / 2;
2282  std::__move_median_to_first(__first, __first + 1, __mid, __last - 1);
2283  return std::__unguarded_partition(__first + 1, __last, *__first);
2284  }
2285 
2286 
2288  template<typename _RandomAccessIterator, typename _Compare>
2289  inline _RandomAccessIterator
2290  __unguarded_partition_pivot(_RandomAccessIterator __first,
2291  _RandomAccessIterator __last, _Compare __comp)
2292  {
2293  _RandomAccessIterator __mid = __first + (__last - __first) / 2;
2294  std::__move_median_to_first(__first, __first + 1, __mid, __last - 1,
2295  __comp);
2296  return std::__unguarded_partition(__first + 1, __last, *__first, __comp);
2297  }
2298 
2300  template<typename _RandomAccessIterator, typename _Size>
2301  void
2302  __introsort_loop(_RandomAccessIterator __first,
2303  _RandomAccessIterator __last,
2304  _Size __depth_limit)
2305  {
2306  while (__last - __first > int(_S_threshold))
2307  {
2308  if (__depth_limit == 0)
2309  {
2310  _GLIBCXX_STD_A::partial_sort(__first, __last, __last);
2311  return;
2312  }
2313  --__depth_limit;
2314  _RandomAccessIterator __cut =
2315  std::__unguarded_partition_pivot(__first, __last);
2316  std::__introsort_loop(__cut, __last, __depth_limit);
2317  __last = __cut;
2318  }
2319  }
2320 
2322  template<typename _RandomAccessIterator, typename _Size, typename _Compare>
2323  void
2324  __introsort_loop(_RandomAccessIterator __first,
2325  _RandomAccessIterator __last,
2326  _Size __depth_limit, _Compare __comp)
2327  {
2328  while (__last - __first > int(_S_threshold))
2329  {
2330  if (__depth_limit == 0)
2331  {
2332  _GLIBCXX_STD_A::partial_sort(__first, __last, __last, __comp);
2333  return;
2334  }
2335  --__depth_limit;
2336  _RandomAccessIterator __cut =
2337  std::__unguarded_partition_pivot(__first, __last, __comp);
2338  std::__introsort_loop(__cut, __last, __depth_limit, __comp);
2339  __last = __cut;
2340  }
2341  }
2342 
2343  // sort
2344 
2345  template<typename _RandomAccessIterator, typename _Size>
2346  void
2347  __introselect(_RandomAccessIterator __first, _RandomAccessIterator __nth,
2348  _RandomAccessIterator __last, _Size __depth_limit)
2349  {
2350  typedef typename iterator_traits<_RandomAccessIterator>::value_type
2351  _ValueType;
2352 
2353  while (__last - __first > 3)
2354  {
2355  if (__depth_limit == 0)
2356  {
2357  std::__heap_select(__first, __nth + 1, __last);
2358 
2359  // Place the nth largest element in its final position.
2360  std::iter_swap(__first, __nth);
2361  return;
2362  }
2363  --__depth_limit;
2364  _RandomAccessIterator __cut =
2365  std::__unguarded_partition_pivot(__first, __last);
2366  if (__cut <= __nth)
2367  __first = __cut;
2368  else
2369  __last = __cut;
2370  }
2371  std::__insertion_sort(__first, __last);
2372  }
2373 
2374  template<typename _RandomAccessIterator, typename _Size, typename _Compare>
2375  void
2376  __introselect(_RandomAccessIterator __first, _RandomAccessIterator __nth,
2377  _RandomAccessIterator __last, _Size __depth_limit,
2378  _Compare __comp)
2379  {
2380  typedef typename iterator_traits<_RandomAccessIterator>::value_type
2381  _ValueType;
2382 
2383  while (__last - __first > 3)
2384  {
2385  if (__depth_limit == 0)
2386  {
2387  std::__heap_select(__first, __nth + 1, __last, __comp);
2388  // Place the nth largest element in its final position.
2389  std::iter_swap(__first, __nth);
2390  return;
2391  }
2392  --__depth_limit;
2393  _RandomAccessIterator __cut =
2394  std::__unguarded_partition_pivot(__first, __last, __comp);
2395  if (__cut <= __nth)
2396  __first = __cut;
2397  else
2398  __last = __cut;
2399  }
2400  std::__insertion_sort(__first, __last, __comp);
2401  }
2402 
2403  // nth_element
2404 
2405  // lower_bound moved to stl_algobase.h
2406 
2423  template<typename _ForwardIterator, typename _Tp, typename _Compare>
2424  _ForwardIterator
2425  lower_bound(_ForwardIterator __first, _ForwardIterator __last,
2426  const _Tp& __val, _Compare __comp)
2427  {
2428  typedef typename iterator_traits<_ForwardIterator>::value_type
2429  _ValueType;
2430  typedef typename iterator_traits<_ForwardIterator>::difference_type
2431  _DistanceType;
2432 
2433  // concept requirements
2434  __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
2435  __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2436  _ValueType, _Tp>)
2437  __glibcxx_requires_partitioned_lower_pred(__first, __last,
2438  __val, __comp);
2439 
2440  _DistanceType __len = std::distance(__first, __last);
2441 
2442  while (__len > 0)
2443  {
2444  _DistanceType __half = __len >> 1;
2445  _ForwardIterator __middle = __first;
2446  std::advance(__middle, __half);
2447  if (__comp(*__middle, __val))
2448  {
2449  __first = __middle;
2450  ++__first;
2451  __len = __len - __half - 1;
2452  }
2453  else
2454  __len = __half;
2455  }
2456  return __first;
2457  }
2458 
2470  template<typename _ForwardIterator, typename _Tp>
2471  _ForwardIterator
2472  upper_bound(_ForwardIterator __first, _ForwardIterator __last,
2473  const _Tp& __val)
2474  {
2475  typedef typename iterator_traits<_ForwardIterator>::value_type
2476  _ValueType;
2477  typedef typename iterator_traits<_ForwardIterator>::difference_type
2478  _DistanceType;
2479 
2480  // concept requirements
2481  __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
2482  __glibcxx_function_requires(_LessThanOpConcept<_Tp, _ValueType>)
2483  __glibcxx_requires_partitioned_upper(__first, __last, __val);
2484 
2485  _DistanceType __len = std::distance(__first, __last);
2486 
2487  while (__len > 0)
2488  {
2489  _DistanceType __half = __len >> 1;
2490  _ForwardIterator __middle = __first;
2491  std::advance(__middle, __half);
2492  if (__val < *__middle)
2493  __len = __half;
2494  else
2495  {
2496  __first = __middle;
2497  ++__first;
2498  __len = __len - __half - 1;
2499  }
2500  }
2501  return __first;
2502  }
2503 
2519  template<typename _ForwardIterator, typename _Tp, typename _Compare>
2520  _ForwardIterator
2521  upper_bound(_ForwardIterator __first, _ForwardIterator __last,
2522  const _Tp& __val, _Compare __comp)
2523  {
2524  typedef typename iterator_traits<_ForwardIterator>::value_type
2525  _ValueType;
2526  typedef typename iterator_traits<_ForwardIterator>::difference_type
2527  _DistanceType;
2528 
2529  // concept requirements
2530  __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
2531  __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2532  _Tp, _ValueType>)
2533  __glibcxx_requires_partitioned_upper_pred(__first, __last,
2534  __val, __comp);
2535 
2536  _DistanceType __len = std::distance(__first, __last);
2537 
2538  while (__len > 0)
2539  {
2540  _DistanceType __half = __len >> 1;
2541  _ForwardIterator __middle = __first;
2542  std::advance(__middle, __half);
2543  if (__comp(__val, *__middle))
2544  __len = __half;
2545  else
2546  {
2547  __first = __middle;
2548  ++__first;
2549  __len = __len - __half - 1;
2550  }
2551  }
2552  return __first;
2553  }
2554 
2572  template<typename _ForwardIterator, typename _Tp>
2573  pair<_ForwardIterator, _ForwardIterator>
2574  equal_range(_ForwardIterator __first, _ForwardIterator __last,
2575  const _Tp& __val)
2576  {
2577  typedef typename iterator_traits<_ForwardIterator>::value_type
2578  _ValueType;
2579  typedef typename iterator_traits<_ForwardIterator>::difference_type
2580  _DistanceType;
2581 
2582  // concept requirements
2583  __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
2584  __glibcxx_function_requires(_LessThanOpConcept<_ValueType, _Tp>)
2585  __glibcxx_function_requires(_LessThanOpConcept<_Tp, _ValueType>)
2586  __glibcxx_requires_partitioned_lower(__first, __last, __val);
2587  __glibcxx_requires_partitioned_upper(__first, __last, __val);
2588 
2589  _DistanceType __len = std::distance(__first, __last);
2590 
2591  while (__len > 0)
2592  {
2593  _DistanceType __half = __len >> 1;
2594  _ForwardIterator __middle = __first;
2595  std::advance(__middle, __half);
2596  if (*__middle < __val)
2597  {
2598  __first = __middle;
2599  ++__first;
2600  __len = __len - __half - 1;
2601  }
2602  else if (__val < *__middle)
2603  __len = __half;
2604  else
2605  {
2606  _ForwardIterator __left = std::lower_bound(__first, __middle,
2607  __val);
2608  std::advance(__first, __len);
2609  _ForwardIterator __right = std::upper_bound(++__middle, __first,
2610  __val);
2611  return pair<_ForwardIterator, _ForwardIterator>(__left, __right);
2612  }
2613  }
2614  return pair<_ForwardIterator, _ForwardIterator>(__first, __first);
2615  }
2616 
2634  template<typename _ForwardIterator, typename _Tp, typename _Compare>
2635  pair<_ForwardIterator, _ForwardIterator>
2636  equal_range(_ForwardIterator __first, _ForwardIterator __last,
2637  const _Tp& __val, _Compare __comp)
2638  {
2639  typedef typename iterator_traits<_ForwardIterator>::value_type
2640  _ValueType;
2641  typedef typename iterator_traits<_ForwardIterator>::difference_type
2642  _DistanceType;
2643 
2644  // concept requirements
2645  __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
2646  __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2647  _ValueType, _Tp>)
2648  __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2649  _Tp, _ValueType>)
2650  __glibcxx_requires_partitioned_lower_pred(__first, __last,
2651  __val, __comp);
2652  __glibcxx_requires_partitioned_upper_pred(__first, __last,
2653  __val, __comp);
2654 
2655  _DistanceType __len = std::distance(__first, __last);
2656 
2657  while (__len > 0)
2658  {
2659  _DistanceType __half = __len >> 1;
2660  _ForwardIterator __middle = __first;
2661  std::advance(__middle, __half);
2662  if (__comp(*__middle, __val))
2663  {
2664  __first = __middle;
2665  ++__first;
2666  __len = __len - __half - 1;
2667  }
2668  else if (__comp(__val, *__middle))
2669  __len = __half;
2670  else
2671  {
2672  _ForwardIterator __left = std::lower_bound(__first, __middle,
2673  __val, __comp);
2674  std::advance(__first, __len);
2675  _ForwardIterator __right = std::upper_bound(++__middle, __first,
2676  __val, __comp);
2677  return pair<_ForwardIterator, _ForwardIterator>(__left, __right);
2678  }
2679  }
2680  return pair<_ForwardIterator, _ForwardIterator>(__first, __first);
2681  }
2682 
2695  template<typename _ForwardIterator, typename _Tp>
2696  bool
2697  binary_search(_ForwardIterator __first, _ForwardIterator __last,
2698  const _Tp& __val)
2699  {
2700  typedef typename iterator_traits<_ForwardIterator>::value_type
2701  _ValueType;
2702 
2703  // concept requirements
2704  __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
2705  __glibcxx_function_requires(_LessThanOpConcept<_Tp, _ValueType>)
2706  __glibcxx_requires_partitioned_lower(__first, __last, __val);
2707  __glibcxx_requires_partitioned_upper(__first, __last, __val);
2708 
2709  _ForwardIterator __i = std::lower_bound(__first, __last, __val);
2710  return __i != __last && !(__val < *__i);
2711  }
2712 
2728  template<typename _ForwardIterator, typename _Tp, typename _Compare>
2729  bool
2730  binary_search(_ForwardIterator __first, _ForwardIterator __last,
2731  const _Tp& __val, _Compare __comp)
2732  {
2733  typedef typename iterator_traits<_ForwardIterator>::value_type
2734  _ValueType;
2735 
2736  // concept requirements
2737  __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
2738  __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2739  _Tp, _ValueType>)
2740  __glibcxx_requires_partitioned_lower_pred(__first, __last,
2741  __val, __comp);
2742  __glibcxx_requires_partitioned_upper_pred(__first, __last,
2743  __val, __comp);
2744 
2745  _ForwardIterator __i = std::lower_bound(__first, __last, __val, __comp);
2746  return __i != __last && !bool(__comp(__val, *__i));
2747  }
2748 
2749  // merge
2750 
2752  template<typename _InputIterator1, typename _InputIterator2,
2753  typename _OutputIterator>
2754  void
2755  __move_merge_adaptive(_InputIterator1 __first1, _InputIterator1 __last1,
2756  _InputIterator2 __first2, _InputIterator2 __last2,
2757  _OutputIterator __result)
2758  {
2759  while (__first1 != __last1 && __first2 != __last2)
2760  {
2761  if (*__first2 < *__first1)
2762  {
2763  *__result = _GLIBCXX_MOVE(*__first2);
2764  ++__first2;
2765  }
2766  else
2767  {
2768  *__result = _GLIBCXX_MOVE(*__first1);
2769  ++__first1;
2770  }
2771  ++__result;
2772  }
2773  if (__first1 != __last1)
2774  _GLIBCXX_MOVE3(__first1, __last1, __result);
2775  }
2776 
2778  template<typename _InputIterator1, typename _InputIterator2,
2779  typename _OutputIterator, typename _Compare>
2780  void
2781  __move_merge_adaptive(_InputIterator1 __first1, _InputIterator1 __last1,
2782  _InputIterator2 __first2, _InputIterator2 __last2,
2783  _OutputIterator __result, _Compare __comp)
2784  {
2785  while (__first1 != __last1 && __first2 != __last2)
2786  {
2787  if (__comp(*__first2, *__first1))
2788  {
2789  *__result = _GLIBCXX_MOVE(*__first2);
2790  ++__first2;
2791  }
2792  else
2793  {
2794  *__result = _GLIBCXX_MOVE(*__first1);
2795  ++__first1;
2796  }
2797  ++__result;
2798  }
2799  if (__first1 != __last1)
2800  _GLIBCXX_MOVE3(__first1, __last1, __result);
2801  }
2802 
2804  template<typename _BidirectionalIterator1, typename _BidirectionalIterator2,
2805  typename _BidirectionalIterator3>
2806  void
2807  __move_merge_adaptive_backward(_BidirectionalIterator1 __first1,
2808  _BidirectionalIterator1 __last1,
2809  _BidirectionalIterator2 __first2,
2810  _BidirectionalIterator2 __last2,
2811  _BidirectionalIterator3 __result)
2812  {
2813  if (__first1 == __last1)
2814  {
2815  _GLIBCXX_MOVE_BACKWARD3(__first2, __last2, __result);
2816  return;
2817  }
2818  else if (__first2 == __last2)
2819  return;
2820 
2821  --__last1;
2822  --__last2;
2823  while (true)
2824  {
2825  if (*__last2 < *__last1)
2826  {
2827  *--__result = _GLIBCXX_MOVE(*__last1);
2828  if (__first1 == __last1)
2829  {
2830  _GLIBCXX_MOVE_BACKWARD3(__first2, ++__last2, __result);
2831  return;
2832  }
2833  --__last1;
2834  }
2835  else
2836  {
2837  *--__result = _GLIBCXX_MOVE(*__last2);
2838  if (__first2 == __last2)
2839  return;
2840  --__last2;
2841  }
2842  }
2843  }
2844 
2846  template<typename _BidirectionalIterator1, typename _BidirectionalIterator2,
2847  typename _BidirectionalIterator3, typename _Compare>
2848  void
2849  __move_merge_adaptive_backward(_BidirectionalIterator1 __first1,
2850  _BidirectionalIterator1 __last1,
2851  _BidirectionalIterator2 __first2,
2852  _BidirectionalIterator2 __last2,
2853  _BidirectionalIterator3 __result,
2854  _Compare __comp)
2855  {
2856  if (__first1 == __last1)
2857  {
2858  _GLIBCXX_MOVE_BACKWARD3(__first2, __last2, __result);
2859  return;
2860  }
2861  else if (__first2 == __last2)
2862  return;
2863 
2864  --__last1;
2865  --__last2;
2866  while (true)
2867  {
2868  if (__comp(*__last2, *__last1))
2869  {
2870  *--__result = _GLIBCXX_MOVE(*__last1);
2871  if (__first1 == __last1)
2872  {
2873  _GLIBCXX_MOVE_BACKWARD3(__first2, ++__last2, __result);
2874  return;
2875  }
2876  --__last1;
2877  }
2878  else
2879  {
2880  *--__result = _GLIBCXX_MOVE(*__last2);
2881  if (__first2 == __last2)
2882  return;
2883  --__last2;
2884  }
2885  }
2886  }
2887 
2889  template<typename _BidirectionalIterator1, typename _BidirectionalIterator2,
2890  typename _Distance>
2891  _BidirectionalIterator1
2892  __rotate_adaptive(_BidirectionalIterator1 __first,
2893  _BidirectionalIterator1 __middle,
2894  _BidirectionalIterator1 __last,
2895  _Distance __len1, _Distance __len2,
2896  _BidirectionalIterator2 __buffer,
2897  _Distance __buffer_size)
2898  {
2899  _BidirectionalIterator2 __buffer_end;
2900  if (__len1 > __len2 && __len2 <= __buffer_size)
2901  {
2902  if (__len2)
2903  {
2904  __buffer_end = _GLIBCXX_MOVE3(__middle, __last, __buffer);
2905  _GLIBCXX_MOVE_BACKWARD3(__first, __middle, __last);
2906  return _GLIBCXX_MOVE3(__buffer, __buffer_end, __first);
2907  }
2908  else
2909  return __first;
2910  }
2911  else if (__len1 <= __buffer_size)
2912  {
2913  if (__len1)
2914  {
2915  __buffer_end = _GLIBCXX_MOVE3(__first, __middle, __buffer);
2916  _GLIBCXX_MOVE3(__middle, __last, __first);
2917  return _GLIBCXX_MOVE_BACKWARD3(__buffer, __buffer_end, __last);
2918  }
2919  else
2920  return __last;
2921  }
2922  else
2923  {
2924  std::rotate(__first, __middle, __last);
2925  std::advance(__first, std::distance(__middle, __last));
2926  return __first;
2927  }
2928  }
2929 
2931  template<typename _BidirectionalIterator, typename _Distance,
2932  typename _Pointer>
2933  void
2934  __merge_adaptive(_BidirectionalIterator __first,
2935  _BidirectionalIterator __middle,
2936  _BidirectionalIterator __last,
2937  _Distance __len1, _Distance __len2,
2938  _Pointer __buffer, _Distance __buffer_size)
2939  {
2940  if (__len1 <= __len2 && __len1 <= __buffer_size)
2941  {
2942  _Pointer __buffer_end = _GLIBCXX_MOVE3(__first, __middle, __buffer);
2943  std::__move_merge_adaptive(__buffer, __buffer_end, __middle, __last,
2944  __first);
2945  }
2946  else if (__len2 <= __buffer_size)
2947  {
2948  _Pointer __buffer_end = _GLIBCXX_MOVE3(__middle, __last, __buffer);
2949  std::__move_merge_adaptive_backward(__first, __middle, __buffer,
2950  __buffer_end, __last);
2951  }
2952  else
2953  {
2954  _BidirectionalIterator __first_cut = __first;
2955  _BidirectionalIterator __second_cut = __middle;
2956  _Distance __len11 = 0;
2957  _Distance __len22 = 0;
2958  if (__len1 > __len2)
2959  {
2960  __len11 = __len1 / 2;
2961  std::advance(__first_cut, __len11);
2962  __second_cut = std::lower_bound(__middle, __last,
2963  *__first_cut);
2964  __len22 = std::distance(__middle, __second_cut);
2965  }
2966  else
2967  {
2968  __len22 = __len2 / 2;
2969  std::advance(__second_cut, __len22);
2970  __first_cut = std::upper_bound(__first, __middle,
2971  *__second_cut);
2972  __len11 = std::distance(__first, __first_cut);
2973  }
2974  _BidirectionalIterator __new_middle =
2975  std::__rotate_adaptive(__first_cut, __middle, __second_cut,
2976  __len1 - __len11, __len22, __buffer,
2977  __buffer_size);
2978  std::__merge_adaptive(__first, __first_cut, __new_middle, __len11,
2979  __len22, __buffer, __buffer_size);
2980  std::__merge_adaptive(__new_middle, __second_cut, __last,
2981  __len1 - __len11,
2982  __len2 - __len22, __buffer, __buffer_size);
2983  }
2984  }
2985 
2987  template<typename _BidirectionalIterator, typename _Distance,
2988  typename _Pointer, typename _Compare>
2989  void
2990  __merge_adaptive(_BidirectionalIterator __first,
2991  _BidirectionalIterator __middle,
2992  _BidirectionalIterator __last,
2993  _Distance __len1, _Distance __len2,
2994  _Pointer __buffer, _Distance __buffer_size,
2995  _Compare __comp)
2996  {
2997  if (__len1 <= __len2 && __len1 <= __buffer_size)
2998  {
2999  _Pointer __buffer_end = _GLIBCXX_MOVE3(__first, __middle, __buffer);
3000  std::__move_merge_adaptive(__buffer, __buffer_end, __middle, __last,
3001  __first, __comp);
3002  }
3003  else if (__len2 <= __buffer_size)
3004  {
3005  _Pointer __buffer_end = _GLIBCXX_MOVE3(__middle, __last, __buffer);
3006  std::__move_merge_adaptive_backward(__first, __middle, __buffer,
3007  __buffer_end, __last, __comp);
3008  }
3009  else
3010  {
3011  _BidirectionalIterator __first_cut = __first;
3012  _BidirectionalIterator __second_cut = __middle;
3013  _Distance __len11 = 0;
3014  _Distance __len22 = 0;
3015  if (__len1 > __len2)
3016  {
3017  __len11 = __len1 / 2;
3018  std::advance(__first_cut, __len11);
3019  __second_cut = std::lower_bound(__middle, __last, *__first_cut,
3020  __comp);
3021  __len22 = std::distance(__middle, __second_cut);
3022  }
3023  else
3024  {
3025  __len22 = __len2 / 2;
3026  std::advance(__second_cut, __len22);
3027  __first_cut = std::upper_bound(__first, __middle, *__second_cut,
3028  __comp);
3029  __len11 = std::distance(__first, __first_cut);
3030  }
3031  _BidirectionalIterator __new_middle =
3032  std::__rotate_adaptive(__first_cut, __middle, __second_cut,
3033  __len1 - __len11, __len22, __buffer,
3034  __buffer_size);
3035  std::__merge_adaptive(__first, __first_cut, __new_middle, __len11,
3036  __len22, __buffer, __buffer_size, __comp);
3037  std::__merge_adaptive(__new_middle, __second_cut, __last,
3038  __len1 - __len11,
3039  __len2 - __len22, __buffer,
3040  __buffer_size, __comp);
3041  }
3042  }
3043 
3045  template<typename _BidirectionalIterator, typename _Distance>
3046  void
3047  __merge_without_buffer(_BidirectionalIterator __first,
3048  _BidirectionalIterator __middle,
3049  _BidirectionalIterator __last,
3050  _Distance __len1, _Distance __len2)
3051  {
3052  if (__len1 == 0 || __len2 == 0)
3053  return;
3054  if (__len1 + __len2 == 2)
3055  {
3056  if (*__middle < *__first)
3057  std::iter_swap(__first, __middle);
3058  return;
3059  }
3060  _BidirectionalIterator __first_cut = __first;
3061  _BidirectionalIterator __second_cut = __middle;
3062  _Distance __len11 = 0;
3063  _Distance __len22 = 0;
3064  if (__len1 > __len2)
3065  {
3066  __len11 = __len1 / 2;
3067  std::advance(__first_cut, __len11);
3068  __second_cut = std::lower_bound(__middle, __last, *__first_cut);
3069  __len22 = std::distance(__middle, __second_cut);
3070  }
3071  else
3072  {
3073  __len22 = __len2 / 2;
3074  std::advance(__second_cut, __len22);
3075  __first_cut = std::upper_bound(__first, __middle, *__second_cut);
3076  __len11 = std::distance(__first, __first_cut);
3077  }
3078  std::rotate(__first_cut, __middle, __second_cut);
3079  _BidirectionalIterator __new_middle = __first_cut;
3080  std::advance(__new_middle, std::distance(__middle, __second_cut));
3081  std::__merge_without_buffer(__first, __first_cut, __new_middle,
3082  __len11, __len22);
3083  std::__merge_without_buffer(__new_middle, __second_cut, __last,
3084  __len1 - __len11, __len2 - __len22);
3085  }
3086 
3088  template<typename _BidirectionalIterator, typename _Distance,
3089  typename _Compare>
3090  void
3091  __merge_without_buffer(_BidirectionalIterator __first,
3092  _BidirectionalIterator __middle,
3093  _BidirectionalIterator __last,
3094  _Distance __len1, _Distance __len2,
3095  _Compare __comp)
3096  {
3097  if (__len1 == 0 || __len2 == 0)
3098  return;
3099  if (__len1 + __len2 == 2)
3100  {
3101  if (__comp(*__middle, *__first))
3102  std::iter_swap(__first, __middle);
3103  return;
3104  }
3105  _BidirectionalIterator __first_cut = __first;
3106  _BidirectionalIterator __second_cut = __middle;
3107  _Distance __len11 = 0;
3108  _Distance __len22 = 0;
3109  if (__len1 > __len2)
3110  {
3111  __len11 = __len1 / 2;
3112  std::advance(__first_cut, __len11);
3113  __second_cut = std::lower_bound(__middle, __last, *__first_cut,
3114  __comp);
3115  __len22 = std::distance(__middle, __second_cut);
3116  }
3117  else
3118  {
3119  __len22 = __len2 / 2;
3120  std::advance(__second_cut, __len22);
3121  __first_cut = std::upper_bound(__first, __middle, *__second_cut,
3122  __comp);
3123  __len11 = std::distance(__first, __first_cut);
3124  }
3125  std::rotate(__first_cut, __middle, __second_cut);
3126  _BidirectionalIterator __new_middle = __first_cut;
3127  std::advance(__new_middle, std::distance(__middle, __second_cut));
3128  std::__merge_without_buffer(__first, __first_cut, __new_middle,
3129  __len11, __len22, __comp);
3130  std::__merge_without_buffer(__new_middle, __second_cut, __last,
3131  __len1 - __len11, __len2 - __len22, __comp);
3132  }
3133 
3152  template<typename _BidirectionalIterator>
3153  void
3154  inplace_merge(_BidirectionalIterator __first,
3155  _BidirectionalIterator __middle,
3156  _BidirectionalIterator __last)
3157  {
3158  typedef typename iterator_traits<_BidirectionalIterator>::value_type
3159  _ValueType;
3160  typedef typename iterator_traits<_BidirectionalIterator>::difference_type
3161  _DistanceType;
3162 
3163  // concept requirements
3164  __glibcxx_function_requires(_Mutable_BidirectionalIteratorConcept<
3165  _BidirectionalIterator>)
3166  __glibcxx_function_requires(_LessThanComparableConcept<_ValueType>)
3167  __glibcxx_requires_sorted(__first, __middle);
3168  __glibcxx_requires_sorted(__middle, __last);
3169 
3170  if (__first == __middle || __middle == __last)
3171  return;
3172 
3173  _DistanceType __len1 = std::distance(__first, __middle);
3174  _DistanceType __len2 = std::distance(__middle, __last);
3175 
3176  _Temporary_buffer<_BidirectionalIterator, _ValueType> __buf(__first,
3177  __last);
3178  if (__buf.begin() == 0)
3179  std::__merge_without_buffer(__first, __middle, __last, __len1, __len2);
3180  else
3181  std::__merge_adaptive(__first, __middle, __last, __len1, __len2,
3182  __buf.begin(), _DistanceType(__buf.size()));
3183  }
3184 
3207  template<typename _BidirectionalIterator, typename _Compare>
3208  void
3209  inplace_merge(_BidirectionalIterator __first,
3210  _BidirectionalIterator __middle,
3211  _BidirectionalIterator __last,
3212  _Compare __comp)
3213  {
3214  typedef typename iterator_traits<_BidirectionalIterator>::value_type
3215  _ValueType;
3216  typedef typename iterator_traits<_BidirectionalIterator>::difference_type
3217  _DistanceType;
3218 
3219  // concept requirements
3220  __glibcxx_function_requires(_Mutable_BidirectionalIteratorConcept<
3221  _BidirectionalIterator>)
3222  __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
3223  _ValueType, _ValueType>)
3224  __glibcxx_requires_sorted_pred(__first, __middle, __comp);
3225  __glibcxx_requires_sorted_pred(__middle, __last, __comp);
3226 
3227  if (__first == __middle || __middle == __last)
3228  return;
3229 
3230  const _DistanceType __len1 = std::distance(__first, __middle);
3231  const _DistanceType __len2 = std::distance(__middle, __last);
3232 
3233  _Temporary_buffer<_BidirectionalIterator, _ValueType> __buf(__first,
3234  __last);
3235  if (__buf.begin() == 0)
3236  std::__merge_without_buffer(__first, __middle, __last, __len1,
3237  __len2, __comp);
3238  else
3239  std::__merge_adaptive(__first, __middle, __last, __len1, __len2,
3240  __buf.begin(), _DistanceType(__buf.size()),
3241  __comp);
3242  }
3243 
3244 
3246  template<typename _InputIterator1, typename _InputIterator2,
3247  typename _OutputIterator>
3248  _OutputIterator
3249  __move_merge(_InputIterator1 __first1, _InputIterator1 __last1,
3250  _InputIterator2 __first2, _InputIterator2 __last2,
3251  _OutputIterator __result)
3252  {
3253  while (__first1 != __last1 && __first2 != __last2)
3254  {
3255  if (*__first2 < *__first1)
3256  {
3257  *__result = _GLIBCXX_MOVE(*__first2);
3258  ++__first2;
3259  }
3260  else
3261  {
3262  *__result = _GLIBCXX_MOVE(*__first1);
3263  ++__first1;
3264  }
3265  ++__result;
3266  }
3267  return _GLIBCXX_MOVE3(__first2, __last2,
3268  _GLIBCXX_MOVE3(__first1, __last1,
3269  __result));
3270  }
3271 
3273  template<typename _InputIterator1, typename _InputIterator2,
3274  typename _OutputIterator, typename _Compare>
3275  _OutputIterator
3276  __move_merge(_InputIterator1 __first1, _InputIterator1 __last1,
3277  _InputIterator2 __first2, _InputIterator2 __last2,
3278  _OutputIterator __result, _Compare __comp)
3279  {
3280  while (__first1 != __last1 && __first2 != __last2)
3281  {
3282  if (__comp(*__first2, *__first1))
3283  {
3284  *__result = _GLIBCXX_MOVE(*__first2);
3285  ++__first2;
3286  }
3287  else
3288  {
3289  *__result = _GLIBCXX_MOVE(*__first1);
3290  ++__first1;
3291  }
3292  ++__result;
3293  }
3294  return _GLIBCXX_MOVE3(__first2, __last2,
3295  _GLIBCXX_MOVE3(__first1, __last1,
3296  __result));
3297  }
3298 
3299  template<typename _RandomAccessIterator1, typename _RandomAccessIterator2,
3300  typename _Distance>
3301  void
3302  __merge_sort_loop(_RandomAccessIterator1 __first,
3303  _RandomAccessIterator1 __last,
3304  _RandomAccessIterator2 __result,
3305  _Distance __step_size)
3306  {
3307  const _Distance __two_step = 2 * __step_size;
3308 
3309  while (__last - __first >= __two_step)
3310  {
3311  __result = std::__move_merge(__first, __first + __step_size,
3312  __first + __step_size,
3313  __first + __two_step, __result);
3314  __first += __two_step;
3315  }
3316 
3317  __step_size = std::min(_Distance(__last - __first), __step_size);
3318  std::__move_merge(__first, __first + __step_size,
3319  __first + __step_size, __last, __result);
3320  }
3321 
3322  template<typename _RandomAccessIterator1, typename _RandomAccessIterator2,
3323  typename _Distance, typename _Compare>
3324  void
3325  __merge_sort_loop(_RandomAccessIterator1 __first,
3326  _RandomAccessIterator1 __last,
3327  _RandomAccessIterator2 __result, _Distance __step_size,
3328  _Compare __comp)
3329  {
3330  const _Distance __two_step = 2 * __step_size;
3331 
3332  while (__last - __first >= __two_step)
3333  {
3334  __result = std::__move_merge(__first, __first + __step_size,
3335  __first + __step_size,
3336  __first + __two_step,
3337  __result, __comp);
3338  __first += __two_step;
3339  }
3340  __step_size = std::min(_Distance(__last - __first), __step_size);
3341 
3342  std::__move_merge(__first,__first + __step_size,
3343  __first + __step_size, __last, __result, __comp);
3344  }
3345 
3346  template<typename _RandomAccessIterator, typename _Distance>
3347  void
3348  __chunk_insertion_sort(_RandomAccessIterator __first,
3349  _RandomAccessIterator __last,
3350  _Distance __chunk_size)
3351  {
3352  while (__last - __first >= __chunk_size)
3353  {
3354  std::__insertion_sort(__first, __first + __chunk_size);
3355  __first += __chunk_size;
3356  }
3357  std::__insertion_sort(__first, __last);
3358  }
3359 
3360  template<typename _RandomAccessIterator, typename _Distance,
3361  typename _Compare>
3362  void
3363  __chunk_insertion_sort(_RandomAccessIterator __first,
3364  _RandomAccessIterator __last,
3365  _Distance __chunk_size, _Compare __comp)
3366  {
3367  while (__last - __first >= __chunk_size)
3368  {
3369  std::__insertion_sort(__first, __first + __chunk_size, __comp);
3370  __first += __chunk_size;
3371  }
3372  std::__insertion_sort(__first, __last, __comp);
3373  }
3374 
3375  enum { _S_chunk_size = 7 };
3376 
3377  template<typename _RandomAccessIterator, typename _Pointer>
3378  void
3379  __merge_sort_with_buffer(_RandomAccessIterator __first,
3380  _RandomAccessIterator __last,
3381  _Pointer __buffer)
3382  {
3383  typedef typename iterator_traits<_RandomAccessIterator>::difference_type
3384  _Distance;
3385 
3386  const _Distance __len = __last - __first;
3387  const _Pointer __buffer_last = __buffer + __len;
3388 
3389  _Distance __step_size = _S_chunk_size;
3390  std::__chunk_insertion_sort(__first, __last, __step_size);
3391 
3392  while (__step_size < __len)
3393  {
3394  std::__merge_sort_loop(__first, __last, __buffer, __step_size);
3395  __step_size *= 2;
3396  std::__merge_sort_loop(__buffer, __buffer_last, __first, __step_size);
3397  __step_size *= 2;
3398  }
3399  }
3400 
3401  template<typename _RandomAccessIterator, typename _Pointer, typename _Compare>
3402  void
3403  __merge_sort_with_buffer(_RandomAccessIterator __first,
3404  _RandomAccessIterator __last,
3405  _Pointer __buffer, _Compare __comp)
3406  {
3407  typedef typename iterator_traits<_RandomAccessIterator>::difference_type
3408  _Distance;
3409 
3410  const _Distance __len = __last - __first;
3411  const _Pointer __buffer_last = __buffer + __len;
3412 
3413  _Distance __step_size = _S_chunk_size;
3414  std::__chunk_insertion_sort(__first, __last, __step_size, __comp);
3415 
3416  while (__step_size < __len)
3417  {
3418  std::__merge_sort_loop(__first, __last, __buffer,
3419  __step_size, __comp);
3420  __step_size *= 2;
3421  std::__merge_sort_loop(__buffer, __buffer_last, __first,
3422  __step_size, __comp);
3423  __step_size *= 2;
3424  }
3425  }
3426 
3427  template<typename _RandomAccessIterator, typename _Pointer,
3428  typename _Distance>
3429  void
3430  __stable_sort_adaptive(_RandomAccessIterator __first,
3431  _RandomAccessIterator __last,
3432  _Pointer __buffer, _Distance __buffer_size)
3433  {
3434  const _Distance __len = (__last - __first + 1) / 2;
3435  const _RandomAccessIterator __middle = __first + __len;
3436  if (__len > __buffer_size)
3437  {
3438  std::__stable_sort_adaptive(__first, __middle,
3439  __buffer, __buffer_size);
3440  std::__stable_sort_adaptive(__middle, __last,
3441  __buffer, __buffer_size);
3442  }
3443  else
3444  {
3445  std::__merge_sort_with_buffer(__first, __middle, __buffer);
3446  std::__merge_sort_with_buffer(__middle, __last, __buffer);
3447  }
3448  std::__merge_adaptive(__first, __middle, __last,
3449  _Distance(__middle - __first),
3450  _Distance(__last - __middle),
3451  __buffer, __buffer_size);
3452  }
3453 
3454  template<typename _RandomAccessIterator, typename _Pointer,
3455  typename _Distance, typename _Compare>
3456  void
3457  __stable_sort_adaptive(_RandomAccessIterator __first,
3458  _RandomAccessIterator __last,
3459  _Pointer __buffer, _Distance __buffer_size,
3460  _Compare __comp)
3461  {
3462  const _Distance __len = (__last - __first + 1) / 2;
3463  const _RandomAccessIterator __middle = __first + __len;
3464  if (__len > __buffer_size)
3465  {
3466  std::__stable_sort_adaptive(__first, __middle, __buffer,
3467  __buffer_size, __comp);
3468  std::__stable_sort_adaptive(__middle, __last, __buffer,
3469  __buffer_size, __comp);
3470  }
3471  else
3472  {
3473  std::__merge_sort_with_buffer(__first, __middle, __buffer, __comp);
3474  std::__merge_sort_with_buffer(__middle, __last, __buffer, __comp);
3475  }
3476  std::__merge_adaptive(__first, __middle, __last,
3477  _Distance(__middle - __first),
3478  _Distance(__last - __middle),
3479  __buffer, __buffer_size,
3480  __comp);
3481  }
3482 
3484  template<typename _RandomAccessIterator>
3485  void
3486  __inplace_stable_sort(_RandomAccessIterator __first,
3487  _RandomAccessIterator __last)
3488  {
3489  if (__last - __first < 15)
3490  {
3491  std::__insertion_sort(__first, __last);
3492  return;
3493  }
3494  _RandomAccessIterator __middle = __first + (__last - __first) / 2;
3495  std::__inplace_stable_sort(__first, __middle);
3496  std::__inplace_stable_sort(__middle, __last);
3497  std::__merge_without_buffer(__first, __middle, __last,
3498  __middle - __first,
3499  __last - __middle);
3500  }
3501 
3503  template<typename _RandomAccessIterator, typename _Compare>
3504  void
3505  __inplace_stable_sort(_RandomAccessIterator __first,
3506  _RandomAccessIterator __last, _Compare __comp)
3507  {
3508  if (__last - __first < 15)
3509  {
3510  std::__insertion_sort(__first, __last, __comp);
3511  return;
3512  }
3513  _RandomAccessIterator __middle = __first + (__last - __first) / 2;
3514  std::__inplace_stable_sort(__first, __middle, __comp);
3515  std::__inplace_stable_sort(__middle, __last, __comp);
3516  std::__merge_without_buffer(__first, __middle, __last,
3517  __middle - __first,
3518  __last - __middle,
3519  __comp);
3520  }
3521 
3522  // stable_sort
3523 
3524  // Set algorithms: includes, set_union, set_intersection, set_difference,
3525  // set_symmetric_difference. All of these algorithms have the precondition
3526  // that their input ranges are sorted and the postcondition that their output
3527  // ranges are sorted.
3528 
3547  template<typename _InputIterator1, typename _InputIterator2>
3548  bool
3549  includes(_InputIterator1 __first1, _InputIterator1 __last1,
3550  _InputIterator2 __first2, _InputIterator2 __last2)
3551  {
3552  typedef typename iterator_traits<_InputIterator1>::value_type
3553  _ValueType1;
3554  typedef typename iterator_traits<_InputIterator2>::value_type
3555  _ValueType2;
3556 
3557  // concept requirements
3558  __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
3559  __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
3560  __glibcxx_function_requires(_LessThanOpConcept<_ValueType1, _ValueType2>)
3561  __glibcxx_function_requires(_LessThanOpConcept<_ValueType2, _ValueType1>)
3562  __glibcxx_requires_sorted_set(__first1, __last1, __first2);
3563  __glibcxx_requires_sorted_set(__first2, __last2, __first1);
3564 
3565  while (__first1 != __last1 && __first2 != __last2)
3566  if (*__first2 < *__first1)
3567  return false;
3568  else if(*__first1 < *__first2)
3569  ++__first1;
3570  else
3571  ++__first1, ++__first2;
3572 
3573  return __first2 == __last2;
3574  }
3575 
3597  template<typename _InputIterator1, typename _InputIterator2,
3598  typename _Compare>
3599  bool
3600  includes(_InputIterator1 __first1, _InputIterator1 __last1,
3601  _InputIterator2 __first2, _InputIterator2 __last2,
3602  _Compare __comp)
3603  {
3604  typedef typename iterator_traits<_InputIterator1>::value_type
3605  _ValueType1;
3606  typedef typename iterator_traits<_InputIterator2>::value_type
3607  _ValueType2;
3608 
3609  // concept requirements
3610  __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
3611  __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
3612  __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
3613  _ValueType1, _ValueType2>)
3614  __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
3615  _ValueType2, _ValueType1>)
3616  __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp);
3617  __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp);
3618 
3619  while (__first1 != __last1 && __first2 != __last2)
3620  if (__comp(*__first2, *__first1))
3621  return false;
3622  else if(__comp(*__first1, *__first2))
3623  ++__first1;
3624  else
3625  ++__first1, ++__first2;
3626 
3627  return __first2 == __last2;
3628  }
3629 
3630  // nth_element
3631  // merge
3632  // set_difference
3633  // set_intersection
3634  // set_union
3635  // stable_sort
3636  // set_symmetric_difference
3637  // min_element
3638  // max_element
3639 
3652  template<typename _BidirectionalIterator>
3653  bool
3654  next_permutation(_BidirectionalIterator __first,
3655  _BidirectionalIterator __last)
3656  {
3657  // concept requirements
3658  __glibcxx_function_requires(_BidirectionalIteratorConcept<
3659  _BidirectionalIterator>)
3660  __glibcxx_function_requires(_LessThanComparableConcept<
3661  typename iterator_traits<_BidirectionalIterator>::value_type>)
3662  __glibcxx_requires_valid_range(__first, __last);
3663 
3664  if (__first == __last)
3665  return false;
3666  _BidirectionalIterator __i = __first;
3667  ++__i;
3668  if (__i == __last)
3669  return false;
3670  __i = __last;
3671  --__i;
3672 
3673  for(;;)
3674  {
3675  _BidirectionalIterator __ii = __i;
3676  --__i;
3677  if (*__i < *__ii)
3678  {
3679  _BidirectionalIterator __j = __last;
3680  while (!(*__i < *--__j))
3681  {}
3682  std::iter_swap(__i, __j);
3683  std::reverse(__ii, __last);
3684  return true;
3685  }
3686  if (__i == __first)
3687  {
3688  std::reverse(__first, __last);
3689  return false;
3690  }
3691  }
3692  }
3693 
3709  template<typename _BidirectionalIterator, typename _Compare>
3710  bool
3711  next_permutation(_BidirectionalIterator __first,
3712  _BidirectionalIterator __last, _Compare __comp)
3713  {
3714  // concept requirements
3715  __glibcxx_function_requires(_BidirectionalIteratorConcept<
3716  _BidirectionalIterator>)
3717  __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
3718  typename iterator_traits<_BidirectionalIterator>::value_type,
3719  typename iterator_traits<_BidirectionalIterator>::value_type>)
3720  __glibcxx_requires_valid_range(__first, __last);
3721 
3722  if (__first == __last)
3723  return false;
3724  _BidirectionalIterator __i = __first;
3725  ++__i;
3726  if (__i == __last)
3727  return false;
3728  __i = __last;
3729  --__i;
3730 
3731  for(;;)
3732  {
3733  _BidirectionalIterator __ii = __i;
3734  --__i;
3735  if (__comp(*__i, *__ii))
3736  {
3737  _BidirectionalIterator __j = __last;
3738  while (!bool(__comp(*__i, *--__j)))
3739  {}
3740  std::iter_swap(__i, __j);
3741  std::reverse(__ii, __last);
3742  return true;
3743  }
3744  if (__i == __first)
3745  {
3746  std::reverse(__first, __last);
3747  return false;
3748  }
3749  }
3750  }
3751 
3765  template<typename _BidirectionalIterator>
3766  bool
3767  prev_permutation(_BidirectionalIterator __first,
3768  _BidirectionalIterator __last)
3769  {
3770  // concept requirements
3771  __glibcxx_function_requires(_BidirectionalIteratorConcept<
3772  _BidirectionalIterator>)
3773  __glibcxx_function_requires(_LessThanComparableConcept<
3774  typename iterator_traits<_BidirectionalIterator>::value_type>)
3775  __glibcxx_requires_valid_range(__first, __last);
3776 
3777  if (__first == __last)
3778  return false;
3779  _BidirectionalIterator __i = __first;
3780  ++__i;
3781  if (__i == __last)
3782  return false;
3783  __i = __last;
3784  --__i;
3785 
3786  for(;;)
3787  {
3788  _BidirectionalIterator __ii = __i;
3789  --__i;
3790  if (*__ii < *__i)
3791  {
3792  _BidirectionalIterator __j = __last;
3793  while (!(*--__j < *__i))
3794  {}
3795  std::iter_swap(__i, __j);
3796  std::reverse(__ii, __last);
3797  return true;
3798  }
3799  if (__i == __first)
3800  {
3801  std::reverse(__first, __last);
3802  return false;
3803  }
3804  }
3805  }
3806 
3822  template<typename _BidirectionalIterator, typename _Compare>
3823  bool
3824  prev_permutation(_BidirectionalIterator __first,
3825  _BidirectionalIterator __last, _Compare __comp)
3826  {
3827  // concept requirements
3828  __glibcxx_function_requires(_BidirectionalIteratorConcept<
3829  _BidirectionalIterator>)
3830  __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
3831  typename iterator_traits<_BidirectionalIterator>::value_type,
3832  typename iterator_traits<_BidirectionalIterator>::value_type>)
3833  __glibcxx_requires_valid_range(__first, __last);
3834 
3835  if (__first == __last)
3836  return false;
3837  _BidirectionalIterator __i = __first;
3838  ++__i;
3839  if (__i == __last)
3840  return false;
3841  __i = __last;
3842  --__i;
3843 
3844  for(;;)
3845  {
3846  _BidirectionalIterator __ii = __i;
3847  --__i;
3848  if (__comp(*__ii, *__i))
3849  {
3850  _BidirectionalIterator __j = __last;
3851  while (!bool(__comp(*--__j, *__i)))
3852  {}
3853  std::iter_swap(__i, __j);
3854  std::reverse(__ii, __last);
3855  return true;
3856  }
3857  if (__i == __first)
3858  {
3859  std::reverse(__first, __last);
3860  return false;
3861  }
3862  }
3863  }
3864 
3865  // replace
3866  // replace_if
3867 
3882  template<typename _InputIterator, typename _OutputIterator, typename _Tp>
3883  _OutputIterator
3884  replace_copy(_InputIterator __first, _InputIterator __last,
3885  _OutputIterator __result,
3886  const _Tp& __old_value, const _Tp& __new_value)
3887  {
3888  // concept requirements
3889  __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
3890  __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
3891  typename iterator_traits<_InputIterator>::value_type>)
3892  __glibcxx_function_requires(_EqualOpConcept<
3893  typename iterator_traits<_InputIterator>::value_type, _Tp>)
3894  __glibcxx_requires_valid_range(__first, __last);
3895 
3896  for (; __first != __last; ++__first, ++__result)
3897  if (*__first == __old_value)
3898  *__result = __new_value;
3899  else
3900  *__result = *__first;
3901  return __result;
3902  }
3903 
3919  template<typename _InputIterator, typename _OutputIterator,
3920  typename _Predicate, typename _Tp>
3921  _OutputIterator
3922  replace_copy_if(_InputIterator __first, _InputIterator __last,
3923  _OutputIterator __result,
3924  _Predicate __pred, const _Tp& __new_value)
3925  {
3926  // concept requirements
3927  __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
3928  __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
3929  typename iterator_traits<_InputIterator>::value_type>)
3930  __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
3931  typename iterator_traits<_InputIterator>::value_type>)
3932  __glibcxx_requires_valid_range(__first, __last);
3933 
3934  for (; __first != __last; ++__first, ++__result)
3935  if (__pred(*__first))
3936  *__result = __new_value;
3937  else
3938  *__result = *__first;
3939  return __result;
3940  }
3941 
3942 #if __cplusplus >= 201103L
3943 
3950  template<typename _ForwardIterator>
3951  inline bool
3952  is_sorted(_ForwardIterator __first, _ForwardIterator __last)
3953  { return std::is_sorted_until(__first, __last) == __last; }
3954 
3964  template<typename _ForwardIterator, typename _Compare>
3965  inline bool
3966  is_sorted(_ForwardIterator __first, _ForwardIterator __last,
3967  _Compare __comp)
3968  { return std::is_sorted_until(__first, __last, __comp) == __last; }
3969 
3978  template<typename _ForwardIterator>
3979  _ForwardIterator
3980  is_sorted_until(_ForwardIterator __first, _ForwardIterator __last)
3981  {
3982  // concept requirements
3983  __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
3984  __glibcxx_function_requires(_LessThanComparableConcept<
3985  typename iterator_traits<_ForwardIterator>::value_type>)
3986  __glibcxx_requires_valid_range(__first, __last);
3987 
3988  if (__first == __last)
3989  return __last;
3990 
3991  _ForwardIterator __next = __first;
3992  for (++__next; __next != __last; __first = __next, ++__next)
3993  if (*__next < *__first)
3994  return __next;
3995  return __next;
3996  }
3997 
4007  template<typename _ForwardIterator, typename _Compare>
4008  _ForwardIterator
4009  is_sorted_until(_ForwardIterator __first, _ForwardIterator __last,
4010  _Compare __comp)
4011  {
4012  // concept requirements
4013  __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
4014  __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
4015  typename iterator_traits<_ForwardIterator>::value_type,
4016  typename iterator_traits<_ForwardIterator>::value_type>)
4017  __glibcxx_requires_valid_range(__first, __last);
4018 
4019  if (__first == __last)
4020  return __last;
4021 
4022  _ForwardIterator __next = __first;
4023  for (++__next; __next != __last; __first = __next, ++__next)
4024  if (__comp(*__next, *__first))
4025  return __next;
4026  return __next;
4027  }
4028 
4037  template<typename _Tp>
4038  inline pair<const _Tp&, const _Tp&>
4039  minmax(const _Tp& __a, const _Tp& __b)
4040  {
4041  // concept requirements
4042  __glibcxx_function_requires(_LessThanComparableConcept<_Tp>)
4043 
4044  return __b < __a ? pair<const _Tp&, const _Tp&>(__b, __a)
4045  : pair<const _Tp&, const _Tp&>(__a, __b);
4046  }
4047 
4057  template<typename _Tp, typename _Compare>
4058  inline pair<const _Tp&, const _Tp&>
4059  minmax(const _Tp& __a, const _Tp& __b, _Compare __comp)
4060  {
4061  return __comp(__b, __a) ? pair<const _Tp&, const _Tp&>(__b, __a)
4062  : pair<const _Tp&, const _Tp&>(__a, __b);
4063  }
4064 
4076  template<typename _ForwardIterator>
4077  pair<_ForwardIterator, _ForwardIterator>
4078  minmax_element(_ForwardIterator __first, _ForwardIterator __last)
4079  {
4080  // concept requirements
4081  __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
4082  __glibcxx_function_requires(_LessThanComparableConcept<
4083  typename iterator_traits<_ForwardIterator>::value_type>)
4084  __glibcxx_requires_valid_range(__first, __last);
4085 
4086  _ForwardIterator __next = __first;
4087  if (__first == __last
4088  || ++__next == __last)
4089  return std::make_pair(__first, __first);
4090 
4091  _ForwardIterator __min, __max;
4092  if (*__next < *__first)
4093  {
4094  __min = __next;
4095  __max = __first;
4096  }
4097  else
4098  {
4099  __min = __first;
4100  __max = __next;
4101  }
4102 
4103  __first = __next;
4104  ++__first;
4105 
4106  while (__first != __last)
4107  {
4108  __next = __first;
4109  if (++__next == __last)
4110  {
4111  if (*__first < *__min)
4112  __min = __first;
4113  else if (!(*__first < *__max))
4114  __max = __first;
4115  break;
4116  }
4117 
4118  if (*__next < *__first)
4119  {
4120  if (*__next < *__min)
4121  __min = __next;
4122  if (!(*__first < *__max))
4123  __max = __first;
4124  }
4125  else
4126  {
4127  if (*__first < *__min)
4128  __min = __first;
4129  if (!(*__next < *__max))
4130  __max = __next;
4131  }
4132 
4133  __first = __next;
4134  ++__first;
4135  }
4136 
4137  return std::make_pair(__min, __max);
4138  }
4139 
4152  template<typename _ForwardIterator, typename _Compare>
4153  pair<_ForwardIterator, _ForwardIterator>
4154  minmax_element(_ForwardIterator __first, _ForwardIterator __last,
4155  _Compare __comp)
4156  {
4157  // concept requirements
4158  __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
4159  __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
4160  typename iterator_traits<_ForwardIterator>::value_type,
4161  typename iterator_traits<_ForwardIterator>::value_type>)
4162  __glibcxx_requires_valid_range(__first, __last);
4163 
4164  _ForwardIterator __next = __first;
4165  if (__first == __last
4166  || ++__next == __last)
4167  return std::make_pair(__first, __first);
4168 
4169  _ForwardIterator __min, __max;
4170  if (__comp(*__next, *__first))
4171  {
4172  __min = __next;
4173  __max = __first;
4174  }
4175  else
4176  {
4177  __min = __first;
4178  __max = __next;
4179  }
4180 
4181  __first = __next;
4182  ++__first;
4183 
4184  while (__first != __last)
4185  {
4186  __next = __first;
4187  if (++__next == __last)
4188  {
4189  if (__comp(*__first, *__min))
4190  __min = __first;
4191  else if (!__comp(*__first, *__max))
4192  __max = __first;
4193  break;
4194  }
4195 
4196  if (__comp(*__next, *__first))
4197  {
4198  if (__comp(*__next, *__min))
4199  __min = __next;
4200  if (!__comp(*__first, *__max))
4201  __max = __first;
4202  }
4203  else
4204  {
4205  if (__comp(*__first, *__min))
4206  __min = __first;
4207  if (!__comp(*__next, *__max))
4208  __max = __next;
4209  }
4210 
4211  __first = __next;
4212  ++__first;
4213  }
4214 
4215  return std::make_pair(__min, __max);
4216  }
4217 
4218  // N2722 + DR 915.
4219  template<typename _Tp>
4220  inline _Tp
4221  min(initializer_list<_Tp> __l)
4222  { return *std::min_element(__l.begin(), __l.end()); }
4223 
4224  template<typename _Tp, typename _Compare>
4225  inline _Tp
4226  min(initializer_list<_Tp> __l, _Compare __comp)
4227  { return *std::min_element(__l.begin(), __l.end(), __comp); }
4228 
4229  template<typename _Tp>
4230  inline _Tp
4231  max(initializer_list<_Tp> __l)
4232  { return *std::max_element(__l.begin(), __l.end()); }
4233 
4234  template<typename _Tp, typename _Compare>
4235  inline _Tp
4236  max(initializer_list<_Tp> __l, _Compare __comp)
4237  { return *std::max_element(__l.begin(), __l.end(), __comp); }
4238 
4239  template<typename _Tp>
4240  inline pair<_Tp, _Tp>
4241  minmax(initializer_list<_Tp> __l)
4242  {
4243  pair<const _Tp*, const _Tp*> __p =
4244  std::minmax_element(__l.begin(), __l.end());
4245  return std::make_pair(*__p.first, *__p.second);
4246  }
4247 
4248  template<typename _Tp, typename _Compare>
4249  inline pair<_Tp, _Tp>
4250  minmax(initializer_list<_Tp> __l, _Compare __comp)
4251  {
4252  pair<const _Tp*, const _Tp*> __p =
4253  std::minmax_element(__l.begin(), __l.end(), __comp);
4254  return std::make_pair(*__p.first, *__p.second);
4255  }
4256 
4269  template<typename _ForwardIterator1, typename _ForwardIterator2>
4270  bool
4271  is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
4272  _ForwardIterator2 __first2)
4273  {
4274  // Efficiently compare identical prefixes: O(N) if sequences
4275  // have the same elements in the same order.
4276  for (; __first1 != __last1; ++__first1, ++__first2)
4277  if (!(*__first1 == *__first2))
4278  break;
4279 
4280  if (__first1 == __last1)
4281  return true;
4282 
4283  // Establish __last2 assuming equal ranges by iterating over the
4284  // rest of the list.
4285  _ForwardIterator2 __last2 = __first2;
4286  std::advance(__last2, std::distance(__first1, __last1));
4287  for (_ForwardIterator1 __scan = __first1; __scan != __last1; ++__scan)
4288  {
4289  if (__scan != _GLIBCXX_STD_A::find(__first1, __scan, *__scan))
4290  continue; // We've seen this one before.
4291 
4292  auto __matches = std::count(__first2, __last2, *__scan);
4293  if (0 == __matches
4294  || std::count(__scan, __last1, *__scan) != __matches)
4295  return false;
4296  }
4297  return true;
4298  }
4299 
4314  template<typename _ForwardIterator1, typename _ForwardIterator2,
4315  typename _BinaryPredicate>
4316  bool
4317  is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
4318  _ForwardIterator2 __first2, _BinaryPredicate __pred)
4319  {
4320  // Efficiently compare identical prefixes: O(N) if sequences
4321  // have the same elements in the same order.
4322  for (; __first1 != __last1; ++__first1, ++__first2)
4323  if (!bool(__pred(*__first1, *__first2)))
4324  break;
4325 
4326  if (__first1 == __last1)
4327  return true;
4328 
4329  // Establish __last2 assuming equal ranges by iterating over the
4330  // rest of the list.
4331  _ForwardIterator2 __last2 = __first2;
4332  std::advance(__last2, std::distance(__first1, __last1));
4333  for (_ForwardIterator1 __scan = __first1; __scan != __last1; ++__scan)
4334  {
4335  using std::placeholders::_1;
4336 
4337  if (__scan != _GLIBCXX_STD_A::find_if(__first1, __scan,
4338  std::bind(__pred, _1, *__scan)))
4339  continue; // We've seen this one before.
4340 
4341  auto __matches = std::count_if(__first2, __last2,
4342  std::bind(__pred, _1, *__scan));
4343  if (0 == __matches
4344  || std::count_if(__scan, __last1,
4345  std::bind(__pred, _1, *__scan)) != __matches)
4346  return false;
4347  }
4348  return true;
4349  }
4350 
4351 #ifdef _GLIBCXX_USE_C99_STDINT_TR1
4352 
4364  template<typename _RandomAccessIterator,
4365  typename _UniformRandomNumberGenerator>
4366  void
4367  shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last,
4368  _UniformRandomNumberGenerator&& __g)
4369  {
4370  // concept requirements
4371  __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
4372  _RandomAccessIterator>)
4373  __glibcxx_requires_valid_range(__first, __last);
4374 
4375  if (__first == __last)
4376  return;
4377 
4378  typedef typename iterator_traits<_RandomAccessIterator>::difference_type
4379  _DistanceType;
4380 
4381  typedef typename std::make_unsigned<_DistanceType>::type __ud_type;
4382  typedef typename std::uniform_int_distribution<__ud_type> __distr_type;
4383  typedef typename __distr_type::param_type __p_type;
4384  __distr_type __d;
4385 
4386  for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i)
4387  std::iter_swap(__i, __first + __d(__g, __p_type(0, __i - __first)));
4388  }
4389 #endif
4390 
4391 #endif // C++11
4392 
4393 _GLIBCXX_END_NAMESPACE_VERSION
4394 
4395 _GLIBCXX_BEGIN_NAMESPACE_ALGO
4396 
4409  template<typename _InputIterator, typename _Function>
4410  _Function
4411  for_each(_InputIterator __first, _InputIterator __last, _Function __f)
4412  {
4413  // concept requirements
4414  __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
4415  __glibcxx_requires_valid_range(__first, __last);
4416  for (; __first != __last; ++__first)
4417  __f(*__first);
4418  return _GLIBCXX_MOVE(__f);
4419  }
4420 
4430  template<typename _InputIterator, typename _Tp>
4431  inline _InputIterator
4432  find(_InputIterator __first, _InputIterator __last,
4433  const _Tp& __val)
4434  {
4435  // concept requirements
4436  __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
4437  __glibcxx_function_requires(_EqualOpConcept<
4438  typename iterator_traits<_InputIterator>::value_type, _Tp>)
4439  __glibcxx_requires_valid_range(__first, __last);
4440  return std::__find(__first, __last, __val,
4441  std::__iterator_category(__first));
4442  }
4443 
4454  template<typename _InputIterator, typename _Predicate>
4455  inline _InputIterator
4456  find_if(_InputIterator __first, _InputIterator __last,
4457  _Predicate __pred)
4458  {
4459  // concept requirements
4460  __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
4461  __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
4462  typename iterator_traits<_InputIterator>::value_type>)
4463  __glibcxx_requires_valid_range(__first, __last);
4464  return std::__find_if(__first, __last, __pred,
4465  std::__iterator_category(__first));
4466  }
4467 
4484  template<typename _InputIterator, typename _ForwardIterator>
4485  _InputIterator
4486  find_first_of(_InputIterator __first1, _InputIterator __last1,
4487  _ForwardIterator __first2, _ForwardIterator __last2)
4488  {
4489  // concept requirements
4490  __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
4491  __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
4492  __glibcxx_function_requires(_EqualOpConcept<
4493  typename iterator_traits<_InputIterator>::value_type,
4494  typename iterator_traits<_ForwardIterator>::value_type>)
4495  __glibcxx_requires_valid_range(__first1, __last1);
4496  __glibcxx_requires_valid_range(__first2, __last2);
4497 
4498  for (; __first1 != __last1; ++__first1)
4499  for (_ForwardIterator __iter = __first2; __iter != __last2; ++__iter)
4500  if (*__first1 == *__iter)
4501  return __first1;
4502  return __last1;
4503  }
4504 
4524  template<typename _InputIterator, typename _ForwardIterator,
4525  typename _BinaryPredicate>
4526  _InputIterator
4527  find_first_of(_InputIterator __first1, _InputIterator __last1,
4528  _ForwardIterator __first2, _ForwardIterator __last2,
4529  _BinaryPredicate __comp)
4530  {
4531  // concept requirements
4532  __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
4533  __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
4534  __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
4535  typename iterator_traits<_InputIterator>::value_type,
4536  typename iterator_traits<_ForwardIterator>::value_type>)
4537  __glibcxx_requires_valid_range(__first1, __last1);
4538  __glibcxx_requires_valid_range(__first2, __last2);
4539 
4540  for (; __first1 != __last1; ++__first1)
4541  for (_ForwardIterator __iter = __first2; __iter != __last2; ++__iter)
4542  if (__comp(*__first1, *__iter))
4543  return __first1;
4544  return __last1;
4545  }
4546 
4556  template<typename _ForwardIterator>
4557  _ForwardIterator
4558  adjacent_find(_ForwardIterator __first, _ForwardIterator __last)
4559  {
4560  // concept requirements
4561  __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
4562  __glibcxx_function_requires(_EqualityComparableConcept<
4563  typename iterator_traits<_ForwardIterator>::value_type>)
4564  __glibcxx_requires_valid_range(__first, __last);
4565  if (__first == __last)
4566  return __last;
4567  _ForwardIterator __next = __first;
4568  while(++__next != __last)
4569  {
4570  if (*__first == *__next)
4571  return __first;
4572  __first = __next;
4573  }
4574  return __last;
4575  }
4576 
4588  template<typename _ForwardIterator, typename _BinaryPredicate>
4589  _ForwardIterator
4590  adjacent_find(_ForwardIterator __first, _ForwardIterator __last,
4591  _BinaryPredicate __binary_pred)
4592  {
4593  // concept requirements
4594  __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
4595  __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
4596  typename iterator_traits<_ForwardIterator>::value_type,
4597  typename iterator_traits<_ForwardIterator>::value_type>)
4598  __glibcxx_requires_valid_range(__first, __last);
4599  if (__first == __last)
4600  return __last;
4601  _ForwardIterator __next = __first;
4602  while(++__next != __last)
4603  {
4604  if (__binary_pred(*__first, *__next))
4605  return __first;
4606  __first = __next;
4607  }
4608  return __last;
4609  }
4610 
4620  template<typename _InputIterator, typename _Tp>
4621  typename iterator_traits<_InputIterator>::difference_type
4622  count(_InputIterator __first, _InputIterator __last, const _Tp& __value)
4623  {
4624  // concept requirements
4625  __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
4626  __glibcxx_function_requires(_EqualOpConcept<
4627  typename iterator_traits<_InputIterator>::value_type, _Tp>)
4628  __glibcxx_requires_valid_range(__first, __last);
4629  typename iterator_traits<_InputIterator>::difference_type __n = 0;
4630  for (; __first != __last; ++__first)
4631  if (*__first == __value)
4632  ++__n;
4633  return __n;
4634  }
4635 
4645  template<typename _InputIterator, typename _Predicate>
4646  typename iterator_traits<_InputIterator>::difference_type
4647  count_if(_InputIterator __first, _InputIterator __last, _Predicate __pred)
4648  {
4649  // concept requirements
4650  __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
4651  __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
4652  typename iterator_traits<_InputIterator>::value_type>)
4653  __glibcxx_requires_valid_range(__first, __last);
4654  typename iterator_traits<_InputIterator>::difference_type __n = 0;
4655  for (; __first != __last; ++__first)
4656  if (__pred(*__first))
4657  ++__n;
4658  return __n;
4659  }
4660 
4687  template<typename _ForwardIterator1, typename _ForwardIterator2>
4688  _ForwardIterator1
4689  search(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
4690  _ForwardIterator2 __first2, _ForwardIterator2 __last2)
4691  {
4692  // concept requirements
4693  __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator1>)
4694  __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator2>)
4695  __glibcxx_function_requires(_EqualOpConcept<
4696  typename iterator_traits<_ForwardIterator1>::value_type,
4697  typename iterator_traits<_ForwardIterator2>::value_type>)
4698  __glibcxx_requires_valid_range(__first1, __last1);
4699  __glibcxx_requires_valid_range(__first2, __last2);
4700 
4701  // Test for empty ranges
4702  if (__first1 == __last1 || __first2 == __last2)
4703  return __first1;
4704 
4705  // Test for a pattern of length 1.
4706  _ForwardIterator2 __p1(__first2);
4707  if (++__p1 == __last2)
4708  return _GLIBCXX_STD_A::find(__first1, __last1, *__first2);
4709 
4710  // General case.
4711  _ForwardIterator2 __p;
4712  _ForwardIterator1 __current = __first1;
4713 
4714  for (;;)
4715  {
4716  __first1 = _GLIBCXX_STD_A::find(__first1, __last1, *__first2);
4717  if (__first1 == __last1)
4718  return __last1;
4719 
4720  __p = __p1;
4721  __current = __first1;
4722  if (++__current == __last1)
4723  return __last1;
4724 
4725  while (*__current == *__p)
4726  {
4727  if (++__p == __last2)
4728  return __first1;
4729  if (++__current == __last1)
4730  return __last1;
4731  }
4732  ++__first1;
4733  }
4734  return __first1;
4735  }
4736 
4758  template<typename _ForwardIterator1, typename _ForwardIterator2,
4759  typename _BinaryPredicate>
4760  _ForwardIterator1
4761  search(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
4762  _ForwardIterator2 __first2, _ForwardIterator2 __last2,
4763  _BinaryPredicate __predicate)
4764  {
4765  // concept requirements
4766  __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator1>)
4767  __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator2>)
4768  __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
4769  typename iterator_traits<_ForwardIterator1>::value_type,
4770  typename iterator_traits<_ForwardIterator2>::value_type>)
4771  __glibcxx_requires_valid_range(__first1, __last1);
4772  __glibcxx_requires_valid_range(__first2, __last2);
4773 
4774  // Test for empty ranges
4775  if (__first1 == __last1 || __first2 == __last2)
4776  return __first1;
4777 
4778  // Test for a pattern of length 1.
4779  _ForwardIterator2 __p1(__first2);
4780  if (++__p1 == __last2)
4781  {
4782  while (__first1 != __last1
4783  && !bool(__predicate(*__first1, *__first2)))
4784  ++__first1;
4785  return __first1;
4786  }
4787 
4788  // General case.
4789  _ForwardIterator2 __p;
4790  _ForwardIterator1 __current = __first1;
4791 
4792  for (;;)
4793  {
4794  while (__first1 != __last1
4795  && !bool(__predicate(*__first1, *__first2)))
4796  ++__first1;
4797  if (__first1 == __last1)
4798  return __last1;
4799 
4800  __p = __p1;
4801  __current = __first1;
4802  if (++__current == __last1)
4803  return __last1;
4804 
4805  while (__predicate(*__current, *__p))
4806  {
4807  if (++__p == __last2)
4808  return __first1;
4809  if (++__current == __last1)
4810  return __last1;
4811  }
4812  ++__first1;
4813  }
4814  return __first1;
4815  }
4816 
4817 
4833  template<typename _ForwardIterator, typename _Integer, typename _Tp>
4834  _ForwardIterator
4835  search_n(_ForwardIterator __first, _ForwardIterator __last,
4836  _Integer __count, const _Tp& __val)
4837  {
4838  // concept requirements
4839  __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
4840  __glibcxx_function_requires(_EqualOpConcept<
4841  typename iterator_traits<_ForwardIterator>::value_type, _Tp>)
4842  __glibcxx_requires_valid_range(__first, __last);
4843 
4844  if (__count <= 0)
4845  return __first;
4846  if (__count == 1)
4847  return _GLIBCXX_STD_A::find(__first, __last, __val);
4848  return std::__search_n(__first, __last, __count, __val,
4849  std::__iterator_category(__first));
4850  }
4851 
4852 
4870  template<typename _ForwardIterator, typename _Integer, typename _Tp,
4871  typename _BinaryPredicate>
4872  _ForwardIterator
4873  search_n(_ForwardIterator __first, _ForwardIterator __last,
4874  _Integer __count, const _Tp& __val,
4875  _BinaryPredicate __binary_pred)
4876  {
4877  // concept requirements
4878  __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
4879  __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
4880  typename iterator_traits<_ForwardIterator>::value_type, _Tp>)
4881  __glibcxx_requires_valid_range(__first, __last);
4882 
4883  if (__count <= 0)
4884  return __first;
4885  if (__count == 1)
4886  {
4887  while (__first != __last && !bool(__binary_pred(*__first, __val)))
4888  ++__first;
4889  return __first;
4890  }
4891  return std::__search_n(__first, __last, __count, __val, __binary_pred,
4892  std::__iterator_category(__first));
4893  }
4894 
4895 
4912  template<typename _InputIterator, typename _OutputIterator,
4913  typename _UnaryOperation>
4914  _OutputIterator
4915  transform(_InputIterator __first, _InputIterator __last,
4916  _OutputIterator __result, _UnaryOperation __unary_op)
4917  {
4918  // concept requirements
4919  __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
4920  __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
4921  // "the type returned by a _UnaryOperation"
4922  __typeof__(__unary_op(*__first))>)
4923  __glibcxx_requires_valid_range(__first, __last);
4924 
4925  for (; __first != __last; ++__first, ++__result)
4926  *__result = __unary_op(*__first);
4927  return __result;
4928  }
4929 
4949  template<typename _InputIterator1, typename _InputIterator2,
4950  typename _OutputIterator, typename _BinaryOperation>
4951  _OutputIterator
4952  transform(_InputIterator1 __first1, _InputIterator1 __last1,
4953  _InputIterator2 __first2, _OutputIterator __result,
4954  _BinaryOperation __binary_op)
4955  {
4956  // concept requirements
4957  __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
4958  __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
4959  __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
4960  // "the type returned by a _BinaryOperation"
4961  __typeof__(__binary_op(*__first1,*__first2))>)
4962  __glibcxx_requires_valid_range(__first1, __last1);
4963 
4964  for (; __first1 != __last1; ++__first1, ++__first2, ++__result)
4965  *__result = __binary_op(*__first1, *__first2);
4966  return __result;
4967  }
4968 
4982  template<typename _ForwardIterator, typename _Tp>
4983  void
4984  replace(_ForwardIterator __first, _ForwardIterator __last,
4985  const _Tp& __old_value, const _Tp& __new_value)
4986  {
4987  // concept requirements
4988  __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
4989  _ForwardIterator>)
4990  __glibcxx_function_requires(_EqualOpConcept<
4991  typename iterator_traits<_ForwardIterator>::value_type, _Tp>)
4992  __glibcxx_function_requires(_ConvertibleConcept<_Tp,
4993  typename iterator_traits<_ForwardIterator>::value_type>)
4994  __glibcxx_requires_valid_range(__first, __last);
4995 
4996  for (; __first != __last; ++__first)
4997  if (*__first == __old_value)
4998  *__first = __new_value;
4999  }
5000 
5014  template<typename _ForwardIterator, typename _Predicate, typename _Tp>
5015  void
5016  replace_if(_ForwardIterator __first, _ForwardIterator __last,
5017  _Predicate __pred, const _Tp& __new_value)
5018  {
5019  // concept requirements
5020  __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
5021  _ForwardIterator>)
5022  __glibcxx_function_requires(_ConvertibleConcept<_Tp,
5023  typename iterator_traits<_ForwardIterator>::value_type>)
5024  __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
5025  typename iterator_traits<_ForwardIterator>::value_type>)
5026  __glibcxx_requires_valid_range(__first, __last);
5027 
5028  for (; __first != __last; ++__first)
5029  if (__pred(*__first))
5030  *__first = __new_value;
5031  }
5032 
5046  template<typename _ForwardIterator, typename _Generator>
5047  void
5048  generate(_ForwardIterator __first, _ForwardIterator __last,
5049  _Generator __gen)
5050  {
5051  // concept requirements
5052  __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
5053  __glibcxx_function_requires(_GeneratorConcept<_Generator,
5054  typename iterator_traits<_ForwardIterator>::value_type>)
5055  __glibcxx_requires_valid_range(__first, __last);
5056 
5057  for (; __first != __last; ++__first)
5058  *__first = __gen();
5059  }
5060 
5077  template<typename _OutputIterator, typename _Size, typename _Generator>
5078  _OutputIterator
5079  generate_n(_OutputIterator __first, _Size __n, _Generator __gen)
5080  {
5081  // concept requirements
5082  __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5083  // "the type returned by a _Generator"
5084  __typeof__(__gen())>)
5085 
5086  for (__decltype(__n + 0) __niter = __n;
5087  __niter > 0; --__niter, ++__first)
5088  *__first = __gen();
5089  return __first;
5090  }
5091 
5092 
5114  template<typename _InputIterator, typename _OutputIterator>
5115  inline _OutputIterator
5116  unique_copy(_InputIterator __first, _InputIterator __last,
5117  _OutputIterator __result)
5118  {
5119  // concept requirements
5120  __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
5121  __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5122  typename iterator_traits<_InputIterator>::value_type>)
5123  __glibcxx_function_requires(_EqualityComparableConcept<
5124  typename iterator_traits<_InputIterator>::value_type>)
5125  __glibcxx_requires_valid_range(__first, __last);
5126 
5127  if (__first == __last)
5128  return __result;
5129  return std::__unique_copy(__first, __last, __result,
5130  std::__iterator_category(__first),
5131  std::__iterator_category(__result));
5132  }
5133 
5153  template<typename _InputIterator, typename _OutputIterator,
5154  typename _BinaryPredicate>
5155  inline _OutputIterator
5156  unique_copy(_InputIterator __first, _InputIterator __last,
5157  _OutputIterator __result,
5158  _BinaryPredicate __binary_pred)
5159  {
5160  // concept requirements -- predicates checked later
5161  __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
5162  __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5163  typename iterator_traits<_InputIterator>::value_type>)
5164  __glibcxx_requires_valid_range(__first, __last);
5165 
5166  if (__first == __last)
5167  return __result;
5168  return std::__unique_copy(__first, __last, __result, __binary_pred,
5169  std::__iterator_category(__first),
5170  std::__iterator_category(__result));
5171  }
5172 
5173 
5185  template<typename _RandomAccessIterator>
5186  inline void
5187  random_shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last)
5188  {
5189  // concept requirements
5190  __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
5191  _RandomAccessIterator>)
5192  __glibcxx_requires_valid_range(__first, __last);
5193 
5194  if (__first != __last)
5195  for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i)
5196  {
5197  _RandomAccessIterator __j = __first
5198  + std::rand() % ((__i - __first) + 1);
5199  if (__i != __j)
5200  std::iter_swap(__i, __j);
5201  }
5202  }
5203 
5218  template<typename _RandomAccessIterator, typename _RandomNumberGenerator>
5219  void
5220  random_shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last,
5221 #if __cplusplus >= 201103L
5222  _RandomNumberGenerator&& __rand)
5223 #else
5224  _RandomNumberGenerator& __rand)
5225 #endif
5226  {
5227  // concept requirements
5228  __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
5229  _RandomAccessIterator>)
5230  __glibcxx_requires_valid_range(__first, __last);
5231 
5232  if (__first == __last)
5233  return;
5234  for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i)
5235  {
5236  _RandomAccessIterator __j = __first + __rand((__i - __first) + 1);
5237  if (__i != __j)
5238  std::iter_swap(__i, __j);
5239  }
5240  }
5241 
5242 
5258  template<typename _ForwardIterator, typename _Predicate>
5259  inline _ForwardIterator
5260  partition(_ForwardIterator __first, _ForwardIterator __last,
5261  _Predicate __pred)
5262  {
5263  // concept requirements
5264  __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
5265  _ForwardIterator>)
5266  __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
5267  typename iterator_traits<_ForwardIterator>::value_type>)
5268  __glibcxx_requires_valid_range(__first, __last);
5269 
5270  return std::__partition(__first, __last, __pred,
5271  std::__iterator_category(__first));
5272  }
5273 
5274 
5275 
5292  template<typename _RandomAccessIterator>
5293  inline void
5294  partial_sort(_RandomAccessIterator __first,
5295  _RandomAccessIterator __middle,
5296  _RandomAccessIterator __last)
5297  {
5298  typedef typename iterator_traits<_RandomAccessIterator>::value_type
5299  _ValueType;
5300 
5301  // concept requirements
5302  __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
5303  _RandomAccessIterator>)
5304  __glibcxx_function_requires(_LessThanComparableConcept<_ValueType>)
5305  __glibcxx_requires_valid_range(__first, __middle);
5306  __glibcxx_requires_valid_range(__middle, __last);
5307 
5308  std::__heap_select(__first, __middle, __last);
5309  std::sort_heap(__first, __middle);
5310  }
5311 
5331  template<typename _RandomAccessIterator, typename _Compare>
5332  inline void
5333  partial_sort(_RandomAccessIterator __first,
5334  _RandomAccessIterator __middle,
5335  _RandomAccessIterator __last,
5336  _Compare __comp)
5337  {
5338  typedef typename iterator_traits<_RandomAccessIterator>::value_type
5339  _ValueType;
5340 
5341  // concept requirements
5342  __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
5343  _RandomAccessIterator>)
5344  __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5345  _ValueType, _ValueType>)
5346  __glibcxx_requires_valid_range(__first, __middle);
5347  __glibcxx_requires_valid_range(__middle, __last);
5348 
5349  std::__heap_select(__first, __middle, __last, __comp);
5350  std::sort_heap(__first, __middle, __comp);
5351  }
5352 
5368  template<typename _RandomAccessIterator>
5369  inline void
5370  nth_element(_RandomAccessIterator __first, _RandomAccessIterator __nth,
5371  _RandomAccessIterator __last)
5372  {
5373  typedef typename iterator_traits<_RandomAccessIterator>::value_type
5374  _ValueType;
5375 
5376  // concept requirements
5377  __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
5378  _RandomAccessIterator>)
5379  __glibcxx_function_requires(_LessThanComparableConcept<_ValueType>)
5380  __glibcxx_requires_valid_range(__first, __nth);
5381  __glibcxx_requires_valid_range(__nth, __last);
5382 
5383  if (__first == __last || __nth == __last)
5384  return;
5385 
5386  std::__introselect(__first, __nth, __last,
5387  std::__lg(__last - __first) * 2);
5388  }
5389 
5407  template<typename _RandomAccessIterator, typename _Compare>
5408  inline void
5409  nth_element(_RandomAccessIterator __first, _RandomAccessIterator __nth,
5410  _RandomAccessIterator __last, _Compare __comp)
5411  {
5412  typedef typename iterator_traits<_RandomAccessIterator>::value_type
5413  _ValueType;
5414 
5415  // concept requirements
5416  __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
5417  _RandomAccessIterator>)
5418  __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5419  _ValueType, _ValueType>)
5420  __glibcxx_requires_valid_range(__first, __nth);
5421  __glibcxx_requires_valid_range(__nth, __last);
5422 
5423  if (__first == __last || __nth == __last)
5424  return;
5425 
5426  std::__introselect(__first, __nth, __last,
5427  std::__lg(__last - __first) * 2, __comp);
5428  }
5429 
5430 
5445  template<typename _RandomAccessIterator>
5446  inline void
5447  sort(_RandomAccessIterator __first, _RandomAccessIterator __last)
5448  {
5449  typedef typename iterator_traits<_RandomAccessIterator>::value_type
5450  _ValueType;
5451 
5452  // concept requirements
5453  __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
5454  _RandomAccessIterator>)
5455  __glibcxx_function_requires(_LessThanComparableConcept<_ValueType>)
5456  __glibcxx_requires_valid_range(__first, __last);
5457 
5458  if (__first != __last)
5459  {
5460  std::__introsort_loop(__first, __last,
5461  std::__lg(__last - __first) * 2);
5462  std::__final_insertion_sort(__first, __last);
5463  }
5464  }
5465 
5481  template<typename _RandomAccessIterator, typename _Compare>
5482  inline void
5483  sort(_RandomAccessIterator __first, _RandomAccessIterator __last,
5484  _Compare __comp)
5485  {
5486  typedef typename iterator_traits<_RandomAccessIterator>::value_type
5487  _ValueType;
5488 
5489  // concept requirements
5490  __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
5491  _RandomAccessIterator>)
5492  __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, _ValueType,
5493  _ValueType>)
5494  __glibcxx_requires_valid_range(__first, __last);
5495 
5496  if (__first != __last)
5497  {
5498  std::__introsort_loop(__first, __last,
5499  std::__lg(__last - __first) * 2, __comp);
5500  std::__final_insertion_sort(__first, __last, __comp);
5501  }
5502  }
5503 
5523  template<typename _InputIterator1, typename _InputIterator2,
5524  typename _OutputIterator>
5525  _OutputIterator
5526  merge(_InputIterator1 __first1, _InputIterator1 __last1,
5527  _InputIterator2 __first2, _InputIterator2 __last2,
5528  _OutputIterator __result)
5529  {
5530  typedef typename iterator_traits<_InputIterator1>::value_type
5531  _ValueType1;
5532  typedef typename iterator_traits<_InputIterator2>::value_type
5533  _ValueType2;
5534 
5535  // concept requirements
5536  __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
5537  __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
5538  __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5539  _ValueType1>)
5540  __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5541  _ValueType2>)
5542  __glibcxx_function_requires(_LessThanOpConcept<_ValueType2, _ValueType1>)
5543  __glibcxx_requires_sorted_set(__first1, __last1, __first2);
5544  __glibcxx_requires_sorted_set(__first2, __last2, __first1);
5545 
5546  while (__first1 != __last1 && __first2 != __last2)
5547  {
5548  if (*__first2 < *__first1)
5549  {
5550  *__result = *__first2;
5551  ++__first2;
5552  }
5553  else
5554  {
5555  *__result = *__first1;
5556  ++__first1;
5557  }
5558  ++__result;
5559  }
5560  return std::copy(__first2, __last2, std::copy(__first1, __last1,
5561  __result));
5562  }
5563 
5587  template<typename _InputIterator1, typename _InputIterator2,
5588  typename _OutputIterator, typename _Compare>
5589  _OutputIterator
5590  merge(_InputIterator1 __first1, _InputIterator1 __last1,
5591  _InputIterator2 __first2, _InputIterator2 __last2,
5592  _OutputIterator __result, _Compare __comp)
5593  {
5594  typedef typename iterator_traits<_InputIterator1>::value_type
5595  _ValueType1;
5596  typedef typename iterator_traits<_InputIterator2>::value_type
5597  _ValueType2;
5598 
5599  // concept requirements
5600  __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
5601  __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
5602  __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5603  _ValueType1>)
5604  __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5605  _ValueType2>)
5606  __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5607  _ValueType2, _ValueType1>)
5608  __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp);
5609  __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp);
5610 
5611  while (__first1 != __last1 && __first2 != __last2)
5612  {
5613  if (__comp(*__first2, *__first1))
5614  {
5615  *__result = *__first2;
5616  ++__first2;
5617  }
5618  else
5619  {
5620  *__result = *__first1;
5621  ++__first1;
5622  }
5623  ++__result;
5624  }
5625  return std::copy(__first2, __last2, std::copy(__first1, __last1,
5626  __result));
5627  }
5628 
5629 
5647  template<typename _RandomAccessIterator>
5648  inline void
5649  stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last)
5650  {
5651  typedef typename iterator_traits<_RandomAccessIterator>::value_type
5652  _ValueType;
5653  typedef typename iterator_traits<_RandomAccessIterator>::difference_type
5654  _DistanceType;
5655 
5656  // concept requirements
5657  __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
5658  _RandomAccessIterator>)
5659  __glibcxx_function_requires(_LessThanComparableConcept<_ValueType>)
5660  __glibcxx_requires_valid_range(__first, __last);
5661 
5662  _Temporary_buffer<_RandomAccessIterator, _ValueType> __buf(__first,
5663  __last);
5664  if (__buf.begin() == 0)
5665  std::__inplace_stable_sort(__first, __last);
5666  else
5667  std::__stable_sort_adaptive(__first, __last, __buf.begin(),
5668  _DistanceType(__buf.size()));
5669  }
5670 
5689  template<typename _RandomAccessIterator, typename _Compare>
5690  inline void
5691  stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last,
5692  _Compare __comp)
5693  {
5694  typedef typename iterator_traits<_RandomAccessIterator>::value_type
5695  _ValueType;
5696  typedef typename iterator_traits<_RandomAccessIterator>::difference_type
5697  _DistanceType;
5698 
5699  // concept requirements
5700  __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
5701  _RandomAccessIterator>)
5702  __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5703  _ValueType,
5704  _ValueType>)
5705  __glibcxx_requires_valid_range(__first, __last);
5706 
5707  _Temporary_buffer<_RandomAccessIterator, _ValueType> __buf(__first,
5708  __last);
5709  if (__buf.begin() == 0)
5710  std::__inplace_stable_sort(__first, __last, __comp);
5711  else
5712  std::__stable_sort_adaptive(__first, __last, __buf.begin(),
5713  _DistanceType(__buf.size()), __comp);
5714  }
5715 
5716 
5735  template<typename _InputIterator1, typename _InputIterator2,
5736  typename _OutputIterator>
5737  _OutputIterator
5738  set_union(_InputIterator1 __first1, _InputIterator1 __last1,
5739  _InputIterator2 __first2, _InputIterator2 __last2,
5740  _OutputIterator __result)
5741  {
5742  typedef typename iterator_traits<_InputIterator1>::value_type
5743  _ValueType1;
5744  typedef typename iterator_traits<_InputIterator2>::value_type
5745  _ValueType2;
5746 
5747  // concept requirements
5748  __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
5749  __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
5750  __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5751  _ValueType1>)
5752  __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5753  _ValueType2>)
5754  __glibcxx_function_requires(_LessThanOpConcept<_ValueType1, _ValueType2>)
5755  __glibcxx_function_requires(_LessThanOpConcept<_ValueType2, _ValueType1>)
5756  __glibcxx_requires_sorted_set(__first1, __last1, __first2);
5757  __glibcxx_requires_sorted_set(__first2, __last2, __first1);
5758 
5759  while (__first1 != __last1 && __first2 != __last2)
5760  {
5761  if (*__first1 < *__first2)
5762  {
5763  *__result = *__first1;
5764  ++__first1;
5765  }
5766  else if (*__first2 < *__first1)
5767  {
5768  *__result = *__first2;
5769  ++__first2;
5770  }
5771  else
5772  {
5773  *__result = *__first1;
5774  ++__first1;
5775  ++__first2;
5776  }
5777  ++__result;
5778  }
5779  return std::copy(__first2, __last2, std::copy(__first1, __last1,
5780  __result));
5781  }
5782 
5802  template<typename _InputIterator1, typename _InputIterator2,
5803  typename _OutputIterator, typename _Compare>
5804  _OutputIterator
5805  set_union(_InputIterator1 __first1, _InputIterator1 __last1,
5806  _InputIterator2 __first2, _InputIterator2 __last2,
5807  _OutputIterator __result, _Compare __comp)
5808  {
5809  typedef typename iterator_traits<_InputIterator1>::value_type
5810  _ValueType1;
5811  typedef typename iterator_traits<_InputIterator2>::value_type
5812  _ValueType2;
5813 
5814  // concept requirements
5815  __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
5816  __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
5817  __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5818  _ValueType1>)
5819  __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5820  _ValueType2>)
5821  __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5822  _ValueType1, _ValueType2>)
5823  __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5824  _ValueType2, _ValueType1>)
5825  __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp);
5826  __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp);
5827 
5828  while (__first1 != __last1 && __first2 != __last2)
5829  {
5830  if (__comp(*__first1, *__first2))
5831  {
5832  *__result = *__first1;
5833  ++__first1;
5834  }
5835  else if (__comp(*__first2, *__first1))
5836  {
5837  *__result = *__first2;
5838  ++__first2;
5839  }
5840  else
5841  {
5842  *__result = *__first1;
5843  ++__first1;
5844  ++__first2;
5845  }
5846  ++__result;
5847  }
5848  return std::copy(__first2, __last2, std::copy(__first1, __last1,
5849  __result));
5850  }
5851 
5869  template<typename _InputIterator1, typename _InputIterator2,
5870  typename _OutputIterator>
5871  _OutputIterator
5872  set_intersection(_InputIterator1 __first1, _InputIterator1 __last1,
5873  _InputIterator2 __first2, _InputIterator2 __last2,
5874  _OutputIterator __result)
5875  {
5876  typedef typename iterator_traits<_InputIterator1>::value_type
5877  _ValueType1;
5878  typedef typename iterator_traits<_InputIterator2>::value_type
5879  _ValueType2;
5880 
5881  // concept requirements
5882  __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
5883  __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
5884  __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5885  _ValueType1>)
5886  __glibcxx_function_requires(_LessThanOpConcept<_ValueType1, _ValueType2>)
5887  __glibcxx_function_requires(_LessThanOpConcept<_ValueType2, _ValueType1>)
5888  __glibcxx_requires_sorted_set(__first1, __last1, __first2);
5889  __glibcxx_requires_sorted_set(__first2, __last2, __first1);
5890 
5891  while (__first1 != __last1 && __first2 != __last2)
5892  if (*__first1 < *__first2)
5893  ++__first1;
5894  else if (*__first2 < *__first1)
5895  ++__first2;
5896  else
5897  {
5898  *__result = *__first1;
5899  ++__first1;
5900  ++__first2;
5901  ++__result;
5902  }
5903  return __result;
5904  }
5905 
5926  template<typename _InputIterator1, typename _InputIterator2,
5927  typename _OutputIterator, typename _Compare>
5928  _OutputIterator
5929  set_intersection(_InputIterator1 __first1, _InputIterator1 __last1,
5930  _InputIterator2 __first2, _InputIterator2 __last2,
5931  _OutputIterator __result, _Compare __comp)
5932  {
5933  typedef typename iterator_traits<_InputIterator1>::value_type
5934  _ValueType1;
5935  typedef typename iterator_traits<_InputIterator2>::value_type
5936  _ValueType2;
5937 
5938  // concept requirements
5939  __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
5940  __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
5941  __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5942  _ValueType1>)
5943  __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5944  _ValueType1, _ValueType2>)
5945  __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5946  _ValueType2, _ValueType1>)
5947  __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp);
5948  __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp);
5949 
5950  while (__first1 != __last1 && __first2 != __last2)
5951  if (__comp(*__first1, *__first2))
5952  ++__first1;
5953  else if (__comp(*__first2, *__first1))
5954  ++__first2;
5955  else
5956  {
5957  *__result = *__first1;
5958  ++__first1;
5959  ++__first2;
5960  ++__result;
5961  }
5962  return __result;
5963  }
5964 
5984  template<typename _InputIterator1, typename _InputIterator2,
5985  typename _OutputIterator>
5986  _OutputIterator
5987  set_difference(_InputIterator1 __first1, _InputIterator1 __last1,
5988  _InputIterator2 __first2, _InputIterator2 __last2,
5989  _OutputIterator __result)
5990  {
5991  typedef typename iterator_traits<_InputIterator1>::value_type
5992  _ValueType1;
5993  typedef typename iterator_traits<_InputIterator2>::value_type
5994  _ValueType2;
5995 
5996  // concept requirements
5997  __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
5998  __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
5999  __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
6000  _ValueType1>)
6001  __glibcxx_function_requires(_LessThanOpConcept<_ValueType1, _ValueType2>)
6002  __glibcxx_function_requires(_LessThanOpConcept<_ValueType2, _ValueType1>)
6003  __glibcxx_requires_sorted_set(__first1, __last1, __first2);
6004  __glibcxx_requires_sorted_set(__first2, __last2, __first1);
6005 
6006  while (__first1 != __last1 && __first2 != __last2)
6007  if (*__first1 < *__first2)
6008  {
6009  *__result = *__first1;
6010  ++__first1;
6011  ++__result;
6012  }
6013  else if (*__first2 < *__first1)
6014  ++__first2;
6015  else
6016  {
6017  ++__first1;
6018  ++__first2;
6019  }
6020  return std::copy(__first1, __last1, __result);
6021  }
6022 
6045  template<typename _InputIterator1, typename _InputIterator2,
6046  typename _OutputIterator, typename _Compare>
6047  _OutputIterator
6048  set_difference(_InputIterator1 __first1, _InputIterator1 __last1,
6049  _InputIterator2 __first2, _InputIterator2 __last2,
6050  _OutputIterator __result, _Compare __comp)
6051  {
6052  typedef typename iterator_traits<_InputIterator1>::value_type
6053  _ValueType1;
6054  typedef typename iterator_traits<_InputIterator2>::value_type
6055  _ValueType2;
6056 
6057  // concept requirements
6058  __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
6059  __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
6060  __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
6061  _ValueType1>)
6062  __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
6063  _ValueType1, _ValueType2>)
6064  __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
6065  _ValueType2, _ValueType1>)
6066  __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp);
6067  __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp);
6068 
6069  while (__first1 != __last1 && __first2 != __last2)
6070  if (__comp(*__first1, *__first2))
6071  {
6072  *__result = *__first1;
6073  ++__first1;
6074  ++__result;
6075  }
6076  else if (__comp(*__first2, *__first1))
6077  ++__first2;
6078  else
6079  {
6080  ++__first1;
6081  ++__first2;
6082  }
6083  return std::copy(__first1, __last1, __result);
6084  }
6085 
6103  template<typename _InputIterator1, typename _InputIterator2,
6104  typename _OutputIterator>
6105  _OutputIterator
6106  set_symmetric_difference(_InputIterator1 __first1, _InputIterator1 __last1,
6107  _InputIterator2 __first2, _InputIterator2 __last2,
6108  _OutputIterator __result)
6109  {
6110  typedef typename iterator_traits<_InputIterator1>::value_type
6111  _ValueType1;
6112  typedef typename iterator_traits<_InputIterator2>::value_type
6113  _ValueType2;
6114 
6115  // concept requirements
6116  __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
6117  __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
6118  __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
6119  _ValueType1>)
6120  __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
6121  _ValueType2>)
6122  __glibcxx_function_requires(_LessThanOpConcept<_ValueType1, _ValueType2>)
6123  __glibcxx_function_requires(_LessThanOpConcept<_ValueType2, _ValueType1>)
6124  __glibcxx_requires_sorted_set(__first1, __last1, __first2);
6125  __glibcxx_requires_sorted_set(__first2, __last2, __first1);
6126 
6127  while (__first1 != __last1 && __first2 != __last2)
6128  if (*__first1 < *__first2)
6129  {
6130  *__result = *__first1;
6131  ++__first1;
6132  ++__result;
6133  }
6134  else if (*__first2 < *__first1)
6135  {
6136  *__result = *__first2;
6137  ++__first2;
6138  ++__result;
6139  }
6140  else
6141  {
6142  ++__first1;
6143  ++__first2;
6144  }
6145  return std::copy(__first2, __last2, std::copy(__first1,
6146  __last1, __result));
6147  }
6148 
6169  template<typename _InputIterator1, typename _InputIterator2,
6170  typename _OutputIterator, typename _Compare>
6171  _OutputIterator
6172  set_symmetric_difference(_InputIterator1 __first1, _InputIterator1 __last1,
6173  _InputIterator2 __first2, _InputIterator2 __last2,
6174  _OutputIterator __result,
6175  _Compare __comp)
6176  {
6177  typedef typename iterator_traits<_InputIterator1>::value_type
6178  _ValueType1;
6179  typedef typename iterator_traits<_InputIterator2>::value_type
6180  _ValueType2;
6181 
6182  // concept requirements
6183  __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
6184  __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
6185  __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
6186  _ValueType1>)
6187  __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
6188  _ValueType2>)
6189  __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
6190  _ValueType1, _ValueType2>)
6191  __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
6192  _ValueType2, _ValueType1>)
6193  __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp);
6194  __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp);
6195 
6196  while (__first1 != __last1 && __first2 != __last2)
6197  if (__comp(*__first1, *__first2))
6198  {
6199  *__result = *__first1;
6200  ++__first1;
6201  ++__result;
6202  }
6203  else if (__comp(*__first2, *__first1))
6204  {
6205  *__result = *__first2;
6206  ++__first2;
6207  ++__result;
6208  }
6209  else
6210  {
6211  ++__first1;
6212  ++__first2;
6213  }
6214  return std::copy(__first2, __last2,
6215  std::copy(__first1, __last1, __result));
6216  }
6217 
6218 
6226  template<typename _ForwardIterator>
6227  _ForwardIterator
6228  min_element(_ForwardIterator __first, _ForwardIterator __last)
6229  {
6230  // concept requirements
6231  __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
6232  __glibcxx_function_requires(_LessThanComparableConcept<
6233  typename iterator_traits<_ForwardIterator>::value_type>)
6234  __glibcxx_requires_valid_range(__first, __last);
6235 
6236  if (__first == __last)
6237  return __first;
6238  _ForwardIterator __result = __first;
6239  while (++__first != __last)
6240  if (*__first < *__result)
6241  __result = __first;
6242  return __result;
6243  }
6244 
6254  template<typename _ForwardIterator, typename _Compare>
6255  _ForwardIterator
6256  min_element(_ForwardIterator __first, _ForwardIterator __last,
6257  _Compare __comp)
6258  {
6259  // concept requirements
6260  __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
6261  __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
6262  typename iterator_traits<_ForwardIterator>::value_type,
6263  typename iterator_traits<_ForwardIterator>::value_type>)
6264  __glibcxx_requires_valid_range(__first, __last);
6265 
6266  if (__first == __last)
6267  return __first;
6268  _ForwardIterator __result = __first;
6269  while (++__first != __last)
6270  if (__comp(*__first, *__result))
6271  __result = __first;
6272  return __result;
6273  }
6274 
6282  template<typename _ForwardIterator>
6283  _ForwardIterator
6284  max_element(_ForwardIterator __first, _ForwardIterator __last)
6285  {
6286  // concept requirements
6287  __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
6288  __glibcxx_function_requires(_LessThanComparableConcept<
6289  typename iterator_traits<_ForwardIterator>::value_type>)
6290  __glibcxx_requires_valid_range(__first, __last);
6291 
6292  if (__first == __last)
6293  return __first;
6294  _ForwardIterator __result = __first;
6295  while (++__first != __last)
6296  if (*__result < *__first)
6297  __result = __first;
6298  return __result;
6299  }
6300 
6310  template<typename _ForwardIterator, typename _Compare>
6311  _ForwardIterator
6312  max_element(_ForwardIterator __first, _ForwardIterator __last,
6313  _Compare __comp)
6314  {
6315  // concept requirements
6316  __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
6317  __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
6318  typename iterator_traits<_ForwardIterator>::value_type,
6319  typename iterator_traits<_ForwardIterator>::value_type>)
6320  __glibcxx_requires_valid_range(__first, __last);
6321 
6322  if (__first == __last) return __first;
6323  _ForwardIterator __result = __first;
6324  while (++__first != __last)
6325  if (__comp(*__result, *__first))
6326  __result = __first;
6327  return __result;
6328  }
6329 
6330 _GLIBCXX_END_NAMESPACE_ALGO
6331 } // namespace std
6332 
6333 #endif /* _STL_ALGO_H */
__glibcxx_requires_partitioned_lower
#define __glibcxx_requires_partitioned_lower(_First, _Last, _Value)
Definition: debug.h:71
__glibcxx_requires_partitioned_upper_pred
#define __glibcxx_requires_partitioned_upper_pred(_First, _Last, _Value, _Pred)
Definition: debug.h:74
__glibcxx_function_requires
#define __glibcxx_function_requires(...)
Definition: concept_check.h:47
_GLIBCXX_VISIBILITY
namespace std _GLIBCXX_VISIBILITY(default)
Definition: stl_algo.h:71
_GLIBCXX_MOVE
#define _GLIBCXX_MOVE(__val)
Definition: move.h:145
stl_heap.h
__glibcxx_requires_partitioned_upper
#define __glibcxx_requires_partitioned_upper(_First, _Last, _Value)
Definition: debug.h:72
__glibcxx_requires_sorted_pred
#define __glibcxx_requires_sorted_pred(_First, _Last, _Pred)
Definition: debug.h:68
bool
#define bool
Definition: stdbool.h:33
__gnu_parallel::min
const _Tp & min(const _Tp &__a, const _Tp &__b)
Equivalent to std::min.
Definition: base.h:144
stl_tempbuf.h
__glibcxx_requires_partitioned_lower_pred
#define __glibcxx_requires_partitioned_lower_pred(_First, _Last, _Value, _Pred)
Definition: debug.h:73
_GLIBCXX_MOVE_BACKWARD3
#define _GLIBCXX_MOVE_BACKWARD3(_Tp, _Up, _Vp)
__glibcxx_requires_sorted_set_pred
#define __glibcxx_requires_sorted_set_pred(_First1, _Last1, _First2, _Pred)
Definition: debug.h:70
__gnu_parallel::max
const _Tp & max(const _Tp &__a, const _Tp &__b)
Equivalent to std::max.
Definition: base.h:150
_GLIBCXX_MOVE3
#define _GLIBCXX_MOVE3(_Tp, _Up, _Vp)
__glibcxx_requires_sorted
#define __glibcxx_requires_sorted(_First, _Last)
Definition: debug.h:67
__glibcxx_requires_valid_range
#define __glibcxx_requires_valid_range(_First, _Last)
Definition: debug.h:65
std::__exception_ptr::swap
void swap(exception_ptr &__lhs, exception_ptr &__rhs)
Definition: exception_ptr.h:160
__glibcxx_requires_sorted_set
#define __glibcxx_requires_sorted_set(_First1, _Last1, _First2)
Definition: debug.h:69
Generated on Sat Jul 22 2017 14:40:05 for STLdoc by   doxygen 1.8.6