stl_algo.h

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

Generated on Sat Oct 1 15:08:54 2005 for libstdc++ source by  doxygen 1.4.4