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