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