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

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