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