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; ++__first1, ++__first2)
03599     if (!__pred(__first1, __first2))
03600       break;
03601 
03602       if (__ra_iters)
03603     {
03604       if (__first1 == __last1)
03605         return true;
03606     }
03607       else
03608     {
03609       auto __d1 = std::distance(__first1, __last1);
03610       auto __d2 = std::distance(__first2, __last2);
03611       if (__d1 == 0 && __d2 == 0)
03612         return true;
03613       if (__d1 != __d2)
03614         return false;
03615     }
03616 
03617       for (_ForwardIterator1 __scan = __first1; __scan != __last1; ++__scan)
03618     {
03619       if (__scan != std::__find_if(__first1, __scan,
03620             __gnu_cxx::__ops::__iter_comp_iter(__pred, __scan)))
03621         continue; // We've seen this one before.
03622 
03623       auto __matches = std::__count_if(__first2, __last2,
03624         __gnu_cxx::__ops::__iter_comp_iter(__pred, __scan));
03625       if (0 == __matches
03626           || std::__count_if(__scan, __last1,
03627             __gnu_cxx::__ops::__iter_comp_iter(__pred, __scan))
03628           != __matches)
03629         return false;
03630     }
03631       return true;
03632     }
03633 
03634   /**
03635    *  @brief  Checks whether a permutaion of the second sequence is equal
03636    *          to the first sequence.
03637    *  @ingroup non_mutating_algorithms
03638    *  @param  __first1  Start of first range.
03639    *  @param  __last1   End of first range.
03640    *  @param  __first2  Start of second range.
03641    *  @param  __last2   End of first range.
03642    *  @return true if there exists a permutation of the elements in the range
03643    *          [__first2, __last2), beginning with ForwardIterator2 begin,
03644    *          such that equal(__first1, __last1, begin) returns true;
03645    *          otherwise, returns false.
03646   */
03647   template<typename _ForwardIterator1, typename _ForwardIterator2>
03648     inline bool
03649     is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
03650            _ForwardIterator2 __first2, _ForwardIterator2 __last2)
03651     {
03652       __glibcxx_requires_valid_range(__first1, __last1);
03653       __glibcxx_requires_valid_range(__first2, __last2);
03654 
03655       return
03656     std::__is_permutation(__first1, __last1, __first2, __last2,
03657                   __gnu_cxx::__ops::__iter_equal_to_iter());
03658     }
03659 
03660   /**
03661    *  @brief  Checks whether a permutation of the second sequence is equal
03662    *          to the first sequence.
03663    *  @ingroup non_mutating_algorithms
03664    *  @param  __first1  Start of first range.
03665    *  @param  __last1   End of first range.
03666    *  @param  __first2  Start of second range.
03667    *  @param  __last2   End of first range.
03668    *  @param  __pred    A binary predicate.
03669    *  @return true if there exists a permutation of the elements in the range
03670    *          [__first2, __last2), beginning with ForwardIterator2 begin,
03671    *          such that equal(__first1, __last1, __begin, __pred) returns true;
03672    *          otherwise, returns false.
03673   */
03674   template<typename _ForwardIterator1, typename _ForwardIterator2,
03675        typename _BinaryPredicate>
03676     inline bool
03677     is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
03678            _ForwardIterator2 __first2, _ForwardIterator2 __last2,
03679            _BinaryPredicate __pred)
03680     {
03681       __glibcxx_requires_valid_range(__first1, __last1);
03682       __glibcxx_requires_valid_range(__first2, __last2);
03683 
03684       return std::__is_permutation(__first1, __last1, __first2, __last2,
03685                    __gnu_cxx::__ops::__iter_comp_iter(__pred));
03686     }
03687 #endif
03688 
03689 #ifdef _GLIBCXX_USE_C99_STDINT_TR1
03690   /**
03691    *  @brief Shuffle the elements of a sequence using a uniform random
03692    *         number generator.
03693    *  @ingroup mutating_algorithms
03694    *  @param  __first   A forward iterator.
03695    *  @param  __last    A forward iterator.
03696    *  @param  __g       A UniformRandomNumberGenerator (26.5.1.3).
03697    *  @return  Nothing.
03698    *
03699    *  Reorders the elements in the range @p [__first,__last) using @p __g to
03700    *  provide random numbers.
03701   */
03702   template<typename _RandomAccessIterator,
03703        typename _UniformRandomNumberGenerator>
03704     void
03705     shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last,
03706         _UniformRandomNumberGenerator&& __g)
03707     {
03708       // concept requirements
03709       __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
03710         _RandomAccessIterator>)
03711       __glibcxx_requires_valid_range(__first, __last);
03712 
03713       if (__first == __last)
03714     return;
03715 
03716       typedef typename iterator_traits<_RandomAccessIterator>::difference_type
03717     _DistanceType;
03718 
03719       typedef typename std::make_unsigned<_DistanceType>::type __ud_type;
03720       typedef typename std::uniform_int_distribution<__ud_type> __distr_type;
03721       typedef typename __distr_type::param_type __p_type;
03722       __distr_type __d;
03723 
03724       for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i)
03725     std::iter_swap(__i, __first + __d(__g, __p_type(0, __i - __first)));
03726     }
03727 #endif
03728 
03729 #endif // C++11
03730 
03731 _GLIBCXX_END_NAMESPACE_VERSION
03732 
03733 _GLIBCXX_BEGIN_NAMESPACE_ALGO
03734 
03735   /**
03736    *  @brief Apply a function to every element of a sequence.
03737    *  @ingroup non_mutating_algorithms
03738    *  @param  __first  An input iterator.
03739    *  @param  __last   An input iterator.
03740    *  @param  __f      A unary function object.
03741    *  @return   @p __f (std::move(@p __f) in C++0x).
03742    *
03743    *  Applies the function object @p __f to each element in the range
03744    *  @p [first,last).  @p __f must not modify the order of the sequence.
03745    *  If @p __f has a return value it is ignored.
03746   */
03747   template<typename _InputIterator, typename _Function>
03748     _Function
03749     for_each(_InputIterator __first, _InputIterator __last, _Function __f)
03750     {
03751       // concept requirements
03752       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
03753       __glibcxx_requires_valid_range(__first, __last);
03754       for (; __first != __last; ++__first)
03755     __f(*__first);
03756       return _GLIBCXX_MOVE(__f);
03757     }
03758 
03759   /**
03760    *  @brief Find the first occurrence of a value in a sequence.
03761    *  @ingroup non_mutating_algorithms
03762    *  @param  __first  An input iterator.
03763    *  @param  __last   An input iterator.
03764    *  @param  __val    The value to find.
03765    *  @return   The first iterator @c i in the range @p [__first,__last)
03766    *  such that @c *i == @p __val, or @p __last if no such iterator exists.
03767   */
03768   template<typename _InputIterator, typename _Tp>
03769     inline _InputIterator
03770     find(_InputIterator __first, _InputIterator __last,
03771      const _Tp& __val)
03772     {
03773       // concept requirements
03774       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
03775       __glibcxx_function_requires(_EqualOpConcept<
03776         typename iterator_traits<_InputIterator>::value_type, _Tp>)
03777       __glibcxx_requires_valid_range(__first, __last);
03778       return std::__find_if(__first, __last,
03779                 __gnu_cxx::__ops::__iter_equals_val(__val));
03780     }
03781 
03782   /**
03783    *  @brief Find the first element in a sequence for which a
03784    *         predicate is true.
03785    *  @ingroup non_mutating_algorithms
03786    *  @param  __first  An input iterator.
03787    *  @param  __last   An input iterator.
03788    *  @param  __pred   A predicate.
03789    *  @return   The first iterator @c i in the range @p [__first,__last)
03790    *  such that @p __pred(*i) is true, or @p __last if no such iterator exists.
03791   */
03792   template<typename _InputIterator, typename _Predicate>
03793     inline _InputIterator
03794     find_if(_InputIterator __first, _InputIterator __last,
03795         _Predicate __pred)
03796     {
03797       // concept requirements
03798       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
03799       __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
03800           typename iterator_traits<_InputIterator>::value_type>)
03801       __glibcxx_requires_valid_range(__first, __last);
03802 
03803       return std::__find_if(__first, __last,
03804                 __gnu_cxx::__ops::__pred_iter(__pred));
03805     }
03806 
03807   /**
03808    *  @brief  Find element from a set in a sequence.
03809    *  @ingroup non_mutating_algorithms
03810    *  @param  __first1  Start of range to search.
03811    *  @param  __last1   End of range to search.
03812    *  @param  __first2  Start of match candidates.
03813    *  @param  __last2   End of match candidates.
03814    *  @return   The first iterator @c i in the range
03815    *  @p [__first1,__last1) such that @c *i == @p *(i2) such that i2 is an
03816    *  iterator in [__first2,__last2), or @p __last1 if no such iterator exists.
03817    *
03818    *  Searches the range @p [__first1,__last1) for an element that is
03819    *  equal to some element in the range [__first2,__last2).  If
03820    *  found, returns an iterator in the range [__first1,__last1),
03821    *  otherwise returns @p __last1.
03822   */
03823   template<typename _InputIterator, typename _ForwardIterator>
03824     _InputIterator
03825     find_first_of(_InputIterator __first1, _InputIterator __last1,
03826           _ForwardIterator __first2, _ForwardIterator __last2)
03827     {
03828       // concept requirements
03829       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
03830       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
03831       __glibcxx_function_requires(_EqualOpConcept<
03832         typename iterator_traits<_InputIterator>::value_type,
03833         typename iterator_traits<_ForwardIterator>::value_type>)
03834       __glibcxx_requires_valid_range(__first1, __last1);
03835       __glibcxx_requires_valid_range(__first2, __last2);
03836 
03837       for (; __first1 != __last1; ++__first1)
03838     for (_ForwardIterator __iter = __first2; __iter != __last2; ++__iter)
03839       if (*__first1 == *__iter)
03840         return __first1;
03841       return __last1;
03842     }
03843 
03844   /**
03845    *  @brief  Find element from a set in a sequence using a predicate.
03846    *  @ingroup non_mutating_algorithms
03847    *  @param  __first1  Start of range to search.
03848    *  @param  __last1   End of range to search.
03849    *  @param  __first2  Start of match candidates.
03850    *  @param  __last2   End of match candidates.
03851    *  @param  __comp    Predicate to use.
03852    *  @return   The first iterator @c i in the range
03853    *  @p [__first1,__last1) such that @c comp(*i, @p *(i2)) is true
03854    *  and i2 is an iterator in [__first2,__last2), or @p __last1 if no
03855    *  such iterator exists.
03856    *
03857 
03858    *  Searches the range @p [__first1,__last1) for an element that is
03859    *  equal to some element in the range [__first2,__last2).  If
03860    *  found, returns an iterator in the range [__first1,__last1),
03861    *  otherwise returns @p __last1.
03862   */
03863   template<typename _InputIterator, typename _ForwardIterator,
03864        typename _BinaryPredicate>
03865     _InputIterator
03866     find_first_of(_InputIterator __first1, _InputIterator __last1,
03867           _ForwardIterator __first2, _ForwardIterator __last2,
03868           _BinaryPredicate __comp)
03869     {
03870       // concept requirements
03871       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
03872       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
03873       __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
03874         typename iterator_traits<_InputIterator>::value_type,
03875         typename iterator_traits<_ForwardIterator>::value_type>)
03876       __glibcxx_requires_valid_range(__first1, __last1);
03877       __glibcxx_requires_valid_range(__first2, __last2);
03878 
03879       for (; __first1 != __last1; ++__first1)
03880     for (_ForwardIterator __iter = __first2; __iter != __last2; ++__iter)
03881       if (__comp(*__first1, *__iter))
03882         return __first1;
03883       return __last1;
03884     }
03885 
03886   /**
03887    *  @brief Find two adjacent values in a sequence that are equal.
03888    *  @ingroup non_mutating_algorithms
03889    *  @param  __first  A forward iterator.
03890    *  @param  __last   A forward iterator.
03891    *  @return   The first iterator @c i such that @c i and @c i+1 are both
03892    *  valid iterators in @p [__first,__last) and such that @c *i == @c *(i+1),
03893    *  or @p __last if no such iterator exists.
03894   */
03895   template<typename _ForwardIterator>
03896     inline _ForwardIterator
03897     adjacent_find(_ForwardIterator __first, _ForwardIterator __last)
03898     {
03899       // concept requirements
03900       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
03901       __glibcxx_function_requires(_EqualityComparableConcept<
03902         typename iterator_traits<_ForwardIterator>::value_type>)
03903       __glibcxx_requires_valid_range(__first, __last);
03904 
03905       return std::__adjacent_find(__first, __last,
03906                   __gnu_cxx::__ops::__iter_equal_to_iter());
03907     }
03908 
03909   /**
03910    *  @brief Find two adjacent values in a sequence using a predicate.
03911    *  @ingroup non_mutating_algorithms
03912    *  @param  __first         A forward iterator.
03913    *  @param  __last          A forward iterator.
03914    *  @param  __binary_pred   A binary predicate.
03915    *  @return   The first iterator @c i such that @c i and @c i+1 are both
03916    *  valid iterators in @p [__first,__last) and such that
03917    *  @p __binary_pred(*i,*(i+1)) is true, or @p __last if no such iterator
03918    *  exists.
03919   */
03920   template<typename _ForwardIterator, typename _BinaryPredicate>
03921     inline _ForwardIterator
03922     adjacent_find(_ForwardIterator __first, _ForwardIterator __last,
03923           _BinaryPredicate __binary_pred)
03924     {
03925       // concept requirements
03926       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
03927       __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
03928         typename iterator_traits<_ForwardIterator>::value_type,
03929         typename iterator_traits<_ForwardIterator>::value_type>)
03930       __glibcxx_requires_valid_range(__first, __last);
03931 
03932       return std::__adjacent_find(__first, __last,
03933             __gnu_cxx::__ops::__iter_comp_iter(__binary_pred));
03934     }
03935 
03936   /**
03937    *  @brief Count the number of copies of a value in a sequence.
03938    *  @ingroup non_mutating_algorithms
03939    *  @param  __first  An input iterator.
03940    *  @param  __last   An input iterator.
03941    *  @param  __value  The value to be counted.
03942    *  @return   The number of iterators @c i in the range @p [__first,__last)
03943    *  for which @c *i == @p __value
03944   */
03945   template<typename _InputIterator, typename _Tp>
03946     inline typename iterator_traits<_InputIterator>::difference_type
03947     count(_InputIterator __first, _InputIterator __last, const _Tp& __value)
03948     {
03949       // concept requirements
03950       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
03951       __glibcxx_function_requires(_EqualOpConcept<
03952         typename iterator_traits<_InputIterator>::value_type, _Tp>)
03953       __glibcxx_requires_valid_range(__first, __last);
03954 
03955       return std::__count_if(__first, __last,
03956                  __gnu_cxx::__ops::__iter_equals_val(__value));
03957     }
03958 
03959   /**
03960    *  @brief Count the elements of a sequence for which a predicate is true.
03961    *  @ingroup non_mutating_algorithms
03962    *  @param  __first  An input iterator.
03963    *  @param  __last   An input iterator.
03964    *  @param  __pred   A predicate.
03965    *  @return   The number of iterators @c i in the range @p [__first,__last)
03966    *  for which @p __pred(*i) is true.
03967   */
03968   template<typename _InputIterator, typename _Predicate>
03969     inline typename iterator_traits<_InputIterator>::difference_type
03970     count_if(_InputIterator __first, _InputIterator __last, _Predicate __pred)
03971     {
03972       // concept requirements
03973       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
03974       __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
03975         typename iterator_traits<_InputIterator>::value_type>)
03976       __glibcxx_requires_valid_range(__first, __last);
03977 
03978       return std::__count_if(__first, __last,
03979                  __gnu_cxx::__ops::__pred_iter(__pred));
03980     }
03981 
03982   /**
03983    *  @brief Search a sequence for a matching sub-sequence.
03984    *  @ingroup non_mutating_algorithms
03985    *  @param  __first1  A forward iterator.
03986    *  @param  __last1   A forward iterator.
03987    *  @param  __first2  A forward iterator.
03988    *  @param  __last2   A forward iterator.
03989    *  @return The first iterator @c i in the range @p
03990    *  [__first1,__last1-(__last2-__first2)) such that @c *(i+N) == @p
03991    *  *(__first2+N) for each @c N in the range @p
03992    *  [0,__last2-__first2), or @p __last1 if no such iterator exists.
03993    *
03994    *  Searches the range @p [__first1,__last1) for a sub-sequence that
03995    *  compares equal value-by-value with the sequence given by @p
03996    *  [__first2,__last2) and returns an iterator to the first element
03997    *  of the sub-sequence, or @p __last1 if the sub-sequence is not
03998    *  found.
03999    *
04000    *  Because the sub-sequence must lie completely within the range @p
04001    *  [__first1,__last1) it must start at a position less than @p
04002    *  __last1-(__last2-__first2) where @p __last2-__first2 is the
04003    *  length of the sub-sequence.
04004    *
04005    *  This means that the returned iterator @c i will be in the range
04006    *  @p [__first1,__last1-(__last2-__first2))
04007   */
04008   template<typename _ForwardIterator1, typename _ForwardIterator2>
04009     inline _ForwardIterator1
04010     search(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
04011        _ForwardIterator2 __first2, _ForwardIterator2 __last2)
04012     {
04013       // concept requirements
04014       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator1>)
04015       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator2>)
04016       __glibcxx_function_requires(_EqualOpConcept<
04017         typename iterator_traits<_ForwardIterator1>::value_type,
04018         typename iterator_traits<_ForwardIterator2>::value_type>)
04019       __glibcxx_requires_valid_range(__first1, __last1);
04020       __glibcxx_requires_valid_range(__first2, __last2);
04021 
04022       return std::__search(__first1, __last1, __first2, __last2,
04023                __gnu_cxx::__ops::__iter_equal_to_iter());
04024     }
04025 
04026   /**
04027    *  @brief Search a sequence for a matching sub-sequence using a predicate.
04028    *  @ingroup non_mutating_algorithms
04029    *  @param  __first1     A forward iterator.
04030    *  @param  __last1      A forward iterator.
04031    *  @param  __first2     A forward iterator.
04032    *  @param  __last2      A forward iterator.
04033    *  @param  __predicate  A binary predicate.
04034    *  @return   The first iterator @c i in the range
04035    *  @p [__first1,__last1-(__last2-__first2)) such that
04036    *  @p __predicate(*(i+N),*(__first2+N)) is true for each @c N in the range
04037    *  @p [0,__last2-__first2), or @p __last1 if no such iterator exists.
04038    *
04039    *  Searches the range @p [__first1,__last1) for a sub-sequence that
04040    *  compares equal value-by-value with the sequence given by @p
04041    *  [__first2,__last2), using @p __predicate to determine equality,
04042    *  and returns an iterator to the first element of the
04043    *  sub-sequence, or @p __last1 if no such iterator exists.
04044    *
04045    *  @see search(_ForwardIter1, _ForwardIter1, _ForwardIter2, _ForwardIter2)
04046   */
04047   template<typename _ForwardIterator1, typename _ForwardIterator2,
04048        typename _BinaryPredicate>
04049     inline _ForwardIterator1
04050     search(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
04051        _ForwardIterator2 __first2, _ForwardIterator2 __last2,
04052        _BinaryPredicate  __predicate)
04053     {
04054       // concept requirements
04055       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator1>)
04056       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator2>)
04057       __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
04058         typename iterator_traits<_ForwardIterator1>::value_type,
04059         typename iterator_traits<_ForwardIterator2>::value_type>)
04060       __glibcxx_requires_valid_range(__first1, __last1);
04061       __glibcxx_requires_valid_range(__first2, __last2);
04062 
04063       return std::__search(__first1, __last1, __first2, __last2,
04064                __gnu_cxx::__ops::__iter_comp_iter(__predicate));
04065     }
04066 
04067   /**
04068    *  @brief Search a sequence for a number of consecutive values.
04069    *  @ingroup non_mutating_algorithms
04070    *  @param  __first  A forward iterator.
04071    *  @param  __last   A forward iterator.
04072    *  @param  __count  The number of consecutive values.
04073    *  @param  __val    The value to find.
04074    *  @return The first iterator @c i in the range @p
04075    *  [__first,__last-__count) such that @c *(i+N) == @p __val for
04076    *  each @c N in the range @p [0,__count), or @p __last if no such
04077    *  iterator exists.
04078    *
04079    *  Searches the range @p [__first,__last) for @p count consecutive elements
04080    *  equal to @p __val.
04081   */
04082   template<typename _ForwardIterator, typename _Integer, typename _Tp>
04083     inline _ForwardIterator
04084     search_n(_ForwardIterator __first, _ForwardIterator __last,
04085          _Integer __count, const _Tp& __val)
04086     {
04087       // concept requirements
04088       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
04089       __glibcxx_function_requires(_EqualOpConcept<
04090         typename iterator_traits<_ForwardIterator>::value_type, _Tp>)
04091       __glibcxx_requires_valid_range(__first, __last);
04092 
04093       return std::__search_n(__first, __last, __count,
04094                  __gnu_cxx::__ops::__iter_equals_val(__val));
04095     }
04096 
04097 
04098   /**
04099    *  @brief Search a sequence for a number of consecutive values using a
04100    *         predicate.
04101    *  @ingroup non_mutating_algorithms
04102    *  @param  __first        A forward iterator.
04103    *  @param  __last         A forward iterator.
04104    *  @param  __count        The number of consecutive values.
04105    *  @param  __val          The value to find.
04106    *  @param  __binary_pred  A binary predicate.
04107    *  @return The first iterator @c i in the range @p
04108    *  [__first,__last-__count) such that @p
04109    *  __binary_pred(*(i+N),__val) is true for each @c N in the range
04110    *  @p [0,__count), or @p __last if no such iterator exists.
04111    *
04112    *  Searches the range @p [__first,__last) for @p __count
04113    *  consecutive elements for which the predicate returns true.
04114   */
04115   template<typename _ForwardIterator, typename _Integer, typename _Tp,
04116            typename _BinaryPredicate>
04117     inline _ForwardIterator
04118     search_n(_ForwardIterator __first, _ForwardIterator __last,
04119          _Integer __count, const _Tp& __val,
04120          _BinaryPredicate __binary_pred)
04121     {
04122       // concept requirements
04123       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
04124       __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
04125         typename iterator_traits<_ForwardIterator>::value_type, _Tp>)
04126       __glibcxx_requires_valid_range(__first, __last);
04127 
04128       return std::__search_n(__first, __last, __count,
04129         __gnu_cxx::__ops::__iter_comp_val(__binary_pred, __val));
04130     }
04131 
04132 
04133   /**
04134    *  @brief Perform an operation on a sequence.
04135    *  @ingroup mutating_algorithms
04136    *  @param  __first     An input iterator.
04137    *  @param  __last      An input iterator.
04138    *  @param  __result    An output iterator.
04139    *  @param  __unary_op  A unary operator.
04140    *  @return   An output iterator equal to @p __result+(__last-__first).
04141    *
04142    *  Applies the operator to each element in the input range and assigns
04143    *  the results to successive elements of the output sequence.
04144    *  Evaluates @p *(__result+N)=unary_op(*(__first+N)) for each @c N in the
04145    *  range @p [0,__last-__first).
04146    *
04147    *  @p unary_op must not alter its argument.
04148   */
04149   template<typename _InputIterator, typename _OutputIterator,
04150        typename _UnaryOperation>
04151     _OutputIterator
04152     transform(_InputIterator __first, _InputIterator __last,
04153           _OutputIterator __result, _UnaryOperation __unary_op)
04154     {
04155       // concept requirements
04156       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
04157       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
04158             // "the type returned by a _UnaryOperation"
04159             __typeof__(__unary_op(*__first))>)
04160       __glibcxx_requires_valid_range(__first, __last);
04161 
04162       for (; __first != __last; ++__first, ++__result)
04163     *__result = __unary_op(*__first);
04164       return __result;
04165     }
04166 
04167   /**
04168    *  @brief Perform an operation on corresponding elements of two sequences.
04169    *  @ingroup mutating_algorithms
04170    *  @param  __first1     An input iterator.
04171    *  @param  __last1      An input iterator.
04172    *  @param  __first2     An input iterator.
04173    *  @param  __result     An output iterator.
04174    *  @param  __binary_op  A binary operator.
04175    *  @return   An output iterator equal to @p result+(last-first).
04176    *
04177    *  Applies the operator to the corresponding elements in the two
04178    *  input ranges and assigns the results to successive elements of the
04179    *  output sequence.
04180    *  Evaluates @p
04181    *  *(__result+N)=__binary_op(*(__first1+N),*(__first2+N)) for each
04182    *  @c N in the range @p [0,__last1-__first1).
04183    *
04184    *  @p binary_op must not alter either of its arguments.
04185   */
04186   template<typename _InputIterator1, typename _InputIterator2,
04187        typename _OutputIterator, typename _BinaryOperation>
04188     _OutputIterator
04189     transform(_InputIterator1 __first1, _InputIterator1 __last1,
04190           _InputIterator2 __first2, _OutputIterator __result,
04191           _BinaryOperation __binary_op)
04192     {
04193       // concept requirements
04194       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
04195       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
04196       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
04197             // "the type returned by a _BinaryOperation"
04198             __typeof__(__binary_op(*__first1,*__first2))>)
04199       __glibcxx_requires_valid_range(__first1, __last1);
04200 
04201       for (; __first1 != __last1; ++__first1, ++__first2, ++__result)
04202     *__result = __binary_op(*__first1, *__first2);
04203       return __result;
04204     }
04205 
04206   /**
04207    *  @brief Replace each occurrence of one value in a sequence with another
04208    *         value.
04209    *  @ingroup mutating_algorithms
04210    *  @param  __first      A forward iterator.
04211    *  @param  __last       A forward iterator.
04212    *  @param  __old_value  The value to be replaced.
04213    *  @param  __new_value  The replacement value.
04214    *  @return   replace() returns no value.
04215    *
04216    *  For each iterator @c i in the range @p [__first,__last) if @c *i ==
04217    *  @p __old_value then the assignment @c *i = @p __new_value is performed.
04218   */
04219   template<typename _ForwardIterator, typename _Tp>
04220     void
04221     replace(_ForwardIterator __first, _ForwardIterator __last,
04222         const _Tp& __old_value, const _Tp& __new_value)
04223     {
04224       // concept requirements
04225       __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
04226                   _ForwardIterator>)
04227       __glibcxx_function_requires(_EqualOpConcept<
04228         typename iterator_traits<_ForwardIterator>::value_type, _Tp>)
04229       __glibcxx_function_requires(_ConvertibleConcept<_Tp,
04230         typename iterator_traits<_ForwardIterator>::value_type>)
04231       __glibcxx_requires_valid_range(__first, __last);
04232 
04233       for (; __first != __last; ++__first)
04234     if (*__first == __old_value)
04235       *__first = __new_value;
04236     }
04237 
04238   /**
04239    *  @brief Replace each value in a sequence for which a predicate returns
04240    *         true with another value.
04241    *  @ingroup mutating_algorithms
04242    *  @param  __first      A forward iterator.
04243    *  @param  __last       A forward iterator.
04244    *  @param  __pred       A predicate.
04245    *  @param  __new_value  The replacement value.
04246    *  @return   replace_if() returns no value.
04247    *
04248    *  For each iterator @c i in the range @p [__first,__last) if @p __pred(*i)
04249    *  is true then the assignment @c *i = @p __new_value is performed.
04250   */
04251   template<typename _ForwardIterator, typename _Predicate, typename _Tp>
04252     void
04253     replace_if(_ForwardIterator __first, _ForwardIterator __last,
04254            _Predicate __pred, const _Tp& __new_value)
04255     {
04256       // concept requirements
04257       __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
04258                   _ForwardIterator>)
04259       __glibcxx_function_requires(_ConvertibleConcept<_Tp,
04260         typename iterator_traits<_ForwardIterator>::value_type>)
04261       __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
04262         typename iterator_traits<_ForwardIterator>::value_type>)
04263       __glibcxx_requires_valid_range(__first, __last);
04264 
04265       for (; __first != __last; ++__first)
04266     if (__pred(*__first))
04267       *__first = __new_value;
04268     }
04269 
04270   /**
04271    *  @brief Assign the result of a function object to each value in a
04272    *         sequence.
04273    *  @ingroup mutating_algorithms
04274    *  @param  __first  A forward iterator.
04275    *  @param  __last   A forward iterator.
04276    *  @param  __gen    A function object taking no arguments and returning
04277    *                 std::iterator_traits<_ForwardIterator>::value_type
04278    *  @return   generate() returns no value.
04279    *
04280    *  Performs the assignment @c *i = @p __gen() for each @c i in the range
04281    *  @p [__first,__last).
04282   */
04283   template<typename _ForwardIterator, typename _Generator>
04284     void
04285     generate(_ForwardIterator __first, _ForwardIterator __last,
04286          _Generator __gen)
04287     {
04288       // concept requirements
04289       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
04290       __glibcxx_function_requires(_GeneratorConcept<_Generator,
04291         typename iterator_traits<_ForwardIterator>::value_type>)
04292       __glibcxx_requires_valid_range(__first, __last);
04293 
04294       for (; __first != __last; ++__first)
04295     *__first = __gen();
04296     }
04297 
04298   /**
04299    *  @brief Assign the result of a function object to each value in a
04300    *         sequence.
04301    *  @ingroup mutating_algorithms
04302    *  @param  __first  A forward iterator.
04303    *  @param  __n      The length of the sequence.
04304    *  @param  __gen    A function object taking no arguments and returning
04305    *                 std::iterator_traits<_ForwardIterator>::value_type
04306    *  @return   The end of the sequence, @p __first+__n
04307    *
04308    *  Performs the assignment @c *i = @p __gen() for each @c i in the range
04309    *  @p [__first,__first+__n).
04310    *
04311    *  _GLIBCXX_RESOLVE_LIB_DEFECTS
04312    *  DR 865. More algorithms that throw away information
04313   */
04314   template<typename _OutputIterator, typename _Size, typename _Generator>
04315     _OutputIterator
04316     generate_n(_OutputIterator __first, _Size __n, _Generator __gen)
04317     {
04318       // concept requirements
04319       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
04320             // "the type returned by a _Generator"
04321             __typeof__(__gen())>)
04322 
04323       for (__decltype(__n + 0) __niter = __n;
04324        __niter > 0; --__niter, ++__first)
04325     *__first = __gen();
04326       return __first;
04327     }
04328 
04329   /**
04330    *  @brief Copy a sequence, removing consecutive duplicate values.
04331    *  @ingroup mutating_algorithms
04332    *  @param  __first   An input iterator.
04333    *  @param  __last    An input iterator.
04334    *  @param  __result  An output iterator.
04335    *  @return   An iterator designating the end of the resulting sequence.
04336    *
04337    *  Copies each element in the range @p [__first,__last) to the range
04338    *  beginning at @p __result, except that only the first element is copied
04339    *  from groups of consecutive elements that compare equal.
04340    *  unique_copy() is stable, so the relative order of elements that are
04341    *  copied is unchanged.
04342    *
04343    *  _GLIBCXX_RESOLVE_LIB_DEFECTS
04344    *  DR 241. Does unique_copy() require CopyConstructible and Assignable?
04345    *  
04346    *  _GLIBCXX_RESOLVE_LIB_DEFECTS
04347    *  DR 538. 241 again: Does unique_copy() require CopyConstructible and 
04348    *  Assignable?
04349   */
04350   template<typename _InputIterator, typename _OutputIterator>
04351     inline _OutputIterator
04352     unique_copy(_InputIterator __first, _InputIterator __last,
04353         _OutputIterator __result)
04354     {
04355       // concept requirements
04356       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
04357       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
04358         typename iterator_traits<_InputIterator>::value_type>)
04359       __glibcxx_function_requires(_EqualityComparableConcept<
04360         typename iterator_traits<_InputIterator>::value_type>)
04361       __glibcxx_requires_valid_range(__first, __last);
04362 
04363       if (__first == __last)
04364     return __result;
04365       return std::__unique_copy(__first, __last, __result,
04366                 __gnu_cxx::__ops::__iter_equal_to_iter(),
04367                 std::__iterator_category(__first),
04368                 std::__iterator_category(__result));
04369     }
04370 
04371   /**
04372    *  @brief Copy a sequence, removing consecutive values using a predicate.
04373    *  @ingroup mutating_algorithms
04374    *  @param  __first        An input iterator.
04375    *  @param  __last         An input iterator.
04376    *  @param  __result       An output iterator.
04377    *  @param  __binary_pred  A binary predicate.
04378    *  @return   An iterator designating the end of the resulting sequence.
04379    *
04380    *  Copies each element in the range @p [__first,__last) to the range
04381    *  beginning at @p __result, except that only the first element is copied
04382    *  from groups of consecutive elements for which @p __binary_pred returns
04383    *  true.
04384    *  unique_copy() is stable, so the relative order of elements that are
04385    *  copied is unchanged.
04386    *
04387    *  _GLIBCXX_RESOLVE_LIB_DEFECTS
04388    *  DR 241. Does unique_copy() require CopyConstructible and Assignable?
04389   */
04390   template<typename _InputIterator, typename _OutputIterator,
04391        typename _BinaryPredicate>
04392     inline _OutputIterator
04393     unique_copy(_InputIterator __first, _InputIterator __last,
04394         _OutputIterator __result,
04395         _BinaryPredicate __binary_pred)
04396     {
04397       // concept requirements -- predicates checked later
04398       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
04399       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
04400         typename iterator_traits<_InputIterator>::value_type>)
04401       __glibcxx_requires_valid_range(__first, __last);
04402 
04403       if (__first == __last)
04404     return __result;
04405       return std::__unique_copy(__first, __last, __result,
04406             __gnu_cxx::__ops::__iter_comp_iter(__binary_pred),
04407                 std::__iterator_category(__first),
04408                 std::__iterator_category(__result));
04409     }
04410 
04411   /**
04412    *  @brief Randomly shuffle the elements of a sequence.
04413    *  @ingroup mutating_algorithms
04414    *  @param  __first   A forward iterator.
04415    *  @param  __last    A forward iterator.
04416    *  @return  Nothing.
04417    *
04418    *  Reorder the elements in the range @p [__first,__last) using a random
04419    *  distribution, so that every possible ordering of the sequence is
04420    *  equally likely.
04421   */
04422   template<typename _RandomAccessIterator>
04423     inline void
04424     random_shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last)
04425     {
04426       // concept requirements
04427       __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
04428         _RandomAccessIterator>)
04429       __glibcxx_requires_valid_range(__first, __last);
04430 
04431       if (__first != __last)
04432     for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i)
04433       std::iter_swap(__i, __first + (std::rand() % ((__i - __first) + 1)));
04434     }
04435 
04436   /**
04437    *  @brief Shuffle the elements of a sequence using a random number
04438    *         generator.
04439    *  @ingroup mutating_algorithms
04440    *  @param  __first   A forward iterator.
04441    *  @param  __last    A forward iterator.
04442    *  @param  __rand    The RNG functor or function.
04443    *  @return  Nothing.
04444    *
04445    *  Reorders the elements in the range @p [__first,__last) using @p __rand to
04446    *  provide a random distribution. Calling @p __rand(N) for a positive
04447    *  integer @p N should return a randomly chosen integer from the
04448    *  range [0,N).
04449   */
04450   template<typename _RandomAccessIterator, typename _RandomNumberGenerator>
04451     void
04452     random_shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last,
04453 #if __cplusplus >= 201103L
04454            _RandomNumberGenerator&& __rand)
04455 #else
04456            _RandomNumberGenerator& __rand)
04457 #endif
04458     {
04459       // concept requirements
04460       __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
04461         _RandomAccessIterator>)
04462       __glibcxx_requires_valid_range(__first, __last);
04463 
04464       if (__first == __last)
04465     return;
04466       for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i)
04467     std::iter_swap(__i, __first + __rand((__i - __first) + 1));
04468     }
04469 
04470 
04471   /**
04472    *  @brief Move elements for which a predicate is true to the beginning
04473    *         of a sequence.
04474    *  @ingroup mutating_algorithms
04475    *  @param  __first   A forward iterator.
04476    *  @param  __last    A forward iterator.
04477    *  @param  __pred    A predicate functor.
04478    *  @return  An iterator @p middle such that @p __pred(i) is true for each
04479    *  iterator @p i in the range @p [__first,middle) and false for each @p i
04480    *  in the range @p [middle,__last).
04481    *
04482    *  @p __pred must not modify its operand. @p partition() does not preserve
04483    *  the relative ordering of elements in each group, use
04484    *  @p stable_partition() if this is needed.
04485   */
04486   template<typename _ForwardIterator, typename _Predicate>
04487     inline _ForwardIterator
04488     partition(_ForwardIterator __first, _ForwardIterator __last,
04489           _Predicate   __pred)
04490     {
04491       // concept requirements
04492       __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
04493                   _ForwardIterator>)
04494       __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
04495         typename iterator_traits<_ForwardIterator>::value_type>)
04496       __glibcxx_requires_valid_range(__first, __last);
04497 
04498       return std::__partition(__first, __last, __pred,
04499                   std::__iterator_category(__first));
04500     }
04501 
04502 
04503   /**
04504    *  @brief Sort the smallest elements of a sequence.
04505    *  @ingroup sorting_algorithms
04506    *  @param  __first   An iterator.
04507    *  @param  __middle  Another iterator.
04508    *  @param  __last    Another iterator.
04509    *  @return  Nothing.
04510    *
04511    *  Sorts the smallest @p (__middle-__first) elements in the range
04512    *  @p [first,last) and moves them to the range @p [__first,__middle). The
04513    *  order of the remaining elements in the range @p [__middle,__last) is
04514    *  undefined.
04515    *  After the sort if @e i and @e j are iterators in the range
04516    *  @p [__first,__middle) such that i precedes j and @e k is an iterator in
04517    *  the range @p [__middle,__last) then *j<*i and *k<*i are both false.
04518   */
04519   template<typename _RandomAccessIterator>
04520     inline void
04521     partial_sort(_RandomAccessIterator __first,
04522          _RandomAccessIterator __middle,
04523          _RandomAccessIterator __last)
04524     {
04525       // concept requirements
04526       __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
04527         _RandomAccessIterator>)
04528       __glibcxx_function_requires(_LessThanComparableConcept<
04529         typename iterator_traits<_RandomAccessIterator>::value_type>)
04530       __glibcxx_requires_valid_range(__first, __middle);
04531       __glibcxx_requires_valid_range(__middle, __last);
04532 
04533       std::__partial_sort(__first, __middle, __last,
04534               __gnu_cxx::__ops::__iter_less_iter());
04535     }
04536 
04537   /**
04538    *  @brief Sort the smallest elements of a sequence using a predicate
04539    *         for comparison.
04540    *  @ingroup sorting_algorithms
04541    *  @param  __first   An iterator.
04542    *  @param  __middle  Another iterator.
04543    *  @param  __last    Another iterator.
04544    *  @param  __comp    A comparison functor.
04545    *  @return  Nothing.
04546    *
04547    *  Sorts the smallest @p (__middle-__first) elements in the range
04548    *  @p [__first,__last) and moves them to the range @p [__first,__middle). The
04549    *  order of the remaining elements in the range @p [__middle,__last) is
04550    *  undefined.
04551    *  After the sort if @e i and @e j are iterators in the range
04552    *  @p [__first,__middle) such that i precedes j and @e k is an iterator in
04553    *  the range @p [__middle,__last) then @p *__comp(j,*i) and @p __comp(*k,*i)
04554    *  are both false.
04555   */
04556   template<typename _RandomAccessIterator, typename _Compare>
04557     inline void
04558     partial_sort(_RandomAccessIterator __first,
04559          _RandomAccessIterator __middle,
04560          _RandomAccessIterator __last,
04561          _Compare __comp)
04562     {
04563       // concept requirements
04564       __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
04565         _RandomAccessIterator>)
04566       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
04567         typename iterator_traits<_RandomAccessIterator>::value_type,
04568         typename iterator_traits<_RandomAccessIterator>::value_type>)
04569       __glibcxx_requires_valid_range(__first, __middle);
04570       __glibcxx_requires_valid_range(__middle, __last);
04571 
04572       std::__partial_sort(__first, __middle, __last,
04573               __gnu_cxx::__ops::__iter_comp_iter(__comp));
04574     }
04575 
04576   /**
04577    *  @brief Sort a sequence just enough to find a particular position.
04578    *  @ingroup sorting_algorithms
04579    *  @param  __first   An iterator.
04580    *  @param  __nth     Another iterator.
04581    *  @param  __last    Another iterator.
04582    *  @return  Nothing.
04583    *
04584    *  Rearranges the elements in the range @p [__first,__last) so that @p *__nth
04585    *  is the same element that would have been in that position had the
04586    *  whole sequence been sorted. The elements either side of @p *__nth are
04587    *  not completely sorted, but for any iterator @e i in the range
04588    *  @p [__first,__nth) and any iterator @e j in the range @p [__nth,__last) it
04589    *  holds that *j < *i is false.
04590   */
04591   template<typename _RandomAccessIterator>
04592     inline void
04593     nth_element(_RandomAccessIterator __first, _RandomAccessIterator __nth,
04594         _RandomAccessIterator __last)
04595     {
04596       // concept requirements
04597       __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
04598                   _RandomAccessIterator>)
04599       __glibcxx_function_requires(_LessThanComparableConcept<
04600         typename iterator_traits<_RandomAccessIterator>::value_type>)
04601       __glibcxx_requires_valid_range(__first, __nth);
04602       __glibcxx_requires_valid_range(__nth, __last);
04603 
04604       if (__first == __last || __nth == __last)
04605     return;
04606 
04607       std::__introselect(__first, __nth, __last,
04608              std::__lg(__last - __first) * 2,
04609              __gnu_cxx::__ops::__iter_less_iter());
04610     }
04611 
04612   /**
04613    *  @brief Sort a sequence just enough to find a particular position
04614    *         using a predicate for comparison.
04615    *  @ingroup sorting_algorithms
04616    *  @param  __first   An iterator.
04617    *  @param  __nth     Another iterator.
04618    *  @param  __last    Another iterator.
04619    *  @param  __comp    A comparison functor.
04620    *  @return  Nothing.
04621    *
04622    *  Rearranges the elements in the range @p [__first,__last) so that @p *__nth
04623    *  is the same element that would have been in that position had the
04624    *  whole sequence been sorted. The elements either side of @p *__nth are
04625    *  not completely sorted, but for any iterator @e i in the range
04626    *  @p [__first,__nth) and any iterator @e j in the range @p [__nth,__last) it
04627    *  holds that @p __comp(*j,*i) is false.
04628   */
04629   template<typename _RandomAccessIterator, typename _Compare>
04630     inline void
04631     nth_element(_RandomAccessIterator __first, _RandomAccessIterator __nth,
04632         _RandomAccessIterator __last, _Compare __comp)
04633     {
04634       // concept requirements
04635       __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
04636                   _RandomAccessIterator>)
04637       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
04638         typename iterator_traits<_RandomAccessIterator>::value_type,
04639         typename iterator_traits<_RandomAccessIterator>::value_type>)
04640       __glibcxx_requires_valid_range(__first, __nth);
04641       __glibcxx_requires_valid_range(__nth, __last);
04642 
04643       if (__first == __last || __nth == __last)
04644     return;
04645 
04646       std::__introselect(__first, __nth, __last,
04647              std::__lg(__last - __first) * 2,
04648              __gnu_cxx::__ops::__iter_comp_iter(__comp));
04649     }
04650 
04651   /**
04652    *  @brief Sort the elements of a sequence.
04653    *  @ingroup sorting_algorithms
04654    *  @param  __first   An iterator.
04655    *  @param  __last    Another iterator.
04656    *  @return  Nothing.
04657    *
04658    *  Sorts the elements in the range @p [__first,__last) in ascending order,
04659    *  such that for each iterator @e i in the range @p [__first,__last-1),  
04660    *  *(i+1)<*i is false.
04661    *
04662    *  The relative ordering of equivalent elements is not preserved, use
04663    *  @p stable_sort() if this is needed.
04664   */
04665   template<typename _RandomAccessIterator>
04666     inline void
04667     sort(_RandomAccessIterator __first, _RandomAccessIterator __last)
04668     {
04669       // concept requirements
04670       __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
04671         _RandomAccessIterator>)
04672       __glibcxx_function_requires(_LessThanComparableConcept<
04673         typename iterator_traits<_RandomAccessIterator>::value_type>)
04674       __glibcxx_requires_valid_range(__first, __last);
04675 
04676       std::__sort(__first, __last, __gnu_cxx::__ops::__iter_less_iter());
04677     }
04678 
04679   /**
04680    *  @brief Sort the elements of a sequence using a predicate for comparison.
04681    *  @ingroup sorting_algorithms
04682    *  @param  __first   An iterator.
04683    *  @param  __last    Another iterator.
04684    *  @param  __comp    A comparison functor.
04685    *  @return  Nothing.
04686    *
04687    *  Sorts the elements in the range @p [__first,__last) in ascending order,
04688    *  such that @p __comp(*(i+1),*i) is false for every iterator @e i in the
04689    *  range @p [__first,__last-1).
04690    *
04691    *  The relative ordering of equivalent elements is not preserved, use
04692    *  @p stable_sort() if this is needed.
04693   */
04694   template<typename _RandomAccessIterator, typename _Compare>
04695     inline void
04696     sort(_RandomAccessIterator __first, _RandomAccessIterator __last,
04697      _Compare __comp)
04698     {
04699       // concept requirements
04700       __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
04701         _RandomAccessIterator>)
04702       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
04703         typename iterator_traits<_RandomAccessIterator>::value_type,
04704         typename iterator_traits<_RandomAccessIterator>::value_type>)
04705       __glibcxx_requires_valid_range(__first, __last);
04706 
04707       std::__sort(__first, __last, __gnu_cxx::__ops::__iter_comp_iter(__comp));
04708     }
04709 
04710   template<typename _InputIterator1, typename _InputIterator2,
04711        typename _OutputIterator, typename _Compare>
04712     _OutputIterator
04713     __merge(_InputIterator1 __first1, _InputIterator1 __last1,
04714         _InputIterator2 __first2, _InputIterator2 __last2,
04715         _OutputIterator __result, _Compare __comp)
04716     {
04717       while (__first1 != __last1 && __first2 != __last2)
04718     {
04719       if (__comp(__first2, __first1))
04720         {
04721           *__result = *__first2;
04722           ++__first2;
04723         }
04724       else
04725         {
04726           *__result = *__first1;
04727           ++__first1;
04728         }
04729       ++__result;
04730     }
04731       return std::copy(__first2, __last2,
04732                std::copy(__first1, __last1, __result));
04733     }
04734 
04735   /**
04736    *  @brief Merges two sorted ranges.
04737    *  @ingroup sorting_algorithms
04738    *  @param  __first1  An iterator.
04739    *  @param  __first2  Another iterator.
04740    *  @param  __last1   Another iterator.
04741    *  @param  __last2   Another iterator.
04742    *  @param  __result  An iterator pointing to the end of the merged range.
04743    *  @return         An iterator pointing to the first element <em>not less
04744    *                  than</em> @e val.
04745    *
04746    *  Merges the ranges @p [__first1,__last1) and @p [__first2,__last2) into
04747    *  the sorted range @p [__result, __result + (__last1-__first1) +
04748    *  (__last2-__first2)).  Both input ranges must be sorted, and the
04749    *  output range must not overlap with either of the input ranges.
04750    *  The sort is @e stable, that is, for equivalent elements in the
04751    *  two ranges, elements from the first range will always come
04752    *  before elements from the second.
04753   */
04754   template<typename _InputIterator1, typename _InputIterator2,
04755        typename _OutputIterator>
04756     inline _OutputIterator
04757     merge(_InputIterator1 __first1, _InputIterator1 __last1,
04758       _InputIterator2 __first2, _InputIterator2 __last2,
04759       _OutputIterator __result)
04760     {
04761       // concept requirements
04762       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
04763       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
04764       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
04765         typename iterator_traits<_InputIterator1>::value_type>)
04766       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
04767         typename iterator_traits<_InputIterator2>::value_type>)
04768       __glibcxx_function_requires(_LessThanOpConcept<
04769         typename iterator_traits<_InputIterator2>::value_type,
04770         typename iterator_traits<_InputIterator1>::value_type>) 
04771       __glibcxx_requires_sorted_set(__first1, __last1, __first2);
04772       __glibcxx_requires_sorted_set(__first2, __last2, __first1);
04773 
04774       return _GLIBCXX_STD_A::__merge(__first1, __last1,
04775                      __first2, __last2, __result,
04776                      __gnu_cxx::__ops::__iter_less_iter());
04777     }
04778 
04779   /**
04780    *  @brief Merges two sorted ranges.
04781    *  @ingroup sorting_algorithms
04782    *  @param  __first1  An iterator.
04783    *  @param  __first2  Another iterator.
04784    *  @param  __last1   Another iterator.
04785    *  @param  __last2   Another iterator.
04786    *  @param  __result  An iterator pointing to the end of the merged range.
04787    *  @param  __comp    A functor to use for comparisons.
04788    *  @return         An iterator pointing to the first element "not less
04789    *                  than" @e val.
04790    *
04791    *  Merges the ranges @p [__first1,__last1) and @p [__first2,__last2) into
04792    *  the sorted range @p [__result, __result + (__last1-__first1) +
04793    *  (__last2-__first2)).  Both input ranges must be sorted, and the
04794    *  output range must not overlap with either of the input ranges.
04795    *  The sort is @e stable, that is, for equivalent elements in the
04796    *  two ranges, elements from the first range will always come
04797    *  before elements from the second.
04798    *
04799    *  The comparison function should have the same effects on ordering as
04800    *  the function used for the initial sort.
04801   */
04802   template<typename _InputIterator1, typename _InputIterator2,
04803        typename _OutputIterator, typename _Compare>
04804     inline _OutputIterator
04805     merge(_InputIterator1 __first1, _InputIterator1 __last1,
04806       _InputIterator2 __first2, _InputIterator2 __last2,
04807       _OutputIterator __result, _Compare __comp)
04808     {
04809       // concept requirements
04810       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
04811       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
04812       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
04813         typename iterator_traits<_InputIterator1>::value_type>)
04814       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
04815         typename iterator_traits<_InputIterator2>::value_type>)
04816       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
04817         typename iterator_traits<_InputIterator2>::value_type,
04818         typename iterator_traits<_InputIterator1>::value_type>)
04819       __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp);
04820       __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp);
04821 
04822       return _GLIBCXX_STD_A::__merge(__first1, __last1,
04823                 __first2, __last2, __result,
04824                 __gnu_cxx::__ops::__iter_comp_iter(__comp));
04825     }
04826 
04827   template<typename _RandomAccessIterator, typename _Compare>
04828     inline void
04829     __stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last,
04830           _Compare __comp)
04831     {
04832       typedef typename iterator_traits<_RandomAccessIterator>::value_type
04833     _ValueType;
04834       typedef typename iterator_traits<_RandomAccessIterator>::difference_type
04835     _DistanceType;
04836 
04837       typedef _Temporary_buffer<_RandomAccessIterator, _ValueType> _TmpBuf;
04838       _TmpBuf __buf(__first, __last);
04839 
04840       if (__buf.begin() == 0)
04841     std::__inplace_stable_sort(__first, __last, __comp);
04842       else
04843     std::__stable_sort_adaptive(__first, __last, __buf.begin(),
04844                     _DistanceType(__buf.size()), __comp);
04845     }
04846 
04847   /**
04848    *  @brief Sort the elements of a sequence, preserving the relative order
04849    *         of equivalent elements.
04850    *  @ingroup sorting_algorithms
04851    *  @param  __first   An iterator.
04852    *  @param  __last    Another iterator.
04853    *  @return  Nothing.
04854    *
04855    *  Sorts the elements in the range @p [__first,__last) in ascending order,
04856    *  such that for each iterator @p i in the range @p [__first,__last-1),
04857    *  @p *(i+1)<*i is false.
04858    *
04859    *  The relative ordering of equivalent elements is preserved, so any two
04860    *  elements @p x and @p y in the range @p [__first,__last) such that
04861    *  @p x<y is false and @p y<x is false will have the same relative
04862    *  ordering after calling @p stable_sort().
04863   */
04864   template<typename _RandomAccessIterator>
04865     inline void
04866     stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last)
04867     {
04868       // concept requirements
04869       __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
04870         _RandomAccessIterator>)
04871       __glibcxx_function_requires(_LessThanComparableConcept<
04872         typename iterator_traits<_RandomAccessIterator>::value_type>)
04873       __glibcxx_requires_valid_range(__first, __last);
04874 
04875       _GLIBCXX_STD_A::__stable_sort(__first, __last,
04876                     __gnu_cxx::__ops::__iter_less_iter());
04877     }
04878 
04879   /**
04880    *  @brief Sort the elements of a sequence using a predicate for comparison,
04881    *         preserving the relative order of equivalent elements.
04882    *  @ingroup sorting_algorithms
04883    *  @param  __first   An iterator.
04884    *  @param  __last    Another iterator.
04885    *  @param  __comp    A comparison functor.
04886    *  @return  Nothing.
04887    *
04888    *  Sorts the elements in the range @p [__first,__last) in ascending order,
04889    *  such that for each iterator @p i in the range @p [__first,__last-1),
04890    *  @p __comp(*(i+1),*i) is false.
04891    *
04892    *  The relative ordering of equivalent elements is preserved, so any two
04893    *  elements @p x and @p y in the range @p [__first,__last) such that
04894    *  @p __comp(x,y) is false and @p __comp(y,x) is false will have the same
04895    *  relative ordering after calling @p stable_sort().
04896   */
04897   template<typename _RandomAccessIterator, typename _Compare>
04898     inline void
04899     stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last,
04900         _Compare __comp)
04901     {
04902       // concept requirements
04903       __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
04904         _RandomAccessIterator>)
04905       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
04906         typename iterator_traits<_RandomAccessIterator>::value_type,
04907         typename iterator_traits<_RandomAccessIterator>::value_type>)
04908       __glibcxx_requires_valid_range(__first, __last);
04909 
04910       _GLIBCXX_STD_A::__stable_sort(__first, __last,
04911                     __gnu_cxx::__ops::__iter_comp_iter(__comp));
04912     }
04913 
04914   template<typename _InputIterator1, typename _InputIterator2,
04915        typename _OutputIterator,
04916        typename _Compare>
04917     _OutputIterator
04918     __set_union(_InputIterator1 __first1, _InputIterator1 __last1,
04919         _InputIterator2 __first2, _InputIterator2 __last2,
04920         _OutputIterator __result, _Compare __comp)
04921     {
04922       while (__first1 != __last1 && __first2 != __last2)
04923     {
04924       if (__comp(__first1, __first2))
04925         {
04926           *__result = *__first1;
04927           ++__first1;
04928         }
04929       else if (__comp(__first2, __first1))
04930         {
04931           *__result = *__first2;
04932           ++__first2;
04933         }
04934       else
04935         {
04936           *__result = *__first1;
04937           ++__first1;
04938           ++__first2;
04939         }
04940       ++__result;
04941     }
04942       return std::copy(__first2, __last2,
04943                std::copy(__first1, __last1, __result));
04944     }
04945 
04946   /**
04947    *  @brief Return the union of two sorted ranges.
04948    *  @ingroup set_algorithms
04949    *  @param  __first1  Start of first range.
04950    *  @param  __last1   End of first range.
04951    *  @param  __first2  Start of second range.
04952    *  @param  __last2   End of second range.
04953    *  @return  End of the output range.
04954    *  @ingroup set_algorithms
04955    *
04956    *  This operation iterates over both ranges, copying elements present in
04957    *  each range in order to the output range.  Iterators increment for each
04958    *  range.  When the current element of one range is less than the other,
04959    *  that element is copied and the iterator advanced.  If an element is
04960    *  contained in both ranges, the element from the first range is copied and
04961    *  both ranges advance.  The output range may not overlap either input
04962    *  range.
04963   */
04964   template<typename _InputIterator1, typename _InputIterator2,
04965        typename _OutputIterator>
04966     inline _OutputIterator
04967     set_union(_InputIterator1 __first1, _InputIterator1 __last1,
04968           _InputIterator2 __first2, _InputIterator2 __last2,
04969           _OutputIterator __result)
04970     {
04971       // concept requirements
04972       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
04973       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
04974       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
04975         typename iterator_traits<_InputIterator1>::value_type>)
04976       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
04977         typename iterator_traits<_InputIterator2>::value_type>)
04978       __glibcxx_function_requires(_LessThanOpConcept<
04979         typename iterator_traits<_InputIterator1>::value_type,
04980         typename iterator_traits<_InputIterator2>::value_type>)
04981       __glibcxx_function_requires(_LessThanOpConcept<
04982         typename iterator_traits<_InputIterator2>::value_type,
04983         typename iterator_traits<_InputIterator1>::value_type>)
04984       __glibcxx_requires_sorted_set(__first1, __last1, __first2);
04985       __glibcxx_requires_sorted_set(__first2, __last2, __first1);
04986 
04987       return _GLIBCXX_STD_A::__set_union(__first1, __last1,
04988                 __first2, __last2, __result,
04989                 __gnu_cxx::__ops::__iter_less_iter());
04990     }
04991 
04992   /**
04993    *  @brief Return the union of two sorted ranges using a comparison functor.
04994    *  @ingroup set_algorithms
04995    *  @param  __first1  Start of first range.
04996    *  @param  __last1   End of first range.
04997    *  @param  __first2  Start of second range.
04998    *  @param  __last2   End of second range.
04999    *  @param  __comp    The comparison functor.
05000    *  @return  End of the output range.
05001    *  @ingroup set_algorithms
05002    *
05003    *  This operation iterates over both ranges, copying elements present in
05004    *  each range in order to the output range.  Iterators increment for each
05005    *  range.  When the current element of one range is less than the other
05006    *  according to @p __comp, that element is copied and the iterator advanced.
05007    *  If an equivalent element according to @p __comp is contained in both
05008    *  ranges, the element from the first range is copied and both ranges
05009    *  advance.  The output range may not overlap either input range.
05010   */
05011   template<typename _InputIterator1, typename _InputIterator2,
05012        typename _OutputIterator, typename _Compare>
05013     inline _OutputIterator
05014     set_union(_InputIterator1 __first1, _InputIterator1 __last1,
05015           _InputIterator2 __first2, _InputIterator2 __last2,
05016           _OutputIterator __result, _Compare __comp)
05017     {
05018       // concept requirements
05019       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
05020       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
05021       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
05022         typename iterator_traits<_InputIterator1>::value_type>)
05023       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
05024         typename iterator_traits<_InputIterator2>::value_type>)
05025       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
05026         typename iterator_traits<_InputIterator1>::value_type,
05027         typename iterator_traits<_InputIterator2>::value_type>)
05028       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
05029         typename iterator_traits<_InputIterator2>::value_type,
05030         typename iterator_traits<_InputIterator1>::value_type>)
05031       __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp);
05032       __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp);
05033 
05034       return _GLIBCXX_STD_A::__set_union(__first1, __last1,
05035                 __first2, __last2, __result,
05036                 __gnu_cxx::__ops::__iter_comp_iter(__comp));
05037     }
05038 
05039   template<typename _InputIterator1, typename _InputIterator2,
05040        typename _OutputIterator,
05041        typename _Compare>
05042     _OutputIterator
05043     __set_intersection(_InputIterator1 __first1, _InputIterator1 __last1,
05044                _InputIterator2 __first2, _InputIterator2 __last2,
05045                _OutputIterator __result, _Compare __comp)
05046     {
05047       while (__first1 != __last1 && __first2 != __last2)
05048     if (__comp(__first1, __first2))
05049       ++__first1;
05050     else if (__comp(__first2, __first1))
05051       ++__first2;
05052     else
05053       {
05054         *__result = *__first1;
05055         ++__first1;
05056         ++__first2;
05057         ++__result;
05058       }
05059       return __result;
05060     }
05061 
05062   /**
05063    *  @brief Return the intersection of two sorted ranges.
05064    *  @ingroup set_algorithms
05065    *  @param  __first1  Start of first range.
05066    *  @param  __last1   End of first range.
05067    *  @param  __first2  Start of second range.
05068    *  @param  __last2   End of second range.
05069    *  @return  End of the output range.
05070    *  @ingroup set_algorithms
05071    *
05072    *  This operation iterates over both ranges, copying elements present in
05073    *  both ranges in order to the output range.  Iterators increment for each
05074    *  range.  When the current element of one range is less than the other,
05075    *  that iterator advances.  If an element is contained in both ranges, the
05076    *  element from the first range is copied and both ranges advance.  The
05077    *  output range may not overlap either input range.
05078   */
05079   template<typename _InputIterator1, typename _InputIterator2,
05080        typename _OutputIterator>
05081     inline _OutputIterator
05082     set_intersection(_InputIterator1 __first1, _InputIterator1 __last1,
05083              _InputIterator2 __first2, _InputIterator2 __last2,
05084              _OutputIterator __result)
05085     {
05086       // concept requirements
05087       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
05088       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
05089       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
05090         typename iterator_traits<_InputIterator1>::value_type>)
05091       __glibcxx_function_requires(_LessThanOpConcept<
05092         typename iterator_traits<_InputIterator1>::value_type,
05093         typename iterator_traits<_InputIterator2>::value_type>)
05094       __glibcxx_function_requires(_LessThanOpConcept<
05095         typename iterator_traits<_InputIterator2>::value_type,
05096         typename iterator_traits<_InputIterator1>::value_type>)
05097       __glibcxx_requires_sorted_set(__first1, __last1, __first2);
05098       __glibcxx_requires_sorted_set(__first2, __last2, __first1);
05099 
05100       return _GLIBCXX_STD_A::__set_intersection(__first1, __last1,
05101                      __first2, __last2, __result,
05102                      __gnu_cxx::__ops::__iter_less_iter());
05103     }
05104 
05105   /**
05106    *  @brief Return the intersection of two sorted ranges using comparison
05107    *  functor.
05108    *  @ingroup set_algorithms
05109    *  @param  __first1  Start of first range.
05110    *  @param  __last1   End of first range.
05111    *  @param  __first2  Start of second range.
05112    *  @param  __last2   End of second range.
05113    *  @param  __comp    The comparison functor.
05114    *  @return  End of the output range.
05115    *  @ingroup set_algorithms
05116    *
05117    *  This operation iterates over both ranges, copying elements present in
05118    *  both ranges in order to the output range.  Iterators increment for each
05119    *  range.  When the current element of one range is less than the other
05120    *  according to @p __comp, that iterator advances.  If an element is
05121    *  contained in both ranges according to @p __comp, the element from the
05122    *  first range is copied and both ranges advance.  The output range may not
05123    *  overlap either input range.
05124   */
05125   template<typename _InputIterator1, typename _InputIterator2,
05126        typename _OutputIterator, typename _Compare>
05127     inline _OutputIterator
05128     set_intersection(_InputIterator1 __first1, _InputIterator1 __last1,
05129              _InputIterator2 __first2, _InputIterator2 __last2,
05130              _OutputIterator __result, _Compare __comp)
05131     {
05132       // concept requirements
05133       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
05134       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
05135       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
05136         typename iterator_traits<_InputIterator1>::value_type>)
05137       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
05138         typename iterator_traits<_InputIterator1>::value_type,
05139         typename iterator_traits<_InputIterator2>::value_type>)
05140       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
05141         typename iterator_traits<_InputIterator2>::value_type,
05142         typename iterator_traits<_InputIterator1>::value_type>)
05143       __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp);
05144       __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp);
05145 
05146       return _GLIBCXX_STD_A::__set_intersection(__first1, __last1,
05147                 __first2, __last2, __result,
05148                 __gnu_cxx::__ops::__iter_comp_iter(__comp));
05149     }
05150 
05151   template<typename _InputIterator1, typename _InputIterator2,
05152        typename _OutputIterator,
05153        typename _Compare>
05154     _OutputIterator
05155     __set_difference(_InputIterator1 __first1, _InputIterator1 __last1,
05156              _InputIterator2 __first2, _InputIterator2 __last2,
05157              _OutputIterator __result, _Compare __comp)
05158     {
05159       while (__first1 != __last1 && __first2 != __last2)
05160     if (__comp(__first1, __first2))
05161       {
05162         *__result = *__first1;
05163         ++__first1;
05164         ++__result;
05165       }
05166     else if (__comp(__first2, __first1))
05167       ++__first2;
05168     else
05169       {
05170         ++__first1;
05171         ++__first2;
05172       }
05173       return std::copy(__first1, __last1, __result);
05174     }
05175 
05176   /**
05177    *  @brief Return the difference of two sorted ranges.
05178    *  @ingroup set_algorithms
05179    *  @param  __first1  Start of first range.
05180    *  @param  __last1   End of first range.
05181    *  @param  __first2  Start of second range.
05182    *  @param  __last2   End of second range.
05183    *  @return  End of the output range.
05184    *  @ingroup set_algorithms
05185    *
05186    *  This operation iterates over both ranges, copying elements present in
05187    *  the first range but not the second in order to the output range.
05188    *  Iterators increment for each range.  When the current element of the
05189    *  first range is less than the second, that element is copied and the
05190    *  iterator advances.  If the current element of the second range is less,
05191    *  the iterator advances, but no element is copied.  If an element is
05192    *  contained in both ranges, no elements are copied and both ranges
05193    *  advance.  The output range may not overlap either input range.
05194   */
05195   template<typename _InputIterator1, typename _InputIterator2,
05196        typename _OutputIterator>
05197     inline _OutputIterator
05198     set_difference(_InputIterator1 __first1, _InputIterator1 __last1,
05199            _InputIterator2 __first2, _InputIterator2 __last2,
05200            _OutputIterator __result)
05201     {
05202       // concept requirements
05203       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
05204       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
05205       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
05206         typename iterator_traits<_InputIterator1>::value_type>)
05207       __glibcxx_function_requires(_LessThanOpConcept<
05208         typename iterator_traits<_InputIterator1>::value_type,
05209         typename iterator_traits<_InputIterator2>::value_type>)
05210       __glibcxx_function_requires(_LessThanOpConcept<
05211         typename iterator_traits<_InputIterator2>::value_type,
05212         typename iterator_traits<_InputIterator1>::value_type>) 
05213       __glibcxx_requires_sorted_set(__first1, __last1, __first2);
05214       __glibcxx_requires_sorted_set(__first2, __last2, __first1);
05215 
05216       return _GLIBCXX_STD_A::__set_difference(__first1, __last1,
05217                    __first2, __last2, __result,
05218                    __gnu_cxx::__ops::__iter_less_iter());
05219     }
05220 
05221   /**
05222    *  @brief  Return the difference of two sorted ranges using comparison
05223    *  functor.
05224    *  @ingroup set_algorithms
05225    *  @param  __first1  Start of first range.
05226    *  @param  __last1   End of first range.
05227    *  @param  __first2  Start of second range.
05228    *  @param  __last2   End of second range.
05229    *  @param  __comp    The comparison functor.
05230    *  @return  End of the output range.
05231    *  @ingroup set_algorithms
05232    *
05233    *  This operation iterates over both ranges, copying elements present in
05234    *  the first range but not the second in order to the output range.
05235    *  Iterators increment for each range.  When the current element of the
05236    *  first range is less than the second according to @p __comp, that element
05237    *  is copied and the iterator advances.  If the current element of the
05238    *  second range is less, no element is copied and the iterator advances.
05239    *  If an element is contained in both ranges according to @p __comp, no
05240    *  elements are copied and both ranges advance.  The output range may not
05241    *  overlap either input range.
05242   */
05243   template<typename _InputIterator1, typename _InputIterator2,
05244        typename _OutputIterator, typename _Compare>
05245     inline _OutputIterator
05246     set_difference(_InputIterator1 __first1, _InputIterator1 __last1,
05247            _InputIterator2 __first2, _InputIterator2 __last2,
05248            _OutputIterator __result, _Compare __comp)
05249     {
05250       // concept requirements
05251       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
05252       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
05253       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
05254         typename iterator_traits<_InputIterator1>::value_type>)
05255       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
05256         typename iterator_traits<_InputIterator1>::value_type,
05257         typename iterator_traits<_InputIterator2>::value_type>)
05258       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
05259         typename iterator_traits<_InputIterator2>::value_type,
05260         typename iterator_traits<_InputIterator1>::value_type>)
05261       __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp);
05262       __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp);
05263 
05264       return _GLIBCXX_STD_A::__set_difference(__first1, __last1,
05265                    __first2, __last2, __result,
05266                    __gnu_cxx::__ops::__iter_comp_iter(__comp));
05267     }
05268 
05269   template<typename _InputIterator1, typename _InputIterator2,
05270        typename _OutputIterator,
05271        typename _Compare>
05272     _OutputIterator
05273     __set_symmetric_difference(_InputIterator1 __first1,
05274                    _InputIterator1 __last1,
05275                    _InputIterator2 __first2,
05276                    _InputIterator2 __last2,
05277                    _OutputIterator __result,
05278                    _Compare __comp)
05279     {
05280       while (__first1 != __last1 && __first2 != __last2)
05281     if (__comp(__first1, __first2))
05282       {
05283         *__result = *__first1;
05284         ++__first1;
05285         ++__result;
05286       }
05287     else if (__comp(__first2, __first1))
05288       {
05289         *__result = *__first2;
05290         ++__first2;
05291         ++__result;
05292       }
05293     else
05294       {
05295         ++__first1;
05296         ++__first2;
05297       }
05298       return std::copy(__first2, __last2, 
05299                std::copy(__first1, __last1, __result));
05300     }
05301 
05302   /**
05303    *  @brief  Return the symmetric difference of two sorted ranges.
05304    *  @ingroup set_algorithms
05305    *  @param  __first1  Start of first range.
05306    *  @param  __last1   End of first range.
05307    *  @param  __first2  Start of second range.
05308    *  @param  __last2   End of second range.
05309    *  @return  End of the output range.
05310    *  @ingroup set_algorithms
05311    *
05312    *  This operation iterates over both ranges, copying elements present in
05313    *  one range but not the other in order to the output range.  Iterators
05314    *  increment for each range.  When the current element of one range is less
05315    *  than the other, that element is copied and the iterator advances.  If an
05316    *  element is contained in both ranges, no elements are copied and both
05317    *  ranges advance.  The output range may not overlap either input range.
05318   */
05319   template<typename _InputIterator1, typename _InputIterator2,
05320        typename _OutputIterator>
05321     inline _OutputIterator
05322     set_symmetric_difference(_InputIterator1 __first1, _InputIterator1 __last1,
05323                  _InputIterator2 __first2, _InputIterator2 __last2,
05324                  _OutputIterator __result)
05325     {
05326       // concept requirements
05327       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
05328       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
05329       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
05330         typename iterator_traits<_InputIterator1>::value_type>)
05331       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
05332         typename iterator_traits<_InputIterator2>::value_type>)
05333       __glibcxx_function_requires(_LessThanOpConcept<
05334         typename iterator_traits<_InputIterator1>::value_type,
05335         typename iterator_traits<_InputIterator2>::value_type>)
05336       __glibcxx_function_requires(_LessThanOpConcept<
05337         typename iterator_traits<_InputIterator2>::value_type,
05338         typename iterator_traits<_InputIterator1>::value_type>) 
05339       __glibcxx_requires_sorted_set(__first1, __last1, __first2);
05340       __glibcxx_requires_sorted_set(__first2, __last2, __first1);
05341 
05342       return _GLIBCXX_STD_A::__set_symmetric_difference(__first1, __last1,
05343                     __first2, __last2, __result,
05344                     __gnu_cxx::__ops::__iter_less_iter());
05345     }
05346 
05347   /**
05348    *  @brief  Return the symmetric difference of two sorted ranges using
05349    *  comparison functor.
05350    *  @ingroup set_algorithms
05351    *  @param  __first1  Start of first range.
05352    *  @param  __last1   End of first range.
05353    *  @param  __first2  Start of second range.
05354    *  @param  __last2   End of second range.
05355    *  @param  __comp    The comparison functor.
05356    *  @return  End of the output range.
05357    *  @ingroup set_algorithms
05358    *
05359    *  This operation iterates over both ranges, copying elements present in
05360    *  one range but not the other in order to the output range.  Iterators
05361    *  increment for each range.  When the current element of one range is less
05362    *  than the other according to @p comp, that element is copied and the
05363    *  iterator advances.  If an element is contained in both ranges according
05364    *  to @p __comp, no elements are copied and both ranges advance.  The output
05365    *  range may not overlap either input range.
05366   */
05367   template<typename _InputIterator1, typename _InputIterator2,
05368        typename _OutputIterator, typename _Compare>
05369     inline _OutputIterator
05370     set_symmetric_difference(_InputIterator1 __first1, _InputIterator1 __last1,
05371                  _InputIterator2 __first2, _InputIterator2 __last2,
05372                  _OutputIterator __result,
05373                  _Compare __comp)
05374     {
05375       // concept requirements
05376       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
05377       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
05378       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
05379         typename iterator_traits<_InputIterator1>::value_type>)
05380       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
05381         typename iterator_traits<_InputIterator2>::value_type>)
05382       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
05383         typename iterator_traits<_InputIterator1>::value_type,
05384         typename iterator_traits<_InputIterator2>::value_type>)
05385       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
05386         typename iterator_traits<_InputIterator2>::value_type,
05387         typename iterator_traits<_InputIterator1>::value_type>)
05388       __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp);
05389       __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp);
05390 
05391       return _GLIBCXX_STD_A::__set_symmetric_difference(__first1, __last1,
05392                 __first2, __last2, __result,
05393                 __gnu_cxx::__ops::__iter_comp_iter(__comp));
05394     }
05395 
05396   template<typename _ForwardIterator, typename _Compare>
05397     _ForwardIterator
05398     __min_element(_ForwardIterator __first, _ForwardIterator __last,
05399           _Compare __comp)
05400     {
05401       if (__first == __last)
05402     return __first;
05403       _ForwardIterator __result = __first;
05404       while (++__first != __last)
05405     if (__comp(__first, __result))
05406       __result = __first;
05407       return __result;
05408     }
05409 
05410   /**
05411    *  @brief  Return the minimum element in a range.
05412    *  @ingroup sorting_algorithms
05413    *  @param  __first  Start of range.
05414    *  @param  __last   End of range.
05415    *  @return  Iterator referencing the first instance of the smallest value.
05416   */
05417   template<typename _ForwardIterator>
05418     _ForwardIterator
05419     inline min_element(_ForwardIterator __first, _ForwardIterator __last)
05420     {
05421       // concept requirements
05422       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
05423       __glibcxx_function_requires(_LessThanComparableConcept<
05424         typename iterator_traits<_ForwardIterator>::value_type>)
05425       __glibcxx_requires_valid_range(__first, __last);
05426 
05427       return _GLIBCXX_STD_A::__min_element(__first, __last,
05428                 __gnu_cxx::__ops::__iter_less_iter());
05429     }
05430 
05431   /**
05432    *  @brief  Return the minimum element in a range using comparison functor.
05433    *  @ingroup sorting_algorithms
05434    *  @param  __first  Start of range.
05435    *  @param  __last   End of range.
05436    *  @param  __comp   Comparison functor.
05437    *  @return  Iterator referencing the first instance of the smallest value
05438    *  according to __comp.
05439   */
05440   template<typename _ForwardIterator, typename _Compare>
05441     inline _ForwardIterator
05442     min_element(_ForwardIterator __first, _ForwardIterator __last,
05443         _Compare __comp)
05444     {
05445       // concept requirements
05446       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
05447       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
05448         typename iterator_traits<_ForwardIterator>::value_type,
05449         typename iterator_traits<_ForwardIterator>::value_type>)
05450       __glibcxx_requires_valid_range(__first, __last);
05451 
05452       return _GLIBCXX_STD_A::__min_element(__first, __last,
05453                 __gnu_cxx::__ops::__iter_comp_iter(__comp));
05454     }
05455 
05456   template<typename _ForwardIterator, typename _Compare>
05457     _ForwardIterator
05458     __max_element(_ForwardIterator __first, _ForwardIterator __last,
05459           _Compare __comp)
05460     {
05461       if (__first == __last) return __first;
05462       _ForwardIterator __result = __first;
05463       while (++__first != __last)
05464     if (__comp(__result, __first))
05465       __result = __first;
05466       return __result;
05467     }
05468 
05469   /**
05470    *  @brief  Return the maximum element in a range.
05471    *  @ingroup sorting_algorithms
05472    *  @param  __first  Start of range.
05473    *  @param  __last   End of range.
05474    *  @return  Iterator referencing the first instance of the largest value.
05475   */
05476   template<typename _ForwardIterator>
05477     inline _ForwardIterator
05478     max_element(_ForwardIterator __first, _ForwardIterator __last)
05479     {
05480       // concept requirements
05481       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
05482       __glibcxx_function_requires(_LessThanComparableConcept<
05483         typename iterator_traits<_ForwardIterator>::value_type>)
05484       __glibcxx_requires_valid_range(__first, __last);
05485 
05486       return _GLIBCXX_STD_A::__max_element(__first, __last,
05487                 __gnu_cxx::__ops::__iter_less_iter());
05488     }
05489 
05490   /**
05491    *  @brief  Return the maximum element in a range using comparison functor.
05492    *  @ingroup sorting_algorithms
05493    *  @param  __first  Start of range.
05494    *  @param  __last   End of range.
05495    *  @param  __comp   Comparison functor.
05496    *  @return  Iterator referencing the first instance of the largest value
05497    *  according to __comp.
05498   */
05499   template<typename _ForwardIterator, typename _Compare>
05500     inline _ForwardIterator
05501     max_element(_ForwardIterator __first, _ForwardIterator __last,
05502         _Compare __comp)
05503     {
05504       // concept requirements
05505       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
05506       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
05507         typename iterator_traits<_ForwardIterator>::value_type,
05508         typename iterator_traits<_ForwardIterator>::value_type>)
05509       __glibcxx_requires_valid_range(__first, __last);
05510 
05511       return _GLIBCXX_STD_A::__max_element(__first, __last,
05512                 __gnu_cxx::__ops::__iter_comp_iter(__comp));
05513     }
05514 
05515 _GLIBCXX_END_NAMESPACE_ALGO
05516 } // namespace std
05517 
05518 #endif /* _STL_ALGO_H */