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