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