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