stl_algo.h

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

Generated on Thu Feb 10 23:22:58 2005 for libstdc++-v3 Source by  doxygen 1.4.0