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