contrib/libstdc++/include/bits/stl_algo.h

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