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