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