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

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