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