开通博客赚积分
发布资源赚积分
分类

源码开发语言/平台
当前位置：首页 > 源码/资料 > 数值算法/人工智能 > STL > 查看源码
stl_algo.h
资源名称：STL_doc.rar　[点击查看]
上传用户：nizebo
上传日期：2022-05-14
资源大小：882k
文件大小：111k
源码类别：

STL

开发平台：

Visual C++

stl_algo.h：源码内容
  1. /*
  2.  *
  3.  * Copyright (c) 1994
  4.  * Hewlett-Packard Company
  5.  *
  6.  * Permission to use, copy, modify, distribute and sell this software
  7.  * and its documentation for any purpose is hereby granted without fee,
  8.  * provided that the above copyright notice appear in all copies and
  9.  * that both that copyright notice and this permission notice appear
  10.  * in supporting documentation.  Hewlett-Packard Company makes no
  11.  * representations about the suitability of this software for any
  12.  * purpose.  It is provided "as is" without express or implied warranty.
  13.  *
  14.  *
  15.  * Copyright (c) 1996
  16.  * Silicon Graphics Computer Systems, Inc.
  17.  *
  18.  * Permission to use, copy, modify, distribute and sell this software
  19.  * and its documentation for any purpose is hereby granted without fee,
  20.  * provided that the above copyright notice appear in all copies and
  21.  * that both that copyright notice and this permission notice appear
  22.  * in supporting documentation.  Silicon Graphics makes no
  23.  * representations about the suitability of this software for any
  24.  * purpose.  It is provided "as is" without express or implied warranty.
  25.  */
  27. /* NOTE: This is an internal header file, included by other STL headers.
  28.  *   You should not attempt to use it directly.
  29.  */
  31. #ifndef __SGI_STL_INTERNAL_ALGO_H
  32. #define __SGI_STL_INTERNAL_ALGO_H
  34. #include <stl_heap.h>
  36. // See concept_checks.h for the concept-checking macros 
  37. // __STL_REQUIRES, __STL_CONVERTIBLE, etc.
  40. __STL_BEGIN_NAMESPACE
  42. #if defined(__sgi) && !defined(__GNUC__) && (_MIPS_SIM != _MIPS_SIM_ABI32)
  43. #pragma set woff 1209
  44. #endif
  46. // __median (an extension, not present in the C++ standard).
  48. template <class _Tp>
  49. inline const _Tp& __median(const _Tp& __a, const _Tp& __b, const _Tp& __c) {
  50.   __STL_REQUIRES(_Tp, _LessThanComparable);
  51.   if (__a < __b)
  52.     if (__b < __c)
  53.       return __b;
  54.     else if (__a < __c)
  55.       return __c;
  56.     else
  57.       return __a;
  58.   else if (__a < __c)
  59.     return __a;
  60.   else if (__b < __c)
  61.     return __c;
  62.   else
  63.     return __b;
  64. }
  66. template <class _Tp, class _Compare>
  67. inline const _Tp&
  68. __median(const _Tp& __a, const _Tp& __b, const _Tp& __c, _Compare __comp) {
  69.   __STL_BINARY_FUNCTION_CHECK(_Compare, bool, _Tp, _Tp);
  70.   if (__comp(__a, __b))
  71.     if (__comp(__b, __c))
  72.       return __b;
  73.     else if (__comp(__a, __c))
  74.       return __c;
  75.     else
  76.       return __a;
  77.   else if (__comp(__a, __c))
  78.     return __a;
  79.   else if (__comp(__b, __c))
  80.     return __c;
  81.   else
  82.     return __b;
  83. }
  85. // for_each.  Apply a function to every element of a range.
  86. template <class _InputIter, class _Function>
  87. _Function for_each(_InputIter __first, _InputIter __last, _Function __f) {
  88.   __STL_REQUIRES(_InputIter, _InputIterator);
  89.   for ( ; __first != __last; ++__first)
  90.     __f(*__first);
  91.   return __f;
  92. }
  94. // find and find_if.
  96. template <class _InputIter, class _Tp>
  97. inline _InputIter find(_InputIter __first, _InputIter __last,
  98.                        const _Tp& __val,
  99.                        input_iterator_tag)
  100. {
  101.   while (__first != __last && !(*__first == __val))
  102.     ++__first;
  103.   return __first;
  104. }
  106. template <class _InputIter, class _Predicate>
  107. inline _InputIter find_if(_InputIter __first, _InputIter __last,
  108.                           _Predicate __pred,
  109.                           input_iterator_tag)
  110. {
  111.   while (__first != __last && !__pred(*__first))
  112.     ++__first;
  113.   return __first;
  114. }
  116. #ifdef __STL_CLASS_PARTIAL_SPECIALIZATION
  118. template <class _RandomAccessIter, class _Tp>
  119. _RandomAccessIter find(_RandomAccessIter __first, _RandomAccessIter __last,
  120.                        const _Tp& __val,
  121.                        random_access_iterator_tag)
  122. {
  123.   typename iterator_traits<_RandomAccessIter>::difference_type __trip_count
  124.     = (__last - __first) >> 2;
  126.   for ( ; __trip_count > 0 ; --__trip_count) {
  127.     if (*__first == __val) return __first;
  128.     ++__first;
  130.     if (*__first == __val) return __first;
  131.     ++__first;
  133.     if (*__first == __val) return __first;
  134.     ++__first;
  136.     if (*__first == __val) return __first;
  137.     ++__first;
  138.   }
  140.   switch(__last - __first) {
  141.   case 3:
  142.     if (*__first == __val) return __first;
  143.     ++__first;
  144.   case 2:
  145.     if (*__first == __val) return __first;
  146.     ++__first;
  147.   case 1:
  148.     if (*__first == __val) return __first;
  149.     ++__first;
  150.   case 0:
  151.   default:
  152.     return __last;
  153.   }
  154. }
  156. template <class _RandomAccessIter, class _Predicate>
  157. _RandomAccessIter find_if(_RandomAccessIter __first, _RandomAccessIter __last,
  158.                           _Predicate __pred,
  159.                           random_access_iterator_tag)
  160. {
  161.   typename iterator_traits<_RandomAccessIter>::difference_type __trip_count
  162.     = (__last - __first) >> 2;
  164.   for ( ; __trip_count > 0 ; --__trip_count) {
  165.     if (__pred(*__first)) return __first;
  166.     ++__first;
  168.     if (__pred(*__first)) return __first;
  169.     ++__first;
  171.     if (__pred(*__first)) return __first;
  172.     ++__first;
  174.     if (__pred(*__first)) return __first;
  175.     ++__first;
  176.   }
  178.   switch(__last - __first) {
  179.   case 3:
  180.     if (__pred(*__first)) return __first;
  181.     ++__first;
  182.   case 2:
  183.     if (__pred(*__first)) return __first;
  184.     ++__first;
  185.   case 1:
  186.     if (__pred(*__first)) return __first;
  187.     ++__first;
  188.   case 0:
  189.   default:
  190.     return __last;
  191.   }
  192. }
  194. #endif /* __STL_CLASS_PARTIAL_SPECIALIZATION */
  196. template <class _InputIter, class _Tp>
  197. inline _InputIter find(_InputIter __first, _InputIter __last,
  198.                        const _Tp& __val)
  199. {
  200.   __STL_REQUIRES(_InputIter, _InputIterator);
  201.   __STL_REQUIRES_BINARY_OP(_OP_EQUAL, bool, 
  202.             typename iterator_traits<_InputIter>::value_type, _Tp);
  203.   return find(__first, __last, __val, __ITERATOR_CATEGORY(__first));
  204. }
  206. template <class _InputIter, class _Predicate>
  207. inline _InputIter find_if(_InputIter __first, _InputIter __last,
  208.                           _Predicate __pred) {
  209.   __STL_REQUIRES(_InputIter, _InputIterator);
  210.   __STL_UNARY_FUNCTION_CHECK(_Predicate, bool,
  211.           typename iterator_traits<_InputIter>::value_type);
  212.   return find_if(__first, __last, __pred, __ITERATOR_CATEGORY(__first));
  213. }
  215. // adjacent_find.
  217. template <class _ForwardIter>
  218. _ForwardIter adjacent_find(_ForwardIter __first, _ForwardIter __last) {
  219.   __STL_REQUIRES(_ForwardIter, _ForwardIterator);
  220.   __STL_REQUIRES(typename iterator_traits<_ForwardIter>::value_type,
  221.                  _EqualityComparable);
  222.   if (__first == __last)
  223.     return __last;
  224.   _ForwardIter __next = __first;
  225.   while(++__next != __last) {
  226.     if (*__first == *__next)
  227.       return __first;
  228.     __first = __next;
  229.   }
  230.   return __last;
  231. }
  233. template <class _ForwardIter, class _BinaryPredicate>
  234. _ForwardIter adjacent_find(_ForwardIter __first, _ForwardIter __last,
  235.                            _BinaryPredicate __binary_pred) {
  236.   __STL_REQUIRES(_ForwardIter, _ForwardIterator);
  237.   __STL_BINARY_FUNCTION_CHECK(_BinaryPredicate, bool,
  238.           typename iterator_traits<_ForwardIter>::value_type,
  239.           typename iterator_traits<_ForwardIter>::value_type);
  240.   if (__first == __last)
  241.     return __last;
  242.   _ForwardIter __next = __first;
  243.   while(++__next != __last) {
  244.     if (__binary_pred(*__first, *__next))
  245.       return __first;
  246.     __first = __next;
  247.   }
  248.   return __last;
  249. }
  251. // count and count_if.  There are two version of each, one whose return type
  252. // type is void and one (present only if we have partial specialization)
  253. // whose return type is iterator_traits<_InputIter>::difference_type.  The
  254. // C++ standard only has the latter version, but the former, which was present
  255. // in the HP STL, is retained for backward compatibility.
  257. template <class _InputIter, class _Tp, class _Size>
  258. void count(_InputIter __first, _InputIter __last, const _Tp& __value,
  259.            _Size& __n) {
  260.   __STL_REQUIRES(_InputIter, _InputIterator);
  261.   __STL_REQUIRES(typename iterator_traits<_InputIter>::value_type,
  262.                  _EqualityComparable);
  263.   __STL_REQUIRES(_Tp, _EqualityComparable);
  264.   for ( ; __first != __last; ++__first)
  265.     if (*__first == __value)
  266.       ++__n;
  267. }
  269. template <class _InputIter, class _Predicate, class _Size>
  270. void count_if(_InputIter __first, _InputIter __last, _Predicate __pred,
  271.               _Size& __n) {
  272.   __STL_REQUIRES(_InputIter, _InputIterator);
  273.   __STL_UNARY_FUNCTION_CHECK(_Predicate, bool, 
  274.                   typename iterator_traits<_InputIter>::value_type);
  275.   for ( ; __first != __last; ++__first)
  276.     if (__pred(*__first))
  277.       ++__n;
  278. }
  280. #ifdef __STL_CLASS_PARTIAL_SPECIALIZATION
  282. template <class _InputIter, class _Tp>
  283. typename iterator_traits<_InputIter>::difference_type
  284. count(_InputIter __first, _InputIter __last, const _Tp& __value) {
  285.   __STL_REQUIRES(_InputIter, _InputIterator);
  286.   __STL_REQUIRES(typename iterator_traits<_InputIter>::value_type,
  287.                  _EqualityComparable);
  288.   __STL_REQUIRES(_Tp, _EqualityComparable);
  289.   typename iterator_traits<_InputIter>::difference_type __n = 0;
  290.   for ( ; __first != __last; ++__first)
  291.     if (*__first == __value)
  292.       ++__n;
  293.   return __n;
  294. }
  296. template <class _InputIter, class _Predicate>
  297. typename iterator_traits<_InputIter>::difference_type
  298. count_if(_InputIter __first, _InputIter __last, _Predicate __pred) {
  299.   __STL_REQUIRES(_InputIter, _InputIterator);
  300.   __STL_UNARY_FUNCTION_CHECK(_Predicate, bool, 
  301.                   typename iterator_traits<_InputIter>::value_type);
  302.   typename iterator_traits<_InputIter>::difference_type __n = 0;
  303.   for ( ; __first != __last; ++__first)
  304.     if (__pred(*__first))
  305.       ++__n;
  306.   return __n;
  307. }
  310. #endif /* __STL_CLASS_PARTIAL_SPECIALIZATION */
  312. // search.
  314. template <class _ForwardIter1, class _ForwardIter2>
  315. _ForwardIter1 search(_ForwardIter1 __first1, _ForwardIter1 __last1,
  316.                      _ForwardIter2 __first2, _ForwardIter2 __last2) 
  317. {
  318.   __STL_REQUIRES(_ForwardIter1, _ForwardIterator);
  319.   __STL_REQUIRES(_ForwardIter2, _ForwardIterator);
  320.   __STL_REQUIRES_BINARY_OP(_OP_EQUAL, bool,
  321.    typename iterator_traits<_ForwardIter1>::value_type,
  322.    typename iterator_traits<_ForwardIter2>::value_type);
  324.   // Test for empty ranges
  325.   if (__first1 == __last1 || __first2 == __last2)
  326.     return __first1;
  328.   // Test for a pattern of length 1.
  329.   _ForwardIter2 __tmp(__first2);
  330.   ++__tmp;
  331.   if (__tmp == __last2)
  332.     return find(__first1, __last1, *__first2);
  334.   // General case.
  336.   _ForwardIter2 __p1, __p;
  338.   __p1 = __first2; ++__p1;
  340.   _ForwardIter1 __current = __first1;
  342.   while (__first1 != __last1) {
  343.     __first1 = find(__first1, __last1, *__first2);
  344.     if (__first1 == __last1)
  345.       return __last1;
  347.     __p = __p1;
  348.     __current = __first1; 
  349.     if (++__current == __last1)
  350.       return __last1;
  352.     while (*__current == *__p) {
  353.       if (++__p == __last2)
  354.         return __first1;
  355.       if (++__current == __last1)
  356.         return __last1;
  357.     }
  359.     ++__first1;
  360.   }
  361.   return __first1;
  362. }
  364. template <class _ForwardIter1, class _ForwardIter2, class _BinaryPred>
  365. _ForwardIter1 search(_ForwardIter1 __first1, _ForwardIter1 __last1,
  366.                      _ForwardIter2 __first2, _ForwardIter2 __last2,
  367.                      _BinaryPred  __predicate) 
  368. {
  369.   __STL_REQUIRES(_ForwardIter1, _ForwardIterator);
  370.   __STL_REQUIRES(_ForwardIter2, _ForwardIterator);
  371.   __STL_BINARY_FUNCTION_CHECK(_BinaryPred, bool,
  372.    typename iterator_traits<_ForwardIter1>::value_type,
  373.    typename iterator_traits<_ForwardIter2>::value_type);
  375.   // Test for empty ranges
  376.   if (__first1 == __last1 || __first2 == __last2)
  377.     return __first1;
  379.   // Test for a pattern of length 1.
  380.   _ForwardIter2 __tmp(__first2);
  381.   ++__tmp;
  382.   if (__tmp == __last2) {
  383.     while (__first1 != __last1 && !__predicate(*__first1, *__first2))
  384.       ++__first1;
  385.     return __first1;    
  386.   }
  388.   // General case.
  390.   _ForwardIter2 __p1, __p;
  392.   __p1 = __first2; ++__p1;
  394.   _ForwardIter1 __current = __first1;
  396.   while (__first1 != __last1) {
  397.     while (__first1 != __last1) {
  398.       if (__predicate(*__first1, *__first2))
  399.         break;
  400.       ++__first1;
  401.     }
  402.     while (__first1 != __last1 && !__predicate(*__first1, *__first2))
  403.       ++__first1;
  404.     if (__first1 == __last1)
  405.       return __last1;
  407.     __p = __p1;
  408.     __current = __first1; 
  409.     if (++__current == __last1) return __last1;
  411.     while (__predicate(*__current, *__p)) {
  412.       if (++__p == __last2)
  413.         return __first1;
  414.       if (++__current == __last1)
  415.         return __last1;
  416.     }
  418.     ++__first1;
  419.   }
  420.   return __first1;
  421. }
  423. // search_n.  Search for __count consecutive copies of __val.
  425. template <class _ForwardIter, class _Integer, class _Tp>
  426. _ForwardIter search_n(_ForwardIter __first, _ForwardIter __last,
  427.                       _Integer __count, const _Tp& __val) {
  428.   __STL_REQUIRES(_ForwardIter, _ForwardIterator);
  429.   __STL_REQUIRES(typename iterator_traits<_ForwardIter>::value_type,
  430.                  _EqualityComparable);
  431.   __STL_REQUIRES(_Tp, _EqualityComparable);
  433.   if (__count <= 0)
  434.     return __first;
  435.   else {
  436.     __first = find(__first, __last, __val);
  437.     while (__first != __last) {
  438.       _Integer __n = __count - 1;
  439.       _ForwardIter __i = __first;
  440.       ++__i;
  441.       while (__i != __last && __n != 0 && *__i == __val) {
  442.         ++__i;
  443.         --__n;
  444.       }
  445.       if (__n == 0)
  446.         return __first;
  447.       else
  448.         __first = find(__i, __last, __val);
  449.     }
  450.     return __last;
  451.   }
  452. }
  454. template <class _ForwardIter, class _Integer, class _Tp, class _BinaryPred>
  455. _ForwardIter search_n(_ForwardIter __first, _ForwardIter __last,
  456.                       _Integer __count, const _Tp& __val,
  457.                       _BinaryPred __binary_pred) {
  458.   __STL_REQUIRES(_ForwardIter, _ForwardIterator);
  459.   __STL_BINARY_FUNCTION_CHECK(_BinaryPred, bool, 
  460.              typename iterator_traits<_ForwardIter>::value_type, _Tp);
  461.   if (__count <= 0)
  462.     return __first;
  463.   else {
  464.     while (__first != __last) {
  465.       if (__binary_pred(*__first, __val))
  466.         break;
  467.       ++__first;
  468.     }
  469.     while (__first != __last) {
  470.       _Integer __n = __count - 1;
  471.       _ForwardIter __i = __first;
  472.       ++__i;
  473.       while (__i != __last && __n != 0 && __binary_pred(*__i, __val)) {
  474.         ++__i;
  475.         --__n;
  476.       }
  477.       if (__n == 0)
  478.         return __first;
  479.       else {
  480.         while (__i != __last) {
  481.           if (__binary_pred(*__i, __val))
  482.             break;
  483.           ++__i;
  484.         }
  485.         __first = __i;
  486.       }
  487.     }
  488.     return __last;
  489.   }
  490. } 
  492. // swap_ranges
  494. template <class _ForwardIter1, class _ForwardIter2>
  495. _ForwardIter2 swap_ranges(_ForwardIter1 __first1, _ForwardIter1 __last1,
  496.                           _ForwardIter2 __first2) {
  497.   __STL_REQUIRES(_ForwardIter1, _Mutable_ForwardIterator);
  498.   __STL_REQUIRES(_ForwardIter2, _Mutable_ForwardIterator);
  499.   __STL_CONVERTIBLE(typename iterator_traits<_ForwardIter1>::value_type,
  500.                     typename iterator_traits<_ForwardIter2>::value_type);
  501.   __STL_CONVERTIBLE(typename iterator_traits<_ForwardIter2>::value_type,
  502.                     typename iterator_traits<_ForwardIter1>::value_type);
  503.   for ( ; __first1 != __last1; ++__first1, ++__first2)
  504.     iter_swap(__first1, __first2);
  505.   return __first2;
  506. }
  508. // transform
  510. template <class _InputIter, class _OutputIter, class _UnaryOperation>
  511. _OutputIter transform(_InputIter __first, _InputIter __last,
  512.                       _OutputIter __result, _UnaryOperation __opr) {
  513.   __STL_REQUIRES(_InputIter, _InputIterator);
  514.   __STL_REQUIRES(_OutputIter, _OutputIterator);
  516.   for ( ; __first != __last; ++__first, ++__result)
  517.     *__result = __opr(*__first);
  518.   return __result;
  519. }
  521. template <class _InputIter1, class _InputIter2, class _OutputIter,
  522.           class _BinaryOperation>
  523. _OutputIter transform(_InputIter1 __first1, _InputIter1 __last1,
  524.                       _InputIter2 __first2, _OutputIter __result,
  525.                       _BinaryOperation __binary_op) {
  526.   __STL_REQUIRES(_InputIter1, _InputIterator);
  527.   __STL_REQUIRES(_InputIter2, _InputIterator);
  528.   __STL_REQUIRES(_OutputIter, _OutputIterator);
  529.   for ( ; __first1 != __last1; ++__first1, ++__first2, ++__result)
  530.     *__result = __binary_op(*__first1, *__first2);
  531.   return __result;
  532. }
  534. // replace, replace_if, replace_copy, replace_copy_if
  536. template <class _ForwardIter, class _Tp>
  537. void replace(_ForwardIter __first, _ForwardIter __last,
  538.              const _Tp& __old_value, const _Tp& __new_value) {
  539.   __STL_REQUIRES(_ForwardIter, _Mutable_ForwardIterator);
  540.   __STL_REQUIRES_BINARY_OP(_OP_EQUAL, bool,
  541.          typename iterator_traits<_ForwardIter>::value_type, _Tp);
  542.   __STL_CONVERTIBLE(_Tp, typename iterator_traits<_ForwardIter>::value_type);
  543.   for ( ; __first != __last; ++__first)
  544.     if (*__first == __old_value)
  545.       *__first = __new_value;
  546. }
  548. template <class _ForwardIter, class _Predicate, class _Tp>
  549. void replace_if(_ForwardIter __first, _ForwardIter __last,
  550.                 _Predicate __pred, const _Tp& __new_value) {
  551.   __STL_REQUIRES(_ForwardIter, _Mutable_ForwardIterator);
  552.   __STL_CONVERTIBLE(_Tp, typename iterator_traits<_ForwardIter>::value_type);
  553.   __STL_UNARY_FUNCTION_CHECK(_Predicate, bool,
  554.              typename iterator_traits<_ForwardIter>::value_type);
  555.   for ( ; __first != __last; ++__first)
  556.     if (__pred(*__first))
  557.       *__first = __new_value;
  558. }
  560. template <class _InputIter, class _OutputIter, class _Tp>
  561. _OutputIter replace_copy(_InputIter __first, _InputIter __last,
  562.                          _OutputIter __result,
  563.                          const _Tp& __old_value, const _Tp& __new_value) {
  564.   __STL_REQUIRES(_InputIter, _InputIterator);
  565.   __STL_REQUIRES(_OutputIter, _OutputIterator);
  566.   __STL_REQUIRES_BINARY_OP(_OP_EQUAL, bool,
  567.          typename iterator_traits<_InputIter>::value_type, _Tp);
  568.   for ( ; __first != __last; ++__first, ++__result)
  569.     *__result = *__first == __old_value ? __new_value : *__first;
  570.   return __result;
  571. }
  573. template <class _InputIter, class _OutputIter, class _Predicate, class _Tp>
  574. _OutputIter replace_copy_if(_InputIter __first, _InputIter __last,
  575.                             _OutputIter __result,
  576.                             _Predicate __pred, const _Tp& __new_value) {
  577.   __STL_REQUIRES(_InputIter, _InputIterator);
  578.   __STL_REQUIRES(_OutputIter, _OutputIterator);
  579.   __STL_UNARY_FUNCTION_CHECK(_Predicate, bool,
  580.                 typename iterator_traits<_InputIter>::value_type);
  581.   for ( ; __first != __last; ++__first, ++__result)
  582.     *__result = __pred(*__first) ? __new_value : *__first;
  583.   return __result;
  584. }
  586. // generate and generate_n
  588. template <class _ForwardIter, class _Generator>
  589. void generate(_ForwardIter __first, _ForwardIter __last, _Generator __gen) {
  590.   __STL_REQUIRES(_ForwardIter, _ForwardIterator);
  591.   __STL_GENERATOR_CHECK(_Generator, 
  592.           typename iterator_traits<_ForwardIter>::value_type);
  593.   for ( ; __first != __last; ++__first)
  594.     *__first = __gen();
  595. }
  597. template <class _OutputIter, class _Size, class _Generator>
  598. _OutputIter generate_n(_OutputIter __first, _Size __n, _Generator __gen) {
  599.   __STL_REQUIRES(_OutputIter, _OutputIterator);
  600.   for ( ; __n > 0; --__n, ++__first)
  601.     *__first = __gen();
  602.   return __first;
  603. }
  605. // remove, remove_if, remove_copy, remove_copy_if
  607. template <class _InputIter, class _OutputIter, class _Tp>
  608. _OutputIter remove_copy(_InputIter __first, _InputIter __last,
  609.                         _OutputIter __result, const _Tp& __value) {
  610.   __STL_REQUIRES(_InputIter, _InputIterator);
  611.   __STL_REQUIRES(_OutputIter, _OutputIterator);
  612.   __STL_REQUIRES_BINARY_OP(_OP_EQUAL, bool,
  613.        typename iterator_traits<_InputIter>::value_type, _Tp);
  614.   for ( ; __first != __last; ++__first)
  615.     if (!(*__first == __value)) {
  616.       *__result = *__first;
  617.       ++__result;
  618.     }
  619.   return __result;
  620. }
  622. template <class _InputIter, class _OutputIter, class _Predicate>
  623. _OutputIter remove_copy_if(_InputIter __first, _InputIter __last,
  624.                            _OutputIter __result, _Predicate __pred) {
  625.   __STL_REQUIRES(_InputIter, _InputIterator);
  626.   __STL_REQUIRES(_OutputIter, _OutputIterator);
  627.   __STL_UNARY_FUNCTION_CHECK(_Predicate, bool,
  628.              typename iterator_traits<_InputIter>::value_type);
  629.   for ( ; __first != __last; ++__first)
  630.     if (!__pred(*__first)) {
  631.       *__result = *__first;
  632.       ++__result;
  633.     }
  634.   return __result;
  635. }
  637. template <class _ForwardIter, class _Tp>
  638. _ForwardIter remove(_ForwardIter __first, _ForwardIter __last,
  639.                     const _Tp& __value) {
  640.   __STL_REQUIRES(_ForwardIter, _Mutable_ForwardIterator);
  641.   __STL_REQUIRES_BINARY_OP(_OP_EQUAL, bool,
  642.        typename iterator_traits<_ForwardIter>::value_type, _Tp);
  643.   __STL_CONVERTIBLE(_Tp, typename iterator_traits<_ForwardIter>::value_type);
  644.   __first = find(__first, __last, __value);
  645.   _ForwardIter __i = __first;
  646.   return __first == __last ? __first 
  647.                            : remove_copy(++__i, __last, __first, __value);
  648. }
  650. template <class _ForwardIter, class _Predicate>
  651. _ForwardIter remove_if(_ForwardIter __first, _ForwardIter __last,
  652.                        _Predicate __pred) {
  653.   __STL_REQUIRES(_ForwardIter, _Mutable_ForwardIterator);
  654.   __STL_UNARY_FUNCTION_CHECK(_Predicate, bool,
  655.                typename iterator_traits<_ForwardIter>::value_type);
  656.   __first = find_if(__first, __last, __pred);
  657.   _ForwardIter __i = __first;
  658.   return __first == __last ? __first 
  659.                            : remove_copy_if(++__i, __last, __first, __pred);
  660. }
  662. // unique and unique_copy
  664. template <class _InputIter, class _OutputIter, class _Tp>
  665. _OutputIter __unique_copy(_InputIter __first, _InputIter __last,
  666.                           _OutputIter __result, _Tp*) {
  667.   _Tp __value = *__first;
  668.   *__result = __value;
  669.   while (++__first != __last)
  670.     if (!(__value == *__first)) {
  671.       __value = *__first;
  672.       *++__result = __value;
  673.     }
  674.   return ++__result;
  675. }
  677. template <class _InputIter, class _OutputIter>
  678. inline _OutputIter __unique_copy(_InputIter __first, _InputIter __last,
  679.                                  _OutputIter __result, 
  680.                                  output_iterator_tag) {
  681.   return __unique_copy(__first, __last, __result, __VALUE_TYPE(__first));
  682. }
  684. template <class _InputIter, class _ForwardIter>
  685. _ForwardIter __unique_copy(_InputIter __first, _InputIter __last,
  686.                            _ForwardIter __result, forward_iterator_tag) {
  687.   *__result = *__first;
  688.   while (++__first != __last)
  689.     if (!(*__result == *__first))
  690.       *++__result = *__first;
  691.   return ++__result;
  692. }
  694. template <class _InputIter, class _OutputIter>
  695. inline _OutputIter unique_copy(_InputIter __first, _InputIter __last,
  696.                                _OutputIter __result) {
  697.   __STL_REQUIRES(_InputIter, _InputIterator);
  698.   __STL_REQUIRES(_OutputIter, _OutputIterator);
  699.   __STL_REQUIRES(typename iterator_traits<_InputIter>::value_type,
  700.                  _EqualityComparable);
  701.   if (__first == __last) return __result;
  702.   return __unique_copy(__first, __last, __result,
  703.                        __ITERATOR_CATEGORY(__result));
  704. }
  706. template <class _InputIter, class _OutputIter, class _BinaryPredicate,
  707.           class _Tp>
  708. _OutputIter __unique_copy(_InputIter __first, _InputIter __last,
  709.                           _OutputIter __result,
  710.                           _BinaryPredicate __binary_pred, _Tp*) {
  711.   __STL_BINARY_FUNCTION_CHECK(_BinaryPredicate, bool, _Tp, _Tp);
  712.   _Tp __value = *__first;
  713.   *__result = __value;
  714.   while (++__first != __last)
  715.     if (!__binary_pred(__value, *__first)) {
  716.       __value = *__first;
  717.       *++__result = __value;
  718.     }
  719.   return ++__result;
  720. }
  722. template <class _InputIter, class _OutputIter, class _BinaryPredicate>
  723. inline _OutputIter __unique_copy(_InputIter __first, _InputIter __last,
  724.                                  _OutputIter __result,
  725.                                  _BinaryPredicate __binary_pred,
  726.                                  output_iterator_tag) {
  727.   return __unique_copy(__first, __last, __result, __binary_pred,
  728.                        __VALUE_TYPE(__first));
  729. }
  731. template <class _InputIter, class _ForwardIter, class _BinaryPredicate>
  732. _ForwardIter __unique_copy(_InputIter __first, _InputIter __last,
  733.                            _ForwardIter __result, 
  734.                            _BinaryPredicate __binary_pred,
  735.                            forward_iterator_tag) {
  736.   __STL_BINARY_FUNCTION_CHECK(_BinaryPredicate, bool,
  737.      typename iterator_traits<_ForwardIter>::value_type,
  738.      typename iterator_traits<_InputIter>::value_type);
  739.   *__result = *__first;
  740.   while (++__first != __last)
  741.     if (!__binary_pred(*__result, *__first)) *++__result = *__first;
  742.   return ++__result;
  743. }
  745. template <class _InputIter, class _OutputIter, class _BinaryPredicate>
  746. inline _OutputIter unique_copy(_InputIter __first, _InputIter __last,
  747.                                _OutputIter __result,
  748.                                _BinaryPredicate __binary_pred) {
  749.   __STL_REQUIRES(_InputIter, _InputIterator);
  750.   __STL_REQUIRES(_OutputIter, _OutputIterator);
  751.   if (__first == __last) return __result;
  752.   return __unique_copy(__first, __last, __result, __binary_pred,
  753.                        __ITERATOR_CATEGORY(__result));
  754. }
  756. template <class _ForwardIter>
  757. _ForwardIter unique(_ForwardIter __first, _ForwardIter __last) {
  758.   __STL_REQUIRES(_ForwardIter, _Mutable_ForwardIterator);
  759.   __STL_REQUIRES(typename iterator_traits<_ForwardIter>::value_type,
  760.                  _EqualityComparable);
  761.   __first = adjacent_find(__first, __last);
  762.   return unique_copy(__first, __last, __first);
  763. }
  765. template <class _ForwardIter, class _BinaryPredicate>
  766. _ForwardIter unique(_ForwardIter __first, _ForwardIter __last,
  767.                     _BinaryPredicate __binary_pred) {
  768.   __STL_REQUIRES(_ForwardIter, _Mutable_ForwardIterator);
  769.   __STL_BINARY_FUNCTION_CHECK(_BinaryPredicate, bool, 
  770.       typename iterator_traits<_ForwardIter>::value_type,
  771.       typename iterator_traits<_ForwardIter>::value_type);
  772.   __first = adjacent_find(__first, __last, __binary_pred);
  773.   return unique_copy(__first, __last, __first, __binary_pred);
  774. }
  776. // reverse and reverse_copy, and their auxiliary functions
  778. template <class _BidirectionalIter>
  779. void __reverse(_BidirectionalIter __first, _BidirectionalIter __last, 
  780.                bidirectional_iterator_tag) {
  781.   while (true)
  782.     if (__first == __last || __first == --__last)
  783.       return;
  784.     else
  785.       iter_swap(__first++, __last);
  786. }
  788. template <class _RandomAccessIter>
  789. void __reverse(_RandomAccessIter __first, _RandomAccessIter __last,
  790.                random_access_iterator_tag) {
  791.   while (__first < __last)
  792.     iter_swap(__first++, --__last);
  793. }
  795. template <class _BidirectionalIter>
  796. inline void reverse(_BidirectionalIter __first, _BidirectionalIter __last) {
  797.   __STL_REQUIRES(_BidirectionalIter, _Mutable_BidirectionalIterator);
  798.   __reverse(__first, __last, __ITERATOR_CATEGORY(__first));
  799. }
  801. template <class _BidirectionalIter, class _OutputIter>
  802. _OutputIter reverse_copy(_BidirectionalIter __first,
  803.                          _BidirectionalIter __last,
  804.                          _OutputIter __result) {
  805.   __STL_REQUIRES(_BidirectionalIter, _BidirectionalIterator);
  806.   __STL_REQUIRES(_OutputIter, _OutputIterator);
  807.   while (__first != __last) {
  808.     --__last;
  809.     *__result = *__last;
  810.     ++__result;
  811.   }
  812.   return __result;
  813. }
  815. // rotate and rotate_copy, and their auxiliary functions
  817. template <class _EuclideanRingElement>
  818. _EuclideanRingElement __gcd(_EuclideanRingElement __m,
  819.                             _EuclideanRingElement __n)
  820. {
  821.   while (__n != 0) {
  822.     _EuclideanRingElement __t = __m % __n;
  823.     __m = __n;
  824.     __n = __t;
  825.   }
  826.   return __m;
  827. }
  829. template <class _ForwardIter, class _Distance>
  830. _ForwardIter __rotate(_ForwardIter __first,
  831.                       _ForwardIter __middle,
  832.                       _ForwardIter __last,
  833.                       _Distance*,
  834.                       forward_iterator_tag) {
  835.   if (__first == __middle)
  836.     return __last;
  837.   if (__last  == __middle)
  838.     return __first;
  840.   _ForwardIter __first2 = __middle;
  841.   do {
  842.     swap(*__first++, *__first2++);
  843.     if (__first == __middle)
  844.       __middle = __first2;
  845.   } while (__first2 != __last);
  847.   _ForwardIter __new_middle = __first;
  849.   __first2 = __middle;
  851.   while (__first2 != __last) {
  852.     swap (*__first++, *__first2++);
  853.     if (__first == __middle)
  854.       __middle = __first2;
  855.     else if (__first2 == __last)
  856.       __first2 = __middle;
  857.   }
  859.   return __new_middle;
  860. }
  863. template <class _BidirectionalIter, class _Distance>
  864. _BidirectionalIter __rotate(_BidirectionalIter __first,
  865.                             _BidirectionalIter __middle,
  866.                             _BidirectionalIter __last,
  867.                             _Distance*,
  868.                             bidirectional_iterator_tag) {
  869.   __STL_REQUIRES(_BidirectionalIter, _Mutable_BidirectionalIterator);
  870.   if (__first == __middle)
  871.     return __last;
  872.   if (__last  == __middle)
  873.     return __first;
  875.   __reverse(__first,  __middle, bidirectional_iterator_tag());
  876.   __reverse(__middle, __last,   bidirectional_iterator_tag());
  878.   while (__first != __middle && __middle != __last)
  879.     swap (*__first++, *--__last);
  881.   if (__first == __middle) {
  882.     __reverse(__middle, __last,   bidirectional_iterator_tag());
  883.     return __last;
  884.   }
  885.   else {
  886.     __reverse(__first,  __middle, bidirectional_iterator_tag());
  887.     return __first;
  888.   }
  889. }
  891. template <class _RandomAccessIter, class _Distance, class _Tp>
  892. _RandomAccessIter __rotate(_RandomAccessIter __first,
  893.                            _RandomAccessIter __middle,
  894.                            _RandomAccessIter __last,
  895.                            _Distance *, _Tp *) {
  896.   __STL_REQUIRES(_RandomAccessIter, _Mutable_RandomAccessIterator);
  897.   _Distance __n = __last   - __first;
  898.   _Distance __k = __middle - __first;
  899.   _Distance __l = __n - __k;
  900.   _RandomAccessIter __result = __first + (__last - __middle);
  902.   if (__k == 0)
  903.     return __last;
  905.   else if (__k == __l) {
  906.     swap_ranges(__first, __middle, __middle);
  907.     return __result;
  908.   }
  910.   _Distance __d = __gcd(__n, __k);
  912.   for (_Distance __i = 0; __i < __d; __i++) {
  913.     _Tp __tmp = *__first;
  914.     _RandomAccessIter __p = __first;
  916.     if (__k < __l) {
  917.       for (_Distance __j = 0; __j < __l/__d; __j++) {
  918.         if (__p > __first + __l) {
  919.           *__p = *(__p - __l);
  920.           __p -= __l;
  921.         }
  923.         *__p = *(__p + __k);
  924.         __p += __k;
  925.       }
  926.     }
  928.     else {
  929.       for (_Distance __j = 0; __j < __k/__d - 1; __j ++) {
  930.         if (__p < __last - __k) {
  931.           *__p = *(__p + __k);
  932.           __p += __k;
  933.         }
  935.         *__p = * (__p - __l);
  936.         __p -= __l;
  937.       }
  938.     }
  940.     *__p = __tmp;
  941.     ++__first;
  942.   }
  944.   return __result;
  945. }
  947. template <class _ForwardIter>
  948. inline _ForwardIter rotate(_ForwardIter __first, _ForwardIter __middle,
  949.                            _ForwardIter __last) {
  950.   __STL_REQUIRES(_ForwardIter, _Mutable_ForwardIterator);
  951.   return __rotate(__first, __middle, __last,
  952.                   __DISTANCE_TYPE(__first),
  953.                   __ITERATOR_CATEGORY(__first));
  954. }
  956. template <class _ForwardIter, class _OutputIter>
  957. _OutputIter rotate_copy(_ForwardIter __first, _ForwardIter __middle,
  958.                         _ForwardIter __last, _OutputIter __result) {
  959.   __STL_REQUIRES(_ForwardIter, _ForwardIterator);
  960.   __STL_REQUIRES(_OutputIter, _OutputIterator);
  961.   return copy(__first, __middle, copy(__middle, __last, __result));
  962. }
  964. // Return a random number in the range [0, __n).  This function encapsulates
  965. // whether we're using rand (part of the standard C library) or lrand48
  966. // (not standard, but a much better choice whenever it's available).
  968. template <class _Distance>
  969. inline _Distance __random_number(_Distance __n) {
  970. #ifdef __STL_NO_DRAND48
  971.   return rand() % __n;
  972. #else
  973.   return lrand48() % __n;
  974. #endif
  975. }
  977. // random_shuffle
  979. template <class _RandomAccessIter>
  980. inline void random_shuffle(_RandomAccessIter __first,
  981.                            _RandomAccessIter __last) {
  982.   __STL_REQUIRES(_RandomAccessIter, _Mutable_RandomAccessIterator);
  983.   if (__first == __last) return;
  984.   for (_RandomAccessIter __i = __first + 1; __i != __last; ++__i)
  985.     iter_swap(__i, __first + __random_number((__i - __first) + 1));
  986. }
  988. template <class _RandomAccessIter, class _RandomNumberGenerator>
  989. void random_shuffle(_RandomAccessIter __first, _RandomAccessIter __last,
  990.                     _RandomNumberGenerator& __rand) {
  991.   __STL_REQUIRES(_RandomAccessIter, _Mutable_RandomAccessIterator);
  992.   if (__first == __last) return;
  993.   for (_RandomAccessIter __i = __first + 1; __i != __last; ++__i)
  994.     iter_swap(__i, __first + __rand((__i - __first) + 1));
  995. }
  997. // random_sample and random_sample_n (extensions, not part of the standard).
  999. template <class _ForwardIter, class _OutputIter, class _Distance>
  1000. _OutputIter random_sample_n(_ForwardIter __first, _ForwardIter __last,
  1001.                             _OutputIter __out, const _Distance __n)
  1002. {
  1003.   __STL_REQUIRES(_ForwardIter, _ForwardIterator);
  1004.   __STL_REQUIRES(_OutputIter, _OutputIterator);
  1005.   _Distance __remaining = 0;
  1006.   distance(__first, __last, __remaining);
  1007.   _Distance __m = min(__n, __remaining);
  1009.   while (__m > 0) {
  1010.     if (__random_number(__remaining) < __m) {
  1011.       *__out = *__first;
  1012.       ++__out;
  1013.       --__m;
  1014.     }
  1016.     --__remaining;
  1017.     ++__first;
  1018.   }
  1019.   return __out;
  1020. }
  1022. template <class _ForwardIter, class _OutputIter, class _Distance,
  1023.           class _RandomNumberGenerator>
  1024. _OutputIter random_sample_n(_ForwardIter __first, _ForwardIter __last,
  1025.                             _OutputIter __out, const _Distance __n,
  1026.                             _RandomNumberGenerator& __rand)
  1027. {
  1028.   __STL_REQUIRES(_ForwardIter, _ForwardIterator);
  1029.   __STL_REQUIRES(_OutputIter, _OutputIterator);
  1030.   __STL_UNARY_FUNCTION_CHECK(_RandomNumberGenerator, _Distance, _Distance);
  1031.   _Distance __remaining = 0;
  1032.   distance(__first, __last, __remaining);
  1033.   _Distance __m = min(__n, __remaining);
  1035.   while (__m > 0) {
  1036.     if (__rand(__remaining) < __m) {
  1037.       *__out = *__first;
  1038.       ++__out;
  1039.       --__m;
  1040.     }
  1042.     --__remaining;
  1043.     ++__first;
  1044.   }
  1045.   return __out;
  1046. }
  1048. template <class _InputIter, class _RandomAccessIter, class _Distance>
  1049. _RandomAccessIter __random_sample(_InputIter __first, _InputIter __last,
  1050.                                   _RandomAccessIter __out,
  1051.                                   const _Distance __n)
  1052. {
  1053.   _Distance __m = 0;
  1054.   _Distance __t = __n;
  1055.   for ( ; __first != __last && __m < __n; ++__m, ++__first) 
  1056.     __out[__m] = *__first;
  1058.   while (__first != __last) {
  1059.     ++__t;
  1060.     _Distance __M = __random_number(__t);
  1061.     if (__M < __n)
  1062.       __out[__M] = *__first;
  1063.     ++__first;
  1064.   }
  1066.   return __out + __m;
  1067. }
  1069. template <class _InputIter, class _RandomAccessIter,
  1070.           class _RandomNumberGenerator, class _Distance>
  1071. _RandomAccessIter __random_sample(_InputIter __first, _InputIter __last,
  1072.                                   _RandomAccessIter __out,
  1073.                                   _RandomNumberGenerator& __rand,
  1074.                                   const _Distance __n)
  1075. {
  1076.   __STL_UNARY_FUNCTION_CHECK(_RandomNumberGenerator, _Distance, _Distance);
  1077.   _Distance __m = 0;
  1078.   _Distance __t = __n;
  1079.   for ( ; __first != __last && __m < __n; ++__m, ++__first)
  1080.     __out[__m] = *__first;
  1082.   while (__first != __last) {
  1083.     ++__t;
  1084.     _Distance __M = __rand(__t);
  1085.     if (__M < __n)
  1086.       __out[__M] = *__first;
  1087.     ++__first;
  1088.   }
  1090.   return __out + __m;
  1091. }
  1093. template <class _InputIter, class _RandomAccessIter>
  1094. inline _RandomAccessIter
  1095. random_sample(_InputIter __first, _InputIter __last,
  1096.               _RandomAccessIter __out_first, _RandomAccessIter __out_last) 
  1097. {
  1098.   __STL_REQUIRES(_InputIter, _InputIterator);
  1099.   __STL_REQUIRES(_RandomAccessIter, _Mutable_RandomAccessIterator);
  1100.   return __random_sample(__first, __last,
  1101.                          __out_first, __out_last - __out_first);
  1102. }
  1105. template <class _InputIter, class _RandomAccessIter, 
  1106.           class _RandomNumberGenerator>
  1107. inline _RandomAccessIter
  1108. random_sample(_InputIter __first, _InputIter __last,
  1109.               _RandomAccessIter __out_first, _RandomAccessIter __out_last,
  1110.               _RandomNumberGenerator& __rand) 
  1111. {
  1112.   __STL_REQUIRES(_InputIter, _InputIterator);
  1113.   __STL_REQUIRES(_RandomAccessIter, _Mutable_RandomAccessIterator);
  1114.   return __random_sample(__first, __last,
  1115.                          __out_first, __rand,
  1116.                          __out_last - __out_first);
  1117. }
  1119. // partition, stable_partition, and their auxiliary functions
  1121. template <class _ForwardIter, class _Predicate>
  1122. _ForwardIter __partition(_ForwardIter __first,
  1123.          _ForwardIter __last,
  1124.  _Predicate   __pred,
  1125.  forward_iterator_tag) {
  1126.   if (__first == __last) return __first;
  1128.   while (__pred(*__first))
  1129.     if (++__first == __last) return __first;
  1131.   _ForwardIter __next = __first;
  1133.   while (++__next != __last)
  1134.     if (__pred(*__next)) {
  1135.       swap(*__first, *__next);
  1136.       ++__first;
  1137.     }
  1139.   return __first;
  1140. }
  1142. template <class _BidirectionalIter, class _Predicate>
  1143. _BidirectionalIter __partition(_BidirectionalIter __first,
  1144.                                _BidirectionalIter __last,
  1145.        _Predicate __pred,
  1146.        bidirectional_iterator_tag) {
  1147.   while (true) {
  1148.     while (true)
  1149.       if (__first == __last)
  1150.         return __first;
  1151.       else if (__pred(*__first))
  1152.         ++__first;
  1153.       else
  1154.         break;
  1155.     --__last;
  1156.     while (true)
  1157.       if (__first == __last)
  1158.         return __first;
  1159.       else if (!__pred(*__last))
  1160.         --__last;
  1161.       else
  1162.         break;
  1163.     iter_swap(__first, __last);
  1164.     ++__first;
  1165.   }
  1166. }
  1168. template <class _ForwardIter, class _Predicate>
  1169. inline _ForwardIter partition(_ForwardIter __first,
  1170.           _ForwardIter __last,
  1171.       _Predicate   __pred) {
  1172.   __STL_REQUIRES(_ForwardIter, _Mutable_ForwardIterator);
  1173.   __STL_UNARY_FUNCTION_CHECK(_Predicate, bool, 
  1174.         typename iterator_traits<_ForwardIter>::value_type);
  1175.   return __partition(__first, __last, __pred, __ITERATOR_CATEGORY(__first));
  1176. }
  1179. template <class _ForwardIter, class _Predicate, class _Distance>
  1180. _ForwardIter __inplace_stable_partition(_ForwardIter __first,
  1181.                                         _ForwardIter __last,
  1182.                                         _Predicate __pred, _Distance __len) {
  1183.   if (__len == 1)
  1184.     return __pred(*__first) ? __last : __first;
  1185.   _ForwardIter __middle = __first;
  1186.   advance(__middle, __len / 2);
  1187.   return rotate(__inplace_stable_partition(__first, __middle, __pred, 
  1188.                                            __len / 2),
  1189.                 __middle,
  1190.                 __inplace_stable_partition(__middle, __last, __pred,
  1191.                                            __len - __len / 2));
  1192. }
  1194. template <class _ForwardIter, class _Pointer, class _Predicate, 
  1195.           class _Distance>
  1196. _ForwardIter __stable_partition_adaptive(_ForwardIter __first,
  1197.                                          _ForwardIter __last,
  1198.                                          _Predicate __pred, _Distance __len,
  1199.                                          _Pointer __buffer,
  1200.                                          _Distance __buffer_size) 
  1201. {
  1202.   if (__len <= __buffer_size) {
  1203.     _ForwardIter __result1 = __first;
  1204.     _Pointer __result2 = __buffer;
  1205.     for ( ; __first != __last ; ++__first)
  1206.       if (__pred(*__first)) {
  1207.         *__result1 = *__first;
  1208.         ++__result1;
  1209.       }
  1210.       else {
  1211.         *__result2 = *__first;
  1212.         ++__result2;
  1213.       }
  1214.     copy(__buffer, __result2, __result1);
  1215.     return __result1;
  1216.   }
  1217.   else {
  1218.     _ForwardIter __middle = __first;
  1219.     advance(__middle, __len / 2);
  1220.     return rotate(__stable_partition_adaptive(
  1221.                           __first, __middle, __pred,
  1222.                           __len / 2, __buffer, __buffer_size),
  1223.                     __middle,
  1224.                     __stable_partition_adaptive(
  1225.                           __middle, __last, __pred,
  1226.                           __len - __len / 2, __buffer, __buffer_size));
  1227.   }
  1228. }
  1230. template <class _ForwardIter, class _Predicate, class _Tp, class _Distance>
  1231. inline _ForwardIter
  1232. __stable_partition_aux(_ForwardIter __first, _ForwardIter __last, 
  1233.                        _Predicate __pred, _Tp*, _Distance*)
  1234. {
  1235.   _Temporary_buffer<_ForwardIter, _Tp> __buf(__first, __last);
  1236.   if (__buf.size() > 0)
  1237.     return __stable_partition_adaptive(__first, __last, __pred,
  1238.                                        _Distance(__buf.requested_size()),
  1239.                                        __buf.begin(), __buf.size());
  1240.   else
  1241.     return __inplace_stable_partition(__first, __last, __pred, 
  1242.                                       _Distance(__buf.requested_size()));
  1243. }
  1245. template <class _ForwardIter, class _Predicate>
  1246. inline _ForwardIter stable_partition(_ForwardIter __first,
  1247.                                      _ForwardIter __last, 
  1248.                                      _Predicate __pred) {
  1249.   __STL_REQUIRES(_ForwardIter, _Mutable_ForwardIterator);
  1250.   __STL_UNARY_FUNCTION_CHECK(_Predicate, bool,
  1251.       typename iterator_traits<_ForwardIter>::value_type);
  1252.   if (__first == __last)
  1253.     return __first;
  1254.   else
  1255.     return __stable_partition_aux(__first, __last, __pred,
  1256.                                   __VALUE_TYPE(__first),
  1257.                                   __DISTANCE_TYPE(__first));
  1258. }
  1260. template <class _RandomAccessIter, class _Tp>
  1261. _RandomAccessIter __unguarded_partition(_RandomAccessIter __first, 
  1262.                                         _RandomAccessIter __last, 
  1263.                                         _Tp __pivot) 
  1264. {
  1265.   while (true) {
  1266.     while (*__first < __pivot)
  1267.       ++__first;
  1268.     --__last;
  1269.     while (__pivot < *__last)
  1270.       --__last;
  1271.     if (!(__first < __last))
  1272.       return __first;
  1273.     iter_swap(__first, __last);
  1274.     ++__first;
  1275.   }
  1276. }    
  1278. template <class _RandomAccessIter, class _Tp, class _Compare>
  1279. _RandomAccessIter __unguarded_partition(_RandomAccessIter __first, 
  1280.                                         _RandomAccessIter __last, 
  1281.                                         _Tp __pivot, _Compare __comp) 
  1282. {
  1283.   while (true) {
  1284.     while (__comp(*__first, __pivot))
  1285.       ++__first;
  1286.     --__last;
  1287.     while (__comp(__pivot, *__last))
  1288.       --__last;
  1289.     if (!(__first < __last))
  1290.       return __first;
  1291.     iter_swap(__first, __last);
  1292.     ++__first;
  1293.   }
  1294. }
  1296. const int __stl_threshold = 16;
  1298. // sort() and its auxiliary functions. 
  1300. template <class _RandomAccessIter, class _Tp>
  1301. void __unguarded_linear_insert(_RandomAccessIter __last, _Tp __val) {
  1302.   _RandomAccessIter __next = __last;
  1303.   --__next;
  1304.   while (__val < *__next) {
  1305.     *__last = *__next;
  1306.     __last = __next;
  1307.     --__next;
  1308.   }
  1309.   *__last = __val;
  1310. }
  1312. template <class _RandomAccessIter, class _Tp, class _Compare>
  1313. void __unguarded_linear_insert(_RandomAccessIter __last, _Tp __val, 
  1314.                                _Compare __comp) {
  1315.   _RandomAccessIter __next = __last;
  1316.   --__next;  
  1317.   while (__comp(__val, *__next)) {
  1318.     *__last = *__next;
  1319.     __last = __next;
  1320.     --__next;
  1321.   }
  1322.   *__last = __val;
  1323. }
  1325. template <class _RandomAccessIter, class _Tp>
  1326. inline void __linear_insert(_RandomAccessIter __first, 
  1327.                             _RandomAccessIter __last, _Tp*) {
  1328.   _Tp __val = *__last;
  1329.   if (__val < *__first) {
  1330.     copy_backward(__first, __last, __last + 1);
  1331.     *__first = __val;
  1332.   }
  1333.   else
  1334.     __unguarded_linear_insert(__last, __val);
  1335. }
  1337. template <class _RandomAccessIter, class _Tp, class _Compare>
  1338. inline void __linear_insert(_RandomAccessIter __first, 
  1339.                             _RandomAccessIter __last, _Tp*, _Compare __comp) {
  1340.   _Tp __val = *__last;
  1341.   if (__comp(__val, *__first)) {
  1342.     copy_backward(__first, __last, __last + 1);
  1343.     *__first = __val;
  1344.   }
  1345.   else
  1346.     __unguarded_linear_insert(__last, __val, __comp);
  1347. }
  1349. template <class _RandomAccessIter>
  1350. void __insertion_sort(_RandomAccessIter __first, _RandomAccessIter __last) {
  1351.   if (__first == __last) return; 
  1352.   for (_RandomAccessIter __i = __first + 1; __i != __last; ++__i)
  1353.     __linear_insert(__first, __i, __VALUE_TYPE(__first));
  1354. }
  1356. template <class _RandomAccessIter, class _Compare>
  1357. void __insertion_sort(_RandomAccessIter __first,
  1358.                       _RandomAccessIter __last, _Compare __comp) {
  1359.   if (__first == __last) return;
  1360.   for (_RandomAccessIter __i = __first + 1; __i != __last; ++__i)
  1361.     __linear_insert(__first, __i, __VALUE_TYPE(__first), __comp);
  1362. }
  1364. template <class _RandomAccessIter, class _Tp>
  1365. void __unguarded_insertion_sort_aux(_RandomAccessIter __first, 
  1366.                                     _RandomAccessIter __last, _Tp*) {
  1367.   for (_RandomAccessIter __i = __first; __i != __last; ++__i)
  1368.     __unguarded_linear_insert(__i, _Tp(*__i));
  1369. }
  1371. template <class _RandomAccessIter>
  1372. inline void __unguarded_insertion_sort(_RandomAccessIter __first, 
  1373.                                 _RandomAccessIter __last) {
  1374.   __unguarded_insertion_sort_aux(__first, __last, __VALUE_TYPE(__first));
  1375. }
  1377. template <class _RandomAccessIter, class _Tp, class _Compare>
  1378. void __unguarded_insertion_sort_aux(_RandomAccessIter __first, 
  1379.                                     _RandomAccessIter __last,
  1380.                                     _Tp*, _Compare __comp) {
  1381.   for (_RandomAccessIter __i = __first; __i != __last; ++__i)
  1382.     __unguarded_linear_insert(__i, _Tp(*__i), __comp);
  1383. }
  1385. template <class _RandomAccessIter, class _Compare>
  1386. inline void __unguarded_insertion_sort(_RandomAccessIter __first, 
  1387.                                        _RandomAccessIter __last,
  1388.                                        _Compare __comp) {
  1389.   __unguarded_insertion_sort_aux(__first, __last, __VALUE_TYPE(__first),
  1390.                                  __comp);
  1391. }
  1393. template <class _RandomAccessIter>
  1394. void __final_insertion_sort(_RandomAccessIter __first, 
  1395.                             _RandomAccessIter __last) {
  1396.   if (__last - __first > __stl_threshold) {
  1397.     __insertion_sort(__first, __first + __stl_threshold);
  1398.     __unguarded_insertion_sort(__first + __stl_threshold, __last);
  1399.   }
  1400.   else
  1401.     __insertion_sort(__first, __last);
  1402. }
  1404. template <class _RandomAccessIter, class _Compare>
  1405. void __final_insertion_sort(_RandomAccessIter __first, 
  1406.                             _RandomAccessIter __last, _Compare __comp) {
  1407.   if (__last - __first > __stl_threshold) {
  1408.     __insertion_sort(__first, __first + __stl_threshold, __comp);
  1409.     __unguarded_insertion_sort(__first + __stl_threshold, __last, __comp);
  1410.   }
  1411.   else
  1412.     __insertion_sort(__first, __last, __comp);
  1413. }
  1415. template <class _Size>
  1416. inline _Size __lg(_Size __n) {
  1417.   _Size __k;
  1418.   for (__k = 0; __n != 1; __n >>= 1) ++__k;
  1419.   return __k;
  1420. }
  1422. template <class _RandomAccessIter, class _Tp, class _Size>
  1423. void __introsort_loop(_RandomAccessIter __first,
  1424.                       _RandomAccessIter __last, _Tp*,
  1425.                       _Size __depth_limit)
  1426. {
  1427.   while (__last - __first > __stl_threshold) {
  1428.     if (__depth_limit == 0) {
  1429.       partial_sort(__first, __last, __last);
  1430.       return;
  1431.     }
  1432.     --__depth_limit;
  1433.     _RandomAccessIter __cut =
  1434.       __unguarded_partition(__first, __last,
  1435.                             _Tp(__median(*__first,
  1436.                                          *(__first + (__last - __first)/2),
  1437.                                          *(__last - 1))));
  1438.     __introsort_loop(__cut, __last, (_Tp*) 0, __depth_limit);
  1439.     __last = __cut;
  1440.   }
  1441. }
  1443. template <class _RandomAccessIter, class _Tp, class _Size, class _Compare>
  1444. void __introsort_loop(_RandomAccessIter __first,
  1445.                       _RandomAccessIter __last, _Tp*,
  1446.                       _Size __depth_limit, _Compare __comp)
  1447. {
  1448.   while (__last - __first > __stl_threshold) {
  1449.     if (__depth_limit == 0) {
  1450.       partial_sort(__first, __last, __last, __comp);
  1451.       return;
  1452.     }
  1453.     --__depth_limit;
  1454.     _RandomAccessIter __cut =
  1455.       __unguarded_partition(__first, __last,
  1456.                             _Tp(__median(*__first,
  1457.                                          *(__first + (__last - __first)/2),
  1458.                                          *(__last - 1), __comp)),
  1459.        __comp);
  1460.     __introsort_loop(__cut, __last, (_Tp*) 0, __depth_limit, __comp);
  1461.     __last = __cut;
  1462.   }
  1463. }
  1465. template <class _RandomAccessIter>
  1466. inline void sort(_RandomAccessIter __first, _RandomAccessIter __last) {
  1467.   __STL_REQUIRES(_RandomAccessIter, _Mutable_RandomAccessIterator);
  1468.   __STL_REQUIRES(typename iterator_traits<_RandomAccessIter>::value_type,
  1469.                  _LessThanComparable);
  1470.   if (__first != __last) {
  1471.     __introsort_loop(__first, __last,
  1472.                      __VALUE_TYPE(__first),
  1473.                      __lg(__last - __first) * 2);
  1474.     __final_insertion_sort(__first, __last);
  1475.   }
  1476. }
  1478. template <class _RandomAccessIter, class _Compare>
  1479. inline void sort(_RandomAccessIter __first, _RandomAccessIter __last,
  1480.                  _Compare __comp) {
  1481.   __STL_REQUIRES(_RandomAccessIter, _Mutable_RandomAccessIterator);
  1482.   __STL_BINARY_FUNCTION_CHECK(_Compare, bool,
  1483.        typename iterator_traits<_RandomAccessIter>::value_type,
  1484.        typename iterator_traits<_RandomAccessIter>::value_type);
  1485.   if (__first != __last) {
  1486.     __introsort_loop(__first, __last,
  1487.                      __VALUE_TYPE(__first),
  1488.                      __lg(__last - __first) * 2,
  1489.                      __comp);
  1490.     __final_insertion_sort(__first, __last, __comp);
  1491.   }
  1492. }
  1494. // stable_sort() and its auxiliary functions.
  1496. template <class _RandomAccessIter>
  1497. void __inplace_stable_sort(_RandomAccessIter __first,
  1498.                            _RandomAccessIter __last) {
  1499.   if (__last - __first < 15) {
  1500.     __insertion_sort(__first, __last);
  1501.     return;
  1502.   }
  1503.   _RandomAccessIter __middle = __first + (__last - __first) / 2;
  1504.   __inplace_stable_sort(__first, __middle);
  1505.   __inplace_stable_sort(__middle, __last);
  1506.   __merge_without_buffer(__first, __middle, __last,
  1507.                          __middle - __first,
  1508.                          __last - __middle);
  1509. }
  1511. template <class _RandomAccessIter, class _Compare>
  1512. void __inplace_stable_sort(_RandomAccessIter __first,
  1513.                            _RandomAccessIter __last, _Compare __comp) {
  1514.   if (__last - __first < 15) {
  1515.     __insertion_sort(__first, __last, __comp);
  1516.     return;
  1517.   }
  1518.   _RandomAccessIter __middle = __first + (__last - __first) / 2;
  1519.   __inplace_stable_sort(__first, __middle, __comp);
  1520.   __inplace_stable_sort(__middle, __last, __comp);
  1521.   __merge_without_buffer(__first, __middle, __last,
  1522.                          __middle - __first,
  1523.                          __last - __middle,
  1524.                          __comp);
  1525. }
  1527. template <class _RandomAccessIter1, class _RandomAccessIter2,
  1528.           class _Distance>
  1529. void __merge_sort_loop(_RandomAccessIter1 __first,
  1530.                        _RandomAccessIter1 __last, 
  1531.                        _RandomAccessIter2 __result, _Distance __step_size) {
  1532.   _Distance __two_step = 2 * __step_size;
  1534.   while (__last - __first >= __two_step) {
  1535.     __result = merge(__first, __first + __step_size,
  1536.                      __first + __step_size, __first + __two_step,
  1537.                      __result);
  1538.     __first += __two_step;
  1539.   }
  1541.   __step_size = min(_Distance(__last - __first), __step_size);
  1542.   merge(__first, __first + __step_size, __first + __step_size, __last,
  1543.         __result);
  1544. }
  1546. template <class _RandomAccessIter1, class _RandomAccessIter2,
  1547.           class _Distance, class _Compare>
  1548. void __merge_sort_loop(_RandomAccessIter1 __first,
  1549.                        _RandomAccessIter1 __last, 
  1550.                        _RandomAccessIter2 __result, _Distance __step_size,
  1551.                        _Compare __comp) {
  1552.   _Distance __two_step = 2 * __step_size;
  1554.   while (__last - __first >= __two_step) {
  1555.     __result = merge(__first, __first + __step_size,
  1556.                      __first + __step_size, __first + __two_step,
  1557.                      __result,
  1558.                      __comp);
  1559.     __first += __two_step;
  1560.   }
  1561.   __step_size = min(_Distance(__last - __first), __step_size);
  1563.   merge(__first, __first + __step_size,
  1564.         __first + __step_size, __last,
  1565.         __result,
  1566.         __comp);
  1567. }
  1569. const int __stl_chunk_size = 7;
  1570.         
  1571. template <class _RandomAccessIter, class _Distance>
  1572. void __chunk_insertion_sort(_RandomAccessIter __first, 
  1573.                             _RandomAccessIter __last, _Distance __chunk_size)
  1574. {
  1575.   while (__last - __first >= __chunk_size) {
  1576.     __insertion_sort(__first, __first + __chunk_size);
  1577.     __first += __chunk_size;
  1578.   }
  1579.   __insertion_sort(__first, __last);
  1580. }
  1582. template <class _RandomAccessIter, class _Distance, class _Compare>
  1583. void __chunk_insertion_sort(_RandomAccessIter __first, 
  1584.                             _RandomAccessIter __last,
  1585.                             _Distance __chunk_size, _Compare __comp)
  1586. {
  1587.   while (__last - __first >= __chunk_size) {
  1588.     __insertion_sort(__first, __first + __chunk_size, __comp);
  1589.     __first += __chunk_size;
  1590.   }
  1591.   __insertion_sort(__first, __last, __comp);
  1592. }
  1594. template <class _RandomAccessIter, class _Pointer, class _Distance>
  1595. void __merge_sort_with_buffer(_RandomAccessIter __first, 
  1596.                               _RandomAccessIter __last,
  1597.                               _Pointer __buffer, _Distance*) {
  1598.   _Distance __len = __last - __first;
  1599.   _Pointer __buffer_last = __buffer + __len;
  1601.   _Distance __step_size = __stl_chunk_size;
  1602.   __chunk_insertion_sort(__first, __last, __step_size);
  1604.   while (__step_size < __len) {
  1605.     __merge_sort_loop(__first, __last, __buffer, __step_size);
  1606.     __step_size *= 2;
  1607.     __merge_sort_loop(__buffer, __buffer_last, __first, __step_size);
  1608.     __step_size *= 2;
  1609.   }
  1610. }
  1612. template <class _RandomAccessIter, class _Pointer, class _Distance,
  1613.           class _Compare>
  1614. void __merge_sort_with_buffer(_RandomAccessIter __first, 
  1615.                               _RandomAccessIter __last, _Pointer __buffer,
  1616.                               _Distance*, _Compare __comp) {
  1617.   _Distance __len = __last - __first;
  1618.   _Pointer __buffer_last = __buffer + __len;
  1620.   _Distance __step_size = __stl_chunk_size;
  1621.   __chunk_insertion_sort(__first, __last, __step_size, __comp);
  1623.   while (__step_size < __len) {
  1624.     __merge_sort_loop(__first, __last, __buffer, __step_size, __comp);
  1625.     __step_size *= 2;
  1626.     __merge_sort_loop(__buffer, __buffer_last, __first, __step_size, __comp);
  1627.     __step_size *= 2;
  1628.   }
  1629. }
  1631. template <class _RandomAccessIter, class _Pointer, class _Distance>
  1632. void __stable_sort_adaptive(_RandomAccessIter __first, 
  1633.                             _RandomAccessIter __last, _Pointer __buffer,
  1634.                             _Distance __buffer_size) {
  1635.   _Distance __len = (__last - __first + 1) / 2;
  1636.   _RandomAccessIter __middle = __first + __len;
  1637.   if (__len > __buffer_size) {
  1638.     __stable_sort_adaptive(__first, __middle, __buffer, __buffer_size);
  1639.     __stable_sort_adaptive(__middle, __last, __buffer, __buffer_size);
  1640.   }
  1641.   else {
  1642.     __merge_sort_with_buffer(__first, __middle, __buffer, (_Distance*)0);
  1643.     __merge_sort_with_buffer(__middle, __last, __buffer, (_Distance*)0);
  1644.   }
  1645.   __merge_adaptive(__first, __middle, __last, _Distance(__middle - __first), 
  1646.                    _Distance(__last - __middle), __buffer, __buffer_size);
  1647. }
  1649. template <class _RandomAccessIter, class _Pointer, class _Distance, 
  1650.           class _Compare>
  1651. void __stable_sort_adaptive(_RandomAccessIter __first, 
  1652.                             _RandomAccessIter __last, _Pointer __buffer,
  1653.                             _Distance __buffer_size, _Compare __comp) {
  1654.   _Distance __len = (__last - __first + 1) / 2;
  1655.   _RandomAccessIter __middle = __first + __len;
  1656.   if (__len > __buffer_size) {
  1657.     __stable_sort_adaptive(__first, __middle, __buffer, __buffer_size, 
  1658.                            __comp);
  1659.     __stable_sort_adaptive(__middle, __last, __buffer, __buffer_size, 
  1660.                            __comp);
  1661.   }
  1662.   else {
  1663.     __merge_sort_with_buffer(__first, __middle, __buffer, (_Distance*)0,
  1664.                                __comp);
  1665.     __merge_sort_with_buffer(__middle, __last, __buffer, (_Distance*)0,
  1666.                                __comp);
  1667.   }
  1668.   __merge_adaptive(__first, __middle, __last, _Distance(__middle - __first), 
  1669.                    _Distance(__last - __middle), __buffer, __buffer_size,
  1670.                    __comp);
  1671. }
  1673. template <class _RandomAccessIter, class _Tp, class _Distance>
  1674. inline void __stable_sort_aux(_RandomAccessIter __first,
  1675.                               _RandomAccessIter __last, _Tp*, _Distance*) {
  1676.   _Temporary_buffer<_RandomAccessIter, _Tp> buf(__first, __last);
  1677.   if (buf.begin() == 0)
  1678.     __inplace_stable_sort(__first, __last);
  1679.   else 
  1680.     __stable_sort_adaptive(__first, __last, buf.begin(),
  1681.                            _Distance(buf.size()));
  1682. }
  1684. template <class _RandomAccessIter, class _Tp, class _Distance, class _Compare>
  1685. inline void __stable_sort_aux(_RandomAccessIter __first,
  1686.                               _RandomAccessIter __last, _Tp*, _Distance*,
  1687.                               _Compare __comp) {
  1688.   _Temporary_buffer<_RandomAccessIter, _Tp> buf(__first, __last);
  1689.   if (buf.begin() == 0)
  1690.     __inplace_stable_sort(__first, __last, __comp);
  1691.   else 
  1692.     __stable_sort_adaptive(__first, __last, buf.begin(),
  1693.                            _Distance(buf.size()),
  1694.                            __comp);
  1695. }
  1697. template <class _RandomAccessIter>
  1698. inline void stable_sort(_RandomAccessIter __first,
  1699.                         _RandomAccessIter __last) {
  1700.   __STL_REQUIRES(_RandomAccessIter, _Mutable_RandomAccessIterator);
  1701.   __STL_REQUIRES(typename iterator_traits<_RandomAccessIter>::value_type,
  1702.                  _LessThanComparable);
  1703.   __stable_sort_aux(__first, __last,
  1704.                     __VALUE_TYPE(__first),
  1705.                     __DISTANCE_TYPE(__first));
  1706. }
  1708. template <class _RandomAccessIter, class _Compare>
  1709. inline void stable_sort(_RandomAccessIter __first,
  1710.                         _RandomAccessIter __last, _Compare __comp) {
  1711.   __STL_REQUIRES(_RandomAccessIter, _Mutable_RandomAccessIterator);
  1712.   __STL_BINARY_FUNCTION_CHECK(_Compare, bool,
  1713.        typename iterator_traits<_RandomAccessIter>::value_type,
  1714.        typename iterator_traits<_RandomAccessIter>::value_type);
  1715.   __stable_sort_aux(__first, __last,
  1716.                     __VALUE_TYPE(__first),
  1717.                     __DISTANCE_TYPE(__first), 
  1718.                     __comp);
  1719. }
  1721. // partial_sort, partial_sort_copy, and auxiliary functions.
  1723. template <class _RandomAccessIter, class _Tp>
  1724. void __partial_sort(_RandomAccessIter __first, _RandomAccessIter __middle,
  1725.                     _RandomAccessIter __last, _Tp*) {
  1726.   make_heap(__first, __middle);
  1727.   for (_RandomAccessIter __i = __middle; __i < __last; ++__i)
  1728.     if (*__i < *__first) 
  1729.       __pop_heap(__first, __middle, __i, _Tp(*__i),
  1730.                  __DISTANCE_TYPE(__first));
  1731.   sort_heap(__first, __middle);
  1732. }
  1734. template <class _RandomAccessIter>
  1735. inline void partial_sort(_RandomAccessIter __first,
  1736.                          _RandomAccessIter __middle,
  1737.                          _RandomAccessIter __last) {
  1738.   __STL_REQUIRES(_RandomAccessIter, _Mutable_RandomAccessIterator);
  1739.   __STL_REQUIRES(typename iterator_traits<_RandomAccessIter>::value_type,
  1740.                  _LessThanComparable);
  1741.   __partial_sort(__first, __middle, __last, __VALUE_TYPE(__first));
  1742. }
  1744. template <class _RandomAccessIter, class _Tp, class _Compare>
  1745. void __partial_sort(_RandomAccessIter __first, _RandomAccessIter __middle,
  1746.                     _RandomAccessIter __last, _Tp*, _Compare __comp) {
  1747.   make_heap(__first, __middle, __comp);
  1748.   for (_RandomAccessIter __i = __middle; __i < __last; ++__i)
  1749.     if (__comp(*__i, *__first))
  1750.       __pop_heap(__first, __middle, __i, _Tp(*__i), __comp,
  1751.                  __DISTANCE_TYPE(__first));
  1752.   sort_heap(__first, __middle, __comp);
  1753. }
  1755. template <class _RandomAccessIter, class _Compare>
  1756. inline void partial_sort(_RandomAccessIter __first,
  1757.                          _RandomAccessIter __middle,
  1758.                          _RandomAccessIter __last, _Compare __comp) {
  1759.   __STL_REQUIRES(_RandomAccessIter, _Mutable_RandomAccessIterator);
  1760.   __STL_BINARY_FUNCTION_CHECK(_Compare, bool, 
  1761.       typename iterator_traits<_RandomAccessIter>::value_type,
  1762.       typename iterator_traits<_RandomAccessIter>::value_type);
  1763.   __partial_sort(__first, __middle, __last, __VALUE_TYPE(__first), __comp);
  1764. }
  1766. template <class _InputIter, class _RandomAccessIter, class _Distance,
  1767.           class _Tp>
  1768. _RandomAccessIter __partial_sort_copy(_InputIter __first,
  1769.                                       _InputIter __last,
  1770.                                       _RandomAccessIter __result_first,
  1771.                                       _RandomAccessIter __result_last, 
  1772.                                       _Distance*, _Tp*) {
  1773.   if (__result_first == __result_last) return __result_last;
  1774.   _RandomAccessIter __result_real_last = __result_first;
  1775.   while(__first != __last && __result_real_last != __result_last) {
  1776.     *__result_real_last = *__first;
  1777.     ++__result_real_last;
  1778.     ++__first;
  1779.   }
  1780.   make_heap(__result_first, __result_real_last);
  1781.   while (__first != __last) {
  1782.     if (*__first < *__result_first) 
  1783.       __adjust_heap(__result_first, _Distance(0),
  1784.                     _Distance(__result_real_last - __result_first),
  1785.                     _Tp(*__first));
  1786.     ++__first;
  1787.   }
  1788.   sort_heap(__result_first, __result_real_last);
  1789.   return __result_real_last;
  1790. }
  1792. template <class _InputIter, class _RandomAccessIter>
  1793. inline _RandomAccessIter
  1794. partial_sort_copy(_InputIter __first, _InputIter __last,
  1795.                   _RandomAccessIter __result_first,
  1796.                   _RandomAccessIter __result_last) {
  1797.   __STL_REQUIRES(_InputIter, _InputIterator);
  1798.   __STL_REQUIRES(_RandomAccessIter, _Mutable_RandomAccessIterator);
  1799.   __STL_CONVERTIBLE(typename iterator_traits<_InputIter>::value_type,
  1800.                     typename iterator_traits<_RandomAccessIter>::value_type);
  1801.   __STL_REQUIRES(typename iterator_traits<_RandomAccessIter>::value_type,
  1802.                  _LessThanComparable);
  1803.   __STL_REQUIRES(typename iterator_traits<_InputIter>::value_type,
  1804.                  _LessThanComparable);
  1805.   return __partial_sort_copy(__first, __last, __result_first, __result_last, 
  1806.                              __DISTANCE_TYPE(__result_first),
  1807.                              __VALUE_TYPE(__first));
  1808. }
  1810. template <class _InputIter, class _RandomAccessIter, class _Compare,
  1811.           class _Distance, class _Tp>
  1812. _RandomAccessIter __partial_sort_copy(_InputIter __first,
  1813.                                          _InputIter __last,
  1814.                                          _RandomAccessIter __result_first,
  1815.                                          _RandomAccessIter __result_last,
  1816.                                          _Compare __comp, _Distance*, _Tp*) {
  1817.   if (__result_first == __result_last) return __result_last;
  1818.   _RandomAccessIter __result_real_last = __result_first;
  1819.   while(__first != __last && __result_real_last != __result_last) {
  1820.     *__result_real_last = *__first;
  1821.     ++__result_real_last;
  1822.     ++__first;
  1823.   }
  1824.   make_heap(__result_first, __result_real_last, __comp);
  1825.   while (__first != __last) {
  1826.     if (__comp(*__first, *__result_first))
  1827.       __adjust_heap(__result_first, _Distance(0),
  1828.                     _Distance(__result_real_last - __result_first),
  1829.                     _Tp(*__first),
  1830.                     __comp);
  1831.     ++__first;
  1832.   }
  1833.   sort_heap(__result_first, __result_real_last, __comp);
  1834.   return __result_real_last;
  1835. }
  1837. template <class _InputIter, class _RandomAccessIter, class _Compare>
  1838. inline _RandomAccessIter
  1839. partial_sort_copy(_InputIter __first, _InputIter __last,
  1840.                   _RandomAccessIter __result_first,
  1841.                   _RandomAccessIter __result_last, _Compare __comp) {
  1842.   __STL_REQUIRES(_InputIter, _InputIterator);
  1843.   __STL_REQUIRES(_RandomAccessIter, _Mutable_RandomAccessIterator);
  1844.   __STL_CONVERTIBLE(typename iterator_traits<_InputIter>::value_type,
  1845.                     typename iterator_traits<_RandomAccessIter>::value_type);
  1846.   __STL_BINARY_FUNCTION_CHECK(_Compare, bool,
  1847.      typename iterator_traits<_RandomAccessIter>::value_type,
  1848.      typename iterator_traits<_RandomAccessIter>::value_type);  
  1849.   return __partial_sort_copy(__first, __last, __result_first, __result_last,
  1850.                              __comp,
  1851.                              __DISTANCE_TYPE(__result_first),
  1852.                              __VALUE_TYPE(__first));
  1853. }
  1855. // nth_element() and its auxiliary functions.  
  1857. template <class _RandomAccessIter, class _Tp>
  1858. void __nth_element(_RandomAccessIter __first, _RandomAccessIter __nth,
  1859.                    _RandomAccessIter __last, _Tp*) {
  1860.   while (__last - __first > 3) {
  1861.     _RandomAccessIter __cut =
  1862.       __unguarded_partition(__first, __last,
  1863.                             _Tp(__median(*__first,
  1864.                                          *(__first + (__last - __first)/2),
  1865.                                          *(__last - 1))));
  1866.     if (__cut <= __nth)
  1867.       __first = __cut;
  1868.     else 
  1869.       __last = __cut;
  1870.   }
  1871.   __insertion_sort(__first, __last);
  1872. }
  1874. template <class _RandomAccessIter>
  1875. inline void nth_element(_RandomAccessIter __first, _RandomAccessIter __nth,
  1876.                         _RandomAccessIter __last) {
  1877.   __STL_REQUIRES(_RandomAccessIter, _Mutable_RandomAccessIterator);
  1878.   __STL_REQUIRES(typename iterator_traits<_RandomAccessIter>::value_type,
  1879.                  _LessThanComparable);
  1880.   __nth_element(__first, __nth, __last, __VALUE_TYPE(__first));
  1881. }
  1883. template <class _RandomAccessIter, class _Tp, class _Compare>
  1884. void __nth_element(_RandomAccessIter __first, _RandomAccessIter __nth,
  1885.                    _RandomAccessIter __last, _Tp*, _Compare __comp) {
  1886.   while (__last - __first > 3) {
  1887.     _RandomAccessIter __cut =
  1888.       __unguarded_partition(__first, __last,
  1889.                             _Tp(__median(*__first,
  1890.                                          *(__first + (__last - __first)/2), 
  1891.                                          *(__last - 1),
  1892.                                          __comp)),
  1893.                             __comp);
  1894.     if (__cut <= __nth)
  1895.       __first = __cut;
  1896.     else 
  1897.       __last = __cut;
  1898.   }
  1899.   __insertion_sort(__first, __last, __comp);
  1900. }
  1902. template <class _RandomAccessIter, class _Compare>
  1903. inline void nth_element(_RandomAccessIter __first, _RandomAccessIter __nth,
  1904.                         _RandomAccessIter __last, _Compare __comp) {
  1905.   __STL_REQUIRES(_RandomAccessIter, _Mutable_RandomAccessIterator);
  1906.   __STL_BINARY_FUNCTION_CHECK(_Compare, bool,
  1907.      typename iterator_traits<_RandomAccessIter>::value_type,
  1908.      typename iterator_traits<_RandomAccessIter>::value_type);
  1909.   __nth_element(__first, __nth, __last, __VALUE_TYPE(__first), __comp);
  1910. }
  1913. // Binary search (lower_bound, upper_bound, equal_range, binary_search).
  1915. template <class _ForwardIter, class _Tp, class _Distance>
  1916. _ForwardIter __lower_bound(_ForwardIter __first, _ForwardIter __last,
  1917.                            const _Tp& __val, _Distance*) 
  1918. {
  1919.   _Distance __len = 0;
  1920.   distance(__first, __last, __len);
  1921.   _Distance __half;
  1922.   _ForwardIter __middle;
  1924.   while (__len > 0) {
  1925.     __half = __len >> 1;
  1926.     __middle = __first;
  1927.     advance(__middle, __half);
  1928.     if (*__middle < __val) {
  1929.       __first = __middle;
  1930.       ++__first;
  1931.       __len = __len - __half - 1;
  1932.     }
  1933.     else
  1934.       __len = __half;
  1935.   }
  1936.   return __first;
  1937. }
  1939. template <class _ForwardIter, class _Tp>
  1940. inline _ForwardIter lower_bound(_ForwardIter __first, _ForwardIter __last,
  1941. const _Tp& __val) {
  1942.   __STL_REQUIRES(_ForwardIter, _ForwardIterator);
  1943.   __STL_REQUIRES_SAME_TYPE(_Tp,
  1944.       typename iterator_traits<_ForwardIter>::value_type);
  1945.   __STL_REQUIRES(_Tp, _LessThanComparable);
  1946.   return __lower_bound(__first, __last, __val,
  1947.                        __DISTANCE_TYPE(__first));
  1948. }
  1950. template <class _ForwardIter, class _Tp, class _Compare, class _Distance>
  1951. _ForwardIter __lower_bound(_ForwardIter __first, _ForwardIter __last,
  1952.                               const _Tp& __val, _Compare __comp, _Distance*)
  1953. {
  1954.   _Distance __len = 0;
  1955.   distance(__first, __last, __len);
  1956.   _Distance __half;
  1957.   _ForwardIter __middle;
  1959.   while (__len > 0) {
  1960.     __half = __len >> 1;
  1961.     __middle = __first;
  1962.     advance(__middle, __half);
  1963.     if (__comp(*__middle, __val)) {
  1964.       __first = __middle;
  1965.       ++__first;
  1966.       __len = __len - __half - 1;
  1967.     }
  1968.     else
  1969.       __len = __half;
  1970.   }
  1971.   return __first;
  1972. }
  1974. template <class _ForwardIter, class _Tp, class _Compare>
  1975. inline _ForwardIter lower_bound(_ForwardIter __first, _ForwardIter __last,
  1976.                                 const _Tp& __val, _Compare __comp) {
  1977.   __STL_REQUIRES(_ForwardIter, _ForwardIterator);
  1978.   __STL_REQUIRES_SAME_TYPE(_Tp,
  1979.       typename iterator_traits<_ForwardIter>::value_type);
  1980.   __STL_BINARY_FUNCTION_CHECK(_Compare, bool, _Tp, _Tp);
  1981.   return __lower_bound(__first, __last, __val, __comp,
  1982.                        __DISTANCE_TYPE(__first));
  1983. }
  1985. template <class _ForwardIter, class _Tp, class _Distance>
  1986. _ForwardIter __upper_bound(_ForwardIter __first, _ForwardIter __last,
  1987.                            const _Tp& __val, _Distance*)
  1988. {
  1989.   _Distance __len = 0;
  1990.   distance(__first, __last, __len);
  1991.   _Distance __half;
  1992.   _ForwardIter __middle;
  1994.   while (__len > 0) {
  1995.     __half = __len >> 1;
  1996.     __middle = __first;
  1997.     advance(__middle, __half);
  1998.     if (__val < *__middle)
  1999.       __len = __half;
  2000.     else {
  2001.       __first = __middle;
  2002.       ++__first;
  2003.       __len = __len - __half - 1;
  2004.     }
  2005.   }
  2006.   return __first;
  2007. }
  2009. template <class _ForwardIter, class _Tp>
  2010. inline _ForwardIter upper_bound(_ForwardIter __first, _ForwardIter __last,
  2011.                                 const _Tp& __val) {
  2012.   __STL_REQUIRES(_ForwardIter, _ForwardIterator);
  2013.   __STL_REQUIRES_SAME_TYPE(_Tp,
  2014.       typename iterator_traits<_ForwardIter>::value_type);
  2015.   __STL_REQUIRES(_Tp, _LessThanComparable);
  2016.   return __upper_bound(__first, __last, __val,
  2017.                        __DISTANCE_TYPE(__first));
  2018. }
  2020. template <class _ForwardIter, class _Tp, class _Compare, class _Distance>
  2021. _ForwardIter __upper_bound(_ForwardIter __first, _ForwardIter __last,
  2022.                            const _Tp& __val, _Compare __comp, _Distance*)
  2023. {
  2024.   _Distance __len = 0;
  2025.   distance(__first, __last, __len);
  2026.   _Distance __half;
  2027.   _ForwardIter __middle;
  2029.   while (__len > 0) {
  2030.     __half = __len >> 1;
  2031.     __middle = __first;
  2032.     advance(__middle, __half);
  2033.     if (__comp(__val, *__middle))
  2034.       __len = __half;
  2035.     else {
  2036.       __first = __middle;
  2037.       ++__first;
  2038.       __len = __len - __half - 1;
  2039.     }
  2040.   }
  2041.   return __first;
  2042. }
  2044. template <class _ForwardIter, class _Tp, class _Compare>
  2045. inline _ForwardIter upper_bound(_ForwardIter __first, _ForwardIter __last,
  2046.                                 const _Tp& __val, _Compare __comp) {
  2047.   __STL_REQUIRES(_ForwardIter, _ForwardIterator);
  2048.   __STL_REQUIRES_SAME_TYPE(_Tp,
  2049.       typename iterator_traits<_ForwardIter>::value_type);
  2050.   __STL_BINARY_FUNCTION_CHECK(_Compare, bool, _Tp, _Tp);
  2051.   return __upper_bound(__first, __last, __val, __comp,
  2052.                        __DISTANCE_TYPE(__first));
  2053. }
  2055. template <class _ForwardIter, class _Tp, class _Distance>
  2056. pair<_ForwardIter, _ForwardIter>
  2057. __equal_range(_ForwardIter __first, _ForwardIter __last, const _Tp& __val,
  2058.               _Distance*)
  2059. {
  2060.   _Distance __len = 0;
  2061.   distance(__first, __last, __len);
  2062.   _Distance __half;
  2063.   _ForwardIter __middle, __left, __right;
  2065.   while (__len > 0) {
  2066.     __half = __len >> 1;
  2067.     __middle = __first;
  2068.     advance(__middle, __half);
  2069.     if (*__middle < __val) {
  2070.       __first = __middle;
  2071.       ++__first;
  2072.       __len = __len - __half - 1;
  2073.     }
  2074.     else if (__val < *__middle)
  2075.       __len = __half;
  2076.     else {
  2077.       __left = lower_bound(__first, __middle, __val);
  2078.       advance(__first, __len);
  2079.       __right = upper_bound(++__middle, __first, __val);
  2080.       return pair<_ForwardIter, _ForwardIter>(__left, __right);
  2081.     }
  2082.   }
  2083.   return pair<_ForwardIter, _ForwardIter>(__first, __first);
  2084. }
  2086. template <class _ForwardIter, class _Tp>
  2087. inline pair<_ForwardIter, _ForwardIter>
  2088. equal_range(_ForwardIter __first, _ForwardIter __last, const _Tp& __val) {
  2089.   __STL_REQUIRES(_ForwardIter, _ForwardIterator);
  2090.   __STL_REQUIRES_SAME_TYPE(_Tp, 
  2091.        typename iterator_traits<_ForwardIter>::value_type);
  2092.   __STL_REQUIRES(_Tp, _LessThanComparable);
  2093.   return __equal_range(__first, __last, __val,
  2094.                        __DISTANCE_TYPE(__first));
  2095. }
  2097. template <class _ForwardIter, class _Tp, class _Compare, class _Distance>
  2098. pair<_ForwardIter, _ForwardIter>
  2099. __equal_range(_ForwardIter __first, _ForwardIter __last, const _Tp& __val,
  2100.               _Compare __comp, _Distance*)
  2101. {
  2102.   _Distance __len = 0;
  2103.   distance(__first, __last, __len);
  2104.   _Distance __half;
  2105.   _ForwardIter __middle, __left, __right;
  2107.   while (__len > 0) {
  2108.     __half = __len >> 1;
  2109.     __middle = __first;
  2110.     advance(__middle, __half);
  2111.     if (__comp(*__middle, __val)) {
  2112.       __first = __middle;
  2113.       ++__first;
  2114.       __len = __len - __half - 1;
  2115.     }
  2116.     else if (__comp(__val, *__middle))
  2117.       __len = __half;
  2118.     else {
  2119.       __left = lower_bound(__first, __middle, __val, __comp);
  2120.       advance(__first, __len);
  2121.       __right = upper_bound(++__middle, __first, __val, __comp);
  2122.       return pair<_ForwardIter, _ForwardIter>(__left, __right);
  2123.     }
  2124.   }
  2125.   return pair<_ForwardIter, _ForwardIter>(__first, __first);
  2126. }           
  2128. template <class _ForwardIter, class _Tp, class _Compare>
  2129. inline pair<_ForwardIter, _ForwardIter>
  2130. equal_range(_ForwardIter __first, _ForwardIter __last, const _Tp& __val,
  2131.             _Compare __comp) {
  2132.   __STL_REQUIRES(_ForwardIter, _ForwardIterator);
  2133.   __STL_REQUIRES_SAME_TYPE(_Tp, 
  2134.        typename iterator_traits<_ForwardIter>::value_type);
  2135.   __STL_BINARY_FUNCTION_CHECK(_Compare, bool, _Tp, _Tp);
  2136.   return __equal_range(__first, __last, __val, __comp,
  2137.                        __DISTANCE_TYPE(__first));
  2138. } 
  2140. template <class _ForwardIter, class _Tp>
  2141. bool binary_search(_ForwardIter __first, _ForwardIter __last,
  2142.                    const _Tp& __val) {
  2143.   __STL_REQUIRES(_ForwardIter, _ForwardIterator);
  2144.   __STL_REQUIRES_SAME_TYPE(_Tp,
  2145.         typename iterator_traits<_ForwardIter>::value_type);
  2146.   __STL_REQUIRES(_Tp, _LessThanComparable);
  2147.   _ForwardIter __i = lower_bound(__first, __last, __val);
  2148.   return __i != __last && !(__val < *__i);
  2149. }
  2151. template <class _ForwardIter, class _Tp, class _Compare>
  2152. bool binary_search(_ForwardIter __first, _ForwardIter __last,
  2153.                    const _Tp& __val,
  2154.                    _Compare __comp) {
  2155.   __STL_REQUIRES(_ForwardIter, _ForwardIterator);
  2156.   __STL_REQUIRES_SAME_TYPE(_Tp,
  2157.         typename iterator_traits<_ForwardIter>::value_type);
  2158.   __STL_BINARY_FUNCTION_CHECK(_Compare, bool, _Tp, _Tp);
  2159.   _ForwardIter __i = lower_bound(__first, __last, __val, __comp);
  2160.   return __i != __last && !__comp(__val, *__i);
  2161. }
  2163. // merge, with and without an explicitly supplied comparison function.
  2165. template <class _InputIter1, class _InputIter2, class _OutputIter>
  2166. _OutputIter merge(_InputIter1 __first1, _InputIter1 __last1,
  2167.                   _InputIter2 __first2, _InputIter2 __last2,
  2168.                   _OutputIter __result) {
  2169.   __STL_REQUIRES(_InputIter1, _InputIterator);
  2170.   __STL_REQUIRES(_InputIter2, _InputIterator);
  2171.   __STL_REQUIRES(_OutputIter, _OutputIterator);
  2172.   __STL_REQUIRES_SAME_TYPE(
  2173.           typename iterator_traits<_InputIter1>::value_type,
  2174.           typename iterator_traits<_InputIter2>::value_type);
  2175.   __STL_REQUIRES(typename iterator_traits<_InputIter1>::value_type,
  2176.                  _LessThanComparable);
  2177.   while (__first1 != __last1 && __first2 != __last2) {
  2178.     if (*__first2 < *__first1) {
  2179.       *__result = *__first2;
  2180.       ++__first2;
  2181.     }
  2182.     else {
  2183.       *__result = *__first1;
  2184.       ++__first1;
  2185.     }
  2186.     ++__result;
  2187.   }
  2188.   return copy(__first2, __last2, copy(__first1, __last1, __result));
  2189. }
  2191. template <class _InputIter1, class _InputIter2, class _OutputIter,
  2192.           class _Compare>
  2193. _OutputIter merge(_InputIter1 __first1, _InputIter1 __last1,
  2194.                   _InputIter2 __first2, _InputIter2 __last2,
  2195.                   _OutputIter __result, _Compare __comp) {
  2196.   __STL_REQUIRES(_InputIter1, _InputIterator);
  2197.   __STL_REQUIRES(_InputIter2, _InputIterator);
  2198.   __STL_REQUIRES_SAME_TYPE(
  2199.           typename iterator_traits<_InputIter1>::value_type,
  2200.           typename iterator_traits<_InputIter2>::value_type);
  2201.   __STL_REQUIRES(_OutputIter, _OutputIterator);
  2202.   __STL_BINARY_FUNCTION_CHECK(_Compare, bool,
  2203.           typename iterator_traits<_InputIter1>::value_type,
  2204.           typename iterator_traits<_InputIter1>::value_type);
  2205.   while (__first1 != __last1 && __first2 != __last2) {
  2206.     if (__comp(*__first2, *__first1)) {
  2207.       *__result = *__first2;
  2208.       ++__first2;
  2209.     }
  2210.     else {
  2211.       *__result = *__first1;
  2212.       ++__first1;
  2213.     }
  2214.     ++__result;
  2215.   }
  2216.   return copy(__first2, __last2, copy(__first1, __last1, __result));
  2217. }
  2219. // inplace_merge and its auxiliary functions. 
  2221. template <class _BidirectionalIter, class _Distance>
  2222. void __merge_without_buffer(_BidirectionalIter __first,
  2223.                             _BidirectionalIter __middle,
  2224.                             _BidirectionalIter __last,
  2225.                             _Distance __len1, _Distance __len2) {
  2226.   if (__len1 == 0 || __len2 == 0)
  2227.     return;
  2228.   if (__len1 + __len2 == 2) {
  2229.     if (*__middle < *__first)
  2230.       iter_swap(__first, __middle);
  2231.     return;
  2232.   }
  2233.   _BidirectionalIter __first_cut = __first;
  2234.   _BidirectionalIter __second_cut = __middle;
  2235.   _Distance __len11 = 0;
  2236.   _Distance __len22 = 0;
  2237.   if (__len1 > __len2) {
  2238.     __len11 = __len1 / 2;
  2239.     advance(__first_cut, __len11);
  2240.     __second_cut = lower_bound(__middle, __last, *__first_cut);
  2241.     distance(__middle, __second_cut, __len22);
  2242.   }
  2243.   else {
  2244.     __len22 = __len2 / 2;
  2245.     advance(__second_cut, __len22);
  2246.     __first_cut = upper_bound(__first, __middle, *__second_cut);
  2247.     distance(__first, __first_cut, __len11);
  2248.   }
  2249.   _BidirectionalIter __new_middle
  2250.     = rotate(__first_cut, __middle, __second_cut);
  2251.   __merge_without_buffer(__first, __first_cut, __new_middle,
  2252.                          __len11, __len22);
  2253.   __merge_without_buffer(__new_middle, __second_cut, __last, __len1 - __len11,
  2254.                          __len2 - __len22);
  2255. }
  2257. template <class _BidirectionalIter, class _Distance, class _Compare>
  2258. void __merge_without_buffer(_BidirectionalIter __first,
  2259.                             _BidirectionalIter __middle,
  2260.                             _BidirectionalIter __last,
  2261.                             _Distance __len1, _Distance __len2,
  2262.                             _Compare __comp) {
  2263.   if (__len1 == 0 || __len2 == 0)
  2264.     return;
  2265.   if (__len1 + __len2 == 2) {
  2266.     if (__comp(*__middle, *__first))
  2267.       iter_swap(__first, __middle);
  2268.     return;
  2269.   }
  2270.   _BidirectionalIter __first_cut = __first;
  2271.   _BidirectionalIter __second_cut = __middle;
  2272.   _Distance __len11 = 0;
  2273.   _Distance __len22 = 0;
  2274.   if (__len1 > __len2) {
  2275.     __len11 = __len1 / 2;
  2276.     advance(__first_cut, __len11);
  2277.     __second_cut = lower_bound(__middle, __last, *__first_cut, __comp);
  2278.     distance(__middle, __second_cut, __len22);
  2279.   }
  2280.   else {
  2281.     __len22 = __len2 / 2;
  2282.     advance(__second_cut, __len22);
  2283.     __first_cut = upper_bound(__first, __middle, *__second_cut, __comp);
  2284.     distance(__first, __first_cut, __len11);
  2285.   }
  2286.   _BidirectionalIter __new_middle
  2287.     = rotate(__first_cut, __middle, __second_cut);
  2288.   __merge_without_buffer(__first, __first_cut, __new_middle, __len11, __len22,
  2289.                          __comp);
  2290.   __merge_without_buffer(__new_middle, __second_cut, __last, __len1 - __len11,
  2291.                          __len2 - __len22, __comp);
  2292. }
  2294. template <class _BidirectionalIter1, class _BidirectionalIter2,
  2295.           class _Distance>
  2296. _BidirectionalIter1 __rotate_adaptive(_BidirectionalIter1 __first,
  2297.                                       _BidirectionalIter1 __middle,
  2298.                                       _BidirectionalIter1 __last,
  2299.                                       _Distance __len1, _Distance __len2,
  2300.                                       _BidirectionalIter2 __buffer,
  2301.                                       _Distance __buffer_size) {
  2302.   _BidirectionalIter2 __buffer_end;
  2303.   if (__len1 > __len2 && __len2 <= __buffer_size) {
  2304.     __buffer_end = copy(__middle, __last, __buffer);
  2305.     copy_backward(__first, __middle, __last);
  2306.     return copy(__buffer, __buffer_end, __first);
  2307.   }
  2308.   else if (__len1 <= __buffer_size) {
  2309.     __buffer_end = copy(__first, __middle, __buffer);
  2310.     copy(__middle, __last, __first);
  2311.     return copy_backward(__buffer, __buffer_end, __last);
  2312.   }
  2313.   else
  2314.     return rotate(__first, __middle, __last);
  2315. }
  2317. template <class _BidirectionalIter1, class _BidirectionalIter2,
  2318.           class _BidirectionalIter3>
  2319. _BidirectionalIter3 __merge_backward(_BidirectionalIter1 __first1,
  2320.                                      _BidirectionalIter1 __last1,
  2321.                                      _BidirectionalIter2 __first2,
  2322.                                      _BidirectionalIter2 __last2,
  2323.                                      _BidirectionalIter3 __result) {
  2324.   if (__first1 == __last1)
  2325.     return copy_backward(__first2, __last2, __result);
  2326.   if (__first2 == __last2)
  2327.     return copy_backward(__first1, __last1, __result);
  2328.   --__last1;
  2329.   --__last2;
  2330.   while (true) {
  2331.     if (*__last2 < *__last1) {
  2332.       *--__result = *__last1;
  2333.       if (__first1 == __last1)
  2334.         return copy_backward(__first2, ++__last2, __result);
  2335.       --__last1;
  2336.     }
  2337.     else {
  2338.       *--__result = *__last2;
  2339.       if (__first2 == __last2)
  2340.         return copy_backward(__first1, ++__last1, __result);
  2341.       --__last2;
  2342.     }
  2343.   }
  2344. }
  2346. template <class _BidirectionalIter1, class _BidirectionalIter2,
  2347.           class _BidirectionalIter3, class _Compare>
  2348. _BidirectionalIter3 __merge_backward(_BidirectionalIter1 __first1,
  2349.                                      _BidirectionalIter1 __last1,
  2350.                                      _BidirectionalIter2 __first2,
  2351.                                      _BidirectionalIter2 __last2,
  2352.                                      _BidirectionalIter3 __result,
  2353.                                      _Compare __comp) {
  2354.   if (__first1 == __last1)
  2355.     return copy_backward(__first2, __last2, __result);
  2356.   if (__first2 == __last2)
  2357.     return copy_backward(__first1, __last1, __result);
  2358.   --__last1;
  2359.   --__last2;
  2360.   while (true) {
  2361.     if (__comp(*__last2, *__last1)) {
  2362.       *--__result = *__last1;
  2363.       if (__first1 == __last1)
  2364.         return copy_backward(__first2, ++__last2, __result);
  2365.       --__last1;
  2366.     }
  2367.     else {
  2368.       *--__result = *__last2;
  2369.       if (__first2 == __last2)
  2370.         return copy_backward(__first1, ++__last1, __result);
  2371.       --__last2;
  2372.     }
  2373.   }
  2374. }
  2376. template <class _BidirectionalIter, class _Distance, class _Pointer>
  2377. void __merge_adaptive(_BidirectionalIter __first,
  2378.                       _BidirectionalIter __middle, 
  2379.                       _BidirectionalIter __last,
  2380.                       _Distance __len1, _Distance __len2,
  2381.                       _Pointer __buffer, _Distance __buffer_size) {
  2382.   if (__len1 <= __len2 && __len1 <= __buffer_size) {
  2383.     _Pointer __buffer_end = copy(__first, __middle, __buffer);
  2384.     merge(__buffer, __buffer_end, __middle, __last, __first);
  2385.   }
  2386.   else if (__len2 <= __buffer_size) {
  2387.     _Pointer __buffer_end = copy(__middle, __last, __buffer);
  2388.     __merge_backward(__first, __middle, __buffer, __buffer_end, __last);
  2389.   }
  2390.   else {
  2391.     _BidirectionalIter __first_cut = __first;
  2392.     _BidirectionalIter __second_cut = __middle;
  2393.     _Distance __len11 = 0;
  2394.     _Distance __len22 = 0;
  2395.     if (__len1 > __len2) {
  2396.       __len11 = __len1 / 2;
  2397.       advance(__first_cut, __len11);
  2398.       __second_cut = lower_bound(__middle, __last, *__first_cut);
  2399.       distance(__middle, __second_cut, __len22); 
  2400.     }
  2401.     else {
  2402.       __len22 = __len2 / 2;
  2403.       advance(__second_cut, __len22);
  2404.       __first_cut = upper_bound(__first, __middle, *__second_cut);
  2405.       distance(__first, __first_cut, __len11);
  2406.     }
  2407.     _BidirectionalIter __new_middle =
  2408.       __rotate_adaptive(__first_cut, __middle, __second_cut, __len1 - __len11,
  2409.                         __len22, __buffer, __buffer_size);
  2410.     __merge_adaptive(__first, __first_cut, __new_middle, __len11,
  2411.                      __len22, __buffer, __buffer_size);
  2412.     __merge_adaptive(__new_middle, __second_cut, __last, __len1 - __len11,
  2413.                      __len2 - __len22, __buffer, __buffer_size);
  2414.   }
  2415. }
  2417. template <class _BidirectionalIter, class _Distance, class _Pointer,
  2418.           class _Compare>
  2419. void __merge_adaptive(_BidirectionalIter __first, 
  2420.                       _BidirectionalIter __middle, 
  2421.                       _BidirectionalIter __last,
  2422.                       _Distance __len1, _Distance __len2,
  2423.                       _Pointer __buffer, _Distance __buffer_size,
  2424.                       _Compare __comp) {
  2425.   if (__len1 <= __len2 && __len1 <= __buffer_size) {
  2426.     _Pointer __buffer_end = copy(__first, __middle, __buffer);
  2427.     merge(__buffer, __buffer_end, __middle, __last, __first, __comp);
  2428.   }
  2429.   else if (__len2 <= __buffer_size) {
  2430.     _Pointer __buffer_end = copy(__middle, __last, __buffer);
  2431.     __merge_backward(__first, __middle, __buffer, __buffer_end, __last,
  2432.                      __comp);
  2433.   }
  2434.   else {
  2435.     _BidirectionalIter __first_cut = __first;
  2436.     _BidirectionalIter __second_cut = __middle;
  2437.     _Distance __len11 = 0;
  2438.     _Distance __len22 = 0;
  2439.     if (__len1 > __len2) {
  2440.       __len11 = __len1 / 2;
  2441.       advance(__first_cut, __len11);
  2442.       __second_cut = lower_bound(__middle, __last, *__first_cut, __comp);
  2443.       distance(__middle, __second_cut, __len22);   
  2444.     }
  2445.     else {
  2446.       __len22 = __len2 / 2;
  2447.       advance(__second_cut, __len22);
  2448.       __first_cut = upper_bound(__first, __middle, *__second_cut, __comp);
  2449.       distance(__first, __first_cut, __len11);
  2450.     }
  2451.     _BidirectionalIter __new_middle =
  2452.       __rotate_adaptive(__first_cut, __middle, __second_cut, __len1 - __len11,
  2453.                         __len22, __buffer, __buffer_size);
  2454.     __merge_adaptive(__first, __first_cut, __new_middle, __len11,
  2455.                      __len22, __buffer, __buffer_size, __comp);
  2456.     __merge_adaptive(__new_middle, __second_cut, __last, __len1 - __len11,
  2457.                      __len2 - __len22, __buffer, __buffer_size, __comp);
  2458.   }
  2459. }
  2461. template <class _BidirectionalIter, class _Tp, class _Distance>
  2462. inline void __inplace_merge_aux(_BidirectionalIter __first,
  2463.                                 _BidirectionalIter __middle,
  2464.                                 _BidirectionalIter __last, _Tp*, _Distance*) {
  2465.   _Distance __len1 = 0;
  2466.   distance(__first, __middle, __len1);
  2467.   _Distance __len2 = 0;
  2468.   distance(__middle, __last, __len2);
  2470.   _Temporary_buffer<_BidirectionalIter, _Tp> __buf(__first, __last);
  2471.   if (__buf.begin() == 0)
  2472.     __merge_without_buffer(__first, __middle, __last, __len1, __len2);
  2473.   else
  2474.     __merge_adaptive(__first, __middle, __last, __len1, __len2,
  2475.                      __buf.begin(), _Distance(__buf.size()));
  2476. }
  2478. template <class _BidirectionalIter, class _Tp, 
  2479.           class _Distance, class _Compare>
  2480. inline void __inplace_merge_aux(_BidirectionalIter __first,
  2481.                                 _BidirectionalIter __middle,
  2482.                                 _BidirectionalIter __last, _Tp*, _Distance*,
  2483.                                 _Compare __comp) {
  2484.   _Distance __len1 = 0;
  2485.   distance(__first, __middle, __len1);
  2486.   _Distance __len2 = 0;
  2487.   distance(__middle, __last, __len2);
  2489.   _Temporary_buffer<_BidirectionalIter, _Tp> __buf(__first, __last);
  2490.   if (__buf.begin() == 0)
  2491.     __merge_without_buffer(__first, __middle, __last, __len1, __len2, __comp);
  2492.   else
  2493.     __merge_adaptive(__first, __middle, __last, __len1, __len2,
  2494.                      __buf.begin(), _Distance(__buf.size()),
  2495.                      __comp);
  2496. }
  2498. template <class _BidirectionalIter>
  2499. inline void inplace_merge(_BidirectionalIter __first,
  2500.                           _BidirectionalIter __middle,
  2501.                           _BidirectionalIter __last) {
  2502.   __STL_REQUIRES(_BidirectionalIter, _Mutable_BidirectionalIterator);
  2503.   __STL_REQUIRES(typename iterator_traits<_BidirectionalIter>::value_type,
  2504.                  _LessThanComparable);
  2505.   if (__first == __middle || __middle == __last)
  2506.     return;
  2507.   __inplace_merge_aux(__first, __middle, __last,
  2508.                       __VALUE_TYPE(__first), __DISTANCE_TYPE(__first));
  2509. }
  2511. template <class _BidirectionalIter, class _Compare>
  2512. inline void inplace_merge(_BidirectionalIter __first,
  2513.                           _BidirectionalIter __middle,
  2514.                           _BidirectionalIter __last, _Compare __comp) {
  2515.   __STL_REQUIRES(_BidirectionalIter, _Mutable_BidirectionalIterator);
  2516.   __STL_BINARY_FUNCTION_CHECK(_Compare, bool,
  2517.            typename iterator_traits<_BidirectionalIter>::value_type,
  2518.            typename iterator_traits<_BidirectionalIter>::value_type);
  2519.   if (__first == __middle || __middle == __last)
  2520.     return;
  2521.   __inplace_merge_aux(__first, __middle, __last,
  2522.                       __VALUE_TYPE(__first), __DISTANCE_TYPE(__first),
  2523.                       __comp);
  2524. }
  2526. // Set algorithms: includes, set_union, set_intersection, set_difference,
  2527. // set_symmetric_difference.  All of these algorithms have the precondition
  2528. // that their input ranges are sorted and the postcondition that their output
  2529. // ranges are sorted.
  2531. template <class _InputIter1, class _InputIter2>
  2532. bool includes(_InputIter1 __first1, _InputIter1 __last1,
  2533.               _InputIter2 __first2, _InputIter2 __last2) {
  2534.   __STL_REQUIRES(_InputIter1, _InputIterator);
  2535.   __STL_REQUIRES(_InputIter2, _InputIterator);
  2536.   __STL_REQUIRES_SAME_TYPE(
  2537.        typename iterator_traits<_InputIter1>::value_type,
  2538.        typename iterator_traits<_InputIter2>::value_type);
  2539.   __STL_REQUIRES(typename iterator_traits<_InputIter1>::value_type,
  2540.                  _LessThanComparable);
  2541.   while (__first1 != __last1 && __first2 != __last2)
  2542.     if (*__first2 < *__first1)
  2543.       return false;
  2544.     else if(*__first1 < *__first2) 
  2545.       ++__first1;
  2546.     else
  2547.       ++__first1, ++__first2;
  2549.   return __first2 == __last2;
  2550. }
  2552. template <class _InputIter1, class _InputIter2, class _Compare>
  2553. bool includes(_InputIter1 __first1, _InputIter1 __last1,
  2554.               _InputIter2 __first2, _InputIter2 __last2, _Compare __comp) {
  2555.   __STL_REQUIRES(_InputIter1, _InputIterator);
  2556.   __STL_REQUIRES(_InputIter2, _InputIterator);
  2557.   __STL_REQUIRES_SAME_TYPE(
  2558.        typename iterator_traits<_InputIter1>::value_type,
  2559.        typename iterator_traits<_InputIter2>::value_type);
  2560.   __STL_BINARY_FUNCTION_CHECK(_Compare, bool,
  2561.        typename iterator_traits<_InputIter1>::value_type,
  2562.        typename iterator_traits<_InputIter2>::value_type);
  2563.   while (__first1 != __last1 && __first2 != __last2)
  2564.     if (__comp(*__first2, *__first1))
  2565.       return false;
  2566.     else if(__comp(*__first1, *__first2)) 
  2567.       ++__first1;
  2568.     else
  2569.       ++__first1, ++__first2;
  2571.   return __first2 == __last2;
  2572. }
  2574. template <class _InputIter1, class _InputIter2, class _OutputIter>
  2575. _OutputIter set_union(_InputIter1 __first1, _InputIter1 __last1,
  2576.                       _InputIter2 __first2, _InputIter2 __last2,
  2577.                       _OutputIter __result) {
  2578.   __STL_REQUIRES(_InputIter1, _InputIterator);
  2579.   __STL_REQUIRES(_InputIter2, _InputIterator);
  2580.   __STL_REQUIRES(_OutputIter, _OutputIterator);
  2581.   __STL_REQUIRES_SAME_TYPE(
  2582.        typename iterator_traits<_InputIter1>::value_type,
  2583.        typename iterator_traits<_InputIter2>::value_type);
  2584.   __STL_REQUIRES(typename iterator_traits<_InputIter1>::value_type,
  2585.                  _LessThanComparable);
  2586.   while (__first1 != __last1 && __first2 != __last2) {
  2587.     if (*__first1 < *__first2) {
  2588.       *__result = *__first1;
  2589.       ++__first1;
  2590.     }
  2591.     else if (*__first2 < *__first1) {
  2592.       *__result = *__first2;
  2593.       ++__first2;
  2594.     }
  2595.     else {
  2596.       *__result = *__first1;
  2597.       ++__first1;
  2598.       ++__first2;
  2599.     }
  2600.     ++__result;
  2601.   }
  2602.   return copy(__first2, __last2, copy(__first1, __last1, __result));
  2603. }
  2605. template <class _InputIter1, class _InputIter2, class _OutputIter,
  2606.           class _Compare>
  2607. _OutputIter set_union(_InputIter1 __first1, _InputIter1 __last1,
  2608.                       _InputIter2 __first2, _InputIter2 __last2,
  2609.                       _OutputIter __result, _Compare __comp) {
  2610.   __STL_REQUIRES(_InputIter1, _InputIterator);
  2611.   __STL_REQUIRES(_InputIter2, _InputIterator);
  2612.   __STL_REQUIRES(_OutputIter, _OutputIterator);
  2613.   __STL_REQUIRES_SAME_TYPE(
  2614.        typename iterator_traits<_InputIter1>::value_type,
  2615.        typename iterator_traits<_InputIter2>::value_type);
  2616.   __STL_BINARY_FUNCTION_CHECK(_Compare, bool,
  2617.        typename iterator_traits<_InputIter1>::value_type,
  2618.        typename iterator_traits<_InputIter2>::value_type);
  2619.   while (__first1 != __last1 && __first2 != __last2) {
  2620.     if (__comp(*__first1, *__first2)) {
  2621.       *__result = *__first1;
  2622.       ++__first1;
  2623.     }
  2624.     else if (__comp(*__first2, *__first1)) {
  2625.       *__result = *__first2;
  2626.       ++__first2;
  2627.     }
  2628.     else {
  2629.       *__result = *__first1;
  2630.       ++__first1;
  2631.       ++__first2;
  2632.     }
  2633.     ++__result;
  2634.   }
  2635.   return copy(__first2, __last2, copy(__first1, __last1, __result));
  2636. }
  2638. template <class _InputIter1, class _InputIter2, class _OutputIter>
  2639. _OutputIter set_intersection(_InputIter1 __first1, _InputIter1 __last1,
  2640.                              _InputIter2 __first2, _InputIter2 __last2,
  2641.                              _OutputIter __result) {
  2642.   __STL_REQUIRES(_InputIter1, _InputIterator);
  2643.   __STL_REQUIRES(_InputIter2, _InputIterator);
  2644.   __STL_REQUIRES(_OutputIter, _OutputIterator);
  2645.   __STL_REQUIRES_SAME_TYPE(
  2646.        typename iterator_traits<_InputIter1>::value_type,
  2647.        typename iterator_traits<_InputIter2>::value_type);
  2648.   __STL_REQUIRES(typename iterator_traits<_InputIter1>::value_type,
  2649.                  _LessThanComparable);
  2650.   while (__first1 != __last1 && __first2 != __last2) 
  2651.     if (*__first1 < *__first2) 
  2652.       ++__first1;
  2653.     else if (*__first2 < *__first1) 
  2654.       ++__first2;
  2655.     else {
  2656.       *__result = *__first1;
  2657.       ++__first1;
  2658.       ++__first2;
  2659.       ++__result;
  2660.     }
  2661.   return __result;
  2662. }
  2664. template <class _InputIter1, class _InputIter2, class _OutputIter,
  2665.           class _Compare>
  2666. _OutputIter set_intersection(_InputIter1 __first1, _InputIter1 __last1,
  2667.                              _InputIter2 __first2, _InputIter2 __last2,
  2668.                              _OutputIter __result, _Compare __comp) {
  2669.   __STL_REQUIRES(_InputIter1, _InputIterator);
  2670.   __STL_REQUIRES(_InputIter2, _InputIterator);
  2671.   __STL_REQUIRES(_OutputIter, _OutputIterator);
  2672.   __STL_REQUIRES_SAME_TYPE(
  2673.        typename iterator_traits<_InputIter1>::value_type,
  2674.        typename iterator_traits<_InputIter2>::value_type);
  2675.   __STL_BINARY_FUNCTION_CHECK(_Compare, bool,
  2676.        typename iterator_traits<_InputIter1>::value_type,
  2677.        typename iterator_traits<_InputIter2>::value_type);
  2679.   while (__first1 != __last1 && __first2 != __last2)
  2680.     if (__comp(*__first1, *__first2))
  2681.       ++__first1;
  2682.     else if (__comp(*__first2, *__first1))
  2683.       ++__first2;
  2684.     else {
  2685.       *__result = *__first1;
  2686.       ++__first1;
  2687.       ++__first2;
  2688.       ++__result;
  2689.     }
  2690.   return __result;
  2691. }
  2693. template <class _InputIter1, class _InputIter2, class _OutputIter>
  2694. _OutputIter set_difference(_InputIter1 __first1, _InputIter1 __last1,
  2695.                            _InputIter2 __first2, _InputIter2 __last2,
  2696.                            _OutputIter __result) {
  2697.   __STL_REQUIRES(_InputIter1, _InputIterator);
  2698.   __STL_REQUIRES(_InputIter2, _InputIterator);
  2699.   __STL_REQUIRES(_OutputIter, _OutputIterator);
  2700.   __STL_REQUIRES_SAME_TYPE(
  2701.        typename iterator_traits<_InputIter1>::value_type,
  2702.        typename iterator_traits<_InputIter2>::value_type);
  2703.   __STL_REQUIRES(typename iterator_traits<_InputIter1>::value_type,
  2704.                  _LessThanComparable);
  2705.   while (__first1 != __last1 && __first2 != __last2)
  2706.     if (*__first1 < *__first2) {
  2707.       *__result = *__first1;
  2708.       ++__first1;
  2709.       ++__result;
  2710.     }
  2711.     else if (*__first2 < *__first1)
  2712.       ++__first2;
  2713.     else {
  2714.       ++__first1;
  2715.       ++__first2;
  2716.     }
  2717.   return copy(__first1, __last1, __result);
  2718. }
  2720. template <class _InputIter1, class _InputIter2, class _OutputIter, 
  2721.           class _Compare>
  2722. _OutputIter set_difference(_InputIter1 __first1, _InputIter1 __last1,
  2723.                            _InputIter2 __first2, _InputIter2 __last2, 
  2724.                            _OutputIter __result, _Compare __comp) {
  2725.   __STL_REQUIRES(_InputIter1, _InputIterator);
  2726.   __STL_REQUIRES(_InputIter2, _InputIterator);
  2727.   __STL_REQUIRES(_OutputIter, _OutputIterator);
  2728.   __STL_REQUIRES_SAME_TYPE(
  2729.        typename iterator_traits<_InputIter1>::value_type,
  2730.        typename iterator_traits<_InputIter2>::value_type);
  2731.   __STL_BINARY_FUNCTION_CHECK(_Compare, bool,
  2732.        typename iterator_traits<_InputIter1>::value_type,
  2733.        typename iterator_traits<_InputIter2>::value_type);
  2735.   while (__first1 != __last1 && __first2 != __last2)
  2736.     if (__comp(*__first1, *__first2)) {
  2737.       *__result = *__first1;
  2738.       ++__first1;
  2739.       ++__result;
  2740.     }
  2741.     else if (__comp(*__first2, *__first1))
  2742.       ++__first2;
  2743.     else {
  2744.       ++__first1;
  2745.       ++__first2;
  2746.     }
  2747.   return copy(__first1, __last1, __result);
  2748. }
  2750. template <class _InputIter1, class _InputIter2, class _OutputIter>
  2751. _OutputIter 
  2752. set_symmetric_difference(_InputIter1 __first1, _InputIter1 __last1,
  2753.                          _InputIter2 __first2, _InputIter2 __last2,
  2754.                          _OutputIter __result) {
  2755.   __STL_REQUIRES(_InputIter1, _InputIterator);
  2756.   __STL_REQUIRES(_InputIter2, _InputIterator);
  2757.   __STL_REQUIRES(_OutputIter, _OutputIterator);
  2758.   __STL_REQUIRES_SAME_TYPE(
  2759.        typename iterator_traits<_InputIter1>::value_type,
  2760.        typename iterator_traits<_InputIter2>::value_type);
  2761.   __STL_REQUIRES(typename iterator_traits<_InputIter1>::value_type,
  2762.                  _LessThanComparable);
  2763.   while (__first1 != __last1 && __first2 != __last2)
  2764.     if (*__first1 < *__first2) {
  2765.       *__result = *__first1;
  2766.       ++__first1;
  2767.       ++__result;
  2768.     }
  2769.     else if (*__first2 < *__first1) {
  2770.       *__result = *__first2;
  2771.       ++__first2;
  2772.       ++__result;
  2773.     }
  2774.     else {
  2775.       ++__first1;
  2776.       ++__first2;
  2777.     }
  2778.   return copy(__first2, __last2, copy(__first1, __last1, __result));
  2779. }
  2781. template <class _InputIter1, class _InputIter2, class _OutputIter,
  2782.           class _Compare>
  2783. _OutputIter 
  2784. set_symmetric_difference(_InputIter1 __first1, _InputIter1 __last1,
  2785.                          _InputIter2 __first2, _InputIter2 __last2,
  2786.                          _OutputIter __result,
  2787.                          _Compare __comp) {
  2788.   __STL_REQUIRES(_InputIter1, _InputIterator);
  2789.   __STL_REQUIRES(_InputIter2, _InputIterator);
  2790.   __STL_REQUIRES(_OutputIter, _OutputIterator);
  2791.   __STL_REQUIRES_SAME_TYPE(
  2792.        typename iterator_traits<_InputIter1>::value_type,
  2793.        typename iterator_traits<_InputIter2>::value_type);
  2794.   __STL_BINARY_FUNCTION_CHECK(_Compare, bool,
  2795.        typename iterator_traits<_InputIter1>::value_type,
  2796.        typename iterator_traits<_InputIter2>::value_type);
  2797.   while (__first1 != __last1 && __first2 != __last2)
  2798.     if (__comp(*__first1, *__first2)) {
  2799.       *__result = *__first1;
  2800.       ++__first1;
  2801.       ++__result;
  2802.     }
  2803.     else if (__comp(*__first2, *__first1)) {
  2804.       *__result = *__first2;
  2805.       ++__first2;
  2806.       ++__result;
  2807.     }
  2808.     else {
  2809.       ++__first1;
  2810.       ++__first2;
  2811.     }
  2812.   return copy(__first2, __last2, copy(__first1, __last1, __result));
  2813. }
  2815. // min_element and max_element, with and without an explicitly supplied
  2816. // comparison function.
  2818. template <class _ForwardIter>
  2819. _ForwardIter max_element(_ForwardIter __first, _ForwardIter __last) {
  2820.   __STL_REQUIRES(_ForwardIter, _ForwardIterator);
  2821.   __STL_REQUIRES(typename iterator_traits<_ForwardIter>::value_type,
  2822.                  _LessThanComparable);
  2823.   if (__first == __last) return __first;
  2824.   _ForwardIter __result = __first;
  2825.   while (++__first != __last) 
  2826.     if (*__result < *__first)
  2827.       __result = __first;
  2828.   return __result;
  2829. }
  2831. template <class _ForwardIter, class _Compare>
  2832. _ForwardIter max_element(_ForwardIter __first, _ForwardIter __last,
  2833.  _Compare __comp) {
  2834.   __STL_REQUIRES(_ForwardIter, _ForwardIterator);
  2835.   __STL_BINARY_FUNCTION_CHECK(_Compare, bool,
  2836.     typename iterator_traits<_ForwardIter>::value_type,
  2837.     typename iterator_traits<_ForwardIter>::value_type);
  2838.   if (__first == __last) return __first;
  2839.   _ForwardIter __result = __first;
  2840.   while (++__first != __last) 
  2841.     if (__comp(*__result, *__first)) __result = __first;
  2842.   return __result;
  2843. }
  2845. template <class _ForwardIter>
  2846. _ForwardIter min_element(_ForwardIter __first, _ForwardIter __last) {
  2847.   __STL_REQUIRES(_ForwardIter, _ForwardIterator);
  2848.   __STL_REQUIRES(typename iterator_traits<_ForwardIter>::value_type,
  2849.                  _LessThanComparable);
  2850.   if (__first == __last) return __first;
  2851.   _ForwardIter __result = __first;
  2852.   while (++__first != __last) 
  2853.     if (*__first < *__result)
  2854.       __result = __first;
  2855.   return __result;
  2856. }
  2858. template <class _ForwardIter, class _Compare>
  2859. _ForwardIter min_element(_ForwardIter __first, _ForwardIter __last,
  2860.  _Compare __comp) {
  2861.   __STL_REQUIRES(_ForwardIter, _ForwardIterator);
  2862.   __STL_BINARY_FUNCTION_CHECK(_Compare, bool,
  2863.     typename iterator_traits<_ForwardIter>::value_type,
  2864.     typename iterator_traits<_ForwardIter>::value_type);
  2865.   if (__first == __last) return __first;
  2866.   _ForwardIter __result = __first;
  2867.   while (++__first != __last) 
  2868.     if (__comp(*__first, *__result))
  2869.       __result = __first;
  2870.   return __result;
  2871. }
  2873. // next_permutation and prev_permutation, with and without an explicitly 
  2874. // supplied comparison function.
  2876. template <class _BidirectionalIter>
  2877. bool next_permutation(_BidirectionalIter __first, _BidirectionalIter __last) {
  2878.   __STL_REQUIRES(_BidirectionalIter, _BidirectionalIterator);
  2879.   __STL_REQUIRES(typename iterator_traits<_BidirectionalIter>::value_type,
  2880.                  _LessThanComparable);
  2881.   if (__first == __last)
  2882.     return false;
  2883.   _BidirectionalIter __i = __first;
  2884.   ++__i;
  2885.   if (__i == __last)
  2886.     return false;
  2887.   __i = __last;
  2888.   --__i;
  2890.   for(;;) {
  2891.     _BidirectionalIter __ii = __i;
  2892.     --__i;
  2893.     if (*__i < *__ii) {
  2894.       _BidirectionalIter __j = __last;
  2895.       while (!(*__i < *--__j))
  2896.         {}
  2897.       iter_swap(__i, __j);
  2898.       reverse(__ii, __last);
  2899.       return true;
  2900.     }
  2901.     if (__i == __first) {
  2902.       reverse(__first, __last);
  2903.       return false;
  2904.     }
  2905.   }
  2906. }
  2908. template <class _BidirectionalIter, class _Compare>
  2909. bool next_permutation(_BidirectionalIter __first, _BidirectionalIter __last,
  2910.                       _Compare __comp) {
  2911.   __STL_REQUIRES(_BidirectionalIter, _BidirectionalIterator);
  2912.   __STL_BINARY_FUNCTION_CHECK(_Compare, bool,
  2913.     typename iterator_traits<_BidirectionalIter>::value_type,
  2914.     typename iterator_traits<_BidirectionalIter>::value_type);
  2915.   if (__first == __last)
  2916.     return false;
  2917.   _BidirectionalIter __i = __first;
  2918.   ++__i;
  2919.   if (__i == __last)
  2920.     return false;
  2921.   __i = __last;
  2922.   --__i;
  2924.   for(;;) {
  2925.     _BidirectionalIter __ii = __i;
  2926.     --__i;
  2927.     if (__comp(*__i, *__ii)) {
  2928.       _BidirectionalIter __j = __last;
  2929.       while (!__comp(*__i, *--__j))
  2930.         {}
  2931.       iter_swap(__i, __j);
  2932.       reverse(__ii, __last);
  2933.       return true;
  2934.     }
  2935.     if (__i == __first) {
  2936.       reverse(__first, __last);
  2937.       return false;
  2938.     }
  2939.   }
  2940. }
  2942. template <class _BidirectionalIter>
  2943. bool prev_permutation(_BidirectionalIter __first, _BidirectionalIter __last) {
  2944.   __STL_REQUIRES(_BidirectionalIter, _BidirectionalIterator);
  2945.   __STL_REQUIRES(typename iterator_traits<_BidirectionalIter>::value_type,
  2946.                  _LessThanComparable);
  2947.   if (__first == __last)
  2948.     return false;
  2949.   _BidirectionalIter __i = __first;
  2950.   ++__i;
  2951.   if (__i == __last)
  2952.     return false;
  2953.   __i = __last;
  2954.   --__i;
  2956.   for(;;) {
  2957.     _BidirectionalIter __ii = __i;
  2958.     --__i;
  2959.     if (*__ii < *__i) {
  2960.       _BidirectionalIter __j = __last;
  2961.       while (!(*--__j < *__i))
  2962.         {}
  2963.       iter_swap(__i, __j);
  2964.       reverse(__ii, __last);
  2965.       return true;
  2966.     }
  2967.     if (__i == __first) {
  2968.       reverse(__first, __last);
  2969.       return false;
  2970.     }
  2971.   }
  2972. }
  2974. template <class _BidirectionalIter, class _Compare>
  2975. bool prev_permutation(_BidirectionalIter __first, _BidirectionalIter __last,
  2976.                       _Compare __comp) {
  2977.   __STL_REQUIRES(_BidirectionalIter, _BidirectionalIterator);
  2978.   __STL_BINARY_FUNCTION_CHECK(_Compare, bool,
  2979.     typename iterator_traits<_BidirectionalIter>::value_type,
  2980.     typename iterator_traits<_BidirectionalIter>::value_type);
  2981.   if (__first == __last)
  2982.     return false;
  2983.   _BidirectionalIter __i = __first;
  2984.   ++__i;
  2985.   if (__i == __last)
  2986.     return false;
  2987.   __i = __last;
  2988.   --__i;
  2990.   for(;;) {
  2991.     _BidirectionalIter __ii = __i;
  2992.     --__i;
  2993.     if (__comp(*__ii, *__i)) {
  2994.       _BidirectionalIter __j = __last;
  2995.       while (!__comp(*--__j, *__i))
  2996.         {}
  2997.       iter_swap(__i, __j);
  2998.       reverse(__ii, __last);
  2999.       return true;
  3000.     }
  3001.     if (__i == __first) {
  3002.       reverse(__first, __last);
  3003.       return false;
  3004.     }
  3005.   }
  3006. }
  3008. // find_first_of, with and without an explicitly supplied comparison function.
  3010. template <class _InputIter, class _ForwardIter>
  3011. _InputIter find_first_of(_InputIter __first1, _InputIter __last1,
  3012.                          _ForwardIter __first2, _ForwardIter __last2)
  3013. {
  3014.   __STL_REQUIRES(_InputIter, _InputIterator);
  3015.   __STL_REQUIRES(_ForwardIter, _ForwardIterator);
  3016.   __STL_REQUIRES_BINARY_OP(_OP_EQUAL, bool, 
  3017.      typename iterator_traits<_InputIter>::value_type,
  3018.      typename iterator_traits<_ForwardIter>::value_type);
  3020.   for ( ; __first1 != __last1; ++__first1) 
  3021.     for (_ForwardIter __iter = __first2; __iter != __last2; ++__iter)
  3022.       if (*__first1 == *__iter)
  3023.         return __first1;
  3024.   return __last1;
  3025. }
  3027. template <class _InputIter, class _ForwardIter, class _BinaryPredicate>
  3028. _InputIter find_first_of(_InputIter __first1, _InputIter __last1,
  3029.                          _ForwardIter __first2, _ForwardIter __last2,
  3030.                          _BinaryPredicate __comp)
  3031. {
  3032.   __STL_REQUIRES(_InputIter, _InputIterator);
  3033.   __STL_REQUIRES(_ForwardIter, _ForwardIterator);
  3034.   __STL_BINARY_FUNCTION_CHECK(_BinaryPredicate, bool,
  3035.      typename iterator_traits<_InputIter>::value_type,
  3036.      typename iterator_traits<_ForwardIter>::value_type);
  3038.   for ( ; __first1 != __last1; ++__first1) 
  3039.     for (_ForwardIter __iter = __first2; __iter != __last2; ++__iter)
  3040.       if (__comp(*__first1, *__iter))
  3041.         return __first1;
  3042.   return __last1;
  3043. }
  3046. // find_end, with and without an explicitly supplied comparison function.
  3047. // Search [first2, last2) as a subsequence in [first1, last1), and return
  3048. // the *last* possible match.  Note that find_end for bidirectional iterators
  3049. // is much faster than for forward iterators.
  3051. // find_end for forward iterators. 
  3052. template <class _ForwardIter1, class _ForwardIter2>
  3053. _ForwardIter1 __find_end(_ForwardIter1 __first1, _ForwardIter1 __last1,
  3054.                          _ForwardIter2 __first2, _ForwardIter2 __last2,
  3055.                          forward_iterator_tag, forward_iterator_tag)
  3056. {
  3057.   if (__first2 == __last2)
  3058.     return __last1;
  3059.   else {
  3060.     _ForwardIter1 __result = __last1;
  3061.     while (1) {
  3062.       _ForwardIter1 __new_result
  3063.         = search(__first1, __last1, __first2, __last2);
  3064.       if (__new_result == __last1)
  3065.         return __result;
  3066.       else {
  3067.         __result = __new_result;
  3068.         __first1 = __new_result;
  3069.         ++__first1;
  3070.       }
  3071.     }
  3072.   }
  3073. }
  3075. template <class _ForwardIter1, class _ForwardIter2,
  3076.           class _BinaryPredicate>
  3077. _ForwardIter1 __find_end(_ForwardIter1 __first1, _ForwardIter1 __last1,
  3078.                          _ForwardIter2 __first2, _ForwardIter2 __last2,
  3079.                          forward_iterator_tag, forward_iterator_tag,
  3080.                          _BinaryPredicate __comp)
  3081. {
  3082.   if (__first2 == __last2)
  3083.     return __last1;
  3084.   else {
  3085.     _ForwardIter1 __result = __last1;
  3086.     while (1) {
  3087.       _ForwardIter1 __new_result
  3088.         = search(__first1, __last1, __first2, __last2, __comp);
  3089.       if (__new_result == __last1)
  3090.         return __result;
  3091.       else {
  3092.         __result = __new_result;
  3093.         __first1 = __new_result;
  3094.         ++__first1;
  3095.       }
  3096.     }
  3097.   }
  3098. }
  3100. // find_end for bidirectional iterators.  Requires partial specialization.
  3101. #ifdef __STL_CLASS_PARTIAL_SPECIALIZATION
  3103. template <class _BidirectionalIter1, class _BidirectionalIter2>
  3104. _BidirectionalIter1
  3105. __find_end(_BidirectionalIter1 __first1, _BidirectionalIter1 __last1,
  3106.            _BidirectionalIter2 __first2, _BidirectionalIter2 __last2,
  3107.            bidirectional_iterator_tag, bidirectional_iterator_tag)
  3108. {
  3109.   __STL_REQUIRES(_BidirectionalIter1, _BidirectionalIterator);
  3110.   __STL_REQUIRES(_BidirectionalIter2, _BidirectionalIterator);
  3111.   typedef reverse_iterator<_BidirectionalIter1> _RevIter1;
  3112.   typedef reverse_iterator<_BidirectionalIter2> _RevIter2;
  3114.   _RevIter1 __rlast1(__first1);
  3115.   _RevIter2 __rlast2(__first2);
  3116.   _RevIter1 __rresult = search(_RevIter1(__last1), __rlast1,
  3117.                                _RevIter2(__last2), __rlast2);
  3119.   if (__rresult == __rlast1)
  3120.     return __last1;
  3121.   else {
  3122.     _BidirectionalIter1 __result = __rresult.base();
  3123.     advance(__result, -distance(__first2, __last2));
  3124.     return __result;
  3125.   }
  3126. }
  3128. template <class _BidirectionalIter1, class _BidirectionalIter2,
  3129.           class _BinaryPredicate>
  3130. _BidirectionalIter1
  3131. __find_end(_BidirectionalIter1 __first1, _BidirectionalIter1 __last1,
  3132.            _BidirectionalIter2 __first2, _BidirectionalIter2 __last2,
  3133.            bidirectional_iterator_tag, bidirectional_iterator_tag, 
  3134.            _BinaryPredicate __comp)
  3135. {
  3136.   __STL_REQUIRES(_BidirectionalIter1, _BidirectionalIterator);
  3137.   __STL_REQUIRES(_BidirectionalIter2, _BidirectionalIterator);
  3138.   typedef reverse_iterator<_BidirectionalIter1> _RevIter1;
  3139.   typedef reverse_iterator<_BidirectionalIter2> _RevIter2;
  3141.   _RevIter1 __rlast1(__first1);
  3142.   _RevIter2 __rlast2(__first2);
  3143.   _RevIter1 __rresult = search(_RevIter1(__last1), __rlast1,
  3144.                                _RevIter2(__last2), __rlast2,
  3145.                                __comp);
  3147.   if (__rresult == __rlast1)
  3148.     return __last1;
  3149.   else {
  3150.     _BidirectionalIter1 __result = __rresult.base();
  3151.     advance(__result, -distance(__first2, __last2));
  3152.     return __result;
  3153.   }
  3154. }
  3155. #endif /* __STL_CLASS_PARTIAL_SPECIALIZATION */
  3157. // Dispatching functions for find_end.
  3159. template <class _ForwardIter1, class _ForwardIter2>
  3160. inline _ForwardIter1 
  3161. find_end(_ForwardIter1 __first1, _ForwardIter1 __last1, 
  3162.          _ForwardIter2 __first2, _ForwardIter2 __last2)
  3163. {
  3164.   __STL_REQUIRES(_ForwardIter1, _ForwardIterator);
  3165.   __STL_REQUIRES(_ForwardIter2, _ForwardIterator);
  3166.   __STL_REQUIRES_BINARY_OP(_OP_EQUAL, bool,
  3167.    typename iterator_traits<_ForwardIter1>::value_type,
  3168.    typename iterator_traits<_ForwardIter2>::value_type);
  3169.   return __find_end(__first1, __last1, __first2, __last2,
  3170.                     __ITERATOR_CATEGORY(__first1),
  3171.                     __ITERATOR_CATEGORY(__first2));
  3172. }
  3174. template <class _ForwardIter1, class _ForwardIter2, 
  3175.           class _BinaryPredicate>
  3176. inline _ForwardIter1 
  3177. find_end(_ForwardIter1 __first1, _ForwardIter1 __last1, 
  3178.          _ForwardIter2 __first2, _ForwardIter2 __last2,
  3179.          _BinaryPredicate __comp)
  3180. {
  3181.   __STL_REQUIRES(_ForwardIter1, _ForwardIterator);
  3182.   __STL_REQUIRES(_ForwardIter2, _ForwardIterator);
  3183.   __STL_BINARY_FUNCTION_CHECK(_BinaryPredicate, bool,
  3184.    typename iterator_traits<_ForwardIter1>::value_type,
  3185.    typename iterator_traits<_ForwardIter2>::value_type);
  3187.   return __find_end(__first1, __last1, __first2, __last2,
  3188.                     __ITERATOR_CATEGORY(__first1),
  3189.                     __ITERATOR_CATEGORY(__first2),
  3190.                     __comp);
  3191. }
  3193. // is_heap, a predicate testing whether or not a range is
  3194. // a heap.  This function is an extension, not part of the C++
  3195. // standard.
  3197. template <class _RandomAccessIter, class _Distance>
  3198. bool __is_heap(_RandomAccessIter __first, _Distance __n)
  3199. {
  3200.   _Distance __parent = 0;
  3201.   for (_Distance __child = 1; __child < __n; ++__child) {
  3202.     if (__first[__parent] < __first[__child]) 
  3203.       return false;
  3204.     if ((__child & 1) == 0)
  3205.       ++__parent;
  3206.   }
  3207.   return true;
  3208. }
  3210. template <class _RandomAccessIter, class _Distance, class _StrictWeakOrdering>
  3211. bool __is_heap(_RandomAccessIter __first, _StrictWeakOrdering __comp,
  3212.                _Distance __n)
  3213. {
  3214.   _Distance __parent = 0;
  3215.   for (_Distance __child = 1; __child < __n; ++__child) {
  3216.     if (__comp(__first[__parent], __first[__child]))
  3217.       return false;
  3218.     if ((__child & 1) == 0)
  3219.       ++__parent;
  3220.   }
  3221.   return true;
  3222. }
  3224. template <class _RandomAccessIter>
  3225. inline bool is_heap(_RandomAccessIter __first, _RandomAccessIter __last)
  3226. {
  3227.   __STL_REQUIRES(_RandomAccessIter, _RandomAccessIterator);
  3228.   __STL_REQUIRES(typename iterator_traits<_RandomAccessIter>::value_type,
  3229.                  _LessThanComparable);
  3230.   return __is_heap(__first, __last - __first);
  3231. }
  3234. template <class _RandomAccessIter, class _StrictWeakOrdering>
  3235. inline bool is_heap(_RandomAccessIter __first, _RandomAccessIter __last,
  3236.                     _StrictWeakOrdering __comp)
  3237. {
  3238.   __STL_REQUIRES(_RandomAccessIter, _RandomAccessIterator);
  3239.   __STL_BINARY_FUNCTION_CHECK(_StrictWeakOrdering, bool, 
  3240.          typename iterator_traits<_RandomAccessIter>::value_type, 
  3241.          typename iterator_traits<_RandomAccessIter>::value_type);
  3242.   return __is_heap(__first, __comp, __last - __first);
  3243. }
  3245. // is_sorted, a predicated testing whether a range is sorted in
  3246. // nondescending order.  This is an extension, not part of the C++
  3247. // standard.
  3249. template <class _ForwardIter>
  3250. bool is_sorted(_ForwardIter __first, _ForwardIter __last)
  3251. {
  3252.   __STL_REQUIRES(_ForwardIter, _ForwardIterator);
  3253.   __STL_REQUIRES(typename iterator_traits<_ForwardIter>::value_type,
  3254.                  _LessThanComparable);
  3255.   if (__first == __last)
  3256.     return true;
  3258.   _ForwardIter __next = __first;
  3259.   for (++__next; __next != __last; __first = __next, ++__next) {
  3260.     if (*__next < *__first)
  3261.       return false;
  3262.   }
  3264.   return true;
  3265. }
  3267. template <class _ForwardIter, class _StrictWeakOrdering>
  3268. bool is_sorted(_ForwardIter __first, _ForwardIter __last,
  3269.                _StrictWeakOrdering __comp)
  3270. {
  3271.   __STL_REQUIRES(_ForwardIter, _ForwardIterator);
  3272.   __STL_BINARY_FUNCTION_CHECK(_StrictWeakOrdering, bool, 
  3273.         typename iterator_traits<_ForwardIter>::value_type,
  3274.         typename iterator_traits<_ForwardIter>::value_type);
  3275.   if (__first == __last)
  3276.     return true;
  3278.   _ForwardIter __next = __first;
  3279.   for (++__next; __next != __last; __first = __next, ++__next) {
  3280.     if (__comp(*__next, *__first))
  3281.       return false;
  3282.   }
  3284.   return true;
  3285. }
  3287. #if defined(__sgi) && !defined(__GNUC__) && (_MIPS_SIM != _MIPS_SIM_ABI32)
  3288. #pragma reset woff 1209
  3289. #endif
  3291. __STL_END_NAMESPACE
  3293. #endif /* __SGI_STL_INTERNAL_ALGO_H */
  3295. // Local Variables:
  3296. // mode:C++
  3297. // End: