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