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

Generated on Tue Dec 2 03:59:28 2008 for libstdc++ by  doxygen 1.5.7.1