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