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