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                 *__result1 = _GLIBCXX_MOVE(*__first);
1869                 ++__result1;
1870               }
1871             else
1872               {
1873                 *__result2 = _GLIBCXX_MOVE(*__first);
1874                 ++__result2;
1875               }
1876           _GLIBCXX_MOVE3(__buffer, __result2, __result1);
1877           return __result1;
1878         }
1879       else
1880         {
1881           _ForwardIterator __middle = __first;
1882           std::advance(__middle, __len / 2);
1883           _ForwardIterator __left_split =
1884             std::__stable_partition_adaptive(__first, __middle, __pred,
1885                                              __len / 2, __buffer,
1886                                              __buffer_size);
1887           // Advance past true-predicate values to satisfy this
1888           // function's preconditions.
1889           _Distance __right_len = __len - __len / 2;
1890           _ForwardIterator __right_split =
1891             std::__find_if_not_n(__middle, __right_len, __pred);
1892           if (__right_len)
1893             __right_split =
1894               std::__stable_partition_adaptive(__right_split, __last, __pred,
1895                                                __right_len,
1896                                                __buffer, __buffer_size);
1897           std::rotate(__left_split, __middle, __right_split);
1898           std::advance(__left_split, std::distance(__middle, __right_split));
1899           return __left_split;
1900         }
1901     }
1902
1903   /**
1904    *  @brief Move elements for which a predicate is true to the beginning
1905    *         of a sequence, preserving relative ordering.
1906    *  @ingroup mutating_algorithms
1907    *  @param  __first   A forward iterator.
1908    *  @param  __last    A forward iterator.
1909    *  @param  __pred    A predicate functor.
1910    *  @return  An iterator @p middle such that @p __pred(i) is true for each
1911    *  iterator @p i in the range @p [first,middle) and false for each @p i
1912    *  in the range @p [middle,last).
1913    *
1914    *  Performs the same function as @p partition() with the additional
1915    *  guarantee that the relative ordering of elements in each group is
1916    *  preserved, so any two elements @p x and @p y in the range
1917    *  @p [__first,__last) such that @p __pred(x)==__pred(y) will have the same
1918    *  relative ordering after calling @p stable_partition().
1919   */
1920   template<typename _ForwardIterator, typename _Predicate>
1921     _ForwardIterator
1922     stable_partition(_ForwardIterator __first, _ForwardIterator __last,
1923                      _Predicate __pred)
1924     {
1925       // concept requirements
1926       __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
1927                                   _ForwardIterator>)
1928       __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
1929             typename iterator_traits<_ForwardIterator>::value_type>)
1930       __glibcxx_requires_valid_range(__first, __last);
1931
1932       __first = std::__find_if_not(__first, __last, __pred);
1933
1934       if (__first == __last)
1935         return __first;
1936       else
1937         {
1938           typedef typename iterator_traits<_ForwardIterator>::value_type
1939             _ValueType;
1940           typedef typename iterator_traits<_ForwardIterator>::difference_type
1941             _DistanceType;
1942
1943           _Temporary_buffer<_ForwardIterator, _ValueType> __buf(__first,
1944                                                                 __last);
1945         if (__buf.size() > 0)
1946           return
1947             std::__stable_partition_adaptive(__first, __last, __pred,
1948                                           _DistanceType(__buf.requested_size()),
1949                                           __buf.begin(),
1950                                           _DistanceType(__buf.size()));
1951         else
1952           return
1953             std::__inplace_stable_partition(__first, __pred,
1954                                          _DistanceType(__buf.requested_size()));
1955         }
1956     }
1957
1958   /// This is a helper function for the sort routines.
1959   template<typename _RandomAccessIterator>
1960     void
1961     __heap_select(_RandomAccessIterator __first,
1962                   _RandomAccessIterator __middle,
1963                   _RandomAccessIterator __last)
1964     {
1965       std::make_heap(__first, __middle);
1966       for (_RandomAccessIterator __i = __middle; __i < __last; ++__i)
1967         if (*__i < *__first)
1968           std::__pop_heap(__first, __middle, __i);
1969     }
1970
1971   /// This is a helper function for the sort routines.
1972   template<typename _RandomAccessIterator, typename _Compare>
1973     void
1974     __heap_select(_RandomAccessIterator __first,
1975                   _RandomAccessIterator __middle,
1976                   _RandomAccessIterator __last, _Compare __comp)
1977     {
1978       std::make_heap(__first, __middle, __comp);
1979       for (_RandomAccessIterator __i = __middle; __i < __last; ++__i)
1980         if (__comp(*__i, *__first))
1981           std::__pop_heap(__first, __middle, __i, __comp);
1982     }
1983
1984   // partial_sort
1985
1986   /**
1987    *  @brief Copy the smallest elements of a sequence.
1988    *  @ingroup sorting_algorithms
1989    *  @param  __first   An iterator.
1990    *  @param  __last    Another iterator.
1991    *  @param  __result_first   A random-access iterator.
1992    *  @param  __result_last    Another random-access iterator.
1993    *  @return   An iterator indicating the end of the resulting sequence.
1994    *
1995    *  Copies and sorts the smallest N values from the range @p [__first,__last)
1996    *  to the range beginning at @p __result_first, where the number of
1997    *  elements to be copied, @p N, is the smaller of @p (__last-__first) and
1998    *  @p (__result_last-__result_first).
1999    *  After the sort if @e i and @e j are iterators in the range
2000    *  @p [__result_first,__result_first+N) such that i precedes j then
2001    *  *j<*i is false.
2002    *  The value returned is @p __result_first+N.
2003   */
2004   template<typename _InputIterator, typename _RandomAccessIterator>
2005     _RandomAccessIterator
2006     partial_sort_copy(_InputIterator __first, _InputIterator __last,
2007                       _RandomAccessIterator __result_first,
2008                       _RandomAccessIterator __result_last)
2009     {
2010       typedef typename iterator_traits<_InputIterator>::value_type
2011         _InputValueType;
2012       typedef typename iterator_traits<_RandomAccessIterator>::value_type
2013         _OutputValueType;
2014       typedef typename iterator_traits<_RandomAccessIterator>::difference_type
2015         _DistanceType;
2016
2017       // concept requirements
2018       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
2019       __glibcxx_function_requires(_ConvertibleConcept<_InputValueType,
2020                                   _OutputValueType>)
2021       __glibcxx_function_requires(_LessThanOpConcept<_InputValueType,
2022                                                      _OutputValueType>)
2023       __glibcxx_function_requires(_LessThanComparableConcept<_OutputValueType>)
2024       __glibcxx_requires_valid_range(__first, __last);
2025       __glibcxx_requires_valid_range(__result_first, __result_last);
2026
2027       if (__result_first == __result_last)
2028         return __result_last;
2029       _RandomAccessIterator __result_real_last = __result_first;
2030       while(__first != __last && __result_real_last != __result_last)
2031         {
2032           *__result_real_last = *__first;
2033           ++__result_real_last;
2034           ++__first;
2035         }
2036       std::make_heap(__result_first, __result_real_last);
2037       while (__first != __last)
2038         {
2039           if (*__first < *__result_first)
2040             std::__adjust_heap(__result_first, _DistanceType(0),
2041                                _DistanceType(__result_real_last
2042                                              - __result_first),
2043                                _InputValueType(*__first));
2044           ++__first;
2045         }
2046       std::sort_heap(__result_first, __result_real_last);
2047       return __result_real_last;
2048     }
2049
2050   /**
2051    *  @brief Copy the smallest elements of a sequence using a predicate for
2052    *         comparison.
2053    *  @ingroup sorting_algorithms
2054    *  @param  __first   An input iterator.
2055    *  @param  __last    Another input iterator.
2056    *  @param  __result_first   A random-access iterator.
2057    *  @param  __result_last    Another random-access iterator.
2058    *  @param  __comp    A comparison functor.
2059    *  @return   An iterator indicating the end of the resulting sequence.
2060    *
2061    *  Copies and sorts the smallest N values from the range @p [__first,__last)
2062    *  to the range beginning at @p result_first, where the number of
2063    *  elements to be copied, @p N, is the smaller of @p (__last-__first) and
2064    *  @p (__result_last-__result_first).
2065    *  After the sort if @e i and @e j are iterators in the range
2066    *  @p [__result_first,__result_first+N) such that i precedes j then
2067    *  @p __comp(*j,*i) is false.
2068    *  The value returned is @p __result_first+N.
2069   */
2070   template<typename _InputIterator, typename _RandomAccessIterator, typename _Compare>
2071     _RandomAccessIterator
2072     partial_sort_copy(_InputIterator __first, _InputIterator __last,
2073                       _RandomAccessIterator __result_first,
2074                       _RandomAccessIterator __result_last,
2075                       _Compare __comp)
2076     {
2077       typedef typename iterator_traits<_InputIterator>::value_type
2078         _InputValueType;
2079       typedef typename iterator_traits<_RandomAccessIterator>::value_type
2080         _OutputValueType;
2081       typedef typename iterator_traits<_RandomAccessIterator>::difference_type
2082         _DistanceType;
2083
2084       // concept requirements
2085       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
2086       __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
2087                                   _RandomAccessIterator>)
2088       __glibcxx_function_requires(_ConvertibleConcept<_InputValueType,
2089                                   _OutputValueType>)
2090       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2091                                   _InputValueType, _OutputValueType>)
2092       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2093                                   _OutputValueType, _OutputValueType>)
2094       __glibcxx_requires_valid_range(__first, __last);
2095       __glibcxx_requires_valid_range(__result_first, __result_last);
2096
2097       if (__result_first == __result_last)
2098         return __result_last;
2099       _RandomAccessIterator __result_real_last = __result_first;
2100       while(__first != __last && __result_real_last != __result_last)
2101         {
2102           *__result_real_last = *__first;
2103           ++__result_real_last;
2104           ++__first;
2105         }
2106       std::make_heap(__result_first, __result_real_last, __comp);
2107       while (__first != __last)
2108         {
2109           if (__comp(*__first, *__result_first))
2110             std::__adjust_heap(__result_first, _DistanceType(0),
2111                                _DistanceType(__result_real_last
2112                                              - __result_first),
2113                                _InputValueType(*__first),
2114                                __comp);
2115           ++__first;
2116         }
2117       std::sort_heap(__result_first, __result_real_last, __comp);
2118       return __result_real_last;
2119     }
2120
2121   /// This is a helper function for the sort routine.
2122   template<typename _RandomAccessIterator>
2123     void
2124     __unguarded_linear_insert(_RandomAccessIterator __last)
2125     {
2126       typename iterator_traits<_RandomAccessIterator>::value_type
2127         __val = _GLIBCXX_MOVE(*__last);
2128       _RandomAccessIterator __next = __last;
2129       --__next;
2130       while (__val < *__next)
2131         {
2132           *__last = _GLIBCXX_MOVE(*__next);
2133           __last = __next;
2134           --__next;
2135         }
2136       *__last = _GLIBCXX_MOVE(__val);
2137     }
2138
2139   /// This is a helper function for the sort routine.
2140   template<typename _RandomAccessIterator, typename _Compare>
2141     void
2142     __unguarded_linear_insert(_RandomAccessIterator __last,
2143                               _Compare __comp)
2144     {
2145       typename iterator_traits<_RandomAccessIterator>::value_type
2146         __val = _GLIBCXX_MOVE(*__last);
2147       _RandomAccessIterator __next = __last;
2148       --__next;
2149       while (__comp(__val, *__next))
2150         {
2151           *__last = _GLIBCXX_MOVE(*__next);
2152           __last = __next;
2153           --__next;
2154         }
2155       *__last = _GLIBCXX_MOVE(__val);
2156     }
2157
2158   /// This is a helper function for the sort routine.
2159   template<typename _RandomAccessIterator>
2160     void
2161     __insertion_sort(_RandomAccessIterator __first,
2162                      _RandomAccessIterator __last)
2163     {
2164       if (__first == __last)
2165         return;
2166
2167       for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i)
2168         {
2169           if (*__i < *__first)
2170             {
2171               typename iterator_traits<_RandomAccessIterator>::value_type
2172                 __val = _GLIBCXX_MOVE(*__i);
2173               _GLIBCXX_MOVE_BACKWARD3(__first, __i, __i + 1);
2174               *__first = _GLIBCXX_MOVE(__val);
2175             }
2176           else
2177             std::__unguarded_linear_insert(__i);
2178         }
2179     }
2180
2181   /// This is a helper function for the sort routine.
2182   template<typename _RandomAccessIterator, typename _Compare>
2183     void
2184     __insertion_sort(_RandomAccessIterator __first,
2185                      _RandomAccessIterator __last, _Compare __comp)
2186     {
2187       if (__first == __last) return;
2188
2189       for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i)
2190         {
2191           if (__comp(*__i, *__first))
2192             {
2193               typename iterator_traits<_RandomAccessIterator>::value_type
2194                 __val = _GLIBCXX_MOVE(*__i);
2195               _GLIBCXX_MOVE_BACKWARD3(__first, __i, __i + 1);
2196               *__first = _GLIBCXX_MOVE(__val);
2197             }
2198           else
2199             std::__unguarded_linear_insert(__i, __comp);
2200         }
2201     }
2202
2203   /// This is a helper function for the sort routine.
2204   template<typename _RandomAccessIterator>
2205     inline void
2206     __unguarded_insertion_sort(_RandomAccessIterator __first,
2207                                _RandomAccessIterator __last)
2208     {
2209       typedef typename iterator_traits<_RandomAccessIterator>::value_type
2210         _ValueType;
2211
2212       for (_RandomAccessIterator __i = __first; __i != __last; ++__i)
2213         std::__unguarded_linear_insert(__i);
2214     }
2215
2216   /// This is a helper function for the sort routine.
2217   template<typename _RandomAccessIterator, typename _Compare>
2218     inline void
2219     __unguarded_insertion_sort(_RandomAccessIterator __first,
2220                                _RandomAccessIterator __last, _Compare __comp)
2221     {
2222       typedef typename iterator_traits<_RandomAccessIterator>::value_type
2223         _ValueType;
2224
2225       for (_RandomAccessIterator __i = __first; __i != __last; ++__i)
2226         std::__unguarded_linear_insert(__i, __comp);
2227     }
2228
2229   /**
2230    *  @doctodo
2231    *  This controls some aspect of the sort routines.
2232   */
2233   enum { _S_threshold = 16 };
2234
2235   /// This is a helper function for the sort routine.
2236   template<typename _RandomAccessIterator>
2237     void
2238     __final_insertion_sort(_RandomAccessIterator __first,
2239                            _RandomAccessIterator __last)
2240     {
2241       if (__last - __first > int(_S_threshold))
2242         {
2243           std::__insertion_sort(__first, __first + int(_S_threshold));
2244           std::__unguarded_insertion_sort(__first + int(_S_threshold), __last);
2245         }
2246       else
2247         std::__insertion_sort(__first, __last);
2248     }
2249
2250   /// This is a helper function for the sort routine.
2251   template<typename _RandomAccessIterator, typename _Compare>
2252     void
2253     __final_insertion_sort(_RandomAccessIterator __first,
2254                            _RandomAccessIterator __last, _Compare __comp)
2255     {
2256       if (__last - __first > int(_S_threshold))
2257         {
2258           std::__insertion_sort(__first, __first + int(_S_threshold), __comp);
2259           std::__unguarded_insertion_sort(__first + int(_S_threshold), __last,
2260                                           __comp);
2261         }
2262       else
2263         std::__insertion_sort(__first, __last, __comp);
2264     }
2265
2266   /// This is a helper function...
2267   template<typename _RandomAccessIterator, typename _Tp>
2268     _RandomAccessIterator
2269     __unguarded_partition(_RandomAccessIterator __first,
2270                           _RandomAccessIterator __last, const _Tp& __pivot)
2271     {
2272       while (true)
2273         {
2274           while (*__first < __pivot)
2275             ++__first;
2276           --__last;
2277           while (__pivot < *__last)
2278             --__last;
2279           if (!(__first < __last))
2280             return __first;
2281           std::iter_swap(__first, __last);
2282           ++__first;
2283         }
2284     }
2285
2286   /// This is a helper function...
2287   template<typename _RandomAccessIterator, typename _Tp, typename _Compare>
2288     _RandomAccessIterator
2289     __unguarded_partition(_RandomAccessIterator __first,
2290                           _RandomAccessIterator __last,
2291                           const _Tp& __pivot, _Compare __comp)
2292     {
2293       while (true)
2294         {
2295           while (__comp(*__first, __pivot))
2296             ++__first;
2297           --__last;
2298           while (__comp(__pivot, *__last))
2299             --__last;
2300           if (!(__first < __last))
2301             return __first;
2302           std::iter_swap(__first, __last);
2303           ++__first;
2304         }
2305     }
2306
2307   /// This is a helper function...
2308   template<typename _RandomAccessIterator>
2309     inline _RandomAccessIterator
2310     __unguarded_partition_pivot(_RandomAccessIterator __first,
2311                                 _RandomAccessIterator __last)
2312     {
2313       _RandomAccessIterator __mid = __first + (__last - __first) / 2;
2314       std::__move_median_to_first(__first, __first + 1, __mid, (__last - 2));
2315       return std::__unguarded_partition(__first + 1, __last, *__first);
2316     }
2317
2318
2319   /// This is a helper function...
2320   template<typename _RandomAccessIterator, typename _Compare>
2321     inline _RandomAccessIterator
2322     __unguarded_partition_pivot(_RandomAccessIterator __first,
2323                                 _RandomAccessIterator __last, _Compare __comp)
2324     {
2325       _RandomAccessIterator __mid = __first + (__last - __first) / 2;
2326       std::__move_median_to_first(__first, __first + 1, __mid, (__last - 2),
2327                                   __comp);
2328       return std::__unguarded_partition(__first + 1, __last, *__first, __comp);
2329     }
2330
2331   /// This is a helper function for the sort routine.
2332   template<typename _RandomAccessIterator, typename _Size>
2333     void
2334     __introsort_loop(_RandomAccessIterator __first,
2335                      _RandomAccessIterator __last,
2336                      _Size __depth_limit)
2337     {
2338       while (__last - __first > int(_S_threshold))
2339         {
2340           if (__depth_limit == 0)
2341             {
2342               _GLIBCXX_STD_A::partial_sort(__first, __last, __last);
2343               return;
2344             }
2345           --__depth_limit;
2346           _RandomAccessIterator __cut =
2347             std::__unguarded_partition_pivot(__first, __last);
2348           std::__introsort_loop(__cut, __last, __depth_limit);
2349           __last = __cut;
2350         }
2351     }
2352
2353   /// This is a helper function for the sort routine.
2354   template<typename _RandomAccessIterator, typename _Size, typename _Compare>
2355     void
2356     __introsort_loop(_RandomAccessIterator __first,
2357                      _RandomAccessIterator __last,
2358                      _Size __depth_limit, _Compare __comp)
2359     {
2360       while (__last - __first > int(_S_threshold))
2361         {
2362           if (__depth_limit == 0)
2363             {
2364               _GLIBCXX_STD_A::partial_sort(__first, __last, __last, __comp);
2365               return;
2366             }
2367           --__depth_limit;
2368           _RandomAccessIterator __cut =
2369             std::__unguarded_partition_pivot(__first, __last, __comp);
2370           std::__introsort_loop(__cut, __last, __depth_limit, __comp);
2371           __last = __cut;
2372         }
2373     }
2374
2375   // sort
2376
2377   template<typename _RandomAccessIterator, typename _Size>
2378     void
2379     __introselect(_RandomAccessIterator __first, _RandomAccessIterator __nth,
2380                   _RandomAccessIterator __last, _Size __depth_limit)
2381     {
2382       typedef typename iterator_traits<_RandomAccessIterator>::value_type
2383         _ValueType;
2384
2385       while (__last - __first > 3)
2386         {
2387           if (__depth_limit == 0)
2388             {
2389               std::__heap_select(__first, __nth + 1, __last);
2390
2391               // Place the nth largest element in its final position.
2392               std::iter_swap(__first, __nth);
2393               return;
2394             }
2395           --__depth_limit;
2396           _RandomAccessIterator __cut =
2397             std::__unguarded_partition_pivot(__first, __last);
2398           if (__cut <= __nth)
2399             __first = __cut;
2400           else
2401             __last = __cut;
2402         }
2403       std::__insertion_sort(__first, __last);
2404     }
2405
2406   template<typename _RandomAccessIterator, typename _Size, typename _Compare>
2407     void
2408     __introselect(_RandomAccessIterator __first, _RandomAccessIterator __nth,
2409                   _RandomAccessIterator __last, _Size __depth_limit,
2410                   _Compare __comp)
2411     {
2412       typedef typename iterator_traits<_RandomAccessIterator>::value_type
2413         _ValueType;
2414
2415       while (__last - __first > 3)
2416         {
2417           if (__depth_limit == 0)
2418             {
2419               std::__heap_select(__first, __nth + 1, __last, __comp);
2420               // Place the nth largest element in its final position.
2421               std::iter_swap(__first, __nth);
2422               return;
2423             }
2424           --__depth_limit;
2425           _RandomAccessIterator __cut =
2426             std::__unguarded_partition_pivot(__first, __last, __comp);
2427           if (__cut <= __nth)
2428             __first = __cut;
2429           else
2430             __last = __cut;
2431         }
2432       std::__insertion_sort(__first, __last, __comp);
2433     }
2434
2435   // nth_element
2436
2437   // lower_bound moved to stl_algobase.h
2438
2439   /**
2440    *  @brief Finds the first position in which @p __val could be inserted
2441    *         without changing the ordering.
2442    *  @ingroup binary_search_algorithms
2443    *  @param  __first   An iterator.
2444    *  @param  __last    Another iterator.
2445    *  @param  __val     The search term.
2446    *  @param  __comp    A functor to use for comparisons.
2447    *  @return An iterator pointing to the first element <em>not less
2448    *           than</em> @p __val, or end() if every element is less
2449    *           than @p __val.
2450    *  @ingroup binary_search_algorithms
2451    *
2452    *  The comparison function should have the same effects on ordering as
2453    *  the function used for the initial sort.
2454   */
2455   template<typename _ForwardIterator, typename _Tp, typename _Compare>
2456     _ForwardIterator
2457     lower_bound(_ForwardIterator __first, _ForwardIterator __last,
2458                 const _Tp& __val, _Compare __comp)
2459     {
2460       typedef typename iterator_traits<_ForwardIterator>::value_type
2461         _ValueType;
2462       typedef typename iterator_traits<_ForwardIterator>::difference_type
2463         _DistanceType;
2464
2465       // concept requirements
2466       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
2467       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2468                                   _ValueType, _Tp>)
2469       __glibcxx_requires_partitioned_lower_pred(__first, __last,
2470                                                 __val, __comp);
2471
2472       _DistanceType __len = std::distance(__first, __last);
2473
2474       while (__len > 0)
2475         {
2476           _DistanceType __half = __len >> 1;
2477           _ForwardIterator __middle = __first;
2478           std::advance(__middle, __half);
2479           if (__comp(*__middle, __val))
2480             {
2481               __first = __middle;
2482               ++__first;
2483               __len = __len - __half - 1;
2484             }
2485           else
2486             __len = __half;
2487         }
2488       return __first;
2489     }
2490
2491   /**
2492    *  @brief Finds the last position in which @p __val could be inserted
2493    *         without changing the ordering.
2494    *  @ingroup binary_search_algorithms
2495    *  @param  __first   An iterator.
2496    *  @param  __last    Another iterator.
2497    *  @param  __val     The search term.
2498    *  @return  An iterator pointing to the first element greater than @p __val,
2499    *           or end() if no elements are greater than @p __val.
2500    *  @ingroup binary_search_algorithms
2501   */
2502   template<typename _ForwardIterator, typename _Tp>
2503     _ForwardIterator
2504     upper_bound(_ForwardIterator __first, _ForwardIterator __last,
2505                 const _Tp& __val)
2506     {
2507       typedef typename iterator_traits<_ForwardIterator>::value_type
2508         _ValueType;
2509       typedef typename iterator_traits<_ForwardIterator>::difference_type
2510         _DistanceType;
2511
2512       // concept requirements
2513       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
2514       __glibcxx_function_requires(_LessThanOpConcept<_Tp, _ValueType>)
2515       __glibcxx_requires_partitioned_upper(__first, __last, __val);
2516
2517       _DistanceType __len = std::distance(__first, __last);
2518
2519       while (__len > 0)
2520         {
2521           _DistanceType __half = __len >> 1;
2522           _ForwardIterator __middle = __first;
2523           std::advance(__middle, __half);
2524           if (__val < *__middle)
2525             __len = __half;
2526           else
2527             {
2528               __first = __middle;
2529               ++__first;
2530               __len = __len - __half - 1;
2531             }
2532         }
2533       return __first;
2534     }
2535
2536   /**
2537    *  @brief Finds the last position in which @p __val could be inserted
2538    *         without changing the ordering.
2539    *  @ingroup binary_search_algorithms
2540    *  @param  __first   An iterator.
2541    *  @param  __last    Another iterator.
2542    *  @param  __val     The search term.
2543    *  @param  __comp    A functor to use for comparisons.
2544    *  @return  An iterator pointing to the first element greater than @p __val,
2545    *           or end() if no elements are greater than @p __val.
2546    *  @ingroup binary_search_algorithms
2547    *
2548    *  The comparison function should have the same effects on ordering as
2549    *  the function used for the initial sort.
2550   */
2551   template<typename _ForwardIterator, typename _Tp, typename _Compare>
2552     _ForwardIterator
2553     upper_bound(_ForwardIterator __first, _ForwardIterator __last,
2554                 const _Tp& __val, _Compare __comp)
2555     {
2556       typedef typename iterator_traits<_ForwardIterator>::value_type
2557         _ValueType;
2558       typedef typename iterator_traits<_ForwardIterator>::difference_type
2559         _DistanceType;
2560
2561       // concept requirements
2562       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
2563       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2564                                   _Tp, _ValueType>)
2565       __glibcxx_requires_partitioned_upper_pred(__first, __last,
2566                                                 __val, __comp);
2567
2568       _DistanceType __len = std::distance(__first, __last);
2569
2570       while (__len > 0)
2571         {
2572           _DistanceType __half = __len >> 1;
2573           _ForwardIterator __middle = __first;
2574           std::advance(__middle, __half);
2575           if (__comp(__val, *__middle))
2576             __len = __half;
2577           else
2578             {
2579               __first = __middle;
2580               ++__first;
2581               __len = __len - __half - 1;
2582             }
2583         }
2584       return __first;
2585     }
2586
2587   /**
2588    *  @brief Finds the largest subrange in which @p __val could be inserted
2589    *         at any place in it without changing the ordering.
2590    *  @ingroup binary_search_algorithms
2591    *  @param  __first   An iterator.
2592    *  @param  __last    Another iterator.
2593    *  @param  __val     The search term.
2594    *  @return  An pair of iterators defining the subrange.
2595    *  @ingroup binary_search_algorithms
2596    *
2597    *  This is equivalent to
2598    *  @code
2599    *    std::make_pair(lower_bound(__first, __last, __val),
2600    *                   upper_bound(__first, __last, __val))
2601    *  @endcode
2602    *  but does not actually call those functions.
2603   */
2604   template<typename _ForwardIterator, typename _Tp>
2605     pair<_ForwardIterator, _ForwardIterator>
2606     equal_range(_ForwardIterator __first, _ForwardIterator __last,
2607                 const _Tp& __val)
2608     {
2609       typedef typename iterator_traits<_ForwardIterator>::value_type
2610         _ValueType;
2611       typedef typename iterator_traits<_ForwardIterator>::difference_type
2612         _DistanceType;
2613
2614       // concept requirements
2615       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
2616       __glibcxx_function_requires(_LessThanOpConcept<_ValueType, _Tp>)
2617       __glibcxx_function_requires(_LessThanOpConcept<_Tp, _ValueType>)
2618       __glibcxx_requires_partitioned_lower(__first, __last, __val);
2619       __glibcxx_requires_partitioned_upper(__first, __last, __val);
2620
2621       _DistanceType __len = std::distance(__first, __last);
2622
2623       while (__len > 0)
2624         {
2625           _DistanceType __half = __len >> 1;
2626           _ForwardIterator __middle = __first;
2627           std::advance(__middle, __half);
2628           if (*__middle < __val)
2629             {
2630               __first = __middle;
2631               ++__first;
2632               __len = __len - __half - 1;
2633             }
2634           else if (__val < *__middle)
2635             __len = __half;
2636           else
2637             {
2638               _ForwardIterator __left = std::lower_bound(__first, __middle,
2639                                                          __val);
2640               std::advance(__first, __len);
2641               _ForwardIterator __right = std::upper_bound(++__middle, __first,
2642                                                           __val);
2643               return pair<_ForwardIterator, _ForwardIterator>(__left, __right);
2644             }
2645         }
2646       return pair<_ForwardIterator, _ForwardIterator>(__first, __first);
2647     }
2648
2649   /**
2650    *  @brief Finds the largest subrange in which @p __val could be inserted
2651    *         at any place in it without changing the ordering.
2652    *  @param  __first   An iterator.
2653    *  @param  __last    Another iterator.
2654    *  @param  __val     The search term.
2655    *  @param  __comp    A functor to use for comparisons.
2656    *  @return  An pair of iterators defining the subrange.
2657    *  @ingroup binary_search_algorithms
2658    *
2659    *  This is equivalent to
2660    *  @code
2661    *    std::make_pair(lower_bound(__first, __last, __val, __comp),
2662    *                   upper_bound(__first, __last, __val, __comp))
2663    *  @endcode
2664    *  but does not actually call those functions.
2665   */
2666   template<typename _ForwardIterator, typename _Tp, typename _Compare>
2667     pair<_ForwardIterator, _ForwardIterator>
2668     equal_range(_ForwardIterator __first, _ForwardIterator __last,
2669                 const _Tp& __val, _Compare __comp)
2670     {
2671       typedef typename iterator_traits<_ForwardIterator>::value_type
2672         _ValueType;
2673       typedef typename iterator_traits<_ForwardIterator>::difference_type
2674         _DistanceType;
2675
2676       // concept requirements
2677       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
2678       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2679                                   _ValueType, _Tp>)
2680       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2681                                   _Tp, _ValueType>)
2682       __glibcxx_requires_partitioned_lower_pred(__first, __last,
2683                                                 __val, __comp);
2684       __glibcxx_requires_partitioned_upper_pred(__first, __last,
2685                                                 __val, __comp);
2686
2687       _DistanceType __len = std::distance(__first, __last);
2688
2689       while (__len > 0)
2690         {
2691           _DistanceType __half = __len >> 1;
2692           _ForwardIterator __middle = __first;
2693           std::advance(__middle, __half);
2694           if (__comp(*__middle, __val))
2695             {
2696               __first = __middle;
2697               ++__first;
2698               __len = __len - __half - 1;
2699             }
2700           else if (__comp(__val, *__middle))
2701             __len = __half;
2702           else
2703             {
2704               _ForwardIterator __left = std::lower_bound(__first, __middle,
2705                                                          __val, __comp);
2706               std::advance(__first, __len);
2707               _ForwardIterator __right = std::upper_bound(++__middle, __first,
2708                                                           __val, __comp);
2709               return pair<_ForwardIterator, _ForwardIterator>(__left, __right);
2710             }
2711         }
2712       return pair<_ForwardIterator, _ForwardIterator>(__first, __first);
2713     }
2714
2715   /**
2716    *  @brief Determines whether an element exists in a range.
2717    *  @ingroup binary_search_algorithms
2718    *  @param  __first   An iterator.
2719    *  @param  __last    Another iterator.
2720    *  @param  __val     The search term.
2721    *  @return True if @p __val (or its equivalent) is in [@p
2722    *  __first,@p __last ].
2723    *
2724    *  Note that this does not actually return an iterator to @p __val.  For
2725    *  that, use std::find or a container's specialized find member functions.
2726   */
2727   template<typename _ForwardIterator, typename _Tp>
2728     bool
2729     binary_search(_ForwardIterator __first, _ForwardIterator __last,
2730                   const _Tp& __val)
2731     {
2732       typedef typename iterator_traits<_ForwardIterator>::value_type
2733         _ValueType;
2734
2735       // concept requirements
2736       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
2737       __glibcxx_function_requires(_LessThanOpConcept<_Tp, _ValueType>)
2738       __glibcxx_requires_partitioned_lower(__first, __last, __val);
2739       __glibcxx_requires_partitioned_upper(__first, __last, __val);
2740
2741       _ForwardIterator __i = std::lower_bound(__first, __last, __val);
2742       return __i != __last && !(__val < *__i);
2743     }
2744
2745   /**
2746    *  @brief Determines whether an element exists in a range.
2747    *  @ingroup binary_search_algorithms
2748    *  @param  __first   An iterator.
2749    *  @param  __last    Another iterator.
2750    *  @param  __val     The search term.
2751    *  @param  __comp    A functor to use for comparisons.
2752    *  @return  True if @p __val (or its equivalent) is in @p [__first,__last].
2753    *
2754    *  Note that this does not actually return an iterator to @p __val.  For
2755    *  that, use std::find or a container's specialized find member functions.
2756    *
2757    *  The comparison function should have the same effects on ordering as
2758    *  the function used for the initial sort.
2759   */
2760   template<typename _ForwardIterator, typename _Tp, typename _Compare>
2761     bool
2762     binary_search(_ForwardIterator __first, _ForwardIterator __last,
2763                   const _Tp& __val, _Compare __comp)
2764     {
2765       typedef typename iterator_traits<_ForwardIterator>::value_type
2766         _ValueType;
2767
2768       // concept requirements
2769       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
2770       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2771                                   _Tp, _ValueType>)
2772       __glibcxx_requires_partitioned_lower_pred(__first, __last,
2773                                                 __val, __comp);
2774       __glibcxx_requires_partitioned_upper_pred(__first, __last,
2775                                                 __val, __comp);
2776
2777       _ForwardIterator __i = std::lower_bound(__first, __last, __val, __comp);
2778       return __i != __last && !bool(__comp(__val, *__i));
2779     }
2780
2781   // merge
2782
2783   /// This is a helper function for the __merge_adaptive routines.
2784   template<typename _InputIterator1, typename _InputIterator2,
2785            typename _OutputIterator>
2786     void
2787     __move_merge_adaptive(_InputIterator1 __first1, _InputIterator1 __last1,
2788                           _InputIterator2 __first2, _InputIterator2 __last2,
2789                           _OutputIterator __result)
2790     {
2791       while (__first1 != __last1 && __first2 != __last2)
2792         {
2793           if (*__first2 < *__first1)
2794             {
2795               *__result = _GLIBCXX_MOVE(*__first2);
2796               ++__first2;
2797             }
2798           else
2799             {
2800               *__result = _GLIBCXX_MOVE(*__first1);
2801               ++__first1;
2802             }
2803           ++__result;
2804         }
2805       if (__first1 != __last1)
2806         _GLIBCXX_MOVE3(__first1, __last1, __result);
2807     }
2808
2809   /// This is a helper function for the __merge_adaptive routines.
2810   template<typename _InputIterator1, typename _InputIterator2,
2811            typename _OutputIterator, typename _Compare>
2812     void
2813     __move_merge_adaptive(_InputIterator1 __first1, _InputIterator1 __last1,
2814                           _InputIterator2 __first2, _InputIterator2 __last2,
2815                           _OutputIterator __result, _Compare __comp)
2816     {
2817       while (__first1 != __last1 && __first2 != __last2)
2818         {
2819           if (__comp(*__first2, *__first1))
2820             {
2821               *__result = _GLIBCXX_MOVE(*__first2);
2822               ++__first2;
2823             }
2824           else
2825             {
2826               *__result = _GLIBCXX_MOVE(*__first1);
2827               ++__first1;
2828             }
2829           ++__result;
2830         }
2831       if (__first1 != __last1)
2832         _GLIBCXX_MOVE3(__first1, __last1, __result);
2833     }
2834
2835   /// This is a helper function for the __merge_adaptive routines.
2836   template<typename _BidirectionalIterator1, typename _BidirectionalIterator2,
2837            typename _BidirectionalIterator3>
2838     void
2839     __move_merge_adaptive_backward(_BidirectionalIterator1 __first1,
2840                                    _BidirectionalIterator1 __last1,
2841                                    _BidirectionalIterator2 __first2,
2842                                    _BidirectionalIterator2 __last2,
2843                                    _BidirectionalIterator3 __result)
2844     {
2845       if (__first1 == __last1)
2846         {
2847           _GLIBCXX_MOVE_BACKWARD3(__first2, __last2, __result);
2848           return;
2849         }
2850       else if (__first2 == __last2)
2851         return;
2852
2853       --__last1;
2854       --__last2;
2855       while (true)
2856         {
2857           if (*__last2 < *__last1)
2858             {
2859               *--__result = _GLIBCXX_MOVE(*__last1);
2860               if (__first1 == __last1)
2861                 {
2862                   _GLIBCXX_MOVE_BACKWARD3(__first2, ++__last2, __result);
2863                   return;
2864                 }
2865               --__last1;
2866             }
2867           else
2868             {
2869               *--__result = _GLIBCXX_MOVE(*__last2);
2870               if (__first2 == __last2)
2871                 return;
2872               --__last2;
2873             }
2874         }
2875     }
2876
2877   /// This is a helper function for the __merge_adaptive routines.
2878   template<typename _BidirectionalIterator1, typename _BidirectionalIterator2,
2879            typename _BidirectionalIterator3, typename _Compare>
2880     void
2881     __move_merge_adaptive_backward(_BidirectionalIterator1 __first1,
2882                                    _BidirectionalIterator1 __last1,
2883                                    _BidirectionalIterator2 __first2,
2884                                    _BidirectionalIterator2 __last2,
2885                                    _BidirectionalIterator3 __result,
2886                                    _Compare __comp)
2887     {
2888       if (__first1 == __last1)
2889         {
2890           _GLIBCXX_MOVE_BACKWARD3(__first2, __last2, __result);
2891           return;
2892         }
2893       else if (__first2 == __last2)
2894         return;
2895
2896       --__last1;
2897       --__last2;
2898       while (true)
2899         {
2900           if (__comp(*__last2, *__last1))
2901             {
2902               *--__result = _GLIBCXX_MOVE(*__last1);
2903               if (__first1 == __last1)
2904                 {
2905                   _GLIBCXX_MOVE_BACKWARD3(__first2, ++__last2, __result);
2906                   return;
2907                 }
2908               --__last1;
2909             }
2910           else
2911             {
2912               *--__result = _GLIBCXX_MOVE(*__last2);
2913               if (__first2 == __last2)
2914                 return;
2915               --__last2;
2916             }
2917         }
2918     }
2919
2920   /// This is a helper function for the merge routines.
2921   template<typename _BidirectionalIterator1, typename _BidirectionalIterator2,
2922            typename _Distance>
2923     _BidirectionalIterator1
2924     __rotate_adaptive(_BidirectionalIterator1 __first,
2925                       _BidirectionalIterator1 __middle,
2926                       _BidirectionalIterator1 __last,
2927                       _Distance __len1, _Distance __len2,
2928                       _BidirectionalIterator2 __buffer,
2929                       _Distance __buffer_size)
2930     {
2931       _BidirectionalIterator2 __buffer_end;
2932       if (__len1 > __len2 && __len2 <= __buffer_size)
2933         {
2934           if (__len2)
2935             {
2936               __buffer_end = _GLIBCXX_MOVE3(__middle, __last, __buffer);
2937               _GLIBCXX_MOVE_BACKWARD3(__first, __middle, __last);
2938               return _GLIBCXX_MOVE3(__buffer, __buffer_end, __first);
2939             }
2940           else
2941             return __first;
2942         }
2943       else if (__len1 <= __buffer_size)
2944         {
2945           if (__len1)
2946             {
2947               __buffer_end = _GLIBCXX_MOVE3(__first, __middle, __buffer);
2948               _GLIBCXX_MOVE3(__middle, __last, __first);
2949               return _GLIBCXX_MOVE_BACKWARD3(__buffer, __buffer_end, __last);
2950             }
2951           else
2952             return __last;
2953         }
2954       else
2955         {
2956           std::rotate(__first, __middle, __last);
2957           std::advance(__first, std::distance(__middle, __last));
2958           return __first;
2959         }
2960     }
2961
2962   /// This is a helper function for the merge routines.
2963   template<typename _BidirectionalIterator, typename _Distance,
2964            typename _Pointer>
2965     void
2966     __merge_adaptive(_BidirectionalIterator __first,
2967                      _BidirectionalIterator __middle,
2968                      _BidirectionalIterator __last,
2969                      _Distance __len1, _Distance __len2,
2970                      _Pointer __buffer, _Distance __buffer_size)
2971     {
2972       if (__len1 <= __len2 && __len1 <= __buffer_size)
2973         {
2974           _Pointer __buffer_end = _GLIBCXX_MOVE3(__first, __middle, __buffer);
2975           std::__move_merge_adaptive(__buffer, __buffer_end, __middle, __last,
2976                                      __first);
2977         }
2978       else if (__len2 <= __buffer_size)
2979         {
2980           _Pointer __buffer_end = _GLIBCXX_MOVE3(__middle, __last, __buffer);
2981           std::__move_merge_adaptive_backward(__first, __middle, __buffer,
2982                                               __buffer_end, __last);
2983         }
2984       else
2985         {
2986           _BidirectionalIterator __first_cut = __first;
2987           _BidirectionalIterator __second_cut = __middle;
2988           _Distance __len11 = 0;
2989           _Distance __len22 = 0;
2990           if (__len1 > __len2)
2991             {
2992               __len11 = __len1 / 2;
2993               std::advance(__first_cut, __len11);
2994               __second_cut = std::lower_bound(__middle, __last,
2995                                               *__first_cut);
2996               __len22 = std::distance(__middle, __second_cut);
2997             }
2998           else
2999             {
3000               __len22 = __len2 / 2;
3001               std::advance(__second_cut, __len22);
3002               __first_cut = std::upper_bound(__first, __middle,
3003                                              *__second_cut);
3004               __len11 = std::distance(__first, __first_cut);
3005             }
3006           _BidirectionalIterator __new_middle =
3007             std::__rotate_adaptive(__first_cut, __middle, __second_cut,
3008                                    __len1 - __len11, __len22, __buffer,
3009                                    __buffer_size);
3010           std::__merge_adaptive(__first, __first_cut, __new_middle, __len11,
3011                                 __len22, __buffer, __buffer_size);
3012           std::__merge_adaptive(__new_middle, __second_cut, __last,
3013                                 __len1 - __len11,
3014                                 __len2 - __len22, __buffer, __buffer_size);
3015         }
3016     }
3017
3018   /// This is a helper function for the merge routines.
3019   template<typename _BidirectionalIterator, typename _Distance,
3020            typename _Pointer, typename _Compare>
3021     void
3022     __merge_adaptive(_BidirectionalIterator __first,
3023                      _BidirectionalIterator __middle,
3024                      _BidirectionalIterator __last,
3025                      _Distance __len1, _Distance __len2,
3026                      _Pointer __buffer, _Distance __buffer_size,
3027                      _Compare __comp)
3028     {
3029       if (__len1 <= __len2 && __len1 <= __buffer_size)
3030         {
3031           _Pointer __buffer_end = _GLIBCXX_MOVE3(__first, __middle, __buffer);
3032           std::__move_merge_adaptive(__buffer, __buffer_end, __middle, __last,
3033                                      __first, __comp);
3034         }
3035       else if (__len2 <= __buffer_size)
3036         {
3037           _Pointer __buffer_end = _GLIBCXX_MOVE3(__middle, __last, __buffer);
3038           std::__move_merge_adaptive_backward(__first, __middle, __buffer,
3039                                               __buffer_end, __last, __comp);
3040         }
3041       else
3042         {
3043           _BidirectionalIterator __first_cut = __first;
3044           _BidirectionalIterator __second_cut = __middle;
3045           _Distance __len11 = 0;
3046           _Distance __len22 = 0;
3047           if (__len1 > __len2)
3048             {
3049               __len11 = __len1 / 2;
3050               std::advance(__first_cut, __len11);
3051               __second_cut = std::lower_bound(__middle, __last, *__first_cut,
3052                                               __comp);
3053               __len22 = std::distance(__middle, __second_cut);
3054             }
3055           else
3056             {
3057               __len22 = __len2 / 2;
3058               std::advance(__second_cut, __len22);
3059               __first_cut = std::upper_bound(__first, __middle, *__second_cut,
3060                                              __comp);
3061               __len11 = std::distance(__first, __first_cut);
3062             }
3063           _BidirectionalIterator __new_middle =
3064             std::__rotate_adaptive(__first_cut, __middle, __second_cut,
3065                                    __len1 - __len11, __len22, __buffer,
3066                                    __buffer_size);
3067           std::__merge_adaptive(__first, __first_cut, __new_middle, __len11,
3068                                 __len22, __buffer, __buffer_size, __comp);
3069           std::__merge_adaptive(__new_middle, __second_cut, __last,
3070                                 __len1 - __len11,
3071                                 __len2 - __len22, __buffer,
3072                                 __buffer_size, __comp);
3073         }
3074     }
3075
3076   /// This is a helper function for the merge routines.
3077   template<typename _BidirectionalIterator, typename _Distance>
3078     void
3079     __merge_without_buffer(_BidirectionalIterator __first,
3080                            _BidirectionalIterator __middle,
3081                            _BidirectionalIterator __last,
3082                            _Distance __len1, _Distance __len2)
3083     {
3084       if (__len1 == 0 || __len2 == 0)
3085         return;
3086       if (__len1 + __len2 == 2)
3087         {
3088           if (*__middle < *__first)
3089             std::iter_swap(__first, __middle);
3090           return;
3091         }
3092       _BidirectionalIterator __first_cut = __first;
3093       _BidirectionalIterator __second_cut = __middle;
3094       _Distance __len11 = 0;
3095       _Distance __len22 = 0;
3096       if (__len1 > __len2)
3097         {
3098           __len11 = __len1 / 2;
3099           std::advance(__first_cut, __len11);
3100           __second_cut = std::lower_bound(__middle, __last, *__first_cut);
3101           __len22 = std::distance(__middle, __second_cut);
3102         }
3103       else
3104         {
3105           __len22 = __len2 / 2;
3106           std::advance(__second_cut, __len22);
3107           __first_cut = std::upper_bound(__first, __middle, *__second_cut);
3108           __len11 = std::distance(__first, __first_cut);
3109         }
3110       std::rotate(__first_cut, __middle, __second_cut);
3111       _BidirectionalIterator __new_middle = __first_cut;
3112       std::advance(__new_middle, std::distance(__middle, __second_cut));
3113       std::__merge_without_buffer(__first, __first_cut, __new_middle,
3114                                   __len11, __len22);
3115       std::__merge_without_buffer(__new_middle, __second_cut, __last,
3116                                   __len1 - __len11, __len2 - __len22);
3117     }
3118
3119   /// This is a helper function for the merge routines.
3120   template<typename _BidirectionalIterator, typename _Distance,
3121            typename _Compare>
3122     void
3123     __merge_without_buffer(_BidirectionalIterator __first,
3124                            _BidirectionalIterator __middle,
3125                            _BidirectionalIterator __last,
3126                            _Distance __len1, _Distance __len2,
3127                            _Compare __comp)
3128     {
3129       if (__len1 == 0 || __len2 == 0)
3130         return;
3131       if (__len1 + __len2 == 2)
3132         {
3133           if (__comp(*__middle, *__first))
3134             std::iter_swap(__first, __middle);
3135           return;
3136         }
3137       _BidirectionalIterator __first_cut = __first;
3138       _BidirectionalIterator __second_cut = __middle;
3139       _Distance __len11 = 0;
3140       _Distance __len22 = 0;
3141       if (__len1 > __len2)
3142         {
3143           __len11 = __len1 / 2;
3144           std::advance(__first_cut, __len11);
3145           __second_cut = std::lower_bound(__middle, __last, *__first_cut,
3146                                           __comp);
3147           __len22 = std::distance(__middle, __second_cut);
3148         }
3149       else
3150         {
3151           __len22 = __len2 / 2;
3152           std::advance(__second_cut, __len22);
3153           __first_cut = std::upper_bound(__first, __middle, *__second_cut,
3154                                          __comp);
3155           __len11 = std::distance(__first, __first_cut);
3156         }
3157       std::rotate(__first_cut, __middle, __second_cut);
3158       _BidirectionalIterator __new_middle = __first_cut;
3159       std::advance(__new_middle, std::distance(__middle, __second_cut));
3160       std::__merge_without_buffer(__first, __first_cut, __new_middle,
3161                                   __len11, __len22, __comp);
3162       std::__merge_without_buffer(__new_middle, __second_cut, __last,
3163                                   __len1 - __len11, __len2 - __len22, __comp);
3164     }
3165
3166   /**
3167    *  @brief Merges two sorted ranges in place.
3168    *  @ingroup sorting_algorithms
3169    *  @param  __first   An iterator.
3170    *  @param  __middle  Another iterator.
3171    *  @param  __last    Another iterator.
3172    *  @return  Nothing.
3173    *
3174    *  Merges two sorted and consecutive ranges, [__first,__middle) and
3175    *  [__middle,__last), and puts the result in [__first,__last).  The
3176    *  output will be sorted.  The sort is @e stable, that is, for
3177    *  equivalent elements in the two ranges, elements from the first
3178    *  range will always come before elements from the second.
3179    *
3180    *  If enough additional memory is available, this takes (__last-__first)-1
3181    *  comparisons.  Otherwise an NlogN algorithm is used, where N is
3182    *  distance(__first,__last).
3183   */
3184   template<typename _BidirectionalIterator>
3185     void
3186     inplace_merge(_BidirectionalIterator __first,
3187                   _BidirectionalIterator __middle,
3188                   _BidirectionalIterator __last)
3189     {
3190       typedef typename iterator_traits<_BidirectionalIterator>::value_type
3191           _ValueType;
3192       typedef typename iterator_traits<_BidirectionalIterator>::difference_type
3193           _DistanceType;
3194
3195       // concept requirements
3196       __glibcxx_function_requires(_Mutable_BidirectionalIteratorConcept<
3197             _BidirectionalIterator>)
3198       __glibcxx_function_requires(_LessThanComparableConcept<_ValueType>)
3199       __glibcxx_requires_sorted(__first, __middle);
3200       __glibcxx_requires_sorted(__middle, __last);
3201
3202       if (__first == __middle || __middle == __last)
3203         return;
3204
3205       _DistanceType __len1 = std::distance(__first, __middle);
3206       _DistanceType __len2 = std::distance(__middle, __last);
3207
3208       _Temporary_buffer<_BidirectionalIterator, _ValueType> __buf(__first,
3209                                                                   __last);
3210       if (__buf.begin() == 0)
3211         std::__merge_without_buffer(__first, __middle, __last, __len1, __len2);
3212       else
3213         std::__merge_adaptive(__first, __middle, __last, __len1, __len2,
3214                               __buf.begin(), _DistanceType(__buf.size()));
3215     }
3216
3217   /**
3218    *  @brief Merges two sorted ranges in place.
3219    *  @ingroup sorting_algorithms
3220    *  @param  __first   An iterator.
3221    *  @param  __middle  Another iterator.
3222    *  @param  __last    Another iterator.
3223    *  @param  __comp    A functor to use for comparisons.
3224    *  @return  Nothing.
3225    *
3226    *  Merges two sorted and consecutive ranges, [__first,__middle) and
3227    *  [middle,last), and puts the result in [__first,__last).  The output will
3228    *  be sorted.  The sort is @e stable, that is, for equivalent
3229    *  elements in the two ranges, elements from the first range will always
3230    *  come before elements from the second.
3231    *
3232    *  If enough additional memory is available, this takes (__last-__first)-1
3233    *  comparisons.  Otherwise an NlogN algorithm is used, where N is
3234    *  distance(__first,__last).
3235    *
3236    *  The comparison function should have the same effects on ordering as
3237    *  the function used for the initial sort.
3238   */
3239   template<typename _BidirectionalIterator, typename _Compare>
3240     void
3241     inplace_merge(_BidirectionalIterator __first,
3242                   _BidirectionalIterator __middle,
3243                   _BidirectionalIterator __last,
3244                   _Compare __comp)
3245     {
3246       typedef typename iterator_traits<_BidirectionalIterator>::value_type
3247           _ValueType;
3248       typedef typename iterator_traits<_BidirectionalIterator>::difference_type
3249           _DistanceType;
3250
3251       // concept requirements
3252       __glibcxx_function_requires(_Mutable_BidirectionalIteratorConcept<
3253             _BidirectionalIterator>)
3254       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
3255             _ValueType, _ValueType>)
3256       __glibcxx_requires_sorted_pred(__first, __middle, __comp);
3257       __glibcxx_requires_sorted_pred(__middle, __last, __comp);
3258
3259       if (__first == __middle || __middle == __last)
3260         return;
3261
3262       const _DistanceType __len1 = std::distance(__first, __middle);
3263       const _DistanceType __len2 = std::distance(__middle, __last);
3264
3265       _Temporary_buffer<_BidirectionalIterator, _ValueType> __buf(__first,
3266                                                                   __last);
3267       if (__buf.begin() == 0)
3268         std::__merge_without_buffer(__first, __middle, __last, __len1,
3269                                     __len2, __comp);
3270       else
3271         std::__merge_adaptive(__first, __middle, __last, __len1, __len2,
3272                               __buf.begin(), _DistanceType(__buf.size()),
3273                               __comp);
3274     }
3275
3276
3277   /// This is a helper function for the __merge_sort_loop routines.
3278   template<typename _InputIterator1, typename _InputIterator2,
3279            typename _OutputIterator>
3280     _OutputIterator
3281     __move_merge(_InputIterator1 __first1, _InputIterator1 __last1,
3282                  _InputIterator2 __first2, _InputIterator2 __last2,
3283                  _OutputIterator __result)
3284     {
3285       while (__first1 != __last1 && __first2 != __last2)
3286         {
3287           if (*__first2 < *__first1)
3288             {
3289               *__result = _GLIBCXX_MOVE(*__first2);
3290               ++__first2;
3291             }
3292           else
3293             {
3294               *__result = _GLIBCXX_MOVE(*__first1);
3295               ++__first1;
3296             }
3297           ++__result;
3298         }
3299       return _GLIBCXX_MOVE3(__first2, __last2,
3300                             _GLIBCXX_MOVE3(__first1, __last1,
3301                                            __result));
3302     }
3303
3304   /// This is a helper function for the __merge_sort_loop routines.
3305   template<typename _InputIterator1, typename _InputIterator2,
3306            typename _OutputIterator, typename _Compare>
3307     _OutputIterator
3308     __move_merge(_InputIterator1 __first1, _InputIterator1 __last1,
3309                  _InputIterator2 __first2, _InputIterator2 __last2,
3310                  _OutputIterator __result, _Compare __comp)
3311     {
3312       while (__first1 != __last1 && __first2 != __last2)
3313         {
3314           if (__comp(*__first2, *__first1))
3315             {
3316               *__result = _GLIBCXX_MOVE(*__first2);
3317               ++__first2;
3318             }
3319           else
3320             {
3321               *__result = _GLIBCXX_MOVE(*__first1);
3322               ++__first1;
3323             }
3324           ++__result;
3325         }
3326       return _GLIBCXX_MOVE3(__first2, __last2,
3327                             _GLIBCXX_MOVE3(__first1, __last1,
3328                                            __result));
3329     }
3330
3331   template<typename _RandomAccessIterator1, typename _RandomAccessIterator2,
3332            typename _Distance>
3333     void
3334     __merge_sort_loop(_RandomAccessIterator1 __first,
3335                       _RandomAccessIterator1 __last,
3336                       _RandomAccessIterator2 __result,
3337                       _Distance __step_size)
3338     {
3339       const _Distance __two_step = 2 * __step_size;
3340
3341       while (__last - __first >= __two_step)
3342         {
3343           __result = std::__move_merge(__first, __first + __step_size,
3344                                        __first + __step_size,
3345                                        __first + __two_step, __result);
3346           __first += __two_step;
3347         }
3348
3349       __step_size = std::min(_Distance(__last - __first), __step_size);
3350       std::__move_merge(__first, __first + __step_size,
3351                         __first + __step_size, __last, __result);
3352     }
3353
3354   template<typename _RandomAccessIterator1, typename _RandomAccessIterator2,
3355            typename _Distance, typename _Compare>
3356     void
3357     __merge_sort_loop(_RandomAccessIterator1 __first,
3358                       _RandomAccessIterator1 __last,
3359                       _RandomAccessIterator2 __result, _Distance __step_size,
3360                       _Compare __comp)
3361     {
3362       const _Distance __two_step = 2 * __step_size;
3363
3364       while (__last - __first >= __two_step)
3365         {
3366           __result = std::__move_merge(__first, __first + __step_size,
3367                                        __first + __step_size,
3368                                        __first + __two_step,
3369                                        __result, __comp);
3370           __first += __two_step;
3371         }
3372       __step_size = std::min(_Distance(__last - __first), __step_size);
3373
3374       std::__move_merge(__first,__first + __step_size,
3375                         __first + __step_size, __last, __result, __comp);
3376     }
3377
3378   template<typename _RandomAccessIterator, typename _Distance>
3379     void
3380     __chunk_insertion_sort(_RandomAccessIterator __first,
3381                            _RandomAccessIterator __last,
3382                            _Distance __chunk_size)
3383     {
3384       while (__last - __first >= __chunk_size)
3385         {
3386           std::__insertion_sort(__first, __first + __chunk_size);
3387           __first += __chunk_size;
3388         }
3389       std::__insertion_sort(__first, __last);
3390     }
3391
3392   template<typename _RandomAccessIterator, typename _Distance,
3393            typename _Compare>
3394     void
3395     __chunk_insertion_sort(_RandomAccessIterator __first,
3396                            _RandomAccessIterator __last,
3397                            _Distance __chunk_size, _Compare __comp)
3398     {
3399       while (__last - __first >= __chunk_size)
3400         {
3401           std::__insertion_sort(__first, __first + __chunk_size, __comp);
3402           __first += __chunk_size;
3403         }
3404       std::__insertion_sort(__first, __last, __comp);
3405     }
3406
3407   enum { _S_chunk_size = 7 };
3408
3409   template<typename _RandomAccessIterator, typename _Pointer>
3410     void
3411     __merge_sort_with_buffer(_RandomAccessIterator __first,
3412                              _RandomAccessIterator __last,
3413                              _Pointer __buffer)
3414     {
3415       typedef typename iterator_traits<_RandomAccessIterator>::difference_type
3416         _Distance;
3417
3418       const _Distance __len = __last - __first;
3419       const _Pointer __buffer_last = __buffer + __len;
3420
3421       _Distance __step_size = _S_chunk_size;
3422       std::__chunk_insertion_sort(__first, __last, __step_size);
3423
3424       while (__step_size < __len)
3425         {
3426           std::__merge_sort_loop(__first, __last, __buffer, __step_size);
3427           __step_size *= 2;
3428           std::__merge_sort_loop(__buffer, __buffer_last, __first, __step_size);
3429           __step_size *= 2;
3430         }
3431     }
3432
3433   template<typename _RandomAccessIterator, typename _Pointer, typename _Compare>
3434     void
3435     __merge_sort_with_buffer(_RandomAccessIterator __first,
3436                              _RandomAccessIterator __last,
3437                              _Pointer __buffer, _Compare __comp)
3438     {
3439       typedef typename iterator_traits<_RandomAccessIterator>::difference_type
3440         _Distance;
3441
3442       const _Distance __len = __last - __first;
3443       const _Pointer __buffer_last = __buffer + __len;
3444
3445       _Distance __step_size = _S_chunk_size;
3446       std::__chunk_insertion_sort(__first, __last, __step_size, __comp);
3447
3448       while (__step_size < __len)
3449         {
3450           std::__merge_sort_loop(__first, __last, __buffer,
3451                                  __step_size, __comp);
3452           __step_size *= 2;
3453           std::__merge_sort_loop(__buffer, __buffer_last, __first,
3454                                  __step_size, __comp);
3455           __step_size *= 2;
3456         }
3457     }
3458
3459   template<typename _RandomAccessIterator, typename _Pointer,
3460            typename _Distance>
3461     void
3462     __stable_sort_adaptive(_RandomAccessIterator __first,
3463                            _RandomAccessIterator __last,
3464                            _Pointer __buffer, _Distance __buffer_size)
3465     {
3466       const _Distance __len = (__last - __first + 1) / 2;
3467       const _RandomAccessIterator __middle = __first + __len;
3468       if (__len > __buffer_size)
3469         {
3470           std::__stable_sort_adaptive(__first, __middle,
3471                                       __buffer, __buffer_size);
3472           std::__stable_sort_adaptive(__middle, __last,
3473                                       __buffer, __buffer_size);
3474         }
3475       else
3476         {
3477           std::__merge_sort_with_buffer(__first, __middle, __buffer);
3478           std::__merge_sort_with_buffer(__middle, __last, __buffer);
3479         }
3480       std::__merge_adaptive(__first, __middle, __last,
3481                             _Distance(__middle - __first),
3482                             _Distance(__last - __middle),
3483                             __buffer, __buffer_size);
3484     }
3485
3486   template<typename _RandomAccessIterator, typename _Pointer,
3487            typename _Distance, typename _Compare>
3488     void
3489     __stable_sort_adaptive(_RandomAccessIterator __first,
3490                            _RandomAccessIterator __last,
3491                            _Pointer __buffer, _Distance __buffer_size,
3492                            _Compare __comp)
3493     {
3494       const _Distance __len = (__last - __first + 1) / 2;
3495       const _RandomAccessIterator __middle = __first + __len;
3496       if (__len > __buffer_size)
3497         {
3498           std::__stable_sort_adaptive(__first, __middle, __buffer,
3499                                       __buffer_size, __comp);
3500           std::__stable_sort_adaptive(__middle, __last, __buffer,
3501                                       __buffer_size, __comp);
3502         }
3503       else
3504         {
3505           std::__merge_sort_with_buffer(__first, __middle, __buffer, __comp);
3506           std::__merge_sort_with_buffer(__middle, __last, __buffer, __comp);
3507         }
3508       std::__merge_adaptive(__first, __middle, __last,
3509                             _Distance(__middle - __first),
3510                             _Distance(__last - __middle),
3511                             __buffer, __buffer_size,
3512                             __comp);
3513     }
3514
3515   /// This is a helper function for the stable sorting routines.
3516   template<typename _RandomAccessIterator>
3517     void
3518     __inplace_stable_sort(_RandomAccessIterator __first,
3519                           _RandomAccessIterator __last)
3520     {
3521       if (__last - __first < 15)
3522         {
3523           std::__insertion_sort(__first, __last);
3524           return;
3525         }
3526       _RandomAccessIterator __middle = __first + (__last - __first) / 2;
3527       std::__inplace_stable_sort(__first, __middle);
3528       std::__inplace_stable_sort(__middle, __last);
3529       std::__merge_without_buffer(__first, __middle, __last,
3530                                   __middle - __first,
3531                                   __last - __middle);
3532     }
3533
3534   /// This is a helper function for the stable sorting routines.
3535   template<typename _RandomAccessIterator, typename _Compare>
3536     void
3537     __inplace_stable_sort(_RandomAccessIterator __first,
3538                           _RandomAccessIterator __last, _Compare __comp)
3539     {
3540       if (__last - __first < 15)
3541         {
3542           std::__insertion_sort(__first, __last, __comp);
3543           return;
3544         }
3545       _RandomAccessIterator __middle = __first + (__last - __first) / 2;
3546       std::__inplace_stable_sort(__first, __middle, __comp);
3547       std::__inplace_stable_sort(__middle, __last, __comp);
3548       std::__merge_without_buffer(__first, __middle, __last,
3549                                   __middle - __first,
3550                                   __last - __middle,
3551                                   __comp);
3552     }
3553
3554   // stable_sort
3555
3556   // Set algorithms: includes, set_union, set_intersection, set_difference,
3557   // set_symmetric_difference.  All of these algorithms have the precondition
3558   // that their input ranges are sorted and the postcondition that their output
3559   // ranges are sorted.
3560
3561   /**
3562    *  @brief Determines whether all elements of a sequence exists in a range.
3563    *  @param  __first1  Start of search range.
3564    *  @param  __last1   End of search range.
3565    *  @param  __first2  Start of sequence
3566    *  @param  __last2   End of sequence.
3567    *  @return  True if each element in [__first2,__last2) is contained in order
3568    *  within [__first1,__last1).  False otherwise.
3569    *  @ingroup set_algorithms
3570    *
3571    *  This operation expects both [__first1,__last1) and
3572    *  [__first2,__last2) to be sorted.  Searches for the presence of
3573    *  each element in [__first2,__last2) within [__first1,__last1).
3574    *  The iterators over each range only move forward, so this is a
3575    *  linear algorithm.  If an element in [__first2,__last2) is not
3576    *  found before the search iterator reaches @p __last2, false is
3577    *  returned.
3578   */
3579   template<typename _InputIterator1, typename _InputIterator2>
3580     bool
3581     includes(_InputIterator1 __first1, _InputIterator1 __last1,
3582              _InputIterator2 __first2, _InputIterator2 __last2)
3583     {
3584       typedef typename iterator_traits<_InputIterator1>::value_type
3585         _ValueType1;
3586       typedef typename iterator_traits<_InputIterator2>::value_type
3587         _ValueType2;
3588
3589       // concept requirements
3590       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
3591       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
3592       __glibcxx_function_requires(_LessThanOpConcept<_ValueType1, _ValueType2>)
3593       __glibcxx_function_requires(_LessThanOpConcept<_ValueType2, _ValueType1>)
3594       __glibcxx_requires_sorted_set(__first1, __last1, __first2);
3595       __glibcxx_requires_sorted_set(__first2, __last2, __first1);
3596
3597       while (__first1 != __last1 && __first2 != __last2)
3598         if (*__first2 < *__first1)
3599           return false;
3600         else if(*__first1 < *__first2)
3601           ++__first1;
3602         else
3603           ++__first1, ++__first2;
3604
3605       return __first2 == __last2;
3606     }
3607
3608   /**
3609    *  @brief Determines whether all elements of a sequence exists in a range
3610    *  using comparison.
3611    *  @ingroup set_algorithms
3612    *  @param  __first1  Start of search range.
3613    *  @param  __last1   End of search range.
3614    *  @param  __first2  Start of sequence
3615    *  @param  __last2   End of sequence.
3616    *  @param  __comp    Comparison function to use.
3617    *  @return True if each element in [__first2,__last2) is contained
3618    *  in order within [__first1,__last1) according to comp.  False
3619    *  otherwise.  @ingroup set_algorithms
3620    *
3621    *  This operation expects both [__first1,__last1) and
3622    *  [__first2,__last2) to be sorted.  Searches for the presence of
3623    *  each element in [__first2,__last2) within [__first1,__last1),
3624    *  using comp to decide.  The iterators over each range only move
3625    *  forward, so this is a linear algorithm.  If an element in
3626    *  [__first2,__last2) is not found before the search iterator
3627    *  reaches @p __last2, false is returned.
3628   */
3629   template<typename _InputIterator1, typename _InputIterator2,
3630            typename _Compare>
3631     bool
3632     includes(_InputIterator1 __first1, _InputIterator1 __last1,
3633              _InputIterator2 __first2, _InputIterator2 __last2,
3634              _Compare __comp)
3635     {
3636       typedef typename iterator_traits<_InputIterator1>::value_type
3637         _ValueType1;
3638       typedef typename iterator_traits<_InputIterator2>::value_type
3639         _ValueType2;
3640
3641       // concept requirements
3642       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
3643       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
3644       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
3645                                   _ValueType1, _ValueType2>)
3646       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
3647                                   _ValueType2, _ValueType1>)
3648       __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp);
3649       __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp);
3650
3651       while (__first1 != __last1 && __first2 != __last2)
3652         if (__comp(*__first2, *__first1))
3653           return false;
3654         else if(__comp(*__first1, *__first2))
3655           ++__first1;
3656         else
3657           ++__first1, ++__first2;
3658
3659       return __first2 == __last2;
3660     }
3661
3662   // nth_element
3663   // merge
3664   // set_difference
3665   // set_intersection
3666   // set_union
3667   // stable_sort
3668   // set_symmetric_difference
3669   // min_element
3670   // max_element
3671
3672   /**
3673    *  @brief  Permute range into the next @e dictionary ordering.
3674    *  @ingroup sorting_algorithms
3675    *  @param  __first  Start of range.
3676    *  @param  __last   End of range.
3677    *  @return  False if wrapped to first permutation, true otherwise.
3678    *
3679    *  Treats all permutations of the range as a set of @e dictionary sorted
3680    *  sequences.  Permutes the current sequence into the next one of this set.
3681    *  Returns true if there are more sequences to generate.  If the sequence
3682    *  is the largest of the set, the smallest is generated and false returned.
3683   */
3684   template<typename _BidirectionalIterator>
3685     bool
3686     next_permutation(_BidirectionalIterator __first,
3687                      _BidirectionalIterator __last)
3688     {
3689       // concept requirements
3690       __glibcxx_function_requires(_BidirectionalIteratorConcept<
3691                                   _BidirectionalIterator>)
3692       __glibcxx_function_requires(_LessThanComparableConcept<
3693             typename iterator_traits<_BidirectionalIterator>::value_type>)
3694       __glibcxx_requires_valid_range(__first, __last);
3695
3696       if (__first == __last)
3697         return false;
3698       _BidirectionalIterator __i = __first;
3699       ++__i;
3700       if (__i == __last)
3701         return false;
3702       __i = __last;
3703       --__i;
3704
3705       for(;;)
3706         {
3707           _BidirectionalIterator __ii = __i;
3708           --__i;
3709           if (*__i < *__ii)
3710             {
3711               _BidirectionalIterator __j = __last;
3712               while (!(*__i < *--__j))
3713                 {}
3714               std::iter_swap(__i, __j);
3715               std::reverse(__ii, __last);
3716               return true;
3717             }
3718           if (__i == __first)
3719             {
3720               std::reverse(__first, __last);
3721               return false;
3722             }
3723         }
3724     }
3725
3726   /**
3727    *  @brief  Permute range into the next @e dictionary ordering using
3728    *          comparison functor.
3729    *  @ingroup sorting_algorithms
3730    *  @param  __first  Start of range.
3731    *  @param  __last   End of range.
3732    *  @param  __comp   A comparison functor.
3733    *  @return  False if wrapped to first permutation, true otherwise.
3734    *
3735    *  Treats all permutations of the range [__first,__last) as a set of
3736    *  @e dictionary sorted sequences ordered by @p __comp.  Permutes the current
3737    *  sequence into the next one of this set.  Returns true if there are more
3738    *  sequences to generate.  If the sequence is the largest of the set, the
3739    *  smallest is generated and false returned.
3740   */
3741   template<typename _BidirectionalIterator, typename _Compare>
3742     bool
3743     next_permutation(_BidirectionalIterator __first,
3744                      _BidirectionalIterator __last, _Compare __comp)
3745     {
3746       // concept requirements
3747       __glibcxx_function_requires(_BidirectionalIteratorConcept<
3748                                   _BidirectionalIterator>)
3749       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
3750             typename iterator_traits<_BidirectionalIterator>::value_type,
3751             typename iterator_traits<_BidirectionalIterator>::value_type>)
3752       __glibcxx_requires_valid_range(__first, __last);
3753
3754       if (__first == __last)
3755         return false;
3756       _BidirectionalIterator __i = __first;
3757       ++__i;
3758       if (__i == __last)
3759         return false;
3760       __i = __last;
3761       --__i;
3762
3763       for(;;)
3764         {
3765           _BidirectionalIterator __ii = __i;
3766           --__i;
3767           if (__comp(*__i, *__ii))
3768             {
3769               _BidirectionalIterator __j = __last;
3770               while (!bool(__comp(*__i, *--__j)))
3771                 {}
3772               std::iter_swap(__i, __j);
3773               std::reverse(__ii, __last);
3774               return true;
3775             }
3776           if (__i == __first)
3777             {
3778               std::reverse(__first, __last);
3779               return false;
3780             }
3781         }
3782     }
3783
3784   /**
3785    *  @brief  Permute range into the previous @e dictionary ordering.
3786    *  @ingroup sorting_algorithms
3787    *  @param  __first  Start of range.
3788    *  @param  __last   End of range.
3789    *  @return  False if wrapped to last permutation, true otherwise.
3790    *
3791    *  Treats all permutations of the range as a set of @e dictionary sorted
3792    *  sequences.  Permutes the current sequence into the previous one of this
3793    *  set.  Returns true if there are more sequences to generate.  If the
3794    *  sequence is the smallest of the set, the largest is generated and false
3795    *  returned.
3796   */
3797   template<typename _BidirectionalIterator>
3798     bool
3799     prev_permutation(_BidirectionalIterator __first,
3800                      _BidirectionalIterator __last)
3801     {
3802       // concept requirements
3803       __glibcxx_function_requires(_BidirectionalIteratorConcept<
3804                                   _BidirectionalIterator>)
3805       __glibcxx_function_requires(_LessThanComparableConcept<
3806             typename iterator_traits<_BidirectionalIterator>::value_type>)
3807       __glibcxx_requires_valid_range(__first, __last);
3808
3809       if (__first == __last)
3810         return false;
3811       _BidirectionalIterator __i = __first;
3812       ++__i;
3813       if (__i == __last)
3814         return false;
3815       __i = __last;
3816       --__i;
3817
3818       for(;;)
3819         {
3820           _BidirectionalIterator __ii = __i;
3821           --__i;
3822           if (*__ii < *__i)
3823             {
3824               _BidirectionalIterator __j = __last;
3825               while (!(*--__j < *__i))
3826                 {}
3827               std::iter_swap(__i, __j);
3828               std::reverse(__ii, __last);
3829               return true;
3830             }
3831           if (__i == __first)
3832             {
3833               std::reverse(__first, __last);
3834               return false;
3835             }
3836         }
3837     }
3838
3839   /**
3840    *  @brief  Permute range into the previous @e dictionary ordering using
3841    *          comparison functor.
3842    *  @ingroup sorting_algorithms
3843    *  @param  __first  Start of range.
3844    *  @param  __last   End of range.
3845    *  @param  __comp   A comparison functor.
3846    *  @return  False if wrapped to last permutation, true otherwise.
3847    *
3848    *  Treats all permutations of the range [__first,__last) as a set of
3849    *  @e dictionary sorted sequences ordered by @p __comp.  Permutes the current
3850    *  sequence into the previous one of this set.  Returns true if there are
3851    *  more sequences to generate.  If the sequence is the smallest of the set,
3852    *  the largest is generated and false returned.
3853   */
3854   template<typename _BidirectionalIterator, typename _Compare>
3855     bool
3856     prev_permutation(_BidirectionalIterator __first,
3857                      _BidirectionalIterator __last, _Compare __comp)
3858     {
3859       // concept requirements
3860       __glibcxx_function_requires(_BidirectionalIteratorConcept<
3861                                   _BidirectionalIterator>)
3862       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
3863             typename iterator_traits<_BidirectionalIterator>::value_type,
3864             typename iterator_traits<_BidirectionalIterator>::value_type>)
3865       __glibcxx_requires_valid_range(__first, __last);
3866
3867       if (__first == __last)
3868         return false;
3869       _BidirectionalIterator __i = __first;
3870       ++__i;
3871       if (__i == __last)
3872         return false;
3873       __i = __last;
3874       --__i;
3875
3876       for(;;)
3877         {
3878           _BidirectionalIterator __ii = __i;
3879           --__i;
3880           if (__comp(*__ii, *__i))
3881             {
3882               _BidirectionalIterator __j = __last;
3883               while (!bool(__comp(*--__j, *__i)))
3884                 {}
3885               std::iter_swap(__i, __j);
3886               std::reverse(__ii, __last);
3887               return true;
3888             }
3889           if (__i == __first)
3890             {
3891               std::reverse(__first, __last);
3892               return false;
3893             }
3894         }
3895     }
3896
3897   // replace
3898   // replace_if
3899
3900   /**
3901    *  @brief Copy a sequence, replacing each element of one value with another
3902    *         value.
3903    *  @param  __first      An input iterator.
3904    *  @param  __last       An input iterator.
3905    *  @param  __result     An output iterator.
3906    *  @param  __old_value  The value to be replaced.
3907    *  @param  __new_value  The replacement value.
3908    *  @return   The end of the output sequence, @p result+(last-first).
3909    *
3910    *  Copies each element in the input range @p [__first,__last) to the
3911    *  output range @p [__result,__result+(__last-__first)) replacing elements
3912    *  equal to @p __old_value with @p __new_value.
3913   */
3914   template<typename _InputIterator, typename _OutputIterator, typename _Tp>
3915     _OutputIterator
3916     replace_copy(_InputIterator __first, _InputIterator __last,
3917                  _OutputIterator __result,
3918                  const _Tp& __old_value, const _Tp& __new_value)
3919     {
3920       // concept requirements
3921       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
3922       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
3923             typename iterator_traits<_InputIterator>::value_type>)
3924       __glibcxx_function_requires(_EqualOpConcept<
3925             typename iterator_traits<_InputIterator>::value_type, _Tp>)
3926       __glibcxx_requires_valid_range(__first, __last);
3927
3928       for (; __first != __last; ++__first, ++__result)
3929         if (*__first == __old_value)
3930           *__result = __new_value;
3931         else
3932           *__result = *__first;
3933       return __result;
3934     }
3935
3936   /**
3937    *  @brief Copy a sequence, replacing each value for which a predicate
3938    *         returns true with another value.
3939    *  @ingroup mutating_algorithms
3940    *  @param  __first      An input iterator.
3941    *  @param  __last       An input iterator.
3942    *  @param  __result     An output iterator.
3943    *  @param  __pred       A predicate.
3944    *  @param  __new_value  The replacement value.
3945    *  @return   The end of the output sequence, @p __result+(__last-__first).
3946    *
3947    *  Copies each element in the range @p [__first,__last) to the range
3948    *  @p [__result,__result+(__last-__first)) replacing elements for which
3949    *  @p __pred returns true with @p __new_value.
3950   */
3951   template<typename _InputIterator, typename _OutputIterator,
3952            typename _Predicate, typename _Tp>
3953     _OutputIterator
3954     replace_copy_if(_InputIterator __first, _InputIterator __last,
3955                     _OutputIterator __result,
3956                     _Predicate __pred, const _Tp& __new_value)
3957     {
3958       // concept requirements
3959       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
3960       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
3961             typename iterator_traits<_InputIterator>::value_type>)
3962       __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
3963             typename iterator_traits<_InputIterator>::value_type>)
3964       __glibcxx_requires_valid_range(__first, __last);
3965
3966       for (; __first != __last; ++__first, ++__result)
3967         if (__pred(*__first))
3968           *__result = __new_value;
3969         else
3970           *__result = *__first;
3971       return __result;
3972     }
3973
3974 #ifdef __GXX_EXPERIMENTAL_CXX0X__
3975   /**
3976    *  @brief  Determines whether the elements of a sequence are sorted.
3977    *  @ingroup sorting_algorithms
3978    *  @param  __first   An iterator.
3979    *  @param  __last    Another iterator.
3980    *  @return  True if the elements are sorted, false otherwise.
3981   */
3982   template<typename _ForwardIterator>
3983     inline bool
3984     is_sorted(_ForwardIterator __first, _ForwardIterator __last)
3985     { return std::is_sorted_until(__first, __last) == __last; }
3986
3987   /**
3988    *  @brief  Determines whether the elements of a sequence are sorted
3989    *          according to a comparison functor.
3990    *  @ingroup sorting_algorithms
3991    *  @param  __first   An iterator.
3992    *  @param  __last    Another iterator.
3993    *  @param  __comp    A comparison functor.
3994    *  @return  True if the elements are sorted, false otherwise.
3995   */
3996   template<typename _ForwardIterator, typename _Compare>
3997     inline bool
3998     is_sorted(_ForwardIterator __first, _ForwardIterator __last,
3999               _Compare __comp)
4000     { return std::is_sorted_until(__first, __last, __comp) == __last; }
4001
4002   /**
4003    *  @brief  Determines the end of a sorted sequence.
4004    *  @ingroup sorting_algorithms
4005    *  @param  __first   An iterator.
4006    *  @param  __last    Another iterator.
4007    *  @return  An iterator pointing to the last iterator i in [__first, __last)
4008    *           for which the range [__first, i) is sorted.
4009   */
4010   template<typename _ForwardIterator>
4011     _ForwardIterator
4012     is_sorted_until(_ForwardIterator __first, _ForwardIterator __last)
4013     {
4014       // concept requirements
4015       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
4016       __glibcxx_function_requires(_LessThanComparableConcept<
4017             typename iterator_traits<_ForwardIterator>::value_type>)
4018       __glibcxx_requires_valid_range(__first, __last);
4019
4020       if (__first == __last)
4021         return __last;
4022
4023       _ForwardIterator __next = __first;
4024       for (++__next; __next != __last; __first = __next, ++__next)
4025         if (*__next < *__first)
4026           return __next;
4027       return __next;
4028     }
4029
4030   /**
4031    *  @brief  Determines the end of a sorted sequence using comparison functor.
4032    *  @ingroup sorting_algorithms
4033    *  @param  __first   An iterator.
4034    *  @param  __last    Another iterator.
4035    *  @param  __comp    A comparison functor.
4036    *  @return  An iterator pointing to the last iterator i in [__first, __last)
4037    *           for which the range [__first, i) is sorted.
4038   */
4039   template<typename _ForwardIterator, typename _Compare>
4040     _ForwardIterator
4041     is_sorted_until(_ForwardIterator __first, _ForwardIterator __last,
4042                     _Compare __comp)
4043     {
4044       // concept requirements
4045       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
4046       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
4047             typename iterator_traits<_ForwardIterator>::value_type,
4048             typename iterator_traits<_ForwardIterator>::value_type>)
4049       __glibcxx_requires_valid_range(__first, __last);
4050
4051       if (__first == __last)
4052         return __last;
4053
4054       _ForwardIterator __next = __first;
4055       for (++__next; __next != __last; __first = __next, ++__next)
4056         if (__comp(*__next, *__first))
4057           return __next;
4058       return __next;
4059     }
4060
4061   /**
4062    *  @brief  Determines min and max at once as an ordered pair.
4063    *  @ingroup sorting_algorithms
4064    *  @param  __a  A thing of arbitrary type.
4065    *  @param  __b  Another thing of arbitrary type.
4066    *  @return A pair(__b, __a) if __b is smaller than __a, pair(__a,
4067    *  __b) otherwise.
4068   */
4069   template<typename _Tp>
4070     inline pair<const _Tp&, const _Tp&>
4071     minmax(const _Tp& __a, const _Tp& __b)
4072     {
4073       // concept requirements
4074       __glibcxx_function_requires(_LessThanComparableConcept<_Tp>)
4075
4076       return __b < __a ? pair<const _Tp&, const _Tp&>(__b, __a)
4077                        : pair<const _Tp&, const _Tp&>(__a, __b);
4078     }
4079
4080   /**
4081    *  @brief  Determines min and max at once as an ordered pair.
4082    *  @ingroup sorting_algorithms
4083    *  @param  __a  A thing of arbitrary type.
4084    *  @param  __b  Another thing of arbitrary type.
4085    *  @param  __comp  A @link comparison_functors comparison functor @endlink.
4086    *  @return A pair(__b, __a) if __b is smaller than __a, pair(__a,
4087    *  __b) otherwise.
4088   */
4089   template<typename _Tp, typename _Compare>
4090     inline pair<const _Tp&, const _Tp&>
4091     minmax(const _Tp& __a, const _Tp& __b, _Compare __comp)
4092     {
4093       return __comp(__b, __a) ? pair<const _Tp&, const _Tp&>(__b, __a)
4094                               : pair<const _Tp&, const _Tp&>(__a, __b);
4095     }
4096
4097   /**
4098    *  @brief  Return a pair of iterators pointing to the minimum and maximum
4099    *          elements in a range.
4100    *  @ingroup sorting_algorithms
4101    *  @param  __first  Start of range.
4102    *  @param  __last   End of range.
4103    *  @return  make_pair(m, M), where m is the first iterator i in
4104    *           [__first, __last) such that no other element in the range is
4105    *           smaller, and where M is the last iterator i in [__first, __last)
4106    *           such that no other element in the range is larger.
4107   */
4108   template<typename _ForwardIterator>
4109     pair<_ForwardIterator, _ForwardIterator>
4110     minmax_element(_ForwardIterator __first, _ForwardIterator __last)
4111     {
4112       // concept requirements
4113       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
4114       __glibcxx_function_requires(_LessThanComparableConcept<
4115             typename iterator_traits<_ForwardIterator>::value_type>)
4116       __glibcxx_requires_valid_range(__first, __last);
4117
4118       _ForwardIterator __next = __first;
4119       if (__first == __last
4120           || ++__next == __last)
4121         return std::make_pair(__first, __first);
4122
4123       _ForwardIterator __min, __max;
4124       if (*__next < *__first)
4125         {
4126           __min = __next;
4127           __max = __first;
4128         }
4129       else
4130         {
4131           __min = __first;
4132           __max = __next;
4133         }
4134
4135       __first = __next;
4136       ++__first;
4137
4138       while (__first != __last)
4139         {
4140           __next = __first;
4141           if (++__next == __last)
4142             {
4143               if (*__first < *__min)
4144                 __min = __first;
4145               else if (!(*__first < *__max))
4146                 __max = __first;
4147               break;
4148             }
4149
4150           if (*__next < *__first)
4151             {
4152               if (*__next < *__min)
4153                 __min = __next;
4154               if (!(*__first < *__max))
4155                 __max = __first;
4156             }
4157           else
4158             {
4159               if (*__first < *__min)
4160                 __min = __first;
4161               if (!(*__next < *__max))
4162                 __max = __next;
4163             }
4164
4165           __first = __next;
4166           ++__first;
4167         }
4168
4169       return std::make_pair(__min, __max);
4170     }
4171
4172   /**
4173    *  @brief  Return a pair of iterators pointing to the minimum and maximum
4174    *          elements in a range.
4175    *  @ingroup sorting_algorithms
4176    *  @param  __first  Start of range.
4177    *  @param  __last   End of range.
4178    *  @param  __comp   Comparison functor.
4179    *  @return  make_pair(m, M), where m is the first iterator i in
4180    *           [__first, __last) such that no other element in the range is
4181    *           smaller, and where M is the last iterator i in [__first, __last)
4182    *           such that no other element in the range is larger.
4183   */
4184   template<typename _ForwardIterator, typename _Compare>
4185     pair<_ForwardIterator, _ForwardIterator>
4186     minmax_element(_ForwardIterator __first, _ForwardIterator __last,
4187                    _Compare __comp)
4188     {
4189       // concept requirements
4190       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
4191       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
4192             typename iterator_traits<_ForwardIterator>::value_type,
4193             typename iterator_traits<_ForwardIterator>::value_type>)
4194       __glibcxx_requires_valid_range(__first, __last);
4195
4196       _ForwardIterator __next = __first;
4197       if (__first == __last
4198           || ++__next == __last)
4199         return std::make_pair(__first, __first);
4200
4201       _ForwardIterator __min, __max;
4202       if (__comp(*__next, *__first))
4203         {
4204           __min = __next;
4205           __max = __first;
4206         }
4207       else
4208         {
4209           __min = __first;
4210           __max = __next;
4211         }
4212
4213       __first = __next;
4214       ++__first;
4215
4216       while (__first != __last)
4217         {
4218           __next = __first;
4219           if (++__next == __last)
4220             {
4221               if (__comp(*__first, *__min))
4222                 __min = __first;
4223               else if (!__comp(*__first, *__max))
4224                 __max = __first;
4225               break;
4226             }
4227
4228           if (__comp(*__next, *__first))
4229             {
4230               if (__comp(*__next, *__min))
4231                 __min = __next;
4232               if (!__comp(*__first, *__max))
4233                 __max = __first;
4234             }
4235           else
4236             {
4237               if (__comp(*__first, *__min))
4238                 __min = __first;
4239               if (!__comp(*__next, *__max))
4240                 __max = __next;
4241             }
4242
4243           __first = __next;
4244           ++__first;
4245         }
4246
4247       return std::make_pair(__min, __max);
4248     }
4249
4250   // N2722 + DR 915.
4251   template<typename _Tp>
4252     inline _Tp
4253     min(initializer_list<_Tp> __l)
4254     { return *std::min_element(__l.begin(), __l.end()); }
4255
4256   template<typename _Tp, typename _Compare>
4257     inline _Tp
4258     min(initializer_list<_Tp> __l, _Compare __comp)
4259     { return *std::min_element(__l.begin(), __l.end(), __comp); }
4260
4261   template<typename _Tp>
4262     inline _Tp
4263     max(initializer_list<_Tp> __l)
4264     { return *std::max_element(__l.begin(), __l.end()); }
4265
4266   template<typename _Tp, typename _Compare>
4267     inline _Tp
4268     max(initializer_list<_Tp> __l, _Compare __comp)
4269     { return *std::max_element(__l.begin(), __l.end(), __comp); }
4270
4271   template<typename _Tp>
4272     inline pair<_Tp, _Tp>
4273     minmax(initializer_list<_Tp> __l)
4274     {
4275       pair<const _Tp*, const _Tp*> __p =
4276         std::minmax_element(__l.begin(), __l.end());
4277       return std::make_pair(*__p.first, *__p.second);
4278     }
4279
4280   template<typename _Tp, typename _Compare>
4281     inline pair<_Tp, _Tp>
4282     minmax(initializer_list<_Tp> __l, _Compare __comp)
4283     {
4284       pair<const _Tp*, const _Tp*> __p =
4285         std::minmax_element(__l.begin(), __l.end(), __comp);
4286       return std::make_pair(*__p.first, *__p.second);
4287     }
4288
4289   /**
4290    *  @brief  Checks whether a permutaion of the second sequence is equal
4291    *          to the first sequence.
4292    *  @ingroup non_mutating_algorithms
4293    *  @param  __first1  Start of first range.
4294    *  @param  __last1   End of first range.
4295    *  @param  __first2  Start of second range.
4296    *  @return true if there exists a permutation of the elements in the range
4297    *          [__first2, __first2 + (__last1 - __first1)), beginning with
4298    *          ForwardIterator2 begin, such that equal(__first1, __last1, begin)
4299    *          returns true; otherwise, returns false.
4300   */
4301   template<typename _ForwardIterator1, typename _ForwardIterator2>
4302     bool
4303     is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
4304                    _ForwardIterator2 __first2)
4305     {
4306       // Efficiently compare identical prefixes:  O(N) if sequences
4307       // have the same elements in the same order.
4308       for (; __first1 != __last1; ++__first1, ++__first2)
4309         if (!(*__first1 == *__first2))
4310           break;
4311
4312       if (__first1 == __last1)
4313         return true;
4314
4315       // Establish __last2 assuming equal ranges by iterating over the
4316       // rest of the list.
4317       _ForwardIterator2 __last2 = __first2;
4318       std::advance(__last2, std::distance(__first1, __last1));
4319       for (_ForwardIterator1 __scan = __first1; __scan != __last1; ++__scan)
4320         {
4321           if (__scan != _GLIBCXX_STD_A::find(__first1, __scan, *__scan))
4322             continue; // We've seen this one before.
4323
4324           auto __matches = std::count(__first2, __last2, *__scan);
4325           if (0 == __matches
4326               || std::count(__scan, __last1, *__scan) != __matches)
4327             return false;
4328         }
4329       return true;
4330     }
4331
4332   /**
4333    *  @brief  Checks whether a permutation of the second sequence is equal
4334    *          to the first sequence.
4335    *  @ingroup non_mutating_algorithms
4336    *  @param  __first1  Start of first range.
4337    *  @param  __last1   End of first range.
4338    *  @param  __first2  Start of second range.
4339    *  @param  __pred    A binary predicate.
4340    *  @return true if there exists a permutation of the elements in
4341    *          the range [__first2, __first2 + (__last1 - __first1)),
4342    *          beginning with ForwardIterator2 begin, such that
4343    *          equal(__first1, __last1, __begin, __pred) returns true;
4344    *          otherwise, returns false.
4345   */
4346   template<typename _ForwardIterator1, typename _ForwardIterator2,
4347            typename _BinaryPredicate>
4348     bool
4349     is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
4350                    _ForwardIterator2 __first2, _BinaryPredicate __pred)
4351     {
4352       // Efficiently compare identical prefixes:  O(N) if sequences
4353       // have the same elements in the same order.
4354       for (; __first1 != __last1; ++__first1, ++__first2)
4355         if (!bool(__pred(*__first1, *__first2)))
4356           break;
4357
4358       if (__first1 == __last1)
4359         return true;
4360
4361       // Establish __last2 assuming equal ranges by iterating over the
4362       // rest of the list.
4363       _ForwardIterator2 __last2 = __first2;
4364       std::advance(__last2, std::distance(__first1, __last1));
4365       for (_ForwardIterator1 __scan = __first1; __scan != __last1; ++__scan)
4366         {
4367           using std::placeholders::_1;
4368
4369           if (__scan != _GLIBCXX_STD_A::find_if(__first1, __scan,
4370                                                 std::bind(__pred, _1, *__scan)))
4371             continue; // We've seen this one before.
4372
4373           auto __matches = std::count_if(__first2, __last2,
4374                                          std::bind(__pred, _1, *__scan));
4375           if (0 == __matches
4376               || std::count_if(__scan, __last1,
4377                                std::bind(__pred, _1, *__scan)) != __matches)
4378             return false;
4379         }
4380       return true;
4381     }
4382
4383 #ifdef _GLIBCXX_USE_C99_STDINT_TR1
4384   /**
4385    *  @brief Shuffle the elements of a sequence using a uniform random
4386    *         number generator.
4387    *  @ingroup mutating_algorithms
4388    *  @param  __first   A forward iterator.
4389    *  @param  __last    A forward iterator.
4390    *  @param  __g       A UniformRandomNumberGenerator (26.5.1.3).
4391    *  @return  Nothing.
4392    *
4393    *  Reorders the elements in the range @p [__first,__last) using @p __g to
4394    *  provide random numbers.
4395   */
4396   template<typename _RandomAccessIterator,
4397            typename _UniformRandomNumberGenerator>
4398     void
4399     shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last,
4400             _UniformRandomNumberGenerator&& __g)
4401     {
4402       // concept requirements
4403       __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
4404             _RandomAccessIterator>)
4405       __glibcxx_requires_valid_range(__first, __last);
4406
4407       if (__first == __last)
4408         return;
4409
4410       typedef typename iterator_traits<_RandomAccessIterator>::difference_type
4411         _DistanceType;
4412
4413       typedef typename std::make_unsigned<_DistanceType>::type __ud_type;
4414       typedef typename std::uniform_int_distribution<__ud_type> __distr_type;
4415       typedef typename __distr_type::param_type __p_type;
4416       __distr_type __d;
4417
4418       for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i)
4419         std::iter_swap(__i, __first + __d(__g, __p_type(0, __i - __first)));
4420     }
4421 #endif
4422
4423 #endif // __GXX_EXPERIMENTAL_CXX0X__
4424
4425 _GLIBCXX_END_NAMESPACE_VERSION
4426
4427 _GLIBCXX_BEGIN_NAMESPACE_ALGO
4428
4429   /**
4430    *  @brief Apply a function to every element of a sequence.
4431    *  @ingroup non_mutating_algorithms
4432    *  @param  __first  An input iterator.
4433    *  @param  __last   An input iterator.
4434    *  @param  __f      A unary function object.
4435    *  @return   @p __f (std::move(@p __f) in C++0x).
4436    *
4437    *  Applies the function object @p __f to each element in the range
4438    *  @p [first,last).  @p __f must not modify the order of the sequence.
4439    *  If @p __f has a return value it is ignored.
4440   */
4441   template<typename _InputIterator, typename _Function>
4442     _Function
4443     for_each(_InputIterator __first, _InputIterator __last, _Function __f)
4444     {
4445       // concept requirements
4446       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
4447       __glibcxx_requires_valid_range(__first, __last);
4448       for (; __first != __last; ++__first)
4449         __f(*__first);
4450       return _GLIBCXX_MOVE(__f);
4451     }
4452
4453   /**
4454    *  @brief Find the first occurrence of a value in a sequence.
4455    *  @ingroup non_mutating_algorithms
4456    *  @param  __first  An input iterator.
4457    *  @param  __last   An input iterator.
4458    *  @param  __val    The value to find.
4459    *  @return   The first iterator @c i in the range @p [__first,__last)
4460    *  such that @c *i == @p __val, or @p __last if no such iterator exists.
4461   */
4462   template<typename _InputIterator, typename _Tp>
4463     inline _InputIterator
4464     find(_InputIterator __first, _InputIterator __last,
4465          const _Tp& __val)
4466     {
4467       // concept requirements
4468       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
4469       __glibcxx_function_requires(_EqualOpConcept<
4470                 typename iterator_traits<_InputIterator>::value_type, _Tp>)
4471       __glibcxx_requires_valid_range(__first, __last);
4472       return std::__find(__first, __last, __val,
4473                          std::__iterator_category(__first));
4474     }
4475
4476   /**
4477    *  @brief Find the first element in a sequence for which a
4478    *         predicate is true.
4479    *  @ingroup non_mutating_algorithms
4480    *  @param  __first  An input iterator.
4481    *  @param  __last   An input iterator.
4482    *  @param  __pred   A predicate.
4483    *  @return   The first iterator @c i in the range @p [__first,__last)
4484    *  such that @p __pred(*i) is true, or @p __last if no such iterator exists.
4485   */
4486   template<typename _InputIterator, typename _Predicate>
4487     inline _InputIterator
4488     find_if(_InputIterator __first, _InputIterator __last,
4489             _Predicate __pred)
4490     {
4491       // concept requirements
4492       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
4493       __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
4494               typename iterator_traits<_InputIterator>::value_type>)
4495       __glibcxx_requires_valid_range(__first, __last);
4496       return std::__find_if(__first, __last, __pred,
4497                             std::__iterator_category(__first));
4498     }
4499
4500   /**
4501    *  @brief  Find element from a set in a sequence.
4502    *  @ingroup non_mutating_algorithms
4503    *  @param  __first1  Start of range to search.
4504    *  @param  __last1   End of range to search.
4505    *  @param  __first2  Start of match candidates.
4506    *  @param  __last2   End of match candidates.
4507    *  @return   The first iterator @c i in the range
4508    *  @p [__first1,__last1) such that @c *i == @p *(i2) such that i2 is an
4509    *  iterator in [__first2,__last2), or @p __last1 if no such iterator exists.
4510    *
4511    *  Searches the range @p [__first1,__last1) for an element that is
4512    *  equal to some element in the range [__first2,__last2).  If
4513    *  found, returns an iterator in the range [__first1,__last1),
4514    *  otherwise returns @p __last1.
4515   */
4516   template<typename _InputIterator, typename _ForwardIterator>
4517     _InputIterator
4518     find_first_of(_InputIterator __first1, _InputIterator __last1,
4519                   _ForwardIterator __first2, _ForwardIterator __last2)
4520     {
4521       // concept requirements
4522       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
4523       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
4524       __glibcxx_function_requires(_EqualOpConcept<
4525             typename iterator_traits<_InputIterator>::value_type,
4526             typename iterator_traits<_ForwardIterator>::value_type>)
4527       __glibcxx_requires_valid_range(__first1, __last1);
4528       __glibcxx_requires_valid_range(__first2, __last2);
4529
4530       for (; __first1 != __last1; ++__first1)
4531         for (_ForwardIterator __iter = __first2; __iter != __last2; ++__iter)
4532           if (*__first1 == *__iter)
4533             return __first1;
4534       return __last1;
4535     }
4536
4537   /**
4538    *  @brief  Find element from a set in a sequence using a predicate.
4539    *  @ingroup non_mutating_algorithms
4540    *  @param  __first1  Start of range to search.
4541    *  @param  __last1   End of range to search.
4542    *  @param  __first2  Start of match candidates.
4543    *  @param  __last2   End of match candidates.
4544    *  @param  __comp    Predicate to use.
4545    *  @return   The first iterator @c i in the range
4546    *  @p [__first1,__last1) such that @c comp(*i, @p *(i2)) is true
4547    *  and i2 is an iterator in [__first2,__last2), or @p __last1 if no
4548    *  such iterator exists.
4549    *
4550
4551    *  Searches the range @p [__first1,__last1) for an element that is
4552    *  equal to some element in the range [__first2,__last2).  If
4553    *  found, returns an iterator in the range [__first1,__last1),
4554    *  otherwise returns @p __last1.
4555   */
4556   template<typename _InputIterator, typename _ForwardIterator,
4557            typename _BinaryPredicate>
4558     _InputIterator
4559     find_first_of(_InputIterator __first1, _InputIterator __last1,
4560                   _ForwardIterator __first2, _ForwardIterator __last2,
4561                   _BinaryPredicate __comp)
4562     {
4563       // concept requirements
4564       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
4565       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
4566       __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
4567             typename iterator_traits<_InputIterator>::value_type,
4568             typename iterator_traits<_ForwardIterator>::value_type>)
4569       __glibcxx_requires_valid_range(__first1, __last1);
4570       __glibcxx_requires_valid_range(__first2, __last2);
4571
4572       for (; __first1 != __last1; ++__first1)
4573         for (_ForwardIterator __iter = __first2; __iter != __last2; ++__iter)
4574           if (__comp(*__first1, *__iter))
4575             return __first1;
4576       return __last1;
4577     }
4578
4579   /**
4580    *  @brief Find two adjacent values in a sequence that are equal.
4581    *  @ingroup non_mutating_algorithms
4582    *  @param  __first  A forward iterator.
4583    *  @param  __last   A forward iterator.
4584    *  @return   The first iterator @c i such that @c i and @c i+1 are both
4585    *  valid iterators in @p [__first,__last) and such that @c *i == @c *(i+1),
4586    *  or @p __last if no such iterator exists.
4587   */
4588   template<typename _ForwardIterator>
4589     _ForwardIterator
4590     adjacent_find(_ForwardIterator __first, _ForwardIterator __last)
4591     {
4592       // concept requirements
4593       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
4594       __glibcxx_function_requires(_EqualityComparableConcept<
4595             typename iterator_traits<_ForwardIterator>::value_type>)
4596       __glibcxx_requires_valid_range(__first, __last);
4597       if (__first == __last)
4598         return __last;
4599       _ForwardIterator __next = __first;
4600       while(++__next != __last)
4601         {
4602           if (*__first == *__next)
4603             return __first;
4604           __first = __next;
4605         }
4606       return __last;
4607     }
4608
4609   /**
4610    *  @brief Find two adjacent values in a sequence using a predicate.
4611    *  @ingroup non_mutating_algorithms
4612    *  @param  __first         A forward iterator.
4613    *  @param  __last          A forward iterator.
4614    *  @param  __binary_pred   A binary predicate.
4615    *  @return   The first iterator @c i such that @c i and @c i+1 are both
4616    *  valid iterators in @p [__first,__last) and such that
4617    *  @p __binary_pred(*i,*(i+1)) is true, or @p __last if no such iterator
4618    *  exists.
4619   */
4620   template<typename _ForwardIterator, typename _BinaryPredicate>
4621     _ForwardIterator
4622     adjacent_find(_ForwardIterator __first, _ForwardIterator __last,
4623                   _BinaryPredicate __binary_pred)
4624     {
4625       // concept requirements
4626       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
4627       __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
4628             typename iterator_traits<_ForwardIterator>::value_type,
4629             typename iterator_traits<_ForwardIterator>::value_type>)
4630       __glibcxx_requires_valid_range(__first, __last);
4631       if (__first == __last)
4632         return __last;
4633       _ForwardIterator __next = __first;
4634       while(++__next != __last)
4635         {
4636           if (__binary_pred(*__first, *__next))
4637             return __first;
4638           __first = __next;
4639         }
4640       return __last;
4641     }
4642
4643   /**
4644    *  @brief Count the number of copies of a value in a sequence.
4645    *  @ingroup non_mutating_algorithms
4646    *  @param  __first  An input iterator.
4647    *  @param  __last   An input iterator.
4648    *  @param  __value  The value to be counted.
4649    *  @return   The number of iterators @c i in the range @p [__first,__last)
4650    *  for which @c *i == @p __value
4651   */
4652   template<typename _InputIterator, typename _Tp>
4653     typename iterator_traits<_InputIterator>::difference_type
4654     count(_InputIterator __first, _InputIterator __last, const _Tp& __value)
4655     {
4656       // concept requirements
4657       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
4658       __glibcxx_function_requires(_EqualOpConcept<
4659         typename iterator_traits<_InputIterator>::value_type, _Tp>)
4660       __glibcxx_requires_valid_range(__first, __last);
4661       typename iterator_traits<_InputIterator>::difference_type __n = 0;
4662       for (; __first != __last; ++__first)
4663         if (*__first == __value)
4664           ++__n;
4665       return __n;
4666     }
4667
4668   /**
4669    *  @brief Count the elements of a sequence for which a predicate is true.
4670    *  @ingroup non_mutating_algorithms
4671    *  @param  __first  An input iterator.
4672    *  @param  __last   An input iterator.
4673    *  @param  __pred   A predicate.
4674    *  @return   The number of iterators @c i in the range @p [__first,__last)
4675    *  for which @p __pred(*i) is true.
4676   */
4677   template<typename _InputIterator, typename _Predicate>
4678     typename iterator_traits<_InputIterator>::difference_type
4679     count_if(_InputIterator __first, _InputIterator __last, _Predicate __pred)
4680     {
4681       // concept requirements
4682       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
4683       __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
4684             typename iterator_traits<_InputIterator>::value_type>)
4685       __glibcxx_requires_valid_range(__first, __last);
4686       typename iterator_traits<_InputIterator>::difference_type __n = 0;
4687       for (; __first != __last; ++__first)
4688         if (__pred(*__first))
4689           ++__n;
4690       return __n;
4691     }
4692
4693   /**
4694    *  @brief Search a sequence for a matching sub-sequence.
4695    *  @ingroup non_mutating_algorithms
4696    *  @param  __first1  A forward iterator.
4697    *  @param  __last1   A forward iterator.
4698    *  @param  __first2  A forward iterator.
4699    *  @param  __last2   A forward iterator.
4700    *  @return The first iterator @c i in the range @p
4701    *  [__first1,__last1-(__last2-__first2)) such that @c *(i+N) == @p
4702    *  *(__first2+N) for each @c N in the range @p
4703    *  [0,__last2-__first2), or @p __last1 if no such iterator exists.
4704    *
4705    *  Searches the range @p [__first1,__last1) for a sub-sequence that
4706    *  compares equal value-by-value with the sequence given by @p
4707    *  [__first2,__last2) and returns an iterator to the first element
4708    *  of the sub-sequence, or @p __last1 if the sub-sequence is not
4709    *  found.
4710    *
4711    *  Because the sub-sequence must lie completely within the range @p
4712    *  [__first1,__last1) it must start at a position less than @p
4713    *  __last1-(__last2-__first2) where @p __last2-__first2 is the
4714    *  length of the sub-sequence.
4715    *
4716    *  This means that the returned iterator @c i will be in the range
4717    *  @p [__first1,__last1-(__last2-__first2))
4718   */
4719   template<typename _ForwardIterator1, typename _ForwardIterator2>
4720     _ForwardIterator1
4721     search(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
4722            _ForwardIterator2 __first2, _ForwardIterator2 __last2)
4723     {
4724       // concept requirements
4725       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator1>)
4726       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator2>)
4727       __glibcxx_function_requires(_EqualOpConcept<
4728             typename iterator_traits<_ForwardIterator1>::value_type,
4729             typename iterator_traits<_ForwardIterator2>::value_type>)
4730       __glibcxx_requires_valid_range(__first1, __last1);
4731       __glibcxx_requires_valid_range(__first2, __last2);
4732
4733       // Test for empty ranges
4734       if (__first1 == __last1 || __first2 == __last2)
4735         return __first1;
4736
4737       // Test for a pattern of length 1.
4738       _ForwardIterator2 __p1(__first2);
4739       if (++__p1 == __last2)
4740         return _GLIBCXX_STD_A::find(__first1, __last1, *__first2);
4741
4742       // General case.
4743       _ForwardIterator2 __p;
4744       _ForwardIterator1 __current = __first1;
4745
4746       for (;;)
4747         {
4748           __first1 = _GLIBCXX_STD_A::find(__first1, __last1, *__first2);
4749           if (__first1 == __last1)
4750             return __last1;
4751
4752           __p = __p1;
4753           __current = __first1;
4754           if (++__current == __last1)
4755             return __last1;
4756
4757           while (*__current == *__p)
4758             {
4759               if (++__p == __last2)
4760                 return __first1;
4761               if (++__current == __last1)
4762                 return __last1;
4763             }
4764           ++__first1;
4765         }
4766       return __first1;
4767     }
4768
4769   /**
4770    *  @brief Search a sequence for a matching sub-sequence using a predicate.
4771    *  @ingroup non_mutating_algorithms
4772    *  @param  __first1     A forward iterator.
4773    *  @param  __last1      A forward iterator.
4774    *  @param  __first2     A forward iterator.
4775    *  @param  __last2      A forward iterator.
4776    *  @param  __predicate  A binary predicate.
4777    *  @return   The first iterator @c i in the range
4778    *  @p [__first1,__last1-(__last2-__first2)) such that
4779    *  @p __predicate(*(i+N),*(__first2+N)) is true for each @c N in the range
4780    *  @p [0,__last2-__first2), or @p __last1 if no such iterator exists.
4781    *
4782    *  Searches the range @p [__first1,__last1) for a sub-sequence that
4783    *  compares equal value-by-value with the sequence given by @p
4784    *  [__first2,__last2), using @p __predicate to determine equality,
4785    *  and returns an iterator to the first element of the
4786    *  sub-sequence, or @p __last1 if no such iterator exists.
4787    *
4788    *  @see search(_ForwardIter1, _ForwardIter1, _ForwardIter2, _ForwardIter2)
4789   */
4790   template<typename _ForwardIterator1, typename _ForwardIterator2,
4791            typename _BinaryPredicate>
4792     _ForwardIterator1
4793     search(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
4794            _ForwardIterator2 __first2, _ForwardIterator2 __last2,
4795            _BinaryPredicate  __predicate)
4796     {
4797       // concept requirements
4798       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator1>)
4799       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator2>)
4800       __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
4801             typename iterator_traits<_ForwardIterator1>::value_type,
4802             typename iterator_traits<_ForwardIterator2>::value_type>)
4803       __glibcxx_requires_valid_range(__first1, __last1);
4804       __glibcxx_requires_valid_range(__first2, __last2);
4805
4806       // Test for empty ranges
4807       if (__first1 == __last1 || __first2 == __last2)
4808         return __first1;
4809
4810       // Test for a pattern of length 1.
4811       _ForwardIterator2 __p1(__first2);
4812       if (++__p1 == __last2)
4813         {
4814           while (__first1 != __last1
4815                  && !bool(__predicate(*__first1, *__first2)))
4816             ++__first1;
4817           return __first1;
4818         }
4819
4820       // General case.
4821       _ForwardIterator2 __p;
4822       _ForwardIterator1 __current = __first1;
4823
4824       for (;;)
4825         {
4826           while (__first1 != __last1
4827                  && !bool(__predicate(*__first1, *__first2)))
4828             ++__first1;
4829           if (__first1 == __last1)
4830             return __last1;
4831
4832           __p = __p1;
4833           __current = __first1;
4834           if (++__current == __last1)
4835             return __last1;
4836
4837           while (__predicate(*__current, *__p))
4838             {
4839               if (++__p == __last2)
4840                 return __first1;
4841               if (++__current == __last1)
4842                 return __last1;
4843             }
4844           ++__first1;
4845         }
4846       return __first1;
4847     }
4848
4849
4850   /**
4851    *  @brief Search a sequence for a number of consecutive values.
4852    *  @ingroup non_mutating_algorithms
4853    *  @param  __first  A forward iterator.
4854    *  @param  __last   A forward iterator.
4855    *  @param  __count  The number of consecutive values.
4856    *  @param  __val    The value to find.
4857    *  @return The first iterator @c i in the range @p
4858    *  [__first,__last-__count) such that @c *(i+N) == @p __val for
4859    *  each @c N in the range @p [0,__count), or @p __last if no such
4860    *  iterator exists.
4861    *
4862    *  Searches the range @p [__first,__last) for @p count consecutive elements
4863    *  equal to @p __val.
4864   */
4865   template<typename _ForwardIterator, typename _Integer, typename _Tp>
4866     _ForwardIterator
4867     search_n(_ForwardIterator __first, _ForwardIterator __last,
4868              _Integer __count, const _Tp& __val)
4869     {
4870       // concept requirements
4871       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
4872       __glibcxx_function_requires(_EqualOpConcept<
4873         typename iterator_traits<_ForwardIterator>::value_type, _Tp>)
4874       __glibcxx_requires_valid_range(__first, __last);
4875
4876       if (__count <= 0)
4877         return __first;
4878       if (__count == 1)
4879         return _GLIBCXX_STD_A::find(__first, __last, __val);
4880       return std::__search_n(__first, __last, __count, __val,
4881                              std::__iterator_category(__first));
4882     }
4883
4884
4885   /**
4886    *  @brief Search a sequence for a number of consecutive values using a
4887    *         predicate.
4888    *  @ingroup non_mutating_algorithms
4889    *  @param  __first        A forward iterator.
4890    *  @param  __last         A forward iterator.
4891    *  @param  __count        The number of consecutive values.
4892    *  @param  __val          The value to find.
4893    *  @param  __binary_pred  A binary predicate.
4894    *  @return The first iterator @c i in the range @p
4895    *  [__first,__last-__count) such that @p
4896    *  __binary_pred(*(i+N),__val) is true for each @c N in the range
4897    *  @p [0,__count), or @p __last if no such iterator exists.
4898    *
4899    *  Searches the range @p [__first,__last) for @p __count
4900    *  consecutive elements for which the predicate returns true.
4901   */
4902   template<typename _ForwardIterator, typename _Integer, typename _Tp,
4903            typename _BinaryPredicate>
4904     _ForwardIterator
4905     search_n(_ForwardIterator __first, _ForwardIterator __last,
4906              _Integer __count, const _Tp& __val,
4907              _BinaryPredicate __binary_pred)
4908     {
4909       // concept requirements
4910       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
4911       __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
4912             typename iterator_traits<_ForwardIterator>::value_type, _Tp>)
4913       __glibcxx_requires_valid_range(__first, __last);
4914
4915       if (__count <= 0)
4916         return __first;
4917       if (__count == 1)
4918         {
4919           while (__first != __last && !bool(__binary_pred(*__first, __val)))
4920             ++__first;
4921           return __first;
4922         }
4923       return std::__search_n(__first, __last, __count, __val, __binary_pred,
4924                              std::__iterator_category(__first));
4925     }
4926
4927
4928   /**
4929    *  @brief Perform an operation on a sequence.
4930    *  @ingroup mutating_algorithms
4931    *  @param  __first     An input iterator.
4932    *  @param  __last      An input iterator.
4933    *  @param  __result    An output iterator.
4934    *  @param  __unary_op  A unary operator.
4935    *  @return   An output iterator equal to @p __result+(__last-__first).
4936    *
4937    *  Applies the operator to each element in the input range and assigns
4938    *  the results to successive elements of the output sequence.
4939    *  Evaluates @p *(__result+N)=unary_op(*(__first+N)) for each @c N in the
4940    *  range @p [0,__last-__first).
4941    *
4942    *  @p unary_op must not alter its argument.
4943   */
4944   template<typename _InputIterator, typename _OutputIterator,
4945            typename _UnaryOperation>
4946     _OutputIterator
4947     transform(_InputIterator __first, _InputIterator __last,
4948               _OutputIterator __result, _UnaryOperation __unary_op)
4949     {
4950       // concept requirements
4951       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
4952       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
4953             // "the type returned by a _UnaryOperation"
4954             __typeof__(__unary_op(*__first))>)
4955       __glibcxx_requires_valid_range(__first, __last);
4956
4957       for (; __first != __last; ++__first, ++__result)
4958         *__result = __unary_op(*__first);
4959       return __result;
4960     }
4961
4962   /**
4963    *  @brief Perform an operation on corresponding elements of two sequences.
4964    *  @ingroup mutating_algorithms
4965    *  @param  __first1     An input iterator.
4966    *  @param  __last1      An input iterator.
4967    *  @param  __first2     An input iterator.
4968    *  @param  __result     An output iterator.
4969    *  @param  __binary_op  A binary operator.
4970    *  @return   An output iterator equal to @p result+(last-first).
4971    *
4972    *  Applies the operator to the corresponding elements in the two
4973    *  input ranges and assigns the results to successive elements of the
4974    *  output sequence.
4975    *  Evaluates @p
4976    *  *(__result+N)=__binary_op(*(__first1+N),*(__first2+N)) for each
4977    *  @c N in the range @p [0,__last1-__first1).
4978    *
4979    *  @p binary_op must not alter either of its arguments.
4980   */
4981   template<typename _InputIterator1, typename _InputIterator2,
4982            typename _OutputIterator, typename _BinaryOperation>
4983     _OutputIterator
4984     transform(_InputIterator1 __first1, _InputIterator1 __last1,
4985               _InputIterator2 __first2, _OutputIterator __result,
4986               _BinaryOperation __binary_op)
4987     {
4988       // concept requirements
4989       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
4990       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
4991       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
4992             // "the type returned by a _BinaryOperation"
4993             __typeof__(__binary_op(*__first1,*__first2))>)
4994       __glibcxx_requires_valid_range(__first1, __last1);
4995
4996       for (; __first1 != __last1; ++__first1, ++__first2, ++__result)
4997         *__result = __binary_op(*__first1, *__first2);
4998       return __result;
4999     }
5000
5001   /**
5002    *  @brief Replace each occurrence of one value in a sequence with another
5003    *         value.
5004    *  @ingroup mutating_algorithms
5005    *  @param  __first      A forward iterator.
5006    *  @param  __last       A forward iterator.
5007    *  @param  __old_value  The value to be replaced.
5008    *  @param  __new_value  The replacement value.
5009    *  @return   replace() returns no value.
5010    *
5011    *  For each iterator @c i in the range @p [__first,__last) if @c *i ==
5012    *  @p __old_value then the assignment @c *i = @p __new_value is performed.
5013   */
5014   template<typename _ForwardIterator, typename _Tp>
5015     void
5016     replace(_ForwardIterator __first, _ForwardIterator __last,
5017             const _Tp& __old_value, const _Tp& __new_value)
5018     {
5019       // concept requirements
5020       __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
5021                                   _ForwardIterator>)
5022       __glibcxx_function_requires(_EqualOpConcept<
5023             typename iterator_traits<_ForwardIterator>::value_type, _Tp>)
5024       __glibcxx_function_requires(_ConvertibleConcept<_Tp,
5025             typename iterator_traits<_ForwardIterator>::value_type>)
5026       __glibcxx_requires_valid_range(__first, __last);
5027
5028       for (; __first != __last; ++__first)
5029         if (*__first == __old_value)
5030           *__first = __new_value;
5031     }
5032
5033   /**
5034    *  @brief Replace each value in a sequence for which a predicate returns
5035    *         true with another value.
5036    *  @ingroup mutating_algorithms
5037    *  @param  __first      A forward iterator.
5038    *  @param  __last       A forward iterator.
5039    *  @param  __pred       A predicate.
5040    *  @param  __new_value  The replacement value.
5041    *  @return   replace_if() returns no value.
5042    *
5043    *  For each iterator @c i in the range @p [__first,__last) if @p __pred(*i)
5044    *  is true then the assignment @c *i = @p __new_value is performed.
5045   */
5046   template<typename _ForwardIterator, typename _Predicate, typename _Tp>
5047     void
5048     replace_if(_ForwardIterator __first, _ForwardIterator __last,
5049                _Predicate __pred, const _Tp& __new_value)
5050     {
5051       // concept requirements
5052       __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
5053                                   _ForwardIterator>)
5054       __glibcxx_function_requires(_ConvertibleConcept<_Tp,
5055             typename iterator_traits<_ForwardIterator>::value_type>)
5056       __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
5057             typename iterator_traits<_ForwardIterator>::value_type>)
5058       __glibcxx_requires_valid_range(__first, __last);
5059
5060       for (; __first != __last; ++__first)
5061         if (__pred(*__first))
5062           *__first = __new_value;
5063     }
5064
5065   /**
5066    *  @brief Assign the result of a function object to each value in a
5067    *         sequence.
5068    *  @ingroup mutating_algorithms
5069    *  @param  __first  A forward iterator.
5070    *  @param  __last   A forward iterator.
5071    *  @param  __gen    A function object taking no arguments and returning
5072    *                 std::iterator_traits<_ForwardIterator>::value_type
5073    *  @return   generate() returns no value.
5074    *
5075    *  Performs the assignment @c *i = @p __gen() for each @c i in the range
5076    *  @p [__first,__last).
5077   */
5078   template<typename _ForwardIterator, typename _Generator>
5079     void
5080     generate(_ForwardIterator __first, _ForwardIterator __last,
5081              _Generator __gen)
5082     {
5083       // concept requirements
5084       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
5085       __glibcxx_function_requires(_GeneratorConcept<_Generator,
5086             typename iterator_traits<_ForwardIterator>::value_type>)
5087       __glibcxx_requires_valid_range(__first, __last);
5088
5089       for (; __first != __last; ++__first)
5090         *__first = __gen();
5091     }
5092
5093   /**
5094    *  @brief Assign the result of a function object to each value in a
5095    *         sequence.
5096    *  @ingroup mutating_algorithms
5097    *  @param  __first  A forward iterator.
5098    *  @param  __n      The length of the sequence.
5099    *  @param  __gen    A function object taking no arguments and returning
5100    *                 std::iterator_traits<_ForwardIterator>::value_type
5101    *  @return   The end of the sequence, @p __first+__n
5102    *
5103    *  Performs the assignment @c *i = @p __gen() for each @c i in the range
5104    *  @p [__first,__first+__n).
5105    *
5106    *  _GLIBCXX_RESOLVE_LIB_DEFECTS
5107    *  DR 865. More algorithms that throw away information
5108   */
5109   template<typename _OutputIterator, typename _Size, typename _Generator>
5110     _OutputIterator
5111     generate_n(_OutputIterator __first, _Size __n, _Generator __gen)
5112     {
5113       // concept requirements
5114       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5115             // "the type returned by a _Generator"
5116             __typeof__(__gen())>)
5117
5118       for (__decltype(__n + 0) __niter = __n;
5119            __niter > 0; --__niter, ++__first)
5120         *__first = __gen();
5121       return __first;
5122     }
5123
5124
5125   /**
5126    *  @brief Copy a sequence, removing consecutive duplicate values.
5127    *  @ingroup mutating_algorithms
5128    *  @param  __first   An input iterator.
5129    *  @param  __last    An input iterator.
5130    *  @param  __result  An output iterator.
5131    *  @return   An iterator designating the end of the resulting sequence.
5132    *
5133    *  Copies each element in the range @p [__first,__last) to the range
5134    *  beginning at @p __result, except that only the first element is copied
5135    *  from groups of consecutive elements that compare equal.
5136    *  unique_copy() is stable, so the relative order of elements that are
5137    *  copied is unchanged.
5138    *
5139    *  _GLIBCXX_RESOLVE_LIB_DEFECTS
5140    *  DR 241. Does unique_copy() require CopyConstructible and Assignable?
5141    *
5142    *  _GLIBCXX_RESOLVE_LIB_DEFECTS
5143    *  DR 538. 241 again: Does unique_copy() require CopyConstructible and
5144    *  Assignable?
5145   */
5146   template<typename _InputIterator, typename _OutputIterator>
5147     inline _OutputIterator
5148     unique_copy(_InputIterator __first, _InputIterator __last,
5149                 _OutputIterator __result)
5150     {
5151       // concept requirements
5152       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
5153       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5154             typename iterator_traits<_InputIterator>::value_type>)
5155       __glibcxx_function_requires(_EqualityComparableConcept<
5156             typename iterator_traits<_InputIterator>::value_type>)
5157       __glibcxx_requires_valid_range(__first, __last);
5158
5159       if (__first == __last)
5160         return __result;
5161       return std::__unique_copy(__first, __last, __result,
5162                                 std::__iterator_category(__first),
5163                                 std::__iterator_category(__result));
5164     }
5165
5166   /**
5167    *  @brief Copy a sequence, removing consecutive values using a predicate.
5168    *  @ingroup mutating_algorithms
5169    *  @param  __first        An input iterator.
5170    *  @param  __last         An input iterator.
5171    *  @param  __result       An output iterator.
5172    *  @param  __binary_pred  A binary predicate.
5173    *  @return   An iterator designating the end of the resulting sequence.
5174    *
5175    *  Copies each element in the range @p [__first,__last) to the range
5176    *  beginning at @p __result, except that only the first element is copied
5177    *  from groups of consecutive elements for which @p __binary_pred returns
5178    *  true.
5179    *  unique_copy() is stable, so the relative order of elements that are
5180    *  copied is unchanged.
5181    *
5182    *  _GLIBCXX_RESOLVE_LIB_DEFECTS
5183    *  DR 241. Does unique_copy() require CopyConstructible and Assignable?
5184   */
5185   template<typename _InputIterator, typename _OutputIterator,
5186            typename _BinaryPredicate>
5187     inline _OutputIterator
5188     unique_copy(_InputIterator __first, _InputIterator __last,
5189                 _OutputIterator __result,
5190                 _BinaryPredicate __binary_pred)
5191     {
5192       // concept requirements -- predicates checked later
5193       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
5194       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5195             typename iterator_traits<_InputIterator>::value_type>)
5196       __glibcxx_requires_valid_range(__first, __last);
5197
5198       if (__first == __last)
5199         return __result;
5200       return std::__unique_copy(__first, __last, __result, __binary_pred,
5201                                 std::__iterator_category(__first),
5202                                 std::__iterator_category(__result));
5203     }
5204
5205
5206   /**
5207    *  @brief Randomly shuffle the elements of a sequence.
5208    *  @ingroup mutating_algorithms
5209    *  @param  __first   A forward iterator.
5210    *  @param  __last    A forward iterator.
5211    *  @return  Nothing.
5212    *
5213    *  Reorder the elements in the range @p [__first,__last) using a random
5214    *  distribution, so that every possible ordering of the sequence is
5215    *  equally likely.
5216   */
5217   template<typename _RandomAccessIterator>
5218     inline void
5219     random_shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last)
5220     {
5221       // concept requirements
5222       __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
5223             _RandomAccessIterator>)
5224       __glibcxx_requires_valid_range(__first, __last);
5225
5226       if (__first != __last)
5227         for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i)
5228           std::iter_swap(__i, __first + (std::rand() % ((__i - __first) + 1)));
5229     }
5230
5231   /**
5232    *  @brief Shuffle the elements of a sequence using a random number
5233    *         generator.
5234    *  @ingroup mutating_algorithms
5235    *  @param  __first   A forward iterator.
5236    *  @param  __last    A forward iterator.
5237    *  @param  __rand    The RNG functor or function.
5238    *  @return  Nothing.
5239    *
5240    *  Reorders the elements in the range @p [__first,__last) using @p __rand to
5241    *  provide a random distribution. Calling @p __rand(N) for a positive
5242    *  integer @p N should return a randomly chosen integer from the
5243    *  range [0,N).
5244   */
5245   template<typename _RandomAccessIterator, typename _RandomNumberGenerator>
5246     void
5247     random_shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last,
5248 #ifdef __GXX_EXPERIMENTAL_CXX0X__
5249                    _RandomNumberGenerator&& __rand)
5250 #else
5251                    _RandomNumberGenerator& __rand)
5252 #endif
5253     {
5254       // concept requirements
5255       __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
5256             _RandomAccessIterator>)
5257       __glibcxx_requires_valid_range(__first, __last);
5258
5259       if (__first == __last)
5260         return;
5261       for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i)
5262         std::iter_swap(__i, __first + __rand((__i - __first) + 1));
5263     }
5264
5265
5266   /**
5267    *  @brief Move elements for which a predicate is true to the beginning
5268    *         of a sequence.
5269    *  @ingroup mutating_algorithms
5270    *  @param  __first   A forward iterator.
5271    *  @param  __last    A forward iterator.
5272    *  @param  __pred    A predicate functor.
5273    *  @return  An iterator @p middle such that @p __pred(i) is true for each
5274    *  iterator @p i in the range @p [__first,middle) and false for each @p i
5275    *  in the range @p [middle,__last).
5276    *
5277    *  @p __pred must not modify its operand. @p partition() does not preserve
5278    *  the relative ordering of elements in each group, use
5279    *  @p stable_partition() if this is needed.
5280   */
5281   template<typename _ForwardIterator, typename _Predicate>
5282     inline _ForwardIterator
5283     partition(_ForwardIterator __first, _ForwardIterator __last,
5284               _Predicate   __pred)
5285     {
5286       // concept requirements
5287       __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
5288                                   _ForwardIterator>)
5289       __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
5290             typename iterator_traits<_ForwardIterator>::value_type>)
5291       __glibcxx_requires_valid_range(__first, __last);
5292
5293       return std::__partition(__first, __last, __pred,
5294                               std::__iterator_category(__first));
5295     }
5296
5297
5298
5299   /**
5300    *  @brief Sort the smallest elements of a sequence.
5301    *  @ingroup sorting_algorithms
5302    *  @param  __first   An iterator.
5303    *  @param  __middle  Another iterator.
5304    *  @param  __last    Another iterator.
5305    *  @return  Nothing.
5306    *
5307    *  Sorts the smallest @p (__middle-__first) elements in the range
5308    *  @p [first,last) and moves them to the range @p [__first,__middle). The
5309    *  order of the remaining elements in the range @p [__middle,__last) is
5310    *  undefined.
5311    *  After the sort if @e i and @e j are iterators in the range
5312    *  @p [__first,__middle) such that i precedes j and @e k is an iterator in
5313    *  the range @p [__middle,__last) then *j<*i and *k<*i are both false.
5314   */
5315   template<typename _RandomAccessIterator>
5316     inline void
5317     partial_sort(_RandomAccessIterator __first,
5318                  _RandomAccessIterator __middle,
5319                  _RandomAccessIterator __last)
5320     {
5321       typedef typename iterator_traits<_RandomAccessIterator>::value_type
5322         _ValueType;
5323
5324       // concept requirements
5325       __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
5326             _RandomAccessIterator>)
5327       __glibcxx_function_requires(_LessThanComparableConcept<_ValueType>)
5328       __glibcxx_requires_valid_range(__first, __middle);
5329       __glibcxx_requires_valid_range(__middle, __last);
5330
5331       std::__heap_select(__first, __middle, __last);
5332       std::sort_heap(__first, __middle);
5333     }
5334
5335   /**
5336    *  @brief Sort the smallest elements of a sequence using a predicate
5337    *         for comparison.
5338    *  @ingroup sorting_algorithms
5339    *  @param  __first   An iterator.
5340    *  @param  __middle  Another iterator.
5341    *  @param  __last    Another iterator.
5342    *  @param  __comp    A comparison functor.
5343    *  @return  Nothing.
5344    *
5345    *  Sorts the smallest @p (__middle-__first) elements in the range
5346    *  @p [__first,__last) and moves them to the range @p [__first,__middle). The
5347    *  order of the remaining elements in the range @p [__middle,__last) is
5348    *  undefined.
5349    *  After the sort if @e i and @e j are iterators in the range
5350    *  @p [__first,__middle) such that i precedes j and @e k is an iterator in
5351    *  the range @p [__middle,__last) then @p *__comp(j,*i) and @p __comp(*k,*i)
5352    *  are both false.
5353   */
5354   template<typename _RandomAccessIterator, typename _Compare>
5355     inline void
5356     partial_sort(_RandomAccessIterator __first,
5357                  _RandomAccessIterator __middle,
5358                  _RandomAccessIterator __last,
5359                  _Compare __comp)
5360     {
5361       typedef typename iterator_traits<_RandomAccessIterator>::value_type
5362         _ValueType;
5363
5364       // concept requirements
5365       __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
5366             _RandomAccessIterator>)
5367       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5368                                   _ValueType, _ValueType>)
5369       __glibcxx_requires_valid_range(__first, __middle);
5370       __glibcxx_requires_valid_range(__middle, __last);
5371
5372       std::__heap_select(__first, __middle, __last, __comp);
5373       std::sort_heap(__first, __middle, __comp);
5374     }
5375
5376   /**
5377    *  @brief Sort a sequence just enough to find a particular position.
5378    *  @ingroup sorting_algorithms
5379    *  @param  __first   An iterator.
5380    *  @param  __nth     Another iterator.
5381    *  @param  __last    Another iterator.
5382    *  @return  Nothing.
5383    *
5384    *  Rearranges the elements in the range @p [__first,__last) so that @p *__nth
5385    *  is the same element that would have been in that position had the
5386    *  whole sequence been sorted. The elements either side of @p *__nth are
5387    *  not completely sorted, but for any iterator @e i in the range
5388    *  @p [__first,__nth) and any iterator @e j in the range @p [__nth,__last) it
5389    *  holds that *j < *i is false.
5390   */
5391   template<typename _RandomAccessIterator>
5392     inline void
5393     nth_element(_RandomAccessIterator __first, _RandomAccessIterator __nth,
5394                 _RandomAccessIterator __last)
5395     {
5396       typedef typename iterator_traits<_RandomAccessIterator>::value_type
5397         _ValueType;
5398
5399       // concept requirements
5400       __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
5401                                   _RandomAccessIterator>)
5402       __glibcxx_function_requires(_LessThanComparableConcept<_ValueType>)
5403       __glibcxx_requires_valid_range(__first, __nth);
5404       __glibcxx_requires_valid_range(__nth, __last);
5405
5406       if (__first == __last || __nth == __last)
5407         return;
5408
5409       std::__introselect(__first, __nth, __last,
5410                          std::__lg(__last - __first) * 2);
5411     }
5412
5413   /**
5414    *  @brief Sort a sequence just enough to find a particular position
5415    *         using a predicate for comparison.
5416    *  @ingroup sorting_algorithms
5417    *  @param  __first   An iterator.
5418    *  @param  __nth     Another iterator.
5419    *  @param  __last    Another iterator.
5420    *  @param  __comp    A comparison functor.
5421    *  @return  Nothing.
5422    *
5423    *  Rearranges the elements in the range @p [__first,__last) so that @p *__nth
5424    *  is the same element that would have been in that position had the
5425    *  whole sequence been sorted. The elements either side of @p *__nth are
5426    *  not completely sorted, but for any iterator @e i in the range
5427    *  @p [__first,__nth) and any iterator @e j in the range @p [__nth,__last) it
5428    *  holds that @p __comp(*j,*i) is false.
5429   */
5430   template<typename _RandomAccessIterator, typename _Compare>
5431     inline void
5432     nth_element(_RandomAccessIterator __first, _RandomAccessIterator __nth,
5433                 _RandomAccessIterator __last, _Compare __comp)
5434     {
5435       typedef typename iterator_traits<_RandomAccessIterator>::value_type
5436         _ValueType;
5437
5438       // concept requirements
5439       __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
5440                                   _RandomAccessIterator>)
5441       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5442                                   _ValueType, _ValueType>)
5443       __glibcxx_requires_valid_range(__first, __nth);
5444       __glibcxx_requires_valid_range(__nth, __last);
5445
5446       if (__first == __last || __nth == __last)
5447         return;
5448
5449       std::__introselect(__first, __nth, __last,
5450                          std::__lg(__last - __first) * 2, __comp);
5451     }
5452
5453
5454   /**
5455    *  @brief Sort the elements of a sequence.
5456    *  @ingroup sorting_algorithms
5457    *  @param  __first   An iterator.
5458    *  @param  __last    Another iterator.
5459    *  @return  Nothing.
5460    *
5461    *  Sorts the elements in the range @p [__first,__last) in ascending order,
5462    *  such that for each iterator @e i in the range @p [__first,__last-1),
5463    *  *(i+1)<*i is false.
5464    *
5465    *  The relative ordering of equivalent elements is not preserved, use
5466    *  @p stable_sort() if this is needed.
5467   */
5468   template<typename _RandomAccessIterator>
5469     inline void
5470     sort(_RandomAccessIterator __first, _RandomAccessIterator __last)
5471     {
5472       typedef typename iterator_traits<_RandomAccessIterator>::value_type
5473         _ValueType;
5474
5475       // concept requirements
5476       __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
5477             _RandomAccessIterator>)
5478       __glibcxx_function_requires(_LessThanComparableConcept<_ValueType>)
5479       __glibcxx_requires_valid_range(__first, __last);
5480
5481       if (__first != __last)
5482         {
5483           std::__introsort_loop(__first, __last,
5484                                 std::__lg(__last - __first) * 2);
5485           std::__final_insertion_sort(__first, __last);
5486         }
5487     }
5488
5489   /**
5490    *  @brief Sort the elements of a sequence using a predicate for comparison.
5491    *  @ingroup sorting_algorithms
5492    *  @param  __first   An iterator.
5493    *  @param  __last    Another iterator.
5494    *  @param  __comp    A comparison functor.
5495    *  @return  Nothing.
5496    *
5497    *  Sorts the elements in the range @p [__first,__last) in ascending order,
5498    *  such that @p __comp(*(i+1),*i) is false for every iterator @e i in the
5499    *  range @p [__first,__last-1).
5500    *
5501    *  The relative ordering of equivalent elements is not preserved, use
5502    *  @p stable_sort() if this is needed.
5503   */
5504   template<typename _RandomAccessIterator, typename _Compare>
5505     inline void
5506     sort(_RandomAccessIterator __first, _RandomAccessIterator __last,
5507          _Compare __comp)
5508     {
5509       typedef typename iterator_traits<_RandomAccessIterator>::value_type
5510         _ValueType;
5511
5512       // concept requirements
5513       __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
5514             _RandomAccessIterator>)
5515       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, _ValueType,
5516                                   _ValueType>)
5517       __glibcxx_requires_valid_range(__first, __last);
5518
5519       if (__first != __last)
5520         {
5521           std::__introsort_loop(__first, __last,
5522                                 std::__lg(__last - __first) * 2, __comp);
5523           std::__final_insertion_sort(__first, __last, __comp);
5524         }
5525     }
5526
5527   /**
5528    *  @brief Merges two sorted ranges.
5529    *  @ingroup sorting_algorithms
5530    *  @param  __first1  An iterator.
5531    *  @param  __first2  Another iterator.
5532    *  @param  __last1   Another iterator.
5533    *  @param  __last2   Another iterator.
5534    *  @param  __result  An iterator pointing to the end of the merged range.
5535    *  @return         An iterator pointing to the first element <em>not less
5536    *                  than</em> @e val.
5537    *
5538    *  Merges the ranges @p [__first1,__last1) and @p [__first2,__last2) into
5539    *  the sorted range @p [__result, __result + (__last1-__first1) +
5540    *  (__last2-__first2)).  Both input ranges must be sorted, and the
5541    *  output range must not overlap with either of the input ranges.
5542    *  The sort is @e stable, that is, for equivalent elements in the
5543    *  two ranges, elements from the first range will always come
5544    *  before elements from the second.
5545   */
5546   template<typename _InputIterator1, typename _InputIterator2,
5547            typename _OutputIterator>
5548     _OutputIterator
5549     merge(_InputIterator1 __first1, _InputIterator1 __last1,
5550           _InputIterator2 __first2, _InputIterator2 __last2,
5551           _OutputIterator __result)
5552     {
5553       typedef typename iterator_traits<_InputIterator1>::value_type
5554         _ValueType1;
5555       typedef typename iterator_traits<_InputIterator2>::value_type
5556         _ValueType2;
5557
5558       // concept requirements
5559       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
5560       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
5561       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5562                                   _ValueType1>)
5563       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5564                                   _ValueType2>)
5565       __glibcxx_function_requires(_LessThanOpConcept<_ValueType2, _ValueType1>)
5566       __glibcxx_requires_sorted_set(__first1, __last1, __first2);
5567       __glibcxx_requires_sorted_set(__first2, __last2, __first1);
5568
5569       while (__first1 != __last1 && __first2 != __last2)
5570         {
5571           if (*__first2 < *__first1)
5572             {
5573               *__result = *__first2;
5574               ++__first2;
5575             }
5576           else
5577             {
5578               *__result = *__first1;
5579               ++__first1;
5580             }
5581           ++__result;
5582         }
5583       return std::copy(__first2, __last2, std::copy(__first1, __last1,
5584                                                     __result));
5585     }
5586
5587   /**
5588    *  @brief Merges two sorted ranges.
5589    *  @ingroup sorting_algorithms
5590    *  @param  __first1  An iterator.
5591    *  @param  __first2  Another iterator.
5592    *  @param  __last1   Another iterator.
5593    *  @param  __last2   Another iterator.
5594    *  @param  __result  An iterator pointing to the end of the merged range.
5595    *  @param  __comp    A functor to use for comparisons.
5596    *  @return         An iterator pointing to the first element "not less
5597    *                  than" @e val.
5598    *
5599    *  Merges the ranges @p [__first1,__last1) and @p [__first2,__last2) into
5600    *  the sorted range @p [__result, __result + (__last1-__first1) +
5601    *  (__last2-__first2)).  Both input ranges must be sorted, and the
5602    *  output range must not overlap with either of the input ranges.
5603    *  The sort is @e stable, that is, for equivalent elements in the
5604    *  two ranges, elements from the first range will always come
5605    *  before elements from the second.
5606    *
5607    *  The comparison function should have the same effects on ordering as
5608    *  the function used for the initial sort.
5609   */
5610   template<typename _InputIterator1, typename _InputIterator2,
5611            typename _OutputIterator, typename _Compare>
5612     _OutputIterator
5613     merge(_InputIterator1 __first1, _InputIterator1 __last1,
5614           _InputIterator2 __first2, _InputIterator2 __last2,
5615           _OutputIterator __result, _Compare __comp)
5616     {
5617       typedef typename iterator_traits<_InputIterator1>::value_type
5618         _ValueType1;
5619       typedef typename iterator_traits<_InputIterator2>::value_type
5620         _ValueType2;
5621
5622       // concept requirements
5623       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
5624       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
5625       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5626                                   _ValueType1>)
5627       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5628                                   _ValueType2>)
5629       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5630                                   _ValueType2, _ValueType1>)
5631       __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp);
5632       __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp);
5633
5634       while (__first1 != __last1 && __first2 != __last2)
5635         {
5636           if (__comp(*__first2, *__first1))
5637             {
5638               *__result = *__first2;
5639               ++__first2;
5640             }
5641           else
5642             {
5643               *__result = *__first1;
5644               ++__first1;
5645             }
5646           ++__result;
5647         }
5648       return std::copy(__first2, __last2, std::copy(__first1, __last1,
5649                                                     __result));
5650     }
5651
5652
5653   /**
5654    *  @brief Sort the elements of a sequence, preserving the relative order
5655    *         of equivalent elements.
5656    *  @ingroup sorting_algorithms
5657    *  @param  __first   An iterator.
5658    *  @param  __last    Another iterator.
5659    *  @return  Nothing.
5660    *
5661    *  Sorts the elements in the range @p [__first,__last) in ascending order,
5662    *  such that for each iterator @p i in the range @p [__first,__last-1),
5663    *  @p *(i+1)<*i is false.
5664    *
5665    *  The relative ordering of equivalent elements is preserved, so any two
5666    *  elements @p x and @p y in the range @p [__first,__last) such that
5667    *  @p x<y is false and @p y<x is false will have the same relative
5668    *  ordering after calling @p stable_sort().
5669   */
5670   template<typename _RandomAccessIterator>
5671     inline void
5672     stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last)
5673     {
5674       typedef typename iterator_traits<_RandomAccessIterator>::value_type
5675         _ValueType;
5676       typedef typename iterator_traits<_RandomAccessIterator>::difference_type
5677         _DistanceType;
5678
5679       // concept requirements
5680       __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
5681             _RandomAccessIterator>)
5682       __glibcxx_function_requires(_LessThanComparableConcept<_ValueType>)
5683       __glibcxx_requires_valid_range(__first, __last);
5684
5685       _Temporary_buffer<_RandomAccessIterator, _ValueType> __buf(__first,
5686                                                                  __last);
5687       if (__buf.begin() == 0)
5688         std::__inplace_stable_sort(__first, __last);
5689       else
5690         std::__stable_sort_adaptive(__first, __last, __buf.begin(),
5691                                     _DistanceType(__buf.size()));
5692     }
5693
5694   /**
5695    *  @brief Sort the elements of a sequence using a predicate for comparison,
5696    *         preserving the relative order of equivalent elements.
5697    *  @ingroup sorting_algorithms
5698    *  @param  __first   An iterator.
5699    *  @param  __last    Another iterator.
5700    *  @param  __comp    A comparison functor.
5701    *  @return  Nothing.
5702    *
5703    *  Sorts the elements in the range @p [__first,__last) in ascending order,
5704    *  such that for each iterator @p i in the range @p [__first,__last-1),
5705    *  @p __comp(*(i+1),*i) is false.
5706    *
5707    *  The relative ordering of equivalent elements is preserved, so any two
5708    *  elements @p x and @p y in the range @p [__first,__last) such that
5709    *  @p __comp(x,y) is false and @p __comp(y,x) is false will have the same
5710    *  relative ordering after calling @p stable_sort().
5711   */
5712   template<typename _RandomAccessIterator, typename _Compare>
5713     inline void
5714     stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last,
5715                 _Compare __comp)
5716     {
5717       typedef typename iterator_traits<_RandomAccessIterator>::value_type
5718         _ValueType;
5719       typedef typename iterator_traits<_RandomAccessIterator>::difference_type
5720         _DistanceType;
5721
5722       // concept requirements
5723       __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
5724             _RandomAccessIterator>)
5725       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5726                                   _ValueType,
5727                                   _ValueType>)
5728       __glibcxx_requires_valid_range(__first, __last);
5729
5730       _Temporary_buffer<_RandomAccessIterator, _ValueType> __buf(__first,
5731                                                                  __last);
5732       if (__buf.begin() == 0)
5733         std::__inplace_stable_sort(__first, __last, __comp);
5734       else
5735         std::__stable_sort_adaptive(__first, __last, __buf.begin(),
5736                                     _DistanceType(__buf.size()), __comp);
5737     }
5738
5739
5740   /**
5741    *  @brief Return the union of two sorted ranges.
5742    *  @ingroup set_algorithms
5743    *  @param  __first1  Start of first range.
5744    *  @param  __last1   End of first range.
5745    *  @param  __first2  Start of second range.
5746    *  @param  __last2   End of second range.
5747    *  @return  End of the output range.
5748    *  @ingroup set_algorithms
5749    *
5750    *  This operation iterates over both ranges, copying elements present in
5751    *  each range in order to the output range.  Iterators increment for each
5752    *  range.  When the current element of one range is less than the other,
5753    *  that element is copied and the iterator advanced.  If an element is
5754    *  contained in both ranges, the element from the first range is copied and
5755    *  both ranges advance.  The output range may not overlap either input
5756    *  range.
5757   */
5758   template<typename _InputIterator1, typename _InputIterator2,
5759            typename _OutputIterator>
5760     _OutputIterator
5761     set_union(_InputIterator1 __first1, _InputIterator1 __last1,
5762               _InputIterator2 __first2, _InputIterator2 __last2,
5763               _OutputIterator __result)
5764     {
5765       typedef typename iterator_traits<_InputIterator1>::value_type
5766         _ValueType1;
5767       typedef typename iterator_traits<_InputIterator2>::value_type
5768         _ValueType2;
5769
5770       // concept requirements
5771       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
5772       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
5773       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5774                                   _ValueType1>)
5775       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5776                                   _ValueType2>)
5777       __glibcxx_function_requires(_LessThanOpConcept<_ValueType1, _ValueType2>)
5778       __glibcxx_function_requires(_LessThanOpConcept<_ValueType2, _ValueType1>)
5779       __glibcxx_requires_sorted_set(__first1, __last1, __first2);
5780       __glibcxx_requires_sorted_set(__first2, __last2, __first1);
5781
5782       while (__first1 != __last1 && __first2 != __last2)
5783         {
5784           if (*__first1 < *__first2)
5785             {
5786               *__result = *__first1;
5787               ++__first1;
5788             }
5789           else if (*__first2 < *__first1)
5790             {
5791               *__result = *__first2;
5792               ++__first2;
5793             }
5794           else
5795             {
5796               *__result = *__first1;
5797               ++__first1;
5798               ++__first2;
5799             }
5800           ++__result;
5801         }
5802       return std::copy(__first2, __last2, std::copy(__first1, __last1,
5803                                                     __result));
5804     }
5805
5806   /**
5807    *  @brief Return the union of two sorted ranges using a comparison functor.
5808    *  @ingroup set_algorithms
5809    *  @param  __first1  Start of first range.
5810    *  @param  __last1   End of first range.
5811    *  @param  __first2  Start of second range.
5812    *  @param  __last2   End of second range.
5813    *  @param  __comp    The comparison functor.
5814    *  @return  End of the output range.
5815    *  @ingroup set_algorithms
5816    *
5817    *  This operation iterates over both ranges, copying elements present in
5818    *  each range in order to the output range.  Iterators increment for each
5819    *  range.  When the current element of one range is less than the other
5820    *  according to @p __comp, that element is copied and the iterator advanced.
5821    *  If an equivalent element according to @p __comp is contained in both
5822    *  ranges, the element from the first range is copied and both ranges
5823    *  advance.  The output range may not overlap either input range.
5824   */
5825   template<typename _InputIterator1, typename _InputIterator2,
5826            typename _OutputIterator, typename _Compare>
5827     _OutputIterator
5828     set_union(_InputIterator1 __first1, _InputIterator1 __last1,
5829               _InputIterator2 __first2, _InputIterator2 __last2,
5830               _OutputIterator __result, _Compare __comp)
5831     {
5832       typedef typename iterator_traits<_InputIterator1>::value_type
5833         _ValueType1;
5834       typedef typename iterator_traits<_InputIterator2>::value_type
5835         _ValueType2;
5836
5837       // concept requirements
5838       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
5839       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
5840       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5841                                   _ValueType1>)
5842       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5843                                   _ValueType2>)
5844       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5845                                   _ValueType1, _ValueType2>)
5846       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5847                                   _ValueType2, _ValueType1>)
5848       __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp);
5849       __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp);
5850
5851       while (__first1 != __last1 && __first2 != __last2)
5852         {
5853           if (__comp(*__first1, *__first2))
5854             {
5855               *__result = *__first1;
5856               ++__first1;
5857             }
5858           else if (__comp(*__first2, *__first1))
5859             {
5860               *__result = *__first2;
5861               ++__first2;
5862             }
5863           else
5864             {
5865               *__result = *__first1;
5866               ++__first1;
5867               ++__first2;
5868             }
5869           ++__result;
5870         }
5871       return std::copy(__first2, __last2, std::copy(__first1, __last1,
5872                                                     __result));
5873     }
5874
5875   /**
5876    *  @brief Return the intersection of two sorted ranges.
5877    *  @ingroup set_algorithms
5878    *  @param  __first1  Start of first range.
5879    *  @param  __last1   End of first range.
5880    *  @param  __first2  Start of second range.
5881    *  @param  __last2   End of second range.
5882    *  @return  End of the output range.
5883    *  @ingroup set_algorithms
5884    *
5885    *  This operation iterates over both ranges, copying elements present in
5886    *  both ranges in order to the output range.  Iterators increment for each
5887    *  range.  When the current element of one range is less than the other,
5888    *  that iterator advances.  If an element is contained in both ranges, the
5889    *  element from the first range is copied and both ranges advance.  The
5890    *  output range may not overlap either input range.
5891   */
5892   template<typename _InputIterator1, typename _InputIterator2,
5893            typename _OutputIterator>
5894     _OutputIterator
5895     set_intersection(_InputIterator1 __first1, _InputIterator1 __last1,
5896                      _InputIterator2 __first2, _InputIterator2 __last2,
5897                      _OutputIterator __result)
5898     {
5899       typedef typename iterator_traits<_InputIterator1>::value_type
5900         _ValueType1;
5901       typedef typename iterator_traits<_InputIterator2>::value_type
5902         _ValueType2;
5903
5904       // concept requirements
5905       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
5906       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
5907       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5908                                   _ValueType1>)
5909       __glibcxx_function_requires(_LessThanOpConcept<_ValueType1, _ValueType2>)
5910       __glibcxx_function_requires(_LessThanOpConcept<_ValueType2, _ValueType1>)
5911       __glibcxx_requires_sorted_set(__first1, __last1, __first2);
5912       __glibcxx_requires_sorted_set(__first2, __last2, __first1);
5913
5914       while (__first1 != __last1 && __first2 != __last2)
5915         if (*__first1 < *__first2)
5916           ++__first1;
5917         else if (*__first2 < *__first1)
5918           ++__first2;
5919         else
5920           {
5921             *__result = *__first1;
5922             ++__first1;
5923             ++__first2;
5924             ++__result;
5925           }
5926       return __result;
5927     }
5928
5929   /**
5930    *  @brief Return the intersection of two sorted ranges using comparison
5931    *  functor.
5932    *  @ingroup set_algorithms
5933    *  @param  __first1  Start of first range.
5934    *  @param  __last1   End of first range.
5935    *  @param  __first2  Start of second range.
5936    *  @param  __last2   End of second range.
5937    *  @param  __comp    The comparison functor.
5938    *  @return  End of the output range.
5939    *  @ingroup set_algorithms
5940    *
5941    *  This operation iterates over both ranges, copying elements present in
5942    *  both ranges in order to the output range.  Iterators increment for each
5943    *  range.  When the current element of one range is less than the other
5944    *  according to @p __comp, that iterator advances.  If an element is
5945    *  contained in both ranges according to @p __comp, the element from the
5946    *  first range is copied and both ranges advance.  The output range may not
5947    *  overlap either input range.
5948   */
5949   template<typename _InputIterator1, typename _InputIterator2,
5950            typename _OutputIterator, typename _Compare>
5951     _OutputIterator
5952     set_intersection(_InputIterator1 __first1, _InputIterator1 __last1,
5953                      _InputIterator2 __first2, _InputIterator2 __last2,
5954                      _OutputIterator __result, _Compare __comp)
5955     {
5956       typedef typename iterator_traits<_InputIterator1>::value_type
5957         _ValueType1;
5958       typedef typename iterator_traits<_InputIterator2>::value_type
5959         _ValueType2;
5960
5961       // concept requirements
5962       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
5963       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
5964       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5965                                   _ValueType1>)
5966       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5967                                   _ValueType1, _ValueType2>)
5968       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5969                                   _ValueType2, _ValueType1>)
5970       __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp);
5971       __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp);
5972
5973       while (__first1 != __last1 && __first2 != __last2)
5974         if (__comp(*__first1, *__first2))
5975           ++__first1;
5976         else if (__comp(*__first2, *__first1))
5977           ++__first2;
5978         else
5979           {
5980             *__result = *__first1;
5981             ++__first1;
5982             ++__first2;
5983             ++__result;
5984           }
5985       return __result;
5986     }
5987
5988   /**
5989    *  @brief Return the difference of two sorted ranges.
5990    *  @ingroup set_algorithms
5991    *  @param  __first1  Start of first range.
5992    *  @param  __last1   End of first range.
5993    *  @param  __first2  Start of second range.
5994    *  @param  __last2   End of second range.
5995    *  @return  End of the output range.
5996    *  @ingroup set_algorithms
5997    *
5998    *  This operation iterates over both ranges, copying elements present in
5999    *  the first range but not the second in order to the output range.
6000    *  Iterators increment for each range.  When the current element of the
6001    *  first range is less than the second, that element is copied and the
6002    *  iterator advances.  If the current element of the second range is less,
6003    *  the iterator advances, but no element is copied.  If an element is
6004    *  contained in both ranges, no elements are copied and both ranges
6005    *  advance.  The output range may not overlap either input range.
6006   */
6007   template<typename _InputIterator1, typename _InputIterator2,
6008            typename _OutputIterator>
6009     _OutputIterator
6010     set_difference(_InputIterator1 __first1, _InputIterator1 __last1,
6011                    _InputIterator2 __first2, _InputIterator2 __last2,
6012                    _OutputIterator __result)
6013     {
6014       typedef typename iterator_traits<_InputIterator1>::value_type
6015         _ValueType1;
6016       typedef typename iterator_traits<_InputIterator2>::value_type
6017         _ValueType2;
6018
6019       // concept requirements
6020       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
6021       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
6022       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
6023                                   _ValueType1>)
6024       __glibcxx_function_requires(_LessThanOpConcept<_ValueType1, _ValueType2>)
6025       __glibcxx_function_requires(_LessThanOpConcept<_ValueType2, _ValueType1>)
6026       __glibcxx_requires_sorted_set(__first1, __last1, __first2);
6027       __glibcxx_requires_sorted_set(__first2, __last2, __first1);
6028
6029       while (__first1 != __last1 && __first2 != __last2)
6030         if (*__first1 < *__first2)
6031           {
6032             *__result = *__first1;
6033             ++__first1;
6034             ++__result;
6035           }
6036         else if (*__first2 < *__first1)
6037           ++__first2;
6038         else
6039           {
6040             ++__first1;
6041             ++__first2;
6042           }
6043       return std::copy(__first1, __last1, __result);
6044     }
6045
6046   /**
6047    *  @brief  Return the difference of two sorted ranges using comparison
6048    *  functor.
6049    *  @ingroup set_algorithms
6050    *  @param  __first1  Start of first range.
6051    *  @param  __last1   End of first range.
6052    *  @param  __first2  Start of second range.
6053    *  @param  __last2   End of second range.
6054    *  @param  __comp    The comparison functor.
6055    *  @return  End of the output range.
6056    *  @ingroup set_algorithms
6057    *
6058    *  This operation iterates over both ranges, copying elements present in
6059    *  the first range but not the second in order to the output range.
6060    *  Iterators increment for each range.  When the current element of the
6061    *  first range is less than the second according to @p __comp, that element
6062    *  is copied and the iterator advances.  If the current element of the
6063    *  second range is less, no element is copied and the iterator advances.
6064    *  If an element is contained in both ranges according to @p __comp, no
6065    *  elements are copied and both ranges advance.  The output range may not
6066    *  overlap either input range.
6067   */
6068   template<typename _InputIterator1, typename _InputIterator2,
6069            typename _OutputIterator, typename _Compare>
6070     _OutputIterator
6071     set_difference(_InputIterator1 __first1, _InputIterator1 __last1,
6072                    _InputIterator2 __first2, _InputIterator2 __last2,
6073                    _OutputIterator __result, _Compare __comp)
6074     {
6075       typedef typename iterator_traits<_InputIterator1>::value_type
6076         _ValueType1;
6077       typedef typename iterator_traits<_InputIterator2>::value_type
6078         _ValueType2;
6079
6080       // concept requirements
6081       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
6082       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
6083       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
6084                                   _ValueType1>)
6085       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
6086                                   _ValueType1, _ValueType2>)
6087       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
6088                                   _ValueType2, _ValueType1>)
6089       __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp);
6090       __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp);
6091
6092       while (__first1 != __last1 && __first2 != __last2)
6093         if (__comp(*__first1, *__first2))
6094           {
6095             *__result = *__first1;
6096             ++__first1;
6097             ++__result;
6098           }
6099         else if (__comp(*__first2, *__first1))
6100           ++__first2;
6101         else
6102           {
6103             ++__first1;
6104             ++__first2;
6105           }
6106       return std::copy(__first1, __last1, __result);
6107     }
6108
6109   /**
6110    *  @brief  Return the symmetric difference of two sorted ranges.
6111    *  @ingroup set_algorithms
6112    *  @param  __first1  Start of first range.
6113    *  @param  __last1   End of first range.
6114    *  @param  __first2  Start of second range.
6115    *  @param  __last2   End of second range.
6116    *  @return  End of the output range.
6117    *  @ingroup set_algorithms
6118    *
6119    *  This operation iterates over both ranges, copying elements present in
6120    *  one range but not the other in order to the output range.  Iterators
6121    *  increment for each range.  When the current element of one range is less
6122    *  than the other, that element is copied and the iterator advances.  If an
6123    *  element is contained in both ranges, no elements are copied and both
6124    *  ranges advance.  The output range may not overlap either input range.
6125   */
6126   template<typename _InputIterator1, typename _InputIterator2,
6127            typename _OutputIterator>
6128     _OutputIterator
6129     set_symmetric_difference(_InputIterator1 __first1, _InputIterator1 __last1,
6130                              _InputIterator2 __first2, _InputIterator2 __last2,
6131                              _OutputIterator __result)
6132     {
6133       typedef typename iterator_traits<_InputIterator1>::value_type
6134         _ValueType1;
6135       typedef typename iterator_traits<_InputIterator2>::value_type
6136         _ValueType2;
6137
6138       // concept requirements
6139       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
6140       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
6141       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
6142                                   _ValueType1>)
6143       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
6144                                   _ValueType2>)
6145       __glibcxx_function_requires(_LessThanOpConcept<_ValueType1, _ValueType2>)
6146       __glibcxx_function_requires(_LessThanOpConcept<_ValueType2, _ValueType1>)
6147       __glibcxx_requires_sorted_set(__first1, __last1, __first2);
6148       __glibcxx_requires_sorted_set(__first2, __last2, __first1);
6149
6150       while (__first1 != __last1 && __first2 != __last2)
6151         if (*__first1 < *__first2)
6152           {
6153             *__result = *__first1;
6154             ++__first1;
6155             ++__result;
6156           }
6157         else if (*__first2 < *__first1)
6158           {
6159             *__result = *__first2;
6160             ++__first2;
6161             ++__result;
6162           }
6163         else
6164           {
6165             ++__first1;
6166             ++__first2;
6167           }
6168       return std::copy(__first2, __last2, std::copy(__first1,
6169                                                     __last1, __result));
6170     }
6171
6172   /**
6173    *  @brief  Return the symmetric difference of two sorted ranges using
6174    *  comparison functor.
6175    *  @ingroup set_algorithms
6176    *  @param  __first1  Start of first range.
6177    *  @param  __last1   End of first range.
6178    *  @param  __first2  Start of second range.
6179    *  @param  __last2   End of second range.
6180    *  @param  __comp    The comparison functor.
6181    *  @return  End of the output range.
6182    *  @ingroup set_algorithms
6183    *
6184    *  This operation iterates over both ranges, copying elements present in
6185    *  one range but not the other in order to the output range.  Iterators
6186    *  increment for each range.  When the current element of one range is less
6187    *  than the other according to @p comp, that element is copied and the
6188    *  iterator advances.  If an element is contained in both ranges according
6189    *  to @p __comp, no elements are copied and both ranges advance.  The output
6190    *  range may not overlap either input range.
6191   */
6192   template<typename _InputIterator1, typename _InputIterator2,
6193            typename _OutputIterator, typename _Compare>
6194     _OutputIterator
6195     set_symmetric_difference(_InputIterator1 __first1, _InputIterator1 __last1,
6196                              _InputIterator2 __first2, _InputIterator2 __last2,
6197                              _OutputIterator __result,
6198                              _Compare __comp)
6199     {
6200       typedef typename iterator_traits<_InputIterator1>::value_type
6201         _ValueType1;
6202       typedef typename iterator_traits<_InputIterator2>::value_type
6203         _ValueType2;
6204
6205       // concept requirements
6206       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
6207       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
6208       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
6209                                   _ValueType1>)
6210       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
6211                                   _ValueType2>)
6212       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
6213                                   _ValueType1, _ValueType2>)
6214       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
6215                                   _ValueType2, _ValueType1>)
6216       __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp);
6217       __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp);
6218
6219       while (__first1 != __last1 && __first2 != __last2)
6220         if (__comp(*__first1, *__first2))
6221           {
6222             *__result = *__first1;
6223             ++__first1;
6224             ++__result;
6225           }
6226         else if (__comp(*__first2, *__first1))
6227           {
6228             *__result = *__first2;
6229             ++__first2;
6230             ++__result;
6231           }
6232         else
6233           {
6234             ++__first1;
6235             ++__first2;
6236           }
6237       return std::copy(__first2, __last2,
6238                        std::copy(__first1, __last1, __result));
6239     }
6240
6241
6242   /**
6243    *  @brief  Return the minimum element in a range.
6244    *  @ingroup sorting_algorithms
6245    *  @param  __first  Start of range.
6246    *  @param  __last   End of range.
6247    *  @return  Iterator referencing the first instance of the smallest value.
6248   */
6249   template<typename _ForwardIterator>
6250     _ForwardIterator
6251     min_element(_ForwardIterator __first, _ForwardIterator __last)
6252     {
6253       // concept requirements
6254       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
6255       __glibcxx_function_requires(_LessThanComparableConcept<
6256             typename iterator_traits<_ForwardIterator>::value_type>)
6257       __glibcxx_requires_valid_range(__first, __last);
6258
6259       if (__first == __last)
6260         return __first;
6261       _ForwardIterator __result = __first;
6262       while (++__first != __last)
6263         if (*__first < *__result)
6264           __result = __first;
6265       return __result;
6266     }
6267
6268   /**
6269    *  @brief  Return the minimum element in a range using comparison functor.
6270    *  @ingroup sorting_algorithms
6271    *  @param  __first  Start of range.
6272    *  @param  __last   End of range.
6273    *  @param  __comp   Comparison functor.
6274    *  @return  Iterator referencing the first instance of the smallest value
6275    *  according to __comp.
6276   */
6277   template<typename _ForwardIterator, typename _Compare>
6278     _ForwardIterator
6279     min_element(_ForwardIterator __first, _ForwardIterator __last,
6280                 _Compare __comp)
6281     {
6282       // concept requirements
6283       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
6284       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
6285             typename iterator_traits<_ForwardIterator>::value_type,
6286             typename iterator_traits<_ForwardIterator>::value_type>)
6287       __glibcxx_requires_valid_range(__first, __last);
6288
6289       if (__first == __last)
6290         return __first;
6291       _ForwardIterator __result = __first;
6292       while (++__first != __last)
6293         if (__comp(*__first, *__result))
6294           __result = __first;
6295       return __result;
6296     }
6297
6298   /**
6299    *  @brief  Return the maximum element in a range.
6300    *  @ingroup sorting_algorithms
6301    *  @param  __first  Start of range.
6302    *  @param  __last   End of range.
6303    *  @return  Iterator referencing the first instance of the largest value.
6304   */
6305   template<typename _ForwardIterator>
6306     _ForwardIterator
6307     max_element(_ForwardIterator __first, _ForwardIterator __last)
6308     {
6309       // concept requirements
6310       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
6311       __glibcxx_function_requires(_LessThanComparableConcept<
6312             typename iterator_traits<_ForwardIterator>::value_type>)
6313       __glibcxx_requires_valid_range(__first, __last);
6314
6315       if (__first == __last)
6316         return __first;
6317       _ForwardIterator __result = __first;
6318       while (++__first != __last)
6319         if (*__result < *__first)
6320           __result = __first;
6321       return __result;
6322     }
6323
6324   /**
6325    *  @brief  Return the maximum element in a range using comparison functor.
6326    *  @ingroup sorting_algorithms
6327    *  @param  __first  Start of range.
6328    *  @param  __last   End of range.
6329    *  @param  __comp   Comparison functor.
6330    *  @return  Iterator referencing the first instance of the largest value
6331    *  according to __comp.
6332   */
6333   template<typename _ForwardIterator, typename _Compare>
6334     _ForwardIterator
6335     max_element(_ForwardIterator __first, _ForwardIterator __last,
6336                 _Compare __comp)
6337     {
6338       // concept requirements
6339       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
6340       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
6341             typename iterator_traits<_ForwardIterator>::value_type,
6342             typename iterator_traits<_ForwardIterator>::value_type>)
6343       __glibcxx_requires_valid_range(__first, __last);
6344
6345       if (__first == __last) return __first;
6346       _ForwardIterator __result = __first;
6347       while (++__first != __last)
6348         if (__comp(*__result, *__first))
6349           __result = __first;
6350       return __result;
6351     }
6352
6353 _GLIBCXX_END_NAMESPACE_ALGO
6354 } // namespace std
6355
6356 #endif /* _STL_ALGO_H */