home *** CD-ROM | disk | FTP | other *** search
/ H4CK3R 14 / hacker14.iso / programacao / cwin / c.exe / $INSTDIR / include / c++ / bits / stl_algo.h < prev    next >
Encoding:
C/C++ Source or Header  |  2003-12-15  |  142.8 KB  |  4,352 lines
  1. // Algorithm implementation -*- C++ -*-
  2.  
  3. // Copyright (C) 2001, 2002 Free Software Foundation, Inc.
  4. //
  5. // This file is part of the GNU ISO C++ Library.  This library is free
  6. // software; you can redistribute it and/or modify it under the
  7. // terms of the GNU General Public License as published by the
  8. // Free Software Foundation; either version 2, or (at your option)
  9. // any later version.
  10.  
  11. // This library is distributed in the hope that it will be useful,
  12. // but WITHOUT ANY WARRANTY; without even the implied warranty of
  13. // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14. // GNU General Public License for more details.
  15.  
  16. // You should have received a copy of the GNU General Public License along
  17. // with this library; see the file COPYING.  If not, write to the Free
  18. // Software Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307,
  19. // USA.
  20.  
  21. // As a special exception, you may use this file as part of a free software
  22. // library without restriction.  Specifically, if other files instantiate
  23. // templates or use macros or inline functions from this file, or you compile
  24. // this file and link it with other files to produce an executable, this
  25. // file does not by itself cause the resulting executable to be covered by
  26. // the GNU General Public License.  This exception does not however
  27. // invalidate any other reasons why the executable file might be covered by
  28. // the GNU General Public License.
  29.  
  30. /*
  31.  *
  32.  * Copyright (c) 1994
  33.  * Hewlett-Packard Company
  34.  *
  35.  * Permission to use, copy, modify, distribute and sell this software
  36.  * and its documentation for any purpose is hereby granted without fee,
  37.  * provided that the above copyright notice appear in all copies and
  38.  * that both that copyright notice and this permission notice appear
  39.  * in supporting documentation.  Hewlett-Packard Company makes no
  40.  * representations about the suitability of this software for any
  41.  * purpose.  It is provided "as is" without express or implied warranty.
  42.  *
  43.  *
  44.  * Copyright (c) 1996
  45.  * Silicon Graphics Computer Systems, Inc.
  46.  *
  47.  * Permission to use, copy, modify, distribute and sell this software
  48.  * and its documentation for any purpose is hereby granted without fee,
  49.  * provided that the above copyright notice appear in all copies and
  50.  * that both that copyright notice and this permission notice appear
  51.  * in supporting documentation.  Silicon Graphics makes no
  52.  * representations about the suitability of this software for any
  53.  * purpose.  It is provided "as is" without express or implied warranty.
  54.  */
  55.  
  56. /** @file stl_algo.h
  57.  *  This is an internal header file, included by other library headers.
  58.  *  You should not attempt to use it directly.
  59.  */
  60.  
  61. #ifndef __GLIBCPP_INTERNAL_ALGO_H
  62. #define __GLIBCPP_INTERNAL_ALGO_H
  63.  
  64. #include <bits/stl_heap.h>
  65. #include <bits/stl_tempbuf.h>     // for _Temporary_buffer
  66.  
  67. // See concept_check.h for the __glibcpp_*_requires macros.
  68.  
  69. namespace std
  70. {
  71.  
  72.   /**
  73.    *  @brief Find the median of three values.
  74.    *  @param  a  A value.
  75.    *  @param  b  A value.
  76.    *  @param  c  A value.
  77.    *  @return One of @p a, @p b or @p c.
  78.    *
  79.    *  If @c {l,m,n} is some convolution of @p {a,b,c} such that @c l<=m<=n
  80.    *  then the value returned will be @c m.
  81.    *  This is an SGI extension.
  82.    *  @ingroup SGIextensions
  83.   */
  84.   template<typename _Tp>
  85.   inline const _Tp&
  86.     __median(const _Tp& __a, const _Tp& __b, const _Tp& __c)
  87.     {
  88.       // concept requirements
  89.       __glibcpp_function_requires(_LessThanComparableConcept<_Tp>)
  90.       if (__a < __b)
  91.     if (__b < __c)
  92.       return __b;
  93.     else if (__a < __c)
  94.       return __c;
  95.     else
  96.       return __a;
  97.       else if (__a < __c)
  98.     return __a;
  99.       else if (__b < __c)
  100.     return __c;
  101.       else
  102.     return __b;
  103.     }
  104.  
  105.   /**
  106.    *  @brief Find the median of three values using a predicate for comparison.
  107.    *  @param  a     A value.
  108.    *  @param  b     A value.
  109.    *  @param  c     A value.
  110.    *  @param  comp  A binary predicate.
  111.    *  @return One of @p a, @p b or @p c.
  112.    *
  113.    *  If @c {l,m,n} is some convolution of @p {a,b,c} such that @p comp(l,m)
  114.    *  and @p comp(m,n) are both true then the value returned will be @c m.
  115.    *  This is an SGI extension.
  116.    *  @ingroup SGIextensions
  117.   */
  118.   template<typename _Tp, typename _Compare>
  119.     inline const _Tp&
  120.     __median(const _Tp& __a, const _Tp& __b, const _Tp& __c, _Compare __comp)
  121.     {
  122.       // concept requirements
  123.       __glibcpp_function_requires(_BinaryFunctionConcept<_Compare,bool,_Tp,_Tp>)
  124.       if (__comp(__a, __b))
  125.     if (__comp(__b, __c))
  126.       return __b;
  127.     else if (__comp(__a, __c))
  128.       return __c;
  129.     else
  130.       return __a;
  131.       else if (__comp(__a, __c))
  132.     return __a;
  133.       else if (__comp(__b, __c))
  134.     return __c;
  135.       else
  136.     return __b;
  137.     }
  138.  
  139.   /**
  140.    *  @brief Apply a function to every element of a sequence.
  141.    *  @param  first  An input iterator.
  142.    *  @param  last   An input iterator.
  143.    *  @param  f      A unary function object.
  144.    *  @return   @p f.
  145.    *
  146.    *  Applies the function object @p f to each element in the range
  147.    *  @p [first,last).  @p f must not modify the order of the sequence.
  148.    *  If @p f has a return value it is ignored.
  149.   */
  150.   template<typename _InputIter, typename _Function>
  151.     _Function
  152.     for_each(_InputIter __first, _InputIter __last, _Function __f)
  153.     {
  154.       // concept requirements
  155.       __glibcpp_function_requires(_InputIteratorConcept<_InputIter>)
  156.       for ( ; __first != __last; ++__first)
  157.     __f(*__first);
  158.       return __f;
  159.     }
  160.  
  161.   /**
  162.    *  @if maint
  163.    *  This is an overload used by find() for the Input Iterator case.
  164.    *  @endif
  165.   */
  166.   template<typename _InputIter, typename _Tp>
  167.     inline _InputIter
  168.     find(_InputIter __first, _InputIter __last,
  169.      const _Tp& __val,
  170.      input_iterator_tag)
  171.     {
  172.       while (__first != __last && !(*__first == __val))
  173.     ++__first;
  174.       return __first;
  175.     }
  176.  
  177.   /**
  178.    *  @if maint
  179.    *  This is an overload used by find_if() for the Input Iterator case.
  180.    *  @endif
  181.   */
  182.   template<typename _InputIter, typename _Predicate>
  183.     inline _InputIter
  184.     find_if(_InputIter __first, _InputIter __last,
  185.         _Predicate __pred,
  186.         input_iterator_tag)
  187.     {
  188.       while (__first != __last && !__pred(*__first))
  189.     ++__first;
  190.       return __first;
  191.     }
  192.  
  193.   /**
  194.    *  @if maint
  195.    *  This is an overload used by find() for the RAI case.
  196.    *  @endif
  197.   */
  198.   template<typename _RandomAccessIter, typename _Tp>
  199.     _RandomAccessIter
  200.     find(_RandomAccessIter __first, _RandomAccessIter __last,
  201.      const _Tp& __val,
  202.      random_access_iterator_tag)
  203.     {
  204.       typename iterator_traits<_RandomAccessIter>::difference_type __trip_count
  205.     = (__last - __first) >> 2;
  206.  
  207.       for ( ; __trip_count > 0 ; --__trip_count) {
  208.     if (*__first == __val) return __first;
  209.     ++__first;
  210.  
  211.     if (*__first == __val) return __first;
  212.     ++__first;
  213.  
  214.     if (*__first == __val) return __first;
  215.     ++__first;
  216.  
  217.     if (*__first == __val) return __first;
  218.     ++__first;
  219.       }
  220.  
  221.       switch(__last - __first) {
  222.       case 3:
  223.     if (*__first == __val) return __first;
  224.     ++__first;
  225.       case 2:
  226.     if (*__first == __val) return __first;
  227.     ++__first;
  228.       case 1:
  229.     if (*__first == __val) return __first;
  230.     ++__first;
  231.       case 0:
  232.       default:
  233.     return __last;
  234.       }
  235.     }
  236.  
  237.   /**
  238.    *  @if maint
  239.    *  This is an overload used by find_if() for the RAI case.
  240.    *  @endif
  241.   */
  242.   template<typename _RandomAccessIter, typename _Predicate>
  243.     _RandomAccessIter
  244.     find_if(_RandomAccessIter __first, _RandomAccessIter __last,
  245.         _Predicate __pred,
  246.         random_access_iterator_tag)
  247.     {
  248.       typename iterator_traits<_RandomAccessIter>::difference_type __trip_count
  249.     = (__last - __first) >> 2;
  250.  
  251.       for ( ; __trip_count > 0 ; --__trip_count) {
  252.     if (__pred(*__first)) return __first;
  253.     ++__first;
  254.  
  255.     if (__pred(*__first)) return __first;
  256.     ++__first;
  257.  
  258.     if (__pred(*__first)) return __first;
  259.     ++__first;
  260.  
  261.     if (__pred(*__first)) return __first;
  262.     ++__first;
  263.       }
  264.  
  265.       switch(__last - __first) {
  266.       case 3:
  267.     if (__pred(*__first)) return __first;
  268.     ++__first;
  269.       case 2:
  270.     if (__pred(*__first)) return __first;
  271.     ++__first;
  272.       case 1:
  273.     if (__pred(*__first)) return __first;
  274.     ++__first;
  275.       case 0:
  276.       default:
  277.     return __last;
  278.       }
  279.     }
  280.  
  281.   /**
  282.    *  @brief Find the first occurrence of a value in a sequence.
  283.    *  @param  first  An input iterator.
  284.    *  @param  last   An input iterator.
  285.    *  @param  val    The value to find.
  286.    *  @return   The first iterator @c i in the range @p [first,last)
  287.    *  such that @c *i == @p val, or @p last if no such iterator exists.
  288.   */
  289.   template<typename _InputIter, typename _Tp>
  290.     inline _InputIter
  291.     find(_InputIter __first, _InputIter __last,
  292.      const _Tp& __val)
  293.     {
  294.       // concept requirements
  295.       __glibcpp_function_requires(_InputIteratorConcept<_InputIter>)
  296.       __glibcpp_function_requires(_EqualOpConcept<
  297.         typename iterator_traits<_InputIter>::value_type, _Tp>)
  298.       return find(__first, __last, __val, __iterator_category(__first));
  299.     }
  300.  
  301.   /**
  302.    *  @brief Find the first element in a sequence for which a predicate is true.
  303.    *  @param  first  An input iterator.
  304.    *  @param  last   An input iterator.
  305.    *  @param  pred   A predicate.
  306.    *  @return   The first iterator @c i in the range @p [first,last)
  307.    *  such that @p pred(*i) is true, or @p last if no such iterator exists.
  308.   */
  309.   template<typename _InputIter, typename _Predicate>
  310.     inline _InputIter
  311.     find_if(_InputIter __first, _InputIter __last,
  312.         _Predicate __pred)
  313.     {
  314.       // concept requirements
  315.       __glibcpp_function_requires(_InputIteratorConcept<_InputIter>)
  316.       __glibcpp_function_requires(_UnaryPredicateConcept<_Predicate,
  317.           typename iterator_traits<_InputIter>::value_type>)
  318.       return find_if(__first, __last, __pred, __iterator_category(__first));
  319.     }
  320.  
  321.   /**
  322.    *  @brief Find two adjacent values in a sequence that are equal.
  323.    *  @param  first  A forward iterator.
  324.    *  @param  last   A forward iterator.
  325.    *  @return   The first iterator @c i such that @c i and @c i+1 are both
  326.    *  valid iterators in @p [first,last) and such that @c *i == @c *(i+1),
  327.    *  or @p last if no such iterator exists.
  328.   */
  329.   template<typename _ForwardIter>
  330.     _ForwardIter
  331.     adjacent_find(_ForwardIter __first, _ForwardIter __last)
  332.     {
  333.       // concept requirements
  334.       __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter>)
  335.       __glibcpp_function_requires(_EqualityComparableConcept<
  336.         typename iterator_traits<_ForwardIter>::value_type>)
  337.       if (__first == __last)
  338.     return __last;
  339.       _ForwardIter __next = __first;
  340.       while(++__next != __last) {
  341.     if (*__first == *__next)
  342.       return __first;
  343.     __first = __next;
  344.       }
  345.       return __last;
  346.     }
  347.  
  348.   /**
  349.    *  @brief Find two adjacent values in a sequence using a predicate.
  350.    *  @param  first         A forward iterator.
  351.    *  @param  last          A forward iterator.
  352.    *  @param  binary_pred   A binary predicate.
  353.    *  @return   The first iterator @c i such that @c i and @c i+1 are both
  354.    *  valid iterators in @p [first,last) and such that
  355.    *  @p binary_pred(*i,*(i+1)) is true, or @p last if no such iterator
  356.    *  exists.
  357.   */
  358.   template<typename _ForwardIter, typename _BinaryPredicate>
  359.     _ForwardIter
  360.     adjacent_find(_ForwardIter __first, _ForwardIter __last,
  361.           _BinaryPredicate __binary_pred)
  362.     {
  363.       // concept requirements
  364.       __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter>)
  365.       __glibcpp_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
  366.         typename iterator_traits<_ForwardIter>::value_type,
  367.         typename iterator_traits<_ForwardIter>::value_type>)
  368.       if (__first == __last)
  369.     return __last;
  370.       _ForwardIter __next = __first;
  371.       while(++__next != __last) {
  372.     if (__binary_pred(*__first, *__next))
  373.       return __first;
  374.     __first = __next;
  375.       }
  376.       return __last;
  377.     }
  378.  
  379.   /**
  380.    *  @brief Count the number of copies of a value in a sequence.
  381.    *  @param  first  An input iterator.
  382.    *  @param  last   An input iterator.
  383.    *  @param  value  The value to be counted.
  384.    *  @return   The number of iterators @c i in the range @p [first,last)
  385.    *  for which @c *i == @p value
  386.   */
  387.   template<typename _InputIter, typename _Tp>
  388.     typename iterator_traits<_InputIter>::difference_type
  389.     count(_InputIter __first, _InputIter __last, const _Tp& __value)
  390.     {
  391.       // concept requirements
  392.       __glibcpp_function_requires(_InputIteratorConcept<_InputIter>)
  393.       __glibcpp_function_requires(_EqualityComparableConcept<
  394.         typename iterator_traits<_InputIter>::value_type >)
  395.       __glibcpp_function_requires(_EqualityComparableConcept<_Tp>)
  396.       typename iterator_traits<_InputIter>::difference_type __n = 0;
  397.       for ( ; __first != __last; ++__first)
  398.     if (*__first == __value)
  399.       ++__n;
  400.       return __n;
  401.     }
  402.  
  403.   /**
  404.    *  @brief Count the elements of a sequence for which a predicate is true.
  405.    *  @param  first  An input iterator.
  406.    *  @param  last   An input iterator.
  407.    *  @param  pred   A predicate.
  408.    *  @return   The number of iterators @c i in the range @p [first,last)
  409.    *  for which @p pred(*i) is true.
  410.   */
  411.   template<typename _InputIter, typename _Predicate>
  412.     typename iterator_traits<_InputIter>::difference_type
  413.     count_if(_InputIter __first, _InputIter __last, _Predicate __pred)
  414.     {
  415.       // concept requirements
  416.       __glibcpp_function_requires(_InputIteratorConcept<_InputIter>)
  417.       __glibcpp_function_requires(_UnaryPredicateConcept<_Predicate,
  418.         typename iterator_traits<_InputIter>::value_type>)
  419.       typename iterator_traits<_InputIter>::difference_type __n = 0;
  420.       for ( ; __first != __last; ++__first)
  421.     if (__pred(*__first))
  422.       ++__n;
  423.       return __n;
  424.     }
  425.  
  426.  
  427.   /**
  428.    *  @brief Search a sequence for a matching sub-sequence.
  429.    *  @param  first1  A forward iterator.
  430.    *  @param  last1   A forward iterator.
  431.    *  @param  first2  A forward iterator.
  432.    *  @param  last2   A forward iterator.
  433.    *  @return   The first iterator @c i in the range
  434.    *  @p [first1,last1-(last2-first2)) such that @c *(i+N) == @p *(first2+N)
  435.    *  for each @c N in the range @p [0,last2-first2), or @p last1 if no
  436.    *  such iterator exists.
  437.    *
  438.    *  Searches the range @p [first1,last1) for a sub-sequence that compares
  439.    *  equal value-by-value with the sequence given by @p [first2,last2) and
  440.    *  returns an iterator to the first element of the sub-sequence, or
  441.    *  @p last1 if the sub-sequence is not found.
  442.    *
  443.    *  Because the sub-sequence must lie completely within the range
  444.    *  @p [first1,last1) it must start at a position less than
  445.    *  @p last1-(last2-first2) where @p last2-first2 is the length of the
  446.    *  sub-sequence.
  447.    *  This means that the returned iterator @c i will be in the range
  448.    *  @p [first1,last1-(last2-first2))
  449.   */
  450.   template<typename _ForwardIter1, typename _ForwardIter2>
  451.     _ForwardIter1
  452.     search(_ForwardIter1 __first1, _ForwardIter1 __last1,
  453.        _ForwardIter2 __first2, _ForwardIter2 __last2)
  454.     {
  455.       // concept requirements
  456.       __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter1>)
  457.       __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter2>)
  458.       __glibcpp_function_requires(_EqualOpConcept<
  459.         typename iterator_traits<_ForwardIter1>::value_type,
  460.         typename iterator_traits<_ForwardIter2>::value_type>)
  461.  
  462.       // Test for empty ranges
  463.       if (__first1 == __last1 || __first2 == __last2)
  464.     return __first1;
  465.  
  466.       // Test for a pattern of length 1.
  467.       _ForwardIter2 __tmp(__first2);
  468.       ++__tmp;
  469.       if (__tmp == __last2)
  470.     return find(__first1, __last1, *__first2);
  471.  
  472.       // General case.
  473.  
  474.       _ForwardIter2 __p1, __p;
  475.  
  476.       __p1 = __first2; ++__p1;
  477.  
  478.       _ForwardIter1 __current = __first1;
  479.  
  480.       while (__first1 != __last1) {
  481.     __first1 = find(__first1, __last1, *__first2);
  482.     if (__first1 == __last1)
  483.       return __last1;
  484.  
  485.     __p = __p1;
  486.     __current = __first1;
  487.     if (++__current == __last1)
  488.       return __last1;
  489.  
  490.     while (*__current == *__p) {
  491.       if (++__p == __last2)
  492.         return __first1;
  493.       if (++__current == __last1)
  494.         return __last1;
  495.     }
  496.  
  497.     ++__first1;
  498.       }
  499.       return __first1;
  500.     }
  501.  
  502.   /**
  503.    *  @brief Search a sequence for a matching sub-sequence using a predicate.
  504.    *  @param  first1     A forward iterator.
  505.    *  @param  last1      A forward iterator.
  506.    *  @param  first2     A forward iterator.
  507.    *  @param  last2      A forward iterator.
  508.    *  @param  predicate  A binary predicate.
  509.    *  @return   The first iterator @c i in the range
  510.    *  @p [first1,last1-(last2-first2)) such that
  511.    *  @p predicate(*(i+N),*(first2+N)) is true for each @c N in the range
  512.    *  @p [0,last2-first2), or @p last1 if no such iterator exists.
  513.    *
  514.    *  Searches the range @p [first1,last1) for a sub-sequence that compares
  515.    *  equal value-by-value with the sequence given by @p [first2,last2),
  516.    *  using @p predicate to determine equality, and returns an iterator
  517.    *  to the first element of the sub-sequence, or @p last1 if no such
  518.    *  iterator exists.
  519.    *
  520.    *  @see search(_ForwardIter1, _ForwardIter1, _ForwardIter2, _ForwardIter2)
  521.   */
  522.   template<typename _ForwardIter1, typename _ForwardIter2, typename _BinaryPred>
  523.     _ForwardIter1
  524.     search(_ForwardIter1 __first1, _ForwardIter1 __last1,
  525.        _ForwardIter2 __first2, _ForwardIter2 __last2,
  526.        _BinaryPred  __predicate)
  527.     {
  528.       // concept requirements
  529.       __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter1>)
  530.       __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter2>)
  531.       __glibcpp_function_requires(_BinaryPredicateConcept<_BinaryPred,
  532.         typename iterator_traits<_ForwardIter1>::value_type,
  533.         typename iterator_traits<_ForwardIter2>::value_type>)
  534.  
  535.       // Test for empty ranges
  536.       if (__first1 == __last1 || __first2 == __last2)
  537.     return __first1;
  538.  
  539.       // Test for a pattern of length 1.
  540.       _ForwardIter2 __tmp(__first2);
  541.       ++__tmp;
  542.       if (__tmp == __last2) {
  543.     while (__first1 != __last1 && !__predicate(*__first1, *__first2))
  544.       ++__first1;
  545.     return __first1;
  546.       }
  547.  
  548.       // General case.
  549.  
  550.       _ForwardIter2 __p1, __p;
  551.  
  552.       __p1 = __first2; ++__p1;
  553.  
  554.       _ForwardIter1 __current = __first1;
  555.  
  556.       while (__first1 != __last1) {
  557.     while (__first1 != __last1) {
  558.       if (__predicate(*__first1, *__first2))
  559.         break;
  560.       ++__first1;
  561.     }
  562.     while (__first1 != __last1 && !__predicate(*__first1, *__first2))
  563.       ++__first1;
  564.     if (__first1 == __last1)
  565.       return __last1;
  566.  
  567.     __p = __p1;
  568.     __current = __first1;
  569.     if (++__current == __last1) return __last1;
  570.  
  571.     while (__predicate(*__current, *__p)) {
  572.       if (++__p == __last2)
  573.         return __first1;
  574.       if (++__current == __last1)
  575.         return __last1;
  576.     }
  577.  
  578.     ++__first1;
  579.       }
  580.       return __first1;
  581.     }
  582.  
  583.   /**
  584.    *  @brief Search a sequence for a number of consecutive values.
  585.    *  @param  first  A forward iterator.
  586.    *  @param  last   A forward iterator.
  587.    *  @param  count  The number of consecutive values.
  588.    *  @param  val    The value to find.
  589.    *  @return   The first iterator @c i in the range @p [first,last-count)
  590.    *  such that @c *(i+N) == @p val for each @c N in the range @p [0,count),
  591.    *  or @p last if no such iterator exists.
  592.    *
  593.    *  Searches the range @p [first,last) for @p count consecutive elements
  594.    *  equal to @p val.
  595.   */
  596.   template<typename _ForwardIter, typename _Integer, typename _Tp>
  597.     _ForwardIter
  598.     search_n(_ForwardIter __first, _ForwardIter __last,
  599.          _Integer __count, const _Tp& __val)
  600.     {
  601.       // concept requirements
  602.       __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter>)
  603.       __glibcpp_function_requires(_EqualityComparableConcept<
  604.         typename iterator_traits<_ForwardIter>::value_type>)
  605.       __glibcpp_function_requires(_EqualityComparableConcept<_Tp>)
  606.  
  607.       if (__count <= 0)
  608.     return __first;
  609.       else {
  610.     __first = find(__first, __last, __val);
  611.     while (__first != __last) {
  612.       _Integer __n = __count - 1;
  613.       _ForwardIter __i = __first;
  614.       ++__i;
  615.       while (__i != __last && __n != 0 && *__i == __val) {
  616.         ++__i;
  617.         --__n;
  618.       }
  619.       if (__n == 0)
  620.         return __first;
  621.       else
  622.         __first = find(__i, __last, __val);
  623.     }
  624.     return __last;
  625.       }
  626.     }
  627.  
  628.   /**
  629.    *  @brief Search a sequence for a number of consecutive values using a
  630.    *         predicate.
  631.    *  @param  first        A forward iterator.
  632.    *  @param  last         A forward iterator.
  633.    *  @param  count        The number of consecutive values.
  634.    *  @param  val          The value to find.
  635.    *  @param  binary_pred  A binary predicate.
  636.    *  @return   The first iterator @c i in the range @p [first,last-count)
  637.    *  such that @p binary_pred(*(i+N),val) is true for each @c N in the
  638.    *  range @p [0,count), or @p last if no such iterator exists.
  639.    *
  640.    *  Searches the range @p [first,last) for @p count consecutive elements
  641.    *  for which the predicate returns true.
  642.   */
  643.   template<typename _ForwardIter, typename _Integer, typename _Tp,
  644.            typename _BinaryPred>
  645.     _ForwardIter
  646.     search_n(_ForwardIter __first, _ForwardIter __last,
  647.          _Integer __count, const _Tp& __val,
  648.          _BinaryPred __binary_pred)
  649.     {
  650.       // concept requirements
  651.       __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter>)
  652.       __glibcpp_function_requires(_BinaryPredicateConcept<_BinaryPred,
  653.         typename iterator_traits<_ForwardIter>::value_type, _Tp>)
  654.  
  655.       if (__count <= 0)
  656.     return __first;
  657.       else {
  658.     while (__first != __last) {
  659.       if (__binary_pred(*__first, __val))
  660.         break;
  661.       ++__first;
  662.     }
  663.     while (__first != __last) {
  664.       _Integer __n = __count - 1;
  665.       _ForwardIter __i = __first;
  666.       ++__i;
  667.       while (__i != __last && __n != 0 && __binary_pred(*__i, __val)) {
  668.         ++__i;
  669.         --__n;
  670.       }
  671.       if (__n == 0)
  672.         return __first;
  673.       else {
  674.         while (__i != __last) {
  675.           if (__binary_pred(*__i, __val))
  676.         break;
  677.           ++__i;
  678.         }
  679.         __first = __i;
  680.       }
  681.     }
  682.     return __last;
  683.       }
  684.     }
  685.  
  686.   /**
  687.    *  @brief Swap the elements of two sequences.
  688.    *  @param  first1  A forward iterator.
  689.    *  @param  last1   A forward iterator.
  690.    *  @param  first2  A forward iterator.
  691.    *  @return   An iterator equal to @p first2+(last1-first1).
  692.    *
  693.    *  Swaps each element in the range @p [first1,last1) with the
  694.    *  corresponding element in the range @p [first2,(last1-first1)).
  695.    *  The ranges must not overlap.
  696.   */
  697.   template<typename _ForwardIter1, typename _ForwardIter2>
  698.     _ForwardIter2
  699.     swap_ranges(_ForwardIter1 __first1, _ForwardIter1 __last1,
  700.         _ForwardIter2 __first2)
  701.     {
  702.       // concept requirements
  703.       __glibcpp_function_requires(_Mutable_ForwardIteratorConcept<_ForwardIter1>)
  704.       __glibcpp_function_requires(_Mutable_ForwardIteratorConcept<_ForwardIter2>)
  705.       __glibcpp_function_requires(_ConvertibleConcept<
  706.         typename iterator_traits<_ForwardIter1>::value_type,
  707.         typename iterator_traits<_ForwardIter2>::value_type>)
  708.       __glibcpp_function_requires(_ConvertibleConcept<
  709.         typename iterator_traits<_ForwardIter2>::value_type,
  710.         typename iterator_traits<_ForwardIter1>::value_type>)
  711.  
  712.       for ( ; __first1 != __last1; ++__first1, ++__first2)
  713.     iter_swap(__first1, __first2);
  714.       return __first2;
  715.     }
  716.  
  717.   /**
  718.    *  @brief Perform an operation on a sequence.
  719.    *  @param  first     An input iterator.
  720.    *  @param  last      An input iterator.
  721.    *  @param  result    An output iterator.
  722.    *  @param  unary_op  A unary operator.
  723.    *  @return   An output iterator equal to @p result+(last-first).
  724.    *
  725.    *  Applies the operator to each element in the input range and assigns
  726.    *  the results to successive elements of the output sequence.
  727.    *  Evaluates @p *(result+N)=unary_op(*(first+N)) for each @c N in the
  728.    *  range @p [0,last-first).
  729.    *
  730.    *  @p unary_op must not alter its argument.
  731.   */
  732.   template<typename _InputIter, typename _OutputIter, typename _UnaryOperation>
  733.     _OutputIter
  734.     transform(_InputIter __first, _InputIter __last,
  735.           _OutputIter __result, _UnaryOperation __unary_op)
  736.     {
  737.       // concept requirements
  738.       __glibcpp_function_requires(_InputIteratorConcept<_InputIter>)
  739.       __glibcpp_function_requires(_OutputIteratorConcept<_OutputIter,
  740.             // "the type returned by a _UnaryOperation"
  741.             __typeof__(__unary_op(*__first))>)
  742.  
  743.       for ( ; __first != __last; ++__first, ++__result)
  744.     *__result = __unary_op(*__first);
  745.       return __result;
  746.     }
  747.  
  748.   /**
  749.    *  @brief Perform an operation on corresponding elements of two sequences.
  750.    *  @param  first1     An input iterator.
  751.    *  @param  last1      An input iterator.
  752.    *  @param  first2     An input iterator.
  753.    *  @param  result     An output iterator.
  754.    *  @param  binary_op  A binary operator.
  755.    *  @return   An output iterator equal to @p result+(last-first).
  756.    *
  757.    *  Applies the operator to the corresponding elements in the two
  758.    *  input ranges and assigns the results to successive elements of the
  759.    *  output sequence.
  760.    *  Evaluates @p *(result+N)=binary_op(*(first1+N),*(first2+N)) for each
  761.    *  @c N in the range @p [0,last1-first1).
  762.    *
  763.    *  @p binary_op must not alter either of its arguments.
  764.   */
  765.   template<typename _InputIter1, typename _InputIter2, typename _OutputIter,
  766.        typename _BinaryOperation>
  767.     _OutputIter
  768.     transform(_InputIter1 __first1, _InputIter1 __last1,
  769.           _InputIter2 __first2, _OutputIter __result,
  770.           _BinaryOperation __binary_op)
  771.     {
  772.       // concept requirements
  773.       __glibcpp_function_requires(_InputIteratorConcept<_InputIter1>)
  774.       __glibcpp_function_requires(_InputIteratorConcept<_InputIter2>)
  775.       __glibcpp_function_requires(_OutputIteratorConcept<_OutputIter,
  776.             // "the type returned by a _BinaryOperation"
  777.             __typeof__(__binary_op(*__first1,*__first2))>)
  778.  
  779.       for ( ; __first1 != __last1; ++__first1, ++__first2, ++__result)
  780.     *__result = __binary_op(*__first1, *__first2);
  781.       return __result;
  782.     }
  783.  
  784.   /**
  785.    *  @brief Replace each occurrence of one value in a sequence with another
  786.    *         value.
  787.    *  @param  first      A forward iterator.
  788.    *  @param  last       A forward iterator.
  789.    *  @param  old_value  The value to be replaced.
  790.    *  @param  new_value  The replacement value.
  791.    *  @return   replace() returns no value.
  792.    *
  793.    *  For each iterator @c i in the range @p [first,last) if @c *i ==
  794.    *  @p old_value then the assignment @c *i = @p new_value is performed.
  795.   */
  796.   template<typename _ForwardIter, typename _Tp>
  797.     void
  798.     replace(_ForwardIter __first, _ForwardIter __last,
  799.         const _Tp& __old_value, const _Tp& __new_value)
  800.     {
  801.       // concept requirements
  802.       __glibcpp_function_requires(_Mutable_ForwardIteratorConcept<_ForwardIter>)
  803.       __glibcpp_function_requires(_EqualOpConcept<
  804.         typename iterator_traits<_ForwardIter>::value_type, _Tp>)
  805.       __glibcpp_function_requires(_ConvertibleConcept<_Tp,
  806.         typename iterator_traits<_ForwardIter>::value_type>)
  807.  
  808.       for ( ; __first != __last; ++__first)
  809.     if (*__first == __old_value)
  810.       *__first = __new_value;
  811.     }
  812.  
  813.   /**
  814.    *  @brief Replace each value in a sequence for which a predicate returns
  815.    *         true with another value.
  816.    *  @param  first      A forward iterator.
  817.    *  @param  last       A forward iterator.
  818.    *  @param  pred       A predicate.
  819.    *  @param  new_value  The replacement value.
  820.    *  @return   replace_if() returns no value.
  821.    *
  822.    *  For each iterator @c i in the range @p [first,last) if @p pred(*i)
  823.    *  is true then the assignment @c *i = @p new_value is performed.
  824.   */
  825.   template<typename _ForwardIter, typename _Predicate, typename _Tp>
  826.     void
  827.     replace_if(_ForwardIter __first, _ForwardIter __last,
  828.            _Predicate __pred, const _Tp& __new_value)
  829.     {
  830.       // concept requirements
  831.       __glibcpp_function_requires(_Mutable_ForwardIteratorConcept<_ForwardIter>)
  832.       __glibcpp_function_requires(_ConvertibleConcept<_Tp,
  833.         typename iterator_traits<_ForwardIter>::value_type>)
  834.       __glibcpp_function_requires(_UnaryPredicateConcept<_Predicate,
  835.         typename iterator_traits<_ForwardIter>::value_type>)
  836.  
  837.       for ( ; __first != __last; ++__first)
  838.     if (__pred(*__first))
  839.       *__first = __new_value;
  840.     }
  841.  
  842.   /**
  843.    *  @brief Copy a sequence, replacing each element of one value with another
  844.    *         value.
  845.    *  @param  first      An input iterator.
  846.    *  @param  last       An input iterator.
  847.    *  @param  result     An output iterator.
  848.    *  @param  old_value  The value to be replaced.
  849.    *  @param  new_value  The replacement value.
  850.    *  @return   The end of the output sequence, @p result+(last-first).
  851.    *
  852.    *  Copies each element in the input range @p [first,last) to the
  853.    *  output range @p [result,result+(last-first)) replacing elements
  854.    *  equal to @p old_value with @p new_value.
  855.   */
  856.   template<typename _InputIter, typename _OutputIter, typename _Tp>
  857.     _OutputIter
  858.     replace_copy(_InputIter __first, _InputIter __last,
  859.          _OutputIter __result,
  860.          const _Tp& __old_value, const _Tp& __new_value)
  861.     {
  862.       // concept requirements
  863.       __glibcpp_function_requires(_InputIteratorConcept<_InputIter>)
  864.       __glibcpp_function_requires(_OutputIteratorConcept<_OutputIter,
  865.         typename iterator_traits<_InputIter>::value_type>)
  866.       __glibcpp_function_requires(_EqualOpConcept<
  867.         typename iterator_traits<_InputIter>::value_type, _Tp>)
  868.  
  869.       for ( ; __first != __last; ++__first, ++__result)
  870.     *__result = *__first == __old_value ? __new_value : *__first;
  871.       return __result;
  872.     }
  873.  
  874.   /**
  875.    *  @brief Copy a sequence, replacing each value for which a predicate
  876.    *         returns true with another value.
  877.    *  @param  first      An input iterator.
  878.    *  @param  last       An input iterator.
  879.    *  @param  result     An output iterator.
  880.    *  @param  pred       A predicate.
  881.    *  @param  new_value  The replacement value.
  882.    *  @return   The end of the output sequence, @p result+(last-first).
  883.    *
  884.    *  Copies each element in the range @p [first,last) to the range
  885.    *  @p [result,result+(last-first)) replacing elements for which
  886.    *  @p pred returns true with @p new_value.
  887.   */
  888.   template<typename _InputIter, typename _OutputIter, typename _Predicate,
  889.            typename _Tp>
  890.     _OutputIter
  891.     replace_copy_if(_InputIter __first, _InputIter __last,
  892.             _OutputIter __result,
  893.             _Predicate __pred, const _Tp& __new_value)
  894.     {
  895.       // concept requirements
  896.       __glibcpp_function_requires(_InputIteratorConcept<_InputIter>)
  897.       __glibcpp_function_requires(_OutputIteratorConcept<_OutputIter,
  898.         typename iterator_traits<_InputIter>::value_type>)
  899.       __glibcpp_function_requires(_UnaryPredicateConcept<_Predicate,
  900.         typename iterator_traits<_InputIter>::value_type>)
  901.  
  902.       for ( ; __first != __last; ++__first, ++__result)
  903.     *__result = __pred(*__first) ? __new_value : *__first;
  904.       return __result;
  905.     }
  906.  
  907.   /**
  908.    *  @brief Assign the result of a function object to each value in a
  909.    *         sequence.
  910.    *  @param  first  A forward iterator.
  911.    *  @param  last   A forward iterator.
  912.    *  @param  gen    A function object taking no arguments.
  913.    *  @return   generate() returns no value.
  914.    *
  915.    *  Performs the assignment @c *i = @p gen() for each @c i in the range
  916.    *  @p [first,last).
  917.   */
  918.   template<typename _ForwardIter, typename _Generator>
  919.     void
  920.     generate(_ForwardIter __first, _ForwardIter __last, _Generator __gen)
  921.     {
  922.       // concept requirements
  923.       __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter>)
  924.       __glibcpp_function_requires(_GeneratorConcept<_Generator,
  925.         typename iterator_traits<_ForwardIter>::value_type>)
  926.  
  927.       for ( ; __first != __last; ++__first)
  928.     *__first = __gen();
  929.     }
  930.  
  931.   /**
  932.    *  @brief Assign the result of a function object to each value in a
  933.    *         sequence.
  934.    *  @param  first  A forward iterator.
  935.    *  @param  n      The length of the sequence.
  936.    *  @param  gen    A function object taking no arguments.
  937.    *  @return   The end of the sequence, @p first+n
  938.    *
  939.    *  Performs the assignment @c *i = @p gen() for each @c i in the range
  940.    *  @p [first,first+n).
  941.   */
  942.   template<typename _OutputIter, typename _Size, typename _Generator>
  943.     _OutputIter
  944.     generate_n(_OutputIter __first, _Size __n, _Generator __gen)
  945.     {
  946.       // concept requirements
  947.       __glibcpp_function_requires(_OutputIteratorConcept<_OutputIter,
  948.             // "the type returned by a _Generator"
  949.             __typeof__(gen())>)
  950.  
  951.       for ( ; __n > 0; --__n, ++__first)
  952.     *__first = __gen();
  953.       return __first;
  954.     }
  955.  
  956.   /**
  957.    *  @brief Copy a sequence, removing elements of a given value.
  958.    *  @param  first   An input iterator.
  959.    *  @param  last    An input iterator.
  960.    *  @param  result  An output iterator.
  961.    *  @param  value   The value to be removed.
  962.    *  @return   An iterator designating the end of the resulting sequence.
  963.    *
  964.    *  Copies each element in the range @p [first,last) not equal to @p value
  965.    *  to the range beginning at @p result.
  966.    *  remove_copy() is stable, so the relative order of elements that are
  967.    *  copied is unchanged.
  968.   */
  969.   template<typename _InputIter, typename _OutputIter, typename _Tp>
  970.     _OutputIter
  971.     remove_copy(_InputIter __first, _InputIter __last,
  972.         _OutputIter __result, const _Tp& __value)
  973.     {
  974.       // concept requirements
  975.       __glibcpp_function_requires(_InputIteratorConcept<_InputIter>)
  976.       __glibcpp_function_requires(_OutputIteratorConcept<_OutputIter,
  977.         typename iterator_traits<_InputIter>::value_type>)
  978.       __glibcpp_function_requires(_EqualOpConcept<
  979.         typename iterator_traits<_InputIter>::value_type, _Tp>)
  980.  
  981.       for ( ; __first != __last; ++__first)
  982.     if (!(*__first == __value)) {
  983.       *__result = *__first;
  984.       ++__result;
  985.     }
  986.       return __result;
  987.     }
  988.  
  989.   /**
  990.    *  @brief Copy a sequence, removing elements for which a predicate is true.
  991.    *  @param  first   An input iterator.
  992.    *  @param  last    An input iterator.
  993.    *  @param  result  An output iterator.
  994.    *  @param  pred    A predicate.
  995.    *  @return   An iterator designating the end of the resulting sequence.
  996.    *
  997.    *  Copies each element in the range @p [first,last) for which
  998.    *  @p pred returns true to the range beginning at @p result.
  999.    *
  1000.    *  remove_copy_if() is stable, so the relative order of elements that are
  1001.    *  copied is unchanged.
  1002.   */
  1003.   template<typename _InputIter, typename _OutputIter, typename _Predicate>
  1004.     _OutputIter
  1005.     remove_copy_if(_InputIter __first, _InputIter __last,
  1006.            _OutputIter __result, _Predicate __pred)
  1007.     {
  1008.       // concept requirements
  1009.       __glibcpp_function_requires(_InputIteratorConcept<_InputIter>)
  1010.       __glibcpp_function_requires(_OutputIteratorConcept<_OutputIter,
  1011.         typename iterator_traits<_InputIter>::value_type>)
  1012.       __glibcpp_function_requires(_UnaryPredicateConcept<_Predicate,
  1013.         typename iterator_traits<_InputIter>::value_type>)
  1014.  
  1015.       for ( ; __first != __last; ++__first)
  1016.     if (!__pred(*__first)) {
  1017.       *__result = *__first;
  1018.       ++__result;
  1019.     }
  1020.       return __result;
  1021.     }
  1022.  
  1023.   /**
  1024.    *  @brief Remove elements from a sequence.
  1025.    *  @param  first  An input iterator.
  1026.    *  @param  last   An input iterator.
  1027.    *  @param  value  The value to be removed.
  1028.    *  @return   An iterator designating the end of the resulting sequence.
  1029.    *
  1030.    *  All elements equal to @p value are removed from the range
  1031.    *  @p [first,last).
  1032.    *
  1033.    *  remove() is stable, so the relative order of elements that are
  1034.    *  not removed is unchanged.
  1035.    *
  1036.    *  Elements between the end of the resulting sequence and @p last
  1037.    *  are still present, but their value is unspecified.
  1038.   */
  1039.   template<typename _ForwardIter, typename _Tp>
  1040.     _ForwardIter
  1041.     remove(_ForwardIter __first, _ForwardIter __last,
  1042.        const _Tp& __value)
  1043.     {
  1044.       // concept requirements
  1045.       __glibcpp_function_requires(_Mutable_ForwardIteratorConcept<_ForwardIter>)
  1046.       __glibcpp_function_requires(_ConvertibleConcept<_Tp,
  1047.         typename iterator_traits<_ForwardIter>::value_type>)
  1048.       __glibcpp_function_requires(_EqualOpConcept<
  1049.         typename iterator_traits<_ForwardIter>::value_type, _Tp>)
  1050.  
  1051.       __first = find(__first, __last, __value);
  1052.       _ForwardIter __i = __first;
  1053.       return __first == __last ? __first
  1054.                    : remove_copy(++__i, __last, __first, __value);
  1055.     }
  1056.  
  1057.   /**
  1058.    *  @brief Remove elements from a sequence using a predicate.
  1059.    *  @param  first  A forward iterator.
  1060.    *  @param  last   A forward iterator.
  1061.    *  @param  pred   A predicate.
  1062.    *  @return   An iterator designating the end of the resulting sequence.
  1063.    *
  1064.    *  All elements for which @p pred returns true are removed from the range
  1065.    *  @p [first,last).
  1066.    *
  1067.    *  remove_if() is stable, so the relative order of elements that are
  1068.    *  not removed is unchanged.
  1069.    *
  1070.    *  Elements between the end of the resulting sequence and @p last
  1071.    *  are still present, but their value is unspecified.
  1072.   */
  1073.   template<typename _ForwardIter, typename _Predicate>
  1074.     _ForwardIter
  1075.     remove_if(_ForwardIter __first, _ForwardIter __last,
  1076.           _Predicate __pred)
  1077.     {
  1078.       // concept requirements
  1079.       __glibcpp_function_requires(_Mutable_ForwardIteratorConcept<_ForwardIter>)
  1080.       __glibcpp_function_requires(_UnaryPredicateConcept<_Predicate,
  1081.         typename iterator_traits<_ForwardIter>::value_type>)
  1082.  
  1083.       __first = find_if(__first, __last, __pred);
  1084.       _ForwardIter __i = __first;
  1085.       return __first == __last ? __first
  1086.                    : remove_copy_if(++__i, __last, __first, __pred);
  1087.     }
  1088.  
  1089.   /**
  1090.    *  @if maint
  1091.    *  This is an uglified unique_copy(_InputIter, _InputIter, _OutputIter)
  1092.    *  overloaded for output iterators.
  1093.    *  @endif
  1094.   */
  1095.   template<typename _InputIter, typename _OutputIter>
  1096.     _OutputIter
  1097.     __unique_copy(_InputIter __first, _InputIter __last,
  1098.           _OutputIter __result,
  1099.           output_iterator_tag)
  1100.     {
  1101.       // concept requirements -- taken care of in dispatching function
  1102.       typename iterator_traits<_InputIter>::value_type __value = *__first;
  1103.       *__result = __value;
  1104.       while (++__first != __last)
  1105.     if (!(__value == *__first)) {
  1106.       __value = *__first;
  1107.       *++__result = __value;
  1108.     }
  1109.       return ++__result;
  1110.     }
  1111.  
  1112.   /**
  1113.    *  @if maint
  1114.    *  This is an uglified unique_copy(_InputIter, _InputIter, _OutputIter)
  1115.    *  overloaded for forward iterators.
  1116.    *  @endif
  1117.   */
  1118.   template<typename _InputIter, typename _ForwardIter>
  1119.     _ForwardIter
  1120.     __unique_copy(_InputIter __first, _InputIter __last,
  1121.           _ForwardIter __result,
  1122.           forward_iterator_tag)
  1123.     {
  1124.       // concept requirements -- taken care of in dispatching function
  1125.       *__result = *__first;
  1126.       while (++__first != __last)
  1127.     if (!(*__result == *__first))
  1128.       *++__result = *__first;
  1129.       return ++__result;
  1130.     }
  1131.  
  1132.   /**
  1133.    *  @brief Copy a sequence, removing consecutive duplicate values.
  1134.    *  @param  first   An input iterator.
  1135.    *  @param  last    An input iterator.
  1136.    *  @param  result  An output iterator.
  1137.    *  @return   An iterator designating the end of the resulting sequence.
  1138.    *
  1139.    *  Copies each element in the range @p [first,last) to the range
  1140.    *  beginning at @p result, except that only the first element is copied
  1141.    *  from groups of consecutive elements that compare equal.
  1142.    *  unique_copy() is stable, so the relative order of elements that are
  1143.    *  copied is unchanged.
  1144.   */
  1145.   template<typename _InputIter, typename _OutputIter>
  1146.     inline _OutputIter
  1147.     unique_copy(_InputIter __first, _InputIter __last,
  1148.         _OutputIter __result)
  1149.     {
  1150.       // concept requirements
  1151.       __glibcpp_function_requires(_InputIteratorConcept<_InputIter>)
  1152.       __glibcpp_function_requires(_OutputIteratorConcept<_OutputIter,
  1153.         typename iterator_traits<_InputIter>::value_type>)
  1154.       __glibcpp_function_requires(_EqualityComparableConcept<
  1155.         typename iterator_traits<_InputIter>::value_type>)
  1156.  
  1157.       typedef typename iterator_traits<_OutputIter>::iterator_category _IterType;
  1158.  
  1159.       if (__first == __last) return __result;
  1160.       return __unique_copy(__first, __last, __result, _IterType());
  1161.     }
  1162.  
  1163.   /**
  1164.    *  @if maint
  1165.    *  This is an uglified
  1166.    *  unique_copy(_InputIter, _InputIter, _OutputIter, _BinaryPredicate)
  1167.    *  overloaded for output iterators.
  1168.    *  @endif
  1169.   */
  1170.   template<typename _InputIter, typename _OutputIter, typename _BinaryPredicate>
  1171.     _OutputIter
  1172.     __unique_copy(_InputIter __first, _InputIter __last,
  1173.           _OutputIter __result,
  1174.           _BinaryPredicate __binary_pred,
  1175.           output_iterator_tag)
  1176.     {
  1177.       // concept requirements -- iterators already checked
  1178.       __glibcpp_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
  1179.       typename iterator_traits<_InputIter>::value_type,
  1180.       typename iterator_traits<_InputIter>::value_type>)
  1181.  
  1182.       typename iterator_traits<_InputIter>::value_type __value = *__first;
  1183.       *__result = __value;
  1184.       while (++__first != __last)
  1185.     if (!__binary_pred(__value, *__first)) {
  1186.       __value = *__first;
  1187.       *++__result = __value;
  1188.     }
  1189.       return ++__result;
  1190.     }
  1191.  
  1192.   /**
  1193.    *  @if maint
  1194.    *  This is an uglified
  1195.    *  unique_copy(_InputIter, _InputIter, _OutputIter, _BinaryPredicate)
  1196.    *  overloaded for forward iterators.
  1197.    *  @endif
  1198.   */
  1199.   template<typename _InputIter, typename _ForwardIter, typename _BinaryPredicate>
  1200.     _ForwardIter
  1201.     __unique_copy(_InputIter __first, _InputIter __last,
  1202.           _ForwardIter __result,
  1203.           _BinaryPredicate __binary_pred,
  1204.           forward_iterator_tag)
  1205.     {
  1206.       // concept requirements -- iterators already checked
  1207.       __glibcpp_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
  1208.         typename iterator_traits<_ForwardIter>::value_type,
  1209.         typename iterator_traits<_InputIter>::value_type>)
  1210.  
  1211.       *__result = *__first;
  1212.       while (++__first != __last)
  1213.     if (!__binary_pred(*__result, *__first)) *++__result = *__first;
  1214.       return ++__result;
  1215.     }
  1216.  
  1217.   /**
  1218.    *  @brief Copy a sequence, removing consecutive values using a predicate.
  1219.    *  @param  first        An input iterator.
  1220.    *  @param  last         An input iterator.
  1221.    *  @param  result       An output iterator.
  1222.    *  @param  binary_pred  A binary predicate.
  1223.    *  @return   An iterator designating the end of the resulting sequence.
  1224.    *
  1225.    *  Copies each element in the range @p [first,last) to the range
  1226.    *  beginning at @p result, except that only the first element is copied
  1227.    *  from groups of consecutive elements for which @p binary_pred returns
  1228.    *  true.
  1229.    *  unique_copy() is stable, so the relative order of elements that are
  1230.    *  copied is unchanged.
  1231.   */
  1232.   template<typename _InputIter, typename _OutputIter, typename _BinaryPredicate>
  1233.     inline _OutputIter
  1234.     unique_copy(_InputIter __first, _InputIter __last,
  1235.         _OutputIter __result,
  1236.         _BinaryPredicate __binary_pred)
  1237.     {
  1238.       // concept requirements -- predicates checked later
  1239.       __glibcpp_function_requires(_InputIteratorConcept<_InputIter>)
  1240.       __glibcpp_function_requires(_OutputIteratorConcept<_OutputIter,
  1241.         typename iterator_traits<_InputIter>::value_type>)
  1242.  
  1243.       typedef typename iterator_traits<_OutputIter>::iterator_category _IterType;
  1244.  
  1245.       if (__first == __last) return __result;
  1246.       return __unique_copy(__first, __last,
  1247. __result, __binary_pred, _IterType());
  1248.     }
  1249.  
  1250.   /**
  1251.    *  @brief Remove consecutive duplicate values from a sequence.
  1252.    *  @param  first  A forward iterator.
  1253.    *  @param  last   A forward iterator.
  1254.    *  @return  An iterator designating the end of the resulting sequence.
  1255.    *
  1256.    *  Removes all but the first element from each group of consecutive
  1257.    *  values that compare equal.
  1258.    *  unique() is stable, so the relative order of elements that are
  1259.    *  not removed is unchanged.
  1260.    *  Elements between the end of the resulting sequence and @p last
  1261.    *  are still present, but their value is unspecified.
  1262.   */
  1263.   template<typename _ForwardIter>
  1264.     _ForwardIter
  1265.     unique(_ForwardIter __first, _ForwardIter __last)
  1266.     {
  1267.       // concept requirements
  1268.       __glibcpp_function_requires(_Mutable_ForwardIteratorConcept<_ForwardIter>)
  1269.       __glibcpp_function_requires(_EqualityComparableConcept<
  1270.             typename iterator_traits<_ForwardIter>::value_type>)
  1271.  
  1272.       __first = adjacent_find(__first, __last);
  1273.       return unique_copy(__first, __last, __first);
  1274.     }
  1275.  
  1276.   /**
  1277.    *  @brief Remove consecutive values from a sequence using a predicate.
  1278.    *  @param  first        A forward iterator.
  1279.    *  @param  last         A forward iterator.
  1280.    *  @param  binary_pred  A binary predicate.
  1281.    *  @return  An iterator designating the end of the resulting sequence.
  1282.    *
  1283.    *  Removes all but the first element from each group of consecutive
  1284.    *  values for which @p binary_pred returns true.
  1285.    *  unique() is stable, so the relative order of elements that are
  1286.    *  not removed is unchanged.
  1287.    *  Elements between the end of the resulting sequence and @p last
  1288.    *  are still present, but their value is unspecified.
  1289.   */
  1290.   template<typename _ForwardIter, typename _BinaryPredicate>
  1291.     _ForwardIter
  1292.     unique(_ForwardIter __first, _ForwardIter __last,
  1293.            _BinaryPredicate __binary_pred)
  1294.     {
  1295.       // concept requirements
  1296.       __glibcpp_function_requires(_Mutable_ForwardIteratorConcept<_ForwardIter>)
  1297.       __glibcpp_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
  1298.         typename iterator_traits<_ForwardIter>::value_type,
  1299.         typename iterator_traits<_ForwardIter>::value_type>)
  1300.  
  1301.       __first = adjacent_find(__first, __last, __binary_pred);
  1302.       return unique_copy(__first, __last, __first, __binary_pred);
  1303.     }
  1304.  
  1305.   /**
  1306.    *  @if maint
  1307.    *  This is an uglified reverse(_BidirectionalIter, _BidirectionalIter)
  1308.    *  overloaded for bidirectional iterators.
  1309.    *  @endif
  1310.   */
  1311.   template<typename _BidirectionalIter>
  1312.     void
  1313.     __reverse(_BidirectionalIter __first, _BidirectionalIter __last,
  1314.               bidirectional_iterator_tag)
  1315.     {
  1316.       while (true)
  1317.         if (__first == __last || __first == --__last)
  1318.           return;
  1319.         else
  1320.           iter_swap(__first++, __last);
  1321.     }
  1322.  
  1323.   /**
  1324.    *  @if maint
  1325.    *  This is an uglified reverse(_BidirectionalIter, _BidirectionalIter)
  1326.    *  overloaded for bidirectional iterators.
  1327.    *  @endif
  1328.   */
  1329.   template<typename _RandomAccessIter>
  1330.     void
  1331.     __reverse(_RandomAccessIter __first, _RandomAccessIter __last,
  1332.               random_access_iterator_tag)
  1333.     {
  1334.       while (__first < __last)
  1335.         iter_swap(__first++, --__last);
  1336.     }
  1337.  
  1338.   /**
  1339.    *  @brief Reverse a sequence.
  1340.    *  @param  first  A bidirectional iterator.
  1341.    *  @param  last   A bidirectional iterator.
  1342.    *  @return   reverse() returns no value.
  1343.    *
  1344.    *  Reverses the order of the elements in the range @p [first,last),
  1345.    *  so that the first element becomes the last etc.
  1346.    *  For every @c i such that @p 0<=i<=(last-first)/2), @p reverse()
  1347.    *  swaps @p *(first+i) and @p *(last-(i+1))
  1348.   */
  1349.   template<typename _BidirectionalIter>
  1350.     inline void
  1351.     reverse(_BidirectionalIter __first, _BidirectionalIter __last)
  1352.     {
  1353.       // concept requirements
  1354.       __glibcpp_function_requires(_Mutable_BidirectionalIteratorConcept<
  1355.             _BidirectionalIter>)
  1356.       __reverse(__first, __last, __iterator_category(__first));
  1357.     }
  1358.  
  1359.   /**
  1360.    *  @brief Copy a sequence, reversing its elements.
  1361.    *  @param  first   A bidirectional iterator.
  1362.    *  @param  last    A bidirectional iterator.
  1363.    *  @param  result  An output iterator.
  1364.    *  @return  An iterator designating the end of the resulting sequence.
  1365.    *
  1366.    *  Copies the elements in the range @p [first,last) to the range
  1367.    *  @p [result,result+(last-first)) such that the order of the
  1368.    *  elements is reversed.
  1369.    *  For every @c i such that @p 0<=i<=(last-first), @p reverse_copy()
  1370.    *  performs the assignment @p *(result+(last-first)-i) = *(first+i).
  1371.    *  The ranges @p [first,last) and @p [result,result+(last-first))
  1372.    *  must not overlap.
  1373.   */
  1374.   template<typename _BidirectionalIter, typename _OutputIter>
  1375.     _OutputIter
  1376.     reverse_copy(_BidirectionalIter __first, _BidirectionalIter __last,
  1377.                  _OutputIter __result)
  1378.     {
  1379.       // concept requirements
  1380.       __glibcpp_function_requires(_BidirectionalIteratorConcept<_BidirectionalIter>)
  1381.       __glibcpp_function_requires(_OutputIteratorConcept<_OutputIter,
  1382.         typename iterator_traits<_BidirectionalIter>::value_type>)
  1383.  
  1384.       while (__first != __last) {
  1385.     --__last;
  1386.     *__result = *__last;
  1387.     ++__result;
  1388.       }
  1389.       return __result;
  1390.     }
  1391.  
  1392.  
  1393.   /**
  1394.    *  @if maint
  1395.    *  This is a helper function for the rotate algorithm specialized on RAIs.
  1396.    *  It returns the greatest common divisor of two integer values.
  1397.    *  @endif
  1398.   */
  1399.   template<typename _EuclideanRingElement>
  1400.     _EuclideanRingElement
  1401.     __gcd(_EuclideanRingElement __m, _EuclideanRingElement __n)
  1402.     {
  1403.       while (__n != 0) {
  1404.     _EuclideanRingElement __t = __m % __n;
  1405.     __m = __n;
  1406.     __n = __t;
  1407.       }
  1408.       return __m;
  1409.     }
  1410.  
  1411.   /**
  1412.    *  @if maint
  1413.    *  This is a helper function for the rotate algorithm.
  1414.    *  @endif
  1415.   */
  1416.   template<typename _ForwardIter>
  1417.     void
  1418.     __rotate(_ForwardIter __first,
  1419.          _ForwardIter __middle,
  1420.          _ForwardIter __last,
  1421.           forward_iterator_tag)
  1422.     {
  1423.       if ((__first == __middle) || (__last  == __middle))
  1424.     return;
  1425.  
  1426.       _ForwardIter __first2 = __middle;
  1427.       do {
  1428.     swap(*__first++, *__first2++);
  1429.     if (__first == __middle)
  1430.       __middle = __first2;
  1431.       } while (__first2 != __last);
  1432.  
  1433.       __first2 = __middle;
  1434.  
  1435.       while (__first2 != __last) {
  1436.     swap(*__first++, *__first2++);
  1437.     if (__first == __middle)
  1438.       __middle = __first2;
  1439.     else if (__first2 == __last)
  1440.       __first2 = __middle;
  1441.       }
  1442.     }
  1443.  
  1444.   /**
  1445.    *  @if maint
  1446.    *  This is a helper function for the rotate algorithm.
  1447.    *  @endif
  1448.   */
  1449.   template<typename _BidirectionalIter>
  1450.     void
  1451.     __rotate(_BidirectionalIter __first,
  1452.          _BidirectionalIter __middle,
  1453.          _BidirectionalIter __last,
  1454.           bidirectional_iterator_tag)
  1455.     {
  1456.       // concept requirements
  1457.       __glibcpp_function_requires(_Mutable_BidirectionalIteratorConcept<
  1458.         _BidirectionalIter>)
  1459.  
  1460.       if ((__first == __middle) || (__last  == __middle))
  1461.     return;
  1462.  
  1463.       __reverse(__first,  __middle, bidirectional_iterator_tag());
  1464.       __reverse(__middle, __last,   bidirectional_iterator_tag());
  1465.  
  1466.       while (__first != __middle && __middle != __last)
  1467.     swap (*__first++, *--__last);
  1468.  
  1469.       if (__first == __middle) {
  1470.     __reverse(__middle, __last,   bidirectional_iterator_tag());
  1471.       }
  1472.       else {
  1473.     __reverse(__first,  __middle, bidirectional_iterator_tag());
  1474.       }
  1475.     }
  1476.  
  1477.   /**
  1478.    *  @if maint
  1479.    *  This is a helper function for the rotate algorithm.
  1480.    *  @endif
  1481.   */
  1482.   template<typename _RandomAccessIter>
  1483.     void
  1484.     __rotate(_RandomAccessIter __first,
  1485.          _RandomAccessIter __middle,
  1486.          _RandomAccessIter __last,
  1487.          random_access_iterator_tag)
  1488.     {
  1489.       // concept requirements
  1490.       __glibcpp_function_requires(_Mutable_RandomAccessIteratorConcept<
  1491.         _RandomAccessIter>)
  1492.  
  1493.       if ((__first == __middle) || (__last  == __middle))
  1494.     return;
  1495.  
  1496.       typedef typename iterator_traits<_RandomAccessIter>::difference_type _Distance;
  1497.       typedef typename iterator_traits<_RandomAccessIter>::value_type _ValueType;
  1498.  
  1499.       _Distance __n = __last   - __first;
  1500.       _Distance __k = __middle - __first;
  1501.       _Distance __l = __n - __k;
  1502.  
  1503.       if (__k == __l) {
  1504.     swap_ranges(__first, __middle, __middle);
  1505.     return;
  1506.       }
  1507.  
  1508.       _Distance __d = __gcd(__n, __k);
  1509.  
  1510.       for (_Distance __i = 0; __i < __d; __i++) {
  1511.     _ValueType __tmp = *__first;
  1512.     _RandomAccessIter __p = __first;
  1513.  
  1514.     if (__k < __l) {
  1515.       for (_Distance __j = 0; __j < __l/__d; __j++) {
  1516.         if (__p > __first + __l) {
  1517.           *__p = *(__p - __l);
  1518.           __p -= __l;
  1519.         }
  1520.  
  1521.         *__p = *(__p + __k);
  1522.         __p += __k;
  1523.       }
  1524.     }
  1525.  
  1526.     else {
  1527.       for (_Distance __j = 0; __j < __k/__d - 1; __j ++) {
  1528.         if (__p < __last - __k) {
  1529.           *__p = *(__p + __k);
  1530.           __p += __k;
  1531.         }
  1532.  
  1533.         *__p = * (__p - __l);
  1534.         __p -= __l;
  1535.       }
  1536.     }
  1537.  
  1538.     *__p = __tmp;
  1539.     ++__first;
  1540.       }
  1541.     }
  1542.  
  1543.   /**
  1544.    *  @brief Rotate the elements of a sequence.
  1545.    *  @param  first   A forward iterator.
  1546.    *  @param  middle  A forward iterator.
  1547.    *  @param  last    A forward iterator.
  1548.    *  @return  Nothing.
  1549.    *
  1550.    *  Rotates the elements of the range @p [first,last) by @p (middle-first)
  1551.    *  positions so that the element at @p middle is moved to @p first, the
  1552.    *  element at @p middle+1 is moved to @first+1 and so on for each element
  1553.    *  in the range @p [first,last).
  1554.    *
  1555.    *  This effectively swaps the ranges @p [first,middle) and
  1556.    *  @p [middle,last).
  1557.    *
  1558.    *  Performs @p *(first+(n+(last-middle))%(last-first))=*(first+n) for
  1559.    *  each @p n in the range @p [0,last-first).
  1560.   */
  1561.   template<typename _ForwardIter>
  1562.     inline void
  1563.     rotate(_ForwardIter __first, _ForwardIter __middle, _ForwardIter __last)
  1564.     {
  1565.       // concept requirements
  1566.       __glibcpp_function_requires(_Mutable_ForwardIteratorConcept<_ForwardIter>)
  1567.  
  1568.       typedef typename iterator_traits<_ForwardIter>::iterator_category _IterType;
  1569.       __rotate(__first, __middle, __last, _IterType());
  1570.     }
  1571.  
  1572.   /**
  1573.    *  @brief Copy a sequence, rotating its elements.
  1574.    *  @param  first   A forward iterator.
  1575.    *  @param  middle  A forward iterator.
  1576.    *  @param  last    A forward iterator.
  1577.    *  @param  result  An output iterator.
  1578.    *  @return   An iterator designating the end of the resulting sequence.
  1579.    *
  1580.    *  Copies the elements of the range @p [first,last) to the range
  1581.    *  beginning at @result, rotating the copied elements by @p (middle-first)
  1582.    *  positions so that the element at @p middle is moved to @p result, the
  1583.    *  element at @p middle+1 is moved to @result+1 and so on for each element
  1584.    *  in the range @p [first,last).
  1585.    *
  1586.    *  Performs @p *(result+(n+(last-middle))%(last-first))=*(first+n) for
  1587.    *  each @p n in the range @p [0,last-first).
  1588.   */
  1589.   template<typename _ForwardIter, typename _OutputIter>
  1590.     _OutputIter
  1591.     rotate_copy(_ForwardIter __first, _ForwardIter __middle,
  1592.                 _ForwardIter __last, _OutputIter __result)
  1593.     {
  1594.       // concept requirements
  1595.       __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter>)
  1596.       __glibcpp_function_requires(_OutputIteratorConcept<_OutputIter,
  1597.         typename iterator_traits<_ForwardIter>::value_type>)
  1598.  
  1599.       return copy(__first, __middle, copy(__middle, __last, __result));
  1600.     }
  1601.  
  1602.  
  1603.   /**
  1604.    *  @if maint
  1605.    *  Return a random number in the range [0, __n).  This function encapsulates
  1606.    *  whether we're using rand (part of the standard C library) or lrand48
  1607.    *  (not standard, but a much better choice whenever it's available).
  1608.    *
  1609.    *  XXX There is no corresponding encapsulation fn to seed the generator.
  1610.    *  @endif
  1611.   */
  1612.   template<typename _Distance>
  1613.     inline _Distance
  1614.     __random_number(_Distance __n)
  1615.     {
  1616.   #ifdef _GLIBCPP_HAVE_DRAND48
  1617.       return lrand48() % __n;
  1618.   #else
  1619.       return rand() % __n;
  1620.   #endif
  1621.     }
  1622.  
  1623.  
  1624.   /**
  1625.    *  @brief Randomly shuffle the elements of a sequence.
  1626.    *  @param  first   A forward iterator.
  1627.    *  @param  last    A forward iterator.
  1628.    *  @return  Nothing.
  1629.    *
  1630.    *  Reorder the elements in the range @p [first,last) using a random
  1631.    *  distribution, so that every possible ordering of the sequence is
  1632.    *  equally likely.
  1633.   */
  1634.   template<typename _RandomAccessIter>
  1635.     inline void
  1636.     random_shuffle(_RandomAccessIter __first, _RandomAccessIter __last)
  1637.     {
  1638.       // concept requirements
  1639.       __glibcpp_function_requires(_Mutable_RandomAccessIteratorConcept<
  1640.         _RandomAccessIter>)
  1641.  
  1642.       if (__first == __last) return;
  1643.       for (_RandomAccessIter __i = __first + 1; __i != __last; ++__i)
  1644.     iter_swap(__i, __first + __random_number((__i - __first) + 1));
  1645.     }
  1646.  
  1647.   /**
  1648.    *  @brief Shuffle the elements of a sequence using a random number
  1649.    *         generator.
  1650.    *  @param  first   A forward iterator.
  1651.    *  @param  last    A forward iterator.
  1652.    *  @param  rand    The RNG functor or function.
  1653.    *  @return  Nothing.
  1654.    *
  1655.    *  Reorders the elements in the range @p [first,last) using @p rand to
  1656.    *  provide a random distribution. Calling @p rand(N) for a positive
  1657.    *  integer @p N should return a randomly chosen integer from the
  1658.    *  range [0,N).
  1659.   */
  1660.   template<typename _RandomAccessIter, typename _RandomNumberGenerator>
  1661.     void
  1662.     random_shuffle(_RandomAccessIter __first, _RandomAccessIter __last,
  1663.            _RandomNumberGenerator& __rand)
  1664.     {
  1665.       // concept requirements
  1666.       __glibcpp_function_requires(_Mutable_RandomAccessIteratorConcept<
  1667.         _RandomAccessIter>)
  1668.  
  1669.       if (__first == __last) return;
  1670.       for (_RandomAccessIter __i = __first + 1; __i != __last; ++__i)
  1671.     iter_swap(__i, __first + __rand((__i - __first) + 1));
  1672.     }
  1673.  
  1674.  
  1675.   /**
  1676.    *  @if maint
  1677.    *  This is a helper function...
  1678.    *  @endif
  1679.   */
  1680.   template<typename _ForwardIter, typename _Predicate>
  1681.     _ForwardIter
  1682.     __partition(_ForwardIter __first, _ForwardIter __last,
  1683.         _Predicate   __pred,
  1684.         forward_iterator_tag)
  1685.     {
  1686.       if (__first == __last) return __first;
  1687.  
  1688.       while (__pred(*__first))
  1689.     if (++__first == __last) return __first;
  1690.  
  1691.       _ForwardIter __next = __first;
  1692.  
  1693.       while (++__next != __last)
  1694.     if (__pred(*__next)) {
  1695.       swap(*__first, *__next);
  1696.       ++__first;
  1697.     }
  1698.  
  1699.       return __first;
  1700.     }
  1701.  
  1702.   /**
  1703.    *  @if maint
  1704.    *  This is a helper function...
  1705.    *  @endif
  1706.   */
  1707.   template<typename _BidirectionalIter, typename _Predicate>
  1708.     _BidirectionalIter
  1709.     __partition(_BidirectionalIter __first, _BidirectionalIter __last,
  1710.         _Predicate __pred,
  1711.         bidirectional_iterator_tag)
  1712.     {
  1713.       while (true) {
  1714.     while (true)
  1715.       if (__first == __last)
  1716.         return __first;
  1717.       else if (__pred(*__first))
  1718.         ++__first;
  1719.       else
  1720.         break;
  1721.     --__last;
  1722.     while (true)
  1723.       if (__first == __last)
  1724.         return __first;
  1725.       else if (!__pred(*__last))
  1726.         --__last;
  1727.       else
  1728.         break;
  1729.     iter_swap(__first, __last);
  1730.     ++__first;
  1731.       }
  1732.     }
  1733.  
  1734.   /**
  1735.    *  @brief Move elements for which a predicate is true to the beginning
  1736.    *         of a sequence.
  1737.    *  @param  first   A forward iterator.
  1738.    *  @param  last    A forward iterator.
  1739.    *  @param  pred    A predicate functor.
  1740.    *  @return  An iterator @p middle such that @p pred(i) is true for each
  1741.    *  iterator @p i in the range @p [first,middle) and false for each @p i
  1742.    *  in the range @p [middle,last).
  1743.    *  
  1744.    *  @p pred must not modify its operand. @p partition() does not preserve
  1745.    *  the relative ordering of elements in each group, use
  1746.    *  @p stable_partition() if this is needed.
  1747.   */
  1748.   template<typename _ForwardIter, typename _Predicate>
  1749.     inline _ForwardIter
  1750.     partition(_ForwardIter __first, _ForwardIter __last,
  1751.           _Predicate   __pred)
  1752.     {
  1753.       // concept requirements
  1754.       __glibcpp_function_requires(_Mutable_ForwardIteratorConcept<_ForwardIter>)
  1755.       __glibcpp_function_requires(_UnaryPredicateConcept<_Predicate,
  1756.         typename iterator_traits<_ForwardIter>::value_type>)
  1757.  
  1758.       return __partition(__first, __last, __pred, __iterator_category(__first));
  1759.     }
  1760.  
  1761.  
  1762.   /**
  1763.    *  @if maint
  1764.    *  This is a helper function...
  1765.    *  @endif
  1766.   */
  1767.   template<typename _ForwardIter, typename _Predicate, typename _Distance>
  1768.     _ForwardIter
  1769.     __inplace_stable_partition(_ForwardIter __first, _ForwardIter __last,
  1770.                    _Predicate __pred, _Distance __len)
  1771.     {
  1772.       if (__len == 1)
  1773.     return __pred(*__first) ? __last : __first;
  1774.       _ForwardIter __middle = __first;
  1775.       advance(__middle, __len / 2);
  1776.       _ForwardIter __begin = __inplace_stable_partition(__first, __middle,
  1777.                             __pred,
  1778.                             __len / 2);
  1779.       _ForwardIter __end = __inplace_stable_partition(__middle, __last,
  1780.                               __pred,
  1781.                               __len - __len / 2);
  1782.       rotate(__begin, __middle, __end);
  1783.       advance(__begin, distance(__middle, __end));
  1784.       return __begin;
  1785.     }
  1786.  
  1787.   /**
  1788.    *  @if maint
  1789.    *  This is a helper function...
  1790.    *  @endif
  1791.   */
  1792.   template<typename _ForwardIter, typename _Pointer, typename _Predicate,
  1793.        typename _Distance>
  1794.     _ForwardIter
  1795.     __stable_partition_adaptive(_ForwardIter __first, _ForwardIter __last,
  1796.                 _Predicate __pred, _Distance __len,
  1797.                 _Pointer __buffer,
  1798.                 _Distance __buffer_size)
  1799.     {
  1800.       if (__len <= __buffer_size) {
  1801.     _ForwardIter __result1 = __first;
  1802.     _Pointer __result2 = __buffer;
  1803.     for ( ; __first != __last ; ++__first)
  1804.       if (__pred(*__first)) {
  1805.         *__result1 = *__first;
  1806.         ++__result1;
  1807.       }
  1808.       else {
  1809.         *__result2 = *__first;
  1810.         ++__result2;
  1811.       }
  1812.     copy(__buffer, __result2, __result1);
  1813.     return __result1;
  1814.       }
  1815.       else {
  1816.     _ForwardIter __middle = __first;
  1817.     advance(__middle, __len / 2);
  1818.     _ForwardIter __begin = __stable_partition_adaptive(__first, __middle,
  1819.                                __pred,
  1820.                                __len / 2,
  1821.                                __buffer, __buffer_size);
  1822.     _ForwardIter __end = __stable_partition_adaptive( __middle, __last,
  1823.                               __pred,
  1824.                               __len - __len / 2,
  1825.                               __buffer, __buffer_size);
  1826.     rotate(__begin, __middle, __end);
  1827.     advance(__begin, distance(__middle, __end));
  1828.     return __begin;
  1829.       }
  1830.     }
  1831.  
  1832.   /**
  1833.    *  @brief Move elements for which a predicate is true to the beginning
  1834.    *         of a sequence, preserving relative ordering.
  1835.    *  @param  first   A forward iterator.
  1836.    *  @param  last    A forward iterator.
  1837.    *  @param  pred    A predicate functor.
  1838.    *  @return  An iterator @p middle such that @p pred(i) is true for each
  1839.    *  iterator @p i in the range @p [first,middle) and false for each @p i
  1840.    *  in the range @p [middle,last).
  1841.    *  
  1842.    *  Performs the same function as @p partition() with the additional
  1843.    *  guarantee that the relative ordering of elements in each group is
  1844.    *  preserved, so any two elements @p x and @p y in the range
  1845.    *  @p [first,last) such that @p pred(x)==pred(y) will have the same
  1846.    *  relative ordering after calling @p stable_partition().
  1847.   */
  1848.   template<typename _ForwardIter, typename _Predicate>
  1849.     _ForwardIter
  1850.     stable_partition(_ForwardIter __first, _ForwardIter __last,
  1851.              _Predicate __pred)
  1852.     {
  1853.       // concept requirements
  1854.       __glibcpp_function_requires(_Mutable_ForwardIteratorConcept<_ForwardIter>)
  1855.       __glibcpp_function_requires(_UnaryPredicateConcept<_Predicate,
  1856.         typename iterator_traits<_ForwardIter>::value_type>)
  1857.  
  1858.       if (__first == __last)
  1859.     return __first;
  1860.       else
  1861.       {
  1862.     typedef typename iterator_traits<_ForwardIter>::value_type _ValueType;
  1863.     typedef typename iterator_traits<_ForwardIter>::difference_type _DistanceType;
  1864.  
  1865.     _Temporary_buffer<_ForwardIter, _ValueType> __buf(__first, __last);
  1866.     if (__buf.size() > 0)
  1867.       return __stable_partition_adaptive(__first, __last, __pred,
  1868.                          _DistanceType(__buf.requested_size()),
  1869.                          __buf.begin(), __buf.size());
  1870.     else
  1871.       return __inplace_stable_partition(__first, __last, __pred,
  1872.                         _DistanceType(__buf.requested_size()));
  1873.       }
  1874.     }
  1875.  
  1876.   /**
  1877.    *  @if maint
  1878.    *  This is a helper function...
  1879.    *  @endif
  1880.   */
  1881.   template<typename _RandomAccessIter, typename _Tp>
  1882.     _RandomAccessIter
  1883.     __unguarded_partition(_RandomAccessIter __first, _RandomAccessIter __last,
  1884.               _Tp __pivot)
  1885.     {
  1886.       while (true) {
  1887.     while (*__first < __pivot)
  1888.       ++__first;
  1889.     --__last;
  1890.     while (__pivot < *__last)
  1891.       --__last;
  1892.     if (!(__first < __last))
  1893.       return __first;
  1894.     iter_swap(__first, __last);
  1895.     ++__first;
  1896.       }
  1897.     }
  1898.  
  1899.   /**
  1900.    *  @if maint
  1901.    *  This is a helper function...
  1902.    *  @endif
  1903.   */
  1904.   template<typename _RandomAccessIter, typename _Tp, typename _Compare>
  1905.     _RandomAccessIter
  1906.     __unguarded_partition(_RandomAccessIter __first, _RandomAccessIter __last,
  1907.               _Tp __pivot, _Compare __comp)
  1908.     {
  1909.       while (true) {
  1910.     while (__comp(*__first, __pivot))
  1911.       ++__first;
  1912.     --__last;
  1913.     while (__comp(__pivot, *__last))
  1914.       --__last;
  1915.     if (!(__first < __last))
  1916.       return __first;
  1917.     iter_swap(__first, __last);
  1918.     ++__first;
  1919.       }
  1920.     }
  1921.  
  1922.  
  1923.   /**
  1924.    *  @if maint
  1925.    *  @doctodo
  1926.    *  This controls some aspect of the sort routines.
  1927.    *  @endif
  1928.   */
  1929.   enum { _M_threshold = 16 };
  1930.  
  1931.   /**
  1932.    *  @if maint
  1933.    *  This is a helper function for the sort routine.
  1934.    *  @endif
  1935.   */
  1936.   template<typename _RandomAccessIter, typename _Tp>
  1937.     void
  1938.     __unguarded_linear_insert(_RandomAccessIter __last, _Tp __val)
  1939.     {
  1940.       _RandomAccessIter __next = __last;
  1941.       --__next;
  1942.       while (__val < *__next) {
  1943.     *__last = *__next;
  1944.     __last = __next;
  1945.     --__next;
  1946.       }
  1947.       *__last = __val;
  1948.     }
  1949.  
  1950.   /**
  1951.    *  @if maint
  1952.    *  This is a helper function for the sort routine.
  1953.    *  @endif
  1954.   */
  1955.   template<typename _RandomAccessIter, typename _Tp, typename _Compare>
  1956.     void
  1957.     __unguarded_linear_insert(_RandomAccessIter __last, _Tp __val, _Compare __comp)
  1958.     {
  1959.       _RandomAccessIter __next = __last;
  1960.       --__next;
  1961.       while (__comp(__val, *__next)) {
  1962.     *__last = *__next;
  1963.     __last = __next;
  1964.     --__next;
  1965.       }
  1966.       *__last = __val;
  1967.     }
  1968.  
  1969.   /**
  1970.    *  @if maint
  1971.    *  This is a helper function for the sort routine.
  1972.    *  @endif
  1973.   */
  1974.   template<typename _RandomAccessIter>
  1975.     void
  1976.     __insertion_sort(_RandomAccessIter __first, _RandomAccessIter __last)
  1977.     {
  1978.       if (__first == __last) return;
  1979.  
  1980.       for (_RandomAccessIter __i = __first + 1; __i != __last; ++__i)
  1981.       {
  1982.     typename iterator_traits<_RandomAccessIter>::value_type __val = *__i;
  1983.     if (__val < *__first) {
  1984.       copy_backward(__first, __i, __i + 1);
  1985.       *__first = __val;
  1986.     }
  1987.     else
  1988.       __unguarded_linear_insert(__i, __val);
  1989.       }
  1990.     }
  1991.  
  1992.   /**
  1993.    *  @if maint
  1994.    *  This is a helper function for the sort routine.
  1995.    *  @endif
  1996.   */
  1997.   template<typename _RandomAccessIter, typename _Compare>
  1998.     void
  1999.     __insertion_sort(_RandomAccessIter __first, _RandomAccessIter __last,
  2000.              _Compare __comp)
  2001.     {
  2002.       if (__first == __last) return;
  2003.  
  2004.       for (_RandomAccessIter __i = __first + 1; __i != __last; ++__i)
  2005.       {
  2006.     typename iterator_traits<_RandomAccessIter>::value_type __val = *__i;
  2007.     if (__comp(__val, *__first)) {
  2008.       copy_backward(__first, __i, __i + 1);
  2009.       *__first = __val;
  2010.     }
  2011.     else
  2012.       __unguarded_linear_insert(__i, __val, __comp);
  2013.       }
  2014.     }
  2015.  
  2016.   /**
  2017.    *  @if maint
  2018.    *  This is a helper function for the sort routine.
  2019.    *  @endif
  2020.   */
  2021.   template<typename _RandomAccessIter>
  2022.     inline void
  2023.     __unguarded_insertion_sort(_RandomAccessIter __first, _RandomAccessIter __last)
  2024.     {
  2025.       typedef typename iterator_traits<_RandomAccessIter>::value_type _ValueType;
  2026.  
  2027.       for (_RandomAccessIter __i = __first; __i != __last; ++__i)
  2028.     __unguarded_linear_insert(__i, _ValueType(*__i));
  2029.     }
  2030.  
  2031.   /**
  2032.    *  @if maint
  2033.    *  This is a helper function for the sort routine.
  2034.    *  @endif
  2035.   */
  2036.   template<typename _RandomAccessIter, typename _Compare>
  2037.     inline void
  2038.     __unguarded_insertion_sort(_RandomAccessIter __first, _RandomAccessIter __last,
  2039.                    _Compare __comp)
  2040.     {
  2041.       typedef typename iterator_traits<_RandomAccessIter>::value_type _ValueType;
  2042.  
  2043.       for (_RandomAccessIter __i = __first; __i != __last; ++__i)
  2044.     __unguarded_linear_insert(__i, _ValueType(*__i), __comp);
  2045.     }
  2046.  
  2047.   /**
  2048.    *  @if maint
  2049.    *  This is a helper function for the sort routine.
  2050.    *  @endif
  2051.   */
  2052.   template<typename _RandomAccessIter>
  2053.     void
  2054.     __final_insertion_sort(_RandomAccessIter __first, _RandomAccessIter __last)
  2055.     {
  2056.       if (__last - __first > _M_threshold) {
  2057.     __insertion_sort(__first, __first + _M_threshold);
  2058.     __unguarded_insertion_sort(__first + _M_threshold, __last);
  2059.       }
  2060.       else
  2061.     __insertion_sort(__first, __last);
  2062.     }
  2063.  
  2064.   /**
  2065.    *  @if maint
  2066.    *  This is a helper function for the sort routine.
  2067.    *  @endif
  2068.   */
  2069.   template<typename _RandomAccessIter, typename _Compare>
  2070.     void
  2071.     __final_insertion_sort(_RandomAccessIter __first, _RandomAccessIter __last,
  2072.                _Compare __comp)
  2073.     {
  2074.       if (__last - __first > _M_threshold) {
  2075.     __insertion_sort(__first, __first + _M_threshold, __comp);
  2076.     __unguarded_insertion_sort(__first + _M_threshold, __last, __comp);
  2077.       }
  2078.       else
  2079.     __insertion_sort(__first, __last, __comp);
  2080.     }
  2081.  
  2082.   /**
  2083.    *  @if maint
  2084.    *  This is a helper function for the sort routine.
  2085.    *  @endif
  2086.   */
  2087.   template<typename _Size>
  2088.     inline _Size
  2089.     __lg(_Size __n)
  2090.     {
  2091.       _Size __k;
  2092.       for (__k = 0; __n != 1; __n >>= 1) ++__k;
  2093.       return __k;
  2094.     }
  2095.  
  2096.   /**
  2097.    *  @if maint
  2098.    *  This is a helper function for the sort routine.
  2099.    *  @endif
  2100.   */
  2101.   template<typename _RandomAccessIter, typename _Size>
  2102.     void
  2103.     __introsort_loop(_RandomAccessIter __first, _RandomAccessIter __last,
  2104.              _Size __depth_limit)
  2105.     {
  2106.       typedef typename iterator_traits<_RandomAccessIter>::value_type _ValueType;
  2107.  
  2108.       while (__last - __first > _M_threshold) {
  2109.     if (__depth_limit == 0) {
  2110.       partial_sort(__first, __last, __last);
  2111.       return;
  2112.     }
  2113.     --__depth_limit;
  2114.     _RandomAccessIter __cut =
  2115.       __unguarded_partition(__first, __last,
  2116.                 _ValueType(__median(*__first,
  2117.                             *(__first + (__last - __first)/2),
  2118.                             *(__last - 1))));
  2119.     __introsort_loop(__cut, __last, __depth_limit);
  2120.     __last = __cut;
  2121.       }
  2122.     }
  2123.  
  2124.   /**
  2125.    *  @if maint
  2126.    *  This is a helper function for the sort routine.
  2127.    *  @endif
  2128.   */
  2129.   template<typename _RandomAccessIter, typename _Size, typename _Compare>
  2130.     void
  2131.     __introsort_loop(_RandomAccessIter __first, _RandomAccessIter __last,
  2132.              _Size __depth_limit, _Compare __comp)
  2133.     {
  2134.       typedef typename iterator_traits<_RandomAccessIter>::value_type _ValueType;
  2135.  
  2136.       while (__last - __first > _M_threshold) {
  2137.     if (__depth_limit == 0) {
  2138.       partial_sort(__first, __last, __last, __comp);
  2139.       return;
  2140.     }
  2141.     --__depth_limit;
  2142.     _RandomAccessIter __cut =
  2143.       __unguarded_partition(__first, __last,
  2144.                 _ValueType(__median(*__first,
  2145.                             *(__first + (__last - __first)/2),
  2146.                             *(__last - 1), __comp)),
  2147.        __comp);
  2148.     __introsort_loop(__cut, __last, __depth_limit, __comp);
  2149.     __last = __cut;
  2150.       }
  2151.     }
  2152.  
  2153.   /**
  2154.    *  @brief Sort the elements of a sequence.
  2155.    *  @param  first   An iterator.
  2156.    *  @param  last    Another iterator.
  2157.    *  @return  Nothing.
  2158.    *
  2159.    *  Sorts the elements in the range @p [first,last) in ascending order,
  2160.    *  such that @p *(i+1)<*i is false for each iterator @p i in the range
  2161.    *  @p [first,last-1).
  2162.    *
  2163.    *  The relative ordering of equivalent elements is not preserved, use
  2164.    *  @p stable_sort() if this is needed.
  2165.   */
  2166.   template<typename _RandomAccessIter>
  2167.     inline void
  2168.     sort(_RandomAccessIter __first, _RandomAccessIter __last)
  2169.     {
  2170.       typedef typename iterator_traits<_RandomAccessIter>::value_type _ValueType;
  2171.  
  2172.       // concept requirements
  2173.       __glibcpp_function_requires(_Mutable_RandomAccessIteratorConcept<
  2174.         _RandomAccessIter>)
  2175.       __glibcpp_function_requires(_LessThanComparableConcept<_ValueType>)
  2176.  
  2177.       if (__first != __last) {
  2178.     __introsort_loop(__first, __last, __lg(__last - __first) * 2);
  2179.     __final_insertion_sort(__first, __last);
  2180.       }
  2181.     }
  2182.  
  2183.   /**
  2184.    *  @brief Sort the elements of a sequence using a predicate for comparison.
  2185.    *  @param  first   An iterator.
  2186.    *  @param  last    Another iterator.
  2187.    *  @param  comp    A comparison functor.
  2188.    *  @return  Nothing.
  2189.    *
  2190.    *  Sorts the elements in the range @p [first,last) in ascending order,
  2191.    *  such that @p comp(*(i+1),*i) is false for every iterator @p i in the
  2192.    *  range @p [first,last-1).
  2193.    *
  2194.    *  The relative ordering of equivalent elements is not preserved, use
  2195.    *  @p stable_sort() if this is needed.
  2196.   */
  2197.   template<typename _RandomAccessIter, typename _Compare>
  2198.     inline void
  2199.     sort(_RandomAccessIter __first, _RandomAccessIter __last, _Compare __comp)
  2200.     {
  2201.       typedef typename iterator_traits<_RandomAccessIter>::value_type _ValueType;
  2202.  
  2203.       // concept requirements
  2204.       __glibcpp_function_requires(_Mutable_RandomAccessIteratorConcept<
  2205.         _RandomAccessIter>)
  2206.       __glibcpp_function_requires(_BinaryPredicateConcept<_Compare, _ValueType, _ValueType>)
  2207.  
  2208.       if (__first != __last) {
  2209.     __introsort_loop(__first, __last, __lg(__last - __first) * 2, __comp);
  2210.     __final_insertion_sort(__first, __last, __comp);
  2211.       }
  2212.     }
  2213.  
  2214.  
  2215.   /**
  2216.    *  @if maint
  2217.    *  This is a helper function for the stable sorting routines.
  2218.    *  @endif
  2219.   */
  2220.   template<typename _RandomAccessIter>
  2221.     void
  2222.     __inplace_stable_sort(_RandomAccessIter __first, _RandomAccessIter __last)
  2223.     {
  2224.       if (__last - __first < 15) {
  2225.     __insertion_sort(__first, __last);
  2226.     return;
  2227.       }
  2228.       _RandomAccessIter __middle = __first + (__last - __first) / 2;
  2229.       __inplace_stable_sort(__first, __middle);
  2230.       __inplace_stable_sort(__middle, __last);
  2231.       __merge_without_buffer(__first, __middle, __last,
  2232.                  __middle - __first,
  2233.                  __last - __middle);
  2234.     }
  2235.  
  2236.   /**
  2237.    *  @if maint
  2238.    *  This is a helper function for the stable sorting routines.
  2239.    *  @endif
  2240.   */
  2241.   template<typename _RandomAccessIter, typename _Compare>
  2242.     void
  2243.     __inplace_stable_sort(_RandomAccessIter __first, _RandomAccessIter __last,
  2244.               _Compare __comp)
  2245.     {
  2246.       if (__last - __first < 15) {
  2247.     __insertion_sort(__first, __last, __comp);
  2248.     return;
  2249.       }
  2250.       _RandomAccessIter __middle = __first + (__last - __first) / 2;
  2251.       __inplace_stable_sort(__first, __middle, __comp);
  2252.       __inplace_stable_sort(__middle, __last, __comp);
  2253.       __merge_without_buffer(__first, __middle, __last,
  2254.                  __middle - __first,
  2255.                  __last - __middle,
  2256.                  __comp);
  2257.     }
  2258.  
  2259.   template<typename _RandomAccessIter1, typename _RandomAccessIter2,
  2260.        typename _Distance>
  2261.     void
  2262.     __merge_sort_loop(_RandomAccessIter1 __first, _RandomAccessIter1 __last,
  2263.               _RandomAccessIter2 __result, _Distance __step_size)
  2264.     {
  2265.       _Distance __two_step = 2 * __step_size;
  2266.  
  2267.       while (__last - __first >= __two_step) {
  2268.     __result = merge(__first, __first + __step_size,
  2269.              __first + __step_size, __first + __two_step,
  2270.              __result);
  2271.     __first += __two_step;
  2272.       }
  2273.  
  2274.       __step_size = min(_Distance(__last - __first), __step_size);
  2275.       merge(__first, __first + __step_size, __first + __step_size, __last,
  2276.         __result);
  2277.     }
  2278.  
  2279.   template<typename _RandomAccessIter1, typename _RandomAccessIter2,
  2280.        typename _Distance, typename _Compare>
  2281.     void
  2282.     __merge_sort_loop(_RandomAccessIter1 __first, _RandomAccessIter1 __last,
  2283.               _RandomAccessIter2 __result, _Distance __step_size,
  2284.               _Compare __comp)
  2285.     {
  2286.       _Distance __two_step = 2 * __step_size;
  2287.  
  2288.       while (__last - __first >= __two_step) {
  2289.     __result = merge(__first, __first + __step_size,
  2290.              __first + __step_size, __first + __two_step,
  2291.              __result,
  2292.              __comp);
  2293.     __first += __two_step;
  2294.       }
  2295.       __step_size = min(_Distance(__last - __first), __step_size);
  2296.  
  2297.       merge(__first, __first + __step_size,
  2298.         __first + __step_size, __last,
  2299.         __result,
  2300.         __comp);
  2301.     }
  2302.  
  2303.   enum { _M_chunk_size = 7 };
  2304.  
  2305.   template<typename _RandomAccessIter, typename _Distance>
  2306.     void
  2307.     __chunk_insertion_sort(_RandomAccessIter __first, _RandomAccessIter __last,
  2308.                _Distance __chunk_size)
  2309.     {
  2310.       while (__last - __first >= __chunk_size) {
  2311.     __insertion_sort(__first, __first + __chunk_size);
  2312.     __first += __chunk_size;
  2313.       }
  2314.       __insertion_sort(__first, __last);
  2315.     }
  2316.  
  2317.   template<typename _RandomAccessIter, typename _Distance, typename _Compare>
  2318.     void
  2319.     __chunk_insertion_sort(_RandomAccessIter __first, _RandomAccessIter __last,
  2320.                _Distance __chunk_size, _Compare __comp)
  2321.     {
  2322.       while (__last - __first >= __chunk_size) {
  2323.     __insertion_sort(__first, __first + __chunk_size, __comp);
  2324.     __first += __chunk_size;
  2325.       }
  2326.       __insertion_sort(__first, __last, __comp);
  2327.     }
  2328.  
  2329.   template<typename _RandomAccessIter, typename _Pointer>
  2330.     void
  2331.     __merge_sort_with_buffer(_RandomAccessIter __first, _RandomAccessIter __last,
  2332.                              _Pointer __buffer)
  2333.     {
  2334.       typedef typename iterator_traits<_RandomAccessIter>::difference_type _Distance;
  2335.  
  2336.       _Distance __len = __last - __first;
  2337.       _Pointer __buffer_last = __buffer + __len;
  2338.  
  2339.       _Distance __step_size = _M_chunk_size;
  2340.       __chunk_insertion_sort(__first, __last, __step_size);
  2341.  
  2342.       while (__step_size < __len) {
  2343.     __merge_sort_loop(__first, __last, __buffer, __step_size);
  2344.     __step_size *= 2;
  2345.     __merge_sort_loop(__buffer, __buffer_last, __first, __step_size);
  2346.     __step_size *= 2;
  2347.       }
  2348.     }
  2349.  
  2350.   template<typename _RandomAccessIter, typename _Pointer, typename _Compare>
  2351.     void
  2352.     __merge_sort_with_buffer(_RandomAccessIter __first, _RandomAccessIter __last,
  2353.                              _Pointer __buffer, _Compare __comp)
  2354.     {
  2355.       typedef typename iterator_traits<_RandomAccessIter>::difference_type _Distance;
  2356.  
  2357.       _Distance __len = __last - __first;
  2358.       _Pointer __buffer_last = __buffer + __len;
  2359.  
  2360.       _Distance __step_size = _M_chunk_size;
  2361.       __chunk_insertion_sort(__first, __last, __step_size, __comp);
  2362.  
  2363.       while (__step_size < __len) {
  2364.     __merge_sort_loop(__first, __last, __buffer, __step_size, __comp);
  2365.     __step_size *= 2;
  2366.     __merge_sort_loop(__buffer, __buffer_last, __first, __step_size, __comp);
  2367.     __step_size *= 2;
  2368.       }
  2369.     }
  2370.  
  2371.   template<typename _RandomAccessIter, typename _Pointer, typename _Distance>
  2372.     void
  2373.     __stable_sort_adaptive(_RandomAccessIter __first, _RandomAccessIter __last,
  2374.                            _Pointer __buffer, _Distance __buffer_size)
  2375.     {
  2376.       _Distance __len = (__last - __first + 1) / 2;
  2377.       _RandomAccessIter __middle = __first + __len;
  2378.       if (__len > __buffer_size) {
  2379.     __stable_sort_adaptive(__first, __middle, __buffer, __buffer_size);
  2380.     __stable_sort_adaptive(__middle, __last, __buffer, __buffer_size);
  2381.       }
  2382.       else {
  2383.     __merge_sort_with_buffer(__first, __middle, __buffer);
  2384.     __merge_sort_with_buffer(__middle, __last, __buffer);
  2385.       }
  2386.       __merge_adaptive(__first, __middle, __last, _Distance(__middle - __first),
  2387.                        _Distance(__last - __middle), __buffer, __buffer_size);
  2388.     }
  2389.  
  2390.   template<typename _RandomAccessIter, typename _Pointer, typename _Distance,
  2391.            typename _Compare>
  2392.     void
  2393.     __stable_sort_adaptive(_RandomAccessIter __first, _RandomAccessIter __last,
  2394.                            _Pointer __buffer, _Distance __buffer_size,
  2395.                            _Compare __comp)
  2396.     {
  2397.       _Distance __len = (__last - __first + 1) / 2;
  2398.       _RandomAccessIter __middle = __first + __len;
  2399.       if (__len > __buffer_size) {
  2400.     __stable_sort_adaptive(__first, __middle, __buffer, __buffer_size,
  2401.                                __comp);
  2402.     __stable_sort_adaptive(__middle, __last, __buffer, __buffer_size,
  2403.                                __comp);
  2404.       }
  2405.       else {
  2406.     __merge_sort_with_buffer(__first, __middle, __buffer, __comp);
  2407.     __merge_sort_with_buffer(__middle, __last, __buffer, __comp);
  2408.       }
  2409.       __merge_adaptive(__first, __middle, __last, _Distance(__middle - __first),
  2410.                        _Distance(__last - __middle), __buffer, __buffer_size,
  2411.                        __comp);
  2412.     }
  2413.  
  2414.   /**
  2415.    *  @brief Sort the elements of a sequence, preserving the relative order
  2416.    *         of equivalent elements.
  2417.    *  @param  first   An iterator.
  2418.    *  @param  last    Another iterator.
  2419.    *  @return  Nothing.
  2420.    *
  2421.    *  Sorts the elements in the range @p [first,last) in ascending order,
  2422.    *  such that @p *(i+1)<*i is false for each iterator @p i in the range
  2423.    *  @p [first,last-1).
  2424.    *
  2425.    *  The relative ordering of equivalent elements is preserved, so any two
  2426.    *  elements @p x and @p y in the range @p [first,last) such that
  2427.    *  @p x<y is false and @p y<x is false will have the same relative
  2428.    *  ordering after calling @p stable_sort().
  2429.   */
  2430.   template<typename _RandomAccessIter>
  2431.     inline void
  2432.     stable_sort(_RandomAccessIter __first, _RandomAccessIter __last)
  2433.     {
  2434.       typedef typename iterator_traits<_RandomAccessIter>::value_type _ValueType;
  2435.       typedef typename iterator_traits<_RandomAccessIter>::difference_type _DistanceType;
  2436.  
  2437.       // concept requirements
  2438.       __glibcpp_function_requires(_Mutable_RandomAccessIteratorConcept<
  2439.         _RandomAccessIter>)
  2440.       __glibcpp_function_requires(_LessThanComparableConcept<_ValueType>)
  2441.  
  2442.       _Temporary_buffer<_RandomAccessIter, _ValueType> buf(__first, __last);
  2443.       if (buf.begin() == 0)
  2444.     __inplace_stable_sort(__first, __last);
  2445.       else
  2446.     __stable_sort_adaptive(__first, __last, buf.begin(), _DistanceType(buf.size()));
  2447.     }
  2448.  
  2449.   /**
  2450.    *  @brief Sort the elements of a sequence using a predicate for comparison,
  2451.    *         preserving the relative order of equivalent elements.
  2452.    *  @param  first   An iterator.
  2453.    *  @param  last    Another iterator.
  2454.    *  @param  comp    A comparison functor.
  2455.    *  @return  Nothing.
  2456.    *
  2457.    *  Sorts the elements in the range @p [first,last) in ascending order,
  2458.    *  such that @p comp(*(i+1),*i) is false for each iterator @p i in the
  2459.    *  range @p [first,last-1).
  2460.    *
  2461.    *  The relative ordering of equivalent elements is preserved, so any two
  2462.    *  elements @p x and @p y in the range @p [first,last) such that
  2463.    *  @p comp(x,y) is false and @p comp(y,x) is false will have the same
  2464.    *  relative ordering after calling @p stable_sort().
  2465.   */
  2466.   template<typename _RandomAccessIter, typename _Compare>
  2467.     inline void
  2468.     stable_sort(_RandomAccessIter __first, _RandomAccessIter __last, _Compare __comp)
  2469.     {
  2470.       typedef typename iterator_traits<_RandomAccessIter>::value_type _ValueType;
  2471.       typedef typename iterator_traits<_RandomAccessIter>::difference_type _DistanceType;
  2472.  
  2473.       // concept requirements
  2474.       __glibcpp_function_requires(_Mutable_RandomAccessIteratorConcept<
  2475.         _RandomAccessIter>)
  2476.       __glibcpp_function_requires(_BinaryPredicateConcept<_Compare,
  2477.                               _ValueType, _ValueType>)
  2478.  
  2479.       _Temporary_buffer<_RandomAccessIter, _ValueType> buf(__first, __last);
  2480.       if (buf.begin() == 0)
  2481.     __inplace_stable_sort(__first, __last, __comp);
  2482.       else
  2483.     __stable_sort_adaptive(__first, __last, buf.begin(), _DistanceType(buf.size()),
  2484.                    __comp);
  2485.     }
  2486.  
  2487.   /**
  2488.    *  @brief Sort the smallest elements of a sequence.
  2489.    *  @param  first   An iterator.
  2490.    *  @param  middle  Another iterator.
  2491.    *  @param  last    Another iterator.
  2492.    *  @return  Nothing.
  2493.    *
  2494.    *  Sorts the smallest @p (middle-first) elements in the range
  2495.    *  @p [first,last) and moves them to the range @p [first,middle). The
  2496.    *  order of the remaining elements in the range @p [middle,last) is
  2497.    *  undefined.
  2498.    *  After the sort if @p i and @j are iterators in the range
  2499.    *  @p [first,middle) such that @i precedes @j and @k is an iterator in
  2500.    *  the range @p [middle,last) then @p *j<*i and @p *k<*i are both false.
  2501.   */
  2502.   template<typename _RandomAccessIter>
  2503.     void
  2504.     partial_sort(_RandomAccessIter __first,
  2505.          _RandomAccessIter __middle,
  2506.          _RandomAccessIter __last)
  2507.     {
  2508.       typedef typename iterator_traits<_RandomAccessIter>::value_type _ValueType;
  2509.  
  2510.       // concept requirements
  2511.       __glibcpp_function_requires(_Mutable_RandomAccessIteratorConcept<
  2512.         _RandomAccessIter>)
  2513.       __glibcpp_function_requires(_LessThanComparableConcept<_ValueType>)
  2514.  
  2515.       make_heap(__first, __middle);
  2516.       for (_RandomAccessIter __i = __middle; __i < __last; ++__i)
  2517.     if (*__i < *__first)
  2518.       __pop_heap(__first, __middle, __i, _ValueType(*__i));
  2519.       sort_heap(__first, __middle);
  2520.     }
  2521.  
  2522.   /**
  2523.    *  @brief Sort the smallest elements of a sequence using a predicate
  2524.    *         for comparison.
  2525.    *  @param  first   An iterator.
  2526.    *  @param  middle  Another iterator.
  2527.    *  @param  last    Another iterator.
  2528.    *  @param  comp    A comparison functor.
  2529.    *  @return  Nothing.
  2530.    *
  2531.    *  Sorts the smallest @p (middle-first) elements in the range
  2532.    *  @p [first,last) and moves them to the range @p [first,middle). The
  2533.    *  order of the remaining elements in the range @p [middle,last) is
  2534.    *  undefined.
  2535.    *  After the sort if @p i and @j are iterators in the range
  2536.    *  @p [first,middle) such that @i precedes @j and @k is an iterator in
  2537.    *  the range @p [middle,last) then @p *comp(j,*i) and @p comp(*k,*i)
  2538.    *  are both false.
  2539.   */
  2540.   template<typename _RandomAccessIter, typename _Compare>
  2541.     void
  2542.     partial_sort(_RandomAccessIter __first,
  2543.          _RandomAccessIter __middle,
  2544.          _RandomAccessIter __last,
  2545.          _Compare __comp)
  2546.     {
  2547.       typedef typename iterator_traits<_RandomAccessIter>::value_type _ValueType;
  2548.  
  2549.       // concept requirements
  2550.       __glibcpp_function_requires(_Mutable_RandomAccessIteratorConcept<
  2551.         _RandomAccessIter>)
  2552.       __glibcpp_function_requires(_BinaryPredicateConcept<_Compare,
  2553.                               _ValueType, _ValueType>)
  2554.  
  2555.       make_heap(__first, __middle, __comp);
  2556.       for (_RandomAccessIter __i = __middle; __i < __last; ++__i)
  2557.     if (__comp(*__i, *__first))
  2558.       __pop_heap(__first, __middle, __i, _ValueType(*__i), __comp);
  2559.       sort_heap(__first, __middle, __comp);
  2560.     }
  2561.  
  2562.   /**
  2563.    *  @brief Copy the smallest elements of a sequence.
  2564.    *  @param  first   An iterator.
  2565.    *  @param  last    Another iterator.
  2566.    *  @param  result_first   A random-access iterator.
  2567.    *  @param  result_last    Another random-access iterator.
  2568.    *  @return   An iterator indicating the end of the resulting sequence.
  2569.    *
  2570.    *  Copies and sorts the smallest N values from the range @p [first,last)
  2571.    *  to the range beginning at @p result_first, where the number of
  2572.    *  elements to be copied, @p N, is the smaller of @p (last-first) and
  2573.    *  @p (result_last-result_first).
  2574.    *  After the sort if @p i and @j are iterators in the range
  2575.    *  @p [result_first,result_first+N) such that @i precedes @j then
  2576.    *  @p *j<*i is false.
  2577.    *  The value returned is @p result_first+N.
  2578.   */
  2579.   template<typename _InputIter, typename _RandomAccessIter>
  2580.     _RandomAccessIter
  2581.     partial_sort_copy(_InputIter __first, _InputIter __last,
  2582.               _RandomAccessIter __result_first,
  2583.               _RandomAccessIter __result_last)
  2584.     {
  2585.       typedef typename iterator_traits<_InputIter>::value_type _InputValueType;
  2586.       typedef typename iterator_traits<_RandomAccessIter>::value_type _OutputValueType;
  2587.       typedef typename iterator_traits<_RandomAccessIter>::difference_type _DistanceType;
  2588.  
  2589.       // concept requirements
  2590.       __glibcpp_function_requires(_InputIteratorConcept<_InputIter>)
  2591.       __glibcpp_function_requires(_ConvertibleConcept<_InputValueType, _OutputValueType>)
  2592.       __glibcpp_function_requires(_LessThanComparableConcept<_OutputValueType>)
  2593.       __glibcpp_function_requires(_LessThanComparableConcept<_InputValueType>)
  2594.  
  2595.       if (__result_first == __result_last) return __result_last;
  2596.       _RandomAccessIter __result_real_last = __result_first;
  2597.       while(__first != __last && __result_real_last != __result_last) {
  2598.     *__result_real_last = *__first;
  2599.     ++__result_real_last;
  2600.     ++__first;
  2601.       }
  2602.       make_heap(__result_first, __result_real_last);
  2603.       while (__first != __last) {
  2604.     if (*__first < *__result_first)
  2605.       __adjust_heap(__result_first, _DistanceType(0),
  2606.             _DistanceType(__result_real_last - __result_first),
  2607.             _InputValueType(*__first));
  2608.     ++__first;
  2609.       }
  2610.       sort_heap(__result_first, __result_real_last);
  2611.       return __result_real_last;
  2612.     }
  2613.  
  2614.   /**
  2615.    *  @brief Copy the smallest elements of a sequence using a predicate for
  2616.    *         comparison.
  2617.    *  @param  first   An input iterator.
  2618.    *  @param  last    Another input iterator.
  2619.    *  @param  result_first   A random-access iterator.
  2620.    *  @param  result_last    Another random-access iterator.
  2621.    *  @param  comp    A comparison functor.
  2622.    *  @return   An iterator indicating the end of the resulting sequence.
  2623.    *
  2624.    *  Copies and sorts the smallest N values from the range @p [first,last)
  2625.    *  to the range beginning at @p result_first, where the number of
  2626.    *  elements to be copied, @p N, is the smaller of @p (last-first) and
  2627.    *  @p (result_last-result_first).
  2628.    *  After the sort if @p i and @j are iterators in the range
  2629.    *  @p [result_first,result_first+N) such that @i precedes @j then
  2630.    *  @p comp(*j,*i) is false.
  2631.    *  The value returned is @p result_first+N.
  2632.   */
  2633.   template<typename _InputIter, typename _RandomAccessIter, typename _Compare>
  2634.     _RandomAccessIter
  2635.     partial_sort_copy(_InputIter __first, _InputIter __last,
  2636.               _RandomAccessIter __result_first,
  2637.               _RandomAccessIter __result_last,
  2638.               _Compare __comp)
  2639.     {
  2640.       typedef typename iterator_traits<_InputIter>::value_type _InputValueType;
  2641.       typedef typename iterator_traits<_RandomAccessIter>::value_type _OutputValueType;
  2642.       typedef typename iterator_traits<_RandomAccessIter>::difference_type _DistanceType;
  2643.  
  2644.       // concept requirements
  2645.       __glibcpp_function_requires(_InputIteratorConcept<_InputIter>)
  2646.       __glibcpp_function_requires(_Mutable_RandomAccessIteratorConcept<_RandomAccessIter>)
  2647.       __glibcpp_function_requires(_ConvertibleConcept<_InputValueType, _OutputValueType>)
  2648.       __glibcpp_function_requires(_BinaryPredicateConcept<_Compare,
  2649.                   _OutputValueType, _OutputValueType>)
  2650.  
  2651.       if (__result_first == __result_last) return __result_last;
  2652.       _RandomAccessIter __result_real_last = __result_first;
  2653.       while(__first != __last && __result_real_last != __result_last) {
  2654.     *__result_real_last = *__first;
  2655.     ++__result_real_last;
  2656.     ++__first;
  2657.       }
  2658.       make_heap(__result_first, __result_real_last, __comp);
  2659.       while (__first != __last) {
  2660.     if (__comp(*__first, *__result_first))
  2661.       __adjust_heap(__result_first, _DistanceType(0),
  2662.             _DistanceType(__result_real_last - __result_first),
  2663.             _InputValueType(*__first),
  2664.             __comp);
  2665.     ++__first;
  2666.       }
  2667.       sort_heap(__result_first, __result_real_last, __comp);
  2668.       return __result_real_last;
  2669.     }
  2670.  
  2671.   /**
  2672.    *  @brief Sort a sequence just enough to find a particular position.
  2673.    *  @param  first   An iterator.
  2674.    *  @param  nth     Another iterator.
  2675.    *  @param  last    Another iterator.
  2676.    *  @return  Nothing.
  2677.    *
  2678.    *  Rearranges the elements in the range @p [first,last) so that @p *nth
  2679.    *  is the same element that would have been in that position had the
  2680.    *  whole sequence been sorted. 
  2681.    *  whole sequence been sorted. The elements either side of @p *nth are
  2682.    *  not completely sorted, but for any iterator @i in the range
  2683.    *  @p [first,nth) and any iterator @j in the range @p [nth,last) it
  2684.    *  holds that @p *j<*i is false.
  2685.   */
  2686.   template<typename _RandomAccessIter>
  2687.     void
  2688.     nth_element(_RandomAccessIter __first,
  2689.         _RandomAccessIter __nth,
  2690.         _RandomAccessIter __last)
  2691.     {
  2692.       typedef typename iterator_traits<_RandomAccessIter>::value_type _ValueType;
  2693.  
  2694.       // concept requirements
  2695.       __glibcpp_function_requires(_Mutable_RandomAccessIteratorConcept<_RandomAccessIter>)
  2696.       __glibcpp_function_requires(_LessThanComparableConcept<_ValueType>)
  2697.  
  2698.       while (__last - __first > 3) {
  2699.     _RandomAccessIter __cut =
  2700.       __unguarded_partition(__first, __last,
  2701.                 _ValueType(__median(*__first,
  2702.                             *(__first + (__last - __first)/2),
  2703.                             *(__last - 1))));
  2704.     if (__cut <= __nth)
  2705.       __first = __cut;
  2706.     else
  2707.       __last = __cut;
  2708.       }
  2709.       __insertion_sort(__first, __last);
  2710.     }
  2711.  
  2712.   /**
  2713.    *  @brief Sort a sequence just enough to find a particular position
  2714.    *         using a predicate for comparison.
  2715.    *  @param  first   An iterator.
  2716.    *  @param  nth     Another iterator.
  2717.    *  @param  last    Another iterator.
  2718.    *  @param  comp    A comparison functor.
  2719.    *  @return  Nothing.
  2720.    *
  2721.    *  Rearranges the elements in the range @p [first,last) so that @p *nth
  2722.    *  is the same element that would have been in that position had the
  2723.    *  whole sequence been sorted. The elements either side of @p *nth are
  2724.    *  not completely sorted, but for any iterator @i in the range
  2725.    *  @p [first,nth) and any iterator @j in the range @p [nth,last) it
  2726.    *  holds that @p comp(*j,*i) is false.
  2727.   */
  2728.   template<typename _RandomAccessIter, typename _Compare>
  2729.     void
  2730.     nth_element(_RandomAccessIter __first,
  2731.         _RandomAccessIter __nth,
  2732.         _RandomAccessIter __last,
  2733.                 _Compare __comp)
  2734.     {
  2735.       typedef typename iterator_traits<_RandomAccessIter>::value_type _ValueType;
  2736.  
  2737.       // concept requirements
  2738.       __glibcpp_function_requires(_Mutable_RandomAccessIteratorConcept<_RandomAccessIter>)
  2739.       __glibcpp_function_requires(_BinaryPredicateConcept<_Compare,
  2740.                   _ValueType, _ValueType>)
  2741.  
  2742.       while (__last - __first > 3) {
  2743.     _RandomAccessIter __cut =
  2744.       __unguarded_partition(__first, __last,
  2745.                 _ValueType(__median(*__first,
  2746.                             *(__first + (__last - __first)/2),
  2747.                             *(__last - 1),
  2748.                             __comp)),
  2749.                 __comp);
  2750.     if (__cut <= __nth)
  2751.       __first = __cut;
  2752.     else
  2753.       __last = __cut;
  2754.       }
  2755.       __insertion_sort(__first, __last, __comp);
  2756.     }
  2757.  
  2758.  
  2759.   /**
  2760.    *  @brief Finds the first position in which @a val could be inserted
  2761.    *         without changing the ordering.
  2762.    *  @param  first   An iterator.
  2763.    *  @param  last    Another iterator.
  2764.    *  @param  val     The search term.
  2765.    *  @return  An iterator pointing to the first element "not less than" @a val.
  2766.    *  @ingroup binarysearch
  2767.   */
  2768.   template<typename _ForwardIter, typename _Tp>
  2769.     _ForwardIter
  2770.     lower_bound(_ForwardIter __first, _ForwardIter __last, const _Tp& __val)
  2771.     {
  2772.       typedef typename iterator_traits<_ForwardIter>::value_type _ValueType;
  2773.       typedef typename iterator_traits<_ForwardIter>::difference_type _DistanceType;
  2774.  
  2775.       // concept requirements
  2776.       // Note that these are slightly stricter than those of the 4-argument
  2777.       // version, defined next.  The difference is in the strictness of the
  2778.       // comparison operations... so for looser checking, define your own
  2779.       // comparison function, as was intended.
  2780.       __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter>)
  2781.       __glibcpp_function_requires(_SameTypeConcept<_Tp, _ValueType>)
  2782.       __glibcpp_function_requires(_LessThanComparableConcept<_Tp>)
  2783.  
  2784.       _DistanceType __len = distance(__first, __last);
  2785.       _DistanceType __half;
  2786.       _ForwardIter __middle;
  2787.  
  2788.       while (__len > 0) {
  2789.     __half = __len >> 1;
  2790.     __middle = __first;
  2791.     advance(__middle, __half);
  2792.     if (*__middle < __val) {
  2793.       __first = __middle;
  2794.       ++__first;
  2795.       __len = __len - __half - 1;
  2796.     }
  2797.     else
  2798.       __len = __half;
  2799.       }
  2800.       return __first;
  2801.     }
  2802.  
  2803.   /**
  2804.    *  @brief Finds the first position in which @a val could be inserted
  2805.    *         without changing the ordering.
  2806.    *  @param  first   An iterator.
  2807.    *  @param  last    Another iterator.
  2808.    *  @param  val     The search term.
  2809.    *  @param  comp    A functor to use for comparisons.
  2810.    *  @return  An iterator pointing to the first element "not less than" @a val.
  2811.    *  @ingroup binarysearch
  2812.    *
  2813.    *  The comparison function should have the same effects on ordering as
  2814.    *  the function used for the initial sort.
  2815.   */
  2816.   template<typename _ForwardIter, typename _Tp, typename _Compare>
  2817.     _ForwardIter
  2818.     lower_bound(_ForwardIter __first, _ForwardIter __last,
  2819.         const _Tp& __val, _Compare __comp)
  2820.     {
  2821.       typedef typename iterator_traits<_ForwardIter>::value_type _ValueType;
  2822.       typedef typename iterator_traits<_ForwardIter>::difference_type _DistanceType;
  2823.  
  2824.       // concept requirements
  2825.       __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter>)
  2826.       __glibcpp_function_requires(_BinaryPredicateConcept<_Compare, _ValueType, _Tp>)
  2827.  
  2828.       _DistanceType __len = distance(__first, __last);
  2829.       _DistanceType __half;
  2830.       _ForwardIter __middle;
  2831.  
  2832.       while (__len > 0) {
  2833.     __half = __len >> 1;
  2834.     __middle = __first;
  2835.     advance(__middle, __half);
  2836.     if (__comp(*__middle, __val)) {
  2837.       __first = __middle;
  2838.       ++__first;
  2839.       __len = __len - __half - 1;
  2840.     }
  2841.     else
  2842.       __len = __half;
  2843.       }
  2844.       return __first;
  2845.     }
  2846.  
  2847.   /**
  2848.    *  @brief Finds the last position in which @a val could be inserted
  2849.    *         without changing the ordering.
  2850.    *  @param  first   An iterator.
  2851.    *  @param  last    Another iterator.
  2852.    *  @param  val     The search term.
  2853.    *  @return  An iterator pointing to the first element greater than @a val.
  2854.    *  @ingroup binarysearch
  2855.   */
  2856.   template<typename _ForwardIter, typename _Tp>
  2857.     _ForwardIter
  2858.     upper_bound(_ForwardIter __first, _ForwardIter __last, const _Tp& __val)
  2859.     {
  2860.       typedef typename iterator_traits<_ForwardIter>::value_type _ValueType;
  2861.       typedef typename iterator_traits<_ForwardIter>::difference_type _DistanceType;
  2862.  
  2863.       // concept requirements
  2864.       // See comments on lower_bound.
  2865.       __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter>)
  2866.       __glibcpp_function_requires(_SameTypeConcept<_Tp, _ValueType>)
  2867.       __glibcpp_function_requires(_LessThanComparableConcept<_Tp>)
  2868.  
  2869.       _DistanceType __len = distance(__first, __last);
  2870.       _DistanceType __half;
  2871.       _ForwardIter __middle;
  2872.  
  2873.       while (__len > 0) {
  2874.     __half = __len >> 1;
  2875.     __middle = __first;
  2876.     advance(__middle, __half);
  2877.     if (__val < *__middle)
  2878.       __len = __half;
  2879.     else {
  2880.       __first = __middle;
  2881.       ++__first;
  2882.       __len = __len - __half - 1;
  2883.     }
  2884.       }
  2885.       return __first;
  2886.     }
  2887.  
  2888.   /**
  2889.    *  @brief Finds the last position in which @a val could be inserted
  2890.    *         without changing the ordering.
  2891.    *  @param  first   An iterator.
  2892.    *  @param  last    Another iterator.
  2893.    *  @param  val     The search term.
  2894.    *  @param  comp    A functor to use for comparisons.
  2895.    *  @return  An iterator pointing to the first element greater than @a val.
  2896.    *  @ingroup binarysearch
  2897.    *
  2898.    *  The comparison function should have the same effects on ordering as
  2899.    *  the function used for the initial sort.
  2900.   */
  2901.   template<typename _ForwardIter, typename _Tp, typename _Compare>
  2902.     _ForwardIter
  2903.     upper_bound(_ForwardIter __first, _ForwardIter __last,
  2904.         const _Tp& __val, _Compare __comp)
  2905.     {
  2906.       typedef typename iterator_traits<_ForwardIter>::value_type _ValueType;
  2907.       typedef typename iterator_traits<_ForwardIter>::difference_type _DistanceType;
  2908.  
  2909.       // concept requirements
  2910.       __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter>)
  2911.       __glibcpp_function_requires(_BinaryPredicateConcept<_Compare, _Tp, _ValueType>)
  2912.  
  2913.       _DistanceType __len = distance(__first, __last);
  2914.       _DistanceType __half;
  2915.       _ForwardIter __middle;
  2916.  
  2917.       while (__len > 0) {
  2918.     __half = __len >> 1;
  2919.     __middle = __first;
  2920.     advance(__middle, __half);
  2921.     if (__comp(__val, *__middle))
  2922.       __len = __half;
  2923.     else {
  2924.       __first = __middle;
  2925.       ++__first;
  2926.       __len = __len - __half - 1;
  2927.     }
  2928.       }
  2929.       return __first;
  2930.     }
  2931.  
  2932.   /**
  2933.    *  @brief Finds the largest subrange in which @a val could be inserted
  2934.    *         at any place in it without changing the ordering.
  2935.    *  @param  first   An iterator.
  2936.    *  @param  last    Another iterator.
  2937.    *  @param  val     The search term.
  2938.    *  @return  An pair of iterators defining the subrange.
  2939.    *  @ingroup binarysearch
  2940.    *
  2941.    *  This is equivalent to
  2942.    *  @code
  2943.    *    std::make_pair(lower_bound(first, last, val),
  2944.    *                   upper_bound(first, last, val))
  2945.    *  @endcode
  2946.    *  but does not actually call those functions.
  2947.   */
  2948.   template<typename _ForwardIter, typename _Tp>
  2949.     pair<_ForwardIter, _ForwardIter>
  2950.     equal_range(_ForwardIter __first, _ForwardIter __last, const _Tp& __val)
  2951.     {
  2952.       typedef typename iterator_traits<_ForwardIter>::value_type _ValueType;
  2953.       typedef typename iterator_traits<_ForwardIter>::difference_type _DistanceType;
  2954.  
  2955.       // concept requirements
  2956.       // See comments on lower_bound.
  2957.       __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter>)
  2958.       __glibcpp_function_requires(_SameTypeConcept<_Tp, _ValueType>)
  2959.       __glibcpp_function_requires(_LessThanComparableConcept<_Tp>)
  2960.  
  2961.       _DistanceType __len = distance(__first, __last);
  2962.       _DistanceType __half;
  2963.       _ForwardIter __middle, __left, __right;
  2964.  
  2965.       while (__len > 0) {
  2966.     __half = __len >> 1;
  2967.     __middle = __first;
  2968.     advance(__middle, __half);
  2969.     if (*__middle < __val) {
  2970.       __first = __middle;
  2971.       ++__first;
  2972.       __len = __len - __half - 1;
  2973.     }
  2974.     else if (__val < *__middle)
  2975.       __len = __half;
  2976.     else {
  2977.       __left = lower_bound(__first, __middle, __val);
  2978.       advance(__first, __len);
  2979.       __right = upper_bound(++__middle, __first, __val);
  2980.       return pair<_ForwardIter, _ForwardIter>(__left, __right);
  2981.     }
  2982.       }
  2983.       return pair<_ForwardIter, _ForwardIter>(__first, __first);
  2984.     }
  2985.  
  2986.   /**
  2987.    *  @brief Finds the largest subrange in which @a val could be inserted
  2988.    *         at any place in it without changing the ordering.
  2989.    *  @param  first   An iterator.
  2990.    *  @param  last    Another iterator.
  2991.    *  @param  val     The search term.
  2992.    *  @param  comp    A functor to use for comparisons.
  2993.    *  @return  An pair of iterators defining the subrange.
  2994.    *  @ingroup binarysearch
  2995.    *
  2996.    *  This is equivalent to
  2997.    *  @code
  2998.    *    std::make_pair(lower_bound(first, last, val, comp),
  2999.    *                   upper_bound(first, last, val, comp))
  3000.    *  @endcode
  3001.    *  but does not actually call those functions.
  3002.   */
  3003.   template<typename _ForwardIter, typename _Tp, typename _Compare>
  3004.     pair<_ForwardIter, _ForwardIter>
  3005.     equal_range(_ForwardIter __first, _ForwardIter __last, const _Tp& __val,
  3006.         _Compare __comp)
  3007.     {
  3008.       typedef typename iterator_traits<_ForwardIter>::value_type _ValueType;
  3009.       typedef typename iterator_traits<_ForwardIter>::difference_type _DistanceType;
  3010.  
  3011.       // concept requirements
  3012.       __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter>)
  3013.       __glibcpp_function_requires(_BinaryPredicateConcept<_Compare, _ValueType, _Tp>)
  3014.       __glibcpp_function_requires(_BinaryPredicateConcept<_Compare, _Tp, _ValueType>)
  3015.  
  3016.       _DistanceType __len = distance(__first, __last);
  3017.       _DistanceType __half;
  3018.       _ForwardIter __middle, __left, __right;
  3019.  
  3020.       while (__len > 0) {
  3021.     __half = __len >> 1;
  3022.     __middle = __first;
  3023.     advance(__middle, __half);
  3024.     if (__comp(*__middle, __val)) {
  3025.       __first = __middle;
  3026.       ++__first;
  3027.       __len = __len - __half - 1;
  3028.     }
  3029.     else if (__comp(__val, *__middle))
  3030.       __len = __half;
  3031.     else {
  3032.       __left = lower_bound(__first, __middle, __val, __comp);
  3033.       advance(__first, __len);
  3034.       __right = upper_bound(++__middle, __first, __val, __comp);
  3035.       return pair<_ForwardIter, _ForwardIter>(__left, __right);
  3036.     }
  3037.       }
  3038.       return pair<_ForwardIter, _ForwardIter>(__first, __first);
  3039.     }
  3040.  
  3041.   /**
  3042.    *  @brief Determines whether an element exists in a range.
  3043.    *  @param  first   An iterator.
  3044.    *  @param  last    Another iterator.
  3045.    *  @param  val     The search term.
  3046.    *  @return  True if @a val (or its equivelent) is in [@a first,@a last ].
  3047.    *  @ingroup binarysearch
  3048.    *
  3049.    *  Note that this does not actually return an iterator to @a val.  For
  3050.    *  that, use std::find or a container's specialized find member functions.
  3051.   */
  3052.   template<typename _ForwardIter, typename _Tp>
  3053.     bool
  3054.     binary_search(_ForwardIter __first, _ForwardIter __last,
  3055.                   const _Tp& __val)
  3056.     {
  3057.       // concept requirements
  3058.       // See comments on lower_bound.
  3059.       __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter>)
  3060.       __glibcpp_function_requires(_SameTypeConcept<_Tp,
  3061.         typename iterator_traits<_ForwardIter>::value_type>)
  3062.       __glibcpp_function_requires(_LessThanComparableConcept<_Tp>)
  3063.  
  3064.       _ForwardIter __i = lower_bound(__first, __last, __val);
  3065.       return __i != __last && !(__val < *__i);
  3066.     }
  3067.  
  3068.   /**
  3069.    *  @brief Determines whether an element exists in a range.
  3070.    *  @param  first   An iterator.
  3071.    *  @param  last    Another iterator.
  3072.    *  @param  val     The search term.
  3073.    *  @param  comp    A functor to use for comparisons.
  3074.    *  @return  True if @a val (or its equivelent) is in [@a first,@a last ].
  3075.    *  @ingroup binarysearch
  3076.    *
  3077.    *  Note that this does not actually return an iterator to @a val.  For
  3078.    *  that, use std::find or a container's specialized find member functions.
  3079.    *
  3080.    *  The comparison function should have the same effects on ordering as
  3081.    *  the function used for the initial sort.
  3082.   */
  3083.   template<typename _ForwardIter, typename _Tp, typename _Compare>
  3084.     bool
  3085.     binary_search(_ForwardIter __first, _ForwardIter __last,
  3086.                   const _Tp& __val, _Compare __comp)
  3087.     {
  3088.       // concept requirements
  3089.       __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter>)
  3090.       __glibcpp_function_requires(_BinaryPredicateConcept<_Compare,
  3091.         typename iterator_traits<_ForwardIter>::value_type, _Tp>)
  3092.       __glibcpp_function_requires(_BinaryPredicateConcept<_Compare, _Tp,
  3093.         typename iterator_traits<_ForwardIter>::value_type>)
  3094.  
  3095.       _ForwardIter __i = lower_bound(__first, __last, __val, __comp);
  3096.       return __i != __last && !__comp(__val, *__i);
  3097.     }
  3098.  
  3099.   /**
  3100.    *  @brief Merges two sorted ranges.
  3101.    *  @param  first1  An iterator.
  3102.    *  @param  first2  Another iterator.
  3103.    *  @param  last1   Another iterator.
  3104.    *  @param  last2   Another iterator.
  3105.    *  @param  result  An iterator pointing to the end of the merged range.
  3106.    *  @return  An iterator pointing to the first element "not less than" @a val.
  3107.    *
  3108.    *  Merges the ranges [first1,last1) and [first2,last2) into the sorted range
  3109.    *  [result, result + (last1-first1) + (last2-first2)).  Both input ranges
  3110.    *  must be sorted, and the output range must not overlap with either of
  3111.    *  the input ranges.  The sort is @e stable, that is, for equivalent
  3112.    *  elements in the two ranges, elements from the first range will always
  3113.    *  come before elements from the second.
  3114.   */
  3115.   template<typename _InputIter1, typename _InputIter2, typename _OutputIter>
  3116.     _OutputIter
  3117.     merge(_InputIter1 __first1, _InputIter1 __last1,
  3118.       _InputIter2 __first2, _InputIter2 __last2,
  3119.       _OutputIter __result)
  3120.     {
  3121.       // concept requirements
  3122.       __glibcpp_function_requires(_InputIteratorConcept<_InputIter1>)
  3123.       __glibcpp_function_requires(_InputIteratorConcept<_InputIter2>)
  3124.       __glibcpp_function_requires(_OutputIteratorConcept<_OutputIter,
  3125.         typename iterator_traits<_InputIter1>::value_type>)
  3126.       __glibcpp_function_requires(_SameTypeConcept<
  3127.         typename iterator_traits<_InputIter1>::value_type,
  3128.         typename iterator_traits<_InputIter2>::value_type>)
  3129.       __glibcpp_function_requires(_LessThanComparableConcept<
  3130.         typename iterator_traits<_InputIter1>::value_type>)
  3131.  
  3132.       while (__first1 != __last1 && __first2 != __last2) {
  3133.     if (*__first2 < *__first1) {
  3134.       *__result = *__first2;
  3135.       ++__first2;
  3136.     }
  3137.     else {
  3138.       *__result = *__first1;
  3139.       ++__first1;
  3140.     }
  3141.     ++__result;
  3142.       }
  3143.       return copy(__first2, __last2, copy(__first1, __last1, __result));
  3144.     }
  3145.  
  3146.   /**
  3147.    *  @brief Merges two sorted ranges.
  3148.    *  @param  first1  An iterator.
  3149.    *  @param  first2  Another iterator.
  3150.    *  @param  last1   Another iterator.
  3151.    *  @param  last2   Another iterator.
  3152.    *  @param  result  An iterator pointing to the end of the merged range.
  3153.    *  @param  comp    A functor to use for comparisons.
  3154.    *  @return  An iterator pointing to the first element "not less than" @a val.
  3155.    *
  3156.    *  Merges the ranges [first1,last1) and [first2,last2) into the sorted range
  3157.    *  [result, result + (last1-first1) + (last2-first2)).  Both input ranges
  3158.    *  must be sorted, and the output range must not overlap with either of
  3159.    *  the input ranges.  The sort is @e stable, that is, for equivalent
  3160.    *  elements in the two ranges, elements from the first range will always
  3161.    *  come before elements from the second.
  3162.    *
  3163.    *  The comparison function should have the same effects on ordering as
  3164.    *  the function used for the initial sort.
  3165.   */
  3166.   template<typename _InputIter1, typename _InputIter2, typename _OutputIter,
  3167.        typename _Compare>
  3168.     _OutputIter
  3169.     merge(_InputIter1 __first1, _InputIter1 __last1,
  3170.       _InputIter2 __first2, _InputIter2 __last2,
  3171.       _OutputIter __result, _Compare __comp)
  3172.     {
  3173.       // concept requirements
  3174.       __glibcpp_function_requires(_InputIteratorConcept<_InputIter1>)
  3175.       __glibcpp_function_requires(_InputIteratorConcept<_InputIter2>)
  3176.       __glibcpp_function_requires(_SameTypeConcept<
  3177.         typename iterator_traits<_InputIter1>::value_type,
  3178.         typename iterator_traits<_InputIter2>::value_type>)
  3179.       __glibcpp_function_requires(_OutputIteratorConcept<_OutputIter,
  3180.         typename iterator_traits<_InputIter1>::value_type>)
  3181.       __glibcpp_function_requires(_BinaryPredicateConcept<_Compare,
  3182.         typename iterator_traits<_InputIter1>::value_type,
  3183.         typename iterator_traits<_InputIter2>::value_type>)
  3184.  
  3185.       while (__first1 != __last1 && __first2 != __last2) {
  3186.     if (__comp(*__first2, *__first1)) {
  3187.       *__result = *__first2;
  3188.       ++__first2;
  3189.     }
  3190.     else {
  3191.       *__result = *__first1;
  3192.       ++__first1;
  3193.     }
  3194.     ++__result;
  3195.       }
  3196.       return copy(__first2, __last2, copy(__first1, __last1, __result));
  3197.     }
  3198.  
  3199.   /**
  3200.    *  @if maint
  3201.    *  This is a helper function for the merge routines.
  3202.    *  @endif
  3203.   */
  3204.   template<typename _BidirectionalIter, typename _Distance>
  3205.     void
  3206.     __merge_without_buffer(_BidirectionalIter __first,
  3207.                _BidirectionalIter __middle,
  3208.                _BidirectionalIter __last,
  3209.                _Distance __len1, _Distance __len2)
  3210.     {
  3211.       if (__len1 == 0 || __len2 == 0)
  3212.     return;
  3213.       if (__len1 + __len2 == 2) {
  3214.     if (*__middle < *__first)
  3215.           iter_swap(__first, __middle);
  3216.     return;
  3217.       }
  3218.       _BidirectionalIter __first_cut = __first;
  3219.       _BidirectionalIter __second_cut = __middle;
  3220.       _Distance __len11 = 0;
  3221.       _Distance __len22 = 0;
  3222.       if (__len1 > __len2) {
  3223.     __len11 = __len1 / 2;
  3224.     advance(__first_cut, __len11);
  3225.     __second_cut = lower_bound(__middle, __last, *__first_cut);
  3226.     __len22 = distance(__middle, __second_cut);
  3227.       }
  3228.       else {
  3229.     __len22 = __len2 / 2;
  3230.     advance(__second_cut, __len22);
  3231.     __first_cut = upper_bound(__first, __middle, *__second_cut);
  3232.     __len11 = distance(__first, __first_cut);
  3233.       }
  3234.       rotate(__first_cut, __middle, __second_cut);
  3235.       _BidirectionalIter __new_middle = __first_cut;
  3236.       advance(__new_middle, distance(__middle, __second_cut));
  3237.       __merge_without_buffer(__first, __first_cut, __new_middle,
  3238.                  __len11, __len22);
  3239.       __merge_without_buffer(__new_middle, __second_cut, __last,
  3240.                  __len1 - __len11, __len2 - __len22);
  3241.     }
  3242.  
  3243.   /**
  3244.    *  @if maint
  3245.    *  This is a helper function for the merge routines.
  3246.    *  @endif
  3247.   */
  3248.   template<typename _BidirectionalIter, typename _Distance, typename _Compare>
  3249.     void
  3250.     __merge_without_buffer(_BidirectionalIter __first,
  3251.                            _BidirectionalIter __middle,
  3252.                _BidirectionalIter __last,
  3253.                _Distance __len1, _Distance __len2,
  3254.                _Compare __comp)
  3255.     {
  3256.       if (__len1 == 0 || __len2 == 0)
  3257.     return;
  3258.       if (__len1 + __len2 == 2) {
  3259.     if (__comp(*__middle, *__first))
  3260.           iter_swap(__first, __middle);
  3261.     return;
  3262.       }
  3263.       _BidirectionalIter __first_cut = __first;
  3264.       _BidirectionalIter __second_cut = __middle;
  3265.       _Distance __len11 = 0;
  3266.       _Distance __len22 = 0;
  3267.       if (__len1 > __len2) {
  3268.     __len11 = __len1 / 2;
  3269.     advance(__first_cut, __len11);
  3270.     __second_cut = lower_bound(__middle, __last, *__first_cut, __comp);
  3271.     __len22 = distance(__middle, __second_cut);
  3272.       }
  3273.       else {
  3274.     __len22 = __len2 / 2;
  3275.     advance(__second_cut, __len22);
  3276.     __first_cut = upper_bound(__first, __middle, *__second_cut, __comp);
  3277.     __len11 = distance(__first, __first_cut);
  3278.       }
  3279.       rotate(__first_cut, __middle, __second_cut);
  3280.       _BidirectionalIter __new_middle = __first_cut;
  3281.       advance(__new_middle, distance(__middle, __second_cut));
  3282.       __merge_without_buffer(__first, __first_cut, __new_middle,
  3283.                  __len11, __len22, __comp);
  3284.       __merge_without_buffer(__new_middle, __second_cut, __last,
  3285.                  __len1 - __len11, __len2 - __len22, __comp);
  3286.     }
  3287.  
  3288.   /**
  3289.    *  @if maint
  3290.    *  This is a helper function for the merge routines.
  3291.    *  @endif
  3292.   */
  3293.   template<typename _BidirectionalIter1, typename _BidirectionalIter2,
  3294.        typename _Distance>
  3295.     _BidirectionalIter1
  3296.     __rotate_adaptive(_BidirectionalIter1 __first,
  3297.               _BidirectionalIter1 __middle,
  3298.               _BidirectionalIter1 __last,
  3299.               _Distance __len1, _Distance __len2,
  3300.               _BidirectionalIter2 __buffer,
  3301.               _Distance __buffer_size)
  3302.     {
  3303.       _BidirectionalIter2 __buffer_end;
  3304.       if (__len1 > __len2 && __len2 <= __buffer_size) {
  3305.     __buffer_end = copy(__middle, __last, __buffer);
  3306.     copy_backward(__first, __middle, __last);
  3307.     return copy(__buffer, __buffer_end, __first);
  3308.       }
  3309.       else if (__len1 <= __buffer_size) {
  3310.     __buffer_end = copy(__first, __middle, __buffer);
  3311.     copy(__middle, __last, __first);
  3312.     return copy_backward(__buffer, __buffer_end, __last);
  3313.       }
  3314.       else {
  3315.     rotate(__first, __middle, __last);
  3316.     advance(__first, distance(__middle, __last));
  3317.     return __first;
  3318.       }
  3319.     }
  3320.  
  3321.   /**
  3322.    *  @if maint
  3323.    *  This is a helper function for the merge routines.
  3324.    *  @endif
  3325.   */
  3326.   template<typename _BidirectionalIter1, typename _BidirectionalIter2,
  3327.        typename _BidirectionalIter3>
  3328.     _BidirectionalIter3
  3329.     __merge_backward(_BidirectionalIter1 __first1, _BidirectionalIter1 __last1,
  3330.              _BidirectionalIter2 __first2, _BidirectionalIter2 __last2,
  3331.              _BidirectionalIter3 __result)
  3332.     {
  3333.       if (__first1 == __last1)
  3334.     return copy_backward(__first2, __last2, __result);
  3335.       if (__first2 == __last2)
  3336.     return copy_backward(__first1, __last1, __result);
  3337.       --__last1;
  3338.       --__last2;
  3339.       while (true) {
  3340.     if (*__last2 < *__last1) {
  3341.       *--__result = *__last1;
  3342.       if (__first1 == __last1)
  3343.         return copy_backward(__first2, ++__last2, __result);
  3344.       --__last1;
  3345.     }
  3346.     else {
  3347.       *--__result = *__last2;
  3348.       if (__first2 == __last2)
  3349.         return copy_backward(__first1, ++__last1, __result);
  3350.       --__last2;
  3351.     }
  3352.       }
  3353.     }
  3354.  
  3355.   /**
  3356.    *  @if maint
  3357.    *  This is a helper function for the merge routines.
  3358.    *  @endif
  3359.   */
  3360.   template<typename _BidirectionalIter1, typename _BidirectionalIter2,
  3361.        typename _BidirectionalIter3, typename _Compare>
  3362.     _BidirectionalIter3
  3363.     __merge_backward(_BidirectionalIter1 __first1, _BidirectionalIter1 __last1,
  3364.              _BidirectionalIter2 __first2, _BidirectionalIter2 __last2,
  3365.              _BidirectionalIter3 __result,
  3366.              _Compare __comp)
  3367.     {
  3368.       if (__first1 == __last1)
  3369.     return copy_backward(__first2, __last2, __result);
  3370.       if (__first2 == __last2)
  3371.     return copy_backward(__first1, __last1, __result);
  3372.       --__last1;
  3373.       --__last2;
  3374.       while (true) {
  3375.     if (__comp(*__last2, *__last1)) {
  3376.       *--__result = *__last1;
  3377.       if (__first1 == __last1)
  3378.         return copy_backward(__first2, ++__last2, __result);
  3379.       --__last1;
  3380.     }
  3381.     else {
  3382.       *--__result = *__last2;
  3383.       if (__first2 == __last2)
  3384.         return copy_backward(__first1, ++__last1, __result);
  3385.       --__last2;
  3386.     }
  3387.       }
  3388.     }
  3389.  
  3390.   /**
  3391.    *  @if maint
  3392.    *  This is a helper function for the merge routines.
  3393.    *  @endif
  3394.   */
  3395.   template<typename _BidirectionalIter, typename _Distance, typename _Pointer>
  3396.     void
  3397.     __merge_adaptive(_BidirectionalIter __first,
  3398.                      _BidirectionalIter __middle,
  3399.              _BidirectionalIter __last,
  3400.              _Distance __len1, _Distance __len2,
  3401.              _Pointer __buffer, _Distance __buffer_size)
  3402.     {
  3403.       if (__len1 <= __len2 && __len1 <= __buffer_size) {
  3404.         _Pointer __buffer_end = copy(__first, __middle, __buffer);
  3405.         merge(__buffer, __buffer_end, __middle, __last, __first);
  3406.       }
  3407.       else if (__len2 <= __buffer_size) {
  3408.         _Pointer __buffer_end = copy(__middle, __last, __buffer);
  3409.         __merge_backward(__first, __middle, __buffer, __buffer_end, __last);
  3410.       }
  3411.       else {
  3412.         _BidirectionalIter __first_cut = __first;
  3413.         _BidirectionalIter __second_cut = __middle;
  3414.         _Distance __len11 = 0;
  3415.         _Distance __len22 = 0;
  3416.         if (__len1 > __len2) {
  3417.           __len11 = __len1 / 2;
  3418.           advance(__first_cut, __len11);
  3419.           __second_cut = lower_bound(__middle, __last, *__first_cut);
  3420.           __len22 = distance(__middle, __second_cut);
  3421.         }
  3422.         else {
  3423.           __len22 = __len2 / 2;
  3424.           advance(__second_cut, __len22);
  3425.           __first_cut = upper_bound(__first, __middle, *__second_cut);
  3426.           __len11 = distance(__first, __first_cut);
  3427.         }
  3428.         _BidirectionalIter __new_middle =
  3429.           __rotate_adaptive(__first_cut, __middle, __second_cut,
  3430.                     __len1 - __len11, __len22, __buffer,
  3431.                     __buffer_size);
  3432.         __merge_adaptive(__first, __first_cut, __new_middle, __len11,
  3433.                  __len22, __buffer, __buffer_size);
  3434.         __merge_adaptive(__new_middle, __second_cut, __last, __len1 - __len11,
  3435.                  __len2 - __len22, __buffer, __buffer_size);
  3436.       }
  3437.     }
  3438.  
  3439.   /**
  3440.    *  @if maint
  3441.    *  This is a helper function for the merge routines.
  3442.    *  @endif
  3443.   */
  3444.   template<typename _BidirectionalIter, typename _Distance, typename _Pointer,
  3445.        typename _Compare>
  3446.     void
  3447.     __merge_adaptive(_BidirectionalIter __first,
  3448.                      _BidirectionalIter __middle,
  3449.              _BidirectionalIter __last,
  3450.              _Distance __len1, _Distance __len2,
  3451.              _Pointer __buffer, _Distance __buffer_size,
  3452.              _Compare __comp)
  3453.     {
  3454.       if (__len1 <= __len2 && __len1 <= __buffer_size) {
  3455.         _Pointer __buffer_end = copy(__first, __middle, __buffer);
  3456.         merge(__buffer, __buffer_end, __middle, __last, __first, __comp);
  3457.       }
  3458.       else if (__len2 <= __buffer_size) {
  3459.         _Pointer __buffer_end = copy(__middle, __last, __buffer);
  3460.         __merge_backward(__first, __middle, __buffer, __buffer_end, __last,
  3461.                          __comp);
  3462.       }
  3463.       else {
  3464.         _BidirectionalIter __first_cut = __first;
  3465.         _BidirectionalIter __second_cut = __middle;
  3466.         _Distance __len11 = 0;
  3467.         _Distance __len22 = 0;
  3468.         if (__len1 > __len2) {
  3469.           __len11 = __len1 / 2;
  3470.           advance(__first_cut, __len11);
  3471.           __second_cut = lower_bound(__middle, __last, *__first_cut, __comp);
  3472.           __len22 = distance(__middle, __second_cut);
  3473.         }
  3474.         else {
  3475.           __len22 = __len2 / 2;
  3476.           advance(__second_cut, __len22);
  3477.           __first_cut = upper_bound(__first, __middle, *__second_cut, __comp);
  3478.           __len11 = distance(__first, __first_cut);
  3479.         }
  3480.         _BidirectionalIter __new_middle =
  3481.           __rotate_adaptive(__first_cut, __middle, __second_cut,
  3482.                     __len1 - __len11, __len22, __buffer,
  3483.                     __buffer_size);
  3484.         __merge_adaptive(__first, __first_cut, __new_middle, __len11,
  3485.                  __len22, __buffer, __buffer_size, __comp);
  3486.         __merge_adaptive(__new_middle, __second_cut, __last, __len1 - __len11,
  3487.                  __len2 - __len22, __buffer, __buffer_size, __comp);
  3488.       }
  3489.     }
  3490.  
  3491.   /**
  3492.    *  @brief Merges two sorted ranges in place.
  3493.    *  @param  first   An iterator.
  3494.    *  @param  middle  Another iterator.
  3495.    *  @param  last    Another iterator.
  3496.    *  @return  Nothing.
  3497.    *
  3498.    *  Merges two sorted and consecutive ranges, [first,middle) and
  3499.    *  [middle,last), and puts the result in [first,last).  The output will
  3500.    *  be sorted.  The sort is @e stable, that is, for equivalent
  3501.    *  elements in the two ranges, elements from the first range will always
  3502.    *  come before elements from the second.
  3503.    *
  3504.    *  If enough additional memory is available, this takes (last-first)-1
  3505.    *  comparisons.  Otherwise an NlogN algorithm is used, where N is
  3506.    *  distance(first,last).
  3507.   */
  3508.   template<typename _BidirectionalIter>
  3509.     void
  3510.     inplace_merge(_BidirectionalIter __first,
  3511.           _BidirectionalIter __middle,
  3512.           _BidirectionalIter __last)
  3513.     {
  3514.       typedef typename iterator_traits<_BidirectionalIter>::value_type
  3515.           _ValueType;
  3516.       typedef typename iterator_traits<_BidirectionalIter>::difference_type
  3517.           _DistanceType;
  3518.  
  3519.       // concept requirements
  3520.       __glibcpp_function_requires(_Mutable_BidirectionalIteratorConcept<
  3521.         _BidirectionalIter>)
  3522.       __glibcpp_function_requires(_LessThanComparableConcept<_ValueType>)
  3523.  
  3524.       if (__first == __middle || __middle == __last)
  3525.     return;
  3526.  
  3527.       _DistanceType __len1 = distance(__first, __middle);
  3528.       _DistanceType __len2 = distance(__middle, __last);
  3529.  
  3530.       _Temporary_buffer<_BidirectionalIter, _ValueType> __buf(__first, __last);
  3531.       if (__buf.begin() == 0)
  3532.     __merge_without_buffer(__first, __middle, __last, __len1, __len2);
  3533.       else
  3534.     __merge_adaptive(__first, __middle, __last, __len1, __len2,
  3535.              __buf.begin(), _DistanceType(__buf.size()));
  3536.     }
  3537.  
  3538.   /**
  3539.    *  @brief Merges two sorted ranges in place.
  3540.    *  @param  first   An iterator.
  3541.    *  @param  middle  Another iterator.
  3542.    *  @param  last    Another iterator.
  3543.    *  @param  comp    A functor to use for comparisons.
  3544.    *  @return  Nothing.
  3545.    *
  3546.    *  Merges two sorted and consecutive ranges, [first,middle) and
  3547.    *  [middle,last), and puts the result in [first,last).  The output will
  3548.    *  be sorted.  The sort is @e stable, that is, for equivalent
  3549.    *  elements in the two ranges, elements from the first range will always
  3550.    *  come before elements from the second.
  3551.    *
  3552.    *  If enough additional memory is available, this takes (last-first)-1
  3553.    *  comparisons.  Otherwise an NlogN algorithm is used, where N is
  3554.    *  distance(first,last).
  3555.    *
  3556.    *  The comparison function should have the same effects on ordering as
  3557.    *  the function used for the initial sort.
  3558.   */
  3559.   template<typename _BidirectionalIter, typename _Compare>
  3560.     void
  3561.     inplace_merge(_BidirectionalIter __first,
  3562.           _BidirectionalIter __middle,
  3563.           _BidirectionalIter __last,
  3564.           _Compare __comp)
  3565.     {
  3566.       typedef typename iterator_traits<_BidirectionalIter>::value_type
  3567.           _ValueType;
  3568.       typedef typename iterator_traits<_BidirectionalIter>::difference_type
  3569.           _DistanceType;
  3570.  
  3571.       // concept requirements
  3572.       __glibcpp_function_requires(_Mutable_BidirectionalIteratorConcept<
  3573.         _BidirectionalIter>)
  3574.       __glibcpp_function_requires(_BinaryPredicateConcept<_Compare,
  3575.         _ValueType, _ValueType>)
  3576.  
  3577.       if (__first == __middle || __middle == __last)
  3578.     return;
  3579.  
  3580.       _DistanceType __len1 = distance(__first, __middle);
  3581.       _DistanceType __len2 = distance(__middle, __last);
  3582.  
  3583.       _Temporary_buffer<_BidirectionalIter, _ValueType> __buf(__first, __last);
  3584.       if (__buf.begin() == 0)
  3585.     __merge_without_buffer(__first, __middle, __last, __len1, __len2, __comp);
  3586.       else
  3587.     __merge_adaptive(__first, __middle, __last, __len1, __len2,
  3588.              __buf.begin(), _DistanceType(__buf.size()),
  3589.              __comp);
  3590.     }
  3591.  
  3592.   // Set algorithms: includes, set_union, set_intersection, set_difference,
  3593.   // set_symmetric_difference.  All of these algorithms have the precondition
  3594.   // that their input ranges are sorted and the postcondition that their output
  3595.   // ranges are sorted.
  3596.  
  3597.   template<typename _InputIter1, typename _InputIter2>
  3598.     bool
  3599.     includes(_InputIter1 __first1, _InputIter1 __last1,
  3600.          _InputIter2 __first2, _InputIter2 __last2)
  3601.     {
  3602.       // concept requirements
  3603.       __glibcpp_function_requires(_InputIteratorConcept<_InputIter1>)
  3604.       __glibcpp_function_requires(_InputIteratorConcept<_InputIter2>)
  3605.       __glibcpp_function_requires(_SameTypeConcept<
  3606.         typename iterator_traits<_InputIter1>::value_type,
  3607.         typename iterator_traits<_InputIter2>::value_type>)
  3608.       __glibcpp_function_requires(_LessThanComparableConcept<
  3609.         typename iterator_traits<_InputIter1>::value_type>)
  3610.  
  3611.       while (__first1 != __last1 && __first2 != __last2)
  3612.     if (*__first2 < *__first1)
  3613.       return false;
  3614.     else if(*__first1 < *__first2)
  3615.       ++__first1;
  3616.     else
  3617.       ++__first1, ++__first2;
  3618.  
  3619.       return __first2 == __last2;
  3620.     }
  3621.  
  3622.   template<typename _InputIter1, typename _InputIter2, typename _Compare>
  3623.     bool
  3624.     includes(_InputIter1 __first1, _InputIter1 __last1,
  3625.          _InputIter2 __first2, _InputIter2 __last2, _Compare __comp)
  3626.     {
  3627.       // concept requirements
  3628.       __glibcpp_function_requires(_InputIteratorConcept<_InputIter1>)
  3629.       __glibcpp_function_requires(_InputIteratorConcept<_InputIter2>)
  3630.       __glibcpp_function_requires(_SameTypeConcept<
  3631.         typename iterator_traits<_InputIter1>::value_type,
  3632.         typename iterator_traits<_InputIter2>::value_type>)
  3633.       __glibcpp_function_requires(_BinaryPredicateConcept<_Compare,
  3634.         typename iterator_traits<_InputIter1>::value_type,
  3635.         typename iterator_traits<_InputIter2>::value_type>)
  3636.  
  3637.       while (__first1 != __last1 && __first2 != __last2)
  3638.     if (__comp(*__first2, *__first1))
  3639.       return false;
  3640.     else if(__comp(*__first1, *__first2))
  3641.       ++__first1;
  3642.     else
  3643.       ++__first1, ++__first2;
  3644.  
  3645.       return __first2 == __last2;
  3646.     }
  3647.  
  3648.   template<typename _InputIter1, typename _InputIter2, typename _OutputIter>
  3649.     _OutputIter
  3650.     set_union(_InputIter1 __first1, _InputIter1 __last1,
  3651.           _InputIter2 __first2, _InputIter2 __last2,
  3652.           _OutputIter __result)
  3653.     {
  3654.       // concept requirements
  3655.       __glibcpp_function_requires(_InputIteratorConcept<_InputIter1>)
  3656.       __glibcpp_function_requires(_InputIteratorConcept<_InputIter2>)
  3657.       __glibcpp_function_requires(_OutputIteratorConcept<_OutputIter,
  3658.         typename iterator_traits<_InputIter1>::value_type>)
  3659.       __glibcpp_function_requires(_SameTypeConcept<
  3660.         typename iterator_traits<_InputIter1>::value_type,
  3661.         typename iterator_traits<_InputIter2>::value_type>)
  3662.       __glibcpp_function_requires(_LessThanComparableConcept<
  3663.         typename iterator_traits<_InputIter1>::value_type>)
  3664.  
  3665.       while (__first1 != __last1 && __first2 != __last2) {
  3666.     if (*__first1 < *__first2) {
  3667.       *__result = *__first1;
  3668.       ++__first1;
  3669.     }
  3670.     else if (*__first2 < *__first1) {
  3671.       *__result = *__first2;
  3672.       ++__first2;
  3673.     }
  3674.     else {
  3675.       *__result = *__first1;
  3676.       ++__first1;
  3677.       ++__first2;
  3678.     }
  3679.     ++__result;
  3680.       }
  3681.       return copy(__first2, __last2, copy(__first1, __last1, __result));
  3682.     }
  3683.  
  3684.   template<typename _InputIter1, typename _InputIter2, typename _OutputIter,
  3685.        typename _Compare>
  3686.     _OutputIter
  3687.     set_union(_InputIter1 __first1, _InputIter1 __last1,
  3688.           _InputIter2 __first2, _InputIter2 __last2,
  3689.           _OutputIter __result, _Compare __comp)
  3690.     {
  3691.       // concept requirements
  3692.       __glibcpp_function_requires(_InputIteratorConcept<_InputIter1>)
  3693.       __glibcpp_function_requires(_InputIteratorConcept<_InputIter2>)
  3694.       __glibcpp_function_requires(_SameTypeConcept<
  3695.         typename iterator_traits<_InputIter1>::value_type,
  3696.         typename iterator_traits<_InputIter2>::value_type>)
  3697.       __glibcpp_function_requires(_OutputIteratorConcept<_OutputIter,
  3698.         typename iterator_traits<_InputIter1>::value_type>)
  3699.       __glibcpp_function_requires(_BinaryPredicateConcept<_Compare,
  3700.         typename iterator_traits<_InputIter1>::value_type,
  3701.         typename iterator_traits<_InputIter2>::value_type>)
  3702.  
  3703.       while (__first1 != __last1 && __first2 != __last2) {
  3704.     if (__comp(*__first1, *__first2)) {
  3705.       *__result = *__first1;
  3706.       ++__first1;
  3707.     }
  3708.     else if (__comp(*__first2, *__first1)) {
  3709.       *__result = *__first2;
  3710.       ++__first2;
  3711.     }
  3712.     else {
  3713.       *__result = *__first1;
  3714.       ++__first1;
  3715.       ++__first2;
  3716.     }
  3717.     ++__result;
  3718.       }
  3719.       return copy(__first2, __last2, copy(__first1, __last1, __result));
  3720.     }
  3721.  
  3722.   template<typename _InputIter1, typename _InputIter2, typename _OutputIter>
  3723.     _OutputIter
  3724.     set_intersection(_InputIter1 __first1, _InputIter1 __last1,
  3725.              _InputIter2 __first2, _InputIter2 __last2,
  3726.              _OutputIter __result)
  3727.     {
  3728.       // concept requirements
  3729.       __glibcpp_function_requires(_InputIteratorConcept<_InputIter1>)
  3730.       __glibcpp_function_requires(_InputIteratorConcept<_InputIter2>)
  3731.       __glibcpp_function_requires(_OutputIteratorConcept<_OutputIter,
  3732.         typename iterator_traits<_InputIter1>::value_type>)
  3733.       __glibcpp_function_requires(_SameTypeConcept<
  3734.         typename iterator_traits<_InputIter1>::value_type,
  3735.         typename iterator_traits<_InputIter2>::value_type>)
  3736.       __glibcpp_function_requires(_LessThanComparableConcept<
  3737.         typename iterator_traits<_InputIter1>::value_type>)
  3738.  
  3739.       while (__first1 != __last1 && __first2 != __last2)
  3740.     if (*__first1 < *__first2)
  3741.       ++__first1;
  3742.     else if (*__first2 < *__first1)
  3743.       ++__first2;
  3744.     else {
  3745.       *__result = *__first1;
  3746.       ++__first1;
  3747.       ++__first2;
  3748.       ++__result;
  3749.     }
  3750.       return __result;
  3751.     }
  3752.  
  3753.   template<typename _InputIter1, typename _InputIter2, typename _OutputIter,
  3754.        typename _Compare>
  3755.     _OutputIter
  3756.     set_intersection(_InputIter1 __first1, _InputIter1 __last1,
  3757.              _InputIter2 __first2, _InputIter2 __last2,
  3758.              _OutputIter __result, _Compare __comp)
  3759.     {
  3760.       // concept requirements
  3761.       __glibcpp_function_requires(_InputIteratorConcept<_InputIter1>)
  3762.       __glibcpp_function_requires(_InputIteratorConcept<_InputIter2>)
  3763.       __glibcpp_function_requires(_SameTypeConcept<
  3764.         typename iterator_traits<_InputIter1>::value_type,
  3765.         typename iterator_traits<_InputIter2>::value_type>)
  3766.       __glibcpp_function_requires(_OutputIteratorConcept<_OutputIter,
  3767.         typename iterator_traits<_InputIter1>::value_type>)
  3768.       __glibcpp_function_requires(_BinaryPredicateConcept<_Compare,
  3769.         typename iterator_traits<_InputIter1>::value_type,
  3770.         typename iterator_traits<_InputIter2>::value_type>)
  3771.  
  3772.       while (__first1 != __last1 && __first2 != __last2)
  3773.     if (__comp(*__first1, *__first2))
  3774.       ++__first1;
  3775.     else if (__comp(*__first2, *__first1))
  3776.       ++__first2;
  3777.     else {
  3778.       *__result = *__first1;
  3779.       ++__first1;
  3780.       ++__first2;
  3781.       ++__result;
  3782.     }
  3783.       return __result;
  3784.     }
  3785.  
  3786.   template<typename _InputIter1, typename _InputIter2, typename _OutputIter>
  3787.     _OutputIter
  3788.     set_difference(_InputIter1 __first1, _InputIter1 __last1,
  3789.            _InputIter2 __first2, _InputIter2 __last2,
  3790.            _OutputIter __result)
  3791.     {
  3792.       // concept requirements
  3793.       __glibcpp_function_requires(_InputIteratorConcept<_InputIter1>)
  3794.       __glibcpp_function_requires(_InputIteratorConcept<_InputIter2>)
  3795.       __glibcpp_function_requires(_OutputIteratorConcept<_OutputIter,
  3796.         typename iterator_traits<_InputIter1>::value_type>)
  3797.       __glibcpp_function_requires(_SameTypeConcept<
  3798.         typename iterator_traits<_InputIter1>::value_type,
  3799.         typename iterator_traits<_InputIter2>::value_type>)
  3800.       __glibcpp_function_requires(_LessThanComparableConcept<
  3801.         typename iterator_traits<_InputIter1>::value_type>)
  3802.  
  3803.       while (__first1 != __last1 && __first2 != __last2)
  3804.     if (*__first1 < *__first2) {
  3805.       *__result = *__first1;
  3806.       ++__first1;
  3807.       ++__result;
  3808.     }
  3809.     else if (*__first2 < *__first1)
  3810.       ++__first2;
  3811.     else {
  3812.       ++__first1;
  3813.       ++__first2;
  3814.     }
  3815.       return copy(__first1, __last1, __result);
  3816.     }
  3817.  
  3818.   template<typename _InputIter1, typename _InputIter2, typename _OutputIter,
  3819.        typename _Compare>
  3820.     _OutputIter
  3821.     set_difference(_InputIter1 __first1, _InputIter1 __last1,
  3822.            _InputIter2 __first2, _InputIter2 __last2,
  3823.            _OutputIter __result, _Compare __comp)
  3824.     {
  3825.       // concept requirements
  3826.       __glibcpp_function_requires(_InputIteratorConcept<_InputIter1>)
  3827.       __glibcpp_function_requires(_InputIteratorConcept<_InputIter2>)
  3828.       __glibcpp_function_requires(_SameTypeConcept<
  3829.         typename iterator_traits<_InputIter1>::value_type,
  3830.         typename iterator_traits<_InputIter2>::value_type>)
  3831.       __glibcpp_function_requires(_OutputIteratorConcept<_OutputIter,
  3832.         typename iterator_traits<_InputIter1>::value_type>)
  3833.       __glibcpp_function_requires(_BinaryPredicateConcept<_Compare,
  3834.         typename iterator_traits<_InputIter1>::value_type,
  3835.         typename iterator_traits<_InputIter2>::value_type>)
  3836.  
  3837.       while (__first1 != __last1 && __first2 != __last2)
  3838.     if (__comp(*__first1, *__first2)) {
  3839.       *__result = *__first1;
  3840.       ++__first1;
  3841.       ++__result;
  3842.     }
  3843.     else if (__comp(*__first2, *__first1))
  3844.       ++__first2;
  3845.     else {
  3846.       ++__first1;
  3847.       ++__first2;
  3848.     }
  3849.       return copy(__first1, __last1, __result);
  3850.     }
  3851.  
  3852.   template<typename _InputIter1, typename _InputIter2, typename _OutputIter>
  3853.     _OutputIter
  3854.     set_symmetric_difference(_InputIter1 __first1, _InputIter1 __last1,
  3855.                  _InputIter2 __first2, _InputIter2 __last2,
  3856.                  _OutputIter __result)
  3857.     {
  3858.       // concept requirements
  3859.       __glibcpp_function_requires(_InputIteratorConcept<_InputIter1>)
  3860.       __glibcpp_function_requires(_InputIteratorConcept<_InputIter2>)
  3861.       __glibcpp_function_requires(_OutputIteratorConcept<_OutputIter,
  3862.         typename iterator_traits<_InputIter1>::value_type>)
  3863.       __glibcpp_function_requires(_SameTypeConcept<
  3864.         typename iterator_traits<_InputIter1>::value_type,
  3865.         typename iterator_traits<_InputIter2>::value_type>)
  3866.       __glibcpp_function_requires(_LessThanComparableConcept<
  3867.         typename iterator_traits<_InputIter1>::value_type>)
  3868.  
  3869.       while (__first1 != __last1 && __first2 != __last2)
  3870.     if (*__first1 < *__first2) {
  3871.       *__result = *__first1;
  3872.       ++__first1;
  3873.       ++__result;
  3874.     }
  3875.     else if (*__first2 < *__first1) {
  3876.       *__result = *__first2;
  3877.       ++__first2;
  3878.       ++__result;
  3879.     }
  3880.     else {
  3881.       ++__first1;
  3882.       ++__first2;
  3883.     }
  3884.       return copy(__first2, __last2, copy(__first1, __last1, __result));
  3885.     }
  3886.  
  3887.   template<typename _InputIter1, typename _InputIter2, typename _OutputIter,
  3888.        typename _Compare>
  3889.     _OutputIter
  3890.     set_symmetric_difference(_InputIter1 __first1, _InputIter1 __last1,
  3891.                  _InputIter2 __first2, _InputIter2 __last2,
  3892.                  _OutputIter __result,
  3893.                  _Compare __comp)
  3894.     {
  3895.       // concept requirements
  3896.       __glibcpp_function_requires(_InputIteratorConcept<_InputIter1>)
  3897.       __glibcpp_function_requires(_InputIteratorConcept<_InputIter2>)
  3898.       __glibcpp_function_requires(_SameTypeConcept<
  3899.         typename iterator_traits<_InputIter1>::value_type,
  3900.         typename iterator_traits<_InputIter2>::value_type>)
  3901.       __glibcpp_function_requires(_OutputIteratorConcept<_OutputIter,
  3902.         typename iterator_traits<_InputIter1>::value_type>)
  3903.       __glibcpp_function_requires(_BinaryPredicateConcept<_Compare,
  3904.         typename iterator_traits<_InputIter1>::value_type,
  3905.         typename iterator_traits<_InputIter2>::value_type>)
  3906.  
  3907.       while (__first1 != __last1 && __first2 != __last2)
  3908.     if (__comp(*__first1, *__first2)) {
  3909.       *__result = *__first1;
  3910.       ++__first1;
  3911.       ++__result;
  3912.     }
  3913.     else if (__comp(*__first2, *__first1)) {
  3914.       *__result = *__first2;
  3915.       ++__first2;
  3916.       ++__result;
  3917.     }
  3918.     else {
  3919.       ++__first1;
  3920.       ++__first2;
  3921.     }
  3922.       return copy(__first2, __last2, copy(__first1, __last1, __result));
  3923.     }
  3924.  
  3925.   // min_element and max_element, with and without an explicitly supplied
  3926.   // comparison function.
  3927.  
  3928.   template<typename _ForwardIter>
  3929.     _ForwardIter
  3930.     max_element(_ForwardIter __first, _ForwardIter __last)
  3931.     {
  3932.       // concept requirements
  3933.       __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter>)
  3934.       __glibcpp_function_requires(_LessThanComparableConcept<
  3935.         typename iterator_traits<_ForwardIter>::value_type>)
  3936.  
  3937.       if (__first == __last) return __first;
  3938.       _ForwardIter __result = __first;
  3939.       while (++__first != __last)
  3940.     if (*__result < *__first)
  3941.       __result = __first;
  3942.       return __result;
  3943.     }
  3944.  
  3945.   template<typename _ForwardIter, typename _Compare>
  3946.     _ForwardIter
  3947.     max_element(_ForwardIter __first, _ForwardIter __last,
  3948.         _Compare __comp)
  3949.     {
  3950.       // concept requirements
  3951.       __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter>)
  3952.       __glibcpp_function_requires(_BinaryPredicateConcept<_Compare,
  3953.         typename iterator_traits<_ForwardIter>::value_type,
  3954.         typename iterator_traits<_ForwardIter>::value_type>)
  3955.  
  3956.       if (__first == __last) return __first;
  3957.       _ForwardIter __result = __first;
  3958.       while (++__first != __last)
  3959.     if (__comp(*__result, *__first)) __result = __first;
  3960.       return __result;
  3961.     }
  3962.  
  3963.   template<typename _ForwardIter>
  3964.     _ForwardIter
  3965.     min_element(_ForwardIter __first, _ForwardIter __last)
  3966.     {
  3967.       // concept requirements
  3968.       __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter>)
  3969.       __glibcpp_function_requires(_LessThanComparableConcept<
  3970.         typename iterator_traits<_ForwardIter>::value_type>)
  3971.  
  3972.       if (__first == __last) return __first;
  3973.       _ForwardIter __result = __first;
  3974.       while (++__first != __last)
  3975.     if (*__first < *__result)
  3976.       __result = __first;
  3977.       return __result;
  3978.     }
  3979.  
  3980.   template<typename _ForwardIter, typename _Compare>
  3981.     _ForwardIter
  3982.     min_element(_ForwardIter __first, _ForwardIter __last,
  3983.         _Compare __comp)
  3984.     {
  3985.       // concept requirements
  3986.       __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter>)
  3987.       __glibcpp_function_requires(_BinaryPredicateConcept<_Compare,
  3988.         typename iterator_traits<_ForwardIter>::value_type,
  3989.         typename iterator_traits<_ForwardIter>::value_type>)
  3990.  
  3991.       if (__first == __last) return __first;
  3992.       _ForwardIter __result = __first;
  3993.       while (++__first != __last)
  3994.     if (__comp(*__first, *__result))
  3995.       __result = __first;
  3996.       return __result;
  3997.     }
  3998.  
  3999.   // next_permutation and prev_permutation, with and without an explicitly
  4000.   // supplied comparison function.
  4001.  
  4002.   template<typename _BidirectionalIter>
  4003.     bool
  4004.     next_permutation(_BidirectionalIter __first, _BidirectionalIter __last)
  4005.     {
  4006.       // concept requirements
  4007.       __glibcpp_function_requires(_BidirectionalIteratorConcept<_BidirectionalIter>)
  4008.       __glibcpp_function_requires(_LessThanComparableConcept<
  4009.         typename iterator_traits<_BidirectionalIter>::value_type>)
  4010.  
  4011.       if (__first == __last)
  4012.     return false;
  4013.       _BidirectionalIter __i = __first;
  4014.       ++__i;
  4015.       if (__i == __last)
  4016.     return false;
  4017.       __i = __last;
  4018.       --__i;
  4019.  
  4020.       for(;;) {
  4021.     _BidirectionalIter __ii = __i;
  4022.     --__i;
  4023.     if (*__i < *__ii) {
  4024.       _BidirectionalIter __j = __last;
  4025.       while (!(*__i < *--__j))
  4026.         {}
  4027.       iter_swap(__i, __j);
  4028.       reverse(__ii, __last);
  4029.       return true;
  4030.     }
  4031.     if (__i == __first) {
  4032.       reverse(__first, __last);
  4033.       return false;
  4034.     }
  4035.       }
  4036.     }
  4037.  
  4038.   template<typename _BidirectionalIter, typename _Compare>
  4039.     bool
  4040.     next_permutation(_BidirectionalIter __first, _BidirectionalIter __last,
  4041.              _Compare __comp)
  4042.     {
  4043.       // concept requirements
  4044.       __glibcpp_function_requires(_BidirectionalIteratorConcept<_BidirectionalIter>)
  4045.       __glibcpp_function_requires(_BinaryPredicateConcept<_Compare,
  4046.         typename iterator_traits<_BidirectionalIter>::value_type,
  4047.         typename iterator_traits<_BidirectionalIter>::value_type>)
  4048.  
  4049.       if (__first == __last)
  4050.     return false;
  4051.       _BidirectionalIter __i = __first;
  4052.       ++__i;
  4053.       if (__i == __last)
  4054.     return false;
  4055.       __i = __last;
  4056.       --__i;
  4057.  
  4058.       for(;;) {
  4059.     _BidirectionalIter __ii = __i;
  4060.     --__i;
  4061.     if (__comp(*__i, *__ii)) {
  4062.       _BidirectionalIter __j = __last;
  4063.       while (!__comp(*__i, *--__j))
  4064.         {}
  4065.       iter_swap(__i, __j);
  4066.       reverse(__ii, __last);
  4067.       return true;
  4068.     }
  4069.     if (__i == __first) {
  4070.       reverse(__first, __last);
  4071.       return false;
  4072.     }
  4073.       }
  4074.     }
  4075.  
  4076.   template<typename _BidirectionalIter>
  4077.     bool
  4078.     prev_permutation(_BidirectionalIter __first, _BidirectionalIter __last)
  4079.     {
  4080.       // concept requirements
  4081.       __glibcpp_function_requires(_BidirectionalIteratorConcept<_BidirectionalIter>)
  4082.       __glibcpp_function_requires(_LessThanComparableConcept<
  4083.         typename iterator_traits<_BidirectionalIter>::value_type>)
  4084.  
  4085.       if (__first == __last)
  4086.     return false;
  4087.       _BidirectionalIter __i = __first;
  4088.       ++__i;
  4089.       if (__i == __last)
  4090.     return false;
  4091.       __i = __last;
  4092.       --__i;
  4093.  
  4094.       for(;;) {
  4095.     _BidirectionalIter __ii = __i;
  4096.     --__i;
  4097.     if (*__ii < *__i) {
  4098.       _BidirectionalIter __j = __last;
  4099.       while (!(*--__j < *__i))
  4100.         {}
  4101.       iter_swap(__i, __j);
  4102.       reverse(__ii, __last);
  4103.       return true;
  4104.     }
  4105.     if (__i == __first) {
  4106.       reverse(__first, __last);
  4107.       return false;
  4108.     }
  4109.       }
  4110.     }
  4111.  
  4112.   template<typename _BidirectionalIter, typename _Compare>
  4113.     bool
  4114.     prev_permutation(_BidirectionalIter __first, _BidirectionalIter __last,
  4115.              _Compare __comp)
  4116.     {
  4117.       // concept requirements
  4118.       __glibcpp_function_requires(_BidirectionalIteratorConcept<_BidirectionalIter>)
  4119.       __glibcpp_function_requires(_BinaryPredicateConcept<_Compare,
  4120.         typename iterator_traits<_BidirectionalIter>::value_type,
  4121.         typename iterator_traits<_BidirectionalIter>::value_type>)
  4122.  
  4123.       if (__first == __last)
  4124.     return false;
  4125.       _BidirectionalIter __i = __first;
  4126.       ++__i;
  4127.       if (__i == __last)
  4128.     return false;
  4129.       __i = __last;
  4130.       --__i;
  4131.  
  4132.       for(;;) {
  4133.     _BidirectionalIter __ii = __i;
  4134.     --__i;
  4135.     if (__comp(*__ii, *__i)) {
  4136.       _BidirectionalIter __j = __last;
  4137.       while (!__comp(*--__j, *__i))
  4138.         {}
  4139.       iter_swap(__i, __j);
  4140.       reverse(__ii, __last);
  4141.       return true;
  4142.     }
  4143.     if (__i == __first) {
  4144.       reverse(__first, __last);
  4145.       return false;
  4146.     }
  4147.       }
  4148.     }
  4149.  
  4150.   // find_first_of, with and without an explicitly supplied comparison function.
  4151.  
  4152.   template<typename _InputIter, typename _ForwardIter>
  4153.     _InputIter
  4154.     find_first_of(_InputIter __first1, _InputIter __last1,
  4155.           _ForwardIter __first2, _ForwardIter __last2)
  4156.     {
  4157.       // concept requirements
  4158.       __glibcpp_function_requires(_InputIteratorConcept<_InputIter>)
  4159.       __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter>)
  4160.       __glibcpp_function_requires(_EqualOpConcept<
  4161.         typename iterator_traits<_InputIter>::value_type,
  4162.         typename iterator_traits<_ForwardIter>::value_type>)
  4163.  
  4164.       for ( ; __first1 != __last1; ++__first1)
  4165.     for (_ForwardIter __iter = __first2; __iter != __last2; ++__iter)
  4166.       if (*__first1 == *__iter)
  4167.         return __first1;
  4168.       return __last1;
  4169.     }
  4170.  
  4171.   template<typename _InputIter, typename _ForwardIter, typename _BinaryPredicate>
  4172.     _InputIter
  4173.     find_first_of(_InputIter __first1, _InputIter __last1,
  4174.           _ForwardIter __first2, _ForwardIter __last2,
  4175.           _BinaryPredicate __comp)
  4176.     {
  4177.       // concept requirements
  4178.       __glibcpp_function_requires(_InputIteratorConcept<_InputIter>)
  4179.       __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter>)
  4180.       __glibcpp_function_requires(_EqualOpConcept<
  4181.         typename iterator_traits<_InputIter>::value_type,
  4182.         typename iterator_traits<_ForwardIter>::value_type>)
  4183.       __glibcpp_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
  4184.         typename iterator_traits<_InputIter>::value_type,
  4185.         typename iterator_traits<_ForwardIter>::value_type>)
  4186.  
  4187.       for ( ; __first1 != __last1; ++__first1)
  4188.     for (_ForwardIter __iter = __first2; __iter != __last2; ++__iter)
  4189.       if (__comp(*__first1, *__iter))
  4190.         return __first1;
  4191.       return __last1;
  4192.     }
  4193.  
  4194.  
  4195.   // find_end, with and without an explicitly supplied comparison function.
  4196.   // Search [first2, last2) as a subsequence in [first1, last1), and return
  4197.   // the *last* possible match.  Note that find_end for bidirectional iterators
  4198.   // is much faster than for forward iterators.
  4199.  
  4200.   // find_end for forward iterators.
  4201.   template<typename _ForwardIter1, typename _ForwardIter2>
  4202.     _ForwardIter1
  4203.     __find_end(_ForwardIter1 __first1, _ForwardIter1 __last1,
  4204.            _ForwardIter2 __first2, _ForwardIter2 __last2,
  4205.            forward_iterator_tag, forward_iterator_tag)
  4206.     {
  4207.       if (__first2 == __last2)
  4208.     return __last1;
  4209.       else {
  4210.     _ForwardIter1 __result = __last1;
  4211.     while (1) {
  4212.       _ForwardIter1 __new_result
  4213.         = search(__first1, __last1, __first2, __last2);
  4214.       if (__new_result == __last1)
  4215.         return __result;
  4216.       else {
  4217.         __result = __new_result;
  4218.         __first1 = __new_result;
  4219.         ++__first1;
  4220.       }
  4221.     }
  4222.       }
  4223.     }
  4224.  
  4225.   template<typename _ForwardIter1, typename _ForwardIter2,
  4226.        typename _BinaryPredicate>
  4227.     _ForwardIter1
  4228.     __find_end(_ForwardIter1 __first1, _ForwardIter1 __last1,
  4229.            _ForwardIter2 __first2, _ForwardIter2 __last2,
  4230.            forward_iterator_tag, forward_iterator_tag,
  4231.            _BinaryPredicate __comp)
  4232.     {
  4233.       if (__first2 == __last2)
  4234.     return __last1;
  4235.       else {
  4236.     _ForwardIter1 __result = __last1;
  4237.     while (1) {
  4238.       _ForwardIter1 __new_result
  4239.         = search(__first1, __last1, __first2, __last2, __comp);
  4240.       if (__new_result == __last1)
  4241.         return __result;
  4242.       else {
  4243.         __result = __new_result;
  4244.         __first1 = __new_result;
  4245.         ++__first1;
  4246.       }
  4247.     }
  4248.       }
  4249.     }
  4250.  
  4251.   // find_end for bidirectional iterators.  Requires partial specialization.
  4252.   template<typename _BidirectionalIter1, typename _BidirectionalIter2>
  4253.     _BidirectionalIter1
  4254.     __find_end(_BidirectionalIter1 __first1, _BidirectionalIter1 __last1,
  4255.            _BidirectionalIter2 __first2, _BidirectionalIter2 __last2,
  4256.            bidirectional_iterator_tag, bidirectional_iterator_tag)
  4257.     {
  4258.       // concept requirements
  4259.       __glibcpp_function_requires(_BidirectionalIteratorConcept<_BidirectionalIter1>)
  4260.       __glibcpp_function_requires(_BidirectionalIteratorConcept<_BidirectionalIter2>)
  4261.  
  4262.       typedef reverse_iterator<_BidirectionalIter1> _RevIter1;
  4263.       typedef reverse_iterator<_BidirectionalIter2> _RevIter2;
  4264.  
  4265.       _RevIter1 __rlast1(__first1);
  4266.       _RevIter2 __rlast2(__first2);
  4267.       _RevIter1 __rresult = search(_RevIter1(__last1), __rlast1,
  4268.                    _RevIter2(__last2), __rlast2);
  4269.  
  4270.       if (__rresult == __rlast1)
  4271.     return __last1;
  4272.       else {
  4273.     _BidirectionalIter1 __result = __rresult.base();
  4274.     advance(__result, -distance(__first2, __last2));
  4275.     return __result;
  4276.       }
  4277.     }
  4278.  
  4279.   template<typename _BidirectionalIter1, typename _BidirectionalIter2,
  4280.        typename _BinaryPredicate>
  4281.     _BidirectionalIter1
  4282.     __find_end(_BidirectionalIter1 __first1, _BidirectionalIter1 __last1,
  4283.            _BidirectionalIter2 __first2, _BidirectionalIter2 __last2,
  4284.            bidirectional_iterator_tag, bidirectional_iterator_tag,
  4285.            _BinaryPredicate __comp)
  4286.     {
  4287.       // concept requirements
  4288.       __glibcpp_function_requires(_BidirectionalIteratorConcept<_BidirectionalIter1>)
  4289.       __glibcpp_function_requires(_BidirectionalIteratorConcept<_BidirectionalIter2>)
  4290.  
  4291.       typedef reverse_iterator<_BidirectionalIter1> _RevIter1;
  4292.       typedef reverse_iterator<_BidirectionalIter2> _RevIter2;
  4293.  
  4294.       _RevIter1 __rlast1(__first1);
  4295.       _RevIter2 __rlast2(__first2);
  4296.       _RevIter1 __rresult = search(_RevIter1(__last1), __rlast1,
  4297.                    _RevIter2(__last2), __rlast2,
  4298.                    __comp);
  4299.  
  4300.       if (__rresult == __rlast1)
  4301.     return __last1;
  4302.       else {
  4303.     _BidirectionalIter1 __result = __rresult.base();
  4304.     advance(__result, -distance(__first2, __last2));
  4305.     return __result;
  4306.       }
  4307.     }
  4308.  
  4309.   // Dispatching functions for find_end.
  4310.  
  4311.   template<typename _ForwardIter1, typename _ForwardIter2>
  4312.     inline _ForwardIter1
  4313.     find_end(_ForwardIter1 __first1, _ForwardIter1 __last1,
  4314.          _ForwardIter2 __first2, _ForwardIter2 __last2)
  4315.     {
  4316.       // concept requirements
  4317.       __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter1>)
  4318.       __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter2>)
  4319.       __glibcpp_function_requires(_EqualOpConcept<
  4320.         typename iterator_traits<_ForwardIter1>::value_type,
  4321.         typename iterator_traits<_ForwardIter2>::value_type>)
  4322.  
  4323.       return __find_end(__first1, __last1, __first2, __last2,
  4324.             __iterator_category(__first1),
  4325.             __iterator_category(__first2));
  4326.     }
  4327.  
  4328.   template<typename _ForwardIter1, typename _ForwardIter2,
  4329.        typename _BinaryPredicate>
  4330.     inline _ForwardIter1
  4331.     find_end(_ForwardIter1 __first1, _ForwardIter1 __last1,
  4332.          _ForwardIter2 __first2, _ForwardIter2 __last2,
  4333.          _BinaryPredicate __comp)
  4334.     {
  4335.       // concept requirements
  4336.       __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter1>)
  4337.       __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter2>)
  4338.       __glibcpp_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
  4339.         typename iterator_traits<_ForwardIter1>::value_type,
  4340.         typename iterator_traits<_ForwardIter2>::value_type>)
  4341.  
  4342.       return __find_end(__first1, __last1, __first2, __last2,
  4343.             __iterator_category(__first1),
  4344.             __iterator_category(__first2),
  4345.             __comp);
  4346.     }
  4347.  
  4348. } // namespace std
  4349.  
  4350. #endif /* __GLIBCPP_INTERNAL_ALGO_H */
  4351.  
  4352.