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