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