stl_algo.h

Go to the documentation of this file.
00001 // Algorithm implementation -*- C++ -*- 00002 00003 // Copyright (C) 2001, 2002 Free Software Foundation, Inc. 00004 // 00005 // This file is part of the GNU ISO C++ Library. This library is free 00006 // software; you can redistribute it and/or modify it under the 00007 // terms of the GNU General Public License as published by the 00008 // Free Software Foundation; either version 2, or (at your option) 00009 // any later version. 00010 00011 // This library is distributed in the hope that it will be useful, 00012 // but WITHOUT ANY WARRANTY; without even the implied warranty of 00013 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 00014 // GNU General Public License for more details. 00015 00016 // You should have received a copy of the GNU General Public License along 00017 // with this library; see the file COPYING. If not, write to the Free 00018 // Software Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307, 00019 // USA. 00020 00021 // As a special exception, you may use this file as part of a free software 00022 // library without restriction. Specifically, if other files instantiate 00023 // templates or use macros or inline functions from this file, or you compile 00024 // this file and link it with other files to produce an executable, this 00025 // file does not by itself cause the resulting executable to be covered by 00026 // the GNU General Public License. This exception does not however 00027 // invalidate any other reasons why the executable file might be covered by 00028 // the GNU General Public License. 00029 00030 /* 00031 * 00032 * Copyright (c) 1994 00033 * Hewlett-Packard Company 00034 * 00035 * Permission to use, copy, modify, distribute and sell this software 00036 * and its documentation for any purpose is hereby granted without fee, 00037 * provided that the above copyright notice appear in all copies and 00038 * that both that copyright notice and this permission notice appear 00039 * in supporting documentation. Hewlett-Packard Company makes no 00040 * representations about the suitability of this software for any 00041 * purpose. It is provided "as is" without express or implied warranty. 00042 * 00043 * 00044 * Copyright (c) 1996 00045 * Silicon Graphics Computer Systems, Inc. 00046 * 00047 * Permission to use, copy, modify, distribute and sell this software 00048 * and its documentation for any purpose is hereby granted without fee, 00049 * provided that the above copyright notice appear in all copies and 00050 * that both that copyright notice and this permission notice appear 00051 * in supporting documentation. Silicon Graphics makes no 00052 * representations about the suitability of this software for any 00053 * purpose. It is provided "as is" without express or implied warranty. 00054 */ 00055 00061 #ifndef __GLIBCPP_INTERNAL_ALGO_H 00062 #define __GLIBCPP_INTERNAL_ALGO_H 00063 00064 #include <bits/stl_heap.h> 00065 #include <bits/stl_tempbuf.h> // for _Temporary_buffer 00066 00067 // See concept_check.h for the __glibcpp_*_requires macros. 00068 00069 namespace std 00070 { 00071 00084 template<typename _Tp> 00085 inline const _Tp& 00086 __median(const _Tp& __a, const _Tp& __b, const _Tp& __c) 00087 { 00088 // concept requirements 00089 __glibcpp_function_requires(_LessThanComparableConcept<_Tp>) 00090 if (__a < __b) 00091 if (__b < __c) 00092 return __b; 00093 else if (__a < __c) 00094 return __c; 00095 else 00096 return __a; 00097 else if (__a < __c) 00098 return __a; 00099 else if (__b < __c) 00100 return __c; 00101 else 00102 return __b; 00103 } 00104 00118 template<typename _Tp, typename _Compare> 00119 inline const _Tp& 00120 __median(const _Tp& __a, const _Tp& __b, const _Tp& __c, _Compare __comp) 00121 { 00122 // concept requirements 00123 __glibcpp_function_requires(_BinaryFunctionConcept<_Compare,bool,_Tp,_Tp>) 00124 if (__comp(__a, __b)) 00125 if (__comp(__b, __c)) 00126 return __b; 00127 else if (__comp(__a, __c)) 00128 return __c; 00129 else 00130 return __a; 00131 else if (__comp(__a, __c)) 00132 return __a; 00133 else if (__comp(__b, __c)) 00134 return __c; 00135 else 00136 return __b; 00137 } 00138 00150 template<typename _InputIter, typename _Function> 00151 _Function 00152 for_each(_InputIter __first, _InputIter __last, _Function __f) 00153 { 00154 // concept requirements 00155 __glibcpp_function_requires(_InputIteratorConcept<_InputIter>) 00156 for ( ; __first != __last; ++__first) 00157 __f(*__first); 00158 return __f; 00159 } 00160 00166 template<typename _InputIter, typename _Tp> 00167 inline _InputIter 00168 find(_InputIter __first, _InputIter __last, 00169 const _Tp& __val, 00170 input_iterator_tag) 00171 { 00172 while (__first != __last && !(*__first == __val)) 00173 ++__first; 00174 return __first; 00175 } 00176 00182 template<typename _InputIter, typename _Predicate> 00183 inline _InputIter 00184 find_if(_InputIter __first, _InputIter __last, 00185 _Predicate __pred, 00186 input_iterator_tag) 00187 { 00188 while (__first != __last && !__pred(*__first)) 00189 ++__first; 00190 return __first; 00191 } 00192 00198 template<typename _RandomAccessIter, typename _Tp> 00199 _RandomAccessIter 00200 find(_RandomAccessIter __first, _RandomAccessIter __last, 00201 const _Tp& __val, 00202 random_access_iterator_tag) 00203 { 00204 typename iterator_traits<_RandomAccessIter>::difference_type __trip_count 00205 = (__last - __first) >> 2; 00206 00207 for ( ; __trip_count > 0 ; --__trip_count) { 00208 if (*__first == __val) return __first; 00209 ++__first; 00210 00211 if (*__first == __val) return __first; 00212 ++__first; 00213 00214 if (*__first == __val) return __first; 00215 ++__first; 00216 00217 if (*__first == __val) return __first; 00218 ++__first; 00219 } 00220 00221 switch(__last - __first) { 00222 case 3: 00223 if (*__first == __val) return __first; 00224 ++__first; 00225 case 2: 00226 if (*__first == __val) return __first; 00227 ++__first; 00228 case 1: 00229 if (*__first == __val) return __first; 00230 ++__first; 00231 case 0: 00232 default: 00233 return __last; 00234 } 00235 } 00236 00242 template<typename _RandomAccessIter, typename _Predicate> 00243 _RandomAccessIter 00244 find_if(_RandomAccessIter __first, _RandomAccessIter __last, 00245 _Predicate __pred, 00246 random_access_iterator_tag) 00247 { 00248 typename iterator_traits<_RandomAccessIter>::difference_type __trip_count 00249 = (__last - __first) >> 2; 00250 00251 for ( ; __trip_count > 0 ; --__trip_count) { 00252 if (__pred(*__first)) return __first; 00253 ++__first; 00254 00255 if (__pred(*__first)) return __first; 00256 ++__first; 00257 00258 if (__pred(*__first)) return __first; 00259 ++__first; 00260 00261 if (__pred(*__first)) return __first; 00262 ++__first; 00263 } 00264 00265 switch(__last - __first) { 00266 case 3: 00267 if (__pred(*__first)) return __first; 00268 ++__first; 00269 case 2: 00270 if (__pred(*__first)) return __first; 00271 ++__first; 00272 case 1: 00273 if (__pred(*__first)) return __first; 00274 ++__first; 00275 case 0: 00276 default: 00277 return __last; 00278 } 00279 } 00280 00289 template<typename _InputIter, typename _Tp> 00290 inline _InputIter 00291 find(_InputIter __first, _InputIter __last, 00292 const _Tp& __val) 00293 { 00294 // concept requirements 00295 __glibcpp_function_requires(_InputIteratorConcept<_InputIter>) 00296 __glibcpp_function_requires(_EqualOpConcept< 00297 typename iterator_traits<_InputIter>::value_type, _Tp>) 00298 return find(__first, __last, __val, __iterator_category(__first)); 00299 } 00300 00309 template<typename _InputIter, typename _Predicate> 00310 inline _InputIter 00311 find_if(_InputIter __first, _InputIter __last, 00312 _Predicate __pred) 00313 { 00314 // concept requirements 00315 __glibcpp_function_requires(_InputIteratorConcept<_InputIter>) 00316 __glibcpp_function_requires(_UnaryPredicateConcept<_Predicate, 00317 typename iterator_traits<_InputIter>::value_type>) 00318 return find_if(__first, __last, __pred, __iterator_category(__first)); 00319 } 00320 00329 template<typename _ForwardIter> 00330 _ForwardIter 00331 adjacent_find(_ForwardIter __first, _ForwardIter __last) 00332 { 00333 // concept requirements 00334 __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter>) 00335 __glibcpp_function_requires(_EqualityComparableConcept< 00336 typename iterator_traits<_ForwardIter>::value_type>) 00337 if (__first == __last) 00338 return __last; 00339 _ForwardIter __next = __first; 00340 while(++__next != __last) { 00341 if (*__first == *__next) 00342 return __first; 00343 __first = __next; 00344 } 00345 return __last; 00346 } 00347 00358 template<typename _ForwardIter, typename _BinaryPredicate> 00359 _ForwardIter 00360 adjacent_find(_ForwardIter __first, _ForwardIter __last, 00361 _BinaryPredicate __binary_pred) 00362 { 00363 // concept requirements 00364 __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter>) 00365 __glibcpp_function_requires(_BinaryPredicateConcept<_BinaryPredicate, 00366 typename iterator_traits<_ForwardIter>::value_type, 00367 typename iterator_traits<_ForwardIter>::value_type>) 00368 if (__first == __last) 00369 return __last; 00370 _ForwardIter __next = __first; 00371 while(++__next != __last) { 00372 if (__binary_pred(*__first, *__next)) 00373 return __first; 00374 __first = __next; 00375 } 00376 return __last; 00377 } 00378 00387 template<typename _InputIter, typename _Tp> 00388 typename iterator_traits<_InputIter>::difference_type 00389 count(_InputIter __first, _InputIter __last, const _Tp& __value) 00390 { 00391 // concept requirements 00392 __glibcpp_function_requires(_InputIteratorConcept<_InputIter>) 00393 __glibcpp_function_requires(_EqualityComparableConcept< 00394 typename iterator_traits<_InputIter>::value_type >) 00395 __glibcpp_function_requires(_EqualityComparableConcept<_Tp>) 00396 typename iterator_traits<_InputIter>::difference_type __n = 0; 00397 for ( ; __first != __last; ++__first) 00398 if (*__first == __value) 00399 ++__n; 00400 return __n; 00401 } 00402 00411 template<typename _InputIter, typename _Predicate> 00412 typename iterator_traits<_InputIter>::difference_type 00413 count_if(_InputIter __first, _InputIter __last, _Predicate __pred) 00414 { 00415 // concept requirements 00416 __glibcpp_function_requires(_InputIteratorConcept<_InputIter>) 00417 __glibcpp_function_requires(_UnaryPredicateConcept<_Predicate, 00418 typename iterator_traits<_InputIter>::value_type>) 00419 typename iterator_traits<_InputIter>::difference_type __n = 0; 00420 for ( ; __first != __last; ++__first) 00421 if (__pred(*__first)) 00422 ++__n; 00423 return __n; 00424 } 00425 00426 00450 template<typename _ForwardIter1, typename _ForwardIter2> 00451 _ForwardIter1 00452 search(_ForwardIter1 __first1, _ForwardIter1 __last1, 00453 _ForwardIter2 __first2, _ForwardIter2 __last2) 00454 { 00455 // concept requirements 00456 __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter1>) 00457 __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter2>) 00458 __glibcpp_function_requires(_EqualOpConcept< 00459 typename iterator_traits<_ForwardIter1>::value_type, 00460 typename iterator_traits<_ForwardIter2>::value_type>) 00461 00462 // Test for empty ranges 00463 if (__first1 == __last1 || __first2 == __last2) 00464 return __first1; 00465 00466 // Test for a pattern of length 1. 00467 _ForwardIter2 __tmp(__first2); 00468 ++__tmp; 00469 if (__tmp == __last2) 00470 return find(__first1, __last1, *__first2); 00471 00472 // General case. 00473 00474 _ForwardIter2 __p1, __p; 00475 00476 __p1 = __first2; ++__p1; 00477 00478 _ForwardIter1 __current = __first1; 00479 00480 while (__first1 != __last1) { 00481 __first1 = find(__first1, __last1, *__first2); 00482 if (__first1 == __last1) 00483 return __last1; 00484 00485 __p = __p1; 00486 __current = __first1; 00487 if (++__current == __last1) 00488 return __last1; 00489 00490 while (*__current == *__p) { 00491 if (++__p == __last2) 00492 return __first1; 00493 if (++__current == __last1) 00494 return __last1; 00495 } 00496 00497 ++__first1; 00498 } 00499 return __first1; 00500 } 00501 00522 template<typename _ForwardIter1, typename _ForwardIter2, typename _BinaryPred> 00523 _ForwardIter1 00524 search(_ForwardIter1 __first1, _ForwardIter1 __last1, 00525 _ForwardIter2 __first2, _ForwardIter2 __last2, 00526 _BinaryPred __predicate) 00527 { 00528 // concept requirements 00529 __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter1>) 00530 __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter2>) 00531 __glibcpp_function_requires(_BinaryPredicateConcept<_BinaryPred, 00532 typename iterator_traits<_ForwardIter1>::value_type, 00533 typename iterator_traits<_ForwardIter2>::value_type>) 00534 00535 // Test for empty ranges 00536 if (__first1 == __last1 || __first2 == __last2) 00537 return __first1; 00538 00539 // Test for a pattern of length 1. 00540 _ForwardIter2 __tmp(__first2); 00541 ++__tmp; 00542 if (__tmp == __last2) { 00543 while (__first1 != __last1 && !__predicate(*__first1, *__first2)) 00544 ++__first1; 00545 return __first1; 00546 } 00547 00548 // General case. 00549 00550 _ForwardIter2 __p1, __p; 00551 00552 __p1 = __first2; ++__p1; 00553 00554 _ForwardIter1 __current = __first1; 00555 00556 while (__first1 != __last1) { 00557 while (__first1 != __last1) { 00558 if (__predicate(*__first1, *__first2)) 00559 break; 00560 ++__first1; 00561 } 00562 while (__first1 != __last1 && !__predicate(*__first1, *__first2)) 00563 ++__first1; 00564 if (__first1 == __last1) 00565 return __last1; 00566 00567 __p = __p1; 00568 __current = __first1; 00569 if (++__current == __last1) return __last1; 00570 00571 while (__predicate(*__current, *__p)) { 00572 if (++__p == __last2) 00573 return __first1; 00574 if (++__current == __last1) 00575 return __last1; 00576 } 00577 00578 ++__first1; 00579 } 00580 return __first1; 00581 } 00582 00596 template<typename _ForwardIter, typename _Integer, typename _Tp> 00597 _ForwardIter 00598 search_n(_ForwardIter __first, _ForwardIter __last, 00599 _Integer __count, const _Tp& __val) 00600 { 00601 // concept requirements 00602 __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter>) 00603 __glibcpp_function_requires(_EqualityComparableConcept< 00604 typename iterator_traits<_ForwardIter>::value_type>) 00605 __glibcpp_function_requires(_EqualityComparableConcept<_Tp>) 00606 00607 if (__count <= 0) 00608 return __first; 00609 else { 00610 __first = find(__first, __last, __val); 00611 while (__first != __last) { 00612 _Integer __n = __count - 1; 00613 _ForwardIter __i = __first; 00614 ++__i; 00615 while (__i != __last && __n != 0 && *__i == __val) { 00616 ++__i; 00617 --__n; 00618 } 00619 if (__n == 0) 00620 return __first; 00621 else 00622 __first = find(__i, __last, __val); 00623 } 00624 return __last; 00625 } 00626 } 00627 00643 template<typename _ForwardIter, typename _Integer, typename _Tp, 00644 typename _BinaryPred> 00645 _ForwardIter 00646 search_n(_ForwardIter __first, _ForwardIter __last, 00647 _Integer __count, const _Tp& __val, 00648 _BinaryPred __binary_pred) 00649 { 00650 // concept requirements 00651 __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter>) 00652 __glibcpp_function_requires(_BinaryPredicateConcept<_BinaryPred, 00653 typename iterator_traits<_ForwardIter>::value_type, _Tp>) 00654 00655 if (__count <= 0) 00656 return __first; 00657 else { 00658 while (__first != __last) { 00659 if (__binary_pred(*__first, __val)) 00660 break; 00661 ++__first; 00662 } 00663 while (__first != __last) { 00664 _Integer __n = __count - 1; 00665 _ForwardIter __i = __first; 00666 ++__i; 00667 while (__i != __last && __n != 0 && __binary_pred(*__i, __val)) { 00668 ++__i; 00669 --__n; 00670 } 00671 if (__n == 0) 00672 return __first; 00673 else { 00674 while (__i != __last) { 00675 if (__binary_pred(*__i, __val)) 00676 break; 00677 ++__i; 00678 } 00679 __first = __i; 00680 } 00681 } 00682 return __last; 00683 } 00684 } 00685 00697 template<typename _ForwardIter1, typename _ForwardIter2> 00698 _ForwardIter2 00699 swap_ranges(_ForwardIter1 __first1, _ForwardIter1 __last1, 00700 _ForwardIter2 __first2) 00701 { 00702 // concept requirements 00703 __glibcpp_function_requires(_Mutable_ForwardIteratorConcept<_ForwardIter1>) 00704 __glibcpp_function_requires(_Mutable_ForwardIteratorConcept<_ForwardIter2>) 00705 __glibcpp_function_requires(_ConvertibleConcept< 00706 typename iterator_traits<_ForwardIter1>::value_type, 00707 typename iterator_traits<_ForwardIter2>::value_type>) 00708 __glibcpp_function_requires(_ConvertibleConcept< 00709 typename iterator_traits<_ForwardIter2>::value_type, 00710 typename iterator_traits<_ForwardIter1>::value_type>) 00711 00712 for ( ; __first1 != __last1; ++__first1, ++__first2) 00713 iter_swap(__first1, __first2); 00714 return __first2; 00715 } 00716 00732 template<typename _InputIter, typename _OutputIter, typename _UnaryOperation> 00733 _OutputIter 00734 transform(_InputIter __first, _InputIter __last, 00735 _OutputIter __result, _UnaryOperation __unary_op) 00736 { 00737 // concept requirements 00738 __glibcpp_function_requires(_InputIteratorConcept<_InputIter>) 00739 __glibcpp_function_requires(_OutputIteratorConcept<_OutputIter, 00740 // "the type returned by a _UnaryOperation" 00741 __typeof__(__unary_op(*__first))>) 00742 00743 for ( ; __first != __last; ++__first, ++__result) 00744 *__result = __unary_op(*__first); 00745 return __result; 00746 } 00747 00765 template<typename _InputIter1, typename _InputIter2, typename _OutputIter, 00766 typename _BinaryOperation> 00767 _OutputIter 00768 transform(_InputIter1 __first1, _InputIter1 __last1, 00769 _InputIter2 __first2, _OutputIter __result, 00770 _BinaryOperation __binary_op) 00771 { 00772 // concept requirements 00773 __glibcpp_function_requires(_InputIteratorConcept<_InputIter1>) 00774 __glibcpp_function_requires(_InputIteratorConcept<_InputIter2>) 00775 __glibcpp_function_requires(_OutputIteratorConcept<_OutputIter, 00776 // "the type returned by a _BinaryOperation" 00777 __typeof__(__binary_op(*__first1,*__first2))>) 00778 00779 for ( ; __first1 != __last1; ++__first1, ++__first2, ++__result) 00780 *__result = __binary_op(*__first1, *__first2); 00781 return __result; 00782 } 00783 00796 template<typename _ForwardIter, typename _Tp> 00797 void 00798 replace(_ForwardIter __first, _ForwardIter __last, 00799 const _Tp& __old_value, const _Tp& __new_value) 00800 { 00801 // concept requirements 00802 __glibcpp_function_requires(_Mutable_ForwardIteratorConcept<_ForwardIter>) 00803 __glibcpp_function_requires(_EqualOpConcept< 00804 typename iterator_traits<_ForwardIter>::value_type, _Tp>) 00805 __glibcpp_function_requires(_ConvertibleConcept<_Tp, 00806 typename iterator_traits<_ForwardIter>::value_type>) 00807 00808 for ( ; __first != __last; ++__first) 00809 if (*__first == __old_value) 00810 *__first = __new_value; 00811 } 00812 00825 template<typename _ForwardIter, typename _Predicate, typename _Tp> 00826 void 00827 replace_if(_ForwardIter __first, _ForwardIter __last, 00828 _Predicate __pred, const _Tp& __new_value) 00829 { 00830 // concept requirements 00831 __glibcpp_function_requires(_Mutable_ForwardIteratorConcept<_ForwardIter>) 00832 __glibcpp_function_requires(_ConvertibleConcept<_Tp, 00833 typename iterator_traits<_ForwardIter>::value_type>) 00834 __glibcpp_function_requires(_UnaryPredicateConcept<_Predicate, 00835 typename iterator_traits<_ForwardIter>::value_type>) 00836 00837 for ( ; __first != __last; ++__first) 00838 if (__pred(*__first)) 00839 *__first = __new_value; 00840 } 00841 00856 template<typename _InputIter, typename _OutputIter, typename _Tp> 00857 _OutputIter 00858 replace_copy(_InputIter __first, _InputIter __last, 00859 _OutputIter __result, 00860 const _Tp& __old_value, const _Tp& __new_value) 00861 { 00862 // concept requirements 00863 __glibcpp_function_requires(_InputIteratorConcept<_InputIter>) 00864 __glibcpp_function_requires(_OutputIteratorConcept<_OutputIter, 00865 typename iterator_traits<_InputIter>::value_type>) 00866 __glibcpp_function_requires(_EqualOpConcept< 00867 typename iterator_traits<_InputIter>::value_type, _Tp>) 00868 00869 for ( ; __first != __last; ++__first, ++__result) 00870 *__result = *__first == __old_value ? __new_value : *__first; 00871 return __result; 00872 } 00873 00888 template<typename _InputIter, typename _OutputIter, typename _Predicate, 00889 typename _Tp> 00890 _OutputIter 00891 replace_copy_if(_InputIter __first, _InputIter __last, 00892 _OutputIter __result, 00893 _Predicate __pred, const _Tp& __new_value) 00894 { 00895 // concept requirements 00896 __glibcpp_function_requires(_InputIteratorConcept<_InputIter>) 00897 __glibcpp_function_requires(_OutputIteratorConcept<_OutputIter, 00898 typename iterator_traits<_InputIter>::value_type>) 00899 __glibcpp_function_requires(_UnaryPredicateConcept<_Predicate, 00900 typename iterator_traits<_InputIter>::value_type>) 00901 00902 for ( ; __first != __last; ++__first, ++__result) 00903 *__result = __pred(*__first) ? __new_value : *__first; 00904 return __result; 00905 } 00906 00918 template<typename _ForwardIter, typename _Generator> 00919 void 00920 generate(_ForwardIter __first, _ForwardIter __last, _Generator __gen) 00921 { 00922 // concept requirements 00923 __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter>) 00924 __glibcpp_function_requires(_GeneratorConcept<_Generator, 00925 typename iterator_traits<_ForwardIter>::value_type>) 00926 00927 for ( ; __first != __last; ++__first) 00928 *__first = __gen(); 00929 } 00930 00942 template<typename _OutputIter, typename _Size, typename _Generator> 00943 _OutputIter 00944 generate_n(_OutputIter __first, _Size __n, _Generator __gen) 00945 { 00946 // concept requirements 00947 __glibcpp_function_requires(_OutputIteratorConcept<_OutputIter, 00948 // "the type returned by a _Generator" 00949 __typeof__(gen())>) 00950 00951 for ( ; __n > 0; --__n, ++__first) 00952 *__first = __gen(); 00953 return __first; 00954 } 00955 00969 template<typename _InputIter, typename _OutputIter, typename _Tp> 00970 _OutputIter 00971 remove_copy(_InputIter __first, _InputIter __last, 00972 _OutputIter __result, const _Tp& __value) 00973 { 00974 // concept requirements 00975 __glibcpp_function_requires(_InputIteratorConcept<_InputIter>) 00976 __glibcpp_function_requires(_OutputIteratorConcept<_OutputIter, 00977 typename iterator_traits<_InputIter>::value_type>) 00978 __glibcpp_function_requires(_EqualOpConcept< 00979 typename iterator_traits<_InputIter>::value_type, _Tp>) 00980 00981 for ( ; __first != __last; ++__first) 00982 if (!(*__first == __value)) { 00983 *__result = *__first; 00984 ++__result; 00985 } 00986 return __result; 00987 } 00988 01003 template<typename _InputIter, typename _OutputIter, typename _Predicate> 01004 _OutputIter 01005 remove_copy_if(_InputIter __first, _InputIter __last, 01006 _OutputIter __result, _Predicate __pred) 01007 { 01008 // concept requirements 01009 __glibcpp_function_requires(_InputIteratorConcept<_InputIter>) 01010 __glibcpp_function_requires(_OutputIteratorConcept<_OutputIter, 01011 typename iterator_traits<_InputIter>::value_type>) 01012 __glibcpp_function_requires(_UnaryPredicateConcept<_Predicate, 01013 typename iterator_traits<_InputIter>::value_type>) 01014 01015 for ( ; __first != __last; ++__first) 01016 if (!__pred(*__first)) { 01017 *__result = *__first; 01018 ++__result; 01019 } 01020 return __result; 01021 } 01022 01039 template<typename _ForwardIter, typename _Tp> 01040 _ForwardIter 01041 remove(_ForwardIter __first, _ForwardIter __last, 01042 const _Tp& __value) 01043 { 01044 // concept requirements 01045 __glibcpp_function_requires(_Mutable_ForwardIteratorConcept<_ForwardIter>) 01046 __glibcpp_function_requires(_ConvertibleConcept<_Tp, 01047 typename iterator_traits<_ForwardIter>::value_type>) 01048 __glibcpp_function_requires(_EqualOpConcept< 01049 typename iterator_traits<_ForwardIter>::value_type, _Tp>) 01050 01051 __first = find(__first, __last, __value); 01052 _ForwardIter __i = __first; 01053 return __first == __last ? __first 01054 : remove_copy(++__i, __last, __first, __value); 01055 } 01056 01073 template<typename _ForwardIter, typename _Predicate> 01074 _ForwardIter 01075 remove_if(_ForwardIter __first, _ForwardIter __last, 01076 _Predicate __pred) 01077 { 01078 // concept requirements 01079 __glibcpp_function_requires(_Mutable_ForwardIteratorConcept<_ForwardIter>) 01080 __glibcpp_function_requires(_UnaryPredicateConcept<_Predicate, 01081 typename iterator_traits<_ForwardIter>::value_type>) 01082 01083 __first = find_if(__first, __last, __pred); 01084 _ForwardIter __i = __first; 01085 return __first == __last ? __first 01086 : remove_copy_if(++__i, __last, __first, __pred); 01087 } 01088 01095 template<typename _InputIter, typename _OutputIter> 01096 _OutputIter 01097 __unique_copy(_InputIter __first, _InputIter __last, 01098 _OutputIter __result, 01099 output_iterator_tag) 01100 { 01101 // concept requirements -- taken care of in dispatching function 01102 typename iterator_traits<_InputIter>::value_type __value = *__first; 01103 *__result = __value; 01104 while (++__first != __last) 01105 if (!(__value == *__first)) { 01106 __value = *__first; 01107 *++__result = __value; 01108 } 01109 return ++__result; 01110 } 01111 01118 template<typename _InputIter, typename _ForwardIter> 01119 _ForwardIter 01120 __unique_copy(_InputIter __first, _InputIter __last, 01121 _ForwardIter __result, 01122 forward_iterator_tag) 01123 { 01124 // concept requirements -- taken care of in dispatching function 01125 *__result = *__first; 01126 while (++__first != __last) 01127 if (!(*__result == *__first)) 01128 *++__result = *__first; 01129 return ++__result; 01130 } 01131 01145 template<typename _InputIter, typename _OutputIter> 01146 inline _OutputIter 01147 unique_copy(_InputIter __first, _InputIter __last, 01148 _OutputIter __result) 01149 { 01150 // concept requirements 01151 __glibcpp_function_requires(_InputIteratorConcept<_InputIter>) 01152 __glibcpp_function_requires(_OutputIteratorConcept<_OutputIter, 01153 typename iterator_traits<_InputIter>::value_type>) 01154 __glibcpp_function_requires(_EqualityComparableConcept< 01155 typename iterator_traits<_InputIter>::value_type>) 01156 01157 typedef typename iterator_traits<_OutputIter>::iterator_category _IterType; 01158 01159 if (__first == __last) return __result; 01160 return __unique_copy(__first, __last, __result, _IterType()); 01161 } 01162 01170 template<typename _InputIter, typename _OutputIter, typename _BinaryPredicate> 01171 _OutputIter 01172 __unique_copy(_InputIter __first, _InputIter __last, 01173 _OutputIter __result, 01174 _BinaryPredicate __binary_pred, 01175 output_iterator_tag) 01176 { 01177 // concept requirements -- iterators already checked 01178 __glibcpp_function_requires(_BinaryPredicateConcept<_BinaryPredicate, 01179 typename iterator_traits<_InputIter>::value_type, 01180 typename iterator_traits<_InputIter>::value_type>) 01181 01182 typename iterator_traits<_InputIter>::value_type __value = *__first; 01183 *__result = __value; 01184 while (++__first != __last) 01185 if (!__binary_pred(__value, *__first)) { 01186 __value = *__first; 01187 *++__result = __value; 01188 } 01189 return ++__result; 01190 } 01191 01199 template<typename _InputIter, typename _ForwardIter, typename _BinaryPredicate> 01200 _ForwardIter 01201 __unique_copy(_InputIter __first, _InputIter __last, 01202 _ForwardIter __result, 01203 _BinaryPredicate __binary_pred, 01204 forward_iterator_tag) 01205 { 01206 // concept requirements -- iterators already checked 01207 __glibcpp_function_requires(_BinaryPredicateConcept<_BinaryPredicate, 01208 typename iterator_traits<_ForwardIter>::value_type, 01209 typename iterator_traits<_InputIter>::value_type>) 01210 01211 *__result = *__first; 01212 while (++__first != __last) 01213 if (!__binary_pred(*__result, *__first)) *++__result = *__first; 01214 return ++__result; 01215 } 01216 01232 template<typename _InputIter, typename _OutputIter, typename _BinaryPredicate> 01233 inline _OutputIter 01234 unique_copy(_InputIter __first, _InputIter __last, 01235 _OutputIter __result, 01236 _BinaryPredicate __binary_pred) 01237 { 01238 // concept requirements -- predicates checked later 01239 __glibcpp_function_requires(_InputIteratorConcept<_InputIter>) 01240 __glibcpp_function_requires(_OutputIteratorConcept<_OutputIter, 01241 typename iterator_traits<_InputIter>::value_type>) 01242 01243 typedef typename iterator_traits<_OutputIter>::iterator_category _IterType; 01244 01245 if (__first == __last) return __result; 01246 return __unique_copy(__first, __last, 01247 __result, __binary_pred, _IterType()); 01248 } 01249 01263 template<typename _ForwardIter> 01264 _ForwardIter 01265 unique(_ForwardIter __first, _ForwardIter __last) 01266 { 01267 // concept requirements 01268 __glibcpp_function_requires(_Mutable_ForwardIteratorConcept<_ForwardIter>) 01269 __glibcpp_function_requires(_EqualityComparableConcept< 01270 typename iterator_traits<_ForwardIter>::value_type>) 01271 01272 __first = adjacent_find(__first, __last); 01273 return unique_copy(__first, __last, __first); 01274 } 01275 01290 template<typename _ForwardIter, typename _BinaryPredicate> 01291 _ForwardIter 01292 unique(_ForwardIter __first, _ForwardIter __last, 01293 _BinaryPredicate __binary_pred) 01294 { 01295 // concept requirements 01296 __glibcpp_function_requires(_Mutable_ForwardIteratorConcept<_ForwardIter>) 01297 __glibcpp_function_requires(_BinaryPredicateConcept<_BinaryPredicate, 01298 typename iterator_traits<_ForwardIter>::value_type, 01299 typename iterator_traits<_ForwardIter>::value_type>) 01300 01301 __first = adjacent_find(__first, __last, __binary_pred); 01302 return unique_copy(__first, __last, __first, __binary_pred); 01303 } 01304 01311 template<typename _BidirectionalIter> 01312 void 01313 __reverse(_BidirectionalIter __first, _BidirectionalIter __last, 01314 bidirectional_iterator_tag) 01315 { 01316 while (true) 01317 if (__first == __last || __first == --__last) 01318 return; 01319 else 01320 iter_swap(__first++, __last); 01321 } 01322 01329 template<typename _RandomAccessIter> 01330 void 01331 __reverse(_RandomAccessIter __first, _RandomAccessIter __last, 01332 random_access_iterator_tag) 01333 { 01334 while (__first < __last) 01335 iter_swap(__first++, --__last); 01336 } 01337 01349 template<typename _BidirectionalIter> 01350 inline void 01351 reverse(_BidirectionalIter __first, _BidirectionalIter __last) 01352 { 01353 // concept requirements 01354 __glibcpp_function_requires(_Mutable_BidirectionalIteratorConcept< 01355 _BidirectionalIter>) 01356 __reverse(__first, __last, __iterator_category(__first)); 01357 } 01358 01374 template<typename _BidirectionalIter, typename _OutputIter> 01375 _OutputIter 01376 reverse_copy(_BidirectionalIter __first, _BidirectionalIter __last, 01377 _OutputIter __result) 01378 { 01379 // concept requirements 01380 __glibcpp_function_requires(_BidirectionalIteratorConcept<_BidirectionalIter>) 01381 __glibcpp_function_requires(_OutputIteratorConcept<_OutputIter, 01382 typename iterator_traits<_BidirectionalIter>::value_type>) 01383 01384 while (__first != __last) { 01385 --__last; 01386 *__result = *__last; 01387 ++__result; 01388 } 01389 return __result; 01390 } 01391 01392 01399 template<typename _EuclideanRingElement> 01400 _EuclideanRingElement 01401 __gcd(_EuclideanRingElement __m, _EuclideanRingElement __n) 01402 { 01403 while (__n != 0) { 01404 _EuclideanRingElement __t = __m % __n; 01405 __m = __n; 01406 __n = __t; 01407 } 01408 return __m; 01409 } 01410 01416 template<typename _ForwardIter> 01417 void 01418 __rotate(_ForwardIter __first, 01419 _ForwardIter __middle, 01420 _ForwardIter __last, 01421 forward_iterator_tag) 01422 { 01423 if ((__first == __middle) || (__last == __middle)) 01424 return; 01425 01426 _ForwardIter __first2 = __middle; 01427 do { 01428 swap(*__first++, *__first2++); 01429 if (__first == __middle) 01430 __middle = __first2; 01431 } while (__first2 != __last); 01432 01433 __first2 = __middle; 01434 01435 while (__first2 != __last) { 01436 swap(*__first++, *__first2++); 01437 if (__first == __middle) 01438 __middle = __first2; 01439 else if (__first2 == __last) 01440 __first2 = __middle; 01441 } 01442 } 01443 01449 template<typename _BidirectionalIter> 01450 void 01451 __rotate(_BidirectionalIter __first, 01452 _BidirectionalIter __middle, 01453 _BidirectionalIter __last, 01454 bidirectional_iterator_tag) 01455 { 01456 // concept requirements 01457 __glibcpp_function_requires(_Mutable_BidirectionalIteratorConcept< 01458 _BidirectionalIter>) 01459 01460 if ((__first == __middle) || (__last == __middle)) 01461 return; 01462 01463 __reverse(__first, __middle, bidirectional_iterator_tag()); 01464 __reverse(__middle, __last, bidirectional_iterator_tag()); 01465 01466 while (__first != __middle && __middle != __last) 01467 swap (*__first++, *--__last); 01468 01469 if (__first == __middle) { 01470 __reverse(__middle, __last, bidirectional_iterator_tag()); 01471 } 01472 else { 01473 __reverse(__first, __middle, bidirectional_iterator_tag()); 01474 } 01475 } 01476 01482 template<typename _RandomAccessIter> 01483 void 01484 __rotate(_RandomAccessIter __first, 01485 _RandomAccessIter __middle, 01486 _RandomAccessIter __last, 01487 random_access_iterator_tag) 01488 { 01489 // concept requirements 01490 __glibcpp_function_requires(_Mutable_RandomAccessIteratorConcept< 01491 _RandomAccessIter>) 01492 01493 if ((__first == __middle) || (__last == __middle)) 01494 return; 01495 01496 typedef typename iterator_traits<_RandomAccessIter>::difference_type _Distance; 01497 typedef typename iterator_traits<_RandomAccessIter>::value_type _ValueType; 01498 01499 _Distance __n = __last - __first; 01500 _Distance __k = __middle - __first; 01501 _Distance __l = __n - __k; 01502 01503 if (__k == __l) { 01504 swap_ranges(__first, __middle, __middle); 01505 return; 01506 } 01507 01508 _Distance __d = __gcd(__n, __k); 01509 01510 for (_Distance __i = 0; __i < __d; __i++) { 01511 _ValueType __tmp = *__first; 01512 _RandomAccessIter __p = __first; 01513 01514 if (__k < __l) { 01515 for (_Distance __j = 0; __j < __l/__d; __j++) { 01516 if (__p > __first + __l) { 01517 *__p = *(__p - __l); 01518 __p -= __l; 01519 } 01520 01521 *__p = *(__p + __k); 01522 __p += __k; 01523 } 01524 } 01525 01526 else { 01527 for (_Distance __j = 0; __j < __k/__d - 1; __j ++) { 01528 if (__p < __last - __k) { 01529 *__p = *(__p + __k); 01530 __p += __k; 01531 } 01532 01533 *__p = * (__p - __l); 01534 __p -= __l; 01535 } 01536 } 01537 01538 *__p = __tmp; 01539 ++__first; 01540 } 01541 } 01542 01561 template<typename _ForwardIter> 01562 inline void 01563 rotate(_ForwardIter __first, _ForwardIter __middle, _ForwardIter __last) 01564 { 01565 // concept requirements 01566 __glibcpp_function_requires(_Mutable_ForwardIteratorConcept<_ForwardIter>) 01567 01568 typedef typename iterator_traits<_ForwardIter>::iterator_category _IterType; 01569 __rotate(__first, __middle, __last, _IterType()); 01570 } 01571 01589 template<typename _ForwardIter, typename _OutputIter> 01590 _OutputIter 01591 rotate_copy(_ForwardIter __first, _ForwardIter __middle, 01592 _ForwardIter __last, _OutputIter __result) 01593 { 01594 // concept requirements 01595 __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter>) 01596 __glibcpp_function_requires(_OutputIteratorConcept<_OutputIter, 01597 typename iterator_traits<_ForwardIter>::value_type>) 01598 01599 return copy(__first, __middle, copy(__middle, __last, __result)); 01600 } 01601 01602 01612 template<typename _Distance> 01613 inline _Distance 01614 __random_number(_Distance __n) 01615 { 01616 #ifdef _GLIBCPP_HAVE_DRAND48 01617 return lrand48() % __n; 01618 #else 01619 return rand() % __n; 01620 #endif 01621 } 01622 01623 01634 template<typename _RandomAccessIter> 01635 inline void 01636 random_shuffle(_RandomAccessIter __first, _RandomAccessIter __last) 01637 { 01638 // concept requirements 01639 __glibcpp_function_requires(_Mutable_RandomAccessIteratorConcept< 01640 _RandomAccessIter>) 01641 01642 if (__first == __last) return; 01643 for (_RandomAccessIter __i = __first + 1; __i != __last; ++__i) 01644 iter_swap(__i, __first + __random_number((__i - __first) + 1)); 01645 } 01646 01660 template<typename _RandomAccessIter, typename _RandomNumberGenerator> 01661 void 01662 random_shuffle(_RandomAccessIter __first, _RandomAccessIter __last, 01663 _RandomNumberGenerator& __rand) 01664 { 01665 // concept requirements 01666 __glibcpp_function_requires(_Mutable_RandomAccessIteratorConcept< 01667 _RandomAccessIter>) 01668 01669 if (__first == __last) return; 01670 for (_RandomAccessIter __i = __first + 1; __i != __last; ++__i) 01671 iter_swap(__i, __first + __rand((__i - __first) + 1)); 01672 } 01673 01674 01680 template<typename _ForwardIter, typename _Predicate> 01681 _ForwardIter 01682 __partition(_ForwardIter __first, _ForwardIter __last, 01683 _Predicate __pred, 01684 forward_iterator_tag) 01685 { 01686 if (__first == __last) return __first; 01687 01688 while (__pred(*__first)) 01689 if (++__first == __last) return __first; 01690 01691 _ForwardIter __next = __first; 01692 01693 while (++__next != __last) 01694 if (__pred(*__next)) { 01695 swap(*__first, *__next); 01696 ++__first; 01697 } 01698 01699 return __first; 01700 } 01701 01707 template<typename _BidirectionalIter, typename _Predicate> 01708 _BidirectionalIter 01709 __partition(_BidirectionalIter __first, _BidirectionalIter __last, 01710 _Predicate __pred, 01711 bidirectional_iterator_tag) 01712 { 01713 while (true) { 01714 while (true) 01715 if (__first == __last) 01716 return __first; 01717 else if (__pred(*__first)) 01718 ++__first; 01719 else 01720 break; 01721 --__last; 01722 while (true) 01723 if (__first == __last) 01724 return __first; 01725 else if (!__pred(*__last)) 01726 --__last; 01727 else 01728 break; 01729 iter_swap(__first, __last); 01730 ++__first; 01731 } 01732 } 01733 01748 template<typename _ForwardIter, typename _Predicate> 01749 inline _ForwardIter 01750 partition(_ForwardIter __first, _ForwardIter __last, 01751 _Predicate __pred) 01752 { 01753 // concept requirements 01754 __glibcpp_function_requires(_Mutable_ForwardIteratorConcept<_ForwardIter>) 01755 __glibcpp_function_requires(_UnaryPredicateConcept<_Predicate, 01756 typename iterator_traits<_ForwardIter>::value_type>) 01757 01758 return __partition(__first, __last, __pred, __iterator_category(__first)); 01759 } 01760 01761 01767 template<typename _ForwardIter, typename _Predicate, typename _Distance> 01768 _ForwardIter 01769 __inplace_stable_partition(_ForwardIter __first, _ForwardIter __last, 01770 _Predicate __pred, _Distance __len) 01771 { 01772 if (__len == 1) 01773 return __pred(*__first) ? __last : __first; 01774 _ForwardIter __middle = __first; 01775 advance(__middle, __len / 2); 01776 _ForwardIter __begin = __inplace_stable_partition(__first, __middle, 01777 __pred, 01778 __len / 2); 01779 _ForwardIter __end = __inplace_stable_partition(__middle, __last, 01780 __pred, 01781 __len - __len / 2); 01782 rotate(__begin, __middle, __end); 01783 advance(__begin, distance(__middle, __end)); 01784 return __begin; 01785 } 01786 01792 template<typename _ForwardIter, typename _Pointer, typename _Predicate, 01793 typename _Distance> 01794 _ForwardIter 01795 __stable_partition_adaptive(_ForwardIter __first, _ForwardIter __last, 01796 _Predicate __pred, _Distance __len, 01797 _Pointer __buffer, 01798 _Distance __buffer_size) 01799 { 01800 if (__len <= __buffer_size) { 01801 _ForwardIter __result1 = __first; 01802 _Pointer __result2 = __buffer; 01803 for ( ; __first != __last ; ++__first) 01804 if (__pred(*__first)) { 01805 *__result1 = *__first; 01806 ++__result1; 01807 } 01808 else { 01809 *__result2 = *__first; 01810 ++__result2; 01811 } 01812 copy(__buffer, __result2, __result1); 01813 return __result1; 01814 } 01815 else { 01816 _ForwardIter __middle = __first; 01817 advance(__middle, __len / 2); 01818 _ForwardIter __begin = __stable_partition_adaptive(__first, __middle, 01819 __pred, 01820 __len / 2, 01821 __buffer, __buffer_size); 01822 _ForwardIter __end = __stable_partition_adaptive( __middle, __last, 01823 __pred, 01824 __len - __len / 2, 01825 __buffer, __buffer_size); 01826 rotate(__begin, __middle, __end); 01827 advance(__begin, distance(__middle, __end)); 01828 return __begin; 01829 } 01830 } 01831 01848 template<typename _ForwardIter, typename _Predicate> 01849 _ForwardIter 01850 stable_partition(_ForwardIter __first, _ForwardIter __last, 01851 _Predicate __pred) 01852 { 01853 // concept requirements 01854 __glibcpp_function_requires(_Mutable_ForwardIteratorConcept<_ForwardIter>) 01855 __glibcpp_function_requires(_UnaryPredicateConcept<_Predicate, 01856 typename iterator_traits<_ForwardIter>::value_type>) 01857 01858 if (__first == __last) 01859 return __first; 01860 else 01861 { 01862 typedef typename iterator_traits<_ForwardIter>::value_type _ValueType; 01863 typedef typename iterator_traits<_ForwardIter>::difference_type _DistanceType; 01864 01865 _Temporary_buffer<_ForwardIter, _ValueType> __buf(__first, __last); 01866 if (__buf.size() > 0) 01867 return __stable_partition_adaptive(__first, __last, __pred, 01868 _DistanceType(__buf.requested_size()), 01869 __buf.begin(), __buf.size()); 01870 else 01871 return __inplace_stable_partition(__first, __last, __pred, 01872 _DistanceType(__buf.requested_size())); 01873 } 01874 } 01875 01881 template<typename _RandomAccessIter, typename _Tp> 01882 _RandomAccessIter 01883 __unguarded_partition(_RandomAccessIter __first, _RandomAccessIter __last, 01884 _Tp __pivot) 01885 { 01886 while (true) { 01887 while (*__first < __pivot) 01888 ++__first; 01889 --__last; 01890 while (__pivot < *__last) 01891 --__last; 01892 if (!(__first < __last)) 01893 return __first; 01894 iter_swap(__first, __last); 01895 ++__first; 01896 } 01897 } 01898 01904 template<typename _RandomAccessIter, typename _Tp, typename _Compare> 01905 _RandomAccessIter 01906 __unguarded_partition(_RandomAccessIter __first, _RandomAccessIter __last, 01907 _Tp __pivot, _Compare __comp) 01908 { 01909 while (true) { 01910 while (__comp(*__first, __pivot)) 01911 ++__first; 01912 --__last; 01913 while (__comp(__pivot, *__last)) 01914 --__last; 01915 if (!(__first < __last)) 01916 return __first; 01917 iter_swap(__first, __last); 01918 ++__first; 01919 } 01920 } 01921 01922 01929 enum { _M_threshold = 16 }; 01930 01936 template<typename _RandomAccessIter, typename _Tp> 01937 void 01938 __unguarded_linear_insert(_RandomAccessIter __last, _Tp __val) 01939 { 01940 _RandomAccessIter __next = __last; 01941 --__next; 01942 while (__val < *__next) { 01943 *__last = *__next; 01944 __last = __next; 01945 --__next; 01946 } 01947 *__last = __val; 01948 } 01949 01955 template<typename _RandomAccessIter, typename _Tp, typename _Compare> 01956 void 01957 __unguarded_linear_insert(_RandomAccessIter __last, _Tp __val, _Compare __comp) 01958 { 01959 _RandomAccessIter __next = __last; 01960 --__next; 01961 while (__comp(__val, *__next)) { 01962 *__last = *__next; 01963 __last = __next; 01964 --__next; 01965 } 01966 *__last = __val; 01967 } 01968 01974 template<typename _RandomAccessIter> 01975 void 01976 __insertion_sort(_RandomAccessIter __first, _RandomAccessIter __last) 01977 { 01978 if (__first == __last) return; 01979 01980 for (_RandomAccessIter __i = __first + 1; __i != __last; ++__i) 01981 { 01982 typename iterator_traits<_RandomAccessIter>::value_type __val = *__i; 01983 if (__val < *__first) { 01984 copy_backward(__first, __i, __i + 1); 01985 *__first = __val; 01986 } 01987 else 01988 __unguarded_linear_insert(__i, __val); 01989 } 01990 } 01991 01997 template<typename _RandomAccessIter, typename _Compare> 01998 void 01999 __insertion_sort(_RandomAccessIter __first, _RandomAccessIter __last, 02000 _Compare __comp) 02001 { 02002 if (__first == __last) return; 02003 02004 for (_RandomAccessIter __i = __first + 1; __i != __last; ++__i) 02005 { 02006 typename iterator_traits<_RandomAccessIter>::value_type __val = *__i; 02007 if (__comp(__val, *__first)) { 02008 copy_backward(__first, __i, __i + 1); 02009 *__first = __val; 02010 } 02011 else 02012 __unguarded_linear_insert(__i, __val, __comp); 02013 } 02014 } 02015 02021 template<typename _RandomAccessIter> 02022 inline void 02023 __unguarded_insertion_sort(_RandomAccessIter __first, _RandomAccessIter __last) 02024 { 02025 typedef typename iterator_traits<_RandomAccessIter>::value_type _ValueType; 02026 02027 for (_RandomAccessIter __i = __first; __i != __last; ++__i) 02028 __unguarded_linear_insert(__i, _ValueType(*__i)); 02029 } 02030 02036 template<typename _RandomAccessIter, typename _Compare> 02037 inline void 02038 __unguarded_insertion_sort(_RandomAccessIter __first, _RandomAccessIter __last, 02039 _Compare __comp) 02040 { 02041 typedef typename iterator_traits<_RandomAccessIter>::value_type _ValueType; 02042 02043 for (_RandomAccessIter __i = __first; __i != __last; ++__i) 02044 __unguarded_linear_insert(__i, _ValueType(*__i), __comp); 02045 } 02046 02052 template<typename _RandomAccessIter> 02053 void 02054 __final_insertion_sort(_RandomAccessIter __first, _RandomAccessIter __last) 02055 { 02056 if (__last - __first > _M_threshold) { 02057 __insertion_sort(__first, __first + _M_threshold); 02058 __unguarded_insertion_sort(__first + _M_threshold, __last); 02059 } 02060 else 02061 __insertion_sort(__first, __last); 02062 } 02063 02069 template<typename _RandomAccessIter, typename _Compare> 02070 void 02071 __final_insertion_sort(_RandomAccessIter __first, _RandomAccessIter __last, 02072 _Compare __comp) 02073 { 02074 if (__last - __first > _M_threshold) { 02075 __insertion_sort(__first, __first + _M_threshold, __comp); 02076 __unguarded_insertion_sort(__first + _M_threshold, __last, __comp); 02077 } 02078 else 02079 __insertion_sort(__first, __last, __comp); 02080 } 02081 02087 template<typename _Size> 02088 inline _Size 02089 __lg(_Size __n) 02090 { 02091 _Size __k; 02092 for (__k = 0; __n != 1; __n >>= 1) ++__k; 02093 return __k; 02094 } 02095 02101 template<typename _RandomAccessIter, typename _Size> 02102 void 02103 __introsort_loop(_RandomAccessIter __first, _RandomAccessIter __last, 02104 _Size __depth_limit) 02105 { 02106 typedef typename iterator_traits<_RandomAccessIter>::value_type _ValueType; 02107 02108 while (__last - __first > _M_threshold) { 02109 if (__depth_limit == 0) { 02110 partial_sort(__first, __last, __last); 02111 return; 02112 } 02113 --__depth_limit; 02114 _RandomAccessIter __cut = 02115 __unguarded_partition(__first, __last, 02116 _ValueType(__median(*__first, 02117 *(__first + (__last - __first)/2), 02118 *(__last - 1)))); 02119 __introsort_loop(__cut, __last, __depth_limit); 02120 __last = __cut; 02121 } 02122 } 02123 02129 template<typename _RandomAccessIter, typename _Size, typename _Compare> 02130 void 02131 __introsort_loop(_RandomAccessIter __first, _RandomAccessIter __last, 02132 _Size __depth_limit, _Compare __comp) 02133 { 02134 typedef typename iterator_traits<_RandomAccessIter>::value_type _ValueType; 02135 02136 while (__last - __first > _M_threshold) { 02137 if (__depth_limit == 0) { 02138 partial_sort(__first, __last, __last, __comp); 02139 return; 02140 } 02141 --__depth_limit; 02142 _RandomAccessIter __cut = 02143 __unguarded_partition(__first, __last, 02144 _ValueType(__median(*__first, 02145 *(__first + (__last - __first)/2), 02146 *(__last - 1), __comp)), 02147 __comp); 02148 __introsort_loop(__cut, __last, __depth_limit, __comp); 02149 __last = __cut; 02150 } 02151 } 02152 02166 template<typename _RandomAccessIter> 02167 inline void 02168 sort(_RandomAccessIter __first, _RandomAccessIter __last) 02169 { 02170 typedef typename iterator_traits<_RandomAccessIter>::value_type _ValueType; 02171 02172 // concept requirements 02173 __glibcpp_function_requires(_Mutable_RandomAccessIteratorConcept< 02174 _RandomAccessIter>) 02175 __glibcpp_function_requires(_LessThanComparableConcept<_ValueType>) 02176 02177 if (__first != __last) { 02178 __introsort_loop(__first, __last, __lg(__last - __first) * 2); 02179 __final_insertion_sort(__first, __last); 02180 } 02181 } 02182 02197 template<typename _RandomAccessIter, typename _Compare> 02198 inline void 02199 sort(_RandomAccessIter __first, _RandomAccessIter __last, _Compare __comp) 02200 { 02201 typedef typename iterator_traits<_RandomAccessIter>::value_type _ValueType; 02202 02203 // concept requirements 02204 __glibcpp_function_requires(_Mutable_RandomAccessIteratorConcept< 02205 _RandomAccessIter>) 02206 __glibcpp_function_requires(_BinaryPredicateConcept<_Compare, _ValueType, _ValueType>) 02207 02208 if (__first != __last) { 02209 __introsort_loop(__first, __last, __lg(__last - __first) * 2, __comp); 02210 __final_insertion_sort(__first, __last, __comp); 02211 } 02212 } 02213 02214 02220 template<typename _RandomAccessIter> 02221 void 02222 __inplace_stable_sort(_RandomAccessIter __first, _RandomAccessIter __last) 02223 { 02224 if (__last - __first < 15) { 02225 __insertion_sort(__first, __last); 02226 return; 02227 } 02228 _RandomAccessIter __middle = __first + (__last - __first) / 2; 02229 __inplace_stable_sort(__first, __middle); 02230 __inplace_stable_sort(__middle, __last); 02231 __merge_without_buffer(__first, __middle, __last, 02232 __middle - __first, 02233 __last - __middle); 02234 } 02235 02241 template<typename _RandomAccessIter, typename _Compare> 02242 void 02243 __inplace_stable_sort(_RandomAccessIter __first, _RandomAccessIter __last, 02244 _Compare __comp) 02245 { 02246 if (__last - __first < 15) { 02247 __insertion_sort(__first, __last, __comp); 02248 return; 02249 } 02250 _RandomAccessIter __middle = __first + (__last - __first) / 2; 02251 __inplace_stable_sort(__first, __middle, __comp); 02252 __inplace_stable_sort(__middle, __last, __comp); 02253 __merge_without_buffer(__first, __middle, __last, 02254 __middle - __first, 02255 __last - __middle, 02256 __comp); 02257 } 02258 02259 template<typename _RandomAccessIter1, typename _RandomAccessIter2, 02260 typename _Distance> 02261 void 02262 __merge_sort_loop(_RandomAccessIter1 __first, _RandomAccessIter1 __last, 02263 _RandomAccessIter2 __result, _Distance __step_size) 02264 { 02265 _Distance __two_step = 2 * __step_size; 02266 02267 while (__last - __first >= __two_step) { 02268 __result = merge(__first, __first + __step_size, 02269 __first + __step_size, __first + __two_step, 02270 __result); 02271 __first += __two_step; 02272 } 02273 02274 __step_size = min(_Distance(__last - __first), __step_size); 02275 merge(__first, __first + __step_size, __first + __step_size, __last, 02276 __result); 02277 } 02278 02279 template<typename _RandomAccessIter1, typename _RandomAccessIter2, 02280 typename _Distance, typename _Compare> 02281 void 02282 __merge_sort_loop(_RandomAccessIter1 __first, _RandomAccessIter1 __last, 02283 _RandomAccessIter2 __result, _Distance __step_size, 02284 _Compare __comp) 02285 { 02286 _Distance __two_step = 2 * __step_size; 02287 02288 while (__last - __first >= __two_step) { 02289 __result = merge(__first, __first + __step_size, 02290 __first + __step_size, __first + __two_step, 02291 __result, 02292 __comp); 02293 __first += __two_step; 02294 } 02295 __step_size = min(_Distance(__last - __first), __step_size); 02296 02297 merge(__first, __first + __step_size, 02298 __first + __step_size, __last, 02299 __result, 02300 __comp); 02301 } 02302 02303 enum { _M_chunk_size = 7 }; 02304 02305 template<typename _RandomAccessIter, typename _Distance> 02306 void 02307 __chunk_insertion_sort(_RandomAccessIter __first, _RandomAccessIter __last, 02308 _Distance __chunk_size) 02309 { 02310 while (__last - __first >= __chunk_size) { 02311 __insertion_sort(__first, __first + __chunk_size); 02312 __first += __chunk_size; 02313 } 02314 __insertion_sort(__first, __last); 02315 } 02316 02317 template<typename _RandomAccessIter, typename _Distance, typename _Compare> 02318 void 02319 __chunk_insertion_sort(_RandomAccessIter __first, _RandomAccessIter __last, 02320 _Distance __chunk_size, _Compare __comp) 02321 { 02322 while (__last - __first >= __chunk_size) { 02323 __insertion_sort(__first, __first + __chunk_size, __comp); 02324 __first += __chunk_size; 02325 } 02326 __insertion_sort(__first, __last, __comp); 02327 } 02328 02329 template<typename _RandomAccessIter, typename _Pointer> 02330 void 02331 __merge_sort_with_buffer(_RandomAccessIter __first, _RandomAccessIter __last, 02332 _Pointer __buffer) 02333 { 02334 typedef typename iterator_traits<_RandomAccessIter>::difference_type _Distance; 02335 02336 _Distance __len = __last - __first; 02337 _Pointer __buffer_last = __buffer + __len; 02338 02339 _Distance __step_size = _M_chunk_size; 02340 __chunk_insertion_sort(__first, __last, __step_size); 02341 02342 while (__step_size < __len) { 02343 __merge_sort_loop(__first, __last, __buffer, __step_size); 02344 __step_size *= 2; 02345 __merge_sort_loop(__buffer, __buffer_last, __first, __step_size); 02346 __step_size *= 2; 02347 } 02348 } 02349 02350 template<typename _RandomAccessIter, typename _Pointer, typename _Compare> 02351 void 02352 __merge_sort_with_buffer(_RandomAccessIter __first, _RandomAccessIter __last, 02353 _Pointer __buffer, _Compare __comp) 02354 { 02355 typedef typename iterator_traits<_RandomAccessIter>::difference_type _Distance; 02356 02357 _Distance __len = __last - __first; 02358 _Pointer __buffer_last = __buffer + __len; 02359 02360 _Distance __step_size = _M_chunk_size; 02361 __chunk_insertion_sort(__first, __last, __step_size, __comp); 02362 02363 while (__step_size < __len) { 02364 __merge_sort_loop(__first, __last, __buffer, __step_size, __comp); 02365 __step_size *= 2; 02366 __merge_sort_loop(__buffer, __buffer_last, __first, __step_size, __comp); 02367 __step_size *= 2; 02368 } 02369 } 02370 02371 template<typename _RandomAccessIter, typename _Pointer, typename _Distance> 02372 void 02373 __stable_sort_adaptive(_RandomAccessIter __first, _RandomAccessIter __last, 02374 _Pointer __buffer, _Distance __buffer_size) 02375 { 02376 _Distance __len = (__last - __first + 1) / 2; 02377 _RandomAccessIter __middle = __first + __len; 02378 if (__len > __buffer_size) { 02379 __stable_sort_adaptive(__first, __middle, __buffer, __buffer_size); 02380 __stable_sort_adaptive(__middle, __last, __buffer, __buffer_size); 02381 } 02382 else { 02383 __merge_sort_with_buffer(__first, __middle, __buffer); 02384 __merge_sort_with_buffer(__middle, __last, __buffer); 02385 } 02386 __merge_adaptive(__first, __middle, __last, _Distance(__middle - __first), 02387 _Distance(__last - __middle), __buffer, __buffer_size); 02388 } 02389 02390 template<typename _RandomAccessIter, typename _Pointer, typename _Distance, 02391 typename _Compare> 02392 void 02393 __stable_sort_adaptive(_RandomAccessIter __first, _RandomAccessIter __last, 02394 _Pointer __buffer, _Distance __buffer_size, 02395 _Compare __comp) 02396 { 02397 _Distance __len = (__last - __first + 1) / 2; 02398 _RandomAccessIter __middle = __first + __len; 02399 if (__len > __buffer_size) { 02400 __stable_sort_adaptive(__first, __middle, __buffer, __buffer_size, 02401 __comp); 02402 __stable_sort_adaptive(__middle, __last, __buffer, __buffer_size, 02403 __comp); 02404 } 02405 else { 02406 __merge_sort_with_buffer(__first, __middle, __buffer, __comp); 02407 __merge_sort_with_buffer(__middle, __last, __buffer, __comp); 02408 } 02409 __merge_adaptive(__first, __middle, __last, _Distance(__middle - __first), 02410 _Distance(__last - __middle), __buffer, __buffer_size, 02411 __comp); 02412 } 02413 02430 template<typename _RandomAccessIter> 02431 inline void 02432 stable_sort(_RandomAccessIter __first, _RandomAccessIter __last) 02433 { 02434 typedef typename iterator_traits<_RandomAccessIter>::value_type _ValueType; 02435 typedef typename iterator_traits<_RandomAccessIter>::difference_type _DistanceType; 02436 02437 // concept requirements 02438 __glibcpp_function_requires(_Mutable_RandomAccessIteratorConcept< 02439 _RandomAccessIter>) 02440 __glibcpp_function_requires(_LessThanComparableConcept<_ValueType>) 02441 02442 _Temporary_buffer<_RandomAccessIter, _ValueType> buf(__first, __last); 02443 if (buf.begin() == 0) 02444 __inplace_stable_sort(__first, __last); 02445 else 02446 __stable_sort_adaptive(__first, __last, buf.begin(), _DistanceType(buf.size())); 02447 } 02448 02466 template<typename _RandomAccessIter, typename _Compare> 02467 inline void 02468 stable_sort(_RandomAccessIter __first, _RandomAccessIter __last, _Compare __comp) 02469 { 02470 typedef typename iterator_traits<_RandomAccessIter>::value_type _ValueType; 02471 typedef typename iterator_traits<_RandomAccessIter>::difference_type _DistanceType; 02472 02473 // concept requirements 02474 __glibcpp_function_requires(_Mutable_RandomAccessIteratorConcept< 02475 _RandomAccessIter>) 02476 __glibcpp_function_requires(_BinaryPredicateConcept<_Compare, 02477 _ValueType, _ValueType>) 02478 02479 _Temporary_buffer<_RandomAccessIter, _ValueType> buf(__first, __last); 02480 if (buf.begin() == 0) 02481 __inplace_stable_sort(__first, __last, __comp); 02482 else 02483 __stable_sort_adaptive(__first, __last, buf.begin(), _DistanceType(buf.size()), 02484 __comp); 02485 } 02486 02502 template<typename _RandomAccessIter> 02503 void 02504 partial_sort(_RandomAccessIter __first, 02505 _RandomAccessIter __middle, 02506 _RandomAccessIter __last) 02507 { 02508 typedef typename iterator_traits<_RandomAccessIter>::value_type _ValueType; 02509 02510 // concept requirements 02511 __glibcpp_function_requires(_Mutable_RandomAccessIteratorConcept< 02512 _RandomAccessIter>) 02513 __glibcpp_function_requires(_LessThanComparableConcept<_ValueType>) 02514 02515 make_heap(__first, __middle); 02516 for (_RandomAccessIter __i = __middle; __i < __last; ++__i) 02517 if (*__i < *__first) 02518 __pop_heap(__first, __middle, __i, _ValueType(*__i)); 02519 sort_heap(__first, __middle); 02520 } 02521 02540 template<typename _RandomAccessIter, typename _Compare> 02541 void 02542 partial_sort(_RandomAccessIter __first, 02543 _RandomAccessIter __middle, 02544 _RandomAccessIter __last, 02545 _Compare __comp) 02546 { 02547 typedef typename iterator_traits<_RandomAccessIter>::value_type _ValueType; 02548 02549 // concept requirements 02550 __glibcpp_function_requires(_Mutable_RandomAccessIteratorConcept< 02551 _RandomAccessIter>) 02552 __glibcpp_function_requires(_BinaryPredicateConcept<_Compare, 02553 _ValueType, _ValueType>) 02554 02555 make_heap(__first, __middle, __comp); 02556 for (_RandomAccessIter __i = __middle; __i < __last; ++__i) 02557 if (__comp(*__i, *__first)) 02558 __pop_heap(__first, __middle, __i, _ValueType(*__i), __comp); 02559 sort_heap(__first, __middle, __comp); 02560 } 02561 02579 template<typename _InputIter, typename _RandomAccessIter> 02580 _RandomAccessIter 02581 partial_sort_copy(_InputIter __first, _InputIter __last, 02582 _RandomAccessIter __result_first, 02583 _RandomAccessIter __result_last) 02584 { 02585 typedef typename iterator_traits<_InputIter>::value_type _InputValueType; 02586 typedef typename iterator_traits<_RandomAccessIter>::value_type _OutputValueType; 02587 typedef typename iterator_traits<_RandomAccessIter>::difference_type _DistanceType; 02588 02589 // concept requirements 02590 __glibcpp_function_requires(_InputIteratorConcept<_InputIter>) 02591 __glibcpp_function_requires(_ConvertibleConcept<_InputValueType, _OutputValueType>) 02592 __glibcpp_function_requires(_LessThanComparableConcept<_OutputValueType>) 02593 __glibcpp_function_requires(_LessThanComparableConcept<_InputValueType>) 02594 02595 if (__result_first == __result_last) return __result_last; 02596 _RandomAccessIter __result_real_last = __result_first; 02597 while(__first != __last && __result_real_last != __result_last) { 02598 *__result_real_last = *__first; 02599 ++__result_real_last; 02600 ++__first; 02601 } 02602 make_heap(__result_first, __result_real_last); 02603 while (__first != __last) { 02604 if (*__first < *__result_first) 02605 __adjust_heap(__result_first, _DistanceType(0), 02606 _DistanceType(__result_real_last - __result_first), 02607 _InputValueType(*__first)); 02608 ++__first; 02609 } 02610 sort_heap(__result_first, __result_real_last); 02611 return __result_real_last; 02612 } 02613 02633 template<typename _InputIter, typename _RandomAccessIter, typename _Compare> 02634 _RandomAccessIter 02635 partial_sort_copy(_InputIter __first, _InputIter __last, 02636 _RandomAccessIter __result_first, 02637 _RandomAccessIter __result_last, 02638 _Compare __comp) 02639 { 02640 typedef typename iterator_traits<_InputIter>::value_type _InputValueType; 02641 typedef typename iterator_traits<_RandomAccessIter>::value_type _OutputValueType; 02642 typedef typename iterator_traits<_RandomAccessIter>::difference_type _DistanceType; 02643 02644 // concept requirements 02645 __glibcpp_function_requires(_InputIteratorConcept<_InputIter>) 02646 __glibcpp_function_requires(_Mutable_RandomAccessIteratorConcept<_RandomAccessIter>) 02647 __glibcpp_function_requires(_ConvertibleConcept<_InputValueType, _OutputValueType>) 02648 __glibcpp_function_requires(_BinaryPredicateConcept<_Compare, 02649 _OutputValueType, _OutputValueType>) 02650 02651 if (__result_first == __result_last) return __result_last; 02652 _RandomAccessIter __result_real_last = __result_first; 02653 while(__first != __last && __result_real_last != __result_last) { 02654 *__result_real_last = *__first; 02655 ++__result_real_last; 02656 ++__first; 02657 } 02658 make_heap(__result_first, __result_real_last, __comp); 02659 while (__first != __last) { 02660 if (__comp(*__first, *__result_first)) 02661 __adjust_heap(__result_first, _DistanceType(0), 02662 _DistanceType(__result_real_last - __result_first), 02663 _InputValueType(*__first), 02664 __comp); 02665 ++__first; 02666 } 02667 sort_heap(__result_first, __result_real_last, __comp); 02668 return __result_real_last; 02669 } 02670 02686 template<typename _RandomAccessIter> 02687 void 02688 nth_element(_RandomAccessIter __first, 02689 _RandomAccessIter __nth, 02690 _RandomAccessIter __last) 02691 { 02692 typedef typename iterator_traits<_RandomAccessIter>::value_type _ValueType; 02693 02694 // concept requirements 02695 __glibcpp_function_requires(_Mutable_RandomAccessIteratorConcept<_RandomAccessIter>) 02696 __glibcpp_function_requires(_LessThanComparableConcept<_ValueType>) 02697 02698 while (__last - __first > 3) { 02699 _RandomAccessIter __cut = 02700 __unguarded_partition(__first, __last, 02701 _ValueType(__median(*__first, 02702 *(__first + (__last - __first)/2), 02703 *(__last - 1)))); 02704 if (__cut <= __nth) 02705 __first = __cut; 02706 else 02707 __last = __cut; 02708 } 02709 __insertion_sort(__first, __last); 02710 } 02711 02728 template<typename _RandomAccessIter, typename _Compare> 02729 void 02730 nth_element(_RandomAccessIter __first, 02731 _RandomAccessIter __nth, 02732 _RandomAccessIter __last, 02733 _Compare __comp) 02734 { 02735 typedef typename iterator_traits<_RandomAccessIter>::value_type _ValueType; 02736 02737 // concept requirements 02738 __glibcpp_function_requires(_Mutable_RandomAccessIteratorConcept<_RandomAccessIter>) 02739 __glibcpp_function_requires(_BinaryPredicateConcept<_Compare, 02740 _ValueType, _ValueType>) 02741 02742 while (__last - __first > 3) { 02743 _RandomAccessIter __cut = 02744 __unguarded_partition(__first, __last, 02745 _ValueType(__median(*__first, 02746 *(__first + (__last - __first)/2), 02747 *(__last - 1), 02748 __comp)), 02749 __comp); 02750 if (__cut <= __nth) 02751 __first = __cut; 02752 else 02753 __last = __cut; 02754 } 02755 __insertion_sort(__first, __last, __comp); 02756 } 02757 02758 02768 template<typename _ForwardIter, typename _Tp> 02769 _ForwardIter 02770 lower_bound(_ForwardIter __first, _ForwardIter __last, const _Tp& __val) 02771 { 02772 typedef typename iterator_traits<_ForwardIter>::value_type _ValueType; 02773 typedef typename iterator_traits<_ForwardIter>::difference_type _DistanceType; 02774 02775 // concept requirements 02776 // Note that these are slightly stricter than those of the 4-argument 02777 // version, defined next. The difference is in the strictness of the 02778 // comparison operations... so for looser checking, define your own 02779 // comparison function, as was intended. 02780 __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter>) 02781 __glibcpp_function_requires(_SameTypeConcept<_Tp, _ValueType>) 02782 __glibcpp_function_requires(_LessThanComparableConcept<_Tp>) 02783 02784 _DistanceType __len = distance(__first, __last); 02785 _DistanceType __half; 02786 _ForwardIter __middle; 02787 02788 while (__len > 0) { 02789 __half = __len >> 1; 02790 __middle = __first; 02791 advance(__middle, __half); 02792 if (*__middle < __val) { 02793 __first = __middle; 02794 ++__first; 02795 __len = __len - __half - 1; 02796 } 02797 else 02798 __len = __half; 02799 } 02800 return __first; 02801 } 02802 02816 template<typename _ForwardIter, typename _Tp, typename _Compare> 02817 _ForwardIter 02818 lower_bound(_ForwardIter __first, _ForwardIter __last, 02819 const _Tp& __val, _Compare __comp) 02820 { 02821 typedef typename iterator_traits<_ForwardIter>::value_type _ValueType; 02822 typedef typename iterator_traits<_ForwardIter>::difference_type _DistanceType; 02823 02824 // concept requirements 02825 __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter>) 02826 __glibcpp_function_requires(_BinaryPredicateConcept<_Compare, _ValueType, _Tp>) 02827 02828 _DistanceType __len = distance(__first, __last); 02829 _DistanceType __half; 02830 _ForwardIter __middle; 02831 02832 while (__len > 0) { 02833 __half = __len >> 1; 02834 __middle = __first; 02835 advance(__middle, __half); 02836 if (__comp(*__middle, __val)) { 02837 __first = __middle; 02838 ++__first; 02839 __len = __len - __half - 1; 02840 } 02841 else 02842 __len = __half; 02843 } 02844 return __first; 02845 } 02846 02856 template<typename _ForwardIter, typename _Tp> 02857 _ForwardIter 02858 upper_bound(_ForwardIter __first, _ForwardIter __last, const _Tp& __val) 02859 { 02860 typedef typename iterator_traits<_ForwardIter>::value_type _ValueType; 02861 typedef typename iterator_traits<_ForwardIter>::difference_type _DistanceType; 02862 02863 // concept requirements 02864 // See comments on lower_bound. 02865 __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter>) 02866 __glibcpp_function_requires(_SameTypeConcept<_Tp, _ValueType>) 02867 __glibcpp_function_requires(_LessThanComparableConcept<_Tp>) 02868 02869 _DistanceType __len = distance(__first, __last); 02870 _DistanceType __half; 02871 _ForwardIter __middle; 02872 02873 while (__len > 0) { 02874 __half = __len >> 1; 02875 __middle = __first; 02876 advance(__middle, __half); 02877 if (__val < *__middle) 02878 __len = __half; 02879 else { 02880 __first = __middle; 02881 ++__first; 02882 __len = __len - __half - 1; 02883 } 02884 } 02885 return __first; 02886 } 02887 02901 template<typename _ForwardIter, typename _Tp, typename _Compare> 02902 _ForwardIter 02903 upper_bound(_ForwardIter __first, _ForwardIter __last, 02904 const _Tp& __val, _Compare __comp) 02905 { 02906 typedef typename iterator_traits<_ForwardIter>::value_type _ValueType; 02907 typedef typename iterator_traits<_ForwardIter>::difference_type _DistanceType; 02908 02909 // concept requirements 02910 __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter>) 02911 __glibcpp_function_requires(_BinaryPredicateConcept<_Compare, _Tp, _ValueType>) 02912 02913 _DistanceType __len = distance(__first, __last); 02914 _DistanceType __half; 02915 _ForwardIter __middle; 02916 02917 while (__len > 0) { 02918 __half = __len >> 1; 02919 __middle = __first; 02920 advance(__middle, __half); 02921 if (__comp(__val, *__middle)) 02922 __len = __half; 02923 else { 02924 __first = __middle; 02925 ++__first; 02926 __len = __len - __half - 1; 02927 } 02928 } 02929 return __first; 02930 } 02931 02948 template<typename _ForwardIter, typename _Tp> 02949 pair<_ForwardIter, _ForwardIter> 02950 equal_range(_ForwardIter __first, _ForwardIter __last, const _Tp& __val) 02951 { 02952 typedef typename iterator_traits<_ForwardIter>::value_type _ValueType; 02953 typedef typename iterator_traits<_ForwardIter>::difference_type _DistanceType; 02954 02955 // concept requirements 02956 // See comments on lower_bound. 02957 __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter>) 02958 __glibcpp_function_requires(_SameTypeConcept<_Tp, _ValueType>) 02959 __glibcpp_function_requires(_LessThanComparableConcept<_Tp>) 02960 02961 _DistanceType __len = distance(__first, __last); 02962 _DistanceType __half; 02963 _ForwardIter __middle, __left, __right; 02964 02965 while (__len > 0) { 02966 __half = __len >> 1; 02967 __middle = __first; 02968 advance(__middle, __half); 02969 if (*__middle < __val) { 02970 __first = __middle; 02971 ++__first; 02972 __len = __len - __half - 1; 02973 } 02974 else if (__val < *__middle) 02975 __len = __half; 02976 else { 02977 __left = lower_bound(__first, __middle, __val); 02978 advance(__first, __len); 02979 __right = upper_bound(++__middle, __first, __val); 02980 return pair<_ForwardIter, _ForwardIter>(__left, __right); 02981 } 02982 } 02983 return pair<_ForwardIter, _ForwardIter>(__first, __first); 02984 } 02985 03003 template<typename _ForwardIter, typename _Tp, typename _Compare> 03004 pair<_ForwardIter, _ForwardIter> 03005 equal_range(_ForwardIter __first, _ForwardIter __last, const _Tp& __val, 03006 _Compare __comp) 03007 { 03008 typedef typename iterator_traits<_ForwardIter>::value_type _ValueType; 03009 typedef typename iterator_traits<_ForwardIter>::difference_type _DistanceType; 03010 03011 // concept requirements 03012 __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter>) 03013 __glibcpp_function_requires(_BinaryPredicateConcept<_Compare, _ValueType, _Tp>) 03014 __glibcpp_function_requires(_BinaryPredicateConcept<_Compare, _Tp, _ValueType>) 03015 03016 _DistanceType __len = distance(__first, __last); 03017 _DistanceType __half; 03018 _ForwardIter __middle, __left, __right; 03019 03020 while (__len > 0) { 03021 __half = __len >> 1; 03022 __middle = __first; 03023 advance(__middle, __half); 03024 if (__comp(*__middle, __val)) { 03025 __first = __middle; 03026 ++__first; 03027 __len = __len - __half - 1; 03028 } 03029 else if (__comp(__val, *__middle)) 03030 __len = __half; 03031 else { 03032 __left = lower_bound(__first, __middle, __val, __comp); 03033 advance(__first, __len); 03034 __right = upper_bound(++__middle, __first, __val, __comp); 03035 return pair<_ForwardIter, _ForwardIter>(__left, __right); 03036 } 03037 } 03038 return pair<_ForwardIter, _ForwardIter>(__first, __first); 03039 } 03040 03052 template<typename _ForwardIter, typename _Tp> 03053 bool 03054 binary_search(_ForwardIter __first, _ForwardIter __last, 03055 const _Tp& __val) 03056 { 03057 // concept requirements 03058 // See comments on lower_bound. 03059 __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter>) 03060 __glibcpp_function_requires(_SameTypeConcept<_Tp, 03061 typename iterator_traits<_ForwardIter>::value_type>) 03062 __glibcpp_function_requires(_LessThanComparableConcept<_Tp>) 03063 03064 _ForwardIter __i = lower_bound(__first, __last, __val); 03065 return __i != __last && !(__val < *__i); 03066 } 03067 03083 template<typename _ForwardIter, typename _Tp, typename _Compare> 03084 bool 03085 binary_search(_ForwardIter __first, _ForwardIter __last, 03086 const _Tp& __val, _Compare __comp) 03087 { 03088 // concept requirements 03089 __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter>) 03090 __glibcpp_function_requires(_BinaryPredicateConcept<_Compare, 03091 typename iterator_traits<_ForwardIter>::value_type, _Tp>) 03092 __glibcpp_function_requires(_BinaryPredicateConcept<_Compare, _Tp, 03093 typename iterator_traits<_ForwardIter>::value_type>) 03094 03095 _ForwardIter __i = lower_bound(__first, __last, __val, __comp); 03096 return __i != __last && !__comp(__val, *__i); 03097 } 03098 03115 template<typename _InputIter1, typename _InputIter2, typename _OutputIter> 03116 _OutputIter 03117 merge(_InputIter1 __first1, _InputIter1 __last1, 03118 _InputIter2 __first2, _InputIter2 __last2, 03119 _OutputIter __result) 03120 { 03121 // concept requirements 03122 __glibcpp_function_requires(_InputIteratorConcept<_InputIter1>) 03123 __glibcpp_function_requires(_InputIteratorConcept<_InputIter2>) 03124 __glibcpp_function_requires(_OutputIteratorConcept<_OutputIter, 03125 typename iterator_traits<_InputIter1>::value_type>) 03126 __glibcpp_function_requires(_SameTypeConcept< 03127 typename iterator_traits<_InputIter1>::value_type, 03128 typename iterator_traits<_InputIter2>::value_type>) 03129 __glibcpp_function_requires(_LessThanComparableConcept< 03130 typename iterator_traits<_InputIter1>::value_type>) 03131 03132 while (__first1 != __last1 && __first2 != __last2) { 03133 if (*__first2 < *__first1) { 03134 *__result = *__first2; 03135 ++__first2; 03136 } 03137 else { 03138 *__result = *__first1; 03139 ++__first1; 03140 } 03141 ++__result; 03142 } 03143 return copy(__first2, __last2, copy(__first1, __last1, __result)); 03144 } 03145 03166 template<typename _InputIter1, typename _InputIter2, typename _OutputIter, 03167 typename _Compare> 03168 _OutputIter 03169 merge(_InputIter1 __first1, _InputIter1 __last1, 03170 _InputIter2 __first2, _InputIter2 __last2, 03171 _OutputIter __result, _Compare __comp) 03172 { 03173 // concept requirements 03174 __glibcpp_function_requires(_InputIteratorConcept<_InputIter1>) 03175 __glibcpp_function_requires(_InputIteratorConcept<_InputIter2>) 03176 __glibcpp_function_requires(_SameTypeConcept< 03177 typename iterator_traits<_InputIter1>::value_type, 03178 typename iterator_traits<_InputIter2>::value_type>) 03179 __glibcpp_function_requires(_OutputIteratorConcept<_OutputIter, 03180 typename iterator_traits<_InputIter1>::value_type>) 03181 __glibcpp_function_requires(_BinaryPredicateConcept<_Compare, 03182 typename iterator_traits<_InputIter1>::value_type, 03183 typename iterator_traits<_InputIter2>::value_type>) 03184 03185 while (__first1 != __last1 && __first2 != __last2) { 03186 if (__comp(*__first2, *__first1)) { 03187 *__result = *__first2; 03188 ++__first2; 03189 } 03190 else { 03191 *__result = *__first1; 03192 ++__first1; 03193 } 03194 ++__result; 03195 } 03196 return copy(__first2, __last2, copy(__first1, __last1, __result)); 03197 } 03198 03204 template<typename _BidirectionalIter, typename _Distance> 03205 void 03206 __merge_without_buffer(_BidirectionalIter __first, 03207 _BidirectionalIter __middle, 03208 _BidirectionalIter __last, 03209 _Distance __len1, _Distance __len2) 03210 { 03211 if (__len1 == 0 || __len2 == 0) 03212 return; 03213 if (__len1 + __len2 == 2) { 03214 if (*__middle < *__first) 03215 iter_swap(__first, __middle); 03216 return; 03217 } 03218 _BidirectionalIter __first_cut = __first; 03219 _BidirectionalIter __second_cut = __middle; 03220 _Distance __len11 = 0; 03221 _Distance __len22 = 0; 03222 if (__len1 > __len2) { 03223 __len11 = __len1 / 2; 03224 advance(__first_cut, __len11); 03225 __second_cut = lower_bound(__middle, __last, *__first_cut); 03226 __len22 = distance(__middle, __second_cut); 03227 } 03228 else { 03229 __len22 = __len2 / 2; 03230 advance(__second_cut, __len22); 03231 __first_cut = upper_bound(__first, __middle, *__second_cut); 03232 __len11 = distance(__first, __first_cut); 03233 } 03234 rotate(__first_cut, __middle, __second_cut); 03235 _BidirectionalIter __new_middle = __first_cut; 03236 advance(__new_middle, distance(__middle, __second_cut)); 03237 __merge_without_buffer(__first, __first_cut, __new_middle, 03238 __len11, __len22); 03239 __merge_without_buffer(__new_middle, __second_cut, __last, 03240 __len1 - __len11, __len2 - __len22); 03241 } 03242 03248 template<typename _BidirectionalIter, typename _Distance, typename _Compare> 03249 void 03250 __merge_without_buffer(_BidirectionalIter __first, 03251 _BidirectionalIter __middle, 03252 _BidirectionalIter __last, 03253 _Distance __len1, _Distance __len2, 03254 _Compare __comp) 03255 { 03256 if (__len1 == 0 || __len2 == 0) 03257 return; 03258 if (__len1 + __len2 == 2) { 03259 if (__comp(*__middle, *__first)) 03260 iter_swap(__first, __middle); 03261 return; 03262 } 03263 _BidirectionalIter __first_cut = __first; 03264 _BidirectionalIter __second_cut = __middle; 03265 _Distance __len11 = 0; 03266 _Distance __len22 = 0; 03267 if (__len1 > __len2) { 03268 __len11 = __len1 / 2; 03269 advance(__first_cut, __len11); 03270 __second_cut = lower_bound(__middle, __last, *__first_cut, __comp); 03271 __len22 = distance(__middle, __second_cut); 03272 } 03273 else { 03274 __len22 = __len2 / 2; 03275 advance(__second_cut, __len22); 03276 __first_cut = upper_bound(__first, __middle, *__second_cut, __comp); 03277 __len11 = distance(__first, __first_cut); 03278 } 03279 rotate(__first_cut, __middle, __second_cut); 03280 _BidirectionalIter __new_middle = __first_cut; 03281 advance(__new_middle, distance(__middle, __second_cut)); 03282 __merge_without_buffer(__first, __first_cut, __new_middle, 03283 __len11, __len22, __comp); 03284 __merge_without_buffer(__new_middle, __second_cut, __last, 03285 __len1 - __len11, __len2 - __len22, __comp); 03286 } 03287 03293 template<typename _BidirectionalIter1, typename _BidirectionalIter2, 03294 typename _Distance> 03295 _BidirectionalIter1 03296 __rotate_adaptive(_BidirectionalIter1 __first, 03297 _BidirectionalIter1 __middle, 03298 _BidirectionalIter1 __last, 03299 _Distance __len1, _Distance __len2, 03300 _BidirectionalIter2 __buffer, 03301 _Distance __buffer_size) 03302 { 03303 _BidirectionalIter2 __buffer_end; 03304 if (__len1 > __len2 && __len2 <= __buffer_size) { 03305 __buffer_end = copy(__middle, __last, __buffer); 03306 copy_backward(__first, __middle, __last); 03307 return copy(__buffer, __buffer_end, __first); 03308 } 03309 else if (__len1 <= __buffer_size) { 03310 __buffer_end = copy(__first, __middle, __buffer); 03311 copy(__middle, __last, __first); 03312 return copy_backward(__buffer, __buffer_end, __last); 03313 } 03314 else { 03315 rotate(__first, __middle, __last); 03316 advance(__first, distance(__middle, __last)); 03317 return __first; 03318 } 03319 } 03320 03326 template<typename _BidirectionalIter1, typename _BidirectionalIter2, 03327 typename _BidirectionalIter3> 03328 _BidirectionalIter3 03329 __merge_backward(_BidirectionalIter1 __first1, _BidirectionalIter1 __last1, 03330 _BidirectionalIter2 __first2, _BidirectionalIter2 __last2, 03331 _BidirectionalIter3 __result) 03332 { 03333 if (__first1 == __last1) 03334 return copy_backward(__first2, __last2, __result); 03335 if (__first2 == __last2) 03336 return copy_backward(__first1, __last1, __result); 03337 --__last1; 03338 --__last2; 03339 while (true) { 03340 if (*__last2 < *__last1) { 03341 *--__result = *__last1; 03342 if (__first1 == __last1) 03343 return copy_backward(__first2, ++__last2, __result); 03344 --__last1; 03345 } 03346 else { 03347 *--__result = *__last2; 03348 if (__first2 == __last2) 03349 return copy_backward(__first1, ++__last1, __result); 03350 --__last2; 03351 } 03352 } 03353 } 03354 03360 template<typename _BidirectionalIter1, typename _BidirectionalIter2, 03361 typename _BidirectionalIter3, typename _Compare> 03362 _BidirectionalIter3 03363 __merge_backward(_BidirectionalIter1 __first1, _BidirectionalIter1 __last1, 03364 _BidirectionalIter2 __first2, _BidirectionalIter2 __last2, 03365 _BidirectionalIter3 __result, 03366 _Compare __comp) 03367 { 03368 if (__first1 == __last1) 03369 return copy_backward(__first2, __last2, __result); 03370 if (__first2 == __last2) 03371 return copy_backward(__first1, __last1, __result); 03372 --__last1; 03373 --__last2; 03374 while (true) { 03375 if (__comp(*__last2, *__last1)) { 03376 *--__result = *__last1; 03377 if (__first1 == __last1) 03378 return copy_backward(__first2, ++__last2, __result); 03379 --__last1; 03380 } 03381 else { 03382 *--__result = *__last2; 03383 if (__first2 == __last2) 03384 return copy_backward(__first1, ++__last1, __result); 03385 --__last2; 03386 } 03387 } 03388 } 03389 03395 template<typename _BidirectionalIter, typename _Distance, typename _Pointer> 03396 void 03397 __merge_adaptive(_BidirectionalIter __first, 03398 _BidirectionalIter __middle, 03399 _BidirectionalIter __last, 03400 _Distance __len1, _Distance __len2, 03401 _Pointer __buffer, _Distance __buffer_size) 03402 { 03403 if (__len1 <= __len2 && __len1 <= __buffer_size) { 03404 _Pointer __buffer_end = copy(__first, __middle, __buffer); 03405 merge(__buffer, __buffer_end, __middle, __last, __first); 03406 } 03407 else if (__len2 <= __buffer_size) { 03408 _Pointer __buffer_end = copy(__middle, __last, __buffer); 03409 __merge_backward(__first, __middle, __buffer, __buffer_end, __last); 03410 } 03411 else { 03412 _BidirectionalIter __first_cut = __first; 03413 _BidirectionalIter __second_cut = __middle; 03414 _Distance __len11 = 0; 03415 _Distance __len22 = 0; 03416 if (__len1 > __len2) { 03417 __len11 = __len1 / 2; 03418 advance(__first_cut, __len11); 03419 __second_cut = lower_bound(__middle, __last, *__first_cut); 03420 __len22 = distance(__middle, __second_cut); 03421 } 03422 else { 03423 __len22 = __len2 / 2; 03424 advance(__second_cut, __len22); 03425 __first_cut = upper_bound(__first, __middle, *__second_cut); 03426 __len11 = distance(__first, __first_cut); 03427 } 03428 _BidirectionalIter __new_middle = 03429 __rotate_adaptive(__first_cut, __middle, __second_cut, 03430 __len1 - __len11, __len22, __buffer, 03431 __buffer_size); 03432 __merge_adaptive(__first, __first_cut, __new_middle, __len11, 03433 __len22, __buffer, __buffer_size); 03434 __merge_adaptive(__new_middle, __second_cut, __last, __len1 - __len11, 03435 __len2 - __len22, __buffer, __buffer_size); 03436 } 03437 } 03438 03444 template<typename _BidirectionalIter, typename _Distance, typename _Pointer, 03445 typename _Compare> 03446 void 03447 __merge_adaptive(_BidirectionalIter __first, 03448 _BidirectionalIter __middle, 03449 _BidirectionalIter __last, 03450 _Distance __len1, _Distance __len2, 03451 _Pointer __buffer, _Distance __buffer_size, 03452 _Compare __comp) 03453 { 03454 if (__len1 <= __len2 && __len1 <= __buffer_size) { 03455 _Pointer __buffer_end = copy(__first, __middle, __buffer); 03456 merge(__buffer, __buffer_end, __middle, __last, __first, __comp); 03457 } 03458 else if (__len2 <= __buffer_size) { 03459 _Pointer __buffer_end = copy(__middle, __last, __buffer); 03460 __merge_backward(__first, __middle, __buffer, __buffer_end, __last, 03461 __comp); 03462 } 03463 else { 03464 _BidirectionalIter __first_cut = __first; 03465 _BidirectionalIter __second_cut = __middle; 03466 _Distance __len11 = 0; 03467 _Distance __len22 = 0; 03468 if (__len1 > __len2) { 03469 __len11 = __len1 / 2; 03470 advance(__first_cut, __len11); 03471 __second_cut = lower_bound(__middle, __last, *__first_cut, __comp); 03472 __len22 = distance(__middle, __second_cut); 03473 } 03474 else { 03475 __len22 = __len2 / 2; 03476 advance(__second_cut, __len22); 03477 __first_cut = upper_bound(__first, __middle, *__second_cut, __comp); 03478 __len11 = distance(__first, __first_cut); 03479 } 03480 _BidirectionalIter __new_middle = 03481 __rotate_adaptive(__first_cut, __middle, __second_cut, 03482 __len1 - __len11, __len22, __buffer, 03483 __buffer_size); 03484 __merge_adaptive(__first, __first_cut, __new_middle, __len11, 03485 __len22, __buffer, __buffer_size, __comp); 03486 __merge_adaptive(__new_middle, __second_cut, __last, __len1 - __len11, 03487 __len2 - __len22, __buffer, __buffer_size, __comp); 03488 } 03489 } 03490 03508 template<typename _BidirectionalIter> 03509 void 03510 inplace_merge(_BidirectionalIter __first, 03511 _BidirectionalIter __middle, 03512 _BidirectionalIter __last) 03513 { 03514 typedef typename iterator_traits<_BidirectionalIter>::value_type 03515 _ValueType; 03516 typedef typename iterator_traits<_BidirectionalIter>::difference_type 03517 _DistanceType; 03518 03519 // concept requirements 03520 __glibcpp_function_requires(_Mutable_BidirectionalIteratorConcept< 03521 _BidirectionalIter>) 03522 __glibcpp_function_requires(_LessThanComparableConcept<_ValueType>) 03523 03524 if (__first == __middle || __middle == __last) 03525 return; 03526 03527 _DistanceType __len1 = distance(__first, __middle); 03528 _DistanceType __len2 = distance(__middle, __last); 03529 03530 _Temporary_buffer<_BidirectionalIter, _ValueType> __buf(__first, __last); 03531 if (__buf.begin() == 0) 03532 __merge_without_buffer(__first, __middle, __last, __len1, __len2); 03533 else 03534 __merge_adaptive(__first, __middle, __last, __len1, __len2, 03535 __buf.begin(), _DistanceType(__buf.size())); 03536 } 03537 03559 template<typename _BidirectionalIter, typename _Compare> 03560 void 03561 inplace_merge(_BidirectionalIter __first, 03562 _BidirectionalIter __middle, 03563 _BidirectionalIter __last, 03564 _Compare __comp) 03565 { 03566 typedef typename iterator_traits<_BidirectionalIter>::value_type 03567 _ValueType; 03568 typedef typename iterator_traits<_BidirectionalIter>::difference_type 03569 _DistanceType; 03570 03571 // concept requirements 03572 __glibcpp_function_requires(_Mutable_BidirectionalIteratorConcept< 03573 _BidirectionalIter>) 03574 __glibcpp_function_requires(_BinaryPredicateConcept<_Compare, 03575 _ValueType, _ValueType>) 03576 03577 if (__first == __middle || __middle == __last) 03578 return; 03579 03580 _DistanceType __len1 = distance(__first, __middle); 03581 _DistanceType __len2 = distance(__middle, __last); 03582 03583 _Temporary_buffer<_BidirectionalIter, _ValueType> __buf(__first, __last); 03584 if (__buf.begin() == 0) 03585 __merge_without_buffer(__first, __middle, __last, __len1, __len2, __comp); 03586 else 03587 __merge_adaptive(__first, __middle, __last, __len1, __len2, 03588 __buf.begin(), _DistanceType(__buf.size()), 03589 __comp); 03590 } 03591 03592 // Set algorithms: includes, set_union, set_intersection, set_difference, 03593 // set_symmetric_difference. All of these algorithms have the precondition 03594 // that their input ranges are sorted and the postcondition that their output 03595 // ranges are sorted. 03596 03597 template<typename _InputIter1, typename _InputIter2> 03598 bool 03599 includes(_InputIter1 __first1, _InputIter1 __last1, 03600 _InputIter2 __first2, _InputIter2 __last2) 03601 { 03602 // concept requirements 03603 __glibcpp_function_requires(_InputIteratorConcept<_InputIter1>) 03604 __glibcpp_function_requires(_InputIteratorConcept<_InputIter2>) 03605 __glibcpp_function_requires(_SameTypeConcept< 03606 typename iterator_traits<_InputIter1>::value_type, 03607 typename iterator_traits<_InputIter2>::value_type>) 03608 __glibcpp_function_requires(_LessThanComparableConcept< 03609 typename iterator_traits<_InputIter1>::value_type>) 03610 03611 while (__first1 != __last1 && __first2 != __last2) 03612 if (*__first2 < *__first1) 03613 return false; 03614 else if(*__first1 < *__first2) 03615 ++__first1; 03616 else 03617 ++__first1, ++__first2; 03618 03619 return __first2 == __last2; 03620 } 03621 03622 template<typename _InputIter1, typename _InputIter2, typename _Compare> 03623 bool 03624 includes(_InputIter1 __first1, _InputIter1 __last1, 03625 _InputIter2 __first2, _InputIter2 __last2, _Compare __comp) 03626 { 03627 // concept requirements 03628 __glibcpp_function_requires(_InputIteratorConcept<_InputIter1>) 03629 __glibcpp_function_requires(_InputIteratorConcept<_InputIter2>) 03630 __glibcpp_function_requires(_SameTypeConcept< 03631 typename iterator_traits<_InputIter1>::value_type, 03632 typename iterator_traits<_InputIter2>::value_type>) 03633 __glibcpp_function_requires(_BinaryPredicateConcept<_Compare, 03634 typename iterator_traits<_InputIter1>::value_type, 03635 typename iterator_traits<_InputIter2>::value_type>) 03636 03637 while (__first1 != __last1 && __first2 != __last2) 03638 if (__comp(*__first2, *__first1)) 03639 return false; 03640 else if(__comp(*__first1, *__first2)) 03641 ++__first1; 03642 else 03643 ++__first1, ++__first2; 03644 03645 return __first2 == __last2; 03646 } 03647 03648 template<typename _InputIter1, typename _InputIter2, typename _OutputIter> 03649 _OutputIter 03650 set_union(_InputIter1 __first1, _InputIter1 __last1, 03651 _InputIter2 __first2, _InputIter2 __last2, 03652 _OutputIter __result) 03653 { 03654 // concept requirements 03655 __glibcpp_function_requires(_InputIteratorConcept<_InputIter1>) 03656 __glibcpp_function_requires(_InputIteratorConcept<_InputIter2>) 03657 __glibcpp_function_requires(_OutputIteratorConcept<_OutputIter, 03658 typename iterator_traits<_InputIter1>::value_type>) 03659 __glibcpp_function_requires(_SameTypeConcept< 03660 typename iterator_traits<_InputIter1>::value_type, 03661 typename iterator_traits<_InputIter2>::value_type>) 03662 __glibcpp_function_requires(_LessThanComparableConcept< 03663 typename iterator_traits<_InputIter1>::value_type>) 03664 03665 while (__first1 != __last1 && __first2 != __last2) { 03666 if (*__first1 < *__first2) { 03667 *__result = *__first1; 03668 ++__first1; 03669 } 03670 else if (*__first2 < *__first1) { 03671 *__result = *__first2; 03672 ++__first2; 03673 } 03674 else { 03675 *__result = *__first1; 03676 ++__first1; 03677 ++__first2; 03678 } 03679 ++__result; 03680 } 03681 return copy(__first2, __last2, copy(__first1, __last1, __result)); 03682 } 03683 03684 template<typename _InputIter1, typename _InputIter2, typename _OutputIter, 03685 typename _Compare> 03686 _OutputIter 03687 set_union(_InputIter1 __first1, _InputIter1 __last1, 03688 _InputIter2 __first2, _InputIter2 __last2, 03689 _OutputIter __result, _Compare __comp) 03690 { 03691 // concept requirements 03692 __glibcpp_function_requires(_InputIteratorConcept<_InputIter1>) 03693 __glibcpp_function_requires(_InputIteratorConcept<_InputIter2>) 03694 __glibcpp_function_requires(_SameTypeConcept< 03695 typename iterator_traits<_InputIter1>::value_type, 03696 typename iterator_traits<_InputIter2>::value_type>) 03697 __glibcpp_function_requires(_OutputIteratorConcept<_OutputIter, 03698 typename iterator_traits<_InputIter1>::value_type>) 03699 __glibcpp_function_requires(_BinaryPredicateConcept<_Compare, 03700 typename iterator_traits<_InputIter1>::value_type, 03701 typename iterator_traits<_InputIter2>::value_type>) 03702 03703 while (__first1 != __last1 && __first2 != __last2) { 03704 if (__comp(*__first1, *__first2)) { 03705 *__result = *__first1; 03706 ++__first1; 03707 } 03708 else if (__comp(*__first2, *__first1)) { 03709 *__result = *__first2; 03710 ++__first2; 03711 } 03712 else { 03713 *__result = *__first1; 03714 ++__first1; 03715 ++__first2; 03716 } 03717 ++__result; 03718 } 03719 return copy(__first2, __last2, copy(__first1, __last1, __result)); 03720 } 03721 03722 template<typename _InputIter1, typename _InputIter2, typename _OutputIter> 03723 _OutputIter 03724 set_intersection(_InputIter1 __first1, _InputIter1 __last1, 03725 _InputIter2 __first2, _InputIter2 __last2, 03726 _OutputIter __result) 03727 { 03728 // concept requirements 03729 __glibcpp_function_requires(_InputIteratorConcept<_InputIter1>) 03730 __glibcpp_function_requires(_InputIteratorConcept<_InputIter2>) 03731 __glibcpp_function_requires(_OutputIteratorConcept<_OutputIter, 03732 typename iterator_traits<_InputIter1>::value_type>) 03733 __glibcpp_function_requires(_SameTypeConcept< 03734 typename iterator_traits<_InputIter1>::value_type, 03735 typename iterator_traits<_InputIter2>::value_type>) 03736 __glibcpp_function_requires(_LessThanComparableConcept< 03737 typename iterator_traits<_InputIter1>::value_type>) 03738 03739 while (__first1 != __last1 && __first2 != __last2) 03740 if (*__first1 < *__first2) 03741 ++__first1; 03742 else if (*__first2 < *__first1) 03743 ++__first2; 03744 else { 03745 *__result = *__first1; 03746 ++__first1; 03747 ++__first2; 03748 ++__result; 03749 } 03750 return __result; 03751 } 03752 03753 template<typename _InputIter1, typename _InputIter2, typename _OutputIter, 03754 typename _Compare> 03755 _OutputIter 03756 set_intersection(_InputIter1 __first1, _InputIter1 __last1, 03757 _InputIter2 __first2, _InputIter2 __last2, 03758 _OutputIter __result, _Compare __comp) 03759 { 03760 // concept requirements 03761 __glibcpp_function_requires(_InputIteratorConcept<_InputIter1>) 03762 __glibcpp_function_requires(_InputIteratorConcept<_InputIter2>) 03763 __glibcpp_function_requires(_SameTypeConcept< 03764 typename iterator_traits<_InputIter1>::value_type, 03765 typename iterator_traits<_InputIter2>::value_type>) 03766 __glibcpp_function_requires(_OutputIteratorConcept<_OutputIter, 03767 typename iterator_traits<_InputIter1>::value_type>) 03768 __glibcpp_function_requires(_BinaryPredicateConcept<_Compare, 03769 typename iterator_traits<_InputIter1>::value_type, 03770 typename iterator_traits<_InputIter2>::value_type>) 03771 03772 while (__first1 != __last1 && __first2 != __last2) 03773 if (__comp(*__first1, *__first2)) 03774 ++__first1; 03775 else if (__comp(*__first2, *__first1)) 03776 ++__first2; 03777 else { 03778 *__result = *__first1; 03779 ++__first1; 03780 ++__first2; 03781 ++__result; 03782 } 03783 return __result; 03784 } 03785 03786 template<typename _InputIter1, typename _InputIter2, typename _OutputIter> 03787 _OutputIter 03788 set_difference(_InputIter1 __first1, _InputIter1 __last1, 03789 _InputIter2 __first2, _InputIter2 __last2, 03790 _OutputIter __result) 03791 { 03792 // concept requirements 03793 __glibcpp_function_requires(_InputIteratorConcept<_InputIter1>) 03794 __glibcpp_function_requires(_InputIteratorConcept<_InputIter2>) 03795 __glibcpp_function_requires(_OutputIteratorConcept<_OutputIter, 03796 typename iterator_traits<_InputIter1>::value_type>) 03797 __glibcpp_function_requires(_SameTypeConcept< 03798 typename iterator_traits<_InputIter1>::value_type, 03799 typename iterator_traits<_InputIter2>::value_type>) 03800 __glibcpp_function_requires(_LessThanComparableConcept< 03801 typename iterator_traits<_InputIter1>::value_type>) 03802 03803 while (__first1 != __last1 && __first2 != __last2) 03804 if (*__first1 < *__first2) { 03805 *__result = *__first1; 03806 ++__first1; 03807 ++__result; 03808 } 03809 else if (*__first2 < *__first1) 03810 ++__first2; 03811 else { 03812 ++__first1; 03813 ++__first2; 03814 } 03815 return copy(__first1, __last1, __result); 03816 } 03817 03818 template<typename _InputIter1, typename _InputIter2, typename _OutputIter, 03819 typename _Compare> 03820 _OutputIter 03821 set_difference(_InputIter1 __first1, _InputIter1 __last1, 03822 _InputIter2 __first2, _InputIter2 __last2, 03823 _OutputIter __result, _Compare __comp) 03824 { 03825 // concept requirements 03826 __glibcpp_function_requires(_InputIteratorConcept<_InputIter1>) 03827 __glibcpp_function_requires(_InputIteratorConcept<_InputIter2>) 03828 __glibcpp_function_requires(_SameTypeConcept< 03829 typename iterator_traits<_InputIter1>::value_type, 03830 typename iterator_traits<_InputIter2>::value_type>) 03831 __glibcpp_function_requires(_OutputIteratorConcept<_OutputIter, 03832 typename iterator_traits<_InputIter1>::value_type>) 03833 __glibcpp_function_requires(_BinaryPredicateConcept<_Compare, 03834 typename iterator_traits<_InputIter1>::value_type, 03835 typename iterator_traits<_InputIter2>::value_type>) 03836 03837 while (__first1 != __last1 && __first2 != __last2) 03838 if (__comp(*__first1, *__first2)) { 03839 *__result = *__first1; 03840 ++__first1; 03841 ++__result; 03842 } 03843 else if (__comp(*__first2, *__first1)) 03844 ++__first2; 03845 else { 03846 ++__first1; 03847 ++__first2; 03848 } 03849 return copy(__first1, __last1, __result); 03850 } 03851 03852 template<typename _InputIter1, typename _InputIter2, typename _OutputIter> 03853 _OutputIter 03854 set_symmetric_difference(_InputIter1 __first1, _InputIter1 __last1, 03855 _InputIter2 __first2, _InputIter2 __last2, 03856 _OutputIter __result) 03857 { 03858 // concept requirements 03859 __glibcpp_function_requires(_InputIteratorConcept<_InputIter1>) 03860 __glibcpp_function_requires(_InputIteratorConcept<_InputIter2>) 03861 __glibcpp_function_requires(_OutputIteratorConcept<_OutputIter, 03862 typename iterator_traits<_InputIter1>::value_type>) 03863 __glibcpp_function_requires(_SameTypeConcept< 03864 typename iterator_traits<_InputIter1>::value_type, 03865 typename iterator_traits<_InputIter2>::value_type>) 03866 __glibcpp_function_requires(_LessThanComparableConcept< 03867 typename iterator_traits<_InputIter1>::value_type>) 03868 03869 while (__first1 != __last1 && __first2 != __last2) 03870 if (*__first1 < *__first2) { 03871 *__result = *__first1; 03872 ++__first1; 03873 ++__result; 03874 } 03875 else if (*__first2 < *__first1) { 03876 *__result = *__first2; 03877 ++__first2; 03878 ++__result; 03879 } 03880 else { 03881 ++__first1; 03882 ++__first2; 03883 } 03884 return copy(__first2, __last2, copy(__first1, __last1, __result)); 03885 } 03886 03887 template<typename _InputIter1, typename _InputIter2, typename _OutputIter, 03888 typename _Compare> 03889 _OutputIter 03890 set_symmetric_difference(_InputIter1 __first1, _InputIter1 __last1, 03891 _InputIter2 __first2, _InputIter2 __last2, 03892 _OutputIter __result, 03893 _Compare __comp) 03894 { 03895 // concept requirements 03896 __glibcpp_function_requires(_InputIteratorConcept<_InputIter1>) 03897 __glibcpp_function_requires(_InputIteratorConcept<_InputIter2>) 03898 __glibcpp_function_requires(_SameTypeConcept< 03899 typename iterator_traits<_InputIter1>::value_type, 03900 typename iterator_traits<_InputIter2>::value_type>) 03901 __glibcpp_function_requires(_OutputIteratorConcept<_OutputIter, 03902 typename iterator_traits<_InputIter1>::value_type>) 03903 __glibcpp_function_requires(_BinaryPredicateConcept<_Compare, 03904 typename iterator_traits<_InputIter1>::value_type, 03905 typename iterator_traits<_InputIter2>::value_type>) 03906 03907 while (__first1 != __last1 && __first2 != __last2) 03908 if (__comp(*__first1, *__first2)) { 03909 *__result = *__first1; 03910 ++__first1; 03911 ++__result; 03912 } 03913 else if (__comp(*__first2, *__first1)) { 03914 *__result = *__first2; 03915 ++__first2; 03916 ++__result; 03917 } 03918 else { 03919 ++__first1; 03920 ++__first2; 03921 } 03922 return copy(__first2, __last2, copy(__first1, __last1, __result)); 03923 } 03924 03925 // min_element and max_element, with and without an explicitly supplied 03926 // comparison function. 03927 03928 template<typename _ForwardIter> 03929 _ForwardIter 03930 max_element(_ForwardIter __first, _ForwardIter __last) 03931 { 03932 // concept requirements 03933 __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter>) 03934 __glibcpp_function_requires(_LessThanComparableConcept< 03935 typename iterator_traits<_ForwardIter>::value_type>) 03936 03937 if (__first == __last) return __first; 03938 _ForwardIter __result = __first; 03939 while (++__first != __last) 03940 if (*__result < *__first) 03941 __result = __first; 03942 return __result; 03943 } 03944 03945 template<typename _ForwardIter, typename _Compare> 03946 _ForwardIter 03947 max_element(_ForwardIter __first, _ForwardIter __last, 03948 _Compare __comp) 03949 { 03950 // concept requirements 03951 __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter>) 03952 __glibcpp_function_requires(_BinaryPredicateConcept<_Compare, 03953 typename iterator_traits<_ForwardIter>::value_type, 03954 typename iterator_traits<_ForwardIter>::value_type>) 03955 03956 if (__first == __last) return __first; 03957 _ForwardIter __result = __first; 03958 while (++__first != __last) 03959 if (__comp(*__result, *__first)) __result = __first; 03960 return __result; 03961 } 03962 03963 template<typename _ForwardIter> 03964 _ForwardIter 03965 min_element(_ForwardIter __first, _ForwardIter __last) 03966 { 03967 // concept requirements 03968 __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter>) 03969 __glibcpp_function_requires(_LessThanComparableConcept< 03970 typename iterator_traits<_ForwardIter>::value_type>) 03971 03972 if (__first == __last) return __first; 03973 _ForwardIter __result = __first; 03974 while (++__first != __last) 03975 if (*__first < *__result) 03976 __result = __first; 03977 return __result; 03978 } 03979 03980 template<typename _ForwardIter, typename _Compare> 03981 _ForwardIter 03982 min_element(_ForwardIter __first, _ForwardIter __last, 03983 _Compare __comp) 03984 { 03985 // concept requirements 03986 __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter>) 03987 __glibcpp_function_requires(_BinaryPredicateConcept<_Compare, 03988 typename iterator_traits<_ForwardIter>::value_type, 03989 typename iterator_traits<_ForwardIter>::value_type>) 03990 03991 if (__first == __last) return __first; 03992 _ForwardIter __result = __first; 03993 while (++__first != __last) 03994 if (__comp(*__first, *__result)) 03995 __result = __first; 03996 return __result; 03997 } 03998 03999 // next_permutation and prev_permutation, with and without an explicitly 04000 // supplied comparison function. 04001 04002 template<typename _BidirectionalIter> 04003 bool 04004 next_permutation(_BidirectionalIter __first, _BidirectionalIter __last) 04005 { 04006 // concept requirements 04007 __glibcpp_function_requires(_BidirectionalIteratorConcept<_BidirectionalIter>) 04008 __glibcpp_function_requires(_LessThanComparableConcept< 04009 typename iterator_traits<_BidirectionalIter>::value_type>) 04010 04011 if (__first == __last) 04012 return false; 04013 _BidirectionalIter __i = __first; 04014 ++__i; 04015 if (__i == __last) 04016 return false; 04017 __i = __last; 04018 --__i; 04019 04020 for(;;) { 04021 _BidirectionalIter __ii = __i; 04022 --__i; 04023 if (*__i < *__ii) { 04024 _BidirectionalIter __j = __last; 04025 while (!(*__i < *--__j)) 04026 {} 04027 iter_swap(__i, __j); 04028 reverse(__ii, __last); 04029 return true; 04030 } 04031 if (__i == __first) { 04032 reverse(__first, __last); 04033 return false; 04034 } 04035 } 04036 } 04037 04038 template<typename _BidirectionalIter, typename _Compare> 04039 bool 04040 next_permutation(_BidirectionalIter __first, _BidirectionalIter __last, 04041 _Compare __comp) 04042 { 04043 // concept requirements 04044 __glibcpp_function_requires(_BidirectionalIteratorConcept<_BidirectionalIter>) 04045 __glibcpp_function_requires(_BinaryPredicateConcept<_Compare, 04046 typename iterator_traits<_BidirectionalIter>::value_type, 04047 typename iterator_traits<_BidirectionalIter>::value_type>) 04048 04049 if (__first == __last) 04050 return false; 04051 _BidirectionalIter __i = __first; 04052 ++__i; 04053 if (__i == __last) 04054 return false; 04055 __i = __last; 04056 --__i; 04057 04058 for(;;) { 04059 _BidirectionalIter __ii = __i; 04060 --__i; 04061 if (__comp(*__i, *__ii)) { 04062 _BidirectionalIter __j = __last; 04063 while (!__comp(*__i, *--__j)) 04064 {} 04065 iter_swap(__i, __j); 04066 reverse(__ii, __last); 04067 return true; 04068 } 04069 if (__i == __first) { 04070 reverse(__first, __last); 04071 return false; 04072 } 04073 } 04074 } 04075 04076 template<typename _BidirectionalIter> 04077 bool 04078 prev_permutation(_BidirectionalIter __first, _BidirectionalIter __last) 04079 { 04080 // concept requirements 04081 __glibcpp_function_requires(_BidirectionalIteratorConcept<_BidirectionalIter>) 04082 __glibcpp_function_requires(_LessThanComparableConcept< 04083 typename iterator_traits<_BidirectionalIter>::value_type>) 04084 04085 if (__first == __last) 04086 return false; 04087 _BidirectionalIter __i = __first; 04088 ++__i; 04089 if (__i == __last) 04090 return false; 04091 __i = __last; 04092 --__i; 04093 04094 for(;;) { 04095 _BidirectionalIter __ii = __i; 04096 --__i; 04097 if (*__ii < *__i) { 04098 _BidirectionalIter __j = __last; 04099 while (!(*--__j < *__i)) 04100 {} 04101 iter_swap(__i, __j); 04102 reverse(__ii, __last); 04103 return true; 04104 } 04105 if (__i == __first) { 04106 reverse(__first, __last); 04107 return false; 04108 } 04109 } 04110 } 04111 04112 template<typename _BidirectionalIter, typename _Compare> 04113 bool 04114 prev_permutation(_BidirectionalIter __first, _BidirectionalIter __last, 04115 _Compare __comp) 04116 { 04117 // concept requirements 04118 __glibcpp_function_requires(_BidirectionalIteratorConcept<_BidirectionalIter>) 04119 __glibcpp_function_requires(_BinaryPredicateConcept<_Compare, 04120 typename iterator_traits<_BidirectionalIter>::value_type, 04121 typename iterator_traits<_BidirectionalIter>::value_type>) 04122 04123 if (__first == __last) 04124 return false; 04125 _BidirectionalIter __i = __first; 04126 ++__i; 04127 if (__i == __last) 04128 return false; 04129 __i = __last; 04130 --__i; 04131 04132 for(;;) { 04133 _BidirectionalIter __ii = __i; 04134 --__i; 04135 if (__comp(*__ii, *__i)) { 04136 _BidirectionalIter __j = __last; 04137 while (!__comp(*--__j, *__i)) 04138 {} 04139 iter_swap(__i, __j); 04140 reverse(__ii, __last); 04141 return true; 04142 } 04143 if (__i == __first) { 04144 reverse(__first, __last); 04145 return false; 04146 } 04147 } 04148 } 04149 04150 // find_first_of, with and without an explicitly supplied comparison function. 04151 04152 template<typename _InputIter, typename _ForwardIter> 04153 _InputIter 04154 find_first_of(_InputIter __first1, _InputIter __last1, 04155 _ForwardIter __first2, _ForwardIter __last2) 04156 { 04157 // concept requirements 04158 __glibcpp_function_requires(_InputIteratorConcept<_InputIter>) 04159 __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter>) 04160 __glibcpp_function_requires(_EqualOpConcept< 04161 typename iterator_traits<_InputIter>::value_type, 04162 typename iterator_traits<_ForwardIter>::value_type>) 04163 04164 for ( ; __first1 != __last1; ++__first1) 04165 for (_ForwardIter __iter = __first2; __iter != __last2; ++__iter) 04166 if (*__first1 == *__iter) 04167 return __first1; 04168 return __last1; 04169 } 04170 04171 template<typename _InputIter, typename _ForwardIter, typename _BinaryPredicate> 04172 _InputIter 04173 find_first_of(_InputIter __first1, _InputIter __last1, 04174 _ForwardIter __first2, _ForwardIter __last2, 04175 _BinaryPredicate __comp) 04176 { 04177 // concept requirements 04178 __glibcpp_function_requires(_InputIteratorConcept<_InputIter>) 04179 __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter>) 04180 __glibcpp_function_requires(_EqualOpConcept< 04181 typename iterator_traits<_InputIter>::value_type, 04182 typename iterator_traits<_ForwardIter>::value_type>) 04183 __glibcpp_function_requires(_BinaryPredicateConcept<_BinaryPredicate, 04184 typename iterator_traits<_InputIter>::value_type, 04185 typename iterator_traits<_ForwardIter>::value_type>) 04186 04187 for ( ; __first1 != __last1; ++__first1) 04188 for (_ForwardIter __iter = __first2; __iter != __last2; ++__iter) 04189 if (__comp(*__first1, *__iter)) 04190 return __first1; 04191 return __last1; 04192 } 04193 04194 04195 // find_end, with and without an explicitly supplied comparison function. 04196 // Search [first2, last2) as a subsequence in [first1, last1), and return 04197 // the *last* possible match. Note that find_end for bidirectional iterators 04198 // is much faster than for forward iterators. 04199 04200 // find_end for forward iterators. 04201 template<typename _ForwardIter1, typename _ForwardIter2> 04202 _ForwardIter1 04203 __find_end(_ForwardIter1 __first1, _ForwardIter1 __last1, 04204 _ForwardIter2 __first2, _ForwardIter2 __last2, 04205 forward_iterator_tag, forward_iterator_tag) 04206 { 04207 if (__first2 == __last2) 04208 return __last1; 04209 else { 04210 _ForwardIter1 __result = __last1; 04211 while (1) { 04212 _ForwardIter1 __new_result 04213 = search(__first1, __last1, __first2, __last2); 04214 if (__new_result == __last1) 04215 return __result; 04216 else { 04217 __result = __new_result; 04218 __first1 = __new_result; 04219 ++__first1; 04220 } 04221 } 04222 } 04223 } 04224 04225 template<typename _ForwardIter1, typename _ForwardIter2, 04226 typename _BinaryPredicate> 04227 _ForwardIter1 04228 __find_end(_ForwardIter1 __first1, _ForwardIter1 __last1, 04229 _ForwardIter2 __first2, _ForwardIter2 __last2, 04230 forward_iterator_tag, forward_iterator_tag, 04231 _BinaryPredicate __comp) 04232 { 04233 if (__first2 == __last2) 04234 return __last1; 04235 else { 04236 _ForwardIter1 __result = __last1; 04237 while (1) { 04238 _ForwardIter1 __new_result 04239 = search(__first1, __last1, __first2, __last2, __comp); 04240 if (__new_result == __last1) 04241 return __result; 04242 else { 04243 __result = __new_result; 04244 __first1 = __new_result; 04245 ++__first1; 04246 } 04247 } 04248 } 04249 } 04250 04251 // find_end for bidirectional iterators. Requires partial specialization. 04252 template<typename _BidirectionalIter1, typename _BidirectionalIter2> 04253 _BidirectionalIter1 04254 __find_end(_BidirectionalIter1 __first1, _BidirectionalIter1 __last1, 04255 _BidirectionalIter2 __first2, _BidirectionalIter2 __last2, 04256 bidirectional_iterator_tag, bidirectional_iterator_tag) 04257 { 04258 // concept requirements 04259 __glibcpp_function_requires(_BidirectionalIteratorConcept<_BidirectionalIter1>) 04260 __glibcpp_function_requires(_BidirectionalIteratorConcept<_BidirectionalIter2>) 04261 04262 typedef reverse_iterator<_BidirectionalIter1> _RevIter1; 04263 typedef reverse_iterator<_BidirectionalIter2> _RevIter2; 04264 04265 _RevIter1 __rlast1(__first1); 04266 _RevIter2 __rlast2(__first2); 04267 _RevIter1 __rresult = search(_RevIter1(__last1), __rlast1, 04268 _RevIter2(__last2), __rlast2); 04269 04270 if (__rresult == __rlast1) 04271 return __last1; 04272 else { 04273 _BidirectionalIter1 __result = __rresult.base(); 04274 advance(__result, -distance(__first2, __last2)); 04275 return __result; 04276 } 04277 } 04278 04279 template<typename _BidirectionalIter1, typename _BidirectionalIter2, 04280 typename _BinaryPredicate> 04281 _BidirectionalIter1 04282 __find_end(_BidirectionalIter1 __first1, _BidirectionalIter1 __last1, 04283 _BidirectionalIter2 __first2, _BidirectionalIter2 __last2, 04284 bidirectional_iterator_tag, bidirectional_iterator_tag, 04285 _BinaryPredicate __comp) 04286 { 04287 // concept requirements 04288 __glibcpp_function_requires(_BidirectionalIteratorConcept<_BidirectionalIter1>) 04289 __glibcpp_function_requires(_BidirectionalIteratorConcept<_BidirectionalIter2>) 04290 04291 typedef reverse_iterator<_BidirectionalIter1> _RevIter1; 04292 typedef reverse_iterator<_BidirectionalIter2> _RevIter2; 04293 04294 _RevIter1 __rlast1(__first1); 04295 _RevIter2 __rlast2(__first2); 04296 _RevIter1 __rresult = search(_RevIter1(__last1), __rlast1, 04297 _RevIter2(__last2), __rlast2, 04298 __comp); 04299 04300 if (__rresult == __rlast1) 04301 return __last1; 04302 else { 04303 _BidirectionalIter1 __result = __rresult.base(); 04304 advance(__result, -distance(__first2, __last2)); 04305 return __result; 04306 } 04307 } 04308 04309 // Dispatching functions for find_end. 04310 04311 template<typename _ForwardIter1, typename _ForwardIter2> 04312 inline _ForwardIter1 04313 find_end(_ForwardIter1 __first1, _ForwardIter1 __last1, 04314 _ForwardIter2 __first2, _ForwardIter2 __last2) 04315 { 04316 // concept requirements 04317 __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter1>) 04318 __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter2>) 04319 __glibcpp_function_requires(_EqualOpConcept< 04320 typename iterator_traits<_ForwardIter1>::value_type, 04321 typename iterator_traits<_ForwardIter2>::value_type>) 04322 04323 return __find_end(__first1, __last1, __first2, __last2, 04324 __iterator_category(__first1), 04325 __iterator_category(__first2)); 04326 } 04327 04328 template<typename _ForwardIter1, typename _ForwardIter2, 04329 typename _BinaryPredicate> 04330 inline _ForwardIter1 04331 find_end(_ForwardIter1 __first1, _ForwardIter1 __last1, 04332 _ForwardIter2 __first2, _ForwardIter2 __last2, 04333 _BinaryPredicate __comp) 04334 { 04335 // concept requirements 04336 __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter1>) 04337 __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter2>) 04338 __glibcpp_function_requires(_BinaryPredicateConcept<_BinaryPredicate, 04339 typename iterator_traits<_ForwardIter1>::value_type, 04340 typename iterator_traits<_ForwardIter2>::value_type>) 04341 04342 return __find_end(__first1, __last1, __first2, __last2, 04343 __iterator_category(__first1), 04344 __iterator_category(__first2), 04345 __comp); 04346 } 04347 04348 } // namespace std 04349 04350 #endif /* __GLIBCPP_INTERNAL_ALGO_H */ 04351

Generated on Wed Sep 29 13:54:51 2004 for libstdc++-v3 Source by doxygen 1.3.7