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         *__result1 = _GLIBCXX_MOVE(*__first);
01815         ++__result1;
01816           }
01817         else
01818           {
01819         *__result2 = _GLIBCXX_MOVE(*__first);
01820         ++__result2;
01821           }
01822       _GLIBCXX_MOVE3(__buffer, __result2, __result1);
01823       return __result1;
01824     }
01825       else
01826     {
01827       _ForwardIterator __middle = __first;
01828       std::advance(__middle, __len / 2);
01829       _ForwardIterator __begin =
01830         std::__stable_partition_adaptive(__first, __middle, __pred,
01831                          __len / 2, __buffer,
01832                          __buffer_size);
01833       _ForwardIterator __end =
01834         std::__stable_partition_adaptive(__middle, __last, __pred,
01835                          __len - __len / 2,
01836                          __buffer, __buffer_size);
01837       std::rotate(__begin, __middle, __end);
01838       std::advance(__begin, std::distance(__middle, __end));
01839       return __begin;
01840     }
01841     }
01842 
01843   /**
01844    *  @brief Move elements for which a predicate is true to the beginning
01845    *         of a sequence, preserving relative ordering.
01846    *  @ingroup mutating_algorithms
01847    *  @param  first   A forward iterator.
01848    *  @param  last    A forward iterator.
01849    *  @param  pred    A predicate functor.
01850    *  @return  An iterator @p middle such that @p pred(i) is true for each
01851    *  iterator @p i in the range @p [first,middle) and false for each @p i
01852    *  in the range @p [middle,last).
01853    *
01854    *  Performs the same function as @p partition() with the additional
01855    *  guarantee that the relative ordering of elements in each group is
01856    *  preserved, so any two elements @p x and @p y in the range
01857    *  @p [first,last) such that @p pred(x)==pred(y) will have the same
01858    *  relative ordering after calling @p stable_partition().
01859   */
01860   template<typename _ForwardIterator, typename _Predicate>
01861     _ForwardIterator
01862     stable_partition(_ForwardIterator __first, _ForwardIterator __last,
01863              _Predicate __pred)
01864     {
01865       // concept requirements
01866       __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
01867                   _ForwardIterator>)
01868       __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
01869         typename iterator_traits<_ForwardIterator>::value_type>)
01870       __glibcxx_requires_valid_range(__first, __last);
01871 
01872       if (__first == __last)
01873     return __first;
01874       else
01875     {
01876       typedef typename iterator_traits<_ForwardIterator>::value_type
01877         _ValueType;
01878       typedef typename iterator_traits<_ForwardIterator>::difference_type
01879         _DistanceType;
01880 
01881       _Temporary_buffer<_ForwardIterator, _ValueType> __buf(__first,
01882                                 __last);
01883     if (__buf.size() > 0)
01884       return
01885         std::__stable_partition_adaptive(__first, __last, __pred,
01886                       _DistanceType(__buf.requested_size()),
01887                       __buf.begin(),
01888                       _DistanceType(__buf.size()));
01889     else
01890       return
01891         std::__inplace_stable_partition(__first, __last, __pred,
01892                      _DistanceType(__buf.requested_size()));
01893     }
01894     }
01895 
01896   /// This is a helper function for the sort routines.
01897   template<typename _RandomAccessIterator>
01898     void
01899     __heap_select(_RandomAccessIterator __first,
01900           _RandomAccessIterator __middle,
01901           _RandomAccessIterator __last)
01902     {
01903       std::make_heap(__first, __middle);
01904       for (_RandomAccessIterator __i = __middle; __i < __last; ++__i)
01905     if (*__i < *__first)
01906       std::__pop_heap(__first, __middle, __i);
01907     }
01908 
01909   /// This is a helper function for the sort routines.
01910   template<typename _RandomAccessIterator, typename _Compare>
01911     void
01912     __heap_select(_RandomAccessIterator __first,
01913           _RandomAccessIterator __middle,
01914           _RandomAccessIterator __last, _Compare __comp)
01915     {
01916       std::make_heap(__first, __middle, __comp);
01917       for (_RandomAccessIterator __i = __middle; __i < __last; ++__i)
01918     if (__comp(*__i, *__first))
01919       std::__pop_heap(__first, __middle, __i, __comp);
01920     }
01921 
01922   // partial_sort
01923 
01924   /**
01925    *  @brief Copy the smallest elements of a sequence.
01926    *  @ingroup sorting_algorithms
01927    *  @param  first   An iterator.
01928    *  @param  last    Another iterator.
01929    *  @param  result_first   A random-access iterator.
01930    *  @param  result_last    Another random-access iterator.
01931    *  @return   An iterator indicating the end of the resulting sequence.
01932    *
01933    *  Copies and sorts the smallest N values from the range @p [first,last)
01934    *  to the range beginning at @p result_first, where the number of
01935    *  elements to be copied, @p N, is the smaller of @p (last-first) and
01936    *  @p (result_last-result_first).
01937    *  After the sort if @p i and @j are iterators in the range
01938    *  @p [result_first,result_first+N) such that @i precedes @j then
01939    *  @p *j<*i is false.
01940    *  The value returned is @p result_first+N.
01941   */
01942   template<typename _InputIterator, typename _RandomAccessIterator>
01943     _RandomAccessIterator
01944     partial_sort_copy(_InputIterator __first, _InputIterator __last,
01945               _RandomAccessIterator __result_first,
01946               _RandomAccessIterator __result_last)
01947     {
01948       typedef typename iterator_traits<_InputIterator>::value_type
01949     _InputValueType;
01950       typedef typename iterator_traits<_RandomAccessIterator>::value_type
01951     _OutputValueType;
01952       typedef typename iterator_traits<_RandomAccessIterator>::difference_type
01953     _DistanceType;
01954 
01955       // concept requirements
01956       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
01957       __glibcxx_function_requires(_ConvertibleConcept<_InputValueType,
01958                   _OutputValueType>)
01959       __glibcxx_function_requires(_LessThanOpConcept<_InputValueType,
01960                                      _OutputValueType>)
01961       __glibcxx_function_requires(_LessThanComparableConcept<_OutputValueType>)
01962       __glibcxx_requires_valid_range(__first, __last);
01963       __glibcxx_requires_valid_range(__result_first, __result_last);
01964 
01965       if (__result_first == __result_last)
01966     return __result_last;
01967       _RandomAccessIterator __result_real_last = __result_first;
01968       while(__first != __last && __result_real_last != __result_last)
01969     {
01970       *__result_real_last = *__first;
01971       ++__result_real_last;
01972       ++__first;
01973     }
01974       std::make_heap(__result_first, __result_real_last);
01975       while (__first != __last)
01976     {
01977       if (*__first < *__result_first)
01978         std::__adjust_heap(__result_first, _DistanceType(0),
01979                    _DistanceType(__result_real_last
01980                          - __result_first),
01981                    _InputValueType(*__first));
01982       ++__first;
01983     }
01984       std::sort_heap(__result_first, __result_real_last);
01985       return __result_real_last;
01986     }
01987 
01988   /**
01989    *  @brief Copy the smallest elements of a sequence using a predicate for
01990    *         comparison.
01991    *  @ingroup sorting_algorithms
01992    *  @param  first   An input iterator.
01993    *  @param  last    Another input iterator.
01994    *  @param  result_first   A random-access iterator.
01995    *  @param  result_last    Another random-access iterator.
01996    *  @param  comp    A comparison functor.
01997    *  @return   An iterator indicating the end of the resulting sequence.
01998    *
01999    *  Copies and sorts the smallest N values from the range @p [first,last)
02000    *  to the range beginning at @p result_first, where the number of
02001    *  elements to be copied, @p N, is the smaller of @p (last-first) and
02002    *  @p (result_last-result_first).
02003    *  After the sort if @p i and @j are iterators in the range
02004    *  @p [result_first,result_first+N) such that @i precedes @j then
02005    *  @p comp(*j,*i) is false.
02006    *  The value returned is @p result_first+N.
02007   */
02008   template<typename _InputIterator, typename _RandomAccessIterator, typename _Compare>
02009     _RandomAccessIterator
02010     partial_sort_copy(_InputIterator __first, _InputIterator __last,
02011               _RandomAccessIterator __result_first,
02012               _RandomAccessIterator __result_last,
02013               _Compare __comp)
02014     {
02015       typedef typename iterator_traits<_InputIterator>::value_type
02016     _InputValueType;
02017       typedef typename iterator_traits<_RandomAccessIterator>::value_type
02018     _OutputValueType;
02019       typedef typename iterator_traits<_RandomAccessIterator>::difference_type
02020     _DistanceType;
02021 
02022       // concept requirements
02023       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
02024       __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
02025                   _RandomAccessIterator>)
02026       __glibcxx_function_requires(_ConvertibleConcept<_InputValueType,
02027                   _OutputValueType>)
02028       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
02029                   _InputValueType, _OutputValueType>)
02030       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
02031                   _OutputValueType, _OutputValueType>)
02032       __glibcxx_requires_valid_range(__first, __last);
02033       __glibcxx_requires_valid_range(__result_first, __result_last);
02034 
02035       if (__result_first == __result_last)
02036     return __result_last;
02037       _RandomAccessIterator __result_real_last = __result_first;
02038       while(__first != __last && __result_real_last != __result_last)
02039     {
02040       *__result_real_last = *__first;
02041       ++__result_real_last;
02042       ++__first;
02043     }
02044       std::make_heap(__result_first, __result_real_last, __comp);
02045       while (__first != __last)
02046     {
02047       if (__comp(*__first, *__result_first))
02048         std::__adjust_heap(__result_first, _DistanceType(0),
02049                    _DistanceType(__result_real_last
02050                          - __result_first),
02051                    _InputValueType(*__first),
02052                    __comp);
02053       ++__first;
02054     }
02055       std::sort_heap(__result_first, __result_real_last, __comp);
02056       return __result_real_last;
02057     }
02058 
02059   /// This is a helper function for the sort routine.
02060   template<typename _RandomAccessIterator>
02061     void
02062     __unguarded_linear_insert(_RandomAccessIterator __last)
02063     {
02064       typename iterator_traits<_RandomAccessIterator>::value_type
02065     __val = _GLIBCXX_MOVE(*__last);
02066       _RandomAccessIterator __next = __last;
02067       --__next;
02068       while (__val < *__next)
02069     {
02070       *__last = _GLIBCXX_MOVE(*__next);
02071       __last = __next;
02072       --__next;
02073     }
02074       *__last = _GLIBCXX_MOVE(__val);
02075     }
02076 
02077   /// This is a helper function for the sort routine.
02078   template<typename _RandomAccessIterator, typename _Compare>
02079     void
02080     __unguarded_linear_insert(_RandomAccessIterator __last,
02081                   _Compare __comp)
02082     {
02083       typename iterator_traits<_RandomAccessIterator>::value_type
02084     __val = _GLIBCXX_MOVE(*__last);
02085       _RandomAccessIterator __next = __last;
02086       --__next;
02087       while (__comp(__val, *__next))
02088     {
02089       *__last = _GLIBCXX_MOVE(*__next);
02090       __last = __next;
02091       --__next;
02092     }
02093       *__last = _GLIBCXX_MOVE(__val);
02094     }
02095 
02096   /// This is a helper function for the sort routine.
02097   template<typename _RandomAccessIterator>
02098     void
02099     __insertion_sort(_RandomAccessIterator __first,
02100              _RandomAccessIterator __last)
02101     {
02102       if (__first == __last)
02103     return;
02104 
02105       for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i)
02106     {
02107       if (*__i < *__first)
02108         {
02109           typename iterator_traits<_RandomAccessIterator>::value_type
02110         __val = _GLIBCXX_MOVE(*__i);
02111           _GLIBCXX_MOVE_BACKWARD3(__first, __i, __i + 1);
02112           *__first = _GLIBCXX_MOVE(__val);
02113         }
02114       else
02115         std::__unguarded_linear_insert(__i);
02116     }
02117     }
02118 
02119   /// This is a helper function for the sort routine.
02120   template<typename _RandomAccessIterator, typename _Compare>
02121     void
02122     __insertion_sort(_RandomAccessIterator __first,
02123              _RandomAccessIterator __last, _Compare __comp)
02124     {
02125       if (__first == __last) return;
02126 
02127       for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i)
02128     {
02129       if (__comp(*__i, *__first))
02130         {
02131           typename iterator_traits<_RandomAccessIterator>::value_type
02132         __val = _GLIBCXX_MOVE(*__i);
02133           _GLIBCXX_MOVE_BACKWARD3(__first, __i, __i + 1);
02134           *__first = _GLIBCXX_MOVE(__val);
02135         }
02136       else
02137         std::__unguarded_linear_insert(__i, __comp);
02138     }
02139     }
02140 
02141   /// This is a helper function for the sort routine.
02142   template<typename _RandomAccessIterator>
02143     inline void
02144     __unguarded_insertion_sort(_RandomAccessIterator __first,
02145                    _RandomAccessIterator __last)
02146     {
02147       typedef typename iterator_traits<_RandomAccessIterator>::value_type
02148     _ValueType;
02149 
02150       for (_RandomAccessIterator __i = __first; __i != __last; ++__i)
02151     std::__unguarded_linear_insert(__i);
02152     }
02153 
02154   /// This is a helper function for the sort routine.
02155   template<typename _RandomAccessIterator, typename _Compare>
02156     inline void
02157     __unguarded_insertion_sort(_RandomAccessIterator __first,
02158                    _RandomAccessIterator __last, _Compare __comp)
02159     {
02160       typedef typename iterator_traits<_RandomAccessIterator>::value_type
02161     _ValueType;
02162 
02163       for (_RandomAccessIterator __i = __first; __i != __last; ++__i)
02164     std::__unguarded_linear_insert(__i, __comp);
02165     }
02166 
02167   /**
02168    *  @doctodo
02169    *  This controls some aspect of the sort routines.
02170   */
02171   enum { _S_threshold = 16 };
02172 
02173   /// This is a helper function for the sort routine.
02174   template<typename _RandomAccessIterator>
02175     void
02176     __final_insertion_sort(_RandomAccessIterator __first,
02177                _RandomAccessIterator __last)
02178     {
02179       if (__last - __first > int(_S_threshold))
02180     {
02181       std::__insertion_sort(__first, __first + int(_S_threshold));
02182       std::__unguarded_insertion_sort(__first + int(_S_threshold), __last);
02183     }
02184       else
02185     std::__insertion_sort(__first, __last);
02186     }
02187 
02188   /// This is a helper function for the sort routine.
02189   template<typename _RandomAccessIterator, typename _Compare>
02190     void
02191     __final_insertion_sort(_RandomAccessIterator __first,
02192                _RandomAccessIterator __last, _Compare __comp)
02193     {
02194       if (__last - __first > int(_S_threshold))
02195     {
02196       std::__insertion_sort(__first, __first + int(_S_threshold), __comp);
02197       std::__unguarded_insertion_sort(__first + int(_S_threshold), __last,
02198                       __comp);
02199     }
02200       else
02201     std::__insertion_sort(__first, __last, __comp);
02202     }
02203 
02204   /// This is a helper function...
02205   template<typename _RandomAccessIterator, typename _Tp>
02206     _RandomAccessIterator
02207     __unguarded_partition(_RandomAccessIterator __first,
02208               _RandomAccessIterator __last, const _Tp& __pivot)
02209     {
02210       while (true)
02211     {
02212       while (*__first < __pivot)
02213         ++__first;
02214       --__last;
02215       while (__pivot < *__last)
02216         --__last;
02217       if (!(__first < __last))
02218         return __first;
02219       std::iter_swap(__first, __last);
02220       ++__first;
02221     }
02222     }
02223 
02224   /// This is a helper function...
02225   template<typename _RandomAccessIterator, typename _Tp, typename _Compare>
02226     _RandomAccessIterator
02227     __unguarded_partition(_RandomAccessIterator __first,
02228               _RandomAccessIterator __last,
02229               const _Tp& __pivot, _Compare __comp)
02230     {
02231       while (true)
02232     {
02233       while (__comp(*__first, __pivot))
02234         ++__first;
02235       --__last;
02236       while (__comp(__pivot, *__last))
02237         --__last;
02238       if (!(__first < __last))
02239         return __first;
02240       std::iter_swap(__first, __last);
02241       ++__first;
02242     }
02243     }
02244 
02245   /// This is a helper function...
02246   template<typename _RandomAccessIterator>
02247     inline _RandomAccessIterator
02248     __unguarded_partition_pivot(_RandomAccessIterator __first,
02249                 _RandomAccessIterator __last)
02250     {
02251       _RandomAccessIterator __mid = __first + (__last - __first) / 2;
02252       std::__move_median_first(__first, __mid, (__last - 1));
02253       return std::__unguarded_partition(__first + 1, __last, *__first);
02254     }
02255 
02256 
02257   /// This is a helper function...
02258   template<typename _RandomAccessIterator, typename _Compare>
02259     inline _RandomAccessIterator
02260     __unguarded_partition_pivot(_RandomAccessIterator __first,
02261                 _RandomAccessIterator __last, _Compare __comp)
02262     {
02263       _RandomAccessIterator __mid = __first + (__last - __first) / 2;
02264       std::__move_median_first(__first, __mid, (__last - 1), __comp);
02265       return std::__unguarded_partition(__first + 1, __last, *__first, __comp);
02266     }
02267 
02268   /// This is a helper function for the sort routine.
02269   template<typename _RandomAccessIterator, typename _Size>
02270     void
02271     __introsort_loop(_RandomAccessIterator __first,
02272              _RandomAccessIterator __last,
02273              _Size __depth_limit)
02274     {
02275       while (__last - __first > int(_S_threshold))
02276     {
02277       if (__depth_limit == 0)
02278         {
02279           _GLIBCXX_STD_A::partial_sort(__first, __last, __last);
02280           return;
02281         }
02282       --__depth_limit;
02283       _RandomAccessIterator __cut =
02284         std::__unguarded_partition_pivot(__first, __last);
02285       std::__introsort_loop(__cut, __last, __depth_limit);
02286       __last = __cut;
02287     }
02288     }
02289 
02290   /// This is a helper function for the sort routine.
02291   template<typename _RandomAccessIterator, typename _Size, typename _Compare>
02292     void
02293     __introsort_loop(_RandomAccessIterator __first,
02294              _RandomAccessIterator __last,
02295              _Size __depth_limit, _Compare __comp)
02296     {
02297       while (__last - __first > int(_S_threshold))
02298     {
02299       if (__depth_limit == 0)
02300         {
02301           _GLIBCXX_STD_A::partial_sort(__first, __last, __last, __comp);
02302           return;
02303         }
02304       --__depth_limit;
02305       _RandomAccessIterator __cut =
02306         std::__unguarded_partition_pivot(__first, __last, __comp);
02307       std::__introsort_loop(__cut, __last, __depth_limit, __comp);
02308       __last = __cut;
02309     }
02310     }
02311 
02312   // sort
02313 
02314   template<typename _RandomAccessIterator, typename _Size>
02315     void
02316     __introselect(_RandomAccessIterator __first, _RandomAccessIterator __nth,
02317           _RandomAccessIterator __last, _Size __depth_limit)
02318     {
02319       typedef typename iterator_traits<_RandomAccessIterator>::value_type
02320     _ValueType;
02321 
02322       while (__last - __first > 3)
02323     {
02324       if (__depth_limit == 0)
02325         {
02326           std::__heap_select(__first, __nth + 1, __last);
02327 
02328           // Place the nth largest element in its final position.
02329           std::iter_swap(__first, __nth);
02330           return;
02331         }
02332       --__depth_limit;
02333       _RandomAccessIterator __cut =
02334         std::__unguarded_partition_pivot(__first, __last);
02335       if (__cut <= __nth)
02336         __first = __cut;
02337       else
02338         __last = __cut;
02339     }
02340       std::__insertion_sort(__first, __last);
02341     }
02342 
02343   template<typename _RandomAccessIterator, typename _Size, typename _Compare>
02344     void
02345     __introselect(_RandomAccessIterator __first, _RandomAccessIterator __nth,
02346           _RandomAccessIterator __last, _Size __depth_limit,
02347           _Compare __comp)
02348     {
02349       typedef typename iterator_traits<_RandomAccessIterator>::value_type
02350     _ValueType;
02351 
02352       while (__last - __first > 3)
02353     {
02354       if (__depth_limit == 0)
02355         {
02356           std::__heap_select(__first, __nth + 1, __last, __comp);
02357           // Place the nth largest element in its final position.
02358           std::iter_swap(__first, __nth);
02359           return;
02360         }
02361       --__depth_limit;
02362       _RandomAccessIterator __cut =
02363         std::__unguarded_partition_pivot(__first, __last, __comp);
02364       if (__cut <= __nth)
02365         __first = __cut;
02366       else
02367         __last = __cut;
02368     }
02369       std::__insertion_sort(__first, __last, __comp);
02370     }
02371 
02372   // nth_element
02373 
02374   // lower_bound moved to stl_algobase.h
02375 
02376   /**
02377    *  @brief Finds the first position in which @a val could be inserted
02378    *         without changing the ordering.
02379    *  @ingroup binary_search_algorithms
02380    *  @param  first   An iterator.
02381    *  @param  last    Another iterator.
02382    *  @param  val     The search term.
02383    *  @param  comp    A functor to use for comparisons.
02384    *  @return An iterator pointing to the first element <em>not less
02385    *           than</em> @a val, or end() if every element is less
02386    *           than @a val.
02387    *  @ingroup binary_search_algorithms
02388    *
02389    *  The comparison function should have the same effects on ordering as
02390    *  the function used for the initial sort.
02391   */
02392   template<typename _ForwardIterator, typename _Tp, typename _Compare>
02393     _ForwardIterator
02394     lower_bound(_ForwardIterator __first, _ForwardIterator __last,
02395         const _Tp& __val, _Compare __comp)
02396     {
02397       typedef typename iterator_traits<_ForwardIterator>::value_type
02398     _ValueType;
02399       typedef typename iterator_traits<_ForwardIterator>::difference_type
02400     _DistanceType;
02401 
02402       // concept requirements
02403       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
02404       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
02405                   _ValueType, _Tp>)
02406       __glibcxx_requires_partitioned_lower_pred(__first, __last,
02407                         __val, __comp);
02408 
02409       _DistanceType __len = std::distance(__first, __last);
02410 
02411       while (__len > 0)
02412     {
02413       _DistanceType __half = __len >> 1;
02414       _ForwardIterator __middle = __first;
02415       std::advance(__middle, __half);
02416       if (__comp(*__middle, __val))
02417         {
02418           __first = __middle;
02419           ++__first;
02420           __len = __len - __half - 1;
02421         }
02422       else
02423         __len = __half;
02424     }
02425       return __first;
02426     }
02427 
02428   /**
02429    *  @brief Finds the last position in which @a val could be inserted
02430    *         without changing the ordering.
02431    *  @ingroup binary_search_algorithms
02432    *  @param  first   An iterator.
02433    *  @param  last    Another iterator.
02434    *  @param  val     The search term.
02435    *  @return  An iterator pointing to the first element greater than @a val,
02436    *           or end() if no elements are greater than @a val.
02437    *  @ingroup binary_search_algorithms
02438   */
02439   template<typename _ForwardIterator, typename _Tp>
02440     _ForwardIterator
02441     upper_bound(_ForwardIterator __first, _ForwardIterator __last,
02442         const _Tp& __val)
02443     {
02444       typedef typename iterator_traits<_ForwardIterator>::value_type
02445     _ValueType;
02446       typedef typename iterator_traits<_ForwardIterator>::difference_type
02447     _DistanceType;
02448 
02449       // concept requirements
02450       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
02451       __glibcxx_function_requires(_LessThanOpConcept<_Tp, _ValueType>)
02452       __glibcxx_requires_partitioned_upper(__first, __last, __val);
02453 
02454       _DistanceType __len = std::distance(__first, __last);
02455 
02456       while (__len > 0)
02457     {
02458       _DistanceType __half = __len >> 1;
02459       _ForwardIterator __middle = __first;
02460       std::advance(__middle, __half);
02461       if (__val < *__middle)
02462         __len = __half;
02463       else
02464         {
02465           __first = __middle;
02466           ++__first;
02467           __len = __len - __half - 1;
02468         }
02469     }
02470       return __first;
02471     }
02472 
02473   /**
02474    *  @brief Finds the last position in which @a val could be inserted
02475    *         without changing the ordering.
02476    *  @ingroup binary_search_algorithms
02477    *  @param  first   An iterator.
02478    *  @param  last    Another iterator.
02479    *  @param  val     The search term.
02480    *  @param  comp    A functor to use for comparisons.
02481    *  @return  An iterator pointing to the first element greater than @a val,
02482    *           or end() if no elements are greater than @a val.
02483    *  @ingroup binary_search_algorithms
02484    *
02485    *  The comparison function should have the same effects on ordering as
02486    *  the function used for the initial sort.
02487   */
02488   template<typename _ForwardIterator, typename _Tp, typename _Compare>
02489     _ForwardIterator
02490     upper_bound(_ForwardIterator __first, _ForwardIterator __last,
02491         const _Tp& __val, _Compare __comp)
02492     {
02493       typedef typename iterator_traits<_ForwardIterator>::value_type
02494     _ValueType;
02495       typedef typename iterator_traits<_ForwardIterator>::difference_type
02496     _DistanceType;
02497 
02498       // concept requirements
02499       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
02500       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
02501                   _Tp, _ValueType>)
02502       __glibcxx_requires_partitioned_upper_pred(__first, __last,
02503                         __val, __comp);
02504 
02505       _DistanceType __len = std::distance(__first, __last);
02506 
02507       while (__len > 0)
02508     {
02509       _DistanceType __half = __len >> 1;
02510       _ForwardIterator __middle = __first;
02511       std::advance(__middle, __half);
02512       if (__comp(__val, *__middle))
02513         __len = __half;
02514       else
02515         {
02516           __first = __middle;
02517           ++__first;
02518           __len = __len - __half - 1;
02519         }
02520     }
02521       return __first;
02522     }
02523 
02524   /**
02525    *  @brief Finds the largest subrange in which @a val could be inserted
02526    *         at any place in it without changing the ordering.
02527    *  @ingroup binary_search_algorithms
02528    *  @param  first   An iterator.
02529    *  @param  last    Another iterator.
02530    *  @param  val     The search term.
02531    *  @return  An pair of iterators defining the subrange.
02532    *  @ingroup binary_search_algorithms
02533    *
02534    *  This is equivalent to
02535    *  @code
02536    *    std::make_pair(lower_bound(first, last, val),
02537    *                   upper_bound(first, last, val))
02538    *  @endcode
02539    *  but does not actually call those functions.
02540   */
02541   template<typename _ForwardIterator, typename _Tp>
02542     pair<_ForwardIterator, _ForwardIterator>
02543     equal_range(_ForwardIterator __first, _ForwardIterator __last,
02544         const _Tp& __val)
02545     {
02546       typedef typename iterator_traits<_ForwardIterator>::value_type
02547     _ValueType;
02548       typedef typename iterator_traits<_ForwardIterator>::difference_type
02549     _DistanceType;
02550 
02551       // concept requirements
02552       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
02553       __glibcxx_function_requires(_LessThanOpConcept<_ValueType, _Tp>)
02554       __glibcxx_function_requires(_LessThanOpConcept<_Tp, _ValueType>)  
02555       __glibcxx_requires_partitioned_lower(__first, __last, __val);
02556       __glibcxx_requires_partitioned_upper(__first, __last, __val);      
02557 
02558       _DistanceType __len = std::distance(__first, __last);
02559  
02560       while (__len > 0)
02561     {
02562       _DistanceType __half = __len >> 1;
02563       _ForwardIterator __middle = __first;
02564       std::advance(__middle, __half);
02565       if (*__middle < __val)
02566         {
02567           __first = __middle;
02568           ++__first;
02569           __len = __len - __half - 1;
02570         }
02571       else if (__val < *__middle)
02572         __len = __half;
02573       else
02574         {
02575           _ForwardIterator __left = std::lower_bound(__first, __middle,
02576                              __val);
02577           std::advance(__first, __len);
02578           _ForwardIterator __right = std::upper_bound(++__middle, __first,
02579                               __val);
02580           return pair<_ForwardIterator, _ForwardIterator>(__left, __right);
02581         }
02582     }
02583       return pair<_ForwardIterator, _ForwardIterator>(__first, __first);
02584     }
02585 
02586   /**
02587    *  @brief Finds the largest subrange in which @a val could be inserted
02588    *         at any place in it without changing the ordering.
02589    *  @param  first   An iterator.
02590    *  @param  last    Another iterator.
02591    *  @param  val     The search term.
02592    *  @param  comp    A functor to use for comparisons.
02593    *  @return  An pair of iterators defining the subrange.
02594    *  @ingroup binary_search_algorithms
02595    *
02596    *  This is equivalent to
02597    *  @code
02598    *    std::make_pair(lower_bound(first, last, val, comp),
02599    *                   upper_bound(first, last, val, comp))
02600    *  @endcode
02601    *  but does not actually call those functions.
02602   */
02603   template<typename _ForwardIterator, typename _Tp, typename _Compare>
02604     pair<_ForwardIterator, _ForwardIterator>
02605     equal_range(_ForwardIterator __first, _ForwardIterator __last,
02606         const _Tp& __val, _Compare __comp)
02607     {
02608       typedef typename iterator_traits<_ForwardIterator>::value_type
02609     _ValueType;
02610       typedef typename iterator_traits<_ForwardIterator>::difference_type
02611     _DistanceType;
02612 
02613       // concept requirements
02614       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
02615       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
02616                   _ValueType, _Tp>)
02617       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
02618                   _Tp, _ValueType>)
02619       __glibcxx_requires_partitioned_lower_pred(__first, __last,
02620                         __val, __comp);
02621       __glibcxx_requires_partitioned_upper_pred(__first, __last,
02622                         __val, __comp);
02623 
02624       _DistanceType __len = std::distance(__first, __last);
02625 
02626       while (__len > 0)
02627     {
02628       _DistanceType __half = __len >> 1;
02629       _ForwardIterator __middle = __first;
02630       std::advance(__middle, __half);
02631       if (__comp(*__middle, __val))
02632         {
02633           __first = __middle;
02634           ++__first;
02635           __len = __len - __half - 1;
02636         }
02637       else if (__comp(__val, *__middle))
02638         __len = __half;
02639       else
02640         {
02641           _ForwardIterator __left = std::lower_bound(__first, __middle,
02642                              __val, __comp);
02643           std::advance(__first, __len);
02644           _ForwardIterator __right = std::upper_bound(++__middle, __first,
02645                               __val, __comp);
02646           return pair<_ForwardIterator, _ForwardIterator>(__left, __right);
02647         }
02648     }
02649       return pair<_ForwardIterator, _ForwardIterator>(__first, __first);
02650     }
02651 
02652   /**
02653    *  @brief Determines whether an element exists in a range.
02654    *  @ingroup binary_search_algorithms
02655    *  @param  first   An iterator.
02656    *  @param  last    Another iterator.
02657    *  @param  val     The search term.
02658    *  @return  True if @a val (or its equivalent) is in [@a first,@a last ].
02659    *
02660    *  Note that this does not actually return an iterator to @a val.  For
02661    *  that, use std::find or a container's specialized find member functions.
02662   */
02663   template<typename _ForwardIterator, typename _Tp>
02664     bool
02665     binary_search(_ForwardIterator __first, _ForwardIterator __last,
02666                   const _Tp& __val)
02667     {
02668       typedef typename iterator_traits<_ForwardIterator>::value_type
02669     _ValueType;
02670 
02671       // concept requirements
02672       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
02673       __glibcxx_function_requires(_LessThanOpConcept<_Tp, _ValueType>)
02674       __glibcxx_requires_partitioned_lower(__first, __last, __val);
02675       __glibcxx_requires_partitioned_upper(__first, __last, __val);
02676 
02677       _ForwardIterator __i = std::lower_bound(__first, __last, __val);
02678       return __i != __last && !(__val < *__i);
02679     }
02680 
02681   /**
02682    *  @brief Determines whether an element exists in a range.
02683    *  @ingroup binary_search_algorithms
02684    *  @param  first   An iterator.
02685    *  @param  last    Another iterator.
02686    *  @param  val     The search term.
02687    *  @param  comp    A functor to use for comparisons.
02688    *  @return  True if @a val (or its equivalent) is in [@a first,@a last ].
02689    *
02690    *  Note that this does not actually return an iterator to @a val.  For
02691    *  that, use std::find or a container's specialized find member functions.
02692    *
02693    *  The comparison function should have the same effects on ordering as
02694    *  the function used for the initial sort.
02695   */
02696   template<typename _ForwardIterator, typename _Tp, typename _Compare>
02697     bool
02698     binary_search(_ForwardIterator __first, _ForwardIterator __last,
02699                   const _Tp& __val, _Compare __comp)
02700     {
02701       typedef typename iterator_traits<_ForwardIterator>::value_type
02702     _ValueType;
02703 
02704       // concept requirements
02705       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
02706       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
02707                   _Tp, _ValueType>)
02708       __glibcxx_requires_partitioned_lower_pred(__first, __last,
02709                         __val, __comp);
02710       __glibcxx_requires_partitioned_upper_pred(__first, __last,
02711                         __val, __comp);
02712 
02713       _ForwardIterator __i = std::lower_bound(__first, __last, __val, __comp);
02714       return __i != __last && !bool(__comp(__val, *__i));
02715     }
02716 
02717   // merge
02718 
02719   /// This is a helper function for the merge routines.
02720   template<typename _BidirectionalIterator1, typename _BidirectionalIterator2,
02721        typename _BidirectionalIterator3>
02722     _BidirectionalIterator3
02723     __merge_backward(_BidirectionalIterator1 __first1,
02724              _BidirectionalIterator1 __last1,
02725              _BidirectionalIterator2 __first2,
02726              _BidirectionalIterator2 __last2,
02727              _BidirectionalIterator3 __result)
02728     {
02729       if (__first1 == __last1)
02730     return std::copy_backward(__first2, __last2, __result);
02731       if (__first2 == __last2)
02732     return std::copy_backward(__first1, __last1, __result);
02733       --__last1;
02734       --__last2;
02735       while (true)
02736     {
02737       if (*__last2 < *__last1)
02738         {
02739           *--__result = *__last1;
02740           if (__first1 == __last1)
02741         return std::copy_backward(__first2, ++__last2, __result);
02742           --__last1;
02743         }
02744       else
02745         {
02746           *--__result = *__last2;
02747           if (__first2 == __last2)
02748         return std::copy_backward(__first1, ++__last1, __result);
02749           --__last2;
02750         }
02751     }
02752     }
02753 
02754   /// This is a helper function for the merge routines.
02755   template<typename _BidirectionalIterator1, typename _BidirectionalIterator2,
02756        typename _BidirectionalIterator3, typename _Compare>
02757     _BidirectionalIterator3
02758     __merge_backward(_BidirectionalIterator1 __first1,
02759              _BidirectionalIterator1 __last1,
02760              _BidirectionalIterator2 __first2,
02761              _BidirectionalIterator2 __last2,
02762              _BidirectionalIterator3 __result,
02763              _Compare __comp)
02764     {
02765       if (__first1 == __last1)
02766     return std::copy_backward(__first2, __last2, __result);
02767       if (__first2 == __last2)
02768     return std::copy_backward(__first1, __last1, __result);
02769       --__last1;
02770       --__last2;
02771       while (true)
02772     {
02773       if (__comp(*__last2, *__last1))
02774         {
02775           *--__result = *__last1;
02776           if (__first1 == __last1)
02777         return std::copy_backward(__first2, ++__last2, __result);
02778           --__last1;
02779         }
02780       else
02781         {
02782           *--__result = *__last2;
02783           if (__first2 == __last2)
02784         return std::copy_backward(__first1, ++__last1, __result);
02785           --__last2;
02786         }
02787     }
02788     }
02789 
02790   /// This is a helper function for the merge routines.
02791   template<typename _BidirectionalIterator1, typename _BidirectionalIterator2,
02792        typename _Distance>
02793     _BidirectionalIterator1
02794     __rotate_adaptive(_BidirectionalIterator1 __first,
02795               _BidirectionalIterator1 __middle,
02796               _BidirectionalIterator1 __last,
02797               _Distance __len1, _Distance __len2,
02798               _BidirectionalIterator2 __buffer,
02799               _Distance __buffer_size)
02800     {
02801       _BidirectionalIterator2 __buffer_end;
02802       if (__len1 > __len2 && __len2 <= __buffer_size)
02803     {
02804       __buffer_end = _GLIBCXX_MOVE3(__middle, __last, __buffer);
02805       _GLIBCXX_MOVE_BACKWARD3(__first, __middle, __last);
02806       return _GLIBCXX_MOVE3(__buffer, __buffer_end, __first);
02807     }
02808       else if (__len1 <= __buffer_size)
02809     {
02810       __buffer_end = _GLIBCXX_MOVE3(__first, __middle, __buffer);
02811       _GLIBCXX_MOVE3(__middle, __last, __first);
02812       return _GLIBCXX_MOVE_BACKWARD3(__buffer, __buffer_end, __last);
02813     }
02814       else
02815     {
02816       std::rotate(__first, __middle, __last);
02817       std::advance(__first, std::distance(__middle, __last));
02818       return __first;
02819     }
02820     }
02821 
02822   /// This is a helper function for the merge routines.
02823   template<typename _BidirectionalIterator, typename _Distance,
02824        typename _Pointer>
02825     void
02826     __merge_adaptive(_BidirectionalIterator __first,
02827                      _BidirectionalIterator __middle,
02828              _BidirectionalIterator __last,
02829              _Distance __len1, _Distance __len2,
02830              _Pointer __buffer, _Distance __buffer_size)
02831     {
02832       if (__len1 <= __len2 && __len1 <= __buffer_size)
02833     {
02834       _Pointer __buffer_end = _GLIBCXX_MOVE3(__first, __middle, __buffer);
02835       _GLIBCXX_STD_A::merge(_GLIBCXX_MAKE_MOVE_ITERATOR(__buffer),
02836                 _GLIBCXX_MAKE_MOVE_ITERATOR(__buffer_end),
02837                 _GLIBCXX_MAKE_MOVE_ITERATOR(__middle),
02838                 _GLIBCXX_MAKE_MOVE_ITERATOR(__last),
02839                 __first);
02840     }
02841       else if (__len2 <= __buffer_size)
02842     {
02843       _Pointer __buffer_end = _GLIBCXX_MOVE3(__middle, __last, __buffer);
02844       std::__merge_backward(_GLIBCXX_MAKE_MOVE_ITERATOR(__first),
02845                 _GLIBCXX_MAKE_MOVE_ITERATOR(__middle),
02846                 _GLIBCXX_MAKE_MOVE_ITERATOR(__buffer),
02847                 _GLIBCXX_MAKE_MOVE_ITERATOR(__buffer_end),
02848                 __last);
02849     }
02850       else
02851     {
02852       _BidirectionalIterator __first_cut = __first;
02853       _BidirectionalIterator __second_cut = __middle;
02854       _Distance __len11 = 0;
02855       _Distance __len22 = 0;
02856       if (__len1 > __len2)
02857         {
02858           __len11 = __len1 / 2;
02859           std::advance(__first_cut, __len11);
02860           __second_cut = std::lower_bound(__middle, __last,
02861                           *__first_cut);
02862           __len22 = std::distance(__middle, __second_cut);
02863         }
02864       else
02865         {
02866           __len22 = __len2 / 2;
02867           std::advance(__second_cut, __len22);
02868           __first_cut = std::upper_bound(__first, __middle,
02869                          *__second_cut);
02870           __len11 = std::distance(__first, __first_cut);
02871         }
02872       _BidirectionalIterator __new_middle =
02873         std::__rotate_adaptive(__first_cut, __middle, __second_cut,
02874                    __len1 - __len11, __len22, __buffer,
02875                    __buffer_size);
02876       std::__merge_adaptive(__first, __first_cut, __new_middle, __len11,
02877                 __len22, __buffer, __buffer_size);
02878       std::__merge_adaptive(__new_middle, __second_cut, __last,
02879                 __len1 - __len11,
02880                 __len2 - __len22, __buffer, __buffer_size);
02881     }
02882     }
02883 
02884   /// This is a helper function for the merge routines.
02885   template<typename _BidirectionalIterator, typename _Distance, 
02886        typename _Pointer, typename _Compare>
02887     void
02888     __merge_adaptive(_BidirectionalIterator __first,
02889                      _BidirectionalIterator __middle,
02890              _BidirectionalIterator __last,
02891              _Distance __len1, _Distance __len2,
02892              _Pointer __buffer, _Distance __buffer_size,
02893              _Compare __comp)
02894     {
02895       if (__len1 <= __len2 && __len1 <= __buffer_size)
02896     {
02897       _Pointer __buffer_end = _GLIBCXX_MOVE3(__first, __middle, __buffer);
02898       _GLIBCXX_STD_A::merge(_GLIBCXX_MAKE_MOVE_ITERATOR(__buffer),
02899                 _GLIBCXX_MAKE_MOVE_ITERATOR(__buffer_end),
02900                 _GLIBCXX_MAKE_MOVE_ITERATOR(__middle),
02901                 _GLIBCXX_MAKE_MOVE_ITERATOR(__last),
02902                 __first, __comp);
02903     }
02904       else if (__len2 <= __buffer_size)
02905     {
02906       _Pointer __buffer_end = _GLIBCXX_MOVE3(__middle, __last, __buffer);
02907       std::__merge_backward(_GLIBCXX_MAKE_MOVE_ITERATOR(__first),
02908                 _GLIBCXX_MAKE_MOVE_ITERATOR(__middle),
02909                 _GLIBCXX_MAKE_MOVE_ITERATOR(__buffer),
02910                 _GLIBCXX_MAKE_MOVE_ITERATOR(__buffer_end),
02911                 __last,__comp);
02912     }
02913       else
02914     {
02915       _BidirectionalIterator __first_cut = __first;
02916       _BidirectionalIterator __second_cut = __middle;
02917       _Distance __len11 = 0;
02918       _Distance __len22 = 0;
02919       if (__len1 > __len2)
02920         {
02921           __len11 = __len1 / 2;
02922           std::advance(__first_cut, __len11);
02923           __second_cut = std::lower_bound(__middle, __last, *__first_cut,
02924                           __comp);
02925           __len22 = std::distance(__middle, __second_cut);
02926         }
02927       else
02928         {
02929           __len22 = __len2 / 2;
02930           std::advance(__second_cut, __len22);
02931           __first_cut = std::upper_bound(__first, __middle, *__second_cut,
02932                          __comp);
02933           __len11 = std::distance(__first, __first_cut);
02934         }
02935       _BidirectionalIterator __new_middle =
02936         std::__rotate_adaptive(__first_cut, __middle, __second_cut,
02937                    __len1 - __len11, __len22, __buffer,
02938                    __buffer_size);
02939       std::__merge_adaptive(__first, __first_cut, __new_middle, __len11,
02940                 __len22, __buffer, __buffer_size, __comp);
02941       std::__merge_adaptive(__new_middle, __second_cut, __last,
02942                 __len1 - __len11,
02943                 __len2 - __len22, __buffer,
02944                 __buffer_size, __comp);
02945     }
02946     }
02947 
02948   /// This is a helper function for the merge routines.
02949   template<typename _BidirectionalIterator, typename _Distance>
02950     void
02951     __merge_without_buffer(_BidirectionalIterator __first,
02952                _BidirectionalIterator __middle,
02953                _BidirectionalIterator __last,
02954                _Distance __len1, _Distance __len2)
02955     {
02956       if (__len1 == 0 || __len2 == 0)
02957     return;
02958       if (__len1 + __len2 == 2)
02959     {
02960       if (*__middle < *__first)
02961         std::iter_swap(__first, __middle);
02962       return;
02963     }
02964       _BidirectionalIterator __first_cut = __first;
02965       _BidirectionalIterator __second_cut = __middle;
02966       _Distance __len11 = 0;
02967       _Distance __len22 = 0;
02968       if (__len1 > __len2)
02969     {
02970       __len11 = __len1 / 2;
02971       std::advance(__first_cut, __len11);
02972       __second_cut = std::lower_bound(__middle, __last, *__first_cut);
02973       __len22 = std::distance(__middle, __second_cut);
02974     }
02975       else
02976     {
02977       __len22 = __len2 / 2;
02978       std::advance(__second_cut, __len22);
02979       __first_cut = std::upper_bound(__first, __middle, *__second_cut);
02980       __len11 = std::distance(__first, __first_cut);
02981     }
02982       std::rotate(__first_cut, __middle, __second_cut);
02983       _BidirectionalIterator __new_middle = __first_cut;
02984       std::advance(__new_middle, std::distance(__middle, __second_cut));
02985       std::__merge_without_buffer(__first, __first_cut, __new_middle,
02986                   __len11, __len22);
02987       std::__merge_without_buffer(__new_middle, __second_cut, __last,
02988                   __len1 - __len11, __len2 - __len22);
02989     }
02990 
02991   /// This is a helper function for the merge routines.
02992   template<typename _BidirectionalIterator, typename _Distance,
02993        typename _Compare>
02994     void
02995     __merge_without_buffer(_BidirectionalIterator __first,
02996                            _BidirectionalIterator __middle,
02997                _BidirectionalIterator __last,
02998                _Distance __len1, _Distance __len2,
02999                _Compare __comp)
03000     {
03001       if (__len1 == 0 || __len2 == 0)
03002     return;
03003       if (__len1 + __len2 == 2)
03004     {
03005       if (__comp(*__middle, *__first))
03006         std::iter_swap(__first, __middle);
03007       return;
03008     }
03009       _BidirectionalIterator __first_cut = __first;
03010       _BidirectionalIterator __second_cut = __middle;
03011       _Distance __len11 = 0;
03012       _Distance __len22 = 0;
03013       if (__len1 > __len2)
03014     {
03015       __len11 = __len1 / 2;
03016       std::advance(__first_cut, __len11);
03017       __second_cut = std::lower_bound(__middle, __last, *__first_cut,
03018                       __comp);
03019       __len22 = std::distance(__middle, __second_cut);
03020     }
03021       else
03022     {
03023       __len22 = __len2 / 2;
03024       std::advance(__second_cut, __len22);
03025       __first_cut = std::upper_bound(__first, __middle, *__second_cut,
03026                      __comp);
03027       __len11 = std::distance(__first, __first_cut);
03028     }
03029       std::rotate(__first_cut, __middle, __second_cut);
03030       _BidirectionalIterator __new_middle = __first_cut;
03031       std::advance(__new_middle, std::distance(__middle, __second_cut));
03032       std::__merge_without_buffer(__first, __first_cut, __new_middle,
03033                   __len11, __len22, __comp);
03034       std::__merge_without_buffer(__new_middle, __second_cut, __last,
03035                   __len1 - __len11, __len2 - __len22, __comp);
03036     }
03037 
03038   /**
03039    *  @brief Merges two sorted ranges in place.
03040    *  @ingroup sorting_algorithms
03041    *  @param  first   An iterator.
03042    *  @param  middle  Another iterator.
03043    *  @param  last    Another iterator.
03044    *  @return  Nothing.
03045    *
03046    *  Merges two sorted and consecutive ranges, [first,middle) and
03047    *  [middle,last), and puts the result in [first,last).  The output will
03048    *  be sorted.  The sort is @e stable, that is, for equivalent
03049    *  elements in the two ranges, elements from the first range will always
03050    *  come before elements from the second.
03051    *
03052    *  If enough additional memory is available, this takes (last-first)-1
03053    *  comparisons.  Otherwise an NlogN algorithm is used, where N is
03054    *  distance(first,last).
03055   */
03056   template<typename _BidirectionalIterator>
03057     void
03058     inplace_merge(_BidirectionalIterator __first,
03059           _BidirectionalIterator __middle,
03060           _BidirectionalIterator __last)
03061     {
03062       typedef typename iterator_traits<_BidirectionalIterator>::value_type
03063           _ValueType;
03064       typedef typename iterator_traits<_BidirectionalIterator>::difference_type
03065           _DistanceType;
03066 
03067       // concept requirements
03068       __glibcxx_function_requires(_Mutable_BidirectionalIteratorConcept<
03069         _BidirectionalIterator>)
03070       __glibcxx_function_requires(_LessThanComparableConcept<_ValueType>)
03071       __glibcxx_requires_sorted(__first, __middle);
03072       __glibcxx_requires_sorted(__middle, __last);
03073 
03074       if (__first == __middle || __middle == __last)
03075     return;
03076 
03077       _DistanceType __len1 = std::distance(__first, __middle);
03078       _DistanceType __len2 = std::distance(__middle, __last);
03079 
03080       _Temporary_buffer<_BidirectionalIterator, _ValueType> __buf(__first,
03081                                   __last);
03082       if (__buf.begin() == 0)
03083     std::__merge_without_buffer(__first, __middle, __last, __len1, __len2);
03084       else
03085     std::__merge_adaptive(__first, __middle, __last, __len1, __len2,
03086                   __buf.begin(), _DistanceType(__buf.size()));
03087     }
03088 
03089   /**
03090    *  @brief Merges two sorted ranges in place.
03091    *  @ingroup sorting_algorithms
03092    *  @param  first   An iterator.
03093    *  @param  middle  Another iterator.
03094    *  @param  last    Another iterator.
03095    *  @param  comp    A functor to use for comparisons.
03096    *  @return  Nothing.
03097    *
03098    *  Merges two sorted and consecutive ranges, [first,middle) and
03099    *  [middle,last), and puts the result in [first,last).  The output will
03100    *  be sorted.  The sort is @e stable, that is, for equivalent
03101    *  elements in the two ranges, elements from the first range will always
03102    *  come before elements from the second.
03103    *
03104    *  If enough additional memory is available, this takes (last-first)-1
03105    *  comparisons.  Otherwise an NlogN algorithm is used, where N is
03106    *  distance(first,last).
03107    *
03108    *  The comparison function should have the same effects on ordering as
03109    *  the function used for the initial sort.
03110   */
03111   template<typename _BidirectionalIterator, typename _Compare>
03112     void
03113     inplace_merge(_BidirectionalIterator __first,
03114           _BidirectionalIterator __middle,
03115           _BidirectionalIterator __last,
03116           _Compare __comp)
03117     {
03118       typedef typename iterator_traits<_BidirectionalIterator>::value_type
03119           _ValueType;
03120       typedef typename iterator_traits<_BidirectionalIterator>::difference_type
03121           _DistanceType;
03122 
03123       // concept requirements
03124       __glibcxx_function_requires(_Mutable_BidirectionalIteratorConcept<
03125         _BidirectionalIterator>)
03126       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
03127         _ValueType, _ValueType>)
03128       __glibcxx_requires_sorted_pred(__first, __middle, __comp);
03129       __glibcxx_requires_sorted_pred(__middle, __last, __comp);
03130 
03131       if (__first == __middle || __middle == __last)
03132     return;
03133 
03134       const _DistanceType __len1 = std::distance(__first, __middle);
03135       const _DistanceType __len2 = std::distance(__middle, __last);
03136 
03137       _Temporary_buffer<_BidirectionalIterator, _ValueType> __buf(__first,
03138                                   __last);
03139       if (__buf.begin() == 0)
03140     std::__merge_without_buffer(__first, __middle, __last, __len1,
03141                     __len2, __comp);
03142       else
03143     std::__merge_adaptive(__first, __middle, __last, __len1, __len2,
03144                   __buf.begin(), _DistanceType(__buf.size()),
03145                   __comp);
03146     }
03147 
03148   template<typename _RandomAccessIterator1, typename _RandomAccessIterator2,
03149        typename _Distance>
03150     void
03151     __merge_sort_loop(_RandomAccessIterator1 __first,
03152               _RandomAccessIterator1 __last,
03153               _RandomAccessIterator2 __result,
03154               _Distance __step_size)
03155     {
03156       const _Distance __two_step = 2 * __step_size;
03157 
03158       while (__last - __first >= __two_step)
03159     {
03160       __result = _GLIBCXX_STD_A::merge(
03161             _GLIBCXX_MAKE_MOVE_ITERATOR(__first),
03162             _GLIBCXX_MAKE_MOVE_ITERATOR(__first + __step_size),
03163             _GLIBCXX_MAKE_MOVE_ITERATOR(__first + __step_size),
03164             _GLIBCXX_MAKE_MOVE_ITERATOR(__first + __two_step),
03165             __result);
03166       __first += __two_step;
03167     }
03168 
03169       __step_size = std::min(_Distance(__last - __first), __step_size);
03170       _GLIBCXX_STD_A::merge(_GLIBCXX_MAKE_MOVE_ITERATOR(__first),
03171                 _GLIBCXX_MAKE_MOVE_ITERATOR(__first +
03172                             __step_size),
03173                 _GLIBCXX_MAKE_MOVE_ITERATOR(__first +
03174                             __step_size),
03175                 _GLIBCXX_MAKE_MOVE_ITERATOR(__last),
03176                 __result);
03177     }
03178 
03179   template<typename _RandomAccessIterator1, typename _RandomAccessIterator2,
03180        typename _Distance, typename _Compare>
03181     void
03182     __merge_sort_loop(_RandomAccessIterator1 __first,
03183               _RandomAccessIterator1 __last,
03184               _RandomAccessIterator2 __result, _Distance __step_size,
03185               _Compare __comp)
03186     {
03187       const _Distance __two_step = 2 * __step_size;
03188 
03189       while (__last - __first >= __two_step)
03190     {
03191       __result = _GLIBCXX_STD_A::merge(
03192             _GLIBCXX_MAKE_MOVE_ITERATOR(__first),
03193             _GLIBCXX_MAKE_MOVE_ITERATOR(__first + __step_size),
03194             _GLIBCXX_MAKE_MOVE_ITERATOR(__first + __step_size),
03195             _GLIBCXX_MAKE_MOVE_ITERATOR(__first + __two_step),
03196             __result, __comp);
03197       __first += __two_step;
03198     }
03199       __step_size = std::min(_Distance(__last - __first), __step_size);
03200 
03201       _GLIBCXX_STD_A::merge(_GLIBCXX_MAKE_MOVE_ITERATOR(__first),
03202                 _GLIBCXX_MAKE_MOVE_ITERATOR(__first +
03203                             __step_size),
03204                 _GLIBCXX_MAKE_MOVE_ITERATOR(__first +
03205                             __step_size),
03206                 _GLIBCXX_MAKE_MOVE_ITERATOR(__last),
03207                 __result, __comp);
03208     }
03209 
03210   template<typename _RandomAccessIterator, typename _Distance>
03211     void
03212     __chunk_insertion_sort(_RandomAccessIterator __first,
03213                _RandomAccessIterator __last,
03214                _Distance __chunk_size)
03215     {
03216       while (__last - __first >= __chunk_size)
03217     {
03218       std::__insertion_sort(__first, __first + __chunk_size);
03219       __first += __chunk_size;
03220     }
03221       std::__insertion_sort(__first, __last);
03222     }
03223 
03224   template<typename _RandomAccessIterator, typename _Distance,
03225        typename _Compare>
03226     void
03227     __chunk_insertion_sort(_RandomAccessIterator __first,
03228                _RandomAccessIterator __last,
03229                _Distance __chunk_size, _Compare __comp)
03230     {
03231       while (__last - __first >= __chunk_size)
03232     {
03233       std::__insertion_sort(__first, __first + __chunk_size, __comp);
03234       __first += __chunk_size;
03235     }
03236       std::__insertion_sort(__first, __last, __comp);
03237     }
03238 
03239   enum { _S_chunk_size = 7 };
03240 
03241   template<typename _RandomAccessIterator, typename _Pointer>
03242     void
03243     __merge_sort_with_buffer(_RandomAccessIterator __first,
03244                  _RandomAccessIterator __last,
03245                              _Pointer __buffer)
03246     {
03247       typedef typename iterator_traits<_RandomAccessIterator>::difference_type
03248     _Distance;
03249 
03250       const _Distance __len = __last - __first;
03251       const _Pointer __buffer_last = __buffer + __len;
03252 
03253       _Distance __step_size = _S_chunk_size;
03254       std::__chunk_insertion_sort(__first, __last, __step_size);
03255 
03256       while (__step_size < __len)
03257     {
03258       std::__merge_sort_loop(__first, __last, __buffer, __step_size);
03259       __step_size *= 2;
03260       std::__merge_sort_loop(__buffer, __buffer_last, __first, __step_size);
03261       __step_size *= 2;
03262     }
03263     }
03264 
03265   template<typename _RandomAccessIterator, typename _Pointer, typename _Compare>
03266     void
03267     __merge_sort_with_buffer(_RandomAccessIterator __first,
03268                  _RandomAccessIterator __last,
03269                              _Pointer __buffer, _Compare __comp)
03270     {
03271       typedef typename iterator_traits<_RandomAccessIterator>::difference_type
03272     _Distance;
03273 
03274       const _Distance __len = __last - __first;
03275       const _Pointer __buffer_last = __buffer + __len;
03276 
03277       _Distance __step_size = _S_chunk_size;
03278       std::__chunk_insertion_sort(__first, __last, __step_size, __comp);
03279 
03280       while (__step_size < __len)
03281     {
03282       std::__merge_sort_loop(__first, __last, __buffer,
03283                  __step_size, __comp);
03284       __step_size *= 2;
03285       std::__merge_sort_loop(__buffer, __buffer_last, __first,
03286                  __step_size, __comp);
03287       __step_size *= 2;
03288     }
03289     }
03290 
03291   template<typename _RandomAccessIterator, typename _Pointer,
03292        typename _Distance>
03293     void
03294     __stable_sort_adaptive(_RandomAccessIterator __first,
03295                _RandomAccessIterator __last,
03296                            _Pointer __buffer, _Distance __buffer_size)
03297     {
03298       const _Distance __len = (__last - __first + 1) / 2;
03299       const _RandomAccessIterator __middle = __first + __len;
03300       if (__len > __buffer_size)
03301     {
03302       std::__stable_sort_adaptive(__first, __middle,
03303                       __buffer, __buffer_size);
03304       std::__stable_sort_adaptive(__middle, __last,
03305                       __buffer, __buffer_size);
03306     }
03307       else
03308     {
03309       std::__merge_sort_with_buffer(__first, __middle, __buffer);
03310       std::__merge_sort_with_buffer(__middle, __last, __buffer);
03311     }
03312       std::__merge_adaptive(__first, __middle, __last,
03313                 _Distance(__middle - __first),
03314                 _Distance(__last - __middle),
03315                 __buffer, __buffer_size);
03316     }
03317 
03318   template<typename _RandomAccessIterator, typename _Pointer,
03319        typename _Distance, typename _Compare>
03320     void
03321     __stable_sort_adaptive(_RandomAccessIterator __first,
03322                _RandomAccessIterator __last,
03323                            _Pointer __buffer, _Distance __buffer_size,
03324                            _Compare __comp)
03325     {
03326       const _Distance __len = (__last - __first + 1) / 2;
03327       const _RandomAccessIterator __middle = __first + __len;
03328       if (__len > __buffer_size)
03329     {
03330       std::__stable_sort_adaptive(__first, __middle, __buffer,
03331                       __buffer_size, __comp);
03332       std::__stable_sort_adaptive(__middle, __last, __buffer,
03333                       __buffer_size, __comp);
03334     }
03335       else
03336     {
03337       std::__merge_sort_with_buffer(__first, __middle, __buffer, __comp);
03338       std::__merge_sort_with_buffer(__middle, __last, __buffer, __comp);
03339     }
03340       std::__merge_adaptive(__first, __middle, __last,
03341                 _Distance(__middle - __first),
03342                 _Distance(__last - __middle),
03343                 __buffer, __buffer_size,
03344                 __comp);
03345     }
03346 
03347   /// This is a helper function for the stable sorting routines.
03348   template<typename _RandomAccessIterator>
03349     void
03350     __inplace_stable_sort(_RandomAccessIterator __first,
03351               _RandomAccessIterator __last)
03352     {
03353       if (__last - __first < 15)
03354     {
03355       std::__insertion_sort(__first, __last);
03356       return;
03357     }
03358       _RandomAccessIterator __middle = __first + (__last - __first) / 2;
03359       std::__inplace_stable_sort(__first, __middle);
03360       std::__inplace_stable_sort(__middle, __last);
03361       std::__merge_without_buffer(__first, __middle, __last,
03362                   __middle - __first,
03363                   __last - __middle);
03364     }
03365 
03366   /// This is a helper function for the stable sorting routines.
03367   template<typename _RandomAccessIterator, typename _Compare>
03368     void
03369     __inplace_stable_sort(_RandomAccessIterator __first,
03370               _RandomAccessIterator __last, _Compare __comp)
03371     {
03372       if (__last - __first < 15)
03373     {
03374       std::__insertion_sort(__first, __last, __comp);
03375       return;
03376     }
03377       _RandomAccessIterator __middle = __first + (__last - __first) / 2;
03378       std::__inplace_stable_sort(__first, __middle, __comp);
03379       std::__inplace_stable_sort(__middle, __last, __comp);
03380       std::__merge_without_buffer(__first, __middle, __last,
03381                   __middle - __first,
03382                   __last - __middle,
03383                   __comp);
03384     }
03385 
03386   // stable_sort
03387 
03388   // Set algorithms: includes, set_union, set_intersection, set_difference,
03389   // set_symmetric_difference.  All of these algorithms have the precondition
03390   // that their input ranges are sorted and the postcondition that their output
03391   // ranges are sorted.
03392 
03393   /**
03394    *  @brief Determines whether all elements of a sequence exists in a range.
03395    *  @param  first1  Start of search range.
03396    *  @param  last1   End of search range.
03397    *  @param  first2  Start of sequence
03398    *  @param  last2   End of sequence.
03399    *  @return  True if each element in [first2,last2) is contained in order
03400    *  within [first1,last1).  False otherwise.
03401    *  @ingroup set_algorithms
03402    *
03403    *  This operation expects both [first1,last1) and [first2,last2) to be
03404    *  sorted.  Searches for the presence of each element in [first2,last2)
03405    *  within [first1,last1).  The iterators over each range only move forward,
03406    *  so this is a linear algorithm.  If an element in [first2,last2) is not
03407    *  found before the search iterator reaches @a last2, false is returned.
03408   */
03409   template<typename _InputIterator1, typename _InputIterator2>
03410     bool
03411     includes(_InputIterator1 __first1, _InputIterator1 __last1,
03412          _InputIterator2 __first2, _InputIterator2 __last2)
03413     {
03414       typedef typename iterator_traits<_InputIterator1>::value_type
03415     _ValueType1;
03416       typedef typename iterator_traits<_InputIterator2>::value_type
03417     _ValueType2;
03418 
03419       // concept requirements
03420       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
03421       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
03422       __glibcxx_function_requires(_LessThanOpConcept<_ValueType1, _ValueType2>)
03423       __glibcxx_function_requires(_LessThanOpConcept<_ValueType2, _ValueType1>)
03424       __glibcxx_requires_sorted_set(__first1, __last1, __first2);
03425       __glibcxx_requires_sorted_set(__first2, __last2, __first1);
03426 
03427       while (__first1 != __last1 && __first2 != __last2)
03428     if (*__first2 < *__first1)
03429       return false;
03430     else if(*__first1 < *__first2)
03431       ++__first1;
03432     else
03433       ++__first1, ++__first2;
03434 
03435       return __first2 == __last2;
03436     }
03437 
03438   /**
03439    *  @brief Determines whether all elements of a sequence exists in a range
03440    *  using comparison.
03441    *  @ingroup set_algorithms
03442    *  @param  first1  Start of search range.
03443    *  @param  last1   End of search range.
03444    *  @param  first2  Start of sequence
03445    *  @param  last2   End of sequence.
03446    *  @param  comp    Comparison function to use.
03447    *  @return  True if each element in [first2,last2) is contained in order
03448    *  within [first1,last1) according to comp.  False otherwise.
03449    *  @ingroup set_algorithms
03450    *
03451    *  This operation expects both [first1,last1) and [first2,last2) to be
03452    *  sorted.  Searches for the presence of each element in [first2,last2)
03453    *  within [first1,last1), using comp to decide.  The iterators over each
03454    *  range only move forward, so this is a linear algorithm.  If an element
03455    *  in [first2,last2) is not found before the search iterator reaches @a
03456    *  last2, false is returned.
03457   */
03458   template<typename _InputIterator1, typename _InputIterator2,
03459        typename _Compare>
03460     bool
03461     includes(_InputIterator1 __first1, _InputIterator1 __last1,
03462          _InputIterator2 __first2, _InputIterator2 __last2,
03463          _Compare __comp)
03464     {
03465       typedef typename iterator_traits<_InputIterator1>::value_type
03466     _ValueType1;
03467       typedef typename iterator_traits<_InputIterator2>::value_type
03468     _ValueType2;
03469 
03470       // concept requirements
03471       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
03472       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
03473       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
03474                   _ValueType1, _ValueType2>)
03475       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
03476                   _ValueType2, _ValueType1>)
03477       __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp);
03478       __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp);
03479 
03480       while (__first1 != __last1 && __first2 != __last2)
03481     if (__comp(*__first2, *__first1))
03482       return false;
03483     else if(__comp(*__first1, *__first2))
03484       ++__first1;
03485     else
03486       ++__first1, ++__first2;
03487 
03488       return __first2 == __last2;
03489     }
03490 
03491   // nth_element
03492   // merge
03493   // set_difference
03494   // set_intersection
03495   // set_union
03496   // stable_sort
03497   // set_symmetric_difference
03498   // min_element
03499   // max_element
03500 
03501   /**
03502    *  @brief  Permute range into the next @a dictionary ordering.
03503    *  @ingroup sorting_algorithms
03504    *  @param  first  Start of range.
03505    *  @param  last   End of range.
03506    *  @return  False if wrapped to first permutation, true otherwise.
03507    *
03508    *  Treats all permutations of the range as a set of @a dictionary sorted
03509    *  sequences.  Permutes the current sequence into the next one of this set.
03510    *  Returns true if there are more sequences to generate.  If the sequence
03511    *  is the largest of the set, the smallest is generated and false returned.
03512   */
03513   template<typename _BidirectionalIterator>
03514     bool
03515     next_permutation(_BidirectionalIterator __first,
03516              _BidirectionalIterator __last)
03517     {
03518       // concept requirements
03519       __glibcxx_function_requires(_BidirectionalIteratorConcept<
03520                   _BidirectionalIterator>)
03521       __glibcxx_function_requires(_LessThanComparableConcept<
03522         typename iterator_traits<_BidirectionalIterator>::value_type>)
03523       __glibcxx_requires_valid_range(__first, __last);
03524 
03525       if (__first == __last)
03526     return false;
03527       _BidirectionalIterator __i = __first;
03528       ++__i;
03529       if (__i == __last)
03530     return false;
03531       __i = __last;
03532       --__i;
03533 
03534       for(;;)
03535     {
03536       _BidirectionalIterator __ii = __i;
03537       --__i;
03538       if (*__i < *__ii)
03539         {
03540           _BidirectionalIterator __j = __last;
03541           while (!(*__i < *--__j))
03542         {}
03543           std::iter_swap(__i, __j);
03544           std::reverse(__ii, __last);
03545           return true;
03546         }
03547       if (__i == __first)
03548         {
03549           std::reverse(__first, __last);
03550           return false;
03551         }
03552     }
03553     }
03554 
03555   /**
03556    *  @brief  Permute range into the next @a dictionary ordering using
03557    *          comparison functor.
03558    *  @ingroup sorting_algorithms
03559    *  @param  first  Start of range.
03560    *  @param  last   End of range.
03561    *  @param  comp   A comparison functor.
03562    *  @return  False if wrapped to first permutation, true otherwise.
03563    *
03564    *  Treats all permutations of the range [first,last) as a set of
03565    *  @a dictionary sorted sequences ordered by @a comp.  Permutes the current
03566    *  sequence into the next one of this set.  Returns true if there are more
03567    *  sequences to generate.  If the sequence is the largest of the set, the
03568    *  smallest is generated and false returned.
03569   */
03570   template<typename _BidirectionalIterator, typename _Compare>
03571     bool
03572     next_permutation(_BidirectionalIterator __first,
03573              _BidirectionalIterator __last, _Compare __comp)
03574     {
03575       // concept requirements
03576       __glibcxx_function_requires(_BidirectionalIteratorConcept<
03577                   _BidirectionalIterator>)
03578       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
03579         typename iterator_traits<_BidirectionalIterator>::value_type,
03580         typename iterator_traits<_BidirectionalIterator>::value_type>)
03581       __glibcxx_requires_valid_range(__first, __last);
03582 
03583       if (__first == __last)
03584     return false;
03585       _BidirectionalIterator __i = __first;
03586       ++__i;
03587       if (__i == __last)
03588     return false;
03589       __i = __last;
03590       --__i;
03591 
03592       for(;;)
03593     {
03594       _BidirectionalIterator __ii = __i;
03595       --__i;
03596       if (__comp(*__i, *__ii))
03597         {
03598           _BidirectionalIterator __j = __last;
03599           while (!bool(__comp(*__i, *--__j)))
03600         {}
03601           std::iter_swap(__i, __j);
03602           std::reverse(__ii, __last);
03603           return true;
03604         }
03605       if (__i == __first)
03606         {
03607           std::reverse(__first, __last);
03608           return false;
03609         }
03610     }
03611     }
03612 
03613   /**
03614    *  @brief  Permute range into the previous @a dictionary ordering.
03615    *  @ingroup sorting_algorithms
03616    *  @param  first  Start of range.
03617    *  @param  last   End of range.
03618    *  @return  False if wrapped to last permutation, true otherwise.
03619    *
03620    *  Treats all permutations of the range as a set of @a dictionary sorted
03621    *  sequences.  Permutes the current sequence into the previous one of this
03622    *  set.  Returns true if there are more sequences to generate.  If the
03623    *  sequence is the smallest of the set, the largest is generated and false
03624    *  returned.
03625   */
03626   template<typename _BidirectionalIterator>
03627     bool
03628     prev_permutation(_BidirectionalIterator __first,
03629              _BidirectionalIterator __last)
03630     {
03631       // concept requirements
03632       __glibcxx_function_requires(_BidirectionalIteratorConcept<
03633                   _BidirectionalIterator>)
03634       __glibcxx_function_requires(_LessThanComparableConcept<
03635         typename iterator_traits<_BidirectionalIterator>::value_type>)
03636       __glibcxx_requires_valid_range(__first, __last);
03637 
03638       if (__first == __last)
03639     return false;
03640       _BidirectionalIterator __i = __first;
03641       ++__i;
03642       if (__i == __last)
03643     return false;
03644       __i = __last;
03645       --__i;
03646 
03647       for(;;)
03648     {
03649       _BidirectionalIterator __ii = __i;
03650       --__i;
03651       if (*__ii < *__i)
03652         {
03653           _BidirectionalIterator __j = __last;
03654           while (!(*--__j < *__i))
03655         {}
03656           std::iter_swap(__i, __j);
03657           std::reverse(__ii, __last);
03658           return true;
03659         }
03660       if (__i == __first)
03661         {
03662           std::reverse(__first, __last);
03663           return false;
03664         }
03665     }
03666     }
03667 
03668   /**
03669    *  @brief  Permute range into the previous @a dictionary ordering using
03670    *          comparison functor.
03671    *  @ingroup sorting_algorithms
03672    *  @param  first  Start of range.
03673    *  @param  last   End of range.
03674    *  @param  comp   A comparison functor.
03675    *  @return  False if wrapped to last permutation, true otherwise.
03676    *
03677    *  Treats all permutations of the range [first,last) as a set of
03678    *  @a dictionary sorted sequences ordered by @a comp.  Permutes the current
03679    *  sequence into the previous one of this set.  Returns true if there are
03680    *  more sequences to generate.  If the sequence is the smallest of the set,
03681    *  the largest is generated and false returned.
03682   */
03683   template<typename _BidirectionalIterator, typename _Compare>
03684     bool
03685     prev_permutation(_BidirectionalIterator __first,
03686              _BidirectionalIterator __last, _Compare __comp)
03687     {
03688       // concept requirements
03689       __glibcxx_function_requires(_BidirectionalIteratorConcept<
03690                   _BidirectionalIterator>)
03691       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
03692         typename iterator_traits<_BidirectionalIterator>::value_type,
03693         typename iterator_traits<_BidirectionalIterator>::value_type>)
03694       __glibcxx_requires_valid_range(__first, __last);
03695 
03696       if (__first == __last)
03697     return false;
03698       _BidirectionalIterator __i = __first;
03699       ++__i;
03700       if (__i == __last)
03701     return false;
03702       __i = __last;
03703       --__i;
03704 
03705       for(;;)
03706     {
03707       _BidirectionalIterator __ii = __i;
03708       --__i;
03709       if (__comp(*__ii, *__i))
03710         {
03711           _BidirectionalIterator __j = __last;
03712           while (!bool(__comp(*--__j, *__i)))
03713         {}
03714           std::iter_swap(__i, __j);
03715           std::reverse(__ii, __last);
03716           return true;
03717         }
03718       if (__i == __first)
03719         {
03720           std::reverse(__first, __last);
03721           return false;
03722         }
03723     }
03724     }
03725 
03726   // replace
03727   // replace_if
03728 
03729   /**
03730    *  @brief Copy a sequence, replacing each element of one value with another
03731    *         value.
03732    *  @param  first      An input iterator.
03733    *  @param  last       An input iterator.
03734    *  @param  result     An output iterator.
03735    *  @param  old_value  The value to be replaced.
03736    *  @param  new_value  The replacement value.
03737    *  @return   The end of the output sequence, @p result+(last-first).
03738    *
03739    *  Copies each element in the input range @p [first,last) to the
03740    *  output range @p [result,result+(last-first)) replacing elements
03741    *  equal to @p old_value with @p new_value.
03742   */
03743   template<typename _InputIterator, typename _OutputIterator, typename _Tp>
03744     _OutputIterator
03745     replace_copy(_InputIterator __first, _InputIterator __last,
03746          _OutputIterator __result,
03747          const _Tp& __old_value, const _Tp& __new_value)
03748     {
03749       // concept requirements
03750       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
03751       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
03752         typename iterator_traits<_InputIterator>::value_type>)
03753       __glibcxx_function_requires(_EqualOpConcept<
03754         typename iterator_traits<_InputIterator>::value_type, _Tp>)
03755       __glibcxx_requires_valid_range(__first, __last);
03756 
03757       for (; __first != __last; ++__first, ++__result)
03758     if (*__first == __old_value)
03759       *__result = __new_value;
03760     else
03761       *__result = *__first;
03762       return __result;
03763     }
03764 
03765   /**
03766    *  @brief Copy a sequence, replacing each value for which a predicate
03767    *         returns true with another value.
03768    *  @ingroup mutating_algorithms
03769    *  @param  first      An input iterator.
03770    *  @param  last       An input iterator.
03771    *  @param  result     An output iterator.
03772    *  @param  pred       A predicate.
03773    *  @param  new_value  The replacement value.
03774    *  @return   The end of the output sequence, @p result+(last-first).
03775    *
03776    *  Copies each element in the range @p [first,last) to the range
03777    *  @p [result,result+(last-first)) replacing elements for which
03778    *  @p pred returns true with @p new_value.
03779   */
03780   template<typename _InputIterator, typename _OutputIterator,
03781        typename _Predicate, typename _Tp>
03782     _OutputIterator
03783     replace_copy_if(_InputIterator __first, _InputIterator __last,
03784             _OutputIterator __result,
03785             _Predicate __pred, const _Tp& __new_value)
03786     {
03787       // concept requirements
03788       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
03789       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
03790         typename iterator_traits<_InputIterator>::value_type>)
03791       __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
03792         typename iterator_traits<_InputIterator>::value_type>)
03793       __glibcxx_requires_valid_range(__first, __last);
03794 
03795       for (; __first != __last; ++__first, ++__result)
03796     if (__pred(*__first))
03797       *__result = __new_value;
03798     else
03799       *__result = *__first;
03800       return __result;
03801     }
03802 
03803 #ifdef __GXX_EXPERIMENTAL_CXX0X__
03804   /**
03805    *  @brief  Determines whether the elements of a sequence are sorted.
03806    *  @ingroup sorting_algorithms
03807    *  @param  first   An iterator.
03808    *  @param  last    Another iterator.
03809    *  @return  True if the elements are sorted, false otherwise.
03810   */
03811   template<typename _ForwardIterator>
03812     inline bool
03813     is_sorted(_ForwardIterator __first, _ForwardIterator __last)
03814     { return std::is_sorted_until(__first, __last) == __last; }
03815 
03816   /**
03817    *  @brief  Determines whether the elements of a sequence are sorted
03818    *          according to a comparison functor.
03819    *  @ingroup sorting_algorithms
03820    *  @param  first   An iterator.
03821    *  @param  last    Another iterator.
03822    *  @param  comp    A comparison functor.
03823    *  @return  True if the elements are sorted, false otherwise.
03824   */
03825   template<typename _ForwardIterator, typename _Compare>
03826     inline bool
03827     is_sorted(_ForwardIterator __first, _ForwardIterator __last,
03828           _Compare __comp)
03829     { return std::is_sorted_until(__first, __last, __comp) == __last; }
03830 
03831   /**
03832    *  @brief  Determines the end of a sorted sequence.
03833    *  @ingroup sorting_algorithms
03834    *  @param  first   An iterator.
03835    *  @param  last    Another iterator.
03836    *  @return  An iterator pointing to the last iterator i in [first, last)
03837    *           for which the range [first, i) is sorted.
03838   */
03839   template<typename _ForwardIterator>
03840     _ForwardIterator
03841     is_sorted_until(_ForwardIterator __first, _ForwardIterator __last)
03842     {
03843       // concept requirements
03844       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
03845       __glibcxx_function_requires(_LessThanComparableConcept<
03846         typename iterator_traits<_ForwardIterator>::value_type>)
03847       __glibcxx_requires_valid_range(__first, __last);
03848 
03849       if (__first == __last)
03850     return __last;
03851 
03852       _ForwardIterator __next = __first;
03853       for (++__next; __next != __last; __first = __next, ++__next)
03854     if (*__next < *__first)
03855       return __next;
03856       return __next;
03857     }
03858 
03859   /**
03860    *  @brief  Determines the end of a sorted sequence using comparison functor.
03861    *  @ingroup sorting_algorithms
03862    *  @param  first   An iterator.
03863    *  @param  last    Another iterator.
03864    *  @param  comp    A comparison functor.
03865    *  @return  An iterator pointing to the last iterator i in [first, last)
03866    *           for which the range [first, i) is sorted.
03867   */
03868   template<typename _ForwardIterator, typename _Compare>
03869     _ForwardIterator
03870     is_sorted_until(_ForwardIterator __first, _ForwardIterator __last,
03871             _Compare __comp)
03872     {
03873       // concept requirements
03874       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
03875       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
03876         typename iterator_traits<_ForwardIterator>::value_type,
03877         typename iterator_traits<_ForwardIterator>::value_type>)
03878       __glibcxx_requires_valid_range(__first, __last);
03879 
03880       if (__first == __last)
03881     return __last;
03882 
03883       _ForwardIterator __next = __first;
03884       for (++__next; __next != __last; __first = __next, ++__next)
03885     if (__comp(*__next, *__first))
03886       return __next;
03887       return __next;
03888     }
03889 
03890   /**
03891    *  @brief  Determines min and max at once as an ordered pair.
03892    *  @ingroup sorting_algorithms
03893    *  @param  a  A thing of arbitrary type.
03894    *  @param  b  Another thing of arbitrary type.
03895    *  @return  A pair(b, a) if b is smaller than a, pair(a, b) otherwise.
03896   */
03897   template<typename _Tp>
03898     inline pair<const _Tp&, const _Tp&>
03899     minmax(const _Tp& __a, const _Tp& __b)
03900     {
03901       // concept requirements
03902       __glibcxx_function_requires(_LessThanComparableConcept<_Tp>)
03903 
03904       return __b < __a ? pair<const _Tp&, const _Tp&>(__b, __a)
03905                    : pair<const _Tp&, const _Tp&>(__a, __b);
03906     }
03907 
03908   /**
03909    *  @brief  Determines min and max at once as an ordered pair.
03910    *  @ingroup sorting_algorithms
03911    *  @param  a  A thing of arbitrary type.
03912    *  @param  b  Another thing of arbitrary type.
03913    *  @param  comp  A @link comparison_functor comparison functor@endlink.
03914    *  @return  A pair(b, a) if b is smaller than a, pair(a, b) otherwise.
03915   */
03916   template<typename _Tp, typename _Compare>
03917     inline pair<const _Tp&, const _Tp&>
03918     minmax(const _Tp& __a, const _Tp& __b, _Compare __comp)
03919     {
03920       return __comp(__b, __a) ? pair<const _Tp&, const _Tp&>(__b, __a)
03921                           : pair<const _Tp&, const _Tp&>(__a, __b);
03922     }
03923 
03924   /**
03925    *  @brief  Return a pair of iterators pointing to the minimum and maximum
03926    *          elements in a range.
03927    *  @ingroup sorting_algorithms
03928    *  @param  first  Start of range.
03929    *  @param  last   End of range.
03930    *  @return  make_pair(m, M), where m is the first iterator i in 
03931    *           [first, last) such that no other element in the range is
03932    *           smaller, and where M is the last iterator i in [first, last)
03933    *           such that no other element in the range is larger.
03934   */
03935   template<typename _ForwardIterator>
03936     pair<_ForwardIterator, _ForwardIterator>
03937     minmax_element(_ForwardIterator __first, _ForwardIterator __last)
03938     {
03939       // concept requirements
03940       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
03941       __glibcxx_function_requires(_LessThanComparableConcept<
03942         typename iterator_traits<_ForwardIterator>::value_type>)
03943       __glibcxx_requires_valid_range(__first, __last);
03944 
03945       _ForwardIterator __next = __first;
03946       if (__first == __last
03947       || ++__next == __last)
03948     return std::make_pair(__first, __first);
03949 
03950       _ForwardIterator __min, __max;
03951       if (*__next < *__first)
03952     {
03953       __min = __next;
03954       __max = __first;
03955     }
03956       else
03957     {
03958       __min = __first;
03959       __max = __next;
03960     }
03961 
03962       __first = __next;
03963       ++__first;
03964 
03965       while (__first != __last)
03966     {
03967       __next = __first;
03968       if (++__next == __last)
03969         {
03970           if (*__first < *__min)
03971         __min = __first;
03972           else if (!(*__first < *__max))
03973         __max = __first;
03974           break;
03975         }
03976 
03977       if (*__next < *__first)
03978         {
03979           if (*__next < *__min)
03980         __min = __next;
03981           if (!(*__first < *__max))
03982         __max = __first;
03983         }
03984       else
03985         {
03986           if (*__first < *__min)
03987         __min = __first;
03988           if (!(*__next < *__max))
03989         __max = __next;
03990         }
03991 
03992       __first = __next;
03993       ++__first;
03994     }
03995 
03996       return std::make_pair(__min, __max);
03997     }
03998 
03999   /**
04000    *  @brief  Return a pair of iterators pointing to the minimum and maximum
04001    *          elements in a range.
04002    *  @ingroup sorting_algorithms
04003    *  @param  first  Start of range.
04004    *  @param  last   End of range.
04005    *  @param  comp   Comparison functor.
04006    *  @return  make_pair(m, M), where m is the first iterator i in 
04007    *           [first, last) such that no other element in the range is
04008    *           smaller, and where M is the last iterator i in [first, last)
04009    *           such that no other element in the range is larger.
04010   */
04011   template<typename _ForwardIterator, typename _Compare>
04012     pair<_ForwardIterator, _ForwardIterator>
04013     minmax_element(_ForwardIterator __first, _ForwardIterator __last,
04014            _Compare __comp)
04015     {
04016       // concept requirements
04017       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
04018       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
04019         typename iterator_traits<_ForwardIterator>::value_type,
04020         typename iterator_traits<_ForwardIterator>::value_type>)
04021       __glibcxx_requires_valid_range(__first, __last);
04022 
04023       _ForwardIterator __next = __first;
04024       if (__first == __last
04025       || ++__next == __last)
04026     return std::make_pair(__first, __first);
04027 
04028       _ForwardIterator __min, __max;
04029       if (__comp(*__next, *__first))
04030     {
04031       __min = __next;
04032       __max = __first;
04033     }
04034       else
04035     {
04036       __min = __first;
04037       __max = __next;
04038     }
04039 
04040       __first = __next;
04041       ++__first;
04042 
04043       while (__first != __last)
04044     {
04045       __next = __first;
04046       if (++__next == __last)
04047         {
04048           if (__comp(*__first, *__min))
04049         __min = __first;
04050           else if (!__comp(*__first, *__max))
04051         __max = __first;
04052           break;
04053         }
04054 
04055       if (__comp(*__next, *__first))
04056         {
04057           if (__comp(*__next, *__min))
04058         __min = __next;
04059           if (!__comp(*__first, *__max))
04060         __max = __first;
04061         }
04062       else
04063         {
04064           if (__comp(*__first, *__min))
04065         __min = __first;
04066           if (!__comp(*__next, *__max))
04067         __max = __next;
04068         }
04069 
04070       __first = __next;
04071       ++__first;
04072     }
04073 
04074       return std::make_pair(__min, __max);
04075     }
04076 
04077   // N2722 + DR 915.
04078   template<typename _Tp>
04079     inline _Tp
04080     min(initializer_list<_Tp> __l)
04081     { return *std::min_element(__l.begin(), __l.end()); }
04082 
04083   template<typename _Tp, typename _Compare>
04084     inline _Tp
04085     min(initializer_list<_Tp> __l, _Compare __comp)
04086     { return *std::min_element(__l.begin(), __l.end(), __comp); }
04087 
04088   template<typename _Tp>
04089     inline _Tp
04090     max(initializer_list<_Tp> __l)
04091     { return *std::max_element(__l.begin(), __l.end()); }
04092 
04093   template<typename _Tp, typename _Compare>
04094     inline _Tp
04095     max(initializer_list<_Tp> __l, _Compare __comp)
04096     { return *std::max_element(__l.begin(), __l.end(), __comp); }
04097 
04098   template<typename _Tp>
04099     inline pair<_Tp, _Tp>
04100     minmax(initializer_list<_Tp> __l)
04101     {
04102       pair<const _Tp*, const _Tp*> __p =
04103     std::minmax_element(__l.begin(), __l.end());
04104       return std::make_pair(*__p.first, *__p.second);
04105     }
04106 
04107   template<typename _Tp, typename _Compare>
04108     inline pair<_Tp, _Tp>
04109     minmax(initializer_list<_Tp> __l, _Compare __comp)
04110     {
04111       pair<const _Tp*, const _Tp*> __p =
04112     std::minmax_element(__l.begin(), __l.end(), __comp);
04113       return std::make_pair(*__p.first, *__p.second);
04114     }
04115 
04116   /**
04117    *  @brief  Checks whether a permutaion of the second sequence is equal
04118    *          to the first sequence.
04119    *  @ingroup non_mutating_algorithms
04120    *  @param  first1  Start of first range.
04121    *  @param  last1   End of first range.
04122    *  @param  first2  Start of second range.
04123    *  @return true if there exists a permutation of the elements in the range
04124    *          [first2, first2 + (last1 - first1)), beginning with 
04125    *          ForwardIterator2 begin, such that equal(first1, last1, begin)
04126    *          returns true; otherwise, returns false.
04127   */
04128   template<typename _ForwardIterator1, typename _ForwardIterator2>
04129     bool
04130     is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
04131            _ForwardIterator2 __first2)
04132     {
04133       // Efficiently compare identical prefixes:  O(N) if sequences
04134       // have the same elements in the same order.
04135       for (; __first1 != __last1; ++__first1, ++__first2)
04136     if (!(*__first1 == *__first2))
04137       break;
04138 
04139       if (__first1 == __last1)
04140     return true;
04141 
04142       // Establish __last2 assuming equal ranges by iterating over the
04143       // rest of the list.
04144       _ForwardIterator2 __last2 = __first2;
04145       std::advance(__last2, std::distance(__first1, __last1));
04146       for (_ForwardIterator1 __scan = __first1; __scan != __last1; ++__scan)
04147     {
04148       if (__scan != _GLIBCXX_STD_A::find(__first1, __scan, *__scan))
04149         continue; // We've seen this one before.
04150 
04151       auto __matches = std::count(__first2, __last2, *__scan);
04152       if (0 == __matches
04153           || std::count(__scan, __last1, *__scan) != __matches)
04154         return false;
04155     }
04156       return true;
04157     }
04158 
04159   /**
04160    *  @brief  Checks whether a permutation of the second sequence is equal
04161    *          to the first sequence.
04162    *  @ingroup non_mutating_algorithms
04163    *  @param  first1  Start of first range.
04164    *  @param  last1   End of first range.
04165    *  @param  first2  Start of second range.
04166    *  @param  pred    A binary predicate.
04167    *  @return true if there exists a permutation of the elements in the range
04168    *          [first2, first2 + (last1 - first1)), beginning with 
04169    *          ForwardIterator2 begin, such that equal(first1, last1, begin,
04170    *          pred) returns true; otherwise, returns false.
04171   */
04172   template<typename _ForwardIterator1, typename _ForwardIterator2,
04173        typename _BinaryPredicate>
04174     bool
04175     is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
04176            _ForwardIterator2 __first2, _BinaryPredicate __pred)
04177     {
04178       // Efficiently compare identical prefixes:  O(N) if sequences
04179       // have the same elements in the same order.
04180       for (; __first1 != __last1; ++__first1, ++__first2)
04181     if (!bool(__pred(*__first1, *__first2)))
04182       break;
04183 
04184       if (__first1 == __last1)
04185     return true;
04186 
04187       // Establish __last2 assuming equal ranges by iterating over the
04188       // rest of the list.
04189       _ForwardIterator2 __last2 = __first2;
04190       std::advance(__last2, std::distance(__first1, __last1));
04191       for (_ForwardIterator1 __scan = __first1; __scan != __last1; ++__scan)
04192     {
04193       using std::placeholders::_1;
04194 
04195       if (__scan != _GLIBCXX_STD_A::find_if(__first1, __scan,
04196                         std::bind(__pred, _1, *__scan)))
04197         continue; // We've seen this one before.
04198       
04199       auto __matches = std::count_if(__first2, __last2,
04200                      std::bind(__pred, _1, *__scan));
04201       if (0 == __matches
04202           || std::count_if(__scan, __last1,
04203                    std::bind(__pred, _1, *__scan)) != __matches)
04204         return false;
04205     }
04206       return true;
04207     }
04208 
04209 #ifdef _GLIBCXX_USE_C99_STDINT_TR1
04210   /**
04211    *  @brief Shuffle the elements of a sequence using a uniform random
04212    *         number generator.
04213    *  @ingroup mutating_algorithms
04214    *  @param  first   A forward iterator.
04215    *  @param  last    A forward iterator.
04216    *  @param  g       A UniformRandomNumberGenerator (26.5.1.3).
04217    *  @return  Nothing.
04218    *
04219    *  Reorders the elements in the range @p [first,last) using @p g to
04220    *  provide random numbers.
04221   */
04222   template<typename _RandomAccessIterator,
04223        typename _UniformRandomNumberGenerator>
04224     void
04225     shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last,
04226         _UniformRandomNumberGenerator&& __g)
04227     {
04228       // concept requirements
04229       __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
04230         _RandomAccessIterator>)
04231       __glibcxx_requires_valid_range(__first, __last);
04232 
04233       if (__first == __last)
04234     return;
04235 
04236       typedef typename iterator_traits<_RandomAccessIterator>::difference_type
04237     _DistanceType;
04238 
04239       typedef typename std::make_unsigned<_DistanceType>::type __ud_type;
04240       typedef typename std::uniform_int_distribution<__ud_type> __distr_type;
04241       typedef typename __distr_type::param_type __p_type;
04242       __distr_type __d;
04243 
04244       for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i)
04245     std::iter_swap(__i, __first + __d(__g, __p_type(0, __i - __first)));
04246     }
04247 #endif
04248 
04249 #endif // __GXX_EXPERIMENTAL_CXX0X__
04250 
04251 _GLIBCXX_END_NAMESPACE_VERSION
04252 
04253 _GLIBCXX_BEGIN_NAMESPACE_ALGO
04254 
04255   /**
04256    *  @brief Apply a function to every element of a sequence.
04257    *  @ingroup non_mutating_algorithms
04258    *  @param  first  An input iterator.
04259    *  @param  last   An input iterator.
04260    *  @param  f      A unary function object.
04261    *  @return   @p f (std::move(@p f) in C++0x).
04262    *
04263    *  Applies the function object @p f to each element in the range
04264    *  @p [first,last).  @p f must not modify the order of the sequence.
04265    *  If @p f has a return value it is ignored.
04266   */
04267   template<typename _InputIterator, typename _Function>
04268     _Function
04269     for_each(_InputIterator __first, _InputIterator __last, _Function __f)
04270     {
04271       // concept requirements
04272       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
04273       __glibcxx_requires_valid_range(__first, __last);
04274       for (; __first != __last; ++__first)
04275     __f(*__first);
04276       return _GLIBCXX_MOVE(__f);
04277     }
04278 
04279   /**
04280    *  @brief Find the first occurrence of a value in a sequence.
04281    *  @ingroup non_mutating_algorithms
04282    *  @param  first  An input iterator.
04283    *  @param  last   An input iterator.
04284    *  @param  val    The value to find.
04285    *  @return   The first iterator @c i in the range @p [first,last)
04286    *  such that @c *i == @p val, or @p last if no such iterator exists.
04287   */
04288   template<typename _InputIterator, typename _Tp>
04289     inline _InputIterator
04290     find(_InputIterator __first, _InputIterator __last,
04291      const _Tp& __val)
04292     {
04293       // concept requirements
04294       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
04295       __glibcxx_function_requires(_EqualOpConcept<
04296         typename iterator_traits<_InputIterator>::value_type, _Tp>)
04297       __glibcxx_requires_valid_range(__first, __last);
04298       return std::__find(__first, __last, __val,
04299                  std::__iterator_category(__first));
04300     }
04301 
04302   /**
04303    *  @brief Find the first element in a sequence for which a
04304    *         predicate is true.
04305    *  @ingroup non_mutating_algorithms
04306    *  @param  first  An input iterator.
04307    *  @param  last   An input iterator.
04308    *  @param  pred   A predicate.
04309    *  @return   The first iterator @c i in the range @p [first,last)
04310    *  such that @p pred(*i) is true, or @p last if no such iterator exists.
04311   */
04312   template<typename _InputIterator, typename _Predicate>
04313     inline _InputIterator
04314     find_if(_InputIterator __first, _InputIterator __last,
04315         _Predicate __pred)
04316     {
04317       // concept requirements
04318       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
04319       __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
04320           typename iterator_traits<_InputIterator>::value_type>)
04321       __glibcxx_requires_valid_range(__first, __last);
04322       return std::__find_if(__first, __last, __pred,
04323                 std::__iterator_category(__first));
04324     }
04325 
04326   /**
04327    *  @brief  Find element from a set in a sequence.
04328    *  @ingroup non_mutating_algorithms
04329    *  @param  first1  Start of range to search.
04330    *  @param  last1   End of range to search.
04331    *  @param  first2  Start of match candidates.
04332    *  @param  last2   End of match candidates.
04333    *  @return   The first iterator @c i in the range
04334    *  @p [first1,last1) such that @c *i == @p *(i2) such that i2 is an
04335    *  iterator in [first2,last2), or @p last1 if no such iterator exists.
04336    *
04337    *  Searches the range @p [first1,last1) for an element that is equal to
04338    *  some element in the range [first2,last2).  If found, returns an iterator
04339    *  in the range [first1,last1), otherwise returns @p last1.
04340   */
04341   template<typename _InputIterator, typename _ForwardIterator>
04342     _InputIterator
04343     find_first_of(_InputIterator __first1, _InputIterator __last1,
04344           _ForwardIterator __first2, _ForwardIterator __last2)
04345     {
04346       // concept requirements
04347       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
04348       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
04349       __glibcxx_function_requires(_EqualOpConcept<
04350         typename iterator_traits<_InputIterator>::value_type,
04351         typename iterator_traits<_ForwardIterator>::value_type>)
04352       __glibcxx_requires_valid_range(__first1, __last1);
04353       __glibcxx_requires_valid_range(__first2, __last2);
04354 
04355       for (; __first1 != __last1; ++__first1)
04356     for (_ForwardIterator __iter = __first2; __iter != __last2; ++__iter)
04357       if (*__first1 == *__iter)
04358         return __first1;
04359       return __last1;
04360     }
04361 
04362   /**
04363    *  @brief  Find element from a set in a sequence using a predicate.
04364    *  @ingroup non_mutating_algorithms
04365    *  @param  first1  Start of range to search.
04366    *  @param  last1   End of range to search.
04367    *  @param  first2  Start of match candidates.
04368    *  @param  last2   End of match candidates.
04369    *  @param  comp    Predicate to use.
04370    *  @return   The first iterator @c i in the range
04371    *  @p [first1,last1) such that @c comp(*i, @p *(i2)) is true and i2 is an
04372    *  iterator in [first2,last2), or @p last1 if no such iterator exists.
04373    *
04374 
04375    *  Searches the range @p [first1,last1) for an element that is
04376    *  equal to some element in the range [first2,last2).  If found,
04377    *  returns an iterator in the range [first1,last1), otherwise
04378    *  returns @p last1.
04379   */
04380   template<typename _InputIterator, typename _ForwardIterator,
04381        typename _BinaryPredicate>
04382     _InputIterator
04383     find_first_of(_InputIterator __first1, _InputIterator __last1,
04384           _ForwardIterator __first2, _ForwardIterator __last2,
04385           _BinaryPredicate __comp)
04386     {
04387       // concept requirements
04388       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
04389       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
04390       __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
04391         typename iterator_traits<_InputIterator>::value_type,
04392         typename iterator_traits<_ForwardIterator>::value_type>)
04393       __glibcxx_requires_valid_range(__first1, __last1);
04394       __glibcxx_requires_valid_range(__first2, __last2);
04395 
04396       for (; __first1 != __last1; ++__first1)
04397     for (_ForwardIterator __iter = __first2; __iter != __last2; ++__iter)
04398       if (__comp(*__first1, *__iter))
04399         return __first1;
04400       return __last1;
04401     }
04402 
04403   /**
04404    *  @brief Find two adjacent values in a sequence that are equal.
04405    *  @ingroup non_mutating_algorithms
04406    *  @param  first  A forward iterator.
04407    *  @param  last   A forward iterator.
04408    *  @return   The first iterator @c i such that @c i and @c i+1 are both
04409    *  valid iterators in @p [first,last) and such that @c *i == @c *(i+1),
04410    *  or @p last if no such iterator exists.
04411   */
04412   template<typename _ForwardIterator>
04413     _ForwardIterator
04414     adjacent_find(_ForwardIterator __first, _ForwardIterator __last)
04415     {
04416       // concept requirements
04417       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
04418       __glibcxx_function_requires(_EqualityComparableConcept<
04419         typename iterator_traits<_ForwardIterator>::value_type>)
04420       __glibcxx_requires_valid_range(__first, __last);
04421       if (__first == __last)
04422     return __last;
04423       _ForwardIterator __next = __first;
04424       while(++__next != __last)
04425     {
04426       if (*__first == *__next)
04427         return __first;
04428       __first = __next;
04429     }
04430       return __last;
04431     }
04432 
04433   /**
04434    *  @brief Find two adjacent values in a sequence using a predicate.
04435    *  @ingroup non_mutating_algorithms
04436    *  @param  first         A forward iterator.
04437    *  @param  last          A forward iterator.
04438    *  @param  binary_pred   A binary predicate.
04439    *  @return   The first iterator @c i such that @c i and @c i+1 are both
04440    *  valid iterators in @p [first,last) and such that
04441    *  @p binary_pred(*i,*(i+1)) is true, or @p last if no such iterator
04442    *  exists.
04443   */
04444   template<typename _ForwardIterator, typename _BinaryPredicate>
04445     _ForwardIterator
04446     adjacent_find(_ForwardIterator __first, _ForwardIterator __last,
04447           _BinaryPredicate __binary_pred)
04448     {
04449       // concept requirements
04450       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
04451       __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
04452         typename iterator_traits<_ForwardIterator>::value_type,
04453         typename iterator_traits<_ForwardIterator>::value_type>)
04454       __glibcxx_requires_valid_range(__first, __last);
04455       if (__first == __last)
04456     return __last;
04457       _ForwardIterator __next = __first;
04458       while(++__next != __last)
04459     {
04460       if (__binary_pred(*__first, *__next))
04461         return __first;
04462       __first = __next;
04463     }
04464       return __last;
04465     }
04466 
04467   /**
04468    *  @brief Count the number of copies of a value in a sequence.
04469    *  @ingroup non_mutating_algorithms
04470    *  @param  first  An input iterator.
04471    *  @param  last   An input iterator.
04472    *  @param  value  The value to be counted.
04473    *  @return   The number of iterators @c i in the range @p [first,last)
04474    *  for which @c *i == @p value
04475   */
04476   template<typename _InputIterator, typename _Tp>
04477     typename iterator_traits<_InputIterator>::difference_type
04478     count(_InputIterator __first, _InputIterator __last, const _Tp& __value)
04479     {
04480       // concept requirements
04481       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
04482       __glibcxx_function_requires(_EqualOpConcept<
04483     typename iterator_traits<_InputIterator>::value_type, _Tp>)
04484       __glibcxx_requires_valid_range(__first, __last);
04485       typename iterator_traits<_InputIterator>::difference_type __n = 0;
04486       for (; __first != __last; ++__first)
04487     if (*__first == __value)
04488       ++__n;
04489       return __n;
04490     }
04491 
04492   /**
04493    *  @brief Count the elements of a sequence for which a predicate is true.
04494    *  @ingroup non_mutating_algorithms
04495    *  @param  first  An input iterator.
04496    *  @param  last   An input iterator.
04497    *  @param  pred   A predicate.
04498    *  @return   The number of iterators @c i in the range @p [first,last)
04499    *  for which @p pred(*i) is true.
04500   */
04501   template<typename _InputIterator, typename _Predicate>
04502     typename iterator_traits<_InputIterator>::difference_type
04503     count_if(_InputIterator __first, _InputIterator __last, _Predicate __pred)
04504     {
04505       // concept requirements
04506       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
04507       __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
04508         typename iterator_traits<_InputIterator>::value_type>)
04509       __glibcxx_requires_valid_range(__first, __last);
04510       typename iterator_traits<_InputIterator>::difference_type __n = 0;
04511       for (; __first != __last; ++__first)
04512     if (__pred(*__first))
04513       ++__n;
04514       return __n;
04515     }
04516 
04517   /**
04518    *  @brief Search a sequence for a matching sub-sequence.
04519    *  @ingroup non_mutating_algorithms
04520    *  @param  first1  A forward iterator.
04521    *  @param  last1   A forward iterator.
04522    *  @param  first2  A forward iterator.
04523    *  @param  last2   A forward iterator.
04524    *  @return   The first iterator @c i in the range
04525    *  @p [first1,last1-(last2-first2)) such that @c *(i+N) == @p *(first2+N)
04526    *  for each @c N in the range @p [0,last2-first2), or @p last1 if no
04527    *  such iterator exists.
04528    *
04529    *  Searches the range @p [first1,last1) for a sub-sequence that compares
04530    *  equal value-by-value with the sequence given by @p [first2,last2) and
04531    *  returns an iterator to the first element of the sub-sequence, or
04532    *  @p last1 if the sub-sequence is not found.
04533    *
04534    *  Because the sub-sequence must lie completely within the range
04535    *  @p [first1,last1) it must start at a position less than
04536    *  @p last1-(last2-first2) where @p last2-first2 is the length of the
04537    *  sub-sequence.
04538    *  This means that the returned iterator @c i will be in the range
04539    *  @p [first1,last1-(last2-first2))
04540   */
04541   template<typename _ForwardIterator1, typename _ForwardIterator2>
04542     _ForwardIterator1
04543     search(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
04544        _ForwardIterator2 __first2, _ForwardIterator2 __last2)
04545     {
04546       // concept requirements
04547       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator1>)
04548       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator2>)
04549       __glibcxx_function_requires(_EqualOpConcept<
04550         typename iterator_traits<_ForwardIterator1>::value_type,
04551         typename iterator_traits<_ForwardIterator2>::value_type>)
04552       __glibcxx_requires_valid_range(__first1, __last1);
04553       __glibcxx_requires_valid_range(__first2, __last2);
04554 
04555       // Test for empty ranges
04556       if (__first1 == __last1 || __first2 == __last2)
04557     return __first1;
04558 
04559       // Test for a pattern of length 1.
04560       _ForwardIterator2 __p1(__first2);
04561       if (++__p1 == __last2)
04562     return _GLIBCXX_STD_A::find(__first1, __last1, *__first2);
04563 
04564       // General case.
04565       _ForwardIterator2 __p;
04566       _ForwardIterator1 __current = __first1;
04567 
04568       for (;;)
04569     {
04570       __first1 = _GLIBCXX_STD_A::find(__first1, __last1, *__first2);
04571       if (__first1 == __last1)
04572         return __last1;
04573 
04574       __p = __p1;
04575       __current = __first1;
04576       if (++__current == __last1)
04577         return __last1;
04578 
04579       while (*__current == *__p)
04580         {
04581           if (++__p == __last2)
04582         return __first1;
04583           if (++__current == __last1)
04584         return __last1;
04585         }
04586       ++__first1;
04587     }
04588       return __first1;
04589     }
04590 
04591   /**
04592    *  @brief Search a sequence for a matching sub-sequence using a predicate.
04593    *  @ingroup non_mutating_algorithms
04594    *  @param  first1     A forward iterator.
04595    *  @param  last1      A forward iterator.
04596    *  @param  first2     A forward iterator.
04597    *  @param  last2      A forward iterator.
04598    *  @param  predicate  A binary predicate.
04599    *  @return   The first iterator @c i in the range
04600    *  @p [first1,last1-(last2-first2)) such that
04601    *  @p predicate(*(i+N),*(first2+N)) is true for each @c N in the range
04602    *  @p [0,last2-first2), or @p last1 if no such iterator exists.
04603    *
04604    *  Searches the range @p [first1,last1) for a sub-sequence that compares
04605    *  equal value-by-value with the sequence given by @p [first2,last2),
04606    *  using @p predicate to determine equality, and returns an iterator
04607    *  to the first element of the sub-sequence, or @p last1 if no such
04608    *  iterator exists.
04609    *
04610    *  @see search(_ForwardIter1, _ForwardIter1, _ForwardIter2, _ForwardIter2)
04611   */
04612   template<typename _ForwardIterator1, typename _ForwardIterator2,
04613        typename _BinaryPredicate>
04614     _ForwardIterator1
04615     search(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
04616        _ForwardIterator2 __first2, _ForwardIterator2 __last2,
04617        _BinaryPredicate  __predicate)
04618     {
04619       // concept requirements
04620       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator1>)
04621       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator2>)
04622       __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
04623         typename iterator_traits<_ForwardIterator1>::value_type,
04624         typename iterator_traits<_ForwardIterator2>::value_type>)
04625       __glibcxx_requires_valid_range(__first1, __last1);
04626       __glibcxx_requires_valid_range(__first2, __last2);
04627 
04628       // Test for empty ranges
04629       if (__first1 == __last1 || __first2 == __last2)
04630     return __first1;
04631 
04632       // Test for a pattern of length 1.
04633       _ForwardIterator2 __p1(__first2);
04634       if (++__p1 == __last2)
04635     {
04636       while (__first1 != __last1
04637          && !bool(__predicate(*__first1, *__first2)))
04638         ++__first1;
04639       return __first1;
04640     }
04641 
04642       // General case.
04643       _ForwardIterator2 __p;
04644       _ForwardIterator1 __current = __first1;
04645 
04646       for (;;)
04647     {
04648       while (__first1 != __last1
04649          && !bool(__predicate(*__first1, *__first2)))
04650         ++__first1;
04651       if (__first1 == __last1)
04652         return __last1;
04653 
04654       __p = __p1;
04655       __current = __first1;
04656       if (++__current == __last1)
04657         return __last1;
04658 
04659       while (__predicate(*__current, *__p))
04660         {
04661           if (++__p == __last2)
04662         return __first1;
04663           if (++__current == __last1)
04664         return __last1;
04665         }
04666       ++__first1;
04667     }
04668       return __first1;
04669     }
04670 
04671 
04672   /**
04673    *  @brief Search a sequence for a number of consecutive values.
04674    *  @ingroup non_mutating_algorithms
04675    *  @param  first  A forward iterator.
04676    *  @param  last   A forward iterator.
04677    *  @param  count  The number of consecutive values.
04678    *  @param  val    The value to find.
04679    *  @return   The first iterator @c i in the range @p [first,last-count)
04680    *  such that @c *(i+N) == @p val for each @c N in the range @p [0,count),
04681    *  or @p last if no such iterator exists.
04682    *
04683    *  Searches the range @p [first,last) for @p count consecutive elements
04684    *  equal to @p val.
04685   */
04686   template<typename _ForwardIterator, typename _Integer, typename _Tp>
04687     _ForwardIterator
04688     search_n(_ForwardIterator __first, _ForwardIterator __last,
04689          _Integer __count, const _Tp& __val)
04690     {
04691       // concept requirements
04692       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
04693       __glibcxx_function_requires(_EqualOpConcept<
04694     typename iterator_traits<_ForwardIterator>::value_type, _Tp>)
04695       __glibcxx_requires_valid_range(__first, __last);
04696 
04697       if (__count <= 0)
04698     return __first;
04699       if (__count == 1)
04700     return _GLIBCXX_STD_A::find(__first, __last, __val);
04701       return std::__search_n(__first, __last, __count, __val,
04702                  std::__iterator_category(__first));
04703     }
04704 
04705 
04706   /**
04707    *  @brief Search a sequence for a number of consecutive values using a
04708    *         predicate.
04709    *  @ingroup non_mutating_algorithms
04710    *  @param  first        A forward iterator.
04711    *  @param  last         A forward iterator.
04712    *  @param  count        The number of consecutive values.
04713    *  @param  val          The value to find.
04714    *  @param  binary_pred  A binary predicate.
04715    *  @return   The first iterator @c i in the range @p [first,last-count)
04716    *  such that @p binary_pred(*(i+N),val) is true for each @c N in the
04717    *  range @p [0,count), or @p last if no such iterator exists.
04718    *
04719    *  Searches the range @p [first,last) for @p count consecutive elements
04720    *  for which the predicate returns true.
04721   */
04722   template<typename _ForwardIterator, typename _Integer, typename _Tp,
04723            typename _BinaryPredicate>
04724     _ForwardIterator
04725     search_n(_ForwardIterator __first, _ForwardIterator __last,
04726          _Integer __count, const _Tp& __val,
04727          _BinaryPredicate __binary_pred)
04728     {
04729       // concept requirements
04730       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
04731       __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
04732         typename iterator_traits<_ForwardIterator>::value_type, _Tp>)
04733       __glibcxx_requires_valid_range(__first, __last);
04734 
04735       if (__count <= 0)
04736     return __first;
04737       if (__count == 1)
04738     {
04739       while (__first != __last && !bool(__binary_pred(*__first, __val)))
04740         ++__first;
04741       return __first;
04742     }
04743       return std::__search_n(__first, __last, __count, __val, __binary_pred,
04744                  std::__iterator_category(__first));
04745     }
04746 
04747 
04748   /**
04749    *  @brief Perform an operation on a sequence.
04750    *  @ingroup mutating_algorithms
04751    *  @param  first     An input iterator.
04752    *  @param  last      An input iterator.
04753    *  @param  result    An output iterator.
04754    *  @param  unary_op  A unary operator.
04755    *  @return   An output iterator equal to @p result+(last-first).
04756    *
04757    *  Applies the operator to each element in the input range and assigns
04758    *  the results to successive elements of the output sequence.
04759    *  Evaluates @p *(result+N)=unary_op(*(first+N)) for each @c N in the
04760    *  range @p [0,last-first).
04761    *
04762    *  @p unary_op must not alter its argument.
04763   */
04764   template<typename _InputIterator, typename _OutputIterator,
04765        typename _UnaryOperation>
04766     _OutputIterator
04767     transform(_InputIterator __first, _InputIterator __last,
04768           _OutputIterator __result, _UnaryOperation __unary_op)
04769     {
04770       // concept requirements
04771       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
04772       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
04773             // "the type returned by a _UnaryOperation"
04774             __typeof__(__unary_op(*__first))>)
04775       __glibcxx_requires_valid_range(__first, __last);
04776 
04777       for (; __first != __last; ++__first, ++__result)
04778     *__result = __unary_op(*__first);
04779       return __result;
04780     }
04781 
04782   /**
04783    *  @brief Perform an operation on corresponding elements of two sequences.
04784    *  @ingroup mutating_algorithms
04785    *  @param  first1     An input iterator.
04786    *  @param  last1      An input iterator.
04787    *  @param  first2     An input iterator.
04788    *  @param  result     An output iterator.
04789    *  @param  binary_op  A binary operator.
04790    *  @return   An output iterator equal to @p result+(last-first).
04791    *
04792    *  Applies the operator to the corresponding elements in the two
04793    *  input ranges and assigns the results to successive elements of the
04794    *  output sequence.
04795    *  Evaluates @p *(result+N)=binary_op(*(first1+N),*(first2+N)) for each
04796    *  @c N in the range @p [0,last1-first1).
04797    *
04798    *  @p binary_op must not alter either of its arguments.
04799   */
04800   template<typename _InputIterator1, typename _InputIterator2,
04801        typename _OutputIterator, typename _BinaryOperation>
04802     _OutputIterator
04803     transform(_InputIterator1 __first1, _InputIterator1 __last1,
04804           _InputIterator2 __first2, _OutputIterator __result,
04805           _BinaryOperation __binary_op)
04806     {
04807       // concept requirements
04808       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
04809       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
04810       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
04811             // "the type returned by a _BinaryOperation"
04812             __typeof__(__binary_op(*__first1,*__first2))>)
04813       __glibcxx_requires_valid_range(__first1, __last1);
04814 
04815       for (; __first1 != __last1; ++__first1, ++__first2, ++__result)
04816     *__result = __binary_op(*__first1, *__first2);
04817       return __result;
04818     }
04819 
04820   /**
04821    *  @brief Replace each occurrence of one value in a sequence with another
04822    *         value.
04823    *  @ingroup mutating_algorithms
04824    *  @param  first      A forward iterator.
04825    *  @param  last       A forward iterator.
04826    *  @param  old_value  The value to be replaced.
04827    *  @param  new_value  The replacement value.
04828    *  @return   replace() returns no value.
04829    *
04830    *  For each iterator @c i in the range @p [first,last) if @c *i ==
04831    *  @p old_value then the assignment @c *i = @p new_value is performed.
04832   */
04833   template<typename _ForwardIterator, typename _Tp>
04834     void
04835     replace(_ForwardIterator __first, _ForwardIterator __last,
04836         const _Tp& __old_value, const _Tp& __new_value)
04837     {
04838       // concept requirements
04839       __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
04840                   _ForwardIterator>)
04841       __glibcxx_function_requires(_EqualOpConcept<
04842         typename iterator_traits<_ForwardIterator>::value_type, _Tp>)
04843       __glibcxx_function_requires(_ConvertibleConcept<_Tp,
04844         typename iterator_traits<_ForwardIterator>::value_type>)
04845       __glibcxx_requires_valid_range(__first, __last);
04846 
04847       for (; __first != __last; ++__first)
04848     if (*__first == __old_value)
04849       *__first = __new_value;
04850     }
04851 
04852   /**
04853    *  @brief Replace each value in a sequence for which a predicate returns
04854    *         true with another value.
04855    *  @ingroup mutating_algorithms
04856    *  @param  first      A forward iterator.
04857    *  @param  last       A forward iterator.
04858    *  @param  pred       A predicate.
04859    *  @param  new_value  The replacement value.
04860    *  @return   replace_if() returns no value.
04861    *
04862    *  For each iterator @c i in the range @p [first,last) if @p pred(*i)
04863    *  is true then the assignment @c *i = @p new_value is performed.
04864   */
04865   template<typename _ForwardIterator, typename _Predicate, typename _Tp>
04866     void
04867     replace_if(_ForwardIterator __first, _ForwardIterator __last,
04868            _Predicate __pred, const _Tp& __new_value)
04869     {
04870       // concept requirements
04871       __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
04872                   _ForwardIterator>)
04873       __glibcxx_function_requires(_ConvertibleConcept<_Tp,
04874         typename iterator_traits<_ForwardIterator>::value_type>)
04875       __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
04876         typename iterator_traits<_ForwardIterator>::value_type>)
04877       __glibcxx_requires_valid_range(__first, __last);
04878 
04879       for (; __first != __last; ++__first)
04880     if (__pred(*__first))
04881       *__first = __new_value;
04882     }
04883 
04884   /**
04885    *  @brief Assign the result of a function object to each value in a
04886    *         sequence.
04887    *  @ingroup mutating_algorithms
04888    *  @param  first  A forward iterator.
04889    *  @param  last   A forward iterator.
04890    *  @param  gen    A function object taking no arguments and returning
04891    *                 std::iterator_traits<_ForwardIterator>::value_type
04892    *  @return   generate() returns no value.
04893    *
04894    *  Performs the assignment @c *i = @p gen() for each @c i in the range
04895    *  @p [first,last).
04896   */
04897   template<typename _ForwardIterator, typename _Generator>
04898     void
04899     generate(_ForwardIterator __first, _ForwardIterator __last,
04900          _Generator __gen)
04901     {
04902       // concept requirements
04903       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
04904       __glibcxx_function_requires(_GeneratorConcept<_Generator,
04905         typename iterator_traits<_ForwardIterator>::value_type>)
04906       __glibcxx_requires_valid_range(__first, __last);
04907 
04908       for (; __first != __last; ++__first)
04909     *__first = __gen();
04910     }
04911 
04912   /**
04913    *  @brief Assign the result of a function object to each value in a
04914    *         sequence.
04915    *  @ingroup mutating_algorithms
04916    *  @param  first  A forward iterator.
04917    *  @param  n      The length of the sequence.
04918    *  @param  gen    A function object taking no arguments and returning
04919    *                 std::iterator_traits<_ForwardIterator>::value_type
04920    *  @return   The end of the sequence, @p first+n
04921    *
04922    *  Performs the assignment @c *i = @p gen() for each @c i in the range
04923    *  @p [first,first+n).
04924    *
04925    *  _GLIBCXX_RESOLVE_LIB_DEFECTS
04926    *  DR 865. More algorithms that throw away information
04927   */
04928   template<typename _OutputIterator, typename _Size, typename _Generator>
04929     _OutputIterator
04930     generate_n(_OutputIterator __first, _Size __n, _Generator __gen)
04931     {
04932       // concept requirements
04933       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
04934             // "the type returned by a _Generator"
04935             __typeof__(__gen())>)
04936 
04937       for (__decltype(__n + 0) __niter = __n;
04938        __niter > 0; --__niter, ++__first)
04939     *__first = __gen();
04940       return __first;
04941     }
04942 
04943 
04944   /**
04945    *  @brief Copy a sequence, removing consecutive duplicate values.
04946    *  @ingroup mutating_algorithms
04947    *  @param  first   An input iterator.
04948    *  @param  last    An input iterator.
04949    *  @param  result  An output iterator.
04950    *  @return   An iterator designating the end of the resulting sequence.
04951    *
04952    *  Copies each element in the range @p [first,last) to the range
04953    *  beginning at @p result, except that only the first element is copied
04954    *  from groups of consecutive elements that compare equal.
04955    *  unique_copy() is stable, so the relative order of elements that are
04956    *  copied is unchanged.
04957    *
04958    *  _GLIBCXX_RESOLVE_LIB_DEFECTS
04959    *  DR 241. Does unique_copy() require CopyConstructible and Assignable?
04960    *  
04961    *  _GLIBCXX_RESOLVE_LIB_DEFECTS
04962    *  DR 538. 241 again: Does unique_copy() require CopyConstructible and 
04963    *  Assignable?
04964   */
04965   template<typename _InputIterator, typename _OutputIterator>
04966     inline _OutputIterator
04967     unique_copy(_InputIterator __first, _InputIterator __last,
04968         _OutputIterator __result)
04969     {
04970       // concept requirements
04971       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
04972       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
04973         typename iterator_traits<_InputIterator>::value_type>)
04974       __glibcxx_function_requires(_EqualityComparableConcept<
04975         typename iterator_traits<_InputIterator>::value_type>)
04976       __glibcxx_requires_valid_range(__first, __last);
04977 
04978       if (__first == __last)
04979     return __result;
04980       return std::__unique_copy(__first, __last, __result,
04981                 std::__iterator_category(__first),
04982                 std::__iterator_category(__result));
04983     }
04984 
04985   /**
04986    *  @brief Copy a sequence, removing consecutive values using a predicate.
04987    *  @ingroup mutating_algorithms
04988    *  @param  first        An input iterator.
04989    *  @param  last         An input iterator.
04990    *  @param  result       An output iterator.
04991    *  @param  binary_pred  A binary predicate.
04992    *  @return   An iterator designating the end of the resulting sequence.
04993    *
04994    *  Copies each element in the range @p [first,last) to the range
04995    *  beginning at @p result, except that only the first element is copied
04996    *  from groups of consecutive elements for which @p binary_pred returns
04997    *  true.
04998    *  unique_copy() is stable, so the relative order of elements that are
04999    *  copied is unchanged.
05000    *
05001    *  _GLIBCXX_RESOLVE_LIB_DEFECTS
05002    *  DR 241. Does unique_copy() require CopyConstructible and Assignable?
05003   */
05004   template<typename _InputIterator, typename _OutputIterator,
05005        typename _BinaryPredicate>
05006     inline _OutputIterator
05007     unique_copy(_InputIterator __first, _InputIterator __last,
05008         _OutputIterator __result,
05009         _BinaryPredicate __binary_pred)
05010     {
05011       // concept requirements -- predicates checked later
05012       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
05013       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
05014         typename iterator_traits<_InputIterator>::value_type>)
05015       __glibcxx_requires_valid_range(__first, __last);
05016 
05017       if (__first == __last)
05018     return __result;
05019       return std::__unique_copy(__first, __last, __result, __binary_pred,
05020                 std::__iterator_category(__first),
05021                 std::__iterator_category(__result));
05022     }
05023 
05024 
05025   /**
05026    *  @brief Randomly shuffle the elements of a sequence.
05027    *  @ingroup mutating_algorithms
05028    *  @param  first   A forward iterator.
05029    *  @param  last    A forward iterator.
05030    *  @return  Nothing.
05031    *
05032    *  Reorder the elements in the range @p [first,last) using a random
05033    *  distribution, so that every possible ordering of the sequence is
05034    *  equally likely.
05035   */
05036   template<typename _RandomAccessIterator>
05037     inline void
05038     random_shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last)
05039     {
05040       // concept requirements
05041       __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
05042         _RandomAccessIterator>)
05043       __glibcxx_requires_valid_range(__first, __last);
05044 
05045       if (__first != __last)
05046     for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i)
05047       std::iter_swap(__i, __first + (std::rand() % ((__i - __first) + 1)));
05048     }
05049 
05050   /**
05051    *  @brief Shuffle the elements of a sequence using a random number
05052    *         generator.
05053    *  @ingroup mutating_algorithms
05054    *  @param  first   A forward iterator.
05055    *  @param  last    A forward iterator.
05056    *  @param  rand    The RNG functor or function.
05057    *  @return  Nothing.
05058    *
05059    *  Reorders the elements in the range @p [first,last) using @p rand to
05060    *  provide a random distribution. Calling @p rand(N) for a positive
05061    *  integer @p N should return a randomly chosen integer from the
05062    *  range [0,N).
05063   */
05064   template<typename _RandomAccessIterator, typename _RandomNumberGenerator>
05065     void
05066     random_shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last,
05067 #ifdef __GXX_EXPERIMENTAL_CXX0X__
05068            _RandomNumberGenerator&& __rand)
05069 #else
05070            _RandomNumberGenerator& __rand)
05071 #endif
05072     {
05073       // concept requirements
05074       __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
05075         _RandomAccessIterator>)
05076       __glibcxx_requires_valid_range(__first, __last);
05077 
05078       if (__first == __last)
05079     return;
05080       for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i)
05081     std::iter_swap(__i, __first + __rand((__i - __first) + 1));
05082     }
05083 
05084 
05085   /**
05086    *  @brief Move elements for which a predicate is true to the beginning
05087    *         of a sequence.
05088    *  @ingroup mutating_algorithms
05089    *  @param  first   A forward iterator.
05090    *  @param  last    A forward iterator.
05091    *  @param  pred    A predicate functor.
05092    *  @return  An iterator @p middle such that @p pred(i) is true for each
05093    *  iterator @p i in the range @p [first,middle) and false for each @p i
05094    *  in the range @p [middle,last).
05095    *
05096    *  @p pred must not modify its operand. @p partition() does not preserve
05097    *  the relative ordering of elements in each group, use
05098    *  @p stable_partition() if this is needed.
05099   */
05100   template<typename _ForwardIterator, typename _Predicate>
05101     inline _ForwardIterator
05102     partition(_ForwardIterator __first, _ForwardIterator __last,
05103           _Predicate   __pred)
05104     {
05105       // concept requirements
05106       __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
05107                   _ForwardIterator>)
05108       __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
05109         typename iterator_traits<_ForwardIterator>::value_type>)
05110       __glibcxx_requires_valid_range(__first, __last);
05111 
05112       return std::__partition(__first, __last, __pred,
05113                   std::__iterator_category(__first));
05114     }
05115 
05116 
05117 
05118   /**
05119    *  @brief Sort the smallest elements of a sequence.
05120    *  @ingroup sorting_algorithms
05121    *  @param  first   An iterator.
05122    *  @param  middle  Another iterator.
05123    *  @param  last    Another iterator.
05124    *  @return  Nothing.
05125    *
05126    *  Sorts the smallest @p (middle-first) elements in the range
05127    *  @p [first,last) and moves them to the range @p [first,middle). The
05128    *  order of the remaining elements in the range @p [middle,last) is
05129    *  undefined.
05130    *  After the sort if @p i and @j are iterators in the range
05131    *  @p [first,middle) such that @i precedes @j and @k is an iterator in
05132    *  the range @p [middle,last) then @p *j<*i and @p *k<*i are both false.
05133   */
05134   template<typename _RandomAccessIterator>
05135     inline void
05136     partial_sort(_RandomAccessIterator __first,
05137          _RandomAccessIterator __middle,
05138          _RandomAccessIterator __last)
05139     {
05140       typedef typename iterator_traits<_RandomAccessIterator>::value_type
05141     _ValueType;
05142 
05143       // concept requirements
05144       __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
05145         _RandomAccessIterator>)
05146       __glibcxx_function_requires(_LessThanComparableConcept<_ValueType>)
05147       __glibcxx_requires_valid_range(__first, __middle);
05148       __glibcxx_requires_valid_range(__middle, __last);
05149 
05150       std::__heap_select(__first, __middle, __last);
05151       std::sort_heap(__first, __middle);
05152     }
05153 
05154   /**
05155    *  @brief Sort the smallest elements of a sequence using a predicate
05156    *         for comparison.
05157    *  @ingroup sorting_algorithms
05158    *  @param  first   An iterator.
05159    *  @param  middle  Another iterator.
05160    *  @param  last    Another iterator.
05161    *  @param  comp    A comparison functor.
05162    *  @return  Nothing.
05163    *
05164    *  Sorts the smallest @p (middle-first) elements in the range
05165    *  @p [first,last) and moves them to the range @p [first,middle). The
05166    *  order of the remaining elements in the range @p [middle,last) is
05167    *  undefined.
05168    *  After the sort if @p i and @j are iterators in the range
05169    *  @p [first,middle) such that @i precedes @j and @k is an iterator in
05170    *  the range @p [middle,last) then @p *comp(j,*i) and @p comp(*k,*i)
05171    *  are both false.
05172   */
05173   template<typename _RandomAccessIterator, typename _Compare>
05174     inline void
05175     partial_sort(_RandomAccessIterator __first,
05176          _RandomAccessIterator __middle,
05177          _RandomAccessIterator __last,
05178          _Compare __comp)
05179     {
05180       typedef typename iterator_traits<_RandomAccessIterator>::value_type
05181     _ValueType;
05182 
05183       // concept requirements
05184       __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
05185         _RandomAccessIterator>)
05186       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
05187                   _ValueType, _ValueType>)
05188       __glibcxx_requires_valid_range(__first, __middle);
05189       __glibcxx_requires_valid_range(__middle, __last);
05190 
05191       std::__heap_select(__first, __middle, __last, __comp);
05192       std::sort_heap(__first, __middle, __comp);
05193     }
05194 
05195   /**
05196    *  @brief Sort a sequence just enough to find a particular position.
05197    *  @ingroup sorting_algorithms
05198    *  @param  first   An iterator.
05199    *  @param  nth     Another iterator.
05200    *  @param  last    Another iterator.
05201    *  @return  Nothing.
05202    *
05203    *  Rearranges the elements in the range @p [first,last) so that @p *nth
05204    *  is the same element that would have been in that position had the
05205    *  whole sequence been sorted.
05206    *  whole sequence been sorted. The elements either side of @p *nth are
05207    *  not completely sorted, but for any iterator @i in the range
05208    *  @p [first,nth) and any iterator @j in the range @p [nth,last) it
05209    *  holds that @p *j<*i is false.
05210   */
05211   template<typename _RandomAccessIterator>
05212     inline void
05213     nth_element(_RandomAccessIterator __first, _RandomAccessIterator __nth,
05214         _RandomAccessIterator __last)
05215     {
05216       typedef typename iterator_traits<_RandomAccessIterator>::value_type
05217     _ValueType;
05218 
05219       // concept requirements
05220       __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
05221                   _RandomAccessIterator>)
05222       __glibcxx_function_requires(_LessThanComparableConcept<_ValueType>)
05223       __glibcxx_requires_valid_range(__first, __nth);
05224       __glibcxx_requires_valid_range(__nth, __last);
05225 
05226       if (__first == __last || __nth == __last)
05227     return;
05228 
05229       std::__introselect(__first, __nth, __last,
05230              std::__lg(__last - __first) * 2);
05231     }
05232 
05233   /**
05234    *  @brief Sort a sequence just enough to find a particular position
05235    *         using a predicate for comparison.
05236    *  @ingroup sorting_algorithms
05237    *  @param  first   An iterator.
05238    *  @param  nth     Another iterator.
05239    *  @param  last    Another iterator.
05240    *  @param  comp    A comparison functor.
05241    *  @return  Nothing.
05242    *
05243    *  Rearranges the elements in the range @p [first,last) so that @p *nth
05244    *  is the same element that would have been in that position had the
05245    *  whole sequence been sorted. The elements either side of @p *nth are
05246    *  not completely sorted, but for any iterator @i in the range
05247    *  @p [first,nth) and any iterator @j in the range @p [nth,last) it
05248    *  holds that @p comp(*j,*i) is false.
05249   */
05250   template<typename _RandomAccessIterator, typename _Compare>
05251     inline void
05252     nth_element(_RandomAccessIterator __first, _RandomAccessIterator __nth,
05253         _RandomAccessIterator __last, _Compare __comp)
05254     {
05255       typedef typename iterator_traits<_RandomAccessIterator>::value_type
05256     _ValueType;
05257 
05258       // concept requirements
05259       __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
05260                   _RandomAccessIterator>)
05261       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
05262                   _ValueType, _ValueType>)
05263       __glibcxx_requires_valid_range(__first, __nth);
05264       __glibcxx_requires_valid_range(__nth, __last);
05265 
05266       if (__first == __last || __nth == __last)
05267     return;
05268 
05269       std::__introselect(__first, __nth, __last,
05270              std::__lg(__last - __first) * 2, __comp);
05271     }
05272 
05273 
05274   /**
05275    *  @brief Sort the elements of a sequence.
05276    *  @ingroup sorting_algorithms
05277    *  @param  first   An iterator.
05278    *  @param  last    Another iterator.
05279    *  @return  Nothing.
05280    *
05281    *  Sorts the elements in the range @p [first,last) in ascending order,
05282    *  such that @p *(i+1)<*i is false for each iterator @p i in the range
05283    *  @p [first,last-1).
05284    *
05285    *  The relative ordering of equivalent elements is not preserved, use
05286    *  @p stable_sort() if this is needed.
05287   */
05288   template<typename _RandomAccessIterator>
05289     inline void
05290     sort(_RandomAccessIterator __first, _RandomAccessIterator __last)
05291     {
05292       typedef typename iterator_traits<_RandomAccessIterator>::value_type
05293     _ValueType;
05294 
05295       // concept requirements
05296       __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
05297         _RandomAccessIterator>)
05298       __glibcxx_function_requires(_LessThanComparableConcept<_ValueType>)
05299       __glibcxx_requires_valid_range(__first, __last);
05300 
05301       if (__first != __last)
05302     {
05303       std::__introsort_loop(__first, __last,
05304                 std::__lg(__last - __first) * 2);
05305       std::__final_insertion_sort(__first, __last);
05306     }
05307     }
05308 
05309   /**
05310    *  @brief Sort the elements of a sequence using a predicate for comparison.
05311    *  @ingroup sorting_algorithms
05312    *  @param  first   An iterator.
05313    *  @param  last    Another iterator.
05314    *  @param  comp    A comparison functor.
05315    *  @return  Nothing.
05316    *
05317    *  Sorts the elements in the range @p [first,last) in ascending order,
05318    *  such that @p comp(*(i+1),*i) is false for every iterator @p i in the
05319    *  range @p [first,last-1).
05320    *
05321    *  The relative ordering of equivalent elements is not preserved, use
05322    *  @p stable_sort() if this is needed.
05323   */
05324   template<typename _RandomAccessIterator, typename _Compare>
05325     inline void
05326     sort(_RandomAccessIterator __first, _RandomAccessIterator __last,
05327      _Compare __comp)
05328     {
05329       typedef typename iterator_traits<_RandomAccessIterator>::value_type
05330     _ValueType;
05331 
05332       // concept requirements
05333       __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
05334         _RandomAccessIterator>)
05335       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, _ValueType,
05336                   _ValueType>)
05337       __glibcxx_requires_valid_range(__first, __last);
05338 
05339       if (__first != __last)
05340     {
05341       std::__introsort_loop(__first, __last,
05342                 std::__lg(__last - __first) * 2, __comp);
05343       std::__final_insertion_sort(__first, __last, __comp);
05344     }
05345     }
05346 
05347   /**
05348    *  @brief Merges two sorted ranges.
05349    *  @ingroup sorting_algorithms
05350    *  @param  first1  An iterator.
05351    *  @param  first2  Another iterator.
05352    *  @param  last1   Another iterator.
05353    *  @param  last2   Another iterator.
05354    *  @param  result  An iterator pointing to the end of the merged range.
05355    *  @return         An iterator pointing to the first element <em>not less
05356    *                  than</em> @a val.
05357    *
05358    *  Merges the ranges [first1,last1) and [first2,last2) into the sorted range
05359    *  [result, result + (last1-first1) + (last2-first2)).  Both input ranges
05360    *  must be sorted, and the output range must not overlap with either of
05361    *  the input ranges.  The sort is @e stable, that is, for equivalent
05362    *  elements in the two ranges, elements from the first range will always
05363    *  come before elements from the second.
05364   */
05365   template<typename _InputIterator1, typename _InputIterator2,
05366        typename _OutputIterator>
05367     _OutputIterator
05368     merge(_InputIterator1 __first1, _InputIterator1 __last1,
05369       _InputIterator2 __first2, _InputIterator2 __last2,
05370       _OutputIterator __result)
05371     {
05372       typedef typename iterator_traits<_InputIterator1>::value_type
05373     _ValueType1;
05374       typedef typename iterator_traits<_InputIterator2>::value_type
05375     _ValueType2;
05376 
05377       // concept requirements
05378       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
05379       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
05380       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
05381                   _ValueType1>)
05382       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
05383                   _ValueType2>)
05384       __glibcxx_function_requires(_LessThanOpConcept<_ValueType2, _ValueType1>) 
05385       __glibcxx_requires_sorted_set(__first1, __last1, __first2);
05386       __glibcxx_requires_sorted_set(__first2, __last2, __first1);
05387 
05388       while (__first1 != __last1 && __first2 != __last2)
05389     {
05390       if (*__first2 < *__first1)
05391         {
05392           *__result = *__first2;
05393           ++__first2;
05394         }
05395       else
05396         {
05397           *__result = *__first1;
05398           ++__first1;
05399         }
05400       ++__result;
05401     }
05402       return std::copy(__first2, __last2, std::copy(__first1, __last1,
05403                             __result));
05404     }
05405 
05406   /**
05407    *  @brief Merges two sorted ranges.
05408    *  @ingroup sorting_algorithms
05409    *  @param  first1  An iterator.
05410    *  @param  first2  Another iterator.
05411    *  @param  last1   Another iterator.
05412    *  @param  last2   Another iterator.
05413    *  @param  result  An iterator pointing to the end of the merged range.
05414    *  @param  comp    A functor to use for comparisons.
05415    *  @return         An iterator pointing to the first element "not less
05416    *                  than" @a val.
05417    *
05418    *  Merges the ranges [first1,last1) and [first2,last2) into the sorted range
05419    *  [result, result + (last1-first1) + (last2-first2)).  Both input ranges
05420    *  must be sorted, and the output range must not overlap with either of
05421    *  the input ranges.  The sort is @e stable, that is, for equivalent
05422    *  elements in the two ranges, elements from the first range will always
05423    *  come before elements from the second.
05424    *
05425    *  The comparison function should have the same effects on ordering as
05426    *  the function used for the initial sort.
05427   */
05428   template<typename _InputIterator1, typename _InputIterator2,
05429        typename _OutputIterator, typename _Compare>
05430     _OutputIterator
05431     merge(_InputIterator1 __first1, _InputIterator1 __last1,
05432       _InputIterator2 __first2, _InputIterator2 __last2,
05433       _OutputIterator __result, _Compare __comp)
05434     {
05435       typedef typename iterator_traits<_InputIterator1>::value_type
05436     _ValueType1;
05437       typedef typename iterator_traits<_InputIterator2>::value_type
05438     _ValueType2;
05439 
05440       // concept requirements
05441       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
05442       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
05443       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
05444                   _ValueType1>)
05445       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
05446                   _ValueType2>)
05447       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
05448                   _ValueType2, _ValueType1>)
05449       __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp);
05450       __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp);
05451 
05452       while (__first1 != __last1 && __first2 != __last2)
05453     {
05454       if (__comp(*__first2, *__first1))
05455         {
05456           *__result = *__first2;
05457           ++__first2;
05458         }
05459       else
05460         {
05461           *__result = *__first1;
05462           ++__first1;
05463         }
05464       ++__result;
05465     }
05466       return std::copy(__first2, __last2, std::copy(__first1, __last1,
05467                             __result));
05468     }
05469 
05470 
05471   /**
05472    *  @brief Sort the elements of a sequence, preserving the relative order
05473    *         of equivalent elements.
05474    *  @ingroup sorting_algorithms
05475    *  @param  first   An iterator.
05476    *  @param  last    Another iterator.
05477    *  @return  Nothing.
05478    *
05479    *  Sorts the elements in the range @p [first,last) in ascending order,
05480    *  such that @p *(i+1)<*i is false for each iterator @p i in the range
05481    *  @p [first,last-1).
05482    *
05483    *  The relative ordering of equivalent elements is preserved, so any two
05484    *  elements @p x and @p y in the range @p [first,last) such that
05485    *  @p x<y is false and @p y<x is false will have the same relative
05486    *  ordering after calling @p stable_sort().
05487   */
05488   template<typename _RandomAccessIterator>
05489     inline void
05490     stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last)
05491     {
05492       typedef typename iterator_traits<_RandomAccessIterator>::value_type
05493     _ValueType;
05494       typedef typename iterator_traits<_RandomAccessIterator>::difference_type
05495     _DistanceType;
05496 
05497       // concept requirements
05498       __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
05499         _RandomAccessIterator>)
05500       __glibcxx_function_requires(_LessThanComparableConcept<_ValueType>)
05501       __glibcxx_requires_valid_range(__first, __last);
05502 
05503       _Temporary_buffer<_RandomAccessIterator, _ValueType> __buf(__first,
05504                                  __last);
05505       if (__buf.begin() == 0)
05506     std::__inplace_stable_sort(__first, __last);
05507       else
05508     std::__stable_sort_adaptive(__first, __last, __buf.begin(),
05509                     _DistanceType(__buf.size()));
05510     }
05511 
05512   /**
05513    *  @brief Sort the elements of a sequence using a predicate for comparison,
05514    *         preserving the relative order of equivalent elements.
05515    *  @ingroup sorting_algorithms
05516    *  @param  first   An iterator.
05517    *  @param  last    Another iterator.
05518    *  @param  comp    A comparison functor.
05519    *  @return  Nothing.
05520    *
05521    *  Sorts the elements in the range @p [first,last) in ascending order,
05522    *  such that @p comp(*(i+1),*i) is false for each iterator @p i in the
05523    *  range @p [first,last-1).
05524    *
05525    *  The relative ordering of equivalent elements is preserved, so any two
05526    *  elements @p x and @p y in the range @p [first,last) such that
05527    *  @p comp(x,y) is false and @p comp(y,x) is false will have the same
05528    *  relative ordering after calling @p stable_sort().
05529   */
05530   template<typename _RandomAccessIterator, typename _Compare>
05531     inline void
05532     stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last,
05533         _Compare __comp)
05534     {
05535       typedef typename iterator_traits<_RandomAccessIterator>::value_type
05536     _ValueType;
05537       typedef typename iterator_traits<_RandomAccessIterator>::difference_type
05538     _DistanceType;
05539 
05540       // concept requirements
05541       __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
05542         _RandomAccessIterator>)
05543       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
05544                   _ValueType,
05545                   _ValueType>)
05546       __glibcxx_requires_valid_range(__first, __last);
05547 
05548       _Temporary_buffer<_RandomAccessIterator, _ValueType> __buf(__first,
05549                                  __last);
05550       if (__buf.begin() == 0)
05551     std::__inplace_stable_sort(__first, __last, __comp);
05552       else
05553     std::__stable_sort_adaptive(__first, __last, __buf.begin(),
05554                     _DistanceType(__buf.size()), __comp);
05555     }
05556 
05557 
05558   /**
05559    *  @brief Return the union of two sorted ranges.
05560    *  @ingroup set_algorithms
05561    *  @param  first1  Start of first range.
05562    *  @param  last1   End of first range.
05563    *  @param  first2  Start of second range.
05564    *  @param  last2   End of second range.
05565    *  @return  End of the output range.
05566    *  @ingroup set_algorithms
05567    *
05568    *  This operation iterates over both ranges, copying elements present in
05569    *  each range in order to the output range.  Iterators increment for each
05570    *  range.  When the current element of one range is less than the other,
05571    *  that element is copied and the iterator advanced.  If an element is
05572    *  contained in both ranges, the element from the first range is copied and
05573    *  both ranges advance.  The output range may not overlap either input
05574    *  range.
05575   */
05576   template<typename _InputIterator1, typename _InputIterator2,
05577        typename _OutputIterator>
05578     _OutputIterator
05579     set_union(_InputIterator1 __first1, _InputIterator1 __last1,
05580           _InputIterator2 __first2, _InputIterator2 __last2,
05581           _OutputIterator __result)
05582     {
05583       typedef typename iterator_traits<_InputIterator1>::value_type
05584     _ValueType1;
05585       typedef typename iterator_traits<_InputIterator2>::value_type
05586     _ValueType2;
05587 
05588       // concept requirements
05589       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
05590       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
05591       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
05592                   _ValueType1>)
05593       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
05594                   _ValueType2>)
05595       __glibcxx_function_requires(_LessThanOpConcept<_ValueType1, _ValueType2>)
05596       __glibcxx_function_requires(_LessThanOpConcept<_ValueType2, _ValueType1>)
05597       __glibcxx_requires_sorted_set(__first1, __last1, __first2);
05598       __glibcxx_requires_sorted_set(__first2, __last2, __first1);
05599 
05600       while (__first1 != __last1 && __first2 != __last2)
05601     {
05602       if (*__first1 < *__first2)
05603         {
05604           *__result = *__first1;
05605           ++__first1;
05606         }
05607       else if (*__first2 < *__first1)
05608         {
05609           *__result = *__first2;
05610           ++__first2;
05611         }
05612       else
05613         {
05614           *__result = *__first1;
05615           ++__first1;
05616           ++__first2;
05617         }
05618       ++__result;
05619     }
05620       return std::copy(__first2, __last2, std::copy(__first1, __last1,
05621                             __result));
05622     }
05623 
05624   /**
05625    *  @brief Return the union of two sorted ranges using a comparison functor.
05626    *  @ingroup set_algorithms
05627    *  @param  first1  Start of first range.
05628    *  @param  last1   End of first range.
05629    *  @param  first2  Start of second range.
05630    *  @param  last2   End of second range.
05631    *  @param  comp    The comparison functor.
05632    *  @return  End of the output range.
05633    *  @ingroup set_algorithms
05634    *
05635    *  This operation iterates over both ranges, copying elements present in
05636    *  each range in order to the output range.  Iterators increment for each
05637    *  range.  When the current element of one range is less than the other
05638    *  according to @a comp, that element is copied and the iterator advanced.
05639    *  If an equivalent element according to @a comp is contained in both
05640    *  ranges, the element from the first range is copied and both ranges
05641    *  advance.  The output range may not overlap either input range.
05642   */
05643   template<typename _InputIterator1, typename _InputIterator2,
05644        typename _OutputIterator, typename _Compare>
05645     _OutputIterator
05646     set_union(_InputIterator1 __first1, _InputIterator1 __last1,
05647           _InputIterator2 __first2, _InputIterator2 __last2,
05648           _OutputIterator __result, _Compare __comp)
05649     {
05650       typedef typename iterator_traits<_InputIterator1>::value_type
05651     _ValueType1;
05652       typedef typename iterator_traits<_InputIterator2>::value_type
05653     _ValueType2;
05654 
05655       // concept requirements
05656       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
05657       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
05658       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
05659                   _ValueType1>)
05660       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
05661                   _ValueType2>)
05662       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
05663                   _ValueType1, _ValueType2>)
05664       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
05665                   _ValueType2, _ValueType1>)
05666       __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp);
05667       __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp);
05668 
05669       while (__first1 != __last1 && __first2 != __last2)
05670     {
05671       if (__comp(*__first1, *__first2))
05672         {
05673           *__result = *__first1;
05674           ++__first1;
05675         }
05676       else if (__comp(*__first2, *__first1))
05677         {
05678           *__result = *__first2;
05679           ++__first2;
05680         }
05681       else
05682         {
05683           *__result = *__first1;
05684           ++__first1;
05685           ++__first2;
05686         }
05687       ++__result;
05688     }
05689       return std::copy(__first2, __last2, std::copy(__first1, __last1,
05690                             __result));
05691     }
05692 
05693   /**
05694    *  @brief Return the intersection of two sorted ranges.
05695    *  @ingroup set_algorithms
05696    *  @param  first1  Start of first range.
05697    *  @param  last1   End of first range.
05698    *  @param  first2  Start of second range.
05699    *  @param  last2   End of second range.
05700    *  @return  End of the output range.
05701    *  @ingroup set_algorithms
05702    *
05703    *  This operation iterates over both ranges, copying elements present in
05704    *  both ranges in order to the output range.  Iterators increment for each
05705    *  range.  When the current element of one range is less than the other,
05706    *  that iterator advances.  If an element is contained in both ranges, the
05707    *  element from the first range is copied and both ranges advance.  The
05708    *  output range may not overlap either input range.
05709   */
05710   template<typename _InputIterator1, typename _InputIterator2,
05711        typename _OutputIterator>
05712     _OutputIterator
05713     set_intersection(_InputIterator1 __first1, _InputIterator1 __last1,
05714              _InputIterator2 __first2, _InputIterator2 __last2,
05715              _OutputIterator __result)
05716     {
05717       typedef typename iterator_traits<_InputIterator1>::value_type
05718     _ValueType1;
05719       typedef typename iterator_traits<_InputIterator2>::value_type
05720     _ValueType2;
05721 
05722       // concept requirements
05723       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
05724       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
05725       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
05726                   _ValueType1>)
05727       __glibcxx_function_requires(_LessThanOpConcept<_ValueType1, _ValueType2>)
05728       __glibcxx_function_requires(_LessThanOpConcept<_ValueType2, _ValueType1>)
05729       __glibcxx_requires_sorted_set(__first1, __last1, __first2);
05730       __glibcxx_requires_sorted_set(__first2, __last2, __first1);
05731 
05732       while (__first1 != __last1 && __first2 != __last2)
05733     if (*__first1 < *__first2)
05734       ++__first1;
05735     else if (*__first2 < *__first1)
05736       ++__first2;
05737     else
05738       {
05739         *__result = *__first1;
05740         ++__first1;
05741         ++__first2;
05742         ++__result;
05743       }
05744       return __result;
05745     }
05746 
05747   /**
05748    *  @brief Return the intersection of two sorted ranges using comparison
05749    *  functor.
05750    *  @ingroup set_algorithms
05751    *  @param  first1  Start of first range.
05752    *  @param  last1   End of first range.
05753    *  @param  first2  Start of second range.
05754    *  @param  last2   End of second range.
05755    *  @param  comp    The comparison functor.
05756    *  @return  End of the output range.
05757    *  @ingroup set_algorithms
05758    *
05759    *  This operation iterates over both ranges, copying elements present in
05760    *  both ranges in order to the output range.  Iterators increment for each
05761    *  range.  When the current element of one range is less than the other
05762    *  according to @a comp, that iterator advances.  If an element is
05763    *  contained in both ranges according to @a comp, the element from the
05764    *  first range is copied and both ranges advance.  The output range may not
05765    *  overlap either input range.
05766   */
05767   template<typename _InputIterator1, typename _InputIterator2,
05768        typename _OutputIterator, typename _Compare>
05769     _OutputIterator
05770     set_intersection(_InputIterator1 __first1, _InputIterator1 __last1,
05771              _InputIterator2 __first2, _InputIterator2 __last2,
05772              _OutputIterator __result, _Compare __comp)
05773     {
05774       typedef typename iterator_traits<_InputIterator1>::value_type
05775     _ValueType1;
05776       typedef typename iterator_traits<_InputIterator2>::value_type
05777     _ValueType2;
05778 
05779       // concept requirements
05780       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
05781       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
05782       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
05783                   _ValueType1>)
05784       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
05785                   _ValueType1, _ValueType2>)
05786       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
05787                   _ValueType2, _ValueType1>)
05788       __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp);
05789       __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp);
05790 
05791       while (__first1 != __last1 && __first2 != __last2)
05792     if (__comp(*__first1, *__first2))
05793       ++__first1;
05794     else if (__comp(*__first2, *__first1))
05795       ++__first2;
05796     else
05797       {
05798         *__result = *__first1;
05799         ++__first1;
05800         ++__first2;
05801         ++__result;
05802       }
05803       return __result;
05804     }
05805 
05806   /**
05807    *  @brief Return the difference of two sorted ranges.
05808    *  @ingroup set_algorithms
05809    *  @param  first1  Start of first range.
05810    *  @param  last1   End of first range.
05811    *  @param  first2  Start of second range.
05812    *  @param  last2   End of second range.
05813    *  @return  End of the output range.
05814    *  @ingroup set_algorithms
05815    *
05816    *  This operation iterates over both ranges, copying elements present in
05817    *  the first range but not the second in order to the output range.
05818    *  Iterators increment for each range.  When the current element of the
05819    *  first range is less than the second, that element is copied and the
05820    *  iterator advances.  If the current element of the second range is less,
05821    *  the iterator advances, but no element is copied.  If an element is
05822    *  contained in both ranges, no elements are copied and both ranges
05823    *  advance.  The output range may not overlap either input range.
05824   */
05825   template<typename _InputIterator1, typename _InputIterator2,
05826        typename _OutputIterator>
05827     _OutputIterator
05828     set_difference(_InputIterator1 __first1, _InputIterator1 __last1,
05829            _InputIterator2 __first2, _InputIterator2 __last2,
05830            _OutputIterator __result)
05831     {
05832       typedef typename iterator_traits<_InputIterator1>::value_type
05833     _ValueType1;
05834       typedef typename iterator_traits<_InputIterator2>::value_type
05835     _ValueType2;
05836 
05837       // concept requirements
05838       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
05839       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
05840       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
05841                   _ValueType1>)
05842       __glibcxx_function_requires(_LessThanOpConcept<_ValueType1, _ValueType2>)
05843       __glibcxx_function_requires(_LessThanOpConcept<_ValueType2, _ValueType1>) 
05844       __glibcxx_requires_sorted_set(__first1, __last1, __first2);
05845       __glibcxx_requires_sorted_set(__first2, __last2, __first1);
05846 
05847       while (__first1 != __last1 && __first2 != __last2)
05848     if (*__first1 < *__first2)
05849       {
05850         *__result = *__first1;
05851         ++__first1;
05852         ++__result;
05853       }
05854     else if (*__first2 < *__first1)
05855       ++__first2;
05856     else
05857       {
05858         ++__first1;
05859         ++__first2;
05860       }
05861       return std::copy(__first1, __last1, __result);
05862     }
05863 
05864   /**
05865    *  @brief  Return the difference of two sorted ranges using comparison
05866    *  functor.
05867    *  @ingroup set_algorithms
05868    *  @param  first1  Start of first range.
05869    *  @param  last1   End of first range.
05870    *  @param  first2  Start of second range.
05871    *  @param  last2   End of second range.
05872    *  @param  comp    The comparison functor.
05873    *  @return  End of the output range.
05874    *  @ingroup set_algorithms
05875    *
05876    *  This operation iterates over both ranges, copying elements present in
05877    *  the first range but not the second in order to the output range.
05878    *  Iterators increment for each range.  When the current element of the
05879    *  first range is less than the second according to @a comp, that element
05880    *  is copied and the iterator advances.  If the current element of the
05881    *  second range is less, no element is copied and the iterator advances.
05882    *  If an element is contained in both ranges according to @a comp, no
05883    *  elements are copied and both ranges advance.  The output range may not
05884    *  overlap either input range.
05885   */
05886   template<typename _InputIterator1, typename _InputIterator2,
05887        typename _OutputIterator, typename _Compare>
05888     _OutputIterator
05889     set_difference(_InputIterator1 __first1, _InputIterator1 __last1,
05890            _InputIterator2 __first2, _InputIterator2 __last2,
05891            _OutputIterator __result, _Compare __comp)
05892     {
05893       typedef typename iterator_traits<_InputIterator1>::value_type
05894     _ValueType1;
05895       typedef typename iterator_traits<_InputIterator2>::value_type
05896     _ValueType2;
05897 
05898       // concept requirements
05899       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
05900       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
05901       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
05902                   _ValueType1>)
05903       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
05904                   _ValueType1, _ValueType2>)
05905       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
05906                   _ValueType2, _ValueType1>)
05907       __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp);
05908       __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp);
05909 
05910       while (__first1 != __last1 && __first2 != __last2)
05911     if (__comp(*__first1, *__first2))
05912       {
05913         *__result = *__first1;
05914         ++__first1;
05915         ++__result;
05916       }
05917     else if (__comp(*__first2, *__first1))
05918       ++__first2;
05919     else
05920       {
05921         ++__first1;
05922         ++__first2;
05923       }
05924       return std::copy(__first1, __last1, __result);
05925     }
05926 
05927   /**
05928    *  @brief  Return the symmetric difference of two sorted ranges.
05929    *  @ingroup set_algorithms
05930    *  @param  first1  Start of first range.
05931    *  @param  last1   End of first range.
05932    *  @param  first2  Start of second range.
05933    *  @param  last2   End of second range.
05934    *  @return  End of the output range.
05935    *  @ingroup set_algorithms
05936    *
05937    *  This operation iterates over both ranges, copying elements present in
05938    *  one range but not the other in order to the output range.  Iterators
05939    *  increment for each range.  When the current element of one range is less
05940    *  than the other, that element is copied and the iterator advances.  If an
05941    *  element is contained in both ranges, no elements are copied and both
05942    *  ranges advance.  The output range may not overlap either input range.
05943   */
05944   template<typename _InputIterator1, typename _InputIterator2,
05945        typename _OutputIterator>
05946     _OutputIterator
05947     set_symmetric_difference(_InputIterator1 __first1, _InputIterator1 __last1,
05948                  _InputIterator2 __first2, _InputIterator2 __last2,
05949                  _OutputIterator __result)
05950     {
05951       typedef typename iterator_traits<_InputIterator1>::value_type
05952     _ValueType1;
05953       typedef typename iterator_traits<_InputIterator2>::value_type
05954     _ValueType2;
05955 
05956       // concept requirements
05957       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
05958       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
05959       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
05960                   _ValueType1>)
05961       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
05962                   _ValueType2>)
05963       __glibcxx_function_requires(_LessThanOpConcept<_ValueType1, _ValueType2>)
05964       __glibcxx_function_requires(_LessThanOpConcept<_ValueType2, _ValueType1>) 
05965       __glibcxx_requires_sorted_set(__first1, __last1, __first2);
05966       __glibcxx_requires_sorted_set(__first2, __last2, __first1);
05967 
05968       while (__first1 != __last1 && __first2 != __last2)
05969     if (*__first1 < *__first2)
05970       {
05971         *__result = *__first1;
05972         ++__first1;
05973         ++__result;
05974       }
05975     else if (*__first2 < *__first1)
05976       {
05977         *__result = *__first2;
05978         ++__first2;
05979         ++__result;
05980       }
05981     else
05982       {
05983         ++__first1;
05984         ++__first2;
05985       }
05986       return std::copy(__first2, __last2, std::copy(__first1,
05987                             __last1, __result));
05988     }
05989 
05990   /**
05991    *  @brief  Return the symmetric difference of two sorted ranges using
05992    *  comparison functor.
05993    *  @ingroup set_algorithms
05994    *  @param  first1  Start of first range.
05995    *  @param  last1   End of first range.
05996    *  @param  first2  Start of second range.
05997    *  @param  last2   End of second range.
05998    *  @param  comp    The comparison functor.
05999    *  @return  End of the output range.
06000    *  @ingroup set_algorithms
06001    *
06002    *  This operation iterates over both ranges, copying elements present in
06003    *  one range but not the other in order to the output range.  Iterators
06004    *  increment for each range.  When the current element of one range is less
06005    *  than the other according to @a comp, that element is copied and the
06006    *  iterator advances.  If an element is contained in both ranges according
06007    *  to @a comp, no elements are copied and both ranges advance.  The output
06008    *  range may not overlap either input range.
06009   */
06010   template<typename _InputIterator1, typename _InputIterator2,
06011        typename _OutputIterator, typename _Compare>
06012     _OutputIterator
06013     set_symmetric_difference(_InputIterator1 __first1, _InputIterator1 __last1,
06014                  _InputIterator2 __first2, _InputIterator2 __last2,
06015                  _OutputIterator __result,
06016                  _Compare __comp)
06017     {
06018       typedef typename iterator_traits<_InputIterator1>::value_type
06019     _ValueType1;
06020       typedef typename iterator_traits<_InputIterator2>::value_type
06021     _ValueType2;
06022 
06023       // concept requirements
06024       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
06025       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
06026       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
06027                   _ValueType1>)
06028       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
06029                   _ValueType2>)
06030       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
06031                   _ValueType1, _ValueType2>)
06032       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
06033                   _ValueType2, _ValueType1>)
06034       __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp);
06035       __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp);
06036 
06037       while (__first1 != __last1 && __first2 != __last2)
06038     if (__comp(*__first1, *__first2))
06039       {
06040         *__result = *__first1;
06041         ++__first1;
06042         ++__result;
06043       }
06044     else if (__comp(*__first2, *__first1))
06045       {
06046         *__result = *__first2;
06047         ++__first2;
06048         ++__result;
06049       }
06050     else
06051       {
06052         ++__first1;
06053         ++__first2;
06054       }
06055       return std::copy(__first2, __last2, 
06056                std::copy(__first1, __last1, __result));
06057     }
06058 
06059 
06060   /**
06061    *  @brief  Return the minimum element in a range.
06062    *  @ingroup sorting_algorithms
06063    *  @param  first  Start of range.
06064    *  @param  last   End of range.
06065    *  @return  Iterator referencing the first instance of the smallest value.
06066   */
06067   template<typename _ForwardIterator>
06068     _ForwardIterator
06069     min_element(_ForwardIterator __first, _ForwardIterator __last)
06070     {
06071       // concept requirements
06072       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
06073       __glibcxx_function_requires(_LessThanComparableConcept<
06074         typename iterator_traits<_ForwardIterator>::value_type>)
06075       __glibcxx_requires_valid_range(__first, __last);
06076 
06077       if (__first == __last)
06078     return __first;
06079       _ForwardIterator __result = __first;
06080       while (++__first != __last)
06081     if (*__first < *__result)
06082       __result = __first;
06083       return __result;
06084     }
06085 
06086   /**
06087    *  @brief  Return the minimum element in a range using comparison functor.
06088    *  @ingroup sorting_algorithms
06089    *  @param  first  Start of range.
06090    *  @param  last   End of range.
06091    *  @param  comp   Comparison functor.
06092    *  @return  Iterator referencing the first instance of the smallest value
06093    *  according to comp.
06094   */
06095   template<typename _ForwardIterator, typename _Compare>
06096     _ForwardIterator
06097     min_element(_ForwardIterator __first, _ForwardIterator __last,
06098         _Compare __comp)
06099     {
06100       // concept requirements
06101       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
06102       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
06103         typename iterator_traits<_ForwardIterator>::value_type,
06104         typename iterator_traits<_ForwardIterator>::value_type>)
06105       __glibcxx_requires_valid_range(__first, __last);
06106 
06107       if (__first == __last)
06108     return __first;
06109       _ForwardIterator __result = __first;
06110       while (++__first != __last)
06111     if (__comp(*__first, *__result))
06112       __result = __first;
06113       return __result;
06114     }
06115 
06116   /**
06117    *  @brief  Return the maximum element in a range.
06118    *  @ingroup sorting_algorithms
06119    *  @param  first  Start of range.
06120    *  @param  last   End of range.
06121    *  @return  Iterator referencing the first instance of the largest value.
06122   */
06123   template<typename _ForwardIterator>
06124     _ForwardIterator
06125     max_element(_ForwardIterator __first, _ForwardIterator __last)
06126     {
06127       // concept requirements
06128       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
06129       __glibcxx_function_requires(_LessThanComparableConcept<
06130         typename iterator_traits<_ForwardIterator>::value_type>)
06131       __glibcxx_requires_valid_range(__first, __last);
06132 
06133       if (__first == __last)
06134     return __first;
06135       _ForwardIterator __result = __first;
06136       while (++__first != __last)
06137     if (*__result < *__first)
06138       __result = __first;
06139       return __result;
06140     }
06141 
06142   /**
06143    *  @brief  Return the maximum element in a range using comparison functor.
06144    *  @ingroup sorting_algorithms
06145    *  @param  first  Start of range.
06146    *  @param  last   End of range.
06147    *  @param  comp   Comparison functor.
06148    *  @return  Iterator referencing the first instance of the largest value
06149    *  according to comp.
06150   */
06151   template<typename _ForwardIterator, typename _Compare>
06152     _ForwardIterator
06153     max_element(_ForwardIterator __first, _ForwardIterator __last,
06154         _Compare __comp)
06155     {
06156       // concept requirements
06157       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
06158       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
06159         typename iterator_traits<_ForwardIterator>::value_type,
06160         typename iterator_traits<_ForwardIterator>::value_type>)
06161       __glibcxx_requires_valid_range(__first, __last);
06162 
06163       if (__first == __last) return __first;
06164       _ForwardIterator __result = __first;
06165       while (++__first != __last)
06166     if (__comp(*__result, *__first))
06167       __result = __first;
06168       return __result;
06169     }
06170 
06171 _GLIBCXX_END_NAMESPACE_ALGO
06172 } // namespace std
06173 
06174 #endif /* _STL_ALGO_H */