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

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