contrib/gcc-3.4/libstdc++-v3/include/bits/stl_algo.h

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