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 if (__result1 != __first) 01815 *__result1 = _GLIBCXX_MOVE(*__first); 01816 ++__result1; 01817 } 01818 else 01819 { 01820 *__result2 = _GLIBCXX_MOVE(*__first); 01821 ++__result2; 01822 } 01823 _GLIBCXX_MOVE3(__buffer, __result2, __result1); 01824 return __result1; 01825 } 01826 else 01827 { 01828 _ForwardIterator __middle = __first; 01829 std::advance(__middle, __len / 2); 01830 _ForwardIterator __begin = 01831 std::__stable_partition_adaptive(__first, __middle, __pred, 01832 __len / 2, __buffer, 01833 __buffer_size); 01834 _ForwardIterator __end = 01835 std::__stable_partition_adaptive(__middle, __last, __pred, 01836 __len - __len / 2, 01837 __buffer, __buffer_size); 01838 std::rotate(__begin, __middle, __end); 01839 std::advance(__begin, std::distance(__middle, __end)); 01840 return __begin; 01841 } 01842 } 01843 01844 /** 01845 * @brief Move elements for which a predicate is true to the beginning 01846 * of a sequence, preserving relative ordering. 01847 * @ingroup mutating_algorithms 01848 * @param first A forward iterator. 01849 * @param last A forward iterator. 01850 * @param pred A predicate functor. 01851 * @return An iterator @p middle such that @p pred(i) is true for each 01852 * iterator @p i in the range @p [first,middle) and false for each @p i 01853 * in the range @p [middle,last). 01854 * 01855 * Performs the same function as @p partition() with the additional 01856 * guarantee that the relative ordering of elements in each group is 01857 * preserved, so any two elements @p x and @p y in the range 01858 * @p [first,last) such that @p pred(x)==pred(y) will have the same 01859 * relative ordering after calling @p stable_partition(). 01860 */ 01861 template<typename _ForwardIterator, typename _Predicate> 01862 _ForwardIterator 01863 stable_partition(_ForwardIterator __first, _ForwardIterator __last, 01864 _Predicate __pred) 01865 { 01866 // concept requirements 01867 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept< 01868 _ForwardIterator>) 01869 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate, 01870 typename iterator_traits<_ForwardIterator>::value_type>) 01871 __glibcxx_requires_valid_range(__first, __last); 01872 01873 if (__first == __last) 01874 return __first; 01875 else 01876 { 01877 typedef typename iterator_traits<_ForwardIterator>::value_type 01878 _ValueType; 01879 typedef typename iterator_traits<_ForwardIterator>::difference_type 01880 _DistanceType; 01881 01882 _Temporary_buffer<_ForwardIterator, _ValueType> __buf(__first, 01883 __last); 01884 if (__buf.size() > 0) 01885 return 01886 std::__stable_partition_adaptive(__first, __last, __pred, 01887 _DistanceType(__buf.requested_size()), 01888 __buf.begin(), 01889 _DistanceType(__buf.size())); 01890 else 01891 return 01892 std::__inplace_stable_partition(__first, __last, __pred, 01893 _DistanceType(__buf.requested_size())); 01894 } 01895 } 01896 01897 /// This is a helper function for the sort routines. 01898 template<typename _RandomAccessIterator> 01899 void 01900 __heap_select(_RandomAccessIterator __first, 01901 _RandomAccessIterator __middle, 01902 _RandomAccessIterator __last) 01903 { 01904 std::make_heap(__first, __middle); 01905 for (_RandomAccessIterator __i = __middle; __i < __last; ++__i) 01906 if (*__i < *__first) 01907 std::__pop_heap(__first, __middle, __i); 01908 } 01909 01910 /// This is a helper function for the sort routines. 01911 template<typename _RandomAccessIterator, typename _Compare> 01912 void 01913 __heap_select(_RandomAccessIterator __first, 01914 _RandomAccessIterator __middle, 01915 _RandomAccessIterator __last, _Compare __comp) 01916 { 01917 std::make_heap(__first, __middle, __comp); 01918 for (_RandomAccessIterator __i = __middle; __i < __last; ++__i) 01919 if (__comp(*__i, *__first)) 01920 std::__pop_heap(__first, __middle, __i, __comp); 01921 } 01922 01923 // partial_sort 01924 01925 /** 01926 * @brief Copy the smallest elements of a sequence. 01927 * @ingroup sorting_algorithms 01928 * @param first An iterator. 01929 * @param last Another iterator. 01930 * @param result_first A random-access iterator. 01931 * @param result_last Another random-access iterator. 01932 * @return An iterator indicating the end of the resulting sequence. 01933 * 01934 * Copies and sorts the smallest N values from the range @p [first,last) 01935 * to the range beginning at @p result_first, where the number of 01936 * elements to be copied, @p N, is the smaller of @p (last-first) and 01937 * @p (result_last-result_first). 01938 * After the sort if @p i and @j are iterators in the range 01939 * @p [result_first,result_first+N) such that @i precedes @j then 01940 * @p *j<*i is false. 01941 * The value returned is @p result_first+N. 01942 */ 01943 template<typename _InputIterator, typename _RandomAccessIterator> 01944 _RandomAccessIterator 01945 partial_sort_copy(_InputIterator __first, _InputIterator __last, 01946 _RandomAccessIterator __result_first, 01947 _RandomAccessIterator __result_last) 01948 { 01949 typedef typename iterator_traits<_InputIterator>::value_type 01950 _InputValueType; 01951 typedef typename iterator_traits<_RandomAccessIterator>::value_type 01952 _OutputValueType; 01953 typedef typename iterator_traits<_RandomAccessIterator>::difference_type 01954 _DistanceType; 01955 01956 // concept requirements 01957 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) 01958 __glibcxx_function_requires(_ConvertibleConcept<_InputValueType, 01959 _OutputValueType>) 01960 __glibcxx_function_requires(_LessThanOpConcept<_InputValueType, 01961 _OutputValueType>) 01962 __glibcxx_function_requires(_LessThanComparableConcept<_OutputValueType>) 01963 __glibcxx_requires_valid_range(__first, __last); 01964 __glibcxx_requires_valid_range(__result_first, __result_last); 01965 01966 if (__result_first == __result_last) 01967 return __result_last; 01968 _RandomAccessIterator __result_real_last = __result_first; 01969 while(__first != __last && __result_real_last != __result_last) 01970 { 01971 *__result_real_last = *__first; 01972 ++__result_real_last; 01973 ++__first; 01974 } 01975 std::make_heap(__result_first, __result_real_last); 01976 while (__first != __last) 01977 { 01978 if (*__first < *__result_first) 01979 std::__adjust_heap(__result_first, _DistanceType(0), 01980 _DistanceType(__result_real_last 01981 - __result_first), 01982 _InputValueType(*__first)); 01983 ++__first; 01984 } 01985 std::sort_heap(__result_first, __result_real_last); 01986 return __result_real_last; 01987 } 01988 01989 /** 01990 * @brief Copy the smallest elements of a sequence using a predicate for 01991 * comparison. 01992 * @ingroup sorting_algorithms 01993 * @param first An input iterator. 01994 * @param last Another input iterator. 01995 * @param result_first A random-access iterator. 01996 * @param result_last Another random-access iterator. 01997 * @param comp A comparison functor. 01998 * @return An iterator indicating the end of the resulting sequence. 01999 * 02000 * Copies and sorts the smallest N values from the range @p [first,last) 02001 * to the range beginning at @p result_first, where the number of 02002 * elements to be copied, @p N, is the smaller of @p (last-first) and 02003 * @p (result_last-result_first). 02004 * After the sort if @p i and @j are iterators in the range 02005 * @p [result_first,result_first+N) such that @i precedes @j then 02006 * @p comp(*j,*i) is false. 02007 * The value returned is @p result_first+N. 02008 */ 02009 template<typename _InputIterator, typename _RandomAccessIterator, typename _Compare> 02010 _RandomAccessIterator 02011 partial_sort_copy(_InputIterator __first, _InputIterator __last, 02012 _RandomAccessIterator __result_first, 02013 _RandomAccessIterator __result_last, 02014 _Compare __comp) 02015 { 02016 typedef typename iterator_traits<_InputIterator>::value_type 02017 _InputValueType; 02018 typedef typename iterator_traits<_RandomAccessIterator>::value_type 02019 _OutputValueType; 02020 typedef typename iterator_traits<_RandomAccessIterator>::difference_type 02021 _DistanceType; 02022 02023 // concept requirements 02024 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) 02025 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept< 02026 _RandomAccessIterator>) 02027 __glibcxx_function_requires(_ConvertibleConcept<_InputValueType, 02028 _OutputValueType>) 02029 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, 02030 _InputValueType, _OutputValueType>) 02031 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, 02032 _OutputValueType, _OutputValueType>) 02033 __glibcxx_requires_valid_range(__first, __last); 02034 __glibcxx_requires_valid_range(__result_first, __result_last); 02035 02036 if (__result_first == __result_last) 02037 return __result_last; 02038 _RandomAccessIterator __result_real_last = __result_first; 02039 while(__first != __last && __result_real_last != __result_last) 02040 { 02041 *__result_real_last = *__first; 02042 ++__result_real_last; 02043 ++__first; 02044 } 02045 std::make_heap(__result_first, __result_real_last, __comp); 02046 while (__first != __last) 02047 { 02048 if (__comp(*__first, *__result_first)) 02049 std::__adjust_heap(__result_first, _DistanceType(0), 02050 _DistanceType(__result_real_last 02051 - __result_first), 02052 _InputValueType(*__first), 02053 __comp); 02054 ++__first; 02055 } 02056 std::sort_heap(__result_first, __result_real_last, __comp); 02057 return __result_real_last; 02058 } 02059 02060 /// This is a helper function for the sort routine. 02061 template<typename _RandomAccessIterator> 02062 void 02063 __unguarded_linear_insert(_RandomAccessIterator __last) 02064 { 02065 typename iterator_traits<_RandomAccessIterator>::value_type 02066 __val = _GLIBCXX_MOVE(*__last); 02067 _RandomAccessIterator __next = __last; 02068 --__next; 02069 while (__val < *__next) 02070 { 02071 *__last = _GLIBCXX_MOVE(*__next); 02072 __last = __next; 02073 --__next; 02074 } 02075 *__last = _GLIBCXX_MOVE(__val); 02076 } 02077 02078 /// This is a helper function for the sort routine. 02079 template<typename _RandomAccessIterator, typename _Compare> 02080 void 02081 __unguarded_linear_insert(_RandomAccessIterator __last, 02082 _Compare __comp) 02083 { 02084 typename iterator_traits<_RandomAccessIterator>::value_type 02085 __val = _GLIBCXX_MOVE(*__last); 02086 _RandomAccessIterator __next = __last; 02087 --__next; 02088 while (__comp(__val, *__next)) 02089 { 02090 *__last = _GLIBCXX_MOVE(*__next); 02091 __last = __next; 02092 --__next; 02093 } 02094 *__last = _GLIBCXX_MOVE(__val); 02095 } 02096 02097 /// This is a helper function for the sort routine. 02098 template<typename _RandomAccessIterator> 02099 void 02100 __insertion_sort(_RandomAccessIterator __first, 02101 _RandomAccessIterator __last) 02102 { 02103 if (__first == __last) 02104 return; 02105 02106 for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i) 02107 { 02108 if (*__i < *__first) 02109 { 02110 typename iterator_traits<_RandomAccessIterator>::value_type 02111 __val = _GLIBCXX_MOVE(*__i); 02112 _GLIBCXX_MOVE_BACKWARD3(__first, __i, __i + 1); 02113 *__first = _GLIBCXX_MOVE(__val); 02114 } 02115 else 02116 std::__unguarded_linear_insert(__i); 02117 } 02118 } 02119 02120 /// This is a helper function for the sort routine. 02121 template<typename _RandomAccessIterator, typename _Compare> 02122 void 02123 __insertion_sort(_RandomAccessIterator __first, 02124 _RandomAccessIterator __last, _Compare __comp) 02125 { 02126 if (__first == __last) return; 02127 02128 for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i) 02129 { 02130 if (__comp(*__i, *__first)) 02131 { 02132 typename iterator_traits<_RandomAccessIterator>::value_type 02133 __val = _GLIBCXX_MOVE(*__i); 02134 _GLIBCXX_MOVE_BACKWARD3(__first, __i, __i + 1); 02135 *__first = _GLIBCXX_MOVE(__val); 02136 } 02137 else 02138 std::__unguarded_linear_insert(__i, __comp); 02139 } 02140 } 02141 02142 /// This is a helper function for the sort routine. 02143 template<typename _RandomAccessIterator> 02144 inline void 02145 __unguarded_insertion_sort(_RandomAccessIterator __first, 02146 _RandomAccessIterator __last) 02147 { 02148 typedef typename iterator_traits<_RandomAccessIterator>::value_type 02149 _ValueType; 02150 02151 for (_RandomAccessIterator __i = __first; __i != __last; ++__i) 02152 std::__unguarded_linear_insert(__i); 02153 } 02154 02155 /// This is a helper function for the sort routine. 02156 template<typename _RandomAccessIterator, typename _Compare> 02157 inline void 02158 __unguarded_insertion_sort(_RandomAccessIterator __first, 02159 _RandomAccessIterator __last, _Compare __comp) 02160 { 02161 typedef typename iterator_traits<_RandomAccessIterator>::value_type 02162 _ValueType; 02163 02164 for (_RandomAccessIterator __i = __first; __i != __last; ++__i) 02165 std::__unguarded_linear_insert(__i, __comp); 02166 } 02167 02168 /** 02169 * @doctodo 02170 * This controls some aspect of the sort routines. 02171 */ 02172 enum { _S_threshold = 16 }; 02173 02174 /// This is a helper function for the sort routine. 02175 template<typename _RandomAccessIterator> 02176 void 02177 __final_insertion_sort(_RandomAccessIterator __first, 02178 _RandomAccessIterator __last) 02179 { 02180 if (__last - __first > int(_S_threshold)) 02181 { 02182 std::__insertion_sort(__first, __first + int(_S_threshold)); 02183 std::__unguarded_insertion_sort(__first + int(_S_threshold), __last); 02184 } 02185 else 02186 std::__insertion_sort(__first, __last); 02187 } 02188 02189 /// This is a helper function for the sort routine. 02190 template<typename _RandomAccessIterator, typename _Compare> 02191 void 02192 __final_insertion_sort(_RandomAccessIterator __first, 02193 _RandomAccessIterator __last, _Compare __comp) 02194 { 02195 if (__last - __first > int(_S_threshold)) 02196 { 02197 std::__insertion_sort(__first, __first + int(_S_threshold), __comp); 02198 std::__unguarded_insertion_sort(__first + int(_S_threshold), __last, 02199 __comp); 02200 } 02201 else 02202 std::__insertion_sort(__first, __last, __comp); 02203 } 02204 02205 /// This is a helper function... 02206 template<typename _RandomAccessIterator, typename _Tp> 02207 _RandomAccessIterator 02208 __unguarded_partition(_RandomAccessIterator __first, 02209 _RandomAccessIterator __last, const _Tp& __pivot) 02210 { 02211 while (true) 02212 { 02213 while (*__first < __pivot) 02214 ++__first; 02215 --__last; 02216 while (__pivot < *__last) 02217 --__last; 02218 if (!(__first < __last)) 02219 return __first; 02220 std::iter_swap(__first, __last); 02221 ++__first; 02222 } 02223 } 02224 02225 /// This is a helper function... 02226 template<typename _RandomAccessIterator, typename _Tp, typename _Compare> 02227 _RandomAccessIterator 02228 __unguarded_partition(_RandomAccessIterator __first, 02229 _RandomAccessIterator __last, 02230 const _Tp& __pivot, _Compare __comp) 02231 { 02232 while (true) 02233 { 02234 while (__comp(*__first, __pivot)) 02235 ++__first; 02236 --__last; 02237 while (__comp(__pivot, *__last)) 02238 --__last; 02239 if (!(__first < __last)) 02240 return __first; 02241 std::iter_swap(__first, __last); 02242 ++__first; 02243 } 02244 } 02245 02246 /// This is a helper function... 02247 template<typename _RandomAccessIterator> 02248 inline _RandomAccessIterator 02249 __unguarded_partition_pivot(_RandomAccessIterator __first, 02250 _RandomAccessIterator __last) 02251 { 02252 _RandomAccessIterator __mid = __first + (__last - __first) / 2; 02253 std::__move_median_first(__first, __mid, (__last - 1)); 02254 return std::__unguarded_partition(__first + 1, __last, *__first); 02255 } 02256 02257 02258 /// This is a helper function... 02259 template<typename _RandomAccessIterator, typename _Compare> 02260 inline _RandomAccessIterator 02261 __unguarded_partition_pivot(_RandomAccessIterator __first, 02262 _RandomAccessIterator __last, _Compare __comp) 02263 { 02264 _RandomAccessIterator __mid = __first + (__last - __first) / 2; 02265 std::__move_median_first(__first, __mid, (__last - 1), __comp); 02266 return std::__unguarded_partition(__first + 1, __last, *__first, __comp); 02267 } 02268 02269 /// This is a helper function for the sort routine. 02270 template<typename _RandomAccessIterator, typename _Size> 02271 void 02272 __introsort_loop(_RandomAccessIterator __first, 02273 _RandomAccessIterator __last, 02274 _Size __depth_limit) 02275 { 02276 while (__last - __first > int(_S_threshold)) 02277 { 02278 if (__depth_limit == 0) 02279 { 02280 _GLIBCXX_STD_A::partial_sort(__first, __last, __last); 02281 return; 02282 } 02283 --__depth_limit; 02284 _RandomAccessIterator __cut = 02285 std::__unguarded_partition_pivot(__first, __last); 02286 std::__introsort_loop(__cut, __last, __depth_limit); 02287 __last = __cut; 02288 } 02289 } 02290 02291 /// This is a helper function for the sort routine. 02292 template<typename _RandomAccessIterator, typename _Size, typename _Compare> 02293 void 02294 __introsort_loop(_RandomAccessIterator __first, 02295 _RandomAccessIterator __last, 02296 _Size __depth_limit, _Compare __comp) 02297 { 02298 while (__last - __first > int(_S_threshold)) 02299 { 02300 if (__depth_limit == 0) 02301 { 02302 _GLIBCXX_STD_A::partial_sort(__first, __last, __last, __comp); 02303 return; 02304 } 02305 --__depth_limit; 02306 _RandomAccessIterator __cut = 02307 std::__unguarded_partition_pivot(__first, __last, __comp); 02308 std::__introsort_loop(__cut, __last, __depth_limit, __comp); 02309 __last = __cut; 02310 } 02311 } 02312 02313 // sort 02314 02315 template<typename _RandomAccessIterator, typename _Size> 02316 void 02317 __introselect(_RandomAccessIterator __first, _RandomAccessIterator __nth, 02318 _RandomAccessIterator __last, _Size __depth_limit) 02319 { 02320 typedef typename iterator_traits<_RandomAccessIterator>::value_type 02321 _ValueType; 02322 02323 while (__last - __first > 3) 02324 { 02325 if (__depth_limit == 0) 02326 { 02327 std::__heap_select(__first, __nth + 1, __last); 02328 02329 // Place the nth largest element in its final position. 02330 std::iter_swap(__first, __nth); 02331 return; 02332 } 02333 --__depth_limit; 02334 _RandomAccessIterator __cut = 02335 std::__unguarded_partition_pivot(__first, __last); 02336 if (__cut <= __nth) 02337 __first = __cut; 02338 else 02339 __last = __cut; 02340 } 02341 std::__insertion_sort(__first, __last); 02342 } 02343 02344 template<typename _RandomAccessIterator, typename _Size, typename _Compare> 02345 void 02346 __introselect(_RandomAccessIterator __first, _RandomAccessIterator __nth, 02347 _RandomAccessIterator __last, _Size __depth_limit, 02348 _Compare __comp) 02349 { 02350 typedef typename iterator_traits<_RandomAccessIterator>::value_type 02351 _ValueType; 02352 02353 while (__last - __first > 3) 02354 { 02355 if (__depth_limit == 0) 02356 { 02357 std::__heap_select(__first, __nth + 1, __last, __comp); 02358 // Place the nth largest element in its final position. 02359 std::iter_swap(__first, __nth); 02360 return; 02361 } 02362 --__depth_limit; 02363 _RandomAccessIterator __cut = 02364 std::__unguarded_partition_pivot(__first, __last, __comp); 02365 if (__cut <= __nth) 02366 __first = __cut; 02367 else 02368 __last = __cut; 02369 } 02370 std::__insertion_sort(__first, __last, __comp); 02371 } 02372 02373 // nth_element 02374 02375 // lower_bound moved to stl_algobase.h 02376 02377 /** 02378 * @brief Finds the first position in which @a val could be inserted 02379 * without changing the ordering. 02380 * @ingroup binary_search_algorithms 02381 * @param first An iterator. 02382 * @param last Another iterator. 02383 * @param val The search term. 02384 * @param comp A functor to use for comparisons. 02385 * @return An iterator pointing to the first element <em>not less 02386 * than</em> @a val, or end() if every element is less 02387 * than @a val. 02388 * @ingroup binary_search_algorithms 02389 * 02390 * The comparison function should have the same effects on ordering as 02391 * the function used for the initial sort. 02392 */ 02393 template<typename _ForwardIterator, typename _Tp, typename _Compare> 02394 _ForwardIterator 02395 lower_bound(_ForwardIterator __first, _ForwardIterator __last, 02396 const _Tp& __val, _Compare __comp) 02397 { 02398 typedef typename iterator_traits<_ForwardIterator>::value_type 02399 _ValueType; 02400 typedef typename iterator_traits<_ForwardIterator>::difference_type 02401 _DistanceType; 02402 02403 // concept requirements 02404 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) 02405 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, 02406 _ValueType, _Tp>) 02407 __glibcxx_requires_partitioned_lower_pred(__first, __last, 02408 __val, __comp); 02409 02410 _DistanceType __len = std::distance(__first, __last); 02411 02412 while (__len > 0) 02413 { 02414 _DistanceType __half = __len >> 1; 02415 _ForwardIterator __middle = __first; 02416 std::advance(__middle, __half); 02417 if (__comp(*__middle, __val)) 02418 { 02419 __first = __middle; 02420 ++__first; 02421 __len = __len - __half - 1; 02422 } 02423 else 02424 __len = __half; 02425 } 02426 return __first; 02427 } 02428 02429 /** 02430 * @brief Finds the last position in which @a val could be inserted 02431 * without changing the ordering. 02432 * @ingroup binary_search_algorithms 02433 * @param first An iterator. 02434 * @param last Another iterator. 02435 * @param val The search term. 02436 * @return An iterator pointing to the first element greater than @a val, 02437 * or end() if no elements are greater than @a val. 02438 * @ingroup binary_search_algorithms 02439 */ 02440 template<typename _ForwardIterator, typename _Tp> 02441 _ForwardIterator 02442 upper_bound(_ForwardIterator __first, _ForwardIterator __last, 02443 const _Tp& __val) 02444 { 02445 typedef typename iterator_traits<_ForwardIterator>::value_type 02446 _ValueType; 02447 typedef typename iterator_traits<_ForwardIterator>::difference_type 02448 _DistanceType; 02449 02450 // concept requirements 02451 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) 02452 __glibcxx_function_requires(_LessThanOpConcept<_Tp, _ValueType>) 02453 __glibcxx_requires_partitioned_upper(__first, __last, __val); 02454 02455 _DistanceType __len = std::distance(__first, __last); 02456 02457 while (__len > 0) 02458 { 02459 _DistanceType __half = __len >> 1; 02460 _ForwardIterator __middle = __first; 02461 std::advance(__middle, __half); 02462 if (__val < *__middle) 02463 __len = __half; 02464 else 02465 { 02466 __first = __middle; 02467 ++__first; 02468 __len = __len - __half - 1; 02469 } 02470 } 02471 return __first; 02472 } 02473 02474 /** 02475 * @brief Finds the last position in which @a val could be inserted 02476 * without changing the ordering. 02477 * @ingroup binary_search_algorithms 02478 * @param first An iterator. 02479 * @param last Another iterator. 02480 * @param val The search term. 02481 * @param comp A functor to use for comparisons. 02482 * @return An iterator pointing to the first element greater than @a val, 02483 * or end() if no elements are greater than @a val. 02484 * @ingroup binary_search_algorithms 02485 * 02486 * The comparison function should have the same effects on ordering as 02487 * the function used for the initial sort. 02488 */ 02489 template<typename _ForwardIterator, typename _Tp, typename _Compare> 02490 _ForwardIterator 02491 upper_bound(_ForwardIterator __first, _ForwardIterator __last, 02492 const _Tp& __val, _Compare __comp) 02493 { 02494 typedef typename iterator_traits<_ForwardIterator>::value_type 02495 _ValueType; 02496 typedef typename iterator_traits<_ForwardIterator>::difference_type 02497 _DistanceType; 02498 02499 // concept requirements 02500 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) 02501 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, 02502 _Tp, _ValueType>) 02503 __glibcxx_requires_partitioned_upper_pred(__first, __last, 02504 __val, __comp); 02505 02506 _DistanceType __len = std::distance(__first, __last); 02507 02508 while (__len > 0) 02509 { 02510 _DistanceType __half = __len >> 1; 02511 _ForwardIterator __middle = __first; 02512 std::advance(__middle, __half); 02513 if (__comp(__val, *__middle)) 02514 __len = __half; 02515 else 02516 { 02517 __first = __middle; 02518 ++__first; 02519 __len = __len - __half - 1; 02520 } 02521 } 02522 return __first; 02523 } 02524 02525 /** 02526 * @brief Finds the largest subrange in which @a val could be inserted 02527 * at any place in it without changing the ordering. 02528 * @ingroup binary_search_algorithms 02529 * @param first An iterator. 02530 * @param last Another iterator. 02531 * @param val The search term. 02532 * @return An pair of iterators defining the subrange. 02533 * @ingroup binary_search_algorithms 02534 * 02535 * This is equivalent to 02536 * @code 02537 * std::make_pair(lower_bound(first, last, val), 02538 * upper_bound(first, last, val)) 02539 * @endcode 02540 * but does not actually call those functions. 02541 */ 02542 template<typename _ForwardIterator, typename _Tp> 02543 pair<_ForwardIterator, _ForwardIterator> 02544 equal_range(_ForwardIterator __first, _ForwardIterator __last, 02545 const _Tp& __val) 02546 { 02547 typedef typename iterator_traits<_ForwardIterator>::value_type 02548 _ValueType; 02549 typedef typename iterator_traits<_ForwardIterator>::difference_type 02550 _DistanceType; 02551 02552 // concept requirements 02553 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) 02554 __glibcxx_function_requires(_LessThanOpConcept<_ValueType, _Tp>) 02555 __glibcxx_function_requires(_LessThanOpConcept<_Tp, _ValueType>) 02556 __glibcxx_requires_partitioned_lower(__first, __last, __val); 02557 __glibcxx_requires_partitioned_upper(__first, __last, __val); 02558 02559 _DistanceType __len = std::distance(__first, __last); 02560 02561 while (__len > 0) 02562 { 02563 _DistanceType __half = __len >> 1; 02564 _ForwardIterator __middle = __first; 02565 std::advance(__middle, __half); 02566 if (*__middle < __val) 02567 { 02568 __first = __middle; 02569 ++__first; 02570 __len = __len - __half - 1; 02571 } 02572 else if (__val < *__middle) 02573 __len = __half; 02574 else 02575 { 02576 _ForwardIterator __left = std::lower_bound(__first, __middle, 02577 __val); 02578 std::advance(__first, __len); 02579 _ForwardIterator __right = std::upper_bound(++__middle, __first, 02580 __val); 02581 return pair<_ForwardIterator, _ForwardIterator>(__left, __right); 02582 } 02583 } 02584 return pair<_ForwardIterator, _ForwardIterator>(__first, __first); 02585 } 02586 02587 /** 02588 * @brief Finds the largest subrange in which @a val could be inserted 02589 * at any place in it without changing the ordering. 02590 * @param first An iterator. 02591 * @param last Another iterator. 02592 * @param val The search term. 02593 * @param comp A functor to use for comparisons. 02594 * @return An pair of iterators defining the subrange. 02595 * @ingroup binary_search_algorithms 02596 * 02597 * This is equivalent to 02598 * @code 02599 * std::make_pair(lower_bound(first, last, val, comp), 02600 * upper_bound(first, last, val, comp)) 02601 * @endcode 02602 * but does not actually call those functions. 02603 */ 02604 template<typename _ForwardIterator, typename _Tp, typename _Compare> 02605 pair<_ForwardIterator, _ForwardIterator> 02606 equal_range(_ForwardIterator __first, _ForwardIterator __last, 02607 const _Tp& __val, _Compare __comp) 02608 { 02609 typedef typename iterator_traits<_ForwardIterator>::value_type 02610 _ValueType; 02611 typedef typename iterator_traits<_ForwardIterator>::difference_type 02612 _DistanceType; 02613 02614 // concept requirements 02615 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) 02616 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, 02617 _ValueType, _Tp>) 02618 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, 02619 _Tp, _ValueType>) 02620 __glibcxx_requires_partitioned_lower_pred(__first, __last, 02621 __val, __comp); 02622 __glibcxx_requires_partitioned_upper_pred(__first, __last, 02623 __val, __comp); 02624 02625 _DistanceType __len = std::distance(__first, __last); 02626 02627 while (__len > 0) 02628 { 02629 _DistanceType __half = __len >> 1; 02630 _ForwardIterator __middle = __first; 02631 std::advance(__middle, __half); 02632 if (__comp(*__middle, __val)) 02633 { 02634 __first = __middle; 02635 ++__first; 02636 __len = __len - __half - 1; 02637 } 02638 else if (__comp(__val, *__middle)) 02639 __len = __half; 02640 else 02641 { 02642 _ForwardIterator __left = std::lower_bound(__first, __middle, 02643 __val, __comp); 02644 std::advance(__first, __len); 02645 _ForwardIterator __right = std::upper_bound(++__middle, __first, 02646 __val, __comp); 02647 return pair<_ForwardIterator, _ForwardIterator>(__left, __right); 02648 } 02649 } 02650 return pair<_ForwardIterator, _ForwardIterator>(__first, __first); 02651 } 02652 02653 /** 02654 * @brief Determines whether an element exists in a range. 02655 * @ingroup binary_search_algorithms 02656 * @param first An iterator. 02657 * @param last Another iterator. 02658 * @param val The search term. 02659 * @return True if @a val (or its equivalent) is in [@a first,@a last ]. 02660 * 02661 * Note that this does not actually return an iterator to @a val. For 02662 * that, use std::find or a container's specialized find member functions. 02663 */ 02664 template<typename _ForwardIterator, typename _Tp> 02665 bool 02666 binary_search(_ForwardIterator __first, _ForwardIterator __last, 02667 const _Tp& __val) 02668 { 02669 typedef typename iterator_traits<_ForwardIterator>::value_type 02670 _ValueType; 02671 02672 // concept requirements 02673 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) 02674 __glibcxx_function_requires(_LessThanOpConcept<_Tp, _ValueType>) 02675 __glibcxx_requires_partitioned_lower(__first, __last, __val); 02676 __glibcxx_requires_partitioned_upper(__first, __last, __val); 02677 02678 _ForwardIterator __i = std::lower_bound(__first, __last, __val); 02679 return __i != __last && !(__val < *__i); 02680 } 02681 02682 /** 02683 * @brief Determines whether an element exists in a range. 02684 * @ingroup binary_search_algorithms 02685 * @param first An iterator. 02686 * @param last Another iterator. 02687 * @param val The search term. 02688 * @param comp A functor to use for comparisons. 02689 * @return True if @a val (or its equivalent) is in [@a first,@a last ]. 02690 * 02691 * Note that this does not actually return an iterator to @a val. For 02692 * that, use std::find or a container's specialized find member functions. 02693 * 02694 * The comparison function should have the same effects on ordering as 02695 * the function used for the initial sort. 02696 */ 02697 template<typename _ForwardIterator, typename _Tp, typename _Compare> 02698 bool 02699 binary_search(_ForwardIterator __first, _ForwardIterator __last, 02700 const _Tp& __val, _Compare __comp) 02701 { 02702 typedef typename iterator_traits<_ForwardIterator>::value_type 02703 _ValueType; 02704 02705 // concept requirements 02706 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) 02707 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, 02708 _Tp, _ValueType>) 02709 __glibcxx_requires_partitioned_lower_pred(__first, __last, 02710 __val, __comp); 02711 __glibcxx_requires_partitioned_upper_pred(__first, __last, 02712 __val, __comp); 02713 02714 _ForwardIterator __i = std::lower_bound(__first, __last, __val, __comp); 02715 return __i != __last && !bool(__comp(__val, *__i)); 02716 } 02717 02718 // merge 02719 02720 /// This is a helper function for the __merge_adaptive routines. 02721 template<typename _InputIterator1, typename _InputIterator2, 02722 typename _OutputIterator> 02723 void 02724 __move_merge_adaptive(_InputIterator1 __first1, _InputIterator1 __last1, 02725 _InputIterator2 __first2, _InputIterator2 __last2, 02726 _OutputIterator __result) 02727 { 02728 while (__first1 != __last1 && __first2 != __last2) 02729 { 02730 if (*__first2 < *__first1) 02731 { 02732 *__result = _GLIBCXX_MOVE(*__first2); 02733 ++__first2; 02734 } 02735 else 02736 { 02737 *__result = _GLIBCXX_MOVE(*__first1); 02738 ++__first1; 02739 } 02740 ++__result; 02741 } 02742 if (__first1 != __last1) 02743 _GLIBCXX_MOVE3(__first1, __last1, __result); 02744 } 02745 02746 /// This is a helper function for the __merge_adaptive routines. 02747 template<typename _InputIterator1, typename _InputIterator2, 02748 typename _OutputIterator, typename _Compare> 02749 void 02750 __move_merge_adaptive(_InputIterator1 __first1, _InputIterator1 __last1, 02751 _InputIterator2 __first2, _InputIterator2 __last2, 02752 _OutputIterator __result, _Compare __comp) 02753 { 02754 while (__first1 != __last1 && __first2 != __last2) 02755 { 02756 if (__comp(*__first2, *__first1)) 02757 { 02758 *__result = _GLIBCXX_MOVE(*__first2); 02759 ++__first2; 02760 } 02761 else 02762 { 02763 *__result = _GLIBCXX_MOVE(*__first1); 02764 ++__first1; 02765 } 02766 ++__result; 02767 } 02768 if (__first1 != __last1) 02769 _GLIBCXX_MOVE3(__first1, __last1, __result); 02770 } 02771 02772 /// This is a helper function for the __merge_adaptive routines. 02773 template<typename _BidirectionalIterator1, typename _BidirectionalIterator2, 02774 typename _BidirectionalIterator3> 02775 void 02776 __move_merge_adaptive_backward(_BidirectionalIterator1 __first1, 02777 _BidirectionalIterator1 __last1, 02778 _BidirectionalIterator2 __first2, 02779 _BidirectionalIterator2 __last2, 02780 _BidirectionalIterator3 __result) 02781 { 02782 if (__first1 == __last1) 02783 { 02784 _GLIBCXX_MOVE_BACKWARD3(__first2, __last2, __result); 02785 return; 02786 } 02787 else if (__first2 == __last2) 02788 return; 02789 02790 --__last1; 02791 --__last2; 02792 while (true) 02793 { 02794 if (*__last2 < *__last1) 02795 { 02796 *--__result = _GLIBCXX_MOVE(*__last1); 02797 if (__first1 == __last1) 02798 { 02799 _GLIBCXX_MOVE_BACKWARD3(__first2, ++__last2, __result); 02800 return; 02801 } 02802 --__last1; 02803 } 02804 else 02805 { 02806 *--__result = _GLIBCXX_MOVE(*__last2); 02807 if (__first2 == __last2) 02808 return; 02809 --__last2; 02810 } 02811 } 02812 } 02813 02814 /// This is a helper function for the __merge_adaptive routines. 02815 template<typename _BidirectionalIterator1, typename _BidirectionalIterator2, 02816 typename _BidirectionalIterator3, typename _Compare> 02817 void 02818 __move_merge_adaptive_backward(_BidirectionalIterator1 __first1, 02819 _BidirectionalIterator1 __last1, 02820 _BidirectionalIterator2 __first2, 02821 _BidirectionalIterator2 __last2, 02822 _BidirectionalIterator3 __result, 02823 _Compare __comp) 02824 { 02825 if (__first1 == __last1) 02826 { 02827 _GLIBCXX_MOVE_BACKWARD3(__first2, __last2, __result); 02828 return; 02829 } 02830 else if (__first2 == __last2) 02831 return; 02832 02833 --__last1; 02834 --__last2; 02835 while (true) 02836 { 02837 if (__comp(*__last2, *__last1)) 02838 { 02839 *--__result = _GLIBCXX_MOVE(*__last1); 02840 if (__first1 == __last1) 02841 { 02842 _GLIBCXX_MOVE_BACKWARD3(__first2, ++__last2, __result); 02843 return; 02844 } 02845 --__last1; 02846 } 02847 else 02848 { 02849 *--__result = _GLIBCXX_MOVE(*__last2); 02850 if (__first2 == __last2) 02851 return; 02852 --__last2; 02853 } 02854 } 02855 } 02856 02857 /// This is a helper function for the merge routines. 02858 template<typename _BidirectionalIterator1, typename _BidirectionalIterator2, 02859 typename _Distance> 02860 _BidirectionalIterator1 02861 __rotate_adaptive(_BidirectionalIterator1 __first, 02862 _BidirectionalIterator1 __middle, 02863 _BidirectionalIterator1 __last, 02864 _Distance __len1, _Distance __len2, 02865 _BidirectionalIterator2 __buffer, 02866 _Distance __buffer_size) 02867 { 02868 _BidirectionalIterator2 __buffer_end; 02869 if (__len1 > __len2 && __len2 <= __buffer_size) 02870 { 02871 if (__len2) 02872 { 02873 __buffer_end = _GLIBCXX_MOVE3(__middle, __last, __buffer); 02874 _GLIBCXX_MOVE_BACKWARD3(__first, __middle, __last); 02875 return _GLIBCXX_MOVE3(__buffer, __buffer_end, __first); 02876 } 02877 else 02878 return __first; 02879 } 02880 else if (__len1 <= __buffer_size) 02881 { 02882 if (__len1) 02883 { 02884 __buffer_end = _GLIBCXX_MOVE3(__first, __middle, __buffer); 02885 _GLIBCXX_MOVE3(__middle, __last, __first); 02886 return _GLIBCXX_MOVE_BACKWARD3(__buffer, __buffer_end, __last); 02887 } 02888 else 02889 return __last; 02890 } 02891 else 02892 { 02893 std::rotate(__first, __middle, __last); 02894 std::advance(__first, std::distance(__middle, __last)); 02895 return __first; 02896 } 02897 } 02898 02899 /// This is a helper function for the merge routines. 02900 template<typename _BidirectionalIterator, typename _Distance, 02901 typename _Pointer> 02902 void 02903 __merge_adaptive(_BidirectionalIterator __first, 02904 _BidirectionalIterator __middle, 02905 _BidirectionalIterator __last, 02906 _Distance __len1, _Distance __len2, 02907 _Pointer __buffer, _Distance __buffer_size) 02908 { 02909 if (__len1 <= __len2 && __len1 <= __buffer_size) 02910 { 02911 _Pointer __buffer_end = _GLIBCXX_MOVE3(__first, __middle, __buffer); 02912 std::__move_merge_adaptive(__buffer, __buffer_end, __middle, __last, 02913 __first); 02914 } 02915 else if (__len2 <= __buffer_size) 02916 { 02917 _Pointer __buffer_end = _GLIBCXX_MOVE3(__middle, __last, __buffer); 02918 std::__move_merge_adaptive_backward(__first, __middle, __buffer, 02919 __buffer_end, __last); 02920 } 02921 else 02922 { 02923 _BidirectionalIterator __first_cut = __first; 02924 _BidirectionalIterator __second_cut = __middle; 02925 _Distance __len11 = 0; 02926 _Distance __len22 = 0; 02927 if (__len1 > __len2) 02928 { 02929 __len11 = __len1 / 2; 02930 std::advance(__first_cut, __len11); 02931 __second_cut = std::lower_bound(__middle, __last, 02932 *__first_cut); 02933 __len22 = std::distance(__middle, __second_cut); 02934 } 02935 else 02936 { 02937 __len22 = __len2 / 2; 02938 std::advance(__second_cut, __len22); 02939 __first_cut = std::upper_bound(__first, __middle, 02940 *__second_cut); 02941 __len11 = std::distance(__first, __first_cut); 02942 } 02943 _BidirectionalIterator __new_middle = 02944 std::__rotate_adaptive(__first_cut, __middle, __second_cut, 02945 __len1 - __len11, __len22, __buffer, 02946 __buffer_size); 02947 std::__merge_adaptive(__first, __first_cut, __new_middle, __len11, 02948 __len22, __buffer, __buffer_size); 02949 std::__merge_adaptive(__new_middle, __second_cut, __last, 02950 __len1 - __len11, 02951 __len2 - __len22, __buffer, __buffer_size); 02952 } 02953 } 02954 02955 /// This is a helper function for the merge routines. 02956 template<typename _BidirectionalIterator, typename _Distance, 02957 typename _Pointer, typename _Compare> 02958 void 02959 __merge_adaptive(_BidirectionalIterator __first, 02960 _BidirectionalIterator __middle, 02961 _BidirectionalIterator __last, 02962 _Distance __len1, _Distance __len2, 02963 _Pointer __buffer, _Distance __buffer_size, 02964 _Compare __comp) 02965 { 02966 if (__len1 <= __len2 && __len1 <= __buffer_size) 02967 { 02968 _Pointer __buffer_end = _GLIBCXX_MOVE3(__first, __middle, __buffer); 02969 std::__move_merge_adaptive(__buffer, __buffer_end, __middle, __last, 02970 __first, __comp); 02971 } 02972 else if (__len2 <= __buffer_size) 02973 { 02974 _Pointer __buffer_end = _GLIBCXX_MOVE3(__middle, __last, __buffer); 02975 std::__move_merge_adaptive_backward(__first, __middle, __buffer, 02976 __buffer_end, __last, __comp); 02977 } 02978 else 02979 { 02980 _BidirectionalIterator __first_cut = __first; 02981 _BidirectionalIterator __second_cut = __middle; 02982 _Distance __len11 = 0; 02983 _Distance __len22 = 0; 02984 if (__len1 > __len2) 02985 { 02986 __len11 = __len1 / 2; 02987 std::advance(__first_cut, __len11); 02988 __second_cut = std::lower_bound(__middle, __last, *__first_cut, 02989 __comp); 02990 __len22 = std::distance(__middle, __second_cut); 02991 } 02992 else 02993 { 02994 __len22 = __len2 / 2; 02995 std::advance(__second_cut, __len22); 02996 __first_cut = std::upper_bound(__first, __middle, *__second_cut, 02997 __comp); 02998 __len11 = std::distance(__first, __first_cut); 02999 } 03000 _BidirectionalIterator __new_middle = 03001 std::__rotate_adaptive(__first_cut, __middle, __second_cut, 03002 __len1 - __len11, __len22, __buffer, 03003 __buffer_size); 03004 std::__merge_adaptive(__first, __first_cut, __new_middle, __len11, 03005 __len22, __buffer, __buffer_size, __comp); 03006 std::__merge_adaptive(__new_middle, __second_cut, __last, 03007 __len1 - __len11, 03008 __len2 - __len22, __buffer, 03009 __buffer_size, __comp); 03010 } 03011 } 03012 03013 /// This is a helper function for the merge routines. 03014 template<typename _BidirectionalIterator, typename _Distance> 03015 void 03016 __merge_without_buffer(_BidirectionalIterator __first, 03017 _BidirectionalIterator __middle, 03018 _BidirectionalIterator __last, 03019 _Distance __len1, _Distance __len2) 03020 { 03021 if (__len1 == 0 || __len2 == 0) 03022 return; 03023 if (__len1 + __len2 == 2) 03024 { 03025 if (*__middle < *__first) 03026 std::iter_swap(__first, __middle); 03027 return; 03028 } 03029 _BidirectionalIterator __first_cut = __first; 03030 _BidirectionalIterator __second_cut = __middle; 03031 _Distance __len11 = 0; 03032 _Distance __len22 = 0; 03033 if (__len1 > __len2) 03034 { 03035 __len11 = __len1 / 2; 03036 std::advance(__first_cut, __len11); 03037 __second_cut = std::lower_bound(__middle, __last, *__first_cut); 03038 __len22 = std::distance(__middle, __second_cut); 03039 } 03040 else 03041 { 03042 __len22 = __len2 / 2; 03043 std::advance(__second_cut, __len22); 03044 __first_cut = std::upper_bound(__first, __middle, *__second_cut); 03045 __len11 = std::distance(__first, __first_cut); 03046 } 03047 std::rotate(__first_cut, __middle, __second_cut); 03048 _BidirectionalIterator __new_middle = __first_cut; 03049 std::advance(__new_middle, std::distance(__middle, __second_cut)); 03050 std::__merge_without_buffer(__first, __first_cut, __new_middle, 03051 __len11, __len22); 03052 std::__merge_without_buffer(__new_middle, __second_cut, __last, 03053 __len1 - __len11, __len2 - __len22); 03054 } 03055 03056 /// This is a helper function for the merge routines. 03057 template<typename _BidirectionalIterator, typename _Distance, 03058 typename _Compare> 03059 void 03060 __merge_without_buffer(_BidirectionalIterator __first, 03061 _BidirectionalIterator __middle, 03062 _BidirectionalIterator __last, 03063 _Distance __len1, _Distance __len2, 03064 _Compare __comp) 03065 { 03066 if (__len1 == 0 || __len2 == 0) 03067 return; 03068 if (__len1 + __len2 == 2) 03069 { 03070 if (__comp(*__middle, *__first)) 03071 std::iter_swap(__first, __middle); 03072 return; 03073 } 03074 _BidirectionalIterator __first_cut = __first; 03075 _BidirectionalIterator __second_cut = __middle; 03076 _Distance __len11 = 0; 03077 _Distance __len22 = 0; 03078 if (__len1 > __len2) 03079 { 03080 __len11 = __len1 / 2; 03081 std::advance(__first_cut, __len11); 03082 __second_cut = std::lower_bound(__middle, __last, *__first_cut, 03083 __comp); 03084 __len22 = std::distance(__middle, __second_cut); 03085 } 03086 else 03087 { 03088 __len22 = __len2 / 2; 03089 std::advance(__second_cut, __len22); 03090 __first_cut = std::upper_bound(__first, __middle, *__second_cut, 03091 __comp); 03092 __len11 = std::distance(__first, __first_cut); 03093 } 03094 std::rotate(__first_cut, __middle, __second_cut); 03095 _BidirectionalIterator __new_middle = __first_cut; 03096 std::advance(__new_middle, std::distance(__middle, __second_cut)); 03097 std::__merge_without_buffer(__first, __first_cut, __new_middle, 03098 __len11, __len22, __comp); 03099 std::__merge_without_buffer(__new_middle, __second_cut, __last, 03100 __len1 - __len11, __len2 - __len22, __comp); 03101 } 03102 03103 /** 03104 * @brief Merges two sorted ranges in place. 03105 * @ingroup sorting_algorithms 03106 * @param first An iterator. 03107 * @param middle Another iterator. 03108 * @param last Another iterator. 03109 * @return Nothing. 03110 * 03111 * Merges two sorted and consecutive ranges, [first,middle) and 03112 * [middle,last), and puts the result in [first,last). The output will 03113 * be sorted. The sort is @e stable, that is, for equivalent 03114 * elements in the two ranges, elements from the first range will always 03115 * come before elements from the second. 03116 * 03117 * If enough additional memory is available, this takes (last-first)-1 03118 * comparisons. Otherwise an NlogN algorithm is used, where N is 03119 * distance(first,last). 03120 */ 03121 template<typename _BidirectionalIterator> 03122 void 03123 inplace_merge(_BidirectionalIterator __first, 03124 _BidirectionalIterator __middle, 03125 _BidirectionalIterator __last) 03126 { 03127 typedef typename iterator_traits<_BidirectionalIterator>::value_type 03128 _ValueType; 03129 typedef typename iterator_traits<_BidirectionalIterator>::difference_type 03130 _DistanceType; 03131 03132 // concept requirements 03133 __glibcxx_function_requires(_Mutable_BidirectionalIteratorConcept< 03134 _BidirectionalIterator>) 03135 __glibcxx_function_requires(_LessThanComparableConcept<_ValueType>) 03136 __glibcxx_requires_sorted(__first, __middle); 03137 __glibcxx_requires_sorted(__middle, __last); 03138 03139 if (__first == __middle || __middle == __last) 03140 return; 03141 03142 _DistanceType __len1 = std::distance(__first, __middle); 03143 _DistanceType __len2 = std::distance(__middle, __last); 03144 03145 _Temporary_buffer<_BidirectionalIterator, _ValueType> __buf(__first, 03146 __last); 03147 if (__buf.begin() == 0) 03148 std::__merge_without_buffer(__first, __middle, __last, __len1, __len2); 03149 else 03150 std::__merge_adaptive(__first, __middle, __last, __len1, __len2, 03151 __buf.begin(), _DistanceType(__buf.size())); 03152 } 03153 03154 /** 03155 * @brief Merges two sorted ranges in place. 03156 * @ingroup sorting_algorithms 03157 * @param first An iterator. 03158 * @param middle Another iterator. 03159 * @param last Another iterator. 03160 * @param comp A functor to use for comparisons. 03161 * @return Nothing. 03162 * 03163 * Merges two sorted and consecutive ranges, [first,middle) and 03164 * [middle,last), and puts the result in [first,last). The output will 03165 * be sorted. The sort is @e stable, that is, for equivalent 03166 * elements in the two ranges, elements from the first range will always 03167 * come before elements from the second. 03168 * 03169 * If enough additional memory is available, this takes (last-first)-1 03170 * comparisons. Otherwise an NlogN algorithm is used, where N is 03171 * distance(first,last). 03172 * 03173 * The comparison function should have the same effects on ordering as 03174 * the function used for the initial sort. 03175 */ 03176 template<typename _BidirectionalIterator, typename _Compare> 03177 void 03178 inplace_merge(_BidirectionalIterator __first, 03179 _BidirectionalIterator __middle, 03180 _BidirectionalIterator __last, 03181 _Compare __comp) 03182 { 03183 typedef typename iterator_traits<_BidirectionalIterator>::value_type 03184 _ValueType; 03185 typedef typename iterator_traits<_BidirectionalIterator>::difference_type 03186 _DistanceType; 03187 03188 // concept requirements 03189 __glibcxx_function_requires(_Mutable_BidirectionalIteratorConcept< 03190 _BidirectionalIterator>) 03191 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, 03192 _ValueType, _ValueType>) 03193 __glibcxx_requires_sorted_pred(__first, __middle, __comp); 03194 __glibcxx_requires_sorted_pred(__middle, __last, __comp); 03195 03196 if (__first == __middle || __middle == __last) 03197 return; 03198 03199 const _DistanceType __len1 = std::distance(__first, __middle); 03200 const _DistanceType __len2 = std::distance(__middle, __last); 03201 03202 _Temporary_buffer<_BidirectionalIterator, _ValueType> __buf(__first, 03203 __last); 03204 if (__buf.begin() == 0) 03205 std::__merge_without_buffer(__first, __middle, __last, __len1, 03206 __len2, __comp); 03207 else 03208 std::__merge_adaptive(__first, __middle, __last, __len1, __len2, 03209 __buf.begin(), _DistanceType(__buf.size()), 03210 __comp); 03211 } 03212 03213 03214 /// This is a helper function for the __merge_sort_loop routines. 03215 template<typename _InputIterator1, typename _InputIterator2, 03216 typename _OutputIterator> 03217 _OutputIterator 03218 __move_merge(_InputIterator1 __first1, _InputIterator1 __last1, 03219 _InputIterator2 __first2, _InputIterator2 __last2, 03220 _OutputIterator __result) 03221 { 03222 while (__first1 != __last1 && __first2 != __last2) 03223 { 03224 if (*__first2 < *__first1) 03225 { 03226 *__result = _GLIBCXX_MOVE(*__first2); 03227 ++__first2; 03228 } 03229 else 03230 { 03231 *__result = _GLIBCXX_MOVE(*__first1); 03232 ++__first1; 03233 } 03234 ++__result; 03235 } 03236 return _GLIBCXX_MOVE3(__first2, __last2, 03237 _GLIBCXX_MOVE3(__first1, __last1, 03238 __result)); 03239 } 03240 03241 /// This is a helper function for the __merge_sort_loop routines. 03242 template<typename _InputIterator1, typename _InputIterator2, 03243 typename _OutputIterator, typename _Compare> 03244 _OutputIterator 03245 __move_merge(_InputIterator1 __first1, _InputIterator1 __last1, 03246 _InputIterator2 __first2, _InputIterator2 __last2, 03247 _OutputIterator __result, _Compare __comp) 03248 { 03249 while (__first1 != __last1 && __first2 != __last2) 03250 { 03251 if (__comp(*__first2, *__first1)) 03252 { 03253 *__result = _GLIBCXX_MOVE(*__first2); 03254 ++__first2; 03255 } 03256 else 03257 { 03258 *__result = _GLIBCXX_MOVE(*__first1); 03259 ++__first1; 03260 } 03261 ++__result; 03262 } 03263 return _GLIBCXX_MOVE3(__first2, __last2, 03264 _GLIBCXX_MOVE3(__first1, __last1, 03265 __result)); 03266 } 03267 03268 template<typename _RandomAccessIterator1, typename _RandomAccessIterator2, 03269 typename _Distance> 03270 void 03271 __merge_sort_loop(_RandomAccessIterator1 __first, 03272 _RandomAccessIterator1 __last, 03273 _RandomAccessIterator2 __result, 03274 _Distance __step_size) 03275 { 03276 const _Distance __two_step = 2 * __step_size; 03277 03278 while (__last - __first >= __two_step) 03279 { 03280 __result = std::__move_merge(__first, __first + __step_size, 03281 __first + __step_size, 03282 __first + __two_step, __result); 03283 __first += __two_step; 03284 } 03285 03286 __step_size = std::min(_Distance(__last - __first), __step_size); 03287 std::__move_merge(__first, __first + __step_size, 03288 __first + __step_size, __last, __result); 03289 } 03290 03291 template<typename _RandomAccessIterator1, typename _RandomAccessIterator2, 03292 typename _Distance, typename _Compare> 03293 void 03294 __merge_sort_loop(_RandomAccessIterator1 __first, 03295 _RandomAccessIterator1 __last, 03296 _RandomAccessIterator2 __result, _Distance __step_size, 03297 _Compare __comp) 03298 { 03299 const _Distance __two_step = 2 * __step_size; 03300 03301 while (__last - __first >= __two_step) 03302 { 03303 __result = std::__move_merge(__first, __first + __step_size, 03304 __first + __step_size, 03305 __first + __two_step, 03306 __result, __comp); 03307 __first += __two_step; 03308 } 03309 __step_size = std::min(_Distance(__last - __first), __step_size); 03310 03311 std::__move_merge(__first,__first + __step_size, 03312 __first + __step_size, __last, __result, __comp); 03313 } 03314 03315 template<typename _RandomAccessIterator, typename _Distance> 03316 void 03317 __chunk_insertion_sort(_RandomAccessIterator __first, 03318 _RandomAccessIterator __last, 03319 _Distance __chunk_size) 03320 { 03321 while (__last - __first >= __chunk_size) 03322 { 03323 std::__insertion_sort(__first, __first + __chunk_size); 03324 __first += __chunk_size; 03325 } 03326 std::__insertion_sort(__first, __last); 03327 } 03328 03329 template<typename _RandomAccessIterator, typename _Distance, 03330 typename _Compare> 03331 void 03332 __chunk_insertion_sort(_RandomAccessIterator __first, 03333 _RandomAccessIterator __last, 03334 _Distance __chunk_size, _Compare __comp) 03335 { 03336 while (__last - __first >= __chunk_size) 03337 { 03338 std::__insertion_sort(__first, __first + __chunk_size, __comp); 03339 __first += __chunk_size; 03340 } 03341 std::__insertion_sort(__first, __last, __comp); 03342 } 03343 03344 enum { _S_chunk_size = 7 }; 03345 03346 template<typename _RandomAccessIterator, typename _Pointer> 03347 void 03348 __merge_sort_with_buffer(_RandomAccessIterator __first, 03349 _RandomAccessIterator __last, 03350 _Pointer __buffer) 03351 { 03352 typedef typename iterator_traits<_RandomAccessIterator>::difference_type 03353 _Distance; 03354 03355 const _Distance __len = __last - __first; 03356 const _Pointer __buffer_last = __buffer + __len; 03357 03358 _Distance __step_size = _S_chunk_size; 03359 std::__chunk_insertion_sort(__first, __last, __step_size); 03360 03361 while (__step_size < __len) 03362 { 03363 std::__merge_sort_loop(__first, __last, __buffer, __step_size); 03364 __step_size *= 2; 03365 std::__merge_sort_loop(__buffer, __buffer_last, __first, __step_size); 03366 __step_size *= 2; 03367 } 03368 } 03369 03370 template<typename _RandomAccessIterator, typename _Pointer, typename _Compare> 03371 void 03372 __merge_sort_with_buffer(_RandomAccessIterator __first, 03373 _RandomAccessIterator __last, 03374 _Pointer __buffer, _Compare __comp) 03375 { 03376 typedef typename iterator_traits<_RandomAccessIterator>::difference_type 03377 _Distance; 03378 03379 const _Distance __len = __last - __first; 03380 const _Pointer __buffer_last = __buffer + __len; 03381 03382 _Distance __step_size = _S_chunk_size; 03383 std::__chunk_insertion_sort(__first, __last, __step_size, __comp); 03384 03385 while (__step_size < __len) 03386 { 03387 std::__merge_sort_loop(__first, __last, __buffer, 03388 __step_size, __comp); 03389 __step_size *= 2; 03390 std::__merge_sort_loop(__buffer, __buffer_last, __first, 03391 __step_size, __comp); 03392 __step_size *= 2; 03393 } 03394 } 03395 03396 template<typename _RandomAccessIterator, typename _Pointer, 03397 typename _Distance> 03398 void 03399 __stable_sort_adaptive(_RandomAccessIterator __first, 03400 _RandomAccessIterator __last, 03401 _Pointer __buffer, _Distance __buffer_size) 03402 { 03403 const _Distance __len = (__last - __first + 1) / 2; 03404 const _RandomAccessIterator __middle = __first + __len; 03405 if (__len > __buffer_size) 03406 { 03407 std::__stable_sort_adaptive(__first, __middle, 03408 __buffer, __buffer_size); 03409 std::__stable_sort_adaptive(__middle, __last, 03410 __buffer, __buffer_size); 03411 } 03412 else 03413 { 03414 std::__merge_sort_with_buffer(__first, __middle, __buffer); 03415 std::__merge_sort_with_buffer(__middle, __last, __buffer); 03416 } 03417 std::__merge_adaptive(__first, __middle, __last, 03418 _Distance(__middle - __first), 03419 _Distance(__last - __middle), 03420 __buffer, __buffer_size); 03421 } 03422 03423 template<typename _RandomAccessIterator, typename _Pointer, 03424 typename _Distance, typename _Compare> 03425 void 03426 __stable_sort_adaptive(_RandomAccessIterator __first, 03427 _RandomAccessIterator __last, 03428 _Pointer __buffer, _Distance __buffer_size, 03429 _Compare __comp) 03430 { 03431 const _Distance __len = (__last - __first + 1) / 2; 03432 const _RandomAccessIterator __middle = __first + __len; 03433 if (__len > __buffer_size) 03434 { 03435 std::__stable_sort_adaptive(__first, __middle, __buffer, 03436 __buffer_size, __comp); 03437 std::__stable_sort_adaptive(__middle, __last, __buffer, 03438 __buffer_size, __comp); 03439 } 03440 else 03441 { 03442 std::__merge_sort_with_buffer(__first, __middle, __buffer, __comp); 03443 std::__merge_sort_with_buffer(__middle, __last, __buffer, __comp); 03444 } 03445 std::__merge_adaptive(__first, __middle, __last, 03446 _Distance(__middle - __first), 03447 _Distance(__last - __middle), 03448 __buffer, __buffer_size, 03449 __comp); 03450 } 03451 03452 /// This is a helper function for the stable sorting routines. 03453 template<typename _RandomAccessIterator> 03454 void 03455 __inplace_stable_sort(_RandomAccessIterator __first, 03456 _RandomAccessIterator __last) 03457 { 03458 if (__last - __first < 15) 03459 { 03460 std::__insertion_sort(__first, __last); 03461 return; 03462 } 03463 _RandomAccessIterator __middle = __first + (__last - __first) / 2; 03464 std::__inplace_stable_sort(__first, __middle); 03465 std::__inplace_stable_sort(__middle, __last); 03466 std::__merge_without_buffer(__first, __middle, __last, 03467 __middle - __first, 03468 __last - __middle); 03469 } 03470 03471 /// This is a helper function for the stable sorting routines. 03472 template<typename _RandomAccessIterator, typename _Compare> 03473 void 03474 __inplace_stable_sort(_RandomAccessIterator __first, 03475 _RandomAccessIterator __last, _Compare __comp) 03476 { 03477 if (__last - __first < 15) 03478 { 03479 std::__insertion_sort(__first, __last, __comp); 03480 return; 03481 } 03482 _RandomAccessIterator __middle = __first + (__last - __first) / 2; 03483 std::__inplace_stable_sort(__first, __middle, __comp); 03484 std::__inplace_stable_sort(__middle, __last, __comp); 03485 std::__merge_without_buffer(__first, __middle, __last, 03486 __middle - __first, 03487 __last - __middle, 03488 __comp); 03489 } 03490 03491 // stable_sort 03492 03493 // Set algorithms: includes, set_union, set_intersection, set_difference, 03494 // set_symmetric_difference. All of these algorithms have the precondition 03495 // that their input ranges are sorted and the postcondition that their output 03496 // ranges are sorted. 03497 03498 /** 03499 * @brief Determines whether all elements of a sequence exists in a range. 03500 * @param first1 Start of search range. 03501 * @param last1 End of search range. 03502 * @param first2 Start of sequence 03503 * @param last2 End of sequence. 03504 * @return True if each element in [first2,last2) is contained in order 03505 * within [first1,last1). False otherwise. 03506 * @ingroup set_algorithms 03507 * 03508 * This operation expects both [first1,last1) and [first2,last2) to be 03509 * sorted. Searches for the presence of each element in [first2,last2) 03510 * within [first1,last1). The iterators over each range only move forward, 03511 * so this is a linear algorithm. If an element in [first2,last2) is not 03512 * found before the search iterator reaches @a last2, false is returned. 03513 */ 03514 template<typename _InputIterator1, typename _InputIterator2> 03515 bool 03516 includes(_InputIterator1 __first1, _InputIterator1 __last1, 03517 _InputIterator2 __first2, _InputIterator2 __last2) 03518 { 03519 typedef typename iterator_traits<_InputIterator1>::value_type 03520 _ValueType1; 03521 typedef typename iterator_traits<_InputIterator2>::value_type 03522 _ValueType2; 03523 03524 // concept requirements 03525 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>) 03526 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>) 03527 __glibcxx_function_requires(_LessThanOpConcept<_ValueType1, _ValueType2>) 03528 __glibcxx_function_requires(_LessThanOpConcept<_ValueType2, _ValueType1>) 03529 __glibcxx_requires_sorted_set(__first1, __last1, __first2); 03530 __glibcxx_requires_sorted_set(__first2, __last2, __first1); 03531 03532 while (__first1 != __last1 && __first2 != __last2) 03533 if (*__first2 < *__first1) 03534 return false; 03535 else if(*__first1 < *__first2) 03536 ++__first1; 03537 else 03538 ++__first1, ++__first2; 03539 03540 return __first2 == __last2; 03541 } 03542 03543 /** 03544 * @brief Determines whether all elements of a sequence exists in a range 03545 * using comparison. 03546 * @ingroup set_algorithms 03547 * @param first1 Start of search range. 03548 * @param last1 End of search range. 03549 * @param first2 Start of sequence 03550 * @param last2 End of sequence. 03551 * @param comp Comparison function to use. 03552 * @return True if each element in [first2,last2) is contained in order 03553 * within [first1,last1) according to comp. False otherwise. 03554 * @ingroup set_algorithms 03555 * 03556 * This operation expects both [first1,last1) and [first2,last2) to be 03557 * sorted. Searches for the presence of each element in [first2,last2) 03558 * within [first1,last1), using comp to decide. The iterators over each 03559 * range only move forward, so this is a linear algorithm. If an element 03560 * in [first2,last2) is not found before the search iterator reaches @a 03561 * last2, false is returned. 03562 */ 03563 template<typename _InputIterator1, typename _InputIterator2, 03564 typename _Compare> 03565 bool 03566 includes(_InputIterator1 __first1, _InputIterator1 __last1, 03567 _InputIterator2 __first2, _InputIterator2 __last2, 03568 _Compare __comp) 03569 { 03570 typedef typename iterator_traits<_InputIterator1>::value_type 03571 _ValueType1; 03572 typedef typename iterator_traits<_InputIterator2>::value_type 03573 _ValueType2; 03574 03575 // concept requirements 03576 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>) 03577 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>) 03578 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, 03579 _ValueType1, _ValueType2>) 03580 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, 03581 _ValueType2, _ValueType1>) 03582 __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp); 03583 __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp); 03584 03585 while (__first1 != __last1 && __first2 != __last2) 03586 if (__comp(*__first2, *__first1)) 03587 return false; 03588 else if(__comp(*__first1, *__first2)) 03589 ++__first1; 03590 else 03591 ++__first1, ++__first2; 03592 03593 return __first2 == __last2; 03594 } 03595 03596 // nth_element 03597 // merge 03598 // set_difference 03599 // set_intersection 03600 // set_union 03601 // stable_sort 03602 // set_symmetric_difference 03603 // min_element 03604 // max_element 03605 03606 /** 03607 * @brief Permute range into the next @a dictionary ordering. 03608 * @ingroup sorting_algorithms 03609 * @param first Start of range. 03610 * @param last End of range. 03611 * @return False if wrapped to first permutation, true otherwise. 03612 * 03613 * Treats all permutations of the range as a set of @a dictionary sorted 03614 * sequences. Permutes the current sequence into the next one of this set. 03615 * Returns true if there are more sequences to generate. If the sequence 03616 * is the largest of the set, the smallest is generated and false returned. 03617 */ 03618 template<typename _BidirectionalIterator> 03619 bool 03620 next_permutation(_BidirectionalIterator __first, 03621 _BidirectionalIterator __last) 03622 { 03623 // concept requirements 03624 __glibcxx_function_requires(_BidirectionalIteratorConcept< 03625 _BidirectionalIterator>) 03626 __glibcxx_function_requires(_LessThanComparableConcept< 03627 typename iterator_traits<_BidirectionalIterator>::value_type>) 03628 __glibcxx_requires_valid_range(__first, __last); 03629 03630 if (__first == __last) 03631 return false; 03632 _BidirectionalIterator __i = __first; 03633 ++__i; 03634 if (__i == __last) 03635 return false; 03636 __i = __last; 03637 --__i; 03638 03639 for(;;) 03640 { 03641 _BidirectionalIterator __ii = __i; 03642 --__i; 03643 if (*__i < *__ii) 03644 { 03645 _BidirectionalIterator __j = __last; 03646 while (!(*__i < *--__j)) 03647 {} 03648 std::iter_swap(__i, __j); 03649 std::reverse(__ii, __last); 03650 return true; 03651 } 03652 if (__i == __first) 03653 { 03654 std::reverse(__first, __last); 03655 return false; 03656 } 03657 } 03658 } 03659 03660 /** 03661 * @brief Permute range into the next @a dictionary ordering using 03662 * comparison functor. 03663 * @ingroup sorting_algorithms 03664 * @param first Start of range. 03665 * @param last End of range. 03666 * @param comp A comparison functor. 03667 * @return False if wrapped to first permutation, true otherwise. 03668 * 03669 * Treats all permutations of the range [first,last) as a set of 03670 * @a dictionary sorted sequences ordered by @a comp. Permutes the current 03671 * sequence into the next one of this set. Returns true if there are more 03672 * sequences to generate. If the sequence is the largest of the set, the 03673 * smallest is generated and false returned. 03674 */ 03675 template<typename _BidirectionalIterator, typename _Compare> 03676 bool 03677 next_permutation(_BidirectionalIterator __first, 03678 _BidirectionalIterator __last, _Compare __comp) 03679 { 03680 // concept requirements 03681 __glibcxx_function_requires(_BidirectionalIteratorConcept< 03682 _BidirectionalIterator>) 03683 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, 03684 typename iterator_traits<_BidirectionalIterator>::value_type, 03685 typename iterator_traits<_BidirectionalIterator>::value_type>) 03686 __glibcxx_requires_valid_range(__first, __last); 03687 03688 if (__first == __last) 03689 return false; 03690 _BidirectionalIterator __i = __first; 03691 ++__i; 03692 if (__i == __last) 03693 return false; 03694 __i = __last; 03695 --__i; 03696 03697 for(;;) 03698 { 03699 _BidirectionalIterator __ii = __i; 03700 --__i; 03701 if (__comp(*__i, *__ii)) 03702 { 03703 _BidirectionalIterator __j = __last; 03704 while (!bool(__comp(*__i, *--__j))) 03705 {} 03706 std::iter_swap(__i, __j); 03707 std::reverse(__ii, __last); 03708 return true; 03709 } 03710 if (__i == __first) 03711 { 03712 std::reverse(__first, __last); 03713 return false; 03714 } 03715 } 03716 } 03717 03718 /** 03719 * @brief Permute range into the previous @a dictionary ordering. 03720 * @ingroup sorting_algorithms 03721 * @param first Start of range. 03722 * @param last End of range. 03723 * @return False if wrapped to last permutation, true otherwise. 03724 * 03725 * Treats all permutations of the range as a set of @a dictionary sorted 03726 * sequences. Permutes the current sequence into the previous one of this 03727 * set. Returns true if there are more sequences to generate. If the 03728 * sequence is the smallest of the set, the largest is generated and false 03729 * returned. 03730 */ 03731 template<typename _BidirectionalIterator> 03732 bool 03733 prev_permutation(_BidirectionalIterator __first, 03734 _BidirectionalIterator __last) 03735 { 03736 // concept requirements 03737 __glibcxx_function_requires(_BidirectionalIteratorConcept< 03738 _BidirectionalIterator>) 03739 __glibcxx_function_requires(_LessThanComparableConcept< 03740 typename iterator_traits<_BidirectionalIterator>::value_type>) 03741 __glibcxx_requires_valid_range(__first, __last); 03742 03743 if (__first == __last) 03744 return false; 03745 _BidirectionalIterator __i = __first; 03746 ++__i; 03747 if (__i == __last) 03748 return false; 03749 __i = __last; 03750 --__i; 03751 03752 for(;;) 03753 { 03754 _BidirectionalIterator __ii = __i; 03755 --__i; 03756 if (*__ii < *__i) 03757 { 03758 _BidirectionalIterator __j = __last; 03759 while (!(*--__j < *__i)) 03760 {} 03761 std::iter_swap(__i, __j); 03762 std::reverse(__ii, __last); 03763 return true; 03764 } 03765 if (__i == __first) 03766 { 03767 std::reverse(__first, __last); 03768 return false; 03769 } 03770 } 03771 } 03772 03773 /** 03774 * @brief Permute range into the previous @a dictionary ordering using 03775 * comparison functor. 03776 * @ingroup sorting_algorithms 03777 * @param first Start of range. 03778 * @param last End of range. 03779 * @param comp A comparison functor. 03780 * @return False if wrapped to last permutation, true otherwise. 03781 * 03782 * Treats all permutations of the range [first,last) as a set of 03783 * @a dictionary sorted sequences ordered by @a comp. Permutes the current 03784 * sequence into the previous one of this set. Returns true if there are 03785 * more sequences to generate. If the sequence is the smallest of the set, 03786 * the largest is generated and false returned. 03787 */ 03788 template<typename _BidirectionalIterator, typename _Compare> 03789 bool 03790 prev_permutation(_BidirectionalIterator __first, 03791 _BidirectionalIterator __last, _Compare __comp) 03792 { 03793 // concept requirements 03794 __glibcxx_function_requires(_BidirectionalIteratorConcept< 03795 _BidirectionalIterator>) 03796 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, 03797 typename iterator_traits<_BidirectionalIterator>::value_type, 03798 typename iterator_traits<_BidirectionalIterator>::value_type>) 03799 __glibcxx_requires_valid_range(__first, __last); 03800 03801 if (__first == __last) 03802 return false; 03803 _BidirectionalIterator __i = __first; 03804 ++__i; 03805 if (__i == __last) 03806 return false; 03807 __i = __last; 03808 --__i; 03809 03810 for(;;) 03811 { 03812 _BidirectionalIterator __ii = __i; 03813 --__i; 03814 if (__comp(*__ii, *__i)) 03815 { 03816 _BidirectionalIterator __j = __last; 03817 while (!bool(__comp(*--__j, *__i))) 03818 {} 03819 std::iter_swap(__i, __j); 03820 std::reverse(__ii, __last); 03821 return true; 03822 } 03823 if (__i == __first) 03824 { 03825 std::reverse(__first, __last); 03826 return false; 03827 } 03828 } 03829 } 03830 03831 // replace 03832 // replace_if 03833 03834 /** 03835 * @brief Copy a sequence, replacing each element of one value with another 03836 * value. 03837 * @param first An input iterator. 03838 * @param last An input iterator. 03839 * @param result An output iterator. 03840 * @param old_value The value to be replaced. 03841 * @param new_value The replacement value. 03842 * @return The end of the output sequence, @p result+(last-first). 03843 * 03844 * Copies each element in the input range @p [first,last) to the 03845 * output range @p [result,result+(last-first)) replacing elements 03846 * equal to @p old_value with @p new_value. 03847 */ 03848 template<typename _InputIterator, typename _OutputIterator, typename _Tp> 03849 _OutputIterator 03850 replace_copy(_InputIterator __first, _InputIterator __last, 03851 _OutputIterator __result, 03852 const _Tp& __old_value, const _Tp& __new_value) 03853 { 03854 // concept requirements 03855 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) 03856 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, 03857 typename iterator_traits<_InputIterator>::value_type>) 03858 __glibcxx_function_requires(_EqualOpConcept< 03859 typename iterator_traits<_InputIterator>::value_type, _Tp>) 03860 __glibcxx_requires_valid_range(__first, __last); 03861 03862 for (; __first != __last; ++__first, ++__result) 03863 if (*__first == __old_value) 03864 *__result = __new_value; 03865 else 03866 *__result = *__first; 03867 return __result; 03868 } 03869 03870 /** 03871 * @brief Copy a sequence, replacing each value for which a predicate 03872 * returns true with another value. 03873 * @ingroup mutating_algorithms 03874 * @param first An input iterator. 03875 * @param last An input iterator. 03876 * @param result An output iterator. 03877 * @param pred A predicate. 03878 * @param new_value The replacement value. 03879 * @return The end of the output sequence, @p result+(last-first). 03880 * 03881 * Copies each element in the range @p [first,last) to the range 03882 * @p [result,result+(last-first)) replacing elements for which 03883 * @p pred returns true with @p new_value. 03884 */ 03885 template<typename _InputIterator, typename _OutputIterator, 03886 typename _Predicate, typename _Tp> 03887 _OutputIterator 03888 replace_copy_if(_InputIterator __first, _InputIterator __last, 03889 _OutputIterator __result, 03890 _Predicate __pred, const _Tp& __new_value) 03891 { 03892 // concept requirements 03893 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) 03894 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, 03895 typename iterator_traits<_InputIterator>::value_type>) 03896 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate, 03897 typename iterator_traits<_InputIterator>::value_type>) 03898 __glibcxx_requires_valid_range(__first, __last); 03899 03900 for (; __first != __last; ++__first, ++__result) 03901 if (__pred(*__first)) 03902 *__result = __new_value; 03903 else 03904 *__result = *__first; 03905 return __result; 03906 } 03907 03908 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 03909 /** 03910 * @brief Determines whether the elements of a sequence are sorted. 03911 * @ingroup sorting_algorithms 03912 * @param first An iterator. 03913 * @param last Another iterator. 03914 * @return True if the elements are sorted, false otherwise. 03915 */ 03916 template<typename _ForwardIterator> 03917 inline bool 03918 is_sorted(_ForwardIterator __first, _ForwardIterator __last) 03919 { return std::is_sorted_until(__first, __last) == __last; } 03920 03921 /** 03922 * @brief Determines whether the elements of a sequence are sorted 03923 * according to a comparison functor. 03924 * @ingroup sorting_algorithms 03925 * @param first An iterator. 03926 * @param last Another iterator. 03927 * @param comp A comparison functor. 03928 * @return True if the elements are sorted, false otherwise. 03929 */ 03930 template<typename _ForwardIterator, typename _Compare> 03931 inline bool 03932 is_sorted(_ForwardIterator __first, _ForwardIterator __last, 03933 _Compare __comp) 03934 { return std::is_sorted_until(__first, __last, __comp) == __last; } 03935 03936 /** 03937 * @brief Determines the end of a sorted sequence. 03938 * @ingroup sorting_algorithms 03939 * @param first An iterator. 03940 * @param last Another iterator. 03941 * @return An iterator pointing to the last iterator i in [first, last) 03942 * for which the range [first, i) is sorted. 03943 */ 03944 template<typename _ForwardIterator> 03945 _ForwardIterator 03946 is_sorted_until(_ForwardIterator __first, _ForwardIterator __last) 03947 { 03948 // concept requirements 03949 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) 03950 __glibcxx_function_requires(_LessThanComparableConcept< 03951 typename iterator_traits<_ForwardIterator>::value_type>) 03952 __glibcxx_requires_valid_range(__first, __last); 03953 03954 if (__first == __last) 03955 return __last; 03956 03957 _ForwardIterator __next = __first; 03958 for (++__next; __next != __last; __first = __next, ++__next) 03959 if (*__next < *__first) 03960 return __next; 03961 return __next; 03962 } 03963 03964 /** 03965 * @brief Determines the end of a sorted sequence using comparison functor. 03966 * @ingroup sorting_algorithms 03967 * @param first An iterator. 03968 * @param last Another iterator. 03969 * @param comp A comparison functor. 03970 * @return An iterator pointing to the last iterator i in [first, last) 03971 * for which the range [first, i) is sorted. 03972 */ 03973 template<typename _ForwardIterator, typename _Compare> 03974 _ForwardIterator 03975 is_sorted_until(_ForwardIterator __first, _ForwardIterator __last, 03976 _Compare __comp) 03977 { 03978 // concept requirements 03979 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) 03980 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, 03981 typename iterator_traits<_ForwardIterator>::value_type, 03982 typename iterator_traits<_ForwardIterator>::value_type>) 03983 __glibcxx_requires_valid_range(__first, __last); 03984 03985 if (__first == __last) 03986 return __last; 03987 03988 _ForwardIterator __next = __first; 03989 for (++__next; __next != __last; __first = __next, ++__next) 03990 if (__comp(*__next, *__first)) 03991 return __next; 03992 return __next; 03993 } 03994 03995 /** 03996 * @brief Determines min and max at once as an ordered pair. 03997 * @ingroup sorting_algorithms 03998 * @param a A thing of arbitrary type. 03999 * @param b Another thing of arbitrary type. 04000 * @return A pair(b, a) if b is smaller than a, pair(a, b) otherwise. 04001 */ 04002 template<typename _Tp> 04003 inline pair<const _Tp&, const _Tp&> 04004 minmax(const _Tp& __a, const _Tp& __b) 04005 { 04006 // concept requirements 04007 __glibcxx_function_requires(_LessThanComparableConcept<_Tp>) 04008 04009 return __b < __a ? pair<const _Tp&, const _Tp&>(__b, __a) 04010 : pair<const _Tp&, const _Tp&>(__a, __b); 04011 } 04012 04013 /** 04014 * @brief Determines min and max at once as an ordered pair. 04015 * @ingroup sorting_algorithms 04016 * @param a A thing of arbitrary type. 04017 * @param b Another thing of arbitrary type. 04018 * @param comp A @link comparison_functor comparison functor@endlink. 04019 * @return A pair(b, a) if b is smaller than a, pair(a, b) otherwise. 04020 */ 04021 template<typename _Tp, typename _Compare> 04022 inline pair<const _Tp&, const _Tp&> 04023 minmax(const _Tp& __a, const _Tp& __b, _Compare __comp) 04024 { 04025 return __comp(__b, __a) ? pair<const _Tp&, const _Tp&>(__b, __a) 04026 : pair<const _Tp&, const _Tp&>(__a, __b); 04027 } 04028 04029 /** 04030 * @brief Return a pair of iterators pointing to the minimum and maximum 04031 * elements in a range. 04032 * @ingroup sorting_algorithms 04033 * @param first Start of range. 04034 * @param last End of range. 04035 * @return make_pair(m, M), where m is the first iterator i in 04036 * [first, last) such that no other element in the range is 04037 * smaller, and where M is the last iterator i in [first, last) 04038 * such that no other element in the range is larger. 04039 */ 04040 template<typename _ForwardIterator> 04041 pair<_ForwardIterator, _ForwardIterator> 04042 minmax_element(_ForwardIterator __first, _ForwardIterator __last) 04043 { 04044 // concept requirements 04045 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) 04046 __glibcxx_function_requires(_LessThanComparableConcept< 04047 typename iterator_traits<_ForwardIterator>::value_type>) 04048 __glibcxx_requires_valid_range(__first, __last); 04049 04050 _ForwardIterator __next = __first; 04051 if (__first == __last 04052 || ++__next == __last) 04053 return std::make_pair(__first, __first); 04054 04055 _ForwardIterator __min, __max; 04056 if (*__next < *__first) 04057 { 04058 __min = __next; 04059 __max = __first; 04060 } 04061 else 04062 { 04063 __min = __first; 04064 __max = __next; 04065 } 04066 04067 __first = __next; 04068 ++__first; 04069 04070 while (__first != __last) 04071 { 04072 __next = __first; 04073 if (++__next == __last) 04074 { 04075 if (*__first < *__min) 04076 __min = __first; 04077 else if (!(*__first < *__max)) 04078 __max = __first; 04079 break; 04080 } 04081 04082 if (*__next < *__first) 04083 { 04084 if (*__next < *__min) 04085 __min = __next; 04086 if (!(*__first < *__max)) 04087 __max = __first; 04088 } 04089 else 04090 { 04091 if (*__first < *__min) 04092 __min = __first; 04093 if (!(*__next < *__max)) 04094 __max = __next; 04095 } 04096 04097 __first = __next; 04098 ++__first; 04099 } 04100 04101 return std::make_pair(__min, __max); 04102 } 04103 04104 /** 04105 * @brief Return a pair of iterators pointing to the minimum and maximum 04106 * elements in a range. 04107 * @ingroup sorting_algorithms 04108 * @param first Start of range. 04109 * @param last End of range. 04110 * @param comp Comparison functor. 04111 * @return make_pair(m, M), where m is the first iterator i in 04112 * [first, last) such that no other element in the range is 04113 * smaller, and where M is the last iterator i in [first, last) 04114 * such that no other element in the range is larger. 04115 */ 04116 template<typename _ForwardIterator, typename _Compare> 04117 pair<_ForwardIterator, _ForwardIterator> 04118 minmax_element(_ForwardIterator __first, _ForwardIterator __last, 04119 _Compare __comp) 04120 { 04121 // concept requirements 04122 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) 04123 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, 04124 typename iterator_traits<_ForwardIterator>::value_type, 04125 typename iterator_traits<_ForwardIterator>::value_type>) 04126 __glibcxx_requires_valid_range(__first, __last); 04127 04128 _ForwardIterator __next = __first; 04129 if (__first == __last 04130 || ++__next == __last) 04131 return std::make_pair(__first, __first); 04132 04133 _ForwardIterator __min, __max; 04134 if (__comp(*__next, *__first)) 04135 { 04136 __min = __next; 04137 __max = __first; 04138 } 04139 else 04140 { 04141 __min = __first; 04142 __max = __next; 04143 } 04144 04145 __first = __next; 04146 ++__first; 04147 04148 while (__first != __last) 04149 { 04150 __next = __first; 04151 if (++__next == __last) 04152 { 04153 if (__comp(*__first, *__min)) 04154 __min = __first; 04155 else if (!__comp(*__first, *__max)) 04156 __max = __first; 04157 break; 04158 } 04159 04160 if (__comp(*__next, *__first)) 04161 { 04162 if (__comp(*__next, *__min)) 04163 __min = __next; 04164 if (!__comp(*__first, *__max)) 04165 __max = __first; 04166 } 04167 else 04168 { 04169 if (__comp(*__first, *__min)) 04170 __min = __first; 04171 if (!__comp(*__next, *__max)) 04172 __max = __next; 04173 } 04174 04175 __first = __next; 04176 ++__first; 04177 } 04178 04179 return std::make_pair(__min, __max); 04180 } 04181 04182 // N2722 + DR 915. 04183 template<typename _Tp> 04184 inline _Tp 04185 min(initializer_list<_Tp> __l) 04186 { return *std::min_element(__l.begin(), __l.end()); } 04187 04188 template<typename _Tp, typename _Compare> 04189 inline _Tp 04190 min(initializer_list<_Tp> __l, _Compare __comp) 04191 { return *std::min_element(__l.begin(), __l.end(), __comp); } 04192 04193 template<typename _Tp> 04194 inline _Tp 04195 max(initializer_list<_Tp> __l) 04196 { return *std::max_element(__l.begin(), __l.end()); } 04197 04198 template<typename _Tp, typename _Compare> 04199 inline _Tp 04200 max(initializer_list<_Tp> __l, _Compare __comp) 04201 { return *std::max_element(__l.begin(), __l.end(), __comp); } 04202 04203 template<typename _Tp> 04204 inline pair<_Tp, _Tp> 04205 minmax(initializer_list<_Tp> __l) 04206 { 04207 pair<const _Tp*, const _Tp*> __p = 04208 std::minmax_element(__l.begin(), __l.end()); 04209 return std::make_pair(*__p.first, *__p.second); 04210 } 04211 04212 template<typename _Tp, typename _Compare> 04213 inline pair<_Tp, _Tp> 04214 minmax(initializer_list<_Tp> __l, _Compare __comp) 04215 { 04216 pair<const _Tp*, const _Tp*> __p = 04217 std::minmax_element(__l.begin(), __l.end(), __comp); 04218 return std::make_pair(*__p.first, *__p.second); 04219 } 04220 04221 /** 04222 * @brief Checks whether a permutaion of the second sequence is equal 04223 * to the first sequence. 04224 * @ingroup non_mutating_algorithms 04225 * @param first1 Start of first range. 04226 * @param last1 End of first range. 04227 * @param first2 Start of second range. 04228 * @return true if there exists a permutation of the elements in the range 04229 * [first2, first2 + (last1 - first1)), beginning with 04230 * ForwardIterator2 begin, such that equal(first1, last1, begin) 04231 * returns true; otherwise, returns false. 04232 */ 04233 template<typename _ForwardIterator1, typename _ForwardIterator2> 04234 bool 04235 is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1, 04236 _ForwardIterator2 __first2) 04237 { 04238 // Efficiently compare identical prefixes: O(N) if sequences 04239 // have the same elements in the same order. 04240 for (; __first1 != __last1; ++__first1, ++__first2) 04241 if (!(*__first1 == *__first2)) 04242 break; 04243 04244 if (__first1 == __last1) 04245 return true; 04246 04247 // Establish __last2 assuming equal ranges by iterating over the 04248 // rest of the list. 04249 _ForwardIterator2 __last2 = __first2; 04250 std::advance(__last2, std::distance(__first1, __last1)); 04251 for (_ForwardIterator1 __scan = __first1; __scan != __last1; ++__scan) 04252 { 04253 if (__scan != _GLIBCXX_STD_A::find(__first1, __scan, *__scan)) 04254 continue; // We've seen this one before. 04255 04256 auto __matches = std::count(__first2, __last2, *__scan); 04257 if (0 == __matches 04258 || std::count(__scan, __last1, *__scan) != __matches) 04259 return false; 04260 } 04261 return true; 04262 } 04263 04264 /** 04265 * @brief Checks whether a permutation of the second sequence is equal 04266 * to the first sequence. 04267 * @ingroup non_mutating_algorithms 04268 * @param first1 Start of first range. 04269 * @param last1 End of first range. 04270 * @param first2 Start of second range. 04271 * @param pred A binary predicate. 04272 * @return true if there exists a permutation of the elements in the range 04273 * [first2, first2 + (last1 - first1)), beginning with 04274 * ForwardIterator2 begin, such that equal(first1, last1, begin, 04275 * pred) returns true; otherwise, returns false. 04276 */ 04277 template<typename _ForwardIterator1, typename _ForwardIterator2, 04278 typename _BinaryPredicate> 04279 bool 04280 is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1, 04281 _ForwardIterator2 __first2, _BinaryPredicate __pred) 04282 { 04283 // Efficiently compare identical prefixes: O(N) if sequences 04284 // have the same elements in the same order. 04285 for (; __first1 != __last1; ++__first1, ++__first2) 04286 if (!bool(__pred(*__first1, *__first2))) 04287 break; 04288 04289 if (__first1 == __last1) 04290 return true; 04291 04292 // Establish __last2 assuming equal ranges by iterating over the 04293 // rest of the list. 04294 _ForwardIterator2 __last2 = __first2; 04295 std::advance(__last2, std::distance(__first1, __last1)); 04296 for (_ForwardIterator1 __scan = __first1; __scan != __last1; ++__scan) 04297 { 04298 using std::placeholders::_1; 04299 04300 if (__scan != _GLIBCXX_STD_A::find_if(__first1, __scan, 04301 std::bind(__pred, _1, *__scan))) 04302 continue; // We've seen this one before. 04303 04304 auto __matches = std::count_if(__first2, __last2, 04305 std::bind(__pred, _1, *__scan)); 04306 if (0 == __matches 04307 || std::count_if(__scan, __last1, 04308 std::bind(__pred, _1, *__scan)) != __matches) 04309 return false; 04310 } 04311 return true; 04312 } 04313 04314 #ifdef _GLIBCXX_USE_C99_STDINT_TR1 04315 /** 04316 * @brief Shuffle the elements of a sequence using a uniform random 04317 * number generator. 04318 * @ingroup mutating_algorithms 04319 * @param first A forward iterator. 04320 * @param last A forward iterator. 04321 * @param g A UniformRandomNumberGenerator (26.5.1.3). 04322 * @return Nothing. 04323 * 04324 * Reorders the elements in the range @p [first,last) using @p g to 04325 * provide random numbers. 04326 */ 04327 template<typename _RandomAccessIterator, 04328 typename _UniformRandomNumberGenerator> 04329 void 04330 shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last, 04331 _UniformRandomNumberGenerator&& __g) 04332 { 04333 // concept requirements 04334 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept< 04335 _RandomAccessIterator>) 04336 __glibcxx_requires_valid_range(__first, __last); 04337 04338 if (__first == __last) 04339 return; 04340 04341 typedef typename iterator_traits<_RandomAccessIterator>::difference_type 04342 _DistanceType; 04343 04344 typedef typename std::make_unsigned<_DistanceType>::type __ud_type; 04345 typedef typename std::uniform_int_distribution<__ud_type> __distr_type; 04346 typedef typename __distr_type::param_type __p_type; 04347 __distr_type __d; 04348 04349 for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i) 04350 std::iter_swap(__i, __first + __d(__g, __p_type(0, __i - __first))); 04351 } 04352 #endif 04353 04354 #endif // __GXX_EXPERIMENTAL_CXX0X__ 04355 04356 _GLIBCXX_END_NAMESPACE_VERSION 04357 04358 _GLIBCXX_BEGIN_NAMESPACE_ALGO 04359 04360 /** 04361 * @brief Apply a function to every element of a sequence. 04362 * @ingroup non_mutating_algorithms 04363 * @param first An input iterator. 04364 * @param last An input iterator. 04365 * @param f A unary function object. 04366 * @return @p f (std::move(@p f) in C++0x). 04367 * 04368 * Applies the function object @p f to each element in the range 04369 * @p [first,last). @p f must not modify the order of the sequence. 04370 * If @p f has a return value it is ignored. 04371 */ 04372 template<typename _InputIterator, typename _Function> 04373 _Function 04374 for_each(_InputIterator __first, _InputIterator __last, _Function __f) 04375 { 04376 // concept requirements 04377 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) 04378 __glibcxx_requires_valid_range(__first, __last); 04379 for (; __first != __last; ++__first) 04380 __f(*__first); 04381 return _GLIBCXX_MOVE(__f); 04382 } 04383 04384 /** 04385 * @brief Find the first occurrence of a value in a sequence. 04386 * @ingroup non_mutating_algorithms 04387 * @param first An input iterator. 04388 * @param last An input iterator. 04389 * @param val The value to find. 04390 * @return The first iterator @c i in the range @p [first,last) 04391 * such that @c *i == @p val, or @p last if no such iterator exists. 04392 */ 04393 template<typename _InputIterator, typename _Tp> 04394 inline _InputIterator 04395 find(_InputIterator __first, _InputIterator __last, 04396 const _Tp& __val) 04397 { 04398 // concept requirements 04399 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) 04400 __glibcxx_function_requires(_EqualOpConcept< 04401 typename iterator_traits<_InputIterator>::value_type, _Tp>) 04402 __glibcxx_requires_valid_range(__first, __last); 04403 return std::__find(__first, __last, __val, 04404 std::__iterator_category(__first)); 04405 } 04406 04407 /** 04408 * @brief Find the first element in a sequence for which a 04409 * predicate is true. 04410 * @ingroup non_mutating_algorithms 04411 * @param first An input iterator. 04412 * @param last An input iterator. 04413 * @param pred A predicate. 04414 * @return The first iterator @c i in the range @p [first,last) 04415 * such that @p pred(*i) is true, or @p last if no such iterator exists. 04416 */ 04417 template<typename _InputIterator, typename _Predicate> 04418 inline _InputIterator 04419 find_if(_InputIterator __first, _InputIterator __last, 04420 _Predicate __pred) 04421 { 04422 // concept requirements 04423 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) 04424 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate, 04425 typename iterator_traits<_InputIterator>::value_type>) 04426 __glibcxx_requires_valid_range(__first, __last); 04427 return std::__find_if(__first, __last, __pred, 04428 std::__iterator_category(__first)); 04429 } 04430 04431 /** 04432 * @brief Find element from a set in a sequence. 04433 * @ingroup non_mutating_algorithms 04434 * @param first1 Start of range to search. 04435 * @param last1 End of range to search. 04436 * @param first2 Start of match candidates. 04437 * @param last2 End of match candidates. 04438 * @return The first iterator @c i in the range 04439 * @p [first1,last1) such that @c *i == @p *(i2) such that i2 is an 04440 * iterator in [first2,last2), or @p last1 if no such iterator exists. 04441 * 04442 * Searches the range @p [first1,last1) for an element that is equal to 04443 * some element in the range [first2,last2). If found, returns an iterator 04444 * in the range [first1,last1), otherwise returns @p last1. 04445 */ 04446 template<typename _InputIterator, typename _ForwardIterator> 04447 _InputIterator 04448 find_first_of(_InputIterator __first1, _InputIterator __last1, 04449 _ForwardIterator __first2, _ForwardIterator __last2) 04450 { 04451 // concept requirements 04452 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) 04453 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) 04454 __glibcxx_function_requires(_EqualOpConcept< 04455 typename iterator_traits<_InputIterator>::value_type, 04456 typename iterator_traits<_ForwardIterator>::value_type>) 04457 __glibcxx_requires_valid_range(__first1, __last1); 04458 __glibcxx_requires_valid_range(__first2, __last2); 04459 04460 for (; __first1 != __last1; ++__first1) 04461 for (_ForwardIterator __iter = __first2; __iter != __last2; ++__iter) 04462 if (*__first1 == *__iter) 04463 return __first1; 04464 return __last1; 04465 } 04466 04467 /** 04468 * @brief Find element from a set in a sequence using a predicate. 04469 * @ingroup non_mutating_algorithms 04470 * @param first1 Start of range to search. 04471 * @param last1 End of range to search. 04472 * @param first2 Start of match candidates. 04473 * @param last2 End of match candidates. 04474 * @param comp Predicate to use. 04475 * @return The first iterator @c i in the range 04476 * @p [first1,last1) such that @c comp(*i, @p *(i2)) is true and i2 is an 04477 * iterator in [first2,last2), or @p last1 if no such iterator exists. 04478 * 04479 04480 * Searches the range @p [first1,last1) for an element that is 04481 * equal to some element in the range [first2,last2). If found, 04482 * returns an iterator in the range [first1,last1), otherwise 04483 * returns @p last1. 04484 */ 04485 template<typename _InputIterator, typename _ForwardIterator, 04486 typename _BinaryPredicate> 04487 _InputIterator 04488 find_first_of(_InputIterator __first1, _InputIterator __last1, 04489 _ForwardIterator __first2, _ForwardIterator __last2, 04490 _BinaryPredicate __comp) 04491 { 04492 // concept requirements 04493 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) 04494 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) 04495 __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate, 04496 typename iterator_traits<_InputIterator>::value_type, 04497 typename iterator_traits<_ForwardIterator>::value_type>) 04498 __glibcxx_requires_valid_range(__first1, __last1); 04499 __glibcxx_requires_valid_range(__first2, __last2); 04500 04501 for (; __first1 != __last1; ++__first1) 04502 for (_ForwardIterator __iter = __first2; __iter != __last2; ++__iter) 04503 if (__comp(*__first1, *__iter)) 04504 return __first1; 04505 return __last1; 04506 } 04507 04508 /** 04509 * @brief Find two adjacent values in a sequence that are equal. 04510 * @ingroup non_mutating_algorithms 04511 * @param first A forward iterator. 04512 * @param last A forward iterator. 04513 * @return The first iterator @c i such that @c i and @c i+1 are both 04514 * valid iterators in @p [first,last) and such that @c *i == @c *(i+1), 04515 * or @p last if no such iterator exists. 04516 */ 04517 template<typename _ForwardIterator> 04518 _ForwardIterator 04519 adjacent_find(_ForwardIterator __first, _ForwardIterator __last) 04520 { 04521 // concept requirements 04522 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) 04523 __glibcxx_function_requires(_EqualityComparableConcept< 04524 typename iterator_traits<_ForwardIterator>::value_type>) 04525 __glibcxx_requires_valid_range(__first, __last); 04526 if (__first == __last) 04527 return __last; 04528 _ForwardIterator __next = __first; 04529 while(++__next != __last) 04530 { 04531 if (*__first == *__next) 04532 return __first; 04533 __first = __next; 04534 } 04535 return __last; 04536 } 04537 04538 /** 04539 * @brief Find two adjacent values in a sequence using a predicate. 04540 * @ingroup non_mutating_algorithms 04541 * @param first A forward iterator. 04542 * @param last A forward iterator. 04543 * @param binary_pred A binary predicate. 04544 * @return The first iterator @c i such that @c i and @c i+1 are both 04545 * valid iterators in @p [first,last) and such that 04546 * @p binary_pred(*i,*(i+1)) is true, or @p last if no such iterator 04547 * exists. 04548 */ 04549 template<typename _ForwardIterator, typename _BinaryPredicate> 04550 _ForwardIterator 04551 adjacent_find(_ForwardIterator __first, _ForwardIterator __last, 04552 _BinaryPredicate __binary_pred) 04553 { 04554 // concept requirements 04555 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) 04556 __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate, 04557 typename iterator_traits<_ForwardIterator>::value_type, 04558 typename iterator_traits<_ForwardIterator>::value_type>) 04559 __glibcxx_requires_valid_range(__first, __last); 04560 if (__first == __last) 04561 return __last; 04562 _ForwardIterator __next = __first; 04563 while(++__next != __last) 04564 { 04565 if (__binary_pred(*__first, *__next)) 04566 return __first; 04567 __first = __next; 04568 } 04569 return __last; 04570 } 04571 04572 /** 04573 * @brief Count the number of copies of a value in a sequence. 04574 * @ingroup non_mutating_algorithms 04575 * @param first An input iterator. 04576 * @param last An input iterator. 04577 * @param value The value to be counted. 04578 * @return The number of iterators @c i in the range @p [first,last) 04579 * for which @c *i == @p value 04580 */ 04581 template<typename _InputIterator, typename _Tp> 04582 typename iterator_traits<_InputIterator>::difference_type 04583 count(_InputIterator __first, _InputIterator __last, const _Tp& __value) 04584 { 04585 // concept requirements 04586 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) 04587 __glibcxx_function_requires(_EqualOpConcept< 04588 typename iterator_traits<_InputIterator>::value_type, _Tp>) 04589 __glibcxx_requires_valid_range(__first, __last); 04590 typename iterator_traits<_InputIterator>::difference_type __n = 0; 04591 for (; __first != __last; ++__first) 04592 if (*__first == __value) 04593 ++__n; 04594 return __n; 04595 } 04596 04597 /** 04598 * @brief Count the elements of a sequence for which a predicate is true. 04599 * @ingroup non_mutating_algorithms 04600 * @param first An input iterator. 04601 * @param last An input iterator. 04602 * @param pred A predicate. 04603 * @return The number of iterators @c i in the range @p [first,last) 04604 * for which @p pred(*i) is true. 04605 */ 04606 template<typename _InputIterator, typename _Predicate> 04607 typename iterator_traits<_InputIterator>::difference_type 04608 count_if(_InputIterator __first, _InputIterator __last, _Predicate __pred) 04609 { 04610 // concept requirements 04611 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) 04612 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate, 04613 typename iterator_traits<_InputIterator>::value_type>) 04614 __glibcxx_requires_valid_range(__first, __last); 04615 typename iterator_traits<_InputIterator>::difference_type __n = 0; 04616 for (; __first != __last; ++__first) 04617 if (__pred(*__first)) 04618 ++__n; 04619 return __n; 04620 } 04621 04622 /** 04623 * @brief Search a sequence for a matching sub-sequence. 04624 * @ingroup non_mutating_algorithms 04625 * @param first1 A forward iterator. 04626 * @param last1 A forward iterator. 04627 * @param first2 A forward iterator. 04628 * @param last2 A forward iterator. 04629 * @return The first iterator @c i in the range 04630 * @p [first1,last1-(last2-first2)) such that @c *(i+N) == @p *(first2+N) 04631 * for each @c N in the range @p [0,last2-first2), or @p last1 if no 04632 * such iterator exists. 04633 * 04634 * Searches the range @p [first1,last1) for a sub-sequence that compares 04635 * equal value-by-value with the sequence given by @p [first2,last2) and 04636 * returns an iterator to the first element of the sub-sequence, or 04637 * @p last1 if the sub-sequence is not found. 04638 * 04639 * Because the sub-sequence must lie completely within the range 04640 * @p [first1,last1) it must start at a position less than 04641 * @p last1-(last2-first2) where @p last2-first2 is the length of the 04642 * sub-sequence. 04643 * This means that the returned iterator @c i will be in the range 04644 * @p [first1,last1-(last2-first2)) 04645 */ 04646 template<typename _ForwardIterator1, typename _ForwardIterator2> 04647 _ForwardIterator1 04648 search(_ForwardIterator1 __first1, _ForwardIterator1 __last1, 04649 _ForwardIterator2 __first2, _ForwardIterator2 __last2) 04650 { 04651 // concept requirements 04652 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator1>) 04653 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator2>) 04654 __glibcxx_function_requires(_EqualOpConcept< 04655 typename iterator_traits<_ForwardIterator1>::value_type, 04656 typename iterator_traits<_ForwardIterator2>::value_type>) 04657 __glibcxx_requires_valid_range(__first1, __last1); 04658 __glibcxx_requires_valid_range(__first2, __last2); 04659 04660 // Test for empty ranges 04661 if (__first1 == __last1 || __first2 == __last2) 04662 return __first1; 04663 04664 // Test for a pattern of length 1. 04665 _ForwardIterator2 __p1(__first2); 04666 if (++__p1 == __last2) 04667 return _GLIBCXX_STD_A::find(__first1, __last1, *__first2); 04668 04669 // General case. 04670 _ForwardIterator2 __p; 04671 _ForwardIterator1 __current = __first1; 04672 04673 for (;;) 04674 { 04675 __first1 = _GLIBCXX_STD_A::find(__first1, __last1, *__first2); 04676 if (__first1 == __last1) 04677 return __last1; 04678 04679 __p = __p1; 04680 __current = __first1; 04681 if (++__current == __last1) 04682 return __last1; 04683 04684 while (*__current == *__p) 04685 { 04686 if (++__p == __last2) 04687 return __first1; 04688 if (++__current == __last1) 04689 return __last1; 04690 } 04691 ++__first1; 04692 } 04693 return __first1; 04694 } 04695 04696 /** 04697 * @brief Search a sequence for a matching sub-sequence using a predicate. 04698 * @ingroup non_mutating_algorithms 04699 * @param first1 A forward iterator. 04700 * @param last1 A forward iterator. 04701 * @param first2 A forward iterator. 04702 * @param last2 A forward iterator. 04703 * @param predicate A binary predicate. 04704 * @return The first iterator @c i in the range 04705 * @p [first1,last1-(last2-first2)) such that 04706 * @p predicate(*(i+N),*(first2+N)) is true for each @c N in the range 04707 * @p [0,last2-first2), or @p last1 if no such iterator exists. 04708 * 04709 * Searches the range @p [first1,last1) for a sub-sequence that compares 04710 * equal value-by-value with the sequence given by @p [first2,last2), 04711 * using @p predicate to determine equality, and returns an iterator 04712 * to the first element of the sub-sequence, or @p last1 if no such 04713 * iterator exists. 04714 * 04715 * @see search(_ForwardIter1, _ForwardIter1, _ForwardIter2, _ForwardIter2) 04716 */ 04717 template<typename _ForwardIterator1, typename _ForwardIterator2, 04718 typename _BinaryPredicate> 04719 _ForwardIterator1 04720 search(_ForwardIterator1 __first1, _ForwardIterator1 __last1, 04721 _ForwardIterator2 __first2, _ForwardIterator2 __last2, 04722 _BinaryPredicate __predicate) 04723 { 04724 // concept requirements 04725 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator1>) 04726 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator2>) 04727 __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate, 04728 typename iterator_traits<_ForwardIterator1>::value_type, 04729 typename iterator_traits<_ForwardIterator2>::value_type>) 04730 __glibcxx_requires_valid_range(__first1, __last1); 04731 __glibcxx_requires_valid_range(__first2, __last2); 04732 04733 // Test for empty ranges 04734 if (__first1 == __last1 || __first2 == __last2) 04735 return __first1; 04736 04737 // Test for a pattern of length 1. 04738 _ForwardIterator2 __p1(__first2); 04739 if (++__p1 == __last2) 04740 { 04741 while (__first1 != __last1 04742 && !bool(__predicate(*__first1, *__first2))) 04743 ++__first1; 04744 return __first1; 04745 } 04746 04747 // General case. 04748 _ForwardIterator2 __p; 04749 _ForwardIterator1 __current = __first1; 04750 04751 for (;;) 04752 { 04753 while (__first1 != __last1 04754 && !bool(__predicate(*__first1, *__first2))) 04755 ++__first1; 04756 if (__first1 == __last1) 04757 return __last1; 04758 04759 __p = __p1; 04760 __current = __first1; 04761 if (++__current == __last1) 04762 return __last1; 04763 04764 while (__predicate(*__current, *__p)) 04765 { 04766 if (++__p == __last2) 04767 return __first1; 04768 if (++__current == __last1) 04769 return __last1; 04770 } 04771 ++__first1; 04772 } 04773 return __first1; 04774 } 04775 04776 04777 /** 04778 * @brief Search a sequence for a number of consecutive values. 04779 * @ingroup non_mutating_algorithms 04780 * @param first A forward iterator. 04781 * @param last A forward iterator. 04782 * @param count The number of consecutive values. 04783 * @param val The value to find. 04784 * @return The first iterator @c i in the range @p [first,last-count) 04785 * such that @c *(i+N) == @p val for each @c N in the range @p [0,count), 04786 * or @p last if no such iterator exists. 04787 * 04788 * Searches the range @p [first,last) for @p count consecutive elements 04789 * equal to @p val. 04790 */ 04791 template<typename _ForwardIterator, typename _Integer, typename _Tp> 04792 _ForwardIterator 04793 search_n(_ForwardIterator __first, _ForwardIterator __last, 04794 _Integer __count, const _Tp& __val) 04795 { 04796 // concept requirements 04797 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) 04798 __glibcxx_function_requires(_EqualOpConcept< 04799 typename iterator_traits<_ForwardIterator>::value_type, _Tp>) 04800 __glibcxx_requires_valid_range(__first, __last); 04801 04802 if (__count <= 0) 04803 return __first; 04804 if (__count == 1) 04805 return _GLIBCXX_STD_A::find(__first, __last, __val); 04806 return std::__search_n(__first, __last, __count, __val, 04807 std::__iterator_category(__first)); 04808 } 04809 04810 04811 /** 04812 * @brief Search a sequence for a number of consecutive values using a 04813 * predicate. 04814 * @ingroup non_mutating_algorithms 04815 * @param first A forward iterator. 04816 * @param last A forward iterator. 04817 * @param count The number of consecutive values. 04818 * @param val The value to find. 04819 * @param binary_pred A binary predicate. 04820 * @return The first iterator @c i in the range @p [first,last-count) 04821 * such that @p binary_pred(*(i+N),val) is true for each @c N in the 04822 * range @p [0,count), or @p last if no such iterator exists. 04823 * 04824 * Searches the range @p [first,last) for @p count consecutive elements 04825 * for which the predicate returns true. 04826 */ 04827 template<typename _ForwardIterator, typename _Integer, typename _Tp, 04828 typename _BinaryPredicate> 04829 _ForwardIterator 04830 search_n(_ForwardIterator __first, _ForwardIterator __last, 04831 _Integer __count, const _Tp& __val, 04832 _BinaryPredicate __binary_pred) 04833 { 04834 // concept requirements 04835 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) 04836 __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate, 04837 typename iterator_traits<_ForwardIterator>::value_type, _Tp>) 04838 __glibcxx_requires_valid_range(__first, __last); 04839 04840 if (__count <= 0) 04841 return __first; 04842 if (__count == 1) 04843 { 04844 while (__first != __last && !bool(__binary_pred(*__first, __val))) 04845 ++__first; 04846 return __first; 04847 } 04848 return std::__search_n(__first, __last, __count, __val, __binary_pred, 04849 std::__iterator_category(__first)); 04850 } 04851 04852 04853 /** 04854 * @brief Perform an operation on a sequence. 04855 * @ingroup mutating_algorithms 04856 * @param first An input iterator. 04857 * @param last An input iterator. 04858 * @param result An output iterator. 04859 * @param unary_op A unary operator. 04860 * @return An output iterator equal to @p result+(last-first). 04861 * 04862 * Applies the operator to each element in the input range and assigns 04863 * the results to successive elements of the output sequence. 04864 * Evaluates @p *(result+N)=unary_op(*(first+N)) for each @c N in the 04865 * range @p [0,last-first). 04866 * 04867 * @p unary_op must not alter its argument. 04868 */ 04869 template<typename _InputIterator, typename _OutputIterator, 04870 typename _UnaryOperation> 04871 _OutputIterator 04872 transform(_InputIterator __first, _InputIterator __last, 04873 _OutputIterator __result, _UnaryOperation __unary_op) 04874 { 04875 // concept requirements 04876 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) 04877 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, 04878 // "the type returned by a _UnaryOperation" 04879 __typeof__(__unary_op(*__first))>) 04880 __glibcxx_requires_valid_range(__first, __last); 04881 04882 for (; __first != __last; ++__first, ++__result) 04883 *__result = __unary_op(*__first); 04884 return __result; 04885 } 04886 04887 /** 04888 * @brief Perform an operation on corresponding elements of two sequences. 04889 * @ingroup mutating_algorithms 04890 * @param first1 An input iterator. 04891 * @param last1 An input iterator. 04892 * @param first2 An input iterator. 04893 * @param result An output iterator. 04894 * @param binary_op A binary operator. 04895 * @return An output iterator equal to @p result+(last-first). 04896 * 04897 * Applies the operator to the corresponding elements in the two 04898 * input ranges and assigns the results to successive elements of the 04899 * output sequence. 04900 * Evaluates @p *(result+N)=binary_op(*(first1+N),*(first2+N)) for each 04901 * @c N in the range @p [0,last1-first1). 04902 * 04903 * @p binary_op must not alter either of its arguments. 04904 */ 04905 template<typename _InputIterator1, typename _InputIterator2, 04906 typename _OutputIterator, typename _BinaryOperation> 04907 _OutputIterator 04908 transform(_InputIterator1 __first1, _InputIterator1 __last1, 04909 _InputIterator2 __first2, _OutputIterator __result, 04910 _BinaryOperation __binary_op) 04911 { 04912 // concept requirements 04913 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>) 04914 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>) 04915 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, 04916 // "the type returned by a _BinaryOperation" 04917 __typeof__(__binary_op(*__first1,*__first2))>) 04918 __glibcxx_requires_valid_range(__first1, __last1); 04919 04920 for (; __first1 != __last1; ++__first1, ++__first2, ++__result) 04921 *__result = __binary_op(*__first1, *__first2); 04922 return __result; 04923 } 04924 04925 /** 04926 * @brief Replace each occurrence of one value in a sequence with another 04927 * value. 04928 * @ingroup mutating_algorithms 04929 * @param first A forward iterator. 04930 * @param last A forward iterator. 04931 * @param old_value The value to be replaced. 04932 * @param new_value The replacement value. 04933 * @return replace() returns no value. 04934 * 04935 * For each iterator @c i in the range @p [first,last) if @c *i == 04936 * @p old_value then the assignment @c *i = @p new_value is performed. 04937 */ 04938 template<typename _ForwardIterator, typename _Tp> 04939 void 04940 replace(_ForwardIterator __first, _ForwardIterator __last, 04941 const _Tp& __old_value, const _Tp& __new_value) 04942 { 04943 // concept requirements 04944 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept< 04945 _ForwardIterator>) 04946 __glibcxx_function_requires(_EqualOpConcept< 04947 typename iterator_traits<_ForwardIterator>::value_type, _Tp>) 04948 __glibcxx_function_requires(_ConvertibleConcept<_Tp, 04949 typename iterator_traits<_ForwardIterator>::value_type>) 04950 __glibcxx_requires_valid_range(__first, __last); 04951 04952 for (; __first != __last; ++__first) 04953 if (*__first == __old_value) 04954 *__first = __new_value; 04955 } 04956 04957 /** 04958 * @brief Replace each value in a sequence for which a predicate returns 04959 * true with another value. 04960 * @ingroup mutating_algorithms 04961 * @param first A forward iterator. 04962 * @param last A forward iterator. 04963 * @param pred A predicate. 04964 * @param new_value The replacement value. 04965 * @return replace_if() returns no value. 04966 * 04967 * For each iterator @c i in the range @p [first,last) if @p pred(*i) 04968 * is true then the assignment @c *i = @p new_value is performed. 04969 */ 04970 template<typename _ForwardIterator, typename _Predicate, typename _Tp> 04971 void 04972 replace_if(_ForwardIterator __first, _ForwardIterator __last, 04973 _Predicate __pred, const _Tp& __new_value) 04974 { 04975 // concept requirements 04976 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept< 04977 _ForwardIterator>) 04978 __glibcxx_function_requires(_ConvertibleConcept<_Tp, 04979 typename iterator_traits<_ForwardIterator>::value_type>) 04980 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate, 04981 typename iterator_traits<_ForwardIterator>::value_type>) 04982 __glibcxx_requires_valid_range(__first, __last); 04983 04984 for (; __first != __last; ++__first) 04985 if (__pred(*__first)) 04986 *__first = __new_value; 04987 } 04988 04989 /** 04990 * @brief Assign the result of a function object to each value in a 04991 * sequence. 04992 * @ingroup mutating_algorithms 04993 * @param first A forward iterator. 04994 * @param last A forward iterator. 04995 * @param gen A function object taking no arguments and returning 04996 * std::iterator_traits<_ForwardIterator>::value_type 04997 * @return generate() returns no value. 04998 * 04999 * Performs the assignment @c *i = @p gen() for each @c i in the range 05000 * @p [first,last). 05001 */ 05002 template<typename _ForwardIterator, typename _Generator> 05003 void 05004 generate(_ForwardIterator __first, _ForwardIterator __last, 05005 _Generator __gen) 05006 { 05007 // concept requirements 05008 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) 05009 __glibcxx_function_requires(_GeneratorConcept<_Generator, 05010 typename iterator_traits<_ForwardIterator>::value_type>) 05011 __glibcxx_requires_valid_range(__first, __last); 05012 05013 for (; __first != __last; ++__first) 05014 *__first = __gen(); 05015 } 05016 05017 /** 05018 * @brief Assign the result of a function object to each value in a 05019 * sequence. 05020 * @ingroup mutating_algorithms 05021 * @param first A forward iterator. 05022 * @param n The length of the sequence. 05023 * @param gen A function object taking no arguments and returning 05024 * std::iterator_traits<_ForwardIterator>::value_type 05025 * @return The end of the sequence, @p first+n 05026 * 05027 * Performs the assignment @c *i = @p gen() for each @c i in the range 05028 * @p [first,first+n). 05029 * 05030 * _GLIBCXX_RESOLVE_LIB_DEFECTS 05031 * DR 865. More algorithms that throw away information 05032 */ 05033 template<typename _OutputIterator, typename _Size, typename _Generator> 05034 _OutputIterator 05035 generate_n(_OutputIterator __first, _Size __n, _Generator __gen) 05036 { 05037 // concept requirements 05038 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, 05039 // "the type returned by a _Generator" 05040 __typeof__(__gen())>) 05041 05042 for (__decltype(__n + 0) __niter = __n; 05043 __niter > 0; --__niter, ++__first) 05044 *__first = __gen(); 05045 return __first; 05046 } 05047 05048 05049 /** 05050 * @brief Copy a sequence, removing consecutive duplicate values. 05051 * @ingroup mutating_algorithms 05052 * @param first An input iterator. 05053 * @param last An input iterator. 05054 * @param result An output iterator. 05055 * @return An iterator designating the end of the resulting sequence. 05056 * 05057 * Copies each element in the range @p [first,last) to the range 05058 * beginning at @p result, except that only the first element is copied 05059 * from groups of consecutive elements that compare equal. 05060 * unique_copy() is stable, so the relative order of elements that are 05061 * copied is unchanged. 05062 * 05063 * _GLIBCXX_RESOLVE_LIB_DEFECTS 05064 * DR 241. Does unique_copy() require CopyConstructible and Assignable? 05065 * 05066 * _GLIBCXX_RESOLVE_LIB_DEFECTS 05067 * DR 538. 241 again: Does unique_copy() require CopyConstructible and 05068 * Assignable? 05069 */ 05070 template<typename _InputIterator, typename _OutputIterator> 05071 inline _OutputIterator 05072 unique_copy(_InputIterator __first, _InputIterator __last, 05073 _OutputIterator __result) 05074 { 05075 // concept requirements 05076 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) 05077 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, 05078 typename iterator_traits<_InputIterator>::value_type>) 05079 __glibcxx_function_requires(_EqualityComparableConcept< 05080 typename iterator_traits<_InputIterator>::value_type>) 05081 __glibcxx_requires_valid_range(__first, __last); 05082 05083 if (__first == __last) 05084 return __result; 05085 return std::__unique_copy(__first, __last, __result, 05086 std::__iterator_category(__first), 05087 std::__iterator_category(__result)); 05088 } 05089 05090 /** 05091 * @brief Copy a sequence, removing consecutive values using a predicate. 05092 * @ingroup mutating_algorithms 05093 * @param first An input iterator. 05094 * @param last An input iterator. 05095 * @param result An output iterator. 05096 * @param binary_pred A binary predicate. 05097 * @return An iterator designating the end of the resulting sequence. 05098 * 05099 * Copies each element in the range @p [first,last) to the range 05100 * beginning at @p result, except that only the first element is copied 05101 * from groups of consecutive elements for which @p binary_pred returns 05102 * true. 05103 * unique_copy() is stable, so the relative order of elements that are 05104 * copied is unchanged. 05105 * 05106 * _GLIBCXX_RESOLVE_LIB_DEFECTS 05107 * DR 241. Does unique_copy() require CopyConstructible and Assignable? 05108 */ 05109 template<typename _InputIterator, typename _OutputIterator, 05110 typename _BinaryPredicate> 05111 inline _OutputIterator 05112 unique_copy(_InputIterator __first, _InputIterator __last, 05113 _OutputIterator __result, 05114 _BinaryPredicate __binary_pred) 05115 { 05116 // concept requirements -- predicates checked later 05117 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) 05118 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, 05119 typename iterator_traits<_InputIterator>::value_type>) 05120 __glibcxx_requires_valid_range(__first, __last); 05121 05122 if (__first == __last) 05123 return __result; 05124 return std::__unique_copy(__first, __last, __result, __binary_pred, 05125 std::__iterator_category(__first), 05126 std::__iterator_category(__result)); 05127 } 05128 05129 05130 /** 05131 * @brief Randomly shuffle the elements of a sequence. 05132 * @ingroup mutating_algorithms 05133 * @param first A forward iterator. 05134 * @param last A forward iterator. 05135 * @return Nothing. 05136 * 05137 * Reorder the elements in the range @p [first,last) using a random 05138 * distribution, so that every possible ordering of the sequence is 05139 * equally likely. 05140 */ 05141 template<typename _RandomAccessIterator> 05142 inline void 05143 random_shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last) 05144 { 05145 // concept requirements 05146 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept< 05147 _RandomAccessIterator>) 05148 __glibcxx_requires_valid_range(__first, __last); 05149 05150 if (__first != __last) 05151 for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i) 05152 std::iter_swap(__i, __first + (std::rand() % ((__i - __first) + 1))); 05153 } 05154 05155 /** 05156 * @brief Shuffle the elements of a sequence using a random number 05157 * generator. 05158 * @ingroup mutating_algorithms 05159 * @param first A forward iterator. 05160 * @param last A forward iterator. 05161 * @param rand The RNG functor or function. 05162 * @return Nothing. 05163 * 05164 * Reorders the elements in the range @p [first,last) using @p rand to 05165 * provide a random distribution. Calling @p rand(N) for a positive 05166 * integer @p N should return a randomly chosen integer from the 05167 * range [0,N). 05168 */ 05169 template<typename _RandomAccessIterator, typename _RandomNumberGenerator> 05170 void 05171 random_shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last, 05172 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 05173 _RandomNumberGenerator&& __rand) 05174 #else 05175 _RandomNumberGenerator& __rand) 05176 #endif 05177 { 05178 // concept requirements 05179 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept< 05180 _RandomAccessIterator>) 05181 __glibcxx_requires_valid_range(__first, __last); 05182 05183 if (__first == __last) 05184 return; 05185 for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i) 05186 std::iter_swap(__i, __first + __rand((__i - __first) + 1)); 05187 } 05188 05189 05190 /** 05191 * @brief Move elements for which a predicate is true to the beginning 05192 * of a sequence. 05193 * @ingroup mutating_algorithms 05194 * @param first A forward iterator. 05195 * @param last A forward iterator. 05196 * @param pred A predicate functor. 05197 * @return An iterator @p middle such that @p pred(i) is true for each 05198 * iterator @p i in the range @p [first,middle) and false for each @p i 05199 * in the range @p [middle,last). 05200 * 05201 * @p pred must not modify its operand. @p partition() does not preserve 05202 * the relative ordering of elements in each group, use 05203 * @p stable_partition() if this is needed. 05204 */ 05205 template<typename _ForwardIterator, typename _Predicate> 05206 inline _ForwardIterator 05207 partition(_ForwardIterator __first, _ForwardIterator __last, 05208 _Predicate __pred) 05209 { 05210 // concept requirements 05211 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept< 05212 _ForwardIterator>) 05213 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate, 05214 typename iterator_traits<_ForwardIterator>::value_type>) 05215 __glibcxx_requires_valid_range(__first, __last); 05216 05217 return std::__partition(__first, __last, __pred, 05218 std::__iterator_category(__first)); 05219 } 05220 05221 05222 05223 /** 05224 * @brief Sort the smallest elements of a sequence. 05225 * @ingroup sorting_algorithms 05226 * @param first An iterator. 05227 * @param middle Another iterator. 05228 * @param last Another iterator. 05229 * @return Nothing. 05230 * 05231 * Sorts the smallest @p (middle-first) elements in the range 05232 * @p [first,last) and moves them to the range @p [first,middle). The 05233 * order of the remaining elements in the range @p [middle,last) is 05234 * undefined. 05235 * After the sort if @p i and @j are iterators in the range 05236 * @p [first,middle) such that @i precedes @j and @k is an iterator in 05237 * the range @p [middle,last) then @p *j<*i and @p *k<*i are both false. 05238 */ 05239 template<typename _RandomAccessIterator> 05240 inline void 05241 partial_sort(_RandomAccessIterator __first, 05242 _RandomAccessIterator __middle, 05243 _RandomAccessIterator __last) 05244 { 05245 typedef typename iterator_traits<_RandomAccessIterator>::value_type 05246 _ValueType; 05247 05248 // concept requirements 05249 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept< 05250 _RandomAccessIterator>) 05251 __glibcxx_function_requires(_LessThanComparableConcept<_ValueType>) 05252 __glibcxx_requires_valid_range(__first, __middle); 05253 __glibcxx_requires_valid_range(__middle, __last); 05254 05255 std::__heap_select(__first, __middle, __last); 05256 std::sort_heap(__first, __middle); 05257 } 05258 05259 /** 05260 * @brief Sort the smallest elements of a sequence using a predicate 05261 * for comparison. 05262 * @ingroup sorting_algorithms 05263 * @param first An iterator. 05264 * @param middle Another iterator. 05265 * @param last Another iterator. 05266 * @param comp A comparison functor. 05267 * @return Nothing. 05268 * 05269 * Sorts the smallest @p (middle-first) elements in the range 05270 * @p [first,last) and moves them to the range @p [first,middle). The 05271 * order of the remaining elements in the range @p [middle,last) is 05272 * undefined. 05273 * After the sort if @p i and @j are iterators in the range 05274 * @p [first,middle) such that @i precedes @j and @k is an iterator in 05275 * the range @p [middle,last) then @p *comp(j,*i) and @p comp(*k,*i) 05276 * are both false. 05277 */ 05278 template<typename _RandomAccessIterator, typename _Compare> 05279 inline void 05280 partial_sort(_RandomAccessIterator __first, 05281 _RandomAccessIterator __middle, 05282 _RandomAccessIterator __last, 05283 _Compare __comp) 05284 { 05285 typedef typename iterator_traits<_RandomAccessIterator>::value_type 05286 _ValueType; 05287 05288 // concept requirements 05289 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept< 05290 _RandomAccessIterator>) 05291 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, 05292 _ValueType, _ValueType>) 05293 __glibcxx_requires_valid_range(__first, __middle); 05294 __glibcxx_requires_valid_range(__middle, __last); 05295 05296 std::__heap_select(__first, __middle, __last, __comp); 05297 std::sort_heap(__first, __middle, __comp); 05298 } 05299 05300 /** 05301 * @brief Sort a sequence just enough to find a particular position. 05302 * @ingroup sorting_algorithms 05303 * @param first An iterator. 05304 * @param nth Another iterator. 05305 * @param last Another iterator. 05306 * @return Nothing. 05307 * 05308 * Rearranges the elements in the range @p [first,last) so that @p *nth 05309 * is the same element that would have been in that position had the 05310 * whole sequence been sorted. 05311 * whole sequence been sorted. The elements either side of @p *nth are 05312 * not completely sorted, but for any iterator @i in the range 05313 * @p [first,nth) and any iterator @j in the range @p [nth,last) it 05314 * holds that @p *j<*i is false. 05315 */ 05316 template<typename _RandomAccessIterator> 05317 inline void 05318 nth_element(_RandomAccessIterator __first, _RandomAccessIterator __nth, 05319 _RandomAccessIterator __last) 05320 { 05321 typedef typename iterator_traits<_RandomAccessIterator>::value_type 05322 _ValueType; 05323 05324 // concept requirements 05325 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept< 05326 _RandomAccessIterator>) 05327 __glibcxx_function_requires(_LessThanComparableConcept<_ValueType>) 05328 __glibcxx_requires_valid_range(__first, __nth); 05329 __glibcxx_requires_valid_range(__nth, __last); 05330 05331 if (__first == __last || __nth == __last) 05332 return; 05333 05334 std::__introselect(__first, __nth, __last, 05335 std::__lg(__last - __first) * 2); 05336 } 05337 05338 /** 05339 * @brief Sort a sequence just enough to find a particular position 05340 * using a predicate for comparison. 05341 * @ingroup sorting_algorithms 05342 * @param first An iterator. 05343 * @param nth Another iterator. 05344 * @param last Another iterator. 05345 * @param comp A comparison functor. 05346 * @return Nothing. 05347 * 05348 * Rearranges the elements in the range @p [first,last) so that @p *nth 05349 * is the same element that would have been in that position had the 05350 * whole sequence been sorted. The elements either side of @p *nth are 05351 * not completely sorted, but for any iterator @i in the range 05352 * @p [first,nth) and any iterator @j in the range @p [nth,last) it 05353 * holds that @p comp(*j,*i) is false. 05354 */ 05355 template<typename _RandomAccessIterator, typename _Compare> 05356 inline void 05357 nth_element(_RandomAccessIterator __first, _RandomAccessIterator __nth, 05358 _RandomAccessIterator __last, _Compare __comp) 05359 { 05360 typedef typename iterator_traits<_RandomAccessIterator>::value_type 05361 _ValueType; 05362 05363 // concept requirements 05364 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept< 05365 _RandomAccessIterator>) 05366 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, 05367 _ValueType, _ValueType>) 05368 __glibcxx_requires_valid_range(__first, __nth); 05369 __glibcxx_requires_valid_range(__nth, __last); 05370 05371 if (__first == __last || __nth == __last) 05372 return; 05373 05374 std::__introselect(__first, __nth, __last, 05375 std::__lg(__last - __first) * 2, __comp); 05376 } 05377 05378 05379 /** 05380 * @brief Sort the elements of a sequence. 05381 * @ingroup sorting_algorithms 05382 * @param first An iterator. 05383 * @param last Another iterator. 05384 * @return Nothing. 05385 * 05386 * Sorts the elements in the range @p [first,last) in ascending order, 05387 * such that @p *(i+1)<*i is false for each iterator @p i in the range 05388 * @p [first,last-1). 05389 * 05390 * The relative ordering of equivalent elements is not preserved, use 05391 * @p stable_sort() if this is needed. 05392 */ 05393 template<typename _RandomAccessIterator> 05394 inline void 05395 sort(_RandomAccessIterator __first, _RandomAccessIterator __last) 05396 { 05397 typedef typename iterator_traits<_RandomAccessIterator>::value_type 05398 _ValueType; 05399 05400 // concept requirements 05401 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept< 05402 _RandomAccessIterator>) 05403 __glibcxx_function_requires(_LessThanComparableConcept<_ValueType>) 05404 __glibcxx_requires_valid_range(__first, __last); 05405 05406 if (__first != __last) 05407 { 05408 std::__introsort_loop(__first, __last, 05409 std::__lg(__last - __first) * 2); 05410 std::__final_insertion_sort(__first, __last); 05411 } 05412 } 05413 05414 /** 05415 * @brief Sort the elements of a sequence using a predicate for comparison. 05416 * @ingroup sorting_algorithms 05417 * @param first An iterator. 05418 * @param last Another iterator. 05419 * @param comp A comparison functor. 05420 * @return Nothing. 05421 * 05422 * Sorts the elements in the range @p [first,last) in ascending order, 05423 * such that @p comp(*(i+1),*i) is false for every iterator @p i in the 05424 * range @p [first,last-1). 05425 * 05426 * The relative ordering of equivalent elements is not preserved, use 05427 * @p stable_sort() if this is needed. 05428 */ 05429 template<typename _RandomAccessIterator, typename _Compare> 05430 inline void 05431 sort(_RandomAccessIterator __first, _RandomAccessIterator __last, 05432 _Compare __comp) 05433 { 05434 typedef typename iterator_traits<_RandomAccessIterator>::value_type 05435 _ValueType; 05436 05437 // concept requirements 05438 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept< 05439 _RandomAccessIterator>) 05440 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, _ValueType, 05441 _ValueType>) 05442 __glibcxx_requires_valid_range(__first, __last); 05443 05444 if (__first != __last) 05445 { 05446 std::__introsort_loop(__first, __last, 05447 std::__lg(__last - __first) * 2, __comp); 05448 std::__final_insertion_sort(__first, __last, __comp); 05449 } 05450 } 05451 05452 /** 05453 * @brief Merges two sorted ranges. 05454 * @ingroup sorting_algorithms 05455 * @param first1 An iterator. 05456 * @param first2 Another iterator. 05457 * @param last1 Another iterator. 05458 * @param last2 Another iterator. 05459 * @param result An iterator pointing to the end of the merged range. 05460 * @return An iterator pointing to the first element <em>not less 05461 * than</em> @a val. 05462 * 05463 * Merges the ranges [first1,last1) and [first2,last2) into the sorted range 05464 * [result, result + (last1-first1) + (last2-first2)). Both input ranges 05465 * must be sorted, and the output range must not overlap with either of 05466 * the input ranges. The sort is @e stable, that is, for equivalent 05467 * elements in the two ranges, elements from the first range will always 05468 * come before elements from the second. 05469 */ 05470 template<typename _InputIterator1, typename _InputIterator2, 05471 typename _OutputIterator> 05472 _OutputIterator 05473 merge(_InputIterator1 __first1, _InputIterator1 __last1, 05474 _InputIterator2 __first2, _InputIterator2 __last2, 05475 _OutputIterator __result) 05476 { 05477 typedef typename iterator_traits<_InputIterator1>::value_type 05478 _ValueType1; 05479 typedef typename iterator_traits<_InputIterator2>::value_type 05480 _ValueType2; 05481 05482 // concept requirements 05483 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>) 05484 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>) 05485 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, 05486 _ValueType1>) 05487 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, 05488 _ValueType2>) 05489 __glibcxx_function_requires(_LessThanOpConcept<_ValueType2, _ValueType1>) 05490 __glibcxx_requires_sorted_set(__first1, __last1, __first2); 05491 __glibcxx_requires_sorted_set(__first2, __last2, __first1); 05492 05493 while (__first1 != __last1 && __first2 != __last2) 05494 { 05495 if (*__first2 < *__first1) 05496 { 05497 *__result = *__first2; 05498 ++__first2; 05499 } 05500 else 05501 { 05502 *__result = *__first1; 05503 ++__first1; 05504 } 05505 ++__result; 05506 } 05507 return std::copy(__first2, __last2, std::copy(__first1, __last1, 05508 __result)); 05509 } 05510 05511 /** 05512 * @brief Merges two sorted ranges. 05513 * @ingroup sorting_algorithms 05514 * @param first1 An iterator. 05515 * @param first2 Another iterator. 05516 * @param last1 Another iterator. 05517 * @param last2 Another iterator. 05518 * @param result An iterator pointing to the end of the merged range. 05519 * @param comp A functor to use for comparisons. 05520 * @return An iterator pointing to the first element "not less 05521 * than" @a val. 05522 * 05523 * Merges the ranges [first1,last1) and [first2,last2) into the sorted range 05524 * [result, result + (last1-first1) + (last2-first2)). Both input ranges 05525 * must be sorted, and the output range must not overlap with either of 05526 * the input ranges. The sort is @e stable, that is, for equivalent 05527 * elements in the two ranges, elements from the first range will always 05528 * come before elements from the second. 05529 * 05530 * The comparison function should have the same effects on ordering as 05531 * the function used for the initial sort. 05532 */ 05533 template<typename _InputIterator1, typename _InputIterator2, 05534 typename _OutputIterator, typename _Compare> 05535 _OutputIterator 05536 merge(_InputIterator1 __first1, _InputIterator1 __last1, 05537 _InputIterator2 __first2, _InputIterator2 __last2, 05538 _OutputIterator __result, _Compare __comp) 05539 { 05540 typedef typename iterator_traits<_InputIterator1>::value_type 05541 _ValueType1; 05542 typedef typename iterator_traits<_InputIterator2>::value_type 05543 _ValueType2; 05544 05545 // concept requirements 05546 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>) 05547 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>) 05548 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, 05549 _ValueType1>) 05550 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, 05551 _ValueType2>) 05552 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, 05553 _ValueType2, _ValueType1>) 05554 __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp); 05555 __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp); 05556 05557 while (__first1 != __last1 && __first2 != __last2) 05558 { 05559 if (__comp(*__first2, *__first1)) 05560 { 05561 *__result = *__first2; 05562 ++__first2; 05563 } 05564 else 05565 { 05566 *__result = *__first1; 05567 ++__first1; 05568 } 05569 ++__result; 05570 } 05571 return std::copy(__first2, __last2, std::copy(__first1, __last1, 05572 __result)); 05573 } 05574 05575 05576 /** 05577 * @brief Sort the elements of a sequence, preserving the relative order 05578 * of equivalent elements. 05579 * @ingroup sorting_algorithms 05580 * @param first An iterator. 05581 * @param last Another iterator. 05582 * @return Nothing. 05583 * 05584 * Sorts the elements in the range @p [first,last) in ascending order, 05585 * such that @p *(i+1)<*i is false for each iterator @p i in the range 05586 * @p [first,last-1). 05587 * 05588 * The relative ordering of equivalent elements is preserved, so any two 05589 * elements @p x and @p y in the range @p [first,last) such that 05590 * @p x<y is false and @p y<x is false will have the same relative 05591 * ordering after calling @p stable_sort(). 05592 */ 05593 template<typename _RandomAccessIterator> 05594 inline void 05595 stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last) 05596 { 05597 typedef typename iterator_traits<_RandomAccessIterator>::value_type 05598 _ValueType; 05599 typedef typename iterator_traits<_RandomAccessIterator>::difference_type 05600 _DistanceType; 05601 05602 // concept requirements 05603 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept< 05604 _RandomAccessIterator>) 05605 __glibcxx_function_requires(_LessThanComparableConcept<_ValueType>) 05606 __glibcxx_requires_valid_range(__first, __last); 05607 05608 _Temporary_buffer<_RandomAccessIterator, _ValueType> __buf(__first, 05609 __last); 05610 if (__buf.begin() == 0) 05611 std::__inplace_stable_sort(__first, __last); 05612 else 05613 std::__stable_sort_adaptive(__first, __last, __buf.begin(), 05614 _DistanceType(__buf.size())); 05615 } 05616 05617 /** 05618 * @brief Sort the elements of a sequence using a predicate for comparison, 05619 * preserving the relative order of equivalent elements. 05620 * @ingroup sorting_algorithms 05621 * @param first An iterator. 05622 * @param last Another iterator. 05623 * @param comp A comparison functor. 05624 * @return Nothing. 05625 * 05626 * Sorts the elements in the range @p [first,last) in ascending order, 05627 * such that @p comp(*(i+1),*i) is false for each iterator @p i in the 05628 * range @p [first,last-1). 05629 * 05630 * The relative ordering of equivalent elements is preserved, so any two 05631 * elements @p x and @p y in the range @p [first,last) such that 05632 * @p comp(x,y) is false and @p comp(y,x) is false will have the same 05633 * relative ordering after calling @p stable_sort(). 05634 */ 05635 template<typename _RandomAccessIterator, typename _Compare> 05636 inline void 05637 stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last, 05638 _Compare __comp) 05639 { 05640 typedef typename iterator_traits<_RandomAccessIterator>::value_type 05641 _ValueType; 05642 typedef typename iterator_traits<_RandomAccessIterator>::difference_type 05643 _DistanceType; 05644 05645 // concept requirements 05646 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept< 05647 _RandomAccessIterator>) 05648 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, 05649 _ValueType, 05650 _ValueType>) 05651 __glibcxx_requires_valid_range(__first, __last); 05652 05653 _Temporary_buffer<_RandomAccessIterator, _ValueType> __buf(__first, 05654 __last); 05655 if (__buf.begin() == 0) 05656 std::__inplace_stable_sort(__first, __last, __comp); 05657 else 05658 std::__stable_sort_adaptive(__first, __last, __buf.begin(), 05659 _DistanceType(__buf.size()), __comp); 05660 } 05661 05662 05663 /** 05664 * @brief Return the union of two sorted ranges. 05665 * @ingroup set_algorithms 05666 * @param first1 Start of first range. 05667 * @param last1 End of first range. 05668 * @param first2 Start of second range. 05669 * @param last2 End of second range. 05670 * @return End of the output range. 05671 * @ingroup set_algorithms 05672 * 05673 * This operation iterates over both ranges, copying elements present in 05674 * each range in order to the output range. Iterators increment for each 05675 * range. When the current element of one range is less than the other, 05676 * that element is copied and the iterator advanced. If an element is 05677 * contained in both ranges, the element from the first range is copied and 05678 * both ranges advance. The output range may not overlap either input 05679 * range. 05680 */ 05681 template<typename _InputIterator1, typename _InputIterator2, 05682 typename _OutputIterator> 05683 _OutputIterator 05684 set_union(_InputIterator1 __first1, _InputIterator1 __last1, 05685 _InputIterator2 __first2, _InputIterator2 __last2, 05686 _OutputIterator __result) 05687 { 05688 typedef typename iterator_traits<_InputIterator1>::value_type 05689 _ValueType1; 05690 typedef typename iterator_traits<_InputIterator2>::value_type 05691 _ValueType2; 05692 05693 // concept requirements 05694 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>) 05695 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>) 05696 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, 05697 _ValueType1>) 05698 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, 05699 _ValueType2>) 05700 __glibcxx_function_requires(_LessThanOpConcept<_ValueType1, _ValueType2>) 05701 __glibcxx_function_requires(_LessThanOpConcept<_ValueType2, _ValueType1>) 05702 __glibcxx_requires_sorted_set(__first1, __last1, __first2); 05703 __glibcxx_requires_sorted_set(__first2, __last2, __first1); 05704 05705 while (__first1 != __last1 && __first2 != __last2) 05706 { 05707 if (*__first1 < *__first2) 05708 { 05709 *__result = *__first1; 05710 ++__first1; 05711 } 05712 else if (*__first2 < *__first1) 05713 { 05714 *__result = *__first2; 05715 ++__first2; 05716 } 05717 else 05718 { 05719 *__result = *__first1; 05720 ++__first1; 05721 ++__first2; 05722 } 05723 ++__result; 05724 } 05725 return std::copy(__first2, __last2, std::copy(__first1, __last1, 05726 __result)); 05727 } 05728 05729 /** 05730 * @brief Return the union of two sorted ranges using a comparison functor. 05731 * @ingroup set_algorithms 05732 * @param first1 Start of first range. 05733 * @param last1 End of first range. 05734 * @param first2 Start of second range. 05735 * @param last2 End of second range. 05736 * @param comp The comparison functor. 05737 * @return End of the output range. 05738 * @ingroup set_algorithms 05739 * 05740 * This operation iterates over both ranges, copying elements present in 05741 * each range in order to the output range. Iterators increment for each 05742 * range. When the current element of one range is less than the other 05743 * according to @a comp, that element is copied and the iterator advanced. 05744 * If an equivalent element according to @a comp is contained in both 05745 * ranges, the element from the first range is copied and both ranges 05746 * advance. The output range may not overlap either input range. 05747 */ 05748 template<typename _InputIterator1, typename _InputIterator2, 05749 typename _OutputIterator, typename _Compare> 05750 _OutputIterator 05751 set_union(_InputIterator1 __first1, _InputIterator1 __last1, 05752 _InputIterator2 __first2, _InputIterator2 __last2, 05753 _OutputIterator __result, _Compare __comp) 05754 { 05755 typedef typename iterator_traits<_InputIterator1>::value_type 05756 _ValueType1; 05757 typedef typename iterator_traits<_InputIterator2>::value_type 05758 _ValueType2; 05759 05760 // concept requirements 05761 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>) 05762 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>) 05763 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, 05764 _ValueType1>) 05765 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, 05766 _ValueType2>) 05767 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, 05768 _ValueType1, _ValueType2>) 05769 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, 05770 _ValueType2, _ValueType1>) 05771 __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp); 05772 __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp); 05773 05774 while (__first1 != __last1 && __first2 != __last2) 05775 { 05776 if (__comp(*__first1, *__first2)) 05777 { 05778 *__result = *__first1; 05779 ++__first1; 05780 } 05781 else if (__comp(*__first2, *__first1)) 05782 { 05783 *__result = *__first2; 05784 ++__first2; 05785 } 05786 else 05787 { 05788 *__result = *__first1; 05789 ++__first1; 05790 ++__first2; 05791 } 05792 ++__result; 05793 } 05794 return std::copy(__first2, __last2, std::copy(__first1, __last1, 05795 __result)); 05796 } 05797 05798 /** 05799 * @brief Return the intersection of two sorted ranges. 05800 * @ingroup set_algorithms 05801 * @param first1 Start of first range. 05802 * @param last1 End of first range. 05803 * @param first2 Start of second range. 05804 * @param last2 End of second range. 05805 * @return End of the output range. 05806 * @ingroup set_algorithms 05807 * 05808 * This operation iterates over both ranges, copying elements present in 05809 * both ranges in order to the output range. Iterators increment for each 05810 * range. When the current element of one range is less than the other, 05811 * that iterator advances. If an element is contained in both ranges, the 05812 * element from the first range is copied and both ranges advance. The 05813 * output range may not overlap either input range. 05814 */ 05815 template<typename _InputIterator1, typename _InputIterator2, 05816 typename _OutputIterator> 05817 _OutputIterator 05818 set_intersection(_InputIterator1 __first1, _InputIterator1 __last1, 05819 _InputIterator2 __first2, _InputIterator2 __last2, 05820 _OutputIterator __result) 05821 { 05822 typedef typename iterator_traits<_InputIterator1>::value_type 05823 _ValueType1; 05824 typedef typename iterator_traits<_InputIterator2>::value_type 05825 _ValueType2; 05826 05827 // concept requirements 05828 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>) 05829 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>) 05830 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, 05831 _ValueType1>) 05832 __glibcxx_function_requires(_LessThanOpConcept<_ValueType1, _ValueType2>) 05833 __glibcxx_function_requires(_LessThanOpConcept<_ValueType2, _ValueType1>) 05834 __glibcxx_requires_sorted_set(__first1, __last1, __first2); 05835 __glibcxx_requires_sorted_set(__first2, __last2, __first1); 05836 05837 while (__first1 != __last1 && __first2 != __last2) 05838 if (*__first1 < *__first2) 05839 ++__first1; 05840 else if (*__first2 < *__first1) 05841 ++__first2; 05842 else 05843 { 05844 *__result = *__first1; 05845 ++__first1; 05846 ++__first2; 05847 ++__result; 05848 } 05849 return __result; 05850 } 05851 05852 /** 05853 * @brief Return the intersection of two sorted ranges using comparison 05854 * functor. 05855 * @ingroup set_algorithms 05856 * @param first1 Start of first range. 05857 * @param last1 End of first range. 05858 * @param first2 Start of second range. 05859 * @param last2 End of second range. 05860 * @param comp The comparison functor. 05861 * @return End of the output range. 05862 * @ingroup set_algorithms 05863 * 05864 * This operation iterates over both ranges, copying elements present in 05865 * both ranges in order to the output range. Iterators increment for each 05866 * range. When the current element of one range is less than the other 05867 * according to @a comp, that iterator advances. If an element is 05868 * contained in both ranges according to @a comp, the element from the 05869 * first range is copied and both ranges advance. The output range may not 05870 * overlap either input range. 05871 */ 05872 template<typename _InputIterator1, typename _InputIterator2, 05873 typename _OutputIterator, typename _Compare> 05874 _OutputIterator 05875 set_intersection(_InputIterator1 __first1, _InputIterator1 __last1, 05876 _InputIterator2 __first2, _InputIterator2 __last2, 05877 _OutputIterator __result, _Compare __comp) 05878 { 05879 typedef typename iterator_traits<_InputIterator1>::value_type 05880 _ValueType1; 05881 typedef typename iterator_traits<_InputIterator2>::value_type 05882 _ValueType2; 05883 05884 // concept requirements 05885 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>) 05886 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>) 05887 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, 05888 _ValueType1>) 05889 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, 05890 _ValueType1, _ValueType2>) 05891 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, 05892 _ValueType2, _ValueType1>) 05893 __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp); 05894 __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp); 05895 05896 while (__first1 != __last1 && __first2 != __last2) 05897 if (__comp(*__first1, *__first2)) 05898 ++__first1; 05899 else if (__comp(*__first2, *__first1)) 05900 ++__first2; 05901 else 05902 { 05903 *__result = *__first1; 05904 ++__first1; 05905 ++__first2; 05906 ++__result; 05907 } 05908 return __result; 05909 } 05910 05911 /** 05912 * @brief Return the difference of two sorted ranges. 05913 * @ingroup set_algorithms 05914 * @param first1 Start of first range. 05915 * @param last1 End of first range. 05916 * @param first2 Start of second range. 05917 * @param last2 End of second range. 05918 * @return End of the output range. 05919 * @ingroup set_algorithms 05920 * 05921 * This operation iterates over both ranges, copying elements present in 05922 * the first range but not the second in order to the output range. 05923 * Iterators increment for each range. When the current element of the 05924 * first range is less than the second, that element is copied and the 05925 * iterator advances. If the current element of the second range is less, 05926 * the iterator advances, but no element is copied. If an element is 05927 * contained in both ranges, no elements are copied and both ranges 05928 * advance. The output range may not overlap either input range. 05929 */ 05930 template<typename _InputIterator1, typename _InputIterator2, 05931 typename _OutputIterator> 05932 _OutputIterator 05933 set_difference(_InputIterator1 __first1, _InputIterator1 __last1, 05934 _InputIterator2 __first2, _InputIterator2 __last2, 05935 _OutputIterator __result) 05936 { 05937 typedef typename iterator_traits<_InputIterator1>::value_type 05938 _ValueType1; 05939 typedef typename iterator_traits<_InputIterator2>::value_type 05940 _ValueType2; 05941 05942 // concept requirements 05943 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>) 05944 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>) 05945 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, 05946 _ValueType1>) 05947 __glibcxx_function_requires(_LessThanOpConcept<_ValueType1, _ValueType2>) 05948 __glibcxx_function_requires(_LessThanOpConcept<_ValueType2, _ValueType1>) 05949 __glibcxx_requires_sorted_set(__first1, __last1, __first2); 05950 __glibcxx_requires_sorted_set(__first2, __last2, __first1); 05951 05952 while (__first1 != __last1 && __first2 != __last2) 05953 if (*__first1 < *__first2) 05954 { 05955 *__result = *__first1; 05956 ++__first1; 05957 ++__result; 05958 } 05959 else if (*__first2 < *__first1) 05960 ++__first2; 05961 else 05962 { 05963 ++__first1; 05964 ++__first2; 05965 } 05966 return std::copy(__first1, __last1, __result); 05967 } 05968 05969 /** 05970 * @brief Return the difference of two sorted ranges using comparison 05971 * functor. 05972 * @ingroup set_algorithms 05973 * @param first1 Start of first range. 05974 * @param last1 End of first range. 05975 * @param first2 Start of second range. 05976 * @param last2 End of second range. 05977 * @param comp The comparison functor. 05978 * @return End of the output range. 05979 * @ingroup set_algorithms 05980 * 05981 * This operation iterates over both ranges, copying elements present in 05982 * the first range but not the second in order to the output range. 05983 * Iterators increment for each range. When the current element of the 05984 * first range is less than the second according to @a comp, that element 05985 * is copied and the iterator advances. If the current element of the 05986 * second range is less, no element is copied and the iterator advances. 05987 * If an element is contained in both ranges according to @a comp, no 05988 * elements are copied and both ranges advance. The output range may not 05989 * overlap either input range. 05990 */ 05991 template<typename _InputIterator1, typename _InputIterator2, 05992 typename _OutputIterator, typename _Compare> 05993 _OutputIterator 05994 set_difference(_InputIterator1 __first1, _InputIterator1 __last1, 05995 _InputIterator2 __first2, _InputIterator2 __last2, 05996 _OutputIterator __result, _Compare __comp) 05997 { 05998 typedef typename iterator_traits<_InputIterator1>::value_type 05999 _ValueType1; 06000 typedef typename iterator_traits<_InputIterator2>::value_type 06001 _ValueType2; 06002 06003 // concept requirements 06004 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>) 06005 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>) 06006 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, 06007 _ValueType1>) 06008 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, 06009 _ValueType1, _ValueType2>) 06010 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, 06011 _ValueType2, _ValueType1>) 06012 __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp); 06013 __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp); 06014 06015 while (__first1 != __last1 && __first2 != __last2) 06016 if (__comp(*__first1, *__first2)) 06017 { 06018 *__result = *__first1; 06019 ++__first1; 06020 ++__result; 06021 } 06022 else if (__comp(*__first2, *__first1)) 06023 ++__first2; 06024 else 06025 { 06026 ++__first1; 06027 ++__first2; 06028 } 06029 return std::copy(__first1, __last1, __result); 06030 } 06031 06032 /** 06033 * @brief Return the symmetric difference of two sorted ranges. 06034 * @ingroup set_algorithms 06035 * @param first1 Start of first range. 06036 * @param last1 End of first range. 06037 * @param first2 Start of second range. 06038 * @param last2 End of second range. 06039 * @return End of the output range. 06040 * @ingroup set_algorithms 06041 * 06042 * This operation iterates over both ranges, copying elements present in 06043 * one range but not the other in order to the output range. Iterators 06044 * increment for each range. When the current element of one range is less 06045 * than the other, that element is copied and the iterator advances. If an 06046 * element is contained in both ranges, no elements are copied and both 06047 * ranges advance. The output range may not overlap either input range. 06048 */ 06049 template<typename _InputIterator1, typename _InputIterator2, 06050 typename _OutputIterator> 06051 _OutputIterator 06052 set_symmetric_difference(_InputIterator1 __first1, _InputIterator1 __last1, 06053 _InputIterator2 __first2, _InputIterator2 __last2, 06054 _OutputIterator __result) 06055 { 06056 typedef typename iterator_traits<_InputIterator1>::value_type 06057 _ValueType1; 06058 typedef typename iterator_traits<_InputIterator2>::value_type 06059 _ValueType2; 06060 06061 // concept requirements 06062 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>) 06063 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>) 06064 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, 06065 _ValueType1>) 06066 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, 06067 _ValueType2>) 06068 __glibcxx_function_requires(_LessThanOpConcept<_ValueType1, _ValueType2>) 06069 __glibcxx_function_requires(_LessThanOpConcept<_ValueType2, _ValueType1>) 06070 __glibcxx_requires_sorted_set(__first1, __last1, __first2); 06071 __glibcxx_requires_sorted_set(__first2, __last2, __first1); 06072 06073 while (__first1 != __last1 && __first2 != __last2) 06074 if (*__first1 < *__first2) 06075 { 06076 *__result = *__first1; 06077 ++__first1; 06078 ++__result; 06079 } 06080 else if (*__first2 < *__first1) 06081 { 06082 *__result = *__first2; 06083 ++__first2; 06084 ++__result; 06085 } 06086 else 06087 { 06088 ++__first1; 06089 ++__first2; 06090 } 06091 return std::copy(__first2, __last2, std::copy(__first1, 06092 __last1, __result)); 06093 } 06094 06095 /** 06096 * @brief Return the symmetric difference of two sorted ranges using 06097 * comparison functor. 06098 * @ingroup set_algorithms 06099 * @param first1 Start of first range. 06100 * @param last1 End of first range. 06101 * @param first2 Start of second range. 06102 * @param last2 End of second range. 06103 * @param comp The comparison functor. 06104 * @return End of the output range. 06105 * @ingroup set_algorithms 06106 * 06107 * This operation iterates over both ranges, copying elements present in 06108 * one range but not the other in order to the output range. Iterators 06109 * increment for each range. When the current element of one range is less 06110 * than the other according to @a comp, that element is copied and the 06111 * iterator advances. If an element is contained in both ranges according 06112 * to @a comp, no elements are copied and both ranges advance. The output 06113 * range may not overlap either input range. 06114 */ 06115 template<typename _InputIterator1, typename _InputIterator2, 06116 typename _OutputIterator, typename _Compare> 06117 _OutputIterator 06118 set_symmetric_difference(_InputIterator1 __first1, _InputIterator1 __last1, 06119 _InputIterator2 __first2, _InputIterator2 __last2, 06120 _OutputIterator __result, 06121 _Compare __comp) 06122 { 06123 typedef typename iterator_traits<_InputIterator1>::value_type 06124 _ValueType1; 06125 typedef typename iterator_traits<_InputIterator2>::value_type 06126 _ValueType2; 06127 06128 // concept requirements 06129 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>) 06130 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>) 06131 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, 06132 _ValueType1>) 06133 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, 06134 _ValueType2>) 06135 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, 06136 _ValueType1, _ValueType2>) 06137 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, 06138 _ValueType2, _ValueType1>) 06139 __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp); 06140 __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp); 06141 06142 while (__first1 != __last1 && __first2 != __last2) 06143 if (__comp(*__first1, *__first2)) 06144 { 06145 *__result = *__first1; 06146 ++__first1; 06147 ++__result; 06148 } 06149 else if (__comp(*__first2, *__first1)) 06150 { 06151 *__result = *__first2; 06152 ++__first2; 06153 ++__result; 06154 } 06155 else 06156 { 06157 ++__first1; 06158 ++__first2; 06159 } 06160 return std::copy(__first2, __last2, 06161 std::copy(__first1, __last1, __result)); 06162 } 06163 06164 06165 /** 06166 * @brief Return the minimum element in a range. 06167 * @ingroup sorting_algorithms 06168 * @param first Start of range. 06169 * @param last End of range. 06170 * @return Iterator referencing the first instance of the smallest value. 06171 */ 06172 template<typename _ForwardIterator> 06173 _ForwardIterator 06174 min_element(_ForwardIterator __first, _ForwardIterator __last) 06175 { 06176 // concept requirements 06177 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) 06178 __glibcxx_function_requires(_LessThanComparableConcept< 06179 typename iterator_traits<_ForwardIterator>::value_type>) 06180 __glibcxx_requires_valid_range(__first, __last); 06181 06182 if (__first == __last) 06183 return __first; 06184 _ForwardIterator __result = __first; 06185 while (++__first != __last) 06186 if (*__first < *__result) 06187 __result = __first; 06188 return __result; 06189 } 06190 06191 /** 06192 * @brief Return the minimum element in a range using comparison functor. 06193 * @ingroup sorting_algorithms 06194 * @param first Start of range. 06195 * @param last End of range. 06196 * @param comp Comparison functor. 06197 * @return Iterator referencing the first instance of the smallest value 06198 * according to comp. 06199 */ 06200 template<typename _ForwardIterator, typename _Compare> 06201 _ForwardIterator 06202 min_element(_ForwardIterator __first, _ForwardIterator __last, 06203 _Compare __comp) 06204 { 06205 // concept requirements 06206 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) 06207 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, 06208 typename iterator_traits<_ForwardIterator>::value_type, 06209 typename iterator_traits<_ForwardIterator>::value_type>) 06210 __glibcxx_requires_valid_range(__first, __last); 06211 06212 if (__first == __last) 06213 return __first; 06214 _ForwardIterator __result = __first; 06215 while (++__first != __last) 06216 if (__comp(*__first, *__result)) 06217 __result = __first; 06218 return __result; 06219 } 06220 06221 /** 06222 * @brief Return the maximum element in a range. 06223 * @ingroup sorting_algorithms 06224 * @param first Start of range. 06225 * @param last End of range. 06226 * @return Iterator referencing the first instance of the largest value. 06227 */ 06228 template<typename _ForwardIterator> 06229 _ForwardIterator 06230 max_element(_ForwardIterator __first, _ForwardIterator __last) 06231 { 06232 // concept requirements 06233 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) 06234 __glibcxx_function_requires(_LessThanComparableConcept< 06235 typename iterator_traits<_ForwardIterator>::value_type>) 06236 __glibcxx_requires_valid_range(__first, __last); 06237 06238 if (__first == __last) 06239 return __first; 06240 _ForwardIterator __result = __first; 06241 while (++__first != __last) 06242 if (*__result < *__first) 06243 __result = __first; 06244 return __result; 06245 } 06246 06247 /** 06248 * @brief Return the maximum element in a range using comparison functor. 06249 * @ingroup sorting_algorithms 06250 * @param first Start of range. 06251 * @param last End of range. 06252 * @param comp Comparison functor. 06253 * @return Iterator referencing the first instance of the largest value 06254 * according to comp. 06255 */ 06256 template<typename _ForwardIterator, typename _Compare> 06257 _ForwardIterator 06258 max_element(_ForwardIterator __first, _ForwardIterator __last, 06259 _Compare __comp) 06260 { 06261 // concept requirements 06262 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) 06263 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, 06264 typename iterator_traits<_ForwardIterator>::value_type, 06265 typename iterator_traits<_ForwardIterator>::value_type>) 06266 __glibcxx_requires_valid_range(__first, __last); 06267 06268 if (__first == __last) return __first; 06269 _ForwardIterator __result = __first; 06270 while (++__first != __last) 06271 if (__comp(*__result, *__first)) 06272 __result = __first; 06273 return __result; 06274 } 06275 06276 _GLIBCXX_END_NAMESPACE_ALGO 06277 } // namespace std 06278 06279 #endif /* _STL_ALGO_H */