Subversion Repositories Kolibri OS

Rev

Blame | Last modification | View Log | RSS feed

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