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