libstdc++
stl_algo.h
Go to the documentation of this file.
00001 // Algorithm implementation -*- C++ -*-
00002 
00003 // Copyright (C) 2001-2014 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 <random>     // for std::uniform_int_distribution
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   /// This is a helper function for the rotate algorithm.
01241   template<typename _ForwardIterator>
01242     void
01243     __rotate(_ForwardIterator __first,
01244          _ForwardIterator __middle,
01245          _ForwardIterator __last,
01246          forward_iterator_tag)
01247     {
01248       if (__first == __middle || __last  == __middle)
01249     return;
01250 
01251       _ForwardIterator __first2 = __middle;
01252       do
01253     {
01254       std::iter_swap(__first, __first2);
01255       ++__first;
01256       ++__first2;
01257       if (__first == __middle)
01258         __middle = __first2;
01259     }
01260       while (__first2 != __last);
01261 
01262       __first2 = __middle;
01263 
01264       while (__first2 != __last)
01265     {
01266       std::iter_swap(__first, __first2);
01267       ++__first;
01268       ++__first2;
01269       if (__first == __middle)
01270         __middle = __first2;
01271       else if (__first2 == __last)
01272         __first2 = __middle;
01273     }
01274     }
01275 
01276    /// This is a helper function for the rotate algorithm.
01277   template<typename _BidirectionalIterator>
01278     void
01279     __rotate(_BidirectionalIterator __first,
01280          _BidirectionalIterator __middle,
01281          _BidirectionalIterator __last,
01282           bidirectional_iterator_tag)
01283     {
01284       // concept requirements
01285       __glibcxx_function_requires(_Mutable_BidirectionalIteratorConcept<
01286                   _BidirectionalIterator>)
01287 
01288       if (__first == __middle || __last  == __middle)
01289     return;
01290 
01291       std::__reverse(__first,  __middle, bidirectional_iterator_tag());
01292       std::__reverse(__middle, __last,   bidirectional_iterator_tag());
01293 
01294       while (__first != __middle && __middle != __last)
01295     {
01296       std::iter_swap(__first, --__last);
01297       ++__first;
01298     }
01299 
01300       if (__first == __middle)
01301     std::__reverse(__middle, __last,   bidirectional_iterator_tag());
01302       else
01303     std::__reverse(__first,  __middle, bidirectional_iterator_tag());
01304     }
01305 
01306   /// This is a helper function for the rotate algorithm.
01307   template<typename _RandomAccessIterator>
01308     void
01309     __rotate(_RandomAccessIterator __first,
01310          _RandomAccessIterator __middle,
01311          _RandomAccessIterator __last,
01312          random_access_iterator_tag)
01313     {
01314       // concept requirements
01315       __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
01316                   _RandomAccessIterator>)
01317 
01318       if (__first == __middle || __last  == __middle)
01319     return;
01320 
01321       typedef typename iterator_traits<_RandomAccessIterator>::difference_type
01322     _Distance;
01323       typedef typename iterator_traits<_RandomAccessIterator>::value_type
01324     _ValueType;
01325 
01326       _Distance __n = __last   - __first;
01327       _Distance __k = __middle - __first;
01328 
01329       if (__k == __n - __k)
01330     {
01331       std::swap_ranges(__first, __middle, __middle);
01332       return;
01333     }
01334 
01335       _RandomAccessIterator __p = __first;
01336 
01337       for (;;)
01338     {
01339       if (__k < __n - __k)
01340         {
01341           if (__is_pod(_ValueType) && __k == 1)
01342         {
01343           _ValueType __t = _GLIBCXX_MOVE(*__p);
01344           _GLIBCXX_MOVE3(__p + 1, __p + __n, __p);
01345           *(__p + __n - 1) = _GLIBCXX_MOVE(__t);
01346           return;
01347         }
01348           _RandomAccessIterator __q = __p + __k;
01349           for (_Distance __i = 0; __i < __n - __k; ++ __i)
01350         {
01351           std::iter_swap(__p, __q);
01352           ++__p;
01353           ++__q;
01354         }
01355           __n %= __k;
01356           if (__n == 0)
01357         return;
01358           std::swap(__n, __k);
01359           __k = __n - __k;
01360         }
01361       else
01362         {
01363           __k = __n - __k;
01364           if (__is_pod(_ValueType) && __k == 1)
01365         {
01366           _ValueType __t = _GLIBCXX_MOVE(*(__p + __n - 1));
01367           _GLIBCXX_MOVE_BACKWARD3(__p, __p + __n - 1, __p + __n);
01368           *__p = _GLIBCXX_MOVE(__t);
01369           return;
01370         }
01371           _RandomAccessIterator __q = __p + __n;
01372           __p = __q - __k;
01373           for (_Distance __i = 0; __i < __n - __k; ++ __i)
01374         {
01375           --__p;
01376           --__q;
01377           std::iter_swap(__p, __q);
01378         }
01379           __n %= __k;
01380           if (__n == 0)
01381         return;
01382           std::swap(__n, __k);
01383         }
01384     }
01385     }
01386 
01387   /**
01388    *  @brief Rotate the elements of a sequence.
01389    *  @ingroup mutating_algorithms
01390    *  @param  __first   A forward iterator.
01391    *  @param  __middle  A forward iterator.
01392    *  @param  __last    A forward iterator.
01393    *  @return  Nothing.
01394    *
01395    *  Rotates the elements of the range @p [__first,__last) by 
01396    *  @p (__middle - __first) positions so that the element at @p __middle
01397    *  is moved to @p __first, the element at @p __middle+1 is moved to
01398    *  @p __first+1 and so on for each element in the range
01399    *  @p [__first,__last).
01400    *
01401    *  This effectively swaps the ranges @p [__first,__middle) and
01402    *  @p [__middle,__last).
01403    *
01404    *  Performs
01405    *   @p *(__first+(n+(__last-__middle))%(__last-__first))=*(__first+n)
01406    *  for each @p n in the range @p [0,__last-__first).
01407   */
01408   template<typename _ForwardIterator>
01409     inline void
01410     rotate(_ForwardIterator __first, _ForwardIterator __middle,
01411        _ForwardIterator __last)
01412     {
01413       // concept requirements
01414       __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
01415                   _ForwardIterator>)
01416       __glibcxx_requires_valid_range(__first, __middle);
01417       __glibcxx_requires_valid_range(__middle, __last);
01418 
01419       std::__rotate(__first, __middle, __last,
01420             std::__iterator_category(__first));
01421     }
01422 
01423   /**
01424    *  @brief Copy a sequence, rotating its elements.
01425    *  @ingroup mutating_algorithms
01426    *  @param  __first   A forward iterator.
01427    *  @param  __middle  A forward iterator.
01428    *  @param  __last    A forward iterator.
01429    *  @param  __result  An output iterator.
01430    *  @return   An iterator designating the end of the resulting sequence.
01431    *
01432    *  Copies the elements of the range @p [__first,__last) to the
01433    *  range beginning at @result, rotating the copied elements by 
01434    *  @p (__middle-__first) positions so that the element at @p __middle
01435    *  is moved to @p __result, the element at @p __middle+1 is moved
01436    *  to @p __result+1 and so on for each element in the range @p
01437    *  [__first,__last).
01438    *
01439    *  Performs 
01440    *  @p *(__result+(n+(__last-__middle))%(__last-__first))=*(__first+n)
01441    *  for each @p n in the range @p [0,__last-__first).
01442   */
01443   template<typename _ForwardIterator, typename _OutputIterator>
01444     inline _OutputIterator
01445     rotate_copy(_ForwardIterator __first, _ForwardIterator __middle,
01446                 _ForwardIterator __last, _OutputIterator __result)
01447     {
01448       // concept requirements
01449       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
01450       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
01451         typename iterator_traits<_ForwardIterator>::value_type>)
01452       __glibcxx_requires_valid_range(__first, __middle);
01453       __glibcxx_requires_valid_range(__middle, __last);
01454 
01455       return std::copy(__first, __middle,
01456                        std::copy(__middle, __last, __result));
01457     }
01458 
01459   /// This is a helper function...
01460   template<typename _ForwardIterator, typename _Predicate>
01461     _ForwardIterator
01462     __partition(_ForwardIterator __first, _ForwardIterator __last,
01463         _Predicate __pred, forward_iterator_tag)
01464     {
01465       if (__first == __last)
01466     return __first;
01467 
01468       while (__pred(*__first))
01469     if (++__first == __last)
01470       return __first;
01471 
01472       _ForwardIterator __next = __first;
01473 
01474       while (++__next != __last)
01475     if (__pred(*__next))
01476       {
01477         std::iter_swap(__first, __next);
01478         ++__first;
01479       }
01480 
01481       return __first;
01482     }
01483 
01484   /// This is a helper function...
01485   template<typename _BidirectionalIterator, typename _Predicate>
01486     _BidirectionalIterator
01487     __partition(_BidirectionalIterator __first, _BidirectionalIterator __last,
01488         _Predicate __pred, bidirectional_iterator_tag)
01489     {
01490       while (true)
01491     {
01492       while (true)
01493         if (__first == __last)
01494           return __first;
01495         else if (__pred(*__first))
01496           ++__first;
01497         else
01498           break;
01499       --__last;
01500       while (true)
01501         if (__first == __last)
01502           return __first;
01503         else if (!bool(__pred(*__last)))
01504           --__last;
01505         else
01506           break;
01507       std::iter_swap(__first, __last);
01508       ++__first;
01509     }
01510     }
01511 
01512   // partition
01513 
01514   /// This is a helper function...
01515   /// Requires __len != 0 and !__pred(*__first),
01516   /// same as __stable_partition_adaptive.
01517   template<typename _ForwardIterator, typename _Predicate, typename _Distance>
01518     _ForwardIterator
01519     __inplace_stable_partition(_ForwardIterator __first,
01520                    _Predicate __pred, _Distance __len)
01521     {
01522       if (__len == 1)
01523     return __first;
01524       _ForwardIterator __middle = __first;
01525       std::advance(__middle, __len / 2);
01526       _ForwardIterator __left_split =
01527     std::__inplace_stable_partition(__first, __pred, __len / 2);
01528       // Advance past true-predicate values to satisfy this
01529       // function's preconditions.
01530       _Distance __right_len = __len - __len / 2;
01531       _ForwardIterator __right_split =
01532     std::__find_if_not_n(__middle, __right_len, __pred);
01533       if (__right_len)
01534     __right_split = std::__inplace_stable_partition(__middle,
01535                             __pred,
01536                             __right_len);
01537       std::rotate(__left_split, __middle, __right_split);
01538       std::advance(__left_split, std::distance(__middle, __right_split));
01539       return __left_split;
01540     }
01541 
01542   /// This is a helper function...
01543   /// Requires __first != __last and !__pred(__first)
01544   /// and __len == distance(__first, __last).
01545   ///
01546   /// !__pred(__first) allows us to guarantee that we don't
01547   /// move-assign an element onto itself.
01548   template<typename _ForwardIterator, typename _Pointer, typename _Predicate,
01549        typename _Distance>
01550     _ForwardIterator
01551     __stable_partition_adaptive(_ForwardIterator __first,
01552                 _ForwardIterator __last,
01553                 _Predicate __pred, _Distance __len,
01554                 _Pointer __buffer,
01555                 _Distance __buffer_size)
01556     {
01557       if (__len <= __buffer_size)
01558     {
01559       _ForwardIterator __result1 = __first;
01560       _Pointer __result2 = __buffer;
01561       // The precondition guarantees that !__pred(__first), so
01562       // move that element to the buffer before starting the loop.
01563       // This ensures that we only call __pred once per element.
01564       *__result2 = _GLIBCXX_MOVE(*__first);
01565       ++__result2;
01566       ++__first;
01567       for (; __first != __last; ++__first)
01568         if (__pred(__first))
01569           {
01570         *__result1 = _GLIBCXX_MOVE(*__first);
01571         ++__result1;
01572           }
01573         else
01574           {
01575         *__result2 = _GLIBCXX_MOVE(*__first);
01576         ++__result2;
01577           }
01578       _GLIBCXX_MOVE3(__buffer, __result2, __result1);
01579       return __result1;
01580     }
01581       else
01582     {
01583       _ForwardIterator __middle = __first;
01584       std::advance(__middle, __len / 2);
01585       _ForwardIterator __left_split =
01586         std::__stable_partition_adaptive(__first, __middle, __pred,
01587                          __len / 2, __buffer,
01588                          __buffer_size);
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       if (__right_len)
01595         __right_split =
01596           std::__stable_partition_adaptive(__right_split, __last, __pred,
01597                            __right_len,
01598                            __buffer, __buffer_size);
01599       std::rotate(__left_split, __middle, __right_split);
01600       std::advance(__left_split, std::distance(__middle, __right_split));
01601       return __left_split;
01602     }
01603     }
01604 
01605   template<typename _ForwardIterator, typename _Predicate>
01606     _ForwardIterator
01607     __stable_partition(_ForwardIterator __first, _ForwardIterator __last,
01608                _Predicate __pred)
01609     {
01610       __first = std::__find_if_not(__first, __last, __pred);
01611 
01612       if (__first == __last)
01613     return __first;
01614 
01615       typedef typename iterator_traits<_ForwardIterator>::value_type
01616     _ValueType;
01617       typedef typename iterator_traits<_ForwardIterator>::difference_type
01618     _DistanceType;
01619 
01620       _Temporary_buffer<_ForwardIterator, _ValueType> __buf(__first, __last);
01621       if (__buf.size() > 0)
01622     return
01623       std::__stable_partition_adaptive(__first, __last, __pred,
01624                        _DistanceType(__buf.requested_size()),
01625                        __buf.begin(),
01626                        _DistanceType(__buf.size()));
01627       else
01628     return
01629       std::__inplace_stable_partition(__first, __pred,
01630                       _DistanceType(__buf.requested_size()));
01631     }
01632 
01633   /**
01634    *  @brief Move elements for which a predicate is true to the beginning
01635    *         of a sequence, preserving relative ordering.
01636    *  @ingroup mutating_algorithms
01637    *  @param  __first   A forward iterator.
01638    *  @param  __last    A forward iterator.
01639    *  @param  __pred    A predicate functor.
01640    *  @return  An iterator @p middle such that @p __pred(i) is true for each
01641    *  iterator @p i in the range @p [first,middle) and false for each @p i
01642    *  in the range @p [middle,last).
01643    *
01644    *  Performs the same function as @p partition() with the additional
01645    *  guarantee that the relative ordering of elements in each group is
01646    *  preserved, so any two elements @p x and @p y in the range
01647    *  @p [__first,__last) such that @p __pred(x)==__pred(y) will have the same
01648    *  relative ordering after calling @p stable_partition().
01649   */
01650   template<typename _ForwardIterator, typename _Predicate>
01651     inline _ForwardIterator
01652     stable_partition(_ForwardIterator __first, _ForwardIterator __last,
01653              _Predicate __pred)
01654     {
01655       // concept requirements
01656       __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
01657                   _ForwardIterator>)
01658       __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
01659         typename iterator_traits<_ForwardIterator>::value_type>)
01660       __glibcxx_requires_valid_range(__first, __last);
01661 
01662       return std::__stable_partition(__first, __last,
01663                      __gnu_cxx::__ops::__pred_iter(__pred));
01664     }
01665 
01666   /// This is a helper function for the sort routines.
01667   template<typename _RandomAccessIterator, typename _Compare>
01668     void
01669     __heap_select(_RandomAccessIterator __first,
01670           _RandomAccessIterator __middle,
01671           _RandomAccessIterator __last, _Compare __comp)
01672     {
01673       std::__make_heap(__first, __middle, __comp);
01674       for (_RandomAccessIterator __i = __middle; __i < __last; ++__i)
01675     if (__comp(__i, __first))
01676       std::__pop_heap(__first, __middle, __i, __comp);
01677     }
01678 
01679   // partial_sort
01680 
01681   template<typename _InputIterator, typename _RandomAccessIterator,
01682        typename _Compare>
01683     _RandomAccessIterator
01684     __partial_sort_copy(_InputIterator __first, _InputIterator __last,
01685             _RandomAccessIterator __result_first,
01686             _RandomAccessIterator __result_last,
01687             _Compare __comp)
01688     {
01689       typedef typename iterator_traits<_InputIterator>::value_type
01690     _InputValueType;
01691       typedef iterator_traits<_RandomAccessIterator> _RItTraits;
01692       typedef typename _RItTraits::difference_type _DistanceType;
01693 
01694       if (__result_first == __result_last)
01695     return __result_last;
01696       _RandomAccessIterator __result_real_last = __result_first;
01697       while (__first != __last && __result_real_last != __result_last)
01698     {
01699       *__result_real_last = *__first;
01700       ++__result_real_last;
01701       ++__first;
01702     }
01703       
01704       std::__make_heap(__result_first, __result_real_last, __comp);
01705       while (__first != __last)
01706     {
01707       if (__comp(__first, __result_first))
01708         std::__adjust_heap(__result_first, _DistanceType(0),
01709                    _DistanceType(__result_real_last
01710                          - __result_first),
01711                    _InputValueType(*__first), __comp);
01712       ++__first;
01713     }
01714       std::__sort_heap(__result_first, __result_real_last, __comp);
01715       return __result_real_last;
01716     }
01717 
01718   /**
01719    *  @brief Copy the smallest elements of a sequence.
01720    *  @ingroup sorting_algorithms
01721    *  @param  __first   An iterator.
01722    *  @param  __last    Another iterator.
01723    *  @param  __result_first   A random-access iterator.
01724    *  @param  __result_last    Another random-access iterator.
01725    *  @return   An iterator indicating the end of the resulting sequence.
01726    *
01727    *  Copies and sorts the smallest N values from the range @p [__first,__last)
01728    *  to the range beginning at @p __result_first, where the number of
01729    *  elements to be copied, @p N, is the smaller of @p (__last-__first) and
01730    *  @p (__result_last-__result_first).
01731    *  After the sort if @e i and @e j are iterators in the range
01732    *  @p [__result_first,__result_first+N) such that i precedes j then
01733    *  *j<*i is false.
01734    *  The value returned is @p __result_first+N.
01735   */
01736   template<typename _InputIterator, typename _RandomAccessIterator>
01737     inline _RandomAccessIterator
01738     partial_sort_copy(_InputIterator __first, _InputIterator __last,
01739               _RandomAccessIterator __result_first,
01740               _RandomAccessIterator __result_last)
01741     {
01742       typedef typename iterator_traits<_InputIterator>::value_type
01743     _InputValueType;
01744       typedef typename iterator_traits<_RandomAccessIterator>::value_type
01745     _OutputValueType;
01746       typedef typename iterator_traits<_RandomAccessIterator>::difference_type
01747     _DistanceType;
01748 
01749       // concept requirements
01750       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
01751       __glibcxx_function_requires(_ConvertibleConcept<_InputValueType,
01752                   _OutputValueType>)
01753       __glibcxx_function_requires(_LessThanOpConcept<_InputValueType,
01754                                      _OutputValueType>)
01755       __glibcxx_function_requires(_LessThanComparableConcept<_OutputValueType>)
01756       __glibcxx_requires_valid_range(__first, __last);
01757       __glibcxx_requires_valid_range(__result_first, __result_last);
01758 
01759       return std::__partial_sort_copy(__first, __last,
01760                       __result_first, __result_last,
01761                       __gnu_cxx::__ops::__iter_less_iter());
01762     }
01763 
01764   /**
01765    *  @brief Copy the smallest elements of a sequence using a predicate for
01766    *         comparison.
01767    *  @ingroup sorting_algorithms
01768    *  @param  __first   An input iterator.
01769    *  @param  __last    Another input iterator.
01770    *  @param  __result_first   A random-access iterator.
01771    *  @param  __result_last    Another random-access iterator.
01772    *  @param  __comp    A comparison functor.
01773    *  @return   An iterator indicating the end of the resulting sequence.
01774    *
01775    *  Copies and sorts the smallest N values from the range @p [__first,__last)
01776    *  to the range beginning at @p result_first, where the number of
01777    *  elements to be copied, @p N, is the smaller of @p (__last-__first) and
01778    *  @p (__result_last-__result_first).
01779    *  After the sort if @e i and @e j are iterators in the range
01780    *  @p [__result_first,__result_first+N) such that i precedes j then
01781    *  @p __comp(*j,*i) is false.
01782    *  The value returned is @p __result_first+N.
01783   */
01784   template<typename _InputIterator, typename _RandomAccessIterator,
01785        typename _Compare>
01786     inline _RandomAccessIterator
01787     partial_sort_copy(_InputIterator __first, _InputIterator __last,
01788               _RandomAccessIterator __result_first,
01789               _RandomAccessIterator __result_last,
01790               _Compare __comp)
01791     {
01792       typedef typename iterator_traits<_InputIterator>::value_type
01793     _InputValueType;
01794       typedef typename iterator_traits<_RandomAccessIterator>::value_type
01795     _OutputValueType;
01796       typedef typename iterator_traits<_RandomAccessIterator>::difference_type
01797     _DistanceType;
01798 
01799       // concept requirements
01800       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
01801       __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
01802                   _RandomAccessIterator>)
01803       __glibcxx_function_requires(_ConvertibleConcept<_InputValueType,
01804                   _OutputValueType>)
01805       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
01806                   _InputValueType, _OutputValueType>)
01807       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
01808                   _OutputValueType, _OutputValueType>)
01809       __glibcxx_requires_valid_range(__first, __last);
01810       __glibcxx_requires_valid_range(__result_first, __result_last);
01811 
01812       return std::__partial_sort_copy(__first, __last,
01813                       __result_first, __result_last,
01814                 __gnu_cxx::__ops::__iter_comp_iter(__comp));
01815     }
01816 
01817   /// This is a helper function for the sort routine.
01818   template<typename _RandomAccessIterator, typename _Compare>
01819     void
01820     __unguarded_linear_insert(_RandomAccessIterator __last,
01821                   _Compare __comp)
01822     {
01823       typename iterator_traits<_RandomAccessIterator>::value_type
01824     __val = _GLIBCXX_MOVE(*__last);
01825       _RandomAccessIterator __next = __last;
01826       --__next;
01827       while (__comp(__val, __next))
01828     {
01829       *__last = _GLIBCXX_MOVE(*__next);
01830       __last = __next;
01831       --__next;
01832     }
01833       *__last = _GLIBCXX_MOVE(__val);
01834     }
01835 
01836   /// This is a helper function for the sort routine.
01837   template<typename _RandomAccessIterator, typename _Compare>
01838     void
01839     __insertion_sort(_RandomAccessIterator __first,
01840              _RandomAccessIterator __last, _Compare __comp)
01841     {
01842       if (__first == __last) return;
01843 
01844       for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i)
01845     {
01846       if (__comp(__i, __first))
01847         {
01848           typename iterator_traits<_RandomAccessIterator>::value_type
01849         __val = _GLIBCXX_MOVE(*__i);
01850           _GLIBCXX_MOVE_BACKWARD3(__first, __i, __i + 1);
01851           *__first = _GLIBCXX_MOVE(__val);
01852         }
01853       else
01854         std::__unguarded_linear_insert(__i,
01855                 __gnu_cxx::__ops::__val_comp_iter(__comp));
01856     }
01857     }
01858 
01859   /// This is a helper function for the sort routine.
01860   template<typename _RandomAccessIterator, typename _Compare>
01861     inline void
01862     __unguarded_insertion_sort(_RandomAccessIterator __first,
01863                    _RandomAccessIterator __last, _Compare __comp)
01864     {
01865       for (_RandomAccessIterator __i = __first; __i != __last; ++__i)
01866     std::__unguarded_linear_insert(__i,
01867                 __gnu_cxx::__ops::__val_comp_iter(__comp));
01868     }
01869 
01870   /**
01871    *  @doctodo
01872    *  This controls some aspect of the sort routines.
01873   */
01874   enum { _S_threshold = 16 };
01875 
01876   /// This is a helper function for the sort routine.
01877   template<typename _RandomAccessIterator, typename _Compare>
01878     void
01879     __final_insertion_sort(_RandomAccessIterator __first,
01880                _RandomAccessIterator __last, _Compare __comp)
01881     {
01882       if (__last - __first > int(_S_threshold))
01883     {
01884       std::__insertion_sort(__first, __first + int(_S_threshold), __comp);
01885       std::__unguarded_insertion_sort(__first + int(_S_threshold), __last,
01886                       __comp);
01887     }
01888       else
01889     std::__insertion_sort(__first, __last, __comp);
01890     }
01891 
01892   /// This is a helper function...
01893   template<typename _RandomAccessIterator, typename _Compare>
01894     _RandomAccessIterator
01895     __unguarded_partition(_RandomAccessIterator __first,
01896               _RandomAccessIterator __last,
01897               _RandomAccessIterator __pivot, _Compare __comp)
01898     {
01899       while (true)
01900     {
01901       while (__comp(__first, __pivot))
01902         ++__first;
01903       --__last;
01904       while (__comp(__pivot, __last))
01905         --__last;
01906       if (!(__first < __last))
01907         return __first;
01908       std::iter_swap(__first, __last);
01909       ++__first;
01910     }
01911     }
01912 
01913   /// This is a helper function...
01914   template<typename _RandomAccessIterator, typename _Compare>
01915     inline _RandomAccessIterator
01916     __unguarded_partition_pivot(_RandomAccessIterator __first,
01917                 _RandomAccessIterator __last, _Compare __comp)
01918     {
01919       _RandomAccessIterator __mid = __first + (__last - __first) / 2;
01920       std::__move_median_to_first(__first, __first + 1, __mid, __last - 1,
01921                   __comp);
01922       return std::__unguarded_partition(__first + 1, __last, __first, __comp);
01923     }
01924 
01925   template<typename _RandomAccessIterator, typename _Compare>
01926     inline void
01927     __partial_sort(_RandomAccessIterator __first,
01928            _RandomAccessIterator __middle,
01929            _RandomAccessIterator __last,
01930            _Compare __comp)
01931     {
01932       std::__heap_select(__first, __middle, __last, __comp);
01933       std::__sort_heap(__first, __middle, __comp);
01934     }
01935 
01936   /// This is a helper function for the sort routine.
01937   template<typename _RandomAccessIterator, typename _Size, typename _Compare>
01938     void
01939     __introsort_loop(_RandomAccessIterator __first,
01940              _RandomAccessIterator __last,
01941              _Size __depth_limit, _Compare __comp)
01942     {
01943       while (__last - __first > int(_S_threshold))
01944     {
01945       if (__depth_limit == 0)
01946         {
01947           std::__partial_sort(__first, __last, __last, __comp);
01948           return;
01949         }
01950       --__depth_limit;
01951       _RandomAccessIterator __cut =
01952         std::__unguarded_partition_pivot(__first, __last, __comp);
01953       std::__introsort_loop(__cut, __last, __depth_limit, __comp);
01954       __last = __cut;
01955     }
01956     }
01957 
01958   // sort
01959 
01960   template<typename _RandomAccessIterator, typename _Compare>
01961     inline void
01962     __sort(_RandomAccessIterator __first, _RandomAccessIterator __last,
01963        _Compare __comp)
01964     {
01965       if (__first != __last)
01966     {
01967       std::__introsort_loop(__first, __last,
01968                 std::__lg(__last - __first) * 2,
01969                 __comp);
01970       std::__final_insertion_sort(__first, __last, __comp);
01971     }
01972     }
01973 
01974   template<typename _RandomAccessIterator, typename _Size, typename _Compare>
01975     void
01976     __introselect(_RandomAccessIterator __first, _RandomAccessIterator __nth,
01977           _RandomAccessIterator __last, _Size __depth_limit,
01978           _Compare __comp)
01979     {
01980       while (__last - __first > 3)
01981     {
01982       if (__depth_limit == 0)
01983         {
01984           std::__heap_select(__first, __nth + 1, __last, __comp);
01985           // Place the nth largest element in its final position.
01986           std::iter_swap(__first, __nth);
01987           return;
01988         }
01989       --__depth_limit;
01990       _RandomAccessIterator __cut =
01991         std::__unguarded_partition_pivot(__first, __last, __comp);
01992       if (__cut <= __nth)
01993         __first = __cut;
01994       else
01995         __last = __cut;
01996     }
01997       std::__insertion_sort(__first, __last, __comp);
01998     }
01999 
02000   // nth_element
02001 
02002   // lower_bound moved to stl_algobase.h
02003 
02004   /**
02005    *  @brief Finds the first position in which @p __val could be inserted
02006    *         without changing the ordering.
02007    *  @ingroup binary_search_algorithms
02008    *  @param  __first   An iterator.
02009    *  @param  __last    Another iterator.
02010    *  @param  __val     The search term.
02011    *  @param  __comp    A functor to use for comparisons.
02012    *  @return An iterator pointing to the first element <em>not less
02013    *           than</em> @p __val, or end() if every element is less
02014    *           than @p __val.
02015    *  @ingroup binary_search_algorithms
02016    *
02017    *  The comparison function should have the same effects on ordering as
02018    *  the function used for the initial sort.
02019   */
02020   template<typename _ForwardIterator, typename _Tp, typename _Compare>
02021     inline _ForwardIterator
02022     lower_bound(_ForwardIterator __first, _ForwardIterator __last,
02023         const _Tp& __val, _Compare __comp)
02024     {
02025       typedef typename iterator_traits<_ForwardIterator>::value_type
02026     _ValueType;
02027 
02028       // concept requirements
02029       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
02030       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
02031                   _ValueType, _Tp>)
02032       __glibcxx_requires_partitioned_lower_pred(__first, __last,
02033                         __val, __comp);
02034 
02035       return std::__lower_bound(__first, __last, __val,
02036                 __gnu_cxx::__ops::__iter_comp_val(__comp));
02037     }
02038 
02039   template<typename _ForwardIterator, typename _Tp, typename _Compare>
02040     _ForwardIterator
02041     __upper_bound(_ForwardIterator __first, _ForwardIterator __last,
02042           const _Tp& __val, _Compare __comp)
02043     {
02044       typedef typename iterator_traits<_ForwardIterator>::difference_type
02045     _DistanceType;
02046 
02047       _DistanceType __len = std::distance(__first, __last);
02048 
02049       while (__len > 0)
02050     {
02051       _DistanceType __half = __len >> 1;
02052       _ForwardIterator __middle = __first;
02053       std::advance(__middle, __half);
02054       if (__comp(__val, __middle))
02055         __len = __half;
02056       else
02057         {
02058           __first = __middle;
02059           ++__first;
02060           __len = __len - __half - 1;
02061         }
02062     }
02063       return __first;
02064     }
02065 
02066   /**
02067    *  @brief Finds the last position in which @p __val could be inserted
02068    *         without changing the ordering.
02069    *  @ingroup binary_search_algorithms
02070    *  @param  __first   An iterator.
02071    *  @param  __last    Another iterator.
02072    *  @param  __val     The search term.
02073    *  @return  An iterator pointing to the first element greater than @p __val,
02074    *           or end() if no elements are greater than @p __val.
02075    *  @ingroup binary_search_algorithms
02076   */
02077   template<typename _ForwardIterator, typename _Tp>
02078     inline _ForwardIterator
02079     upper_bound(_ForwardIterator __first, _ForwardIterator __last,
02080         const _Tp& __val)
02081     {
02082       typedef typename iterator_traits<_ForwardIterator>::value_type
02083     _ValueType;
02084 
02085       // concept requirements
02086       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
02087       __glibcxx_function_requires(_LessThanOpConcept<_Tp, _ValueType>)
02088       __glibcxx_requires_partitioned_upper(__first, __last, __val);
02089 
02090       return std::__upper_bound(__first, __last, __val,
02091                 __gnu_cxx::__ops::__val_less_iter());
02092     }
02093 
02094   /**
02095    *  @brief Finds the last position in which @p __val could be inserted
02096    *         without changing the ordering.
02097    *  @ingroup binary_search_algorithms
02098    *  @param  __first   An iterator.
02099    *  @param  __last    Another iterator.
02100    *  @param  __val     The search term.
02101    *  @param  __comp    A functor to use for comparisons.
02102    *  @return  An iterator pointing to the first element greater than @p __val,
02103    *           or end() if no elements are greater than @p __val.
02104    *  @ingroup binary_search_algorithms
02105    *
02106    *  The comparison function should have the same effects on ordering as
02107    *  the function used for the initial sort.
02108   */
02109   template<typename _ForwardIterator, typename _Tp, typename _Compare>
02110     inline _ForwardIterator
02111     upper_bound(_ForwardIterator __first, _ForwardIterator __last,
02112         const _Tp& __val, _Compare __comp)
02113     {
02114       typedef typename iterator_traits<_ForwardIterator>::value_type
02115     _ValueType;
02116 
02117       // concept requirements
02118       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
02119       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
02120                   _Tp, _ValueType>)
02121       __glibcxx_requires_partitioned_upper_pred(__first, __last,
02122                         __val, __comp);
02123 
02124       return std::__upper_bound(__first, __last, __val,
02125                 __gnu_cxx::__ops::__val_comp_iter(__comp));
02126     }
02127 
02128   template<typename _ForwardIterator, typename _Tp,
02129        typename _CompareItTp, typename _CompareTpIt>
02130     pair<_ForwardIterator, _ForwardIterator>
02131     __equal_range(_ForwardIterator __first, _ForwardIterator __last,
02132           const _Tp& __val,
02133           _CompareItTp __comp_it_val, _CompareTpIt __comp_val_it)
02134     {
02135       typedef typename iterator_traits<_ForwardIterator>::difference_type
02136     _DistanceType;
02137 
02138       _DistanceType __len = std::distance(__first, __last);
02139 
02140       while (__len > 0)
02141     {
02142       _DistanceType __half = __len >> 1;
02143       _ForwardIterator __middle = __first;
02144       std::advance(__middle, __half);
02145       if (__comp_it_val(__middle, __val))
02146         {
02147           __first = __middle;
02148           ++__first;
02149           __len = __len - __half - 1;
02150         }
02151       else if (__comp_val_it(__val, __middle))
02152         __len = __half;
02153       else
02154         {
02155           _ForwardIterator __left
02156         = std::__lower_bound(__first, __middle, __val, __comp_it_val);
02157           std::advance(__first, __len);
02158           _ForwardIterator __right
02159         = std::__upper_bound(++__middle, __first, __val, __comp_val_it);
02160           return pair<_ForwardIterator, _ForwardIterator>(__left, __right);
02161         }
02162     }
02163       return pair<_ForwardIterator, _ForwardIterator>(__first, __first);
02164     }
02165 
02166   /**
02167    *  @brief Finds the largest subrange in which @p __val could be inserted
02168    *         at any place in it without changing the ordering.
02169    *  @ingroup binary_search_algorithms
02170    *  @param  __first   An iterator.
02171    *  @param  __last    Another iterator.
02172    *  @param  __val     The search term.
02173    *  @return  An pair of iterators defining the subrange.
02174    *  @ingroup binary_search_algorithms
02175    *
02176    *  This is equivalent to
02177    *  @code
02178    *    std::make_pair(lower_bound(__first, __last, __val),
02179    *                   upper_bound(__first, __last, __val))
02180    *  @endcode
02181    *  but does not actually call those functions.
02182   */
02183   template<typename _ForwardIterator, typename _Tp>
02184     inline pair<_ForwardIterator, _ForwardIterator>
02185     equal_range(_ForwardIterator __first, _ForwardIterator __last,
02186         const _Tp& __val)
02187     {
02188       typedef typename iterator_traits<_ForwardIterator>::value_type
02189     _ValueType;
02190 
02191       // concept requirements
02192       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
02193       __glibcxx_function_requires(_LessThanOpConcept<_ValueType, _Tp>)
02194       __glibcxx_function_requires(_LessThanOpConcept<_Tp, _ValueType>)
02195       __glibcxx_requires_partitioned_lower(__first, __last, __val);
02196       __glibcxx_requires_partitioned_upper(__first, __last, __val);      
02197 
02198       return std::__equal_range(__first, __last, __val,
02199                 __gnu_cxx::__ops::__iter_less_val(),
02200                 __gnu_cxx::__ops::__val_less_iter());
02201     }
02202 
02203   /**
02204    *  @brief Finds the largest subrange in which @p __val could be inserted
02205    *         at any place in it without changing the ordering.
02206    *  @param  __first   An iterator.
02207    *  @param  __last    Another iterator.
02208    *  @param  __val     The search term.
02209    *  @param  __comp    A functor to use for comparisons.
02210    *  @return  An pair of iterators defining the subrange.
02211    *  @ingroup binary_search_algorithms
02212    *
02213    *  This is equivalent to
02214    *  @code
02215    *    std::make_pair(lower_bound(__first, __last, __val, __comp),
02216    *                   upper_bound(__first, __last, __val, __comp))
02217    *  @endcode
02218    *  but does not actually call those functions.
02219   */
02220   template<typename _ForwardIterator, typename _Tp, typename _Compare>
02221     inline pair<_ForwardIterator, _ForwardIterator>
02222     equal_range(_ForwardIterator __first, _ForwardIterator __last,
02223         const _Tp& __val, _Compare __comp)
02224     {
02225       typedef typename iterator_traits<_ForwardIterator>::value_type
02226     _ValueType;
02227 
02228       // concept requirements
02229       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
02230       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
02231                   _ValueType, _Tp>)
02232       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
02233                   _Tp, _ValueType>)
02234       __glibcxx_requires_partitioned_lower_pred(__first, __last,
02235                         __val, __comp);
02236       __glibcxx_requires_partitioned_upper_pred(__first, __last,
02237                         __val, __comp);
02238 
02239       return std::__equal_range(__first, __last, __val,
02240                 __gnu_cxx::__ops::__iter_comp_val(__comp),
02241                 __gnu_cxx::__ops::__val_comp_iter(__comp));
02242     }
02243 
02244   /**
02245    *  @brief Determines whether an element exists in a range.
02246    *  @ingroup binary_search_algorithms
02247    *  @param  __first   An iterator.
02248    *  @param  __last    Another iterator.
02249    *  @param  __val     The search term.
02250    *  @return True if @p __val (or its equivalent) is in [@p
02251    *  __first,@p __last ].
02252    *
02253    *  Note that this does not actually return an iterator to @p __val.  For
02254    *  that, use std::find or a container's specialized find member functions.
02255   */
02256   template<typename _ForwardIterator, typename _Tp>
02257     bool
02258     binary_search(_ForwardIterator __first, _ForwardIterator __last,
02259                   const _Tp& __val)
02260     {
02261       typedef typename iterator_traits<_ForwardIterator>::value_type
02262     _ValueType;
02263 
02264       // concept requirements
02265       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
02266       __glibcxx_function_requires(_LessThanOpConcept<_Tp, _ValueType>)
02267       __glibcxx_requires_partitioned_lower(__first, __last, __val);
02268       __glibcxx_requires_partitioned_upper(__first, __last, __val);
02269 
02270       _ForwardIterator __i
02271     = std::__lower_bound(__first, __last, __val,
02272                  __gnu_cxx::__ops::__iter_less_val());
02273       return __i != __last && !(__val < *__i);
02274     }
02275 
02276   /**
02277    *  @brief Determines whether an element exists in a range.
02278    *  @ingroup binary_search_algorithms
02279    *  @param  __first   An iterator.
02280    *  @param  __last    Another iterator.
02281    *  @param  __val     The search term.
02282    *  @param  __comp    A functor to use for comparisons.
02283    *  @return  True if @p __val (or its equivalent) is in @p [__first,__last].
02284    *
02285    *  Note that this does not actually return an iterator to @p __val.  For
02286    *  that, use std::find or a container's specialized find member functions.
02287    *
02288    *  The comparison function should have the same effects on ordering as
02289    *  the function used for the initial sort.
02290   */
02291   template<typename _ForwardIterator, typename _Tp, typename _Compare>
02292     bool
02293     binary_search(_ForwardIterator __first, _ForwardIterator __last,
02294                   const _Tp& __val, _Compare __comp)
02295     {
02296       typedef typename iterator_traits<_ForwardIterator>::value_type
02297     _ValueType;
02298 
02299       // concept requirements
02300       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
02301       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
02302                   _Tp, _ValueType>)
02303       __glibcxx_requires_partitioned_lower_pred(__first, __last,
02304                         __val, __comp);
02305       __glibcxx_requires_partitioned_upper_pred(__first, __last,
02306                         __val, __comp);
02307 
02308       _ForwardIterator __i
02309     = std::__lower_bound(__first, __last, __val,
02310                  __gnu_cxx::__ops::__iter_comp_val(__comp));
02311       return __i != __last && !bool(__comp(__val, *__i));
02312     }
02313 
02314   // merge
02315 
02316   /// This is a helper function for the __merge_adaptive routines.
02317   template<typename _InputIterator1, typename _InputIterator2,
02318        typename _OutputIterator, typename _Compare>
02319     void
02320     __move_merge_adaptive(_InputIterator1 __first1, _InputIterator1 __last1,
02321               _InputIterator2 __first2, _InputIterator2 __last2,
02322               _OutputIterator __result, _Compare __comp)
02323     {
02324       while (__first1 != __last1 && __first2 != __last2)
02325     {
02326       if (__comp(__first2, __first1))
02327         {
02328           *__result = _GLIBCXX_MOVE(*__first2);
02329           ++__first2;
02330         }
02331       else
02332         {
02333           *__result = _GLIBCXX_MOVE(*__first1);
02334           ++__first1;
02335         }
02336       ++__result;
02337     }
02338       if (__first1 != __last1)
02339     _GLIBCXX_MOVE3(__first1, __last1, __result);
02340     }
02341 
02342   /// This is a helper function for the __merge_adaptive routines.
02343   template<typename _BidirectionalIterator1, typename _BidirectionalIterator2,
02344        typename _BidirectionalIterator3, typename _Compare>
02345     void
02346     __move_merge_adaptive_backward(_BidirectionalIterator1 __first1,
02347                    _BidirectionalIterator1 __last1,
02348                    _BidirectionalIterator2 __first2,
02349                    _BidirectionalIterator2 __last2,
02350                    _BidirectionalIterator3 __result,
02351                    _Compare __comp)
02352     {
02353       if (__first1 == __last1)
02354     {
02355       _GLIBCXX_MOVE_BACKWARD3(__first2, __last2, __result);
02356       return;
02357     }
02358       else if (__first2 == __last2)
02359     return;
02360 
02361       --__last1;
02362       --__last2;
02363       while (true)
02364     {
02365       if (__comp(__last2, __last1))
02366         {
02367           *--__result = _GLIBCXX_MOVE(*__last1);
02368           if (__first1 == __last1)
02369         {
02370           _GLIBCXX_MOVE_BACKWARD3(__first2, ++__last2, __result);
02371           return;
02372         }
02373           --__last1;
02374         }
02375       else
02376         {
02377           *--__result = _GLIBCXX_MOVE(*__last2);
02378           if (__first2 == __last2)
02379         return;
02380           --__last2;
02381         }
02382     }
02383     }
02384 
02385   /// This is a helper function for the merge routines.
02386   template<typename _BidirectionalIterator1, typename _BidirectionalIterator2,
02387        typename _Distance>
02388     _BidirectionalIterator1
02389     __rotate_adaptive(_BidirectionalIterator1 __first,
02390               _BidirectionalIterator1 __middle,
02391               _BidirectionalIterator1 __last,
02392               _Distance __len1, _Distance __len2,
02393               _BidirectionalIterator2 __buffer,
02394               _Distance __buffer_size)
02395     {
02396       _BidirectionalIterator2 __buffer_end;
02397       if (__len1 > __len2 && __len2 <= __buffer_size)
02398     {
02399       if (__len2)
02400         {
02401           __buffer_end = _GLIBCXX_MOVE3(__middle, __last, __buffer);
02402           _GLIBCXX_MOVE_BACKWARD3(__first, __middle, __last);
02403           return _GLIBCXX_MOVE3(__buffer, __buffer_end, __first);
02404         }
02405       else
02406         return __first;
02407     }
02408       else if (__len1 <= __buffer_size)
02409     {
02410       if (__len1)
02411         {
02412           __buffer_end = _GLIBCXX_MOVE3(__first, __middle, __buffer);
02413           _GLIBCXX_MOVE3(__middle, __last, __first);
02414           return _GLIBCXX_MOVE_BACKWARD3(__buffer, __buffer_end, __last);
02415         }
02416       else
02417         return __last;
02418     }
02419       else
02420     {
02421       std::rotate(__first, __middle, __last);
02422       std::advance(__first, std::distance(__middle, __last));
02423       return __first;
02424     }
02425     }
02426 
02427   /// This is a helper function for the merge routines.
02428   template<typename _BidirectionalIterator, typename _Distance, 
02429        typename _Pointer, typename _Compare>
02430     void
02431     __merge_adaptive(_BidirectionalIterator __first,
02432                      _BidirectionalIterator __middle,
02433              _BidirectionalIterator __last,
02434              _Distance __len1, _Distance __len2,
02435              _Pointer __buffer, _Distance __buffer_size,
02436              _Compare __comp)
02437     {
02438       if (__len1 <= __len2 && __len1 <= __buffer_size)
02439     {
02440       _Pointer __buffer_end = _GLIBCXX_MOVE3(__first, __middle, __buffer);
02441       std::__move_merge_adaptive(__buffer, __buffer_end, __middle, __last,
02442                      __first, __comp);
02443     }
02444       else if (__len2 <= __buffer_size)
02445     {
02446       _Pointer __buffer_end = _GLIBCXX_MOVE3(__middle, __last, __buffer);
02447       std::__move_merge_adaptive_backward(__first, __middle, __buffer,
02448                           __buffer_end, __last, __comp);
02449     }
02450       else
02451     {
02452       _BidirectionalIterator __first_cut = __first;
02453       _BidirectionalIterator __second_cut = __middle;
02454       _Distance __len11 = 0;
02455       _Distance __len22 = 0;
02456       if (__len1 > __len2)
02457         {
02458           __len11 = __len1 / 2;
02459           std::advance(__first_cut, __len11);
02460           __second_cut
02461         = std::__lower_bound(__middle, __last, *__first_cut,
02462                      __gnu_cxx::__ops::__iter_comp_val(__comp));
02463           __len22 = std::distance(__middle, __second_cut);
02464         }
02465       else
02466         {
02467           __len22 = __len2 / 2;
02468           std::advance(__second_cut, __len22);
02469           __first_cut
02470         = std::__upper_bound(__first, __middle, *__second_cut,
02471                      __gnu_cxx::__ops::__val_comp_iter(__comp));
02472           __len11 = std::distance(__first, __first_cut);
02473         }
02474       _BidirectionalIterator __new_middle
02475         = std::__rotate_adaptive(__first_cut, __middle, __second_cut,
02476                      __len1 - __len11, __len22, __buffer,
02477                      __buffer_size);
02478       std::__merge_adaptive(__first, __first_cut, __new_middle, __len11,
02479                 __len22, __buffer, __buffer_size, __comp);
02480       std::__merge_adaptive(__new_middle, __second_cut, __last,
02481                 __len1 - __len11,
02482                 __len2 - __len22, __buffer,
02483                 __buffer_size, __comp);
02484     }
02485     }
02486 
02487   /// This is a helper function for the merge routines.
02488   template<typename _BidirectionalIterator, typename _Distance,
02489        typename _Compare>
02490     void
02491     __merge_without_buffer(_BidirectionalIterator __first,
02492                            _BidirectionalIterator __middle,
02493                _BidirectionalIterator __last,
02494                _Distance __len1, _Distance __len2,
02495                _Compare __comp)
02496     {
02497       if (__len1 == 0 || __len2 == 0)
02498     return;
02499       if (__len1 + __len2 == 2)
02500     {
02501       if (__comp(__middle, __first))
02502         std::iter_swap(__first, __middle);
02503       return;
02504     }
02505       _BidirectionalIterator __first_cut = __first;
02506       _BidirectionalIterator __second_cut = __middle;
02507       _Distance __len11 = 0;
02508       _Distance __len22 = 0;
02509       if (__len1 > __len2)
02510     {
02511       __len11 = __len1 / 2;
02512       std::advance(__first_cut, __len11);
02513       __second_cut
02514         = std::__lower_bound(__middle, __last, *__first_cut,
02515                  __gnu_cxx::__ops::__iter_comp_val(__comp));
02516       __len22 = std::distance(__middle, __second_cut);
02517     }
02518       else
02519     {
02520       __len22 = __len2 / 2;
02521       std::advance(__second_cut, __len22);
02522       __first_cut
02523         = std::__upper_bound(__first, __middle, *__second_cut,
02524                  __gnu_cxx::__ops::__val_comp_iter(__comp));
02525       __len11 = std::distance(__first, __first_cut);
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     inline pair<const _Tp&, const _Tp&>
03298     minmax(const _Tp& __a, const _Tp& __b)
03299     {
03300       // concept requirements
03301       __glibcxx_function_requires(_LessThanComparableConcept<_Tp>)
03302 
03303       return __b < __a ? pair<const _Tp&, const _Tp&>(__b, __a)
03304                    : pair<const _Tp&, const _Tp&>(__a, __b);
03305     }
03306 
03307   /**
03308    *  @brief  Determines min and max at once as an ordered pair.
03309    *  @ingroup sorting_algorithms
03310    *  @param  __a  A thing of arbitrary type.
03311    *  @param  __b  Another thing of arbitrary type.
03312    *  @param  __comp  A @link comparison_functors comparison functor @endlink.
03313    *  @return A pair(__b, __a) if __b is smaller than __a, pair(__a,
03314    *  __b) otherwise.
03315   */
03316   template<typename _Tp, typename _Compare>
03317     inline pair<const _Tp&, const _Tp&>
03318     minmax(const _Tp& __a, const _Tp& __b, _Compare __comp)
03319     {
03320       return __comp(__b, __a) ? pair<const _Tp&, const _Tp&>(__b, __a)
03321                           : pair<const _Tp&, const _Tp&>(__a, __b);
03322     }
03323 
03324   template<typename _ForwardIterator, typename _Compare>
03325     pair<_ForwardIterator, _ForwardIterator>
03326     __minmax_element(_ForwardIterator __first, _ForwardIterator __last,
03327              _Compare __comp)
03328     {
03329       _ForwardIterator __next = __first;
03330       if (__first == __last
03331       || ++__next == __last)
03332     return std::make_pair(__first, __first);
03333 
03334       _ForwardIterator __min, __max;
03335       if (__comp(__next, __first))
03336     {
03337       __min = __next;
03338       __max = __first;
03339     }
03340       else
03341     {
03342       __min = __first;
03343       __max = __next;
03344     }
03345 
03346       __first = __next;
03347       ++__first;
03348 
03349       while (__first != __last)
03350     {
03351       __next = __first;
03352       if (++__next == __last)
03353         {
03354           if (__comp(__first, __min))
03355         __min = __first;
03356           else if (!__comp(__first, __max))
03357         __max = __first;
03358           break;
03359         }
03360 
03361       if (__comp(__next, __first))
03362         {
03363           if (__comp(__next, __min))
03364         __min = __next;
03365           if (!__comp(__first, __max))
03366         __max = __first;
03367         }
03368       else
03369         {
03370           if (__comp(__first, __min))
03371         __min = __first;
03372           if (!__comp(__next, __max))
03373         __max = __next;
03374         }
03375 
03376       __first = __next;
03377       ++__first;
03378     }
03379 
03380       return std::make_pair(__min, __max);
03381     }
03382 
03383   /**
03384    *  @brief  Return a pair of iterators pointing to the minimum and maximum
03385    *          elements in a range.
03386    *  @ingroup sorting_algorithms
03387    *  @param  __first  Start of range.
03388    *  @param  __last   End of range.
03389    *  @return  make_pair(m, M), where m is the first iterator i in 
03390    *           [__first, __last) such that no other element in the range is
03391    *           smaller, and where M is the last iterator i in [__first, __last)
03392    *           such that no other element in the range is larger.
03393   */
03394   template<typename _ForwardIterator>
03395     inline pair<_ForwardIterator, _ForwardIterator>
03396     minmax_element(_ForwardIterator __first, _ForwardIterator __last)
03397     {
03398       // concept requirements
03399       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
03400       __glibcxx_function_requires(_LessThanComparableConcept<
03401         typename iterator_traits<_ForwardIterator>::value_type>)
03402       __glibcxx_requires_valid_range(__first, __last);
03403 
03404       return std::__minmax_element(__first, __last,
03405                    __gnu_cxx::__ops::__iter_less_iter());
03406     }
03407 
03408   /**
03409    *  @brief  Return a pair of iterators pointing to the minimum and maximum
03410    *          elements in a range.
03411    *  @ingroup sorting_algorithms
03412    *  @param  __first  Start of range.
03413    *  @param  __last   End of range.
03414    *  @param  __comp   Comparison functor.
03415    *  @return  make_pair(m, M), where m is the first iterator i in 
03416    *           [__first, __last) such that no other element in the range is
03417    *           smaller, and where M is the last iterator i in [__first, __last)
03418    *           such that no other element in the range is larger.
03419   */
03420   template<typename _ForwardIterator, typename _Compare>
03421     inline pair<_ForwardIterator, _ForwardIterator>
03422     minmax_element(_ForwardIterator __first, _ForwardIterator __last,
03423            _Compare __comp)
03424     {
03425       // concept requirements
03426       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
03427       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
03428         typename iterator_traits<_ForwardIterator>::value_type,
03429         typename iterator_traits<_ForwardIterator>::value_type>)
03430       __glibcxx_requires_valid_range(__first, __last);
03431 
03432       return std::__minmax_element(__first, __last,
03433                    __gnu_cxx::__ops::__iter_comp_iter(__comp));
03434     }
03435 
03436   // N2722 + DR 915.
03437   template<typename _Tp>
03438     inline _Tp
03439     min(initializer_list<_Tp> __l)
03440     { return *std::min_element(__l.begin(), __l.end()); }
03441 
03442   template<typename _Tp, typename _Compare>
03443     inline _Tp
03444     min(initializer_list<_Tp> __l, _Compare __comp)
03445     { return *std::min_element(__l.begin(), __l.end(), __comp); }
03446 
03447   template<typename _Tp>
03448     inline _Tp
03449     max(initializer_list<_Tp> __l)
03450     { return *std::max_element(__l.begin(), __l.end()); }
03451 
03452   template<typename _Tp, typename _Compare>
03453     inline _Tp
03454     max(initializer_list<_Tp> __l, _Compare __comp)
03455     { return *std::max_element(__l.begin(), __l.end(), __comp); }
03456 
03457   template<typename _Tp>
03458     inline pair<_Tp, _Tp>
03459     minmax(initializer_list<_Tp> __l)
03460     {
03461       pair<const _Tp*, const _Tp*> __p =
03462     std::minmax_element(__l.begin(), __l.end());
03463       return std::make_pair(*__p.first, *__p.second);
03464     }
03465 
03466   template<typename _Tp, typename _Compare>
03467     inline pair<_Tp, _Tp>
03468     minmax(initializer_list<_Tp> __l, _Compare __comp)
03469     {
03470       pair<const _Tp*, const _Tp*> __p =
03471     std::minmax_element(__l.begin(), __l.end(), __comp);
03472       return std::make_pair(*__p.first, *__p.second);
03473     }
03474 
03475   template<typename _ForwardIterator1, typename _ForwardIterator2,
03476        typename _BinaryPredicate>
03477     bool
03478     __is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
03479              _ForwardIterator2 __first2, _BinaryPredicate __pred)
03480     {
03481       // Efficiently compare identical prefixes:  O(N) if sequences
03482       // have the same elements in the same order.
03483       for (; __first1 != __last1; ++__first1, ++__first2)
03484     if (!__pred(__first1, __first2))
03485       break;
03486 
03487       if (__first1 == __last1)
03488     return true;
03489 
03490       // Establish __last2 assuming equal ranges by iterating over the
03491       // rest of the list.
03492       _ForwardIterator2 __last2 = __first2;
03493       std::advance(__last2, std::distance(__first1, __last1));
03494       for (_ForwardIterator1 __scan = __first1; __scan != __last1; ++__scan)
03495     {
03496       if (__scan != std::__find_if(__first1, __scan,
03497               __gnu_cxx::__ops::__iter_comp_iter(__pred, __scan)))
03498         continue; // We've seen this one before.
03499       
03500       auto __matches
03501         = std::__count_if(__first2, __last2,
03502             __gnu_cxx::__ops::__iter_comp_iter(__pred, __scan));
03503       if (0 == __matches ||
03504           std::__count_if(__scan, __last1,
03505             __gnu_cxx::__ops::__iter_comp_iter(__pred, __scan))
03506           != __matches)
03507         return false;
03508     }
03509       return true;
03510     }
03511 
03512   /**
03513    *  @brief  Checks whether a permutation of the second sequence is equal
03514    *          to the first sequence.
03515    *  @ingroup non_mutating_algorithms
03516    *  @param  __first1  Start of first range.
03517    *  @param  __last1   End of first range.
03518    *  @param  __first2  Start of second range.
03519    *  @return true if there exists a permutation of the elements in the range
03520    *          [__first2, __first2 + (__last1 - __first1)), beginning with 
03521    *          ForwardIterator2 begin, such that equal(__first1, __last1, begin)
03522    *          returns true; otherwise, returns false.
03523   */
03524   template<typename _ForwardIterator1, typename _ForwardIterator2>
03525     inline bool
03526     is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
03527            _ForwardIterator2 __first2)
03528     {
03529       // concept requirements
03530       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator1>)
03531       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator2>)
03532       __glibcxx_function_requires(_EqualOpConcept<
03533         typename iterator_traits<_ForwardIterator1>::value_type,
03534         typename iterator_traits<_ForwardIterator2>::value_type>)
03535       __glibcxx_requires_valid_range(__first1, __last1);
03536 
03537       return std::__is_permutation(__first1, __last1, __first2,
03538                    __gnu_cxx::__ops::__iter_equal_to_iter());
03539     }
03540 
03541   /**
03542    *  @brief  Checks whether a permutation of the second sequence is equal
03543    *          to the first sequence.
03544    *  @ingroup non_mutating_algorithms
03545    *  @param  __first1  Start of first range.
03546    *  @param  __last1   End of first range.
03547    *  @param  __first2  Start of second range.
03548    *  @param  __pred    A binary predicate.
03549    *  @return true if there exists a permutation of the elements in
03550    *          the range [__first2, __first2 + (__last1 - __first1)),
03551    *          beginning with ForwardIterator2 begin, such that
03552    *          equal(__first1, __last1, __begin, __pred) returns true;
03553    *          otherwise, returns false.
03554   */
03555   template<typename _ForwardIterator1, typename _ForwardIterator2,
03556        typename _BinaryPredicate>
03557     inline bool
03558     is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
03559            _ForwardIterator2 __first2, _BinaryPredicate __pred)
03560     {
03561       // concept requirements
03562       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator1>)
03563       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator2>)
03564       __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
03565         typename iterator_traits<_ForwardIterator1>::value_type,
03566         typename iterator_traits<_ForwardIterator2>::value_type>)
03567       __glibcxx_requires_valid_range(__first1, __last1);
03568 
03569       return std::__is_permutation(__first1, __last1, __first2,
03570                    __gnu_cxx::__ops::__iter_comp_iter(__pred));
03571     }
03572 
03573 #if __cplusplus > 201103L
03574   template<typename _ForwardIterator1, typename _ForwardIterator2,
03575        typename _BinaryPredicate>
03576     bool
03577     __is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
03578              _ForwardIterator2 __first2, _ForwardIterator2 __last2,
03579              _BinaryPredicate __pred)
03580     {
03581       using _Cat1
03582     = typename iterator_traits<_ForwardIterator1>::iterator_category;
03583       using _Cat2
03584     = typename iterator_traits<_ForwardIterator2>::iterator_category;
03585       using _It1_is_RA = is_same<_Cat1, random_access_iterator_tag>;
03586       using _It2_is_RA = is_same<_Cat2, random_access_iterator_tag>;
03587       constexpr bool __ra_iters = _It1_is_RA() && _It2_is_RA();
03588       if (__ra_iters)
03589     {
03590       auto __d1 = std::distance(__first1, __last1);
03591       auto __d2 = std::distance(__first2, __last2);
03592       if (__d1 != __d2)
03593         return false;
03594     }
03595 
03596       // Efficiently compare identical prefixes:  O(N) if sequences
03597       // have the same elements in the same order.
03598       for (; __first1 != __last1 && __first2 != __last2;
03599       ++__first1, ++__first2)
03600     if (!__pred(__first1, __first2))
03601       break;
03602 
03603       if (__ra_iters)
03604     {
03605       if (__first1 == __last1)
03606         return true;
03607     }
03608       else
03609     {
03610       auto __d1 = std::distance(__first1, __last1);
03611       auto __d2 = std::distance(__first2, __last2);
03612       if (__d1 == 0 && __d2 == 0)
03613         return true;
03614       if (__d1 != __d2)
03615         return false;
03616     }
03617 
03618       for (_ForwardIterator1 __scan = __first1; __scan != __last1; ++__scan)
03619     {
03620       if (__scan != std::__find_if(__first1, __scan,
03621             __gnu_cxx::__ops::__iter_comp_iter(__pred, __scan)))
03622         continue; // We've seen this one before.
03623 
03624       auto __matches = std::__count_if(__first2, __last2,
03625         __gnu_cxx::__ops::__iter_comp_iter(__pred, __scan));
03626       if (0 == __matches
03627           || std::__count_if(__scan, __last1,
03628             __gnu_cxx::__ops::__iter_comp_iter(__pred, __scan))
03629           != __matches)
03630         return false;
03631     }
03632       return true;
03633     }
03634 
03635   /**
03636    *  @brief  Checks whether a permutaion of the second sequence is equal
03637    *          to the first sequence.
03638    *  @ingroup non_mutating_algorithms
03639    *  @param  __first1  Start of first range.
03640    *  @param  __last1   End of first range.
03641    *  @param  __first2  Start of second range.
03642    *  @param  __last2   End of first range.
03643    *  @return true if there exists a permutation of the elements in the range
03644    *          [__first2, __last2), beginning with ForwardIterator2 begin,
03645    *          such that equal(__first1, __last1, begin) returns true;
03646    *          otherwise, returns false.
03647   */
03648   template<typename _ForwardIterator1, typename _ForwardIterator2>
03649     inline bool
03650     is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
03651            _ForwardIterator2 __first2, _ForwardIterator2 __last2)
03652     {
03653       __glibcxx_requires_valid_range(__first1, __last1);
03654       __glibcxx_requires_valid_range(__first2, __last2);
03655 
03656       return
03657     std::__is_permutation(__first1, __last1, __first2, __last2,
03658                   __gnu_cxx::__ops::__iter_equal_to_iter());
03659     }
03660 
03661   /**
03662    *  @brief  Checks whether a permutation of the second sequence is equal
03663    *          to the first sequence.
03664    *  @ingroup non_mutating_algorithms
03665    *  @param  __first1  Start of first range.
03666    *  @param  __last1   End of first range.
03667    *  @param  __first2  Start of second range.
03668    *  @param  __last2   End of first range.
03669    *  @param  __pred    A binary predicate.
03670    *  @return true if there exists a permutation of the elements in the range
03671    *          [__first2, __last2), beginning with ForwardIterator2 begin,
03672    *          such that equal(__first1, __last1, __begin, __pred) returns true;
03673    *          otherwise, returns false.
03674   */
03675   template<typename _ForwardIterator1, typename _ForwardIterator2,
03676        typename _BinaryPredicate>
03677     inline bool
03678     is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
03679            _ForwardIterator2 __first2, _ForwardIterator2 __last2,
03680            _BinaryPredicate __pred)
03681     {
03682       __glibcxx_requires_valid_range(__first1, __last1);
03683       __glibcxx_requires_valid_range(__first2, __last2);
03684 
03685       return std::__is_permutation(__first1, __last1, __first2, __last2,
03686                    __gnu_cxx::__ops::__iter_comp_iter(__pred));
03687     }
03688 #endif
03689 
03690 #ifdef _GLIBCXX_USE_C99_STDINT_TR1
03691   /**
03692    *  @brief Shuffle the elements of a sequence using a uniform random
03693    *         number generator.
03694    *  @ingroup mutating_algorithms
03695    *  @param  __first   A forward iterator.
03696    *  @param  __last    A forward iterator.
03697    *  @param  __g       A UniformRandomNumberGenerator (26.5.1.3).
03698    *  @return  Nothing.
03699    *
03700    *  Reorders the elements in the range @p [__first,__last) using @p __g to
03701    *  provide random numbers.
03702   */
03703   template<typename _RandomAccessIterator,
03704        typename _UniformRandomNumberGenerator>
03705     void
03706     shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last,
03707         _UniformRandomNumberGenerator&& __g)
03708     {
03709       // concept requirements
03710       __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
03711         _RandomAccessIterator>)
03712       __glibcxx_requires_valid_range(__first, __last);
03713 
03714       if (__first == __last)
03715     return;
03716 
03717       typedef typename iterator_traits<_RandomAccessIterator>::difference_type
03718     _DistanceType;
03719 
03720       typedef typename std::make_unsigned<_DistanceType>::type __ud_type;
03721       typedef typename std::uniform_int_distribution<__ud_type> __distr_type;
03722       typedef typename __distr_type::param_type __p_type;
03723       __distr_type __d;
03724 
03725       for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i)
03726     std::iter_swap(__i, __first + __d(__g, __p_type(0, __i - __first)));
03727     }
03728 #endif
03729 
03730 #endif // C++11
03731 
03732 _GLIBCXX_END_NAMESPACE_VERSION
03733 
03734 _GLIBCXX_BEGIN_NAMESPACE_ALGO
03735 
03736   /**
03737    *  @brief Apply a function to every element of a sequence.
03738    *  @ingroup non_mutating_algorithms
03739    *  @param  __first  An input iterator.
03740    *  @param  __last   An input iterator.
03741    *  @param  __f      A unary function object.
03742    *  @return   @p __f (std::move(@p __f) in C++0x).
03743    *
03744    *  Applies the function object @p __f to each element in the range
03745    *  @p [first,last).  @p __f must not modify the order of the sequence.
03746    *  If @p __f has a return value it is ignored.
03747   */
03748   template<typename _InputIterator, typename _Function>
03749     _Function
03750     for_each(_InputIterator __first, _InputIterator __last, _Function __f)
03751     {
03752       // concept requirements
03753       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
03754       __glibcxx_requires_valid_range(__first, __last);
03755       for (; __first != __last; ++__first)
03756     __f(*__first);
03757       return _GLIBCXX_MOVE(__f);
03758     }
03759 
03760   /**
03761    *  @brief Find the first occurrence of a value in a sequence.
03762    *  @ingroup non_mutating_algorithms
03763    *  @param  __first  An input iterator.
03764    *  @param  __last   An input iterator.
03765    *  @param  __val    The value to find.
03766    *  @return   The first iterator @c i in the range @p [__first,__last)
03767    *  such that @c *i == @p __val, or @p __last if no such iterator exists.
03768   */
03769   template<typename _InputIterator, typename _Tp>
03770     inline _InputIterator
03771     find(_InputIterator __first, _InputIterator __last,
03772      const _Tp& __val)
03773     {
03774       // concept requirements
03775       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
03776       __glibcxx_function_requires(_EqualOpConcept<
03777         typename iterator_traits<_InputIterator>::value_type, _Tp>)
03778       __glibcxx_requires_valid_range(__first, __last);
03779       return std::__find_if(__first, __last,
03780                 __gnu_cxx::__ops::__iter_equals_val(__val));
03781     }
03782 
03783   /**
03784    *  @brief Find the first element in a sequence for which a
03785    *         predicate is true.
03786    *  @ingroup non_mutating_algorithms
03787    *  @param  __first  An input iterator.
03788    *  @param  __last   An input iterator.
03789    *  @param  __pred   A predicate.
03790    *  @return   The first iterator @c i in the range @p [__first,__last)
03791    *  such that @p __pred(*i) is true, or @p __last if no such iterator exists.
03792   */
03793   template<typename _InputIterator, typename _Predicate>
03794     inline _InputIterator
03795     find_if(_InputIterator __first, _InputIterator __last,
03796         _Predicate __pred)
03797     {
03798       // concept requirements
03799       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
03800       __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
03801           typename iterator_traits<_InputIterator>::value_type>)
03802       __glibcxx_requires_valid_range(__first, __last);
03803 
03804       return std::__find_if(__first, __last,
03805                 __gnu_cxx::__ops::__pred_iter(__pred));
03806     }
03807 
03808   /**
03809    *  @brief  Find element from a set in a sequence.
03810    *  @ingroup non_mutating_algorithms
03811    *  @param  __first1  Start of range to search.
03812    *  @param  __last1   End of range to search.
03813    *  @param  __first2  Start of match candidates.
03814    *  @param  __last2   End of match candidates.
03815    *  @return   The first iterator @c i in the range
03816    *  @p [__first1,__last1) such that @c *i == @p *(i2) such that i2 is an
03817    *  iterator in [__first2,__last2), or @p __last1 if no such iterator exists.
03818    *
03819    *  Searches the range @p [__first1,__last1) for an element that is
03820    *  equal to some element in the range [__first2,__last2).  If
03821    *  found, returns an iterator in the range [__first1,__last1),
03822    *  otherwise returns @p __last1.
03823   */
03824   template<typename _InputIterator, typename _ForwardIterator>
03825     _InputIterator
03826     find_first_of(_InputIterator __first1, _InputIterator __last1,
03827           _ForwardIterator __first2, _ForwardIterator __last2)
03828     {
03829       // concept requirements
03830       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
03831       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
03832       __glibcxx_function_requires(_EqualOpConcept<
03833         typename iterator_traits<_InputIterator>::value_type,
03834         typename iterator_traits<_ForwardIterator>::value_type>)
03835       __glibcxx_requires_valid_range(__first1, __last1);
03836       __glibcxx_requires_valid_range(__first2, __last2);
03837 
03838       for (; __first1 != __last1; ++__first1)
03839     for (_ForwardIterator __iter = __first2; __iter != __last2; ++__iter)
03840       if (*__first1 == *__iter)
03841         return __first1;
03842       return __last1;
03843     }
03844 
03845   /**
03846    *  @brief  Find element from a set in a sequence using a predicate.
03847    *  @ingroup non_mutating_algorithms
03848    *  @param  __first1  Start of range to search.
03849    *  @param  __last1   End of range to search.
03850    *  @param  __first2  Start of match candidates.
03851    *  @param  __last2   End of match candidates.
03852    *  @param  __comp    Predicate to use.
03853    *  @return   The first iterator @c i in the range
03854    *  @p [__first1,__last1) such that @c comp(*i, @p *(i2)) is true
03855    *  and i2 is an iterator in [__first2,__last2), or @p __last1 if no
03856    *  such iterator exists.
03857    *
03858 
03859    *  Searches the range @p [__first1,__last1) for an element that is
03860    *  equal to some element in the range [__first2,__last2).  If
03861    *  found, returns an iterator in the range [__first1,__last1),
03862    *  otherwise returns @p __last1.
03863   */
03864   template<typename _InputIterator, typename _ForwardIterator,
03865        typename _BinaryPredicate>
03866     _InputIterator
03867     find_first_of(_InputIterator __first1, _InputIterator __last1,
03868           _ForwardIterator __first2, _ForwardIterator __last2,
03869           _BinaryPredicate __comp)
03870     {
03871       // concept requirements
03872       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
03873       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
03874       __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
03875         typename iterator_traits<_InputIterator>::value_type,
03876         typename iterator_traits<_ForwardIterator>::value_type>)
03877       __glibcxx_requires_valid_range(__first1, __last1);
03878       __glibcxx_requires_valid_range(__first2, __last2);
03879 
03880       for (; __first1 != __last1; ++__first1)
03881     for (_ForwardIterator __iter = __first2; __iter != __last2; ++__iter)
03882       if (__comp(*__first1, *__iter))
03883         return __first1;
03884       return __last1;
03885     }
03886 
03887   /**
03888    *  @brief Find two adjacent values in a sequence that are equal.
03889    *  @ingroup non_mutating_algorithms
03890    *  @param  __first  A forward iterator.
03891    *  @param  __last   A forward iterator.
03892    *  @return   The first iterator @c i such that @c i and @c i+1 are both
03893    *  valid iterators in @p [__first,__last) and such that @c *i == @c *(i+1),
03894    *  or @p __last if no such iterator exists.
03895   */
03896   template<typename _ForwardIterator>
03897     inline _ForwardIterator
03898     adjacent_find(_ForwardIterator __first, _ForwardIterator __last)
03899     {
03900       // concept requirements
03901       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
03902       __glibcxx_function_requires(_EqualityComparableConcept<
03903         typename iterator_traits<_ForwardIterator>::value_type>)
03904       __glibcxx_requires_valid_range(__first, __last);
03905 
03906       return std::__adjacent_find(__first, __last,
03907                   __gnu_cxx::__ops::__iter_equal_to_iter());
03908     }
03909 
03910   /**
03911    *  @brief Find two adjacent values in a sequence using a predicate.
03912    *  @ingroup non_mutating_algorithms
03913    *  @param  __first         A forward iterator.
03914    *  @param  __last          A forward iterator.
03915    *  @param  __binary_pred   A binary predicate.
03916    *  @return   The first iterator @c i such that @c i and @c i+1 are both
03917    *  valid iterators in @p [__first,__last) and such that
03918    *  @p __binary_pred(*i,*(i+1)) is true, or @p __last if no such iterator
03919    *  exists.
03920   */
03921   template<typename _ForwardIterator, typename _BinaryPredicate>
03922     inline _ForwardIterator
03923     adjacent_find(_ForwardIterator __first, _ForwardIterator __last,
03924           _BinaryPredicate __binary_pred)
03925     {
03926       // concept requirements
03927       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
03928       __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
03929         typename iterator_traits<_ForwardIterator>::value_type,
03930         typename iterator_traits<_ForwardIterator>::value_type>)
03931       __glibcxx_requires_valid_range(__first, __last);
03932 
03933       return std::__adjacent_find(__first, __last,
03934             __gnu_cxx::__ops::__iter_comp_iter(__binary_pred));
03935     }
03936 
03937   /**
03938    *  @brief Count the number of copies of a value in a sequence.
03939    *  @ingroup non_mutating_algorithms
03940    *  @param  __first  An input iterator.
03941    *  @param  __last   An input iterator.
03942    *  @param  __value  The value to be counted.
03943    *  @return   The number of iterators @c i in the range @p [__first,__last)
03944    *  for which @c *i == @p __value
03945   */
03946   template<typename _InputIterator, typename _Tp>
03947     inline typename iterator_traits<_InputIterator>::difference_type
03948     count(_InputIterator __first, _InputIterator __last, const _Tp& __value)
03949     {
03950       // concept requirements
03951       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
03952       __glibcxx_function_requires(_EqualOpConcept<
03953         typename iterator_traits<_InputIterator>::value_type, _Tp>)
03954       __glibcxx_requires_valid_range(__first, __last);
03955 
03956       return std::__count_if(__first, __last,
03957                  __gnu_cxx::__ops::__iter_equals_val(__value));
03958     }
03959 
03960   /**
03961    *  @brief Count the elements of a sequence for which a predicate is true.
03962    *  @ingroup non_mutating_algorithms
03963    *  @param  __first  An input iterator.
03964    *  @param  __last   An input iterator.
03965    *  @param  __pred   A predicate.
03966    *  @return   The number of iterators @c i in the range @p [__first,__last)
03967    *  for which @p __pred(*i) is true.
03968   */
03969   template<typename _InputIterator, typename _Predicate>
03970     inline typename iterator_traits<_InputIterator>::difference_type
03971     count_if(_InputIterator __first, _InputIterator __last, _Predicate __pred)
03972     {
03973       // concept requirements
03974       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
03975       __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
03976         typename iterator_traits<_InputIterator>::value_type>)
03977       __glibcxx_requires_valid_range(__first, __last);
03978 
03979       return std::__count_if(__first, __last,
03980                  __gnu_cxx::__ops::__pred_iter(__pred));
03981     }
03982 
03983   /**
03984    *  @brief Search a sequence for a matching sub-sequence.
03985    *  @ingroup non_mutating_algorithms
03986    *  @param  __first1  A forward iterator.
03987    *  @param  __last1   A forward iterator.
03988    *  @param  __first2  A forward iterator.
03989    *  @param  __last2   A forward iterator.
03990    *  @return The first iterator @c i in the range @p
03991    *  [__first1,__last1-(__last2-__first2)) such that @c *(i+N) == @p
03992    *  *(__first2+N) for each @c N in the range @p
03993    *  [0,__last2-__first2), or @p __last1 if no such iterator exists.
03994    *
03995    *  Searches the range @p [__first1,__last1) for a sub-sequence that
03996    *  compares equal value-by-value with the sequence given by @p
03997    *  [__first2,__last2) and returns an iterator to the first element
03998    *  of the sub-sequence, or @p __last1 if the sub-sequence is not
03999    *  found.
04000    *
04001    *  Because the sub-sequence must lie completely within the range @p
04002    *  [__first1,__last1) it must start at a position less than @p
04003    *  __last1-(__last2-__first2) where @p __last2-__first2 is the
04004    *  length of the sub-sequence.
04005    *
04006    *  This means that the returned iterator @c i will be in the range
04007    *  @p [__first1,__last1-(__last2-__first2))
04008   */
04009   template<typename _ForwardIterator1, typename _ForwardIterator2>
04010     inline _ForwardIterator1
04011     search(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
04012        _ForwardIterator2 __first2, _ForwardIterator2 __last2)
04013     {
04014       // concept requirements
04015       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator1>)
04016       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator2>)
04017       __glibcxx_function_requires(_EqualOpConcept<
04018         typename iterator_traits<_ForwardIterator1>::value_type,
04019         typename iterator_traits<_ForwardIterator2>::value_type>)
04020       __glibcxx_requires_valid_range(__first1, __last1);
04021       __glibcxx_requires_valid_range(__first2, __last2);
04022 
04023       return std::__search(__first1, __last1, __first2, __last2,
04024                __gnu_cxx::__ops::__iter_equal_to_iter());
04025     }
04026 
04027   /**
04028    *  @brief Search a sequence for a matching sub-sequence using a predicate.
04029    *  @ingroup non_mutating_algorithms
04030    *  @param  __first1     A forward iterator.
04031    *  @param  __last1      A forward iterator.
04032    *  @param  __first2     A forward iterator.
04033    *  @param  __last2      A forward iterator.
04034    *  @param  __predicate  A binary predicate.
04035    *  @return   The first iterator @c i in the range
04036    *  @p [__first1,__last1-(__last2-__first2)) such that
04037    *  @p __predicate(*(i+N),*(__first2+N)) is true for each @c N in the range
04038    *  @p [0,__last2-__first2), or @p __last1 if no such iterator exists.
04039    *
04040    *  Searches the range @p [__first1,__last1) for a sub-sequence that
04041    *  compares equal value-by-value with the sequence given by @p
04042    *  [__first2,__last2), using @p __predicate to determine equality,
04043    *  and returns an iterator to the first element of the
04044    *  sub-sequence, or @p __last1 if no such iterator exists.
04045    *
04046    *  @see search(_ForwardIter1, _ForwardIter1, _ForwardIter2, _ForwardIter2)
04047   */
04048   template<typename _ForwardIterator1, typename _ForwardIterator2,
04049        typename _BinaryPredicate>
04050     inline _ForwardIterator1
04051     search(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
04052        _ForwardIterator2 __first2, _ForwardIterator2 __last2,
04053        _BinaryPredicate  __predicate)
04054     {
04055       // concept requirements
04056       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator1>)
04057       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator2>)
04058       __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
04059         typename iterator_traits<_ForwardIterator1>::value_type,
04060         typename iterator_traits<_ForwardIterator2>::value_type>)
04061       __glibcxx_requires_valid_range(__first1, __last1);
04062       __glibcxx_requires_valid_range(__first2, __last2);
04063 
04064       return std::__search(__first1, __last1, __first2, __last2,
04065                __gnu_cxx::__ops::__iter_comp_iter(__predicate));
04066     }
04067 
04068   /**
04069    *  @brief Search a sequence for a number of consecutive values.
04070    *  @ingroup non_mutating_algorithms
04071    *  @param  __first  A forward iterator.
04072    *  @param  __last   A forward iterator.
04073    *  @param  __count  The number of consecutive values.
04074    *  @param  __val    The value to find.
04075    *  @return The first iterator @c i in the range @p
04076    *  [__first,__last-__count) such that @c *(i+N) == @p __val for
04077    *  each @c N in the range @p [0,__count), or @p __last if no such
04078    *  iterator exists.
04079    *
04080    *  Searches the range @p [__first,__last) for @p count consecutive elements
04081    *  equal to @p __val.
04082   */
04083   template<typename _ForwardIterator, typename _Integer, typename _Tp>
04084     inline _ForwardIterator
04085     search_n(_ForwardIterator __first, _ForwardIterator __last,
04086          _Integer __count, const _Tp& __val)
04087     {
04088       // concept requirements
04089       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
04090       __glibcxx_function_requires(_EqualOpConcept<
04091         typename iterator_traits<_ForwardIterator>::value_type, _Tp>)
04092       __glibcxx_requires_valid_range(__first, __last);
04093 
04094       return std::__search_n(__first, __last, __count,
04095                  __gnu_cxx::__ops::__iter_equals_val(__val));
04096     }
04097 
04098 
04099   /**
04100    *  @brief Search a sequence for a number of consecutive values using a
04101    *         predicate.
04102    *  @ingroup non_mutating_algorithms
04103    *  @param  __first        A forward iterator.
04104    *  @param  __last         A forward iterator.
04105    *  @param  __count        The number of consecutive values.
04106    *  @param  __val          The value to find.
04107    *  @param  __binary_pred  A binary predicate.
04108    *  @return The first iterator @c i in the range @p
04109    *  [__first,__last-__count) such that @p
04110    *  __binary_pred(*(i+N),__val) is true for each @c N in the range
04111    *  @p [0,__count), or @p __last if no such iterator exists.
04112    *
04113    *  Searches the range @p [__first,__last) for @p __count
04114    *  consecutive elements for which the predicate returns true.
04115   */
04116   template<typename _ForwardIterator, typename _Integer, typename _Tp,
04117            typename _BinaryPredicate>
04118     inline _ForwardIterator
04119     search_n(_ForwardIterator __first, _ForwardIterator __last,
04120          _Integer __count, const _Tp& __val,
04121          _BinaryPredicate __binary_pred)
04122     {
04123       // concept requirements
04124       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
04125       __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
04126         typename iterator_traits<_ForwardIterator>::value_type, _Tp>)
04127       __glibcxx_requires_valid_range(__first, __last);
04128 
04129       return std::__search_n(__first, __last, __count,
04130         __gnu_cxx::__ops::__iter_comp_val(__binary_pred, __val));
04131     }
04132 
04133 
04134   /**
04135    *  @brief Perform an operation on a sequence.
04136    *  @ingroup mutating_algorithms
04137    *  @param  __first     An input iterator.
04138    *  @param  __last      An input iterator.
04139    *  @param  __result    An output iterator.
04140    *  @param  __unary_op  A unary operator.
04141    *  @return   An output iterator equal to @p __result+(__last-__first).
04142    *
04143    *  Applies the operator to each element in the input range and assigns
04144    *  the results to successive elements of the output sequence.
04145    *  Evaluates @p *(__result+N)=unary_op(*(__first+N)) for each @c N in the
04146    *  range @p [0,__last-__first).
04147    *
04148    *  @p unary_op must not alter its argument.
04149   */
04150   template<typename _InputIterator, typename _OutputIterator,
04151        typename _UnaryOperation>
04152     _OutputIterator
04153     transform(_InputIterator __first, _InputIterator __last,
04154           _OutputIterator __result, _UnaryOperation __unary_op)
04155     {
04156       // concept requirements
04157       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
04158       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
04159             // "the type returned by a _UnaryOperation"
04160             __typeof__(__unary_op(*__first))>)
04161       __glibcxx_requires_valid_range(__first, __last);
04162 
04163       for (; __first != __last; ++__first, ++__result)
04164     *__result = __unary_op(*__first);
04165       return __result;
04166     }
04167 
04168   /**
04169    *  @brief Perform an operation on corresponding elements of two sequences.
04170    *  @ingroup mutating_algorithms
04171    *  @param  __first1     An input iterator.
04172    *  @param  __last1      An input iterator.
04173    *  @param  __first2     An input iterator.
04174    *  @param  __result     An output iterator.
04175    *  @param  __binary_op  A binary operator.
04176    *  @return   An output iterator equal to @p result+(last-first).
04177    *
04178    *  Applies the operator to the corresponding elements in the two
04179    *  input ranges and assigns the results to successive elements of the
04180    *  output sequence.
04181    *  Evaluates @p
04182    *  *(__result+N)=__binary_op(*(__first1+N),*(__first2+N)) for each
04183    *  @c N in the range @p [0,__last1-__first1).
04184    *
04185    *  @p binary_op must not alter either of its arguments.
04186   */
04187   template<typename _InputIterator1, typename _InputIterator2,
04188        typename _OutputIterator, typename _BinaryOperation>
04189     _OutputIterator
04190     transform(_InputIterator1 __first1, _InputIterator1 __last1,
04191           _InputIterator2 __first2, _OutputIterator __result,
04192           _BinaryOperation __binary_op)
04193     {
04194       // concept requirements
04195       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
04196       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
04197       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
04198             // "the type returned by a _BinaryOperation"
04199             __typeof__(__binary_op(*__first1,*__first2))>)
04200       __glibcxx_requires_valid_range(__first1, __last1);
04201 
04202       for (; __first1 != __last1; ++__first1, ++__first2, ++__result)
04203     *__result = __binary_op(*__first1, *__first2);
04204       return __result;
04205     }
04206 
04207   /**
04208    *  @brief Replace each occurrence of one value in a sequence with another
04209    *         value.
04210    *  @ingroup mutating_algorithms
04211    *  @param  __first      A forward iterator.
04212    *  @param  __last       A forward iterator.
04213    *  @param  __old_value  The value to be replaced.
04214    *  @param  __new_value  The replacement value.
04215    *  @return   replace() returns no value.
04216    *
04217    *  For each iterator @c i in the range @p [__first,__last) if @c *i ==
04218    *  @p __old_value then the assignment @c *i = @p __new_value is performed.
04219   */
04220   template<typename _ForwardIterator, typename _Tp>
04221     void
04222     replace(_ForwardIterator __first, _ForwardIterator __last,
04223         const _Tp& __old_value, const _Tp& __new_value)
04224     {
04225       // concept requirements
04226       __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
04227                   _ForwardIterator>)
04228       __glibcxx_function_requires(_EqualOpConcept<
04229         typename iterator_traits<_ForwardIterator>::value_type, _Tp>)
04230       __glibcxx_function_requires(_ConvertibleConcept<_Tp,
04231         typename iterator_traits<_ForwardIterator>::value_type>)
04232       __glibcxx_requires_valid_range(__first, __last);
04233 
04234       for (; __first != __last; ++__first)
04235     if (*__first == __old_value)
04236       *__first = __new_value;
04237     }
04238 
04239   /**
04240    *  @brief Replace each value in a sequence for which a predicate returns
04241    *         true with another value.
04242    *  @ingroup mutating_algorithms
04243    *  @param  __first      A forward iterator.
04244    *  @param  __last       A forward iterator.
04245    *  @param  __pred       A predicate.
04246    *  @param  __new_value  The replacement value.
04247    *  @return   replace_if() returns no value.
04248    *
04249    *  For each iterator @c i in the range @p [__first,__last) if @p __pred(*i)
04250    *  is true then the assignment @c *i = @p __new_value is performed.
04251   */
04252   template<typename _ForwardIterator, typename _Predicate, typename _Tp>
04253     void
04254     replace_if(_ForwardIterator __first, _ForwardIterator __last,
04255            _Predicate __pred, const _Tp& __new_value)
04256     {
04257       // concept requirements
04258       __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
04259                   _ForwardIterator>)
04260       __glibcxx_function_requires(_ConvertibleConcept<_Tp,
04261         typename iterator_traits<_ForwardIterator>::value_type>)
04262       __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
04263         typename iterator_traits<_ForwardIterator>::value_type>)
04264       __glibcxx_requires_valid_range(__first, __last);
04265 
04266       for (; __first != __last; ++__first)
04267     if (__pred(*__first))
04268       *__first = __new_value;
04269     }
04270 
04271   /**
04272    *  @brief Assign the result of a function object to each value in a
04273    *         sequence.
04274    *  @ingroup mutating_algorithms
04275    *  @param  __first  A forward iterator.
04276    *  @param  __last   A forward iterator.
04277    *  @param  __gen    A function object taking no arguments and returning
04278    *                 std::iterator_traits<_ForwardIterator>::value_type
04279    *  @return   generate() returns no value.
04280    *
04281    *  Performs the assignment @c *i = @p __gen() for each @c i in the range
04282    *  @p [__first,__last).
04283   */
04284   template<typename _ForwardIterator, typename _Generator>
04285     void
04286     generate(_ForwardIterator __first, _ForwardIterator __last,
04287          _Generator __gen)
04288     {
04289       // concept requirements
04290       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
04291       __glibcxx_function_requires(_GeneratorConcept<_Generator,
04292         typename iterator_traits<_ForwardIterator>::value_type>)
04293       __glibcxx_requires_valid_range(__first, __last);
04294 
04295       for (; __first != __last; ++__first)
04296     *__first = __gen();
04297     }
04298 
04299   /**
04300    *  @brief Assign the result of a function object to each value in a
04301    *         sequence.
04302    *  @ingroup mutating_algorithms
04303    *  @param  __first  A forward iterator.
04304    *  @param  __n      The length of the sequence.
04305    *  @param  __gen    A function object taking no arguments and returning
04306    *                 std::iterator_traits<_ForwardIterator>::value_type
04307    *  @return   The end of the sequence, @p __first+__n
04308    *
04309    *  Performs the assignment @c *i = @p __gen() for each @c i in the range
04310    *  @p [__first,__first+__n).
04311    *
04312    *  _GLIBCXX_RESOLVE_LIB_DEFECTS
04313    *  DR 865. More algorithms that throw away information
04314   */
04315   template<typename _OutputIterator, typename _Size, typename _Generator>
04316     _OutputIterator
04317     generate_n(_OutputIterator __first, _Size __n, _Generator __gen)
04318     {
04319       // concept requirements
04320       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
04321             // "the type returned by a _Generator"
04322             __typeof__(__gen())>)
04323 
04324       for (__decltype(__n + 0) __niter = __n;
04325        __niter > 0; --__niter, ++__first)
04326     *__first = __gen();
04327       return __first;
04328     }
04329 
04330   /**
04331    *  @brief Copy a sequence, removing consecutive duplicate values.
04332    *  @ingroup mutating_algorithms
04333    *  @param  __first   An input iterator.
04334    *  @param  __last    An input iterator.
04335    *  @param  __result  An output iterator.
04336    *  @return   An iterator designating the end of the resulting sequence.
04337    *
04338    *  Copies each element in the range @p [__first,__last) to the range
04339    *  beginning at @p __result, except that only the first element is copied
04340    *  from groups of consecutive elements that compare equal.
04341    *  unique_copy() is stable, so the relative order of elements that are
04342    *  copied is unchanged.
04343    *
04344    *  _GLIBCXX_RESOLVE_LIB_DEFECTS
04345    *  DR 241. Does unique_copy() require CopyConstructible and Assignable?
04346    *  
04347    *  _GLIBCXX_RESOLVE_LIB_DEFECTS
04348    *  DR 538. 241 again: Does unique_copy() require CopyConstructible and 
04349    *  Assignable?
04350   */
04351   template<typename _InputIterator, typename _OutputIterator>
04352     inline _OutputIterator
04353     unique_copy(_InputIterator __first, _InputIterator __last,
04354         _OutputIterator __result)
04355     {
04356       // concept requirements
04357       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
04358       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
04359         typename iterator_traits<_InputIterator>::value_type>)
04360       __glibcxx_function_requires(_EqualityComparableConcept<
04361         typename iterator_traits<_InputIterator>::value_type>)
04362       __glibcxx_requires_valid_range(__first, __last);
04363 
04364       if (__first == __last)
04365     return __result;
04366       return std::__unique_copy(__first, __last, __result,
04367                 __gnu_cxx::__ops::__iter_equal_to_iter(),
04368                 std::__iterator_category(__first),
04369                 std::__iterator_category(__result));
04370     }
04371 
04372   /**
04373    *  @brief Copy a sequence, removing consecutive values using a predicate.
04374    *  @ingroup mutating_algorithms
04375    *  @param  __first        An input iterator.
04376    *  @param  __last         An input iterator.
04377    *  @param  __result       An output iterator.
04378    *  @param  __binary_pred  A binary predicate.
04379    *  @return   An iterator designating the end of the resulting sequence.
04380    *
04381    *  Copies each element in the range @p [__first,__last) to the range
04382    *  beginning at @p __result, except that only the first element is copied
04383    *  from groups of consecutive elements for which @p __binary_pred returns
04384    *  true.
04385    *  unique_copy() is stable, so the relative order of elements that are
04386    *  copied is unchanged.
04387    *
04388    *  _GLIBCXX_RESOLVE_LIB_DEFECTS
04389    *  DR 241. Does unique_copy() require CopyConstructible and Assignable?
04390   */
04391   template<typename _InputIterator, typename _OutputIterator,
04392        typename _BinaryPredicate>
04393     inline _OutputIterator
04394     unique_copy(_InputIterator __first, _InputIterator __last,
04395         _OutputIterator __result,
04396         _BinaryPredicate __binary_pred)
04397     {
04398       // concept requirements -- predicates checked later
04399       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
04400       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
04401         typename iterator_traits<_InputIterator>::value_type>)
04402       __glibcxx_requires_valid_range(__first, __last);
04403 
04404       if (__first == __last)
04405     return __result;
04406       return std::__unique_copy(__first, __last, __result,
04407             __gnu_cxx::__ops::__iter_comp_iter(__binary_pred),
04408                 std::__iterator_category(__first),
04409                 std::__iterator_category(__result));
04410     }
04411 
04412   /**
04413    *  @brief Randomly shuffle the elements of a sequence.
04414    *  @ingroup mutating_algorithms
04415    *  @param  __first   A forward iterator.
04416    *  @param  __last    A forward iterator.
04417    *  @return  Nothing.
04418    *
04419    *  Reorder the elements in the range @p [__first,__last) using a random
04420    *  distribution, so that every possible ordering of the sequence is
04421    *  equally likely.
04422   */
04423   template<typename _RandomAccessIterator>
04424     inline void
04425     random_shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last)
04426     {
04427       // concept requirements
04428       __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
04429         _RandomAccessIterator>)
04430       __glibcxx_requires_valid_range(__first, __last);
04431 
04432       if (__first != __last)
04433     for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i)
04434       {
04435         _RandomAccessIterator __j = __first
04436                     + std::rand() % ((__i - __first) + 1);
04437         if (__i != __j)
04438           std::iter_swap(__i, __j);
04439       }
04440     }
04441 
04442   /**
04443    *  @brief Shuffle the elements of a sequence using a random number
04444    *         generator.
04445    *  @ingroup mutating_algorithms
04446    *  @param  __first   A forward iterator.
04447    *  @param  __last    A forward iterator.
04448    *  @param  __rand    The RNG functor or function.
04449    *  @return  Nothing.
04450    *
04451    *  Reorders the elements in the range @p [__first,__last) using @p __rand to
04452    *  provide a random distribution. Calling @p __rand(N) for a positive
04453    *  integer @p N should return a randomly chosen integer from the
04454    *  range [0,N).
04455   */
04456   template<typename _RandomAccessIterator, typename _RandomNumberGenerator>
04457     void
04458     random_shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last,
04459 #if __cplusplus >= 201103L
04460            _RandomNumberGenerator&& __rand)
04461 #else
04462            _RandomNumberGenerator& __rand)
04463 #endif
04464     {
04465       // concept requirements
04466       __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
04467         _RandomAccessIterator>)
04468       __glibcxx_requires_valid_range(__first, __last);
04469 
04470       if (__first == __last)
04471     return;
04472       for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i)
04473     {
04474       _RandomAccessIterator __j = __first + __rand((__i - __first) + 1);
04475       if (__i != __j)
04476         std::iter_swap(__i, __j);
04477     }
04478     }
04479 
04480 
04481   /**
04482    *  @brief Move elements for which a predicate is true to the beginning
04483    *         of a sequence.
04484    *  @ingroup mutating_algorithms
04485    *  @param  __first   A forward iterator.
04486    *  @param  __last    A forward iterator.
04487    *  @param  __pred    A predicate functor.
04488    *  @return  An iterator @p middle such that @p __pred(i) is true for each
04489    *  iterator @p i in the range @p [__first,middle) and false for each @p i
04490    *  in the range @p [middle,__last).
04491    *
04492    *  @p __pred must not modify its operand. @p partition() does not preserve
04493    *  the relative ordering of elements in each group, use
04494    *  @p stable_partition() if this is needed.
04495   */
04496   template<typename _ForwardIterator, typename _Predicate>
04497     inline _ForwardIterator
04498     partition(_ForwardIterator __first, _ForwardIterator __last,
04499           _Predicate   __pred)
04500     {
04501       // concept requirements
04502       __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
04503                   _ForwardIterator>)
04504       __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
04505         typename iterator_traits<_ForwardIterator>::value_type>)
04506       __glibcxx_requires_valid_range(__first, __last);
04507 
04508       return std::__partition(__first, __last, __pred,
04509                   std::__iterator_category(__first));
04510     }
04511 
04512 
04513   /**
04514    *  @brief Sort the smallest elements of a sequence.
04515    *  @ingroup sorting_algorithms
04516    *  @param  __first   An iterator.
04517    *  @param  __middle  Another iterator.
04518    *  @param  __last    Another iterator.
04519    *  @return  Nothing.
04520    *
04521    *  Sorts the smallest @p (__middle-__first) elements in the range
04522    *  @p [first,last) and moves them to the range @p [__first,__middle). The
04523    *  order of the remaining elements in the range @p [__middle,__last) is
04524    *  undefined.
04525    *  After the sort if @e i and @e j are iterators in the range
04526    *  @p [__first,__middle) such that i precedes j and @e k is an iterator in
04527    *  the range @p [__middle,__last) then *j<*i and *k<*i are both false.
04528   */
04529   template<typename _RandomAccessIterator>
04530     inline void
04531     partial_sort(_RandomAccessIterator __first,
04532          _RandomAccessIterator __middle,
04533          _RandomAccessIterator __last)
04534     {
04535       // concept requirements
04536       __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
04537         _RandomAccessIterator>)
04538       __glibcxx_function_requires(_LessThanComparableConcept<
04539         typename iterator_traits<_RandomAccessIterator>::value_type>)
04540       __glibcxx_requires_valid_range(__first, __middle);
04541       __glibcxx_requires_valid_range(__middle, __last);
04542 
04543       std::__partial_sort(__first, __middle, __last,
04544               __gnu_cxx::__ops::__iter_less_iter());
04545     }
04546 
04547   /**
04548    *  @brief Sort the smallest elements of a sequence using a predicate
04549    *         for comparison.
04550    *  @ingroup sorting_algorithms
04551    *  @param  __first   An iterator.
04552    *  @param  __middle  Another iterator.
04553    *  @param  __last    Another iterator.
04554    *  @param  __comp    A comparison functor.
04555    *  @return  Nothing.
04556    *
04557    *  Sorts the smallest @p (__middle-__first) elements in the range
04558    *  @p [__first,__last) and moves them to the range @p [__first,__middle). The
04559    *  order of the remaining elements in the range @p [__middle,__last) is
04560    *  undefined.
04561    *  After the sort if @e i and @e j are iterators in the range
04562    *  @p [__first,__middle) such that i precedes j and @e k is an iterator in
04563    *  the range @p [__middle,__last) then @p *__comp(j,*i) and @p __comp(*k,*i)
04564    *  are both false.
04565   */
04566   template<typename _RandomAccessIterator, typename _Compare>
04567     inline void
04568     partial_sort(_RandomAccessIterator __first,
04569          _RandomAccessIterator __middle,
04570          _RandomAccessIterator __last,
04571          _Compare __comp)
04572     {
04573       // concept requirements
04574       __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
04575         _RandomAccessIterator>)
04576       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
04577         typename iterator_traits<_RandomAccessIterator>::value_type,
04578         typename iterator_traits<_RandomAccessIterator>::value_type>)
04579       __glibcxx_requires_valid_range(__first, __middle);
04580       __glibcxx_requires_valid_range(__middle, __last);
04581 
04582       std::__partial_sort(__first, __middle, __last,
04583               __gnu_cxx::__ops::__iter_comp_iter(__comp));
04584     }
04585 
04586   /**
04587    *  @brief Sort a sequence just enough to find a particular position.
04588    *  @ingroup sorting_algorithms
04589    *  @param  __first   An iterator.
04590    *  @param  __nth     Another iterator.
04591    *  @param  __last    Another iterator.
04592    *  @return  Nothing.
04593    *
04594    *  Rearranges the elements in the range @p [__first,__last) so that @p *__nth
04595    *  is the same element that would have been in that position had the
04596    *  whole sequence been sorted. The elements either side of @p *__nth are
04597    *  not completely sorted, but for any iterator @e i in the range
04598    *  @p [__first,__nth) and any iterator @e j in the range @p [__nth,__last) it
04599    *  holds that *j < *i is false.
04600   */
04601   template<typename _RandomAccessIterator>
04602     inline void
04603     nth_element(_RandomAccessIterator __first, _RandomAccessIterator __nth,
04604         _RandomAccessIterator __last)
04605     {
04606       // concept requirements
04607       __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
04608                   _RandomAccessIterator>)
04609       __glibcxx_function_requires(_LessThanComparableConcept<
04610         typename iterator_traits<_RandomAccessIterator>::value_type>)
04611       __glibcxx_requires_valid_range(__first, __nth);
04612       __glibcxx_requires_valid_range(__nth, __last);
04613 
04614       if (__first == __last || __nth == __last)
04615     return;
04616 
04617       std::__introselect(__first, __nth, __last,
04618              std::__lg(__last - __first) * 2,
04619              __gnu_cxx::__ops::__iter_less_iter());
04620     }
04621 
04622   /**
04623    *  @brief Sort a sequence just enough to find a particular position
04624    *         using a predicate for comparison.
04625    *  @ingroup sorting_algorithms
04626    *  @param  __first   An iterator.
04627    *  @param  __nth     Another iterator.
04628    *  @param  __last    Another iterator.
04629    *  @param  __comp    A comparison functor.
04630    *  @return  Nothing.
04631    *
04632    *  Rearranges the elements in the range @p [__first,__last) so that @p *__nth
04633    *  is the same element that would have been in that position had the
04634    *  whole sequence been sorted. The elements either side of @p *__nth are
04635    *  not completely sorted, but for any iterator @e i in the range
04636    *  @p [__first,__nth) and any iterator @e j in the range @p [__nth,__last) it
04637    *  holds that @p __comp(*j,*i) is false.
04638   */
04639   template<typename _RandomAccessIterator, typename _Compare>
04640     inline void
04641     nth_element(_RandomAccessIterator __first, _RandomAccessIterator __nth,
04642         _RandomAccessIterator __last, _Compare __comp)
04643     {
04644       // concept requirements
04645       __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
04646                   _RandomAccessIterator>)
04647       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
04648         typename iterator_traits<_RandomAccessIterator>::value_type,
04649         typename iterator_traits<_RandomAccessIterator>::value_type>)
04650       __glibcxx_requires_valid_range(__first, __nth);
04651       __glibcxx_requires_valid_range(__nth, __last);
04652 
04653       if (__first == __last || __nth == __last)
04654     return;
04655 
04656       std::__introselect(__first, __nth, __last,
04657              std::__lg(__last - __first) * 2,
04658              __gnu_cxx::__ops::__iter_comp_iter(__comp));
04659     }
04660 
04661   /**
04662    *  @brief Sort the elements of a sequence.
04663    *  @ingroup sorting_algorithms
04664    *  @param  __first   An iterator.
04665    *  @param  __last    Another iterator.
04666    *  @return  Nothing.
04667    *
04668    *  Sorts the elements in the range @p [__first,__last) in ascending order,
04669    *  such that for each iterator @e i in the range @p [__first,__last-1),  
04670    *  *(i+1)<*i is false.
04671    *
04672    *  The relative ordering of equivalent elements is not preserved, use
04673    *  @p stable_sort() if this is needed.
04674   */
04675   template<typename _RandomAccessIterator>
04676     inline void
04677     sort(_RandomAccessIterator __first, _RandomAccessIterator __last)
04678     {
04679       // concept requirements
04680       __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
04681         _RandomAccessIterator>)
04682       __glibcxx_function_requires(_LessThanComparableConcept<
04683         typename iterator_traits<_RandomAccessIterator>::value_type>)
04684       __glibcxx_requires_valid_range(__first, __last);
04685 
04686       std::__sort(__first, __last, __gnu_cxx::__ops::__iter_less_iter());
04687     }
04688 
04689   /**
04690    *  @brief Sort the elements of a sequence using a predicate for comparison.
04691    *  @ingroup sorting_algorithms
04692    *  @param  __first   An iterator.
04693    *  @param  __last    Another iterator.
04694    *  @param  __comp    A comparison functor.
04695    *  @return  Nothing.
04696    *
04697    *  Sorts the elements in the range @p [__first,__last) in ascending order,
04698    *  such that @p __comp(*(i+1),*i) is false for every iterator @e i in the
04699    *  range @p [__first,__last-1).
04700    *
04701    *  The relative ordering of equivalent elements is not preserved, use
04702    *  @p stable_sort() if this is needed.
04703   */
04704   template<typename _RandomAccessIterator, typename _Compare>
04705     inline void
04706     sort(_RandomAccessIterator __first, _RandomAccessIterator __last,
04707      _Compare __comp)
04708     {
04709       // concept requirements
04710       __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
04711         _RandomAccessIterator>)
04712       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
04713         typename iterator_traits<_RandomAccessIterator>::value_type,
04714         typename iterator_traits<_RandomAccessIterator>::value_type>)
04715       __glibcxx_requires_valid_range(__first, __last);
04716 
04717       std::__sort(__first, __last, __gnu_cxx::__ops::__iter_comp_iter(__comp));
04718     }
04719 
04720   template<typename _InputIterator1, typename _InputIterator2,
04721        typename _OutputIterator, typename _Compare>
04722     _OutputIterator
04723     __merge(_InputIterator1 __first1, _InputIterator1 __last1,
04724         _InputIterator2 __first2, _InputIterator2 __last2,
04725         _OutputIterator __result, _Compare __comp)
04726     {
04727       while (__first1 != __last1 && __first2 != __last2)
04728     {
04729       if (__comp(__first2, __first1))
04730         {
04731           *__result = *__first2;
04732           ++__first2;
04733         }
04734       else
04735         {
04736           *__result = *__first1;
04737           ++__first1;
04738         }
04739       ++__result;
04740     }
04741       return std::copy(__first2, __last2,
04742                std::copy(__first1, __last1, __result));
04743     }
04744 
04745   /**
04746    *  @brief Merges two sorted ranges.
04747    *  @ingroup sorting_algorithms
04748    *  @param  __first1  An iterator.
04749    *  @param  __first2  Another iterator.
04750    *  @param  __last1   Another iterator.
04751    *  @param  __last2   Another iterator.
04752    *  @param  __result  An iterator pointing to the end of the merged range.
04753    *  @return         An iterator pointing to the first element <em>not less
04754    *                  than</em> @e val.
04755    *
04756    *  Merges the ranges @p [__first1,__last1) and @p [__first2,__last2) into
04757    *  the sorted range @p [__result, __result + (__last1-__first1) +
04758    *  (__last2-__first2)).  Both input ranges must be sorted, and the
04759    *  output range must not overlap with either of the input ranges.
04760    *  The sort is @e stable, that is, for equivalent elements in the
04761    *  two ranges, elements from the first range will always come
04762    *  before elements from the second.
04763   */
04764   template<typename _InputIterator1, typename _InputIterator2,
04765        typename _OutputIterator>
04766     inline _OutputIterator
04767     merge(_InputIterator1 __first1, _InputIterator1 __last1,
04768       _InputIterator2 __first2, _InputIterator2 __last2,
04769       _OutputIterator __result)
04770     {
04771       // concept requirements
04772       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
04773       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
04774       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
04775         typename iterator_traits<_InputIterator1>::value_type>)
04776       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
04777         typename iterator_traits<_InputIterator2>::value_type>)
04778       __glibcxx_function_requires(_LessThanOpConcept<
04779         typename iterator_traits<_InputIterator2>::value_type,
04780         typename iterator_traits<_InputIterator1>::value_type>) 
04781       __glibcxx_requires_sorted_set(__first1, __last1, __first2);
04782       __glibcxx_requires_sorted_set(__first2, __last2, __first1);
04783 
04784       return _GLIBCXX_STD_A::__merge(__first1, __last1,
04785                      __first2, __last2, __result,
04786                      __gnu_cxx::__ops::__iter_less_iter());
04787     }
04788 
04789   /**
04790    *  @brief Merges two sorted ranges.
04791    *  @ingroup sorting_algorithms
04792    *  @param  __first1  An iterator.
04793    *  @param  __first2  Another iterator.
04794    *  @param  __last1   Another iterator.
04795    *  @param  __last2   Another iterator.
04796    *  @param  __result  An iterator pointing to the end of the merged range.
04797    *  @param  __comp    A functor to use for comparisons.
04798    *  @return         An iterator pointing to the first element "not less
04799    *                  than" @e val.
04800    *
04801    *  Merges the ranges @p [__first1,__last1) and @p [__first2,__last2) into
04802    *  the sorted range @p [__result, __result + (__last1-__first1) +
04803    *  (__last2-__first2)).  Both input ranges must be sorted, and the
04804    *  output range must not overlap with either of the input ranges.
04805    *  The sort is @e stable, that is, for equivalent elements in the
04806    *  two ranges, elements from the first range will always come
04807    *  before elements from the second.
04808    *
04809    *  The comparison function should have the same effects on ordering as
04810    *  the function used for the initial sort.
04811   */
04812   template<typename _InputIterator1, typename _InputIterator2,
04813        typename _OutputIterator, typename _Compare>
04814     inline _OutputIterator
04815     merge(_InputIterator1 __first1, _InputIterator1 __last1,
04816       _InputIterator2 __first2, _InputIterator2 __last2,
04817       _OutputIterator __result, _Compare __comp)
04818     {
04819       // concept requirements
04820       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
04821       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
04822       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
04823         typename iterator_traits<_InputIterator1>::value_type>)
04824       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
04825         typename iterator_traits<_InputIterator2>::value_type>)
04826       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
04827         typename iterator_traits<_InputIterator2>::value_type,
04828         typename iterator_traits<_InputIterator1>::value_type>)
04829       __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp);
04830       __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp);
04831 
04832       return _GLIBCXX_STD_A::__merge(__first1, __last1,
04833                 __first2, __last2, __result,
04834                 __gnu_cxx::__ops::__iter_comp_iter(__comp));
04835     }
04836 
04837   template<typename _RandomAccessIterator, typename _Compare>
04838     inline void
04839     __stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last,
04840           _Compare __comp)
04841     {
04842       typedef typename iterator_traits<_RandomAccessIterator>::value_type
04843     _ValueType;
04844       typedef typename iterator_traits<_RandomAccessIterator>::difference_type
04845     _DistanceType;
04846 
04847       typedef _Temporary_buffer<_RandomAccessIterator, _ValueType> _TmpBuf;
04848       _TmpBuf __buf(__first, __last);
04849 
04850       if (__buf.begin() == 0)
04851     std::__inplace_stable_sort(__first, __last, __comp);
04852       else
04853     std::__stable_sort_adaptive(__first, __last, __buf.begin(),
04854                     _DistanceType(__buf.size()), __comp);
04855     }
04856 
04857   /**
04858    *  @brief Sort the elements of a sequence, preserving the relative order
04859    *         of equivalent elements.
04860    *  @ingroup sorting_algorithms
04861    *  @param  __first   An iterator.
04862    *  @param  __last    Another iterator.
04863    *  @return  Nothing.
04864    *
04865    *  Sorts the elements in the range @p [__first,__last) in ascending order,
04866    *  such that for each iterator @p i in the range @p [__first,__last-1),
04867    *  @p *(i+1)<*i is false.
04868    *
04869    *  The relative ordering of equivalent elements is preserved, so any two
04870    *  elements @p x and @p y in the range @p [__first,__last) such that
04871    *  @p x<y is false and @p y<x is false will have the same relative
04872    *  ordering after calling @p stable_sort().
04873   */
04874   template<typename _RandomAccessIterator>
04875     inline void
04876     stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last)
04877     {
04878       // concept requirements
04879       __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
04880         _RandomAccessIterator>)
04881       __glibcxx_function_requires(_LessThanComparableConcept<
04882         typename iterator_traits<_RandomAccessIterator>::value_type>)
04883       __glibcxx_requires_valid_range(__first, __last);
04884 
04885       _GLIBCXX_STD_A::__stable_sort(__first, __last,
04886                     __gnu_cxx::__ops::__iter_less_iter());
04887     }
04888 
04889   /**
04890    *  @brief Sort the elements of a sequence using a predicate for comparison,
04891    *         preserving the relative order of equivalent elements.
04892    *  @ingroup sorting_algorithms
04893    *  @param  __first   An iterator.
04894    *  @param  __last    Another iterator.
04895    *  @param  __comp    A comparison functor.
04896    *  @return  Nothing.
04897    *
04898    *  Sorts the elements in the range @p [__first,__last) in ascending order,
04899    *  such that for each iterator @p i in the range @p [__first,__last-1),
04900    *  @p __comp(*(i+1),*i) is false.
04901    *
04902    *  The relative ordering of equivalent elements is preserved, so any two
04903    *  elements @p x and @p y in the range @p [__first,__last) such that
04904    *  @p __comp(x,y) is false and @p __comp(y,x) is false will have the same
04905    *  relative ordering after calling @p stable_sort().
04906   */
04907   template<typename _RandomAccessIterator, typename _Compare>
04908     inline void
04909     stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last,
04910         _Compare __comp)
04911     {
04912       // concept requirements
04913       __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
04914         _RandomAccessIterator>)
04915       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
04916         typename iterator_traits<_RandomAccessIterator>::value_type,
04917         typename iterator_traits<_RandomAccessIterator>::value_type>)
04918       __glibcxx_requires_valid_range(__first, __last);
04919 
04920       _GLIBCXX_STD_A::__stable_sort(__first, __last,
04921                     __gnu_cxx::__ops::__iter_comp_iter(__comp));
04922     }
04923 
04924   template<typename _InputIterator1, typename _InputIterator2,
04925        typename _OutputIterator,
04926        typename _Compare>
04927     _OutputIterator
04928     __set_union(_InputIterator1 __first1, _InputIterator1 __last1,
04929         _InputIterator2 __first2, _InputIterator2 __last2,
04930         _OutputIterator __result, _Compare __comp)
04931     {
04932       while (__first1 != __last1 && __first2 != __last2)
04933     {
04934       if (__comp(__first1, __first2))
04935         {
04936           *__result = *__first1;
04937           ++__first1;
04938         }
04939       else if (__comp(__first2, __first1))
04940         {
04941           *__result = *__first2;
04942           ++__first2;
04943         }
04944       else
04945         {
04946           *__result = *__first1;
04947           ++__first1;
04948           ++__first2;
04949         }
04950       ++__result;
04951     }
04952       return std::copy(__first2, __last2,
04953                std::copy(__first1, __last1, __result));
04954     }
04955 
04956   /**
04957    *  @brief Return the union of two sorted ranges.
04958    *  @ingroup set_algorithms
04959    *  @param  __first1  Start of first range.
04960    *  @param  __last1   End of first range.
04961    *  @param  __first2  Start of second range.
04962    *  @param  __last2   End of second range.
04963    *  @return  End of the output range.
04964    *  @ingroup set_algorithms
04965    *
04966    *  This operation iterates over both ranges, copying elements present in
04967    *  each range in order to the output range.  Iterators increment for each
04968    *  range.  When the current element of one range is less than the other,
04969    *  that element is copied and the iterator advanced.  If an element is
04970    *  contained in both ranges, the element from the first range is copied and
04971    *  both ranges advance.  The output range may not overlap either input
04972    *  range.
04973   */
04974   template<typename _InputIterator1, typename _InputIterator2,
04975        typename _OutputIterator>
04976     inline _OutputIterator
04977     set_union(_InputIterator1 __first1, _InputIterator1 __last1,
04978           _InputIterator2 __first2, _InputIterator2 __last2,
04979           _OutputIterator __result)
04980     {
04981       // concept requirements
04982       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
04983       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
04984       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
04985         typename iterator_traits<_InputIterator1>::value_type>)
04986       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
04987         typename iterator_traits<_InputIterator2>::value_type>)
04988       __glibcxx_function_requires(_LessThanOpConcept<
04989         typename iterator_traits<_InputIterator1>::value_type,
04990         typename iterator_traits<_InputIterator2>::value_type>)
04991       __glibcxx_function_requires(_LessThanOpConcept<
04992         typename iterator_traits<_InputIterator2>::value_type,
04993         typename iterator_traits<_InputIterator1>::value_type>)
04994       __glibcxx_requires_sorted_set(__first1, __last1, __first2);
04995       __glibcxx_requires_sorted_set(__first2, __last2, __first1);
04996 
04997       return _GLIBCXX_STD_A::__set_union(__first1, __last1,
04998                 __first2, __last2, __result,
04999                 __gnu_cxx::__ops::__iter_less_iter());
05000     }
05001 
05002   /**
05003    *  @brief Return the union of two sorted ranges using a comparison functor.
05004    *  @ingroup set_algorithms
05005    *  @param  __first1  Start of first range.
05006    *  @param  __last1   End of first range.
05007    *  @param  __first2  Start of second range.
05008    *  @param  __last2   End of second range.
05009    *  @param  __comp    The comparison functor.
05010    *  @return  End of the output range.
05011    *  @ingroup set_algorithms
05012    *
05013    *  This operation iterates over both ranges, copying elements present in
05014    *  each range in order to the output range.  Iterators increment for each
05015    *  range.  When the current element of one range is less than the other
05016    *  according to @p __comp, that element is copied and the iterator advanced.
05017    *  If an equivalent element according to @p __comp is contained in both
05018    *  ranges, the element from the first range is copied and both ranges
05019    *  advance.  The output range may not overlap either input range.
05020   */
05021   template<typename _InputIterator1, typename _InputIterator2,
05022        typename _OutputIterator, typename _Compare>
05023     inline _OutputIterator
05024     set_union(_InputIterator1 __first1, _InputIterator1 __last1,
05025           _InputIterator2 __first2, _InputIterator2 __last2,
05026           _OutputIterator __result, _Compare __comp)
05027     {
05028       // concept requirements
05029       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
05030       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
05031       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
05032         typename iterator_traits<_InputIterator1>::value_type>)
05033       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
05034         typename iterator_traits<_InputIterator2>::value_type>)
05035       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
05036         typename iterator_traits<_InputIterator1>::value_type,
05037         typename iterator_traits<_InputIterator2>::value_type>)
05038       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
05039         typename iterator_traits<_InputIterator2>::value_type,
05040         typename iterator_traits<_InputIterator1>::value_type>)
05041       __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp);
05042       __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp);
05043 
05044       return _GLIBCXX_STD_A::__set_union(__first1, __last1,
05045                 __first2, __last2, __result,
05046                 __gnu_cxx::__ops::__iter_comp_iter(__comp));
05047     }
05048 
05049   template<typename _InputIterator1, typename _InputIterator2,
05050        typename _OutputIterator,
05051        typename _Compare>
05052     _OutputIterator
05053     __set_intersection(_InputIterator1 __first1, _InputIterator1 __last1,
05054                _InputIterator2 __first2, _InputIterator2 __last2,
05055                _OutputIterator __result, _Compare __comp)
05056     {
05057       while (__first1 != __last1 && __first2 != __last2)
05058     if (__comp(__first1, __first2))
05059       ++__first1;
05060     else if (__comp(__first2, __first1))
05061       ++__first2;
05062     else
05063       {
05064         *__result = *__first1;
05065         ++__first1;
05066         ++__first2;
05067         ++__result;
05068       }
05069       return __result;
05070     }
05071 
05072   /**
05073    *  @brief Return the intersection of two sorted ranges.
05074    *  @ingroup set_algorithms
05075    *  @param  __first1  Start of first range.
05076    *  @param  __last1   End of first range.
05077    *  @param  __first2  Start of second range.
05078    *  @param  __last2   End of second range.
05079    *  @return  End of the output range.
05080    *  @ingroup set_algorithms
05081    *
05082    *  This operation iterates over both ranges, copying elements present in
05083    *  both ranges in order to the output range.  Iterators increment for each
05084    *  range.  When the current element of one range is less than the other,
05085    *  that iterator advances.  If an element is contained in both ranges, the
05086    *  element from the first range is copied and both ranges advance.  The
05087    *  output range may not overlap either input range.
05088   */
05089   template<typename _InputIterator1, typename _InputIterator2,
05090        typename _OutputIterator>
05091     inline _OutputIterator
05092     set_intersection(_InputIterator1 __first1, _InputIterator1 __last1,
05093              _InputIterator2 __first2, _InputIterator2 __last2,
05094              _OutputIterator __result)
05095     {
05096       // concept requirements
05097       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
05098       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
05099       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
05100         typename iterator_traits<_InputIterator1>::value_type>)
05101       __glibcxx_function_requires(_LessThanOpConcept<
05102         typename iterator_traits<_InputIterator1>::value_type,
05103         typename iterator_traits<_InputIterator2>::value_type>)
05104       __glibcxx_function_requires(_LessThanOpConcept<
05105         typename iterator_traits<_InputIterator2>::value_type,
05106         typename iterator_traits<_InputIterator1>::value_type>)
05107       __glibcxx_requires_sorted_set(__first1, __last1, __first2);
05108       __glibcxx_requires_sorted_set(__first2, __last2, __first1);
05109 
05110       return _GLIBCXX_STD_A::__set_intersection(__first1, __last1,
05111                      __first2, __last2, __result,
05112                      __gnu_cxx::__ops::__iter_less_iter());
05113     }
05114 
05115   /**
05116    *  @brief Return the intersection of two sorted ranges using comparison
05117    *  functor.
05118    *  @ingroup set_algorithms
05119    *  @param  __first1  Start of first range.
05120    *  @param  __last1   End of first range.
05121    *  @param  __first2  Start of second range.
05122    *  @param  __last2   End of second range.
05123    *  @param  __comp    The comparison functor.
05124    *  @return  End of the output range.
05125    *  @ingroup set_algorithms
05126    *
05127    *  This operation iterates over both ranges, copying elements present in
05128    *  both ranges in order to the output range.  Iterators increment for each
05129    *  range.  When the current element of one range is less than the other
05130    *  according to @p __comp, that iterator advances.  If an element is
05131    *  contained in both ranges according to @p __comp, the element from the
05132    *  first range is copied and both ranges advance.  The output range may not
05133    *  overlap either input range.
05134   */
05135   template<typename _InputIterator1, typename _InputIterator2,
05136        typename _OutputIterator, typename _Compare>
05137     inline _OutputIterator
05138     set_intersection(_InputIterator1 __first1, _InputIterator1 __last1,
05139              _InputIterator2 __first2, _InputIterator2 __last2,
05140              _OutputIterator __result, _Compare __comp)
05141     {
05142       // concept requirements
05143       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
05144       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
05145       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
05146         typename iterator_traits<_InputIterator1>::value_type>)
05147       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
05148         typename iterator_traits<_InputIterator1>::value_type,
05149         typename iterator_traits<_InputIterator2>::value_type>)
05150       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
05151         typename iterator_traits<_InputIterator2>::value_type,
05152         typename iterator_traits<_InputIterator1>::value_type>)
05153       __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp);
05154       __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp);
05155 
05156       return _GLIBCXX_STD_A::__set_intersection(__first1, __last1,
05157                 __first2, __last2, __result,
05158                 __gnu_cxx::__ops::__iter_comp_iter(__comp));
05159     }
05160 
05161   template<typename _InputIterator1, typename _InputIterator2,
05162        typename _OutputIterator,
05163        typename _Compare>
05164     _OutputIterator
05165     __set_difference(_InputIterator1 __first1, _InputIterator1 __last1,
05166              _InputIterator2 __first2, _InputIterator2 __last2,
05167              _OutputIterator __result, _Compare __comp)
05168     {
05169       while (__first1 != __last1 && __first2 != __last2)
05170     if (__comp(__first1, __first2))
05171       {
05172         *__result = *__first1;
05173         ++__first1;
05174         ++__result;
05175       }
05176     else if (__comp(__first2, __first1))
05177       ++__first2;
05178     else
05179       {
05180         ++__first1;
05181         ++__first2;
05182       }
05183       return std::copy(__first1, __last1, __result);
05184     }
05185 
05186   /**
05187    *  @brief Return the difference of two sorted ranges.
05188    *  @ingroup set_algorithms
05189    *  @param  __first1  Start of first range.
05190    *  @param  __last1   End of first range.
05191    *  @param  __first2  Start of second range.
05192    *  @param  __last2   End of second range.
05193    *  @return  End of the output range.
05194    *  @ingroup set_algorithms
05195    *
05196    *  This operation iterates over both ranges, copying elements present in
05197    *  the first range but not the second in order to the output range.
05198    *  Iterators increment for each range.  When the current element of the
05199    *  first range is less than the second, that element is copied and the
05200    *  iterator advances.  If the current element of the second range is less,
05201    *  the iterator advances, but no element is copied.  If an element is
05202    *  contained in both ranges, no elements are copied and both ranges
05203    *  advance.  The output range may not overlap either input range.
05204   */
05205   template<typename _InputIterator1, typename _InputIterator2,
05206        typename _OutputIterator>
05207     inline _OutputIterator
05208     set_difference(_InputIterator1 __first1, _InputIterator1 __last1,
05209            _InputIterator2 __first2, _InputIterator2 __last2,
05210            _OutputIterator __result)
05211     {
05212       // concept requirements
05213       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
05214       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
05215       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
05216         typename iterator_traits<_InputIterator1>::value_type>)
05217       __glibcxx_function_requires(_LessThanOpConcept<
05218         typename iterator_traits<_InputIterator1>::value_type,
05219         typename iterator_traits<_InputIterator2>::value_type>)
05220       __glibcxx_function_requires(_LessThanOpConcept<
05221         typename iterator_traits<_InputIterator2>::value_type,
05222         typename iterator_traits<_InputIterator1>::value_type>) 
05223       __glibcxx_requires_sorted_set(__first1, __last1, __first2);
05224       __glibcxx_requires_sorted_set(__first2, __last2, __first1);
05225 
05226       return _GLIBCXX_STD_A::__set_difference(__first1, __last1,
05227                    __first2, __last2, __result,
05228                    __gnu_cxx::__ops::__iter_less_iter());
05229     }
05230 
05231   /**
05232    *  @brief  Return the difference of two sorted ranges using comparison
05233    *  functor.
05234    *  @ingroup set_algorithms
05235    *  @param  __first1  Start of first range.
05236    *  @param  __last1   End of first range.
05237    *  @param  __first2  Start of second range.
05238    *  @param  __last2   End of second range.
05239    *  @param  __comp    The comparison functor.
05240    *  @return  End of the output range.
05241    *  @ingroup set_algorithms
05242    *
05243    *  This operation iterates over both ranges, copying elements present in
05244    *  the first range but not the second in order to the output range.
05245    *  Iterators increment for each range.  When the current element of the
05246    *  first range is less than the second according to @p __comp, that element
05247    *  is copied and the iterator advances.  If the current element of the
05248    *  second range is less, no element is copied and the iterator advances.
05249    *  If an element is contained in both ranges according to @p __comp, no
05250    *  elements are copied and both ranges advance.  The output range may not
05251    *  overlap either input range.
05252   */
05253   template<typename _InputIterator1, typename _InputIterator2,
05254        typename _OutputIterator, typename _Compare>
05255     inline _OutputIterator
05256     set_difference(_InputIterator1 __first1, _InputIterator1 __last1,
05257            _InputIterator2 __first2, _InputIterator2 __last2,
05258            _OutputIterator __result, _Compare __comp)
05259     {
05260       // concept requirements
05261       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
05262       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
05263       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
05264         typename iterator_traits<_InputIterator1>::value_type>)
05265       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
05266         typename iterator_traits<_InputIterator1>::value_type,
05267         typename iterator_traits<_InputIterator2>::value_type>)
05268       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
05269         typename iterator_traits<_InputIterator2>::value_type,
05270         typename iterator_traits<_InputIterator1>::value_type>)
05271       __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp);
05272       __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp);
05273 
05274       return _GLIBCXX_STD_A::__set_difference(__first1, __last1,
05275                    __first2, __last2, __result,
05276                    __gnu_cxx::__ops::__iter_comp_iter(__comp));
05277     }
05278 
05279   template<typename _InputIterator1, typename _InputIterator2,
05280        typename _OutputIterator,
05281        typename _Compare>
05282     _OutputIterator
05283     __set_symmetric_difference(_InputIterator1 __first1,
05284                    _InputIterator1 __last1,
05285                    _InputIterator2 __first2,
05286                    _InputIterator2 __last2,
05287                    _OutputIterator __result,
05288                    _Compare __comp)
05289     {
05290       while (__first1 != __last1 && __first2 != __last2)
05291     if (__comp(__first1, __first2))
05292       {
05293         *__result = *__first1;
05294         ++__first1;
05295         ++__result;
05296       }
05297     else if (__comp(__first2, __first1))
05298       {
05299         *__result = *__first2;
05300         ++__first2;
05301         ++__result;
05302       }
05303     else
05304       {
05305         ++__first1;
05306         ++__first2;
05307       }
05308       return std::copy(__first2, __last2, 
05309                std::copy(__first1, __last1, __result));
05310     }
05311 
05312   /**
05313    *  @brief  Return the symmetric difference of two sorted ranges.
05314    *  @ingroup set_algorithms
05315    *  @param  __first1  Start of first range.
05316    *  @param  __last1   End of first range.
05317    *  @param  __first2  Start of second range.
05318    *  @param  __last2   End of second range.
05319    *  @return  End of the output range.
05320    *  @ingroup set_algorithms
05321    *
05322    *  This operation iterates over both ranges, copying elements present in
05323    *  one range but not the other in order to the output range.  Iterators
05324    *  increment for each range.  When the current element of one range is less
05325    *  than the other, that element is copied and the iterator advances.  If an
05326    *  element is contained in both ranges, no elements are copied and both
05327    *  ranges advance.  The output range may not overlap either input range.
05328   */
05329   template<typename _InputIterator1, typename _InputIterator2,
05330        typename _OutputIterator>
05331     inline _OutputIterator
05332     set_symmetric_difference(_InputIterator1 __first1, _InputIterator1 __last1,
05333                  _InputIterator2 __first2, _InputIterator2 __last2,
05334                  _OutputIterator __result)
05335     {
05336       // concept requirements
05337       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
05338       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
05339       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
05340         typename iterator_traits<_InputIterator1>::value_type>)
05341       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
05342         typename iterator_traits<_InputIterator2>::value_type>)
05343       __glibcxx_function_requires(_LessThanOpConcept<
05344         typename iterator_traits<_InputIterator1>::value_type,
05345         typename iterator_traits<_InputIterator2>::value_type>)
05346       __glibcxx_function_requires(_LessThanOpConcept<
05347         typename iterator_traits<_InputIterator2>::value_type,
05348         typename iterator_traits<_InputIterator1>::value_type>) 
05349       __glibcxx_requires_sorted_set(__first1, __last1, __first2);
05350       __glibcxx_requires_sorted_set(__first2, __last2, __first1);
05351 
05352       return _GLIBCXX_STD_A::__set_symmetric_difference(__first1, __last1,
05353                     __first2, __last2, __result,
05354                     __gnu_cxx::__ops::__iter_less_iter());
05355     }
05356 
05357   /**
05358    *  @brief  Return the symmetric difference of two sorted ranges using
05359    *  comparison functor.
05360    *  @ingroup set_algorithms
05361    *  @param  __first1  Start of first range.
05362    *  @param  __last1   End of first range.
05363    *  @param  __first2  Start of second range.
05364    *  @param  __last2   End of second range.
05365    *  @param  __comp    The comparison functor.
05366    *  @return  End of the output range.
05367    *  @ingroup set_algorithms
05368    *
05369    *  This operation iterates over both ranges, copying elements present in
05370    *  one range but not the other in order to the output range.  Iterators
05371    *  increment for each range.  When the current element of one range is less
05372    *  than the other according to @p comp, that element is copied and the
05373    *  iterator advances.  If an element is contained in both ranges according
05374    *  to @p __comp, no elements are copied and both ranges advance.  The output
05375    *  range may not overlap either input range.
05376   */
05377   template<typename _InputIterator1, typename _InputIterator2,
05378        typename _OutputIterator, typename _Compare>
05379     inline _OutputIterator
05380     set_symmetric_difference(_InputIterator1 __first1, _InputIterator1 __last1,
05381                  _InputIterator2 __first2, _InputIterator2 __last2,
05382                  _OutputIterator __result,
05383                  _Compare __comp)
05384     {
05385       // concept requirements
05386       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
05387       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
05388       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
05389         typename iterator_traits<_InputIterator1>::value_type>)
05390       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
05391         typename iterator_traits<_InputIterator2>::value_type>)
05392       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
05393         typename iterator_traits<_InputIterator1>::value_type,
05394         typename iterator_traits<_InputIterator2>::value_type>)
05395       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
05396         typename iterator_traits<_InputIterator2>::value_type,
05397         typename iterator_traits<_InputIterator1>::value_type>)
05398       __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp);
05399       __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp);
05400 
05401       return _GLIBCXX_STD_A::__set_symmetric_difference(__first1, __last1,
05402                 __first2, __last2, __result,
05403                 __gnu_cxx::__ops::__iter_comp_iter(__comp));
05404     }
05405 
05406   template<typename _ForwardIterator, typename _Compare>
05407     _ForwardIterator
05408     __min_element(_ForwardIterator __first, _ForwardIterator __last,
05409           _Compare __comp)
05410     {
05411       if (__first == __last)
05412     return __first;
05413       _ForwardIterator __result = __first;
05414       while (++__first != __last)
05415     if (__comp(__first, __result))
05416       __result = __first;
05417       return __result;
05418     }
05419 
05420   /**
05421    *  @brief  Return the minimum element in a range.
05422    *  @ingroup sorting_algorithms
05423    *  @param  __first  Start of range.
05424    *  @param  __last   End of range.
05425    *  @return  Iterator referencing the first instance of the smallest value.
05426   */
05427   template<typename _ForwardIterator>
05428     _ForwardIterator
05429     inline min_element(_ForwardIterator __first, _ForwardIterator __last)
05430     {
05431       // concept requirements
05432       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
05433       __glibcxx_function_requires(_LessThanComparableConcept<
05434         typename iterator_traits<_ForwardIterator>::value_type>)
05435       __glibcxx_requires_valid_range(__first, __last);
05436 
05437       return _GLIBCXX_STD_A::__min_element(__first, __last,
05438                 __gnu_cxx::__ops::__iter_less_iter());
05439     }
05440 
05441   /**
05442    *  @brief  Return the minimum element in a range using comparison functor.
05443    *  @ingroup sorting_algorithms
05444    *  @param  __first  Start of range.
05445    *  @param  __last   End of range.
05446    *  @param  __comp   Comparison functor.
05447    *  @return  Iterator referencing the first instance of the smallest value
05448    *  according to __comp.
05449   */
05450   template<typename _ForwardIterator, typename _Compare>
05451     inline _ForwardIterator
05452     min_element(_ForwardIterator __first, _ForwardIterator __last,
05453         _Compare __comp)
05454     {
05455       // concept requirements
05456       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
05457       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
05458         typename iterator_traits<_ForwardIterator>::value_type,
05459         typename iterator_traits<_ForwardIterator>::value_type>)
05460       __glibcxx_requires_valid_range(__first, __last);
05461 
05462       return _GLIBCXX_STD_A::__min_element(__first, __last,
05463                 __gnu_cxx::__ops::__iter_comp_iter(__comp));
05464     }
05465 
05466   template<typename _ForwardIterator, typename _Compare>
05467     _ForwardIterator
05468     __max_element(_ForwardIterator __first, _ForwardIterator __last,
05469           _Compare __comp)
05470     {
05471       if (__first == __last) return __first;
05472       _ForwardIterator __result = __first;
05473       while (++__first != __last)
05474     if (__comp(__result, __first))
05475       __result = __first;
05476       return __result;
05477     }
05478 
05479   /**
05480    *  @brief  Return the maximum element in a range.
05481    *  @ingroup sorting_algorithms
05482    *  @param  __first  Start of range.
05483    *  @param  __last   End of range.
05484    *  @return  Iterator referencing the first instance of the largest value.
05485   */
05486   template<typename _ForwardIterator>
05487     inline _ForwardIterator
05488     max_element(_ForwardIterator __first, _ForwardIterator __last)
05489     {
05490       // concept requirements
05491       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
05492       __glibcxx_function_requires(_LessThanComparableConcept<
05493         typename iterator_traits<_ForwardIterator>::value_type>)
05494       __glibcxx_requires_valid_range(__first, __last);
05495 
05496       return _GLIBCXX_STD_A::__max_element(__first, __last,
05497                 __gnu_cxx::__ops::__iter_less_iter());
05498     }
05499 
05500   /**
05501    *  @brief  Return the maximum element in a range using comparison functor.
05502    *  @ingroup sorting_algorithms
05503    *  @param  __first  Start of range.
05504    *  @param  __last   End of range.
05505    *  @param  __comp   Comparison functor.
05506    *  @return  Iterator referencing the first instance of the largest value
05507    *  according to __comp.
05508   */
05509   template<typename _ForwardIterator, typename _Compare>
05510     inline _ForwardIterator
05511     max_element(_ForwardIterator __first, _ForwardIterator __last,
05512         _Compare __comp)
05513     {
05514       // concept requirements
05515       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
05516       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
05517         typename iterator_traits<_ForwardIterator>::value_type,
05518         typename iterator_traits<_ForwardIterator>::value_type>)
05519       __glibcxx_requires_valid_range(__first, __last);
05520 
05521       return _GLIBCXX_STD_A::__max_element(__first, __last,
05522                 __gnu_cxx::__ops::__iter_comp_iter(__comp));
05523     }
05524 
05525 _GLIBCXX_END_NAMESPACE_ALGO
05526 } // namespace std
05527 
05528 #endif /* _STL_ALGO_H */