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

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