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) ==
 633    *  @p *(__first2+N) for each @c N in the range @p
 634    *  [0,__last2-__first2), or @p __last1 if no such iterator exists.
 635    *
 636    *  Searches the range @p [__first1,__last1) for a sub-sequence that
 637    *  compares equal value-by-value with the sequence given by @p
 638    *  [__first2,__last2) and returns an iterator to the __first
 639    *  element of the sub-sequence, or @p __last1 if the sub-sequence
 640    *  is not found.  The sub-sequence will be the last such
 641    *  subsequence contained in [__first,__last1).
 642    *
 643    *  Because the sub-sequence must lie completely within the range @p
 644    *  [__first1,__last1) it must start at a position less than @p
 645    *  __last1-(__last2-__first2) where @p __last2-__first2 is the
 646    *  length of the sub-sequence.  This means that the returned
 647    *  iterator @c i will be in the range @p
 648    *  [__first1,__last1-(__last2-__first2))
 649   */
 650   template<typename _ForwardIterator1, typename _ForwardIterator2>
 651     inline _ForwardIterator1
 652     find_end(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
 653              _ForwardIterator2 __first2, _ForwardIterator2 __last2)
 654     {
 655       // concept requirements
 656       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator1>)
 657       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator2>)
 658       __glibcxx_function_requires(_EqualOpConcept<
 659             typename iterator_traits<_ForwardIterator1>::value_type,
 660             typename iterator_traits<_ForwardIterator2>::value_type>)
 661       __glibcxx_requires_valid_range(__first1, __last1);
 662       __glibcxx_requires_valid_range(__first2, __last2);
 663
 664       return std::__find_end(__first1, __last1, __first2, __last2,
 665                              std::__iterator_category(__first1),
 666                              std::__iterator_category(__first2));
 667     }
 668
 669   /**
 670    *  @brief  Find last matching subsequence in a sequence using a predicate.
 671    *  @ingroup non_mutating_algorithms
 672    *  @param  __first1  Start of range to search.
 673    *  @param  __last1   End of range to search.
 674    *  @param  __first2  Start of sequence to match.
 675    *  @param  __last2   End of sequence to match.
 676    *  @param  __comp    The predicate to use.
 677    *  @return The last iterator @c i in the range @p
 678    *  [__first1,__last1-(__last2-__first2)) such that @c
 679    *  predicate(*(i+N), @p (__first2+N)) is true for each @c N in the
 680    *  range @p [0,__last2-__first2), or @p __last1 if no such iterator
 681    *  exists.
 682    *
 683    *  Searches the range @p [__first1,__last1) for a sub-sequence that
 684    *  compares equal value-by-value with the sequence given by @p
 685    *  [__first2,__last2) using comp as a predicate and returns an
 686    *  iterator to the first element of the sub-sequence, or @p __last1
 687    *  if the sub-sequence is not found.  The sub-sequence will be the
 688    *  last such subsequence contained in [__first,__last1).
 689    *
 690    *  Because the sub-sequence must lie completely within the range @p
 691    *  [__first1,__last1) it must start at a position less than @p
 692    *  __last1-(__last2-__first2) where @p __last2-__first2 is the
 693    *  length of the sub-sequence.  This means that the returned
 694    *  iterator @c i will be in the range @p
 695    *  [__first1,__last1-(__last2-__first2))
 696   */
 697   template<typename _ForwardIterator1, typename _ForwardIterator2,
 698            typename _BinaryPredicate>
 699     inline _ForwardIterator1
 700     find_end(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
 701              _ForwardIterator2 __first2, _ForwardIterator2 __last2,
 702              _BinaryPredicate __comp)
 703     {
 704       // concept requirements
 705       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator1>)
 706       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator2>)
 707       __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
 708             typename iterator_traits<_ForwardIterator1>::value_type,
 709             typename iterator_traits<_ForwardIterator2>::value_type>)
 710       __glibcxx_requires_valid_range(__first1, __last1);
 711       __glibcxx_requires_valid_range(__first2, __last2);
 712
 713       return std::__find_end(__first1, __last1, __first2, __last2,
 714                              std::__iterator_category(__first1),
 715                              std::__iterator_category(__first2),
 716                              __comp);
 717     }
 718
 719 #ifdef __GXX_EXPERIMENTAL_CXX0X__
 720   /**
 721    *  @brief  Checks that a predicate is true for all the elements
 722    *          of a sequence.
 723    *  @ingroup non_mutating_algorithms
 724    *  @param  __first   An input iterator.
 725    *  @param  __last    An input iterator.
 726    *  @param  __pred    A predicate.
 727    *  @return  True if the check is true, false otherwise.
 728    *
 729    *  Returns true if @p __pred is true for each element in the range
 730    *  @p [__first,__last), and false otherwise.
 731   */
 732   template<typename _InputIterator, typename _Predicate>
 733     inline bool
 734     all_of(_InputIterator __first, _InputIterator __last, _Predicate __pred)
 735     { return __last == std::find_if_not(__first, __last, __pred); }
 736
 737   /**
 738    *  @brief  Checks that a predicate is false for all the elements
 739    *          of a sequence.
 740    *  @ingroup non_mutating_algorithms
 741    *  @param  __first   An input iterator.
 742    *  @param  __last    An input iterator.
 743    *  @param  __pred    A predicate.
 744    *  @return  True if the check is true, false otherwise.
 745    *
 746    *  Returns true if @p __pred is false for each element in the range
 747    *  @p [__first,__last), and false otherwise.
 748   */
 749   template<typename _InputIterator, typename _Predicate>
 750     inline bool
 751     none_of(_InputIterator __first, _InputIterator __last, _Predicate __pred)
 752     { return __last == _GLIBCXX_STD_A::find_if(__first, __last, __pred); }
 753
 754   /**
 755    *  @brief  Checks that a predicate is false for at least an element
 756    *          of a sequence.
 757    *  @ingroup non_mutating_algorithms
 758    *  @param  __first   An input iterator.
 759    *  @param  __last    An input iterator.
 760    *  @param  __pred    A predicate.
 761    *  @return  True if the check is true, false otherwise.
 762    *
 763    *  Returns true if an element exists in the range @p
 764    *  [__first,__last) such that @p __pred is true, and false
 765    *  otherwise.
 766   */
 767   template<typename _InputIterator, typename _Predicate>
 768     inline bool
 769     any_of(_InputIterator __first, _InputIterator __last, _Predicate __pred)
 770     { return !std::none_of(__first, __last, __pred); }
 771
 772   /**
 773    *  @brief  Find the first element in a sequence for which a
 774    *          predicate is false.
 775    *  @ingroup non_mutating_algorithms
 776    *  @param  __first  An input iterator.
 777    *  @param  __last   An input iterator.
 778    *  @param  __pred   A predicate.
 779    *  @return   The first iterator @c i in the range @p [__first,__last)
 780    *  such that @p __pred(*i) is false, or @p __last if no such iterator exists.
 781   */
 782   template<typename _InputIterator, typename _Predicate>
 783     inline _InputIterator
 784     find_if_not(_InputIterator __first, _InputIterator __last,
 785                 _Predicate __pred)
 786     {
 787       // concept requirements
 788       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
 789       __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
 790               typename iterator_traits<_InputIterator>::value_type>)
 791       __glibcxx_requires_valid_range(__first, __last);
 792       return std::__find_if_not(__first, __last, __pred,
 793                                 std::__iterator_category(__first));
 794     }
 795
 796   /**
 797    *  @brief  Checks whether the sequence is partitioned.
 798    *  @ingroup mutating_algorithms
 799    *  @param  __first  An input iterator.
 800    *  @param  __last   An input iterator.
 801    *  @param  __pred   A predicate.
 802    *  @return  True if the range @p [__first,__last) is partioned by @p __pred,
 803    *  i.e. if all elements that satisfy @p __pred appear before those that
 804    *  do not.
 805   */
 806   template<typename _InputIterator, typename _Predicate>
 807     inline bool
 808     is_partitioned(_InputIterator __first, _InputIterator __last,
 809                    _Predicate __pred)
 810     {
 811       __first = std::find_if_not(__first, __last, __pred);
 812       return std::none_of(__first, __last, __pred);
 813     }
 814
 815   /**
 816    *  @brief  Find the partition point of a partitioned range.
 817    *  @ingroup mutating_algorithms
 818    *  @param  __first   An iterator.
 819    *  @param  __last    Another iterator.
 820    *  @param  __pred    A predicate.
 821    *  @return  An iterator @p mid such that @p all_of(__first, mid, __pred)
 822    *           and @p none_of(mid, __last, __pred) are both true.
 823   */
 824   template<typename _ForwardIterator, typename _Predicate>
 825     _ForwardIterator
 826     partition_point(_ForwardIterator __first, _ForwardIterator __last,
 827                     _Predicate __pred)
 828     {
 829       // concept requirements
 830       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
 831       __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
 832               typename iterator_traits<_ForwardIterator>::value_type>)
 833
 834       // A specific debug-mode test will be necessary...
 835       __glibcxx_requires_valid_range(__first, __last);
 836
 837       typedef typename iterator_traits<_ForwardIterator>::difference_type
 838         _DistanceType;
 839
 840       _DistanceType __len = std::distance(__first, __last);
 841       _DistanceType __half;
 842       _ForwardIterator __middle;
 843
 844       while (__len > 0)
 845         {
 846           __half = __len >> 1;
 847           __middle = __first;
 848           std::advance(__middle, __half);
 849           if (__pred(*__middle))
 850             {
 851               __first = __middle;
 852               ++__first;
 853               __len = __len - __half - 1;
 854             }
 855           else
 856             __len = __half;
 857         }
 858       return __first;
 859     }
 860 #endif
 861
 862
 863   /**
 864    *  @brief Copy a sequence, removing elements of a given value.
 865    *  @ingroup mutating_algorithms
 866    *  @param  __first   An input iterator.
 867    *  @param  __last    An input iterator.
 868    *  @param  __result  An output iterator.
 869    *  @param  __value   The value to be removed.
 870    *  @return   An iterator designating the end of the resulting sequence.
 871    *
 872    *  Copies each element in the range @p [__first,__last) not equal
 873    *  to @p __value to the range beginning at @p __result.
 874    *  remove_copy() is stable, so the relative order of elements that
 875    *  are copied is unchanged.
 876   */
 877   template<typename _InputIterator, typename _OutputIterator, typename _Tp>
 878     _OutputIterator
 879     remove_copy(_InputIterator __first, _InputIterator __last,
 880                 _OutputIterator __result, const _Tp& __value)
 881     {
 882       // concept requirements
 883       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
 884       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
 885             typename iterator_traits<_InputIterator>::value_type>)
 886       __glibcxx_function_requires(_EqualOpConcept<
 887             typename iterator_traits<_InputIterator>::value_type, _Tp>)
 888       __glibcxx_requires_valid_range(__first, __last);
 889
 890       for (; __first != __last; ++__first)
 891         if (!(*__first == __value))
 892           {
 893             *__result = *__first;
 894             ++__result;
 895           }
 896       return __result;
 897     }
 898
 899   /**
 900    *  @brief Copy a sequence, removing elements for which a predicate is true.
 901    *  @ingroup mutating_algorithms
 902    *  @param  __first   An input iterator.
 903    *  @param  __last    An input iterator.
 904    *  @param  __result  An output iterator.
 905    *  @param  __pred    A predicate.
 906    *  @return   An iterator designating the end of the resulting sequence.
 907    *
 908    *  Copies each element in the range @p [__first,__last) for which
 909    *  @p __pred returns false to the range beginning at @p __result.
 910    *
 911    *  remove_copy_if() is stable, so the relative order of elements that are
 912    *  copied is unchanged.
 913   */
 914   template<typename _InputIterator, typename _OutputIterator,
 915            typename _Predicate>
 916     _OutputIterator
 917     remove_copy_if(_InputIterator __first, _InputIterator __last,
 918                    _OutputIterator __result, _Predicate __pred)
 919     {
 920       // concept requirements
 921       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
 922       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
 923             typename iterator_traits<_InputIterator>::value_type>)
 924       __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
 925             typename iterator_traits<_InputIterator>::value_type>)
 926       __glibcxx_requires_valid_range(__first, __last);
 927
 928       for (; __first != __last; ++__first)
 929         if (!bool(__pred(*__first)))
 930           {
 931             *__result = *__first;
 932             ++__result;
 933           }
 934       return __result;
 935     }
 936
 937 #ifdef __GXX_EXPERIMENTAL_CXX0X__
 938   /**
 939    *  @brief Copy the elements of a sequence for which a predicate is true.
 940    *  @ingroup mutating_algorithms
 941    *  @param  __first   An input iterator.
 942    *  @param  __last    An input iterator.
 943    *  @param  __result  An output iterator.
 944    *  @param  __pred    A predicate.
 945    *  @return   An iterator designating the end of the resulting sequence.
 946    *
 947    *  Copies each element in the range @p [__first,__last) for which
 948    *  @p __pred returns true to the range beginning at @p __result.
 949    *
 950    *  copy_if() is stable, so the relative order of elements that are
 951    *  copied is unchanged.
 952   */
 953   template<typename _InputIterator, typename _OutputIterator,
 954            typename _Predicate>
 955     _OutputIterator
 956     copy_if(_InputIterator __first, _InputIterator __last,
 957             _OutputIterator __result, _Predicate __pred)
 958     {
 959       // concept requirements
 960       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
 961       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
 962             typename iterator_traits<_InputIterator>::value_type>)
 963       __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
 964             typename iterator_traits<_InputIterator>::value_type>)
 965       __glibcxx_requires_valid_range(__first, __last);
 966
 967       for (; __first != __last; ++__first)
 968         if (__pred(*__first))
 969           {
 970             *__result = *__first;
 971             ++__result;
 972           }
 973       return __result;
 974     }
 975
 976
 977   template<typename _InputIterator, typename _Size, typename _OutputIterator>
 978     _OutputIterator
 979     __copy_n(_InputIterator __first, _Size __n,
 980              _OutputIterator __result, input_iterator_tag)
 981     {
 982       if (__n > 0)
 983         {
 984           while (true)
 985             {
 986               *__result = *__first;
 987               ++__result;
 988               if (--__n > 0)
 989                 ++__first;
 990               else
 991                 break;
 992             }
 993         }
 994       return __result;
 995     }
 996
 997   template<typename _RandomAccessIterator, typename _Size,
 998            typename _OutputIterator>
 999     inline _OutputIterator
