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