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

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