# stl_algo.h

Go to the documentation of this file.

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