Subversion Repositories Kolibri OS

Rev

Go to most recent revision | Blame | Compare with Previous | Last modification | View Log | RSS feed

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