OSDN Git Service

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