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