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