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