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