libstdc++-v3/include/bits/stl_algo.h

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