LCOV - code coverage report
Current view: top level - usr/include/c++/6/bits - stl_algo.h (source / functions) Hit Total Coverage
Test: coverage.info Lines: 8 117 6.8 %
Date: 2018-11-14 16:53:58 Functions: 2 22 9.1 %

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

Generated by: LCOV version 1.13