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 _ALGO_H
  62 #define _ALGO_H 1
  63
  64 #include <bits/stl_heap.h>
  65 #include <bits/stl_tempbuf.h>     // for _Temporary_buffer
  66
  67 // See concept_check.h for the __glibcxx_*_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       __glibcxx_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       __glibcxx_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       __glibcxx_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       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
 296       __glibcxx_function_requires(_EqualOpConcept<
 297                 typename iterator_traits<_InputIterator>::value_type, _Tp>)
 298       return std::find(__first, __last, __val, std::__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       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
 316       __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
 317               typename iterator_traits<_InputIterator>::value_type>)
 318       return std::find_if(__first, __last, __pred, std::__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       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
 335       __glibcxx_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       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
 365       __glibcxx_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       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
 393       __glibcxx_function_requires(_EqualityComparableConcept<
 394             typename iterator_traits<_InputIterator>::value_type >)
 395       __glibcxx_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       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
 417       __glibcxx_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       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator1>)
 457       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator2>)
 458       __glibcxx_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 std::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 = std::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       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator1>)
 530       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator2>)
 531       __glibcxx_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       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
 603       __glibcxx_function_requires(_EqualityComparableConcept<
 604             typename iterator_traits<_ForwardIterator>::value_type>)
 605       __glibcxx_function_requires(_EqualityComparableConcept<_Tp>)
 606
 607       if (__count <= 0)
 608         return __first;
 609       else {
 610         __first = std::find(__first, __last, __val);
 611         while (__first != __last) {
 612           typename iterator_traits<_ForwardIterator>::difference_type __n = __count;
 613           _ForwardIterator __i = __first;
 614           ++__i;
 615           while (__i != __last && __n != 1 && *__i == __val) {
 616             ++__i;
 617             --__n;
 618           }
 619           if (__n == 1)
 620             return __first;
 621           else
 622             __first = std::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       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
 652       __glibcxx_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           typename iterator_traits<_ForwardIterator>::difference_type __n = __count;
 665           _ForwardIterator __i = __first;
 666           ++__i;
 667           while (__i != __last && __n != 1 && __binary_pred(*__i, __val)) {
 668             ++__i;
 669             --__n;
 670           }
 671           if (__n == 1)
 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       __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<_ForwardIterator1>)
 704       __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<_ForwardIterator2>)
 705       __glibcxx_function_requires(_ConvertibleConcept<
 706             typename iterator_traits<_ForwardIterator1>::value_type,
 707             typename iterator_traits<_ForwardIterator2>::value_type>)
 708       __glibcxx_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         std::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       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
 739       __glibcxx_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       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
 774       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
 775       __glibcxx_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       __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<_ForwardIterator>)
 803       __glibcxx_function_requires(_EqualOpConcept<
 804             typename iterator_traits<_ForwardIterator>::value_type, _Tp>)
 805       __glibcxx_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       __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<_ForwardIterator>)
 832       __glibcxx_function_requires(_ConvertibleConcept<_Tp,
 833             typename iterator_traits<_ForwardIterator>::value_type>)
 834       __glibcxx_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       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
 864       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
 865             typename iterator_traits<_InputIterator>::value_type>)
 866       __glibcxx_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       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
 897       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
 898             typename iterator_traits<_InputIterator>::value_type>)
 899       __glibcxx_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       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
 924       __glibcxx_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       __glibcxx_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       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
 976       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
 977             typename iterator_traits<_InputIterator>::value_type>)
 978       __glibcxx_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       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
