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