Merge branch 'vendor/GCC47'
[dragonfly.git] / contrib / gcc-4.7 / libstdc++-v3 / include / bits / stl_algo.h
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 *__result
78   template<typename _Iterator>
79     void
80     __move_median_to_first(_Iterator __result, _Iterator __a,
81                            _Iterator __b, _Iterator __c)
82     {
83       // concept requirements
84       __glibcxx_function_requires(_LessThanComparableConcept<
85             typename iterator_traits<_Iterator>::value_type>)
86
87       if (*__a < *__b)
88         {
89           if (*__b < *__c)
90             std::iter_swap(__result, __b);
91           else if (*__a < *__c)
92             std::iter_swap(__result, __c);
93           else
94             std::iter_swap(__result, __a);
95         }
96       else if (*__a < *__c)
97         std::iter_swap(__result, __a);
98       else if (*__b < *__c)
99         std::iter_swap(__result, __c);
100       else
101         std::iter_swap(__result, __b);
102     }
103
104   /// Swaps the median value of *__a, *__b and *__c under __comp to *__result
105   template<typename _Iterator, typename _Compare>
106     void
107     __move_median_to_first(_Iterator __result, _Iterator __a,
108                            _Iterator __b, _Iterator __c,
109                            _Compare __comp)
110     {
111       // concept requirements
112       __glibcxx_function_requires(_BinaryFunctionConcept<_Compare, bool,
113             typename iterator_traits<_Iterator>::value_type,
114             typename iterator_traits<_Iterator>::value_type>)
115
116       if (__comp(*__a, *__b))
117         {
118           if (__comp(*__b, *__c))
119             std::iter_swap(__result, __b);
120           else if (__comp(*__a, *__c))
121             std::iter_swap(__result, __c);
122           else
123             std::iter_swap(__result, __a);
124         }
125       else if (__comp(*__a, *__c))
126         std::iter_swap(__result, __a);
127       else if (__comp(*__b, *__c))
128         std::iter_swap(__result, __c);
129       else
130         std::iter_swap(__result, __b);
131     }
132
133   // for_each
134
135   /// This is an overload used by find() for the Input Iterator case.
136   template<typename _InputIterator, typename _Tp>
137     inline _InputIterator
138     __find(_InputIterator __first, _InputIterator __last,
139            const _Tp& __val, input_iterator_tag)
140     {
141       while (__first != __last && !(*__first == __val))
142         ++__first;
143       return __first;
144     }
145
146   /// This is an overload used by find_if() for the Input Iterator case.
147   template<typename _InputIterator, typename _Predicate>
148     inline _InputIterator
149     __find_if(_InputIterator __first, _InputIterator __last,
150               _Predicate __pred, input_iterator_tag)
151     {
152       while (__first != __last && !bool(__pred(*__first)))
153         ++__first;
154       return __first;
155     }
156
157   /// This is an overload used by find() for the RAI case.
158   template<typename _RandomAccessIterator, typename _Tp>
159     _RandomAccessIterator
160     __find(_RandomAccessIterator __first, _RandomAccessIterator __last,
161            const _Tp& __val, random_access_iterator_tag)
162     {
163       typename iterator_traits<_RandomAccessIterator>::difference_type
164         __trip_count = (__last - __first) >> 2;
165
166       for (; __trip_count > 0; --__trip_count)
167         {
168           if (*__first == __val)
169             return __first;
170           ++__first;
171
172           if (*__first == __val)
173             return __first;
174           ++__first;
175
176           if (*__first == __val)
177             return __first;
178           ++__first;
179
180           if (*__first == __val)
181             return __first;
182           ++__first;
183         }
184
185       switch (__last - __first)
186         {
187         case 3:
188           if (*__first == __val)
189             return __first;
190           ++__first;
191         case 2:
192           if (*__first == __val)
193             return __first;
194           ++__first;
195         case 1:
196           if (*__first == __val)
197             return __first;
198           ++__first;
199         case 0:
200         default:
201           return __last;
202         }
203     }
204
205   /// This is an overload used by find_if() for the RAI case.
206   template<typename _RandomAccessIterator, typename _Predicate>
207     _RandomAccessIterator
208     __find_if(_RandomAccessIterator __first, _RandomAccessIterator __last,
209               _Predicate __pred, random_access_iterator_tag)
210     {
211       typename iterator_traits<_RandomAccessIterator>::difference_type
212         __trip_count = (__last - __first) >> 2;
213
214       for (; __trip_count > 0; --__trip_count)
215         {
216           if (__pred(*__first))
217             return __first;
218           ++__first;
219
220           if (__pred(*__first))
221             return __first;
222           ++__first;
223
224           if (__pred(*__first))
225             return __first;
226           ++__first;
227
228           if (__pred(*__first))
229             return __first;
230           ++__first;
231         }
232
233       switch (__last - __first)
234         {
235         case 3:
236           if (__pred(*__first))
237             return __first;
238           ++__first;
239         case 2:
240           if (__pred(*__first))
241             return __first;
242           ++__first;
243         case 1:
244           if (__pred(*__first))
245             return __first;
246           ++__first;
247         case 0:
248         default:
249           return __last;
250         }
251     }
252
253   /// This is an overload used by find_if_not() for the Input Iterator case.
254   template<typename _InputIterator, typename _Predicate>
255     inline _InputIterator
256     __find_if_not(_InputIterator __first, _InputIterator __last,
257                   _Predicate __pred, input_iterator_tag)
258     {
259       while (__first != __last && bool(__pred(*__first)))
260         ++__first;
261       return __first;
262     }
263
264   /// This is an overload used by find_if_not() for the RAI case.
265   template<typename _RandomAccessIterator, typename _Predicate>
266     _RandomAccessIterator
267     __find_if_not(_RandomAccessIterator __first, _RandomAccessIterator __last,
268                   _Predicate __pred, random_access_iterator_tag)
269     {
270       typename iterator_traits<_RandomAccessIterator>::difference_type
271         __trip_count = (__last - __first) >> 2;
272
273       for (; __trip_count > 0; --__trip_count)
274         {
275           if (!bool(__pred(*__first)))
276             return __first;
277           ++__first;
278
279           if (!bool(__pred(*__first)))
280             return __first;
281           ++__first;
282
283           if (!bool(__pred(*__first)))
284             return __first;
285           ++__first;
286
287           if (!bool(__pred(*__first)))
288             return __first;
289           ++__first;
290         }
291
292       switch (__last - __first)
293         {
294         case 3:
295           if (!bool(__pred(*__first)))
296             return __first;
297           ++__first;
298         case 2:
299           if (!bool(__pred(*__first)))
300             return __first;
301           ++__first;
302         case 1:
303           if (!bool(__pred(*__first)))
304             return __first;
305           ++__first;
306         case 0:
307         default:
308           return __last;
309         }
310     }
311
312   /// Provided for stable_partition to use.
313   template<typename _InputIterator, typename _Predicate>
314     inline _InputIterator
315     __find_if_not(_InputIterator __first, _InputIterator __last,
316                   _Predicate __pred)
317     {
318       return std::__find_if_not(__first, __last, __pred,
319                                 std::__iterator_category(__first));
320     }
321
322   /// Like find_if_not(), but uses and updates a count of the
323   /// remaining range length instead of comparing against an end
324   /// iterator.
325   template<typename _InputIterator, typename _Predicate, typename _Distance>
326     _InputIterator
327     __find_if_not_n(_InputIterator __first, _Distance& __len, _Predicate __pred)
328     {
329       for (; __len; --__len, ++__first)
330         if (!bool(__pred(*__first)))
331           break;
332       return __first;
333     }
334
335   // set_difference
336   // set_intersection
337   // set_symmetric_difference
338   // set_union
339   // for_each
340   // find
341   // find_if
342   // find_first_of
343   // adjacent_find
344   // count
345   // count_if
346   // search
347
348   /**
349    *  This is an uglified
350    *  search_n(_ForwardIterator, _ForwardIterator, _Integer, const _Tp&)
351    *  overloaded for forward iterators.
352   */
353   template<typename _ForwardIterator, typename _Integer, typename _Tp>
354     _ForwardIterator
355     __search_n(_ForwardIterator __first, _ForwardIterator __last,
356                _Integer __count, const _Tp& __val,
357                std::forward_iterator_tag)
358     {
359       __first = _GLIBCXX_STD_A::find(__first, __last, __val);
360       while (__first != __last)
361         {
362           typename iterator_traits<_ForwardIterator>::difference_type
363             __n = __count;
364           _ForwardIterator __i = __first;
365           ++__i;
366           while (__i != __last && __n != 1 && *__i == __val)
367             {
368               ++__i;
369               --__n;
370             }
371           if (__n == 1)
372             return __first;
373           if (__i == __last)
374             return __last;
375           __first = _GLIBCXX_STD_A::find(++__i, __last, __val);
376         }
377       return __last;
378     }
379
380   /**
381    *  This is an uglified
382    *  search_n(_ForwardIterator, _ForwardIterator, _Integer, const _Tp&)
383    *  overloaded for random access iterators.
384   */
385   template<typename _RandomAccessIter, typename _Integer, typename _Tp>
386     _RandomAccessIter
387     __search_n(_RandomAccessIter __first, _RandomAccessIter __last,
388                _Integer __count, const _Tp& __val, 
389                std::random_access_iterator_tag)
390     {
391       
392       typedef typename std::iterator_traits<_RandomAccessIter>::difference_type
393         _DistanceType;
394
395       _DistanceType __tailSize = __last - __first;
396       const _DistanceType __pattSize = __count;
397
398       if (__tailSize < __pattSize)
399         return __last;
400
401       const _DistanceType __skipOffset = __pattSize - 1;
402       _RandomAccessIter __lookAhead = __first + __skipOffset;
403       __tailSize -= __pattSize;
404
405       while (1) // the main loop...
406         {
407           // __lookAhead here is always pointing to the last element of next 
408           // possible match.
409           while (!(*__lookAhead == __val)) // the skip loop...
410             {
411               if (__tailSize < __pattSize)
412                 return __last;  // Failure
413               __lookAhead += __pattSize;
414               __tailSize -= __pattSize;
415             }
416           _DistanceType __remainder = __skipOffset;
417           for (_RandomAccessIter __backTrack = __lookAhead - 1; 
418                *__backTrack == __val; --__backTrack)
419             {
420               if (--__remainder == 0)
421                 return (__lookAhead - __skipOffset); // Success
422             }
423           if (__remainder > __tailSize)
424             return __last; // Failure
425           __lookAhead += __remainder;
426           __tailSize -= __remainder;
427         }
428     }
429
430   // search_n
431
432   /**
433    *  This is an uglified
434    *  search_n(_ForwardIterator, _ForwardIterator, _Integer, const _Tp&,
435    *           _BinaryPredicate)
436    *  overloaded for forward iterators.
437   */
438   template<typename _ForwardIterator, typename _Integer, typename _Tp,
439            typename _BinaryPredicate>
440     _ForwardIterator
441     __search_n(_ForwardIterator __first, _ForwardIterator __last,
442                _Integer __count, const _Tp& __val,
443                _BinaryPredicate __binary_pred, std::forward_iterator_tag)
444     {
445       while (__first != __last && !bool(__binary_pred(*__first, __val)))
446         ++__first;
447
448       while (__first != __last)
449         {
450           typename iterator_traits<_ForwardIterator>::difference_type
451             __n = __count;
452           _ForwardIterator __i = __first;
453           ++__i;
454           while (__i != __last && __n != 1 && bool(__binary_pred(*__i, __val)))
455             {
456               ++__i;
457               --__n;
458             }
459           if (__n == 1)
460             return __first;
461           if (__i == __last)
462             return __last;
463           __first = ++__i;
464           while (__first != __last
465                  && !bool(__binary_pred(*__first, __val)))
466             ++__first;
467         }
468       return __last;
469     }
470
471   /**
472    *  This is an uglified
473    *  search_n(_ForwardIterator, _ForwardIterator, _Integer, const _Tp&,
474    *           _BinaryPredicate)
475    *  overloaded for random access iterators.
476   */
477   template<typename _RandomAccessIter, typename _Integer, typename _Tp,
478            typename _BinaryPredicate>
479     _RandomAccessIter
480     __search_n(_RandomAccessIter __first, _RandomAccessIter __last,
481                _Integer __count, const _Tp& __val,
482                _BinaryPredicate __binary_pred, std::random_access_iterator_tag)
483     {
484       
485       typedef typename std::iterator_traits<_RandomAccessIter>::difference_type
486         _DistanceType;
487
488       _DistanceType __tailSize = __last - __first;
489       const _DistanceType __pattSize = __count;
490
491       if (__tailSize < __pattSize)
492         return __last;
493
494       const _DistanceType __skipOffset = __pattSize - 1;
495       _RandomAccessIter __lookAhead = __first + __skipOffset;
496       __tailSize -= __pattSize;
497
498       while (1) // the main loop...
499         {
500           // __lookAhead here is always pointing to the last element of next 
501           // possible match.
502           while (!bool(__binary_pred(*__lookAhead, __val))) // the skip loop...
503             {
504               if (__tailSize < __pattSize)
505                 return __last;  // Failure
506               __lookAhead += __pattSize;
507               __tailSize -= __pattSize;
508             }
509           _DistanceType __remainder = __skipOffset;
510           for (_RandomAccessIter __backTrack = __lookAhead - 1; 
511                __binary_pred(*__backTrack, __val); --__backTrack)
512             {
513               if (--__remainder == 0)
514                 return (__lookAhead - __skipOffset); // Success
515             }
516           if (__remainder > __tailSize)
517             return __last; // Failure
518           __lookAhead += __remainder;
519           __tailSize -= __remainder;
520         }
521     }
522
523   // find_end for forward iterators.
524   template<typename _ForwardIterator1, typename _ForwardIterator2>
525     _ForwardIterator1
526     __find_end(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
527                _ForwardIterator2 __first2, _ForwardIterator2 __last2,
528                forward_iterator_tag, forward_iterator_tag)
529     {
530       if (__first2 == __last2)
531         return __last1;
532       else
533         {
534           _ForwardIterator1 __result = __last1;
535           while (1)
536             {
537               _ForwardIterator1 __new_result
538                 = _GLIBCXX_STD_A::search(__first1, __last1, __first2, __last2);
539               if (__new_result == __last1)
540                 return __result;
541               else
542                 {
543                   __result = __new_result;
544                   __first1 = __new_result;
545                   ++__first1;
546                 }
547             }
548         }
549     }
550
551   template<typename _ForwardIterator1, typename _ForwardIterator2,
552            typename _BinaryPredicate>
553     _ForwardIterator1
554     __find_end(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
555                _ForwardIterator2 __first2, _ForwardIterator2 __last2,
556                forward_iterator_tag, forward_iterator_tag,
557                _BinaryPredicate __comp)
558     {
559       if (__first2 == __last2)
560         return __last1;
561       else
562         {
563           _ForwardIterator1 __result = __last1;
564           while (1)
565             {
566               _ForwardIterator1 __new_result
567                 = _GLIBCXX_STD_A::search(__first1, __last1, __first2,
568                                          __last2, __comp);
569               if (__new_result == __last1)
570                 return __result;
571               else
572                 {
573                   __result = __new_result;
574                   __first1 = __new_result;
575                   ++__first1;
576                 }
577             }
578         }
579     }
580
581   // find_end for bidirectional iterators (much faster).
582   template<typename _BidirectionalIterator1, typename _BidirectionalIterator2>
583     _BidirectionalIterator1
584     __find_end(_BidirectionalIterator1 __first1,
585                _BidirectionalIterator1 __last1,
586                _BidirectionalIterator2 __first2,
587                _BidirectionalIterator2 __last2,
588                bidirectional_iterator_tag, bidirectional_iterator_tag)
589     {
590       // concept requirements
591       __glibcxx_function_requires(_BidirectionalIteratorConcept<
592                                   _BidirectionalIterator1>)
593       __glibcxx_function_requires(_BidirectionalIteratorConcept<
594                                   _BidirectionalIterator2>)
595
596       typedef reverse_iterator<_BidirectionalIterator1> _RevIterator1;
597       typedef reverse_iterator<_BidirectionalIterator2> _RevIterator2;
598
599       _RevIterator1 __rlast1(__first1);
600       _RevIterator2 __rlast2(__first2);
601       _RevIterator1 __rresult = _GLIBCXX_STD_A::search(_RevIterator1(__last1),
602                                                        __rlast1,
603                                                        _RevIterator2(__last2),
604                                                        __rlast2);
605
606       if (__rresult == __rlast1)
607         return __last1;
608       else
609         {
610           _BidirectionalIterator1 __result = __rresult.base();
611           std::advance(__result, -std::distance(__first2, __last2));
612           return __result;
613         }
614     }
615
616   template<typename _BidirectionalIterator1, typename _BidirectionalIterator2,
617            typename _BinaryPredicate>
618     _BidirectionalIterator1
619     __find_end(_BidirectionalIterator1 __first1,
620                _BidirectionalIterator1 __last1,
621                _BidirectionalIterator2 __first2,
622                _BidirectionalIterator2 __last2,
623                bidirectional_iterator_tag, bidirectional_iterator_tag,
624                _BinaryPredicate __comp)
625     {
626       // concept requirements
627       __glibcxx_function_requires(_BidirectionalIteratorConcept<
628                                   _BidirectionalIterator1>)
629       __glibcxx_function_requires(_BidirectionalIteratorConcept<
630                                   _BidirectionalIterator2>)
631
632       typedef reverse_iterator<_BidirectionalIterator1> _RevIterator1;
633       typedef reverse_iterator<_BidirectionalIterator2> _RevIterator2;
634
635       _RevIterator1 __rlast1(__first1);
636       _RevIterator2 __rlast2(__first2);
637       _RevIterator1 __rresult = std::search(_RevIterator1(__last1), __rlast1,
638                                             _RevIterator2(__last2), __rlast2,
639                                             __comp);
640
641       if (__rresult == __rlast1)
642         return __last1;
643       else
644         {
645           _BidirectionalIterator1 __result = __rresult.base();
646           std::advance(__result, -std::distance(__first2, __last2));
647           return __result;
648         }
649     }
650
651   /**
652    *  @brief  Find last matching subsequence in a sequence.
653    *  @ingroup non_mutating_algorithms
654    *  @param  __first1  Start of range to search.
655    *  @param  __last1   End of range to search.
656    *  @param  __first2  Start of sequence to match.
657    *  @param  __last2   End of sequence to match.
658    *  @return   The last iterator @c i in the range
659    *  @p [__first1,__last1-(__last2-__first2)) such that @c *(i+N) ==
660    *  @p *(__first2+N) for each @c N in the range @p
661    *  [0,__last2-__first2), or @p __last1 if no such iterator exists.
662    *
663    *  Searches the range @p [__first1,__last1) for a sub-sequence that
664    *  compares equal value-by-value with the sequence given by @p
665    *  [__first2,__last2) and returns an iterator to the __first
666    *  element of the sub-sequence, or @p __last1 if the sub-sequence
667    *  is not found.  The sub-sequence will be the last such
668    *  subsequence contained in [__first,__last1).
669    *
670    *  Because the sub-sequence must lie completely within the range @p
671    *  [__first1,__last1) it must start at a position less than @p
672    *  __last1-(__last2-__first2) where @p __last2-__first2 is the
673    *  length of the sub-sequence.  This means that the returned
674    *  iterator @c i will be in the range @p
675    *  [__first1,__last1-(__last2-__first2))
676   */
677   template<typename _ForwardIterator1, typename _ForwardIterator2>
678     inline _ForwardIterator1
679     find_end(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
680              _ForwardIterator2 __first2, _ForwardIterator2 __last2)
681     {
682       // concept requirements
683       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator1>)
684       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator2>)
685       __glibcxx_function_requires(_EqualOpConcept<
686             typename iterator_traits<_ForwardIterator1>::value_type,
687             typename iterator_traits<_ForwardIterator2>::value_type>)
688       __glibcxx_requires_valid_range(__first1, __last1);
689       __glibcxx_requires_valid_range(__first2, __last2);
690
691       return std::__find_end(__first1, __last1, __first2, __last2,
692                              std::__iterator_category(__first1),
693                              std::__iterator_category(__first2));
694     }
695
696   /**
697    *  @brief  Find last matching subsequence in a sequence using a predicate.
698    *  @ingroup non_mutating_algorithms
699    *  @param  __first1  Start of range to search.
700    *  @param  __last1   End of range to search.
701    *  @param  __first2  Start of sequence to match.
702    *  @param  __last2   End of sequence to match.
703    *  @param  __comp    The predicate to use.
704    *  @return The last iterator @c i in the range @p
705    *  [__first1,__last1-(__last2-__first2)) such that @c
706    *  predicate(*(i+N), @p (__first2+N)) is true for each @c N in the
707    *  range @p [0,__last2-__first2), or @p __last1 if no such iterator
708    *  exists.
709    *
710    *  Searches the range @p [__first1,__last1) for a sub-sequence that
711    *  compares equal value-by-value with the sequence given by @p
712    *  [__first2,__last2) using comp as a predicate and returns an
713    *  iterator to the first element of the sub-sequence, or @p __last1
714    *  if the sub-sequence is not found.  The sub-sequence will be the
715    *  last such subsequence contained in [__first,__last1).
716    *
717    *  Because the sub-sequence must lie completely within the range @p
718    *  [__first1,__last1) it must start at a position less than @p
719    *  __last1-(__last2-__first2) where @p __last2-__first2 is the
720    *  length of the sub-sequence.  This means that the returned
721    *  iterator @c i will be in the range @p
722    *  [__first1,__last1-(__last2-__first2))
723   */
724   template<typename _ForwardIterator1, typename _ForwardIterator2,
725            typename _BinaryPredicate>
726     inline _ForwardIterator1
727     find_end(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
728              _ForwardIterator2 __first2, _ForwardIterator2 __last2,
729              _BinaryPredicate __comp)
730     {
731       // concept requirements
732       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator1>)
733       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator2>)
734       __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
735             typename iterator_traits<_ForwardIterator1>::value_type,
736             typename iterator_traits<_ForwardIterator2>::value_type>)
737       __glibcxx_requires_valid_range(__first1, __last1);
738       __glibcxx_requires_valid_range(__first2, __last2);
739
740       return std::__find_end(__first1, __last1, __first2, __last2,
741                              std::__iterator_category(__first1),
742                              std::__iterator_category(__first2),
743                              __comp);
744     }
745
746 #ifdef __GXX_EXPERIMENTAL_CXX0X__
747   /**
748    *  @brief  Checks that a predicate is true for all the elements
749    *          of a sequence.
750    *  @ingroup non_mutating_algorithms
751    *  @param  __first   An input iterator.
752    *  @param  __last    An input iterator.
753    *  @param  __pred    A predicate.
754    *  @return  True if the check is true, false otherwise.
755    *
756    *  Returns true if @p __pred is true for each element in the range
757    *  @p [__first,__last), and false otherwise.
758   */
759   template<typename _InputIterator, typename _Predicate>
760     inline bool
761     all_of(_InputIterator __first, _InputIterator __last, _Predicate __pred)
762     { return __last == std::find_if_not(__first, __last, __pred); }
763
764   /**
765    *  @brief  Checks that a predicate is false for all the elements
766    *          of a sequence.
767    *  @ingroup non_mutating_algorithms
768    *  @param  __first   An input iterator.
769    *  @param  __last    An input iterator.
770    *  @param  __pred    A predicate.
771    *  @return  True if the check is true, false otherwise.
772    *
773    *  Returns true if @p __pred is false for each element in the range
774    *  @p [__first,__last), and false otherwise.
775   */
776   template<typename _InputIterator, typename _Predicate>
777     inline bool
778     none_of(_InputIterator __first, _InputIterator __last, _Predicate __pred)
779     { return __last == _GLIBCXX_STD_A::find_if(__first, __last, __pred); }
780
781   /**
782    *  @brief  Checks that a predicate is false for at least an element
783    *          of a sequence.
784    *  @ingroup non_mutating_algorithms
785    *  @param  __first   An input iterator.
786    *  @param  __last    An input iterator.
787    *  @param  __pred    A predicate.
788    *  @return  True if the check is true, false otherwise.
789    *
790    *  Returns true if an element exists in the range @p
791    *  [__first,__last) such that @p __pred is true, and false
792    *  otherwise.
793   */
794   template<typename _InputIterator, typename _Predicate>
795     inline bool
796     any_of(_InputIterator __first, _InputIterator __last, _Predicate __pred)
797     { return !std::none_of(__first, __last, __pred); }
798
799   /**
800    *  @brief  Find the first element in a sequence for which a
801    *          predicate is false.
802    *  @ingroup non_mutating_algorithms
803    *  @param  __first  An input iterator.
804    *  @param  __last   An input iterator.
805    *  @param  __pred   A predicate.
806    *  @return   The first iterator @c i in the range @p [__first,__last)
807    *  such that @p __pred(*i) is false, or @p __last if no such iterator exists.
808   */
809   template<typename _InputIterator, typename _Predicate>
810     inline _InputIterator
811     find_if_not(_InputIterator __first, _InputIterator __last,
812                 _Predicate __pred)
813     {
814       // concept requirements
815       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
816       __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
817               typename iterator_traits<_InputIterator>::value_type>)
818       __glibcxx_requires_valid_range(__first, __last);
819       return std::__find_if_not(__first, __last, __pred);
820     }
821
822   /**
823    *  @brief  Checks whether the sequence is partitioned.
824    *  @ingroup mutating_algorithms
825    *  @param  __first  An input iterator.
826    *  @param  __last   An input iterator.
827    *  @param  __pred   A predicate.
828    *  @return  True if the range @p [__first,__last) is partioned by @p __pred,
829    *  i.e. if all elements that satisfy @p __pred appear before those that
830    *  do not.
831   */
832   template<typename _InputIterator, typename _Predicate>
833     inline bool
834     is_partitioned(_InputIterator __first, _InputIterator __last,
835                    _Predicate __pred)
836     {
837       __first = std::find_if_not(__first, __last, __pred);
838       return std::none_of(__first, __last, __pred);
839     }
840
841   /**
842    *  @brief  Find the partition point of a partitioned range.
843    *  @ingroup mutating_algorithms
844    *  @param  __first   An iterator.
845    *  @param  __last    Another iterator.
846    *  @param  __pred    A predicate.
847    *  @return  An iterator @p mid such that @p all_of(__first, mid, __pred)
848    *           and @p none_of(mid, __last, __pred) are both true.
849   */
850   template<typename _ForwardIterator, typename _Predicate>
851     _ForwardIterator
852     partition_point(_ForwardIterator __first, _ForwardIterator __last,
853                     _Predicate __pred)
854     {
855       // concept requirements
856       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
857       __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
858               typename iterator_traits<_ForwardIterator>::value_type>)
859
860       // A specific debug-mode test will be necessary...
861       __glibcxx_requires_valid_range(__first, __last);
862
863       typedef typename iterator_traits<_ForwardIterator>::difference_type
864         _DistanceType;
865
866       _DistanceType __len = std::distance(__first, __last);
867       _DistanceType __half;
868       _ForwardIterator __middle;
869
870       while (__len > 0)
871         {
872           __half = __len >> 1;
873           __middle = __first;
874           std::advance(__middle, __half);
875           if (__pred(*__middle))
876             {
877               __first = __middle;
878               ++__first;
879               __len = __len - __half - 1;
880             }
881           else
882             __len = __half;
883         }
884       return __first;
885     }
886 #endif
887
888
889   /**
890    *  @brief Copy a sequence, removing elements of a given value.
891    *  @ingroup mutating_algorithms
892    *  @param  __first   An input iterator.
893    *  @param  __last    An input iterator.
894    *  @param  __result  An output iterator.
895    *  @param  __value   The value to be removed.
896    *  @return   An iterator designating the end of the resulting sequence.
897    *
898    *  Copies each element in the range @p [__first,__last) not equal
899    *  to @p __value to the range beginning at @p __result.
900    *  remove_copy() is stable, so the relative order of elements that
901    *  are copied is unchanged.
902   */
903   template<typename _InputIterator, typename _OutputIterator, typename _Tp>
904     _OutputIterator
905     remove_copy(_InputIterator __first, _InputIterator __last,
906                 _OutputIterator __result, const _Tp& __value)
907     {
908       // concept requirements
909       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
910       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
911             typename iterator_traits<_InputIterator>::value_type>)
912       __glibcxx_function_requires(_EqualOpConcept<
913             typename iterator_traits<_InputIterator>::value_type, _Tp>)
914       __glibcxx_requires_valid_range(__first, __last);
915
916       for (; __first != __last; ++__first)
917         if (!(*__first == __value))
918           {
919             *__result = *__first;
920             ++__result;
921           }
922       return __result;
923     }
924
925   /**
926    *  @brief Copy a sequence, removing elements for which a predicate is true.
927    *  @ingroup mutating_algorithms
928    *  @param  __first   An input iterator.
929    *  @param  __last    An input iterator.
930    *  @param  __result  An output iterator.
931    *  @param  __pred    A predicate.
932    *  @return   An iterator designating the end of the resulting sequence.
933    *
934    *  Copies each element in the range @p [__first,__last) for which
935    *  @p __pred returns false to the range beginning at @p __result.
936    *
937    *  remove_copy_if() is stable, so the relative order of elements that are
938    *  copied is unchanged.
939   */
940   template<typename _InputIterator, typename _OutputIterator,
941            typename _Predicate>
942     _OutputIterator
943     remove_copy_if(_InputIterator __first, _InputIterator __last,
944                    _OutputIterator __result, _Predicate __pred)
945     {
946       // concept requirements
947       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
948       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
949             typename iterator_traits<_InputIterator>::value_type>)
950       __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
951             typename iterator_traits<_InputIterator>::value_type>)
952       __glibcxx_requires_valid_range(__first, __last);
953
954       for (; __first != __last; ++__first)
955         if (!bool(__pred(*__first)))
956           {
957             *__result = *__first;
958             ++__result;
959           }
960       return __result;
961     }
962
963 #ifdef __GXX_EXPERIMENTAL_CXX0X__
964   /**
965    *  @brief Copy the elements of a sequence for which a predicate is true.
966    *  @ingroup mutating_algorithms
967    *  @param  __first   An input iterator.
968    *  @param  __last    An input iterator.
969    *  @param  __result  An output iterator.
970    *  @param  __pred    A predicate.
971    *  @return   An iterator designating the end of the resulting sequence.
972    *
973    *  Copies each element in the range @p [__first,__last) for which
974    *  @p __pred returns true to the range beginning at @p __result.
975    *
976    *  copy_if() is stable, so the relative order of elements that are
977    *  copied is unchanged.
978   */
979   template<typename _InputIterator, typename _OutputIterator,
980            typename _Predicate>
981     _OutputIterator
982     copy_if(_InputIterator __first, _InputIterator __last,
983             _OutputIterator __result, _Predicate __pred)
984     {
985       // concept requirements
986       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
987       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
988             typename iterator_traits<_InputIterator>::value_type>)
989       __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
990             typename iterator_traits<_InputIterator>::value_type>)
991       __glibcxx_requires_valid_range(__first, __last);
992
993       for (; __first != __last; ++__first)
994         if (__pred(*__first))
995           {
996             *__result = *__first;
997             ++__result;
998           }
999       return __result;
1000     }
1001
1002
1003   template<typename _InputIterator, typename _Size, typename _OutputIterator>
1004     _OutputIterator
1005     __copy_n(_InputIterator __first, _Size __n,
1006              _OutputIterator __result, input_iterator_tag)
1007     {
1008       if (__n > 0)
1009         {
1010           while (true)
1011             {
1012               *__result = *__first;
1013               ++__result;
1014               if (--__n > 0)
1015                 ++__first;
1016               else
1017                 break;
1018             }
1019         }
1020       return __result;
1021     }
1022
1023   template<typename _RandomAccessIterator, typename _Size,
1024            typename _OutputIterator>
1025     inline _OutputIterator
1026     __copy_n(_RandomAccessIterator __first, _Size __n,
1027              _OutputIterator __result, random_access_iterator_tag)
1028     { return std::copy(__first, __first + __n, __result); }
1029
1030   /**
1031    *  @brief Copies the range [first,first+n) into [result,result+n).
1032    *  @ingroup mutating_algorithms
1033    *  @param  __first  An input iterator.
1034    *  @param  __n      The number of elements to copy.
1035    *  @param  __result An output iterator.
1036    *  @return  result+n.
1037    *
1038    *  This inline function will boil down to a call to @c memmove whenever
1039    *  possible.  Failing that, if random access iterators are passed, then the
1040    *  loop count will be known (and therefore a candidate for compiler
1041    *  optimizations such as unrolling).
1042   */
1043   template<typename _InputIterator, typename _Size, typename _OutputIterator>
1044     inline _OutputIterator
1045     copy_n(_InputIterator __first, _Size __n, _OutputIterator __result)
1046     {
1047       // concept requirements
1048       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
1049       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
1050             typename iterator_traits<_InputIterator>::value_type>)
1051
1052       return std::__copy_n(__first, __n, __result,
1053                            std::__iterator_category(__first));
1054     }
1055
1056   /**
1057    *  @brief Copy the elements of a sequence to separate output sequences
1058    *         depending on the truth value of a predicate.
1059    *  @ingroup mutating_algorithms
1060    *  @param  __first   An input iterator.
1061    *  @param  __last    An input iterator.
1062    *  @param  __out_true   An output iterator.
1063    *  @param  __out_false  An output iterator.
1064    *  @param  __pred    A predicate.
1065    *  @return   A pair designating the ends of the resulting sequences.
1066    *
1067    *  Copies each element in the range @p [__first,__last) for which
1068    *  @p __pred returns true to the range beginning at @p out_true
1069    *  and each element for which @p __pred returns false to @p __out_false.
1070   */
1071   template<typename _InputIterator, typename _OutputIterator1,
1072            typename _OutputIterator2, typename _Predicate>
1073     pair<_OutputIterator1, _OutputIterator2>
1074     partition_copy(_InputIterator __first, _InputIterator __last,
1075                    _OutputIterator1 __out_true, _OutputIterator2 __out_false,
1076                    _Predicate __pred)
1077     {
1078       // concept requirements
1079       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
1080       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator1,
1081             typename iterator_traits<_InputIterator>::value_type>)
1082       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator2,
1083             typename iterator_traits<_InputIterator>::value_type>)
1084       __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
1085             typename iterator_traits<_InputIterator>::value_type>)
1086       __glibcxx_requires_valid_range(__first, __last);
1087       
1088       for (; __first != __last; ++__first)
1089         if (__pred(*__first))
1090           {
1091             *__out_true = *__first;
1092             ++__out_true;
1093           }
1094         else
1095           {
1096             *__out_false = *__first;
1097             ++__out_false;
1098           }
1099
1100       return pair<_OutputIterator1, _OutputIterator2>(__out_true, __out_false);
1101     }
1102 #endif
1103
1104   /**
1105    *  @brief Remove elements from a sequence.
1106    *  @ingroup mutating_algorithms
1107    *  @param  __first  An input iterator.
1108    *  @param  __last   An input iterator.
1109    *  @param  __value  The value to be removed.
1110    *  @return   An iterator designating the end of the resulting sequence.
1111    *
1112    *  All elements equal to @p __value are removed from the range
1113    *  @p [__first,__last).
1114    *
1115    *  remove() is stable, so the relative order of elements that are
1116    *  not removed is unchanged.
1117    *
1118    *  Elements between the end of the resulting sequence and @p __last
1119    *  are still present, but their value is unspecified.
1120   */
1121   template<typename _ForwardIterator, typename _Tp>
1122     _ForwardIterator
1123     remove(_ForwardIterator __first, _ForwardIterator __last,
1124            const _Tp& __value)
1125     {
1126       // concept requirements
1127       __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
1128                                   _ForwardIterator>)
1129       __glibcxx_function_requires(_EqualOpConcept<
1130             typename iterator_traits<_ForwardIterator>::value_type, _Tp>)
1131       __glibcxx_requires_valid_range(__first, __last);
1132
1133       __first = _GLIBCXX_STD_A::find(__first, __last, __value);
1134       if(__first == __last)
1135         return __first;
1136       _ForwardIterator __result = __first;
1137       ++__first;
1138       for(; __first != __last; ++__first)
1139         if(!(*__first == __value))
1140           {
1141             *__result = _GLIBCXX_MOVE(*__first);
1142             ++__result;
1143           }
1144       return __result;
1145     }
1146
1147   /**
1148    *  @brief Remove elements from a sequence using a predicate.
1149    *  @ingroup mutating_algorithms
1150    *  @param  __first  A forward iterator.
1151    *  @param  __last   A forward iterator.
1152    *  @param  __pred   A predicate.
1153    *  @return   An iterator designating the end of the resulting sequence.
1154    *
1155    *  All elements for which @p __pred returns true are removed from the range
1156    *  @p [__first,__last).
1157    *
1158    *  remove_if() is stable, so the relative order of elements that are
1159    *  not removed is unchanged.
1160    *
1161    *  Elements between the end of the resulting sequence and @p __last
1162    *  are still present, but their value is unspecified.
1163   */
1164   template<typename _ForwardIterator, typename _Predicate>
1165     _ForwardIterator
1166     remove_if(_ForwardIterator __first, _ForwardIterator __last,
1167               _Predicate __pred)
1168     {
1169       // concept requirements
1170       __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
1171                                   _ForwardIterator>)
1172       __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
1173             typename iterator_traits<_ForwardIterator>::value_type>)
1174       __glibcxx_requires_valid_range(__first, __last);
1175
1176       __first = _GLIBCXX_STD_A::find_if(__first, __last, __pred);
1177       if(__first == __last)
1178         return __first;
1179       _ForwardIterator __result = __first;
1180       ++__first;
1181       for(; __first != __last; ++__first)
1182         if(!bool(__pred(*__first)))
1183           {
1184             *__result = _GLIBCXX_MOVE(*__first);
1185             ++__result;
1186           }
1187       return __result;
1188     }
1189
1190   /**
1191    *  @brief Remove consecutive duplicate values from a sequence.
1192    *  @ingroup mutating_algorithms
1193    *  @param  __first  A forward iterator.
1194    *  @param  __last   A forward iterator.
1195    *  @return  An iterator designating the end of the resulting sequence.
1196    *
1197    *  Removes all but the first element from each group of consecutive
1198    *  values that compare equal.
1199    *  unique() is stable, so the relative order of elements that are
1200    *  not removed is unchanged.
1201    *  Elements between the end of the resulting sequence and @p __last
1202    *  are still present, but their value is unspecified.
1203   */
1204   template<typename _ForwardIterator>
1205     _ForwardIterator
1206     unique(_ForwardIterator __first, _ForwardIterator __last)
1207     {
1208       // concept requirements
1209       __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
1210                                   _ForwardIterator>)
1211       __glibcxx_function_requires(_EqualityComparableConcept<
1212                      typename iterator_traits<_ForwardIterator>::value_type>)
1213       __glibcxx_requires_valid_range(__first, __last);
1214
1215       // Skip the beginning, if already unique.
1216       __first = _GLIBCXX_STD_A::adjacent_find(__first, __last);
1217       if (__first == __last)
1218         return __last;
1219
1220       // Do the real copy work.
1221       _ForwardIterator __dest = __first;
1222       ++__first;
1223       while (++__first != __last)
1224         if (!(*__dest == *__first))
1225           *++__dest = _GLIBCXX_MOVE(*__first);
1226       return ++__dest;
1227     }
1228
1229   /**
1230    *  @brief Remove consecutive values from a sequence using a predicate.
1231    *  @ingroup mutating_algorithms
1232    *  @param  __first        A forward iterator.
1233    *  @param  __last         A forward iterator.
1234    *  @param  __binary_pred  A binary predicate.
1235    *  @return  An iterator designating the end of the resulting sequence.
1236    *
1237    *  Removes all but the first element from each group of consecutive
1238    *  values for which @p __binary_pred returns true.
1239    *  unique() is stable, so the relative order of elements that are
1240    *  not removed is unchanged.
1241    *  Elements between the end of the resulting sequence and @p __last
1242    *  are still present, but their value is unspecified.
1243   */
1244   template<typename _ForwardIterator, typename _BinaryPredicate>
1245     _ForwardIterator
1246     unique(_ForwardIterator __first, _ForwardIterator __last,
1247            _BinaryPredicate __binary_pred)
1248     {
1249       // concept requirements
1250       __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
1251                                   _ForwardIterator>)
1252       __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
1253                 typename iterator_traits<_ForwardIterator>::value_type,
1254                 typename iterator_traits<_ForwardIterator>::value_type>)
1255       __glibcxx_requires_valid_range(__first, __last);
1256
1257       // Skip the beginning, if already unique.
1258       __first = _GLIBCXX_STD_A::adjacent_find(__first, __last, __binary_pred);
1259       if (__first == __last)
1260         return __last;
1261
1262       // Do the real copy work.
1263       _ForwardIterator __dest = __first;
1264       ++__first;
1265       while (++__first != __last)
1266         if (!bool(__binary_pred(*__dest, *__first)))
1267           *++__dest = _GLIBCXX_MOVE(*__first);
1268       return ++__dest;
1269     }
1270
1271   /**
1272    *  This is an uglified unique_copy(_InputIterator, _InputIterator,
1273    *                                  _OutputIterator)
1274    *  overloaded for forward iterators and output iterator as result.
1275   */
1276   template<typename _ForwardIterator, typename _OutputIterator>
1277     _OutputIterator
1278     __unique_copy(_ForwardIterator __first, _ForwardIterator __last,
1279                   _OutputIterator __result,
1280                   forward_iterator_tag, output_iterator_tag)
1281     {
1282       // concept requirements -- taken care of in dispatching function
1283       _ForwardIterator __next = __first;
1284       *__result = *__first;
1285       while (++__next != __last)
1286         if (!(*__first == *__next))
1287           {
1288             __first = __next;
1289             *++__result = *__first;
1290           }
1291       return ++__result;
1292     }
1293
1294   /**
1295    *  This is an uglified unique_copy(_InputIterator, _InputIterator,
1296    *                                  _OutputIterator)
1297    *  overloaded for input iterators and output iterator as result.
1298   */
1299   template<typename _InputIterator, typename _OutputIterator>
1300     _OutputIterator
1301     __unique_copy(_InputIterator __first, _InputIterator __last,
1302                   _OutputIterator __result,
1303                   input_iterator_tag, output_iterator_tag)
1304     {
1305       // concept requirements -- taken care of in dispatching function
1306       typename iterator_traits<_InputIterator>::value_type __value = *__first;
1307       *__result = __value;
1308       while (++__first != __last)
1309         if (!(__value == *__first))
1310           {
1311             __value = *__first;
1312             *++__result = __value;
1313           }
1314       return ++__result;
1315     }
1316
1317   /**
1318    *  This is an uglified unique_copy(_InputIterator, _InputIterator,
1319    *                                  _OutputIterator)
1320    *  overloaded for input iterators and forward iterator as result.
1321   */
1322   template<typename _InputIterator, typename _ForwardIterator>
1323     _ForwardIterator
1324     __unique_copy(_InputIterator __first, _InputIterator __last,
1325                   _ForwardIterator __result,
1326                   input_iterator_tag, forward_iterator_tag)
1327     {
1328       // concept requirements -- taken care of in dispatching function
1329       *__result = *__first;
1330       while (++__first != __last)
1331         if (!(*__result == *__first))
1332           *++__result = *__first;
1333       return ++__result;
1334     }
1335
1336   /**
1337    *  This is an uglified
1338    *  unique_copy(_InputIterator, _InputIterator, _OutputIterator,
1339    *              _BinaryPredicate)
1340    *  overloaded for forward iterators and output iterator as result.
1341   */
1342   template<typename _ForwardIterator, typename _OutputIterator,
1343            typename _BinaryPredicate>
1344     _OutputIterator
1345     __unique_copy(_ForwardIterator __first, _ForwardIterator __last,
1346                   _OutputIterator __result, _BinaryPredicate __binary_pred,
1347                   forward_iterator_tag, output_iterator_tag)
1348     {
1349       // concept requirements -- iterators already checked
1350       __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
1351           typename iterator_traits<_ForwardIterator>::value_type,
1352           typename iterator_traits<_ForwardIterator>::value_type>)
1353
1354       _ForwardIterator __next = __first;
1355       *__result = *__first;
1356       while (++__next != __last)
1357         if (!bool(__binary_pred(*__first, *__next)))
1358           {
1359             __first = __next;
1360             *++__result = *__first;
1361           }
1362       return ++__result;
1363     }
1364
1365   /**
1366    *  This is an uglified
1367    *  unique_copy(_InputIterator, _InputIterator, _OutputIterator,
1368    *              _BinaryPredicate)
1369    *  overloaded for input iterators and output iterator as result.
1370   */
1371   template<typename _InputIterator, typename _OutputIterator,
1372            typename _BinaryPredicate>
1373     _OutputIterator
1374     __unique_copy(_InputIterator __first, _InputIterator __last,
1375                   _OutputIterator __result, _BinaryPredicate __binary_pred,
1376                   input_iterator_tag, output_iterator_tag)
1377     {
1378       // concept requirements -- iterators already checked
1379       __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
1380           typename iterator_traits<_InputIterator>::value_type,
1381           typename iterator_traits<_InputIterator>::value_type>)
1382
1383       typename iterator_traits<_InputIterator>::value_type __value = *__first;
1384       *__result = __value;
1385       while (++__first != __last)
1386         if (!bool(__binary_pred(__value, *__first)))
1387           {
1388             __value = *__first;
1389             *++__result = __value;
1390           }
1391       return ++__result;
1392     }
1393
1394   /**
1395    *  This is an uglified
1396    *  unique_copy(_InputIterator, _InputIterator, _OutputIterator,
1397    *              _BinaryPredicate)
1398    *  overloaded for input iterators and forward iterator as result.
1399   */
1400   template<typename _InputIterator, typename _ForwardIterator,
1401            typename _BinaryPredicate>
1402     _ForwardIterator
1403     __unique_copy(_InputIterator __first, _InputIterator __last,
1404                   _ForwardIterator __result, _BinaryPredicate __binary_pred,
1405                   input_iterator_tag, forward_iterator_tag)
1406     {
1407       // concept requirements -- iterators already checked
1408       __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
1409           typename iterator_traits<_ForwardIterator>::value_type,
1410           typename iterator_traits<_InputIterator>::value_type>)
1411
1412       *__result = *__first;
1413       while (++__first != __last)
1414         if (!bool(__binary_pred(*__result, *__first)))
1415           *++__result = *__first;
1416       return ++__result;
1417     }
1418
1419   /**
1420    *  This is an uglified reverse(_BidirectionalIterator,
1421    *                              _BidirectionalIterator)
1422    *  overloaded for bidirectional iterators.
1423   */
1424   template<typename _BidirectionalIterator>
1425     void
1426     __reverse(_BidirectionalIterator __first, _BidirectionalIterator __last,
1427               bidirectional_iterator_tag)
1428     {
1429       while (true)
1430         if (__first == __last || __first == --__last)
1431           return;
1432         else
1433           {
1434             std::iter_swap(__first, __last);
1435             ++__first;
1436           }
1437     }
1438
1439   /**
1440    *  This is an uglified reverse(_BidirectionalIterator,
1441    *                              _BidirectionalIterator)
1442    *  overloaded for random access iterators.
1443   */
1444   template<typename _RandomAccessIterator>
1445     void
1446     __reverse(_RandomAccessIterator __first, _RandomAccessIterator __last,
1447               random_access_iterator_tag)
1448     {
1449       if (__first == __last)
1450         return;
1451       --__last;
1452       while (__first < __last)
1453         {
1454           std::iter_swap(__first, __last);
1455           ++__first;
1456           --__last;
1457         }
1458     }
1459
1460   /**
1461    *  @brief Reverse a sequence.
1462    *  @ingroup mutating_algorithms
1463    *  @param  __first  A bidirectional iterator.
1464    *  @param  __last   A bidirectional iterator.
1465    *  @return   reverse() returns no value.
1466    *
1467    *  Reverses the order of the elements in the range @p [__first,__last),
1468    *  so that the first element becomes the last etc.
1469    *  For every @c i such that @p 0<=i<=(__last-__first)/2), @p reverse()
1470    *  swaps @p *(__first+i) and @p *(__last-(i+1))
1471   */
1472   template<typename _BidirectionalIterator>
1473     inline void
1474     reverse(_BidirectionalIterator __first, _BidirectionalIterator __last)
1475     {
1476       // concept requirements
1477       __glibcxx_function_requires(_Mutable_BidirectionalIteratorConcept<
1478                                   _BidirectionalIterator>)
1479       __glibcxx_requires_valid_range(__first, __last);
1480       std::__reverse(__first, __last, std::__iterator_category(__first));
1481     }
1482
1483   /**
1484    *  @brief Copy a sequence, reversing its elements.
1485    *  @ingroup mutating_algorithms
1486    *  @param  __first   A bidirectional iterator.
1487    *  @param  __last    A bidirectional iterator.
1488    *  @param  __result  An output iterator.
1489    *  @return  An iterator designating the end of the resulting sequence.
1490    *
1491    *  Copies the elements in the range @p [__first,__last) to the
1492    *  range @p [__result,__result+(__last-__first)) such that the
1493    *  order of the elements is reversed.  For every @c i such that @p
1494    *  0<=i<=(__last-__first), @p reverse_copy() performs the
1495    *  assignment @p *(__result+(__last-__first)-i) = *(__first+i).
1496    *  The ranges @p [__first,__last) and @p
1497    *  [__result,__result+(__last-__first)) must not overlap.
1498   */
1499   template<typename _BidirectionalIterator, typename _OutputIterator>
1500     _OutputIterator
1501     reverse_copy(_BidirectionalIterator __first, _BidirectionalIterator __last,
1502                  _OutputIterator __result)
1503     {
1504       // concept requirements
1505       __glibcxx_function_requires(_BidirectionalIteratorConcept<
1506                                   _BidirectionalIterator>)
1507       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
1508                 typename iterator_traits<_BidirectionalIterator>::value_type>)
1509       __glibcxx_requires_valid_range(__first, __last);
1510
1511       while (__first != __last)
1512         {
1513           --__last;
1514           *__result = *__last;
1515           ++__result;
1516         }
1517       return __result;
1518     }
1519
1520   /**
1521    *  This is a helper function for the rotate algorithm specialized on RAIs.
1522    *  It returns the greatest common divisor of two integer values.
1523   */
1524   template<typename _EuclideanRingElement>
1525     _EuclideanRingElement
1526     __gcd(_EuclideanRingElement __m, _EuclideanRingElement __n)
1527     {
1528       while (__n != 0)
1529         {
1530           _EuclideanRingElement __t = __m % __n;
1531           __m = __n;
1532           __n = __t;
1533         }
1534       return __m;
1535     }
1536
1537   /// This is a helper function for the rotate algorithm.
1538   template<typename _ForwardIterator>
1539     void
1540     __rotate(_ForwardIterator __first,
1541              _ForwardIterator __middle,
1542              _ForwardIterator __last,
1543              forward_iterator_tag)
1544     {
1545       if (__first == __middle || __last  == __middle)
1546         return;
1547
1548       _ForwardIterator __first2 = __middle;
1549       do
1550         {
1551           std::iter_swap(__first, __first2);
1552           ++__first;
1553           ++__first2;
1554           if (__first == __middle)
1555             __middle = __first2;
1556         }
1557       while (__first2 != __last);
1558
1559       __first2 = __middle;
1560
1561       while (__first2 != __last)
1562         {
1563           std::iter_swap(__first, __first2);
1564           ++__first;
1565           ++__first2;
1566           if (__first == __middle)
1567             __middle = __first2;
1568           else if (__first2 == __last)
1569             __first2 = __middle;
1570         }
1571     }
1572
1573    /// This is a helper function for the rotate algorithm.
1574   template<typename _BidirectionalIterator>
1575     void
1576     __rotate(_BidirectionalIterator __first,
1577              _BidirectionalIterator __middle,
1578              _BidirectionalIterator __last,
1579               bidirectional_iterator_tag)
1580     {
1581       // concept requirements
1582       __glibcxx_function_requires(_Mutable_BidirectionalIteratorConcept<
1583                                   _BidirectionalIterator>)
1584
1585       if (__first == __middle || __last  == __middle)
1586         return;
1587
1588       std::__reverse(__first,  __middle, bidirectional_iterator_tag());
1589       std::__reverse(__middle, __last,   bidirectional_iterator_tag());
1590
1591       while (__first != __middle && __middle != __last)
1592         {
1593           std::iter_swap(__first, --__last);
1594           ++__first;
1595         }
1596
1597       if (__first == __middle)
1598         std::__reverse(__middle, __last,   bidirectional_iterator_tag());
1599       else
1600         std::__reverse(__first,  __middle, bidirectional_iterator_tag());
1601     }
1602
1603   /// This is a helper function for the rotate algorithm.
1604   template<typename _RandomAccessIterator>
1605     void
1606     __rotate(_RandomAccessIterator __first,
1607              _RandomAccessIterator __middle,
1608              _RandomAccessIterator __last,
1609              random_access_iterator_tag)
1610     {
1611       // concept requirements
1612       __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
1613                                   _RandomAccessIterator>)
1614
1615       if (__first == __middle || __last  == __middle)
1616         return;
1617
1618       typedef typename iterator_traits<_RandomAccessIterator>::difference_type
1619         _Distance;
1620       typedef typename iterator_traits<_RandomAccessIterator>::value_type
1621         _ValueType;
1622
1623       _Distance __n = __last   - __first;
1624       _Distance __k = __middle - __first;
1625
1626       if (__k == __n - __k)
1627         {
1628           std::swap_ranges(__first, __middle, __middle);
1629           return;
1630         }
1631
1632       _RandomAccessIterator __p = __first;
1633
1634       for (;;)
1635         {
1636           if (__k < __n - __k)
1637             {
1638               if (__is_pod(_ValueType) && __k == 1)
1639                 {
1640                   _ValueType __t = _GLIBCXX_MOVE(*__p);
1641                   _GLIBCXX_MOVE3(__p + 1, __p + __n, __p);
1642                   *(__p + __n - 1) = _GLIBCXX_MOVE(__t);
1643                   return;
1644                 }
1645               _RandomAccessIterator __q = __p + __k;
1646               for (_Distance __i = 0; __i < __n - __k; ++ __i)
1647                 {
1648                   std::iter_swap(__p, __q);
1649                   ++__p;
1650                   ++__q;
1651                 }
1652               __n %= __k;
1653               if (__n == 0)
1654                 return;
1655               std::swap(__n, __k);
1656               __k = __n - __k;
1657             }
1658           else
1659             {
1660               __k = __n - __k;
1661               if (__is_pod(_ValueType) && __k == 1)
1662                 {
1663                   _ValueType __t = _GLIBCXX_MOVE(*(__p + __n - 1));
1664                   _GLIBCXX_MOVE_BACKWARD3(__p, __p + __n - 1, __p + __n);
1665                   *__p = _GLIBCXX_MOVE(__t);
1666                   return;
1667                 }
1668               _RandomAccessIterator __q = __p + __n;
1669               __p = __q - __k;
1670               for (_Distance __i = 0; __i < __n - __k; ++ __i)
1671                 {
1672                   --__p;
1673                   --__q;
1674                   std::iter_swap(__p, __q);
1675                 }
1676               __n %= __k;
1677               if (__n == 0)
1678                 return;
1679               std::swap(__n, __k);
1680             }
1681         }
1682     }
1683
1684   /**
1685    *  @brief Rotate the elements of a sequence.
1686    *  @ingroup mutating_algorithms
1687    *  @param  __first   A forward iterator.
1688    *  @param  __middle  A forward iterator.
1689    *  @param  __last    A forward iterator.
1690    *  @return  Nothing.
1691    *
1692    *  Rotates the elements of the range @p [__first,__last) by 
1693    *  @p (__middle - __first) positions so that the element at @p __middle
1694    *  is moved to @p __first, the element at @p __middle+1 is moved to
1695    *  @p __first+1 and so on for each element in the range
1696    *  @p [__first,__last).
1697    *
1698    *  This effectively swaps the ranges @p [__first,__middle) and
1699    *  @p [__middle,__last).
1700    *
1701    *  Performs
1702    *   @p *(__first+(n+(__last-__middle))%(__last-__first))=*(__first+n)
1703    *  for each @p n in the range @p [0,__last-__first).
1704   */
1705   template<typename _ForwardIterator>
1706     inline void
1707     rotate(_ForwardIterator __first, _ForwardIterator __middle,
1708            _ForwardIterator __last)
1709     {
1710       // concept requirements
1711       __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
1712                                   _ForwardIterator>)
1713       __glibcxx_requires_valid_range(__first, __middle);
1714       __glibcxx_requires_valid_range(__middle, __last);
1715
1716       typedef typename iterator_traits<_ForwardIterator>::iterator_category
1717         _IterType;
1718       std::__rotate(__first, __middle, __last, _IterType());
1719     }
1720
1721   /**
1722    *  @brief Copy a sequence, rotating its elements.
1723    *  @ingroup mutating_algorithms
1724    *  @param  __first   A forward iterator.
1725    *  @param  __middle  A forward iterator.
1726    *  @param  __last    A forward iterator.
1727    *  @param  __result  An output iterator.
1728    *  @return   An iterator designating the end of the resulting sequence.
1729    *
1730    *  Copies the elements of the range @p [__first,__last) to the
1731    *  range beginning at @result, rotating the copied elements by 
1732    *  @p (__middle-__first) positions so that the element at @p __middle
1733    *  is moved to @p __result, the element at @p __middle+1 is moved
1734    *  to @p __result+1 and so on for each element in the range @p
1735    *  [__first,__last).
1736    *
1737    *  Performs 
1738    *  @p *(__result+(n+(__last-__middle))%(__last-__first))=*(__first+n)
1739    *  for each @p n in the range @p [0,__last-__first).
1740   */
1741   template<typename _ForwardIterator, typename _OutputIterator>
1742     _OutputIterator
1743     rotate_copy(_ForwardIterator __first, _ForwardIterator __middle,
1744                 _ForwardIterator __last, _OutputIterator __result)
1745     {
1746       // concept requirements
1747       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
1748       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
1749                 typename iterator_traits<_ForwardIterator>::value_type>)
1750       __glibcxx_requires_valid_range(__first, __middle);
1751       __glibcxx_requires_valid_range(__middle, __last);
1752
1753       return std::copy(__first, __middle,
1754                        std::copy(__middle, __last, __result));
1755     }
1756
1757   /// This is a helper function...
1758   template<typename _ForwardIterator, typename _Predicate>
1759     _ForwardIterator
1760     __partition(_ForwardIterator __first, _ForwardIterator __last,
1761                 _Predicate __pred, forward_iterator_tag)
1762     {
1763       if (__first == __last)
1764         return __first;
1765
1766       while (__pred(*__first))
1767         if (++__first == __last)
1768           return __first;
1769
1770       _ForwardIterator __next = __first;
1771
1772       while (++__next != __last)
1773         if (__pred(*__next))
1774           {
1775             std::iter_swap(__first, __next);
1776             ++__first;
1777           }
1778
1779       return __first;
1780     }
1781
1782   /// This is a helper function...
1783   template<typename _BidirectionalIterator, typename _Predicate>
1784     _BidirectionalIterator
1785     __partition(_BidirectionalIterator __first, _BidirectionalIterator __last,
1786                 _Predicate __pred, bidirectional_iterator_tag)
1787     {
1788       while (true)
1789         {
1790           while (true)
1791             if (__first == __last)
1792               return __first;
1793             else if (__pred(*__first))
1794               ++__first;
1795             else
1796               break;
1797           --__last;
1798           while (true)
1799             if (__first == __last)
1800               return __first;
1801             else if (!bool(__pred(*__last)))
1802               --__last;
1803             else
1804               break;
1805           std::iter_swap(__first, __last);
1806           ++__first;
1807         }
1808     }
1809
1810   // partition
1811
1812   /// This is a helper function...
1813   /// Requires __len != 0 and !__pred(*__first),
1814   /// same as __stable_partition_adaptive.
1815   template<typename _ForwardIterator, typename _Predicate, typename _Distance>
1816     _ForwardIterator
1817     __inplace_stable_partition(_ForwardIterator __first,
1818                                _Predicate __pred, _Distance __len)
1819     {
1820       if (__len == 1)
1821         return __first;
1822       _ForwardIterator __middle = __first;
1823       std::advance(__middle, __len / 2);
1824       _ForwardIterator __left_split =
1825         std::__inplace_stable_partition(__first, __pred, __len / 2);
1826       // Advance past true-predicate values to satisfy this
1827       // function's preconditions.
1828       _Distance __right_len = __len - __len / 2;
1829       _ForwardIterator __right_split =
1830         std::__find_if_not_n(__middle, __right_len, __pred);
1831       if (__right_len)
1832         __right_split = std::__inplace_stable_partition(__middle,
1833                                                         __pred,
1834                                                         __right_len);
1835       std::rotate(__left_split, __middle, __right_split);
1836       std::advance(__left_split, std::distance(__middle, __right_split));
1837       return __left_split;
1838     }
1839
1840   /// This is a helper function...
1841   /// Requires __first != __last and !__pred(*__first)
1842   /// and __len == distance(__first, __last).
1843   ///
1844   /// !__pred(*__first) allows us to guarantee that we don't
1845   /// move-assign an element onto itself.
1846   template<typename _ForwardIterator, typename _Pointer, typename _Predicate,
1847            typename _Distance>
1848     _ForwardIterator
1849     __stable_partition_adaptive(_ForwardIterator __first,
1850                                 _ForwardIterator __last,
1851                                 _Predicate __pred, _Distance __len,
1852                                 _Pointer __buffer,
1853                                 _Distance __buffer_size)
1854     {
1855       if (__len <= __buffer_size)
1856         {
1857           _ForwardIterator __result1 = __first;
1858           _Pointer __result2 = __buffer;
1859           // The precondition guarantees that !__pred(*__first), so
1860           // move that element to the buffer before starting the loop.
1861           // This ensures that we only call __pred once per element.
1862           *__result2 = _GLIBCXX_MOVE(*__first);
1863           ++__result2;
1864           ++__first;
1865           for (; __first != __last; ++__first)
1866             if (__pred(*__first))
1867               {
1868                 *__result1 = _GLIBCXX_MOVE(*__first);
1869                 ++__result1;
1870               }
1871             else
1872               {
1873                 *__result2 = _GLIBCXX_MOVE(*__first);
1874                 ++__result2;
1875               }
1876           _GLIBCXX_MOVE3(__buffer, __result2, __result1);
1877           return __result1;
1878         }
1879       else
1880         {
1881           _ForwardIterator __middle = __first;
1882           std::advance(__middle, __len / 2);
1883           _ForwardIterator __left_split =
1884             std::__stable_partition_adaptive(__first, __middle, __pred,
1885                                              __len / 2, __buffer,
1886                                              __buffer_size);
1887           // Advance past true-predicate values to satisfy this
1888           // function's preconditions.
1889           _Distance __right_len = __len - __len / 2;
1890           _ForwardIterator __right_split =
1891             std::__find_if_not_n(__middle, __right_len, __pred);
1892           if (__right_len)
1893             __right_split =
1894               std::__stable_partition_adaptive(__right_split, __last, __pred,
1895                                                __right_len,
1896                                                __buffer, __buffer_size);
1897           std::rotate(__left_split, __middle, __right_split);
1898           std::advance(__left_split, std::distance(__middle, __right_split));
1899           return __left_split;
1900         }
1901     }
1902
1903   /**
1904    *  @brief Move elements for which a predicate is true to the beginning
1905    *         of a sequence, preserving relative ordering.
1906    *  @ingroup mutating_algorithms
1907    *  @param  __first   A forward iterator.
1908    *  @param  __last    A forward iterator.
1909    *  @param  __pred    A predicate functor.
1910    *  @return  An iterator @p middle such that @p __pred(i) is true for each
1911    *  iterator @p i in the range @p [first,middle) and false for each @p i
1912    *  in the range @p [middle,last).
1913    *
1914    *  Performs the same function as @p partition() with the additional
1915    *  guarantee that the relative ordering of elements in each group is
1916    *  preserved, so any two elements @p x and @p y in the range
1917    *  @p [__first,__last) such that @p __pred(x)==__pred(y) will have the same
1918    *  relative ordering after calling @p stable_partition().
1919   */
1920   template<typename _ForwardIterator, typename _Predicate>
1921     _ForwardIterator
1922     stable_partition(_ForwardIterator __first, _ForwardIterator __last,
1923                      _Predicate __pred)
1924     {
1925       // concept requirements
1926       __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
1927                                   _ForwardIterator>)
1928       __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
1929             typename iterator_traits<_ForwardIterator>::value_type>)
1930       __glibcxx_requires_valid_range(__first, __last);
1931
1932       __first = std::__find_if_not(__first, __last, __pred);
1933
1934       if (__first == __last)
1935         return __first;
1936       else
1937         {
1938           typedef typename iterator_traits<_ForwardIterator>::value_type
1939             _ValueType;
1940           typedef typename iterator_traits<_ForwardIterator>::difference_type
1941             _DistanceType;
1942
1943           _Temporary_buffer<_ForwardIterator, _ValueType> __buf(__first,
1944                                                                 __last);
1945         if (__buf.size() > 0)
1946           return
1947             std::__stable_partition_adaptive(__first, __last, __pred,
1948                                           _DistanceType(__buf.requested_size()),
1949                                           __buf.begin(),
1950                                           _DistanceType(__buf.size()));
1951         else
1952           return
1953             std::__inplace_stable_partition(__first, __pred,
1954                                          _DistanceType(__buf.requested_size()));
1955         }
1956     }
1957
1958   /// This is a helper function for the sort routines.
1959   template<typename _RandomAccessIterator>
1960     void
1961     __heap_select(_RandomAccessIterator __first,
1962                   _RandomAccessIterator __middle,
1963                   _RandomAccessIterator __last)
1964     {
1965       std::make_heap(__first, __middle);
1966       for (_RandomAccessIterator __i = __middle; __i < __last; ++__i)
1967         if (*__i < *__first)
1968           std::__pop_heap(__first, __middle, __i);
1969     }
1970
1971   /// This is a helper function for the sort routines.
1972   template<typename _RandomAccessIterator, typename _Compare>
1973     void
1974     __heap_select(_RandomAccessIterator __first,
1975                   _RandomAccessIterator __middle,
1976                   _RandomAccessIterator __last, _Compare __comp)
1977     {
1978       std::make_heap(__first, __middle, __comp);
1979       for (_RandomAccessIterator __i = __middle; __i < __last; ++__i)
1980         if (__comp(*__i, *__first))
1981           std::__pop_heap(__first, __middle, __i, __comp);
1982     }
1983
1984   // partial_sort
1985
1986   /**
1987    *  @brief Copy the smallest elements of a sequence.
1988    *  @ingroup sorting_algorithms
1989    *  @param  __first   An iterator.
1990    *  @param  __last    Another iterator.
1991    *  @param  __result_first   A random-access iterator.
1992    *  @param  __result_last    Another random-access iterator.
1993    *  @return   An iterator indicating the end of the resulting sequence.
1994    *
1995    *  Copies and sorts the smallest N values from the range @p [__first,__last)
1996    *  to the range beginning at @p __result_first, where the number of
1997    *  elements to be copied, @p N, is the smaller of @p (__last-__first) and
1998    *  @p (__result_last-__result_first).
1999    *  After the sort if @e i and @e j are iterators in the range
2000    *  @p [__result_first,__result_first+N) such that i precedes j then
2001    *  *j<*i is false.
2002    *  The value returned is @p __result_first+N.
2003   */
2004   template<typename _InputIterator, typename _RandomAccessIterator>
2005     _RandomAccessIterator
2006     partial_sort_copy(_InputIterator __first, _InputIterator __last,
2007                       _RandomAccessIterator __result_first,
2008                       _RandomAccessIterator __result_last)
2009     {
2010       typedef typename iterator_traits<_InputIterator>::value_type
2011         _InputValueType;
2012       typedef typename iterator_traits<_RandomAccessIterator>::value_type
2013         _OutputValueType;
2014       typedef typename iterator_traits<_RandomAccessIterator>::difference_type
2015         _DistanceType;
2016
2017       // concept requirements
2018       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
2019       __glibcxx_function_requires(_ConvertibleConcept<_InputValueType,
2020                                   _OutputValueType>)
2021       __glibcxx_function_requires(_LessThanOpConcept<_InputValueType,
2022                                                      _OutputValueType>)
2023       __glibcxx_function_requires(_LessThanComparableConcept<_OutputValueType>)
2024       __glibcxx_requires_valid_range(__first, __last);
2025       __glibcxx_requires_valid_range(__result_first, __result_last);
2026
2027       if (__result_first == __result_last)
2028         return __result_last;
2029       _RandomAccessIterator __result_real_last = __result_first;
2030       while(__first != __last && __result_real_last != __result_last)
2031         {
2032           *__result_real_last = *__first;
2033           ++__result_real_last;
2034           ++__first;
2035         }
2036       std::make_heap(__result_first, __result_real_last);
2037       while (__first != __last)
2038         {
2039           if (*__first < *__result_first)
2040             std::__adjust_heap(__result_first, _DistanceType(0),
2041                                _DistanceType(__result_real_last
2042                                              - __result_first),
2043                                _InputValueType(*__first));
2044           ++__first;
2045         }
2046       std::sort_heap(__result_first, __result_real_last);
2047       return __result_real_last;
2048     }
2049
2050   /**
2051    *  @brief Copy the smallest elements of a sequence using a predicate for
2052    *         comparison.
2053    *  @ingroup sorting_algorithms
2054    *  @param  __first   An input iterator.
2055    *  @param  __last    Another input iterator.
2056    *  @param  __result_first   A random-access iterator.
2057    *  @param  __result_last    Another random-access iterator.
2058    *  @param  __comp    A comparison functor.
2059    *  @return   An iterator indicating the end of the resulting sequence.
2060    *
2061    *  Copies and sorts the smallest N values from the range @p [__first,__last)
2062    *  to the range beginning at @p result_first, where the number of
2063    *  elements to be copied, @p N, is the smaller of @p (__last-__first) and
2064    *  @p (__result_last-__result_first).
2065    *  After the sort if @e i and @e j are iterators in the range
2066    *  @p [__result_first,__result_first+N) such that i precedes j then
2067    *  @p __comp(*j,*i) is false.
2068    *  The value returned is @p __result_first+N.
2069   */
2070   template<typename _InputIterator, typename _RandomAccessIterator, typename _Compare>
2071     _RandomAccessIterator
2072     partial_sort_copy(_InputIterator __first, _InputIterator __last,
2073                       _RandomAccessIterator __result_first,
2074                       _RandomAccessIterator __result_last,
2075                       _Compare __comp)
2076     {
2077       typedef typename iterator_traits<_InputIterator>::value_type
2078         _InputValueType;
2079       typedef typename iterator_traits<_RandomAccessIterator>::value_type
2080         _OutputValueType;
2081       typedef typename iterator_traits<_RandomAccessIterator>::difference_type
2082         _DistanceType;
2083
2084       // concept requirements
2085       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
2086       __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
2087                                   _RandomAccessIterator>)
2088       __glibcxx_function_requires(_ConvertibleConcept<_InputValueType,
2089                                   _OutputValueType>)
2090       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2091                                   _InputValueType, _OutputValueType>)
2092       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2093                                   _OutputValueType, _OutputValueType>)
2094       __glibcxx_requires_valid_range(__first, __last);
2095       __glibcxx_requires_valid_range(__result_first, __result_last);
2096
2097       if (__result_first == __result_last)
2098         return __result_last;
2099       _RandomAccessIterator __result_real_last = __result_first;
2100       while(__first != __last && __result_real_last != __result_last)
2101         {
2102           *__result_real_last = *__first;
2103           ++__result_real_last;
2104           ++__first;
2105         }
2106       std::make_heap(__result_first, __result_real_last, __comp);
2107       while (__first != __last)
2108         {
2109           if (__comp(*__first, *__result_first))
2110             std::__adjust_heap(__result_first, _DistanceType(0),
2111                                _DistanceType(__result_real_last
2112                                              - __result_first),
2113                                _InputValueType(*__first),
2114                                __comp);
2115           ++__first;
2116         }
2117       std::sort_heap(__result_first, __result_real_last, __comp);
2118       return __result_real_last;
2119     }
2120
2121   /// This is a helper function for the sort routine.
2122   template<typename _RandomAccessIterator>
2123     void
2124     __unguarded_linear_insert(_RandomAccessIterator __last)
2125     {
2126       typename iterator_traits<_RandomAccessIterator>::value_type
2127         __val = _GLIBCXX_MOVE(*__last);
2128       _RandomAccessIterator __next = __last;
2129       --__next;
2130       while (__val < *__next)
2131         {
2132           *__last = _GLIBCXX_MOVE(*__next);
2133           __last = __next;
2134           --__next;
2135         }
2136       *__last = _GLIBCXX_MOVE(__val);
2137     }
2138
2139   /// This is a helper function for the sort routine.
2140   template<typename _RandomAccessIterator, typename _Compare>
2141     void
2142     __unguarded_linear_insert(_RandomAccessIterator __last,
2143                               _Compare __comp)
2144     {
2145       typename iterator_traits<_RandomAccessIterator>::value_type
2146         __val = _GLIBCXX_MOVE(*__last);
2147       _RandomAccessIterator __next = __last;
2148       --__next;
2149       while (__comp(__val, *__next))
2150         {
2151           *__last = _GLIBCXX_MOVE(*__next);
2152           __last = __next;
2153           --__next;
2154         }
2155       *__last = _GLIBCXX_MOVE(__val);
2156     }
2157
2158   /// This is a helper function for the sort routine.
2159   template<typename _RandomAccessIterator>
2160     void
2161     __insertion_sort(_RandomAccessIterator __first,
2162                      _RandomAccessIterator __last)
2163     {
2164       if (__first == __last)
2165         return;
2166
2167       for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i)
2168         {
2169           if (*__i < *__first)
2170             {
2171               typename iterator_traits<_RandomAccessIterator>::value_type
2172                 __val = _GLIBCXX_MOVE(*__i);
2173               _GLIBCXX_MOVE_BACKWARD3(__first, __i, __i + 1);
2174               *__first = _GLIBCXX_MOVE(__val);
2175             }
2176           else
2177             std::__unguarded_linear_insert(__i);
2178         }
2179     }
2180
2181   /// This is a helper function for the sort routine.
2182   template<typename _RandomAccessIterator, typename _Compare>
2183     void
2184     __insertion_sort(_RandomAccessIterator __first,
2185                      _RandomAccessIterator __last, _Compare __comp)
2186     {
2187       if (__first == __last) return;
2188
2189       for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i)
2190         {
2191           if (__comp(*__i, *__first))
2192             {
2193               typename iterator_traits<_RandomAccessIterator>::value_type
2194                 __val = _GLIBCXX_MOVE(*__i);
2195               _GLIBCXX_MOVE_BACKWARD3(__first, __i, __i + 1);
2196               *__first = _GLIBCXX_MOVE(__val);
2197             }
2198           else
2199             std::__unguarded_linear_insert(__i, __comp);
2200         }
2201     }
2202
2203   /// This is a helper function for the sort routine.
2204   template<typename _RandomAccessIterator>
2205     inline void
2206     __unguarded_insertion_sort(_RandomAccessIterator __first,
2207                                _RandomAccessIterator __last)
2208     {
2209       typedef typename iterator_traits<_RandomAccessIterator>::value_type
2210         _ValueType;
2211
2212       for (_RandomAccessIterator __i = __first; __i != __last; ++__i)
2213         std::__unguarded_linear_insert(__i);
2214     }
2215
2216   /// This is a helper function for the sort routine.
2217   template<typename _RandomAccessIterator, typename _Compare>
2218     inline void
2219     __unguarded_insertion_sort(_RandomAccessIterator __first,
2220                                _RandomAccessIterator __last, _Compare __comp)
2221     {
2222       typedef typename iterator_traits<_RandomAccessIterator>::value_type
2223         _ValueType;
2224
2225       for (_RandomAccessIterator __i = __first; __i != __last; ++__i)
2226         std::__unguarded_linear_insert(__i, __comp);
2227     }
2228
2229   /**
2230    *  @doctodo
2231    *  This controls some aspect of the sort routines.
2232   */
2233   enum { _S_threshold = 16 };
2234
2235   /// This is a helper function for the sort routine.
2236   template<typename _RandomAccessIterator>
2237     void
2238     __final_insertion_sort(_RandomAccessIterator __first,
2239                            _RandomAccessIterator __last)
2240     {
2241       if (__last - __first > int(_S_threshold))
2242         {
2243           std::__insertion_sort(__first, __first + int(_S_threshold));
2244           std::__unguarded_insertion_sort(__first + int(_S_threshold), __last);
2245         }
2246       else
2247         std::__insertion_sort(__first, __last);
2248     }
2249
2250   /// This is a helper function for the sort routine.
2251   template<typename _RandomAccessIterator, typename _Compare>
2252     void
2253     __final_insertion_sort(_RandomAccessIterator __first,
2254                            _RandomAccessIterator __last, _Compare __comp)
2255     {
2256       if (__last - __first > int(_S_threshold))
2257         {
2258           std::__insertion_sort(__first, __first + int(_S_threshold), __comp);
2259           std::__unguarded_insertion_sort(__first + int(_S_threshold), __last,
2260                                           __comp);
2261         }
2262       else
2263         std::__insertion_sort(__first, __last, __comp);
2264     }
2265
2266   /// This is a helper function...
2267   template<typename _RandomAccessIterator, typename _Tp>
2268     _RandomAccessIterator
2269     __unguarded_partition(_RandomAccessIterator __first,
2270                           _RandomAccessIterator __last, const _Tp& __pivot)
2271     {
2272       while (true)
2273         {
2274           while (*__first < __pivot)
2275             ++__first;
2276           --__last;
2277           while (__pivot < *__last)
2278             --__last;
2279           if (!(__first < __last))
2280             return __first;
2281           std::iter_swap(__first, __last);
2282           ++__first;
2283         }
2284     }
2285
2286   /// This is a helper function...
2287   template<typename _RandomAccessIterator, typename _Tp, typename _Compare>
2288     _RandomAccessIterator
2289     __unguarded_partition(_RandomAccessIterator __first,
2290                           _RandomAccessIterator __last,
2291                           const _Tp& __pivot, _Compare __comp)
2292     {
2293       while (true)
2294         {
2295           while (__comp(*__first, __pivot))
2296             ++__first;
2297           --__last;
2298           while (__comp(__pivot, *__last))
2299             --__last;
2300           if (!(__first < __last))
2301             return __first;
2302           std::iter_swap(__first, __last);
2303           ++__first;
2304         }
2305     }
2306
2307   /// This is a helper function...
2308   template<typename _RandomAccessIterator>
2309     inline _RandomAccessIterator
2310     __unguarded_partition_pivot(_RandomAccessIterator __first,
2311                                 _RandomAccessIterator __last)
2312     {
2313       _RandomAccessIterator __mid = __first + (__last - __first) / 2;
2314       std::__move_median_to_first(__first, __first + 1, __mid, __last - 1);
2315       return std::__unguarded_partition(__first + 1, __last, *__first);
2316     }
2317
2318
2319   /// This is a helper function...
2320   template<typename _RandomAccessIterator, typename _Compare>
2321     inline _RandomAccessIterator
2322     __unguarded_partition_pivot(_RandomAccessIterator __first,
2323                                 _RandomAccessIterator __last, _Compare __comp)
2324     {
2325       _RandomAccessIterator __mid = __first + (__last - __first) / 2;
2326       std::__move_median_to_first(__first, __first + 1, __mid, __last - 1,
2327                                   __comp);
2328       return std::__unguarded_partition(__first + 1, __last, *__first, __comp);
2329     }
2330
2331   /// This is a helper function for the sort routine.
2332   template<typename _RandomAccessIterator, typename _Size>
2333     void
2334     __introsort_loop(_RandomAccessIterator __first,
2335                      _RandomAccessIterator __last,
2336                      _Size __depth_limit)
2337     {
2338       while (__last - __first > int(_S_threshold))
2339         {
2340           if (__depth_limit == 0)
2341             {
2342               _GLIBCXX_STD_A::partial_sort(__first, __last, __last);
2343               return;
2344             }
2345           --__depth_limit;
2346           _RandomAccessIterator __cut =
2347             std::__unguarded_partition_pivot(__first, __last);
2348           std::__introsort_loop(__cut, __last, __depth_limit);
2349           __last = __cut;
2350         }
2351     }
2352
2353   /// This is a helper function for the sort routine.
2354   template<typename _RandomAccessIterator, typename _Size, typename _Compare>
2355     void
2356     __introsort_loop(_RandomAccessIterator __first,
2357                      _RandomAccessIterator __last,
2358                      _Size __depth_limit, _Compare __comp)
2359     {
2360       while (__last - __first > int(_S_threshold))
2361         {
2362           if (__depth_limit == 0)
2363             {
2364               _GLIBCXX_STD_A::partial_sort(__first, __last, __last, __comp);
2365               return;
2366             }
2367           --__depth_limit;
2368           _RandomAccessIterator __cut =
2369             std::__unguarded_partition_pivot(__first, __last, __comp);
2370           std::__introsort_loop(__cut, __last, __depth_limit, __comp);
2371           __last = __cut;
2372         }
2373     }
2374
2375   // sort
2376
2377   template<typename _RandomAccessIterator, typename _Size>
2378     void
2379     __introselect(_RandomAccessIterator __first, _RandomAccessIterator __nth,
2380                   _RandomAccessIterator __last, _Size __depth_limit)
2381     {
2382       typedef typename iterator_traits<_RandomAccessIterator>::value_type
2383         _ValueType;
2384
2385       while (__last - __first > 3)
2386         {
2387           if (__depth_limit == 0)
2388             {
2389               std::__heap_select(__first, __nth + 1, __last);
2390
2391               // Place the nth largest element in its final position.
2392               std::iter_swap(__first, __nth);
2393               return;
2394             }
2395           --__depth_limit;
2396           _RandomAccessIterator __cut =
2397             std::__unguarded_partition_pivot(__first, __last);
2398           if (__cut <= __nth)
2399             __first = __cut;
2400           else
2401             __last = __cut;
2402         }
2403       std::__insertion_sort(__first, __last);
2404     }
2405
2406   template<typename _RandomAccessIterator, typename _Size, typename _Compare>
2407     void
2408     __introselect(_RandomAccessIterator __first, _RandomAccessIterator __nth,
2409                   _RandomAccessIterator __last, _Size __depth_limit,
2410                   _Compare __comp)
2411     {
2412       typedef typename iterator_traits<_RandomAccessIterator>::value_type
2413         _ValueType;
2414
2415       while (__last - __first > 3)
2416         {
2417           if (__depth_limit == 0)
2418             {
2419               std::__heap_select(__first, __nth + 1, __last, __comp);
2420               // Place the nth largest element in its final position.
2421               std::iter_swap(__first, __nth);
2422               return;
2423             }
2424           --__depth_limit;
2425           _RandomAccessIterator __cut =
2426             std::__unguarded_partition_pivot(__first, __last, __comp);
2427           if (__cut <= __nth)
2428             __first = __cut;
2429           else
2430             __last = __cut;
2431         }
2432       std::__insertion_sort(__first, __last, __comp);
2433     }
2434
2435   // nth_element
2436
2437   // lower_bound moved to stl_algobase.h
2438
2439   /**
2440    *  @brief Finds the first position in which @p __val could be inserted
2441    *         without changing the ordering.
2442    *  @ingroup binary_search_algorithms
2443    *  @param  __first   An iterator.
2444    *  @param  __last    Another iterator.
2445    *  @param  __val     The search term.
2446    *  @param  __comp    A functor to use for comparisons.
2447    *  @return An iterator pointing to the first element <em>not less
2448    *           than</em> @p __val, or end() if every element is less
2449    *           than @p __val.
2450    *  @ingroup binary_search_algorithms
2451    *
2452    *  The comparison function should have the same effects on ordering as
2453    *  the function used for the initial sort.
2454   */
2455   template<typename _ForwardIterator, typename _Tp, typename _Compare>
2456     _ForwardIterator
2457     lower_bound(_ForwardIterator __first, _ForwardIterator __last,
2458                 const _Tp& __val, _Compare __comp)
2459     {
2460       typedef typename iterator_traits<_ForwardIterator>::value_type
2461         _ValueType;
2462       typedef typename iterator_traits<_ForwardIterator>::difference_type
2463         _DistanceType;
2464
2465       // concept requirements
2466       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
2467       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2468                                   _ValueType, _Tp>)
2469       __glibcxx_requires_partitioned_lower_pred(__first, __last,
2470                                                 __val, __comp);
2471
2472       _DistanceType __len = std::distance(__first, __last);
2473
2474       while (__len > 0)
2475         {
2476           _DistanceType __half = __len >> 1;
2477           _ForwardIterator __middle = __first;
2478           std::advance(__middle, __half);
2479           if (__comp(*__middle, __val))
2480             {
2481               __first = __middle;
2482               ++__first;
2483               __len = __len - __half - 1;
2484             }
2485           else
2486             __len = __half;
2487         }
2488       return __first;
2489     }
2490
2491   /**
2492    *  @brief Finds the last position in which @p __val could be inserted
2493    *         without changing the ordering.
2494    *  @ingroup binary_search_algorithms
2495    *  @param  __first   An iterator.
2496    *  @param  __last    Another iterator.
2497    *  @param  __val     The search term.
2498    *  @return  An iterator pointing to the first element greater than @p __val,
2499    *           or end() if no elements are greater than @p __val.
2500    *  @ingroup binary_search_algorithms
2501   */
2502   template<typename _ForwardIterator, typename _Tp>
2503     _ForwardIterator
2504     upper_bound(_ForwardIterator __first, _ForwardIterator __last,
2505                 const _Tp& __val)
2506     {
2507       typedef typename iterator_traits<_ForwardIterator>::value_type
2508         _ValueType;
2509       typedef typename iterator_traits<_ForwardIterator>::difference_type
2510         _DistanceType;
2511
2512       // concept requirements
2513       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
2514       __glibcxx_function_requires(_LessThanOpConcept<_Tp, _ValueType>)
2515       __glibcxx_requires_partitioned_upper(__first, __last, __val);
2516
2517       _DistanceType __len = std::distance(__first, __last);
2518
2519       while (__len > 0)
2520         {
2521           _DistanceType __half = __len >> 1;
2522           _ForwardIterator __middle = __first;
2523           std::advance(__middle, __half);
2524           if (__val < *__middle)
2525             __len = __half;
2526           else
2527             {
2528               __first = __middle;
2529               ++__first;
2530               __len = __len - __half - 1;
2531             }
2532         }
2533       return __first;
2534     }
2535
2536   /**
2537    *  @brief Finds the last position in which @p __val could be inserted
2538    *         without changing the ordering.
2539    *  @ingroup binary_search_algorithms
2540    *  @param  __first   An iterator.
2541    *  @param  __last    Another iterator.
2542    *  @param  __val     The search term.
2543    *  @param  __comp    A functor to use for comparisons.
2544    *  @return  An iterator pointing to the first element greater than @p __val,
2545    *           or end() if no elements are greater than @p __val.
2546    *  @ingroup binary_search_algorithms
2547    *
2548    *  The comparison function should have the same effects on ordering as
2549    *  the function used for the initial sort.
2550   */
2551   template<typename _ForwardIterator, typename _Tp, typename _Compare>
2552     _ForwardIterator
2553     upper_bound(_ForwardIterator __first, _ForwardIterator __last,
2554                 const _Tp& __val, _Compare __comp)
2555     {
2556       typedef typename iterator_traits<_ForwardIterator>::value_type
2557         _ValueType;
2558       typedef typename iterator_traits<_ForwardIterator>::difference_type
2559         _DistanceType;
2560
2561       // concept requirements
2562       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
2563       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2564 &