l4/pkg/libstdc++-v3/contrib/libstdc++-v3-4.1.0/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 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(_LessThanComparableConcept<_OutputValueType>)
2516       __glibcxx_function_requires(_LessThanComparableConcept<_InputValueType>)
2517       __glibcxx_requires_valid_range(__first, __last);
2518       __glibcxx_requires_valid_range(__result_first, __result_last);
2519
2520       if (__result_first == __result_last)
2521         return __result_last;
2522       _RandomAccessIterator __result_real_last = __result_first;
2523       while(__first != __last && __result_real_last != __result_last)
2524         {
2525           *__result_real_last = *__first;
2526           ++__result_real_last;
2527           ++__first;
2528         }
2529       std::make_heap(__result_first, __result_real_last);
2530       while (__first != __last)
2531         {
2532           if (*__first < *__result_first)
2533             std::__adjust_heap(__result_first, _DistanceType(0),
2534                                _DistanceType(__result_real_last
2535                                              - __result_first),
2536                                _InputValueType(*__first));
2537           ++__first;
2538         }
2539       std::sort_heap(__result_first, __result_real_last);
2540       return __result_real_last;
2541     }
2542
2543   /**
2544    *  @brief Copy the smallest elements of a sequence using a predicate for
2545    *         comparison.
2546    *  @param  first   An input iterator.
2547    *  @param  last    Another input iterator.
2548    *  @param  result_first   A random-access iterator.
2549    *  @param  result_last    Another random-access iterator.
2550    *  @param  comp    A comparison functor.
2551    *  @return   An iterator indicating the end of the resulting sequence.
2552    *
2553    *  Copies and sorts the smallest N values from the range @p [first,last)
2554    *  to the range beginning at @p result_first, where the number of
2555    *  elements to be copied, @p N, is the smaller of @p (last-first) and
2556    *  @p (result_last-result_first).
2557    *  After the sort if @p i and @j are iterators in the range
2558    *  @p [result_first,result_first+N) such that @i precedes @j then
2559    *  @p comp(*j,*i) is false.
2560    *  The value returned is @p result_first+N.
2561   */
2562   template<typename _InputIterator, typename _RandomAccessIterator, typename _Compare>
2563     _RandomAccessIterator
2564     partial_sort_copy(_InputIterator __first, _InputIterator __last,
2565                       _RandomAccessIterator __result_first,
2566                       _RandomAccessIterator __result_last,
2567                       _Compare __comp)
2568     {
2569       typedef typename iterator_traits<_InputIterator>::value_type
2570         _InputValueType;
2571       typedef typename iterator_traits<_RandomAccessIterator>::value_type
2572         _OutputValueType;
2573       typedef typename iterator_traits<_RandomAccessIterator>::difference_type
2574         _DistanceType;
2575
2576       // concept requirements
2577       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
2578       __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
2579                                   _RandomAccessIterator>)
2580       __glibcxx_function_requires(_ConvertibleConcept<_InputValueType,
2581                                   _OutputValueType>)
2582       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2583                                   _OutputValueType, _OutputValueType>)
2584       __glibcxx_requires_valid_range(__first, __last);
2585       __glibcxx_requires_valid_range(__result_first, __result_last);
2586
2587       if (__result_first == __result_last)
2588         return __result_last;
2589       _RandomAccessIterator __result_real_last = __result_first;
2590       while(__first != __last && __result_real_last != __result_last)
2591         {
2592           *__result_real_last = *__first;
2593           ++__result_real_last;
2594           ++__first;
2595         }
2596       std::make_heap(__result_first, __result_real_last, __comp);
2597       while (__first != __last)
2598         {
2599           if (__comp(*__first, *__result_first))
2600             std::__adjust_heap(__result_first, _DistanceType(0),
2601                                _DistanceType(__result_real_last
2602                                              - __result_first),
2603                                _InputValueType(*__first),
2604                                __comp);
2605           ++__first;
2606         }
2607       std::sort_heap(__result_first, __result_real_last, __comp);
2608       return __result_real_last;
2609     }
2610
2611   /**
2612    *  @if maint
2613    *  This is a helper function for the sort routine.
2614    *  @endif
2615   */
2616   template<typename _RandomAccessIterator, typename _Size>
2617     void
2618     __introsort_loop(_RandomAccessIterator __first,
2619                      _RandomAccessIterator __last,
2620                      _Size __depth_limit)
2621     {
2622       typedef typename iterator_traits<_RandomAccessIterator>::value_type
2623         _ValueType;
2624
2625       while (__last - __first > int(_S_threshold))
2626         {
2627           if (__depth_limit == 0)
2628             {
2629               std::partial_sort(__first, __last, __last);
2630               return;
2631             }
2632           --__depth_limit;
2633           _RandomAccessIterator __cut =
2634             std::__unguarded_partition(__first, __last,
2635                                        _ValueType(std::__median(*__first,
2636                                                                 *(__first
2637                                                                   + (__last
2638                                                                      - __first)
2639                                                                   / 2),
2640                                                                 *(__last
2641                                                                   - 1))));
2642           std::__introsort_loop(__cut, __last, __depth_limit);
2643           __last = __cut;
2644         }
2645     }
2646
2647   /**
2648    *  @if maint
2649    *  This is a helper function for the sort routine.
2650    *  @endif
2651   */
2652   template<typename _RandomAccessIterator, typename _Size, typename _Compare>
2653     void
2654     __introsort_loop(_RandomAccessIterator __first,
2655                      _RandomAccessIterator __last,
2656                      _Size __depth_limit, _Compare __comp)
2657     {
2658       typedef typename iterator_traits<_RandomAccessIterator>::value_type
2659         _ValueType;
2660
2661       while (__last - __first > int(_S_threshold))
2662         {
2663           if (__depth_limit == 0)
2664             {
2665               std::partial_sort(__first, __last, __last, __comp);
2666               return;
2667             }
2668           --__depth_limit;
2669           _RandomAccessIterator __cut =
2670             std::__unguarded_partition(__first, __last,
2671                                        _ValueType(std::__median(*__first,
2672                                                                 *(__first
2673                                                                   + (__last
2674                                                                      - __first)
2675                                                                   / 2),
2676                                                                 *(__last - 1),
2677                                                                 __comp)),
2678                                        __comp);
2679           std::__introsort_loop(__cut, __last, __depth_limit, __comp);
2680           __last = __cut;
2681         }
2682     }
2683
2684   /**
2685    *  @brief Sort the elements of a sequence.
2686    *  @param  first   An iterator.
2687    *  @param  last    Another iterator.
2688    *  @return  Nothing.
2689    *
2690    *  Sorts the elements in the range @p [first,last) in ascending order,
2691    *  such that @p *(i+1)<*i is false for each iterator @p i in the range
2692    *  @p [first,last-1).
2693    *
2694    *  The relative ordering of equivalent elements is not preserved, use
2695    *  @p stable_sort() if this is needed.
2696   */
2697   template<typename _RandomAccessIterator>
2698     inline void
2699     sort(_RandomAccessIterator __first, _RandomAccessIterator __last)
2700     {
2701       typedef typename iterator_traits<_RandomAccessIterator>::value_type
2702         _ValueType;
2703
2704       // concept requirements
2705       __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
2706             _RandomAccessIterator>)
2707       __glibcxx_function_requires(_LessThanComparableConcept<_ValueType>)
2708       __glibcxx_requires_valid_range(__first, __last);
2709
2710       if (__first != __last)
2711         {
2712           std::__introsort_loop(__first, __last, __lg(__last - __first) * 2);
2713           std::__final_insertion_sort(__first, __last);
2714         }
2715     }
2716
2717   /**
2718    *  @brief Sort the elements of a sequence using a predicate for comparison.
2719    *  @param  first   An iterator.
2720    *  @param  last    Another iterator.
2721    *  @param  comp    A comparison functor.
2722    *  @return  Nothing.
2723    *
2724    *  Sorts the elements in the range @p [first,last) in ascending order,
2725    *  such that @p comp(*(i+1),*i) is false for every iterator @p i in the
2726    *  range @p [first,last-1).
2727    *
2728    *  The relative ordering of equivalent elements is not preserved, use
2729    *  @p stable_sort() if this is needed.
2730   */
2731   template<typename _RandomAccessIterator, typename _Compare>
2732     inline void
2733     sort(_RandomAccessIterator __first, _RandomAccessIterator __last,
2734          _Compare __comp)
2735     {
2736       typedef typename iterator_traits<_RandomAccessIterator>::value_type
2737         _ValueType;
2738
2739       // concept requirements
2740       __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
2741             _RandomAccessIterator>)
2742       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, _ValueType,
2743                                   _ValueType>)
2744       __glibcxx_requires_valid_range(__first, __last);
2745
2746       if (__first != __last)
2747         {
2748           std::__introsort_loop(__first, __last, __lg(__last - __first) * 2,
2749                                 __comp);
2750           std::__final_insertion_sort(__first, __last, __comp);
2751         }
2752     }
2753
2754   /**
2755    *  @brief Finds the first position in which @a val could be inserted
2756    *         without changing the ordering.
2757    *  @param  first   An iterator.
2758    *  @param  last    Another iterator.
2759    *  @param  val     The search term.
2760    *  @return  An iterator pointing to the first element "not less than" @a val,
2761    *           or end() if every element is less than @a val.
2762    *  @ingroup binarysearch
2763   */
2764   template<typename _ForwardIterator, typename _Tp>
2765     _ForwardIterator
2766     lower_bound(_ForwardIterator __first, _ForwardIterator __last,
2767                 const _Tp& __val)
2768     {
2769       typedef typename iterator_traits<_ForwardIterator>::value_type
2770         _ValueType;
2771       typedef typename iterator_traits<_ForwardIterator>::difference_type
2772         _DistanceType;
2773
2774       // concept requirements
2775       // Note that these are slightly stricter than those of the 4-argument
2776       // version, defined next.  The difference is in the strictness of the
2777       // comparison operations... so for looser checking, define your own
2778       // comparison function, as was intended.
2779       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
2780       __glibcxx_function_requires(_SameTypeConcept<_Tp, _ValueType>)
2781       __glibcxx_function_requires(_LessThanComparableConcept<_Tp>)
2782       __glibcxx_requires_partitioned(__first, __last, __val);
2783
2784       _DistanceType __len = std::distance(__first, __last);
2785       _DistanceType __half;
2786       _ForwardIterator __middle;
2787
2788       while (__len > 0)
2789         {
2790           __half = __len >> 1;
2791           __middle = __first;
2792           std::advance(__middle, __half);
2793           if (*__middle < __val)
2794             {
2795               __first = __middle;
2796               ++__first;
2797               __len = __len - __half - 1;
2798             }
2799           else
2800             __len = __half;
2801         }
2802       return __first;
2803     }
2804
2805   /**
2806    *  @brief Finds the first position in which @a val could be inserted
2807    *         without changing the ordering.
2808    *  @param  first   An iterator.
2809    *  @param  last    Another iterator.
2810    *  @param  val     The search term.
2811    *  @param  comp    A functor to use for comparisons.
2812    *  @return  An iterator pointing to the first element "not less than" @a val,
2813    *           or end() if every element is less than @a val.
2814    *  @ingroup binarysearch
2815    *
2816    *  The comparison function should have the same effects on ordering as
2817    *  the function used for the initial sort.
2818   */
2819   template<typename _ForwardIterator, typename _Tp, typename _Compare>
2820     _ForwardIterator
2821     lower_bound(_ForwardIterator __first, _ForwardIterator __last,
2822                 const _Tp& __val, _Compare __comp)
2823     {
2824       typedef typename iterator_traits<_ForwardIterator>::value_type
2825         _ValueType;
2826       typedef typename iterator_traits<_ForwardIterator>::difference_type
2827         _DistanceType;
2828
2829       // concept requirements
2830       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
2831       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2832                                   _ValueType, _Tp>)
2833       __glibcxx_requires_partitioned_pred(__first, __last, __val, __comp);
2834
2835       _DistanceType __len = std::distance(__first, __last);
2836       _DistanceType __half;
2837       _ForwardIterator __middle;
2838
2839       while (__len > 0)
2840         {
2841           __half = __len >> 1;
2842           __middle = __first;
2843           std::advance(__middle, __half);
2844           if (__comp(*__middle, __val))
2845             {
2846               __first = __middle;
2847               ++__first;
2848               __len = __len - __half - 1;
2849             }
2850           else
2851             __len = __half;
2852         }
2853       return __first;
2854     }
2855
2856   /**
2857    *  @brief Finds the last position in which @a val could be inserted
2858    *         without changing the ordering.
2859    *  @param  first   An iterator.
2860    *  @param  last    Another iterator.
2861    *  @param  val     The search term.
2862    *  @return  An iterator pointing to the first element greater than @a val,
2863    *           or end() if no elements are greater than @a val.
2864    *  @ingroup binarysearch
2865   */
2866   template<typename _ForwardIterator, typename _Tp>
2867     _ForwardIterator
2868     upper_bound(_ForwardIterator __first, _ForwardIterator __last,
2869                 const _Tp& __val)
2870     {
2871       typedef typename iterator_traits<_ForwardIterator>::value_type
2872         _ValueType;
2873       typedef typename iterator_traits<_ForwardIterator>::difference_type
2874         _DistanceType;
2875
2876       // concept requirements
2877       // See comments on lower_bound.
2878       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
2879       __glibcxx_function_requires(_SameTypeConcept<_Tp, _ValueType>)
2880       __glibcxx_function_requires(_LessThanComparableConcept<_Tp>)
2881       __glibcxx_requires_partitioned(__first, __last, __val);
2882
2883       _DistanceType __len = std::distance(__first, __last);
2884       _DistanceType __half;
2885       _ForwardIterator __middle;
2886
2887       while (__len > 0)
2888         {
2889           __half = __len >> 1;
2890           __middle = __first;
2891           std::advance(__middle, __half);
2892           if (__val < *__middle)
2893             __len = __half;
2894           else
2895             {
2896               __first = __middle;
2897               ++__first;
2898               __len = __len - __half - 1;
2899             }
2900         }
2901       return __first;
2902     }
2903
2904   /**
2905    *  @brief Finds the last position in which @a val could be inserted
2906    *         without changing the ordering.
2907    *  @param  first   An iterator.
2908    *  @param  last    Another iterator.
2909    *  @param  val     The search term.
2910    *  @param  comp    A functor to use for comparisons.
2911    *  @return  An iterator pointing to the first element greater than @a val,
2912    *           or end() if no elements are greater than @a val.
2913    *  @ingroup binarysearch
2914    *
2915    *  The comparison function should have the same effects on ordering as
2916    *  the function used for the initial sort.
2917   */
2918   template<typename _ForwardIterator, typename _Tp, typename _Compare>
2919     _ForwardIterator
2920     upper_bound(_ForwardIterator __first, _ForwardIterator __last,
2921                 const _Tp& __val, _Compare __comp)
2922     {
2923       typedef typename iterator_traits<_ForwardIterator>::value_type
2924         _ValueType;
2925       typedef typename iterator_traits<_ForwardIterator>::difference_type
2926         _DistanceType;
2927
2928       // concept requirements
2929       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
2930       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2931                                   _Tp, _ValueType>)
2932       __glibcxx_requires_partitioned_pred(__first, __last, __val, __comp);
2933
2934       _DistanceType __len = std::distance(__first, __last);
2935       _DistanceType __half;
2936       _ForwardIterator __middle;
2937
2938       while (__len > 0)
2939         {
2940           __half = __len >> 1;
2941           __middle = __first;
2942           std::advance(__middle, __half);
2943           if (__comp(__val, *__middle))
2944             __len = __half;
2945           else
2946             {
2947               __first = __middle;
2948               ++__first;
2949               __len = __len - __half - 1;
2950             }
2951         }
2952       return __first;
2953     }
2954
2955   /**
2956    *  @if maint
2957    *  This is a helper function for the merge routines.
2958    *  @endif
2959   */
2960   template<typename _BidirectionalIterator, typename _Distance>
2961     void
2962     __merge_without_buffer(_BidirectionalIterator __first,
2963                            _BidirectionalIterator __middle,
2964                            _BidirectionalIterator __last,
2965                            _Distance __len1, _Distance __len2)
2966     {
2967       if (__len1 == 0 || __len2 == 0)
2968         return;
2969       if (__len1 + __len2 == 2)
2970         {
2971           if (*__middle < *__first)
2972             std::iter_swap(__first, __middle);
2973           return;
2974         }
2975       _BidirectionalIterator __first_cut = __first;
2976       _BidirectionalIterator __second_cut = __middle;
2977       _Distance __len11 = 0;
2978       _Distance __len22 = 0;
2979       if (__len1 > __len2)
2980         {
2981           __len11 = __len1 / 2;
2982           std::advance(__first_cut, __len11);
2983           __second_cut = std::lower_bound(__middle, __last, *__first_cut);
2984           __len22 = std::distance(__middle, __second_cut);
2985         }
2986       else
2987         {
2988           __len22 = __len2 / 2;
2989           std::advance(__second_cut, __len22);
2990           __first_cut = std::upper_bound(__first, __middle, *__second_cut);
2991           __len11 = std::distance(__first, __first_cut);
2992         }
2993       std::rotate(__first_cut, __middle, __second_cut);
2994       _BidirectionalIterator __new_middle = __first_cut;
2995       std::advance(__new_middle, std::distance(__middle, __second_cut));
2996       std::__merge_without_buffer(__first, __first_cut, __new_middle,
2997                                   __len11, __len22);
2998       std::__merge_without_buffer(__new_middle, __second_cut, __last,
2999                                   __len1 - __len11, __len2 - __len22);
3000     }
3001
3002   /**
3003    *  @if maint
3004    *  This is a helper function for the merge routines.
3005    *  @endif
3006   */
3007   template<typename _BidirectionalIterator, typename _Distance,
3008            typename _Compare>
3009     void
3010     __merge_without_buffer(_BidirectionalIterator __first,
3011                            _BidirectionalIterator __middle,
3012                            _BidirectionalIterator __last,
3013                            _Distance __len1, _Distance __len2,
3014                            _Compare __comp)
3015     {
3016       if (__len1 == 0 || __len2 == 0)
3017         return;
3018       if (__len1 + __len2 == 2)
3019         {
3020           if (__comp(*__middle, *__first))
3021             std::iter_swap(__first, __middle);
3022           return;
3023         }
3024       _BidirectionalIterator __first_cut = __first;
3025       _BidirectionalIterator __second_cut = __middle;
3026       _Distance __len11 = 0;
3027       _Distance __len22 = 0;
3028       if (__len1 > __len2)
3029         {
3030           __len11 = __len1 / 2;
3031           std::advance(__first_cut, __len11);
3032           __second_cut = std::lower_bound(__middle, __last, *__first_cut,
3033                                           __comp);
3034           __len22 = std::distance(__middle, __second_cut);
3035         }
3036       else
3037         {
3038           __len22 = __len2 / 2;
3039           std::advance(__second_cut, __len22);
3040           __first_cut = std::upper_bound(__first, __middle, *__second_cut,
3041                                          __comp);
3042           __len11 = std::distance(__first, __first_cut);
3043         }
3044       std::rotate(__first_cut, __middle, __second_cut);
3045       _BidirectionalIterator __new_middle = __first_cut;
3046       std::advance(__new_middle, std::distance(__middle, __second_cut));
3047       std::__merge_without_buffer(__first, __first_cut, __new_middle,
3048                                   __len11, __len22, __comp);
3049       std::__merge_without_buffer(__new_middle, __second_cut, __last,
3050                                   __len1 - __len11, __len2 - __len22, __comp);
3051     }
3052
3053   /**
3054    *  @if maint
3055    *  This is a helper function for the stable sorting routines.
3056    *  @endif
3057   */
3058   template<typename _RandomAccessIterator>
3059     void
3060     __inplace_stable_sort(_RandomAccessIterator __first,
3061                           _RandomAccessIterator __last)
3062     {
3063       if (__last - __first < 15)
3064         {
3065           std::__insertion_sort(__first, __last);
3066           return;
3067         }
3068       _RandomAccessIterator __middle = __first + (__last - __first) / 2;
3069       std::__inplace_stable_sort(__first, __middle);
3070       std::__inplace_stable_sort(__middle, __last);
3071       std::__merge_without_buffer(__first, __middle, __last,
3072                                   __middle - __first,
3073                                   __last - __middle);
3074     }
3075
3076   /**
3077    *  @if maint
3078    *  This is a helper function for the stable sorting routines.
3079    *  @endif
3080   */
3081   template<typename _RandomAccessIterator, typename _Compare>
3082     void
3083     __inplace_stable_sort(_RandomAccessIterator __first,
3084                           _RandomAccessIterator __last, _Compare __comp)
3085     {
3086       if (__last - __first < 15)
3087         {
3088           std::__insertion_sort(__first, __last, __comp);
3089           return;
3090         }
3091       _RandomAccessIterator __middle = __first + (__last - __first) / 2;
3092       std::__inplace_stable_sort(__first, __middle, __comp);
3093       std::__inplace_stable_sort(__middle, __last, __comp);
3094       std::__merge_without_buffer(__first, __middle, __last,
3095                                   __middle - __first,
3096                                   __last - __middle,
3097                                   __comp);
3098     }
3099
3100   /**
3101    *  @brief Merges two sorted ranges.
3102    *  @param  first1  An iterator.
3103    *  @param  first2  Another iterator.
3104    *  @param  last1   Another iterator.
3105    *  @param  last2   Another iterator.
3106    *  @param  result  An iterator pointing to the end of the merged range.
3107    *  @return  An iterator pointing to the first element "not less than" @a val.
3108    *
3109    *  Merges the ranges [first1,last1) and [first2,last2) into the sorted range
3110    *  [result, result + (last1-first1) + (last2-first2)).  Both input ranges
3111    *  must be sorted, and the output range must not overlap with either of
3112    *  the input ranges.  The sort is @e stable, that is, for equivalent
3113    *  elements in the two ranges, elements from the first range will always
3114    *  come before elements from the second.
3115   */
3116   template<typename _InputIterator1, typename _InputIterator2,
3117            typename _OutputIterator>
3118     _OutputIterator
3119     merge(_InputIterator1 __first1, _InputIterator1 __last1,
3120           _InputIterator2 __first2, _InputIterator2 __last2,
3121           _OutputIterator __result)
3122     {
3123       // concept requirements
3124       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
3125       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
3126       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
3127             typename iterator_traits<_InputIterator1>::value_type>)
3128       __glibcxx_function_requires(_SameTypeConcept<
3129             typename iterator_traits<_InputIterator1>::value_type,
3130             typename iterator_traits<_InputIterator2>::value_type>)
3131       __glibcxx_function_requires(_LessThanComparableConcept<
3132             typename iterator_traits<_InputIterator1>::value_type>)
3133       __glibcxx_requires_sorted(__first1, __last1);
3134       __glibcxx_requires_sorted(__first2, __last2);
3135
3136       while (__first1 != __last1 && __first2 != __last2)
3137         {
3138           if (*__first2 < *__first1)
3139             {
3140               *__result = *__first2;
3141               ++__first2;
3142             }
3143           else
3144             {
3145               *__result = *__first1;
3146               ++__first1;
3147             }
3148           ++__result;
3149         }
3150       return std::copy(__first2, __last2, std::copy(__first1, __last1,
3151                                                     __result));
3152     }
3153
3154   /**
3155    *  @brief Merges two sorted ranges.
3156    *  @param  first1  An iterator.
3157    *  @param  first2  Another iterator.
3158    *  @param  last1   Another iterator.
3159    *  @param  last2   Another iterator.
3160    *  @param  result  An iterator pointing to the end of the merged range.
3161    *  @param  comp    A functor to use for comparisons.
3162    *  @return  An iterator pointing to the first element "not less than" @a val.
3163    *
3164    *  Merges the ranges [first1,last1) and [first2,last2) into the sorted range
3165    *  [result, result + (last1-first1) + (last2-first2)).  Both input ranges
3166    *  must be sorted, and the output range must not overlap with either of
3167    *  the input ranges.  The sort is @e stable, that is, for equivalent
3168    *  elements in the two ranges, elements from the first range will always
3169    *  come before elements from the second.
3170    *
3171    *  The comparison function should have the same effects on ordering as
3172    *  the function used for the initial sort.
3173   */
3174   template<typename _InputIterator1, typename _InputIterator2,
3175            typename _OutputIterator, typename _Compare>
3176     _OutputIterator
3177     merge(_InputIterator1 __first1, _InputIterator1 __last1,
3178           _InputIterator2 __first2, _InputIterator2 __last2,
3179           _OutputIterator __result, _Compare __comp)
3180     {
3181       // concept requirements
3182       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
3183       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
3184       __glibcxx_function_requires(_SameTypeConcept<
3185             typename iterator_traits<_InputIterator1>::value_type,
3186             typename iterator_traits<_InputIterator2>::value_type>)
3187       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
3188             typename iterator_traits<_InputIterator1>::value_type>)
3189       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
3190             typename iterator_traits<_InputIterator1>::value_type,
3191             typename iterator_traits<_InputIterator2>::value_type>)
3192       __glibcxx_requires_sorted_pred(__first1, __last1, __comp);
3193       __glibcxx_requires_sorted_pred(__first2, __last2, __comp);
3194
3195       while (__first1 != __last1 && __first2 != __last2)
3196         {
3197           if (__comp(*__first2, *__first1))
3198             {
3199               *__result = *__first2;
3200               ++__first2;
3201             }
3202           else
3203             {
3204               *__result = *__first1;
3205               ++__first1;
3206             }
3207           ++__result;
3208         }
3209       return std::copy(__first2, __last2, std::copy(__first1, __last1,
3210                                                     __result));
3211     }
3212
3213   template<typename _RandomAccessIterator1, typename _RandomAccessIterator2,
3214            typename _Distance>
3215     void
3216     __merge_sort_loop(_RandomAccessIterator1 __first,
3217                       _RandomAccessIterator1 __last,
3218                       _RandomAccessIterator2 __result,
3219                       _Distance __step_size)
3220     {
3221       const _Distance __two_step = 2 * __step_size;
3222
3223       while (__last - __first >= __two_step)
3224         {
3225           __result = std::merge(__first, __first + __step_size,
3226                                 __first + __step_size, __first + __two_step,
3227                                 __result);
3228           __first += __two_step;
3229         }
3230
3231       __step_size = std::min(_Distance(__last - __first), __step_size);
3232       std::merge(__first, __first + __step_size, __first + __step_size, __last,
3233                  __result);
3234     }
3235
3236   template<typename _RandomAccessIterator1, typename _RandomAccessIterator2,
3237            typename _Distance, typename _Compare>
3238     void
3239     __merge_sort_loop(_RandomAccessIterator1 __first,
3240                       _RandomAccessIterator1 __last,
3241                       _RandomAccessIterator2 __result, _Distance __step_size,
3242                       _Compare __comp)
3243     {
3244       const _Distance __two_step = 2 * __step_size;
3245
3246       while (__last - __first >= __two_step)
3247         {
3248           __result = std::merge(__first, __first + __step_size,
3249                                 __first + __step_size, __first + __two_step,
3250                                 __result,
3251                                 __comp);
3252           __first += __two_step;
3253         }
3254       __step_size = std::min(_Distance(__last - __first), __step_size);
3255
3256       std::merge(__first, __first + __step_size,
3257                  __first + __step_size, __last,
3258                  __result,
3259                  __comp);
3260     }
3261
3262   enum { _S_chunk_size = 7 };
3263
3264   template<typename _RandomAccessIterator, typename _Distance>
3265     void
3266     __chunk_insertion_sort(_RandomAccessIterator __first,
3267                            _RandomAccessIterator __last,
3268                            _Distance __chunk_size)
3269     {
3270       while (__last - __first >= __chunk_size)
3271         {
3272           std::__insertion_sort(__first, __first + __chunk_size);
3273           __first += __chunk_size;
3274         }
3275       std::__insertion_sort(__first, __last);
3276     }
3277
3278   template<typename _RandomAccessIterator, typename _Distance, typename _Compare>
3279     void
3280     __chunk_insertion_sort(_RandomAccessIterator __first,
3281                            _RandomAccessIterator __last,
3282                            _Distance __chunk_size, _Compare __comp)
3283     {
3284       while (__last - __first >= __chunk_size)
3285         {
3286           std::__insertion_sort(__first, __first + __chunk_size, __comp);
3287           __first += __chunk_size;
3288         }
3289       std::__insertion_sort(__first, __last, __comp);
3290     }
3291
3292   template<typename _RandomAccessIterator, typename _Pointer>
3293     void
3294     __merge_sort_with_buffer(_RandomAccessIterator __first,
3295                              _RandomAccessIterator __last,
3296                              _Pointer __buffer)
3297     {
3298       typedef typename iterator_traits<_RandomAccessIterator>::difference_type
3299         _Distance;
3300
3301       const _Distance __len = __last - __first;
3302       const _Pointer __buffer_last = __buffer + __len;
3303
3304       _Distance __step_size = _S_chunk_size;
3305       std::__chunk_insertion_sort(__first, __last, __step_size);
3306
3307       while (__step_size < __len)
3308         {
3309           std::__merge_sort_loop(__first, __last, __buffer, __step_size);
3310           __step_size *= 2;
3311           std::__merge_sort_loop(__buffer, __buffer_last, __first, __step_size);
3312           __step_size *= 2;
3313         }
3314     }
3315
3316   template<typename _RandomAccessIterator, typename _Pointer, typename _Compare>
3317     void
3318     __merge_sort_with_buffer(_RandomAccessIterator __first,
3319                              _RandomAccessIterator __last,
3320                              _Pointer __buffer, _Compare __comp)
3321     {
3322       typedef typename iterator_traits<_RandomAccessIterator>::difference_type
3323         _Distance;
3324
3325       const _Distance __len = __last - __first;
3326       const _Pointer __buffer_last = __buffer + __len;
3327
3328       _Distance __step_size = _S_chunk_size;
3329       std::__chunk_insertion_sort(__first, __last, __step_size, __comp);
3330
3331       while (__step_size < __len)
3332         {
3333           std::__merge_sort_loop(__first, __last, __buffer,
3334                                  __step_size, __comp);
3335           __step_size *= 2;
3336           std::__merge_sort_loop(__buffer, __buffer_last, __first,
3337                                  __step_size, __comp);
3338           __step_size *= 2;
3339         }
3340     }
3341
3342   /**
3343    *  @if maint
3344    *  This is a helper function for the merge routines.
3345    *  @endif
3346   */
3347   template<typename _BidirectionalIterator1, typename _BidirectionalIterator2,
3348            typename _BidirectionalIterator3>
3349     _BidirectionalIterator3
3350     __merge_backward(_BidirectionalIterator1 __first1,
3351                      _BidirectionalIterator1 __last1,
3352                      _BidirectionalIterator2 __first2,
3353                      _BidirectionalIterator2 __last2,
3354                      _BidirectionalIterator3 __result)
3355     {
3356       if (__first1 == __last1)
3357         return std::copy_backward(__first2, __last2, __result);
3358       if (__first2 == __last2)
3359         return std::copy_backward(__first1, __last1, __result);
3360       --__last1;
3361       --__last2;
3362       while (true)
3363         {
3364           if (*__last2 < *__last1)
3365             {
3366               *--__result = *__last1;
3367               if (__first1 == __last1)
3368                 return std::copy_backward(__first2, ++__last2, __result);
3369               --__last1;
3370             }
3371           else
3372             {
3373               *--__result = *__last2;
3374               if (__first2 == __last2)
3375                 return std::copy_backward(__first1, ++__last1, __result);
3376               --__last2;
3377             }
3378         }
3379     }
3380
3381   /**
3382    *  @if maint
3383    *  This is a helper function for the merge routines.
3384    *  @endif
3385   */
3386   template<typename _BidirectionalIterator1, typename _BidirectionalIterator2,
3387            typename _BidirectionalIterator3, typename _Compare>
3388     _BidirectionalIterator3
3389     __merge_backward(_BidirectionalIterator1 __first1,
3390                      _BidirectionalIterator1 __last1,
3391                      _BidirectionalIterator2 __first2,
3392                      _BidirectionalIterator2 __last2,
3393                      _BidirectionalIterator3 __result,
3394                      _Compare __comp)
3395     {
3396       if (__first1 == __last1)
3397         return std::copy_backward(__first2, __last2, __result);
3398       if (__first2 == __last2)
3399         return std::copy_backward(__first1, __last1, __result);
3400       --__last1;
3401       --__last2;
3402       while (true)
3403         {
3404           if (__comp(*__last2, *__last1))
3405             {
3406               *--__result = *__last1;
3407               if (__first1 == __last1)
3408                 return std::copy_backward(__first2, ++__last2, __result);
3409               --__last1;
3410             }
3411           else
3412             {
3413               *--__result = *__last2;
3414               if (__first2 == __last2)
3415                 return std::copy_backward(__first1, ++__last1, __result);
3416               --__last2;
3417             }
3418         }
3419     }
3420
3421   /**
3422    *  @if maint
3423    *  This is a helper function for the merge routines.
3424    *  @endif
3425   */
3426   template<typename _BidirectionalIterator1, typename _BidirectionalIterator2,
3427            typename _Distance>
3428     _BidirectionalIterator1
3429     __rotate_adaptive(_BidirectionalIterator1 __first,
3430                       _BidirectionalIterator1 __middle,
3431                       _BidirectionalIterator1 __last,
3432                       _Distance __len1, _Distance __len2,
3433                       _BidirectionalIterator2 __buffer,
3434                       _Distance __buffer_size)
3435     {
3436       _BidirectionalIterator2 __buffer_end;
3437       if (__len1 > __len2 && __len2 <= __buffer_size)
3438         {
3439           __buffer_end = std::copy(__middle, __last, __buffer);
3440           std::copy_backward(__first, __middle, __last);
3441           return std::copy(__buffer, __buffer_end, __first);
3442         }
3443       else if (__len1 <= __buffer_size)
3444         {
3445           __buffer_end = std::copy(__first, __middle, __buffer);
3446           std::copy(__middle, __last, __first);
3447           return std::copy_backward(__buffer, __buffer_end, __last);
3448         }
3449       else
3450         {
3451           std::rotate(__first, __middle, __last);
3452           std::advance(__first, std::distance(__middle, __last));
3453           return __first;
3454         }
3455     }
3456
3457   /**
3458    *  @if maint
3459    *  This is a helper function for the merge routines.
3460    *  @endif
3461   */
3462   template<typename _BidirectionalIterator, typename _Distance,
3463            typename _Pointer>
3464     void
3465     __merge_adaptive(_BidirectionalIterator __first,
3466                      _BidirectionalIterator __middle,
3467                      _BidirectionalIterator __last,
3468                      _Distance __len1, _Distance __len2,
3469                      _Pointer __buffer, _Distance __buffer_size)
3470     {
3471       if (__len1 <= __len2 && __len1 <= __buffer_size)
3472         {
3473           _Pointer __buffer_end = std::copy(__first, __middle, __buffer);
3474           std::merge(__buffer, __buffer_end, __middle, __last, __first);
3475         }
3476       else if (__len2 <= __buffer_size)
3477         {
3478           _Pointer __buffer_end = std::copy(__middle, __last, __buffer);
3479           std::__merge_backward(__first, __middle, __buffer,
3480                                 __buffer_end, __last);
3481         }
3482       else
3483         {
3484           _BidirectionalIterator __first_cut = __first;
3485           _BidirectionalIterator __second_cut = __middle;
3486           _Distance __len11 = 0;
3487           _Distance __len22 = 0;
3488           if (__len1 > __len2)
3489             {
3490               __len11 = __len1 / 2;
3491               std::advance(__first_cut, __len11);
3492               __second_cut = std::lower_bound(__middle, __last,
3493                                               *__first_cut);
3494               __len22 = std::distance(__middle, __second_cut);
3495             }
3496           else
3497             {
3498               __len22 = __len2 / 2;
3499               std::advance(__second_cut, __len22);
3500               __first_cut = std::upper_bound(__first, __middle,
3501                                              *__second_cut);
3502               __len11 = std::distance(__first, __first_cut);
3503             }
3504           _BidirectionalIterator __new_middle =
3505             std::__rotate_adaptive(__first_cut, __middle, __second_cut,
3506                                    __len1 - __len11, __len22, __buffer,
3507                                    __buffer_size);
3508           std::__merge_adaptive(__first, __first_cut, __new_middle, __len11,
3509                                 __len22, __buffer, __buffer_size);
3510           std::__merge_adaptive(__new_middle, __second_cut, __last,
3511                                 __len1 - __len11,
3512                                 __len2 - __len22, __buffer, __buffer_size);
3513         }
3514     }
3515
3516   /**
3517    *  @if maint
3518    *  This is a helper function for the merge routines.
3519    *  @endif
3520   */
3521   template<typename _BidirectionalIterator, typename _Distance, typename _Pointer,
3522            typename _Compare>
3523     void
3524     __merge_adaptive(_BidirectionalIterator __first,
3525                      _BidirectionalIterator __middle,
3526                      _BidirectionalIterator __last,
3527                      _Distance __len1, _Distance __len2,
3528                      _Pointer __buffer, _Distance __buffer_size,
3529                      _Compare __comp)
3530     {
3531       if (__len1 <= __len2 && __len1 <= __buffer_size)
3532         {
3533           _Pointer __buffer_end = std::copy(__first, __middle, __buffer);
3534           std::merge(__buffer, __buffer_end, __middle, __last, __first, __comp);
3535         }
3536       else if (__len2 <= __buffer_size)
3537         {
3538           _Pointer __buffer_end = std::copy(__middle, __last, __buffer);
3539           std::__merge_backward(__first, __middle, __buffer, __buffer_end,
3540                                 __last, __comp);
3541         }
3542       else
3543         {
3544           _BidirectionalIterator __first_cut = __first;
3545           _BidirectionalIterator __second_cut = __middle;
3546           _Distance __len11 = 0;
3547           _Distance __len22 = 0;
3548           if (__len1 > __len2)
3549             {
3550               __len11 = __len1 / 2;
3551               std::advance(__first_cut, __len11);
3552               __second_cut = std::lower_bound(__middle, __last, *__first_cut,
3553                                               __comp);
3554               __len22 = std::distance(__middle, __second_cut);
3555             }
3556           else
3557             {
3558               __len22 = __len2 / 2;
3559               std::advance(__second_cut, __len22);
3560               __first_cut = std::upper_bound(__first, __middle, *__second_cut,
3561                                              __comp);
3562               __len11 = std::distance(__first, __first_cut);
3563             }
3564           _BidirectionalIterator __new_middle =
3565             std::__rotate_adaptive(__first_cut, __middle, __second_cut,
3566                                    __len1 - __len11, __len22, __buffer,
3567                                    __buffer_size);
3568           std::__merge_adaptive(__first, __first_cut, __new_middle, __len11,
3569                                 __len22, __buffer, __buffer_size, __comp);
3570           std::__merge_adaptive(__new_middle, __second_cut, __last,
3571                                 __len1 - __len11,
3572                                 __len2 - __len22, __buffer,
3573                                 __buffer_size, __comp);
3574         }
3575     }
3576
3577   /**
3578    *  @brief Merges two sorted ranges in place.
3579    *  @param  first   An iterator.
3580    *  @param  middle  Another iterator.
3581    *  @param  last    Another iterator.
3582    *  @return  Nothing.
3583    *
3584    *  Merges two sorted and consecutive ranges, [first,middle) and
3585    *  [middle,last), and puts the result in [first,last).  The output will
3586    *  be sorted.  The sort is @e stable, that is, for equivalent
3587    *  elements in the two ranges, elements from the first range will always
3588    *  come before elements from the second.
3589    *
3590    *  If enough additional memory is available, this takes (last-first)-1
3591    *  comparisons.  Otherwise an NlogN algorithm is used, where N is
3592    *  distance(first,last).
3593   */
3594   template<typename _BidirectionalIterator>
3595     void
3596     inplace_merge(_BidirectionalIterator __first,
3597                   _BidirectionalIterator __middle,
3598                   _BidirectionalIterator __last)
3599     {
3600       typedef typename iterator_traits<_BidirectionalIterator>::value_type
3601           _ValueType;
3602       typedef typename iterator_traits<_BidirectionalIterator>::difference_type
3603           _DistanceType;
3604
3605       // concept requirements
3606       __glibcxx_function_requires(_Mutable_BidirectionalIteratorConcept<
3607             _BidirectionalIterator>)
3608       __glibcxx_function_requires(_LessThanComparableConcept<_ValueType>)
3609       __glibcxx_requires_sorted(__first, __middle);
3610       __glibcxx_requires_sorted(__middle, __last);
3611
3612       if (__first == __middle || __middle == __last)
3613         return;
3614
3615       _DistanceType __len1 = std::distance(__first, __middle);
3616       _DistanceType __len2 = std::distance(__middle, __last);
3617
3618       _Temporary_buffer<_BidirectionalIterator, _ValueType> __buf(__first,
3619                                                                   __last);
3620       if (__buf.begin() == 0)
3621         std::__merge_without_buffer(__first, __middle, __last, __len1, __len2);
3622       else
3623         std::__merge_adaptive(__first, __middle, __last, __len1, __len2,
3624                               __buf.begin(), _DistanceType(__buf.size()));
3625     }
3626
3627   /**
3628    *  @brief Merges two sorted ranges in place.
3629    *  @param  first   An iterator.
3630    *  @param  middle  Another iterator.
3631    *  @param  last    Another iterator.
3632    *  @param  comp    A functor to use for comparisons.
3633    *  @return  Nothing.
3634    *
3635    *  Merges two sorted and consecutive ranges, [first,middle) and
3636    *  [middle,last), and puts the result in [first,last).  The output will
3637    *  be sorted.  The sort is @e stable, that is, for equivalent
3638    *  elements in the two ranges, elements from the first range will always
3639    *  come before elements from the second.
3640    *
3641    *  If enough additional memory is available, this takes (last-first)-1
3642    *  comparisons.  Otherwise an NlogN algorithm is used, where N is
3643    *  distance(first,last).
3644    *
3645    *  The comparison function should have the same effects on ordering as
3646    *  the function used for the initial sort.
3647   */
3648   template<typename _BidirectionalIterator, typename _Compare>
3649     void
3650     inplace_merge(_BidirectionalIterator __first,
3651                   _BidirectionalIterator __middle,
3652                   _BidirectionalIterator __last,
3653                   _Compare __comp)
3654     {
3655       typedef typename iterator_traits<_BidirectionalIterator>::value_type
3656           _ValueType;
3657       typedef typename iterator_traits<_BidirectionalIterator>::difference_type
3658           _DistanceType;
3659
3660       // concept requirements
3661       __glibcxx_function_requires(_Mutable_BidirectionalIteratorConcept<
3662             _BidirectionalIterator>)
3663       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
3664             _ValueType, _ValueType>)
3665       __glibcxx_requires_sorted_pred(__first, __middle, __comp);
3666       __glibcxx_requires_sorted_pred(__middle, __last, __comp);
3667
3668       if (__first == __middle || __middle == __last)
3669         return;
3670
3671       const _DistanceType __len1 = std::distance(__first, __middle);
3672       const _DistanceType __len2 = std::distance(__middle, __last);
3673
3674       _Temporary_buffer<_BidirectionalIterator, _ValueType> __buf(__first,
3675                                                                   __last);
3676       if (__buf.begin() == 0)
3677         std::__merge_without_buffer(__first, __middle, __last, __len1,
3678                                     __len2, __comp);
3679       else
3680         std::__merge_adaptive(__first, __middle, __last, __len1, __len2,
3681                               __buf.begin(), _DistanceType(__buf.size()),
3682                               __comp);
3683     }
3684
3685   template<typename _RandomAccessIterator, typename _Pointer,
3686            typename _Distance>
3687     void
3688     __stable_sort_adaptive(_RandomAccessIterator __first,
3689                            _RandomAccessIterator __last,
3690                            _Pointer __buffer, _Distance __buffer_size)
3691     {
3692       const _Distance __len = (__last - __first + 1) / 2;
3693       const _RandomAccessIterator __middle = __first + __len;
3694       if (__len > __buffer_size)
3695         {
3696           std::__stable_sort_adaptive(__first, __middle,
3697                                       __buffer, __buffer_size);
3698           std::__stable_sort_adaptive(__middle, __last,
3699                                       __buffer, __buffer_size);
3700         }
3701       else
3702         {
3703           std::__merge_sort_with_buffer(__first, __middle, __buffer);
3704           std::__merge_sort_with_buffer(__middle, __last, __buffer);
3705         }
3706       std::__merge_adaptive(__first, __middle, __last,
3707                             _Distance(__middle - __first),
3708                             _Distance(__last - __middle),
3709                             __buffer, __buffer_size);
3710     }
3711
3712   template<typename _RandomAccessIterator, typename _Pointer,
3713            typename _Distance, typename _Compare>
3714     void
3715     __stable_sort_adaptive(_RandomAccessIterator __first,
3716                            _RandomAccessIterator __last,
3717                            _Pointer __buffer, _Distance __buffer_size,
3718                            _Compare __comp)
3719     {
3720       const _Distance __len = (__last - __first + 1) / 2;
3721       const _RandomAccessIterator __middle = __first + __len;
3722       if (__len > __buffer_size)
3723         {
3724           std::__stable_sort_adaptive(__first, __middle, __buffer,
3725                                       __buffer_size, __comp);
3726           std::__stable_sort_adaptive(__middle, __last, __buffer,
3727                                       __buffer_size, __comp);
3728         }
3729       else
3730         {
3731           std::__merge_sort_with_buffer(__first, __middle, __buffer, __comp);
3732           std::__merge_sort_with_buffer(__middle, __last, __buffer, __comp);
3733         }
3734       std::__merge_adaptive(__first, __middle, __last,
3735                             _Distance(__middle - __first),
3736                             _Distance(__last - __middle),
3737                             __buffer, __buffer_size,
3738                             __comp);
3739     }
3740
3741   /**
3742    *  @brief Sort the elements of a sequence, preserving the relative order
3743    *         of equivalent elements.
3744    *  @param  first   An iterator.
3745    *  @param  last    Another iterator.
3746    *  @return  Nothing.
3747    *
3748    *  Sorts the elements in the range @p [first,last) in ascending order,
3749    *  such that @p *(i+1)<*i is false for each iterator @p i in the range
3750    *  @p [first,last-1).
3751    *
3752    *  The relative ordering of equivalent elements is preserved, so any two
3753    *  elements @p x and @p y in the range @p [first,last) such that
3754    *  @p x<y is false and @p y<x is false will have the same relative
3755    *  ordering after calling @p stable_sort().
3756   */
3757   template<typename _RandomAccessIterator>
3758     inline void
3759     stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last)
3760     {
3761       typedef typename iterator_traits<_RandomAccessIterator>::value_type
3762         _ValueType;
3763       typedef typename iterator_traits<_RandomAccessIterator>::difference_type
3764         _DistanceType;
3765
3766       // concept requirements
3767       __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
3768             _RandomAccessIterator>)
3769       __glibcxx_function_requires(_LessThanComparableConcept<_ValueType>)
3770       __glibcxx_requires_valid_range(__first, __last);
3771
3772       _Temporary_buffer<_RandomAccessIterator, _ValueType>
3773         buf(__first, __last);
3774       if (buf.begin() == 0)
3775         std::__inplace_stable_sort(__first, __last);
3776       else
3777         std::__stable_sort_adaptive(__first, __last, buf.begin(),
3778                                     _DistanceType(buf.size()));
3779     }
3780
3781   /**
3782    *  @brief Sort the elements of a sequence using a predicate for comparison,
3783    *         preserving the relative order of equivalent elements.
3784    *  @param  first   An iterator.
3785    *  @param  last    Another iterator.
3786    *  @param  comp    A comparison functor.
3787    *  @return  Nothing.
3788    *
3789    *  Sorts the elements in the range @p [first,last) in ascending order,
3790    *  such that @p comp(*(i+1),*i) is false for each iterator @p i in the
3791    *  range @p [first,last-1).
3792    *
3793    *  The relative ordering of equivalent elements is preserved, so any two
3794    *  elements @p x and @p y in the range @p [first,last) such that
3795    *  @p comp(x,y) is false and @p comp(y,x) is false will have the same
3796    *  relative ordering after calling @p stable_sort().
3797   */
3798   template<typename _RandomAccessIterator, typename _Compare>
3799     inline void
3800     stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last,
3801                 _Compare __comp)
3802     {
3803       typedef typename iterator_traits<_RandomAccessIterator>::value_type
3804         _ValueType;
3805       typedef typename iterator_traits<_RandomAccessIterator>::difference_type
3806         _DistanceType;
3807
3808       // concept requirements
3809       __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
3810             _RandomAccessIterator>)
3811       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
3812                                   _ValueType,
3813                                   _ValueType>)
3814       __glibcxx_requires_valid_range(__first, __last);
3815
3816       _Temporary_buffer<_RandomAccessIterator, _ValueType> buf(__first, __last);
3817       if (buf.begin() == 0)
3818         std::__inplace_stable_sort(__first, __last, __comp);
3819       else
3820         std::__stable_sort_adaptive(__first, __last, buf.begin(),
3821                                     _DistanceType(buf.size()), __comp);
3822     }
3823
3824   /**
3825    *  @brief Sort a sequence just enough to find a particular position.
3826    *  @param  first   An iterator.
3827    *  @param  nth     Another iterator.
3828    *  @param  last    Another iterator.
3829    *  @return  Nothing.
3830    *
3831    *  Rearranges the elements in the range @p [first,last) so that @p *nth
3832    *  is the same element that would have been in that position had the
3833    *  whole sequence been sorted.
3834    *  whole sequence been sorted. The elements either side of @p *nth are
3835    *  not completely sorted, but for any iterator @i in the range
3836    *  @p [first,nth) and any iterator @j in the range @p [nth,last) it
3837    *  holds that @p *j<*i is false.
3838   */
3839   template<typename _RandomAccessIterator>
3840     void
3841     nth_element(_RandomAccessIterator __first,
3842                 _RandomAccessIterator __nth,
3843                 _RandomAccessIterator __last)
3844     {
3845       typedef typename iterator_traits<_RandomAccessIterator>::value_type
3846         _ValueType;
3847
3848       // concept requirements
3849       __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
3850                                   _RandomAccessIterator>)
3851       __glibcxx_function_requires(_LessThanComparableConcept<_ValueType>)
3852       __glibcxx_requires_valid_range(__first, __nth);
3853       __glibcxx_requires_valid_range(__nth, __last);
3854
3855       while (__last - __first > 3)
3856         {
3857           _RandomAccessIterator __cut =
3858             std::__unguarded_partition(__first, __last,
3859                                        _ValueType(std::__median(*__first,
3860                                                                 *(__first
3861                                                                   + (__last
3862                                                                      - __first)
3863                                                                   / 2),
3864                                                                 *(__last
3865                                                                   - 1))));
3866           if (__cut <= __nth)
3867             __first = __cut;
3868           else
3869             __last = __cut;
3870         }
3871       std::__insertion_sort(__first, __last);
3872     }
3873
3874   /**
3875    *  @brief Sort a sequence just enough to find a particular position
3876    *         using a predicate for comparison.
3877    *  @param  first   An iterator.
3878    *  @param  nth     Another iterator.
3879    *  @param  last    Another iterator.
3880    *  @param  comp    A comparison functor.
3881    *  @return  Nothing.
3882    *
3883    *  Rearranges the elements in the range @p [first,last) so that @p *nth
3884    *  is the same element that would have been in that position had the
3885    *  whole sequence been sorted. The elements either side of @p *nth are
3886    *  not completely sorted, but for any iterator @i in the range
3887    *  @p [first,nth) and any iterator @j in the range @p [nth,last) it
3888    *  holds that @p comp(*j,*i) is false.
3889   */
3890   template<typename _RandomAccessIterator, typename _Compare>
3891     void
3892     nth_element(_RandomAccessIterator __first,
3893                 _RandomAccessIterator __nth,
3894                 _RandomAccessIterator __last,
3895                             _Compare __comp)
3896     {
3897       typedef typename iterator_traits<_RandomAccessIterator>::value_type
3898         _ValueType;
3899
3900       // concept requirements
3901       __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
3902                                   _RandomAccessIterator>)
3903       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
3904                                   _ValueType, _ValueType>)
3905       __glibcxx_requires_valid_range(__first, __nth);
3906       __glibcxx_requires_valid_range(__nth, __last);
3907
3908       while (__last - __first > 3)
3909         {
3910           _RandomAccessIterator __cut =
3911             std::__unguarded_partition(__first, __last,
3912                                        _ValueType(std::__median(*__first,
3913                                                                 *(__first
3914                                                                   + (__last
3915                                                                      - __first)
3916                                                                   / 2),
3917                                                                 *(__last - 1),
3918                                                               __comp)), __comp);
3919           if (__cut <= __nth)
3920             __first = __cut;
3921           else
3922             __last = __cut;
3923         }
3924       std::__insertion_sort(__first, __last, __comp);
3925     }
3926
3927   /**
3928    *  @brief Finds the largest subrange in which @a val could be inserted
3929    *         at any place in it without changing the ordering.
3930    *  @param  first   An iterator.
3931    *  @param  last    Another iterator.
3932    *  @param  val     The search term.
3933    *  @return  An pair of iterators defining the subrange.
3934    *  @ingroup binarysearch
3935    *
3936    *  This is equivalent to
3937    *  @code
3938    *    std::make_pair(lower_bound(first, last, val),
3939    *                   upper_bound(first, last, val))
3940    *  @endcode
3941    *  but does not actually call those functions.
3942   */
3943   template<typename _ForwardIterator, typename _Tp>
3944     pair<_ForwardIterator, _ForwardIterator>
3945     equal_range(_ForwardIterator __first, _ForwardIterator __last,
3946                 const _Tp& __val)
3947     {
3948       typedef typename iterator_traits<_ForwardIterator>::value_type
3949         _ValueType;
3950       typedef typename iterator_traits<_ForwardIterator>::difference_type
3951         _DistanceType;
3952
3953       // concept requirements
3954       // See comments on lower_bound.
3955       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
3956       __glibcxx_function_requires(_SameTypeConcept<_Tp, _ValueType>)
3957       __glibcxx_function_requires(_LessThanComparableConcept<_Tp>)
3958       __glibcxx_requires_partitioned(__first, __last, __val);
3959
3960       _DistanceType __len = std::distance(__first, __last);
3961       _DistanceType __half;
3962       _ForwardIterator __middle, __left, __right;
3963
3964       while (__len > 0)
3965         {
3966           __half = __len >> 1;
3967           __middle = __first;
3968           std::advance(__middle, __half);
3969           if (*__middle < __val)
3970             {
3971               __first = __middle;
3972               ++__first;
3973               __len = __len - __half - 1;
3974             }
3975           else if (__val < *__middle)
3976             __len = __half;
3977           else
3978             {
3979               __left = std::lower_bound(__first, __middle, __val);
3980               std::advance(__first, __len);
3981               __right = std::upper_bound(++__middle, __first, __val);
3982               return pair<_ForwardIterator, _ForwardIterator>(__left, __right);
3983             }
3984         }
3985       return pair<_ForwardIterator, _ForwardIterator>(__first, __first);
3986     }
3987
3988   /**
3989    *  @brief Finds the largest subrange in which @a val could be inserted
3990    *         at any place in it without changing the ordering.
3991    *  @param  first   An iterator.
3992    *  @param  last    Another iterator.
3993    *  @param  val     The search term.
3994    *  @param  comp    A functor to use for comparisons.
3995    *  @return  An pair of iterators defining the subrange.
3996    *  @ingroup binarysearch
3997    *
3998    *  This is equivalent to
3999    *  @code
4000    *    std::make_pair(lower_bound(first, last, val, comp),
4001    *                   upper_bound(first, last, val, comp))
4002    *  @endcode
4003    *  but does not actually call those functions.
4004   */
4005   template<typename _ForwardIterator, typename _Tp, typename _Compare>
4006     pair<_ForwardIterator, _ForwardIterator>
4007     equal_range(_ForwardIterator __first, _ForwardIterator __last,
4008                 const _Tp& __val,
4009                 _Compare __comp)
4010     {
4011       typedef typename iterator_traits<_ForwardIterator>::value_type
4012         _ValueType;
4013       typedef typename iterator_traits<_ForwardIterator>::difference_type
4014         _DistanceType;
4015
4016       // concept requirements
4017       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
4018       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
4019                                   _ValueType, _Tp>)
4020       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
4021                                   _Tp, _ValueType>)
4022       __glibcxx_requires_partitioned_pred(__first, __last, __val, __comp);
4023
4024       _DistanceType __len = std::distance(__first, __last);
4025       _DistanceType __half;
4026       _ForwardIterator __middle, __left, __right;
4027
4028       while (__len > 0)
4029         {
4030           __half = __len >> 1;
4031           __middle = __first;
4032           std::advance(__middle, __half);
4033           if (__comp(*__middle, __val))
4034             {
4035               __first = __middle;
4036               ++__first;
4037               __len = __len - __half - 1;
4038             }
4039           else if (__comp(__val, *__middle))
4040             __len = __half;
4041           else
4042             {
4043               __left = std::lower_bound(__first, __middle, __val, __comp);
4044               std::advance(__first, __len);
4045               __right = std::upper_bound(++__middle, __first, __val, __comp);
4046               return pair<_ForwardIterator, _ForwardIterator>(__left, __right);
4047             }
4048         }
4049       return pair<_ForwardIterator, _ForwardIterator>(__first, __first);
4050     }
4051
4052   /**
4053    *  @brief Determines whether an element exists in a range.
4054    *  @param  first   An iterator.
4055    *  @param  last    Another iterator.
4056    *  @param  val     The search term.
4057    *  @return  True if @a val (or its equivelent) is in [@a first,@a last ].
4058    *  @ingroup binarysearch
4059    *
4060    *  Note that this does not actually return an iterator to @a val.  For
4061    *  that, use std::find or a container's specialized find member functions.
4062   */
4063   template<typename _ForwardIterator, typename _Tp>
4064     bool
4065     binary_search(_ForwardIterator __first, _ForwardIterator __last,
4066                   const _Tp& __val)
4067     {
4068       // concept requirements
4069       // See comments on lower_bound.
4070       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
4071       __glibcxx_function_requires(_SameTypeConcept<_Tp,
4072                 typename iterator_traits<_ForwardIterator>::value_type>)
4073       __glibcxx_function_requires(_LessThanComparableConcept<_Tp>)
4074       __glibcxx_requires_partitioned(__first, __last, __val);
4075
4076       _ForwardIterator __i = std::lower_bound(__first, __last, __val);
4077       return __i != __last && !(__val < *__i);
4078     }
4079
4080   /**
4081    *  @brief Determines whether an element exists in a range.
4082    *  @param  first   An iterator.
4083    *  @param  last    Another iterator.
4084    *  @param  val     The search term.
4085    *  @param  comp    A functor to use for comparisons.
4086    *  @return  True if @a val (or its equivelent) is in [@a first,@a last ].
4087    *  @ingroup binarysearch
4088    *
4089    *  Note that this does not actually return an iterator to @a val.  For
4090    *  that, use std::find or a container's specialized find member functions.
4091    *
4092    *  The comparison function should have the same effects on ordering as
4093    *  the function used for the initial sort.
4094   */
4095   template<typename _ForwardIterator, typename _Tp, typename _Compare>
4096     bool
4097     binary_search(_ForwardIterator __first, _ForwardIterator __last,
4098                   const _Tp& __val, _Compare __comp)
4099     {
4100       // concept requirements
4101       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
4102       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
4103                 typename iterator_traits<_ForwardIterator>::value_type, _Tp>)
4104       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, _Tp,
4105                 typename iterator_traits<_ForwardIterator>::value_type>)
4106       __glibcxx_requires_partitioned_pred(__first, __last, __val, __comp);
4107
4108       _ForwardIterator __i = std::lower_bound(__first, __last, __val, __comp);
4109       return __i != __last && !__comp(__val, *__i);
4110     }
4111
4112   // Set algorithms: includes, set_union, set_intersection, set_difference,
4113   // set_symmetric_difference.  All of these algorithms have the precondition
4114   // that their input ranges are sorted and the postcondition that their output
4115   // ranges are sorted.
4116
4117   /**
4118    *  @brief Determines whether all elements of a sequence exists in a range.
4119    *  @param  first1  Start of search range.
4120    *  @param  last1   End of search range.
4121    *  @param  first2  Start of sequence
4122    *  @param  last2   End of sequence.
4123    *  @return  True if each element in [first2,last2) is contained in order
4124    *  within [first1,last1).  False otherwise.
4125    *  @ingroup setoperations
4126    *
4127    *  This operation expects both [first1,last1) and [first2,last2) to be
4128    *  sorted.  Searches for the presence of each element in [first2,last2)
4129    *  within [first1,last1).  The iterators over each range only move forward,
4130    *  so this is a linear algorithm.  If an element in [first2,last2) is not
4131    *  found before the search iterator reaches @a last2, false is returned.
4132   */
4133   template<typename _InputIterator1, typename _InputIterator2>
4134     bool
4135     includes(_InputIterator1 __first1, _InputIterator1 __last1,
4136              _InputIterator2 __first2, _InputIterator2 __last2)
4137     {
4138       // concept requirements
4139       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
4140       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
4141       __glibcxx_function_requires(_SameTypeConcept<
4142             typename iterator_traits<_InputIterator1>::value_type,
4143             typename iterator_traits<_InputIterator2>::value_type>)
4144       __glibcxx_function_requires(_LessThanComparableConcept<
4145             typename iterator_traits<_InputIterator1>::value_type>)
4146       __glibcxx_requires_sorted(__first1, __last1);
4147       __glibcxx_requires_sorted(__first2, __last2);
4148
4149       while (__first1 != __last1 && __first2 != __last2)
4150         if (*__first2 < *__first1)
4151           return false;
4152         else if(*__first1 < *__first2)
4153           ++__first1;
4154         else
4155           ++__first1, ++__first2;
4156
4157       return __first2 == __last2;
4158     }
4159
4160   /**
4161    *  @brief Determines whether all elements of a sequence exists in a range
4162    *  using comparison.
4163    *  @param  first1  Start of search range.
4164    *  @param  last1   End of search range.
4165    *  @param  first2  Start of sequence
4166    *  @param  last2   End of sequence.
4167    *  @param  comp    Comparison function to use.
4168    *  @return  True if each element in [first2,last2) is contained in order
4169    *  within [first1,last1) according to comp.  False otherwise.
4170    *  @ingroup setoperations
4171    *
4172    *  This operation expects both [first1,last1) and [first2,last2) to be
4173    *  sorted.  Searches for the presence of each element in [first2,last2)
4174    *  within [first1,last1), using comp to decide.  The iterators over each
4175    *  range only move forward, so this is a linear algorithm.  If an element
4176    *  in [first2,last2) is not found before the search iterator reaches @a
4177    *  last2, false is returned.
4178   */
4179   template<typename _InputIterator1, typename _InputIterator2,
4180            typename _Compare>
4181     bool
4182     includes(_InputIterator1 __first1, _InputIterator1 __last1,
4183              _InputIterator2 __first2, _InputIterator2 __last2, _Compare __comp)
4184     {
4185       // concept requirements
4186       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
4187       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
4188       __glibcxx_function_requires(_SameTypeConcept<
4189             typename iterator_traits<_InputIterator1>::value_type,
4190             typename iterator_traits<_InputIterator2>::value_type>)
4191       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
4192             typename iterator_traits<_InputIterator1>::value_type,
4193             typename iterator_traits<_InputIterator2>::value_type>)
4194       __glibcxx_requires_sorted_pred(__first1, __last1, __comp);
4195       __glibcxx_requires_sorted_pred(__first2, __last2, __comp);
4196
4197       while (__first1 != __last1 && __first2 != __last2)
4198         if (__comp(*__first2, *__first1))
4199           return false;
4200         else if(__comp(*__first1, *__first2))
4201           ++__first1;
4202         else
4203           ++__first1, ++__first2;
4204
4205       return __first2 == __last2;
4206     }
4207
4208   /**
4209    *  @brief Return the union of two sorted ranges.
4210    *  @param  first1  Start of first range.
4211    *  @param  last1   End of first range.
4212    *  @param  first2  Start of second range.
4213    *  @param  last2   End of second range.
4214    *  @return  End of the output range.
4215    *  @ingroup setoperations
4216    *
4217    *  This operation iterates over both ranges, copying elements present in
4218    *  each range in order to the output range.  Iterators increment for each
4219    *  range.  When the current element of one range is less than the other,
4220    *  that element is copied and the iterator advanced.  If an element is
4221    *  contained in both ranges, the element from the first range is copied and
4222    *  both ranges advance.  The output range may not overlap either input
4223    *  range.
4224   */
4225   template<typename _InputIterator1, typename _InputIterator2,
4226            typename _OutputIterator>
4227     _OutputIterator
4228     set_union(_InputIterator1 __first1, _InputIterator1 __last1,
4229               _InputIterator2 __first2, _InputIterator2 __last2,
4230               _OutputIterator __result)
4231     {
4232       // concept requirements
4233       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
4234       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
4235       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
4236             typename iterator_traits<_InputIterator1>::value_type>)
4237       __glibcxx_function_requires(_SameTypeConcept<
4238             typename iterator_traits<_InputIterator1>::value_type,
4239             typename iterator_traits<_InputIterator2>::value_type>)
4240       __glibcxx_function_requires(_LessThanComparableConcept<
4241             typename iterator_traits<_InputIterator1>::value_type>)
4242       __glibcxx_requires_sorted(__first1, __last1);
4243       __glibcxx_requires_sorted(__first2, __last2);
4244
4245       while (__first1 != __last1 && __first2 != __last2)
4246         {
4247           if (*__first1 < *__first2)
4248             {
4249               *__result = *__first1;
4250               ++__first1;
4251             }
4252           else if (*__first2 < *__first1)
4253             {
4254               *__result = *__first2;
4255               ++__first2;
4256             }
4257           else
4258             {
4259               *__result = *__first1;
4260               ++__first1;
4261               ++__first2;
4262             }
4263           ++__result;
4264         }
4265       return std::copy(__first2, __last2, std::copy(__first1, __last1,
4266                                                     __result));
4267     }
4268
4269   /**
4270    *  @brief Return the union of two sorted ranges using a comparison functor.
4271    *  @param  first1  Start of first range.
4272    *  @param  last1   End of first range.
4273    *  @param  first2  Start of second range.
4274    *  @param  last2   End of second range.
4275    *  @param  comp    The comparison functor.
4276    *  @return  End of the output range.
4277    *  @ingroup setoperations
4278    *
4279    *  This operation iterates over both ranges, copying elements present in
4280    *  each range in order to the output range.  Iterators increment for each
4281    *  range.  When the current element of one range is less than the other
4282    *  according to @a comp, that element is copied and the iterator advanced.
4283    *  If an equivalent element according to @a comp is contained in both
4284    *  ranges, the element from the first range is copied and both ranges
4285    *  advance.  The output range may not overlap either input range.
4286   */
4287   template<typename _InputIterator1, typename _InputIterator2,
4288            typename _OutputIterator, typename _Compare>
4289     _OutputIterator
4290     set_union(_InputIterator1 __first1, _InputIterator1 __last1,
4291               _InputIterator2 __first2, _InputIterator2 __last2,
4292               _OutputIterator __result, _Compare __comp)
4293     {
4294       // concept requirements
4295       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
4296       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
4297       __glibcxx_function_requires(_SameTypeConcept<
4298             typename iterator_traits<_InputIterator1>::value_type,
4299             typename iterator_traits<_InputIterator2>::value_type>)
4300       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
4301             typename iterator_traits<_InputIterator1>::value_type>)
4302       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
4303             typename iterator_traits<_InputIterator1>::value_type,
4304             typename iterator_traits<_InputIterator2>::value_type>)
4305       __glibcxx_requires_sorted_pred(__first1, __last1, __comp);
4306       __glibcxx_requires_sorted_pred(__first2, __last2, __comp);
4307
4308       while (__first1 != __last1 && __first2 != __last2)
4309         {
4310           if (__comp(*__first1, *__first2))
4311             {
4312               *__result = *__first1;
4313               ++__first1;
4314             }
4315           else if (__comp(*__first2, *__first1))
4316             {
4317               *__result = *__first2;
4318               ++__first2;
4319             }
4320           else
4321             {
4322               *__result = *__first1;
4323               ++__first1;
4324               ++__first2;
4325             }
4326           ++__result;
4327         }
4328       return std::copy(__first2, __last2, std::copy(__first1, __last1,
4329                                                     __result));
4330     }
4331
4332   /**
4333    *  @brief Return the intersection of two sorted ranges.
4334    *  @param  first1  Start of first range.
4335    *  @param  last1   End of first range.
4336    *  @param  first2  Start of second range.
4337    *  @param  last2   End of second range.
4338    *  @return  End of the output range.
4339    *  @ingroup setoperations
4340    *
4341    *  This operation iterates over both ranges, copying elements present in
4342    *  both ranges in order to the output range.  Iterators increment for each
4343    *  range.  When the current element of one range is less than the other,
4344    *  that iterator advances.  If an element is contained in both ranges, the
4345    *  element from the first range is copied and both ranges advance.  The
4346    *  output range may not overlap either input range.
4347   */
4348   template<typename _InputIterator1, typename _InputIterator2,
4349            typename _OutputIterator>
4350     _OutputIterator
4351     set_intersection(_InputIterator1 __first1, _InputIterator1 __last1,
4352                      _InputIterator2 __first2, _InputIterator2 __last2,
4353                      _OutputIterator __result)
4354     {
4355       // concept requirements
4356       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
4357       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
4358       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
4359             typename iterator_traits<_InputIterator1>::value_type>)
4360       __glibcxx_function_requires(_SameTypeConcept<
4361             typename iterator_traits<_InputIterator1>::value_type,
4362             typename iterator_traits<_InputIterator2>::value_type>)
4363       __glibcxx_function_requires(_LessThanComparableConcept<
4364             typename iterator_traits<_InputIterator1>::value_type>)
4365       __glibcxx_requires_sorted(__first1, __last1);
4366       __glibcxx_requires_sorted(__first2, __last2);
4367
4368       while (__first1 != __last1 && __first2 != __last2)
4369         if (*__first1 < *__first2)
4370           ++__first1;
4371         else if (*__first2 < *__first1)
4372           ++__first2;
4373         else
4374           {
4375             *__result = *__first1;
4376             ++__first1;
4377             ++__first2;
4378             ++__result;
4379           }
4380       return __result;
4381     }
4382
4383   /**
4384    *  @brief Return the intersection of two sorted ranges using comparison
4385    *  functor.
4386    *  @param  first1  Start of first range.
4387    *  @param  last1   End of first range.
4388    *  @param  first2  Start of second range.
4389    *  @param  last2   End of second range.
4390    *  @param  comp    The comparison functor.
4391    *  @return  End of the output range.
4392    *  @ingroup setoperations
4393    *
4394    *  This operation iterates over both ranges, copying elements present in
4395    *  both ranges in order to the output range.  Iterators increment for each
4396    *  range.  When the current element of one range is less than the other
4397    *  according to @a comp, that iterator advances.  If an element is
4398    *  contained in both ranges according to @a comp, the element from the
4399    *  first range is copied and both ranges advance.  The output range may not
4400    *  overlap either input range.
4401   */
4402   template<typename _InputIterator1, typename _InputIterator2,
4403            typename _OutputIterator, typename _Compare>
4404     _OutputIterator
4405     set_intersection(_InputIterator1 __first1, _InputIterator1 __last1,
4406                      _InputIterator2 __first2, _InputIterator2 __last2,
4407                      _OutputIterator __result, _Compare __comp)
4408     {
4409       // concept requirements
4410       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
4411       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
4412       __glibcxx_function_requires(_SameTypeConcept<
4413             typename iterator_traits<_InputIterator1>::value_type,
4414             typename iterator_traits<_InputIterator2>::value_type>)
4415       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
4416             typename iterator_traits<_InputIterator1>::value_type>)
4417       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
4418             typename iterator_traits<_InputIterator1>::value_type,
4419             typename iterator_traits<_InputIterator2>::value_type>)
4420       __glibcxx_requires_sorted_pred(__first1, __last1, __comp);
4421       __glibcxx_requires_sorted_pred(__first2, __last2, __comp);
4422
4423       while (__first1 != __last1 && __first2 != __last2)
4424         if (__comp(*__first1, *__first2))
4425           ++__first1;
4426         else if (__comp(*__first2, *__first1))
4427           ++__first2;
4428         else
4429           {
4430             *__result = *__first1;
4431             ++__first1;
4432             ++__first2;
4433             ++__result;
4434           }
4435       return __result;
4436     }
4437
4438   /**
4439    *  @brief Return the difference of two sorted ranges.
4440    *  @param  first1  Start of first range.
4441    *  @param  last1   End of first range.
4442    *  @param  first2  Start of second range.
4443    *  @param  last2   End of second range.
4444    *  @return  End of the output range.
4445    *  @ingroup setoperations
4446    *
4447    *  This operation iterates over both ranges, copying elements present in
4448    *  the first range but not the second in order to the output range.
4449    *  Iterators increment for each range.  When the current element of the
4450    *  first range is less than the second, that element is copied and the
4451    *  iterator advances.  If the current element of the second range is less,
4452    *  the iterator advances, but no element is copied.  If an element is
4453    *  contained in both ranges, no elements are copied and both ranges
4454    *  advance.  The output range may not overlap either input range.
4455   */
4456   template<typename _InputIterator1, typename _InputIterator2,
4457            typename _OutputIterator>
4458     _OutputIterator
4459     set_difference(_InputIterator1 __first1, _InputIterator1 __last1,
4460                    _InputIterator2 __first2, _InputIterator2 __last2,
4461                    _OutputIterator __result)
4462     {
4463       // concept requirements
4464       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
4465       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
4466       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
4467             typename iterator_traits<_InputIterator1>::value_type>)
4468       __glibcxx_function_requires(_SameTypeConcept<
4469             typename iterator_traits<_InputIterator1>::value_type,
4470             typename iterator_traits<_InputIterator2>::value_type>)
4471       __glibcxx_function_requires(_LessThanComparableConcept<
4472             typename iterator_traits<_InputIterator1>::value_type>)
4473       __glibcxx_requires_sorted(__first1, __last1);
4474       __glibcxx_requires_sorted(__first2, __last2);
4475
4476       while (__first1 != __last1 && __first2 != __last2)
4477         if (*__first1 < *__first2)
4478           {
4479             *__result = *__first1;
4480             ++__first1;
4481             ++__result;
4482           }
4483         else if (*__first2 < *__first1)
4484           ++__first2;
4485         else
4486           {
4487             ++__first1;
4488             ++__first2;
4489           }
4490       return std::copy(__first1, __last1, __result);
4491     }
4492
4493   /**
4494    *  @brief  Return the difference of two sorted ranges using comparison
4495    *  functor.
4496    *  @param  first1  Start of first range.
4497    *  @param  last1   End of first range.
4498    *  @param  first2  Start of second range.
4499    *  @param  last2   End of second range.
4500    *  @param  comp    The comparison functor.
4501    *  @return  End of the output range.
4502    *  @ingroup setoperations
4503    *
4504    *  This operation iterates over both ranges, copying elements present in
4505    *  the first range but not the second in order to the output range.
4506    *  Iterators increment for each range.  When the current element of the
4507    *  first range is less than the second according to @a comp, that element
4508    *  is copied and the iterator advances.  If the current element of the
4509    *  second range is less, no element is copied and the iterator advances.
4510    *  If an element is contained in both ranges according to @a comp, no
4511    *  elements are copied and both ranges advance.  The output range may not
4512    *  overlap either input range.
4513   */
4514   template<typename _InputIterator1, typename _InputIterator2,
4515            typename _OutputIterator, typename _Compare>
4516     _OutputIterator
4517     set_difference(_InputIterator1 __first1, _InputIterator1 __last1,
4518                    _InputIterator2 __first2, _InputIterator2 __last2,
4519                    _OutputIterator __result, _Compare __comp)
4520     {
4521       // concept requirements
4522       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
4523       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
4524       __glibcxx_function_requires(_SameTypeConcept<
4525             typename iterator_traits<_InputIterator1>::value_type,
4526             typename iterator_traits<_InputIterator2>::value_type>)
4527       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
4528             typename iterator_traits<_InputIterator1>::value_type>)
4529       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
4530             typename iterator_traits<_InputIterator1>::value_type,
4531             typename iterator_traits<_InputIterator2>::value_type>)
4532       __glibcxx_requires_sorted_pred(__first1, __last1, __comp);
4533       __glibcxx_requires_sorted_pred(__first2, __last2, __comp);
4534
4535       while (__first1 != __last1 && __first2 != __last2)
4536         if (__comp(*__first1, *__first2))
4537           {
4538             *__result = *__first1;
4539             ++__first1;
4540             ++__result;
4541           }
4542         else if (__comp(*__first2, *__first1))
4543           ++__first2;
4544         else
4545           {
4546             ++__first1;
4547             ++__first2;
4548           }
4549       return std::copy(__first1, __last1, __result);
4550     }
4551
4552   /**
4553    *  @brief  Return the symmetric difference of two sorted ranges.
4554    *  @param  first1  Start of first range.
4555    *  @param  last1   End of first range.
4556    *  @param  first2  Start of second range.
4557    *  @param  last2   End of second range.
4558    *  @return  End of the output range.
4559    *  @ingroup setoperations
4560    *
4561    *  This operation iterates over both ranges, copying elements present in
4562    *  one range but not the other in order to the output range.  Iterators
4563    *  increment for each range.  When the current element of one range is less
4564    *  than the other, that element is copied and the iterator advances.  If an
4565    *  element is contained in both ranges, no elements are copied and both
4566    *  ranges advance.  The output range may not overlap either input range.
4567   */
4568   template<typename _InputIterator1, typename _InputIterator2,
4569            typename _OutputIterator>
4570     _OutputIterator
4571     set_symmetric_difference(_InputIterator1 __first1, _InputIterator1 __last1,
4572                              _InputIterator2 __first2, _InputIterator2 __last2,
4573                              _OutputIterator __result)
4574     {
4575       // concept requirements
4576       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
4577       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
4578       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
4579             typename iterator_traits<_InputIterator1>::value_type>)
4580       __glibcxx_function_requires(_SameTypeConcept<
4581             typename iterator_traits<_InputIterator1>::value_type,
4582             typename iterator_traits<_InputIterator2>::value_type>)
4583       __glibcxx_function_requires(_LessThanComparableConcept<
4584             typename iterator_traits<_InputIterator1>::value_type>)
4585       __glibcxx_requires_sorted(__first1, __last1);
4586       __glibcxx_requires_sorted(__first2, __last2);
4587
4588       while (__first1 != __last1 && __first2 != __last2)
4589         if (*__first1 < *__first2)
4590           {
4591             *__result = *__first1;
4592             ++__first1;
4593             ++__result;
4594           }
4595         else if (*__first2 < *__first1)
4596           {
4597             *__result = *__first2;
4598             ++__first2;
4599             ++__result;
4600           }
4601         else
4602           {
4603             ++__first1;
4604             ++__first2;
4605           }
4606       return std::copy(__first2, __last2, std::copy(__first1,
4607                                                     __last1, __result));
4608     }
4609
4610   /**
4611    *  @brief  Return the symmetric difference of two sorted ranges using
4612    *  comparison functor.
4613    *  @param  first1  Start of first range.
4614    *  @param  last1   End of first range.
4615    *  @param  first2  Start of second range.
4616    *  @param  last2   End of second range.
4617    *  @param  comp    The comparison functor.
4618    *  @return  End of the output range.
4619    *  @ingroup setoperations
4620    *
4621    *  This operation iterates over both ranges, copying elements present in
4622    *  one range but not the other in order to the output range.  Iterators
4623    *  increment for each range.  When the current element of one range is less
4624    *  than the other according to @a comp, that element is copied and the
4625    *  iterator advances.  If an element is contained in both ranges according
4626    *  to @a comp, no elements are copied and both ranges advance.  The output
4627    *  range may not overlap either input range.
4628   */
4629   template<typename _InputIterator1, typename _InputIterator2,
4630            typename _OutputIterator, typename _Compare>
4631     _OutputIterator
4632     set_symmetric_difference(_InputIterator1 __first1, _InputIterator1 __last1,
4633                              _InputIterator2 __first2, _InputIterator2 __last2,
4634                              _OutputIterator __result,
4635                              _Compare __comp)
4636     {
4637       // concept requirements
4638       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
4639       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
4640       __glibcxx_function_requires(_SameTypeConcept<
4641             typename iterator_traits<_InputIterator1>::value_type,
4642             typename iterator_traits<_InputIterator2>::value_type>)
4643       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
4644             typename iterator_traits<_InputIterator1>::value_type>)
4645       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
4646             typename iterator_traits<_InputIterator1>::value_type,
4647             typename iterator_traits<_InputIterator2>::value_type>)
4648       __glibcxx_requires_sorted_pred(__first1, __last1, __comp);
4649       __glibcxx_requires_sorted_pred(__first2, __last2, __comp);
4650
4651       while (__first1 != __last1 && __first2 != __last2)
4652         if (__comp(*__first1, *__first2))
4653           {
4654             *__result = *__first1;
4655             ++__first1;
4656             ++__result;
4657           }
4658         else if (__comp(*__first2, *__first1))
4659           {
4660             *__result = *__first2;
4661             ++__first2;
4662             ++__result;
4663           }
4664         else
4665           {
4666             ++__first1;
4667             ++__first2;
4668           }
4669       return std::copy(__first2, __last2, std::copy(__first1,
4670                                                     __last1, __result));
4671     }
4672
4673   // min_element and max_element, with and without an explicitly supplied
4674   // comparison function.
4675
4676   /**
4677    *  @brief  Return the maximum element in a range.
4678    *  @param  first  Start of range.
4679    *  @param  last   End of range.
4680    *  @return  Iterator referencing the first instance of the largest value.
4681   */
4682   template<typename _ForwardIterator>
4683     _ForwardIterator
4684     max_element(_ForwardIterator __first, _ForwardIterator __last)
4685     {
4686       // concept requirements
4687       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
4688       __glibcxx_function_requires(_LessThanComparableConcept<
4689             typename iterator_traits<_ForwardIterator>::value_type>)
4690       __glibcxx_requires_valid_range(__first, __last);
4691
4692       if (__first == __last)
4693         return __first;
4694       _ForwardIterator __result = __first;
4695       while (++__first != __last)
4696         if (*__result < *__first)
4697           __result = __first;
4698       return __result;
4699     }
4700
4701   /**
4702    *  @brief  Return the maximum element in a range using comparison functor.
4703    *  @param  first  Start of range.
4704    *  @param  last   End of range.
4705    *  @param  comp   Comparison functor.
4706    *  @return  Iterator referencing the first instance of the largest value
4707    *  according to comp.
4708   */
4709   template<typename _ForwardIterator, typename _Compare>
4710     _ForwardIterator
4711     max_element(_ForwardIterator __first, _ForwardIterator __last,
4712                 _Compare __comp)
4713     {
4714       // concept requirements
4715       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
4716       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
4717             typename iterator_traits<_ForwardIterator>::value_type,
4718             typename iterator_traits<_ForwardIterator>::value_type>)
4719       __glibcxx_requires_valid_range(__first, __last);
4720
4721       if (__first == __last) return __first;
4722       _ForwardIterator __result = __first;
4723       while (++__first != __last)
4724         if (__comp(*__result, *__first)) __result = __first;
4725       return __result;
4726     }
4727
4728   /**
4729    *  @brief  Return the minimum element in a range.
4730    *  @param  first  Start of range.
4731    *  @param  last   End of range.
4732    *  @return  Iterator referencing the first instance of the smallest value.
4733   */
4734   template<typename _ForwardIterator>
4735     _ForwardIterator
4736     min_element(_ForwardIterator __first, _ForwardIterator __last)
4737     {
4738       // concept requirements
4739       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
4740       __glibcxx_function_requires(_LessThanComparableConcept<
4741             typename iterator_traits<_ForwardIterator>::value_type>)
4742       __glibcxx_requires_valid_range(__first, __last);
4743
4744       if (__first == __last)
4745         return __first;
4746       _ForwardIterator __result = __first;
4747       while (++__first != __last)
4748         if (*__first < *__result)
4749           __result = __first;
4750       return __result;
4751     }
4752
4753   /**
4754    *  @brief  Return the minimum element in a range using comparison functor.
4755    *  @param  first  Start of range.
4756    *  @param  last   End of range.
4757    *  @param  comp   Comparison functor.
4758    *  @return  Iterator referencing the first instance of the smallest value
4759    *  according to comp.
4760   */
4761   template<typename _ForwardIterator, typename _Compare>
4762     _ForwardIterator
4763     min_element(_ForwardIterator __first, _ForwardIterator __last,
4764                 _Compare __comp)
4765     {
4766       // concept requirements
4767       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
4768       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
4769             typename iterator_traits<_ForwardIterator>::value_type,
4770             typename iterator_traits<_ForwardIterator>::value_type>)
4771       __glibcxx_requires_valid_range(__first, __last);
4772
4773       if (__first == __last)
4774         return __first;
4775       _ForwardIterator __result = __first;
4776       while (++__first != __last)
4777         if (__comp(*__first, *__result))
4778           __result = __first;
4779       return __result;
4780     }
4781
4782   // next_permutation and prev_permutation, with and without an explicitly
4783   // supplied comparison function.
4784
4785   /**
4786    *  @brief  Permute range into the next "dictionary" ordering.
4787    *  @param  first  Start of range.
4788    *  @param  last   End of range.
4789    *  @return  False if wrapped to first permutation, true otherwise.
4790    *
4791    *  Treats all permutations of the range as a set of "dictionary" sorted
4792    *  sequences.  Permutes the current sequence into the next one of this set.
4793    *  Returns true if there are more sequences to generate.  If the sequence
4794    *  is the largest of the set, the smallest is generated and false returned.
4795   */
4796   template<typename _BidirectionalIterator>
4797     bool
4798     next_permutation(_BidirectionalIterator __first,
4799                      _BidirectionalIterator __last)
4800     {
4801       // concept requirements
4802       __glibcxx_function_requires(_BidirectionalIteratorConcept<
4803                                   _BidirectionalIterator>)
4804       __glibcxx_function_requires(_LessThanComparableConcept<
4805             typename iterator_traits<_BidirectionalIterator>::value_type>)
4806       __glibcxx_requires_valid_range(__first, __last);
4807
4808       if (__first == __last)
4809         return false;
4810       _BidirectionalIterator __i = __first;
4811       ++__i;
4812       if (__i == __last)
4813         return false;
4814       __i = __last;
4815       --__i;
4816
4817       for(;;)
4818         {
4819           _BidirectionalIterator __ii = __i;
4820           --__i;
4821           if (*__i < *__ii)
4822             {
4823               _BidirectionalIterator __j = __last;
4824               while (!(*__i < *--__j))
4825                 {}
4826               std::iter_swap(__i, __j);
4827               std::reverse(__ii, __last);
4828               return true;
4829             }
4830           if (__i == __first)
4831             {
4832               std::reverse(__first, __last);
4833               return false;
4834             }
4835         }
4836     }
4837
4838   /**
4839    *  @brief  Permute range into the next "dictionary" ordering using
4840    *  comparison functor.
4841    *  @param  first  Start of range.
4842    *  @param  last   End of range.
4843    *  @param  comp
4844    *  @return  False if wrapped to first permutation, true otherwise.
4845    *
4846    *  Treats all permutations of the range [first,last) as a set of
4847    *  "dictionary" sorted sequences ordered by @a comp.  Permutes the current
4848    *  sequence into the next one of this set.  Returns true if there are more
4849    *  sequences to generate.  If the sequence is the largest of the set, the
4850    *  smallest is generated and false returned.
4851   */
4852   template<typename _BidirectionalIterator, typename _Compare>
4853     bool
4854     next_permutation(_BidirectionalIterator __first,
4855                      _BidirectionalIterator __last, _Compare __comp)
4856     {
4857       // concept requirements
4858       __glibcxx_function_requires(_BidirectionalIteratorConcept<
4859                                   _BidirectionalIterator>)
4860       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
4861             typename iterator_traits<_BidirectionalIterator>::value_type,
4862             typename iterator_traits<_BidirectionalIterator>::value_type>)
4863       __glibcxx_requires_valid_range(__first, __last);
4864
4865       if (__first == __last)
4866         return false;
4867       _BidirectionalIterator __i = __first;
4868       ++__i;
4869       if (__i == __last)
4870         return false;
4871       __i = __last;
4872       --__i;
4873
4874       for(;;)
4875         {
4876           _BidirectionalIterator __ii = __i;
4877           --__i;
4878           if (__comp(*__i, *__ii))
4879             {
4880               _BidirectionalIterator __j = __last;
4881               while (!__comp(*__i, *--__j))
4882                 {}
4883               std::iter_swap(__i, __j);
4884               std::reverse(__ii, __last);
4885               return true;
4886             }
4887           if (__i == __first)
4888             {
4889               std::reverse(__first, __last);
4890               return false;
4891             }
4892         }
4893     }
4894
4895   /**
4896    *  @brief  Permute range into the previous "dictionary" ordering.
4897    *  @param  first  Start of range.
4898    *  @param  last   End of range.
4899    *  @return  False if wrapped to last permutation, true otherwise.
4900    *
4901    *  Treats all permutations of the range as a set of "dictionary" sorted
4902    *  sequences.  Permutes the current sequence into the previous one of this
4903    *  set.  Returns true if there are more sequences to generate.  If the
4904    *  sequence is the smallest of the set, the largest is generated and false
4905    *  returned.
4906   */
4907   template<typename _BidirectionalIterator>
4908     bool
4909     prev_permutation(_BidirectionalIterator __first,
4910                      _BidirectionalIterator __last)
4911     {
4912       // concept requirements
4913       __glibcxx_function_requires(_BidirectionalIteratorConcept<
4914                                   _BidirectionalIterator>)
4915       __glibcxx_function_requires(_LessThanComparableConcept<
4916             typename iterator_traits<_BidirectionalIterator>::value_type>)
4917       __glibcxx_requires_valid_range(__first, __last);
4918
4919       if (__first == __last)
4920         return false;
4921       _BidirectionalIterator __i = __first;
4922       ++__i;
4923       if (__i == __last)
4924         return false;
4925       __i = __last;
4926       --__i;
4927
4928       for(;;)
4929         {
4930           _BidirectionalIterator __ii = __i;
4931           --__i;
4932           if (*__ii < *__i)
4933             {
4934               _BidirectionalIterator __j = __last;
4935               while (!(*--__j < *__i))
4936                 {}
4937               std::iter_swap(__i, __j);
4938               std::reverse(__ii, __last);
4939               return true;
4940             }
4941           if (__i == __first)
4942             {
4943               std::reverse(__first, __last);
4944               return false;
4945             }
4946         }
4947     }
4948
4949   /**
4950    *  @brief  Permute range into the previous "dictionary" ordering using
4951    *  comparison functor.
4952    *  @param  first  Start of range.
4953    *  @param  last   End of range.
4954    *  @param  comp
4955    *  @return  False if wrapped to last permutation, true otherwise.
4956    *
4957    *  Treats all permutations of the range [first,last) as a set of
4958    *  "dictionary" sorted sequences ordered by @a comp.  Permutes the current
4959    *  sequence into the previous one of this set.  Returns true if there are
4960    *  more sequences to generate.  If the sequence is the smallest of the set,
4961    *  the largest is generated and false returned.
4962   */
4963   template<typename _BidirectionalIterator, typename _Compare>
4964     bool
4965     prev_permutation(_BidirectionalIterator __first,
4966                      _BidirectionalIterator __last, _Compare __comp)
4967     {
4968       // concept requirements
4969       __glibcxx_function_requires(_BidirectionalIteratorConcept<
4970                                   _BidirectionalIterator>)
4971       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
4972             typename iterator_traits<_BidirectionalIterator>::value_type,
4973             typename iterator_traits<_BidirectionalIterator>::value_type>)
4974       __glibcxx_requires_valid_range(__first, __last);
4975
4976       if (__first == __last)
4977         return false;
4978       _BidirectionalIterator __i = __first;
4979       ++__i;
4980       if (__i == __last)
4981         return false;
4982       __i = __last;
4983       --__i;
4984
4985       for(;;)
4986         {
4987           _BidirectionalIterator __ii = __i;
4988           --__i;
4989           if (__comp(*__ii, *__i))
4990             {
4991               _BidirectionalIterator __j = __last;
4992               while (!__comp(*--__j, *__i))
4993                 {}
4994               std::iter_swap(__i, __j);
4995               std::reverse(__ii, __last);
4996               return true;
4997             }
4998           if (__i == __first)
4999             {
5000               std::reverse(__first, __last);
5001               return false;
5002             }
5003         }
5004     }
5005
5006   // find_first_of, with and without an explicitly supplied comparison function.
5007
5008   /**
5009    *  @brief  Find element from a set in a sequence.
5010    *  @param  first1  Start of range to search.
5011    *  @param  last1   End of range to search.
5012    *  @param  first2  Start of match candidates.
5013    *  @param  last2   End of match candidates.
5014    *  @return   The first iterator @c i in the range
5015    *  @p [first1,last1) such that @c *i == @p *(i2) such that i2 is an
5016    *  interator in [first2,last2), or @p last1 if no such iterator exists.
5017    *
5018    *  Searches the range @p [first1,last1) for an element that is equal to
5019    *  some element in the range [first2,last2).  If found, returns an iterator
5020    *  in the range [first1,last1), otherwise returns @p last1.
5021   */
5022   template<typename _InputIterator, typename _ForwardIterator>
5023     _InputIterator
5024     find_first_of(_InputIterator __first1, _InputIterator __last1,
5025                   _ForwardIterator __first2, _ForwardIterator __last2)
5026     {
5027       // concept requirements
5028       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
5029       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
5030       __glibcxx_function_requires(_EqualOpConcept<
5031             typename iterator_traits<_InputIterator>::value_type,
5032             typename iterator_traits<_ForwardIterator>::value_type>)
5033       __glibcxx_requires_valid_range(__first1, __last1);
5034       __glibcxx_requires_valid_range(__first2, __last2);
5035
5036       for ( ; __first1 != __last1; ++__first1)
5037         for (_ForwardIterator __iter = __first2; __iter != __last2; ++__iter)
5038           if (*__first1 == *__iter)
5039             return __first1;
5040       return __last1;
5041     }
5042
5043   /**
5044    *  @brief  Find element from a set in a sequence using a predicate.
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    *  @param  comp    Predicate to use.
5050    *  @return   The first iterator @c i in the range
5051    *  @p [first1,last1) such that @c comp(*i, @p *(i2)) is true and i2 is an
5052    *  interator in [first2,last2), or @p last1 if no such iterator exists.
5053    *
5054    *  Searches the range @p [first1,last1) for an element that is equal to
5055    *  some element in the range [first2,last2).  If found, returns an iterator in
5056    *  the range [first1,last1), otherwise returns @p last1.
5057   */
5058   template<typename _InputIterator, typename _ForwardIterator,
5059            typename _BinaryPredicate>
5060     _InputIterator
5061     find_first_of(_InputIterator __first1, _InputIterator __last1,
5062                   _ForwardIterator __first2, _ForwardIterator __last2,
5063                   _BinaryPredicate __comp)
5064     {
5065       // concept requirements
5066       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
5067       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
5068       __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
5069             typename iterator_traits<_InputIterator>::value_type,
5070             typename iterator_traits<_ForwardIterator>::value_type>)
5071       __glibcxx_requires_valid_range(__first1, __last1);
5072       __glibcxx_requires_valid_range(__first2, __last2);
5073
5074       for ( ; __first1 != __last1; ++__first1)
5075         for (_ForwardIterator __iter = __first2; __iter != __last2; ++__iter)
5076           if (__comp(*__first1, *__iter))
5077             return __first1;
5078       return __last1;
5079     }
5080
5081
5082   // find_end, with and without an explicitly supplied comparison function.
5083   // Search [first2, last2) as a subsequence in [first1, last1), and return
5084   // the *last* possible match.  Note that find_end for bidirectional iterators
5085   // is much faster than for forward iterators.
5086
5087   // find_end for forward iterators.
5088   template<typename _ForwardIterator1, typename _ForwardIterator2>
5089     _ForwardIterator1
5090     __find_end(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
5091                _ForwardIterator2 __first2, _ForwardIterator2 __last2,
5092                forward_iterator_tag, forward_iterator_tag)
5093     {
5094       if (__first2 == __last2)
5095         return __last1;
5096       else
5097         {
5098           _ForwardIterator1 __result = __last1;
5099           while (1)
5100             {
5101               _ForwardIterator1 __new_result
5102                 = std::search(__first1, __last1, __first2, __last2);
5103               if (__new_result == __last1)
5104                 return __result;
5105               else
5106                 {
5107                   __result = __new_result;
5108                   __first1 = __new_result;
5109                   ++__first1;
5110                 }
5111             }
5112         }
5113     }
5114
5115   template<typename _ForwardIterator1, typename _ForwardIterator2,
5116            typename _BinaryPredicate>
5117     _ForwardIterator1
5118     __find_end(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
5119                _ForwardIterator2 __first2, _ForwardIterator2 __last2,
5120                forward_iterator_tag, forward_iterator_tag,
5121                _BinaryPredicate __comp)
5122     {
5123       if (__first2 == __last2)
5124         return __last1;
5125       else
5126         {
5127           _ForwardIterator1 __result = __last1;
5128           while (1)
5129             {
5130               _ForwardIterator1 __new_result
5131                 = std::search(__first1, __last1, __first2, __last2, __comp);
5132               if (__new_result == __last1)
5133                 return __result;
5134               else
5135                 {
5136                   __result = __new_result;
5137                   __first1 = __new_result;
5138                   ++__first1;
5139                 }
5140             }
5141         }
5142     }
5143
5144   // find_end for bidirectional iterators.  Requires partial specialization.
5145   template<typename _BidirectionalIterator1, typename _BidirectionalIterator2>
5146     _BidirectionalIterator1
5147     __find_end(_BidirectionalIterator1 __first1,
5148                _BidirectionalIterator1 __last1,
5149                _BidirectionalIterator2 __first2,
5150                _BidirectionalIterator2 __last2,
5151                bidirectional_iterator_tag, bidirectional_iterator_tag)
5152     {
5153       // concept requirements
5154       __glibcxx_function_requires(_BidirectionalIteratorConcept<
5155                                   _BidirectionalIterator1>)
5156       __glibcxx_function_requires(_BidirectionalIteratorConcept<
5157                                   _BidirectionalIterator2>)
5158
5159       typedef reverse_iterator<_BidirectionalIterator1> _RevIterator1;
5160       typedef reverse_iterator<_BidirectionalIterator2> _RevIterator2;
5161
5162       _RevIterator1 __rlast1(__first1);
5163       _RevIterator2 __rlast2(__first2);
5164       _RevIterator1 __rresult = std::search(_RevIterator1(__last1), __rlast1,
5165                                             _RevIterator2(__last2), __rlast2);
5166
5167       if (__rresult == __rlast1)
5168         return __last1;
5169       else
5170         {
5171           _BidirectionalIterator1 __result = __rresult.base();
5172           std::advance(__result, -std::distance(__first2, __last2));
5173           return __result;
5174         }
5175     }
5176
5177   template<typename _BidirectionalIterator1, typename _BidirectionalIterator2,
5178            typename _BinaryPredicate>
5179     _BidirectionalIterator1
5180     __find_end(_BidirectionalIterator1 __first1,
5181                _BidirectionalIterator1 __last1,
5182                _BidirectionalIterator2 __first2,
5183                _BidirectionalIterator2 __last2,
5184                bidirectional_iterator_tag, bidirectional_iterator_tag,
5185                _BinaryPredicate __comp)
5186     {
5187       // concept requirements
5188       __glibcxx_function_requires(_BidirectionalIteratorConcept<
5189                                   _BidirectionalIterator1>)
5190       __glibcxx_function_requires(_BidirectionalIteratorConcept<
5191                                   _BidirectionalIterator2>)
5192
5193       typedef reverse_iterator<_BidirectionalIterator1> _RevIterator1;
5194       typedef reverse_iterator<_BidirectionalIterator2> _RevIterator2;
5195
5196       _RevIterator1 __rlast1(__first1);
5197       _RevIterator2 __rlast2(__first2);
5198       _RevIterator1 __rresult = std::search(_RevIterator1(__last1), __rlast1,
5199                                             _RevIterator2(__last2), __rlast2,
5200                                             __comp);
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   // Dispatching functions for find_end.
5213
5214   /**
5215    *  @brief  Find last matching subsequence in a sequence.
5216    *  @param  first1  Start of range to search.
5217    *  @param  last1   End of range to search.
5218    *  @param  first2  Start of sequence to match.
5219    *  @param  last2   End of sequence to match.
5220    *  @return   The last iterator @c i in the range
5221    *  @p [first1,last1-(last2-first2)) such that @c *(i+N) == @p *(first2+N)
5222    *  for each @c N in the range @p [0,last2-first2), or @p last1 if no
5223    *  such iterator exists.
5224    *
5225    *  Searches the range @p [first1,last1) for a sub-sequence that compares
5226    *  equal value-by-value with the sequence given by @p [first2,last2) and
5227    *  returns an iterator to the first element of the sub-sequence, or
5228    *  @p last1 if the sub-sequence is not found.  The sub-sequence will be the
5229    *  last such subsequence contained in [first,last1).
5230    *
5231    *  Because the sub-sequence must lie completely within the range
5232    *  @p [first1,last1) it must start at a position less than
5233    *  @p last1-(last2-first2) where @p last2-first2 is the length of the
5234    *  sub-sequence.
5235    *  This means that the returned iterator @c i will be in the range
5236    *  @p [first1,last1-(last2-first2))
5237   */
5238   template<typename _ForwardIterator1, typename _ForwardIterator2>
5239     inline _ForwardIterator1
5240     find_end(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
5241              _ForwardIterator2 __first2, _ForwardIterator2 __last2)
5242     {
5243       // concept requirements
5244       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator1>)
5245       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator2>)
5246       __glibcxx_function_requires(_EqualOpConcept<
5247             typename iterator_traits<_ForwardIterator1>::value_type,
5248             typename iterator_traits<_ForwardIterator2>::value_type>)
5249       __glibcxx_requires_valid_range(__first1, __last1);
5250       __glibcxx_requires_valid_range(__first2, __last2);
5251
5252       return std::__find_end(__first1, __last1, __first2, __last2,
5253                              std::__iterator_category(__first1),
5254                              std::__iterator_category(__first2));
5255     }
5256
5257   /**
5258    *  @brief  Find last matching subsequence in a sequence using a predicate.
5259    *  @param  first1  Start of range to search.
5260    *  @param  last1   End of range to search.
5261    *  @param  first2  Start of sequence to match.
5262    *  @param  last2   End of sequence to match.
5263    *  @param  comp    The predicate to use.
5264    *  @return   The last iterator @c i in the range
5265    *  @p [first1,last1-(last2-first2)) such that @c predicate(*(i+N), @p
5266    *  (first2+N)) is true for each @c N in the range @p [0,last2-first2), or
5267    *  @p last1 if no such iterator exists.
5268    *
5269    *  Searches the range @p [first1,last1) for a sub-sequence that compares
5270    *  equal value-by-value with the sequence given by @p [first2,last2) using
5271    *  comp as a predicate and returns an iterator to the first element of the
5272    *  sub-sequence, or @p last1 if the sub-sequence is not found.  The
5273    *  sub-sequence will be the last such subsequence contained in
5274    *  [first,last1).
5275    *
5276    *  Because the sub-sequence must lie completely within the range
5277    *  @p [first1,last1) it must start at a position less than
5278    *  @p last1-(last2-first2) where @p last2-first2 is the length of the
5279    *  sub-sequence.
5280    *  This means that the returned iterator @c i will be in the range
5281    *  @p [first1,last1-(last2-first2))
5282   */
5283   template<typename _ForwardIterator1, typename _ForwardIterator2,
5284            typename _BinaryPredicate>
5285     inline _ForwardIterator1
5286     find_end(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
5287              _ForwardIterator2 __first2, _ForwardIterator2 __last2,
5288              _BinaryPredicate __comp)
5289     {
5290       // concept requirements
5291       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator1>)
5292       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator2>)
5293       __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
5294             typename iterator_traits<_ForwardIterator1>::value_type,
5295             typename iterator_traits<_ForwardIterator2>::value_type>)
5296       __glibcxx_requires_valid_range(__first1, __last1);
5297       __glibcxx_requires_valid_range(__first2, __last2);
5298
5299       return std::__find_end(__first1, __last1, __first2, __last2,
5300                              std::__iterator_category(__first1),
5301                              std::__iterator_category(__first2),
5302                              __comp);
5303     }
5304
5305 } // namespace std
5306
5307 #endif /* _ALGO_H */