stl_algo.h

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

Generated on Thu Jul 23 21:16:19 2009 for libstdc++ by  doxygen 1.5.8