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

   1 // Algorithm implementation -*- C++ -*-
   2
   3 // Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006, 2007
   4 // Free Software Foundation, Inc.
   5 //
   6 // This file is part of the GNU ISO C++ Library.  This library is free
   7 // software; you can redistribute it and/or modify it under the
   8 // terms of the GNU General Public License as published by the
   9 // Free Software Foundation; either version 2, or (at your option)
  10 // any later version.
  11
  12 // This library is distributed in the hope that it will be useful,
  13 // but WITHOUT ANY WARRANTY; without even the implied warranty of
  14 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  15 // GNU General Public License for more details.
  16
  17 // You should have received a copy of the GNU General Public License along
  18 // with this library; see the file COPYING.  If not, write to the Free
  19 // Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301,
  20 // USA.
  21
  22 // As a special exception, you may use this file as part of a free software
  23 // library without restriction.  Specifically, if other files instantiate
  24 // templates or use macros or inline functions from this file, or you compile
  25 // this file and link it with other files to produce an executable, this
  26 // file does not by itself cause the resulting executable to be covered by
  27 // the GNU General Public License.  This exception does not however
  28 // invalidate any other reasons why the executable file might be covered by
  29 // the GNU General Public License.
  30
  31 /*
  32  *
  33  * Copyright (c) 1994
  34  * Hewlett-Packard Company
  35  *
  36  * Permission to use, copy, modify, distribute and sell this software
  37  * and its documentation for any purpose is hereby granted without fee,
  38  * provided that the above copyright notice appear in all copies and
  39  * that both that copyright notice and this permission notice appear
  40  * in supporting documentation.  Hewlett-Packard Company makes no
  41  * representations about the suitability of this software for any
  42  * purpose.  It is provided "as is" without express or implied warranty.
  43  *
  44  *
  45  * Copyright (c) 1996
  46  * Silicon Graphics Computer Systems, Inc.
  47  *
  48  * Permission to use, copy, modify, distribute and sell this software
  49  * and its documentation for any purpose is hereby granted without fee,
  50  * provided that the above copyright notice appear in all copies and
  51  * that both that copyright notice and this permission notice appear
  52  * in supporting documentation.  Silicon Graphics makes no
  53  * representations about the suitability of this software for any
  54  * purpose.  It is provided "as is" without express or implied warranty.
  55  */
  56
  57 /** @file stl_algo.h
  58  *  This is an internal header file, included by other library headers.
  59  *  You should not attempt to use it directly.
  60  */
  61
  62 #ifndef _STL_ALGO_H
  63 #define _STL_ALGO_H 1
  64
  65 #include <cstdlib>             // for rand
  66 #include <bits/stl_heap.h>
  67 #include <bits/stl_tempbuf.h>  // for _Temporary_buffer
  68 #include <bits/algorithmfwd.h>
  69 #include <debug/debug.h>
  70
  71 // See concept_check.h for the __glibcxx_*_requires macros.
  72
  73 _GLIBCXX_BEGIN_NAMESPACE(std)
  74
  75   /**
  76    *  @brief Find the median of three values.
  77    *  @param  a  A value.
  78    *  @param  b  A value.
  79    *  @param  c  A value.
  80    *  @return One of @p a, @p b or @p c.
  81    *
  82    *  If @c {l,m,n} is some convolution of @p {a,b,c} such that @c l<=m<=n
  83    *  then the value returned will be @c m.
  84    *  This is an SGI extension.
  85    *  @ingroup SGIextensions
  86   */
  87   template<typename _Tp>
  88     inline const _Tp&
  89     __median(const _Tp& __a, const _Tp& __b, const _Tp& __c)
  90     {
  91       // concept requirements
  92       __glibcxx_function_requires(_LessThanComparableConcept<_Tp>)
  93       if (__a < __b)
  94         if (__b < __c)
  95           return __b;
  96         else if (__a < __c)
  97           return __c;
  98         else
  99           return __a;
 100       else if (__a < __c)
 101         return __a;
 102       else if (__b < __c)
 103         return __c;
 104       else
 105         return __b;
 106     }
 107
 108   /**
 109    *  @brief Find the median of three values using a predicate for comparison.
 110    *  @param  a     A value.
 111    *  @param  b     A value.
 112    *  @param  c     A value.
 113    *  @param  comp  A binary predicate.
 114    *  @return One of @p a, @p b or @p c.
 115    *
 116    *  If @c {l,m,n} is some convolution of @p {a,b,c} such that @p comp(l,m)
 117    *  and @p comp(m,n) are both true then the value returned will be @c m.
 118    *  This is an SGI extension.
 119    *  @ingroup SGIextensions
 120   */
 121   template<typename _Tp, typename _Compare>
 122     inline const _Tp&
 123     __median(const _Tp& __a, const _Tp& __b, const _Tp& __c, _Compare __comp)
 124     {
 125       // concept requirements
 126       __glibcxx_function_requires(_BinaryFunctionConcept<_Compare,bool,_Tp,_Tp>)
 127       if (__comp(__a, __b))
 128         if (__comp(__b, __c))
 129           return __b;
 130         else if (__comp(__a, __c))
 131           return __c;
 132         else
 133           return __a;
 134       else if (__comp(__a, __c))
 135         return __a;
 136       else if (__comp(__b, __c))
 137         return __c;
 138       else
 139         return __b;
 140     }
 141
 142   // for_each
 143
 144   /**
 145    *  @if maint
 146    *  This is an overload used by find() for the Input Iterator case.
 147    *  @endif
 148   */
 149   template<typename _InputIterator, typename _Tp>
 150     inline _InputIterator
 151     __find(_InputIterator __first, _InputIterator __last,
 152            const _Tp& __val, input_iterator_tag)
 153     {
 154       while (__first != __last && !(*__first == __val))
 155         ++__first;
 156       return __first;
 157     }
 158
 159   /**
 160    *  @if maint
 161    *  This is an overload used by find_if() for the Input Iterator case.
 162    *  @endif
 163   */
 164   template<typename _InputIterator, typename _Predicate>
 165     inline _InputIterator
 166     __find_if(_InputIterator __first, _InputIterator __last,
 167               _Predicate __pred, input_iterator_tag)
 168     {
 169       while (__first != __last && !bool(__pred(*__first)))
 170         ++__first;
 171       return __first;
 172     }
 173
 174   /**
 175    *  @if maint
 176    *  This is an overload used by find() for the RAI case.
 177    *  @endif
 178   */
 179   template<typename _RandomAccessIterator, typename _Tp>
 180     _RandomAccessIterator
 181     __find(_RandomAccessIterator __first, _RandomAccessIterator __last,
 182            const _Tp& __val, random_access_iterator_tag)
 183     {
 184       typename iterator_traits<_RandomAccessIterator>::difference_type
 185         __trip_count = (__last - __first) >> 2;
 186
 187       for (; __trip_count > 0; --__trip_count)
 188         {
 189           if (*__first == __val)
 190             return __first;
 191           ++__first;
 192
 193           if (*__first == __val)
 194             return __first;
 195           ++__first;
 196
 197           if (*__first == __val)
 198             return __first;
 199           ++__first;
 200
 201           if (*__first == __val)
 202             return __first;
 203           ++__first;
 204         }
 205
 206       switch (__last - __first)
 207         {
 208         case 3:
 209           if (*__first == __val)
 210             return __first;
 211           ++__first;
 212         case 2:
 213           if (*__first == __val)
 214             return __first;
 215           ++__first;
 216         case 1:
 217           if (*__first == __val)
 218             return __first;
 219           ++__first;
 220         case 0:
 221         default:
 222           return __last;
 223         }
 224     }
 225
 226   /**
 227    *  @if maint
 228    *  This is an overload used by find_if() for the RAI case.
 229    *  @endif
 230   */
 231   template<typename _RandomAccessIterator, typename _Predicate>
 232     _RandomAccessIterator
 233     __find_if(_RandomAccessIterator __first, _RandomAccessIterator __last,
 234               _Predicate __pred, random_access_iterator_tag)
 235     {
 236       typename iterator_traits<_RandomAccessIterator>::difference_type
 237         __trip_count = (__last - __first) >> 2;
 238
 239       for (; __trip_count > 0; --__trip_count)
 240         {
 241           if (__pred(*__first))
 242             return __first;
 243           ++__first;
 244
 245           if (__pred(*__first))
 246             return __first;
 247           ++__first;
 248
 249           if (__pred(*__first))
 250             return __first;
 251           ++__first;
 252
 253           if (__pred(*__first))
 254             return __first;
 255           ++__first;
 256         }
 257
 258       switch (__last - __first)
 259         {
 260         case 3:
 261           if (__pred(*__first))
 262             return __first;
 263           ++__first;
 264         case 2:
 265           if (__pred(*__first))
 266             return __first;
 267           ++__first;
 268         case 1:
 269           if (__pred(*__first))
 270             return __first;
 271           ++__first;
 272         case 0:
 273         default:
 274           return __last;
 275         }
 276     }
 277
 278   // set_difference
 279   // set_intersection
 280   // set_symmetric_difference
 281   // set_union
 282   // for_each
 283   // find
 284   // find_if
 285   // find_first_of
 286   // adjacent_find
 287   // count
 288   // count_if
 289   // search
 290
 291   /**
 292    *  @if maint
 293    *  This is an uglified
 294    *  search_n(_ForwardIterator, _ForwardIterator, _Integer, const _Tp&)
 295    *  overloaded for forward iterators.
 296    *  @endif
 297   */
 298   template<typename _ForwardIterator, typename _Integer, typename _Tp>
 299     _ForwardIterator
 300     __search_n(_ForwardIterator __first, _ForwardIterator __last,
 301                _Integer __count, const _Tp& __val,
 302                std::forward_iterator_tag)
 303     {
 304       __first = _GLIBCXX_STD_P::find(__first, __last, __val);
 305       while (__first != __last)
 306         {
 307           typename iterator_traits<_ForwardIterator>::difference_type
 308             __n = __count;
 309           _ForwardIterator __i = __first;
 310           ++__i;
 311           while (__i != __last && __n != 1 && *__i == __val)
 312             {
 313               ++__i;
 314               --__n;
 315             }
 316           if (__n == 1)
 317             return __first;
 318           if (__i == __last)
 319             return __last;
 320           __first = _GLIBCXX_STD_P::find(++__i, __last, __val);
 321         }
 322       return __last;
 323     }
 324
 325   /**
 326    *  @if maint
 327    *  This is an uglified
 328    *  search_n(_ForwardIterator, _ForwardIterator, _Integer, const _Tp&)
 329    *  overloaded for random access iterators.
 330    *  @endif
 331   */
 332   template<typename _RandomAccessIter, typename _Integer, typename _Tp>
 333     _RandomAccessIter
 334     __search_n(_RandomAccessIter __first, _RandomAccessIter __last,
 335                _Integer __count, const _Tp& __val,
 336                std::random_access_iterator_tag)
 337     {
 338
 339       typedef typename std::iterator_traits<_RandomAccessIter>::difference_type
 340         _DistanceType;
 341
 342       _DistanceType __tailSize = __last - __first;
 343       const _DistanceType __pattSize = __count;
 344
 345       if (__tailSize < __pattSize)
 346         return __last;
 347
 348       const _DistanceType __skipOffset = __pattSize - 1;
 349       _RandomAccessIter __lookAhead = __first + __skipOffset;
 350       __tailSize -= __pattSize;
 351
 352       while (1) // the main loop...
 353         {
 354           // __lookAhead here is always pointing to the last element of next
 355           // possible match.
 356           while (!(*__lookAhead == __val)) // the skip loop...
 357             {
 358               if (__tailSize < __pattSize)
 359                 return __last;  // Failure
 360               __lookAhead += __pattSize;
 361               __tailSize -= __pattSize;
 362             }
 363           _DistanceType __remainder = __skipOffset;
 364           for (_RandomAccessIter __backTrack = __lookAhead - 1;
 365                *__backTrack == __val; --__backTrack)
 366             {
 367               if (--__remainder == 0)
 368                 return (__lookAhead - __skipOffset); // Success
 369             }
 370           if (__remainder > __tailSize)
 371             return __last; // Failure
 372           __lookAhead += __remainder;
 373           __tailSize -= __remainder;
 374         }
 375     }
 376
 377   // search_n
 378
 379   /**
 380    *  @if maint
 381    *  This is an uglified
 382    *  search_n(_ForwardIterator, _ForwardIterator, _Integer, const _Tp&,
 383    *           _BinaryPredicate)
 384    *  overloaded for forward iterators.
 385    *  @endif
 386   */
 387   template<typename _ForwardIterator, typename _Integer, typename _Tp,
 388            typename _BinaryPredicate>
 389     _ForwardIterator
 390     __search_n(_ForwardIterator __first, _ForwardIterator __last,
 391                _Integer __count, const _Tp& __val,
 392                _BinaryPredicate __binary_pred, std::forward_iterator_tag)
 393     {
 394       while (__first != __last && !bool(__binary_pred(*__first, __val)))
 395         ++__first;
 396
 397       while (__first != __last)
 398         {
 399           typename iterator_traits<_ForwardIterator>::difference_type
 400             __n = __count;
 401           _ForwardIterator __i = __first;
 402           ++__i;
 403           while (__i != __last && __n != 1 && bool(__binary_pred(*__i, __val)))
 404             {
 405               ++__i;
 406               --__n;
 407             }
 408           if (__n == 1)
 409             return __first;
 410           if (__i == __last)
 411             return __last;
 412           __first = ++__i;
 413           while (__first != __last
 414                  && !bool(__binary_pred(*__first, __val)))
 415             ++__first;
 416         }
 417       return __last;
 418     }
 419
 420   /**
 421    *  @if maint
 422    *  This is an uglified
 423    *  search_n(_ForwardIterator, _ForwardIterator, _Integer, const _Tp&,
 424    *           _BinaryPredicate)
 425    *  overloaded for random access iterators.
 426    *  @endif
 427   */
 428   template<typename _RandomAccessIter, typename _Integer, typename _Tp,
 429            typename _BinaryPredicate>
 430     _RandomAccessIter
 431     __search_n(_RandomAccessIter __first, _RandomAccessIter __last,
 432                _Integer __count, const _Tp& __val,
 433                _BinaryPredicate __binary_pred, std::random_access_iterator_tag)
 434     {
 435
 436       typedef typename std::iterator_traits<_RandomAccessIter>::difference_type
 437         _DistanceType;
 438
 439       _DistanceType __tailSize = __last - __first;
 440       const _DistanceType __pattSize = __count;
 441
 442       if (__tailSize < __pattSize)
 443         return __last;
 444
 445       const _DistanceType __skipOffset = __pattSize - 1;
 446       _RandomAccessIter __lookAhead = __first + __skipOffset;
 447       __tailSize -= __pattSize;
 448
 449       while (1) // the main loop...
 450         {
 451           // __lookAhead here is always pointing to the last element of next
 452           // possible match.
 453           while (!bool(__binary_pred(*__lookAhead, __val))) // the skip loop...
 454             {
 455               if (__tailSize < __pattSize)
 456                 return __last;  // Failure
 457               __lookAhead += __pattSize;
 458               __tailSize -= __pattSize;
 459             }
 460           _DistanceType __remainder = __skipOffset;
 461           for (_RandomAccessIter __backTrack = __lookAhead - 1;
 462                __binary_pred(*__backTrack, __val); --__backTrack)
 463             {
 464               if (--__remainder == 0)
 465                 return (__lookAhead - __skipOffset); // Success
 466             }
 467           if (__remainder > __tailSize)
 468             return __last; // Failure
 469           __lookAhead += __remainder;
 470           __tailSize -= __remainder;
 471         }
 472     }
 473
 474   // find_end for forward iterators.
 475   template<typename _ForwardIterator1, typename _ForwardIterator2>
 476     _ForwardIterator1
 477     __find_end(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
 478                _ForwardIterator2 __first2, _ForwardIterator2 __last2,
 479                forward_iterator_tag, forward_iterator_tag)
 480     {
 481       if (__first2 == __last2)
 482         return __last1;
 483       else
 484         {
 485           _ForwardIterator1 __result = __last1;
 486           while (1)
 487             {
 488               _ForwardIterator1 __new_result
 489                 = _GLIBCXX_STD_P::search(__first1, __last1, __first2, __last2);
 490               if (__new_result == __last1)
 491                 return __result;
 492               else
 493                 {
 494                   __result = __new_result;
 495                   __first1 = __new_result;
 496                   ++__first1;
 497                 }
 498             }
 499         }
 500     }
 501
 502   template<typename _ForwardIterator1, typename _ForwardIterator2,
 503            typename _BinaryPredicate>
 504     _ForwardIterator1
 505     __find_end(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
 506                _ForwardIterator2 __first2, _ForwardIterator2 __last2,
 507                forward_iterator_tag, forward_iterator_tag,
 508                _BinaryPredicate __comp)
 509     {
 510       if (__first2 == __last2)
 511         return __last1;
 512       else
 513         {
 514           _ForwardIterator1 __result = __last1;
 515           while (1)
 516             {
 517               _ForwardIterator1 __new_result
 518                 = _GLIBCXX_STD_P::search(__first1, __last1, __first2, __last2, __comp);
 519               if (__new_result == __last1)
 520                 return __result;
 521               else
 522                 {
 523                   __result = __new_result;
 524                   __first1 = __new_result;
 525                   ++__first1;
 526                 }
 527             }
 528         }
 529     }
 530
 531   // find_end for bidirectional iterators (much faster).
 532   template<typename _BidirectionalIterator1, typename _BidirectionalIterator2>
 533     _BidirectionalIterator1
 534     __find_end(_BidirectionalIterator1 __first1,
 535                _BidirectionalIterator1 __last1,
 536                _BidirectionalIterator2 __first2,
 537                _BidirectionalIterator2 __last2,
 538                bidirectional_iterator_tag, bidirectional_iterator_tag)
 539     {
 540       // concept requirements
 541       __glibcxx_function_requires(_BidirectionalIteratorConcept<
 542                                   _BidirectionalIterator1>)
 543       __glibcxx_function_requires(_BidirectionalIteratorConcept<
 544                                   _BidirectionalIterator2>)
 545
 546       typedef reverse_iterator<_BidirectionalIterator1> _RevIterator1;
 547       typedef reverse_iterator<_BidirectionalIterator2> _RevIterator2;
 548
 549       _RevIterator1 __rlast1(__first1);
 550       _RevIterator2 __rlast2(__first2);
 551       _RevIterator1 __rresult = _GLIBCXX_STD_P::search(_RevIterator1(__last1), __rlast1, _RevIterator2(__last2), __rlast2);
 552
 553       if (__rresult == __rlast1)
 554         return __last1;
 555       else
 556         {
 557           _BidirectionalIterator1 __result = __rresult.base();
 558           std::advance(__result, -std::distance(__first2, __last2));
 559           return __result;
 560         }
 561     }
 562
 563   template<typename _BidirectionalIterator1, typename _BidirectionalIterator2,
 564            typename _BinaryPredicate>
 565     _BidirectionalIterator1
 566     __find_end(_BidirectionalIterator1 __first1,
 567                _BidirectionalIterator1 __last1,
 568                _BidirectionalIterator2 __first2,
 569                _BidirectionalIterator2 __last2,
 570                bidirectional_iterator_tag, bidirectional_iterator_tag,
 571                _BinaryPredicate __comp)
 572     {
 573       // concept requirements
 574       __glibcxx_function_requires(_BidirectionalIteratorConcept<
 575                                   _BidirectionalIterator1>)
 576       __glibcxx_function_requires(_BidirectionalIteratorConcept<
 577                                   _BidirectionalIterator2>)
 578
 579       typedef reverse_iterator<_BidirectionalIterator1> _RevIterator1;
 580       typedef reverse_iterator<_BidirectionalIterator2> _RevIterator2;
 581
 582       _RevIterator1 __rlast1(__first1);
 583       _RevIterator2 __rlast2(__first2);
 584       _RevIterator1 __rresult = std::search(_RevIterator1(__last1), __rlast1,
 585                                             _RevIterator2(__last2), __rlast2,
 586                                             __comp);
 587
 588       if (__rresult == __rlast1)
 589         return __last1;
 590       else
 591         {
 592           _BidirectionalIterator1 __result = __rresult.base();
 593           std::advance(__result, -std::distance(__first2, __last2));
 594           return __result;
 595         }
 596     }
 597
 598   /**
 599    *  @brief  Find last matching subsequence in a sequence.
 600    *  @param  first1  Start of range to search.
 601    *  @param  last1   End of range to search.
 602    *  @param  first2  Start of sequence to match.
 603    *  @param  last2   End of sequence to match.
 604    *  @return   The last iterator @c i in the range
 605    *  @p [first1,last1-(last2-first2)) such that @c *(i+N) == @p *(first2+N)
 606    *  for each @c N in the range @p [0,last2-first2), or @p last1 if no
 607    *  such iterator exists.
 608    *
 609    *  Searches the range @p [first1,last1) for a sub-sequence that compares
 610    *  equal value-by-value with the sequence given by @p [first2,last2) and
 611    *  returns an iterator to the first element of the sub-sequence, or
 612    *  @p last1 if the sub-sequence is not found.  The sub-sequence will be the
 613    *  last such subsequence contained in [first,last1).
 614    *
 615    *  Because the sub-sequence must lie completely within the range
 616    *  @p [first1,last1) it must start at a position less than
 617    *  @p last1-(last2-first2) where @p last2-first2 is the length of the
 618    *  sub-sequence.
 619    *  This means that the returned iterator @c i will be in the range
 620    *  @p [first1,last1-(last2-first2))
 621   */
 622   template<typename _ForwardIterator1, typename _ForwardIterator2>
 623     inline _ForwardIterator1
 624     find_end(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
 625              _ForwardIterator2 __first2, _ForwardIterator2 __last2)
 626     {
 627       // concept requirements
 628       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator1>)
 629       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator2>)
 630       __glibcxx_function_requires(_EqualOpConcept<
 631             typename iterator_traits<_ForwardIterator1>::value_type,
 632             typename iterator_traits<_ForwardIterator2>::value_type>)
 633       __glibcxx_requires_valid_range(__first1, __last1);
 634       __glibcxx_requires_valid_range(__first2, __last2);
 635
 636       return std::__find_end(__first1, __last1, __first2, __last2,
 637                              std::__iterator_category(__first1),
 638                              std::__iterator_category(__first2));
 639     }
 640
 641   /**
 642    *  @brief  Find last matching subsequence in a sequence using a predicate.
 643    *  @param  first1  Start of range to search.
 644    *  @param  last1   End of range to search.
 645    *  @param  first2  Start of sequence to match.
 646    *  @param  last2   End of sequence to match.
 647    *  @param  comp    The predicate to use.
 648    *  @return   The last iterator @c i in the range
 649    *  @p [first1,last1-(last2-first2)) such that @c predicate(*(i+N), @p
 650    *  (first2+N)) is true for each @c N in the range @p [0,last2-first2), or
 651    *  @p last1 if no such iterator exists.
 652    *
 653    *  Searches the range @p [first1,last1) for a sub-sequence that compares
 654    *  equal value-by-value with the sequence given by @p [first2,last2) using
 655    *  comp as a predicate and returns an iterator to the first element of the
 656    *  sub-sequence, or @p last1 if the sub-sequence is not found.  The
 657    *  sub-sequence will be the last such subsequence contained in
 658    *  [first,last1).
 659    *
 660    *  Because the sub-sequence must lie completely within the range
 661    *  @p [first1,last1) it must start at a position less than
 662    *  @p last1-(last2-first2) where @p last2-first2 is the length of the
 663    *  sub-sequence.
 664    *  This means that the returned iterator @c i will be in the range
 665    *  @p [first1,last1-(last2-first2))
 666   */
 667   template<typename _ForwardIterator1, typename _ForwardIterator2,
 668            typename _BinaryPredicate>
 669     inline _ForwardIterator1
 670     find_end(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
 671              _ForwardIterator2 __first2, _ForwardIterator2 __last2,
 672              _BinaryPredicate __comp)
 673     {
 674       // concept requirements
 675       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator1>)
 676       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator2>)
 677       __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
 678             typename iterator_traits<_ForwardIterator1>::value_type,
 679             typename iterator_traits<_ForwardIterator2>::value_type>)
 680       __glibcxx_requires_valid_range(__first1, __last1);
 681       __glibcxx_requires_valid_range(__first2, __last2);
 682
 683       return std::__find_end(__first1, __last1, __first2, __last2,
 684                              std::__iterator_category(__first1),
 685                              std::__iterator_category(__first2),
 686                              __comp);
 687     }
 688
 689
 690   /**
 691    *  @brief Copy a sequence, removing elements of a given value.
 692    *  @param  first   An input iterator.
 693    *  @param  last    An input iterator.
 694    *  @param  result  An output iterator.
 695    *  @param  value   The value to be removed.
 696    *  @return   An iterator designating the end of the resulting sequence.
 697    *
 698    *  Copies each element in the range @p [first,last) not equal to @p value
 699    *  to the range beginning at @p result.
 700    *  remove_copy() is stable, so the relative order of elements that are
 701    *  copied is unchanged.
 702   */
 703   template<typename _InputIterator, typename _OutputIterator, typename _Tp>
 704     _OutputIterator
 705     remove_copy(_InputIterator __first, _InputIterator __last,
 706                 _OutputIterator __result, const _Tp& __value)
 707     {
 708       // concept requirements
 709       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
 710       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
 711             typename iterator_traits<_InputIterator>::value_type>)
 712       __glibcxx_function_requires(_EqualOpConcept<
 713             typename iterator_traits<_InputIterator>::value_type, _Tp>)
 714       __glibcxx_requires_valid_range(__first, __last);
 715
 716       for (; __first != __last; ++__first)
 717         if (!(*__first == __value))
 718           {
 719             *__result = *__first;
 720             ++__result;
 721           }
 722       return __result;
 723     }
 724
 725   /**
 726    *  @brief Copy a sequence, removing elements for which a predicate is true.
 727    *  @param  first   An input iterator.
 728    *  @param  last    An input iterator.
 729    *  @param  result  An output iterator.
 730    *  @param  pred    A predicate.
 731    *  @return   An iterator designating the end of the resulting sequence.
 732    *
 733    *  Copies each element in the range @p [first,last) for which
 734    *  @p pred returns true to the range beginning at @p result.
 735    *
 736    *  remove_copy_if() is stable, so the relative order of elements that are
 737    *  copied is unchanged.
 738   */
 739   template<typename _InputIterator, typename _OutputIterator,
 740            typename _Predicate>
 741     _OutputIterator
 742     remove_copy_if(_InputIterator __first, _InputIterator __last,
 743                    _OutputIterator __result, _Predicate __pred)
 744     {
 745       // concept requirements
 746       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
 747       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
 748             typename iterator_traits<_InputIterator>::value_type>)
 749       __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
 750             typename iterator_traits<_InputIterator>::value_type>)
 751       __glibcxx_requires_valid_range(__first, __last);
 752
 753       for (; __first != __last; ++__first)
 754         if (!bool(__pred(*__first)))
 755           {
 756             *__result = *__first;
 757             ++__result;
 758           }
 759       return __result;
 760     }
 761
 762   /**
 763    *  @brief Remove elements from a sequence.
 764    *  @param  first  An input iterator.
 765    *  @param  last   An input iterator.
 766    *  @param  value  The value to be removed.
 767    *  @return   An iterator designating the end of the resulting sequence.
 768    *
 769    *  All elements equal to @p value are removed from the range
 770    *  @p [first,last).
 771    *
 772    *  remove() is stable, so the relative order of elements that are
 773    *  not removed is unchanged.
 774    *
 775    *  Elements between the end of the resulting sequence and @p last
 776    *  are still present, but their value is unspecified.
 777   */
 778   template<typename _ForwardIterator, typename _Tp>
 779     _ForwardIterator
 780     remove(_ForwardIterator __first, _ForwardIterator __last,
 781            const _Tp& __value)
 782     {
 783       // concept requirements
 784       __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
 785                                   _ForwardIterator>)
 786       __glibcxx_function_requires(_EqualOpConcept<
 787             typename iterator_traits<_ForwardIterator>::value_type, _Tp>)
 788       __glibcxx_requires_valid_range(__first, __last);
 789
 790       __first = _GLIBCXX_STD_P::find(__first, __last, __value);
 791       _ForwardIterator __i = __first;
 792       return __first == __last ? __first
 793                         : std::remove_copy(++__i, __last, __first, __value);
 794     }
 795
 796   /**
 797    *  @brief Remove elements from a sequence using a predicate.
 798    *  @param  first  A forward iterator.
 799    *  @param  last   A forward iterator.
 800    *  @param  pred   A predicate.
 801    *  @return   An iterator designating the end of the resulting sequence.
 802    *
 803    *  All elements for which @p pred returns true are removed from the range
 804    *  @p [first,last).
 805    *
 806    *  remove_if() is stable, so the relative order of elements that are
 807    *  not removed is unchanged.
 808    *
 809    *  Elements between the end of the resulting sequence and @p last
 810    *  are still present, but their value is unspecified.
 811   */
 812   template<typename _ForwardIterator, typename _Predicate>
 813     _ForwardIterator
 814     remove_if(_ForwardIterator __first, _ForwardIterator __last,
 815               _Predicate __pred)
 816     {
 817       // concept requirements
 818       __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
 819                                   _ForwardIterator>)
 820       __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
 821             typename iterator_traits<_ForwardIterator>::value_type>)
 822       __glibcxx_requires_valid_range(__first, __last);
 823
 824       __first = _GLIBCXX_STD_P::find_if(__first, __last, __pred);
 825       _ForwardIterator __i = __first;
 826       return __first == __last ? __first
 827                                : std::remove_copy_if(++__i, __last,
 828                                                      __first, __pred);
 829     }
 830
 831   /**
 832    *  @brief Remove consecutive duplicate values from a sequence.
 833    *  @param  first  A forward iterator.
 834    *  @param  last   A forward iterator.
 835    *  @return  An iterator designating the end of the resulting sequence.
 836    *
 837    *  Removes all but the first element from each group of consecutive
 838    *  values that compare equal.
 839    *  unique() is stable, so the relative order of elements that are
 840    *  not removed is unchanged.
 841    *  Elements between the end of the resulting sequence and @p last
 842    *  are still present, but their value is unspecified.
 843   */
 844   template<typename _ForwardIterator>
 845     _ForwardIterator
 846     unique(_ForwardIterator __first, _ForwardIterator __last)
 847     {
 848       // concept requirements
 849       __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
 850                                   _ForwardIterator>)
 851       __glibcxx_function_requires(_EqualityComparableConcept<
 852                      typename iterator_traits<_ForwardIterator>::value_type>)
 853       __glibcxx_requires_valid_range(__first, __last);
 854
 855       // Skip the beginning, if already unique.
 856       __first = _GLIBCXX_STD_P::adjacent_find(__first, __last);
 857       if (__first == __last)
 858         return __last;
 859
 860       // Do the real copy work.
 861       _ForwardIterator __dest = __first;
 862       ++__first;
 863       while (++__first != __last)
 864         if (!(*__dest == *__first))
 865           *++__dest = *__first;
 866       return ++__dest;
 867     }
 868
 869   /**
 870    *  @brief Remove consecutive values from a sequence using a predicate.
 871    *  @param  first        A forward iterator.
 872    *  @param  last         A forward iterator.
 873    *  @param  binary_pred  A binary predicate.
 874    *  @return  An iterator designating the end of the resulting sequence.
 875    *
 876    *  Removes all but the first element from each group of consecutive
 877    *  values for which @p binary_pred returns true.
 878    *  unique() is stable, so the relative order of elements that are
 879    *  not removed is unchanged.
 880    *  Elements between the end of the resulting sequence and @p last
 881    *  are still present, but their value is unspecified.
 882   */
 883   template<typename _ForwardIterator, typename _BinaryPredicate>
 884     _ForwardIterator
 885     unique(_ForwardIterator __first, _ForwardIterator __last,
 886            _BinaryPredicate __binary_pred)
 887     {
 888       // concept requirements
 889       __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
 890                                   _ForwardIterator>)
 891       __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
 892                 typename iterator_traits<_ForwardIterator>::value_type,
 893                 typename iterator_traits<_ForwardIterator>::value_type>)
 894       __glibcxx_requires_valid_range(__first, __last);
 895
 896       // Skip the beginning, if already unique.
 897       __first = _GLIBCXX_STD_P::adjacent_find(__first, __last, __binary_pred);
 898       if (__first == __last)
 899         return __last;
 900
 901       // Do the real copy work.
 902       _ForwardIterator __dest = __first;
 903       ++__first;
 904       while (++__first != __last)
 905         if (!bool(__binary_pred(*__dest, *__first)))
 906           *++__dest = *__first;
 907       return ++__dest;
 908     }
 909
 910   /**
 911    *  @if maint
 912    *  This is an uglified unique_copy(_InputIterator, _InputIterator,
 913    *                                  _OutputIterator)
 914    *  overloaded for forward iterators and output iterator as result.
 915    *  @endif
 916   */
 917   template<typename _ForwardIterator, typename _OutputIterator>
 918     _OutputIterator
 919     __unique_copy(_ForwardIterator __first, _ForwardIterator __last,
 920                   _OutputIterator __result,
 921                   forward_iterator_tag, output_iterator_tag)
 922     {
 923       // concept requirements -- taken care of in dispatching function
 924       _ForwardIterator __next = __first;
 925       *__result = *__first;
 926       while (++__next != __last)
 927         if (!(*__first == *__next))
 928           {
 929             __first = __next;
 930             *++__result = *__first;
 931           }
 932       return ++__result;
 933     }
 934
 935   /**
 936    *  @if maint
 937    *  This is an uglified unique_copy(_InputIterator, _InputIterator,
 938    *                                  _OutputIterator)
 939    *  overloaded for input iterators and output iterator as result.
 940    *  @endif
 941   */
 942   template<typename _InputIterator, typename _OutputIterator>
 943     _OutputIterator
 944     __unique_copy(_InputIterator __first, _InputIterator __last,
 945                   _OutputIterator __result,
 946                   input_iterator_tag, output_iterator_tag)
 947     {
 948       // concept requirements -- taken care of in dispatching function
 949       typename iterator_traits<_InputIterator>::value_type __value = *__first;
 950       *__result = __value;
 951       while (++__first != __last)
 952         if (!(__value == *__first))
 953           {
 954             __value = *__first;
 955             *++__result = __value;
 956           }
 957       return ++__result;
 958     }
 959
 960   /**
 961    *  @if maint
 962    *  This is an uglified unique_copy(_InputIterator, _InputIterator,
 963    *                                  _OutputIterator)
 964    *  overloaded for input iterators and forward iterator as result.
 965    *  @endif
 966   */
 967   template<typename _InputIterator, typename _ForwardIterator>
 968     _ForwardIterator
 969     __unique_copy(_InputIterator __first, _InputIterator __last,
 970                   _ForwardIterator __result,
 971                   input_iterator_tag, forward_iterator_tag)
 972     {
 973       // concept requirements -- taken care of in dispatching function
 974       *__result = *__first;
 975       while (++__first != __last)
 976         if (!(*__result == *__first))
 977           *++__result = *__first;
 978       return ++__result;
 979     }
 980
 981   /**
 982    *  @if maint
 983    *  This is an uglified
 984    *  unique_copy(_InputIterator, _InputIterator, _OutputIterator,
 985    *              _BinaryPredicate)
 986    *  overloaded for forward iterators and output iterator as result.
 987    *  @endif
 988   */
 989   template<typename _ForwardIterator, typename _OutputIterator,
 990            typename _BinaryPredicate>
 991     _OutputIterator
 992     __unique_copy(_ForwardIterator __first, _ForwardIterator __last,
 993                   _OutputIterator __result, _BinaryPredicate __binary_pred,
 994                   forward_iterator_tag, output_iterator_tag)
 995     {
 996       // concept requirements -- iterators already checked
 997       __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
 998           typename iterator_traits<_ForwardIterator>::value_type,
 999           typename iterator_traits<_ForwardIterator>::value_type>)
