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