libstdc++
stl_algo.h
Go to the documentation of this file.
00001 // Algorithm implementation -*- C++ -*-
00002 
00003 // Copyright (C) 2001-2013 Free Software Foundation, Inc.
00004 //
00005 // This file is part of the GNU ISO C++ Library.  This library is free
00006 // software; you can redistribute it and/or modify it under the
00007 // terms of the GNU General Public License as published by the
00008 // Free Software Foundation; either version 3, or (at your option)
00009 // any later version.
00010 
00011 // This library is distributed in the hope that it will be useful,
00012 // but WITHOUT ANY WARRANTY; without even the implied warranty of
00013 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
00014 // GNU General Public License for more details.
00015 
00016 // Under Section 7 of GPL version 3, you are granted additional
00017 // permissions described in the GCC Runtime Library Exception, version
00018 // 3.1, as published by the Free Software Foundation.
00019 
00020 // You should have received a copy of the GNU General Public License and
00021 // a copy of the GCC Runtime Library Exception along with this program;
00022 // see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
00023 // <http://www.gnu.org/licenses/>.
00024 
00025 /*
00026  *
00027  * Copyright (c) 1994
00028  * Hewlett-Packard Company
00029  *
00030  * Permission to use, copy, modify, distribute and sell this software
00031  * and its documentation for any purpose is hereby granted without fee,
00032  * provided that the above copyright notice appear in all copies and
00033  * that both that copyright notice and this permission notice appear
00034  * in supporting documentation.  Hewlett-Packard Company makes no
00035  * representations about the suitability of this software for any
00036  * purpose.  It is provided "as is" without express or implied warranty.
00037  *
00038  *
00039  * Copyright (c) 1996
00040  * Silicon Graphics Computer Systems, Inc.
00041  *
00042  * Permission to use, copy, modify, distribute and sell this software
00043  * and its documentation for any purpose is hereby granted without fee,
00044  * provided that the above copyright notice appear in all copies and
00045  * that both that copyright notice and this permission notice appear
00046  * in supporting documentation.  Silicon Graphics makes no
00047  * representations about the suitability of this software for any
00048  * purpose.  It is provided "as is" without express or implied warranty.
00049  */
00050 
00051 /** @file bits/stl_algo.h
00052  *  This is an internal header file, included by other library headers.
00053  *  Do not attempt to use it directly. @headername{algorithm}
00054  */
00055 
00056 #ifndef _STL_ALGO_H
00057 #define _STL_ALGO_H 1
00058 
00059 #include <cstdlib>             // for rand
00060 #include <bits/algorithmfwd.h>
00061 #include <bits/stl_heap.h>
00062 #include <bits/stl_tempbuf.h>  // for _Temporary_buffer
00063 
00064 #if __cplusplus >= 201103L
00065 #include <random>     // for std::uniform_int_distribution
00066 #include <functional> // for std::bind
00067 #endif
00068 
00069 // See concept_check.h for the __glibcxx_*_requires macros.
00070 
00071 namespace std _GLIBCXX_VISIBILITY(default)
00072 {
00073 _GLIBCXX_BEGIN_NAMESPACE_VERSION
00074 
00075   /// Swaps the median value of *__a, *__b and *__c to *__result
00076   template<typename _Iterator>
00077     void
00078     __move_median_to_first(_Iterator __result, _Iterator __a,
00079                _Iterator __b, _Iterator __c)
00080     {
00081       // concept requirements
00082       __glibcxx_function_requires(_LessThanComparableConcept<
00083         typename iterator_traits<_Iterator>::value_type>)
00084 
00085       if (*__a < *__b)
00086     {
00087       if (*__b < *__c)
00088         std::iter_swap(__result, __b);
00089       else if (*__a < *__c)
00090         std::iter_swap(__result, __c);
00091       else
00092         std::iter_swap(__result, __a);
00093     }
00094       else if (*__a < *__c)
00095         std::iter_swap(__result, __a);
00096       else if (*__b < *__c)
00097     std::iter_swap(__result, __c);
00098       else
00099     std::iter_swap(__result, __b);
00100     }
00101 
00102   /// Swaps the median value of *__a, *__b and *__c under __comp to *__result
00103   template<typename _Iterator, typename _Compare>
00104     void
00105     __move_median_to_first(_Iterator __result, _Iterator __a,
00106                _Iterator __b, _Iterator __c,
00107                _Compare __comp)
00108     {
00109       // concept requirements
00110       __glibcxx_function_requires(_BinaryFunctionConcept<_Compare, bool,
00111         typename iterator_traits<_Iterator>::value_type,
00112         typename iterator_traits<_Iterator>::value_type>)
00113 
00114       if (__comp(*__a, *__b))
00115     {
00116       if (__comp(*__b, *__c))
00117         std::iter_swap(__result, __b);
00118       else if (__comp(*__a, *__c))
00119         std::iter_swap(__result, __c);
00120       else
00121         std::iter_swap(__result, __a);
00122     }
00123       else if (__comp(*__a, *__c))
00124     std::iter_swap(__result, __a);
00125       else if (__comp(*__b, *__c))
00126     std::iter_swap(__result, __c);
00127       else
00128     std::iter_swap(__result, __b);
00129     }
00130 
00131   // for_each
00132 
00133   /// This is an overload used by find() for the Input Iterator case.
00134   template<typename _InputIterator, typename _Tp>
00135     inline _InputIterator
00136     __find(_InputIterator __first, _InputIterator __last,
00137        const _Tp& __val, input_iterator_tag)
00138     {
00139       while (__first != __last && !(*__first == __val))
00140     ++__first;
00141       return __first;
00142     }
00143 
00144   /// This is an overload used by find_if() for the Input Iterator case.
00145   template<typename _InputIterator, typename _Predicate>
00146     inline _InputIterator
00147     __find_if(_InputIterator __first, _InputIterator __last,
00148           _Predicate __pred, input_iterator_tag)
00149     {
00150       while (__first != __last && !bool(__pred(*__first)))
00151     ++__first;
00152       return __first;
00153     }
00154 
00155   /// This is an overload used by find() for the RAI case.
00156   template<typename _RandomAccessIterator, typename _Tp>
00157     _RandomAccessIterator
00158     __find(_RandomAccessIterator __first, _RandomAccessIterator __last,
00159        const _Tp& __val, random_access_iterator_tag)
00160     {
00161       typename iterator_traits<_RandomAccessIterator>::difference_type
00162     __trip_count = (__last - __first) >> 2;
00163 
00164       for (; __trip_count > 0; --__trip_count)
00165     {
00166       if (*__first == __val)
00167         return __first;
00168       ++__first;
00169 
00170       if (*__first == __val)
00171         return __first;
00172       ++__first;
00173 
00174       if (*__first == __val)
00175         return __first;
00176       ++__first;
00177 
00178       if (*__first == __val)
00179         return __first;
00180       ++__first;
00181     }
00182 
00183       switch (__last - __first)
00184     {
00185     case 3:
00186       if (*__first == __val)
00187         return __first;
00188       ++__first;
00189     case 2:
00190       if (*__first == __val)
00191         return __first;
00192       ++__first;
00193     case 1:
00194       if (*__first == __val)
00195         return __first;
00196       ++__first;
00197     case 0:
00198     default:
00199       return __last;
00200     }
00201     }
00202 
00203   /// This is an overload used by find_if() for the RAI case.
00204   template<typename _RandomAccessIterator, typename _Predicate>
00205     _RandomAccessIterator
00206     __find_if(_RandomAccessIterator __first, _RandomAccessIterator __last,
00207           _Predicate __pred, random_access_iterator_tag)
00208     {
00209       typename iterator_traits<_RandomAccessIterator>::difference_type
00210     __trip_count = (__last - __first) >> 2;
00211 
00212       for (; __trip_count > 0; --__trip_count)
00213     {
00214       if (__pred(*__first))
00215         return __first;
00216       ++__first;
00217 
00218       if (__pred(*__first))
00219         return __first;
00220       ++__first;
00221 
00222       if (__pred(*__first))
00223         return __first;
00224       ++__first;
00225 
00226       if (__pred(*__first))
00227         return __first;
00228       ++__first;
00229     }
00230 
00231       switch (__last - __first)
00232     {
00233     case 3:
00234       if (__pred(*__first))
00235         return __first;
00236       ++__first;
00237     case 2:
00238       if (__pred(*__first))
00239         return __first;
00240       ++__first;
00241     case 1:
00242       if (__pred(*__first))
00243         return __first;
00244       ++__first;
00245     case 0:
00246     default:
00247       return __last;
00248     }
00249     }
00250 
00251   /// This is an overload used by find_if_not() for the Input Iterator case.
00252   template<typename _InputIterator, typename _Predicate>
00253     inline _InputIterator
00254     __find_if_not(_InputIterator __first, _InputIterator __last,
00255           _Predicate __pred, input_iterator_tag)
00256     {
00257       while (__first != __last && bool(__pred(*__first)))
00258     ++__first;
00259       return __first;
00260     }
00261 
00262   /// This is an overload used by find_if_not() for the RAI case.
00263   template<typename _RandomAccessIterator, typename _Predicate>
00264     _RandomAccessIterator
00265     __find_if_not(_RandomAccessIterator __first, _RandomAccessIterator __last,
00266           _Predicate __pred, random_access_iterator_tag)
00267     {
00268       typename iterator_traits<_RandomAccessIterator>::difference_type
00269     __trip_count = (__last - __first) >> 2;
00270 
00271       for (; __trip_count > 0; --__trip_count)
00272     {
00273       if (!bool(__pred(*__first)))
00274         return __first;
00275       ++__first;
00276 
00277       if (!bool(__pred(*__first)))
00278         return __first;
00279       ++__first;
00280 
00281       if (!bool(__pred(*__first)))
00282         return __first;
00283       ++__first;
00284 
00285       if (!bool(__pred(*__first)))
00286         return __first;
00287       ++__first;
00288     }
00289 
00290       switch (__last - __first)
00291     {
00292     case 3:
00293       if (!bool(__pred(*__first)))
00294         return __first;
00295       ++__first;
00296     case 2:
00297       if (!bool(__pred(*__first)))
00298         return __first;
00299       ++__first;
00300     case 1:
00301       if (!bool(__pred(*__first)))
00302         return __first;
00303       ++__first;
00304     case 0:
00305     default:
00306       return __last;
00307     }
00308     }
00309 
00310   /// Provided for stable_partition to use.
00311   template<typename _InputIterator, typename _Predicate>
00312     inline _InputIterator
00313     __find_if_not(_InputIterator __first, _InputIterator __last,
00314           _Predicate __pred)
00315     {
00316       return std::__find_if_not(__first, __last, __pred,
00317                 std::__iterator_category(__first));
00318     }
00319 
00320   /// Like find_if_not(), but uses and updates a count of the
00321   /// remaining range length instead of comparing against an end
00322   /// iterator.
00323   template<typename _InputIterator, typename _Predicate, typename _Distance>
00324     _InputIterator
00325     __find_if_not_n(_InputIterator __first, _Distance& __len, _Predicate __pred)
00326     {
00327       for (; __len; --__len, ++__first)
00328     if (!bool(__pred(*__first)))
00329       break;
00330       return __first;
00331     }
00332 
00333   // set_difference
00334   // set_intersection
00335   // set_symmetric_difference
00336   // set_union
00337   // for_each
00338   // find
00339   // find_if
00340   // find_first_of
00341   // adjacent_find
00342   // count
00343   // count_if
00344   // search
00345 
00346   /**
00347    *  This is an uglified
00348    *  search_n(_ForwardIterator, _ForwardIterator, _Integer, const _Tp&)
00349    *  overloaded for forward iterators.
00350   */
00351   template<typename _ForwardIterator, typename _Integer, typename _Tp>
00352     _ForwardIterator
00353     __search_n(_ForwardIterator __first, _ForwardIterator __last,
00354            _Integer __count, const _Tp& __val,
00355            std::forward_iterator_tag)
00356     {
00357       __first = _GLIBCXX_STD_A::find(__first, __last, __val);
00358       while (__first != __last)
00359     {
00360       typename iterator_traits<_ForwardIterator>::difference_type
00361         __n = __count;
00362       _ForwardIterator __i = __first;
00363       ++__i;
00364       while (__i != __last && __n != 1 && *__i == __val)
00365         {
00366           ++__i;
00367           --__n;
00368         }
00369       if (__n == 1)
00370         return __first;
00371       if (__i == __last)
00372         return __last;
00373       __first = _GLIBCXX_STD_A::find(++__i, __last, __val);
00374     }
00375       return __last;
00376     }
00377 
00378   /**
00379    *  This is an uglified
00380    *  search_n(_ForwardIterator, _ForwardIterator, _Integer, const _Tp&)
00381    *  overloaded for random access iterators.
00382   */
00383   template<typename _RandomAccessIter, typename _Integer, typename _Tp>
00384     _RandomAccessIter
00385     __search_n(_RandomAccessIter __first, _RandomAccessIter __last,
00386            _Integer __count, const _Tp& __val, 
00387            std::random_access_iterator_tag)
00388     {
00389       
00390       typedef typename std::iterator_traits<_RandomAccessIter>::difference_type
00391     _DistanceType;
00392 
00393       _DistanceType __tailSize = __last - __first;
00394       _DistanceType __remainder = __count;
00395 
00396       while (__remainder <= __tailSize) // the main loop...
00397     {
00398       __first += __remainder;
00399       __tailSize -= __remainder;
00400       // __first here is always pointing to one past the last element of
00401       // next possible match.
00402       _RandomAccessIter __backTrack = __first; 
00403       while (*--__backTrack == __val)
00404         {
00405           if (--__remainder == 0)
00406             return (__first - __count); // Success
00407         }
00408       __remainder = __count + 1 - (__first - __backTrack);
00409     }
00410       return __last; // Failure
00411     }
00412 
00413   // search_n
00414 
00415   /**
00416    *  This is an uglified
00417    *  search_n(_ForwardIterator, _ForwardIterator, _Integer, const _Tp&,
00418    *           _BinaryPredicate)
00419    *  overloaded for forward iterators.
00420   */
00421   template<typename _ForwardIterator, typename _Integer, typename _Tp,
00422            typename _BinaryPredicate>
00423     _ForwardIterator
00424     __search_n(_ForwardIterator __first, _ForwardIterator __last,
00425            _Integer __count, const _Tp& __val,
00426            _BinaryPredicate __binary_pred, std::forward_iterator_tag)
00427     {
00428       while (__first != __last && !bool(__binary_pred(*__first, __val)))
00429         ++__first;
00430 
00431       while (__first != __last)
00432     {
00433       typename iterator_traits<_ForwardIterator>::difference_type
00434         __n = __count;
00435       _ForwardIterator __i = __first;
00436       ++__i;
00437       while (__i != __last && __n != 1 && bool(__binary_pred(*__i, __val)))
00438         {
00439           ++__i;
00440           --__n;
00441         }
00442       if (__n == 1)
00443         return __first;
00444       if (__i == __last)
00445         return __last;
00446       __first = ++__i;
00447       while (__first != __last
00448          && !bool(__binary_pred(*__first, __val)))
00449         ++__first;
00450     }
00451       return __last;
00452     }
00453 
00454   /**
00455    *  This is an uglified
00456    *  search_n(_ForwardIterator, _ForwardIterator, _Integer, const _Tp&,
00457    *           _BinaryPredicate)
00458    *  overloaded for random access iterators.
00459   */
00460   template<typename _RandomAccessIter, typename _Integer, typename _Tp,
00461        typename _BinaryPredicate>
00462     _RandomAccessIter
00463     __search_n(_RandomAccessIter __first, _RandomAccessIter __last,
00464            _Integer __count, const _Tp& __val,
00465            _BinaryPredicate __binary_pred, std::random_access_iterator_tag)
00466     {
00467       
00468       typedef typename std::iterator_traits<_RandomAccessIter>::difference_type
00469     _DistanceType;
00470 
00471       _DistanceType __tailSize = __last - __first;
00472       _DistanceType __remainder = __count;
00473 
00474       while (__remainder <= __tailSize) // the main loop...
00475     {
00476       __first += __remainder;
00477       __tailSize -= __remainder;
00478       // __first here is always pointing to one past the last element of
00479       // next possible match.
00480       _RandomAccessIter __backTrack = __first; 
00481       while (__binary_pred(*--__backTrack, __val))
00482         {
00483           if (--__remainder == 0)
00484             return (__first - __count); // Success
00485         }
00486       __remainder = __count + 1 - (__first - __backTrack);
00487     }
00488       return __last; // Failure
00489     }
00490 
00491   // find_end for forward iterators.
00492   template<typename _ForwardIterator1, typename _ForwardIterator2>
00493     _ForwardIterator1
00494     __find_end(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
00495            _ForwardIterator2 __first2, _ForwardIterator2 __last2,
00496            forward_iterator_tag, forward_iterator_tag)
00497     {
00498       if (__first2 == __last2)
00499     return __last1;
00500       else
00501     {
00502       _ForwardIterator1 __result = __last1;
00503       while (1)
00504         {
00505           _ForwardIterator1 __new_result
00506         = _GLIBCXX_STD_A::search(__first1, __last1, __first2, __last2);
00507           if (__new_result == __last1)
00508         return __result;
00509           else
00510         {
00511           __result = __new_result;
00512           __first1 = __new_result;
00513           ++__first1;
00514         }
00515         }
00516     }
00517     }
00518 
00519   template<typename _ForwardIterator1, typename _ForwardIterator2,
00520        typename _BinaryPredicate>
00521     _ForwardIterator1
00522     __find_end(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
00523            _ForwardIterator2 __first2, _ForwardIterator2 __last2,
00524            forward_iterator_tag, forward_iterator_tag,
00525            _BinaryPredicate __comp)
00526     {
00527       if (__first2 == __last2)
00528     return __last1;
00529       else
00530     {
00531       _ForwardIterator1 __result = __last1;
00532       while (1)
00533         {
00534           _ForwardIterator1 __new_result
00535         = _GLIBCXX_STD_A::search(__first1, __last1, __first2,
00536                      __last2, __comp);
00537           if (__new_result == __last1)
00538         return __result;
00539           else
00540         {
00541           __result = __new_result;
00542           __first1 = __new_result;
00543           ++__first1;
00544         }
00545         }
00546     }
00547     }
00548 
00549   // find_end for bidirectional iterators (much faster).
00550   template<typename _BidirectionalIterator1, typename _BidirectionalIterator2>
00551     _BidirectionalIterator1
00552     __find_end(_BidirectionalIterator1 __first1,
00553            _BidirectionalIterator1 __last1,
00554            _BidirectionalIterator2 __first2,
00555            _BidirectionalIterator2 __last2,
00556            bidirectional_iterator_tag, bidirectional_iterator_tag)
00557     {
00558       // concept requirements
00559       __glibcxx_function_requires(_BidirectionalIteratorConcept<
00560                   _BidirectionalIterator1>)
00561       __glibcxx_function_requires(_BidirectionalIteratorConcept<
00562                   _BidirectionalIterator2>)
00563 
00564       typedef reverse_iterator<_BidirectionalIterator1> _RevIterator1;
00565       typedef reverse_iterator<_BidirectionalIterator2> _RevIterator2;
00566 
00567       _RevIterator1 __rlast1(__first1);
00568       _RevIterator2 __rlast2(__first2);
00569       _RevIterator1 __rresult = _GLIBCXX_STD_A::search(_RevIterator1(__last1),
00570                                __rlast1,
00571                                _RevIterator2(__last2),
00572                                __rlast2);
00573 
00574       if (__rresult == __rlast1)
00575     return __last1;
00576       else
00577     {
00578       _BidirectionalIterator1 __result = __rresult.base();
00579       std::advance(__result, -std::distance(__first2, __last2));
00580       return __result;
00581     }
00582     }
00583 
00584   template<typename _BidirectionalIterator1, typename _BidirectionalIterator2,
00585        typename _BinaryPredicate>
00586     _BidirectionalIterator1
00587     __find_end(_BidirectionalIterator1 __first1,
00588            _BidirectionalIterator1 __last1,
00589            _BidirectionalIterator2 __first2,
00590            _BidirectionalIterator2 __last2,
00591            bidirectional_iterator_tag, bidirectional_iterator_tag,
00592            _BinaryPredicate __comp)
00593     {
00594       // concept requirements
00595       __glibcxx_function_requires(_BidirectionalIteratorConcept<
00596                   _BidirectionalIterator1>)
00597       __glibcxx_function_requires(_BidirectionalIteratorConcept<
00598                   _BidirectionalIterator2>)
00599 
00600       typedef reverse_iterator<_BidirectionalIterator1> _RevIterator1;
00601       typedef reverse_iterator<_BidirectionalIterator2> _RevIterator2;
00602 
00603       _RevIterator1 __rlast1(__first1);
00604       _RevIterator2 __rlast2(__first2);
00605       _RevIterator1 __rresult = std::search(_RevIterator1(__last1), __rlast1,
00606                         _RevIterator2(__last2), __rlast2,
00607                         __comp);
00608 
00609       if (__rresult == __rlast1)
00610     return __last1;
00611       else
00612     {
00613       _BidirectionalIterator1 __result = __rresult.base();
00614       std::advance(__result, -std::distance(__first2, __last2));
00615       return __result;
00616     }
00617     }
00618 
00619   /**
00620    *  @brief  Find last matching subsequence in a sequence.
00621    *  @ingroup non_mutating_algorithms
00622    *  @param  __first1  Start of range to search.
00623    *  @param  __last1   End of range to search.
00624    *  @param  __first2  Start of sequence to match.
00625    *  @param  __last2   End of sequence to match.
00626    *  @return   The last iterator @c i in the range
00627    *  @p [__first1,__last1-(__last2-__first2)) such that @c *(i+N) ==
00628    *  @p *(__first2+N) for each @c N in the range @p
00629    *  [0,__last2-__first2), or @p __last1 if no such iterator exists.
00630    *
00631    *  Searches the range @p [__first1,__last1) for a sub-sequence that
00632    *  compares equal value-by-value with the sequence given by @p
00633    *  [__first2,__last2) and returns an iterator to the __first
00634    *  element of the sub-sequence, or @p __last1 if the sub-sequence
00635    *  is not found.  The sub-sequence will be the last such
00636    *  subsequence contained in [__first,__last1).
00637    *
00638    *  Because the sub-sequence must lie completely within the range @p
00639    *  [__first1,__last1) it must start at a position less than @p
00640    *  __last1-(__last2-__first2) where @p __last2-__first2 is the
00641    *  length of the sub-sequence.  This means that the returned
00642    *  iterator @c i will be in the range @p
00643    *  [__first1,__last1-(__last2-__first2))
00644   */
00645   template<typename _ForwardIterator1, typename _ForwardIterator2>
00646     inline _ForwardIterator1
00647     find_end(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
00648          _ForwardIterator2 __first2, _ForwardIterator2 __last2)
00649     {
00650       // concept requirements
00651       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator1>)
00652       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator2>)
00653       __glibcxx_function_requires(_EqualOpConcept<
00654         typename iterator_traits<_ForwardIterator1>::value_type,
00655         typename iterator_traits<_ForwardIterator2>::value_type>)
00656       __glibcxx_requires_valid_range(__first1, __last1);
00657       __glibcxx_requires_valid_range(__first2, __last2);
00658 
00659       return std::__find_end(__first1, __last1, __first2, __last2,
00660                  std::__iterator_category(__first1),
00661                  std::__iterator_category(__first2));
00662     }
00663 
00664   /**
00665    *  @brief  Find last matching subsequence in a sequence using a predicate.
00666    *  @ingroup non_mutating_algorithms
00667    *  @param  __first1  Start of range to search.
00668    *  @param  __last1   End of range to search.
00669    *  @param  __first2  Start of sequence to match.
00670    *  @param  __last2   End of sequence to match.
00671    *  @param  __comp    The predicate to use.
00672    *  @return The last iterator @c i in the range @p
00673    *  [__first1,__last1-(__last2-__first2)) such that @c
00674    *  predicate(*(i+N), @p (__first2+N)) is true for each @c N in the
00675    *  range @p [0,__last2-__first2), or @p __last1 if no such iterator
00676    *  exists.
00677    *
00678    *  Searches the range @p [__first1,__last1) for a sub-sequence that
00679    *  compares equal value-by-value with the sequence given by @p
00680    *  [__first2,__last2) using comp as a predicate and returns an
00681    *  iterator to the first element of the sub-sequence, or @p __last1
00682    *  if the sub-sequence is not found.  The sub-sequence will be the
00683    *  last such subsequence contained in [__first,__last1).
00684    *
00685    *  Because the sub-sequence must lie completely within the range @p
00686    *  [__first1,__last1) it must start at a position less than @p
00687    *  __last1-(__last2-__first2) where @p __last2-__first2 is the
00688    *  length of the sub-sequence.  This means that the returned
00689    *  iterator @c i will be in the range @p
00690    *  [__first1,__last1-(__last2-__first2))
00691   */
00692   template<typename _ForwardIterator1, typename _ForwardIterator2,
00693        typename _BinaryPredicate>
00694     inline _ForwardIterator1
00695     find_end(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
00696          _ForwardIterator2 __first2, _ForwardIterator2 __last2,
00697          _BinaryPredicate __comp)
00698     {
00699       // concept requirements
00700       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator1>)
00701       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator2>)
00702       __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
00703         typename iterator_traits<_ForwardIterator1>::value_type,
00704         typename iterator_traits<_ForwardIterator2>::value_type>)
00705       __glibcxx_requires_valid_range(__first1, __last1);
00706       __glibcxx_requires_valid_range(__first2, __last2);
00707 
00708       return std::__find_end(__first1, __last1, __first2, __last2,
00709                  std::__iterator_category(__first1),
00710                  std::__iterator_category(__first2),
00711                  __comp);
00712     }
00713 
00714 #if __cplusplus >= 201103L
00715   /**
00716    *  @brief  Checks that a predicate is true for all the elements
00717    *          of a sequence.
00718    *  @ingroup non_mutating_algorithms
00719    *  @param  __first   An input iterator.
00720    *  @param  __last    An input iterator.
00721    *  @param  __pred    A predicate.
00722    *  @return  True if the check is true, false otherwise.
00723    *
00724    *  Returns true if @p __pred is true for each element in the range
00725    *  @p [__first,__last), and false otherwise.
00726   */
00727   template<typename _InputIterator, typename _Predicate>
00728     inline bool
00729     all_of(_InputIterator __first, _InputIterator __last, _Predicate __pred)
00730     { return __last == std::find_if_not(__first, __last, __pred); }
00731 
00732   /**
00733    *  @brief  Checks that a predicate is false for all the elements
00734    *          of a sequence.
00735    *  @ingroup non_mutating_algorithms
00736    *  @param  __first   An input iterator.
00737    *  @param  __last    An input iterator.
00738    *  @param  __pred    A predicate.
00739    *  @return  True if the check is true, false otherwise.
00740    *
00741    *  Returns true if @p __pred is false for each element in the range
00742    *  @p [__first,__last), and false otherwise.
00743   */
00744   template<typename _InputIterator, typename _Predicate>
00745     inline bool
00746     none_of(_InputIterator __first, _InputIterator __last, _Predicate __pred)
00747     { return __last == _GLIBCXX_STD_A::find_if(__first, __last, __pred); }
00748 
00749   /**
00750    *  @brief  Checks that a predicate is false for at least an element
00751    *          of a sequence.
00752    *  @ingroup non_mutating_algorithms
00753    *  @param  __first   An input iterator.
00754    *  @param  __last    An input iterator.
00755    *  @param  __pred    A predicate.
00756    *  @return  True if the check is true, false otherwise.
00757    *
00758    *  Returns true if an element exists in the range @p
00759    *  [__first,__last) such that @p __pred is true, and false
00760    *  otherwise.
00761   */
00762   template<typename _InputIterator, typename _Predicate>
00763     inline bool
00764     any_of(_InputIterator __first, _InputIterator __last, _Predicate __pred)
00765     { return !std::none_of(__first, __last, __pred); }
00766 
00767   /**
00768    *  @brief  Find the first element in a sequence for which a
00769    *          predicate is false.
00770    *  @ingroup non_mutating_algorithms
00771    *  @param  __first  An input iterator.
00772    *  @param  __last   An input iterator.
00773    *  @param  __pred   A predicate.
00774    *  @return   The first iterator @c i in the range @p [__first,__last)
00775    *  such that @p __pred(*i) is false, or @p __last if no such iterator exists.
00776   */
00777   template<typename _InputIterator, typename _Predicate>
00778     inline _InputIterator
00779     find_if_not(_InputIterator __first, _InputIterator __last,
00780         _Predicate __pred)
00781     {
00782       // concept requirements
00783       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
00784       __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
00785           typename iterator_traits<_InputIterator>::value_type>)
00786       __glibcxx_requires_valid_range(__first, __last);
00787       return std::__find_if_not(__first, __last, __pred);
00788     }
00789 
00790   /**
00791    *  @brief  Checks whether the sequence is partitioned.
00792    *  @ingroup mutating_algorithms
00793    *  @param  __first  An input iterator.
00794    *  @param  __last   An input iterator.
00795    *  @param  __pred   A predicate.
00796    *  @return  True if the range @p [__first,__last) is partioned by @p __pred,
00797    *  i.e. if all elements that satisfy @p __pred appear before those that
00798    *  do not.
00799   */
00800   template<typename _InputIterator, typename _Predicate>
00801     inline bool
00802     is_partitioned(_InputIterator __first, _InputIterator __last,
00803            _Predicate __pred)
00804     {
00805       __first = std::find_if_not(__first, __last, __pred);
00806       return std::none_of(__first, __last, __pred);
00807     }
00808 
00809   /**
00810    *  @brief  Find the partition point of a partitioned range.
00811    *  @ingroup mutating_algorithms
00812    *  @param  __first   An iterator.
00813    *  @param  __last    Another iterator.
00814    *  @param  __pred    A predicate.
00815    *  @return  An iterator @p mid such that @p all_of(__first, mid, __pred)
00816    *           and @p none_of(mid, __last, __pred) are both true.
00817   */
00818   template<typename _ForwardIterator, typename _Predicate>
00819     _ForwardIterator
00820     partition_point(_ForwardIterator __first, _ForwardIterator __last,
00821             _Predicate __pred)
00822     {
00823       // concept requirements
00824       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
00825       __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
00826           typename iterator_traits<_ForwardIterator>::value_type>)
00827 
00828       // A specific debug-mode test will be necessary...
00829       __glibcxx_requires_valid_range(__first, __last);
00830 
00831       typedef typename iterator_traits<_ForwardIterator>::difference_type
00832     _DistanceType;
00833 
00834       _DistanceType __len = std::distance(__first, __last);
00835       _DistanceType __half;
00836       _ForwardIterator __middle;
00837 
00838       while (__len > 0)
00839     {
00840       __half = __len >> 1;
00841       __middle = __first;
00842       std::advance(__middle, __half);
00843       if (__pred(*__middle))
00844         {
00845           __first = __middle;
00846           ++__first;
00847           __len = __len - __half - 1;
00848         }
00849       else
00850         __len = __half;
00851     }
00852       return __first;
00853     }
00854 #endif
00855 
00856 
00857   /**
00858    *  @brief Copy a sequence, removing elements of a given value.
00859    *  @ingroup mutating_algorithms
00860    *  @param  __first   An input iterator.
00861    *  @param  __last    An input iterator.
00862    *  @param  __result  An output iterator.
00863    *  @param  __value   The value to be removed.
00864    *  @return   An iterator designating the end of the resulting sequence.
00865    *
00866    *  Copies each element in the range @p [__first,__last) not equal
00867    *  to @p __value to the range beginning at @p __result.
00868    *  remove_copy() is stable, so the relative order of elements that
00869    *  are copied is unchanged.
00870   */
00871   template<typename _InputIterator, typename _OutputIterator, typename _Tp>
00872     _OutputIterator
00873     remove_copy(_InputIterator __first, _InputIterator __last,
00874         _OutputIterator __result, const _Tp& __value)
00875     {
00876       // concept requirements
00877       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
00878       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
00879         typename iterator_traits<_InputIterator>::value_type>)
00880       __glibcxx_function_requires(_EqualOpConcept<
00881         typename iterator_traits<_InputIterator>::value_type, _Tp>)
00882       __glibcxx_requires_valid_range(__first, __last);
00883 
00884       for (; __first != __last; ++__first)
00885     if (!(*__first == __value))
00886       {
00887         *__result = *__first;
00888         ++__result;
00889       }
00890       return __result;
00891     }
00892 
00893   /**
00894    *  @brief Copy a sequence, removing elements for which a predicate is true.
00895    *  @ingroup mutating_algorithms
00896    *  @param  __first   An input iterator.
00897    *  @param  __last    An input iterator.
00898    *  @param  __result  An output iterator.
00899    *  @param  __pred    A predicate.
00900    *  @return   An iterator designating the end of the resulting sequence.
00901    *
00902    *  Copies each element in the range @p [__first,__last) for which
00903    *  @p __pred returns false to the range beginning at @p __result.
00904    *
00905    *  remove_copy_if() is stable, so the relative order of elements that are
00906    *  copied is unchanged.
00907   */
00908   template<typename _InputIterator, typename _OutputIterator,
00909        typename _Predicate>
00910     _OutputIterator
00911     remove_copy_if(_InputIterator __first, _InputIterator __last,
00912            _OutputIterator __result, _Predicate __pred)
00913     {
00914       // concept requirements
00915       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
00916       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
00917         typename iterator_traits<_InputIterator>::value_type>)
00918       __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
00919         typename iterator_traits<_InputIterator>::value_type>)
00920       __glibcxx_requires_valid_range(__first, __last);
00921 
00922       for (; __first != __last; ++__first)
00923     if (!bool(__pred(*__first)))
00924       {
00925         *__result = *__first;
00926         ++__result;
00927       }
00928       return __result;
00929     }
00930 
00931 #if __cplusplus >= 201103L
00932   /**
00933    *  @brief Copy the elements of a sequence for which a predicate is true.
00934    *  @ingroup mutating_algorithms
00935    *  @param  __first   An input iterator.
00936    *  @param  __last    An input iterator.
00937    *  @param  __result  An output iterator.
00938    *  @param  __pred    A predicate.
00939    *  @return   An iterator designating the end of the resulting sequence.
00940    *
00941    *  Copies each element in the range @p [__first,__last) for which
00942    *  @p __pred returns true to the range beginning at @p __result.
00943    *
00944    *  copy_if() is stable, so the relative order of elements that are
00945    *  copied is unchanged.
00946   */
00947   template<typename _InputIterator, typename _OutputIterator,
00948        typename _Predicate>
00949     _OutputIterator
00950     copy_if(_InputIterator __first, _InputIterator __last,
00951         _OutputIterator __result, _Predicate __pred)
00952     {
00953       // concept requirements
00954       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
00955       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
00956         typename iterator_traits<_InputIterator>::value_type>)
00957       __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
00958         typename iterator_traits<_InputIterator>::value_type>)
00959       __glibcxx_requires_valid_range(__first, __last);
00960 
00961       for (; __first != __last; ++__first)
00962     if (__pred(*__first))
00963       {
00964         *__result = *__first;
00965         ++__result;
00966       }
00967       return __result;
00968     }
00969 
00970 
00971   template<typename _InputIterator, typename _Size, typename _OutputIterator>
00972     _OutputIterator
00973     __copy_n(_InputIterator __first, _Size __n,
00974          _OutputIterator __result, input_iterator_tag)
00975     {
00976       if (__n > 0)
00977     {
00978       while (true)
00979         {
00980           *__result = *__first;
00981           ++__result;
00982           if (--__n > 0)
00983         ++__first;
00984           else
00985         break;
00986         }
00987     }
00988       return __result;
00989     }
00990 
00991   template<typename _RandomAccessIterator, typename _Size,
00992        typename _OutputIterator>
00993     inline _OutputIterator
00994     __copy_n(_RandomAccessIterator __first, _Size __n,
00995          _OutputIterator __result, random_access_iterator_tag)
00996     { return std::copy(__first, __first + __n, __result); }
00997 
00998   /**
00999    *  @brief Copies the range [first,first+n) into [result,result+n).
01000    *  @ingroup mutating_algorithms
01001    *  @param  __first  An input iterator.
01002    *  @param  __n      The number of elements to copy.
01003    *  @param  __result An output iterator.
01004    *  @return  result+n.
01005    *
01006    *  This inline function will boil down to a call to @c memmove whenever
01007    *  possible.  Failing that, if random access iterators are passed, then the
01008    *  loop count will be known (and therefore a candidate for compiler
01009    *  optimizations such as unrolling).
01010   */
01011   template<typename _InputIterator, typename _Size, typename _OutputIterator>
01012     inline _OutputIterator
01013     copy_n(_InputIterator __first, _Size __n, _OutputIterator __result)
01014     {
01015       // concept requirements
01016       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
01017       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
01018         typename iterator_traits<_InputIterator>::value_type>)
01019 
01020       return std::__copy_n(__first, __n, __result,
01021                std::__iterator_category(__first));
01022     }
01023 
01024   /**
01025    *  @brief Copy the elements of a sequence to separate output sequences
01026    *         depending on the truth value of a predicate.
01027    *  @ingroup mutating_algorithms
01028    *  @param  __first   An input iterator.
01029    *  @param  __last    An input iterator.
01030    *  @param  __out_true   An output iterator.
01031    *  @param  __out_false  An output iterator.
01032    *  @param  __pred    A predicate.
01033    *  @return   A pair designating the ends of the resulting sequences.
01034    *
01035    *  Copies each element in the range @p [__first,__last) for which
01036    *  @p __pred returns true to the range beginning at @p out_true
01037    *  and each element for which @p __pred returns false to @p __out_false.
01038   */
01039   template<typename _InputIterator, typename _OutputIterator1,
01040        typename _OutputIterator2, typename _Predicate>
01041     pair<_OutputIterator1, _OutputIterator2>
01042     partition_copy(_InputIterator __first, _InputIterator __last,
01043            _OutputIterator1 __out_true, _OutputIterator2 __out_false,
01044            _Predicate __pred)
01045     {
01046       // concept requirements
01047       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
01048       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator1,
01049         typename iterator_traits<_InputIterator>::value_type>)
01050       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator2,
01051         typename iterator_traits<_InputIterator>::value_type>)
01052       __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
01053         typename iterator_traits<_InputIterator>::value_type>)
01054       __glibcxx_requires_valid_range(__first, __last);
01055       
01056       for (; __first != __last; ++__first)
01057     if (__pred(*__first))
01058       {
01059         *__out_true = *__first;
01060         ++__out_true;
01061       }
01062     else
01063       {
01064         *__out_false = *__first;
01065         ++__out_false;
01066       }
01067 
01068       return pair<_OutputIterator1, _OutputIterator2>(__out_true, __out_false);
01069     }
01070 #endif
01071 
01072   /**
01073    *  @brief Remove elements from a sequence.
01074    *  @ingroup mutating_algorithms
01075    *  @param  __first  An input iterator.
01076    *  @param  __last   An input iterator.
01077    *  @param  __value  The value to be removed.
01078    *  @return   An iterator designating the end of the resulting sequence.
01079    *
01080    *  All elements equal to @p __value are removed from the range
01081    *  @p [__first,__last).
01082    *
01083    *  remove() is stable, so the relative order of elements that are
01084    *  not removed is unchanged.
01085    *
01086    *  Elements between the end of the resulting sequence and @p __last
01087    *  are still present, but their value is unspecified.
01088   */
01089   template<typename _ForwardIterator, typename _Tp>
01090     _ForwardIterator
01091     remove(_ForwardIterator __first, _ForwardIterator __last,
01092        const _Tp& __value)
01093     {
01094       // concept requirements
01095       __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
01096                   _ForwardIterator>)
01097       __glibcxx_function_requires(_EqualOpConcept<
01098         typename iterator_traits<_ForwardIterator>::value_type, _Tp>)
01099       __glibcxx_requires_valid_range(__first, __last);
01100 
01101       __first = _GLIBCXX_STD_A::find(__first, __last, __value);
01102       if(__first == __last)
01103         return __first;
01104       _ForwardIterator __result = __first;
01105       ++__first;
01106       for(; __first != __last; ++__first)
01107         if(!(*__first == __value))
01108           {
01109             *__result = _GLIBCXX_MOVE(*__first);
01110             ++__result;
01111           }
01112       return __result;
01113     }
01114 
01115   /**
01116    *  @brief Remove elements from a sequence using a predicate.
01117    *  @ingroup mutating_algorithms
01118    *  @param  __first  A forward iterator.
01119    *  @param  __last   A forward iterator.
01120    *  @param  __pred   A predicate.
01121    *  @return   An iterator designating the end of the resulting sequence.
01122    *
01123    *  All elements for which @p __pred returns true are removed from the range
01124    *  @p [__first,__last).
01125    *
01126    *  remove_if() is stable, so the relative order of elements that are
01127    *  not removed is unchanged.
01128    *
01129    *  Elements between the end of the resulting sequence and @p __last
01130    *  are still present, but their value is unspecified.
01131   */
01132   template<typename _ForwardIterator, typename _Predicate>
01133     _ForwardIterator
01134     remove_if(_ForwardIterator __first, _ForwardIterator __last,
01135           _Predicate __pred)
01136     {
01137       // concept requirements
01138       __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
01139                   _ForwardIterator>)
01140       __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
01141         typename iterator_traits<_ForwardIterator>::value_type>)
01142       __glibcxx_requires_valid_range(__first, __last);
01143 
01144       __first = _GLIBCXX_STD_A::find_if(__first, __last, __pred);
01145       if(__first == __last)
01146         return __first;
01147       _ForwardIterator __result = __first;
01148       ++__first;
01149       for(; __first != __last; ++__first)
01150         if(!bool(__pred(*__first)))
01151           {
01152             *__result = _GLIBCXX_MOVE(*__first);
01153             ++__result;
01154           }
01155       return __result;
01156     }
01157 
01158   /**
01159    *  @brief Remove consecutive duplicate values from a sequence.
01160    *  @ingroup mutating_algorithms
01161    *  @param  __first  A forward iterator.
01162    *  @param  __last   A forward iterator.
01163    *  @return  An iterator designating the end of the resulting sequence.
01164    *
01165    *  Removes all but the first element from each group of consecutive
01166    *  values that compare equal.
01167    *  unique() is stable, so the relative order of elements that are
01168    *  not removed is unchanged.
01169    *  Elements between the end of the resulting sequence and @p __last
01170    *  are still present, but their value is unspecified.
01171   */
01172   template<typename _ForwardIterator>
01173     _ForwardIterator
01174     unique(_ForwardIterator __first, _ForwardIterator __last)
01175     {
01176       // concept requirements
01177       __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
01178                   _ForwardIterator>)
01179       __glibcxx_function_requires(_EqualityComparableConcept<
01180              typename iterator_traits<_ForwardIterator>::value_type>)
01181       __glibcxx_requires_valid_range(__first, __last);
01182 
01183       // Skip the beginning, if already unique.
01184       __first = _GLIBCXX_STD_A::adjacent_find(__first, __last);
01185       if (__first == __last)
01186     return __last;
01187 
01188       // Do the real copy work.
01189       _ForwardIterator __dest = __first;
01190       ++__first;
01191       while (++__first != __last)
01192     if (!(*__dest == *__first))
01193       *++__dest = _GLIBCXX_MOVE(*__first);
01194       return ++__dest;
01195     }
01196 
01197   /**
01198    *  @brief Remove consecutive values from a sequence using a predicate.
01199    *  @ingroup mutating_algorithms
01200    *  @param  __first        A forward iterator.
01201    *  @param  __last         A forward iterator.
01202    *  @param  __binary_pred  A binary predicate.
01203    *  @return  An iterator designating the end of the resulting sequence.
01204    *
01205    *  Removes all but the first element from each group of consecutive
01206    *  values for which @p __binary_pred returns true.
01207    *  unique() is stable, so the relative order of elements that are
01208    *  not removed is unchanged.
01209    *  Elements between the end of the resulting sequence and @p __last
01210    *  are still present, but their value is unspecified.
01211   */
01212   template<typename _ForwardIterator, typename _BinaryPredicate>
01213     _ForwardIterator
01214     unique(_ForwardIterator __first, _ForwardIterator __last,
01215            _BinaryPredicate __binary_pred)
01216     {
01217       // concept requirements
01218       __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
01219                   _ForwardIterator>)
01220       __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
01221         typename iterator_traits<_ForwardIterator>::value_type,
01222         typename iterator_traits<_ForwardIterator>::value_type>)
01223       __glibcxx_requires_valid_range(__first, __last);
01224 
01225       // Skip the beginning, if already unique.
01226       __first = _GLIBCXX_STD_A::adjacent_find(__first, __last, __binary_pred);
01227       if (__first == __last)
01228     return __last;
01229 
01230       // Do the real copy work.
01231       _ForwardIterator __dest = __first;
01232       ++__first;
01233       while (++__first != __last)
01234     if (!bool(__binary_pred(*__dest, *__first)))
01235       *++__dest = _GLIBCXX_MOVE(*__first);
01236       return ++__dest;
01237     }
01238 
01239   /**
01240    *  This is an uglified unique_copy(_InputIterator, _InputIterator,
01241    *                                  _OutputIterator)
01242    *  overloaded for forward iterators and output iterator as result.
01243   */
01244   template<typename _ForwardIterator, typename _OutputIterator>
01245     _OutputIterator
01246     __unique_copy(_ForwardIterator __first, _ForwardIterator __last,
01247           _OutputIterator __result,
01248           forward_iterator_tag, output_iterator_tag)
01249     {
01250       // concept requirements -- taken care of in dispatching function
01251       _ForwardIterator __next = __first;
01252       *__result = *__first;
01253       while (++__next != __last)
01254     if (!(*__first == *__next))
01255       {
01256         __first = __next;
01257         *++__result = *__first;
01258       }
01259       return ++__result;
01260     }
01261 
01262   /**
01263    *  This is an uglified unique_copy(_InputIterator, _InputIterator,
01264    *                                  _OutputIterator)
01265    *  overloaded for input iterators and output iterator as result.
01266   */
01267   template<typename _InputIterator, typename _OutputIterator>
01268     _OutputIterator
01269     __unique_copy(_InputIterator __first, _InputIterator __last,
01270           _OutputIterator __result,
01271           input_iterator_tag, output_iterator_tag)
01272     {
01273       // concept requirements -- taken care of in dispatching function
01274       typename iterator_traits<_InputIterator>::value_type __value = *__first;
01275       *__result = __value;
01276       while (++__first != __last)
01277     if (!(__value == *__first))
01278       {
01279         __value = *__first;
01280         *++__result = __value;
01281       }
01282       return ++__result;
01283     }
01284 
01285   /**
01286    *  This is an uglified unique_copy(_InputIterator, _InputIterator,
01287    *                                  _OutputIterator)
01288    *  overloaded for input iterators and forward iterator as result.
01289   */
01290   template<typename _InputIterator, typename _ForwardIterator>
01291     _ForwardIterator
01292     __unique_copy(_InputIterator __first, _InputIterator __last,
01293           _ForwardIterator __result,
01294           input_iterator_tag, forward_iterator_tag)
01295     {
01296       // concept requirements -- taken care of in dispatching function
01297       *__result = *__first;
01298       while (++__first != __last)
01299     if (!(*__result == *__first))
01300       *++__result = *__first;
01301       return ++__result;
01302     }
01303 
01304   /**
01305    *  This is an uglified
01306    *  unique_copy(_InputIterator, _InputIterator, _OutputIterator,
01307    *              _BinaryPredicate)
01308    *  overloaded for forward iterators and output iterator as result.
01309   */
01310   template<typename _ForwardIterator, typename _OutputIterator,
01311        typename _BinaryPredicate>
01312     _OutputIterator
01313     __unique_copy(_ForwardIterator __first, _ForwardIterator __last,
01314           _OutputIterator __result, _BinaryPredicate __binary_pred,
01315           forward_iterator_tag, output_iterator_tag)
01316     {
01317       // concept requirements -- iterators already checked
01318       __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
01319       typename iterator_traits<_ForwardIterator>::value_type,
01320       typename iterator_traits<_ForwardIterator>::value_type>)
01321 
01322       _ForwardIterator __next = __first;
01323       *__result = *__first;
01324       while (++__next != __last)
01325     if (!bool(__binary_pred(*__first, *__next)))
01326       {
01327         __first = __next;
01328         *++__result = *__first;
01329       }
01330       return ++__result;
01331     }
01332 
01333   /**
01334    *  This is an uglified
01335    *  unique_copy(_InputIterator, _InputIterator, _OutputIterator,
01336    *              _BinaryPredicate)
01337    *  overloaded for input iterators and output iterator as result.
01338   */
01339   template<typename _InputIterator, typename _OutputIterator,
01340        typename _BinaryPredicate>
01341     _OutputIterator
01342     __unique_copy(_InputIterator __first, _InputIterator __last,
01343           _OutputIterator __result, _BinaryPredicate __binary_pred,
01344           input_iterator_tag, output_iterator_tag)
01345     {
01346       // concept requirements -- iterators already checked
01347       __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
01348       typename iterator_traits<_InputIterator>::value_type,
01349       typename iterator_traits<_InputIterator>::value_type>)
01350 
01351       typename iterator_traits<_InputIterator>::value_type __value = *__first;
01352       *__result = __value;
01353       while (++__first != __last)
01354     if (!bool(__binary_pred(__value, *__first)))
01355       {
01356         __value = *__first;
01357         *++__result = __value;
01358       }
01359       return ++__result;
01360     }
01361 
01362   /**
01363    *  This is an uglified
01364    *  unique_copy(_InputIterator, _InputIterator, _OutputIterator,
01365    *              _BinaryPredicate)
01366    *  overloaded for input iterators and forward iterator as result.
01367   */
01368   template<typename _InputIterator, typename _ForwardIterator,
01369        typename _BinaryPredicate>
01370     _ForwardIterator
01371     __unique_copy(_InputIterator __first, _InputIterator __last,
01372           _ForwardIterator __result, _BinaryPredicate __binary_pred,
01373           input_iterator_tag, forward_iterator_tag)
01374     {
01375       // concept requirements -- iterators already checked
01376       __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
01377       typename iterator_traits<_ForwardIterator>::value_type,
01378       typename iterator_traits<_InputIterator>::value_type>)
01379 
01380       *__result = *__first;
01381       while (++__first != __last)
01382     if (!bool(__binary_pred(*__result, *__first)))
01383       *++__result = *__first;
01384       return ++__result;
01385     }
01386 
01387   /**
01388    *  This is an uglified reverse(_BidirectionalIterator,
01389    *                              _BidirectionalIterator)
01390    *  overloaded for bidirectional iterators.
01391   */
01392   template<typename _BidirectionalIterator>
01393     void
01394     __reverse(_BidirectionalIterator __first, _BidirectionalIterator __last,
01395           bidirectional_iterator_tag)
01396     {
01397       while (true)
01398     if (__first == __last || __first == --__last)
01399       return;
01400     else
01401       {
01402         std::iter_swap(__first, __last);
01403         ++__first;
01404       }
01405     }
01406 
01407   /**
01408    *  This is an uglified reverse(_BidirectionalIterator,
01409    *                              _BidirectionalIterator)
01410    *  overloaded for random access iterators.
01411   */
01412   template<typename _RandomAccessIterator>
01413     void
01414     __reverse(_RandomAccessIterator __first, _RandomAccessIterator __last,
01415           random_access_iterator_tag)
01416     {
01417       if (__first == __last)
01418     return;
01419       --__last;
01420       while (__first < __last)
01421     {
01422       std::iter_swap(__first, __last);
01423       ++__first;
01424       --__last;
01425     }
01426     }
01427 
01428   /**
01429    *  @brief Reverse a sequence.
01430    *  @ingroup mutating_algorithms
01431    *  @param  __first  A bidirectional iterator.
01432    *  @param  __last   A bidirectional iterator.
01433    *  @return   reverse() returns no value.
01434    *
01435    *  Reverses the order of the elements in the range @p [__first,__last),
01436    *  so that the first element becomes the last etc.
01437    *  For every @c i such that @p 0<=i<=(__last-__first)/2), @p reverse()
01438    *  swaps @p *(__first+i) and @p *(__last-(i+1))
01439   */
01440   template<typename _BidirectionalIterator>
01441     inline void
01442     reverse(_BidirectionalIterator __first, _BidirectionalIterator __last)
01443     {
01444       // concept requirements
01445       __glibcxx_function_requires(_Mutable_BidirectionalIteratorConcept<
01446                   _BidirectionalIterator>)
01447       __glibcxx_requires_valid_range(__first, __last);
01448       std::__reverse(__first, __last, std::__iterator_category(__first));
01449     }
01450 
01451   /**
01452    *  @brief Copy a sequence, reversing its elements.
01453    *  @ingroup mutating_algorithms
01454    *  @param  __first   A bidirectional iterator.
01455    *  @param  __last    A bidirectional iterator.
01456    *  @param  __result  An output iterator.
01457    *  @return  An iterator designating the end of the resulting sequence.
01458    *
01459    *  Copies the elements in the range @p [__first,__last) to the
01460    *  range @p [__result,__result+(__last-__first)) such that the
01461    *  order of the elements is reversed.  For every @c i such that @p
01462    *  0<=i<=(__last-__first), @p reverse_copy() performs the
01463    *  assignment @p *(__result+(__last-__first)-1-i) = *(__first+i).
01464    *  The ranges @p [__first,__last) and @p
01465    *  [__result,__result+(__last-__first)) must not overlap.
01466   */
01467   template<typename _BidirectionalIterator, typename _OutputIterator>
01468     _OutputIterator
01469     reverse_copy(_BidirectionalIterator __first, _BidirectionalIterator __last,
01470          _OutputIterator __result)
01471     {
01472       // concept requirements
01473       __glibcxx_function_requires(_BidirectionalIteratorConcept<
01474                   _BidirectionalIterator>)
01475       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
01476         typename iterator_traits<_BidirectionalIterator>::value_type>)
01477       __glibcxx_requires_valid_range(__first, __last);
01478 
01479       while (__first != __last)
01480     {
01481       --__last;
01482       *__result = *__last;
01483       ++__result;
01484     }
01485       return __result;
01486     }
01487 
01488   /**
01489    *  This is a helper function for the rotate algorithm specialized on RAIs.
01490    *  It returns the greatest common divisor of two integer values.
01491   */
01492   template<typename _EuclideanRingElement>
01493     _EuclideanRingElement
01494     __gcd(_EuclideanRingElement __m, _EuclideanRingElement __n)
01495     {
01496       while (__n != 0)
01497     {
01498       _EuclideanRingElement __t = __m % __n;
01499       __m = __n;
01500       __n = __t;
01501     }
01502       return __m;
01503     }
01504 
01505   /// This is a helper function for the rotate algorithm.
01506   template<typename _ForwardIterator>
01507     void
01508     __rotate(_ForwardIterator __first,
01509          _ForwardIterator __middle,
01510          _ForwardIterator __last,
01511          forward_iterator_tag)
01512     {
01513       if (__first == __middle || __last  == __middle)
01514     return;
01515 
01516       _ForwardIterator __first2 = __middle;
01517       do
01518     {
01519       std::iter_swap(__first, __first2);
01520       ++__first;
01521       ++__first2;
01522       if (__first == __middle)
01523         __middle = __first2;
01524     }
01525       while (__first2 != __last);
01526 
01527       __first2 = __middle;
01528 
01529       while (__first2 != __last)
01530     {
01531       std::iter_swap(__first, __first2);
01532       ++__first;
01533       ++__first2;
01534       if (__first == __middle)
01535         __middle = __first2;
01536       else if (__first2 == __last)
01537         __first2 = __middle;
01538     }
01539     }
01540 
01541    /// This is a helper function for the rotate algorithm.
01542   template<typename _BidirectionalIterator>
01543     void
01544     __rotate(_BidirectionalIterator __first,
01545          _BidirectionalIterator __middle,
01546          _BidirectionalIterator __last,
01547           bidirectional_iterator_tag)
01548     {
01549       // concept requirements
01550       __glibcxx_function_requires(_Mutable_BidirectionalIteratorConcept<
01551                   _BidirectionalIterator>)
01552 
01553       if (__first == __middle || __last  == __middle)
01554     return;
01555 
01556       std::__reverse(__first,  __middle, bidirectional_iterator_tag());
01557       std::__reverse(__middle, __last,   bidirectional_iterator_tag());
01558 
01559       while (__first != __middle && __middle != __last)
01560     {
01561       std::iter_swap(__first, --__last);
01562       ++__first;
01563     }
01564 
01565       if (__first == __middle)
01566     std::__reverse(__middle, __last,   bidirectional_iterator_tag());
01567       else
01568     std::__reverse(__first,  __middle, bidirectional_iterator_tag());
01569     }
01570 
01571   /// This is a helper function for the rotate algorithm.
01572   template<typename _RandomAccessIterator>
01573     void
01574     __rotate(_RandomAccessIterator __first,
01575          _RandomAccessIterator __middle,
01576          _RandomAccessIterator __last,
01577          random_access_iterator_tag)
01578     {
01579       // concept requirements
01580       __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
01581                   _RandomAccessIterator>)
01582 
01583       if (__first == __middle || __last  == __middle)
01584     return;
01585 
01586       typedef typename iterator_traits<_RandomAccessIterator>::difference_type
01587     _Distance;
01588       typedef typename iterator_traits<_RandomAccessIterator>::value_type
01589     _ValueType;
01590 
01591       _Distance __n = __last   - __first;
01592       _Distance __k = __middle - __first;
01593 
01594       if (__k == __n - __k)
01595     {
01596       std::swap_ranges(__first, __middle, __middle);
01597       return;
01598     }
01599 
01600       _RandomAccessIterator __p = __first;
01601 
01602       for (;;)
01603     {
01604       if (__k < __n - __k)
01605         {
01606           if (__is_pod(_ValueType) && __k == 1)
01607         {
01608           _ValueType __t = _GLIBCXX_MOVE(*__p);
01609           _GLIBCXX_MOVE3(__p + 1, __p + __n, __p);
01610           *(__p + __n - 1) = _GLIBCXX_MOVE(__t);
01611           return;
01612         }
01613           _RandomAccessIterator __q = __p + __k;
01614           for (_Distance __i = 0; __i < __n - __k; ++ __i)
01615         {
01616           std::iter_swap(__p, __q);
01617           ++__p;
01618           ++__q;
01619         }
01620           __n %= __k;
01621           if (__n == 0)
01622         return;
01623           std::swap(__n, __k);
01624           __k = __n - __k;
01625         }
01626       else
01627         {
01628           __k = __n - __k;
01629           if (__is_pod(_ValueType) && __k == 1)
01630         {
01631           _ValueType __t = _GLIBCXX_MOVE(*(__p + __n - 1));
01632           _GLIBCXX_MOVE_BACKWARD3(__p, __p + __n - 1, __p + __n);
01633           *__p = _GLIBCXX_MOVE(__t);
01634           return;
01635         }
01636           _RandomAccessIterator __q = __p + __n;
01637           __p = __q - __k;
01638           for (_Distance __i = 0; __i < __n - __k; ++ __i)
01639         {
01640           --__p;
01641           --__q;
01642           std::iter_swap(__p, __q);
01643         }
01644           __n %= __k;
01645           if (__n == 0)
01646         return;
01647           std::swap(__n, __k);
01648         }
01649     }
01650     }
01651 
01652   /**
01653    *  @brief Rotate the elements of a sequence.
01654    *  @ingroup mutating_algorithms
01655    *  @param  __first   A forward iterator.
01656    *  @param  __middle  A forward iterator.
01657    *  @param  __last    A forward iterator.
01658    *  @return  Nothing.
01659    *
01660    *  Rotates the elements of the range @p [__first,__last) by 
01661    *  @p (__middle - __first) positions so that the element at @p __middle
01662    *  is moved to @p __first, the element at @p __middle+1 is moved to
01663    *  @p __first+1 and so on for each element in the range
01664    *  @p [__first,__last).
01665    *
01666    *  This effectively swaps the ranges @p [__first,__middle) and
01667    *  @p [__middle,__last).
01668    *
01669    *  Performs
01670    *   @p *(__first+(n+(__last-__middle))%(__last-__first))=*(__first+n)
01671    *  for each @p n in the range @p [0,__last-__first).
01672   */
01673   template<typename _ForwardIterator>
01674     inline void
01675     rotate(_ForwardIterator __first, _ForwardIterator __middle,
01676        _ForwardIterator __last)
01677     {
01678       // concept requirements
01679       __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
01680                   _ForwardIterator>)
01681       __glibcxx_requires_valid_range(__first, __middle);
01682       __glibcxx_requires_valid_range(__middle, __last);
01683 
01684       typedef typename iterator_traits<_ForwardIterator>::iterator_category
01685     _IterType;
01686       std::__rotate(__first, __middle, __last, _IterType());
01687     }
01688 
01689   /**
01690    *  @brief Copy a sequence, rotating its elements.
01691    *  @ingroup mutating_algorithms
01692    *  @param  __first   A forward iterator.
01693    *  @param  __middle  A forward iterator.
01694    *  @param  __last    A forward iterator.
01695    *  @param  __result  An output iterator.
01696    *  @return   An iterator designating the end of the resulting sequence.
01697    *
01698    *  Copies the elements of the range @p [__first,__last) to the
01699    *  range beginning at @result, rotating the copied elements by 
01700    *  @p (__middle-__first) positions so that the element at @p __middle
01701    *  is moved to @p __result, the element at @p __middle+1 is moved
01702    *  to @p __result+1 and so on for each element in the range @p
01703    *  [__first,__last).
01704    *
01705    *  Performs 
01706    *  @p *(__result+(n+(__last-__middle))%(__last-__first))=*(__first+n)
01707    *  for each @p n in the range @p [0,__last-__first).
01708   */
01709   template<typename _ForwardIterator, typename _OutputIterator>
01710     _OutputIterator
01711     rotate_copy(_ForwardIterator __first, _ForwardIterator __middle,
01712                 _ForwardIterator __last, _OutputIterator __result)
01713     {
01714       // concept requirements
01715       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
01716       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
01717         typename iterator_traits<_ForwardIterator>::value_type>)
01718       __glibcxx_requires_valid_range(__first, __middle);
01719       __glibcxx_requires_valid_range(__middle, __last);
01720 
01721       return std::copy(__first, __middle,
01722                        std::copy(__middle, __last, __result));
01723     }
01724 
01725   /// This is a helper function...
01726   template<typename _ForwardIterator, typename _Predicate>
01727     _ForwardIterator
01728     __partition(_ForwardIterator __first, _ForwardIterator __last,
01729         _Predicate __pred, forward_iterator_tag)
01730     {
01731       if (__first == __last)
01732     return __first;
01733 
01734       while (__pred(*__first))
01735     if (++__first == __last)
01736       return __first;
01737 
01738       _ForwardIterator __next = __first;
01739 
01740       while (++__next != __last)
01741     if (__pred(*__next))
01742       {
01743         std::iter_swap(__first, __next);
01744         ++__first;
01745       }
01746 
01747       return __first;
01748     }
01749 
01750   /// This is a helper function...
01751   template<typename _BidirectionalIterator, typename _Predicate>
01752     _BidirectionalIterator
01753     __partition(_BidirectionalIterator __first, _BidirectionalIterator __last,
01754         _Predicate __pred, bidirectional_iterator_tag)
01755     {
01756       while (true)
01757     {
01758       while (true)
01759         if (__first == __last)
01760           return __first;
01761         else if (__pred(*__first))
01762           ++__first;
01763         else
01764           break;
01765       --__last;
01766       while (true)
01767         if (__first == __last)
01768           return __first;
01769         else if (!bool(__pred(*__last)))
01770           --__last;
01771         else
01772           break;
01773       std::iter_swap(__first, __last);
01774       ++__first;
01775     }
01776     }
01777 
01778   // partition
01779 
01780   /// This is a helper function...
01781   /// Requires __len != 0 and !__pred(*__first),
01782   /// same as __stable_partition_adaptive.
01783   template<typename _ForwardIterator, typename _Predicate, typename _Distance>
01784     _ForwardIterator
01785     __inplace_stable_partition(_ForwardIterator __first,
01786                    _Predicate __pred, _Distance __len)
01787     {
01788       if (__len == 1)
01789     return __first;
01790       _ForwardIterator __middle = __first;
01791       std::advance(__middle, __len / 2);
01792       _ForwardIterator __left_split =
01793     std::__inplace_stable_partition(__first, __pred, __len / 2);
01794       // Advance past true-predicate values to satisfy this
01795       // function's preconditions.
01796       _Distance __right_len = __len - __len / 2;
01797       _ForwardIterator __right_split =
01798     std::__find_if_not_n(__middle, __right_len, __pred);
01799       if (__right_len)
01800     __right_split = std::__inplace_stable_partition(__middle,
01801                             __pred,
01802                             __right_len);
01803       std::rotate(__left_split, __middle, __right_split);
01804       std::advance(__left_split, std::distance(__middle, __right_split));
01805       return __left_split;
01806     }
01807 
01808   /// This is a helper function...
01809   /// Requires __first != __last and !__pred(*__first)
01810   /// and __len == distance(__first, __last).
01811   ///
01812   /// !__pred(*__first) allows us to guarantee that we don't
01813   /// move-assign an element onto itself.
01814   template<typename _ForwardIterator, typename _Pointer, typename _Predicate,
01815        typename _Distance>
01816     _ForwardIterator
01817     __stable_partition_adaptive(_ForwardIterator __first,
01818                 _ForwardIterator __last,
01819                 _Predicate __pred, _Distance __len,
01820                 _Pointer __buffer,
01821                 _Distance __buffer_size)
01822     {
01823       if (__len <= __buffer_size)
01824     {
01825       _ForwardIterator __result1 = __first;
01826       _Pointer __result2 = __buffer;
01827       // The precondition guarantees that !__pred(*__first), so
01828       // move that element to the buffer before starting the loop.
01829       // This ensures that we only call __pred once per element.
01830       *__result2 = _GLIBCXX_MOVE(*__first);
01831       ++__result2;
01832       ++__first;
01833       for (; __first != __last; ++__first)
01834         if (__pred(*__first))
01835           {
01836         *__result1 = _GLIBCXX_MOVE(*__first);
01837         ++__result1;
01838           }
01839         else
01840           {
01841         *__result2 = _GLIBCXX_MOVE(*__first);
01842         ++__result2;
01843           }
01844       _GLIBCXX_MOVE3(__buffer, __result2, __result1);
01845       return __result1;
01846     }
01847       else
01848     {
01849       _ForwardIterator __middle = __first;
01850       std::advance(__middle, __len / 2);
01851       _ForwardIterator __left_split =
01852         std::__stable_partition_adaptive(__first, __middle, __pred,
01853                          __len / 2, __buffer,
01854                          __buffer_size);
01855       // Advance past true-predicate values to satisfy this
01856       // function's preconditions.
01857       _Distance __right_len = __len - __len / 2;
01858       _ForwardIterator __right_split =
01859         std::__find_if_not_n(__middle, __right_len, __pred);
01860       if (__right_len)
01861         __right_split =
01862           std::__stable_partition_adaptive(__right_split, __last, __pred,
01863                            __right_len,
01864                            __buffer, __buffer_size);
01865       std::rotate(__left_split, __middle, __right_split);
01866       std::advance(__left_split, std::distance(__middle, __right_split));
01867       return __left_split;
01868     }
01869     }
01870 
01871   /**
01872    *  @brief Move elements for which a predicate is true to the beginning
01873    *         of a sequence, preserving relative ordering.
01874    *  @ingroup mutating_algorithms
01875    *  @param  __first   A forward iterator.
01876    *  @param  __last    A forward iterator.
01877    *  @param  __pred    A predicate functor.
01878    *  @return  An iterator @p middle such that @p __pred(i) is true for each
01879    *  iterator @p i in the range @p [first,middle) and false for each @p i
01880    *  in the range @p [middle,last).
01881    *
01882    *  Performs the same function as @p partition() with the additional
01883    *  guarantee that the relative ordering of elements in each group is
01884    *  preserved, so any two elements @p x and @p y in the range
01885    *  @p [__first,__last) such that @p __pred(x)==__pred(y) will have the same
01886    *  relative ordering after calling @p stable_partition().
01887   */
01888   template<typename _ForwardIterator, typename _Predicate>
01889     _ForwardIterator
01890     stable_partition(_ForwardIterator __first, _ForwardIterator __last,
01891              _Predicate __pred)
01892     {
01893       // concept requirements
01894       __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
01895                   _ForwardIterator>)
01896       __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
01897         typename iterator_traits<_ForwardIterator>::value_type>)
01898       __glibcxx_requires_valid_range(__first, __last);
01899 
01900       __first = std::__find_if_not(__first, __last, __pred);
01901 
01902       if (__first == __last)
01903     return __first;
01904       else
01905     {
01906       typedef typename iterator_traits<_ForwardIterator>::value_type
01907         _ValueType;
01908       typedef typename iterator_traits<_ForwardIterator>::difference_type
01909         _DistanceType;
01910 
01911       _Temporary_buffer<_ForwardIterator, _ValueType> __buf(__first,
01912                                 __last);
01913     if (__buf.size() > 0)
01914       return
01915         std::__stable_partition_adaptive(__first, __last, __pred,
01916                       _DistanceType(__buf.requested_size()),
01917                       __buf.begin(),
01918                       _DistanceType(__buf.size()));
01919     else
01920       return
01921         std::__inplace_stable_partition(__first, __pred,
01922                      _DistanceType(__buf.requested_size()));
01923     }
01924     }
01925 
01926   /// This is a helper function for the sort routines.
01927   template<typename _RandomAccessIterator>
01928     void
01929     __heap_select(_RandomAccessIterator __first,
01930           _RandomAccessIterator __middle,
01931           _RandomAccessIterator __last)
01932     {
01933       std::make_heap(__first, __middle);
01934       for (_RandomAccessIterator __i = __middle; __i < __last; ++__i)
01935     if (*__i < *__first)
01936       std::__pop_heap(__first, __middle, __i);
01937     }
01938 
01939   /// This is a helper function for the sort routines.
01940   template<typename _RandomAccessIterator, typename _Compare>
01941     void
01942     __heap_select(_RandomAccessIterator __first,
01943           _RandomAccessIterator __middle,
01944           _RandomAccessIterator __last, _Compare __comp)
01945     {
01946       std::make_heap(__first, __middle, __comp);
01947       for (_RandomAccessIterator __i = __middle; __i < __last; ++__i)
01948     if (__comp(*__i, *__first))
01949       std::__pop_heap(__first, __middle, __i, __comp);
01950     }
01951 
01952   // partial_sort
01953 
01954   /**
01955    *  @brief Copy the smallest elements of a sequence.
01956    *  @ingroup sorting_algorithms
01957    *  @param  __first   An iterator.
01958    *  @param  __last    Another iterator.
01959    *  @param  __result_first   A random-access iterator.
01960    *  @param  __result_last    Another random-access iterator.
01961    *  @return   An iterator indicating the end of the resulting sequence.
01962    *
01963    *  Copies and sorts the smallest N values from the range @p [__first,__last)
01964    *  to the range beginning at @p __result_first, where the number of
01965    *  elements to be copied, @p N, is the smaller of @p (__last-__first) and
01966    *  @p (__result_last-__result_first).
01967    *  After the sort if @e i and @e j are iterators in the range
01968    *  @p [__result_first,__result_first+N) such that i precedes j then
01969    *  *j<*i is false.
01970    *  The value returned is @p __result_first+N.
01971   */
01972   template<typename _InputIterator, typename _RandomAccessIterator>
01973     _RandomAccessIterator
01974     partial_sort_copy(_InputIterator __first, _InputIterator __last,
01975               _RandomAccessIterator __result_first,
01976               _RandomAccessIterator __result_last)
01977     {
01978       typedef typename iterator_traits<_InputIterator>::value_type
01979     _InputValueType;
01980       typedef typename iterator_traits<_RandomAccessIterator>::value_type
01981     _OutputValueType;
01982       typedef typename iterator_traits<_RandomAccessIterator>::difference_type
01983     _DistanceType;
01984 
01985       // concept requirements
01986       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
01987       __glibcxx_function_requires(_ConvertibleConcept<_InputValueType,
01988                   _OutputValueType>)
01989       __glibcxx_function_requires(_LessThanOpConcept<_InputValueType,
01990                                      _OutputValueType>)
01991       __glibcxx_function_requires(_LessThanComparableConcept<_OutputValueType>)
01992       __glibcxx_requires_valid_range(__first, __last);
01993       __glibcxx_requires_valid_range(__result_first, __result_last);
01994 
01995       if (__result_first == __result_last)
01996     return __result_last;
01997       _RandomAccessIterator __result_real_last = __result_first;
01998       while(__first != __last && __result_real_last != __result_last)
01999     {
02000       *__result_real_last = *__first;
02001       ++__result_real_last;
02002       ++__first;
02003     }
02004       std::make_heap(__result_first, __result_real_last);
02005       while (__first != __last)
02006     {
02007       if (*__first < *__result_first)
02008         std::__adjust_heap(__result_first, _DistanceType(0),
02009                    _DistanceType(__result_real_last
02010                          - __result_first),
02011                    _InputValueType(*__first));
02012       ++__first;
02013     }
02014       std::sort_heap(__result_first, __result_real_last);
02015       return __result_real_last;
02016     }
02017 
02018   /**
02019    *  @brief Copy the smallest elements of a sequence using a predicate for
02020    *         comparison.
02021    *  @ingroup sorting_algorithms
02022    *  @param  __first   An input iterator.
02023    *  @param  __last    Another input iterator.
02024    *  @param  __result_first   A random-access iterator.
02025    *  @param  __result_last    Another random-access iterator.
02026    *  @param  __comp    A comparison functor.
02027    *  @return   An iterator indicating the end of the resulting sequence.
02028    *
02029    *  Copies and sorts the smallest N values from the range @p [__first,__last)
02030    *  to the range beginning at @p result_first, where the number of
02031    *  elements to be copied, @p N, is the smaller of @p (__last-__first) and
02032    *  @p (__result_last-__result_first).
02033    *  After the sort if @e i and @e j are iterators in the range
02034    *  @p [__result_first,__result_first+N) such that i precedes j then
02035    *  @p __comp(*j,*i) is false.
02036    *  The value returned is @p __result_first+N.
02037   */
02038   template<typename _InputIterator, typename _RandomAccessIterator, typename _Compare>
02039     _RandomAccessIterator
02040     partial_sort_copy(_InputIterator __first, _InputIterator __last,
02041               _RandomAccessIterator __result_first,
02042               _RandomAccessIterator __result_last,
02043               _Compare __comp)
02044     {
02045       typedef typename iterator_traits<_InputIterator>::value_type
02046     _InputValueType;
02047       typedef typename iterator_traits<_RandomAccessIterator>::value_type
02048     _OutputValueType;
02049       typedef typename iterator_traits<_RandomAccessIterator>::difference_type
02050     _DistanceType;
02051 
02052       // concept requirements
02053       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
02054       __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
02055                   _RandomAccessIterator>)
02056       __glibcxx_function_requires(_ConvertibleConcept<_InputValueType,
02057                   _OutputValueType>)
02058       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
02059                   _InputValueType, _OutputValueType>)
02060       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
02061                   _OutputValueType, _OutputValueType>)
02062       __glibcxx_requires_valid_range(__first, __last);
02063       __glibcxx_requires_valid_range(__result_first, __result_last);
02064 
02065       if (__result_first == __result_last)
02066     return __result_last;
02067       _RandomAccessIterator __result_real_last = __result_first;
02068       while(__first != __last && __result_real_last != __result_last)
02069     {
02070       *__result_real_last = *__first;
02071       ++__result_real_last;
02072       ++__first;
02073     }
02074       std::make_heap(__result_first, __result_real_last, __comp);
02075       while (__first != __last)
02076     {
02077       if (__comp(*__first, *__result_first))
02078         std::__adjust_heap(__result_first, _DistanceType(0),
02079                    _DistanceType(__result_real_last
02080                          - __result_first),
02081                    _InputValueType(*__first),
02082                    __comp);
02083       ++__first;
02084     }
02085       std::sort_heap(__result_first, __result_real_last, __comp);
02086       return __result_real_last;
02087     }
02088 
02089   /// This is a helper function for the sort routine.
02090   template<typename _RandomAccessIterator>
02091     void
02092     __unguarded_linear_insert(_RandomAccessIterator __last)
02093     {
02094       typename iterator_traits<_RandomAccessIterator>::value_type
02095     __val = _GLIBCXX_MOVE(*__last);
02096       _RandomAccessIterator __next = __last;
02097       --__next;
02098       while (__val < *__next)
02099     {
02100       *__last = _GLIBCXX_MOVE(*__next);
02101       __last = __next;
02102       --__next;
02103     }
02104       *__last = _GLIBCXX_MOVE(__val);
02105     }
02106 
02107   /// This is a helper function for the sort routine.
02108   template<typename _RandomAccessIterator, typename _Compare>
02109     void
02110     __unguarded_linear_insert(_RandomAccessIterator __last,
02111                   _Compare __comp)
02112     {
02113       typename iterator_traits<_RandomAccessIterator>::value_type
02114     __val = _GLIBCXX_MOVE(*__last);
02115       _RandomAccessIterator __next = __last;
02116       --__next;
02117       while (__comp(__val, *__next))
02118     {
02119       *__last = _GLIBCXX_MOVE(*__next);
02120       __last = __next;
02121       --__next;
02122     }
02123       *__last = _GLIBCXX_MOVE(__val);
02124     }
02125 
02126   /// This is a helper function for the sort routine.
02127   template<typename _RandomAccessIterator>
02128     void
02129     __insertion_sort(_RandomAccessIterator __first,
02130              _RandomAccessIterator __last)
02131     {
02132       if (__first == __last)
02133     return;
02134 
02135       for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i)
02136     {
02137       if (*__i < *__first)
02138         {
02139           typename iterator_traits<_RandomAccessIterator>::value_type
02140         __val = _GLIBCXX_MOVE(*__i);
02141           _GLIBCXX_MOVE_BACKWARD3(__first, __i, __i + 1);
02142           *__first = _GLIBCXX_MOVE(__val);
02143         }
02144       else
02145         std::__unguarded_linear_insert(__i);
02146     }
02147     }
02148 
02149   /// This is a helper function for the sort routine.
02150   template<typename _RandomAccessIterator, typename _Compare>
02151     void
02152     __insertion_sort(_RandomAccessIterator __first,
02153              _RandomAccessIterator __last, _Compare __comp)
02154     {
02155       if (__first == __last) return;
02156 
02157       for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i)
02158     {
02159       if (__comp(*__i, *__first))
02160         {
02161           typename iterator_traits<_RandomAccessIterator>::value_type
02162         __val = _GLIBCXX_MOVE(*__i);
02163           _GLIBCXX_MOVE_BACKWARD3(__first, __i, __i + 1);
02164           *__first = _GLIBCXX_MOVE(__val);
02165         }
02166       else
02167         std::__unguarded_linear_insert(__i, __comp);
02168     }
02169     }
02170 
02171   /// This is a helper function for the sort routine.
02172   template<typename _RandomAccessIterator>
02173     inline void
02174     __unguarded_insertion_sort(_RandomAccessIterator __first,
02175                    _RandomAccessIterator __last)
02176     {
02177       typedef typename iterator_traits<_RandomAccessIterator>::value_type
02178     _ValueType;
02179 
02180       for (_RandomAccessIterator __i = __first; __i != __last; ++__i)
02181     std::__unguarded_linear_insert(__i);
02182     }
02183 
02184   /// This is a helper function for the sort routine.
02185   template<typename _RandomAccessIterator, typename _Compare>
02186     inline void
02187     __unguarded_insertion_sort(_RandomAccessIterator __first,
02188                    _RandomAccessIterator __last, _Compare __comp)
02189     {
02190       typedef typename iterator_traits<_RandomAccessIterator>::value_type
02191     _ValueType;
02192 
02193       for (_RandomAccessIterator __i = __first; __i != __last; ++__i)
02194     std::__unguarded_linear_insert(__i, __comp);
02195     }
02196 
02197   /**
02198    *  @doctodo
02199    *  This controls some aspect of the sort routines.
02200   */
02201   enum { _S_threshold = 16 };
02202 
02203   /// This is a helper function for the sort routine.
02204   template<typename _RandomAccessIterator>
02205     void
02206     __final_insertion_sort(_RandomAccessIterator __first,
02207                _RandomAccessIterator __last)
02208     {
02209       if (__last - __first > int(_S_threshold))
02210     {
02211       std::__insertion_sort(__first, __first + int(_S_threshold));
02212       std::__unguarded_insertion_sort(__first + int(_S_threshold), __last);
02213     }
02214       else
02215     std::__insertion_sort(__first, __last);
02216     }
02217 
02218   /// This is a helper function for the sort routine.
02219   template<typename _RandomAccessIterator, typename _Compare>
02220     void
02221     __final_insertion_sort(_RandomAccessIterator __first,
02222                _RandomAccessIterator __last, _Compare __comp)
02223     {
02224       if (__last - __first > int(_S_threshold))
02225     {
02226       std::__insertion_sort(__first, __first + int(_S_threshold), __comp);
02227       std::__unguarded_insertion_sort(__first + int(_S_threshold), __last,
02228                       __comp);
02229     }
02230       else
02231     std::__insertion_sort(__first, __last, __comp);
02232     }
02233 
02234   /// This is a helper function...
02235   template<typename _RandomAccessIterator, typename _Tp>
02236     _RandomAccessIterator
02237     __unguarded_partition(_RandomAccessIterator __first,
02238               _RandomAccessIterator __last, const _Tp& __pivot)
02239     {
02240       while (true)
02241     {
02242       while (*__first < __pivot)
02243         ++__first;
02244       --__last;
02245       while (__pivot < *__last)
02246         --__last;
02247       if (!(__first < __last))
02248         return __first;
02249       std::iter_swap(__first, __last);
02250       ++__first;
02251     }
02252     }
02253 
02254   /// This is a helper function...
02255   template<typename _RandomAccessIterator, typename _Tp, typename _Compare>
02256     _RandomAccessIterator
02257     __unguarded_partition(_RandomAccessIterator __first,
02258               _RandomAccessIterator __last,
02259               const _Tp& __pivot, _Compare __comp)
02260     {
02261       while (true)
02262     {
02263       while (__comp(*__first, __pivot))
02264         ++__first;
02265       --__last;
02266       while (__comp(__pivot, *__last))
02267         --__last;
02268       if (!(__first < __last))
02269         return __first;
02270       std::iter_swap(__first, __last);
02271       ++__first;
02272     }
02273     }
02274 
02275   /// This is a helper function...
02276   template<typename _RandomAccessIterator>
02277     inline _RandomAccessIterator
02278     __unguarded_partition_pivot(_RandomAccessIterator __first,
02279                 _RandomAccessIterator __last)
02280     {
02281       _RandomAccessIterator __mid = __first + (__last - __first) / 2;
02282       std::__move_median_to_first(__first, __first + 1, __mid, __last - 1);
02283       return std::__unguarded_partition(__first + 1, __last, *__first);
02284     }
02285 
02286 
02287   /// This is a helper function...
02288   template<typename _RandomAccessIterator, typename _Compare>
02289     inline _RandomAccessIterator
02290     __unguarded_partition_pivot(_RandomAccessIterator __first,
02291                 _RandomAccessIterator __last, _Compare __comp)
02292     {
02293       _RandomAccessIterator __mid = __first + (__last - __first) / 2;
02294       std::__move_median_to_first(__first, __first + 1, __mid, __last - 1,
02295                   __comp);
02296       return std::__unguarded_partition(__first + 1, __last, *__first, __comp);
02297     }
02298 
02299   /// This is a helper function for the sort routine.
02300   template<typename _RandomAccessIterator, typename _Size>
02301     void
02302     __introsort_loop(_RandomAccessIterator __first,
02303              _RandomAccessIterator __last,
02304              _Size __depth_limit)
02305     {
02306       while (__last - __first > int(_S_threshold))
02307     {
02308       if (__depth_limit == 0)
02309         {
02310           _GLIBCXX_STD_A::partial_sort(__first, __last, __last);
02311           return;
02312         }
02313       --__depth_limit;
02314       _RandomAccessIterator __cut =
02315         std::__unguarded_partition_pivot(__first, __last);
02316       std::__introsort_loop(__cut, __last, __depth_limit);
02317       __last = __cut;
02318     }
02319     }
02320 
02321   /// This is a helper function for the sort routine.
02322   template<typename _RandomAccessIterator, typename _Size, typename _Compare>
02323     void
02324     __introsort_loop(_RandomAccessIterator __first,
02325              _RandomAccessIterator __last,
02326              _Size __depth_limit, _Compare __comp)
02327     {
02328       while (__last - __first > int(_S_threshold))
02329     {
02330       if (__depth_limit == 0)
02331         {
02332           _GLIBCXX_STD_A::partial_sort(__first, __last, __last, __comp);
02333           return;
02334         }
02335       --__depth_limit;
02336       _RandomAccessIterator __cut =
02337         std::__unguarded_partition_pivot(__first, __last, __comp);
02338       std::__introsort_loop(__cut, __last, __depth_limit, __comp);
02339       __last = __cut;
02340     }
02341     }
02342 
02343   // sort
02344 
02345   template<typename _RandomAccessIterator, typename _Size>
02346     void
02347     __introselect(_RandomAccessIterator __first, _RandomAccessIterator __nth,
02348           _RandomAccessIterator __last, _Size __depth_limit)
02349     {
02350       typedef typename iterator_traits<_RandomAccessIterator>::value_type
02351     _ValueType;
02352 
02353       while (__last - __first > 3)
02354     {
02355       if (__depth_limit == 0)
02356         {
02357           std::__heap_select(__first, __nth + 1, __last);
02358 
02359           // Place the nth largest element in its final position.
02360           std::iter_swap(__first, __nth);
02361           return;
02362         }
02363       --__depth_limit;
02364       _RandomAccessIterator __cut =
02365         std::__unguarded_partition_pivot(__first, __last);
02366       if (__cut <= __nth)
02367         __first = __cut;
02368       else
02369         __last = __cut;
02370     }
02371       std::__insertion_sort(__first, __last);
02372     }
02373 
02374   template<typename _RandomAccessIterator, typename _Size, typename _Compare>
02375     void
02376     __introselect(_RandomAccessIterator __first, _RandomAccessIterator __nth,
02377           _RandomAccessIterator __last, _Size __depth_limit,
02378           _Compare __comp)
02379     {
02380       typedef typename iterator_traits<_RandomAccessIterator>::value_type
02381     _ValueType;
02382 
02383       while (__last - __first > 3)
02384     {
02385       if (__depth_limit == 0)
02386         {
02387           std::__heap_select(__first, __nth + 1, __last, __comp);
02388           // Place the nth largest element in its final position.
02389           std::iter_swap(__first, __nth);
02390           return;
02391         }
02392       --__depth_limit;
02393       _RandomAccessIterator __cut =
02394         std::__unguarded_partition_pivot(__first, __last, __comp);
02395       if (__cut <= __nth)
02396         __first = __cut;
02397       else
02398         __last = __cut;
02399     }
02400       std::__insertion_sort(__first, __last, __comp);
02401     }
02402 
02403   // nth_element
02404 
02405   // lower_bound moved to stl_algobase.h
02406 
02407   /**
02408    *  @brief Finds the first position in which @p __val could be inserted
02409    *         without changing the ordering.
02410    *  @ingroup binary_search_algorithms
02411    *  @param  __first   An iterator.
02412    *  @param  __last    Another iterator.
02413    *  @param  __val     The search term.
02414    *  @param  __comp    A functor to use for comparisons.
02415    *  @return An iterator pointing to the first element <em>not less
02416    *           than</em> @p __val, or end() if every element is less
02417    *           than @p __val.
02418    *  @ingroup binary_search_algorithms
02419    *
02420    *  The comparison function should have the same effects on ordering as
02421    *  the function used for the initial sort.
02422   */
02423   template<typename _ForwardIterator, typename _Tp, typename _Compare>
02424     _ForwardIterator
02425     lower_bound(_ForwardIterator __first, _ForwardIterator __last,
02426         const _Tp& __val, _Compare __comp)
02427     {
02428       typedef typename iterator_traits<_ForwardIterator>::value_type
02429     _ValueType;
02430       typedef typename iterator_traits<_ForwardIterator>::difference_type
02431     _DistanceType;
02432 
02433       // concept requirements
02434       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
02435       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
02436                   _ValueType, _Tp>)
02437       __glibcxx_requires_partitioned_lower_pred(__first, __last,
02438                         __val, __comp);
02439 
02440       _DistanceType __len = std::distance(__first, __last);
02441 
02442       while (__len > 0)
02443     {
02444       _DistanceType __half = __len >> 1;
02445       _ForwardIterator __middle = __first;
02446       std::advance(__middle, __half);
02447       if (__comp(*__middle, __val))
02448         {
02449           __first = __middle;
02450           ++__first;
02451           __len = __len - __half - 1;
02452         }
02453       else
02454         __len = __half;
02455     }
02456       return __first;
02457     }
02458 
02459   /**
02460    *  @brief Finds the last position in which @p __val could be inserted
02461    *         without changing the ordering.
02462    *  @ingroup binary_search_algorithms
02463    *  @param  __first   An iterator.
02464    *  @param  __last    Another iterator.
02465    *  @param  __val     The search term.
02466    *  @return  An iterator pointing to the first element greater than @p __val,
02467    *           or end() if no elements are greater than @p __val.
02468    *  @ingroup binary_search_algorithms
02469   */
02470   template<typename _ForwardIterator, typename _Tp>
02471     _ForwardIterator
02472     upper_bound(_ForwardIterator __first, _ForwardIterator __last,
02473         const _Tp& __val)
02474     {
02475       typedef typename iterator_traits<_ForwardIterator>::value_type
02476     _ValueType;
02477       typedef typename iterator_traits<_ForwardIterator>::difference_type
02478     _DistanceType;
02479 
02480       // concept requirements
02481       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
02482       __glibcxx_function_requires(_LessThanOpConcept<_Tp, _ValueType>)
02483       __glibcxx_requires_partitioned_upper(__first, __last, __val);
02484 
02485       _DistanceType __len = std::distance(__first, __last);
02486 
02487       while (__len > 0)
02488     {
02489       _DistanceType __half = __len >> 1;
02490       _ForwardIterator __middle = __first;
02491       std::advance(__middle, __half);
02492       if (__val < *__middle)
02493         __len = __half;
02494       else
02495         {
02496           __first = __middle;
02497           ++__first;
02498           __len = __len - __half - 1;
02499         }
02500     }
02501       return __first;
02502     }
02503 
02504   /**
02505    *  @brief Finds the last position in which @p __val could be inserted
02506    *         without changing the ordering.
02507    *  @ingroup binary_search_algorithms
02508    *  @param  __first   An iterator.
02509    *  @param  __last    Another iterator.
02510    *  @param  __val     The search term.
02511    *  @param  __comp    A functor to use for comparisons.
02512    *  @return  An iterator pointing to the first element greater than @p __val,
02513    *           or end() if no elements are greater than @p __val.
02514    *  @ingroup binary_search_algorithms
02515    *
02516    *  The comparison function should have the same effects on ordering as
02517    *  the function used for the initial sort.
02518   */
02519   template<typename _ForwardIterator, typename _Tp, typename _Compare>
02520     _ForwardIterator
02521     upper_bound(_ForwardIterator __first, _ForwardIterator __last,
02522         const _Tp& __val, _Compare __comp)
02523     {
02524       typedef typename iterator_traits<_ForwardIterator>::value_type
02525     _ValueType;
02526       typedef typename iterator_traits<_ForwardIterator>::difference_type
02527     _DistanceType;
02528 
02529       // concept requirements
02530       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
02531       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
02532                   _Tp, _ValueType>)
02533       __glibcxx_requires_partitioned_upper_pred(__first, __last,
02534                         __val, __comp);
02535 
02536       _DistanceType __len = std::distance(__first, __last);
02537 
02538       while (__len > 0)
02539     {
02540       _DistanceType __half = __len >> 1;
02541       _ForwardIterator __middle = __first;
02542       std::advance(__middle, __half);
02543       if (__comp(__val, *__middle))
02544         __len = __half;
02545       else
02546         {
02547           __first = __middle;
02548           ++__first;
02549           __len = __len - __half - 1;
02550         }
02551     }
02552       return __first;
02553     }
02554 
02555   /**
02556    *  @brief Finds the largest subrange in which @p __val could be inserted
02557    *         at any place in it without changing the ordering.
02558    *  @ingroup binary_search_algorithms
02559    *  @param  __first   An iterator.
02560    *  @param  __last    Another iterator.
02561    *  @param  __val     The search term.
02562    *  @return  An pair of iterators defining the subrange.
02563    *  @ingroup binary_search_algorithms
02564    *
02565    *  This is equivalent to
02566    *  @code
02567    *    std::make_pair(lower_bound(__first, __last, __val),
02568    *                   upper_bound(__first, __last, __val))
02569    *  @endcode
02570    *  but does not actually call those functions.
02571   */
02572   template<typename _ForwardIterator, typename _Tp>
02573     pair<_ForwardIterator, _ForwardIterator>
02574     equal_range(_ForwardIterator __first, _ForwardIterator __last,
02575         const _Tp& __val)
02576     {
02577       typedef typename iterator_traits<_ForwardIterator>::value_type
02578     _ValueType;
02579       typedef typename iterator_traits<_ForwardIterator>::difference_type
02580     _DistanceType;
02581 
02582       // concept requirements
02583       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
02584       __glibcxx_function_requires(_LessThanOpConcept<_ValueType, _Tp>)
02585       __glibcxx_function_requires(_LessThanOpConcept<_Tp, _ValueType>)  
02586       __glibcxx_requires_partitioned_lower(__first, __last, __val);
02587       __glibcxx_requires_partitioned_upper(__first, __last, __val);      
02588 
02589       _DistanceType __len = std::distance(__first, __last);
02590  
02591       while (__len > 0)
02592     {
02593       _DistanceType __half = __len >> 1;
02594       _ForwardIterator __middle = __first;
02595       std::advance(__middle, __half);
02596       if (*__middle < __val)
02597         {
02598           __first = __middle;
02599           ++__first;
02600           __len = __len - __half - 1;
02601         }
02602       else if (__val < *__middle)
02603         __len = __half;
02604       else
02605         {
02606           _ForwardIterator __left = std::lower_bound(__first, __middle,
02607                              __val);
02608           std::advance(__first, __len);
02609           _ForwardIterator __right = std::upper_bound(++__middle, __first,
02610                               __val);
02611           return pair<_ForwardIterator, _ForwardIterator>(__left, __right);
02612         }
02613     }
02614       return pair<_ForwardIterator, _ForwardIterator>(__first, __first);
02615     }
02616 
02617   /**
02618    *  @brief Finds the largest subrange in which @p __val could be inserted
02619    *         at any place in it without changing the ordering.
02620    *  @param  __first   An iterator.
02621    *  @param  __last    Another iterator.
02622    *  @param  __val     The search term.
02623    *  @param  __comp    A functor to use for comparisons.
02624    *  @return  An pair of iterators defining the subrange.
02625    *  @ingroup binary_search_algorithms
02626    *
02627    *  This is equivalent to
02628    *  @code
02629    *    std::make_pair(lower_bound(__first, __last, __val, __comp),
02630    *                   upper_bound(__first, __last, __val, __comp))
02631    *  @endcode
02632    *  but does not actually call those functions.
02633   */
02634   template<typename _ForwardIterator, typename _Tp, typename _Compare>
02635     pair<_ForwardIterator, _ForwardIterator>
02636     equal_range(_ForwardIterator __first, _ForwardIterator __last,
02637         const _Tp& __val, _Compare __comp)
02638     {
02639       typedef typename iterator_traits<_ForwardIterator>::value_type
02640     _ValueType;
02641       typedef typename iterator_traits<_ForwardIterator>::difference_type
02642     _DistanceType;
02643 
02644       // concept requirements
02645       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
02646       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
02647                   _ValueType, _Tp>)
02648       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
02649                   _Tp, _ValueType>)
02650       __glibcxx_requires_partitioned_lower_pred(__first, __last,
02651                         __val, __comp);
02652       __glibcxx_requires_partitioned_upper_pred(__first, __last,
02653                         __val, __comp);
02654 
02655       _DistanceType __len = std::distance(__first, __last);
02656 
02657       while (__len > 0)
02658     {
02659       _DistanceType __half = __len >> 1;
02660       _ForwardIterator __middle = __first;
02661       std::advance(__middle, __half);
02662       if (__comp(*__middle, __val))
02663         {
02664           __first = __middle;
02665           ++__first;
02666           __len = __len - __half - 1;
02667         }
02668       else if (__comp(__val, *__middle))
02669         __len = __half;
02670       else
02671         {
02672           _ForwardIterator __left = std::lower_bound(__first, __middle,
02673                              __val, __comp);
02674           std::advance(__first, __len);
02675           _ForwardIterator __right = std::upper_bound(++__middle, __first,
02676                               __val, __comp);
02677           return pair<_ForwardIterator, _ForwardIterator>(__left, __right);
02678         }
02679     }
02680       return pair<_ForwardIterator, _ForwardIterator>(__first, __first);
02681     }
02682 
02683   /**
02684    *  @brief Determines whether an element exists in a range.
02685    *  @ingroup binary_search_algorithms
02686    *  @param  __first   An iterator.
02687    *  @param  __last    Another iterator.
02688    *  @param  __val     The search term.
02689    *  @return True if @p __val (or its equivalent) is in [@p
02690    *  __first,@p __last ].
02691    *
02692    *  Note that this does not actually return an iterator to @p __val.  For
02693    *  that, use std::find or a container's specialized find member functions.
02694   */
02695   template<typename _ForwardIterator, typename _Tp>
02696     bool
02697     binary_search(_ForwardIterator __first, _ForwardIterator __last,
02698                   const _Tp& __val)
02699     {
02700       typedef typename iterator_traits<_ForwardIterator>::value_type
02701     _ValueType;
02702 
02703       // concept requirements
02704       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
02705       __glibcxx_function_requires(_LessThanOpConcept<_Tp, _ValueType>)
02706       __glibcxx_requires_partitioned_lower(__first, __last, __val);
02707       __glibcxx_requires_partitioned_upper(__first, __last, __val);
02708 
02709       _ForwardIterator __i = std::lower_bound(__first, __last, __val);
02710       return __i != __last && !(__val < *__i);
02711     }
02712 
02713   /**
02714    *  @brief Determines whether an element exists in a range.
02715    *  @ingroup binary_search_algorithms
02716    *  @param  __first   An iterator.
02717    *  @param  __last    Another iterator.
02718    *  @param  __val     The search term.
02719    *  @param  __comp    A functor to use for comparisons.
02720    *  @return  True if @p __val (or its equivalent) is in @p [__first,__last].
02721    *
02722    *  Note that this does not actually return an iterator to @p __val.  For
02723    *  that, use std::find or a container's specialized find member functions.
02724    *
02725    *  The comparison function should have the same effects on ordering as
02726    *  the function used for the initial sort.
02727   */
02728   template<typename _ForwardIterator, typename _Tp, typename _Compare>
02729     bool
02730     binary_search(_ForwardIterator __first, _ForwardIterator __last,
02731                   const _Tp& __val, _Compare __comp)
02732     {
02733       typedef typename iterator_traits<_ForwardIterator>::value_type
02734     _ValueType;
02735 
02736       // concept requirements
02737       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
02738       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
02739                   _Tp, _ValueType>)
02740       __glibcxx_requires_partitioned_lower_pred(__first, __last,
02741                         __val, __comp);
02742       __glibcxx_requires_partitioned_upper_pred(__first, __last,
02743                         __val, __comp);
02744 
02745       _ForwardIterator __i = std::lower_bound(__first, __last, __val, __comp);
02746       return __i != __last && !bool(__comp(__val, *__i));
02747     }
02748 
02749   // merge
02750 
02751   /// This is a helper function for the __merge_adaptive routines.
02752   template<typename _InputIterator1, typename _InputIterator2,
02753        typename _OutputIterator>
02754     void
02755     __move_merge_adaptive(_InputIterator1 __first1, _InputIterator1 __last1,
02756               _InputIterator2 __first2, _InputIterator2 __last2,
02757               _OutputIterator __result)
02758     {
02759       while (__first1 != __last1 && __first2 != __last2)
02760     {
02761       if (*__first2 < *__first1)
02762         {
02763           *__result = _GLIBCXX_MOVE(*__first2);
02764           ++__first2;
02765         }
02766       else
02767         {
02768           *__result = _GLIBCXX_MOVE(*__first1);
02769           ++__first1;
02770         }
02771       ++__result;
02772     }
02773       if (__first1 != __last1)
02774     _GLIBCXX_MOVE3(__first1, __last1, __result);
02775     }
02776 
02777   /// This is a helper function for the __merge_adaptive routines.
02778   template<typename _InputIterator1, typename _InputIterator2,
02779        typename _OutputIterator, typename _Compare>
02780     void
02781     __move_merge_adaptive(_InputIterator1 __first1, _InputIterator1 __last1,
02782               _InputIterator2 __first2, _InputIterator2 __last2,
02783               _OutputIterator __result, _Compare __comp)
02784     {
02785       while (__first1 != __last1 && __first2 != __last2)
02786     {
02787       if (__comp(*__first2, *__first1))
02788         {
02789           *__result = _GLIBCXX_MOVE(*__first2);
02790           ++__first2;
02791         }
02792       else
02793         {
02794           *__result = _GLIBCXX_MOVE(*__first1);
02795           ++__first1;
02796         }
02797       ++__result;
02798     }
02799       if (__first1 != __last1)
02800     _GLIBCXX_MOVE3(__first1, __last1, __result);
02801     }
02802 
02803   /// This is a helper function for the __merge_adaptive routines.
02804   template<typename _BidirectionalIterator1, typename _BidirectionalIterator2,
02805        typename _BidirectionalIterator3>
02806     void
02807     __move_merge_adaptive_backward(_BidirectionalIterator1 __first1,
02808                    _BidirectionalIterator1 __last1,
02809                    _BidirectionalIterator2 __first2,
02810                    _BidirectionalIterator2 __last2,
02811                    _BidirectionalIterator3 __result)
02812     {
02813       if (__first1 == __last1)
02814     {
02815       _GLIBCXX_MOVE_BACKWARD3(__first2, __last2, __result);
02816       return;
02817     }
02818       else if (__first2 == __last2)
02819     return;
02820 
02821       --__last1;
02822       --__last2;
02823       while (true)
02824     {
02825       if (*__last2 < *__last1)
02826         {
02827           *--__result = _GLIBCXX_MOVE(*__last1);
02828           if (__first1 == __last1)
02829         {
02830           _GLIBCXX_MOVE_BACKWARD3(__first2, ++__last2, __result);
02831           return;
02832         }
02833           --__last1;
02834         }
02835       else
02836         {
02837           *--__result = _GLIBCXX_MOVE(*__last2);
02838           if (__first2 == __last2)
02839         return;
02840           --__last2;
02841         }
02842     }
02843     }
02844 
02845   /// This is a helper function for the __merge_adaptive routines.
02846   template<typename _BidirectionalIterator1, typename _BidirectionalIterator2,
02847        typename _BidirectionalIterator3, typename _Compare>
02848     void
02849     __move_merge_adaptive_backward(_BidirectionalIterator1 __first1,
02850                    _BidirectionalIterator1 __last1,
02851                    _BidirectionalIterator2 __first2,
02852                    _BidirectionalIterator2 __last2,
02853                    _BidirectionalIterator3 __result,
02854                    _Compare __comp)
02855     {
02856       if (__first1 == __last1)
02857     {
02858       _GLIBCXX_MOVE_BACKWARD3(__first2, __last2, __result);
02859       return;
02860     }
02861       else if (__first2 == __last2)
02862     return;
02863 
02864       --__last1;
02865       --__last2;
02866       while (true)
02867     {
02868       if (__comp(*__last2, *__last1))
02869         {
02870           *--__result = _GLIBCXX_MOVE(*__last1);
02871           if (__first1 == __last1)
02872         {
02873           _GLIBCXX_MOVE_BACKWARD3(__first2, ++__last2, __result);
02874           return;
02875         }
02876           --__last1;
02877         }
02878       else
02879         {
02880           *--__result = _GLIBCXX_MOVE(*__last2);
02881           if (__first2 == __last2)
02882         return;
02883           --__last2;
02884         }
02885     }
02886     }
02887 
02888   /// This is a helper function for the merge routines.
02889   template<typename _BidirectionalIterator1, typename _BidirectionalIterator2,
02890        typename _Distance>
02891     _BidirectionalIterator1
02892     __rotate_adaptive(_BidirectionalIterator1 __first,
02893               _BidirectionalIterator1 __middle,
02894               _BidirectionalIterator1 __last,
02895               _Distance __len1, _Distance __len2,
02896               _BidirectionalIterator2 __buffer,
02897               _Distance __buffer_size)
02898     {
02899       _BidirectionalIterator2 __buffer_end;
02900       if (__len1 > __len2 && __len2 <= __buffer_size)
02901     {
02902       if (__len2)
02903         {
02904           __buffer_end = _GLIBCXX_MOVE3(__middle, __last, __buffer);
02905           _GLIBCXX_MOVE_BACKWARD3(__first, __middle, __last);
02906           return _GLIBCXX_MOVE3(__buffer, __buffer_end, __first);
02907         }
02908       else
02909         return __first;
02910     }
02911       else if (__len1 <= __buffer_size)
02912     {
02913       if (__len1)
02914         {
02915           __buffer_end = _GLIBCXX_MOVE3(__first, __middle, __buffer);
02916           _GLIBCXX_MOVE3(__middle, __last, __first);
02917           return _GLIBCXX_MOVE_BACKWARD3(__buffer, __buffer_end, __last);
02918         }
02919       else
02920         return __last;
02921     }
02922       else
02923     {
02924       std::rotate(__first, __middle, __last);
02925       std::advance(__first, std::distance(__middle, __last));
02926       return __first;
02927     }
02928     }
02929 
02930   /// This is a helper function for the merge routines.
02931   template<typename _BidirectionalIterator, typename _Distance,
02932        typename _Pointer>
02933     void
02934     __merge_adaptive(_BidirectionalIterator __first,
02935                      _BidirectionalIterator __middle,
02936              _BidirectionalIterator __last,
02937              _Distance __len1, _Distance __len2,
02938              _Pointer __buffer, _Distance __buffer_size)
02939     {
02940       if (__len1 <= __len2 && __len1 <= __buffer_size)
02941     {
02942       _Pointer __buffer_end = _GLIBCXX_MOVE3(__first, __middle, __buffer);
02943       std::__move_merge_adaptive(__buffer, __buffer_end, __middle, __last,
02944                      __first);
02945     }
02946       else if (__len2 <= __buffer_size)
02947     {
02948       _Pointer __buffer_end = _GLIBCXX_MOVE3(__middle, __last, __buffer);
02949       std::__move_merge_adaptive_backward(__first, __middle, __buffer,
02950                           __buffer_end, __last);
02951     }
02952       else
02953     {
02954       _BidirectionalIterator __first_cut = __first;
02955       _BidirectionalIterator __second_cut = __middle;
02956       _Distance __len11 = 0;
02957       _Distance __len22 = 0;
02958       if (__len1 > __len2)
02959         {
02960           __len11 = __len1 / 2;
02961           std::advance(__first_cut, __len11);
02962           __second_cut = std::lower_bound(__middle, __last,
02963                           *__first_cut);
02964           __len22 = std::distance(__middle, __second_cut);
02965         }
02966       else
02967         {
02968           __len22 = __len2 / 2;
02969           std::advance(__second_cut, __len22);
02970           __first_cut = std::upper_bound(__first, __middle,
02971                          *__second_cut);
02972           __len11 = std::distance(__first, __first_cut);
02973         }
02974       _BidirectionalIterator __new_middle =
02975         std::__rotate_adaptive(__first_cut, __middle, __second_cut,
02976                    __len1 - __len11, __len22, __buffer,
02977                    __buffer_size);
02978       std::__merge_adaptive(__first, __first_cut, __new_middle, __len11,
02979                 __len22, __buffer, __buffer_size);
02980       std::__merge_adaptive(__new_middle, __second_cut, __last,
02981                 __len1 - __len11,
02982                 __len2 - __len22, __buffer, __buffer_size);
02983     }
02984     }
02985 
02986   /// This is a helper function for the merge routines.
02987   template<typename _BidirectionalIterator, typename _Distance, 
02988        typename _Pointer, typename _Compare>
02989     void
02990     __merge_adaptive(_BidirectionalIterator __first,
02991                      _BidirectionalIterator __middle,
02992              _BidirectionalIterator __last,
02993              _Distance __len1, _Distance __len2,
02994              _Pointer __buffer, _Distance __buffer_size,
02995              _Compare __comp)
02996     {
02997       if (__len1 <= __len2 && __len1 <= __buffer_size)
02998     {
02999       _Pointer __buffer_end = _GLIBCXX_MOVE3(__first, __middle, __buffer);
03000       std::__move_merge_adaptive(__buffer, __buffer_end, __middle, __last,
03001                      __first, __comp);
03002     }
03003       else if (__len2 <= __buffer_size)
03004     {
03005       _Pointer __buffer_end = _GLIBCXX_MOVE3(__middle, __last, __buffer);
03006       std::__move_merge_adaptive_backward(__first, __middle, __buffer,
03007                           __buffer_end, __last, __comp);
03008     }
03009       else
03010     {
03011       _BidirectionalIterator __first_cut = __first;
03012       _BidirectionalIterator __second_cut = __middle;
03013       _Distance __len11 = 0;
03014       _Distance __len22 = 0;
03015       if (__len1 > __len2)
03016         {
03017           __len11 = __len1 / 2;
03018           std::advance(__first_cut, __len11);
03019           __second_cut = std::lower_bound(__middle, __last, *__first_cut,
03020                           __comp);
03021           __len22 = std::distance(__middle, __second_cut);
03022         }
03023       else
03024         {
03025           __len22 = __len2 / 2;
03026           std::advance(__second_cut, __len22);
03027           __first_cut = std::upper_bound(__first, __middle, *__second_cut,
03028                          __comp);
03029           __len11 = std::distance(__first, __first_cut);
03030         }
03031       _BidirectionalIterator __new_middle =
03032         std::__rotate_adaptive(__first_cut, __middle, __second_cut,
03033                    __len1 - __len11, __len22, __buffer,
03034                    __buffer_size);
03035       std::__merge_adaptive(__first, __first_cut, __new_middle, __len11,
03036                 __len22, __buffer, __buffer_size, __comp);
03037       std::__merge_adaptive(__new_middle, __second_cut, __last,
03038                 __len1 - __len11,
03039                 __len2 - __len22, __buffer,
03040                 __buffer_size, __comp);
03041     }
03042     }
03043 
03044   /// This is a helper function for the merge routines.
03045   template<typename _BidirectionalIterator, typename _Distance>
03046     void
03047     __merge_without_buffer(_BidirectionalIterator __first,
03048                _BidirectionalIterator __middle,
03049                _BidirectionalIterator __last,
03050                _Distance __len1, _Distance __len2)
03051     {
03052       if (__len1 == 0 || __len2 == 0)
03053     return;
03054       if (__len1 + __len2 == 2)
03055     {
03056       if (*__middle < *__first)
03057         std::iter_swap(__first, __middle);
03058       return;
03059     }
03060       _BidirectionalIterator __first_cut = __first;
03061       _BidirectionalIterator __second_cut = __middle;
03062       _Distance __len11 = 0;
03063       _Distance __len22 = 0;
03064       if (__len1 > __len2)
03065     {
03066       __len11 = __len1 / 2;
03067       std::advance(__first_cut, __len11);
03068       __second_cut = std::lower_bound(__middle, __last, *__first_cut);
03069       __len22 = std::distance(__middle, __second_cut);
03070     }
03071       else
03072     {
03073       __len22 = __len2 / 2;
03074       std::advance(__second_cut, __len22);
03075       __first_cut = std::upper_bound(__first, __middle, *__second_cut);
03076       __len11 = std::distance(__first, __first_cut);
03077     }
03078       std::rotate(__first_cut, __middle, __second_cut);
03079       _BidirectionalIterator __new_middle = __first_cut;
03080       std::advance(__new_middle, std::distance(__middle, __second_cut));
03081       std::__merge_without_buffer(__first, __first_cut, __new_middle,
03082                   __len11, __len22);
03083       std::__merge_without_buffer(__new_middle, __second_cut, __last,
03084                   __len1 - __len11, __len2 - __len22);
03085     }
03086 
03087   /// This is a helper function for the merge routines.
03088   template<typename _BidirectionalIterator, typename _Distance,
03089        typename _Compare>
03090     void
03091     __merge_without_buffer(_BidirectionalIterator __first,
03092                            _BidirectionalIterator __middle,
03093                _BidirectionalIterator __last,
03094                _Distance __len1, _Distance __len2,
03095                _Compare __comp)
03096     {
03097       if (__len1 == 0 || __len2 == 0)
03098     return;
03099       if (__len1 + __len2 == 2)
03100     {
03101       if (__comp(*__middle, *__first))
03102         std::iter_swap(__first, __middle);
03103       return;
03104     }
03105       _BidirectionalIterator __first_cut = __first;
03106       _BidirectionalIterator __second_cut = __middle;
03107       _Distance __len11 = 0;
03108       _Distance __len22 = 0;
03109       if (__len1 > __len2)
03110     {
03111       __len11 = __len1 / 2;
03112       std::advance(__first_cut, __len11);
03113       __second_cut = std::lower_bound(__middle, __last, *__first_cut,
03114                       __comp);
03115       __len22 = std::distance(__middle, __second_cut);
03116     }
03117       else
03118     {
03119       __len22 = __len2 / 2;
03120       std::advance(__second_cut, __len22);
03121       __first_cut = std::upper_bound(__first, __middle, *__second_cut,
03122                      __comp);
03123       __len11 = std::distance(__first, __first_cut);
03124     }
03125       std::rotate(__first_cut, __middle, __second_cut);
03126       _BidirectionalIterator __new_middle = __first_cut;
03127       std::advance(__new_middle, std::distance(__middle, __second_cut));
03128       std::__merge_without_buffer(__first, __first_cut, __new_middle,
03129                   __len11, __len22, __comp);
03130       std::__merge_without_buffer(__new_middle, __second_cut, __last,
03131                   __len1 - __len11, __len2 - __len22, __comp);
03132     }
03133 
03134   /**
03135    *  @brief Merges two sorted ranges in place.
03136    *  @ingroup sorting_algorithms
03137    *  @param  __first   An iterator.
03138    *  @param  __middle  Another iterator.
03139    *  @param  __last    Another iterator.
03140    *  @return  Nothing.
03141    *
03142    *  Merges two sorted and consecutive ranges, [__first,__middle) and
03143    *  [__middle,__last), and puts the result in [__first,__last).  The
03144    *  output will be sorted.  The sort is @e stable, that is, for
03145    *  equivalent elements in the two ranges, elements from the first
03146    *  range will always come before elements from the second.
03147    *
03148    *  If enough additional memory is available, this takes (__last-__first)-1
03149    *  comparisons.  Otherwise an NlogN algorithm is used, where N is
03150    *  distance(__first,__last).
03151   */
03152   template<typename _BidirectionalIterator>
03153     void
03154     inplace_merge(_BidirectionalIterator __first,
03155           _BidirectionalIterator __middle,
03156           _BidirectionalIterator __last)
03157     {
03158       typedef typename iterator_traits<_BidirectionalIterator>::value_type
03159           _ValueType;
03160       typedef typename iterator_traits<_BidirectionalIterator>::difference_type
03161           _DistanceType;
03162 
03163       // concept requirements
03164       __glibcxx_function_requires(_Mutable_BidirectionalIteratorConcept<
03165         _BidirectionalIterator>)
03166       __glibcxx_function_requires(_LessThanComparableConcept<_ValueType>)
03167       __glibcxx_requires_sorted(__first, __middle);
03168       __glibcxx_requires_sorted(__middle, __last);
03169 
03170       if (__first == __middle || __middle == __last)
03171     return;
03172 
03173       _DistanceType __len1 = std::distance(__first, __middle);
03174       _DistanceType __len2 = std::distance(__middle, __last);
03175 
03176       _Temporary_buffer<_BidirectionalIterator, _ValueType> __buf(__first,
03177                                   __last);
03178       if (__buf.begin() == 0)
03179     std::__merge_without_buffer(__first, __middle, __last, __len1, __len2);
03180       else
03181     std::__merge_adaptive(__first, __middle, __last, __len1, __len2,
03182                   __buf.begin(), _DistanceType(__buf.size()));
03183     }
03184 
03185   /**
03186    *  @brief Merges two sorted ranges in place.
03187    *  @ingroup sorting_algorithms
03188    *  @param  __first   An iterator.
03189    *  @param  __middle  Another iterator.
03190    *  @param  __last    Another iterator.
03191    *  @param  __comp    A functor to use for comparisons.
03192    *  @return  Nothing.
03193    *
03194    *  Merges two sorted and consecutive ranges, [__first,__middle) and
03195    *  [middle,last), and puts the result in [__first,__last).  The output will
03196    *  be sorted.  The sort is @e stable, that is, for equivalent
03197    *  elements in the two ranges, elements from the first range will always
03198    *  come before elements from the second.
03199    *
03200    *  If enough additional memory is available, this takes (__last-__first)-1
03201    *  comparisons.  Otherwise an NlogN algorithm is used, where N is
03202    *  distance(__first,__last).
03203    *
03204    *  The comparison function should have the same effects on ordering as
03205    *  the function used for the initial sort.
03206   */
03207   template<typename _BidirectionalIterator, typename _Compare>
03208     void
03209     inplace_merge(_BidirectionalIterator __first,
03210           _BidirectionalIterator __middle,
03211           _BidirectionalIterator __last,
03212           _Compare __comp)
03213     {
03214       typedef typename iterator_traits<_BidirectionalIterator>::value_type
03215           _ValueType;
03216       typedef typename iterator_traits<_BidirectionalIterator>::difference_type
03217           _DistanceType;
03218 
03219       // concept requirements
03220       __glibcxx_function_requires(_Mutable_BidirectionalIteratorConcept<
03221         _BidirectionalIterator>)
03222       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
03223         _ValueType, _ValueType>)
03224       __glibcxx_requires_sorted_pred(__first, __middle, __comp);
03225       __glibcxx_requires_sorted_pred(__middle, __last, __comp);
03226 
03227       if (__first == __middle || __middle == __last)
03228     return;
03229 
03230       const _DistanceType __len1 = std::distance(__first, __middle);
03231       const _DistanceType __len2 = std::distance(__middle, __last);
03232 
03233       _Temporary_buffer<_BidirectionalIterator, _ValueType> __buf(__first,
03234                                   __last);
03235       if (__buf.begin() == 0)
03236     std::__merge_without_buffer(__first, __middle, __last, __len1,
03237                     __len2, __comp);
03238       else
03239     std::__merge_adaptive(__first, __middle, __last, __len1, __len2,
03240                   __buf.begin(), _DistanceType(__buf.size()),
03241                   __comp);
03242     }
03243 
03244 
03245   /// This is a helper function for the __merge_sort_loop routines.
03246   template<typename _InputIterator1, typename _InputIterator2,
03247        typename _OutputIterator>
03248     _OutputIterator
03249     __move_merge(_InputIterator1 __first1, _InputIterator1 __last1,
03250          _InputIterator2 __first2, _InputIterator2 __last2,
03251          _OutputIterator __result)
03252     {
03253       while (__first1 != __last1 && __first2 != __last2)
03254     {
03255       if (*__first2 < *__first1)
03256         {
03257           *__result = _GLIBCXX_MOVE(*__first2);
03258           ++__first2;
03259         }
03260       else
03261         {
03262           *__result = _GLIBCXX_MOVE(*__first1);
03263           ++__first1;
03264         }
03265       ++__result;
03266     }
03267       return _GLIBCXX_MOVE3(__first2, __last2,
03268                 _GLIBCXX_MOVE3(__first1, __last1,
03269                        __result));
03270     }
03271 
03272   /// This is a helper function for the __merge_sort_loop routines.
03273   template<typename _InputIterator1, typename _InputIterator2,
03274        typename _OutputIterator, typename _Compare>
03275     _OutputIterator
03276     __move_merge(_InputIterator1 __first1, _InputIterator1 __last1,
03277          _InputIterator2 __first2, _InputIterator2 __last2,
03278          _OutputIterator __result, _Compare __comp)
03279     {
03280       while (__first1 != __last1 && __first2 != __last2)
03281     {
03282       if (__comp(*__first2, *__first1))
03283         {
03284           *__result = _GLIBCXX_MOVE(*__first2);
03285           ++__first2;
03286         }
03287       else
03288         {
03289           *__result = _GLIBCXX_MOVE(*__first1);
03290           ++__first1;
03291         }
03292       ++__result;
03293     }
03294       return _GLIBCXX_MOVE3(__first2, __last2,
03295                 _GLIBCXX_MOVE3(__first1, __last1,
03296                        __result));
03297     }
03298 
03299   template<typename _RandomAccessIterator1, typename _RandomAccessIterator2,
03300        typename _Distance>
03301     void
03302     __merge_sort_loop(_RandomAccessIterator1 __first,
03303               _RandomAccessIterator1 __last,
03304               _RandomAccessIterator2 __result,
03305               _Distance __step_size)
03306     {
03307       const _Distance __two_step = 2 * __step_size;
03308 
03309       while (__last - __first >= __two_step)
03310     {
03311       __result = std::__move_merge(__first, __first + __step_size,
03312                        __first + __step_size,
03313                        __first + __two_step, __result);
03314       __first += __two_step;
03315     }
03316 
03317       __step_size = std::min(_Distance(__last - __first), __step_size);
03318       std::__move_merge(__first, __first + __step_size,
03319             __first + __step_size, __last, __result);
03320     }
03321 
03322   template<typename _RandomAccessIterator1, typename _RandomAccessIterator2,
03323        typename _Distance, typename _Compare>
03324     void
03325     __merge_sort_loop(_RandomAccessIterator1 __first,
03326               _RandomAccessIterator1 __last,
03327               _RandomAccessIterator2 __result, _Distance __step_size,
03328               _Compare __comp)
03329     {
03330       const _Distance __two_step = 2 * __step_size;
03331 
03332       while (__last - __first >= __two_step)
03333     {
03334       __result = std::__move_merge(__first, __first + __step_size,
03335                        __first + __step_size,
03336                        __first + __two_step,
03337                        __result, __comp);
03338       __first += __two_step;
03339     }
03340       __step_size = std::min(_Distance(__last - __first), __step_size);
03341 
03342       std::__move_merge(__first,__first + __step_size,
03343             __first + __step_size, __last, __result, __comp);
03344     }
03345 
03346   template<typename _RandomAccessIterator, typename _Distance>
03347     void
03348     __chunk_insertion_sort(_RandomAccessIterator __first,
03349                _RandomAccessIterator __last,
03350                _Distance __chunk_size)
03351     {
03352       while (__last - __first >= __chunk_size)
03353     {
03354       std::__insertion_sort(__first, __first + __chunk_size);
03355       __first += __chunk_size;
03356     }
03357       std::__insertion_sort(__first, __last);
03358     }
03359 
03360   template<typename _RandomAccessIterator, typename _Distance,
03361        typename _Compare>
03362     void
03363     __chunk_insertion_sort(_RandomAccessIterator __first,
03364                _RandomAccessIterator __last,
03365                _Distance __chunk_size, _Compare __comp)
03366     {
03367       while (__last - __first >= __chunk_size)
03368     {
03369       std::__insertion_sort(__first, __first + __chunk_size, __comp);
03370       __first += __chunk_size;
03371     }
03372       std::__insertion_sort(__first, __last, __comp);
03373     }
03374 
03375   enum { _S_chunk_size = 7 };
03376 
03377   template<typename _RandomAccessIterator, typename _Pointer>
03378     void
03379     __merge_sort_with_buffer(_RandomAccessIterator __first,
03380                  _RandomAccessIterator __last,
03381                              _Pointer __buffer)
03382     {
03383       typedef typename iterator_traits<_RandomAccessIterator>::difference_type
03384     _Distance;
03385 
03386       const _Distance __len = __last - __first;
03387       const _Pointer __buffer_last = __buffer + __len;
03388 
03389       _Distance __step_size = _S_chunk_size;
03390       std::__chunk_insertion_sort(__first, __last, __step_size);
03391 
03392       while (__step_size < __len)
03393     {
03394       std::__merge_sort_loop(__first, __last, __buffer, __step_size);
03395       __step_size *= 2;
03396       std::__merge_sort_loop(__buffer, __buffer_last, __first, __step_size);
03397       __step_size *= 2;
03398     }
03399     }
03400 
03401   template<typename _RandomAccessIterator, typename _Pointer, typename _Compare>
03402     void
03403     __merge_sort_with_buffer(_RandomAccessIterator __first,
03404                  _RandomAccessIterator __last,
03405                              _Pointer __buffer, _Compare __comp)
03406     {
03407       typedef typename iterator_traits<_RandomAccessIterator>::difference_type
03408     _Distance;
03409 
03410       const _Distance __len = __last - __first;
03411       const _Pointer __buffer_last = __buffer + __len;
03412 
03413       _Distance __step_size = _S_chunk_size;
03414       std::__chunk_insertion_sort(__first, __last, __step_size, __comp);
03415 
03416       while (__step_size < __len)
03417     {
03418       std::__merge_sort_loop(__first, __last, __buffer,
03419                  __step_size, __comp);
03420       __step_size *= 2;
03421       std::__merge_sort_loop(__buffer, __buffer_last, __first,
03422                  __step_size, __comp);
03423       __step_size *= 2;
03424     }
03425     }
03426 
03427   template<typename _RandomAccessIterator, typename _Pointer,
03428        typename _Distance>
03429     void
03430     __stable_sort_adaptive(_RandomAccessIterator __first,
03431                _RandomAccessIterator __last,
03432                            _Pointer __buffer, _Distance __buffer_size)
03433     {
03434       const _Distance __len = (__last - __first + 1) / 2;
03435       const _RandomAccessIterator __middle = __first + __len;
03436       if (__len > __buffer_size)
03437     {
03438       std::__stable_sort_adaptive(__first, __middle,
03439                       __buffer, __buffer_size);
03440       std::__stable_sort_adaptive(__middle, __last,
03441                       __buffer, __buffer_size);
03442     }
03443       else
03444     {
03445       std::__merge_sort_with_buffer(__first, __middle, __buffer);
03446       std::__merge_sort_with_buffer(__middle, __last, __buffer);
03447     }
03448       std::__merge_adaptive(__first, __middle, __last,
03449                 _Distance(__middle - __first),
03450                 _Distance(__last - __middle),
03451                 __buffer, __buffer_size);
03452     }
03453 
03454   template<typename _RandomAccessIterator, typename _Pointer,
03455        typename _Distance, typename _Compare>
03456     void
03457     __stable_sort_adaptive(_RandomAccessIterator __first,
03458                _RandomAccessIterator __last,
03459                            _Pointer __buffer, _Distance __buffer_size,
03460                            _Compare __comp)
03461     {
03462       const _Distance __len = (__last - __first + 1) / 2;
03463       const _RandomAccessIterator __middle = __first + __len;
03464       if (__len > __buffer_size)
03465     {
03466       std::__stable_sort_adaptive(__first, __middle, __buffer,
03467                       __buffer_size, __comp);
03468       std::__stable_sort_adaptive(__middle, __last, __buffer,
03469                       __buffer_size, __comp);
03470     }
03471       else
03472     {
03473       std::__merge_sort_with_buffer(__first, __middle, __buffer, __comp);
03474       std::__merge_sort_with_buffer(__middle, __last, __buffer, __comp);
03475     }
03476       std::__merge_adaptive(__first, __middle, __last,
03477                 _Distance(__middle - __first),
03478                 _Distance(__last - __middle),
03479                 __buffer, __buffer_size,
03480                 __comp);
03481     }
03482 
03483   /// This is a helper function for the stable sorting routines.
03484   template<typename _RandomAccessIterator>
03485     void
03486     __inplace_stable_sort(_RandomAccessIterator __first,
03487               _RandomAccessIterator __last)
03488     {
03489       if (__last - __first < 15)
03490     {
03491       std::__insertion_sort(__first, __last);
03492       return;
03493     }
03494       _RandomAccessIterator __middle = __first + (__last - __first) / 2;
03495       std::__inplace_stable_sort(__first, __middle);
03496       std::__inplace_stable_sort(__middle, __last);
03497       std::__merge_without_buffer(__first, __middle, __last,
03498                   __middle - __first,
03499                   __last - __middle);
03500     }
03501 
03502   /// This is a helper function for the stable sorting routines.
03503   template<typename _RandomAccessIterator, typename _Compare>
03504     void
03505     __inplace_stable_sort(_RandomAccessIterator __first,
03506               _RandomAccessIterator __last, _Compare __comp)
03507     {
03508       if (__last - __first < 15)
03509     {
03510       std::__insertion_sort(__first, __last, __comp);
03511       return;
03512     }
03513       _RandomAccessIterator __middle = __first + (__last - __first) / 2;
03514       std::__inplace_stable_sort(__first, __middle, __comp);
03515       std::__inplace_stable_sort(__middle, __last, __comp);
03516       std::__merge_without_buffer(__first, __middle, __last,
03517                   __middle - __first,
03518                   __last - __middle,
03519                   __comp);
03520     }
03521 
03522   // stable_sort
03523 
03524   // Set algorithms: includes, set_union, set_intersection, set_difference,
03525   // set_symmetric_difference.  All of these algorithms have the precondition
03526   // that their input ranges are sorted and the postcondition that their output
03527   // ranges are sorted.
03528 
03529   /**
03530    *  @brief Determines whether all elements of a sequence exists in a range.
03531    *  @param  __first1  Start of search range.
03532    *  @param  __last1   End of search range.
03533    *  @param  __first2  Start of sequence
03534    *  @param  __last2   End of sequence.
03535    *  @return  True if each element in [__first2,__last2) is contained in order
03536    *  within [__first1,__last1).  False otherwise.
03537    *  @ingroup set_algorithms
03538    *
03539    *  This operation expects both [__first1,__last1) and
03540    *  [__first2,__last2) to be sorted.  Searches for the presence of
03541    *  each element in [__first2,__last2) within [__first1,__last1).
03542    *  The iterators over each range only move forward, so this is a
03543    *  linear algorithm.  If an element in [__first2,__last2) is not
03544    *  found before the search iterator reaches @p __last2, false is
03545    *  returned.
03546   */
03547   template<typename _InputIterator1, typename _InputIterator2>
03548     bool
03549     includes(_InputIterator1 __first1, _InputIterator1 __last1,
03550          _InputIterator2 __first2, _InputIterator2 __last2)
03551     {
03552       typedef typename iterator_traits<_InputIterator1>::value_type
03553     _ValueType1;
03554       typedef typename iterator_traits<_InputIterator2>::value_type
03555     _ValueType2;
03556 
03557       // concept requirements
03558       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
03559       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
03560       __glibcxx_function_requires(_LessThanOpConcept<_ValueType1, _ValueType2>)
03561       __glibcxx_function_requires(_LessThanOpConcept<_ValueType2, _ValueType1>)
03562       __glibcxx_requires_sorted_set(__first1, __last1, __first2);
03563       __glibcxx_requires_sorted_set(__first2, __last2, __first1);
03564 
03565       while (__first1 != __last1 && __first2 != __last2)
03566     if (*__first2 < *__first1)
03567       return false;
03568     else if(*__first1 < *__first2)
03569       ++__first1;
03570     else
03571       ++__first1, ++__first2;
03572 
03573       return __first2 == __last2;
03574     }
03575 
03576   /**
03577    *  @brief Determines whether all elements of a sequence exists in a range
03578    *  using comparison.
03579    *  @ingroup set_algorithms
03580    *  @param  __first1  Start of search range.
03581    *  @param  __last1   End of search range.
03582    *  @param  __first2  Start of sequence
03583    *  @param  __last2   End of sequence.
03584    *  @param  __comp    Comparison function to use.
03585    *  @return True if each element in [__first2,__last2) is contained
03586    *  in order within [__first1,__last1) according to comp.  False
03587    *  otherwise.  @ingroup set_algorithms
03588    *
03589    *  This operation expects both [__first1,__last1) and
03590    *  [__first2,__last2) to be sorted.  Searches for the presence of
03591    *  each element in [__first2,__last2) within [__first1,__last1),
03592    *  using comp to decide.  The iterators over each range only move
03593    *  forward, so this is a linear algorithm.  If an element in
03594    *  [__first2,__last2) is not found before the search iterator
03595    *  reaches @p __last2, false is returned.
03596   */
03597   template<typename _InputIterator1, typename _InputIterator2,
03598        typename _Compare>
03599     bool
03600     includes(_InputIterator1 __first1, _InputIterator1 __last1,
03601          _InputIterator2 __first2, _InputIterator2 __last2,
03602          _Compare __comp)
03603     {
03604       typedef typename iterator_traits<_InputIterator1>::value_type
03605     _ValueType1;
03606       typedef typename iterator_traits<_InputIterator2>::value_type
03607     _ValueType2;
03608 
03609       // concept requirements
03610       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
03611       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
03612       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
03613                   _ValueType1, _ValueType2>)
03614       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
03615                   _ValueType2, _ValueType1>)
03616       __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp);
03617       __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp);
03618 
03619       while (__first1 != __last1 && __first2 != __last2)
03620     if (__comp(*__first2, *__first1))
03621       return false;
03622     else if(__comp(*__first1, *__first2))
03623       ++__first1;
03624     else
03625       ++__first1, ++__first2;
03626 
03627       return __first2 == __last2;
03628     }
03629 
03630   // nth_element
03631   // merge
03632   // set_difference
03633   // set_intersection
03634   // set_union
03635   // stable_sort
03636   // set_symmetric_difference
03637   // min_element
03638   // max_element
03639 
03640   /**
03641    *  @brief  Permute range into the next @e dictionary ordering.
03642    *  @ingroup sorting_algorithms
03643    *  @param  __first  Start of range.
03644    *  @param  __last   End of range.
03645    *  @return  False if wrapped to first permutation, true otherwise.
03646    *
03647    *  Treats all permutations of the range as a set of @e dictionary sorted
03648    *  sequences.  Permutes the current sequence into the next one of this set.
03649    *  Returns true if there are more sequences to generate.  If the sequence
03650    *  is the largest of the set, the smallest is generated and false returned.
03651   */
03652   template<typename _BidirectionalIterator>
03653     bool
03654     next_permutation(_BidirectionalIterator __first,
03655              _BidirectionalIterator __last)
03656     {
03657       // concept requirements
03658       __glibcxx_function_requires(_BidirectionalIteratorConcept<
03659                   _BidirectionalIterator>)
03660       __glibcxx_function_requires(_LessThanComparableConcept<
03661         typename iterator_traits<_BidirectionalIterator>::value_type>)
03662       __glibcxx_requires_valid_range(__first, __last);
03663 
03664       if (__first == __last)
03665     return false;
03666       _BidirectionalIterator __i = __first;
03667       ++__i;
03668       if (__i == __last)
03669     return false;
03670       __i = __last;
03671       --__i;
03672 
03673       for(;;)
03674     {
03675       _BidirectionalIterator __ii = __i;
03676       --__i;
03677       if (*__i < *__ii)
03678         {
03679           _BidirectionalIterator __j = __last;
03680           while (!(*__i < *--__j))
03681         {}
03682           std::iter_swap(__i, __j);
03683           std::reverse(__ii, __last);
03684           return true;
03685         }
03686       if (__i == __first)
03687         {
03688           std::reverse(__first, __last);
03689           return false;
03690         }
03691     }
03692     }
03693 
03694   /**
03695    *  @brief  Permute range into the next @e dictionary ordering using
03696    *          comparison functor.
03697    *  @ingroup sorting_algorithms
03698    *  @param  __first  Start of range.
03699    *  @param  __last   End of range.
03700    *  @param  __comp   A comparison functor.
03701    *  @return  False if wrapped to first permutation, true otherwise.
03702    *
03703    *  Treats all permutations of the range [__first,__last) as a set of
03704    *  @e dictionary sorted sequences ordered by @p __comp.  Permutes the current
03705    *  sequence into the next one of this set.  Returns true if there are more
03706    *  sequences to generate.  If the sequence is the largest of the set, the
03707    *  smallest is generated and false returned.
03708   */
03709   template<typename _BidirectionalIterator, typename _Compare>
03710     bool
03711     next_permutation(_BidirectionalIterator __first,
03712              _BidirectionalIterator __last, _Compare __comp)
03713     {
03714       // concept requirements
03715       __glibcxx_function_requires(_BidirectionalIteratorConcept<
03716                   _BidirectionalIterator>)
03717       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
03718         typename iterator_traits<_BidirectionalIterator>::value_type,
03719         typename iterator_traits<_BidirectionalIterator>::value_type>)
03720       __glibcxx_requires_valid_range(__first, __last);
03721 
03722       if (__first == __last)
03723     return false;
03724       _BidirectionalIterator __i = __first;
03725       ++__i;
03726       if (__i == __last)
03727     return false;
03728       __i = __last;
03729       --__i;
03730 
03731       for(;;)
03732     {
03733       _BidirectionalIterator __ii = __i;
03734       --__i;
03735       if (__comp(*__i, *__ii))
03736         {
03737           _BidirectionalIterator __j = __last;
03738           while (!bool(__comp(*__i, *--__j)))
03739         {}
03740           std::iter_swap(__i, __j);
03741           std::reverse(__ii, __last);
03742           return true;
03743         }
03744       if (__i == __first)
03745         {
03746           std::reverse(__first, __last);
03747           return false;
03748         }
03749     }
03750     }
03751 
03752   /**
03753    *  @brief  Permute range into the previous @e dictionary ordering.
03754    *  @ingroup sorting_algorithms
03755    *  @param  __first  Start of range.
03756    *  @param  __last   End of range.
03757    *  @return  False if wrapped to last permutation, true otherwise.
03758    *
03759    *  Treats all permutations of the range as a set of @e dictionary sorted
03760    *  sequences.  Permutes the current sequence into the previous one of this
03761    *  set.  Returns true if there are more sequences to generate.  If the
03762    *  sequence is the smallest of the set, the largest is generated and false
03763    *  returned.
03764   */
03765   template<typename _BidirectionalIterator>
03766     bool
03767     prev_permutation(_BidirectionalIterator __first,
03768              _BidirectionalIterator __last)
03769     {
03770       // concept requirements
03771       __glibcxx_function_requires(_BidirectionalIteratorConcept<
03772                   _BidirectionalIterator>)
03773       __glibcxx_function_requires(_LessThanComparableConcept<
03774         typename iterator_traits<_BidirectionalIterator>::value_type>)
03775       __glibcxx_requires_valid_range(__first, __last);
03776 
03777       if (__first == __last)
03778     return false;
03779       _BidirectionalIterator __i = __first;
03780       ++__i;
03781       if (__i == __last)
03782     return false;
03783       __i = __last;
03784       --__i;
03785 
03786       for(;;)
03787     {
03788       _BidirectionalIterator __ii = __i;
03789       --__i;
03790       if (*__ii < *__i)
03791         {
03792           _BidirectionalIterator __j = __last;
03793           while (!(*--__j < *__i))
03794         {}
03795           std::iter_swap(__i, __j);
03796           std::reverse(__ii, __last);
03797           return true;
03798         }
03799       if (__i == __first)
03800         {
03801           std::reverse(__first, __last);
03802           return false;
03803         }
03804     }
03805     }
03806 
03807   /**
03808    *  @brief  Permute range into the previous @e dictionary ordering using
03809    *          comparison functor.
03810    *  @ingroup sorting_algorithms
03811    *  @param  __first  Start of range.
03812    *  @param  __last   End of range.
03813    *  @param  __comp   A comparison functor.
03814    *  @return  False if wrapped to last permutation, true otherwise.
03815    *
03816    *  Treats all permutations of the range [__first,__last) as a set of
03817    *  @e dictionary sorted sequences ordered by @p __comp.  Permutes the current
03818    *  sequence into the previous one of this set.  Returns true if there are
03819    *  more sequences to generate.  If the sequence is the smallest of the set,
03820    *  the largest is generated and false returned.
03821   */
03822   template<typename _BidirectionalIterator, typename _Compare>
03823     bool
03824     prev_permutation(_BidirectionalIterator __first,
03825              _BidirectionalIterator __last, _Compare __comp)
03826     {
03827       // concept requirements
03828       __glibcxx_function_requires(_BidirectionalIteratorConcept<
03829                   _BidirectionalIterator>)
03830       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
03831         typename iterator_traits<_BidirectionalIterator>::value_type,
03832         typename iterator_traits<_BidirectionalIterator>::value_type>)
03833       __glibcxx_requires_valid_range(__first, __last);
03834 
03835       if (__first == __last)
03836     return false;
03837       _BidirectionalIterator __i = __first;
03838       ++__i;
03839       if (__i == __last)
03840     return false;
03841       __i = __last;
03842       --__i;
03843 
03844       for(;;)
03845     {
03846       _BidirectionalIterator __ii = __i;
03847       --__i;
03848       if (__comp(*__ii, *__i))
03849         {
03850           _BidirectionalIterator __j = __last;
03851           while (!bool(__comp(*--__j, *__i)))
03852         {}
03853           std::iter_swap(__i, __j);
03854           std::reverse(__ii, __last);
03855           return true;
03856         }
03857       if (__i == __first)
03858         {
03859           std::reverse(__first, __last);
03860           return false;
03861         }
03862     }
03863     }
03864 
03865   // replace
03866   // replace_if
03867 
03868   /**
03869    *  @brief Copy a sequence, replacing each element of one value with another
03870    *         value.
03871    *  @param  __first      An input iterator.
03872    *  @param  __last       An input iterator.
03873    *  @param  __result     An output iterator.
03874    *  @param  __old_value  The value to be replaced.
03875    *  @param  __new_value  The replacement value.
03876    *  @return   The end of the output sequence, @p result+(last-first).
03877    *
03878    *  Copies each element in the input range @p [__first,__last) to the
03879    *  output range @p [__result,__result+(__last-__first)) replacing elements
03880    *  equal to @p __old_value with @p __new_value.
03881   */
03882   template<typename _InputIterator, typename _OutputIterator, typename _Tp>
03883     _OutputIterator
03884     replace_copy(_InputIterator __first, _InputIterator __last,
03885          _OutputIterator __result,
03886          const _Tp& __old_value, const _Tp& __new_value)
03887     {
03888       // concept requirements
03889       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
03890       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
03891         typename iterator_traits<_InputIterator>::value_type>)
03892       __glibcxx_function_requires(_EqualOpConcept<
03893         typename iterator_traits<_InputIterator>::value_type, _Tp>)
03894       __glibcxx_requires_valid_range(__first, __last);
03895 
03896       for (; __first != __last; ++__first, ++__result)
03897     if (*__first == __old_value)
03898       *__result = __new_value;
03899     else
03900       *__result = *__first;
03901       return __result;
03902     }
03903 
03904   /**
03905    *  @brief Copy a sequence, replacing each value for which a predicate
03906    *         returns true with another value.
03907    *  @ingroup mutating_algorithms
03908    *  @param  __first      An input iterator.
03909    *  @param  __last       An input iterator.
03910    *  @param  __result     An output iterator.
03911    *  @param  __pred       A predicate.
03912    *  @param  __new_value  The replacement value.
03913    *  @return   The end of the output sequence, @p __result+(__last-__first).
03914    *
03915    *  Copies each element in the range @p [__first,__last) to the range
03916    *  @p [__result,__result+(__last-__first)) replacing elements for which
03917    *  @p __pred returns true with @p __new_value.
03918   */
03919   template<typename _InputIterator, typename _OutputIterator,
03920        typename _Predicate, typename _Tp>
03921     _OutputIterator
03922     replace_copy_if(_InputIterator __first, _InputIterator __last,
03923             _OutputIterator __result,
03924             _Predicate __pred, const _Tp& __new_value)
03925     {
03926       // concept requirements
03927       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
03928       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
03929         typename iterator_traits<_InputIterator>::value_type>)
03930       __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
03931         typename iterator_traits<_InputIterator>::value_type>)
03932       __glibcxx_requires_valid_range(__first, __last);
03933 
03934       for (; __first != __last; ++__first, ++__result)
03935     if (__pred(*__first))
03936       *__result = __new_value;
03937     else
03938       *__result = *__first;
03939       return __result;
03940     }
03941 
03942 #if __cplusplus >= 201103L
03943   /**
03944    *  @brief  Determines whether the elements of a sequence are sorted.
03945    *  @ingroup sorting_algorithms
03946    *  @param  __first   An iterator.
03947    *  @param  __last    Another iterator.
03948    *  @return  True if the elements are sorted, false otherwise.
03949   */
03950   template<typename _ForwardIterator>
03951     inline bool
03952     is_sorted(_ForwardIterator __first, _ForwardIterator __last)
03953     { return std::is_sorted_until(__first, __last) == __last; }
03954 
03955   /**
03956    *  @brief  Determines whether the elements of a sequence are sorted
03957    *          according to a comparison functor.
03958    *  @ingroup sorting_algorithms
03959    *  @param  __first   An iterator.
03960    *  @param  __last    Another iterator.
03961    *  @param  __comp    A comparison functor.
03962    *  @return  True if the elements are sorted, false otherwise.
03963   */
03964   template<typename _ForwardIterator, typename _Compare>
03965     inline bool
03966     is_sorted(_ForwardIterator __first, _ForwardIterator __last,
03967           _Compare __comp)
03968     { return std::is_sorted_until(__first, __last, __comp) == __last; }
03969 
03970   /**
03971    *  @brief  Determines the end of a sorted sequence.
03972    *  @ingroup sorting_algorithms
03973    *  @param  __first   An iterator.
03974    *  @param  __last    Another iterator.
03975    *  @return  An iterator pointing to the last iterator i in [__first, __last)
03976    *           for which the range [__first, i) is sorted.
03977   */
03978   template<typename _ForwardIterator>
03979     _ForwardIterator
03980     is_sorted_until(_ForwardIterator __first, _ForwardIterator __last)
03981     {
03982       // concept requirements
03983       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
03984       __glibcxx_function_requires(_LessThanComparableConcept<
03985         typename iterator_traits<_ForwardIterator>::value_type>)
03986       __glibcxx_requires_valid_range(__first, __last);
03987 
03988       if (__first == __last)
03989     return __last;
03990 
03991       _ForwardIterator __next = __first;
03992       for (++__next; __next != __last; __first = __next, ++__next)
03993     if (*__next < *__first)
03994       return __next;
03995       return __next;
03996     }
03997 
03998   /**
03999    *  @brief  Determines the end of a sorted sequence using comparison functor.
04000    *  @ingroup sorting_algorithms
04001    *  @param  __first   An iterator.
04002    *  @param  __last    Another iterator.
04003    *  @param  __comp    A comparison functor.
04004    *  @return  An iterator pointing to the last iterator i in [__first, __last)
04005    *           for which the range [__first, i) is sorted.
04006   */
04007   template<typename _ForwardIterator, typename _Compare>
04008     _ForwardIterator
04009     is_sorted_until(_ForwardIterator __first, _ForwardIterator __last,
04010             _Compare __comp)
04011     {
04012       // concept requirements
04013       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
04014       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
04015         typename iterator_traits<_ForwardIterator>::value_type,
04016         typename iterator_traits<_ForwardIterator>::value_type>)
04017       __glibcxx_requires_valid_range(__first, __last);
04018 
04019       if (__first == __last)
04020     return __last;
04021 
04022       _ForwardIterator __next = __first;
04023       for (++__next; __next != __last; __first = __next, ++__next)
04024     if (__comp(*__next, *__first))
04025       return __next;
04026       return __next;
04027     }
04028 
04029   /**
04030    *  @brief  Determines min and max at once as an ordered pair.
04031    *  @ingroup sorting_algorithms
04032    *  @param  __a  A thing of arbitrary type.
04033    *  @param  __b  Another thing of arbitrary type.
04034    *  @return A pair(__b, __a) if __b is smaller than __a, pair(__a,
04035    *  __b) otherwise.
04036   */
04037   template<typename _Tp>
04038     inline pair<const _Tp&, const _Tp&>
04039     minmax(const _Tp& __a, const _Tp& __b)
04040     {
04041       // concept requirements
04042       __glibcxx_function_requires(_LessThanComparableConcept<_Tp>)
04043 
04044       return __b < __a ? pair<const _Tp&, const _Tp&>(__b, __a)
04045                    : pair<const _Tp&, const _Tp&>(__a, __b);
04046     }
04047 
04048   /**
04049    *  @brief  Determines min and max at once as an ordered pair.
04050    *  @ingroup sorting_algorithms
04051    *  @param  __a  A thing of arbitrary type.
04052    *  @param  __b  Another thing of arbitrary type.
04053    *  @param  __comp  A @link comparison_functors comparison functor @endlink.
04054    *  @return A pair(__b, __a) if __b is smaller than __a, pair(__a,
04055    *  __b) otherwise.
04056   */
04057   template<typename _Tp, typename _Compare>
04058     inline pair<const _Tp&, const _Tp&>
04059     minmax(const _Tp& __a, const _Tp& __b, _Compare __comp)
04060     {
04061       return __comp(__b, __a) ? pair<const _Tp&, const _Tp&>(__b, __a)
04062                           : pair<const _Tp&, const _Tp&>(__a, __b);
04063     }
04064 
04065   /**
04066    *  @brief  Return a pair of iterators pointing to the minimum and maximum
04067    *          elements in a range.
04068    *  @ingroup sorting_algorithms
04069    *  @param  __first  Start of range.
04070    *  @param  __last   End of range.
04071    *  @return  make_pair(m, M), where m is the first iterator i in 
04072    *           [__first, __last) such that no other element in the range is
04073    *           smaller, and where M is the last iterator i in [__first, __last)
04074    *           such that no other element in the range is larger.
04075   */
04076   template<typename _ForwardIterator>
04077     pair<_ForwardIterator, _ForwardIterator>
04078     minmax_element(_ForwardIterator __first, _ForwardIterator __last)
04079     {
04080       // concept requirements
04081       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
04082       __glibcxx_function_requires(_LessThanComparableConcept<
04083         typename iterator_traits<_ForwardIterator>::value_type>)
04084       __glibcxx_requires_valid_range(__first, __last);
04085 
04086       _ForwardIterator __next = __first;
04087       if (__first == __last
04088       || ++__next == __last)
04089     return std::make_pair(__first, __first);
04090 
04091       _ForwardIterator __min, __max;
04092       if (*__next < *__first)
04093     {
04094       __min = __next;
04095       __max = __first;
04096     }
04097       else
04098     {
04099       __min = __first;
04100       __max = __next;
04101     }
04102 
04103       __first = __next;
04104       ++__first;
04105 
04106       while (__first != __last)
04107     {
04108       __next = __first;
04109       if (++__next == __last)
04110         {
04111           if (*__first < *__min)
04112         __min = __first;
04113           else if (!(*__first < *__max))
04114         __max = __first;
04115           break;
04116         }
04117 
04118       if (*__next < *__first)
04119         {
04120           if (*__next < *__min)
04121         __min = __next;
04122           if (!(*__first < *__max))
04123         __max = __first;
04124         }
04125       else
04126         {
04127           if (*__first < *__min)
04128         __min = __first;
04129           if (!(*__next < *__max))
04130         __max = __next;
04131         }
04132 
04133       __first = __next;
04134       ++__first;
04135     }
04136 
04137       return std::make_pair(__min, __max);
04138     }
04139 
04140   /**
04141    *  @brief  Return a pair of iterators pointing to the minimum and maximum
04142    *          elements in a range.
04143    *  @ingroup sorting_algorithms
04144    *  @param  __first  Start of range.
04145    *  @param  __last   End of range.
04146    *  @param  __comp   Comparison functor.
04147    *  @return  make_pair(m, M), where m is the first iterator i in 
04148    *           [__first, __last) such that no other element in the range is
04149    *           smaller, and where M is the last iterator i in [__first, __last)
04150    *           such that no other element in the range is larger.
04151   */
04152   template<typename _ForwardIterator, typename _Compare>
04153     pair<_ForwardIterator, _ForwardIterator>
04154     minmax_element(_ForwardIterator __first, _ForwardIterator __last,
04155            _Compare __comp)
04156     {
04157       // concept requirements
04158       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
04159       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
04160         typename iterator_traits<_ForwardIterator>::value_type,
04161         typename iterator_traits<_ForwardIterator>::value_type>)
04162       __glibcxx_requires_valid_range(__first, __last);
04163 
04164       _ForwardIterator __next = __first;
04165       if (__first == __last
04166       || ++__next == __last)
04167     return std::make_pair(__first, __first);
04168 
04169       _ForwardIterator __min, __max;
04170       if (__comp(*__next, *__first))
04171     {
04172       __min = __next;
04173       __max = __first;
04174     }
04175       else
04176     {
04177       __min = __first;
04178       __max = __next;
04179     }
04180 
04181       __first = __next;
04182       ++__first;
04183 
04184       while (__first != __last)
04185     {
04186       __next = __first;
04187       if (++__next == __last)
04188         {
04189           if (__comp(*__first, *__min))
04190         __min = __first;
04191           else if (!__comp(*__first, *__max))
04192         __max = __first;
04193           break;
04194         }
04195 
04196       if (__comp(*__next, *__first))
04197         {
04198           if (__comp(*__next, *__min))
04199         __min = __next;
04200           if (!__comp(*__first, *__max))
04201         __max = __first;
04202         }
04203       else
04204         {
04205           if (__comp(*__first, *__min))
04206         __min = __first;
04207           if (!__comp(*__next, *__max))
04208         __max = __next;
04209         }
04210 
04211       __first = __next;
04212       ++__first;
04213     }
04214 
04215       return std::make_pair(__min, __max);
04216     }
04217 
04218   // N2722 + DR 915.
04219   template<typename _Tp>
04220     inline _Tp
04221     min(initializer_list<_Tp> __l)
04222     { return *std::min_element(__l.begin(), __l.end()); }
04223 
04224   template<typename _Tp, typename _Compare>
04225     inline _Tp
04226     min(initializer_list<_Tp> __l, _Compare __comp)
04227     { return *std::min_element(__l.begin(), __l.end(), __comp); }
04228 
04229   template<typename _Tp>
04230     inline _Tp
04231     max(initializer_list<_Tp> __l)
04232     { return *std::max_element(__l.begin(), __l.end()); }
04233 
04234   template<typename _Tp, typename _Compare>
04235     inline _Tp
04236     max(initializer_list<_Tp> __l, _Compare __comp)
04237     { return *std::max_element(__l.begin(), __l.end(), __comp); }
04238 
04239   template<typename _Tp>
04240     inline pair<_Tp, _Tp>
04241     minmax(initializer_list<_Tp> __l)
04242     {
04243       pair<const _Tp*, const _Tp*> __p =
04244     std::minmax_element(__l.begin(), __l.end());
04245       return std::make_pair(*__p.first, *__p.second);
04246     }
04247 
04248   template<typename _Tp, typename _Compare>
04249     inline pair<_Tp, _Tp>
04250     minmax(initializer_list<_Tp> __l, _Compare __comp)
04251     {
04252       pair<const _Tp*, const _Tp*> __p =
04253     std::minmax_element(__l.begin(), __l.end(), __comp);
04254       return std::make_pair(*__p.first, *__p.second);
04255     }
04256 
04257   /**
04258    *  @brief  Checks whether a permutaion of the second sequence is equal
04259    *          to the first sequence.
04260    *  @ingroup non_mutating_algorithms
04261    *  @param  __first1  Start of first range.
04262    *  @param  __last1   End of first range.
04263    *  @param  __first2  Start of second range.
04264    *  @return true if there exists a permutation of the elements in the range
04265    *          [__first2, __first2 + (__last1 - __first1)), beginning with 
04266    *          ForwardIterator2 begin, such that equal(__first1, __last1, begin)
04267    *          returns true; otherwise, returns false.
04268   */
04269   template<typename _ForwardIterator1, typename _ForwardIterator2>
04270     bool
04271     is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
04272            _ForwardIterator2 __first2)
04273     {
04274       // Efficiently compare identical prefixes:  O(N) if sequences
04275       // have the same elements in the same order.
04276       for (; __first1 != __last1; ++__first1, ++__first2)
04277     if (!(*__first1 == *__first2))
04278       break;
04279 
04280       if (__first1 == __last1)
04281     return true;
04282 
04283       // Establish __last2 assuming equal ranges by iterating over the
04284       // rest of the list.
04285       _ForwardIterator2 __last2 = __first2;
04286       std::advance(__last2, std::distance(__first1, __last1));
04287       for (_ForwardIterator1 __scan = __first1; __scan != __last1; ++__scan)
04288     {
04289       if (__scan != _GLIBCXX_STD_A::find(__first1, __scan, *__scan))
04290         continue; // We've seen this one before.
04291 
04292       auto __matches = std::count(__first2, __last2, *__scan);
04293       if (0 == __matches
04294           || std::count(__scan, __last1, *__scan) != __matches)
04295         return false;
04296     }
04297       return true;
04298     }
04299 
04300   /**
04301    *  @brief  Checks whether a permutation of the second sequence is equal
04302    *          to the first sequence.
04303    *  @ingroup non_mutating_algorithms
04304    *  @param  __first1  Start of first range.
04305    *  @param  __last1   End of first range.
04306    *  @param  __first2  Start of second range.
04307    *  @param  __pred    A binary predicate.
04308    *  @return true if there exists a permutation of the elements in
04309    *          the range [__first2, __first2 + (__last1 - __first1)),
04310    *          beginning with ForwardIterator2 begin, such that
04311    *          equal(__first1, __last1, __begin, __pred) returns true;
04312    *          otherwise, returns false.
04313   */
04314   template<typename _ForwardIterator1, typename _ForwardIterator2,
04315        typename _BinaryPredicate>
04316     bool
04317     is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
04318            _ForwardIterator2 __first2, _BinaryPredicate __pred)
04319     {
04320       // Efficiently compare identical prefixes:  O(N) if sequences
04321       // have the same elements in the same order.
04322       for (; __first1 != __last1; ++__first1, ++__first2)
04323     if (!bool(__pred(*__first1, *__first2)))
04324       break;
04325 
04326       if (__first1 == __last1)
04327     return true;
04328 
04329       // Establish __last2 assuming equal ranges by iterating over the
04330       // rest of the list.
04331       _ForwardIterator2 __last2 = __first2;
04332       std::advance(__last2, std::distance(__first1, __last1));
04333       for (_ForwardIterator1 __scan = __first1; __scan != __last1; ++__scan)
04334     {
04335       using std::placeholders::_1;
04336 
04337       if (__scan != _GLIBCXX_STD_A::find_if(__first1, __scan,
04338                         std::bind(__pred, _1, *__scan)))
04339         continue; // We've seen this one before.
04340       
04341       auto __matches = std::count_if(__first2, __last2,
04342                      std::bind(__pred, _1, *__scan));
04343       if (0 == __matches
04344           || std::count_if(__scan, __last1,
04345                    std::bind(__pred, _1, *__scan)) != __matches)
04346         return false;
04347     }
04348       return true;
04349     }
04350 
04351 #ifdef _GLIBCXX_USE_C99_STDINT_TR1
04352   /**
04353    *  @brief Shuffle the elements of a sequence using a uniform random
04354    *         number generator.
04355    *  @ingroup mutating_algorithms
04356    *  @param  __first   A forward iterator.
04357    *  @param  __last    A forward iterator.
04358    *  @param  __g       A UniformRandomNumberGenerator (26.5.1.3).
04359    *  @return  Nothing.
04360    *
04361    *  Reorders the elements in the range @p [__first,__last) using @p __g to
04362    *  provide random numbers.
04363   */
04364   template<typename _RandomAccessIterator,
04365        typename _UniformRandomNumberGenerator>
04366     void
04367     shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last,
04368         _UniformRandomNumberGenerator&& __g)
04369     {
04370       // concept requirements
04371       __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
04372         _RandomAccessIterator>)
04373       __glibcxx_requires_valid_range(__first, __last);
04374 
04375       if (__first == __last)
04376     return;
04377 
04378       typedef typename iterator_traits<_RandomAccessIterator>::difference_type
04379     _DistanceType;
04380 
04381       typedef typename std::make_unsigned<_DistanceType>::type __ud_type;
04382       typedef typename std::uniform_int_distribution<__ud_type> __distr_type;
04383       typedef typename __distr_type::param_type __p_type;
04384       __distr_type __d;
04385 
04386       for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i)
04387     std::iter_swap(__i, __first + __d(__g, __p_type(0, __i - __first)));
04388     }
04389 #endif
04390 
04391 #endif // C++11
04392 
04393 _GLIBCXX_END_NAMESPACE_VERSION
04394 
04395 _GLIBCXX_BEGIN_NAMESPACE_ALGO
04396 
04397   /**
04398    *  @brief Apply a function to every element of a sequence.
04399    *  @ingroup non_mutating_algorithms
04400    *  @param  __first  An input iterator.
04401    *  @param  __last   An input iterator.
04402    *  @param  __f      A unary function object.
04403    *  @return   @p __f (std::move(@p __f) in C++0x).
04404    *
04405    *  Applies the function object @p __f to each element in the range
04406    *  @p [first,last).  @p __f must not modify the order of the sequence.
04407    *  If @p __f has a return value it is ignored.
04408   */
04409   template<typename _InputIterator, typename _Function>
04410     _Function
04411     for_each(_InputIterator __first, _InputIterator __last, _Function __f)
04412     {
04413       // concept requirements
04414       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
04415       __glibcxx_requires_valid_range(__first, __last);
04416       for (; __first != __last; ++__first)
04417     __f(*__first);
04418       return _GLIBCXX_MOVE(__f);
04419     }
04420 
04421   /**
04422    *  @brief Find the first occurrence of a value in a sequence.
04423    *  @ingroup non_mutating_algorithms
04424    *  @param  __first  An input iterator.
04425    *  @param  __last   An input iterator.
04426    *  @param  __val    The value to find.
04427    *  @return   The first iterator @c i in the range @p [__first,__last)
04428    *  such that @c *i == @p __val, or @p __last if no such iterator exists.
04429   */
04430   template<typename _InputIterator, typename _Tp>
04431     inline _InputIterator
04432     find(_InputIterator __first, _InputIterator __last,
04433      const _Tp& __val)
04434     {
04435       // concept requirements
04436       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
04437       __glibcxx_function_requires(_EqualOpConcept<
04438         typename iterator_traits<_InputIterator>::value_type, _Tp>)
04439       __glibcxx_requires_valid_range(__first, __last);
04440       return std::__find(__first, __last, __val,
04441                  std::__iterator_category(__first));
04442     }
04443 
04444   /**
04445    *  @brief Find the first element in a sequence for which a
04446    *         predicate is true.
04447    *  @ingroup non_mutating_algorithms
04448    *  @param  __first  An input iterator.
04449    *  @param  __last   An input iterator.
04450    *  @param  __pred   A predicate.
04451    *  @return   The first iterator @c i in the range @p [__first,__last)
04452    *  such that @p __pred(*i) is true, or @p __last if no such iterator exists.
04453   */
04454   template<typename _InputIterator, typename _Predicate>
04455     inline _InputIterator
04456     find_if(_InputIterator __first, _InputIterator __last,
04457         _Predicate __pred)
04458     {
04459       // concept requirements
04460       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
04461       __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
04462           typename iterator_traits<_InputIterator>::value_type>)
04463       __glibcxx_requires_valid_range(__first, __last);
04464       return std::__find_if(__first, __last, __pred,
04465                 std::__iterator_category(__first));
04466     }
04467 
04468   /**
04469    *  @brief  Find element from a set in a sequence.
04470    *  @ingroup non_mutating_algorithms
04471    *  @param  __first1  Start of range to search.
04472    *  @param  __last1   End of range to search.
04473    *  @param  __first2  Start of match candidates.
04474    *  @param  __last2   End of match candidates.
04475    *  @return   The first iterator @c i in the range
04476    *  @p [__first1,__last1) such that @c *i == @p *(i2) such that i2 is an
04477    *  iterator in [__first2,__last2), or @p __last1 if no such iterator exists.
04478    *
04479    *  Searches the range @p [__first1,__last1) for an element that is
04480    *  equal to some element in the range [__first2,__last2).  If
04481    *  found, returns an iterator in the range [__first1,__last1),
04482    *  otherwise returns @p __last1.
04483   */
04484   template<typename _InputIterator, typename _ForwardIterator>
04485     _InputIterator
04486     find_first_of(_InputIterator __first1, _InputIterator __last1,
04487           _ForwardIterator __first2, _ForwardIterator __last2)
04488     {
04489       // concept requirements
04490       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
04491       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
04492       __glibcxx_function_requires(_EqualOpConcept<
04493         typename iterator_traits<_InputIterator>::value_type,
04494         typename iterator_traits<_ForwardIterator>::value_type>)
04495       __glibcxx_requires_valid_range(__first1, __last1);
04496       __glibcxx_requires_valid_range(__first2, __last2);
04497 
04498       for (; __first1 != __last1; ++__first1)
04499     for (_ForwardIterator __iter = __first2; __iter != __last2; ++__iter)
04500       if (*__first1 == *__iter)
04501         return __first1;
04502       return __last1;
04503     }
04504 
04505   /**
04506    *  @brief  Find element from a set in a sequence using a predicate.
04507    *  @ingroup non_mutating_algorithms
04508    *  @param  __first1  Start of range to search.
04509    *  @param  __last1   End of range to search.
04510    *  @param  __first2  Start of match candidates.
04511    *  @param  __last2   End of match candidates.
04512    *  @param  __comp    Predicate to use.
04513    *  @return   The first iterator @c i in the range
04514    *  @p [__first1,__last1) such that @c comp(*i, @p *(i2)) is true
04515    *  and i2 is an iterator in [__first2,__last2), or @p __last1 if no
04516    *  such iterator exists.
04517    *
04518 
04519    *  Searches the range @p [__first1,__last1) for an element that is
04520    *  equal to some element in the range [__first2,__last2).  If
04521    *  found, returns an iterator in the range [__first1,__last1),
04522    *  otherwise returns @p __last1.
04523   */
04524   template<typename _InputIterator, typename _ForwardIterator,
04525        typename _BinaryPredicate>
04526     _InputIterator
04527     find_first_of(_InputIterator __first1, _InputIterator __last1,
04528           _ForwardIterator __first2, _ForwardIterator __last2,
04529           _BinaryPredicate __comp)
04530     {
04531       // concept requirements
04532       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
04533       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
04534       __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
04535         typename iterator_traits<_InputIterator>::value_type,
04536         typename iterator_traits<_ForwardIterator>::value_type>)
04537       __glibcxx_requires_valid_range(__first1, __last1);
04538       __glibcxx_requires_valid_range(__first2, __last2);
04539 
04540       for (; __first1 != __last1; ++__first1)
04541     for (_ForwardIterator __iter = __first2; __iter != __last2; ++__iter)
04542       if (__comp(*__first1, *__iter))
04543         return __first1;
04544       return __last1;
04545     }
04546 
04547   /**
04548    *  @brief Find two adjacent values in a sequence that are equal.
04549    *  @ingroup non_mutating_algorithms
04550    *  @param  __first  A forward iterator.
04551    *  @param  __last   A forward iterator.
04552    *  @return   The first iterator @c i such that @c i and @c i+1 are both
04553    *  valid iterators in @p [__first,__last) and such that @c *i == @c *(i+1),
04554    *  or @p __last if no such iterator exists.
04555   */
04556   template<typename _ForwardIterator>
04557     _ForwardIterator
04558     adjacent_find(_ForwardIterator __first, _ForwardIterator __last)
04559     {
04560       // concept requirements
04561       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
04562       __glibcxx_function_requires(_EqualityComparableConcept<
04563         typename iterator_traits<_ForwardIterator>::value_type>)
04564       __glibcxx_requires_valid_range(__first, __last);
04565       if (__first == __last)
04566     return __last;
04567       _ForwardIterator __next = __first;
04568       while(++__next != __last)
04569     {
04570       if (*__first == *__next)
04571         return __first;
04572       __first = __next;
04573     }
04574       return __last;
04575     }
04576 
04577   /**
04578    *  @brief Find two adjacent values in a sequence using a predicate.
04579    *  @ingroup non_mutating_algorithms
04580    *  @param  __first         A forward iterator.
04581    *  @param  __last          A forward iterator.
04582    *  @param  __binary_pred   A binary predicate.
04583    *  @return   The first iterator @c i such that @c i and @c i+1 are both
04584    *  valid iterators in @p [__first,__last) and such that
04585    *  @p __binary_pred(*i,*(i+1)) is true, or @p __last if no such iterator
04586    *  exists.
04587   */
04588   template<typename _ForwardIterator, typename _BinaryPredicate>
04589     _ForwardIterator
04590     adjacent_find(_ForwardIterator __first, _ForwardIterator __last,
04591           _BinaryPredicate __binary_pred)
04592     {
04593       // concept requirements
04594       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
04595       __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
04596         typename iterator_traits<_ForwardIterator>::value_type,
04597         typename iterator_traits<_ForwardIterator>::value_type>)
04598       __glibcxx_requires_valid_range(__first, __last);
04599       if (__first == __last)
04600     return __last;
04601       _ForwardIterator __next = __first;
04602       while(++__next != __last)
04603     {
04604       if (__binary_pred(*__first, *__next))
04605         return __first;
04606       __first = __next;
04607     }
04608       return __last;
04609     }
04610 
04611   /**
04612    *  @brief Count the number of copies of a value in a sequence.
04613    *  @ingroup non_mutating_algorithms
04614    *  @param  __first  An input iterator.
04615    *  @param  __last   An input iterator.
04616    *  @param  __value  The value to be counted.
04617    *  @return   The number of iterators @c i in the range @p [__first,__last)
04618    *  for which @c *i == @p __value
04619   */
04620   template<typename _InputIterator, typename _Tp>
04621     typename iterator_traits<_InputIterator>::difference_type
04622     count(_InputIterator __first, _InputIterator __last, const _Tp& __value)
04623     {
04624       // concept requirements
04625       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
04626       __glibcxx_function_requires(_EqualOpConcept<
04627     typename iterator_traits<_InputIterator>::value_type, _Tp>)
04628       __glibcxx_requires_valid_range(__first, __last);
04629       typename iterator_traits<_InputIterator>::difference_type __n = 0;
04630       for (; __first != __last; ++__first)
04631     if (*__first == __value)
04632       ++__n;
04633       return __n;
04634     }
04635 
04636   /**
04637    *  @brief Count the elements of a sequence for which a predicate is true.
04638    *  @ingroup non_mutating_algorithms
04639    *  @param  __first  An input iterator.
04640    *  @param  __last   An input iterator.
04641    *  @param  __pred   A predicate.
04642    *  @return   The number of iterators @c i in the range @p [__first,__last)
04643    *  for which @p __pred(*i) is true.
04644   */
04645   template<typename _InputIterator, typename _Predicate>
04646     typename iterator_traits<_InputIterator>::difference_type
04647     count_if(_InputIterator __first, _InputIterator __last, _Predicate __pred)
04648     {
04649       // concept requirements
04650       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
04651       __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
04652         typename iterator_traits<_InputIterator>::value_type>)
04653       __glibcxx_requires_valid_range(__first, __last);
04654       typename iterator_traits<_InputIterator>::difference_type __n = 0;
04655       for (; __first != __last; ++__first)
04656     if (__pred(*__first))
04657       ++__n;
04658       return __n;
04659     }
04660 
04661   /**
04662    *  @brief Search a sequence for a matching sub-sequence.
04663    *  @ingroup non_mutating_algorithms
04664    *  @param  __first1  A forward iterator.
04665    *  @param  __last1   A forward iterator.
04666    *  @param  __first2  A forward iterator.
04667    *  @param  __last2   A forward iterator.
04668    *  @return The first iterator @c i in the range @p
04669    *  [__first1,__last1-(__last2-__first2)) such that @c *(i+N) == @p
04670    *  *(__first2+N) for each @c N in the range @p
04671    *  [0,__last2-__first2), or @p __last1 if no such iterator exists.
04672    *
04673    *  Searches the range @p [__first1,__last1) for a sub-sequence that
04674    *  compares equal value-by-value with the sequence given by @p
04675    *  [__first2,__last2) and returns an iterator to the first element
04676    *  of the sub-sequence, or @p __last1 if the sub-sequence is not
04677    *  found.
04678    *
04679    *  Because the sub-sequence must lie completely within the range @p
04680    *  [__first1,__last1) it must start at a position less than @p
04681    *  __last1-(__last2-__first2) where @p __last2-__first2 is the
04682    *  length of the sub-sequence.
04683    *
04684    *  This means that the returned iterator @c i will be in the range
04685    *  @p [__first1,__last1-(__last2-__first2))
04686   */
04687   template<typename _ForwardIterator1, typename _ForwardIterator2>
04688     _ForwardIterator1
04689     search(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
04690        _ForwardIterator2 __first2, _ForwardIterator2 __last2)
04691     {
04692       // concept requirements
04693       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator1>)
04694       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator2>)
04695       __glibcxx_function_requires(_EqualOpConcept<
04696         typename iterator_traits<_ForwardIterator1>::value_type,
04697         typename iterator_traits<_ForwardIterator2>::value_type>)
04698       __glibcxx_requires_valid_range(__first1, __last1);
04699       __glibcxx_requires_valid_range(__first2, __last2);
04700 
04701       // Test for empty ranges
04702       if (__first1 == __last1 || __first2 == __last2)
04703     return __first1;
04704 
04705       // Test for a pattern of length 1.
04706       _ForwardIterator2 __p1(__first2);
04707       if (++__p1 == __last2)
04708     return _GLIBCXX_STD_A::find(__first1, __last1, *__first2);
04709 
04710       // General case.
04711       _ForwardIterator2 __p;
04712       _ForwardIterator1 __current = __first1;
04713 
04714       for (;;)
04715     {
04716       __first1 = _GLIBCXX_STD_A::find(__first1, __last1, *__first2);
04717       if (__first1 == __last1)
04718         return __last1;
04719 
04720       __p = __p1;
04721       __current = __first1;
04722       if (++__current == __last1)
04723         return __last1;
04724 
04725       while (*__current == *__p)
04726         {
04727           if (++__p == __last2)
04728         return __first1;
04729           if (++__current == __last1)
04730         return __last1;
04731         }
04732       ++__first1;
04733     }
04734       return __first1;
04735     }
04736 
04737   /**
04738    *  @brief Search a sequence for a matching sub-sequence using a predicate.
04739    *  @ingroup non_mutating_algorithms
04740    *  @param  __first1     A forward iterator.
04741    *  @param  __last1      A forward iterator.
04742    *  @param  __first2     A forward iterator.
04743    *  @param  __last2      A forward iterator.
04744    *  @param  __predicate  A binary predicate.
04745    *  @return   The first iterator @c i in the range
04746    *  @p [__first1,__last1-(__last2-__first2)) such that
04747    *  @p __predicate(*(i+N),*(__first2+N)) is true for each @c N in the range
04748    *  @p [0,__last2-__first2), or @p __last1 if no such iterator exists.
04749    *
04750    *  Searches the range @p [__first1,__last1) for a sub-sequence that
04751    *  compares equal value-by-value with the sequence given by @p
04752    *  [__first2,__last2), using @p __predicate to determine equality,
04753    *  and returns an iterator to the first element of the
04754    *  sub-sequence, or @p __last1 if no such iterator exists.
04755    *
04756    *  @see search(_ForwardIter1, _ForwardIter1, _ForwardIter2, _ForwardIter2)
04757   */
04758   template<typename _ForwardIterator1, typename _ForwardIterator2,
04759        typename _BinaryPredicate>
04760     _ForwardIterator1
04761     search(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
04762        _ForwardIterator2 __first2, _ForwardIterator2 __last2,
04763        _BinaryPredicate  __predicate)
04764     {
04765       // concept requirements
04766       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator1>)
04767       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator2>)
04768       __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
04769         typename iterator_traits<_ForwardIterator1>::value_type,
04770         typename iterator_traits<_ForwardIterator2>::value_type>)
04771       __glibcxx_requires_valid_range(__first1, __last1);
04772       __glibcxx_requires_valid_range(__first2, __last2);
04773 
04774       // Test for empty ranges
04775       if (__first1 == __last1 || __first2 == __last2)
04776     return __first1;
04777 
04778       // Test for a pattern of length 1.
04779       _ForwardIterator2 __p1(__first2);
04780       if (++__p1 == __last2)
04781     {
04782       while (__first1 != __last1
04783          && !bool(__predicate(*__first1, *__first2)))
04784         ++__first1;
04785       return __first1;
04786     }
04787 
04788       // General case.
04789       _ForwardIterator2 __p;
04790       _ForwardIterator1 __current = __first1;
04791 
04792       for (;;)
04793     {
04794       while (__first1 != __last1
04795          && !bool(__predicate(*__first1, *__first2)))
04796         ++__first1;
04797       if (__first1 == __last1)
04798         return __last1;
04799 
04800       __p = __p1;
04801       __current = __first1;
04802       if (++__current == __last1)
04803         return __last1;
04804 
04805       while (__predicate(*__current, *__p))
04806         {
04807           if (++__p == __last2)
04808         return __first1;
04809           if (++__current == __last1)
04810         return __last1;
04811         }
04812       ++__first1;
04813     }
04814       return __first1;
04815     }
04816 
04817 
04818   /**
04819    *  @brief Search a sequence for a number of consecutive values.
04820    *  @ingroup non_mutating_algorithms
04821    *  @param  __first  A forward iterator.
04822    *  @param  __last   A forward iterator.
04823    *  @param  __count  The number of consecutive values.
04824    *  @param  __val    The value to find.
04825    *  @return The first iterator @c i in the range @p
04826    *  [__first,__last-__count) such that @c *(i+N) == @p __val for
04827    *  each @c N in the range @p [0,__count), or @p __last if no such
04828    *  iterator exists.
04829    *
04830    *  Searches the range @p [__first,__last) for @p count consecutive elements
04831    *  equal to @p __val.
04832   */
04833   template<typename _ForwardIterator, typename _Integer, typename _Tp>
04834     _ForwardIterator
04835     search_n(_ForwardIterator __first, _ForwardIterator __last,
04836          _Integer __count, const _Tp& __val)
04837     {
04838       // concept requirements
04839       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
04840       __glibcxx_function_requires(_EqualOpConcept<
04841     typename iterator_traits<_ForwardIterator>::value_type, _Tp>)
04842       __glibcxx_requires_valid_range(__first, __last);
04843 
04844       if (__count <= 0)
04845     return __first;
04846       if (__count == 1)
04847     return _GLIBCXX_STD_A::find(__first, __last, __val);
04848       return std::__search_n(__first, __last, __count, __val,
04849                  std::__iterator_category(__first));
04850     }
04851 
04852 
04853   /**
04854    *  @brief Search a sequence for a number of consecutive values using a
04855    *         predicate.
04856    *  @ingroup non_mutating_algorithms
04857    *  @param  __first        A forward iterator.
04858    *  @param  __last         A forward iterator.
04859    *  @param  __count        The number of consecutive values.
04860    *  @param  __val          The value to find.
04861    *  @param  __binary_pred  A binary predicate.
04862    *  @return The first iterator @c i in the range @p
04863    *  [__first,__last-__count) such that @p
04864    *  __binary_pred(*(i+N),__val) is true for each @c N in the range
04865    *  @p [0,__count), or @p __last if no such iterator exists.
04866    *
04867    *  Searches the range @p [__first,__last) for @p __count
04868    *  consecutive elements for which the predicate returns true.
04869   */
04870   template<typename _ForwardIterator, typename _Integer, typename _Tp,
04871            typename _BinaryPredicate>
04872     _ForwardIterator
04873     search_n(_ForwardIterator __first, _ForwardIterator __last,
04874          _Integer __count, const _Tp& __val,
04875          _BinaryPredicate __binary_pred)
04876     {
04877       // concept requirements
04878       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
04879       __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
04880         typename iterator_traits<_ForwardIterator>::value_type, _Tp>)
04881       __glibcxx_requires_valid_range(__first, __last);
04882 
04883       if (__count <= 0)
04884     return __first;
04885       if (__count == 1)
04886     {
04887       while (__first != __last && !bool(__binary_pred(*__first, __val)))
04888         ++__first;
04889       return __first;
04890     }
04891       return std::__search_n(__first, __last, __count, __val, __binary_pred,
04892                  std::__iterator_category(__first));
04893     }
04894 
04895 
04896   /**
04897    *  @brief Perform an operation on a sequence.
04898    *  @ingroup mutating_algorithms
04899    *  @param  __first     An input iterator.
04900    *  @param  __last      An input iterator.
04901    *  @param  __result    An output iterator.
04902    *  @param  __unary_op  A unary operator.
04903    *  @return   An output iterator equal to @p __result+(__last-__first).
04904    *
04905    *  Applies the operator to each element in the input range and assigns
04906    *  the results to successive elements of the output sequence.
04907    *  Evaluates @p *(__result+N)=unary_op(*(__first+N)) for each @c N in the
04908    *  range @p [0,__last-__first).
04909    *
04910    *  @p unary_op must not alter its argument.
04911   */
04912   template<typename _InputIterator, typename _OutputIterator,
04913        typename _UnaryOperation>
04914     _OutputIterator
04915     transform(_InputIterator __first, _InputIterator __last,
04916           _OutputIterator __result, _UnaryOperation __unary_op)
04917     {
04918       // concept requirements
04919       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
04920       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
04921             // "the type returned by a _UnaryOperation"
04922             __typeof__(__unary_op(*__first))>)
04923       __glibcxx_requires_valid_range(__first, __last);
04924 
04925       for (; __first != __last; ++__first, ++__result)
04926     *__result = __unary_op(*__first);
04927       return __result;
04928     }
04929 
04930   /**
04931    *  @brief Perform an operation on corresponding elements of two sequences.
04932    *  @ingroup mutating_algorithms
04933    *  @param  __first1     An input iterator.
04934    *  @param  __last1      An input iterator.
04935    *  @param  __first2     An input iterator.
04936    *  @param  __result     An output iterator.
04937    *  @param  __binary_op  A binary operator.
04938    *  @return   An output iterator equal to @p result+(last-first).
04939    *
04940    *  Applies the operator to the corresponding elements in the two
04941    *  input ranges and assigns the results to successive elements of the
04942    *  output sequence.
04943    *  Evaluates @p
04944    *  *(__result+N)=__binary_op(*(__first1+N),*(__first2+N)) for each
04945    *  @c N in the range @p [0,__last1-__first1).
04946    *
04947    *  @p binary_op must not alter either of its arguments.
04948   */
04949   template<typename _InputIterator1, typename _InputIterator2,
04950        typename _OutputIterator, typename _BinaryOperation>
04951     _OutputIterator
04952     transform(_InputIterator1 __first1, _InputIterator1 __last1,
04953           _InputIterator2 __first2, _OutputIterator __result,
04954           _BinaryOperation __binary_op)
04955     {
04956       // concept requirements
04957       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
04958       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
04959       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
04960             // "the type returned by a _BinaryOperation"
04961             __typeof__(__binary_op(*__first1,*__first2))>)
04962       __glibcxx_requires_valid_range(__first1, __last1);
04963 
04964       for (; __first1 != __last1; ++__first1, ++__first2, ++__result)
04965     *__result = __binary_op(*__first1, *__first2);
04966       return __result;
04967     }
04968 
04969   /**
04970    *  @brief Replace each occurrence of one value in a sequence with another
04971    *         value.
04972    *  @ingroup mutating_algorithms
04973    *  @param  __first      A forward iterator.
04974    *  @param  __last       A forward iterator.
04975    *  @param  __old_value  The value to be replaced.
04976    *  @param  __new_value  The replacement value.
04977    *  @return   replace() returns no value.
04978    *
04979    *  For each iterator @c i in the range @p [__first,__last) if @c *i ==
04980    *  @p __old_value then the assignment @c *i = @p __new_value is performed.
04981   */
04982   template<typename _ForwardIterator, typename _Tp>
04983     void
04984     replace(_ForwardIterator __first, _ForwardIterator __last,
04985         const _Tp& __old_value, const _Tp& __new_value)
04986     {
04987       // concept requirements
04988       __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
04989                   _ForwardIterator>)
04990       __glibcxx_function_requires(_EqualOpConcept<
04991         typename iterator_traits<_ForwardIterator>::value_type, _Tp>)
04992       __glibcxx_function_requires(_ConvertibleConcept<_Tp,
04993         typename iterator_traits<_ForwardIterator>::value_type>)
04994       __glibcxx_requires_valid_range(__first, __last);
04995 
04996       for (; __first != __last; ++__first)
04997     if (*__first == __old_value)
04998       *__first = __new_value;
04999     }
05000 
05001   /**
05002    *  @brief Replace each value in a sequence for which a predicate returns
05003    *         true with another value.
05004    *  @ingroup mutating_algorithms
05005    *  @param  __first      A forward iterator.
05006    *  @param  __last       A forward iterator.
05007    *  @param  __pred       A predicate.
05008    *  @param  __new_value  The replacement value.
05009    *  @return   replace_if() returns no value.
05010    *
05011    *  For each iterator @c i in the range @p [__first,__last) if @p __pred(*i)
05012    *  is true then the assignment @c *i = @p __new_value is performed.
05013   */
05014   template<typename _ForwardIterator, typename _Predicate, typename _Tp>
05015     void
05016     replace_if(_ForwardIterator __first, _ForwardIterator __last,
05017            _Predicate __pred, const _Tp& __new_value)
05018     {
05019       // concept requirements
05020       __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
05021                   _ForwardIterator>)
05022       __glibcxx_function_requires(_ConvertibleConcept<_Tp,
05023         typename iterator_traits<_ForwardIterator>::value_type>)
05024       __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
05025         typename iterator_traits<_ForwardIterator>::value_type>)
05026       __glibcxx_requires_valid_range(__first, __last);
05027 
05028       for (; __first != __last; ++__first)
05029     if (__pred(*__first))
05030       *__first = __new_value;
05031     }
05032 
05033   /**
05034    *  @brief Assign the result of a function object to each value in a
05035    *         sequence.
05036    *  @ingroup mutating_algorithms
05037    *  @param  __first  A forward iterator.
05038    *  @param  __last   A forward iterator.
05039    *  @param  __gen    A function object taking no arguments and returning
05040    *                 std::iterator_traits<_ForwardIterator>::value_type
05041    *  @return   generate() returns no value.
05042    *
05043    *  Performs the assignment @c *i = @p __gen() for each @c i in the range
05044    *  @p [__first,__last).
05045   */
05046   template<typename _ForwardIterator, typename _Generator>
05047     void
05048     generate(_ForwardIterator __first, _ForwardIterator __last,
05049          _Generator __gen)
05050     {
05051       // concept requirements
05052       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
05053       __glibcxx_function_requires(_GeneratorConcept<_Generator,
05054         typename iterator_traits<_ForwardIterator>::value_type>)
05055       __glibcxx_requires_valid_range(__first, __last);
05056 
05057       for (; __first != __last; ++__first)
05058     *__first = __gen();
05059     }
05060 
05061   /**
05062    *  @brief Assign the result of a function object to each value in a
05063    *         sequence.
05064    *  @ingroup mutating_algorithms
05065    *  @param  __first  A forward iterator.
05066    *  @param  __n      The length of the sequence.
05067    *  @param  __gen    A function object taking no arguments and returning
05068    *                 std::iterator_traits<_ForwardIterator>::value_type
05069    *  @return   The end of the sequence, @p __first+__n
05070    *
05071    *  Performs the assignment @c *i = @p __gen() for each @c i in the range
05072    *  @p [__first,__first+__n).
05073    *
05074    *  _GLIBCXX_RESOLVE_LIB_DEFECTS
05075    *  DR 865. More algorithms that throw away information
05076   */
05077   template<typename _OutputIterator, typename _Size, typename _Generator>
05078     _OutputIterator
05079     generate_n(_OutputIterator __first, _Size __n, _Generator __gen)
05080     {
05081       // concept requirements
05082       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
05083             // "the type returned by a _Generator"
05084             __typeof__(__gen())>)
05085 
05086       for (__decltype(__n + 0) __niter = __n;
05087        __niter > 0; --__niter, ++__first)
05088     *__first = __gen();
05089       return __first;
05090     }
05091 
05092 
05093   /**
05094    *  @brief Copy a sequence, removing consecutive duplicate values.
05095    *  @ingroup mutating_algorithms
05096    *  @param  __first   An input iterator.
05097    *  @param  __last    An input iterator.
05098    *  @param  __result  An output iterator.
05099    *  @return   An iterator designating the end of the resulting sequence.
05100    *
05101    *  Copies each element in the range @p [__first,__last) to the range
05102    *  beginning at @p __result, except that only the first element is copied
05103    *  from groups of consecutive elements that compare equal.
05104    *  unique_copy() is stable, so the relative order of elements that are
05105    *  copied is unchanged.
05106    *
05107    *  _GLIBCXX_RESOLVE_LIB_DEFECTS
05108    *  DR 241. Does unique_copy() require CopyConstructible and Assignable?
05109    *  
05110    *  _GLIBCXX_RESOLVE_LIB_DEFECTS
05111    *  DR 538. 241 again: Does unique_copy() require CopyConstructible and 
05112    *  Assignable?
05113   */
05114   template<typename _InputIterator, typename _OutputIterator>
05115     inline _OutputIterator
05116     unique_copy(_InputIterator __first, _InputIterator __last,
05117         _OutputIterator __result)
05118     {
05119       // concept requirements
05120       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
05121       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
05122         typename iterator_traits<_InputIterator>::value_type>)
05123       __glibcxx_function_requires(_EqualityComparableConcept<
05124         typename iterator_traits<_InputIterator>::value_type>)
05125       __glibcxx_requires_valid_range(__first, __last);
05126 
05127       if (__first == __last)
05128     return __result;
05129       return std::__unique_copy(__first, __last, __result,
05130                 std::__iterator_category(__first),
05131                 std::__iterator_category(__result));
05132     }
05133 
05134   /**
05135    *  @brief Copy a sequence, removing consecutive values using a predicate.
05136    *  @ingroup mutating_algorithms
05137    *  @param  __first        An input iterator.
05138    *  @param  __last         An input iterator.
05139    *  @param  __result       An output iterator.
05140    *  @param  __binary_pred  A binary predicate.
05141    *  @return   An iterator designating the end of the resulting sequence.
05142    *
05143    *  Copies each element in the range @p [__first,__last) to the range
05144    *  beginning at @p __result, except that only the first element is copied
05145    *  from groups of consecutive elements for which @p __binary_pred returns
05146    *  true.
05147    *  unique_copy() is stable, so the relative order of elements that are
05148    *  copied is unchanged.
05149    *
05150    *  _GLIBCXX_RESOLVE_LIB_DEFECTS
05151    *  DR 241. Does unique_copy() require CopyConstructible and Assignable?
05152   */
05153   template<typename _InputIterator, typename _OutputIterator,
05154        typename _BinaryPredicate>
05155     inline _OutputIterator
05156     unique_copy(_InputIterator __first, _InputIterator __last,
05157         _OutputIterator __result,
05158         _BinaryPredicate __binary_pred)
05159     {
05160       // concept requirements -- predicates checked later
05161       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
05162       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
05163         typename iterator_traits<_InputIterator>::value_type>)
05164       __glibcxx_requires_valid_range(__first, __last);
05165 
05166       if (__first == __last)
05167     return __result;
05168       return std::__unique_copy(__first, __last, __result, __binary_pred,
05169                 std::__iterator_category(__first),
05170                 std::__iterator_category(__result));
05171     }
05172 
05173 
05174   /**
05175    *  @brief Randomly shuffle the elements of a sequence.
05176    *  @ingroup mutating_algorithms
05177    *  @param  __first   A forward iterator.
05178    *  @param  __last    A forward iterator.
05179    *  @return  Nothing.
05180    *
05181    *  Reorder the elements in the range @p [__first,__last) using a random
05182    *  distribution, so that every possible ordering of the sequence is
05183    *  equally likely.
05184   */
05185   template<typename _RandomAccessIterator>
05186     inline void
05187     random_shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last)
05188     {
05189       // concept requirements
05190       __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
05191         _RandomAccessIterator>)
05192       __glibcxx_requires_valid_range(__first, __last);
05193 
05194       if (__first != __last)
05195     for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i)
05196       {
05197         _RandomAccessIterator __j = __first
05198                     + std::rand() % ((__i - __first) + 1);
05199         if (__i != __j)
05200           std::iter_swap(__i, __j);
05201       }
05202     }
05203 
05204   /**
05205    *  @brief Shuffle the elements of a sequence using a random number
05206    *         generator.
05207    *  @ingroup mutating_algorithms
05208    *  @param  __first   A forward iterator.
05209    *  @param  __last    A forward iterator.
05210    *  @param  __rand    The RNG functor or function.
05211    *  @return  Nothing.
05212    *
05213    *  Reorders the elements in the range @p [__first,__last) using @p __rand to
05214    *  provide a random distribution. Calling @p __rand(N) for a positive
05215    *  integer @p N should return a randomly chosen integer from the
05216    *  range [0,N).
05217   */
05218   template<typename _RandomAccessIterator, typename _RandomNumberGenerator>
05219     void
05220     random_shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last,
05221 #if __cplusplus >= 201103L
05222            _RandomNumberGenerator&& __rand)
05223 #else
05224            _RandomNumberGenerator& __rand)
05225 #endif
05226     {
05227       // concept requirements
05228       __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
05229         _RandomAccessIterator>)
05230       __glibcxx_requires_valid_range(__first, __last);
05231 
05232       if (__first == __last)
05233     return;
05234       for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i)
05235     {
05236       _RandomAccessIterator __j = __first + __rand((__i - __first) + 1);
05237       if (__i != __j)
05238         std::iter_swap(__i, __j);
05239     }
05240     }
05241 
05242 
05243   /**
05244    *  @brief Move elements for which a predicate is true to the beginning
05245    *         of a sequence.
05246    *  @ingroup mutating_algorithms
05247    *  @param  __first   A forward iterator.
05248    *  @param  __last    A forward iterator.
05249    *  @param  __pred    A predicate functor.
05250    *  @return  An iterator @p middle such that @p __pred(i) is true for each
05251    *  iterator @p i in the range @p [__first,middle) and false for each @p i
05252    *  in the range @p [middle,__last).
05253    *
05254    *  @p __pred must not modify its operand. @p partition() does not preserve
05255    *  the relative ordering of elements in each group, use
05256    *  @p stable_partition() if this is needed.
05257   */
05258   template<typename _ForwardIterator, typename _Predicate>
05259     inline _ForwardIterator
05260     partition(_ForwardIterator __first, _ForwardIterator __last,
05261           _Predicate   __pred)
05262     {
05263       // concept requirements
05264       __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
05265                   _ForwardIterator>)
05266       __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
05267         typename iterator_traits<_ForwardIterator>::value_type>)
05268       __glibcxx_requires_valid_range(__first, __last);
05269 
05270       return std::__partition(__first, __last, __pred,
05271                   std::__iterator_category(__first));
05272     }
05273 
05274 
05275 
05276   /**
05277    *  @brief Sort the smallest elements of a sequence.
05278    *  @ingroup sorting_algorithms
05279    *  @param  __first   An iterator.
05280    *  @param  __middle  Another iterator.
05281    *  @param  __last    Another iterator.
05282    *  @return  Nothing.
05283    *
05284    *  Sorts the smallest @p (__middle-__first) elements in the range
05285    *  @p [first,last) and moves them to the range @p [__first,__middle). The
05286    *  order of the remaining elements in the range @p [__middle,__last) is
05287    *  undefined.
05288    *  After the sort if @e i and @e j are iterators in the range
05289    *  @p [__first,__middle) such that i precedes j and @e k is an iterator in
05290    *  the range @p [__middle,__last) then *j<*i and *k<*i are both false.
05291   */
05292   template<typename _RandomAccessIterator>
05293     inline void
05294     partial_sort(_RandomAccessIterator __first,
05295          _RandomAccessIterator __middle,
05296          _RandomAccessIterator __last)
05297     {
05298       typedef typename iterator_traits<_RandomAccessIterator>::value_type
05299     _ValueType;
05300 
05301       // concept requirements
05302       __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
05303         _RandomAccessIterator>)
05304       __glibcxx_function_requires(_LessThanComparableConcept<_ValueType>)
05305       __glibcxx_requires_valid_range(__first, __middle);
05306       __glibcxx_requires_valid_range(__middle, __last);
05307 
05308       std::__heap_select(__first, __middle, __last);
05309       std::sort_heap(__first, __middle);
05310     }
05311 
05312   /**
05313    *  @brief Sort the smallest elements of a sequence using a predicate
05314    *         for comparison.
05315    *  @ingroup sorting_algorithms
05316    *  @param  __first   An iterator.
05317    *  @param  __middle  Another iterator.
05318    *  @param  __last    Another iterator.
05319    *  @param  __comp    A comparison functor.
05320    *  @return  Nothing.
05321    *
05322    *  Sorts the smallest @p (__middle-__first) elements in the range
05323    *  @p [__first,__last) and moves them to the range @p [__first,__middle). The
05324    *  order of the remaining elements in the range @p [__middle,__last) is
05325    *  undefined.
05326    *  After the sort if @e i and @e j are iterators in the range
05327    *  @p [__first,__middle) such that i precedes j and @e k is an iterator in
05328    *  the range @p [__middle,__last) then @p *__comp(j,*i) and @p __comp(*k,*i)
05329    *  are both false.
05330   */
05331   template<typename _RandomAccessIterator, typename _Compare>
05332     inline void
05333     partial_sort(_RandomAccessIterator __first,
05334          _RandomAccessIterator __middle,
05335          _RandomAccessIterator __last,
05336          _Compare __comp)
05337     {
05338       typedef typename iterator_traits<_RandomAccessIterator>::value_type
05339     _ValueType;
05340 
05341       // concept requirements
05342       __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
05343         _RandomAccessIterator>)
05344       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
05345                   _ValueType, _ValueType>)
05346       __glibcxx_requires_valid_range(__first, __middle);
05347       __glibcxx_requires_valid_range(__middle, __last);
05348 
05349       std::__heap_select(__first, __middle, __last, __comp);
05350       std::sort_heap(__first, __middle, __comp);
05351     }
05352 
05353   /**
05354    *  @brief Sort a sequence just enough to find a particular position.
05355    *  @ingroup sorting_algorithms
05356    *  @param  __first   An iterator.
05357    *  @param  __nth     Another iterator.
05358    *  @param  __last    Another iterator.
05359    *  @return  Nothing.
05360    *
05361    *  Rearranges the elements in the range @p [__first,__last) so that @p *__nth
05362    *  is the same element that would have been in that position had the
05363    *  whole sequence been sorted. The elements either side of @p *__nth are
05364    *  not completely sorted, but for any iterator @e i in the range
05365    *  @p [__first,__nth) and any iterator @e j in the range @p [__nth,__last) it
05366    *  holds that *j < *i is false.
05367   */
05368   template<typename _RandomAccessIterator>
05369     inline void
05370     nth_element(_RandomAccessIterator __first, _RandomAccessIterator __nth,
05371         _RandomAccessIterator __last)
05372     {
05373       typedef typename iterator_traits<_RandomAccessIterator>::value_type
05374     _ValueType;
05375 
05376       // concept requirements
05377       __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
05378                   _RandomAccessIterator>)
05379       __glibcxx_function_requires(_LessThanComparableConcept<_ValueType>)
05380       __glibcxx_requires_valid_range(__first, __nth);
05381       __glibcxx_requires_valid_range(__nth, __last);
05382 
05383       if (__first == __last || __nth == __last)
05384     return;
05385 
05386       std::__introselect(__first, __nth, __last,
05387              std::__lg(__last - __first) * 2);
05388     }
05389 
05390   /**
05391    *  @brief Sort a sequence just enough to find a particular position
05392    *         using a predicate for comparison.
05393    *  @ingroup sorting_algorithms
05394    *  @param  __first   An iterator.
05395    *  @param  __nth     Another iterator.
05396    *  @param  __last    Another iterator.
05397    *  @param  __comp    A comparison functor.
05398    *  @return  Nothing.
05399    *
05400    *  Rearranges the elements in the range @p [__first,__last) so that @p *__nth
05401    *  is the same element that would have been in that position had the
05402    *  whole sequence been sorted. The elements either side of @p *__nth are
05403    *  not completely sorted, but for any iterator @e i in the range
05404    *  @p [__first,__nth) and any iterator @e j in the range @p [__nth,__last) it
05405    *  holds that @p __comp(*j,*i) is false.
05406   */
05407   template<typename _RandomAccessIterator, typename _Compare>
05408     inline void
05409     nth_element(_RandomAccessIterator __first, _RandomAccessIterator __nth,
05410         _RandomAccessIterator __last, _Compare __comp)
05411     {
05412       typedef typename iterator_traits<_RandomAccessIterator>::value_type
05413     _ValueType;
05414 
05415       // concept requirements
05416       __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
05417                   _RandomAccessIterator>)
05418       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
05419                   _ValueType, _ValueType>)
05420       __glibcxx_requires_valid_range(__first, __nth);
05421       __glibcxx_requires_valid_range(__nth, __last);
05422 
05423       if (__first == __last || __nth == __last)
05424     return;
05425 
05426       std::__introselect(__first, __nth, __last,
05427              std::__lg(__last - __first) * 2, __comp);
05428     }
05429 
05430 
05431   /**
05432    *  @brief Sort the elements of a sequence.
05433    *  @ingroup sorting_algorithms
05434    *  @param  __first   An iterator.
05435    *  @param  __last    Another iterator.
05436    *  @return  Nothing.
05437    *
05438    *  Sorts the elements in the range @p [__first,__last) in ascending order,
05439    *  such that for each iterator @e i in the range @p [__first,__last-1),  
05440    *  *(i+1)<*i is false.
05441    *
05442    *  The relative ordering of equivalent elements is not preserved, use
05443    *  @p stable_sort() if this is needed.
05444   */
05445   template<typename _RandomAccessIterator>
05446     inline void
05447     sort(_RandomAccessIterator __first, _RandomAccessIterator __last)
05448     {
05449       typedef typename iterator_traits<_RandomAccessIterator>::value_type
05450     _ValueType;
05451 
05452       // concept requirements
05453       __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
05454         _RandomAccessIterator>)
05455       __glibcxx_function_requires(_LessThanComparableConcept<_ValueType>)
05456       __glibcxx_requires_valid_range(__first, __last);
05457 
05458       if (__first != __last)
05459     {
05460       std::__introsort_loop(__first, __last,
05461                 std::__lg(__last - __first) * 2);
05462       std::__final_insertion_sort(__first, __last);
05463     }
05464     }
05465 
05466   /**
05467    *  @brief Sort the elements of a sequence using a predicate for comparison.
05468    *  @ingroup sorting_algorithms
05469    *  @param  __first   An iterator.
05470    *  @param  __last    Another iterator.
05471    *  @param  __comp    A comparison functor.
05472    *  @return  Nothing.
05473    *
05474    *  Sorts the elements in the range @p [__first,__last) in ascending order,
05475    *  such that @p __comp(*(i+1),*i) is false for every iterator @e i in the
05476    *  range @p [__first,__last-1).
05477    *
05478    *  The relative ordering of equivalent elements is not preserved, use
05479    *  @p stable_sort() if this is needed.
05480   */
05481   template<typename _RandomAccessIterator, typename _Compare>
05482     inline void
05483     sort(_RandomAccessIterator __first, _RandomAccessIterator __last,
05484      _Compare __comp)
05485     {
05486       typedef typename iterator_traits<_RandomAccessIterator>::value_type
05487     _ValueType;
05488 
05489       // concept requirements
05490       __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
05491         _RandomAccessIterator>)
05492       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, _ValueType,
05493                   _ValueType>)
05494       __glibcxx_requires_valid_range(__first, __last);
05495 
05496       if (__first != __last)
05497     {
05498       std::__introsort_loop(__first, __last,
05499                 std::__lg(__last - __first) * 2, __comp);
05500       std::__final_insertion_sort(__first, __last, __comp);
05501     }
05502     }
05503 
05504   /**
05505    *  @brief Merges two sorted ranges.
05506    *  @ingroup sorting_algorithms
05507    *  @param  __first1  An iterator.
05508    *  @param  __first2  Another iterator.
05509    *  @param  __last1   Another iterator.
05510    *  @param  __last2   Another iterator.
05511    *  @param  __result  An iterator pointing to the end of the merged range.
05512    *  @return         An iterator pointing to the first element <em>not less
05513    *                  than</em> @e val.
05514    *
05515    *  Merges the ranges @p [__first1,__last1) and @p [__first2,__last2) into
05516    *  the sorted range @p [__result, __result + (__last1-__first1) +
05517    *  (__last2-__first2)).  Both input ranges must be sorted, and the
05518    *  output range must not overlap with either of the input ranges.
05519    *  The sort is @e stable, that is, for equivalent elements in the
05520    *  two ranges, elements from the first range will always come
05521    *  before elements from the second.
05522   */
05523   template<typename _InputIterator1, typename _InputIterator2,
05524        typename _OutputIterator>
05525     _OutputIterator
05526     merge(_InputIterator1 __first1, _InputIterator1 __last1,
05527       _InputIterator2 __first2, _InputIterator2 __last2,
05528       _OutputIterator __result)
05529     {
05530       typedef typename iterator_traits<_InputIterator1>::value_type
05531     _ValueType1;
05532       typedef typename iterator_traits<_InputIterator2>::value_type
05533     _ValueType2;
05534 
05535       // concept requirements
05536       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
05537       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
05538       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
05539                   _ValueType1>)
05540       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
05541                   _ValueType2>)
05542       __glibcxx_function_requires(_LessThanOpConcept<_ValueType2, _ValueType1>) 
05543       __glibcxx_requires_sorted_set(__first1, __last1, __first2);
05544       __glibcxx_requires_sorted_set(__first2, __last2, __first1);
05545 
05546       while (__first1 != __last1 && __first2 != __last2)
05547     {
05548       if (*__first2 < *__first1)
05549         {
05550           *__result = *__first2;
05551           ++__first2;
05552         }
05553       else
05554         {
05555           *__result = *__first1;
05556           ++__first1;
05557         }
05558       ++__result;
05559     }
05560       return std::copy(__first2, __last2, std::copy(__first1, __last1,
05561                             __result));
05562     }
05563 
05564   /**
05565    *  @brief Merges two sorted ranges.
05566    *  @ingroup sorting_algorithms
05567    *  @param  __first1  An iterator.
05568    *  @param  __first2  Another iterator.
05569    *  @param  __last1   Another iterator.
05570    *  @param  __last2   Another iterator.
05571    *  @param  __result  An iterator pointing to the end of the merged range.
05572    *  @param  __comp    A functor to use for comparisons.
05573    *  @return         An iterator pointing to the first element "not less
05574    *                  than" @e val.
05575    *
05576    *  Merges the ranges @p [__first1,__last1) and @p [__first2,__last2) into
05577    *  the sorted range @p [__result, __result + (__last1-__first1) +
05578    *  (__last2-__first2)).  Both input ranges must be sorted, and the
05579    *  output range must not overlap with either of the input ranges.
05580    *  The sort is @e stable, that is, for equivalent elements in the
05581    *  two ranges, elements from the first range will always come
05582    *  before elements from the second.
05583    *
05584    *  The comparison function should have the same effects on ordering as
05585    *  the function used for the initial sort.
05586   */
05587   template<typename _InputIterator1, typename _InputIterator2,
05588        typename _OutputIterator, typename _Compare>
05589     _OutputIterator
05590     merge(_InputIterator1 __first1, _InputIterator1 __last1,
05591       _InputIterator2 __first2, _InputIterator2 __last2,
05592       _OutputIterator __result, _Compare __comp)
05593     {
05594       typedef typename iterator_traits<_InputIterator1>::value_type
05595     _ValueType1;
05596       typedef typename iterator_traits<_InputIterator2>::value_type
05597     _ValueType2;
05598 
05599       // concept requirements
05600       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
05601       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
05602       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
05603                   _ValueType1>)
05604       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
05605                   _ValueType2>)
05606       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
05607                   _ValueType2, _ValueType1>)
05608       __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp);
05609       __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp);
05610 
05611       while (__first1 != __last1 && __first2 != __last2)
05612     {
05613       if (__comp(*__first2, *__first1))
05614         {
05615           *__result = *__first2;
05616           ++__first2;
05617         }
05618       else
05619         {
05620           *__result = *__first1;
05621           ++__first1;
05622         }
05623       ++__result;
05624     }
05625       return std::copy(__first2, __last2, std::copy(__first1, __last1,
05626                             __result));
05627     }
05628 
05629 
05630   /**
05631    *  @brief Sort the elements of a sequence, preserving the relative order
05632    *         of equivalent elements.
05633    *  @ingroup sorting_algorithms
05634    *  @param  __first   An iterator.
05635    *  @param  __last    Another iterator.
05636    *  @return  Nothing.
05637    *
05638    *  Sorts the elements in the range @p [__first,__last) in ascending order,
05639    *  such that for each iterator @p i in the range @p [__first,__last-1),
05640    *  @p *(i+1)<*i is false.
05641    *
05642    *  The relative ordering of equivalent elements is preserved, so any two
05643    *  elements @p x and @p y in the range @p [__first,__last) such that
05644    *  @p x<y is false and @p y<x is false will have the same relative
05645    *  ordering after calling @p stable_sort().
05646   */
05647   template<typename _RandomAccessIterator>
05648     inline void
05649     stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last)
05650     {
05651       typedef typename iterator_traits<_RandomAccessIterator>::value_type
05652     _ValueType;
05653       typedef typename iterator_traits<_RandomAccessIterator>::difference_type
05654     _DistanceType;
05655 
05656       // concept requirements
05657       __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
05658         _RandomAccessIterator>)
05659       __glibcxx_function_requires(_LessThanComparableConcept<_ValueType>)
05660       __glibcxx_requires_valid_range(__first, __last);
05661 
05662       _Temporary_buffer<_RandomAccessIterator, _ValueType> __buf(__first,
05663                                  __last);
05664       if (__buf.begin() == 0)
05665     std::__inplace_stable_sort(__first, __last);
05666       else
05667     std::__stable_sort_adaptive(__first, __last, __buf.begin(),
05668                     _DistanceType(__buf.size()));
05669     }
05670 
05671   /**
05672    *  @brief Sort the elements of a sequence using a predicate for comparison,
05673    *         preserving the relative order of equivalent elements.
05674    *  @ingroup sorting_algorithms
05675    *  @param  __first   An iterator.
05676    *  @param  __last    Another iterator.
05677    *  @param  __comp    A comparison functor.
05678    *  @return  Nothing.
05679    *
05680    *  Sorts the elements in the range @p [__first,__last) in ascending order,
05681    *  such that for each iterator @p i in the range @p [__first,__last-1),
05682    *  @p __comp(*(i+1),*i) is false.
05683    *
05684    *  The relative ordering of equivalent elements is preserved, so any two
05685    *  elements @p x and @p y in the range @p [__first,__last) such that
05686    *  @p __comp(x,y) is false and @p __comp(y,x) is false will have the same
05687    *  relative ordering after calling @p stable_sort().
05688   */
05689   template<typename _RandomAccessIterator, typename _Compare>
05690     inline void
05691     stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last,
05692         _Compare __comp)
05693     {
05694       typedef typename iterator_traits<_RandomAccessIterator>::value_type
05695     _ValueType;
05696       typedef typename iterator_traits<_RandomAccessIterator>::difference_type
05697     _DistanceType;
05698 
05699       // concept requirements
05700       __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
05701         _RandomAccessIterator>)
05702       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
05703                   _ValueType,
05704                   _ValueType>)
05705       __glibcxx_requires_valid_range(__first, __last);
05706 
05707       _Temporary_buffer<_RandomAccessIterator, _ValueType> __buf(__first,
05708                                  __last);
05709       if (__buf.begin() == 0)
05710     std::__inplace_stable_sort(__first, __last, __comp);
05711       else
05712     std::__stable_sort_adaptive(__first, __last, __buf.begin(),
05713                     _DistanceType(__buf.size()), __comp);
05714     }
05715 
05716 
05717   /**
05718    *  @brief Return the union of two sorted ranges.
05719    *  @ingroup set_algorithms
05720    *  @param  __first1  Start of first range.
05721    *  @param  __last1   End of first range.
05722    *  @param  __first2  Start of second range.
05723    *  @param  __last2   End of second range.
05724    *  @return  End of the output range.
05725    *  @ingroup set_algorithms
05726    *
05727    *  This operation iterates over both ranges, copying elements present in
05728    *  each range in order to the output range.  Iterators increment for each
05729    *  range.  When the current element of one range is less than the other,
05730    *  that element is copied and the iterator advanced.  If an element is
05731    *  contained in both ranges, the element from the first range is copied and
05732    *  both ranges advance.  The output range may not overlap either input
05733    *  range.
05734   */
05735   template<typename _InputIterator1, typename _InputIterator2,
05736        typename _OutputIterator>
05737     _OutputIterator
05738     set_union(_InputIterator1 __first1, _InputIterator1 __last1,
05739           _InputIterator2 __first2, _InputIterator2 __last2,
05740           _OutputIterator __result)
05741     {
05742       typedef typename iterator_traits<_InputIterator1>::value_type
05743     _ValueType1;
05744       typedef typename iterator_traits<_InputIterator2>::value_type
05745     _ValueType2;
05746 
05747       // concept requirements
05748       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
05749       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
05750       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
05751                   _ValueType1>)
05752       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
05753                   _ValueType2>)
05754       __glibcxx_function_requires(_LessThanOpConcept<_ValueType1, _ValueType2>)
05755       __glibcxx_function_requires(_LessThanOpConcept<_ValueType2, _ValueType1>)
05756       __glibcxx_requires_sorted_set(__first1, __last1, __first2);
05757       __glibcxx_requires_sorted_set(__first2, __last2, __first1);
05758 
05759       while (__first1 != __last1 && __first2 != __last2)
05760     {
05761       if (*__first1 < *__first2)
05762         {
05763           *__result = *__first1;
05764           ++__first1;
05765         }
05766       else if (*__first2 < *__first1)
05767         {
05768           *__result = *__first2;
05769           ++__first2;
05770         }
05771       else
05772         {
05773           *__result = *__first1;
05774           ++__first1;
05775           ++__first2;
05776         }
05777       ++__result;
05778     }
05779       return std::copy(__first2, __last2, std::copy(__first1, __last1,
05780                             __result));
05781     }
05782 
05783   /**
05784    *  @brief Return the union of two sorted ranges using a comparison functor.
05785    *  @ingroup set_algorithms
05786    *  @param  __first1  Start of first range.
05787    *  @param  __last1   End of first range.
05788    *  @param  __first2  Start of second range.
05789    *  @param  __last2   End of second range.
05790    *  @param  __comp    The comparison functor.
05791    *  @return  End of the output range.
05792    *  @ingroup set_algorithms
05793    *
05794    *  This operation iterates over both ranges, copying elements present in
05795    *  each range in order to the output range.  Iterators increment for each
05796    *  range.  When the current element of one range is less than the other
05797    *  according to @p __comp, that element is copied and the iterator advanced.
05798    *  If an equivalent element according to @p __comp is contained in both
05799    *  ranges, the element from the first range is copied and both ranges
05800    *  advance.  The output range may not overlap either input range.
05801   */
05802   template<typename _InputIterator1, typename _InputIterator2,
05803        typename _OutputIterator, typename _Compare>
05804     _OutputIterator
05805     set_union(_InputIterator1 __first1, _InputIterator1 __last1,
05806           _InputIterator2 __first2, _InputIterator2 __last2,
05807           _OutputIterator __result, _Compare __comp)
05808     {
05809       typedef typename iterator_traits<_InputIterator1>::value_type
05810     _ValueType1;
05811       typedef typename iterator_traits<_InputIterator2>::value_type
05812     _ValueType2;
05813 
05814       // concept requirements
05815       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
05816       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
05817       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
05818                   _ValueType1>)
05819       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
05820                   _ValueType2>)
05821       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
05822                   _ValueType1, _ValueType2>)
05823       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
05824                   _ValueType2, _ValueType1>)
05825       __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp);
05826       __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp);
05827 
05828       while (__first1 != __last1 && __first2 != __last2)
05829     {
05830       if (__comp(*__first1, *__first2))
05831         {
05832           *__result = *__first1;
05833           ++__first1;
05834         }
05835       else if (__comp(*__first2, *__first1))
05836         {
05837           *__result = *__first2;
05838           ++__first2;
05839         }
05840       else
05841         {
05842           *__result = *__first1;
05843           ++__first1;
05844           ++__first2;
05845         }
05846       ++__result;
05847     }
05848       return std::copy(__first2, __last2, std::copy(__first1, __last1,
05849                             __result));
05850     }
05851 
05852   /**
05853    *  @brief Return the intersection of two sorted ranges.
05854    *  @ingroup set_algorithms
05855    *  @param  __first1  Start of first range.
05856    *  @param  __last1   End of first range.
05857    *  @param  __first2  Start of second range.
05858    *  @param  __last2   End of second range.
05859    *  @return  End of the output range.
05860    *  @ingroup set_algorithms
05861    *
05862    *  This operation iterates over both ranges, copying elements present in
05863    *  both ranges in order to the output range.  Iterators increment for each
05864    *  range.  When the current element of one range is less than the other,
05865    *  that iterator advances.  If an element is contained in both ranges, the
05866    *  element from the first range is copied and both ranges advance.  The
05867    *  output range may not overlap either input range.
05868   */
05869   template<typename _InputIterator1, typename _InputIterator2,
05870        typename _OutputIterator>
05871     _OutputIterator
05872     set_intersection(_InputIterator1 __first1, _InputIterator1 __last1,
05873              _InputIterator2 __first2, _InputIterator2 __last2,
05874              _OutputIterator __result)
05875     {
05876       typedef typename iterator_traits<_InputIterator1>::value_type
05877     _ValueType1;
05878       typedef typename iterator_traits<_InputIterator2>::value_type
05879     _ValueType2;
05880 
05881       // concept requirements
05882       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
05883       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
05884       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
05885                   _ValueType1>)
05886       __glibcxx_function_requires(_LessThanOpConcept<_ValueType1, _ValueType2>)
05887       __glibcxx_function_requires(_LessThanOpConcept<_ValueType2, _ValueType1>)
05888       __glibcxx_requires_sorted_set(__first1, __last1, __first2);
05889       __glibcxx_requires_sorted_set(__first2, __last2, __first1);
05890 
05891       while (__first1 != __last1 && __first2 != __last2)
05892     if (*__first1 < *__first2)
05893       ++__first1;
05894     else if (*__first2 < *__first1)
05895       ++__first2;
05896     else
05897       {
05898         *__result = *__first1;
05899         ++__first1;
05900         ++__first2;
05901         ++__result;
05902       }
05903       return __result;
05904     }
05905 
05906   /**
05907    *  @brief Return the intersection of two sorted ranges using comparison
05908    *  functor.
05909    *  @ingroup set_algorithms
05910    *  @param  __first1  Start of first range.
05911    *  @param  __last1   End of first range.
05912    *  @param  __first2  Start of second range.
05913    *  @param  __last2   End of second range.
05914    *  @param  __comp    The comparison functor.
05915    *  @return  End of the output range.
05916    *  @ingroup set_algorithms
05917    *
05918    *  This operation iterates over both ranges, copying elements present in
05919    *  both ranges in order to the output range.  Iterators increment for each
05920    *  range.  When the current element of one range is less than the other
05921    *  according to @p __comp, that iterator advances.  If an element is
05922    *  contained in both ranges according to @p __comp, the element from the
05923    *  first range is copied and both ranges advance.  The output range may not
05924    *  overlap either input range.
05925   */
05926   template<typename _InputIterator1, typename _InputIterator2,
05927        typename _OutputIterator, typename _Compare>
05928     _OutputIterator
05929     set_intersection(_InputIterator1 __first1, _InputIterator1 __last1,
05930              _InputIterator2 __first2, _InputIterator2 __last2,
05931              _OutputIterator __result, _Compare __comp)
05932     {
05933       typedef typename iterator_traits<_InputIterator1>::value_type
05934     _ValueType1;
05935       typedef typename iterator_traits<_InputIterator2>::value_type
05936     _ValueType2;
05937 
05938       // concept requirements
05939       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
05940       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
05941       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
05942                   _ValueType1>)
05943       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
05944                   _ValueType1, _ValueType2>)
05945       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
05946                   _ValueType2, _ValueType1>)
05947       __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp);
05948       __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp);
05949 
05950       while (__first1 != __last1 && __first2 != __last2)
05951     if (__comp(*__first1, *__first2))
05952       ++__first1;
05953     else if (__comp(*__first2, *__first1))
05954       ++__first2;
05955     else
05956       {
05957         *__result = *__first1;
05958         ++__first1;
05959         ++__first2;
05960         ++__result;
05961       }
05962       return __result;
05963     }
05964 
05965   /**
05966    *  @brief Return the difference of two sorted ranges.
05967    *  @ingroup set_algorithms
05968    *  @param  __first1  Start of first range.
05969    *  @param  __last1   End of first range.
05970    *  @param  __first2  Start of second range.
05971    *  @param  __last2   End of second range.
05972    *  @return  End of the output range.
05973    *  @ingroup set_algorithms
05974    *
05975    *  This operation iterates over both ranges, copying elements present in
05976    *  the first range but not the second in order to the output range.
05977    *  Iterators increment for each range.  When the current element of the
05978    *  first range is less than the second, that element is copied and the
05979    *  iterator advances.  If the current element of the second range is less,
05980    *  the iterator advances, but no element is copied.  If an element is
05981    *  contained in both ranges, no elements are copied and both ranges
05982    *  advance.  The output range may not overlap either input range.
05983   */
05984   template<typename _InputIterator1, typename _InputIterator2,
05985        typename _OutputIterator>
05986     _OutputIterator
05987     set_difference(_InputIterator1 __first1, _InputIterator1 __last1,
05988            _InputIterator2 __first2, _InputIterator2 __last2,
05989            _OutputIterator __result)
05990     {
05991       typedef typename iterator_traits<_InputIterator1>::value_type
05992     _ValueType1;
05993       typedef typename iterator_traits<_InputIterator2>::value_type
05994     _ValueType2;
05995 
05996       // concept requirements
05997       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
05998       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
05999       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
06000                   _ValueType1>)
06001       __glibcxx_function_requires(_LessThanOpConcept<_ValueType1, _ValueType2>)
06002       __glibcxx_function_requires(_LessThanOpConcept<_ValueType2, _ValueType1>) 
06003       __glibcxx_requires_sorted_set(__first1, __last1, __first2);
06004       __glibcxx_requires_sorted_set(__first2, __last2, __first1);
06005 
06006       while (__first1 != __last1 && __first2 != __last2)
06007     if (*__first1 < *__first2)
06008       {
06009         *__result = *__first1;
06010         ++__first1;
06011         ++__result;
06012       }
06013     else if (*__first2 < *__first1)
06014       ++__first2;
06015     else
06016       {
06017         ++__first1;
06018         ++__first2;
06019       }
06020       return std::copy(__first1, __last1, __result);
06021     }
06022 
06023   /**
06024    *  @brief  Return the difference of two sorted ranges using comparison
06025    *  functor.
06026    *  @ingroup set_algorithms
06027    *  @param  __first1  Start of first range.
06028    *  @param  __last1   End of first range.
06029    *  @param  __first2  Start of second range.
06030    *  @param  __last2   End of second range.
06031    *  @param  __comp    The comparison functor.
06032    *  @return  End of the output range.
06033    *  @ingroup set_algorithms
06034    *
06035    *  This operation iterates over both ranges, copying elements present in
06036    *  the first range but not the second in order to the output range.
06037    *  Iterators increment for each range.  When the current element of the
06038    *  first range is less than the second according to @p __comp, that element
06039    *  is copied and the iterator advances.  If the current element of the
06040    *  second range is less, no element is copied and the iterator advances.
06041    *  If an element is contained in both ranges according to @p __comp, no
06042    *  elements are copied and both ranges advance.  The output range may not
06043    *  overlap either input range.
06044   */
06045   template<typename _InputIterator1, typename _InputIterator2,
06046        typename _OutputIterator, typename _Compare>
06047     _OutputIterator
06048     set_difference(_InputIterator1 __first1, _InputIterator1 __last1,
06049            _InputIterator2 __first2, _InputIterator2 __last2,
06050            _OutputIterator __result, _Compare __comp)
06051     {
06052       typedef typename iterator_traits<_InputIterator1>::value_type
06053     _ValueType1;
06054       typedef typename iterator_traits<_InputIterator2>::value_type
06055     _ValueType2;
06056 
06057       // concept requirements
06058       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
06059       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
06060       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
06061                   _ValueType1>)
06062       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
06063                   _ValueType1, _ValueType2>)
06064       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
06065                   _ValueType2, _ValueType1>)
06066       __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp);
06067       __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp);
06068 
06069       while (__first1 != __last1 && __first2 != __last2)
06070     if (__comp(*__first1, *__first2))
06071       {
06072         *__result = *__first1;
06073         ++__first1;
06074         ++__result;
06075       }
06076     else if (__comp(*__first2, *__first1))
06077       ++__first2;
06078     else
06079       {
06080         ++__first1;
06081         ++__first2;
06082       }
06083       return std::copy(__first1, __last1, __result);
06084     }
06085 
06086   /**
06087    *  @brief  Return the symmetric difference of two sorted ranges.
06088    *  @ingroup set_algorithms
06089    *  @param  __first1  Start of first range.
06090    *  @param  __last1   End of first range.
06091    *  @param  __first2  Start of second range.
06092    *  @param  __last2   End of second range.
06093    *  @return  End of the output range.
06094    *  @ingroup set_algorithms
06095    *
06096    *  This operation iterates over both ranges, copying elements present in
06097    *  one range but not the other in order to the output range.  Iterators
06098    *  increment for each range.  When the current element of one range is less
06099    *  than the other, that element is copied and the iterator advances.  If an
06100    *  element is contained in both ranges, no elements are copied and both
06101    *  ranges advance.  The output range may not overlap either input range.
06102   */
06103   template<typename _InputIterator1, typename _InputIterator2,
06104        typename _OutputIterator>
06105     _OutputIterator
06106     set_symmetric_difference(_InputIterator1 __first1, _InputIterator1 __last1,
06107                  _InputIterator2 __first2, _InputIterator2 __last2,
06108                  _OutputIterator __result)
06109     {
06110       typedef typename iterator_traits<_InputIterator1>::value_type
06111     _ValueType1;
06112       typedef typename iterator_traits<_InputIterator2>::value_type
06113     _ValueType2;
06114 
06115       // concept requirements
06116       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
06117       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
06118       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
06119                   _ValueType1>)
06120       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
06121                   _ValueType2>)
06122       __glibcxx_function_requires(_LessThanOpConcept<_ValueType1, _ValueType2>)
06123       __glibcxx_function_requires(_LessThanOpConcept<_ValueType2, _ValueType1>) 
06124       __glibcxx_requires_sorted_set(__first1, __last1, __first2);
06125       __glibcxx_requires_sorted_set(__first2, __last2, __first1);
06126 
06127       while (__first1 != __last1 && __first2 != __last2)
06128     if (*__first1 < *__first2)
06129       {
06130         *__result = *__first1;
06131         ++__first1;
06132         ++__result;
06133       }
06134     else if (*__first2 < *__first1)
06135       {
06136         *__result = *__first2;
06137         ++__first2;
06138         ++__result;
06139       }
06140     else
06141       {
06142         ++__first1;
06143         ++__first2;
06144       }
06145       return std::copy(__first2, __last2, std::copy(__first1,
06146                             __last1, __result));
06147     }
06148 
06149   /**
06150    *  @brief  Return the symmetric difference of two sorted ranges using
06151    *  comparison functor.
06152    *  @ingroup set_algorithms
06153    *  @param  __first1  Start of first range.
06154    *  @param  __last1   End of first range.
06155    *  @param  __first2  Start of second range.
06156    *  @param  __last2   End of second range.
06157    *  @param  __comp    The comparison functor.
06158    *  @return  End of the output range.
06159    *  @ingroup set_algorithms
06160    *
06161    *  This operation iterates over both ranges, copying elements present in
06162    *  one range but not the other in order to the output range.  Iterators
06163    *  increment for each range.  When the current element of one range is less
06164    *  than the other according to @p comp, that element is copied and the
06165    *  iterator advances.  If an element is contained in both ranges according
06166    *  to @p __comp, no elements are copied and both ranges advance.  The output
06167    *  range may not overlap either input range.
06168   */
06169   template<typename _InputIterator1, typename _InputIterator2,
06170        typename _OutputIterator, typename _Compare>
06171     _OutputIterator
06172     set_symmetric_difference(_InputIterator1 __first1, _InputIterator1 __last1,
06173                  _InputIterator2 __first2, _InputIterator2 __last2,
06174                  _OutputIterator __result,
06175                  _Compare __comp)
06176     {
06177       typedef typename iterator_traits<_InputIterator1>::value_type
06178     _ValueType1;
06179       typedef typename iterator_traits<_InputIterator2>::value_type
06180     _ValueType2;
06181 
06182       // concept requirements
06183       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
06184       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
06185       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
06186                   _ValueType1>)
06187       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
06188                   _ValueType2>)
06189       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
06190                   _ValueType1, _ValueType2>)
06191       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
06192                   _ValueType2, _ValueType1>)
06193       __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp);
06194       __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp);
06195 
06196       while (__first1 != __last1 && __first2 != __last2)
06197     if (__comp(*__first1, *__first2))
06198       {
06199         *__result = *__first1;
06200         ++__first1;
06201         ++__result;
06202       }
06203     else if (__comp(*__first2, *__first1))
06204       {
06205         *__result = *__first2;
06206         ++__first2;
06207         ++__result;
06208       }
06209     else
06210       {
06211         ++__first1;
06212         ++__first2;
06213       }
06214       return std::copy(__first2, __last2, 
06215                std::copy(__first1, __last1, __result));
06216     }
06217 
06218 
06219   /**
06220    *  @brief  Return the minimum element in a range.
06221    *  @ingroup sorting_algorithms
06222    *  @param  __first  Start of range.
06223    *  @param  __last   End of range.
06224    *  @return  Iterator referencing the first instance of the smallest value.
06225   */
06226   template<typename _ForwardIterator>
06227     _ForwardIterator
06228     min_element(_ForwardIterator __first, _ForwardIterator __last)
06229     {
06230       // concept requirements
06231       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
06232       __glibcxx_function_requires(_LessThanComparableConcept<
06233         typename iterator_traits<_ForwardIterator>::value_type>)
06234       __glibcxx_requires_valid_range(__first, __last);
06235 
06236       if (__first == __last)
06237     return __first;
06238       _ForwardIterator __result = __first;
06239       while (++__first != __last)
06240     if (*__first < *__result)
06241       __result = __first;
06242       return __result;
06243     }
06244 
06245   /**
06246    *  @brief  Return the minimum element in a range using comparison functor.
06247    *  @ingroup sorting_algorithms
06248    *  @param  __first  Start of range.
06249    *  @param  __last   End of range.
06250    *  @param  __comp   Comparison functor.
06251    *  @return  Iterator referencing the first instance of the smallest value
06252    *  according to __comp.
06253   */
06254   template<typename _ForwardIterator, typename _Compare>
06255     _ForwardIterator
06256     min_element(_ForwardIterator __first, _ForwardIterator __last,
06257         _Compare __comp)
06258     {
06259       // concept requirements
06260       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
06261       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
06262         typename iterator_traits<_ForwardIterator>::value_type,
06263         typename iterator_traits<_ForwardIterator>::value_type>)
06264       __glibcxx_requires_valid_range(__first, __last);
06265 
06266       if (__first == __last)
06267     return __first;
06268       _ForwardIterator __result = __first;
06269       while (++__first != __last)
06270     if (__comp(*__first, *__result))
06271       __result = __first;
06272       return __result;
06273     }
06274 
06275   /**
06276    *  @brief  Return the maximum element in a range.
06277    *  @ingroup sorting_algorithms
06278    *  @param  __first  Start of range.
06279    *  @param  __last   End of range.
06280    *  @return  Iterator referencing the first instance of the largest value.
06281   */
06282   template<typename _ForwardIterator>
06283     _ForwardIterator
06284     max_element(_ForwardIterator __first, _ForwardIterator __last)
06285     {
06286       // concept requirements
06287       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
06288       __glibcxx_function_requires(_LessThanComparableConcept<
06289         typename iterator_traits<_ForwardIterator>::value_type>)
06290       __glibcxx_requires_valid_range(__first, __last);
06291 
06292       if (__first == __last)
06293     return __first;
06294       _ForwardIterator __result = __first;
06295       while (++__first != __last)
06296     if (*__result < *__first)
06297       __result = __first;
06298       return __result;
06299     }
06300 
06301   /**
06302    *  @brief  Return the maximum element in a range using comparison functor.
06303    *  @ingroup sorting_algorithms
06304    *  @param  __first  Start of range.
06305    *  @param  __last   End of range.
06306    *  @param  __comp   Comparison functor.
06307    *  @return  Iterator referencing the first instance of the largest value
06308    *  according to __comp.
06309   */
06310   template<typename _ForwardIterator, typename _Compare>
06311     _ForwardIterator
06312     max_element(_ForwardIterator __first, _ForwardIterator __last,
06313         _Compare __comp)
06314     {
06315       // concept requirements
06316       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
06317       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
06318         typename iterator_traits<_ForwardIterator>::value_type,
06319         typename iterator_traits<_ForwardIterator>::value_type>)
06320       __glibcxx_requires_valid_range(__first, __last);
06321 
06322       if (__first == __last) return __first;
06323       _ForwardIterator __result = __first;
06324       while (++__first != __last)
06325     if (__comp(*__result, *__first))
06326       __result = __first;
06327       return __result;
06328     }
06329 
06330 _GLIBCXX_END_NAMESPACE_ALGO
06331 } // namespace std
06332 
06333 #endif /* _STL_ALGO_H */