1010       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
1011             typename iterator_traits<_InputIterator>::value_type>)
1012       __glibcxx_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       __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<_ForwardIterator>)
1046       __glibcxx_function_requires(_ConvertibleConcept<_Tp,
1047             typename iterator_traits<_ForwardIterator>::value_type>)
1048       __glibcxx_function_requires(_EqualOpConcept<
1049             typename iterator_traits<_ForwardIterator>::value_type, _Tp>)
1050
1051       __first = std::find(__first, __last, __value);
1052       _ForwardIterator __i = __first;
1053       return __first == __last ? __first
1054                                : std::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       __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<_ForwardIterator>)
1080       __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
1081             typename iterator_traits<_ForwardIterator>::value_type>)
1082
1083       __first = std::find_if(__first, __last, __pred);
1084       _ForwardIterator __i = __first;
1085       return __first == __last ? __first
1086                                : std::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    *  @if maint
1134    *  This is an uglified
1135    *  unique_copy(_InputIterator, _InputIterator, _OutputIterator, _BinaryPredicate)
1136    *  overloaded for output iterators.
1137    *  @endif
1138   */
1139   template<typename _InputIterator, typename _OutputIterator, typename _BinaryPredicate>
1140     _OutputIterator
1141     __unique_copy(_InputIterator __first, _InputIterator __last,
1142                   _OutputIterator __result,
1143                   _BinaryPredicate __binary_pred,
1144                   output_iterator_tag)
1145     {
1146       // concept requirements -- iterators already checked
1147       __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
1148           typename iterator_traits<_InputIterator>::value_type,
1149           typename iterator_traits<_InputIterator>::value_type>)
1150
1151       typename iterator_traits<_InputIterator>::value_type __value = *__first;
1152       *__result = __value;
1153       while (++__first != __last)
1154         if (!__binary_pred(__value, *__first)) {
1155           __value = *__first;
1156           *++__result = __value;
1157         }
1158       return ++__result;
1159     }
1160
1161   /**
1162    *  @if maint
1163    *  This is an uglified
1164    *  unique_copy(_InputIterator, _InputIterator, _OutputIterator, _BinaryPredicate)
1165    *  overloaded for forward iterators.
1166    *  @endif
1167   */
1168   template<typename _InputIterator, typename _ForwardIterator, typename _BinaryPredicate>
1169     _ForwardIterator
1170     __unique_copy(_InputIterator __first, _InputIterator __last,
1171                   _ForwardIterator __result,
1172                   _BinaryPredicate __binary_pred,
1173                   forward_iterator_tag)
1174     {
1175       // concept requirements -- iterators already checked
1176       __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
1177             typename iterator_traits<_ForwardIterator>::value_type,
1178             typename iterator_traits<_InputIterator>::value_type>)
1179
1180       *__result = *__first;
1181       while (++__first != __last)
1182         if (!__binary_pred(*__result, *__first)) *++__result = *__first;
1183       return ++__result;
1184     }
1185
1186   /**
1187    *  @brief Copy a sequence, removing consecutive duplicate values.
1188    *  @param  first   An input iterator.
1189    *  @param  last    An input iterator.
1190    *  @param  result  An output iterator.
1191    *  @return   An iterator designating the end of the resulting sequence.
1192    *
1193    *  Copies each element in the range @p [first,last) to the range
1194    *  beginning at @p result, except that only the first element is copied
1195    *  from groups of consecutive elements that compare equal.
1196    *  unique_copy() is stable, so the relative order of elements that are
1197    *  copied is unchanged.
1198   */
1199   template<typename _InputIterator, typename _OutputIterator>
1200     inline _OutputIterator
1201     unique_copy(_InputIterator __first, _InputIterator __last,
1202                 _OutputIterator __result)
1203     {
1204       // concept requirements
1205       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
1206       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
1207             typename iterator_traits<_InputIterator>::value_type>)
1208       __glibcxx_function_requires(_EqualityComparableConcept<
1209             typename iterator_traits<_InputIterator>::value_type>)
1210
1211       typedef typename iterator_traits<_OutputIterator>::iterator_category _IterType;
1212
1213       if (__first == __last) return __result;
1214       return std::__unique_copy(__first, __last, __result, _IterType());
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       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
1240       __glibcxx_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 std::__unique_copy(__first, __last, __result, __binary_pred, _IterType());
1247     }
1248
1249   /**
1250    *  @brief Remove consecutive duplicate values from a sequence.
1251    *  @param  first  A forward iterator.
1252    *  @param  last   A forward iterator.
1253    *  @return  An iterator designating the end of the resulting sequence.
1254    *
1255    *  Removes all but the first element from each group of consecutive
1256    *  values that compare equal.
1257    *  unique() is stable, so the relative order of elements that are
1258    *  not removed is unchanged.
1259    *  Elements between the end of the resulting sequence and @p last
1260    *  are still present, but their value is unspecified.
1261   */
1262   template<typename _ForwardIterator>
1263     _ForwardIterator
1264     unique(_ForwardIterator __first, _ForwardIterator __last)
1265     {
1266           // concept requirements
1267           __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<_ForwardIterator>)
1268           __glibcxx_function_requires(_EqualityComparableConcept<
1269                     typename iterator_traits<_ForwardIterator>::value_type>)
1270
1271           __first = std::adjacent_find(__first, __last);
1272           return std::unique_copy(__first, __last, __first);
1273     }
1274
1275   /**
1276    *  @brief Remove consecutive values from a sequence using a predicate.
1277    *  @param  first        A forward iterator.
1278    *  @param  last         A forward iterator.
1279    *  @param  binary_pred  A binary predicate.
1280    *  @return  An iterator designating the end of the resulting sequence.
1281    *
1282    *  Removes all but the first element from each group of consecutive
1283    *  values for which @p binary_pred returns true.
1284    *  unique() is stable, so the relative order of elements that are
1285    *  not removed is unchanged.
1286    *  Elements between the end of the resulting sequence and @p last
1287    *  are still present, but their value is unspecified.
1288   */
1289   template<typename _ForwardIterator, typename _BinaryPredicate>
1290     _ForwardIterator
1291     unique(_ForwardIterator __first, _ForwardIterator __last,
1292            _BinaryPredicate __binary_pred)
1293     {
1294       // concept requirements
1295       __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<_ForwardIterator>)
1296       __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
1297                 typename iterator_traits<_ForwardIterator>::value_type,
1298                 typename iterator_traits<_ForwardIterator>::value_type>)
1299
1300       __first = std::adjacent_find(__first, __last, __binary_pred);
1301       return std::unique_copy(__first, __last, __first, __binary_pred);
1302     }
1303
1304   /**
1305    *  @if maint
1306    *  This is an uglified reverse(_BidirectionalIterator, _BidirectionalIterator)
1307    *  overloaded for bidirectional iterators.
1308    *  @endif
1309   */
1310   template<typename _BidirectionalIterator>
1311     void
1312     __reverse(_BidirectionalIterator __first, _BidirectionalIterator __last,
1313                           bidirectional_iterator_tag)
1314     {
1315       while (true)
1316         if (__first == __last || __first == --__last)
1317           return;
1318         else
1319           std::iter_swap(__first++, __last);
1320     }
1321
1322   /**
1323    *  @if maint
1324    *  This is an uglified reverse(_BidirectionalIterator, _BidirectionalIterator)
1325    *  overloaded for bidirectional iterators.
1326    *  @endif
1327   */
1328   template<typename _RandomAccessIterator>
1329     void
1330     __reverse(_RandomAccessIterator __first, _RandomAccessIterator __last,
1331                           random_access_iterator_tag)
1332     {
1333       while (__first < __last)
1334         std::iter_swap(__first++, --__last);
1335     }
1336
1337   /**
1338    *  @brief Reverse a sequence.
1339    *  @param  first  A bidirectional iterator.
1340    *  @param  last   A bidirectional iterator.
1341    *  @return   reverse() returns no value.
1342    *
1343    *  Reverses the order of the elements in the range @p [first,last),
1344    *  so that the first element becomes the last etc.
1345    *  For every @c i such that @p 0<=i<=(last-first)/2), @p reverse()
1346    *  swaps @p *(first+i) and @p *(last-(i+1))
1347   */
1348   template<typename _BidirectionalIterator>
1349     inline void
1350     reverse(_BidirectionalIterator __first, _BidirectionalIterator __last)
1351     {
1352           // concept requirements
1353           __glibcxx_function_requires(_Mutable_BidirectionalIteratorConcept<
1354                     _BidirectionalIterator>)
1355           std::__reverse(__first, __last, std::__iterator_category(__first));
1356     }
1357
1358   /**
1359    *  @brief Copy a sequence, reversing its elements.
1360    *  @param  first   A bidirectional iterator.
1361    *  @param  last    A bidirectional iterator.
1362    *  @param  result  An output iterator.
1363    *  @return  An iterator designating the end of the resulting sequence.
1364    *
1365    *  Copies the elements in the range @p [first,last) to the range
1366    *  @p [result,result+(last-first)) such that the order of the
1367    *  elements is reversed.
1368    *  For every @c i such that @p 0<=i<=(last-first), @p reverse_copy()
1369    *  performs the assignment @p *(result+(last-first)-i) = *(first+i).
1370    *  The ranges @p [first,last) and @p [result,result+(last-first))
1371    *  must not overlap.
1372   */
1373   template<typename _BidirectionalIterator, typename _OutputIterator>
1374     _OutputIterator
1375     reverse_copy(_BidirectionalIterator __first, _BidirectionalIterator __last,
1376                              _OutputIterator __result)
1377     {
1378       // concept requirements
1379       __glibcxx_function_requires(_BidirectionalIteratorConcept<_BidirectionalIterator>)
1380       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
1381                 typename iterator_traits<_BidirectionalIterator>::value_type>)
1382
1383       while (__first != __last) {
1384         --__last;
1385         *__result = *__last;
1386         ++__result;
1387       }
1388       return __result;
1389     }
1390
1391
1392   /**
1393    *  @if maint
1394    *  This is a helper function for the rotate algorithm specialized on RAIs.
1395    *  It returns the greatest common divisor of two integer values.
1396    *  @endif
1397   */
1398   template<typename _EuclideanRingElement>
1399     _EuclideanRingElement
1400     __gcd(_EuclideanRingElement __m, _EuclideanRingElement __n)
1401     {
1402       while (__n != 0) {
1403         _EuclideanRingElement __t = __m % __n;
1404         __m = __n;
1405         __n = __t;
1406       }
1407       return __m;
1408     }
1409
1410   /**
1411    *  @if maint
1412    *  This is a helper function for the rotate algorithm.
1413    *  @endif
1414   */
1415   template<typename _ForwardIterator>
1416     void
1417     __rotate(_ForwardIterator __first,
1418              _ForwardIterator __middle,
1419              _ForwardIterator __last,
1420               forward_iterator_tag)
1421     {
1422       if ((__first == __middle) || (__last  == __middle))
1423         return;
1424
1425       _ForwardIterator __first2 = __middle;
1426       do {
1427         swap(*__first++, *__first2++);
1428         if (__first == __middle)
1429           __middle = __first2;
1430       } while (__first2 != __last);
1431
1432       __first2 = __middle;
1433
1434       while (__first2 != __last) {
1435         swap(*__first++, *__first2++);
1436         if (__first == __middle)
1437           __middle = __first2;
1438         else if (__first2 == __last)
1439           __first2 = __middle;
1440       }
1441     }
1442
1443   /**
1444    *  @if maint
1445    *  This is a helper function for the rotate algorithm.
1446    *  @endif
1447   */
1448   template<typename _BidirectionalIterator>
1449     void
1450     __rotate(_BidirectionalIterator __first,
1451              _BidirectionalIterator __middle,
1452              _BidirectionalIterator __last,
1453               bidirectional_iterator_tag)
1454     {
1455       // concept requirements
1456       __glibcxx_function_requires(_Mutable_BidirectionalIteratorConcept<
1457             _BidirectionalIterator>)
1458
1459       if ((__first == __middle) || (__last  == __middle))
1460         return;
1461
1462       std::__reverse(__first,  __middle, bidirectional_iterator_tag());
1463       std::__reverse(__middle, __last,   bidirectional_iterator_tag());
1464
1465       while (__first != __middle && __middle != __last)
1466         swap(*__first++, *--__last);
1467
1468       if (__first == __middle) {
1469         std::__reverse(__middle, __last,   bidirectional_iterator_tag());
1470       }
1471       else {
1472         std::__reverse(__first,  __middle, bidirectional_iterator_tag());
1473       }
1474     }
1475
1476   /**
1477    *  @if maint
1478    *  This is a helper function for the rotate algorithm.
1479    *  @endif
1480   */
1481   template<typename _RandomAccessIterator>
1482     void
1483     __rotate(_RandomAccessIterator __first,
1484              _RandomAccessIterator __middle,
1485              _RandomAccessIterator __last,
1486              random_access_iterator_tag)
1487     {
1488       // concept requirements
1489       __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
1490             _RandomAccessIterator>)
1491
1492       if ((__first == __middle) || (__last  == __middle))
1493         return;
1494
1495       typedef typename iterator_traits<_RandomAccessIterator>::difference_type _Distance;
1496       typedef typename iterator_traits<_RandomAccessIterator>::value_type _ValueType;
1497
1498       _Distance __n = __last   - __first;
1499       _Distance __k = __middle - __first;
1500       _Distance __l = __n - __k;
1501
1502       if (__k == __l) {
1503         std::swap_ranges(__first, __middle, __middle);
1504         return;
1505       }
1506
1507       _Distance __d = __gcd(__n, __k);
1508
1509       for (_Distance __i = 0; __i < __d; __i++) {
1510         _ValueType __tmp = *__first;
1511         _RandomAccessIterator __p = __first;
1512
1513         if (__k < __l) {
1514           for (_Distance __j = 0; __j < __l/__d; __j++) {
1515             if (__p > __first + __l) {
1516               *__p = *(__p - __l);
1517               __p -= __l;
1518             }
1519
1520             *__p = *(__p + __k);
1521             __p += __k;
1522           }
1523         }
1524
1525         else {
1526           for (_Distance __j = 0; __j < __k/__d - 1; __j ++) {
1527             if (__p < __last - __k) {
1528               *__p = *(__p + __k);
1529               __p += __k;
1530             }
1531
1532             *__p = * (__p - __l);
1533             __p -= __l;
1534           }
1535         }
1536
1537         *__p = __tmp;
1538         ++__first;
1539       }
1540     }
1541
1542   /**
1543    *  @brief Rotate the elements of a sequence.
1544    *  @param  first   A forward iterator.
1545    *  @param  middle  A forward iterator.
1546    *  @param  last    A forward iterator.
1547    *  @return  Nothing.
1548    *
1549    *  Rotates the elements of the range @p [first,last) by @p (middle-first)
1550    *  positions so that the element at @p middle is moved to @p first, the
1551    *  element at @p middle+1 is moved to @first+1 and so on for each element
1552    *  in the range @p [first,last).
1553    *
1554    *  This effectively swaps the ranges @p [first,middle) and
1555    *  @p [middle,last).
1556    *
1557    *  Performs @p *(first+(n+(last-middle))%(last-first))=*(first+n) for
1558    *  each @p n in the range @p [0,last-first).
1559   */
1560   template<typename _ForwardIterator>
1561     inline void
1562     rotate(_ForwardIterator __first, _ForwardIterator __middle, _ForwardIterator __last)
1563     {
1564       // concept requirements
1565       __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<_ForwardIterator>)
1566
1567       typedef typename iterator_traits<_ForwardIterator>::iterator_category _IterType;
1568       std::__rotate(__first, __middle, __last, _IterType());
1569     }
1570
1571   /**
1572    *  @brief Copy a sequence, rotating its elements.
1573    *  @param  first   A forward iterator.
1574    *  @param  middle  A forward iterator.
1575    *  @param  last    A forward iterator.
1576    *  @param  result  An output iterator.
1577    *  @return   An iterator designating the end of the resulting sequence.
1578    *
1579    *  Copies the elements of the range @p [first,last) to the range
1580    *  beginning at @result, rotating the copied elements by @p (middle-first)
1581    *  positions so that the element at @p middle is moved to @p result, the
1582    *  element at @p middle+1 is moved to @result+1 and so on for each element
1583    *  in the range @p [first,last).
1584    *
1585    *  Performs @p *(result+(n+(last-middle))%(last-first))=*(first+n) for
1586    *  each @p n in the range @p [0,last-first).
1587   */
1588   template<typename _ForwardIterator, typename _OutputIterator>
1589     _OutputIterator
1590     rotate_copy(_ForwardIterator __first, _ForwardIterator __middle,
1591                 _ForwardIterator __last, _OutputIterator __result)
1592     {
1593       // concept requirements
1594       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
1595       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
1596                 typename iterator_traits<_ForwardIterator>::value_type>)
1597
1598       return std::copy(__first, __middle, copy(__middle, __last, __result));
1599     }
1600
1601
1602   /**
1603    *  @if maint
1604    *  Return a random number in the range [0, __n).  This function encapsulates
1605    *  whether we're using rand (part of the standard C library) or lrand48
1606    *  (not standard, but a much better choice whenever it's available).
1607    *
1608    *  XXX There is no corresponding encapsulation fn to seed the generator.
1609    *  @endif
1610   */
1611   template<typename _Distance>
1612     inline _Distance
1613     __random_number(_Distance __n)
1614     {
1615   #ifdef _GLIBCXX_HAVE_DRAND48
1616       return lrand48() % __n;
1617   #else
1618       return rand() % __n;
1619   #endif
1620     }
1621
1622
1623   /**
1624    *  @brief Randomly shuffle the elements of a sequence.
1625    *  @param  first   A forward iterator.
1626    *  @param  last    A forward iterator.
1627    *  @return  Nothing.
1628    *
1629    *  Reorder the elements in the range @p [first,last) using a random
1630    *  distribution, so that every possible ordering of the sequence is
1631    *  equally likely.
1632   */
1633   template<typename _RandomAccessIterator>
1634     inline void
1635     random_shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last)
1636     {
1637       // concept requirements
1638       __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
1639             _RandomAccessIterator>)
1640
1641       if (__first == __last) return;
1642       for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i)
1643         std::iter_swap(__i, __first + std::__random_number((__i - __first) + 1));
1644     }
1645
1646   /**
1647    *  @brief Shuffle the elements of a sequence using a random number
1648    *         generator.
1649    *  @param  first   A forward iterator.
1650    *  @param  last    A forward iterator.
1651    *  @param  rand    The RNG functor or function.
1652    *  @return  Nothing.
1653    *
1654    *  Reorders the elements in the range @p [first,last) using @p rand to
1655    *  provide a random distribution. Calling @p rand(N) for a positive
1656    *  integer @p N should return a randomly chosen integer from the
1657    *  range [0,N).
1658   */
1659   template<typename _RandomAccessIterator, typename _RandomNumberGenerator>
1660     void
1661     random_shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last,
1662                    _RandomNumberGenerator& __rand)
1663     {
1664       // concept requirements
1665       __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
1666             _RandomAccessIterator>)
1667
1668       if (__first == __last) return;
1669       for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i)
1670         std::iter_swap(__i, __first + __rand((__i - __first) + 1));
1671     }
1672
1673
1674   /**
1675    *  @if maint
1676    *  This is a helper function...
1677    *  @endif
1678   */
1679   template<typename _ForwardIterator, typename _Predicate>
1680     _ForwardIterator
1681     __partition(_ForwardIterator __first, _ForwardIterator __last,
1682                 _Predicate   __pred,
1683                 forward_iterator_tag)
1684     {
1685       if (__first == __last) return __first;
1686
1687       while (__pred(*__first))
1688         if (++__first == __last) return __first;
1689
1690       _ForwardIterator __next = __first;
1691
1692       while (++__next != __last)
1693         if (__pred(*__next)) {
1694           swap(*__first, *__next);
1695           ++__first;
1696         }
1697
1698       return __first;
1699     }
1700
1701   /**
1702    *  @if maint
1703    *  This is a helper function...
1704    *  @endif
1705   */
1706   template<typename _BidirectionalIterator, typename _Predicate>
1707     _BidirectionalIterator
1708     __partition(_BidirectionalIterator __first, _BidirectionalIterator __last,
1709                 _Predicate __pred,
1710                 bidirectional_iterator_tag)
1711     {
1712       while (true) {
1713         while (true)
1714           if (__first == __last)
1715             return __first;
1716           else if (__pred(*__first))
1717             ++__first;
1718           else
1719             break;
1720         --__last;
1721         while (true)
1722           if (__first == __last)
1723             return __first;
1724           else if (!__pred(*__last))
1725             --__last;
1726           else
1727             break;
1728         std::iter_swap(__first, __last);
1729         ++__first;
1730       }
1731     }
1732
1733   /**
1734    *  @brief Move elements for which a predicate is true to the beginning
1735    *         of a sequence.
1736    *  @param  first   A forward iterator.
1737    *  @param  last    A forward iterator.
1738    *  @param  pred    A predicate functor.
1739    *  @return  An iterator @p middle such that @p pred(i) is true for each
1740    *  iterator @p i in the range @p [first,middle) and false for each @p i
1741    *  in the range @p [middle,last).
1742    *
1743    *  @p pred must not modify its operand. @p partition() does not preserve
1744    *  the relative ordering of elements in each group, use
1745    *  @p stable_partition() if this is needed.
1746   */
1747   template<typename _ForwardIterator, typename _Predicate>
1748     inline _ForwardIterator
1749     partition(_ForwardIterator __first, _ForwardIterator __last,
1750               _Predicate   __pred)
1751     {
1752       // concept requirements
1753       __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<_ForwardIterator>)
1754       __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
1755             typename iterator_traits<_ForwardIterator>::value_type>)
1756
1757       return std::__partition(__first, __last, __pred, std::__iterator_category(__first));
1758     }
1759
1760
1761   /**
1762    *  @if maint
1763    *  This is a helper function...
1764    *  @endif
1765   */
1766   template<typename _ForwardIterator, typename _Predicate, typename _Distance>
1767     _ForwardIterator
1768     __inplace_stable_partition(_ForwardIterator __first, _ForwardIterator __last,
1769                                _Predicate __pred, _Distance __len)
1770     {
1771       if (__len == 1)
1772         return __pred(*__first) ? __last : __first;
1773       _ForwardIterator __middle = __first;
1774       std::advance(__middle, __len / 2);
1775       _ForwardIterator __begin = std::__inplace_stable_partition(__first, __middle,
1776                                                                  __pred,
1777                                                                  __len / 2);
1778       _ForwardIterator __end = std::__inplace_stable_partition(__middle, __last,
1779                                                                __pred,
1780                                                                __len - __len / 2);
1781       std::rotate(__begin, __middle, __end);
1782       std::advance(__begin, std::distance(__middle, __end));
1783       return __begin;
1784     }
1785
1786   /**
1787    *  @if maint
1788    *  This is a helper function...
1789    *  @endif
1790   */
1791   template<typename _ForwardIterator, typename _Pointer, typename _Predicate,
1792            typename _Distance>
1793     _ForwardIterator
1794     __stable_partition_adaptive(_ForwardIterator __first, _ForwardIterator __last,
1795                                 _Predicate __pred, _Distance __len,
1796                                 _Pointer __buffer,
1797                                 _Distance __buffer_size)
1798     {
1799       if (__len <= __buffer_size) {
1800         _ForwardIterator __result1 = __first;
1801         _Pointer __result2 = __buffer;
1802         for ( ; __first != __last ; ++__first)
1803           if (__pred(*__first)) {
1804             *__result1 = *__first;
1805             ++__result1;
1806           }
1807           else {
1808             *__result2 = *__first;
1809             ++__result2;
1810           }
1811         std::copy(__buffer, __result2, __result1);
1812         return __result1;
1813       }
1814       else {
1815         _ForwardIterator __middle = __first;
1816         std::advance(__middle, __len / 2);
1817         _ForwardIterator __begin = std::__stable_partition_adaptive(__first, __middle,
1818                                                                     __pred,
1819                                                                     __len / 2,
1820                                                                     __buffer, __buffer_size);
1821         _ForwardIterator __end = std::__stable_partition_adaptive( __middle, __last,
1822                                                                    __pred,
1823                                                                    __len - __len / 2,
1824                                                                    __buffer, __buffer_size);
1825         std::rotate(__begin, __middle, __end);
1826         std::advance(__begin, std::distance(__middle, __end));
1827         return __begin;
1828       }
1829     }
1830
1831   /**
1832    *  @brief Move elements for which a predicate is true to the beginning
1833    *         of a sequence, preserving relative ordering.
1834    *  @param  first   A forward iterator.
1835    *  @param  last    A forward iterator.
1836    *  @param  pred    A predicate functor.
1837    *  @return  An iterator @p middle such that @p pred(i) is true for each
1838    *  iterator @p i in the range @p [first,middle) and false for each @p i
1839    *  in the range @p [middle,last).
1840    *
1841    *  Performs the same function as @p partition() with the additional
1842    *  guarantee that the relative ordering of elements in each group is
1843    *  preserved, so any two elements @p x and @p y in the range
1844    *  @p [first,last) such that @p pred(x)==pred(y) will have the same
1845    *  relative ordering after calling @p stable_partition().
1846   */
1847   template<typename _ForwardIterator, typename _Predicate>
1848     _ForwardIterator
1849     stable_partition(_ForwardIterator __first, _ForwardIterator __last,
1850                      _Predicate __pred)
1851     {
1852       // concept requirements
1853       __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<_ForwardIterator>)
1854       __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
1855             typename iterator_traits<_ForwardIterator>::value_type>)
1856
1857       if (__first == __last)
1858         return __first;
1859       else
1860       {
1861         typedef typename iterator_traits<_ForwardIterator>::value_type _ValueType;
1862         typedef typename iterator_traits<_ForwardIterator>::difference_type _DistanceType;
1863
1864         _Temporary_buffer<_ForwardIterator, _ValueType> __buf(__first, __last);
1865         if (__buf.size() > 0)
1866           return std::__stable_partition_adaptive(__first, __last, __pred,
1867                                                   _DistanceType(__buf.requested_size()),
1868                                                   __buf.begin(), __buf.size());
1869         else
1870           return std::__inplace_stable_partition(__first, __last, __pred,
1871                                                  _DistanceType(__buf.requested_size()));
1872       }
1873     }
1874
1875   /**
1876    *  @if maint
1877    *  This is a helper function...
1878    *  @endif
1879   */
1880   template<typename _RandomAccessIterator, typename _Tp>
1881     _RandomAccessIterator
1882     __unguarded_partition(_RandomAccessIterator __first, _RandomAccessIterator __last,
1883                           _Tp __pivot)
1884     {
1885       while (true) {
1886         while (*__first < __pivot)
1887           ++__first;
1888         --__last;
1889         while (__pivot < *__last)
1890           --__last;
1891         if (!(__first < __last))
1892           return __first;
1893         std::iter_swap(__first, __last);
1894         ++__first;
1895       }
1896     }
1897
1898   /**
1899    *  @if maint
1900    *  This is a helper function...
1901    *  @endif
1902   */
1903   template<typename _RandomAccessIterator, typename _Tp, typename _Compare>
1904     _RandomAccessIterator
1905     __unguarded_partition(_RandomAccessIterator __first, _RandomAccessIterator __last,
1906                           _Tp __pivot, _Compare __comp)
1907     {
1908       while (true) {
1909         while (__comp(*__first, __pivot))
1910           ++__first;
1911         --__last;
1912         while (__comp(__pivot, *__last))
1913           --__last;
1914         if (!(__first < __last))
1915           return __first;
1916         std::iter_swap(__first, __last);
1917         ++__first;
1918       }
1919     }
1920
1921
1922   /**
1923    *  @if maint
1924    *  @doctodo
1925    *  This controls some aspect of the sort routines.
1926    *  @endif
1927   */
1928   enum { _S_threshold = 16 };
1929
1930   /**
1931    *  @if maint
1932    *  This is a helper function for the sort routine.
1933    *  @endif
1934   */
1935   template<typename _RandomAccessIterator, typename _Tp>
1936     void
1937     __unguarded_linear_insert(_RandomAccessIterator __last, _Tp __val)
1938     {
1939       _RandomAccessIterator __next = __last;
1940       --__next;
1941       while (__val < *__next) {
1942         *__last = *__next;
1943         __last = __next;
1944         --__next;
1945       }
1946       *__last = __val;
1947     }
1948
1949   /**
1950    *  @if maint
1951    *  This is a helper function for the sort routine.
1952    *  @endif
1953   */
1954   template<typename _RandomAccessIterator, typename _Tp, typename _Compare>
1955     void
1956     __unguarded_linear_insert(_RandomAccessIterator __last, _Tp __val, _Compare __comp)
1957     {
1958       _RandomAccessIterator __next = __last;
1959       --__next;
1960       while (__comp(__val, *__next)) {
1961         *__last = *__next;
1962         __last = __next;
1963         --__next;
1964       }
1965       *__last = __val;
1966     }
1967
1968   /**
1969    *  @if maint
1970    *  This is a helper function for the sort routine.
1971    *  @endif
1972   */
1973   template<typename _RandomAccessIterator>
1974     void
1975     __insertion_sort(_RandomAccessIterator __first, _RandomAccessIterator __last)
1976     {
1977       if (__first == __last) return;
1978
1979       for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i)
1980       {
1981         typename iterator_traits<_RandomAccessIterator>::value_type __val = *__i;
1982         if (__val < *__first) {
1983           std::copy_backward(__first, __i, __i + 1);
1984           *__first = __val;
1985         }
1986         else
1987           std::__unguarded_linear_insert(__i, __val);
1988       }
1989     }
1990
1991   /**
1992    *  @if maint
1993    *  This is a helper function for the sort routine.
1994    *  @endif
1995   */
1996   template<typename _RandomAccessIterator, typename _Compare>
1997     void
1998     __insertion_sort(_RandomAccessIterator __first, _RandomAccessIterator __last,
1999                      _Compare __comp)
2000     {
2001       if (__first == __last) return;
2002
2003       for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i)
2004       {
2005         typename iterator_traits<_RandomAccessIterator>::value_type __val = *__i;
2006         if (__comp(__val, *__first)) {
2007           std::copy_backward(__first, __i, __i + 1);
2008           *__first = __val;
2009         }
2010         else
2011           std::__unguarded_linear_insert(__i, __val, __comp);
2012       }
2013     }
2014
2015   /**
2016    *  @if maint
2017    *  This is a helper function for the sort routine.
2018    *  @endif
2019   */
2020   template<typename _RandomAccessIterator>
2021     inline void
2022     __unguarded_insertion_sort(_RandomAccessIterator __first, _RandomAccessIterator __last)
2023     {
2024       typedef typename iterator_traits<_RandomAccessIterator>::value_type _ValueType;
2025
2026       for (_RandomAccessIterator __i = __first; __i != __last; ++__i)
2027         std::__unguarded_linear_insert(__i, _ValueType(*__i));
2028     }
2029
2030   /**
2031    *  @if maint
2032    *  This is a helper function for the sort routine.
2033    *  @endif
2034   */
2035   template<typename _RandomAccessIterator, typename _Compare>
2036     inline void
2037     __unguarded_insertion_sort(_RandomAccessIterator __first, _RandomAccessIterator __last,
2038                                _Compare __comp)
2039     {
2040       typedef typename iterator_traits<_RandomAccessIterator>::value_type _ValueType;
2041
2042       for (_RandomAccessIterator __i = __first; __i != __last; ++__i)
2043         std::__unguarded_linear_insert(__i, _ValueType(*__i), __comp);
2044     }
2045
2046   /**
2047    *  @if maint
2048    *  This is a helper function for the sort routine.
2049    *  @endif
2050   */
2051   template<typename _RandomAccessIterator>
2052     void
2053     __final_insertion_sort(_RandomAccessIterator __first, _RandomAccessIterator __last)
2054     {
2055       if (__last - __first > _S_threshold) {
2056         std::__insertion_sort(__first, __first + _S_threshold);
2057         std::__unguarded_insertion_sort(__first + _S_threshold, __last);
2058       }
2059       else
2060         std::__insertion_sort(__first, __last);
2061     }
2062
2063   /**
2064    *  @if maint
2065    *  This is a helper function for the sort routine.
2066    *  @endif
2067   */
2068   template<typename _RandomAccessIterator, typename _Compare>
2069     void
2070     __final_insertion_sort(_RandomAccessIterator __first, _RandomAccessIterator __last,
2071                            _Compare __comp)
2072     {
2073       if (__last - __first > _S_threshold) {
2074         std::__insertion_sort(__first, __first + _S_threshold, __comp);
2075         std::__unguarded_insertion_sort(__first + _S_threshold, __last, __comp);
2076       }
2077       else
2078         std::__insertion_sort(__first, __last, __comp);
2079     }
2080
2081   /**
2082    *  @if maint
2083    *  This is a helper function for the sort routine.
2084    *  @endif
2085   */
2086   template<typename _Size>
2087     inline _Size
2088     __lg(_Size __n)
2089     {
2090       _Size __k;
2091       for (__k = 0; __n != 1; __n >>= 1) ++__k;
2092       return __k;
2093     }
2094
2095   /**
2096    *  @brief Sort the smallest elements of a sequence.
2097    *  @param  first   An iterator.
2098    *  @param  middle  Another iterator.
2099    *  @param  last    Another iterator.
2100    *  @return  Nothing.
2101    *
2102    *  Sorts the smallest @p (middle-first) elements in the range
2103    *  @p [first,last) and moves them to the range @p [first,middle). The
2104    *  order of the remaining elements in the range @p [middle,last) is
2105    *  undefined.
2106    *  After the sort if @p i and @j are iterators in the range
2107    *  @p [first,middle) such that @i precedes @j and @k is an iterator in
2108    *  the range @p [middle,last) then @p *j<*i and @p *k<*i are both false.
2109   */
2110   template<typename _RandomAccessIterator>
2111     void
2112     partial_sort(_RandomAccessIterator __first,
2113                  _RandomAccessIterator __middle,
2114                  _RandomAccessIterator __last)
2115     {
2116       typedef typename iterator_traits<_RandomAccessIterator>::value_type _ValueType;
2117
2118       // concept requirements
2119       __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
2120             _RandomAccessIterator>)
2121       __glibcxx_function_requires(_LessThanComparableConcept<_ValueType>)
2122
2123       std::make_heap(__first, __middle);
2124       for (_RandomAccessIterator __i = __middle; __i < __last; ++__i)
2125         if (*__i < *__first)
2126           std::__pop_heap(__first, __middle, __i, _ValueType(*__i));
2127       std::sort_heap(__first, __middle);
2128     }
2129
2130   /**
2131    *  @brief Sort the smallest elements of a sequence using a predicate
2132    *         for comparison.
2133    *  @param  first   An iterator.
2134    *  @param  middle  Another iterator.
2135    *  @param  last    Another iterator.
2136    *  @param  comp    A comparison functor.
2137    *  @return  Nothing.
2138    *
2139    *  Sorts the smallest @p (middle-first) elements in the range
2140    *  @p [first,last) and moves them to the range @p [first,middle). The
2141    *  order of the remaining elements in the range @p [middle,last) is
2142    *  undefined.
2143    *  After the sort if @p i and @j are iterators in the range
2144    *  @p [first,middle) such that @i precedes @j and @k is an iterator in
2145    *  the range @p [middle,last) then @p *comp(j,*i) and @p comp(*k,*i)
2146    *  are both false.
2147   */
2148   template<typename _RandomAccessIterator, typename _Compare>
2149     void
2150     partial_sort(_RandomAccessIterator __first,
2151                  _RandomAccessIterator __middle,
2152                  _RandomAccessIterator __last,
2153                  _Compare __comp)
2154     {
2155       typedef typename iterator_traits<_RandomAccessIterator>::value_type _ValueType;
2156
2157       // concept requirements
2158       __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
2159             _RandomAccessIterator>)
2160       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2161                                                           _ValueType, _ValueType>)
2162
2163       std::make_heap(__first, __middle, __comp);
2164       for (_RandomAccessIterator __i = __middle; __i < __last; ++__i)
2165         if (__comp(*__i, *__first))
2166           std::__pop_heap(__first, __middle, __i, _ValueType(*__i), __comp);
2167       std::sort_heap(__first, __middle, __comp);
2168     }
2169
2170   /**
2171    *  @brief Copy the smallest elements of a sequence.
2172    *  @param  first   An iterator.
2173    *  @param  last    Another iterator.
2174    *  @param  result_first   A random-access iterator.
2175    *  @param  result_last    Another random-access iterator.
2176    *  @return   An iterator indicating the end of the resulting sequence.
2177    *
2178    *  Copies and sorts the smallest N values from the range @p [first,last)
2179    *  to the range beginning at @p result_first, where the number of
2180    *  elements to be copied, @p N, is the smaller of @p (last-first) and
2181    *  @p (result_last-result_first).
2182    *  After the sort if @p i and @j are iterators in the range
2183    *  @p [result_first,result_first+N) such that @i precedes @j then
2184    *  @p *j<*i is false.
2185    *  The value returned is @p result_first+N.
2186   */
2187   template<typename _InputIterator, typename _RandomAccessIterator>
2188     _RandomAccessIterator
2189     partial_sort_copy(_InputIterator __first, _InputIterator __last,
2190                       _RandomAccessIterator __result_first,
2191                       _RandomAccessIterator __result_last)
2192     {
2193       typedef typename iterator_traits<_InputIterator>::value_type _InputValueType;
2194       typedef typename iterator_traits<_RandomAccessIterator>::value_type _OutputValueType;
2195       typedef typename iterator_traits<_RandomAccessIterator>::difference_type _DistanceType;
2196
2197       // concept requirements
2198       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
2199       __glibcxx_function_requires(_ConvertibleConcept<_InputValueType, _OutputValueType>)
2200       __glibcxx_function_requires(_LessThanComparableConcept<_OutputValueType>)
2201       __glibcxx_function_requires(_LessThanComparableConcept<_InputValueType>)
2202
2203       if (__result_first == __result_last) return __result_last;
2204       _RandomAccessIterator __result_real_last = __result_first;
2205       while(__first != __last && __result_real_last != __result_last) {
2206         *__result_real_last = *__first;
2207         ++__result_real_last;
2208         ++__first;
2209       }
2210       std::make_heap(__result_first, __result_real_last);
2211       while (__first != __last) {
2212         if (*__first < *__result_first)
2213           std::__adjust_heap(__result_first, _DistanceType(0),
2214                              _DistanceType(__result_real_last - __result_first),
2215                              _InputValueType(*__first));
2216         ++__first;
2217       }
2218       std::sort_heap(__result_first, __result_real_last);
2219       return __result_real_last;
2220     }
2221
2222   /**
2223    *  @brief Copy the smallest elements of a sequence using a predicate for
2224    *         comparison.
2225    *  @param  first   An input iterator.
2226    *  @param  last    Another input iterator.
2227    *  @param  result_first   A random-access iterator.
2228    *  @param  result_last    Another random-access iterator.
2229    *  @param  comp    A comparison functor.
2230    *  @return   An iterator indicating the end of the resulting sequence.
2231    *
2232    *  Copies and sorts the smallest N values from the range @p [first,last)
2233    *  to the range beginning at @p result_first, where the number of
2234    *  elements to be copied, @p N, is the smaller of @p (last-first) and
2235    *  @p (result_last-result_first).
2236    *  After the sort if @p i and @j are iterators in the range
2237    *  @p [result_first,result_first+N) such that @i precedes @j then
2238    *  @p comp(*j,*i) is false.
2239    *  The value returned is @p result_first+N.
2240   */
2241   template<typename _InputIterator, typename _RandomAccessIterator, typename _Compare>
2242     _RandomAccessIterator
2243     partial_sort_copy(_InputIterator __first, _InputIterator __last,
2244                       _RandomAccessIterator __result_first,
2245                       _RandomAccessIterator __result_last,
2246                       _Compare __comp)
2247     {
2248       typedef typename iterator_traits<_InputIterator>::value_type _InputValueType;
2249       typedef typename iterator_traits<_RandomAccessIterator>::value_type _OutputValueType;
2250       typedef typename iterator_traits<_RandomAccessIterator>::difference_type _DistanceType;
2251
2252       // concept requirements
2253       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
2254       __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<_RandomAccessIterator>)
2255       __glibcxx_function_requires(_ConvertibleConcept<_InputValueType, _OutputValueType>)
2256       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2257                                   _OutputValueType, _OutputValueType>)
2258
2259       if (__result_first == __result_last) return __result_last;
2260       _RandomAccessIterator __result_real_last = __result_first;
2261       while(__first != __last && __result_real_last != __result_last) {
2262         *__result_real_last = *__first;
2263         ++__result_real_last;
2264         ++__first;
2265       }
2266       std::make_heap(__result_first, __result_real_last, __comp);
2267       while (__first != __last) {
2268         if (__comp(*__first, *__result_first))
2269           std::__adjust_heap(__result_first, _DistanceType(0),
2270                              _DistanceType(__result_real_last - __result_first),
2271                              _InputValueType(*__first),
2272                              __comp);
2273         ++__first;
2274       }
2275       std::sort_heap(__result_first, __result_real_last, __comp);
2276       return __result_real_last;
2277     }
2278
2279   /**
2280    *  @if maint
2281    *  This is a helper function for the sort routine.
2282    *  @endif
2283   */
2284   template<typename _RandomAccessIterator, typename _Size>
2285     void
2286     __introsort_loop(_RandomAccessIterator __first, _RandomAccessIterator __last,
2287                      _Size __depth_limit)
2288     {
2289       typedef typename iterator_traits<_RandomAccessIterator>::value_type _ValueType;
2290
2291       while (__last - __first > _S_threshold) {
2292         if (__depth_limit == 0) {
2293           std::partial_sort(__first, __last, __last);
2294           return;
2295         }
2296         --__depth_limit;
2297         _RandomAccessIterator __cut =
2298           std::__unguarded_partition(__first, __last,
2299                                      _ValueType(std::__median(*__first,
2300                                                               *(__first + (__last - __first)/2),
2301                                                               *(__last - 1))));
2302         std::__introsort_loop(__cut, __last, __depth_limit);
2303         __last = __cut;
2304       }
2305     }
2306
2307   /**
2308    *  @if maint
2309    *  This is a helper function for the sort routine.
2310    *  @endif
2311   */
2312   template<typename _RandomAccessIterator, typename _Size, typename _Compare>
2313     void
2314     __introsort_loop(_RandomAccessIterator __first, _RandomAccessIterator __last,
2315                      _Size __depth_limit, _Compare __comp)
2316     {
2317       typedef typename iterator_traits<_RandomAccessIterator>::value_type _ValueType;
2318
2319       while (__last - __first > _S_threshold) {
2320         if (__depth_limit == 0) {
2321           std::partial_sort(__first, __last, __last, __comp);
2322           return;
2323         }
2324         --__depth_limit;
2325         _RandomAccessIterator __cut =
2326           std::__unguarded_partition(__first, __last,
2327                                      _ValueType(std::__median(*__first,
2328                                                               *(__first + (__last - __first)/2),
2329                                                               *(__last - 1), __comp)), __comp);
2330         std::__introsort_loop(__cut, __last, __depth_limit, __comp);
2331         __last = __cut;
2332       }
2333     }
2334
2335   /**
2336    *  @brief Sort the elements of a sequence.
2337    *  @param  first   An iterator.
2338    *  @param  last    Another iterator.
2339    *  @return  Nothing.
2340    *
2341    *  Sorts the elements in the range @p [first,last) in ascending order,
2342    *  such that @p *(i+1)<*i is false for each iterator @p i in the range
2343    *  @p [first,last-1).
2344    *
2345    *  The relative ordering of equivalent elements is not preserved, use
2346    *  @p stable_sort() if this is needed.
2347   */
2348   template<typename _RandomAccessIterator>
2349     inline void
2350     sort(_RandomAccessIterator __first, _RandomAccessIterator __last)
2351     {
2352       typedef typename iterator_traits<_RandomAccessIterator>::value_type _ValueType;
2353
2354       // concept requirements
2355       __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
2356             _RandomAccessIterator>)
2357       __glibcxx_function_requires(_LessThanComparableConcept<_ValueType>)
2358
2359       if (__first != __last) {
2360         std::__introsort_loop(__first, __last, __lg(__last - __first) * 2);
2361         std::__final_insertion_sort(__first, __last);
2362       }
2363     }
2364
2365   /**
2366    *  @brief Sort the elements of a sequence using a predicate for comparison.
2367    *  @param  first   An iterator.
2368    *  @param  last    Another iterator.
2369    *  @param  comp    A comparison functor.
2370    *  @return  Nothing.
2371    *
2372    *  Sorts the elements in the range @p [first,last) in ascending order,
2373    *  such that @p comp(*(i+1),*i) is false for every iterator @p i in the
2374    *  range @p [first,last-1).
2375    *
2376    *  The relative ordering of equivalent elements is not preserved, use
2377    *  @p stable_sort() if this is needed.
2378   */
2379   template<typename _RandomAccessIterator, typename _Compare>
2380     inline void
2381     sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
2382     {
2383       typedef typename iterator_traits<_RandomAccessIterator>::value_type _ValueType;
2384
2385       // concept requirements
2386       __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
2387             _RandomAccessIterator>)
2388       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, _ValueType, _ValueType>)
2389
2390       if (__first != __last) {
2391         std::__introsort_loop(__first, __last, __lg(__last - __first) * 2, __comp);
2392         std::__final_insertion_sort(__first, __last, __comp);
2393       }
2394     }
2395
2396   /**
2397    *  @brief Finds the first position in which @a val could be inserted
2398    *         without changing the ordering.
2399    *  @param  first   An iterator.
2400    *  @param  last    Another iterator.
2401    *  @param  val     The search term.
2402    *  @return  An iterator pointing to the first element "not less than" @a val,
2403    *           or end() if every element is less than @a val.
2404    *  @ingroup binarysearch
2405   */
2406   template<typename _ForwardIterator, typename _Tp>
2407     _ForwardIterator
2408     lower_bound(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __val)
2409     {
2410       typedef typename iterator_traits<_ForwardIterator>::value_type _ValueType;
2411       typedef typename iterator_traits<_ForwardIterator>::difference_type _DistanceType;
2412
2413       // concept requirements
2414       // Note that these are slightly stricter than those of the 4-argument
2415       // version, defined next.  The difference is in the strictness of the
2416       // comparison operations... so for looser checking, define your own
2417       // comparison function, as was intended.
2418       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
2419       __glibcxx_function_requires(_SameTypeConcept<_Tp, _ValueType>)
2420       __glibcxx_function_requires(_LessThanComparableConcept<_Tp>)
2421
2422       _DistanceType __len = std::distance(__first, __last);
2423       _DistanceType __half;
2424       _ForwardIterator __middle;
2425
2426       while (__len > 0) {
2427         __half = __len >> 1;
2428         __middle = __first;
2429         std::advance(__middle, __half);
2430         if (*__middle < __val) {
2431           __first = __middle;
2432           ++__first;
2433           __len = __len - __half - 1;
2434         }
2435         else
2436           __len = __half;
2437       }
2438       return __first;
2439     }
2440
2441   /**
2442    *  @brief Finds the first position in which @a val could be inserted
2443    *         without changing the ordering.
2444    *  @param  first   An iterator.
2445    *  @param  last    Another iterator.
2446    *  @param  val     The search term.
2447    *  @param  comp    A functor to use for comparisons.
2448    *  @return  An iterator pointing to the first element "not less than" @a val,
2449    *           or end() if every element is less than @a val.
2450    *  @ingroup binarysearch
2451    *
2452    *  The comparison function should have the same effects on ordering as
2453    *  the function used for the initial sort.
2454   */
2455   template<typename _ForwardIterator, typename _Tp, typename _Compare>
2456     _ForwardIterator
2457     lower_bound(_ForwardIterator __first, _ForwardIterator __last,
2458                 const _Tp& __val, _Compare __comp)
2459     {
2460       typedef typename iterator_traits<_ForwardIterator>::value_type _ValueType;
2461       typedef typename iterator_traits<_ForwardIterator>::difference_type _DistanceType;
2462
2463       // concept requirements
2464       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
2465       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, _ValueType, _Tp>)
2466
2467       _DistanceType __len = std::distance(__first, __last);
2468       _DistanceType __half;
2469       _ForwardIterator __middle;
2470
2471       while (__len > 0) {
2472         __half = __len >> 1;
2473         __middle = __first;
2474         std::advance(__middle, __half);
2475         if (__comp(*__middle, __val)) {
2476           __first = __middle;
2477           ++__first;
2478           __len = __len - __half - 1;
2479         }
2480         else
2481           __len = __half;
2482       }
2483       return __first;
2484     }
2485
2486   /**
2487    *  @brief Finds the last position in which @a val could be inserted
2488    *         without changing the ordering.
2489    *  @param  first   An iterator.
2490    *  @param  last    Another iterator.
2491    *  @param  val     The search term.
2492    *  @return  An iterator pointing to the first element greater than @a val,
2493    *           or end() if no elements are greater than @a val.
2494    *  @ingroup binarysearch
2495   */
2496   template<typename _ForwardIterator, typename _Tp>
2497     _ForwardIterator
2498     upper_bound(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __val)
2499     {
2500       typedef typename iterator_traits<_ForwardIterator>::value_type _ValueType;
2501       typedef typename iterator_traits<_ForwardIterator>::difference_type _DistanceType;
2502
2503       // concept requirements
2504       // See comments on lower_bound.
2505       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
2506       __glibcxx_function_requires(_SameTypeConcept<_Tp, _ValueType>)
2507       __glibcxx_function_requires(_LessThanComparableConcept<_Tp>)
2508
2509       _DistanceType __len = std::distance(__first, __last);
2510       _DistanceType __half;
2511       _ForwardIterator __middle;
2512
2513       while (__len > 0) {
2514         __half = __len >> 1;
2515         __middle = __first;
2516         std::advance(__middle, __half);
2517         if (__val < *__middle)
2518           __len = __half;
2519         else {
2520           __first = __middle;
2521           ++__first;
2522           __len = __len - __half - 1;
2523         }
2524       }
2525       return __first;
2526     }
2527
2528   /**
2529    *  @brief Finds the last position in which @a val could be inserted
2530    *         without changing the ordering.
2531    *  @param  first   An iterator.
2532    *  @param  last    Another iterator.
2533    *  @param  val     The search term.
2534    *  @param  comp    A functor to use for comparisons.
2535    *  @return  An iterator pointing to the first element greater than @a val,
2536    *           or end() if no elements are greater than @a val.
2537    *  @ingroup binarysearch
2538    *
2539    *  The comparison function should have the same effects on ordering as
2540    *  the function used for the initial sort.
2541   */
2542   template<typename _ForwardIterator, typename _Tp, typename _Compare>
2543     _ForwardIterator
2544     upper_bound(_ForwardIterator __first, _ForwardIterator __last,
2545                 const _Tp& __val, _Compare __comp)
2546     {
2547       typedef typename iterator_traits<_ForwardIterator>::value_type _ValueType;
2548       typedef typename iterator_traits<_ForwardIterator>::difference_type _DistanceType;
2549
2550       // concept requirements
2551       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
2552       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, _Tp, _ValueType>)
2553
2554       _DistanceType __len = std::distance(__first, __last);
2555       _DistanceType __half;
2556       _ForwardIterator __middle;
2557
2558       while (__len > 0) {
2559         __half = __len >> 1;
2560         __middle = __first;
2561         std::advance(__middle, __half);
2562         if (__comp(__val, *__middle))
2563           __len = __half;
2564         else {
2565           __first = __middle;
2566           ++__first;
2567           __len = __len - __half - 1;
2568         }
2569       }
2570       return __first;
2571     }
2572
2573   /**
2574    *  @if maint
2575    *  This is a helper function for the merge routines.
2576    *  @endif
2577   */
2578   template<typename _BidirectionalIterator, typename _Distance>
2579     void
2580     __merge_without_buffer(_BidirectionalIterator __first,
2581                            _BidirectionalIterator __middle,
2582                            _BidirectionalIterator __last,
2583                            _Distance __len1, _Distance __len2)
2584     {
2585       if (__len1 == 0 || __len2 == 0)
2586         return;
2587       if (__len1 + __len2 == 2) {
2588         if (*__middle < *__first)
2589           std::iter_swap(__first, __middle);
2590         return;
2591       }
2592       _BidirectionalIterator __first_cut = __first;
2593       _BidirectionalIterator __second_cut = __middle;
2594       _Distance __len11 = 0;
2595       _Distance __len22 = 0;
2596       if (__len1 > __len2) {
2597         __len11 = __len1 / 2;
2598         std::advance(__first_cut, __len11);
2599         __second_cut = std::lower_bound(__middle, __last, *__first_cut);
2600         __len22 = std::distance(__middle, __second_cut);
2601       }
2602       else {
2603         __len22 = __len2 / 2;
2604         std::advance(__second_cut, __len22);
2605         __first_cut = std::upper_bound(__first, __middle, *__second_cut);
2606         __len11 = std::distance(__first, __first_cut);
2607       }
2608       std::rotate(__first_cut, __middle, __second_cut);
2609       _BidirectionalIterator __new_middle = __first_cut;
2610       std::advance(__new_middle, std::distance(__middle, __second_cut));
2611       std::__merge_without_buffer(__first, __first_cut, __new_middle,
2612                                   __len11, __len22);
2613       std::__merge_without_buffer(__new_middle, __second_cut, __last,
2614                                   __len1 - __len11, __len2 - __len22);
2615     }
2616
2617   /**
2618    *  @if maint
2619    *  This is a helper function for the merge routines.
2620    *  @endif
2621   */
2622   template<typename _BidirectionalIterator, typename _Distance, typename _Compare>
2623     void
2624     __merge_without_buffer(_BidirectionalIterator __first,
2625                            _BidirectionalIterator __middle,
2626                            _BidirectionalIterator __last,
2627                            _Distance __len1, _Distance __len2,
2628                            _Compare __comp)
2629     {
2630       if (__len1 == 0 || __len2 == 0)
2631         return;
2632       if (__len1 + __len2 == 2) {
2633         if (__comp(*__middle, *__first))
2634           std::iter_swap(__first, __middle);
2635         return;
2636       }
2637       _BidirectionalIterator __first_cut = __first;
2638       _BidirectionalIterator __second_cut = __middle;
2639       _Distance __len11 = 0;
2640       _Distance __len22 = 0;
2641       if (__len1 > __len2) {
2642         __len11 = __len1 / 2;
2643         std::advance(__first_cut, __len11);
2644         __second_cut = std::lower_bound(__middle, __last, *__first_cut, __comp);
2645         __len22 = std::distance(__middle, __second_cut);
2646       }
2647       else {
2648         __len22 = __len2 / 2;
2649         std::advance(__second_cut, __len22);
2650         __first_cut = std::upper_bound(__first, __middle, *__second_cut, __comp);
2651         __len11 = std::distance(__first, __first_cut);
2652       }
2653       std::rotate(__first_cut, __middle, __second_cut);
2654       _BidirectionalIterator __new_middle = __first_cut;
2655       std::advance(__new_middle, std::distance(__middle, __second_cut));
2656       std::__merge_without_buffer(__first, __first_cut, __new_middle,
2657                                   __len11, __len22, __comp);
2658       std::__merge_without_buffer(__new_middle, __second_cut, __last,
2659                                   __len1 - __len11, __len2 - __len22, __comp);
2660     }
2661
2662   /**
2663    *  @if maint
2664    *  This is a helper function for the stable sorting routines.
2665    *  @endif
2666   */
2667   template<typename _RandomAccessIterator>
2668     void
2669     __inplace_stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last)
2670     {
2671       if (__last - __first < 15) {
2672         std::__insertion_sort(__first, __last);
2673         return;
2674       }
2675       _RandomAccessIterator __middle = __first + (__last - __first) / 2;
2676       std::__inplace_stable_sort(__first, __middle);
2677       std::__inplace_stable_sort(__middle, __last);
2678       std::__merge_without_buffer(__first, __middle, __last,
2679                                   __middle - __first,
2680                                   __last - __middle);
2681     }
2682
2683   /**
2684    *  @if maint
2685    *  This is a helper function for the stable sorting routines.
2686    *  @endif
2687   */
2688   template<typename _RandomAccessIterator, typename _Compare>
2689     void
2690     __inplace_stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last,
2691                           _Compare __comp)
2692     {
2693       if (__last - __first < 15) {
2694         std::__insertion_sort(__first, __last, __comp);
2695         return;
2696       }
2697       _RandomAccessIterator __middle = __first + (__last - __first) / 2;
2698       std::__inplace_stable_sort(__first, __middle, __comp);
2699       std::__inplace_stable_sort(__middle, __last, __comp);
2700       std::__merge_without_buffer(__first, __middle, __last,
2701                                   __middle - __first,
2702                                   __last - __middle,
2703                                   __comp);
2704     }
2705
2706   /**
2707    *  @brief Merges two sorted ranges.
2708    *  @param  first1  An iterator.
2709    *  @param  first2  Another iterator.
2710    *  @param  last1   Another iterator.
2711    *  @param  last2   Another iterator.
2712    *  @param  result  An iterator pointing to the end of the merged range.
2713    *  @return  An iterator pointing to the first element "not less than" @a val.
2714    *
2715    *  Merges the ranges [first1,last1) and [first2,last2) into the sorted range
2716    *  [result, result + (last1-first1) + (last2-first2)).  Both input ranges
2717    *  must be sorted, and the output range must not overlap with either of
2718    *  the input ranges.  The sort is @e stable, that is, for equivalent
2719    *  elements in the two ranges, elements from the first range will always
2720    *  come before elements from the second.
2721   */
2722   template<typename _InputIterator1, typename _InputIterator2, typename _OutputIterator>
2723     _OutputIterator
2724     merge(_InputIterator1 __first1, _InputIterator1 __last1,
2725           _InputIterator2 __first2, _InputIterator2 __last2,
2726           _OutputIterator __result)
2727     {
2728       // concept requirements
2729       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
2730       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
2731       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
2732             typename iterator_traits<_InputIterator1>::value_type>)
2733       __glibcxx_function_requires(_SameTypeConcept<
2734             typename iterator_traits<_InputIterator1>::value_type,
2735             typename iterator_traits<_InputIterator2>::value_type>)
2736       __glibcxx_function_requires(_LessThanComparableConcept<
2737             typename iterator_traits<_InputIterator1>::value_type>)
2738
2739       while (__first1 != __last1 && __first2 != __last2) {
2740         if (*__first2 < *__first1) {
2741           *__result = *__first2;
2742           ++__first2;
2743         }
2744         else {
2745           *__result = *__first1;
2746           ++__first1;
2747         }
2748         ++__result;
2749       }
2750       return std::copy(__first2, __last2, std::copy(__first1, __last1, __result));
2751     }
2752
2753   /**
2754    *  @brief Merges two sorted ranges.
2755    *  @param  first1  An iterator.
2756    *  @param  first2  Another iterator.
2757    *  @param  last1   Another iterator.
2758    *  @param  last2   Another iterator.
2759    *  @param  result  An iterator pointing to the end of the merged range.
2760    *  @param  comp    A functor to use for comparisons.
2761    *  @return  An iterator pointing to the first element "not less than" @a val.
2762    *
2763    *  Merges the ranges [first1,last1) and [first2,last2) into the sorted range
2764    *  [result, result + (last1-first1) + (last2-first2)).  Both input ranges
2765    *  must be sorted, and the output range must not overlap with either of
2766    *  the input ranges.  The sort is @e stable, that is, for equivalent
2767    *  elements in the two ranges, elements from the first range will always
2768    *  come before elements from the second.
2769    *
2770    *  The comparison function should have the same effects on ordering as
2771    *  the function used for the initial sort.
2772   */
2773   template<typename _InputIterator1, typename _InputIterator2, typename _OutputIterator,
2774            typename _Compare>
2775     _OutputIterator
2776     merge(_InputIterator1 __first1, _InputIterator1 __last1,
2777           _InputIterator2 __first2, _InputIterator2 __last2,
2778           _OutputIterator __result, _Compare __comp)
2779     {
2780       // concept requirements
2781       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
2782       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
2783       __glibcxx_function_requires(_SameTypeConcept<
2784             typename iterator_traits<_InputIterator1>::value_type,
2785             typename iterator_traits<_InputIterator2>::value_type>)
2786       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
2787             typename iterator_traits<_InputIterator1>::value_type>)
2788       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2789             typename iterator_traits<_InputIterator1>::value_type,
2790             typename iterator_traits<_InputIterator2>::value_type>)
2791
2792       while (__first1 != __last1 && __first2 != __last2) {
2793         if (__comp(*__first2, *__first1)) {
2794           *__result = *__first2;
2795           ++__first2;
2796         }
2797         else {
2798           *__result = *__first1;
2799           ++__first1;
2800         }
2801         ++__result;
2802       }
2803       return std::copy(__first2, __last2, std::copy(__first1, __last1, __result));
2804     }
2805
2806   template<typename _RandomAccessIterator1, typename _RandomAccessIterator2,
2807            typename _Distance>
2808     void
2809     __merge_sort_loop(_RandomAccessIterator1 __first, _RandomAccessIterator1 __last,
2810                       _RandomAccessIterator2 __result, _Distance __step_size)
2811     {
2812       _Distance __two_step = 2 * __step_size;
2813
2814       while (__last - __first >= __two_step) {
2815         __result = std::merge(__first, __first + __step_size,
2816                               __first + __step_size, __first + __two_step,
2817                               __result);
2818         __first += __two_step;
2819       }
2820
2821       __step_size = std::min(_Distance(__last - __first), __step_size);
2822       std::merge(__first, __first + __step_size, __first + __step_size, __last,
2823                  __result);
2824     }
2825
2826   template<typename _RandomAccessIterator1, typename _RandomAccessIterator2,
2827            typename _Distance, typename _Compare>
2828     void
2829     __merge_sort_loop(_RandomAccessIterator1 __first, _RandomAccessIterator1 __last,
2830                       _RandomAccessIterator2 __result, _Distance __step_size,
2831                       _Compare __comp)
2832     {
2833       _Distance __two_step = 2 * __step_size;
2834
2835       while (__last - __first >= __two_step) {
2836         __result = std::merge(__first, __first + __step_size,
2837                               __first + __step_size, __first + __two_step,
2838                               __result,
2839                               __comp);
2840         __first += __two_step;
2841       }
2842       __step_size = std::min(_Distance(__last - __first), __step_size);
2843
2844       std::merge(__first, __first + __step_size,
2845                  __first + __step_size, __last,
2846                  __result,
2847                  __comp);
2848     }
2849
2850   enum { _S_chunk_size = 7 };
2851
2852   template<typename _RandomAccessIterator, typename _Distance>
2853     void
2854     __chunk_insertion_sort(_RandomAccessIterator __first, _RandomAccessIterator __last,
2855                            _Distance __chunk_size)
2856     {
2857       while (__last - __first >= __chunk_size) {
2858         std::__insertion_sort(__first, __first + __chunk_size);
2859         __first += __chunk_size;
2860       }
2861       std::__insertion_sort(__first, __last);
2862     }
2863
2864   template<typename _RandomAccessIterator, typename _Distance, typename _Compare>
2865     void
2866     __chunk_insertion_sort(_RandomAccessIterator __first, _RandomAccessIterator __last,
2867                            _Distance __chunk_size, _Compare __comp)
2868     {
2869       while (__last - __first >= __chunk_size) {
2870         std::__insertion_sort(__first, __first + __chunk_size, __comp);
2871         __first += __chunk_size;
2872       }
2873       std::__insertion_sort(__first, __last, __comp);
2874     }
2875
2876   template<typename _RandomAccessIterator, typename _Pointer>
2877     void
2878     __merge_sort_with_buffer(_RandomAccessIterator __first, _RandomAccessIterator __last,
2879                              _Pointer __buffer)
2880     {
2881       typedef typename iterator_traits<_RandomAccessIterator>::difference_type _Distance;
2882
2883       _Distance __len = __last - __first;
2884       _Pointer __buffer_last = __buffer + __len;
2885
2886       _Distance __step_size = _S_chunk_size;
2887       std::__chunk_insertion_sort(__first, __last, __step_size);
2888
2889       while (__step_size < __len) {
2890         std::__merge_sort_loop(__first, __last, __buffer, __step_size);
2891         __step_size *= 2;
2892         std::__merge_sort_loop(__buffer, __buffer_last, __first, __step_size);
2893         __step_size *= 2;
2894       }
2895     }
2896
2897   template<typename _RandomAccessIterator, typename _Pointer, typename _Compare>
2898     void
2899     __merge_sort_with_buffer(_RandomAccessIterator __first, _RandomAccessIterator __last,
2900                              _Pointer __buffer, _Compare __comp)
2901     {
2902       typedef typename iterator_traits<_RandomAccessIterator>::difference_type _Distance;
2903
2904       _Distance __len = __last - __first;
2905       _Pointer __buffer_last = __buffer + __len;
2906
2907       _Distance __step_size = _S_chunk_size;
2908       std::__chunk_insertion_sort(__first, __last, __step_size, __comp);
2909
2910       while (__step_size < __len) {
2911         std::__merge_sort_loop(__first, __last, __buffer, __step_size, __comp);
2912         __step_size *= 2;
2913         std::__merge_sort_loop(__buffer, __buffer_last, __first, __step_size, __comp);
2914         __step_size *= 2;
2915       }
2916     }
2917
2918   /**
2919    *  @if maint
2920    *  This is a helper function for the merge routines.
2921    *  @endif
2922   */
2923   template<typename _BidirectionalIterator1, typename _BidirectionalIterator2,
2924            typename _BidirectionalIterator3>
2925     _BidirectionalIterator3
2926     __merge_backward(_BidirectionalIterator1 __first1, _BidirectionalIterator1 __last1,
2927                      _BidirectionalIterator2 __first2, _BidirectionalIterator2 __last2,
2928                      _BidirectionalIterator3 __result)
2929     {
2930       if (__first1 == __last1)
2931         return std::copy_backward(__first2, __last2, __result);
2932       if (__first2 == __last2)
2933         return std::copy_backward(__first1, __last1, __result);
2934       --__last1;
2935       --__last2;
2936       while (true) {
2937         if (*__last2 < *__last1) {
2938           *--__result = *__last1;
2939           if (__first1 == __last1)
2940             return std::copy_backward(__first2, ++__last2, __result);
2941           --__last1;
2942         }
2943         else {
2944           *--__result = *__last2;
2945           if (__first2 == __last2)
2946             return std::copy_backward(__first1, ++__last1, __result);
2947           --__last2;
2948         }
2949       }
2950     }
2951
2952   /**
2953    *  @if maint
2954    *  This is a helper function for the merge routines.
2955    *  @endif
2956   */
2957   template<typename _BidirectionalIterator1, typename _BidirectionalIterator2,
2958            typename _BidirectionalIterator3, typename _Compare>
2959     _BidirectionalIterator3
2960     __merge_backward(_BidirectionalIterator1 __first1, _BidirectionalIterator1 __last1,
2961                      _BidirectionalIterator2 __first2, _BidirectionalIterator2 __last2,
2962                      _BidirectionalIterator3 __result,
2963                      _Compare __comp)
2964     {
2965       if (__first1 == __last1)
2966         return std::copy_backward(__first2, __last2, __result);
2967       if (__first2 == __last2)
2968         return std::copy_backward(__first1, __last1, __result);
2969       --__last1;
2970       --__last2;
2971       while (true) {
2972         if (__comp(*__last2, *__last1)) {
2973           *--__result = *__last1;
2974           if (__first1 == __last1)
2975             return std::copy_backward(__first2, ++__last2, __result);
2976           --__last1;
2977         }
2978         else {
2979           *--__result = *__last2;
2980           if (__first2 == __last2)
2981             return std::copy_backward(__first1, ++__last1, __result);
2982           --__last2;
2983         }
2984       }
2985     }
2986
2987   /**
2988    *  @if maint
2989    *  This is a helper function for the merge routines.
2990    *  @endif
2991   */
2992   template<typename _BidirectionalIterator1, typename _BidirectionalIterator2,
2993            typename _Distance>
2994     _BidirectionalIterator1
2995     __rotate_adaptive(_BidirectionalIterator1 __first,
2996                       _BidirectionalIterator1 __middle,
2997                       _BidirectionalIterator1 __last,
2998                       _Distance __len1, _Distance __len2,
2999                       _BidirectionalIterator2 __buffer,
3000                       _Distance __buffer_size)
3001     {
3002       _BidirectionalIterator2 __buffer_end;
3003       if (__len1 > __len2 && __len2 <= __buffer_size) {
3004         __buffer_end = std::copy(__middle, __last, __buffer);
3005         std::copy_backward(__first, __middle, __last);
3006         return std::copy(__buffer, __buffer_end, __first);
3007       }
3008       else if (__len1 <= __buffer_size) {
3009         __buffer_end = std::copy(__first, __middle, __buffer);
3010         std::copy(__middle, __last, __first);
3011         return std::copy_backward(__buffer, __buffer_end, __last);
3012       }
3013       else {
3014         std::rotate(__first, __middle, __last);
3015         std::advance(__first, std::distance(__middle, __last));
3016         return __first;
3017       }
3018     }
3019
3020   /**
3021    *  @if maint
3022    *  This is a helper function for the merge routines.
3023    *  @endif
3024   */
3025   template<typename _BidirectionalIterator, typename _Distance, typename _Pointer>
3026     void
3027     __merge_adaptive(_BidirectionalIterator __first,
3028                      _BidirectionalIterator __middle,
3029                      _BidirectionalIterator __last,
3030                      _Distance __len1, _Distance __len2,
3031                      _Pointer __buffer, _Distance __buffer_size)
3032     {
3033           if (__len1 <= __len2 && __len1 <= __buffer_size) {
3034             _Pointer __buffer_end = std::copy(__first, __middle, __buffer);
3035             std::merge(__buffer, __buffer_end, __middle, __last, __first);
3036           }
3037           else if (__len2 <= __buffer_size) {
3038             _Pointer __buffer_end = std::copy(__middle, __last, __buffer);
3039             std::__merge_backward(__first, __middle, __buffer, __buffer_end, __last);
3040           }
3041           else {
3042             _BidirectionalIterator __first_cut = __first;
3043             _BidirectionalIterator __second_cut = __middle;
3044             _Distance __len11 = 0;
3045             _Distance __len22 = 0;
3046             if (__len1 > __len2) {
3047                   __len11 = __len1 / 2;
3048                   std::advance(__first_cut, __len11);
3049                   __second_cut = std::lower_bound(__middle, __last, *__first_cut);
3050                   __len22 = std::distance(__middle, __second_cut);
3051             }
3052             else {
3053                   __len22 = __len2 / 2;
3054                   std::advance(__second_cut, __len22);
3055                   __first_cut = std::upper_bound(__first, __middle, *__second_cut);
3056                   __len11 = std::distance(__first, __first_cut);
3057             }
3058             _BidirectionalIterator __new_middle =
3059                   std::__rotate_adaptive(__first_cut, __middle, __second_cut,
3060                                          __len1 - __len11, __len22, __buffer,
3061                                          __buffer_size);
3062             std::__merge_adaptive(__first, __first_cut, __new_middle, __len11,
3063                                   __len22, __buffer, __buffer_size);
3064             std::__merge_adaptive(__new_middle, __second_cut, __last, __len1 - __len11,
3065                                   __len2 - __len22, __buffer, __buffer_size);
3066           }
3067     }
3068
3069   /**
3070    *  @if maint
3071    *  This is a helper function for the merge routines.
3072    *  @endif
3073   */
3074   template<typename _BidirectionalIterator, typename _Distance, typename _Pointer,
3075            typename _Compare>
3076     void
3077     __merge_adaptive(_BidirectionalIterator __first,
3078                      _BidirectionalIterator __middle,
3079                      _BidirectionalIterator __last,
3080                      _Distance __len1, _Distance __len2,
3081                      _Pointer __buffer, _Distance __buffer_size,
3082                      _Compare __comp)
3083     {
3084           if (__len1 <= __len2 && __len1 <= __buffer_size) {
3085             _Pointer __buffer_end = std::copy(__first, __middle, __buffer);
3086             std::merge(__buffer, __buffer_end, __middle, __last, __first, __comp);
3087           }
3088           else if (__len2 <= __buffer_size) {
3089             _Pointer __buffer_end = std::copy(__middle, __last, __buffer);
3090             std::__merge_backward(__first, __middle, __buffer, __buffer_end, __last,
3091                                   __comp);
3092           }
3093           else {
3094             _BidirectionalIterator __first_cut = __first;
3095             _BidirectionalIterator __second_cut = __middle;
3096             _Distance __len11 = 0;
3097             _Distance __len22 = 0;
3098             if (__len1 > __len2) {
3099                   __len11 = __len1 / 2;
3100                   std::advance(__first_cut, __len11);
3101                   __second_cut = std::lower_bound(__middle, __last, *__first_cut, __comp);
3102                   __len22 = std::distance(__middle, __second_cut);
3103             }
3104             else {
3105                   __len22 = __len2 / 2;
3106                   std::advance(__second_cut, __len22);
3107                   __first_cut = std::upper_bound(__first, __middle, *__second_cut, __comp);
3108                   __len11 = std::distance(__first, __first_cut);
3109             }
3110             _BidirectionalIterator __new_middle =
3111                   std::__rotate_adaptive(__first_cut, __middle, __second_cut,
3112                                          __len1 - __len11, __len22, __buffer,
3113                                          __buffer_size);
3114             std::__merge_adaptive(__first, __first_cut, __new_middle, __len11,
3115                                   __len22, __buffer, __buffer_size, __comp);
3116             std::__merge_adaptive(__new_middle, __second_cut, __last, __len1 - __len11,
3117                                   __len2 - __len22, __buffer, __buffer_size, __comp);
3118           }
3119     }
3120
3121   /**
3122    *  @brief Merges two sorted ranges in place.
3123    *  @param  first   An iterator.
3124    *  @param  middle  Another iterator.
3125    *  @param  last    Another iterator.
3126    *  @return  Nothing.
3127    *
3128    *  Merges two sorted and consecutive ranges, [first,middle) and
3129    *  [middle,last), and puts the result in [first,last).  The output will
3130    *  be sorted.  The sort is @e stable, that is, for equivalent
3131    *  elements in the two ranges, elements from the first range will always
3132    *  come before elements from the second.
3133    *
3134    *  If enough additional memory is available, this takes (last-first)-1
3135    *  comparisons.  Otherwise an NlogN algorithm is used, where N is
3136    *  distance(first,last).
3137   */
3138   template<typename _BidirectionalIterator>
3139     void
3140     inplace_merge(_BidirectionalIterator __first,
3141                   _BidirectionalIterator __middle,
3142                   _BidirectionalIterator __last)
3143     {
3144       typedef typename iterator_traits<_BidirectionalIterator>::value_type
3145           _ValueType;
3146       typedef typename iterator_traits<_BidirectionalIterator>::difference_type
3147           _DistanceType;
3148
3149       // concept requirements
3150       __glibcxx_function_requires(_Mutable_BidirectionalIteratorConcept<
3151             _BidirectionalIterator>)
3152       __glibcxx_function_requires(_LessThanComparableConcept<_ValueType>)
3153
3154       if (__first == __middle || __middle == __last)
3155         return;
3156
3157       _DistanceType __len1 = std::distance(__first, __middle);
3158       _DistanceType __len2 = std::distance(__middle, __last);
3159
3160       _Temporary_buffer<_BidirectionalIterator, _ValueType> __buf(__first, __last);
3161       if (__buf.begin() == 0)
3162         std::__merge_without_buffer(__first, __middle, __last, __len1, __len2);
3163       else
3164         std::__merge_adaptive(__first, __middle, __last, __len1, __len2,
3165                               __buf.begin(), _DistanceType(__buf.size()));
3166     }
3167
3168   /**
3169    *  @brief Merges two sorted ranges in place.
3170    *  @param  first   An iterator.
3171    *  @param  middle  Another iterator.
3172    *  @param  last    Another iterator.
3173    *  @param  comp    A functor to use for comparisons.
3174    *  @return  Nothing.
3175    *
3176    *  Merges two sorted and consecutive ranges, [first,middle) and
3177    *  [middle,last), and puts the result in [first,last).  The output will
3178    *  be sorted.  The sort is @e stable, that is, for equivalent
3179    *  elements in the two ranges, elements from the first range will always
3180    *  come before elements from the second.
3181    *
3182    *  If enough additional memory is available, this takes (last-first)-1
3183    *  comparisons.  Otherwise an NlogN algorithm is used, where N is
3184    *  distance(first,last).
3185    *
3186    *  The comparison function should have the same effects on ordering as
3187    *  the function used for the initial sort.
3188   */
3189   template<typename _BidirectionalIterator, typename _Compare>
3190     void
3191     inplace_merge(_BidirectionalIterator __first,
3192                   _BidirectionalIterator __middle,
3193                   _BidirectionalIterator __last,
3194                   _Compare __comp)
3195     {
3196       typedef typename iterator_traits<_BidirectionalIterator>::value_type
3197           _ValueType;
3198       typedef typename iterator_traits<_BidirectionalIterator>::difference_type
3199           _DistanceType;
3200
3201       // concept requirements
3202       __glibcxx_function_requires(_Mutable_BidirectionalIteratorConcept<
3203             _BidirectionalIterator>)
3204       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
3205             _ValueType, _ValueType>)
3206
3207       if (__first == __middle || __middle == __last)
3208         return;
3209
3210       _DistanceType __len1 = std::distance(__first, __middle);
3211       _DistanceType __len2 = std::distance(__middle, __last);
3212
3213       _Temporary_buffer<_BidirectionalIterator, _ValueType> __buf(__first, __last);
3214       if (__buf.begin() == 0)
3215         std::__merge_without_buffer(__first, __middle, __last, __len1, __len2, __comp);
3216       else
3217         std::__merge_adaptive(__first, __middle, __last, __len1, __len2,
3218                               __buf.begin(), _DistanceType(__buf.size()),
3219                               __comp);
3220     }
3221
3222   template<typename _RandomAccessIterator, typename _Pointer, typename _Distance>
3223     void
3224     __stable_sort_adaptive(_RandomAccessIterator __first, _RandomAccessIterator __last,
3225                            _Pointer __buffer, _Distance __buffer_size)
3226     {
3227       _Distance __len = (__last - __first + 1) / 2;
3228       _RandomAccessIterator __middle = __first + __len;
3229       if (__len > __buffer_size) {
3230         std::__stable_sort_adaptive(__first, __middle, __buffer, __buffer_size);
3231         std::__stable_sort_adaptive(__middle, __last, __buffer, __buffer_size);
3232       }
3233       else {
3234         std::__merge_sort_with_buffer(__first, __middle, __buffer);
3235         std::__merge_sort_with_buffer(__middle, __last, __buffer);
3236       }
3237       std::__merge_adaptive(__first, __middle, __last, _Distance(__middle - __first),
3238                             _Distance(__last - __middle), __buffer, __buffer_size);
3239     }
3240
3241   template<typename _RandomAccessIterator, typename _Pointer, typename _Distance,
3242            typename _Compare>
3243     void
3244     __stable_sort_adaptive(_RandomAccessIterator __first, _RandomAccessIterator __last,
3245                            _Pointer __buffer, _Distance __buffer_size,
3246                            _Compare __comp)
3247     {
3248       _Distance __len = (__last - __first + 1) / 2;
3249       _RandomAccessIterator __middle = __first + __len;
3250       if (__len > __buffer_size) {
3251         std::__stable_sort_adaptive(__first, __middle, __buffer, __buffer_size,
3252                                     __comp);
3253         std::__stable_sort_adaptive(__middle, __last, __buffer, __buffer_size,
3254                                     __comp);
3255       }
3256       else {
3257         std::__merge_sort_with_buffer(__first, __middle, __buffer, __comp);
3258         std::__merge_sort_with_buffer(__middle, __last, __buffer, __comp);
3259       }
3260       std::__merge_adaptive(__first, __middle, __last, _Distance(__middle - __first),
3261                             _Distance(__last - __middle), __buffer, __buffer_size,
3262                             __comp);
3263     }
3264
3265   /**
3266    *  @brief Sort the elements of a sequence, preserving the relative order
3267    *         of equivalent elements.
3268    *  @param  first   An iterator.
3269    *  @param  last    Another iterator.
3270    *  @return  Nothing.
3271    *
3272    *  Sorts the elements in the range @p [first,last) in ascending order,
3273    *  such that @p *(i+1)<*i is false for each iterator @p i in the range
3274    *  @p [first,last-1).
3275    *
3276    *  The relative ordering of equivalent elements is preserved, so any two
3277    *  elements @p x and @p y in the range @p [first,last) such that
3278    *  @p x<y is false and @p y<x is false will have the same relative
3279    *  ordering after calling @p stable_sort().
3280   */
3281   template<typename _RandomAccessIterator>
3282     inline void
3283     stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last)
3284     {
3285       typedef typename iterator_traits<_RandomAccessIterator>::value_type _ValueType;
3286       typedef typename iterator_traits<_RandomAccessIterator>::difference_type _DistanceType;
3287
3288       // concept requirements
3289       __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
3290             _RandomAccessIterator>)
3291       __glibcxx_function_requires(_LessThanComparableConcept<_ValueType>)
3292
3293       _Temporary_buffer<_RandomAccessIterator, _ValueType> buf(__first, __last);
3294       if (buf.begin() == 0)
3295         std::__inplace_stable_sort(__first, __last);
3296       else
3297         std::__stable_sort_adaptive(__first, __last, buf.begin(), _DistanceType(buf.size()));
3298     }
3299
3300   /**
3301    *  @brief Sort the elements of a sequence using a predicate for comparison,
3302    *         preserving the relative order of equivalent elements.
3303    *  @param  first   An iterator.
3304    *  @param  last    Another iterator.
3305    *  @param  comp    A comparison functor.
3306    *  @return  Nothing.
3307    *
3308    *  Sorts the elements in the range @p [first,last) in ascending order,
3309    *  such that @p comp(*(i+1),*i) is false for each iterator @p i in the
3310    *  range @p [first,last-1).
3311    *
3312    *  The relative ordering of equivalent elements is preserved, so any two
3313    *  elements @p x and @p y in the range @p [first,last) such that
3314    *  @p comp(x,y) is false and @p comp(y,x) is false will have the same
3315    *  relative ordering after calling @p stable_sort().
3316   */
3317   template<typename _RandomAccessIterator, typename _Compare>
3318     inline void
3319     stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
3320     {
3321       typedef typename iterator_traits<_RandomAccessIterator>::value_type _ValueType;
3322       typedef typename iterator_traits<_RandomAccessIterator>::difference_type _DistanceType;
3323
3324       // concept requirements
3325       __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
3326             _RandomAccessIterator>)
3327       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
3328                                                           _ValueType, _ValueType>)
3329
3330       _Temporary_buffer<_RandomAccessIterator, _ValueType> buf(__first, __last);
3331       if (buf.begin() == 0)
3332         std::__inplace_stable_sort(__first, __last, __comp);
3333       else
3334         std::__stable_sort_adaptive(__first, __last, buf.begin(), _DistanceType(buf.size()),
3335                                     __comp);
3336     }
3337
3338   /**
3339    *  @brief Sort a sequence just enough to find a particular position.
3340    *  @param  first   An iterator.
3341    *  @param  nth     Another iterator.
3342    *  @param  last    Another iterator.
3343    *  @return  Nothing.
3344    *
3345    *  Rearranges the elements in the range @p [first,last) so that @p *nth
3346    *  is the same element that would have been in that position had the
3347    *  whole sequence been sorted.
3348    *  whole sequence been sorted. The elements either side of @p *nth are
3349    *  not completely sorted, but for any iterator @i in the range
3350    *  @p [first,nth) and any iterator @j in the range @p [nth,last) it
3351    *  holds that @p *j<*i is false.
3352   */
3353   template<typename _RandomAccessIterator>
3354     void
3355     nth_element(_RandomAccessIterator __first,
3356                 _RandomAccessIterator __nth,
3357                 _RandomAccessIterator __last)
3358     {
3359       typedef typename iterator_traits<_RandomAccessIterator>::value_type _ValueType;
3360
3361       // concept requirements
3362       __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<_RandomAccessIterator>)
3363       __glibcxx_function_requires(_LessThanComparableConcept<_ValueType>)
3364
3365       while (__last - __first > 3) {
3366         _RandomAccessIterator __cut =
3367           std::__unguarded_partition(__first, __last,
3368                                      _ValueType(std::__median(*__first,
3369                                                               *(__first + (__last - __first)/2),
3370                                                               *(__last - 1))));
3371         if (__cut <= __nth)
3372           __first = __cut;
3373         else
3374           __last = __cut;
3375       }
3376       std::__insertion_sort(__first, __last);
3377     }
3378
3379   /**
3380    *  @brief Sort a sequence just enough to find a particular position
3381    *         using a predicate for comparison.
3382    *  @param  first   An iterator.
3383    *  @param  nth     Another iterator.
3384    *  @param  last    Another iterator.
3385    *  @param  comp    A comparison functor.
3386    *  @return  Nothing.
3387    *
3388    *  Rearranges the elements in the range @p [first,last) so that @p *nth
3389    *  is the same element that would have been in that position had the
3390    *  whole sequence been sorted. The elements either side of @p *nth are
3391    *  not completely sorted, but for any iterator @i in the range
3392    *  @p [first,nth) and any iterator @j in the range @p [nth,last) it
3393    *  holds that @p comp(*j,*i) is false.
3394   */
3395   template<typename _RandomAccessIterator, typename _Compare>
3396     void
3397     nth_element(_RandomAccessIterator __first,
3398                 _RandomAccessIterator __nth,
3399                 _RandomAccessIterator __last,
3400                             _Compare __comp)
3401     {
3402       typedef typename iterator_traits<_RandomAccessIterator>::value_type _ValueType;
3403
3404       // concept requirements
3405       __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<_RandomAccessIterator>)
3406       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
3407                                   _ValueType, _ValueType>)
3408
3409       while (__last - __first > 3) {
3410         _RandomAccessIterator __cut =
3411           std::__unguarded_partition(__first, __last,
3412                                      _ValueType(std::__median(*__first,
3413                                                               *(__first + (__last - __first)/2),
3414                                                               *(__last - 1),
3415                                                               __comp)), __comp);
3416         if (__cut <= __nth)
3417           __first = __cut;
3418         else
3419           __last = __cut;
3420       }
3421       std::__insertion_sort(__first, __last, __comp);
3422     }
3423
3424   /**
3425    *  @brief Finds the largest subrange in which @a val could be inserted
3426    *         at any place in it without changing the ordering.
3427    *  @param  first   An iterator.
3428    *  @param  last    Another iterator.
3429    *  @param  val     The search term.
3430    *  @return  An pair of iterators defining the subrange.
3431    *  @ingroup binarysearch
3432    *
3433    *  This is equivalent to
3434    *  @code
3435    *    std::make_pair(lower_bound(first, last, val),
3436    *                   upper_bound(first, last, val))
3437    *  @endcode
3438    *  but does not actually call those functions.
3439   */
3440   template<typename _ForwardIterator, typename _Tp>
3441     pair<_ForwardIterator, _ForwardIterator>
3442     equal_range(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __val)
3443     {
3444       typedef typename iterator_traits<_ForwardIterator>::value_type _ValueType;
3445       typedef typename iterator_traits<_ForwardIterator>::difference_type _DistanceType;
3446
3447       // concept requirements
3448       // See comments on lower_bound.
3449       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
3450       __glibcxx_function_requires(_SameTypeConcept<_Tp, _ValueType>)
3451       __glibcxx_function_requires(_LessThanComparableConcept<_Tp>)
3452
3453       _DistanceType __len = std::distance(__first, __last);
3454       _DistanceType __half;
3455       _ForwardIterator __middle, __left, __right;
3456
3457       while (__len > 0) {
3458         __half = __len >> 1;
3459         __middle = __first;
3460         std::advance(__middle, __half);
3461         if (*__middle < __val) {
3462           __first = __middle;
3463           ++__first;
3464           __len = __len - __half - 1;
3465         }
3466         else if (__val < *__middle)
3467           __len = __half;
3468         else {
3469           __left = std::lower_bound(__first, __middle, __val);
3470           std::advance(__first, __len);
3471           __right = std::upper_bound(++__middle, __first, __val);
3472           return pair<_ForwardIterator, _ForwardIterator>(__left, __right);
3473         }
3474       }
3475       return pair<_ForwardIterator, _ForwardIterator>(__first, __first);
3476     }
3477
3478   /**
3479    *  @brief Finds the largest subrange in which @a val could be inserted
3480    *         at any place in it without changing the ordering.
3481    *  @param  first   An iterator.
3482    *  @param  last    Another iterator.
3483    *  @param  val     The search term.
3484    *  @param  comp    A functor to use for comparisons.
3485    *  @return  An pair of iterators defining the subrange.
3486    *  @ingroup binarysearch
3487    *
3488    *  This is equivalent to
3489    *  @code
3490    *    std::make_pair(lower_bound(first, last, val, comp),
3491    *                   upper_bound(first, last, val, comp))
3492    *  @endcode
3493    *  but does not actually call those functions.
3494   */
3495   template<typename _ForwardIterator, typename _Tp, typename _Compare>
3496     pair<_ForwardIterator, _ForwardIterator>
3497     equal_range(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __val,
3498                 _Compare __comp)
3499     {
3500       typedef typename iterator_traits<_ForwardIterator>::value_type _ValueType;
3501       typedef typename iterator_traits<_ForwardIterator>::difference_type _DistanceType;
3502
3503       // concept requirements
3504       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
3505       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, _ValueType, _Tp>)
3506       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, _Tp, _ValueType>)
3507
3508       _DistanceType __len = std::distance(__first, __last);
3509       _DistanceType __half;
3510       _ForwardIterator __middle, __left, __right;
3511
3512       while (__len > 0) {
3513         __half = __len >> 1;
3514         __middle = __first;
3515         std::advance(__middle, __half);
3516         if (__comp(*__middle, __val)) {
3517           __first = __middle;
3518           ++__first;
3519           __len = __len - __half - 1;
3520         }
3521         else if (__comp(__val, *__middle))
3522           __len = __half;
3523         else {
3524           __left = std::lower_bound(__first, __middle, __val, __comp);
3525           std::advance(__first, __len);
3526           __right = std::upper_bound(++__middle, __first, __val, __comp);
3527           return pair<_ForwardIterator, _ForwardIterator>(__left, __right);
3528         }
3529       }
3530       return pair<_ForwardIterator, _ForwardIterator>(__first, __first);
3531     }
3532
3533   /**
3534    *  @brief Determines whether an element exists in a range.
3535    *  @param  first   An iterator.
3536    *  @param  last    Another iterator.
3537    *  @param  val     The search term.
3538    *  @return  True if @a val (or its equivelent) is in [@a first,@a last ].
3539    *  @ingroup binarysearch
3540    *
3541    *  Note that this does not actually return an iterator to @a val.  For
3542    *  that, use std::find or a container's specialized find member functions.
3543   */
3544   template<typename _ForwardIterator, typename _Tp>
3545     bool
3546     binary_search(_ForwardIterator __first, _ForwardIterator __last,
3547                   const _Tp& __val)
3548     {
3549       // concept requirements
3550       // See comments on lower_bound.
3551       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
3552       __glibcxx_function_requires(_SameTypeConcept<_Tp,
3553                 typename iterator_traits<_ForwardIterator>::value_type>)
3554       __glibcxx_function_requires(_LessThanComparableConcept<_Tp>)
3555
3556       _ForwardIterator __i = std::lower_bound(__first, __last, __val);
3557       return __i != __last && !(__val < *__i);
3558     }
3559
3560   /**
3561    *  @brief Determines whether an element exists in a range.
3562    *  @param  first   An iterator.
3563    *  @param  last    Another iterator.
3564    *  @param  val     The search term.
3565    *  @param  comp    A functor to use for comparisons.
3566    *  @return  True if @a val (or its equivelent) is in [@a first,@a last ].
3567    *  @ingroup binarysearch
3568    *
3569    *  Note that this does not actually return an iterator to @a val.  For
3570    *  that, use std::find or a container's specialized find member functions.
3571    *
3572    *  The comparison function should have the same effects on ordering as
3573    *  the function used for the initial sort.
3574   */
3575   template<typename _ForwardIterator, typename _Tp, typename _Compare>
3576     bool
3577     binary_search(_ForwardIterator __first, _ForwardIterator __last,
3578                   const _Tp& __val, _Compare __comp)
3579     {
3580       // concept requirements
3581       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
3582       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
3583                 typename iterator_traits<_ForwardIterator>::value_type, _Tp>)
3584       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, _Tp,
3585                 typename iterator_traits<_ForwardIterator>::value_type>)
3586
3587       _ForwardIterator __i = std::lower_bound(__first, __last, __val, __comp);
3588       return __i != __last && !__comp(__val, *__i);
3589     }
3590
3591   // Set algorithms: includes, set_union, set_intersection, set_difference,
3592   // set_symmetric_difference.  All of these algorithms have the precondition
3593   // that their input ranges are sorted and the postcondition that their output
3594   // ranges are sorted.
3595
3596   /**
3597    *  @brief Determines whether all elements of a sequence exists in a range.
3598    *  @param  first1  Start of search range.
3599    *  @param  last1   End of search range.
3600    *  @param  first2  Start of sequence
3601    *  @param  last2   End of sequence.
3602    *  @return  True if each element in [first2,last2) is contained in order
3603    *  within [first1,last1).  False otherwise.
3604    *  @ingroup setoperations
3605    *
3606    *  This operation expects both [first1,last1) and [first2,last2) to be
3607    *  sorted.  Searches for the presence of each element in [first2,last2)
3608    *  within [first1,last1).  The iterators over each range only move forward,
3609    *  so this is a linear algorithm.  If an element in [first2,last2) is not
3610    *  found before the search iterator reaches @a last2, false is returned.
3611   */
3612   template<typename _InputIterator1, typename _InputIterator2>
3613     bool
3614     includes(_InputIterator1 __first1, _InputIterator1 __last1,
3615              _InputIterator2 __first2, _InputIterator2 __last2)
3616     {
3617       // concept requirements
3618       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
3619       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
3620       __glibcxx_function_requires(_SameTypeConcept<
3621             typename iterator_traits<_InputIterator1>::value_type,
3622             typename iterator_traits<_InputIterator2>::value_type>)
3623       __glibcxx_function_requires(_LessThanComparableConcept<
3624             typename iterator_traits<_InputIterator1>::value_type>)
3625
3626       while (__first1 != __last1 && __first2 != __last2)
3627         if (*__first2 < *__first1)
3628           return false;
3629         else if(*__first1 < *__first2)
3630           ++__first1;
3631         else
3632           ++__first1, ++__first2;
3633
3634       return __first2 == __last2;
3635     }
3636
3637   /**
3638    *  @brief Determines whether all elements of a sequence exists in a range
3639    *  using comparison.
3640    *  @param  first1  Start of search range.
3641    *  @param  last1   End of search range.
3642    *  @param  first2  Start of sequence
3643    *  @param  last2   End of sequence.
3644    *  @param  comp    Comparison function to use.
3645    *  @return  True if each element in [first2,last2) is contained in order
3646    *  within [first1,last1) according to comp.  False otherwise.
3647    *  @ingroup setoperations
3648    *
3649    *  This operation expects both [first1,last1) and [first2,last2) to be
3650    *  sorted.  Searches for the presence of each element in [first2,last2)
3651    *  within [first1,last1), using comp to decide.  The iterators over each
3652    *  range only move forward, so this is a linear algorithm.  If an element
3653    *  in [first2,last2) is not found before the search iterator reaches @a
3654    *  last2, false is returned.
3655   */
3656   template<typename _InputIterator1, typename _InputIterator2, typename _Compare>
3657     bool
3658     includes(_InputIterator1 __first1, _InputIterator1 __last1,
3659              _InputIterator2 __first2, _InputIterator2 __last2, _Compare __comp)
3660     {
3661       // concept requirements
3662       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
3663       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
3664       __glibcxx_function_requires(_SameTypeConcept<
3665             typename iterator_traits<_InputIterator1>::value_type,
3666             typename iterator_traits<_InputIterator2>::value_type>)
3667       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
3668             typename iterator_traits<_InputIterator1>::value_type,
3669             typename iterator_traits<_InputIterator2>::value_type>)
3670
3671       while (__first1 != __last1 && __first2 != __last2)
3672         if (__comp(*__first2, *__first1))
3673           return false;
3674         else if(__comp(*__first1, *__first2))
3675           ++__first1;
3676         else
3677           ++__first1, ++__first2;
3678
3679       return __first2 == __last2;
3680     }
3681
3682   /**
3683    *  @brief Return the union of two sorted ranges.
3684    *  @param  first1  Start of first range.
3685    *  @param  last1   End of first range.
3686    *  @param  first2  Start of second range.
3687    *  @param  last2   End of second range.
3688    *  @return  End of the output range.
3689    *  @ingroup setoperations
3690    *
3691    *  This operation iterates over both ranges, copying elements present in
3692    *  each range in order to the output range.  Iterators increment for each
3693    *  range.  When the current element of one range is less than the other,
3694    *  that element is copied and the iterator advanced.  If an element is
3695    *  contained in both ranges, the element from the first range is copied and
3696    *  both ranges advance.  The output range may not overlap either input
3697    *  range.
3698   */
3699   template<typename _InputIterator1, typename _InputIterator2, typename _OutputIterator>
3700     _OutputIterator
3701     set_union(_InputIterator1 __first1, _InputIterator1 __last1,
3702               _InputIterator2 __first2, _InputIterator2 __last2,
3703               _OutputIterator __result)
3704     {
3705       // concept requirements
3706       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
3707       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
3708       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
3709             typename iterator_traits<_InputIterator1>::value_type>)
3710       __glibcxx_function_requires(_SameTypeConcept<
3711             typename iterator_traits<_InputIterator1>::value_type,
3712             typename iterator_traits<_InputIterator2>::value_type>)
3713       __glibcxx_function_requires(_LessThanComparableConcept<
3714             typename iterator_traits<_InputIterator1>::value_type>)
3715
3716       while (__first1 != __last1 && __first2 != __last2) {
3717         if (*__first1 < *__first2) {
3718           *__result = *__first1;
3719           ++__first1;
3720         }
3721         else if (*__first2 < *__first1) {
3722           *__result = *__first2;
3723           ++__first2;
3724         }
3725         else {
3726           *__result = *__first1;
3727           ++__first1;
3728           ++__first2;
3729         }
3730         ++__result;
3731       }
3732       return std::copy(__first2, __last2, std::copy(__first1, __last1, __result));
3733     }
3734
3735   /**
3736    *  @brief Return the union of two sorted ranges using a comparison functor.
3737    *  @param  first1  Start of first range.
3738    *  @param  last1   End of first range.
3739    *  @param  first2  Start of second range.
3740    *  @param  last2   End of second range.
3741    *  @param  comp    The comparison functor.
3742    *  @return  End of the output range.
3743    *  @ingroup setoperations
3744    *
3745    *  This operation iterates over both ranges, copying elements present in
3746    *  each range in order to the output range.  Iterators increment for each
3747    *  range.  When the current element of one range is less than the other
3748    *  according to @a comp, that element is copied and the iterator advanced.
3749    *  If an equivalent element according to @a comp is contained in both
3750    *  ranges, the element from the first range is copied and both ranges
3751    *  advance.  The output range may not overlap either input range.
3752   */
3753   template<typename _InputIterator1, typename _InputIterator2, typename _OutputIterator,
3754            typename _Compare>
3755     _OutputIterator
3756     set_union(_InputIterator1 __first1, _InputIterator1 __last1,
3757               _InputIterator2 __first2, _InputIterator2 __last2,
3758               _OutputIterator __result, _Compare __comp)
3759     {
3760       // concept requirements
3761       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
3762       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
3763       __glibcxx_function_requires(_SameTypeConcept<
3764             typename iterator_traits<_InputIterator1>::value_type,
3765             typename iterator_traits<_InputIterator2>::value_type>)
3766       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
3767             typename iterator_traits<_InputIterator1>::value_type>)
3768       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
3769             typename iterator_traits<_InputIterator1>::value_type,
3770             typename iterator_traits<_InputIterator2>::value_type>)
3771
3772       while (__first1 != __last1 && __first2 != __last2) {
3773         if (__comp(*__first1, *__first2)) {
3774           *__result = *__first1;
3775           ++__first1;
3776         }
3777         else if (__comp(*__first2, *__first1)) {
3778           *__result = *__first2;
3779           ++__first2;
3780         }
3781         else {
3782           *__result = *__first1;
3783           ++__first1;
3784           ++__first2;
3785         }
3786         ++__result;
3787       }
3788       return std::copy(__first2, __last2, std::copy(__first1, __last1, __result));
3789     }
3790
3791   /**
3792    *  @brief Return the intersection of two sorted ranges.
3793    *  @param  first1  Start of first range.
3794    *  @param  last1   End of first range.
3795    *  @param  first2  Start of second range.
3796    *  @param  last2   End of second range.
3797    *  @return  End of the output range.
3798    *  @ingroup setoperations
3799    *
3800    *  This operation iterates over both ranges, copying elements present in
3801    *  both ranges in order to the output range.  Iterators increment for each
3802    *  range.  When the current element of one range is less than the other,
3803    *  that iterator advances.  If an element is contained in both ranges, the
3804    *  element from the first range is copied and both ranges advance.  The
3805    *  output range may not overlap either input range.
3806   */
3807   template<typename _InputIterator1, typename _InputIterator2, typename _OutputIterator>
3808     _OutputIterator
3809     set_intersection(_InputIterator1 __first1, _InputIterator1 __last1,
3810                      _InputIterator2 __first2, _InputIterator2 __last2,
3811                      _OutputIterator __result)
3812     {
3813       // concept requirements
3814       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
3815       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
3816       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
3817             typename iterator_traits<_InputIterator1>::value_type>)
3818       __glibcxx_function_requires(_SameTypeConcept<
3819             typename iterator_traits<_InputIterator1>::value_type,
3820             typename iterator_traits<_InputIterator2>::value_type>)
3821       __glibcxx_function_requires(_LessThanComparableConcept<
3822             typename iterator_traits<_InputIterator1>::value_type>)
3823
3824       while (__first1 != __last1 && __first2 != __last2)
3825         if (*__first1 < *__first2)
3826           ++__first1;
3827         else if (*__first2 < *__first1)
3828           ++__first2;
3829         else {
3830           *__result = *__first1;
3831           ++__first1;
3832           ++__first2;
3833           ++__result;
3834         }
3835       return __result;
3836     }
3837
3838   /**
3839    *  @brief Return the intersection of two sorted ranges using comparison
3840    *  functor.
3841    *  @param  first1  Start of first range.
3842    *  @param  last1   End of first range.
3843    *  @param  first2  Start of second range.
3844    *  @param  last2   End of second range.
3845    *  @param  comp    The comparison functor.
3846    *  @return  End of the output range.
3847    *  @ingroup setoperations
3848    *
3849    *  This operation iterates over both ranges, copying elements present in
3850    *  both ranges in order to the output range.  Iterators increment for each
3851    *  range.  When the current element of one range is less than the other
3852    *  according to @a comp, that iterator advances.  If an element is
3853    *  contained in both ranges according to @a comp, the element from the
3854    *  first range is copied and both ranges advance.  The output range may not
3855    *  overlap either input range.
3856   */
3857   template<typename _InputIterator1, typename _InputIterator2, typename _OutputIterator,
3858            typename _Compare>
3859     _OutputIterator
3860     set_intersection(_InputIterator1 __first1, _InputIterator1 __last1,
3861                      _InputIterator2 __first2, _InputIterator2 __last2,
3862                      _OutputIterator __result, _Compare __comp)
3863     {
3864       // concept requirements
3865       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
3866       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
3867       __glibcxx_function_requires(_SameTypeConcept<
3868             typename iterator_traits<_InputIterator1>::value_type,
3869             typename iterator_traits<_InputIterator2>::value_type>)
3870       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
3871             typename iterator_traits<_InputIterator1>::value_type>)
3872       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
3873             typename iterator_traits<_InputIterator1>::value_type,
3874             typename iterator_traits<_InputIterator2>::value_type>)
3875
3876       while (__first1 != __last1 && __first2 != __last2)
3877         if (__comp(*__first1, *__first2))
3878           ++__first1;
3879         else if (__comp(*__first2, *__first1))
3880           ++__first2;
3881         else {
3882           *__result = *__first1;
3883           ++__first1;
3884           ++__first2;
3885           ++__result;
3886         }
3887       return __result;
3888     }
3889
3890   /**
3891    *  @brief Return the difference of two sorted ranges.
3892    *  @param  first1  Start of first range.
3893    *  @param  last1   End of first range.
3894    *  @param  first2  Start of second range.
3895    *  @param  last2   End of second range.
3896    *  @return  End of the output range.
3897    *  @ingroup setoperations
3898    *
3899    *  This operation iterates over both ranges, copying elements present in
3900    *  the first range but not the second in order to the output range.
3901    *  Iterators increment for each range.  When the current element of the
3902    *  first range is less than the second, that element is copied and the
3903    *  iterator advances.  If the current element of the second range is less,
3904    *  the iterator advances, but no element is copied.  If an element is
3905    *  contained in both ranges, no elements are copied and both ranges
3906    *  advance.  The output range may not overlap either input range.
3907   */
3908   template<typename _InputIterator1, typename _InputIterator2, typename _OutputIterator>
3909     _OutputIterator
3910     set_difference(_InputIterator1 __first1, _InputIterator1 __last1,
3911                    _InputIterator2 __first2, _InputIterator2 __last2,
3912                    _OutputIterator __result)
3913     {
3914       // concept requirements
3915       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
3916       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
3917       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
3918             typename iterator_traits<_InputIterator1>::value_type>)
3919       __glibcxx_function_requires(_SameTypeConcept<
3920             typename iterator_traits<_InputIterator1>::value_type,
3921             typename iterator_traits<_InputIterator2>::value_type>)
3922       __glibcxx_function_requires(_LessThanComparableConcept<
3923             typename iterator_traits<_InputIterator1>::value_type>)
3924
3925       while (__first1 != __last1 && __first2 != __last2)
3926         if (*__first1 < *__first2) {
3927           *__result = *__first1;
3928           ++__first1;
3929           ++__result;
3930         }
3931         else if (*__first2 < *__first1)
3932           ++__first2;
3933         else {
3934           ++__first1;
3935           ++__first2;
3936         }
3937       return std::copy(__first1, __last1, __result);
3938     }
3939
3940   /**
3941    *  @brief  Return the difference of two sorted ranges using comparison
3942    *  functor.
3943    *  @param  first1  Start of first range.
3944    *  @param  last1   End of first range.
3945    *  @param  first2  Start of second range.
3946    *  @param  last2   End of second range.
3947    *  @param  comp    The comparison functor.
3948    *  @return  End of the output range.
3949    *  @ingroup setoperations
3950    *
3951    *  This operation iterates over both ranges, copying elements present in
3952    *  the first range but not the second in order to the output range.
3953    *  Iterators increment for each range.  When the current element of the
3954    *  first range is less than the second according to @a comp, that element
3955    *  is copied and the iterator advances.  If the current element of the
3956    *  second range is less, no element is copied and the iterator advances.
3957    *  If an element is contained in both ranges according to @a comp, no
3958    *  elements are copied and both ranges advance.  The output range may not
3959    *  overlap either input range.
3960   */
3961   template<typename _InputIterator1, typename _InputIterator2, typename _OutputIterator,
3962            typename _Compare>
3963     _OutputIterator
3964     set_difference(_InputIterator1 __first1, _InputIterator1 __last1,
3965                    _InputIterator2 __first2, _InputIterator2 __last2,
3966                    _OutputIterator __result, _Compare __comp)
3967     {
3968       // concept requirements
3969       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
3970       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
3971       __glibcxx_function_requires(_SameTypeConcept<
3972             typename iterator_traits<_InputIterator1>::value_type,
3973             typename iterator_traits<_InputIterator2>::value_type>)
3974       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
3975             typename iterator_traits<_InputIterator1>::value_type>)
3976       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
3977             typename iterator_traits<_InputIterator1>::value_type,
3978             typename iterator_traits<_InputIterator2>::value_type>)
3979
3980       while (__first1 != __last1 && __first2 != __last2)
3981         if (__comp(*__first1, *__first2)) {
3982           *__result = *__first1;
3983           ++__first1;
3984           ++__result;
3985         }
3986         else if (__comp(*__first2, *__first1))
3987           ++__first2;
3988         else {
3989           ++__first1;
3990           ++__first2;
3991         }
3992       return std::copy(__first1, __last1, __result);
3993     }
3994
3995   /**
3996    *  @brief  Return the symmetric difference of two sorted ranges.
3997    *  @param  first1  Start of first range.
3998    *  @param  last1   End of first range.
3999    *  @param  first2  Start of second range.
4000    *  @param  last2   End of second range.
4001    *  @return  End of the output range.
4002    *  @ingroup setoperations
4003    *
4004    *  This operation iterates over both ranges, copying elements present in
4005    *  one range but not the other in order to the output range.  Iterators
4006    *  increment for each range.  When the current element of one range is less
4007    *  than the other, that element is copied and the iterator advances.  If an
4008    *  element is contained in both ranges, no elements are copied and both
4009    *  ranges advance.  The output range may not overlap either input range.
4010   */
4011   template<typename _InputIterator1, typename _InputIterator2, typename _OutputIterator>
4012     _OutputIterator
4013     set_symmetric_difference(_InputIterator1 __first1, _InputIterator1 __last1,
4014                              _InputIterator2 __first2, _InputIterator2 __last2,
4015                              _OutputIterator __result)
4016     {
4017       // concept requirements
4018       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
4019       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
4020       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
4021             typename iterator_traits<_InputIterator1>::value_type>)
4022       __glibcxx_function_requires(_SameTypeConcept<
4023             typename iterator_traits<_InputIterator1>::value_type,
4024             typename iterator_traits<_InputIterator2>::value_type>)
4025       __glibcxx_function_requires(_LessThanComparableConcept<
4026             typename iterator_traits<_InputIterator1>::value_type>)
4027
4028       while (__first1 != __last1 && __first2 != __last2)
4029         if (*__first1 < *__first2) {
4030           *__result = *__first1;
4031           ++__first1;
4032           ++__result;
4033         }
4034         else if (*__first2 < *__first1) {
4035           *__result = *__first2;
4036           ++__first2;
4037           ++__result;
4038         }
4039         else {
4040           ++__first1;
4041           ++__first2;
4042         }
4043       return std::copy(__first2, __last2, std::copy(__first1, __last1, __result));
4044     }
4045
4046   /**
4047    *  @brief  Return the symmetric difference of two sorted ranges using
4048    *  comparison functor.
4049    *  @param  first1  Start of first range.
4050    *  @param  last1   End of first range.
4051    *  @param  first2  Start of second range.
4052    *  @param  last2   End of second range.
4053    *  @param  comp    The comparison functor.
4054    *  @return  End of the output range.
4055    *  @ingroup setoperations
4056    *
4057    *  This operation iterates over both ranges, copying elements present in
4058    *  one range but not the other in order to the output range.  Iterators
4059    *  increment for each range.  When the current element of one range is less
4060    *  than the other according to @a comp, that element is copied and the
4061    *  iterator advances.  If an element is contained in both ranges according
4062    *  to @a comp, no elements are copied and both ranges advance.  The output
4063    *  range may not overlap either input range.
4064   */
4065   template<typename _InputIterator1, typename _InputIterator2, typename _OutputIterator,
4066            typename _Compare>
4067     _OutputIterator
4068     set_symmetric_difference(_InputIterator1 __first1, _InputIterator1 __last1,
4069                              _InputIterator2 __first2, _InputIterator2 __last2,
4070                              _OutputIterator __result,
4071                              _Compare __comp)
4072     {
4073       // concept requirements
4074       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
4075       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
4076       __glibcxx_function_requires(_SameTypeConcept<
4077             typename iterator_traits<_InputIterator1>::value_type,
4078             typename iterator_traits<_InputIterator2>::value_type>)
4079       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
4080             typename iterator_traits<_InputIterator1>::value_type>)
4081       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
4082             typename iterator_traits<_InputIterator1>::value_type,
4083             typename iterator_traits<_InputIterator2>::value_type>)
4084
4085       while (__first1 != __last1 && __first2 != __last2)
4086         if (__comp(*__first1, *__first2)) {
4087           *__result = *__first1;
4088           ++__first1;
4089           ++__result;
4090         }
4091         else if (__comp(*__first2, *__first1)) {
4092           *__result = *__first2;
4093           ++__first2;
4094           ++__result;
4095         }
4096         else {
4097           ++__first1;
4098           ++__first2;
4099         }
4100       return std::copy(__first2, __last2, std::copy(__first1, __last1, __result));
4101     }
4102
4103   // min_element and max_element, with and without an explicitly supplied
4104   // comparison function.
4105
4106   /**
4107    *  @brief  Return the maximum element in a range.
4108    *  @param  first  Start of range.
4109    *  @param  last   End of range.
4110    *  @return  Iterator referencing the first instance of the largest value.
4111   */
4112   template<typename _ForwardIterator>
4113     _ForwardIterator
4114     max_element(_ForwardIterator __first, _ForwardIterator __last)
4115     {
4116       // concept requirements
4117       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
4118       __glibcxx_function_requires(_LessThanComparableConcept<
4119             typename iterator_traits<_ForwardIterator>::value_type>)
4120
4121       if (__first == __last) return __first;
4122       _ForwardIterator __result = __first;
4123       while (++__first != __last)
4124         if (*__result < *__first)
4125           __result = __first;
4126       return __result;
4127     }
4128
4129   /**
4130    *  @brief  Return the maximum element in a range using comparison functor.
4131    *  @param  first  Start of range.
4132    *  @param  last   End of range.
4133    *  @param  comp   Comparison functor.
4134    *  @return  Iterator referencing the first instance of the largest value
4135    *  according to comp.
4136   */
4137   template<typename _ForwardIterator, typename _Compare>
4138     _ForwardIterator
4139     max_element(_ForwardIterator __first, _ForwardIterator __last,
4140                 _Compare __comp)
4141     {
4142       // concept requirements
4143       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
4144       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
4145             typename iterator_traits<_ForwardIterator>::value_type,
4146             typename iterator_traits<_ForwardIterator>::value_type>)
4147
4148       if (__first == __last) return __first;
4149       _ForwardIterator __result = __first;
4150       while (++__first != __last)
4151         if (__comp(*__result, *__first)) __result = __first;
4152       return __result;
4153     }
4154
4155   /**
4156    *  @brief  Return the minimum element in a range.
4157    *  @param  first  Start of range.
4158    *  @param  last   End of range.
4159    *  @return  Iterator referencing the first instance of the smallest value.
4160   */
4161   template<typename _ForwardIterator>
4162     _ForwardIterator
4163     min_element(_ForwardIterator __first, _ForwardIterator __last)
4164     {
4165       // concept requirements
4166       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
4167       __glibcxx_function_requires(_LessThanComparableConcept<
4168             typename iterator_traits<_ForwardIterator>::value_type>)
4169
4170       if (__first == __last) return __first;
4171       _ForwardIterator __result = __first;
4172       while (++__first != __last)
4173         if (*__first < *__result)
4174           __result = __first;
4175       return __result;
4176     }
4177
4178   /**
4179    *  @brief  Return the minimum element in a range using comparison functor.
4180    *  @param  first  Start of range.
4181    *  @param  last   End of range.
4182    *  @param  comp   Comparison functor.
4183    *  @return  Iterator referencing the first instance of the smallest value
4184    *  according to comp.
4185   */
4186   template<typename _ForwardIterator, typename _Compare>
4187     _ForwardIterator
4188     min_element(_ForwardIterator __first, _ForwardIterator __last,
4189                 _Compare __comp)
4190     {
4191       // concept requirements
4192       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
4193       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
4194             typename iterator_traits<_ForwardIterator>::value_type,
4195             typename iterator_traits<_ForwardIterator>::value_type>)
4196
4197       if (__first == __last) return __first;
4198       _ForwardIterator __result = __first;
4199       while (++__first != __last)
4200         if (__comp(*__first, *__result))
4201           __result = __first;
4202       return __result;
4203     }
4204
4205   // next_permutation and prev_permutation, with and without an explicitly
4206   // supplied comparison function.
4207
4208   /**
4209    *  @brief  Permute range into the next "dictionary" ordering.
4210    *  @param  first  Start of range.
4211    *  @param  last   End of range.
4212    *  @return  False if wrapped to first permutation, true otherwise.
4213    *
4214    *  Treats all permutations of the range as a set of "dictionary" sorted
4215    *  sequences.  Permutes the current sequence into the next one of this set.
4216    *  Returns true if there are more sequences to generate.  If the sequence
4217    *  is the largest of the set, the smallest is generated and false returned.
4218   */
4219   template<typename _BidirectionalIterator>
4220     bool
4221     next_permutation(_BidirectionalIterator __first, _BidirectionalIterator __last)
4222     {
4223       // concept requirements
4224       __glibcxx_function_requires(_BidirectionalIteratorConcept<_BidirectionalIterator>)
4225       __glibcxx_function_requires(_LessThanComparableConcept<
4226             typename iterator_traits<_BidirectionalIterator>::value_type>)
4227
4228       if (__first == __last)
4229         return false;
4230       _BidirectionalIterator __i = __first;
4231       ++__i;
4232       if (__i == __last)
4233         return false;
4234       __i = __last;
4235       --__i;
4236
4237       for(;;) {
4238         _BidirectionalIterator __ii = __i;
4239         --__i;
4240         if (*__i < *__ii) {
4241           _BidirectionalIterator __j = __last;
4242           while (!(*__i < *--__j))
4243             {}
4244           std::iter_swap(__i, __j);
4245           std::reverse(__ii, __last);
4246           return true;
4247         }
4248         if (__i == __first) {
4249           std::reverse(__first, __last);
4250           return false;
4251         }
4252       }
4253     }
4254
4255   /**
4256    *  @brief  Permute range into the next "dictionary" ordering using
4257    *  comparison functor.
4258    *  @param  first  Start of range.
4259    *  @param  last   End of range.
4260    *  @param  comp
4261    *  @return  False if wrapped to first permutation, true otherwise.
4262    *
4263    *  Treats all permutations of the range [first,last) as a set of
4264    *  "dictionary" sorted sequences ordered by @a comp.  Permutes the current
4265    *  sequence into the next one of this set.  Returns true if there are more
4266    *  sequences to generate.  If the sequence is the largest of the set, the
4267    *  smallest is generated and false returned.
4268   */
4269   template<typename _BidirectionalIterator, typename _Compare>
4270     bool
4271     next_permutation(_BidirectionalIterator __first, _BidirectionalIterator __last,
4272                      _Compare __comp)
4273     {
4274       // concept requirements
4275       __glibcxx_function_requires(_BidirectionalIteratorConcept<_BidirectionalIterator>)
4276       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
4277             typename iterator_traits<_BidirectionalIterator>::value_type,
4278             typename iterator_traits<_BidirectionalIterator>::value_type>)
4279
4280       if (__first == __last)
4281         return false;
4282       _BidirectionalIterator __i = __first;
4283       ++__i;
4284       if (__i == __last)
4285         return false;
4286       __i = __last;
4287       --__i;
4288
4289       for(;;) {
4290         _BidirectionalIterator __ii = __i;
4291         --__i;
4292         if (__comp(*__i, *__ii)) {
4293           _BidirectionalIterator __j = __last;
4294           while (!__comp(*__i, *--__j))
4295             {}
4296           std::iter_swap(__i, __j);
4297           std::reverse(__ii, __last);
4298           return true;
4299         }
4300         if (__i == __first) {
4301           std::reverse(__first, __last);
4302           return false;
4303         }
4304       }
4305     }
4306
4307   /**
4308    *  @brief  Permute range into the previous "dictionary" ordering.
4309    *  @param  first  Start of range.
4310    *  @param  last   End of range.
4311    *  @return  False if wrapped to last permutation, true otherwise.
4312    *
4313    *  Treats all permutations of the range as a set of "dictionary" sorted
4314    *  sequences.  Permutes the current sequence into the previous one of this
4315    *  set.  Returns true if there are more sequences to generate.  If the
4316    *  sequence is the smallest of the set, the largest is generated and false
4317    *  returned.
4318   */
4319   template<typename _BidirectionalIterator>
4320     bool
4321     prev_permutation(_BidirectionalIterator __first, _BidirectionalIterator __last)
4322     {
4323       // concept requirements
4324       __glibcxx_function_requires(_BidirectionalIteratorConcept<_BidirectionalIterator>)
4325       __glibcxx_function_requires(_LessThanComparableConcept<
4326             typename iterator_traits<_BidirectionalIterator>::value_type>)
4327
4328       if (__first == __last)
4329         return false;
4330       _BidirectionalIterator __i = __first;
4331       ++__i;
4332       if (__i == __last)
4333         return false;
4334       __i = __last;
4335       --__i;
4336
4337       for(;;) {
4338         _BidirectionalIterator __ii = __i;
4339         --__i;
4340         if (*__ii < *__i) {
4341           _BidirectionalIterator __j = __last;
4342           while (!(*--__j < *__i))
4343             {}
4344           std::iter_swap(__i, __j);
4345           std::reverse(__ii, __last);
4346           return true;
4347         }
4348         if (__i == __first) {
4349           std::reverse(__first, __last);
4350           return false;
4351         }
4352       }
4353     }
4354
4355   /**
4356    *  @brief  Permute range into the previous "dictionary" ordering using
4357    *  comparison functor.
4358    *  @param  first  Start of range.
4359    *  @param  last   End of range.
4360    *  @param  comp
4361    *  @return  False if wrapped to last permutation, true otherwise.
4362    *
4363    *  Treats all permutations of the range [first,last) as a set of
4364    *  "dictionary" sorted sequences ordered by @a comp.  Permutes the current
4365    *  sequence into the previous one of this set.  Returns true if there are
4366    *  more sequences to generate.  If the sequence is the smallest of the set,
4367    *  the largest is generated and false returned.
4368   */
4369   template<typename _BidirectionalIterator, typename _Compare>
4370     bool
4371     prev_permutation(_BidirectionalIterator __first, _BidirectionalIterator __last,
4372                      _Compare __comp)
4373     {
4374       // concept requirements
4375       __glibcxx_function_requires(_BidirectionalIteratorConcept<_BidirectionalIterator>)
4376       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
4377             typename iterator_traits<_BidirectionalIterator>::value_type,
4378             typename iterator_traits<_BidirectionalIterator>::value_type>)
4379
4380       if (__first == __last)
4381         return false;
4382       _BidirectionalIterator __i = __first;
4383       ++__i;
4384       if (__i == __last)
4385         return false;
4386       __i = __last;
4387       --__i;
4388
4389       for(;;) {
4390         _BidirectionalIterator __ii = __i;
4391         --__i;
4392         if (__comp(*__ii, *__i)) {
4393           _BidirectionalIterator __j = __last;
4394           while (!__comp(*--__j, *__i))
4395             {}
4396           std::iter_swap(__i, __j);
4397           std::reverse(__ii, __last);
4398           return true;
4399         }
4400         if (__i == __first) {
4401           std::reverse(__first, __last);
4402           return false;
4403         }
4404       }
4405     }
4406
4407   // find_first_of, with and without an explicitly supplied comparison function.
4408
4409   /**
4410    *  @brief  Find element from a set in a sequence.
4411    *  @param  first1  Start of range to search.
4412    *  @param  last1   End of range to search.
4413    *  @param  first2  Start of match candidates.
4414    *  @param  last2   End of match candidates.
4415    *  @return   The first iterator @c i in the range
4416    *  @p [first1,last1) such that @c *i == @p *(i2) such that i2 is an
4417    *  interator in [first2,last2), or @p last1 if no such iterator exists.
4418    *
4419    *  Searches the range @p [first1,last1) for an element that is equal to
4420    *  some element in the range [first2,last2).  If found, returns an iterator
4421    *  in the range [first1,last1), otherwise returns @p last1.
4422   */
4423   template<typename _InputIterator, typename _ForwardIterator>
4424     _InputIterator
4425     find_first_of(_InputIterator __first1, _InputIterator __last1,
4426                   _ForwardIterator __first2, _ForwardIterator __last2)
4427     {
4428       // concept requirements
4429       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
4430       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
4431       __glibcxx_function_requires(_EqualOpConcept<
4432             typename iterator_traits<_InputIterator>::value_type,
4433             typename iterator_traits<_ForwardIterator>::value_type>)
4434
4435       for ( ; __first1 != __last1; ++__first1)
4436         for (_ForwardIterator __iter = __first2; __iter != __last2; ++__iter)
4437           if (*__first1 == *__iter)
4438             return __first1;
4439       return __last1;
4440     }
4441
4442   /**
4443    *  @brief  Find element from a set in a sequence using a predicate.
4444    *  @param  first1  Start of range to search.
4445    *  @param  last1   End of range to search.
4446    *  @param  first2  Start of match candidates.
4447    *  @param  last2   End of match candidates.
4448    *  @param  comp    Predicate to use.
4449    *  @return   The first iterator @c i in the range
4450    *  @p [first1,last1) such that @c comp(*i, @p *(i2)) is true and i2 is an
4451    *  interator in [first2,last2), or @p last1 if no such iterator exists.
4452    *
4453    *  Searches the range @p [first1,last1) for an element that is equal to
4454    *  some element in the range [first2,last2).  If found, returns an iterator in
4455    *  the range [first1,last1), otherwise returns @p last1.
4456   */
4457   template<typename _InputIterator, typename _ForwardIterator, typename _BinaryPredicate>
4458     _InputIterator
4459     find_first_of(_InputIterator __first1, _InputIterator __last1,
4460                   _ForwardIterator __first2, _ForwardIterator __last2,
4461                   _BinaryPredicate __comp)
4462     {
4463       // concept requirements
4464       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
4465       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
4466       __glibcxx_function_requires(_EqualOpConcept<
4467             typename iterator_traits<_InputIterator>::value_type,
4468             typename iterator_traits<_ForwardIterator>::value_type>)
4469       __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
4470             typename iterator_traits<_InputIterator>::value_type,
4471             typename iterator_traits<_ForwardIterator>::value_type>)
4472
4473       for ( ; __first1 != __last1; ++__first1)
4474         for (_ForwardIterator __iter = __first2; __iter != __last2; ++__iter)
4475           if (__comp(*__first1, *__iter))
4476             return __first1;
4477       return __last1;
4478     }
4479
4480
4481   // find_end, with and without an explicitly supplied comparison function.
4482   // Search [first2, last2) as a subsequence in [first1, last1), and return
4483   // the *last* possible match.  Note that find_end for bidirectional iterators
4484   // is much faster than for forward iterators.
4485
4486   // find_end for forward iterators.
4487   template<typename _ForwardIterator1, typename _ForwardIterator2>
4488     _ForwardIterator1
4489     __find_end(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
4490                _ForwardIterator2 __first2, _ForwardIterator2 __last2,
4491                forward_iterator_tag, forward_iterator_tag)
4492     {
4493       if (__first2 == __last2)
4494         return __last1;
4495       else {
4496         _ForwardIterator1 __result = __last1;
4497         while (1) {
4498           _ForwardIterator1 __new_result
4499             = std::search(__first1, __last1, __first2, __last2);
4500           if (__new_result == __last1)
4501             return __result;
4502           else {
4503             __result = __new_result;
4504             __first1 = __new_result;
4505             ++__first1;
4506           }
4507         }
4508       }
4509     }
4510
4511   template<typename _ForwardIterator1, typename _ForwardIterator2,
4512            typename _BinaryPredicate>
4513     _ForwardIterator1
4514     __find_end(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
4515                _ForwardIterator2 __first2, _ForwardIterator2 __last2,
4516                forward_iterator_tag, forward_iterator_tag,
4517                _BinaryPredicate __comp)
4518     {
4519       if (__first2 == __last2)
4520         return __last1;
4521       else {
4522         _ForwardIterator1 __result = __last1;
4523         while (1) {
4524           _ForwardIterator1 __new_result
4525             = std::search(__first1, __last1, __first2, __last2, __comp);
4526           if (__new_result == __last1)
4527             return __result;
4528           else {
4529             __result = __new_result;
4530             __first1 = __new_result;
4531             ++__first1;
4532           }
4533         }
4534       }
4535     }
4536
4537   // find_end for bidirectional iterators.  Requires partial specialization.
4538   template<typename _BidirectionalIterator1, typename _BidirectionalIterator2>
4539     _BidirectionalIterator1
4540     __find_end(_BidirectionalIterator1 __first1, _BidirectionalIterator1 __last1,
4541                _BidirectionalIterator2 __first2, _BidirectionalIterator2 __last2,
4542                bidirectional_iterator_tag, bidirectional_iterator_tag)
4543     {
4544       // concept requirements
4545       __glibcxx_function_requires(_BidirectionalIteratorConcept<_BidirectionalIterator1>)
4546       __glibcxx_function_requires(_BidirectionalIteratorConcept<_BidirectionalIterator2>)
4547
4548       typedef reverse_iterator<_BidirectionalIterator1> _RevIterator1;
4549       typedef reverse_iterator<_BidirectionalIterator2> _RevIterator2;
4550
4551       _RevIterator1 __rlast1(__first1);
4552       _RevIterator2 __rlast2(__first2);
4553       _RevIterator1 __rresult = std::search(_RevIterator1(__last1), __rlast1,
4554                                             _RevIterator2(__last2), __rlast2);
4555
4556       if (__rresult == __rlast1)
4557         return __last1;
4558       else {
4559         _BidirectionalIterator1 __result = __rresult.base();
4560         std::advance(__result, -std::distance(__first2, __last2));
4561         return __result;
4562       }
4563     }
4564
4565   template<typename _BidirectionalIterator1, typename _BidirectionalIterator2,
4566            typename _BinaryPredicate>
4567     _BidirectionalIterator1
4568     __find_end(_BidirectionalIterator1 __first1, _BidirectionalIterator1 __last1,
4569                _BidirectionalIterator2 __first2, _BidirectionalIterator2 __last2,
4570                bidirectional_iterator_tag, bidirectional_iterator_tag,
4571                _BinaryPredicate __comp)
4572     {
4573       // concept requirements
4574       __glibcxx_function_requires(_BidirectionalIteratorConcept<_BidirectionalIterator1>)
4575       __glibcxx_function_requires(_BidirectionalIteratorConcept<_BidirectionalIterator2>)
4576
4577       typedef reverse_iterator<_BidirectionalIterator1> _RevIterator1;
4578       typedef reverse_iterator<_BidirectionalIterator2> _RevIterator2;
4579
4580       _RevIterator1 __rlast1(__first1);
4581       _RevIterator2 __rlast2(__first2);
4582       _RevIterator1 __rresult = std::search(_RevIterator1(__last1), __rlast1,
4583                                             _RevIterator2(__last2), __rlast2,
4584                                             __comp);
4585
4586       if (__rresult == __rlast1)
4587         return __last1;
4588       else {
4589         _BidirectionalIterator1 __result = __rresult.base();
4590         std::advance(__result, -std::distance(__first2, __last2));
4591         return __result;
4592       }
4593     }
4594
4595   // Dispatching functions for find_end.
4596
4597   /**
4598    *  @brief  Find last matching subsequence in a sequence.
4599    *  @param  first1  Start of range to search.
4600    *  @param  last1   End of range to search.
4601    *  @param  first2  Start of sequence to match.
4602    *  @param  last2   End of sequence to match.
4603    *  @return   The last iterator @c i in the range
4604    *  @p [first1,last1-(last2-first2)) such that @c *(i+N) == @p *(first2+N)
4605    *  for each @c N in the range @p [0,last2-first2), or @p last1 if no
4606    *  such iterator exists.
4607    *
4608    *  Searches the range @p [first1,last1) for a sub-sequence that compares
4609    *  equal value-by-value with the sequence given by @p [first2,last2) and
4610    *  returns an iterator to the first element of the sub-sequence, or
4611    *  @p last1 if the sub-sequence is not found.  The sub-sequence will be the
4612    *  last such subsequence contained in [first,last1).
4613    *
4614    *  Because the sub-sequence must lie completely within the range
4615    *  @p [first1,last1) it must start at a position less than
4616    *  @p last1-(last2-first2) where @p last2-first2 is the length of the
4617    *  sub-sequence.
4618    *  This means that the returned iterator @c i will be in the range
4619    *  @p [first1,last1-(last2-first2))
4620   */
4621   template<typename _ForwardIterator1, typename _ForwardIterator2>
4622     inline _ForwardIterator1
4623     find_end(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
4624              _ForwardIterator2 __first2, _ForwardIterator2 __last2)
4625     {
4626       // concept requirements
4627       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator1>)
4628       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator2>)
4629       __glibcxx_function_requires(_EqualOpConcept<
4630             typename iterator_traits<_ForwardIterator1>::value_type,
4631             typename iterator_traits<_ForwardIterator2>::value_type>)
4632
4633       return std::__find_end(__first1, __last1, __first2, __last2,
4634                              std::__iterator_category(__first1),
4635                              std::__iterator_category(__first2));
4636     }
4637
4638   /**
4639    *  @brief  Find last matching subsequence in a sequence using a predicate.
4640    *  @param  first1  Start of range to search.
4641    *  @param  last1   End of range to search.
4642    *  @param  first2  Start of sequence to match.
4643    *  @param  last2   End of sequence to match.
4644    *  @param  comp    The predicate to use.
4645    *  @return   The last iterator @c i in the range
4646    *  @p [first1,last1-(last2-first2)) such that @c predicate(*(i+N), @p
4647    *  (first2+N)) is true for each @c N in the range @p [0,last2-first2), or
4648    *  @p last1 if no such iterator exists.
4649    *
4650    *  Searches the range @p [first1,last1) for a sub-sequence that compares
4651    *  equal value-by-value with the sequence given by @p [first2,last2) using
4652    *  comp as a predicate and returns an iterator to the first element of the
4653    *  sub-sequence, or @p last1 if the sub-sequence is not found.  The
4654    *  sub-sequence will be the last such subsequence contained in
4655    *  [first,last1).
4656    *
4657    *  Because the sub-sequence must lie completely within the range
4658    *  @p [first1,last1) it must start at a position less than
4659    *  @p last1-(last2-first2) where @p last2-first2 is the length of the
4660    *  sub-sequence.
4661    *  This means that the returned iterator @c i will be in the range
4662    *  @p [first1,last1-(last2-first2))
4663   */
4664   template<typename _ForwardIterator1, typename _ForwardIterator2,
4665            typename _BinaryPredicate>
4666     inline _ForwardIterator1
4667     find_end(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
4668              _ForwardIterator2 __first2, _ForwardIterator2 __last2,
4669              _BinaryPredicate __comp)
4670     {
4671       // concept requirements
4672       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator1>)
4673       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator2>)
4674       __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
4675             typename iterator_traits<_ForwardIterator1>::value_type,
4676             typename iterator_traits<_ForwardIterator2>::value_type>)
4677
4678       return std::__find_end(__first1, __last1, __first2, __last2,
4679                              std::__iterator_category(__first1),
4680                              std::__iterator_category(__first2),
4681                              __comp);
4682     }
4683
4684 } // namespace std
4685
4686 #endif /* _ALGO_H */
4687