1000     __copy_n(_RandomAccessIterator __first, _Size __n,
1001              _OutputIterator __result, random_access_iterator_tag)
1002     { return std::copy(__first, __first + __n, __result); }
1003
1004   /**
1005    *  @brief Copies the range [first,first+n) into [result,result+n).
1006    *  @ingroup mutating_algorithms
1007    *  @param  __first  An input iterator.
1008    *  @param  __n      The number of elements to copy.
1009    *  @param  __result An output iterator.
1010    *  @return  result+n.
1011    *
1012    *  This inline function will boil down to a call to @c memmove whenever
1013    *  possible.  Failing that, if random access iterators are passed, then the
1014    *  loop count will be known (and therefore a candidate for compiler
1015    *  optimizations such as unrolling).
1016   */
1017   template<typename _InputIterator, typename _Size, typename _OutputIterator>
1018     inline _OutputIterator
1019     copy_n(_InputIterator __first, _Size __n, _OutputIterator __result)
1020     {
1021       // concept requirements
1022       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
1023       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
1024             typename iterator_traits<_InputIterator>::value_type>)
1025
1026       return std::__copy_n(__first, __n, __result,
1027                            std::__iterator_category(__first));
1028     }
1029
1030   /**
1031    *  @brief Copy the elements of a sequence to separate output sequences
1032    *         depending on the truth value of a predicate.
1033    *  @ingroup mutating_algorithms
1034    *  @param  __first   An input iterator.
1035    *  @param  __last    An input iterator.
1036    *  @param  __out_true   An output iterator.
1037    *  @param  __out_false  An output iterator.
1038    *  @param  __pred    A predicate.
1039    *  @return   A pair designating the ends of the resulting sequences.
1040    *
1041    *  Copies each element in the range @p [__first,__last) for which
1042    *  @p __pred returns true to the range beginning at @p out_true
1043    *  and each element for which @p __pred returns false to @p __out_false.
1044   */
1045   template<typename _InputIterator, typename _OutputIterator1,
1046            typename _OutputIterator2, typename _Predicate>
1047     pair<_OutputIterator1, _OutputIterator2>
1048     partition_copy(_InputIterator __first, _InputIterator __last,
1049                    _OutputIterator1 __out_true, _OutputIterator2 __out_false,
1050                    _Predicate __pred)
1051     {
1052       // concept requirements
1053       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
1054       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator1,
1055             typename iterator_traits<_InputIterator>::value_type>)
1056       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator2,
1057             typename iterator_traits<_InputIterator>::value_type>)
1058       __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
1059             typename iterator_traits<_InputIterator>::value_type>)
1060       __glibcxx_requires_valid_range(__first, __last);
1061
1062       for (; __first != __last; ++__first)
1063         if (__pred(*__first))
1064           {
1065             *__out_true = *__first;
1066             ++__out_true;
1067           }
1068         else
1069           {
1070             *__out_false = *__first;
1071             ++__out_false;
1072           }
1073
1074       return pair<_OutputIterator1, _OutputIterator2>(__out_true, __out_false);
1075     }
1076 #endif
1077
1078   /**
1079    *  @brief Remove elements from a sequence.
1080    *  @ingroup mutating_algorithms
1081    *  @param  __first  An input iterator.
1082    *  @param  __last   An input iterator.
1083    *  @param  __value  The value to be removed.
1084    *  @return   An iterator designating the end of the resulting sequence.
1085    *
1086    *  All elements equal to @p __value are removed from the range
1087    *  @p [__first,__last).
1088    *
1089    *  remove() is stable, so the relative order of elements that are
1090    *  not removed is unchanged.
1091    *
1092    *  Elements between the end of the resulting sequence and @p __last
1093    *  are still present, but their value is unspecified.
1094   */
1095   template<typename _ForwardIterator, typename _Tp>
1096     _ForwardIterator
1097     remove(_ForwardIterator __first, _ForwardIterator __last,
1098            const _Tp& __value)
1099     {
1100       // concept requirements
1101       __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
1102                                   _ForwardIterator>)
1103       __glibcxx_function_requires(_EqualOpConcept<
1104             typename iterator_traits<_ForwardIterator>::value_type, _Tp>)
1105       __glibcxx_requires_valid_range(__first, __last);
1106
1107       __first = _GLIBCXX_STD_A::find(__first, __last, __value);
1108       if(__first == __last)
1109         return __first;
1110       _ForwardIterator __result = __first;
1111       ++__first;
1112       for(; __first != __last; ++__first)
1113         if(!(*__first == __value))
1114           {
1115             *__result = _GLIBCXX_MOVE(*__first);
1116             ++__result;
1117           }
1118       return __result;
1119     }
1120
1121   /**
1122    *  @brief Remove elements from a sequence using a predicate.
1123    *  @ingroup mutating_algorithms
1124    *  @param  __first  A forward iterator.
1125    *  @param  __last   A forward iterator.
1126    *  @param  __pred   A predicate.
1127    *  @return   An iterator designating the end of the resulting sequence.
1128    *
1129    *  All elements for which @p __pred returns true are removed from the range
1130    *  @p [__first,__last).
1131    *
1132    *  remove_if() is stable, so the relative order of elements that are
1133    *  not removed is unchanged.
1134    *
1135    *  Elements between the end of the resulting sequence and @p __last
1136    *  are still present, but their value is unspecified.
1137   */
1138   template<typename _ForwardIterator, typename _Predicate>
1139     _ForwardIterator
1140     remove_if(_ForwardIterator __first, _ForwardIterator __last,
1141               _Predicate __pred)
1142     {
1143       // concept requirements
1144       __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
1145                                   _ForwardIterator>)
1146       __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
1147             typename iterator_traits<_ForwardIterator>::value_type>)
1148       __glibcxx_requires_valid_range(__first, __last);
1149
1150       __first = _GLIBCXX_STD_A::find_if(__first, __last, __pred);
1151       if(__first == __last)
1152         return __first;
1153       _ForwardIterator __result = __first;
1154       ++__first;
1155       for(; __first != __last; ++__first)
1156         if(!bool(__pred(*__first)))
1157           {
1158             *__result = _GLIBCXX_MOVE(*__first);
1159             ++__result;
1160           }
1161       return __result;
1162     }
1163
1164   /**
1165    *  @brief Remove consecutive duplicate values from a sequence.
1166    *  @ingroup mutating_algorithms
1167    *  @param  __first  A forward iterator.
1168    *  @param  __last   A forward iterator.
1169    *  @return  An iterator designating the end of the resulting sequence.
1170    *
1171    *  Removes all but the first element from each group of consecutive
1172    *  values that compare equal.
1173    *  unique() is stable, so the relative order of elements that are
1174    *  not removed is unchanged.
1175    *  Elements between the end of the resulting sequence and @p __last
1176    *  are still present, but their value is unspecified.
1177   */
1178   template<typename _ForwardIterator>
1179     _ForwardIterator
1180     unique(_ForwardIterator __first, _ForwardIterator __last)
1181     {
1182       // concept requirements
1183       __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
1184                                   _ForwardIterator>)
1185       __glibcxx_function_requires(_EqualityComparableConcept<
1186                      typename iterator_traits<_ForwardIterator>::value_type>)
1187       __glibcxx_requires_valid_range(__first, __last);
1188
1189       // Skip the beginning, if already unique.
1190       __first = _GLIBCXX_STD_A::adjacent_find(__first, __last);
1191       if (__first == __last)
1192         return __last;
1193
1194       // Do the real copy work.
1195       _ForwardIterator __dest = __first;
1196       ++__first;
1197       while (++__first != __last)
1198         if (!(*__dest == *__first))
1199           *++__dest = _GLIBCXX_MOVE(*__first);
1200       return ++__dest;
1201     }
1202
1203   /**
1204    *  @brief Remove consecutive values from a sequence using a predicate.
1205    *  @ingroup mutating_algorithms
1206    *  @param  __first        A forward iterator.
1207    *  @param  __last         A forward iterator.
1208    *  @param  __binary_pred  A binary predicate.
1209    *  @return  An iterator designating the end of the resulting sequence.
1210    *
1211    *  Removes all but the first element from each group of consecutive
1212    *  values for which @p __binary_pred returns true.
1213    *  unique() is stable, so the relative order of elements that are
1214    *  not removed is unchanged.
1215    *  Elements between the end of the resulting sequence and @p __last
1216    *  are still present, but their value is unspecified.
1217   */
1218   template<typename _ForwardIterator, typename _BinaryPredicate>
1219     _ForwardIterator
1220     unique(_ForwardIterator __first, _ForwardIterator __last,
1221            _BinaryPredicate __binary_pred)
1222     {
1223       // concept requirements
1224       __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
1225                                   _ForwardIterator>)
1226       __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
1227                 typename iterator_traits<_ForwardIterator>::value_type,
1228                 typename iterator_traits<_ForwardIterator>::value_type>)
1229       __glibcxx_requires_valid_range(__first, __last);
1230
1231       // Skip the beginning, if already unique.
1232       __first = _GLIBCXX_STD_A::adjacent_find(__first, __last, __binary_pred);
1233       if (__first == __last)
1234         return __last;
1235
1236       // Do the real copy work.
1237       _ForwardIterator __dest = __first;
1238       ++__first;
1239       while (++__first != __last)
1240         if (!bool(__binary_pred(*__dest, *__first)))
1241           *++__dest = _GLIBCXX_MOVE(*__first);
1242       return ++__dest;
1243     }
1244
1245   /**
1246    *  This is an uglified unique_copy(_InputIterator, _InputIterator,
1247    *                                  _OutputIterator)
1248    *  overloaded for forward iterators and output iterator as result.
1249   */
1250   template<typename _ForwardIterator, typename _OutputIterator>
1251     _OutputIterator
1252     __unique_copy(_ForwardIterator __first, _ForwardIterator __last,
1253                   _OutputIterator __result,
1254                   forward_iterator_tag, output_iterator_tag)
1255     {
1256       // concept requirements -- taken care of in dispatching function
1257       _ForwardIterator __next = __first;
1258       *__result = *__first;
1259       while (++__next != __last)
1260         if (!(*__first == *__next))
1261           {
1262             __first = __next;
1263             *++__result = *__first;
1264           }
1265       return ++__result;
1266     }
1267
1268   /**
1269    *  This is an uglified unique_copy(_InputIterator, _InputIterator,
1270    *                                  _OutputIterator)
1271    *  overloaded for input iterators and output iterator as result.
1272   */
1273   template<typename _InputIterator, typename _OutputIterator>
1274     _OutputIterator
1275     __unique_copy(_InputIterator __first, _InputIterator __last,
1276                   _OutputIterator __result,
1277                   input_iterator_tag, output_iterator_tag)
1278     {
1279       // concept requirements -- taken care of in dispatching function
1280       typename iterator_traits<_InputIterator>::value_type __value = *__first;
1281       *__result = __value;
1282       while (++__first != __last)
1283         if (!(__value == *__first))
1284           {
1285             __value = *__first;
1286             *++__result = __value;
1287           }
1288       return ++__result;
1289     }
1290
1291   /**
1292    *  This is an uglified unique_copy(_InputIterator, _InputIterator,
1293    *                                  _OutputIterator)
1294    *  overloaded for input iterators and forward iterator as result.
1295   */
1296   template<typename _InputIterator, typename _ForwardIterator>
1297     _ForwardIterator
1298     __unique_copy(_InputIterator __first, _InputIterator __last,
1299                   _ForwardIterator __result,
1300                   input_iterator_tag, forward_iterator_tag)
1301     {
1302       // concept requirements -- taken care of in dispatching function
1303       *__result = *__first;
1304       while (++__first != __last)
1305         if (!(*__result == *__first))
1306           *++__result = *__first;
1307       return ++__result;
1308     }
1309
1310   /**
1311    *  This is an uglified
1312    *  unique_copy(_InputIterator, _InputIterator, _OutputIterator,
1313    *              _BinaryPredicate)
1314    *  overloaded for forward iterators and output iterator as result.
1315   */
1316   template<typename _ForwardIterator, typename _OutputIterator,
1317            typename _BinaryPredicate>
1318     _OutputIterator
1319     __unique_copy(_ForwardIterator __first, _ForwardIterator __last,
1320                   _OutputIterator __result, _BinaryPredicate __binary_pred,
1321                   forward_iterator_tag, output_iterator_tag)
1322     {
1323       // concept requirements -- iterators already checked
1324       __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
1325           typename iterator_traits<_ForwardIterator>::value_type,
1326           typename iterator_traits<_ForwardIterator>::value_type>)
1327
1328       _ForwardIterator __next = __first;
1329       *__result = *__first;
1330       while (++__next != __last)
1331         if (!bool(__binary_pred(*__first, *__next)))
1332           {
1333             __first = __next;
1334             *++__result = *__first;
1335           }
1336       return ++__result;
1337     }
1338
1339   /**
1340    *  This is an uglified
1341    *  unique_copy(_InputIterator, _InputIterator, _OutputIterator,
1342    *              _BinaryPredicate)
1343    *  overloaded for input iterators and output iterator as result.
1344   */
1345   template<typename _InputIterator, typename _OutputIterator,
1346            typename _BinaryPredicate>
1347     _OutputIterator
1348     __unique_copy(_InputIterator __first, _InputIterator __last,
1349                   _OutputIterator __result, _BinaryPredicate __binary_pred,
1350                   input_iterator_tag, output_iterator_tag)
1351     {
1352       // concept requirements -- iterators already checked
1353       __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
1354           typename iterator_traits<_InputIterator>::value_type,
1355           typename iterator_traits<_InputIterator>::value_type>)
1356
1357       typename iterator_traits<_InputIterator>::value_type __value = *__first;
1358       *__result = __value;
1359       while (++__first != __last)
1360         if (!bool(__binary_pred(__value, *__first)))
1361           {
1362             __value = *__first;
1363             *++__result = __value;
1364           }
1365       return ++__result;
1366     }
1367
1368   /**
1369    *  This is an uglified
1370    *  unique_copy(_InputIterator, _InputIterator, _OutputIterator,
1371    *              _BinaryPredicate)
1372    *  overloaded for input iterators and forward iterator as result.
1373   */
1374   template<typename _InputIterator, typename _ForwardIterator,
1375            typename _BinaryPredicate>
1376     _ForwardIterator
1377     __unique_copy(_InputIterator __first, _InputIterator __last,
1378                   _ForwardIterator __result, _BinaryPredicate __binary_pred,
1379                   input_iterator_tag, forward_iterator_tag)
1380     {
1381       // concept requirements -- iterators already checked
1382       __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
1383           typename iterator_traits<_ForwardIterator>::value_type,
1384           typename iterator_traits<_InputIterator>::value_type>)
1385
1386       *__result = *__first;
1387       while (++__first != __last)
1388         if (!bool(__binary_pred(*__result, *__first)))
1389           *++__result = *__first;
1390       return ++__result;
1391     }
1392
1393   /**
1394    *  This is an uglified reverse(_BidirectionalIterator,
1395    *                              _BidirectionalIterator)
1396    *  overloaded for bidirectional iterators.
1397   */
1398   template<typename _BidirectionalIterator>
1399     void
1400     __reverse(_BidirectionalIterator __first, _BidirectionalIterator __last,
1401               bidirectional_iterator_tag)
1402     {
1403       while (true)
1404         if (__first == __last || __first == --__last)
1405           return;
1406         else
1407           {
1408             std::iter_swap(__first, __last);
1409             ++__first;
1410           }
1411     }
1412
1413   /**
1414    *  This is an uglified reverse(_BidirectionalIterator,
1415    *                              _BidirectionalIterator)
1416    *  overloaded for random access iterators.
1417   */
1418   template<typename _RandomAccessIterator>
1419     void
1420     __reverse(_RandomAccessIterator __first, _RandomAccessIterator __last,
1421               random_access_iterator_tag)
1422     {
1423       if (__first == __last)
1424         return;
1425       --__last;
1426       while (__first < __last)
1427         {
1428           std::iter_swap(__first, __last);
1429           ++__first;
1430           --__last;
1431         }
1432     }
1433
1434   /**
1435    *  @brief Reverse a sequence.
1436    *  @ingroup mutating_algorithms
1437    *  @param  __first  A bidirectional iterator.
1438    *  @param  __last   A bidirectional iterator.
1439    *  @return   reverse() returns no value.
1440    *
1441    *  Reverses the order of the elements in the range @p [__first,__last),
1442    *  so that the first element becomes the last etc.
1443    *  For every @c i such that @p 0<=i<=(__last-__first)/2), @p reverse()
1444    *  swaps @p *(__first+i) and @p *(__last-(i+1))
1445   */
1446   template<typename _BidirectionalIterator>
1447     inline void
1448     reverse(_BidirectionalIterator __first, _BidirectionalIterator __last)
1449     {
1450       // concept requirements
1451       __glibcxx_function_requires(_Mutable_BidirectionalIteratorConcept<
1452                                   _BidirectionalIterator>)
1453       __glibcxx_requires_valid_range(__first, __last);
1454       std::__reverse(__first, __last, std::__iterator_category(__first));
1455     }
1456
1457   /**
1458    *  @brief Copy a sequence, reversing its elements.
1459    *  @ingroup mutating_algorithms
1460    *  @param  __first   A bidirectional iterator.
1461    *  @param  __last    A bidirectional iterator.
1462    *  @param  __result  An output iterator.
1463    *  @return  An iterator designating the end of the resulting sequence.
1464    *
1465    *  Copies the elements in the range @p [__first,__last) to the
1466    *  range @p [__result,__result+(__last-__first)) such that the
1467    *  order of the elements is reversed.  For every @c i such that @p
1468    *  0<=i<=(__last-__first), @p reverse_copy() performs the
1469    *  assignment @p *(__result+(__last-__first)-i) = *(__first+i).
1470    *  The ranges @p [__first,__last) and @p
1471    *  [__result,__result+(__last-__first)) must not overlap.
1472   */
1473   template<typename _BidirectionalIterator, typename _OutputIterator>
1474     _OutputIterator
1475     reverse_copy(_BidirectionalIterator __first, _BidirectionalIterator __last,
1476                  _OutputIterator __result)
1477     {
1478       // concept requirements
1479       __glibcxx_function_requires(_BidirectionalIteratorConcept<
1480                                   _BidirectionalIterator>)
1481       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
1482                 typename iterator_traits<_BidirectionalIterator>::value_type>)
1483       __glibcxx_requires_valid_range(__first, __last);
1484
1485       while (__first != __last)
1486         {
1487           --__last;
1488           *__result = *__last;
1489           ++__result;
1490         }
1491       return __result;
1492     }
1493
1494   /**
1495    *  This is a helper function for the rotate algorithm specialized on RAIs.
1496    *  It returns the greatest common divisor of two integer values.
1497   */
1498   template<typename _EuclideanRingElement>
1499     _EuclideanRingElement
1500     __gcd(_EuclideanRingElement __m, _EuclideanRingElement __n)
1501     {
1502       while (__n != 0)
1503         {
1504           _EuclideanRingElement __t = __m % __n;
1505           __m = __n;
1506           __n = __t;
1507         }
1508       return __m;
1509     }
1510
1511   /// This is a helper function for the rotate algorithm.
1512   template<typename _ForwardIterator>
1513     void
1514     __rotate(_ForwardIterator __first,
1515              _ForwardIterator __middle,
1516              _ForwardIterator __last,
1517              forward_iterator_tag)
1518     {
1519       if (__first == __middle || __last  == __middle)
1520         return;
1521
1522       _ForwardIterator __first2 = __middle;
1523       do
1524         {
1525           std::iter_swap(__first, __first2);
1526           ++__first;
1527           ++__first2;
1528           if (__first == __middle)
1529             __middle = __first2;
1530         }
1531       while (__first2 != __last);
1532
1533       __first2 = __middle;
1534
1535       while (__first2 != __last)
1536         {
1537           std::iter_swap(__first, __first2);
1538           ++__first;
1539           ++__first2;
1540           if (__first == __middle)
1541             __middle = __first2;
1542           else if (__first2 == __last)
1543             __first2 = __middle;
1544         }
1545     }
1546
1547    /// This is a helper function for the rotate algorithm.
1548   template<typename _BidirectionalIterator>
1549     void
1550     __rotate(_BidirectionalIterator __first,
1551              _BidirectionalIterator __middle,
1552              _BidirectionalIterator __last,
1553               bidirectional_iterator_tag)
1554     {
1555       // concept requirements
1556       __glibcxx_function_requires(_Mutable_BidirectionalIteratorConcept<
1557                                   _BidirectionalIterator>)
1558
1559       if (__first == __middle || __last  == __middle)
1560         return;
1561
1562       std::__reverse(__first,  __middle, bidirectional_iterator_tag());
1563       std::__reverse(__middle, __last,   bidirectional_iterator_tag());
1564
1565       while (__first != __middle && __middle != __last)
1566         {
1567           std::iter_swap(__first, --__last);
1568           ++__first;
1569         }
1570
1571       if (__first == __middle)
1572         std::__reverse(__middle, __last,   bidirectional_iterator_tag());
1573       else
1574         std::__reverse(__first,  __middle, bidirectional_iterator_tag());
1575     }
1576
1577   /// This is a helper function for the rotate algorithm.
1578   template<typename _RandomAccessIterator>
1579     void
1580     __rotate(_RandomAccessIterator __first,
1581              _RandomAccessIterator __middle,
1582              _RandomAccessIterator __last,
1583              random_access_iterator_tag)
1584     {
1585       // concept requirements
1586       __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
1587                                   _RandomAccessIterator>)
1588
1589       if (__first == __middle || __last  == __middle)
1590         return;
1591
1592       typedef typename iterator_traits<_RandomAccessIterator>::difference_type
1593         _Distance;
1594       typedef typename iterator_traits<_RandomAccessIterator>::value_type
1595         _ValueType;
1596
1597       _Distance __n = __last   - __first;
1598       _Distance __k = __middle - __first;
1599
1600       if (__k == __n - __k)
1601         {
1602           std::swap_ranges(__first, __middle, __middle);
1603           return;
1604         }
1605
1606       _RandomAccessIterator __p = __first;
1607
1608       for (;;)
1609         {
1610           if (__k < __n - __k)
1611             {
1612               if (__is_pod(_ValueType) && __k == 1)
1613                 {
1614                   _ValueType __t = _GLIBCXX_MOVE(*__p);
1615                   _GLIBCXX_MOVE3(__p + 1, __p + __n, __p);
1616                   *(__p + __n - 1) = _GLIBCXX_MOVE(__t);
1617                   return;
1618                 }
1619               _RandomAccessIterator __q = __p + __k;
1620               for (_Distance __i = 0; __i < __n - __k; ++ __i)
1621                 {
1622                   std::iter_swap(__p, __q);
1623                   ++__p;
1624                   ++__q;
1625                 }
1626               __n %= __k;
1627               if (__n == 0)
1628                 return;
1629               std::swap(__n, __k);
1630               __k = __n - __k;
1631             }
1632           else
1633             {
1634               __k = __n - __k;
1635               if (__is_pod(_ValueType) && __k == 1)
1636                 {
1637                   _ValueType __t = _GLIBCXX_MOVE(*(__p + __n - 1));
1638                   _GLIBCXX_MOVE_BACKWARD3(__p, __p + __n - 1, __p + __n);
1639                   *__p = _GLIBCXX_MOVE(__t);
1640                   return;
1641                 }
1642               _RandomAccessIterator __q = __p + __n;
1643               __p = __q - __k;
1644               for (_Distance __i = 0; __i < __n - __k; ++ __i)
1645                 {
1646                   --__p;
1647                   --__q;
1648                   std::iter_swap(__p, __q);
1649                 }
1650               __n %= __k;
1651               if (__n == 0)
1652                 return;
1653               std::swap(__n, __k);
1654             }
1655         }
1656     }
1657
1658   /**
1659    *  @brief Rotate the elements of a sequence.
1660    *  @ingroup mutating_algorithms
1661    *  @param  __first   A forward iterator.
1662    *  @param  __middle  A forward iterator.
1663    *  @param  __last    A forward iterator.
1664    *  @return  Nothing.
1665    *
1666    *  Rotates the elements of the range @p [__first,__last) by
1667    *  @p(__middle - __first) positions so that the element at @p __middle
1668    *  is moved to @p __first, the element at @p __middle+1 is moved to
1669    *  @ __first+1 and so on for each element in the range
1670    *  @p [__first,__last).
1671    *
1672    *  This effectively swaps the ranges @p [__first,__middle) and
1673    *  @p [__middle,__last).
1674    *
1675    *  Performs
1676    *   @p *(__first+(n+(__last-__middle))%(__last-__first))=*(__first+n)
1677    *  for each @p n in the range @p [0,__last-__first).
1678   */
1679   template<typename _ForwardIterator>
1680     inline void
1681     rotate(_ForwardIterator __first, _ForwardIterator __middle,
1682            _ForwardIterator __last)
1683     {
1684       // concept requirements
1685       __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
1686                                   _ForwardIterator>)
1687       __glibcxx_requires_valid_range(__first, __middle);
1688       __glibcxx_requires_valid_range(__middle, __last);
1689
1690       typedef typename iterator_traits<_ForwardIterator>::iterator_category
1691         _IterType;
1692       std::__rotate(__first, __middle, __last, _IterType());
1693     }
1694
1695   /**
1696    *  @brief Copy a sequence, rotating its elements.
1697    *  @ingroup mutating_algorithms
1698    *  @param  __first   A forward iterator.
1699    *  @param  __middle  A forward iterator.
1700    *  @param  __last    A forward iterator.
1701    *  @param  __result  An output iterator.
1702    *  @return   An iterator designating the end of the resulting sequence.
1703    *
1704    *  Copies the elements of the range @p [__first,__last) to the
1705    *  range beginning at @result, rotating the copied elements by
1706    *  @p (__middle-__first) positions so that the element at @p __middle
1707    *  is moved to @p __result, the element at @p __middle+1 is moved
1708    *  to @__result+1 and so on for each element in the range @p
1709    *  [__first,__last).
1710    *
1711    *  Performs
1712    *  @p *(__result+(n+(__last-__middle))%(__last-__first))=*(__first+n)
1713    *  for each @p n in the range @p [0,__last-__first).
1714   */
1715   template<typename _ForwardIterator, typename _OutputIterator>
1716     _OutputIterator
1717     rotate_copy(_ForwardIterator __first, _ForwardIterator __middle,
1718                 _ForwardIterator __last, _OutputIterator __result)
1719     {
1720       // concept requirements
1721       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
1722       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
1723                 typename iterator_traits<_ForwardIterator>::value_type>)
1724       __glibcxx_requires_valid_range(__first, __middle);
1725       __glibcxx_requires_valid_range(__middle, __last);
1726
1727       return std::copy(__first, __middle,
1728                        std::copy(__middle, __last, __result));
1729     }
1730
1731   /// This is a helper function...
1732   template<typename _ForwardIterator, typename _Predicate>
1733     _ForwardIterator
1734     __partition(_ForwardIterator __first, _ForwardIterator __last,
1735                 _Predicate __pred, forward_iterator_tag)
1736     {
1737       if (__first == __last)
1738         return __first;
1739
1740       while (__pred(*__first))
1741         if (++__first == __last)
1742           return __first;
1743
1744       _ForwardIterator __next = __first;
1745
1746       while (++__next != __last)
1747         if (__pred(*__next))
1748           {
1749             std::iter_swap(__first, __next);
1750             ++__first;
1751           }
1752
1753       return __first;
1754     }
1755
1756   /// This is a helper function...
1757   template<typename _BidirectionalIterator, typename _Predicate>
1758     _BidirectionalIterator
1759     __partition(_BidirectionalIterator __first, _BidirectionalIterator __last,
1760                 _Predicate __pred, bidirectional_iterator_tag)
1761     {
1762       while (true)
1763         {
1764           while (true)
1765             if (__first == __last)
1766               return __first;
1767             else if (__pred(*__first))
1768               ++__first;
1769             else
1770               break;
1771           --__last;
1772           while (true)
1773             if (__first == __last)
1774               return __first;
1775             else if (!bool(__pred(*__last)))
1776               --__last;
1777             else
1778               break;
1779           std::iter_swap(__first, __last);
1780           ++__first;
1781         }
1782     }
1783
1784   // partition
1785
1786   /// This is a helper function...
1787   template<typename _ForwardIterator, typename _Predicate, typename _Distance>
1788     _ForwardIterator
1789     __inplace_stable_partition(_ForwardIterator __first,
1790                                _ForwardIterator __last,
1791                                _Predicate __pred, _Distance __len)
1792     {
1793       if (__len == 1)
1794         return __pred(*__first) ? __last : __first;
1795       _ForwardIterator __middle = __first;
1796       std::advance(__middle, __len / 2);
1797       _ForwardIterator __begin = std::__inplace_stable_partition(__first,
1798                                                                  __middle,
1799                                                                  __pred,
1800                                                                  __len / 2);
1801       _ForwardIterator __end = std::__inplace_stable_partition(__middle, __last,
1802                                                                __pred,
1803                                                                __len
1804                                                                - __len / 2);
1805       std::rotate(__begin, __middle, __end);
1806       std::advance(__begin, std::distance(__middle, __end));
1807       return __begin;
1808     }
1809
1810   /// This is a helper function...
1811   template<typename _ForwardIterator, typename _Pointer, typename _Predicate,
1812            typename _Distance>
1813     _ForwardIterator
1814     __stable_partition_adaptive(_ForwardIterator __first,
1815                                 _ForwardIterator __last,
1816                                 _Predicate __pred, _Distance __len,
1817                                 _Pointer __buffer,
1818                                 _Distance __buffer_size)
1819     {
1820       if (__len <= __buffer_size)
1821         {
1822           _ForwardIterator __result1 = __first;
1823           _Pointer __result2 = __buffer;
1824           for (; __first != __last; ++__first)
1825             if (__pred(*__first))
1826               {
1827                 *__result1 = _GLIBCXX_MOVE(*__first);
1828                 ++__result1;
1829               }
1830             else
1831               {
1832                 *__result2 = _GLIBCXX_MOVE(*__first);
1833                 ++__result2;
1834               }
1835           _GLIBCXX_MOVE3(__buffer, __result2, __result1);
1836           return __result1;
1837         }
1838       else
1839         {
1840           _ForwardIterator __middle = __first;
1841           std::advance(__middle, __len / 2);
1842           _ForwardIterator __begin =
1843             std::__stable_partition_adaptive(__first, __middle, __pred,
1844                                              __len / 2, __buffer,
1845                                              __buffer_size);
1846           _ForwardIterator __end =
1847             std::__stable_partition_adaptive(__middle, __last, __pred,
1848                                              __len - __len / 2,
1849                                              __buffer, __buffer_size);
1850           std::rotate(__begin, __middle, __end);
1851           std::advance(__begin, std::distance(__middle, __end));
1852           return __begin;
1853         }
1854     }
1855
1856   /**
1857    *  @brief Move elements for which a predicate is true to the beginning
1858    *         of a sequence, preserving relative ordering.
1859    *  @ingroup mutating_algorithms
1860    *  @param  __first   A forward iterator.
1861    *  @param  __last    A forward iterator.
1862    *  @param  __pred    A predicate functor.
1863    *  @return  An iterator @p middle such that @p __pred(i) is true for each
1864    *  iterator @p i in the range @p [first,middle) and false for each @p i
1865    *  in the range @p [middle,last).
1866    *
1867    *  Performs the same function as @p partition() with the additional
1868    *  guarantee that the relative ordering of elements in each group is
1869    *  preserved, so any two elements @p x and @p y in the range
1870    *  @p [__first,__last) such that @p __pred(x)==__pred(y) will have the same
1871    *  relative ordering after calling @p stable_partition().
1872   */
1873   template<typename _ForwardIterator, typename _Predicate>
1874     _ForwardIterator
1875     stable_partition(_ForwardIterator __first, _ForwardIterator __last,
1876                      _Predicate __pred)
1877     {
1878       // concept requirements
1879       __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
1880                                   _ForwardIterator>)
1881       __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
1882             typename iterator_traits<_ForwardIterator>::value_type>)
1883       __glibcxx_requires_valid_range(__first, __last);
1884
1885       if (__first == __last)
1886         return __first;
1887       else
1888         {
1889           typedef typename iterator_traits<_ForwardIterator>::value_type
1890             _ValueType;
1891           typedef typename iterator_traits<_ForwardIterator>::difference_type
1892             _DistanceType;
1893
1894           _Temporary_buffer<_ForwardIterator, _ValueType> __buf(__first,
1895                                                                 __last);
1896         if (__buf.size() > 0)
1897           return
1898             std::__stable_partition_adaptive(__first, __last, __pred,
1899                                           _DistanceType(__buf.requested_size()),
1900                                           __buf.begin(),
1901                                           _DistanceType(__buf.size()));
1902         else
1903           return
1904             std::__inplace_stable_partition(__first, __last, __pred,
1905                                          _DistanceType(__buf.requested_size()));
1906         }
1907     }
1908
1909   /// This is a helper function for the sort routines.
1910   template<typename _RandomAccessIterator>
1911     void
1912     __heap_select(_RandomAccessIterator __first,
1913                   _RandomAccessIterator __middle,
1914                   _RandomAccessIterator __last)
1915     {
1916       std::make_heap(__first, __middle);
1917       for (_RandomAccessIterator __i = __middle; __i < __last; ++__i)
1918         if (*__i < *__first)
1919           std::__pop_heap(__first, __middle, __i);
1920     }
1921
1922   /// This is a helper function for the sort routines.
1923   template<typename _RandomAccessIterator, typename _Compare>
1924     void
1925     __heap_select(_RandomAccessIterator __first,
1926                   _RandomAccessIterator __middle,
1927                   _RandomAccessIterator __last, _Compare __comp)
1928     {
1929       std::make_heap(__first, __middle, __comp);
1930       for (_RandomAccessIterator __i = __middle; __i < __last; ++__i)
1931         if (__comp(*__i, *__first))
1932           std::__pop_heap(__first, __middle, __i, __comp);
1933     }
1934
1935   // partial_sort
1936
1937   /**
1938    *  @brief Copy the smallest elements of a sequence.
1939    *  @ingroup sorting_algorithms
1940    *  @param  __first   An iterator.
1941    *  @param  __last    Another iterator.
1942    *  @param  __result_first   A random-access iterator.
1943    *  @param  __result_last    Another random-access iterator.
1944    *  @return   An iterator indicating the end of the resulting sequence.
1945    *
1946    *  Copies and sorts the smallest N values from the range @p [__first,__last)
1947    *  to the range beginning at @p __result_first, where the number of
1948    *  elements to be copied, @p N, is the smaller of @p (__last-__first) and
1949    *  @p (__result_last-__result_first).
1950    *  After the sort if @p i and @j are iterators in the range
1951    *  @p [__result_first,__result_first+N) such that @i precedes @j then
1952    *  @p *j<*i is false.
1953    *  The value returned is @p __result_first+N.
1954   */
1955   template<typename _InputIterator, typename _RandomAccessIterator>
1956     _RandomAccessIterator
1957     partial_sort_copy(_InputIterator __first, _InputIterator __last,
1958                       _RandomAccessIterator __result_first,
1959                       _RandomAccessIterator __result_last)
1960     {
1961       typedef typename iterator_traits<_InputIterator>::value_type
1962         _InputValueType;
1963       typedef typename iterator_traits<_RandomAccessIterator>::value_type
1964         _OutputValueType;
1965       typedef typename iterator_traits<_RandomAccessIterator>::difference_type
1966         _DistanceType;
1967
1968       // concept requirements
1969       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
1970       __glibcxx_function_requires(_ConvertibleConcept<_InputValueType,
1971                                   _OutputValueType>)
1972       __glibcxx_function_requires(_LessThanOpConcept<_InputValueType,
1973                                                      _OutputValueType>)
1974       __glibcxx_function_requires(_LessThanComparableConcept<_OutputValueType>)
1975       __glibcxx_requires_valid_range(__first, __last);
1976       __glibcxx_requires_valid_range(__result_first, __result_last);
1977
1978       if (__result_first == __result_last)
1979         return __result_last;
1980       _RandomAccessIterator __result_real_last = __result_first;
1981       while(__first != __last && __result_real_last != __result_last)
1982         {
1983           *__result_real_last = *__first;
1984           ++__result_real_last;
1985           ++__first;
1986         }
1987       std::make_heap(__result_first, __result_real_last);
1988       while (__first != __last)
1989         {
1990           if (*__first < *__result_first)
1991             std::__adjust_heap(__result_first, _DistanceType(0),
1992                                _DistanceType(__result_real_last
1993                                              - __result_first),
1994                                _InputValueType(*__first));
1995           ++__first;
1996         }
1997       std::sort_heap(__result_first, __result_real_last);
1998       return __result_real_last;
1999     }
2000
2001   /**
2002    *  @brief Copy the smallest elements of a sequence using a predicate for
2003    *         comparison.
2004    *  @ingroup sorting_algorithms
2005    *  @param  __first   An input iterator.
2006    *  @param  __last    Another input iterator.
2007    *  @param  __result_first   A random-access iterator.
2008    *  @param  __result_last    Another random-access iterator.
2009    *  @param  __comp    A comparison functor.
2010    *  @return   An iterator indicating the end of the resulting sequence.
2011    *
2012    *  Copies and sorts the smallest N values from the range @p [__first,__last)
2013    *  to the range beginning at @p result_first, where the number of
2014    *  elements to be copied, @p N, is the smaller of @p (__last-__first) and
2015    *  @p (__result_last-__result_first).
2016    *  After the sort if @p i and @j are iterators in the range
2017    *  @p [__result_first,__result_first+N) such that @i precedes @j then
2018    *  @p __comp(*j,*i) is false.
2019    *  The value returned is @p __result_first+N.
2020   */
2021   template<typename _InputIterator, typename _RandomAccessIterator, typename _Compare>
2022     _RandomAccessIterator
2023     partial_sort_copy(_InputIterator __first, _InputIterator __last,
2024                       _RandomAccessIterator __result_first,
2025                       _RandomAccessIterator __result_last,
2026                       _Compare __comp)
2027     {
2028       typedef typename iterator_traits<_InputIterator>::value_type
2029         _InputValueType;
2030       typedef typename iterator_traits<_RandomAccessIterator>::value_type
2031         _OutputValueType;
2032       typedef typename iterator_traits<_RandomAccessIterator>::difference_type
2033         _DistanceType;
2034
2035       // concept requirements
2036       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
2037       __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
2038                                   _RandomAccessIterator>)
2039       __glibcxx_function_requires(_ConvertibleConcept<_InputValueType,
2040                                   _OutputValueType>)
2041       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2042                                   _InputValueType, _OutputValueType>)
2043       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2044                                   _OutputValueType, _OutputValueType>)
2045       __glibcxx_requires_valid_range(__first, __last);
2046       __glibcxx_requires_valid_range(__result_first, __result_last);
2047
2048       if (__result_first == __result_last)
2049         return __result_last;
2050       _RandomAccessIterator __result_real_last = __result_first;
2051       while(__first != __last && __result_real_last != __result_last)
2052         {
2053           *__result_real_last = *__first;
2054           ++__result_real_last;
2055           ++__first;
2056         }
2057       std::make_heap(__result_first, __result_real_last, __comp);
2058       while (__first != __last)
2059         {
2060           if (__comp(*__first, *__result_first))
2061             std::__adjust_heap(__result_first, _DistanceType(0),
2062                                _DistanceType(__result_real_last
2063                                              - __result_first),
2064                                _InputValueType(*__first),
2065                                __comp);
2066           ++__first;
2067         }
2068       std::sort_heap(__result_first, __result_real_last, __comp);
2069       return __result_real_last;
2070     }
2071
2072   /// This is a helper function for the sort routine.
2073   template<typename _RandomAccessIterator>
2074     void
2075     __unguarded_linear_insert(_RandomAccessIterator __last)
2076     {
2077       typename iterator_traits<_RandomAccessIterator>::value_type
2078         __val = _GLIBCXX_MOVE(*__last);
2079       _RandomAccessIterator __next = __last;
2080       --__next;
2081       while (__val < *__next)
2082         {
2083           *__last = _GLIBCXX_MOVE(*__next);
2084           __last = __next;
2085           --__next;
2086         }
2087       *__last = _GLIBCXX_MOVE(__val);
2088     }
2089
2090   /// This is a helper function for the sort routine.
2091   template<typename _RandomAccessIterator, typename _Compare>
2092     void
2093     __unguarded_linear_insert(_RandomAccessIterator __last,
2094                               _Compare __comp)
2095     {
2096       typename iterator_traits<_RandomAccessIterator>::value_type
2097         __val = _GLIBCXX_MOVE(*__last);
2098       _RandomAccessIterator __next = __last;
2099       --__next;
2100       while (__comp(__val, *__next))
2101         {
2102           *__last = _GLIBCXX_MOVE(*__next);
2103           __last = __next;
2104           --__next;
2105         }
2106       *__last = _GLIBCXX_MOVE(__val);
2107     }
2108
2109   /// This is a helper function for the sort routine.
2110   template<typename _RandomAccessIterator>
2111     void
2112     __insertion_sort(_RandomAccessIterator __first,
2113                      _RandomAccessIterator __last)
2114     {
2115       if (__first == __last)
2116         return;
2117
2118       for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i)
2119         {
2120           if (*__i < *__first)
2121             {
2122               typename iterator_traits<_RandomAccessIterator>::value_type
2123                 __val = _GLIBCXX_MOVE(*__i);
2124               _GLIBCXX_MOVE_BACKWARD3(__first, __i, __i + 1);
2125               *__first = _GLIBCXX_MOVE(__val);
2126             }
2127           else
2128             std::__unguarded_linear_insert(__i);
2129         }
2130     }
2131
2132   /// This is a helper function for the sort routine.
2133   template<typename _RandomAccessIterator, typename _Compare>
2134     void
2135     __insertion_sort(_RandomAccessIterator __first,
2136                      _RandomAccessIterator __last, _Compare __comp)
2137     {
2138       if (__first == __last) return;
2139
2140       for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i)
2141         {
2142           if (__comp(*__i, *__first))
2143             {
2144               typename iterator_traits<_RandomAccessIterator>::value_type
2145                 __val = _GLIBCXX_MOVE(*__i);
2146               _GLIBCXX_MOVE_BACKWARD3(__first, __i, __i + 1);
2147               *__first = _GLIBCXX_MOVE(__val);
2148             }
2149           else
2150             std::__unguarded_linear_insert(__i, __comp);
2151         }
2152     }
2153
2154   /// This is a helper function for the sort routine.
2155   template<typename _RandomAccessIterator>
2156     inline void
2157     __unguarded_insertion_sort(_RandomAccessIterator __first,
2158                                _RandomAccessIterator __last)
2159     {
2160       typedef typename iterator_traits<_RandomAccessIterator>::value_type
2161         _ValueType;
2162
2163       for (_RandomAccessIterator __i = __first; __i != __last; ++__i)
2164         std::__unguarded_linear_insert(__i);
2165     }
2166
2167   /// This is a helper function for the sort routine.
2168   template<typename _RandomAccessIterator, typename _Compare>
2169     inline void
2170     __unguarded_insertion_sort(_RandomAccessIterator __first,
2171                                _RandomAccessIterator __last, _Compare __comp)
2172     {
2173       typedef typename iterator_traits<_RandomAccessIterator>::value_type
2174         _ValueType;
2175
2176       for (_RandomAccessIterator __i = __first; __i != __last; ++__i)
2177         std::__unguarded_linear_insert(__i, __comp);
2178     }
2179
2180   /**
2181    *  @doctodo
2182    *  This controls some aspect of the sort routines.
2183   */
2184   enum { _S_threshold = 16 };
2185
2186   /// This is a helper function for the sort routine.
2187   template<typename _RandomAccessIterator>
2188     void
2189     __final_insertion_sort(_RandomAccessIterator __first,
2190                            _RandomAccessIterator __last)
2191     {
2192       if (__last - __first > int(_S_threshold))
2193         {
2194           std::__insertion_sort(__first, __first + int(_S_threshold));
2195           std::__unguarded_insertion_sort(__first + int(_S_threshold), __last);
2196         }
2197       else
2198         std::__insertion_sort(__first, __last);
2199     }
2200
2201   /// This is a helper function for the sort routine.
2202   template<typename _RandomAccessIterator, typename _Compare>
2203     void
2204     __final_insertion_sort(_RandomAccessIterator __first,
2205                            _RandomAccessIterator __last, _Compare __comp)
2206     {
2207       if (__last - __first > int(_S_threshold))
2208         {
2209           std::__insertion_sort(__first, __first + int(_S_threshold), __comp);
2210           std::__unguarded_insertion_sort(__first + int(_S_threshold), __last,
2211                                           __comp);
2212         }
2213       else
2214         std::__insertion_sort(__first, __last, __comp);
2215     }
2216
2217   /// This is a helper function...
2218   template<typename _RandomAccessIterator, typename _Tp>
2219     _RandomAccessIterator
2220     __unguarded_partition(_RandomAccessIterator __first,
2221                           _RandomAccessIterator __last, const _Tp& __pivot)
2222     {
2223       while (true)
2224         {
2225           while (*__first < __pivot)
2226             ++__first;
2227           --__last;
2228           while (__pivot < *__last)
2229             --__last;
2230           if (!(__first < __last))
2231             return __first;
2232           std::iter_swap(__first, __last);
2233           ++__first;
2234         }
2235     }
2236
2237   /// This is a helper function...
2238   template<typename _RandomAccessIterator, typename _Tp, typename _Compare>
2239     _RandomAccessIterator
2240     __unguarded_partition(_RandomAccessIterator __first,
2241                           _RandomAccessIterator __last,
2242                           const _Tp& __pivot, _Compare __comp)
2243     {
2244       while (true)
2245         {
2246           while (__comp(*__first, __pivot))
2247             ++__first;
2248           --__last;
2249           while (__comp(__pivot, *__last))
2250             --__last;
2251           if (!(__first < __last))
2252             return __first;
2253           std::iter_swap(__first, __last);
2254           ++__first;
2255         }
2256     }
2257
2258   /// This is a helper function...
2259   template<typename _RandomAccessIterator>
2260     inline _RandomAccessIterator
2261     __unguarded_partition_pivot(_RandomAccessIterator __first,
2262                                 _RandomAccessIterator __last)
2263     {
2264       _RandomAccessIterator __mid = __first + (__last - __first) / 2;
2265       std::__move_median_first(__first, __mid, (__last - 1));
2266       return std::__unguarded_partition(__first + 1, __last, *__first);
2267     }
2268
2269
2270   /// This is a helper function...
2271   template<typename _RandomAccessIterator, typename _Compare>
2272     inline _RandomAccessIterator
2273     __unguarded_partition_pivot(_RandomAccessIterator __first,
2274                                 _RandomAccessIterator __last, _Compare __comp)
2275     {
2276       _RandomAccessIterator __mid = __first + (__last - __first) / 2;
2277       std::__move_median_first(__first, __mid, (__last - 1), __comp);
2278       return std::__unguarded_partition(__first + 1, __last, *__first, __comp);
2279     }
2280
2281   /// This is a helper function for the sort routine.
2282   template<typename _RandomAccessIterator, typename _Size>
2283     void
2284     __introsort_loop(_RandomAccessIterator __first,
2285                      _RandomAccessIterator __last,
2286                      _Size __depth_limit)
2287     {
2288       while (__last - __first > int(_S_threshold))
2289         {
2290           if (__depth_limit == 0)
2291             {
2292               _GLIBCXX_STD_A::partial_sort(__first, __last, __last);
2293               return;
2294             }
2295           --__depth_limit;
2296           _RandomAccessIterator __cut =
2297             std::__unguarded_partition_pivot(__first, __last);
2298           std::__introsort_loop(__cut, __last, __depth_limit);
2299           __last = __cut;
2300         }
2301     }
2302
2303   /// This is a helper function for the sort routine.
2304   template<typename _RandomAccessIterator, typename _Size, typename _Compare>
2305     void
2306     __introsort_loop(_RandomAccessIterator __first,
2307                      _RandomAccessIterator __last,
2308                      _Size __depth_limit, _Compare __comp)
2309     {
2310       while (__last - __first > int(_S_threshold))
2311         {
2312           if (__depth_limit == 0)
2313             {
2314               _GLIBCXX_STD_A::partial_sort(__first, __last, __last, __comp);
2315               return;
2316             }
2317           --__depth_limit;
2318           _RandomAccessIterator __cut =
2319             std::__unguarded_partition_pivot(__first, __last, __comp);
2320           std::__introsort_loop(__cut, __last, __depth_limit, __comp);
2321           __last = __cut;
2322         }
2323     }
2324
2325   // sort
2326
2327   template<typename _RandomAccessIterator, typename _Size>
2328     void
2329     __introselect(_RandomAccessIterator __first, _RandomAccessIterator __nth,
2330                   _RandomAccessIterator __last, _Size __depth_limit)
2331     {
2332       typedef typename iterator_traits<_RandomAccessIterator>::value_type
2333         _ValueType;
2334
2335       while (__last - __first > 3)
2336         {
2337           if (__depth_limit == 0)
2338             {
2339               std::__heap_select(__first, __nth + 1, __last);
2340
2341               // Place the nth largest element in its final position.
2342               std::iter_swap(__first, __nth);
2343               return;
2344             }
2345           --__depth_limit;
2346           _RandomAccessIterator __cut =
2347             std::__unguarded_partition_pivot(__first, __last);
2348           if (__cut <= __nth)
2349             __first = __cut;
2350           else
2351             __last = __cut;
2352         }
2353       std::__insertion_sort(__first, __last);
2354     }
2355
2356   template<typename _RandomAccessIterator, typename _Size, typename _Compare>
2357     void
2358     __introselect(_RandomAccessIterator __first, _RandomAccessIterator __nth,
2359                   _RandomAccessIterator __last, _Size __depth_limit,
2360                   _Compare __comp)
2361     {
2362       typedef typename iterator_traits<_RandomAccessIterator>::value_type
2363         _ValueType;
2364
2365       while (__last - __first > 3)
2366         {
2367           if (__depth_limit == 0)
2368             {
2369               std::__heap_select(__first, __nth + 1, __last, __comp);
2370               // Place the nth largest element in its final position.
2371               std::iter_swap(__first, __nth);
2372               return;
2373             }
2374           --__depth_limit;
2375           _RandomAccessIterator __cut =
2376             std::__unguarded_partition_pivot(__first, __last, __comp);
2377           if (__cut <= __nth)
2378             __first = __cut;
2379           else
2380             __last = __cut;
2381         }
2382       std::__insertion_sort(__first, __last, __comp);
2383     }
2384
2385   // nth_element
2386
2387   // lower_bound moved to stl_algobase.h
2388
2389   /**
2390    *  @brief Finds the first position in which @a val could be inserted
2391    *         without changing the ordering.
2392    *  @ingroup binary_search_algorithms
2393    *  @param  __first   An iterator.
2394    *  @param  __last    Another iterator.
2395    *  @param  __val     The search term.
2396    *  @param  __comp    A functor to use for comparisons.
2397    *  @return An iterator pointing to the first element <em>not less
2398    *           than</em> @a __val, or end() if every element is less
2399    *           than @a __val.
2400    *  @ingroup binary_search_algorithms
2401    *
2402    *  The comparison function should have the same effects on ordering as
2403    *  the function used for the initial sort.
2404   */
2405   template<typename _ForwardIterator, typename _Tp, typename _Compare>
2406     _ForwardIterator
2407     lower_bound(_ForwardIterator __first, _ForwardIterator __last,
2408                 const _Tp& __val, _Compare __comp)
2409     {
2410       typedef typename iterator_traits<_ForwardIterator>::value_type
2411         _ValueType;
2412       typedef typename iterator_traits<_ForwardIterator>::difference_type
2413         _DistanceType;
2414
2415       // concept requirements
2416       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
2417       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2418                                   _ValueType, _Tp>)
2419       __glibcxx_requires_partitioned_lower_pred(__first, __last,
2420                                                 __val, __comp);
2421
2422       _DistanceType __len = std::distance(__first, __last);
2423
2424       while (__len > 0)
2425         {
2426           _DistanceType __half = __len >> 1;
2427           _ForwardIterator __middle = __first;
2428           std::advance(__middle, __half);
2429           if (__comp(*__middle, __val))
2430             {
2431               __first = __middle;
2432               ++__first;
2433               __len = __len - __half - 1;
2434             }
2435           else
2436             __len = __half;
2437         }
2438       return __first;
2439     }
2440
2441   /**
2442    *  @brief Finds the last position in which @a val could be inserted
2443    *         without changing the ordering.
2444    *  @ingroup binary_search_algorithms
2445    *  @param  __first   An iterator.
2446    *  @param  __last    Another iterator.
2447    *  @param  __val     The search term.
2448    *  @return  An iterator pointing to the first element greater than @a __val,
2449    *           or end() if no elements are greater than @a __val.
2450    *  @ingroup binary_search_algorithms
2451   */
2452   template<typename _ForwardIterator, typename _Tp>
2453     _ForwardIterator
2454     upper_bound(_ForwardIterator __first, _ForwardIterator __last,
2455                 const _Tp& __val)
2456     {
2457       typedef typename iterator_traits<_ForwardIterator>::value_type
2458         _ValueType;
2459       typedef typename iterator_traits<_ForwardIterator>::difference_type
2460         _DistanceType;
2461
2462       // concept requirements
2463       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
2464       __glibcxx_function_requires(_LessThanOpConcept<_Tp, _ValueType>)
2465       __glibcxx_requires_partitioned_upper(__first, __last, __val);
2466
2467       _DistanceType __len = std::distance(__first, __last);
2468
2469       while (__len > 0)
2470         {
2471           _DistanceType __half = __len >> 1;
2472           _ForwardIterator __middle = __first;
2473           std::advance(__middle, __half);
2474           if (__val < *__middle)
2475             __len = __half;
2476           else
2477             {
2478               __first = __middle;
2479               ++__first;
2480               __len = __len - __half - 1;
2481             }
2482         }
2483       return __first;
2484     }
2485
2486   /**
2487    *  @brief Finds the last position in which @a val could be inserted
2488    *         without changing the ordering.
2489    *  @ingroup binary_search_algorithms
2490    *  @param  __first   An iterator.
2491    *  @param  __last    Another iterator.
2492    *  @param  __val     The search term.
2493    *  @param  __comp    A functor to use for comparisons.
2494    *  @return  An iterator pointing to the first element greater than @a __val,
2495    *           or end() if no elements are greater than @a __val.
2496    *  @ingroup binary_search_algorithms
2497    *
2498    *  The comparison function should have the same effects on ordering as
2499    *  the function used for the initial sort.
2500   */
2501   template<typename _ForwardIterator, typename _Tp, typename _Compare>
2502     _ForwardIterator
2503     upper_bound(_ForwardIterator __first, _ForwardIterator __last,
2504                 const _Tp& __val, _Compare __comp)
2505     {
2506       typedef typename iterator_traits<_ForwardIterator>::value_type
2507         _ValueType;
2508       typedef typename iterator_traits<_ForwardIterator>::difference_type
2509         _DistanceType;
2510
2511       // concept requirements
2512       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
2513       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2514                                   _Tp, _ValueType>)
2515       __glibcxx_requires_partitioned_upper_pred(__first, __last,
2516                                                 __val, __comp);
2517
2518       _DistanceType __len = std::distance(__first, __last);
2519
2520       while (__len > 0)
2521         {
2522           _DistanceType __half = __len >> 1;
2523           _ForwardIterator __middle = __first;
2524           std::advance(__middle, __half);
2525           if (__comp(__val, *__middle))
2526             __len = __half;
2527           else
2528             {
2529               __first = __middle;
2530               ++__first;
2531               __len = __len - __half - 1;
2532             }
2533         }
2534       return __first;
2535     }
2536
2537   /**
2538    *  @brief Finds the largest subrange in which @a val could be inserted
2539    *         at any place in it without changing the ordering.
2540    *  @ingroup binary_search_algorithms
2541    *  @param  __first   An iterator.
2542    *  @param  __last    Another iterator.
2543    *  @param  __val     The search term.
2544    *  @return  An pair of iterators defining the subrange.
2545    *  @ingroup binary_search_algorithms
2546    *
2547    *  This is equivalent to
2548    *  @code
2549    *    std::make_pair(lower_bound(__first, __last, __val),
2550    *                   upper_bound(__first, __last, __val))
2551    *  @endcode
2552    *  but does not actually call those functions.
2553   */
2554   template<typename _ForwardIterator, typename _Tp>
2555     pair<_ForwardIterator, _ForwardIterator>
2556     equal_range(_ForwardIterator __first, _ForwardIterator __last,
2557                 const _Tp& __val)
2558     {
2559       typedef typename iterator_traits<_ForwardIterator>::value_type
2560         _ValueType;
2561       typedef typename iterator_traits<_ForwardIterator>::difference_type
2562         _DistanceType;
2563
2564       // concept requirements
2565       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
2566       __glibcxx_function_requires(_LessThanOpConcept<_ValueType, _Tp>)
2567       __glibcxx_function_requires(_LessThanOpConcept<_Tp, _ValueType>)
2568       __glibcxx_requires_partitioned_lower(__first, __last, __val);
2569       __glibcxx_requires_partitioned_upper(__first, __last, __val);
2570
2571       _DistanceType __len = std::distance(__first, __last);
2572
2573       while (__len > 0)
2574         {
2575           _DistanceType __half = __len >> 1;
2576           _ForwardIterator __middle = __first;
2577           std::advance(__middle, __half);
2578           if (*__middle < __val)
2579             {
2580               __first = __middle;
2581               ++__first;
2582               __len = __len - __half - 1;
2583             }
2584           else if (__val < *__middle)
2585             __len = __half;
2586           else
2587             {
2588               _ForwardIterator __left = std::lower_bound(__first, __middle,
2589                                                          __val);
2590               std::advance(__first, __len);
2591               _ForwardIterator __right = std::upper_bound(++__middle, __first,
2592                                                           __val);
2593               return pair<_ForwardIterator, _ForwardIterator>(__left, __right);
2594             }
2595         }
2596       return pair<_ForwardIterator, _ForwardIterator>(__first, __first);
2597     }
2598
2599   /**
2600    *  @brief Finds the largest subrange in which @a val could be inserted
2601    *         at any place in it without changing the ordering.
2602    *  @param  __first   An iterator.
2603    *  @param  __last    Another iterator.
2604    *  @param  __val     The search term.
2605    *  @param  __comp    A functor to use for comparisons.
2606    *  @return  An pair of iterators defining the subrange.
2607    *  @ingroup binary_search_algorithms
2608    *
2609    *  This is equivalent to
2610    *  @code
2611    *    std::make_pair(lower_bound(__first, __last, __val, __comp),
2612    *                   upper_bound(__first, __last, __val, __comp))
2613    *  @endcode
2614    *  but does not actually call those functions.
2615   */
2616   template<typename _ForwardIterator, typename _Tp, typename _Compare>
2617     pair<_ForwardIterator, _ForwardIterator>
2618     equal_range(_ForwardIterator __first, _ForwardIterator __last,
2619                 const _Tp& __val, _Compare __comp)
2620     {
2621       typedef typename iterator_traits<_ForwardIterator>::value_type
2622         _ValueType;
2623       typedef typename iterator_traits<_ForwardIterator>::difference_type
2624         _DistanceType;
2625
2626       // concept requirements
2627       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
2628       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2629                                   _ValueType, _Tp>)
2630       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2631                                   _Tp, _ValueType>)
2632       __glibcxx_requires_partitioned_lower_pred(__first, __last,
2633                                                 __val, __comp);
2634       __glibcxx_requires_partitioned_upper_pred(__first, __last,
2635                                                 __val, __comp);
2636
2637       _DistanceType __len = std::distance(__first, __last);
2638
2639       while (__len > 0)
2640         {
2641           _DistanceType __half = __len >> 1;
2642           _ForwardIterator __middle = __first;
2643           std::advance(__middle, __half);
2644           if (__comp(*__middle, __val))
2645             {
2646               __first = __middle;
2647               ++__first;
2648               __len = __len - __half - 1;
2649             }
2650           else if (__comp(__val, *__middle))
2651             __len = __half;
2652           else
2653             {
2654               _ForwardIterator __left = std::lower_bound(__first, __middle,
2655                                                          __val, __comp);
2656               std::advance(__first, __len);
2657               _ForwardIterator __right = std::upper_bound(++__middle, __first,
2658                                                           __val, __comp);
2659               return pair<_ForwardIterator, _ForwardIterator>(__left, __right);
2660             }
2661         }
2662       return pair<_ForwardIterator, _ForwardIterator>(__first, __first);
2663     }
2664
2665   /**
2666    *  @brief Determines whether an element exists in a range.
2667    *  @ingroup binary_search_algorithms
2668    *  @param  __first   An iterator.
2669    *  @param  __last    Another iterator.
2670    *  @param  __val     The search term.
2671    *  @return True if @a __val (or its equivalent) is in [@a
2672    *  __first,@a __last ].
2673    *
2674    *  Note that this does not actually return an iterator to @a __val.  For
2675    *  that, use std::find or a container's specialized find member functions.
2676   */
2677   template<typename _ForwardIterator, typename _Tp>
2678     bool
2679     binary_search(_ForwardIterator __first, _ForwardIterator __last,
2680                   const _Tp& __val)
2681     {
2682       typedef typename iterator_traits<_ForwardIterator>::value_type
2683         _ValueType;
2684
2685       // concept requirements
2686       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
2687       __glibcxx_function_requires(_LessThanOpConcept<_Tp, _ValueType>)
2688       __glibcxx_requires_partitioned_lower(__first, __last, __val);
2689       __glibcxx_requires_partitioned_upper(__first, __last, __val);
2690
2691       _ForwardIterator __i = std::lower_bound(__first, __last, __val);
2692       return __i != __last && !(__val < *__i);
2693     }
2694
2695   /**
2696    *  @brief Determines whether an element exists in a range.
2697    *  @ingroup binary_search_algorithms
2698    *  @param  __first   An iterator.
2699    *  @param  __last    Another iterator.
2700    *  @param  __val     The search term.
2701    *  @param  __comp    A functor to use for comparisons.
2702    *  @return  True if @a val (or its equivalent) is in [@a first,@a last ].
2703    *
2704    *  Note that this does not actually return an iterator to @a val.  For
2705    *  that, use std::find or a container's specialized find member functions.
2706    *
2707    *  The comparison function should have the same effects on ordering as
2708    *  the function used for the initial sort.
2709   */
2710   template<typename _ForwardIterator, typename _Tp, typename _Compare>
2711     bool
2712     binary_search(_ForwardIterator __first, _ForwardIterator __last,
2713                   const _Tp& __val, _Compare __comp)
2714     {
2715       typedef typename iterator_traits<_ForwardIterator>::value_type
2716         _ValueType;
2717
2718       // concept requirements
2719       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
2720       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2721                                   _Tp, _ValueType>)
2722       __glibcxx_requires_partitioned_lower_pred(__first, __last,
2723                                                 __val, __comp);
2724       __glibcxx_requires_partitioned_upper_pred(__first, __last,
2725                                                 __val, __comp);
2726
2727       _ForwardIterator __i = std::lower_bound(__first, __last, __val, __comp);
2728       return __i != __last && !bool(__comp(__val, *__i));
2729     }
2730
2731   // merge
2732
2733   /// This is a helper function for the __merge_adaptive routines.
2734   template<typename _InputIterator1, typename _InputIterator2,
2735            typename _OutputIterator>
2736     void
2737     __move_merge_adaptive(_InputIterator1 __first1, _InputIterator1 __last1,
2738                           _InputIterator2 __first2, _InputIterator2 __last2,
2739                           _OutputIterator __result)
2740     {
2741       while (__first1 != __last1 && __first2 != __last2)
2742         {
2743           if (*__first2 < *__first1)
2744             {
2745               *__result = _GLIBCXX_MOVE(*__first2);
2746               ++__first2;
2747             }
2748           else
2749             {
2750               *__result = _GLIBCXX_MOVE(*__first1);
2751               ++__first1;
2752             }
2753           ++__result;
2754         }
2755       if (__first1 != __last1)
2756         _GLIBCXX_MOVE3(__first1, __last1, __result);
2757     }
2758
2759   /// This is a helper function for the __merge_adaptive routines.
2760   template<typename _InputIterator1, typename _InputIterator2,
2761            typename _OutputIterator, typename _Compare>
2762     void
2763     __move_merge_adaptive(_InputIterator1 __first1, _InputIterator1 __last1,
2764                           _InputIterator2 __first2, _InputIterator2 __last2,
2765                           _OutputIterator __result, _Compare __comp)
2766     {
2767       while (__first1 != __last1 && __first2 != __last2)
2768         {
2769           if (__comp(*__first2, *__first1))
2770             {
2771               *__result = _GLIBCXX_MOVE(*__first2);
2772               ++__first2;
2773             }
2774           else
2775             {
2776               *__result = _GLIBCXX_MOVE(*__first1);
2777               ++__first1;
2778             }
2779           ++__result;
2780         }
2781       if (__first1 != __last1)
2782         _GLIBCXX_MOVE3(__first1, __last1, __result);
2783     }
2784
2785   /// This is a helper function for the __merge_adaptive routines.
2786   template<typename _BidirectionalIterator1, typename _BidirectionalIterator2,
2787            typename _BidirectionalIterator3>
2788     void
2789     __move_merge_adaptive_backward(_BidirectionalIterator1 __first1,
2790                                    _BidirectionalIterator1 __last1,
2791                                    _BidirectionalIterator2 __first2,
2792                                    _BidirectionalIterator2 __last2,
2793                                    _BidirectionalIterator3 __result)
2794     {
2795       if (__first1 == __last1)
2796         {
2797           _GLIBCXX_MOVE_BACKWARD3(__first2, __last2, __result);
2798           return;
2799         }
2800       else if (__first2 == __last2)
2801         return;
2802
2803       --__last1;
2804       --__last2;
2805       while (true)
2806         {
2807           if (*__last2 < *__last1)
2808             {
2809               *--__result = _GLIBCXX_MOVE(*__last1);
2810               if (__first1 == __last1)
2811                 {
2812                   _GLIBCXX_MOVE_BACKWARD3(__first2, ++__last2, __result);
2813                   return;
2814                 }
2815               --__last1;
2816             }
2817           else
2818             {
2819               *--__result = _GLIBCXX_MOVE(*__last2);
2820               if (__first2 == __last2)
2821                 return;
2822               --__last2;
2823             }
2824         }
2825     }
2826
2827   /// This is a helper function for the __merge_adaptive routines.
2828   template<typename _BidirectionalIterator1, typename _BidirectionalIterator2,
2829            typename _BidirectionalIterator3, typename _Compare>
2830     void
2831     __move_merge_adaptive_backward(_BidirectionalIterator1 __first1,
2832                                    _BidirectionalIterator1 __last1,
2833                                    _BidirectionalIterator2 __first2,
2834                                    _BidirectionalIterator2 __last2,
2835                                    _BidirectionalIterator3 __result,
2836                                    _Compare __comp)
2837     {
2838       if (__first1 == __last1)
2839         {
2840           _GLIBCXX_MOVE_BACKWARD3(__first2, __last2, __result);
2841           return;
2842         }
2843       else if (__first2 == __last2)
2844         return;
2845
2846       --__last1;
2847       --__last2;
2848       while (true)
2849         {
2850           if (__comp(*__last2, *__last1))
2851             {
2852               *--__result = _GLIBCXX_MOVE(*__last1);
2853               if (__first1 == __last1)
2854                 {
2855                   _GLIBCXX_MOVE_BACKWARD3(__first2, ++__last2, __result);
2856                   return;
2857                 }
2858               --__last1;
2859             }
2860           else
2861             {
2862               *--__result = _GLIBCXX_MOVE(*__last2);
2863               if (__first2 == __last2)
2864                 return;
2865               --__last2;
2866             }
2867         }
2868     }
2869
2870   /// This is a helper function for the merge routines.
2871   template<typename _BidirectionalIterator1, typename _BidirectionalIterator2,
2872            typename _Distance>
2873     _BidirectionalIterator1
2874     __rotate_adaptive(_BidirectionalIterator1 __first,
2875                       _BidirectionalIterator1 __middle,
2876                       _BidirectionalIterator1 __last,
2877                       _Distance __len1, _Distance __len2,
2878                       _BidirectionalIterator2 __buffer,
2879                       _Distance __buffer_size)
2880     {
2881       _BidirectionalIterator2 __buffer_end;
2882       if (__len1 > __len2 && __len2 <= __buffer_size)
2883         {
2884           if (__len2)
2885             {
2886               __buffer_end = _GLIBCXX_MOVE3(__middle, __last, __buffer);
2887               _GLIBCXX_MOVE_BACKWARD3(__first, __middle, __last);
2888               return _GLIBCXX_MOVE3(__buffer, __buffer_end, __first);
2889             }
2890           else
2891             return __first;
2892         }
2893       else if (__len1 <= __buffer_size)
2894         {
2895           if (__len1)
2896             {
2897               __buffer_end = _GLIBCXX_MOVE3(__first, __middle, __buffer);
2898               _GLIBCXX_MOVE3(__middle, __last, __first);
2899               return _GLIBCXX_MOVE_BACKWARD3(__buffer, __buffer_end, __last);
2900             }
2901           else
2902             return __last;
2903         }
2904       else
2905         {
2906           std::rotate(__first, __middle, __last);
2907           std::advance(__first, std::distance(__middle, __last));
2908           return __first;
2909         }
2910     }
2911
2912   /// This is a helper function for the merge routines.
2913   template<typename _BidirectionalIterator, typename _Distance,
2914            typename _Pointer>
2915     void
2916     __merge_adaptive(_BidirectionalIterator __first,
2917                      _BidirectionalIterator __middle,
2918                      _BidirectionalIterator __last,
2919                      _Distance __len1, _Distance __len2,
2920                      _Pointer __buffer, _Distance __buffer_size)
2921     {
2922       if (__len1 <= __len2 && __len1 <= __buffer_size)
2923         {
2924           _Pointer __buffer_end = _GLIBCXX_MOVE3(__first, __middle, __buffer);
2925           std::__move_merge_adaptive(__buffer, __buffer_end, __middle, __last,
2926                                      __first);
2927         }
2928       else if (__len2 <= __buffer_size)
2929         {
2930           _Pointer __buffer_end = _GLIBCXX_MOVE3(__middle, __last, __buffer);
2931           std::__move_merge_adaptive_backward(__first, __middle, __buffer,
2932                                               __buffer_end, __last);
2933         }
2934       else
2935         {
2936           _BidirectionalIterator __first_cut = __first;
2937           _BidirectionalIterator __second_cut = __middle;
2938           _Distance __len11 = 0;
2939           _Distance __len22 = 0;
2940           if (__len1 > __len2)
2941             {
2942               __len11 = __len1 / 2;
2943               std::advance(__first_cut, __len11);
2944               __second_cut = std::lower_bound(__middle, __last,
2945                                               *__first_cut);
2946               __len22 = std::distance(__middle, __second_cut);
2947             }
2948           else
2949             {
2950               __len22 = __len2 / 2;
2951               std::advance(__second_cut, __len22);
2952               __first_cut = std::upper_bound(__first, __middle,
2953                                              *__second_cut);
2954               __len11 = std::distance(__first, __first_cut);
2955             }
2956           _BidirectionalIterator __new_middle =
2957             std::__rotate_adaptive(__first_cut, __middle, __second_cut,
2958                                    __len1 - __len11, __len22, __buffer,
2959                                    __buffer_size);
2960           std::__merge_adaptive(__first, __first_cut, __new_middle, __len11,
2961                                 __len22, __buffer, __buffer_size);
2962           std::__merge_adaptive(__new_middle, __second_cut, __last,
2963                                 __len1 - __len11,
2964                                 __len2 - __len22, __buffer, __buffer_size);
2965         }
2966     }
2967
2968   /// This is a helper function for the merge routines.
2969   template<typename _BidirectionalIterator, typename _Distance,
2970            typename _Pointer, typename _Compare>
2971     void
2972     __merge_adaptive(_BidirectionalIterator __first,
2973                      _BidirectionalIterator __middle,
2974                      _BidirectionalIterator __last,
2975                      _Distance __len1, _Distance __len2,
2976                      _Pointer __buffer, _Distance __buffer_size,
2977                      _Compare __comp)
2978     {
2979       if (__len1 <= __len2 && __len1 <= __buffer_size)
2980         {
2981           _Pointer __buffer_end = _GLIBCXX_MOVE3(__first, __middle, __buffer);
2982           std::__move_merge_adaptive(__buffer, __buffer_end, __middle, __last,
2983                                      __first, __comp);
2984         }
2985       else if (__len2 <= __buffer_size)
2986         {
2987           _Pointer __buffer_end = _GLIBCXX_MOVE3(__middle, __last, __buffer);
2988           std::__move_merge_adaptive_backward(__first, __middle, __buffer,
2989                                               __buffer_end, __last, __comp);
2990         }
2991       else
2992         {
2993           _BidirectionalIterator __first_cut = __first;
2994           _BidirectionalIterator __second_cut = __middle;
2995           _Distance __len11 = 0;
2996           _Distance __len22 = 0;
2997           if (__len1 > __len2)
2998             {
2999               __len11 = __len1 / 2;
3000               std::advance(__first_cut, __len11);
3001               __second_cut = std::lower_bound(__middle, __last, *__first_cut,
3002                                               __comp);
3003               __len22 = std::distance(__middle, __second_cut);
3004             }
3005           else
3006             {
3007               __len22 = __len2 / 2;
3008               std::advance(__second_cut, __len22);
3009               __first_cut = std::upper_bound(__first, __middle, *__second_cut,
3010                                              __comp);
3011               __len11 = std::distance(__first, __first_cut);
3012             }
3013           _BidirectionalIterator __new_middle =
3014             std::__rotate_adaptive(__first_cut, __middle, __second_cut,
3015                                    __len1 - __len11, __len22, __buffer,
3016                                    __buffer_size);
3017           std::__merge_adaptive(__first, __first_cut, __new_middle, __len11,
3018                                 __len22, __buffer, __buffer_size, __comp);
3019           std::__merge_adaptive(__new_middle, __second_cut, __last,
3020                                 __len1 - __len11,
3021                                 __len2 - __len22, __buffer,
3022                                 __buffer_size, __comp);
3023         }
3024     }
3025
3026   /// This is a helper function for the merge routines.
3027   template<typename _BidirectionalIterator, typename _Distance>
3028     void
3029     __merge_without_buffer(_BidirectionalIterator __first,
3030                            _BidirectionalIterator __middle,
3031                            _BidirectionalIterator __last,
3032                            _Distance __len1, _Distance __len2)
3033     {
3034       if (__len1 == 0 || __len2 == 0)
3035         return;
3036       if (__len1 + __len2 == 2)
3037         {
3038           if (*__middle < *__first)
3039             std::iter_swap(__first, __middle);
3040           return;
3041         }
3042       _BidirectionalIterator __first_cut = __first;
3043       _BidirectionalIterator __second_cut = __middle;
3044       _Distance __len11 = 0;
3045       _Distance __len22 = 0;
3046       if (__len1 > __len2)
3047         {
3048           __len11 = __len1 / 2;
3049           std::advance(__first_cut, __len11);
3050           __second_cut = std::lower_bound(__middle, __last, *__first_cut);
3051           __len22 = std::distance(__middle, __second_cut);
3052         }
3053       else
3054         {
3055           __len22 = __len2 / 2;
3056           std::advance(__second_cut, __len22);
3057           __first_cut = std::upper_bound(__first, __middle, *__second_cut);
3058           __len11 = std::distance(__first, __first_cut);
3059         }
3060       std::rotate(__first_cut, __middle, __second_cut);
3061       _BidirectionalIterator __new_middle = __first_cut;
3062       std::advance(__new_middle, std::distance(__middle, __second_cut));
3063       std::__merge_without_buffer(__first, __first_cut, __new_middle,
3064                                   __len11, __len22);
3065       std::__merge_without_buffer(__new_middle, __second_cut, __last,
3066                                   __len1 - __len11, __len2 - __len22);
3067     }
3068
3069   /// This is a helper function for the merge routines.
3070   template<typename _BidirectionalIterator, typename _Distance,
3071            typename _Compare>
3072     void
3073     __merge_without_buffer(_BidirectionalIterator __first,
3074                            _BidirectionalIterator __middle,
3075                            _BidirectionalIterator __last,
3076                            _Distance __len1, _Distance __len2,
3077                            _Compare __comp)
3078     {
3079       if (__len1 == 0 || __len2 == 0)
3080         return;
3081       if (__len1 + __len2 == 2)
3082         {
3083           if (__comp(*__middle, *__first))
3084             std::iter_swap(__first, __middle);
3085           return;
3086         }
3087       _BidirectionalIterator __first_cut = __first;
3088       _BidirectionalIterator __second_cut = __middle;
3089       _Distance __len11 = 0;
3090       _Distance __len22 = 0;
3091       if (__len1 > __len2)
3092         {
3093           __len11 = __len1 / 2;
3094           std::advance(__first_cut, __len11);
3095           __second_cut = std::lower_bound(__middle, __last, *__first_cut,
3096                                           __comp);
3097           __len22 = std::distance(__middle, __second_cut);
3098         }
3099       else
3100         {
3101           __len22 = __len2 / 2;
3102           std::advance(__second_cut, __len22);
3103           __first_cut = std::upper_bound(__first, __middle, *__second_cut,
3104                                          __comp);
3105           __len11 = std::distance(__first, __first_cut);
3106         }
3107       std::rotate(__first_cut, __middle, __second_cut);
3108       _BidirectionalIterator __new_middle = __first_cut;
3109       std::advance(__new_middle, std::distance(__middle, __second_cut));
3110       std::__merge_without_buffer(__first, __first_cut, __new_middle,
3111                                   __len11, __len22, __comp);
3112       std::__merge_without_buffer(__new_middle, __second_cut, __last,
3113                                   __len1 - __len11, __len2 - __len22, __comp);
3114     }
3115
3116   /**
3117    *  @brief Merges two sorted ranges in place.
3118    *  @ingroup sorting_algorithms
3119    *  @param  __first   An iterator.
3120    *  @param  __middle  Another iterator.
3121    *  @param  __last    Another iterator.
3122    *  @return  Nothing.
3123    *
3124    *  Merges two sorted and consecutive ranges, [__first,__middle) and
3125    *  [__middle,__last), and puts the result in [__first,__last).  The
3126    *  output will be sorted.  The sort is @e stable, that is, for
3127    *  equivalent elements in the two ranges, elements from the first
3128    *  range will always come before elements from the second.
3129    *
3130    *  If enough additional memory is available, this takes (__last-__first)-1
3131    *  comparisons.  Otherwise an NlogN algorithm is used, where N is
3132    *  distance(__first,__last).
3133   */
3134   template<typename _BidirectionalIterator>
3135     void
3136     inplace_merge(_BidirectionalIterator __first,
3137                   _BidirectionalIterator __middle,
3138                   _BidirectionalIterator __last)
3139     {
3140       typedef typename iterator_traits<_BidirectionalIterator>::value_type
3141           _ValueType;
3142       typedef typename iterator_traits<_BidirectionalIterator>::difference_type
3143           _DistanceType;
3144
3145       // concept requirements
3146       __glibcxx_function_requires(_Mutable_BidirectionalIteratorConcept<
3147             _BidirectionalIterator>)
3148       __glibcxx_function_requires(_LessThanComparableConcept<_ValueType>)
3149       __glibcxx_requires_sorted(__first, __middle);
3150       __glibcxx_requires_sorted(__middle, __last);
3151
3152       if (__first == __middle || __middle == __last)
3153         return;
3154
3155       _DistanceType __len1 = std::distance(__first, __middle);
3156       _DistanceType __len2 = std::distance(__middle, __last);
3157
3158       _Temporary_buffer<_BidirectionalIterator, _ValueType> __buf(__first,
3159                                                                   __last);
3160       if (__buf.begin() == 0)
3161         std::__merge_without_buffer(__first, __middle, __last, __len1, __len2);
3162       else
3163         std::__merge_adaptive(__first, __middle, __last, __len1, __len2,
3164                               __buf.begin(), _DistanceType(__buf.size()));
3165     }
3166
3167   /**
3168    *  @brief Merges two sorted ranges in place.
3169    *  @ingroup sorting_algorithms
3170    *  @param  __first   An iterator.
3171    *  @param  __middle  Another iterator.
3172    *  @param  __last    Another iterator.
3173    *  @param  __comp    A functor to use for comparisons.
3174    *  @return  Nothing.
3175    *
3176    *  Merges two sorted and consecutive ranges, [__first,__middle) and
3177    *  [middle,last), and puts the result in [__first,__last).  The output will
3178    *  be sorted.  The sort is @e stable, that is, for equivalent
3179    *  elements in the two ranges, elements from the first range will always
3180    *  come before elements from the second.
3181    *
3182    *  If enough additional memory is available, this takes (__last-__first)-1
3183    *  comparisons.  Otherwise an NlogN algorithm is used, where N is
3184    *  distance(__first,__last).
3185    *
3186    *  The comparison function should have the same effects on ordering as
3187    *  the function used for the initial sort.
3188   */
3189   template<typename _BidirectionalIterator, typename _Compare>
3190     void
3191     inplace_merge(_BidirectionalIterator __first,
3192                   _BidirectionalIterator __middle,
3193                   _BidirectionalIterator __last,
3194                   _Compare __comp)
3195     {
3196       typedef typename iterator_traits<_BidirectionalIterator>::value_type
3197           _ValueType;
3198       typedef typename iterator_traits<_BidirectionalIterator>::difference_type
3199           _DistanceType;
3200
3201       // concept requirements
3202       __glibcxx_function_requires(_Mutable_BidirectionalIteratorConcept<
3203             _BidirectionalIterator>)
3204       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
3205             _ValueType, _ValueType>)
3206       __glibcxx_requires_sorted_pred(__first, __middle, __comp);
3207       __glibcxx_requires_sorted_pred(__middle, __last, __comp);
3208
3209       if (__first == __middle || __middle == __last)
3210         return;
3211
3212       const _DistanceType __len1 = std::distance(__first, __middle);
3213       const _DistanceType __len2 = std::distance(__middle, __last);
3214
3215       _Temporary_buffer<_BidirectionalIterator, _ValueType> __buf(__first,
3216                                                                   __last);
3217       if (__buf.begin() == 0)
3218         std::__merge_without_buffer(__first, __middle, __last, __len1,
3219                                     __len2, __comp);
3220       else
3221         std::__merge_adaptive(__first, __middle, __last, __len1, __len2,
3222                               __buf.begin(), _DistanceType(__buf.size()),
3223                               __comp);
3224     }
3225
3226
3227   /// This is a helper function for the __merge_sort_loop routines.
3228   template<typename _InputIterator1, typename _InputIterator2,
3229            typename _OutputIterator>
3230     _OutputIterator
3231     __move_merge(_InputIterator1 __first1, _InputIterator1 __last1,
3232                  _InputIterator2 __first2, _InputIterator2 __last2,
3233                  _OutputIterator __result)
3234     {
3235       while (__first1 != __last1 && __first2 != __last2)
3236         {
3237           if (*__first2 < *__first1)
3238             {
3239               *__result = _GLIBCXX_MOVE(*__first2);
3240               ++__first2;
3241             }
3242           else
3243             {
3244               *__result = _GLIBCXX_MOVE(*__first1);
3245               ++__first1;
3246             }
3247           ++__result;
3248         }
3249       return _GLIBCXX_MOVE3(__first2, __last2,
3250                             _GLIBCXX_MOVE3(__first1, __last1,
3251                                            __result));
3252     }
3253
3254   /// This is a helper function for the __merge_sort_loop routines.
3255   template<typename _InputIterator1, typename _InputIterator2,
3256            typename _OutputIterator, typename _Compare>
3257     _OutputIterator
3258     __move_merge(_InputIterator1 __first1, _InputIterator1 __last1,
3259                  _InputIterator2 __first2, _InputIterator2 __last2,
3260                  _OutputIterator __result, _Compare __comp)
3261     {
3262       while (__first1 != __last1 && __first2 != __last2)
3263         {
3264           if (__comp(*__first2, *__first1))
3265             {
3266               *__result = _GLIBCXX_MOVE(*__first2);
3267               ++__first2;
3268             }
3269           else
3270             {
3271               *__result = _GLIBCXX_MOVE(*__first1);
3272               ++__first1;
3273             }
3274           ++__result;
3275         }
3276       return _GLIBCXX_MOVE3(__first2, __last2,
3277                             _GLIBCXX_MOVE3(__first1, __last1,
3278                                            __result));
3279     }
3280
3281   template<typename _RandomAccessIterator1, typename _RandomAccessIterator2,
3282            typename _Distance>
3283     void
3284     __merge_sort_loop(_RandomAccessIterator1 __first,
3285                       _RandomAccessIterator1 __last,
3286                       _RandomAccessIterator2 __result,
3287                       _Distance __step_size)
3288     {
3289       const _Distance __two_step = 2 * __step_size;
3290
3291       while (__last - __first >= __two_step)
3292         {
3293           __result = std::__move_merge(__first, __first + __step_size,
3294                                        __first + __step_size,
3295                                        __first + __two_step, __result);
3296           __first += __two_step;
3297         }
3298
3299       __step_size = std::min(_Distance(__last - __first), __step_size);
3300       std::__move_merge(__first, __first + __step_size,
3301                         __first + __step_size, __last, __result);
3302     }
3303
3304   template<typename _RandomAccessIterator1, typename _RandomAccessIterator2,
3305            typename _Distance, typename _Compare>
3306     void
3307     __merge_sort_loop(_RandomAccessIterator1 __first,
3308                       _RandomAccessIterator1 __last,
3309                       _RandomAccessIterator2 __result, _Distance __step_size,
3310                       _Compare __comp)
3311     {
3312       const _Distance __two_step = 2 * __step_size;
3313
3314       while (__last - __first >= __two_step)
3315         {
3316           __result = std::__move_merge(__first, __first + __step_size,
3317                                        __first + __step_size,
3318                                        __first + __two_step,
3319                                        __result, __comp);
3320           __first += __two_step;
3321         }
3322       __step_size = std::min(_Distance(__last - __first), __step_size);
3323
3324       std::__move_merge(__first,__first + __step_size,
3325                         __first + __step_size, __last, __result, __comp);
3326     }
3327
3328   template<typename _RandomAccessIterator, typename _Distance>
3329     void
3330     __chunk_insertion_sort(_RandomAccessIterator __first,
3331                            _RandomAccessIterator __last,
3332                            _Distance __chunk_size)
3333     {
3334       while (__last - __first >= __chunk_size)
3335         {
3336           std::__insertion_sort(__first, __first + __chunk_size);
3337           __first += __chunk_size;
3338         }
3339       std::__insertion_sort(__first, __last);
3340     }
3341
3342   template<typename _RandomAccessIterator, typename _Distance,
3343            typename _Compare>
3344     void
3345     __chunk_insertion_sort(_RandomAccessIterator __first,
3346                            _RandomAccessIterator __last,
3347                            _Distance __chunk_size, _Compare __comp)
3348     {
3349       while (__last - __first >= __chunk_size)
3350         {
3351           std::__insertion_sort(__first, __first + __chunk_size, __comp);
3352           __first += __chunk_size;
3353         }
3354       std::__insertion_sort(__first, __last, __comp);
3355     }
3356
3357   enum { _S_chunk_size = 7 };
3358
3359   template<typename _RandomAccessIterator, typename _Pointer>
3360     void
3361     __merge_sort_with_buffer(_RandomAccessIterator __first,
3362                              _RandomAccessIterator __last,
3363                              _Pointer __buffer)
3364     {
3365       typedef typename iterator_traits<_RandomAccessIterator>::difference_type
3366         _Distance;
3367
3368       const _Distance __len = __last - __first;
3369       const _Pointer __buffer_last = __buffer + __len;
3370
3371       _Distance __step_size = _S_chunk_size;
3372       std::__chunk_insertion_sort(__first, __last, __step_size);
3373
3374       while (__step_size < __len)
3375         {
3376           std::__merge_sort_loop(__first, __last, __buffer, __step_size);
3377           __step_size *= 2;
3378           std::__merge_sort_loop(__buffer, __buffer_last, __first, __step_size);
3379           __step_size *= 2;
3380         }
3381     }
3382
3383   template<typename _RandomAccessIterator, typename _Pointer, typename _Compare>
3384     void
3385     __merge_sort_with_buffer(_RandomAccessIterator __first,
3386                              _RandomAccessIterator __last,
3387                              _Pointer __buffer, _Compare __comp)
3388     {
3389       typedef typename iterator_traits<_RandomAccessIterator>::difference_type
3390         _Distance;
3391
3392       const _Distance __len = __last - __first;
3393       const _Pointer __buffer_last = __buffer + __len;
3394
3395       _Distance __step_size = _S_chunk_size;
3396       std::__chunk_insertion_sort(__first, __last, __step_size, __comp);
3397
3398       while (__step_size < __len)
3399         {
3400           std::__merge_sort_loop(__first, __last, __buffer,
3401                                  __step_size, __comp);
3402           __step_size *= 2;
3403           std::__merge_sort_loop(__buffer, __buffer_last, __first,
3404                                  __step_size, __comp);
3405           __step_size *= 2;
3406         }
3407     }
3408
3409   template<typename _RandomAccessIterator, typename _Pointer,
3410            typename _Distance>
3411     void
3412     __stable_sort_adaptive(_RandomAccessIterator __first,
3413                            _RandomAccessIterator __last,
3414                            _Pointer __buffer, _Distance __buffer_size)
3415     {
3416       const _Distance __len = (__last - __first + 1) / 2;
3417       const _RandomAccessIterator __middle = __first + __len;
3418       if (__len > __buffer_size)
3419         {
3420           std::__stable_sort_adaptive(__first, __middle,
3421                                       __buffer, __buffer_size);
3422           std::__stable_sort_adaptive(__middle, __last,
3423                                       __buffer, __buffer_size);
3424         }
3425       else
3426         {
3427           std::__merge_sort_with_buffer(__first, __middle, __buffer);
3428           std::__merge_sort_with_buffer(__middle, __last, __buffer);
3429         }
3430       std::__merge_adaptive(__first, __middle, __last,
3431                             _Distance(__middle - __first),
3432                             _Distance(__last - __middle),
3433                             __buffer, __buffer_size);
3434     }
3435
3436   template<typename _RandomAccessIterator, typename _Pointer,
3437            typename _Distance, typename _Compare>
3438     void
3439     __stable_sort_adaptive(_RandomAccessIterator __first,
3440                            _RandomAccessIterator __last,
3441                            _Pointer __buffer, _Distance __buffer_size,
3442                            _Compare __comp)
3443     {
3444       const _Distance __len = (__last - __first + 1) / 2;
3445       const _RandomAccessIterator __middle = __first + __len;
3446       if (__len > __buffer_size)
3447         {
3448           std::__stable_sort_adaptive(__first, __middle, __buffer,
3449                                       __buffer_size, __comp);
3450           std::__stable_sort_adaptive(__middle, __last, __buffer,
3451                                       __buffer_size, __comp);
3452         }
3453       else
3454         {
3455           std::__merge_sort_with_buffer(__first, __middle, __buffer, __comp);
3456           std::__merge_sort_with_buffer(__middle, __last, __buffer, __comp);
3457         }
3458       std::__merge_adaptive(__first, __middle, __last,
3459                             _Distance(__middle - __first),
3460                             _Distance(__last - __middle),
3461                             __buffer, __buffer_size,
3462                             __comp);
3463     }
3464
3465   /// This is a helper function for the stable sorting routines.
3466   template<typename _RandomAccessIterator>
3467     void
3468     __inplace_stable_sort(_RandomAccessIterator __first,
3469                           _RandomAccessIterator __last)
3470     {
3471       if (__last - __first < 15)
3472         {
3473           std::__insertion_sort(__first, __last);
3474           return;
3475         }
3476       _RandomAccessIterator __middle = __first + (__last - __first) / 2;
3477       std::__inplace_stable_sort(__first, __middle);
3478       std::__inplace_stable_sort(__middle, __last);
3479       std::__merge_without_buffer(__first, __middle, __last,
3480                                   __middle - __first,
3481                                   __last - __middle);
3482     }
3483
3484   /// This is a helper function for the stable sorting routines.
3485   template<typename _RandomAccessIterator, typename _Compare>
3486     void
3487     __inplace_stable_sort(_RandomAccessIterator __first,
3488                           _RandomAccessIterator __last, _Compare __comp)
3489     {
3490       if (__last - __first < 15)
3491         {
3492           std::__insertion_sort(__first, __last, __comp);
3493           return;
3494         }
3495       _RandomAccessIterator __middle = __first + (__last - __first) / 2;
3496       std::__inplace_stable_sort(__first, __middle, __comp);
3497       std::__inplace_stable_sort(__middle, __last, __comp);
3498       std::__merge_without_buffer(__first, __middle, __last,
3499                                   __middle - __first,
3500                                   __last - __middle,
3501                                   __comp);
3502     }
3503
3504   // stable_sort
3505
3506   // Set algorithms: includes, set_union, set_intersection, set_difference,
3507   // set_symmetric_difference.  All of these algorithms have the precondition
3508   // that their input ranges are sorted and the postcondition that their output
3509   // ranges are sorted.
3510
3511   /**
3512    *  @brief Determines whether all elements of a sequence exists in a range.
3513    *  @param  __first1  Start of search range.
3514    *  @param  __last1   End of search range.
3515    *  @param  __first2  Start of sequence
3516    *  @param  __last2   End of sequence.
3517    *  @return  True if each element in [__first2,__last2) is contained in order
3518    *  within [__first1,__last1).  False otherwise.
3519    *  @ingroup set_algorithms
3520    *
3521    *  This operation expects both [__first1,__last1) and
3522    *  [__first2,__last2) to be sorted.  Searches for the presence of
3523    *  each element in [__first2,__last2) within [__first1,__last1).
3524    *  The iterators over each range only move forward, so this is a
3525    *  linear algorithm.  If an element in [__first2,__last2) is not
3526    *  found before the search iterator reaches @a __last2, false is
3527    *  returned.
3528   */
3529   template<typename _InputIterator1, typename _InputIterator2>
3530     bool
3531     includes(_InputIterator1 __first1, _InputIterator1 __last1,
3532              _InputIterator2 __first2, _InputIterator2 __last2)
3533     {
3534       typedef typename iterator_traits<_InputIterator1>::value_type
3535         _ValueType1;
3536       typedef typename iterator_traits<_InputIterator2>::value_type
3537         _ValueType2;
3538
3539       // concept requirements
3540       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
3541       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
3542       __glibcxx_function_requires(_LessThanOpConcept<_ValueType1, _ValueType2>)
3543       __glibcxx_function_requires(_LessThanOpConcept<_ValueType2, _ValueType1>)
3544       __glibcxx_requires_sorted_set(__first1, __last1, __first2);
3545       __glibcxx_requires_sorted_set(__first2, __last2, __first1);
3546
3547       while (__first1 != __last1 && __first2 != __last2)
3548         if (*__first2 < *__first1)
3549           return false;
3550         else if(*__first1 < *__first2)
3551           ++__first1;
3552         else
3553           ++__first1, ++__first2;
3554
3555       return __first2 == __last2;
3556     }
3557
3558   /**
3559    *  @brief Determines whether all elements of a sequence exists in a range
3560    *  using comparison.
3561    *  @ingroup set_algorithms
3562    *  @param  __first1  Start of search range.
3563    *  @param  __last1   End of search range.
3564    *  @param  __first2  Start of sequence
3565    *  @param  __last2   End of sequence.
3566    *  @param  __comp    Comparison function to use.
3567    *  @return True if each element in [__first2,__last2) is contained
3568    *  in order within [__first1,__last1) according to comp.  False
3569    *  otherwise.  @ingroup set_algorithms
3570    *
3571    *  This operation expects both [__first1,__last1) and
3572    *  [__first2,__last2) to be sorted.  Searches for the presence of
3573    *  each element in [__first2,__last2) within [__first1,__last1),
3574    *  using comp to decide.  The iterators over each range only move
3575    *  forward, so this is a linear algorithm.  If an element in
3576    *  [__first2,__last2) is not found before the search iterator
3577    *  reaches @a __last2, false is returned.
3578   */
3579   template<typename _InputIterator1, typename _InputIterator2,
3580            typename _Compare>
3581     bool
3582     includes(_InputIterator1 __first1, _InputIterator1 __last1,
3583              _InputIterator2 __first2, _InputIterator2 __last2,
3584              _Compare __comp)
3585     {
3586       typedef typename iterator_traits<_InputIterator1>::value_type
3587         _ValueType1;
3588       typedef typename iterator_traits<_InputIterator2>::value_type
3589         _ValueType2;
3590
3591       // concept requirements
3592       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
3593       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
3594       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,