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; ++__first1, ++__first2) 03599 if (!__pred(__first1, __first2)) 03600 break; 03601 03602 if (__ra_iters) 03603 { 03604 if (__first1 == __last1) 03605 return true; 03606 } 03607 else 03608 { 03609 auto __d1 = std::distance(__first1, __last1); 03610 auto __d2 = std::distance(__first2, __last2); 03611 if (__d1 == 0 && __d2 == 0) 03612 return true; 03613 if (__d1 != __d2) 03614 return false; 03615 } 03616 03617 for (_ForwardIterator1 __scan = __first1; __scan != __last1; ++__scan) 03618 { 03619 if (__scan != std::__find_if(__first1, __scan, 03620 __gnu_cxx::__ops::__iter_comp_iter(__pred, __scan))) 03621 continue; // We've seen this one before. 03622 03623 auto __matches = std::__count_if(__first2, __last2, 03624 __gnu_cxx::__ops::__iter_comp_iter(__pred, __scan)); 03625 if (0 == __matches 03626 || std::__count_if(__scan, __last1, 03627 __gnu_cxx::__ops::__iter_comp_iter(__pred, __scan)) 03628 != __matches) 03629 return false; 03630 } 03631 return true; 03632 } 03633 03634 /** 03635 * @brief Checks whether a permutaion of the second sequence is equal 03636 * to the first sequence. 03637 * @ingroup non_mutating_algorithms 03638 * @param __first1 Start of first range. 03639 * @param __last1 End of first range. 03640 * @param __first2 Start of second range. 03641 * @param __last2 End of first range. 03642 * @return true if there exists a permutation of the elements in the range 03643 * [__first2, __last2), beginning with ForwardIterator2 begin, 03644 * such that equal(__first1, __last1, begin) returns true; 03645 * otherwise, returns false. 03646 */ 03647 template<typename _ForwardIterator1, typename _ForwardIterator2> 03648 inline bool 03649 is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1, 03650 _ForwardIterator2 __first2, _ForwardIterator2 __last2) 03651 { 03652 __glibcxx_requires_valid_range(__first1, __last1); 03653 __glibcxx_requires_valid_range(__first2, __last2); 03654 03655 return 03656 std::__is_permutation(__first1, __last1, __first2, __last2, 03657 __gnu_cxx::__ops::__iter_equal_to_iter()); 03658 } 03659 03660 /** 03661 * @brief Checks whether a permutation of the second sequence is equal 03662 * to the first sequence. 03663 * @ingroup non_mutating_algorithms 03664 * @param __first1 Start of first range. 03665 * @param __last1 End of first range. 03666 * @param __first2 Start of second range. 03667 * @param __last2 End of first range. 03668 * @param __pred A binary predicate. 03669 * @return true if there exists a permutation of the elements in the range 03670 * [__first2, __last2), beginning with ForwardIterator2 begin, 03671 * such that equal(__first1, __last1, __begin, __pred) returns true; 03672 * otherwise, returns false. 03673 */ 03674 template<typename _ForwardIterator1, typename _ForwardIterator2, 03675 typename _BinaryPredicate> 03676 inline bool 03677 is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1, 03678 _ForwardIterator2 __first2, _ForwardIterator2 __last2, 03679 _BinaryPredicate __pred) 03680 { 03681 __glibcxx_requires_valid_range(__first1, __last1); 03682 __glibcxx_requires_valid_range(__first2, __last2); 03683 03684 return std::__is_permutation(__first1, __last1, __first2, __last2, 03685 __gnu_cxx::__ops::__iter_comp_iter(__pred)); 03686 } 03687 #endif 03688 03689 #ifdef _GLIBCXX_USE_C99_STDINT_TR1 03690 /** 03691 * @brief Shuffle the elements of a sequence using a uniform random 03692 * number generator. 03693 * @ingroup mutating_algorithms 03694 * @param __first A forward iterator. 03695 * @param __last A forward iterator. 03696 * @param __g A UniformRandomNumberGenerator (26.5.1.3). 03697 * @return Nothing. 03698 * 03699 * Reorders the elements in the range @p [__first,__last) using @p __g to 03700 * provide random numbers. 03701 */ 03702 template<typename _RandomAccessIterator, 03703 typename _UniformRandomNumberGenerator> 03704 void 03705 shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last, 03706 _UniformRandomNumberGenerator&& __g) 03707 { 03708 // concept requirements 03709 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept< 03710 _RandomAccessIterator>) 03711 __glibcxx_requires_valid_range(__first, __last); 03712 03713 if (__first == __last) 03714 return; 03715 03716 typedef typename iterator_traits<_RandomAccessIterator>::difference_type 03717 _DistanceType; 03718 03719 typedef typename std::make_unsigned<_DistanceType>::type __ud_type; 03720 typedef typename std::uniform_int_distribution<__ud_type> __distr_type; 03721 typedef typename __distr_type::param_type __p_type; 03722 __distr_type __d; 03723 03724 for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i) 03725 std::iter_swap(__i, __first + __d(__g, __p_type(0, __i - __first))); 03726 } 03727 #endif 03728 03729 #endif // C++11 03730 03731 _GLIBCXX_END_NAMESPACE_VERSION 03732 03733 _GLIBCXX_BEGIN_NAMESPACE_ALGO 03734 03735 /** 03736 * @brief Apply a function to every element of a sequence. 03737 * @ingroup non_mutating_algorithms 03738 * @param __first An input iterator. 03739 * @param __last An input iterator. 03740 * @param __f A unary function object. 03741 * @return @p __f (std::move(@p __f) in C++0x). 03742 * 03743 * Applies the function object @p __f to each element in the range 03744 * @p [first,last). @p __f must not modify the order of the sequence. 03745 * If @p __f has a return value it is ignored. 03746 */ 03747 template<typename _InputIterator, typename _Function> 03748 _Function 03749 for_each(_InputIterator __first, _InputIterator __last, _Function __f) 03750 { 03751 // concept requirements 03752 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) 03753 __glibcxx_requires_valid_range(__first, __last); 03754 for (; __first != __last; ++__first) 03755 __f(*__first); 03756 return _GLIBCXX_MOVE(__f); 03757 } 03758 03759 /** 03760 * @brief Find the first occurrence of a value in a sequence. 03761 * @ingroup non_mutating_algorithms 03762 * @param __first An input iterator. 03763 * @param __last An input iterator. 03764 * @param __val The value to find. 03765 * @return The first iterator @c i in the range @p [__first,__last) 03766 * such that @c *i == @p __val, or @p __last if no such iterator exists. 03767 */ 03768 template<typename _InputIterator, typename _Tp> 03769 inline _InputIterator 03770 find(_InputIterator __first, _InputIterator __last, 03771 const _Tp& __val) 03772 { 03773 // concept requirements 03774 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) 03775 __glibcxx_function_requires(_EqualOpConcept< 03776 typename iterator_traits<_InputIterator>::value_type, _Tp>) 03777 __glibcxx_requires_valid_range(__first, __last); 03778 return std::__find_if(__first, __last, 03779 __gnu_cxx::__ops::__iter_equals_val(__val)); 03780 } 03781 03782 /** 03783 * @brief Find the first element in a sequence for which a 03784 * predicate is true. 03785 * @ingroup non_mutating_algorithms 03786 * @param __first An input iterator. 03787 * @param __last An input iterator. 03788 * @param __pred A predicate. 03789 * @return The first iterator @c i in the range @p [__first,__last) 03790 * such that @p __pred(*i) is true, or @p __last if no such iterator exists. 03791 */ 03792 template<typename _InputIterator, typename _Predicate> 03793 inline _InputIterator 03794 find_if(_InputIterator __first, _InputIterator __last, 03795 _Predicate __pred) 03796 { 03797 // concept requirements 03798 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) 03799 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate, 03800 typename iterator_traits<_InputIterator>::value_type>) 03801 __glibcxx_requires_valid_range(__first, __last); 03802 03803 return std::__find_if(__first, __last, 03804 __gnu_cxx::__ops::__pred_iter(__pred)); 03805 } 03806 03807 /** 03808 * @brief Find element from a set in a sequence. 03809 * @ingroup non_mutating_algorithms 03810 * @param __first1 Start of range to search. 03811 * @param __last1 End of range to search. 03812 * @param __first2 Start of match candidates. 03813 * @param __last2 End of match candidates. 03814 * @return The first iterator @c i in the range 03815 * @p [__first1,__last1) such that @c *i == @p *(i2) such that i2 is an 03816 * iterator in [__first2,__last2), or @p __last1 if no such iterator exists. 03817 * 03818 * Searches the range @p [__first1,__last1) for an element that is 03819 * equal to some element in the range [__first2,__last2). If 03820 * found, returns an iterator in the range [__first1,__last1), 03821 * otherwise returns @p __last1. 03822 */ 03823 template<typename _InputIterator, typename _ForwardIterator> 03824 _InputIterator 03825 find_first_of(_InputIterator __first1, _InputIterator __last1, 03826 _ForwardIterator __first2, _ForwardIterator __last2) 03827 { 03828 // concept requirements 03829 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) 03830 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) 03831 __glibcxx_function_requires(_EqualOpConcept< 03832 typename iterator_traits<_InputIterator>::value_type, 03833 typename iterator_traits<_ForwardIterator>::value_type>) 03834 __glibcxx_requires_valid_range(__first1, __last1); 03835 __glibcxx_requires_valid_range(__first2, __last2); 03836 03837 for (; __first1 != __last1; ++__first1) 03838 for (_ForwardIterator __iter = __first2; __iter != __last2; ++__iter) 03839 if (*__first1 == *__iter) 03840 return __first1; 03841 return __last1; 03842 } 03843 03844 /** 03845 * @brief Find element from a set in a sequence using a predicate. 03846 * @ingroup non_mutating_algorithms 03847 * @param __first1 Start of range to search. 03848 * @param __last1 End of range to search. 03849 * @param __first2 Start of match candidates. 03850 * @param __last2 End of match candidates. 03851 * @param __comp Predicate to use. 03852 * @return The first iterator @c i in the range 03853 * @p [__first1,__last1) such that @c comp(*i, @p *(i2)) is true 03854 * and i2 is an iterator in [__first2,__last2), or @p __last1 if no 03855 * such iterator exists. 03856 * 03857 03858 * Searches the range @p [__first1,__last1) for an element that is 03859 * equal to some element in the range [__first2,__last2). If 03860 * found, returns an iterator in the range [__first1,__last1), 03861 * otherwise returns @p __last1. 03862 */ 03863 template<typename _InputIterator, typename _ForwardIterator, 03864 typename _BinaryPredicate> 03865 _InputIterator 03866 find_first_of(_InputIterator __first1, _InputIterator __last1, 03867 _ForwardIterator __first2, _ForwardIterator __last2, 03868 _BinaryPredicate __comp) 03869 { 03870 // concept requirements 03871 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) 03872 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) 03873 __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate, 03874 typename iterator_traits<_InputIterator>::value_type, 03875 typename iterator_traits<_ForwardIterator>::value_type>) 03876 __glibcxx_requires_valid_range(__first1, __last1); 03877 __glibcxx_requires_valid_range(__first2, __last2); 03878 03879 for (; __first1 != __last1; ++__first1) 03880 for (_ForwardIterator __iter = __first2; __iter != __last2; ++__iter) 03881 if (__comp(*__first1, *__iter)) 03882 return __first1; 03883 return __last1; 03884 } 03885 03886 /** 03887 * @brief Find two adjacent values in a sequence that are equal. 03888 * @ingroup non_mutating_algorithms 03889 * @param __first A forward iterator. 03890 * @param __last A forward iterator. 03891 * @return The first iterator @c i such that @c i and @c i+1 are both 03892 * valid iterators in @p [__first,__last) and such that @c *i == @c *(i+1), 03893 * or @p __last if no such iterator exists. 03894 */ 03895 template<typename _ForwardIterator> 03896 inline _ForwardIterator 03897 adjacent_find(_ForwardIterator __first, _ForwardIterator __last) 03898 { 03899 // concept requirements 03900 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) 03901 __glibcxx_function_requires(_EqualityComparableConcept< 03902 typename iterator_traits<_ForwardIterator>::value_type>) 03903 __glibcxx_requires_valid_range(__first, __last); 03904 03905 return std::__adjacent_find(__first, __last, 03906 __gnu_cxx::__ops::__iter_equal_to_iter()); 03907 } 03908 03909 /** 03910 * @brief Find two adjacent values in a sequence using a predicate. 03911 * @ingroup non_mutating_algorithms 03912 * @param __first A forward iterator. 03913 * @param __last A forward iterator. 03914 * @param __binary_pred A binary predicate. 03915 * @return The first iterator @c i such that @c i and @c i+1 are both 03916 * valid iterators in @p [__first,__last) and such that 03917 * @p __binary_pred(*i,*(i+1)) is true, or @p __last if no such iterator 03918 * exists. 03919 */ 03920 template<typename _ForwardIterator, typename _BinaryPredicate> 03921 inline _ForwardIterator 03922 adjacent_find(_ForwardIterator __first, _ForwardIterator __last, 03923 _BinaryPredicate __binary_pred) 03924 { 03925 // concept requirements 03926 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) 03927 __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate, 03928 typename iterator_traits<_ForwardIterator>::value_type, 03929 typename iterator_traits<_ForwardIterator>::value_type>) 03930 __glibcxx_requires_valid_range(__first, __last); 03931 03932 return std::__adjacent_find(__first, __last, 03933 __gnu_cxx::__ops::__iter_comp_iter(__binary_pred)); 03934 } 03935 03936 /** 03937 * @brief Count the number of copies of a value in a sequence. 03938 * @ingroup non_mutating_algorithms 03939 * @param __first An input iterator. 03940 * @param __last An input iterator. 03941 * @param __value The value to be counted. 03942 * @return The number of iterators @c i in the range @p [__first,__last) 03943 * for which @c *i == @p __value 03944 */ 03945 template<typename _InputIterator, typename _Tp> 03946 inline typename iterator_traits<_InputIterator>::difference_type 03947 count(_InputIterator __first, _InputIterator __last, const _Tp& __value) 03948 { 03949 // concept requirements 03950 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) 03951 __glibcxx_function_requires(_EqualOpConcept< 03952 typename iterator_traits<_InputIterator>::value_type, _Tp>) 03953 __glibcxx_requires_valid_range(__first, __last); 03954 03955 return std::__count_if(__first, __last, 03956 __gnu_cxx::__ops::__iter_equals_val(__value)); 03957 } 03958 03959 /** 03960 * @brief Count the elements of a sequence for which a predicate is true. 03961 * @ingroup non_mutating_algorithms 03962 * @param __first An input iterator. 03963 * @param __last An input iterator. 03964 * @param __pred A predicate. 03965 * @return The number of iterators @c i in the range @p [__first,__last) 03966 * for which @p __pred(*i) is true. 03967 */ 03968 template<typename _InputIterator, typename _Predicate> 03969 inline typename iterator_traits<_InputIterator>::difference_type 03970 count_if(_InputIterator __first, _InputIterator __last, _Predicate __pred) 03971 { 03972 // concept requirements 03973 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) 03974 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate, 03975 typename iterator_traits<_InputIterator>::value_type>) 03976 __glibcxx_requires_valid_range(__first, __last); 03977 03978 return std::__count_if(__first, __last, 03979 __gnu_cxx::__ops::__pred_iter(__pred)); 03980 } 03981 03982 /** 03983 * @brief Search a sequence for a matching sub-sequence. 03984 * @ingroup non_mutating_algorithms 03985 * @param __first1 A forward iterator. 03986 * @param __last1 A forward iterator. 03987 * @param __first2 A forward iterator. 03988 * @param __last2 A forward iterator. 03989 * @return The first iterator @c i in the range @p 03990 * [__first1,__last1-(__last2-__first2)) such that @c *(i+N) == @p 03991 * *(__first2+N) for each @c N in the range @p 03992 * [0,__last2-__first2), or @p __last1 if no such iterator exists. 03993 * 03994 * Searches the range @p [__first1,__last1) for a sub-sequence that 03995 * compares equal value-by-value with the sequence given by @p 03996 * [__first2,__last2) and returns an iterator to the first element 03997 * of the sub-sequence, or @p __last1 if the sub-sequence is not 03998 * found. 03999 * 04000 * Because the sub-sequence must lie completely within the range @p 04001 * [__first1,__last1) it must start at a position less than @p 04002 * __last1-(__last2-__first2) where @p __last2-__first2 is the 04003 * length of the sub-sequence. 04004 * 04005 * This means that the returned iterator @c i will be in the range 04006 * @p [__first1,__last1-(__last2-__first2)) 04007 */ 04008 template<typename _ForwardIterator1, typename _ForwardIterator2> 04009 inline _ForwardIterator1 04010 search(_ForwardIterator1 __first1, _ForwardIterator1 __last1, 04011 _ForwardIterator2 __first2, _ForwardIterator2 __last2) 04012 { 04013 // concept requirements 04014 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator1>) 04015 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator2>) 04016 __glibcxx_function_requires(_EqualOpConcept< 04017 typename iterator_traits<_ForwardIterator1>::value_type, 04018 typename iterator_traits<_ForwardIterator2>::value_type>) 04019 __glibcxx_requires_valid_range(__first1, __last1); 04020 __glibcxx_requires_valid_range(__first2, __last2); 04021 04022 return std::__search(__first1, __last1, __first2, __last2, 04023 __gnu_cxx::__ops::__iter_equal_to_iter()); 04024 } 04025 04026 /** 04027 * @brief Search a sequence for a matching sub-sequence using a predicate. 04028 * @ingroup non_mutating_algorithms 04029 * @param __first1 A forward iterator. 04030 * @param __last1 A forward iterator. 04031 * @param __first2 A forward iterator. 04032 * @param __last2 A forward iterator. 04033 * @param __predicate A binary predicate. 04034 * @return The first iterator @c i in the range 04035 * @p [__first1,__last1-(__last2-__first2)) such that 04036 * @p __predicate(*(i+N),*(__first2+N)) is true for each @c N in the range 04037 * @p [0,__last2-__first2), or @p __last1 if no such iterator exists. 04038 * 04039 * Searches the range @p [__first1,__last1) for a sub-sequence that 04040 * compares equal value-by-value with the sequence given by @p 04041 * [__first2,__last2), using @p __predicate to determine equality, 04042 * and returns an iterator to the first element of the 04043 * sub-sequence, or @p __last1 if no such iterator exists. 04044 * 04045 * @see search(_ForwardIter1, _ForwardIter1, _ForwardIter2, _ForwardIter2) 04046 */ 04047 template<typename _ForwardIterator1, typename _ForwardIterator2, 04048 typename _BinaryPredicate> 04049 inline _ForwardIterator1 04050 search(_ForwardIterator1 __first1, _ForwardIterator1 __last1, 04051 _ForwardIterator2 __first2, _ForwardIterator2 __last2, 04052 _BinaryPredicate __predicate) 04053 { 04054 // concept requirements 04055 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator1>) 04056 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator2>) 04057 __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate, 04058 typename iterator_traits<_ForwardIterator1>::value_type, 04059 typename iterator_traits<_ForwardIterator2>::value_type>) 04060 __glibcxx_requires_valid_range(__first1, __last1); 04061 __glibcxx_requires_valid_range(__first2, __last2); 04062 04063 return std::__search(__first1, __last1, __first2, __last2, 04064 __gnu_cxx::__ops::__iter_comp_iter(__predicate)); 04065 } 04066 04067 /** 04068 * @brief Search a sequence for a number of consecutive values. 04069 * @ingroup non_mutating_algorithms 04070 * @param __first A forward iterator. 04071 * @param __last A forward iterator. 04072 * @param __count The number of consecutive values. 04073 * @param __val The value to find. 04074 * @return The first iterator @c i in the range @p 04075 * [__first,__last-__count) such that @c *(i+N) == @p __val for 04076 * each @c N in the range @p [0,__count), or @p __last if no such 04077 * iterator exists. 04078 * 04079 * Searches the range @p [__first,__last) for @p count consecutive elements 04080 * equal to @p __val. 04081 */ 04082 template<typename _ForwardIterator, typename _Integer, typename _Tp> 04083 inline _ForwardIterator 04084 search_n(_ForwardIterator __first, _ForwardIterator __last, 04085 _Integer __count, const _Tp& __val) 04086 { 04087 // concept requirements 04088 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) 04089 __glibcxx_function_requires(_EqualOpConcept< 04090 typename iterator_traits<_ForwardIterator>::value_type, _Tp>) 04091 __glibcxx_requires_valid_range(__first, __last); 04092 04093 return std::__search_n(__first, __last, __count, 04094 __gnu_cxx::__ops::__iter_equals_val(__val)); 04095 } 04096 04097 04098 /** 04099 * @brief Search a sequence for a number of consecutive values using a 04100 * predicate. 04101 * @ingroup non_mutating_algorithms 04102 * @param __first A forward iterator. 04103 * @param __last A forward iterator. 04104 * @param __count The number of consecutive values. 04105 * @param __val The value to find. 04106 * @param __binary_pred A binary predicate. 04107 * @return The first iterator @c i in the range @p 04108 * [__first,__last-__count) such that @p 04109 * __binary_pred(*(i+N),__val) is true for each @c N in the range 04110 * @p [0,__count), or @p __last if no such iterator exists. 04111 * 04112 * Searches the range @p [__first,__last) for @p __count 04113 * consecutive elements for which the predicate returns true. 04114 */ 04115 template<typename _ForwardIterator, typename _Integer, typename _Tp, 04116 typename _BinaryPredicate> 04117 inline _ForwardIterator 04118 search_n(_ForwardIterator __first, _ForwardIterator __last, 04119 _Integer __count, const _Tp& __val, 04120 _BinaryPredicate __binary_pred) 04121 { 04122 // concept requirements 04123 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) 04124 __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate, 04125 typename iterator_traits<_ForwardIterator>::value_type, _Tp>) 04126 __glibcxx_requires_valid_range(__first, __last); 04127 04128 return std::__search_n(__first, __last, __count, 04129 __gnu_cxx::__ops::__iter_comp_val(__binary_pred, __val)); 04130 } 04131 04132 04133 /** 04134 * @brief Perform an operation on a sequence. 04135 * @ingroup mutating_algorithms 04136 * @param __first An input iterator. 04137 * @param __last An input iterator. 04138 * @param __result An output iterator. 04139 * @param __unary_op A unary operator. 04140 * @return An output iterator equal to @p __result+(__last-__first). 04141 * 04142 * Applies the operator to each element in the input range and assigns 04143 * the results to successive elements of the output sequence. 04144 * Evaluates @p *(__result+N)=unary_op(*(__first+N)) for each @c N in the 04145 * range @p [0,__last-__first). 04146 * 04147 * @p unary_op must not alter its argument. 04148 */ 04149 template<typename _InputIterator, typename _OutputIterator, 04150 typename _UnaryOperation> 04151 _OutputIterator 04152 transform(_InputIterator __first, _InputIterator __last, 04153 _OutputIterator __result, _UnaryOperation __unary_op) 04154 { 04155 // concept requirements 04156 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) 04157 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, 04158 // "the type returned by a _UnaryOperation" 04159 __typeof__(__unary_op(*__first))>) 04160 __glibcxx_requires_valid_range(__first, __last); 04161 04162 for (; __first != __last; ++__first, ++__result) 04163 *__result = __unary_op(*__first); 04164 return __result; 04165 } 04166 04167 /** 04168 * @brief Perform an operation on corresponding elements of two sequences. 04169 * @ingroup mutating_algorithms 04170 * @param __first1 An input iterator. 04171 * @param __last1 An input iterator. 04172 * @param __first2 An input iterator. 04173 * @param __result An output iterator. 04174 * @param __binary_op A binary operator. 04175 * @return An output iterator equal to @p result+(last-first). 04176 * 04177 * Applies the operator to the corresponding elements in the two 04178 * input ranges and assigns the results to successive elements of the 04179 * output sequence. 04180 * Evaluates @p 04181 * *(__result+N)=__binary_op(*(__first1+N),*(__first2+N)) for each 04182 * @c N in the range @p [0,__last1-__first1). 04183 * 04184 * @p binary_op must not alter either of its arguments. 04185 */ 04186 template<typename _InputIterator1, typename _InputIterator2, 04187 typename _OutputIterator, typename _BinaryOperation> 04188 _OutputIterator 04189 transform(_InputIterator1 __first1, _InputIterator1 __last1, 04190 _InputIterator2 __first2, _OutputIterator __result, 04191 _BinaryOperation __binary_op) 04192 { 04193 // concept requirements 04194 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>) 04195 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>) 04196 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, 04197 // "the type returned by a _BinaryOperation" 04198 __typeof__(__binary_op(*__first1,*__first2))>) 04199 __glibcxx_requires_valid_range(__first1, __last1); 04200 04201 for (; __first1 != __last1; ++__first1, ++__first2, ++__result) 04202 *__result = __binary_op(*__first1, *__first2); 04203 return __result; 04204 } 04205 04206 /** 04207 * @brief Replace each occurrence of one value in a sequence with another 04208 * value. 04209 * @ingroup mutating_algorithms 04210 * @param __first A forward iterator. 04211 * @param __last A forward iterator. 04212 * @param __old_value The value to be replaced. 04213 * @param __new_value The replacement value. 04214 * @return replace() returns no value. 04215 * 04216 * For each iterator @c i in the range @p [__first,__last) if @c *i == 04217 * @p __old_value then the assignment @c *i = @p __new_value is performed. 04218 */ 04219 template<typename _ForwardIterator, typename _Tp> 04220 void 04221 replace(_ForwardIterator __first, _ForwardIterator __last, 04222 const _Tp& __old_value, const _Tp& __new_value) 04223 { 04224 // concept requirements 04225 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept< 04226 _ForwardIterator>) 04227 __glibcxx_function_requires(_EqualOpConcept< 04228 typename iterator_traits<_ForwardIterator>::value_type, _Tp>) 04229 __glibcxx_function_requires(_ConvertibleConcept<_Tp, 04230 typename iterator_traits<_ForwardIterator>::value_type>) 04231 __glibcxx_requires_valid_range(__first, __last); 04232 04233 for (; __first != __last; ++__first) 04234 if (*__first == __old_value) 04235 *__first = __new_value; 04236 } 04237 04238 /** 04239 * @brief Replace each value in a sequence for which a predicate returns 04240 * true with another value. 04241 * @ingroup mutating_algorithms 04242 * @param __first A forward iterator. 04243 * @param __last A forward iterator. 04244 * @param __pred A predicate. 04245 * @param __new_value The replacement value. 04246 * @return replace_if() returns no value. 04247 * 04248 * For each iterator @c i in the range @p [__first,__last) if @p __pred(*i) 04249 * is true then the assignment @c *i = @p __new_value is performed. 04250 */ 04251 template<typename _ForwardIterator, typename _Predicate, typename _Tp> 04252 void 04253 replace_if(_ForwardIterator __first, _ForwardIterator __last, 04254 _Predicate __pred, const _Tp& __new_value) 04255 { 04256 // concept requirements 04257 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept< 04258 _ForwardIterator>) 04259 __glibcxx_function_requires(_ConvertibleConcept<_Tp, 04260 typename iterator_traits<_ForwardIterator>::value_type>) 04261 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate, 04262 typename iterator_traits<_ForwardIterator>::value_type>) 04263 __glibcxx_requires_valid_range(__first, __last); 04264 04265 for (; __first != __last; ++__first) 04266 if (__pred(*__first)) 04267 *__first = __new_value; 04268 } 04269 04270 /** 04271 * @brief Assign the result of a function object to each value in a 04272 * sequence. 04273 * @ingroup mutating_algorithms 04274 * @param __first A forward iterator. 04275 * @param __last A forward iterator. 04276 * @param __gen A function object taking no arguments and returning 04277 * std::iterator_traits<_ForwardIterator>::value_type 04278 * @return generate() returns no value. 04279 * 04280 * Performs the assignment @c *i = @p __gen() for each @c i in the range 04281 * @p [__first,__last). 04282 */ 04283 template<typename _ForwardIterator, typename _Generator> 04284 void 04285 generate(_ForwardIterator __first, _ForwardIterator __last, 04286 _Generator __gen) 04287 { 04288 // concept requirements 04289 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) 04290 __glibcxx_function_requires(_GeneratorConcept<_Generator, 04291 typename iterator_traits<_ForwardIterator>::value_type>) 04292 __glibcxx_requires_valid_range(__first, __last); 04293 04294 for (; __first != __last; ++__first) 04295 *__first = __gen(); 04296 } 04297 04298 /** 04299 * @brief Assign the result of a function object to each value in a 04300 * sequence. 04301 * @ingroup mutating_algorithms 04302 * @param __first A forward iterator. 04303 * @param __n The length of the sequence. 04304 * @param __gen A function object taking no arguments and returning 04305 * std::iterator_traits<_ForwardIterator>::value_type 04306 * @return The end of the sequence, @p __first+__n 04307 * 04308 * Performs the assignment @c *i = @p __gen() for each @c i in the range 04309 * @p [__first,__first+__n). 04310 * 04311 * _GLIBCXX_RESOLVE_LIB_DEFECTS 04312 * DR 865. More algorithms that throw away information 04313 */ 04314 template<typename _OutputIterator, typename _Size, typename _Generator> 04315 _OutputIterator 04316 generate_n(_OutputIterator __first, _Size __n, _Generator __gen) 04317 { 04318 // concept requirements 04319 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, 04320 // "the type returned by a _Generator" 04321 __typeof__(__gen())>) 04322 04323 for (__decltype(__n + 0) __niter = __n; 04324 __niter > 0; --__niter, ++__first) 04325 *__first = __gen(); 04326 return __first; 04327 } 04328 04329 /** 04330 * @brief Copy a sequence, removing consecutive duplicate values. 04331 * @ingroup mutating_algorithms 04332 * @param __first An input iterator. 04333 * @param __last An input iterator. 04334 * @param __result An output iterator. 04335 * @return An iterator designating the end of the resulting sequence. 04336 * 04337 * Copies each element in the range @p [__first,__last) to the range 04338 * beginning at @p __result, except that only the first element is copied 04339 * from groups of consecutive elements that compare equal. 04340 * unique_copy() is stable, so the relative order of elements that are 04341 * copied is unchanged. 04342 * 04343 * _GLIBCXX_RESOLVE_LIB_DEFECTS 04344 * DR 241. Does unique_copy() require CopyConstructible and Assignable? 04345 * 04346 * _GLIBCXX_RESOLVE_LIB_DEFECTS 04347 * DR 538. 241 again: Does unique_copy() require CopyConstructible and 04348 * Assignable? 04349 */ 04350 template<typename _InputIterator, typename _OutputIterator> 04351 inline _OutputIterator 04352 unique_copy(_InputIterator __first, _InputIterator __last, 04353 _OutputIterator __result) 04354 { 04355 // concept requirements 04356 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) 04357 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, 04358 typename iterator_traits<_InputIterator>::value_type>) 04359 __glibcxx_function_requires(_EqualityComparableConcept< 04360 typename iterator_traits<_InputIterator>::value_type>) 04361 __glibcxx_requires_valid_range(__first, __last); 04362 04363 if (__first == __last) 04364 return __result; 04365 return std::__unique_copy(__first, __last, __result, 04366 __gnu_cxx::__ops::__iter_equal_to_iter(), 04367 std::__iterator_category(__first), 04368 std::__iterator_category(__result)); 04369 } 04370 04371 /** 04372 * @brief Copy a sequence, removing consecutive values using a predicate. 04373 * @ingroup mutating_algorithms 04374 * @param __first An input iterator. 04375 * @param __last An input iterator. 04376 * @param __result An output iterator. 04377 * @param __binary_pred A binary predicate. 04378 * @return An iterator designating the end of the resulting sequence. 04379 * 04380 * Copies each element in the range @p [__first,__last) to the range 04381 * beginning at @p __result, except that only the first element is copied 04382 * from groups of consecutive elements for which @p __binary_pred returns 04383 * true. 04384 * unique_copy() is stable, so the relative order of elements that are 04385 * copied is unchanged. 04386 * 04387 * _GLIBCXX_RESOLVE_LIB_DEFECTS 04388 * DR 241. Does unique_copy() require CopyConstructible and Assignable? 04389 */ 04390 template<typename _InputIterator, typename _OutputIterator, 04391 typename _BinaryPredicate> 04392 inline _OutputIterator 04393 unique_copy(_InputIterator __first, _InputIterator __last, 04394 _OutputIterator __result, 04395 _BinaryPredicate __binary_pred) 04396 { 04397 // concept requirements -- predicates checked later 04398 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) 04399 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, 04400 typename iterator_traits<_InputIterator>::value_type>) 04401 __glibcxx_requires_valid_range(__first, __last); 04402 04403 if (__first == __last) 04404 return __result; 04405 return std::__unique_copy(__first, __last, __result, 04406 __gnu_cxx::__ops::__iter_comp_iter(__binary_pred), 04407 std::__iterator_category(__first), 04408 std::__iterator_category(__result)); 04409 } 04410 04411 /** 04412 * @brief Randomly shuffle the elements of a sequence. 04413 * @ingroup mutating_algorithms 04414 * @param __first A forward iterator. 04415 * @param __last A forward iterator. 04416 * @return Nothing. 04417 * 04418 * Reorder the elements in the range @p [__first,__last) using a random 04419 * distribution, so that every possible ordering of the sequence is 04420 * equally likely. 04421 */ 04422 template<typename _RandomAccessIterator> 04423 inline void 04424 random_shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last) 04425 { 04426 // concept requirements 04427 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept< 04428 _RandomAccessIterator>) 04429 __glibcxx_requires_valid_range(__first, __last); 04430 04431 if (__first != __last) 04432 for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i) 04433 std::iter_swap(__i, __first + (std::rand() % ((__i - __first) + 1))); 04434 } 04435 04436 /** 04437 * @brief Shuffle the elements of a sequence using a random number 04438 * generator. 04439 * @ingroup mutating_algorithms 04440 * @param __first A forward iterator. 04441 * @param __last A forward iterator. 04442 * @param __rand The RNG functor or function. 04443 * @return Nothing. 04444 * 04445 * Reorders the elements in the range @p [__first,__last) using @p __rand to 04446 * provide a random distribution. Calling @p __rand(N) for a positive 04447 * integer @p N should return a randomly chosen integer from the 04448 * range [0,N). 04449 */ 04450 template<typename _RandomAccessIterator, typename _RandomNumberGenerator> 04451 void 04452 random_shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last, 04453 #if __cplusplus >= 201103L 04454 _RandomNumberGenerator&& __rand) 04455 #else 04456 _RandomNumberGenerator& __rand) 04457 #endif 04458 { 04459 // concept requirements 04460 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept< 04461 _RandomAccessIterator>) 04462 __glibcxx_requires_valid_range(__first, __last); 04463 04464 if (__first == __last) 04465 return; 04466 for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i) 04467 std::iter_swap(__i, __first + __rand((__i - __first) + 1)); 04468 } 04469 04470 04471 /** 04472 * @brief Move elements for which a predicate is true to the beginning 04473 * of a sequence. 04474 * @ingroup mutating_algorithms 04475 * @param __first A forward iterator. 04476 * @param __last A forward iterator. 04477 * @param __pred A predicate functor. 04478 * @return An iterator @p middle such that @p __pred(i) is true for each 04479 * iterator @p i in the range @p [__first,middle) and false for each @p i 04480 * in the range @p [middle,__last). 04481 * 04482 * @p __pred must not modify its operand. @p partition() does not preserve 04483 * the relative ordering of elements in each group, use 04484 * @p stable_partition() if this is needed. 04485 */ 04486 template<typename _ForwardIterator, typename _Predicate> 04487 inline _ForwardIterator 04488 partition(_ForwardIterator __first, _ForwardIterator __last, 04489 _Predicate __pred) 04490 { 04491 // concept requirements 04492 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept< 04493 _ForwardIterator>) 04494 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate, 04495 typename iterator_traits<_ForwardIterator>::value_type>) 04496 __glibcxx_requires_valid_range(__first, __last); 04497 04498 return std::__partition(__first, __last, __pred, 04499 std::__iterator_category(__first)); 04500 } 04501 04502 04503 /** 04504 * @brief Sort the smallest elements of a sequence. 04505 * @ingroup sorting_algorithms 04506 * @param __first An iterator. 04507 * @param __middle Another iterator. 04508 * @param __last Another iterator. 04509 * @return Nothing. 04510 * 04511 * Sorts the smallest @p (__middle-__first) elements in the range 04512 * @p [first,last) and moves them to the range @p [__first,__middle). The 04513 * order of the remaining elements in the range @p [__middle,__last) is 04514 * undefined. 04515 * After the sort if @e i and @e j are iterators in the range 04516 * @p [__first,__middle) such that i precedes j and @e k is an iterator in 04517 * the range @p [__middle,__last) then *j<*i and *k<*i are both false. 04518 */ 04519 template<typename _RandomAccessIterator> 04520 inline void 04521 partial_sort(_RandomAccessIterator __first, 04522 _RandomAccessIterator __middle, 04523 _RandomAccessIterator __last) 04524 { 04525 // concept requirements 04526 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept< 04527 _RandomAccessIterator>) 04528 __glibcxx_function_requires(_LessThanComparableConcept< 04529 typename iterator_traits<_RandomAccessIterator>::value_type>) 04530 __glibcxx_requires_valid_range(__first, __middle); 04531 __glibcxx_requires_valid_range(__middle, __last); 04532 04533 std::__partial_sort(__first, __middle, __last, 04534 __gnu_cxx::__ops::__iter_less_iter()); 04535 } 04536 04537 /** 04538 * @brief Sort the smallest elements of a sequence using a predicate 04539 * for comparison. 04540 * @ingroup sorting_algorithms 04541 * @param __first An iterator. 04542 * @param __middle Another iterator. 04543 * @param __last Another iterator. 04544 * @param __comp A comparison functor. 04545 * @return Nothing. 04546 * 04547 * Sorts the smallest @p (__middle-__first) elements in the range 04548 * @p [__first,__last) and moves them to the range @p [__first,__middle). The 04549 * order of the remaining elements in the range @p [__middle,__last) is 04550 * undefined. 04551 * After the sort if @e i and @e j are iterators in the range 04552 * @p [__first,__middle) such that i precedes j and @e k is an iterator in 04553 * the range @p [__middle,__last) then @p *__comp(j,*i) and @p __comp(*k,*i) 04554 * are both false. 04555 */ 04556 template<typename _RandomAccessIterator, typename _Compare> 04557 inline void 04558 partial_sort(_RandomAccessIterator __first, 04559 _RandomAccessIterator __middle, 04560 _RandomAccessIterator __last, 04561 _Compare __comp) 04562 { 04563 // concept requirements 04564 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept< 04565 _RandomAccessIterator>) 04566 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, 04567 typename iterator_traits<_RandomAccessIterator>::value_type, 04568 typename iterator_traits<_RandomAccessIterator>::value_type>) 04569 __glibcxx_requires_valid_range(__first, __middle); 04570 __glibcxx_requires_valid_range(__middle, __last); 04571 04572 std::__partial_sort(__first, __middle, __last, 04573 __gnu_cxx::__ops::__iter_comp_iter(__comp)); 04574 } 04575 04576 /** 04577 * @brief Sort a sequence just enough to find a particular position. 04578 * @ingroup sorting_algorithms 04579 * @param __first An iterator. 04580 * @param __nth Another iterator. 04581 * @param __last Another iterator. 04582 * @return Nothing. 04583 * 04584 * Rearranges the elements in the range @p [__first,__last) so that @p *__nth 04585 * is the same element that would have been in that position had the 04586 * whole sequence been sorted. The elements either side of @p *__nth are 04587 * not completely sorted, but for any iterator @e i in the range 04588 * @p [__first,__nth) and any iterator @e j in the range @p [__nth,__last) it 04589 * holds that *j < *i is false. 04590 */ 04591 template<typename _RandomAccessIterator> 04592 inline void 04593 nth_element(_RandomAccessIterator __first, _RandomAccessIterator __nth, 04594 _RandomAccessIterator __last) 04595 { 04596 // concept requirements 04597 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept< 04598 _RandomAccessIterator>) 04599 __glibcxx_function_requires(_LessThanComparableConcept< 04600 typename iterator_traits<_RandomAccessIterator>::value_type>) 04601 __glibcxx_requires_valid_range(__first, __nth); 04602 __glibcxx_requires_valid_range(__nth, __last); 04603 04604 if (__first == __last || __nth == __last) 04605 return; 04606 04607 std::__introselect(__first, __nth, __last, 04608 std::__lg(__last - __first) * 2, 04609 __gnu_cxx::__ops::__iter_less_iter()); 04610 } 04611 04612 /** 04613 * @brief Sort a sequence just enough to find a particular position 04614 * using a predicate for comparison. 04615 * @ingroup sorting_algorithms 04616 * @param __first An iterator. 04617 * @param __nth Another iterator. 04618 * @param __last Another iterator. 04619 * @param __comp A comparison functor. 04620 * @return Nothing. 04621 * 04622 * Rearranges the elements in the range @p [__first,__last) so that @p *__nth 04623 * is the same element that would have been in that position had the 04624 * whole sequence been sorted. The elements either side of @p *__nth are 04625 * not completely sorted, but for any iterator @e i in the range 04626 * @p [__first,__nth) and any iterator @e j in the range @p [__nth,__last) it 04627 * holds that @p __comp(*j,*i) is false. 04628 */ 04629 template<typename _RandomAccessIterator, typename _Compare> 04630 inline void 04631 nth_element(_RandomAccessIterator __first, _RandomAccessIterator __nth, 04632 _RandomAccessIterator __last, _Compare __comp) 04633 { 04634 // concept requirements 04635 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept< 04636 _RandomAccessIterator>) 04637 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, 04638 typename iterator_traits<_RandomAccessIterator>::value_type, 04639 typename iterator_traits<_RandomAccessIterator>::value_type>) 04640 __glibcxx_requires_valid_range(__first, __nth); 04641 __glibcxx_requires_valid_range(__nth, __last); 04642 04643 if (__first == __last || __nth == __last) 04644 return; 04645 04646 std::__introselect(__first, __nth, __last, 04647 std::__lg(__last - __first) * 2, 04648 __gnu_cxx::__ops::__iter_comp_iter(__comp)); 04649 } 04650 04651 /** 04652 * @brief Sort the elements of a sequence. 04653 * @ingroup sorting_algorithms 04654 * @param __first An iterator. 04655 * @param __last Another iterator. 04656 * @return Nothing. 04657 * 04658 * Sorts the elements in the range @p [__first,__last) in ascending order, 04659 * such that for each iterator @e i in the range @p [__first,__last-1), 04660 * *(i+1)<*i is false. 04661 * 04662 * The relative ordering of equivalent elements is not preserved, use 04663 * @p stable_sort() if this is needed. 04664 */ 04665 template<typename _RandomAccessIterator> 04666 inline void 04667 sort(_RandomAccessIterator __first, _RandomAccessIterator __last) 04668 { 04669 // concept requirements 04670 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept< 04671 _RandomAccessIterator>) 04672 __glibcxx_function_requires(_LessThanComparableConcept< 04673 typename iterator_traits<_RandomAccessIterator>::value_type>) 04674 __glibcxx_requires_valid_range(__first, __last); 04675 04676 std::__sort(__first, __last, __gnu_cxx::__ops::__iter_less_iter()); 04677 } 04678 04679 /** 04680 * @brief Sort the elements of a sequence using a predicate for comparison. 04681 * @ingroup sorting_algorithms 04682 * @param __first An iterator. 04683 * @param __last Another iterator. 04684 * @param __comp A comparison functor. 04685 * @return Nothing. 04686 * 04687 * Sorts the elements in the range @p [__first,__last) in ascending order, 04688 * such that @p __comp(*(i+1),*i) is false for every iterator @e i in the 04689 * range @p [__first,__last-1). 04690 * 04691 * The relative ordering of equivalent elements is not preserved, use 04692 * @p stable_sort() if this is needed. 04693 */ 04694 template<typename _RandomAccessIterator, typename _Compare> 04695 inline void 04696 sort(_RandomAccessIterator __first, _RandomAccessIterator __last, 04697 _Compare __comp) 04698 { 04699 // concept requirements 04700 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept< 04701 _RandomAccessIterator>) 04702 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, 04703 typename iterator_traits<_RandomAccessIterator>::value_type, 04704 typename iterator_traits<_RandomAccessIterator>::value_type>) 04705 __glibcxx_requires_valid_range(__first, __last); 04706 04707 std::__sort(__first, __last, __gnu_cxx::__ops::__iter_comp_iter(__comp)); 04708 } 04709 04710 template<typename _InputIterator1, typename _InputIterator2, 04711 typename _OutputIterator, typename _Compare> 04712 _OutputIterator 04713 __merge(_InputIterator1 __first1, _InputIterator1 __last1, 04714 _InputIterator2 __first2, _InputIterator2 __last2, 04715 _OutputIterator __result, _Compare __comp) 04716 { 04717 while (__first1 != __last1 && __first2 != __last2) 04718 { 04719 if (__comp(__first2, __first1)) 04720 { 04721 *__result = *__first2; 04722 ++__first2; 04723 } 04724 else 04725 { 04726 *__result = *__first1; 04727 ++__first1; 04728 } 04729 ++__result; 04730 } 04731 return std::copy(__first2, __last2, 04732 std::copy(__first1, __last1, __result)); 04733 } 04734 04735 /** 04736 * @brief Merges two sorted ranges. 04737 * @ingroup sorting_algorithms 04738 * @param __first1 An iterator. 04739 * @param __first2 Another iterator. 04740 * @param __last1 Another iterator. 04741 * @param __last2 Another iterator. 04742 * @param __result An iterator pointing to the end of the merged range. 04743 * @return An iterator pointing to the first element <em>not less 04744 * than</em> @e val. 04745 * 04746 * Merges the ranges @p [__first1,__last1) and @p [__first2,__last2) into 04747 * the sorted range @p [__result, __result + (__last1-__first1) + 04748 * (__last2-__first2)). Both input ranges must be sorted, and the 04749 * output range must not overlap with either of the input ranges. 04750 * The sort is @e stable, that is, for equivalent elements in the 04751 * two ranges, elements from the first range will always come 04752 * before elements from the second. 04753 */ 04754 template<typename _InputIterator1, typename _InputIterator2, 04755 typename _OutputIterator> 04756 inline _OutputIterator 04757 merge(_InputIterator1 __first1, _InputIterator1 __last1, 04758 _InputIterator2 __first2, _InputIterator2 __last2, 04759 _OutputIterator __result) 04760 { 04761 // concept requirements 04762 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>) 04763 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>) 04764 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, 04765 typename iterator_traits<_InputIterator1>::value_type>) 04766 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, 04767 typename iterator_traits<_InputIterator2>::value_type>) 04768 __glibcxx_function_requires(_LessThanOpConcept< 04769 typename iterator_traits<_InputIterator2>::value_type, 04770 typename iterator_traits<_InputIterator1>::value_type>) 04771 __glibcxx_requires_sorted_set(__first1, __last1, __first2); 04772 __glibcxx_requires_sorted_set(__first2, __last2, __first1); 04773 04774 return _GLIBCXX_STD_A::__merge(__first1, __last1, 04775 __first2, __last2, __result, 04776 __gnu_cxx::__ops::__iter_less_iter()); 04777 } 04778 04779 /** 04780 * @brief Merges two sorted ranges. 04781 * @ingroup sorting_algorithms 04782 * @param __first1 An iterator. 04783 * @param __first2 Another iterator. 04784 * @param __last1 Another iterator. 04785 * @param __last2 Another iterator. 04786 * @param __result An iterator pointing to the end of the merged range. 04787 * @param __comp A functor to use for comparisons. 04788 * @return An iterator pointing to the first element "not less 04789 * than" @e val. 04790 * 04791 * Merges the ranges @p [__first1,__last1) and @p [__first2,__last2) into 04792 * the sorted range @p [__result, __result + (__last1-__first1) + 04793 * (__last2-__first2)). Both input ranges must be sorted, and the 04794 * output range must not overlap with either of the input ranges. 04795 * The sort is @e stable, that is, for equivalent elements in the 04796 * two ranges, elements from the first range will always come 04797 * before elements from the second. 04798 * 04799 * The comparison function should have the same effects on ordering as 04800 * the function used for the initial sort. 04801 */ 04802 template<typename _InputIterator1, typename _InputIterator2, 04803 typename _OutputIterator, typename _Compare> 04804 inline _OutputIterator 04805 merge(_InputIterator1 __first1, _InputIterator1 __last1, 04806 _InputIterator2 __first2, _InputIterator2 __last2, 04807 _OutputIterator __result, _Compare __comp) 04808 { 04809 // concept requirements 04810 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>) 04811 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>) 04812 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, 04813 typename iterator_traits<_InputIterator1>::value_type>) 04814 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, 04815 typename iterator_traits<_InputIterator2>::value_type>) 04816 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, 04817 typename iterator_traits<_InputIterator2>::value_type, 04818 typename iterator_traits<_InputIterator1>::value_type>) 04819 __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp); 04820 __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp); 04821 04822 return _GLIBCXX_STD_A::__merge(__first1, __last1, 04823 __first2, __last2, __result, 04824 __gnu_cxx::__ops::__iter_comp_iter(__comp)); 04825 } 04826 04827 template<typename _RandomAccessIterator, typename _Compare> 04828 inline void 04829 __stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last, 04830 _Compare __comp) 04831 { 04832 typedef typename iterator_traits<_RandomAccessIterator>::value_type 04833 _ValueType; 04834 typedef typename iterator_traits<_RandomAccessIterator>::difference_type 04835 _DistanceType; 04836 04837 typedef _Temporary_buffer<_RandomAccessIterator, _ValueType> _TmpBuf; 04838 _TmpBuf __buf(__first, __last); 04839 04840 if (__buf.begin() == 0) 04841 std::__inplace_stable_sort(__first, __last, __comp); 04842 else 04843 std::__stable_sort_adaptive(__first, __last, __buf.begin(), 04844 _DistanceType(__buf.size()), __comp); 04845 } 04846 04847 /** 04848 * @brief Sort the elements of a sequence, preserving the relative order 04849 * of equivalent elements. 04850 * @ingroup sorting_algorithms 04851 * @param __first An iterator. 04852 * @param __last Another iterator. 04853 * @return Nothing. 04854 * 04855 * Sorts the elements in the range @p [__first,__last) in ascending order, 04856 * such that for each iterator @p i in the range @p [__first,__last-1), 04857 * @p *(i+1)<*i is false. 04858 * 04859 * The relative ordering of equivalent elements is preserved, so any two 04860 * elements @p x and @p y in the range @p [__first,__last) such that 04861 * @p x<y is false and @p y<x is false will have the same relative 04862 * ordering after calling @p stable_sort(). 04863 */ 04864 template<typename _RandomAccessIterator> 04865 inline void 04866 stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last) 04867 { 04868 // concept requirements 04869 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept< 04870 _RandomAccessIterator>) 04871 __glibcxx_function_requires(_LessThanComparableConcept< 04872 typename iterator_traits<_RandomAccessIterator>::value_type>) 04873 __glibcxx_requires_valid_range(__first, __last); 04874 04875 _GLIBCXX_STD_A::__stable_sort(__first, __last, 04876 __gnu_cxx::__ops::__iter_less_iter()); 04877 } 04878 04879 /** 04880 * @brief Sort the elements of a sequence using a predicate for comparison, 04881 * preserving the relative order of equivalent elements. 04882 * @ingroup sorting_algorithms 04883 * @param __first An iterator. 04884 * @param __last Another iterator. 04885 * @param __comp A comparison functor. 04886 * @return Nothing. 04887 * 04888 * Sorts the elements in the range @p [__first,__last) in ascending order, 04889 * such that for each iterator @p i in the range @p [__first,__last-1), 04890 * @p __comp(*(i+1),*i) is false. 04891 * 04892 * The relative ordering of equivalent elements is preserved, so any two 04893 * elements @p x and @p y in the range @p [__first,__last) such that 04894 * @p __comp(x,y) is false and @p __comp(y,x) is false will have the same 04895 * relative ordering after calling @p stable_sort(). 04896 */ 04897 template<typename _RandomAccessIterator, typename _Compare> 04898 inline void 04899 stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last, 04900 _Compare __comp) 04901 { 04902 // concept requirements 04903 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept< 04904 _RandomAccessIterator>) 04905 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, 04906 typename iterator_traits<_RandomAccessIterator>::value_type, 04907 typename iterator_traits<_RandomAccessIterator>::value_type>) 04908 __glibcxx_requires_valid_range(__first, __last); 04909 04910 _GLIBCXX_STD_A::__stable_sort(__first, __last, 04911 __gnu_cxx::__ops::__iter_comp_iter(__comp)); 04912 } 04913 04914 template<typename _InputIterator1, typename _InputIterator2, 04915 typename _OutputIterator, 04916 typename _Compare> 04917 _OutputIterator 04918 __set_union(_InputIterator1 __first1, _InputIterator1 __last1, 04919 _InputIterator2 __first2, _InputIterator2 __last2, 04920 _OutputIterator __result, _Compare __comp) 04921 { 04922 while (__first1 != __last1 && __first2 != __last2) 04923 { 04924 if (__comp(__first1, __first2)) 04925 { 04926 *__result = *__first1; 04927 ++__first1; 04928 } 04929 else if (__comp(__first2, __first1)) 04930 { 04931 *__result = *__first2; 04932 ++__first2; 04933 } 04934 else 04935 { 04936 *__result = *__first1; 04937 ++__first1; 04938 ++__first2; 04939 } 04940 ++__result; 04941 } 04942 return std::copy(__first2, __last2, 04943 std::copy(__first1, __last1, __result)); 04944 } 04945 04946 /** 04947 * @brief Return the union of two sorted ranges. 04948 * @ingroup set_algorithms 04949 * @param __first1 Start of first range. 04950 * @param __last1 End of first range. 04951 * @param __first2 Start of second range. 04952 * @param __last2 End of second range. 04953 * @return End of the output range. 04954 * @ingroup set_algorithms 04955 * 04956 * This operation iterates over both ranges, copying elements present in 04957 * each range in order to the output range. Iterators increment for each 04958 * range. When the current element of one range is less than the other, 04959 * that element is copied and the iterator advanced. If an element is 04960 * contained in both ranges, the element from the first range is copied and 04961 * both ranges advance. The output range may not overlap either input 04962 * range. 04963 */ 04964 template<typename _InputIterator1, typename _InputIterator2, 04965 typename _OutputIterator> 04966 inline _OutputIterator 04967 set_union(_InputIterator1 __first1, _InputIterator1 __last1, 04968 _InputIterator2 __first2, _InputIterator2 __last2, 04969 _OutputIterator __result) 04970 { 04971 // concept requirements 04972 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>) 04973 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>) 04974 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, 04975 typename iterator_traits<_InputIterator1>::value_type>) 04976 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, 04977 typename iterator_traits<_InputIterator2>::value_type>) 04978 __glibcxx_function_requires(_LessThanOpConcept< 04979 typename iterator_traits<_InputIterator1>::value_type, 04980 typename iterator_traits<_InputIterator2>::value_type>) 04981 __glibcxx_function_requires(_LessThanOpConcept< 04982 typename iterator_traits<_InputIterator2>::value_type, 04983 typename iterator_traits<_InputIterator1>::value_type>) 04984 __glibcxx_requires_sorted_set(__first1, __last1, __first2); 04985 __glibcxx_requires_sorted_set(__first2, __last2, __first1); 04986 04987 return _GLIBCXX_STD_A::__set_union(__first1, __last1, 04988 __first2, __last2, __result, 04989 __gnu_cxx::__ops::__iter_less_iter()); 04990 } 04991 04992 /** 04993 * @brief Return the union of two sorted ranges using a comparison functor. 04994 * @ingroup set_algorithms 04995 * @param __first1 Start of first range. 04996 * @param __last1 End of first range. 04997 * @param __first2 Start of second range. 04998 * @param __last2 End of second range. 04999 * @param __comp The comparison functor. 05000 * @return End of the output range. 05001 * @ingroup set_algorithms 05002 * 05003 * This operation iterates over both ranges, copying elements present in 05004 * each range in order to the output range. Iterators increment for each 05005 * range. When the current element of one range is less than the other 05006 * according to @p __comp, that element is copied and the iterator advanced. 05007 * If an equivalent element according to @p __comp is contained in both 05008 * ranges, the element from the first range is copied and both ranges 05009 * advance. The output range may not overlap either input range. 05010 */ 05011 template<typename _InputIterator1, typename _InputIterator2, 05012 typename _OutputIterator, typename _Compare> 05013 inline _OutputIterator 05014 set_union(_InputIterator1 __first1, _InputIterator1 __last1, 05015 _InputIterator2 __first2, _InputIterator2 __last2, 05016 _OutputIterator __result, _Compare __comp) 05017 { 05018 // concept requirements 05019 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>) 05020 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>) 05021 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, 05022 typename iterator_traits<_InputIterator1>::value_type>) 05023 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, 05024 typename iterator_traits<_InputIterator2>::value_type>) 05025 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, 05026 typename iterator_traits<_InputIterator1>::value_type, 05027 typename iterator_traits<_InputIterator2>::value_type>) 05028 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, 05029 typename iterator_traits<_InputIterator2>::value_type, 05030 typename iterator_traits<_InputIterator1>::value_type>) 05031 __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp); 05032 __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp); 05033 05034 return _GLIBCXX_STD_A::__set_union(__first1, __last1, 05035 __first2, __last2, __result, 05036 __gnu_cxx::__ops::__iter_comp_iter(__comp)); 05037 } 05038 05039 template<typename _InputIterator1, typename _InputIterator2, 05040 typename _OutputIterator, 05041 typename _Compare> 05042 _OutputIterator 05043 __set_intersection(_InputIterator1 __first1, _InputIterator1 __last1, 05044 _InputIterator2 __first2, _InputIterator2 __last2, 05045 _OutputIterator __result, _Compare __comp) 05046 { 05047 while (__first1 != __last1 && __first2 != __last2) 05048 if (__comp(__first1, __first2)) 05049 ++__first1; 05050 else if (__comp(__first2, __first1)) 05051 ++__first2; 05052 else 05053 { 05054 *__result = *__first1; 05055 ++__first1; 05056 ++__first2; 05057 ++__result; 05058 } 05059 return __result; 05060 } 05061 05062 /** 05063 * @brief Return the intersection of two sorted ranges. 05064 * @ingroup set_algorithms 05065 * @param __first1 Start of first range. 05066 * @param __last1 End of first range. 05067 * @param __first2 Start of second range. 05068 * @param __last2 End of second range. 05069 * @return End of the output range. 05070 * @ingroup set_algorithms 05071 * 05072 * This operation iterates over both ranges, copying elements present in 05073 * both ranges in order to the output range. Iterators increment for each 05074 * range. When the current element of one range is less than the other, 05075 * that iterator advances. If an element is contained in both ranges, the 05076 * element from the first range is copied and both ranges advance. The 05077 * output range may not overlap either input range. 05078 */ 05079 template<typename _InputIterator1, typename _InputIterator2, 05080 typename _OutputIterator> 05081 inline _OutputIterator 05082 set_intersection(_InputIterator1 __first1, _InputIterator1 __last1, 05083 _InputIterator2 __first2, _InputIterator2 __last2, 05084 _OutputIterator __result) 05085 { 05086 // concept requirements 05087 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>) 05088 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>) 05089 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, 05090 typename iterator_traits<_InputIterator1>::value_type>) 05091 __glibcxx_function_requires(_LessThanOpConcept< 05092 typename iterator_traits<_InputIterator1>::value_type, 05093 typename iterator_traits<_InputIterator2>::value_type>) 05094 __glibcxx_function_requires(_LessThanOpConcept< 05095 typename iterator_traits<_InputIterator2>::value_type, 05096 typename iterator_traits<_InputIterator1>::value_type>) 05097 __glibcxx_requires_sorted_set(__first1, __last1, __first2); 05098 __glibcxx_requires_sorted_set(__first2, __last2, __first1); 05099 05100 return _GLIBCXX_STD_A::__set_intersection(__first1, __last1, 05101 __first2, __last2, __result, 05102 __gnu_cxx::__ops::__iter_less_iter()); 05103 } 05104 05105 /** 05106 * @brief Return the intersection of two sorted ranges using comparison 05107 * functor. 05108 * @ingroup set_algorithms 05109 * @param __first1 Start of first range. 05110 * @param __last1 End of first range. 05111 * @param __first2 Start of second range. 05112 * @param __last2 End of second range. 05113 * @param __comp The comparison functor. 05114 * @return End of the output range. 05115 * @ingroup set_algorithms 05116 * 05117 * This operation iterates over both ranges, copying elements present in 05118 * both ranges in order to the output range. Iterators increment for each 05119 * range. When the current element of one range is less than the other 05120 * according to @p __comp, that iterator advances. If an element is 05121 * contained in both ranges according to @p __comp, the element from the 05122 * first range is copied and both ranges advance. The output range may not 05123 * overlap either input range. 05124 */ 05125 template<typename _InputIterator1, typename _InputIterator2, 05126 typename _OutputIterator, typename _Compare> 05127 inline _OutputIterator 05128 set_intersection(_InputIterator1 __first1, _InputIterator1 __last1, 05129 _InputIterator2 __first2, _InputIterator2 __last2, 05130 _OutputIterator __result, _Compare __comp) 05131 { 05132 // concept requirements 05133 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>) 05134 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>) 05135 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, 05136 typename iterator_traits<_InputIterator1>::value_type>) 05137 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, 05138 typename iterator_traits<_InputIterator1>::value_type, 05139 typename iterator_traits<_InputIterator2>::value_type>) 05140 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, 05141 typename iterator_traits<_InputIterator2>::value_type, 05142 typename iterator_traits<_InputIterator1>::value_type>) 05143 __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp); 05144 __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp); 05145 05146 return _GLIBCXX_STD_A::__set_intersection(__first1, __last1, 05147 __first2, __last2, __result, 05148 __gnu_cxx::__ops::__iter_comp_iter(__comp)); 05149 } 05150 05151 template<typename _InputIterator1, typename _InputIterator2, 05152 typename _OutputIterator, 05153 typename _Compare> 05154 _OutputIterator 05155 __set_difference(_InputIterator1 __first1, _InputIterator1 __last1, 05156 _InputIterator2 __first2, _InputIterator2 __last2, 05157 _OutputIterator __result, _Compare __comp) 05158 { 05159 while (__first1 != __last1 && __first2 != __last2) 05160 if (__comp(__first1, __first2)) 05161 { 05162 *__result = *__first1; 05163 ++__first1; 05164 ++__result; 05165 } 05166 else if (__comp(__first2, __first1)) 05167 ++__first2; 05168 else 05169 { 05170 ++__first1; 05171 ++__first2; 05172 } 05173 return std::copy(__first1, __last1, __result); 05174 } 05175 05176 /** 05177 * @brief Return the difference of two sorted ranges. 05178 * @ingroup set_algorithms 05179 * @param __first1 Start of first range. 05180 * @param __last1 End of first range. 05181 * @param __first2 Start of second range. 05182 * @param __last2 End of second range. 05183 * @return End of the output range. 05184 * @ingroup set_algorithms 05185 * 05186 * This operation iterates over both ranges, copying elements present in 05187 * the first range but not the second in order to the output range. 05188 * Iterators increment for each range. When the current element of the 05189 * first range is less than the second, that element is copied and the 05190 * iterator advances. If the current element of the second range is less, 05191 * the iterator advances, but no element is copied. If an element is 05192 * contained in both ranges, no elements are copied and both ranges 05193 * advance. The output range may not overlap either input range. 05194 */ 05195 template<typename _InputIterator1, typename _InputIterator2, 05196 typename _OutputIterator> 05197 inline _OutputIterator 05198 set_difference(_InputIterator1 __first1, _InputIterator1 __last1, 05199 _InputIterator2 __first2, _InputIterator2 __last2, 05200 _OutputIterator __result) 05201 { 05202 // concept requirements 05203 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>) 05204 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>) 05205 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, 05206 typename iterator_traits<_InputIterator1>::value_type>) 05207 __glibcxx_function_requires(_LessThanOpConcept< 05208 typename iterator_traits<_InputIterator1>::value_type, 05209 typename iterator_traits<_InputIterator2>::value_type>) 05210 __glibcxx_function_requires(_LessThanOpConcept< 05211 typename iterator_traits<_InputIterator2>::value_type, 05212 typename iterator_traits<_InputIterator1>::value_type>) 05213 __glibcxx_requires_sorted_set(__first1, __last1, __first2); 05214 __glibcxx_requires_sorted_set(__first2, __last2, __first1); 05215 05216 return _GLIBCXX_STD_A::__set_difference(__first1, __last1, 05217 __first2, __last2, __result, 05218 __gnu_cxx::__ops::__iter_less_iter()); 05219 } 05220 05221 /** 05222 * @brief Return the difference of two sorted ranges using comparison 05223 * functor. 05224 * @ingroup set_algorithms 05225 * @param __first1 Start of first range. 05226 * @param __last1 End of first range. 05227 * @param __first2 Start of second range. 05228 * @param __last2 End of second range. 05229 * @param __comp The comparison functor. 05230 * @return End of the output range. 05231 * @ingroup set_algorithms 05232 * 05233 * This operation iterates over both ranges, copying elements present in 05234 * the first range but not the second in order to the output range. 05235 * Iterators increment for each range. When the current element of the 05236 * first range is less than the second according to @p __comp, that element 05237 * is copied and the iterator advances. If the current element of the 05238 * second range is less, no element is copied and the iterator advances. 05239 * If an element is contained in both ranges according to @p __comp, no 05240 * elements are copied and both ranges advance. The output range may not 05241 * overlap either input range. 05242 */ 05243 template<typename _InputIterator1, typename _InputIterator2, 05244 typename _OutputIterator, typename _Compare> 05245 inline _OutputIterator 05246 set_difference(_InputIterator1 __first1, _InputIterator1 __last1, 05247 _InputIterator2 __first2, _InputIterator2 __last2, 05248 _OutputIterator __result, _Compare __comp) 05249 { 05250 // concept requirements 05251 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>) 05252 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>) 05253 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, 05254 typename iterator_traits<_InputIterator1>::value_type>) 05255 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, 05256 typename iterator_traits<_InputIterator1>::value_type, 05257 typename iterator_traits<_InputIterator2>::value_type>) 05258 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, 05259 typename iterator_traits<_InputIterator2>::value_type, 05260 typename iterator_traits<_InputIterator1>::value_type>) 05261 __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp); 05262 __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp); 05263 05264 return _GLIBCXX_STD_A::__set_difference(__first1, __last1, 05265 __first2, __last2, __result, 05266 __gnu_cxx::__ops::__iter_comp_iter(__comp)); 05267 } 05268 05269 template<typename _InputIterator1, typename _InputIterator2, 05270 typename _OutputIterator, 05271 typename _Compare> 05272 _OutputIterator 05273 __set_symmetric_difference(_InputIterator1 __first1, 05274 _InputIterator1 __last1, 05275 _InputIterator2 __first2, 05276 _InputIterator2 __last2, 05277 _OutputIterator __result, 05278 _Compare __comp) 05279 { 05280 while (__first1 != __last1 && __first2 != __last2) 05281 if (__comp(__first1, __first2)) 05282 { 05283 *__result = *__first1; 05284 ++__first1; 05285 ++__result; 05286 } 05287 else if (__comp(__first2, __first1)) 05288 { 05289 *__result = *__first2; 05290 ++__first2; 05291 ++__result; 05292 } 05293 else 05294 { 05295 ++__first1; 05296 ++__first2; 05297 } 05298 return std::copy(__first2, __last2, 05299 std::copy(__first1, __last1, __result)); 05300 } 05301 05302 /** 05303 * @brief Return the symmetric difference of two sorted ranges. 05304 * @ingroup set_algorithms 05305 * @param __first1 Start of first range. 05306 * @param __last1 End of first range. 05307 * @param __first2 Start of second range. 05308 * @param __last2 End of second range. 05309 * @return End of the output range. 05310 * @ingroup set_algorithms 05311 * 05312 * This operation iterates over both ranges, copying elements present in 05313 * one range but not the other in order to the output range. Iterators 05314 * increment for each range. When the current element of one range is less 05315 * than the other, that element is copied and the iterator advances. If an 05316 * element is contained in both ranges, no elements are copied and both 05317 * ranges advance. The output range may not overlap either input range. 05318 */ 05319 template<typename _InputIterator1, typename _InputIterator2, 05320 typename _OutputIterator> 05321 inline _OutputIterator 05322 set_symmetric_difference(_InputIterator1 __first1, _InputIterator1 __last1, 05323 _InputIterator2 __first2, _InputIterator2 __last2, 05324 _OutputIterator __result) 05325 { 05326 // concept requirements 05327 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>) 05328 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>) 05329 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, 05330 typename iterator_traits<_InputIterator1>::value_type>) 05331 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, 05332 typename iterator_traits<_InputIterator2>::value_type>) 05333 __glibcxx_function_requires(_LessThanOpConcept< 05334 typename iterator_traits<_InputIterator1>::value_type, 05335 typename iterator_traits<_InputIterator2>::value_type>) 05336 __glibcxx_function_requires(_LessThanOpConcept< 05337 typename iterator_traits<_InputIterator2>::value_type, 05338 typename iterator_traits<_InputIterator1>::value_type>) 05339 __glibcxx_requires_sorted_set(__first1, __last1, __first2); 05340 __glibcxx_requires_sorted_set(__first2, __last2, __first1); 05341 05342 return _GLIBCXX_STD_A::__set_symmetric_difference(__first1, __last1, 05343 __first2, __last2, __result, 05344 __gnu_cxx::__ops::__iter_less_iter()); 05345 } 05346 05347 /** 05348 * @brief Return the symmetric difference of two sorted ranges using 05349 * comparison functor. 05350 * @ingroup set_algorithms 05351 * @param __first1 Start of first range. 05352 * @param __last1 End of first range. 05353 * @param __first2 Start of second range. 05354 * @param __last2 End of second range. 05355 * @param __comp The comparison functor. 05356 * @return End of the output range. 05357 * @ingroup set_algorithms 05358 * 05359 * This operation iterates over both ranges, copying elements present in 05360 * one range but not the other in order to the output range. Iterators 05361 * increment for each range. When the current element of one range is less 05362 * than the other according to @p comp, that element is copied and the 05363 * iterator advances. If an element is contained in both ranges according 05364 * to @p __comp, no elements are copied and both ranges advance. The output 05365 * range may not overlap either input range. 05366 */ 05367 template<typename _InputIterator1, typename _InputIterator2, 05368 typename _OutputIterator, typename _Compare> 05369 inline _OutputIterator 05370 set_symmetric_difference(_InputIterator1 __first1, _InputIterator1 __last1, 05371 _InputIterator2 __first2, _InputIterator2 __last2, 05372 _OutputIterator __result, 05373 _Compare __comp) 05374 { 05375 // concept requirements 05376 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>) 05377 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>) 05378 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, 05379 typename iterator_traits<_InputIterator1>::value_type>) 05380 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, 05381 typename iterator_traits<_InputIterator2>::value_type>) 05382 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, 05383 typename iterator_traits<_InputIterator1>::value_type, 05384 typename iterator_traits<_InputIterator2>::value_type>) 05385 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, 05386 typename iterator_traits<_InputIterator2>::value_type, 05387 typename iterator_traits<_InputIterator1>::value_type>) 05388 __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp); 05389 __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp); 05390 05391 return _GLIBCXX_STD_A::__set_symmetric_difference(__first1, __last1, 05392 __first2, __last2, __result, 05393 __gnu_cxx::__ops::__iter_comp_iter(__comp)); 05394 } 05395 05396 template<typename _ForwardIterator, typename _Compare> 05397 _ForwardIterator 05398 __min_element(_ForwardIterator __first, _ForwardIterator __last, 05399 _Compare __comp) 05400 { 05401 if (__first == __last) 05402 return __first; 05403 _ForwardIterator __result = __first; 05404 while (++__first != __last) 05405 if (__comp(__first, __result)) 05406 __result = __first; 05407 return __result; 05408 } 05409 05410 /** 05411 * @brief Return the minimum element in a range. 05412 * @ingroup sorting_algorithms 05413 * @param __first Start of range. 05414 * @param __last End of range. 05415 * @return Iterator referencing the first instance of the smallest value. 05416 */ 05417 template<typename _ForwardIterator> 05418 _ForwardIterator 05419 inline min_element(_ForwardIterator __first, _ForwardIterator __last) 05420 { 05421 // concept requirements 05422 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) 05423 __glibcxx_function_requires(_LessThanComparableConcept< 05424 typename iterator_traits<_ForwardIterator>::value_type>) 05425 __glibcxx_requires_valid_range(__first, __last); 05426 05427 return _GLIBCXX_STD_A::__min_element(__first, __last, 05428 __gnu_cxx::__ops::__iter_less_iter()); 05429 } 05430 05431 /** 05432 * @brief Return the minimum element in a range using comparison functor. 05433 * @ingroup sorting_algorithms 05434 * @param __first Start of range. 05435 * @param __last End of range. 05436 * @param __comp Comparison functor. 05437 * @return Iterator referencing the first instance of the smallest value 05438 * according to __comp. 05439 */ 05440 template<typename _ForwardIterator, typename _Compare> 05441 inline _ForwardIterator 05442 min_element(_ForwardIterator __first, _ForwardIterator __last, 05443 _Compare __comp) 05444 { 05445 // concept requirements 05446 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) 05447 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, 05448 typename iterator_traits<_ForwardIterator>::value_type, 05449 typename iterator_traits<_ForwardIterator>::value_type>) 05450 __glibcxx_requires_valid_range(__first, __last); 05451 05452 return _GLIBCXX_STD_A::__min_element(__first, __last, 05453 __gnu_cxx::__ops::__iter_comp_iter(__comp)); 05454 } 05455 05456 template<typename _ForwardIterator, typename _Compare> 05457 _ForwardIterator 05458 __max_element(_ForwardIterator __first, _ForwardIterator __last, 05459 _Compare __comp) 05460 { 05461 if (__first == __last) return __first; 05462 _ForwardIterator __result = __first; 05463 while (++__first != __last) 05464 if (__comp(__result, __first)) 05465 __result = __first; 05466 return __result; 05467 } 05468 05469 /** 05470 * @brief Return the maximum element in a range. 05471 * @ingroup sorting_algorithms 05472 * @param __first Start of range. 05473 * @param __last End of range. 05474 * @return Iterator referencing the first instance of the largest value. 05475 */ 05476 template<typename _ForwardIterator> 05477 inline _ForwardIterator 05478 max_element(_ForwardIterator __first, _ForwardIterator __last) 05479 { 05480 // concept requirements 05481 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) 05482 __glibcxx_function_requires(_LessThanComparableConcept< 05483 typename iterator_traits<_ForwardIterator>::value_type>) 05484 __glibcxx_requires_valid_range(__first, __last); 05485 05486 return _GLIBCXX_STD_A::__max_element(__first, __last, 05487 __gnu_cxx::__ops::__iter_less_iter()); 05488 } 05489 05490 /** 05491 * @brief Return the maximum element in a range using comparison functor. 05492 * @ingroup sorting_algorithms 05493 * @param __first Start of range. 05494 * @param __last End of range. 05495 * @param __comp Comparison functor. 05496 * @return Iterator referencing the first instance of the largest value 05497 * according to __comp. 05498 */ 05499 template<typename _ForwardIterator, typename _Compare> 05500 inline _ForwardIterator 05501 max_element(_ForwardIterator __first, _ForwardIterator __last, 05502 _Compare __comp) 05503 { 05504 // concept requirements 05505 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) 05506 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, 05507 typename iterator_traits<_ForwardIterator>::value_type, 05508 typename iterator_traits<_ForwardIterator>::value_type>) 05509 __glibcxx_requires_valid_range(__first, __last); 05510 05511 return _GLIBCXX_STD_A::__max_element(__first, __last, 05512 __gnu_cxx::__ops::__iter_comp_iter(__comp)); 05513 } 05514 05515 _GLIBCXX_END_NAMESPACE_ALGO 05516 } // namespace std 05517 05518 #endif /* _STL_ALGO_H */