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