1000
1001       _ForwardIterator __next = __first;
1002       *__result = *__first;
1003       while (++__next != __last)
1004         if (!bool(__binary_pred(*__first, *__next)))
1005           {
1006             __first = __next;
1007             *++__result = *__first;
1008           }
1009       return ++__result;
1010     }
1011
1012   /**
1013    *  @if maint
1014    *  This is an uglified
1015    *  unique_copy(_InputIterator, _InputIterator, _OutputIterator,
1016    *              _BinaryPredicate)
1017    *  overloaded for input iterators and output iterator as result.
1018    *  @endif
1019   */
1020   template<typename _InputIterator, typename _OutputIterator,
1021            typename _BinaryPredicate>
1022     _OutputIterator
1023     __unique_copy(_InputIterator __first, _InputIterator __last,
1024                   _OutputIterator __result, _BinaryPredicate __binary_pred,
1025                   input_iterator_tag, output_iterator_tag)
1026     {
1027       // concept requirements -- iterators already checked
1028       __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
1029           typename iterator_traits<_InputIterator>::value_type,
1030           typename iterator_traits<_InputIterator>::value_type>)
1031
1032       typename iterator_traits<_InputIterator>::value_type __value = *__first;
1033       *__result = __value;
1034       while (++__first != __last)
1035         if (!bool(__binary_pred(__value, *__first)))
1036           {
1037             __value = *__first;
1038             *++__result = __value;
1039           }
1040       return ++__result;
1041     }
1042
1043   /**
1044    *  @if maint
1045    *  This is an uglified
1046    *  unique_copy(_InputIterator, _InputIterator, _OutputIterator,
1047    *              _BinaryPredicate)
1048    *  overloaded for input iterators and forward iterator as result.
1049    *  @endif
1050   */
1051   template<typename _InputIterator, typename _ForwardIterator,
1052            typename _BinaryPredicate>
1053     _ForwardIterator
1054     __unique_copy(_InputIterator __first, _InputIterator __last,
1055                   _ForwardIterator __result, _BinaryPredicate __binary_pred,
1056                   input_iterator_tag, forward_iterator_tag)
1057     {
1058       // concept requirements -- iterators already checked
1059       __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
1060           typename iterator_traits<_ForwardIterator>::value_type,
1061           typename iterator_traits<_InputIterator>::value_type>)
1062
1063       *__result = *__first;
1064       while (++__first != __last)
1065         if (!bool(__binary_pred(*__result, *__first)))
1066           *++__result = *__first;
1067       return ++__result;
1068     }
1069
1070   /**
1071    *  @if maint
1072    *  This is an uglified reverse(_BidirectionalIterator,
1073    *                              _BidirectionalIterator)
1074    *  overloaded for bidirectional iterators.
1075    *  @endif
1076   */
1077   template<typename _BidirectionalIterator>
1078     void
1079     __reverse(_BidirectionalIterator __first, _BidirectionalIterator __last,
1080               bidirectional_iterator_tag)
1081     {
1082       while (true)
1083         if (__first == __last || __first == --__last)
1084           return;
1085         else
1086           {
1087             std::iter_swap(__first, __last);
1088             ++__first;
1089           }
1090     }
1091
1092   /**
1093    *  @if maint
1094    *  This is an uglified reverse(_BidirectionalIterator,
1095    *                              _BidirectionalIterator)
1096    *  overloaded for random access iterators.
1097    *  @endif
1098   */
1099   template<typename _RandomAccessIterator>
1100     void
1101     __reverse(_RandomAccessIterator __first, _RandomAccessIterator __last,
1102               random_access_iterator_tag)
1103     {
1104       if (__first == __last)
1105         return;
1106       --__last;
1107       while (__first < __last)
1108         {
1109           std::iter_swap(__first, __last);
1110           ++__first;
1111           --__last;
1112         }
1113     }
1114
1115   /**
1116    *  @brief Reverse a sequence.
1117    *  @param  first  A bidirectional iterator.
1118    *  @param  last   A bidirectional iterator.
1119    *  @return   reverse() returns no value.
1120    *
1121    *  Reverses the order of the elements in the range @p [first,last),
1122    *  so that the first element becomes the last etc.
1123    *  For every @c i such that @p 0<=i<=(last-first)/2), @p reverse()
1124    *  swaps @p *(first+i) and @p *(last-(i+1))
1125   */
1126   template<typename _BidirectionalIterator>
1127     inline void
1128     reverse(_BidirectionalIterator __first, _BidirectionalIterator __last)
1129     {
1130       // concept requirements
1131       __glibcxx_function_requires(_Mutable_BidirectionalIteratorConcept<
1132                                   _BidirectionalIterator>)
1133       __glibcxx_requires_valid_range(__first, __last);
1134       std::__reverse(__first, __last, std::__iterator_category(__first));
1135     }
1136
1137   /**
1138    *  @brief Copy a sequence, reversing its elements.
1139    *  @param  first   A bidirectional iterator.
1140    *  @param  last    A bidirectional iterator.
1141    *  @param  result  An output iterator.
1142    *  @return  An iterator designating the end of the resulting sequence.
1143    *
1144    *  Copies the elements in the range @p [first,last) to the range
1145    *  @p [result,result+(last-first)) such that the order of the
1146    *  elements is reversed.
1147    *  For every @c i such that @p 0<=i<=(last-first), @p reverse_copy()
1148    *  performs the assignment @p *(result+(last-first)-i) = *(first+i).
1149    *  The ranges @p [first,last) and @p [result,result+(last-first))
1150    *  must not overlap.
1151   */
1152   template<typename _BidirectionalIterator, typename _OutputIterator>
1153     _OutputIterator
1154     reverse_copy(_BidirectionalIterator __first, _BidirectionalIterator __last,
1155                              _OutputIterator __result)
1156     {
1157       // concept requirements
1158       __glibcxx_function_requires(_BidirectionalIteratorConcept<
1159                                   _BidirectionalIterator>)
1160       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
1161                 typename iterator_traits<_BidirectionalIterator>::value_type>)
1162       __glibcxx_requires_valid_range(__first, __last);
1163
1164       while (__first != __last)
1165         {
1166           --__last;
1167           *__result = *__last;
1168           ++__result;
1169         }
1170       return __result;
1171     }
1172
1173   /**
1174    *  @if maint
1175    *  This is a helper function for the rotate algorithm specialized on RAIs.
1176    *  It returns the greatest common divisor of two integer values.
1177    *  @endif
1178   */
1179   template<typename _EuclideanRingElement>
1180     _EuclideanRingElement
1181     __gcd(_EuclideanRingElement __m, _EuclideanRingElement __n)
1182     {
1183       while (__n != 0)
1184         {
1185           _EuclideanRingElement __t = __m % __n;
1186           __m = __n;
1187           __n = __t;
1188         }
1189       return __m;
1190     }
1191
1192   /**
1193    *  @if maint
1194    *  This is a helper function for the rotate algorithm.
1195    *  @endif
1196   */
1197   template<typename _ForwardIterator>
1198     void
1199     __rotate(_ForwardIterator __first,
1200              _ForwardIterator __middle,
1201              _ForwardIterator __last,
1202              forward_iterator_tag)
1203     {
1204       if (__first == __middle || __last  == __middle)
1205         return;
1206
1207       _ForwardIterator __first2 = __middle;
1208       do
1209         {
1210           swap(*__first, *__first2);
1211           ++__first;
1212           ++__first2;
1213           if (__first == __middle)
1214             __middle = __first2;
1215         }
1216       while (__first2 != __last);
1217
1218       __first2 = __middle;
1219
1220       while (__first2 != __last)
1221         {
1222           swap(*__first, *__first2);
1223           ++__first;
1224           ++__first2;
1225           if (__first == __middle)
1226             __middle = __first2;
1227           else if (__first2 == __last)
1228             __first2 = __middle;
1229         }
1230     }
1231
1232   /**
1233    *  @if maint
1234    *  This is a helper function for the rotate algorithm.
1235    *  @endif
1236   */
1237   template<typename _BidirectionalIterator>
1238     void
1239     __rotate(_BidirectionalIterator __first,
1240              _BidirectionalIterator __middle,
1241              _BidirectionalIterator __last,
1242               bidirectional_iterator_tag)
1243     {
1244       // concept requirements
1245       __glibcxx_function_requires(_Mutable_BidirectionalIteratorConcept<
1246                                   _BidirectionalIterator>)
1247
1248       if (__first == __middle || __last  == __middle)
1249         return;
1250
1251       std::__reverse(__first,  __middle, bidirectional_iterator_tag());
1252       std::__reverse(__middle, __last,   bidirectional_iterator_tag());
1253
1254       while (__first != __middle && __middle != __last)
1255         {
1256           swap(*__first, *--__last);
1257           ++__first;
1258         }
1259
1260       if (__first == __middle)
1261         std::__reverse(__middle, __last,   bidirectional_iterator_tag());
1262       else
1263         std::__reverse(__first,  __middle, bidirectional_iterator_tag());
1264     }
1265
1266   /**
1267    *  @if maint
1268    *  This is a helper function for the rotate algorithm.
1269    *  @endif
1270   */
1271   template<typename _RandomAccessIterator>
1272     void
1273     __rotate(_RandomAccessIterator __first,
1274              _RandomAccessIterator __middle,
1275              _RandomAccessIterator __last,
1276              random_access_iterator_tag)
1277     {
1278       // concept requirements
1279       __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
1280                                   _RandomAccessIterator>)
1281
1282       if (__first == __middle || __last  == __middle)
1283         return;
1284
1285       typedef typename iterator_traits<_RandomAccessIterator>::difference_type
1286         _Distance;
1287       typedef typename iterator_traits<_RandomAccessIterator>::value_type
1288         _ValueType;
1289
1290       const _Distance __n = __last   - __first;
1291       const _Distance __k = __middle - __first;
1292       const _Distance __l = __n - __k;
1293
1294       if (__k == __l)
1295         {
1296           std::swap_ranges(__first, __middle, __middle);
1297           return;
1298         }
1299
1300       const _Distance __d = std::__gcd(__n, __k);
1301
1302       for (_Distance __i = 0; __i < __d; __i++)
1303         {
1304           _ValueType __tmp = *__first;
1305           _RandomAccessIterator __p = __first;
1306
1307           if (__k < __l)
1308             {
1309               for (_Distance __j = 0; __j < __l / __d; __j++)
1310                 {
1311                   if (__p > __first + __l)
1312                     {
1313                       *__p = *(__p - __l);
1314                       __p -= __l;
1315                     }
1316
1317                   *__p = *(__p + __k);
1318                   __p += __k;
1319                 }
1320             }
1321           else
1322             {
1323               for (_Distance __j = 0; __j < __k / __d - 1; __j ++)
1324                 {
1325                   if (__p < __last - __k)
1326                     {
1327                       *__p = *(__p + __k);
1328                       __p += __k;
1329                     }
1330                   *__p = * (__p - __l);
1331                   __p -= __l;
1332                 }
1333             }
1334
1335           *__p = __tmp;
1336           ++__first;
1337         }
1338     }
1339
1340   /**
1341    *  @brief Rotate the elements of a sequence.
1342    *  @param  first   A forward iterator.
1343    *  @param  middle  A forward iterator.
1344    *  @param  last    A forward iterator.
1345    *  @return  Nothing.
1346    *
1347    *  Rotates the elements of the range @p [first,last) by @p (middle-first)
1348    *  positions so that the element at @p middle is moved to @p first, the
1349    *  element at @p middle+1 is moved to @first+1 and so on for each element
1350    *  in the range @p [first,last).
1351    *
1352    *  This effectively swaps the ranges @p [first,middle) and
1353    *  @p [middle,last).
1354    *
1355    *  Performs @p *(first+(n+(last-middle))%(last-first))=*(first+n) for
1356    *  each @p n in the range @p [0,last-first).
1357   */
1358   template<typename _ForwardIterator>
1359     inline void
1360     rotate(_ForwardIterator __first, _ForwardIterator __middle,
1361            _ForwardIterator __last)
1362     {
1363       // concept requirements
1364       __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
1365                                   _ForwardIterator>)
1366       __glibcxx_requires_valid_range(__first, __middle);
1367       __glibcxx_requires_valid_range(__middle, __last);
1368
1369       typedef typename iterator_traits<_ForwardIterator>::iterator_category
1370         _IterType;
1371       std::__rotate(__first, __middle, __last, _IterType());
1372     }
1373
1374   /**
1375    *  @brief Copy a sequence, rotating its elements.
1376    *  @param  first   A forward iterator.
1377    *  @param  middle  A forward iterator.
1378    *  @param  last    A forward iterator.
1379    *  @param  result  An output iterator.
1380    *  @return   An iterator designating the end of the resulting sequence.
1381    *
1382    *  Copies the elements of the range @p [first,last) to the range
1383    *  beginning at @result, rotating the copied elements by @p (middle-first)
1384    *  positions so that the element at @p middle is moved to @p result, the
1385    *  element at @p middle+1 is moved to @result+1 and so on for each element
1386    *  in the range @p [first,last).
1387    *
1388    *  Performs @p *(result+(n+(last-middle))%(last-first))=*(first+n) for
1389    *  each @p n in the range @p [0,last-first).
1390   */
1391   template<typename _ForwardIterator, typename _OutputIterator>
1392     _OutputIterator
1393     rotate_copy(_ForwardIterator __first, _ForwardIterator __middle,
1394                 _ForwardIterator __last, _OutputIterator __result)
1395     {
1396       // concept requirements
1397       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
1398       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
1399                 typename iterator_traits<_ForwardIterator>::value_type>)
1400       __glibcxx_requires_valid_range(__first, __middle);
1401       __glibcxx_requires_valid_range(__middle, __last);
1402
1403       return std::copy(__first, __middle,
1404                        std::copy(__middle, __last, __result));
1405     }
1406
1407   /**
1408    *  @if maint
1409    *  This is a helper function...
1410    *  @endif
1411   */
1412   template<typename _ForwardIterator, typename _Predicate>
1413     _ForwardIterator
1414     __partition(_ForwardIterator __first, _ForwardIterator __last,
1415                 _Predicate __pred,
1416                 forward_iterator_tag)
1417     {
1418       if (__first == __last)
1419         return __first;
1420
1421       while (__pred(*__first))
1422         if (++__first == __last)
1423           return __first;
1424
1425       _ForwardIterator __next = __first;
1426
1427       while (++__next != __last)
1428         if (__pred(*__next))
1429           {
1430             swap(*__first, *__next);
1431             ++__first;
1432           }
1433
1434       return __first;
1435     }
1436
1437   /**
1438    *  @if maint
1439    *  This is a helper function...
1440    *  @endif
1441   */
1442   template<typename _BidirectionalIterator, typename _Predicate>
1443     _BidirectionalIterator
1444     __partition(_BidirectionalIterator __first, _BidirectionalIterator __last,
1445                 _Predicate __pred,
1446                 bidirectional_iterator_tag)
1447     {
1448       while (true)
1449         {
1450           while (true)
1451             if (__first == __last)
1452               return __first;
1453             else if (__pred(*__first))
1454               ++__first;
1455             else
1456               break;
1457           --__last;
1458           while (true)
1459             if (__first == __last)
1460               return __first;
1461             else if (!bool(__pred(*__last)))
1462               --__last;
1463             else
1464               break;
1465           std::iter_swap(__first, __last);
1466           ++__first;
1467         }
1468     }
1469
1470   // partition
1471
1472   /**
1473    *  @if maint
1474    *  This is a helper function...
1475    *  @endif
1476   */
1477   template<typename _ForwardIterator, typename _Predicate, typename _Distance>
1478     _ForwardIterator
1479     __inplace_stable_partition(_ForwardIterator __first,
1480                                _ForwardIterator __last,
1481                                _Predicate __pred, _Distance __len)
1482     {
1483       if (__len == 1)
1484         return __pred(*__first) ? __last : __first;
1485       _ForwardIterator __middle = __first;
1486       std::advance(__middle, __len / 2);
1487       _ForwardIterator __begin = std::__inplace_stable_partition(__first,
1488                                                                  __middle,
1489                                                                  __pred,
1490                                                                  __len / 2);
1491       _ForwardIterator __end = std::__inplace_stable_partition(__middle, __last,
1492                                                                __pred,
1493                                                                __len
1494                                                                - __len / 2);
1495       std::rotate(__begin, __middle, __end);
1496       std::advance(__begin, std::distance(__middle, __end));
1497       return __begin;
1498     }
1499
1500   /**
1501    *  @if maint
1502    *  This is a helper function...
1503    *  @endif
1504   */
1505   template<typename _ForwardIterator, typename _Pointer, typename _Predicate,
1506            typename _Distance>
1507     _ForwardIterator
1508     __stable_partition_adaptive(_ForwardIterator __first,
1509                                 _ForwardIterator __last,
1510                                 _Predicate __pred, _Distance __len,
1511                                 _Pointer __buffer,
1512                                 _Distance __buffer_size)
1513     {
1514       if (__len <= __buffer_size)
1515         {
1516           _ForwardIterator __result1 = __first;
1517           _Pointer __result2 = __buffer;
1518           for (; __first != __last; ++__first)
1519             if (__pred(*__first))
1520               {
1521                 *__result1 = *__first;
1522                 ++__result1;
1523               }
1524             else
1525               {
1526                 *__result2 = *__first;
1527                 ++__result2;
1528               }
1529           std::copy(__buffer, __result2, __result1);
1530           return __result1;
1531         }
1532       else
1533         {
1534           _ForwardIterator __middle = __first;
1535           std::advance(__middle, __len / 2);
1536           _ForwardIterator __begin =
1537             std::__stable_partition_adaptive(__first, __middle, __pred,
1538                                              __len / 2, __buffer,
1539                                              __buffer_size);
1540           _ForwardIterator __end =
1541             std::__stable_partition_adaptive(__middle, __last, __pred,
1542                                              __len - __len / 2,
1543                                              __buffer, __buffer_size);
1544           std::rotate(__begin, __middle, __end);
1545           std::advance(__begin, std::distance(__middle, __end));
1546           return __begin;
1547         }
1548     }
1549
1550   /**
1551    *  @brief Move elements for which a predicate is true to the beginning
1552    *         of a sequence, preserving relative ordering.
1553    *  @param  first   A forward iterator.
1554    *  @param  last    A forward iterator.
1555    *  @param  pred    A predicate functor.
1556    *  @return  An iterator @p middle such that @p pred(i) is true for each
1557    *  iterator @p i in the range @p [first,middle) and false for each @p i
1558    *  in the range @p [middle,last).
1559    *
1560    *  Performs the same function as @p partition() with the additional
1561    *  guarantee that the relative ordering of elements in each group is
1562    *  preserved, so any two elements @p x and @p y in the range
1563    *  @p [first,last) such that @p pred(x)==pred(y) will have the same
1564    *  relative ordering after calling @p stable_partition().
1565   */
1566   template<typename _ForwardIterator, typename _Predicate>
1567     _ForwardIterator
1568     stable_partition(_ForwardIterator __first, _ForwardIterator __last,
1569                      _Predicate __pred)
1570     {
1571       // concept requirements
1572       __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
1573                                   _ForwardIterator>)
1574       __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
1575             typename iterator_traits<_ForwardIterator>::value_type>)
1576       __glibcxx_requires_valid_range(__first, __last);
1577
1578       if (__first == __last)
1579         return __first;
1580       else
1581         {
1582           typedef typename iterator_traits<_ForwardIterator>::value_type
1583             _ValueType;
1584           typedef typename iterator_traits<_ForwardIterator>::difference_type
1585             _DistanceType;
1586
1587           _Temporary_buffer<_ForwardIterator, _ValueType> __buf(__first,
1588                                                                 __last);
1589         if (__buf.size() > 0)
1590           return
1591             std::__stable_partition_adaptive(__first, __last, __pred,
1592                                           _DistanceType(__buf.requested_size()),
1593                                           __buf.begin(),
1594                                           _DistanceType(__buf.size()));
1595         else
1596           return
1597             std::__inplace_stable_partition(__first, __last, __pred,
1598                                          _DistanceType(__buf.requested_size()));
1599         }
1600     }
1601
1602   /**
1603    *  @if maint
1604    *  This is a helper function for the sort routines.
1605    *  @endif
1606   */
1607   template<typename _RandomAccessIterator>
1608     void
1609     __heap_select(_RandomAccessIterator __first,
1610                   _RandomAccessIterator __middle,
1611                   _RandomAccessIterator __last)
1612     {
1613       typedef typename iterator_traits<_RandomAccessIterator>::value_type
1614         _ValueType;
1615
1616       std::make_heap(__first, __middle);
1617       for (_RandomAccessIterator __i = __middle; __i < __last; ++__i)
1618         if (*__i < *__first)
1619           std::__pop_heap(__first, __middle, __i, _ValueType(*__i));
1620     }
1621
1622   /**
1623    *  @if maint
1624    *  This is a helper function for the sort routines.
1625    *  @endif
1626   */
1627   template<typename _RandomAccessIterator, typename _Compare>
1628     void
1629     __heap_select(_RandomAccessIterator __first,
1630                   _RandomAccessIterator __middle,
1631                   _RandomAccessIterator __last, _Compare __comp)
1632     {
1633       typedef typename iterator_traits<_RandomAccessIterator>::value_type
1634         _ValueType;
1635
1636       std::make_heap(__first, __middle, __comp);
1637       for (_RandomAccessIterator __i = __middle; __i < __last; ++__i)
1638         if (__comp(*__i, *__first))
1639           std::__pop_heap(__first, __middle, __i, _ValueType(*__i), __comp);
1640     }
1641
1642   // partial_sort
1643
1644   /**
1645    *  @brief Copy the smallest elements of a sequence.
1646    *  @param  first   An iterator.
1647    *  @param  last    Another iterator.
1648    *  @param  result_first   A random-access iterator.
1649    *  @param  result_last    Another random-access iterator.
1650    *  @return   An iterator indicating the end of the resulting sequence.
1651    *
1652    *  Copies and sorts the smallest N values from the range @p [first,last)
1653    *  to the range beginning at @p result_first, where the number of
1654    *  elements to be copied, @p N, is the smaller of @p (last-first) and
1655    *  @p (result_last-result_first).
1656    *  After the sort if @p i and @j are iterators in the range
1657    *  @p [result_first,result_first+N) such that @i precedes @j then
1658    *  @p *j<*i is false.
1659    *  The value returned is @p result_first+N.
1660   */
1661   template<typename _InputIterator, typename _RandomAccessIterator>
1662     _RandomAccessIterator
1663     partial_sort_copy(_InputIterator __first, _InputIterator __last,
1664                       _RandomAccessIterator __result_first,
1665                       _RandomAccessIterator __result_last)
1666     {
1667       typedef typename iterator_traits<_InputIterator>::value_type
1668         _InputValueType;
1669       typedef typename iterator_traits<_RandomAccessIterator>::value_type
1670         _OutputValueType;
1671       typedef typename iterator_traits<_RandomAccessIterator>::difference_type
1672         _DistanceType;
1673
1674       // concept requirements
1675       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
1676       __glibcxx_function_requires(_ConvertibleConcept<_InputValueType,
1677                                   _OutputValueType>)
1678       __glibcxx_function_requires(_LessThanOpConcept<_InputValueType,
1679                                                      _OutputValueType>)
1680       __glibcxx_function_requires(_LessThanComparableConcept<_OutputValueType>)
1681       __glibcxx_requires_valid_range(__first, __last);
1682       __glibcxx_requires_valid_range(__result_first, __result_last);
1683
1684       if (__result_first == __result_last)
1685         return __result_last;
1686       _RandomAccessIterator __result_real_last = __result_first;
1687       while(__first != __last && __result_real_last != __result_last)
1688         {
1689           *__result_real_last = *__first;
1690           ++__result_real_last;
1691           ++__first;
1692         }
1693       std::make_heap(__result_first, __result_real_last);
1694       while (__first != __last)
1695         {
1696           if (*__first < *__result_first)
1697             std::__adjust_heap(__result_first, _DistanceType(0),
1698                                _DistanceType(__result_real_last
1699                                              - __result_first),
1700                                _InputValueType(*__first));
1701           ++__first;
1702         }
1703       std::sort_heap(__result_first, __result_real_last);
1704       return __result_real_last;
1705     }
1706
1707   /**
1708    *  @brief Copy the smallest elements of a sequence using a predicate for
1709    *         comparison.
1710    *  @param  first   An input iterator.
1711    *  @param  last    Another input iterator.
1712    *  @param  result_first   A random-access iterator.
1713    *  @param  result_last    Another random-access iterator.
1714    *  @param  comp    A comparison functor.
1715    *  @return   An iterator indicating the end of the resulting sequence.
1716    *
1717    *  Copies and sorts the smallest N values from the range @p [first,last)
1718    *  to the range beginning at @p result_first, where the number of
1719    *  elements to be copied, @p N, is the smaller of @p (last-first) and
1720    *  @p (result_last-result_first).
1721    *  After the sort if @p i and @j are iterators in the range
1722    *  @p [result_first,result_first+N) such that @i precedes @j then
1723    *  @p comp(*j,*i) is false.
1724    *  The value returned is @p result_first+N.
1725   */
1726   template<typename _InputIterator, typename _RandomAccessIterator, typename _Compare>
1727     _RandomAccessIterator
1728     partial_sort_copy(_InputIterator __first, _InputIterator __last,
1729                       _RandomAccessIterator __result_first,
1730                       _RandomAccessIterator __result_last,
1731                       _Compare __comp)
1732     {
1733       typedef typename iterator_traits<_InputIterator>::value_type
1734         _InputValueType;
1735       typedef typename iterator_traits<_RandomAccessIterator>::value_type
1736         _OutputValueType;
1737       typedef typename iterator_traits<_RandomAccessIterator>::difference_type
1738         _DistanceType;
1739
1740       // concept requirements
1741       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
1742       __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
1743                                   _RandomAccessIterator>)
1744       __glibcxx_function_requires(_ConvertibleConcept<_InputValueType,
1745                                   _OutputValueType>)
1746       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
1747                                   _InputValueType, _OutputValueType>)
1748       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
1749                                   _OutputValueType, _OutputValueType>)
1750       __glibcxx_requires_valid_range(__first, __last);
1751       __glibcxx_requires_valid_range(__result_first, __result_last);
1752
1753       if (__result_first == __result_last)
1754         return __result_last;
1755       _RandomAccessIterator __result_real_last = __result_first;
1756       while(__first != __last && __result_real_last != __result_last)
1757         {
1758           *__result_real_last = *__first;
1759           ++__result_real_last;
1760           ++__first;
1761         }
1762       std::make_heap(__result_first, __result_real_last, __comp);
1763       while (__first != __last)
1764         {
1765           if (__comp(*__first, *__result_first))
1766             std::__adjust_heap(__result_first, _DistanceType(0),
1767                                _DistanceType(__result_real_last
1768                                              - __result_first),
1769                                _InputValueType(*__first),
1770                                __comp);
1771           ++__first;
1772         }
1773       std::sort_heap(__result_first, __result_real_last, __comp);
1774       return __result_real_last;
1775     }
1776
1777   /**
1778    *  @if maint
1779    *  This is a helper function for the sort routine.
1780    *  @endif
1781   */
1782   template<typename _RandomAccessIterator, typename _Tp>
1783     void
1784     __unguarded_linear_insert(_RandomAccessIterator __last, _Tp __val)
1785     {
1786       _RandomAccessIterator __next = __last;
1787       --__next;
1788       while (__val < *__next)
1789         {
1790           *__last = *__next;
1791           __last = __next;
1792           --__next;
1793         }
1794       *__last = __val;
1795     }
1796
1797   /**
1798    *  @if maint
1799    *  This is a helper function for the sort routine.
1800    *  @endif
1801   */
1802   template<typename _RandomAccessIterator, typename _Tp, typename _Compare>
1803     void
1804     __unguarded_linear_insert(_RandomAccessIterator __last, _Tp __val,
1805                               _Compare __comp)
1806     {
1807       _RandomAccessIterator __next = __last;
1808       --__next;
1809       while (__comp(__val, *__next))
1810         {
1811           *__last = *__next;
1812           __last = __next;
1813           --__next;
1814         }
1815       *__last = __val;
1816     }
1817
1818   /**
1819    *  @if maint
1820    *  This is a helper function for the sort routine.
1821    *  @endif
1822   */
1823   template<typename _RandomAccessIterator>
1824     void
1825     __insertion_sort(_RandomAccessIterator __first,
1826                      _RandomAccessIterator __last)
1827     {
1828       if (__first == __last)
1829         return;
1830
1831       for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i)
1832         {
1833           typename iterator_traits<_RandomAccessIterator>::value_type
1834             __val = *__i;
1835           if (__val < *__first)
1836             {
1837               std::copy_backward(__first, __i, __i + 1);
1838               *__first = __val;
1839             }
1840           else
1841             std::__unguarded_linear_insert(__i, __val);
1842         }
1843     }
1844
1845   /**
1846    *  @if maint
1847    *  This is a helper function for the sort routine.
1848    *  @endif
1849   */
1850   template<typename _RandomAccessIterator, typename _Compare>
1851     void
1852     __insertion_sort(_RandomAccessIterator __first,
1853                      _RandomAccessIterator __last, _Compare __comp)
1854     {
1855       if (__first == __last) return;
1856
1857       for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i)
1858         {
1859           typename iterator_traits<_RandomAccessIterator>::value_type
1860             __val = *__i;
1861           if (__comp(__val, *__first))
1862             {
1863               std::copy_backward(__first, __i, __i + 1);
1864               *__first = __val;
1865             }
1866           else
1867             std::__unguarded_linear_insert(__i, __val, __comp);
1868         }
1869     }
1870
1871   /**
1872    *  @if maint
1873    *  This is a helper function for the sort routine.
1874    *  @endif
1875   */
1876   template<typename _RandomAccessIterator>
1877     inline void
1878     __unguarded_insertion_sort(_RandomAccessIterator __first,
1879                                _RandomAccessIterator __last)
1880     {
1881       typedef typename iterator_traits<_RandomAccessIterator>::value_type
1882         _ValueType;
1883
1884       for (_RandomAccessIterator __i = __first; __i != __last; ++__i)
1885         std::__unguarded_linear_insert(__i, _ValueType(*__i));
1886     }
1887
1888   /**
1889    *  @if maint
1890    *  This is a helper function for the sort routine.
1891    *  @endif
1892   */
1893   template<typename _RandomAccessIterator, typename _Compare>
1894     inline void
1895     __unguarded_insertion_sort(_RandomAccessIterator __first,
1896                                _RandomAccessIterator __last, _Compare __comp)
1897     {
1898       typedef typename iterator_traits<_RandomAccessIterator>::value_type
1899         _ValueType;
1900
1901       for (_RandomAccessIterator __i = __first; __i != __last; ++__i)
1902         std::__unguarded_linear_insert(__i, _ValueType(*__i), __comp);
1903     }
1904
1905   /**
1906    *  @if maint
1907    *  @doctodo
1908    *  This controls some aspect of the sort routines.
1909    *  @endif
1910   */
1911   enum { _S_threshold = 16 };
1912
1913   /**
1914    *  @if maint
1915    *  This is a helper function for the sort routine.
1916    *  @endif
1917   */
1918   template<typename _RandomAccessIterator>
1919     void
1920     __final_insertion_sort(_RandomAccessIterator __first,
1921                            _RandomAccessIterator __last)
1922     {
1923       if (__last - __first > int(_S_threshold))
1924         {
1925           std::__insertion_sort(__first, __first + int(_S_threshold));
1926           std::__unguarded_insertion_sort(__first + int(_S_threshold), __last);
1927         }
1928       else
1929         std::__insertion_sort(__first, __last);
1930     }
1931
1932   /**
1933    *  @if maint
1934    *  This is a helper function for the sort routine.
1935    *  @endif
1936   */
1937   template<typename _RandomAccessIterator, typename _Compare>
1938     void
1939     __final_insertion_sort(_RandomAccessIterator __first,
1940                            _RandomAccessIterator __last, _Compare __comp)
1941     {
1942       if (__last - __first > int(_S_threshold))
1943         {
1944           std::__insertion_sort(__first, __first + int(_S_threshold), __comp);
1945           std::__unguarded_insertion_sort(__first + int(_S_threshold), __last,
1946                                           __comp);
1947         }
1948       else
1949         std::__insertion_sort(__first, __last, __comp);
1950     }
1951
1952   /**
1953    *  @if maint
1954    *  This is a helper function...
1955    *  @endif
1956   */
1957   template<typename _RandomAccessIterator, typename _Tp>
1958     _RandomAccessIterator
1959     __unguarded_partition(_RandomAccessIterator __first,
1960                           _RandomAccessIterator __last, _Tp __pivot)
1961     {
1962       while (true)
1963         {
1964           while (*__first < __pivot)
1965             ++__first;
1966           --__last;
1967           while (__pivot < *__last)
1968             --__last;
1969           if (!(__first < __last))
1970             return __first;
1971           std::iter_swap(__first, __last);
1972           ++__first;
1973         }
1974     }
1975
1976   /**
1977    *  @if maint
1978    *  This is a helper function...
1979    *  @endif
1980   */
1981   template<typename _RandomAccessIterator, typename _Tp, typename _Compare>
1982     _RandomAccessIterator
1983     __unguarded_partition(_RandomAccessIterator __first,
1984                           _RandomAccessIterator __last,
1985                           _Tp __pivot, _Compare __comp)
1986     {
1987       while (true)
1988         {
1989           while (__comp(*__first, __pivot))
1990             ++__first;
1991           --__last;
1992           while (__comp(__pivot, *__last))
1993             --__last;
1994           if (!(__first < __last))
1995             return __first;
1996           std::iter_swap(__first, __last);
1997           ++__first;
1998         }
1999     }
2000
2001   /**
2002    *  @if maint
2003    *  This is a helper function for the sort routine.
2004    *  @endif
2005   */
2006   template<typename _RandomAccessIterator, typename _Size>
2007     void
2008     __introsort_loop(_RandomAccessIterator __first,
2009                      _RandomAccessIterator __last,
2010                      _Size __depth_limit)
2011     {
2012       typedef typename iterator_traits<_RandomAccessIterator>::value_type
2013         _ValueType;
2014
2015       while (__last - __first > int(_S_threshold))
2016         {
2017           if (__depth_limit == 0)
2018             {
2019               _GLIBCXX_STD_P:partial_sort(__first, __last, __last);
2020               return;
2021             }
2022           --__depth_limit;
2023           _RandomAccessIterator __cut =
2024             std::__unguarded_partition(__first, __last,
2025                                        _ValueType(std::__median(*__first,
2026                                                                 *(__first
2027                                                                   + (__last
2028                                                                      - __first)
2029                                                                   / 2),
2030                                                                 *(__last
2031                                                                   - 1))));
2032           std::__introsort_loop(__cut, __last, __depth_limit);
2033           __last = __cut;
2034         }
2035     }
2036
2037   /**
2038    *  @if maint
2039    *  This is a helper function for the sort routine.
2040    *  @endif
2041   */
2042   template<typename _RandomAccessIterator, typename _Size, typename _Compare>
2043     void
2044     __introsort_loop(_RandomAccessIterator __first,
2045                      _RandomAccessIterator __last,
2046                      _Size __depth_limit, _Compare __comp)
2047     {
2048       typedef typename iterator_traits<_RandomAccessIterator>::value_type
2049         _ValueType;
2050
2051       while (__last - __first > int(_S_threshold))
2052         {
2053           if (__depth_limit == 0)
2054             {
2055               _GLIBCXX_STD_P::partial_sort(__first, __last, __last, __comp);
2056               return;
2057             }
2058           --__depth_limit;
2059           _RandomAccessIterator __cut =
2060             std::__unguarded_partition(__first, __last,
2061                                        _ValueType(std::__median(*__first,
2062                                                                 *(__first
2063                                                                   + (__last
2064                                                                      - __first)
2065                                                                   / 2),
2066                                                                 *(__last - 1),
2067                                                                 __comp)),
2068                                        __comp);
2069           std::__introsort_loop(__cut, __last, __depth_limit, __comp);
2070           __last = __cut;
2071         }
2072     }
2073
2074   /**
2075    *  @if maint
2076    *  This is a helper function for the sort routines.
2077    *  @endif
2078   */
2079   template<typename _Size>
2080     inline _Size
2081     __lg(_Size __n)
2082     {
2083       _Size __k;
2084       for (__k = 0; __n != 1; __n >>= 1)
2085         ++__k;
2086       return __k;
2087     }
2088
2089   // sort
2090
2091   template<typename _RandomAccessIterator, typename _Size>
2092     void
2093     __introselect(_RandomAccessIterator __first, _RandomAccessIterator __nth,
2094                   _RandomAccessIterator __last, _Size __depth_limit)
2095     {
2096       typedef typename iterator_traits<_RandomAccessIterator>::value_type
2097         _ValueType;
2098
2099       while (__last - __first > 3)
2100         {
2101           if (__depth_limit == 0)
2102             {
2103               std::__heap_select(__first, __nth + 1, __last);
2104               // Place the nth largest element in its final position.
2105               std::iter_swap(__first, __nth);
2106               return;
2107             }
2108           --__depth_limit;
2109           _RandomAccessIterator __cut =
2110             std::__unguarded_partition(__first, __last,
2111                                        _ValueType(std::__median(*__first,
2112                                                                 *(__first
2113                                                                   + (__last
2114                                                                      - __first)
2115                                                                   / 2),
2116                                                                 *(__last
2117                                                                   - 1))));
2118           if (__cut <= __nth)
2119             __first = __cut;
2120           else
2121             __last = __cut;
2122         }
2123       std::__insertion_sort(__first, __last);
2124     }
2125
2126   template<typename _RandomAccessIterator, typename _Size, typename _Compare>
2127     void
2128     __introselect(_RandomAccessIterator __first, _RandomAccessIterator __nth,
2129                   _RandomAccessIterator __last, _Size __depth_limit,
2130                   _Compare __comp)
2131     {
2132       typedef typename iterator_traits<_RandomAccessIterator>::value_type
2133         _ValueType;
2134
2135       while (__last - __first > 3)
2136         {
2137           if (__depth_limit == 0)
2138             {
2139               std::__heap_select(__first, __nth + 1, __last, __comp);
2140               // Place the nth largest element in its final position.
2141               std::iter_swap(__first, __nth);
2142               return;
2143             }
2144           --__depth_limit;
2145           _RandomAccessIterator __cut =
2146             std::__unguarded_partition(__first, __last,
2147                                        _ValueType(std::__median(*__first,
2148                                                                 *(__first
2149                                                                   + (__last
2150                                                                      - __first)
2151                                                                   / 2),
2152                                                                 *(__last - 1),
2153                                                                 __comp)),
2154                                        __comp);
2155           if (__cut <= __nth)
2156             __first = __cut;
2157           else
2158             __last = __cut;
2159         }
2160       std::__insertion_sort(__first, __last, __comp);
2161     }
2162
2163   // nth_element
2164
2165   /**
2166    *  @brief Finds the first position in which @a val could be inserted
2167    *         without changing the ordering.
2168    *  @param  first   An iterator.
2169    *  @param  last    Another iterator.
2170    *  @param  val     The search term.
2171    *  @return         An iterator pointing to the first element "not less
2172    *                  than" @a val, or end() if every element is less than
2173    *                  @a val.
2174    *  @ingroup binarysearch
2175   */
2176   template<typename _ForwardIterator, typename _Tp>
2177     _ForwardIterator
2178     lower_bound(_ForwardIterator __first, _ForwardIterator __last,
2179                 const _Tp& __val)
2180     {
2181       typedef typename iterator_traits<_ForwardIterator>::value_type
2182         _ValueType;
2183       typedef typename iterator_traits<_ForwardIterator>::difference_type
2184         _DistanceType;
2185
2186       // concept requirements
2187       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
2188       __glibcxx_function_requires(_LessThanOpConcept<_ValueType, _Tp>)
2189       __glibcxx_requires_partitioned(__first, __last, __val);
2190
2191       _DistanceType __len = std::distance(__first, __last);
2192       _DistanceType __half;
2193       _ForwardIterator __middle;
2194
2195       while (__len > 0)
2196         {
2197           __half = __len >> 1;
2198           __middle = __first;
2199           std::advance(__middle, __half);
2200           if (*__middle < __val)
2201             {
2202               __first = __middle;
2203               ++__first;
2204               __len = __len - __half - 1;
2205             }
2206           else
2207             __len = __half;
2208         }
2209       return __first;
2210     }
2211
2212   /**
2213    *  @brief Finds the first position in which @a val could be inserted
2214    *         without changing the ordering.
2215    *  @param  first   An iterator.
2216    *  @param  last    Another iterator.
2217    *  @param  val     The search term.
2218    *  @param  comp    A functor to use for comparisons.
2219    *  @return  An iterator pointing to the first element "not less than" @a val,
2220    *           or end() if every element is less than @a val.
2221    *  @ingroup binarysearch
2222    *
2223    *  The comparison function should have the same effects on ordering as
2224    *  the function used for the initial sort.
2225   */
2226   template<typename _ForwardIterator, typename _Tp, typename _Compare>
2227     _ForwardIterator
2228     lower_bound(_ForwardIterator __first, _ForwardIterator __last,
2229                 const _Tp& __val, _Compare __comp)
2230     {
2231       typedef typename iterator_traits<_ForwardIterator>::value_type
2232         _ValueType;
2233       typedef typename iterator_traits<_ForwardIterator>::difference_type
2234         _DistanceType;
2235
2236       // concept requirements
2237       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
2238       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2239                                   _ValueType, _Tp>)
2240       __glibcxx_requires_partitioned_pred(__first, __last, __val, __comp);
2241
2242       _DistanceType __len = std::distance(__first, __last);
2243       _DistanceType __half;
2244       _ForwardIterator __middle;
2245
2246       while (__len > 0)
2247         {
2248           __half = __len >> 1;
2249           __middle = __first;
2250           std::advance(__middle, __half);
2251           if (__comp(*__middle, __val))
2252             {
2253               __first = __middle;
2254               ++__first;
2255               __len = __len - __half - 1;
2256             }
2257           else
2258             __len = __half;
2259         }
2260       return __first;
2261     }
2262
2263   /**
2264    *  @brief Finds the last position in which @a val could be inserted
2265    *         without changing the ordering.
2266    *  @param  first   An iterator.
2267    *  @param  last    Another iterator.
2268    *  @param  val     The search term.
2269    *  @return  An iterator pointing to the first element greater than @a val,
2270    *           or end() if no elements are greater than @a val.
2271    *  @ingroup binarysearch
2272   */
2273   template<typename _ForwardIterator, typename _Tp>
2274     _ForwardIterator
2275     upper_bound(_ForwardIterator __first, _ForwardIterator __last,
2276                 const _Tp& __val)
2277     {
2278       typedef typename iterator_traits<_ForwardIterator>::value_type
2279         _ValueType;
2280       typedef typename iterator_traits<_ForwardIterator>::difference_type
2281         _DistanceType;
2282
2283       // concept requirements
2284       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
2285       __glibcxx_function_requires(_LessThanOpConcept<_Tp, _ValueType>)
2286       __glibcxx_requires_partitioned(__first, __last, __val);
2287
2288       _DistanceType __len = std::distance(__first, __last);
2289       _DistanceType __half;
2290       _ForwardIterator __middle;
2291
2292       while (__len > 0)
2293         {
2294           __half = __len >> 1;
2295           __middle = __first;
2296           std::advance(__middle, __half);
2297           if (__val < *__middle)
2298             __len = __half;
2299           else
2300             {
2301               __first = __middle;
2302               ++__first;
2303               __len = __len - __half - 1;
2304             }
2305         }
2306       return __first;
2307     }
2308
2309   /**
2310    *  @brief Finds the last position in which @a val could be inserted
2311    *         without changing the ordering.
2312    *  @param  first   An iterator.
2313    *  @param  last    Another iterator.
2314    *  @param  val     The search term.
2315    *  @param  comp    A functor to use for comparisons.
2316    *  @return  An iterator pointing to the first element greater than @a val,
2317    *           or end() if no elements are greater than @a val.
2318    *  @ingroup binarysearch
2319    *
2320    *  The comparison function should have the same effects on ordering as
2321    *  the function used for the initial sort.
2322   */
2323   template<typename _ForwardIterator, typename _Tp, typename _Compare>
2324     _ForwardIterator
2325     upper_bound(_ForwardIterator __first, _ForwardIterator __last,
2326                 const _Tp& __val, _Compare __comp)
2327     {
2328       typedef typename iterator_traits<_ForwardIterator>::value_type
2329         _ValueType;
2330       typedef typename iterator_traits<_ForwardIterator>::difference_type
2331         _DistanceType;
2332
2333       // concept requirements
2334       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
2335       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2336                                   _Tp, _ValueType>)
2337       __glibcxx_requires_partitioned_pred(__first, __last, __val, __comp);
2338
2339       _DistanceType __len = std::distance(__first, __last);
2340       _DistanceType __half;
2341       _ForwardIterator __middle;
2342
2343       while (__len > 0)
2344         {
2345           __half = __len >> 1;
2346           __middle = __first;
2347           std::advance(__middle, __half);
2348           if (__comp(__val, *__middle))
2349             __len = __half;
2350           else
2351             {
2352               __first = __middle;
2353               ++__first;
2354               __len = __len - __half - 1;
2355             }
2356         }
2357       return __first;
2358     }
2359
2360   /**
2361    *  @brief Finds the largest subrange in which @a val could be inserted
2362    *         at any place in it without changing the ordering.
2363    *  @param  first   An iterator.
2364    *  @param  last    Another iterator.
2365    *  @param  val     The search term.
2366    *  @return  An pair of iterators defining the subrange.
2367    *  @ingroup binarysearch
2368    *
2369    *  This is equivalent to
2370    *  @code
2371    *    std::make_pair(lower_bound(first, last, val),
2372    *                   upper_bound(first, last, val))
2373    *  @endcode
2374    *  but does not actually call those functions.
2375   */
2376   template<typename _ForwardIterator, typename _Tp>
2377     pair<_ForwardIterator, _ForwardIterator>
2378     equal_range(_ForwardIterator __first, _ForwardIterator __last,
2379                 const _Tp& __val)
2380     {
2381       typedef typename iterator_traits<_ForwardIterator>::value_type
2382         _ValueType;
2383       typedef typename iterator_traits<_ForwardIterator>::difference_type
2384         _DistanceType;
2385
2386       // concept requirements
2387       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
2388       __glibcxx_function_requires(_LessThanOpConcept<_ValueType, _Tp>)
2389       __glibcxx_function_requires(_LessThanOpConcept<_Tp, _ValueType>)
2390       __glibcxx_requires_partitioned(__first, __last, __val);
2391
2392       _DistanceType __len = std::distance(__first, __last);
2393       _DistanceType __half;
2394       _ForwardIterator __middle, __left, __right;
2395
2396       while (__len > 0)
2397         {
2398           __half = __len >> 1;
2399           __middle = __first;
2400           std::advance(__middle, __half);
2401           if (*__middle < __val)
2402             {
2403               __first = __middle;
2404               ++__first;
2405               __len = __len - __half - 1;
2406             }
2407           else if (__val < *__middle)
2408             __len = __half;
2409           else
2410             {
2411               __left = std::lower_bound(__first, __middle, __val);
2412               std::advance(__first, __len);
2413               __right = std::upper_bound(++__middle, __first, __val);
2414               return pair<_ForwardIterator, _ForwardIterator>(__left, __right);
2415             }
2416         }
2417       return pair<_ForwardIterator, _ForwardIterator>(__first, __first);
2418     }
2419
2420   /**
2421    *  @brief Finds the largest subrange in which @a val could be inserted
2422    *         at any place in it without changing the ordering.
2423    *  @param  first   An iterator.
2424    *  @param  last    Another iterator.
2425    *  @param  val     The search term.
2426    *  @param  comp    A functor to use for comparisons.
2427    *  @return  An pair of iterators defining the subrange.
2428    *  @ingroup binarysearch
2429    *
2430    *  This is equivalent to
2431    *  @code
2432    *    std::make_pair(lower_bound(first, last, val, comp),
2433    *                   upper_bound(first, last, val, comp))
2434    *  @endcode
2435    *  but does not actually call those functions.
2436   */
2437   template<typename _ForwardIterator, typename _Tp, typename _Compare>
2438     pair<_ForwardIterator, _ForwardIterator>
2439     equal_range(_ForwardIterator __first, _ForwardIterator __last,
2440                 const _Tp& __val,
2441                 _Compare __comp)
2442     {
2443       typedef typename iterator_traits<_ForwardIterator>::value_type
2444         _ValueType;
2445       typedef typename iterator_traits<_ForwardIterator>::difference_type
2446         _DistanceType;
2447
2448       // concept requirements
2449       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
2450       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2451                                   _ValueType, _Tp>)
2452       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2453                                   _Tp, _ValueType>)
2454       __glibcxx_requires_partitioned_pred(__first, __last, __val, __comp);
2455
2456       _DistanceType __len = std::distance(__first, __last);
2457       _DistanceType __half;
2458       _ForwardIterator __middle, __left, __right;
2459
2460       while (__len > 0)
2461         {
2462           __half = __len >> 1;
2463           __middle = __first;
2464           std::advance(__middle, __half);
2465           if (__comp(*__middle, __val))
2466             {
2467               __first = __middle;
2468               ++__first;
2469               __len = __len - __half - 1;
2470             }
2471           else if (__comp(__val, *__middle))
2472             __len = __half;
2473           else
2474             {
2475               __left = std::lower_bound(__first, __middle, __val, __comp);
2476               std::advance(__first, __len);
2477               __right = std::upper_bound(++__middle, __first, __val, __comp);
2478               return pair<_ForwardIterator, _ForwardIterator>(__left, __right);
2479             }
2480         }
2481       return pair<_ForwardIterator, _ForwardIterator>(__first, __first);
2482     }
2483
2484   /**
2485    *  @brief Determines whether an element exists in a range.
2486    *  @param  first   An iterator.
2487    *  @param  last    Another iterator.
2488    *  @param  val     The search term.
2489    *  @return  True if @a val (or its equivelent) is in [@a first,@a last ].
2490    *  @ingroup binarysearch
2491    *
2492    *  Note that this does not actually return an iterator to @a val.  For
2493    *  that, use std::find or a container's specialized find member functions.
2494   */
2495   template<typename _ForwardIterator, typename _Tp>
2496     bool
2497     binary_search(_ForwardIterator __first, _ForwardIterator __last,
2498                   const _Tp& __val)
2499     {
2500       typedef typename iterator_traits<_ForwardIterator>::value_type
2501         _ValueType;
2502
2503       // concept requirements
2504       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
2505       __glibcxx_function_requires(_LessThanOpConcept<_Tp, _ValueType>)
2506       __glibcxx_requires_partitioned(__first, __last, __val);
2507
2508       _ForwardIterator __i = std::lower_bound(__first, __last, __val);
2509       return __i != __last && !(__val < *__i);
2510     }
2511
2512   /**
2513    *  @brief Determines whether an element exists in a range.
2514    *  @param  first   An iterator.
2515    *  @param  last    Another iterator.
2516    *  @param  val     The search term.
2517    *  @param  comp    A functor to use for comparisons.
2518    *  @return  True if @a val (or its equivelent) is in [@a first,@a last ].
2519    *  @ingroup binarysearch
2520    *
2521    *  Note that this does not actually return an iterator to @a val.  For
2522    *  that, use std::find or a container's specialized find member functions.
2523    *
2524    *  The comparison function should have the same effects on ordering as
2525    *  the function used for the initial sort.
2526   */
2527   template<typename _ForwardIterator, typename _Tp, typename _Compare>
2528     bool
2529     binary_search(_ForwardIterator __first, _ForwardIterator __last,
2530                   const _Tp& __val, _Compare __comp)
2531     {
2532       typedef typename iterator_traits<_ForwardIterator>::value_type
2533         _ValueType;
2534
2535       // concept requirements
2536       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
2537       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2538                                   _Tp, _ValueType>)
2539       __glibcxx_requires_partitioned_pred(__first, __last, __val, __comp);
2540
2541       _ForwardIterator __i = std::lower_bound(__first, __last, __val, __comp);
2542       return __i != __last && !bool(__comp(__val, *__i));
2543     }
2544
2545   // merge
2546
2547   /**
2548    *  @if maint
2549    *  This is a helper function for the merge routines.
2550    *  @endif
2551   */
2552   template<typename _BidirectionalIterator1, typename _BidirectionalIterator2,
2553            typename _BidirectionalIterator3>
2554     _BidirectionalIterator3
2555     __merge_backward(_BidirectionalIterator1 __first1,
2556                      _BidirectionalIterator1 __last1,
2557                      _BidirectionalIterator2 __first2,
2558                      _BidirectionalIterator2 __last2,
2559                      _BidirectionalIterator3 __result)
2560     {
2561       if (__first1 == __last1)
2562         return std::copy_backward(__first2, __last2, __result);
2563       if (__first2 == __last2)
2564         return std::copy_backward(__first1, __last1, __result);
2565       --__last1;
2566       --__last2;
2567       while (true)
2568         {
2569           if (*__last2 < *__last1)
2570             {
2571               *--__result = *__last1;
2572               if (__first1 == __last1)
2573                 return std::copy_backward(__first2, ++__last2, __result);
2574               --__last1;
2575             }
2576           else
2577             {
2578               *--__result = *__last2;
2579               if (__first2 == __last2)
2580                 return std::copy_backward(__first1, ++__last1, __result);
2581               --__last2;
2582             }
2583         }
2584     }
2585
2586   /**
2587    *  @if maint
2588    *  This is a helper function for the merge routines.
2589    *  @endif
2590   */
2591   template<typename _BidirectionalIterator1, typename _BidirectionalIterator2,
2592            typename _BidirectionalIterator3, typename _Compare>
2593     _BidirectionalIterator3
2594     __merge_backward(_BidirectionalIterator1 __first1,
2595                      _BidirectionalIterator1 __last1,
2596                      _BidirectionalIterator2 __first2,
2597                      _BidirectionalIterator2 __last2,
2598                      _BidirectionalIterator3 __result,
2599                      _Compare __comp)
2600     {
2601       if (__first1 == __last1)
2602         return std::copy_backward(__first2, __last2, __result);
2603       if (__first2 == __last2)
2604         return std::copy_backward(__first1, __last1, __result);
2605       --__last1;
2606       --__last2;
2607       while (true)
2608         {
2609           if (__comp(*__last2, *__last1))
2610             {
2611               *--__result = *__last1;
2612               if (__first1 == __last1)
2613                 return std::copy_backward(__first2, ++__last2, __result);
2614               --__last1;
2615             }
2616           else
2617             {
2618               *--__result = *__last2;
2619               if (__first2 == __last2)
2620                 return std::copy_backward(__first1, ++__last1, __result);
2621               --__last2;
2622             }
2623         }
2624     }
2625
2626   /**
2627    *  @if maint
2628    *  This is a helper function for the merge routines.
2629    *  @endif
2630   */
2631   template<typename _BidirectionalIterator1, typename _BidirectionalIterator2,
2632            typename _Distance>
2633     _BidirectionalIterator1
2634     __rotate_adaptive(_BidirectionalIterator1 __first,
2635                       _BidirectionalIterator1 __middle,
2636                       _BidirectionalIterator1 __last,
2637                       _Distance __len1, _Distance __len2,
2638                       _BidirectionalIterator2 __buffer,
2639                       _Distance __buffer_size)
2640     {
2641       _BidirectionalIterator2 __buffer_end;
2642       if (__len1 > __len2 && __len2 <= __buffer_size)
2643         {
2644           __buffer_end = std::copy(__middle, __last, __buffer);
2645           std::copy_backward(__first, __middle, __last);
2646           return std::copy(__buffer, __buffer_end, __first);
2647         }
2648       else if (__len1 <= __buffer_size)
2649         {
2650           __buffer_end = std::copy(__first, __middle, __buffer);
2651           std::copy(__middle, __last, __first);
2652           return std::copy_backward(__buffer, __buffer_end, __last);
2653         }
2654       else
2655         {
2656           std::rotate(__first, __middle, __last);
2657           std::advance(__first, std::distance(__middle, __last));
2658           return __first;
2659         }
2660     }
2661
2662   /**
2663    *  @if maint
2664    *  This is a helper function for the merge routines.
2665    *  @endif
2666   */
2667   template<typename _BidirectionalIterator, typename _Distance,
2668            typename _Pointer>
2669     void
2670     __merge_adaptive(_BidirectionalIterator __first,
2671                      _BidirectionalIterator __middle,
2672                      _BidirectionalIterator __last,
2673                      _Distance __len1, _Distance __len2,
2674                      _Pointer __buffer, _Distance __buffer_size)
2675     {
2676       if (__len1 <= __len2 && __len1 <= __buffer_size)
2677         {
2678           _Pointer __buffer_end = std::copy(__first, __middle, __buffer);
2679           _GLIBCXX_STD_P::merge(__buffer, __buffer_end, __middle, __last,
2680                                 __first);
2681         }
2682       else if (__len2 <= __buffer_size)
2683         {
2684           _Pointer __buffer_end = std::copy(__middle, __last, __buffer);
2685           std::__merge_backward(__first, __middle, __buffer,
2686                                 __buffer_end, __last);
2687         }
2688       else
2689         {
2690           _BidirectionalIterator __first_cut = __first;
2691           _BidirectionalIterator __second_cut = __middle;
2692           _Distance __len11 = 0;
2693           _Distance __len22 = 0;
2694           if (__len1 > __len2)
2695             {
2696               __len11 = __len1 / 2;
2697               std::advance(__first_cut, __len11);
2698               __second_cut = std::lower_bound(__middle, __last,
2699                                               *__first_cut);
2700               __len22 = std::distance(__middle, __second_cut);
2701             }
2702           else
2703             {
2704               __len22 = __len2 / 2;
2705               std::advance(__second_cut, __len22);
2706               __first_cut = std::upper_bound(__first, __middle,
2707                                              *__second_cut);
2708               __len11 = std::distance(__first, __first_cut);
2709             }
2710           _BidirectionalIterator __new_middle =
2711             std::__rotate_adaptive(__first_cut, __middle, __second_cut,
2712                                    __len1 - __len11, __len22, __buffer,
2713                                    __buffer_size);
2714           std::__merge_adaptive(__first, __first_cut, __new_middle, __len11,
2715                                 __len22, __buffer, __buffer_size);
2716           std::__merge_adaptive(__new_middle, __second_cut, __last,
2717                                 __len1 - __len11,
2718                                 __len2 - __len22, __buffer, __buffer_size);
2719         }
2720     }
2721
2722   /**
2723    *  @if maint
2724    *  This is a helper function for the merge routines.
2725    *  @endif
2726   */
2727   template<typename _BidirectionalIterator, typename _Distance,
2728            typename _Pointer, typename _Compare>
2729     void
2730     __merge_adaptive(_BidirectionalIterator __first,
2731                      _BidirectionalIterator __middle,
2732                      _BidirectionalIterator __last,
2733                      _Distance __len1, _Distance __len2,
2734                      _Pointer __buffer, _Distance __buffer_size,
2735                      _Compare __comp)
2736     {
2737       if (__len1 <= __len2 && __len1 <= __buffer_size)
2738         {
2739           _Pointer __buffer_end = std::copy(__first, __middle, __buffer);
2740           _GLIBCXX_STD_P::merge(__buffer, __buffer_end, __middle, __last, __first, __comp);
2741         }
2742       else if (__len2 <= __buffer_size)
2743         {
2744           _Pointer __buffer_end = std::copy(__middle, __last, __buffer);
2745           std::__merge_backward(__first, __middle, __buffer, __buffer_end,
2746                                 __last, __comp);
2747         }
2748       else
2749         {
2750           _BidirectionalIterator __first_cut = __first;
2751           _BidirectionalIterator __second_cut = __middle;
2752           _Distance __len11 = 0;
2753           _Distance __len22 = 0;
2754           if (__len1 > __len2)
2755             {
2756               __len11 = __len1 / 2;
2757               std::advance(__first_cut, __len11);
2758               __second_cut = std::lower_bound(__middle, __last, *__first_cut,
2759                                               __comp);
2760               __len22 = std::distance(__middle, __second_cut);
2761             }
2762           else
2763             {
2764               __len22 = __len2 / 2;
2765               std::advance(__second_cut, __len22);
2766               __first_cut = std::upper_bound(__first, __middle, *__second_cut,
2767                                              __comp);
2768               __len11 = std::distance(__first, __first_cut);
2769             }
2770           _BidirectionalIterator __new_middle =
2771             std::__rotate_adaptive(__first_cut, __middle, __second_cut,
2772                                    __len1 - __len11, __len22, __buffer,
2773                                    __buffer_size);
2774           std::__merge_adaptive(__first, __first_cut, __new_middle, __len11,
2775                                 __len22, __buffer, __buffer_size, __comp);
2776           std::__merge_adaptive(__new_middle, __second_cut, __last,
2777                                 __len1 - __len11,
2778                                 __len2 - __len22, __buffer,
2779                                 __buffer_size, __comp);
2780         }
2781     }
2782
2783   /**
2784    *  @if maint
2785    *  This is a helper function for the merge routines.
2786    *  @endif
2787   */
2788   template<typename _BidirectionalIterator, typename _Distance>
2789     void
2790     __merge_without_buffer(_BidirectionalIterator __first,
2791                            _BidirectionalIterator __middle,
2792                            _BidirectionalIterator __last,
2793                            _Distance __len1, _Distance __len2)
2794     {
2795       if (__len1 == 0 || __len2 == 0)
2796         return;
2797       if (__len1 + __len2 == 2)
2798         {
2799           if (*__middle < *__first)
2800             std::iter_swap(__first, __middle);
2801           return;
2802         }
2803       _BidirectionalIterator __first_cut = __first;
2804       _BidirectionalIterator __second_cut = __middle;
2805       _Distance __len11 = 0;
2806       _Distance __len22 = 0;
2807       if (__len1 > __len2)
2808         {
2809           __len11 = __len1 / 2;
2810           std::advance(__first_cut, __len11);
2811           __second_cut = std::lower_bound(__middle, __last, *__first_cut);
2812           __len22 = std::distance(__middle, __second_cut);
2813         }
2814       else
2815         {
2816           __len22 = __len2 / 2;
2817           std::advance(__second_cut, __len22);
2818           __first_cut = std::upper_bound(__first, __middle, *__second_cut);
2819           __len11 = std::distance(__first, __first_cut);
2820         }
2821       std::rotate(__first_cut, __middle, __second_cut);
2822       _BidirectionalIterator __new_middle = __first_cut;
2823       std::advance(__new_middle, std::distance(__middle, __second_cut));
2824       std::__merge_without_buffer(__first, __first_cut, __new_middle,
2825                                   __len11, __len22);
2826       std::__merge_without_buffer(__new_middle, __second_cut, __last,
2827                                   __len1 - __len11, __len2 - __len22);
2828     }
2829
2830   /**
2831    *  @if maint
2832    *  This is a helper function for the merge routines.
2833    *  @endif
2834   */
2835   template<typename _BidirectionalIterator, typename _Distance,
2836            typename _Compare>
2837     void
2838     __merge_without_buffer(_BidirectionalIterator __first,
2839                            _BidirectionalIterator __middle,
2840                            _BidirectionalIterator __last,
2841                            _Distance __len1, _Distance __len2,
2842                            _Compare __comp)
2843     {
2844       if (__len1 == 0 || __len2 == 0)
2845         return;
2846       if (__len1 + __len2 == 2)
2847         {
2848           if (__comp(*__middle, *__first))
2849             std::iter_swap(__first, __middle);
2850           return;
2851         }
2852       _BidirectionalIterator __first_cut = __first;
2853       _BidirectionalIterator __second_cut = __middle;
2854       _Distance __len11 = 0;
2855       _Distance __len22 = 0;
2856       if (__len1 > __len2)
2857         {
2858           __len11 = __len1 / 2;
2859           std::advance(__first_cut, __len11);
2860           __second_cut = std::lower_bound(__middle, __last, *__first_cut,
2861                                           __comp);
2862           __len22 = std::distance(__middle, __second_cut);
2863         }
2864       else
2865         {
2866           __len22 = __len2 / 2;
2867           std::advance(__second_cut, __len22);
2868           __first_cut = std::upper_bound(__first, __middle, *__second_cut,
2869                                          __comp);
2870           __len11 = std::distance(__first, __first_cut);
2871         }
2872       std::rotate(__first_cut, __middle, __second_cut);
2873       _BidirectionalIterator __new_middle = __first_cut;
2874       std::advance(__new_middle, std::distance(__middle, __second_cut));
2875       std::__merge_without_buffer(__first, __first_cut, __new_middle,
2876                                   __len11, __len22, __comp);
2877       std::__merge_without_buffer(__new_middle, __second_cut, __last,
2878                                   __len1 - __len11, __len2 - __len22, __comp);
2879     }
2880
2881   /**
2882    *  @brief Merges two sorted ranges in place.
2883    *  @param  first   An iterator.
2884    *  @param  middle  Another iterator.
2885    *  @param  last    Another iterator.
2886    *  @return  Nothing.
2887    *
2888    *  Merges two sorted and consecutive ranges, [first,middle) and
2889    *  [middle,last), and puts the result in [first,last).  The output will
2890    *  be sorted.  The sort is @e stable, that is, for equivalent
2891    *  elements in the two ranges, elements from the first range will always
2892    *  come before elements from the second.
2893    *
2894    *  If enough additional memory is available, this takes (last-first)-1
2895    *  comparisons.  Otherwise an NlogN algorithm is used, where N is
2896    *  distance(first,last).
2897   */
2898   template<typename _BidirectionalIterator>
2899     void
2900     inplace_merge(_BidirectionalIterator __first,
2901                   _BidirectionalIterator __middle,
2902                   _BidirectionalIterator __last)
2903     {
2904       typedef typename iterator_traits<_BidirectionalIterator>::value_type
2905           _ValueType;
2906       typedef typename iterator_traits<_BidirectionalIterator>::difference_type
2907           _DistanceType;
2908
2909       // concept requirements
2910       __glibcxx_function_requires(_Mutable_BidirectionalIteratorConcept<
2911             _BidirectionalIterator>)
2912       __glibcxx_function_requires(_LessThanComparableConcept<_ValueType>)
2913       __glibcxx_requires_sorted(__first, __middle);
2914       __glibcxx_requires_sorted(__middle, __last);
2915
2916       if (__first == __middle || __middle == __last)
2917         return;
2918
2919       _DistanceType __len1 = std::distance(__first, __middle);
2920       _DistanceType __len2 = std::distance(__middle, __last);
2921
2922       _Temporary_buffer<_BidirectionalIterator, _ValueType> __buf(__first,
2923                                                                   __last);
2924       if (__buf.begin() == 0)
2925         std::__merge_without_buffer(__first, __middle, __last, __len1, __len2);
2926       else
2927         std::__merge_adaptive(__first, __middle, __last, __len1, __len2,
2928                               __buf.begin(), _DistanceType(__buf.size()));
2929     }
2930
2931   /**
2932    *  @brief Merges two sorted ranges in place.
2933    *  @param  first   An iterator.
2934    *  @param  middle  Another iterator.
2935    *  @param  last    Another iterator.
2936    *  @param  comp    A functor to use for comparisons.
2937    *  @return  Nothing.
2938    *
2939    *  Merges two sorted and consecutive ranges, [first,middle) and
2940    *  [middle,last), and puts the result in [first,last).  The output will
2941    *  be sorted.  The sort is @e stable, that is, for equivalent
2942    *  elements in the two ranges, elements from the first range will always
2943    *  come before elements from the second.
2944    *
2945    *  If enough additional memory is available, this takes (last-first)-1
2946    *  comparisons.  Otherwise an NlogN algorithm is used, where N is
2947    *  distance(first,last).
2948    *
2949    *  The comparison function should have the same effects on ordering as
2950    *  the function used for the initial sort.
2951   */
2952   template<typename _BidirectionalIterator, typename _Compare>
2953     void
2954     inplace_merge(_BidirectionalIterator __first,
2955                   _BidirectionalIterator __middle,
2956                   _BidirectionalIterator __last,
2957                   _Compare __comp)
2958     {
2959       typedef typename iterator_traits<_BidirectionalIterator>::value_type
2960           _ValueType;
2961       typedef typename iterator_traits<_BidirectionalIterator>::difference_type
2962           _DistanceType;
2963
2964       // concept requirements
2965       __glibcxx_function_requires(_Mutable_BidirectionalIteratorConcept<
2966             _BidirectionalIterator>)
2967       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2968             _ValueType, _ValueType>)
2969       __glibcxx_requires_sorted_pred(__first, __middle, __comp);
2970       __glibcxx_requires_sorted_pred(__middle, __last, __comp);
2971
2972       if (__first == __middle || __middle == __last)
2973         return;
2974
2975       const _DistanceType __len1 = std::distance(__first, __middle);
2976       const _DistanceType __len2 = std::distance(__middle, __last);
2977
2978       _Temporary_buffer<_BidirectionalIterator, _ValueType> __buf(__first,
2979                                                                   __last);
2980       if (__buf.begin() == 0)
2981         std::__merge_without_buffer(__first, __middle, __last, __len1,
2982                                     __len2, __comp);
2983       else
2984         std::__merge_adaptive(__first, __middle, __last, __len1, __len2,
2985                               __buf.begin(), _DistanceType(__buf.size()),
2986                               __comp);
2987     }
2988
2989   template<typename _RandomAccessIterator1, typename _RandomAccessIterator2,
2990            typename _Distance>
2991     void
2992     __merge_sort_loop(_RandomAccessIterator1 __first,
2993                       _RandomAccessIterator1 __last,
2994                       _RandomAccessIterator2 __result,
2995                       _Distance __step_size)
2996     {
2997       const _Distance __two_step = 2 * __step_size;
2998
2999       while (__last - __first >= __two_step)
3000         {
3001           __result = _GLIBCXX_STD_P::merge(__first, __first + __step_size,
3002                                 __first + __step_size, __first + __two_step,
3003                                 __result);
3004           __first += __two_step;
3005         }
3006
3007       __step_size = std::min(_Distance(__last - __first), __step_size);
3008       _GLIBCXX_STD_P::merge(__first, __first + __step_size,
3009                             __first + __step_size, __last,
3010                  __result);
3011     }
3012
3013   template<typename _RandomAccessIterator1, typename _RandomAccessIterator2,
3014            typename _Distance, typename _Compare>
3015     void
3016     __merge_sort_loop(_RandomAccessIterator1 __first,
3017                       _RandomAccessIterator1 __last,
3018                       _RandomAccessIterator2 __result, _Distance __step_size,
3019                       _Compare __comp)
3020     {
3021       const _Distance __two_step = 2 * __step_size;
3022
3023       while (__last - __first >= __two_step)
3024         {
3025           __result = _GLIBCXX_STD_P::merge(__first, __first + __step_size,
3026                                 __first + __step_size, __first + __two_step,
3027                                 __result,
3028                                 __comp);
3029           __first += __two_step;
3030         }
3031       __step_size = std::min(_Distance(__last - __first), __step_size);
3032
3033       _GLIBCXX_STD_P::merge(__first, __first + __step_size,
3034                             __first + __step_size, __last, __result, __comp);
3035     }
3036
3037   template<typename _RandomAccessIterator, typename _Distance>
3038     void
3039     __chunk_insertion_sort(_RandomAccessIterator __first,
3040                            _RandomAccessIterator __last,
3041                            _Distance __chunk_size)
3042     {
3043       while (__last - __first >= __chunk_size)
3044         {
3045           std::__insertion_sort(__first, __first + __chunk_size);
3046           __first += __chunk_size;
3047         }
3048       std::__insertion_sort(__first, __last);
3049     }
3050
3051   template<typename _RandomAccessIterator, typename _Distance, typename _Compare>
3052     void
3053     __chunk_insertion_sort(_RandomAccessIterator __first,
3054                            _RandomAccessIterator __last,
3055                            _Distance __chunk_size, _Compare __comp)
3056     {
3057       while (__last - __first >= __chunk_size)
3058         {
3059           std::__insertion_sort(__first, __first + __chunk_size, __comp);
3060           __first += __chunk_size;
3061         }
3062       std::__insertion_sort(__first, __last, __comp);
3063     }
3064
3065   enum { _S_chunk_size = 7 };
3066
3067   template<typename _RandomAccessIterator, typename _Pointer>
3068     void
3069     __merge_sort_with_buffer(_RandomAccessIterator __first,
3070                              _RandomAccessIterator __last,
3071                              _Pointer __buffer)
3072     {
3073       typedef typename iterator_traits<_RandomAccessIterator>::difference_type
3074         _Distance;
3075
3076       const _Distance __len = __last - __first;
3077       const _Pointer __buffer_last = __buffer + __len;
3078
3079       _Distance __step_size = _S_chunk_size;
3080       std::__chunk_insertion_sort(__first, __last, __step_size);
3081
3082       while (__step_size < __len)
3083         {
3084           std::__merge_sort_loop(__first, __last, __buffer, __step_size);
3085           __step_size *= 2;
3086           std::__merge_sort_loop(__buffer, __buffer_last, __first, __step_size);
3087           __step_size *= 2;
3088         }
3089     }
3090
3091   template<typename _RandomAccessIterator, typename _Pointer, typename _Compare>
3092     void
3093     __merge_sort_with_buffer(_RandomAccessIterator __first,
3094                              _RandomAccessIterator __last,
3095                              _Pointer __buffer, _Compare __comp)
3096     {
3097       typedef typename iterator_traits<_RandomAccessIterator>::difference_type
3098         _Distance;
3099
3100       const _Distance __len = __last - __first;
3101       const _Pointer __buffer_last = __buffer + __len;
3102
3103       _Distance __step_size = _S_chunk_size;
3104       std::__chunk_insertion_sort(__first, __last, __step_size, __comp);
3105
3106       while (__step_size < __len)
3107         {
3108           std::__merge_sort_loop(__first, __last, __buffer,
3109                                  __step_size, __comp);
3110           __step_size *= 2;
3111           std::__merge_sort_loop(__buffer, __buffer_last, __first,
3112                                  __step_size, __comp);
3113           __step_size *= 2;
3114         }
3115     }
3116
3117   template<typename _RandomAccessIterator, typename _Pointer,
3118            typename _Distance>
3119     void
3120     __stable_sort_adaptive(_RandomAccessIterator __first,
3121                            _RandomAccessIterator __last,
3122                            _Pointer __buffer, _Distance __buffer_size)
3123     {
3124       const _Distance __len = (__last - __first + 1) / 2;
3125       const _RandomAccessIterator __middle = __first + __len;
3126       if (__len > __buffer_size)
3127         {
3128           std::__stable_sort_adaptive(__first, __middle,
3129                                       __buffer, __buffer_size);
3130           std::__stable_sort_adaptive(__middle, __last,
3131                                       __buffer, __buffer_size);
3132         }
3133       else
3134         {
3135           std::__merge_sort_with_buffer(__first, __middle, __buffer);
3136           std::__merge_sort_with_buffer(__middle, __last, __buffer);
3137         }
3138       std::__merge_adaptive(__first, __middle, __last,
3139                             _Distance(__middle - __first),
3140                             _Distance(__last - __middle),
3141                             __buffer, __buffer_size);
3142     }
3143
3144   template<typename _RandomAccessIterator, typename _Pointer,
3145            typename _Distance, typename _Compare>
3146     void
3147     __stable_sort_adaptive(_RandomAccessIterator __first,
3148                            _RandomAccessIterator __last,
3149                            _Pointer __buffer, _Distance __buffer_size,
3150                            _Compare __comp)
3151     {
3152       const _Distance __len = (__last - __first + 1) / 2;
3153       const _RandomAccessIterator __middle = __first + __len;
3154       if (__len > __buffer_size)
3155         {
3156           std::__stable_sort_adaptive(__first, __middle, __buffer,
3157                                       __buffer_size, __comp);
3158           std::__stable_sort_adaptive(__middle, __last, __buffer,
3159                                       __buffer_size, __comp);
3160         }
3161       else
3162         {
3163           std::__merge_sort_with_buffer(__first, __middle, __buffer, __comp);
3164           std::__merge_sort_with_buffer(__middle, __last, __buffer, __comp);
3165         }
3166       std::__merge_adaptive(__first, __middle, __last,
3167                             _Distance(__middle - __first),
3168                             _Distance(__last - __middle),
3169                             __buffer, __buffer_size,
3170                             __comp);
3171     }
3172
3173   /**
3174    *  @if maint
3175    *  This is a helper function for the stable sorting routines.
3176    *  @endif
3177   */
3178   template<typename _RandomAccessIterator>
3179     void
3180     __inplace_stable_sort(_RandomAccessIterator __first,
3181                           _RandomAccessIterator __last)
3182     {
3183       if (__last - __first < 15)
3184         {
3185           std::__insertion_sort(__first, __last);
3186           return;
3187         }
3188       _RandomAccessIterator __middle = __first + (__last - __first) / 2;
3189       std::__inplace_stable_sort(__first, __middle);
3190       std::__inplace_stable_sort(__middle, __last);
3191       std::__merge_without_buffer(__first, __middle, __last,
3192                                   __middle - __first,
3193                                   __last - __middle);
3194     }
3195
3196   /**
3197    *  @if maint
3198    *  This is a helper function for the stable sorting routines.
3199    *  @endif
3200   */
3201   template<typename _RandomAccessIterator, typename _Compare>
3202     void
3203     __inplace_stable_sort(_RandomAccessIterator __first,
3204                           _RandomAccessIterator __last, _Compare __comp)
3205     {
3206       if (__last - __first < 15)
3207         {
3208           std::__insertion_sort(__first, __last, __comp);
3209           return;
3210         }
3211       _RandomAccessIterator __middle = __first + (__last - __first) / 2;
3212       std::__inplace_stable_sort(__first, __middle, __comp);
3213       std::__inplace_stable_sort(__middle, __last, __comp);
3214       std::__merge_without_buffer(__first, __middle, __last,
3215                                   __middle - __first,
3216                                   __last - __middle,
3217                                   __comp);
3218     }
3219
3220   // stable_sort
3221
3222   // Set algorithms: includes, set_union, set_intersection, set_difference,
3223   // set_symmetric_difference.  All of these algorithms have the precondition
3224   // that their input ranges are sorted and the postcondition that their output
3225   // ranges are sorted.
3226
3227   /**
3228    *  @brief Determines whether all elements of a sequence exists in a range.
3229    *  @param  first1  Start of search range.
3230    *  @param  last1   End of search range.
3231    *  @param  first2  Start of sequence
3232    *  @param  last2   End of sequence.
3233    *  @return  True if each element in [first2,last2) is contained in order
3234    *  within [first1,last1).  False otherwise.
3235    *  @ingroup setoperations
3236    *
3237    *  This operation expects both [first1,last1) and [first2,last2) to be
3238    *  sorted.  Searches for the presence of each element in [first2,last2)
3239    *  within [first1,last1).  The iterators over each range only move forward,
3240    *  so this is a linear algorithm.  If an element in [first2,last2) is not
3241    *  found before the search iterator reaches @a last2, false is returned.
3242   */
3243   template<typename _InputIterator1, typename _InputIterator2>
3244     bool
3245     includes(_InputIterator1 __first1, _InputIterator1 __last1,
3246              _InputIterator2 __first2, _InputIterator2 __last2)
3247     {
3248       typedef typename iterator_traits<_InputIterator1>::value_type
3249         _ValueType1;
3250       typedef typename iterator_traits<_InputIterator2>::value_type
3251         _ValueType2;
3252
3253       // concept requirements
3254       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
3255       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
3256       __glibcxx_function_requires(_LessThanOpConcept<_ValueType1, _ValueType2>)
3257       __glibcxx_function_requires(_LessThanOpConcept<_ValueType2, _ValueType1>)
3258       __glibcxx_requires_sorted(__first1, __last1);
3259       __glibcxx_requires_sorted(__first2, __last2);
3260
3261       while (__first1 != __last1 && __first2 != __last2)
3262         if (*__first2 < *__first1)
3263           return false;
3264         else if(*__first1 < *__first2)
3265           ++__first1;
3266         else
3267           ++__first1, ++__first2;
3268
3269       return __first2 == __last2;
3270     }
3271
3272   /**
3273    *  @brief Determines whether all elements of a sequence exists in a range
3274    *  using comparison.
3275    *  @param  first1  Start of search range.
3276    *  @param  last1   End of search range.
3277    *  @param  first2  Start of sequence
3278    *  @param  last2   End of sequence.
3279    *  @param  comp    Comparison function to use.
3280    *  @return  True if each element in [first2,last2) is contained in order
3281    *  within [first1,last1) according to comp.  False otherwise.
3282    *  @ingroup setoperations
3283    *
3284    *  This operation expects both [first1,last1) and [first2,last2) to be
3285    *  sorted.  Searches for the presence of each element in [first2,last2)
3286    *  within [first1,last1), using comp to decide.  The iterators over each
3287    *  range only move forward, so this is a linear algorithm.  If an element
3288    *  in [first2,last2) is not found before the search iterator reaches @a
3289    *  last2, false is returned.
3290   */
3291   template<typename _InputIterator1, typename _InputIterator2,
3292            typename _Compare>
3293     bool
3294     includes(_InputIterator1 __first1, _InputIterator1 __last1,
3295              _InputIterator2 __first2, _InputIterator2 __last2, _Compare __comp)
3296     {
3297       typedef typename iterator_traits<_InputIterator1>::value_type
3298         _ValueType1;
3299       typedef typename iterator_traits<_InputIterator2>::value_type
3300         _ValueType2;
3301
3302       // concept requirements
3303       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
3304       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
3305       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
3306                                   _ValueType1, _ValueType2>)
3307       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
3308                                   _ValueType2, _ValueType1>)
3309       __glibcxx_requires_sorted_pred(__first1, __last1, __comp);
3310       __glibcxx_requires_sorted_pred(__first2, __last2, __comp);
3311
3312       while (__first1 != __last1 && __first2 != __last2)
3313         if (__comp(*__first2, *__first1))
3314           return false;
3315         else if(__comp(*__first1, *__first2))
3316           ++__first1;
3317         else
3318           ++__first1, ++__first2;
3319
3320       return __first2 == __last2;
3321     }
3322
3323   // nth_element
3324   // merge
3325   // set_difference
3326   // set_intersection
3327   // set_union
3328   // stable_sort
3329   // set_symmetric_difference
3330   // min_element
3331   // max_element
3332
3333   /**
3334    *  @brief  Permute range into the next "dictionary" ordering.
3335    *  @param  first  Start of range.
3336    *  @param  last   End of range.
3337    *  @return  False if wrapped to first permutation, true otherwise.
3338    *
3339    *  Treats all permutations of the range as a set of "dictionary" sorted
3340    *  sequences.  Permutes the current sequence into the next one of this set.
3341    *  Returns true if there are more sequences to generate.  If the sequence
3342    *  is the largest of the set, the smallest is generated and false returned.
3343   */
3344   template<typename _BidirectionalIterator>
3345     bool
3346     next_permutation(_BidirectionalIterator __first,
3347                      _BidirectionalIterator __last)
3348     {
3349       // concept requirements
3350       __glibcxx_function_requires(_BidirectionalIteratorConcept<
3351                                   _BidirectionalIterator>)
3352       __glibcxx_function_requires(_LessThanComparableConcept<
3353             typename iterator_traits<_BidirectionalIterator>::value_type>)
3354       __glibcxx_requires_valid_range(__first, __last);
3355
3356       if (__first == __last)
3357         return false;
3358       _BidirectionalIterator __i = __first;
3359       ++__i;
3360       if (__i == __last)
3361         return false;
3362       __i = __last;
3363       --__i;
3364
3365       for(;;)
3366         {
3367           _BidirectionalIterator __ii = __i;
3368           --__i;
3369           if (*__i < *__ii)
3370             {
3371               _BidirectionalIterator __j = __last;
3372               while (!(*__i < *--__j))
3373                 {}
3374               std::iter_swap(__i, __j);
3375               std::reverse(__ii, __last);
3376               return true;
3377             }
3378           if (__i == __first)
3379             {
3380               std::reverse(__first, __last);
3381               return false;
3382             }
3383         }
3384     }
3385
3386   /**
3387    *  @brief  Permute range into the next "dictionary" ordering using
3388    *  comparison functor.
3389    *  @param  first  Start of range.
3390    *  @param  last   End of range.
3391    *  @param  comp
3392    *  @return  False if wrapped to first permutation, true otherwise.
3393    *
3394    *  Treats all permutations of the range [first,last) as a set of
3395    *  "dictionary" sorted sequences ordered by @a comp.  Permutes the current
3396    *  sequence into the next one of this set.  Returns true if there are more
3397    *  sequences to generate.  If the sequence is the largest of the set, the
3398    *  smallest is generated and false returned.
3399   */
3400   template<typename _BidirectionalIterator, typename _Compare>
3401     bool
3402     next_permutation(_BidirectionalIterator __first,
3403                      _BidirectionalIterator __last, _Compare __comp)
3404     {
3405       // concept requirements
3406       __glibcxx_function_requires(_BidirectionalIteratorConcept<
3407                                   _BidirectionalIterator>)
3408       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
3409             typename iterator_traits<_BidirectionalIterator>::value_type,
3410             typename iterator_traits<_BidirectionalIterator>::value_type>)
3411       __glibcxx_requires_valid_range(__first, __last);
3412
3413       if (__first == __last)
3414         return false;
3415       _BidirectionalIterator __i = __first;
3416       ++__i;
3417       if (__i == __last)
3418         return false;
3419       __i = __last;
3420       --__i;
3421
3422       for(;;)
3423         {
3424           _BidirectionalIterator __ii = __i;
3425           --__i;
3426           if (__comp(*__i, *__ii))
3427             {
3428               _BidirectionalIterator __j = __last;
3429               while (!bool(__comp(*__i, *--__j)))
3430                 {}
3431               std::iter_swap(__i, __j);
3432               std::reverse(__ii, __last);
3433               return true;
3434             }
3435           if (__i == __first)
3436             {
3437               std::reverse(__first, __last);
3438               return false;
3439             }
3440         }
3441     }
3442
3443   /**
3444    *  @brief  Permute range into the previous "dictionary" ordering.
3445    *  @param  first  Start of range.
3446    *  @param  last   End of range.
3447    *  @return  False if wrapped to last permutation, true otherwise.
3448    *
3449    *  Treats all permutations of the range as a set of "dictionary" sorted
3450    *  sequences.  Permutes the current sequence into the previous one of this
3451    *  set.  Returns true if there are more sequences to generate.  If the
3452    *  sequence is the smallest of the set, the largest is generated and false
3453    *  returned.
3454   */
3455   template<typename _BidirectionalIterator>
3456     bool
3457     prev_permutation(_BidirectionalIterator __first,
3458                      _BidirectionalIterator __last)
3459     {
3460       // concept requirements
3461       __glibcxx_function_requires(_BidirectionalIteratorConcept<
3462                                   _BidirectionalIterator>)
3463       __glibcxx_function_requires(_LessThanComparableConcept<
3464             typename iterator_traits<_BidirectionalIterator>::value_type>)
3465       __glibcxx_requires_valid_range(__first, __last);
3466
3467       if (__first == __last)
3468         return false;
3469       _BidirectionalIterator __i = __first;
3470       ++__i;
3471       if (__i == __last)
3472         return false;
3473       __i = __last;
3474       --__i;
3475
3476       for(;;)
3477         {
3478           _BidirectionalIterator __ii = __i;
3479           --__i;
3480           if (*__ii < *__i)
3481             {
3482               _BidirectionalIterator __j = __last;
3483               while (!(*--__j < *__i))
3484                 {}
3485               std::iter_swap(__i, __j);
3486               std::reverse(__ii, __last);
3487               return true;
3488             }
3489           if (__i == __first)
3490             {
3491               std::reverse(__first, __last);
3492               return false;
3493             }
3494         }
3495     }
3496
3497   /**
3498    *  @brief  Permute range into the previous "dictionary" ordering using
3499    *  comparison functor.
3500    *  @param  first  Start of range.
3501    *  @param  last   End of range.
3502    *  @param  comp
3503    *  @return  False if wrapped to last permutation, true otherwise.
3504    *
3505    *  Treats all permutations of the range [first,last) as a set of
3506    *  "dictionary" sorted sequences ordered by @a comp.  Permutes the current
3507    *  sequence into the previous one of this set.  Returns true if there are
3508    *  more sequences to generate.  If the sequence is the smallest of the set,
3509    *  the largest is generated and false returned.
3510   */
3511   template<typename _BidirectionalIterator, typename _Compare>
3512     bool
3513     prev_permutation(_BidirectionalIterator __first,
3514                      _BidirectionalIterator __last, _Compare __comp)
3515     {
3516       // concept requirements
3517       __glibcxx_function_requires(_BidirectionalIteratorConcept<
3518                                   _BidirectionalIterator>)
3519       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
3520             typename iterator_traits<_BidirectionalIterator>::value_type,
3521             typename iterator_traits<_BidirectionalIterator>::value_type>)
3522       __glibcxx_requires_valid_range(__first, __last);
3523
3524       if (__first == __last)
3525         return false;
3526       _BidirectionalIterator __i = __first;
3527       ++__i;
3528       if (__i == __last)
3529         return false;
3530       __i = __last;
3531       --__i;
3532
3533       for(;;)
3534         {
3535           _BidirectionalIterator __ii = __i;
3536           --__i;
3537           if (__comp(*__ii, *__i))
3538             {
3539               _BidirectionalIterator __j = __last;
3540               while (!bool(__comp(*--__j, *__i)))
3541                 {}
3542               std::iter_swap(__i, __j);
3543               std::reverse(__ii, __last);
3544               return true;
3545             }
3546           if (__i == __first)
3547             {
3548               std::reverse(__first, __last);
3549               return false;
3550             }
3551         }
3552     }
3553
3554   // replace
3555   // replace_if
3556
3557   /**
3558    *  @brief Copy a sequence, replacing each element of one value with another
3559    *         value.
3560    *  @param  first      An input iterator.
3561    *  @param  last       An input iterator.
3562    *  @param  result     An output iterator.
3563    *  @param  old_value  The value to be replaced.
3564    *  @param  new_value  The replacement value.
3565    *  @return   The end of the output sequence, @p result+(last-first).
3566    *
3567    *  Copies each element in the input range @p [first,last) to the
3568    *  output range @p [result,result+(last-first)) replacing elements
3569    *  equal to @p old_value with @p new_value.
3570   */
3571   template<typename _InputIterator, typename _OutputIterator, typename _Tp>
3572     _OutputIterator
3573     replace_copy(_InputIterator __first, _InputIterator __last,
3574                  _OutputIterator __result,
3575                  const _Tp& __old_value, const _Tp& __new_value)
3576     {
3577       // concept requirements
3578       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
3579       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
3580             typename iterator_traits<_InputIterator>::value_type>)
3581       __glibcxx_function_requires(_EqualOpConcept<
3582             typename iterator_traits<_InputIterator>::value_type, _Tp>)
3583       __glibcxx_requires_valid_range(__first, __last);
3584
3585       for (; __first != __last; ++__first, ++__result)
3586         if (*__first == __old_value)
3587           *__result = __new_value;
3588         else
3589           *__result = *__first;
3590       return __result;
3591     }
3592
3593   /**
3594    *  @brief Copy a sequence, replacing each value for which a predicate
3595    *         returns true with another value.
3596    *  @param  first      An input iterator.
3597    *  @param  last       An input iterator.
3598    *  @param  result     An output iterator.
3599    *  @param  pred       A predicate.
3600    *  @param  new_value  The replacement value.
3601    *  @return   The end of the output sequence, @p result+(last-first).
3602    *
3603    *  Copies each element in the range @p [first,last) to the range
3604    *  @p [result,result+(last-first)) replacing elements for which
3605    *  @p pred returns true with @p new_value.
3606   */
3607   template<typename _InputIterator, typename _OutputIterator,
3608            typename _Predicate, typename _Tp>
3609     _OutputIterator
3610     replace_copy_if(_InputIterator __first, _InputIterator __last,
3611                     _OutputIterator __result,
3612                     _Predicate __pred, const _Tp& __new_value)
3613     {
3614       // concept requirements
3615       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
3616       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
3617             typename iterator_traits<_InputIterator>::value_type>)
3618       __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
3619             typename iterator_traits<_InputIterator>::value_type>)
3620       __glibcxx_requires_valid_range(__first, __last);
3621
3622       for (; __first != __last; ++__first, ++__result)
3623         if (__pred(*__first))
3624           *__result = __new_value;
3625         else
3626           *__result = *__first;
3627       return __result;
3628     }
3629
3630 _GLIBCXX_END_NAMESPACE
3631
3632 _GLIBCXX_BEGIN_NESTED_NAMESPACE(std, _GLIBCXX_STD_P)
3633
3634   /**
3635    *  @brief Apply a function to every element of a sequence.
3636    *  @param  first  An input iterator.
3637    *  @param  last   An input iterator.
3638    *  @param  f      A unary function object.
3639    *  @return   @p f.
3640    *
3641    *  Applies the function object @p f to each element in the range
3642    *  @p [first,last).  @p f must not modify the order of the sequence.
3643    *  If @p f has a return value it is ignored.
3644   */
3645   template<typename _InputIterator, typename _Function>
3646     _Function
3647     for_each(_InputIterator __first, _InputIterator __last, _Function __f)
3648     {
3649       // concept requirements
3650       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
3651       __glibcxx_requires_valid_range(__first, __last);
3652       for (; __first != __last; ++__first)
3653         __f(*__first);
3654       return __f;
3655     }
3656
3657   /**
3658    *  @brief Find the first occurrence of a value in a sequence.
3659    *  @param  first  An input iterator.
3660    *  @param  last   An input iterator.
3661    *  @param  val    The value to find.
3662    *  @return   The first iterator @c i in the range @p [first,last)
3663    *  such that @c *i == @p val, or @p last if no such iterator exists.
3664   */
3665   template<typename _InputIterator, typename _Tp>
3666     inline _InputIterator
3667     find(_InputIterator __first, _InputIterator __last,
3668          const _Tp& __val)
3669     {
3670       // concept requirements
3671       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
3672       __glibcxx_function_requires(_EqualOpConcept<
3673                 typename iterator_traits<_InputIterator>::value_type, _Tp>)
3674       __glibcxx_requires_valid_range(__first, __last);
3675       return std::__find(__first, __last, __val,
3676                          std::__iterator_category(__first));
3677     }
3678
3679   /**
3680    *  @brief Find the first element in a sequence for which a
3681    *         predicate is true.
3682    *  @param  first  An input iterator.
3683    *  @param  last   An input iterator.
3684    *  @param  pred   A predicate.
3685    *  @return   The first iterator @c i in the range @p [first,last)
3686    *  such that @p pred(*i) is true, or @p last if no such iterator exists.
3687   */
3688   template<typename _InputIterator, typename _Predicate>
3689     inline _InputIterator
3690     find_if(_InputIterator __first, _InputIterator __last,
3691             _Predicate __pred)
3692     {
3693       // concept requirements
3694       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
3695       __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
3696               typename iterator_traits<_InputIterator>::value_type>)
3697       __glibcxx_requires_valid_range(__first, __last);
3698       return std::__find_if(__first, __last, __pred,
3699                             std::__iterator_category(__first));
3700     }
3701
3702   /**
3703    *  @brief  Find element from a set in a sequence.
3704    *  @param  first1  Start of range to search.
3705    *  @param  last1   End of range to search.
3706    *  @param  first2  Start of match candidates.
3707    *  @param  last2   End of match candidates.
3708    *  @return   The first iterator @c i in the range
3709    *  @p [first1,last1) such that @c *i == @p *(i2) such that i2 is an
3710    *  interator in [first2,last2), or @p last1 if no such iterator exists.
3711    *
3712    *  Searches the range @p [first1,last1) for an element that is equal to
3713    *  some element in the range [first2,last2).  If found, returns an iterator
3714    *  in the range [first1,last1), otherwise returns @p last1.
3715   */
3716   template<typename _InputIterator, typename _ForwardIterator>
3717     _InputIterator
3718     find_first_of(_InputIterator __first1, _InputIterator __last1,
3719                   _ForwardIterator __first2, _ForwardIterator __last2)
3720     {
3721       // concept requirements
3722       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
3723       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
3724       __glibcxx_function_requires(_EqualOpConcept<
3725             typename iterator_traits<_InputIterator>::value_type,
3726             typename iterator_traits<_ForwardIterator>::value_type>)
3727       __glibcxx_requires_valid_range(__first1, __last1);
3728       __glibcxx_requires_valid_range(__first2, __last2);
3729
3730       for (; __first1 != __last1; ++__first1)
3731         for (_ForwardIterator __iter = __first2; __iter != __last2; ++__iter)
3732           if (*__first1 == *__iter)
3733             return __first1;
3734       return __last1;
3735     }
3736
3737   /**
3738    *  @brief  Find element from a set in a sequence using a predicate.
3739    *  @param  first1  Start of range to search.
3740    *  @param  last1   End of range to search.
3741    *  @param  first2  Start of match candidates.
3742    *  @param  last2   End of match candidates.
3743    *  @param  comp    Predicate to use.
3744    *  @return   The first iterator @c i in the range
3745    *  @p [first1,last1) such that @c comp(*i, @p *(i2)) is true and i2 is an
3746    *  interator in [first2,last2), or @p last1 if no such iterator exists.
3747    *
3748
3749    *  Searches the range @p [first1,last1) for an element that is
3750    *  equal to some element in the range [first2,last2).  If found,
3751    *  returns an iterator in the range [first1,last1), otherwise
3752    *  returns @p last1.
3753   */
3754   template<typename _InputIterator, typename _ForwardIterator,
3755            typename _BinaryPredicate>
3756     _InputIterator
3757     find_first_of(_InputIterator __first1, _InputIterator __last1,
3758                   _ForwardIterator __first2, _ForwardIterator __last2,
3759                   _BinaryPredicate __comp)
3760     {
3761       // concept requirements
3762       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
3763       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
3764       __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
3765             typename iterator_traits<_InputIterator>::value_type,
3766             typename iterator_traits<_ForwardIterator>::value_type>)
3767       __glibcxx_requires_valid_range(__first1, __last1);
3768       __glibcxx_requires_valid_range(__first2, __last2);
3769
3770       for (; __first1 != __last1; ++__first1)
3771         for (_ForwardIterator __iter = __first2; __iter != __last2; ++__iter)
3772           if (__comp(*__first1, *__iter))
3773             return __first1;
3774       return __last1;
3775     }
3776
3777   /**
3778    *  @brief Find two adjacent values in a sequence that are equal.
3779    *  @param  first  A forward iterator.
3780    *  @param  last   A forward iterator.
3781    *  @return   The first iterator @c i such that @c i and @c i+1 are both
3782    *  valid iterators in @p [first,last) and such that @c *i == @c *(i+1),
3783    *  or @p last if no such iterator exists.
3784   */
3785   template<typename _ForwardIterator>
3786     _ForwardIterator
3787     adjacent_find(_ForwardIterator __first, _ForwardIterator __last)
3788     {
3789       // concept requirements
3790       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
3791       __glibcxx_function_requires(_EqualityComparableConcept<
3792             typename iterator_traits<_ForwardIterator>::value_type>)
3793       __glibcxx_requires_valid_range(__first, __last);
3794       if (__first == __last)
3795         return __last;
3796       _ForwardIterator __next = __first;
3797       while(++__next != __last)
3798         {
3799           if (*__first == *__next)
3800             return __first;
3801           __first = __next;
3802         }
3803       return __last;
3804     }
3805
3806   /**
3807    *  @brief Find two adjacent values in a sequence using a predicate.
3808    *  @param  first         A forward iterator.
3809    *  @param  last          A forward iterator.
3810    *  @param  binary_pred   A binary predicate.
3811    *  @return   The first iterator @c i such that @c i and @c i+1 are both
3812    *  valid iterators in @p [first,last) and such that
3813    *  @p binary_pred(*i,*(i+1)) is true, or @p last if no such iterator
3814    *  exists.
3815   */
3816   template<typename _ForwardIterator, typename _BinaryPredicate>
3817     _ForwardIterator
3818     adjacent_find(_ForwardIterator __first, _ForwardIterator __last,
3819                   _BinaryPredicate __binary_pred)
3820     {
3821       // concept requirements
3822       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
3823       __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
3824             typename iterator_traits<_ForwardIterator>::value_type,
3825             typename iterator_traits<_ForwardIterator>::value_type>)
3826       __glibcxx_requires_valid_range(__first, __last);
3827       if (__first == __last)
3828         return __last;
3829       _ForwardIterator __next = __first;
3830       while(++__next != __last)
3831         {
3832           if (__binary_pred(*__first, *__next))
3833             return __first;
3834           __first = __next;
3835         }
3836       return __last;
3837     }
3838
3839   /**
3840    *  @brief Count the number of copies of a value in a sequence.
3841    *  @param  first  An input iterator.
3842    *  @param  last   An input iterator.
3843    *  @param  value  The value to be counted.
3844    *  @return   The number of iterators @c i in the range @p [first,last)
3845    *  for which @c *i == @p value
3846   */
3847   template<typename _InputIterator, typename _Tp>
3848     typename iterator_traits<_InputIterator>::difference_type
3849     count(_InputIterator __first, _InputIterator __last, const _Tp& __value)
3850     {
3851       // concept requirements
3852       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
3853       __glibcxx_function_requires(_EqualOpConcept<
3854         typename iterator_traits<_InputIterator>::value_type, _Tp>)
3855       __glibcxx_requires_valid_range(__first, __last);
3856       typename iterator_traits<_InputIterator>::difference_type __n = 0;
3857       for (; __first != __last; ++__first)
3858         if (*__first == __value)
3859           ++__n;
3860       return __n;
3861     }
3862
3863   /**
3864    *  @brief Count the elements of a sequence for which a predicate is true.
3865    *  @param  first  An input iterator.
3866    *  @param  last   An input iterator.
3867    *  @param  pred   A predicate.
3868    *  @return   The number of iterators @c i in the range @p [first,last)
3869    *  for which @p pred(*i) is true.
3870   */
3871   template<typename _InputIterator, typename _Predicate>
3872     typename iterator_traits<_InputIterator>::difference_type
3873     count_if(_InputIterator __first, _InputIterator __last, _Predicate __pred)
3874     {
3875       // concept requirements
3876       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
3877       __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
3878             typename iterator_traits<_InputIterator>::value_type>)
3879       __glibcxx_requires_valid_range(__first, __last);
3880       typename iterator_traits<_InputIterator>::difference_type __n = 0;
3881       for (; __first != __last; ++__first)
3882         if (__pred(*__first))
3883           ++__n;
3884       return __n;
3885     }
3886
3887   /**
3888    *  @brief Search a sequence for a matching sub-sequence.
3889    *  @param  first1  A forward iterator.
3890    *  @param  last1   A forward iterator.
3891    *  @param  first2  A forward iterator.
3892    *  @param  last2   A forward iterator.
3893    *  @return   The first iterator @c i in the range
3894    *  @p [first1,last1-(last2-first2)) such that @c *(i+N) == @p *(first2+N)
3895    *  for each @c N in the range @p [0,last2-first2), or @p last1 if no
3896    *  such iterator exists.
3897    *
3898    *  Searches the range @p [first1,last1) for a sub-sequence that compares
3899    *  equal value-by-value with the sequence given by @p [first2,last2) and
3900    *  returns an iterator to the first element of the sub-sequence, or
3901    *  @p last1 if the sub-sequence is not found.
3902    *
3903    *  Because the sub-sequence must lie completely within the range
3904    *  @p [first1,last1) it must start at a position less than
3905    *  @p last1-(last2-first2) where @p last2-first2 is the length of the
3906    *  sub-sequence.
3907    *  This means that the returned iterator @c i will be in the range
3908    *  @p [first1,last1-(last2-first2))
3909   */
3910   template<typename _ForwardIterator1, typename _ForwardIterator2>
3911     _ForwardIterator1
3912     search(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
3913            _ForwardIterator2 __first2, _ForwardIterator2 __last2)
3914     {
3915       // concept requirements
3916       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator1>)
3917       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator2>)
3918       __glibcxx_function_requires(_EqualOpConcept<
3919             typename iterator_traits<_ForwardIterator1>::value_type,
3920             typename iterator_traits<_ForwardIterator2>::value_type>)
3921       __glibcxx_requires_valid_range(__first1, __last1);
3922       __glibcxx_requires_valid_range(__first2, __last2);
3923
3924       // Test for empty ranges
3925       if (__first1 == __last1 || __first2 == __last2)
3926         return __first1;
3927
3928       // Test for a pattern of length 1.
3929       _ForwardIterator2 __p1(__first2);
3930       if (++__p1 == __last2)
3931         return _GLIBCXX_STD_P::find(__first1, __last1, *__first2);
3932
3933       // General case.
3934       _ForwardIterator2 __p;
3935       _ForwardIterator1 __current = __first1;
3936
3937       for (;;)
3938         {
3939           __first1 = _GLIBCXX_STD_P::find(__first1, __last1, *__first2);
3940           if (__first1 == __last1)
3941             return __last1;
3942
3943           __p = __p1;
3944           __current = __first1;
3945           if (++__current == __last1)
3946             return __last1;
3947
3948           while (*__current == *__p)
3949             {
3950               if (++__p == __last2)
3951                 return __first1;
3952               if (++__current == __last1)
3953                 return __last1;
3954             }
3955           ++__first1;
3956         }
3957       return __first1;
3958     }
3959
3960   /**
3961    *  @brief Search a sequence for a matching sub-sequence using a predicate.
3962    *  @param  first1     A forward iterator.
3963    *  @param  last1      A forward iterator.
3964    *  @param  first2     A forward iterator.
3965    *  @param  last2      A forward iterator.
3966    *  @param  predicate  A binary predicate.
3967    *  @return   The first iterator @c i in the range
3968    *  @p [first1,last1-(last2-first2)) such that
3969    *  @p predicate(*(i+N),*(first2+N)) is true for each @c N in the range
3970    *  @p [0,last2-first2), or @p last1 if no such iterator exists.
3971    *
3972    *  Searches the range @p [first1,last1) for a sub-sequence that compares
3973    *  equal value-by-value with the sequence given by @p [first2,last2),
3974    *  using @p predicate to determine equality, and returns an iterator
3975    *  to the first element of the sub-sequence, or @p last1 if no such
3976    *  iterator exists.
3977    *
3978    *  @see search(_ForwardIter1, _ForwardIter1, _ForwardIter2, _ForwardIter2)
3979   */
3980   template<typename _ForwardIterator1, typename _ForwardIterator2,
3981            typename _BinaryPredicate>
3982     _ForwardIterator1
3983     search(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
3984            _ForwardIterator2 __first2, _ForwardIterator2 __last2,
3985            _BinaryPredicate  __predicate)
3986     {
3987       // concept requirements
3988       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator1>)
3989       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator2>)
3990       __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
3991             typename iterator_traits<_ForwardIterator1>::value_type,
3992             typename iterator_traits<_ForwardIterator2>::value_type>)
3993       __glibcxx_requires_valid_range(__first1, __last1);
3994       __glibcxx_requires_valid_range(__first2, __last2);
3995
3996       // Test for empty ranges
3997       if (__first1 == __last1 || __first2 == __last2)
3998         return __first1;
3999
4000       // Test for a pattern of length 1.
4001       _ForwardIterator2 __p1(__first2);
4002       if (++__p1 == __last2)
4003         {
4004           while (__first1 != __last1
4005                  && !bool(__predicate(*__first1, *__first2)))
4006             ++__first1;
4007           return __first1;
4008         }
4009
4010       // General case.
4011       _ForwardIterator2 __p;
4012       _ForwardIterator1 __current = __first1;
4013
4014       for (;;)
4015         {
4016           while (__first1 != __last1
4017                  && !bool(__predicate(*__first1, *__first2)))
4018             ++__first1;
4019           if (__first1 == __last1)
4020             return __last1;
4021
4022           __p = __p1;
4023           __current = __first1;
4024           if (++__current == __last1)
4025             return __last1;
4026
4027           while (__predicate(*__current, *__p))
4028             {
4029               if (++__p == __last2)
4030                 return __first1;
4031               if (++__current == __last1)
4032                 return __last1;
4033             }
4034           ++__first1;
4035         }
4036       return __first1;
4037     }
4038
4039
4040   /**
4041    *  @brief Search a sequence for a number of consecutive values.
4042    *  @param  first  A forward iterator.
4043    *  @param  last   A forward iterator.
4044    *  @param  count  The number of consecutive values.
4045    *  @param  val    The value to find.
4046    *  @return   The first iterator @c i in the range @p [first,last-count)
4047    *  such that @c *(i+N) == @p val for each @c N in the range @p [0,count),
4048    *  or @p last if no such iterator exists.
4049    *
4050    *  Searches the range @p [first,last) for @p count consecutive elements
4051    *  equal to @p val.
4052   */
4053   template<typename _ForwardIterator, typename _Integer, typename _Tp>
4054     _ForwardIterator
4055     search_n(_ForwardIterator __first, _ForwardIterator __last,
4056              _Integer __count, const _Tp& __val)
4057     {
4058       // concept requirements
4059       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
4060       __glibcxx_function_requires(_EqualOpConcept<
4061         typename iterator_traits<_ForwardIterator>::value_type, _Tp>)
4062       __glibcxx_requires_valid_range(__first, __last);
4063
4064       if (__count <= 0)
4065         return __first;
4066       if (__count == 1)
4067         return _GLIBCXX_STD_P::find(__first, __last, __val);
4068       return std::__search_n(__first, __last, __count, __val,
4069                              std::__iterator_category(__first));
4070     }
4071
4072
4073   /**
4074    *  @brief Search a sequence for a number of consecutive values using a
4075    *         predicate.
4076    *  @param  first        A forward iterator.
4077    *  @param  last         A forward iterator.
4078    *  @param  count        The number of consecutive values.
4079    *  @param  val          The value to find.
4080    *  @param  binary_pred  A binary predicate.
4081    *  @return   The first iterator @c i in the range @p [first,last-count)
4082    *  such that @p binary_pred(*(i+N),val) is true for each @c N in the
4083    *  range @p [0,count), or @p last if no such iterator exists.
4084    *
4085    *  Searches the range @p [first,last) for @p count consecutive elements
4086    *  for which the predicate returns true.
4087   */
4088   template<typename _ForwardIterator, typename _Integer, typename _Tp,
4089            typename _BinaryPredicate>
4090     _ForwardIterator
4091     search_n(_ForwardIterator __first, _ForwardIterator __last,
4092              _Integer __count, const _Tp& __val,
4093              _BinaryPredicate __binary_pred)
4094     {
4095       // concept requirements
4096       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
4097       __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
4098             typename iterator_traits<_ForwardIterator>::value_type, _Tp>)
4099       __glibcxx_requires_valid_range(__first, __last);
4100
4101       if (__count <= 0)
4102         return __first;
4103       if (__count == 1)
4104         {
4105           while (__first != __last && !bool(__binary_pred(*__first, __val)))
4106             ++__first;
4107           return __first;
4108         }
4109       return std::__search_n(__first, __last, __count, __val, __binary_pred,
4110                              std::__iterator_category(__first));
4111     }
4112
4113
4114   /**
4115    *  @brief Perform an operation on a sequence.
4116    *  @param  first     An input iterator.
4117    *  @param  last      An input iterator.
4118    *  @param  result    An output iterator.
4119    *  @param  unary_op  A unary operator.
4120    *  @return   An output iterator equal to @p result+(last-first).
4121    *
4122    *  Applies the operator to each element in the input range and assigns
4123    *  the results to successive elements of the output sequence.
4124    *  Evaluates @p *(result+N)=unary_op(*(first+N)) for each @c N in the
4125    *  range @p [0,last-first).
4126    *
4127    *  @p unary_op must not alter its argument.
4128   */
4129   template<typename _InputIterator, typename _OutputIterator,
4130            typename _UnaryOperation>
4131     _OutputIterator
4132     transform(_InputIterator __first, _InputIterator __last,
4133               _OutputIterator __result, _UnaryOperation __unary_op)
4134     {
4135       // concept requirements
4136       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
4137       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
4138             // "the type returned by a _UnaryOperation"
4139             __typeof__(__unary_op(*__first))>)
4140       __glibcxx_requires_valid_range(__first, __last);
4141
4142       for (; __first != __last; ++__first, ++__result)
4143         *__result = __unary_op(*__first);
4144       return __result;
4145     }
4146
4147   /**
4148    *  @brief Perform an operation on corresponding elements of two sequences.
4149    *  @param  first1     An input iterator.
4150    *  @param  last1      An input iterator.
4151    *  @param  first2     An input iterator.
4152    *  @param  result     An output iterator.
4153    *  @param  binary_op  A binary operator.
4154    *  @return   An output iterator equal to @p result+(last-first).
4155    *
4156    *  Applies the operator to the corresponding elements in the two
4157    *  input ranges and assigns the results to successive elements of the
4158    *  output sequence.
4159    *  Evaluates @p *(result+N)=binary_op(*(first1+N),*(first2+N)) for each
4160    *  @c N in the range @p [0,last1-first1).
4161    *
4162    *  @p binary_op must not alter either of its arguments.
4163   */
4164   template<typename _InputIterator1, typename _InputIterator2,
4165            typename _OutputIterator, typename _BinaryOperation>
4166     _OutputIterator
4167     transform(_InputIterator1 __first1, _InputIterator1 __last1,
4168               _InputIterator2 __first2, _OutputIterator __result,
4169               _BinaryOperation __binary_op)
4170     {
4171       // concept requirements
4172       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
4173       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
4174       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
4175             // "the type returned by a _BinaryOperation"
4176             __typeof__(__binary_op(*__first1,*__first2))>)
4177       __glibcxx_requires_valid_range(__first1, __last1);
4178
4179       for (; __first1 != __last1; ++__first1, ++__first2, ++__result)
4180         *__result = __binary_op(*__first1, *__first2);
4181       return __result;
4182     }
4183
4184   /**
4185    *  @brief Replace each occurrence of one value in a sequence with another
4186    *         value.
4187    *  @param  first      A forward iterator.
4188    *  @param  last       A forward iterator.
4189    *  @param  old_value  The value to be replaced.
4190    *  @param  new_value  The replacement value.
4191    *  @return   replace() returns no value.
4192    *
4193    *  For each iterator @c i in the range @p [first,last) if @c *i ==
4194    *  @p old_value then the assignment @c *i = @p new_value is performed.
4195   */
4196   template<typename _ForwardIterator, typename _Tp>
4197     void
4198     replace(_ForwardIterator __first, _ForwardIterator __last,
4199             const _Tp& __old_value, const _Tp& __new_value)
4200     {
4201       // concept requirements
4202       __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
4203                                   _ForwardIterator>)
4204       __glibcxx_function_requires(_EqualOpConcept<
4205             typename iterator_traits<_ForwardIterator>::value_type, _Tp>)
4206       __glibcxx_function_requires(_ConvertibleConcept<_Tp,
4207             typename iterator_traits<_ForwardIterator>::value_type>)
4208       __glibcxx_requires_valid_range(__first, __last);
4209
4210       for (; __first != __last; ++__first)
4211         if (*__first == __old_value)
4212           *__first = __new_value;
4213     }
4214
4215   /**
4216    *  @brief Replace each value in a sequence for which a predicate returns
4217    *         true with another value.
4218    *  @param  first      A forward iterator.
4219    *  @param  last       A forward iterator.
4220    *  @param  pred       A predicate.
4221    *  @param  new_value  The replacement value.
4222    *  @return   replace_if() returns no value.
4223    *
4224    *  For each iterator @c i in the range @p [first,last) if @p pred(*i)
4225    *  is true then the assignment @c *i = @p new_value is performed.
4226   */
4227   template<typename _ForwardIterator, typename _Predicate, typename _Tp>
4228     void
4229     replace_if(_ForwardIterator __first, _ForwardIterator __last,
4230                _Predicate __pred, const _Tp& __new_value)
4231     {
4232       // concept requirements
4233       __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
4234                                   _ForwardIterator>)
4235       __glibcxx_function_requires(_ConvertibleConcept<_Tp,
4236             typename iterator_traits<_ForwardIterator>::value_type>)
4237       __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
4238             typename iterator_traits<_ForwardIterator>::value_type>)
4239       __glibcxx_requires_valid_range(__first, __last);
4240
4241       for (; __first != __last; ++__first)
4242         if (__pred(*__first))
4243           *__first = __new_value;
4244     }
4245
4246   /**
4247    *  @brief Assign the result of a function object to each value in a
4248    *         sequence.
4249    *  @param  first  A forward iterator.
4250    *  @param  last   A forward iterator.
4251    *  @param  gen    A function object taking no arguments and returning
4252    *                 std::iterator_traits<_ForwardIterator>::value_type
4253    *  @return   generate() returns no value.
4254    *
4255    *  Performs the assignment @c *i = @p gen() for each @c i in the range
4256    *  @p [first,last).
4257   */
4258   template<typename _ForwardIterator, typename _Generator>
4259     void
4260     generate(_ForwardIterator __first, _ForwardIterator __last,
4261              _Generator __gen)
4262     {
4263       // concept requirements
4264       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
4265       __glibcxx_function_requires(_GeneratorConcept<_Generator,
4266             typename iterator_traits<_ForwardIterator>::value_type>)
4267       __glibcxx_requires_valid_range(__first, __last);
4268
4269       for (; __first != __last; ++__first)
4270         *__first = __gen();
4271     }
4272
4273   /**
4274    *  @brief Assign the result of a function object to each value in a
4275    *         sequence.
4276    *  @param  first  A forward iterator.
4277    *  @param  n      The length of the sequence.
4278    *  @param  gen    A function object taking no arguments and returning
4279    *                 std::iterator_traits<_ForwardIterator>::value_type
4280    *  @return   The end of the sequence, @p first+n
4281    *
4282    *  Performs the assignment @c *i = @p gen() for each @c i in the range
4283    *  @p [first,first+n).
4284   */
4285   template<typename _OutputIterator, typename _Size, typename _Generator>
4286     _OutputIterator
4287     generate_n(_OutputIterator __first, _Size __n, _Generator __gen)
4288     {
4289       // concept requirements
4290       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
4291             // "the type returned by a _Generator"
4292             __typeof__(__gen())>)
4293
4294       for (; __n > 0; --__n, ++__first)
4295         *__first = __gen();
4296       return __first;
4297     }
4298
4299
4300   /**
4301    *  @brief Copy a sequence, removing consecutive duplicate values.
4302    *  @param  first   An input iterator.
4303    *  @param  last    An input iterator.
4304    *  @param  result  An output iterator.
4305    *  @return   An iterator designating the end of the resulting sequence.
4306    *
4307    *  Copies each element in the range @p [first,last) to the range
4308    *  beginning at @p result, except that only the first element is copied
4309    *  from groups of consecutive elements that compare equal.
4310    *  unique_copy() is stable, so the relative order of elements that are
4311    *  copied is unchanged.
4312    *
4313    *  @if maint
4314    *  _GLIBCXX_RESOLVE_LIB_DEFECTS
4315    *  DR 241. Does unique_copy() require CopyConstructible and Assignable?
4316    *
4317    *  _GLIBCXX_RESOLVE_LIB_DEFECTS
4318    *  DR 538. 241 again: Does unique_copy() require CopyConstructible and
4319    *  Assignable?
4320    *  @endif
4321   */
4322   template<typename _InputIterator, typename _OutputIterator>
4323     inline _OutputIterator
4324     unique_copy(_InputIterator __first, _InputIterator __last,
4325                 _OutputIterator __result)
4326     {
4327       // concept requirements
4328       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
4329       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
4330             typename iterator_traits<_InputIterator>::value_type>)
4331       __glibcxx_function_requires(_EqualityComparableConcept<
4332             typename iterator_traits<_InputIterator>::value_type>)
4333       __glibcxx_requires_valid_range(__first, __last);
4334
4335       if (__first == __last)
4336         return __result;
4337       return std::__unique_copy(__first, __last, __result,
4338                                 std::__iterator_category(__first),
4339                                 std::__iterator_category(__result));
4340     }
4341
4342   /**
4343    *  @brief Copy a sequence, removing consecutive values using a predicate.
4344    *  @param  first        An input iterator.
4345    *  @param  last         An input iterator.
4346    *  @param  result       An output iterator.
4347    *  @param  binary_pred  A binary predicate.
4348    *  @return   An iterator designating the end of the resulting sequence.
4349    *
4350    *  Copies each element in the range @p [first,last) to the range
4351    *  beginning at @p result, except that only the first element is copied
4352    *  from groups of consecutive elements for which @p binary_pred returns
4353    *  true.
4354    *  unique_copy() is stable, so the relative order of elements that are
4355    *  copied is unchanged.
4356    *
4357    *  @if maint
4358    *  _GLIBCXX_RESOLVE_LIB_DEFECTS
4359    *  DR 241. Does unique_copy() require CopyConstructible and Assignable?
4360    *  @endif
4361   */
4362   template<typename _InputIterator, typename _OutputIterator,
4363            typename _BinaryPredicate>
4364     inline _OutputIterator
4365     unique_copy(_InputIterator __first, _InputIterator __last,
4366                 _OutputIterator __result,
4367                 _BinaryPredicate __binary_pred)
4368     {
4369       // concept requirements -- predicates checked later
4370       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
4371       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
4372             typename iterator_traits<_InputIterator>::value_type>)
4373       __glibcxx_requires_valid_range(__first, __last);
4374
4375       if (__first == __last)
4376         return __result;
4377       return std::__unique_copy(__first, __last, __result, __binary_pred,
4378                                 std::__iterator_category(__first),
4379                                 std::__iterator_category(__result));
4380     }
4381
4382
4383   /**
4384    *  @brief Randomly shuffle the elements of a sequence.
4385    *  @param  first   A forward iterator.
4386    *  @param  last    A forward iterator.
4387    *  @return  Nothing.
4388    *
4389    *  Reorder the elements in the range @p [first,last) using a random
4390    *  distribution, so that every possible ordering of the sequence is
4391    *  equally likely.
4392   */
4393   template<typename _RandomAccessIterator>
4394     inline void
4395     random_shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last)
4396     {
4397       // concept requirements
4398       __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
4399             _RandomAccessIterator>)
4400       __glibcxx_requires_valid_range(__first, __last);
4401
4402       if (__first != __last)
4403         for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i)
4404           std::iter_swap(__i, __first + (std::rand() % ((__i - __first) + 1)));
4405     }
4406
4407   /**
4408    *  @brief Shuffle the elements of a sequence using a random number
4409    *         generator.
4410    *  @param  first   A forward iterator.
4411    *  @param  last    A forward iterator.
4412    *  @param  rand    The RNG functor or function.
4413    *  @return  Nothing.
4414    *
4415    *  Reorders the elements in the range @p [first,last) using @p rand to
4416    *  provide a random distribution. Calling @p rand(N) for a positive
4417    *  integer @p N should return a randomly chosen integer from the
4418    *  range [0,N).
4419   */
4420   template<typename _RandomAccessIterator, typename _RandomNumberGenerator>
4421     void
4422     random_shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last,
4423                    _RandomNumberGenerator& __rand)
4424     {
4425       // concept requirements
4426       __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
4427             _RandomAccessIterator>)
4428       __glibcxx_requires_valid_range(__first, __last);
4429
4430       if (__first == __last)
4431         return;
4432       for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i)
4433         std::iter_swap(__i, __first + __rand((__i - __first) + 1));
4434     }
4435
4436
4437   /**
4438    *  @brief Move elements for which a predicate is true to the beginning
4439    *         of a sequence.
4440    *  @param  first   A forward iterator.
4441    *  @param  last    A forward iterator.
4442    *  @param  pred    A predicate functor.
4443    *  @return  An iterator @p middle such that @p pred(i) is true for each
4444    *  iterator @p i in the range @p [first,middle) and false for each @p i
4445    *  in the range @p [middle,last).
4446    *
4447    *  @p pred must not modify its operand. @p partition() does not preserve
4448    *  the relative ordering of elements in each group, use
4449    *  @p stable_partition() if this is needed.
4450   */
4451   template<typename _ForwardIterator, typename _Predicate>
4452     inline _ForwardIterator
4453     partition(_ForwardIterator __first, _ForwardIterator __last,
4454               _Predicate   __pred)
4455     {
4456       // concept requirements
4457       __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
4458                                   _ForwardIterator>)
4459       __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
4460             typename iterator_traits<_ForwardIterator>::value_type>)
4461       __glibcxx_requires_valid_range(__first, __last);
4462
4463       return std::__partition(__first, __last, __pred,
4464                               std::__iterator_category(__first));
4465     }
4466
4467
4468
4469   /**
4470    *  @brief Sort the smallest elements of a sequence.
4471    *  @param  first   An iterator.
4472    *  @param  middle  Another iterator.
4473    *  @param  last    Another iterator.
4474    *  @return  Nothing.
4475    *
4476    *  Sorts the smallest @p (middle-first) elements in the range
4477    *  @p [first,last) and moves them to the range @p [first,middle). The
4478    *  order of the remaining elements in the range @p [middle,last) is
4479    *  undefined.
4480    *  After the sort if @p i and @j are iterators in the range
4481    *  @p [first,middle) such that @i precedes @j and @k is an iterator in
4482    *  the range @p [middle,last) then @p *j<*i and @p *k<*i are both false.
4483   */
4484   template<typename _RandomAccessIterator>
4485     inline void
4486     partial_sort(_RandomAccessIterator __first,
4487                  _RandomAccessIterator __middle,
4488                  _RandomAccessIterator __last)
4489     {
4490       typedef typename iterator_traits<_RandomAccessIterator>::value_type
4491         _ValueType;
4492
4493       // concept requirements
4494       __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
4495             _RandomAccessIterator>)
4496       __glibcxx_function_requires(_LessThanComparableConcept<_ValueType>)
4497       __glibcxx_requires_valid_range(__first, __middle);
4498       __glibcxx_requires_valid_range(__middle, __last);
4499
4500       std::__heap_select(__first, __middle, __last);
4501       std::sort_heap(__first, __middle);
4502     }
4503
4504   /**
4505    *  @brief Sort the smallest elements of a sequence using a predicate
4506    *         for comparison.
4507    *  @param  first   An iterator.
4508    *  @param  middle  Another iterator.
4509    *  @param  last    Another iterator.
4510    *  @param  comp    A comparison functor.
4511    *  @return  Nothing.
4512    *
4513    *  Sorts the smallest @p (middle-first) elements in the range
4514    *  @p [first,last) and moves them to the range @p [first,middle). The
4515    *  order of the remaining elements in the range @p [middle,last) is
4516    *  undefined.
4517    *  After the sort if @p i and @j are iterators in the range
4518    *  @p [first,middle) such that @i precedes @j and @k is an iterator in
4519    *  the range @p [middle,last) then @p *comp(j,*i) and @p comp(*k,*i)
4520    *  are both false.
4521   */
4522   template<typename _RandomAccessIterator, typename _Compare>
4523     inline void
4524     partial_sort(_RandomAccessIterator __first,
4525                  _RandomAccessIterator __middle,
4526                  _RandomAccessIterator __last,
4527                  _Compare __comp)
4528     {
4529       typedef typename iterator_traits<_RandomAccessIterator>::value_type
4530         _ValueType;
4531
4532       // concept requirements
4533       __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
4534             _RandomAccessIterator>)
4535       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
4536                                   _ValueType, _ValueType>)
4537       __glibcxx_requires_valid_range(__first, __middle);
4538       __glibcxx_requires_valid_range(__middle, __last);
4539
4540       std::__heap_select(__first, __middle, __last, __comp);
4541       std::sort_heap(__first, __middle, __comp);
4542     }
4543
4544   /**
4545    *  @brief Sort a sequence just enough to find a particular position.
4546    *  @param  first   An iterator.
4547    *  @param  nth     Another iterator.
4548    *  @param  last    Another iterator.
4549    *  @return  Nothing.
4550    *
4551    *  Rearranges the elements in the range @p [first,last) so that @p *nth
4552    *  is the same element that would have been in that position had the
4553    *  whole sequence been sorted.
4554    *  whole sequence been sorted. The elements either side of @p *nth are
4555    *  not completely sorted, but for any iterator @i in the range
4556    *  @p [first,nth) and any iterator @j in the range @p [nth,last) it
4557    *  holds that @p *j<*i is false.
4558   */
4559   template<typename _RandomAccessIterator>
4560     inline void
4561     nth_element(_RandomAccessIterator __first, _RandomAccessIterator __nth,
4562                 _RandomAccessIterator __last)
4563     {
4564       typedef typename iterator_traits<_RandomAccessIterator>::value_type
4565         _ValueType;
4566
4567       // concept requirements
4568       __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
4569                                   _RandomAccessIterator>)
4570       __glibcxx_function_requires(_LessThanComparableConcept<_ValueType>)
4571       __glibcxx_requires_valid_range(__first, __nth);
4572       __glibcxx_requires_valid_range(__nth, __last);
4573
4574       if (__first == __last || __nth == __last)
4575         return;
4576
4577       std::__introselect(__first, __nth, __last,
4578                          std::__lg(__last - __first) * 2);
4579     }
4580
4581   /**
4582    *  @brief Sort a sequence just enough to find a particular position
4583    *         using a predicate for comparison.
4584    *  @param  first   An iterator.
4585    *  @param  nth     Another iterator.
4586    *  @param  last    Another iterator.
4587    *  @param  comp    A comparison functor.
4588    *  @return  Nothing.
4589    *
4590    *  Rearranges the elements in the range @p [first,last) so that @p *nth
4591    *  is the same element that would have been in that position had the
4592    *  whole sequence been sorted. The elements either side of @p *nth are
4593    *  not completely sorted, but for any iterator @i in the range
4594    *  @p [first,nth) and any iterator @j in the range @p [nth,last) it
4595    *  holds that @p comp(*j,*i) is false.
4596   */
4597   template<typename _RandomAccessIterator, typename _Compare>
4598     inline void
4599     nth_element(_RandomAccessIterator __first, _RandomAccessIterator __nth,
4600                 _RandomAccessIterator __last, _Compare __comp)
4601     {
4602       typedef typename iterator_traits<_RandomAccessIterator>::value_type
4603         _ValueType;
4604
4605       // concept requirements
4606       __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
4607                                   _RandomAccessIterator>)
4608       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
4609                                   _ValueType, _ValueType>)
4610       __glibcxx_requires_valid_range(__first, __nth);
4611       __glibcxx_requires_valid_range(__nth, __last);
4612
4613       if (__first == __last || __nth == __last)
4614         return;
4615
4616       std::__introselect(__first, __nth, __last,
4617                          std::__lg(__last - __first) * 2, __comp);
4618     }
4619
4620
4621   /**
4622    *  @brief Sort the elements of a sequence.
4623    *  @param  first   An iterator.
4624    *  @param  last    Another iterator.
4625    *  @return  Nothing.
4626    *
4627    *  Sorts the elements in the range @p [first,last) in ascending order,
4628    *  such that @p *(i+1)<*i is false for each iterator @p i in the range
4629    *  @p [first,last-1).
4630    *
4631    *  The relative ordering of equivalent elements is not preserved, use
4632    *  @p stable_sort() if this is needed.
4633   */
4634   template<typename _RandomAccessIterator>
4635     inline void
4636     sort(_RandomAccessIterator __first, _RandomAccessIterator __last)
4637     {
4638       typedef typename iterator_traits<_RandomAccessIterator>::value_type
4639         _ValueType;
4640
4641       // concept requirements
4642       __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
4643             _RandomAccessIterator>)
4644       __glibcxx_function_requires(_LessThanComparableConcept<_ValueType>)
4645       __glibcxx_requires_valid_range(__first, __last);
4646
4647       if (__first != __last)
4648         {
4649           std::__introsort_loop(__first, __last,
4650                                 std::__lg(__last - __first) * 2);
4651           std::__final_insertion_sort(__first, __last);
4652         }
4653     }
4654
4655   /**
4656    *  @brief Sort the elements of a sequence using a predicate for comparison.
4657    *  @param  first   An iterator.
4658    *  @param  last    Another iterator.
4659    *  @param  comp    A comparison functor.
4660    *  @return  Nothing.
4661    *
4662    *  Sorts the elements in the range @p [first,last) in ascending order,
4663    *  such that @p comp(*(i+1),*i) is false for every iterator @p i in the
4664    *  range @p [first,last-1).
4665    *
4666    *  The relative ordering of equivalent elements is not preserved, use
4667    *  @p stable_sort() if this is needed.
4668   */
4669   template<typename _RandomAccessIterator, typename _Compare>
4670     inline void
4671     sort(_RandomAccessIterator __first, _RandomAccessIterator __last,
4672          _Compare __comp)
4673     {
4674       typedef typename iterator_traits<_RandomAccessIterator>::value_type
4675         _ValueType;
4676
4677       // concept requirements
4678       __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
4679             _RandomAccessIterator>)
4680       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, _ValueType,
4681                                   _ValueType>)
4682       __glibcxx_requires_valid_range(__first, __last);
4683
4684       if (__first != __last)
4685         {
4686           std::__introsort_loop(__first, __last,
4687                                 std::__lg(__last - __first) * 2, __comp);
4688           std::__final_insertion_sort(__first, __last, __comp);
4689         }
4690     }
4691
4692   /**
4693    *  @brief Merges two sorted ranges.
4694    *  @param  first1  An iterator.
4695    *  @param  first2  Another iterator.
4696    *  @param  last1   Another iterator.
4697    *  @param  last2   Another iterator.
4698    *  @param  result  An iterator pointing to the end of the merged range.
4699    *  @return         An iterator pointing to the first element "not less
4700    *                  than" @a val.
4701    *
4702    *  Merges the ranges [first1,last1) and [first2,last2) into the sorted range
4703    *  [result, result + (last1-first1) + (last2-first2)).  Both input ranges
4704    *  must be sorted, and the output range must not overlap with either of
4705    *  the input ranges.  The sort is @e stable, that is, for equivalent
4706    *  elements in the two ranges, elements from the first range will always
4707    *  come before elements from the second.
4708   */
4709   template<typename _InputIterator1, typename _InputIterator2,
4710            typename _OutputIterator>
4711     _OutputIterator
4712     merge(_InputIterator1 __first1, _InputIterator1 __last1,
4713           _InputIterator2 __first2, _InputIterator2 __last2,
4714           _OutputIterator __result)
4715     {
4716       typedef typename iterator_traits<_InputIterator1>::value_type
4717         _ValueType1;
4718       typedef typename iterator_traits<_InputIterator2>::value_type
4719         _ValueType2;
4720
4721       // concept requirements
4722       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
4723       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
4724       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
4725                                   _ValueType1>)
4726       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
4727                                   _ValueType2>)
4728       __glibcxx_function_requires(_LessThanOpConcept<_ValueType2, _ValueType1>)
4729       __glibcxx_requires_sorted(__first1, __last1);
4730       __glibcxx_requires_sorted(__first2, __last2);
4731
4732       while (__first1 != __last1 && __first2 != __last2)
4733         {
4734           if (*__first2 < *__first1)
4735             {
4736               *__result = *__first2;
4737               ++__first2;
4738             }
4739           else
4740             {
4741               *__result = *__first1;
4742               ++__first1;
4743             }
4744           ++__result;
4745         }
4746       return std::copy(__first2, __last2, std::copy(__first1, __last1,
4747                                                     __result));
4748     }
4749
4750   /**
4751    *  @brief Merges two sorted ranges.
4752    *  @param  first1  An iterator.
4753    *  @param  first2  Another iterator.
4754    *  @param  last1   Another iterator.
4755    *  @param  last2   Another iterator.
4756    *  @param  result  An iterator pointing to the end of the merged range.
4757    *  @param  comp    A functor to use for comparisons.
4758    *  @return         An iterator pointing to the first element "not less
4759    *                  than" @a val.
4760    *
4761    *  Merges the ranges [first1,last1) and [first2,last2) into the sorted range
4762    *  [result, result + (last1-first1) + (last2-first2)).  Both input ranges
4763    *  must be sorted, and the output range must not overlap with either of
4764    *  the input ranges.  The sort is @e stable, that is, for equivalent
4765    *  elements in the two ranges, elements from the first range will always
4766    *  come before elements from the second.
4767    *
4768    *  The comparison function should have the same effects on ordering as
4769    *  the function used for the initial sort.
4770   */
4771   template<typename _InputIterator1, typename _InputIterator2,
4772            typename _OutputIterator, typename _Compare>
4773     _OutputIterator
4774     merge(_InputIterator1 __first1, _InputIterator1 __last1,
4775           _InputIterator2 __first2, _InputIterator2 __last2,
4776           _OutputIterator __result, _Compare __comp)
4777     {
4778       typedef typename iterator_traits<_InputIterator1>::value_type
4779         _ValueType1;
4780       typedef typename iterator_traits<_InputIterator2>::value_type
4781         _ValueType2;
4782
4783       // concept requirements
4784       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
4785       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
4786       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
4787                                   _ValueType1>)
4788       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
4789                                   _ValueType2>)
4790       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
4791                                   _ValueType2, _ValueType1>)
4792       __glibcxx_requires_sorted_pred(__first1, __last1, __comp);
4793       __glibcxx_requires_sorted_pred(__first2, __last2, __comp);
4794
4795       while (__first1 != __last1 && __first2 != __last2)
4796         {
4797           if (__comp(*__first2, *__first1))
4798             {
4799               *__result = *__first2;
4800               ++__first2;
4801             }
4802           else
4803             {
4804               *__result = *__first1;
4805               ++__first1;
4806             }
4807           ++__result;
4808         }
4809       return std::copy(__first2, __last2, std::copy(__first1, __last1,
4810                                                     __result));
4811     }
4812
4813
4814   /**
4815    *  @brief Sort the elements of a sequence, preserving the relative order
4816    *         of equivalent elements.
4817    *  @param  first   An iterator.
4818    *  @param  last    Another iterator.
4819    *  @return  Nothing.
4820    *
4821    *  Sorts the elements in the range @p [first,last) in ascending order,
4822    *  such that @p *(i+1)<*i is false for each iterator @p i in the range
4823    *  @p [first,last-1).
4824    *
4825    *  The relative ordering of equivalent elements is preserved, so any two
4826    *  elements @p x and @p y in the range @p [first,last) such that
4827    *  @p x<y is false and @p y<x is false will have the same relative
4828    *  ordering after calling @p stable_sort().
4829   */
4830   template<typename _RandomAccessIterator>
4831     inline void
4832     stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last)
4833     {
4834       typedef typename iterator_traits<_RandomAccessIterator>::value_type
4835         _ValueType;
4836       typedef typename iterator_traits<_RandomAccessIterator>::difference_type
4837         _DistanceType;
4838
4839       // concept requirements
4840       __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
4841             _RandomAccessIterator>)
4842       __glibcxx_function_requires(_LessThanComparableConcept<_ValueType>)
4843       __glibcxx_requires_valid_range(__first, __last);
4844
4845       _Temporary_buffer<_RandomAccessIterator, _ValueType> __buf(__first,
4846                                                                  __last);
4847       if (__buf.begin() == 0)
4848         std::__inplace_stable_sort(__first, __last);
4849       else
4850         std::__stable_sort_adaptive(__first, __last, __buf.begin(),
4851                                     _DistanceType(__buf.size()));
4852     }
4853
4854   /**
4855    *  @brief Sort the elements of a sequence using a predicate for comparison,
4856    *         preserving the relative order of equivalent elements.
4857    *  @param  first   An iterator.
4858    *  @param  last    Another iterator.
4859    *  @param  comp    A comparison functor.
4860    *  @return  Nothing.
4861    *
4862    *  Sorts the elements in the range @p [first,last) in ascending order,
4863    *  such that @p comp(*(i+1),*i) is false for each iterator @p i in the
4864    *  range @p [first,last-1).
4865    *
4866    *  The relative ordering of equivalent elements is preserved, so any two
4867    *  elements @p x and @p y in the range @p [first,last) such that
4868    *  @p comp(x,y) is false and @p comp(y,x) is false will have the same
4869    *  relative ordering after calling @p stable_sort().
4870   */
4871   template<typename _RandomAccessIterator, typename _Compare>
4872     inline void
4873     stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last,
4874                 _Compare __comp)
4875     {
4876       typedef typename iterator_traits<_RandomAccessIterator>::value_type
4877         _ValueType;
4878       typedef typename iterator_traits<_RandomAccessIterator>::difference_type
4879         _DistanceType;
4880
4881       // concept requirements
4882       __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
4883             _RandomAccessIterator>)
4884       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
4885                                   _ValueType,
4886                                   _ValueType>)
4887       __glibcxx_requires_valid_range(__first, __last);
4888
4889       _Temporary_buffer<_RandomAccessIterator, _ValueType> __buf(__first,
4890                                                                  __last);
4891       if (__buf.begin() == 0)
4892         std::__inplace_stable_sort(__first, __last, __comp);
4893       else
4894         std::__stable_sort_adaptive(__first, __last, __buf.begin(),
4895                                     _DistanceType(__buf.size()), __comp);
4896     }
4897
4898
4899   /**
4900    *  @brief Return the union of two sorted ranges.
4901    *  @param  first1  Start of first range.
4902    *  @param  last1   End of first range.
4903    *  @param  first2  Start of second range.
4904    *  @param  last2   End of second range.
4905    *  @return  End of the output range.
4906    *  @ingroup setoperations
4907    *
4908    *  This operation iterates over both ranges, copying elements present in
4909    *  each range in order to the output range.  Iterators increment for each
4910    *  range.  When the current element of one range is less than the other,
4911    *  that element is copied and the iterator advanced.  If an element is
4912    *  contained in both ranges, the element from the first range is copied and
4913    *  both ranges advance.  The output range may not overlap either input
4914    *  range.
4915   */
4916   template<typename _InputIterator1, typename _InputIterator2,
4917            typename _OutputIterator>
4918     _OutputIterator
4919     set_union(_InputIterator1 __first1, _InputIterator1 __last1,
4920               _InputIterator2 __first2, _InputIterator2 __last2,
4921               _OutputIterator __result)
4922     {
4923       typedef typename iterator_traits<_InputIterator1>::value_type
4924         _ValueType1;
4925       typedef typename iterator_traits<_InputIterator2>::value_type
4926         _ValueType2;
4927
4928       // concept requirements
4929       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
4930       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
4931       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
4932                                   _ValueType1>)
4933       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
4934                                   _ValueType2>)
4935       __glibcxx_function_requires(_LessThanOpConcept<_ValueType1, _ValueType2>)
4936       __glibcxx_function_requires(_LessThanOpConcept<_ValueType2, _ValueType1>)
4937       __glibcxx_requires_sorted(__first1, __last1);
4938       __glibcxx_requires_sorted(__first2, __last2);
4939
4940       while (__first1 != __last1 && __first2 != __last2)
4941         {
4942           if (*__first1 < *__first2)
4943             {
4944               *__result = *__first1;
4945               ++__first1;
4946             }
4947           else if (*__first2 < *__first1)
4948             {
4949               *__result = *__first2;
4950               ++__first2;
4951             }
4952           else
4953             {
4954               *__result = *__first1;
4955               ++__first1;
4956               ++__first2;
4957             }
4958           ++__result;
4959         }
4960       return std::copy(__first2, __last2, std::copy(__first1, __last1,
4961                                                     __result));
4962     }
4963
4964   /**
4965    *  @brief Return the union of two sorted ranges using a comparison functor.
4966    *  @param  first1  Start of first range.
4967    *  @param  last1   End of first range.
4968    *  @param  first2  Start of second range.
4969    *  @param  last2   End of second range.
4970    *  @param  comp    The comparison functor.
4971    *  @return  End of the output range.
4972    *  @ingroup setoperations
4973    *
4974    *  This operation iterates over both ranges, copying elements present in
4975    *  each range in order to the output range.  Iterators increment for each
4976    *  range.  When the current element of one range is less than the other
4977    *  according to @a comp, that element is copied and the iterator advanced.
4978    *  If an equivalent element according to @a comp is contained in both
4979    *  ranges, the element from the first range is copied and both ranges
4980    *  advance.  The output range may not overlap either input range.
4981   */
4982   template<typename _InputIterator1, typename _InputIterator2,
4983            typename _OutputIterator, typename _Compare>
4984     _OutputIterator
4985     set_union(_InputIterator1 __first1, _InputIterator1 __last1,
4986               _InputIterator2 __first2, _InputIterator2 __last2,
4987               _OutputIterator __result, _Compare __comp)
4988     {
4989       typedef typename iterator_traits<_InputIterator1>::value_type
4990         _ValueType1;
4991       typedef typename iterator_traits<_InputIterator2>::value_type
4992         _ValueType2;
4993
4994       // concept requirements
4995       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
4996       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
4997       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
4998                                   _ValueType1>)
4999       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5000                                   _ValueType2>)
5001       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5002                                   _ValueType1, _ValueType2>)
5003       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5004                                   _ValueType2, _ValueType1>)
5005       __glibcxx_requires_sorted_pred(__first1, __last1, __comp);
5006       __glibcxx_requires_sorted_pred(__first2, __last2, __comp);
5007
5008       while (__first1 != __last1 && __first2 != __last2)
5009         {
5010           if (__comp(*__first1, *__first2))
5011             {
5012               *__result = *__first1;
5013               ++__first1;
5014             }
5015           else if (__comp(*__first2, *__first1))
5016             {
5017               *__result = *__first2;
5018               ++__first2;
5019             }
5020           else
5021             {
5022               *__result = *__first1;
5023               ++__first1;
5024               ++__first2;
5025             }
5026           ++__result;
5027         }
5028       return std::copy(__first2, __last2, std::copy(__first1, __last1,
5029                                                     __result));
5030     }
5031
5032   /**
5033    *  @brief Return the intersection of two sorted ranges.
5034    *  @param  first1  Start of first range.
5035    *  @param  last1   End of first range.
5036    *  @param  first2  Start of second range.
5037    *  @param  last2   End of second range.
5038    *  @return  End of the output range.
5039    *  @ingroup setoperations
5040    *
5041    *  This operation iterates over both ranges, copying elements present in
5042    *  both ranges in order to the output range.  Iterators increment for each
5043    *  range.  When the current element of one range is less than the other,
5044    *  that iterator advances.  If an element is contained in both ranges, the
5045    *  element from the first range is copied and both ranges advance.  The
5046    *  output range may not overlap either input range.
5047   */
5048   template<typename _InputIterator1, typename _InputIterator2,
5049            typename _OutputIterator>
5050     _OutputIterator
5051     set_intersection(_InputIterator1 __first1, _InputIterator1 __last1,
5052                      _InputIterator2 __first2, _InputIterator2 __last2,
5053                      _OutputIterator __result)
5054     {
5055       typedef typename iterator_traits<_InputIterator1>::value_type
5056         _ValueType1;
5057       typedef typename iterator_traits<_InputIterator2>::value_type
5058         _ValueType2;
5059
5060       // concept requirements
5061       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
5062       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
5063       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5064                                   _ValueType1>)
5065       __glibcxx_function_requires(_LessThanOpConcept<_ValueType1, _ValueType2>)
5066       __glibcxx_function_requires(_LessThanOpConcept<_ValueType2, _ValueType1>)
5067       __glibcxx_requires_sorted(__first1, __last1);
5068       __glibcxx_requires_sorted(__first2, __last2);
5069
5070       while (__first1 != __last1 && __first2 != __last2)
5071         if (*__first1 < *__first2)
5072           ++__first1;
5073         else if (*__first2 < *__first1)
5074           ++__first2;
5075         else
5076           {
5077             *__result = *__first1;
5078             ++__first1;
5079             ++__first2;
5080             ++__result;
5081           }
5082       return __result;
5083     }
5084
5085   /**
5086    *  @brief Return the intersection of two sorted ranges using comparison
5087    *  functor.
5088    *  @param  first1  Start of first range.
5089    *  @param  last1   End of first range.
5090    *  @param  first2  Start of second range.
5091    *  @param  last2   End of second range.
5092    *  @param  comp    The comparison functor.
5093    *  @return  End of the output range.
5094    *  @ingroup setoperations
5095    *
5096    *  This operation iterates over both ranges, copying elements present in
5097    *  both ranges in order to the output range.  Iterators increment for each
5098    *  range.  When the current element of one range is less than the other
5099    *  according to @a comp, that iterator advances.  If an element is
5100    *  contained in both ranges according to @a comp, the element from the
5101    *  first range is copied and both ranges advance.  The output range may not
5102    *  overlap either input range.
5103   */
5104   template<typename _InputIterator1, typename _InputIterator2,
5105            typename _OutputIterator, typename _Compare>
5106     _OutputIterator
5107     set_intersection(_InputIterator1 __first1, _InputIterator1 __last1,
5108                      _InputIterator2 __first2, _InputIterator2 __last2,
5109                      _OutputIterator __result, _Compare __comp)
5110     {
5111       typedef typename iterator_traits<_InputIterator1>::value_type
5112         _ValueType1;
5113       typedef typename iterator_traits<_InputIterator2>::value_type
5114         _ValueType2;
5115
5116       // concept requirements
5117       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
5118       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
5119       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5120                                   _ValueType1>)
5121       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5122                                   _ValueType1, _ValueType2>)
5123       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5124                                   _ValueType2, _ValueType1>)
5125       __glibcxx_requires_sorted_pred(__first1, __last1, __comp);
5126       __glibcxx_requires_sorted_pred(__first2, __last2, __comp);
5127
5128       while (__first1 != __last1 && __first2 != __last2)
5129         if (__comp(*__first1, *__first2))
5130           ++__first1;
5131         else if (__comp(*__first2, *__first1))
5132           ++__first2;
5133         else
5134           {
5135             *__result = *__first1;
5136             ++__first1;
5137             ++__first2;
5138             ++__result;
5139           }
5140       return __result;
5141     }
5142
5143   /**
5144    *  @brief Return the difference of two sorted ranges.
5145    *  @param  first1  Start of first range.
5146    *  @param  last1   End of first range.
5147    *  @param  first2  Start of second range.
5148    *  @param  last2   End of second range.
5149    *  @return  End of the output range.
5150    *  @ingroup setoperations
5151    *
5152    *  This operation iterates over both ranges, copying elements present in
5153    *  the first range but not the second in order to the output range.
5154    *  Iterators increment for each range.  When the current element of the
5155    *  first range is less than the second, that element is copied and the
5156    *  iterator advances.  If the current element of the second range is less,
5157    *  the iterator advances, but no element is copied.  If an element is
5158    *  contained in both ranges, no elements are copied and both ranges
5159    *  advance.  The output range may not overlap either input range.
5160   */
5161   template<typename _InputIterator1, typename _InputIterator2,
5162            typename _OutputIterator>
5163     _OutputIterator
5164     set_difference(_InputIterator1 __first1, _InputIterator1 __last1,
5165                    _InputIterator2 __first2, _InputIterator2 __last2,
5166                    _OutputIterator __result)
5167     {
5168       typedef typename iterator_traits<_InputIterator1>::value_type
5169         _ValueType1;
5170       typedef typename iterator_traits<_InputIterator2>::value_type
5171         _ValueType2;
5172
5173       // concept requirements
5174       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
5175       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
5176       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5177                                   _ValueType1>)
5178       __glibcxx_function_requires(_LessThanOpConcept<_ValueType1, _ValueType2>)
5179       __glibcxx_function_requires(_LessThanOpConcept<_ValueType2, _ValueType1>)
5180       __glibcxx_requires_sorted(__first1, __last1);
5181       __glibcxx_requires_sorted(__first2, __last2);
5182
5183       while (__first1 != __last1 && __first2 != __last2)
5184         if (*__first1 < *__first2)
5185           {
5186             *__result = *__first1;
5187             ++__first1;
5188             ++__result;
5189           }
5190         else if (*__first2 < *__first1)
5191           ++__first2;
5192         else
5193           {
5194             ++__first1;
5195             ++__first2;
5196           }
5197       return std::copy(__first1, __last1, __result);
5198     }
5199
5200   /**
5201    *  @brief  Return the difference of two sorted ranges using comparison
5202    *  functor.
5203    *  @param  first1  Start of first range.
5204    *  @param  last1   End of first range.
5205    *  @param  first2  Start of second range.
5206    *  @param  last2   End of second range.
5207    *  @param  comp    The comparison functor.
5208    *  @return  End of the output range.
5209    *  @ingroup setoperations
5210    *
5211    *  This operation iterates over both ranges, copying elements present in
5212    *  the first range but not the second in order to the output range.
5213    *  Iterators increment for each range.  When the current element of the
5214    *  first range is less than the second according to @a comp, that element
5215    *  is copied and the iterator advances.  If the current element of the
5216    *  second range is less, no element is copied and the iterator advances.
5217    *  If an element is contained in both ranges according to @a comp, no
5218    *  elements are copied and both ranges advance.  The output range may not
5219    *  overlap either input range.
5220   */
5221   template<typename _InputIterator1, typename _InputIterator2,
5222            typename _OutputIterator, typename _Compare>
5223     _OutputIterator
5224     set_difference(_InputIterator1 __first1, _InputIterator1 __last1,
5225                    _InputIterator2 __first2, _InputIterator2 __last2,
5226                    _OutputIterator __result, _Compare __comp)
5227     {
5228       typedef typename iterator_traits<_InputIterator1>::value_type
5229         _ValueType1;
5230       typedef typename iterator_traits<_InputIterator2>::value_type
5231         _ValueType2;
5232
5233       // concept requirements
5234       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
5235       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
5236       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5237                                   _ValueType1>)
5238       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5239                                   _ValueType1, _ValueType2>)
5240       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5241                                   _ValueType2, _ValueType1>)
5242       __glibcxx_requires_sorted_pred(__first1, __last1, __comp);
5243       __glibcxx_requires_sorted_pred(__first2, __last2, __comp);
5244
5245       while (__first1 != __last1 && __first2 != __last2)
5246         if (__comp(*__first1, *__first2))
5247           {
5248             *__result = *__first1;
5249             ++__first1;
5250             ++__result;
5251           }
5252         else if (__comp(*__first2, *__first1))
5253           ++__first2;
5254         else
5255           {
5256             ++__first1;
5257             ++__first2;
5258           }
5259       return std::copy(__first1, __last1, __result);
5260     }
5261
5262   /**
5263    *  @brief  Return the symmetric difference of two sorted ranges.
5264    *  @param  first1  Start of first range.
5265    *  @param  last1   End of first range.
5266    *  @param  first2  Start of second range.
5267    *  @param  last2   End of second range.
5268    *  @return  End of the output range.
5269    *  @ingroup setoperations
5270    *
5271    *  This operation iterates over both ranges, copying elements present in
5272    *  one range but not the other in order to the output range.  Iterators
5273    *  increment for each range.  When the current element of one range is less
5274    *  than the other, that element is copied and the iterator advances.  If an
5275    *  element is contained in both ranges, no elements are copied and both
5276    *  ranges advance.  The output range may not overlap either input range.
5277   */
5278   template<typename _InputIterator1, typename _InputIterator2,
5279            typename _OutputIterator>
5280     _OutputIterator
5281     set_symmetric_difference(_InputIterator1 __first1, _InputIterator1 __last1,
5282                              _InputIterator2 __first2, _InputIterator2 __last2,
5283                              _OutputIterator __result)
5284     {
5285       typedef typename iterator_traits<_InputIterator1>::value_type
5286         _ValueType1;
5287       typedef typename iterator_traits<_InputIterator2>::value_type
5288         _ValueType2;
5289
5290       // concept requirements
5291       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
5292       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
5293       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5294                                   _ValueType1>)
5295       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5296                                   _ValueType2>)
5297       __glibcxx_function_requires(_LessThanOpConcept<_ValueType1, _ValueType2>)
5298       __glibcxx_function_requires(_LessThanOpConcept<_ValueType2, _ValueType1>)
5299       __glibcxx_requires_sorted(__first1, __last1);
5300       __glibcxx_requires_sorted(__first2, __last2);
5301
5302       while (__first1 != __last1 && __first2 != __last2)
5303         if (*__first1 < *__first2)
5304           {
5305             *__result = *__first1;
5306             ++__first1;
5307             ++__result;
5308           }
5309         else if (*__first2 < *__first1)
5310           {
5311             *__result = *__first2;
5312             ++__first2;
5313             ++__result;
5314           }
5315         else
5316           {
5317             ++__first1;
5318             ++__first2;
5319           }
5320       return std::copy(__first2, __last2, std::copy(__first1,
5321                                                     __last1, __result));
5322     }
5323
5324   /**
5325    *  @brief  Return the symmetric difference of two sorted ranges using
5326    *  comparison functor.
5327    *  @param  first1  Start of first range.
5328    *  @param  last1   End of first range.
5329    *  @param  first2  Start of second range.
5330    *  @param  last2   End of second range.
5331    *  @param  comp    The comparison functor.
5332    *  @return  End of the output range.
5333    *  @ingroup setoperations
5334    *
5335    *  This operation iterates over both ranges, copying elements present in
5336    *  one range but not the other in order to the output range.  Iterators
5337    *  increment for each range.  When the current element of one range is less
5338    *  than the other according to @a comp, that element is copied and the
5339    *  iterator advances.  If an element is contained in both ranges according
5340    *  to @a comp, no elements are copied and both ranges advance.  The output
5341    *  range may not overlap either input range.
5342   */
5343   template<typename _InputIterator1, typename _InputIterator2,
5344            typename _OutputIterator, typename _Compare>
5345     _OutputIterator
5346     set_symmetric_difference(_InputIterator1 __first1, _InputIterator1 __last1,
5347                              _InputIterator2 __first2, _InputIterator2 __last2,
5348                              _OutputIterator __result,
5349                              _Compare __comp)
5350     {
5351       typedef typename iterator_traits<_InputIterator1>::value_type
5352         _ValueType1;
5353       typedef typename iterator_traits<_InputIterator2>::value_type
5354         _ValueType2;
5355
5356       // concept requirements
5357       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
5358       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
5359       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5360                                   _ValueType1>)
5361       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5362                                   _ValueType2>)
5363       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5364                                   _ValueType1, _ValueType2>)
5365       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5366                                   _ValueType2, _ValueType1>)
5367       __glibcxx_requires_sorted_pred(__first1, __last1, __comp);
5368       __glibcxx_requires_sorted_pred(__first2, __last2, __comp);
5369
5370       while (__first1 != __last1 && __first2 != __last2)
5371         if (__comp(*__first1, *__first2))
5372           {
5373             *__result = *__first1;
5374             ++__first1;
5375             ++__result;
5376           }
5377         else if (__comp(*__first2, *__first1))
5378           {
5379             *__result = *__first2;
5380             ++__first2;
5381             ++__result;
5382           }
5383         else
5384           {
5385             ++__first1;
5386             ++__first2;
5387           }
5388       return std::copy(__first2, __last2,
5389                        std::copy(__first1, __last1, __result));
5390     }
5391
5392
5393   /**
5394    *  @brief  Return the minimum element in a range.
5395    *  @param  first  Start of range.
5396    *  @param  last   End of range.
5397    *  @return  Iterator referencing the first instance of the smallest value.
5398   */
5399   template<typename _ForwardIterator>
5400     _ForwardIterator
5401     min_element(_ForwardIterator __first, _ForwardIterator __last)
5402     {
5403       // concept requirements
5404       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
5405       __glibcxx_function_requires(_LessThanComparableConcept<
5406             typename iterator_traits<_ForwardIterator>::value_type>)
5407       __glibcxx_requires_valid_range(__first, __last);
5408
5409       if (__first == __last)
5410         return __first;
5411       _ForwardIterator __result = __first;
5412       while (++__first != __last)
5413         if (*__first < *__result)
5414           __result = __first;
5415       return __result;
5416     }
5417
5418   /**
5419    *  @brief  Return the minimum element in a range using comparison functor.
5420    *  @param  first  Start of range.
5421    *  @param  last   End of range.
5422    *  @param  comp   Comparison functor.
5423    *  @return  Iterator referencing the first instance of the smallest value
5424    *  according to comp.
5425   */
5426   template<typename _ForwardIterator, typename _Compare>
5427     _ForwardIterator
5428     min_element(_ForwardIterator __first, _ForwardIterator __last,
5429                 _Compare __comp)
5430     {
5431       // concept requirements
5432       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
5433       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5434             typename iterator_traits<_ForwardIterator>::value_type,
5435             typename iterator_traits<_ForwardIterator>::value_type>)
5436       __glibcxx_requires_valid_range(__first, __last);
5437
5438       if (__first == __last)
5439         return __first;
5440       _ForwardIterator __result = __first;
5441       while (++__first != __last)
5442         if (__comp(*__first, *__result))
5443           __result = __first;
5444       return __result;
5445     }
5446
5447   /**
5448    *  @brief  Return the maximum element in a range.
5449    *  @param  first  Start of range.
5450    *  @param  last   End of range.
5451    *  @return  Iterator referencing the first instance of the largest value.
5452   */
5453   template<typename _ForwardIterator>
5454     _ForwardIterator
5455     max_element(_ForwardIterator __first, _ForwardIterator __last)
5456     {
5457       // concept requirements
5458       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
5459       __glibcxx_function_requires(_LessThanComparableConcept<
5460             typename iterator_traits<_ForwardIterator>::value_type>)
5461       __glibcxx_requires_valid_range(__first, __last);
5462
5463       if (__first == __last)
5464         return __first;
5465       _ForwardIterator __result = __first;
5466       while (++__first != __last)
5467         if (*__result < *__first)
5468           __result = __first;
5469       return __result;
5470     }
5471
5472   /**
5473    *  @brief  Return the maximum element in a range using comparison functor.
5474    *  @param  first  Start of range.
5475    *  @param  last   End of range.
5476    *  @param  comp   Comparison functor.
5477    *  @return  Iterator referencing the first instance of the largest value
5478    *  according to comp.
5479   */
5480   template<typename _ForwardIterator, typename _Compare>
5481     _ForwardIterator
5482     max_element(_ForwardIterator __first, _ForwardIterator __last,
5483                 _Compare __comp)
5484     {
5485       // concept requirements
5486       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
5487       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5488             typename iterator_traits<_ForwardIterator>::value_type,
5489             typename iterator_traits<_ForwardIterator>::value_type>)
5490       __glibcxx_requires_valid_range(__first, __last);
5491
5492       if (__first == __last) return __first;
5493       _ForwardIterator __result = __first;
5494       while (++__first != __last)
5495         if (__comp(*__result, *__first))
5496           __result = __first;
5497       return __result;
5498     }
5499
5500 _GLIBCXX_END_NESTED_NAMESPACE
5501
5502 #endif /* _STL_ALGO_H */