LCOV - code coverage report
Current view: top level - usr/include/c++/4.9/bits - stl_algo.h (source / functions) Hit Total Coverage
Test: coverage.info Lines: 8 118 6.8 %
Date: 2016-12-01 18:45:36 Functions: 2 22 9.1 %

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

Generated by: LCOV version 1.11