stl_algo.h

Go to the documentation of this file.
00001 // Algorithm implementation -*- C++ -*- 00002 00003 // Copyright (C) 2001, 2002, 2003, 2004 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 _ALGO_H 00062 #define _ALGO_H 1 00063 00064 #include <bits/stl_heap.h> 00065 #include <bits/stl_tempbuf.h> // for _Temporary_buffer 00066 #include <debug/debug.h> 00067 00068 // See concept_check.h for the __glibcxx_*_requires macros. 00069 00070 namespace std 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 __glibcxx_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 __glibcxx_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 _InputIterator, typename _Function> 00151 _Function 00152 for_each(_InputIterator __first, _InputIterator __last, _Function __f) 00153 { 00154 // concept requirements 00155 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) 00156 __glibcxx_requires_valid_range(__first, __last); 00157 for ( ; __first != __last; ++__first) 00158 __f(*__first); 00159 return __f; 00160 } 00161 00162 /** 00163 * @if maint 00164 * This is an overload used by find() for the Input Iterator case. 00165 * @endif 00166 */ 00167 template<typename _InputIterator, typename _Tp> 00168 inline _InputIterator 00169 find(_InputIterator __first, _InputIterator __last, 00170 const _Tp& __val, 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 _InputIterator, typename _Predicate> 00183 inline _InputIterator 00184 find_if(_InputIterator __first, _InputIterator __last, 00185 _Predicate __pred, input_iterator_tag) 00186 { 00187 while (__first != __last && !__pred(*__first)) 00188 ++__first; 00189 return __first; 00190 } 00191 00192 /** 00193 * @if maint 00194 * This is an overload used by find() for the RAI case. 00195 * @endif 00196 */ 00197 template<typename _RandomAccessIterator, typename _Tp> 00198 _RandomAccessIterator 00199 find(_RandomAccessIterator __first, _RandomAccessIterator __last, 00200 const _Tp& __val, random_access_iterator_tag) 00201 { 00202 typename iterator_traits<_RandomAccessIterator>::difference_type 00203 __trip_count = (__last - __first) >> 2; 00204 00205 for ( ; __trip_count > 0 ; --__trip_count) 00206 { 00207 if (*__first == __val) 00208 return __first; 00209 ++__first; 00210 00211 if (*__first == __val) 00212 return __first; 00213 ++__first; 00214 00215 if (*__first == __val) 00216 return __first; 00217 ++__first; 00218 00219 if (*__first == __val) 00220 return __first; 00221 ++__first; 00222 } 00223 00224 switch (__last - __first) 00225 { 00226 case 3: 00227 if (*__first == __val) 00228 return __first; 00229 ++__first; 00230 case 2: 00231 if (*__first == __val) 00232 return __first; 00233 ++__first; 00234 case 1: 00235 if (*__first == __val) 00236 return __first; 00237 ++__first; 00238 case 0: 00239 default: 00240 return __last; 00241 } 00242 } 00243 00244 /** 00245 * @if maint 00246 * This is an overload used by find_if() for the RAI case. 00247 * @endif 00248 */ 00249 template<typename _RandomAccessIterator, typename _Predicate> 00250 _RandomAccessIterator 00251 find_if(_RandomAccessIterator __first, _RandomAccessIterator __last, 00252 _Predicate __pred, random_access_iterator_tag) 00253 { 00254 typename iterator_traits<_RandomAccessIterator>::difference_type 00255 __trip_count = (__last - __first) >> 2; 00256 00257 for ( ; __trip_count > 0 ; --__trip_count) 00258 { 00259 if (__pred(*__first)) 00260 return __first; 00261 ++__first; 00262 00263 if (__pred(*__first)) 00264 return __first; 00265 ++__first; 00266 00267 if (__pred(*__first)) 00268 return __first; 00269 ++__first; 00270 00271 if (__pred(*__first)) 00272 return __first; 00273 ++__first; 00274 } 00275 00276 switch (__last - __first) 00277 { 00278 case 3: 00279 if (__pred(*__first)) 00280 return __first; 00281 ++__first; 00282 case 2: 00283 if (__pred(*__first)) 00284 return __first; 00285 ++__first; 00286 case 1: 00287 if (__pred(*__first)) 00288 return __first; 00289 ++__first; 00290 case 0: 00291 default: 00292 return __last; 00293 } 00294 } 00295 00296 /** 00297 * @brief Find the first occurrence of a value in a sequence. 00298 * @param first An input iterator. 00299 * @param last An input iterator. 00300 * @param val The value to find. 00301 * @return The first iterator @c i in the range @p [first,last) 00302 * such that @c *i == @p val, or @p last if no such iterator exists. 00303 */ 00304 template<typename _InputIterator, typename _Tp> 00305 inline _InputIterator 00306 find(_InputIterator __first, _InputIterator __last, 00307 const _Tp& __val) 00308 { 00309 // concept requirements 00310 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) 00311 __glibcxx_function_requires(_EqualOpConcept< 00312 typename iterator_traits<_InputIterator>::value_type, _Tp>) 00313 __glibcxx_requires_valid_range(__first, __last); 00314 return std::find(__first, __last, __val, 00315 std::__iterator_category(__first)); 00316 } 00317 00318 /** 00319 * @brief Find the first element in a sequence for which a predicate is true. 00320 * @param first An input iterator. 00321 * @param last An input iterator. 00322 * @param pred A predicate. 00323 * @return The first iterator @c i in the range @p [first,last) 00324 * such that @p pred(*i) is true, or @p last if no such iterator exists. 00325 */ 00326 template<typename _InputIterator, typename _Predicate> 00327 inline _InputIterator 00328 find_if(_InputIterator __first, _InputIterator __last, 00329 _Predicate __pred) 00330 { 00331 // concept requirements 00332 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) 00333 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate, 00334 typename iterator_traits<_InputIterator>::value_type>) 00335 __glibcxx_requires_valid_range(__first, __last); 00336 return std::find_if(__first, __last, __pred, 00337 std::__iterator_category(__first)); 00338 } 00339 00340 /** 00341 * @brief Find two adjacent values in a sequence that are equal. 00342 * @param first A forward iterator. 00343 * @param last A forward iterator. 00344 * @return The first iterator @c i such that @c i and @c i+1 are both 00345 * valid iterators in @p [first,last) and such that @c *i == @c *(i+1), 00346 * or @p last if no such iterator exists. 00347 */ 00348 template<typename _ForwardIterator> 00349 _ForwardIterator 00350 adjacent_find(_ForwardIterator __first, _ForwardIterator __last) 00351 { 00352 // concept requirements 00353 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) 00354 __glibcxx_function_requires(_EqualityComparableConcept< 00355 typename iterator_traits<_ForwardIterator>::value_type>) 00356 __glibcxx_requires_valid_range(__first, __last); 00357 if (__first == __last) 00358 return __last; 00359 _ForwardIterator __next = __first; 00360 while(++__next != __last) 00361 { 00362 if (*__first == *__next) 00363 return __first; 00364 __first = __next; 00365 } 00366 return __last; 00367 } 00368 00369 /** 00370 * @brief Find two adjacent values in a sequence using a predicate. 00371 * @param first A forward iterator. 00372 * @param last A forward iterator. 00373 * @param binary_pred A binary predicate. 00374 * @return The first iterator @c i such that @c i and @c i+1 are both 00375 * valid iterators in @p [first,last) and such that 00376 * @p binary_pred(*i,*(i+1)) is true, or @p last if no such iterator 00377 * exists. 00378 */ 00379 template<typename _ForwardIterator, typename _BinaryPredicate> 00380 _ForwardIterator 00381 adjacent_find(_ForwardIterator __first, _ForwardIterator __last, 00382 _BinaryPredicate __binary_pred) 00383 { 00384 // concept requirements 00385 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) 00386 __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate, 00387 typename iterator_traits<_ForwardIterator>::value_type, 00388 typename iterator_traits<_ForwardIterator>::value_type>) 00389 __glibcxx_requires_valid_range(__first, __last); 00390 if (__first == __last) 00391 return __last; 00392 _ForwardIterator __next = __first; 00393 while(++__next != __last) 00394 { 00395 if (__binary_pred(*__first, *__next)) 00396 return __first; 00397 __first = __next; 00398 } 00399 return __last; 00400 } 00401 00402 /** 00403 * @brief Count the number of copies of a value in a sequence. 00404 * @param first An input iterator. 00405 * @param last An input iterator. 00406 * @param value The value to be counted. 00407 * @return The number of iterators @c i in the range @p [first,last) 00408 * for which @c *i == @p value 00409 */ 00410 template<typename _InputIterator, typename _Tp> 00411 typename iterator_traits<_InputIterator>::difference_type 00412 count(_InputIterator __first, _InputIterator __last, const _Tp& __value) 00413 { 00414 // concept requirements 00415 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) 00416 __glibcxx_function_requires(_EqualityComparableConcept< 00417 typename iterator_traits<_InputIterator>::value_type >) 00418 __glibcxx_function_requires(_EqualityComparableConcept<_Tp>) 00419 __glibcxx_requires_valid_range(__first, __last); 00420 typename iterator_traits<_InputIterator>::difference_type __n = 0; 00421 for ( ; __first != __last; ++__first) 00422 if (*__first == __value) 00423 ++__n; 00424 return __n; 00425 } 00426 00427 /** 00428 * @brief Count the elements of a sequence for which a predicate is true. 00429 * @param first An input iterator. 00430 * @param last An input iterator. 00431 * @param pred A predicate. 00432 * @return The number of iterators @c i in the range @p [first,last) 00433 * for which @p pred(*i) is true. 00434 */ 00435 template<typename _InputIterator, typename _Predicate> 00436 typename iterator_traits<_InputIterator>::difference_type 00437 count_if(_InputIterator __first, _InputIterator __last, _Predicate __pred) 00438 { 00439 // concept requirements 00440 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) 00441 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate, 00442 typename iterator_traits<_InputIterator>::value_type>) 00443 __glibcxx_requires_valid_range(__first, __last); 00444 typename iterator_traits<_InputIterator>::difference_type __n = 0; 00445 for ( ; __first != __last; ++__first) 00446 if (__pred(*__first)) 00447 ++__n; 00448 return __n; 00449 } 00450 00451 /** 00452 * @brief Search a sequence for a matching sub-sequence. 00453 * @param first1 A forward iterator. 00454 * @param last1 A forward iterator. 00455 * @param first2 A forward iterator. 00456 * @param last2 A forward iterator. 00457 * @return The first iterator @c i in the range 00458 * @p [first1,last1-(last2-first2)) such that @c *(i+N) == @p *(first2+N) 00459 * for each @c N in the range @p [0,last2-first2), or @p last1 if no 00460 * such iterator exists. 00461 * 00462 * Searches the range @p [first1,last1) for a sub-sequence that compares 00463 * equal value-by-value with the sequence given by @p [first2,last2) and 00464 * returns an iterator to the first element of the sub-sequence, or 00465 * @p last1 if the sub-sequence is not found. 00466 * 00467 * Because the sub-sequence must lie completely within the range 00468 * @p [first1,last1) it must start at a position less than 00469 * @p last1-(last2-first2) where @p last2-first2 is the length of the 00470 * sub-sequence. 00471 * This means that the returned iterator @c i will be in the range 00472 * @p [first1,last1-(last2-first2)) 00473 */ 00474 template<typename _ForwardIterator1, typename _ForwardIterator2> 00475 _ForwardIterator1 00476 search(_ForwardIterator1 __first1, _ForwardIterator1 __last1, 00477 _ForwardIterator2 __first2, _ForwardIterator2 __last2) 00478 { 00479 // concept requirements 00480 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator1>) 00481 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator2>) 00482 __glibcxx_function_requires(_EqualOpConcept< 00483 typename iterator_traits<_ForwardIterator1>::value_type, 00484 typename iterator_traits<_ForwardIterator2>::value_type>) 00485 __glibcxx_requires_valid_range(__first1, __last1); 00486 __glibcxx_requires_valid_range(__first2, __last2); 00487 // Test for empty ranges 00488 if (__first1 == __last1 || __first2 == __last2) 00489 return __first1; 00490 00491 // Test for a pattern of length 1. 00492 _ForwardIterator2 __tmp(__first2); 00493 ++__tmp; 00494 if (__tmp == __last2) 00495 return std::find(__first1, __last1, *__first2); 00496 00497 // General case. 00498 _ForwardIterator2 __p1, __p; 00499 __p1 = __first2; ++__p1; 00500 _ForwardIterator1 __current = __first1; 00501 00502 while (__first1 != __last1) 00503 { 00504 __first1 = std::find(__first1, __last1, *__first2); 00505 if (__first1 == __last1) 00506 return __last1; 00507 00508 __p = __p1; 00509 __current = __first1; 00510 if (++__current == __last1) 00511 return __last1; 00512 00513 while (*__current == *__p) 00514 { 00515 if (++__p == __last2) 00516 return __first1; 00517 if (++__current == __last1) 00518 return __last1; 00519 } 00520 ++__first1; 00521 } 00522 return __first1; 00523 } 00524 00525 /** 00526 * @brief Search a sequence for a matching sub-sequence using a predicate. 00527 * @param first1 A forward iterator. 00528 * @param last1 A forward iterator. 00529 * @param first2 A forward iterator. 00530 * @param last2 A forward iterator. 00531 * @param predicate A binary predicate. 00532 * @return The first iterator @c i in the range 00533 * @p [first1,last1-(last2-first2)) such that 00534 * @p predicate(*(i+N),*(first2+N)) is true for each @c N in the range 00535 * @p [0,last2-first2), or @p last1 if no such iterator exists. 00536 * 00537 * Searches the range @p [first1,last1) for a sub-sequence that compares 00538 * equal value-by-value with the sequence given by @p [first2,last2), 00539 * using @p predicate to determine equality, and returns an iterator 00540 * to the first element of the sub-sequence, or @p last1 if no such 00541 * iterator exists. 00542 * 00543 * @see search(_ForwardIter1, _ForwardIter1, _ForwardIter2, _ForwardIter2) 00544 */ 00545 template<typename _ForwardIterator1, typename _ForwardIterator2, 00546 typename _BinaryPredicate> 00547 _ForwardIterator1 00548 search(_ForwardIterator1 __first1, _ForwardIterator1 __last1, 00549 _ForwardIterator2 __first2, _ForwardIterator2 __last2, 00550 _BinaryPredicate __predicate) 00551 { 00552 // concept requirements 00553 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator1>) 00554 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator2>) 00555 __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate, 00556 typename iterator_traits<_ForwardIterator1>::value_type, 00557 typename iterator_traits<_ForwardIterator2>::value_type>) 00558 __glibcxx_requires_valid_range(__first1, __last1); 00559 __glibcxx_requires_valid_range(__first2, __last2); 00560 00561 // Test for empty ranges 00562 if (__first1 == __last1 || __first2 == __last2) 00563 return __first1; 00564 00565 // Test for a pattern of length 1. 00566 _ForwardIterator2 __tmp(__first2); 00567 ++__tmp; 00568 if (__tmp == __last2) 00569 { 00570 while (__first1 != __last1 && !__predicate(*__first1, *__first2)) 00571 ++__first1; 00572 return __first1; 00573 } 00574 00575 // General case. 00576 _ForwardIterator2 __p1, __p; 00577 __p1 = __first2; ++__p1; 00578 _ForwardIterator1 __current = __first1; 00579 00580 while (__first1 != __last1) 00581 { 00582 while (__first1 != __last1) 00583 { 00584 if (__predicate(*__first1, *__first2)) 00585 break; 00586 ++__first1; 00587 } 00588 while (__first1 != __last1 && !__predicate(*__first1, *__first2)) 00589 ++__first1; 00590 if (__first1 == __last1) 00591 return __last1; 00592 00593 __p = __p1; 00594 __current = __first1; 00595 if (++__current == __last1) 00596 return __last1; 00597 00598 while (__predicate(*__current, *__p)) 00599 { 00600 if (++__p == __last2) 00601 return __first1; 00602 if (++__current == __last1) 00603 return __last1; 00604 } 00605 ++__first1; 00606 } 00607 return __first1; 00608 } 00609 00610 /** 00611 * @brief Search a sequence for a number of consecutive values. 00612 * @param first A forward iterator. 00613 * @param last A forward iterator. 00614 * @param count The number of consecutive values. 00615 * @param val The value to find. 00616 * @return The first iterator @c i in the range @p [first,last-count) 00617 * such that @c *(i+N) == @p val for each @c N in the range @p [0,count), 00618 * or @p last if no such iterator exists. 00619 * 00620 * Searches the range @p [first,last) for @p count consecutive elements 00621 * equal to @p val. 00622 */ 00623 template<typename _ForwardIterator, typename _Integer, typename _Tp> 00624 _ForwardIterator 00625 search_n(_ForwardIterator __first, _ForwardIterator __last, 00626 _Integer __count, const _Tp& __val) 00627 { 00628 // concept requirements 00629 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) 00630 __glibcxx_function_requires(_EqualityComparableConcept< 00631 typename iterator_traits<_ForwardIterator>::value_type>) 00632 __glibcxx_function_requires(_EqualityComparableConcept<_Tp>) 00633 __glibcxx_requires_valid_range(__first, __last); 00634 00635 if (__count <= 0) 00636 return __first; 00637 else 00638 { 00639 __first = std::find(__first, __last, __val); 00640 while (__first != __last) 00641 { 00642 typename iterator_traits<_ForwardIterator>::difference_type 00643 __n = __count; 00644 _ForwardIterator __i = __first; 00645 ++__i; 00646 while (__i != __last && __n != 1 && *__i == __val) 00647 { 00648 ++__i; 00649 --__n; 00650 } 00651 if (__n == 1) 00652 return __first; 00653 else 00654 __first = std::find(__i, __last, __val); 00655 } 00656 return __last; 00657 } 00658 } 00659 00660 /** 00661 * @brief Search a sequence for a number of consecutive values using a 00662 * predicate. 00663 * @param first A forward iterator. 00664 * @param last A forward iterator. 00665 * @param count The number of consecutive values. 00666 * @param val The value to find. 00667 * @param binary_pred A binary predicate. 00668 * @return The first iterator @c i in the range @p [first,last-count) 00669 * such that @p binary_pred(*(i+N),val) is true for each @c N in the 00670 * range @p [0,count), or @p last if no such iterator exists. 00671 * 00672 * Searches the range @p [first,last) for @p count consecutive elements 00673 * for which the predicate returns true. 00674 */ 00675 template<typename _ForwardIterator, typename _Integer, typename _Tp, 00676 typename _BinaryPredicate> 00677 _ForwardIterator 00678 search_n(_ForwardIterator __first, _ForwardIterator __last, 00679 _Integer __count, const _Tp& __val, 00680 _BinaryPredicate __binary_pred) 00681 { 00682 // concept requirements 00683 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) 00684 __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate, 00685 typename iterator_traits<_ForwardIterator>::value_type, _Tp>) 00686 __glibcxx_requires_valid_range(__first, __last); 00687 00688 if (__count <= 0) 00689 return __first; 00690 else 00691 { 00692 while (__first != __last) 00693 { 00694 if (__binary_pred(*__first, __val)) 00695 break; 00696 ++__first; 00697 } 00698 while (__first != __last) 00699 { 00700 typename iterator_traits<_ForwardIterator>::difference_type 00701 __n = __count; 00702 _ForwardIterator __i = __first; 00703 ++__i; 00704 while (__i != __last && __n != 1 && __binary_pred(*__i, __val)) 00705 { 00706 ++__i; 00707 --__n; 00708 } 00709 if (__n == 1) 00710 return __first; 00711 else 00712 { 00713 while (__i != __last) 00714 { 00715 if (__binary_pred(*__i, __val)) 00716 break; 00717 ++__i; 00718 } 00719 __first = __i; 00720 } 00721 } 00722 return __last; 00723 } 00724 } 00725 00726 /** 00727 * @brief Swap the elements of two sequences. 00728 * @param first1 A forward iterator. 00729 * @param last1 A forward iterator. 00730 * @param first2 A forward iterator. 00731 * @return An iterator equal to @p first2+(last1-first1). 00732 * 00733 * Swaps each element in the range @p [first1,last1) with the 00734 * corresponding element in the range @p [first2,(last1-first1)). 00735 * The ranges must not overlap. 00736 */ 00737 template<typename _ForwardIterator1, typename _ForwardIterator2> 00738 _ForwardIterator2 00739 swap_ranges(_ForwardIterator1 __first1, _ForwardIterator1 __last1, 00740 _ForwardIterator2 __first2) 00741 { 00742 // concept requirements 00743 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept< 00744 _ForwardIterator1>) 00745 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept< 00746 _ForwardIterator2>) 00747 __glibcxx_function_requires(_ConvertibleConcept< 00748 typename iterator_traits<_ForwardIterator1>::value_type, 00749 typename iterator_traits<_ForwardIterator2>::value_type>) 00750 __glibcxx_function_requires(_ConvertibleConcept< 00751 typename iterator_traits<_ForwardIterator2>::value_type, 00752 typename iterator_traits<_ForwardIterator1>::value_type>) 00753 __glibcxx_requires_valid_range(__first1, __last1); 00754 00755 for ( ; __first1 != __last1; ++__first1, ++__first2) 00756 std::iter_swap(__first1, __first2); 00757 return __first2; 00758 } 00759 00760 /** 00761 * @brief Perform an operation on a sequence. 00762 * @param first An input iterator. 00763 * @param last An input iterator. 00764 * @param result An output iterator. 00765 * @param unary_op A unary operator. 00766 * @return An output iterator equal to @p result+(last-first). 00767 * 00768 * Applies the operator to each element in the input range and assigns 00769 * the results to successive elements of the output sequence. 00770 * Evaluates @p *(result+N)=unary_op(*(first+N)) for each @c N in the 00771 * range @p [0,last-first). 00772 * 00773 * @p unary_op must not alter its argument. 00774 */ 00775 template<typename _InputIterator, typename _OutputIterator, 00776 typename _UnaryOperation> 00777 _OutputIterator 00778 transform(_InputIterator __first, _InputIterator __last, 00779 _OutputIterator __result, _UnaryOperation __unary_op) 00780 { 00781 // concept requirements 00782 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) 00783 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, 00784 // "the type returned by a _UnaryOperation" 00785 __typeof__(__unary_op(*__first))>) 00786 __glibcxx_requires_valid_range(__first, __last); 00787 00788 for ( ; __first != __last; ++__first, ++__result) 00789 *__result = __unary_op(*__first); 00790 return __result; 00791 } 00792 00793 /** 00794 * @brief Perform an operation on corresponding elements of two sequences. 00795 * @param first1 An input iterator. 00796 * @param last1 An input iterator. 00797 * @param first2 An input iterator. 00798 * @param result An output iterator. 00799 * @param binary_op A binary operator. 00800 * @return An output iterator equal to @p result+(last-first). 00801 * 00802 * Applies the operator to the corresponding elements in the two 00803 * input ranges and assigns the results to successive elements of the 00804 * output sequence. 00805 * Evaluates @p *(result+N)=binary_op(*(first1+N),*(first2+N)) for each 00806 * @c N in the range @p [0,last1-first1). 00807 * 00808 * @p binary_op must not alter either of its arguments. 00809 */ 00810 template<typename _InputIterator1, typename _InputIterator2, 00811 typename _OutputIterator, typename _BinaryOperation> 00812 _OutputIterator 00813 transform(_InputIterator1 __first1, _InputIterator1 __last1, 00814 _InputIterator2 __first2, _OutputIterator __result, 00815 _BinaryOperation __binary_op) 00816 { 00817 // concept requirements 00818 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>) 00819 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>) 00820 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, 00821 // "the type returned by a _BinaryOperation" 00822 __typeof__(__binary_op(*__first1,*__first2))>) 00823 __glibcxx_requires_valid_range(__first1, __last1); 00824 00825 for ( ; __first1 != __last1; ++__first1, ++__first2, ++__result) 00826 *__result = __binary_op(*__first1, *__first2); 00827 return __result; 00828 } 00829 00830 /** 00831 * @brief Replace each occurrence of one value in a sequence with another 00832 * value. 00833 * @param first A forward iterator. 00834 * @param last A forward iterator. 00835 * @param old_value The value to be replaced. 00836 * @param new_value The replacement value. 00837 * @return replace() returns no value. 00838 * 00839 * For each iterator @c i in the range @p [first,last) if @c *i == 00840 * @p old_value then the assignment @c *i = @p new_value is performed. 00841 */ 00842 template<typename _ForwardIterator, typename _Tp> 00843 void 00844 replace(_ForwardIterator __first, _ForwardIterator __last, 00845 const _Tp& __old_value, const _Tp& __new_value) 00846 { 00847 // concept requirements 00848 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept< 00849 _ForwardIterator>) 00850 __glibcxx_function_requires(_EqualOpConcept< 00851 typename iterator_traits<_ForwardIterator>::value_type, _Tp>) 00852 __glibcxx_function_requires(_ConvertibleConcept<_Tp, 00853 typename iterator_traits<_ForwardIterator>::value_type>) 00854 __glibcxx_requires_valid_range(__first, __last); 00855 00856 for ( ; __first != __last; ++__first) 00857 if (*__first == __old_value) 00858 *__first = __new_value; 00859 } 00860 00861 /** 00862 * @brief Replace each value in a sequence for which a predicate returns 00863 * true with another value. 00864 * @param first A forward iterator. 00865 * @param last A forward iterator. 00866 * @param pred A predicate. 00867 * @param new_value The replacement value. 00868 * @return replace_if() returns no value. 00869 * 00870 * For each iterator @c i in the range @p [first,last) if @p pred(*i) 00871 * is true then the assignment @c *i = @p new_value is performed. 00872 */ 00873 template<typename _ForwardIterator, typename _Predicate, typename _Tp> 00874 void 00875 replace_if(_ForwardIterator __first, _ForwardIterator __last, 00876 _Predicate __pred, const _Tp& __new_value) 00877 { 00878 // concept requirements 00879 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept< 00880 _ForwardIterator>) 00881 __glibcxx_function_requires(_ConvertibleConcept<_Tp, 00882 typename iterator_traits<_ForwardIterator>::value_type>) 00883 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate, 00884 typename iterator_traits<_ForwardIterator>::value_type>) 00885 __glibcxx_requires_valid_range(__first, __last); 00886 00887 for ( ; __first != __last; ++__first) 00888 if (__pred(*__first)) 00889 *__first = __new_value; 00890 } 00891 00892 /** 00893 * @brief Copy a sequence, replacing each element of one value with another 00894 * value. 00895 * @param first An input iterator. 00896 * @param last An input iterator. 00897 * @param result An output iterator. 00898 * @param old_value The value to be replaced. 00899 * @param new_value The replacement value. 00900 * @return The end of the output sequence, @p result+(last-first). 00901 * 00902 * Copies each element in the input range @p [first,last) to the 00903 * output range @p [result,result+(last-first)) replacing elements 00904 * equal to @p old_value with @p new_value. 00905 */ 00906 template<typename _InputIterator, typename _OutputIterator, typename _Tp> 00907 _OutputIterator 00908 replace_copy(_InputIterator __first, _InputIterator __last, 00909 _OutputIterator __result, 00910 const _Tp& __old_value, const _Tp& __new_value) 00911 { 00912 // concept requirements 00913 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) 00914 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, 00915 typename iterator_traits<_InputIterator>::value_type>) 00916 __glibcxx_function_requires(_EqualOpConcept< 00917 typename iterator_traits<_InputIterator>::value_type, _Tp>) 00918 __glibcxx_requires_valid_range(__first, __last); 00919 00920 for ( ; __first != __last; ++__first, ++__result) 00921 *__result = *__first == __old_value ? __new_value : *__first; 00922 return __result; 00923 } 00924 00925 /** 00926 * @brief Copy a sequence, replacing each value for which a predicate 00927 * returns true with another value. 00928 * @param first An input iterator. 00929 * @param last An input iterator. 00930 * @param result An output iterator. 00931 * @param pred A predicate. 00932 * @param new_value The replacement value. 00933 * @return The end of the output sequence, @p result+(last-first). 00934 * 00935 * Copies each element in the range @p [first,last) to the range 00936 * @p [result,result+(last-first)) replacing elements for which 00937 * @p pred returns true with @p new_value. 00938 */ 00939 template<typename _InputIterator, typename _OutputIterator, 00940 typename _Predicate, typename _Tp> 00941 _OutputIterator 00942 replace_copy_if(_InputIterator __first, _InputIterator __last, 00943 _OutputIterator __result, 00944 _Predicate __pred, const _Tp& __new_value) 00945 { 00946 // concept requirements 00947 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) 00948 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, 00949 typename iterator_traits<_InputIterator>::value_type>) 00950 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate, 00951 typename iterator_traits<_InputIterator>::value_type>) 00952 __glibcxx_requires_valid_range(__first, __last); 00953 00954 for ( ; __first != __last; ++__first, ++__result) 00955 *__result = __pred(*__first) ? __new_value : *__first; 00956 return __result; 00957 } 00958 00959 /** 00960 * @brief Assign the result of a function object to each value in a 00961 * sequence. 00962 * @param first A forward iterator. 00963 * @param last A forward iterator. 00964 * @param gen A function object taking no arguments. 00965 * @return generate() returns no value. 00966 * 00967 * Performs the assignment @c *i = @p gen() for each @c i in the range 00968 * @p [first,last). 00969 */ 00970 template<typename _ForwardIterator, typename _Generator> 00971 void 00972 generate(_ForwardIterator __first, _ForwardIterator __last, 00973 _Generator __gen) 00974 { 00975 // concept requirements 00976 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) 00977 __glibcxx_function_requires(_GeneratorConcept<_Generator, 00978 typename iterator_traits<_ForwardIterator>::value_type>) 00979 __glibcxx_requires_valid_range(__first, __last); 00980 00981 for ( ; __first != __last; ++__first) 00982 *__first = __gen(); 00983 } 00984 00985 /** 00986 * @brief Assign the result of a function object to each value in a 00987 * sequence. 00988 * @param first A forward iterator. 00989 * @param n The length of the sequence. 00990 * @param gen A function object taking no arguments. 00991 * @return The end of the sequence, @p first+n 00992 * 00993 * Performs the assignment @c *i = @p gen() for each @c i in the range 00994 * @p [first,first+n). 00995 */ 00996 template<typename _OutputIterator, typename _Size, typename _Generator> 00997 _OutputIterator 00998 generate_n(_OutputIterator __first, _Size __n, _Generator __gen) 00999 { 01000 // concept requirements 01001 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, 01002 // "the type returned by a _Generator" 01003 __typeof__(__gen())>) 01004 01005 for ( ; __n > 0; --__n, ++__first) 01006 *__first = __gen(); 01007 return __first; 01008 } 01009 01010 /** 01011 * @brief Copy a sequence, removing elements of a given value. 01012 * @param first An input iterator. 01013 * @param last An input iterator. 01014 * @param result An output iterator. 01015 * @param value The value to be removed. 01016 * @return An iterator designating the end of the resulting sequence. 01017 * 01018 * Copies each element in the range @p [first,last) not equal to @p value 01019 * to the range beginning at @p result. 01020 * remove_copy() is stable, so the relative order of elements that are 01021 * copied is unchanged. 01022 */ 01023 template<typename _InputIterator, typename _OutputIterator, typename _Tp> 01024 _OutputIterator 01025 remove_copy(_InputIterator __first, _InputIterator __last, 01026 _OutputIterator __result, const _Tp& __value) 01027 { 01028 // concept requirements 01029 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) 01030 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, 01031 typename iterator_traits<_InputIterator>::value_type>) 01032 __glibcxx_function_requires(_EqualOpConcept< 01033 typename iterator_traits<_InputIterator>::value_type, _Tp>) 01034 __glibcxx_requires_valid_range(__first, __last); 01035 01036 for ( ; __first != __last; ++__first) 01037 if (!(*__first == __value)) 01038 { 01039 *__result = *__first; 01040 ++__result; 01041 } 01042 return __result; 01043 } 01044 01045 /** 01046 * @brief Copy a sequence, removing elements for which a predicate is true. 01047 * @param first An input iterator. 01048 * @param last An input iterator. 01049 * @param result An output iterator. 01050 * @param pred A predicate. 01051 * @return An iterator designating the end of the resulting sequence. 01052 * 01053 * Copies each element in the range @p [first,last) for which 01054 * @p pred returns true to the range beginning at @p result. 01055 * 01056 * remove_copy_if() is stable, so the relative order of elements that are 01057 * copied is unchanged. 01058 */ 01059 template<typename _InputIterator, typename _OutputIterator, 01060 typename _Predicate> 01061 _OutputIterator 01062 remove_copy_if(_InputIterator __first, _InputIterator __last, 01063 _OutputIterator __result, _Predicate __pred) 01064 { 01065 // concept requirements 01066 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) 01067 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, 01068 typename iterator_traits<_InputIterator>::value_type>) 01069 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate, 01070 typename iterator_traits<_InputIterator>::value_type>) 01071 __glibcxx_requires_valid_range(__first, __last); 01072 01073 for ( ; __first != __last; ++__first) 01074 if (!__pred(*__first)) 01075 { 01076 *__result = *__first; 01077 ++__result; 01078 } 01079 return __result; 01080 } 01081 01082 /** 01083 * @brief Remove elements from a sequence. 01084 * @param first An input iterator. 01085 * @param last An input iterator. 01086 * @param value The value to be removed. 01087 * @return An iterator designating the end of the resulting sequence. 01088 * 01089 * All elements equal to @p value are removed from the range 01090 * @p [first,last). 01091 * 01092 * remove() is stable, so the relative order of elements that are 01093 * not removed is unchanged. 01094 * 01095 * Elements between the end of the resulting sequence and @p last 01096 * are still present, but their value is unspecified. 01097 */ 01098 template<typename _ForwardIterator, typename _Tp> 01099 _ForwardIterator 01100 remove(_ForwardIterator __first, _ForwardIterator __last, 01101 const _Tp& __value) 01102 { 01103 // concept requirements 01104 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept< 01105 _ForwardIterator>) 01106 __glibcxx_function_requires(_ConvertibleConcept<_Tp, 01107 typename iterator_traits<_ForwardIterator>::value_type>) 01108 __glibcxx_function_requires(_EqualOpConcept< 01109 typename iterator_traits<_ForwardIterator>::value_type, _Tp>) 01110 __glibcxx_requires_valid_range(__first, __last); 01111 01112 __first = std::find(__first, __last, __value); 01113 _ForwardIterator __i = __first; 01114 return __first == __last ? __first 01115 : std::remove_copy(++__i, __last, 01116 __first, __value); 01117 } 01118 01119 /** 01120 * @brief Remove elements from a sequence using a predicate. 01121 * @param first A forward iterator. 01122 * @param last A forward iterator. 01123 * @param pred A predicate. 01124 * @return An iterator designating the end of the resulting sequence. 01125 * 01126 * All elements for which @p pred returns true are removed from the range 01127 * @p [first,last). 01128 * 01129 * remove_if() is stable, so the relative order of elements that are 01130 * not removed is unchanged. 01131 * 01132 * Elements between the end of the resulting sequence and @p last 01133 * are still present, but their value is unspecified. 01134 */ 01135 template<typename _ForwardIterator, typename _Predicate> 01136 _ForwardIterator 01137 remove_if(_ForwardIterator __first, _ForwardIterator __last, 01138 _Predicate __pred) 01139 { 01140 // concept requirements 01141 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept< 01142 _ForwardIterator>) 01143 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate, 01144 typename iterator_traits<_ForwardIterator>::value_type>) 01145 __glibcxx_requires_valid_range(__first, __last); 01146 01147 __first = std::find_if(__first, __last, __pred); 01148 _ForwardIterator __i = __first; 01149 return __first == __last ? __first 01150 : std::remove_copy_if(++__i, __last, 01151 __first, __pred); 01152 } 01153 01154 /** 01155 * @if maint 01156 * This is an uglified unique_copy(_InputIterator, _InputIterator, 01157 * _OutputIterator) 01158 * overloaded for output iterators. 01159 * @endif 01160 */ 01161 template<typename _InputIterator, typename _OutputIterator> 01162 _OutputIterator 01163 __unique_copy(_InputIterator __first, _InputIterator __last, 01164 _OutputIterator __result, 01165 output_iterator_tag) 01166 { 01167 // concept requirements -- taken care of in dispatching function 01168 typename iterator_traits<_InputIterator>::value_type __value = *__first; 01169 *__result = __value; 01170 while (++__first != __last) 01171 if (!(__value == *__first)) 01172 { 01173 __value = *__first; 01174 *++__result = __value; 01175 } 01176 return ++__result; 01177 } 01178 01179 /** 01180 * @if maint 01181 * This is an uglified unique_copy(_InputIterator, _InputIterator, 01182 * _OutputIterator) 01183 * overloaded for forward iterators. 01184 * @endif 01185 */ 01186 template<typename _InputIterator, typename _ForwardIterator> 01187 _ForwardIterator 01188 __unique_copy(_InputIterator __first, _InputIterator __last, 01189 _ForwardIterator __result, 01190 forward_iterator_tag) 01191 { 01192 // concept requirements -- taken care of in dispatching function 01193 *__result = *__first; 01194 while (++__first != __last) 01195 if (!(*__result == *__first)) 01196 *++__result = *__first; 01197 return ++__result; 01198 } 01199 01200 /** 01201 * @if maint 01202 * This is an uglified 01203 * unique_copy(_InputIterator, _InputIterator, _OutputIterator, 01204 * _BinaryPredicate) 01205 * overloaded for output iterators. 01206 * @endif 01207 */ 01208 template<typename _InputIterator, typename _OutputIterator, 01209 typename _BinaryPredicate> 01210 _OutputIterator 01211 __unique_copy(_InputIterator __first, _InputIterator __last, 01212 _OutputIterator __result, 01213 _BinaryPredicate __binary_pred, 01214 output_iterator_tag) 01215 { 01216 // concept requirements -- iterators already checked 01217 __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate, 01218 typename iterator_traits<_InputIterator>::value_type, 01219 typename iterator_traits<_InputIterator>::value_type>) 01220 01221 typename iterator_traits<_InputIterator>::value_type __value = *__first; 01222 *__result = __value; 01223 while (++__first != __last) 01224 if (!__binary_pred(__value, *__first)) 01225 { 01226 __value = *__first; 01227 *++__result = __value; 01228 } 01229 return ++__result; 01230 } 01231 01232 /** 01233 * @if maint 01234 * This is an uglified 01235 * unique_copy(_InputIterator, _InputIterator, _OutputIterator, 01236 * _BinaryPredicate) 01237 * overloaded for forward iterators. 01238 * @endif 01239 */ 01240 template<typename _InputIterator, typename _ForwardIterator, 01241 typename _BinaryPredicate> 01242 _ForwardIterator 01243 __unique_copy(_InputIterator __first, _InputIterator __last, 01244 _ForwardIterator __result, 01245 _BinaryPredicate __binary_pred, 01246 forward_iterator_tag) 01247 { 01248 // concept requirements -- iterators already checked 01249 __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate, 01250 typename iterator_traits<_ForwardIterator>::value_type, 01251 typename iterator_traits<_InputIterator>::value_type>) 01252 01253 *__result = *__first; 01254 while (++__first != __last) 01255 if (!__binary_pred(*__result, *__first)) *++__result = *__first; 01256 return ++__result; 01257 } 01258 01259 /** 01260 * @brief Copy a sequence, removing consecutive duplicate values. 01261 * @param first An input iterator. 01262 * @param last An input iterator. 01263 * @param result An output iterator. 01264 * @return An iterator designating the end of the resulting sequence. 01265 * 01266 * Copies each element in the range @p [first,last) to the range 01267 * beginning at @p result, except that only the first element is copied 01268 * from groups of consecutive elements that compare equal. 01269 * unique_copy() is stable, so the relative order of elements that are 01270 * copied is unchanged. 01271 */ 01272 template<typename _InputIterator, typename _OutputIterator> 01273 inline _OutputIterator 01274 unique_copy(_InputIterator __first, _InputIterator __last, 01275 _OutputIterator __result) 01276 { 01277 // concept requirements 01278 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) 01279 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, 01280 typename iterator_traits<_InputIterator>::value_type>) 01281 __glibcxx_function_requires(_EqualityComparableConcept< 01282 typename iterator_traits<_InputIterator>::value_type>) 01283 __glibcxx_requires_valid_range(__first, __last); 01284 01285 typedef typename iterator_traits<_OutputIterator>::iterator_category 01286 _IterType; 01287 01288 if (__first == __last) return __result; 01289 return std::__unique_copy(__first, __last, __result, _IterType()); 01290 } 01291 01292 /** 01293 * @brief Copy a sequence, removing consecutive values using a predicate. 01294 * @param first An input iterator. 01295 * @param last An input iterator. 01296 * @param result An output iterator. 01297 * @param binary_pred A binary predicate. 01298 * @return An iterator designating the end of the resulting sequence. 01299 * 01300 * Copies each element in the range @p [first,last) to the range 01301 * beginning at @p result, except that only the first element is copied 01302 * from groups of consecutive elements for which @p binary_pred returns 01303 * true. 01304 * unique_copy() is stable, so the relative order of elements that are 01305 * copied is unchanged. 01306 */ 01307 template<typename _InputIterator, typename _OutputIterator, 01308 typename _BinaryPredicate> 01309 inline _OutputIterator 01310 unique_copy(_InputIterator __first, _InputIterator __last, 01311 _OutputIterator __result, 01312 _BinaryPredicate __binary_pred) 01313 { 01314 // concept requirements -- predicates checked later 01315 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) 01316 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, 01317 typename iterator_traits<_InputIterator>::value_type>) 01318 __glibcxx_requires_valid_range(__first, __last); 01319 01320 typedef typename iterator_traits<_OutputIterator>::iterator_category 01321 _IterType; 01322 01323 if (__first == __last) return __result; 01324 return std::__unique_copy(__first, __last, __result, 01325 __binary_pred, _IterType()); 01326 } 01327 01328 /** 01329 * @brief Remove consecutive duplicate values from a sequence. 01330 * @param first A forward iterator. 01331 * @param last A forward iterator. 01332 * @return An iterator designating the end of the resulting sequence. 01333 * 01334 * Removes all but the first element from each group of consecutive 01335 * values that compare equal. 01336 * unique() is stable, so the relative order of elements that are 01337 * not removed is unchanged. 01338 * Elements between the end of the resulting sequence and @p last 01339 * are still present, but their value is unspecified. 01340 */ 01341 template<typename _ForwardIterator> 01342 _ForwardIterator 01343 unique(_ForwardIterator __first, _ForwardIterator __last) 01344 { 01345 // concept requirements 01346 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept< 01347 _ForwardIterator>) 01348 __glibcxx_function_requires(_EqualityComparableConcept< 01349 typename iterator_traits<_ForwardIterator>::value_type>) 01350 __glibcxx_requires_valid_range(__first, __last); 01351 01352 // Skip the beginning, if already unique. 01353 __first = std::adjacent_find(__first, __last); 01354 if (__first == __last) 01355 return __last; 01356 01357 // Do the real copy work. 01358 _ForwardIterator __dest = __first; 01359 ++__first; 01360 while (++__first != __last) 01361 if (!(*__dest == *__first)) 01362 *++__dest = *__first; 01363 return ++__dest; 01364 } 01365 01366 /** 01367 * @brief Remove consecutive values from a sequence using a predicate. 01368 * @param first A forward iterator. 01369 * @param last A forward iterator. 01370 * @param binary_pred A binary predicate. 01371 * @return An iterator designating the end of the resulting sequence. 01372 * 01373 * Removes all but the first element from each group of consecutive 01374 * values for which @p binary_pred returns true. 01375 * unique() is stable, so the relative order of elements that are 01376 * not removed is unchanged. 01377 * Elements between the end of the resulting sequence and @p last 01378 * are still present, but their value is unspecified. 01379 */ 01380 template<typename _ForwardIterator, typename _BinaryPredicate> 01381 _ForwardIterator 01382 unique(_ForwardIterator __first, _ForwardIterator __last, 01383 _BinaryPredicate __binary_pred) 01384 { 01385 // concept requirements 01386 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept< 01387 _ForwardIterator>) 01388 __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate, 01389 typename iterator_traits<_ForwardIterator>::value_type, 01390 typename iterator_traits<_ForwardIterator>::value_type>) 01391 __glibcxx_requires_valid_range(__first, __last); 01392 01393 // Skip the beginning, if already unique. 01394 __first = std::adjacent_find(__first, __last, __binary_pred); 01395 if (__first == __last) 01396 return __last; 01397 01398 // Do the real copy work. 01399 _ForwardIterator __dest = __first; 01400 ++__first; 01401 while (++__first != __last) 01402 if (!__binary_pred(*__dest, *__first)) 01403 *++__dest = *__first; 01404 return ++__dest; 01405 } 01406 01407 /** 01408 * @if maint 01409 * This is an uglified reverse(_BidirectionalIterator, 01410 * _BidirectionalIterator) 01411 * overloaded for bidirectional iterators. 01412 * @endif 01413 */ 01414 template<typename _BidirectionalIterator> 01415 void 01416 __reverse(_BidirectionalIterator __first, _BidirectionalIterator __last, 01417 bidirectional_iterator_tag) 01418 { 01419 while (true) 01420 if (__first == __last || __first == --__last) 01421 return; 01422 else 01423 std::iter_swap(__first++, __last); 01424 } 01425 01426 /** 01427 * @if maint 01428 * This is an uglified reverse(_BidirectionalIterator, 01429 * _BidirectionalIterator) 01430 * overloaded for bidirectional iterators. 01431 * @endif 01432 */ 01433 template<typename _RandomAccessIterator> 01434 void 01435 __reverse(_RandomAccessIterator __first, _RandomAccessIterator __last, 01436 random_access_iterator_tag) 01437 { 01438 while (__first < __last) 01439 std::iter_swap(__first++, --__last); 01440 } 01441 01442 /** 01443 * @brief Reverse a sequence. 01444 * @param first A bidirectional iterator. 01445 * @param last A bidirectional iterator. 01446 * @return reverse() returns no value. 01447 * 01448 * Reverses the order of the elements in the range @p [first,last), 01449 * so that the first element becomes the last etc. 01450 * For every @c i such that @p 0<=i<=(last-first)/2), @p reverse() 01451 * swaps @p *(first+i) and @p *(last-(i+1)) 01452 */ 01453 template<typename _BidirectionalIterator> 01454 inline void 01455 reverse(_BidirectionalIterator __first, _BidirectionalIterator __last) 01456 { 01457 // concept requirements 01458 __glibcxx_function_requires(_Mutable_BidirectionalIteratorConcept< 01459 _BidirectionalIterator>) 01460 __glibcxx_requires_valid_range(__first, __last); 01461 std::__reverse(__first, __last, std::__iterator_category(__first)); 01462 } 01463 01464 /** 01465 * @brief Copy a sequence, reversing its elements. 01466 * @param first A bidirectional iterator. 01467 * @param last A bidirectional iterator. 01468 * @param result An output iterator. 01469 * @return An iterator designating the end of the resulting sequence. 01470 * 01471 * Copies the elements in the range @p [first,last) to the range 01472 * @p [result,result+(last-first)) such that the order of the 01473 * elements is reversed. 01474 * For every @c i such that @p 0<=i<=(last-first), @p reverse_copy() 01475 * performs the assignment @p *(result+(last-first)-i) = *(first+i). 01476 * The ranges @p [first,last) and @p [result,result+(last-first)) 01477 * must not overlap. 01478 */ 01479 template<typename _BidirectionalIterator, typename _OutputIterator> 01480 _OutputIterator 01481 reverse_copy(_BidirectionalIterator __first, _BidirectionalIterator __last, 01482 _OutputIterator __result) 01483 { 01484 // concept requirements 01485 __glibcxx_function_requires(_BidirectionalIteratorConcept< 01486 _BidirectionalIterator>) 01487 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, 01488 typename iterator_traits<_BidirectionalIterator>::value_type>) 01489 __glibcxx_requires_valid_range(__first, __last); 01490 01491 while (__first != __last) 01492 { 01493 --__last; 01494 *__result = *__last; 01495 ++__result; 01496 } 01497 return __result; 01498 } 01499 01500 01501 /** 01502 * @if maint 01503 * This is a helper function for the rotate algorithm specialized on RAIs. 01504 * It returns the greatest common divisor of two integer values. 01505 * @endif 01506 */ 01507 template<typename _EuclideanRingElement> 01508 _EuclideanRingElement 01509 __gcd(_EuclideanRingElement __m, _EuclideanRingElement __n) 01510 { 01511 while (__n != 0) 01512 { 01513 _EuclideanRingElement __t = __m % __n; 01514 __m = __n; 01515 __n = __t; 01516 } 01517 return __m; 01518 } 01519 01520 /** 01521 * @if maint 01522 * This is a helper function for the rotate algorithm. 01523 * @endif 01524 */ 01525 template<typename _ForwardIterator> 01526 void 01527 __rotate(_ForwardIterator __first, 01528 _ForwardIterator __middle, 01529 _ForwardIterator __last, 01530 forward_iterator_tag) 01531 { 01532 if ((__first == __middle) || (__last == __middle)) 01533 return; 01534 01535 _ForwardIterator __first2 = __middle; 01536 do 01537 { 01538 swap(*__first++, *__first2++); 01539 if (__first == __middle) 01540 __middle = __first2; 01541 } 01542 while (__first2 != __last); 01543 01544 __first2 = __middle; 01545 01546 while (__first2 != __last) 01547 { 01548 swap(*__first++, *__first2++); 01549 if (__first == __middle) 01550 __middle = __first2; 01551 else if (__first2 == __last) 01552 __first2 = __middle; 01553 } 01554 } 01555 01556 /** 01557 * @if maint 01558 * This is a helper function for the rotate algorithm. 01559 * @endif 01560 */ 01561 template<typename _BidirectionalIterator> 01562 void 01563 __rotate(_BidirectionalIterator __first, 01564 _BidirectionalIterator __middle, 01565 _BidirectionalIterator __last, 01566 bidirectional_iterator_tag) 01567 { 01568 // concept requirements 01569 __glibcxx_function_requires(_Mutable_BidirectionalIteratorConcept< 01570 _BidirectionalIterator>) 01571 01572 if ((__first == __middle) || (__last == __middle)) 01573 return; 01574 01575 std::__reverse(__first, __middle, bidirectional_iterator_tag()); 01576 std::__reverse(__middle, __last, bidirectional_iterator_tag()); 01577 01578 while (__first != __middle && __middle != __last) 01579 swap(*__first++, *--__last); 01580 01581 if (__first == __middle) 01582 std::__reverse(__middle, __last, bidirectional_iterator_tag()); 01583 else 01584 std::__reverse(__first, __middle, bidirectional_iterator_tag()); 01585 } 01586 01587 /** 01588 * @if maint 01589 * This is a helper function for the rotate algorithm. 01590 * @endif 01591 */ 01592 template<typename _RandomAccessIterator> 01593 void 01594 __rotate(_RandomAccessIterator __first, 01595 _RandomAccessIterator __middle, 01596 _RandomAccessIterator __last, 01597 random_access_iterator_tag) 01598 { 01599 // concept requirements 01600 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept< 01601 _RandomAccessIterator>) 01602 01603 if ((__first == __middle) || (__last == __middle)) 01604 return; 01605 01606 typedef typename iterator_traits<_RandomAccessIterator>::difference_type 01607 _Distance; 01608 typedef typename iterator_traits<_RandomAccessIterator>::value_type 01609 _ValueType; 01610 01611 const _Distance __n = __last - __first; 01612 const _Distance __k = __middle - __first; 01613 const _Distance __l = __n - __k; 01614 01615 if (__k == __l) 01616 { 01617 std::swap_ranges(__first, __middle, __middle); 01618 return; 01619 } 01620 01621 const _Distance __d = __gcd(__n, __k); 01622 01623 for (_Distance __i = 0; __i < __d; __i++) 01624 { 01625 const _ValueType __tmp = *__first; 01626 _RandomAccessIterator __p = __first; 01627 01628 if (__k < __l) 01629 { 01630 for (_Distance __j = 0; __j < __l / __d; __j++) 01631 { 01632 if (__p > __first + __l) 01633 { 01634 *__p = *(__p - __l); 01635 __p -= __l; 01636 } 01637 01638 *__p = *(__p + __k); 01639 __p += __k; 01640 } 01641 } 01642 else 01643 { 01644 for (_Distance __j = 0; __j < __k / __d - 1; __j ++) 01645 { 01646 if (__p < __last - __k) 01647 { 01648 *__p = *(__p + __k); 01649 __p += __k; 01650 } 01651 *__p = * (__p - __l); 01652 __p -= __l; 01653 } 01654 } 01655 01656 *__p = __tmp; 01657 ++__first; 01658 } 01659 } 01660 01661 /** 01662 * @brief Rotate the elements of a sequence. 01663 * @param first A forward iterator. 01664 * @param middle A forward iterator. 01665 * @param last A forward iterator. 01666 * @return Nothing. 01667 * 01668 * Rotates the elements of the range @p [first,last) by @p (middle-first) 01669 * positions so that the element at @p middle is moved to @p first, the 01670 * element at @p middle+1 is moved to @first+1 and so on for each element 01671 * in the range @p [first,last). 01672 * 01673 * This effectively swaps the ranges @p [first,middle) and 01674 * @p [middle,last). 01675 * 01676 * Performs @p *(first+(n+(last-middle))%(last-first))=*(first+n) for 01677 * each @p n in the range @p [0,last-first). 01678 */ 01679 template<typename _ForwardIterator> 01680 inline void 01681 rotate(_ForwardIterator __first, _ForwardIterator __middle, 01682 _ForwardIterator __last) 01683 { 01684 // concept requirements 01685 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept< 01686 _ForwardIterator>) 01687 __glibcxx_requires_valid_range(__first, __middle); 01688 __glibcxx_requires_valid_range(__middle, __last); 01689 01690 typedef typename iterator_traits<_ForwardIterator>::iterator_category 01691 _IterType; 01692 std::__rotate(__first, __middle, __last, _IterType()); 01693 } 01694 01695 /** 01696 * @brief Copy a sequence, rotating its elements. 01697 * @param first A forward iterator. 01698 * @param middle A forward iterator. 01699 * @param last A forward iterator. 01700 * @param result An output iterator. 01701 * @return An iterator designating the end of the resulting sequence. 01702 * 01703 * Copies the elements of the range @p [first,last) to the range 01704 * beginning at @result, rotating the copied elements by @p (middle-first) 01705 * positions so that the element at @p middle is moved to @p result, the 01706 * element at @p middle+1 is moved to @result+1 and so on for each element 01707 * in the range @p [first,last). 01708 * 01709 * Performs @p *(result+(n+(last-middle))%(last-first))=*(first+n) for 01710 * each @p n in the range @p [0,last-first). 01711 */ 01712 template<typename _ForwardIterator, typename _OutputIterator> 01713 _OutputIterator 01714 rotate_copy(_ForwardIterator __first, _ForwardIterator __middle, 01715 _ForwardIterator __last, _OutputIterator __result) 01716 { 01717 // concept requirements 01718 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) 01719 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, 01720 typename iterator_traits<_ForwardIterator>::value_type>) 01721 __glibcxx_requires_valid_range(__first, __middle); 01722 __glibcxx_requires_valid_range(__middle, __last); 01723 01724 return std::copy(__first, __middle, copy(__middle, __last, __result)); 01725 } 01726 01727 /** 01728 * @brief Randomly shuffle the elements of a sequence. 01729 * @param first A forward iterator. 01730 * @param last A forward iterator. 01731 * @return Nothing. 01732 * 01733 * Reorder the elements in the range @p [first,last) using a random 01734 * distribution, so that every possible ordering of the sequence is 01735 * equally likely. 01736 */ 01737 template<typename _RandomAccessIterator> 01738 inline void 01739 random_shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last) 01740 { 01741 // concept requirements 01742 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept< 01743 _RandomAccessIterator>) 01744 __glibcxx_requires_valid_range(__first, __last); 01745 01746 if (__first != __last) 01747 for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i) 01748 std::iter_swap(__i, __first + (std::rand() % ((__i - __first) + 1))); 01749 } 01750 01751 /** 01752 * @brief Shuffle the elements of a sequence using a random number 01753 * generator. 01754 * @param first A forward iterator. 01755 * @param last A forward iterator. 01756 * @param rand The RNG functor or function. 01757 * @return Nothing. 01758 * 01759 * Reorders the elements in the range @p [first,last) using @p rand to 01760 * provide a random distribution. Calling @p rand(N) for a positive 01761 * integer @p N should return a randomly chosen integer from the 01762 * range [0,N). 01763 */ 01764 template<typename _RandomAccessIterator, typename _RandomNumberGenerator> 01765 void 01766 random_shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last, 01767 _RandomNumberGenerator& __rand) 01768 { 01769 // concept requirements 01770 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept< 01771 _RandomAccessIterator>) 01772 __glibcxx_requires_valid_range(__first, __last); 01773 01774 if (__first == __last) 01775 return; 01776 for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i) 01777 std::iter_swap(__i, __first + __rand((__i - __first) + 1)); 01778 } 01779 01780 01781 /** 01782 * @if maint 01783 * This is a helper function... 01784 * @endif 01785 */ 01786 template<typename _ForwardIterator, typename _Predicate> 01787 _ForwardIterator 01788 __partition(_ForwardIterator __first, _ForwardIterator __last, 01789 _Predicate __pred, 01790 forward_iterator_tag) 01791 { 01792 if (__first == __last) 01793 return __first; 01794 01795 while (__pred(*__first)) 01796 if (++__first == __last) 01797 return __first; 01798 01799 _ForwardIterator __next = __first; 01800 01801 while (++__next != __last) 01802 if (__pred(*__next)) 01803 { 01804 swap(*__first, *__next); 01805 ++__first; 01806 } 01807 01808 return __first; 01809 } 01810 01811 /** 01812 * @if maint 01813 * This is a helper function... 01814 * @endif 01815 */ 01816 template<typename _BidirectionalIterator, typename _Predicate> 01817 _BidirectionalIterator 01818 __partition(_BidirectionalIterator __first, _BidirectionalIterator __last, 01819 _Predicate __pred, 01820 bidirectional_iterator_tag) 01821 { 01822 while (true) 01823 { 01824 while (true) 01825 if (__first == __last) 01826 return __first; 01827 else if (__pred(*__first)) 01828 ++__first; 01829 else 01830 break; 01831 --__last; 01832 while (true) 01833 if (__first == __last) 01834 return __first; 01835 else if (!__pred(*__last)) 01836 --__last; 01837 else 01838 break; 01839 std::iter_swap(__first, __last); 01840 ++__first; 01841 } 01842 } 01843 01844 /** 01845 * @brief Move elements for which a predicate is true to the beginning 01846 * of a sequence. 01847 * @param first A forward iterator. 01848 * @param last A forward iterator. 01849 * @param pred A predicate functor. 01850 * @return An iterator @p middle such that @p pred(i) is true for each 01851 * iterator @p i in the range @p [first,middle) and false for each @p i 01852 * in the range @p [middle,last). 01853 * 01854 * @p pred must not modify its operand. @p partition() does not preserve 01855 * the relative ordering of elements in each group, use 01856 * @p stable_partition() if this is needed. 01857 */ 01858 template<typename _ForwardIterator, typename _Predicate> 01859 inline _ForwardIterator 01860 partition(_ForwardIterator __first, _ForwardIterator __last, 01861 _Predicate __pred) 01862 { 01863 // concept requirements 01864 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept< 01865 _ForwardIterator>) 01866 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate, 01867 typename iterator_traits<_ForwardIterator>::value_type>) 01868 __glibcxx_requires_valid_range(__first, __last); 01869 01870 return std::__partition(__first, __last, __pred, 01871 std::__iterator_category(__first)); 01872 } 01873 01874 01875 /** 01876 * @if maint 01877 * This is a helper function... 01878 * @endif 01879 */ 01880 template<typename _ForwardIterator, typename _Predicate, typename _Distance> 01881 _ForwardIterator 01882 __inplace_stable_partition(_ForwardIterator __first, 01883 _ForwardIterator __last, 01884 _Predicate __pred, _Distance __len) 01885 { 01886 if (__len == 1) 01887 return __pred(*__first) ? __last : __first; 01888 _ForwardIterator __middle = __first; 01889 std::advance(__middle, __len / 2); 01890 _ForwardIterator __begin = std::__inplace_stable_partition(__first, 01891 __middle, 01892 __pred, 01893 __len / 2); 01894 _ForwardIterator __end = std::__inplace_stable_partition(__middle, __last, 01895 __pred, 01896 __len 01897 - __len / 2); 01898 std::rotate(__begin, __middle, __end); 01899 std::advance(__begin, std::distance(__middle, __end)); 01900 return __begin; 01901 } 01902 01903 /** 01904 * @if maint 01905 * This is a helper function... 01906 * @endif 01907 */ 01908 template<typename _ForwardIterator, typename _Pointer, typename _Predicate, 01909 typename _Distance> 01910 _ForwardIterator 01911 __stable_partition_adaptive(_ForwardIterator __first, 01912 _ForwardIterator __last, 01913 _Predicate __pred, _Distance __len, 01914 _Pointer __buffer, 01915 _Distance __buffer_size) 01916 { 01917 if (__len <= __buffer_size) 01918 { 01919 _ForwardIterator __result1 = __first; 01920 _Pointer __result2 = __buffer; 01921 for ( ; __first != __last ; ++__first) 01922 if (__pred(*__first)) 01923 { 01924 *__result1 = *__first; 01925 ++__result1; 01926 } 01927 else 01928 { 01929 *__result2 = *__first; 01930 ++__result2; 01931 } 01932 std::copy(__buffer, __result2, __result1); 01933 return __result1; 01934 } 01935 else 01936 { 01937 _ForwardIterator __middle = __first; 01938 std::advance(__middle, __len / 2); 01939 _ForwardIterator __begin = 01940 std::__stable_partition_adaptive(__first, __middle, __pred, 01941 __len / 2, __buffer, 01942 __buffer_size); 01943 _ForwardIterator __end = 01944 std::__stable_partition_adaptive(__middle, __last, __pred, 01945 __len - __len / 2, 01946 __buffer, __buffer_size); 01947 std::rotate(__begin, __middle, __end); 01948 std::advance(__begin, std::distance(__middle, __end)); 01949 return __begin; 01950 } 01951 } 01952 01953 /** 01954 * @brief Move elements for which a predicate is true to the beginning 01955 * of a sequence, preserving relative ordering. 01956 * @param first A forward iterator. 01957 * @param last A forward iterator. 01958 * @param pred A predicate functor. 01959 * @return An iterator @p middle such that @p pred(i) is true for each 01960 * iterator @p i in the range @p [first,middle) and false for each @p i 01961 * in the range @p [middle,last). 01962 * 01963 * Performs the same function as @p partition() with the additional 01964 * guarantee that the relative ordering of elements in each group is 01965 * preserved, so any two elements @p x and @p y in the range 01966 * @p [first,last) such that @p pred(x)==pred(y) will have the same 01967 * relative ordering after calling @p stable_partition(). 01968 */ 01969 template<typename _ForwardIterator, typename _Predicate> 01970 _ForwardIterator 01971 stable_partition(_ForwardIterator __first, _ForwardIterator __last, 01972 _Predicate __pred) 01973 { 01974 // concept requirements 01975 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept< 01976 _ForwardIterator>) 01977 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate, 01978 typename iterator_traits<_ForwardIterator>::value_type>) 01979 __glibcxx_requires_valid_range(__first, __last); 01980 01981 if (__first == __last) 01982 return __first; 01983 else 01984 { 01985 typedef typename iterator_traits<_ForwardIterator>::value_type 01986 _ValueType; 01987 typedef typename iterator_traits<_ForwardIterator>::difference_type 01988 _DistanceType; 01989 01990 _Temporary_buffer<_ForwardIterator, _ValueType> __buf(__first, 01991 __last); 01992 if (__buf.size() > 0) 01993 return 01994 std::__stable_partition_adaptive(__first, __last, __pred, 01995 _DistanceType(__buf.requested_size()), 01996 __buf.begin(), __buf.size()); 01997 else 01998 return 01999 std::__inplace_stable_partition(__first, __last, __pred, 02000 _DistanceType(__buf.requested_size())); 02001 } 02002 } 02003 02004 /** 02005 * @if maint 02006 * This is a helper function... 02007 * @endif 02008 */ 02009 template<typename _RandomAccessIterator, typename _Tp> 02010 _RandomAccessIterator 02011 __unguarded_partition(_RandomAccessIterator __first, 02012 _RandomAccessIterator __last, _Tp __pivot) 02013 { 02014 while (true) 02015 { 02016 while (*__first < __pivot) 02017 ++__first; 02018 --__last; 02019 while (__pivot < *__last) 02020 --__last; 02021 if (!(__first < __last)) 02022 return __first; 02023 std::iter_swap(__first, __last); 02024 ++__first; 02025 } 02026 } 02027 02028 /** 02029 * @if maint 02030 * This is a helper function... 02031 * @endif 02032 */ 02033 template<typename _RandomAccessIterator, typename _Tp, typename _Compare> 02034 _RandomAccessIterator 02035 __unguarded_partition(_RandomAccessIterator __first, 02036 _RandomAccessIterator __last, 02037 _Tp __pivot, _Compare __comp) 02038 { 02039 while (true) 02040 { 02041 while (__comp(*__first, __pivot)) 02042 ++__first; 02043 --__last; 02044 while (__comp(__pivot, *__last)) 02045 --__last; 02046 if (!(__first < __last)) 02047 return __first; 02048 std::iter_swap(__first, __last); 02049 ++__first; 02050 } 02051 } 02052 02053 /** 02054 * @if maint 02055 * @doctodo 02056 * This controls some aspect of the sort routines. 02057 * @endif 02058 */ 02059 enum { _S_threshold = 16 }; 02060 02061 /** 02062 * @if maint 02063 * This is a helper function for the sort routine. 02064 * @endif 02065 */ 02066 template<typename _RandomAccessIterator, typename _Tp> 02067 void 02068 __unguarded_linear_insert(_RandomAccessIterator __last, _Tp __val) 02069 { 02070 _RandomAccessIterator __next = __last; 02071 --__next; 02072 while (__val < *__next) 02073 { 02074 *__last = *__next; 02075 __last = __next; 02076 --__next; 02077 } 02078 *__last = __val; 02079 } 02080 02081 /** 02082 * @if maint 02083 * This is a helper function for the sort routine. 02084 * @endif 02085 */ 02086 template<typename _RandomAccessIterator, typename _Tp, typename _Compare> 02087 void 02088 __unguarded_linear_insert(_RandomAccessIterator __last, _Tp __val, 02089 _Compare __comp) 02090 { 02091 _RandomAccessIterator __next = __last; 02092 --__next; 02093 while (__comp(__val, *__next)) 02094 { 02095 *__last = *__next; 02096 __last = __next; 02097 --__next; 02098 } 02099 *__last = __val; 02100 } 02101 02102 /** 02103 * @if maint 02104 * This is a helper function for the sort routine. 02105 * @endif 02106 */ 02107 template<typename _RandomAccessIterator> 02108 void 02109 __insertion_sort(_RandomAccessIterator __first, 02110 _RandomAccessIterator __last) 02111 { 02112 if (__first == __last) 02113 return; 02114 02115 for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i) 02116 { 02117 typename iterator_traits<_RandomAccessIterator>::value_type 02118 __val = *__i; 02119 if (__val < *__first) 02120 { 02121 std::copy_backward(__first, __i, __i + 1); 02122 *__first = __val; 02123 } 02124 else 02125 std::__unguarded_linear_insert(__i, __val); 02126 } 02127 } 02128 02129 /** 02130 * @if maint 02131 * This is a helper function for the sort routine. 02132 * @endif 02133 */ 02134 template<typename _RandomAccessIterator, typename _Compare> 02135 void 02136 __insertion_sort(_RandomAccessIterator __first, 02137 _RandomAccessIterator __last, _Compare __comp) 02138 { 02139 if (__first == __last) return; 02140 02141 for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i) 02142 { 02143 typename iterator_traits<_RandomAccessIterator>::value_type 02144 __val = *__i; 02145 if (__comp(__val, *__first)) 02146 { 02147 std::copy_backward(__first, __i, __i + 1); 02148 *__first = __val; 02149 } 02150 else 02151 std::__unguarded_linear_insert(__i, __val, __comp); 02152 } 02153 } 02154 02155 /** 02156 * @if maint 02157 * This is a helper function for the sort routine. 02158 * @endif 02159 */ 02160 template<typename _RandomAccessIterator> 02161 inline void 02162 __unguarded_insertion_sort(_RandomAccessIterator __first, 02163 _RandomAccessIterator __last) 02164 { 02165 typedef typename iterator_traits<_RandomAccessIterator>::value_type 02166 _ValueType; 02167 02168 for (_RandomAccessIterator __i = __first; __i != __last; ++__i) 02169 std::__unguarded_linear_insert(__i, _ValueType(*__i)); 02170 } 02171 02172 /** 02173 * @if maint 02174 * This is a helper function for the sort routine. 02175 * @endif 02176 */ 02177 template<typename _RandomAccessIterator, typename _Compare> 02178 inline void 02179 __unguarded_insertion_sort(_RandomAccessIterator __first, 02180 _RandomAccessIterator __last, _Compare __comp) 02181 { 02182 typedef typename iterator_traits<_RandomAccessIterator>::value_type 02183 _ValueType; 02184 02185 for (_RandomAccessIterator __i = __first; __i != __last; ++__i) 02186 std::__unguarded_linear_insert(__i, _ValueType(*__i), __comp); 02187 } 02188 02189 /** 02190 * @if maint 02191 * This is a helper function for the sort routine. 02192 * @endif 02193 */ 02194 template<typename _RandomAccessIterator> 02195 void 02196 __final_insertion_sort(_RandomAccessIterator __first, 02197 _RandomAccessIterator __last) 02198 { 02199 if (__last - __first > _S_threshold) 02200 { 02201 std::__insertion_sort(__first, __first + _S_threshold); 02202 std::__unguarded_insertion_sort(__first + _S_threshold, __last); 02203 } 02204 else 02205 std::__insertion_sort(__first, __last); 02206 } 02207 02208 /** 02209 * @if maint 02210 * This is a helper function for the sort routine. 02211 * @endif 02212 */ 02213 template<typename _RandomAccessIterator, typename _Compare> 02214 void 02215 __final_insertion_sort(_RandomAccessIterator __first, 02216 _RandomAccessIterator __last, _Compare __comp) 02217 { 02218 if (__last - __first > _S_threshold) 02219 { 02220 std::__insertion_sort(__first, __first + _S_threshold, __comp); 02221 std::__unguarded_insertion_sort(__first + _S_threshold, __last, 02222 __comp); 02223 } 02224 else 02225 std::__insertion_sort(__first, __last, __comp); 02226 } 02227 02228 /** 02229 * @if maint 02230 * This is a helper function for the sort routine. 02231 * @endif 02232 */ 02233 template<typename _Size> 02234 inline _Size 02235 __lg(_Size __n) 02236 { 02237 _Size __k; 02238 for (__k = 0; __n != 1; __n >>= 1) 02239 ++__k; 02240 return __k; 02241 } 02242 02243 /** 02244 * @brief Sort the smallest elements of a sequence. 02245 * @param first An iterator. 02246 * @param middle Another iterator. 02247 * @param last Another iterator. 02248 * @return Nothing. 02249 * 02250 * Sorts the smallest @p (middle-first) elements in the range 02251 * @p [first,last) and moves them to the range @p [first,middle). The 02252 * order of the remaining elements in the range @p [middle,last) is 02253 * undefined. 02254 * After the sort if @p i and @j are iterators in the range 02255 * @p [first,middle) such that @i precedes @j and @k is an iterator in 02256 * the range @p [middle,last) then @p *j<*i and @p *k<*i are both false. 02257 */ 02258 template<typename _RandomAccessIterator> 02259 void 02260 partial_sort(_RandomAccessIterator __first, 02261 _RandomAccessIterator __middle, 02262 _RandomAccessIterator __last) 02263 { 02264 typedef typename iterator_traits<_RandomAccessIterator>::value_type 02265 _ValueType; 02266 02267 // concept requirements 02268 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept< 02269 _RandomAccessIterator>) 02270 __glibcxx_function_requires(_LessThanComparableConcept<_ValueType>) 02271 __glibcxx_requires_valid_range(__first, __middle); 02272 __glibcxx_requires_valid_range(__middle, __last); 02273 02274 std::make_heap(__first, __middle); 02275 for (_RandomAccessIterator __i = __middle; __i < __last; ++__i) 02276 if (*__i < *__first) 02277 std::__pop_heap(__first, __middle, __i, _ValueType(*__i)); 02278 std::sort_heap(__first, __middle); 02279 } 02280 02281 /** 02282 * @brief Sort the smallest elements of a sequence using a predicate 02283 * for comparison. 02284 * @param first An iterator. 02285 * @param middle Another iterator. 02286 * @param last Another iterator. 02287 * @param comp A comparison functor. 02288 * @return Nothing. 02289 * 02290 * Sorts the smallest @p (middle-first) elements in the range 02291 * @p [first,last) and moves them to the range @p [first,middle). The 02292 * order of the remaining elements in the range @p [middle,last) is 02293 * undefined. 02294 * After the sort if @p i and @j are iterators in the range 02295 * @p [first,middle) such that @i precedes @j and @k is an iterator in 02296 * the range @p [middle,last) then @p *comp(j,*i) and @p comp(*k,*i) 02297 * are both false. 02298 */ 02299 template<typename _RandomAccessIterator, typename _Compare> 02300 void 02301 partial_sort(_RandomAccessIterator __first, 02302 _RandomAccessIterator __middle, 02303 _RandomAccessIterator __last, 02304 _Compare __comp) 02305 { 02306 typedef typename iterator_traits<_RandomAccessIterator>::value_type 02307 _ValueType; 02308 02309 // concept requirements 02310 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept< 02311 _RandomAccessIterator>) 02312 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, 02313 _ValueType, _ValueType>) 02314 __glibcxx_requires_valid_range(__first, __middle); 02315 __glibcxx_requires_valid_range(__middle, __last); 02316 02317 std::make_heap(__first, __middle, __comp); 02318 for (_RandomAccessIterator __i = __middle; __i < __last; ++__i) 02319 if (__comp(*__i, *__first)) 02320 std::__pop_heap(__first, __middle, __i, _ValueType(*__i), __comp); 02321 std::sort_heap(__first, __middle, __comp); 02322 } 02323 02324 /** 02325 * @brief Copy the smallest elements of a sequence. 02326 * @param first An iterator. 02327 * @param last Another iterator. 02328 * @param result_first A random-access iterator. 02329 * @param result_last Another random-access iterator. 02330 * @return An iterator indicating the end of the resulting sequence. 02331 * 02332 * Copies and sorts the smallest N values from the range @p [first,last) 02333 * to the range beginning at @p result_first, where the number of 02334 * elements to be copied, @p N, is the smaller of @p (last-first) and 02335 * @p (result_last-result_first). 02336 * After the sort if @p i and @j are iterators in the range 02337 * @p [result_first,result_first+N) such that @i precedes @j then 02338 * @p *j<*i is false. 02339 * The value returned is @p result_first+N. 02340 */ 02341 template<typename _InputIterator, typename _RandomAccessIterator> 02342 _RandomAccessIterator 02343 partial_sort_copy(_InputIterator __first, _InputIterator __last, 02344 _RandomAccessIterator __result_first, 02345 _RandomAccessIterator __result_last) 02346 { 02347 typedef typename iterator_traits<_InputIterator>::value_type 02348 _InputValueType; 02349 typedef typename iterator_traits<_RandomAccessIterator>::value_type 02350 _OutputValueType; 02351 typedef typename iterator_traits<_RandomAccessIterator>::difference_type 02352 _DistanceType; 02353 02354 // concept requirements 02355 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) 02356 __glibcxx_function_requires(_ConvertibleConcept<_InputValueType, 02357 _OutputValueType>) 02358 __glibcxx_function_requires(_LessThanComparableConcept<_OutputValueType>) 02359 __glibcxx_function_requires(_LessThanComparableConcept<_InputValueType>) 02360 __glibcxx_requires_valid_range(__first, __last); 02361 __glibcxx_requires_valid_range(__result_first, __result_last); 02362 02363 if (__result_first == __result_last) 02364 return __result_last; 02365 _RandomAccessIterator __result_real_last = __result_first; 02366 while(__first != __last && __result_real_last != __result_last) 02367 { 02368 *__result_real_last = *__first; 02369 ++__result_real_last; 02370 ++__first; 02371 } 02372 std::make_heap(__result_first, __result_real_last); 02373 while (__first != __last) 02374 { 02375 if (*__first < *__result_first) 02376 std::__adjust_heap(__result_first, _DistanceType(0), 02377 _DistanceType(__result_real_last 02378 - __result_first), 02379 _InputValueType(*__first)); 02380 ++__first; 02381 } 02382 std::sort_heap(__result_first, __result_real_last); 02383 return __result_real_last; 02384 } 02385 02386 /** 02387 * @brief Copy the smallest elements of a sequence using a predicate for 02388 * comparison. 02389 * @param first An input iterator. 02390 * @param last Another input iterator. 02391 * @param result_first A random-access iterator. 02392 * @param result_last Another random-access iterator. 02393 * @param comp A comparison functor. 02394 * @return An iterator indicating the end of the resulting sequence. 02395 * 02396 * Copies and sorts the smallest N values from the range @p [first,last) 02397 * to the range beginning at @p result_first, where the number of 02398 * elements to be copied, @p N, is the smaller of @p (last-first) and 02399 * @p (result_last-result_first). 02400 * After the sort if @p i and @j are iterators in the range 02401 * @p [result_first,result_first+N) such that @i precedes @j then 02402 * @p comp(*j,*i) is false. 02403 * The value returned is @p result_first+N. 02404 */ 02405 template<typename _InputIterator, typename _RandomAccessIterator, typename _Compare> 02406 _RandomAccessIterator 02407 partial_sort_copy(_InputIterator __first, _InputIterator __last, 02408 _RandomAccessIterator __result_first, 02409 _RandomAccessIterator __result_last, 02410 _Compare __comp) 02411 { 02412 typedef typename iterator_traits<_InputIterator>::value_type 02413 _InputValueType; 02414 typedef typename iterator_traits<_RandomAccessIterator>::value_type 02415 _OutputValueType; 02416 typedef typename iterator_traits<_RandomAccessIterator>::difference_type 02417 _DistanceType; 02418 02419 // concept requirements 02420 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) 02421 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept< 02422 _RandomAccessIterator>) 02423 __glibcxx_function_requires(_ConvertibleConcept<_InputValueType, 02424 _OutputValueType>) 02425 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, 02426 _OutputValueType, _OutputValueType>) 02427 __glibcxx_requires_valid_range(__first, __last); 02428 __glibcxx_requires_valid_range(__result_first, __result_last); 02429 02430 if (__result_first == __result_last) 02431 return __result_last; 02432 _RandomAccessIterator __result_real_last = __result_first; 02433 while(__first != __last && __result_real_last != __result_last) 02434 { 02435 *__result_real_last = *__first; 02436 ++__result_real_last; 02437 ++__first; 02438 } 02439 std::make_heap(__result_first, __result_real_last, __comp); 02440 while (__first != __last) 02441 { 02442 if (__comp(*__first, *__result_first)) 02443 std::__adjust_heap(__result_first, _DistanceType(0), 02444 _DistanceType(__result_real_last 02445 - __result_first), 02446 _InputValueType(*__first), 02447 __comp); 02448 ++__first; 02449 } 02450 std::sort_heap(__result_first, __result_real_last, __comp); 02451 return __result_real_last; 02452 } 02453 02454 /** 02455 * @if maint 02456 * This is a helper function for the sort routine. 02457 * @endif 02458 */ 02459 template<typename _RandomAccessIterator, typename _Size> 02460 void 02461 __introsort_loop(_RandomAccessIterator __first, 02462 _RandomAccessIterator __last, 02463 _Size __depth_limit) 02464 { 02465 typedef typename iterator_traits<_RandomAccessIterator>::value_type 02466 _ValueType; 02467 02468 while (__last - __first > _S_threshold) 02469 { 02470 if (__depth_limit == 0) 02471 { 02472 std::partial_sort(__first, __last, __last); 02473 return; 02474 } 02475 --__depth_limit; 02476 _RandomAccessIterator __cut = 02477 std::__unguarded_partition(__first, __last, 02478 _ValueType(std::__median(*__first, 02479 *(__first 02480 + (__last 02481 - __first) 02482 / 2), 02483 *(__last 02484 - 1)))); 02485 std::__introsort_loop(__cut, __last, __depth_limit); 02486 __last = __cut; 02487 } 02488 } 02489 02490 /** 02491 * @if maint 02492 * This is a helper function for the sort routine. 02493 * @endif 02494 */ 02495 template<typename _RandomAccessIterator, typename _Size, typename _Compare> 02496 void 02497 __introsort_loop(_RandomAccessIterator __first, 02498 _RandomAccessIterator __last, 02499 _Size __depth_limit, _Compare __comp) 02500 { 02501 typedef typename iterator_traits<_RandomAccessIterator>::value_type 02502 _ValueType; 02503 02504 while (__last - __first > _S_threshold) 02505 { 02506 if (__depth_limit == 0) 02507 { 02508 std::partial_sort(__first, __last, __last, __comp); 02509 return; 02510 } 02511 --__depth_limit; 02512 _RandomAccessIterator __cut = 02513 std::__unguarded_partition(__first, __last, 02514 _ValueType(std::__median(*__first, 02515 *(__first 02516 + (__last 02517 - __first) 02518 / 2), 02519 *(__last - 1), 02520 __comp)), 02521 __comp); 02522 std::__introsort_loop(__cut, __last, __depth_limit, __comp); 02523 __last = __cut; 02524 } 02525 } 02526 02527 /** 02528 * @brief Sort the elements of a sequence. 02529 * @param first An iterator. 02530 * @param last Another iterator. 02531 * @return Nothing. 02532 * 02533 * Sorts the elements in the range @p [first,last) in ascending order, 02534 * such that @p *(i+1)<*i is false for each iterator @p i in the range 02535 * @p [first,last-1). 02536 * 02537 * The relative ordering of equivalent elements is not preserved, use 02538 * @p stable_sort() if this is needed. 02539 */ 02540 template<typename _RandomAccessIterator> 02541 inline void 02542 sort(_RandomAccessIterator __first, _RandomAccessIterator __last) 02543 { 02544 typedef typename iterator_traits<_RandomAccessIterator>::value_type 02545 _ValueType; 02546 02547 // concept requirements 02548 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept< 02549 _RandomAccessIterator>) 02550 __glibcxx_function_requires(_LessThanComparableConcept<_ValueType>) 02551 __glibcxx_requires_valid_range(__first, __last); 02552 02553 if (__first != __last) 02554 { 02555 std::__introsort_loop(__first, __last, __lg(__last - __first) * 2); 02556 std::__final_insertion_sort(__first, __last); 02557 } 02558 } 02559 02560 /** 02561 * @brief Sort the elements of a sequence using a predicate for comparison. 02562 * @param first An iterator. 02563 * @param last Another iterator. 02564 * @param comp A comparison functor. 02565 * @return Nothing. 02566 * 02567 * Sorts the elements in the range @p [first,last) in ascending order, 02568 * such that @p comp(*(i+1),*i) is false for every iterator @p i in the 02569 * range @p [first,last-1). 02570 * 02571 * The relative ordering of equivalent elements is not preserved, use 02572 * @p stable_sort() if this is needed. 02573 */ 02574 template<typename _RandomAccessIterator, typename _Compare> 02575 inline void 02576 sort(_RandomAccessIterator __first, _RandomAccessIterator __last, 02577 _Compare __comp) 02578 { 02579 typedef typename iterator_traits<_RandomAccessIterator>::value_type 02580 _ValueType; 02581 02582 // concept requirements 02583 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept< 02584 _RandomAccessIterator>) 02585 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, _ValueType, 02586 _ValueType>) 02587 __glibcxx_requires_valid_range(__first, __last); 02588 02589 if (__first != __last) 02590 { 02591 std::__introsort_loop(__first, __last, __lg(__last - __first) * 2, 02592 __comp); 02593 std::__final_insertion_sort(__first, __last, __comp); 02594 } 02595 } 02596 02597 /** 02598 * @brief Finds the first position in which @a val could be inserted 02599 * without changing the ordering. 02600 * @param first An iterator. 02601 * @param last Another iterator. 02602 * @param val The search term. 02603 * @return An iterator pointing to the first element "not less than" @a val, 02604 * or end() if every element is less than @a val. 02605 * @ingroup binarysearch 02606 */ 02607 template<typename _ForwardIterator, typename _Tp> 02608 _ForwardIterator 02609 lower_bound(_ForwardIterator __first, _ForwardIterator __last, 02610 const _Tp& __val) 02611 { 02612 typedef typename iterator_traits<_ForwardIterator>::value_type 02613 _ValueType; 02614 typedef typename iterator_traits<_ForwardIterator>::difference_type 02615 _DistanceType; 02616 02617 // concept requirements 02618 // Note that these are slightly stricter than those of the 4-argument 02619 // version, defined next. The difference is in the strictness of the 02620 // comparison operations... so for looser checking, define your own 02621 // comparison function, as was intended. 02622 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) 02623 __glibcxx_function_requires(_SameTypeConcept<_Tp, _ValueType>) 02624 __glibcxx_function_requires(_LessThanComparableConcept<_Tp>) 02625 __glibcxx_requires_partitioned(__first, __last, __val); 02626 02627 _DistanceType __len = std::distance(__first, __last); 02628 _DistanceType __half; 02629 _ForwardIterator __middle; 02630 02631 while (__len > 0) 02632 { 02633 __half = __len >> 1; 02634 __middle = __first; 02635 std::advance(__middle, __half); 02636 if (*__middle < __val) 02637 { 02638 __first = __middle; 02639 ++__first; 02640 __len = __len - __half - 1; 02641 } 02642 else 02643 __len = __half; 02644 } 02645 return __first; 02646 } 02647 02648 /** 02649 * @brief Finds the first position in which @a val could be inserted 02650 * without changing the ordering. 02651 * @param first An iterator. 02652 * @param last Another iterator. 02653 * @param val The search term. 02654 * @param comp A functor to use for comparisons. 02655 * @return An iterator pointing to the first element "not less than" @a val, 02656 * or end() if every element is less than @a val. 02657 * @ingroup binarysearch 02658 * 02659 * The comparison function should have the same effects on ordering as 02660 * the function used for the initial sort. 02661 */ 02662 template<typename _ForwardIterator, typename _Tp, typename _Compare> 02663 _ForwardIterator 02664 lower_bound(_ForwardIterator __first, _ForwardIterator __last, 02665 const _Tp& __val, _Compare __comp) 02666 { 02667 typedef typename iterator_traits<_ForwardIterator>::value_type 02668 _ValueType; 02669 typedef typename iterator_traits<_ForwardIterator>::difference_type 02670 _DistanceType; 02671 02672 // concept requirements 02673 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) 02674 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, 02675 _ValueType, _Tp>) 02676 __glibcxx_requires_partitioned_pred(__first, __last, __val, __comp); 02677 02678 _DistanceType __len = std::distance(__first, __last); 02679 _DistanceType __half; 02680 _ForwardIterator __middle; 02681 02682 while (__len > 0) 02683 { 02684 __half = __len >> 1; 02685 __middle = __first; 02686 std::advance(__middle, __half); 02687 if (__comp(*__middle, __val)) 02688 { 02689 __first = __middle; 02690 ++__first; 02691 __len = __len - __half - 1; 02692 } 02693 else 02694 __len = __half; 02695 } 02696 return __first; 02697 } 02698 02699 /** 02700 * @brief Finds the last position in which @a val could be inserted 02701 * without changing the ordering. 02702 * @param first An iterator. 02703 * @param last Another iterator. 02704 * @param val The search term. 02705 * @return An iterator pointing to the first element greater than @a val, 02706 * or end() if no elements are greater than @a val. 02707 * @ingroup binarysearch 02708 */ 02709 template<typename _ForwardIterator, typename _Tp> 02710 _ForwardIterator 02711 upper_bound(_ForwardIterator __first, _ForwardIterator __last, 02712 const _Tp& __val) 02713 { 02714 typedef typename iterator_traits<_ForwardIterator>::value_type 02715 _ValueType; 02716 typedef typename iterator_traits<_ForwardIterator>::difference_type 02717 _DistanceType; 02718 02719 // concept requirements 02720 // See comments on lower_bound. 02721 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) 02722 __glibcxx_function_requires(_SameTypeConcept<_Tp, _ValueType>) 02723 __glibcxx_function_requires(_LessThanComparableConcept<_Tp>) 02724 __glibcxx_requires_partitioned(__first, __last, __val); 02725 02726 _DistanceType __len = std::distance(__first, __last); 02727 _DistanceType __half; 02728 _ForwardIterator __middle; 02729 02730 while (__len > 0) 02731 { 02732 __half = __len >> 1; 02733 __middle = __first; 02734 std::advance(__middle, __half); 02735 if (__val < *__middle) 02736 __len = __half; 02737 else 02738 { 02739 __first = __middle; 02740 ++__first; 02741 __len = __len - __half - 1; 02742 } 02743 } 02744 return __first; 02745 } 02746 02747 /** 02748 * @brief Finds the last position in which @a val could be inserted 02749 * without changing the ordering. 02750 * @param first An iterator. 02751 * @param last Another iterator. 02752 * @param val The search term. 02753 * @param comp A functor to use for comparisons. 02754 * @return An iterator pointing to the first element greater than @a val, 02755 * or end() if no elements are greater than @a val. 02756 * @ingroup binarysearch 02757 * 02758 * The comparison function should have the same effects on ordering as 02759 * the function used for the initial sort. 02760 */ 02761 template<typename _ForwardIterator, typename _Tp, typename _Compare> 02762 _ForwardIterator 02763 upper_bound(_ForwardIterator __first, _ForwardIterator __last, 02764 const _Tp& __val, _Compare __comp) 02765 { 02766 typedef typename iterator_traits<_ForwardIterator>::value_type 02767 _ValueType; 02768 typedef typename iterator_traits<_ForwardIterator>::difference_type 02769 _DistanceType; 02770 02771 // concept requirements 02772 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) 02773 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, 02774 _Tp, _ValueType>) 02775 __glibcxx_requires_partitioned_pred(__first, __last, __val, __comp); 02776 02777 _DistanceType __len = std::distance(__first, __last); 02778 _DistanceType __half; 02779 _ForwardIterator __middle; 02780 02781 while (__len > 0) 02782 { 02783 __half = __len >> 1; 02784 __middle = __first; 02785 std::advance(__middle, __half); 02786 if (__comp(__val, *__middle)) 02787 __len = __half; 02788 else 02789 { 02790 __first = __middle; 02791 ++__first; 02792 __len = __len - __half - 1; 02793 } 02794 } 02795 return __first; 02796 } 02797 02798 /** 02799 * @if maint 02800 * This is a helper function for the merge routines. 02801 * @endif 02802 */ 02803 template<typename _BidirectionalIterator, typename _Distance> 02804 void 02805 __merge_without_buffer(_BidirectionalIterator __first, 02806 _BidirectionalIterator __middle, 02807 _BidirectionalIterator __last, 02808 _Distance __len1, _Distance __len2) 02809 { 02810 if (__len1 == 0 || __len2 == 0) 02811 return; 02812 if (__len1 + __len2 == 2) 02813 { 02814 if (*__middle < *__first) 02815 std::iter_swap(__first, __middle); 02816 return; 02817 } 02818 _BidirectionalIterator __first_cut = __first; 02819 _BidirectionalIterator __second_cut = __middle; 02820 _Distance __len11 = 0; 02821 _Distance __len22 = 0; 02822 if (__len1 > __len2) 02823 { 02824 __len11 = __len1 / 2; 02825 std::advance(__first_cut, __len11); 02826 __second_cut = std::lower_bound(__middle, __last, *__first_cut); 02827 __len22 = std::distance(__middle, __second_cut); 02828 } 02829 else 02830 { 02831 __len22 = __len2 / 2; 02832 std::advance(__second_cut, __len22); 02833 __first_cut = std::upper_bound(__first, __middle, *__second_cut); 02834 __len11 = std::distance(__first, __first_cut); 02835 } 02836 std::rotate(__first_cut, __middle, __second_cut); 02837 _BidirectionalIterator __new_middle = __first_cut; 02838 std::advance(__new_middle, std::distance(__middle, __second_cut)); 02839 std::__merge_without_buffer(__first, __first_cut, __new_middle, 02840 __len11, __len22); 02841 std::__merge_without_buffer(__new_middle, __second_cut, __last, 02842 __len1 - __len11, __len2 - __len22); 02843 } 02844 02845 /** 02846 * @if maint 02847 * This is a helper function for the merge routines. 02848 * @endif 02849 */ 02850 template<typename _BidirectionalIterator, typename _Distance, 02851 typename _Compare> 02852 void 02853 __merge_without_buffer(_BidirectionalIterator __first, 02854 _BidirectionalIterator __middle, 02855 _BidirectionalIterator __last, 02856 _Distance __len1, _Distance __len2, 02857 _Compare __comp) 02858 { 02859 if (__len1 == 0 || __len2 == 0) 02860 return; 02861 if (__len1 + __len2 == 2) 02862 { 02863 if (__comp(*__middle, *__first)) 02864 std::iter_swap(__first, __middle); 02865 return; 02866 } 02867 _BidirectionalIterator __first_cut = __first; 02868 _BidirectionalIterator __second_cut = __middle; 02869 _Distance __len11 = 0; 02870 _Distance __len22 = 0; 02871 if (__len1 > __len2) 02872 { 02873 __len11 = __len1 / 2; 02874 std::advance(__first_cut, __len11); 02875 __second_cut = std::lower_bound(__middle, __last, *__first_cut, 02876 __comp); 02877 __len22 = std::distance(__middle, __second_cut); 02878 } 02879 else 02880 { 02881 __len22 = __len2 / 2; 02882 std::advance(__second_cut, __len22); 02883 __first_cut = std::upper_bound(__first, __middle, *__second_cut, 02884 __comp); 02885 __len11 = std::distance(__first, __first_cut); 02886 } 02887 std::rotate(__first_cut, __middle, __second_cut); 02888 _BidirectionalIterator __new_middle = __first_cut; 02889 std::advance(__new_middle, std::distance(__middle, __second_cut)); 02890 std::__merge_without_buffer(__first, __first_cut, __new_middle, 02891 __len11, __len22, __comp); 02892 std::__merge_without_buffer(__new_middle, __second_cut, __last, 02893 __len1 - __len11, __len2 - __len22, __comp); 02894 } 02895 02896 /** 02897 * @if maint 02898 * This is a helper function for the stable sorting routines. 02899 * @endif 02900 */ 02901 template<typename _RandomAccessIterator> 02902 void 02903 __inplace_stable_sort(_RandomAccessIterator __first, 02904 _RandomAccessIterator __last) 02905 { 02906 if (__last - __first < 15) 02907 { 02908 std::__insertion_sort(__first, __last); 02909 return; 02910 } 02911 _RandomAccessIterator __middle = __first + (__last - __first) / 2; 02912 std::__inplace_stable_sort(__first, __middle); 02913 std::__inplace_stable_sort(__middle, __last); 02914 std::__merge_without_buffer(__first, __middle, __last, 02915 __middle - __first, 02916 __last - __middle); 02917 } 02918 02919 /** 02920 * @if maint 02921 * This is a helper function for the stable sorting routines. 02922 * @endif 02923 */ 02924 template<typename _RandomAccessIterator, typename _Compare> 02925 void 02926 __inplace_stable_sort(_RandomAccessIterator __first, 02927 _RandomAccessIterator __last, _Compare __comp) 02928 { 02929 if (__last - __first < 15) 02930 { 02931 std::__insertion_sort(__first, __last, __comp); 02932 return; 02933 } 02934 _RandomAccessIterator __middle = __first + (__last - __first) / 2; 02935 std::__inplace_stable_sort(__first, __middle, __comp); 02936 std::__inplace_stable_sort(__middle, __last, __comp); 02937 std::__merge_without_buffer(__first, __middle, __last, 02938 __middle - __first, 02939 __last - __middle, 02940 __comp); 02941 } 02942 02943 /** 02944 * @brief Merges two sorted ranges. 02945 * @param first1 An iterator. 02946 * @param first2 Another iterator. 02947 * @param last1 Another iterator. 02948 * @param last2 Another iterator. 02949 * @param result An iterator pointing to the end of the merged range. 02950 * @return An iterator pointing to the first element "not less than" @a val. 02951 * 02952 * Merges the ranges [first1,last1) and [first2,last2) into the sorted range 02953 * [result, result + (last1-first1) + (last2-first2)). Both input ranges 02954 * must be sorted, and the output range must not overlap with either of 02955 * the input ranges. The sort is @e stable, that is, for equivalent 02956 * elements in the two ranges, elements from the first range will always 02957 * come before elements from the second. 02958 */ 02959 template<typename _InputIterator1, typename _InputIterator2, 02960 typename _OutputIterator> 02961 _OutputIterator 02962 merge(_InputIterator1 __first1, _InputIterator1 __last1, 02963 _InputIterator2 __first2, _InputIterator2 __last2, 02964 _OutputIterator __result) 02965 { 02966 // concept requirements 02967 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>) 02968 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>) 02969 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, 02970 typename iterator_traits<_InputIterator1>::value_type>) 02971 __glibcxx_function_requires(_SameTypeConcept< 02972 typename iterator_traits<_InputIterator1>::value_type, 02973 typename iterator_traits<_InputIterator2>::value_type>) 02974 __glibcxx_function_requires(_LessThanComparableConcept< 02975 typename iterator_traits<_InputIterator1>::value_type>) 02976 __glibcxx_requires_sorted(__first1, __last1); 02977 __glibcxx_requires_sorted(__first2, __last2); 02978 02979 while (__first1 != __last1 && __first2 != __last2) 02980 { 02981 if (*__first2 < *__first1) 02982 { 02983 *__result = *__first2; 02984 ++__first2; 02985 } 02986 else 02987 { 02988 *__result = *__first1; 02989 ++__first1; 02990 } 02991 ++__result; 02992 } 02993 return std::copy(__first2, __last2, std::copy(__first1, __last1, 02994 __result)); 02995 } 02996 02997 /** 02998 * @brief Merges two sorted ranges. 02999 * @param first1 An iterator. 03000 * @param first2 Another iterator. 03001 * @param last1 Another iterator. 03002 * @param last2 Another iterator. 03003 * @param result An iterator pointing to the end of the merged range. 03004 * @param comp A functor to use for comparisons. 03005 * @return An iterator pointing to the first element "not less than" @a val. 03006 * 03007 * Merges the ranges [first1,last1) and [first2,last2) into the sorted range 03008 * [result, result + (last1-first1) + (last2-first2)). Both input ranges 03009 * must be sorted, and the output range must not overlap with either of 03010 * the input ranges. The sort is @e stable, that is, for equivalent 03011 * elements in the two ranges, elements from the first range will always 03012 * come before elements from the second. 03013 * 03014 * The comparison function should have the same effects on ordering as 03015 * the function used for the initial sort. 03016 */ 03017 template<typename _InputIterator1, typename _InputIterator2, 03018 typename _OutputIterator, typename _Compare> 03019 _OutputIterator 03020 merge(_InputIterator1 __first1, _InputIterator1 __last1, 03021 _InputIterator2 __first2, _InputIterator2 __last2, 03022 _OutputIterator __result, _Compare __comp) 03023 { 03024 // concept requirements 03025 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>) 03026 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>) 03027 __glibcxx_function_requires(_SameTypeConcept< 03028 typename iterator_traits<_InputIterator1>::value_type, 03029 typename iterator_traits<_InputIterator2>::value_type>) 03030 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, 03031 typename iterator_traits<_InputIterator1>::value_type>) 03032 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, 03033 typename iterator_traits<_InputIterator1>::value_type, 03034 typename iterator_traits<_InputIterator2>::value_type>) 03035 __glibcxx_requires_sorted_pred(__first1, __last1, __comp); 03036 __glibcxx_requires_sorted_pred(__first2, __last2, __comp); 03037 03038 while (__first1 != __last1 && __first2 != __last2) 03039 { 03040 if (__comp(*__first2, *__first1)) 03041 { 03042 *__result = *__first2; 03043 ++__first2; 03044 } 03045 else 03046 { 03047 *__result = *__first1; 03048 ++__first1; 03049 } 03050 ++__result; 03051 } 03052 return std::copy(__first2, __last2, std::copy(__first1, __last1, 03053 __result)); 03054 } 03055 03056 template<typename _RandomAccessIterator1, typename _RandomAccessIterator2, 03057 typename _Distance> 03058 void 03059 __merge_sort_loop(_RandomAccessIterator1 __first, 03060 _RandomAccessIterator1 __last, 03061 _RandomAccessIterator2 __result, 03062 _Distance __step_size) 03063 { 03064 const _Distance __two_step = 2 * __step_size; 03065 03066 while (__last - __first >= __two_step) 03067 { 03068 __result = std::merge(__first, __first + __step_size, 03069 __first + __step_size, __first + __two_step, 03070 __result); 03071 __first += __two_step; 03072 } 03073 03074 __step_size = std::min(_Distance(__last - __first), __step_size); 03075 std::merge(__first, __first + __step_size, __first + __step_size, __last, 03076 __result); 03077 } 03078 03079 template<typename _RandomAccessIterator1, typename _RandomAccessIterator2, 03080 typename _Distance, typename _Compare> 03081 void 03082 __merge_sort_loop(_RandomAccessIterator1 __first, 03083 _RandomAccessIterator1 __last, 03084 _RandomAccessIterator2 __result, _Distance __step_size, 03085 _Compare __comp) 03086 { 03087 const _Distance __two_step = 2 * __step_size; 03088 03089 while (__last - __first >= __two_step) 03090 { 03091 __result = std::merge(__first, __first + __step_size, 03092 __first + __step_size, __first + __two_step, 03093 __result, 03094 __comp); 03095 __first += __two_step; 03096 } 03097 __step_size = std::min(_Distance(__last - __first), __step_size); 03098 03099 std::merge(__first, __first + __step_size, 03100 __first + __step_size, __last, 03101 __result, 03102 __comp); 03103 } 03104 03105 enum { _S_chunk_size = 7 }; 03106 03107 template<typename _RandomAccessIterator, typename _Distance> 03108 void 03109 __chunk_insertion_sort(_RandomAccessIterator __first, 03110 _RandomAccessIterator __last, 03111 _Distance __chunk_size) 03112 { 03113 while (__last - __first >= __chunk_size) 03114 { 03115 std::__insertion_sort(__first, __first + __chunk_size); 03116 __first += __chunk_size; 03117 } 03118 std::__insertion_sort(__first, __last); 03119 } 03120 03121 template<typename _RandomAccessIterator, typename _Distance, typename _Compare> 03122 void 03123 __chunk_insertion_sort(_RandomAccessIterator __first, 03124 _RandomAccessIterator __last, 03125 _Distance __chunk_size, _Compare __comp) 03126 { 03127 while (__last - __first >= __chunk_size) 03128 { 03129 std::__insertion_sort(__first, __first + __chunk_size, __comp); 03130 __first += __chunk_size; 03131 } 03132 std::__insertion_sort(__first, __last, __comp); 03133 } 03134 03135 template<typename _RandomAccessIterator, typename _Pointer> 03136 void 03137 __merge_sort_with_buffer(_RandomAccessIterator __first, 03138 _RandomAccessIterator __last, 03139 _Pointer __buffer) 03140 { 03141 typedef typename iterator_traits<_RandomAccessIterator>::difference_type 03142 _Distance; 03143 03144 const _Distance __len = __last - __first; 03145 const _Pointer __buffer_last = __buffer + __len; 03146 03147 _Distance __step_size = _S_chunk_size; 03148 std::__chunk_insertion_sort(__first, __last, __step_size); 03149 03150 while (__step_size < __len) 03151 { 03152 std::__merge_sort_loop(__first, __last, __buffer, __step_size); 03153 __step_size *= 2; 03154 std::__merge_sort_loop(__buffer, __buffer_last, __first, __step_size); 03155 __step_size *= 2; 03156 } 03157 } 03158 03159 template<typename _RandomAccessIterator, typename _Pointer, typename _Compare> 03160 void 03161 __merge_sort_with_buffer(_RandomAccessIterator __first, 03162 _RandomAccessIterator __last, 03163 _Pointer __buffer, _Compare __comp) 03164 { 03165 typedef typename iterator_traits<_RandomAccessIterator>::difference_type 03166 _Distance; 03167 03168 const _Distance __len = __last - __first; 03169 const _Pointer __buffer_last = __buffer + __len; 03170 03171 _Distance __step_size = _S_chunk_size; 03172 std::__chunk_insertion_sort(__first, __last, __step_size, __comp); 03173 03174 while (__step_size < __len) 03175 { 03176 std::__merge_sort_loop(__first, __last, __buffer, 03177 __step_size, __comp); 03178 __step_size *= 2; 03179 std::__merge_sort_loop(__buffer, __buffer_last, __first, 03180 __step_size, __comp); 03181 __step_size *= 2; 03182 } 03183 } 03184 03185 /** 03186 * @if maint 03187 * This is a helper function for the merge routines. 03188 * @endif 03189 */ 03190 template<typename _BidirectionalIterator1, typename _BidirectionalIterator2, 03191 typename _BidirectionalIterator3> 03192 _BidirectionalIterator3 03193 __merge_backward(_BidirectionalIterator1 __first1, 03194 _BidirectionalIterator1 __last1, 03195 _BidirectionalIterator2 __first2, 03196 _BidirectionalIterator2 __last2, 03197 _BidirectionalIterator3 __result) 03198 { 03199 if (__first1 == __last1) 03200 return std::copy_backward(__first2, __last2, __result); 03201 if (__first2 == __last2) 03202 return std::copy_backward(__first1, __last1, __result); 03203 --__last1; 03204 --__last2; 03205 while (true) 03206 { 03207 if (*__last2 < *__last1) 03208 { 03209 *--__result = *__last1; 03210 if (__first1 == __last1) 03211 return std::copy_backward(__first2, ++__last2, __result); 03212 --__last1; 03213 } 03214 else 03215 { 03216 *--__result = *__last2; 03217 if (__first2 == __last2) 03218 return std::copy_backward(__first1, ++__last1, __result); 03219 --__last2; 03220 } 03221 } 03222 } 03223 03224 /** 03225 * @if maint 03226 * This is a helper function for the merge routines. 03227 * @endif 03228 */ 03229 template<typename _BidirectionalIterator1, typename _BidirectionalIterator2, 03230 typename _BidirectionalIterator3, typename _Compare> 03231 _BidirectionalIterator3 03232 __merge_backward(_BidirectionalIterator1 __first1, 03233 _BidirectionalIterator1 __last1, 03234 _BidirectionalIterator2 __first2, 03235 _BidirectionalIterator2 __last2, 03236 _BidirectionalIterator3 __result, 03237 _Compare __comp) 03238 { 03239 if (__first1 == __last1) 03240 return std::copy_backward(__first2, __last2, __result); 03241 if (__first2 == __last2) 03242 return std::copy_backward(__first1, __last1, __result); 03243 --__last1; 03244 --__last2; 03245 while (true) 03246 { 03247 if (__comp(*__last2, *__last1)) 03248 { 03249 *--__result = *__last1; 03250 if (__first1 == __last1) 03251 return std::copy_backward(__first2, ++__last2, __result); 03252 --__last1; 03253 } 03254 else 03255 { 03256 *--__result = *__last2; 03257 if (__first2 == __last2) 03258 return std::copy_backward(__first1, ++__last1, __result); 03259 --__last2; 03260 } 03261 } 03262 } 03263 03264 /** 03265 * @if maint 03266 * This is a helper function for the merge routines. 03267 * @endif 03268 */ 03269 template<typename _BidirectionalIterator1, typename _BidirectionalIterator2, 03270 typename _Distance> 03271 _BidirectionalIterator1 03272 __rotate_adaptive(_BidirectionalIterator1 __first, 03273 _BidirectionalIterator1 __middle, 03274 _BidirectionalIterator1 __last, 03275 _Distance __len1, _Distance __len2, 03276 _BidirectionalIterator2 __buffer, 03277 _Distance __buffer_size) 03278 { 03279 _BidirectionalIterator2 __buffer_end; 03280 if (__len1 > __len2 && __len2 <= __buffer_size) 03281 { 03282 __buffer_end = std::copy(__middle, __last, __buffer); 03283 std::copy_backward(__first, __middle, __last); 03284 return std::copy(__buffer, __buffer_end, __first); 03285 } 03286 else if (__len1 <= __buffer_size) 03287 { 03288 __buffer_end = std::copy(__first, __middle, __buffer); 03289 std::copy(__middle, __last, __first); 03290 return std::copy_backward(__buffer, __buffer_end, __last); 03291 } 03292 else 03293 { 03294 std::rotate(__first, __middle, __last); 03295 std::advance(__first, std::distance(__middle, __last)); 03296 return __first; 03297 } 03298 } 03299 03300 /** 03301 * @if maint 03302 * This is a helper function for the merge routines. 03303 * @endif 03304 */ 03305 template<typename _BidirectionalIterator, typename _Distance, 03306 typename _Pointer> 03307 void 03308 __merge_adaptive(_BidirectionalIterator __first, 03309 _BidirectionalIterator __middle, 03310 _BidirectionalIterator __last, 03311 _Distance __len1, _Distance __len2, 03312 _Pointer __buffer, _Distance __buffer_size) 03313 { 03314 if (__len1 <= __len2 && __len1 <= __buffer_size) 03315 { 03316 _Pointer __buffer_end = std::copy(__first, __middle, __buffer); 03317 std::merge(__buffer, __buffer_end, __middle, __last, __first); 03318 } 03319 else if (__len2 <= __buffer_size) 03320 { 03321 _Pointer __buffer_end = std::copy(__middle, __last, __buffer); 03322 std::__merge_backward(__first, __middle, __buffer, 03323 __buffer_end, __last); 03324 } 03325 else 03326 { 03327 _BidirectionalIterator __first_cut = __first; 03328 _BidirectionalIterator __second_cut = __middle; 03329 _Distance __len11 = 0; 03330 _Distance __len22 = 0; 03331 if (__len1 > __len2) 03332 { 03333 __len11 = __len1 / 2; 03334 std::advance(__first_cut, __len11); 03335 __second_cut = std::lower_bound(__middle, __last, 03336 *__first_cut); 03337 __len22 = std::distance(__middle, __second_cut); 03338 } 03339 else 03340 { 03341 __len22 = __len2 / 2; 03342 std::advance(__second_cut, __len22); 03343 __first_cut = std::upper_bound(__first, __middle, 03344 *__second_cut); 03345 __len11 = std::distance(__first, __first_cut); 03346 } 03347 _BidirectionalIterator __new_middle = 03348 std::__rotate_adaptive(__first_cut, __middle, __second_cut, 03349 __len1 - __len11, __len22, __buffer, 03350 __buffer_size); 03351 std::__merge_adaptive(__first, __first_cut, __new_middle, __len11, 03352 __len22, __buffer, __buffer_size); 03353 std::__merge_adaptive(__new_middle, __second_cut, __last, 03354 __len1 - __len11, 03355 __len2 - __len22, __buffer, __buffer_size); 03356 } 03357 } 03358 03359 /** 03360 * @if maint 03361 * This is a helper function for the merge routines. 03362 * @endif 03363 */ 03364 template<typename _BidirectionalIterator, typename _Distance, typename _Pointer, 03365 typename _Compare> 03366 void 03367 __merge_adaptive(_BidirectionalIterator __first, 03368 _BidirectionalIterator __middle, 03369 _BidirectionalIterator __last, 03370 _Distance __len1, _Distance __len2, 03371 _Pointer __buffer, _Distance __buffer_size, 03372 _Compare __comp) 03373 { 03374 if (__len1 <= __len2 && __len1 <= __buffer_size) 03375 { 03376 _Pointer __buffer_end = std::copy(__first, __middle, __buffer); 03377 std::merge(__buffer, __buffer_end, __middle, __last, __first, __comp); 03378 } 03379 else if (__len2 <= __buffer_size) 03380 { 03381 _Pointer __buffer_end = std::copy(__middle, __last, __buffer); 03382 std::__merge_backward(__first, __middle, __buffer, __buffer_end, 03383 __last, __comp); 03384 } 03385 else 03386 { 03387 _BidirectionalIterator __first_cut = __first; 03388 _BidirectionalIterator __second_cut = __middle; 03389 _Distance __len11 = 0; 03390 _Distance __len22 = 0; 03391 if (__len1 > __len2) 03392 { 03393 __len11 = __len1 / 2; 03394 std::advance(__first_cut, __len11); 03395 __second_cut = std::lower_bound(__middle, __last, *__first_cut, 03396 __comp); 03397 __len22 = std::distance(__middle, __second_cut); 03398 } 03399 else 03400 { 03401 __len22 = __len2 / 2; 03402 std::advance(__second_cut, __len22); 03403 __first_cut = std::upper_bound(__first, __middle, *__second_cut, 03404 __comp); 03405 __len11 = std::distance(__first, __first_cut); 03406 } 03407 _BidirectionalIterator __new_middle = 03408 std::__rotate_adaptive(__first_cut, __middle, __second_cut, 03409 __len1 - __len11, __len22, __buffer, 03410 __buffer_size); 03411 std::__merge_adaptive(__first, __first_cut, __new_middle, __len11, 03412 __len22, __buffer, __buffer_size, __comp); 03413 std::__merge_adaptive(__new_middle, __second_cut, __last, 03414 __len1 - __len11, 03415 __len2 - __len22, __buffer, 03416 __buffer_size, __comp); 03417 } 03418 } 03419 03420 /** 03421 * @brief Merges two sorted ranges in place. 03422 * @param first An iterator. 03423 * @param middle Another iterator. 03424 * @param last Another iterator. 03425 * @return Nothing. 03426 * 03427 * Merges two sorted and consecutive ranges, [first,middle) and 03428 * [middle,last), and puts the result in [first,last). The output will 03429 * be sorted. The sort is @e stable, that is, for equivalent 03430 * elements in the two ranges, elements from the first range will always 03431 * come before elements from the second. 03432 * 03433 * If enough additional memory is available, this takes (last-first)-1 03434 * comparisons. Otherwise an NlogN algorithm is used, where N is 03435 * distance(first,last). 03436 */ 03437 template<typename _BidirectionalIterator> 03438 void 03439 inplace_merge(_BidirectionalIterator __first, 03440 _BidirectionalIterator __middle, 03441 _BidirectionalIterator __last) 03442 { 03443 typedef typename iterator_traits<_BidirectionalIterator>::value_type 03444 _ValueType; 03445 typedef typename iterator_traits<_BidirectionalIterator>::difference_type 03446 _DistanceType; 03447 03448 // concept requirements 03449 __glibcxx_function_requires(_Mutable_BidirectionalIteratorConcept< 03450 _BidirectionalIterator>) 03451 __glibcxx_function_requires(_LessThanComparableConcept<_ValueType>) 03452 __glibcxx_requires_sorted(__first, __middle); 03453 __glibcxx_requires_sorted(__middle, __last); 03454 03455 if (__first == __middle || __middle == __last) 03456 return; 03457 03458 _DistanceType __len1 = std::distance(__first, __middle); 03459 _DistanceType __len2 = std::distance(__middle, __last); 03460 03461 _Temporary_buffer<_BidirectionalIterator, _ValueType> __buf(__first, 03462 __last); 03463 if (__buf.begin() == 0) 03464 std::__merge_without_buffer(__first, __middle, __last, __len1, __len2); 03465 else 03466 std::__merge_adaptive(__first, __middle, __last, __len1, __len2, 03467 __buf.begin(), _DistanceType(__buf.size())); 03468 } 03469 03470 /** 03471 * @brief Merges two sorted ranges in place. 03472 * @param first An iterator. 03473 * @param middle Another iterator. 03474 * @param last Another iterator. 03475 * @param comp A functor to use for comparisons. 03476 * @return Nothing. 03477 * 03478 * Merges two sorted and consecutive ranges, [first,middle) and 03479 * [middle,last), and puts the result in [first,last). The output will 03480 * be sorted. The sort is @e stable, that is, for equivalent 03481 * elements in the two ranges, elements from the first range will always 03482 * come before elements from the second. 03483 * 03484 * If enough additional memory is available, this takes (last-first)-1 03485 * comparisons. Otherwise an NlogN algorithm is used, where N is 03486 * distance(first,last). 03487 * 03488 * The comparison function should have the same effects on ordering as 03489 * the function used for the initial sort. 03490 */ 03491 template<typename _BidirectionalIterator, typename _Compare> 03492 void 03493 inplace_merge(_BidirectionalIterator __first, 03494 _BidirectionalIterator __middle, 03495 _BidirectionalIterator __last, 03496 _Compare __comp) 03497 { 03498 typedef typename iterator_traits<_BidirectionalIterator>::value_type 03499 _ValueType; 03500 typedef typename iterator_traits<_BidirectionalIterator>::difference_type 03501 _DistanceType; 03502 03503 // concept requirements 03504 __glibcxx_function_requires(_Mutable_BidirectionalIteratorConcept< 03505 _BidirectionalIterator>) 03506 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, 03507 _ValueType, _ValueType>) 03508 __glibcxx_requires_sorted_pred(__first, __middle, __comp); 03509 __glibcxx_requires_sorted_pred(__middle, __last, __comp); 03510 03511 if (__first == __middle || __middle == __last) 03512 return; 03513 03514 const _DistanceType __len1 = std::distance(__first, __middle); 03515 const _DistanceType __len2 = std::distance(__middle, __last); 03516 03517 _Temporary_buffer<_BidirectionalIterator, _ValueType> __buf(__first, 03518 __last); 03519 if (__buf.begin() == 0) 03520 std::__merge_without_buffer(__first, __middle, __last, __len1, 03521 __len2, __comp); 03522 else 03523 std::__merge_adaptive(__first, __middle, __last, __len1, __len2, 03524 __buf.begin(), _DistanceType(__buf.size()), 03525 __comp); 03526 } 03527 03528 template<typename _RandomAccessIterator, typename _Pointer, 03529 typename _Distance> 03530 void 03531 __stable_sort_adaptive(_RandomAccessIterator __first, 03532 _RandomAccessIterator __last, 03533 _Pointer __buffer, _Distance __buffer_size) 03534 { 03535 const _Distance __len = (__last - __first + 1) / 2; 03536 const _RandomAccessIterator __middle = __first + __len; 03537 if (__len > __buffer_size) 03538 { 03539 std::__stable_sort_adaptive(__first, __middle, 03540 __buffer, __buffer_size); 03541 std::__stable_sort_adaptive(__middle, __last, 03542 __buffer, __buffer_size); 03543 } 03544 else 03545 { 03546 std::__merge_sort_with_buffer(__first, __middle, __buffer); 03547 std::__merge_sort_with_buffer(__middle, __last, __buffer); 03548 } 03549 std::__merge_adaptive(__first, __middle, __last, 03550 _Distance(__middle - __first), 03551 _Distance(__last - __middle), 03552 __buffer, __buffer_size); 03553 } 03554 03555 template<typename _RandomAccessIterator, typename _Pointer, 03556 typename _Distance, typename _Compare> 03557 void 03558 __stable_sort_adaptive(_RandomAccessIterator __first, 03559 _RandomAccessIterator __last, 03560 _Pointer __buffer, _Distance __buffer_size, 03561 _Compare __comp) 03562 { 03563 const _Distance __len = (__last - __first + 1) / 2; 03564 const _RandomAccessIterator __middle = __first + __len; 03565 if (__len > __buffer_size) 03566 { 03567 std::__stable_sort_adaptive(__first, __middle, __buffer, 03568 __buffer_size, __comp); 03569 std::__stable_sort_adaptive(__middle, __last, __buffer, 03570 __buffer_size, __comp); 03571 } 03572 else 03573 { 03574 std::__merge_sort_with_buffer(__first, __middle, __buffer, __comp); 03575 std::__merge_sort_with_buffer(__middle, __last, __buffer, __comp); 03576 } 03577 std::__merge_adaptive(__first, __middle, __last, 03578 _Distance(__middle - __first), 03579 _Distance(__last - __middle), 03580 __buffer, __buffer_size, 03581 __comp); 03582 } 03583 03584 /** 03585 * @brief Sort the elements of a sequence, preserving the relative order 03586 * of equivalent elements. 03587 * @param first An iterator. 03588 * @param last Another iterator. 03589 * @return Nothing. 03590 * 03591 * Sorts the elements in the range @p [first,last) in ascending order, 03592 * such that @p *(i+1)<*i is false for each iterator @p i in the range 03593 * @p [first,last-1). 03594 * 03595 * The relative ordering of equivalent elements is preserved, so any two 03596 * elements @p x and @p y in the range @p [first,last) such that 03597 * @p x<y is false and @p y<x is false will have the same relative 03598 * ordering after calling @p stable_sort(). 03599 */ 03600 template<typename _RandomAccessIterator> 03601 inline void 03602 stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last) 03603 { 03604 typedef typename iterator_traits<_RandomAccessIterator>::value_type 03605 _ValueType; 03606 typedef typename iterator_traits<_RandomAccessIterator>::difference_type 03607 _DistanceType; 03608 03609 // concept requirements 03610 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept< 03611 _RandomAccessIterator>) 03612 __glibcxx_function_requires(_LessThanComparableConcept<_ValueType>) 03613 __glibcxx_requires_valid_range(__first, __last); 03614 03615 _Temporary_buffer<_RandomAccessIterator, _ValueType> 03616 buf(__first, __last); 03617 if (buf.begin() == 0) 03618 std::__inplace_stable_sort(__first, __last); 03619 else 03620 std::__stable_sort_adaptive(__first, __last, buf.begin(), 03621 _DistanceType(buf.size())); 03622 } 03623 03624 /** 03625 * @brief Sort the elements of a sequence using a predicate for comparison, 03626 * preserving the relative order of equivalent elements. 03627 * @param first An iterator. 03628 * @param last Another iterator. 03629 * @param comp A comparison functor. 03630 * @return Nothing. 03631 * 03632 * Sorts the elements in the range @p [first,last) in ascending order, 03633 * such that @p comp(*(i+1),*i) is false for each iterator @p i in the 03634 * range @p [first,last-1). 03635 * 03636 * The relative ordering of equivalent elements is preserved, so any two 03637 * elements @p x and @p y in the range @p [first,last) such that 03638 * @p comp(x,y) is false and @p comp(y,x) is false will have the same 03639 * relative ordering after calling @p stable_sort(). 03640 */ 03641 template<typename _RandomAccessIterator, typename _Compare> 03642 inline void 03643 stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last, 03644 _Compare __comp) 03645 { 03646 typedef typename iterator_traits<_RandomAccessIterator>::value_type 03647 _ValueType; 03648 typedef typename iterator_traits<_RandomAccessIterator>::difference_type 03649 _DistanceType; 03650 03651 // concept requirements 03652 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept< 03653 _RandomAccessIterator>) 03654 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, 03655 _ValueType, 03656 _ValueType>) 03657 __glibcxx_requires_valid_range(__first, __last); 03658 03659 _Temporary_buffer<_RandomAccessIterator, _ValueType> buf(__first, __last); 03660 if (buf.begin() == 0) 03661 std::__inplace_stable_sort(__first, __last, __comp); 03662 else 03663 std::__stable_sort_adaptive(__first, __last, buf.begin(), 03664 _DistanceType(buf.size()), __comp); 03665 } 03666 03667 /** 03668 * @brief Sort a sequence just enough to find a particular position. 03669 * @param first An iterator. 03670 * @param nth Another iterator. 03671 * @param last Another iterator. 03672 * @return Nothing. 03673 * 03674 * Rearranges the elements in the range @p [first,last) so that @p *nth 03675 * is the same element that would have been in that position had the 03676 * whole sequence been sorted. 03677 * whole sequence been sorted. The elements either side of @p *nth are 03678 * not completely sorted, but for any iterator @i in the range 03679 * @p [first,nth) and any iterator @j in the range @p [nth,last) it 03680 * holds that @p *j<*i is false. 03681 */ 03682 template<typename _RandomAccessIterator> 03683 void 03684 nth_element(_RandomAccessIterator __first, 03685 _RandomAccessIterator __nth, 03686 _RandomAccessIterator __last) 03687 { 03688 typedef typename iterator_traits<_RandomAccessIterator>::value_type 03689 _ValueType; 03690 03691 // concept requirements 03692 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept< 03693 _RandomAccessIterator>) 03694 __glibcxx_function_requires(_LessThanComparableConcept<_ValueType>) 03695 __glibcxx_requires_valid_range(__first, __nth); 03696 __glibcxx_requires_valid_range(__nth, __last); 03697 03698 while (__last - __first > 3) 03699 { 03700 _RandomAccessIterator __cut = 03701 std::__unguarded_partition(__first, __last, 03702 _ValueType(std::__median(*__first, 03703 *(__first 03704 + (__last 03705 - __first) 03706 / 2), 03707 *(__last 03708 - 1)))); 03709 if (__cut <= __nth) 03710 __first = __cut; 03711 else 03712 __last = __cut; 03713 } 03714 std::__insertion_sort(__first, __last); 03715 } 03716 03717 /** 03718 * @brief Sort a sequence just enough to find a particular position 03719 * using a predicate for comparison. 03720 * @param first An iterator. 03721 * @param nth Another iterator. 03722 * @param last Another iterator. 03723 * @param comp A comparison functor. 03724 * @return Nothing. 03725 * 03726 * Rearranges the elements in the range @p [first,last) so that @p *nth 03727 * is the same element that would have been in that position had the 03728 * whole sequence been sorted. The elements either side of @p *nth are 03729 * not completely sorted, but for any iterator @i in the range 03730 * @p [first,nth) and any iterator @j in the range @p [nth,last) it 03731 * holds that @p comp(*j,*i) is false. 03732 */ 03733 template<typename _RandomAccessIterator, typename _Compare> 03734 void 03735 nth_element(_RandomAccessIterator __first, 03736 _RandomAccessIterator __nth, 03737 _RandomAccessIterator __last, 03738 _Compare __comp) 03739 { 03740 typedef typename iterator_traits<_RandomAccessIterator>::value_type 03741 _ValueType; 03742 03743 // concept requirements 03744 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept< 03745 _RandomAccessIterator>) 03746 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, 03747 _ValueType, _ValueType>) 03748 __glibcxx_requires_valid_range(__first, __nth); 03749 __glibcxx_requires_valid_range(__nth, __last); 03750 03751 while (__last - __first > 3) 03752 { 03753 _RandomAccessIterator __cut = 03754 std::__unguarded_partition(__first, __last, 03755 _ValueType(std::__median(*__first, 03756 *(__first 03757 + (__last 03758 - __first) 03759 / 2), 03760 *(__last - 1), 03761 __comp)), __comp); 03762 if (__cut <= __nth) 03763 __first = __cut; 03764 else 03765 __last = __cut; 03766 } 03767 std::__insertion_sort(__first, __last, __comp); 03768 } 03769 03770 /** 03771 * @brief Finds the largest subrange in which @a val could be inserted 03772 * at any place in it without changing the ordering. 03773 * @param first An iterator. 03774 * @param last Another iterator. 03775 * @param val The search term. 03776 * @return An pair of iterators defining the subrange. 03777 * @ingroup binarysearch 03778 * 03779 * This is equivalent to 03780 * @code 03781 * std::make_pair(lower_bound(first, last, val), 03782 * upper_bound(first, last, val)) 03783 * @endcode 03784 * but does not actually call those functions. 03785 */ 03786 template<typename _ForwardIterator, typename _Tp> 03787 pair<_ForwardIterator, _ForwardIterator> 03788 equal_range(_ForwardIterator __first, _ForwardIterator __last, 03789 const _Tp& __val) 03790 { 03791 typedef typename iterator_traits<_ForwardIterator>::value_type 03792 _ValueType; 03793 typedef typename iterator_traits<_ForwardIterator>::difference_type 03794 _DistanceType; 03795 03796 // concept requirements 03797 // See comments on lower_bound. 03798 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) 03799 __glibcxx_function_requires(_SameTypeConcept<_Tp, _ValueType>) 03800 __glibcxx_function_requires(_LessThanComparableConcept<_Tp>) 03801 __glibcxx_requires_partitioned(__first, __last, __val); 03802 03803 _DistanceType __len = std::distance(__first, __last); 03804 _DistanceType __half; 03805 _ForwardIterator __middle, __left, __right; 03806 03807 while (__len > 0) 03808 { 03809 __half = __len >> 1; 03810 __middle = __first; 03811 std::advance(__middle, __half); 03812 if (*__middle < __val) 03813 { 03814 __first = __middle; 03815 ++__first; 03816 __len = __len - __half - 1; 03817 } 03818 else if (__val < *__middle) 03819 __len = __half; 03820 else 03821 { 03822 __left = std::lower_bound(__first, __middle, __val); 03823 std::advance(__first, __len); 03824 __right = std::upper_bound(++__middle, __first, __val); 03825 return pair<_ForwardIterator, _ForwardIterator>(__left, __right); 03826 } 03827 } 03828 return pair<_ForwardIterator, _ForwardIterator>(__first, __first); 03829 } 03830 03831 /** 03832 * @brief Finds the largest subrange in which @a val could be inserted 03833 * at any place in it without changing the ordering. 03834 * @param first An iterator. 03835 * @param last Another iterator. 03836 * @param val The search term. 03837 * @param comp A functor to use for comparisons. 03838 * @return An pair of iterators defining the subrange. 03839 * @ingroup binarysearch 03840 * 03841 * This is equivalent to 03842 * @code 03843 * std::make_pair(lower_bound(first, last, val, comp), 03844 * upper_bound(first, last, val, comp)) 03845 * @endcode 03846 * but does not actually call those functions. 03847 */ 03848 template<typename _ForwardIterator, typename _Tp, typename _Compare> 03849 pair<_ForwardIterator, _ForwardIterator> 03850 equal_range(_ForwardIterator __first, _ForwardIterator __last, 03851 const _Tp& __val, 03852 _Compare __comp) 03853 { 03854 typedef typename iterator_traits<_ForwardIterator>::value_type 03855 _ValueType; 03856 typedef typename iterator_traits<_ForwardIterator>::difference_type 03857 _DistanceType; 03858 03859 // concept requirements 03860 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) 03861 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, 03862 _ValueType, _Tp>) 03863 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, 03864 _Tp, _ValueType>) 03865 __glibcxx_requires_partitioned_pred(__first, __last, __val, __comp); 03866 03867 _DistanceType __len = std::distance(__first, __last); 03868 _DistanceType __half; 03869 _ForwardIterator __middle, __left, __right; 03870 03871 while (__len > 0) 03872 { 03873 __half = __len >> 1; 03874 __middle = __first; 03875 std::advance(__middle, __half); 03876 if (__comp(*__middle, __val)) 03877 { 03878 __first = __middle; 03879 ++__first; 03880 __len = __len - __half - 1; 03881 } 03882 else if (__comp(__val, *__middle)) 03883 __len = __half; 03884 else 03885 { 03886 __left = std::lower_bound(__first, __middle, __val, __comp); 03887 std::advance(__first, __len); 03888 __right = std::upper_bound(++__middle, __first, __val, __comp); 03889 return pair<_ForwardIterator, _ForwardIterator>(__left, __right); 03890 } 03891 } 03892 return pair<_ForwardIterator, _ForwardIterator>(__first, __first); 03893 } 03894 03895 /** 03896 * @brief Determines whether an element exists in a range. 03897 * @param first An iterator. 03898 * @param last Another iterator. 03899 * @param val The search term. 03900 * @return True if @a val (or its equivelent) is in [@a first,@a last ]. 03901 * @ingroup binarysearch 03902 * 03903 * Note that this does not actually return an iterator to @a val. For 03904 * that, use std::find or a container's specialized find member functions. 03905 */ 03906 template<typename _ForwardIterator, typename _Tp> 03907 bool 03908 binary_search(_ForwardIterator __first, _ForwardIterator __last, 03909 const _Tp& __val) 03910 { 03911 // concept requirements 03912 // See comments on lower_bound. 03913 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) 03914 __glibcxx_function_requires(_SameTypeConcept<_Tp, 03915 typename iterator_traits<_ForwardIterator>::value_type>) 03916 __glibcxx_function_requires(_LessThanComparableConcept<_Tp>) 03917 __glibcxx_requires_partitioned(__first, __last, __val); 03918 03919 _ForwardIterator __i = std::lower_bound(__first, __last, __val); 03920 return __i != __last && !(__val < *__i); 03921 } 03922 03923 /** 03924 * @brief Determines whether an element exists in a range. 03925 * @param first An iterator. 03926 * @param last Another iterator. 03927 * @param val The search term. 03928 * @param comp A functor to use for comparisons. 03929 * @return True if @a val (or its equivelent) is in [@a first,@a last ]. 03930 * @ingroup binarysearch 03931 * 03932 * Note that this does not actually return an iterator to @a val. For 03933 * that, use std::find or a container's specialized find member functions. 03934 * 03935 * The comparison function should have the same effects on ordering as 03936 * the function used for the initial sort. 03937 */ 03938 template<typename _ForwardIterator, typename _Tp, typename _Compare> 03939 bool 03940 binary_search(_ForwardIterator __first, _ForwardIterator __last, 03941 const _Tp& __val, _Compare __comp) 03942 { 03943 // concept requirements 03944 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) 03945 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, 03946 typename iterator_traits<_ForwardIterator>::value_type, _Tp>) 03947 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, _Tp, 03948 typename iterator_traits<_ForwardIterator>::value_type>) 03949 __glibcxx_requires_partitioned_pred(__first, __last, __val, __comp); 03950 03951 _ForwardIterator __i = std::lower_bound(__first, __last, __val, __comp); 03952 return __i != __last && !__comp(__val, *__i); 03953 } 03954 03955 // Set algorithms: includes, set_union, set_intersection, set_difference, 03956 // set_symmetric_difference. All of these algorithms have the precondition 03957 // that their input ranges are sorted and the postcondition that their output 03958 // ranges are sorted. 03959 03960 /** 03961 * @brief Determines whether all elements of a sequence exists in a range. 03962 * @param first1 Start of search range. 03963 * @param last1 End of search range. 03964 * @param first2 Start of sequence 03965 * @param last2 End of sequence. 03966 * @return True if each element in [first2,last2) is contained in order 03967 * within [first1,last1). False otherwise. 03968 * @ingroup setoperations 03969 * 03970 * This operation expects both [first1,last1) and [first2,last2) to be 03971 * sorted. Searches for the presence of each element in [first2,last2) 03972 * within [first1,last1). The iterators over each range only move forward, 03973 * so this is a linear algorithm. If an element in [first2,last2) is not 03974 * found before the search iterator reaches @a last2, false is returned. 03975 */ 03976 template<typename _InputIterator1, typename _InputIterator2> 03977 bool 03978 includes(_InputIterator1 __first1, _InputIterator1 __last1, 03979 _InputIterator2 __first2, _InputIterator2 __last2) 03980 { 03981 // concept requirements 03982 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>) 03983 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>) 03984 __glibcxx_function_requires(_SameTypeConcept< 03985 typename iterator_traits<_InputIterator1>::value_type, 03986 typename iterator_traits<_InputIterator2>::value_type>) 03987 __glibcxx_function_requires(_LessThanComparableConcept< 03988 typename iterator_traits<_InputIterator1>::value_type>) 03989 __glibcxx_requires_sorted(__first1, __last1); 03990 __glibcxx_requires_sorted(__first2, __last2); 03991 03992 while (__first1 != __last1 && __first2 != __last2) 03993 if (*__first2 < *__first1) 03994 return false; 03995 else if(*__first1 < *__first2) 03996 ++__first1; 03997 else 03998 ++__first1, ++__first2; 03999 04000 return __first2 == __last2; 04001 } 04002 04003 /** 04004 * @brief Determines whether all elements of a sequence exists in a range 04005 * using comparison. 04006 * @param first1 Start of search range. 04007 * @param last1 End of search range. 04008 * @param first2 Start of sequence 04009 * @param last2 End of sequence. 04010 * @param comp Comparison function to use. 04011 * @return True if each element in [first2,last2) is contained in order 04012 * within [first1,last1) according to comp. False otherwise. 04013 * @ingroup setoperations 04014 * 04015 * This operation expects both [first1,last1) and [first2,last2) to be 04016 * sorted. Searches for the presence of each element in [first2,last2) 04017 * within [first1,last1), using comp to decide. The iterators over each 04018 * range only move forward, so this is a linear algorithm. If an element 04019 * in [first2,last2) is not found before the search iterator reaches @a 04020 * last2, false is returned. 04021 */ 04022 template<typename _InputIterator1, typename _InputIterator2, 04023 typename _Compare> 04024 bool 04025 includes(_InputIterator1 __first1, _InputIterator1 __last1, 04026 _InputIterator2 __first2, _InputIterator2 __last2, _Compare __comp) 04027 { 04028 // concept requirements 04029 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>) 04030 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>) 04031 __glibcxx_function_requires(_SameTypeConcept< 04032 typename iterator_traits<_InputIterator1>::value_type, 04033 typename iterator_traits<_InputIterator2>::value_type>) 04034 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, 04035 typename iterator_traits<_InputIterator1>::value_type, 04036 typename iterator_traits<_InputIterator2>::value_type>) 04037 __glibcxx_requires_sorted_pred(__first1, __last1, __comp); 04038 __glibcxx_requires_sorted_pred(__first2, __last2, __comp); 04039 04040 while (__first1 != __last1 && __first2 != __last2) 04041 if (__comp(*__first2, *__first1)) 04042 return false; 04043 else if(__comp(*__first1, *__first2)) 04044 ++__first1; 04045 else 04046 ++__first1, ++__first2; 04047 04048 return __first2 == __last2; 04049 } 04050 04051 /** 04052 * @brief Return the union of two sorted ranges. 04053 * @param first1 Start of first range. 04054 * @param last1 End of first range. 04055 * @param first2 Start of second range. 04056 * @param last2 End of second range. 04057 * @return End of the output range. 04058 * @ingroup setoperations 04059 * 04060 * This operation iterates over both ranges, copying elements present in 04061 * each range in order to the output range. Iterators increment for each 04062 * range. When the current element of one range is less than the other, 04063 * that element is copied and the iterator advanced. If an element is 04064 * contained in both ranges, the element from the first range is copied and 04065 * both ranges advance. The output range may not overlap either input 04066 * range. 04067 */ 04068 template<typename _InputIterator1, typename _InputIterator2, 04069 typename _OutputIterator> 04070 _OutputIterator 04071 set_union(_InputIterator1 __first1, _InputIterator1 __last1, 04072 _InputIterator2 __first2, _InputIterator2 __last2, 04073 _OutputIterator __result) 04074 { 04075 // concept requirements 04076 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>) 04077 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>) 04078 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, 04079 typename iterator_traits<_InputIterator1>::value_type>) 04080 __glibcxx_function_requires(_SameTypeConcept< 04081 typename iterator_traits<_InputIterator1>::value_type, 04082 typename iterator_traits<_InputIterator2>::value_type>) 04083 __glibcxx_function_requires(_LessThanComparableConcept< 04084 typename iterator_traits<_InputIterator1>::value_type>) 04085 __glibcxx_requires_sorted(__first1, __last1); 04086 __glibcxx_requires_sorted(__first2, __last2); 04087 04088 while (__first1 != __last1 && __first2 != __last2) 04089 { 04090 if (*__first1 < *__first2) 04091 { 04092 *__result = *__first1; 04093 ++__first1; 04094 } 04095 else if (*__first2 < *__first1) 04096 { 04097 *__result = *__first2; 04098 ++__first2; 04099 } 04100 else 04101 { 04102 *__result = *__first1; 04103 ++__first1; 04104 ++__first2; 04105 } 04106 ++__result; 04107 } 04108 return std::copy(__first2, __last2, std::copy(__first1, __last1, 04109 __result)); 04110 } 04111 04112 /** 04113 * @brief Return the union of two sorted ranges using a comparison functor. 04114 * @param first1 Start of first range. 04115 * @param last1 End of first range. 04116 * @param first2 Start of second range. 04117 * @param last2 End of second range. 04118 * @param comp The comparison functor. 04119 * @return End of the output range. 04120 * @ingroup setoperations 04121 * 04122 * This operation iterates over both ranges, copying elements present in 04123 * each range in order to the output range. Iterators increment for each 04124 * range. When the current element of one range is less than the other 04125 * according to @a comp, that element is copied and the iterator advanced. 04126 * If an equivalent element according to @a comp is contained in both 04127 * ranges, the element from the first range is copied and both ranges 04128 * advance. The output range may not overlap either input range. 04129 */ 04130 template<typename _InputIterator1, typename _InputIterator2, 04131 typename _OutputIterator, typename _Compare> 04132 _OutputIterator 04133 set_union(_InputIterator1 __first1, _InputIterator1 __last1, 04134 _InputIterator2 __first2, _InputIterator2 __last2, 04135 _OutputIterator __result, _Compare __comp) 04136 { 04137 // concept requirements 04138 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>) 04139 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>) 04140 __glibcxx_function_requires(_SameTypeConcept< 04141 typename iterator_traits<_InputIterator1>::value_type, 04142 typename iterator_traits<_InputIterator2>::value_type>) 04143 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, 04144 typename iterator_traits<_InputIterator1>::value_type>) 04145 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, 04146 typename iterator_traits<_InputIterator1>::value_type, 04147 typename iterator_traits<_InputIterator2>::value_type>) 04148 __glibcxx_requires_sorted_pred(__first1, __last1, __comp); 04149 __glibcxx_requires_sorted_pred(__first2, __last2, __comp); 04150 04151 while (__first1 != __last1 && __first2 != __last2) 04152 { 04153 if (__comp(*__first1, *__first2)) 04154 { 04155 *__result = *__first1; 04156 ++__first1; 04157 } 04158 else if (__comp(*__first2, *__first1)) 04159 { 04160 *__result = *__first2; 04161 ++__first2; 04162 } 04163 else 04164 { 04165 *__result = *__first1; 04166 ++__first1; 04167 ++__first2; 04168 } 04169 ++__result; 04170 } 04171 return std::copy(__first2, __last2, std::copy(__first1, __last1, 04172 __result)); 04173 } 04174 04175 /** 04176 * @brief Return the intersection of two sorted ranges. 04177 * @param first1 Start of first range. 04178 * @param last1 End of first range. 04179 * @param first2 Start of second range. 04180 * @param last2 End of second range. 04181 * @return End of the output range. 04182 * @ingroup setoperations 04183 * 04184 * This operation iterates over both ranges, copying elements present in 04185 * both ranges in order to the output range. Iterators increment for each 04186 * range. When the current element of one range is less than the other, 04187 * that iterator advances. If an element is contained in both ranges, the 04188 * element from the first range is copied and both ranges advance. The 04189 * output range may not overlap either input range. 04190 */ 04191 template<typename _InputIterator1, typename _InputIterator2, 04192 typename _OutputIterator> 04193 _OutputIterator 04194 set_intersection(_InputIterator1 __first1, _InputIterator1 __last1, 04195 _InputIterator2 __first2, _InputIterator2 __last2, 04196 _OutputIterator __result) 04197 { 04198 // concept requirements 04199 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>) 04200 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>) 04201 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, 04202 typename iterator_traits<_InputIterator1>::value_type>) 04203 __glibcxx_function_requires(_SameTypeConcept< 04204 typename iterator_traits<_InputIterator1>::value_type, 04205 typename iterator_traits<_InputIterator2>::value_type>) 04206 __glibcxx_function_requires(_LessThanComparableConcept< 04207 typename iterator_traits<_InputIterator1>::value_type>) 04208 __glibcxx_requires_sorted(__first1, __last1); 04209 __glibcxx_requires_sorted(__first2, __last2); 04210 04211 while (__first1 != __last1 && __first2 != __last2) 04212 if (*__first1 < *__first2) 04213 ++__first1; 04214 else if (*__first2 < *__first1) 04215 ++__first2; 04216 else 04217 { 04218 *__result = *__first1; 04219 ++__first1; 04220 ++__first2; 04221 ++__result; 04222 } 04223 return __result; 04224 } 04225 04226 /** 04227 * @brief Return the intersection of two sorted ranges using comparison 04228 * functor. 04229 * @param first1 Start of first range. 04230 * @param last1 End of first range. 04231 * @param first2 Start of second range. 04232 * @param last2 End of second range. 04233 * @param comp The comparison functor. 04234 * @return End of the output range. 04235 * @ingroup setoperations 04236 * 04237 * This operation iterates over both ranges, copying elements present in 04238 * both ranges in order to the output range. Iterators increment for each 04239 * range. When the current element of one range is less than the other 04240 * according to @a comp, that iterator advances. If an element is 04241 * contained in both ranges according to @a comp, the element from the 04242 * first range is copied and both ranges advance. The output range may not 04243 * overlap either input range. 04244 */ 04245 template<typename _InputIterator1, typename _InputIterator2, 04246 typename _OutputIterator, typename _Compare> 04247 _OutputIterator 04248 set_intersection(_InputIterator1 __first1, _InputIterator1 __last1, 04249 _InputIterator2 __first2, _InputIterator2 __last2, 04250 _OutputIterator __result, _Compare __comp) 04251 { 04252 // concept requirements 04253 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>) 04254 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>) 04255 __glibcxx_function_requires(_SameTypeConcept< 04256 typename iterator_traits<_InputIterator1>::value_type, 04257 typename iterator_traits<_InputIterator2>::value_type>) 04258 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, 04259 typename iterator_traits<_InputIterator1>::value_type>) 04260 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, 04261 typename iterator_traits<_InputIterator1>::value_type, 04262 typename iterator_traits<_InputIterator2>::value_type>) 04263 __glibcxx_requires_sorted_pred(__first1, __last1, __comp); 04264 __glibcxx_requires_sorted_pred(__first2, __last2, __comp); 04265 04266 while (__first1 != __last1 && __first2 != __last2) 04267 if (__comp(*__first1, *__first2)) 04268 ++__first1; 04269 else if (__comp(*__first2, *__first1)) 04270 ++__first2; 04271 else 04272 { 04273 *__result = *__first1; 04274 ++__first1; 04275 ++__first2; 04276 ++__result; 04277 } 04278 return __result; 04279 } 04280 04281 /** 04282 * @brief Return the difference of two sorted ranges. 04283 * @param first1 Start of first range. 04284 * @param last1 End of first range. 04285 * @param first2 Start of second range. 04286 * @param last2 End of second range. 04287 * @return End of the output range. 04288 * @ingroup setoperations 04289 * 04290 * This operation iterates over both ranges, copying elements present in 04291 * the first range but not the second in order to the output range. 04292 * Iterators increment for each range. When the current element of the 04293 * first range is less than the second, that element is copied and the 04294 * iterator advances. If the current element of the second range is less, 04295 * the iterator advances, but no element is copied. If an element is 04296 * contained in both ranges, no elements are copied and both ranges 04297 * advance. The output range may not overlap either input range. 04298 */ 04299 template<typename _InputIterator1, typename _InputIterator2, 04300 typename _OutputIterator> 04301 _OutputIterator 04302 set_difference(_InputIterator1 __first1, _InputIterator1 __last1, 04303 _InputIterator2 __first2, _InputIterator2 __last2, 04304 _OutputIterator __result) 04305 { 04306 // concept requirements 04307 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>) 04308 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>) 04309 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, 04310 typename iterator_traits<_InputIterator1>::value_type>) 04311 __glibcxx_function_requires(_SameTypeConcept< 04312 typename iterator_traits<_InputIterator1>::value_type, 04313 typename iterator_traits<_InputIterator2>::value_type>) 04314 __glibcxx_function_requires(_LessThanComparableConcept< 04315 typename iterator_traits<_InputIterator1>::value_type>) 04316 __glibcxx_requires_sorted(__first1, __last1); 04317 __glibcxx_requires_sorted(__first2, __last2); 04318 04319 while (__first1 != __last1 && __first2 != __last2) 04320 if (*__first1 < *__first2) 04321 { 04322 *__result = *__first1; 04323 ++__first1; 04324 ++__result; 04325 } 04326 else if (*__first2 < *__first1) 04327 ++__first2; 04328 else 04329 { 04330 ++__first1; 04331 ++__first2; 04332 } 04333 return std::copy(__first1, __last1, __result); 04334 } 04335 04336 /** 04337 * @brief Return the difference of two sorted ranges using comparison 04338 * functor. 04339 * @param first1 Start of first range. 04340 * @param last1 End of first range. 04341 * @param first2 Start of second range. 04342 * @param last2 End of second range. 04343 * @param comp The comparison functor. 04344 * @return End of the output range. 04345 * @ingroup setoperations 04346 * 04347 * This operation iterates over both ranges, copying elements present in 04348 * the first range but not the second in order to the output range. 04349 * Iterators increment for each range. When the current element of the 04350 * first range is less than the second according to @a comp, that element 04351 * is copied and the iterator advances. If the current element of the 04352 * second range is less, no element is copied and the iterator advances. 04353 * If an element is contained in both ranges according to @a comp, no 04354 * elements are copied and both ranges advance. The output range may not 04355 * overlap either input range. 04356 */ 04357 template<typename _InputIterator1, typename _InputIterator2, 04358 typename _OutputIterator, typename _Compare> 04359 _OutputIterator 04360 set_difference(_InputIterator1 __first1, _InputIterator1 __last1, 04361 _InputIterator2 __first2, _InputIterator2 __last2, 04362 _OutputIterator __result, _Compare __comp) 04363 { 04364 // concept requirements 04365 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>) 04366 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>) 04367 __glibcxx_function_requires(_SameTypeConcept< 04368 typename iterator_traits<_InputIterator1>::value_type, 04369 typename iterator_traits<_InputIterator2>::value_type>) 04370 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, 04371 typename iterator_traits<_InputIterator1>::value_type>) 04372 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, 04373 typename iterator_traits<_InputIterator1>::value_type, 04374 typename iterator_traits<_InputIterator2>::value_type>) 04375 __glibcxx_requires_sorted_pred(__first1, __last1, __comp); 04376 __glibcxx_requires_sorted_pred(__first2, __last2, __comp); 04377 04378 while (__first1 != __last1 && __first2 != __last2) 04379 if (__comp(*__first1, *__first2)) 04380 { 04381 *__result = *__first1; 04382 ++__first1; 04383 ++__result; 04384 } 04385 else if (__comp(*__first2, *__first1)) 04386 ++__first2; 04387 else 04388 { 04389 ++__first1; 04390 ++__first2; 04391 } 04392 return std::copy(__first1, __last1, __result); 04393 } 04394 04395 /** 04396 * @brief Return the symmetric difference of two sorted ranges. 04397 * @param first1 Start of first range. 04398 * @param last1 End of first range. 04399 * @param first2 Start of second range. 04400 * @param last2 End of second range. 04401 * @return End of the output range. 04402 * @ingroup setoperations 04403 * 04404 * This operation iterates over both ranges, copying elements present in 04405 * one range but not the other in order to the output range. Iterators 04406 * increment for each range. When the current element of one range is less 04407 * than the other, that element is copied and the iterator advances. If an 04408 * element is contained in both ranges, no elements are copied and both 04409 * ranges advance. The output range may not overlap either input range. 04410 */ 04411 template<typename _InputIterator1, typename _InputIterator2, 04412 typename _OutputIterator> 04413 _OutputIterator 04414 set_symmetric_difference(_InputIterator1 __first1, _InputIterator1 __last1, 04415 _InputIterator2 __first2, _InputIterator2 __last2, 04416 _OutputIterator __result) 04417 { 04418 // concept requirements 04419 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>) 04420 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>) 04421 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, 04422 typename iterator_traits<_InputIterator1>::value_type>) 04423 __glibcxx_function_requires(_SameTypeConcept< 04424 typename iterator_traits<_InputIterator1>::value_type, 04425 typename iterator_traits<_InputIterator2>::value_type>) 04426 __glibcxx_function_requires(_LessThanComparableConcept< 04427 typename iterator_traits<_InputIterator1>::value_type>) 04428 __glibcxx_requires_sorted(__first1, __last1); 04429 __glibcxx_requires_sorted(__first2, __last2); 04430 04431 while (__first1 != __last1 && __first2 != __last2) 04432 if (*__first1 < *__first2) 04433 { 04434 *__result = *__first1; 04435 ++__first1; 04436 ++__result; 04437 } 04438 else if (*__first2 < *__first1) 04439 { 04440 *__result = *__first2; 04441 ++__first2; 04442 ++__result; 04443 } 04444 else 04445 { 04446 ++__first1; 04447 ++__first2; 04448 } 04449 return std::copy(__first2, __last2, std::copy(__first1, 04450 __last1, __result)); 04451 } 04452 04453 /** 04454 * @brief Return the symmetric difference of two sorted ranges using 04455 * comparison functor. 04456 * @param first1 Start of first range. 04457 * @param last1 End of first range. 04458 * @param first2 Start of second range. 04459 * @param last2 End of second range. 04460 * @param comp The comparison functor. 04461 * @return End of the output range. 04462 * @ingroup setoperations 04463 * 04464 * This operation iterates over both ranges, copying elements present in 04465 * one range but not the other in order to the output range. Iterators 04466 * increment for each range. When the current element of one range is less 04467 * than the other according to @a comp, that element is copied and the 04468 * iterator advances. If an element is contained in both ranges according 04469 * to @a comp, no elements are copied and both ranges advance. The output 04470 * range may not overlap either input range. 04471 */ 04472 template<typename _InputIterator1, typename _InputIterator2, 04473 typename _OutputIterator, typename _Compare> 04474 _OutputIterator 04475 set_symmetric_difference(_InputIterator1 __first1, _InputIterator1 __last1, 04476 _InputIterator2 __first2, _InputIterator2 __last2, 04477 _OutputIterator __result, 04478 _Compare __comp) 04479 { 04480 // concept requirements 04481 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>) 04482 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>) 04483 __glibcxx_function_requires(_SameTypeConcept< 04484 typename iterator_traits<_InputIterator1>::value_type, 04485 typename iterator_traits<_InputIterator2>::value_type>) 04486 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, 04487 typename iterator_traits<_InputIterator1>::value_type>) 04488 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, 04489 typename iterator_traits<_InputIterator1>::value_type, 04490 typename iterator_traits<_InputIterator2>::value_type>) 04491 __glibcxx_requires_sorted_pred(__first1, __last1, __comp); 04492 __glibcxx_requires_sorted_pred(__first2, __last2, __comp); 04493 04494 while (__first1 != __last1 && __first2 != __last2) 04495 if (__comp(*__first1, *__first2)) 04496 { 04497 *__result = *__first1; 04498 ++__first1; 04499 ++__result; 04500 } 04501 else if (__comp(*__first2, *__first1)) 04502 { 04503 *__result = *__first2; 04504 ++__first2; 04505 ++__result; 04506 } 04507 else 04508 { 04509 ++__first1; 04510 ++__first2; 04511 } 04512 return std::copy(__first2, __last2, std::copy(__first1, 04513 __last1, __result)); 04514 } 04515 04516 // min_element and max_element, with and without an explicitly supplied 04517 // comparison function. 04518 04519 /** 04520 * @brief Return the maximum element in a range. 04521 * @param first Start of range. 04522 * @param last End of range. 04523 * @return Iterator referencing the first instance of the largest value. 04524 */ 04525 template<typename _ForwardIterator> 04526 _ForwardIterator 04527 max_element(_ForwardIterator __first, _ForwardIterator __last) 04528 { 04529 // concept requirements 04530 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) 04531 __glibcxx_function_requires(_LessThanComparableConcept< 04532 typename iterator_traits<_ForwardIterator>::value_type>) 04533 __glibcxx_requires_valid_range(__first, __last); 04534 04535 if (__first == __last) 04536 return __first; 04537 _ForwardIterator __result = __first; 04538 while (++__first != __last) 04539 if (*__result < *__first) 04540 __result = __first; 04541 return __result; 04542 } 04543 04544 /** 04545 * @brief Return the maximum element in a range using comparison functor. 04546 * @param first Start of range. 04547 * @param last End of range. 04548 * @param comp Comparison functor. 04549 * @return Iterator referencing the first instance of the largest value 04550 * according to comp. 04551 */ 04552 template<typename _ForwardIterator, typename _Compare> 04553 _ForwardIterator 04554 max_element(_ForwardIterator __first, _ForwardIterator __last, 04555 _Compare __comp) 04556 { 04557 // concept requirements 04558 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) 04559 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, 04560 typename iterator_traits<_ForwardIterator>::value_type, 04561 typename iterator_traits<_ForwardIterator>::value_type>) 04562 __glibcxx_requires_valid_range(__first, __last); 04563 04564 if (__first == __last) return __first; 04565 _ForwardIterator __result = __first; 04566 while (++__first != __last) 04567 if (__comp(*__result, *__first)) __result = __first; 04568 return __result; 04569 } 04570 04571 /** 04572 * @brief Return the minimum element in a range. 04573 * @param first Start of range. 04574 * @param last End of range. 04575 * @return Iterator referencing the first instance of the smallest value. 04576 */ 04577 template<typename _ForwardIterator> 04578 _ForwardIterator 04579 min_element(_ForwardIterator __first, _ForwardIterator __last) 04580 { 04581 // concept requirements 04582 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) 04583 __glibcxx_function_requires(_LessThanComparableConcept< 04584 typename iterator_traits<_ForwardIterator>::value_type>) 04585 __glibcxx_requires_valid_range(__first, __last); 04586 04587 if (__first == __last) 04588 return __first; 04589 _ForwardIterator __result = __first; 04590 while (++__first != __last) 04591 if (*__first < *__result) 04592 __result = __first; 04593 return __result; 04594 } 04595 04596 /** 04597 * @brief Return the minimum element in a range using comparison functor. 04598 * @param first Start of range. 04599 * @param last End of range. 04600 * @param comp Comparison functor. 04601 * @return Iterator referencing the first instance of the smallest value 04602 * according to comp. 04603 */ 04604 template<typename _ForwardIterator, typename _Compare> 04605 _ForwardIterator 04606 min_element(_ForwardIterator __first, _ForwardIterator __last, 04607 _Compare __comp) 04608 { 04609 // concept requirements 04610 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) 04611 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, 04612 typename iterator_traits<_ForwardIterator>::value_type, 04613 typename iterator_traits<_ForwardIterator>::value_type>) 04614 __glibcxx_requires_valid_range(__first, __last); 04615 04616 if (__first == __last) 04617 return __first; 04618 _ForwardIterator __result = __first; 04619 while (++__first != __last) 04620 if (__comp(*__first, *__result)) 04621 __result = __first; 04622 return __result; 04623 } 04624 04625 // next_permutation and prev_permutation, with and without an explicitly 04626 // supplied comparison function. 04627 04628 /** 04629 * @brief Permute range into the next "dictionary" ordering. 04630 * @param first Start of range. 04631 * @param last End of range. 04632 * @return False if wrapped to first permutation, true otherwise. 04633 * 04634 * Treats all permutations of the range as a set of "dictionary" sorted 04635 * sequences. Permutes the current sequence into the next one of this set. 04636 * Returns true if there are more sequences to generate. If the sequence 04637 * is the largest of the set, the smallest is generated and false returned. 04638 */ 04639 template<typename _BidirectionalIterator> 04640 bool 04641 next_permutation(_BidirectionalIterator __first, 04642 _BidirectionalIterator __last) 04643 { 04644 // concept requirements 04645 __glibcxx_function_requires(_BidirectionalIteratorConcept< 04646 _BidirectionalIterator>) 04647 __glibcxx_function_requires(_LessThanComparableConcept< 04648 typename iterator_traits<_BidirectionalIterator>::value_type>) 04649 __glibcxx_requires_valid_range(__first, __last); 04650 04651 if (__first == __last) 04652 return false; 04653 _BidirectionalIterator __i = __first; 04654 ++__i; 04655 if (__i == __last) 04656 return false; 04657 __i = __last; 04658 --__i; 04659 04660 for(;;) 04661 { 04662 _BidirectionalIterator __ii = __i; 04663 --__i; 04664 if (*__i < *__ii) 04665 { 04666 _BidirectionalIterator __j = __last; 04667 while (!(*__i < *--__j)) 04668 {} 04669 std::iter_swap(__i, __j); 04670 std::reverse(__ii, __last); 04671 return true; 04672 } 04673 if (__i == __first) 04674 { 04675 std::reverse(__first, __last); 04676 return false; 04677 } 04678 } 04679 } 04680 04681 /** 04682 * @brief Permute range into the next "dictionary" ordering using 04683 * comparison functor. 04684 * @param first Start of range. 04685 * @param last End of range. 04686 * @param comp 04687 * @return False if wrapped to first permutation, true otherwise. 04688 * 04689 * Treats all permutations of the range [first,last) as a set of 04690 * "dictionary" sorted sequences ordered by @a comp. Permutes the current 04691 * sequence into the next one of this set. Returns true if there are more 04692 * sequences to generate. If the sequence is the largest of the set, the 04693 * smallest is generated and false returned. 04694 */ 04695 template<typename _BidirectionalIterator, typename _Compare> 04696 bool 04697 next_permutation(_BidirectionalIterator __first, 04698 _BidirectionalIterator __last, _Compare __comp) 04699 { 04700 // concept requirements 04701 __glibcxx_function_requires(_BidirectionalIteratorConcept< 04702 _BidirectionalIterator>) 04703 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, 04704 typename iterator_traits<_BidirectionalIterator>::value_type, 04705 typename iterator_traits<_BidirectionalIterator>::value_type>) 04706 __glibcxx_requires_valid_range(__first, __last); 04707 04708 if (__first == __last) 04709 return false; 04710 _BidirectionalIterator __i = __first; 04711 ++__i; 04712 if (__i == __last) 04713 return false; 04714 __i = __last; 04715 --__i; 04716 04717 for(;;) 04718 { 04719 _BidirectionalIterator __ii = __i; 04720 --__i; 04721 if (__comp(*__i, *__ii)) 04722 { 04723 _BidirectionalIterator __j = __last; 04724 while (!__comp(*__i, *--__j)) 04725 {} 04726 std::iter_swap(__i, __j); 04727 std::reverse(__ii, __last); 04728 return true; 04729 } 04730 if (__i == __first) 04731 { 04732 std::reverse(__first, __last); 04733 return false; 04734 } 04735 } 04736 } 04737 04738 /** 04739 * @brief Permute range into the previous "dictionary" ordering. 04740 * @param first Start of range. 04741 * @param last End of range. 04742 * @return False if wrapped to last permutation, true otherwise. 04743 * 04744 * Treats all permutations of the range as a set of "dictionary" sorted 04745 * sequences. Permutes the current sequence into the previous one of this 04746 * set. Returns true if there are more sequences to generate. If the 04747 * sequence is the smallest of the set, the largest is generated and false 04748 * returned. 04749 */ 04750 template<typename _BidirectionalIterator> 04751 bool 04752 prev_permutation(_BidirectionalIterator __first, 04753 _BidirectionalIterator __last) 04754 { 04755 // concept requirements 04756 __glibcxx_function_requires(_BidirectionalIteratorConcept< 04757 _BidirectionalIterator>) 04758 __glibcxx_function_requires(_LessThanComparableConcept< 04759 typename iterator_traits<_BidirectionalIterator>::value_type>) 04760 __glibcxx_requires_valid_range(__first, __last); 04761 04762 if (__first == __last) 04763 return false; 04764 _BidirectionalIterator __i = __first; 04765 ++__i; 04766 if (__i == __last) 04767 return false; 04768 __i = __last; 04769 --__i; 04770 04771 for(;;) 04772 { 04773 _BidirectionalIterator __ii = __i; 04774 --__i; 04775 if (*__ii < *__i) 04776 { 04777 _BidirectionalIterator __j = __last; 04778 while (!(*--__j < *__i)) 04779 {} 04780 std::iter_swap(__i, __j); 04781 std::reverse(__ii, __last); 04782 return true; 04783 } 04784 if (__i == __first) 04785 { 04786 std::reverse(__first, __last); 04787 return false; 04788 } 04789 } 04790 } 04791 04792 /** 04793 * @brief Permute range into the previous "dictionary" ordering using 04794 * comparison functor. 04795 * @param first Start of range. 04796 * @param last End of range. 04797 * @param comp 04798 * @return False if wrapped to last permutation, true otherwise. 04799 * 04800 * Treats all permutations of the range [first,last) as a set of 04801 * "dictionary" sorted sequences ordered by @a comp. Permutes the current 04802 * sequence into the previous one of this set. Returns true if there are 04803 * more sequences to generate. If the sequence is the smallest of the set, 04804 * the largest is generated and false returned. 04805 */ 04806 template<typename _BidirectionalIterator, typename _Compare> 04807 bool 04808 prev_permutation(_BidirectionalIterator __first, 04809 _BidirectionalIterator __last, _Compare __comp) 04810 { 04811 // concept requirements 04812 __glibcxx_function_requires(_BidirectionalIteratorConcept< 04813 _BidirectionalIterator>) 04814 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, 04815 typename iterator_traits<_BidirectionalIterator>::value_type, 04816 typename iterator_traits<_BidirectionalIterator>::value_type>) 04817 __glibcxx_requires_valid_range(__first, __last); 04818 04819 if (__first == __last) 04820 return false; 04821 _BidirectionalIterator __i = __first; 04822 ++__i; 04823 if (__i == __last) 04824 return false; 04825 __i = __last; 04826 --__i; 04827 04828 for(;;) 04829 { 04830 _BidirectionalIterator __ii = __i; 04831 --__i; 04832 if (__comp(*__ii, *__i)) 04833 { 04834 _BidirectionalIterator __j = __last; 04835 while (!__comp(*--__j, *__i)) 04836 {} 04837 std::iter_swap(__i, __j); 04838 std::reverse(__ii, __last); 04839 return true; 04840 } 04841 if (__i == __first) 04842 { 04843 std::reverse(__first, __last); 04844 return false; 04845 } 04846 } 04847 } 04848 04849 // find_first_of, with and without an explicitly supplied comparison function. 04850 04851 /** 04852 * @brief Find element from a set in a sequence. 04853 * @param first1 Start of range to search. 04854 * @param last1 End of range to search. 04855 * @param first2 Start of match candidates. 04856 * @param last2 End of match candidates. 04857 * @return The first iterator @c i in the range 04858 * @p [first1,last1) such that @c *i == @p *(i2) such that i2 is an 04859 * interator in [first2,last2), or @p last1 if no such iterator exists. 04860 * 04861 * Searches the range @p [first1,last1) for an element that is equal to 04862 * some element in the range [first2,last2). If found, returns an iterator 04863 * in the range [first1,last1), otherwise returns @p last1. 04864 */ 04865 template<typename _InputIterator, typename _ForwardIterator> 04866 _InputIterator 04867 find_first_of(_InputIterator __first1, _InputIterator __last1, 04868 _ForwardIterator __first2, _ForwardIterator __last2) 04869 { 04870 // concept requirements 04871 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) 04872 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) 04873 __glibcxx_function_requires(_EqualOpConcept< 04874 typename iterator_traits<_InputIterator>::value_type, 04875 typename iterator_traits<_ForwardIterator>::value_type>) 04876 __glibcxx_requires_valid_range(__first1, __last1); 04877 __glibcxx_requires_valid_range(__first2, __last2); 04878 04879 for ( ; __first1 != __last1; ++__first1) 04880 for (_ForwardIterator __iter = __first2; __iter != __last2; ++__iter) 04881 if (*__first1 == *__iter) 04882 return __first1; 04883 return __last1; 04884 } 04885 04886 /** 04887 * @brief Find element from a set in a sequence using a predicate. 04888 * @param first1 Start of range to search. 04889 * @param last1 End of range to search. 04890 * @param first2 Start of match candidates. 04891 * @param last2 End of match candidates. 04892 * @param comp Predicate to use. 04893 * @return The first iterator @c i in the range 04894 * @p [first1,last1) such that @c comp(*i, @p *(i2)) is true and i2 is an 04895 * interator in [first2,last2), or @p last1 if no such iterator exists. 04896 * 04897 * Searches the range @p [first1,last1) for an element that is equal to 04898 * some element in the range [first2,last2). If found, returns an iterator in 04899 * the range [first1,last1), otherwise returns @p last1. 04900 */ 04901 template<typename _InputIterator, typename _ForwardIterator, 04902 typename _BinaryPredicate> 04903 _InputIterator 04904 find_first_of(_InputIterator __first1, _InputIterator __last1, 04905 _ForwardIterator __first2, _ForwardIterator __last2, 04906 _BinaryPredicate __comp) 04907 { 04908 // concept requirements 04909 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) 04910 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) 04911 __glibcxx_function_requires(_EqualOpConcept< 04912 typename iterator_traits<_InputIterator>::value_type, 04913 typename iterator_traits<_ForwardIterator>::value_type>) 04914 __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate, 04915 typename iterator_traits<_InputIterator>::value_type, 04916 typename iterator_traits<_ForwardIterator>::value_type>) 04917 __glibcxx_requires_valid_range(__first1, __last1); 04918 __glibcxx_requires_valid_range(__first2, __last2); 04919 04920 for ( ; __first1 != __last1; ++__first1) 04921 for (_ForwardIterator __iter = __first2; __iter != __last2; ++__iter) 04922 if (__comp(*__first1, *__iter)) 04923 return __first1; 04924 return __last1; 04925 } 04926 04927 04928 // find_end, with and without an explicitly supplied comparison function. 04929 // Search [first2, last2) as a subsequence in [first1, last1), and return 04930 // the *last* possible match. Note that find_end for bidirectional iterators 04931 // is much faster than for forward iterators. 04932 04933 // find_end for forward iterators. 04934 template<typename _ForwardIterator1, typename _ForwardIterator2> 04935 _ForwardIterator1 04936 __find_end(_ForwardIterator1 __first1, _ForwardIterator1 __last1, 04937 _ForwardIterator2 __first2, _ForwardIterator2 __last2, 04938 forward_iterator_tag, forward_iterator_tag) 04939 { 04940 if (__first2 == __last2) 04941 return __last1; 04942 else 04943 { 04944 _ForwardIterator1 __result = __last1; 04945 while (1) 04946 { 04947 _ForwardIterator1 __new_result 04948 = std::search(__first1, __last1, __first2, __last2); 04949 if (__new_result == __last1) 04950 return __result; 04951 else 04952 { 04953 __result = __new_result; 04954 __first1 = __new_result; 04955 ++__first1; 04956 } 04957 } 04958 } 04959 } 04960 04961 template<typename _ForwardIterator1, typename _ForwardIterator2, 04962 typename _BinaryPredicate> 04963 _ForwardIterator1 04964 __find_end(_ForwardIterator1 __first1, _ForwardIterator1 __last1, 04965 _ForwardIterator2 __first2, _ForwardIterator2 __last2, 04966 forward_iterator_tag, forward_iterator_tag, 04967 _BinaryPredicate __comp) 04968 { 04969 if (__first2 == __last2) 04970 return __last1; 04971 else 04972 { 04973 _ForwardIterator1 __result = __last1; 04974 while (1) 04975 { 04976 _ForwardIterator1 __new_result 04977 = std::search(__first1, __last1, __first2, __last2, __comp); 04978 if (__new_result == __last1) 04979 return __result; 04980 else 04981 { 04982 __result = __new_result; 04983 __first1 = __new_result; 04984 ++__first1; 04985 } 04986 } 04987 } 04988 } 04989 04990 // find_end for bidirectional iterators. Requires partial specialization. 04991 template<typename _BidirectionalIterator1, typename _BidirectionalIterator2> 04992 _BidirectionalIterator1 04993 __find_end(_BidirectionalIterator1 __first1, 04994 _BidirectionalIterator1 __last1, 04995 _BidirectionalIterator2 __first2, 04996 _BidirectionalIterator2 __last2, 04997 bidirectional_iterator_tag, bidirectional_iterator_tag) 04998 { 04999 // concept requirements 05000 __glibcxx_function_requires(_BidirectionalIteratorConcept< 05001 _BidirectionalIterator1>) 05002 __glibcxx_function_requires(_BidirectionalIteratorConcept< 05003 _BidirectionalIterator2>) 05004 05005 typedef reverse_iterator<_BidirectionalIterator1> _RevIterator1; 05006 typedef reverse_iterator<_BidirectionalIterator2> _RevIterator2; 05007 05008 _RevIterator1 __rlast1(__first1); 05009 _RevIterator2 __rlast2(__first2); 05010 _RevIterator1 __rresult = std::search(_RevIterator1(__last1), __rlast1, 05011 _RevIterator2(__last2), __rlast2); 05012 05013 if (__rresult == __rlast1) 05014 return __last1; 05015 else 05016 { 05017 _BidirectionalIterator1 __result = __rresult.base(); 05018 std::advance(__result, -std::distance(__first2, __last2)); 05019 return __result; 05020 } 05021 } 05022 05023 template<typename _BidirectionalIterator1, typename _BidirectionalIterator2, 05024 typename _BinaryPredicate> 05025 _BidirectionalIterator1 05026 __find_end(_BidirectionalIterator1 __first1, 05027 _BidirectionalIterator1 __last1, 05028 _BidirectionalIterator2 __first2, 05029 _BidirectionalIterator2 __last2, 05030 bidirectional_iterator_tag, bidirectional_iterator_tag, 05031 _BinaryPredicate __comp) 05032 { 05033 // concept requirements 05034 __glibcxx_function_requires(_BidirectionalIteratorConcept< 05035 _BidirectionalIterator1>) 05036 __glibcxx_function_requires(_BidirectionalIteratorConcept< 05037 _BidirectionalIterator2>) 05038 05039 typedef reverse_iterator<_BidirectionalIterator1> _RevIterator1; 05040 typedef reverse_iterator<_BidirectionalIterator2> _RevIterator2; 05041 05042 _RevIterator1 __rlast1(__first1); 05043 _RevIterator2 __rlast2(__first2); 05044 _RevIterator1 __rresult = std::search(_RevIterator1(__last1), __rlast1, 05045 _RevIterator2(__last2), __rlast2, 05046 __comp); 05047 05048 if (__rresult == __rlast1) 05049 return __last1; 05050 else 05051 { 05052 _BidirectionalIterator1 __result = __rresult.base(); 05053 std::advance(__result, -std::distance(__first2, __last2)); 05054 return __result; 05055 } 05056 } 05057 05058 // Dispatching functions for find_end. 05059 05060 /** 05061 * @brief Find last matching subsequence in a sequence. 05062 * @param first1 Start of range to search. 05063 * @param last1 End of range to search. 05064 * @param first2 Start of sequence to match. 05065 * @param last2 End of sequence to match. 05066 * @return The last iterator @c i in the range 05067 * @p [first1,last1-(last2-first2)) such that @c *(i+N) == @p *(first2+N) 05068 * for each @c N in the range @p [0,last2-first2), or @p last1 if no 05069 * such iterator exists. 05070 * 05071 * Searches the range @p [first1,last1) for a sub-sequence that compares 05072 * equal value-by-value with the sequence given by @p [first2,last2) and 05073 * returns an iterator to the first element of the sub-sequence, or 05074 * @p last1 if the sub-sequence is not found. The sub-sequence will be the 05075 * last such subsequence contained in [first,last1). 05076 * 05077 * Because the sub-sequence must lie completely within the range 05078 * @p [first1,last1) it must start at a position less than 05079 * @p last1-(last2-first2) where @p last2-first2 is the length of the 05080 * sub-sequence. 05081 * This means that the returned iterator @c i will be in the range 05082 * @p [first1,last1-(last2-first2)) 05083 */ 05084 template<typename _ForwardIterator1, typename _ForwardIterator2> 05085 inline _ForwardIterator1 05086 find_end(_ForwardIterator1 __first1, _ForwardIterator1 __last1, 05087 _ForwardIterator2 __first2, _ForwardIterator2 __last2) 05088 { 05089 // concept requirements 05090 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator1>) 05091 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator2>) 05092 __glibcxx_function_requires(_EqualOpConcept< 05093 typename iterator_traits<_ForwardIterator1>::value_type, 05094 typename iterator_traits<_ForwardIterator2>::value_type>) 05095 __glibcxx_requires_valid_range(__first1, __last1); 05096 __glibcxx_requires_valid_range(__first2, __last2); 05097 05098 return std::__find_end(__first1, __last1, __first2, __last2, 05099 std::__iterator_category(__first1), 05100 std::__iterator_category(__first2)); 05101 } 05102 05103 /** 05104 * @brief Find last matching subsequence in a sequence using a predicate. 05105 * @param first1 Start of range to search. 05106 * @param last1 End of range to search. 05107 * @param first2 Start of sequence to match. 05108 * @param last2 End of sequence to match. 05109 * @param comp The predicate to use. 05110 * @return The last iterator @c i in the range 05111 * @p [first1,last1-(last2-first2)) such that @c predicate(*(i+N), @p 05112 * (first2+N)) is true for each @c N in the range @p [0,last2-first2), or 05113 * @p last1 if no such iterator exists. 05114 * 05115 * Searches the range @p [first1,last1) for a sub-sequence that compares 05116 * equal value-by-value with the sequence given by @p [first2,last2) using 05117 * comp as a predicate and returns an iterator to the first element of the 05118 * sub-sequence, or @p last1 if the sub-sequence is not found. The 05119 * sub-sequence will be the last such subsequence contained in 05120 * [first,last1). 05121 * 05122 * Because the sub-sequence must lie completely within the range 05123 * @p [first1,last1) it must start at a position less than 05124 * @p last1-(last2-first2) where @p last2-first2 is the length of the 05125 * sub-sequence. 05126 * This means that the returned iterator @c i will be in the range 05127 * @p [first1,last1-(last2-first2)) 05128 */ 05129 template<typename _ForwardIterator1, typename _ForwardIterator2, 05130 typename _BinaryPredicate> 05131 inline _ForwardIterator1 05132 find_end(_ForwardIterator1 __first1, _ForwardIterator1 __last1, 05133 _ForwardIterator2 __first2, _ForwardIterator2 __last2, 05134 _BinaryPredicate __comp) 05135 { 05136 // concept requirements 05137 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator1>) 05138 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator2>) 05139 __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate, 05140 typename iterator_traits<_ForwardIterator1>::value_type, 05141 typename iterator_traits<_ForwardIterator2>::value_type>) 05142 __glibcxx_requires_valid_range(__first1, __last1); 05143 __glibcxx_requires_valid_range(__first2, __last2); 05144 05145 return std::__find_end(__first1, __last1, __first2, __last2, 05146 std::__iterator_category(__first1), 05147 std::__iterator_category(__first2), 05148 __comp); 05149 } 05150 05151 } // namespace std 05152 05153 #endif /* _ALGO_H */

Generated on Wed Sep 8 10:19:42 2004 for libstdc++-v3 Source by doxygen 1.3.8