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

   1 // Algorithm implementation -*- 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   /**
  73    *  @brief Find the median of three values.
  74    *  @param  a  A value.
  75    *  @param  b  A value.
  76    *  @param  c  A value.
  77    *  @return One of @p a, @p b or @p c.
  78    *
  79    *  If @c {l,m,n} is some convolution of @p {a,b,c} such that @c l<=m<=n
  80    *  then the value returned will be @c m.
  81    *  This is an SGI extension.
  82    *  @ingroup SGIextensions
  83   */
  84   template<typename _Tp>
  85   inline const _Tp&
  86     __median(const _Tp& __a, const _Tp& __b, const _Tp& __c)
  87     {
  88       // concept requirements
  89       __glibcpp_function_requires(_LessThanComparableConcept<_Tp>)
  90       if (__a < __b)
  91         if (__b < __c)
  92           return __b;
  93         else if (__a < __c)
  94           return __c;
  95         else
  96           return __a;
  97       else if (__a < __c)
  98         return __a;
  99       else if (__b < __c)
 100         return __c;
 101       else
 102         return __b;
 103     }
 104
 105   /**
 106    *  @brief Find the median of three values using a predicate for comparison.
 107    *  @param  a     A value.
 108    *  @param  b     A value.
 109    *  @param  c     A value.
 110    *  @param  comp  A binary predicate.
 111    *  @return One of @p a, @p b or @p c.
 112    *
 113    *  If @c {l,m,n} is some convolution of @p {a,b,c} such that @p comp(l,m)
 114    *  and @p comp(m,n) are both true then the value returned will be @c m.
 115    *  This is an SGI extension.
 116    *  @ingroup SGIextensions
 117   */
 118   template<typename _Tp, typename _Compare>
 119     inline const _Tp&
 120     __median(const _Tp& __a, const _Tp& __b, const _Tp& __c, _Compare __comp)
 121     {
 122       // concept requirements
 123       __glibcpp_function_requires(_BinaryFunctionConcept<_Compare,bool,_Tp,_Tp>)
 124       if (__comp(__a, __b))
 125         if (__comp(__b, __c))
 126           return __b;
 127         else if (__comp(__a, __c))
 128           return __c;
 129         else
 130           return __a;
 131       else if (__comp(__a, __c))
 132         return __a;
 133       else if (__comp(__b, __c))
 134         return __c;
 135       else
 136         return __b;
 137     }
 138
 139   /**
 140    *  @brief Apply a function to every element of a sequence.
 141    *  @param  first  An input iterator.
 142    *  @param  last   An input iterator.
 143    *  @param  f      A unary function object.
 144    *  @return   @p f.
 145    *
 146    *  Applies the function object @p f to each element in the range
 147    *  @p [first,last).  @p f must not modify the order of the sequence.
 148    *  If @p f has a return value it is ignored.
 149   */
 150   template<typename _InputIter, typename _Function>
 151     _Function
 152     for_each(_InputIter __first, _InputIter __last, _Function __f)
 153     {
 154       // concept requirements
 155       __glibcpp_function_requires(_InputIteratorConcept<_InputIter>)
 156       for ( ; __first != __last; ++__first)
 157         __f(*__first);
 158       return __f;
 159     }
 160
 161   /**
 162    *  @if maint
 163    *  This is an overload used by find() for the Input Iterator case.
 164    *  @endif
 165   */
 166   template<typename _InputIter, typename _Tp>
 167     inline _InputIter
 168     find(_InputIter __first, _InputIter __last,
 169          const _Tp& __val,
 170          input_iterator_tag)
 171     {
 172       while (__first != __last && !(*__first == __val))
 173         ++__first;
 174       return __first;
 175     }
 176
 177   /**
 178    *  @if maint
 179    *  This is an overload used by find_if() for the Input Iterator case.
 180    *  @endif
 181   */
 182   template<typename _InputIter, typename _Predicate>
 183     inline _InputIter
 184     find_if(_InputIter __first, _InputIter __last,
 185             _Predicate __pred,
 186             input_iterator_tag)
 187     {
 188       while (__first != __last && !__pred(*__first))
 189         ++__first;
 190       return __first;
 191     }
 192
 193   /**
 194    *  @if maint
 195    *  This is an overload used by find() for the RAI case.
 196    *  @endif
 197   */
 198   template<typename _RandomAccessIter, typename _Tp>
 199     _RandomAccessIter
 200     find(_RandomAccessIter __first, _RandomAccessIter __last,
 201          const _Tp& __val,
 202          random_access_iterator_tag)
 203     {
 204       typename iterator_traits<_RandomAccessIter>::difference_type __trip_count
 205         = (__last - __first) >> 2;
 206
 207       for ( ; __trip_count > 0 ; --__trip_count) {
 208         if (*__first == __val) return __first;
 209         ++__first;
 210
 211         if (*__first == __val) return __first;
 212         ++__first;
 213
 214         if (*__first == __val) return __first;
 215         ++__first;
 216
 217         if (*__first == __val) return __first;
 218         ++__first;
 219       }
 220
 221       switch(__last - __first) {
 222       case 3:
 223         if (*__first == __val) return __first;
 224         ++__first;
 225       case 2:
 226         if (*__first == __val) return __first;
 227         ++__first;
 228       case 1:
 229         if (*__first == __val) return __first;
 230         ++__first;
 231       case 0:
 232       default:
 233         return __last;
 234       }
 235     }
 236
 237   /**
 238    *  @if maint
 239    *  This is an overload used by find_if() for the RAI case.
 240    *  @endif
 241   */
 242   template<typename _RandomAccessIter, typename _Predicate>
 243     _RandomAccessIter
 244     find_if(_RandomAccessIter __first, _RandomAccessIter __last,
 245             _Predicate __pred,
 246             random_access_iterator_tag)
 247     {
 248       typename iterator_traits<_RandomAccessIter>::difference_type __trip_count
 249         = (__last - __first) >> 2;
 250
 251       for ( ; __trip_count > 0 ; --__trip_count) {
 252         if (__pred(*__first)) return __first;
 253         ++__first;
 254
 255         if (__pred(*__first)) return __first;
 256         ++__first;
 257
 258         if (__pred(*__first)) return __first;
 259         ++__first;
 260
 261         if (__pred(*__first)) return __first;
 262         ++__first;
 263       }
 264
 265       switch(__last - __first) {
 266       case 3:
 267         if (__pred(*__first)) return __first;
 268         ++__first;
 269       case 2:
 270         if (__pred(*__first)) return __first;
 271         ++__first;
 272       case 1:
 273         if (__pred(*__first)) return __first;
 274         ++__first;
 275       case 0:
 276       default:
 277         return __last;
 278       }
 279     }
 280
 281   /**
 282    *  @brief Find the first occurrence of a value in a sequence.
 283    *  @param  first  An input iterator.
 284    *  @param  last   An input iterator.
 285    *  @param  val    The value to find.
 286    *  @return   The first iterator @c i in the range @p [first,last)
 287    *  such that @c *i == @p val, or @p last if no such iterator exists.
 288   */
 289   template<typename _InputIter, typename _Tp>
 290     inline _InputIter
 291     find(_InputIter __first, _InputIter __last,
 292          const _Tp& __val)
 293     {
 294       // concept requirements
 295       __glibcpp_function_requires(_InputIteratorConcept<_InputIter>)
 296       __glibcpp_function_requires(_EqualOpConcept<
 297                 typename iterator_traits<_InputIter>::value_type, _Tp>)
 298       return find(__first, __last, __val, __iterator_category(__first));
 299     }
 300
 301   /**
 302    *  @brief Find the first element in a sequence for which a predicate is true.
 303    *  @param  first  An input iterator.
 304    *  @param  last   An input iterator.
 305    *  @param  pred   A predicate.
 306    *  @return   The first iterator @c i in the range @p [first,last)
 307    *  such that @p pred(*i) is true, or @p last if no such iterator exists.
 308   */
 309   template<typename _InputIter, typename _Predicate>
 310     inline _InputIter
 311     find_if(_InputIter __first, _InputIter __last,
 312             _Predicate __pred)
 313     {
 314       // concept requirements
 315       __glibcpp_function_requires(_InputIteratorConcept<_InputIter>)
 316       __glibcpp_function_requires(_UnaryPredicateConcept<_Predicate,
 317               typename iterator_traits<_InputIter>::value_type>)
 318       return find_if(__first, __last, __pred, __iterator_category(__first));
 319     }
 320
 321   /**
 322    *  @brief Find two adjacent values in a sequence that are equal.
 323    *  @param  first  A forward iterator.
 324    *  @param  last   A forward iterator.
 325    *  @return   The first iterator @c i such that @c i and @c i+1 are both
 326    *  valid iterators in @p [first,last) and such that @c *i == @c *(i+1),
 327    *  or @p last if no such iterator exists.
 328   */
 329   template<typename _ForwardIter>
 330     _ForwardIter
 331     adjacent_find(_ForwardIter __first, _ForwardIter __last)
 332     {
 333       // concept requirements
 334       __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter>)
 335       __glibcpp_function_requires(_EqualityComparableConcept<
 336             typename iterator_traits<_ForwardIter>::value_type>)
 337       if (__first == __last)
 338         return __last;
 339       _ForwardIter __next = __first;
 340       while(++__next != __last) {
 341         if (*__first == *__next)
 342           return __first;
 343         __first = __next;
 344       }
 345       return __last;
 346     }
 347
 348   /**
 349    *  @brief Find two adjacent values in a sequence using a predicate.
 350    *  @param  first         A forward iterator.
 351    *  @param  last          A forward iterator.
 352    *  @param  binary_pred   A binary predicate.
 353    *  @return   The first iterator @c i such that @c i and @c i+1 are both
 354    *  valid iterators in @p [first,last) and such that
 355    *  @p binary_pred(*i,*(i+1)) is true, or @p last if no such iterator
 356    *  exists.
 357   */
 358   template<typename _ForwardIter, typename _BinaryPredicate>
 359     _ForwardIter
 360     adjacent_find(_ForwardIter __first, _ForwardIter __last,
 361                   _BinaryPredicate __binary_pred)
 362     {
 363       // concept requirements
 364       __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter>)
 365       __glibcpp_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
 366             typename iterator_traits<_ForwardIter>::value_type,
 367             typename iterator_traits<_ForwardIter>::value_type>)
 368       if (__first == __last)
 369         return __last;
 370       _ForwardIter __next = __first;
 371       while(++__next != __last) {
 372         if (__binary_pred(*__first, *__next))
 373           return __first;
 374         __first = __next;
 375       }
 376       return __last;
 377     }
 378
 379   /**
 380    *  @brief Count the number of copies of a value in a sequence.
 381    *  @param  first  An input iterator.
 382    *  @param  last   An input iterator.
 383    *  @param  value  The value to be counted.
 384    *  @return   The number of iterators @c i in the range @p [first,last)
 385    *  for which @c *i == @p value
 386   */
 387   template<typename _InputIter, typename _Tp>
 388     typename iterator_traits<_InputIter>::difference_type
 389     count(_InputIter __first, _InputIter __last, const _Tp& __value)
 390     {
 391       // concept requirements
 392       __glibcpp_function_requires(_InputIteratorConcept<_InputIter>)
 393       __glibcpp_function_requires(_EqualityComparableConcept<
 394             typename iterator_traits<_InputIter>::value_type >)
 395       __glibcpp_function_requires(_EqualityComparableConcept<_Tp>)
 396       typename iterator_traits<_InputIter>::difference_type __n = 0;
 397       for ( ; __first != __last; ++__first)
 398         if (*__first == __value)
 399           ++__n;
 400       return __n;
 401     }
 402
 403   /**
 404    *  @brief Count the elements of a sequence for which a predicate is true.
 405    *  @param  first  An input iterator.
 406    *  @param  last   An input iterator.
 407    *  @param  pred   A predicate.
 408    *  @return   The number of iterators @c i in the range @p [first,last)
 409    *  for which @p pred(*i) is true.
 410   */
 411   template<typename _InputIter, typename _Predicate>
 412     typename iterator_traits<_InputIter>::difference_type
 413     count_if(_InputIter __first, _InputIter __last, _Predicate __pred)
 414     {
 415       // concept requirements
 416       __glibcpp_function_requires(_InputIteratorConcept<_InputIter>)
 417       __glibcpp_function_requires(_UnaryPredicateConcept<_Predicate,
 418             typename iterator_traits<_InputIter>::value_type>)
 419       typename iterator_traits<_InputIter>::difference_type __n = 0;
 420       for ( ; __first != __last; ++__first)
 421         if (__pred(*__first))
 422           ++__n;
 423       return __n;
 424     }
 425
 426
 427   /**
 428    *  @brief Search a sequence for a matching sub-sequence.
 429    *  @param  first1  A forward iterator.
 430    *  @param  last1   A forward iterator.
 431    *  @param  first2  A forward iterator.
 432    *  @param  last2   A forward iterator.
 433    *  @return   The first iterator @c i in the range
 434    *  @p [first1,last1-(last2-first2)) such that @c *(i+N) == @p *(first2+N)
 435    *  for each @c N in the range @p [0,last2-first2), or @p last1 if no
 436    *  such iterator exists.
 437    *
 438    *  Searches the range @p [first1,last1) for a sub-sequence that compares
 439    *  equal value-by-value with the sequence given by @p [first2,last2) and
 440    *  returns an iterator to the first element of the sub-sequence, or
 441    *  @p last1 if the sub-sequence is not found.
 442    *
 443    *  Because the sub-sequence must lie completely within the range
 444    *  @p [first1,last1) it must start at a position less than
 445    *  @p last1-(last2-first2) where @p last2-first2 is the length of the
 446    *  sub-sequence.
 447    *  This means that the returned iterator @c i will be in the range
 448    *  @p [first1,last1-(last2-first2))
 449   */
 450   template<typename _ForwardIter1, typename _ForwardIter2>
 451     _ForwardIter1
 452     search(_ForwardIter1 __first1, _ForwardIter1 __last1,
 453            _ForwardIter2 __first2, _ForwardIter2 __last2)
 454     {
 455       // concept requirements
 456       __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter1>)
 457       __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter2>)
 458       __glibcpp_function_requires(_EqualOpConcept<
 459             typename iterator_traits<_ForwardIter1>::value_type,
 460             typename iterator_traits<_ForwardIter2>::value_type>)
 461
 462       // Test for empty ranges
 463       if (__first1 == __last1 || __first2 == __last2)
 464         return __first1;
 465
 466       // Test for a pattern of length 1.
 467       _ForwardIter2 __tmp(__first2);
 468       ++__tmp;
 469       if (__tmp == __last2)
 470         return find(__first1, __last1, *__first2);
 471
 472       // General case.
 473
 474       _ForwardIter2 __p1, __p;
 475
 476       __p1 = __first2; ++__p1;
 477
 478       _ForwardIter1 __current = __first1;
 479
 480       while (__first1 != __last1) {
 481         __first1 = find(__first1, __last1, *__first2);
 482         if (__first1 == __last1)
 483           return __last1;
 484
 485         __p = __p1;
 486         __current = __first1;
 487         if (++__current == __last1)
 488           return __last1;
 489
 490         while (*__current == *__p) {
 491           if (++__p == __last2)
 492             return __first1;
 493           if (++__current == __last1)
 494             return __last1;
 495         }
 496
 497         ++__first1;
 498       }
 499       return __first1;
 500     }
 501
 502   /**
 503    *  @brief Search a sequence for a matching sub-sequence using a predicate.
 504    *  @param  first1     A forward iterator.
 505    *  @param  last1      A forward iterator.
 506    *  @param  first2     A forward iterator.
 507    *  @param  last2      A forward iterator.
 508    *  @param  predicate  A binary predicate.
 509    *  @return   The first iterator @c i in the range
 510    *  @p [first1,last1-(last2-first2)) such that
 511    *  @p predicate(*(i+N),*(first2+N)) is true for each @c N in the range
 512    *  @p [0,last2-first2), or @p last1 if no such iterator exists.
 513    *
 514    *  Searches the range @p [first1,last1) for a sub-sequence that compares
 515    *  equal value-by-value with the sequence given by @p [first2,last2),
 516    *  using @p predicate to determine equality, and returns an iterator
 517    *  to the first element of the sub-sequence, or @p last1 if no such
 518    *  iterator exists.
 519    *
 520    *  @see search(_ForwardIter1, _ForwardIter1, _ForwardIter2, _ForwardIter2)
 521   */
 522   template<typename _ForwardIter1, typename _ForwardIter2, typename _BinaryPred>
 523     _ForwardIter1
 524     search(_ForwardIter1 __first1, _ForwardIter1 __last1,
 525            _ForwardIter2 __first2, _ForwardIter2 __last2,
 526            _BinaryPred  __predicate)
 527     {
 528       // concept requirements
 529       __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter1>)
 530       __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter2>)
 531       __glibcpp_function_requires(_BinaryPredicateConcept<_BinaryPred,
 532             typename iterator_traits<_ForwardIter1>::value_type,
 533             typename iterator_traits<_ForwardIter2>::value_type>)
 534
 535       // Test for empty ranges
 536       if (__first1 == __last1 || __first2 == __last2)
 537         return __first1;
 538
 539       // Test for a pattern of length 1.
 540       _ForwardIter2 __tmp(__first2);
 541       ++__tmp;
 542       if (__tmp == __last2) {
 543         while (__first1 != __last1 && !__predicate(*__first1, *__first2))
 544           ++__first1;
 545         return __first1;
 546       }
 547
 548       // General case.
 549
 550       _ForwardIter2 __p1, __p;
 551
 552       __p1 = __first2; ++__p1;
 553
 554       _ForwardIter1 __current = __first1;
 555
 556       while (__first1 != __last1) {
 557         while (__first1 != __last1) {
 558           if (__predicate(*__first1, *__first2))
 559             break;
 560           ++__first1;
 561         }
 562         while (__first1 != __last1 && !__predicate(*__first1, *__first2))
 563           ++__first1;
 564         if (__first1 == __last1)
 565           return __last1;
 566
 567         __p = __p1;
 568         __current = __first1;
 569         if (++__current == __last1) return __last1;
 570
 571         while (__predicate(*__current, *__p)) {
 572           if (++__p == __last2)
 573             return __first1;
 574           if (++__current == __last1)
 575             return __last1;
 576         }
 577
 578         ++__first1;
 579       }
 580       return __first1;
 581     }
 582
 583   /**
 584    *  @brief Search a sequence for a number of consecutive values.
 585    *  @param  first  A forward iterator.
 586    *  @param  last   A forward iterator.
 587    *  @param  count  The number of consecutive values.
 588    *  @param  val    The value to find.
 589    *  @return   The first iterator @c i in the range @p [first,last-count)
 590    *  such that @c *(i+N) == @p val for each @c N in the range @p [0,count),
 591    *  or @p last if no such iterator exists.
 592    *
 593    *  Searches the range @p [first,last) for @p count consecutive elements
 594    *  equal to @p val.
 595   */
 596   template<typename _ForwardIter, typename _Integer, typename _Tp>
 597     _ForwardIter
 598     search_n(_ForwardIter __first, _ForwardIter __last,
 599              _Integer __count, const _Tp& __val)
 600     {
 601       // concept requirements
 602       __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter>)
 603       __glibcpp_function_requires(_EqualityComparableConcept<
 604             typename iterator_traits<_ForwardIter>::value_type>)
 605       __glibcpp_function_requires(_EqualityComparableConcept<_Tp>)
 606
 607       if (__count <= 0)
 608         return __first;
 609       else {
 610         __first = find(__first, __last, __val);
 611         while (__first != __last) {
 612           _Integer __n = __count - 1;
 613           _ForwardIter __i = __first;
 614           ++__i;
 615           while (__i != __last && __n != 0 && *__i == __val) {
 616             ++__i;
 617             --__n;
 618           }
 619           if (__n == 0)
 620             return __first;
 621           else
 622             __first = find(__i, __last, __val);
 623         }
 624         return __last;
 625       }
 626     }
 627
 628   /**
 629    *  @brief Search a sequence for a number of consecutive values using a
 630    *         predicate.
 631    *  @param  first        A forward iterator.
 632    *  @param  last         A forward iterator.
 633    *  @param  count        The number of consecutive values.
 634    *  @param  val          The value to find.
 635    *  @param  binary_pred  A binary predicate.
 636    *  @return   The first iterator @c i in the range @p [first,last-count)
 637    *  such that @p binary_pred(*(i+N),val) is true for each @c N in the
 638    *  range @p [0,count), or @p last if no such iterator exists.
 639    *
 640    *  Searches the range @p [first,last) for @p count consecutive elements
 641    *  for which the predicate returns true.
 642   */
 643   template<typename _ForwardIter, typename _Integer, typename _Tp,
 644            typename _BinaryPred>
 645     _ForwardIter
 646     search_n(_ForwardIter __first, _ForwardIter __last,
 647              _Integer __count, const _Tp& __val,
 648              _BinaryPred __binary_pred)
 649     {
 650       // concept requirements
 651       __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter>)
 652       __glibcpp_function_requires(_BinaryPredicateConcept<_BinaryPred,
 653             typename iterator_traits<_ForwardIter>::value_type, _Tp>)
 654
 655       if (__count <= 0)
 656         return __first;
 657       else {
 658         while (__first != __last) {
 659           if (__binary_pred(*__first, __val))
 660             break;
 661           ++__first;
 662         }
 663         while (__first != __last) {
 664           _Integer __n = __count - 1;
 665           _ForwardIter __i = __first;
 666           ++__i;
 667           while (__i != __last && __n != 0 && __binary_pred(*__i, __val)) {
 668             ++__i;
 669             --__n;
 670           }
 671           if (__n == 0)
 672             return __first;
 673           else {
 674             while (__i != __last) {
 675               if (__binary_pred(*__i, __val))
 676                 break;
 677               ++__i;
 678             }
 679             __first = __i;
 680           }
 681         }
 682         return __last;
 683       }
 684     }
 685
 686   /**
 687    *  @brief Swap the elements of two sequences.
 688    *  @param  first1  A forward iterator.
 689    *  @param  last1   A forward iterator.
 690    *  @param  first2  A forward iterator.
 691    *  @return   An iterator equal to @p first2+(last1-first1).
 692    *
 693    *  Swaps each element in the range @p [first1,last1) with the
 694    *  corresponding element in the range @p [first2,(last1-first1)).
 695    *  The ranges must not overlap.
 696   */
 697   template<typename _ForwardIter1, typename _ForwardIter2>
 698     _ForwardIter2
 699     swap_ranges(_ForwardIter1 __first1, _ForwardIter1 __last1,
 700                 _ForwardIter2 __first2)
 701     {
 702       // concept requirements
 703       __glibcpp_function_requires(_Mutable_ForwardIteratorConcept<_ForwardIter1>)
 704       __glibcpp_function_requires(_Mutable_ForwardIteratorConcept<_ForwardIter2>)
 705       __glibcpp_function_requires(_ConvertibleConcept<
 706             typename iterator_traits<_ForwardIter1>::value_type,
 707             typename iterator_traits<_ForwardIter2>::value_type>)
 708       __glibcpp_function_requires(_ConvertibleConcept<
 709             typename iterator_traits<_ForwardIter2>::value_type,
 710             typename iterator_traits<_ForwardIter1>::value_type>)
 711
 712       for ( ; __first1 != __last1; ++__first1, ++__first2)
 713         iter_swap(__first1, __first2);
 714       return __first2;
 715     }
 716
 717   /**
 718    *  @brief Perform an operation on a sequence.
 719    *  @param  first     An input iterator.
 720    *  @param  last      An input iterator.
 721    *  @param  result    An output iterator.
 722    *  @param  unary_op  A unary operator.
 723    *  @return   An output iterator equal to @p result+(last-first).
 724    *
 725    *  Applies the operator to each element in the input range and assigns
 726    *  the results to successive elements of the output sequence.
 727    *  Evaluates @p *(result+N)=unary_op(*(first+N)) for each @c N in the
 728    *  range @p [0,last-first).
 729    *
 730    *  @p unary_op must not alter its argument.
 731   */
 732   template<typename _InputIter, typename _OutputIter, typename _UnaryOperation>
 733     _OutputIter
 734     transform(_InputIter __first, _InputIter __last,
 735               _OutputIter __result, _UnaryOperation __unary_op)
 736     {
 737       // concept requirements
 738       __glibcpp_function_requires(_InputIteratorConcept<_InputIter>)
 739       __glibcpp_function_requires(_OutputIteratorConcept<_OutputIter,
 740             // "the type returned by a _UnaryOperation"
 741             __typeof__(__unary_op(*__first))>)
 742
 743       for ( ; __first != __last; ++__first, ++__result)
 744         *__result = __unary_op(*__first);
 745       return __result;
 746     }
 747
 748   /**
 749    *  @brief Perform an operation on corresponding elements of two sequences.
 750    *  @param  first1     An input iterator.
 751    *  @param  last1      An input iterator.
 752    *  @param  first2     An input iterator.
 753    *  @param  result     An output iterator.
 754    *  @param  binary_op  A binary operator.
 755    *  @return   An output iterator equal to @p result+(last-first).
 756    *
 757    *  Applies the operator to the corresponding elements in the two
 758    *  input ranges and assigns the results to successive elements of the
 759    *  output sequence.
 760    *  Evaluates @p *(result+N)=binary_op(*(first1+N),*(first2+N)) for each
 761    *  @c N in the range @p [0,last1-first1).
 762    *
 763    *  @p binary_op must not alter either of its arguments.
 764   */
 765   template<typename _InputIter1, typename _InputIter2, typename _OutputIter,
 766            typename _BinaryOperation>
 767     _OutputIter
 768     transform(_InputIter1 __first1, _InputIter1 __last1,
 769               _InputIter2 __first2, _OutputIter __result,
 770               _BinaryOperation __binary_op)
 771     {
 772       // concept requirements
 773       __glibcpp_function_requires(_InputIteratorConcept<_InputIter1>)
 774       __glibcpp_function_requires(_InputIteratorConcept<_InputIter2>)
 775       __glibcpp_function_requires(_OutputIteratorConcept<_OutputIter,
 776             // "the type returned by a _BinaryOperation"
 777             __typeof__(__binary_op(*__first1,*__first2))>)
 778
 779       for ( ; __first1 != __last1; ++__first1, ++__first2, ++__result)
 780         *__result = __binary_op(*__first1, *__first2);
 781       return __result;
 782     }
 783
 784   /**
 785    *  @brief Replace each occurrence of one value in a sequence with another
 786    *         value.
 787    *  @param  first      A forward iterator.
 788    *  @param  last       A forward iterator.
 789    *  @param  old_value  The value to be replaced.
 790    *  @param  new_value  The replacement value.
 791    *  @return   replace() returns no value.
 792    *
 793    *  For each iterator @c i in the range @p [first,last) if @c *i ==
 794    *  @p old_value then the assignment @c *i = @p new_value is performed.
 795   */
 796   template<typename _ForwardIter, typename _Tp>
 797     void
 798     replace(_ForwardIter __first, _ForwardIter __last,
 799             const _Tp& __old_value, const _Tp& __new_value)
 800     {
 801       // concept requirements
 802       __glibcpp_function_requires(_Mutable_ForwardIteratorConcept<_ForwardIter>)
 803       __glibcpp_function_requires(_EqualOpConcept<
 804             typename iterator_traits<_ForwardIter>::value_type, _Tp>)
 805       __glibcpp_function_requires(_ConvertibleConcept<_Tp,
 806             typename iterator_traits<_ForwardIter>::value_type>)
 807
 808       for ( ; __first != __last; ++__first)
 809         if (*__first == __old_value)
 810           *__first = __new_value;
 811     }
 812
 813   /**
 814    *  @brief Replace each value in a sequence for which a predicate returns
 815    *         true with another value.
 816    *  @param  first      A forward iterator.
 817    *  @param  last       A forward iterator.
 818    *  @param  pred       A predicate.
 819    *  @param  new_value  The replacement value.
 820    *  @return   replace_if() returns no value.
 821    *
 822    *  For each iterator @c i in the range @p [first,last) if @p pred(*i)
 823    *  is true then the assignment @c *i = @p new_value is performed.
 824   */
 825   template<typename _ForwardIter, typename _Predicate, typename _Tp>
 826     void
 827     replace_if(_ForwardIter __first, _ForwardIter __last,
 828                _Predicate __pred, const _Tp& __new_value)
 829     {
 830       // concept requirements
 831       __glibcpp_function_requires(_Mutable_ForwardIteratorConcept<_ForwardIter>)
 832       __glibcpp_function_requires(_ConvertibleConcept<_Tp,
 833             typename iterator_traits<_ForwardIter>::value_type>)
 834       __glibcpp_function_requires(_UnaryPredicateConcept<_Predicate,
 835             typename iterator_traits<_ForwardIter>::value_type>)
 836
 837       for ( ; __first != __last; ++__first)
 838         if (__pred(*__first))
 839           *__first = __new_value;
 840     }
 841
 842   /**
 843    *  @brief Copy a sequence, replacing each element of one value with another
 844    *         value.
 845    *  @param  first      An input iterator.
 846    *  @param  last       An input iterator.
 847    *  @param  result     An output iterator.
 848    *  @param  old_value  The value to be replaced.
 849    *  @param  new_value  The replacement value.
 850    *  @return   The end of the output sequence, @p result+(last-first).
 851    *
 852    *  Copies each element in the input range @p [first,last) to the
 853    *  output range @p [result,result+(last-first)) replacing elements
 854    *  equal to @p old_value with @p new_value.
 855   */
 856   template<typename _InputIter, typename _OutputIter, typename _Tp>
 857     _OutputIter
 858     replace_copy(_InputIter __first, _InputIter __last,
 859                  _OutputIter __result,
 860                  const _Tp& __old_value, const _Tp& __new_value)
 861     {
 862       // concept requirements
 863       __glibcpp_function_requires(_InputIteratorConcept<_InputIter>)
 864       __glibcpp_function_requires(_OutputIteratorConcept<_OutputIter,
 865             typename iterator_traits<_InputIter>::value_type>)
 866       __glibcpp_function_requires(_EqualOpConcept<
 867             typename iterator_traits<_InputIter>::value_type, _Tp>)
 868
 869       for ( ; __first != __last; ++__first, ++__result)
 870         *__result = *__first == __old_value ? __new_value : *__first;
 871       return __result;
 872     }
 873
 874   /**
 875    *  @brief Copy a sequence, replacing each value for which a predicate
 876    *         returns true with another value.
 877    *  @param  first      An input iterator.
 878    *  @param  last       An input iterator.
 879    *  @param  result     An output iterator.
 880    *  @param  pred       A predicate.
 881    *  @param  new_value  The replacement value.
 882    *  @return   The end of the output sequence, @p result+(last-first).
 883    *
 884    *  Copies each element in the range @p [first,last) to the range
 885    *  @p [result,result+(last-first)) replacing elements for which
 886    *  @p pred returns true with @p new_value.
 887   */
 888   template<typename _InputIter, typename _OutputIter, typename _Predicate,
 889            typename _Tp>
 890     _OutputIter
 891     replace_copy_if(_InputIter __first, _InputIter __last,
 892                     _OutputIter __result,
 893                     _Predicate __pred, const _Tp& __new_value)
 894     {
 895       // concept requirements
 896       __glibcpp_function_requires(_InputIteratorConcept<_InputIter>)
 897       __glibcpp_function_requires(_OutputIteratorConcept<_OutputIter,
 898             typename iterator_traits<_InputIter>::value_type>)
 899       __glibcpp_function_requires(_UnaryPredicateConcept<_Predicate,
 900             typename iterator_traits<_InputIter>::value_type>)
 901
 902       for ( ; __first != __last; ++__first, ++__result)
 903         *__result = __pred(*__first) ? __new_value : *__first;
 904       return __result;
 905     }
 906
 907   /**
 908    *  @brief Assign the result of a function object to each value in a
 909    *         sequence.
 910    *  @param  first  A forward iterator.
 911    *  @param  last   A forward iterator.
 912    *  @param  gen    A function object taking no arguments.
 913    *  @return   generate() returns no value.
 914    *
 915    *  Performs the assignment @c *i = @p gen() for each @c i in the range
 916    *  @p [first,last).
 917   */
 918   template<typename _ForwardIter, typename _Generator>
 919     void
 920     generate(_ForwardIter __first, _ForwardIter __last, _Generator __gen)
 921     {
 922       // concept requirements
 923       __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter>)
 924       __glibcpp_function_requires(_GeneratorConcept<_Generator,
 925             typename iterator_traits<_ForwardIter>::value_type>)
 926
 927       for ( ; __first != __last; ++__first)
 928         *__first = __gen();
 929     }
 930
 931   /**
 932    *  @brief Assign the result of a function object to each value in a
 933    *         sequence.
 934    *  @param  first  A forward iterator.
 935    *  @param  n      The length of the sequence.
 936    *  @param  gen    A function object taking no arguments.
 937    *  @return   The end of the sequence, @p first+n
 938    *
 939    *  Performs the assignment @c *i = @p gen() for each @c i in the range
 940    *  @p [first,first+n).
 941   */
 942   template<typename _OutputIter, typename _Size, typename _Generator>
 943     _OutputIter
 944     generate_n(_OutputIter __first, _Size __n, _Generator __gen)
 945     {
 946       // concept requirements
 947       __glibcpp_function_requires(_OutputIteratorConcept<_OutputIter,
 948             // "the type returned by a _Generator"
 949             __typeof__(gen())>)
 950
 951       for ( ; __n > 0; --__n, ++__first)
 952         *__first = __gen();
 953       return __first;
 954     }
 955
 956   /**
 957    *  @brief Copy a sequence, removing elements of a given value.
 958    *  @param  first   An input iterator.
 959    *  @param  last    An input iterator.
 960    *  @param  result  An output iterator.
 961    *  @param  value   The value to be removed.
 962    *  @return   An iterator designating the end of the resulting sequence.
 963    *
 964    *  Copies each element in the range @p [first,last) not equal to @p value
 965    *  to the range beginning at @p result.
 966    *  remove_copy() is stable, so the relative order of elements that are
 967    *  copied is unchanged.
 968   */
 969   template<typename _InputIter, typename _OutputIter, typename _Tp>
 970     _OutputIter
 971     remove_copy(_InputIter __first, _InputIter __last,
 972                 _OutputIter __result, const _Tp& __value)
 973     {
 974       // concept requirements
 975       __glibcpp_function_requires(_InputIteratorConcept<_InputIter>)
 976       __glibcpp_function_requires(_OutputIteratorConcept<_OutputIter,
 977             typename iterator_traits<_InputIter>::value_type>)
 978       __glibcpp_function_requires(_EqualOpConcept<
 979             typename iterator_traits<_InputIter>::value_type, _Tp>)
 980
 981       for ( ; __first != __last; ++__first)
 982         if (!(*__first == __value)) {
 983           *__result = *__first;
 984           ++__result;
 985         }
 986       return __result;
 987     }
 988
 989   /**
 990    *  @brief Copy a sequence, removing elements for which a predicate is true.
 991    *  @param  first   An input iterator.
 992    *  @param  last    An input iterator.
 993    *  @param  result  An output iterator.
 994    *  @param  pred    A predicate.
 995    *  @return   An iterator designating the end of the resulting sequence.
 996    *
 997    *  Copies each element in the range @p [first,last) for which
 998    *  @p pred returns true to the range beginning at @p result.
 999    *
1000    *  remove_copy_if() is stable, so the relative order of elements that are
1001    *  copied is unchanged.
1002   */
1003   template<typename _InputIter, typename _OutputIter, typename _Predicate>
1004     _OutputIter
1005     remove_copy_if(_InputIter __first, _InputIter __last,
1006                    _OutputIter __result, _Predicate __pred)
1007     {
1008       // concept requirements
1009       __glibcpp_function_requires(_InputIteratorConcept<_InputIter>)
1010       __glibcpp_function_requires(_OutputIteratorConcept<_OutputIter,
1011             typename iterator_traits<_InputIter>::value_type>)
1012       __glibcpp_function_requires(_UnaryPredicateConcept<_Predicate,
1013             typename iterator_traits<_InputIter>::value_type>)
1014
1015       for ( ; __first != __last; ++__first)
1016         if (!__pred(*__first)) {
1017           *__result = *__first;
1018           ++__result;
1019         }
1020       return __result;
1021     }
1022
1023   /**
1024    *  @brief Remove elements from a sequence.
1025    *  @param  first  An input iterator.
1026    *  @param  last   An input iterator.
1027    *  @param  value  The value to be removed.
1028    *  @return   An iterator designating the end of the resulting sequence.
1029    *
1030    *  All elements equal to @p value are removed from the range
1031    *  @p [first,last).
1032    *
1033    *  remove() is stable, so the relative order of elements that are
1034    *  not removed is unchanged.
1035    *
1036    *  Elements between the end of the resulting sequence and @p last
1037    *  are still present, but their value is unspecified.
1038   */
1039   template<typename _ForwardIter, typename _Tp>
1040     _ForwardIter
1041     remove(_ForwardIter __first, _ForwardIter __last,
1042            const _Tp& __value)
1043     {
1044       // concept requirements
1045       __glibcpp_function_requires(_Mutable_ForwardIteratorConcept<_ForwardIter>)
1046       __glibcpp_function_requires(_ConvertibleConcept<_Tp,
1047             typename iterator_traits<_ForwardIter>::value_type>)
1048       __glibcpp_function_requires(_EqualOpConcept<
1049             typename iterator_traits<_ForwardIter>::value_type, _Tp>)
1050
1051       __first = find(__first, __last, __value);
1052       _ForwardIter __i = __first;
1053       return __first == __last ? __first
1054                                : remove_copy(++__i, __last, __first, __value);
1055     }
1056
1057   /**
1058    *  @brief Remove elements from a sequence using a predicate.
1059    *  @param  first  A forward iterator.
1060    *  @param  last   A forward iterator.
1061    *  @param  pred   A predicate.
1062    *  @return   An iterator designating the end of the resulting sequence.
1063    *
1064    *  All elements for which @p pred returns true are removed from the range
1065    *  @p [first,last).
1066    *
1067    *  remove_if() is stable, so the relative order of elements that are
1068    *  not removed is unchanged.
1069    *
1070    *  Elements between the end of the resulting sequence and @p last
1071    *  are still present, but their value is unspecified.
1072   */
1073   template<typename _ForwardIter, typename _Predicate>
1074     _ForwardIter
1075     remove_if(_ForwardIter __first, _ForwardIter __last,
1076               _Predicate __pred)
1077     {
1078       // concept requirements
1079       __glibcpp_function_requires(_Mutable_ForwardIteratorConcept<_ForwardIter>)
1080       __glibcpp_function_requires(_UnaryPredicateConcept<_Predicate,
1081             typename iterator_traits<_ForwardIter>::value_type>)
1082
1083       __first = find_if(__first, __last, __pred);
1084       _ForwardIter __i = __first;
1085       return __first == __last ? __first
1086                                : remove_copy_if(++__i, __last, __first, __pred);
1087     }
1088
1089   /**
1090    *  @if maint
1091    *  This is an uglified unique_copy(_InputIter, _InputIter, _OutputIter)
1092    *  overloaded for output iterators.
1093    *  @endif
1094   */
1095   template<typename _InputIter, typename _OutputIter>
1096     _OutputIter
1097     __unique_copy(_InputIter __first, _InputIter __last,
1098                   _OutputIter __result,
1099                   output_iterator_tag)
1100     {
1101       // concept requirements -- taken care of in dispatching function
1102       typename iterator_traits<_InputIter>::value_type __value = *__first;
1103       *__result = __value;
1104       while (++__first != __last)
1105         if (!(__value == *__first)) {
1106           __value = *__first;
1107           *++__result = __value;
1108         }
1109       return ++__result;
1110     }
1111
1112   /**
1113    *  @if maint
1114    *  This is an uglified unique_copy(_InputIter, _InputIter, _OutputIter)
1115    *  overloaded for forward iterators.
1116    *  @endif
1117   */
1118   template<typename _InputIter, typename _ForwardIter>
1119     _ForwardIter
1120     __unique_copy(_InputIter __first, _InputIter __last,
1121                   _ForwardIter __result,
1122                   forward_iterator_tag)
1123     {
1124       // concept requirements -- taken care of in dispatching function
1125       *__result = *__first;
1126       while (++__first != __last)
1127         if (!(*__result == *__first))
1128           *++__result = *__first;
1129       return ++__result;
1130     }
1131
1132   /**
1133    *  @brief Copy a sequence, removing consecutive duplicate values.
1134    *  @param  first   An input iterator.
1135    *  @param  last    An input iterator.
1136    *  @param  result  An output iterator.
1137    *  @return   An iterator designating the end of the resulting sequence.
1138    *
1139    *  Copies each element in the range @p [first,last) to the range
1140    *  beginning at @p result, except that only the first element is copied
1141    *  from groups of consecutive elements that compare equal.
1142    *  unique_copy() is stable, so the relative order of elements that are
1143    *  copied is unchanged.
1144   */
1145   template<typename _InputIter, typename _OutputIter>
1146     inline _OutputIter
1147     unique_copy(_InputIter __first, _InputIter __last,
1148                 _OutputIter __result)
1149     {
1150       // concept requirements
1151       __glibcpp_function_requires(_InputIteratorConcept<_InputIter>)
1152       __glibcpp_function_requires(_OutputIteratorConcept<_OutputIter,
1153             typename iterator_traits<_InputIter>::value_type>)
1154       __glibcpp_function_requires(_EqualityComparableConcept<
1155             typename iterator_traits<_InputIter>::value_type>)
1156
1157       typedef typename iterator_traits<_OutputIter>::iterator_category _IterType;
1158
1159       if (__first == __last) return __result;
1160       return __unique_copy(__first, __last, __result, _IterType());
1161     }
1162
1163   /**
1164    *  @if maint
1165    *  This is an uglified
1166    *  unique_copy(_InputIter, _InputIter, _OutputIter, _BinaryPredicate)
1167    *  overloaded for output iterators.
1168    *  @endif
1169   */
1170   template<typename _InputIter, typename _OutputIter, typename _BinaryPredicate>
1171     _OutputIter
1172     __unique_copy(_InputIter __first, _InputIter __last,
1173                   _OutputIter __result,
1174                   _BinaryPredicate __binary_pred,
1175                   output_iterator_tag)
1176     {
1177       // concept requirements -- iterators already checked
1178       __glibcpp_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
1179           typename iterator_traits<_InputIter>::value_type,
1180           typename iterator_traits<_InputIter>::value_type>)
1181
1182       typename iterator_traits<_InputIter>::value_type __value = *__first;
1183       *__result = __value;
1184       while (++__first != __last)
1185         if (!__binary_pred(__value, *__first)) {
1186           __value = *__first;
1187           *++__result = __value;
1188         }
1189       return ++__result;
1190     }
1191
1192   /**
1193    *  @if maint
1194    *  This is an uglified
1195    *  unique_copy(_InputIter, _InputIter, _OutputIter, _BinaryPredicate)
1196    *  overloaded for forward iterators.
1197    *  @endif
1198   */
1199   template<typename _InputIter, typename _ForwardIter, typename _BinaryPredicate>
1200     _ForwardIter
1201     __unique_copy(_InputIter __first, _InputIter __last,
1202                   _ForwardIter __result,
1203                   _BinaryPredicate __binary_pred,
1204                   forward_iterator_tag)
1205     {
1206       // concept requirements -- iterators already checked
1207       __glibcpp_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
1208             typename iterator_traits<_ForwardIter>::value_type,
1209             typename iterator_traits<_InputIter>::value_type>)
1210
1211       *__result = *__first;
1212       while (++__first != __last)
1213         if (!__binary_pred(*__result, *__first)) *++__result = *__first;
1214       return ++__result;
1215     }
1216
1217   /**
1218    *  @brief Copy a sequence, removing consecutive values using a predicate.
1219    *  @param  first        An input iterator.
1220    *  @param  last         An input iterator.
1221    *  @param  result       An output iterator.
1222    *  @param  binary_pred  A binary predicate.
1223    *  @return   An iterator designating the end of the resulting sequence.
1224    *
1225    *  Copies each element in the range @p [first,last) to the range
1226    *  beginning at @p result, except that only the first element is copied
1227    *  from groups of consecutive elements for which @p binary_pred returns
1228    *  true.
1229    *  unique_copy() is stable, so the relative order of elements that are
1230    *  copied is unchanged.
1231   */
1232   template<typename _InputIter, typename _OutputIter, typename _BinaryPredicate>
1233     inline _OutputIter
1234     unique_copy(_InputIter __first, _InputIter __last,
1235                 _OutputIter __result,
1236                 _BinaryPredicate __binary_pred)
1237     {
1238       // concept requirements -- predicates checked later
1239       __glibcpp_function_requires(_InputIteratorConcept<_InputIter>)
1240       __glibcpp_function_requires(_OutputIteratorConcept<_OutputIter,
1241             typename iterator_traits<_InputIter>::value_type>)
1242
1243       typedef typename iterator_traits<_OutputIter>::iterator_category _IterType;
1244
1245       if (__first == __last) return __result;
1246       return __unique_copy(__first, __last,
1247 __result, __binary_pred, _IterType());
1248     }
1249
1250   /**
1251    *  @brief Remove consecutive duplicate values from a sequence.
1252    *  @param  first  A forward iterator.
1253    *  @param  last   A forward iterator.
1254    *  @return  An iterator designating the end of the resulting sequence.
1255    *
1256    *  Removes all but the first element from each group of consecutive
1257    *  values that compare equal.
1258    *  unique() is stable, so the relative order of elements that are
1259    *  not removed is unchanged.
1260    *  Elements between the end of the resulting sequence and @p last
1261    *  are still present, but their value is unspecified.
1262   */
1263   template<typename _ForwardIter>
1264     _ForwardIter
1265     unique(_ForwardIter __first, _ForwardIter __last)
1266     {
1267           // concept requirements
1268           __glibcpp_function_requires(_Mutable_ForwardIteratorConcept<_ForwardIter>)
1269           __glibcpp_function_requires(_EqualityComparableConcept<
1270                     typename iterator_traits<_ForwardIter>::value_type>)
1271
1272           __first = adjacent_find(__first, __last);
1273           return unique_copy(__first, __last, __first);
1274     }
1275
1276   /**
1277    *  @brief Remove consecutive values from a sequence using a predicate.
1278    *  @param  first        A forward iterator.
1279    *  @param  last         A forward iterator.
1280    *  @param  binary_pred  A binary predicate.
1281    *  @return  An iterator designating the end of the resulting sequence.
1282    *
1283    *  Removes all but the first element from each group of consecutive
1284    *  values for which @p binary_pred returns true.
1285    *  unique() is stable, so the relative order of elements that are
1286    *  not removed is unchanged.
1287    *  Elements between the end of the resulting sequence and @p last
1288    *  are still present, but their value is unspecified.
1289   */
1290   template<typename _ForwardIter, typename _BinaryPredicate>
1291     _ForwardIter
1292     unique(_ForwardIter __first, _ForwardIter __last,
1293            _BinaryPredicate __binary_pred)
1294     {
1295       // concept requirements
1296       __glibcpp_function_requires(_Mutable_ForwardIteratorConcept<_ForwardIter>)
1297       __glibcpp_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
1298                 typename iterator_traits<_ForwardIter>::value_type,
1299                 typename iterator_traits<_ForwardIter>::value_type>)
1300
1301       __first = adjacent_find(__first, __last, __binary_pred);
1302       return unique_copy(__first, __last, __first, __binary_pred);
1303     }
1304
1305   /**
1306    *  @if maint
1307    *  This is an uglified reverse(_BidirectionalIter, _BidirectionalIter)
1308    *  overloaded for bidirectional iterators.
1309    *  @endif
1310   */
1311   template<typename _BidirectionalIter>
1312     void
1313     __reverse(_BidirectionalIter __first, _BidirectionalIter __last,
1314                           bidirectional_iterator_tag)
1315     {
1316           while (true)
1317             if (__first == __last || __first == --__last)
1318                   return;
1319             else
1320                   iter_swap(__first++, __last);
1321     }
1322
1323   /**
1324    *  @if maint
1325    *  This is an uglified reverse(_BidirectionalIter, _BidirectionalIter)
1326    *  overloaded for bidirectional iterators.
1327    *  @endif
1328   */
1329   template<typename _RandomAccessIter>
1330     void
1331     __reverse(_RandomAccessIter __first, _RandomAccessIter __last,
1332                           random_access_iterator_tag)
1333     {
1334           while (__first < __last)
1335             iter_swap(__first++, --__last);
1336     }
1337
1338   /**
1339    *  @brief Reverse a sequence.
1340    *  @param  first  A bidirectional iterator.
1341    *  @param  last   A bidirectional iterator.
1342    *  @return   reverse() returns no value.
1343    *
1344    *  Reverses the order of the elements in the range @p [first,last),
1345    *  so that the first element becomes the last etc.
1346    *  For every @c i such that @p 0<=i<=(last-first)/2), @p reverse()
1347    *  swaps @p *(first+i) and @p *(last-(i+1))
1348   */
1349   template<typename _BidirectionalIter>
1350     inline void
1351     reverse(_BidirectionalIter __first, _BidirectionalIter __last)
1352     {
1353           // concept requirements
1354           __glibcpp_function_requires(_Mutable_BidirectionalIteratorConcept<
1355                     _BidirectionalIter>)
1356           __reverse(__first, __last, __iterator_category(__first));
1357     }
1358
1359   /**
1360    *  @brief Copy a sequence, reversing its elements.
1361    *  @param  first   A bidirectional iterator.
1362    *  @param  last    A bidirectional iterator.
1363    *  @param  result  An output iterator.
1364    *  @return  An iterator designating the end of the resulting sequence.
1365    *
1366    *  Copies the elements in the range @p [first,last) to the range
1367    *  @p [result,result+(last-first)) such that the order of the
1368    *  elements is reversed.
1369    *  For every @c i such that @p 0<=i<=(last-first), @p reverse_copy()
1370    *  performs the assignment @p *(result+(last-first)-i) = *(first+i).
1371    *  The ranges @p [first,last) and @p [result,result+(last-first))
1372    *  must not overlap.
1373   */
1374   template<typename _BidirectionalIter, typename _OutputIter>
1375     _OutputIter
1376     reverse_copy(_BidirectionalIter __first, _BidirectionalIter __last,
1377                              _OutputIter __result)
1378     {
1379       // concept requirements
1380       __glibcpp_function_requires(_BidirectionalIteratorConcept<_BidirectionalIter>)
1381       __glibcpp_function_requires(_OutputIteratorConcept<_OutputIter,
1382                 typename iterator_traits<_BidirectionalIter>::value_type>)
1383
1384       while (__first != __last) {
1385         --__last;
1386         *__result = *__last;
1387         ++__result;
1388       }
1389       return __result;
1390     }
1391
1392
1393   /**
1394    *  @if maint
1395    *  This is a helper function for the rotate algorithm specialized on RAIs.
1396    *  It returns the greatest common divisor of two integer values.
1397    *  @endif
1398   */
1399   template<typename _EuclideanRingElement>
1400     _EuclideanRingElement
1401     __gcd(_EuclideanRingElement __m, _EuclideanRingElement __n)
1402     {
1403       while (__n != 0) {
1404         _EuclideanRingElement __t = __m % __n;
1405         __m = __n;
1406         __n = __t;
1407       }
1408       return __m;
1409     }
1410
1411   /**
1412    *  @if maint
1413    *  This is a helper function for the rotate algorithm.
1414    *  @endif
1415   */
1416   template<typename _ForwardIter>
1417     void
1418     __rotate(_ForwardIter __first,
1419              _ForwardIter __middle,
1420              _ForwardIter __last,
1421               forward_iterator_tag)
1422     {
1423       if ((__first == __middle) || (__last  == __middle))
1424         return;
1425
1426       _ForwardIter __first2 = __middle;
1427       do {
1428         swap(*__first++, *__first2++);
1429         if (__first == __middle)
1430           __middle = __first2;
1431       } while (__first2 != __last);
1432
1433       __first2 = __middle;
1434
1435       while (__first2 != __last) {
1436         swap(*__first++, *__first2++);
1437         if (__first == __middle)
1438           __middle = __first2;
1439         else if (__first2 == __last)
1440           __first2 = __middle;
1441       }
1442     }
1443
1444   /**
1445    *  @if maint
1446    *  This is a helper function for the rotate algorithm.
1447    *  @endif
1448   */
1449   template<typename _BidirectionalIter>
1450     void
1451     __rotate(_BidirectionalIter __first,
1452              _BidirectionalIter __middle,
1453              _BidirectionalIter __last,
1454               bidirectional_iterator_tag)
1455     {
1456       // concept requirements
1457       __glibcpp_function_requires(_Mutable_BidirectionalIteratorConcept<
1458             _BidirectionalIter>)
1459
1460       if ((__first == __middle) || (__last  == __middle))
1461         return;
1462
1463       __reverse(__first,  __middle, bidirectional_iterator_tag());
1464       __reverse(__middle, __last,   bidirectional_iterator_tag());
1465
1466       while (__first != __middle && __middle != __last)
1467         swap (*__first++, *--__last);
1468
1469       if (__first == __middle) {
1470         __reverse(__middle, __last,   bidirectional_iterator_tag());
1471       }
1472       else {
1473         __reverse(__first,  __middle, bidirectional_iterator_tag());
1474       }
1475     }
1476
1477   /**
1478    *  @if maint
1479    *  This is a helper function for the rotate algorithm.
1480    *  @endif
1481   */
1482   template<typename _RandomAccessIter>
1483     void
1484     __rotate(_RandomAccessIter __first,
1485              _RandomAccessIter __middle,
1486              _RandomAccessIter __last,
1487              random_access_iterator_tag)
1488     {
1489       // concept requirements
1490       __glibcpp_function_requires(_Mutable_RandomAccessIteratorConcept<
1491             _RandomAccessIter>)
1492
1493       if ((__first == __middle) || (__last  == __middle))
1494         return;
1495
1496       typedef typename iterator_traits<_RandomAccessIter>::difference_type _Distance;
1497       typedef typename iterator_traits<_RandomAccessIter>::value_type _ValueType;
1498
1499       _Distance __n = __last   - __first;
1500       _Distance __k = __middle - __first;
1501       _Distance __l = __n - __k;
1502
1503       if (__k == __l) {
1504         swap_ranges(__first, __middle, __middle);
1505         return;
1506       }
1507
1508       _Distance __d = __gcd(__n, __k);
1509
1510       for (_Distance __i = 0; __i < __d; __i++) {
1511         _ValueType __tmp = *__first;
1512         _RandomAccessIter __p = __first;
1513
1514         if (__k < __l) {
1515           for (_Distance __j = 0; __j < __l/__d; __j++) {
1516             if (__p > __first + __l) {
1517               *__p = *(__p - __l);
1518               __p -= __l;
1519             }
1520
1521             *__p = *(__p + __k);
1522             __p += __k;
1523           }
1524         }
1525
1526         else {
1527           for (_Distance __j = 0; __j < __k/__d - 1; __j ++) {
1528             if (__p < __last - __k) {
1529               *__p = *(__p + __k);
1530               __p += __k;
1531             }
1532
1533             *__p = * (__p - __l);
1534             __p -= __l;
1535           }
1536         }
1537
1538         *__p = __tmp;
1539         ++__first;
1540       }
1541     }
1542
1543   /**
1544    *  @brief Rotate the elements of a sequence.
1545    *  @param  first   A forward iterator.
1546    *  @param  middle  A forward iterator.
1547    *  @param  last    A forward iterator.
1548    *  @return  Nothing.
1549    *
1550    *  Rotates the elements of the range @p [first,last) by @p (middle-first)
1551    *  positions so that the element at @p middle is moved to @p first, the
1552    *  element at @p middle+1 is moved to @first+1 and so on for each element
1553    *  in the range @p [first,last).
1554    *
1555    *  This effectively swaps the ranges @p [first,middle) and
1556    *  @p [middle,last).
1557    *
1558    *  Performs @p *(first+(n+(last-middle))%(last-first))=*(first+n) for
1559    *  each @p n in the range @p [0,last-first).
1560   */
1561   template<typename _ForwardIter>
1562     inline void
1563     rotate(_ForwardIter __first, _ForwardIter __middle, _ForwardIter __last)
1564     {
1565       // concept requirements
1566       __glibcpp_function_requires(_Mutable_ForwardIteratorConcept<_ForwardIter>)
1567
1568       typedef typename iterator_traits<_ForwardIter>::iterator_category _IterType;
1569       __rotate(__first, __middle, __last, _IterType());
1570     }
1571
1572   /**
1573    *  @brief Copy a sequence, rotating its elements.
1574    *  @param  first   A forward iterator.
1575    *  @param  middle  A forward iterator.
1576    *  @param  last    A forward iterator.
1577    *  @param  result  An output iterator.
1578    *  @return   An iterator designating the end of the resulting sequence.
1579    *
1580    *  Copies the elements of the range @p [first,last) to the range
1581    *  beginning at @result, rotating the copied elements by @p (middle-first)
1582    *  positions so that the element at @p middle is moved to @p result, the
1583    *  element at @p middle+1 is moved to @result+1 and so on for each element
1584    *  in the range @p [first,last).
1585    *
1586    *  Performs @p *(result+(n+(last-middle))%(last-first))=*(first+n) for
1587    *  each @p n in the range @p [0,last-first).
1588   */
1589   template<typename _ForwardIter, typename _OutputIter>
1590     _OutputIter
1591     rotate_copy(_ForwardIter __first, _ForwardIter __middle,
1592                 _ForwardIter __last, _OutputIter __result)
1593     {
1594       // concept requirements
1595       __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter>)
1596       __glibcpp_function_requires(_OutputIteratorConcept<_OutputIter,
1597                 typename iterator_traits<_ForwardIter>::value_type>)
1598
1599       return copy(__first, __middle, copy(__middle, __last, __result));
1600     }
1601
1602
1603   /**
1604    *  @if maint
1605    *  Return a random number in the range [0, __n).  This function encapsulates
1606    *  whether we're using rand (part of the standard C library) or lrand48
1607    *  (not standard, but a much better choice whenever it's available).
1608    *
1609    *  XXX There is no corresponding encapsulation fn to seed the generator.
1610    *  @endif
1611   */
1612   template<typename _Distance>
1613     inline _Distance
1614     __random_number(_Distance __n)
1615     {
1616   #ifdef _GLIBCPP_HAVE_DRAND48
1617       return lrand48() % __n;
1618   #else
1619       return rand() % __n;
1620   #endif
1621     }
1622
1623
1624   /**
1625    *  @brief Randomly shuffle the elements of a sequence.
1626    *  @param  first   A forward iterator.
1627    *  @param  last    A forward iterator.
1628    *  @return  Nothing.
1629    *
1630    *  Reorder the elements in the range @p [first,last) using a random
1631    *  distribution, so that every possible ordering of the sequence is
1632    *  equally likely.
1633   */
1634   template<typename _RandomAccessIter>
1635     inline void
1636     random_shuffle(_RandomAccessIter __first, _RandomAccessIter __last)
1637     {
1638       // concept requirements
1639       __glibcpp_function_requires(_Mutable_RandomAccessIteratorConcept<
1640             _RandomAccessIter>)
1641
1642       if (__first == __last) return;
1643       for (_RandomAccessIter __i = __first + 1; __i != __last; ++__i)
1644         iter_swap(__i, __first + __random_number((__i - __first) + 1));
1645     }
1646
1647   /**
1648    *  @brief Shuffle the elements of a sequence using a random number
1649    *         generator.
1650    *  @param  first   A forward iterator.
1651    *  @param  last    A forward iterator.
1652    *  @param  rand    The RNG functor or function.
1653    *  @return  Nothing.
1654    *
1655    *  Reorders the elements in the range @p [first,last) using @p rand to
1656    *  provide a random distribution. Calling @p rand(N) for a positive
1657    *  integer @p N should return a randomly chosen integer from the
1658    *  range [0,N).
1659   */
1660   template<typename _RandomAccessIter, typename _RandomNumberGenerator>
1661     void
1662     random_shuffle(_RandomAccessIter __first, _RandomAccessIter __last,
1663                    _RandomNumberGenerator& __rand)
1664     {
1665       // concept requirements
1666       __glibcpp_function_requires(_Mutable_RandomAccessIteratorConcept<
1667             _RandomAccessIter>)
1668
1669       if (__first == __last) return;
1670       for (_RandomAccessIter __i = __first + 1; __i != __last; ++__i)
1671         iter_swap(__i, __first + __rand((__i - __first) + 1));
1672     }
1673
1674
1675   /**
1676    *  @if maint
1677    *  This is a helper function...
1678    *  @endif
1679   */
1680   template<typename _ForwardIter, typename _Predicate>
1681     _ForwardIter
1682     __partition(_ForwardIter __first, _ForwardIter __last,
1683                 _Predicate   __pred,
1684                 forward_iterator_tag)
1685     {
1686       if (__first == __last) return __first;
1687
1688       while (__pred(*__first))
1689         if (++__first == __last) return __first;
1690
1691       _ForwardIter __next = __first;
1692
1693       while (++__next != __last)
1694         if (__pred(*__next)) {
1695           swap(*__first, *__next);
1696           ++__first;
1697         }
1698
1699       return __first;
1700     }
1701
1702   /**
1703    *  @if maint
1704    *  This is a helper function...
1705    *  @endif
1706   */
1707   template<typename _BidirectionalIter, typename _Predicate>
1708     _BidirectionalIter
1709     __partition(_BidirectionalIter __first, _BidirectionalIter __last,
1710                 _Predicate __pred,
1711                 bidirectional_iterator_tag)
1712     {
1713       while (true) {
1714         while (true)
1715           if (__first == __last)
1716             return __first;
1717           else if (__pred(*__first))
1718             ++__first;
1719           else
1720             break;
1721         --__last;
1722         while (true)
1723           if (__first == __last)
1724             return __first;
1725           else if (!__pred(*__last))
1726             --__last;
1727           else
1728             break;
1729         iter_swap(__first, __last);
1730         ++__first;
1731       }
1732     }
1733
1734   /**
1735    *  @brief Move elements for which a predicate is true to the beginning
1736    *         of a sequence.
1737    *  @param  first   A forward iterator.
1738    *  @param  last    A forward iterator.
1739    *  @param  pred    A predicate functor.
1740    *  @return  An iterator @p middle such that @p pred(i) is true for each
1741    *  iterator @p i in the range @p [first,middle) and false for each @p i
1742    *  in the range @p [middle,last).
1743    *
1744    *  @p pred must not modify its operand. @p partition() does not preserve
1745    *  the relative ordering of elements in each group, use
1746    *  @p stable_partition() if this is needed.
1747   */
1748   template<typename _ForwardIter, typename _Predicate>
1749     inline _ForwardIter
1750     partition(_ForwardIter __first, _ForwardIter __last,
1751               _Predicate   __pred)
1752     {
1753       // concept requirements
1754       __glibcpp_function_requires(_Mutable_ForwardIteratorConcept<_ForwardIter>)
1755       __glibcpp_function_requires(_UnaryPredicateConcept<_Predicate,
1756             typename iterator_traits<_ForwardIter>::value_type>)
1757
1758       return __partition(__first, __last, __pred, __iterator_category(__first));
1759     }
1760
1761
1762   /**
1763    *  @if maint
1764    *  This is a helper function...
1765    *  @endif
1766   */
1767   template<typename _ForwardIter, typename _Predicate, typename _Distance>
1768     _ForwardIter
1769     __inplace_stable_partition(_ForwardIter __first, _ForwardIter __last,
1770                                _Predicate __pred, _Distance __len)
1771     {
1772       if (__len == 1)
1773         return __pred(*__first) ? __last : __first;
1774       _ForwardIter __middle = __first;
1775       advance(__middle, __len / 2);
1776       _ForwardIter __begin = __inplace_stable_partition(__first, __middle,
1777                                                         __pred,
1778                                                         __len / 2);
1779       _ForwardIter __end = __inplace_stable_partition(__middle, __last,
1780                                                       __pred,
1781                                                       __len - __len / 2);
1782       rotate(__begin, __middle, __end);
1783       advance(__begin, std::distance(__middle, __end));
1784       return __begin;
1785     }
1786
1787   /**
1788    *  @if maint
1789    *  This is a helper function...
1790    *  @endif
1791   */
1792   template<typename _ForwardIter, typename _Pointer, typename _Predicate,
1793            typename _Distance>
1794     _ForwardIter
1795     __stable_partition_adaptive(_ForwardIter __first, _ForwardIter __last,
1796                                 _Predicate __pred, _Distance __len,
1797                                 _Pointer __buffer,
1798                                 _Distance __buffer_size)
1799     {
1800       if (__len <= __buffer_size) {
1801         _ForwardIter __result1 = __first;
1802         _Pointer __result2 = __buffer;
1803         for ( ; __first != __last ; ++__first)
1804           if (__pred(*__first)) {
1805             *__result1 = *__first;
1806             ++__result1;
1807           }
1808           else {
1809             *__result2 = *__first;
1810             ++__result2;
1811           }
1812         copy(__buffer, __result2, __result1);
1813         return __result1;
1814       }
1815       else {
1816         _ForwardIter __middle = __first;
1817         advance(__middle, __len / 2);
1818         _ForwardIter __begin = __stable_partition_adaptive(__first, __middle,
1819                                                            __pred,
1820                                                            __len / 2,
1821                                                            __buffer, __buffer_size);
1822         _ForwardIter __end = __stable_partition_adaptive( __middle, __last,
1823                                                           __pred,
1824                                                           __len - __len / 2,
1825                                                           __buffer, __buffer_size);
1826         rotate(__begin, __middle, __end);
1827         advance(__begin, std::distance(__middle, __end));
1828         return __begin;
1829       }
1830     }
1831
1832   /**
1833    *  @brief Move elements for which a predicate is true to the beginning
1834    *         of a sequence, preserving relative ordering.
1835    *  @param  first   A forward iterator.
1836    *  @param  last    A forward iterator.
1837    *  @param  pred    A predicate functor.
1838    *  @return  An iterator @p middle such that @p pred(i) is true for each
1839    *  iterator @p i in the range @p [first,middle) and false for each @p i
1840    *  in the range @p [middle,last).
1841    *
1842    *  Performs the same function as @p partition() with the additional
1843    *  guarantee that the relative ordering of elements in each group is
1844    *  preserved, so any two elements @p x and @p y in the range
1845    *  @p [first,last) such that @p pred(x)==pred(y) will have the same
1846    *  relative ordering after calling @p stable_partition().
1847   */
1848   template<typename _ForwardIter, typename _Predicate>
1849     _ForwardIter
1850     stable_partition(_ForwardIter __first, _ForwardIter __last,
1851                      _Predicate __pred)
1852     {
1853       // concept requirements
1854       __glibcpp_function_requires(_Mutable_ForwardIteratorConcept<_ForwardIter>)
1855       __glibcpp_function_requires(_UnaryPredicateConcept<_Predicate,
1856             typename iterator_traits<_ForwardIter>::value_type>)
1857
1858       if (__first == __last)
1859         return __first;
1860       else
1861       {
1862         typedef typename iterator_traits<_ForwardIter>::value_type _ValueType;
1863         typedef typename iterator_traits<_ForwardIter>::difference_type _DistanceType;
1864
1865         _Temporary_buffer<_ForwardIter, _ValueType> __buf(__first, __last);
1866         if (__buf.size() > 0)
1867           return __stable_partition_adaptive(__first, __last, __pred,
1868                                              _DistanceType(__buf.requested_size()),
1869                                              __buf.begin(), __buf.size());
1870         else
1871           return __inplace_stable_partition(__first, __last, __pred,
1872                                             _DistanceType(__buf.requested_size()));
1873       }
1874     }
1875
1876   /**
1877    *  @if maint
1878    *  This is a helper function...
1879    *  @endif
1880   */
1881   template<typename _RandomAccessIter, typename _Tp>
1882     _RandomAccessIter
1883     __unguarded_partition(_RandomAccessIter __first, _RandomAccessIter __last,
1884                           _Tp __pivot)
1885     {
1886       while (true) {
1887         while (*__first < __pivot)
1888           ++__first;
1889         --__last;
1890         while (__pivot < *__last)
1891           --__last;
1892         if (!(__first < __last))
1893           return __first;
1894         iter_swap(__first, __last);
1895         ++__first;
1896       }
1897     }
1898
1899   /**
1900    *  @if maint
1901    *  This is a helper function...
1902    *  @endif
1903   */
1904   template<typename _RandomAccessIter, typename _Tp, typename _Compare>
1905     _RandomAccessIter
1906     __unguarded_partition(_RandomAccessIter __first, _RandomAccessIter __last,
1907                           _Tp __pivot, _Compare __comp)
1908     {
1909       while (true) {
1910         while (__comp(*__first, __pivot))
1911           ++__first;
1912         --__last;
1913         while (__comp(__pivot, *__last))
1914           --__last;
1915         if (!(__first < __last))
1916           return __first;
1917         iter_swap(__first, __last);
1918         ++__first;
1919       }
1920     }
1921
1922
1923   /**
1924    *  @if maint
1925    *  @doctodo
1926    *  This controls some aspect of the sort routines.
1927    *  @endif
1928   */
1929   enum { _M_threshold = 16 };
1930
1931   /**
1932    *  @if maint
1933    *  This is a helper function for the sort routine.
1934    *  @endif
1935   */
1936   template<typename _RandomAccessIter, typename _Tp>
1937     void
1938     __unguarded_linear_insert(_RandomAccessIter __last, _Tp __val)
1939     {
1940       _RandomAccessIter __next = __last;
1941       --__next;
1942       while (__val < *__next) {
1943         *__last = *__next;
1944         __last = __next;
1945         --__next;
1946       }
1947       *__last = __val;
1948     }
1949
1950   /**
1951    *  @if maint
1952    *  This is a helper function for the sort routine.
1953    *  @endif
1954   */
1955   template<typename _RandomAccessIter, typename _Tp, typename _Compare>
1956     void
1957     __unguarded_linear_insert(_RandomAccessIter __last, _Tp __val, _Compare __comp)
1958     {
1959       _RandomAccessIter __next = __last;
1960       --__next;
1961       while (__comp(__val, *__next)) {
1962         *__last = *__next;
1963         __last = __next;
1964         --__next;
1965       }
1966       *__last = __val;
1967     }
1968
1969   /**
1970    *  @if maint
1971    *  This is a helper function for the sort routine.
1972    *  @endif
1973   */
1974   template<typename _RandomAccessIter>
1975     void
1976     __insertion_sort(_RandomAccessIter __first, _RandomAccessIter __last)
1977     {
1978       if (__first == __last) return;
1979
1980       for (_RandomAccessIter __i = __first + 1; __i != __last; ++__i)
1981       {
1982         typename iterator_traits<_RandomAccessIter>::value_type __val = *__i;
1983         if (__val < *__first) {
1984           copy_backward(__first, __i, __i + 1);
1985           *__first = __val;
1986         }
1987         else
1988           __unguarded_linear_insert(__i, __val);
1989       }
1990     }
1991
1992   /**
1993    *  @if maint
1994    *  This is a helper function for the sort routine.
1995    *  @endif
1996   */
1997   template<typename _RandomAccessIter, typename _Compare>
1998     void
1999     __insertion_sort(_RandomAccessIter __first, _RandomAccessIter __last,
2000                      _Compare __comp)
2001     {
2002       if (__first == __last) return;
2003
2004       for (_RandomAccessIter __i = __first + 1; __i != __last; ++__i)
2005       {
2006         typename iterator_traits<_RandomAccessIter>::value_type __val = *__i;
2007         if (__comp(__val, *__first)) {
2008           copy_backward(__first, __i, __i + 1);
2009           *__first = __val;
2010         }
2011         else
2012           __unguarded_linear_insert(__i, __val, __comp);
2013       }
2014     }
2015
2016   /**
2017    *  @if maint
2018    *  This is a helper function for the sort routine.
2019    *  @endif
2020   */
2021   template<typename _RandomAccessIter>
2022     inline void
2023     __unguarded_insertion_sort(_RandomAccessIter __first, _RandomAccessIter __last)
2024     {
2025       typedef typename iterator_traits<_RandomAccessIter>::value_type _ValueType;
2026
2027       for (_RandomAccessIter __i = __first; __i != __last; ++__i)
2028         __unguarded_linear_insert(__i, _ValueType(*__i));
2029     }
2030
2031   /**
2032    *  @if maint
2033    *  This is a helper function for the sort routine.
2034    *  @endif
2035   */
2036   template<typename _RandomAccessIter, typename _Compare>
2037     inline void
2038     __unguarded_insertion_sort(_RandomAccessIter __first, _RandomAccessIter __last,
2039                                _Compare __comp)
2040     {
2041       typedef typename iterator_traits<_RandomAccessIter>::value_type _ValueType;
2042
2043       for (_RandomAccessIter __i = __first; __i != __last; ++__i)
2044         __unguarded_linear_insert(__i, _ValueType(*__i), __comp);
2045     }
2046
2047   /**
2048    *  @if maint
2049    *  This is a helper function for the sort routine.
2050    *  @endif
2051   */
2052   template<typename _RandomAccessIter>
2053     void
2054     __final_insertion_sort(_RandomAccessIter __first, _RandomAccessIter __last)
2055     {
2056       if (__last - __first > _M_threshold) {
2057         __insertion_sort(__first, __first + _M_threshold);
2058         __unguarded_insertion_sort(__first + _M_threshold, __last);
2059       }
2060       else
2061         __insertion_sort(__first, __last);
2062     }
2063
2064   /**
2065    *  @if maint
2066    *  This is a helper function for the sort routine.
2067    *  @endif
2068   */
2069   template<typename _RandomAccessIter, typename _Compare>
2070     void
2071     __final_insertion_sort(_RandomAccessIter __first, _RandomAccessIter __last,
2072                            _Compare __comp)
2073     {
2074       if (__last - __first > _M_threshold) {
2075         __insertion_sort(__first, __first + _M_threshold, __comp);
2076         __unguarded_insertion_sort(__first + _M_threshold, __last, __comp);
2077       }
2078       else
2079         __insertion_sort(__first, __last, __comp);
2080     }
2081
2082   /**
2083    *  @if maint
2084    *  This is a helper function for the sort routine.
2085    *  @endif
2086   */
2087   template<typename _Size>
2088     inline _Size
2089     __lg(_Size __n)
2090     {
2091       _Size __k;
2092       for (__k = 0; __n != 1; __n >>= 1) ++__k;
2093       return __k;
2094     }
2095
2096   /**
2097    *  @if maint
2098    *  This is a helper function for the sort routine.
2099    *  @endif
2100   */
2101   template<typename _RandomAccessIter, typename _Size>
2102     void
2103     __introsort_loop(_RandomAccessIter __first, _RandomAccessIter __last,
2104                      _Size __depth_limit)
2105     {
2106       typedef typename iterator_traits<_RandomAccessIter>::value_type _ValueType;
2107
2108       while (__last - __first > _M_threshold) {
2109         if (__depth_limit == 0) {
2110           partial_sort(__first, __last, __last);
2111           return;
2112         }
2113         --__depth_limit;
2114         _RandomAccessIter __cut =
2115           __unguarded_partition(__first, __last,
2116                                 _ValueType(__median(*__first,
2117                                                     *(__first + (__last - __first)/2),
2118                                                     *(__last - 1))));
2119         __introsort_loop(__cut, __last, __depth_limit);
2120         __last = __cut;
2121       }
2122     }
2123
2124   /**
2125    *  @if maint
2126    *  This is a helper function for the sort routine.
2127    *  @endif
2128   */
2129   template<typename _RandomAccessIter, typename _Size, typename _Compare>
2130     void
2131     __introsort_loop(_RandomAccessIter __first, _RandomAccessIter __last,
2132                      _Size __depth_limit, _Compare __comp)
2133     {
2134       typedef typename iterator_traits<_RandomAccessIter>::value_type _ValueType;
2135
2136       while (__last - __first > _M_threshold) {
2137         if (__depth_limit == 0) {
2138           partial_sort(__first, __last, __last, __comp);
2139           return;
2140         }
2141         --__depth_limit;
2142         _RandomAccessIter __cut =
2143           __unguarded_partition(__first, __last,
2144                                 _ValueType(__median(*__first,
2145                                                     *(__first + (__last - __first)/2),
2146                                                     *(__last - 1), __comp)),
2147            __comp);
2148         __introsort_loop(__cut, __last, __depth_limit, __comp);
2149         __last = __cut;
2150       }
2151     }
2152
2153   /**
2154    *  @brief Sort the elements of a sequence.
2155    *  @param  first   An iterator.
2156    *  @param  last    Another iterator.
2157    *  @return  Nothing.
2158    *
2159    *  Sorts the elements in the range @p [first,last) in ascending order,
2160    *  such that @p *(i+1)<*i is false for each iterator @p i in the range
2161    *  @p [first,last-1).
2162    *
2163    *  The relative ordering of equivalent elements is not preserved, use
2164    *  @p stable_sort() if this is needed.
2165   */
2166   template<typename _RandomAccessIter>
2167     inline void
2168     sort(_RandomAccessIter __first, _RandomAccessIter __last)
2169     {
2170       typedef typename iterator_traits<_RandomAccessIter>::value_type _ValueType;
2171
2172       // concept requirements
2173       __glibcpp_function_requires(_Mutable_RandomAccessIteratorConcept<
2174             _RandomAccessIter>)
2175       __glibcpp_function_requires(_LessThanComparableConcept<_ValueType>)
2176
2177       if (__first != __last) {
2178         __introsort_loop(__first, __last, __lg(__last - __first) * 2);
2179         __final_insertion_sort(__first, __last);
2180       }
2181     }
2182
2183   /**
2184    *  @brief Sort the elements of a sequence using a predicate for comparison.
2185    *  @param  first   An iterator.
2186    *  @param  last    Another iterator.
2187    *  @param  comp    A comparison functor.
2188    *  @return  Nothing.
2189    *
2190    *  Sorts the elements in the range @p [first,last) in ascending order,
2191    *  such that @p comp(*(i+1),*i) is false for every iterator @p i in the
2192    *  range @p [first,last-1).
2193    *
2194    *  The relative ordering of equivalent elements is not preserved, use
2195    *  @p stable_sort() if this is needed.
2196   */
2197   template<typename _RandomAccessIter, typename _Compare>
2198     inline void
2199     sort(_RandomAccessIter __first, _RandomAccessIter __last, _Compare __comp)
2200     {
2201       typedef typename iterator_traits<_RandomAccessIter>::value_type _ValueType;
2202
2203       // concept requirements
2204       __glibcpp_function_requires(_Mutable_RandomAccessIteratorConcept<
2205             _RandomAccessIter>)
2206       __glibcpp_function_requires(_BinaryPredicateConcept<_Compare, _ValueType, _ValueType>)
2207
2208       if (__first != __last) {
2209         __introsort_loop(__first, __last, __lg(__last - __first) * 2, __comp);
2210         __final_insertion_sort(__first, __last, __comp);
2211       }
2212     }
2213
2214
2215   /**
2216    *  @if maint
2217    *  This is a helper function for the stable sorting routines.
2218    *  @endif
2219   */
2220   template<typename _RandomAccessIter>
2221     void
2222     __inplace_stable_sort(_RandomAccessIter __first, _RandomAccessIter __last)
2223     {
2224       if (__last - __first < 15) {
2225         __insertion_sort(__first, __last);
2226         return;
2227       }
2228       _RandomAccessIter __middle = __first + (__last - __first) / 2;
2229       __inplace_stable_sort(__first, __middle);
2230       __inplace_stable_sort(__middle, __last);
2231       __merge_without_buffer(__first, __middle, __last,
2232                              __middle - __first,
2233                              __last - __middle);
2234     }
2235
2236   /**
2237    *  @if maint
2238    *  This is a helper function for the stable sorting routines.
2239    *  @endif
2240   */
2241   template<typename _RandomAccessIter, typename _Compare>
2242     void
2243     __inplace_stable_sort(_RandomAccessIter __first, _RandomAccessIter __last,
2244                           _Compare __comp)
2245     {
2246       if (__last - __first < 15) {
2247         __insertion_sort(__first, __last, __comp);
2248         return;
2249       }
2250       _RandomAccessIter __middle = __first + (__last - __first) / 2;
2251       __inplace_stable_sort(__first, __middle, __comp);
2252       __inplace_stable_sort(__middle, __last, __comp);
2253       __merge_without_buffer(__first, __middle, __last,
2254                              __middle - __first,
2255                              __last - __middle,
2256                              __comp);
2257     }
2258
2259   template<typename _RandomAccessIter1, typename _RandomAccessIter2,
2260            typename _Distance>
2261     void
2262     __merge_sort_loop(_RandomAccessIter1 __first, _RandomAccessIter1 __last,
2263                       _RandomAccessIter2 __result, _Distance __step_size)
2264     {
2265       _Distance __two_step = 2 * __step_size;
2266
2267       while (__last - __first >= __two_step) {
2268         __result = merge(__first, __first + __step_size,
2269                          __first + __step_size, __first + __two_step,
2270                          __result);
2271         __first += __two_step;
2272       }
2273
2274       __step_size = std::min(_Distance(__last - __first), __step_size);
2275       merge(__first, __first + __step_size, __first + __step_size, __last,
2276             __result);
2277     }
2278
2279   template<typename _RandomAccessIter1, typename _RandomAccessIter2,
2280            typename _Distance, typename _Compare>
2281     void
2282     __merge_sort_loop(_RandomAccessIter1 __first, _RandomAccessIter1 __last,
2283                       _RandomAccessIter2 __result, _Distance __step_size,
2284                       _Compare __comp)
2285     {
2286       _Distance __two_step = 2 * __step_size;
2287
2288       while (__last - __first >= __two_step) {
2289         __result = merge(__first, __first + __step_size,
2290                          __first + __step_size, __first + __two_step,
2291                          __result,
2292                          __comp);
2293         __first += __two_step;
2294       }
2295       __step_size = std::min(_Distance(__last - __first), __step_size);
2296
2297       merge(__first, __first + __step_size,
2298             __first + __step_size, __last,
2299             __result,
2300             __comp);
2301     }
2302
2303   enum { _M_chunk_size = 7 };
2304
2305   template<typename _RandomAccessIter, typename _Distance>
2306     void
2307     __chunk_insertion_sort(_RandomAccessIter __first, _RandomAccessIter __last,
2308                            _Distance __chunk_size)
2309     {
2310       while (__last - __first >= __chunk_size) {
2311         __insertion_sort(__first, __first + __chunk_size);
2312         __first += __chunk_size;
2313       }
2314       __insertion_sort(__first, __last);
2315     }
2316
2317   template<typename _RandomAccessIter, typename _Distance, typename _Compare>
2318     void
2319     __chunk_insertion_sort(_RandomAccessIter __first, _RandomAccessIter __last,
2320                            _Distance __chunk_size, _Compare __comp)
2321     {
2322       while (__last - __first >= __chunk_size) {
2323         __insertion_sort(__first, __first + __chunk_size, __comp);
2324         __first += __chunk_size;
2325       }
2326       __insertion_sort(__first, __last, __comp);
2327     }
2328
2329   template<typename _RandomAccessIter, typename _Pointer>
2330     void
2331     __merge_sort_with_buffer(_RandomAccessIter __first, _RandomAccessIter __last,
2332                              _Pointer __buffer)
2333     {
2334       typedef typename iterator_traits<_RandomAccessIter>::difference_type _Distance;
2335
2336       _Distance __len = __last - __first;
2337       _Pointer __buffer_last = __buffer + __len;
2338
2339       _Distance __step_size = _M_chunk_size;
2340       __chunk_insertion_sort(__first, __last, __step_size);
2341
2342       while (__step_size < __len) {
2343         __merge_sort_loop(__first, __last, __buffer, __step_size);
2344         __step_size *= 2;
2345         __merge_sort_loop(__buffer, __buffer_last, __first, __step_size);
2346         __step_size *= 2;
2347       }
2348     }
2349
2350   template<typename _RandomAccessIter, typename _Pointer, typename _Compare>
2351     void
2352     __merge_sort_with_buffer(_RandomAccessIter __first, _RandomAccessIter __last,
2353                              _Pointer __buffer, _Compare __comp)
2354     {
2355       typedef typename iterator_traits<_RandomAccessIter>::difference_type _Distance;
2356
2357       _Distance __len = __last - __first;
2358       _Pointer __buffer_last = __buffer + __len;
2359
2360       _Distance __step_size = _M_chunk_size;
2361       __chunk_insertion_sort(__first, __last, __step_size, __comp);
2362
2363       while (__step_size < __len) {
2364         __merge_sort_loop(__first, __last, __buffer, __step_size, __comp);
2365         __step_size *= 2;
2366         __merge_sort_loop(__buffer, __buffer_last, __first, __step_size, __comp);
2367         __step_size *= 2;
2368       }
2369     }
2370
2371   template<typename _RandomAccessIter, typename _Pointer, typename _Distance>
2372     void
2373     __stable_sort_adaptive(_RandomAccessIter __first, _RandomAccessIter __last,
2374                            _Pointer __buffer, _Distance __buffer_size)
2375     {
2376       _Distance __len = (__last - __first + 1) / 2;
2377       _RandomAccessIter __middle = __first + __len;
2378       if (__len > __buffer_size) {
2379         __stable_sort_adaptive(__first, __middle, __buffer, __buffer_size);
2380         __stable_sort_adaptive(__middle, __last, __buffer, __buffer_size);
2381       }
2382       else {
2383         __merge_sort_with_buffer(__first, __middle, __buffer);
2384         __merge_sort_with_buffer(__middle, __last, __buffer);
2385       }
2386       __merge_adaptive(__first, __middle, __last, _Distance(__middle - __first),
2387                        _Distance(__last - __middle), __buffer, __buffer_size);
2388     }
2389
2390   template<typename _RandomAccessIter, typename _Pointer, typename _Distance,
2391            typename _Compare>
2392     void
2393     __stable_sort_adaptive(_RandomAccessIter __first, _RandomAccessIter __last,
2394                            _Pointer __buffer, _Distance __buffer_size,
2395                            _Compare __comp)
2396     {
2397       _Distance __len = (__last - __first + 1) / 2;
2398       _RandomAccessIter __middle = __first + __len;
2399       if (__len > __buffer_size) {
2400         __stable_sort_adaptive(__first, __middle, __buffer, __buffer_size,
2401                                __comp);
2402         __stable_sort_adaptive(__middle, __last, __buffer, __buffer_size,
2403                                __comp);
2404       }
2405       else {
2406         __merge_sort_with_buffer(__first, __middle, __buffer, __comp);
2407         __merge_sort_with_buffer(__middle, __last, __buffer, __comp);
2408       }
2409       __merge_adaptive(__first, __middle, __last, _Distance(__middle - __first),
2410                        _Distance(__last - __middle), __buffer, __buffer_size,
2411                        __comp);
2412     }
2413
2414   /**
2415    *  @brief Sort the elements of a sequence, preserving the relative order
2416    *         of equivalent elements.
2417    *  @param  first   An iterator.
2418    *  @param  last    Another iterator.
2419    *  @return  Nothing.
2420    *
2421    *  Sorts the elements in the range @p [first,last) in ascending order,
2422    *  such that @p *(i+1)<*i is false for each iterator @p i in the range
2423    *  @p [first,last-1).
2424    *
2425    *  The relative ordering of equivalent elements is preserved, so any two
2426    *  elements @p x and @p y in the range @p [first,last) such that
2427    *  @p x<y is false and @p y<x is false will have the same relative
2428    *  ordering after calling @p stable_sort().
2429   */
2430   template<typename _RandomAccessIter>
2431     inline void
2432     stable_sort(_RandomAccessIter __first, _RandomAccessIter __last)
2433     {
2434       typedef typename iterator_traits<_RandomAccessIter>::value_type _ValueType;
2435       typedef typename iterator_traits<_RandomAccessIter>::difference_type _DistanceType;
2436
2437       // concept requirements
2438       __glibcpp_function_requires(_Mutable_RandomAccessIteratorConcept<
2439             _RandomAccessIter>)
2440       __glibcpp_function_requires(_LessThanComparableConcept<_ValueType>)
2441
2442       _Temporary_buffer<_RandomAccessIter, _ValueType> buf(__first, __last);
2443       if (buf.begin() == 0)
2444         __inplace_stable_sort(__first, __last);
2445       else
2446         __stable_sort_adaptive(__first, __last, buf.begin(), _DistanceType(buf.size()));
2447     }
2448
2449   /**
2450    *  @brief Sort the elements of a sequence using a predicate for comparison,
2451    *         preserving the relative order of equivalent elements.
2452    *  @param  first   An iterator.
2453    *  @param  last    Another iterator.
2454    *  @param  comp    A comparison functor.
2455    *  @return  Nothing.
2456    *
2457    *  Sorts the elements in the range @p [first,last) in ascending order,
2458    *  such that @p comp(*(i+1),*i) is false for each iterator @p i in the
2459    *  range @p [first,last-1).
2460    *
2461    *  The relative ordering of equivalent elements is preserved, so any two
2462    *  elements @p x and @p y in the range @p [first,last) such that
2463    *  @p comp(x,y) is false and @p comp(y,x) is false will have the same
2464    *  relative ordering after calling @p stable_sort().
2465   */
2466   template<typename _RandomAccessIter, typename _Compare>
2467     inline void
2468     stable_sort(_RandomAccessIter __first, _RandomAccessIter __last, _Compare __comp)
2469     {
2470       typedef typename iterator_traits<_RandomAccessIter>::value_type _ValueType;
2471       typedef typename iterator_traits<_RandomAccessIter>::difference_type _DistanceType;
2472
2473       // concept requirements
2474       __glibcpp_function_requires(_Mutable_RandomAccessIteratorConcept<
2475             _RandomAccessIter>)
2476       __glibcpp_function_requires(_BinaryPredicateConcept<_Compare,
2477                                                           _ValueType, _ValueType>)
2478
2479       _Temporary_buffer<_RandomAccessIter, _ValueType> buf(__first, __last);
2480       if (buf.begin() == 0)
2481         __inplace_stable_sort(__first, __last, __comp);
2482       else
2483         __stable_sort_adaptive(__first, __last, buf.begin(), _DistanceType(buf.size()),
2484                                __comp);
2485     }
2486
2487   /**
2488    *  @brief Sort the smallest elements of a sequence.
2489    *  @param  first   An iterator.
2490    *  @param  middle  Another iterator.
2491    *  @param  last    Another iterator.
2492    *  @return  Nothing.
2493    *
2494    *  Sorts the smallest @p (middle-first) elements in the range
2495    *  @p [first,last) and moves them to the range @p [first,middle). The
2496    *  order of the remaining elements in the range @p [middle,last) is
2497    *  undefined.
2498    *  After the sort if @p i and @j are iterators in the range
2499    *  @p [first,middle) such that @i precedes @j and @k is an iterator in
2500    *  the range @p [middle,last) then @p *j<*i and @p *k<*i are both false.
2501   */
2502   template<typename _RandomAccessIter>
2503     void
2504     partial_sort(_RandomAccessIter __first,
2505                  _RandomAccessIter __middle,
2506                  _RandomAccessIter __last)
2507     {
2508       typedef typename iterator_traits<_RandomAccessIter>::value_type _ValueType;
2509
2510       // concept requirements
2511       __glibcpp_function_requires(_Mutable_RandomAccessIteratorConcept<
2512             _RandomAccessIter>)
2513       __glibcpp_function_requires(_LessThanComparableConcept<_ValueType>)
2514
2515       make_heap(__first, __middle);
2516       for (_RandomAccessIter __i = __middle; __i < __last; ++__i)
2517         if (*__i < *__first)
2518           __pop_heap(__first, __middle, __i, _ValueType(*__i));
2519       sort_heap(__first, __middle);
2520     }
2521
2522   /**
2523    *  @brief Sort the smallest elements of a sequence using a predicate
2524    *         for comparison.
2525    *  @param  first   An iterator.
2526    *  @param  middle  Another iterator.
2527    *  @param  last    Another iterator.
2528    *  @param  comp    A comparison functor.
2529    *  @return  Nothing.
2530    *
2531    *  Sorts the smallest @p (middle-first) elements in the range
2532    *  @p [first,last) and moves them to the range @p [first,middle). The
2533    *  order of the remaining elements in the range @p [middle,last) is
2534    *  undefined.
2535    *  After the sort if @p i and @j are iterators in the range
2536    *  @p [first,middle) such that @i precedes @j and @k is an iterator in
2537    *  the range @p [middle,last) then @p *comp(j,*i) and @p comp(*k,*i)
2538    *  are both false.
2539   */
2540   template<typename _RandomAccessIter, typename _Compare>
2541     void
2542     partial_sort(_RandomAccessIter __first,
2543                  _RandomAccessIter __middle,
2544                  _RandomAccessIter __last,
2545                  _Compare __comp)
2546     {
2547       typedef typename iterator_traits<_RandomAccessIter>::value_type _ValueType;
2548
2549       // concept requirements
2550       __glibcpp_function_requires(_Mutable_RandomAccessIteratorConcept<
2551             _RandomAccessIter>)
2552       __glibcpp_function_requires(_BinaryPredicateConcept<_Compare,
2553                                                           _ValueType, _ValueType>)
2554
2555       make_heap(__first, __middle, __comp);
2556       for (_RandomAccessIter __i = __middle; __i < __last; ++__i)
2557         if (__comp(*__i, *__first))
2558           __pop_heap(__first, __middle, __i, _ValueType(*__i), __comp);
2559       sort_heap(__first, __middle, __comp);
2560     }
2561
2562   /**
2563    *  @brief Copy the smallest elements of a sequence.
2564    *  @param  first   An iterator.
2565    *  @param  last    Another iterator.
2566    *  @param  result_first   A random-access iterator.
2567    *  @param  result_last    Another random-access iterator.
2568    *  @return   An iterator indicating the end of the resulting sequence.
2569    *
2570    *  Copies and sorts the smallest N values from the range @p [first,last)
2571    *  to the range beginning at @p result_first, where the number of
2572    *  elements to be copied, @p N, is the smaller of @p (last-first) and
2573    *  @p (result_last-result_first).
2574    *  After the sort if @p i and @j are iterators in the range
2575    *  @p [result_first,result_first+N) such that @i precedes @j then
2576    *  @p *j<*i is false.
2577    *  The value returned is @p result_first+N.
2578   */
2579   template<typename _InputIter, typename _RandomAccessIter>
2580     _RandomAccessIter
2581     partial_sort_copy(_InputIter __first, _InputIter __last,
2582                       _RandomAccessIter __result_first,
2583                       _RandomAccessIter __result_last)
2584     {
2585       typedef typename iterator_traits<_InputIter>::value_type _InputValueType;
2586       typedef typename iterator_traits<_RandomAccessIter>::value_type _OutputValueType;
2587       typedef typename iterator_traits<_RandomAccessIter>::difference_type _DistanceType;
2588
2589       // concept requirements
2590       __glibcpp_function_requires(_InputIteratorConcept<_InputIter>)
2591       __glibcpp_function_requires(_ConvertibleConcept<_InputValueType, _OutputValueType>)
2592       __glibcpp_function_requires(_LessThanComparableConcept<_OutputValueType>)
2593       __glibcpp_function_requires(_LessThanComparableConcept<_InputValueType>)
2594
2595       if (__result_first == __result_last) return __result_last;
2596       _RandomAccessIter __result_real_last = __result_first;
2597       while(__first != __last && __result_real_last != __result_last) {
2598         *__result_real_last = *__first;
2599         ++__result_real_last;
2600         ++__first;
2601       }
2602       make_heap(__result_first, __result_real_last);
2603       while (__first != __last) {
2604         if (*__first < *__result_first)
2605           __adjust_heap(__result_first, _DistanceType(0),
2606                         _DistanceType(__result_real_last - __result_first),
2607                         _InputValueType(*__first));
2608         ++__first;
2609       }
2610       sort_heap(__result_first, __result_real_last);
2611       return __result_real_last;
2612     }
2613
2614   /**
2615    *  @brief Copy the smallest elements of a sequence using a predicate for
2616    *         comparison.
2617    *  @param  first   An input iterator.
2618    *  @param  last    Another input iterator.
2619    *  @param  result_first   A random-access iterator.
2620    *  @param  result_last    Another random-access iterator.
2621    *  @param  comp    A comparison functor.
2622    *  @return   An iterator indicating the end of the resulting sequence.
2623    *
2624    *  Copies and sorts the smallest N values from the range @p [first,last)
2625    *  to the range beginning at @p result_first, where the number of
2626    *  elements to be copied, @p N, is the smaller of @p (last-first) and
2627    *  @p (result_last-result_first).
2628    *  After the sort if @p i and @j are iterators in the range
2629    *  @p [result_first,result_first+N) such that @i precedes @j then
2630    *  @p comp(*j,*i) is false.
2631    *  The value returned is @p result_first+N.
2632   */
2633   template<typename _InputIter, typename _RandomAccessIter, typename _Compare>
2634     _RandomAccessIter
2635     partial_sort_copy(_InputIter __first, _InputIter __last,
2636                       _RandomAccessIter __result_first,
2637                       _RandomAccessIter __result_last,
2638                       _Compare __comp)
2639     {
2640       typedef typename iterator_traits<_InputIter>::value_type _InputValueType;
2641       typedef typename iterator_traits<_RandomAccessIter>::value_type _OutputValueType;
2642       typedef typename iterator_traits<_RandomAccessIter>::difference_type _DistanceType;
2643
2644       // concept requirements
2645       __glibcpp_function_requires(_InputIteratorConcept<_InputIter>)
2646       __glibcpp_function_requires(_Mutable_RandomAccessIteratorConcept<_RandomAccessIter>)
2647       __glibcpp_function_requires(_ConvertibleConcept<_InputValueType, _OutputValueType>)
2648       __glibcpp_function_requires(_BinaryPredicateConcept<_Compare,
2649                                   _OutputValueType, _OutputValueType>)
2650
2651       if (__result_first == __result_last) return __result_last;
2652       _RandomAccessIter __result_real_last = __result_first;
2653       while(__first != __last && __result_real_last != __result_last) {
2654         *__result_real_last = *__first;
2655         ++__result_real_last;
2656         ++__first;
2657       }
2658       make_heap(__result_first, __result_real_last, __comp);
2659       while (__first != __last) {
2660         if (__comp(*__first, *__result_first))
2661           __adjust_heap(__result_first, _DistanceType(0),
2662                         _DistanceType(__result_real_last - __result_first),
2663                         _InputValueType(*__first),
2664                         __comp);
2665         ++__first;
2666       }
2667       sort_heap(__result_first, __result_real_last, __comp);
2668       return __result_real_last;
2669     }
2670
2671   /**
2672    *  @brief Sort a sequence just enough to find a particular position.
2673    *  @param  first   An iterator.
2674    *  @param  nth     Another iterator.
2675    *  @param  last    Another iterator.
2676    *  @return  Nothing.
2677    *
2678    *  Rearranges the elements in the range @p [first,last) so that @p *nth
2679    *  is the same element that would have been in that position had the
2680    *  whole sequence been sorted.
2681    *  whole sequence been sorted. The elements either side of @p *nth are
2682    *  not completely sorted, but for any iterator @i in the range
2683    *  @p [first,nth) and any iterator @j in the range @p [nth,last) it
2684    *  holds that @p *j<*i is false.
2685   */
2686   template<typename _RandomAccessIter>
2687     void
2688     nth_element(_RandomAccessIter __first,
2689                 _RandomAccessIter __nth,
2690                 _RandomAccessIter __last)
2691     {
2692       typedef typename iterator_traits<_RandomAccessIter>::value_type _ValueType;
2693
2694       // concept requirements
2695       __glibcpp_function_requires(_Mutable_RandomAccessIteratorConcept<_RandomAccessIter>)
2696       __glibcpp_function_requires(_LessThanComparableConcept<_ValueType>)
2697
2698       while (__last - __first > 3) {
2699         _RandomAccessIter __cut =
2700           __unguarded_partition(__first, __last,
2701                                 _ValueType(__median(*__first,
2702                                                     *(__first + (__last - __first)/2),
2703                                                     *(__last - 1))));
2704         if (__cut <= __nth)
2705           __first = __cut;
2706         else
2707           __last = __cut;
2708       }
2709       __insertion_sort(__first, __last);
2710     }
2711
2712   /**
2713    *  @brief Sort a sequence just enough to find a particular position
2714    *         using a predicate for comparison.
2715    *  @param  first   An iterator.
2716    *  @param  nth     Another iterator.
2717    *  @param  last    Another iterator.
2718    *  @param  comp    A comparison functor.
2719    *  @return  Nothing.
2720    *
2721    *  Rearranges the elements in the range @p [first,last) so that @p *nth
2722    *  is the same element that would have been in that position had the
2723    *  whole sequence been sorted. The elements either side of @p *nth are
2724    *  not completely sorted, but for any iterator @i in the range
2725    *  @p [first,nth) and any iterator @j in the range @p [nth,last) it
2726    *  holds that @p comp(*j,*i) is false.
2727   */
2728   template<typename _RandomAccessIter, typename _Compare>
2729     void
2730     nth_element(_RandomAccessIter __first,
2731                 _RandomAccessIter __nth,
2732                 _RandomAccessIter __last,
2733                             _Compare __comp)
2734     {
2735       typedef typename iterator_traits<_RandomAccessIter>::value_type _ValueType;
2736
2737       // concept requirements
2738       __glibcpp_function_requires(_Mutable_RandomAccessIteratorConcept<_RandomAccessIter>)
2739       __glibcpp_function_requires(_BinaryPredicateConcept<_Compare,
2740                                   _ValueType, _ValueType>)
2741
2742       while (__last - __first > 3) {
2743         _RandomAccessIter __cut =
2744           __unguarded_partition(__first, __last,
2745                                 _ValueType(__median(*__first,
2746                                                     *(__first + (__last - __first)/2),
2747                                                     *(__last - 1),
2748                                                     __comp)),
2749                                 __comp);
2750         if (__cut <= __nth)
2751           __first = __cut;
2752         else
2753           __last = __cut;
2754       }
2755       __insertion_sort(__first, __last, __comp);
2756     }
2757
2758
2759   /**
2760    *  @brief Finds the first position in which @a val could be inserted
2761    *         without changing the ordering.
2762    *  @param  first   An iterator.
2763    *  @param  last    Another iterator.
2764    *  @param  val     The search term.
2765    *  @return  An iterator pointing to the first element "not less than" @a val.
2766    *  @ingroup binarysearch
2767   */
2768   template<typename _ForwardIter, typename _Tp>
2769     _ForwardIter
2770     lower_bound(_ForwardIter __first, _ForwardIter __last, const _Tp& __val)
2771     {
2772       typedef typename iterator_traits<_ForwardIter>::value_type _ValueType;
2773       typedef typename iterator_traits<_ForwardIter>::difference_type _DistanceType;
2774
2775       // concept requirements
2776       // Note that these are slightly stricter than those of the 4-argument
2777       // version, defined next.  The difference is in the strictness of the
2778       // comparison operations... so for looser checking, define your own
2779       // comparison function, as was intended.
2780       __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter>)
2781       __glibcpp_function_requires(_SameTypeConcept<_Tp, _ValueType>)
2782       __glibcpp_function_requires(_LessThanComparableConcept<_Tp>)
2783
2784       _DistanceType __len = std::distance(__first, __last);
2785       _DistanceType __half;
2786       _ForwardIter __middle;
2787
2788       while (__len > 0) {
2789         __half = __len >> 1;
2790         __middle = __first;
2791         advance(__middle, __half);
2792         if (*__middle < __val) {
2793           __first = __middle;
2794           ++__first;
2795           __len = __len - __half - 1;
2796         }
2797         else
2798           __len = __half;
2799       }
2800       return __first;
2801     }
2802
2803   /**
2804    *  @brief Finds the first position in which @a val could be inserted
2805    *         without changing the ordering.
2806    *  @param  first   An iterator.
2807    *  @param  last    Another iterator.
2808    *  @param  val     The search term.
2809    *  @param  comp    A functor to use for comparisons.
2810    *  @return  An iterator pointing to the first element "not less than" @a val.
2811    *  @ingroup binarysearch
2812    *
2813    *  The comparison function should have the same effects on ordering as
2814    *  the function used for the initial sort.
2815   */
2816   template<typename _ForwardIter, typename _Tp, typename _Compare>
2817     _ForwardIter
2818     lower_bound(_ForwardIter __first, _ForwardIter __last,
2819                 const _Tp& __val, _Compare __comp)
2820     {
2821       typedef typename iterator_traits<_ForwardIter>::value_type _ValueType;
2822       typedef typename iterator_traits<_ForwardIter>::difference_type _DistanceType;
2823
2824       // concept requirements
2825       __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter>)
2826       __glibcpp_function_requires(_BinaryPredicateConcept<_Compare, _ValueType, _Tp>)
2827
2828       _DistanceType __len = std::distance(__first, __last);
2829       _DistanceType __half;
2830       _ForwardIter __middle;
2831
2832       while (__len > 0) {
2833         __half = __len >> 1;
2834         __middle = __first;
2835         advance(__middle, __half);
2836         if (__comp(*__middle, __val)) {
2837           __first = __middle;
2838           ++__first;
2839           __len = __len - __half - 1;
2840         }
2841         else
2842           __len = __half;
2843       }
2844       return __first;
2845     }
2846
2847   /**
2848    *  @brief Finds the last position in which @a val could be inserted
2849    *         without changing the ordering.
2850    *  @param  first   An iterator.
2851    *  @param  last    Another iterator.
2852    *  @param  val     The search term.
2853    *  @return  An iterator pointing to the first element greater than @a val.
2854    *  @ingroup binarysearch
2855   */
2856   template<typename _ForwardIter, typename _Tp>
2857     _ForwardIter
2858     upper_bound(_ForwardIter __first, _ForwardIter __last, const _Tp& __val)
2859     {
2860       typedef typename iterator_traits<_ForwardIter>::value_type _ValueType;
2861       typedef typename iterator_traits<_ForwardIter>::difference_type _DistanceType;
2862
2863       // concept requirements
2864       // See comments on lower_bound.
2865       __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter>)
2866       __glibcpp_function_requires(_SameTypeConcept<_Tp, _ValueType>)
2867       __glibcpp_function_requires(_LessThanComparableConcept<_Tp>)
2868
2869       _DistanceType __len = std::distance(__first, __last);
2870       _DistanceType __half;
2871       _ForwardIter __middle;
2872
2873       while (__len > 0) {
2874         __half = __len >> 1;
2875         __middle = __first;
2876         advance(__middle, __half);
2877         if (__val < *__middle)
2878           __len = __half;
2879         else {
2880           __first = __middle;
2881           ++__first;
2882           __len = __len - __half - 1;
2883         }
2884       }
2885       return __first;
2886     }
2887
2888   /**
2889    *  @brief Finds the last position in which @a val could be inserted
2890    *         without changing the ordering.
2891    *  @param  first   An iterator.
2892    *  @param  last    Another iterator.
2893    *  @param  val     The search term.
2894    *  @param  comp    A functor to use for comparisons.
2895    *  @return  An iterator pointing to the first element greater than @a val.
2896    *  @ingroup binarysearch
2897    *
2898    *  The comparison function should have the same effects on ordering as
2899    *  the function used for the initial sort.
2900   */
2901   template<typename _ForwardIter, typename _Tp, typename _Compare>
2902     _ForwardIter
2903     upper_bound(_ForwardIter __first, _ForwardIter __last,
2904                 const _Tp& __val, _Compare __comp)
2905     {
2906       typedef typename iterator_traits<_ForwardIter>::value_type _ValueType;
2907       typedef typename iterator_traits<_ForwardIter>::difference_type _DistanceType;
2908
2909       // concept requirements
2910       __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter>)
2911       __glibcpp_function_requires(_BinaryPredicateConcept<_Compare, _Tp, _ValueType>)
2912
2913       _DistanceType __len = std::distance(__first, __last);
2914       _DistanceType __half;
2915       _ForwardIter __middle;
2916
2917       while (__len > 0) {
2918         __half = __len >> 1;
2919         __middle = __first;
2920         advance(__middle, __half);
2921         if (__comp(__val, *__middle))
2922           __len = __half;
2923         else {
2924           __first = __middle;
2925           ++__first;
2926           __len = __len - __half - 1;
2927         }
2928       }
2929       return __first;
2930     }
2931
2932   /**
2933    *  @brief Finds the largest subrange in which @a val could be inserted
2934    *         at any place in it without changing the ordering.
2935    *  @param  first   An iterator.
2936    *  @param  last    Another iterator.
2937    *  @param  val     The search term.
2938    *  @return  An pair of iterators defining the subrange.
2939    *  @ingroup binarysearch
2940    *
2941    *  This is equivalent to
2942    *  @code
2943    *    std::make_pair(lower_bound(first, last, val),
2944    *                   upper_bound(first, last, val))
2945    *  @endcode
2946    *  but does not actually call those functions.
2947   */
2948   template<typename _ForwardIter, typename _Tp>
2949     pair<_ForwardIter, _ForwardIter>
2950     equal_range(_ForwardIter __first, _ForwardIter __last, const _Tp& __val)
2951     {
2952       typedef typename iterator_traits<_ForwardIter>::value_type _ValueType;
2953       typedef typename iterator_traits<_ForwardIter>::difference_type _DistanceType;
2954
2955       // concept requirements
2956       // See comments on lower_bound.
2957       __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter>)
2958       __glibcpp_function_requires(_SameTypeConcept<_Tp, _ValueType>)
2959       __glibcpp_function_requires(_LessThanComparableConcept<_Tp>)
2960
2961       _DistanceType __len = std::distance(__first, __last);
2962       _DistanceType __half;
2963       _ForwardIter __middle, __left, __right;
2964
2965       while (__len > 0) {
2966         __half = __len >> 1;
2967         __middle = __first;
2968         advance(__middle, __half);
2969         if (*__middle < __val) {
2970           __first = __middle;
2971           ++__first;
2972           __len = __len - __half - 1;
2973         }
2974         else if (__val < *__middle)
2975           __len = __half;
2976         else {
2977           __left = lower_bound(__first, __middle, __val);
2978           advance(__first, __len);
2979           __right = upper_bound(++__middle, __first, __val);
2980           return pair<_ForwardIter, _ForwardIter>(__left, __right);
2981         }
2982       }
2983       return pair<_ForwardIter, _ForwardIter>(__first, __first);
2984     }
2985
2986   /**
2987    *  @brief Finds the largest subrange in which @a val could be inserted
2988    *         at any place in it without changing the ordering.
2989    *  @param  first   An iterator.
2990    *  @param  last    Another iterator.
2991    *  @param  val     The search term.
2992    *  @param  comp    A functor to use for comparisons.
2993    *  @return  An pair of iterators defining the subrange.
2994    *  @ingroup binarysearch
2995    *
2996    *  This is equivalent to
2997    *  @code
2998    *    std::make_pair(lower_bound(first, last, val, comp),
2999    *                   upper_bound(first, last, val, comp))
3000    *  @endcode
3001    *  but does not actually call those functions.
3002   */
3003   template<typename _ForwardIter, typename _Tp, typename _Compare>
3004     pair<_ForwardIter, _ForwardIter>
3005     equal_range(_ForwardIter __first, _ForwardIter __last, const _Tp& __val,
3006                 _Compare __comp)
3007     {
3008       typedef typename iterator_traits<_ForwardIter>::value_type _ValueType;
3009       typedef typename iterator_traits<_ForwardIter>::difference_type _DistanceType;
3010
3011       // concept requirements
3012       __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter>)
3013       __glibcpp_function_requires(_BinaryPredicateConcept<_Compare, _ValueType, _Tp>)
3014       __glibcpp_function_requires(_BinaryPredicateConcept<_Compare, _Tp, _ValueType>)
3015
3016       _DistanceType __len = std::distance(__first, __last);
3017       _DistanceType __half;
3018       _ForwardIter __middle, __left, __right;
3019
3020       while (__len > 0) {
3021         __half = __len >> 1;
3022         __middle = __first;
3023         advance(__middle, __half);
3024         if (__comp(*__middle, __val)) {
3025           __first = __middle;
3026           ++__first;
3027           __len = __len - __half - 1;
3028         }
3029         else if (__comp(__val, *__middle))
3030           __len = __half;
3031         else {
3032           __left = lower_bound(__first, __middle, __val, __comp);
3033           advance(__first, __len);
3034           __right = upper_bound(++__middle, __first, __val, __comp);
3035           return pair<_ForwardIter, _ForwardIter>(__left, __right);
3036         }
3037       }
3038       return pair<_ForwardIter, _ForwardIter>(__first, __first);
3039     }
3040
3041   /**
3042    *  @brief Determines whether an element exists in a range.
3043    *  @param  first   An iterator.
3044    *  @param  last    Another iterator.
3045    *  @param  val     The search term.
3046    *  @return  True if @a val (or its equivelent) is in [@a first,@a last ].
3047    *  @ingroup binarysearch
3048    *
3049    *  Note that this does not actually return an iterator to @a val.  For
3050    *  that, use std::find or a container's specialized find member functions.
3051   */
3052   template<typename _ForwardIter, typename _Tp>
3053     bool
3054     binary_search(_ForwardIter __first, _ForwardIter __last,
3055                   const _Tp& __val)
3056     {
3057       // concept requirements
3058       // See comments on lower_bound.
3059       __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter>)
3060       __glibcpp_function_requires(_SameTypeConcept<_Tp,
3061                 typename iterator_traits<_ForwardIter>::value_type>)
3062       __glibcpp_function_requires(_LessThanComparableConcept<_Tp>)
3063
3064       _ForwardIter __i = lower_bound(__first, __last, __val);
3065       return __i != __last && !(__val < *__i);
3066     }
3067
3068   /**
3069    *  @brief Determines whether an element exists in a range.
3070    *  @param  first   An iterator.
3071    *  @param  last    Another iterator.
3072    *  @param  val     The search term.
3073    *  @param  comp    A functor to use for comparisons.
3074    *  @return  True if @a val (or its equivelent) is in [@a first,@a last ].
3075    *  @ingroup binarysearch
3076    *
3077    *  Note that this does not actually return an iterator to @a val.  For
3078    *  that, use std::find or a container's specialized find member functions.
3079    *
3080    *  The comparison function should have the same effects on ordering as
3081    *  the function used for the initial sort.
3082   */
3083   template<typename _ForwardIter, typename _Tp, typename _Compare>
3084     bool
3085     binary_search(_ForwardIter __first, _ForwardIter __last,
3086                   const _Tp& __val, _Compare __comp)
3087     {
3088       // concept requirements
3089       __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter>)
3090       __glibcpp_function_requires(_BinaryPredicateConcept<_Compare,
3091                 typename iterator_traits<_ForwardIter>::value_type, _Tp>)
3092       __glibcpp_function_requires(_BinaryPredicateConcept<_Compare, _Tp,
3093                 typename iterator_traits<_ForwardIter>::value_type>)
3094
3095       _ForwardIter __i = lower_bound(__first, __last, __val, __comp);
3096       return __i != __last && !__comp(__val, *__i);
3097     }
3098
3099   /**
3100    *  @brief Merges two sorted ranges.
3101    *  @param  first1  An iterator.
3102    *  @param  first2  Another iterator.
3103    *  @param  last1   Another iterator.
3104    *  @param  last2   Another iterator.
3105    *  @param  result  An iterator pointing to the end of the merged range.
3106    *  @return  An iterator pointing to the first element "not less than" @a val.
3107    *
3108    *  Merges the ranges [first1,last1) and [first2,last2) into the sorted range
3109    *  [result, result + (last1-first1) + (last2-first2)).  Both input ranges
3110    *  must be sorted, and the output range must not overlap with either of
3111    *  the input ranges.  The sort is @e stable, that is, for equivalent
3112    *  elements in the two ranges, elements from the first range will always
3113    *  come before elements from the second.
3114   */
3115   template<typename _InputIter1, typename _InputIter2, typename _OutputIter>
3116     _OutputIter
3117     merge(_InputIter1 __first1, _InputIter1 __last1,
3118           _InputIter2 __first2, _InputIter2 __last2,
3119           _OutputIter __result)
3120     {
3121       // concept requirements
3122       __glibcpp_function_requires(_InputIteratorConcept<_InputIter1>)
3123       __glibcpp_function_requires(_InputIteratorConcept<_InputIter2>)
3124       __glibcpp_function_requires(_OutputIteratorConcept<_OutputIter,
3125             typename iterator_traits<_InputIter1>::value_type>)
3126       __glibcpp_function_requires(_SameTypeConcept<
3127             typename iterator_traits<_InputIter1>::value_type,
3128             typename iterator_traits<_InputIter2>::value_type>)
3129       __glibcpp_function_requires(_LessThanComparableConcept<
3130             typename iterator_traits<_InputIter1>::value_type>)
3131
3132       while (__first1 != __last1 && __first2 != __last2) {
3133         if (*__first2 < *__first1) {
3134           *__result = *__first2;
3135           ++__first2;
3136         }
3137         else {
3138           *__result = *__first1;
3139           ++__first1;
3140         }
3141         ++__result;
3142       }
3143       return copy(__first2, __last2, copy(__first1, __last1, __result));
3144     }
3145
3146   /**
3147    *  @brief Merges two sorted ranges.
3148    *  @param  first1  An iterator.
3149    *  @param  first2  Another iterator.
3150    *  @param  last1   Another iterator.
3151    *  @param  last2   Another iterator.
3152    *  @param  result  An iterator pointing to the end of the merged range.
3153    *  @param  comp    A functor to use for comparisons.
3154    *  @return  An iterator pointing to the first element "not less than" @a val.
3155    *
3156    *  Merges the ranges [first1,last1) and [first2,last2) into the sorted range
3157    *  [result, result + (last1-first1) + (last2-first2)).  Both input ranges
3158    *  must be sorted, and the output range must not overlap with either of
3159    *  the input ranges.  The sort is @e stable, that is, for equivalent
3160    *  elements in the two ranges, elements from the first range will always
3161    *  come before elements from the second.
3162    *
3163    *  The comparison function should have the same effects on ordering as
3164    *  the function used for the initial sort.
3165   */
3166   template<typename _InputIter1, typename _InputIter2, typename _OutputIter,
3167            typename _Compare>
3168     _OutputIter
3169     merge(_InputIter1 __first1, _InputIter1 __last1,
3170           _InputIter2 __first2, _InputIter2 __last2,
3171           _OutputIter __result, _Compare __comp)
3172     {
3173       // concept requirements
3174       __glibcpp_function_requires(_InputIteratorConcept<_InputIter1>)
3175       __glibcpp_function_requires(_InputIteratorConcept<_InputIter2>)
3176       __glibcpp_function_requires(_SameTypeConcept<
3177             typename iterator_traits<_InputIter1>::value_type,
3178             typename iterator_traits<_InputIter2>::value_type>)
3179       __glibcpp_function_requires(_OutputIteratorConcept<_OutputIter,
3180             typename iterator_traits<_InputIter1>::value_type>)
3181       __glibcpp_function_requires(_BinaryPredicateConcept<_Compare,
3182             typename iterator_traits<_InputIter1>::value_type,
3183             typename iterator_traits<_InputIter2>::value_type>)
3184
3185       while (__first1 != __last1 && __first2 != __last2) {
3186         if (__comp(*__first2, *__first1)) {
3187           *__result = *__first2;
3188           ++__first2;
3189         }
3190         else {
3191           *__result = *__first1;
3192           ++__first1;
3193         }
3194         ++__result;
3195       }
3196       return copy(__first2, __last2, copy(__first1, __last1, __result));
3197     }
3198
3199   /**
3200    *  @if maint
3201    *  This is a helper function for the merge routines.
3202    *  @endif
3203   */
3204   template<typename _BidirectionalIter, typename _Distance>
3205     void
3206     __merge_without_buffer(_BidirectionalIter __first,
3207                            _BidirectionalIter __middle,
3208                            _BidirectionalIter __last,
3209                            _Distance __len1, _Distance __len2)
3210     {
3211       if (__len1 == 0 || __len2 == 0)
3212         return;
3213       if (__len1 + __len2 == 2) {
3214         if (*__middle < *__first)
3215               iter_swap(__first, __middle);
3216         return;
3217       }
3218       _BidirectionalIter __first_cut = __first;
3219       _BidirectionalIter __second_cut = __middle;
3220       _Distance __len11 = 0;
3221       _Distance __len22 = 0;
3222       if (__len1 > __len2) {
3223         __len11 = __len1 / 2;
3224         advance(__first_cut, __len11);
3225         __second_cut = lower_bound(__middle, __last, *__first_cut);
3226         __len22 = std::distance(__middle, __second_cut);
3227       }
3228       else {
3229         __len22 = __len2 / 2;
3230         advance(__second_cut, __len22);
3231         __first_cut = upper_bound(__first, __middle, *__second_cut);
3232         __len11 = std::distance(__first, __first_cut);
3233       }
3234       rotate(__first_cut, __middle, __second_cut);
3235       _BidirectionalIter __new_middle = __first_cut;
3236       advance(__new_middle, std::distance(__middle, __second_cut));
3237       __merge_without_buffer(__first, __first_cut, __new_middle,
3238                              __len11, __len22);
3239       __merge_without_buffer(__new_middle, __second_cut, __last,
3240                              __len1 - __len11, __len2 - __len22);
3241     }
3242
3243   /**
3244    *  @if maint
3245    *  This is a helper function for the merge routines.
3246    *  @endif
3247   */
3248   template<typename _BidirectionalIter, typename _Distance, typename _Compare>
3249     void
3250     __merge_without_buffer(_BidirectionalIter __first,
3251                            _BidirectionalIter __middle,
3252                            _BidirectionalIter __last,
3253                            _Distance __len1, _Distance __len2,
3254                            _Compare __comp)
3255     {
3256       if (__len1 == 0 || __len2 == 0)
3257         return;
3258       if (__len1 + __len2 == 2) {
3259         if (__comp(*__middle, *__first))
3260               iter_swap(__first, __middle);
3261         return;
3262       }
3263       _BidirectionalIter __first_cut = __first;
3264       _BidirectionalIter __second_cut = __middle;
3265       _Distance __len11 = 0;
3266       _Distance __len22 = 0;
3267       if (__len1 > __len2) {
3268         __len11 = __len1 / 2;
3269         advance(__first_cut, __len11);
3270         __second_cut = lower_bound(__middle, __last, *__first_cut, __comp);
3271         __len22 = std::distance(__middle, __second_cut);
3272       }
3273       else {
3274         __len22 = __len2 / 2;
3275         advance(__second_cut, __len22);
3276         __first_cut = upper_bound(__first, __middle, *__second_cut, __comp);
3277         __len11 = std::distance(__first, __first_cut);
3278       }
3279       rotate(__first_cut, __middle, __second_cut);
3280       _BidirectionalIter __new_middle = __first_cut;
3281       advance(__new_middle, std::distance(__middle, __second_cut));
3282       __merge_without_buffer(__first, __first_cut, __new_middle,
3283                              __len11, __len22, __comp);
3284       __merge_without_buffer(__new_middle, __second_cut, __last,
3285                              __len1 - __len11, __len2 - __len22, __comp);
3286     }
3287
3288   /**
3289    *  @if maint
3290    *  This is a helper function for the merge routines.
3291    *  @endif
3292   */
3293   template<typename _BidirectionalIter1, typename _BidirectionalIter2,
3294            typename _Distance>
3295     _BidirectionalIter1
3296     __rotate_adaptive(_BidirectionalIter1 __first,
3297                       _BidirectionalIter1 __middle,
3298                       _BidirectionalIter1 __last,
3299                       _Distance __len1, _Distance __len2,
3300                       _BidirectionalIter2 __buffer,
3301                       _Distance __buffer_size)
3302     {
3303       _BidirectionalIter2 __buffer_end;
3304       if (__len1 > __len2 && __len2 <= __buffer_size) {
3305         __buffer_end = copy(__middle, __last, __buffer);
3306         copy_backward(__first, __middle, __last);
3307         return copy(__buffer, __buffer_end, __first);
3308       }
3309       else if (__len1 <= __buffer_size) {
3310         __buffer_end = copy(__first, __middle, __buffer);
3311         copy(__middle, __last, __first);
3312         return copy_backward(__buffer, __buffer_end, __last);
3313       }
3314       else {
3315         rotate(__first, __middle, __last);
3316         advance(__first, std::distance(__middle, __last));
3317         return __first;
3318       }
3319     }
3320
3321   /**
3322    *  @if maint
3323    *  This is a helper function for the merge routines.
3324    *  @endif
3325   */
3326   template<typename _BidirectionalIter1, typename _BidirectionalIter2,
3327            typename _BidirectionalIter3>
3328     _BidirectionalIter3
3329     __merge_backward(_BidirectionalIter1 __first1, _BidirectionalIter1 __last1,
3330                      _BidirectionalIter2 __first2, _BidirectionalIter2 __last2,
3331                      _BidirectionalIter3 __result)
3332     {
3333       if (__first1 == __last1)
3334         return copy_backward(__first2, __last2, __result);
3335       if (__first2 == __last2)
3336         return copy_backward(__first1, __last1, __result);
3337       --__last1;
3338       --__last2;
3339       while (true) {
3340         if (*__last2 < *__last1) {
3341           *--__result = *__last1;
3342           if (__first1 == __last1)
3343             return copy_backward(__first2, ++__last2, __result);
3344           --__last1;
3345         }
3346         else {
3347           *--__result = *__last2;
3348           if (__first2 == __last2)
3349             return copy_backward(__first1, ++__last1, __result);
3350           --__last2;
3351         }
3352       }
3353     }
3354
3355   /**
3356    *  @if maint
3357    *  This is a helper function for the merge routines.
3358    *  @endif
3359   */
3360   template<typename _BidirectionalIter1, typename _BidirectionalIter2,
3361            typename _BidirectionalIter3, typename _Compare>
3362     _BidirectionalIter3
3363     __merge_backward(_BidirectionalIter1 __first1, _BidirectionalIter1 __last1,
3364                      _BidirectionalIter2 __first2, _BidirectionalIter2 __last2,
3365                      _BidirectionalIter3 __result,
3366                      _Compare __comp)
3367     {
3368       if (__first1 == __last1)
3369         return copy_backward(__first2, __last2, __result);
3370       if (__first2 == __last2)
3371         return copy_backward(__first1, __last1, __result);
3372       --__last1;
3373       --__last2;
3374       while (true) {
3375         if (__comp(*__last2, *__last1)) {
3376           *--__result = *__last1;
3377           if (__first1 == __last1)
3378             return copy_backward(__first2, ++__last2, __result);
3379           --__last1;
3380         }
3381         else {
3382           *--__result = *__last2;
3383           if (__first2 == __last2)
3384             return copy_backward(__first1, ++__last1, __result);
3385           --__last2;
3386         }
3387       }
3388     }
3389
3390   /**
3391    *  @if maint
3392    *  This is a helper function for the merge routines.
3393    *  @endif
3394   */
3395   template<typename _BidirectionalIter, typename _Distance, typename _Pointer>
3396     void
3397     __merge_adaptive(_BidirectionalIter __first,
3398                      _BidirectionalIter __middle,
3399                      _BidirectionalIter __last,
3400                      _Distance __len1, _Distance __len2,
3401                      _Pointer __buffer, _Distance __buffer_size)
3402     {
3403           if (__len1 <= __len2 && __len1 <= __buffer_size) {
3404             _Pointer __buffer_end = copy(__first, __middle, __buffer);
3405             merge(__buffer, __buffer_end, __middle, __last, __first);
3406           }
3407           else if (__len2 <= __buffer_size) {
3408             _Pointer __buffer_end = copy(__middle, __last, __buffer);
3409             __merge_backward(__first, __middle, __buffer, __buffer_end, __last);
3410           }
3411           else {
3412             _BidirectionalIter __first_cut = __first;
3413             _BidirectionalIter __second_cut = __middle;
3414             _Distance __len11 = 0;
3415             _Distance __len22 = 0;
3416             if (__len1 > __len2) {
3417                   __len11 = __len1 / 2;
3418                   advance(__first_cut, __len11);
3419                   __second_cut = lower_bound(__middle, __last, *__first_cut);
3420                   __len22 = std::distance(__middle, __second_cut);
3421             }
3422             else {
3423                   __len22 = __len2 / 2;
3424                   advance(__second_cut, __len22);
3425                   __first_cut = upper_bound(__first, __middle, *__second_cut);
3426                   __len11 = std::distance(__first, __first_cut);
3427             }
3428             _BidirectionalIter __new_middle =
3429                   __rotate_adaptive(__first_cut, __middle, __second_cut,
3430                                     __len1 - __len11, __len22, __buffer,
3431                                     __buffer_size);
3432             __merge_adaptive(__first, __first_cut, __new_middle, __len11,
3433                              __len22, __buffer, __buffer_size);
3434             __merge_adaptive(__new_middle, __second_cut, __last, __len1 - __len11,
3435                              __len2 - __len22, __buffer, __buffer_size);
3436           }
3437     }
3438
3439   /**
3440    *  @if maint
3441    *  This is a helper function for the merge routines.
3442    *  @endif
3443   */
3444   template<typename _BidirectionalIter, typename _Distance, typename _Pointer,
3445            typename _Compare>
3446     void
3447     __merge_adaptive(_BidirectionalIter __first,
3448                      _BidirectionalIter __middle,
3449                      _BidirectionalIter __last,
3450                      _Distance __len1, _Distance __len2,
3451                      _Pointer __buffer, _Distance __buffer_size,
3452                      _Compare __comp)
3453     {
3454           if (__len1 <= __len2 && __len1 <= __buffer_size) {
3455             _Pointer __buffer_end = copy(__first, __middle, __buffer);
3456             merge(__buffer, __buffer_end, __middle, __last, __first, __comp);
3457           }
3458           else if (__len2 <= __buffer_size) {
3459             _Pointer __buffer_end = copy(__middle, __last, __buffer);
3460             __merge_backward(__first, __middle, __buffer, __buffer_end, __last,
3461                                              __comp);
3462           }
3463           else {
3464             _BidirectionalIter __first_cut = __first;
3465             _BidirectionalIter __second_cut = __middle;
3466             _Distance __len11 = 0;
3467             _Distance __len22 = 0;
3468             if (__len1 > __len2) {
3469                   __len11 = __len1 / 2;
3470                   advance(__first_cut, __len11);
3471                   __second_cut = lower_bound(__middle, __last, *__first_cut, __comp);
3472                   __len22 = std::distance(__middle, __second_cut);
3473             }
3474             else {
3475                   __len22 = __len2 / 2;
3476                   advance(__second_cut, __len22);
3477                   __first_cut = upper_bound(__first, __middle, *__second_cut, __comp);
3478                   __len11 = std::distance(__first, __first_cut);
3479             }
3480             _BidirectionalIter __new_middle =
3481                   __rotate_adaptive(__first_cut, __middle, __second_cut,
3482                                     __len1 - __len11, __len22, __buffer,
3483                                     __buffer_size);
3484             __merge_adaptive(__first, __first_cut, __new_middle, __len11,
3485                              __len22, __buffer, __buffer_size, __comp);
3486             __merge_adaptive(__new_middle, __second_cut, __last, __len1 - __len11,
3487                              __len2 - __len22, __buffer, __buffer_size, __comp);
3488           }
3489     }
3490
3491   /**
3492    *  @brief Merges two sorted ranges in place.
3493    *  @param  first   An iterator.
3494    *  @param  middle  Another iterator.
3495    *  @param  last    Another iterator.
3496    *  @return  Nothing.
3497    *
3498    *  Merges two sorted and consecutive ranges, [first,middle) and
3499    *  [middle,last), and puts the result in [first,last).  The output will
3500    *  be sorted.  The sort is @e stable, that is, for equivalent
3501    *  elements in the two ranges, elements from the first range will always
3502    *  come before elements from the second.
3503    *
3504    *  If enough additional memory is available, this takes (last-first)-1
3505    *  comparisons.  Otherwise an NlogN algorithm is used, where N is
3506    *  distance(first,last).
3507   */
3508   template<typename _BidirectionalIter>
3509     void
3510     inplace_merge(_BidirectionalIter __first,
3511                   _BidirectionalIter __middle,
3512                   _BidirectionalIter __last)
3513     {
3514       typedef typename iterator_traits<_BidirectionalIter>::value_type
3515           _ValueType;
3516       typedef typename iterator_traits<_BidirectionalIter>::difference_type
3517           _DistanceType;
3518
3519       // concept requirements
3520       __glibcpp_function_requires(_Mutable_BidirectionalIteratorConcept<
3521             _BidirectionalIter>)
3522       __glibcpp_function_requires(_LessThanComparableConcept<_ValueType>)
3523
3524       if (__first == __middle || __middle == __last)
3525         return;
3526
3527       _DistanceType __len1 = std::distance(__first, __middle);
3528       _DistanceType __len2 = std::distance(__middle, __last);
3529
3530       _Temporary_buffer<_BidirectionalIter, _ValueType> __buf(__first, __last);
3531       if (__buf.begin() == 0)
3532         __merge_without_buffer(__first, __middle, __last, __len1, __len2);
3533       else
3534         __merge_adaptive(__first, __middle, __last, __len1, __len2,
3535                          __buf.begin(), _DistanceType(__buf.size()));
3536     }
3537
3538   /**
3539    *  @brief Merges two sorted ranges in place.
3540    *  @param  first   An iterator.
3541    *  @param  middle  Another iterator.
3542    *  @param  last    Another iterator.
3543    *  @param  comp    A functor to use for comparisons.
3544    *  @return  Nothing.
3545    *
3546    *  Merges two sorted and consecutive ranges, [first,middle) and
3547    *  [middle,last), and puts the result in [first,last).  The output will
3548    *  be sorted.  The sort is @e stable, that is, for equivalent
3549    *  elements in the two ranges, elements from the first range will always
3550    *  come before elements from the second.
3551    *
3552    *  If enough additional memory is available, this takes (last-first)-1
3553    *  comparisons.  Otherwise an NlogN algorithm is used, where N is
3554    *  distance(first,last).
3555    *
3556    *  The comparison function should have the same effects on ordering as
3557    *  the function used for the initial sort.
3558   */
3559   template<typename _BidirectionalIter, typename _Compare>
3560     void
3561     inplace_merge(_BidirectionalIter __first,
3562                   _BidirectionalIter __middle,
3563                   _BidirectionalIter __last,
3564                   _Compare __comp)
3565     {
3566       typedef typename iterator_traits<_BidirectionalIter>::value_type
3567           _ValueType;
3568       typedef typename iterator_traits<_BidirectionalIter>::difference_type
3569           _DistanceType;
3570
3571       // concept requirements
3572       __glibcpp_function_requires(_Mutable_BidirectionalIteratorConcept<
3573             _BidirectionalIter>)
3574       __glibcpp_function_requires(_BinaryPredicateConcept<_Compare,
3575             _ValueType, _ValueType>)
3576
3577       if (__first == __middle || __middle == __last)
3578         return;
3579
3580       _DistanceType __len1 = std::distance(__first, __middle);
3581       _DistanceType __len2 = std::distance(__middle, __last);
3582
3583       _Temporary_buffer<_BidirectionalIter, _ValueType> __buf(__first, __last);
3584       if (__buf.begin() == 0)
3585         __merge_without_buffer(__first, __middle, __last, __len1, __len2, __comp);
3586       else
3587         __merge_adaptive(__first, __middle, __last, __len1, __len2,
3588                          __buf.begin(), _DistanceType(__buf.size()),
3589                          __comp);
3590     }
3591
3592   // Set algorithms: includes, set_union, set_intersection, set_difference,
3593   // set_symmetric_difference.  All of these algorithms have the precondition
3594   // that their input ranges are sorted and the postcondition that their output
3595   // ranges are sorted.
3596
3597   template<typename _InputIter1, typename _InputIter2>
3598     bool
3599     includes(_InputIter1 __first1, _InputIter1 __last1,
3600              _InputIter2 __first2, _InputIter2 __last2)
3601     {
3602       // concept requirements
3603       __glibcpp_function_requires(_InputIteratorConcept<_InputIter1>)
3604       __glibcpp_function_requires(_InputIteratorConcept<_InputIter2>)
3605       __glibcpp_function_requires(_SameTypeConcept<
3606             typename iterator_traits<_InputIter1>::value_type,
3607             typename iterator_traits<_InputIter2>::value_type>)
3608       __glibcpp_function_requires(_LessThanComparableConcept<
3609             typename iterator_traits<_InputIter1>::value_type>)
3610
3611       while (__first1 != __last1 && __first2 != __last2)
3612         if (*__first2 < *__first1)
3613           return false;
3614         else if(*__first1 < *__first2)
3615           ++__first1;
3616         else
3617           ++__first1, ++__first2;
3618
3619       return __first2 == __last2;
3620     }
3621
3622   template<typename _InputIter1, typename _InputIter2, typename _Compare>
3623     bool
3624     includes(_InputIter1 __first1, _InputIter1 __last1,
3625              _InputIter2 __first2, _InputIter2 __last2, _Compare __comp)
3626     {
3627       // concept requirements
3628       __glibcpp_function_requires(_InputIteratorConcept<_InputIter1>)
3629       __glibcpp_function_requires(_InputIteratorConcept<_InputIter2>)
3630       __glibcpp_function_requires(_SameTypeConcept<
3631             typename iterator_traits<_InputIter1>::value_type,
3632             typename iterator_traits<_InputIter2>::value_type>)
3633       __glibcpp_function_requires(_BinaryPredicateConcept<_Compare,
3634             typename iterator_traits<_InputIter1>::value_type,
3635             typename iterator_traits<_InputIter2>::value_type>)
3636
3637       while (__first1 != __last1 && __first2 != __last2)
3638         if (__comp(*__first2, *__first1))
3639           return false;
3640         else if(__comp(*__first1, *__first2))
3641           ++__first1;
3642         else
3643           ++__first1, ++__first2;
3644
3645       return __first2 == __last2;
3646     }
3647
3648   template<typename _InputIter1, typename _InputIter2, typename _OutputIter>
3649     _OutputIter
3650     set_union(_InputIter1 __first1, _InputIter1 __last1,
3651               _InputIter2 __first2, _InputIter2 __last2,
3652               _OutputIter __result)
3653     {
3654       // concept requirements
3655       __glibcpp_function_requires(_InputIteratorConcept<_InputIter1>)
3656       __glibcpp_function_requires(_InputIteratorConcept<_InputIter2>)
3657       __glibcpp_function_requires(_OutputIteratorConcept<_OutputIter,
3658             typename iterator_traits<_InputIter1>::value_type>)
3659       __glibcpp_function_requires(_SameTypeConcept<
3660             typename iterator_traits<_InputIter1>::value_type,
3661             typename iterator_traits<_InputIter2>::value_type>)
3662       __glibcpp_function_requires(_LessThanComparableConcept<
3663             typename iterator_traits<_InputIter1>::value_type>)
3664
3665       while (__first1 != __last1 && __first2 != __last2) {
3666         if (*__first1 < *__first2) {
3667           *__result = *__first1;
3668           ++__first1;
3669         }
3670         else if (*__first2 < *__first1) {
3671           *__result = *__first2;
3672           ++__first2;
3673         }
3674         else {
3675           *__result = *__first1;
3676           ++__first1;
3677           ++__first2;
3678         }
3679         ++__result;
3680       }
3681       return copy(__first2, __last2, copy(__first1, __last1, __result));
3682     }
3683
3684   template<typename _InputIter1, typename _InputIter2, typename _OutputIter,
3685            typename _Compare>
3686     _OutputIter
3687     set_union(_InputIter1 __first1, _InputIter1 __last1,
3688               _InputIter2 __first2, _InputIter2 __last2,
3689               _OutputIter __result, _Compare __comp)
3690     {
3691       // concept requirements
3692       __glibcpp_function_requires(_InputIteratorConcept<_InputIter1>)
3693       __glibcpp_function_requires(_InputIteratorConcept<_InputIter2>)
3694       __glibcpp_function_requires(_SameTypeConcept<
3695             typename iterator_traits<_InputIter1>::value_type,
3696             typename iterator_traits<_InputIter2>::value_type>)
3697       __glibcpp_function_requires(_OutputIteratorConcept<_OutputIter,
3698             typename iterator_traits<_InputIter1>::value_type>)
3699       __glibcpp_function_requires(_BinaryPredicateConcept<_Compare,
3700             typename iterator_traits<_InputIter1>::value_type,
3701             typename iterator_traits<_InputIter2>::value_type>)
3702
3703       while (__first1 != __last1 && __first2 != __last2) {
3704         if (__comp(*__first1, *__first2)) {
3705           *__result = *__first1;
3706           ++__first1;
3707         }
3708         else if (__comp(*__first2, *__first1)) {
3709           *__result = *__first2;
3710           ++__first2;
3711         }
3712         else {
3713           *__result = *__first1;
3714           ++__first1;
3715           ++__first2;
3716         }
3717         ++__result;
3718       }
3719       return copy(__first2, __last2, copy(__first1, __last1, __result));
3720     }
3721
3722   template<typename _InputIter1, typename _InputIter2, typename _OutputIter>
3723     _OutputIter
3724     set_intersection(_InputIter1 __first1, _InputIter1 __last1,
3725                      _InputIter2 __first2, _InputIter2 __last2,
3726                      _OutputIter __result)
3727     {
3728       // concept requirements
3729       __glibcpp_function_requires(_InputIteratorConcept<_InputIter1>)
3730       __glibcpp_function_requires(_InputIteratorConcept<_InputIter2>)
3731       __glibcpp_function_requires(_OutputIteratorConcept<_OutputIter,
3732             typename iterator_traits<_InputIter1>::value_type>)
3733       __glibcpp_function_requires(_SameTypeConcept<
3734             typename iterator_traits<_InputIter1>::value_type,
3735             typename iterator_traits<_InputIter2>::value_type>)
3736       __glibcpp_function_requires(_LessThanComparableConcept<
3737             typename iterator_traits<_InputIter1>::value_type>)
3738
3739       while (__first1 != __last1 && __first2 != __last2)
3740         if (*__first1 < *__first2)
3741           ++__first1;
3742         else if (*__first2 < *__first1)
3743           ++__first2;
3744         else {
3745           *__result = *__first1;
3746           ++__first1;
3747           ++__first2;
3748           ++__result;
3749         }
3750       return __result;
3751     }
3752
3753   template<typename _InputIter1, typename _InputIter2, typename _OutputIter,
3754            typename _Compare>
3755     _OutputIter
3756     set_intersection(_InputIter1 __first1, _InputIter1 __last1,
3757                      _InputIter2 __first2, _InputIter2 __last2,
3758                      _OutputIter __result, _Compare __comp)
3759     {
3760       // concept requirements
3761       __glibcpp_function_requires(_InputIteratorConcept<_InputIter1>)
3762       __glibcpp_function_requires(_InputIteratorConcept<_InputIter2>)
3763       __glibcpp_function_requires(_SameTypeConcept<
3764             typename iterator_traits<_InputIter1>::value_type,
3765             typename iterator_traits<_InputIter2>::value_type>)
3766       __glibcpp_function_requires(_OutputIteratorConcept<_OutputIter,
3767             typename iterator_traits<_InputIter1>::value_type>)
3768       __glibcpp_function_requires(_BinaryPredicateConcept<_Compare,
3769             typename iterator_traits<_InputIter1>::value_type,
3770             typename iterator_traits<_InputIter2>::value_type>)
3771
3772       while (__first1 != __last1 && __first2 != __last2)
3773         if (__comp(*__first1, *__first2))
3774           ++__first1;
3775         else if (__comp(*__first2, *__first1))
3776           ++__first2;
3777         else {
3778           *__result = *__first1;
3779           ++__first1;
3780           ++__first2;
3781           ++__result;
3782         }
3783       return __result;
3784     }
3785
3786   template<typename _InputIter1, typename _InputIter2, typename _OutputIter>
3787     _OutputIter
3788     set_difference(_InputIter1 __first1, _InputIter1 __last1,
3789                    _InputIter2 __first2, _InputIter2 __last2,
3790                    _OutputIter __result)
3791     {
3792       // concept requirements
3793       __glibcpp_function_requires(_InputIteratorConcept<_InputIter1>)
3794       __glibcpp_function_requires(_InputIteratorConcept<_InputIter2>)
3795       __glibcpp_function_requires(_OutputIteratorConcept<_OutputIter,
3796             typename iterator_traits<_InputIter1>::value_type>)
3797       __glibcpp_function_requires(_SameTypeConcept<
3798             typename iterator_traits<_InputIter1>::value_type,
3799             typename iterator_traits<_InputIter2>::value_type>)
3800       __glibcpp_function_requires(_LessThanComparableConcept<
3801             typename iterator_traits<_InputIter1>::value_type>)
3802
3803       while (__first1 != __last1 && __first2 != __last2)
3804         if (*__first1 < *__first2) {
3805           *__result = *__first1;
3806           ++__first1;
3807           ++__result;
3808         }
3809         else if (*__first2 < *__first1)
3810           ++__first2;
3811         else {
3812           ++__first1;
3813           ++__first2;
3814         }
3815       return copy(__first1, __last1, __result);
3816     }
3817
3818   template<typename _InputIter1, typename _InputIter2, typename _OutputIter,
3819            typename _Compare>
3820     _OutputIter
3821     set_difference(_InputIter1 __first1, _InputIter1 __last1,
3822                    _InputIter2 __first2, _InputIter2 __last2,
3823                    _OutputIter __result, _Compare __comp)
3824     {
3825       // concept requirements
3826       __glibcpp_function_requires(_InputIteratorConcept<_InputIter1>)
3827       __glibcpp_function_requires(_InputIteratorConcept<_InputIter2>)
3828       __glibcpp_function_requires(_SameTypeConcept<
3829             typename iterator_traits<_InputIter1>::value_type,
3830             typename iterator_traits<_InputIter2>::value_type>)
3831       __glibcpp_function_requires(_OutputIteratorConcept<_OutputIter,
3832             typename iterator_traits<_InputIter1>::value_type>)
3833       __glibcpp_function_requires(_BinaryPredicateConcept<_Compare,
3834             typename iterator_traits<_InputIter1>::value_type,
3835             typename iterator_traits<_InputIter2>::value_type>)
3836
3837       while (__first1 != __last1 && __first2 != __last2)
3838         if (__comp(*__first1, *__first2)) {
3839           *__result = *__first1;
3840           ++__first1;
3841           ++__result;
3842         }
3843         else if (__comp(*__first2, *__first1))
3844           ++__first2;
3845         else {
3846           ++__first1;
3847           ++__first2;
3848         }
3849       return copy(__first1, __last1, __result);
3850     }
3851
3852   template<typename _InputIter1, typename _InputIter2, typename _OutputIter>
3853     _OutputIter
3854     set_symmetric_difference(_InputIter1 __first1, _InputIter1 __last1,
3855                              _InputIter2 __first2, _InputIter2 __last2,
3856                              _OutputIter __result)
3857     {
3858       // concept requirements
3859       __glibcpp_function_requires(_InputIteratorConcept<_InputIter1>)
3860       __glibcpp_function_requires(_InputIteratorConcept<_InputIter2>)
3861       __glibcpp_function_requires(_OutputIteratorConcept<_OutputIter,
3862             typename iterator_traits<_InputIter1>::value_type>)
3863       __glibcpp_function_requires(_SameTypeConcept<
3864             typename iterator_traits<_InputIter1>::value_type,
3865             typename iterator_traits<_InputIter2>::value_type>)
3866       __glibcpp_function_requires(_LessThanComparableConcept<
3867             typename iterator_traits<_InputIter1>::value_type>)
3868
3869       while (__first1 != __last1 && __first2 != __last2)
3870         if (*__first1 < *__first2) {
3871           *__result = *__first1;
3872           ++__first1;
3873           ++__result;
3874         }
3875         else if (*__first2 < *__first1) {
3876           *__result = *__first2;
3877           ++__first2;
3878           ++__result;
3879         }
3880         else {
3881           ++__first1;
3882           ++__first2;
3883         }
3884       return copy(__first2, __last2, copy(__first1, __last1, __result));
3885     }
3886
3887   template<typename _InputIter1, typename _InputIter2, typename _OutputIter,
3888            typename _Compare>
3889     _OutputIter
3890     set_symmetric_difference(_InputIter1 __first1, _InputIter1 __last1,
3891                              _InputIter2 __first2, _InputIter2 __last2,
3892                              _OutputIter __result,
3893                              _Compare __comp)
3894     {
3895       // concept requirements
3896       __glibcpp_function_requires(_InputIteratorConcept<_InputIter1>)
3897       __glibcpp_function_requires(_InputIteratorConcept<_InputIter2>)
3898       __glibcpp_function_requires(_SameTypeConcept<
3899             typename iterator_traits<_InputIter1>::value_type,
3900             typename iterator_traits<_InputIter2>::value_type>)
3901       __glibcpp_function_requires(_OutputIteratorConcept<_OutputIter,
3902             typename iterator_traits<_InputIter1>::value_type>)
3903       __glibcpp_function_requires(_BinaryPredicateConcept<_Compare,
3904             typename iterator_traits<_InputIter1>::value_type,
3905             typename iterator_traits<_InputIter2>::value_type>)
3906
3907       while (__first1 != __last1 && __first2 != __last2)
3908         if (__comp(*__first1, *__first2)) {
3909           *__result = *__first1;
3910           ++__first1;
3911           ++__result;
3912         }
3913         else if (__comp(*__first2, *__first1)) {
3914           *__result = *__first2;
3915           ++__first2;
3916           ++__result;
3917         }
3918         else {
3919           ++__first1;
3920           ++__first2;
3921         }
3922       return copy(__first2, __last2, copy(__first1, __last1, __result));
3923     }
3924
3925   // min_element and max_element, with and without an explicitly supplied
3926   // comparison function.
3927
3928   template<typename _ForwardIter>
3929     _ForwardIter
3930     max_element(_ForwardIter __first, _ForwardIter __last)
3931     {
3932       // concept requirements
3933       __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter>)
3934       __glibcpp_function_requires(_LessThanComparableConcept<
3935             typename iterator_traits<_ForwardIter>::value_type>)
3936
3937       if (__first == __last) return __first;
3938       _ForwardIter __result = __first;
3939       while (++__first != __last)
3940         if (*__result < *__first)
3941           __result = __first;
3942       return __result;
3943     }
3944
3945   template<typename _ForwardIter, typename _Compare>
3946     _ForwardIter
3947     max_element(_ForwardIter __first, _ForwardIter __last,
3948                 _Compare __comp)
3949     {
3950       // concept requirements
3951       __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter>)
3952       __glibcpp_function_requires(_BinaryPredicateConcept<_Compare,
3953             typename iterator_traits<_ForwardIter>::value_type,
3954             typename iterator_traits<_ForwardIter>::value_type>)
3955
3956       if (__first == __last) return __first;
3957       _ForwardIter __result = __first;
3958       while (++__first != __last)
3959         if (__comp(*__result, *__first)) __result = __first;
3960       return __result;
3961     }
3962
3963   template<typename _ForwardIter>
3964     _ForwardIter
3965     min_element(_ForwardIter __first, _ForwardIter __last)
3966     {
3967       // concept requirements
3968       __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter>)
3969       __glibcpp_function_requires(_LessThanComparableConcept<
3970             typename iterator_traits<_ForwardIter>::value_type>)
3971
3972       if (__first == __last) return __first;
3973       _ForwardIter __result = __first;
3974       while (++__first != __last)
3975         if (*__first < *__result)
3976           __result = __first;
3977       return __result;
3978     }
3979
3980   template<typename _ForwardIter, typename _Compare>
3981     _ForwardIter
3982     min_element(_ForwardIter __first, _ForwardIter __last,
3983                 _Compare __comp)
3984     {
3985       // concept requirements
3986       __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter>)
3987       __glibcpp_function_requires(_BinaryPredicateConcept<_Compare,
3988             typename iterator_traits<_ForwardIter>::value_type,
3989             typename iterator_traits<_ForwardIter>::value_type>)
3990
3991       if (__first == __last) return __first;
3992       _ForwardIter __result = __first;
3993       while (++__first != __last)
3994         if (__comp(*__first, *__result))
3995           __result = __first;
3996       return __result;
3997     }
3998
3999   // next_permutation and prev_permutation, with and without an explicitly
4000   // supplied comparison function.
4001
4002   template<typename _BidirectionalIter>
4003     bool
4004     next_permutation(_BidirectionalIter __first, _BidirectionalIter __last)
4005     {
4006       // concept requirements
4007       __glibcpp_function_requires(_BidirectionalIteratorConcept<_BidirectionalIter>)
4008       __glibcpp_function_requires(_LessThanComparableConcept<
4009             typename iterator_traits<_BidirectionalIter>::value_type>)
4010
4011       if (__first == __last)
4012         return false;
4013       _BidirectionalIter __i = __first;
4014       ++__i;
4015       if (__i == __last)
4016         return false;
4017       __i = __last;
4018       --__i;
4019
4020       for(;;) {
4021         _BidirectionalIter __ii = __i;
4022         --__i;
4023         if (*__i < *__ii) {
4024           _BidirectionalIter __j = __last;
4025           while (!(*__i < *--__j))
4026             {}
4027           iter_swap(__i, __j);
4028           reverse(__ii, __last);
4029           return true;
4030         }
4031         if (__i == __first) {
4032           reverse(__first, __last);
4033           return false;
4034         }
4035       }
4036     }
4037
4038   template<typename _BidirectionalIter, typename _Compare>
4039     bool
4040     next_permutation(_BidirectionalIter __first, _BidirectionalIter __last,
4041                      _Compare __comp)
4042     {
4043       // concept requirements
4044       __glibcpp_function_requires(_BidirectionalIteratorConcept<_BidirectionalIter>)
4045       __glibcpp_function_requires(_BinaryPredicateConcept<_Compare,
4046             typename iterator_traits<_BidirectionalIter>::value_type,
4047             typename iterator_traits<_BidirectionalIter>::value_type>)
4048
4049       if (__first == __last)
4050         return false;
4051       _BidirectionalIter __i = __first;
4052       ++__i;
4053       if (__i == __last)
4054         return false;
4055       __i = __last;
4056       --__i;
4057
4058       for(;;) {
4059         _BidirectionalIter __ii = __i;
4060         --__i;
4061         if (__comp(*__i, *__ii)) {
4062           _BidirectionalIter __j = __last;
4063           while (!__comp(*__i, *--__j))
4064             {}
4065           iter_swap(__i, __j);
4066           reverse(__ii, __last);
4067           return true;
4068         }
4069         if (__i == __first) {
4070           reverse(__first, __last);
4071           return false;
4072         }
4073       }
4074     }
4075
4076   template<typename _BidirectionalIter>
4077     bool
4078     prev_permutation(_BidirectionalIter __first, _BidirectionalIter __last)
4079     {
4080       // concept requirements
4081       __glibcpp_function_requires(_BidirectionalIteratorConcept<_BidirectionalIter>)
4082       __glibcpp_function_requires(_LessThanComparableConcept<
4083             typename iterator_traits<_BidirectionalIter>::value_type>)
4084
4085       if (__first == __last)
4086         return false;
4087       _BidirectionalIter __i = __first;
4088       ++__i;
4089       if (__i == __last)
4090         return false;
4091       __i = __last;
4092       --__i;
4093
4094       for(;;) {
4095         _BidirectionalIter __ii = __i;
4096         --__i;
4097         if (*__ii < *__i) {
4098           _BidirectionalIter __j = __last;
4099           while (!(*--__j < *__i))
4100             {}
4101           iter_swap(__i, __j);
4102           reverse(__ii, __last);
4103           return true;
4104         }
4105         if (__i == __first) {
4106           reverse(__first, __last);
4107           return false;
4108         }
4109       }
4110     }
4111
4112   template<typename _BidirectionalIter, typename _Compare>
4113     bool
4114     prev_permutation(_BidirectionalIter __first, _BidirectionalIter __last,
4115                      _Compare __comp)
4116     {
4117       // concept requirements
4118       __glibcpp_function_requires(_BidirectionalIteratorConcept<_BidirectionalIter>)
4119       __glibcpp_function_requires(_BinaryPredicateConcept<_Compare,
4120             typename iterator_traits<_BidirectionalIter>::value_type,
4121             typename iterator_traits<_BidirectionalIter>::value_type>)
4122
4123       if (__first == __last)
4124         return false;
4125       _BidirectionalIter __i = __first;
4126       ++__i;
4127       if (__i == __last)
4128         return false;
4129       __i = __last;
4130       --__i;
4131
4132       for(;;) {
4133         _BidirectionalIter __ii = __i;
4134         --__i;
4135         if (__comp(*__ii, *__i)) {
4136           _BidirectionalIter __j = __last;
4137           while (!__comp(*--__j, *__i))
4138             {}
4139           iter_swap(__i, __j);
4140           reverse(__ii, __last);
4141           return true;
4142         }
4143         if (__i == __first) {
4144           reverse(__first, __last);
4145           return false;
4146         }
4147       }
4148     }
4149
4150   // find_first_of, with and without an explicitly supplied comparison function.
4151
4152   template<typename _InputIter, typename _ForwardIter>
4153     _InputIter
4154     find_first_of(_InputIter __first1, _InputIter __last1,
4155                   _ForwardIter __first2, _ForwardIter __last2)
4156     {
4157       // concept requirements
4158       __glibcpp_function_requires(_InputIteratorConcept<_InputIter>)
4159       __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter>)
4160       __glibcpp_function_requires(_EqualOpConcept<
4161             typename iterator_traits<_InputIter>::value_type,
4162             typename iterator_traits<_ForwardIter>::value_type>)
4163
4164       for ( ; __first1 != __last1; ++__first1)
4165         for (_ForwardIter __iter = __first2; __iter != __last2; ++__iter)
4166           if (*__first1 == *__iter)
4167             return __first1;
4168       return __last1;
4169     }
4170
4171   template<typename _InputIter, typename _ForwardIter, typename _BinaryPredicate>
4172     _InputIter
4173     find_first_of(_InputIter __first1, _InputIter __last1,
4174                   _ForwardIter __first2, _ForwardIter __last2,
4175                   _BinaryPredicate __comp)
4176     {
4177       // concept requirements
4178       __glibcpp_function_requires(_InputIteratorConcept<_InputIter>)
4179       __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter>)
4180       __glibcpp_function_requires(_EqualOpConcept<
4181             typename iterator_traits<_InputIter>::value_type,
4182             typename iterator_traits<_ForwardIter>::value_type>)
4183       __glibcpp_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
4184             typename iterator_traits<_InputIter>::value_type,
4185             typename iterator_traits<_ForwardIter>::value_type>)
4186
4187       for ( ; __first1 != __last1; ++__first1)
4188         for (_ForwardIter __iter = __first2; __iter != __last2; ++__iter)
4189           if (__comp(*__first1, *__iter))
4190             return __first1;
4191       return __last1;
4192     }
4193
4194
4195   // find_end, with and without an explicitly supplied comparison function.
4196   // Search [first2, last2) as a subsequence in [first1, last1), and return
4197   // the *last* possible match.  Note that find_end for bidirectional iterators
4198   // is much faster than for forward iterators.
4199
4200   // find_end for forward iterators.
4201   template<typename _ForwardIter1, typename _ForwardIter2>
4202     _ForwardIter1
4203     __find_end(_ForwardIter1 __first1, _ForwardIter1 __last1,
4204                _ForwardIter2 __first2, _ForwardIter2 __last2,
4205                forward_iterator_tag, forward_iterator_tag)
4206     {
4207       if (__first2 == __last2)
4208         return __last1;
4209       else {
4210         _ForwardIter1 __result = __last1;
4211         while (1) {
4212           _ForwardIter1 __new_result
4213             = search(__first1, __last1, __first2, __last2);
4214           if (__new_result == __last1)
4215             return __result;
4216           else {
4217             __result = __new_result;
4218             __first1 = __new_result;
4219             ++__first1;
4220           }
4221         }
4222       }
4223     }
4224
4225   template<typename _ForwardIter1, typename _ForwardIter2,
4226            typename _BinaryPredicate>
4227     _ForwardIter1
4228     __find_end(_ForwardIter1 __first1, _ForwardIter1 __last1,
4229                _ForwardIter2 __first2, _ForwardIter2 __last2,
4230                forward_iterator_tag, forward_iterator_tag,
4231                _BinaryPredicate __comp)
4232     {
4233       if (__first2 == __last2)
4234         return __last1;
4235       else {
4236         _ForwardIter1 __result = __last1;
4237         while (1) {
4238           _ForwardIter1 __new_result
4239             = search(__first1, __last1, __first2, __last2, __comp);
4240           if (__new_result == __last1)
4241             return __result;
4242           else {
4243             __result = __new_result;
4244             __first1 = __new_result;
4245             ++__first1;
4246           }
4247         }
4248       }
4249     }
4250
4251   // find_end for bidirectional iterators.  Requires partial specialization.
4252   template<typename _BidirectionalIter1, typename _BidirectionalIter2>
4253     _BidirectionalIter1
4254     __find_end(_BidirectionalIter1 __first1, _BidirectionalIter1 __last1,
4255                _BidirectionalIter2 __first2, _BidirectionalIter2 __last2,
4256                bidirectional_iterator_tag, bidirectional_iterator_tag)
4257     {
4258       // concept requirements
4259       __glibcpp_function_requires(_BidirectionalIteratorConcept<_BidirectionalIter1>)
4260       __glibcpp_function_requires(_BidirectionalIteratorConcept<_BidirectionalIter2>)
4261
4262       typedef reverse_iterator<_BidirectionalIter1> _RevIter1;
4263       typedef reverse_iterator<_BidirectionalIter2> _RevIter2;
4264
4265       _RevIter1 __rlast1(__first1);
4266       _RevIter2 __rlast2(__first2);
4267       _RevIter1 __rresult = search(_RevIter1(__last1), __rlast1,
4268                                    _RevIter2(__last2), __rlast2);
4269
4270       if (__rresult == __rlast1)
4271         return __last1;
4272       else {
4273         _BidirectionalIter1 __result = __rresult.base();
4274         advance(__result, -std::distance(__first2, __last2));
4275         return __result;
4276       }
4277     }
4278
4279   template<typename _BidirectionalIter1, typename _BidirectionalIter2,
4280            typename _BinaryPredicate>
4281     _BidirectionalIter1
4282     __find_end(_BidirectionalIter1 __first1, _BidirectionalIter1 __last1,
4283                _BidirectionalIter2 __first2, _BidirectionalIter2 __last2,
4284                bidirectional_iterator_tag, bidirectional_iterator_tag,
4285                _BinaryPredicate __comp)
4286     {
4287       // concept requirements
4288       __glibcpp_function_requires(_BidirectionalIteratorConcept<_BidirectionalIter1>)
4289       __glibcpp_function_requires(_BidirectionalIteratorConcept<_BidirectionalIter2>)
4290
4291       typedef reverse_iterator<_BidirectionalIter1> _RevIter1;
4292       typedef reverse_iterator<_BidirectionalIter2> _RevIter2;
4293
4294       _RevIter1 __rlast1(__first1);
4295       _RevIter2 __rlast2(__first2);
4296       _RevIter1 __rresult = search(_RevIter1(__last1), __rlast1,
4297                                    _RevIter2(__last2), __rlast2,
4298                                    __comp);
4299
4300       if (__rresult == __rlast1)
4301         return __last1;
4302       else {
4303         _BidirectionalIter1 __result = __rresult.base();
4304         advance(__result, -std::distance(__first2, __last2));
4305         return __result;
4306       }
4307     }
4308
4309   // Dispatching functions for find_end.
4310
4311   template<typename _ForwardIter1, typename _ForwardIter2>
4312     inline _ForwardIter1
4313     find_end(_ForwardIter1 __first1, _ForwardIter1 __last1,
4314              _ForwardIter2 __first2, _ForwardIter2 __last2)
4315     {
4316       // concept requirements
4317       __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter1>)
4318       __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter2>)
4319       __glibcpp_function_requires(_EqualOpConcept<
4320             typename iterator_traits<_ForwardIter1>::value_type,
4321             typename iterator_traits<_ForwardIter2>::value_type>)
4322
4323       return __find_end(__first1, __last1, __first2, __last2,
4324                         __iterator_category(__first1),
4325                         __iterator_category(__first2));
4326     }
4327
4328   template<typename _ForwardIter1, typename _ForwardIter2,
4329            typename _BinaryPredicate>
4330     inline _ForwardIter1
4331     find_end(_ForwardIter1 __first1, _ForwardIter1 __last1,
4332              _ForwardIter2 __first2, _ForwardIter2 __last2,
4333              _BinaryPredicate __comp)
4334     {
4335       // concept requirements
4336       __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter1>)
4337       __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter2>)
4338       __glibcpp_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
4339             typename iterator_traits<_ForwardIter1>::value_type,
4340             typename iterator_traits<_ForwardIter2>::value_type>)
4341
4342       return __find_end(__first1, __last1, __first2, __last2,
4343                         __iterator_category(__first1),
4344                         __iterator_category(__first2),
4345                         __comp);
4346     }
4347
4348 } // namespace std
4349
4350 #endif /* __GLIBCPP_INTERNAL_ALGO_H */
4351