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