# stl_algo.h

Go to the documentation of this file.

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