stl_algo.h

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

Generated on Thu Nov 1 13:12:31 2007 for libstdc++ by  doxygen 1.5.1