contrib/gcc-4.7/libstdc++-v3/include/bits/stl_algo.h

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