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