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