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