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

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