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

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