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

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