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