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 00056 /** @file stl_algo.h 00057 * This is an internal header file, included by other library headers. 00058 * You should not attempt to use it directly. 00059 */ 00060 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 00072 /** 00073 * @brief Find the median of three values. 00074 * @param a A value. 00075 * @param b A value. 00076 * @param c A value. 00077 * @return One of @p a, @p b or @p c. 00078 * 00079 * If @c {l,m,n} is some convolution of @p {a,b,c} such that @c l<=m<=n 00080 * then the value returned will be @c m. 00081 * This is an SGI extension. 00082 * @ingroup SGIextensions 00083 */ 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 00105 /** 00106 * @brief Find the median of three values using a predicate for comparison. 00107 * @param a A value. 00108 * @param b A value. 00109 * @param c A value. 00110 * @param comp A binary predicate. 00111 * @return One of @p a, @p b or @p c. 00112 * 00113 * If @c {l,m,n} is some convolution of @p {a,b,c} such that @p comp(l,m) 00114 * and @p comp(m,n) are both true then the value returned will be @c m. 00115 * This is an SGI extension. 00116 * @ingroup SGIextensions 00117 */ 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 00139 /** 00140 * @brief Apply a function to every element of a sequence. 00141 * @param first An input iterator. 00142 * @param last An input iterator. 00143 * @param f A unary function object. 00144 * @return @p f. 00145 * 00146 * Applies the function object @p f to each element in the range 00147 * @p [first,last). @p f must not modify the order of the sequence. 00148 * If @p f has a return value it is ignored. 00149 */ 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 00161 /** 00162 * @if maint 00163 * This is an overload used by find() for the Input Iterator case. 00164 * @endif 00165 */ 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 00177 /** 00178 * @if maint 00179 * This is an overload used by find_if() for the Input Iterator case. 00180 * @endif 00181 */ 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 00193 /** 00194 * @if maint 00195 * This is an overload used by find() for the RAI case. 00196 * @endif 00197 */ 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 00237 /** 00238 * @if maint 00239 * This is an overload used by find_if() for the RAI case. 00240 * @endif 00241 */ 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 00281 /** 00282 * @brief Find the first occurrence of a value in a sequence. 00283 * @param first An input iterator. 00284 * @param last An input iterator. 00285 * @param val The value to find. 00286 * @return The first iterator @c i in the range @p [first,last) 00287 * such that @c *i == @p val, or @p last if no such iterator exists. 00288 */ 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 00301 /** 00302 * @brief Find the first element in a sequence for which a predicate is true. 00303 * @param first An input iterator. 00304 * @param last An input iterator. 00305 * @param pred A predicate. 00306 * @return The first iterator @c i in the range @p [first,last) 00307 * such that @p pred(*i) is true, or @p last if no such iterator exists. 00308 */ 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 00321 /** 00322 * @brief Find two adjacent values in a sequence that are equal. 00323 * @param first A forward iterator. 00324 * @param last A forward iterator. 00325 * @return The first iterator @c i such that @c i and @c i+1 are both 00326 * valid iterators in @p [first,last) and such that @c *i == @c *(i+1), 00327 * or @p last if no such iterator exists. 00328 */ 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 00348 /** 00349 * @brief Find two adjacent values in a sequence using a predicate. 00350 * @param first A forward iterator. 00351 * @param last A forward iterator. 00352 * @param binary_pred A binary predicate. 00353 * @return The first iterator @c i such that @c i and @c i+1 are both 00354 * valid iterators in @p [first,last) and such that 00355 * @p binary_pred(*i,*(i+1)) is true, or @p last if no such iterator 00356 * exists. 00357 */ 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 00379 /** 00380 * @brief Count the number of copies of a value in a sequence. 00381 * @param first An input iterator. 00382 * @param last An input iterator. 00383 * @param value The value to be counted. 00384 * @return The number of iterators @c i in the range @p [first,last) 00385 * for which @c *i == @p value 00386 */ 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 00403 /** 00404 * @brief Count the elements of a sequence for which a predicate is true. 00405 * @param first An input iterator. 00406 * @param last An input iterator. 00407 * @param pred A predicate. 00408 * @return The number of iterators @c i in the range @p [first,last) 00409 * for which @p pred(*i) is true. 00410 */ 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 00427 /** 00428 * @brief Search a sequence for a matching sub-sequence. 00429 * @param first1 A forward iterator. 00430 * @param last1 A forward iterator. 00431 * @param first2 A forward iterator. 00432 * @param last2 A forward iterator. 00433 * @return The first iterator @c i in the range 00434 * @p [first1,last1-(last2-first2)) such that @c *(i+N) == @p *(first2+N) 00435 * for each @c N in the range @p [0,last2-first2), or @p last1 if no 00436 * such iterator exists. 00437 * 00438 * Searches the range @p [first1,last1) for a sub-sequence that compares 00439 * equal value-by-value with the sequence given by @p [first2,last2) and 00440 * returns an iterator to the first element of the sub-sequence, or 00441 * @p last1 if the sub-sequence is not found. 00442 * 00443 * Because the sub-sequence must lie completely within the range 00444 * @p [first1,last1) it must start at a position less than 00445 * @p last1-(last2-first2) where @p last2-first2 is the length of the 00446 * sub-sequence. 00447 * This means that the returned iterator @c i will be in the range 00448 * @p [first1,last1-(last2-first2)) 00449 */ 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 00502 /** 00503 * @brief Search a sequence for a matching sub-sequence using a predicate. 00504 * @param first1 A forward iterator. 00505 * @param last1 A forward iterator. 00506 * @param first2 A forward iterator. 00507 * @param last2 A forward iterator. 00508 * @param predicate A binary predicate. 00509 * @return The first iterator @c i in the range 00510 * @p [first1,last1-(last2-first2)) such that 00511 * @p predicate(*(i+N),*(first2+N)) is true for each @c N in the range 00512 * @p [0,last2-first2), or @p last1 if no such iterator exists. 00513 * 00514 * Searches the range @p [first1,last1) for a sub-sequence that compares 00515 * equal value-by-value with the sequence given by @p [first2,last2), 00516 * using @p predicate to determine equality, and returns an iterator 00517 * to the first element of the sub-sequence, or @p last1 if no such 00518 * iterator exists. 00519 * 00520 * @see search(_ForwardIter1, _ForwardIter1, _ForwardIter2, _ForwardIter2) 00521 */ 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 00583 /** 00584 * @brief Search a sequence for a number of consecutive values. 00585 * @param first A forward iterator. 00586 * @param last A forward iterator. 00587 * @param count The number of consecutive values. 00588 * @param val The value to find. 00589 * @return The first iterator @c i in the range @p [first,last-count) 00590 * such that @c *(i+N) == @p val for each @c N in the range @p [0,count), 00591 * or @p last if no such iterator exists. 00592 * 00593 * Searches the range @p [first,last) for @p count consecutive elements 00594 * equal to @p val. 00595 */ 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 typename iterator_traits<_ForwardIter>::difference_type __n = __count; 00613 --__n; 00614 _ForwardIter __i = __first; 00615 ++__i; 00616 while (__i != __last && __n != 0 && *__i == __val) { 00617 ++__i; 00618 --__n; 00619 } 00620 if (__n == 0) 00621 return __first; 00622 else 00623 __first = find(__i, __last, __val); 00624 } 00625 return __last; 00626 } 00627 } 00628 00629 /** 00630 * @brief Search a sequence for a number of consecutive values using a 00631 * predicate. 00632 * @param first A forward iterator. 00633 * @param last A forward iterator. 00634 * @param count The number of consecutive values. 00635 * @param val The value to find. 00636 * @param binary_pred A binary predicate. 00637 * @return The first iterator @c i in the range @p [first,last-count) 00638 * such that @p binary_pred(*(i+N),val) is true for each @c N in the 00639 * range @p [0,count), or @p last if no such iterator exists. 00640 * 00641 * Searches the range @p [first,last) for @p count consecutive elements 00642 * for which the predicate returns true. 00643 */ 00644 template<typename _ForwardIter, typename _Integer, typename _Tp, 00645 typename _BinaryPred> 00646 _ForwardIter 00647 search_n(_ForwardIter __first, _ForwardIter __last, 00648 _Integer __count, const _Tp& __val, 00649 _BinaryPred __binary_pred) 00650 { 00651 // concept requirements 00652 __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter>) 00653 __glibcpp_function_requires(_BinaryPredicateConcept<_BinaryPred, 00654 typename iterator_traits<_ForwardIter>::value_type, _Tp>) 00655 00656 if (__count <= 0) 00657 return __first; 00658 else { 00659 while (__first != __last) { 00660 if (__binary_pred(*__first, __val)) 00661 break; 00662 ++__first; 00663 } 00664 while (__first != __last) { 00665 typename iterator_traits<_ForwardIter>::difference_type __n = __count; 00666 --__n; 00667 _ForwardIter __i = __first; 00668 ++__i; 00669 while (__i != __last && __n != 0 && __binary_pred(*__i, __val)) { 00670 ++__i; 00671 --__n; 00672 } 00673 if (__n == 0) 00674 return __first; 00675 else { 00676 while (__i != __last) { 00677 if (__binary_pred(*__i, __val)) 00678 break; 00679 ++__i; 00680 } 00681 __first = __i; 00682 } 00683 } 00684 return __last; 00685 } 00686 } 00687 00688 /** 00689 * @brief Swap the elements of two sequences. 00690 * @param first1 A forward iterator. 00691 * @param last1 A forward iterator. 00692 * @param first2 A forward iterator. 00693 * @return An iterator equal to @p first2+(last1-first1). 00694 * 00695 * Swaps each element in the range @p [first1,last1) with the 00696 * corresponding element in the range @p [first2,(last1-first1)). 00697 * The ranges must not overlap. 00698 */ 00699 template<typename _ForwardIter1, typename _ForwardIter2> 00700 _ForwardIter2 00701 swap_ranges(_ForwardIter1 __first1, _ForwardIter1 __last1, 00702 _ForwardIter2 __first2) 00703 { 00704 // concept requirements 00705 __glibcpp_function_requires(_Mutable_ForwardIteratorConcept<_ForwardIter1>) 00706 __glibcpp_function_requires(_Mutable_ForwardIteratorConcept<_ForwardIter2>) 00707 __glibcpp_function_requires(_ConvertibleConcept< 00708 typename iterator_traits<_ForwardIter1>::value_type, 00709 typename iterator_traits<_ForwardIter2>::value_type>) 00710 __glibcpp_function_requires(_ConvertibleConcept< 00711 typename iterator_traits<_ForwardIter2>::value_type, 00712 typename iterator_traits<_ForwardIter1>::value_type>) 00713 00714 for ( ; __first1 != __last1; ++__first1, ++__first2) 00715 iter_swap(__first1, __first2); 00716 return __first2; 00717 } 00718 00719 /** 00720 * @brief Perform an operation on a sequence. 00721 * @param first An input iterator. 00722 * @param last An input iterator. 00723 * @param result An output iterator. 00724 * @param unary_op A unary operator. 00725 * @return An output iterator equal to @p result+(last-first). 00726 * 00727 * Applies the operator to each element in the input range and assigns 00728 * the results to successive elements of the output sequence. 00729 * Evaluates @p *(result+N)=unary_op(*(first+N)) for each @c N in the 00730 * range @p [0,last-first). 00731 * 00732 * @p unary_op must not alter its argument. 00733 */ 00734 template<typename _InputIter, typename _OutputIter, typename _UnaryOperation> 00735 _OutputIter 00736 transform(_InputIter __first, _InputIter __last, 00737 _OutputIter __result, _UnaryOperation __unary_op) 00738 { 00739 // concept requirements 00740 __glibcpp_function_requires(_InputIteratorConcept<_InputIter>) 00741 __glibcpp_function_requires(_OutputIteratorConcept<_OutputIter, 00742 // "the type returned by a _UnaryOperation" 00743 __typeof__(__unary_op(*__first))>) 00744 00745 for ( ; __first != __last; ++__first, ++__result) 00746 *__result = __unary_op(*__first); 00747 return __result; 00748 } 00749 00750 /** 00751 * @brief Perform an operation on corresponding elements of two sequences. 00752 * @param first1 An input iterator. 00753 * @param last1 An input iterator. 00754 * @param first2 An input iterator. 00755 * @param result An output iterator. 00756 * @param binary_op A binary operator. 00757 * @return An output iterator equal to @p result+(last-first). 00758 * 00759 * Applies the operator to the corresponding elements in the two 00760 * input ranges and assigns the results to successive elements of the 00761 * output sequence. 00762 * Evaluates @p *(result+N)=binary_op(*(first1+N),*(first2+N)) for each 00763 * @c N in the range @p [0,last1-first1). 00764 * 00765 * @p binary_op must not alter either of its arguments. 00766 */ 00767 template<typename _InputIter1, typename _InputIter2, typename _OutputIter, 00768 typename _BinaryOperation> 00769 _OutputIter 00770 transform(_InputIter1 __first1, _InputIter1 __last1, 00771 _InputIter2 __first2, _OutputIter __result, 00772 _BinaryOperation __binary_op) 00773 { 00774 // concept requirements 00775 __glibcpp_function_requires(_InputIteratorConcept<_InputIter1>) 00776 __glibcpp_function_requires(_InputIteratorConcept<_InputIter2>) 00777 __glibcpp_function_requires(_OutputIteratorConcept<_OutputIter, 00778 // "the type returned by a _BinaryOperation" 00779 __typeof__(__binary_op(*__first1,*__first2))>) 00780 00781 for ( ; __first1 != __last1; ++__first1, ++__first2, ++__result) 00782 *__result = __binary_op(*__first1, *__first2); 00783 return __result; 00784 } 00785 00786 /** 00787 * @brief Replace each occurrence of one value in a sequence with another 00788 * value. 00789 * @param first A forward iterator. 00790 * @param last A forward iterator. 00791 * @param old_value The value to be replaced. 00792 * @param new_value The replacement value. 00793 * @return replace() returns no value. 00794 * 00795 * For each iterator @c i in the range @p [first,last) if @c *i == 00796 * @p old_value then the assignment @c *i = @p new_value is performed. 00797 */ 00798 template<typename _ForwardIter, typename _Tp> 00799 void 00800 replace(_ForwardIter __first, _ForwardIter __last, 00801 const _Tp& __old_value, const _Tp& __new_value) 00802 { 00803 // concept requirements 00804 __glibcpp_function_requires(_Mutable_ForwardIteratorConcept<_ForwardIter>) 00805 __glibcpp_function_requires(_EqualOpConcept< 00806 typename iterator_traits<_ForwardIter>::value_type, _Tp>) 00807 __glibcpp_function_requires(_ConvertibleConcept<_Tp, 00808 typename iterator_traits<_ForwardIter>::value_type>) 00809 00810 for ( ; __first != __last; ++__first) 00811 if (*__first == __old_value) 00812 *__first = __new_value; 00813 } 00814 00815 /** 00816 * @brief Replace each value in a sequence for which a predicate returns 00817 * true with another value. 00818 * @param first A forward iterator. 00819 * @param last A forward iterator. 00820 * @param pred A predicate. 00821 * @param new_value The replacement value. 00822 * @return replace_if() returns no value. 00823 * 00824 * For each iterator @c i in the range @p [first,last) if @p pred(*i) 00825 * is true then the assignment @c *i = @p new_value is performed. 00826 */ 00827 template<typename _ForwardIter, typename _Predicate, typename _Tp> 00828 void 00829 replace_if(_ForwardIter __first, _ForwardIter __last, 00830 _Predicate __pred, const _Tp& __new_value) 00831 { 00832 // concept requirements 00833 __glibcpp_function_requires(_Mutable_ForwardIteratorConcept<_ForwardIter>) 00834 __glibcpp_function_requires(_ConvertibleConcept<_Tp, 00835 typename iterator_traits<_ForwardIter>::value_type>) 00836 __glibcpp_function_requires(_UnaryPredicateConcept<_Predicate, 00837 typename iterator_traits<_ForwardIter>::value_type>) 00838 00839 for ( ; __first != __last; ++__first) 00840 if (__pred(*__first)) 00841 *__first = __new_value; 00842 } 00843 00844 /** 00845 * @brief Copy a sequence, replacing each element of one value with another 00846 * value. 00847 * @param first An input iterator. 00848 * @param last An input iterator. 00849 * @param result An output iterator. 00850 * @param old_value The value to be replaced. 00851 * @param new_value The replacement value. 00852 * @return The end of the output sequence, @p result+(last-first). 00853 * 00854 * Copies each element in the input range @p [first,last) to the 00855 * output range @p [result,result+(last-first)) replacing elements 00856 * equal to @p old_value with @p new_value. 00857 */ 00858 template<typename _InputIter, typename _OutputIter, typename _Tp> 00859 _OutputIter 00860 replace_copy(_InputIter __first, _InputIter __last, 00861 _OutputIter __result, 00862 const _Tp& __old_value, const _Tp& __new_value) 00863 { 00864 // concept requirements 00865 __glibcpp_function_requires(_InputIteratorConcept<_InputIter>) 00866 __glibcpp_function_requires(_OutputIteratorConcept<_OutputIter, 00867 typename iterator_traits<_InputIter>::value_type>) 00868 __glibcpp_function_requires(_EqualOpConcept< 00869 typename iterator_traits<_InputIter>::value_type, _Tp>) 00870 00871 for ( ; __first != __last; ++__first, ++__result) 00872 *__result = *__first == __old_value ? __new_value : *__first; 00873 return __result; 00874 } 00875 00876 /** 00877 * @brief Copy a sequence, replacing each value for which a predicate 00878 * returns true with another value. 00879 * @param first An input iterator. 00880 * @param last An input iterator. 00881 * @param result An output iterator. 00882 * @param pred A predicate. 00883 * @param new_value The replacement value. 00884 * @return The end of the output sequence, @p result+(last-first). 00885 * 00886 * Copies each element in the range @p [first,last) to the range 00887 * @p [result,result+(last-first)) replacing elements for which 00888 * @p pred returns true with @p new_value. 00889 */ 00890 template<typename _InputIter, typename _OutputIter, typename _Predicate, 00891 typename _Tp> 00892 _OutputIter 00893 replace_copy_if(_InputIter __first, _InputIter __last, 00894 _OutputIter __result, 00895 _Predicate __pred, const _Tp& __new_value) 00896 { 00897 // concept requirements 00898 __glibcpp_function_requires(_InputIteratorConcept<_InputIter>) 00899 __glibcpp_function_requires(_OutputIteratorConcept<_OutputIter, 00900 typename iterator_traits<_InputIter>::value_type>) 00901 __glibcpp_function_requires(_UnaryPredicateConcept<_Predicate, 00902 typename iterator_traits<_InputIter>::value_type>) 00903 00904 for ( ; __first != __last; ++__first, ++__result) 00905 *__result = __pred(*__first) ? __new_value : *__first; 00906 return __result; 00907 } 00908 00909 /** 00910 * @brief Assign the result of a function object to each value in a 00911 * sequence. 00912 * @param first A forward iterator. 00913 * @param last A forward iterator. 00914 * @param gen A function object taking no arguments. 00915 * @return generate() returns no value. 00916 * 00917 * Performs the assignment @c *i = @p gen() for each @c i in the range 00918 * @p [first,last). 00919 */ 00920 template<typename _ForwardIter, typename _Generator> 00921 void 00922 generate(_ForwardIter __first, _ForwardIter __last, _Generator __gen) 00923 { 00924 // concept requirements 00925 __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter>) 00926 __glibcpp_function_requires(_GeneratorConcept<_Generator, 00927 typename iterator_traits<_ForwardIter>::value_type>) 00928 00929 for ( ; __first != __last; ++__first) 00930 *__first = __gen(); 00931 } 00932 00933 /** 00934 * @brief Assign the result of a function object to each value in a 00935 * sequence. 00936 * @param first A forward iterator. 00937 * @param n The length of the sequence. 00938 * @param gen A function object taking no arguments. 00939 * @return The end of the sequence, @p first+n 00940 * 00941 * Performs the assignment @c *i = @p gen() for each @c i in the range 00942 * @p [first,first+n). 00943 */ 00944 template<typename _OutputIter, typename _Size, typename _Generator> 00945 _OutputIter 00946 generate_n(_OutputIter __first, _Size __n, _Generator __gen) 00947 { 00948 // concept requirements 00949 __glibcpp_function_requires(_OutputIteratorConcept<_OutputIter, 00950 // "the type returned by a _Generator" 00951 __typeof__(__gen())>) 00952 00953 for ( ; __n > 0; --__n, ++__first) 00954 *__first = __gen(); 00955 return __first; 00956 } 00957 00958 /** 00959 * @brief Copy a sequence, removing elements of a given value. 00960 * @param first An input iterator. 00961 * @param last An input iterator. 00962 * @param result An output iterator. 00963 * @param value The value to be removed. 00964 * @return An iterator designating the end of the resulting sequence. 00965 * 00966 * Copies each element in the range @p [first,last) not equal to @p value 00967 * to the range beginning at @p result. 00968 * remove_copy() is stable, so the relative order of elements that are 00969 * copied is unchanged. 00970 */ 00971 template<typename _InputIter, typename _OutputIter, typename _Tp> 00972 _OutputIter 00973 remove_copy(_InputIter __first, _InputIter __last, 00974 _OutputIter __result, const _Tp& __value) 00975 { 00976 // concept requirements 00977 __glibcpp_function_requires(_InputIteratorConcept<_InputIter>) 00978 __glibcpp_function_requires(_OutputIteratorConcept<_OutputIter, 00979 typename iterator_traits<_InputIter>::value_type>) 00980 __glibcpp_function_requires(_EqualOpConcept< 00981 typename iterator_traits<_InputIter>::value_type, _Tp>) 00982 00983 for ( ; __first != __last; ++__first) 00984 if (!(*__first == __value)) { 00985 *__result = *__first; 00986 ++__result; 00987 } 00988 return __result; 00989 } 00990 00991 /** 00992 * @brief Copy a sequence, removing elements for which a predicate is true. 00993 * @param first An input iterator. 00994 * @param last An input iterator. 00995 * @param result An output iterator. 00996 * @param pred A predicate. 00997 * @return An iterator designating the end of the resulting sequence. 00998 * 00999 * Copies each element in the range @p [first,last) for which 01000 * @p pred returns true to the range beginning at @p result. 01001 * 01002 * remove_copy_if() is stable, so the relative order of elements that are 01003 * copied is unchanged. 01004 */ 01005 template<typename _InputIter, typename _OutputIter, typename _Predicate> 01006 _OutputIter 01007 remove_copy_if(_InputIter __first, _InputIter __last, 01008 _OutputIter __result, _Predicate __pred) 01009 { 01010 // concept requirements 01011 __glibcpp_function_requires(_InputIteratorConcept<_InputIter>) 01012 __glibcpp_function_requires(_OutputIteratorConcept<_OutputIter, 01013 typename iterator_traits<_InputIter>::value_type>) 01014 __glibcpp_function_requires(_UnaryPredicateConcept<_Predicate, 01015 typename iterator_traits<_InputIter>::value_type>) 01016 01017 for ( ; __first != __last; ++__first) 01018 if (!__pred(*__first)) { 01019 *__result = *__first; 01020 ++__result; 01021 } 01022 return __result; 01023 } 01024 01025 /** 01026 * @brief Remove elements from a sequence. 01027 * @param first An input iterator. 01028 * @param last An input iterator. 01029 * @param value The value to be removed. 01030 * @return An iterator designating the end of the resulting sequence. 01031 * 01032 * All elements equal to @p value are removed from the range 01033 * @p [first,last). 01034 * 01035 * remove() is stable, so the relative order of elements that are 01036 * not removed is unchanged. 01037 * 01038 * Elements between the end of the resulting sequence and @p last 01039 * are still present, but their value is unspecified. 01040 */ 01041 template<typename _ForwardIter, typename _Tp> 01042 _ForwardIter 01043 remove(_ForwardIter __first, _ForwardIter __last, 01044 const _Tp& __value) 01045 { 01046 // concept requirements 01047 __glibcpp_function_requires(_Mutable_ForwardIteratorConcept<_ForwardIter>) 01048 __glibcpp_function_requires(_ConvertibleConcept<_Tp, 01049 typename iterator_traits<_ForwardIter>::value_type>) 01050 __glibcpp_function_requires(_EqualOpConcept< 01051 typename iterator_traits<_ForwardIter>::value_type, _Tp>) 01052 01053 __first = find(__first, __last, __value); 01054 _ForwardIter __i = __first; 01055 return __first == __last ? __first 01056 : remove_copy(++__i, __last, __first, __value); 01057 } 01058 01059 /** 01060 * @brief Remove elements from a sequence using a predicate. 01061 * @param first A forward iterator. 01062 * @param last A forward iterator. 01063 * @param pred A predicate. 01064 * @return An iterator designating the end of the resulting sequence. 01065 * 01066 * All elements for which @p pred returns true are removed from the range 01067 * @p [first,last). 01068 * 01069 * remove_if() is stable, so the relative order of elements that are 01070 * not removed is unchanged. 01071 * 01072 * Elements between the end of the resulting sequence and @p last 01073 * are still present, but their value is unspecified. 01074 */ 01075 template<typename _ForwardIter, typename _Predicate> 01076 _ForwardIter 01077 remove_if(_ForwardIter __first, _ForwardIter __last, 01078 _Predicate __pred) 01079 { 01080 // concept requirements 01081 __glibcpp_function_requires(_Mutable_ForwardIteratorConcept<_ForwardIter>) 01082 __glibcpp_function_requires(_UnaryPredicateConcept<_Predicate, 01083 typename iterator_traits<_ForwardIter>::value_type>) 01084 01085 __first = find_if(__first, __last, __pred); 01086 _ForwardIter __i = __first; 01087 return __first == __last ? __first 01088 : remove_copy_if(++__i, __last, __first, __pred); 01089 } 01090 01091 /** 01092 * @if maint 01093 * This is an uglified unique_copy(_InputIter, _InputIter, _OutputIter) 01094 * overloaded for output iterators. 01095 * @endif 01096 */ 01097 template<typename _InputIter, typename _OutputIter> 01098 _OutputIter 01099 __unique_copy(_InputIter __first, _InputIter __last, 01100 _OutputIter __result, 01101 output_iterator_tag) 01102 { 01103 // concept requirements -- taken care of in dispatching function 01104 typename iterator_traits<_InputIter>::value_type __value = *__first; 01105 *__result = __value; 01106 while (++__first != __last) 01107 if (!(__value == *__first)) { 01108 __value = *__first; 01109 *++__result = __value; 01110 } 01111 return ++__result; 01112 } 01113 01114 /** 01115 * @if maint 01116 * This is an uglified unique_copy(_InputIter, _InputIter, _OutputIter) 01117 * overloaded for forward iterators. 01118 * @endif 01119 */ 01120 template<typename _InputIter, typename _ForwardIter> 01121 _ForwardIter 01122 __unique_copy(_InputIter __first, _InputIter __last, 01123 _ForwardIter __result, 01124 forward_iterator_tag) 01125 { 01126 // concept requirements -- taken care of in dispatching function 01127 *__result = *__first; 01128 while (++__first != __last) 01129 if (!(*__result == *__first)) 01130 *++__result = *__first; 01131 return ++__result; 01132 } 01133 01134 /** 01135 * @brief Copy a sequence, removing consecutive duplicate values. 01136 * @param first An input iterator. 01137 * @param last An input iterator. 01138 * @param result An output iterator. 01139 * @return An iterator designating the end of the resulting sequence. 01140 * 01141 * Copies each element in the range @p [first,last) to the range 01142 * beginning at @p result, except that only the first element is copied 01143 * from groups of consecutive elements that compare equal. 01144 * unique_copy() is stable, so the relative order of elements that are 01145 * copied is unchanged. 01146 */ 01147 template<typename _InputIter, typename _OutputIter> 01148 inline _OutputIter 01149 unique_copy(_InputIter __first, _InputIter __last, 01150 _OutputIter __result) 01151 { 01152 // concept requirements 01153 __glibcpp_function_requires(_InputIteratorConcept<_InputIter>) 01154 __glibcpp_function_requires(_OutputIteratorConcept<_OutputIter, 01155 typename iterator_traits<_InputIter>::value_type>) 01156 __glibcpp_function_requires(_EqualityComparableConcept< 01157 typename iterator_traits<_InputIter>::value_type>) 01158 01159 typedef typename iterator_traits<_OutputIter>::iterator_category _IterType; 01160 01161 if (__first == __last) return __result; 01162 return __unique_copy(__first, __last, __result, _IterType()); 01163 } 01164 01165 /** 01166 * @if maint 01167 * This is an uglified 01168 * unique_copy(_InputIter, _InputIter, _OutputIter, _BinaryPredicate) 01169 * overloaded for output iterators. 01170 * @endif 01171 */ 01172 template<typename _InputIter, typename _OutputIter, typename _BinaryPredicate> 01173 _OutputIter 01174 __unique_copy(_InputIter __first, _InputIter __last, 01175 _OutputIter __result, 01176 _BinaryPredicate __binary_pred, 01177 output_iterator_tag) 01178 { 01179 // concept requirements -- iterators already checked 01180 __glibcpp_function_requires(_BinaryPredicateConcept<_BinaryPredicate, 01181 typename iterator_traits<_InputIter>::value_type, 01182 typename iterator_traits<_InputIter>::value_type>) 01183 01184 typename iterator_traits<_InputIter>::value_type __value = *__first; 01185 *__result = __value; 01186 while (++__first != __last) 01187 if (!__binary_pred(__value, *__first)) { 01188 __value = *__first; 01189 *++__result = __value; 01190 } 01191 return ++__result; 01192 } 01193 01194 /** 01195 * @if maint 01196 * This is an uglified 01197 * unique_copy(_InputIter, _InputIter, _OutputIter, _BinaryPredicate) 01198 * overloaded for forward iterators. 01199 * @endif 01200 */ 01201 template<typename _InputIter, typename _ForwardIter, typename _BinaryPredicate> 01202 _ForwardIter 01203 __unique_copy(_InputIter __first, _InputIter __last, 01204 _ForwardIter __result, 01205 _BinaryPredicate __binary_pred, 01206 forward_iterator_tag) 01207 { 01208 // concept requirements -- iterators already checked 01209 __glibcpp_function_requires(_BinaryPredicateConcept<_BinaryPredicate, 01210 typename iterator_traits<_ForwardIter>::value_type, 01211 typename iterator_traits<_InputIter>::value_type>) 01212 01213 *__result = *__first; 01214 while (++__first != __last) 01215 if (!__binary_pred(*__result, *__first)) *++__result = *__first; 01216 return ++__result; 01217 } 01218 01219 /** 01220 * @brief Copy a sequence, removing consecutive values using a predicate. 01221 * @param first An input iterator. 01222 * @param last An input iterator. 01223 * @param result An output iterator. 01224 * @param binary_pred A binary predicate. 01225 * @return An iterator designating the end of the resulting sequence. 01226 * 01227 * Copies each element in the range @p [first,last) to the range 01228 * beginning at @p result, except that only the first element is copied 01229 * from groups of consecutive elements for which @p binary_pred returns 01230 * true. 01231 * unique_copy() is stable, so the relative order of elements that are 01232 * copied is unchanged. 01233 */ 01234 template<typename _InputIter, typename _OutputIter, typename _BinaryPredicate> 01235 inline _OutputIter 01236 unique_copy(_InputIter __first, _InputIter __last, 01237 _OutputIter __result, 01238 _BinaryPredicate __binary_pred) 01239 { 01240 // concept requirements -- predicates checked later 01241 __glibcpp_function_requires(_InputIteratorConcept<_InputIter>) 01242 __glibcpp_function_requires(_OutputIteratorConcept<_OutputIter, 01243 typename iterator_traits<_InputIter>::value_type>) 01244 01245 typedef typename iterator_traits<_OutputIter>::iterator_category _IterType; 01246 01247 if (__first == __last) return __result; 01248 return __unique_copy(__first, __last, 01249 __result, __binary_pred, _IterType()); 01250 } 01251 01252 /** 01253 * @brief Remove consecutive duplicate values from a sequence. 01254 * @param first A forward iterator. 01255 * @param last A forward iterator. 01256 * @return An iterator designating the end of the resulting sequence. 01257 * 01258 * Removes all but the first element from each group of consecutive 01259 * values that compare equal. 01260 * unique() is stable, so the relative order of elements that are 01261 * not removed is unchanged. 01262 * Elements between the end of the resulting sequence and @p last 01263 * are still present, but their value is unspecified. 01264 */ 01265 template<typename _ForwardIter> 01266 _ForwardIter 01267 unique(_ForwardIter __first, _ForwardIter __last) 01268 { 01269 // concept requirements 01270 __glibcpp_function_requires(_Mutable_ForwardIteratorConcept<_ForwardIter>) 01271 __glibcpp_function_requires(_EqualityComparableConcept< 01272 typename iterator_traits<_ForwardIter>::value_type>) 01273 01274 __first = adjacent_find(__first, __last); 01275 return unique_copy(__first, __last, __first); 01276 } 01277 01278 /** 01279 * @brief Remove consecutive values from a sequence using a predicate. 01280 * @param first A forward iterator. 01281 * @param last A forward iterator. 01282 * @param binary_pred A binary predicate. 01283 * @return An iterator designating the end of the resulting sequence. 01284 * 01285 * Removes all but the first element from each group of consecutive 01286 * values for which @p binary_pred returns true. 01287 * unique() is stable, so the relative order of elements that are 01288 * not removed is unchanged. 01289 * Elements between the end of the resulting sequence and @p last 01290 * are still present, but their value is unspecified. 01291 */ 01292 template<typename _ForwardIter, typename _BinaryPredicate> 01293 _ForwardIter 01294 unique(_ForwardIter __first, _ForwardIter __last, 01295 _BinaryPredicate __binary_pred) 01296 { 01297 // concept requirements 01298 __glibcpp_function_requires(_Mutable_ForwardIteratorConcept<_ForwardIter>) 01299 __glibcpp_function_requires(_BinaryPredicateConcept<_BinaryPredicate, 01300 typename iterator_traits<_ForwardIter>::value_type, 01301 typename iterator_traits<_ForwardIter>::value_type>) 01302 01303 __first = adjacent_find(__first, __last, __binary_pred); 01304 return unique_copy(__first, __last, __first, __binary_pred); 01305 } 01306 01307 /** 01308 * @if maint 01309 * This is an uglified reverse(_BidirectionalIter, _BidirectionalIter) 01310 * overloaded for bidirectional iterators. 01311 * @endif 01312 */ 01313 template<typename _BidirectionalIter> 01314 void 01315 __reverse(_BidirectionalIter __first, _BidirectionalIter __last, 01316 bidirectional_iterator_tag) 01317 { 01318 while (true) 01319 if (__first == __last || __first == --__last) 01320 return; 01321 else 01322 iter_swap(__first++, __last); 01323 } 01324 01325 /** 01326 * @if maint 01327 * This is an uglified reverse(_BidirectionalIter, _BidirectionalIter) 01328 * overloaded for bidirectional iterators. 01329 * @endif 01330 */ 01331 template<typename _RandomAccessIter> 01332 void 01333 __reverse(_RandomAccessIter __first, _RandomAccessIter __last, 01334 random_access_iterator_tag) 01335 { 01336 while (__first < __last) 01337 iter_swap(__first++, --__last); 01338 } 01339 01340 /** 01341 * @brief Reverse a sequence. 01342 * @param first A bidirectional iterator. 01343 * @param last A bidirectional iterator. 01344 * @return reverse() returns no value. 01345 * 01346 * Reverses the order of the elements in the range @p [first,last), 01347 * so that the first element becomes the last etc. 01348 * For every @c i such that @p 0<=i<=(last-first)/2), @p reverse() 01349 * swaps @p *(first+i) and @p *(last-(i+1)) 01350 */ 01351 template<typename _BidirectionalIter> 01352 inline void 01353 reverse(_BidirectionalIter __first, _BidirectionalIter __last) 01354 { 01355 // concept requirements 01356 __glibcpp_function_requires(_Mutable_BidirectionalIteratorConcept< 01357 _BidirectionalIter>) 01358 __reverse(__first, __last, __iterator_category(__first)); 01359 } 01360 01361 /** 01362 * @brief Copy a sequence, reversing its elements. 01363 * @param first A bidirectional iterator. 01364 * @param last A bidirectional iterator. 01365 * @param result An output iterator. 01366 * @return An iterator designating the end of the resulting sequence. 01367 * 01368 * Copies the elements in the range @p [first,last) to the range 01369 * @p [result,result+(last-first)) such that the order of the 01370 * elements is reversed. 01371 * For every @c i such that @p 0<=i<=(last-first), @p reverse_copy() 01372 * performs the assignment @p *(result+(last-first)-i) = *(first+i). 01373 * The ranges @p [first,last) and @p [result,result+(last-first)) 01374 * must not overlap. 01375 */ 01376 template<typename _BidirectionalIter, typename _OutputIter> 01377 _OutputIter 01378 reverse_copy(_BidirectionalIter __first, _BidirectionalIter __last, 01379 _OutputIter __result) 01380 { 01381 // concept requirements 01382 __glibcpp_function_requires(_BidirectionalIteratorConcept<_BidirectionalIter>) 01383 __glibcpp_function_requires(_OutputIteratorConcept<_OutputIter, 01384 typename iterator_traits<_BidirectionalIter>::value_type>) 01385 01386 while (__first != __last) { 01387 --__last; 01388 *__result = *__last; 01389 ++__result; 01390 } 01391 return __result; 01392 } 01393 01394 01395 /** 01396 * @if maint 01397 * This is a helper function for the rotate algorithm specialized on RAIs. 01398 * It returns the greatest common divisor of two integer values. 01399 * @endif 01400 */ 01401 template<typename _EuclideanRingElement> 01402 _EuclideanRingElement 01403 __gcd(_EuclideanRingElement __m, _EuclideanRingElement __n) 01404 { 01405 while (__n != 0) { 01406 _EuclideanRingElement __t = __m % __n; 01407 __m = __n; 01408 __n = __t; 01409 } 01410 return __m; 01411 } 01412 01413 /** 01414 * @if maint 01415 * This is a helper function for the rotate algorithm. 01416 * @endif 01417 */ 01418 template<typename _ForwardIter> 01419 void 01420 __rotate(_ForwardIter __first, 01421 _ForwardIter __middle, 01422 _ForwardIter __last, 01423 forward_iterator_tag) 01424 { 01425 if ((__first == __middle) || (__last == __middle)) 01426 return; 01427 01428 _ForwardIter __first2 = __middle; 01429 do { 01430 swap(*__first++, *__first2++); 01431 if (__first == __middle) 01432 __middle = __first2; 01433 } while (__first2 != __last); 01434 01435 __first2 = __middle; 01436 01437 while (__first2 != __last) { 01438 swap(*__first++, *__first2++); 01439 if (__first == __middle) 01440 __middle = __first2; 01441 else if (__first2 == __last) 01442 __first2 = __middle; 01443 } 01444 } 01445 01446 /** 01447 * @if maint 01448 * This is a helper function for the rotate algorithm. 01449 * @endif 01450 */ 01451 template<typename _BidirectionalIter> 01452 void 01453 __rotate(_BidirectionalIter __first, 01454 _BidirectionalIter __middle, 01455 _BidirectionalIter __last, 01456 bidirectional_iterator_tag) 01457 { 01458 // concept requirements 01459 __glibcpp_function_requires(_Mutable_BidirectionalIteratorConcept< 01460 _BidirectionalIter>) 01461 01462 if ((__first == __middle) || (__last == __middle)) 01463 return; 01464 01465 __reverse(__first, __middle, bidirectional_iterator_tag()); 01466 __reverse(__middle, __last, bidirectional_iterator_tag()); 01467 01468 while (__first != __middle && __middle != __last) 01469 swap (*__first++, *--__last); 01470 01471 if (__first == __middle) { 01472 __reverse(__middle, __last, bidirectional_iterator_tag()); 01473 } 01474 else { 01475 __reverse(__first, __middle, bidirectional_iterator_tag()); 01476 } 01477 } 01478 01479 /** 01480 * @if maint 01481 * This is a helper function for the rotate algorithm. 01482 * @endif 01483 */ 01484 template<typename _RandomAccessIter> 01485 void 01486 __rotate(_RandomAccessIter __first, 01487 _RandomAccessIter __middle, 01488 _RandomAccessIter __last, 01489 random_access_iterator_tag) 01490 { 01491 // concept requirements 01492 __glibcpp_function_requires(_Mutable_RandomAccessIteratorConcept< 01493 _RandomAccessIter>) 01494 01495 if ((__first == __middle) || (__last == __middle)) 01496 return; 01497 01498 typedef typename iterator_traits<_RandomAccessIter>::difference_type _Distance; 01499 typedef typename iterator_traits<_RandomAccessIter>::value_type _ValueType; 01500 01501 _Distance __n = __last - __first; 01502 _Distance __k = __middle - __first; 01503 _Distance __l = __n - __k; 01504 01505 if (__k == __l) { 01506 swap_ranges(__first, __middle, __middle); 01507 return; 01508 } 01509 01510 _Distance __d = __gcd(__n, __k); 01511 01512 for (_Distance __i = 0; __i < __d; __i++) { 01513 _ValueType __tmp = *__first; 01514 _RandomAccessIter __p = __first; 01515 01516 if (__k < __l) { 01517 for (_Distance __j = 0; __j < __l/__d; __j++) { 01518 if (__p > __first + __l) { 01519 *__p = *(__p - __l); 01520 __p -= __l; 01521 } 01522 01523 *__p = *(__p + __k); 01524 __p += __k; 01525 } 01526 } 01527 01528 else { 01529 for (_Distance __j = 0; __j < __k/__d - 1; __j ++) { 01530 if (__p < __last - __k) { 01531 *__p = *(__p + __k); 01532 __p += __k; 01533 } 01534 01535 *__p = * (__p - __l); 01536 __p -= __l; 01537 } 01538 } 01539 01540 *__p = __tmp; 01541 ++__first; 01542 } 01543 } 01544 01545 /** 01546 * @brief Rotate the elements of a sequence. 01547 * @param first A forward iterator. 01548 * @param middle A forward iterator. 01549 * @param last A forward iterator. 01550 * @return Nothing. 01551 * 01552 * Rotates the elements of the range @p [first,last) by @p (middle-first) 01553 * positions so that the element at @p middle is moved to @p first, the 01554 * element at @p middle+1 is moved to @first+1 and so on for each element 01555 * in the range @p [first,last). 01556 * 01557 * This effectively swaps the ranges @p [first,middle) and 01558 * @p [middle,last). 01559 * 01560 * Performs @p *(first+(n+(last-middle))%(last-first))=*(first+n) for 01561 * each @p n in the range @p [0,last-first). 01562 */ 01563 template<typename _ForwardIter> 01564 inline void 01565 rotate(_ForwardIter __first, _ForwardIter __middle, _ForwardIter __last) 01566 { 01567 // concept requirements 01568 __glibcpp_function_requires(_Mutable_ForwardIteratorConcept<_ForwardIter>) 01569 01570 typedef typename iterator_traits<_ForwardIter>::iterator_category _IterType; 01571 __rotate(__first, __middle, __last, _IterType()); 01572 } 01573 01574 /** 01575 * @brief Copy a sequence, rotating its elements. 01576 * @param first A forward iterator. 01577 * @param middle A forward iterator. 01578 * @param last A forward iterator. 01579 * @param result An output iterator. 01580 * @return An iterator designating the end of the resulting sequence. 01581 * 01582 * Copies the elements of the range @p [first,last) to the range 01583 * beginning at @result, rotating the copied elements by @p (middle-first) 01584 * positions so that the element at @p middle is moved to @p result, the 01585 * element at @p middle+1 is moved to @result+1 and so on for each element 01586 * in the range @p [first,last). 01587 * 01588 * Performs @p *(result+(n+(last-middle))%(last-first))=*(first+n) for 01589 * each @p n in the range @p [0,last-first). 01590 */ 01591 template<typename _ForwardIter, typename _OutputIter> 01592 _OutputIter 01593 rotate_copy(_ForwardIter __first, _ForwardIter __middle, 01594 _ForwardIter __last, _OutputIter __result) 01595 { 01596 // concept requirements 01597 __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter>) 01598 __glibcpp_function_requires(_OutputIteratorConcept<_OutputIter, 01599 typename iterator_traits<_ForwardIter>::value_type>) 01600 01601 return copy(__first, __middle, copy(__middle, __last, __result)); 01602 } 01603 01604 01605 /** 01606 * @if maint 01607 * Return a random number in the range [0, __n). This function encapsulates 01608 * whether we're using rand (part of the standard C library) or lrand48 01609 * (not standard, but a much better choice whenever it's available). 01610 * 01611 * XXX There is no corresponding encapsulation fn to seed the generator. 01612 * @endif 01613 */ 01614 template<typename _Distance> 01615 inline _Distance 01616 __random_number(_Distance __n) 01617 { 01618 #ifdef _GLIBCPP_HAVE_DRAND48 01619 return lrand48() % __n; 01620 #else 01621 return rand() % __n; 01622 #endif 01623 } 01624 01625 01626 /** 01627 * @brief Randomly shuffle the elements of a sequence. 01628 * @param first A forward iterator. 01629 * @param last A forward iterator. 01630 * @return Nothing. 01631 * 01632 * Reorder the elements in the range @p [first,last) using a random 01633 * distribution, so that every possible ordering of the sequence is 01634 * equally likely. 01635 */ 01636 template<typename _RandomAccessIter> 01637 inline void 01638 random_shuffle(_RandomAccessIter __first, _RandomAccessIter __last) 01639 { 01640 // concept requirements 01641 __glibcpp_function_requires(_Mutable_RandomAccessIteratorConcept< 01642 _RandomAccessIter>) 01643 01644 if (__first == __last) return; 01645 for (_RandomAccessIter __i = __first + 1; __i != __last; ++__i) 01646 iter_swap(__i, __first + __random_number((__i - __first) + 1)); 01647 } 01648 01649 /** 01650 * @brief Shuffle the elements of a sequence using a random number 01651 * generator. 01652 * @param first A forward iterator. 01653 * @param last A forward iterator. 01654 * @param rand The RNG functor or function. 01655 * @return Nothing. 01656 * 01657 * Reorders the elements in the range @p [first,last) using @p rand to 01658 * provide a random distribution. Calling @p rand(N) for a positive 01659 * integer @p N should return a randomly chosen integer from the 01660 * range [0,N). 01661 */ 01662 template<typename _RandomAccessIter, typename _RandomNumberGenerator> 01663 void 01664 random_shuffle(_RandomAccessIter __first, _RandomAccessIter __last, 01665 _RandomNumberGenerator& __rand) 01666 { 01667 // concept requirements 01668 __glibcpp_function_requires(_Mutable_RandomAccessIteratorConcept< 01669 _RandomAccessIter>) 01670 01671 if (__first == __last) return; 01672 for (_RandomAccessIter __i = __first + 1; __i != __last; ++__i) 01673 iter_swap(__i, __first + __rand((__i - __first) + 1)); 01674 } 01675 01676 01677 /** 01678 * @if maint 01679 * This is a helper function... 01680 * @endif 01681 */ 01682 template<typename _ForwardIter, typename _Predicate> 01683 _ForwardIter 01684 __partition(_ForwardIter __first, _ForwardIter __last, 01685 _Predicate __pred, 01686 forward_iterator_tag) 01687 { 01688 if (__first == __last) return __first; 01689 01690 while (__pred(*__first)) 01691 if (++__first == __last) return __first; 01692 01693 _ForwardIter __next = __first; 01694 01695 while (++__next != __last) 01696 if (__pred(*__next)) { 01697 swap(*__first, *__next); 01698 ++__first; 01699 } 01700 01701 return __first; 01702 } 01703 01704 /** 01705 * @if maint 01706 * This is a helper function... 01707 * @endif 01708 */ 01709 template<typename _BidirectionalIter, typename _Predicate> 01710 _BidirectionalIter 01711 __partition(_BidirectionalIter __first, _BidirectionalIter __last, 01712 _Predicate __pred, 01713 bidirectional_iterator_tag) 01714 { 01715 while (true) { 01716 while (true) 01717 if (__first == __last) 01718 return __first; 01719 else if (__pred(*__first)) 01720 ++__first; 01721 else 01722 break; 01723 --__last; 01724 while (true) 01725 if (__first == __last) 01726 return __first; 01727 else if (!__pred(*__last)) 01728 --__last; 01729 else 01730 break; 01731 iter_swap(__first, __last); 01732 ++__first; 01733 } 01734 } 01735 01736 /** 01737 * @brief Move elements for which a predicate is true to the beginning 01738 * of a sequence. 01739 * @param first A forward iterator. 01740 * @param last A forward iterator. 01741 * @param pred A predicate functor. 01742 * @return An iterator @p middle such that @p pred(i) is true for each 01743 * iterator @p i in the range @p [first,middle) and false for each @p i 01744 * in the range @p [middle,last). 01745 * 01746 * @p pred must not modify its operand. @p partition() does not preserve 01747 * the relative ordering of elements in each group, use 01748 * @p stable_partition() if this is needed. 01749 */ 01750 template<typename _ForwardIter, typename _Predicate> 01751 inline _ForwardIter 01752 partition(_ForwardIter __first, _ForwardIter __last, 01753 _Predicate __pred) 01754 { 01755 // concept requirements 01756 __glibcpp_function_requires(_Mutable_ForwardIteratorConcept<_ForwardIter>) 01757 __glibcpp_function_requires(_UnaryPredicateConcept<_Predicate, 01758 typename iterator_traits<_ForwardIter>::value_type>) 01759 01760 return __partition(__first, __last, __pred, __iterator_category(__first)); 01761 } 01762 01763 01764 /** 01765 * @if maint 01766 * This is a helper function... 01767 * @endif 01768 */ 01769 template<typename _ForwardIter, typename _Predicate, typename _Distance> 01770 _ForwardIter 01771 __inplace_stable_partition(_ForwardIter __first, _ForwardIter __last, 01772 _Predicate __pred, _Distance __len) 01773 { 01774 if (__len == 1) 01775 return __pred(*__first) ? __last : __first; 01776 _ForwardIter __middle = __first; 01777 advance(__middle, __len / 2); 01778 _ForwardIter __begin = __inplace_stable_partition(__first, __middle, 01779 __pred, 01780 __len / 2); 01781 _ForwardIter __end = __inplace_stable_partition(__middle, __last, 01782 __pred, 01783 __len - __len / 2); 01784 rotate(__begin, __middle, __end); 01785 advance(__begin, distance(__middle, __end)); 01786 return __begin; 01787 } 01788 01789 /** 01790 * @if maint 01791 * This is a helper function... 01792 * @endif 01793 */ 01794 template<typename _ForwardIter, typename _Pointer, typename _Predicate, 01795 typename _Distance> 01796 _ForwardIter 01797 __stable_partition_adaptive(_ForwardIter __first, _ForwardIter __last, 01798 _Predicate __pred, _Distance __len, 01799 _Pointer __buffer, 01800 _Distance __buffer_size) 01801 { 01802 if (__len <= __buffer_size) { 01803 _ForwardIter __result1 = __first; 01804 _Pointer __result2 = __buffer; 01805 for ( ; __first != __last ; ++__first) 01806 if (__pred(*__first)) { 01807 *__result1 = *__first; 01808 ++__result1; 01809 } 01810 else { 01811 *__result2 = *__first; 01812 ++__result2; 01813 } 01814 copy(__buffer, __result2, __result1); 01815 return __result1; 01816 } 01817 else { 01818 _ForwardIter __middle = __first; 01819 advance(__middle, __len / 2); 01820 _ForwardIter __begin = __stable_partition_adaptive(__first, __middle, 01821 __pred, 01822 __len / 2, 01823 __buffer, __buffer_size); 01824 _ForwardIter __end = __stable_partition_adaptive( __middle, __last, 01825 __pred, 01826 __len - __len / 2, 01827 __buffer, __buffer_size); 01828 rotate(__begin, __middle, __end); 01829 advance(__begin, distance(__middle, __end)); 01830 return __begin; 01831 } 01832 } 01833 01834 /** 01835 * @brief Move elements for which a predicate is true to the beginning 01836 * of a sequence, preserving relative ordering. 01837 * @param first A forward iterator. 01838 * @param last A forward iterator. 01839 * @param pred A predicate functor. 01840 * @return An iterator @p middle such that @p pred(i) is true for each 01841 * iterator @p i in the range @p [first,middle) and false for each @p i 01842 * in the range @p [middle,last). 01843 * 01844 * Performs the same function as @p partition() with the additional 01845 * guarantee that the relative ordering of elements in each group is 01846 * preserved, so any two elements @p x and @p y in the range 01847 * @p [first,last) such that @p pred(x)==pred(y) will have the same 01848 * relative ordering after calling @p stable_partition(). 01849 */ 01850 template<typename _ForwardIter, typename _Predicate> 01851 _ForwardIter 01852 stable_partition(_ForwardIter __first, _ForwardIter __last, 01853 _Predicate __pred) 01854 { 01855 // concept requirements 01856 __glibcpp_function_requires(_Mutable_ForwardIteratorConcept<_ForwardIter>) 01857 __glibcpp_function_requires(_UnaryPredicateConcept<_Predicate, 01858 typename iterator_traits<_ForwardIter>::value_type>) 01859 01860 if (__first == __last) 01861 return __first; 01862 else 01863 { 01864 typedef typename iterator_traits<_ForwardIter>::value_type _ValueType; 01865 typedef typename iterator_traits<_ForwardIter>::difference_type _DistanceType; 01866 01867 _Temporary_buffer<_ForwardIter, _ValueType> __buf(__first, __last); 01868 if (__buf.size() > 0) 01869 return __stable_partition_adaptive(__first, __last, __pred, 01870 _DistanceType(__buf.requested_size()), 01871 __buf.begin(), __buf.size()); 01872 else 01873 return __inplace_stable_partition(__first, __last, __pred, 01874 _DistanceType(__buf.requested_size())); 01875 } 01876 } 01877 01878 /** 01879 * @if maint 01880 * This is a helper function... 01881 * @endif 01882 */ 01883 template<typename _RandomAccessIter, typename _Tp> 01884 _RandomAccessIter 01885 __unguarded_partition(_RandomAccessIter __first, _RandomAccessIter __last, 01886 _Tp __pivot) 01887 { 01888 while (true) { 01889 while (*__first < __pivot) 01890 ++__first; 01891 --__last; 01892 while (__pivot < *__last) 01893 --__last; 01894 if (!(__first < __last)) 01895 return __first; 01896 iter_swap(__first, __last); 01897 ++__first; 01898 } 01899 } 01900 01901 /** 01902 * @if maint 01903 * This is a helper function... 01904 * @endif 01905 */ 01906 template<typename _RandomAccessIter, typename _Tp, typename _Compare> 01907 _RandomAccessIter 01908 __unguarded_partition(_RandomAccessIter __first, _RandomAccessIter __last, 01909 _Tp __pivot, _Compare __comp) 01910 { 01911 while (true) { 01912 while (__comp(*__first, __pivot)) 01913 ++__first; 01914 --__last; 01915 while (__comp(__pivot, *__last)) 01916 --__last; 01917 if (!(__first < __last)) 01918 return __first; 01919 iter_swap(__first, __last); 01920 ++__first; 01921 } 01922 } 01923 01924 01925 /** 01926 * @if maint 01927 * @doctodo 01928 * This controls some aspect of the sort routines. 01929 * @endif 01930 */ 01931 enum { _M_threshold = 16 }; 01932 01933 /** 01934 * @if maint 01935 * This is a helper function for the sort routine. 01936 * @endif 01937 */ 01938 template<typename _RandomAccessIter, typename _Tp> 01939 void 01940 __unguarded_linear_insert(_RandomAccessIter __last, _Tp __val) 01941 { 01942 _RandomAccessIter __next = __last; 01943 --__next; 01944 while (__val < *__next) { 01945 *__last = *__next; 01946 __last = __next; 01947 --__next; 01948 } 01949 *__last = __val; 01950 } 01951 01952 /** 01953 * @if maint 01954 * This is a helper function for the sort routine. 01955 * @endif 01956 */ 01957 template<typename _RandomAccessIter, typename _Tp, typename _Compare> 01958 void 01959 __unguarded_linear_insert(_RandomAccessIter __last, _Tp __val, _Compare __comp) 01960 { 01961 _RandomAccessIter __next = __last; 01962 --__next; 01963 while (__comp(__val, *__next)) { 01964 *__last = *__next; 01965 __last = __next; 01966 --__next; 01967 } 01968 *__last = __val; 01969 } 01970 01971 /** 01972 * @if maint 01973 * This is a helper function for the sort routine. 01974 * @endif 01975 */ 01976 template<typename _RandomAccessIter> 01977 void 01978 __insertion_sort(_RandomAccessIter __first, _RandomAccessIter __last) 01979 { 01980 if (__first == __last) return; 01981 01982 for (_RandomAccessIter __i = __first + 1; __i != __last; ++__i) 01983 { 01984 typename iterator_traits<_RandomAccessIter>::value_type __val = *__i; 01985 if (__val < *__first) { 01986 copy_backward(__first, __i, __i + 1); 01987 *__first = __val; 01988 } 01989 else 01990 __unguarded_linear_insert(__i, __val); 01991 } 01992 } 01993 01994 /** 01995 * @if maint 01996 * This is a helper function for the sort routine. 01997 * @endif 01998 */ 01999 template<typename _RandomAccessIter, typename _Compare> 02000 void 02001 __insertion_sort(_RandomAccessIter __first, _RandomAccessIter __last, 02002 _Compare __comp) 02003 { 02004 if (__first == __last) return; 02005 02006 for (_RandomAccessIter __i = __first + 1; __i != __last; ++__i) 02007 { 02008 typename iterator_traits<_RandomAccessIter>::value_type __val = *__i; 02009 if (__comp(__val, *__first)) { 02010 copy_backward(__first, __i, __i + 1); 02011 *__first = __val; 02012 } 02013 else 02014 __unguarded_linear_insert(__i, __val, __comp); 02015 } 02016 } 02017 02018 /** 02019 * @if maint 02020 * This is a helper function for the sort routine. 02021 * @endif 02022 */ 02023 template<typename _RandomAccessIter> 02024 inline void 02025 __unguarded_insertion_sort(_RandomAccessIter __first, _RandomAccessIter __last) 02026 { 02027 typedef typename iterator_traits<_RandomAccessIter>::value_type _ValueType; 02028 02029 for (_RandomAccessIter __i = __first; __i != __last; ++__i) 02030 __unguarded_linear_insert(__i, _ValueType(*__i)); 02031 } 02032 02033 /** 02034 * @if maint 02035 * This is a helper function for the sort routine. 02036 * @endif 02037 */ 02038 template<typename _RandomAccessIter, typename _Compare> 02039 inline void 02040 __unguarded_insertion_sort(_RandomAccessIter __first, _RandomAccessIter __last, 02041 _Compare __comp) 02042 { 02043 typedef typename iterator_traits<_RandomAccessIter>::value_type _ValueType; 02044 02045 for (_RandomAccessIter __i = __first; __i != __last; ++__i) 02046 __unguarded_linear_insert(__i, _ValueType(*__i), __comp); 02047 } 02048 02049 /** 02050 * @if maint 02051 * This is a helper function for the sort routine. 02052 * @endif 02053 */ 02054 template<typename _RandomAccessIter> 02055 void 02056 __final_insertion_sort(_RandomAccessIter __first, _RandomAccessIter __last) 02057 { 02058 if (__last - __first > _M_threshold) { 02059 __insertion_sort(__first, __first + _M_threshold); 02060 __unguarded_insertion_sort(__first + _M_threshold, __last); 02061 } 02062 else 02063 __insertion_sort(__first, __last); 02064 } 02065 02066 /** 02067 * @if maint 02068 * This is a helper function for the sort routine. 02069 * @endif 02070 */ 02071 template<typename _RandomAccessIter, typename _Compare> 02072 void 02073 __final_insertion_sort(_RandomAccessIter __first, _RandomAccessIter __last, 02074 _Compare __comp) 02075 { 02076 if (__last - __first > _M_threshold) { 02077 __insertion_sort(__first, __first + _M_threshold, __comp); 02078 __unguarded_insertion_sort(__first + _M_threshold, __last, __comp); 02079 } 02080 else 02081 __insertion_sort(__first, __last, __comp); 02082 } 02083 02084 /** 02085 * @if maint 02086 * This is a helper function for the sort routine. 02087 * @endif 02088 */ 02089 template<typename _Size> 02090 inline _Size 02091 __lg(_Size __n) 02092 { 02093 _Size __k; 02094 for (__k = 0; __n != 1; __n >>= 1) ++__k; 02095 return __k; 02096 } 02097 02098 /** 02099 * @if maint 02100 * This is a helper function for the sort routine. 02101 * @endif 02102 */ 02103 template<typename _RandomAccessIter, typename _Size> 02104 void 02105 __introsort_loop(_RandomAccessIter __first, _RandomAccessIter __last, 02106 _Size __depth_limit) 02107 { 02108 typedef typename iterator_traits<_RandomAccessIter>::value_type _ValueType; 02109 02110 while (__last - __first > _M_threshold) { 02111 if (__depth_limit == 0) { 02112 partial_sort(__first, __last, __last); 02113 return; 02114 } 02115 --__depth_limit; 02116 _RandomAccessIter __cut = 02117 __unguarded_partition(__first, __last, 02118 _ValueType(__median(*__first, 02119 *(__first + (__last - __first)/2), 02120 *(__last - 1)))); 02121 __introsort_loop(__cut, __last, __depth_limit); 02122 __last = __cut; 02123 } 02124 } 02125 02126 /** 02127 * @if maint 02128 * This is a helper function for the sort routine. 02129 * @endif 02130 */ 02131 template<typename _RandomAccessIter, typename _Size, typename _Compare> 02132 void 02133 __introsort_loop(_RandomAccessIter __first, _RandomAccessIter __last, 02134 _Size __depth_limit, _Compare __comp) 02135 { 02136 typedef typename iterator_traits<_RandomAccessIter>::value_type _ValueType; 02137 02138 while (__last - __first > _M_threshold) { 02139 if (__depth_limit == 0) { 02140 partial_sort(__first, __last, __last, __comp); 02141 return; 02142 } 02143 --__depth_limit; 02144 _RandomAccessIter __cut = 02145 __unguarded_partition(__first, __last, 02146 _ValueType(__median(*__first, 02147 *(__first + (__last - __first)/2), 02148 *(__last - 1), __comp)), 02149 __comp); 02150 __introsort_loop(__cut, __last, __depth_limit, __comp); 02151 __last = __cut; 02152 } 02153 } 02154 02155 /** 02156 * @brief Sort the elements of a sequence. 02157 * @param first An iterator. 02158 * @param last Another iterator. 02159 * @return Nothing. 02160 * 02161 * Sorts the elements in the range @p [first,last) in ascending order, 02162 * such that @p *(i+1)<*i is false for each iterator @p i in the range 02163 * @p [first,last-1). 02164 * 02165 * The relative ordering of equivalent elements is not preserved, use 02166 * @p stable_sort() if this is needed. 02167 */ 02168 template<typename _RandomAccessIter> 02169 inline void 02170 sort(_RandomAccessIter __first, _RandomAccessIter __last) 02171 { 02172 typedef typename iterator_traits<_RandomAccessIter>::value_type _ValueType; 02173 02174 // concept requirements 02175 __glibcpp_function_requires(_Mutable_RandomAccessIteratorConcept< 02176 _RandomAccessIter>) 02177 __glibcpp_function_requires(_LessThanComparableConcept<_ValueType>) 02178 02179 if (__first != __last) { 02180 __introsort_loop(__first, __last, __lg(__last - __first) * 2); 02181 __final_insertion_sort(__first, __last); 02182 } 02183 } 02184 02185 /** 02186 * @brief Sort the elements of a sequence using a predicate for comparison. 02187 * @param first An iterator. 02188 * @param last Another iterator. 02189 * @param comp A comparison functor. 02190 * @return Nothing. 02191 * 02192 * Sorts the elements in the range @p [first,last) in ascending order, 02193 * such that @p comp(*(i+1),*i) is false for every iterator @p i in the 02194 * range @p [first,last-1). 02195 * 02196 * The relative ordering of equivalent elements is not preserved, use 02197 * @p stable_sort() if this is needed. 02198 */ 02199 template<typename _RandomAccessIter, typename _Compare> 02200 inline void 02201 sort(_RandomAccessIter __first, _RandomAccessIter __last, _Compare __comp) 02202 { 02203 typedef typename iterator_traits<_RandomAccessIter>::value_type _ValueType; 02204 02205 // concept requirements 02206 __glibcpp_function_requires(_Mutable_RandomAccessIteratorConcept< 02207 _RandomAccessIter>) 02208 __glibcpp_function_requires(_BinaryPredicateConcept<_Compare, _ValueType, _ValueType>) 02209 02210 if (__first != __last) { 02211 __introsort_loop(__first, __last, __lg(__last - __first) * 2, __comp); 02212 __final_insertion_sort(__first, __last, __comp); 02213 } 02214 } 02215 02216 02217 /** 02218 * @if maint 02219 * This is a helper function for the stable sorting routines. 02220 * @endif 02221 */ 02222 template<typename _RandomAccessIter> 02223 void 02224 __inplace_stable_sort(_RandomAccessIter __first, _RandomAccessIter __last) 02225 { 02226 if (__last - __first < 15) { 02227 __insertion_sort(__first, __last); 02228 return; 02229 } 02230 _RandomAccessIter __middle = __first + (__last - __first) / 2; 02231 __inplace_stable_sort(__first, __middle); 02232 __inplace_stable_sort(__middle, __last); 02233 __merge_without_buffer(__first, __middle, __last, 02234 __middle - __first, 02235 __last - __middle); 02236 } 02237 02238 /** 02239 * @if maint 02240 * This is a helper function for the stable sorting routines. 02241 * @endif 02242 */ 02243 template<typename _RandomAccessIter, typename _Compare> 02244 void 02245 __inplace_stable_sort(_RandomAccessIter __first, _RandomAccessIter __last, 02246 _Compare __comp) 02247 { 02248 if (__last - __first < 15) { 02249 __insertion_sort(__first, __last, __comp); 02250 return; 02251 } 02252 _RandomAccessIter __middle = __first + (__last - __first) / 2; 02253 __inplace_stable_sort(__first, __middle, __comp); 02254 __inplace_stable_sort(__middle, __last, __comp); 02255 __merge_without_buffer(__first, __middle, __last, 02256 __middle - __first, 02257 __last - __middle, 02258 __comp); 02259 } 02260 02261 template<typename _RandomAccessIter1, typename _RandomAccessIter2, 02262 typename _Distance> 02263 void 02264 __merge_sort_loop(_RandomAccessIter1 __first, _RandomAccessIter1 __last, 02265 _RandomAccessIter2 __result, _Distance __step_size) 02266 { 02267 _Distance __two_step = 2 * __step_size; 02268 02269 while (__last - __first >= __two_step) { 02270 __result = merge(__first, __first + __step_size, 02271 __first + __step_size, __first + __two_step, 02272 __result); 02273 __first += __two_step; 02274 } 02275 02276 __step_size = min(_Distance(__last - __first), __step_size); 02277 merge(__first, __first + __step_size, __first + __step_size, __last, 02278 __result); 02279 } 02280 02281 template<typename _RandomAccessIter1, typename _RandomAccessIter2, 02282 typename _Distance, typename _Compare> 02283 void 02284 __merge_sort_loop(_RandomAccessIter1 __first, _RandomAccessIter1 __last, 02285 _RandomAccessIter2 __result, _Distance __step_size, 02286 _Compare __comp) 02287 { 02288 _Distance __two_step = 2 * __step_size; 02289 02290 while (__last - __first >= __two_step) { 02291 __result = merge(__first, __first + __step_size, 02292 __first + __step_size, __first + __two_step, 02293 __result, 02294 __comp); 02295 __first += __two_step; 02296 } 02297 __step_size = min(_Distance(__last - __first), __step_size); 02298 02299 merge(__first, __first + __step_size, 02300 __first + __step_size, __last, 02301 __result, 02302 __comp); 02303 } 02304 02305 enum { _M_chunk_size = 7 }; 02306 02307 template<typename _RandomAccessIter, typename _Distance> 02308 void 02309 __chunk_insertion_sort(_RandomAccessIter __first, _RandomAccessIter __last, 02310 _Distance __chunk_size) 02311 { 02312 while (__last - __first >= __chunk_size) { 02313 __insertion_sort(__first, __first + __chunk_size); 02314 __first += __chunk_size; 02315 } 02316 __insertion_sort(__first, __last); 02317 } 02318 02319 template<typename _RandomAccessIter, typename _Distance, typename _Compare> 02320 void 02321 __chunk_insertion_sort(_RandomAccessIter __first, _RandomAccessIter __last, 02322 _Distance __chunk_size, _Compare __comp) 02323 { 02324 while (__last - __first >= __chunk_size) { 02325 __insertion_sort(__first, __first + __chunk_size, __comp); 02326 __first += __chunk_size; 02327 } 02328 __insertion_sort(__first, __last, __comp); 02329 } 02330 02331 template<typename _RandomAccessIter, typename _Pointer> 02332 void 02333 __merge_sort_with_buffer(_RandomAccessIter __first, _RandomAccessIter __last, 02334 _Pointer __buffer) 02335 { 02336 typedef typename iterator_traits<_RandomAccessIter>::difference_type _Distance; 02337 02338 _Distance __len = __last - __first; 02339 _Pointer __buffer_last = __buffer + __len; 02340 02341 _Distance __step_size = _M_chunk_size; 02342 __chunk_insertion_sort(__first, __last, __step_size); 02343 02344 while (__step_size < __len) { 02345 __merge_sort_loop(__first, __last, __buffer, __step_size); 02346 __step_size *= 2; 02347 __merge_sort_loop(__buffer, __buffer_last, __first, __step_size); 02348 __step_size *= 2; 02349 } 02350 } 02351 02352 template<typename _RandomAccessIter, typename _Pointer, typename _Compare> 02353 void 02354 __merge_sort_with_buffer(_RandomAccessIter __first, _RandomAccessIter __last, 02355 _Pointer __buffer, _Compare __comp) 02356 { 02357 typedef typename iterator_traits<_RandomAccessIter>::difference_type _Distance; 02358 02359 _Distance __len = __last - __first; 02360 _Pointer __buffer_last = __buffer + __len; 02361 02362 _Distance __step_size = _M_chunk_size; 02363 __chunk_insertion_sort(__first, __last, __step_size, __comp); 02364 02365 while (__step_size < __len) { 02366 __merge_sort_loop(__first, __last, __buffer, __step_size, __comp); 02367 __step_size *= 2; 02368 __merge_sort_loop(__buffer, __buffer_last, __first, __step_size, __comp); 02369 __step_size *= 2; 02370 } 02371 } 02372 02373 template<typename _RandomAccessIter, typename _Pointer, typename _Distance> 02374 void 02375 __stable_sort_adaptive(_RandomAccessIter __first, _RandomAccessIter __last, 02376 _Pointer __buffer, _Distance __buffer_size) 02377 { 02378 _Distance __len = (__last - __first + 1) / 2; 02379 _RandomAccessIter __middle = __first + __len; 02380 if (__len > __buffer_size) { 02381 __stable_sort_adaptive(__first, __middle, __buffer, __buffer_size); 02382 __stable_sort_adaptive(__middle, __last, __buffer, __buffer_size); 02383 } 02384 else { 02385 __merge_sort_with_buffer(__first, __middle, __buffer); 02386 __merge_sort_with_buffer(__middle, __last, __buffer); 02387 } 02388 __merge_adaptive(__first, __middle, __last, _Distance(__middle - __first), 02389 _Distance(__last - __middle), __buffer, __buffer_size); 02390 } 02391 02392 template<typename _RandomAccessIter, typename _Pointer, typename _Distance, 02393 typename _Compare> 02394 void 02395 __stable_sort_adaptive(_RandomAccessIter __first, _RandomAccessIter __last, 02396 _Pointer __buffer, _Distance __buffer_size, 02397 _Compare __comp) 02398 { 02399 _Distance __len = (__last - __first + 1) / 2; 02400 _RandomAccessIter __middle = __first + __len; 02401 if (__len > __buffer_size) { 02402 __stable_sort_adaptive(__first, __middle, __buffer, __buffer_size, 02403 __comp); 02404 __stable_sort_adaptive(__middle, __last, __buffer, __buffer_size, 02405 __comp); 02406 } 02407 else { 02408 __merge_sort_with_buffer(__first, __middle, __buffer, __comp); 02409 __merge_sort_with_buffer(__middle, __last, __buffer, __comp); 02410 } 02411 __merge_adaptive(__first, __middle, __last, _Distance(__middle - __first), 02412 _Distance(__last - __middle), __buffer, __buffer_size, 02413 __comp); 02414 } 02415 02416 /** 02417 * @brief Sort the elements of a sequence, preserving the relative order 02418 * of equivalent elements. 02419 * @param first An iterator. 02420 * @param last Another iterator. 02421 * @return Nothing. 02422 * 02423 * Sorts the elements in the range @p [first,last) in ascending order, 02424 * such that @p *(i+1)<*i is false for each iterator @p i in the range 02425 * @p [first,last-1). 02426 * 02427 * The relative ordering of equivalent elements is preserved, so any two 02428 * elements @p x and @p y in the range @p [first,last) such that 02429 * @p x<y is false and @p y<x is false will have the same relative 02430 * ordering after calling @p stable_sort(). 02431 */ 02432 template<typename _RandomAccessIter> 02433 inline void 02434 stable_sort(_RandomAccessIter __first, _RandomAccessIter __last) 02435 { 02436 typedef typename iterator_traits<_RandomAccessIter>::value_type _ValueType; 02437 typedef typename iterator_traits<_RandomAccessIter>::difference_type _DistanceType; 02438 02439 // concept requirements 02440 __glibcpp_function_requires(_Mutable_RandomAccessIteratorConcept< 02441 _RandomAccessIter>) 02442 __glibcpp_function_requires(_LessThanComparableConcept<_ValueType>) 02443 02444 _Temporary_buffer<_RandomAccessIter, _ValueType> buf(__first, __last); 02445 if (buf.begin() == 0) 02446 __inplace_stable_sort(__first, __last); 02447 else 02448 __stable_sort_adaptive(__first, __last, buf.begin(), _DistanceType(buf.size())); 02449 } 02450 02451 /** 02452 * @brief Sort the elements of a sequence using a predicate for comparison, 02453 * preserving the relative order of equivalent elements. 02454 * @param first An iterator. 02455 * @param last Another iterator. 02456 * @param comp A comparison functor. 02457 * @return Nothing. 02458 * 02459 * Sorts the elements in the range @p [first,last) in ascending order, 02460 * such that @p comp(*(i+1),*i) is false for each iterator @p i in the 02461 * range @p [first,last-1). 02462 * 02463 * The relative ordering of equivalent elements is preserved, so any two 02464 * elements @p x and @p y in the range @p [first,last) such that 02465 * @p comp(x,y) is false and @p comp(y,x) is false will have the same 02466 * relative ordering after calling @p stable_sort(). 02467 */ 02468 template<typename _RandomAccessIter, typename _Compare> 02469 inline void 02470 stable_sort(_RandomAccessIter __first, _RandomAccessIter __last, _Compare __comp) 02471 { 02472 typedef typename iterator_traits<_RandomAccessIter>::value_type _ValueType; 02473 typedef typename iterator_traits<_RandomAccessIter>::difference_type _DistanceType; 02474 02475 // concept requirements 02476 __glibcpp_function_requires(_Mutable_RandomAccessIteratorConcept< 02477 _RandomAccessIter>) 02478 __glibcpp_function_requires(_BinaryPredicateConcept<_Compare, 02479 _ValueType, _ValueType>) 02480 02481 _Temporary_buffer<_RandomAccessIter, _ValueType> buf(__first, __last); 02482 if (buf.begin() == 0) 02483 __inplace_stable_sort(__first, __last, __comp); 02484 else 02485 __stable_sort_adaptive(__first, __last, buf.begin(), _DistanceType(buf.size()), 02486 __comp); 02487 } 02488 02489 /** 02490 * @brief Sort the smallest elements of a sequence. 02491 * @param first An iterator. 02492 * @param middle Another iterator. 02493 * @param last Another iterator. 02494 * @return Nothing. 02495 * 02496 * Sorts the smallest @p (middle-first) elements in the range 02497 * @p [first,last) and moves them to the range @p [first,middle). The 02498 * order of the remaining elements in the range @p [middle,last) is 02499 * undefined. 02500 * After the sort if @p i and @j are iterators in the range 02501 * @p [first,middle) such that @i precedes @j and @k is an iterator in 02502 * the range @p [middle,last) then @p *j<*i and @p *k<*i are both false. 02503 */ 02504 template<typename _RandomAccessIter> 02505 void 02506 partial_sort(_RandomAccessIter __first, 02507 _RandomAccessIter __middle, 02508 _RandomAccessIter __last) 02509 { 02510 typedef typename iterator_traits<_RandomAccessIter>::value_type _ValueType; 02511 02512 // concept requirements 02513 __glibcpp_function_requires(_Mutable_RandomAccessIteratorConcept< 02514 _RandomAccessIter>) 02515 __glibcpp_function_requires(_LessThanComparableConcept<_ValueType>) 02516 02517 make_heap(__first, __middle); 02518 for (_RandomAccessIter __i = __middle; __i < __last; ++__i) 02519 if (*__i < *__first) 02520 __pop_heap(__first, __middle, __i, _ValueType(*__i)); 02521 sort_heap(__first, __middle); 02522 } 02523 02524 /** 02525 * @brief Sort the smallest elements of a sequence using a predicate 02526 * for comparison. 02527 * @param first An iterator. 02528 * @param middle Another iterator. 02529 * @param last Another iterator. 02530 * @param comp A comparison functor. 02531 * @return Nothing. 02532 * 02533 * Sorts the smallest @p (middle-first) elements in the range 02534 * @p [first,last) and moves them to the range @p [first,middle). The 02535 * order of the remaining elements in the range @p [middle,last) is 02536 * undefined. 02537 * After the sort if @p i and @j are iterators in the range 02538 * @p [first,middle) such that @i precedes @j and @k is an iterator in 02539 * the range @p [middle,last) then @p *comp(j,*i) and @p comp(*k,*i) 02540 * are both false. 02541 */ 02542 template<typename _RandomAccessIter, typename _Compare> 02543 void 02544 partial_sort(_RandomAccessIter __first, 02545 _RandomAccessIter __middle, 02546 _RandomAccessIter __last, 02547 _Compare __comp) 02548 { 02549 typedef typename iterator_traits<_RandomAccessIter>::value_type _ValueType; 02550 02551 // concept requirements 02552 __glibcpp_function_requires(_Mutable_RandomAccessIteratorConcept< 02553 _RandomAccessIter>) 02554 __glibcpp_function_requires(_BinaryPredicateConcept<_Compare, 02555 _ValueType, _ValueType>) 02556 02557 make_heap(__first, __middle, __comp); 02558 for (_RandomAccessIter __i = __middle; __i < __last; ++__i) 02559 if (__comp(*__i, *__first)) 02560 __pop_heap(__first, __middle, __i, _ValueType(*__i), __comp); 02561 sort_heap(__first, __middle, __comp); 02562 } 02563 02564 /** 02565 * @brief Copy the smallest elements of a sequence. 02566 * @param first An iterator. 02567 * @param last Another iterator. 02568 * @param result_first A random-access iterator. 02569 * @param result_last Another random-access iterator. 02570 * @return An iterator indicating the end of the resulting sequence. 02571 * 02572 * Copies and sorts the smallest N values from the range @p [first,last) 02573 * to the range beginning at @p result_first, where the number of 02574 * elements to be copied, @p N, is the smaller of @p (last-first) and 02575 * @p (result_last-result_first). 02576 * After the sort if @p i and @j are iterators in the range 02577 * @p [result_first,result_first+N) such that @i precedes @j then 02578 * @p *j<*i is false. 02579 * The value returned is @p result_first+N. 02580 */ 02581 template<typename _InputIter, typename _RandomAccessIter> 02582 _RandomAccessIter 02583 partial_sort_copy(_InputIter __first, _InputIter __last, 02584 _RandomAccessIter __result_first, 02585 _RandomAccessIter __result_last) 02586 { 02587 typedef typename iterator_traits<_InputIter>::value_type _InputValueType; 02588 typedef typename iterator_traits<_RandomAccessIter>::value_type _OutputValueType; 02589 typedef typename iterator_traits<_RandomAccessIter>::difference_type _DistanceType; 02590 02591 // concept requirements 02592 __glibcpp_function_requires(_InputIteratorConcept<_InputIter>) 02593 __glibcpp_function_requires(_ConvertibleConcept<_InputValueType, _OutputValueType>) 02594 __glibcpp_function_requires(_LessThanComparableConcept<_OutputValueType>) 02595 __glibcpp_function_requires(_LessThanComparableConcept<_InputValueType>) 02596 02597 if (__result_first == __result_last) return __result_last; 02598 _RandomAccessIter __result_real_last = __result_first; 02599 while(__first != __last && __result_real_last != __result_last) { 02600 *__result_real_last = *__first; 02601 ++__result_real_last; 02602 ++__first; 02603 } 02604 make_heap(__result_first, __result_real_last); 02605 while (__first != __last) { 02606 if (*__first < *__result_first) 02607 __adjust_heap(__result_first, _DistanceType(0), 02608 _DistanceType(__result_real_last - __result_first), 02609 _InputValueType(*__first)); 02610 ++__first; 02611 } 02612 sort_heap(__result_first, __result_real_last); 02613 return __result_real_last; 02614 } 02615 02616 /** 02617 * @brief Copy the smallest elements of a sequence using a predicate for 02618 * comparison. 02619 * @param first An input iterator. 02620 * @param last Another input iterator. 02621 * @param result_first A random-access iterator. 02622 * @param result_last Another random-access iterator. 02623 * @param comp A comparison functor. 02624 * @return An iterator indicating the end of the resulting sequence. 02625 * 02626 * Copies and sorts the smallest N values from the range @p [first,last) 02627 * to the range beginning at @p result_first, where the number of 02628 * elements to be copied, @p N, is the smaller of @p (last-first) and 02629 * @p (result_last-result_first). 02630 * After the sort if @p i and @j are iterators in the range 02631 * @p [result_first,result_first+N) such that @i precedes @j then 02632 * @p comp(*j,*i) is false. 02633 * The value returned is @p result_first+N. 02634 */ 02635 template<typename _InputIter, typename _RandomAccessIter, typename _Compare> 02636 _RandomAccessIter 02637 partial_sort_copy(_InputIter __first, _InputIter __last, 02638 _RandomAccessIter __result_first, 02639 _RandomAccessIter __result_last, 02640 _Compare __comp) 02641 { 02642 typedef typename iterator_traits<_InputIter>::value_type _InputValueType; 02643 typedef typename iterator_traits<_RandomAccessIter>::value_type _OutputValueType; 02644 typedef typename iterator_traits<_RandomAccessIter>::difference_type _DistanceType; 02645 02646 // concept requirements 02647 __glibcpp_function_requires(_InputIteratorConcept<_InputIter>) 02648 __glibcpp_function_requires(_Mutable_RandomAccessIteratorConcept<_RandomAccessIter>) 02649 __glibcpp_function_requires(_ConvertibleConcept<_InputValueType, _OutputValueType>) 02650 __glibcpp_function_requires(_BinaryPredicateConcept<_Compare, 02651 _OutputValueType, _OutputValueType>) 02652 02653 if (__result_first == __result_last) return __result_last; 02654 _RandomAccessIter __result_real_last = __result_first; 02655 while(__first != __last && __result_real_last != __result_last) { 02656 *__result_real_last = *__first; 02657 ++__result_real_last; 02658 ++__first; 02659 } 02660 make_heap(__result_first, __result_real_last, __comp); 02661 while (__first != __last) { 02662 if (__comp(*__first, *__result_first)) 02663 __adjust_heap(__result_first, _DistanceType(0), 02664 _DistanceType(__result_real_last - __result_first), 02665 _InputValueType(*__first), 02666 __comp); 02667 ++__first; 02668 } 02669 sort_heap(__result_first, __result_real_last, __comp); 02670 return __result_real_last; 02671 } 02672 02673 /** 02674 * @brief Sort a sequence just enough to find a particular position. 02675 * @param first An iterator. 02676 * @param nth Another iterator. 02677 * @param last Another iterator. 02678 * @return Nothing. 02679 * 02680 * Rearranges the elements in the range @p [first,last) so that @p *nth 02681 * is the same element that would have been in that position had the 02682 * whole sequence been sorted. 02683 * whole sequence been sorted. The elements either side of @p *nth are 02684 * not completely sorted, but for any iterator @i in the range 02685 * @p [first,nth) and any iterator @j in the range @p [nth,last) it 02686 * holds that @p *j<*i is false. 02687 */ 02688 template<typename _RandomAccessIter> 02689 void 02690 nth_element(_RandomAccessIter __first, 02691 _RandomAccessIter __nth, 02692 _RandomAccessIter __last) 02693 { 02694 typedef typename iterator_traits<_RandomAccessIter>::value_type _ValueType; 02695 02696 // concept requirements 02697 __glibcpp_function_requires(_Mutable_RandomAccessIteratorConcept<_RandomAccessIter>) 02698 __glibcpp_function_requires(_LessThanComparableConcept<_ValueType>) 02699 02700 while (__last - __first > 3) { 02701 _RandomAccessIter __cut = 02702 __unguarded_partition(__first, __last, 02703 _ValueType(__median(*__first, 02704 *(__first + (__last - __first)/2), 02705 *(__last - 1)))); 02706 if (__cut <= __nth) 02707 __first = __cut; 02708 else 02709 __last = __cut; 02710 } 02711 __insertion_sort(__first, __last); 02712 } 02713 02714 /** 02715 * @brief Sort a sequence just enough to find a particular position 02716 * using a predicate for comparison. 02717 * @param first An iterator. 02718 * @param nth Another iterator. 02719 * @param last Another iterator. 02720 * @param comp A comparison functor. 02721 * @return Nothing. 02722 * 02723 * Rearranges the elements in the range @p [first,last) so that @p *nth 02724 * is the same element that would have been in that position had the 02725 * whole sequence been sorted. The elements either side of @p *nth are 02726 * not completely sorted, but for any iterator @i in the range 02727 * @p [first,nth) and any iterator @j in the range @p [nth,last) it 02728 * holds that @p comp(*j,*i) is false. 02729 */ 02730 template<typename _RandomAccessIter, typename _Compare> 02731 void 02732 nth_element(_RandomAccessIter __first, 02733 _RandomAccessIter __nth, 02734 _RandomAccessIter __last, 02735 _Compare __comp) 02736 { 02737 typedef typename iterator_traits<_RandomAccessIter>::value_type _ValueType; 02738 02739 // concept requirements 02740 __glibcpp_function_requires(_Mutable_RandomAccessIteratorConcept<_RandomAccessIter>) 02741 __glibcpp_function_requires(_BinaryPredicateConcept<_Compare, 02742 _ValueType, _ValueType>) 02743 02744 while (__last - __first > 3) { 02745 _RandomAccessIter __cut = 02746 __unguarded_partition(__first, __last, 02747 _ValueType(__median(*__first, 02748 *(__first + (__last - __first)/2), 02749 *(__last - 1), 02750 __comp)), 02751 __comp); 02752 if (__cut <= __nth) 02753 __first = __cut; 02754 else 02755 __last = __cut; 02756 } 02757 __insertion_sort(__first, __last, __comp); 02758 } 02759 02760 02761 /** 02762 * @brief Finds the first position in which @a val could be inserted 02763 * without changing the ordering. 02764 * @param first An iterator. 02765 * @param last Another iterator. 02766 * @param val The search term. 02767 * @return An iterator pointing to the first element "not less than" @a val. 02768 * @ingroup binarysearch 02769 */ 02770 template<typename _ForwardIter, typename _Tp> 02771 _ForwardIter 02772 lower_bound(_ForwardIter __first, _ForwardIter __last, const _Tp& __val) 02773 { 02774 typedef typename iterator_traits<_ForwardIter>::value_type _ValueType; 02775 typedef typename iterator_traits<_ForwardIter>::difference_type _DistanceType; 02776 02777 // concept requirements 02778 // Note that these are slightly stricter than those of the 4-argument 02779 // version, defined next. The difference is in the strictness of the 02780 // comparison operations... so for looser checking, define your own 02781 // comparison function, as was intended. 02782 __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter>) 02783 __glibcpp_function_requires(_SameTypeConcept<_Tp, _ValueType>) 02784 __glibcpp_function_requires(_LessThanComparableConcept<_Tp>) 02785 02786 _DistanceType __len = distance(__first, __last); 02787 _DistanceType __half; 02788 _ForwardIter __middle; 02789 02790 while (__len > 0) { 02791 __half = __len >> 1; 02792 __middle = __first; 02793 advance(__middle, __half); 02794 if (*__middle < __val) { 02795 __first = __middle; 02796 ++__first; 02797 __len = __len - __half - 1; 02798 } 02799 else 02800 __len = __half; 02801 } 02802 return __first; 02803 } 02804 02805 /** 02806 * @brief Finds the first position in which @a val could be inserted 02807 * without changing the ordering. 02808 * @param first An iterator. 02809 * @param last Another iterator. 02810 * @param val The search term. 02811 * @param comp A functor to use for comparisons. 02812 * @return An iterator pointing to the first element "not less than" @a val. 02813 * @ingroup binarysearch 02814 * 02815 * The comparison function should have the same effects on ordering as 02816 * the function used for the initial sort. 02817 */ 02818 template<typename _ForwardIter, typename _Tp, typename _Compare> 02819 _ForwardIter 02820 lower_bound(_ForwardIter __first, _ForwardIter __last, 02821 const _Tp& __val, _Compare __comp) 02822 { 02823 typedef typename iterator_traits<_ForwardIter>::value_type _ValueType; 02824 typedef typename iterator_traits<_ForwardIter>::difference_type _DistanceType; 02825 02826 // concept requirements 02827 __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter>) 02828 __glibcpp_function_requires(_BinaryPredicateConcept<_Compare, _ValueType, _Tp>) 02829 02830 _DistanceType __len = distance(__first, __last); 02831 _DistanceType __half; 02832 _ForwardIter __middle; 02833 02834 while (__len > 0) { 02835 __half = __len >> 1; 02836 __middle = __first; 02837 advance(__middle, __half); 02838 if (__comp(*__middle, __val)) { 02839 __first = __middle; 02840 ++__first; 02841 __len = __len - __half - 1; 02842 } 02843 else 02844 __len = __half; 02845 } 02846 return __first; 02847 } 02848 02849 /** 02850 * @brief Finds the last position in which @a val could be inserted 02851 * without changing the ordering. 02852 * @param first An iterator. 02853 * @param last Another iterator. 02854 * @param val The search term. 02855 * @return An iterator pointing to the first element greater than @a val. 02856 * @ingroup binarysearch 02857 */ 02858 template<typename _ForwardIter, typename _Tp> 02859 _ForwardIter 02860 upper_bound(_ForwardIter __first, _ForwardIter __last, const _Tp& __val) 02861 { 02862 typedef typename iterator_traits<_ForwardIter>::value_type _ValueType; 02863 typedef typename iterator_traits<_ForwardIter>::difference_type _DistanceType; 02864 02865 // concept requirements 02866 // See comments on lower_bound. 02867 __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter>) 02868 __glibcpp_function_requires(_SameTypeConcept<_Tp, _ValueType>) 02869 __glibcpp_function_requires(_LessThanComparableConcept<_Tp>) 02870 02871 _DistanceType __len = distance(__first, __last); 02872 _DistanceType __half; 02873 _ForwardIter __middle; 02874 02875 while (__len > 0) { 02876 __half = __len >> 1; 02877 __middle = __first; 02878 advance(__middle, __half); 02879 if (__val < *__middle) 02880 __len = __half; 02881 else { 02882 __first = __middle; 02883 ++__first; 02884 __len = __len - __half - 1; 02885 } 02886 } 02887 return __first; 02888 } 02889 02890 /** 02891 * @brief Finds the last position in which @a val could be inserted 02892 * without changing the ordering. 02893 * @param first An iterator. 02894 * @param last Another iterator. 02895 * @param val The search term. 02896 * @param comp A functor to use for comparisons. 02897 * @return An iterator pointing to the first element greater than @a val. 02898 * @ingroup binarysearch 02899 * 02900 * The comparison function should have the same effects on ordering as 02901 * the function used for the initial sort. 02902 */ 02903 template<typename _ForwardIter, typename _Tp, typename _Compare> 02904 _ForwardIter 02905 upper_bound(_ForwardIter __first, _ForwardIter __last, 02906 const _Tp& __val, _Compare __comp) 02907 { 02908 typedef typename iterator_traits<_ForwardIter>::value_type _ValueType; 02909 typedef typename iterator_traits<_ForwardIter>::difference_type _DistanceType; 02910 02911 // concept requirements 02912 __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter>) 02913 __glibcpp_function_requires(_BinaryPredicateConcept<_Compare, _Tp, _ValueType>) 02914 02915 _DistanceType __len = distance(__first, __last); 02916 _DistanceType __half; 02917 _ForwardIter __middle; 02918 02919 while (__len > 0) { 02920 __half = __len >> 1; 02921 __middle = __first; 02922 advance(__middle, __half); 02923 if (__comp(__val, *__middle)) 02924 __len = __half; 02925 else { 02926 __first = __middle; 02927 ++__first; 02928 __len = __len - __half - 1; 02929 } 02930 } 02931 return __first; 02932 } 02933 02934 /** 02935 * @brief Finds the largest subrange in which @a val could be inserted 02936 * at any place in it without changing the ordering. 02937 * @param first An iterator. 02938 * @param last Another iterator. 02939 * @param val The search term. 02940 * @return An pair of iterators defining the subrange. 02941 * @ingroup binarysearch 02942 * 02943 * This is equivalent to 02944 * @code 02945 * std::make_pair(lower_bound(first, last, val), 02946 * upper_bound(first, last, val)) 02947 * @endcode 02948 * but does not actually call those functions. 02949 */ 02950 template<typename _ForwardIter, typename _Tp> 02951 pair<_ForwardIter, _ForwardIter> 02952 equal_range(_ForwardIter __first, _ForwardIter __last, const _Tp& __val) 02953 { 02954 typedef typename iterator_traits<_ForwardIter>::value_type _ValueType; 02955 typedef typename iterator_traits<_ForwardIter>::difference_type _DistanceType; 02956 02957 // concept requirements 02958 // See comments on lower_bound. 02959 __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter>) 02960 __glibcpp_function_requires(_SameTypeConcept<_Tp, _ValueType>) 02961 __glibcpp_function_requires(_LessThanComparableConcept<_Tp>) 02962 02963 _DistanceType __len = distance(__first, __last); 02964 _DistanceType __half; 02965 _ForwardIter __middle, __left, __right; 02966 02967 while (__len > 0) { 02968 __half = __len >> 1; 02969 __middle = __first; 02970 advance(__middle, __half); 02971 if (*__middle < __val) { 02972 __first = __middle; 02973 ++__first; 02974 __len = __len - __half - 1; 02975 } 02976 else if (__val < *__middle) 02977 __len = __half; 02978 else { 02979 __left = lower_bound(__first, __middle, __val); 02980 advance(__first, __len); 02981 __right = upper_bound(++__middle, __first, __val); 02982 return pair<_ForwardIter, _ForwardIter>(__left, __right); 02983 } 02984 } 02985 return pair<_ForwardIter, _ForwardIter>(__first, __first); 02986 } 02987 02988 /** 02989 * @brief Finds the largest subrange in which @a val could be inserted 02990 * at any place in it without changing the ordering. 02991 * @param first An iterator. 02992 * @param last Another iterator. 02993 * @param val The search term. 02994 * @param comp A functor to use for comparisons. 02995 * @return An pair of iterators defining the subrange. 02996 * @ingroup binarysearch 02997 * 02998 * This is equivalent to 02999 * @code 03000 * std::make_pair(lower_bound(first, last, val, comp), 03001 * upper_bound(first, last, val, comp)) 03002 * @endcode 03003 * but does not actually call those functions. 03004 */ 03005 template<typename _ForwardIter, typename _Tp, typename _Compare> 03006 pair<_ForwardIter, _ForwardIter> 03007 equal_range(_ForwardIter __first, _ForwardIter __last, const _Tp& __val, 03008 _Compare __comp) 03009 { 03010 typedef typename iterator_traits<_ForwardIter>::value_type _ValueType; 03011 typedef typename iterator_traits<_ForwardIter>::difference_type _DistanceType; 03012 03013 // concept requirements 03014 __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter>) 03015 __glibcpp_function_requires(_BinaryPredicateConcept<_Compare, _ValueType, _Tp>) 03016 __glibcpp_function_requires(_BinaryPredicateConcept<_Compare, _Tp, _ValueType>) 03017 03018 _DistanceType __len = distance(__first, __last); 03019 _DistanceType __half; 03020 _ForwardIter __middle, __left, __right; 03021 03022 while (__len > 0) { 03023 __half = __len >> 1; 03024 __middle = __first; 03025 advance(__middle, __half); 03026 if (__comp(*__middle, __val)) { 03027 __first = __middle; 03028 ++__first; 03029 __len = __len - __half - 1; 03030 } 03031 else if (__comp(__val, *__middle)) 03032 __len = __half; 03033 else { 03034 __left = lower_bound(__first, __middle, __val, __comp); 03035 advance(__first, __len); 03036 __right = upper_bound(++__middle, __first, __val, __comp); 03037 return pair<_ForwardIter, _ForwardIter>(__left, __right); 03038 } 03039 } 03040 return pair<_ForwardIter, _ForwardIter>(__first, __first); 03041 } 03042 03043 /** 03044 * @brief Determines whether an element exists in a range. 03045 * @param first An iterator. 03046 * @param last Another iterator. 03047 * @param val The search term. 03048 * @return True if @a val (or its equivelent) is in [@a first,@a last ]. 03049 * @ingroup binarysearch 03050 * 03051 * Note that this does not actually return an iterator to @a val. For 03052 * that, use std::find or a container's specialized find member functions. 03053 */ 03054 template<typename _ForwardIter, typename _Tp> 03055 bool 03056 binary_search(_ForwardIter __first, _ForwardIter __last, 03057 const _Tp& __val) 03058 { 03059 // concept requirements 03060 // See comments on lower_bound. 03061 __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter>) 03062 __glibcpp_function_requires(_SameTypeConcept<_Tp, 03063 typename iterator_traits<_ForwardIter>::value_type>) 03064 __glibcpp_function_requires(_LessThanComparableConcept<_Tp>) 03065 03066 _ForwardIter __i = lower_bound(__first, __last, __val); 03067 return __i != __last && !(__val < *__i); 03068 } 03069 03070 /** 03071 * @brief Determines whether an element exists in a range. 03072 * @param first An iterator. 03073 * @param last Another iterator. 03074 * @param val The search term. 03075 * @param comp A functor to use for comparisons. 03076 * @return True if @a val (or its equivelent) is in [@a first,@a last ]. 03077 * @ingroup binarysearch 03078 * 03079 * Note that this does not actually return an iterator to @a val. For 03080 * that, use std::find or a container's specialized find member functions. 03081 * 03082 * The comparison function should have the same effects on ordering as 03083 * the function used for the initial sort. 03084 */ 03085 template<typename _ForwardIter, typename _Tp, typename _Compare> 03086 bool 03087 binary_search(_ForwardIter __first, _ForwardIter __last, 03088 const _Tp& __val, _Compare __comp) 03089 { 03090 // concept requirements 03091 __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter>) 03092 __glibcpp_function_requires(_BinaryPredicateConcept<_Compare, 03093 typename iterator_traits<_ForwardIter>::value_type, _Tp>) 03094 __glibcpp_function_requires(_BinaryPredicateConcept<_Compare, _Tp, 03095 typename iterator_traits<_ForwardIter>::value_type>) 03096 03097 _ForwardIter __i = lower_bound(__first, __last, __val, __comp); 03098 return __i != __last && !__comp(__val, *__i); 03099 } 03100 03101 /** 03102 * @brief Merges two sorted ranges. 03103 * @param first1 An iterator. 03104 * @param first2 Another iterator. 03105 * @param last1 Another iterator. 03106 * @param last2 Another iterator. 03107 * @param result An iterator pointing to the end of the merged range. 03108 * @return An iterator pointing to the first element "not less than" @a val. 03109 * 03110 * Merges the ranges [first1,last1) and [first2,last2) into the sorted range 03111 * [result, result + (last1-first1) + (last2-first2)). Both input ranges 03112 * must be sorted, and the output range must not overlap with either of 03113 * the input ranges. The sort is @e stable, that is, for equivalent 03114 * elements in the two ranges, elements from the first range will always 03115 * come before elements from the second. 03116 */ 03117 template<typename _InputIter1, typename _InputIter2, typename _OutputIter> 03118 _OutputIter 03119 merge(_InputIter1 __first1, _InputIter1 __last1, 03120 _InputIter2 __first2, _InputIter2 __last2, 03121 _OutputIter __result) 03122 { 03123 // concept requirements 03124 __glibcpp_function_requires(_InputIteratorConcept<_InputIter1>) 03125 __glibcpp_function_requires(_InputIteratorConcept<_InputIter2>) 03126 __glibcpp_function_requires(_OutputIteratorConcept<_OutputIter, 03127 typename iterator_traits<_InputIter1>::value_type>) 03128 __glibcpp_function_requires(_SameTypeConcept< 03129 typename iterator_traits<_InputIter1>::value_type, 03130 typename iterator_traits<_InputIter2>::value_type>) 03131 __glibcpp_function_requires(_LessThanComparableConcept< 03132 typename iterator_traits<_InputIter1>::value_type>) 03133 03134 while (__first1 != __last1 && __first2 != __last2) { 03135 if (*__first2 < *__first1) { 03136 *__result = *__first2; 03137 ++__first2; 03138 } 03139 else { 03140 *__result = *__first1; 03141 ++__first1; 03142 } 03143 ++__result; 03144 } 03145 return copy(__first2, __last2, copy(__first1, __last1, __result)); 03146 } 03147 03148 /** 03149 * @brief Merges two sorted ranges. 03150 * @param first1 An iterator. 03151 * @param first2 Another iterator. 03152 * @param last1 Another iterator. 03153 * @param last2 Another iterator. 03154 * @param result An iterator pointing to the end of the merged range. 03155 * @param comp A functor to use for comparisons. 03156 * @return An iterator pointing to the first element "not less than" @a val. 03157 * 03158 * Merges the ranges [first1,last1) and [first2,last2) into the sorted range 03159 * [result, result + (last1-first1) + (last2-first2)). Both input ranges 03160 * must be sorted, and the output range must not overlap with either of 03161 * the input ranges. The sort is @e stable, that is, for equivalent 03162 * elements in the two ranges, elements from the first range will always 03163 * come before elements from the second. 03164 * 03165 * The comparison function should have the same effects on ordering as 03166 * the function used for the initial sort. 03167 */ 03168 template<typename _InputIter1, typename _InputIter2, typename _OutputIter, 03169 typename _Compare> 03170 _OutputIter 03171 merge(_InputIter1 __first1, _InputIter1 __last1, 03172 _InputIter2 __first2, _InputIter2 __last2, 03173 _OutputIter __result, _Compare __comp) 03174 { 03175 // concept requirements 03176 __glibcpp_function_requires(_InputIteratorConcept<_InputIter1>) 03177 __glibcpp_function_requires(_InputIteratorConcept<_InputIter2>) 03178 __glibcpp_function_requires(_SameTypeConcept< 03179 typename iterator_traits<_InputIter1>::value_type, 03180 typename iterator_traits<_InputIter2>::value_type>) 03181 __glibcpp_function_requires(_OutputIteratorConcept<_OutputIter, 03182 typename iterator_traits<_InputIter1>::value_type>) 03183 __glibcpp_function_requires(_BinaryPredicateConcept<_Compare, 03184 typename iterator_traits<_InputIter1>::value_type, 03185 typename iterator_traits<_InputIter2>::value_type>) 03186 03187 while (__first1 != __last1 && __first2 != __last2) { 03188 if (__comp(*__first2, *__first1)) { 03189 *__result = *__first2; 03190 ++__first2; 03191 } 03192 else { 03193 *__result = *__first1; 03194 ++__first1; 03195 } 03196 ++__result; 03197 } 03198 return copy(__first2, __last2, copy(__first1, __last1, __result)); 03199 } 03200 03201 /** 03202 * @if maint 03203 * This is a helper function for the merge routines. 03204 * @endif 03205 */ 03206 template<typename _BidirectionalIter, typename _Distance> 03207 void 03208 __merge_without_buffer(_BidirectionalIter __first, 03209 _BidirectionalIter __middle, 03210 _BidirectionalIter __last, 03211 _Distance __len1, _Distance __len2) 03212 { 03213 if (__len1 == 0 || __len2 == 0) 03214 return; 03215 if (__len1 + __len2 == 2) { 03216 if (*__middle < *__first) 03217 iter_swap(__first, __middle); 03218 return; 03219 } 03220 _BidirectionalIter __first_cut = __first; 03221 _BidirectionalIter __second_cut = __middle; 03222 _Distance __len11 = 0; 03223 _Distance __len22 = 0; 03224 if (__len1 > __len2) { 03225 __len11 = __len1 / 2; 03226 advance(__first_cut, __len11); 03227 __second_cut = lower_bound(__middle, __last, *__first_cut); 03228 __len22 = distance(__middle, __second_cut); 03229 } 03230 else { 03231 __len22 = __len2 / 2; 03232 advance(__second_cut, __len22); 03233 __first_cut = upper_bound(__first, __middle, *__second_cut); 03234 __len11 = distance(__first, __first_cut); 03235 } 03236 rotate(__first_cut, __middle, __second_cut); 03237 _BidirectionalIter __new_middle = __first_cut; 03238 advance(__new_middle, distance(__middle, __second_cut)); 03239 __merge_without_buffer(__first, __first_cut, __new_middle, 03240 __len11, __len22); 03241 __merge_without_buffer(__new_middle, __second_cut, __last, 03242 __len1 - __len11, __len2 - __len22); 03243 } 03244 03245 /** 03246 * @if maint 03247 * This is a helper function for the merge routines. 03248 * @endif 03249 */ 03250 template<typename _BidirectionalIter, typename _Distance, typename _Compare> 03251 void 03252 __merge_without_buffer(_BidirectionalIter __first, 03253 _BidirectionalIter __middle, 03254 _BidirectionalIter __last, 03255 _Distance __len1, _Distance __len2, 03256 _Compare __comp) 03257 { 03258 if (__len1 == 0 || __len2 == 0) 03259 return; 03260 if (__len1 + __len2 == 2) { 03261 if (__comp(*__middle, *__first)) 03262 iter_swap(__first, __middle); 03263 return; 03264 } 03265 _BidirectionalIter __first_cut = __first; 03266 _BidirectionalIter __second_cut = __middle; 03267 _Distance __len11 = 0; 03268 _Distance __len22 = 0; 03269 if (__len1 > __len2) { 03270 __len11 = __len1 / 2; 03271 advance(__first_cut, __len11); 03272 __second_cut = lower_bound(__middle, __last, *__first_cut, __comp); 03273 __len22 = distance(__middle, __second_cut); 03274 } 03275 else { 03276 __len22 = __len2 / 2; 03277 advance(__second_cut, __len22); 03278 __first_cut = upper_bound(__first, __middle, *__second_cut, __comp); 03279 __len11 = distance(__first, __first_cut); 03280 } 03281 rotate(__first_cut, __middle, __second_cut); 03282 _BidirectionalIter __new_middle = __first_cut; 03283 advance(__new_middle, distance(__middle, __second_cut)); 03284 __merge_without_buffer(__first, __first_cut, __new_middle, 03285 __len11, __len22, __comp); 03286 __merge_without_buffer(__new_middle, __second_cut, __last, 03287 __len1 - __len11, __len2 - __len22, __comp); 03288 } 03289 03290 /** 03291 * @if maint 03292 * This is a helper function for the merge routines. 03293 * @endif 03294 */ 03295 template<typename _BidirectionalIter1, typename _BidirectionalIter2, 03296 typename _Distance> 03297 _BidirectionalIter1 03298 __rotate_adaptive(_BidirectionalIter1 __first, 03299 _BidirectionalIter1 __middle, 03300 _BidirectionalIter1 __last, 03301 _Distance __len1, _Distance __len2, 03302 _BidirectionalIter2 __buffer, 03303 _Distance __buffer_size) 03304 { 03305 _BidirectionalIter2 __buffer_end; 03306 if (__len1 > __len2 && __len2 <= __buffer_size) { 03307 __buffer_end = copy(__middle, __last, __buffer); 03308 copy_backward(__first, __middle, __last); 03309 return copy(__buffer, __buffer_end, __first); 03310 } 03311 else if (__len1 <= __buffer_size) { 03312 __buffer_end = copy(__first, __middle, __buffer); 03313 copy(__middle, __last, __first); 03314 return copy_backward(__buffer, __buffer_end, __last); 03315 } 03316 else { 03317 rotate(__first, __middle, __last); 03318 advance(__first, distance(__middle, __last)); 03319 return __first; 03320 } 03321 } 03322 03323 /** 03324 * @if maint 03325 * This is a helper function for the merge routines. 03326 * @endif 03327 */ 03328 template<typename _BidirectionalIter1, typename _BidirectionalIter2, 03329 typename _BidirectionalIter3> 03330 _BidirectionalIter3 03331 __merge_backward(_BidirectionalIter1 __first1, _BidirectionalIter1 __last1, 03332 _BidirectionalIter2 __first2, _BidirectionalIter2 __last2, 03333 _BidirectionalIter3 __result) 03334 { 03335 if (__first1 == __last1) 03336 return copy_backward(__first2, __last2, __result); 03337 if (__first2 == __last2) 03338 return copy_backward(__first1, __last1, __result); 03339 --__last1; 03340 --__last2; 03341 while (true) { 03342 if (*__last2 < *__last1) { 03343 *--__result = *__last1; 03344 if (__first1 == __last1) 03345 return copy_backward(__first2, ++__last2, __result); 03346 --__last1; 03347 } 03348 else { 03349 *--__result = *__last2; 03350 if (__first2 == __last2) 03351 return copy_backward(__first1, ++__last1, __result); 03352 --__last2; 03353 } 03354 } 03355 } 03356 03357 /** 03358 * @if maint 03359 * This is a helper function for the merge routines. 03360 * @endif 03361 */ 03362 template<typename _BidirectionalIter1, typename _BidirectionalIter2, 03363 typename _BidirectionalIter3, typename _Compare> 03364 _BidirectionalIter3 03365 __merge_backward(_BidirectionalIter1 __first1, _BidirectionalIter1 __last1, 03366 _BidirectionalIter2 __first2, _BidirectionalIter2 __last2, 03367 _BidirectionalIter3 __result, 03368 _Compare __comp) 03369 { 03370 if (__first1 == __last1) 03371 return copy_backward(__first2, __last2, __result); 03372 if (__first2 == __last2) 03373 return copy_backward(__first1, __last1, __result); 03374 --__last1; 03375 --__last2; 03376 while (true) { 03377 if (__comp(*__last2, *__last1)) { 03378 *--__result = *__last1; 03379 if (__first1 == __last1) 03380 return copy_backward(__first2, ++__last2, __result); 03381 --__last1; 03382 } 03383 else { 03384 *--__result = *__last2; 03385 if (__first2 == __last2) 03386 return copy_backward(__first1, ++__last1, __result); 03387 --__last2; 03388 } 03389 } 03390 } 03391 03392 /** 03393 * @if maint 03394 * This is a helper function for the merge routines. 03395 * @endif 03396 */ 03397 template<typename _BidirectionalIter, typename _Distance, typename _Pointer> 03398 void 03399 __merge_adaptive(_BidirectionalIter __first, 03400 _BidirectionalIter __middle, 03401 _BidirectionalIter __last, 03402 _Distance __len1, _Distance __len2, 03403 _Pointer __buffer, _Distance __buffer_size) 03404 { 03405 if (__len1 <= __len2 && __len1 <= __buffer_size) { 03406 _Pointer __buffer_end = copy(__first, __middle, __buffer); 03407 merge(__buffer, __buffer_end, __middle, __last, __first); 03408 } 03409 else if (__len2 <= __buffer_size) { 03410 _Pointer __buffer_end = copy(__middle, __last, __buffer); 03411 __merge_backward(__first, __middle, __buffer, __buffer_end, __last); 03412 } 03413 else { 03414 _BidirectionalIter __first_cut = __first; 03415 _BidirectionalIter __second_cut = __middle; 03416 _Distance __len11 = 0; 03417 _Distance __len22 = 0; 03418 if (__len1 > __len2) { 03419 __len11 = __len1 / 2; 03420 advance(__first_cut, __len11); 03421 __second_cut = lower_bound(__middle, __last, *__first_cut); 03422 __len22 = distance(__middle, __second_cut); 03423 } 03424 else { 03425 __len22 = __len2 / 2; 03426 advance(__second_cut, __len22); 03427 __first_cut = upper_bound(__first, __middle, *__second_cut); 03428 __len11 = distance(__first, __first_cut); 03429 } 03430 _BidirectionalIter __new_middle = 03431 __rotate_adaptive(__first_cut, __middle, __second_cut, 03432 __len1 - __len11, __len22, __buffer, 03433 __buffer_size); 03434 __merge_adaptive(__first, __first_cut, __new_middle, __len11, 03435 __len22, __buffer, __buffer_size); 03436 __merge_adaptive(__new_middle, __second_cut, __last, __len1 - __len11, 03437 __len2 - __len22, __buffer, __buffer_size); 03438 } 03439 } 03440 03441 /** 03442 * @if maint 03443 * This is a helper function for the merge routines. 03444 * @endif 03445 */ 03446 template<typename _BidirectionalIter, typename _Distance, typename _Pointer, 03447 typename _Compare> 03448 void 03449 __merge_adaptive(_BidirectionalIter __first, 03450 _BidirectionalIter __middle, 03451 _BidirectionalIter __last, 03452 _Distance __len1, _Distance __len2, 03453 _Pointer __buffer, _Distance __buffer_size, 03454 _Compare __comp) 03455 { 03456 if (__len1 <= __len2 && __len1 <= __buffer_size) { 03457 _Pointer __buffer_end = copy(__first, __middle, __buffer); 03458 merge(__buffer, __buffer_end, __middle, __last, __first, __comp); 03459 } 03460 else if (__len2 <= __buffer_size) { 03461 _Pointer __buffer_end = copy(__middle, __last, __buffer); 03462 __merge_backward(__first, __middle, __buffer, __buffer_end, __last, 03463 __comp); 03464 } 03465 else { 03466 _BidirectionalIter __first_cut = __first; 03467 _BidirectionalIter __second_cut = __middle; 03468 _Distance __len11 = 0; 03469 _Distance __len22 = 0; 03470 if (__len1 > __len2) { 03471 __len11 = __len1 / 2; 03472 advance(__first_cut, __len11); 03473 __second_cut = lower_bound(__middle, __last, *__first_cut, __comp); 03474 __len22 = distance(__middle, __second_cut); 03475 } 03476 else { 03477 __len22 = __len2 / 2; 03478 advance(__second_cut, __len22); 03479 __first_cut = upper_bound(__first, __middle, *__second_cut, __comp); 03480 __len11 = distance(__first, __first_cut); 03481 } 03482 _BidirectionalIter __new_middle = 03483 __rotate_adaptive(__first_cut, __middle, __second_cut, 03484 __len1 - __len11, __len22, __buffer, 03485 __buffer_size); 03486 __merge_adaptive(__first, __first_cut, __new_middle, __len11, 03487 __len22, __buffer, __buffer_size, __comp); 03488 __merge_adaptive(__new_middle, __second_cut, __last, __len1 - __len11, 03489 __len2 - __len22, __buffer, __buffer_size, __comp); 03490 } 03491 } 03492 03493 /** 03494 * @brief Merges two sorted ranges in place. 03495 * @param first An iterator. 03496 * @param middle Another iterator. 03497 * @param last Another iterator. 03498 * @return Nothing. 03499 * 03500 * Merges two sorted and consecutive ranges, [first,middle) and 03501 * [middle,last), and puts the result in [first,last). The output will 03502 * be sorted. The sort is @e stable, that is, for equivalent 03503 * elements in the two ranges, elements from the first range will always 03504 * come before elements from the second. 03505 * 03506 * If enough additional memory is available, this takes (last-first)-1 03507 * comparisons. Otherwise an NlogN algorithm is used, where N is 03508 * distance(first,last). 03509 */ 03510 template<typename _BidirectionalIter> 03511 void 03512 inplace_merge(_BidirectionalIter __first, 03513 _BidirectionalIter __middle, 03514 _BidirectionalIter __last) 03515 { 03516 typedef typename iterator_traits<_BidirectionalIter>::value_type 03517 _ValueType; 03518 typedef typename iterator_traits<_BidirectionalIter>::difference_type 03519 _DistanceType; 03520 03521 // concept requirements 03522 __glibcpp_function_requires(_Mutable_BidirectionalIteratorConcept< 03523 _BidirectionalIter>) 03524 __glibcpp_function_requires(_LessThanComparableConcept<_ValueType>) 03525 03526 if (__first == __middle || __middle == __last) 03527 return; 03528 03529 _DistanceType __len1 = distance(__first, __middle); 03530 _DistanceType __len2 = distance(__middle, __last); 03531 03532 _Temporary_buffer<_BidirectionalIter, _ValueType> __buf(__first, __last); 03533 if (__buf.begin() == 0) 03534 __merge_without_buffer(__first, __middle, __last, __len1, __len2); 03535 else 03536 __merge_adaptive(__first, __middle, __last, __len1, __len2, 03537 __buf.begin(), _DistanceType(__buf.size())); 03538 } 03539 03540 /** 03541 * @brief Merges two sorted ranges in place. 03542 * @param first An iterator. 03543 * @param middle Another iterator. 03544 * @param last Another iterator. 03545 * @param comp A functor to use for comparisons. 03546 * @return Nothing. 03547 * 03548 * Merges two sorted and consecutive ranges, [first,middle) and 03549 * [middle,last), and puts the result in [first,last). The output will 03550 * be sorted. The sort is @e stable, that is, for equivalent 03551 * elements in the two ranges, elements from the first range will always 03552 * come before elements from the second. 03553 * 03554 * If enough additional memory is available, this takes (last-first)-1 03555 * comparisons. Otherwise an NlogN algorithm is used, where N is 03556 * distance(first,last). 03557 * 03558 * The comparison function should have the same effects on ordering as 03559 * the function used for the initial sort. 03560 */ 03561 template<typename _BidirectionalIter, typename _Compare> 03562 void 03563 inplace_merge(_BidirectionalIter __first, 03564 _BidirectionalIter __middle, 03565 _BidirectionalIter __last, 03566 _Compare __comp) 03567 { 03568 typedef typename iterator_traits<_BidirectionalIter>::value_type 03569 _ValueType; 03570 typedef typename iterator_traits<_BidirectionalIter>::difference_type 03571 _DistanceType; 03572 03573 // concept requirements 03574 __glibcpp_function_requires(_Mutable_BidirectionalIteratorConcept< 03575 _BidirectionalIter>) 03576 __glibcpp_function_requires(_BinaryPredicateConcept<_Compare, 03577 _ValueType, _ValueType>) 03578 03579 if (__first == __middle || __middle == __last) 03580 return; 03581 03582 _DistanceType __len1 = distance(__first, __middle); 03583 _DistanceType __len2 = distance(__middle, __last); 03584 03585 _Temporary_buffer<_BidirectionalIter, _ValueType> __buf(__first, __last); 03586 if (__buf.begin() == 0) 03587 __merge_without_buffer(__first, __middle, __last, __len1, __len2, __comp); 03588 else 03589 __merge_adaptive(__first, __middle, __last, __len1, __len2, 03590 __buf.begin(), _DistanceType(__buf.size()), 03591 __comp); 03592 } 03593 03594 // Set algorithms: includes, set_union, set_intersection, set_difference, 03595 // set_symmetric_difference. All of these algorithms have the precondition 03596 // that their input ranges are sorted and the postcondition that their output 03597 // ranges are sorted. 03598 03599 template<typename _InputIter1, typename _InputIter2> 03600 bool 03601 includes(_InputIter1 __first1, _InputIter1 __last1, 03602 _InputIter2 __first2, _InputIter2 __last2) 03603 { 03604 // concept requirements 03605 __glibcpp_function_requires(_InputIteratorConcept<_InputIter1>) 03606 __glibcpp_function_requires(_InputIteratorConcept<_InputIter2>) 03607 __glibcpp_function_requires(_SameTypeConcept< 03608 typename iterator_traits<_InputIter1>::value_type, 03609 typename iterator_traits<_InputIter2>::value_type>) 03610 __glibcpp_function_requires(_LessThanComparableConcept< 03611 typename iterator_traits<_InputIter1>::value_type>) 03612 03613 while (__first1 != __last1 && __first2 != __last2) 03614 if (*__first2 < *__first1) 03615 return false; 03616 else if(*__first1 < *__first2) 03617 ++__first1; 03618 else 03619 ++__first1, ++__first2; 03620 03621 return __first2 == __last2; 03622 } 03623 03624 template<typename _InputIter1, typename _InputIter2, typename _Compare> 03625 bool 03626 includes(_InputIter1 __first1, _InputIter1 __last1, 03627 _InputIter2 __first2, _InputIter2 __last2, _Compare __comp) 03628 { 03629 // concept requirements 03630 __glibcpp_function_requires(_InputIteratorConcept<_InputIter1>) 03631 __glibcpp_function_requires(_InputIteratorConcept<_InputIter2>) 03632 __glibcpp_function_requires(_SameTypeConcept< 03633 typename iterator_traits<_InputIter1>::value_type, 03634 typename iterator_traits<_InputIter2>::value_type>) 03635 __glibcpp_function_requires(_BinaryPredicateConcept<_Compare, 03636 typename iterator_traits<_InputIter1>::value_type, 03637 typename iterator_traits<_InputIter2>::value_type>) 03638 03639 while (__first1 != __last1 && __first2 != __last2) 03640 if (__comp(*__first2, *__first1)) 03641 return false; 03642 else if(__comp(*__first1, *__first2)) 03643 ++__first1; 03644 else 03645 ++__first1, ++__first2; 03646 03647 return __first2 == __last2; 03648 } 03649 03650 template<typename _InputIter1, typename _InputIter2, typename _OutputIter> 03651 _OutputIter 03652 set_union(_InputIter1 __first1, _InputIter1 __last1, 03653 _InputIter2 __first2, _InputIter2 __last2, 03654 _OutputIter __result) 03655 { 03656 // concept requirements 03657 __glibcpp_function_requires(_InputIteratorConcept<_InputIter1>) 03658 __glibcpp_function_requires(_InputIteratorConcept<_InputIter2>) 03659 __glibcpp_function_requires(_OutputIteratorConcept<_OutputIter, 03660 typename iterator_traits<_InputIter1>::value_type>) 03661 __glibcpp_function_requires(_SameTypeConcept< 03662 typename iterator_traits<_InputIter1>::value_type, 03663 typename iterator_traits<_InputIter2>::value_type>) 03664 __glibcpp_function_requires(_LessThanComparableConcept< 03665 typename iterator_traits<_InputIter1>::value_type>) 03666 03667 while (__first1 != __last1 && __first2 != __last2) { 03668 if (*__first1 < *__first2) { 03669 *__result = *__first1; 03670 ++__first1; 03671 } 03672 else if (*__first2 < *__first1) { 03673 *__result = *__first2; 03674 ++__first2; 03675 } 03676 else { 03677 *__result = *__first1; 03678 ++__first1; 03679 ++__first2; 03680 } 03681 ++__result; 03682 } 03683 return copy(__first2, __last2, copy(__first1, __last1, __result)); 03684 } 03685 03686 template<typename _InputIter1, typename _InputIter2, typename _OutputIter, 03687 typename _Compare> 03688 _OutputIter 03689 set_union(_InputIter1 __first1, _InputIter1 __last1, 03690 _InputIter2 __first2, _InputIter2 __last2, 03691 _OutputIter __result, _Compare __comp) 03692 { 03693 // concept requirements 03694 __glibcpp_function_requires(_InputIteratorConcept<_InputIter1>) 03695 __glibcpp_function_requires(_InputIteratorConcept<_InputIter2>) 03696 __glibcpp_function_requires(_SameTypeConcept< 03697 typename iterator_traits<_InputIter1>::value_type, 03698 typename iterator_traits<_InputIter2>::value_type>) 03699 __glibcpp_function_requires(_OutputIteratorConcept<_OutputIter, 03700 typename iterator_traits<_InputIter1>::value_type>) 03701 __glibcpp_function_requires(_BinaryPredicateConcept<_Compare, 03702 typename iterator_traits<_InputIter1>::value_type, 03703 typename iterator_traits<_InputIter2>::value_type>) 03704 03705 while (__first1 != __last1 && __first2 != __last2) { 03706 if (__comp(*__first1, *__first2)) { 03707 *__result = *__first1; 03708 ++__first1; 03709 } 03710 else if (__comp(*__first2, *__first1)) { 03711 *__result = *__first2; 03712 ++__first2; 03713 } 03714 else { 03715 *__result = *__first1; 03716 ++__first1; 03717 ++__first2; 03718 } 03719 ++__result; 03720 } 03721 return copy(__first2, __last2, copy(__first1, __last1, __result)); 03722 } 03723 03724 template<typename _InputIter1, typename _InputIter2, typename _OutputIter> 03725 _OutputIter 03726 set_intersection(_InputIter1 __first1, _InputIter1 __last1, 03727 _InputIter2 __first2, _InputIter2 __last2, 03728 _OutputIter __result) 03729 { 03730 // concept requirements 03731 __glibcpp_function_requires(_InputIteratorConcept<_InputIter1>) 03732 __glibcpp_function_requires(_InputIteratorConcept<_InputIter2>) 03733 __glibcpp_function_requires(_OutputIteratorConcept<_OutputIter, 03734 typename iterator_traits<_InputIter1>::value_type>) 03735 __glibcpp_function_requires(_SameTypeConcept< 03736 typename iterator_traits<_InputIter1>::value_type, 03737 typename iterator_traits<_InputIter2>::value_type>) 03738 __glibcpp_function_requires(_LessThanComparableConcept< 03739 typename iterator_traits<_InputIter1>::value_type>) 03740 03741 while (__first1 != __last1 && __first2 != __last2) 03742 if (*__first1 < *__first2) 03743 ++__first1; 03744 else if (*__first2 < *__first1) 03745 ++__first2; 03746 else { 03747 *__result = *__first1; 03748 ++__first1; 03749 ++__first2; 03750 ++__result; 03751 } 03752 return __result; 03753 } 03754 03755 template<typename _InputIter1, typename _InputIter2, typename _OutputIter, 03756 typename _Compare> 03757 _OutputIter 03758 set_intersection(_InputIter1 __first1, _InputIter1 __last1, 03759 _InputIter2 __first2, _InputIter2 __last2, 03760 _OutputIter __result, _Compare __comp) 03761 { 03762 // concept requirements 03763 __glibcpp_function_requires(_InputIteratorConcept<_InputIter1>) 03764 __glibcpp_function_requires(_InputIteratorConcept<_InputIter2>) 03765 __glibcpp_function_requires(_SameTypeConcept< 03766 typename iterator_traits<_InputIter1>::value_type, 03767 typename iterator_traits<_InputIter2>::value_type>) 03768 __glibcpp_function_requires(_OutputIteratorConcept<_OutputIter, 03769 typename iterator_traits<_InputIter1>::value_type>) 03770 __glibcpp_function_requires(_BinaryPredicateConcept<_Compare, 03771 typename iterator_traits<_InputIter1>::value_type, 03772 typename iterator_traits<_InputIter2>::value_type>) 03773 03774 while (__first1 != __last1 && __first2 != __last2) 03775 if (__comp(*__first1, *__first2)) 03776 ++__first1; 03777 else if (__comp(*__first2, *__first1)) 03778 ++__first2; 03779 else { 03780 *__result = *__first1; 03781 ++__first1; 03782 ++__first2; 03783 ++__result; 03784 } 03785 return __result; 03786 } 03787 03788 template<typename _InputIter1, typename _InputIter2, typename _OutputIter> 03789 _OutputIter 03790 set_difference(_InputIter1 __first1, _InputIter1 __last1, 03791 _InputIter2 __first2, _InputIter2 __last2, 03792 _OutputIter __result) 03793 { 03794 // concept requirements 03795 __glibcpp_function_requires(_InputIteratorConcept<_InputIter1>) 03796 __glibcpp_function_requires(_InputIteratorConcept<_InputIter2>) 03797 __glibcpp_function_requires(_OutputIteratorConcept<_OutputIter, 03798 typename iterator_traits<_InputIter1>::value_type>) 03799 __glibcpp_function_requires(_SameTypeConcept< 03800 typename iterator_traits<_InputIter1>::value_type, 03801 typename iterator_traits<_InputIter2>::value_type>) 03802 __glibcpp_function_requires(_LessThanComparableConcept< 03803 typename iterator_traits<_InputIter1>::value_type>) 03804 03805 while (__first1 != __last1 && __first2 != __last2) 03806 if (*__first1 < *__first2) { 03807 *__result = *__first1; 03808 ++__first1; 03809 ++__result; 03810 } 03811 else if (*__first2 < *__first1) 03812 ++__first2; 03813 else { 03814 ++__first1; 03815 ++__first2; 03816 } 03817 return copy(__first1, __last1, __result); 03818 } 03819 03820 template<typename _InputIter1, typename _InputIter2, typename _OutputIter, 03821 typename _Compare> 03822 _OutputIter 03823 set_difference(_InputIter1 __first1, _InputIter1 __last1, 03824 _InputIter2 __first2, _InputIter2 __last2, 03825 _OutputIter __result, _Compare __comp) 03826 { 03827 // concept requirements 03828 __glibcpp_function_requires(_InputIteratorConcept<_InputIter1>) 03829 __glibcpp_function_requires(_InputIteratorConcept<_InputIter2>) 03830 __glibcpp_function_requires(_SameTypeConcept< 03831 typename iterator_traits<_InputIter1>::value_type, 03832 typename iterator_traits<_InputIter2>::value_type>) 03833 __glibcpp_function_requires(_OutputIteratorConcept<_OutputIter, 03834 typename iterator_traits<_InputIter1>::value_type>) 03835 __glibcpp_function_requires(_BinaryPredicateConcept<_Compare, 03836 typename iterator_traits<_InputIter1>::value_type, 03837 typename iterator_traits<_InputIter2>::value_type>) 03838 03839 while (__first1 != __last1 && __first2 != __last2) 03840 if (__comp(*__first1, *__first2)) { 03841 *__result = *__first1; 03842 ++__first1; 03843 ++__result; 03844 } 03845 else if (__comp(*__first2, *__first1)) 03846 ++__first2; 03847 else { 03848 ++__first1; 03849 ++__first2; 03850 } 03851 return copy(__first1, __last1, __result); 03852 } 03853 03854 template<typename _InputIter1, typename _InputIter2, typename _OutputIter> 03855 _OutputIter 03856 set_symmetric_difference(_InputIter1 __first1, _InputIter1 __last1, 03857 _InputIter2 __first2, _InputIter2 __last2, 03858 _OutputIter __result) 03859 { 03860 // concept requirements 03861 __glibcpp_function_requires(_InputIteratorConcept<_InputIter1>) 03862 __glibcpp_function_requires(_InputIteratorConcept<_InputIter2>) 03863 __glibcpp_function_requires(_OutputIteratorConcept<_OutputIter, 03864 typename iterator_traits<_InputIter1>::value_type>) 03865 __glibcpp_function_requires(_SameTypeConcept< 03866 typename iterator_traits<_InputIter1>::value_type, 03867 typename iterator_traits<_InputIter2>::value_type>) 03868 __glibcpp_function_requires(_LessThanComparableConcept< 03869 typename iterator_traits<_InputIter1>::value_type>) 03870 03871 while (__first1 != __last1 && __first2 != __last2) 03872 if (*__first1 < *__first2) { 03873 *__result = *__first1; 03874 ++__first1; 03875 ++__result; 03876 } 03877 else if (*__first2 < *__first1) { 03878 *__result = *__first2; 03879 ++__first2; 03880 ++__result; 03881 } 03882 else { 03883 ++__first1; 03884 ++__first2; 03885 } 03886 return copy(__first2, __last2, copy(__first1, __last1, __result)); 03887 } 03888 03889 template<typename _InputIter1, typename _InputIter2, typename _OutputIter, 03890 typename _Compare> 03891 _OutputIter 03892 set_symmetric_difference(_InputIter1 __first1, _InputIter1 __last1, 03893 _InputIter2 __first2, _InputIter2 __last2, 03894 _OutputIter __result, 03895 _Compare __comp) 03896 { 03897 // concept requirements 03898 __glibcpp_function_requires(_InputIteratorConcept<_InputIter1>) 03899 __glibcpp_function_requires(_InputIteratorConcept<_InputIter2>) 03900 __glibcpp_function_requires(_SameTypeConcept< 03901 typename iterator_traits<_InputIter1>::value_type, 03902 typename iterator_traits<_InputIter2>::value_type>) 03903 __glibcpp_function_requires(_OutputIteratorConcept<_OutputIter, 03904 typename iterator_traits<_InputIter1>::value_type>) 03905 __glibcpp_function_requires(_BinaryPredicateConcept<_Compare, 03906 typename iterator_traits<_InputIter1>::value_type, 03907 typename iterator_traits<_InputIter2>::value_type>) 03908 03909 while (__first1 != __last1 && __first2 != __last2) 03910 if (__comp(*__first1, *__first2)) { 03911 *__result = *__first1; 03912 ++__first1; 03913 ++__result; 03914 } 03915 else if (__comp(*__first2, *__first1)) { 03916 *__result = *__first2; 03917 ++__first2; 03918 ++__result; 03919 } 03920 else { 03921 ++__first1; 03922 ++__first2; 03923 } 03924 return copy(__first2, __last2, copy(__first1, __last1, __result)); 03925 } 03926 03927 // min_element and max_element, with and without an explicitly supplied 03928 // comparison function. 03929 03930 template<typename _ForwardIter> 03931 _ForwardIter 03932 max_element(_ForwardIter __first, _ForwardIter __last) 03933 { 03934 // concept requirements 03935 __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter>) 03936 __glibcpp_function_requires(_LessThanComparableConcept< 03937 typename iterator_traits<_ForwardIter>::value_type>) 03938 03939 if (__first == __last) return __first; 03940 _ForwardIter __result = __first; 03941 while (++__first != __last) 03942 if (*__result < *__first) 03943 __result = __first; 03944 return __result; 03945 } 03946 03947 template<typename _ForwardIter, typename _Compare> 03948 _ForwardIter 03949 max_element(_ForwardIter __first, _ForwardIter __last, 03950 _Compare __comp) 03951 { 03952 // concept requirements 03953 __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter>) 03954 __glibcpp_function_requires(_BinaryPredicateConcept<_Compare, 03955 typename iterator_traits<_ForwardIter>::value_type, 03956 typename iterator_traits<_ForwardIter>::value_type>) 03957 03958 if (__first == __last) return __first; 03959 _ForwardIter __result = __first; 03960 while (++__first != __last) 03961 if (__comp(*__result, *__first)) __result = __first; 03962 return __result; 03963 } 03964 03965 template<typename _ForwardIter> 03966 _ForwardIter 03967 min_element(_ForwardIter __first, _ForwardIter __last) 03968 { 03969 // concept requirements 03970 __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter>) 03971 __glibcpp_function_requires(_LessThanComparableConcept< 03972 typename iterator_traits<_ForwardIter>::value_type>) 03973 03974 if (__first == __last) return __first; 03975 _ForwardIter __result = __first; 03976 while (++__first != __last) 03977 if (*__first < *__result) 03978 __result = __first; 03979 return __result; 03980 } 03981 03982 template<typename _ForwardIter, typename _Compare> 03983 _ForwardIter 03984 min_element(_ForwardIter __first, _ForwardIter __last, 03985 _Compare __comp) 03986 { 03987 // concept requirements 03988 __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter>) 03989 __glibcpp_function_requires(_BinaryPredicateConcept<_Compare, 03990 typename iterator_traits<_ForwardIter>::value_type, 03991 typename iterator_traits<_ForwardIter>::value_type>) 03992 03993 if (__first == __last) return __first; 03994 _ForwardIter __result = __first; 03995 while (++__first != __last) 03996 if (__comp(*__first, *__result)) 03997 __result = __first; 03998 return __result; 03999 } 04000 04001 // next_permutation and prev_permutation, with and without an explicitly 04002 // supplied comparison function. 04003 04004 template<typename _BidirectionalIter> 04005 bool 04006 next_permutation(_BidirectionalIter __first, _BidirectionalIter __last) 04007 { 04008 // concept requirements 04009 __glibcpp_function_requires(_BidirectionalIteratorConcept<_BidirectionalIter>) 04010 __glibcpp_function_requires(_LessThanComparableConcept< 04011 typename iterator_traits<_BidirectionalIter>::value_type>) 04012 04013 if (__first == __last) 04014 return false; 04015 _BidirectionalIter __i = __first; 04016 ++__i; 04017 if (__i == __last) 04018 return false; 04019 __i = __last; 04020 --__i; 04021 04022 for(;;) { 04023 _BidirectionalIter __ii = __i; 04024 --__i; 04025 if (*__i < *__ii) { 04026 _BidirectionalIter __j = __last; 04027 while (!(*__i < *--__j)) 04028 {} 04029 iter_swap(__i, __j); 04030 reverse(__ii, __last); 04031 return true; 04032 } 04033 if (__i == __first) { 04034 reverse(__first, __last); 04035 return false; 04036 } 04037 } 04038 } 04039 04040 template<typename _BidirectionalIter, typename _Compare> 04041 bool 04042 next_permutation(_BidirectionalIter __first, _BidirectionalIter __last, 04043 _Compare __comp) 04044 { 04045 // concept requirements 04046 __glibcpp_function_requires(_BidirectionalIteratorConcept<_BidirectionalIter>) 04047 __glibcpp_function_requires(_BinaryPredicateConcept<_Compare, 04048 typename iterator_traits<_BidirectionalIter>::value_type, 04049 typename iterator_traits<_BidirectionalIter>::value_type>) 04050 04051 if (__first == __last) 04052 return false; 04053 _BidirectionalIter __i = __first; 04054 ++__i; 04055 if (__i == __last) 04056 return false; 04057 __i = __last; 04058 --__i; 04059 04060 for(;;) { 04061 _BidirectionalIter __ii = __i; 04062 --__i; 04063 if (__comp(*__i, *__ii)) { 04064 _BidirectionalIter __j = __last; 04065 while (!__comp(*__i, *--__j)) 04066 {} 04067 iter_swap(__i, __j); 04068 reverse(__ii, __last); 04069 return true; 04070 } 04071 if (__i == __first) { 04072 reverse(__first, __last); 04073 return false; 04074 } 04075 } 04076 } 04077 04078 template<typename _BidirectionalIter> 04079 bool 04080 prev_permutation(_BidirectionalIter __first, _BidirectionalIter __last) 04081 { 04082 // concept requirements 04083 __glibcpp_function_requires(_BidirectionalIteratorConcept<_BidirectionalIter>) 04084 __glibcpp_function_requires(_LessThanComparableConcept< 04085 typename iterator_traits<_BidirectionalIter>::value_type>) 04086 04087 if (__first == __last) 04088 return false; 04089 _BidirectionalIter __i = __first; 04090 ++__i; 04091 if (__i == __last) 04092 return false; 04093 __i = __last; 04094 --__i; 04095 04096 for(;;) { 04097 _BidirectionalIter __ii = __i; 04098 --__i; 04099 if (*__ii < *__i) { 04100 _BidirectionalIter __j = __last; 04101 while (!(*--__j < *__i)) 04102 {} 04103 iter_swap(__i, __j); 04104 reverse(__ii, __last); 04105 return true; 04106 } 04107 if (__i == __first) { 04108 reverse(__first, __last); 04109 return false; 04110 } 04111 } 04112 } 04113 04114 template<typename _BidirectionalIter, typename _Compare> 04115 bool 04116 prev_permutation(_BidirectionalIter __first, _BidirectionalIter __last, 04117 _Compare __comp) 04118 { 04119 // concept requirements 04120 __glibcpp_function_requires(_BidirectionalIteratorConcept<_BidirectionalIter>) 04121 __glibcpp_function_requires(_BinaryPredicateConcept<_Compare, 04122 typename iterator_traits<_BidirectionalIter>::value_type, 04123 typename iterator_traits<_BidirectionalIter>::value_type>) 04124 04125 if (__first == __last) 04126 return false; 04127 _BidirectionalIter __i = __first; 04128 ++__i; 04129 if (__i == __last) 04130 return false; 04131 __i = __last; 04132 --__i; 04133 04134 for(;;) { 04135 _BidirectionalIter __ii = __i; 04136 --__i; 04137 if (__comp(*__ii, *__i)) { 04138 _BidirectionalIter __j = __last; 04139 while (!__comp(*--__j, *__i)) 04140 {} 04141 iter_swap(__i, __j); 04142 reverse(__ii, __last); 04143 return true; 04144 } 04145 if (__i == __first) { 04146 reverse(__first, __last); 04147 return false; 04148 } 04149 } 04150 } 04151 04152 // find_first_of, with and without an explicitly supplied comparison function. 04153 04154 template<typename _InputIter, typename _ForwardIter> 04155 _InputIter 04156 find_first_of(_InputIter __first1, _InputIter __last1, 04157 _ForwardIter __first2, _ForwardIter __last2) 04158 { 04159 // concept requirements 04160 __glibcpp_function_requires(_InputIteratorConcept<_InputIter>) 04161 __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter>) 04162 __glibcpp_function_requires(_EqualOpConcept< 04163 typename iterator_traits<_InputIter>::value_type, 04164 typename iterator_traits<_ForwardIter>::value_type>) 04165 04166 for ( ; __first1 != __last1; ++__first1) 04167 for (_ForwardIter __iter = __first2; __iter != __last2; ++__iter) 04168 if (*__first1 == *__iter) 04169 return __first1; 04170 return __last1; 04171 } 04172 04173 template<typename _InputIter, typename _ForwardIter, typename _BinaryPredicate> 04174 _InputIter 04175 find_first_of(_InputIter __first1, _InputIter __last1, 04176 _ForwardIter __first2, _ForwardIter __last2, 04177 _BinaryPredicate __comp) 04178 { 04179 // concept requirements 04180 __glibcpp_function_requires(_InputIteratorConcept<_InputIter>) 04181 __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter>) 04182 __glibcpp_function_requires(_EqualOpConcept< 04183 typename iterator_traits<_InputIter>::value_type, 04184 typename iterator_traits<_ForwardIter>::value_type>) 04185 __glibcpp_function_requires(_BinaryPredicateConcept<_BinaryPredicate, 04186 typename iterator_traits<_InputIter>::value_type, 04187 typename iterator_traits<_ForwardIter>::value_type>) 04188 04189 for ( ; __first1 != __last1; ++__first1) 04190 for (_ForwardIter __iter = __first2; __iter != __last2; ++__iter) 04191 if (__comp(*__first1, *__iter)) 04192 return __first1; 04193 return __last1; 04194 } 04195 04196 04197 // find_end, with and without an explicitly supplied comparison function. 04198 // Search [first2, last2) as a subsequence in [first1, last1), and return 04199 // the *last* possible match. Note that find_end for bidirectional iterators 04200 // is much faster than for forward iterators. 04201 04202 // find_end for forward iterators. 04203 template<typename _ForwardIter1, typename _ForwardIter2> 04204 _ForwardIter1 04205 __find_end(_ForwardIter1 __first1, _ForwardIter1 __last1, 04206 _ForwardIter2 __first2, _ForwardIter2 __last2, 04207 forward_iterator_tag, forward_iterator_tag) 04208 { 04209 if (__first2 == __last2) 04210 return __last1; 04211 else { 04212 _ForwardIter1 __result = __last1; 04213 while (1) { 04214 _ForwardIter1 __new_result 04215 = search(__first1, __last1, __first2, __last2); 04216 if (__new_result == __last1) 04217 return __result; 04218 else { 04219 __result = __new_result; 04220 __first1 = __new_result; 04221 ++__first1; 04222 } 04223 } 04224 } 04225 } 04226 04227 template<typename _ForwardIter1, typename _ForwardIter2, 04228 typename _BinaryPredicate> 04229 _ForwardIter1 04230 __find_end(_ForwardIter1 __first1, _ForwardIter1 __last1, 04231 _ForwardIter2 __first2, _ForwardIter2 __last2, 04232 forward_iterator_tag, forward_iterator_tag, 04233 _BinaryPredicate __comp) 04234 { 04235 if (__first2 == __last2) 04236 return __last1; 04237 else { 04238 _ForwardIter1 __result = __last1; 04239 while (1) { 04240 _ForwardIter1 __new_result 04241 = search(__first1, __last1, __first2, __last2, __comp); 04242 if (__new_result == __last1) 04243 return __result; 04244 else { 04245 __result = __new_result; 04246 __first1 = __new_result; 04247 ++__first1; 04248 } 04249 } 04250 } 04251 } 04252 04253 // find_end for bidirectional iterators. Requires partial specialization. 04254 template<typename _BidirectionalIter1, typename _BidirectionalIter2> 04255 _BidirectionalIter1 04256 __find_end(_BidirectionalIter1 __first1, _BidirectionalIter1 __last1, 04257 _BidirectionalIter2 __first2, _BidirectionalIter2 __last2, 04258 bidirectional_iterator_tag, bidirectional_iterator_tag) 04259 { 04260 // concept requirements 04261 __glibcpp_function_requires(_BidirectionalIteratorConcept<_BidirectionalIter1>) 04262 __glibcpp_function_requires(_BidirectionalIteratorConcept<_BidirectionalIter2>) 04263 04264 typedef reverse_iterator<_BidirectionalIter1> _RevIter1; 04265 typedef reverse_iterator<_BidirectionalIter2> _RevIter2; 04266 04267 _RevIter1 __rlast1(__first1); 04268 _RevIter2 __rlast2(__first2); 04269 _RevIter1 __rresult = search(_RevIter1(__last1), __rlast1, 04270 _RevIter2(__last2), __rlast2); 04271 04272 if (__rresult == __rlast1) 04273 return __last1; 04274 else { 04275 _BidirectionalIter1 __result = __rresult.base(); 04276 advance(__result, -distance(__first2, __last2)); 04277 return __result; 04278 } 04279 } 04280 04281 template<typename _BidirectionalIter1, typename _BidirectionalIter2, 04282 typename _BinaryPredicate> 04283 _BidirectionalIter1 04284 __find_end(_BidirectionalIter1 __first1, _BidirectionalIter1 __last1, 04285 _BidirectionalIter2 __first2, _BidirectionalIter2 __last2, 04286 bidirectional_iterator_tag, bidirectional_iterator_tag, 04287 _BinaryPredicate __comp) 04288 { 04289 // concept requirements 04290 __glibcpp_function_requires(_BidirectionalIteratorConcept<_BidirectionalIter1>) 04291 __glibcpp_function_requires(_BidirectionalIteratorConcept<_BidirectionalIter2>) 04292 04293 typedef reverse_iterator<_BidirectionalIter1> _RevIter1; 04294 typedef reverse_iterator<_BidirectionalIter2> _RevIter2; 04295 04296 _RevIter1 __rlast1(__first1); 04297 _RevIter2 __rlast2(__first2); 04298 _RevIter1 __rresult = search(_RevIter1(__last1), __rlast1, 04299 _RevIter2(__last2), __rlast2, 04300 __comp); 04301 04302 if (__rresult == __rlast1) 04303 return __last1; 04304 else { 04305 _BidirectionalIter1 __result = __rresult.base(); 04306 advance(__result, -distance(__first2, __last2)); 04307 return __result; 04308 } 04309 } 04310 04311 // Dispatching functions for find_end. 04312 04313 template<typename _ForwardIter1, typename _ForwardIter2> 04314 inline _ForwardIter1 04315 find_end(_ForwardIter1 __first1, _ForwardIter1 __last1, 04316 _ForwardIter2 __first2, _ForwardIter2 __last2) 04317 { 04318 // concept requirements 04319 __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter1>) 04320 __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter2>) 04321 __glibcpp_function_requires(_EqualOpConcept< 04322 typename iterator_traits<_ForwardIter1>::value_type, 04323 typename iterator_traits<_ForwardIter2>::value_type>) 04324 04325 return __find_end(__first1, __last1, __first2, __last2, 04326 __iterator_category(__first1), 04327 __iterator_category(__first2)); 04328 } 04329 04330 template<typename _ForwardIter1, typename _ForwardIter2, 04331 typename _BinaryPredicate> 04332 inline _ForwardIter1 04333 find_end(_ForwardIter1 __first1, _ForwardIter1 __last1, 04334 _ForwardIter2 __first2, _ForwardIter2 __last2, 04335 _BinaryPredicate __comp) 04336 { 04337 // concept requirements 04338 __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter1>) 04339 __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter2>) 04340 __glibcpp_function_requires(_BinaryPredicateConcept<_BinaryPredicate, 04341 typename iterator_traits<_ForwardIter1>::value_type, 04342 typename iterator_traits<_ForwardIter2>::value_type>) 04343 04344 return __find_end(__first1, __last1, __first2, __last2, 04345 __iterator_category(__first1), 04346 __iterator_category(__first2), 04347 __comp); 04348 } 04349 04350 } // namespace std 04351 04352 #endif /* __GLIBCPP_INTERNAL_ALGO_H */ 04353

Generated on Sun Sep 19 16:33:58 2004 for libstdc++-v3 Source by doxygen 1.3.8