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

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