libstdc++
stl_algo.h
Go to the documentation of this file.
00001 // Algorithm implementation -*- C++ -*-
00002 
00003 // Copyright (C) 2001-2013 Free Software Foundation, Inc.
00004 //
00005 // This file is part of the GNU ISO C++ Library.  This library is free
00006 // software; you can redistribute it and/or modify it under the
00007 // terms of the GNU General Public License as published by the
00008 // Free Software Foundation; either version 3, or (at your option)
00009 // any later version.
00010 
00011 // This library is distributed in the hope that it will be useful,
00012 // but WITHOUT ANY WARRANTY; without even the implied warranty of
00013 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
00014 // GNU General Public License for more details.
00015 
00016 // Under Section 7 of GPL version 3, you are granted additional
00017 // permissions described in the GCC Runtime Library Exception, version
00018 // 3.1, as published by the Free Software Foundation.
00019 
00020 // You should have received a copy of the GNU General Public License and
00021 // a copy of the GCC Runtime Library Exception along with this program;
00022 // see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
00023 // <http://www.gnu.org/licenses/>.
00024 
00025 /*
00026  *
00027  * Copyright (c) 1994
00028  * Hewlett-Packard Company
00029  *
00030  * Permission to use, copy, modify, distribute and sell this software
00031  * and its documentation for any purpose is hereby granted without fee,
00032  * provided that the above copyright notice appear in all copies and
00033  * that both that copyright notice and this permission notice appear
00034  * in supporting documentation.  Hewlett-Packard Company makes no
00035  * representations about the suitability of this software for any
00036  * purpose.  It is provided "as is" without express or implied warranty.
00037  *
00038  *
00039  * Copyright (c) 1996
00040  * Silicon Graphics Computer Systems, Inc.
00041  *
00042  * Permission to use, copy, modify, distribute and sell this software
00043  * and its documentation for any purpose is hereby granted without fee,
00044  * provided that the above copyright notice appear in all copies and
00045  * that both that copyright notice and this permission notice appear
00046  * in supporting documentation.  Silicon Graphics makes no
00047  * representations about the suitability of this software for any
00048  * purpose.  It is provided "as is" without express or implied warranty.
00049  */
00050 
00051 /** @file bits/stl_algo.h
00052  *  This is an internal header file, included by other library headers.
00053  *  Do not attempt to use it directly. @headername{algorithm}
00054  */
00055 
00056 #ifndef _STL_ALGO_H
00057 #define _STL_ALGO_H 1
00058 
00059 #include <cstdlib>             // for rand
00060 #include <bits/algorithmfwd.h>
00061 #include <bits/stl_heap.h>
00062 #include <bits/stl_tempbuf.h>  // for _Temporary_buffer
00063 
00064 #if __cplusplus >= 201103L
00065 #include <random>     // for std::uniform_int_distribution
00066 #include <functional> // for std::bind
00067 #endif
00068 
00069 // See concept_check.h for the __glibcxx_*_requires macros.
00070 
00071 namespace std _GLIBCXX_VISIBILITY(default)
00072 {
00073 _GLIBCXX_BEGIN_NAMESPACE_VERSION
00074 
00075   /// Swaps the median value of *__a, *__b and *__c to *__a
00076   template<typename _Iterator>
00077     void
00078     __move_median_first(_Iterator __a, _Iterator __b, _Iterator __c)
00079     {
00080       // concept requirements
00081       __glibcxx_function_requires(_LessThanComparableConcept<
00082         typename iterator_traits<_Iterator>::value_type>)
00083 
00084       if (*__a < *__b)
00085     {
00086       if (*__b < *__c)
00087         std::iter_swap(__a, __b);
00088       else if (*__a < *__c)
00089         std::iter_swap(__a, __c);
00090     }
00091       else if (*__a < *__c)
00092     return;
00093       else if (*__b < *__c)
00094     std::iter_swap(__a, __c);
00095       else
00096     std::iter_swap(__a, __b);
00097     }
00098 
00099   /// Swaps the median value of *__a, *__b and *__c under __comp to *__a
00100   template<typename _Iterator, typename _Compare>
00101     void
00102     __move_median_first(_Iterator __a, _Iterator __b, _Iterator __c,
00103             _Compare __comp)
00104     {
00105       // concept requirements
00106       __glibcxx_function_requires(_BinaryFunctionConcept<_Compare, bool,
00107         typename iterator_traits<_Iterator>::value_type,
00108         typename iterator_traits<_Iterator>::value_type>)
00109 
00110       if (__comp(*__a, *__b))
00111     {
00112       if (__comp(*__b, *__c))
00113         std::iter_swap(__a, __b);
00114       else if (__comp(*__a, *__c))
00115         std::iter_swap(__a, __c);
00116     }
00117       else if (__comp(*__a, *__c))
00118     return;
00119       else if (__comp(*__b, *__c))
00120     std::iter_swap(__a, __c);
00121       else
00122     std::iter_swap(__a, __b);
00123     }
00124 
00125   // for_each
00126 
00127   /// This is an overload used by find() for the Input Iterator case.
00128   template<typename _InputIterator, typename _Tp>
00129     inline _InputIterator
00130     __find(_InputIterator __first, _InputIterator __last,
00131        const _Tp& __val, input_iterator_tag)
00132     {
00133       while (__first != __last && !(*__first == __val))
00134     ++__first;
00135       return __first;
00136     }
00137 
00138   /// This is an overload used by find_if() for the Input Iterator case.
00139   template<typename _InputIterator, typename _Predicate>
00140     inline _InputIterator
00141     __find_if(_InputIterator __first, _InputIterator __last,
00142           _Predicate __pred, input_iterator_tag)
00143     {
00144       while (__first != __last && !bool(__pred(*__first)))
00145     ++__first;
00146       return __first;
00147     }
00148 
00149   /// This is an overload used by find() for the RAI case.
00150   template<typename _RandomAccessIterator, typename _Tp>
00151     _RandomAccessIterator
00152     __find(_RandomAccessIterator __first, _RandomAccessIterator __last,
00153        const _Tp& __val, random_access_iterator_tag)
00154     {
00155       typename iterator_traits<_RandomAccessIterator>::difference_type
00156     __trip_count = (__last - __first) >> 2;
00157 
00158       for (; __trip_count > 0; --__trip_count)
00159     {
00160       if (*__first == __val)
00161         return __first;
00162       ++__first;
00163 
00164       if (*__first == __val)
00165         return __first;
00166       ++__first;
00167 
00168       if (*__first == __val)
00169         return __first;
00170       ++__first;
00171 
00172       if (*__first == __val)
00173         return __first;
00174       ++__first;
00175     }
00176 
00177       switch (__last - __first)
00178     {
00179     case 3:
00180       if (*__first == __val)
00181         return __first;
00182       ++__first;
00183     case 2:
00184       if (*__first == __val)
00185         return __first;
00186       ++__first;
00187     case 1:
00188       if (*__first == __val)
00189         return __first;
00190       ++__first;
00191     case 0:
00192     default:
00193       return __last;
00194     }
00195     }
00196 
00197   /// This is an overload used by find_if() for the RAI case.
00198   template<typename _RandomAccessIterator, typename _Predicate>
00199     _RandomAccessIterator
00200     __find_if(_RandomAccessIterator __first, _RandomAccessIterator __last,
00201           _Predicate __pred, random_access_iterator_tag)
00202     {
00203       typename iterator_traits<_RandomAccessIterator>::difference_type
00204     __trip_count = (__last - __first) >> 2;
00205 
00206       for (; __trip_count > 0; --__trip_count)
00207     {
00208       if (__pred(*__first))
00209         return __first;
00210       ++__first;
00211 
00212       if (__pred(*__first))
00213         return __first;
00214       ++__first;
00215 
00216       if (__pred(*__first))
00217         return __first;
00218       ++__first;
00219 
00220       if (__pred(*__first))
00221         return __first;
00222       ++__first;
00223     }
00224 
00225       switch (__last - __first)
00226     {
00227     case 3:
00228       if (__pred(*__first))
00229         return __first;
00230       ++__first;
00231     case 2:
00232       if (__pred(*__first))
00233         return __first;
00234       ++__first;
00235     case 1:
00236       if (__pred(*__first))
00237         return __first;
00238       ++__first;
00239     case 0:
00240     default:
00241       return __last;
00242     }
00243     }
00244 
00245   /// This is an overload used by find_if_not() for the Input Iterator case.
00246   template<typename _InputIterator, typename _Predicate>
00247     inline _InputIterator
00248     __find_if_not(_InputIterator __first, _InputIterator __last,
00249           _Predicate __pred, input_iterator_tag)
00250     {
00251       while (__first != __last && bool(__pred(*__first)))
00252     ++__first;
00253       return __first;
00254     }
00255 
00256   /// This is an overload used by find_if_not() for the RAI case.
00257   template<typename _RandomAccessIterator, typename _Predicate>
00258     _RandomAccessIterator
00259     __find_if_not(_RandomAccessIterator __first, _RandomAccessIterator __last,
00260           _Predicate __pred, random_access_iterator_tag)
00261     {
00262       typename iterator_traits<_RandomAccessIterator>::difference_type
00263     __trip_count = (__last - __first) >> 2;
00264 
00265       for (; __trip_count > 0; --__trip_count)
00266     {
00267       if (!bool(__pred(*__first)))
00268         return __first;
00269       ++__first;
00270 
00271       if (!bool(__pred(*__first)))
00272         return __first;
00273       ++__first;
00274 
00275       if (!bool(__pred(*__first)))
00276         return __first;
00277       ++__first;
00278 
00279       if (!bool(__pred(*__first)))
00280         return __first;
00281       ++__first;
00282     }
00283 
00284       switch (__last - __first)
00285     {
00286     case 3:
00287       if (!bool(__pred(*__first)))
00288         return __first;
00289       ++__first;
00290     case 2:
00291       if (!bool(__pred(*__first)))
00292         return __first;
00293       ++__first;
00294     case 1:
00295       if (!bool(__pred(*__first)))
00296         return __first;
00297       ++__first;
00298     case 0:
00299     default:
00300       return __last;
00301     }
00302     }
00303 
00304   /// Provided for stable_partition to use.
00305   template<typename _InputIterator, typename _Predicate>
00306     inline _InputIterator
00307     __find_if_not(_InputIterator __first, _InputIterator __last,
00308           _Predicate __pred)
00309     {
00310       return std::__find_if_not(__first, __last, __pred,
00311                 std::__iterator_category(__first));
00312     }
00313 
00314   /// Like find_if_not(), but uses and updates a count of the
00315   /// remaining range length instead of comparing against an end
00316   /// iterator.
00317   template<typename _InputIterator, typename _Predicate, typename _Distance>
00318     _InputIterator
00319     __find_if_not_n(_InputIterator __first, _Distance& __len, _Predicate __pred)
00320     {
00321       for (; __len; --__len, ++__first)
00322     if (!bool(__pred(*__first)))
00323       break;
00324       return __first;
00325     }
00326 
00327   // set_difference
00328   // set_intersection
00329   // set_symmetric_difference
00330   // set_union
00331   // for_each
00332   // find
00333   // find_if
00334   // find_first_of
00335   // adjacent_find
00336   // count
00337   // count_if
00338   // search
00339 
00340   /**
00341    *  This is an uglified
00342    *  search_n(_ForwardIterator, _ForwardIterator, _Integer, const _Tp&)
00343    *  overloaded for forward iterators.
00344   */
00345   template<typename _ForwardIterator, typename _Integer, typename _Tp>
00346     _ForwardIterator
00347     __search_n(_ForwardIterator __first, _ForwardIterator __last,
00348            _Integer __count, const _Tp& __val,
00349            std::forward_iterator_tag)
00350     {
00351       __first = _GLIBCXX_STD_A::find(__first, __last, __val);
00352       while (__first != __last)
00353     {
00354       typename iterator_traits<_ForwardIterator>::difference_type
00355         __n = __count;
00356       _ForwardIterator __i = __first;
00357       ++__i;
00358       while (__i != __last && __n != 1 && *__i == __val)
00359         {
00360           ++__i;
00361           --__n;
00362         }
00363       if (__n == 1)
00364         return __first;
00365       if (__i == __last)
00366         return __last;
00367       __first = _GLIBCXX_STD_A::find(++__i, __last, __val);
00368     }
00369       return __last;
00370     }
00371 
00372   /**
00373    *  This is an uglified
00374    *  search_n(_ForwardIterator, _ForwardIterator, _Integer, const _Tp&)
00375    *  overloaded for random access iterators.
00376   */
00377   template<typename _RandomAccessIter, typename _Integer, typename _Tp>
00378     _RandomAccessIter
00379     __search_n(_RandomAccessIter __first, _RandomAccessIter __last,
00380            _Integer __count, const _Tp& __val, 
00381            std::random_access_iterator_tag)
00382     {
00383       
00384       typedef typename std::iterator_traits<_RandomAccessIter>::difference_type
00385     _DistanceType;
00386 
00387       _DistanceType __tailSize = __last - __first;
00388       const _DistanceType __pattSize = __count;
00389 
00390       if (__tailSize < __pattSize)
00391         return __last;
00392 
00393       const _DistanceType __skipOffset = __pattSize - 1;
00394       _RandomAccessIter __lookAhead = __first + __skipOffset;
00395       __tailSize -= __pattSize;
00396 
00397       while (1) // the main loop...
00398     {
00399       // __lookAhead here is always pointing to the last element of next 
00400       // possible match.
00401       while (!(*__lookAhead == __val)) // the skip loop...
00402         {
00403           if (__tailSize < __pattSize)
00404         return __last;  // Failure
00405           __lookAhead += __pattSize;
00406           __tailSize -= __pattSize;
00407         }
00408       _DistanceType __remainder = __skipOffset;
00409       for (_RandomAccessIter __backTrack = __lookAhead - 1; 
00410            *__backTrack == __val; --__backTrack)
00411         {
00412           if (--__remainder == 0)
00413         return (__lookAhead - __skipOffset); // Success
00414         }
00415       if (__remainder > __tailSize)
00416         return __last; // Failure
00417       __lookAhead += __remainder;
00418       __tailSize -= __remainder;
00419     }
00420     }
00421 
00422   // search_n
00423 
00424   /**
00425    *  This is an uglified
00426    *  search_n(_ForwardIterator, _ForwardIterator, _Integer, const _Tp&,
00427    *           _BinaryPredicate)
00428    *  overloaded for forward iterators.
00429   */
00430   template<typename _ForwardIterator, typename _Integer, typename _Tp,
00431            typename _BinaryPredicate>
00432     _ForwardIterator
00433     __search_n(_ForwardIterator __first, _ForwardIterator __last,
00434            _Integer __count, const _Tp& __val,
00435            _BinaryPredicate __binary_pred, std::forward_iterator_tag)
00436     {
00437       while (__first != __last && !bool(__binary_pred(*__first, __val)))
00438         ++__first;
00439 
00440       while (__first != __last)
00441     {
00442       typename iterator_traits<_ForwardIterator>::difference_type
00443         __n = __count;
00444       _ForwardIterator __i = __first;
00445       ++__i;
00446       while (__i != __last && __n != 1 && bool(__binary_pred(*__i, __val)))
00447         {
00448           ++__i;
00449           --__n;
00450         }
00451       if (__n == 1)
00452         return __first;
00453       if (__i == __last)
00454         return __last;
00455       __first = ++__i;
00456       while (__first != __last
00457          && !bool(__binary_pred(*__first, __val)))
00458         ++__first;
00459     }
00460       return __last;
00461     }
00462 
00463   /**
00464    *  This is an uglified
00465    *  search_n(_ForwardIterator, _ForwardIterator, _Integer, const _Tp&,
00466    *           _BinaryPredicate)
00467    *  overloaded for random access iterators.
00468   */
00469   template<typename _RandomAccessIter, typename _Integer, typename _Tp,
00470        typename _BinaryPredicate>
00471     _RandomAccessIter
00472     __search_n(_RandomAccessIter __first, _RandomAccessIter __last,
00473            _Integer __count, const _Tp& __val,
00474            _BinaryPredicate __binary_pred, std::random_access_iterator_tag)
00475     {
00476       
00477       typedef typename std::iterator_traits<_RandomAccessIter>::difference_type
00478     _DistanceType;
00479 
00480       _DistanceType __tailSize = __last - __first;
00481       const _DistanceType __pattSize = __count;
00482 
00483       if (__tailSize < __pattSize)
00484         return __last;
00485 
00486       const _DistanceType __skipOffset = __pattSize - 1;
00487       _RandomAccessIter __lookAhead = __first + __skipOffset;
00488       __tailSize -= __pattSize;
00489 
00490       while (1) // the main loop...
00491     {
00492       // __lookAhead here is always pointing to the last element of next 
00493       // possible match.
00494       while (!bool(__binary_pred(*__lookAhead, __val))) // the skip loop...
00495         {
00496           if (__tailSize < __pattSize)
00497         return __last;  // Failure
00498           __lookAhead += __pattSize;
00499           __tailSize -= __pattSize;
00500         }
00501       _DistanceType __remainder = __skipOffset;
00502       for (_RandomAccessIter __backTrack = __lookAhead - 1; 
00503            __binary_pred(*__backTrack, __val); --__backTrack)
00504         {
00505           if (--__remainder == 0)
00506         return (__lookAhead - __skipOffset); // Success
00507         }
00508       if (__remainder > __tailSize)
00509         return __last; // Failure
00510       __lookAhead += __remainder;
00511       __tailSize -= __remainder;
00512     }
00513     }
00514 
00515   // find_end for forward iterators.
00516   template<typename _ForwardIterator1, typename _ForwardIterator2>
00517     _ForwardIterator1
00518     __find_end(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
00519            _ForwardIterator2 __first2, _ForwardIterator2 __last2,
00520            forward_iterator_tag, forward_iterator_tag)
00521     {
00522       if (__first2 == __last2)
00523     return __last1;
00524       else
00525     {
00526       _ForwardIterator1 __result = __last1;
00527       while (1)
00528         {
00529           _ForwardIterator1 __new_result
00530         = _GLIBCXX_STD_A::search(__first1, __last1, __first2, __last2);
00531           if (__new_result == __last1)
00532         return __result;
00533           else
00534         {
00535           __result = __new_result;
00536           __first1 = __new_result;
00537           ++__first1;
00538         }
00539         }
00540     }
00541     }
00542 
00543   template<typename _ForwardIterator1, typename _ForwardIterator2,
00544        typename _BinaryPredicate>
00545     _ForwardIterator1
00546     __find_end(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
00547            _ForwardIterator2 __first2, _ForwardIterator2 __last2,
00548            forward_iterator_tag, forward_iterator_tag,
00549            _BinaryPredicate __comp)
00550     {
00551       if (__first2 == __last2)
00552     return __last1;
00553       else
00554     {
00555       _ForwardIterator1 __result = __last1;
00556       while (1)
00557         {
00558           _ForwardIterator1 __new_result
00559         = _GLIBCXX_STD_A::search(__first1, __last1, __first2,
00560                      __last2, __comp);
00561           if (__new_result == __last1)
00562         return __result;
00563           else
00564         {
00565           __result = __new_result;
00566           __first1 = __new_result;
00567           ++__first1;
00568         }
00569         }
00570     }
00571     }
00572 
00573   // find_end for bidirectional iterators (much faster).
00574   template<typename _BidirectionalIterator1, typename _BidirectionalIterator2>
00575     _BidirectionalIterator1
00576     __find_end(_BidirectionalIterator1 __first1,
00577            _BidirectionalIterator1 __last1,
00578            _BidirectionalIterator2 __first2,
00579            _BidirectionalIterator2 __last2,
00580            bidirectional_iterator_tag, bidirectional_iterator_tag)
00581     {
00582       // concept requirements
00583       __glibcxx_function_requires(_BidirectionalIteratorConcept<
00584                   _BidirectionalIterator1>)
00585       __glibcxx_function_requires(_BidirectionalIteratorConcept<
00586                   _BidirectionalIterator2>)
00587 
00588       typedef reverse_iterator<_BidirectionalIterator1> _RevIterator1;
00589       typedef reverse_iterator<_BidirectionalIterator2> _RevIterator2;
00590 
00591       _RevIterator1 __rlast1(__first1);
00592       _RevIterator2 __rlast2(__first2);
00593       _RevIterator1 __rresult = _GLIBCXX_STD_A::search(_RevIterator1(__last1),
00594                                __rlast1,
00595                                _RevIterator2(__last2),
00596                                __rlast2);
00597 
00598       if (__rresult == __rlast1)
00599     return __last1;
00600       else
00601     {
00602       _BidirectionalIterator1 __result = __rresult.base();
00603       std::advance(__result, -std::distance(__first2, __last2));
00604       return __result;
00605     }
00606     }
00607 
00608   template<typename _BidirectionalIterator1, typename _BidirectionalIterator2,
00609        typename _BinaryPredicate>
00610     _BidirectionalIterator1
00611     __find_end(_BidirectionalIterator1 __first1,
00612            _BidirectionalIterator1 __last1,
00613            _BidirectionalIterator2 __first2,
00614            _BidirectionalIterator2 __last2,
00615            bidirectional_iterator_tag, bidirectional_iterator_tag,
00616            _BinaryPredicate __comp)
00617     {
00618       // concept requirements
00619       __glibcxx_function_requires(_BidirectionalIteratorConcept<
00620                   _BidirectionalIterator1>)
00621       __glibcxx_function_requires(_BidirectionalIteratorConcept<
00622                   _BidirectionalIterator2>)
00623 
00624       typedef reverse_iterator<_BidirectionalIterator1> _RevIterator1;
00625       typedef reverse_iterator<_BidirectionalIterator2> _RevIterator2;
00626 
00627       _RevIterator1 __rlast1(__first1);
00628       _RevIterator2 __rlast2(__first2);
00629       _RevIterator1 __rresult = std::search(_RevIterator1(__last1), __rlast1,
00630                         _RevIterator2(__last2), __rlast2,
00631                         __comp);
00632 
00633       if (__rresult == __rlast1)
00634     return __last1;
00635       else
00636     {
00637       _BidirectionalIterator1 __result = __rresult.base();
00638       std::advance(__result, -std::distance(__first2, __last2));
00639       return __result;
00640     }
00641     }
00642 
00643   /**
00644    *  @brief  Find last matching subsequence in a sequence.
00645    *  @ingroup non_mutating_algorithms
00646    *  @param  __first1  Start of range to search.
00647    *  @param  __last1   End of range to search.
00648    *  @param  __first2  Start of sequence to match.
00649    *  @param  __last2   End of sequence to match.
00650    *  @return   The last iterator @c i in the range
00651    *  @p [__first1,__last1-(__last2-__first2)) such that @c *(i+N) ==
00652    *  @p *(__first2+N) for each @c N in the range @p
00653    *  [0,__last2-__first2), or @p __last1 if no such iterator exists.
00654    *
00655    *  Searches the range @p [__first1,__last1) for a sub-sequence that
00656    *  compares equal value-by-value with the sequence given by @p
00657    *  [__first2,__last2) and returns an iterator to the __first
00658    *  element of the sub-sequence, or @p __last1 if the sub-sequence
00659    *  is not found.  The sub-sequence will be the last such
00660    *  subsequence contained in [__first,__last1).
00661    *
00662    *  Because the sub-sequence must lie completely within the range @p
00663    *  [__first1,__last1) it must start at a position less than @p
00664    *  __last1-(__last2-__first2) where @p __last2-__first2 is the
00665    *  length of the sub-sequence.  This means that the returned
00666    *  iterator @c i will be in the range @p
00667    *  [__first1,__last1-(__last2-__first2))
00668   */
00669   template<typename _ForwardIterator1, typename _ForwardIterator2>
00670     inline _ForwardIterator1
00671     find_end(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
00672          _ForwardIterator2 __first2, _ForwardIterator2 __last2)
00673     {
00674       // concept requirements
00675       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator1>)
00676       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator2>)
00677       __glibcxx_function_requires(_EqualOpConcept<
00678         typename iterator_traits<_ForwardIterator1>::value_type,
00679         typename iterator_traits<_ForwardIterator2>::value_type>)
00680       __glibcxx_requires_valid_range(__first1, __last1);
00681       __glibcxx_requires_valid_range(__first2, __last2);
00682 
00683       return std::__find_end(__first1, __last1, __first2, __last2,
00684                  std::__iterator_category(__first1),
00685                  std::__iterator_category(__first2));
00686     }
00687 
00688   /**
00689    *  @brief  Find last matching subsequence in a sequence using a predicate.
00690    *  @ingroup non_mutating_algorithms
00691    *  @param  __first1  Start of range to search.
00692    *  @param  __last1   End of range to search.
00693    *  @param  __first2  Start of sequence to match.
00694    *  @param  __last2   End of sequence to match.
00695    *  @param  __comp    The predicate to use.
00696    *  @return The last iterator @c i in the range @p
00697    *  [__first1,__last1-(__last2-__first2)) such that @c
00698    *  predicate(*(i+N), @p (__first2+N)) is true for each @c N in the
00699    *  range @p [0,__last2-__first2), or @p __last1 if no such iterator
00700    *  exists.
00701    *
00702    *  Searches the range @p [__first1,__last1) for a sub-sequence that
00703    *  compares equal value-by-value with the sequence given by @p
00704    *  [__first2,__last2) using comp as a predicate and returns an
00705    *  iterator to the first element of the sub-sequence, or @p __last1
00706    *  if the sub-sequence is not found.  The sub-sequence will be the
00707    *  last such subsequence contained in [__first,__last1).
00708    *
00709    *  Because the sub-sequence must lie completely within the range @p
00710    *  [__first1,__last1) it must start at a position less than @p
00711    *  __last1-(__last2-__first2) where @p __last2-__first2 is the
00712    *  length of the sub-sequence.  This means that the returned
00713    *  iterator @c i will be in the range @p
00714    *  [__first1,__last1-(__last2-__first2))
00715   */
00716   template<typename _ForwardIterator1, typename _ForwardIterator2,
00717        typename _BinaryPredicate>
00718     inline _ForwardIterator1
00719     find_end(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
00720          _ForwardIterator2 __first2, _ForwardIterator2 __last2,
00721          _BinaryPredicate __comp)
00722     {
00723       // concept requirements
00724       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator1>)
00725       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator2>)
00726       __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
00727         typename iterator_traits<_ForwardIterator1>::value_type,
00728         typename iterator_traits<_ForwardIterator2>::value_type>)
00729       __glibcxx_requires_valid_range(__first1, __last1);
00730       __glibcxx_requires_valid_range(__first2, __last2);
00731 
00732       return std::__find_end(__first1, __last1, __first2, __last2,
00733                  std::__iterator_category(__first1),
00734                  std::__iterator_category(__first2),
00735                  __comp);
00736     }
00737 
00738 #if __cplusplus >= 201103L
00739   /**
00740    *  @brief  Checks that a predicate is true for all the elements
00741    *          of a sequence.
00742    *  @ingroup non_mutating_algorithms
00743    *  @param  __first   An input iterator.
00744    *  @param  __last    An input iterator.
00745    *  @param  __pred    A predicate.
00746    *  @return  True if the check is true, false otherwise.
00747    *
00748    *  Returns true if @p __pred is true for each element in the range
00749    *  @p [__first,__last), and false otherwise.
00750   */
00751   template<typename _InputIterator, typename _Predicate>
00752     inline bool
00753     all_of(_InputIterator __first, _InputIterator __last, _Predicate __pred)
00754     { return __last == std::find_if_not(__first, __last, __pred); }
00755 
00756   /**
00757    *  @brief  Checks that a predicate is false for all the elements
00758    *          of a sequence.
00759    *  @ingroup non_mutating_algorithms
00760    *  @param  __first   An input iterator.
00761    *  @param  __last    An input iterator.
00762    *  @param  __pred    A predicate.
00763    *  @return  True if the check is true, false otherwise.
00764    *
00765    *  Returns true if @p __pred is false for each element in the range
00766    *  @p [__first,__last), and false otherwise.
00767   */
00768   template<typename _InputIterator, typename _Predicate>
00769     inline bool
00770     none_of(_InputIterator __first, _InputIterator __last, _Predicate __pred)
00771     { return __last == _GLIBCXX_STD_A::find_if(__first, __last, __pred); }
00772 
00773   /**
00774    *  @brief  Checks that a predicate is false for at least an element
00775    *          of a sequence.
00776    *  @ingroup non_mutating_algorithms
00777    *  @param  __first   An input iterator.
00778    *  @param  __last    An input iterator.
00779    *  @param  __pred    A predicate.
00780    *  @return  True if the check is true, false otherwise.
00781    *
00782    *  Returns true if an element exists in the range @p
00783    *  [__first,__last) such that @p __pred is true, and false
00784    *  otherwise.
00785   */
00786   template<typename _InputIterator, typename _Predicate>
00787     inline bool
00788     any_of(_InputIterator __first, _InputIterator __last, _Predicate __pred)
00789     { return !std::none_of(__first, __last, __pred); }
00790 
00791   /**
00792    *  @brief  Find the first element in a sequence for which a
00793    *          predicate is false.
00794    *  @ingroup non_mutating_algorithms
00795    *  @param  __first  An input iterator.
00796    *  @param  __last   An input iterator.
00797    *  @param  __pred   A predicate.
00798    *  @return   The first iterator @c i in the range @p [__first,__last)
00799    *  such that @p __pred(*i) is false, or @p __last if no such iterator exists.
00800   */
00801   template<typename _InputIterator, typename _Predicate>
00802     inline _InputIterator
00803     find_if_not(_InputIterator __first, _InputIterator __last,
00804         _Predicate __pred)
00805     {
00806       // concept requirements
00807       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
00808       __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
00809           typename iterator_traits<_InputIterator>::value_type>)
00810       __glibcxx_requires_valid_range(__first, __last);
00811       return std::__find_if_not(__first, __last, __pred);
00812     }
00813 
00814   /**
00815    *  @brief  Checks whether the sequence is partitioned.
00816    *  @ingroup mutating_algorithms
00817    *  @param  __first  An input iterator.
00818    *  @param  __last   An input iterator.
00819    *  @param  __pred   A predicate.
00820    *  @return  True if the range @p [__first,__last) is partioned by @p __pred,
00821    *  i.e. if all elements that satisfy @p __pred appear before those that
00822    *  do not.
00823   */
00824   template<typename _InputIterator, typename _Predicate>
00825     inline bool
00826     is_partitioned(_InputIterator __first, _InputIterator __last,
00827            _Predicate __pred)
00828     {
00829       __first = std::find_if_not(__first, __last, __pred);
00830       return std::none_of(__first, __last, __pred);
00831     }
00832 
00833   /**
00834    *  @brief  Find the partition point of a partitioned range.
00835    *  @ingroup mutating_algorithms
00836    *  @param  __first   An iterator.
00837    *  @param  __last    Another iterator.
00838    *  @param  __pred    A predicate.
00839    *  @return  An iterator @p mid such that @p all_of(__first, mid, __pred)
00840    *           and @p none_of(mid, __last, __pred) are both true.
00841   */
00842   template<typename _ForwardIterator, typename _Predicate>
00843     _ForwardIterator
00844     partition_point(_ForwardIterator __first, _ForwardIterator __last,
00845             _Predicate __pred)
00846     {
00847       // concept requirements
00848       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
00849       __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
00850           typename iterator_traits<_ForwardIterator>::value_type>)
00851 
00852       // A specific debug-mode test will be necessary...
00853       __glibcxx_requires_valid_range(__first, __last);
00854 
00855       typedef typename iterator_traits<_ForwardIterator>::difference_type
00856     _DistanceType;
00857 
00858       _DistanceType __len = std::distance(__first, __last);
00859       _DistanceType __half;
00860       _ForwardIterator __middle;
00861 
00862       while (__len > 0)
00863     {
00864       __half = __len >> 1;
00865       __middle = __first;
00866       std::advance(__middle, __half);
00867       if (__pred(*__middle))
00868         {
00869           __first = __middle;
00870           ++__first;
00871           __len = __len - __half - 1;
00872         }
00873       else
00874         __len = __half;
00875     }
00876       return __first;
00877     }
00878 #endif
00879 
00880 
00881   /**
00882    *  @brief Copy a sequence, removing elements of a given value.
00883    *  @ingroup mutating_algorithms
00884    *  @param  __first   An input iterator.
00885    *  @param  __last    An input iterator.
00886    *  @param  __result  An output iterator.
00887    *  @param  __value   The value to be removed.
00888    *  @return   An iterator designating the end of the resulting sequence.
00889    *
00890    *  Copies each element in the range @p [__first,__last) not equal
00891    *  to @p __value to the range beginning at @p __result.
00892    *  remove_copy() is stable, so the relative order of elements that
00893    *  are copied is unchanged.
00894   */
00895   template<typename _InputIterator, typename _OutputIterator, typename _Tp>
00896     _OutputIterator
00897     remove_copy(_InputIterator __first, _InputIterator __last,
00898         _OutputIterator __result, const _Tp& __value)
00899     {
00900       // concept requirements
00901       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
00902       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
00903         typename iterator_traits<_InputIterator>::value_type>)
00904       __glibcxx_function_requires(_EqualOpConcept<
00905         typename iterator_traits<_InputIterator>::value_type, _Tp>)
00906       __glibcxx_requires_valid_range(__first, __last);
00907 
00908       for (; __first != __last; ++__first)
00909     if (!(*__first == __value))
00910       {
00911         *__result = *__first;
00912         ++__result;
00913       }
00914       return __result;
00915     }
00916 
00917   /**
00918    *  @brief Copy a sequence, removing elements for which a predicate is true.
00919    *  @ingroup mutating_algorithms
00920    *  @param  __first   An input iterator.
00921    *  @param  __last    An input iterator.
00922    *  @param  __result  An output iterator.
00923    *  @param  __pred    A predicate.
00924    *  @return   An iterator designating the end of the resulting sequence.
00925    *
00926    *  Copies each element in the range @p [__first,__last) for which
00927    *  @p __pred returns false to the range beginning at @p __result.
00928    *
00929    *  remove_copy_if() is stable, so the relative order of elements that are
00930    *  copied is unchanged.
00931   */
00932   template<typename _InputIterator, typename _OutputIterator,
00933        typename _Predicate>
00934     _OutputIterator
00935     remove_copy_if(_InputIterator __first, _InputIterator __last,
00936            _OutputIterator __result, _Predicate __pred)
00937     {
00938       // concept requirements
00939       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
00940       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
00941         typename iterator_traits<_InputIterator>::value_type>)
00942       __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
00943         typename iterator_traits<_InputIterator>::value_type>)
00944       __glibcxx_requires_valid_range(__first, __last);
00945 
00946       for (; __first != __last; ++__first)
00947     if (!bool(__pred(*__first)))
00948       {
00949         *__result = *__first;
00950         ++__result;
00951       }
00952       return __result;
00953     }
00954 
00955 #if __cplusplus >= 201103L
00956   /**
00957    *  @brief Copy the elements of a sequence for which a predicate is true.
00958    *  @ingroup mutating_algorithms
00959    *  @param  __first   An input iterator.
00960    *  @param  __last    An input iterator.
00961    *  @param  __result  An output iterator.
00962    *  @param  __pred    A predicate.
00963    *  @return   An iterator designating the end of the resulting sequence.
00964    *
00965    *  Copies each element in the range @p [__first,__last) for which
00966    *  @p __pred returns true to the range beginning at @p __result.
00967    *
00968    *  copy_if() is stable, so the relative order of elements that are
00969    *  copied is unchanged.
00970   */
00971   template<typename _InputIterator, typename _OutputIterator,
00972        typename _Predicate>
00973     _OutputIterator
00974     copy_if(_InputIterator __first, _InputIterator __last,
00975         _OutputIterator __result, _Predicate __pred)
00976     {
00977       // concept requirements
00978       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
00979       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
00980         typename iterator_traits<_InputIterator>::value_type>)
00981       __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
00982         typename iterator_traits<_InputIterator>::value_type>)
00983       __glibcxx_requires_valid_range(__first, __last);
00984 
00985       for (; __first != __last; ++__first)
00986     if (__pred(*__first))
00987       {
00988         *__result = *__first;
00989         ++__result;
00990       }
00991       return __result;
00992     }
00993 
00994 
00995   template<typename _InputIterator, typename _Size, typename _OutputIterator>
00996     _OutputIterator
00997     __copy_n(_InputIterator __first, _Size __n,
00998          _OutputIterator __result, input_iterator_tag)
00999     {
01000       if (__n > 0)
01001     {
01002       while (true)
01003         {
01004           *__result = *__first;
01005           ++__result;
01006           if (--__n > 0)
01007         ++__first;
01008           else
01009         break;
01010         }
01011     }
01012       return __result;
01013     }
01014 
01015   template<typename _RandomAccessIterator, typename _Size,
01016        typename _OutputIterator>
01017     inline _OutputIterator
01018     __copy_n(_RandomAccessIterator __first, _Size __n,
01019          _OutputIterator __result, random_access_iterator_tag)
01020     { return std::copy(__first, __first + __n, __result); }
01021 
01022   /**
01023    *  @brief Copies the range [first,first+n) into [result,result+n).
01024    *  @ingroup mutating_algorithms
01025    *  @param  __first  An input iterator.
01026    *  @param  __n      The number of elements to copy.
01027    *  @param  __result An output iterator.
01028    *  @return  result+n.
01029    *
01030    *  This inline function will boil down to a call to @c memmove whenever
01031    *  possible.  Failing that, if random access iterators are passed, then the
01032    *  loop count will be known (and therefore a candidate for compiler
01033    *  optimizations such as unrolling).
01034   */
01035   template<typename _InputIterator, typename _Size, typename _OutputIterator>
01036     inline _OutputIterator
01037     copy_n(_InputIterator __first, _Size __n, _OutputIterator __result)
01038     {
01039       // concept requirements
01040       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
01041       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
01042         typename iterator_traits<_InputIterator>::value_type>)
01043 
01044       return std::__copy_n(__first, __n, __result,
01045                std::__iterator_category(__first));
01046     }
01047 
01048   /**
01049    *  @brief Copy the elements of a sequence to separate output sequences
01050    *         depending on the truth value of a predicate.
01051    *  @ingroup mutating_algorithms
01052    *  @param  __first   An input iterator.
01053    *  @param  __last    An input iterator.
01054    *  @param  __out_true   An output iterator.
01055    *  @param  __out_false  An output iterator.
01056    *  @param  __pred    A predicate.
01057    *  @return   A pair designating the ends of the resulting sequences.
01058    *
01059    *  Copies each element in the range @p [__first,__last) for which
01060    *  @p __pred returns true to the range beginning at @p out_true
01061    *  and each element for which @p __pred returns false to @p __out_false.
01062   */
01063   template<typename _InputIterator, typename _OutputIterator1,
01064        typename _OutputIterator2, typename _Predicate>
01065     pair<_OutputIterator1, _OutputIterator2>
01066     partition_copy(_InputIterator __first, _InputIterator __last,
01067            _OutputIterator1 __out_true, _OutputIterator2 __out_false,
01068            _Predicate __pred)
01069     {
01070       // concept requirements
01071       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
01072       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator1,
01073         typename iterator_traits<_InputIterator>::value_type>)
01074       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator2,
01075         typename iterator_traits<_InputIterator>::value_type>)
01076       __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
01077         typename iterator_traits<_InputIterator>::value_type>)
01078       __glibcxx_requires_valid_range(__first, __last);
01079       
01080       for (; __first != __last; ++__first)
01081     if (__pred(*__first))
01082       {
01083         *__out_true = *__first;
01084         ++__out_true;
01085       }
01086     else
01087       {
01088         *__out_false = *__first;
01089         ++__out_false;
01090       }
01091 
01092       return pair<_OutputIterator1, _OutputIterator2>(__out_true, __out_false);
01093     }
01094 #endif
01095 
01096   /**
01097    *  @brief Remove elements from a sequence.
01098    *  @ingroup mutating_algorithms
01099    *  @param  __first  An input iterator.
01100    *  @param  __last   An input iterator.
01101    *  @param  __value  The value to be removed.
01102    *  @return   An iterator designating the end of the resulting sequence.
01103    *
01104    *  All elements equal to @p __value are removed from the range
01105    *  @p [__first,__last).
01106    *
01107    *  remove() is stable, so the relative order of elements that are
01108    *  not removed is unchanged.
01109    *
01110    *  Elements between the end of the resulting sequence and @p __last
01111    *  are still present, but their value is unspecified.
01112   */
01113   template<typename _ForwardIterator, typename _Tp>
01114     _ForwardIterator
01115     remove(_ForwardIterator __first, _ForwardIterator __last,
01116        const _Tp& __value)
01117     {
01118       // concept requirements
01119       __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
01120                   _ForwardIterator>)
01121       __glibcxx_function_requires(_EqualOpConcept<
01122         typename iterator_traits<_ForwardIterator>::value_type, _Tp>)
01123       __glibcxx_requires_valid_range(__first, __last);
01124 
01125       __first = _GLIBCXX_STD_A::find(__first, __last, __value);
01126       if(__first == __last)
01127         return __first;
01128       _ForwardIterator __result = __first;
01129       ++__first;
01130       for(; __first != __last; ++__first)
01131         if(!(*__first == __value))
01132           {
01133             *__result = _GLIBCXX_MOVE(*__first);
01134             ++__result;
01135           }
01136       return __result;
01137     }
01138 
01139   /**
01140    *  @brief Remove elements from a sequence using a predicate.
01141    *  @ingroup mutating_algorithms
01142    *  @param  __first  A forward iterator.
01143    *  @param  __last   A forward iterator.
01144    *  @param  __pred   A predicate.
01145    *  @return   An iterator designating the end of the resulting sequence.
01146    *
01147    *  All elements for which @p __pred returns true are removed from the range
01148    *  @p [__first,__last).
01149    *
01150    *  remove_if() is stable, so the relative order of elements that are
01151    *  not removed is unchanged.
01152    *
01153    *  Elements between the end of the resulting sequence and @p __last
01154    *  are still present, but their value is unspecified.
01155   */
01156   template<typename _ForwardIterator, typename _Predicate>
01157     _ForwardIterator
01158     remove_if(_ForwardIterator __first, _ForwardIterator __last,
01159           _Predicate __pred)
01160     {
01161       // concept requirements
01162       __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
01163                   _ForwardIterator>)
01164       __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
01165         typename iterator_traits<_ForwardIterator>::value_type>)
01166       __glibcxx_requires_valid_range(__first, __last);
01167 
01168       __first = _GLIBCXX_STD_A::find_if(__first, __last, __pred);
01169       if(__first == __last)
01170         return __first;
01171       _ForwardIterator __result = __first;
01172       ++__first;
01173       for(; __first != __last; ++__first)
01174         if(!bool(__pred(*__first)))
01175           {
01176             *__result = _GLIBCXX_MOVE(*__first);
01177             ++__result;
01178           }
01179       return __result;
01180     }
01181 
01182   /**
01183    *  @brief Remove consecutive duplicate values from a sequence.
01184    *  @ingroup mutating_algorithms
01185    *  @param  __first  A forward iterator.
01186    *  @param  __last   A forward iterator.
01187    *  @return  An iterator designating the end of the resulting sequence.
01188    *
01189    *  Removes all but the first element from each group of consecutive
01190    *  values that compare equal.
01191    *  unique() is stable, so the relative order of elements that are
01192    *  not removed is unchanged.
01193    *  Elements between the end of the resulting sequence and @p __last
01194    *  are still present, but their value is unspecified.
01195   */
01196   template<typename _ForwardIterator>
01197     _ForwardIterator
01198     unique(_ForwardIterator __first, _ForwardIterator __last)
01199     {
01200       // concept requirements
01201       __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
01202                   _ForwardIterator>)
01203       __glibcxx_function_requires(_EqualityComparableConcept<
01204              typename iterator_traits<_ForwardIterator>::value_type>)
01205       __glibcxx_requires_valid_range(__first, __last);
01206 
01207       // Skip the beginning, if already unique.
01208       __first = _GLIBCXX_STD_A::adjacent_find(__first, __last);
01209       if (__first == __last)
01210     return __last;
01211 
01212       // Do the real copy work.
01213       _ForwardIterator __dest = __first;
01214       ++__first;
01215       while (++__first != __last)
01216     if (!(*__dest == *__first))
01217       *++__dest = _GLIBCXX_MOVE(*__first);
01218       return ++__dest;
01219     }
01220 
01221   /**
01222    *  @brief Remove consecutive values from a sequence using a predicate.
01223    *  @ingroup mutating_algorithms
01224    *  @param  __first        A forward iterator.
01225    *  @param  __last         A forward iterator.
01226    *  @param  __binary_pred  A binary predicate.
01227    *  @return  An iterator designating the end of the resulting sequence.
01228    *
01229    *  Removes all but the first element from each group of consecutive
01230    *  values for which @p __binary_pred returns true.
01231    *  unique() is stable, so the relative order of elements that are
01232    *  not removed is unchanged.
01233    *  Elements between the end of the resulting sequence and @p __last
01234    *  are still present, but their value is unspecified.
01235   */
01236   template<typename _ForwardIterator, typename _BinaryPredicate>
01237     _ForwardIterator
01238     unique(_ForwardIterator __first, _ForwardIterator __last,
01239            _BinaryPredicate __binary_pred)
01240     {
01241       // concept requirements
01242       __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
01243                   _ForwardIterator>)
01244       __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
01245         typename iterator_traits<_ForwardIterator>::value_type,
01246         typename iterator_traits<_ForwardIterator>::value_type>)
01247       __glibcxx_requires_valid_range(__first, __last);
01248 
01249       // Skip the beginning, if already unique.
01250       __first = _GLIBCXX_STD_A::adjacent_find(__first, __last, __binary_pred);
01251       if (__first == __last)
01252     return __last;
01253 
01254       // Do the real copy work.
01255       _ForwardIterator __dest = __first;
01256       ++__first;
01257       while (++__first != __last)
01258     if (!bool(__binary_pred(*__dest, *__first)))
01259       *++__dest = _GLIBCXX_MOVE(*__first);
01260       return ++__dest;
01261     }
01262 
01263   /**
01264    *  This is an uglified unique_copy(_InputIterator, _InputIterator,
01265    *                                  _OutputIterator)
01266    *  overloaded for forward iterators and output iterator as result.
01267   */
01268   template<typename _ForwardIterator, typename _OutputIterator>
01269     _OutputIterator
01270     __unique_copy(_ForwardIterator __first, _ForwardIterator __last,
01271           _OutputIterator __result,
01272           forward_iterator_tag, output_iterator_tag)
01273     {
01274       // concept requirements -- taken care of in dispatching function
01275       _ForwardIterator __next = __first;
01276       *__result = *__first;
01277       while (++__next != __last)
01278     if (!(*__first == *__next))
01279       {
01280         __first = __next;
01281         *++__result = *__first;
01282       }
01283       return ++__result;
01284     }
01285 
01286   /**
01287    *  This is an uglified unique_copy(_InputIterator, _InputIterator,
01288    *                                  _OutputIterator)
01289    *  overloaded for input iterators and output iterator as result.
01290   */
01291   template<typename _InputIterator, typename _OutputIterator>
01292     _OutputIterator
01293     __unique_copy(_InputIterator __first, _InputIterator __last,
01294           _OutputIterator __result,
01295           input_iterator_tag, output_iterator_tag)
01296     {
01297       // concept requirements -- taken care of in dispatching function
01298       typename iterator_traits<_InputIterator>::value_type __value = *__first;
01299       *__result = __value;
01300       while (++__first != __last)
01301     if (!(__value == *__first))
01302       {
01303         __value = *__first;
01304         *++__result = __value;
01305       }
01306       return ++__result;
01307     }
01308 
01309   /**
01310    *  This is an uglified unique_copy(_InputIterator, _InputIterator,
01311    *                                  _OutputIterator)
01312    *  overloaded for input iterators and forward iterator as result.
01313   */
01314   template<typename _InputIterator, typename _ForwardIterator>
01315     _ForwardIterator
01316     __unique_copy(_InputIterator __first, _InputIterator __last,
01317           _ForwardIterator __result,
01318           input_iterator_tag, forward_iterator_tag)
01319     {
01320       // concept requirements -- taken care of in dispatching function
01321       *__result = *__first;
01322       while (++__first != __last)
01323     if (!(*__result == *__first))
01324       *++__result = *__first;
01325       return ++__result;
01326     }
01327 
01328   /**
01329    *  This is an uglified
01330    *  unique_copy(_InputIterator, _InputIterator, _OutputIterator,
01331    *              _BinaryPredicate)
01332    *  overloaded for forward iterators and output iterator as result.
01333   */
01334   template<typename _ForwardIterator, typename _OutputIterator,
01335        typename _BinaryPredicate>
01336     _OutputIterator
01337     __unique_copy(_ForwardIterator __first, _ForwardIterator __last,
01338           _OutputIterator __result, _BinaryPredicate __binary_pred,
01339           forward_iterator_tag, output_iterator_tag)
01340     {
01341       // concept requirements -- iterators already checked
01342       __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
01343       typename iterator_traits<_ForwardIterator>::value_type,
01344       typename iterator_traits<_ForwardIterator>::value_type>)
01345 
01346       _ForwardIterator __next = __first;
01347       *__result = *__first;
01348       while (++__next != __last)
01349     if (!bool(__binary_pred(*__first, *__next)))
01350       {
01351         __first = __next;
01352         *++__result = *__first;
01353       }
01354       return ++__result;
01355     }
01356 
01357   /**
01358    *  This is an uglified
01359    *  unique_copy(_InputIterator, _InputIterator, _OutputIterator,
01360    *              _BinaryPredicate)
01361    *  overloaded for input iterators and output iterator as result.
01362   */
01363   template<typename _InputIterator, typename _OutputIterator,
01364        typename _BinaryPredicate>
01365     _OutputIterator
01366     __unique_copy(_InputIterator __first, _InputIterator __last,
01367           _OutputIterator __result, _BinaryPredicate __binary_pred,
01368           input_iterator_tag, output_iterator_tag)
01369     {
01370       // concept requirements -- iterators already checked
01371       __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
01372       typename iterator_traits<_InputIterator>::value_type,
01373       typename iterator_traits<_InputIterator>::value_type>)
01374 
01375       typename iterator_traits<_InputIterator>::value_type __value = *__first;
01376       *__result = __value;
01377       while (++__first != __last)
01378     if (!bool(__binary_pred(__value, *__first)))
01379       {
01380         __value = *__first;
01381         *++__result = __value;
01382       }
01383       return ++__result;
01384     }
01385 
01386   /**
01387    *  This is an uglified
01388    *  unique_copy(_InputIterator, _InputIterator, _OutputIterator,
01389    *              _BinaryPredicate)
01390    *  overloaded for input iterators and forward iterator as result.
01391   */
01392   template<typename _InputIterator, typename _ForwardIterator,
01393        typename _BinaryPredicate>
01394     _ForwardIterator
01395     __unique_copy(_InputIterator __first, _InputIterator __last,
01396           _ForwardIterator __result, _BinaryPredicate __binary_pred,
01397           input_iterator_tag, forward_iterator_tag)
01398     {
01399       // concept requirements -- iterators already checked
01400       __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
01401       typename iterator_traits<_ForwardIterator>::value_type,
01402       typename iterator_traits<_InputIterator>::value_type>)
01403 
01404       *__result = *__first;
01405       while (++__first != __last)
01406     if (!bool(__binary_pred(*__result, *__first)))
01407       *++__result = *__first;
01408       return ++__result;
01409     }
01410 
01411   /**
01412    *  This is an uglified reverse(_BidirectionalIterator,
01413    *                              _BidirectionalIterator)
01414    *  overloaded for bidirectional iterators.
01415   */
01416   template<typename _BidirectionalIterator>
01417     void
01418     __reverse(_BidirectionalIterator __first, _BidirectionalIterator __last,
01419           bidirectional_iterator_tag)
01420     {
01421       while (true)
01422     if (__first == __last || __first == --__last)
01423       return;
01424     else
01425       {
01426         std::iter_swap(__first, __last);
01427         ++__first;
01428       }
01429     }
01430 
01431   /**
01432    *  This is an uglified reverse(_BidirectionalIterator,
01433    *                              _BidirectionalIterator)
01434    *  overloaded for random access iterators.
01435   */
01436   template<typename _RandomAccessIterator>
01437     void
01438     __reverse(_RandomAccessIterator __first, _RandomAccessIterator __last,
01439           random_access_iterator_tag)
01440     {
01441       if (__first == __last)
01442     return;
01443       --__last;
01444       while (__first < __last)
01445     {
01446       std::iter_swap(__first, __last);
01447       ++__first;
01448       --__last;
01449     }
01450     }
01451 
01452   /**
01453    *  @brief Reverse a sequence.
01454    *  @ingroup mutating_algorithms
01455    *  @param  __first  A bidirectional iterator.
01456    *  @param  __last   A bidirectional iterator.
01457    *  @return   reverse() returns no value.
01458    *
01459    *  Reverses the order of the elements in the range @p [__first,__last),
01460    *  so that the first element becomes the last etc.
01461    *  For every @c i such that @p 0<=i<=(__last-__first)/2), @p reverse()
01462    *  swaps @p *(__first+i) and @p *(__last-(i+1))
01463   */
01464   template<typename _BidirectionalIterator>
01465     inline void
01466     reverse(_BidirectionalIterator __first, _BidirectionalIterator __last)
01467     {
01468       // concept requirements
01469       __glibcxx_function_requires(_Mutable_BidirectionalIteratorConcept<
01470                   _BidirectionalIterator>)
01471       __glibcxx_requires_valid_range(__first, __last);
01472       std::__reverse(__first, __last, std::__iterator_category(__first));
01473     }
01474 
01475   /**
01476    *  @brief Copy a sequence, reversing its elements.
01477    *  @ingroup mutating_algorithms
01478    *  @param  __first   A bidirectional iterator.
01479    *  @param  __last    A bidirectional iterator.
01480    *  @param  __result  An output iterator.
01481    *  @return  An iterator designating the end of the resulting sequence.
01482    *
01483    *  Copies the elements in the range @p [__first,__last) to the
01484    *  range @p [__result,__result+(__last-__first)) such that the
01485    *  order of the elements is reversed.  For every @c i such that @p
01486    *  0<=i<=(__last-__first), @p reverse_copy() performs the
01487    *  assignment @p *(__result+(__last-__first)-1-i) = *(__first+i).
01488    *  The ranges @p [__first,__last) and @p
01489    *  [__result,__result+(__last-__first)) must not overlap.
01490   */
01491   template<typename _BidirectionalIterator, typename _OutputIterator>
01492     _OutputIterator
01493     reverse_copy(_BidirectionalIterator __first, _BidirectionalIterator __last,
01494          _OutputIterator __result)
01495     {
01496       // concept requirements
01497       __glibcxx_function_requires(_BidirectionalIteratorConcept<
01498                   _BidirectionalIterator>)
01499       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
01500         typename iterator_traits<_BidirectionalIterator>::value_type>)
01501       __glibcxx_requires_valid_range(__first, __last);
01502 
01503       while (__first != __last)
01504     {
01505       --__last;
01506       *__result = *__last;
01507       ++__result;
01508     }
01509       return __result;
01510     }
01511 
01512   /**
01513    *  This is a helper function for the rotate algorithm specialized on RAIs.
01514    *  It returns the greatest common divisor of two integer values.
01515   */
01516   template<typename _EuclideanRingElement>
01517     _EuclideanRingElement
01518     __gcd(_EuclideanRingElement __m, _EuclideanRingElement __n)
01519     {
01520       while (__n != 0)
01521     {
01522       _EuclideanRingElement __t = __m % __n;
01523       __m = __n;
01524       __n = __t;
01525     }
01526       return __m;
01527     }
01528 
01529   /// This is a helper function for the rotate algorithm.
01530   template<typename _ForwardIterator>
01531     void
01532     __rotate(_ForwardIterator __first,
01533          _ForwardIterator __middle,
01534          _ForwardIterator __last,
01535          forward_iterator_tag)
01536     {
01537       if (__first == __middle || __last  == __middle)
01538     return;
01539 
01540       _ForwardIterator __first2 = __middle;
01541       do
01542     {
01543       std::iter_swap(__first, __first2);
01544       ++__first;
01545       ++__first2;
01546       if (__first == __middle)
01547         __middle = __first2;
01548     }
01549       while (__first2 != __last);
01550 
01551       __first2 = __middle;
01552 
01553       while (__first2 != __last)
01554     {
01555       std::iter_swap(__first, __first2);
01556       ++__first;
01557       ++__first2;
01558       if (__first == __middle)
01559         __middle = __first2;
01560       else if (__first2 == __last)
01561         __first2 = __middle;
01562     }
01563     }
01564 
01565    /// This is a helper function for the rotate algorithm.
01566   template<typename _BidirectionalIterator>
01567     void
01568     __rotate(_BidirectionalIterator __first,
01569          _BidirectionalIterator __middle,
01570          _BidirectionalIterator __last,
01571           bidirectional_iterator_tag)
01572     {
01573       // concept requirements
01574       __glibcxx_function_requires(_Mutable_BidirectionalIteratorConcept<
01575                   _BidirectionalIterator>)
01576 
01577       if (__first == __middle || __last  == __middle)
01578     return;
01579 
01580       std::__reverse(__first,  __middle, bidirectional_iterator_tag());
01581       std::__reverse(__middle, __last,   bidirectional_iterator_tag());
01582 
01583       while (__first != __middle && __middle != __last)
01584     {
01585       std::iter_swap(__first, --__last);
01586       ++__first;
01587     }
01588 
01589       if (__first == __middle)
01590     std::__reverse(__middle, __last,   bidirectional_iterator_tag());
01591       else
01592     std::__reverse(__first,  __middle, bidirectional_iterator_tag());
01593     }
01594 
01595   /// This is a helper function for the rotate algorithm.
01596   template<typename _RandomAccessIterator>
01597     void
01598     __rotate(_RandomAccessIterator __first,
01599          _RandomAccessIterator __middle,
01600          _RandomAccessIterator __last,
01601          random_access_iterator_tag)
01602     {
01603       // concept requirements
01604       __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
01605                   _RandomAccessIterator>)
01606 
01607       if (__first == __middle || __last  == __middle)
01608     return;
01609 
01610       typedef typename iterator_traits<_RandomAccessIterator>::difference_type
01611     _Distance;
01612       typedef typename iterator_traits<_RandomAccessIterator>::value_type
01613     _ValueType;
01614 
01615       _Distance __n = __last   - __first;
01616       _Distance __k = __middle - __first;
01617 
01618       if (__k == __n - __k)
01619     {
01620       std::swap_ranges(__first, __middle, __middle);
01621       return;
01622     }
01623 
01624       _RandomAccessIterator __p = __first;
01625 
01626       for (;;)
01627     {
01628       if (__k < __n - __k)
01629         {
01630           if (__is_pod(_ValueType) && __k == 1)
01631         {
01632           _ValueType __t = _GLIBCXX_MOVE(*__p);
01633           _GLIBCXX_MOVE3(__p + 1, __p + __n, __p);
01634           *(__p + __n - 1) = _GLIBCXX_MOVE(__t);
01635           return;
01636         }
01637           _RandomAccessIterator __q = __p + __k;
01638           for (_Distance __i = 0; __i < __n - __k; ++ __i)
01639         {
01640           std::iter_swap(__p, __q);
01641           ++__p;
01642           ++__q;
01643         }
01644           __n %= __k;
01645           if (__n == 0)
01646         return;
01647           std::swap(__n, __k);
01648           __k = __n - __k;
01649         }
01650       else
01651         {
01652           __k = __n - __k;
01653           if (__is_pod(_ValueType) && __k == 1)
01654         {
01655           _ValueType __t = _GLIBCXX_MOVE(*(__p + __n - 1));
01656           _GLIBCXX_MOVE_BACKWARD3(__p, __p + __n - 1, __p + __n);
01657           *__p = _GLIBCXX_MOVE(__t);
01658           return;
01659         }
01660           _RandomAccessIterator __q = __p + __n;
01661           __p = __q - __k;
01662           for (_Distance __i = 0; __i < __n - __k; ++ __i)
01663         {
01664           --__p;
01665           --__q;
01666           std::iter_swap(__p, __q);
01667         }
01668           __n %= __k;
01669           if (__n == 0)
01670         return;
01671           std::swap(__n, __k);
01672         }
01673     }
01674     }
01675 
01676   /**
01677    *  @brief Rotate the elements of a sequence.
01678    *  @ingroup mutating_algorithms
01679    *  @param  __first   A forward iterator.
01680    *  @param  __middle  A forward iterator.
01681    *  @param  __last    A forward iterator.
01682    *  @return  Nothing.
01683    *
01684    *  Rotates the elements of the range @p [__first,__last) by 
01685    *  @p (__middle - __first) positions so that the element at @p __middle
01686    *  is moved to @p __first, the element at @p __middle+1 is moved to
01687    *  @p __first+1 and so on for each element in the range
01688    *  @p [__first,__last).
01689    *
01690    *  This effectively swaps the ranges @p [__first,__middle) and
01691    *  @p [__middle,__last).
01692    *
01693    *  Performs
01694    *   @p *(__first+(n+(__last-__middle))%(__last-__first))=*(__first+n)
01695    *  for each @p n in the range @p [0,__last-__first).
01696   */
01697   template<typename _ForwardIterator>
01698     inline void
01699     rotate(_ForwardIterator __first, _ForwardIterator __middle,
01700        _ForwardIterator __last)
01701     {
01702       // concept requirements
01703       __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
01704                   _ForwardIterator>)
01705       __glibcxx_requires_valid_range(__first, __middle);
01706       __glibcxx_requires_valid_range(__middle, __last);
01707 
01708       typedef typename iterator_traits<_ForwardIterator>::iterator_category
01709     _IterType;
01710       std::__rotate(__first, __middle, __last, _IterType());
01711     }
01712 
01713   /**
01714    *  @brief Copy a sequence, rotating its elements.
01715    *  @ingroup mutating_algorithms
01716    *  @param  __first   A forward iterator.
01717    *  @param  __middle  A forward iterator.
01718    *  @param  __last    A forward iterator.
01719    *  @param  __result  An output iterator.
01720    *  @return   An iterator designating the end of the resulting sequence.
01721    *
01722    *  Copies the elements of the range @p [__first,__last) to the
01723    *  range beginning at @result, rotating the copied elements by 
01724    *  @p (__middle-__first) positions so that the element at @p __middle
01725    *  is moved to @p __result, the element at @p __middle+1 is moved
01726    *  to @p __result+1 and so on for each element in the range @p
01727    *  [__first,__last).
01728    *
01729    *  Performs 
01730    *  @p *(__result+(n+(__last-__middle))%(__last-__first))=*(__first+n)
01731    *  for each @p n in the range @p [0,__last-__first).
01732   */
01733   template<typename _ForwardIterator, typename _OutputIterator>
01734     _OutputIterator
01735     rotate_copy(_ForwardIterator __first, _ForwardIterator __middle,
01736                 _ForwardIterator __last, _OutputIterator __result)
01737     {
01738       // concept requirements
01739       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
01740       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
01741         typename iterator_traits<_ForwardIterator>::value_type>)
01742       __glibcxx_requires_valid_range(__first, __middle);
01743       __glibcxx_requires_valid_range(__middle, __last);
01744 
01745       return std::copy(__first, __middle,
01746                        std::copy(__middle, __last, __result));
01747     }
01748 
01749   /// This is a helper function...
01750   template<typename _ForwardIterator, typename _Predicate>
01751     _ForwardIterator
01752     __partition(_ForwardIterator __first, _ForwardIterator __last,
01753         _Predicate __pred, forward_iterator_tag)
01754     {
01755       if (__first == __last)
01756     return __first;
01757 
01758       while (__pred(*__first))
01759     if (++__first == __last)
01760       return __first;
01761 
01762       _ForwardIterator __next = __first;
01763 
01764       while (++__next != __last)
01765     if (__pred(*__next))
01766       {
01767         std::iter_swap(__first, __next);
01768         ++__first;
01769       }
01770 
01771       return __first;
01772     }
01773 
01774   /// This is a helper function...
01775   template<typename _BidirectionalIterator, typename _Predicate>
01776     _BidirectionalIterator
01777     __partition(_BidirectionalIterator __first, _BidirectionalIterator __last,
01778         _Predicate __pred, bidirectional_iterator_tag)
01779     {
01780       while (true)
01781     {
01782       while (true)
01783         if (__first == __last)
01784           return __first;
01785         else if (__pred(*__first))
01786           ++__first;
01787         else
01788           break;
01789       --__last;
01790       while (true)
01791         if (__first == __last)
01792           return __first;
01793         else if (!bool(__pred(*__last)))
01794           --__last;
01795         else
01796           break;
01797       std::iter_swap(__first, __last);
01798       ++__first;
01799     }
01800     }
01801 
01802   // partition
01803 
01804   /// This is a helper function...
01805   /// Requires __len != 0 and !__pred(*__first),
01806   /// same as __stable_partition_adaptive.
01807   template<typename _ForwardIterator, typename _Predicate, typename _Distance>
01808     _ForwardIterator
01809     __inplace_stable_partition(_ForwardIterator __first,
01810                    _Predicate __pred, _Distance __len)
01811     {
01812       if (__len == 1)
01813     return __first;
01814       _ForwardIterator __middle = __first;
01815       std::advance(__middle, __len / 2);
01816       _ForwardIterator __left_split =
01817     std::__inplace_stable_partition(__first, __pred, __len / 2);
01818       // Advance past true-predicate values to satisfy this
01819       // function's preconditions.
01820       _Distance __right_len = __len - __len / 2;
01821       _ForwardIterator __right_split =
01822     std::__find_if_not_n(__middle, __right_len, __pred);
01823       if (__right_len)
01824     __right_split = std::__inplace_stable_partition(__middle,
01825                             __pred,
01826                             __right_len);
01827       std::rotate(__left_split, __middle, __right_split);
01828       std::advance(__left_split, std::distance(__middle, __right_split));
01829       return __left_split;
01830     }
01831 
01832   /// This is a helper function...
01833   /// Requires __first != __last and !__pred(*__first)
01834   /// and __len == distance(__first, __last).
01835   ///
01836   /// !__pred(*__first) allows us to guarantee that we don't
01837   /// move-assign an element onto itself.
01838   template<typename _ForwardIterator, typename _Pointer, typename _Predicate,
01839        typename _Distance>
01840     _ForwardIterator
01841     __stable_partition_adaptive(_ForwardIterator __first,
01842                 _ForwardIterator __last,
01843                 _Predicate __pred, _Distance __len,
01844                 _Pointer __buffer,
01845                 _Distance __buffer_size)
01846     {
01847       if (__len <= __buffer_size)
01848     {
01849       _ForwardIterator __result1 = __first;
01850       _Pointer __result2 = __buffer;
01851       // The precondition guarantees that !__pred(*__first), so
01852       // move that element to the buffer before starting the loop.
01853       // This ensures that we only call __pred once per element.
01854       *__result2 = _GLIBCXX_MOVE(*__first);
01855       ++__result2;
01856       ++__first;
01857       for (; __first != __last; ++__first)
01858         if (__pred(*__first))
01859           {
01860         *__result1 = _GLIBCXX_MOVE(*__first);
01861         ++__result1;
01862           }
01863         else
01864           {
01865         *__result2 = _GLIBCXX_MOVE(*__first);
01866         ++__result2;
01867           }
01868       _GLIBCXX_MOVE3(__buffer, __result2, __result1);
01869       return __result1;
01870     }
01871       else
01872     {
01873       _ForwardIterator __middle = __first;
01874       std::advance(__middle, __len / 2);
01875       _ForwardIterator __left_split =
01876         std::__stable_partition_adaptive(__first, __middle, __pred,
01877                          __len / 2, __buffer,
01878                          __buffer_size);
01879       // Advance past true-predicate values to satisfy this
01880       // function's preconditions.
01881       _Distance __right_len = __len - __len / 2;
01882       _ForwardIterator __right_split =
01883         std::__find_if_not_n(__middle, __right_len, __pred);
01884       if (__right_len)
01885         __right_split =
01886           std::__stable_partition_adaptive(__right_split, __last, __pred,
01887                            __right_len,
01888                            __buffer, __buffer_size);
01889       std::rotate(__left_split, __middle, __right_split);
01890       std::advance(__left_split, std::distance(__middle, __right_split));
01891       return __left_split;
01892     }
01893     }
01894 
01895   /**
01896    *  @brief Move elements for which a predicate is true to the beginning
01897    *         of a sequence, preserving relative ordering.
01898    *  @ingroup mutating_algorithms
01899    *  @param  __first   A forward iterator.
01900    *  @param  __last    A forward iterator.
01901    *  @param  __pred    A predicate functor.
01902    *  @return  An iterator @p middle such that @p __pred(i) is true for each
01903    *  iterator @p i in the range @p [first,middle) and false for each @p i
01904    *  in the range @p [middle,last).
01905    *
01906    *  Performs the same function as @p partition() with the additional
01907    *  guarantee that the relative ordering of elements in each group is
01908    *  preserved, so any two elements @p x and @p y in the range
01909    *  @p [__first,__last) such that @p __pred(x)==__pred(y) will have the same
01910    *  relative ordering after calling @p stable_partition().
01911   */
01912   template<typename _ForwardIterator, typename _Predicate>
01913     _ForwardIterator
01914     stable_partition(_ForwardIterator __first, _ForwardIterator __last,
01915              _Predicate __pred)
01916     {
01917       // concept requirements
01918       __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
01919                   _ForwardIterator>)
01920       __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
01921         typename iterator_traits<_ForwardIterator>::value_type>)
01922       __glibcxx_requires_valid_range(__first, __last);
01923 
01924       __first = std::__find_if_not(__first, __last, __pred);
01925 
01926       if (__first == __last)
01927     return __first;
01928       else
01929     {
01930       typedef typename iterator_traits<_ForwardIterator>::value_type
01931         _ValueType;
01932       typedef typename iterator_traits<_ForwardIterator>::difference_type
01933         _DistanceType;
01934 
01935       _Temporary_buffer<_ForwardIterator, _ValueType> __buf(__first,
01936                                 __last);
01937     if (__buf.size() > 0)
01938       return
01939         std::__stable_partition_adaptive(__first, __last, __pred,
01940                       _DistanceType(__buf.requested_size()),
01941                       __buf.begin(),
01942                       _DistanceType(__buf.size()));
01943     else
01944       return
01945         std::__inplace_stable_partition(__first, __pred,
01946                      _DistanceType(__buf.requested_size()));
01947     }
01948     }
01949 
01950   /// This is a helper function for the sort routines.
01951   template<typename _RandomAccessIterator>
01952     void
01953     __heap_select(_RandomAccessIterator __first,
01954           _RandomAccessIterator __middle,
01955           _RandomAccessIterator __last)
01956     {
01957       std::make_heap(__first, __middle);
01958       for (_RandomAccessIterator __i = __middle; __i < __last; ++__i)
01959     if (*__i < *__first)
01960       std::__pop_heap(__first, __middle, __i);
01961     }
01962 
01963   /// This is a helper function for the sort routines.
01964   template<typename _RandomAccessIterator, typename _Compare>
01965     void
01966     __heap_select(_RandomAccessIterator __first,
01967           _RandomAccessIterator __middle,
01968           _RandomAccessIterator __last, _Compare __comp)
01969     {
01970       std::make_heap(__first, __middle, __comp);
01971       for (_RandomAccessIterator __i = __middle; __i < __last; ++__i)
01972     if (__comp(*__i, *__first))
01973       std::__pop_heap(__first, __middle, __i, __comp);
01974     }
01975 
01976   // partial_sort
01977 
01978   /**
01979    *  @brief Copy the smallest elements of a sequence.
01980    *  @ingroup sorting_algorithms
01981    *  @param  __first   An iterator.
01982    *  @param  __last    Another iterator.
01983    *  @param  __result_first   A random-access iterator.
01984    *  @param  __result_last    Another random-access iterator.
01985    *  @return   An iterator indicating the end of the resulting sequence.
01986    *
01987    *  Copies and sorts the smallest N values from the range @p [__first,__last)
01988    *  to the range beginning at @p __result_first, where the number of
01989    *  elements to be copied, @p N, is the smaller of @p (__last-__first) and
01990    *  @p (__result_last-__result_first).
01991    *  After the sort if @e i and @e j are iterators in the range
01992    *  @p [__result_first,__result_first+N) such that i precedes j then
01993    *  *j<*i is false.
01994    *  The value returned is @p __result_first+N.
01995   */
01996   template<typename _InputIterator, typename _RandomAccessIterator>
01997     _RandomAccessIterator
01998     partial_sort_copy(_InputIterator __first, _InputIterator __last,
01999               _RandomAccessIterator __result_first,
02000               _RandomAccessIterator __result_last)
02001     {
02002       typedef typename iterator_traits<_InputIterator>::value_type
02003     _InputValueType;
02004       typedef typename iterator_traits<_RandomAccessIterator>::value_type
02005     _OutputValueType;
02006       typedef typename iterator_traits<_RandomAccessIterator>::difference_type
02007     _DistanceType;
02008 
02009       // concept requirements
02010       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
02011       __glibcxx_function_requires(_ConvertibleConcept<_InputValueType,
02012                   _OutputValueType>)
02013       __glibcxx_function_requires(_LessThanOpConcept<_InputValueType,
02014                                      _OutputValueType>)
02015       __glibcxx_function_requires(_LessThanComparableConcept<_OutputValueType>)
02016       __glibcxx_requires_valid_range(__first, __last);
02017       __glibcxx_requires_valid_range(__result_first, __result_last);
02018 
02019       if (__result_first == __result_last)
02020     return __result_last;
02021       _RandomAccessIterator __result_real_last = __result_first;
02022       while(__first != __last && __result_real_last != __result_last)
02023     {
02024       *__result_real_last = *__first;
02025       ++__result_real_last;
02026       ++__first;
02027     }
02028       std::make_heap(__result_first, __result_real_last);
02029       while (__first != __last)
02030     {
02031       if (*__first < *__result_first)
02032         std::__adjust_heap(__result_first, _DistanceType(0),
02033                    _DistanceType(__result_real_last
02034                          - __result_first),
02035                    _InputValueType(*__first));
02036       ++__first;
02037     }
02038       std::sort_heap(__result_first, __result_real_last);
02039       return __result_real_last;
02040     }
02041 
02042   /**
02043    *  @brief Copy the smallest elements of a sequence using a predicate for
02044    *         comparison.
02045    *  @ingroup sorting_algorithms
02046    *  @param  __first   An input iterator.
02047    *  @param  __last    Another input iterator.
02048    *  @param  __result_first   A random-access iterator.
02049    *  @param  __result_last    Another random-access iterator.
02050    *  @param  __comp    A comparison functor.
02051    *  @return   An iterator indicating the end of the resulting sequence.
02052    *
02053    *  Copies and sorts the smallest N values from the range @p [__first,__last)
02054    *  to the range beginning at @p result_first, where the number of
02055    *  elements to be copied, @p N, is the smaller of @p (__last-__first) and
02056    *  @p (__result_last-__result_first).
02057    *  After the sort if @e i and @e j are iterators in the range
02058    *  @p [__result_first,__result_first+N) such that i precedes j then
02059    *  @p __comp(*j,*i) is false.
02060    *  The value returned is @p __result_first+N.
02061   */
02062   template<typename _InputIterator, typename _RandomAccessIterator, typename _Compare>
02063     _RandomAccessIterator
02064     partial_sort_copy(_InputIterator __first, _InputIterator __last,
02065               _RandomAccessIterator __result_first,
02066               _RandomAccessIterator __result_last,
02067               _Compare __comp)
02068     {
02069       typedef typename iterator_traits<_InputIterator>::value_type
02070     _InputValueType;
02071       typedef typename iterator_traits<_RandomAccessIterator>::value_type
02072     _OutputValueType;
02073       typedef typename iterator_traits<_RandomAccessIterator>::difference_type
02074     _DistanceType;
02075 
02076       // concept requirements
02077       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
02078       __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
02079                   _RandomAccessIterator>)
02080       __glibcxx_function_requires(_ConvertibleConcept<_InputValueType,
02081                   _OutputValueType>)
02082       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
02083                   _InputValueType, _OutputValueType>)
02084       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
02085                   _OutputValueType, _OutputValueType>)
02086       __glibcxx_requires_valid_range(__first, __last);
02087       __glibcxx_requires_valid_range(__result_first, __result_last);
02088 
02089       if (__result_first == __result_last)
02090     return __result_last;
02091       _RandomAccessIterator __result_real_last = __result_first;
02092       while(__first != __last && __result_real_last != __result_last)
02093     {
02094       *__result_real_last = *__first;
02095       ++__result_real_last;
02096       ++__first;
02097     }
02098       std::make_heap(__result_first, __result_real_last, __comp);
02099       while (__first != __last)
02100     {
02101       if (__comp(*__first, *__result_first))
02102         std::__adjust_heap(__result_first, _DistanceType(0),
02103                    _DistanceType(__result_real_last
02104                          - __result_first),
02105                    _InputValueType(*__first),
02106                    __comp);
02107       ++__first;
02108     }
02109       std::sort_heap(__result_first, __result_real_last, __comp);
02110       return __result_real_last;
02111     }
02112 
02113   /// This is a helper function for the sort routine.
02114   template<typename _RandomAccessIterator>
02115     void
02116     __unguarded_linear_insert(_RandomAccessIterator __last)
02117     {
02118       typename iterator_traits<_RandomAccessIterator>::value_type
02119     __val = _GLIBCXX_MOVE(*__last);
02120       _RandomAccessIterator __next = __last;
02121       --__next;
02122       while (__val < *__next)
02123     {
02124       *__last = _GLIBCXX_MOVE(*__next);
02125       __last = __next;
02126       --__next;
02127     }
02128       *__last = _GLIBCXX_MOVE(__val);
02129     }
02130 
02131   /// This is a helper function for the sort routine.
02132   template<typename _RandomAccessIterator, typename _Compare>
02133     void
02134     __unguarded_linear_insert(_RandomAccessIterator __last,
02135                   _Compare __comp)
02136     {
02137       typename iterator_traits<_RandomAccessIterator>::value_type
02138     __val = _GLIBCXX_MOVE(*__last);
02139       _RandomAccessIterator __next = __last;
02140       --__next;
02141       while (__comp(__val, *__next))
02142     {
02143       *__last = _GLIBCXX_MOVE(*__next);
02144       __last = __next;
02145       --__next;
02146     }
02147       *__last = _GLIBCXX_MOVE(__val);
02148     }
02149 
02150   /// This is a helper function for the sort routine.
02151   template<typename _RandomAccessIterator>
02152     void
02153     __insertion_sort(_RandomAccessIterator __first,
02154              _RandomAccessIterator __last)
02155     {
02156       if (__first == __last)
02157     return;
02158 
02159       for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i)
02160     {
02161       if (*__i < *__first)
02162         {
02163           typename iterator_traits<_RandomAccessIterator>::value_type
02164         __val = _GLIBCXX_MOVE(*__i);
02165           _GLIBCXX_MOVE_BACKWARD3(__first, __i, __i + 1);
02166           *__first = _GLIBCXX_MOVE(__val);
02167         }
02168       else
02169         std::__unguarded_linear_insert(__i);
02170     }
02171     }
02172 
02173   /// This is a helper function for the sort routine.
02174   template<typename _RandomAccessIterator, typename _Compare>
02175     void
02176     __insertion_sort(_RandomAccessIterator __first,
02177              _RandomAccessIterator __last, _Compare __comp)
02178     {
02179       if (__first == __last) return;
02180 
02181       for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i)
02182     {
02183       if (__comp(*__i, *__first))
02184         {
02185           typename iterator_traits<_RandomAccessIterator>::value_type
02186         __val = _GLIBCXX_MOVE(*__i);
02187           _GLIBCXX_MOVE_BACKWARD3(__first, __i, __i + 1);
02188           *__first = _GLIBCXX_MOVE(__val);
02189         }
02190       else
02191         std::__unguarded_linear_insert(__i, __comp);
02192     }
02193     }
02194 
02195   /// This is a helper function for the sort routine.
02196   template<typename _RandomAccessIterator>
02197     inline void
02198     __unguarded_insertion_sort(_RandomAccessIterator __first,
02199                    _RandomAccessIterator __last)
02200     {
02201       typedef typename iterator_traits<_RandomAccessIterator>::value_type
02202     _ValueType;
02203 
02204       for (_RandomAccessIterator __i = __first; __i != __last; ++__i)
02205     std::__unguarded_linear_insert(__i);
02206     }
02207 
02208   /// This is a helper function for the sort routine.
02209   template<typename _RandomAccessIterator, typename _Compare>
02210     inline void
02211     __unguarded_insertion_sort(_RandomAccessIterator __first,
02212                    _RandomAccessIterator __last, _Compare __comp)
02213     {
02214       typedef typename iterator_traits<_RandomAccessIterator>::value_type
02215     _ValueType;
02216 
02217       for (_RandomAccessIterator __i = __first; __i != __last; ++__i)
02218     std::__unguarded_linear_insert(__i, __comp);
02219     }
02220 
02221   /**
02222    *  @doctodo
02223    *  This controls some aspect of the sort routines.
02224   */
02225   enum { _S_threshold = 16 };
02226 
02227   /// This is a helper function for the sort routine.
02228   template<typename _RandomAccessIterator>
02229     void
02230     __final_insertion_sort(_RandomAccessIterator __first,
02231                _RandomAccessIterator __last)
02232     {
02233       if (__last - __first > int(_S_threshold))
02234     {
02235       std::__insertion_sort(__first, __first + int(_S_threshold));
02236       std::__unguarded_insertion_sort(__first + int(_S_threshold), __last);
02237     }
02238       else
02239     std::__insertion_sort(__first, __last);
02240     }
02241 
02242   /// This is a helper function for the sort routine.
02243   template<typename _RandomAccessIterator, typename _Compare>
02244     void
02245     __final_insertion_sort(_RandomAccessIterator __first,
02246                _RandomAccessIterator __last, _Compare __comp)
02247     {
02248       if (__last - __first > int(_S_threshold))
02249     {
02250       std::__insertion_sort(__first, __first + int(_S_threshold), __comp);
02251       std::__unguarded_insertion_sort(__first + int(_S_threshold), __last,
02252                       __comp);
02253     }
02254       else
02255     std::__insertion_sort(__first, __last, __comp);
02256     }
02257 
02258   /// This is a helper function...
02259   template<typename _RandomAccessIterator, typename _Tp>
02260     _RandomAccessIterator
02261     __unguarded_partition(_RandomAccessIterator __first,
02262               _RandomAccessIterator __last, const _Tp& __pivot)
02263     {
02264       while (true)
02265     {
02266       while (*__first < __pivot)
02267         ++__first;
02268       --__last;
02269       while (__pivot < *__last)
02270         --__last;
02271       if (!(__first < __last))
02272         return __first;
02273       std::iter_swap(__first, __last);
02274       ++__first;
02275     }
02276     }
02277 
02278   /// This is a helper function...
02279   template<typename _RandomAccessIterator, typename _Tp, typename _Compare>
02280     _RandomAccessIterator
02281     __unguarded_partition(_RandomAccessIterator __first,
02282               _RandomAccessIterator __last,
02283               const _Tp& __pivot, _Compare __comp)
02284     {
02285       while (true)
02286     {
02287       while (__comp(*__first, __pivot))
02288         ++__first;
02289       --__last;
02290       while (__comp(__pivot, *__last))
02291         --__last;
02292       if (!(__first < __last))
02293         return __first;
02294       std::iter_swap(__first, __last);
02295       ++__first;
02296     }
02297     }
02298 
02299   /// This is a helper function...
02300   template<typename _RandomAccessIterator>
02301     inline _RandomAccessIterator
02302     __unguarded_partition_pivot(_RandomAccessIterator __first,
02303                 _RandomAccessIterator __last)
02304     {
02305       _RandomAccessIterator __mid = __first + (__last - __first) / 2;
02306       std::__move_median_first(__first, __mid, (__last - 1));
02307       return std::__unguarded_partition(__first + 1, __last, *__first);
02308     }
02309 
02310 
02311   /// This is a helper function...
02312   template<typename _RandomAccessIterator, typename _Compare>
02313     inline _RandomAccessIterator
02314     __unguarded_partition_pivot(_RandomAccessIterator __first,
02315                 _RandomAccessIterator __last, _Compare __comp)
02316     {
02317       _RandomAccessIterator __mid = __first + (__last - __first) / 2;
02318       std::__move_median_first(__first, __mid, (__last - 1), __comp);
02319       return std::__unguarded_partition(__first + 1, __last, *__first, __comp);
02320     }
02321 
02322   /// This is a helper function for the sort routine.
02323   template<typename _RandomAccessIterator, typename _Size>
02324     void
02325     __introsort_loop(_RandomAccessIterator __first,
02326              _RandomAccessIterator __last,
02327              _Size __depth_limit)
02328     {
02329       while (__last - __first > int(_S_threshold))
02330     {
02331       if (__depth_limit == 0)
02332         {
02333           _GLIBCXX_STD_A::partial_sort(__first, __last, __last);
02334           return;
02335         }
02336       --__depth_limit;
02337       _RandomAccessIterator __cut =
02338         std::__unguarded_partition_pivot(__first, __last);
02339       std::__introsort_loop(__cut, __last, __depth_limit);
02340       __last = __cut;
02341     }
02342     }
02343 
02344   /// This is a helper function for the sort routine.
02345   template<typename _RandomAccessIterator, typename _Size, typename _Compare>
02346     void
02347     __introsort_loop(_RandomAccessIterator __first,
02348              _RandomAccessIterator __last,
02349              _Size __depth_limit, _Compare __comp)
02350     {
02351       while (__last - __first > int(_S_threshold))
02352     {
02353       if (__depth_limit == 0)
02354         {
02355           _GLIBCXX_STD_A::partial_sort(__first, __last, __last, __comp);
02356           return;
02357         }
02358       --__depth_limit;
02359       _RandomAccessIterator __cut =
02360         std::__unguarded_partition_pivot(__first, __last, __comp);
02361       std::__introsort_loop(__cut, __last, __depth_limit, __comp);
02362       __last = __cut;
02363     }
02364     }
02365 
02366   // sort
02367 
02368   template<typename _RandomAccessIterator, typename _Size>
02369     void
02370     __introselect(_RandomAccessIterator __first, _RandomAccessIterator __nth,
02371           _RandomAccessIterator __last, _Size __depth_limit)
02372     {
02373       typedef typename iterator_traits<_RandomAccessIterator>::value_type
02374     _ValueType;
02375 
02376       while (__last - __first > 3)
02377     {
02378       if (__depth_limit == 0)
02379         {
02380           std::__heap_select(__first, __nth + 1, __last);
02381 
02382           // Place the nth largest element in its final position.
02383           std::iter_swap(__first, __nth);
02384           return;
02385         }
02386       --__depth_limit;
02387       _RandomAccessIterator __cut =
02388         std::__unguarded_partition_pivot(__first, __last);
02389       if (__cut <= __nth)
02390         __first = __cut;
02391       else
02392         __last = __cut;
02393     }
02394       std::__insertion_sort(__first, __last);
02395     }
02396 
02397   template<typename _RandomAccessIterator, typename _Size, typename _Compare>
02398     void
02399     __introselect(_RandomAccessIterator __first, _RandomAccessIterator __nth,
02400           _RandomAccessIterator __last, _Size __depth_limit,
02401           _Compare __comp)
02402     {
02403       typedef typename iterator_traits<_RandomAccessIterator>::value_type
02404     _ValueType;
02405 
02406       while (__last - __first > 3)
02407     {
02408       if (__depth_limit == 0)
02409         {
02410           std::__heap_select(__first, __nth + 1, __last, __comp);
02411           // Place the nth largest element in its final position.
02412           std::iter_swap(__first, __nth);
02413           return;
02414         }
02415       --__depth_limit;
02416       _RandomAccessIterator __cut =
02417         std::__unguarded_partition_pivot(__first, __last, __comp);
02418       if (__cut <= __nth)
02419         __first = __cut;
02420       else
02421         __last = __cut;
02422     }
02423       std::__insertion_sort(__first, __last, __comp);
02424     }
02425 
02426   // nth_element
02427 
02428   // lower_bound moved to stl_algobase.h
02429 
02430   /**
02431    *  @brief Finds the first position in which @p __val could be inserted
02432    *         without changing the ordering.
02433    *  @ingroup binary_search_algorithms
02434    *  @param  __first   An iterator.
02435    *  @param  __last    Another iterator.
02436    *  @param  __val     The search term.
02437    *  @param  __comp    A functor to use for comparisons.
02438    *  @return An iterator pointing to the first element <em>not less
02439    *           than</em> @p __val, or end() if every element is less
02440    *           than @p __val.
02441    *  @ingroup binary_search_algorithms
02442    *
02443    *  The comparison function should have the same effects on ordering as
02444    *  the function used for the initial sort.
02445   */
02446   template<typename _ForwardIterator, typename _Tp, typename _Compare>
02447     _ForwardIterator
02448     lower_bound(_ForwardIterator __first, _ForwardIterator __last,
02449         const _Tp& __val, _Compare __comp)
02450     {
02451       typedef typename iterator_traits<_ForwardIterator>::value_type
02452     _ValueType;
02453       typedef typename iterator_traits<_ForwardIterator>::difference_type
02454     _DistanceType;
02455 
02456       // concept requirements
02457       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
02458       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
02459                   _ValueType, _Tp>)
02460       __glibcxx_requires_partitioned_lower_pred(__first, __last,
02461                         __val, __comp);
02462 
02463       _DistanceType __len = std::distance(__first, __last);
02464 
02465       while (__len > 0)
02466     {
02467       _DistanceType __half = __len >> 1;
02468       _ForwardIterator __middle = __first;
02469       std::advance(__middle, __half);
02470       if (__comp(*__middle, __val))
02471         {
02472           __first = __middle;
02473           ++__first;
02474           __len = __len - __half - 1;
02475         }
02476       else
02477         __len = __half;
02478     }
02479       return __first;
02480     }
02481 
02482   /**
02483    *  @brief Finds the last position in which @p __val could be inserted
02484    *         without changing the ordering.
02485    *  @ingroup binary_search_algorithms
02486    *  @param  __first   An iterator.
02487    *  @param  __last    Another iterator.
02488    *  @param  __val     The search term.
02489    *  @return  An iterator pointing to the first element greater than @p __val,
02490    *           or end() if no elements are greater than @p __val.
02491    *  @ingroup binary_search_algorithms
02492   */
02493   template<typename _ForwardIterator, typename _Tp>
02494     _ForwardIterator
02495     upper_bound(_ForwardIterator __first, _ForwardIterator __last,
02496         const _Tp& __val)
02497     {
02498       typedef typename iterator_traits<_ForwardIterator>::value_type
02499     _ValueType;
02500       typedef typename iterator_traits<_ForwardIterator>::difference_type
02501     _DistanceType;
02502 
02503       // concept requirements
02504       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
02505       __glibcxx_function_requires(_LessThanOpConcept<_Tp, _ValueType>)
02506       __glibcxx_requires_partitioned_upper(__first, __last, __val);
02507 
02508       _DistanceType __len = std::distance(__first, __last);
02509 
02510       while (__len > 0)
02511     {
02512       _DistanceType __half = __len >> 1;
02513       _ForwardIterator __middle = __first;
02514       std::advance(__middle, __half);
02515       if (__val < *__middle)
02516         __len = __half;
02517       else
02518         {
02519           __first = __middle;
02520           ++__first;
02521           __len = __len - __half - 1;
02522         }
02523     }
02524       return __first;
02525     }
02526 
02527   /**
02528    *  @brief Finds the last position in which @p __val could be inserted
02529    *         without changing the ordering.
02530    *  @ingroup binary_search_algorithms
02531    *  @param  __first   An iterator.
02532    *  @param  __last    Another iterator.
02533    *  @param  __val     The search term.
02534    *  @param  __comp    A functor to use for comparisons.
02535    *  @return  An iterator pointing to the first element greater than @p __val,
02536    *           or end() if no elements are greater than @p __val.
02537    *  @ingroup binary_search_algorithms
02538    *
02539    *  The comparison function should have the same effects on ordering as
02540    *  the function used for the initial sort.
02541   */
02542   template<typename _ForwardIterator, typename _Tp, typename _Compare>
02543     _ForwardIterator
02544     upper_bound(_ForwardIterator __first, _ForwardIterator __last,
02545         const _Tp& __val, _Compare __comp)
02546     {
02547       typedef typename iterator_traits<_ForwardIterator>::value_type
02548     _ValueType;
02549       typedef typename iterator_traits<_ForwardIterator>::difference_type
02550     _DistanceType;
02551 
02552       // concept requirements
02553       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
02554       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
02555                   _Tp, _ValueType>)
02556       __glibcxx_requires_partitioned_upper_pred(__first, __last,
02557                         __val, __comp);
02558 
02559       _DistanceType __len = std::distance(__first, __last);
02560 
02561       while (__len > 0)
02562     {
02563       _DistanceType __half = __len >> 1;
02564       _ForwardIterator __middle = __first;
02565       std::advance(__middle, __half);
02566       if (__comp(__val, *__middle))
02567         __len = __half;
02568       else
02569         {
02570           __first = __middle;
02571           ++__first;
02572           __len = __len - __half - 1;
02573         }
02574     }
02575       return __first;
02576     }
02577 
02578   /**
02579    *  @brief Finds the largest subrange in which @p __val could be inserted
02580    *         at any place in it without changing the ordering.
02581    *  @ingroup binary_search_algorithms
02582    *  @param  __first   An iterator.
02583    *  @param  __last    Another iterator.
02584    *  @param  __val     The search term.
02585    *  @return  An pair of iterators defining the subrange.
02586    *  @ingroup binary_search_algorithms
02587    *
02588    *  This is equivalent to
02589    *  @code
02590    *    std::make_pair(lower_bound(__first, __last, __val),
02591    *                   upper_bound(__first, __last, __val))
02592    *  @endcode
02593    *  but does not actually call those functions.
02594   */
02595   template<typename _ForwardIterator, typename _Tp>
02596     pair<_ForwardIterator, _ForwardIterator>
02597     equal_range(_ForwardIterator __first, _ForwardIterator __last,
02598         const _Tp& __val)
02599     {
02600       typedef typename iterator_traits<_ForwardIterator>::value_type
02601     _ValueType;
02602       typedef typename iterator_traits<_ForwardIterator>::difference_type
02603     _DistanceType;
02604 
02605       // concept requirements
02606       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
02607       __glibcxx_function_requires(_LessThanOpConcept<_ValueType, _Tp>)
02608       __glibcxx_function_requires(_LessThanOpConcept<_Tp, _ValueType>)  
02609       __glibcxx_requires_partitioned_lower(__first, __last, __val);
02610       __glibcxx_requires_partitioned_upper(__first, __last, __val);      
02611 
02612       _DistanceType __len = std::distance(__first, __last);
02613  
02614       while (__len > 0)
02615     {
02616       _DistanceType __half = __len >> 1;
02617       _ForwardIterator __middle = __first;
02618       std::advance(__middle, __half);
02619       if (*__middle < __val)
02620         {
02621           __first = __middle;
02622           ++__first;
02623           __len = __len - __half - 1;
02624         }
02625       else if (__val < *__middle)
02626         __len = __half;
02627       else
02628         {
02629           _ForwardIterator __left = std::lower_bound(__first, __middle,
02630                              __val);
02631           std::advance(__first, __len);
02632           _ForwardIterator __right = std::upper_bound(++__middle, __first,
02633                               __val);
02634           return pair<_ForwardIterator, _ForwardIterator>(__left, __right);
02635         }
02636     }
02637       return pair<_ForwardIterator, _ForwardIterator>(__first, __first);
02638     }
02639 
02640   /**
02641    *  @brief Finds the largest subrange in which @p __val could be inserted
02642    *         at any place in it without changing the ordering.
02643    *  @param  __first   An iterator.
02644    *  @param  __last    Another iterator.
02645    *  @param  __val     The search term.
02646    *  @param  __comp    A functor to use for comparisons.
02647    *  @return  An pair of iterators defining the subrange.
02648    *  @ingroup binary_search_algorithms
02649    *
02650    *  This is equivalent to
02651    *  @code
02652    *    std::make_pair(lower_bound(__first, __last, __val, __comp),
02653    *                   upper_bound(__first, __last, __val, __comp))
02654    *  @endcode
02655    *  but does not actually call those functions.
02656   */
02657   template<typename _ForwardIterator, typename _Tp, typename _Compare>
02658     pair<_ForwardIterator, _ForwardIterator>
02659     equal_range(_ForwardIterator __first, _ForwardIterator __last,
02660         const _Tp& __val, _Compare __comp)
02661     {
02662       typedef typename iterator_traits<_ForwardIterator>::value_type
02663     _ValueType;
02664       typedef typename iterator_traits<_ForwardIterator>::difference_type
02665     _DistanceType;
02666 
02667       // concept requirements
02668       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
02669       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
02670                   _ValueType, _Tp>)
02671       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
02672                   _Tp, _ValueType>)
02673       __glibcxx_requires_partitioned_lower_pred(__first, __last,
02674                         __val, __comp);
02675       __glibcxx_requires_partitioned_upper_pred(__first, __last,
02676                         __val, __comp);
02677 
02678       _DistanceType __len = std::distance(__first, __last);
02679 
02680       while (__len > 0)
02681     {
02682       _DistanceType __half = __len >> 1;
02683       _ForwardIterator __middle = __first;
02684       std::advance(__middle, __half);
02685       if (__comp(*__middle, __val))
02686         {
02687           __first = __middle;
02688           ++__first;
02689           __len = __len - __half - 1;
02690         }
02691       else if (__comp(__val, *__middle))
02692         __len = __half;
02693       else
02694         {
02695           _ForwardIterator __left = std::lower_bound(__first, __middle,
02696                              __val, __comp);
02697           std::advance(__first, __len);
02698           _ForwardIterator __right = std::upper_bound(++__middle, __first,
02699                               __val, __comp);
02700           return pair<_ForwardIterator, _ForwardIterator>(__left, __right);
02701         }
02702     }
02703       return pair<_ForwardIterator, _ForwardIterator>(__first, __first);
02704     }
02705 
02706   /**
02707    *  @brief Determines whether an element exists in a range.
02708    *  @ingroup binary_search_algorithms
02709    *  @param  __first   An iterator.
02710    *  @param  __last    Another iterator.
02711    *  @param  __val     The search term.
02712    *  @return True if @p __val (or its equivalent) is in [@p
02713    *  __first,@p __last ].
02714    *
02715    *  Note that this does not actually return an iterator to @p __val.  For
02716    *  that, use std::find or a container's specialized find member functions.
02717   */
02718   template<typename _ForwardIterator, typename _Tp>
02719     bool
02720     binary_search(_ForwardIterator __first, _ForwardIterator __last,
02721                   const _Tp& __val)
02722     {
02723       typedef typename iterator_traits<_ForwardIterator>::value_type
02724     _ValueType;
02725 
02726       // concept requirements
02727       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
02728       __glibcxx_function_requires(_LessThanOpConcept<_Tp, _ValueType>)
02729       __glibcxx_requires_partitioned_lower(__first, __last, __val);
02730       __glibcxx_requires_partitioned_upper(__first, __last, __val);
02731 
02732       _ForwardIterator __i = std::lower_bound(__first, __last, __val);
02733       return __i != __last && !(__val < *__i);
02734     }
02735 
02736   /**
02737    *  @brief Determines whether an element exists in a range.
02738    *  @ingroup binary_search_algorithms
02739    *  @param  __first   An iterator.
02740    *  @param  __last    Another iterator.
02741    *  @param  __val     The search term.
02742    *  @param  __comp    A functor to use for comparisons.
02743    *  @return  True if @p __val (or its equivalent) is in @p [__first,__last].
02744    *
02745    *  Note that this does not actually return an iterator to @p __val.  For
02746    *  that, use std::find or a container's specialized find member functions.
02747    *
02748    *  The comparison function should have the same effects on ordering as
02749    *  the function used for the initial sort.
02750   */
02751   template<typename _ForwardIterator, typename _Tp, typename _Compare>
02752     bool
02753     binary_search(_ForwardIterator __first, _ForwardIterator __last,
02754                   const _Tp& __val, _Compare __comp)
02755     {
02756       typedef typename iterator_traits<_ForwardIterator>::value_type
02757     _ValueType;
02758 
02759       // concept requirements
02760       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
02761       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
02762                   _Tp, _ValueType>)
02763       __glibcxx_requires_partitioned_lower_pred(__first, __last,
02764                         __val, __comp);
02765       __glibcxx_requires_partitioned_upper_pred(__first, __last,
02766                         __val, __comp);
02767 
02768       _ForwardIterator __i = std::lower_bound(__first, __last, __val, __comp);
02769       return __i != __last && !bool(__comp(__val, *__i));
02770     }
02771 
02772   // merge
02773 
02774   /// This is a helper function for the __merge_adaptive routines.
02775   template<typename _InputIterator1, typename _InputIterator2,
02776        typename _OutputIterator>
02777     void
02778     __move_merge_adaptive(_InputIterator1 __first1, _InputIterator1 __last1,
02779               _InputIterator2 __first2, _InputIterator2 __last2,
02780               _OutputIterator __result)
02781     {
02782       while (__first1 != __last1 && __first2 != __last2)
02783     {
02784       if (*__first2 < *__first1)
02785         {
02786           *__result = _GLIBCXX_MOVE(*__first2);
02787           ++__first2;
02788         }
02789       else
02790         {
02791           *__result = _GLIBCXX_MOVE(*__first1);
02792           ++__first1;
02793         }
02794       ++__result;
02795     }
02796       if (__first1 != __last1)
02797     _GLIBCXX_MOVE3(__first1, __last1, __result);
02798     }
02799 
02800   /// This is a helper function for the __merge_adaptive routines.
02801   template<typename _InputIterator1, typename _InputIterator2,
02802        typename _OutputIterator, typename _Compare>
02803     void
02804     __move_merge_adaptive(_InputIterator1 __first1, _InputIterator1 __last1,
02805               _InputIterator2 __first2, _InputIterator2 __last2,
02806               _OutputIterator __result, _Compare __comp)
02807     {
02808       while (__first1 != __last1 && __first2 != __last2)
02809     {
02810       if (__comp(*__first2, *__first1))
02811         {
02812           *__result = _GLIBCXX_MOVE(*__first2);
02813           ++__first2;
02814         }
02815       else
02816         {
02817           *__result = _GLIBCXX_MOVE(*__first1);
02818           ++__first1;
02819         }
02820       ++__result;
02821     }
02822       if (__first1 != __last1)
02823     _GLIBCXX_MOVE3(__first1, __last1, __result);
02824     }
02825 
02826   /// This is a helper function for the __merge_adaptive routines.
02827   template<typename _BidirectionalIterator1, typename _BidirectionalIterator2,
02828        typename _BidirectionalIterator3>
02829     void
02830     __move_merge_adaptive_backward(_BidirectionalIterator1 __first1,
02831                    _BidirectionalIterator1 __last1,
02832                    _BidirectionalIterator2 __first2,
02833                    _BidirectionalIterator2 __last2,
02834                    _BidirectionalIterator3 __result)
02835     {
02836       if (__first1 == __last1)
02837     {
02838       _GLIBCXX_MOVE_BACKWARD3(__first2, __last2, __result);
02839       return;
02840     }
02841       else if (__first2 == __last2)
02842     return;
02843 
02844       --__last1;
02845       --__last2;
02846       while (true)
02847     {
02848       if (*__last2 < *__last1)
02849         {
02850           *--__result = _GLIBCXX_MOVE(*__last1);
02851           if (__first1 == __last1)
02852         {
02853           _GLIBCXX_MOVE_BACKWARD3(__first2, ++__last2, __result);
02854           return;
02855         }
02856           --__last1;
02857         }
02858       else
02859         {
02860           *--__result = _GLIBCXX_MOVE(*__last2);
02861           if (__first2 == __last2)
02862         return;
02863           --__last2;
02864         }
02865     }
02866     }
02867 
02868   /// This is a helper function for the __merge_adaptive routines.
02869   template<typename _BidirectionalIterator1, typename _BidirectionalIterator2,
02870        typename _BidirectionalIterator3, typename _Compare>
02871     void
02872     __move_merge_adaptive_backward(_BidirectionalIterator1 __first1,
02873                    _BidirectionalIterator1 __last1,
02874                    _BidirectionalIterator2 __first2,
02875                    _BidirectionalIterator2 __last2,
02876                    _BidirectionalIterator3 __result,
02877                    _Compare __comp)
02878     {
02879       if (__first1 == __last1)
02880     {
02881       _GLIBCXX_MOVE_BACKWARD3(__first2, __last2, __result);
02882       return;
02883     }
02884       else if (__first2 == __last2)
02885     return;
02886 
02887       --__last1;
02888       --__last2;
02889       while (true)
02890     {
02891       if (__comp(*__last2, *__last1))
02892         {
02893           *--__result = _GLIBCXX_MOVE(*__last1);
02894           if (__first1 == __last1)
02895         {
02896           _GLIBCXX_MOVE_BACKWARD3(__first2, ++__last2, __result);
02897           return;
02898         }
02899           --__last1;
02900         }
02901       else
02902         {
02903           *--__result = _GLIBCXX_MOVE(*__last2);
02904           if (__first2 == __last2)
02905         return;
02906           --__last2;
02907         }
02908     }
02909     }
02910 
02911   /// This is a helper function for the merge routines.
02912   template<typename _BidirectionalIterator1, typename _BidirectionalIterator2,
02913        typename _Distance>
02914     _BidirectionalIterator1
02915     __rotate_adaptive(_BidirectionalIterator1 __first,
02916               _BidirectionalIterator1 __middle,
02917               _BidirectionalIterator1 __last,
02918               _Distance __len1, _Distance __len2,
02919               _BidirectionalIterator2 __buffer,
02920               _Distance __buffer_size)
02921     {
02922       _BidirectionalIterator2 __buffer_end;
02923       if (__len1 > __len2 && __len2 <= __buffer_size)
02924     {
02925       if (__len2)
02926         {
02927           __buffer_end = _GLIBCXX_MOVE3(__middle, __last, __buffer);
02928           _GLIBCXX_MOVE_BACKWARD3(__first, __middle, __last);
02929           return _GLIBCXX_MOVE3(__buffer, __buffer_end, __first);
02930         }
02931       else
02932         return __first;
02933     }
02934       else if (__len1 <= __buffer_size)
02935     {
02936       if (__len1)
02937         {
02938           __buffer_end = _GLIBCXX_MOVE3(__first, __middle, __buffer);
02939           _GLIBCXX_MOVE3(__middle, __last, __first);
02940           return _GLIBCXX_MOVE_BACKWARD3(__buffer, __buffer_end, __last);
02941         }
02942       else
02943         return __last;
02944     }
02945       else
02946     {
02947       std::rotate(__first, __middle, __last);
02948       std::advance(__first, std::distance(__middle, __last));
02949       return __first;
02950     }
02951     }
02952 
02953   /// This is a helper function for the merge routines.
02954   template<typename _BidirectionalIterator, typename _Distance,
02955        typename _Pointer>
02956     void
02957     __merge_adaptive(_BidirectionalIterator __first,
02958                      _BidirectionalIterator __middle,
02959              _BidirectionalIterator __last,
02960              _Distance __len1, _Distance __len2,
02961              _Pointer __buffer, _Distance __buffer_size)
02962     {
02963       if (__len1 <= __len2 && __len1 <= __buffer_size)
02964     {
02965       _Pointer __buffer_end = _GLIBCXX_MOVE3(__first, __middle, __buffer);
02966       std::__move_merge_adaptive(__buffer, __buffer_end, __middle, __last,
02967                      __first);
02968     }
02969       else if (__len2 <= __buffer_size)
02970     {
02971       _Pointer __buffer_end = _GLIBCXX_MOVE3(__middle, __last, __buffer);
02972       std::__move_merge_adaptive_backward(__first, __middle, __buffer,
02973                           __buffer_end, __last);
02974     }
02975       else
02976     {
02977       _BidirectionalIterator __first_cut = __first;
02978       _BidirectionalIterator __second_cut = __middle;
02979       _Distance __len11 = 0;
02980       _Distance __len22 = 0;
02981       if (__len1 > __len2)
02982         {
02983           __len11 = __len1 / 2;
02984           std::advance(__first_cut, __len11);
02985           __second_cut = std::lower_bound(__middle, __last,
02986                           *__first_cut);
02987           __len22 = std::distance(__middle, __second_cut);
02988         }
02989       else
02990         {
02991           __len22 = __len2 / 2;
02992           std::advance(__second_cut, __len22);
02993           __first_cut = std::upper_bound(__first, __middle,
02994                          *__second_cut);
02995           __len11 = std::distance(__first, __first_cut);
02996         }
02997       _BidirectionalIterator __new_middle =
02998         std::__rotate_adaptive(__first_cut, __middle, __second_cut,
02999                    __len1 - __len11, __len22, __buffer,
03000                    __buffer_size);
03001       std::__merge_adaptive(__first, __first_cut, __new_middle, __len11,
03002                 __len22, __buffer, __buffer_size);
03003       std::__merge_adaptive(__new_middle, __second_cut, __last,
03004                 __len1 - __len11,
03005                 __len2 - __len22, __buffer, __buffer_size);
03006     }
03007     }
03008 
03009   /// This is a helper function for the merge routines.
03010   template<typename _BidirectionalIterator, typename _Distance, 
03011        typename _Pointer, typename _Compare>
03012     void
03013     __merge_adaptive(_BidirectionalIterator __first,
03014                      _BidirectionalIterator __middle,
03015              _BidirectionalIterator __last,
03016              _Distance __len1, _Distance __len2,
03017              _Pointer __buffer, _Distance __buffer_size,
03018              _Compare __comp)
03019     {
03020       if (__len1 <= __len2 && __len1 <= __buffer_size)
03021     {
03022       _Pointer __buffer_end = _GLIBCXX_MOVE3(__first, __middle, __buffer);
03023       std::__move_merge_adaptive(__buffer, __buffer_end, __middle, __last,
03024                      __first, __comp);
03025     }
03026       else if (__len2 <= __buffer_size)
03027     {
03028       _Pointer __buffer_end = _GLIBCXX_MOVE3(__middle, __last, __buffer);
03029       std::__move_merge_adaptive_backward(__first, __middle, __buffer,
03030                           __buffer_end, __last, __comp);
03031     }
03032       else
03033     {
03034       _BidirectionalIterator __first_cut = __first;
03035       _BidirectionalIterator __second_cut = __middle;
03036       _Distance __len11 = 0;
03037       _Distance __len22 = 0;
03038       if (__len1 > __len2)
03039         {
03040           __len11 = __len1 / 2;
03041           std::advance(__first_cut, __len11);
03042           __second_cut = std::lower_bound(__middle, __last, *__first_cut,
03043                           __comp);
03044           __len22 = std::distance(__middle, __second_cut);
03045         }
03046       else
03047         {
03048           __len22 = __len2 / 2;
03049           std::advance(__second_cut, __len22);
03050           __first_cut = std::upper_bound(__first, __middle, *__second_cut,
03051                          __comp);
03052           __len11 = std::distance(__first, __first_cut);
03053         }
03054       _BidirectionalIterator __new_middle =
03055         std::__rotate_adaptive(__first_cut, __middle, __second_cut,
03056                    __len1 - __len11, __len22, __buffer,
03057                    __buffer_size);
03058       std::__merge_adaptive(__first, __first_cut, __new_middle, __len11,
03059                 __len22, __buffer, __buffer_size, __comp);
03060       std::__merge_adaptive(__new_middle, __second_cut, __last,
03061                 __len1 - __len11,
03062                 __len2 - __len22, __buffer,
03063                 __buffer_size, __comp);
03064     }
03065     }
03066 
03067   /// This is a helper function for the merge routines.
03068   template<typename _BidirectionalIterator, typename _Distance>
03069     void
03070     __merge_without_buffer(_BidirectionalIterator __first,
03071                _BidirectionalIterator __middle,
03072                _BidirectionalIterator __last,
03073                _Distance __len1, _Distance __len2)
03074     {
03075       if (__len1 == 0 || __len2 == 0)
03076     return;
03077       if (__len1 + __len2 == 2)
03078     {
03079       if (*__middle < *__first)
03080         std::iter_swap(__first, __middle);
03081       return;
03082     }
03083       _BidirectionalIterator __first_cut = __first;
03084       _BidirectionalIterator __second_cut = __middle;
03085       _Distance __len11 = 0;
03086       _Distance __len22 = 0;
03087       if (__len1 > __len2)
03088     {
03089       __len11 = __len1 / 2;
03090       std::advance(__first_cut, __len11);
03091       __second_cut = std::lower_bound(__middle, __last, *__first_cut);
03092       __len22 = std::distance(__middle, __second_cut);
03093     }
03094       else
03095     {
03096       __len22 = __len2 / 2;
03097       std::advance(__second_cut, __len22);
03098       __first_cut = std::upper_bound(__first, __middle, *__second_cut);
03099       __len11 = std::distance(__first, __first_cut);
03100     }
03101       std::rotate(__first_cut, __middle, __second_cut);
03102       _BidirectionalIterator __new_middle = __first_cut;
03103       std::advance(__new_middle, std::distance(__middle, __second_cut));
03104       std::__merge_without_buffer(__first, __first_cut, __new_middle,
03105                   __len11, __len22);
03106       std::__merge_without_buffer(__new_middle, __second_cut, __last,
03107                   __len1 - __len11, __len2 - __len22);
03108     }
03109 
03110   /// This is a helper function for the merge routines.
03111   template<typename _BidirectionalIterator, typename _Distance,
03112        typename _Compare>
03113     void
03114     __merge_without_buffer(_BidirectionalIterator __first,
03115                            _BidirectionalIterator __middle,
03116                _BidirectionalIterator __last,
03117                _Distance __len1, _Distance __len2,
03118                _Compare __comp)
03119     {
03120       if (__len1 == 0 || __len2 == 0)
03121     return;
03122       if (__len1 + __len2 == 2)
03123     {
03124       if (__comp(*__middle, *__first))
03125         std::iter_swap(__first, __middle);
03126       return;
03127     }
03128       _BidirectionalIterator __first_cut = __first;
03129       _BidirectionalIterator __second_cut = __middle;
03130       _Distance __len11 = 0;
03131       _Distance __len22 = 0;
03132       if (__len1 > __len2)
03133     {
03134       __len11 = __len1 / 2;
03135       std::advance(__first_cut, __len11);
03136       __second_cut = std::lower_bound(__middle, __last, *__first_cut,
03137                       __comp);
03138       __len22 = std::distance(__middle, __second_cut);
03139     }
03140       else
03141     {
03142       __len22 = __len2 / 2;
03143       std::advance(__second_cut, __len22);
03144       __first_cut = std::upper_bound(__first, __middle, *__second_cut,
03145                      __comp);
03146       __len11 = std::distance(__first, __first_cut);
03147     }
03148       std::rotate(__first_cut, __middle, __second_cut);
03149       _BidirectionalIterator __new_middle = __first_cut;
03150       std::advance(__new_middle, std::distance(__middle, __second_cut));
03151       std::__merge_without_buffer(__first, __first_cut, __new_middle,
03152                   __len11, __len22, __comp);
03153       std::__merge_without_buffer(__new_middle, __second_cut, __last,
03154                   __len1 - __len11, __len2 - __len22, __comp);
03155     }
03156 
03157   /**
03158    *  @brief Merges two sorted ranges in place.
03159    *  @ingroup sorting_algorithms
03160    *  @param  __first   An iterator.
03161    *  @param  __middle  Another iterator.
03162    *  @param  __last    Another iterator.
03163    *  @return  Nothing.
03164    *
03165    *  Merges two sorted and consecutive ranges, [__first,__middle) and
03166    *  [__middle,__last), and puts the result in [__first,__last).  The
03167    *  output will be sorted.  The sort is @e stable, that is, for
03168    *  equivalent elements in the two ranges, elements from the first
03169    *  range will always come before elements from the second.
03170    *
03171    *  If enough additional memory is available, this takes (__last-__first)-1
03172    *  comparisons.  Otherwise an NlogN algorithm is used, where N is
03173    *  distance(__first,__last).
03174   */
03175   template<typename _BidirectionalIterator>
03176     void
03177     inplace_merge(_BidirectionalIterator __first,
03178           _BidirectionalIterator __middle,
03179           _BidirectionalIterator __last)
03180     {
03181       typedef typename iterator_traits<_BidirectionalIterator>::value_type
03182           _ValueType;
03183       typedef typename iterator_traits<_BidirectionalIterator>::difference_type
03184           _DistanceType;
03185 
03186       // concept requirements
03187       __glibcxx_function_requires(_Mutable_BidirectionalIteratorConcept<
03188         _BidirectionalIterator>)
03189       __glibcxx_function_requires(_LessThanComparableConcept<_ValueType>)
03190       __glibcxx_requires_sorted(__first, __middle);
03191       __glibcxx_requires_sorted(__middle, __last);
03192 
03193       if (__first == __middle || __middle == __last)
03194     return;
03195 
03196       _DistanceType __len1 = std::distance(__first, __middle);
03197       _DistanceType __len2 = std::distance(__middle, __last);
03198 
03199       _Temporary_buffer<_BidirectionalIterator, _ValueType> __buf(__first,
03200                                   __last);
03201       if (__buf.begin() == 0)
03202     std::__merge_without_buffer(__first, __middle, __last, __len1, __len2);
03203       else
03204     std::__merge_adaptive(__first, __middle, __last, __len1, __len2,
03205                   __buf.begin(), _DistanceType(__buf.size()));
03206     }
03207 
03208   /**
03209    *  @brief Merges two sorted ranges in place.
03210    *  @ingroup sorting_algorithms
03211    *  @param  __first   An iterator.
03212    *  @param  __middle  Another iterator.
03213    *  @param  __last    Another iterator.
03214    *  @param  __comp    A functor to use for comparisons.
03215    *  @return  Nothing.
03216    *
03217    *  Merges two sorted and consecutive ranges, [__first,__middle) and
03218    *  [middle,last), and puts the result in [__first,__last).  The output will
03219    *  be sorted.  The sort is @e stable, that is, for equivalent
03220    *  elements in the two ranges, elements from the first range will always
03221    *  come before elements from the second.
03222    *
03223    *  If enough additional memory is available, this takes (__last-__first)-1
03224    *  comparisons.  Otherwise an NlogN algorithm is used, where N is
03225    *  distance(__first,__last).
03226    *
03227    *  The comparison function should have the same effects on ordering as
03228    *  the function used for the initial sort.
03229   */
03230   template<typename _BidirectionalIterator, typename _Compare>
03231     void
03232     inplace_merge(_BidirectionalIterator __first,
03233           _BidirectionalIterator __middle,
03234           _BidirectionalIterator __last,
03235           _Compare __comp)
03236     {
03237       typedef typename iterator_traits<_BidirectionalIterator>::value_type
03238           _ValueType;
03239       typedef typename iterator_traits<_BidirectionalIterator>::difference_type
03240           _DistanceType;
03241 
03242       // concept requirements
03243       __glibcxx_function_requires(_Mutable_BidirectionalIteratorConcept<
03244         _BidirectionalIterator>)
03245       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
03246         _ValueType, _ValueType>)
03247       __glibcxx_requires_sorted_pred(__first, __middle, __comp);
03248       __glibcxx_requires_sorted_pred(__middle, __last, __comp);
03249 
03250       if (__first == __middle || __middle == __last)
03251     return;
03252 
03253       const _DistanceType __len1 = std::distance(__first, __middle);
03254       const _DistanceType __len2 = std::distance(__middle, __last);
03255 
03256       _Temporary_buffer<_BidirectionalIterator, _ValueType> __buf(__first,
03257                                   __last);
03258       if (__buf.begin() == 0)
03259     std::__merge_without_buffer(__first, __middle, __last, __len1,
03260                     __len2, __comp);
03261       else
03262     std::__merge_adaptive(__first, __middle, __last, __len1, __len2,
03263                   __buf.begin(), _DistanceType(__buf.size()),
03264                   __comp);
03265     }
03266 
03267 
03268   /// This is a helper function for the __merge_sort_loop routines.
03269   template<typename _InputIterator1, typename _InputIterator2,
03270        typename _OutputIterator>
03271     _OutputIterator
03272     __move_merge(_InputIterator1 __first1, _InputIterator1 __last1,
03273          _InputIterator2 __first2, _InputIterator2 __last2,
03274          _OutputIterator __result)
03275     {
03276       while (__first1 != __last1 && __first2 != __last2)
03277     {
03278       if (*__first2 < *__first1)
03279         {
03280           *__result = _GLIBCXX_MOVE(*__first2);
03281           ++__first2;
03282         }
03283       else
03284         {
03285           *__result = _GLIBCXX_MOVE(*__first1);
03286           ++__first1;
03287         }
03288       ++__result;
03289     }
03290       return _GLIBCXX_MOVE3(__first2, __last2,
03291                 _GLIBCXX_MOVE3(__first1, __last1,
03292                        __result));
03293     }
03294 
03295   /// This is a helper function for the __merge_sort_loop routines.
03296   template<typename _InputIterator1, typename _InputIterator2,
03297        typename _OutputIterator, typename _Compare>
03298     _OutputIterator
03299     __move_merge(_InputIterator1 __first1, _InputIterator1 __last1,
03300          _InputIterator2 __first2, _InputIterator2 __last2,
03301          _OutputIterator __result, _Compare __comp)
03302     {
03303       while (__first1 != __last1 && __first2 != __last2)
03304     {
03305       if (__comp(*__first2, *__first1))
03306         {
03307           *__result = _GLIBCXX_MOVE(*__first2);
03308           ++__first2;
03309         }
03310       else
03311         {
03312           *__result = _GLIBCXX_MOVE(*__first1);
03313           ++__first1;
03314         }
03315       ++__result;
03316     }
03317       return _GLIBCXX_MOVE3(__first2, __last2,
03318                 _GLIBCXX_MOVE3(__first1, __last1,
03319                        __result));
03320     }
03321 
03322   template<typename _RandomAccessIterator1, typename _RandomAccessIterator2,
03323        typename _Distance>
03324     void
03325     __merge_sort_loop(_RandomAccessIterator1 __first,
03326               _RandomAccessIterator1 __last,
03327               _RandomAccessIterator2 __result,
03328               _Distance __step_size)
03329     {
03330       const _Distance __two_step = 2 * __step_size;
03331 
03332       while (__last - __first >= __two_step)
03333     {
03334       __result = std::__move_merge(__first, __first + __step_size,
03335                        __first + __step_size,
03336                        __first + __two_step, __result);
03337       __first += __two_step;
03338     }
03339 
03340       __step_size = std::min(_Distance(__last - __first), __step_size);
03341       std::__move_merge(__first, __first + __step_size,
03342             __first + __step_size, __last, __result);
03343     }
03344 
03345   template<typename _RandomAccessIterator1, typename _RandomAccessIterator2,
03346        typename _Distance, typename _Compare>
03347     void
03348     __merge_sort_loop(_RandomAccessIterator1 __first,
03349               _RandomAccessIterator1 __last,
03350               _RandomAccessIterator2 __result, _Distance __step_size,
03351               _Compare __comp)
03352     {
03353       const _Distance __two_step = 2 * __step_size;
03354 
03355       while (__last - __first >= __two_step)
03356     {
03357       __result = std::__move_merge(__first, __first + __step_size,
03358                        __first + __step_size,
03359                        __first + __two_step,
03360                        __result, __comp);
03361       __first += __two_step;
03362     }
03363       __step_size = std::min(_Distance(__last - __first), __step_size);
03364 
03365       std::__move_merge(__first,__first + __step_size,
03366             __first + __step_size, __last, __result, __comp);
03367     }
03368 
03369   template<typename _RandomAccessIterator, typename _Distance>
03370     void
03371     __chunk_insertion_sort(_RandomAccessIterator __first,
03372                _RandomAccessIterator __last,
03373                _Distance __chunk_size)
03374     {
03375       while (__last - __first >= __chunk_size)
03376     {
03377       std::__insertion_sort(__first, __first + __chunk_size);
03378       __first += __chunk_size;
03379     }
03380       std::__insertion_sort(__first, __last);
03381     }
03382 
03383   template<typename _RandomAccessIterator, typename _Distance,
03384        typename _Compare>
03385     void
03386     __chunk_insertion_sort(_RandomAccessIterator __first,
03387                _RandomAccessIterator __last,
03388                _Distance __chunk_size, _Compare __comp)
03389     {
03390       while (__last - __first >= __chunk_size)
03391     {
03392       std::__insertion_sort(__first, __first + __chunk_size, __comp);
03393       __first += __chunk_size;
03394     }
03395       std::__insertion_sort(__first, __last, __comp);
03396     }
03397 
03398   enum { _S_chunk_size = 7 };
03399 
03400   template<typename _RandomAccessIterator, typename _Pointer>
03401     void
03402     __merge_sort_with_buffer(_RandomAccessIterator __first,
03403                  _RandomAccessIterator __last,
03404                              _Pointer __buffer)
03405     {
03406       typedef typename iterator_traits<_RandomAccessIterator>::difference_type
03407     _Distance;
03408 
03409       const _Distance __len = __last - __first;
03410       const _Pointer __buffer_last = __buffer + __len;
03411 
03412       _Distance __step_size = _S_chunk_size;
03413       std::__chunk_insertion_sort(__first, __last, __step_size);
03414 
03415       while (__step_size < __len)
03416     {
03417       std::__merge_sort_loop(__first, __last, __buffer, __step_size);
03418       __step_size *= 2;
03419       std::__merge_sort_loop(__buffer, __buffer_last, __first, __step_size);
03420       __step_size *= 2;
03421     }
03422     }
03423 
03424   template<typename _RandomAccessIterator, typename _Pointer, typename _Compare>
03425     void
03426     __merge_sort_with_buffer(_RandomAccessIterator __first,
03427                  _RandomAccessIterator __last,
03428                              _Pointer __buffer, _Compare __comp)
03429     {
03430       typedef typename iterator_traits<_RandomAccessIterator>::difference_type
03431     _Distance;
03432 
03433       const _Distance __len = __last - __first;
03434       const _Pointer __buffer_last = __buffer + __len;
03435 
03436       _Distance __step_size = _S_chunk_size;
03437       std::__chunk_insertion_sort(__first, __last, __step_size, __comp);
03438 
03439       while (__step_size < __len)
03440     {
03441       std::__merge_sort_loop(__first, __last, __buffer,
03442                  __step_size, __comp);
03443       __step_size *= 2;
03444       std::__merge_sort_loop(__buffer, __buffer_last, __first,
03445                  __step_size, __comp);
03446       __step_size *= 2;
03447     }
03448     }
03449 
03450   template<typename _RandomAccessIterator, typename _Pointer,
03451        typename _Distance>
03452     void
03453     __stable_sort_adaptive(_RandomAccessIterator __first,
03454                _RandomAccessIterator __last,
03455                            _Pointer __buffer, _Distance __buffer_size)
03456     {
03457       const _Distance __len = (__last - __first + 1) / 2;
03458       const _RandomAccessIterator __middle = __first + __len;
03459       if (__len > __buffer_size)
03460     {
03461       std::__stable_sort_adaptive(__first, __middle,
03462                       __buffer, __buffer_size);
03463       std::__stable_sort_adaptive(__middle, __last,
03464                       __buffer, __buffer_size);
03465     }
03466       else
03467     {
03468       std::__merge_sort_with_buffer(__first, __middle, __buffer);
03469       std::__merge_sort_with_buffer(__middle, __last, __buffer);
03470     }
03471       std::__merge_adaptive(__first, __middle, __last,
03472                 _Distance(__middle - __first),
03473                 _Distance(__last - __middle),
03474                 __buffer, __buffer_size);
03475     }
03476 
03477   template<typename _RandomAccessIterator, typename _Pointer,
03478        typename _Distance, typename _Compare>
03479     void
03480     __stable_sort_adaptive(_RandomAccessIterator __first,
03481                _RandomAccessIterator __last,
03482                            _Pointer __buffer, _Distance __buffer_size,
03483                            _Compare __comp)
03484     {
03485       const _Distance __len = (__last - __first + 1) / 2;
03486       const _RandomAccessIterator __middle = __first + __len;
03487       if (__len > __buffer_size)
03488     {
03489       std::__stable_sort_adaptive(__first, __middle, __buffer,
03490                       __buffer_size, __comp);
03491       std::__stable_sort_adaptive(__middle, __last, __buffer,
03492                       __buffer_size, __comp);
03493     }
03494       else
03495     {
03496       std::__merge_sort_with_buffer(__first, __middle, __buffer, __comp);
03497       std::__merge_sort_with_buffer(__middle, __last, __buffer, __comp);
03498     }
03499       std::__merge_adaptive(__first, __middle, __last,
03500                 _Distance(__middle - __first),
03501                 _Distance(__last - __middle),
03502                 __buffer, __buffer_size,
03503                 __comp);
03504     }
03505 
03506   /// This is a helper function for the stable sorting routines.
03507   template<typename _RandomAccessIterator>
03508     void
03509     __inplace_stable_sort(_RandomAccessIterator __first,
03510               _RandomAccessIterator __last)
03511     {
03512       if (__last - __first < 15)
03513     {
03514       std::__insertion_sort(__first, __last);
03515       return;
03516     }
03517       _RandomAccessIterator __middle = __first + (__last - __first) / 2;
03518       std::__inplace_stable_sort(__first, __middle);
03519       std::__inplace_stable_sort(__middle, __last);
03520       std::__merge_without_buffer(__first, __middle, __last,
03521                   __middle - __first,
03522                   __last - __middle);
03523     }
03524 
03525   /// This is a helper function for the stable sorting routines.
03526   template<typename _RandomAccessIterator, typename _Compare>
03527     void
03528     __inplace_stable_sort(_RandomAccessIterator __first,
03529               _RandomAccessIterator __last, _Compare __comp)
03530     {
03531       if (__last - __first < 15)
03532     {
03533       std::__insertion_sort(__first, __last, __comp);
03534       return;
03535     }
03536       _RandomAccessIterator __middle = __first + (__last - __first) / 2;
03537       std::__inplace_stable_sort(__first, __middle, __comp);
03538       std::__inplace_stable_sort(__middle, __last, __comp);
03539       std::__merge_without_buffer(__first, __middle, __last,
03540                   __middle - __first,
03541                   __last - __middle,
03542                   __comp);
03543     }
03544 
03545   // stable_sort
03546 
03547   // Set algorithms: includes, set_union, set_intersection, set_difference,
03548   // set_symmetric_difference.  All of these algorithms have the precondition
03549   // that their input ranges are sorted and the postcondition that their output
03550   // ranges are sorted.
03551 
03552   /**
03553    *  @brief Determines whether all elements of a sequence exists in a range.
03554    *  @param  __first1  Start of search range.
03555    *  @param  __last1   End of search range.
03556    *  @param  __first2  Start of sequence
03557    *  @param  __last2   End of sequence.
03558    *  @return  True if each element in [__first2,__last2) is contained in order
03559    *  within [__first1,__last1).  False otherwise.
03560    *  @ingroup set_algorithms
03561    *
03562    *  This operation expects both [__first1,__last1) and
03563    *  [__first2,__last2) to be sorted.  Searches for the presence of
03564    *  each element in [__first2,__last2) within [__first1,__last1).
03565    *  The iterators over each range only move forward, so this is a
03566    *  linear algorithm.  If an element in [__first2,__last2) is not
03567    *  found before the search iterator reaches @p __last2, false is
03568    *  returned.
03569   */
03570   template<typename _InputIterator1, typename _InputIterator2>
03571     bool
03572     includes(_InputIterator1 __first1, _InputIterator1 __last1,
03573          _InputIterator2 __first2, _InputIterator2 __last2)
03574     {
03575       typedef typename iterator_traits<_InputIterator1>::value_type
03576     _ValueType1;
03577       typedef typename iterator_traits<_InputIterator2>::value_type
03578     _ValueType2;
03579 
03580       // concept requirements
03581       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
03582       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
03583       __glibcxx_function_requires(_LessThanOpConcept<_ValueType1, _ValueType2>)
03584       __glibcxx_function_requires(_LessThanOpConcept<_ValueType2, _ValueType1>)
03585       __glibcxx_requires_sorted_set(__first1, __last1, __first2);
03586       __glibcxx_requires_sorted_set(__first2, __last2, __first1);
03587 
03588       while (__first1 != __last1 && __first2 != __last2)
03589     if (*__first2 < *__first1)
03590       return false;
03591     else if(*__first1 < *__first2)
03592       ++__first1;
03593     else
03594       ++__first1, ++__first2;
03595 
03596       return __first2 == __last2;
03597     }
03598 
03599   /**
03600    *  @brief Determines whether all elements of a sequence exists in a range
03601    *  using comparison.
03602    *  @ingroup set_algorithms
03603    *  @param  __first1  Start of search range.
03604    *  @param  __last1   End of search range.
03605    *  @param  __first2  Start of sequence
03606    *  @param  __last2   End of sequence.
03607    *  @param  __comp    Comparison function to use.
03608    *  @return True if each element in [__first2,__last2) is contained
03609    *  in order within [__first1,__last1) according to comp.  False
03610    *  otherwise.  @ingroup set_algorithms
03611    *
03612    *  This operation expects both [__first1,__last1) and
03613    *  [__first2,__last2) to be sorted.  Searches for the presence of
03614    *  each element in [__first2,__last2) within [__first1,__last1),
03615    *  using comp to decide.  The iterators over each range only move
03616    *  forward, so this is a linear algorithm.  If an element in
03617    *  [__first2,__last2) is not found before the search iterator
03618    *  reaches @p __last2, false is returned.
03619   */
03620   template<typename _InputIterator1, typename _InputIterator2,
03621        typename _Compare>
03622     bool
03623     includes(_InputIterator1 __first1, _InputIterator1 __last1,
03624          _InputIterator2 __first2, _InputIterator2 __last2,
03625          _Compare __comp)
03626     {
03627       typedef typename iterator_traits<_InputIterator1>::value_type
03628     _ValueType1;
03629       typedef typename iterator_traits<_InputIterator2>::value_type
03630     _ValueType2;
03631 
03632       // concept requirements
03633       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
03634       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
03635       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
03636                   _ValueType1, _ValueType2>)
03637       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
03638                   _ValueType2, _ValueType1>)
03639       __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp);
03640       __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp);
03641 
03642       while (__first1 != __last1 && __first2 != __last2)
03643     if (__comp(*__first2, *__first1))
03644       return false;
03645     else if(__comp(*__first1, *__first2))
03646       ++__first1;
03647     else
03648       ++__first1, ++__first2;
03649 
03650       return __first2 == __last2;
03651     }
03652 
03653   // nth_element
03654   // merge
03655   // set_difference
03656   // set_intersection
03657   // set_union
03658   // stable_sort
03659   // set_symmetric_difference
03660   // min_element
03661   // max_element
03662 
03663   /**
03664    *  @brief  Permute range into the next @e dictionary ordering.
03665    *  @ingroup sorting_algorithms
03666    *  @param  __first  Start of range.
03667    *  @param  __last   End of range.
03668    *  @return  False if wrapped to first permutation, true otherwise.
03669    *
03670    *  Treats all permutations of the range as a set of @e dictionary sorted
03671    *  sequences.  Permutes the current sequence into the next one of this set.
03672    *  Returns true if there are more sequences to generate.  If the sequence
03673    *  is the largest of the set, the smallest is generated and false returned.
03674   */
03675   template<typename _BidirectionalIterator>
03676     bool
03677     next_permutation(_BidirectionalIterator __first,
03678              _BidirectionalIterator __last)
03679     {
03680       // concept requirements
03681       __glibcxx_function_requires(_BidirectionalIteratorConcept<
03682                   _BidirectionalIterator>)
03683       __glibcxx_function_requires(_LessThanComparableConcept<
03684         typename iterator_traits<_BidirectionalIterator>::value_type>)
03685       __glibcxx_requires_valid_range(__first, __last);
03686 
03687       if (__first == __last)
03688     return false;
03689       _BidirectionalIterator __i = __first;
03690       ++__i;
03691       if (__i == __last)
03692     return false;
03693       __i = __last;
03694       --__i;
03695 
03696       for(;;)
03697     {
03698       _BidirectionalIterator __ii = __i;
03699       --__i;
03700       if (*__i < *__ii)
03701         {
03702           _BidirectionalIterator __j = __last;
03703           while (!(*__i < *--__j))
03704         {}
03705           std::iter_swap(__i, __j);
03706           std::reverse(__ii, __last);
03707           return true;
03708         }
03709       if (__i == __first)
03710         {
03711           std::reverse(__first, __last);
03712           return false;
03713         }
03714     }
03715     }
03716 
03717   /**
03718    *  @brief  Permute range into the next @e dictionary ordering using
03719    *          comparison functor.
03720    *  @ingroup sorting_algorithms
03721    *  @param  __first  Start of range.
03722    *  @param  __last   End of range.
03723    *  @param  __comp   A comparison functor.
03724    *  @return  False if wrapped to first permutation, true otherwise.
03725    *
03726    *  Treats all permutations of the range [__first,__last) as a set of
03727    *  @e dictionary sorted sequences ordered by @p __comp.  Permutes the current
03728    *  sequence into the next one of this set.  Returns true if there are more
03729    *  sequences to generate.  If the sequence is the largest of the set, the
03730    *  smallest is generated and false returned.
03731   */
03732   template<typename _BidirectionalIterator, typename _Compare>
03733     bool
03734     next_permutation(_BidirectionalIterator __first,
03735              _BidirectionalIterator __last, _Compare __comp)
03736     {
03737       // concept requirements
03738       __glibcxx_function_requires(_BidirectionalIteratorConcept<
03739                   _BidirectionalIterator>)
03740       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
03741         typename iterator_traits<_BidirectionalIterator>::value_type,
03742         typename iterator_traits<_BidirectionalIterator>::value_type>)
03743       __glibcxx_requires_valid_range(__first, __last);
03744 
03745       if (__first == __last)
03746     return false;
03747       _BidirectionalIterator __i = __first;
03748       ++__i;
03749       if (__i == __last)
03750     return false;
03751       __i = __last;
03752       --__i;
03753 
03754       for(;;)
03755     {
03756       _BidirectionalIterator __ii = __i;
03757       --__i;
03758       if (__comp(*__i, *__ii))
03759         {
03760           _BidirectionalIterator __j = __last;
03761           while (!bool(__comp(*__i, *--__j)))
03762         {}
03763           std::iter_swap(__i, __j);
03764           std::reverse(__ii, __last);
03765           return true;
03766         }
03767       if (__i == __first)
03768         {
03769           std::reverse(__first, __last);
03770           return false;
03771         }
03772     }
03773     }
03774 
03775   /**
03776    *  @brief  Permute range into the previous @e dictionary ordering.
03777    *  @ingroup sorting_algorithms
03778    *  @param  __first  Start of range.
03779    *  @param  __last   End of range.
03780    *  @return  False if wrapped to last permutation, true otherwise.
03781    *
03782    *  Treats all permutations of the range as a set of @e dictionary sorted
03783    *  sequences.  Permutes the current sequence into the previous one of this
03784    *  set.  Returns true if there are more sequences to generate.  If the
03785    *  sequence is the smallest of the set, the largest is generated and false
03786    *  returned.
03787   */
03788   template<typename _BidirectionalIterator>
03789     bool
03790     prev_permutation(_BidirectionalIterator __first,
03791              _BidirectionalIterator __last)
03792     {
03793       // concept requirements
03794       __glibcxx_function_requires(_BidirectionalIteratorConcept<
03795                   _BidirectionalIterator>)
03796       __glibcxx_function_requires(_LessThanComparableConcept<
03797         typename iterator_traits<_BidirectionalIterator>::value_type>)
03798       __glibcxx_requires_valid_range(__first, __last);
03799 
03800       if (__first == __last)
03801     return false;
03802       _BidirectionalIterator __i = __first;
03803       ++__i;
03804       if (__i == __last)
03805     return false;
03806       __i = __last;
03807       --__i;
03808 
03809       for(;;)
03810     {
03811       _BidirectionalIterator __ii = __i;
03812       --__i;
03813       if (*__ii < *__i)
03814         {
03815           _BidirectionalIterator __j = __last;
03816           while (!(*--__j < *__i))
03817         {}
03818           std::iter_swap(__i, __j);
03819           std::reverse(__ii, __last);
03820           return true;
03821         }
03822       if (__i == __first)
03823         {
03824           std::reverse(__first, __last);
03825           return false;
03826         }
03827     }
03828     }
03829 
03830   /**
03831    *  @brief  Permute range into the previous @e dictionary ordering using
03832    *          comparison functor.
03833    *  @ingroup sorting_algorithms
03834    *  @param  __first  Start of range.
03835    *  @param  __last   End of range.
03836    *  @param  __comp   A comparison functor.
03837    *  @return  False if wrapped to last permutation, true otherwise.
03838    *
03839    *  Treats all permutations of the range [__first,__last) as a set of
03840    *  @e dictionary sorted sequences ordered by @p __comp.  Permutes the current
03841    *  sequence into the previous one of this set.  Returns true if there are
03842    *  more sequences to generate.  If the sequence is the smallest of the set,
03843    *  the largest is generated and false returned.
03844   */
03845   template<typename _BidirectionalIterator, typename _Compare>
03846     bool
03847     prev_permutation(_BidirectionalIterator __first,
03848              _BidirectionalIterator __last, _Compare __comp)
03849     {
03850       // concept requirements
03851       __glibcxx_function_requires(_BidirectionalIteratorConcept<
03852                   _BidirectionalIterator>)
03853       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
03854         typename iterator_traits<_BidirectionalIterator>::value_type,
03855         typename iterator_traits<_BidirectionalIterator>::value_type>)
03856       __glibcxx_requires_valid_range(__first, __last);
03857 
03858       if (__first == __last)
03859     return false;
03860       _BidirectionalIterator __i = __first;
03861       ++__i;
03862       if (__i == __last)
03863     return false;
03864       __i = __last;
03865       --__i;
03866 
03867       for(;;)
03868     {
03869       _BidirectionalIterator __ii = __i;
03870       --__i;
03871       if (__comp(*__ii, *__i))
03872         {
03873           _BidirectionalIterator __j = __last;
03874           while (!bool(__comp(*--__j, *__i)))
03875         {}
03876           std::iter_swap(__i, __j);
03877           std::reverse(__ii, __last);
03878           return true;
03879         }
03880       if (__i == __first)
03881         {
03882           std::reverse(__first, __last);
03883           return false;
03884         }
03885     }
03886     }
03887 
03888   // replace
03889   // replace_if
03890 
03891   /**
03892    *  @brief Copy a sequence, replacing each element of one value with another
03893    *         value.
03894    *  @param  __first      An input iterator.
03895    *  @param  __last       An input iterator.
03896    *  @param  __result     An output iterator.
03897    *  @param  __old_value  The value to be replaced.
03898    *  @param  __new_value  The replacement value.
03899    *  @return   The end of the output sequence, @p result+(last-first).
03900    *
03901    *  Copies each element in the input range @p [__first,__last) to the
03902    *  output range @p [__result,__result+(__last-__first)) replacing elements
03903    *  equal to @p __old_value with @p __new_value.
03904   */
03905   template<typename _InputIterator, typename _OutputIterator, typename _Tp>
03906     _OutputIterator
03907     replace_copy(_InputIterator __first, _InputIterator __last,
03908          _OutputIterator __result,
03909          const _Tp& __old_value, const _Tp& __new_value)
03910     {
03911       // concept requirements
03912       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
03913       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
03914         typename iterator_traits<_InputIterator>::value_type>)
03915       __glibcxx_function_requires(_EqualOpConcept<
03916         typename iterator_traits<_InputIterator>::value_type, _Tp>)
03917       __glibcxx_requires_valid_range(__first, __last);
03918 
03919       for (; __first != __last; ++__first, ++__result)
03920     if (*__first == __old_value)
03921       *__result = __new_value;
03922     else
03923       *__result = *__first;
03924       return __result;
03925     }
03926 
03927   /**
03928    *  @brief Copy a sequence, replacing each value for which a predicate
03929    *         returns true with another value.
03930    *  @ingroup mutating_algorithms
03931    *  @param  __first      An input iterator.
03932    *  @param  __last       An input iterator.
03933    *  @param  __result     An output iterator.
03934    *  @param  __pred       A predicate.
03935    *  @param  __new_value  The replacement value.
03936    *  @return   The end of the output sequence, @p __result+(__last-__first).
03937    *
03938    *  Copies each element in the range @p [__first,__last) to the range
03939    *  @p [__result,__result+(__last-__first)) replacing elements for which
03940    *  @p __pred returns true with @p __new_value.
03941   */
03942   template<typename _InputIterator, typename _OutputIterator,
03943        typename _Predicate, typename _Tp>
03944     _OutputIterator
03945     replace_copy_if(_InputIterator __first, _InputIterator __last,
03946             _OutputIterator __result,
03947             _Predicate __pred, const _Tp& __new_value)
03948     {
03949       // concept requirements
03950       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
03951       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
03952         typename iterator_traits<_InputIterator>::value_type>)
03953       __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
03954         typename iterator_traits<_InputIterator>::value_type>)
03955       __glibcxx_requires_valid_range(__first, __last);
03956 
03957       for (; __first != __last; ++__first, ++__result)
03958     if (__pred(*__first))
03959       *__result = __new_value;
03960     else
03961       *__result = *__first;
03962       return __result;
03963     }
03964 
03965 #if __cplusplus >= 201103L
03966   /**
03967    *  @brief  Determines whether the elements of a sequence are sorted.
03968    *  @ingroup sorting_algorithms
03969    *  @param  __first   An iterator.
03970    *  @param  __last    Another iterator.
03971    *  @return  True if the elements are sorted, false otherwise.
03972   */
03973   template<typename _ForwardIterator>
03974     inline bool
03975     is_sorted(_ForwardIterator __first, _ForwardIterator __last)
03976     { return std::is_sorted_until(__first, __last) == __last; }
03977 
03978   /**
03979    *  @brief  Determines whether the elements of a sequence are sorted
03980    *          according to a comparison functor.
03981    *  @ingroup sorting_algorithms
03982    *  @param  __first   An iterator.
03983    *  @param  __last    Another iterator.
03984    *  @param  __comp    A comparison functor.
03985    *  @return  True if the elements are sorted, false otherwise.
03986   */
03987   template<typename _ForwardIterator, typename _Compare>
03988     inline bool
03989     is_sorted(_ForwardIterator __first, _ForwardIterator __last,
03990           _Compare __comp)
03991     { return std::is_sorted_until(__first, __last, __comp) == __last; }
03992 
03993   /**
03994    *  @brief  Determines the end of a sorted sequence.
03995    *  @ingroup sorting_algorithms
03996    *  @param  __first   An iterator.
03997    *  @param  __last    Another iterator.
03998    *  @return  An iterator pointing to the last iterator i in [__first, __last)
03999    *           for which the range [__first, i) is sorted.
04000   */
04001   template<typename _ForwardIterator>
04002     _ForwardIterator
04003     is_sorted_until(_ForwardIterator __first, _ForwardIterator __last)
04004     {
04005       // concept requirements
04006       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
04007       __glibcxx_function_requires(_LessThanComparableConcept<
04008         typename iterator_traits<_ForwardIterator>::value_type>)
04009       __glibcxx_requires_valid_range(__first, __last);
04010 
04011       if (__first == __last)
04012     return __last;
04013 
04014       _ForwardIterator __next = __first;
04015       for (++__next; __next != __last; __first = __next, ++__next)
04016     if (*__next < *__first)
04017       return __next;
04018       return __next;
04019     }
04020 
04021   /**
04022    *  @brief  Determines the end of a sorted sequence using comparison functor.
04023    *  @ingroup sorting_algorithms
04024    *  @param  __first   An iterator.
04025    *  @param  __last    Another iterator.
04026    *  @param  __comp    A comparison functor.
04027    *  @return  An iterator pointing to the last iterator i in [__first, __last)
04028    *           for which the range [__first, i) is sorted.
04029   */
04030   template<typename _ForwardIterator, typename _Compare>
04031     _ForwardIterator
04032     is_sorted_until(_ForwardIterator __first, _ForwardIterator __last,
04033             _Compare __comp)
04034     {
04035       // concept requirements
04036       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
04037       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
04038         typename iterator_traits<_ForwardIterator>::value_type,
04039         typename iterator_traits<_ForwardIterator>::value_type>)
04040       __glibcxx_requires_valid_range(__first, __last);
04041 
04042       if (__first == __last)
04043     return __last;
04044 
04045       _ForwardIterator __next = __first;
04046       for (++__next; __next != __last; __first = __next, ++__next)
04047     if (__comp(*__next, *__first))
04048       return __next;
04049       return __next;
04050     }
04051 
04052   /**
04053    *  @brief  Determines min and max at once as an ordered pair.
04054    *  @ingroup sorting_algorithms
04055    *  @param  __a  A thing of arbitrary type.
04056    *  @param  __b  Another thing of arbitrary type.
04057    *  @return A pair(__b, __a) if __b is smaller than __a, pair(__a,
04058    *  __b) otherwise.
04059   */
04060   template<typename _Tp>
04061     inline pair<const _Tp&, const _Tp&>
04062     minmax(const _Tp& __a, const _Tp& __b)
04063     {
04064       // concept requirements
04065       __glibcxx_function_requires(_LessThanComparableConcept<_Tp>)
04066 
04067       return __b < __a ? pair<const _Tp&, const _Tp&>(__b, __a)
04068                    : pair<const _Tp&, const _Tp&>(__a, __b);
04069     }
04070 
04071   /**
04072    *  @brief  Determines min and max at once as an ordered pair.
04073    *  @ingroup sorting_algorithms
04074    *  @param  __a  A thing of arbitrary type.
04075    *  @param  __b  Another thing of arbitrary type.
04076    *  @param  __comp  A @link comparison_functors comparison functor @endlink.
04077    *  @return A pair(__b, __a) if __b is smaller than __a, pair(__a,
04078    *  __b) otherwise.
04079   */
04080   template<typename _Tp, typename _Compare>
04081     inline pair<const _Tp&, const _Tp&>
04082     minmax(const _Tp& __a, const _Tp& __b, _Compare __comp)
04083     {
04084       return __comp(__b, __a) ? pair<const _Tp&, const _Tp&>(__b, __a)
04085                           : pair<const _Tp&, const _Tp&>(__a, __b);
04086     }
04087 
04088   /**
04089    *  @brief  Return a pair of iterators pointing to the minimum and maximum
04090    *          elements in a range.
04091    *  @ingroup sorting_algorithms
04092    *  @param  __first  Start of range.
04093    *  @param  __last   End of range.
04094    *  @return  make_pair(m, M), where m is the first iterator i in 
04095    *           [__first, __last) such that no other element in the range is
04096    *           smaller, and where M is the last iterator i in [__first, __last)
04097    *           such that no other element in the range is larger.
04098   */
04099   template<typename _ForwardIterator>
04100     pair<_ForwardIterator, _ForwardIterator>
04101     minmax_element(_ForwardIterator __first, _ForwardIterator __last)
04102     {
04103       // concept requirements
04104       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
04105       __glibcxx_function_requires(_LessThanComparableConcept<
04106         typename iterator_traits<_ForwardIterator>::value_type>)
04107       __glibcxx_requires_valid_range(__first, __last);
04108 
04109       _ForwardIterator __next = __first;
04110       if (__first == __last
04111       || ++__next == __last)
04112     return std::make_pair(__first, __first);
04113 
04114       _ForwardIterator __min, __max;
04115       if (*__next < *__first)
04116     {
04117       __min = __next;
04118       __max = __first;
04119     }
04120       else
04121     {
04122       __min = __first;
04123       __max = __next;
04124     }
04125 
04126       __first = __next;
04127       ++__first;
04128 
04129       while (__first != __last)
04130     {
04131       __next = __first;
04132       if (++__next == __last)
04133         {
04134           if (*__first < *__min)
04135         __min = __first;
04136           else if (!(*__first < *__max))
04137         __max = __first;
04138           break;
04139         }
04140 
04141       if (*__next < *__first)
04142         {
04143           if (*__next < *__min)
04144         __min = __next;
04145           if (!(*__first < *__max))
04146         __max = __first;
04147         }
04148       else
04149         {
04150           if (*__first < *__min)
04151         __min = __first;
04152           if (!(*__next < *__max))
04153         __max = __next;
04154         }
04155 
04156       __first = __next;
04157       ++__first;
04158     }
04159 
04160       return std::make_pair(__min, __max);
04161     }
04162 
04163   /**
04164    *  @brief  Return a pair of iterators pointing to the minimum and maximum
04165    *          elements in a range.
04166    *  @ingroup sorting_algorithms
04167    *  @param  __first  Start of range.
04168    *  @param  __last   End of range.
04169    *  @param  __comp   Comparison functor.
04170    *  @return  make_pair(m, M), where m is the first iterator i in 
04171    *           [__first, __last) such that no other element in the range is
04172    *           smaller, and where M is the last iterator i in [__first, __last)
04173    *           such that no other element in the range is larger.
04174   */
04175   template<typename _ForwardIterator, typename _Compare>
04176     pair<_ForwardIterator, _ForwardIterator>
04177     minmax_element(_ForwardIterator __first, _ForwardIterator __last,
04178            _Compare __comp)
04179     {
04180       // concept requirements
04181       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
04182       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
04183         typename iterator_traits<_ForwardIterator>::value_type,
04184         typename iterator_traits<_ForwardIterator>::value_type>)
04185       __glibcxx_requires_valid_range(__first, __last);
04186 
04187       _ForwardIterator __next = __first;
04188       if (__first == __last
04189       || ++__next == __last)
04190     return std::make_pair(__first, __first);
04191 
04192       _ForwardIterator __min, __max;
04193       if (__comp(*__next, *__first))
04194     {
04195       __min = __next;
04196       __max = __first;
04197     }
04198       else
04199     {
04200       __min = __first;
04201       __max = __next;
04202     }
04203 
04204       __first = __next;
04205       ++__first;
04206 
04207       while (__first != __last)
04208     {
04209       __next = __first;
04210       if (++__next == __last)
04211         {
04212           if (__comp(*__first, *__min))
04213         __min = __first;
04214           else if (!__comp(*__first, *__max))
04215         __max = __first;
04216           break;
04217         }
04218 
04219       if (__comp(*__next, *__first))
04220         {
04221           if (__comp(*__next, *__min))
04222         __min = __next;
04223           if (!__comp(*__first, *__max))
04224         __max = __first;
04225         }
04226       else
04227         {
04228           if (__comp(*__first, *__min))
04229         __min = __first;
04230           if (!__comp(*__next, *__max))
04231         __max = __next;
04232         }
04233 
04234       __first = __next;
04235       ++__first;
04236     }
04237 
04238       return std::make_pair(__min, __max);
04239     }
04240 
04241   // N2722 + DR 915.
04242   template<typename _Tp>
04243     inline _Tp
04244     min(initializer_list<_Tp> __l)
04245     { return *std::min_element(__l.begin(), __l.end()); }
04246 
04247   template<typename _Tp, typename _Compare>
04248     inline _Tp
04249     min(initializer_list<_Tp> __l, _Compare __comp)
04250     { return *std::min_element(__l.begin(), __l.end(), __comp); }
04251 
04252   template<typename _Tp>
04253     inline _Tp
04254     max(initializer_list<_Tp> __l)
04255     { return *std::max_element(__l.begin(), __l.end()); }
04256 
04257   template<typename _Tp, typename _Compare>
04258     inline _Tp
04259     max(initializer_list<_Tp> __l, _Compare __comp)
04260     { return *std::max_element(__l.begin(), __l.end(), __comp); }
04261 
04262   template<typename _Tp>
04263     inline pair<_Tp, _Tp>
04264     minmax(initializer_list<_Tp> __l)
04265     {
04266       pair<const _Tp*, const _Tp*> __p =
04267     std::minmax_element(__l.begin(), __l.end());
04268       return std::make_pair(*__p.first, *__p.second);
04269     }
04270 
04271   template<typename _Tp, typename _Compare>
04272     inline pair<_Tp, _Tp>
04273     minmax(initializer_list<_Tp> __l, _Compare __comp)
04274     {
04275       pair<const _Tp*, const _Tp*> __p =
04276     std::minmax_element(__l.begin(), __l.end(), __comp);
04277       return std::make_pair(*__p.first, *__p.second);
04278     }
04279 
04280   /**
04281    *  @brief  Checks whether a permutaion of the second sequence is equal
04282    *          to the first sequence.
04283    *  @ingroup non_mutating_algorithms
04284    *  @param  __first1  Start of first range.
04285    *  @param  __last1   End of first range.
04286    *  @param  __first2  Start of second range.
04287    *  @return true if there exists a permutation of the elements in the range
04288    *          [__first2, __first2 + (__last1 - __first1)), beginning with 
04289    *          ForwardIterator2 begin, such that equal(__first1, __last1, begin)
04290    *          returns true; otherwise, returns false.
04291   */
04292   template<typename _ForwardIterator1, typename _ForwardIterator2>
04293     bool
04294     is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
04295            _ForwardIterator2 __first2)
04296     {
04297       // Efficiently compare identical prefixes:  O(N) if sequences
04298       // have the same elements in the same order.
04299       for (; __first1 != __last1; ++__first1, ++__first2)
04300     if (!(*__first1 == *__first2))
04301       break;
04302 
04303       if (__first1 == __last1)
04304     return true;
04305 
04306       // Establish __last2 assuming equal ranges by iterating over the
04307       // rest of the list.
04308       _ForwardIterator2 __last2 = __first2;
04309       std::advance(__last2, std::distance(__first1, __last1));
04310       for (_ForwardIterator1 __scan = __first1; __scan != __last1; ++__scan)
04311     {
04312       if (__scan != _GLIBCXX_STD_A::find(__first1, __scan, *__scan))
04313         continue; // We've seen this one before.
04314 
04315       auto __matches = std::count(__first2, __last2, *__scan);
04316       if (0 == __matches
04317           || std::count(__scan, __last1, *__scan) != __matches)
04318         return false;
04319     }
04320       return true;
04321     }
04322 
04323   /**
04324    *  @brief  Checks whether a permutation of the second sequence is equal
04325    *          to the first sequence.
04326    *  @ingroup non_mutating_algorithms
04327    *  @param  __first1  Start of first range.
04328    *  @param  __last1   End of first range.
04329    *  @param  __first2  Start of second range.
04330    *  @param  __pred    A binary predicate.
04331    *  @return true if there exists a permutation of the elements in
04332    *          the range [__first2, __first2 + (__last1 - __first1)),
04333    *          beginning with ForwardIterator2 begin, such that
04334    *          equal(__first1, __last1, __begin, __pred) returns true;
04335    *          otherwise, returns false.
04336   */
04337   template<typename _ForwardIterator1, typename _ForwardIterator2,
04338        typename _BinaryPredicate>
04339     bool
04340     is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
04341            _ForwardIterator2 __first2, _BinaryPredicate __pred)
04342     {
04343       // Efficiently compare identical prefixes:  O(N) if sequences
04344       // have the same elements in the same order.
04345       for (; __first1 != __last1; ++__first1, ++__first2)
04346     if (!bool(__pred(*__first1, *__first2)))
04347       break;
04348 
04349       if (__first1 == __last1)
04350     return true;
04351 
04352       // Establish __last2 assuming equal ranges by iterating over the
04353       // rest of the list.
04354       _ForwardIterator2 __last2 = __first2;
04355       std::advance(__last2, std::distance(__first1, __last1));
04356       for (_ForwardIterator1 __scan = __first1; __scan != __last1; ++__scan)
04357     {
04358       using std::placeholders::_1;
04359 
04360       if (__scan != _GLIBCXX_STD_A::find_if(__first1, __scan,
04361                         std::bind(__pred, _1, *__scan)))
04362         continue; // We've seen this one before.
04363       
04364       auto __matches = std::count_if(__first2, __last2,
04365                      std::bind(__pred, _1, *__scan));
04366       if (0 == __matches
04367           || std::count_if(__scan, __last1,
04368                    std::bind(__pred, _1, *__scan)) != __matches)
04369         return false;
04370     }
04371       return true;
04372     }
04373 
04374 #ifdef _GLIBCXX_USE_C99_STDINT_TR1
04375   /**
04376    *  @brief Shuffle the elements of a sequence using a uniform random
04377    *         number generator.
04378    *  @ingroup mutating_algorithms
04379    *  @param  __first   A forward iterator.
04380    *  @param  __last    A forward iterator.
04381    *  @param  __g       A UniformRandomNumberGenerator (26.5.1.3).
04382    *  @return  Nothing.
04383    *
04384    *  Reorders the elements in the range @p [__first,__last) using @p __g to
04385    *  provide random numbers.
04386   */
04387   template<typename _RandomAccessIterator,
04388        typename _UniformRandomNumberGenerator>
04389     void
04390     shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last,
04391         _UniformRandomNumberGenerator&& __g)
04392     {
04393       // concept requirements
04394       __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
04395         _RandomAccessIterator>)
04396       __glibcxx_requires_valid_range(__first, __last);
04397 
04398       if (__first == __last)
04399     return;
04400 
04401       typedef typename iterator_traits<_RandomAccessIterator>::difference_type
04402     _DistanceType;
04403 
04404       typedef typename std::make_unsigned<_DistanceType>::type __ud_type;
04405       typedef typename std::uniform_int_distribution<__ud_type> __distr_type;
04406       typedef typename __distr_type::param_type __p_type;
04407       __distr_type __d;
04408 
04409       for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i)
04410     std::iter_swap(__i, __first + __d(__g, __p_type(0, __i - __first)));
04411     }
04412 #endif
04413 
04414 #endif // C++11
04415 
04416 _GLIBCXX_END_NAMESPACE_VERSION
04417 
04418 _GLIBCXX_BEGIN_NAMESPACE_ALGO
04419 
04420   /**
04421    *  @brief Apply a function to every element of a sequence.
04422    *  @ingroup non_mutating_algorithms
04423    *  @param  __first  An input iterator.
04424    *  @param  __last   An input iterator.
04425    *  @param  __f      A unary function object.
04426    *  @return   @p __f (std::move(@p __f) in C++0x).
04427    *
04428    *  Applies the function object @p __f to each element in the range
04429    *  @p [first,last).  @p __f must not modify the order of the sequence.
04430    *  If @p __f has a return value it is ignored.
04431   */
04432   template<typename _InputIterator, typename _Function>
04433     _Function
04434     for_each(_InputIterator __first, _InputIterator __last, _Function __f)
04435     {
04436       // concept requirements
04437       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
04438       __glibcxx_requires_valid_range(__first, __last);
04439       for (; __first != __last; ++__first)
04440     __f(*__first);
04441       return _GLIBCXX_MOVE(__f);
04442     }
04443 
04444   /**
04445    *  @brief Find the first occurrence of a value in a sequence.
04446    *  @ingroup non_mutating_algorithms
04447    *  @param  __first  An input iterator.
04448    *  @param  __last   An input iterator.
04449    *  @param  __val    The value to find.
04450    *  @return   The first iterator @c i in the range @p [__first,__last)
04451    *  such that @c *i == @p __val, or @p __last if no such iterator exists.
04452   */
04453   template<typename _InputIterator, typename _Tp>
04454     inline _InputIterator
04455     find(_InputIterator __first, _InputIterator __last,
04456      const _Tp& __val)
04457     {
04458       // concept requirements
04459       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
04460       __glibcxx_function_requires(_EqualOpConcept<
04461         typename iterator_traits<_InputIterator>::value_type, _Tp>)
04462       __glibcxx_requires_valid_range(__first, __last);
04463       return std::__find(__first, __last, __val,
04464                  std::__iterator_category(__first));
04465     }
04466 
04467   /**
04468    *  @brief Find the first element in a sequence for which a
04469    *         predicate is true.
04470    *  @ingroup non_mutating_algorithms
04471    *  @param  __first  An input iterator.
04472    *  @param  __last   An input iterator.
04473    *  @param  __pred   A predicate.
04474    *  @return   The first iterator @c i in the range @p [__first,__last)
04475    *  such that @p __pred(*i) is true, or @p __last if no such iterator exists.
04476   */
04477   template<typename _InputIterator, typename _Predicate>
04478     inline _InputIterator
04479     find_if(_InputIterator __first, _InputIterator __last,
04480         _Predicate __pred)
04481     {
04482       // concept requirements
04483       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
04484       __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
04485           typename iterator_traits<_InputIterator>::value_type>)
04486       __glibcxx_requires_valid_range(__first, __last);
04487       return std::__find_if(__first, __last, __pred,
04488                 std::__iterator_category(__first));
04489     }
04490 
04491   /**
04492    *  @brief  Find element from a set in a sequence.
04493    *  @ingroup non_mutating_algorithms
04494    *  @param  __first1  Start of range to search.
04495    *  @param  __last1   End of range to search.
04496    *  @param  __first2  Start of match candidates.
04497    *  @param  __last2   End of match candidates.
04498    *  @return   The first iterator @c i in the range
04499    *  @p [__first1,__last1) such that @c *i == @p *(i2) such that i2 is an
04500    *  iterator in [__first2,__last2), or @p __last1 if no such iterator exists.
04501    *
04502    *  Searches the range @p [__first1,__last1) for an element that is
04503    *  equal to some element in the range [__first2,__last2).  If
04504    *  found, returns an iterator in the range [__first1,__last1),
04505    *  otherwise returns @p __last1.
04506   */
04507   template<typename _InputIterator, typename _ForwardIterator>
04508     _InputIterator
04509     find_first_of(_InputIterator __first1, _InputIterator __last1,
04510           _ForwardIterator __first2, _ForwardIterator __last2)
04511     {
04512       // concept requirements
04513       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
04514       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
04515       __glibcxx_function_requires(_EqualOpConcept<
04516         typename iterator_traits<_InputIterator>::value_type,
04517         typename iterator_traits<_ForwardIterator>::value_type>)
04518       __glibcxx_requires_valid_range(__first1, __last1);
04519       __glibcxx_requires_valid_range(__first2, __last2);
04520 
04521       for (; __first1 != __last1; ++__first1)
04522     for (_ForwardIterator __iter = __first2; __iter != __last2; ++__iter)
04523       if (*__first1 == *__iter)
04524         return __first1;
04525       return __last1;
04526     }
04527 
04528   /**
04529    *  @brief  Find element from a set in a sequence using a predicate.
04530    *  @ingroup non_mutating_algorithms
04531    *  @param  __first1  Start of range to search.
04532    *  @param  __last1   End of range to search.
04533    *  @param  __first2  Start of match candidates.
04534    *  @param  __last2   End of match candidates.
04535    *  @param  __comp    Predicate to use.
04536    *  @return   The first iterator @c i in the range
04537    *  @p [__first1,__last1) such that @c comp(*i, @p *(i2)) is true
04538    *  and i2 is an iterator in [__first2,__last2), or @p __last1 if no
04539    *  such iterator exists.
04540    *
04541 
04542    *  Searches the range @p [__first1,__last1) for an element that is
04543    *  equal to some element in the range [__first2,__last2).  If
04544    *  found, returns an iterator in the range [__first1,__last1),
04545    *  otherwise returns @p __last1.
04546   */
04547   template<typename _InputIterator, typename _ForwardIterator,
04548        typename _BinaryPredicate>
04549     _InputIterator
04550     find_first_of(_InputIterator __first1, _InputIterator __last1,
04551           _ForwardIterator __first2, _ForwardIterator __last2,
04552           _BinaryPredicate __comp)
04553     {
04554       // concept requirements
04555       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
04556       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
04557       __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
04558         typename iterator_traits<_InputIterator>::value_type,
04559         typename iterator_traits<_ForwardIterator>::value_type>)
04560       __glibcxx_requires_valid_range(__first1, __last1);
04561       __glibcxx_requires_valid_range(__first2, __last2);
04562 
04563       for (; __first1 != __last1; ++__first1)
04564     for (_ForwardIterator __iter = __first2; __iter != __last2; ++__iter)
04565       if (__comp(*__first1, *__iter))
04566         return __first1;
04567       return __last1;
04568     }
04569 
04570   /**
04571    *  @brief Find two adjacent values in a sequence that are equal.
04572    *  @ingroup non_mutating_algorithms
04573    *  @param  __first  A forward iterator.
04574    *  @param  __last   A forward iterator.
04575    *  @return   The first iterator @c i such that @c i and @c i+1 are both
04576    *  valid iterators in @p [__first,__last) and such that @c *i == @c *(i+1),
04577    *  or @p __last if no such iterator exists.
04578   */
04579   template<typename _ForwardIterator>
04580     _ForwardIterator
04581     adjacent_find(_ForwardIterator __first, _ForwardIterator __last)
04582     {
04583       // concept requirements
04584       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
04585       __glibcxx_function_requires(_EqualityComparableConcept<
04586         typename iterator_traits<_ForwardIterator>::value_type>)
04587       __glibcxx_requires_valid_range(__first, __last);
04588       if (__first == __last)
04589     return __last;
04590       _ForwardIterator __next = __first;
04591       while(++__next != __last)
04592     {
04593       if (*__first == *__next)
04594         return __first;
04595       __first = __next;
04596     }
04597       return __last;
04598     }
04599 
04600   /**
04601    *  @brief Find two adjacent values in a sequence using a predicate.
04602    *  @ingroup non_mutating_algorithms
04603    *  @param  __first         A forward iterator.
04604    *  @param  __last          A forward iterator.
04605    *  @param  __binary_pred   A binary predicate.
04606    *  @return   The first iterator @c i such that @c i and @c i+1 are both
04607    *  valid iterators in @p [__first,__last) and such that
04608    *  @p __binary_pred(*i,*(i+1)) is true, or @p __last if no such iterator
04609    *  exists.
04610   */
04611   template<typename _ForwardIterator, typename _BinaryPredicate>
04612     _ForwardIterator
04613     adjacent_find(_ForwardIterator __first, _ForwardIterator __last,
04614           _BinaryPredicate __binary_pred)
04615     {
04616       // concept requirements
04617       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
04618       __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
04619         typename iterator_traits<_ForwardIterator>::value_type,
04620         typename iterator_traits<_ForwardIterator>::value_type>)
04621       __glibcxx_requires_valid_range(__first, __last);
04622       if (__first == __last)
04623     return __last;
04624       _ForwardIterator __next = __first;
04625       while(++__next != __last)
04626     {
04627       if (__binary_pred(*__first, *__next))
04628         return __first;
04629       __first = __next;
04630     }
04631       return __last;
04632     }
04633 
04634   /**
04635    *  @brief Count the number of copies of a value in a sequence.
04636    *  @ingroup non_mutating_algorithms
04637    *  @param  __first  An input iterator.
04638    *  @param  __last   An input iterator.
04639    *  @param  __value  The value to be counted.
04640    *  @return   The number of iterators @c i in the range @p [__first,__last)
04641    *  for which @c *i == @p __value
04642   */
04643   template<typename _InputIterator, typename _Tp>
04644     typename iterator_traits<_InputIterator>::difference_type
04645     count(_InputIterator __first, _InputIterator __last, const _Tp& __value)
04646     {
04647       // concept requirements
04648       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
04649       __glibcxx_function_requires(_EqualOpConcept<
04650     typename iterator_traits<_InputIterator>::value_type, _Tp>)
04651       __glibcxx_requires_valid_range(__first, __last);
04652       typename iterator_traits<_InputIterator>::difference_type __n = 0;
04653       for (; __first != __last; ++__first)
04654     if (*__first == __value)
04655       ++__n;
04656       return __n;
04657     }
04658 
04659   /**
04660    *  @brief Count the elements of a sequence for which a predicate is true.
04661    *  @ingroup non_mutating_algorithms
04662    *  @param  __first  An input iterator.
04663    *  @param  __last   An input iterator.
04664    *  @param  __pred   A predicate.
04665    *  @return   The number of iterators @c i in the range @p [__first,__last)
04666    *  for which @p __pred(*i) is true.
04667   */
04668   template<typename _InputIterator, typename _Predicate>
04669     typename iterator_traits<_InputIterator>::difference_type
04670     count_if(_InputIterator __first, _InputIterator __last, _Predicate __pred)
04671     {
04672       // concept requirements
04673       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
04674       __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
04675         typename iterator_traits<_InputIterator>::value_type>)
04676       __glibcxx_requires_valid_range(__first, __last);
04677       typename iterator_traits<_InputIterator>::difference_type __n = 0;
04678       for (; __first != __last; ++__first)
04679     if (__pred(*__first))
04680       ++__n;
04681       return __n;
04682     }
04683 
04684   /**
04685    *  @brief Search a sequence for a matching sub-sequence.
04686    *  @ingroup non_mutating_algorithms
04687    *  @param  __first1  A forward iterator.
04688    *  @param  __last1   A forward iterator.
04689    *  @param  __first2  A forward iterator.
04690    *  @param  __last2   A forward iterator.
04691    *  @return The first iterator @c i in the range @p
04692    *  [__first1,__last1-(__last2-__first2)) such that @c *(i+N) == @p
04693    *  *(__first2+N) for each @c N in the range @p
04694    *  [0,__last2-__first2), or @p __last1 if no such iterator exists.
04695    *
04696    *  Searches the range @p [__first1,__last1) for a sub-sequence that
04697    *  compares equal value-by-value with the sequence given by @p
04698    *  [__first2,__last2) and returns an iterator to the first element
04699    *  of the sub-sequence, or @p __last1 if the sub-sequence is not
04700    *  found.
04701    *
04702    *  Because the sub-sequence must lie completely within the range @p
04703    *  [__first1,__last1) it must start at a position less than @p
04704    *  __last1-(__last2-__first2) where @p __last2-__first2 is the
04705    *  length of the sub-sequence.
04706    *
04707    *  This means that the returned iterator @c i will be in the range
04708    *  @p [__first1,__last1-(__last2-__first2))
04709   */
04710   template<typename _ForwardIterator1, typename _ForwardIterator2>
04711     _ForwardIterator1
04712     search(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
04713        _ForwardIterator2 __first2, _ForwardIterator2 __last2)
04714     {
04715       // concept requirements
04716       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator1>)
04717       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator2>)
04718       __glibcxx_function_requires(_EqualOpConcept<
04719         typename iterator_traits<_ForwardIterator1>::value_type,
04720         typename iterator_traits<_ForwardIterator2>::value_type>)
04721       __glibcxx_requires_valid_range(__first1, __last1);
04722       __glibcxx_requires_valid_range(__first2, __last2);
04723 
04724       // Test for empty ranges
04725       if (__first1 == __last1 || __first2 == __last2)
04726     return __first1;
04727 
04728       // Test for a pattern of length 1.
04729       _ForwardIterator2 __p1(__first2);
04730       if (++__p1 == __last2)
04731     return _GLIBCXX_STD_A::find(__first1, __last1, *__first2);
04732 
04733       // General case.
04734       _ForwardIterator2 __p;
04735       _ForwardIterator1 __current = __first1;
04736 
04737       for (;;)
04738     {
04739       __first1 = _GLIBCXX_STD_A::find(__first1, __last1, *__first2);
04740       if (__first1 == __last1)
04741         return __last1;
04742 
04743       __p = __p1;
04744       __current = __first1;
04745       if (++__current == __last1)
04746         return __last1;
04747 
04748       while (*__current == *__p)
04749         {
04750           if (++__p == __last2)
04751         return __first1;
04752           if (++__current == __last1)
04753         return __last1;
04754         }
04755       ++__first1;
04756     }
04757       return __first1;
04758     }
04759 
04760   /**
04761    *  @brief Search a sequence for a matching sub-sequence using a predicate.
04762    *  @ingroup non_mutating_algorithms
04763    *  @param  __first1     A forward iterator.
04764    *  @param  __last1      A forward iterator.
04765    *  @param  __first2     A forward iterator.
04766    *  @param  __last2      A forward iterator.
04767    *  @param  __predicate  A binary predicate.
04768    *  @return   The first iterator @c i in the range
04769    *  @p [__first1,__last1-(__last2-__first2)) such that
04770    *  @p __predicate(*(i+N),*(__first2+N)) is true for each @c N in the range
04771    *  @p [0,__last2-__first2), or @p __last1 if no such iterator exists.
04772    *
04773    *  Searches the range @p [__first1,__last1) for a sub-sequence that
04774    *  compares equal value-by-value with the sequence given by @p
04775    *  [__first2,__last2), using @p __predicate to determine equality,
04776    *  and returns an iterator to the first element of the
04777    *  sub-sequence, or @p __last1 if no such iterator exists.
04778    *
04779    *  @see search(_ForwardIter1, _ForwardIter1, _ForwardIter2, _ForwardIter2)
04780   */
04781   template<typename _ForwardIterator1, typename _ForwardIterator2,
04782        typename _BinaryPredicate>
04783     _ForwardIterator1
04784     search(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
04785        _ForwardIterator2 __first2, _ForwardIterator2 __last2,
04786        _BinaryPredicate  __predicate)
04787     {
04788       // concept requirements
04789       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator1>)
04790       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator2>)
04791       __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
04792         typename iterator_traits<_ForwardIterator1>::value_type,
04793         typename iterator_traits<_ForwardIterator2>::value_type>)
04794       __glibcxx_requires_valid_range(__first1, __last1);
04795       __glibcxx_requires_valid_range(__first2, __last2);
04796 
04797       // Test for empty ranges
04798       if (__first1 == __last1 || __first2 == __last2)
04799     return __first1;
04800 
04801       // Test for a pattern of length 1.
04802       _ForwardIterator2 __p1(__first2);
04803       if (++__p1 == __last2)
04804     {
04805       while (__first1 != __last1
04806          && !bool(__predicate(*__first1, *__first2)))
04807         ++__first1;
04808       return __first1;
04809     }
04810 
04811       // General case.
04812       _ForwardIterator2 __p;
04813       _ForwardIterator1 __current = __first1;
04814 
04815       for (;;)
04816     {
04817       while (__first1 != __last1
04818          && !bool(__predicate(*__first1, *__first2)))
04819         ++__first1;
04820       if (__first1 == __last1)
04821         return __last1;
04822 
04823       __p = __p1;
04824       __current = __first1;
04825       if (++__current == __last1)
04826         return __last1;
04827 
04828       while (__predicate(*__current, *__p))
04829         {
04830           if (++__p == __last2)
04831         return __first1;
04832           if (++__current == __last1)
04833         return __last1;
04834         }
04835       ++__first1;
04836     }
04837       return __first1;
04838     }
04839 
04840 
04841   /**
04842    *  @brief Search a sequence for a number of consecutive values.
04843    *  @ingroup non_mutating_algorithms
04844    *  @param  __first  A forward iterator.
04845    *  @param  __last   A forward iterator.
04846    *  @param  __count  The number of consecutive values.
04847    *  @param  __val    The value to find.
04848    *  @return The first iterator @c i in the range @p
04849    *  [__first,__last-__count) such that @c *(i+N) == @p __val for
04850    *  each @c N in the range @p [0,__count), or @p __last if no such
04851    *  iterator exists.
04852    *
04853    *  Searches the range @p [__first,__last) for @p count consecutive elements
04854    *  equal to @p __val.
04855   */
04856   template<typename _ForwardIterator, typename _Integer, typename _Tp>
04857     _ForwardIterator
04858     search_n(_ForwardIterator __first, _ForwardIterator __last,
04859          _Integer __count, const _Tp& __val)
04860     {
04861       // concept requirements
04862       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
04863       __glibcxx_function_requires(_EqualOpConcept<
04864     typename iterator_traits<_ForwardIterator>::value_type, _Tp>)
04865       __glibcxx_requires_valid_range(__first, __last);
04866 
04867       if (__count <= 0)
04868     return __first;
04869       if (__count == 1)
04870     return _GLIBCXX_STD_A::find(__first, __last, __val);
04871       return std::__search_n(__first, __last, __count, __val,
04872                  std::__iterator_category(__first));
04873     }
04874 
04875 
04876   /**
04877    *  @brief Search a sequence for a number of consecutive values using a
04878    *         predicate.
04879    *  @ingroup non_mutating_algorithms
04880    *  @param  __first        A forward iterator.
04881    *  @param  __last         A forward iterator.
04882    *  @param  __count        The number of consecutive values.
04883    *  @param  __val          The value to find.
04884    *  @param  __binary_pred  A binary predicate.
04885    *  @return The first iterator @c i in the range @p
04886    *  [__first,__last-__count) such that @p
04887    *  __binary_pred(*(i+N),__val) is true for each @c N in the range
04888    *  @p [0,__count), or @p __last if no such iterator exists.
04889    *
04890    *  Searches the range @p [__first,__last) for @p __count
04891    *  consecutive elements for which the predicate returns true.
04892   */
04893   template<typename _ForwardIterator, typename _Integer, typename _Tp,
04894            typename _BinaryPredicate>
04895     _ForwardIterator
04896     search_n(_ForwardIterator __first, _ForwardIterator __last,
04897          _Integer __count, const _Tp& __val,
04898          _BinaryPredicate __binary_pred)
04899     {
04900       // concept requirements
04901       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
04902       __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
04903         typename iterator_traits<_ForwardIterator>::value_type, _Tp>)
04904       __glibcxx_requires_valid_range(__first, __last);
04905 
04906       if (__count <= 0)
04907     return __first;
04908       if (__count == 1)
04909     {
04910       while (__first != __last && !bool(__binary_pred(*__first, __val)))
04911         ++__first;
04912       return __first;
04913     }
04914       return std::__search_n(__first, __last, __count, __val, __binary_pred,
04915                  std::__iterator_category(__first));
04916     }
04917 
04918 
04919   /**
04920    *  @brief Perform an operation on a sequence.
04921    *  @ingroup mutating_algorithms
04922    *  @param  __first     An input iterator.
04923    *  @param  __last      An input iterator.
04924    *  @param  __result    An output iterator.
04925    *  @param  __unary_op  A unary operator.
04926    *  @return   An output iterator equal to @p __result+(__last-__first).
04927    *
04928    *  Applies the operator to each element in the input range and assigns
04929    *  the results to successive elements of the output sequence.
04930    *  Evaluates @p *(__result+N)=unary_op(*(__first+N)) for each @c N in the
04931    *  range @p [0,__last-__first).
04932    *
04933    *  @p unary_op must not alter its argument.
04934   */
04935   template<typename _InputIterator, typename _OutputIterator,
04936        typename _UnaryOperation>
04937     _OutputIterator
04938     transform(_InputIterator __first, _InputIterator __last,
04939           _OutputIterator __result, _UnaryOperation __unary_op)
04940     {
04941       // concept requirements
04942       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
04943       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
04944             // "the type returned by a _UnaryOperation"
04945             __typeof__(__unary_op(*__first))>)
04946       __glibcxx_requires_valid_range(__first, __last);
04947 
04948       for (; __first != __last; ++__first, ++__result)
04949     *__result = __unary_op(*__first);
04950       return __result;
04951     }
04952 
04953   /**
04954    *  @brief Perform an operation on corresponding elements of two sequences.
04955    *  @ingroup mutating_algorithms
04956    *  @param  __first1     An input iterator.
04957    *  @param  __last1      An input iterator.
04958    *  @param  __first2     An input iterator.
04959    *  @param  __result     An output iterator.
04960    *  @param  __binary_op  A binary operator.
04961    *  @return   An output iterator equal to @p result+(last-first).
04962    *
04963    *  Applies the operator to the corresponding elements in the two
04964    *  input ranges and assigns the results to successive elements of the
04965    *  output sequence.
04966    *  Evaluates @p
04967    *  *(__result+N)=__binary_op(*(__first1+N),*(__first2+N)) for each
04968    *  @c N in the range @p [0,__last1-__first1).
04969    *
04970    *  @p binary_op must not alter either of its arguments.
04971   */
04972   template<typename _InputIterator1, typename _InputIterator2,
04973        typename _OutputIterator, typename _BinaryOperation>
04974     _OutputIterator
04975     transform(_InputIterator1 __first1, _InputIterator1 __last1,
04976           _InputIterator2 __first2, _OutputIterator __result,
04977           _BinaryOperation __binary_op)
04978     {
04979       // concept requirements
04980       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
04981       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
04982       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
04983             // "the type returned by a _BinaryOperation"
04984             __typeof__(__binary_op(*__first1,*__first2))>)
04985       __glibcxx_requires_valid_range(__first1, __last1);
04986 
04987       for (; __first1 != __last1; ++__first1, ++__first2, ++__result)
04988     *__result = __binary_op(*__first1, *__first2);
04989       return __result;
04990     }
04991 
04992   /**
04993    *  @brief Replace each occurrence of one value in a sequence with another
04994    *         value.
04995    *  @ingroup mutating_algorithms
04996    *  @param  __first      A forward iterator.
04997    *  @param  __last       A forward iterator.
04998    *  @param  __old_value  The value to be replaced.
04999    *  @param  __new_value  The replacement value.
05000    *  @return   replace() returns no value.
05001    *
05002    *  For each iterator @c i in the range @p [__first,__last) if @c *i ==
05003    *  @p __old_value then the assignment @c *i = @p __new_value is performed.
05004   */
05005   template<typename _ForwardIterator, typename _Tp>
05006     void
05007     replace(_ForwardIterator __first, _ForwardIterator __last,
05008         const _Tp& __old_value, const _Tp& __new_value)
05009     {
05010       // concept requirements
05011       __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
05012                   _ForwardIterator>)
05013       __glibcxx_function_requires(_EqualOpConcept<
05014         typename iterator_traits<_ForwardIterator>::value_type, _Tp>)
05015       __glibcxx_function_requires(_ConvertibleConcept<_Tp,
05016         typename iterator_traits<_ForwardIterator>::value_type>)
05017       __glibcxx_requires_valid_range(__first, __last);
05018 
05019       for (; __first != __last; ++__first)
05020     if (*__first == __old_value)
05021       *__first = __new_value;
05022     }
05023 
05024   /**
05025    *  @brief Replace each value in a sequence for which a predicate returns
05026    *         true with another value.
05027    *  @ingroup mutating_algorithms
05028    *  @param  __first      A forward iterator.
05029    *  @param  __last       A forward iterator.
05030    *  @param  __pred       A predicate.
05031    *  @param  __new_value  The replacement value.
05032    *  @return   replace_if() returns no value.
05033    *
05034    *  For each iterator @c i in the range @p [__first,__last) if @p __pred(*i)
05035    *  is true then the assignment @c *i = @p __new_value is performed.
05036   */
05037   template<typename _ForwardIterator, typename _Predicate, typename _Tp>
05038     void
05039     replace_if(_ForwardIterator __first, _ForwardIterator __last,
05040            _Predicate __pred, const _Tp& __new_value)
05041     {
05042       // concept requirements
05043       __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
05044                   _ForwardIterator>)
05045       __glibcxx_function_requires(_ConvertibleConcept<_Tp,
05046         typename iterator_traits<_ForwardIterator>::value_type>)
05047       __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
05048         typename iterator_traits<_ForwardIterator>::value_type>)
05049       __glibcxx_requires_valid_range(__first, __last);
05050 
05051       for (; __first != __last; ++__first)
05052     if (__pred(*__first))
05053       *__first = __new_value;
05054     }
05055 
05056   /**
05057    *  @brief Assign the result of a function object to each value in a
05058    *         sequence.
05059    *  @ingroup mutating_algorithms
05060    *  @param  __first  A forward iterator.
05061    *  @param  __last   A forward iterator.
05062    *  @param  __gen    A function object taking no arguments and returning
05063    *                 std::iterator_traits<_ForwardIterator>::value_type
05064    *  @return   generate() returns no value.
05065    *
05066    *  Performs the assignment @c *i = @p __gen() for each @c i in the range
05067    *  @p [__first,__last).
05068   */
05069   template<typename _ForwardIterator, typename _Generator>
05070     void
05071     generate(_ForwardIterator __first, _ForwardIterator __last,
05072          _Generator __gen)
05073     {
05074       // concept requirements
05075       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
05076       __glibcxx_function_requires(_GeneratorConcept<_Generator,
05077         typename iterator_traits<_ForwardIterator>::value_type>)
05078       __glibcxx_requires_valid_range(__first, __last);
05079 
05080       for (; __first != __last; ++__first)
05081     *__first = __gen();
05082     }
05083 
05084   /**
05085    *  @brief Assign the result of a function object to each value in a
05086    *         sequence.
05087    *  @ingroup mutating_algorithms
05088    *  @param  __first  A forward iterator.
05089    *  @param  __n      The length of the sequence.
05090    *  @param  __gen    A function object taking no arguments and returning
05091    *                 std::iterator_traits<_ForwardIterator>::value_type
05092    *  @return   The end of the sequence, @p __first+__n
05093    *
05094    *  Performs the assignment @c *i = @p __gen() for each @c i in the range
05095    *  @p [__first,__first+__n).
05096    *
05097    *  _GLIBCXX_RESOLVE_LIB_DEFECTS
05098    *  DR 865. More algorithms that throw away information
05099   */
05100   template<typename _OutputIterator, typename _Size, typename _Generator>
05101     _OutputIterator
05102     generate_n(_OutputIterator __first, _Size __n, _Generator __gen)
05103     {
05104       // concept requirements
05105       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
05106             // "the type returned by a _Generator"
05107             __typeof__(__gen())>)
05108 
05109       for (__decltype(__n + 0) __niter = __n;
05110        __niter > 0; --__niter, ++__first)
05111     *__first = __gen();
05112       return __first;
05113     }
05114 
05115 
05116   /**
05117    *  @brief Copy a sequence, removing consecutive duplicate values.
05118    *  @ingroup mutating_algorithms
05119    *  @param  __first   An input iterator.
05120    *  @param  __last    An input iterator.
05121    *  @param  __result  An output iterator.
05122    *  @return   An iterator designating the end of the resulting sequence.
05123    *
05124    *  Copies each element in the range @p [__first,__last) to the range
05125    *  beginning at @p __result, except that only the first element is copied
05126    *  from groups of consecutive elements that compare equal.
05127    *  unique_copy() is stable, so the relative order of elements that are
05128    *  copied is unchanged.
05129    *
05130    *  _GLIBCXX_RESOLVE_LIB_DEFECTS
05131    *  DR 241. Does unique_copy() require CopyConstructible and Assignable?
05132    *  
05133    *  _GLIBCXX_RESOLVE_LIB_DEFECTS
05134    *  DR 538. 241 again: Does unique_copy() require CopyConstructible and 
05135    *  Assignable?
05136   */
05137   template<typename _InputIterator, typename _OutputIterator>
05138     inline _OutputIterator
05139     unique_copy(_InputIterator __first, _InputIterator __last,
05140         _OutputIterator __result)
05141     {
05142       // concept requirements
05143       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
05144       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
05145         typename iterator_traits<_InputIterator>::value_type>)
05146       __glibcxx_function_requires(_EqualityComparableConcept<
05147         typename iterator_traits<_InputIterator>::value_type>)
05148       __glibcxx_requires_valid_range(__first, __last);
05149 
05150       if (__first == __last)
05151     return __result;
05152       return std::__unique_copy(__first, __last, __result,
05153                 std::__iterator_category(__first),
05154                 std::__iterator_category(__result));
05155     }
05156 
05157   /**
05158    *  @brief Copy a sequence, removing consecutive values using a predicate.
05159    *  @ingroup mutating_algorithms
05160    *  @param  __first        An input iterator.
05161    *  @param  __last         An input iterator.
05162    *  @param  __result       An output iterator.
05163    *  @param  __binary_pred  A binary predicate.
05164    *  @return   An iterator designating the end of the resulting sequence.
05165    *
05166    *  Copies each element in the range @p [__first,__last) to the range
05167    *  beginning at @p __result, except that only the first element is copied
05168    *  from groups of consecutive elements for which @p __binary_pred returns
05169    *  true.
05170    *  unique_copy() is stable, so the relative order of elements that are
05171    *  copied is unchanged.
05172    *
05173    *  _GLIBCXX_RESOLVE_LIB_DEFECTS
05174    *  DR 241. Does unique_copy() require CopyConstructible and Assignable?
05175   */
05176   template<typename _InputIterator, typename _OutputIterator,
05177        typename _BinaryPredicate>
05178     inline _OutputIterator
05179     unique_copy(_InputIterator __first, _InputIterator __last,
05180         _OutputIterator __result,
05181         _BinaryPredicate __binary_pred)
05182     {
05183       // concept requirements -- predicates checked later
05184       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
05185       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
05186         typename iterator_traits<_InputIterator>::value_type>)
05187       __glibcxx_requires_valid_range(__first, __last);
05188 
05189       if (__first == __last)
05190     return __result;
05191       return std::__unique_copy(__first, __last, __result, __binary_pred,
05192                 std::__iterator_category(__first),
05193                 std::__iterator_category(__result));
05194     }
05195 
05196 
05197   /**
05198    *  @brief Randomly shuffle the elements of a sequence.
05199    *  @ingroup mutating_algorithms
05200    *  @param  __first   A forward iterator.
05201    *  @param  __last    A forward iterator.
05202    *  @return  Nothing.
05203    *
05204    *  Reorder the elements in the range @p [__first,__last) using a random
05205    *  distribution, so that every possible ordering of the sequence is
05206    *  equally likely.
05207   */
05208   template<typename _RandomAccessIterator>
05209     inline void
05210     random_shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last)
05211     {
05212       // concept requirements
05213       __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
05214         _RandomAccessIterator>)
05215       __glibcxx_requires_valid_range(__first, __last);
05216 
05217       if (__first != __last)
05218     for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i)
05219       std::iter_swap(__i, __first + (std::rand() % ((__i - __first) + 1)));
05220     }
05221 
05222   /**
05223    *  @brief Shuffle the elements of a sequence using a random number
05224    *         generator.
05225    *  @ingroup mutating_algorithms
05226    *  @param  __first   A forward iterator.
05227    *  @param  __last    A forward iterator.
05228    *  @param  __rand    The RNG functor or function.
05229    *  @return  Nothing.
05230    *
05231    *  Reorders the elements in the range @p [__first,__last) using @p __rand to
05232    *  provide a random distribution. Calling @p __rand(N) for a positive
05233    *  integer @p N should return a randomly chosen integer from the
05234    *  range [0,N).
05235   */
05236   template<typename _RandomAccessIterator, typename _RandomNumberGenerator>
05237     void
05238     random_shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last,
05239 #if __cplusplus >= 201103L
05240            _RandomNumberGenerator&& __rand)
05241 #else
05242            _RandomNumberGenerator& __rand)
05243 #endif
05244     {
05245       // concept requirements
05246       __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
05247         _RandomAccessIterator>)
05248       __glibcxx_requires_valid_range(__first, __last);
05249 
05250       if (__first == __last)
05251     return;
05252       for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i)
05253     std::iter_swap(__i, __first + __rand((__i - __first) + 1));
05254     }
05255 
05256 
05257   /**
05258    *  @brief Move elements for which a predicate is true to the beginning
05259    *         of a sequence.
05260    *  @ingroup mutating_algorithms
05261    *  @param  __first   A forward iterator.
05262    *  @param  __last    A forward iterator.
05263    *  @param  __pred    A predicate functor.
05264    *  @return  An iterator @p middle such that @p __pred(i) is true for each
05265    *  iterator @p i in the range @p [__first,middle) and false for each @p i
05266    *  in the range @p [middle,__last).
05267    *
05268    *  @p __pred must not modify its operand. @p partition() does not preserve
05269    *  the relative ordering of elements in each group, use
05270    *  @p stable_partition() if this is needed.
05271   */
05272   template<typename _ForwardIterator, typename _Predicate>
05273     inline _ForwardIterator
05274     partition(_ForwardIterator __first, _ForwardIterator __last,
05275           _Predicate   __pred)
05276     {
05277       // concept requirements
05278       __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
05279                   _ForwardIterator>)
05280       __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
05281         typename iterator_traits<_ForwardIterator>::value_type>)
05282       __glibcxx_requires_valid_range(__first, __last);
05283 
05284       return std::__partition(__first, __last, __pred,
05285                   std::__iterator_category(__first));
05286     }
05287 
05288 
05289 
05290   /**
05291    *  @brief Sort the smallest elements of a sequence.
05292    *  @ingroup sorting_algorithms
05293    *  @param  __first   An iterator.
05294    *  @param  __middle  Another iterator.
05295    *  @param  __last    Another iterator.
05296    *  @return  Nothing.
05297    *
05298    *  Sorts the smallest @p (__middle-__first) elements in the range
05299    *  @p [first,last) and moves them to the range @p [__first,__middle). The
05300    *  order of the remaining elements in the range @p [__middle,__last) is
05301    *  undefined.
05302    *  After the sort if @e i and @e j are iterators in the range
05303    *  @p [__first,__middle) such that i precedes j and @e k is an iterator in
05304    *  the range @p [__middle,__last) then *j<*i and *k<*i are both false.
05305   */
05306   template<typename _RandomAccessIterator>
05307     inline void
05308     partial_sort(_RandomAccessIterator __first,
05309          _RandomAccessIterator __middle,
05310          _RandomAccessIterator __last)
05311     {
05312       typedef typename iterator_traits<_RandomAccessIterator>::value_type
05313     _ValueType;
05314 
05315       // concept requirements
05316       __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
05317         _RandomAccessIterator>)
05318       __glibcxx_function_requires(_LessThanComparableConcept<_ValueType>)
05319       __glibcxx_requires_valid_range(__first, __middle);
05320       __glibcxx_requires_valid_range(__middle, __last);
05321 
05322       std::__heap_select(__first, __middle, __last);
05323       std::sort_heap(__first, __middle);
05324     }
05325 
05326   /**
05327    *  @brief Sort the smallest elements of a sequence using a predicate
05328    *         for comparison.
05329    *  @ingroup sorting_algorithms
05330    *  @param  __first   An iterator.
05331    *  @param  __middle  Another iterator.
05332    *  @param  __last    Another iterator.
05333    *  @param  __comp    A comparison functor.
05334    *  @return  Nothing.
05335    *
05336    *  Sorts the smallest @p (__middle-__first) elements in the range
05337    *  @p [__first,__last) and moves them to the range @p [__first,__middle). The
05338    *  order of the remaining elements in the range @p [__middle,__last) is
05339    *  undefined.
05340    *  After the sort if @e i and @e j are iterators in the range
05341    *  @p [__first,__middle) such that i precedes j and @e k is an iterator in
05342    *  the range @p [__middle,__last) then @p *__comp(j,*i) and @p __comp(*k,*i)
05343    *  are both false.
05344   */
05345   template<typename _RandomAccessIterator, typename _Compare>
05346     inline void
05347     partial_sort(_RandomAccessIterator __first,
05348          _RandomAccessIterator __middle,
05349          _RandomAccessIterator __last,
05350          _Compare __comp)
05351     {
05352       typedef typename iterator_traits<_RandomAccessIterator>::value_type
05353     _ValueType;
05354 
05355       // concept requirements
05356       __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
05357         _RandomAccessIterator>)
05358       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
05359                   _ValueType, _ValueType>)
05360       __glibcxx_requires_valid_range(__first, __middle);
05361       __glibcxx_requires_valid_range(__middle, __last);
05362 
05363       std::__heap_select(__first, __middle, __last, __comp);
05364       std::sort_heap(__first, __middle, __comp);
05365     }
05366 
05367   /**
05368    *  @brief Sort a sequence just enough to find a particular position.
05369    *  @ingroup sorting_algorithms
05370    *  @param  __first   An iterator.
05371    *  @param  __nth     Another iterator.
05372    *  @param  __last    Another iterator.
05373    *  @return  Nothing.
05374    *
05375    *  Rearranges the elements in the range @p [__first,__last) so that @p *__nth
05376    *  is the same element that would have been in that position had the
05377    *  whole sequence been sorted. The elements either side of @p *__nth are
05378    *  not completely sorted, but for any iterator @e i in the range
05379    *  @p [__first,__nth) and any iterator @e j in the range @p [__nth,__last) it
05380    *  holds that *j < *i is false.
05381   */
05382   template<typename _RandomAccessIterator>
05383     inline void
05384     nth_element(_RandomAccessIterator __first, _RandomAccessIterator __nth,
05385         _RandomAccessIterator __last)
05386     {
05387       typedef typename iterator_traits<_RandomAccessIterator>::value_type
05388     _ValueType;
05389 
05390       // concept requirements
05391       __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
05392                   _RandomAccessIterator>)
05393       __glibcxx_function_requires(_LessThanComparableConcept<_ValueType>)
05394       __glibcxx_requires_valid_range(__first, __nth);
05395       __glibcxx_requires_valid_range(__nth, __last);
05396 
05397       if (__first == __last || __nth == __last)
05398     return;
05399 
05400       std::__introselect(__first, __nth, __last,
05401              std::__lg(__last - __first) * 2);
05402     }
05403 
05404   /**
05405    *  @brief Sort a sequence just enough to find a particular position
05406    *         using a predicate for comparison.
05407    *  @ingroup sorting_algorithms
05408    *  @param  __first   An iterator.
05409    *  @param  __nth     Another iterator.
05410    *  @param  __last    Another iterator.
05411    *  @param  __comp    A comparison functor.
05412    *  @return  Nothing.
05413    *
05414    *  Rearranges the elements in the range @p [__first,__last) so that @p *__nth
05415    *  is the same element that would have been in that position had the
05416    *  whole sequence been sorted. The elements either side of @p *__nth are
05417    *  not completely sorted, but for any iterator @e i in the range
05418    *  @p [__first,__nth) and any iterator @e j in the range @p [__nth,__last) it
05419    *  holds that @p __comp(*j,*i) is false.
05420   */
05421   template<typename _RandomAccessIterator, typename _Compare>
05422     inline void
05423     nth_element(_RandomAccessIterator __first, _RandomAccessIterator __nth,
05424         _RandomAccessIterator __last, _Compare __comp)
05425     {
05426       typedef typename iterator_traits<_RandomAccessIterator>::value_type
05427     _ValueType;
05428 
05429       // concept requirements
05430       __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
05431                   _RandomAccessIterator>)
05432       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
05433                   _ValueType, _ValueType>)
05434       __glibcxx_requires_valid_range(__first, __nth);
05435       __glibcxx_requires_valid_range(__nth, __last);
05436 
05437       if (__first == __last || __nth == __last)
05438     return;
05439 
05440       std::__introselect(__first, __nth, __last,
05441              std::__lg(__last - __first) * 2, __comp);
05442     }
05443 
05444 
05445   /**
05446    *  @brief Sort the elements of a sequence.
05447    *  @ingroup sorting_algorithms
05448    *  @param  __first   An iterator.
05449    *  @param  __last    Another iterator.
05450    *  @return  Nothing.
05451    *
05452    *  Sorts the elements in the range @p [__first,__last) in ascending order,
05453    *  such that for each iterator @e i in the range @p [__first,__last-1),  
05454    *  *(i+1)<*i is false.
05455    *
05456    *  The relative ordering of equivalent elements is not preserved, use
05457    *  @p stable_sort() if this is needed.
05458   */
05459   template<typename _RandomAccessIterator>
05460     inline void
05461     sort(_RandomAccessIterator __first, _RandomAccessIterator __last)
05462     {
05463       typedef typename iterator_traits<_RandomAccessIterator>::value_type
05464     _ValueType;
05465 
05466       // concept requirements
05467       __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
05468         _RandomAccessIterator>)
05469       __glibcxx_function_requires(_LessThanComparableConcept<_ValueType>)
05470       __glibcxx_requires_valid_range(__first, __last);
05471 
05472       if (__first != __last)
05473     {
05474       std::__introsort_loop(__first, __last,
05475                 std::__lg(__last - __first) * 2);
05476       std::__final_insertion_sort(__first, __last);
05477     }
05478     }
05479 
05480   /**
05481    *  @brief Sort the elements of a sequence using a predicate for comparison.
05482    *  @ingroup sorting_algorithms
05483    *  @param  __first   An iterator.
05484    *  @param  __last    Another iterator.
05485    *  @param  __comp    A comparison functor.
05486    *  @return  Nothing.
05487    *
05488    *  Sorts the elements in the range @p [__first,__last) in ascending order,
05489    *  such that @p __comp(*(i+1),*i) is false for every iterator @e i in the
05490    *  range @p [__first,__last-1).
05491    *
05492    *  The relative ordering of equivalent elements is not preserved, use
05493    *  @p stable_sort() if this is needed.
05494   */
05495   template<typename _RandomAccessIterator, typename _Compare>
05496     inline void
05497     sort(_RandomAccessIterator __first, _RandomAccessIterator __last,
05498      _Compare __comp)
05499     {
05500       typedef typename iterator_traits<_RandomAccessIterator>::value_type
05501     _ValueType;
05502 
05503       // concept requirements
05504       __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
05505         _RandomAccessIterator>)
05506       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, _ValueType,
05507                   _ValueType>)
05508       __glibcxx_requires_valid_range(__first, __last);
05509 
05510       if (__first != __last)
05511     {
05512       std::__introsort_loop(__first, __last,
05513                 std::__lg(__last - __first) * 2, __comp);
05514       std::__final_insertion_sort(__first, __last, __comp);
05515     }
05516     }
05517 
05518   /**
05519    *  @brief Merges two sorted ranges.
05520    *  @ingroup sorting_algorithms
05521    *  @param  __first1  An iterator.
05522    *  @param  __first2  Another iterator.
05523    *  @param  __last1   Another iterator.
05524    *  @param  __last2   Another iterator.
05525    *  @param  __result  An iterator pointing to the end of the merged range.
05526    *  @return         An iterator pointing to the first element <em>not less
05527    *                  than</em> @e val.
05528    *
05529    *  Merges the ranges @p [__first1,__last1) and @p [__first2,__last2) into
05530    *  the sorted range @p [__result, __result + (__last1-__first1) +
05531    *  (__last2-__first2)).  Both input ranges must be sorted, and the
05532    *  output range must not overlap with either of the input ranges.
05533    *  The sort is @e stable, that is, for equivalent elements in the
05534    *  two ranges, elements from the first range will always come
05535    *  before elements from the second.
05536   */
05537   template<typename _InputIterator1, typename _InputIterator2,
05538        typename _OutputIterator>
05539     _OutputIterator
05540     merge(_InputIterator1 __first1, _InputIterator1 __last1,
05541       _InputIterator2 __first2, _InputIterator2 __last2,
05542       _OutputIterator __result)
05543     {
05544       typedef typename iterator_traits<_InputIterator1>::value_type
05545     _ValueType1;
05546       typedef typename iterator_traits<_InputIterator2>::value_type
05547     _ValueType2;
05548 
05549       // concept requirements
05550       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
05551       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
05552       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
05553                   _ValueType1>)
05554       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
05555                   _ValueType2>)
05556       __glibcxx_function_requires(_LessThanOpConcept<_ValueType2, _ValueType1>) 
05557       __glibcxx_requires_sorted_set(__first1, __last1, __first2);
05558       __glibcxx_requires_sorted_set(__first2, __last2, __first1);
05559 
05560       while (__first1 != __last1 && __first2 != __last2)
05561     {
05562       if (*__first2 < *__first1)
05563         {
05564           *__result = *__first2;
05565           ++__first2;
05566         }
05567       else
05568         {
05569           *__result = *__first1;
05570           ++__first1;
05571         }
05572       ++__result;
05573     }
05574       return std::copy(__first2, __last2, std::copy(__first1, __last1,
05575                             __result));
05576     }
05577 
05578   /**
05579    *  @brief Merges two sorted ranges.
05580    *  @ingroup sorting_algorithms
05581    *  @param  __first1  An iterator.
05582    *  @param  __first2  Another iterator.
05583    *  @param  __last1   Another iterator.
05584    *  @param  __last2   Another iterator.
05585    *  @param  __result  An iterator pointing to the end of the merged range.
05586    *  @param  __comp    A functor to use for comparisons.
05587    *  @return         An iterator pointing to the first element "not less
05588    *                  than" @e val.
05589    *
05590    *  Merges the ranges @p [__first1,__last1) and @p [__first2,__last2) into
05591    *  the sorted range @p [__result, __result + (__last1-__first1) +
05592    *  (__last2-__first2)).  Both input ranges must be sorted, and the
05593    *  output range must not overlap with either of the input ranges.
05594    *  The sort is @e stable, that is, for equivalent elements in the
05595    *  two ranges, elements from the first range will always come
05596    *  before elements from the second.
05597    *
05598    *  The comparison function should have the same effects on ordering as
05599    *  the function used for the initial sort.
05600   */
05601   template<typename _InputIterator1, typename _InputIterator2,
05602        typename _OutputIterator, typename _Compare>
05603     _OutputIterator
05604     merge(_InputIterator1 __first1, _InputIterator1 __last1,
05605       _InputIterator2 __first2, _InputIterator2 __last2,
05606       _OutputIterator __result, _Compare __comp)
05607     {
05608       typedef typename iterator_traits<_InputIterator1>::value_type
05609     _ValueType1;
05610       typedef typename iterator_traits<_InputIterator2>::value_type
05611     _ValueType2;
05612 
05613       // concept requirements
05614       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
05615       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
05616       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
05617                   _ValueType1>)
05618       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
05619                   _ValueType2>)
05620       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
05621                   _ValueType2, _ValueType1>)
05622       __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp);
05623       __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp);
05624 
05625       while (__first1 != __last1 && __first2 != __last2)
05626     {
05627       if (__comp(*__first2, *__first1))
05628         {
05629           *__result = *__first2;
05630           ++__first2;
05631         }
05632       else
05633         {
05634           *__result = *__first1;
05635           ++__first1;
05636         }
05637       ++__result;
05638     }
05639       return std::copy(__first2, __last2, std::copy(__first1, __last1,
05640                             __result));
05641     }
05642 
05643 
05644   /**
05645    *  @brief Sort the elements of a sequence, preserving the relative order
05646    *         of equivalent elements.
05647    *  @ingroup sorting_algorithms
05648    *  @param  __first   An iterator.
05649    *  @param  __last    Another iterator.
05650    *  @return  Nothing.
05651    *
05652    *  Sorts the elements in the range @p [__first,__last) in ascending order,
05653    *  such that for each iterator @p i in the range @p [__first,__last-1),
05654    *  @p *(i+1)<*i is false.
05655    *
05656    *  The relative ordering of equivalent elements is preserved, so any two
05657    *  elements @p x and @p y in the range @p [__first,__last) such that
05658    *  @p x<y is false and @p y<x is false will have the same relative
05659    *  ordering after calling @p stable_sort().
05660   */
05661   template<typename _RandomAccessIterator>
05662     inline void
05663     stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last)
05664     {
05665       typedef typename iterator_traits<_RandomAccessIterator>::value_type
05666     _ValueType;
05667       typedef typename iterator_traits<_RandomAccessIterator>::difference_type
05668     _DistanceType;
05669 
05670       // concept requirements
05671       __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
05672         _RandomAccessIterator>)
05673       __glibcxx_function_requires(_LessThanComparableConcept<_ValueType>)
05674       __glibcxx_requires_valid_range(__first, __last);
05675 
05676       _Temporary_buffer<_RandomAccessIterator, _ValueType> __buf(__first,
05677                                  __last);
05678       if (__buf.begin() == 0)
05679     std::__inplace_stable_sort(__first, __last);
05680       else
05681     std::__stable_sort_adaptive(__first, __last, __buf.begin(),
05682                     _DistanceType(__buf.size()));
05683     }
05684 
05685   /**
05686    *  @brief Sort the elements of a sequence using a predicate for comparison,
05687    *         preserving the relative order of equivalent elements.
05688    *  @ingroup sorting_algorithms
05689    *  @param  __first   An iterator.
05690    *  @param  __last    Another iterator.
05691    *  @param  __comp    A comparison functor.
05692    *  @return  Nothing.
05693    *
05694    *  Sorts the elements in the range @p [__first,__last) in ascending order,
05695    *  such that for each iterator @p i in the range @p [__first,__last-1),
05696    *  @p __comp(*(i+1),*i) is false.
05697    *
05698    *  The relative ordering of equivalent elements is preserved, so any two
05699    *  elements @p x and @p y in the range @p [__first,__last) such that
05700    *  @p __comp(x,y) is false and @p __comp(y,x) is false will have the same
05701    *  relative ordering after calling @p stable_sort().
05702   */
05703   template<typename _RandomAccessIterator, typename _Compare>
05704     inline void
05705     stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last,
05706         _Compare __comp)
05707     {
05708       typedef typename iterator_traits<_RandomAccessIterator>::value_type
05709     _ValueType;
05710       typedef typename iterator_traits<_RandomAccessIterator>::difference_type
05711     _DistanceType;
05712 
05713       // concept requirements
05714       __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
05715         _RandomAccessIterator>)
05716       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
05717                   _ValueType,
05718                   _ValueType>)
05719       __glibcxx_requires_valid_range(__first, __last);
05720 
05721       _Temporary_buffer<_RandomAccessIterator, _ValueType> __buf(__first,
05722                                  __last);
05723       if (__buf.begin() == 0)
05724     std::__inplace_stable_sort(__first, __last, __comp);
05725       else
05726     std::__stable_sort_adaptive(__first, __last, __buf.begin(),
05727                     _DistanceType(__buf.size()), __comp);
05728     }
05729 
05730 
05731   /**
05732    *  @brief Return the union of two sorted ranges.
05733    *  @ingroup set_algorithms
05734    *  @param  __first1  Start of first range.
05735    *  @param  __last1   End of first range.
05736    *  @param  __first2  Start of second range.
05737    *  @param  __last2   End of second range.
05738    *  @return  End of the output range.
05739    *  @ingroup set_algorithms
05740    *
05741    *  This operation iterates over both ranges, copying elements present in
05742    *  each range in order to the output range.  Iterators increment for each
05743    *  range.  When the current element of one range is less than the other,
05744    *  that element is copied and the iterator advanced.  If an element is
05745    *  contained in both ranges, the element from the first range is copied and
05746    *  both ranges advance.  The output range may not overlap either input
05747    *  range.
05748   */
05749   template<typename _InputIterator1, typename _InputIterator2,
05750        typename _OutputIterator>
05751     _OutputIterator
05752     set_union(_InputIterator1 __first1, _InputIterator1 __last1,
05753           _InputIterator2 __first2, _InputIterator2 __last2,
05754           _OutputIterator __result)
05755     {
05756       typedef typename iterator_traits<_InputIterator1>::value_type
05757     _ValueType1;
05758       typedef typename iterator_traits<_InputIterator2>::value_type
05759     _ValueType2;
05760 
05761       // concept requirements
05762       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
05763       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
05764       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
05765                   _ValueType1>)
05766       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
05767                   _ValueType2>)
05768       __glibcxx_function_requires(_LessThanOpConcept<_ValueType1, _ValueType2>)
05769       __glibcxx_function_requires(_LessThanOpConcept<_ValueType2, _ValueType1>)
05770       __glibcxx_requires_sorted_set(__first1, __last1, __first2);
05771       __glibcxx_requires_sorted_set(__first2, __last2, __first1);
05772 
05773       while (__first1 != __last1 && __first2 != __last2)
05774     {
05775       if (*__first1 < *__first2)
05776         {
05777           *__result = *__first1;
05778           ++__first1;
05779         }
05780       else if (*__first2 < *__first1)
05781         {
05782           *__result = *__first2;
05783           ++__first2;
05784         }
05785       else
05786         {
05787           *__result = *__first1;
05788           ++__first1;
05789           ++__first2;
05790         }
05791       ++__result;
05792     }
05793       return std::copy(__first2, __last2, std::copy(__first1, __last1,
05794                             __result));
05795     }
05796 
05797   /**
05798    *  @brief Return the union of two sorted ranges using a comparison functor.
05799    *  @ingroup set_algorithms
05800    *  @param  __first1  Start of first range.
05801    *  @param  __last1   End of first range.
05802    *  @param  __first2  Start of second range.
05803    *  @param  __last2   End of second range.
05804    *  @param  __comp    The comparison functor.
05805    *  @return  End of the output range.
05806    *  @ingroup set_algorithms
05807    *
05808    *  This operation iterates over both ranges, copying elements present in
05809    *  each range in order to the output range.  Iterators increment for each
05810    *  range.  When the current element of one range is less than the other
05811    *  according to @p __comp, that element is copied and the iterator advanced.
05812    *  If an equivalent element according to @p __comp is contained in both
05813    *  ranges, the element from the first range is copied and both ranges
05814    *  advance.  The output range may not overlap either input range.
05815   */
05816   template<typename _InputIterator1, typename _InputIterator2,
05817        typename _OutputIterator, typename _Compare>
05818     _OutputIterator
05819     set_union(_InputIterator1 __first1, _InputIterator1 __last1,
05820           _InputIterator2 __first2, _InputIterator2 __last2,
05821           _OutputIterator __result, _Compare __comp)
05822     {
05823       typedef typename iterator_traits<_InputIterator1>::value_type
05824     _ValueType1;
05825       typedef typename iterator_traits<_InputIterator2>::value_type
05826     _ValueType2;
05827 
05828       // concept requirements
05829       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
05830       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
05831       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
05832                   _ValueType1>)
05833       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
05834                   _ValueType2>)
05835       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
05836                   _ValueType1, _ValueType2>)
05837       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
05838                   _ValueType2, _ValueType1>)
05839       __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp);
05840       __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp);
05841 
05842       while (__first1 != __last1 && __first2 != __last2)
05843     {
05844       if (__comp(*__first1, *__first2))
05845         {
05846           *__result = *__first1;
05847           ++__first1;
05848         }
05849       else if (__comp(*__first2, *__first1))
05850         {
05851           *__result = *__first2;
05852           ++__first2;
05853         }
05854       else
05855         {
05856           *__result = *__first1;
05857           ++__first1;
05858           ++__first2;
05859         }
05860       ++__result;
05861     }
05862       return std::copy(__first2, __last2, std::copy(__first1, __last1,
05863                             __result));
05864     }
05865 
05866   /**
05867    *  @brief Return the intersection of two sorted ranges.
05868    *  @ingroup set_algorithms
05869    *  @param  __first1  Start of first range.
05870    *  @param  __last1   End of first range.
05871    *  @param  __first2  Start of second range.
05872    *  @param  __last2   End of second range.
05873    *  @return  End of the output range.
05874    *  @ingroup set_algorithms
05875    *
05876    *  This operation iterates over both ranges, copying elements present in
05877    *  both ranges in order to the output range.  Iterators increment for each
05878    *  range.  When the current element of one range is less than the other,
05879    *  that iterator advances.  If an element is contained in both ranges, the
05880    *  element from the first range is copied and both ranges advance.  The
05881    *  output range may not overlap either input range.
05882   */
05883   template<typename _InputIterator1, typename _InputIterator2,
05884        typename _OutputIterator>
05885     _OutputIterator
05886     set_intersection(_InputIterator1 __first1, _InputIterator1 __last1,
05887              _InputIterator2 __first2, _InputIterator2 __last2,
05888              _OutputIterator __result)
05889     {
05890       typedef typename iterator_traits<_InputIterator1>::value_type
05891     _ValueType1;
05892       typedef typename iterator_traits<_InputIterator2>::value_type
05893     _ValueType2;
05894 
05895       // concept requirements
05896       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
05897       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
05898       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
05899                   _ValueType1>)
05900       __glibcxx_function_requires(_LessThanOpConcept<_ValueType1, _ValueType2>)
05901       __glibcxx_function_requires(_LessThanOpConcept<_ValueType2, _ValueType1>)
05902       __glibcxx_requires_sorted_set(__first1, __last1, __first2);
05903       __glibcxx_requires_sorted_set(__first2, __last2, __first1);
05904 
05905       while (__first1 != __last1 && __first2 != __last2)
05906     if (*__first1 < *__first2)
05907       ++__first1;
05908     else if (*__first2 < *__first1)
05909       ++__first2;
05910     else
05911       {
05912         *__result = *__first1;
05913         ++__first1;
05914         ++__first2;
05915         ++__result;
05916       }
05917       return __result;
05918     }
05919 
05920   /**
05921    *  @brief Return the intersection of two sorted ranges using comparison
05922    *  functor.
05923    *  @ingroup set_algorithms
05924    *  @param  __first1  Start of first range.
05925    *  @param  __last1   End of first range.
05926    *  @param  __first2  Start of second range.
05927    *  @param  __last2   End of second range.
05928    *  @param  __comp    The comparison functor.
05929    *  @return  End of the output range.
05930    *  @ingroup set_algorithms
05931    *
05932    *  This operation iterates over both ranges, copying elements present in
05933    *  both ranges in order to the output range.  Iterators increment for each
05934    *  range.  When the current element of one range is less than the other
05935    *  according to @p __comp, that iterator advances.  If an element is
05936    *  contained in both ranges according to @p __comp, the element from the
05937    *  first range is copied and both ranges advance.  The output range may not
05938    *  overlap either input range.
05939   */
05940   template<typename _InputIterator1, typename _InputIterator2,
05941        typename _OutputIterator, typename _Compare>
05942     _OutputIterator
05943     set_intersection(_InputIterator1 __first1, _InputIterator1 __last1,
05944              _InputIterator2 __first2, _InputIterator2 __last2,
05945              _OutputIterator __result, _Compare __comp)
05946     {
05947       typedef typename iterator_traits<_InputIterator1>::value_type
05948     _ValueType1;
05949       typedef typename iterator_traits<_InputIterator2>::value_type
05950     _ValueType2;
05951 
05952       // concept requirements
05953       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
05954       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
05955       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
05956                   _ValueType1>)
05957       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
05958                   _ValueType1, _ValueType2>)
05959       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
05960                   _ValueType2, _ValueType1>)
05961       __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp);
05962       __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp);
05963 
05964       while (__first1 != __last1 && __first2 != __last2)
05965     if (__comp(*__first1, *__first2))
05966       ++__first1;
05967     else if (__comp(*__first2, *__first1))
05968       ++__first2;
05969     else
05970       {
05971         *__result = *__first1;
05972         ++__first1;
05973         ++__first2;
05974         ++__result;
05975       }
05976       return __result;
05977     }
05978 
05979   /**
05980    *  @brief Return the difference of two sorted ranges.
05981    *  @ingroup set_algorithms
05982    *  @param  __first1  Start of first range.
05983    *  @param  __last1   End of first range.
05984    *  @param  __first2  Start of second range.
05985    *  @param  __last2   End of second range.
05986    *  @return  End of the output range.
05987    *  @ingroup set_algorithms
05988    *
05989    *  This operation iterates over both ranges, copying elements present in
05990    *  the first range but not the second in order to the output range.
05991    *  Iterators increment for each range.  When the current element of the
05992    *  first range is less than the second, that element is copied and the
05993    *  iterator advances.  If the current element of the second range is less,
05994    *  the iterator advances, but no element is copied.  If an element is
05995    *  contained in both ranges, no elements are copied and both ranges
05996    *  advance.  The output range may not overlap either input range.
05997   */
05998   template<typename _InputIterator1, typename _InputIterator2,
05999        typename _OutputIterator>
06000     _OutputIterator
06001     set_difference(_InputIterator1 __first1, _InputIterator1 __last1,
06002            _InputIterator2 __first2, _InputIterator2 __last2,
06003            _OutputIterator __result)
06004     {
06005       typedef typename iterator_traits<_InputIterator1>::value_type
06006     _ValueType1;
06007       typedef typename iterator_traits<_InputIterator2>::value_type
06008     _ValueType2;
06009 
06010       // concept requirements
06011       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
06012       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
06013       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
06014                   _ValueType1>)
06015       __glibcxx_function_requires(_LessThanOpConcept<_ValueType1, _ValueType2>)
06016       __glibcxx_function_requires(_LessThanOpConcept<_ValueType2, _ValueType1>) 
06017       __glibcxx_requires_sorted_set(__first1, __last1, __first2);
06018       __glibcxx_requires_sorted_set(__first2, __last2, __first1);
06019 
06020       while (__first1 != __last1 && __first2 != __last2)
06021     if (*__first1 < *__first2)
06022       {
06023         *__result = *__first1;
06024         ++__first1;
06025         ++__result;
06026       }
06027     else if (*__first2 < *__first1)
06028       ++__first2;
06029     else
06030       {
06031         ++__first1;
06032         ++__first2;
06033       }
06034       return std::copy(__first1, __last1, __result);
06035     }
06036 
06037   /**
06038    *  @brief  Return the difference of two sorted ranges using comparison
06039    *  functor.
06040    *  @ingroup set_algorithms
06041    *  @param  __first1  Start of first range.
06042    *  @param  __last1   End of first range.
06043    *  @param  __first2  Start of second range.
06044    *  @param  __last2   End of second range.
06045    *  @param  __comp    The comparison functor.
06046    *  @return  End of the output range.
06047    *  @ingroup set_algorithms
06048    *
06049    *  This operation iterates over both ranges, copying elements present in
06050    *  the first range but not the second in order to the output range.
06051    *  Iterators increment for each range.  When the current element of the
06052    *  first range is less than the second according to @p __comp, that element
06053    *  is copied and the iterator advances.  If the current element of the
06054    *  second range is less, no element is copied and the iterator advances.
06055    *  If an element is contained in both ranges according to @p __comp, no
06056    *  elements are copied and both ranges advance.  The output range may not
06057    *  overlap either input range.
06058   */
06059   template<typename _InputIterator1, typename _InputIterator2,
06060        typename _OutputIterator, typename _Compare>
06061     _OutputIterator
06062     set_difference(_InputIterator1 __first1, _InputIterator1 __last1,
06063            _InputIterator2 __first2, _InputIterator2 __last2,
06064            _OutputIterator __result, _Compare __comp)
06065     {
06066       typedef typename iterator_traits<_InputIterator1>::value_type
06067     _ValueType1;
06068       typedef typename iterator_traits<_InputIterator2>::value_type
06069     _ValueType2;
06070 
06071       // concept requirements
06072       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
06073       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
06074       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
06075                   _ValueType1>)
06076       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
06077                   _ValueType1, _ValueType2>)
06078       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
06079                   _ValueType2, _ValueType1>)
06080       __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp);
06081       __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp);
06082 
06083       while (__first1 != __last1 && __first2 != __last2)
06084     if (__comp(*__first1, *__first2))
06085       {
06086         *__result = *__first1;
06087         ++__first1;
06088         ++__result;
06089       }
06090     else if (__comp(*__first2, *__first1))
06091       ++__first2;
06092     else
06093       {
06094         ++__first1;
06095         ++__first2;
06096       }
06097       return std::copy(__first1, __last1, __result);
06098     }
06099 
06100   /**
06101    *  @brief  Return the symmetric difference of two sorted ranges.
06102    *  @ingroup set_algorithms
06103    *  @param  __first1  Start of first range.
06104    *  @param  __last1   End of first range.
06105    *  @param  __first2  Start of second range.
06106    *  @param  __last2   End of second range.
06107    *  @return  End of the output range.
06108    *  @ingroup set_algorithms
06109    *
06110    *  This operation iterates over both ranges, copying elements present in
06111    *  one range but not the other in order to the output range.  Iterators
06112    *  increment for each range.  When the current element of one range is less
06113    *  than the other, that element is copied and the iterator advances.  If an
06114    *  element is contained in both ranges, no elements are copied and both
06115    *  ranges advance.  The output range may not overlap either input range.
06116   */
06117   template<typename _InputIterator1, typename _InputIterator2,
06118        typename _OutputIterator>
06119     _OutputIterator
06120     set_symmetric_difference(_InputIterator1 __first1, _InputIterator1 __last1,
06121                  _InputIterator2 __first2, _InputIterator2 __last2,
06122                  _OutputIterator __result)
06123     {
06124       typedef typename iterator_traits<_InputIterator1>::value_type
06125     _ValueType1;
06126       typedef typename iterator_traits<_InputIterator2>::value_type
06127     _ValueType2;
06128 
06129       // concept requirements
06130       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
06131       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
06132       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
06133                   _ValueType1>)
06134       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
06135                   _ValueType2>)
06136       __glibcxx_function_requires(_LessThanOpConcept<_ValueType1, _ValueType2>)
06137       __glibcxx_function_requires(_LessThanOpConcept<_ValueType2, _ValueType1>) 
06138       __glibcxx_requires_sorted_set(__first1, __last1, __first2);
06139       __glibcxx_requires_sorted_set(__first2, __last2, __first1);
06140 
06141       while (__first1 != __last1 && __first2 != __last2)
06142     if (*__first1 < *__first2)
06143       {
06144         *__result = *__first1;
06145         ++__first1;
06146         ++__result;
06147       }
06148     else if (*__first2 < *__first1)
06149       {
06150         *__result = *__first2;
06151         ++__first2;
06152         ++__result;
06153       }
06154     else
06155       {
06156         ++__first1;
06157         ++__first2;
06158       }
06159       return std::copy(__first2, __last2, std::copy(__first1,
06160                             __last1, __result));
06161     }
06162 
06163   /**
06164    *  @brief  Return the symmetric difference of two sorted ranges using
06165    *  comparison functor.
06166    *  @ingroup set_algorithms
06167    *  @param  __first1  Start of first range.
06168    *  @param  __last1   End of first range.
06169    *  @param  __first2  Start of second range.
06170    *  @param  __last2   End of second range.
06171    *  @param  __comp    The comparison functor.
06172    *  @return  End of the output range.
06173    *  @ingroup set_algorithms
06174    *
06175    *  This operation iterates over both ranges, copying elements present in
06176    *  one range but not the other in order to the output range.  Iterators
06177    *  increment for each range.  When the current element of one range is less
06178    *  than the other according to @p comp, that element is copied and the
06179    *  iterator advances.  If an element is contained in both ranges according
06180    *  to @p __comp, no elements are copied and both ranges advance.  The output
06181    *  range may not overlap either input range.
06182   */
06183   template<typename _InputIterator1, typename _InputIterator2,
06184        typename _OutputIterator, typename _Compare>
06185     _OutputIterator
06186     set_symmetric_difference(_InputIterator1 __first1, _InputIterator1 __last1,
06187                  _InputIterator2 __first2, _InputIterator2 __last2,
06188                  _OutputIterator __result,
06189                  _Compare __comp)
06190     {
06191       typedef typename iterator_traits<_InputIterator1>::value_type
06192     _ValueType1;
06193       typedef typename iterator_traits<_InputIterator2>::value_type
06194     _ValueType2;
06195 
06196       // concept requirements
06197       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
06198       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
06199       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
06200                   _ValueType1>)
06201       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
06202                   _ValueType2>)
06203       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
06204                   _ValueType1, _ValueType2>)
06205       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
06206                   _ValueType2, _ValueType1>)
06207       __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp);
06208       __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp);
06209 
06210       while (__first1 != __last1 && __first2 != __last2)
06211     if (__comp(*__first1, *__first2))
06212       {
06213         *__result = *__first1;
06214         ++__first1;
06215         ++__result;
06216       }
06217     else if (__comp(*__first2, *__first1))
06218       {
06219         *__result = *__first2;
06220         ++__first2;
06221         ++__result;
06222       }
06223     else
06224       {
06225         ++__first1;
06226         ++__first2;
06227       }
06228       return std::copy(__first2, __last2, 
06229                std::copy(__first1, __last1, __result));
06230     }
06231 
06232 
06233   /**
06234    *  @brief  Return the minimum element in a range.
06235    *  @ingroup sorting_algorithms
06236    *  @param  __first  Start of range.
06237    *  @param  __last   End of range.
06238    *  @return  Iterator referencing the first instance of the smallest value.
06239   */
06240   template<typename _ForwardIterator>
06241     _ForwardIterator
06242     min_element(_ForwardIterator __first, _ForwardIterator __last)
06243     {
06244       // concept requirements
06245       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
06246       __glibcxx_function_requires(_LessThanComparableConcept<
06247         typename iterator_traits<_ForwardIterator>::value_type>)
06248       __glibcxx_requires_valid_range(__first, __last);
06249 
06250       if (__first == __last)
06251     return __first;
06252       _ForwardIterator __result = __first;
06253       while (++__first != __last)
06254     if (*__first < *__result)
06255       __result = __first;
06256       return __result;
06257     }
06258 
06259   /**
06260    *  @brief  Return the minimum element in a range using comparison functor.
06261    *  @ingroup sorting_algorithms
06262    *  @param  __first  Start of range.
06263    *  @param  __last   End of range.
06264    *  @param  __comp   Comparison functor.
06265    *  @return  Iterator referencing the first instance of the smallest value
06266    *  according to __comp.
06267   */
06268   template<typename _ForwardIterator, typename _Compare>
06269     _ForwardIterator
06270     min_element(_ForwardIterator __first, _ForwardIterator __last,
06271         _Compare __comp)
06272     {
06273       // concept requirements
06274       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
06275       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
06276         typename iterator_traits<_ForwardIterator>::value_type,
06277         typename iterator_traits<_ForwardIterator>::value_type>)
06278       __glibcxx_requires_valid_range(__first, __last);
06279 
06280       if (__first == __last)
06281     return __first;
06282       _ForwardIterator __result = __first;
06283       while (++__first != __last)
06284     if (__comp(*__first, *__result))
06285       __result = __first;
06286       return __result;
06287     }
06288 
06289   /**
06290    *  @brief  Return the maximum element in a range.
06291    *  @ingroup sorting_algorithms
06292    *  @param  __first  Start of range.
06293    *  @param  __last   End of range.
06294    *  @return  Iterator referencing the first instance of the largest value.
06295   */
06296   template<typename _ForwardIterator>
06297     _ForwardIterator
06298     max_element(_ForwardIterator __first, _ForwardIterator __last)
06299     {
06300       // concept requirements
06301       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
06302       __glibcxx_function_requires(_LessThanComparableConcept<
06303         typename iterator_traits<_ForwardIterator>::value_type>)
06304       __glibcxx_requires_valid_range(__first, __last);
06305 
06306       if (__first == __last)
06307     return __first;
06308       _ForwardIterator __result = __first;
06309       while (++__first != __last)
06310     if (*__result < *__first)
06311       __result = __first;
06312       return __result;
06313     }
06314 
06315   /**
06316    *  @brief  Return the maximum element in a range using comparison functor.
06317    *  @ingroup sorting_algorithms
06318    *  @param  __first  Start of range.
06319    *  @param  __last   End of range.
06320    *  @param  __comp   Comparison functor.
06321    *  @return  Iterator referencing the first instance of the largest value
06322    *  according to __comp.
06323   */
06324   template<typename _ForwardIterator, typename _Compare>
06325     _ForwardIterator
06326     max_element(_ForwardIterator __first, _ForwardIterator __last,
06327         _Compare __comp)
06328     {
06329       // concept requirements
06330       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
06331       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
06332         typename iterator_traits<_ForwardIterator>::value_type,
06333         typename iterator_traits<_ForwardIterator>::value_type>)
06334       __glibcxx_requires_valid_range(__first, __last);
06335 
06336       if (__first == __last) return __first;
06337       _ForwardIterator __result = __first;
06338       while (++__first != __last)
06339     if (__comp(*__result, *__first))
06340       __result = __first;
06341       return __result;
06342     }
06343 
06344 _GLIBCXX_END_NAMESPACE_ALGO
06345 } // namespace std
06346 
06347 #endif /* _STL_ALGO_H */